1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 /* This file contains low level functions to manipulate the CFG and
24 analyze it. All other modules should not transform the data structure
25 directly and use abstraction instead. The file is supposed to be
26 ordered bottom-up and should not contain any code dependent on a
27 particular intermediate language (RTL or trees).
29 Available functionality:
30 - Initialization/deallocation
31 init_flow, clear_edges
32 - Low level basic block manipulation
33 alloc_block, expunge_block
35 make_edge, make_single_succ_edge, cached_make_edge, remove_edge
36 - Low level edge redirection (without updating instruction chain)
37 redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
38 - Dumping and debugging
39 dump_flow_info, debug_flow_info, dump_edge_info
40 - Allocation of AUX fields for basic blocks
41 alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
43 - Consistency checking
45 - Dumping and debugging
46 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
51 #include "coretypes.h"
55 #include "hard-reg-set.h"
65 #include "tree-pass.h"
68 #include "alloc-pool.h"
72 /* The obstack on which the flow graph components are allocated. */
74 struct bitmap_obstack reg_obstack;
76 void debug_flow_info (void);
77 static void free_edge (edge);
79 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
81 /* Called once at initialization time. */
87 cfun->cfg = GGC_CNEW (struct control_flow_graph);
89 ENTRY_BLOCK_PTR = GGC_CNEW (struct basic_block_def);
90 ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
91 EXIT_BLOCK_PTR = GGC_CNEW (struct basic_block_def);
92 EXIT_BLOCK_PTR->index = EXIT_BLOCK;
93 ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
94 EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
97 /* Helper function for remove_edge and clear_edges. Frees edge structure
98 without actually unlinking it from the pred/succ lists. */
101 free_edge (edge e ATTRIBUTE_UNUSED)
107 /* Free the memory associated with the edge structures. */
118 FOR_EACH_EDGE (e, ei, bb->succs)
120 VEC_truncate (edge, bb->succs, 0);
121 VEC_truncate (edge, bb->preds, 0);
124 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
126 VEC_truncate (edge, EXIT_BLOCK_PTR->preds, 0);
127 VEC_truncate (edge, ENTRY_BLOCK_PTR->succs, 0);
129 gcc_assert (!n_edges);
132 /* Allocate memory for basic_block. */
138 bb = GGC_CNEW (struct basic_block_def);
142 /* Link block B to chain after AFTER. */
144 link_block (basic_block b, basic_block after)
146 b->next_bb = after->next_bb;
149 b->next_bb->prev_bb = b;
152 /* Unlink block B from chain. */
154 unlink_block (basic_block b)
156 b->next_bb->prev_bb = b->prev_bb;
157 b->prev_bb->next_bb = b->next_bb;
162 /* Sequentially order blocks and compact the arrays. */
164 compact_blocks (void)
168 SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
169 SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
172 df_compact_blocks ();
177 i = NUM_FIXED_BLOCKS;
180 SET_BASIC_BLOCK (i, bb);
184 gcc_assert (i == n_basic_blocks);
186 for (; i < last_basic_block; i++)
187 SET_BASIC_BLOCK (i, NULL);
189 last_basic_block = n_basic_blocks;
192 /* Remove block B from the basic block array. */
195 expunge_block (basic_block b)
198 SET_BASIC_BLOCK (b->index, NULL);
200 /* We should be able to ggc_free here, but we are not.
201 The dead SSA_NAMES are left pointing to dead statements that are pointing
202 to dead basic blocks making garbage collector to die.
203 We should be able to release all dead SSA_NAMES and at the same time we should
204 clear out BB pointer of dead statements consistently. */
207 /* Connect E to E->src. */
212 VEC_safe_push (edge, gc, e->src->succs, e);
213 df_mark_solutions_dirty ();
216 /* Connect E to E->dest. */
219 connect_dest (edge e)
221 basic_block dest = e->dest;
222 VEC_safe_push (edge, gc, dest->preds, e);
223 e->dest_idx = EDGE_COUNT (dest->preds) - 1;
224 df_mark_solutions_dirty ();
227 /* Disconnect edge E from E->src. */
230 disconnect_src (edge e)
232 basic_block src = e->src;
236 for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
240 VEC_unordered_remove (edge, src->succs, ei.index);
247 df_mark_solutions_dirty ();
251 /* Disconnect edge E from E->dest. */
254 disconnect_dest (edge e)
256 basic_block dest = e->dest;
257 unsigned int dest_idx = e->dest_idx;
259 VEC_unordered_remove (edge, dest->preds, dest_idx);
261 /* If we removed an edge in the middle of the edge vector, we need
262 to update dest_idx of the edge that moved into the "hole". */
263 if (dest_idx < EDGE_COUNT (dest->preds))
264 EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
265 df_mark_solutions_dirty ();
268 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
269 created edge. Use this only if you are sure that this edge can't
270 possibly already exist. */
273 unchecked_make_edge (basic_block src, basic_block dst, int flags)
276 e = GGC_CNEW (struct edge_def);
286 execute_on_growing_pred (e);
290 /* Create an edge connecting SRC and DST with FLAGS optionally using
291 edge cache CACHE. Return the new edge, NULL if already exist. */
294 cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
296 if (edge_cache == NULL
297 || src == ENTRY_BLOCK_PTR
298 || dst == EXIT_BLOCK_PTR)
299 return make_edge (src, dst, flags);
301 /* Does the requested edge already exist? */
302 if (! TEST_BIT (edge_cache, dst->index))
304 /* The edge does not exist. Create one and update the
306 SET_BIT (edge_cache, dst->index);
307 return unchecked_make_edge (src, dst, flags);
310 /* At this point, we know that the requested edge exists. Adjust
311 flags if necessary. */
314 edge e = find_edge (src, dst);
321 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
322 created edge or NULL if already exist. */
325 make_edge (basic_block src, basic_block dest, int flags)
327 edge e = find_edge (src, dest);
329 /* Make sure we don't add duplicate edges. */
336 return unchecked_make_edge (src, dest, flags);
339 /* Create an edge connecting SRC to DEST and set probability by knowing
340 that it is the single edge leaving SRC. */
343 make_single_succ_edge (basic_block src, basic_block dest, int flags)
345 edge e = make_edge (src, dest, flags);
347 e->probability = REG_BR_PROB_BASE;
348 e->count = src->count;
352 /* This function will remove an edge from the flow graph. */
355 remove_edge_raw (edge e)
357 remove_predictions_associated_with_edge (e);
358 execute_on_shrinking_pred (e);
366 /* Redirect an edge's successor from one block to another. */
369 redirect_edge_succ (edge e, basic_block new_succ)
371 execute_on_shrinking_pred (e);
377 /* Reconnect the edge to the new successor block. */
380 execute_on_growing_pred (e);
383 /* Like previous but avoid possible duplicate edge. */
386 redirect_edge_succ_nodup (edge e, basic_block new_succ)
390 s = find_edge (e->src, new_succ);
393 s->flags |= e->flags;
394 s->probability += e->probability;
395 if (s->probability > REG_BR_PROB_BASE)
396 s->probability = REG_BR_PROB_BASE;
397 s->count += e->count;
402 redirect_edge_succ (e, new_succ);
407 /* Redirect an edge's predecessor from one block to another. */
410 redirect_edge_pred (edge e, basic_block new_pred)
416 /* Reconnect the edge to the new predecessor block. */
420 /* Clear all basic block flags, with the exception of partitioning and
423 clear_bb_flags (void)
427 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
428 bb->flags = (BB_PARTITION (bb)
429 | (bb->flags & (BB_DISABLE_SCHEDULE + BB_RTL + BB_NON_LOCAL_GOTO_TARGET)));
432 /* Check the consistency of profile information. We can't do that
433 in verify_flow_info, as the counts may get invalid for incompletely
434 solved graphs, later eliminating of conditionals or roundoff errors.
435 It is still practical to have them reported for debugging of simple
438 check_bb_profile (basic_block bb, FILE * file)
445 if (profile_status == PROFILE_ABSENT)
448 if (bb != EXIT_BLOCK_PTR)
450 FOR_EACH_EDGE (e, ei, bb->succs)
451 sum += e->probability;
452 if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
453 fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
454 sum * 100.0 / REG_BR_PROB_BASE);
456 FOR_EACH_EDGE (e, ei, bb->succs)
458 if (EDGE_COUNT (bb->succs)
459 && (lsum - bb->count > 100 || lsum - bb->count < -100))
460 fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n",
461 (int) lsum, (int) bb->count);
463 if (bb != ENTRY_BLOCK_PTR)
466 FOR_EACH_EDGE (e, ei, bb->preds)
467 sum += EDGE_FREQUENCY (e);
468 if (abs (sum - bb->frequency) > 100)
470 "Invalid sum of incoming frequencies %i, should be %i\n",
473 FOR_EACH_EDGE (e, ei, bb->preds)
475 if (lsum - bb->count > 100 || lsum - bb->count < -100)
476 fprintf (file, "Invalid sum of incoming counts %i, should be %i\n",
477 (int) lsum, (int) bb->count);
481 /* Write information about registers and basic blocks into FILE.
482 This is part of making a debugging dump. */
485 dump_regset (regset r, FILE *outf)
488 reg_set_iterator rsi;
492 fputs (" (nil)", outf);
496 EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi)
498 fprintf (outf, " %d", i);
499 if (i < FIRST_PSEUDO_REGISTER)
500 fprintf (outf, " [%s]",
505 /* Print a human-readable representation of R on the standard error
506 stream. This function is designed to be used from within the
510 debug_regset (regset r)
512 dump_regset (r, stderr);
516 /* Emit basic block information for BB. HEADER is true if the user wants
517 the generic information and the predecessors, FOOTER is true if they want
518 the successors. FLAGS is the dump flags of interest; TDF_DETAILS emit
519 global register liveness information. PREFIX is put in front of every
520 line. The output is emitted to FILE. */
522 dump_bb_info (basic_block bb, bool header, bool footer, int flags,
523 const char *prefix, FILE *file)
530 fprintf (file, "\n%sBasic block %d ", prefix, bb->index);
532 fprintf (file, ", prev %d", bb->prev_bb->index);
534 fprintf (file, ", next %d", bb->next_bb->index);
535 fprintf (file, ", loop_depth %d, count ", bb->loop_depth);
536 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
537 fprintf (file, ", freq %i", bb->frequency);
538 if (maybe_hot_bb_p (bb))
539 fprintf (file, ", maybe hot");
540 if (probably_never_executed_bb_p (bb))
541 fprintf (file, ", probably never executed");
542 fprintf (file, ".\n");
544 fprintf (file, "%sPredecessors: ", prefix);
545 FOR_EACH_EDGE (e, ei, bb->preds)
546 dump_edge_info (file, e, 0);
548 if ((flags & TDF_DETAILS)
549 && (bb->flags & BB_RTL)
552 fprintf (file, "\n");
553 df_dump_top (bb, file);
559 fprintf (file, "\n%sSuccessors: ", prefix);
560 FOR_EACH_EDGE (e, ei, bb->succs)
561 dump_edge_info (file, e, 1);
563 if ((flags & TDF_DETAILS)
564 && (bb->flags & BB_RTL)
567 fprintf (file, "\n");
568 df_dump_bottom (bb, file);
575 /* Dump the register info to FILE. */
578 dump_reg_info (FILE *file)
580 unsigned int i, max = max_reg_num ();
581 if (reload_completed)
584 if (reg_info_p_size < max)
585 max = reg_info_p_size;
587 fprintf (file, "%d registers.\n", max);
588 for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
590 enum reg_class class, altclass;
592 if (regstat_n_sets_and_refs)
593 fprintf (file, "\nRegister %d used %d times across %d insns",
594 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
596 fprintf (file, "\nRegister %d used %d times across %d insns",
597 i, DF_REG_USE_COUNT (i) + DF_REG_DEF_COUNT (i), REG_LIVE_LENGTH (i));
599 if (REG_BASIC_BLOCK (i) >= NUM_FIXED_BLOCKS)
600 fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
601 if (regstat_n_sets_and_refs)
602 fprintf (file, "; set %d time%s", REG_N_SETS (i),
603 (REG_N_SETS (i) == 1) ? "" : "s");
605 fprintf (file, "; set %d time%s", DF_REG_DEF_COUNT (i),
606 (DF_REG_DEF_COUNT (i) == 1) ? "" : "s");
607 if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
608 fprintf (file, "; user var");
609 if (REG_N_DEATHS (i) != 1)
610 fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
611 if (REG_N_CALLS_CROSSED (i) == 1)
612 fprintf (file, "; crosses 1 call");
613 else if (REG_N_CALLS_CROSSED (i))
614 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
615 if (regno_reg_rtx[i] != NULL
616 && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
617 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
619 class = reg_preferred_class (i);
620 altclass = reg_alternate_class (i);
621 if (class != GENERAL_REGS || altclass != ALL_REGS)
623 if (altclass == ALL_REGS || class == ALL_REGS)
624 fprintf (file, "; pref %s", reg_class_names[(int) class]);
625 else if (altclass == NO_REGS)
626 fprintf (file, "; %s or none", reg_class_names[(int) class]);
628 fprintf (file, "; pref %s, else %s",
629 reg_class_names[(int) class],
630 reg_class_names[(int) altclass]);
633 if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
634 fprintf (file, "; pointer");
635 fprintf (file, ".\n");
641 dump_flow_info (FILE *file, int flags)
645 /* There are no pseudo registers after reload. Don't dump them. */
646 if (reg_info_p_size && (flags & TDF_DETAILS) != 0)
647 dump_reg_info (file);
649 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
652 dump_bb_info (bb, true, true, flags, "", file);
653 check_bb_profile (bb, file);
660 debug_flow_info (void)
662 dump_flow_info (stderr, TDF_DETAILS);
666 dump_edge_info (FILE *file, edge e, int do_succ)
668 basic_block side = (do_succ ? e->dest : e->src);
670 if (side == ENTRY_BLOCK_PTR)
671 fputs (" ENTRY", file);
672 else if (side == EXIT_BLOCK_PTR)
673 fputs (" EXIT", file);
675 fprintf (file, " %d", side->index);
678 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
682 fprintf (file, " count:");
683 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
688 static const char * const bitnames[] = {
689 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
690 "can_fallthru", "irreducible", "sibcall", "loop_exit",
691 "true", "false", "exec"
694 int i, flags = e->flags;
697 for (i = 0; flags; i++)
698 if (flags & (1 << i))
704 if (i < (int) ARRAY_SIZE (bitnames))
705 fputs (bitnames[i], file);
707 fprintf (file, "%d", i);
715 /* Simple routines to easily allocate AUX fields of basic blocks. */
717 static struct obstack block_aux_obstack;
718 static void *first_block_aux_obj = 0;
719 static struct obstack edge_aux_obstack;
720 static void *first_edge_aux_obj = 0;
722 /* Allocate a memory block of SIZE as BB->aux. The obstack must
723 be first initialized by alloc_aux_for_blocks. */
726 alloc_aux_for_block (basic_block bb, int size)
728 /* Verify that aux field is clear. */
729 gcc_assert (!bb->aux && first_block_aux_obj);
730 bb->aux = obstack_alloc (&block_aux_obstack, size);
731 memset (bb->aux, 0, size);
734 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
735 alloc_aux_for_block for each basic block. */
738 alloc_aux_for_blocks (int size)
740 static int initialized;
744 gcc_obstack_init (&block_aux_obstack);
748 /* Check whether AUX data are still allocated. */
749 gcc_assert (!first_block_aux_obj);
751 first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
756 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
757 alloc_aux_for_block (bb, size);
761 /* Clear AUX pointers of all blocks. */
764 clear_aux_for_blocks (void)
768 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
772 /* Free data allocated in block_aux_obstack and clear AUX pointers
776 free_aux_for_blocks (void)
778 gcc_assert (first_block_aux_obj);
779 obstack_free (&block_aux_obstack, first_block_aux_obj);
780 first_block_aux_obj = NULL;
782 clear_aux_for_blocks ();
785 /* Allocate a memory edge of SIZE as BB->aux. The obstack must
786 be first initialized by alloc_aux_for_edges. */
789 alloc_aux_for_edge (edge e, int size)
791 /* Verify that aux field is clear. */
792 gcc_assert (!e->aux && first_edge_aux_obj);
793 e->aux = obstack_alloc (&edge_aux_obstack, size);
794 memset (e->aux, 0, size);
797 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
798 alloc_aux_for_edge for each basic edge. */
801 alloc_aux_for_edges (int size)
803 static int initialized;
807 gcc_obstack_init (&edge_aux_obstack);
811 /* Check whether AUX data are still allocated. */
812 gcc_assert (!first_edge_aux_obj);
814 first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
819 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
824 FOR_EACH_EDGE (e, ei, bb->succs)
825 alloc_aux_for_edge (e, size);
830 /* Clear AUX pointers of all edges. */
833 clear_aux_for_edges (void)
838 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
841 FOR_EACH_EDGE (e, ei, bb->succs)
846 /* Free data allocated in edge_aux_obstack and clear AUX pointers
850 free_aux_for_edges (void)
852 gcc_assert (first_edge_aux_obj);
853 obstack_free (&edge_aux_obstack, first_edge_aux_obj);
854 first_edge_aux_obj = NULL;
856 clear_aux_for_edges ();
860 debug_bb (basic_block bb)
862 dump_bb (bb, stderr, 0);
868 basic_block bb = BASIC_BLOCK (n);
869 dump_bb (bb, stderr, 0);
873 /* Dumps cfg related information about basic block BB to FILE. */
876 dump_cfg_bb_info (FILE *file, basic_block bb)
881 static const char * const bb_bitnames[] =
883 "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock"
885 const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
888 fprintf (file, "Basic block %d", bb->index);
889 for (i = 0; i < n_bitnames; i++)
890 if (bb->flags & (1 << i))
893 fprintf (file, " (");
895 fprintf (file, ", ");
897 fprintf (file, bb_bitnames[i]);
901 fprintf (file, "\n");
903 fprintf (file, "Predecessors: ");
904 FOR_EACH_EDGE (e, ei, bb->preds)
905 dump_edge_info (file, e, 0);
907 fprintf (file, "\nSuccessors: ");
908 FOR_EACH_EDGE (e, ei, bb->succs)
909 dump_edge_info (file, e, 1);
910 fprintf (file, "\n\n");
913 /* Dumps a brief description of cfg to FILE. */
916 brief_dump_cfg (FILE *file)
922 dump_cfg_bb_info (file, bb);
926 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
927 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
928 redirected to destination of TAKEN_EDGE.
930 This function may leave the profile inconsistent in the case TAKEN_EDGE
931 frequency or count is believed to be lower than FREQUENCY or COUNT
934 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
935 gcov_type count, edge taken_edge)
945 fprintf (dump_file, "bb %i count became negative after threading",
950 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
951 Watch for overflows. */
953 prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
956 if (prob > taken_edge->probability)
959 fprintf (dump_file, "Jump threading proved probability of edge "
960 "%i->%i too small (it is %i, should be %i).\n",
961 taken_edge->src->index, taken_edge->dest->index,
962 taken_edge->probability, prob);
963 prob = taken_edge->probability;
966 /* Now rescale the probabilities. */
967 taken_edge->probability -= prob;
968 prob = REG_BR_PROB_BASE - prob;
969 bb->frequency -= edge_frequency;
970 if (bb->frequency < 0)
975 fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
976 "frequency of block should end up being 0, it is %i\n",
977 bb->index, bb->frequency);
978 EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
979 ei = ei_start (bb->succs);
981 for (; (c = ei_safe_edge (ei)); ei_next (&ei))
984 else if (prob != REG_BR_PROB_BASE)
986 int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
988 FOR_EACH_EDGE (c, ei, bb->succs)
990 c->probability = RDIV (c->probability * scale, 65536);
991 if (c->probability > REG_BR_PROB_BASE)
992 c->probability = REG_BR_PROB_BASE;
996 gcc_assert (bb == taken_edge->src);
997 taken_edge->count -= count;
998 if (taken_edge->count < 0)
1001 fprintf (dump_file, "edge %i->%i count became negative after threading",
1002 taken_edge->src->index, taken_edge->dest->index);
1003 taken_edge->count = 0;
1007 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1008 by NUM/DEN, in int arithmetic. May lose some accuracy. */
1010 scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
1017 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
1018 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
1019 and still safely fit in int during calculations. */
1025 num = RDIV (1000 * num, den);
1028 if (num > 100 * den)
1031 for (i = 0; i < nbbs; i++)
1034 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1035 /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
1036 if (bbs[i]->frequency > BB_FREQ_MAX)
1037 bbs[i]->frequency = BB_FREQ_MAX;
1038 bbs[i]->count = RDIV (bbs[i]->count * num, den);
1039 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1040 e->count = RDIV (e->count * num, den);
1044 /* numbers smaller than this value are safe to multiply without getting
1046 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
1048 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1049 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
1050 function but considerably slower. */
1052 scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
1057 gcov_type fraction = RDIV (num * 65536, den);
1059 gcc_assert (fraction >= 0);
1061 if (num < MAX_SAFE_MULTIPLIER)
1062 for (i = 0; i < nbbs; i++)
1065 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1066 if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1067 bbs[i]->count = RDIV (bbs[i]->count * num, den);
1069 bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1070 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1071 if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1072 e->count = RDIV (e->count * num, den);
1074 e->count = RDIV (e->count * fraction, 65536);
1077 for (i = 0; i < nbbs; i++)
1080 if (sizeof (gcov_type) > sizeof (int))
1081 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1083 bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
1084 bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1085 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1086 e->count = RDIV (e->count * fraction, 65536);
1090 /* Data structures used to maintain mapping between basic blocks and
1092 static htab_t bb_original;
1093 static htab_t bb_copy;
1095 /* And between loops and copies. */
1096 static htab_t loop_copy;
1097 static alloc_pool original_copy_bb_pool;
1099 struct htab_bb_copy_original_entry
1101 /* Block we are attaching info to. */
1103 /* Index of original or copy (depending on the hashtable) */
1108 bb_copy_original_hash (const void *p)
1110 const struct htab_bb_copy_original_entry *data
1111 = ((const struct htab_bb_copy_original_entry *)p);
1113 return data->index1;
1116 bb_copy_original_eq (const void *p, const void *q)
1118 const struct htab_bb_copy_original_entry *data
1119 = ((const struct htab_bb_copy_original_entry *)p);
1120 const struct htab_bb_copy_original_entry *data2
1121 = ((const struct htab_bb_copy_original_entry *)q);
1123 return data->index1 == data2->index1;
1126 /* Initialize the data structures to maintain mapping between blocks
1129 initialize_original_copy_tables (void)
1131 gcc_assert (!original_copy_bb_pool);
1132 original_copy_bb_pool
1133 = create_alloc_pool ("original_copy",
1134 sizeof (struct htab_bb_copy_original_entry), 10);
1135 bb_original = htab_create (10, bb_copy_original_hash,
1136 bb_copy_original_eq, NULL);
1137 bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1138 loop_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1141 /* Free the data structures to maintain mapping between blocks and
1144 free_original_copy_tables (void)
1146 gcc_assert (original_copy_bb_pool);
1147 htab_delete (bb_copy);
1148 htab_delete (bb_original);
1149 htab_delete (loop_copy);
1150 free_alloc_pool (original_copy_bb_pool);
1154 original_copy_bb_pool = NULL;
1157 /* Removes the value associated with OBJ from table TAB. */
1160 copy_original_table_clear (htab_t tab, unsigned obj)
1163 struct htab_bb_copy_original_entry key, *elt;
1165 if (!original_copy_bb_pool)
1169 slot = htab_find_slot (tab, &key, NO_INSERT);
1173 elt = (struct htab_bb_copy_original_entry *) *slot;
1174 htab_clear_slot (tab, slot);
1175 pool_free (original_copy_bb_pool, elt);
1178 /* Sets the value associated with OBJ in table TAB to VAL.
1179 Do nothing when data structures are not initialized. */
1182 copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
1184 struct htab_bb_copy_original_entry **slot;
1185 struct htab_bb_copy_original_entry key;
1187 if (!original_copy_bb_pool)
1191 slot = (struct htab_bb_copy_original_entry **)
1192 htab_find_slot (tab, &key, INSERT);
1195 *slot = (struct htab_bb_copy_original_entry *)
1196 pool_alloc (original_copy_bb_pool);
1197 (*slot)->index1 = obj;
1199 (*slot)->index2 = val;
1202 /* Set original for basic block. Do nothing when data structures are not
1203 initialized so passes not needing this don't need to care. */
1205 set_bb_original (basic_block bb, basic_block original)
1207 copy_original_table_set (bb_original, bb->index, original->index);
1210 /* Get the original basic block. */
1212 get_bb_original (basic_block bb)
1214 struct htab_bb_copy_original_entry *entry;
1215 struct htab_bb_copy_original_entry key;
1217 gcc_assert (original_copy_bb_pool);
1219 key.index1 = bb->index;
1220 entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
1222 return BASIC_BLOCK (entry->index2);
1227 /* Set copy for basic block. Do nothing when data structures are not
1228 initialized so passes not needing this don't need to care. */
1230 set_bb_copy (basic_block bb, basic_block copy)
1232 copy_original_table_set (bb_copy, bb->index, copy->index);
1235 /* Get the copy of basic block. */
1237 get_bb_copy (basic_block bb)
1239 struct htab_bb_copy_original_entry *entry;
1240 struct htab_bb_copy_original_entry key;
1242 gcc_assert (original_copy_bb_pool);
1244 key.index1 = bb->index;
1245 entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
1247 return BASIC_BLOCK (entry->index2);
1252 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1253 initialized so passes not needing this don't need to care. */
1256 set_loop_copy (struct loop *loop, struct loop *copy)
1259 copy_original_table_clear (loop_copy, loop->num);
1261 copy_original_table_set (loop_copy, loop->num, copy->num);
1264 /* Get the copy of LOOP. */
1267 get_loop_copy (struct loop *loop)
1269 struct htab_bb_copy_original_entry *entry;
1270 struct htab_bb_copy_original_entry key;
1272 gcc_assert (original_copy_bb_pool);
1274 key.index1 = loop->num;
1275 entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy, &key);
1277 return get_loop (entry->index2);