Daily bump.
[official-gcc.git] / gcc / cfghooks.c
blob8331fa0e9561374a24895ad1e1d8341bc8bc2bdd
1 /* Hooks for cfg representation specific functions.
2 Copyright (C) 2003-2013 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-flow.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);
102 edge_checksum = XCNEWVEC (size_t, last_basic_block);
104 /* Check bb chain & numbers. */
105 last_bb_seen = ENTRY_BLOCK_PTR;
106 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
108 if (bb != EXIT_BLOCK_PTR
109 && bb != BASIC_BLOCK (bb->index))
111 error ("bb %d on wrong place", bb->index);
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 (bb)
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->succs)
238 edge_checksum[e->dest->index] += (size_t) e;
240 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
241 edge_checksum[e->dest->index] -= (size_t) e;
244 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
245 if (edge_checksum[bb->index])
247 error ("basic block %i edge lists are corrupted", bb->index);
248 err = 1;
251 last_bb_seen = ENTRY_BLOCK_PTR;
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, n_edges);
327 FOR_ALL_BB (bb)
328 dump_bb (file, bb, 0, flags);
330 putc ('\n', file);
333 /* Like above, but dump to stderr. To be called from debuggers. */
334 void debug_flow_info (void);
335 DEBUG_FUNCTION void
336 debug_flow_info (void)
338 dump_flow_info (stderr, TDF_DETAILS);
341 /* Redirect edge E to the given basic block DEST and update underlying program
342 representation. Returns edge representing redirected branch (that may not
343 be equivalent to E in the case of duplicate edges being removed) or NULL
344 if edge is not easily redirectable for whatever reason. */
346 edge
347 redirect_edge_and_branch (edge e, basic_block dest)
349 edge ret;
351 if (!cfg_hooks->redirect_edge_and_branch)
352 internal_error ("%s does not support redirect_edge_and_branch",
353 cfg_hooks->name);
355 ret = cfg_hooks->redirect_edge_and_branch (e, dest);
357 /* If RET != E, then either the redirection failed, or the edge E
358 was removed since RET already lead to the same destination. */
359 if (current_loops != NULL && ret == e)
360 rescan_loop_exit (e, false, false);
362 return ret;
365 /* Returns true if it is possible to remove the edge E by redirecting it
366 to the destination of the other edge going from its source. */
368 bool
369 can_remove_branch_p (const_edge e)
371 if (!cfg_hooks->can_remove_branch_p)
372 internal_error ("%s does not support can_remove_branch_p",
373 cfg_hooks->name);
375 if (EDGE_COUNT (e->src->succs) != 2)
376 return false;
378 return cfg_hooks->can_remove_branch_p (e);
381 /* Removes E, by redirecting it to the destination of the other edge going
382 from its source. Can_remove_branch_p must be true for E, hence this
383 operation cannot fail. */
385 void
386 remove_branch (edge e)
388 edge other;
389 basic_block src = e->src;
390 int irr;
392 gcc_assert (EDGE_COUNT (e->src->succs) == 2);
394 other = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
395 irr = other->flags & EDGE_IRREDUCIBLE_LOOP;
397 e = redirect_edge_and_branch (e, other->dest);
398 gcc_assert (e != NULL);
400 e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
401 e->flags |= irr;
404 /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
406 void
407 remove_edge (edge e)
409 if (current_loops != NULL)
410 rescan_loop_exit (e, false, true);
412 /* This is probably not needed, but it doesn't hurt. */
413 /* FIXME: This should be called via a remove_edge hook. */
414 if (current_ir_type () == IR_GIMPLE)
415 redirect_edge_var_map_clear (e);
417 remove_edge_raw (e);
420 /* Like redirect_edge_succ but avoid possible duplicate edge. */
422 edge
423 redirect_edge_succ_nodup (edge e, basic_block new_succ)
425 edge s;
427 s = find_edge (e->src, new_succ);
428 if (s && s != e)
430 s->flags |= e->flags;
431 s->probability += e->probability;
432 if (s->probability > REG_BR_PROB_BASE)
433 s->probability = REG_BR_PROB_BASE;
434 s->count += e->count;
435 /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
436 redirect_edge_var_map_dup (s, e);
437 remove_edge (e);
438 e = s;
440 else
441 redirect_edge_succ (e, new_succ);
443 return e;
446 /* Redirect the edge E to basic block DEST even if it requires creating
447 of a new basic block; then it returns the newly created basic block.
448 Aborts when redirection is impossible. */
450 basic_block
451 redirect_edge_and_branch_force (edge e, basic_block dest)
453 basic_block ret, src = e->src;
455 if (!cfg_hooks->redirect_edge_and_branch_force)
456 internal_error ("%s does not support redirect_edge_and_branch_force",
457 cfg_hooks->name);
459 if (current_loops != NULL)
460 rescan_loop_exit (e, false, true);
462 ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
464 if (ret != NULL && dom_info_available_p (CDI_DOMINATORS))
465 set_immediate_dominator (CDI_DOMINATORS, ret, src);
467 if (current_loops != NULL)
469 if (ret != NULL)
471 struct loop *loop
472 = find_common_loop (single_pred (ret)->loop_father,
473 single_succ (ret)->loop_father);
474 add_bb_to_loop (ret, loop);
476 else if (find_edge (src, dest) == e)
477 rescan_loop_exit (e, true, false);
480 return ret;
483 /* Splits basic block BB after the specified instruction I (but at least after
484 the labels). If I is NULL, splits just after labels. The newly created edge
485 is returned. The new basic block is created just after the old one. */
487 edge
488 split_block (basic_block bb, void *i)
490 basic_block new_bb;
491 edge res;
493 if (!cfg_hooks->split_block)
494 internal_error ("%s does not support split_block", cfg_hooks->name);
496 new_bb = cfg_hooks->split_block (bb, i);
497 if (!new_bb)
498 return NULL;
500 new_bb->count = bb->count;
501 new_bb->frequency = bb->frequency;
502 new_bb->discriminator = bb->discriminator;
504 if (dom_info_available_p (CDI_DOMINATORS))
506 redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
507 set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
510 if (current_loops != NULL)
512 add_bb_to_loop (new_bb, bb->loop_father);
513 if (bb->loop_father->latch == bb)
514 bb->loop_father->latch = new_bb;
517 res = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
519 if (bb->flags & BB_IRREDUCIBLE_LOOP)
521 new_bb->flags |= BB_IRREDUCIBLE_LOOP;
522 res->flags |= EDGE_IRREDUCIBLE_LOOP;
525 return res;
528 /* Splits block BB just after labels. The newly created edge is returned. */
530 edge
531 split_block_after_labels (basic_block bb)
533 return split_block (bb, NULL);
536 /* Moves block BB immediately after block AFTER. Returns false if the
537 movement was impossible. */
539 bool
540 move_block_after (basic_block bb, basic_block after)
542 bool ret;
544 if (!cfg_hooks->move_block_after)
545 internal_error ("%s does not support move_block_after", cfg_hooks->name);
547 ret = cfg_hooks->move_block_after (bb, after);
549 return ret;
552 /* Deletes the basic block BB. */
554 void
555 delete_basic_block (basic_block bb)
557 if (!cfg_hooks->delete_basic_block)
558 internal_error ("%s does not support delete_basic_block", cfg_hooks->name);
560 cfg_hooks->delete_basic_block (bb);
562 if (current_loops != NULL)
564 struct loop *loop = bb->loop_father;
566 /* If we remove the header or the latch of a loop, mark the loop for
567 removal by setting its header and latch to NULL. */
568 if (loop->latch == bb
569 || loop->header == bb)
571 loop->header = NULL;
572 loop->latch = NULL;
573 loops_state_set (LOOPS_NEED_FIXUP);
576 remove_bb_from_loops (bb);
579 /* Remove the edges into and out of this block. Note that there may
580 indeed be edges in, if we are removing an unreachable loop. */
581 while (EDGE_COUNT (bb->preds) != 0)
582 remove_edge (EDGE_PRED (bb, 0));
583 while (EDGE_COUNT (bb->succs) != 0)
584 remove_edge (EDGE_SUCC (bb, 0));
586 if (dom_info_available_p (CDI_DOMINATORS))
587 delete_from_dominance_info (CDI_DOMINATORS, bb);
588 if (dom_info_available_p (CDI_POST_DOMINATORS))
589 delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
591 /* Remove the basic block from the array. */
592 expunge_block (bb);
595 /* Splits edge E and returns the newly created basic block. */
597 basic_block
598 split_edge (edge e)
600 basic_block ret;
601 gcov_type count = e->count;
602 int freq = EDGE_FREQUENCY (e);
603 edge f;
604 bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
605 struct loop *loop;
606 basic_block src = e->src, dest = e->dest;
608 if (!cfg_hooks->split_edge)
609 internal_error ("%s does not support split_edge", cfg_hooks->name);
611 if (current_loops != NULL)
612 rescan_loop_exit (e, false, true);
614 ret = cfg_hooks->split_edge (e);
615 ret->count = count;
616 ret->frequency = freq;
617 single_succ_edge (ret)->probability = REG_BR_PROB_BASE;
618 single_succ_edge (ret)->count = count;
620 if (irr)
622 ret->flags |= BB_IRREDUCIBLE_LOOP;
623 single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
624 single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
627 if (dom_info_available_p (CDI_DOMINATORS))
628 set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
630 if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
632 /* There are two cases:
634 If the immediate dominator of e->dest is not e->src, it
635 remains unchanged.
637 If immediate dominator of e->dest is e->src, it may become
638 ret, provided that all other predecessors of e->dest are
639 dominated by e->dest. */
641 if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
642 == single_pred (ret))
644 edge_iterator ei;
645 FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
647 if (f == single_succ_edge (ret))
648 continue;
650 if (!dominated_by_p (CDI_DOMINATORS, f->src,
651 single_succ (ret)))
652 break;
655 if (!f)
656 set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
660 if (current_loops != NULL)
662 loop = find_common_loop (src->loop_father, dest->loop_father);
663 add_bb_to_loop (ret, loop);
665 /* If we split the latch edge of loop adjust the latch block. */
666 if (loop->latch == src
667 && loop->header == dest)
668 loop->latch = ret;
671 return ret;
674 /* Creates a new basic block just after the basic block AFTER.
675 HEAD and END are the first and the last statement belonging
676 to the block. If both are NULL, an empty block is created. */
678 basic_block
679 create_basic_block (void *head, void *end, basic_block after)
681 basic_block ret;
683 if (!cfg_hooks->create_basic_block)
684 internal_error ("%s does not support create_basic_block", cfg_hooks->name);
686 ret = cfg_hooks->create_basic_block (head, end, after);
688 if (dom_info_available_p (CDI_DOMINATORS))
689 add_to_dominance_info (CDI_DOMINATORS, ret);
690 if (dom_info_available_p (CDI_POST_DOMINATORS))
691 add_to_dominance_info (CDI_POST_DOMINATORS, ret);
693 return ret;
696 /* Creates an empty basic block just after basic block AFTER. */
698 basic_block
699 create_empty_bb (basic_block after)
701 return create_basic_block (NULL, NULL, after);
704 /* Checks whether we may merge blocks BB1 and BB2. */
706 bool
707 can_merge_blocks_p (basic_block bb1, basic_block bb2)
709 bool ret;
711 if (!cfg_hooks->can_merge_blocks_p)
712 internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name);
714 ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
716 return ret;
719 void
720 predict_edge (edge e, enum br_predictor predictor, int probability)
722 if (!cfg_hooks->predict_edge)
723 internal_error ("%s does not support predict_edge", cfg_hooks->name);
725 cfg_hooks->predict_edge (e, predictor, probability);
728 bool
729 predicted_by_p (const_basic_block bb, enum br_predictor predictor)
731 if (!cfg_hooks->predict_edge)
732 internal_error ("%s does not support predicted_by_p", cfg_hooks->name);
734 return cfg_hooks->predicted_by_p (bb, predictor);
737 /* Merges basic block B into basic block A. */
739 void
740 merge_blocks (basic_block a, basic_block b)
742 edge e;
743 edge_iterator ei;
745 if (!cfg_hooks->merge_blocks)
746 internal_error ("%s does not support merge_blocks", cfg_hooks->name);
748 cfg_hooks->merge_blocks (a, b);
750 if (current_loops != NULL)
752 /* If the block we merge into is a loop header do nothing unless ... */
753 if (a->loop_father->header == a)
755 /* ... we merge two loop headers, in which case we kill
756 the inner loop. */
757 if (b->loop_father->header == b)
759 b->loop_father->header = NULL;
760 b->loop_father->latch = NULL;
761 loops_state_set (LOOPS_NEED_FIXUP);
764 /* If we merge a loop header into its predecessor, update the loop
765 structure. */
766 else if (b->loop_father->header == b)
768 remove_bb_from_loops (a);
769 add_bb_to_loop (a, b->loop_father);
770 a->loop_father->header = a;
772 remove_bb_from_loops (b);
775 /* Normally there should only be one successor of A and that is B, but
776 partway though the merge of blocks for conditional_execution we'll
777 be merging a TEST block with THEN and ELSE successors. Free the
778 whole lot of them and hope the caller knows what they're doing. */
780 while (EDGE_COUNT (a->succs) != 0)
781 remove_edge (EDGE_SUCC (a, 0));
783 /* Adjust the edges out of B for the new owner. */
784 FOR_EACH_EDGE (e, ei, b->succs)
786 e->src = a;
787 if (current_loops != NULL)
789 /* If b was a latch, a now is. */
790 if (e->dest->loop_father->latch == b)
791 e->dest->loop_father->latch = a;
792 rescan_loop_exit (e, true, false);
795 a->succs = b->succs;
796 a->flags |= b->flags;
798 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
799 b->preds = b->succs = NULL;
801 if (dom_info_available_p (CDI_DOMINATORS))
802 redirect_immediate_dominators (CDI_DOMINATORS, b, a);
804 if (dom_info_available_p (CDI_DOMINATORS))
805 delete_from_dominance_info (CDI_DOMINATORS, b);
806 if (dom_info_available_p (CDI_POST_DOMINATORS))
807 delete_from_dominance_info (CDI_POST_DOMINATORS, b);
809 expunge_block (b);
812 /* Split BB into entry part and the rest (the rest is the newly created block).
813 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
814 part. Returns the edge connecting the entry part to the rest. */
816 edge
817 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
818 void (*new_bb_cbk) (basic_block))
820 edge e, fallthru;
821 edge_iterator ei;
822 basic_block dummy, jump;
823 struct loop *loop, *ploop, *cloop;
825 if (!cfg_hooks->make_forwarder_block)
826 internal_error ("%s does not support make_forwarder_block",
827 cfg_hooks->name);
829 fallthru = split_block_after_labels (bb);
830 dummy = fallthru->src;
831 bb = fallthru->dest;
833 /* Redirect back edges we want to keep. */
834 for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
836 basic_block e_src;
838 if (redirect_edge_p (e))
840 ei_next (&ei);
841 continue;
844 dummy->frequency -= EDGE_FREQUENCY (e);
845 dummy->count -= e->count;
846 if (dummy->frequency < 0)
847 dummy->frequency = 0;
848 if (dummy->count < 0)
849 dummy->count = 0;
850 fallthru->count -= e->count;
851 if (fallthru->count < 0)
852 fallthru->count = 0;
854 e_src = e->src;
855 jump = redirect_edge_and_branch_force (e, bb);
856 if (jump != NULL)
858 /* If we redirected the loop latch edge, the JUMP block now acts like
859 the new latch of the loop. */
860 if (current_loops != NULL
861 && dummy->loop_father != NULL
862 && dummy->loop_father->header == dummy
863 && dummy->loop_father->latch == e_src)
864 dummy->loop_father->latch = jump;
866 if (new_bb_cbk != NULL)
867 new_bb_cbk (jump);
871 if (dom_info_available_p (CDI_DOMINATORS))
873 vec<basic_block> doms_to_fix;
874 doms_to_fix.create (2);
875 doms_to_fix.quick_push (dummy);
876 doms_to_fix.quick_push (bb);
877 iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
878 doms_to_fix.release ();
881 if (current_loops != NULL)
883 /* If we do not split a loop header, then both blocks belong to the
884 same loop. In case we split loop header and do not redirect the
885 latch edge to DUMMY, then DUMMY belongs to the outer loop, and
886 BB becomes the new header. If latch is not recorded for the loop,
887 we leave this updating on the caller (this may only happen during
888 loop analysis). */
889 loop = dummy->loop_father;
890 if (loop->header == dummy
891 && loop->latch != NULL
892 && find_edge (loop->latch, dummy) == NULL)
894 remove_bb_from_loops (dummy);
895 loop->header = bb;
897 cloop = loop;
898 FOR_EACH_EDGE (e, ei, dummy->preds)
900 cloop = find_common_loop (cloop, e->src->loop_father);
902 add_bb_to_loop (dummy, cloop);
905 /* In case we split loop latch, update it. */
906 for (ploop = loop; ploop; ploop = loop_outer (ploop))
907 if (ploop->latch == dummy)
908 ploop->latch = bb;
911 cfg_hooks->make_forwarder_block (fallthru);
913 return fallthru;
916 /* Try to make the edge fallthru. */
918 void
919 tidy_fallthru_edge (edge e)
921 if (cfg_hooks->tidy_fallthru_edge)
922 cfg_hooks->tidy_fallthru_edge (e);
925 /* Fix up edges that now fall through, or rather should now fall through
926 but previously required a jump around now deleted blocks. Simplify
927 the search by only examining blocks numerically adjacent, since this
928 is how they were created.
930 ??? This routine is currently RTL specific. */
932 void
933 tidy_fallthru_edges (void)
935 basic_block b, c;
937 if (!cfg_hooks->tidy_fallthru_edge)
938 return;
940 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
941 return;
943 FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
945 edge s;
947 c = b->next_bb;
949 /* We care about simple conditional or unconditional jumps with
950 a single successor.
952 If we had a conditional branch to the next instruction when
953 CFG was built, then there will only be one out edge for the
954 block which ended with the conditional branch (since we do
955 not create duplicate edges).
957 Furthermore, the edge will be marked as a fallthru because we
958 merge the flags for the duplicate edges. So we do not want to
959 check that the edge is not a FALLTHRU edge. */
961 if (single_succ_p (b))
963 s = single_succ_edge (b);
964 if (! (s->flags & EDGE_COMPLEX)
965 && s->dest == c
966 && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
967 tidy_fallthru_edge (s);
972 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
973 (and possibly create new basic block) to make edge non-fallthru.
974 Return newly created BB or NULL if none. */
976 basic_block
977 force_nonfallthru (edge e)
979 basic_block ret, src = e->src;
981 if (!cfg_hooks->force_nonfallthru)
982 internal_error ("%s does not support force_nonfallthru",
983 cfg_hooks->name);
985 ret = cfg_hooks->force_nonfallthru (e);
986 if (ret != NULL)
988 if (dom_info_available_p (CDI_DOMINATORS))
989 set_immediate_dominator (CDI_DOMINATORS, ret, src);
991 if (current_loops != NULL)
993 struct loop *loop
994 = find_common_loop (single_pred (ret)->loop_father,
995 single_succ (ret)->loop_father);
996 rescan_loop_exit (e, false, true);
997 add_bb_to_loop (ret, loop);
1001 return ret;
1004 /* Returns true if we can duplicate basic block BB. */
1006 bool
1007 can_duplicate_block_p (const_basic_block bb)
1009 if (!cfg_hooks->can_duplicate_block_p)
1010 internal_error ("%s does not support can_duplicate_block_p",
1011 cfg_hooks->name);
1013 if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
1014 return false;
1016 return cfg_hooks->can_duplicate_block_p (bb);
1019 /* Duplicates basic block BB and redirects edge E to it. Returns the
1020 new basic block. The new basic block is placed after the basic block
1021 AFTER. */
1023 basic_block
1024 duplicate_block (basic_block bb, edge e, basic_block after)
1026 edge s, n;
1027 basic_block new_bb;
1028 gcov_type new_count = e ? e->count : 0;
1029 edge_iterator ei;
1031 if (!cfg_hooks->duplicate_block)
1032 internal_error ("%s does not support duplicate_block",
1033 cfg_hooks->name);
1035 if (bb->count < new_count)
1036 new_count = bb->count;
1038 gcc_checking_assert (can_duplicate_block_p (bb));
1040 new_bb = cfg_hooks->duplicate_block (bb);
1041 if (after)
1042 move_block_after (new_bb, after);
1044 new_bb->flags = bb->flags;
1045 FOR_EACH_EDGE (s, ei, bb->succs)
1047 /* Since we are creating edges from a new block to successors
1048 of another block (which therefore are known to be disjoint), there
1049 is no need to actually check for duplicated edges. */
1050 n = unchecked_make_edge (new_bb, s->dest, s->flags);
1051 n->probability = s->probability;
1052 if (e && bb->count)
1054 /* Take care for overflows! */
1055 n->count = s->count * (new_count * 10000 / bb->count) / 10000;
1056 s->count -= n->count;
1058 else
1059 n->count = s->count;
1060 n->aux = s->aux;
1063 if (e)
1065 new_bb->count = new_count;
1066 bb->count -= new_count;
1068 new_bb->frequency = EDGE_FREQUENCY (e);
1069 bb->frequency -= EDGE_FREQUENCY (e);
1071 redirect_edge_and_branch_force (e, new_bb);
1073 if (bb->count < 0)
1074 bb->count = 0;
1075 if (bb->frequency < 0)
1076 bb->frequency = 0;
1078 else
1080 new_bb->count = bb->count;
1081 new_bb->frequency = bb->frequency;
1084 set_bb_original (new_bb, bb);
1085 set_bb_copy (bb, new_bb);
1087 /* Add the new block to the copy of the loop of BB, or directly to the loop
1088 of BB if the loop is not being copied. */
1089 if (current_loops != NULL)
1091 struct loop *cloop = bb->loop_father;
1092 struct loop *copy = get_loop_copy (cloop);
1093 /* If we copied the loop header block but not the loop
1094 we have created a loop with multiple entries. Ditch the loop,
1095 add the new block to the outer loop and arrange for a fixup. */
1096 if (!copy
1097 && cloop->header == bb)
1099 add_bb_to_loop (new_bb, loop_outer (cloop));
1100 cloop->header = NULL;
1101 cloop->latch = NULL;
1102 loops_state_set (LOOPS_NEED_FIXUP);
1104 else
1106 add_bb_to_loop (new_bb, copy ? copy : cloop);
1107 /* If we copied the loop latch block but not the loop, adjust
1108 loop state. */
1109 if (!copy
1110 && cloop->latch == bb)
1112 cloop->latch = NULL;
1113 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
1118 return new_bb;
1121 /* Return 1 if BB ends with a call, possibly followed by some
1122 instructions that must stay with the call, 0 otherwise. */
1124 bool
1125 block_ends_with_call_p (basic_block bb)
1127 if (!cfg_hooks->block_ends_with_call_p)
1128 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
1130 return (cfg_hooks->block_ends_with_call_p) (bb);
1133 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1135 bool
1136 block_ends_with_condjump_p (const_basic_block bb)
1138 if (!cfg_hooks->block_ends_with_condjump_p)
1139 internal_error ("%s does not support block_ends_with_condjump_p",
1140 cfg_hooks->name);
1142 return (cfg_hooks->block_ends_with_condjump_p) (bb);
1145 /* Add fake edges to the function exit for any non constant and non noreturn
1146 calls, volatile inline assembly in the bitmap of blocks specified by
1147 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1148 that were split.
1150 The goal is to expose cases in which entering a basic block does not imply
1151 that all subsequent instructions must be executed. */
1154 flow_call_edges_add (sbitmap blocks)
1156 if (!cfg_hooks->flow_call_edges_add)
1157 internal_error ("%s does not support flow_call_edges_add",
1158 cfg_hooks->name);
1160 return (cfg_hooks->flow_call_edges_add) (blocks);
1163 /* This function is called immediately after edge E is added to the
1164 edge vector E->dest->preds. */
1166 void
1167 execute_on_growing_pred (edge e)
1169 if (cfg_hooks->execute_on_growing_pred)
1170 cfg_hooks->execute_on_growing_pred (e);
1173 /* This function is called immediately before edge E is removed from
1174 the edge vector E->dest->preds. */
1176 void
1177 execute_on_shrinking_pred (edge e)
1179 if (cfg_hooks->execute_on_shrinking_pred)
1180 cfg_hooks->execute_on_shrinking_pred (e);
1183 /* This is used inside loop versioning when we want to insert
1184 stmts/insns on the edges, which have a different behavior
1185 in tree's and in RTL, so we made a CFG hook. */
1186 void
1187 lv_flush_pending_stmts (edge e)
1189 if (cfg_hooks->flush_pending_stmts)
1190 cfg_hooks->flush_pending_stmts (e);
1193 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1194 a new version of the loop basic-blocks, the parameters here are
1195 exactly the same as in duplicate_loop_to_header_edge or
1196 tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1197 additional work to maintain ssa information that's why there is
1198 a need to call the tree_duplicate_loop_to_header_edge rather
1199 than duplicate_loop_to_header_edge when we are in tree mode. */
1200 bool
1201 cfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e,
1202 unsigned int ndupl,
1203 sbitmap wont_exit, edge orig,
1204 vec<edge> *to_remove,
1205 int flags)
1207 gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge);
1208 return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e,
1209 ndupl, wont_exit,
1210 orig, to_remove,
1211 flags);
1214 /* Conditional jumps are represented differently in trees and RTL,
1215 this hook takes a basic block that is known to have a cond jump
1216 at its end and extracts the taken and not taken edges out of it
1217 and store it in E1 and E2 respectively. */
1218 void
1219 extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1221 gcc_assert (cfg_hooks->extract_cond_bb_edges);
1222 cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1225 /* Responsible for updating the ssa info (PHI nodes) on the
1226 new condition basic block that guards the versioned loop. */
1227 void
1228 lv_adjust_loop_header_phi (basic_block first, basic_block second,
1229 basic_block new_block, edge e)
1231 if (cfg_hooks->lv_adjust_loop_header_phi)
1232 cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1235 /* Conditions in trees and RTL are different so we need
1236 a different handling when we add the condition to the
1237 versioning code. */
1238 void
1239 lv_add_condition_to_bb (basic_block first, basic_block second,
1240 basic_block new_block, void *cond)
1242 gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1243 cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1246 /* Checks whether all N blocks in BBS array can be copied. */
1247 bool
1248 can_copy_bbs_p (basic_block *bbs, unsigned n)
1250 unsigned i;
1251 edge e;
1252 int ret = true;
1254 for (i = 0; i < n; i++)
1255 bbs[i]->flags |= BB_DUPLICATED;
1257 for (i = 0; i < n; i++)
1259 /* In case we should redirect abnormal edge during duplication, fail. */
1260 edge_iterator ei;
1261 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1262 if ((e->flags & EDGE_ABNORMAL)
1263 && (e->dest->flags & BB_DUPLICATED))
1265 ret = false;
1266 goto end;
1269 if (!can_duplicate_block_p (bbs[i]))
1271 ret = false;
1272 break;
1276 end:
1277 for (i = 0; i < n; i++)
1278 bbs[i]->flags &= ~BB_DUPLICATED;
1280 return ret;
1283 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1284 are placed into array NEW_BBS in the same order. Edges from basic blocks
1285 in BBS are also duplicated and copies of those that lead into BBS are
1286 redirected to appropriate newly created block. The function assigns bbs
1287 into loops (copy of basic block bb is assigned to bb->loop_father->copy
1288 loop, so this must be set up correctly in advance)
1290 If UPDATE_DOMINANCE is true then this function updates dominators locally
1291 (LOOPS structure that contains the information about dominators is passed
1292 to enable this), otherwise it does not update the dominator information
1293 and it assumed that the caller will do this, perhaps by destroying and
1294 recreating it instead of trying to do an incremental update like this
1295 function does when update_dominance is true.
1297 BASE is the superloop to that basic block belongs; if its header or latch
1298 is copied, we do not set the new blocks as header or latch.
1300 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1301 also in the same order.
1303 Newly created basic blocks are put after the basic block AFTER in the
1304 instruction stream, and the order of the blocks in BBS array is preserved. */
1306 void
1307 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1308 edge *edges, unsigned num_edges, edge *new_edges,
1309 struct loop *base, basic_block after, bool update_dominance)
1311 unsigned i, j;
1312 basic_block bb, new_bb, dom_bb;
1313 edge e;
1315 /* Duplicate bbs, update dominators, assign bbs to loops. */
1316 for (i = 0; i < n; i++)
1318 /* Duplicate. */
1319 bb = bbs[i];
1320 new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
1321 after = new_bb;
1322 bb->flags |= BB_DUPLICATED;
1323 if (bb->loop_father)
1325 /* Possibly set loop header. */
1326 if (bb->loop_father->header == bb && bb->loop_father != base)
1327 new_bb->loop_father->header = new_bb;
1328 /* Or latch. */
1329 if (bb->loop_father->latch == bb && bb->loop_father != base)
1330 new_bb->loop_father->latch = new_bb;
1334 /* Set dominators. */
1335 if (update_dominance)
1337 for (i = 0; i < n; i++)
1339 bb = bbs[i];
1340 new_bb = new_bbs[i];
1342 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1343 if (dom_bb->flags & BB_DUPLICATED)
1345 dom_bb = get_bb_copy (dom_bb);
1346 set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1351 /* Redirect edges. */
1352 for (j = 0; j < num_edges; j++)
1353 new_edges[j] = NULL;
1354 for (i = 0; i < n; i++)
1356 edge_iterator ei;
1357 new_bb = new_bbs[i];
1358 bb = bbs[i];
1360 FOR_EACH_EDGE (e, ei, new_bb->succs)
1362 for (j = 0; j < num_edges; j++)
1363 if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1364 new_edges[j] = e;
1366 if (!(e->dest->flags & BB_DUPLICATED))
1367 continue;
1368 redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1372 /* Clear information about duplicates. */
1373 for (i = 0; i < n; i++)
1374 bbs[i]->flags &= ~BB_DUPLICATED;
1377 /* Return true if BB contains only labels or non-executable
1378 instructions */
1379 bool
1380 empty_block_p (basic_block bb)
1382 gcc_assert (cfg_hooks->empty_block_p);
1383 return cfg_hooks->empty_block_p (bb);
1386 /* Split a basic block if it ends with a conditional branch and if
1387 the other part of the block is not empty. */
1388 basic_block
1389 split_block_before_cond_jump (basic_block bb)
1391 gcc_assert (cfg_hooks->split_block_before_cond_jump);
1392 return cfg_hooks->split_block_before_cond_jump (bb);
1395 /* Work-horse for passes.c:check_profile_consistency.
1396 Do book-keeping of the CFG for the profile consistency checker.
1397 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
1398 then do post-pass accounting. Store the counting in RECORD. */
1400 void
1401 account_profile_record (struct profile_record *record, int after_pass)
1403 basic_block bb;
1404 edge_iterator ei;
1405 edge e;
1406 int sum;
1407 gcov_type lsum;
1409 FOR_ALL_BB (bb)
1411 if (bb != EXIT_BLOCK_PTR_FOR_FUNCTION (cfun)
1412 && profile_status != PROFILE_ABSENT)
1414 sum = 0;
1415 FOR_EACH_EDGE (e, ei, bb->succs)
1416 sum += e->probability;
1417 if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
1418 record->num_mismatched_freq_out[after_pass]++;
1419 lsum = 0;
1420 FOR_EACH_EDGE (e, ei, bb->succs)
1421 lsum += e->count;
1422 if (EDGE_COUNT (bb->succs)
1423 && (lsum - bb->count > 100 || lsum - bb->count < -100))
1424 record->num_mismatched_count_out[after_pass]++;
1426 if (bb != ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun)
1427 && profile_status != PROFILE_ABSENT)
1429 sum = 0;
1430 FOR_EACH_EDGE (e, ei, bb->preds)
1431 sum += EDGE_FREQUENCY (e);
1432 if (abs (sum - bb->frequency) > 100
1433 || (MAX (sum, bb->frequency) > 10
1434 && abs ((sum - bb->frequency) * 100 / (MAX (sum, bb->frequency) + 1)) > 10))
1435 record->num_mismatched_freq_in[after_pass]++;
1436 lsum = 0;
1437 FOR_EACH_EDGE (e, ei, bb->preds)
1438 lsum += e->count;
1439 if (lsum - bb->count > 100 || lsum - bb->count < -100)
1440 record->num_mismatched_count_in[after_pass]++;
1442 if (bb == ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun)
1443 || bb == EXIT_BLOCK_PTR_FOR_FUNCTION (cfun))
1444 continue;
1445 gcc_assert (cfg_hooks->account_profile_record);
1446 cfg_hooks->account_profile_record(bb, after_pass, record);