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, 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 3, 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 COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file contains low level functions to manipulate the CFG and
23 analyze it. All other modules should not transform the data structure
24 directly and use abstraction instead. The file is supposed to be
25 ordered bottom-up and should not contain any code dependent on a
26 particular intermediate language (RTL or trees).
28 Available functionality:
29 - Initialization/deallocation
30 init_flow, clear_edges
31 - Low level basic block manipulation
32 alloc_block, expunge_block
34 make_edge, make_single_succ_edge, cached_make_edge, remove_edge
35 - Low level edge redirection (without updating instruction chain)
36 redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
37 - Dumping and debugging
38 dump_flow_info, debug_flow_info, dump_edge_info
39 - Allocation of AUX fields for basic blocks
40 alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
42 - Consistency checking
44 - Dumping and debugging
45 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
50 #include "coretypes.h"
54 #include "hard-reg-set.h"
64 #include "tree-pass.h"
67 #include "alloc-pool.h"
69 /* The obstack on which the flow graph components are allocated. */
71 struct bitmap_obstack reg_obstack
;
73 void debug_flow_info (void);
74 static void free_edge (edge
);
76 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
78 /* Called once at initialization time. */
84 cfun
->cfg
= ggc_alloc_cleared (sizeof (struct control_flow_graph
));
86 ENTRY_BLOCK_PTR
= ggc_alloc_cleared (sizeof (struct basic_block_def
));
87 ENTRY_BLOCK_PTR
->index
= ENTRY_BLOCK
;
88 EXIT_BLOCK_PTR
= ggc_alloc_cleared (sizeof (struct basic_block_def
));
89 EXIT_BLOCK_PTR
->index
= EXIT_BLOCK
;
90 ENTRY_BLOCK_PTR
->next_bb
= EXIT_BLOCK_PTR
;
91 EXIT_BLOCK_PTR
->prev_bb
= ENTRY_BLOCK_PTR
;
94 /* Helper function for remove_edge and clear_edges. Frees edge structure
95 without actually unlinking it from the pred/succ lists. */
98 free_edge (edge e ATTRIBUTE_UNUSED
)
104 /* Free the memory associated with the edge structures. */
115 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
117 VEC_truncate (edge
, bb
->succs
, 0);
118 VEC_truncate (edge
, bb
->preds
, 0);
121 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
123 VEC_truncate (edge
, EXIT_BLOCK_PTR
->preds
, 0);
124 VEC_truncate (edge
, ENTRY_BLOCK_PTR
->succs
, 0);
126 gcc_assert (!n_edges
);
129 /* Allocate memory for basic_block. */
135 bb
= ggc_alloc_cleared (sizeof (*bb
));
139 /* Link block B to chain after AFTER. */
141 link_block (basic_block b
, basic_block after
)
143 b
->next_bb
= after
->next_bb
;
146 b
->next_bb
->prev_bb
= b
;
149 /* Unlink block B from chain. */
151 unlink_block (basic_block b
)
153 b
->next_bb
->prev_bb
= b
->prev_bb
;
154 b
->prev_bb
->next_bb
= b
->next_bb
;
159 /* Sequentially order blocks and compact the arrays. */
161 compact_blocks (void)
166 SET_BASIC_BLOCK (ENTRY_BLOCK
, ENTRY_BLOCK_PTR
);
167 SET_BASIC_BLOCK (EXIT_BLOCK
, EXIT_BLOCK_PTR
);
169 i
= NUM_FIXED_BLOCKS
;
172 SET_BASIC_BLOCK (i
, bb
);
177 gcc_assert (i
== n_basic_blocks
);
179 for (; i
< last_basic_block
; i
++)
180 SET_BASIC_BLOCK (i
, NULL
);
182 last_basic_block
= n_basic_blocks
;
185 /* Remove block B from the basic block array. */
188 expunge_block (basic_block b
)
191 SET_BASIC_BLOCK (b
->index
, NULL
);
193 /* We should be able to ggc_free here, but we are not.
194 The dead SSA_NAMES are left pointing to dead statements that are pointing
195 to dead basic blocks making garbage collector to die.
196 We should be able to release all dead SSA_NAMES and at the same time we should
197 clear out BB pointer of dead statements consistently. */
200 /* Connect E to E->src. */
205 VEC_safe_push (edge
, gc
, e
->src
->succs
, e
);
208 /* Connect E to E->dest. */
211 connect_dest (edge e
)
213 basic_block dest
= e
->dest
;
214 VEC_safe_push (edge
, gc
, dest
->preds
, e
);
215 e
->dest_idx
= EDGE_COUNT (dest
->preds
) - 1;
218 /* Disconnect edge E from E->src. */
221 disconnect_src (edge e
)
223 basic_block src
= e
->src
;
227 for (ei
= ei_start (src
->succs
); (tmp
= ei_safe_edge (ei
)); )
231 VEC_unordered_remove (edge
, src
->succs
, ei
.index
);
241 /* Disconnect edge E from E->dest. */
244 disconnect_dest (edge e
)
246 basic_block dest
= e
->dest
;
247 unsigned int dest_idx
= e
->dest_idx
;
249 VEC_unordered_remove (edge
, dest
->preds
, dest_idx
);
251 /* If we removed an edge in the middle of the edge vector, we need
252 to update dest_idx of the edge that moved into the "hole". */
253 if (dest_idx
< EDGE_COUNT (dest
->preds
))
254 EDGE_PRED (dest
, dest_idx
)->dest_idx
= dest_idx
;
257 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
258 created edge. Use this only if you are sure that this edge can't
259 possibly already exist. */
262 unchecked_make_edge (basic_block src
, basic_block dst
, int flags
)
265 e
= ggc_alloc_cleared (sizeof (*e
));
275 execute_on_growing_pred (e
);
280 /* Create an edge connecting SRC and DST with FLAGS optionally using
281 edge cache CACHE. Return the new edge, NULL if already exist. */
284 cached_make_edge (sbitmap edge_cache
, basic_block src
, basic_block dst
, int flags
)
286 if (edge_cache
== NULL
287 || src
== ENTRY_BLOCK_PTR
288 || dst
== EXIT_BLOCK_PTR
)
289 return make_edge (src
, dst
, flags
);
291 /* Does the requested edge already exist? */
292 if (! TEST_BIT (edge_cache
, dst
->index
))
294 /* The edge does not exist. Create one and update the
296 SET_BIT (edge_cache
, dst
->index
);
297 return unchecked_make_edge (src
, dst
, flags
);
300 /* At this point, we know that the requested edge exists. Adjust
301 flags if necessary. */
304 edge e
= find_edge (src
, dst
);
311 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
312 created edge or NULL if already exist. */
315 make_edge (basic_block src
, basic_block dest
, int flags
)
317 edge e
= find_edge (src
, dest
);
319 /* Make sure we don't add duplicate edges. */
326 return unchecked_make_edge (src
, dest
, flags
);
329 /* Create an edge connecting SRC to DEST and set probability by knowing
330 that it is the single edge leaving SRC. */
333 make_single_succ_edge (basic_block src
, basic_block dest
, int flags
)
335 edge e
= make_edge (src
, dest
, flags
);
337 e
->probability
= REG_BR_PROB_BASE
;
338 e
->count
= src
->count
;
342 /* This function will remove an edge from the flow graph. */
347 remove_predictions_associated_with_edge (e
);
348 execute_on_shrinking_pred (e
);
356 /* Redirect an edge's successor from one block to another. */
359 redirect_edge_succ (edge e
, basic_block new_succ
)
361 execute_on_shrinking_pred (e
);
367 /* Reconnect the edge to the new successor block. */
370 execute_on_growing_pred (e
);
373 /* Like previous but avoid possible duplicate edge. */
376 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
380 s
= find_edge (e
->src
, new_succ
);
383 s
->flags
|= e
->flags
;
384 s
->probability
+= e
->probability
;
385 if (s
->probability
> REG_BR_PROB_BASE
)
386 s
->probability
= REG_BR_PROB_BASE
;
387 s
->count
+= e
->count
;
392 redirect_edge_succ (e
, new_succ
);
397 /* Redirect an edge's predecessor from one block to another. */
400 redirect_edge_pred (edge e
, basic_block new_pred
)
406 /* Reconnect the edge to the new predecessor block. */
410 /* Clear all basic block flags, with the exception of partitioning. */
412 clear_bb_flags (void)
416 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
417 bb
->flags
= (BB_PARTITION (bb
) | (bb
->flags
& BB_DISABLE_SCHEDULE
)
418 | (bb
->flags
& BB_RTL
));
421 /* Check the consistency of profile information. We can't do that
422 in verify_flow_info, as the counts may get invalid for incompletely
423 solved graphs, later eliminating of conditionals or roundoff errors.
424 It is still practical to have them reported for debugging of simple
427 check_bb_profile (basic_block bb
, FILE * file
)
434 if (profile_status
== PROFILE_ABSENT
)
437 if (bb
!= EXIT_BLOCK_PTR
)
439 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
440 sum
+= e
->probability
;
441 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
442 fprintf (file
, "Invalid sum of outgoing probabilities %.1f%%\n",
443 sum
* 100.0 / REG_BR_PROB_BASE
);
445 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
447 if (EDGE_COUNT (bb
->succs
)
448 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
449 fprintf (file
, "Invalid sum of outgoing counts %i, should be %i\n",
450 (int) lsum
, (int) bb
->count
);
452 if (bb
!= ENTRY_BLOCK_PTR
)
455 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
456 sum
+= EDGE_FREQUENCY (e
);
457 if (abs (sum
- bb
->frequency
) > 100)
459 "Invalid sum of incoming frequencies %i, should be %i\n",
462 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
464 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
465 fprintf (file
, "Invalid sum of incoming counts %i, should be %i\n",
466 (int) lsum
, (int) bb
->count
);
470 /* Emit basic block information for BB. HEADER is true if the user wants
471 the generic information and the predecessors, FOOTER is true if they want
472 the successors. FLAGS is the dump flags of interest; TDF_DETAILS emit
473 global register liveness information. PREFIX is put in front of every
474 line. The output is emitted to FILE. */
476 dump_bb_info (basic_block bb
, bool header
, bool footer
, int flags
,
477 const char *prefix
, FILE *file
)
484 fprintf (file
, "\n%sBasic block %d ", prefix
, bb
->index
);
486 fprintf (file
, ", prev %d", bb
->prev_bb
->index
);
488 fprintf (file
, ", next %d", bb
->next_bb
->index
);
489 fprintf (file
, ", loop_depth %d, count ", bb
->loop_depth
);
490 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
491 fprintf (file
, ", freq %i", bb
->frequency
);
492 if (maybe_hot_bb_p (bb
))
493 fprintf (file
, ", maybe hot");
494 if (probably_never_executed_bb_p (bb
))
495 fprintf (file
, ", probably never executed");
496 fprintf (file
, ".\n");
498 fprintf (file
, "%sPredecessors: ", prefix
);
499 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
500 dump_edge_info (file
, e
, 0);
505 fprintf (file
, "\n%sSuccessors: ", prefix
);
506 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
507 dump_edge_info (file
, e
, 1);
510 if ((flags
& TDF_DETAILS
)
511 && (bb
->flags
& BB_RTL
))
513 if (bb
->il
.rtl
->global_live_at_start
&& header
)
515 fprintf (file
, "\n%sRegisters live at start:", prefix
);
516 dump_regset (bb
->il
.rtl
->global_live_at_start
, file
);
519 if (bb
->il
.rtl
->global_live_at_end
&& footer
)
521 fprintf (file
, "\n%sRegisters live at end:", prefix
);
522 dump_regset (bb
->il
.rtl
->global_live_at_end
, file
);
530 dump_flow_info (FILE *file
, int flags
)
534 /* There are no pseudo registers after reload. Don't dump them. */
535 if (reg_n_info
&& !reload_completed
536 && (flags
& TDF_DETAILS
) != 0)
538 unsigned int i
, max
= max_reg_num ();
539 fprintf (file
, "%d registers.\n", max
);
540 for (i
= FIRST_PSEUDO_REGISTER
; i
< max
; i
++)
543 enum reg_class
class, altclass
;
545 fprintf (file
, "\nRegister %d used %d times across %d insns",
546 i
, REG_N_REFS (i
), REG_LIVE_LENGTH (i
));
547 if (REG_BASIC_BLOCK (i
) >= 0)
548 fprintf (file
, " in block %d", REG_BASIC_BLOCK (i
));
550 fprintf (file
, "; set %d time%s", REG_N_SETS (i
),
551 (REG_N_SETS (i
) == 1) ? "" : "s");
552 if (regno_reg_rtx
[i
] != NULL
&& REG_USERVAR_P (regno_reg_rtx
[i
]))
553 fprintf (file
, "; user var");
554 if (REG_N_DEATHS (i
) != 1)
555 fprintf (file
, "; dies in %d places", REG_N_DEATHS (i
));
556 if (REG_N_CALLS_CROSSED (i
) == 1)
557 fprintf (file
, "; crosses 1 call");
558 else if (REG_N_CALLS_CROSSED (i
))
559 fprintf (file
, "; crosses %d calls", REG_N_CALLS_CROSSED (i
));
560 if (regno_reg_rtx
[i
] != NULL
561 && PSEUDO_REGNO_BYTES (i
) != UNITS_PER_WORD
)
562 fprintf (file
, "; %d bytes", PSEUDO_REGNO_BYTES (i
));
564 class = reg_preferred_class (i
);
565 altclass
= reg_alternate_class (i
);
566 if (class != GENERAL_REGS
|| altclass
!= ALL_REGS
)
568 if (altclass
== ALL_REGS
|| class == ALL_REGS
)
569 fprintf (file
, "; pref %s", reg_class_names
[(int) class]);
570 else if (altclass
== NO_REGS
)
571 fprintf (file
, "; %s or none", reg_class_names
[(int) class]);
573 fprintf (file
, "; pref %s, else %s",
574 reg_class_names
[(int) class],
575 reg_class_names
[(int) altclass
]);
578 if (regno_reg_rtx
[i
] != NULL
&& REG_POINTER (regno_reg_rtx
[i
]))
579 fprintf (file
, "; pointer");
580 fprintf (file
, ".\n");
584 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks
, n_edges
);
587 dump_bb_info (bb
, true, true, flags
, "", file
);
588 check_bb_profile (bb
, file
);
595 debug_flow_info (void)
597 dump_flow_info (stderr
, TDF_DETAILS
);
601 dump_edge_info (FILE *file
, edge e
, int do_succ
)
603 basic_block side
= (do_succ
? e
->dest
: e
->src
);
605 if (side
== ENTRY_BLOCK_PTR
)
606 fputs (" ENTRY", file
);
607 else if (side
== EXIT_BLOCK_PTR
)
608 fputs (" EXIT", file
);
610 fprintf (file
, " %d", side
->index
);
613 fprintf (file
, " [%.1f%%] ", e
->probability
* 100.0 / REG_BR_PROB_BASE
);
617 fprintf (file
, " count:");
618 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
623 static const char * const bitnames
[] = {
624 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
625 "can_fallthru", "irreducible", "sibcall", "loop_exit",
626 "true", "false", "exec"
629 int i
, flags
= e
->flags
;
632 for (i
= 0; flags
; i
++)
633 if (flags
& (1 << i
))
639 if (i
< (int) ARRAY_SIZE (bitnames
))
640 fputs (bitnames
[i
], file
);
642 fprintf (file
, "%d", i
);
650 /* Simple routines to easily allocate AUX fields of basic blocks. */
652 static struct obstack block_aux_obstack
;
653 static void *first_block_aux_obj
= 0;
654 static struct obstack edge_aux_obstack
;
655 static void *first_edge_aux_obj
= 0;
657 /* Allocate a memory block of SIZE as BB->aux. The obstack must
658 be first initialized by alloc_aux_for_blocks. */
661 alloc_aux_for_block (basic_block bb
, int size
)
663 /* Verify that aux field is clear. */
664 gcc_assert (!bb
->aux
&& first_block_aux_obj
);
665 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
666 memset (bb
->aux
, 0, size
);
669 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
670 alloc_aux_for_block for each basic block. */
673 alloc_aux_for_blocks (int size
)
675 static int initialized
;
679 gcc_obstack_init (&block_aux_obstack
);
683 /* Check whether AUX data are still allocated. */
684 gcc_assert (!first_block_aux_obj
);
686 first_block_aux_obj
= obstack_alloc (&block_aux_obstack
, 0);
691 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
692 alloc_aux_for_block (bb
, size
);
696 /* Clear AUX pointers of all blocks. */
699 clear_aux_for_blocks (void)
703 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
707 /* Free data allocated in block_aux_obstack and clear AUX pointers
711 free_aux_for_blocks (void)
713 gcc_assert (first_block_aux_obj
);
714 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
715 first_block_aux_obj
= NULL
;
717 clear_aux_for_blocks ();
720 /* Allocate a memory edge of SIZE as BB->aux. The obstack must
721 be first initialized by alloc_aux_for_edges. */
724 alloc_aux_for_edge (edge e
, int size
)
726 /* Verify that aux field is clear. */
727 gcc_assert (!e
->aux
&& first_edge_aux_obj
);
728 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
729 memset (e
->aux
, 0, size
);
732 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
733 alloc_aux_for_edge for each basic edge. */
736 alloc_aux_for_edges (int size
)
738 static int initialized
;
742 gcc_obstack_init (&edge_aux_obstack
);
746 /* Check whether AUX data are still allocated. */
747 gcc_assert (!first_edge_aux_obj
);
749 first_edge_aux_obj
= obstack_alloc (&edge_aux_obstack
, 0);
754 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
759 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
760 alloc_aux_for_edge (e
, size
);
765 /* Clear AUX pointers of all edges. */
768 clear_aux_for_edges (void)
773 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
776 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
781 /* Free data allocated in edge_aux_obstack and clear AUX pointers
785 free_aux_for_edges (void)
787 gcc_assert (first_edge_aux_obj
);
788 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
789 first_edge_aux_obj
= NULL
;
791 clear_aux_for_edges ();
795 debug_bb (basic_block bb
)
797 dump_bb (bb
, stderr
, 0);
803 basic_block bb
= BASIC_BLOCK (n
);
804 dump_bb (bb
, stderr
, 0);
808 /* Dumps cfg related information about basic block BB to FILE. */
811 dump_cfg_bb_info (FILE *file
, basic_block bb
)
816 static const char * const bb_bitnames
[] =
818 "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock"
820 const unsigned n_bitnames
= sizeof (bb_bitnames
) / sizeof (char *);
823 fprintf (file
, "Basic block %d", bb
->index
);
824 for (i
= 0; i
< n_bitnames
; i
++)
825 if (bb
->flags
& (1 << i
))
828 fprintf (file
, " (");
830 fprintf (file
, ", ");
832 fprintf (file
, bb_bitnames
[i
]);
836 fprintf (file
, "\n");
838 fprintf (file
, "Predecessors: ");
839 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
840 dump_edge_info (file
, e
, 0);
842 fprintf (file
, "\nSuccessors: ");
843 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
844 dump_edge_info (file
, e
, 1);
845 fprintf (file
, "\n\n");
848 /* Dumps a brief description of cfg to FILE. */
851 brief_dump_cfg (FILE *file
)
857 dump_cfg_bb_info (file
, bb
);
861 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
862 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
863 redirected to destination of TAKEN_EDGE.
865 This function may leave the profile inconsistent in the case TAKEN_EDGE
866 frequency or count is believed to be lower than FREQUENCY or COUNT
869 update_bb_profile_for_threading (basic_block bb
, int edge_frequency
,
870 gcov_type count
, edge taken_edge
)
880 fprintf (dump_file
, "bb %i count became negative after threading",
885 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
886 Watch for overflows. */
888 prob
= edge_frequency
* REG_BR_PROB_BASE
/ bb
->frequency
;
891 if (prob
> taken_edge
->probability
)
894 fprintf (dump_file
, "Jump threading proved probability of edge "
895 "%i->%i too small (it is %i, should be %i).\n",
896 taken_edge
->src
->index
, taken_edge
->dest
->index
,
897 taken_edge
->probability
, prob
);
898 prob
= taken_edge
->probability
;
901 /* Now rescale the probabilities. */
902 taken_edge
->probability
-= prob
;
903 prob
= REG_BR_PROB_BASE
- prob
;
904 bb
->frequency
-= edge_frequency
;
905 if (bb
->frequency
< 0)
910 fprintf (dump_file
, "Edge frequencies of bb %i has been reset, "
911 "frequency of block should end up being 0, it is %i\n",
912 bb
->index
, bb
->frequency
);
913 EDGE_SUCC (bb
, 0)->probability
= REG_BR_PROB_BASE
;
914 ei
= ei_start (bb
->succs
);
916 for (; (c
= ei_safe_edge (ei
)); ei_next (&ei
))
919 else if (prob
!= REG_BR_PROB_BASE
)
921 int scale
= RDIV (65536 * REG_BR_PROB_BASE
, prob
);
923 FOR_EACH_EDGE (c
, ei
, bb
->succs
)
925 c
->probability
= RDIV (c
->probability
* scale
, 65536);
926 if (c
->probability
> REG_BR_PROB_BASE
)
927 c
->probability
= REG_BR_PROB_BASE
;
931 gcc_assert (bb
== taken_edge
->src
);
932 taken_edge
->count
-= count
;
933 if (taken_edge
->count
< 0)
936 fprintf (dump_file
, "edge %i->%i count became negative after threading",
937 taken_edge
->src
->index
, taken_edge
->dest
->index
);
938 taken_edge
->count
= 0;
942 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
943 by NUM/DEN, in int arithmetic. May lose some accuracy. */
945 scale_bbs_frequencies_int (basic_block
*bbs
, int nbbs
, int num
, int den
)
953 /* Assume that the users are producing the fraction from frequencies
954 that never grow far enough to risk arithmetic overflow. */
955 gcc_assert (num
< 65536);
956 for (i
= 0; i
< nbbs
; i
++)
959 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
960 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
961 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
962 e
->count
= RDIV (e
->count
* num
, den
);
966 /* numbers smaller than this value are safe to multiply without getting
968 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
970 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
971 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
972 function but considerably slower. */
974 scale_bbs_frequencies_gcov_type (basic_block
*bbs
, int nbbs
, gcov_type num
,
979 gcov_type fraction
= RDIV (num
* 65536, den
);
981 gcc_assert (fraction
>= 0);
983 if (num
< MAX_SAFE_MULTIPLIER
)
984 for (i
= 0; i
< nbbs
; i
++)
987 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
988 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
989 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
991 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
992 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
993 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
994 e
->count
= RDIV (e
->count
* num
, den
);
996 e
->count
= RDIV (e
->count
* fraction
, 65536);
999 for (i
= 0; i
< nbbs
; i
++)
1002 if (sizeof (gcov_type
) > sizeof (int))
1003 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
1005 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* fraction
, 65536);
1006 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
1007 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1008 e
->count
= RDIV (e
->count
* fraction
, 65536);
1012 /* Data structures used to maintain mapping between basic blocks and
1014 static htab_t bb_original
;
1015 static htab_t bb_copy
;
1016 static alloc_pool original_copy_bb_pool
;
1018 struct htab_bb_copy_original_entry
1020 /* Block we are attaching info to. */
1022 /* Index of original or copy (depending on the hashtable) */
1027 bb_copy_original_hash (const void *p
)
1029 struct htab_bb_copy_original_entry
*data
1030 = ((struct htab_bb_copy_original_entry
*)p
);
1032 return data
->index1
;
1035 bb_copy_original_eq (const void *p
, const void *q
)
1037 struct htab_bb_copy_original_entry
*data
1038 = ((struct htab_bb_copy_original_entry
*)p
);
1039 struct htab_bb_copy_original_entry
*data2
1040 = ((struct htab_bb_copy_original_entry
*)q
);
1042 return data
->index1
== data2
->index1
;
1045 /* Initialize the data structures to maintain mapping between blocks
1048 initialize_original_copy_tables (void)
1050 gcc_assert (!original_copy_bb_pool
);
1051 original_copy_bb_pool
1052 = create_alloc_pool ("original_copy",
1053 sizeof (struct htab_bb_copy_original_entry
), 10);
1054 bb_original
= htab_create (10, bb_copy_original_hash
,
1055 bb_copy_original_eq
, NULL
);
1056 bb_copy
= htab_create (10, bb_copy_original_hash
, bb_copy_original_eq
, NULL
);
1059 /* Free the data structures to maintain mapping between blocks and
1062 free_original_copy_tables (void)
1064 gcc_assert (original_copy_bb_pool
);
1065 htab_delete (bb_copy
);
1066 htab_delete (bb_original
);
1067 free_alloc_pool (original_copy_bb_pool
);
1070 original_copy_bb_pool
= NULL
;
1073 /* Set original for basic block. Do nothing when data structures are not
1074 initialized so passes not needing this don't need to care. */
1076 set_bb_original (basic_block bb
, basic_block original
)
1078 if (original_copy_bb_pool
)
1080 struct htab_bb_copy_original_entry
**slot
;
1081 struct htab_bb_copy_original_entry key
;
1083 key
.index1
= bb
->index
;
1085 (struct htab_bb_copy_original_entry
**) htab_find_slot (bb_original
,
1088 (*slot
)->index2
= original
->index
;
1091 *slot
= pool_alloc (original_copy_bb_pool
);
1092 (*slot
)->index1
= bb
->index
;
1093 (*slot
)->index2
= original
->index
;
1098 /* Get the original basic block. */
1100 get_bb_original (basic_block bb
)
1102 struct htab_bb_copy_original_entry
*entry
;
1103 struct htab_bb_copy_original_entry key
;
1105 gcc_assert (original_copy_bb_pool
);
1107 key
.index1
= bb
->index
;
1108 entry
= (struct htab_bb_copy_original_entry
*) htab_find (bb_original
, &key
);
1110 return BASIC_BLOCK (entry
->index2
);
1115 /* Set copy for basic block. Do nothing when data structures are not
1116 initialized so passes not needing this don't need to care. */
1118 set_bb_copy (basic_block bb
, basic_block copy
)
1120 if (original_copy_bb_pool
)
1122 struct htab_bb_copy_original_entry
**slot
;
1123 struct htab_bb_copy_original_entry key
;
1125 key
.index1
= bb
->index
;
1127 (struct htab_bb_copy_original_entry
**) htab_find_slot (bb_copy
,
1130 (*slot
)->index2
= copy
->index
;
1133 *slot
= pool_alloc (original_copy_bb_pool
);
1134 (*slot
)->index1
= bb
->index
;
1135 (*slot
)->index2
= copy
->index
;
1140 /* Get the copy of 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
= (struct htab_bb_copy_original_entry
*) htab_find (bb_copy
, &key
);
1152 return BASIC_BLOCK (entry
->index2
);