Daily bump.
[official-gcc.git] / gcc / cfghooks.c
blobbc1634aac879abba8130dd2e0febe7efc9f07c1d
1 /* Hooks for cfg representation specific functions.
2 Copyright (C) 2003-2014 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)
10 any later version.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "dumpfile.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "rtl.h"
28 #include "basic-block.h"
29 #include "tree-ssa.h"
30 #include "timevar.h"
31 #include "diagnostic-core.h"
32 #include "cfgloop.h"
33 #include "pretty-print.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. */
39 void
40 rtl_register_cfg_hooks (void)
42 cfg_hooks = &rtl_cfg_hooks;
45 /* Initialization of functions specific to the rtl IR. */
46 void
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. */
54 void
55 gimple_register_cfg_hooks (void)
57 cfg_hooks = &gimple_cfg_hooks;
60 struct cfg_hooks
61 get_cfg_hooks (void)
63 return *cfg_hooks;
66 void
67 set_cfg_hooks (struct cfg_hooks new_cfg_hooks)
69 *cfg_hooks = new_cfg_hooks;
72 /* Returns current ir type. */
74 enum ir_type
75 current_ir_type (void)
77 if (cfg_hooks == &gimple_cfg_hooks)
78 return IR_GIMPLE;
79 else if (cfg_hooks == &rtl_cfg_hooks)
80 return IR_RTL_CFGRTL;
81 else if (cfg_hooks == &cfg_layout_rtl_cfg_hooks)
82 return IR_RTL_CFGLAYOUT;
83 else
84 gcc_unreachable ();
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. */
92 DEBUG_FUNCTION void
93 verify_flow_info (void)
95 size_t *edge_checksum;
96 int err = 0;
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);
112 err = 1;
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);
119 err = 1;
122 last_bb_seen = bb;
125 /* Now check the basic blocks (boundaries etc.) */
126 FOR_EACH_BB_REVERSE_FN (bb, cfun)
128 int n_fallthru = 0;
129 edge e;
130 edge_iterator ei;
132 if (bb->loop_father != NULL && current_loops == NULL)
134 error ("verify_flow_info: Block %i has loop_father, but there are no loops",
135 bb->index);
136 err = 1;
138 if (bb->loop_father == NULL && current_loops != NULL)
140 error ("verify_flow_info: Block %i lacks loop_father", bb->index);
141 err = 1;
144 if (bb->count < 0)
146 error ("verify_flow_info: Wrong count of block %i %i",
147 bb->index, (int)bb->count);
148 err = 1;
150 if (bb->frequency < 0)
152 error ("verify_flow_info: Wrong frequency of block %i %i",
153 bb->index, bb->frequency);
154 err = 1;
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);
162 err = 1;
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);
168 err = 1;
170 if (e->count < 0)
172 error ("verify_flow_info: Wrong count of edge %i->%i %i",
173 e->src->index, e->dest->index, (int)e->count);
174 err = 1;
177 last_visited [e->dest->index] = bb;
179 if (e->flags & EDGE_FALLTHRU)
180 n_fallthru++;
182 if (e->src != bb)
184 error ("verify_flow_info: Basic block %d succ edge is corrupted",
185 bb->index);
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");
191 err = 1;
194 edge_checksum[e->dest->index] += (size_t) e;
196 if (n_fallthru > 1)
198 error ("wrong amount of branch edges after unconditional jump %i", bb->index);
199 err = 1;
202 FOR_EACH_EDGE (e, ei, bb->preds)
204 if (e->dest != bb)
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);
212 err = 1;
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);
225 err = 1;
228 edge_checksum[e->dest->index] -= (size_t) e;
232 /* Complete edge checksumming for ENTRY and EXIT. */
234 edge e;
235 edge_iterator ei;
237 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
238 edge_checksum[e->dest->index] += (size_t) e;
240 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
241 edge_checksum[e->dest->index] -= (size_t) e;
244 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
245 if (edge_checksum[bb->index])
247 error ("basic block %i edge lists are corrupted", bb->index);
248 err = 1;
251 last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
253 /* Clean up. */
254 free (last_visited);
255 free (edge_checksum);
257 if (cfg_hooks->verify_flow_info)
258 err |= cfg_hooks->verify_flow_info ();
259 if (err)
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. */
271 void
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);
280 fputc ('\n', outf);
283 DEBUG_FUNCTION void
284 debug (basic_block_def &ref)
286 dump_bb (stderr, &ref, 0, 0);
289 DEBUG_FUNCTION void
290 debug (basic_block_def *ptr)
292 if (ptr)
293 debug (*ptr);
294 else
295 fprintf (stderr, "<nil>\n");
299 /* Dumps basic block BB to pretty-printer PP, for use as a label of
300 a DOT graph record-node. The implementation of this hook is
301 expected to write the label to the stream that is attached to PP.
302 Field separators between instructions are pipe characters printed
303 verbatim. Instructions should be written with some characters
304 escaped, using pp_write_text_as_dot_label_to_stream(). */
306 void
307 dump_bb_for_graph (pretty_printer *pp, basic_block bb)
309 if (!cfg_hooks->dump_bb_for_graph)
310 internal_error ("%s does not support dump_bb_for_graph",
311 cfg_hooks->name);
312 if (bb->count)
313 pp_printf (pp, "COUNT:" HOST_WIDEST_INT_PRINT_DEC, bb->count);
314 pp_printf (pp, " FREQ:%i |", bb->frequency);
315 pp_write_text_to_stream (pp);
316 if (!(dump_flags & TDF_SLIM))
317 cfg_hooks->dump_bb_for_graph (pp, bb);
320 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
321 void
322 dump_flow_info (FILE *file, int flags)
324 basic_block bb;
326 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun),
327 n_edges_for_fn (cfun));
328 FOR_ALL_BB_FN (bb, cfun)
329 dump_bb (file, bb, 0, flags);
331 putc ('\n', file);
334 /* Like above, but dump to stderr. To be called from debuggers. */
335 void debug_flow_info (void);
336 DEBUG_FUNCTION void
337 debug_flow_info (void)
339 dump_flow_info (stderr, TDF_DETAILS);
342 /* Redirect edge E to the given basic block DEST and update underlying program
343 representation. Returns edge representing redirected branch (that may not
344 be equivalent to E in the case of duplicate edges being removed) or NULL
345 if edge is not easily redirectable for whatever reason. */
347 edge
348 redirect_edge_and_branch (edge e, basic_block dest)
350 edge ret;
352 if (!cfg_hooks->redirect_edge_and_branch)
353 internal_error ("%s does not support redirect_edge_and_branch",
354 cfg_hooks->name);
356 ret = cfg_hooks->redirect_edge_and_branch (e, dest);
358 /* If RET != E, then either the redirection failed, or the edge E
359 was removed since RET already lead to the same destination. */
360 if (current_loops != NULL && ret == e)
361 rescan_loop_exit (e, false, false);
363 return ret;
366 /* Returns true if it is possible to remove the edge E by redirecting it
367 to the destination of the other edge going from its source. */
369 bool
370 can_remove_branch_p (const_edge e)
372 if (!cfg_hooks->can_remove_branch_p)
373 internal_error ("%s does not support can_remove_branch_p",
374 cfg_hooks->name);
376 if (EDGE_COUNT (e->src->succs) != 2)
377 return false;
379 return cfg_hooks->can_remove_branch_p (e);
382 /* Removes E, by redirecting it to the destination of the other edge going
383 from its source. Can_remove_branch_p must be true for E, hence this
384 operation cannot fail. */
386 void
387 remove_branch (edge e)
389 edge other;
390 basic_block src = e->src;
391 int irr;
393 gcc_assert (EDGE_COUNT (e->src->succs) == 2);
395 other = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
396 irr = other->flags & EDGE_IRREDUCIBLE_LOOP;
398 e = redirect_edge_and_branch (e, other->dest);
399 gcc_assert (e != NULL);
401 e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
402 e->flags |= irr;
405 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
407 void
408 remove_edge (edge e)
410 if (current_loops != NULL)
411 rescan_loop_exit (e, false, true);
413 /* This is probably not needed, but it doesn't hurt. */
414 /* FIXME: This should be called via a remove_edge hook. */
415 if (current_ir_type () == IR_GIMPLE)
416 redirect_edge_var_map_clear (e);
418 remove_edge_raw (e);
421 /* Like redirect_edge_succ but avoid possible duplicate edge. */
423 edge
424 redirect_edge_succ_nodup (edge e, basic_block new_succ)
426 edge s;
428 s = find_edge (e->src, new_succ);
429 if (s && s != e)
431 s->flags |= e->flags;
432 s->probability += e->probability;
433 if (s->probability > REG_BR_PROB_BASE)
434 s->probability = REG_BR_PROB_BASE;
435 s->count += e->count;
436 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
437 redirect_edge_var_map_dup (s, e);
438 remove_edge (e);
439 e = s;
441 else
442 redirect_edge_succ (e, new_succ);
444 return e;
447 /* Redirect the edge E to basic block DEST even if it requires creating
448 of a new basic block; then it returns the newly created basic block.
449 Aborts when redirection is impossible. */
451 basic_block
452 redirect_edge_and_branch_force (edge e, basic_block dest)
454 basic_block ret, src = e->src;
456 if (!cfg_hooks->redirect_edge_and_branch_force)
457 internal_error ("%s does not support redirect_edge_and_branch_force",
458 cfg_hooks->name);
460 if (current_loops != NULL)
461 rescan_loop_exit (e, false, true);
463 ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
465 if (ret != NULL && dom_info_available_p (CDI_DOMINATORS))
466 set_immediate_dominator (CDI_DOMINATORS, ret, src);
468 if (current_loops != NULL)
470 if (ret != NULL)
472 struct loop *loop
473 = find_common_loop (single_pred (ret)->loop_father,
474 single_succ (ret)->loop_father);
475 add_bb_to_loop (ret, loop);
477 else if (find_edge (src, dest) == e)
478 rescan_loop_exit (e, true, false);
481 return ret;
484 /* Splits basic block BB after the specified instruction I (but at least after
485 the labels). If I is NULL, splits just after labels. The newly created edge
486 is returned. The new basic block is created just after the old one. */
488 edge
489 split_block (basic_block bb, void *i)
491 basic_block new_bb;
492 edge res;
494 if (!cfg_hooks->split_block)
495 internal_error ("%s does not support split_block", cfg_hooks->name);
497 new_bb = cfg_hooks->split_block (bb, i);
498 if (!new_bb)
499 return NULL;
501 new_bb->count = bb->count;
502 new_bb->frequency = bb->frequency;
503 new_bb->discriminator = bb->discriminator;
505 if (dom_info_available_p (CDI_DOMINATORS))
507 redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
508 set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
511 if (current_loops != NULL)
513 edge_iterator ei;
514 edge e;
515 add_bb_to_loop (new_bb, bb->loop_father);
516 /* Identify all loops bb may have been the latch of and adjust them. */
517 FOR_EACH_EDGE (e, ei, new_bb->succs)
518 if (e->dest->loop_father->latch == bb)
519 e->dest->loop_father->latch = new_bb;
522 res = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
524 if (bb->flags & BB_IRREDUCIBLE_LOOP)
526 new_bb->flags |= BB_IRREDUCIBLE_LOOP;
527 res->flags |= EDGE_IRREDUCIBLE_LOOP;
530 return res;
533 /* Splits block BB just after labels. The newly created edge is returned. */
535 edge
536 split_block_after_labels (basic_block bb)
538 return split_block (bb, NULL);
541 /* Moves block BB immediately after block AFTER. Returns false if the
542 movement was impossible. */
544 bool
545 move_block_after (basic_block bb, basic_block after)
547 bool ret;
549 if (!cfg_hooks->move_block_after)
550 internal_error ("%s does not support move_block_after", cfg_hooks->name);
552 ret = cfg_hooks->move_block_after (bb, after);
554 return ret;
557 /* Deletes the basic block BB. */
559 void
560 delete_basic_block (basic_block bb)
562 if (!cfg_hooks->delete_basic_block)
563 internal_error ("%s does not support delete_basic_block", cfg_hooks->name);
565 cfg_hooks->delete_basic_block (bb);
567 if (current_loops != NULL)
569 struct loop *loop = bb->loop_father;
571 /* If we remove the header or the latch of a loop, mark the loop for
572 removal by setting its header and latch to NULL. */
573 if (loop->latch == bb
574 || loop->header == bb)
576 loop->header = NULL;
577 loop->latch = NULL;
578 loops_state_set (LOOPS_NEED_FIXUP);
581 remove_bb_from_loops (bb);
584 /* Remove the edges into and out of this block. Note that there may
585 indeed be edges in, if we are removing an unreachable loop. */
586 while (EDGE_COUNT (bb->preds) != 0)
587 remove_edge (EDGE_PRED (bb, 0));
588 while (EDGE_COUNT (bb->succs) != 0)
589 remove_edge (EDGE_SUCC (bb, 0));
591 if (dom_info_available_p (CDI_DOMINATORS))
592 delete_from_dominance_info (CDI_DOMINATORS, bb);
593 if (dom_info_available_p (CDI_POST_DOMINATORS))
594 delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
596 /* Remove the basic block from the array. */
597 expunge_block (bb);
600 /* Splits edge E and returns the newly created basic block. */
602 basic_block
603 split_edge (edge e)
605 basic_block ret;
606 gcov_type count = e->count;
607 int freq = EDGE_FREQUENCY (e);
608 edge f;
609 bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
610 struct loop *loop;
611 basic_block src = e->src, dest = e->dest;
613 if (!cfg_hooks->split_edge)
614 internal_error ("%s does not support split_edge", cfg_hooks->name);
616 if (current_loops != NULL)
617 rescan_loop_exit (e, false, true);
619 ret = cfg_hooks->split_edge (e);
620 ret->count = count;
621 ret->frequency = freq;
622 single_succ_edge (ret)->probability = REG_BR_PROB_BASE;
623 single_succ_edge (ret)->count = count;
625 if (irr)
627 ret->flags |= BB_IRREDUCIBLE_LOOP;
628 single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
629 single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
632 if (dom_info_available_p (CDI_DOMINATORS))
633 set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
635 if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
637 /* There are two cases:
639 If the immediate dominator of e->dest is not e->src, it
640 remains unchanged.
642 If immediate dominator of e->dest is e->src, it may become
643 ret, provided that all other predecessors of e->dest are
644 dominated by e->dest. */
646 if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
647 == single_pred (ret))
649 edge_iterator ei;
650 FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
652 if (f == single_succ_edge (ret))
653 continue;
655 if (!dominated_by_p (CDI_DOMINATORS, f->src,
656 single_succ (ret)))
657 break;
660 if (!f)
661 set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
665 if (current_loops != NULL)
667 loop = find_common_loop (src->loop_father, dest->loop_father);
668 add_bb_to_loop (ret, loop);
670 /* If we split the latch edge of loop adjust the latch block. */
671 if (loop->latch == src
672 && loop->header == dest)
673 loop->latch = ret;
676 return ret;
679 /* Creates a new basic block just after the basic block AFTER.
680 HEAD and END are the first and the last statement belonging
681 to the block. If both are NULL, an empty block is created. */
683 basic_block
684 create_basic_block (void *head, void *end, basic_block after)
686 basic_block ret;
688 if (!cfg_hooks->create_basic_block)
689 internal_error ("%s does not support create_basic_block", cfg_hooks->name);
691 ret = cfg_hooks->create_basic_block (head, end, after);
693 if (dom_info_available_p (CDI_DOMINATORS))
694 add_to_dominance_info (CDI_DOMINATORS, ret);
695 if (dom_info_available_p (CDI_POST_DOMINATORS))
696 add_to_dominance_info (CDI_POST_DOMINATORS, ret);
698 return ret;
701 /* Creates an empty basic block just after basic block AFTER. */
703 basic_block
704 create_empty_bb (basic_block after)
706 return create_basic_block (NULL, NULL, after);
709 /* Checks whether we may merge blocks BB1 and BB2. */
711 bool
712 can_merge_blocks_p (basic_block bb1, basic_block bb2)
714 bool ret;
716 if (!cfg_hooks->can_merge_blocks_p)
717 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name);
719 ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
721 return ret;
724 void
725 predict_edge (edge e, enum br_predictor predictor, int probability)
727 if (!cfg_hooks->predict_edge)
728 internal_error ("%s does not support predict_edge", cfg_hooks->name);
730 cfg_hooks->predict_edge (e, predictor, probability);
733 bool
734 predicted_by_p (const_basic_block bb, enum br_predictor predictor)
736 if (!cfg_hooks->predict_edge)
737 internal_error ("%s does not support predicted_by_p", cfg_hooks->name);
739 return cfg_hooks->predicted_by_p (bb, predictor);
742 /* Merges basic block B into basic block A. */
744 void
745 merge_blocks (basic_block a, basic_block b)
747 edge e;
748 edge_iterator ei;
750 if (!cfg_hooks->merge_blocks)
751 internal_error ("%s does not support merge_blocks", cfg_hooks->name);
753 cfg_hooks->merge_blocks (a, b);
755 if (current_loops != NULL)
757 /* If the block we merge into is a loop header do nothing unless ... */
758 if (a->loop_father->header == a)
760 /* ... we merge two loop headers, in which case we kill
761 the inner loop. */
762 if (b->loop_father->header == b)
764 b->loop_father->header = NULL;
765 b->loop_father->latch = NULL;
766 loops_state_set (LOOPS_NEED_FIXUP);
769 /* If we merge a loop header into its predecessor, update the loop
770 structure. */
771 else if (b->loop_father->header == b)
773 remove_bb_from_loops (a);
774 add_bb_to_loop (a, b->loop_father);
775 a->loop_father->header = a;
777 remove_bb_from_loops (b);
780 /* Normally there should only be one successor of A and that is B, but
781 partway though the merge of blocks for conditional_execution we'll
782 be merging a TEST block with THEN and ELSE successors. Free the
783 whole lot of them and hope the caller knows what they're doing. */
785 while (EDGE_COUNT (a->succs) != 0)
786 remove_edge (EDGE_SUCC (a, 0));
788 /* Adjust the edges out of B for the new owner. */
789 FOR_EACH_EDGE (e, ei, b->succs)
791 e->src = a;
792 if (current_loops != NULL)
794 /* If b was a latch, a now is. */
795 if (e->dest->loop_father->latch == b)
796 e->dest->loop_father->latch = a;
797 rescan_loop_exit (e, true, false);
800 a->succs = b->succs;
801 a->flags |= b->flags;
803 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
804 b->preds = b->succs = NULL;
806 if (dom_info_available_p (CDI_DOMINATORS))
807 redirect_immediate_dominators (CDI_DOMINATORS, b, a);
809 if (dom_info_available_p (CDI_DOMINATORS))
810 delete_from_dominance_info (CDI_DOMINATORS, b);
811 if (dom_info_available_p (CDI_POST_DOMINATORS))
812 delete_from_dominance_info (CDI_POST_DOMINATORS, b);
814 expunge_block (b);
817 /* Split BB into entry part and the rest (the rest is the newly created block).
818 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
819 part. Returns the edge connecting the entry part to the rest. */
821 edge
822 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
823 void (*new_bb_cbk) (basic_block))
825 edge e, fallthru;
826 edge_iterator ei;
827 basic_block dummy, jump;
828 struct loop *loop, *ploop, *cloop;
830 if (!cfg_hooks->make_forwarder_block)
831 internal_error ("%s does not support make_forwarder_block",
832 cfg_hooks->name);
834 fallthru = split_block_after_labels (bb);
835 dummy = fallthru->src;
836 bb = fallthru->dest;
838 /* Redirect back edges we want to keep. */
839 for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
841 basic_block e_src;
843 if (redirect_edge_p (e))
845 ei_next (&ei);
846 continue;
849 dummy->frequency -= EDGE_FREQUENCY (e);
850 dummy->count -= e->count;
851 if (dummy->frequency < 0)
852 dummy->frequency = 0;
853 if (dummy->count < 0)
854 dummy->count = 0;
855 fallthru->count -= e->count;
856 if (fallthru->count < 0)
857 fallthru->count = 0;
859 e_src = e->src;
860 jump = redirect_edge_and_branch_force (e, bb);
861 if (jump != NULL)
863 /* If we redirected the loop latch edge, the JUMP block now acts like
864 the new latch of the loop. */
865 if (current_loops != NULL
866 && dummy->loop_father != NULL
867 && dummy->loop_father->header == dummy
868 && dummy->loop_father->latch == e_src)
869 dummy->loop_father->latch = jump;
871 if (new_bb_cbk != NULL)
872 new_bb_cbk (jump);
876 if (dom_info_available_p (CDI_DOMINATORS))
878 vec<basic_block> doms_to_fix;
879 doms_to_fix.create (2);
880 doms_to_fix.quick_push (dummy);
881 doms_to_fix.quick_push (bb);
882 iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
883 doms_to_fix.release ();
886 if (current_loops != NULL)
888 /* If we do not split a loop header, then both blocks belong to the
889 same loop. In case we split loop header and do not redirect the
890 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
891 BB becomes the new header. If latch is not recorded for the loop,
892 we leave this updating on the caller (this may only happen during
893 loop analysis). */
894 loop = dummy->loop_father;
895 if (loop->header == dummy
896 && loop->latch != NULL
897 && find_edge (loop->latch, dummy) == NULL)
899 remove_bb_from_loops (dummy);
900 loop->header = bb;
902 cloop = loop;
903 FOR_EACH_EDGE (e, ei, dummy->preds)
905 cloop = find_common_loop (cloop, e->src->loop_father);
907 add_bb_to_loop (dummy, cloop);
910 /* In case we split loop latch, update it. */
911 for (ploop = loop; ploop; ploop = loop_outer (ploop))
912 if (ploop->latch == dummy)
913 ploop->latch = bb;
916 cfg_hooks->make_forwarder_block (fallthru);
918 return fallthru;
921 /* Try to make the edge fallthru. */
923 void
924 tidy_fallthru_edge (edge e)
926 if (cfg_hooks->tidy_fallthru_edge)
927 cfg_hooks->tidy_fallthru_edge (e);
930 /* Fix up edges that now fall through, or rather should now fall through
931 but previously required a jump around now deleted blocks. Simplify
932 the search by only examining blocks numerically adjacent, since this
933 is how they were created.
935 ??? This routine is currently RTL specific. */
937 void
938 tidy_fallthru_edges (void)
940 basic_block b, c;
942 if (!cfg_hooks->tidy_fallthru_edge)
943 return;
945 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
946 return;
948 FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb,
949 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb, next_bb)
951 edge s;
953 c = b->next_bb;
955 /* We care about simple conditional or unconditional jumps with
956 a single successor.
958 If we had a conditional branch to the next instruction when
959 CFG was built, then there will only be one out edge for the
960 block which ended with the conditional branch (since we do
961 not create duplicate edges).
963 Furthermore, the edge will be marked as a fallthru because we
964 merge the flags for the duplicate edges. So we do not want to
965 check that the edge is not a FALLTHRU edge. */
967 if (single_succ_p (b))
969 s = single_succ_edge (b);
970 if (! (s->flags & EDGE_COMPLEX)
971 && s->dest == c
972 && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
973 tidy_fallthru_edge (s);
978 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
979 (and possibly create new basic block) to make edge non-fallthru.
980 Return newly created BB or NULL if none. */
982 basic_block
983 force_nonfallthru (edge e)
985 basic_block ret, src = e->src;
987 if (!cfg_hooks->force_nonfallthru)
988 internal_error ("%s does not support force_nonfallthru",
989 cfg_hooks->name);
991 ret = cfg_hooks->force_nonfallthru (e);
992 if (ret != NULL)
994 if (dom_info_available_p (CDI_DOMINATORS))
995 set_immediate_dominator (CDI_DOMINATORS, ret, src);
997 if (current_loops != NULL)
999 struct loop *loop
1000 = find_common_loop (single_pred (ret)->loop_father,
1001 single_succ (ret)->loop_father);
1002 rescan_loop_exit (e, false, true);
1003 add_bb_to_loop (ret, loop);
1007 return ret;
1010 /* Returns true if we can duplicate basic block BB. */
1012 bool
1013 can_duplicate_block_p (const_basic_block bb)
1015 if (!cfg_hooks->can_duplicate_block_p)
1016 internal_error ("%s does not support can_duplicate_block_p",
1017 cfg_hooks->name);
1019 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1020 return false;
1022 return cfg_hooks->can_duplicate_block_p (bb);
1025 /* Duplicates basic block BB and redirects edge E to it. Returns the
1026 new basic block. The new basic block is placed after the basic block
1027 AFTER. */
1029 basic_block
1030 duplicate_block (basic_block bb, edge e, basic_block after)
1032 edge s, n;
1033 basic_block new_bb;
1034 gcov_type new_count = e ? e->count : 0;
1035 edge_iterator ei;
1037 if (!cfg_hooks->duplicate_block)
1038 internal_error ("%s does not support duplicate_block",
1039 cfg_hooks->name);
1041 if (bb->count < new_count)
1042 new_count = bb->count;
1044 gcc_checking_assert (can_duplicate_block_p (bb));
1046 new_bb = cfg_hooks->duplicate_block (bb);
1047 if (after)
1048 move_block_after (new_bb, after);
1050 new_bb->flags = bb->flags;
1051 FOR_EACH_EDGE (s, ei, bb->succs)
1053 /* Since we are creating edges from a new block to successors
1054 of another block (which therefore are known to be disjoint), there
1055 is no need to actually check for duplicated edges. */
1056 n = unchecked_make_edge (new_bb, s->dest, s->flags);
1057 n->probability = s->probability;
1058 if (e && bb->count)
1060 /* Take care for overflows! */
1061 n->count = s->count * (new_count * 10000 / bb->count) / 10000;
1062 s->count -= n->count;
1064 else
1065 n->count = s->count;
1066 n->aux = s->aux;
1069 if (e)
1071 new_bb->count = new_count;
1072 bb->count -= new_count;
1074 new_bb->frequency = EDGE_FREQUENCY (e);
1075 bb->frequency -= EDGE_FREQUENCY (e);
1077 redirect_edge_and_branch_force (e, new_bb);
1079 if (bb->count < 0)
1080 bb->count = 0;
1081 if (bb->frequency < 0)
1082 bb->frequency = 0;
1084 else
1086 new_bb->count = bb->count;
1087 new_bb->frequency = bb->frequency;
1090 set_bb_original (new_bb, bb);
1091 set_bb_copy (bb, new_bb);
1093 /* Add the new block to the copy of the loop of BB, or directly to the loop
1094 of BB if the loop is not being copied. */
1095 if (current_loops != NULL)
1097 struct loop *cloop = bb->loop_father;
1098 struct loop *copy = get_loop_copy (cloop);
1099 /* If we copied the loop header block but not the loop
1100 we have created a loop with multiple entries. Ditch the loop,
1101 add the new block to the outer loop and arrange for a fixup. */
1102 if (!copy
1103 && cloop->header == bb)
1105 add_bb_to_loop (new_bb, loop_outer (cloop));
1106 cloop->header = NULL;
1107 cloop->latch = NULL;
1108 loops_state_set (LOOPS_NEED_FIXUP);
1110 else
1112 add_bb_to_loop (new_bb, copy ? copy : cloop);
1113 /* If we copied the loop latch block but not the loop, adjust
1114 loop state. */
1115 if (!copy
1116 && cloop->latch == bb)
1118 cloop->latch = NULL;
1119 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
1124 return new_bb;
1127 /* Return 1 if BB ends with a call, possibly followed by some
1128 instructions that must stay with the call, 0 otherwise. */
1130 bool
1131 block_ends_with_call_p (basic_block bb)
1133 if (!cfg_hooks->block_ends_with_call_p)
1134 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
1136 return (cfg_hooks->block_ends_with_call_p) (bb);
1139 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1141 bool
1142 block_ends_with_condjump_p (const_basic_block bb)
1144 if (!cfg_hooks->block_ends_with_condjump_p)
1145 internal_error ("%s does not support block_ends_with_condjump_p",
1146 cfg_hooks->name);
1148 return (cfg_hooks->block_ends_with_condjump_p) (bb);
1151 /* Add fake edges to the function exit for any non constant and non noreturn
1152 calls, volatile inline assembly in the bitmap of blocks specified by
1153 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1154 that were split.
1156 The goal is to expose cases in which entering a basic block does not imply
1157 that all subsequent instructions must be executed. */
1160 flow_call_edges_add (sbitmap blocks)
1162 if (!cfg_hooks->flow_call_edges_add)
1163 internal_error ("%s does not support flow_call_edges_add",
1164 cfg_hooks->name);
1166 return (cfg_hooks->flow_call_edges_add) (blocks);
1169 /* This function is called immediately after edge E is added to the
1170 edge vector E->dest->preds. */
1172 void
1173 execute_on_growing_pred (edge e)
1175 if (cfg_hooks->execute_on_growing_pred)
1176 cfg_hooks->execute_on_growing_pred (e);
1179 /* This function is called immediately before edge E is removed from
1180 the edge vector E->dest->preds. */
1182 void
1183 execute_on_shrinking_pred (edge e)
1185 if (cfg_hooks->execute_on_shrinking_pred)
1186 cfg_hooks->execute_on_shrinking_pred (e);
1189 /* This is used inside loop versioning when we want to insert
1190 stmts/insns on the edges, which have a different behavior
1191 in tree's and in RTL, so we made a CFG hook. */
1192 void
1193 lv_flush_pending_stmts (edge e)
1195 if (cfg_hooks->flush_pending_stmts)
1196 cfg_hooks->flush_pending_stmts (e);
1199 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1200 a new version of the loop basic-blocks, the parameters here are
1201 exactly the same as in duplicate_loop_to_header_edge or
1202 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1203 additional work to maintain ssa information that's why there is
1204 a need to call the tree_duplicate_loop_to_header_edge rather
1205 than duplicate_loop_to_header_edge when we are in tree mode. */
1206 bool
1207 cfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e,
1208 unsigned int ndupl,
1209 sbitmap wont_exit, edge orig,
1210 vec<edge> *to_remove,
1211 int flags)
1213 gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge);
1214 return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e,
1215 ndupl, wont_exit,
1216 orig, to_remove,
1217 flags);
1220 /* Conditional jumps are represented differently in trees and RTL,
1221 this hook takes a basic block that is known to have a cond jump
1222 at its end and extracts the taken and not taken edges out of it
1223 and store it in E1 and E2 respectively. */
1224 void
1225 extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1227 gcc_assert (cfg_hooks->extract_cond_bb_edges);
1228 cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1231 /* Responsible for updating the ssa info (PHI nodes) on the
1232 new condition basic block that guards the versioned loop. */
1233 void
1234 lv_adjust_loop_header_phi (basic_block first, basic_block second,
1235 basic_block new_block, edge e)
1237 if (cfg_hooks->lv_adjust_loop_header_phi)
1238 cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1241 /* Conditions in trees and RTL are different so we need
1242 a different handling when we add the condition to the
1243 versioning code. */
1244 void
1245 lv_add_condition_to_bb (basic_block first, basic_block second,
1246 basic_block new_block, void *cond)
1248 gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1249 cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1252 /* Checks whether all N blocks in BBS array can be copied. */
1253 bool
1254 can_copy_bbs_p (basic_block *bbs, unsigned n)
1256 unsigned i;
1257 edge e;
1258 int ret = true;
1260 for (i = 0; i < n; i++)
1261 bbs[i]->flags |= BB_DUPLICATED;
1263 for (i = 0; i < n; i++)
1265 /* In case we should redirect abnormal edge during duplication, fail. */
1266 edge_iterator ei;
1267 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1268 if ((e->flags & EDGE_ABNORMAL)
1269 && (e->dest->flags & BB_DUPLICATED))
1271 ret = false;
1272 goto end;
1275 if (!can_duplicate_block_p (bbs[i]))
1277 ret = false;
1278 break;
1282 end:
1283 for (i = 0; i < n; i++)
1284 bbs[i]->flags &= ~BB_DUPLICATED;
1286 return ret;
1289 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1290 are placed into array NEW_BBS in the same order. Edges from basic blocks
1291 in BBS are also duplicated and copies of those that lead into BBS are
1292 redirected to appropriate newly created block. The function assigns bbs
1293 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1294 loop, so this must be set up correctly in advance)
1296 If UPDATE_DOMINANCE is true then this function updates dominators locally
1297 (LOOPS structure that contains the information about dominators is passed
1298 to enable this), otherwise it does not update the dominator information
1299 and it assumed that the caller will do this, perhaps by destroying and
1300 recreating it instead of trying to do an incremental update like this
1301 function does when update_dominance is true.
1303 BASE is the superloop to that basic block belongs; if its header or latch
1304 is copied, we do not set the new blocks as header or latch.
1306 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1307 also in the same order.
1309 Newly created basic blocks are put after the basic block AFTER in the
1310 instruction stream, and the order of the blocks in BBS array is preserved. */
1312 void
1313 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1314 edge *edges, unsigned num_edges, edge *new_edges,
1315 struct loop *base, basic_block after, bool update_dominance)
1317 unsigned i, j;
1318 basic_block bb, new_bb, dom_bb;
1319 edge e;
1321 /* Duplicate bbs, update dominators, assign bbs to loops. */
1322 for (i = 0; i < n; i++)
1324 /* Duplicate. */
1325 bb = bbs[i];
1326 new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
1327 after = new_bb;
1328 bb->flags |= BB_DUPLICATED;
1329 if (bb->loop_father)
1331 /* Possibly set loop header. */
1332 if (bb->loop_father->header == bb && bb->loop_father != base)
1333 new_bb->loop_father->header = new_bb;
1334 /* Or latch. */
1335 if (bb->loop_father->latch == bb && bb->loop_father != base)
1336 new_bb->loop_father->latch = new_bb;
1340 /* Set dominators. */
1341 if (update_dominance)
1343 for (i = 0; i < n; i++)
1345 bb = bbs[i];
1346 new_bb = new_bbs[i];
1348 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1349 if (dom_bb->flags & BB_DUPLICATED)
1351 dom_bb = get_bb_copy (dom_bb);
1352 set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1357 /* Redirect edges. */
1358 for (j = 0; j < num_edges; j++)
1359 new_edges[j] = NULL;
1360 for (i = 0; i < n; i++)
1362 edge_iterator ei;
1363 new_bb = new_bbs[i];
1364 bb = bbs[i];
1366 FOR_EACH_EDGE (e, ei, new_bb->succs)
1368 for (j = 0; j < num_edges; j++)
1369 if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1370 new_edges[j] = e;
1372 if (!(e->dest->flags & BB_DUPLICATED))
1373 continue;
1374 redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1378 /* Clear information about duplicates. */
1379 for (i = 0; i < n; i++)
1380 bbs[i]->flags &= ~BB_DUPLICATED;
1383 /* Return true if BB contains only labels or non-executable
1384 instructions */
1385 bool
1386 empty_block_p (basic_block bb)
1388 gcc_assert (cfg_hooks->empty_block_p);
1389 return cfg_hooks->empty_block_p (bb);
1392 /* Split a basic block if it ends with a conditional branch and if
1393 the other part of the block is not empty. */
1394 basic_block
1395 split_block_before_cond_jump (basic_block bb)
1397 gcc_assert (cfg_hooks->split_block_before_cond_jump);
1398 return cfg_hooks->split_block_before_cond_jump (bb);
1401 /* Work-horse for passes.c:check_profile_consistency.
1402 Do book-keeping of the CFG for the profile consistency checker.
1403 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
1404 then do post-pass accounting. Store the counting in RECORD. */
1406 void
1407 account_profile_record (struct profile_record *record, int after_pass)
1409 basic_block bb;
1410 edge_iterator ei;
1411 edge e;
1412 int sum;
1413 gcov_type lsum;
1415 FOR_ALL_BB_FN (bb, cfun)
1417 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
1418 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
1420 sum = 0;
1421 FOR_EACH_EDGE (e, ei, bb->succs)
1422 sum += e->probability;
1423 if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
1424 record->num_mismatched_freq_out[after_pass]++;
1425 lsum = 0;
1426 FOR_EACH_EDGE (e, ei, bb->succs)
1427 lsum += e->count;
1428 if (EDGE_COUNT (bb->succs)
1429 && (lsum - bb->count > 100 || lsum - bb->count < -100))
1430 record->num_mismatched_count_out[after_pass]++;
1432 if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1433 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
1435 sum = 0;
1436 FOR_EACH_EDGE (e, ei, bb->preds)
1437 sum += EDGE_FREQUENCY (e);
1438 if (abs (sum - bb->frequency) > 100
1439 || (MAX (sum, bb->frequency) > 10
1440 && abs ((sum - bb->frequency) * 100 / (MAX (sum, bb->frequency) + 1)) > 10))
1441 record->num_mismatched_freq_in[after_pass]++;
1442 lsum = 0;
1443 FOR_EACH_EDGE (e, ei, bb->preds)
1444 lsum += e->count;
1445 if (lsum - bb->count > 100 || lsum - bb->count < -100)
1446 record->num_mismatched_count_in[after_pass]++;
1448 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
1449 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1450 continue;
1451 gcc_assert (cfg_hooks->account_profile_record);
1452 cfg_hooks->account_profile_record (bb, after_pass, record);