Daily bump.
[official-gcc.git] / gcc / cfg.c
blob9c6c939139c35ee49f13105ff22b5e3938861838
1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2013 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 "obstack.h"
53 #include "ggc.h"
54 #include "hash-table.h"
55 #include "alloc-pool.h"
56 #include "tree.h"
57 #include "basic-block.h"
58 #include "df.h"
59 #include "cfgloop.h" /* FIXME: For struct loop. */
60 #include "dumpfile.h"
63 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
65 /* Called once at initialization time. */
67 void
68 init_flow (struct function *the_fun)
70 if (!the_fun->cfg)
71 the_fun->cfg = ggc_alloc_cleared_control_flow_graph ();
72 n_edges_for_function (the_fun) = 0;
73 ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)
74 = ggc_alloc_cleared_basic_block_def ();
75 ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = ENTRY_BLOCK;
76 EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)
77 = ggc_alloc_cleared_basic_block_def ();
78 EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = EXIT_BLOCK;
79 ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->next_bb
80 = EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun);
81 EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)->prev_bb
82 = ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun);
85 /* Helper function for remove_edge and clear_edges. Frees edge structure
86 without actually removing it from the pred/succ arrays. */
88 static void
89 free_edge (edge e)
91 n_edges--;
92 ggc_free (e);
95 /* Free the memory associated with the edge structures. */
97 void
98 clear_edges (void)
100 basic_block bb;
101 edge e;
102 edge_iterator ei;
104 FOR_EACH_BB (bb)
106 FOR_EACH_EDGE (e, ei, bb->succs)
107 free_edge (e);
108 vec_safe_truncate (bb->succs, 0);
109 vec_safe_truncate (bb->preds, 0);
112 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
113 free_edge (e);
114 vec_safe_truncate (EXIT_BLOCK_PTR->preds, 0);
115 vec_safe_truncate (ENTRY_BLOCK_PTR->succs, 0);
117 gcc_assert (!n_edges);
120 /* Allocate memory for basic_block. */
122 basic_block
123 alloc_block (void)
125 basic_block bb;
126 bb = ggc_alloc_cleared_basic_block_def ();
127 return bb;
130 /* Link block B to chain after AFTER. */
131 void
132 link_block (basic_block b, basic_block after)
134 b->next_bb = after->next_bb;
135 b->prev_bb = after;
136 after->next_bb = b;
137 b->next_bb->prev_bb = b;
140 /* Unlink block B from chain. */
141 void
142 unlink_block (basic_block b)
144 b->next_bb->prev_bb = b->prev_bb;
145 b->prev_bb->next_bb = b->next_bb;
146 b->prev_bb = NULL;
147 b->next_bb = NULL;
150 /* Sequentially order blocks and compact the arrays. */
151 void
152 compact_blocks (void)
154 int i;
156 SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
157 SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
159 if (df)
160 df_compact_blocks ();
161 else
163 basic_block bb;
165 i = NUM_FIXED_BLOCKS;
166 FOR_EACH_BB (bb)
168 SET_BASIC_BLOCK (i, bb);
169 bb->index = i;
170 i++;
172 gcc_assert (i == n_basic_blocks);
174 for (; i < last_basic_block; i++)
175 SET_BASIC_BLOCK (i, NULL);
177 last_basic_block = n_basic_blocks;
180 /* Remove block B from the basic block array. */
182 void
183 expunge_block (basic_block b)
185 unlink_block (b);
186 SET_BASIC_BLOCK (b->index, NULL);
187 n_basic_blocks--;
188 /* We should be able to ggc_free here, but we are not.
189 The dead SSA_NAMES are left pointing to dead statements that are pointing
190 to dead basic blocks making garbage collector to die.
191 We should be able to release all dead SSA_NAMES and at the same time we should
192 clear out BB pointer of dead statements consistently. */
195 /* Connect E to E->src. */
197 static inline void
198 connect_src (edge e)
200 vec_safe_push (e->src->succs, e);
201 df_mark_solutions_dirty ();
204 /* Connect E to E->dest. */
206 static inline void
207 connect_dest (edge e)
209 basic_block dest = e->dest;
210 vec_safe_push (dest->preds, e);
211 e->dest_idx = EDGE_COUNT (dest->preds) - 1;
212 df_mark_solutions_dirty ();
215 /* Disconnect edge E from E->src. */
217 static inline void
218 disconnect_src (edge e)
220 basic_block src = e->src;
221 edge_iterator ei;
222 edge tmp;
224 for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
226 if (tmp == e)
228 src->succs->unordered_remove (ei.index);
229 df_mark_solutions_dirty ();
230 return;
232 else
233 ei_next (&ei);
236 gcc_unreachable ();
239 /* Disconnect edge E from E->dest. */
241 static inline void
242 disconnect_dest (edge e)
244 basic_block dest = e->dest;
245 unsigned int dest_idx = e->dest_idx;
247 dest->preds->unordered_remove (dest_idx);
249 /* If we removed an edge in the middle of the edge vector, we need
250 to update dest_idx of the edge that moved into the "hole". */
251 if (dest_idx < EDGE_COUNT (dest->preds))
252 EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
253 df_mark_solutions_dirty ();
256 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
257 created edge. Use this only if you are sure that this edge can't
258 possibly already exist. */
260 edge
261 unchecked_make_edge (basic_block src, basic_block dst, int flags)
263 edge e;
264 e = ggc_alloc_cleared_edge_def ();
265 n_edges++;
267 e->src = src;
268 e->dest = dst;
269 e->flags = flags;
271 connect_src (e);
272 connect_dest (e);
274 execute_on_growing_pred (e);
275 return e;
278 /* Create an edge connecting SRC and DST with FLAGS optionally using
279 edge cache CACHE. Return the new edge, NULL if already exist. */
281 edge
282 cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
284 if (edge_cache == NULL
285 || src == ENTRY_BLOCK_PTR
286 || dst == EXIT_BLOCK_PTR)
287 return make_edge (src, dst, flags);
289 /* Does the requested edge already exist? */
290 if (! bitmap_bit_p (edge_cache, dst->index))
292 /* The edge does not exist. Create one and update the
293 cache. */
294 bitmap_set_bit (edge_cache, dst->index);
295 return unchecked_make_edge (src, dst, flags);
298 /* At this point, we know that the requested edge exists. Adjust
299 flags if necessary. */
300 if (flags)
302 edge e = find_edge (src, dst);
303 e->flags |= flags;
306 return NULL;
309 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
310 created edge or NULL if already exist. */
312 edge
313 make_edge (basic_block src, basic_block dest, int flags)
315 edge e = find_edge (src, dest);
317 /* Make sure we don't add duplicate edges. */
318 if (e)
320 e->flags |= flags;
321 return NULL;
324 return unchecked_make_edge (src, dest, flags);
327 /* Create an edge connecting SRC to DEST and set probability by knowing
328 that it is the single edge leaving SRC. */
330 edge
331 make_single_succ_edge (basic_block src, basic_block dest, int flags)
333 edge e = make_edge (src, dest, flags);
335 e->probability = REG_BR_PROB_BASE;
336 e->count = src->count;
337 return e;
340 /* This function will remove an edge from the flow graph. */
342 void
343 remove_edge_raw (edge e)
345 remove_predictions_associated_with_edge (e);
346 execute_on_shrinking_pred (e);
348 disconnect_src (e);
349 disconnect_dest (e);
351 free_edge (e);
354 /* Redirect an edge's successor from one block to another. */
356 void
357 redirect_edge_succ (edge e, basic_block new_succ)
359 execute_on_shrinking_pred (e);
361 disconnect_dest (e);
363 e->dest = new_succ;
365 /* Reconnect the edge to the new successor block. */
366 connect_dest (e);
368 execute_on_growing_pred (e);
371 /* Redirect an edge's predecessor from one block to another. */
373 void
374 redirect_edge_pred (edge e, basic_block new_pred)
376 disconnect_src (e);
378 e->src = new_pred;
380 /* Reconnect the edge to the new predecessor block. */
381 connect_src (e);
384 /* Clear all basic block flags that do not have to be preserved. */
385 void
386 clear_bb_flags (void)
388 basic_block bb;
390 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
391 bb->flags &= BB_FLAGS_TO_PRESERVE;
394 /* Check the consistency of profile information. We can't do that
395 in verify_flow_info, as the counts may get invalid for incompletely
396 solved graphs, later eliminating of conditionals or roundoff errors.
397 It is still practical to have them reported for debugging of simple
398 testcases. */
399 static void
400 check_bb_profile (basic_block bb, FILE * file, int indent, int flags)
402 edge e;
403 int sum = 0;
404 gcov_type lsum;
405 edge_iterator ei;
406 struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
407 char *s_indent = (char *) alloca ((size_t) indent + 1);
408 memset ((void *) s_indent, ' ', (size_t) indent);
409 s_indent[indent] = '\0';
411 if (profile_status_for_function (fun) == PROFILE_ABSENT)
412 return;
414 if (bb != EXIT_BLOCK_PTR_FOR_FUNCTION (fun))
416 FOR_EACH_EDGE (e, ei, bb->succs)
417 sum += e->probability;
418 if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
419 fprintf (file, "%s%sInvalid sum of outgoing probabilities %.1f%%\n",
420 (flags & TDF_COMMENT) ? ";; " : "", s_indent,
421 sum * 100.0 / REG_BR_PROB_BASE);
422 lsum = 0;
423 FOR_EACH_EDGE (e, ei, bb->succs)
424 lsum += e->count;
425 if (EDGE_COUNT (bb->succs)
426 && (lsum - bb->count > 100 || lsum - bb->count < -100))
427 fprintf (file, "%s%sInvalid sum of outgoing counts %i, should be %i\n",
428 (flags & TDF_COMMENT) ? ";; " : "", s_indent,
429 (int) lsum, (int) bb->count);
431 if (bb != ENTRY_BLOCK_PTR_FOR_FUNCTION (fun))
433 sum = 0;
434 FOR_EACH_EDGE (e, ei, bb->preds)
435 sum += EDGE_FREQUENCY (e);
436 if (abs (sum - bb->frequency) > 100)
437 fprintf (file,
438 "%s%sInvalid sum of incoming frequencies %i, should be %i\n",
439 (flags & TDF_COMMENT) ? ";; " : "", s_indent,
440 sum, bb->frequency);
441 lsum = 0;
442 FOR_EACH_EDGE (e, ei, bb->preds)
443 lsum += e->count;
444 if (lsum - bb->count > 100 || lsum - bb->count < -100)
445 fprintf (file, "%s%sInvalid sum of incoming counts %i, should be %i\n",
446 (flags & TDF_COMMENT) ? ";; " : "", s_indent,
447 (int) lsum, (int) bb->count);
451 void
452 dump_edge_info (FILE *file, edge e, int flags, int do_succ)
454 basic_block side = (do_succ ? e->dest : e->src);
455 bool do_details = false;
457 if ((flags & TDF_DETAILS) != 0
458 && (flags & TDF_SLIM) == 0)
459 do_details = true;
461 /* ENTRY_BLOCK_PTR/EXIT_BLOCK_PTR depend on cfun.
462 Compare against ENTRY_BLOCK/EXIT_BLOCK to avoid that dependency. */
463 if (side->index == ENTRY_BLOCK)
464 fputs (" ENTRY", file);
465 else if (side->index == EXIT_BLOCK)
466 fputs (" EXIT", file);
467 else
468 fprintf (file, " %d", side->index);
470 if (e->probability && do_details)
471 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
473 if (e->count && do_details)
475 fputs (" count:", file);
476 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
479 if (e->flags && do_details)
481 static const char * const bitnames[] =
483 #define DEF_EDGE_FLAG(NAME,IDX) #NAME ,
484 #include "cfg-flags.def"
485 NULL
486 #undef DEF_EDGE_FLAG
488 bool comma = false;
489 int i, flags = e->flags;
491 gcc_assert (e->flags <= EDGE_ALL_FLAGS);
492 fputs (" (", file);
493 for (i = 0; flags; i++)
494 if (flags & (1 << i))
496 flags &= ~(1 << i);
498 if (comma)
499 fputc (',', file);
500 fputs (bitnames[i], file);
501 comma = true;
504 fputc (')', file);
508 DEBUG_FUNCTION void
509 debug (edge_def &ref)
511 /* FIXME (crowl): Is this desireable? */
512 dump_edge_info (stderr, &ref, 0, false);
513 dump_edge_info (stderr, &ref, 0, true);
516 DEBUG_FUNCTION void
517 debug (edge_def *ptr)
519 if (ptr)
520 debug (*ptr);
521 else
522 fprintf (stderr, "<nil>\n");
525 /* Simple routines to easily allocate AUX fields of basic blocks. */
527 static struct obstack block_aux_obstack;
528 static void *first_block_aux_obj = 0;
529 static struct obstack edge_aux_obstack;
530 static void *first_edge_aux_obj = 0;
532 /* Allocate a memory block of SIZE as BB->aux. The obstack must
533 be first initialized by alloc_aux_for_blocks. */
535 static void
536 alloc_aux_for_block (basic_block bb, int size)
538 /* Verify that aux field is clear. */
539 gcc_assert (!bb->aux && first_block_aux_obj);
540 bb->aux = obstack_alloc (&block_aux_obstack, size);
541 memset (bb->aux, 0, size);
544 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
545 alloc_aux_for_block for each basic block. */
547 void
548 alloc_aux_for_blocks (int size)
550 static int initialized;
552 if (!initialized)
554 gcc_obstack_init (&block_aux_obstack);
555 initialized = 1;
557 else
558 /* Check whether AUX data are still allocated. */
559 gcc_assert (!first_block_aux_obj);
561 first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
562 if (size)
564 basic_block bb;
566 FOR_ALL_BB (bb)
567 alloc_aux_for_block (bb, size);
571 /* Clear AUX pointers of all blocks. */
573 void
574 clear_aux_for_blocks (void)
576 basic_block bb;
578 FOR_ALL_BB (bb)
579 bb->aux = NULL;
582 /* Free data allocated in block_aux_obstack and clear AUX pointers
583 of all blocks. */
585 void
586 free_aux_for_blocks (void)
588 gcc_assert (first_block_aux_obj);
589 obstack_free (&block_aux_obstack, first_block_aux_obj);
590 first_block_aux_obj = NULL;
592 clear_aux_for_blocks ();
595 /* Allocate a memory edge of SIZE as E->aux. The obstack must
596 be first initialized by alloc_aux_for_edges. */
598 void
599 alloc_aux_for_edge (edge e, int size)
601 /* Verify that aux field is clear. */
602 gcc_assert (!e->aux && first_edge_aux_obj);
603 e->aux = obstack_alloc (&edge_aux_obstack, size);
604 memset (e->aux, 0, size);
607 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
608 alloc_aux_for_edge for each basic edge. */
610 void
611 alloc_aux_for_edges (int size)
613 static int initialized;
615 if (!initialized)
617 gcc_obstack_init (&edge_aux_obstack);
618 initialized = 1;
620 else
621 /* Check whether AUX data are still allocated. */
622 gcc_assert (!first_edge_aux_obj);
624 first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
625 if (size)
627 basic_block bb;
629 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
631 edge e;
632 edge_iterator ei;
634 FOR_EACH_EDGE (e, ei, bb->succs)
635 alloc_aux_for_edge (e, size);
640 /* Clear AUX pointers of all edges. */
642 void
643 clear_aux_for_edges (void)
645 basic_block bb;
646 edge e;
648 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
650 edge_iterator ei;
651 FOR_EACH_EDGE (e, ei, bb->succs)
652 e->aux = NULL;
656 /* Free data allocated in edge_aux_obstack and clear AUX pointers
657 of all edges. */
659 void
660 free_aux_for_edges (void)
662 gcc_assert (first_edge_aux_obj);
663 obstack_free (&edge_aux_obstack, first_edge_aux_obj);
664 first_edge_aux_obj = NULL;
666 clear_aux_for_edges ();
669 DEBUG_FUNCTION void
670 debug_bb (basic_block bb)
672 dump_bb (stderr, bb, 0, dump_flags);
675 DEBUG_FUNCTION basic_block
676 debug_bb_n (int n)
678 basic_block bb = BASIC_BLOCK (n);
679 debug_bb (bb);
680 return bb;
683 /* Dumps cfg related information about basic block BB to OUTF.
684 If HEADER is true, dump things that appear before the instructions
685 contained in BB. If FOOTER is true, dump things that appear after.
686 Flags are the TDF_* masks as documented in dumpfile.h.
687 NB: With TDF_DETAILS, it is assumed that cfun is available, so
688 that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE. */
690 void
691 dump_bb_info (FILE *outf, basic_block bb, int indent, int flags,
692 bool do_header, bool do_footer)
694 edge_iterator ei;
695 edge e;
696 static const char * const bb_bitnames[] =
698 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
699 #include "cfg-flags.def"
700 NULL
701 #undef DEF_BASIC_BLOCK_FLAG
703 const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
704 bool first;
705 char *s_indent = (char *) alloca ((size_t) indent + 1);
706 memset ((void *) s_indent, ' ', (size_t) indent);
707 s_indent[indent] = '\0';
709 gcc_assert (bb->flags <= BB_ALL_FLAGS);
711 if (do_header)
713 unsigned i;
715 if (flags & TDF_COMMENT)
716 fputs (";; ", outf);
717 fprintf (outf, "%sbasic block %d, loop depth %d",
718 s_indent, bb->index, bb_loop_depth (bb));
719 if (flags & TDF_DETAILS)
721 struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
722 fprintf (outf, ", count " HOST_WIDEST_INT_PRINT_DEC,
723 (HOST_WIDEST_INT) bb->count);
724 fprintf (outf, ", freq %i", bb->frequency);
725 if (maybe_hot_bb_p (fun, bb))
726 fputs (", maybe hot", outf);
727 if (probably_never_executed_bb_p (fun, bb))
728 fputs (", probably never executed", outf);
730 fputc ('\n', outf);
731 if (TDF_DETAILS)
732 check_bb_profile (bb, outf, indent, flags);
734 if (flags & TDF_DETAILS)
736 if (flags & TDF_COMMENT)
737 fputs (";; ", outf);
738 fprintf (outf, "%s prev block ", s_indent);
739 if (bb->prev_bb)
740 fprintf (outf, "%d", bb->prev_bb->index);
741 else
742 fprintf (outf, "(nil)");
743 fprintf (outf, ", next block ");
744 if (bb->next_bb)
745 fprintf (outf, "%d", bb->next_bb->index);
746 else
747 fprintf (outf, "(nil)");
749 fputs (", flags:", outf);
750 first = true;
751 for (i = 0; i < n_bitnames; i++)
752 if (bb->flags & (1 << i))
754 if (first)
755 fputs (" (", outf);
756 else
757 fputs (", ", outf);
758 first = false;
759 fputs (bb_bitnames[i], outf);
761 if (!first)
762 fputc (')', outf);
763 fputc ('\n', outf);
766 if (flags & TDF_COMMENT)
767 fputs (";; ", outf);
768 fprintf (outf, "%s pred: ", s_indent);
769 first = true;
770 FOR_EACH_EDGE (e, ei, bb->preds)
772 if (! first)
774 if (flags & TDF_COMMENT)
775 fputs (";; ", outf);
776 fprintf (outf, "%s ", s_indent);
778 first = false;
779 dump_edge_info (outf, e, flags, 0);
780 fputc ('\n', outf);
782 if (first)
783 fputc ('\n', outf);
786 if (do_footer)
788 if (flags & TDF_COMMENT)
789 fputs (";; ", outf);
790 fprintf (outf, "%s succ: ", s_indent);
791 first = true;
792 FOR_EACH_EDGE (e, ei, bb->succs)
794 if (! first)
796 if (flags & TDF_COMMENT)
797 fputs (";; ", outf);
798 fprintf (outf, "%s ", s_indent);
800 first = false;
801 dump_edge_info (outf, e, flags, 1);
802 fputc ('\n', outf);
804 if (first)
805 fputc ('\n', outf);
809 /* Dumps a brief description of cfg to FILE. */
811 void
812 brief_dump_cfg (FILE *file, int flags)
814 basic_block bb;
816 FOR_EACH_BB (bb)
818 dump_bb_info (file, bb, 0,
819 flags & (TDF_COMMENT | TDF_DETAILS),
820 true, true);
824 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
825 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
826 redirected to destination of TAKEN_EDGE.
828 This function may leave the profile inconsistent in the case TAKEN_EDGE
829 frequency or count is believed to be lower than FREQUENCY or COUNT
830 respectively. */
831 void
832 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
833 gcov_type count, edge taken_edge)
835 edge c;
836 int prob;
837 edge_iterator ei;
839 bb->count -= count;
840 if (bb->count < 0)
842 if (dump_file)
843 fprintf (dump_file, "bb %i count became negative after threading",
844 bb->index);
845 bb->count = 0;
848 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
849 Watch for overflows. */
850 if (bb->frequency)
851 prob = GCOV_COMPUTE_SCALE (edge_frequency, bb->frequency);
852 else
853 prob = 0;
854 if (prob > taken_edge->probability)
856 if (dump_file)
857 fprintf (dump_file, "Jump threading proved probability of edge "
858 "%i->%i too small (it is %i, should be %i).\n",
859 taken_edge->src->index, taken_edge->dest->index,
860 taken_edge->probability, prob);
861 prob = taken_edge->probability;
864 /* Now rescale the probabilities. */
865 taken_edge->probability -= prob;
866 prob = REG_BR_PROB_BASE - prob;
867 bb->frequency -= edge_frequency;
868 if (bb->frequency < 0)
869 bb->frequency = 0;
870 if (prob <= 0)
872 if (dump_file)
873 fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
874 "frequency of block should end up being 0, it is %i\n",
875 bb->index, bb->frequency);
876 EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
877 ei = ei_start (bb->succs);
878 ei_next (&ei);
879 for (; (c = ei_safe_edge (ei)); ei_next (&ei))
880 c->probability = 0;
882 else if (prob != REG_BR_PROB_BASE)
884 int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
886 FOR_EACH_EDGE (c, ei, bb->succs)
888 /* Protect from overflow due to additional scaling. */
889 if (c->probability > prob)
890 c->probability = REG_BR_PROB_BASE;
891 else
893 c->probability = RDIV (c->probability * scale, 65536);
894 if (c->probability > REG_BR_PROB_BASE)
895 c->probability = REG_BR_PROB_BASE;
900 gcc_assert (bb == taken_edge->src);
901 taken_edge->count -= count;
902 if (taken_edge->count < 0)
904 if (dump_file)
905 fprintf (dump_file, "edge %i->%i count became negative after threading",
906 taken_edge->src->index, taken_edge->dest->index);
907 taken_edge->count = 0;
911 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
912 by NUM/DEN, in int arithmetic. May lose some accuracy. */
913 void
914 scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
916 int i;
917 edge e;
918 if (num < 0)
919 num = 0;
921 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
922 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
923 and still safely fit in int during calculations. */
924 if (den > 1000)
926 if (num > 1000000)
927 return;
929 num = RDIV (1000 * num, den);
930 den = 1000;
932 if (num > 100 * den)
933 return;
935 for (i = 0; i < nbbs; i++)
937 edge_iterator ei;
938 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
939 /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
940 if (bbs[i]->frequency > BB_FREQ_MAX)
941 bbs[i]->frequency = BB_FREQ_MAX;
942 bbs[i]->count = RDIV (bbs[i]->count * num, den);
943 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
944 e->count = RDIV (e->count * num, den);
948 /* numbers smaller than this value are safe to multiply without getting
949 64bit overflow. */
950 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
952 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
953 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
954 function but considerably slower. */
955 void
956 scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
957 gcov_type den)
959 int i;
960 edge e;
961 gcov_type fraction = RDIV (num * 65536, den);
963 gcc_assert (fraction >= 0);
965 if (num < MAX_SAFE_MULTIPLIER)
966 for (i = 0; i < nbbs; i++)
968 edge_iterator ei;
969 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
970 if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
971 bbs[i]->count = RDIV (bbs[i]->count * num, den);
972 else
973 bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
974 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
975 if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
976 e->count = RDIV (e->count * num, den);
977 else
978 e->count = RDIV (e->count * fraction, 65536);
980 else
981 for (i = 0; i < nbbs; i++)
983 edge_iterator ei;
984 if (sizeof (gcov_type) > sizeof (int))
985 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
986 else
987 bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
988 bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
989 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
990 e->count = RDIV (e->count * fraction, 65536);
994 /* Helper types for hash tables. */
996 struct htab_bb_copy_original_entry
998 /* Block we are attaching info to. */
999 int index1;
1000 /* Index of original or copy (depending on the hashtable) */
1001 int index2;
1004 struct bb_copy_hasher : typed_noop_remove <htab_bb_copy_original_entry>
1006 typedef htab_bb_copy_original_entry value_type;
1007 typedef htab_bb_copy_original_entry compare_type;
1008 static inline hashval_t hash (const value_type *);
1009 static inline bool equal (const value_type *existing,
1010 const compare_type * candidate);
1013 inline hashval_t
1014 bb_copy_hasher::hash (const value_type *data)
1016 return data->index1;
1019 inline bool
1020 bb_copy_hasher::equal (const value_type *data, const compare_type *data2)
1022 return data->index1 == data2->index1;
1025 /* Data structures used to maintain mapping between basic blocks and
1026 copies. */
1027 static hash_table <bb_copy_hasher> bb_original;
1028 static hash_table <bb_copy_hasher> bb_copy;
1030 /* And between loops and copies. */
1031 static hash_table <bb_copy_hasher> loop_copy;
1032 static alloc_pool original_copy_bb_pool;
1035 /* Initialize the data structures to maintain mapping between blocks
1036 and its copies. */
1037 void
1038 initialize_original_copy_tables (void)
1040 gcc_assert (!original_copy_bb_pool);
1041 original_copy_bb_pool
1042 = create_alloc_pool ("original_copy",
1043 sizeof (struct htab_bb_copy_original_entry), 10);
1044 bb_original.create (10);
1045 bb_copy.create (10);
1046 loop_copy.create (10);
1049 /* Free the data structures to maintain mapping between blocks and
1050 its copies. */
1051 void
1052 free_original_copy_tables (void)
1054 gcc_assert (original_copy_bb_pool);
1055 bb_copy.dispose ();
1056 bb_original.dispose ();
1057 loop_copy.dispose ();
1058 free_alloc_pool (original_copy_bb_pool);
1059 original_copy_bb_pool = NULL;
1062 /* Removes the value associated with OBJ from table TAB. */
1064 static void
1065 copy_original_table_clear (hash_table <bb_copy_hasher> tab, unsigned obj)
1067 htab_bb_copy_original_entry **slot;
1068 struct htab_bb_copy_original_entry key, *elt;
1070 if (!original_copy_bb_pool)
1071 return;
1073 key.index1 = obj;
1074 slot = tab.find_slot (&key, NO_INSERT);
1075 if (!slot)
1076 return;
1078 elt = *slot;
1079 tab.clear_slot (slot);
1080 pool_free (original_copy_bb_pool, elt);
1083 /* Sets the value associated with OBJ in table TAB to VAL.
1084 Do nothing when data structures are not initialized. */
1086 static void
1087 copy_original_table_set (hash_table <bb_copy_hasher> tab,
1088 unsigned obj, unsigned val)
1090 struct htab_bb_copy_original_entry **slot;
1091 struct htab_bb_copy_original_entry key;
1093 if (!original_copy_bb_pool)
1094 return;
1096 key.index1 = obj;
1097 slot = tab.find_slot (&key, INSERT);
1098 if (!*slot)
1100 *slot = (struct htab_bb_copy_original_entry *)
1101 pool_alloc (original_copy_bb_pool);
1102 (*slot)->index1 = obj;
1104 (*slot)->index2 = val;
1107 /* Set original for basic block. Do nothing when data structures are not
1108 initialized so passes not needing this don't need to care. */
1109 void
1110 set_bb_original (basic_block bb, basic_block original)
1112 copy_original_table_set (bb_original, bb->index, original->index);
1115 /* Get the original basic block. */
1116 basic_block
1117 get_bb_original (basic_block bb)
1119 struct htab_bb_copy_original_entry *entry;
1120 struct htab_bb_copy_original_entry key;
1122 gcc_assert (original_copy_bb_pool);
1124 key.index1 = bb->index;
1125 entry = bb_original.find (&key);
1126 if (entry)
1127 return BASIC_BLOCK (entry->index2);
1128 else
1129 return NULL;
1132 /* Set copy for basic block. Do nothing when data structures are not
1133 initialized so passes not needing this don't need to care. */
1134 void
1135 set_bb_copy (basic_block bb, basic_block copy)
1137 copy_original_table_set (bb_copy, bb->index, copy->index);
1140 /* Get the copy of basic block. */
1141 basic_block
1142 get_bb_copy (basic_block bb)
1144 struct htab_bb_copy_original_entry *entry;
1145 struct htab_bb_copy_original_entry key;
1147 gcc_assert (original_copy_bb_pool);
1149 key.index1 = bb->index;
1150 entry = bb_copy.find (&key);
1151 if (entry)
1152 return BASIC_BLOCK (entry->index2);
1153 else
1154 return NULL;
1157 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1158 initialized so passes not needing this don't need to care. */
1160 void
1161 set_loop_copy (struct loop *loop, struct loop *copy)
1163 if (!copy)
1164 copy_original_table_clear (loop_copy, loop->num);
1165 else
1166 copy_original_table_set (loop_copy, loop->num, copy->num);
1169 /* Get the copy of LOOP. */
1171 struct loop *
1172 get_loop_copy (struct loop *loop)
1174 struct htab_bb_copy_original_entry *entry;
1175 struct htab_bb_copy_original_entry key;
1177 gcc_assert (original_copy_bb_pool);
1179 key.index1 = loop->num;
1180 entry = loop_copy.find (&key);
1181 if (entry)
1182 return get_loop (cfun, entry->index2);
1183 else
1184 return NULL;