gcc/ChangeLog:
[official-gcc.git] / gcc / cfg.c
blob7a0e5bb16cb5f5e09315ad4636fdc1b5af0c6df7
1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file contains low level functions to manipulate the CFG and
21 analyze it. All other modules should not transform the data structure
22 directly and use abstraction instead. The file is supposed to be
23 ordered bottom-up and should not contain any code dependent on a
24 particular intermediate language (RTL or trees).
26 Available functionality:
27 - Initialization/deallocation
28 init_flow, clear_edges
29 - Low level basic block manipulation
30 alloc_block, expunge_block
31 - Edge manipulation
32 make_edge, make_single_succ_edge, cached_make_edge, remove_edge
33 - Low level edge redirection (without updating instruction chain)
34 redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
35 - Dumping and debugging
36 dump_flow_info, debug_flow_info, dump_edge_info
37 - Allocation of AUX fields for basic blocks
38 alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
39 - clear_bb_flags
40 - Consistency checking
41 verify_flow_info
42 - Dumping and debugging
43 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
45 TODO: Document these "Available functionality" functions in the files
46 that implement them.
49 #include "config.h"
50 #include "system.h"
51 #include "coretypes.h"
52 #include "backend.h"
53 #include "hard-reg-set.h"
54 #include "tree.h"
55 #include "cfghooks.h"
56 #include "df.h"
57 #include "cfganal.h"
58 #include "cfgloop.h" /* FIXME: For struct loop. */
59 #include "dumpfile.h"
62 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
64 /* Called once at initialization time. */
66 void
67 init_flow (struct function *the_fun)
69 if (!the_fun->cfg)
70 the_fun->cfg = ggc_cleared_alloc<control_flow_graph> ();
71 n_edges_for_fn (the_fun) = 0;
72 ENTRY_BLOCK_PTR_FOR_FN (the_fun)
73 = ggc_cleared_alloc<basic_block_def> ();
74 ENTRY_BLOCK_PTR_FOR_FN (the_fun)->index = ENTRY_BLOCK;
75 EXIT_BLOCK_PTR_FOR_FN (the_fun)
76 = ggc_cleared_alloc<basic_block_def> ();
77 EXIT_BLOCK_PTR_FOR_FN (the_fun)->index = EXIT_BLOCK;
78 ENTRY_BLOCK_PTR_FOR_FN (the_fun)->next_bb
79 = EXIT_BLOCK_PTR_FOR_FN (the_fun);
80 EXIT_BLOCK_PTR_FOR_FN (the_fun)->prev_bb
81 = ENTRY_BLOCK_PTR_FOR_FN (the_fun);
84 /* Helper function for remove_edge and clear_edges. Frees edge structure
85 without actually removing it from the pred/succ arrays. */
87 static void
88 free_edge (function *fn, edge e)
90 n_edges_for_fn (fn)--;
91 ggc_free (e);
94 /* Free the memory associated with the edge structures. */
96 void
97 clear_edges (struct function *fn)
99 basic_block bb;
100 edge e;
101 edge_iterator ei;
103 FOR_EACH_BB_FN (bb, fn)
105 FOR_EACH_EDGE (e, ei, bb->succs)
106 free_edge (fn, e);
107 vec_safe_truncate (bb->succs, 0);
108 vec_safe_truncate (bb->preds, 0);
111 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (fn)->succs)
112 free_edge (fn, e);
113 vec_safe_truncate (EXIT_BLOCK_PTR_FOR_FN (fn)->preds, 0);
114 vec_safe_truncate (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs, 0);
116 gcc_assert (!n_edges_for_fn (fn));
119 /* Allocate memory for basic_block. */
121 basic_block
122 alloc_block (void)
124 basic_block bb;
125 bb = ggc_cleared_alloc<basic_block_def> ();
126 return bb;
129 /* Link block B to chain after AFTER. */
130 void
131 link_block (basic_block b, basic_block after)
133 b->next_bb = after->next_bb;
134 b->prev_bb = after;
135 after->next_bb = b;
136 b->next_bb->prev_bb = b;
139 /* Unlink block B from chain. */
140 void
141 unlink_block (basic_block b)
143 b->next_bb->prev_bb = b->prev_bb;
144 b->prev_bb->next_bb = b->next_bb;
145 b->prev_bb = NULL;
146 b->next_bb = NULL;
149 /* Sequentially order blocks and compact the arrays. */
150 void
151 compact_blocks (void)
153 int i;
155 SET_BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK, ENTRY_BLOCK_PTR_FOR_FN (cfun));
156 SET_BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK, EXIT_BLOCK_PTR_FOR_FN (cfun));
158 if (df)
159 df_compact_blocks ();
160 else
162 basic_block bb;
164 i = NUM_FIXED_BLOCKS;
165 FOR_EACH_BB_FN (bb, cfun)
167 SET_BASIC_BLOCK_FOR_FN (cfun, i, bb);
168 bb->index = i;
169 i++;
171 gcc_assert (i == n_basic_blocks_for_fn (cfun));
173 for (; i < last_basic_block_for_fn (cfun); i++)
174 SET_BASIC_BLOCK_FOR_FN (cfun, i, NULL);
176 last_basic_block_for_fn (cfun) = n_basic_blocks_for_fn (cfun);
179 /* Remove block B from the basic block array. */
181 void
182 expunge_block (basic_block b)
184 unlink_block (b);
185 SET_BASIC_BLOCK_FOR_FN (cfun, b->index, NULL);
186 n_basic_blocks_for_fn (cfun)--;
187 /* We should be able to ggc_free here, but we are not.
188 The dead SSA_NAMES are left pointing to dead statements that are pointing
189 to dead basic blocks making garbage collector to die.
190 We should be able to release all dead SSA_NAMES and at the same time we should
191 clear out BB pointer of dead statements consistently. */
194 /* Connect E to E->src. */
196 static inline void
197 connect_src (edge e)
199 vec_safe_push (e->src->succs, e);
200 df_mark_solutions_dirty ();
203 /* Connect E to E->dest. */
205 static inline void
206 connect_dest (edge e)
208 basic_block dest = e->dest;
209 vec_safe_push (dest->preds, e);
210 e->dest_idx = EDGE_COUNT (dest->preds) - 1;
211 df_mark_solutions_dirty ();
214 /* Disconnect edge E from E->src. */
216 static inline void
217 disconnect_src (edge e)
219 basic_block src = e->src;
220 edge_iterator ei;
221 edge tmp;
223 for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
225 if (tmp == e)
227 src->succs->unordered_remove (ei.index);
228 df_mark_solutions_dirty ();
229 return;
231 else
232 ei_next (&ei);
235 gcc_unreachable ();
238 /* Disconnect edge E from E->dest. */
240 static inline void
241 disconnect_dest (edge e)
243 basic_block dest = e->dest;
244 unsigned int dest_idx = e->dest_idx;
246 dest->preds->unordered_remove (dest_idx);
248 /* If we removed an edge in the middle of the edge vector, we need
249 to update dest_idx of the edge that moved into the "hole". */
250 if (dest_idx < EDGE_COUNT (dest->preds))
251 EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
252 df_mark_solutions_dirty ();
255 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
256 created edge. Use this only if you are sure that this edge can't
257 possibly already exist. */
259 edge
260 unchecked_make_edge (basic_block src, basic_block dst, int flags)
262 edge e;
263 e = ggc_cleared_alloc<edge_def> ();
264 n_edges_for_fn (cfun)++;
266 e->src = src;
267 e->dest = dst;
268 e->flags = flags;
270 connect_src (e);
271 connect_dest (e);
273 execute_on_growing_pred (e);
274 return e;
277 /* Create an edge connecting SRC and DST with FLAGS optionally using
278 edge cache CACHE. Return the new edge, NULL if already exist. */
280 edge
281 cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
283 if (edge_cache == NULL
284 || src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
285 || dst == EXIT_BLOCK_PTR_FOR_FN (cfun))
286 return make_edge (src, dst, flags);
288 /* Does the requested edge already exist? */
289 if (! bitmap_bit_p (edge_cache, dst->index))
291 /* The edge does not exist. Create one and update the
292 cache. */
293 bitmap_set_bit (edge_cache, dst->index);
294 return unchecked_make_edge (src, dst, flags);
297 /* At this point, we know that the requested edge exists. Adjust
298 flags if necessary. */
299 if (flags)
301 edge e = find_edge (src, dst);
302 e->flags |= flags;
305 return NULL;
308 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
309 created edge or NULL if already exist. */
311 edge
312 make_edge (basic_block src, basic_block dest, int flags)
314 edge e = find_edge (src, dest);
316 /* Make sure we don't add duplicate edges. */
317 if (e)
319 e->flags |= flags;
320 return NULL;
323 return unchecked_make_edge (src, dest, flags);
326 /* Create an edge connecting SRC to DEST and set probability by knowing
327 that it is the single edge leaving SRC. */
329 edge
330 make_single_succ_edge (basic_block src, basic_block dest, int flags)
332 edge e = make_edge (src, dest, flags);
334 e->probability = REG_BR_PROB_BASE;
335 e->count = src->count;
336 return e;
339 /* This function will remove an edge from the flow graph. */
341 void
342 remove_edge_raw (edge e)
344 remove_predictions_associated_with_edge (e);
345 execute_on_shrinking_pred (e);
347 disconnect_src (e);
348 disconnect_dest (e);
350 free_edge (cfun, e);
353 /* Redirect an edge's successor from one block to another. */
355 void
356 redirect_edge_succ (edge e, basic_block new_succ)
358 execute_on_shrinking_pred (e);
360 disconnect_dest (e);
362 e->dest = new_succ;
364 /* Reconnect the edge to the new successor block. */
365 connect_dest (e);
367 execute_on_growing_pred (e);
370 /* Redirect an edge's predecessor from one block to another. */
372 void
373 redirect_edge_pred (edge e, basic_block new_pred)
375 disconnect_src (e);
377 e->src = new_pred;
379 /* Reconnect the edge to the new predecessor block. */
380 connect_src (e);
383 /* Clear all basic block flags that do not have to be preserved. */
384 void
385 clear_bb_flags (void)
387 basic_block bb;
389 FOR_ALL_BB_FN (bb, cfun)
390 bb->flags &= BB_FLAGS_TO_PRESERVE;
393 /* Check the consistency of profile information. We can't do that
394 in verify_flow_info, as the counts may get invalid for incompletely
395 solved graphs, later eliminating of conditionals or roundoff errors.
396 It is still practical to have them reported for debugging of simple
397 testcases. */
398 static void
399 check_bb_profile (basic_block bb, FILE * file, int indent, int flags)
401 edge e;
402 int sum = 0;
403 gcov_type lsum;
404 edge_iterator ei;
405 struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
406 char *s_indent = (char *) alloca ((size_t) indent + 1);
407 memset ((void *) s_indent, ' ', (size_t) indent);
408 s_indent[indent] = '\0';
410 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
411 return;
413 if (bb != EXIT_BLOCK_PTR_FOR_FN (fun))
415 bool found = false;
416 FOR_EACH_EDGE (e, ei, bb->succs)
418 if (!(e->flags & EDGE_EH))
419 found = true;
420 sum += e->probability;
422 /* Only report mismatches for non-EH control flow. If there are only EH
423 edges it means that the BB ends by noreturn call. Here the control
424 flow may just terminate. */
425 if (found)
427 if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
428 fprintf (file, "%s%sInvalid sum of outgoing probabilities %.1f%%\n",
429 (flags & TDF_COMMENT) ? ";; " : "", s_indent,
430 sum * 100.0 / REG_BR_PROB_BASE);
431 lsum = 0;
432 FOR_EACH_EDGE (e, ei, bb->succs)
433 lsum += e->count;
434 if (EDGE_COUNT (bb->succs)
435 && (lsum - bb->count > 100 || lsum - bb->count < -100))
436 fprintf (file, "%s%sInvalid sum of outgoing counts %i, should be %i\n",
437 (flags & TDF_COMMENT) ? ";; " : "", s_indent,
438 (int) lsum, (int) bb->count);
441 if (bb != ENTRY_BLOCK_PTR_FOR_FN (fun))
443 sum = 0;
444 FOR_EACH_EDGE (e, ei, bb->preds)
445 sum += EDGE_FREQUENCY (e);
446 if (abs (sum - bb->frequency) > 100)
447 fprintf (file,
448 "%s%sInvalid sum of incoming frequencies %i, should be %i\n",
449 (flags & TDF_COMMENT) ? ";; " : "", s_indent,
450 sum, bb->frequency);
451 lsum = 0;
452 FOR_EACH_EDGE (e, ei, bb->preds)
453 lsum += e->count;
454 if (lsum - bb->count > 100 || lsum - bb->count < -100)
455 fprintf (file, "%s%sInvalid sum of incoming counts %i, should be %i\n",
456 (flags & TDF_COMMENT) ? ";; " : "", s_indent,
457 (int) lsum, (int) bb->count);
459 if (BB_PARTITION (bb) == BB_COLD_PARTITION)
461 /* Warn about inconsistencies in the partitioning that are
462 currently caused by profile insanities created via optimization. */
463 if (!probably_never_executed_bb_p (fun, bb))
464 fprintf (file, "%s%sBlock in cold partition with hot count\n",
465 (flags & TDF_COMMENT) ? ";; " : "", s_indent);
466 FOR_EACH_EDGE (e, ei, bb->preds)
468 if (!probably_never_executed_edge_p (fun, e))
469 fprintf (file,
470 "%s%sBlock in cold partition with incoming hot edge\n",
471 (flags & TDF_COMMENT) ? ";; " : "", s_indent);
476 void
477 dump_edge_info (FILE *file, edge e, int flags, int do_succ)
479 basic_block side = (do_succ ? e->dest : e->src);
480 bool do_details = false;
482 if ((flags & TDF_DETAILS) != 0
483 && (flags & TDF_SLIM) == 0)
484 do_details = true;
486 if (side->index == ENTRY_BLOCK)
487 fputs (" ENTRY", file);
488 else if (side->index == EXIT_BLOCK)
489 fputs (" EXIT", file);
490 else
491 fprintf (file, " %d", side->index);
493 if (e->probability && do_details)
494 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
496 if (e->count && do_details)
498 fputs (" count:", file);
499 fprintf (file, "%" PRId64, e->count);
502 if (e->flags && do_details)
504 static const char * const bitnames[] =
506 #define DEF_EDGE_FLAG(NAME,IDX) #NAME ,
507 #include "cfg-flags.def"
508 NULL
509 #undef DEF_EDGE_FLAG
511 bool comma = false;
512 int i, flags = e->flags;
514 gcc_assert (e->flags <= EDGE_ALL_FLAGS);
515 fputs (" (", file);
516 for (i = 0; flags; i++)
517 if (flags & (1 << i))
519 flags &= ~(1 << i);
521 if (comma)
522 fputc (',', file);
523 fputs (bitnames[i], file);
524 comma = true;
527 fputc (')', file);
531 DEBUG_FUNCTION void
532 debug (edge_def &ref)
534 /* FIXME (crowl): Is this desireable? */
535 dump_edge_info (stderr, &ref, 0, false);
536 dump_edge_info (stderr, &ref, 0, true);
539 DEBUG_FUNCTION void
540 debug (edge_def *ptr)
542 if (ptr)
543 debug (*ptr);
544 else
545 fprintf (stderr, "<nil>\n");
548 /* Simple routines to easily allocate AUX fields of basic blocks. */
550 static struct obstack block_aux_obstack;
551 static void *first_block_aux_obj = 0;
552 static struct obstack edge_aux_obstack;
553 static void *first_edge_aux_obj = 0;
555 /* Allocate a memory block of SIZE as BB->aux. The obstack must
556 be first initialized by alloc_aux_for_blocks. */
558 static void
559 alloc_aux_for_block (basic_block bb, int size)
561 /* Verify that aux field is clear. */
562 gcc_assert (!bb->aux && first_block_aux_obj);
563 bb->aux = obstack_alloc (&block_aux_obstack, size);
564 memset (bb->aux, 0, size);
567 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
568 alloc_aux_for_block for each basic block. */
570 void
571 alloc_aux_for_blocks (int size)
573 static int initialized;
575 if (!initialized)
577 gcc_obstack_init (&block_aux_obstack);
578 initialized = 1;
580 else
581 /* Check whether AUX data are still allocated. */
582 gcc_assert (!first_block_aux_obj);
584 first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
585 if (size)
587 basic_block bb;
589 FOR_ALL_BB_FN (bb, cfun)
590 alloc_aux_for_block (bb, size);
594 /* Clear AUX pointers of all blocks. */
596 void
597 clear_aux_for_blocks (void)
599 basic_block bb;
601 FOR_ALL_BB_FN (bb, cfun)
602 bb->aux = NULL;
605 /* Free data allocated in block_aux_obstack and clear AUX pointers
606 of all blocks. */
608 void
609 free_aux_for_blocks (void)
611 gcc_assert (first_block_aux_obj);
612 obstack_free (&block_aux_obstack, first_block_aux_obj);
613 first_block_aux_obj = NULL;
615 clear_aux_for_blocks ();
618 /* Allocate a memory edge of SIZE as E->aux. The obstack must
619 be first initialized by alloc_aux_for_edges. */
621 void
622 alloc_aux_for_edge (edge e, int size)
624 /* Verify that aux field is clear. */
625 gcc_assert (!e->aux && first_edge_aux_obj);
626 e->aux = obstack_alloc (&edge_aux_obstack, size);
627 memset (e->aux, 0, size);
630 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
631 alloc_aux_for_edge for each basic edge. */
633 void
634 alloc_aux_for_edges (int size)
636 static int initialized;
638 if (!initialized)
640 gcc_obstack_init (&edge_aux_obstack);
641 initialized = 1;
643 else
644 /* Check whether AUX data are still allocated. */
645 gcc_assert (!first_edge_aux_obj);
647 first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
648 if (size)
650 basic_block bb;
652 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
653 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
655 edge e;
656 edge_iterator ei;
658 FOR_EACH_EDGE (e, ei, bb->succs)
659 alloc_aux_for_edge (e, size);
664 /* Clear AUX pointers of all edges. */
666 void
667 clear_aux_for_edges (void)
669 basic_block bb;
670 edge e;
672 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
673 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
675 edge_iterator ei;
676 FOR_EACH_EDGE (e, ei, bb->succs)
677 e->aux = NULL;
681 /* Free data allocated in edge_aux_obstack and clear AUX pointers
682 of all edges. */
684 void
685 free_aux_for_edges (void)
687 gcc_assert (first_edge_aux_obj);
688 obstack_free (&edge_aux_obstack, first_edge_aux_obj);
689 first_edge_aux_obj = NULL;
691 clear_aux_for_edges ();
694 DEBUG_FUNCTION void
695 debug_bb (basic_block bb)
697 dump_bb (stderr, bb, 0, dump_flags);
700 DEBUG_FUNCTION basic_block
701 debug_bb_n (int n)
703 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, n);
704 debug_bb (bb);
705 return bb;
708 /* Dumps cfg related information about basic block BB to OUTF.
709 If HEADER is true, dump things that appear before the instructions
710 contained in BB. If FOOTER is true, dump things that appear after.
711 Flags are the TDF_* masks as documented in dumpfile.h.
712 NB: With TDF_DETAILS, it is assumed that cfun is available, so
713 that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE. */
715 void
716 dump_bb_info (FILE *outf, basic_block bb, int indent, int flags,
717 bool do_header, bool do_footer)
719 edge_iterator ei;
720 edge e;
721 static const char * const bb_bitnames[] =
723 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
724 #include "cfg-flags.def"
725 NULL
726 #undef DEF_BASIC_BLOCK_FLAG
728 const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
729 bool first;
730 char *s_indent = (char *) alloca ((size_t) indent + 1);
731 memset ((void *) s_indent, ' ', (size_t) indent);
732 s_indent[indent] = '\0';
734 gcc_assert (bb->flags <= BB_ALL_FLAGS);
736 if (do_header)
738 unsigned i;
740 if (flags & TDF_COMMENT)
741 fputs (";; ", outf);
742 fprintf (outf, "%sbasic block %d, loop depth %d",
743 s_indent, bb->index, bb_loop_depth (bb));
744 if (flags & TDF_DETAILS)
746 struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
747 fprintf (outf, ", count " "%" PRId64,
748 (int64_t) bb->count);
749 fprintf (outf, ", freq %i", bb->frequency);
750 if (maybe_hot_bb_p (fun, bb))
751 fputs (", maybe hot", outf);
752 if (probably_never_executed_bb_p (fun, bb))
753 fputs (", probably never executed", outf);
755 fputc ('\n', outf);
757 if (flags & TDF_DETAILS)
759 check_bb_profile (bb, outf, indent, flags);
760 if (flags & TDF_COMMENT)
761 fputs (";; ", outf);
762 fprintf (outf, "%s prev block ", s_indent);
763 if (bb->prev_bb)
764 fprintf (outf, "%d", bb->prev_bb->index);
765 else
766 fprintf (outf, "(nil)");
767 fprintf (outf, ", next block ");
768 if (bb->next_bb)
769 fprintf (outf, "%d", bb->next_bb->index);
770 else
771 fprintf (outf, "(nil)");
773 fputs (", flags:", outf);
774 first = true;
775 for (i = 0; i < n_bitnames; i++)
776 if (bb->flags & (1 << i))
778 if (first)
779 fputs (" (", outf);
780 else
781 fputs (", ", outf);
782 first = false;
783 fputs (bb_bitnames[i], outf);
785 if (!first)
786 fputc (')', outf);
787 fputc ('\n', outf);
790 if (flags & TDF_COMMENT)
791 fputs (";; ", outf);
792 fprintf (outf, "%s pred: ", s_indent);
793 first = true;
794 FOR_EACH_EDGE (e, ei, bb->preds)
796 if (! first)
798 if (flags & TDF_COMMENT)
799 fputs (";; ", outf);
800 fprintf (outf, "%s ", s_indent);
802 first = false;
803 dump_edge_info (outf, e, flags, 0);
804 fputc ('\n', outf);
806 if (first)
807 fputc ('\n', outf);
810 if (do_footer)
812 if (flags & TDF_COMMENT)
813 fputs (";; ", outf);
814 fprintf (outf, "%s succ: ", s_indent);
815 first = true;
816 FOR_EACH_EDGE (e, ei, bb->succs)
818 if (! first)
820 if (flags & TDF_COMMENT)
821 fputs (";; ", outf);
822 fprintf (outf, "%s ", s_indent);
824 first = false;
825 dump_edge_info (outf, e, flags, 1);
826 fputc ('\n', outf);
828 if (first)
829 fputc ('\n', outf);
833 /* Dumps a brief description of cfg to FILE. */
835 void
836 brief_dump_cfg (FILE *file, int flags)
838 basic_block bb;
840 FOR_EACH_BB_FN (bb, cfun)
842 dump_bb_info (file, bb, 0,
843 flags & (TDF_COMMENT | TDF_DETAILS),
844 true, true);
848 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
849 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
850 redirected to destination of TAKEN_EDGE.
852 This function may leave the profile inconsistent in the case TAKEN_EDGE
853 frequency or count is believed to be lower than FREQUENCY or COUNT
854 respectively. */
855 void
856 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
857 gcov_type count, edge taken_edge)
859 edge c;
860 int prob;
861 edge_iterator ei;
863 bb->count -= count;
864 if (bb->count < 0)
866 if (dump_file)
867 fprintf (dump_file, "bb %i count became negative after threading",
868 bb->index);
869 bb->count = 0;
872 bb->frequency -= edge_frequency;
873 if (bb->frequency < 0)
874 bb->frequency = 0;
876 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
877 Watch for overflows. */
878 if (bb->frequency)
879 prob = GCOV_COMPUTE_SCALE (edge_frequency, bb->frequency);
880 else
881 prob = 0;
882 if (prob > taken_edge->probability)
884 if (dump_file)
885 fprintf (dump_file, "Jump threading proved probability of edge "
886 "%i->%i too small (it is %i, should be %i).\n",
887 taken_edge->src->index, taken_edge->dest->index,
888 taken_edge->probability, prob);
889 prob = taken_edge->probability * 6 / 8;
892 /* Now rescale the probabilities. */
893 taken_edge->probability -= prob;
894 prob = REG_BR_PROB_BASE - prob;
895 if (prob <= 0)
897 if (dump_file)
898 fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
899 "frequency of block should end up being 0, it is %i\n",
900 bb->index, bb->frequency);
901 EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
902 ei = ei_start (bb->succs);
903 ei_next (&ei);
904 for (; (c = ei_safe_edge (ei)); ei_next (&ei))
905 c->probability = 0;
907 else if (prob != REG_BR_PROB_BASE)
909 int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
911 FOR_EACH_EDGE (c, ei, bb->succs)
913 /* Protect from overflow due to additional scaling. */
914 if (c->probability > prob)
915 c->probability = REG_BR_PROB_BASE;
916 else
918 c->probability = RDIV (c->probability * scale, 65536);
919 if (c->probability > REG_BR_PROB_BASE)
920 c->probability = REG_BR_PROB_BASE;
925 gcc_assert (bb == taken_edge->src);
926 taken_edge->count -= count;
927 if (taken_edge->count < 0)
929 if (dump_file)
930 fprintf (dump_file, "edge %i->%i count became negative after threading",
931 taken_edge->src->index, taken_edge->dest->index);
932 taken_edge->count = 0;
936 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
937 by NUM/DEN, in int arithmetic. May lose some accuracy. */
938 void
939 scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
941 int i;
942 edge e;
943 if (num < 0)
944 num = 0;
946 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
947 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
948 and still safely fit in int during calculations. */
949 if (den > 1000)
951 if (num > 1000000)
952 return;
954 num = RDIV (1000 * num, den);
955 den = 1000;
957 if (num > 100 * den)
958 return;
960 for (i = 0; i < nbbs; i++)
962 edge_iterator ei;
963 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
964 /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
965 if (bbs[i]->frequency > BB_FREQ_MAX)
966 bbs[i]->frequency = BB_FREQ_MAX;
967 bbs[i]->count = RDIV (bbs[i]->count * num, den);
968 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
969 e->count = RDIV (e->count * num, den);
973 /* numbers smaller than this value are safe to multiply without getting
974 64bit overflow. */
975 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (int64_t) * 4 - 1))
977 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
978 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
979 function but considerably slower. */
980 void
981 scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
982 gcov_type den)
984 int i;
985 edge e;
986 gcov_type fraction = RDIV (num * 65536, den);
988 gcc_assert (fraction >= 0);
990 if (num < MAX_SAFE_MULTIPLIER)
991 for (i = 0; i < nbbs; i++)
993 edge_iterator ei;
994 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
995 if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
996 bbs[i]->count = RDIV (bbs[i]->count * num, den);
997 else
998 bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
999 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1000 if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1001 e->count = RDIV (e->count * num, den);
1002 else
1003 e->count = RDIV (e->count * fraction, 65536);
1005 else
1006 for (i = 0; i < nbbs; i++)
1008 edge_iterator ei;
1009 if (sizeof (gcov_type) > sizeof (int))
1010 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1011 else
1012 bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
1013 bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1014 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1015 e->count = RDIV (e->count * fraction, 65536);
1019 /* Helper types for hash tables. */
1021 struct htab_bb_copy_original_entry
1023 /* Block we are attaching info to. */
1024 int index1;
1025 /* Index of original or copy (depending on the hashtable) */
1026 int index2;
1029 struct bb_copy_hasher : nofree_ptr_hash <htab_bb_copy_original_entry>
1031 static inline hashval_t hash (const htab_bb_copy_original_entry *);
1032 static inline bool equal (const htab_bb_copy_original_entry *existing,
1033 const htab_bb_copy_original_entry * candidate);
1036 inline hashval_t
1037 bb_copy_hasher::hash (const htab_bb_copy_original_entry *data)
1039 return data->index1;
1042 inline bool
1043 bb_copy_hasher::equal (const htab_bb_copy_original_entry *data,
1044 const htab_bb_copy_original_entry *data2)
1046 return data->index1 == data2->index1;
1049 /* Data structures used to maintain mapping between basic blocks and
1050 copies. */
1051 static hash_table<bb_copy_hasher> *bb_original;
1052 static hash_table<bb_copy_hasher> *bb_copy;
1054 /* And between loops and copies. */
1055 static hash_table<bb_copy_hasher> *loop_copy;
1056 static object_allocator<htab_bb_copy_original_entry> *original_copy_bb_pool;
1058 /* Initialize the data structures to maintain mapping between blocks
1059 and its copies. */
1060 void
1061 initialize_original_copy_tables (void)
1063 original_copy_bb_pool = new object_allocator<htab_bb_copy_original_entry>
1064 ("original_copy");
1065 bb_original = new hash_table<bb_copy_hasher> (10);
1066 bb_copy = new hash_table<bb_copy_hasher> (10);
1067 loop_copy = new hash_table<bb_copy_hasher> (10);
1070 /* Reset the data structures to maintain mapping between blocks and
1071 its copies. */
1073 void
1074 reset_original_copy_tables (void)
1076 gcc_assert (original_copy_bb_pool);
1077 bb_original->empty ();
1078 bb_copy->empty ();
1079 loop_copy->empty ();
1082 /* Free the data structures to maintain mapping between blocks and
1083 its copies. */
1084 void
1085 free_original_copy_tables (void)
1087 gcc_assert (original_copy_bb_pool);
1088 delete bb_copy;
1089 bb_copy = NULL;
1090 delete bb_original;
1091 bb_original = NULL;
1092 delete loop_copy;
1093 loop_copy = NULL;
1094 delete original_copy_bb_pool;
1095 original_copy_bb_pool = NULL;
1098 /* Return true iff we have had a call to initialize_original_copy_tables
1099 without a corresponding call to free_original_copy_tables. */
1101 bool
1102 original_copy_tables_initialized_p (void)
1104 return original_copy_bb_pool != NULL;
1107 /* Removes the value associated with OBJ from table TAB. */
1109 static void
1110 copy_original_table_clear (hash_table<bb_copy_hasher> *tab, unsigned obj)
1112 htab_bb_copy_original_entry **slot;
1113 struct htab_bb_copy_original_entry key, *elt;
1115 if (!original_copy_bb_pool)
1116 return;
1118 key.index1 = obj;
1119 slot = tab->find_slot (&key, NO_INSERT);
1120 if (!slot)
1121 return;
1123 elt = *slot;
1124 tab->clear_slot (slot);
1125 original_copy_bb_pool->remove (elt);
1128 /* Sets the value associated with OBJ in table TAB to VAL.
1129 Do nothing when data structures are not initialized. */
1131 static void
1132 copy_original_table_set (hash_table<bb_copy_hasher> *tab,
1133 unsigned obj, unsigned val)
1135 struct htab_bb_copy_original_entry **slot;
1136 struct htab_bb_copy_original_entry key;
1138 if (!original_copy_bb_pool)
1139 return;
1141 key.index1 = obj;
1142 slot = tab->find_slot (&key, INSERT);
1143 if (!*slot)
1145 *slot = original_copy_bb_pool->allocate ();
1146 (*slot)->index1 = obj;
1148 (*slot)->index2 = val;
1151 /* Set original for basic block. Do nothing when data structures are not
1152 initialized so passes not needing this don't need to care. */
1153 void
1154 set_bb_original (basic_block bb, basic_block original)
1156 copy_original_table_set (bb_original, bb->index, original->index);
1159 /* Get the original basic block. */
1160 basic_block
1161 get_bb_original (basic_block bb)
1163 struct htab_bb_copy_original_entry *entry;
1164 struct htab_bb_copy_original_entry key;
1166 gcc_assert (original_copy_bb_pool);
1168 key.index1 = bb->index;
1169 entry = bb_original->find (&key);
1170 if (entry)
1171 return BASIC_BLOCK_FOR_FN (cfun, entry->index2);
1172 else
1173 return NULL;
1176 /* Set copy for basic block. Do nothing when data structures are not
1177 initialized so passes not needing this don't need to care. */
1178 void
1179 set_bb_copy (basic_block bb, basic_block copy)
1181 copy_original_table_set (bb_copy, bb->index, copy->index);
1184 /* Get the copy of basic block. */
1185 basic_block
1186 get_bb_copy (basic_block bb)
1188 struct htab_bb_copy_original_entry *entry;
1189 struct htab_bb_copy_original_entry key;
1191 gcc_assert (original_copy_bb_pool);
1193 key.index1 = bb->index;
1194 entry = bb_copy->find (&key);
1195 if (entry)
1196 return BASIC_BLOCK_FOR_FN (cfun, entry->index2);
1197 else
1198 return NULL;
1201 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1202 initialized so passes not needing this don't need to care. */
1204 void
1205 set_loop_copy (struct loop *loop, struct loop *copy)
1207 if (!copy)
1208 copy_original_table_clear (loop_copy, loop->num);
1209 else
1210 copy_original_table_set (loop_copy, loop->num, copy->num);
1213 /* Get the copy of LOOP. */
1215 struct loop *
1216 get_loop_copy (struct loop *loop)
1218 struct htab_bb_copy_original_entry *entry;
1219 struct htab_bb_copy_original_entry key;
1221 gcc_assert (original_copy_bb_pool);
1223 key.index1 = loop->num;
1224 entry = loop_copy->find (&key);
1225 if (entry)
1226 return get_loop (cfun, entry->index2);
1227 else
1228 return NULL;