2008-07-06 Kai Tietz <kai.tietz@onevision.com>
[official-gcc.git] / gcc / cfg.c
blobe8bf789480bf9129745428e0a2aed8c917f535a3
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 (struct function *the_fun)
86 if (!the_fun->cfg)
87 the_fun->cfg = GGC_CNEW (struct control_flow_graph);
88 n_edges_for_function (the_fun) = 0;
89 ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)
90 = GGC_CNEW (struct basic_block_def);
91 ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = ENTRY_BLOCK;
92 EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)
93 = GGC_CNEW (struct basic_block_def);
94 EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = EXIT_BLOCK;
95 ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->next_bb
96 = EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun);
97 EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)->prev_bb
98 = ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun);
101 /* Helper function for remove_edge and clear_edges. Frees edge structure
102 without actually unlinking it from the pred/succ lists. */
104 static void
105 free_edge (edge e ATTRIBUTE_UNUSED)
107 n_edges--;
108 ggc_free (e);
111 /* Free the memory associated with the edge structures. */
113 void
114 clear_edges (void)
116 basic_block bb;
117 edge e;
118 edge_iterator ei;
120 FOR_EACH_BB (bb)
122 FOR_EACH_EDGE (e, ei, bb->succs)
123 free_edge (e);
124 VEC_truncate (edge, bb->succs, 0);
125 VEC_truncate (edge, bb->preds, 0);
128 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
129 free_edge (e);
130 VEC_truncate (edge, EXIT_BLOCK_PTR->preds, 0);
131 VEC_truncate (edge, ENTRY_BLOCK_PTR->succs, 0);
133 gcc_assert (!n_edges);
136 /* Allocate memory for basic_block. */
138 basic_block
139 alloc_block (void)
141 basic_block bb;
142 bb = GGC_CNEW (struct basic_block_def);
143 return bb;
146 /* Link block B to chain after AFTER. */
147 void
148 link_block (basic_block b, basic_block after)
150 b->next_bb = after->next_bb;
151 b->prev_bb = after;
152 after->next_bb = b;
153 b->next_bb->prev_bb = b;
156 /* Unlink block B from chain. */
157 void
158 unlink_block (basic_block b)
160 b->next_bb->prev_bb = b->prev_bb;
161 b->prev_bb->next_bb = b->next_bb;
162 b->prev_bb = NULL;
163 b->next_bb = NULL;
166 /* Sequentially order blocks and compact the arrays. */
167 void
168 compact_blocks (void)
170 int i;
172 SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
173 SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
175 if (df)
176 df_compact_blocks ();
177 else
179 basic_block bb;
181 i = NUM_FIXED_BLOCKS;
182 FOR_EACH_BB (bb)
184 SET_BASIC_BLOCK (i, bb);
185 bb->index = i;
186 i++;
188 gcc_assert (i == n_basic_blocks);
190 for (; i < last_basic_block; i++)
191 SET_BASIC_BLOCK (i, NULL);
193 last_basic_block = n_basic_blocks;
196 /* Remove block B from the basic block array. */
198 void
199 expunge_block (basic_block b)
201 unlink_block (b);
202 SET_BASIC_BLOCK (b->index, NULL);
203 n_basic_blocks--;
204 /* We should be able to ggc_free here, but we are not.
205 The dead SSA_NAMES are left pointing to dead statements that are pointing
206 to dead basic blocks making garbage collector to die.
207 We should be able to release all dead SSA_NAMES and at the same time we should
208 clear out BB pointer of dead statements consistently. */
211 /* Connect E to E->src. */
213 static inline void
214 connect_src (edge e)
216 VEC_safe_push (edge, gc, e->src->succs, e);
217 df_mark_solutions_dirty ();
220 /* Connect E to E->dest. */
222 static inline void
223 connect_dest (edge e)
225 basic_block dest = e->dest;
226 VEC_safe_push (edge, gc, dest->preds, e);
227 e->dest_idx = EDGE_COUNT (dest->preds) - 1;
228 df_mark_solutions_dirty ();
231 /* Disconnect edge E from E->src. */
233 static inline void
234 disconnect_src (edge e)
236 basic_block src = e->src;
237 edge_iterator ei;
238 edge tmp;
240 for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
242 if (tmp == e)
244 VEC_unordered_remove (edge, src->succs, ei.index);
245 return;
247 else
248 ei_next (&ei);
251 df_mark_solutions_dirty ();
252 gcc_unreachable ();
255 /* Disconnect edge E from E->dest. */
257 static inline void
258 disconnect_dest (edge e)
260 basic_block dest = e->dest;
261 unsigned int dest_idx = e->dest_idx;
263 VEC_unordered_remove (edge, dest->preds, dest_idx);
265 /* If we removed an edge in the middle of the edge vector, we need
266 to update dest_idx of the edge that moved into the "hole". */
267 if (dest_idx < EDGE_COUNT (dest->preds))
268 EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
269 df_mark_solutions_dirty ();
272 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
273 created edge. Use this only if you are sure that this edge can't
274 possibly already exist. */
276 edge
277 unchecked_make_edge (basic_block src, basic_block dst, int flags)
279 edge e;
280 e = GGC_CNEW (struct edge_def);
281 n_edges++;
283 e->src = src;
284 e->dest = dst;
285 e->flags = flags;
287 connect_src (e);
288 connect_dest (e);
290 execute_on_growing_pred (e);
291 return e;
294 /* Create an edge connecting SRC and DST with FLAGS optionally using
295 edge cache CACHE. Return the new edge, NULL if already exist. */
297 edge
298 cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
300 if (edge_cache == NULL
301 || src == ENTRY_BLOCK_PTR
302 || dst == EXIT_BLOCK_PTR)
303 return make_edge (src, dst, flags);
305 /* Does the requested edge already exist? */
306 if (! TEST_BIT (edge_cache, dst->index))
308 /* The edge does not exist. Create one and update the
309 cache. */
310 SET_BIT (edge_cache, dst->index);
311 return unchecked_make_edge (src, dst, flags);
314 /* At this point, we know that the requested edge exists. Adjust
315 flags if necessary. */
316 if (flags)
318 edge e = find_edge (src, dst);
319 e->flags |= flags;
322 return NULL;
325 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
326 created edge or NULL if already exist. */
328 edge
329 make_edge (basic_block src, basic_block dest, int flags)
331 edge e = find_edge (src, dest);
333 /* Make sure we don't add duplicate edges. */
334 if (e)
336 e->flags |= flags;
337 return NULL;
340 return unchecked_make_edge (src, dest, flags);
343 /* Create an edge connecting SRC to DEST and set probability by knowing
344 that it is the single edge leaving SRC. */
346 edge
347 make_single_succ_edge (basic_block src, basic_block dest, int flags)
349 edge e = make_edge (src, dest, flags);
351 e->probability = REG_BR_PROB_BASE;
352 e->count = src->count;
353 return e;
356 /* This function will remove an edge from the flow graph. */
358 void
359 remove_edge_raw (edge e)
361 remove_predictions_associated_with_edge (e);
362 execute_on_shrinking_pred (e);
364 disconnect_src (e);
365 disconnect_dest (e);
367 /* This is probably not needed, but it doesn't hurt. */
368 redirect_edge_var_map_clear (e);
370 free_edge (e);
373 /* Redirect an edge's successor from one block to another. */
375 void
376 redirect_edge_succ (edge e, basic_block new_succ)
378 execute_on_shrinking_pred (e);
380 disconnect_dest (e);
382 e->dest = new_succ;
384 /* Reconnect the edge to the new successor block. */
385 connect_dest (e);
387 execute_on_growing_pred (e);
390 /* Like previous but avoid possible duplicate edge. */
392 edge
393 redirect_edge_succ_nodup (edge e, basic_block new_succ)
395 edge s;
397 s = find_edge (e->src, new_succ);
398 if (s && s != e)
400 s->flags |= e->flags;
401 s->probability += e->probability;
402 if (s->probability > REG_BR_PROB_BASE)
403 s->probability = REG_BR_PROB_BASE;
404 s->count += e->count;
405 remove_edge (e);
406 redirect_edge_var_map_dup (s, e);
407 e = s;
409 else
410 redirect_edge_succ (e, new_succ);
412 return e;
415 /* Redirect an edge's predecessor from one block to another. */
417 void
418 redirect_edge_pred (edge e, basic_block new_pred)
420 disconnect_src (e);
422 e->src = new_pred;
424 /* Reconnect the edge to the new predecessor block. */
425 connect_src (e);
428 /* Clear all basic block flags, with the exception of partitioning and
429 setjmp_target. */
430 void
431 clear_bb_flags (void)
433 basic_block bb;
435 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
436 bb->flags = (BB_PARTITION (bb)
437 | (bb->flags & (BB_DISABLE_SCHEDULE + BB_RTL + BB_NON_LOCAL_GOTO_TARGET)));
440 /* Check the consistency of profile information. We can't do that
441 in verify_flow_info, as the counts may get invalid for incompletely
442 solved graphs, later eliminating of conditionals or roundoff errors.
443 It is still practical to have them reported for debugging of simple
444 testcases. */
445 void
446 check_bb_profile (basic_block bb, FILE * file)
448 edge e;
449 int sum = 0;
450 gcov_type lsum;
451 edge_iterator ei;
453 if (profile_status == PROFILE_ABSENT)
454 return;
456 if (bb != EXIT_BLOCK_PTR)
458 FOR_EACH_EDGE (e, ei, bb->succs)
459 sum += e->probability;
460 if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
461 fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
462 sum * 100.0 / REG_BR_PROB_BASE);
463 lsum = 0;
464 FOR_EACH_EDGE (e, ei, bb->succs)
465 lsum += e->count;
466 if (EDGE_COUNT (bb->succs)
467 && (lsum - bb->count > 100 || lsum - bb->count < -100))
468 fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n",
469 (int) lsum, (int) bb->count);
471 if (bb != ENTRY_BLOCK_PTR)
473 sum = 0;
474 FOR_EACH_EDGE (e, ei, bb->preds)
475 sum += EDGE_FREQUENCY (e);
476 if (abs (sum - bb->frequency) > 100)
477 fprintf (file,
478 "Invalid sum of incoming frequencies %i, should be %i\n",
479 sum, bb->frequency);
480 lsum = 0;
481 FOR_EACH_EDGE (e, ei, bb->preds)
482 lsum += e->count;
483 if (lsum - bb->count > 100 || lsum - bb->count < -100)
484 fprintf (file, "Invalid sum of incoming counts %i, should be %i\n",
485 (int) lsum, (int) bb->count);
489 /* Write information about registers and basic blocks into FILE.
490 This is part of making a debugging dump. */
492 void
493 dump_regset (regset r, FILE *outf)
495 unsigned i;
496 reg_set_iterator rsi;
498 if (r == NULL)
500 fputs (" (nil)", outf);
501 return;
504 EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi)
506 fprintf (outf, " %d", i);
507 if (i < FIRST_PSEUDO_REGISTER)
508 fprintf (outf, " [%s]",
509 reg_names[i]);
513 /* Print a human-readable representation of R on the standard error
514 stream. This function is designed to be used from within the
515 debugger. */
517 void
518 debug_regset (regset r)
520 dump_regset (r, stderr);
521 putc ('\n', stderr);
524 /* Emit basic block information for BB. HEADER is true if the user wants
525 the generic information and the predecessors, FOOTER is true if they want
526 the successors. FLAGS is the dump flags of interest; TDF_DETAILS emit
527 global register liveness information. PREFIX is put in front of every
528 line. The output is emitted to FILE. */
529 void
530 dump_bb_info (basic_block bb, bool header, bool footer, int flags,
531 const char *prefix, FILE *file)
533 edge e;
534 edge_iterator ei;
536 if (header)
538 fprintf (file, "\n%sBasic block %d ", prefix, bb->index);
539 if (bb->prev_bb)
540 fprintf (file, ", prev %d", bb->prev_bb->index);
541 if (bb->next_bb)
542 fprintf (file, ", next %d", bb->next_bb->index);
543 fprintf (file, ", loop_depth %d, count ", bb->loop_depth);
544 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
545 fprintf (file, ", freq %i", bb->frequency);
546 /* Both maybe_hot_bb_p & probably_never_executed_bb_p functions
547 crash without cfun. */
548 if (cfun && maybe_hot_bb_p (bb))
549 fprintf (file, ", maybe hot");
550 if (cfun && probably_never_executed_bb_p (bb))
551 fprintf (file, ", probably never executed");
552 fprintf (file, ".\n");
554 fprintf (file, "%sPredecessors: ", prefix);
555 FOR_EACH_EDGE (e, ei, bb->preds)
556 dump_edge_info (file, e, 0);
558 if ((flags & TDF_DETAILS)
559 && (bb->flags & BB_RTL)
560 && df)
562 fprintf (file, "\n");
563 df_dump_top (bb, file);
567 if (footer)
569 fprintf (file, "\n%sSuccessors: ", prefix);
570 FOR_EACH_EDGE (e, ei, bb->succs)
571 dump_edge_info (file, e, 1);
573 if ((flags & TDF_DETAILS)
574 && (bb->flags & BB_RTL)
575 && df)
577 fprintf (file, "\n");
578 df_dump_bottom (bb, file);
582 putc ('\n', file);
585 /* Dump the register info to FILE. */
587 void
588 dump_reg_info (FILE *file)
590 unsigned int i, max = max_reg_num ();
591 if (reload_completed)
592 return;
594 if (reg_info_p_size < max)
595 max = reg_info_p_size;
597 fprintf (file, "%d registers.\n", max);
598 for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
600 enum reg_class class, altclass;
602 if (regstat_n_sets_and_refs)
603 fprintf (file, "\nRegister %d used %d times across %d insns",
604 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
605 else if (df)
606 fprintf (file, "\nRegister %d used %d times across %d insns",
607 i, DF_REG_USE_COUNT (i) + DF_REG_DEF_COUNT (i), REG_LIVE_LENGTH (i));
609 if (REG_BASIC_BLOCK (i) >= NUM_FIXED_BLOCKS)
610 fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
611 if (regstat_n_sets_and_refs)
612 fprintf (file, "; set %d time%s", REG_N_SETS (i),
613 (REG_N_SETS (i) == 1) ? "" : "s");
614 else if (df)
615 fprintf (file, "; set %d time%s", DF_REG_DEF_COUNT (i),
616 (DF_REG_DEF_COUNT (i) == 1) ? "" : "s");
617 if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
618 fprintf (file, "; user var");
619 if (REG_N_DEATHS (i) != 1)
620 fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
621 if (REG_N_CALLS_CROSSED (i) == 1)
622 fprintf (file, "; crosses 1 call");
623 else if (REG_N_CALLS_CROSSED (i))
624 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
625 if (REG_FREQ_CALLS_CROSSED (i))
626 fprintf (file, "; crosses call with %d frequency", REG_FREQ_CALLS_CROSSED (i));
627 if (regno_reg_rtx[i] != NULL
628 && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
629 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
631 class = reg_preferred_class (i);
632 altclass = reg_alternate_class (i);
633 if (class != GENERAL_REGS || altclass != ALL_REGS)
635 if (altclass == ALL_REGS || class == ALL_REGS)
636 fprintf (file, "; pref %s", reg_class_names[(int) class]);
637 else if (altclass == NO_REGS)
638 fprintf (file, "; %s or none", reg_class_names[(int) class]);
639 else
640 fprintf (file, "; pref %s, else %s",
641 reg_class_names[(int) class],
642 reg_class_names[(int) altclass]);
645 if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
646 fprintf (file, "; pointer");
647 fprintf (file, ".\n");
652 void
653 dump_flow_info (FILE *file, int flags)
655 basic_block bb;
657 /* There are no pseudo registers after reload. Don't dump them. */
658 if (reg_info_p_size && (flags & TDF_DETAILS) != 0)
659 dump_reg_info (file);
661 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
662 FOR_ALL_BB (bb)
664 dump_bb_info (bb, true, true, flags, "", file);
665 check_bb_profile (bb, file);
668 putc ('\n', file);
671 void
672 debug_flow_info (void)
674 dump_flow_info (stderr, TDF_DETAILS);
677 void
678 dump_edge_info (FILE *file, edge e, int do_succ)
680 basic_block side = (do_succ ? e->dest : e->src);
681 /* both ENTRY_BLOCK_PTR & EXIT_BLOCK_PTR depend upon cfun. */
682 if (cfun && side == ENTRY_BLOCK_PTR)
683 fputs (" ENTRY", file);
684 else if (cfun && side == EXIT_BLOCK_PTR)
685 fputs (" EXIT", file);
686 else
687 fprintf (file, " %d", side->index);
689 if (e->probability)
690 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
692 if (e->count)
694 fprintf (file, " count:");
695 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
698 if (e->flags)
700 static const char * const bitnames[] = {
701 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
702 "can_fallthru", "irreducible", "sibcall", "loop_exit",
703 "true", "false", "exec"
705 int comma = 0;
706 int i, flags = e->flags;
708 fputs (" (", file);
709 for (i = 0; flags; i++)
710 if (flags & (1 << i))
712 flags &= ~(1 << i);
714 if (comma)
715 fputc (',', file);
716 if (i < (int) ARRAY_SIZE (bitnames))
717 fputs (bitnames[i], file);
718 else
719 fprintf (file, "%d", i);
720 comma = 1;
723 fputc (')', file);
727 /* Simple routines to easily allocate AUX fields of basic blocks. */
729 static struct obstack block_aux_obstack;
730 static void *first_block_aux_obj = 0;
731 static struct obstack edge_aux_obstack;
732 static void *first_edge_aux_obj = 0;
734 /* Allocate a memory block of SIZE as BB->aux. The obstack must
735 be first initialized by alloc_aux_for_blocks. */
737 inline void
738 alloc_aux_for_block (basic_block bb, int size)
740 /* Verify that aux field is clear. */
741 gcc_assert (!bb->aux && first_block_aux_obj);
742 bb->aux = obstack_alloc (&block_aux_obstack, size);
743 memset (bb->aux, 0, size);
746 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
747 alloc_aux_for_block for each basic block. */
749 void
750 alloc_aux_for_blocks (int size)
752 static int initialized;
754 if (!initialized)
756 gcc_obstack_init (&block_aux_obstack);
757 initialized = 1;
759 else
760 /* Check whether AUX data are still allocated. */
761 gcc_assert (!first_block_aux_obj);
763 first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
764 if (size)
766 basic_block bb;
768 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
769 alloc_aux_for_block (bb, size);
773 /* Clear AUX pointers of all blocks. */
775 void
776 clear_aux_for_blocks (void)
778 basic_block bb;
780 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
781 bb->aux = NULL;
784 /* Free data allocated in block_aux_obstack and clear AUX pointers
785 of all blocks. */
787 void
788 free_aux_for_blocks (void)
790 gcc_assert (first_block_aux_obj);
791 obstack_free (&block_aux_obstack, first_block_aux_obj);
792 first_block_aux_obj = NULL;
794 clear_aux_for_blocks ();
797 /* Allocate a memory edge of SIZE as BB->aux. The obstack must
798 be first initialized by alloc_aux_for_edges. */
800 inline void
801 alloc_aux_for_edge (edge e, int size)
803 /* Verify that aux field is clear. */
804 gcc_assert (!e->aux && first_edge_aux_obj);
805 e->aux = obstack_alloc (&edge_aux_obstack, size);
806 memset (e->aux, 0, size);
809 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
810 alloc_aux_for_edge for each basic edge. */
812 void
813 alloc_aux_for_edges (int size)
815 static int initialized;
817 if (!initialized)
819 gcc_obstack_init (&edge_aux_obstack);
820 initialized = 1;
822 else
823 /* Check whether AUX data are still allocated. */
824 gcc_assert (!first_edge_aux_obj);
826 first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
827 if (size)
829 basic_block bb;
831 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
833 edge e;
834 edge_iterator ei;
836 FOR_EACH_EDGE (e, ei, bb->succs)
837 alloc_aux_for_edge (e, size);
842 /* Clear AUX pointers of all edges. */
844 void
845 clear_aux_for_edges (void)
847 basic_block bb;
848 edge e;
850 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
852 edge_iterator ei;
853 FOR_EACH_EDGE (e, ei, bb->succs)
854 e->aux = NULL;
858 /* Free data allocated in edge_aux_obstack and clear AUX pointers
859 of all edges. */
861 void
862 free_aux_for_edges (void)
864 gcc_assert (first_edge_aux_obj);
865 obstack_free (&edge_aux_obstack, first_edge_aux_obj);
866 first_edge_aux_obj = NULL;
868 clear_aux_for_edges ();
871 void
872 debug_bb (basic_block bb)
874 dump_bb (bb, stderr, 0);
877 basic_block
878 debug_bb_n (int n)
880 basic_block bb = BASIC_BLOCK (n);
881 dump_bb (bb, stderr, 0);
882 return bb;
885 /* Dumps cfg related information about basic block BB to FILE. */
887 static void
888 dump_cfg_bb_info (FILE *file, basic_block bb)
890 unsigned i;
891 edge_iterator ei;
892 bool first = true;
893 static const char * const bb_bitnames[] =
895 "new", "reachable", "irreducible_loop", "superblock",
896 "nosched", "hot", "cold", "dup", "xlabel", "rtl",
897 "fwdr", "nothrd"
899 const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
900 edge e;
902 fprintf (file, "Basic block %d", bb->index);
903 for (i = 0; i < n_bitnames; i++)
904 if (bb->flags & (1 << i))
906 if (first)
907 fprintf (file, " (");
908 else
909 fprintf (file, ", ");
910 first = false;
911 fprintf (file, bb_bitnames[i]);
913 if (!first)
914 fprintf (file, ")");
915 fprintf (file, "\n");
917 fprintf (file, "Predecessors: ");
918 FOR_EACH_EDGE (e, ei, bb->preds)
919 dump_edge_info (file, e, 0);
921 fprintf (file, "\nSuccessors: ");
922 FOR_EACH_EDGE (e, ei, bb->succs)
923 dump_edge_info (file, e, 1);
924 fprintf (file, "\n\n");
927 /* Dumps a brief description of cfg to FILE. */
929 void
930 brief_dump_cfg (FILE *file)
932 basic_block bb;
934 FOR_EACH_BB (bb)
936 dump_cfg_bb_info (file, bb);
940 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
941 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
942 redirected to destination of TAKEN_EDGE.
944 This function may leave the profile inconsistent in the case TAKEN_EDGE
945 frequency or count is believed to be lower than FREQUENCY or COUNT
946 respectively. */
947 void
948 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
949 gcov_type count, edge taken_edge)
951 edge c;
952 int prob;
953 edge_iterator ei;
955 bb->count -= count;
956 if (bb->count < 0)
958 if (dump_file)
959 fprintf (dump_file, "bb %i count became negative after threading",
960 bb->index);
961 bb->count = 0;
964 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
965 Watch for overflows. */
966 if (bb->frequency)
967 prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
968 else
969 prob = 0;
970 if (prob > taken_edge->probability)
972 if (dump_file)
973 fprintf (dump_file, "Jump threading proved probability of edge "
974 "%i->%i too small (it is %i, should be %i).\n",
975 taken_edge->src->index, taken_edge->dest->index,
976 taken_edge->probability, prob);
977 prob = taken_edge->probability;
980 /* Now rescale the probabilities. */
981 taken_edge->probability -= prob;
982 prob = REG_BR_PROB_BASE - prob;
983 bb->frequency -= edge_frequency;
984 if (bb->frequency < 0)
985 bb->frequency = 0;
986 if (prob <= 0)
988 if (dump_file)
989 fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
990 "frequency of block should end up being 0, it is %i\n",
991 bb->index, bb->frequency);
992 EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
993 ei = ei_start (bb->succs);
994 ei_next (&ei);
995 for (; (c = ei_safe_edge (ei)); ei_next (&ei))
996 c->probability = 0;
998 else if (prob != REG_BR_PROB_BASE)
1000 int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
1002 FOR_EACH_EDGE (c, ei, bb->succs)
1004 /* Protect from overflow due to additional scaling. */
1005 if (c->probability > prob)
1006 c->probability = REG_BR_PROB_BASE;
1007 else
1009 c->probability = RDIV (c->probability * scale, 65536);
1010 if (c->probability > REG_BR_PROB_BASE)
1011 c->probability = REG_BR_PROB_BASE;
1016 gcc_assert (bb == taken_edge->src);
1017 taken_edge->count -= count;
1018 if (taken_edge->count < 0)
1020 if (dump_file)
1021 fprintf (dump_file, "edge %i->%i count became negative after threading",
1022 taken_edge->src->index, taken_edge->dest->index);
1023 taken_edge->count = 0;
1027 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1028 by NUM/DEN, in int arithmetic. May lose some accuracy. */
1029 void
1030 scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
1032 int i;
1033 edge e;
1034 if (num < 0)
1035 num = 0;
1037 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
1038 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
1039 and still safely fit in int during calculations. */
1040 if (den > 1000)
1042 if (num > 1000000)
1043 return;
1045 num = RDIV (1000 * num, den);
1046 den = 1000;
1048 if (num > 100 * den)
1049 return;
1051 for (i = 0; i < nbbs; i++)
1053 edge_iterator ei;
1054 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1055 /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
1056 if (bbs[i]->frequency > BB_FREQ_MAX)
1057 bbs[i]->frequency = BB_FREQ_MAX;
1058 bbs[i]->count = RDIV (bbs[i]->count * num, den);
1059 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1060 e->count = RDIV (e->count * num, den);
1064 /* numbers smaller than this value are safe to multiply without getting
1065 64bit overflow. */
1066 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
1068 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1069 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
1070 function but considerably slower. */
1071 void
1072 scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
1073 gcov_type den)
1075 int i;
1076 edge e;
1077 gcov_type fraction = RDIV (num * 65536, den);
1079 gcc_assert (fraction >= 0);
1081 if (num < MAX_SAFE_MULTIPLIER)
1082 for (i = 0; i < nbbs; i++)
1084 edge_iterator ei;
1085 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1086 if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1087 bbs[i]->count = RDIV (bbs[i]->count * num, den);
1088 else
1089 bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1090 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1091 if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1092 e->count = RDIV (e->count * num, den);
1093 else
1094 e->count = RDIV (e->count * fraction, 65536);
1096 else
1097 for (i = 0; i < nbbs; i++)
1099 edge_iterator ei;
1100 if (sizeof (gcov_type) > sizeof (int))
1101 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1102 else
1103 bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
1104 bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1105 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1106 e->count = RDIV (e->count * fraction, 65536);
1110 /* Data structures used to maintain mapping between basic blocks and
1111 copies. */
1112 static htab_t bb_original;
1113 static htab_t bb_copy;
1115 /* And between loops and copies. */
1116 static htab_t loop_copy;
1117 static alloc_pool original_copy_bb_pool;
1119 struct htab_bb_copy_original_entry
1121 /* Block we are attaching info to. */
1122 int index1;
1123 /* Index of original or copy (depending on the hashtable) */
1124 int index2;
1127 static hashval_t
1128 bb_copy_original_hash (const void *p)
1130 const struct htab_bb_copy_original_entry *data
1131 = ((const struct htab_bb_copy_original_entry *)p);
1133 return data->index1;
1135 static int
1136 bb_copy_original_eq (const void *p, const void *q)
1138 const struct htab_bb_copy_original_entry *data
1139 = ((const struct htab_bb_copy_original_entry *)p);
1140 const struct htab_bb_copy_original_entry *data2
1141 = ((const struct htab_bb_copy_original_entry *)q);
1143 return data->index1 == data2->index1;
1146 /* Initialize the data structures to maintain mapping between blocks
1147 and its copies. */
1148 void
1149 initialize_original_copy_tables (void)
1151 gcc_assert (!original_copy_bb_pool);
1152 original_copy_bb_pool
1153 = create_alloc_pool ("original_copy",
1154 sizeof (struct htab_bb_copy_original_entry), 10);
1155 bb_original = htab_create (10, bb_copy_original_hash,
1156 bb_copy_original_eq, NULL);
1157 bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1158 loop_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1161 /* Free the data structures to maintain mapping between blocks and
1162 its copies. */
1163 void
1164 free_original_copy_tables (void)
1166 gcc_assert (original_copy_bb_pool);
1167 htab_delete (bb_copy);
1168 htab_delete (bb_original);
1169 htab_delete (loop_copy);
1170 free_alloc_pool (original_copy_bb_pool);
1171 bb_copy = NULL;
1172 bb_original = NULL;
1173 loop_copy = NULL;
1174 original_copy_bb_pool = NULL;
1177 /* Removes the value associated with OBJ from table TAB. */
1179 static void
1180 copy_original_table_clear (htab_t tab, unsigned obj)
1182 void **slot;
1183 struct htab_bb_copy_original_entry key, *elt;
1185 if (!original_copy_bb_pool)
1186 return;
1188 key.index1 = obj;
1189 slot = htab_find_slot (tab, &key, NO_INSERT);
1190 if (!slot)
1191 return;
1193 elt = (struct htab_bb_copy_original_entry *) *slot;
1194 htab_clear_slot (tab, slot);
1195 pool_free (original_copy_bb_pool, elt);
1198 /* Sets the value associated with OBJ in table TAB to VAL.
1199 Do nothing when data structures are not initialized. */
1201 static void
1202 copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
1204 struct htab_bb_copy_original_entry **slot;
1205 struct htab_bb_copy_original_entry key;
1207 if (!original_copy_bb_pool)
1208 return;
1210 key.index1 = obj;
1211 slot = (struct htab_bb_copy_original_entry **)
1212 htab_find_slot (tab, &key, INSERT);
1213 if (!*slot)
1215 *slot = (struct htab_bb_copy_original_entry *)
1216 pool_alloc (original_copy_bb_pool);
1217 (*slot)->index1 = obj;
1219 (*slot)->index2 = val;
1222 /* Set original for basic block. Do nothing when data structures are not
1223 initialized so passes not needing this don't need to care. */
1224 void
1225 set_bb_original (basic_block bb, basic_block original)
1227 copy_original_table_set (bb_original, bb->index, original->index);
1230 /* Get the original basic block. */
1231 basic_block
1232 get_bb_original (basic_block bb)
1234 struct htab_bb_copy_original_entry *entry;
1235 struct htab_bb_copy_original_entry key;
1237 gcc_assert (original_copy_bb_pool);
1239 key.index1 = bb->index;
1240 entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
1241 if (entry)
1242 return BASIC_BLOCK (entry->index2);
1243 else
1244 return NULL;
1247 /* Set copy for basic block. Do nothing when data structures are not
1248 initialized so passes not needing this don't need to care. */
1249 void
1250 set_bb_copy (basic_block bb, basic_block copy)
1252 copy_original_table_set (bb_copy, bb->index, copy->index);
1255 /* Get the copy of basic block. */
1256 basic_block
1257 get_bb_copy (basic_block bb)
1259 struct htab_bb_copy_original_entry *entry;
1260 struct htab_bb_copy_original_entry key;
1262 gcc_assert (original_copy_bb_pool);
1264 key.index1 = bb->index;
1265 entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
1266 if (entry)
1267 return BASIC_BLOCK (entry->index2);
1268 else
1269 return NULL;
1272 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1273 initialized so passes not needing this don't need to care. */
1275 void
1276 set_loop_copy (struct loop *loop, struct loop *copy)
1278 if (!copy)
1279 copy_original_table_clear (loop_copy, loop->num);
1280 else
1281 copy_original_table_set (loop_copy, loop->num, copy->num);
1284 /* Get the copy of LOOP. */
1286 struct loop *
1287 get_loop_copy (struct loop *loop)
1289 struct htab_bb_copy_original_entry *entry;
1290 struct htab_bb_copy_original_entry key;
1292 gcc_assert (original_copy_bb_pool);
1294 key.index1 = loop->num;
1295 entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy, &key);
1296 if (entry)
1297 return get_loop (entry->index2);
1298 else
1299 return NULL;