1 /* Hooks for cfg representation specific functions.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "pretty-print.h"
29 #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_for_fn (cfun
));
102 edge_checksum
= XCNEWVEC (size_t, last_basic_block_for_fn (cfun
));
104 /* Check bb chain & numbers. */
105 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
106 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
108 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
109 && bb
!= BASIC_BLOCK_FOR_FN (cfun
, 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_FN (bb
, cfun
)
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
);
144 if (!bb
->count
.verify ())
146 error ("verify_flow_info: Wrong count of block %i", bb
->index
);
149 if (bb
->frequency
< 0)
151 error ("verify_flow_info: Wrong frequency of block %i %i",
152 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 /* FIXME: Graphite and SLJL and target code still tends to produce
165 edges with no probablity. */
166 if (profile_status_for_fn (cfun
) >= PROFILE_GUESSED
167 && !e
->probability
.initialized_p () && 0)
169 error ("Uninitialized probability of edge %i->%i", e
->src
->index
,
173 if (!e
->probability
.verify ())
175 error ("verify_flow_info: Wrong probability of edge %i->%i",
176 e
->src
->index
, e
->dest
->index
);
180 last_visited
[e
->dest
->index
] = bb
;
182 if (e
->flags
& EDGE_FALLTHRU
)
187 error ("verify_flow_info: Basic block %d succ edge is corrupted",
189 fprintf (stderr
, "Predecessor: ");
190 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
191 fprintf (stderr
, "\nSuccessor: ");
192 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
193 fprintf (stderr
, "\n");
197 edge_checksum
[e
->dest
->index
] += (size_t) e
;
201 error ("wrong amount of branch edges after unconditional jump %i", bb
->index
);
205 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
209 error ("basic block %d pred edge is corrupted", bb
->index
);
210 fputs ("Predecessor: ", stderr
);
211 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
212 fputs ("\nSuccessor: ", stderr
);
213 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
214 fputc ('\n', stderr
);
218 if (ei
.index
!= e
->dest_idx
)
220 error ("basic block %d pred edge is corrupted", bb
->index
);
221 error ("its dest_idx should be %d, not %d",
222 ei
.index
, e
->dest_idx
);
223 fputs ("Predecessor: ", stderr
);
224 dump_edge_info (stderr
, e
, TDF_DETAILS
, 0);
225 fputs ("\nSuccessor: ", stderr
);
226 dump_edge_info (stderr
, e
, TDF_DETAILS
, 1);
227 fputc ('\n', stderr
);
231 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
235 /* Complete edge checksumming for ENTRY and EXIT. */
240 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
241 edge_checksum
[e
->dest
->index
] += (size_t) e
;
243 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
244 edge_checksum
[e
->dest
->index
] -= (size_t) e
;
247 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
248 if (edge_checksum
[bb
->index
])
250 error ("basic block %i edge lists are corrupted", bb
->index
);
254 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
258 free (edge_checksum
);
260 if (cfg_hooks
->verify_flow_info
)
261 err
|= cfg_hooks
->verify_flow_info ();
263 internal_error ("verify_flow_info failed");
264 timevar_pop (TV_CFG_VERIFY
);
267 /* Print out one basic block BB to file OUTF. INDENT is printed at the
268 start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
270 This function takes care of the purely graph related information.
271 The cfg hook for the active representation should dump
272 representation-specific information. */
275 dump_bb (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
)
277 if (flags
& TDF_BLOCKS
)
278 dump_bb_info (outf
, bb
, indent
, flags
, true, false);
279 if (cfg_hooks
->dump_bb
)
280 cfg_hooks
->dump_bb (outf
, bb
, indent
, flags
);
281 if (flags
& TDF_BLOCKS
)
282 dump_bb_info (outf
, bb
, indent
, flags
, false, true);
287 debug (basic_block_def
&ref
)
289 dump_bb (stderr
, &ref
, 0, 0);
293 debug (basic_block_def
*ptr
)
298 fprintf (stderr
, "<nil>\n");
302 /* Dumps basic block BB to pretty-printer PP, for use as a label of
303 a DOT graph record-node. The implementation of this hook is
304 expected to write the label to the stream that is attached to PP.
305 Field separators between instructions are pipe characters printed
306 verbatim. Instructions should be written with some characters
307 escaped, using pp_write_text_as_dot_label_to_stream(). */
310 dump_bb_for_graph (pretty_printer
*pp
, basic_block bb
)
312 if (!cfg_hooks
->dump_bb_for_graph
)
313 internal_error ("%s does not support dump_bb_for_graph",
315 /* TODO: Add pretty printer for counter. */
316 if (bb
->count
.initialized_p ())
317 pp_printf (pp
, "COUNT:" "%" PRId64
, bb
->count
.to_gcov_type ());
318 pp_printf (pp
, " FREQ:%i |", bb
->frequency
);
319 pp_write_text_to_stream (pp
);
320 if (!(dump_flags
& TDF_SLIM
))
321 cfg_hooks
->dump_bb_for_graph (pp
, bb
);
324 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
326 dump_flow_info (FILE *file
, dump_flags_t flags
)
330 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun
),
331 n_edges_for_fn (cfun
));
332 FOR_ALL_BB_FN (bb
, cfun
)
333 dump_bb (file
, bb
, 0, flags
);
338 /* Like above, but dump to stderr. To be called from debuggers. */
339 void debug_flow_info (void);
341 debug_flow_info (void)
343 dump_flow_info (stderr
, TDF_DETAILS
);
346 /* Redirect edge E to the given basic block DEST and update underlying program
347 representation. Returns edge representing redirected branch (that may not
348 be equivalent to E in the case of duplicate edges being removed) or NULL
349 if edge is not easily redirectable for whatever reason. */
352 redirect_edge_and_branch (edge e
, basic_block dest
)
356 if (!cfg_hooks
->redirect_edge_and_branch
)
357 internal_error ("%s does not support redirect_edge_and_branch",
360 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
362 /* If RET != E, then either the redirection failed, or the edge E
363 was removed since RET already lead to the same destination. */
364 if (current_loops
!= NULL
&& ret
== e
)
365 rescan_loop_exit (e
, false, false);
370 /* Returns true if it is possible to remove the edge E by redirecting it
371 to the destination of the other edge going from its source. */
374 can_remove_branch_p (const_edge e
)
376 if (!cfg_hooks
->can_remove_branch_p
)
377 internal_error ("%s does not support can_remove_branch_p",
380 if (EDGE_COUNT (e
->src
->succs
) != 2)
383 return cfg_hooks
->can_remove_branch_p (e
);
386 /* Removes E, by redirecting it to the destination of the other edge going
387 from its source. Can_remove_branch_p must be true for E, hence this
388 operation cannot fail. */
391 remove_branch (edge e
)
394 basic_block src
= e
->src
;
397 gcc_assert (EDGE_COUNT (e
->src
->succs
) == 2);
399 other
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
400 irr
= other
->flags
& EDGE_IRREDUCIBLE_LOOP
;
402 e
= redirect_edge_and_branch (e
, other
->dest
);
403 gcc_assert (e
!= NULL
);
405 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
409 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
414 if (current_loops
!= NULL
)
416 rescan_loop_exit (e
, false, true);
418 /* Removal of an edge inside an irreducible region or which leads
419 to an irreducible region can turn the region into a natural loop.
420 In that case, ask for the loop structure fixups.
422 FIXME: Note that LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS is not always
423 set, so always ask for fixups when removing an edge in that case. */
424 if (!loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
425 || (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
426 || (e
->dest
->flags
& BB_IRREDUCIBLE_LOOP
))
427 loops_state_set (LOOPS_NEED_FIXUP
);
430 /* This is probably not needed, but it doesn't hurt. */
431 /* FIXME: This should be called via a remove_edge hook. */
432 if (current_ir_type () == IR_GIMPLE
)
433 redirect_edge_var_map_clear (e
);
438 /* Like redirect_edge_succ but avoid possible duplicate edge. */
441 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
445 s
= find_edge (e
->src
, new_succ
);
448 s
->flags
|= e
->flags
;
449 s
->probability
+= e
->probability
;
450 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
451 redirect_edge_var_map_dup (s
, e
);
456 redirect_edge_succ (e
, new_succ
);
461 /* Redirect the edge E to basic block DEST even if it requires creating
462 of a new basic block; then it returns the newly created basic block.
463 Aborts when redirection is impossible. */
466 redirect_edge_and_branch_force (edge e
, basic_block dest
)
468 basic_block ret
, src
= e
->src
;
470 if (!cfg_hooks
->redirect_edge_and_branch_force
)
471 internal_error ("%s does not support redirect_edge_and_branch_force",
474 if (current_loops
!= NULL
)
475 rescan_loop_exit (e
, false, true);
477 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
479 if (ret
!= NULL
&& dom_info_available_p (CDI_DOMINATORS
))
480 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
482 if (current_loops
!= NULL
)
487 = find_common_loop (single_pred (ret
)->loop_father
,
488 single_succ (ret
)->loop_father
);
489 add_bb_to_loop (ret
, loop
);
491 else if (find_edge (src
, dest
) == e
)
492 rescan_loop_exit (e
, true, false);
498 /* Splits basic block BB after the specified instruction I (but at least after
499 the labels). If I is NULL, splits just after labels. The newly created edge
500 is returned. The new basic block is created just after the old one. */
503 split_block_1 (basic_block bb
, void *i
)
508 if (!cfg_hooks
->split_block
)
509 internal_error ("%s does not support split_block", cfg_hooks
->name
);
511 new_bb
= cfg_hooks
->split_block (bb
, i
);
515 new_bb
->count
= bb
->count
;
516 new_bb
->frequency
= bb
->frequency
;
517 new_bb
->discriminator
= bb
->discriminator
;
519 if (dom_info_available_p (CDI_DOMINATORS
))
521 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
522 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
525 if (current_loops
!= NULL
)
529 add_bb_to_loop (new_bb
, bb
->loop_father
);
530 /* Identify all loops bb may have been the latch of and adjust them. */
531 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
532 if (e
->dest
->loop_father
->latch
== bb
)
533 e
->dest
->loop_father
->latch
= new_bb
;
536 res
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
538 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
540 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
541 res
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
548 split_block (basic_block bb
, gimple
*i
)
550 return split_block_1 (bb
, i
);
554 split_block (basic_block bb
, rtx i
)
556 return split_block_1 (bb
, i
);
559 /* Splits block BB just after labels. The newly created edge is returned. */
562 split_block_after_labels (basic_block bb
)
564 return split_block_1 (bb
, NULL
);
567 /* Moves block BB immediately after block AFTER. Returns false if the
568 movement was impossible. */
571 move_block_after (basic_block bb
, basic_block after
)
575 if (!cfg_hooks
->move_block_after
)
576 internal_error ("%s does not support move_block_after", cfg_hooks
->name
);
578 ret
= cfg_hooks
->move_block_after (bb
, after
);
583 /* Deletes the basic block BB. */
586 delete_basic_block (basic_block bb
)
588 if (!cfg_hooks
->delete_basic_block
)
589 internal_error ("%s does not support delete_basic_block", cfg_hooks
->name
);
591 cfg_hooks
->delete_basic_block (bb
);
593 if (current_loops
!= NULL
)
595 struct loop
*loop
= bb
->loop_father
;
597 /* If we remove the header or the latch of a loop, mark the loop for
599 if (loop
->latch
== bb
600 || loop
->header
== bb
)
601 mark_loop_for_removal (loop
);
603 remove_bb_from_loops (bb
);
606 /* Remove the edges into and out of this block. Note that there may
607 indeed be edges in, if we are removing an unreachable loop. */
608 while (EDGE_COUNT (bb
->preds
) != 0)
609 remove_edge (EDGE_PRED (bb
, 0));
610 while (EDGE_COUNT (bb
->succs
) != 0)
611 remove_edge (EDGE_SUCC (bb
, 0));
613 if (dom_info_available_p (CDI_DOMINATORS
))
614 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
615 if (dom_info_available_p (CDI_POST_DOMINATORS
))
616 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
618 /* Remove the basic block from the array. */
622 /* Splits edge E and returns the newly created basic block. */
628 profile_count count
= e
->count ();
629 int freq
= EDGE_FREQUENCY (e
);
631 bool irr
= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
633 basic_block src
= e
->src
, dest
= e
->dest
;
635 if (!cfg_hooks
->split_edge
)
636 internal_error ("%s does not support split_edge", cfg_hooks
->name
);
638 if (current_loops
!= NULL
)
639 rescan_loop_exit (e
, false, true);
641 ret
= cfg_hooks
->split_edge (e
);
643 ret
->frequency
= freq
;
644 single_succ_edge (ret
)->probability
= profile_probability::always ();
648 ret
->flags
|= BB_IRREDUCIBLE_LOOP
;
649 single_pred_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
650 single_succ_edge (ret
)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
653 if (dom_info_available_p (CDI_DOMINATORS
))
654 set_immediate_dominator (CDI_DOMINATORS
, ret
, single_pred (ret
));
656 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
658 /* There are two cases:
660 If the immediate dominator of e->dest is not e->src, it
663 If immediate dominator of e->dest is e->src, it may become
664 ret, provided that all other predecessors of e->dest are
665 dominated by e->dest. */
667 if (get_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
))
668 == single_pred (ret
))
671 FOR_EACH_EDGE (f
, ei
, single_succ (ret
)->preds
)
673 if (f
== single_succ_edge (ret
))
676 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
682 set_immediate_dominator (CDI_DOMINATORS
, single_succ (ret
), ret
);
686 if (current_loops
!= NULL
)
688 loop
= find_common_loop (src
->loop_father
, dest
->loop_father
);
689 add_bb_to_loop (ret
, loop
);
691 /* If we split the latch edge of loop adjust the latch block. */
692 if (loop
->latch
== src
693 && loop
->header
== dest
)
700 /* Creates a new basic block just after the basic block AFTER.
701 HEAD and END are the first and the last statement belonging
702 to the block. If both are NULL, an empty block is created. */
705 create_basic_block_1 (void *head
, void *end
, basic_block after
)
709 if (!cfg_hooks
->create_basic_block
)
710 internal_error ("%s does not support create_basic_block", cfg_hooks
->name
);
712 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
714 if (dom_info_available_p (CDI_DOMINATORS
))
715 add_to_dominance_info (CDI_DOMINATORS
, ret
);
716 if (dom_info_available_p (CDI_POST_DOMINATORS
))
717 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
723 create_basic_block (gimple_seq seq
, basic_block after
)
725 return create_basic_block_1 (seq
, NULL
, after
);
729 create_basic_block (rtx head
, rtx end
, basic_block after
)
731 return create_basic_block_1 (head
, end
, after
);
735 /* Creates an empty basic block just after basic block AFTER. */
738 create_empty_bb (basic_block after
)
740 return create_basic_block_1 (NULL
, NULL
, after
);
743 /* Checks whether we may merge blocks BB1 and BB2. */
746 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
750 if (!cfg_hooks
->can_merge_blocks_p
)
751 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks
->name
);
753 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
759 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
761 if (!cfg_hooks
->predict_edge
)
762 internal_error ("%s does not support predict_edge", cfg_hooks
->name
);
764 cfg_hooks
->predict_edge (e
, predictor
, probability
);
768 predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
770 if (!cfg_hooks
->predict_edge
)
771 internal_error ("%s does not support predicted_by_p", cfg_hooks
->name
);
773 return cfg_hooks
->predicted_by_p (bb
, predictor
);
776 /* Merges basic block B into basic block A. */
779 merge_blocks (basic_block a
, basic_block b
)
784 if (!cfg_hooks
->merge_blocks
)
785 internal_error ("%s does not support merge_blocks", cfg_hooks
->name
);
787 cfg_hooks
->merge_blocks (a
, b
);
789 if (current_loops
!= NULL
)
791 /* If the block we merge into is a loop header do nothing unless ... */
792 if (a
->loop_father
->header
== a
)
794 /* ... we merge two loop headers, in which case we kill
796 if (b
->loop_father
->header
== b
)
797 mark_loop_for_removal (b
->loop_father
);
799 /* If we merge a loop header into its predecessor, update the loop
801 else if (b
->loop_father
->header
== b
)
803 remove_bb_from_loops (a
);
804 add_bb_to_loop (a
, b
->loop_father
);
805 a
->loop_father
->header
= a
;
807 /* If we merge a loop latch into its predecessor, update the loop
809 if (b
->loop_father
->latch
810 && b
->loop_father
->latch
== b
)
811 b
->loop_father
->latch
= a
;
812 remove_bb_from_loops (b
);
815 /* Normally there should only be one successor of A and that is B, but
816 partway though the merge of blocks for conditional_execution we'll
817 be merging a TEST block with THEN and ELSE successors. Free the
818 whole lot of them and hope the caller knows what they're doing. */
820 while (EDGE_COUNT (a
->succs
) != 0)
821 remove_edge (EDGE_SUCC (a
, 0));
823 /* Adjust the edges out of B for the new owner. */
824 FOR_EACH_EDGE (e
, ei
, b
->succs
)
827 if (current_loops
!= NULL
)
829 /* If b was a latch, a now is. */
830 if (e
->dest
->loop_father
->latch
== b
)
831 e
->dest
->loop_father
->latch
= a
;
832 rescan_loop_exit (e
, true, false);
836 a
->flags
|= b
->flags
;
838 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
839 b
->preds
= b
->succs
= NULL
;
841 if (dom_info_available_p (CDI_DOMINATORS
))
842 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
844 if (dom_info_available_p (CDI_DOMINATORS
))
845 delete_from_dominance_info (CDI_DOMINATORS
, b
);
846 if (dom_info_available_p (CDI_POST_DOMINATORS
))
847 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
852 /* Split BB into entry part and the rest (the rest is the newly created block).
853 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
854 part. Returns the edge connecting the entry part to the rest. */
857 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
858 void (*new_bb_cbk
) (basic_block
))
862 basic_block dummy
, jump
;
863 struct loop
*loop
, *ploop
, *cloop
;
865 if (!cfg_hooks
->make_forwarder_block
)
866 internal_error ("%s does not support make_forwarder_block",
869 fallthru
= split_block_after_labels (bb
);
870 dummy
= fallthru
->src
;
871 dummy
->count
= profile_count::zero ();
872 dummy
->frequency
= 0;
875 /* Redirect back edges we want to keep. */
876 for (ei
= ei_start (dummy
->preds
); (e
= ei_safe_edge (ei
)); )
880 if (redirect_edge_p (e
))
882 dummy
->frequency
+= EDGE_FREQUENCY (e
);
883 if (dummy
->frequency
> BB_FREQ_MAX
)
884 dummy
->frequency
= BB_FREQ_MAX
;
886 dummy
->count
+= e
->count ();
892 jump
= redirect_edge_and_branch_force (e
, bb
);
895 /* If we redirected the loop latch edge, the JUMP block now acts like
896 the new latch of the loop. */
897 if (current_loops
!= NULL
898 && dummy
->loop_father
!= NULL
899 && dummy
->loop_father
->header
== dummy
900 && dummy
->loop_father
->latch
== e_src
)
901 dummy
->loop_father
->latch
= jump
;
903 if (new_bb_cbk
!= NULL
)
908 if (dom_info_available_p (CDI_DOMINATORS
))
910 vec
<basic_block
> doms_to_fix
;
911 doms_to_fix
.create (2);
912 doms_to_fix
.quick_push (dummy
);
913 doms_to_fix
.quick_push (bb
);
914 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, false);
915 doms_to_fix
.release ();
918 if (current_loops
!= NULL
)
920 /* If we do not split a loop header, then both blocks belong to the
921 same loop. In case we split loop header and do not redirect the
922 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
923 BB becomes the new header. If latch is not recorded for the loop,
924 we leave this updating on the caller (this may only happen during
926 loop
= dummy
->loop_father
;
927 if (loop
->header
== dummy
928 && loop
->latch
!= NULL
929 && find_edge (loop
->latch
, dummy
) == NULL
)
931 remove_bb_from_loops (dummy
);
935 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
937 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
939 add_bb_to_loop (dummy
, cloop
);
942 /* In case we split loop latch, update it. */
943 for (ploop
= loop
; ploop
; ploop
= loop_outer (ploop
))
944 if (ploop
->latch
== dummy
)
948 cfg_hooks
->make_forwarder_block (fallthru
);
953 /* Try to make the edge fallthru. */
956 tidy_fallthru_edge (edge e
)
958 if (cfg_hooks
->tidy_fallthru_edge
)
959 cfg_hooks
->tidy_fallthru_edge (e
);
962 /* Fix up edges that now fall through, or rather should now fall through
963 but previously required a jump around now deleted blocks. Simplify
964 the search by only examining blocks numerically adjacent, since this
965 is how they were created.
967 ??? This routine is currently RTL specific. */
970 tidy_fallthru_edges (void)
974 if (!cfg_hooks
->tidy_fallthru_edge
)
977 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
980 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
,
981 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
, next_bb
)
987 /* We care about simple conditional or unconditional jumps with
990 If we had a conditional branch to the next instruction when
991 CFG was built, then there will only be one out edge for the
992 block which ended with the conditional branch (since we do
993 not create duplicate edges).
995 Furthermore, the edge will be marked as a fallthru because we
996 merge the flags for the duplicate edges. So we do not want to
997 check that the edge is not a FALLTHRU edge. */
999 if (single_succ_p (b
))
1001 s
= single_succ_edge (b
);
1002 if (! (s
->flags
& EDGE_COMPLEX
)
1004 && !(JUMP_P (BB_END (b
)) && CROSSING_JUMP_P (BB_END (b
))))
1005 tidy_fallthru_edge (s
);
1010 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1011 (and possibly create new basic block) to make edge non-fallthru.
1012 Return newly created BB or NULL if none. */
1015 force_nonfallthru (edge e
)
1017 basic_block ret
, src
= e
->src
;
1019 if (!cfg_hooks
->force_nonfallthru
)
1020 internal_error ("%s does not support force_nonfallthru",
1023 ret
= cfg_hooks
->force_nonfallthru (e
);
1026 if (dom_info_available_p (CDI_DOMINATORS
))
1027 set_immediate_dominator (CDI_DOMINATORS
, ret
, src
);
1029 if (current_loops
!= NULL
)
1031 basic_block pred
= single_pred (ret
);
1032 basic_block succ
= single_succ (ret
);
1034 = find_common_loop (pred
->loop_father
, succ
->loop_father
);
1035 rescan_loop_exit (e
, false, true);
1036 add_bb_to_loop (ret
, loop
);
1038 /* If we split the latch edge of loop adjust the latch block. */
1039 if (loop
->latch
== pred
1040 && loop
->header
== succ
)
1048 /* Returns true if we can duplicate basic block BB. */
1051 can_duplicate_block_p (const_basic_block bb
)
1053 if (!cfg_hooks
->can_duplicate_block_p
)
1054 internal_error ("%s does not support can_duplicate_block_p",
1057 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1060 return cfg_hooks
->can_duplicate_block_p (bb
);
1063 /* Duplicates basic block BB and redirects edge E to it. Returns the
1064 new basic block. The new basic block is placed after the basic block
1068 duplicate_block (basic_block bb
, edge e
, basic_block after
)
1072 profile_count new_count
= e
? e
->count (): profile_count::uninitialized ();
1075 if (!cfg_hooks
->duplicate_block
)
1076 internal_error ("%s does not support duplicate_block",
1079 if (bb
->count
< new_count
)
1080 new_count
= bb
->count
;
1082 gcc_checking_assert (can_duplicate_block_p (bb
));
1084 new_bb
= cfg_hooks
->duplicate_block (bb
);
1086 move_block_after (new_bb
, after
);
1088 new_bb
->flags
= (bb
->flags
& ~BB_DUPLICATED
);
1089 FOR_EACH_EDGE (s
, ei
, bb
->succs
)
1091 /* Since we are creating edges from a new block to successors
1092 of another block (which therefore are known to be disjoint), there
1093 is no need to actually check for duplicated edges. */
1094 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
1095 n
->probability
= s
->probability
;
1101 new_bb
->count
= new_count
;
1102 bb
->count
-= new_count
;
1104 new_bb
->frequency
= EDGE_FREQUENCY (e
);
1105 bb
->frequency
-= EDGE_FREQUENCY (e
);
1107 redirect_edge_and_branch_force (e
, new_bb
);
1109 if (bb
->frequency
< 0)
1114 new_bb
->count
= bb
->count
;
1115 new_bb
->frequency
= bb
->frequency
;
1118 set_bb_original (new_bb
, bb
);
1119 set_bb_copy (bb
, new_bb
);
1121 /* Add the new block to the copy of the loop of BB, or directly to the loop
1122 of BB if the loop is not being copied. */
1123 if (current_loops
!= NULL
)
1125 struct loop
*cloop
= bb
->loop_father
;
1126 struct loop
*copy
= get_loop_copy (cloop
);
1127 /* If we copied the loop header block but not the loop
1128 we have created a loop with multiple entries. Ditch the loop,
1129 add the new block to the outer loop and arrange for a fixup. */
1131 && cloop
->header
== bb
)
1133 add_bb_to_loop (new_bb
, loop_outer (cloop
));
1134 mark_loop_for_removal (cloop
);
1138 add_bb_to_loop (new_bb
, copy
? copy
: cloop
);
1139 /* If we copied the loop latch block but not the loop, adjust
1142 && cloop
->latch
== bb
)
1144 cloop
->latch
= NULL
;
1145 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
1153 /* Return 1 if BB ends with a call, possibly followed by some
1154 instructions that must stay with the call, 0 otherwise. */
1157 block_ends_with_call_p (basic_block bb
)
1159 if (!cfg_hooks
->block_ends_with_call_p
)
1160 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
1162 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
1165 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1168 block_ends_with_condjump_p (const_basic_block bb
)
1170 if (!cfg_hooks
->block_ends_with_condjump_p
)
1171 internal_error ("%s does not support block_ends_with_condjump_p",
1174 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
1177 /* Add fake edges to the function exit for any non constant and non noreturn
1178 calls, volatile inline assembly in the bitmap of blocks specified by
1179 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1182 The goal is to expose cases in which entering a basic block does not imply
1183 that all subsequent instructions must be executed. */
1186 flow_call_edges_add (sbitmap blocks
)
1188 if (!cfg_hooks
->flow_call_edges_add
)
1189 internal_error ("%s does not support flow_call_edges_add",
1192 return (cfg_hooks
->flow_call_edges_add
) (blocks
);
1195 /* This function is called immediately after edge E is added to the
1196 edge vector E->dest->preds. */
1199 execute_on_growing_pred (edge e
)
1201 if (! (e
->dest
->flags
& BB_DUPLICATED
)
1202 && cfg_hooks
->execute_on_growing_pred
)
1203 cfg_hooks
->execute_on_growing_pred (e
);
1206 /* This function is called immediately before edge E is removed from
1207 the edge vector E->dest->preds. */
1210 execute_on_shrinking_pred (edge e
)
1212 if (! (e
->dest
->flags
& BB_DUPLICATED
)
1213 && cfg_hooks
->execute_on_shrinking_pred
)
1214 cfg_hooks
->execute_on_shrinking_pred (e
);
1217 /* This is used inside loop versioning when we want to insert
1218 stmts/insns on the edges, which have a different behavior
1219 in tree's and in RTL, so we made a CFG hook. */
1221 lv_flush_pending_stmts (edge e
)
1223 if (cfg_hooks
->flush_pending_stmts
)
1224 cfg_hooks
->flush_pending_stmts (e
);
1227 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1228 a new version of the loop basic-blocks, the parameters here are
1229 exactly the same as in duplicate_loop_to_header_edge or
1230 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1231 additional work to maintain ssa information that's why there is
1232 a need to call the tree_duplicate_loop_to_header_edge rather
1233 than duplicate_loop_to_header_edge when we are in tree mode. */
1235 cfg_hook_duplicate_loop_to_header_edge (struct loop
*loop
, edge e
,
1237 sbitmap wont_exit
, edge orig
,
1238 vec
<edge
> *to_remove
,
1241 gcc_assert (cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge
);
1242 return cfg_hooks
->cfg_hook_duplicate_loop_to_header_edge (loop
, e
,
1248 /* Conditional jumps are represented differently in trees and RTL,
1249 this hook takes a basic block that is known to have a cond jump
1250 at its end and extracts the taken and not taken edges out of it
1251 and store it in E1 and E2 respectively. */
1253 extract_cond_bb_edges (basic_block b
, edge
*e1
, edge
*e2
)
1255 gcc_assert (cfg_hooks
->extract_cond_bb_edges
);
1256 cfg_hooks
->extract_cond_bb_edges (b
, e1
, e2
);
1259 /* Responsible for updating the ssa info (PHI nodes) on the
1260 new condition basic block that guards the versioned loop. */
1262 lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
1263 basic_block new_block
, edge e
)
1265 if (cfg_hooks
->lv_adjust_loop_header_phi
)
1266 cfg_hooks
->lv_adjust_loop_header_phi (first
, second
, new_block
, e
);
1269 /* Conditions in trees and RTL are different so we need
1270 a different handling when we add the condition to the
1273 lv_add_condition_to_bb (basic_block first
, basic_block second
,
1274 basic_block new_block
, void *cond
)
1276 gcc_assert (cfg_hooks
->lv_add_condition_to_bb
);
1277 cfg_hooks
->lv_add_condition_to_bb (first
, second
, new_block
, cond
);
1280 /* Checks whether all N blocks in BBS array can be copied. */
1282 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1288 for (i
= 0; i
< n
; i
++)
1289 bbs
[i
]->flags
|= BB_DUPLICATED
;
1291 for (i
= 0; i
< n
; i
++)
1293 /* In case we should redirect abnormal edge during duplication, fail. */
1295 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1296 if ((e
->flags
& EDGE_ABNORMAL
)
1297 && (e
->dest
->flags
& BB_DUPLICATED
))
1303 if (!can_duplicate_block_p (bbs
[i
]))
1311 for (i
= 0; i
< n
; i
++)
1312 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1317 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1318 are placed into array NEW_BBS in the same order. Edges from basic blocks
1319 in BBS are also duplicated and copies of those that lead into BBS are
1320 redirected to appropriate newly created block. The function assigns bbs
1321 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1322 loop, so this must be set up correctly in advance)
1324 If UPDATE_DOMINANCE is true then this function updates dominators locally
1325 (LOOPS structure that contains the information about dominators is passed
1326 to enable this), otherwise it does not update the dominator information
1327 and it assumed that the caller will do this, perhaps by destroying and
1328 recreating it instead of trying to do an incremental update like this
1329 function does when update_dominance is true.
1331 BASE is the superloop to that basic block belongs; if its header or latch
1332 is copied, we do not set the new blocks as header or latch.
1334 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1335 also in the same order.
1337 Newly created basic blocks are put after the basic block AFTER in the
1338 instruction stream, and the order of the blocks in BBS array is preserved. */
1341 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1342 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1343 struct loop
*base
, basic_block after
, bool update_dominance
)
1346 basic_block bb
, new_bb
, dom_bb
;
1349 /* Mark the blocks to be copied. This is used by edge creation hooks
1350 to decide whether to reallocate PHI nodes capacity to avoid reallocating
1351 PHIs in the set of source BBs. */
1352 for (i
= 0; i
< n
; i
++)
1353 bbs
[i
]->flags
|= BB_DUPLICATED
;
1355 /* Duplicate bbs, update dominators, assign bbs to loops. */
1356 for (i
= 0; i
< n
; i
++)
1360 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1362 if (bb
->loop_father
)
1364 /* Possibly set loop header. */
1365 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1366 new_bb
->loop_father
->header
= new_bb
;
1368 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1369 new_bb
->loop_father
->latch
= new_bb
;
1373 /* Set dominators. */
1374 if (update_dominance
)
1376 for (i
= 0; i
< n
; i
++)
1379 new_bb
= new_bbs
[i
];
1381 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1382 if (dom_bb
->flags
& BB_DUPLICATED
)
1384 dom_bb
= get_bb_copy (dom_bb
);
1385 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1390 /* Redirect edges. */
1391 for (j
= 0; j
< num_edges
; j
++)
1392 new_edges
[j
] = NULL
;
1393 for (i
= 0; i
< n
; i
++)
1396 new_bb
= new_bbs
[i
];
1399 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1401 for (j
= 0; j
< num_edges
; j
++)
1402 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1405 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1407 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1411 /* Clear information about duplicates. */
1412 for (i
= 0; i
< n
; i
++)
1413 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1416 /* Return true if BB contains only labels or non-executable
1419 empty_block_p (basic_block bb
)
1421 gcc_assert (cfg_hooks
->empty_block_p
);
1422 return cfg_hooks
->empty_block_p (bb
);
1425 /* Split a basic block if it ends with a conditional branch and if
1426 the other part of the block is not empty. */
1428 split_block_before_cond_jump (basic_block bb
)
1430 gcc_assert (cfg_hooks
->split_block_before_cond_jump
);
1431 return cfg_hooks
->split_block_before_cond_jump (bb
);
1434 /* Work-horse for passes.c:check_profile_consistency.
1435 Do book-keeping of the CFG for the profile consistency checker.
1436 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
1437 then do post-pass accounting. Store the counting in RECORD. */
1440 account_profile_record (struct profile_record
*record
, int after_pass
)
1446 FOR_ALL_BB_FN (bb
, cfun
)
1448 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1449 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1451 profile_probability sum
= profile_probability::never ();
1452 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1453 sum
+= e
->probability
;
1454 if (EDGE_COUNT (bb
->succs
)
1455 && sum
.differs_from_p (profile_probability::always ()))
1456 record
->num_mismatched_freq_out
[after_pass
]++;
1457 profile_count lsum
= profile_count::zero ();
1458 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1459 lsum
+= e
->count ();
1460 if (EDGE_COUNT (bb
->succs
) && (lsum
.differs_from_p (bb
->count
)))
1461 record
->num_mismatched_count_out
[after_pass
]++;
1463 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1464 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
1467 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1468 sum
+= EDGE_FREQUENCY (e
);
1469 if (abs (sum
- bb
->frequency
) > 100
1470 || (MAX (sum
, bb
->frequency
) > 10
1471 && abs ((sum
- bb
->frequency
) * 100 / (MAX (sum
, bb
->frequency
) + 1)) > 10))
1472 record
->num_mismatched_freq_in
[after_pass
]++;
1473 profile_count lsum
= profile_count::zero ();
1474 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1475 lsum
+= e
->count ();
1476 if (lsum
.differs_from_p (bb
->count
))
1477 record
->num_mismatched_count_in
[after_pass
]++;
1479 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1480 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1482 gcc_assert (cfg_hooks
->account_profile_record
);
1483 cfg_hooks
->account_profile_record (bb
, after_pass
, record
);