1 /* Hooks for cfg representation specific functions.
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010, 2011, 2012
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 (current_loops
!= NULL
)
729 /* If the block we merge into is a loop header do nothing unless ... */
730 if (a
->loop_father
->header
== a
)
732 /* ... we merge two loop headers, in which case we kill
734 if (b
->loop_father
->header
== b
)
736 b
->loop_father
->header
= NULL
;
737 b
->loop_father
->latch
= NULL
;
738 loops_state_set (LOOPS_NEED_FIXUP
);
741 /* If we merge a loop header into its predecessor, update the loop
743 else if (b
->loop_father
->header
== b
)
745 remove_bb_from_loops (a
);
746 add_bb_to_loop (a
, b
->loop_father
);
747 a
->loop_father
->header
= a
;
749 remove_bb_from_loops (b
);
752 /* Normally there should only be one successor of A and that is B, but
753 partway though the merge of blocks for conditional_execution we'll
754 be merging a TEST block with THEN and ELSE successors. Free the
755 whole lot of them and hope the caller knows what they're doing. */
757 while (EDGE_COUNT (a
->succs
) != 0)
758 remove_edge (EDGE_SUCC (a
, 0));
760 /* Adjust the edges out of B for the new owner. */
761 FOR_EACH_EDGE (e
, ei
, b
->succs
)
764 if (current_loops
!= NULL
)
765 rescan_loop_exit (e
, true, false);
768 a
->flags
|= b
->flags
;
770 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
771 b
->preds
= b
->succs
= NULL
;
773 if (dom_info_available_p (CDI_DOMINATORS
))
774 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
776 if (dom_info_available_p (CDI_DOMINATORS
))
777 delete_from_dominance_info (CDI_DOMINATORS
, b
);
778 if (dom_info_available_p (CDI_POST_DOMINATORS
))
779 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
784 /* Split BB into entry part and the rest (the rest is the newly created block).
785 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
786 part. Returns the edge connecting the entry part to the rest. */
789 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
790 void (*new_bb_cbk
) (basic_block
))
794 basic_block dummy
, jump
;
795 struct loop
*loop
, *ploop
, *cloop
;
797 if (!cfg_hooks
->make_forwarder_block
)
798 internal_error ("%s does not support make_forwarder_block",
801 fallthru
= split_block_after_labels (bb
);
802 dummy
= fallthru
->src
;
805 /* Redirect back edges we want to keep. */
806 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
810 if (redirect_edge_p (e
))
816 dummy
->frequency
-= EDGE_FREQUENCY (e
);
817 dummy
->count
-= e
->count
;
818 if (dummy
->frequency
< 0)
819 dummy
->frequency
= 0;
820 if (dummy
->count
< 0)
822 fallthru
->count
-= e
->count
;
823 if (fallthru
->count
< 0)
827 jump
= redirect_edge_and_branch_force (e
, bb
);
830 /* If we redirected the loop latch edge, the JUMP block now acts like
831 the new latch of the loop. */
832 if (current_loops
!= NULL
833 && dummy
->loop_father
!= NULL
834 && dummy
->loop_father
->header
== dummy
835 && dummy
->loop_father
->latch
== e_src
)
836 dummy
->loop_father
->latch
= jump
;
838 if (new_bb_cbk
!= NULL
)
843 if (dom_info_available_p (CDI_DOMINATORS
))
845 vec
<basic_block
> doms_to_fix
;
846 doms_to_fix
.create (2);
847 doms_to_fix
.quick_push (dummy
);
848 doms_to_fix
.quick_push (bb
);
849 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
850 doms_to_fix
.release ();
853 if (current_loops
!= NULL
)
855 /* If we do not split a loop header, then both blocks belong to the
856 same loop. In case we split loop header and do not redirect the
857 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
858 BB becomes the new header. If latch is not recorded for the loop,
859 we leave this updating on the caller (this may only happen during
861 loop
= dummy
->loop_father
;
862 if (loop
->header
== dummy
863 && loop
->latch
!= NULL
864 && find_edge (loop
->latch
, dummy
) == NULL
)
866 remove_bb_from_loops (dummy
);
870 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
872 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
874 add_bb_to_loop (dummy
, cloop
);
877 /* In case we split loop latch, update it. */
878 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
879 if (ploop
->latch
== dummy
)
883 cfg_hooks
->make_forwarder_block (fallthru
);
888 /* Try to make the edge fallthru. */
891 tidy_fallthru_edge (edge e
)
893 if (cfg_hooks
->tidy_fallthru_edge
)
894 cfg_hooks
->tidy_fallthru_edge (e
);
897 /* Fix up edges that now fall through, or rather should now fall through
898 but previously required a jump around now deleted blocks. Simplify
899 the search by only examining blocks numerically adjacent, since this
900 is how they were created.
902 ??? This routine is currently RTL specific. */
905 tidy_fallthru_edges (void)
909 if (!cfg_hooks
->tidy_fallthru_edge
)
912 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
915 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, next_bb
)
921 /* We care about simple conditional or unconditional jumps with
924 If we had a conditional branch to the next instruction when
925 CFG was built, then there will only be one out edge for the
926 block which ended with the conditional branch (since we do
927 not create duplicate edges).
929 Furthermore, the edge will be marked as a fallthru because we
930 merge the flags for the duplicate edges. So we do not want to
931 check that the edge is not a FALLTHRU edge. */
933 if (single_succ_p (b
))
935 s
= single_succ_edge (b
);
936 if (! (s
->flags
& EDGE_COMPLEX
)
938 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
939 tidy_fallthru_edge (s
);
944 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
945 (and possibly create new basic block) to make edge non-fallthru.
946 Return newly created BB or NULL if none. */
949 force_nonfallthru (edge e
)
951 basic_block ret
, src
= e
->src
;
953 if (!cfg_hooks
->force_nonfallthru
)
954 internal_error ("%s does not support force_nonfallthru",
957 ret
= cfg_hooks
->force_nonfallthru (e
);
960 if (dom_info_available_p (CDI_DOMINATORS
))
961 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
963 if (current_loops
!= NULL
)
966 = find_common_loop (single_pred (ret
)->loop_father
,
967 single_succ (ret
)->loop_father
);
968 rescan_loop_exit (e
, false, true);
969 add_bb_to_loop (ret
, loop
);
976 /* Returns true if we can duplicate basic block BB. */
979 can_duplicate_block_p (const_basic_block bb
)
981 if (!cfg_hooks
->can_duplicate_block_p
)
982 internal_error ("%s does not support can_duplicate_block_p",
985 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
)
988 return cfg_hooks
->can_duplicate_block_p (bb
);
991 /* Duplicates basic block BB and redirects edge E to it. Returns the
992 new basic block. The new basic block is placed after the basic block
996 duplicate_block (basic_block bb
, edge e
, basic_block after
)
1000 gcov_type new_count
= e
? e
->count
: 0;
1003 if (!cfg_hooks
->duplicate_block
)
1004 internal_error ("%s does not support duplicate_block",
1007 if (bb
->count
< new_count
)
1008 new_count
= bb
->count
;
1010 gcc_checking_assert (can_duplicate_block_p (bb
));
1012 new_bb
= cfg_hooks
->duplicate_block (bb
);
1014 move_block_after (new_bb
, after
);
1016 new_bb
->flags
= bb
->flags
;
1017 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
1019 /* Since we are creating edges from a new block to successors
1020 of another block (which therefore are known to be disjoint), there
1021 is no need to actually check for duplicated edges. */
1022 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
1023 n
->probability
= s
->probability
;
1026 /* Take care for overflows! */
1027 n
->count
= s
->count
* (new_count
* 10000 / bb
->count
) / 10000;
1028 s
->count
-= n
->count
;
1031 n
->count
= s
->count
;
1037 new_bb
->count
= new_count
;
1038 bb
->count
-= new_count
;
1040 new_bb
->frequency
= EDGE_FREQUENCY (e
);
1041 bb
->frequency
-= EDGE_FREQUENCY (e
);
1043 redirect_edge_and_branch_force (e
, new_bb
);
1047 if (bb
->frequency
< 0)
1052 new_bb
->count
= bb
->count
;
1053 new_bb
->frequency
= bb
->frequency
;
1056 set_bb_original (new_bb
, bb
);
1057 set_bb_copy (bb
, new_bb
);
1059 /* Add the new block to the copy of the loop of BB, or directly to the loop
1060 of BB if the loop is not being copied. */
1061 if (current_loops
!= NULL
)
1063 struct loop
*cloop
= bb
->loop_father
;
1064 struct loop
*copy
= get_loop_copy (cloop
);
1065 /* If we copied the loop header block but not the loop
1066 we have created a loop with multiple entries. Ditch the loop,
1067 add the new block to the outer loop and arrange for a fixup. */
1069 && cloop
->header
== bb
)
1071 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1072 cloop
->header
= NULL
;
1073 cloop
->latch
= NULL
;
1074 loops_state_set (LOOPS_NEED_FIXUP
);
1078 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1079 /* If we copied the loop latch block but not the loop, adjust
1082 && cloop
->latch
== bb
)
1084 cloop
->latch
= NULL
;
1085 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1093 /* Return 1 if BB ends with a call, possibly followed by some
1094 instructions that must stay with the call, 0 otherwise. */
1097 block_ends_with_call_p (basic_block bb
)
1099 if (!cfg_hooks
->block_ends_with_call_p
)
1100 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1102 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1105 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1108 block_ends_with_condjump_p (const_basic_block bb
)
1110 if (!cfg_hooks
->block_ends_with_condjump_p
)
1111 internal_error ("%s does not support block_ends_with_condjump_p",
1114 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1117 /* Add fake edges to the function exit for any non constant and non noreturn
1118 calls, volatile inline assembly in the bitmap of blocks specified by
1119 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1122 The goal is to expose cases in which entering a basic block does not imply
1123 that all subsequent instructions must be executed. */
1126 flow_call_edges_add (sbitmap blocks
)
1128 if (!cfg_hooks
->flow_call_edges_add
)
1129 internal_error ("%s does not support flow_call_edges_add",
1132 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1135 /* This function is called immediately after edge E is added to the
1136 edge vector E->dest->preds. */
1139 execute_on_growing_pred (edge e
)
1141 if (cfg_hooks
->execute_on_growing_pred
)
1142 cfg_hooks
->execute_on_growing_pred (e
);
1145 /* This function is called immediately before edge E is removed from
1146 the edge vector E->dest->preds. */
1149 execute_on_shrinking_pred (edge e
)
1151 if (cfg_hooks
->execute_on_shrinking_pred
)
1152 cfg_hooks
->execute_on_shrinking_pred (e
);
1155 /* This is used inside loop versioning when we want to insert
1156 stmts/insns on the edges, which have a different behavior
1157 in tree's and in RTL, so we made a CFG hook. */
1159 lv_flush_pending_stmts (edge e
)
1161 if (cfg_hooks
->flush_pending_stmts
)
1162 cfg_hooks
->flush_pending_stmts (e
);
1165 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1166 a new version of the loop basic-blocks, the parameters here are
1167 exactly the same as in duplicate_loop_to_header_edge or
1168 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1169 additional work to maintain ssa information that's why there is
1170 a need to call the tree_duplicate_loop_to_header_edge rather
1171 than duplicate_loop_to_header_edge when we are in tree mode. */
1173 cfg_hook_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1175 sbitmap wont_exit
, edge orig
,
1176 vec
<edge
> *to_remove
,
1179 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1180 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1186 /* Conditional jumps are represented differently in trees and RTL,
1187 this hook takes a basic block that is known to have a cond jump
1188 at its end and extracts the taken and not taken edges out of it
1189 and store it in E1 and E2 respectively. */
1191 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1193 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1194 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1197 /* Responsible for updating the ssa info (PHI nodes) on the
1198 new condition basic block that guards the versioned loop. */
1200 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1201 basic_block new_block
, edge e
)
1203 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1204 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1207 /* Conditions in trees and RTL are different so we need
1208 a different handling when we add the condition to the
1211 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1212 basic_block new_block
, void *cond
)
1214 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1215 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1218 /* Checks whether all N blocks in BBS array can be copied. */
1220 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1226 for (i
= 0; i
< n
; i
++)
1227 bbs
[i
]->flags
|= BB_DUPLICATED
;
1229 for (i
= 0; i
< n
; i
++)
1231 /* In case we should redirect abnormal edge during duplication, fail. */
1233 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1234 if ((e
->flags
& EDGE_ABNORMAL
)
1235 && (e
->dest
->flags
& BB_DUPLICATED
))
1241 if (!can_duplicate_block_p (bbs
[i
]))
1249 for (i
= 0; i
< n
; i
++)
1250 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1255 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1256 are placed into array NEW_BBS in the same order. Edges from basic blocks
1257 in BBS are also duplicated and copies of those of them
1258 that lead into BBS are redirected to appropriate newly created block. The
1259 function assigns bbs into loops (copy of basic block bb is assigned to
1260 bb->loop_father->copy loop, so this must be set up correctly in advance)
1261 and updates dominators locally (LOOPS structure that contains the information
1262 about dominators is passed to enable this).
1264 BASE is the superloop to that basic block belongs; if its header or latch
1265 is copied, we do not set the new blocks as header or latch.
1267 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1268 also in the same order.
1270 Newly created basic blocks are put after the basic block AFTER in the
1271 instruction stream, and the order of the blocks in BBS array is preserved. */
1274 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1275 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1276 struct loop
*base
, basic_block after
)
1279 basic_block bb
, new_bb
, dom_bb
;
1282 /* Duplicate bbs, update dominators, assign bbs to loops. */
1283 for (i
= 0; i
< n
; i
++)
1287 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1289 bb
->flags
|= BB_DUPLICATED
;
1290 if (bb
->loop_father
)
1292 /* Possibly set loop header. */
1293 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1294 new_bb
->loop_father
->header
= new_bb
;
1296 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1297 new_bb
->loop_father
->latch
= new_bb
;
1301 /* Set dominators. */
1302 for (i
= 0; i
< n
; i
++)
1305 new_bb
= new_bbs
[i
];
1307 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1308 if (dom_bb
->flags
& BB_DUPLICATED
)
1310 dom_bb
= get_bb_copy (dom_bb
);
1311 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1315 /* Redirect edges. */
1316 for (j
= 0; j
< num_edges
; j
++)
1317 new_edges
[j
] = NULL
;
1318 for (i
= 0; i
< n
; i
++)
1321 new_bb
= new_bbs
[i
];
1324 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1326 for (j
= 0; j
< num_edges
; j
++)
1327 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1330 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1332 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1336 /* Clear information about duplicates. */
1337 for (i
= 0; i
< n
; i
++)
1338 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1341 /* Return true if BB contains only labels or non-executable
1344 empty_block_p (basic_block bb
)
1346 gcc_assert (cfg_hooks
->empty_block_p
);
1347 return cfg_hooks
->empty_block_p (bb
);
1350 /* Split a basic block if it ends with a conditional branch and if
1351 the other part of the block is not empty. */
1353 split_block_before_cond_jump (basic_block bb
)
1355 gcc_assert (cfg_hooks
->split_block_before_cond_jump
);
1356 return cfg_hooks
->split_block_before_cond_jump (bb
);
1359 /* Work-horse for passes.c:check_profile_consistency.
1360 Do book-keeping of the CFG for the profile consistency checker.
1361 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
1362 then do post-pass accounting. Store the counting in RECORD. */
1365 account_profile_record (struct profile_record
*record
, int after_pass
)
1375 if (bb
!= EXIT_BLOCK_PTR_FOR_FUNCTION (cfun
)
1376 && profile_status
!= PROFILE_ABSENT
)
1379 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1380 sum
+= e
->probability
;
1381 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
1382 record
->num_mismatched_freq_out
[after_pass
]++;
1384 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1386 if (EDGE_COUNT (bb
->succs
)
1387 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
1388 record
->num_mismatched_count_out
[after_pass
]++;
1390 if (bb
!= ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
)
1391 && profile_status
!= PROFILE_ABSENT
)
1394 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1395 sum
+= EDGE_FREQUENCY (e
);
1396 if (abs (sum
- bb
->frequency
) > 100
1397 || (MAX (sum
, bb
->frequency
) > 10
1398 && abs ((sum
- bb
->frequency
) * 100 / (MAX (sum
, bb
->frequency
) + 1)) > 10))
1399 record
->num_mismatched_freq_in
[after_pass
]++;
1401 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1403 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
1404 record
->num_mismatched_count_in
[after_pass
]++;
1406 if (bb
== ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
)
1407 || bb
== EXIT_BLOCK_PTR_FOR_FUNCTION (cfun
))
1409 gcc_assert (cfg_hooks
->account_profile_record
);
1410 cfg_hooks
->account_profile_record(bb
, after_pass
, record
);