gcc/
[official-gcc.git] / gcc / cfghooks.c
blobc649b7e8fd282637ffe1394bb77f106bbb347544
1 /* Hooks for cfg representation specific functions.
2 Copyright (C) 2003-2015 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 "alias.h"
27 #include "symtab.h"
28 #include "tree.h"
29 #include "rtl.h"
30 #include "predict.h"
31 #include "hard-reg-set.h"
32 #include "function.h"
33 #include "dominance.h"
34 #include "cfg.h"
35 #include "cfganal.h"
36 #include "basic-block.h"
37 #include "tree-ssa.h"
38 #include "timevar.h"
39 #include "diagnostic-core.h"
40 #include "cfgloop.h"
41 #include "pretty-print.h"
43 /* A pointer to one of the hooks containers. */
44 static struct cfg_hooks *cfg_hooks;
46 /* Initialization of functions specific to the rtl IR. */
47 void
48 rtl_register_cfg_hooks (void)
50 cfg_hooks = &rtl_cfg_hooks;
53 /* Initialization of functions specific to the rtl IR. */
54 void
55 cfg_layout_rtl_register_cfg_hooks (void)
57 cfg_hooks = &cfg_layout_rtl_cfg_hooks;
60 /* Initialization of functions specific to the tree IR. */
62 void
63 gimple_register_cfg_hooks (void)
65 cfg_hooks = &gimple_cfg_hooks;
68 struct cfg_hooks
69 get_cfg_hooks (void)
71 return *cfg_hooks;
74 void
75 set_cfg_hooks (struct cfg_hooks new_cfg_hooks)
77 *cfg_hooks = new_cfg_hooks;
80 /* Returns current ir type. */
82 enum ir_type
83 current_ir_type (void)
85 if (cfg_hooks == &gimple_cfg_hooks)
86 return IR_GIMPLE;
87 else if (cfg_hooks == &rtl_cfg_hooks)
88 return IR_RTL_CFGRTL;
89 else if (cfg_hooks == &cfg_layout_rtl_cfg_hooks)
90 return IR_RTL_CFGLAYOUT;
91 else
92 gcc_unreachable ();
95 /* Verify the CFG consistency.
97 Currently it does following: checks edge and basic block list correctness
98 and calls into IL dependent checking then. */
100 DEBUG_FUNCTION void
101 verify_flow_info (void)
103 size_t *edge_checksum;
104 int err = 0;
105 basic_block bb, last_bb_seen;
106 basic_block *last_visited;
108 timevar_push (TV_CFG_VERIFY);
109 last_visited = XCNEWVEC (basic_block, last_basic_block_for_fn (cfun));
110 edge_checksum = XCNEWVEC (size_t, last_basic_block_for_fn (cfun));
112 /* Check bb chain & numbers. */
113 last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
114 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
116 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
117 && bb != BASIC_BLOCK_FOR_FN (cfun, bb->index))
119 error ("bb %d on wrong place", bb->index);
120 err = 1;
123 if (bb->prev_bb != last_bb_seen)
125 error ("prev_bb of %d should be %d, not %d",
126 bb->index, last_bb_seen->index, bb->prev_bb->index);
127 err = 1;
130 last_bb_seen = bb;
133 /* Now check the basic blocks (boundaries etc.) */
134 FOR_EACH_BB_REVERSE_FN (bb, cfun)
136 int n_fallthru = 0;
137 edge e;
138 edge_iterator ei;
140 if (bb->loop_father != NULL && current_loops == NULL)
142 error ("verify_flow_info: Block %i has loop_father, but there are no loops",
143 bb->index);
144 err = 1;
146 if (bb->loop_father == NULL && current_loops != NULL)
148 error ("verify_flow_info: Block %i lacks loop_father", bb->index);
149 err = 1;
152 if (bb->count < 0)
154 error ("verify_flow_info: Wrong count of block %i %i",
155 bb->index, (int)bb->count);
156 err = 1;
158 if (bb->frequency < 0)
160 error ("verify_flow_info: Wrong frequency of block %i %i",
161 bb->index, bb->frequency);
162 err = 1;
164 FOR_EACH_EDGE (e, ei, bb->succs)
166 if (last_visited [e->dest->index] == bb)
168 error ("verify_flow_info: Duplicate edge %i->%i",
169 e->src->index, e->dest->index);
170 err = 1;
172 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
174 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
175 e->src->index, e->dest->index, e->probability);
176 err = 1;
178 if (e->count < 0)
180 error ("verify_flow_info: Wrong count of edge %i->%i %i",
181 e->src->index, e->dest->index, (int)e->count);
182 err = 1;
185 last_visited [e->dest->index] = bb;
187 if (e->flags & EDGE_FALLTHRU)
188 n_fallthru++;
190 if (e->src != bb)
192 error ("verify_flow_info: Basic block %d succ edge is corrupted",
193 bb->index);
194 fprintf (stderr, "Predecessor: ");
195 dump_edge_info (stderr, e, TDF_DETAILS, 0);
196 fprintf (stderr, "\nSuccessor: ");
197 dump_edge_info (stderr, e, TDF_DETAILS, 1);
198 fprintf (stderr, "\n");
199 err = 1;
202 edge_checksum[e->dest->index] += (size_t) e;
204 if (n_fallthru > 1)
206 error ("wrong amount of branch edges after unconditional jump %i", bb->index);
207 err = 1;
210 FOR_EACH_EDGE (e, ei, bb->preds)
212 if (e->dest != bb)
214 error ("basic block %d pred edge is corrupted", bb->index);
215 fputs ("Predecessor: ", stderr);
216 dump_edge_info (stderr, e, TDF_DETAILS, 0);
217 fputs ("\nSuccessor: ", stderr);
218 dump_edge_info (stderr, e, TDF_DETAILS, 1);
219 fputc ('\n', stderr);
220 err = 1;
223 if (ei.index != e->dest_idx)
225 error ("basic block %d pred edge is corrupted", bb->index);
226 error ("its dest_idx should be %d, not %d",
227 ei.index, e->dest_idx);
228 fputs ("Predecessor: ", stderr);
229 dump_edge_info (stderr, e, TDF_DETAILS, 0);
230 fputs ("\nSuccessor: ", stderr);
231 dump_edge_info (stderr, e, TDF_DETAILS, 1);
232 fputc ('\n', stderr);
233 err = 1;
236 edge_checksum[e->dest->index] -= (size_t) e;
240 /* Complete edge checksumming for ENTRY and EXIT. */
242 edge e;
243 edge_iterator ei;
245 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
246 edge_checksum[e->dest->index] += (size_t) e;
248 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
249 edge_checksum[e->dest->index] -= (size_t) e;
252 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
253 if (edge_checksum[bb->index])
255 error ("basic block %i edge lists are corrupted", bb->index);
256 err = 1;
259 last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
261 /* Clean up. */
262 free (last_visited);
263 free (edge_checksum);
265 if (cfg_hooks->verify_flow_info)
266 err |= cfg_hooks->verify_flow_info ();
267 if (err)
268 internal_error ("verify_flow_info failed");
269 timevar_pop (TV_CFG_VERIFY);
272 /* Print out one basic block BB to file OUTF. INDENT is printed at the
273 start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
275 This function takes care of the purely graph related information.
276 The cfg hook for the active representation should dump
277 representation-specific information. */
279 void
280 dump_bb (FILE *outf, basic_block bb, int indent, int flags)
282 if (flags & TDF_BLOCKS)
283 dump_bb_info (outf, bb, indent, flags, true, false);
284 if (cfg_hooks->dump_bb)
285 cfg_hooks->dump_bb (outf, bb, indent, flags);
286 if (flags & TDF_BLOCKS)
287 dump_bb_info (outf, bb, indent, flags, false, true);
288 fputc ('\n', outf);
291 DEBUG_FUNCTION void
292 debug (basic_block_def &ref)
294 dump_bb (stderr, &ref, 0, 0);
297 DEBUG_FUNCTION void
298 debug (basic_block_def *ptr)
300 if (ptr)
301 debug (*ptr);
302 else
303 fprintf (stderr, "<nil>\n");
307 /* Dumps basic block BB to pretty-printer PP, for use as a label of
308 a DOT graph record-node. The implementation of this hook is
309 expected to write the label to the stream that is attached to PP.
310 Field separators between instructions are pipe characters printed
311 verbatim. Instructions should be written with some characters
312 escaped, using pp_write_text_as_dot_label_to_stream(). */
314 void
315 dump_bb_for_graph (pretty_printer *pp, basic_block bb)
317 if (!cfg_hooks->dump_bb_for_graph)
318 internal_error ("%s does not support dump_bb_for_graph",
319 cfg_hooks->name);
320 if (bb->count)
321 pp_printf (pp, "COUNT:" "%" PRId64, bb->count);
322 pp_printf (pp, " FREQ:%i |", bb->frequency);
323 pp_write_text_to_stream (pp);
324 if (!(dump_flags & TDF_SLIM))
325 cfg_hooks->dump_bb_for_graph (pp, bb);
328 /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
329 void
330 dump_flow_info (FILE *file, int flags)
332 basic_block bb;
334 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun),
335 n_edges_for_fn (cfun));
336 FOR_ALL_BB_FN (bb, cfun)
337 dump_bb (file, bb, 0, flags);
339 putc ('\n', file);
342 /* Like above, but dump to stderr. To be called from debuggers. */
343 void debug_flow_info (void);
344 DEBUG_FUNCTION void
345 debug_flow_info (void)
347 dump_flow_info (stderr, TDF_DETAILS);
350 /* Redirect edge E to the given basic block DEST and update underlying program
351 representation. Returns edge representing redirected branch (that may not
352 be equivalent to E in the case of duplicate edges being removed) or NULL
353 if edge is not easily redirectable for whatever reason. */
355 edge
356 redirect_edge_and_branch (edge e, basic_block dest)
358 edge ret;
360 if (!cfg_hooks->redirect_edge_and_branch)
361 internal_error ("%s does not support redirect_edge_and_branch",
362 cfg_hooks->name);
364 ret = cfg_hooks->redirect_edge_and_branch (e, dest);
366 /* If RET != E, then either the redirection failed, or the edge E
367 was removed since RET already lead to the same destination. */
368 if (current_loops != NULL && ret == e)
369 rescan_loop_exit (e, false, false);
371 return ret;
374 /* Returns true if it is possible to remove the edge E by redirecting it
375 to the destination of the other edge going from its source. */
377 bool
378 can_remove_branch_p (const_edge e)
380 if (!cfg_hooks->can_remove_branch_p)
381 internal_error ("%s does not support can_remove_branch_p",
382 cfg_hooks->name);
384 if (EDGE_COUNT (e->src->succs) != 2)
385 return false;
387 return cfg_hooks->can_remove_branch_p (e);
390 /* Removes E, by redirecting it to the destination of the other edge going
391 from its source. Can_remove_branch_p must be true for E, hence this
392 operation cannot fail. */
394 void
395 remove_branch (edge e)
397 edge other;
398 basic_block src = e->src;
399 int irr;
401 gcc_assert (EDGE_COUNT (e->src->succs) == 2);
403 other = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
404 irr = other->flags & EDGE_IRREDUCIBLE_LOOP;
406 e = redirect_edge_and_branch (e, other->dest);
407 gcc_assert (e != NULL);
409 e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
410 e->flags |= irr;
413 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
415 void
416 remove_edge (edge e)
418 if (current_loops != NULL)
419 rescan_loop_exit (e, false, true);
421 /* This is probably not needed, but it doesn't hurt. */
422 /* FIXME: This should be called via a remove_edge hook. */
423 if (current_ir_type () == IR_GIMPLE)
424 redirect_edge_var_map_clear (e);
426 remove_edge_raw (e);
429 /* Like redirect_edge_succ but avoid possible duplicate edge. */
431 edge
432 redirect_edge_succ_nodup (edge e, basic_block new_succ)
434 edge s;
436 s = find_edge (e->src, new_succ);
437 if (s && s != e)
439 s->flags |= e->flags;
440 s->probability += e->probability;
441 if (s->probability > REG_BR_PROB_BASE)
442 s->probability = REG_BR_PROB_BASE;
443 s->count += e->count;
444 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
445 redirect_edge_var_map_dup (s, e);
446 remove_edge (e);
447 e = s;
449 else
450 redirect_edge_succ (e, new_succ);
452 return e;
455 /* Redirect the edge E to basic block DEST even if it requires creating
456 of a new basic block; then it returns the newly created basic block.
457 Aborts when redirection is impossible. */
459 basic_block
460 redirect_edge_and_branch_force (edge e, basic_block dest)
462 basic_block ret, src = e->src;
464 if (!cfg_hooks->redirect_edge_and_branch_force)
465 internal_error ("%s does not support redirect_edge_and_branch_force",
466 cfg_hooks->name);
468 if (current_loops != NULL)
469 rescan_loop_exit (e, false, true);
471 ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
473 if (ret != NULL && dom_info_available_p (CDI_DOMINATORS))
474 set_immediate_dominator (CDI_DOMINATORS, ret, src);
476 if (current_loops != NULL)
478 if (ret != NULL)
480 struct loop *loop
481 = find_common_loop (single_pred (ret)->loop_father,
482 single_succ (ret)->loop_father);
483 add_bb_to_loop (ret, loop);
485 else if (find_edge (src, dest) == e)
486 rescan_loop_exit (e, true, false);
489 return ret;
492 /* Splits basic block BB after the specified instruction I (but at least after
493 the labels). If I is NULL, splits just after labels. The newly created edge
494 is returned. The new basic block is created just after the old one. */
496 static edge
497 split_block_1 (basic_block bb, void *i)
499 basic_block new_bb;
500 edge res;
502 if (!cfg_hooks->split_block)
503 internal_error ("%s does not support split_block", cfg_hooks->name);
505 new_bb = cfg_hooks->split_block (bb, i);
506 if (!new_bb)
507 return NULL;
509 new_bb->count = bb->count;
510 new_bb->frequency = bb->frequency;
511 new_bb->discriminator = bb->discriminator;
513 if (dom_info_available_p (CDI_DOMINATORS))
515 redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
516 set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
519 if (current_loops != NULL)
521 edge_iterator ei;
522 edge e;
523 add_bb_to_loop (new_bb, bb->loop_father);
524 /* Identify all loops bb may have been the latch of and adjust them. */
525 FOR_EACH_EDGE (e, ei, new_bb->succs)
526 if (e->dest->loop_father->latch == bb)
527 e->dest->loop_father->latch = new_bb;
530 res = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
532 if (bb->flags & BB_IRREDUCIBLE_LOOP)
534 new_bb->flags |= BB_IRREDUCIBLE_LOOP;
535 res->flags |= EDGE_IRREDUCIBLE_LOOP;
538 return res;
541 edge
542 split_block (basic_block bb, gimple i)
544 return split_block_1 (bb, i);
547 edge
548 split_block (basic_block bb, rtx i)
550 return split_block_1 (bb, i);
553 /* Splits block BB just after labels. The newly created edge is returned. */
555 edge
556 split_block_after_labels (basic_block bb)
558 return split_block_1 (bb, NULL);
561 /* Moves block BB immediately after block AFTER. Returns false if the
562 movement was impossible. */
564 bool
565 move_block_after (basic_block bb, basic_block after)
567 bool ret;
569 if (!cfg_hooks->move_block_after)
570 internal_error ("%s does not support move_block_after", cfg_hooks->name);
572 ret = cfg_hooks->move_block_after (bb, after);
574 return ret;
577 /* Deletes the basic block BB. */
579 void
580 delete_basic_block (basic_block bb)
582 if (!cfg_hooks->delete_basic_block)
583 internal_error ("%s does not support delete_basic_block", cfg_hooks->name);
585 cfg_hooks->delete_basic_block (bb);
587 if (current_loops != NULL)
589 struct loop *loop = bb->loop_father;
591 /* If we remove the header or the latch of a loop, mark the loop for
592 removal. */
593 if (loop->latch == bb
594 || loop->header == bb)
595 mark_loop_for_removal (loop);
597 remove_bb_from_loops (bb);
600 /* Remove the edges into and out of this block. Note that there may
601 indeed be edges in, if we are removing an unreachable loop. */
602 while (EDGE_COUNT (bb->preds) != 0)
603 remove_edge (EDGE_PRED (bb, 0));
604 while (EDGE_COUNT (bb->succs) != 0)
605 remove_edge (EDGE_SUCC (bb, 0));
607 if (dom_info_available_p (CDI_DOMINATORS))
608 delete_from_dominance_info (CDI_DOMINATORS, bb);
609 if (dom_info_available_p (CDI_POST_DOMINATORS))
610 delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
612 /* Remove the basic block from the array. */
613 expunge_block (bb);
616 /* Splits edge E and returns the newly created basic block. */
618 basic_block
619 split_edge (edge e)
621 basic_block ret;
622 gcov_type count = e->count;
623 int freq = EDGE_FREQUENCY (e);
624 edge f;
625 bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
626 struct loop *loop;
627 basic_block src = e->src, dest = e->dest;
629 if (!cfg_hooks->split_edge)
630 internal_error ("%s does not support split_edge", cfg_hooks->name);
632 if (current_loops != NULL)
633 rescan_loop_exit (e, false, true);
635 ret = cfg_hooks->split_edge (e);
636 ret->count = count;
637 ret->frequency = freq;
638 single_succ_edge (ret)->probability = REG_BR_PROB_BASE;
639 single_succ_edge (ret)->count = count;
641 if (irr)
643 ret->flags |= BB_IRREDUCIBLE_LOOP;
644 single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
645 single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
648 if (dom_info_available_p (CDI_DOMINATORS))
649 set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
651 if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
653 /* There are two cases:
655 If the immediate dominator of e->dest is not e->src, it
656 remains unchanged.
658 If immediate dominator of e->dest is e->src, it may become
659 ret, provided that all other predecessors of e->dest are
660 dominated by e->dest. */
662 if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
663 == single_pred (ret))
665 edge_iterator ei;
666 FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
668 if (f == single_succ_edge (ret))
669 continue;
671 if (!dominated_by_p (CDI_DOMINATORS, f->src,
672 single_succ (ret)))
673 break;
676 if (!f)
677 set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
681 if (current_loops != NULL)
683 loop = find_common_loop (src->loop_father, dest->loop_father);
684 add_bb_to_loop (ret, loop);
686 /* If we split the latch edge of loop adjust the latch block. */
687 if (loop->latch == src
688 && loop->header == dest)
689 loop->latch = ret;
692 return ret;
695 /* Creates a new basic block just after the basic block AFTER.
696 HEAD and END are the first and the last statement belonging
697 to the block. If both are NULL, an empty block is created. */
699 static basic_block
700 create_basic_block_1 (void *head, void *end, basic_block after)
702 basic_block ret;
704 if (!cfg_hooks->create_basic_block)
705 internal_error ("%s does not support create_basic_block", cfg_hooks->name);
707 ret = cfg_hooks->create_basic_block (head, end, after);
709 if (dom_info_available_p (CDI_DOMINATORS))
710 add_to_dominance_info (CDI_DOMINATORS, ret);
711 if (dom_info_available_p (CDI_POST_DOMINATORS))
712 add_to_dominance_info (CDI_POST_DOMINATORS, ret);
714 return ret;
717 basic_block
718 create_basic_block (gimple_seq seq, basic_block after)
720 return create_basic_block_1 (seq, NULL, after);
723 basic_block
724 create_basic_block (rtx head, rtx end, basic_block after)
726 return create_basic_block_1 (head, end, after);
730 /* Creates an empty basic block just after basic block AFTER. */
732 basic_block
733 create_empty_bb (basic_block after)
735 return create_basic_block_1 (NULL, NULL, after);
738 /* Checks whether we may merge blocks BB1 and BB2. */
740 bool
741 can_merge_blocks_p (basic_block bb1, basic_block bb2)
743 bool ret;
745 if (!cfg_hooks->can_merge_blocks_p)
746 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name);
748 ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
750 return ret;
753 void
754 predict_edge (edge e, enum br_predictor predictor, int probability)
756 if (!cfg_hooks->predict_edge)
757 internal_error ("%s does not support predict_edge", cfg_hooks->name);
759 cfg_hooks->predict_edge (e, predictor, probability);
762 bool
763 predicted_by_p (const_basic_block bb, enum br_predictor predictor)
765 if (!cfg_hooks->predict_edge)
766 internal_error ("%s does not support predicted_by_p", cfg_hooks->name);
768 return cfg_hooks->predicted_by_p (bb, predictor);
771 /* Merges basic block B into basic block A. */
773 void
774 merge_blocks (basic_block a, basic_block b)
776 edge e;
777 edge_iterator ei;
779 if (!cfg_hooks->merge_blocks)
780 internal_error ("%s does not support merge_blocks", cfg_hooks->name);
782 cfg_hooks->merge_blocks (a, b);
784 if (current_loops != NULL)
786 /* If the block we merge into is a loop header do nothing unless ... */
787 if (a->loop_father->header == a)
789 /* ... we merge two loop headers, in which case we kill
790 the inner loop. */
791 if (b->loop_father->header == b)
792 mark_loop_for_removal (b->loop_father);
794 /* If we merge a loop header into its predecessor, update the loop
795 structure. */
796 else if (b->loop_father->header == b)
798 remove_bb_from_loops (a);
799 add_bb_to_loop (a, b->loop_father);
800 a->loop_father->header = a;
802 /* If we merge a loop latch into its predecessor, update the loop
803 structure. */
804 if (b->loop_father->latch
805 && b->loop_father->latch == b)
806 b->loop_father->latch = a;
807 remove_bb_from_loops (b);
810 /* Normally there should only be one successor of A and that is B, but
811 partway though the merge of blocks for conditional_execution we'll
812 be merging a TEST block with THEN and ELSE successors. Free the
813 whole lot of them and hope the caller knows what they're doing. */
815 while (EDGE_COUNT (a->succs) != 0)
816 remove_edge (EDGE_SUCC (a, 0));
818 /* Adjust the edges out of B for the new owner. */
819 FOR_EACH_EDGE (e, ei, b->succs)
821 e->src = a;
822 if (current_loops != NULL)
824 /* If b was a latch, a now is. */
825 if (e->dest->loop_father->latch == b)
826 e->dest->loop_father->latch = a;
827 rescan_loop_exit (e, true, false);
830 a->succs = b->succs;
831 a->flags |= b->flags;
833 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
834 b->preds = b->succs = NULL;
836 if (dom_info_available_p (CDI_DOMINATORS))
837 redirect_immediate_dominators (CDI_DOMINATORS, b, a);
839 if (dom_info_available_p (CDI_DOMINATORS))
840 delete_from_dominance_info (CDI_DOMINATORS, b);
841 if (dom_info_available_p (CDI_POST_DOMINATORS))
842 delete_from_dominance_info (CDI_POST_DOMINATORS, b);
844 expunge_block (b);
847 /* Split BB into entry part and the rest (the rest is the newly created block).
848 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
849 part. Returns the edge connecting the entry part to the rest. */
851 edge
852 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
853 void (*new_bb_cbk) (basic_block))
855 edge e, fallthru;
856 edge_iterator ei;
857 basic_block dummy, jump;
858 struct loop *loop, *ploop, *cloop;
860 if (!cfg_hooks->make_forwarder_block)
861 internal_error ("%s does not support make_forwarder_block",
862 cfg_hooks->name);
864 fallthru = split_block_after_labels (bb);
865 dummy = fallthru->src;
866 dummy->count = 0;
867 dummy->frequency = 0;
868 fallthru->count = 0;
869 bb = fallthru->dest;
871 /* Redirect back edges we want to keep. */
872 for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
874 basic_block e_src;
876 if (redirect_edge_p (e))
878 dummy->frequency += EDGE_FREQUENCY (e);
879 if (dummy->frequency > BB_FREQ_MAX)
880 dummy->frequency = BB_FREQ_MAX;
882 dummy->count += e->count;
883 fallthru->count += e->count;
884 ei_next (&ei);
885 continue;
888 e_src = e->src;
889 jump = redirect_edge_and_branch_force (e, bb);
890 if (jump != NULL)
892 /* If we redirected the loop latch edge, the JUMP block now acts like
893 the new latch of the loop. */
894 if (current_loops != NULL
895 && dummy->loop_father != NULL
896 && dummy->loop_father->header == dummy
897 && dummy->loop_father->latch == e_src)
898 dummy->loop_father->latch = jump;
900 if (new_bb_cbk != NULL)
901 new_bb_cbk (jump);
905 if (dom_info_available_p (CDI_DOMINATORS))
907 vec<basic_block> doms_to_fix;
908 doms_to_fix.create (2);
909 doms_to_fix.quick_push (dummy);
910 doms_to_fix.quick_push (bb);
911 iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
912 doms_to_fix.release ();
915 if (current_loops != NULL)
917 /* If we do not split a loop header, then both blocks belong to the
918 same loop. In case we split loop header and do not redirect the
919 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
920 BB becomes the new header. If latch is not recorded for the loop,
921 we leave this updating on the caller (this may only happen during
922 loop analysis). */
923 loop = dummy->loop_father;
924 if (loop->header == dummy
925 && loop->latch != NULL
926 && find_edge (loop->latch, dummy) == NULL)
928 remove_bb_from_loops (dummy);
929 loop->header = bb;
931 cloop = loop;
932 FOR_EACH_EDGE (e, ei, dummy->preds)
934 cloop = find_common_loop (cloop, e->src->loop_father);
936 add_bb_to_loop (dummy, cloop);
939 /* In case we split loop latch, update it. */
940 for (ploop = loop; ploop; ploop = loop_outer (ploop))
941 if (ploop->latch == dummy)
942 ploop->latch = bb;
945 cfg_hooks->make_forwarder_block (fallthru);
947 return fallthru;
950 /* Try to make the edge fallthru. */
952 void
953 tidy_fallthru_edge (edge e)
955 if (cfg_hooks->tidy_fallthru_edge)
956 cfg_hooks->tidy_fallthru_edge (e);
959 /* Fix up edges that now fall through, or rather should now fall through
960 but previously required a jump around now deleted blocks. Simplify
961 the search by only examining blocks numerically adjacent, since this
962 is how they were created.
964 ??? This routine is currently RTL specific. */
966 void
967 tidy_fallthru_edges (void)
969 basic_block b, c;
971 if (!cfg_hooks->tidy_fallthru_edge)
972 return;
974 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
975 return;
977 FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb,
978 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb, next_bb)
980 edge s;
982 c = b->next_bb;
984 /* We care about simple conditional or unconditional jumps with
985 a single successor.
987 If we had a conditional branch to the next instruction when
988 CFG was built, then there will only be one out edge for the
989 block which ended with the conditional branch (since we do
990 not create duplicate edges).
992 Furthermore, the edge will be marked as a fallthru because we
993 merge the flags for the duplicate edges. So we do not want to
994 check that the edge is not a FALLTHRU edge. */
996 if (single_succ_p (b))
998 s = single_succ_edge (b);
999 if (! (s->flags & EDGE_COMPLEX)
1000 && s->dest == c
1001 && !(JUMP_P (BB_END (b)) && CROSSING_JUMP_P (BB_END (b))))
1002 tidy_fallthru_edge (s);
1007 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1008 (and possibly create new basic block) to make edge non-fallthru.
1009 Return newly created BB or NULL if none. */
1011 basic_block
1012 force_nonfallthru (edge e)
1014 basic_block ret, src = e->src;
1016 if (!cfg_hooks->force_nonfallthru)
1017 internal_error ("%s does not support force_nonfallthru",
1018 cfg_hooks->name);
1020 ret = cfg_hooks->force_nonfallthru (e);
1021 if (ret != NULL)
1023 if (dom_info_available_p (CDI_DOMINATORS))
1024 set_immediate_dominator (CDI_DOMINATORS, ret, src);
1026 if (current_loops != NULL)
1028 struct loop *loop
1029 = find_common_loop (single_pred (ret)->loop_father,
1030 single_succ (ret)->loop_father);
1031 rescan_loop_exit (e, false, true);
1032 add_bb_to_loop (ret, loop);
1036 return ret;
1039 /* Returns true if we can duplicate basic block BB. */
1041 bool
1042 can_duplicate_block_p (const_basic_block bb)
1044 if (!cfg_hooks->can_duplicate_block_p)
1045 internal_error ("%s does not support can_duplicate_block_p",
1046 cfg_hooks->name);
1048 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1049 return false;
1051 return cfg_hooks->can_duplicate_block_p (bb);
1054 /* Duplicates basic block BB and redirects edge E to it. Returns the
1055 new basic block. The new basic block is placed after the basic block
1056 AFTER. */
1058 basic_block
1059 duplicate_block (basic_block bb, edge e, basic_block after)
1061 edge s, n;
1062 basic_block new_bb;
1063 gcov_type new_count = e ? e->count : 0;
1064 edge_iterator ei;
1066 if (!cfg_hooks->duplicate_block)
1067 internal_error ("%s does not support duplicate_block",
1068 cfg_hooks->name);
1070 if (bb->count < new_count)
1071 new_count = bb->count;
1073 gcc_checking_assert (can_duplicate_block_p (bb));
1075 new_bb = cfg_hooks->duplicate_block (bb);
1076 if (after)
1077 move_block_after (new_bb, after);
1079 new_bb->flags = bb->flags;
1080 FOR_EACH_EDGE (s, ei, bb->succs)
1082 /* Since we are creating edges from a new block to successors
1083 of another block (which therefore are known to be disjoint), there
1084 is no need to actually check for duplicated edges. */
1085 n = unchecked_make_edge (new_bb, s->dest, s->flags);
1086 n->probability = s->probability;
1087 if (e && bb->count)
1089 /* Take care for overflows! */
1090 n->count = s->count * (new_count * 10000 / bb->count) / 10000;
1091 s->count -= n->count;
1093 else
1094 n->count = s->count;
1095 n->aux = s->aux;
1098 if (e)
1100 new_bb->count = new_count;
1101 bb->count -= new_count;
1103 new_bb->frequency = EDGE_FREQUENCY (e);
1104 bb->frequency -= EDGE_FREQUENCY (e);
1106 redirect_edge_and_branch_force (e, new_bb);
1108 if (bb->count < 0)
1109 bb->count = 0;
1110 if (bb->frequency < 0)
1111 bb->frequency = 0;
1113 else
1115 new_bb->count = bb->count;
1116 new_bb->frequency = bb->frequency;
1119 set_bb_original (new_bb, bb);
1120 set_bb_copy (bb, new_bb);
1122 /* Add the new block to the copy of the loop of BB, or directly to the loop
1123 of BB if the loop is not being copied. */
1124 if (current_loops != NULL)
1126 struct loop *cloop = bb->loop_father;
1127 struct loop *copy = get_loop_copy (cloop);
1128 /* If we copied the loop header block but not the loop
1129 we have created a loop with multiple entries. Ditch the loop,
1130 add the new block to the outer loop and arrange for a fixup. */
1131 if (!copy
1132 && cloop->header == bb)
1134 add_bb_to_loop (new_bb, loop_outer (cloop));
1135 mark_loop_for_removal (cloop);
1137 else
1139 add_bb_to_loop (new_bb, copy ? copy : cloop);
1140 /* If we copied the loop latch block but not the loop, adjust
1141 loop state. */
1142 if (!copy
1143 && cloop->latch == bb)
1145 cloop->latch = NULL;
1146 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
1151 return new_bb;
1154 /* Return 1 if BB ends with a call, possibly followed by some
1155 instructions that must stay with the call, 0 otherwise. */
1157 bool
1158 block_ends_with_call_p (basic_block bb)
1160 if (!cfg_hooks->block_ends_with_call_p)
1161 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
1163 return (cfg_hooks->block_ends_with_call_p) (bb);
1166 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1168 bool
1169 block_ends_with_condjump_p (const_basic_block bb)
1171 if (!cfg_hooks->block_ends_with_condjump_p)
1172 internal_error ("%s does not support block_ends_with_condjump_p",
1173 cfg_hooks->name);
1175 return (cfg_hooks->block_ends_with_condjump_p) (bb);
1178 /* Add fake edges to the function exit for any non constant and non noreturn
1179 calls, volatile inline assembly in the bitmap of blocks specified by
1180 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1181 that were split.
1183 The goal is to expose cases in which entering a basic block does not imply
1184 that all subsequent instructions must be executed. */
1187 flow_call_edges_add (sbitmap blocks)
1189 if (!cfg_hooks->flow_call_edges_add)
1190 internal_error ("%s does not support flow_call_edges_add",
1191 cfg_hooks->name);
1193 return (cfg_hooks->flow_call_edges_add) (blocks);
1196 /* This function is called immediately after edge E is added to the
1197 edge vector E->dest->preds. */
1199 void
1200 execute_on_growing_pred (edge e)
1202 if (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. */
1209 void
1210 execute_on_shrinking_pred (edge e)
1212 if (cfg_hooks->execute_on_shrinking_pred)
1213 cfg_hooks->execute_on_shrinking_pred (e);
1216 /* This is used inside loop versioning when we want to insert
1217 stmts/insns on the edges, which have a different behavior
1218 in tree's and in RTL, so we made a CFG hook. */
1219 void
1220 lv_flush_pending_stmts (edge e)
1222 if (cfg_hooks->flush_pending_stmts)
1223 cfg_hooks->flush_pending_stmts (e);
1226 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1227 a new version of the loop basic-blocks, the parameters here are
1228 exactly the same as in duplicate_loop_to_header_edge or
1229 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1230 additional work to maintain ssa information that's why there is
1231 a need to call the tree_duplicate_loop_to_header_edge rather
1232 than duplicate_loop_to_header_edge when we are in tree mode. */
1233 bool
1234 cfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e,
1235 unsigned int ndupl,
1236 sbitmap wont_exit, edge orig,
1237 vec<edge> *to_remove,
1238 int flags)
1240 gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge);
1241 return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e,
1242 ndupl, wont_exit,
1243 orig, to_remove,
1244 flags);
1247 /* Conditional jumps are represented differently in trees and RTL,
1248 this hook takes a basic block that is known to have a cond jump
1249 at its end and extracts the taken and not taken edges out of it
1250 and store it in E1 and E2 respectively. */
1251 void
1252 extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1254 gcc_assert (cfg_hooks->extract_cond_bb_edges);
1255 cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1258 /* Responsible for updating the ssa info (PHI nodes) on the
1259 new condition basic block that guards the versioned loop. */
1260 void
1261 lv_adjust_loop_header_phi (basic_block first, basic_block second,
1262 basic_block new_block, edge e)
1264 if (cfg_hooks->lv_adjust_loop_header_phi)
1265 cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1268 /* Conditions in trees and RTL are different so we need
1269 a different handling when we add the condition to the
1270 versioning code. */
1271 void
1272 lv_add_condition_to_bb (basic_block first, basic_block second,
1273 basic_block new_block, void *cond)
1275 gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1276 cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1279 /* Checks whether all N blocks in BBS array can be copied. */
1280 bool
1281 can_copy_bbs_p (basic_block *bbs, unsigned n)
1283 unsigned i;
1284 edge e;
1285 int ret = true;
1287 for (i = 0; i < n; i++)
1288 bbs[i]->flags |= BB_DUPLICATED;
1290 for (i = 0; i < n; i++)
1292 /* In case we should redirect abnormal edge during duplication, fail. */
1293 edge_iterator ei;
1294 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1295 if ((e->flags & EDGE_ABNORMAL)
1296 && (e->dest->flags & BB_DUPLICATED))
1298 ret = false;
1299 goto end;
1302 if (!can_duplicate_block_p (bbs[i]))
1304 ret = false;
1305 break;
1309 end:
1310 for (i = 0; i < n; i++)
1311 bbs[i]->flags &= ~BB_DUPLICATED;
1313 return ret;
1316 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1317 are placed into array NEW_BBS in the same order. Edges from basic blocks
1318 in BBS are also duplicated and copies of those that lead into BBS are
1319 redirected to appropriate newly created block. The function assigns bbs
1320 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1321 loop, so this must be set up correctly in advance)
1323 If UPDATE_DOMINANCE is true then this function updates dominators locally
1324 (LOOPS structure that contains the information about dominators is passed
1325 to enable this), otherwise it does not update the dominator information
1326 and it assumed that the caller will do this, perhaps by destroying and
1327 recreating it instead of trying to do an incremental update like this
1328 function does when update_dominance is true.
1330 BASE is the superloop to that basic block belongs; if its header or latch
1331 is copied, we do not set the new blocks as header or latch.
1333 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1334 also in the same order.
1336 Newly created basic blocks are put after the basic block AFTER in the
1337 instruction stream, and the order of the blocks in BBS array is preserved. */
1339 void
1340 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1341 edge *edges, unsigned num_edges, edge *new_edges,
1342 struct loop *base, basic_block after, bool update_dominance)
1344 unsigned i, j;
1345 basic_block bb, new_bb, dom_bb;
1346 edge e;
1348 /* Duplicate bbs, update dominators, assign bbs to loops. */
1349 for (i = 0; i < n; i++)
1351 /* Duplicate. */
1352 bb = bbs[i];
1353 new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
1354 after = new_bb;
1355 bb->flags |= BB_DUPLICATED;
1356 if (bb->loop_father)
1358 /* Possibly set loop header. */
1359 if (bb->loop_father->header == bb && bb->loop_father != base)
1360 new_bb->loop_father->header = new_bb;
1361 /* Or latch. */
1362 if (bb->loop_father->latch == bb && bb->loop_father != base)
1363 new_bb->loop_father->latch = new_bb;
1367 /* Set dominators. */
1368 if (update_dominance)
1370 for (i = 0; i < n; i++)
1372 bb = bbs[i];
1373 new_bb = new_bbs[i];
1375 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1376 if (dom_bb->flags & BB_DUPLICATED)
1378 dom_bb = get_bb_copy (dom_bb);
1379 set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1384 /* Redirect edges. */
1385 for (j = 0; j < num_edges; j++)
1386 new_edges[j] = NULL;
1387 for (i = 0; i < n; i++)
1389 edge_iterator ei;
1390 new_bb = new_bbs[i];
1391 bb = bbs[i];
1393 FOR_EACH_EDGE (e, ei, new_bb->succs)
1395 for (j = 0; j < num_edges; j++)
1396 if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1397 new_edges[j] = e;
1399 if (!(e->dest->flags & BB_DUPLICATED))
1400 continue;
1401 redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1405 /* Clear information about duplicates. */
1406 for (i = 0; i < n; i++)
1407 bbs[i]->flags &= ~BB_DUPLICATED;
1410 /* Return true if BB contains only labels or non-executable
1411 instructions */
1412 bool
1413 empty_block_p (basic_block bb)
1415 gcc_assert (cfg_hooks->empty_block_p);
1416 return cfg_hooks->empty_block_p (bb);
1419 /* Split a basic block if it ends with a conditional branch and if
1420 the other part of the block is not empty. */
1421 basic_block
1422 split_block_before_cond_jump (basic_block bb)
1424 gcc_assert (cfg_hooks->split_block_before_cond_jump);
1425 return cfg_hooks->split_block_before_cond_jump (bb);
1428 /* Work-horse for passes.c:check_profile_consistency.
1429 Do book-keeping of the CFG for the profile consistency checker.
1430 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
1431 then do post-pass accounting. Store the counting in RECORD. */
1433 void
1434 account_profile_record (struct profile_record *record, int after_pass)
1436 basic_block bb;
1437 edge_iterator ei;
1438 edge e;
1439 int sum;
1440 gcov_type lsum;
1442 FOR_ALL_BB_FN (bb, cfun)
1444 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
1445 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
1447 sum = 0;
1448 FOR_EACH_EDGE (e, ei, bb->succs)
1449 sum += e->probability;
1450 if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
1451 record->num_mismatched_freq_out[after_pass]++;
1452 lsum = 0;
1453 FOR_EACH_EDGE (e, ei, bb->succs)
1454 lsum += e->count;
1455 if (EDGE_COUNT (bb->succs)
1456 && (lsum - bb->count > 100 || lsum - bb->count < -100))
1457 record->num_mismatched_count_out[after_pass]++;
1459 if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1460 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
1462 sum = 0;
1463 FOR_EACH_EDGE (e, ei, bb->preds)
1464 sum += EDGE_FREQUENCY (e);
1465 if (abs (sum - bb->frequency) > 100
1466 || (MAX (sum, bb->frequency) > 10
1467 && abs ((sum - bb->frequency) * 100 / (MAX (sum, bb->frequency) + 1)) > 10))
1468 record->num_mismatched_freq_in[after_pass]++;
1469 lsum = 0;
1470 FOR_EACH_EDGE (e, ei, bb->preds)
1471 lsum += e->count;
1472 if (lsum - bb->count > 100 || lsum - bb->count < -100)
1473 record->num_mismatched_count_in[after_pass]++;
1475 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
1476 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1477 continue;
1478 gcc_assert (cfg_hooks->account_profile_record);
1479 cfg_hooks->account_profile_record (bb, after_pass, record);