Daily bump.
[official-gcc.git] / gcc / cfg.c
blobfe8dba984cf576dbf6dd28bf59d3aadddb2d6408
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 3, or (at your option) any later
11 version.
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
16 for more details.
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
33 - Edge manipulation
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
41 - clear_bb_flags
42 - Consistency checking
43 verify_flow_info
44 - Dumping and debugging
45 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
48 #include "config.h"
49 #include "system.h"
50 #include "coretypes.h"
51 #include "tm.h"
52 #include "tree.h"
53 #include "rtl.h"
54 #include "hard-reg-set.h"
55 #include "regs.h"
56 #include "flags.h"
57 #include "output.h"
58 #include "function.h"
59 #include "except.h"
60 #include "toplev.h"
61 #include "tm_p.h"
62 #include "obstack.h"
63 #include "timevar.h"
64 #include "tree-pass.h"
65 #include "ggc.h"
66 #include "hashtab.h"
67 #include "alloc-pool.h"
68 #include "df.h"
69 #include "cfgloop.h"
70 #include "tree-flow.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. */
83 void
84 init_flow (void)
86 if (!cfun->cfg)
87 cfun->cfg = GGC_CNEW (struct control_flow_graph);
88 n_edges = 0;
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. */
100 static void
101 free_edge (edge e ATTRIBUTE_UNUSED)
103 n_edges--;
104 ggc_free (e);
107 /* Free the memory associated with the edge structures. */
109 void
110 clear_edges (void)
112 basic_block bb;
113 edge e;
114 edge_iterator ei;
116 FOR_EACH_BB (bb)
118 FOR_EACH_EDGE (e, ei, bb->succs)
119 free_edge (e);
120 VEC_truncate (edge, bb->succs, 0);
121 VEC_truncate (edge, bb->preds, 0);
124 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
125 free_edge (e);
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. */
134 basic_block
135 alloc_block (void)
137 basic_block bb;
138 bb = GGC_CNEW (struct basic_block_def);
139 return bb;
142 /* Link block B to chain after AFTER. */
143 void
144 link_block (basic_block b, basic_block after)
146 b->next_bb = after->next_bb;
147 b->prev_bb = after;
148 after->next_bb = b;
149 b->next_bb->prev_bb = b;
152 /* Unlink block B from chain. */
153 void
154 unlink_block (basic_block b)
156 b->next_bb->prev_bb = b->prev_bb;
157 b->prev_bb->next_bb = b->next_bb;
158 b->prev_bb = NULL;
159 b->next_bb = NULL;
162 /* Sequentially order blocks and compact the arrays. */
163 void
164 compact_blocks (void)
166 int i;
168 SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
169 SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
171 if (df)
172 df_compact_blocks ();
173 else
175 basic_block bb;
177 i = NUM_FIXED_BLOCKS;
178 FOR_EACH_BB (bb)
180 SET_BASIC_BLOCK (i, bb);
181 bb->index = i;
182 i++;
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. */
194 void
195 expunge_block (basic_block b)
197 unlink_block (b);
198 SET_BASIC_BLOCK (b->index, NULL);
199 n_basic_blocks--;
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. */
209 static inline void
210 connect_src (edge e)
212 VEC_safe_push (edge, gc, e->src->succs, e);
213 df_mark_solutions_dirty ();
216 /* Connect E to E->dest. */
218 static inline void
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. */
229 static inline void
230 disconnect_src (edge e)
232 basic_block src = e->src;
233 edge_iterator ei;
234 edge tmp;
236 for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
238 if (tmp == e)
240 VEC_unordered_remove (edge, src->succs, ei.index);
241 return;
243 else
244 ei_next (&ei);
247 df_mark_solutions_dirty ();
248 gcc_unreachable ();
251 /* Disconnect edge E from E->dest. */
253 static inline void
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. */
272 edge
273 unchecked_make_edge (basic_block src, basic_block dst, int flags)
275 edge e;
276 e = GGC_CNEW (struct edge_def);
277 n_edges++;
279 e->src = src;
280 e->dest = dst;
281 e->flags = flags;
283 connect_src (e);
284 connect_dest (e);
286 execute_on_growing_pred (e);
287 return 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. */
293 edge
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
305 cache. */
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. */
312 if (flags)
314 edge e = find_edge (src, dst);
315 e->flags |= flags;
318 return NULL;
321 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
322 created edge or NULL if already exist. */
324 edge
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. */
330 if (e)
332 e->flags |= flags;
333 return NULL;
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. */
342 edge
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;
349 return e;
352 /* This function will remove an edge from the flow graph. */
354 void
355 remove_edge_raw (edge e)
357 remove_predictions_associated_with_edge (e);
358 execute_on_shrinking_pred (e);
360 disconnect_src (e);
361 disconnect_dest (e);
363 /* This is probably not needed, but it doesn't hurt. */
364 redirect_edge_var_map_clear (e);
366 free_edge (e);
369 /* Redirect an edge's successor from one block to another. */
371 void
372 redirect_edge_succ (edge e, basic_block new_succ)
374 execute_on_shrinking_pred (e);
376 disconnect_dest (e);
378 e->dest = new_succ;
380 /* Reconnect the edge to the new successor block. */
381 connect_dest (e);
383 execute_on_growing_pred (e);
386 /* Like previous but avoid possible duplicate edge. */
388 edge
389 redirect_edge_succ_nodup (edge e, basic_block new_succ)
391 edge s;
393 s = find_edge (e->src, new_succ);
394 if (s && s != e)
396 s->flags |= e->flags;
397 s->probability += e->probability;
398 if (s->probability > REG_BR_PROB_BASE)
399 s->probability = REG_BR_PROB_BASE;
400 s->count += e->count;
401 remove_edge (e);
402 redirect_edge_var_map_dup (s, e);
403 e = s;
405 else
406 redirect_edge_succ (e, new_succ);
408 return e;
411 /* Redirect an edge's predecessor from one block to another. */
413 void
414 redirect_edge_pred (edge e, basic_block new_pred)
416 disconnect_src (e);
418 e->src = new_pred;
420 /* Reconnect the edge to the new predecessor block. */
421 connect_src (e);
424 /* Clear all basic block flags, with the exception of partitioning and
425 setjmp_target. */
426 void
427 clear_bb_flags (void)
429 basic_block bb;
431 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
432 bb->flags = (BB_PARTITION (bb)
433 | (bb->flags & (BB_DISABLE_SCHEDULE + BB_RTL + BB_NON_LOCAL_GOTO_TARGET)));
436 /* Check the consistency of profile information. We can't do that
437 in verify_flow_info, as the counts may get invalid for incompletely
438 solved graphs, later eliminating of conditionals or roundoff errors.
439 It is still practical to have them reported for debugging of simple
440 testcases. */
441 void
442 check_bb_profile (basic_block bb, FILE * file)
444 edge e;
445 int sum = 0;
446 gcov_type lsum;
447 edge_iterator ei;
449 if (profile_status == PROFILE_ABSENT)
450 return;
452 if (bb != EXIT_BLOCK_PTR)
454 FOR_EACH_EDGE (e, ei, bb->succs)
455 sum += e->probability;
456 if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
457 fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
458 sum * 100.0 / REG_BR_PROB_BASE);
459 lsum = 0;
460 FOR_EACH_EDGE (e, ei, bb->succs)
461 lsum += e->count;
462 if (EDGE_COUNT (bb->succs)
463 && (lsum - bb->count > 100 || lsum - bb->count < -100))
464 fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n",
465 (int) lsum, (int) bb->count);
467 if (bb != ENTRY_BLOCK_PTR)
469 sum = 0;
470 FOR_EACH_EDGE (e, ei, bb->preds)
471 sum += EDGE_FREQUENCY (e);
472 if (abs (sum - bb->frequency) > 100)
473 fprintf (file,
474 "Invalid sum of incoming frequencies %i, should be %i\n",
475 sum, bb->frequency);
476 lsum = 0;
477 FOR_EACH_EDGE (e, ei, bb->preds)
478 lsum += e->count;
479 if (lsum - bb->count > 100 || lsum - bb->count < -100)
480 fprintf (file, "Invalid sum of incoming counts %i, should be %i\n",
481 (int) lsum, (int) bb->count);
485 /* Write information about registers and basic blocks into FILE.
486 This is part of making a debugging dump. */
488 void
489 dump_regset (regset r, FILE *outf)
491 unsigned i;
492 reg_set_iterator rsi;
494 if (r == NULL)
496 fputs (" (nil)", outf);
497 return;
500 EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi)
502 fprintf (outf, " %d", i);
503 if (i < FIRST_PSEUDO_REGISTER)
504 fprintf (outf, " [%s]",
505 reg_names[i]);
509 /* Print a human-readable representation of R on the standard error
510 stream. This function is designed to be used from within the
511 debugger. */
513 void
514 debug_regset (regset r)
516 dump_regset (r, stderr);
517 putc ('\n', stderr);
520 /* Emit basic block information for BB. HEADER is true if the user wants
521 the generic information and the predecessors, FOOTER is true if they want
522 the successors. FLAGS is the dump flags of interest; TDF_DETAILS emit
523 global register liveness information. PREFIX is put in front of every
524 line. The output is emitted to FILE. */
525 void
526 dump_bb_info (basic_block bb, bool header, bool footer, int flags,
527 const char *prefix, FILE *file)
529 edge e;
530 edge_iterator ei;
532 if (header)
534 fprintf (file, "\n%sBasic block %d ", prefix, bb->index);
535 if (bb->prev_bb)
536 fprintf (file, ", prev %d", bb->prev_bb->index);
537 if (bb->next_bb)
538 fprintf (file, ", next %d", bb->next_bb->index);
539 fprintf (file, ", loop_depth %d, count ", bb->loop_depth);
540 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
541 fprintf (file, ", freq %i", bb->frequency);
542 /* Both maybe_hot_bb_p & probably_never_executed_bb_p functions
543 crash without cfun. */
544 if (cfun && maybe_hot_bb_p (bb))
545 fprintf (file, ", maybe hot");
546 if (cfun && probably_never_executed_bb_p (bb))
547 fprintf (file, ", probably never executed");
548 fprintf (file, ".\n");
550 fprintf (file, "%sPredecessors: ", prefix);
551 FOR_EACH_EDGE (e, ei, bb->preds)
552 dump_edge_info (file, e, 0);
554 if ((flags & TDF_DETAILS)
555 && (bb->flags & BB_RTL)
556 && df)
558 fprintf (file, "\n");
559 df_dump_top (bb, file);
563 if (footer)
565 fprintf (file, "\n%sSuccessors: ", prefix);
566 FOR_EACH_EDGE (e, ei, bb->succs)
567 dump_edge_info (file, e, 1);
569 if ((flags & TDF_DETAILS)
570 && (bb->flags & BB_RTL)
571 && df)
573 fprintf (file, "\n");
574 df_dump_bottom (bb, file);
578 putc ('\n', file);
581 /* Dump the register info to FILE. */
583 void
584 dump_reg_info (FILE *file)
586 unsigned int i, max = max_reg_num ();
587 if (reload_completed)
588 return;
590 if (reg_info_p_size < max)
591 max = reg_info_p_size;
593 fprintf (file, "%d registers.\n", max);
594 for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
596 enum reg_class class, altclass;
598 if (regstat_n_sets_and_refs)
599 fprintf (file, "\nRegister %d used %d times across %d insns",
600 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
601 else if (df)
602 fprintf (file, "\nRegister %d used %d times across %d insns",
603 i, DF_REG_USE_COUNT (i) + DF_REG_DEF_COUNT (i), REG_LIVE_LENGTH (i));
605 if (REG_BASIC_BLOCK (i) >= NUM_FIXED_BLOCKS)
606 fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
607 if (regstat_n_sets_and_refs)
608 fprintf (file, "; set %d time%s", REG_N_SETS (i),
609 (REG_N_SETS (i) == 1) ? "" : "s");
610 else if (df)
611 fprintf (file, "; set %d time%s", DF_REG_DEF_COUNT (i),
612 (DF_REG_DEF_COUNT (i) == 1) ? "" : "s");
613 if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
614 fprintf (file, "; user var");
615 if (REG_N_DEATHS (i) != 1)
616 fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
617 if (REG_N_CALLS_CROSSED (i) == 1)
618 fprintf (file, "; crosses 1 call");
619 else if (REG_N_CALLS_CROSSED (i))
620 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
621 if (REG_FREQ_CALLS_CROSSED (i))
622 fprintf (file, "; crosses call with %d frequency", REG_FREQ_CALLS_CROSSED (i));
623 if (regno_reg_rtx[i] != NULL
624 && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
625 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
627 class = reg_preferred_class (i);
628 altclass = reg_alternate_class (i);
629 if (class != GENERAL_REGS || altclass != ALL_REGS)
631 if (altclass == ALL_REGS || class == ALL_REGS)
632 fprintf (file, "; pref %s", reg_class_names[(int) class]);
633 else if (altclass == NO_REGS)
634 fprintf (file, "; %s or none", reg_class_names[(int) class]);
635 else
636 fprintf (file, "; pref %s, else %s",
637 reg_class_names[(int) class],
638 reg_class_names[(int) altclass]);
641 if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
642 fprintf (file, "; pointer");
643 fprintf (file, ".\n");
648 void
649 dump_flow_info (FILE *file, int flags)
651 basic_block bb;
653 /* There are no pseudo registers after reload. Don't dump them. */
654 if (reg_info_p_size && (flags & TDF_DETAILS) != 0)
655 dump_reg_info (file);
657 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
658 FOR_ALL_BB (bb)
660 dump_bb_info (bb, true, true, flags, "", file);
661 check_bb_profile (bb, file);
664 putc ('\n', file);
667 void
668 debug_flow_info (void)
670 dump_flow_info (stderr, TDF_DETAILS);
673 void
674 dump_edge_info (FILE *file, edge e, int do_succ)
676 basic_block side = (do_succ ? e->dest : e->src);
677 /* both ENTRY_BLOCK_PTR & EXIT_BLOCK_PTR depend upon cfun. */
678 if (cfun && side == ENTRY_BLOCK_PTR)
679 fputs (" ENTRY", file);
680 else if (cfun && side == EXIT_BLOCK_PTR)
681 fputs (" EXIT", file);
682 else
683 fprintf (file, " %d", side->index);
685 if (e->probability)
686 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
688 if (e->count)
690 fprintf (file, " count:");
691 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
694 if (e->flags)
696 static const char * const bitnames[] = {
697 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
698 "can_fallthru", "irreducible", "sibcall", "loop_exit",
699 "true", "false", "exec"
701 int comma = 0;
702 int i, flags = e->flags;
704 fputs (" (", file);
705 for (i = 0; flags; i++)
706 if (flags & (1 << i))
708 flags &= ~(1 << i);
710 if (comma)
711 fputc (',', file);
712 if (i < (int) ARRAY_SIZE (bitnames))
713 fputs (bitnames[i], file);
714 else
715 fprintf (file, "%d", i);
716 comma = 1;
719 fputc (')', file);
723 /* Simple routines to easily allocate AUX fields of basic blocks. */
725 static struct obstack block_aux_obstack;
726 static void *first_block_aux_obj = 0;
727 static struct obstack edge_aux_obstack;
728 static void *first_edge_aux_obj = 0;
730 /* Allocate a memory block of SIZE as BB->aux. The obstack must
731 be first initialized by alloc_aux_for_blocks. */
733 inline void
734 alloc_aux_for_block (basic_block bb, int size)
736 /* Verify that aux field is clear. */
737 gcc_assert (!bb->aux && first_block_aux_obj);
738 bb->aux = obstack_alloc (&block_aux_obstack, size);
739 memset (bb->aux, 0, size);
742 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
743 alloc_aux_for_block for each basic block. */
745 void
746 alloc_aux_for_blocks (int size)
748 static int initialized;
750 if (!initialized)
752 gcc_obstack_init (&block_aux_obstack);
753 initialized = 1;
755 else
756 /* Check whether AUX data are still allocated. */
757 gcc_assert (!first_block_aux_obj);
759 first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
760 if (size)
762 basic_block bb;
764 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
765 alloc_aux_for_block (bb, size);
769 /* Clear AUX pointers of all blocks. */
771 void
772 clear_aux_for_blocks (void)
774 basic_block bb;
776 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
777 bb->aux = NULL;
780 /* Free data allocated in block_aux_obstack and clear AUX pointers
781 of all blocks. */
783 void
784 free_aux_for_blocks (void)
786 gcc_assert (first_block_aux_obj);
787 obstack_free (&block_aux_obstack, first_block_aux_obj);
788 first_block_aux_obj = NULL;
790 clear_aux_for_blocks ();
793 /* Allocate a memory edge of SIZE as BB->aux. The obstack must
794 be first initialized by alloc_aux_for_edges. */
796 inline void
797 alloc_aux_for_edge (edge e, int size)
799 /* Verify that aux field is clear. */
800 gcc_assert (!e->aux && first_edge_aux_obj);
801 e->aux = obstack_alloc (&edge_aux_obstack, size);
802 memset (e->aux, 0, size);
805 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
806 alloc_aux_for_edge for each basic edge. */
808 void
809 alloc_aux_for_edges (int size)
811 static int initialized;
813 if (!initialized)
815 gcc_obstack_init (&edge_aux_obstack);
816 initialized = 1;
818 else
819 /* Check whether AUX data are still allocated. */
820 gcc_assert (!first_edge_aux_obj);
822 first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
823 if (size)
825 basic_block bb;
827 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
829 edge e;
830 edge_iterator ei;
832 FOR_EACH_EDGE (e, ei, bb->succs)
833 alloc_aux_for_edge (e, size);
838 /* Clear AUX pointers of all edges. */
840 void
841 clear_aux_for_edges (void)
843 basic_block bb;
844 edge e;
846 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
848 edge_iterator ei;
849 FOR_EACH_EDGE (e, ei, bb->succs)
850 e->aux = NULL;
854 /* Free data allocated in edge_aux_obstack and clear AUX pointers
855 of all edges. */
857 void
858 free_aux_for_edges (void)
860 gcc_assert (first_edge_aux_obj);
861 obstack_free (&edge_aux_obstack, first_edge_aux_obj);
862 first_edge_aux_obj = NULL;
864 clear_aux_for_edges ();
867 void
868 debug_bb (basic_block bb)
870 dump_bb (bb, stderr, 0);
873 basic_block
874 debug_bb_n (int n)
876 basic_block bb = BASIC_BLOCK (n);
877 dump_bb (bb, stderr, 0);
878 return bb;
881 /* Dumps cfg related information about basic block BB to FILE. */
883 static void
884 dump_cfg_bb_info (FILE *file, basic_block bb)
886 unsigned i;
887 edge_iterator ei;
888 bool first = true;
889 static const char * const bb_bitnames[] =
891 "new", "reachable", "irreducible_loop", "superblock",
892 "nosched", "hot", "cold", "dup", "xlabel", "rtl",
893 "fwdr", "nothrd"
895 const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
896 edge e;
898 fprintf (file, "Basic block %d", bb->index);
899 for (i = 0; i < n_bitnames; i++)
900 if (bb->flags & (1 << i))
902 if (first)
903 fprintf (file, " (");
904 else
905 fprintf (file, ", ");
906 first = false;
907 fprintf (file, bb_bitnames[i]);
909 if (!first)
910 fprintf (file, ")");
911 fprintf (file, "\n");
913 fprintf (file, "Predecessors: ");
914 FOR_EACH_EDGE (e, ei, bb->preds)
915 dump_edge_info (file, e, 0);
917 fprintf (file, "\nSuccessors: ");
918 FOR_EACH_EDGE (e, ei, bb->succs)
919 dump_edge_info (file, e, 1);
920 fprintf (file, "\n\n");
923 /* Dumps a brief description of cfg to FILE. */
925 void
926 brief_dump_cfg (FILE *file)
928 basic_block bb;
930 FOR_EACH_BB (bb)
932 dump_cfg_bb_info (file, bb);
936 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
937 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
938 redirected to destination of TAKEN_EDGE.
940 This function may leave the profile inconsistent in the case TAKEN_EDGE
941 frequency or count is believed to be lower than FREQUENCY or COUNT
942 respectively. */
943 void
944 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
945 gcov_type count, edge taken_edge)
947 edge c;
948 int prob;
949 edge_iterator ei;
951 bb->count -= count;
952 if (bb->count < 0)
954 if (dump_file)
955 fprintf (dump_file, "bb %i count became negative after threading",
956 bb->index);
957 bb->count = 0;
960 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
961 Watch for overflows. */
962 if (bb->frequency)
963 prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
964 else
965 prob = 0;
966 if (prob > taken_edge->probability)
968 if (dump_file)
969 fprintf (dump_file, "Jump threading proved probability of edge "
970 "%i->%i too small (it is %i, should be %i).\n",
971 taken_edge->src->index, taken_edge->dest->index,
972 taken_edge->probability, prob);
973 prob = taken_edge->probability;
976 /* Now rescale the probabilities. */
977 taken_edge->probability -= prob;
978 prob = REG_BR_PROB_BASE - prob;
979 bb->frequency -= edge_frequency;
980 if (bb->frequency < 0)
981 bb->frequency = 0;
982 if (prob <= 0)
984 if (dump_file)
985 fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
986 "frequency of block should end up being 0, it is %i\n",
987 bb->index, bb->frequency);
988 EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
989 ei = ei_start (bb->succs);
990 ei_next (&ei);
991 for (; (c = ei_safe_edge (ei)); ei_next (&ei))
992 c->probability = 0;
994 else if (prob != REG_BR_PROB_BASE)
996 int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
998 FOR_EACH_EDGE (c, ei, bb->succs)
1000 /* Protect from overflow due to additional scaling. */
1001 if (c->probability > prob)
1002 c->probability = REG_BR_PROB_BASE;
1003 else
1005 c->probability = RDIV (c->probability * scale, 65536);
1006 if (c->probability > REG_BR_PROB_BASE)
1007 c->probability = REG_BR_PROB_BASE;
1012 gcc_assert (bb == taken_edge->src);
1013 taken_edge->count -= count;
1014 if (taken_edge->count < 0)
1016 if (dump_file)
1017 fprintf (dump_file, "edge %i->%i count became negative after threading",
1018 taken_edge->src->index, taken_edge->dest->index);
1019 taken_edge->count = 0;
1023 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1024 by NUM/DEN, in int arithmetic. May lose some accuracy. */
1025 void
1026 scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
1028 int i;
1029 edge e;
1030 if (num < 0)
1031 num = 0;
1033 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
1034 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
1035 and still safely fit in int during calculations. */
1036 if (den > 1000)
1038 if (num > 1000000)
1039 return;
1041 num = RDIV (1000 * num, den);
1042 den = 1000;
1044 if (num > 100 * den)
1045 return;
1047 for (i = 0; i < nbbs; i++)
1049 edge_iterator ei;
1050 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1051 /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
1052 if (bbs[i]->frequency > BB_FREQ_MAX)
1053 bbs[i]->frequency = BB_FREQ_MAX;
1054 bbs[i]->count = RDIV (bbs[i]->count * num, den);
1055 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1056 e->count = RDIV (e->count * num, den);
1060 /* numbers smaller than this value are safe to multiply without getting
1061 64bit overflow. */
1062 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
1064 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1065 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
1066 function but considerably slower. */
1067 void
1068 scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
1069 gcov_type den)
1071 int i;
1072 edge e;
1073 gcov_type fraction = RDIV (num * 65536, den);
1075 gcc_assert (fraction >= 0);
1077 if (num < MAX_SAFE_MULTIPLIER)
1078 for (i = 0; i < nbbs; i++)
1080 edge_iterator ei;
1081 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1082 if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1083 bbs[i]->count = RDIV (bbs[i]->count * num, den);
1084 else
1085 bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1086 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1087 if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1088 e->count = RDIV (e->count * num, den);
1089 else
1090 e->count = RDIV (e->count * fraction, 65536);
1092 else
1093 for (i = 0; i < nbbs; i++)
1095 edge_iterator ei;
1096 if (sizeof (gcov_type) > sizeof (int))
1097 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1098 else
1099 bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
1100 bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1101 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1102 e->count = RDIV (e->count * fraction, 65536);
1106 /* Data structures used to maintain mapping between basic blocks and
1107 copies. */
1108 static htab_t bb_original;
1109 static htab_t bb_copy;
1111 /* And between loops and copies. */
1112 static htab_t loop_copy;
1113 static alloc_pool original_copy_bb_pool;
1115 struct htab_bb_copy_original_entry
1117 /* Block we are attaching info to. */
1118 int index1;
1119 /* Index of original or copy (depending on the hashtable) */
1120 int index2;
1123 static hashval_t
1124 bb_copy_original_hash (const void *p)
1126 const struct htab_bb_copy_original_entry *data
1127 = ((const struct htab_bb_copy_original_entry *)p);
1129 return data->index1;
1131 static int
1132 bb_copy_original_eq (const void *p, const void *q)
1134 const struct htab_bb_copy_original_entry *data
1135 = ((const struct htab_bb_copy_original_entry *)p);
1136 const struct htab_bb_copy_original_entry *data2
1137 = ((const struct htab_bb_copy_original_entry *)q);
1139 return data->index1 == data2->index1;
1142 /* Initialize the data structures to maintain mapping between blocks
1143 and its copies. */
1144 void
1145 initialize_original_copy_tables (void)
1147 gcc_assert (!original_copy_bb_pool);
1148 original_copy_bb_pool
1149 = create_alloc_pool ("original_copy",
1150 sizeof (struct htab_bb_copy_original_entry), 10);
1151 bb_original = htab_create (10, bb_copy_original_hash,
1152 bb_copy_original_eq, NULL);
1153 bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1154 loop_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1157 /* Free the data structures to maintain mapping between blocks and
1158 its copies. */
1159 void
1160 free_original_copy_tables (void)
1162 gcc_assert (original_copy_bb_pool);
1163 htab_delete (bb_copy);
1164 htab_delete (bb_original);
1165 htab_delete (loop_copy);
1166 free_alloc_pool (original_copy_bb_pool);
1167 bb_copy = NULL;
1168 bb_original = NULL;
1169 loop_copy = NULL;
1170 original_copy_bb_pool = NULL;
1173 /* Removes the value associated with OBJ from table TAB. */
1175 static void
1176 copy_original_table_clear (htab_t tab, unsigned obj)
1178 void **slot;
1179 struct htab_bb_copy_original_entry key, *elt;
1181 if (!original_copy_bb_pool)
1182 return;
1184 key.index1 = obj;
1185 slot = htab_find_slot (tab, &key, NO_INSERT);
1186 if (!slot)
1187 return;
1189 elt = (struct htab_bb_copy_original_entry *) *slot;
1190 htab_clear_slot (tab, slot);
1191 pool_free (original_copy_bb_pool, elt);
1194 /* Sets the value associated with OBJ in table TAB to VAL.
1195 Do nothing when data structures are not initialized. */
1197 static void
1198 copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
1200 struct htab_bb_copy_original_entry **slot;
1201 struct htab_bb_copy_original_entry key;
1203 if (!original_copy_bb_pool)
1204 return;
1206 key.index1 = obj;
1207 slot = (struct htab_bb_copy_original_entry **)
1208 htab_find_slot (tab, &key, INSERT);
1209 if (!*slot)
1211 *slot = (struct htab_bb_copy_original_entry *)
1212 pool_alloc (original_copy_bb_pool);
1213 (*slot)->index1 = obj;
1215 (*slot)->index2 = val;
1218 /* Set original for basic block. Do nothing when data structures are not
1219 initialized so passes not needing this don't need to care. */
1220 void
1221 set_bb_original (basic_block bb, basic_block original)
1223 copy_original_table_set (bb_original, bb->index, original->index);
1226 /* Get the original basic block. */
1227 basic_block
1228 get_bb_original (basic_block bb)
1230 struct htab_bb_copy_original_entry *entry;
1231 struct htab_bb_copy_original_entry key;
1233 gcc_assert (original_copy_bb_pool);
1235 key.index1 = bb->index;
1236 entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
1237 if (entry)
1238 return BASIC_BLOCK (entry->index2);
1239 else
1240 return NULL;
1243 /* Set copy for basic block. Do nothing when data structures are not
1244 initialized so passes not needing this don't need to care. */
1245 void
1246 set_bb_copy (basic_block bb, basic_block copy)
1248 copy_original_table_set (bb_copy, bb->index, copy->index);
1251 /* Get the copy of basic block. */
1252 basic_block
1253 get_bb_copy (basic_block bb)
1255 struct htab_bb_copy_original_entry *entry;
1256 struct htab_bb_copy_original_entry key;
1258 gcc_assert (original_copy_bb_pool);
1260 key.index1 = bb->index;
1261 entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
1262 if (entry)
1263 return BASIC_BLOCK (entry->index2);
1264 else
1265 return NULL;
1268 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1269 initialized so passes not needing this don't need to care. */
1271 void
1272 set_loop_copy (struct loop *loop, struct loop *copy)
1274 if (!copy)
1275 copy_original_table_clear (loop_copy, loop->num);
1276 else
1277 copy_original_table_set (loop_copy, loop->num, copy->num);
1280 /* Get the copy of LOOP. */
1282 struct loop *
1283 get_loop_copy (struct loop *loop)
1285 struct htab_bb_copy_original_entry *entry;
1286 struct htab_bb_copy_original_entry key;
1288 gcc_assert (original_copy_bb_pool);
1290 key.index1 = loop->num;
1291 entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy, &key);
1292 if (entry)
1293 return get_loop (entry->index2);
1294 else
1295 return NULL;