OSDN Git Service

2006-02-15 Paolo Bonzini <bonzini@gnu.org>
[pf3gnuchains/gcc-fork.git] / gcc / cfg.c
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
4    Free Software Foundation, Inc.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
11 version.
12
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.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING.  If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 02110-1301, USA.  */
22
23 /* This file contains low level functions to manipulate the CFG and
24    analyze it.  All other modules should not transform the data structure
25    directly and use abstraction instead.  The file is supposed to be
26    ordered bottom-up and should not contain any code dependent on a
27    particular intermediate language (RTL or trees).
28
29    Available functionality:
30      - Initialization/deallocation
31          init_flow, clear_edges
32      - Low level basic block manipulation
33          alloc_block, expunge_block
34      - Edge manipulation
35          make_edge, make_single_succ_edge, cached_make_edge, remove_edge
36          - Low level edge redirection (without updating instruction chain)
37              redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
38      - Dumping and debugging
39          dump_flow_info, debug_flow_info, dump_edge_info
40      - Allocation of AUX fields for basic blocks
41          alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
42      - clear_bb_flags
43      - Consistency checking
44          verify_flow_info
45      - Dumping and debugging
46          print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
47  */
48 \f
49 #include "config.h"
50 #include "system.h"
51 #include "coretypes.h"
52 #include "tm.h"
53 #include "tree.h"
54 #include "rtl.h"
55 #include "hard-reg-set.h"
56 #include "regs.h"
57 #include "flags.h"
58 #include "output.h"
59 #include "function.h"
60 #include "except.h"
61 #include "toplev.h"
62 #include "tm_p.h"
63 #include "obstack.h"
64 #include "timevar.h"
65 #include "tree-pass.h"
66 #include "ggc.h"
67 #include "hashtab.h"
68 #include "alloc-pool.h"
69
70 /* The obstack on which the flow graph components are allocated.  */
71
72 struct bitmap_obstack reg_obstack;
73
74 void debug_flow_info (void);
75 static void free_edge (edge);
76 \f
77 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
78
79 /* Called once at initialization time.  */
80
81 void
82 init_flow (void)
83 {
84   if (!cfun->cfg)
85     cfun->cfg = ggc_alloc_cleared (sizeof (struct control_flow_graph));
86   n_edges = 0;
87   ENTRY_BLOCK_PTR = ggc_alloc_cleared (sizeof (struct basic_block_def));
88   ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
89   EXIT_BLOCK_PTR = ggc_alloc_cleared (sizeof (struct basic_block_def));
90   EXIT_BLOCK_PTR->index = EXIT_BLOCK;
91   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
92   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
93 }
94 \f
95 /* Helper function for remove_edge and clear_edges.  Frees edge structure
96    without actually unlinking it from the pred/succ lists.  */
97
98 static void
99 free_edge (edge e ATTRIBUTE_UNUSED)
100 {
101   n_edges--;
102   ggc_free (e);
103 }
104
105 /* Free the memory associated with the edge structures.  */
106
107 void
108 clear_edges (void)
109 {
110   basic_block bb;
111   edge e;
112   edge_iterator ei;
113
114   FOR_EACH_BB (bb)
115     {
116       FOR_EACH_EDGE (e, ei, bb->succs)
117         free_edge (e);
118       VEC_truncate (edge, bb->succs, 0);
119       VEC_truncate (edge, bb->preds, 0);
120     }
121
122   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
123     free_edge (e);
124   VEC_truncate (edge, EXIT_BLOCK_PTR->preds, 0);
125   VEC_truncate (edge, ENTRY_BLOCK_PTR->succs, 0);
126
127   gcc_assert (!n_edges);
128 }
129 \f
130 /* Allocate memory for basic_block.  */
131
132 basic_block
133 alloc_block (void)
134 {
135   basic_block bb;
136   bb = ggc_alloc_cleared (sizeof (*bb));
137   return bb;
138 }
139
140 /* Link block B to chain after AFTER.  */
141 void
142 link_block (basic_block b, basic_block after)
143 {
144   b->next_bb = after->next_bb;
145   b->prev_bb = after;
146   after->next_bb = b;
147   b->next_bb->prev_bb = b;
148 }
149
150 /* Unlink block B from chain.  */
151 void
152 unlink_block (basic_block b)
153 {
154   b->next_bb->prev_bb = b->prev_bb;
155   b->prev_bb->next_bb = b->next_bb;
156   b->prev_bb = NULL;
157   b->next_bb = NULL;
158 }
159
160 /* Sequentially order blocks and compact the arrays.  */
161 void
162 compact_blocks (void)
163 {
164   int i;
165   basic_block bb;
166
167   SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
168   SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
169
170   i = NUM_FIXED_BLOCKS;
171   FOR_EACH_BB (bb) 
172     {
173       SET_BASIC_BLOCK (i, bb);
174       bb->index = i;
175       i++;
176     }
177
178   gcc_assert (i == n_basic_blocks);
179
180   for (; i < last_basic_block; i++)
181     SET_BASIC_BLOCK (i, NULL);
182
183   last_basic_block = n_basic_blocks;
184 }
185
186 /* Remove block B from the basic block array.  */
187
188 void
189 expunge_block (basic_block b)
190 {
191   unlink_block (b);
192   SET_BASIC_BLOCK (b->index, NULL);
193   n_basic_blocks--;
194   /* We should be able to ggc_free here, but we are not.
195      The dead SSA_NAMES are left pointing to dead statements that are pointing
196      to dead basic blocks making garbage collector to die.
197      We should be able to release all dead SSA_NAMES and at the same time we should
198      clear out BB pointer of dead statements consistently.  */
199 }
200 \f
201 /* Connect E to E->src.  */
202
203 static inline void
204 connect_src (edge e)
205 {
206   VEC_safe_push (edge, gc, e->src->succs, e);
207 }
208
209 /* Connect E to E->dest.  */
210
211 static inline void
212 connect_dest (edge e)
213 {
214   basic_block dest = e->dest;
215   VEC_safe_push (edge, gc, dest->preds, e);
216   e->dest_idx = EDGE_COUNT (dest->preds) - 1;
217 }
218
219 /* Disconnect edge E from E->src.  */
220
221 static inline void
222 disconnect_src (edge e)
223 {
224   basic_block src = e->src;
225   edge_iterator ei;
226   edge tmp;
227
228   for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
229     {
230       if (tmp == e)
231         {
232           VEC_unordered_remove (edge, src->succs, ei.index);
233           return;
234         }
235       else
236         ei_next (&ei);
237     }
238
239   gcc_unreachable ();
240 }
241
242 /* Disconnect edge E from E->dest.  */
243
244 static inline void
245 disconnect_dest (edge e)
246 {
247   basic_block dest = e->dest;
248   unsigned int dest_idx = e->dest_idx;
249
250   VEC_unordered_remove (edge, dest->preds, dest_idx);
251
252   /* If we removed an edge in the middle of the edge vector, we need
253      to update dest_idx of the edge that moved into the "hole".  */
254   if (dest_idx < EDGE_COUNT (dest->preds))
255     EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
256 }
257
258 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
259    created edge.  Use this only if you are sure that this edge can't
260    possibly already exist.  */
261
262 edge
263 unchecked_make_edge (basic_block src, basic_block dst, int flags)
264 {
265   edge e;
266   e = ggc_alloc_cleared (sizeof (*e));
267   n_edges++;
268
269   e->src = src;
270   e->dest = dst;
271   e->flags = flags;
272
273   connect_src (e);
274   connect_dest (e);
275
276   execute_on_growing_pred (e);
277
278   return e;
279 }
280
281 /* Create an edge connecting SRC and DST with FLAGS optionally using
282    edge cache CACHE.  Return the new edge, NULL if already exist.  */
283
284 edge
285 cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
286 {
287   if (edge_cache == NULL
288       || src == ENTRY_BLOCK_PTR
289       || dst == EXIT_BLOCK_PTR)
290     return make_edge (src, dst, flags);
291
292   /* Does the requested edge already exist?  */
293   if (! TEST_BIT (edge_cache, dst->index))
294     {
295       /* The edge does not exist.  Create one and update the
296          cache.  */
297       SET_BIT (edge_cache, dst->index);
298       return unchecked_make_edge (src, dst, flags);
299     }
300
301   /* At this point, we know that the requested edge exists.  Adjust
302      flags if necessary.  */
303   if (flags)
304     {
305       edge e = find_edge (src, dst);
306       e->flags |= flags;
307     }
308
309   return NULL;
310 }
311
312 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
313    created edge or NULL if already exist.  */
314
315 edge
316 make_edge (basic_block src, basic_block dest, int flags)
317 {
318   edge e = find_edge (src, dest);
319
320   /* Make sure we don't add duplicate edges.  */
321   if (e)
322     {
323       e->flags |= flags;
324       return NULL;
325     }
326
327   return unchecked_make_edge (src, dest, flags);
328 }
329
330 /* Create an edge connecting SRC to DEST and set probability by knowing
331    that it is the single edge leaving SRC.  */
332
333 edge
334 make_single_succ_edge (basic_block src, basic_block dest, int flags)
335 {
336   edge e = make_edge (src, dest, flags);
337
338   e->probability = REG_BR_PROB_BASE;
339   e->count = src->count;
340   return e;
341 }
342
343 /* This function will remove an edge from the flow graph.  */
344
345 void
346 remove_edge (edge e)
347 {
348   remove_predictions_associated_with_edge (e);
349   execute_on_shrinking_pred (e);
350
351   disconnect_src (e);
352   disconnect_dest (e);
353
354   free_edge (e);
355 }
356
357 /* Redirect an edge's successor from one block to another.  */
358
359 void
360 redirect_edge_succ (edge e, basic_block new_succ)
361 {
362   execute_on_shrinking_pred (e);
363
364   disconnect_dest (e);
365
366   e->dest = new_succ;
367
368   /* Reconnect the edge to the new successor block.  */
369   connect_dest (e);
370
371   execute_on_growing_pred (e);
372 }
373
374 /* Like previous but avoid possible duplicate edge.  */
375
376 edge
377 redirect_edge_succ_nodup (edge e, basic_block new_succ)
378 {
379   edge s;
380
381   s = find_edge (e->src, new_succ);
382   if (s && s != e)
383     {
384       s->flags |= e->flags;
385       s->probability += e->probability;
386       if (s->probability > REG_BR_PROB_BASE)
387         s->probability = REG_BR_PROB_BASE;
388       s->count += e->count;
389       remove_edge (e);
390       e = s;
391     }
392   else
393     redirect_edge_succ (e, new_succ);
394
395   return e;
396 }
397
398 /* Redirect an edge's predecessor from one block to another.  */
399
400 void
401 redirect_edge_pred (edge e, basic_block new_pred)
402 {
403   disconnect_src (e);
404
405   e->src = new_pred;
406
407   /* Reconnect the edge to the new predecessor block.  */
408   connect_src (e);
409 }
410
411 /* Clear all basic block flags, with the exception of partitioning.  */
412 void
413 clear_bb_flags (void)
414 {
415   basic_block bb;
416
417   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
418     bb->flags = (BB_PARTITION (bb)  | (bb->flags & BB_DISABLE_SCHEDULE)
419                  | (bb->flags & BB_RTL));
420 }
421 \f
422 /* Check the consistency of profile information.  We can't do that
423    in verify_flow_info, as the counts may get invalid for incompletely
424    solved graphs, later eliminating of conditionals or roundoff errors.
425    It is still practical to have them reported for debugging of simple
426    testcases.  */
427 void
428 check_bb_profile (basic_block bb, FILE * file)
429 {
430   edge e;
431   int sum = 0;
432   gcov_type lsum;
433   edge_iterator ei;
434
435   if (profile_status == PROFILE_ABSENT)
436     return;
437
438   if (bb != EXIT_BLOCK_PTR)
439     {
440       FOR_EACH_EDGE (e, ei, bb->succs)
441         sum += e->probability;
442       if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
443         fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
444                  sum * 100.0 / REG_BR_PROB_BASE);
445       lsum = 0;
446       FOR_EACH_EDGE (e, ei, bb->succs)
447         lsum += e->count;
448       if (EDGE_COUNT (bb->succs)
449           && (lsum - bb->count > 100 || lsum - bb->count < -100))
450         fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n",
451                  (int) lsum, (int) bb->count);
452     }
453   if (bb != ENTRY_BLOCK_PTR)
454     {
455       sum = 0;
456       FOR_EACH_EDGE (e, ei, bb->preds)
457         sum += EDGE_FREQUENCY (e);
458       if (abs (sum - bb->frequency) > 100)
459         fprintf (file,
460                  "Invalid sum of incoming frequencies %i, should be %i\n",
461                  sum, bb->frequency);
462       lsum = 0;
463       FOR_EACH_EDGE (e, ei, bb->preds)
464         lsum += e->count;
465       if (lsum - bb->count > 100 || lsum - bb->count < -100)
466         fprintf (file, "Invalid sum of incoming counts %i, should be %i\n",
467                  (int) lsum, (int) bb->count);
468     }
469 }
470 \f
471 /* Emit basic block information for BB.  HEADER is true if the user wants
472    the generic information and the predecessors, FOOTER is true if they want
473    the successors.  FLAGS is the dump flags of interest; TDF_DETAILS emit
474    global register liveness information.  PREFIX is put in front of every
475    line.  The output is emitted to FILE.  */
476 void
477 dump_bb_info (basic_block bb, bool header, bool footer, int flags,
478               const char *prefix, FILE *file)
479 {
480   edge e;
481   edge_iterator ei;
482
483   if (header)
484     {
485       fprintf (file, "\n%sBasic block %d ", prefix, bb->index);
486       if (bb->prev_bb)
487         fprintf (file, ", prev %d", bb->prev_bb->index);
488       if (bb->next_bb)
489         fprintf (file, ", next %d", bb->next_bb->index);
490       fprintf (file, ", loop_depth %d, count ", bb->loop_depth);
491       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
492       fprintf (file, ", freq %i", bb->frequency);
493       if (maybe_hot_bb_p (bb))
494         fprintf (file, ", maybe hot");
495       if (probably_never_executed_bb_p (bb))
496         fprintf (file, ", probably never executed");
497       fprintf (file, ".\n");
498
499       fprintf (file, "%sPredecessors: ", prefix);
500       FOR_EACH_EDGE (e, ei, bb->preds)
501         dump_edge_info (file, e, 0);
502    }
503
504   if (footer)
505     {
506       fprintf (file, "\n%sSuccessors: ", prefix);
507       FOR_EACH_EDGE (e, ei, bb->succs)
508         dump_edge_info (file, e, 1);
509    }
510
511   if ((flags & TDF_DETAILS)
512       && (bb->flags & BB_RTL))
513     {
514       if (bb->il.rtl->global_live_at_start && header)
515         {
516           fprintf (file, "\n%sRegisters live at start:", prefix);
517           dump_regset (bb->il.rtl->global_live_at_start, file);
518         }
519
520       if (bb->il.rtl->global_live_at_end && footer)
521         {
522           fprintf (file, "\n%sRegisters live at end:", prefix);
523           dump_regset (bb->il.rtl->global_live_at_end, file);
524         }
525    }
526
527   putc ('\n', file);
528 }
529
530 void
531 dump_flow_info (FILE *file, int flags)
532 {
533   basic_block bb;
534
535   /* There are no pseudo registers after reload.  Don't dump them.  */
536   if (reg_n_info && !reload_completed
537       && (flags & TDF_DETAILS) != 0)
538     {
539       unsigned int i, max = max_reg_num ();
540       fprintf (file, "%d registers.\n", max);
541       for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
542         if (REG_N_REFS (i))
543           {
544             enum reg_class class, altclass;
545
546             fprintf (file, "\nRegister %d used %d times across %d insns",
547                      i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
548             if (REG_BASIC_BLOCK (i) >= 0)
549               fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
550             if (REG_N_SETS (i))
551               fprintf (file, "; set %d time%s", REG_N_SETS (i),
552                        (REG_N_SETS (i) == 1) ? "" : "s");
553             if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
554               fprintf (file, "; user var");
555             if (REG_N_DEATHS (i) != 1)
556               fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
557             if (REG_N_CALLS_CROSSED (i) == 1)
558               fprintf (file, "; crosses 1 call");
559             else if (REG_N_CALLS_CROSSED (i))
560               fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
561             if (regno_reg_rtx[i] != NULL
562                 && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
563               fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
564
565             class = reg_preferred_class (i);
566             altclass = reg_alternate_class (i);
567             if (class != GENERAL_REGS || altclass != ALL_REGS)
568               {
569                 if (altclass == ALL_REGS || class == ALL_REGS)
570                   fprintf (file, "; pref %s", reg_class_names[(int) class]);
571                 else if (altclass == NO_REGS)
572                   fprintf (file, "; %s or none", reg_class_names[(int) class]);
573                 else
574                   fprintf (file, "; pref %s, else %s",
575                            reg_class_names[(int) class],
576                            reg_class_names[(int) altclass]);
577               }
578
579             if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
580               fprintf (file, "; pointer");
581             fprintf (file, ".\n");
582           }
583     }
584
585   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
586   FOR_EACH_BB (bb)
587     {
588       dump_bb_info (bb, true, true, flags, "", file);
589       check_bb_profile (bb, file);
590     }
591
592   putc ('\n', file);
593 }
594
595 void
596 debug_flow_info (void)
597 {
598   dump_flow_info (stderr, TDF_DETAILS);
599 }
600
601 void
602 dump_edge_info (FILE *file, edge e, int do_succ)
603 {
604   basic_block side = (do_succ ? e->dest : e->src);
605
606   if (side == ENTRY_BLOCK_PTR)
607     fputs (" ENTRY", file);
608   else if (side == EXIT_BLOCK_PTR)
609     fputs (" EXIT", file);
610   else
611     fprintf (file, " %d", side->index);
612
613   if (e->probability)
614     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
615
616   if (e->count)
617     {
618       fprintf (file, " count:");
619       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
620     }
621
622   if (e->flags)
623     {
624       static const char * const bitnames[] = {
625         "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
626         "can_fallthru", "irreducible", "sibcall", "loop_exit",
627         "true", "false", "exec"
628       };
629       int comma = 0;
630       int i, flags = e->flags;
631
632       fputs (" (", file);
633       for (i = 0; flags; i++)
634         if (flags & (1 << i))
635           {
636             flags &= ~(1 << i);
637
638             if (comma)
639               fputc (',', file);
640             if (i < (int) ARRAY_SIZE (bitnames))
641               fputs (bitnames[i], file);
642             else
643               fprintf (file, "%d", i);
644             comma = 1;
645           }
646
647       fputc (')', file);
648     }
649 }
650 \f
651 /* Simple routines to easily allocate AUX fields of basic blocks.  */
652
653 static struct obstack block_aux_obstack;
654 static void *first_block_aux_obj = 0;
655 static struct obstack edge_aux_obstack;
656 static void *first_edge_aux_obj = 0;
657
658 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
659    be first initialized by alloc_aux_for_blocks.  */
660
661 inline void
662 alloc_aux_for_block (basic_block bb, int size)
663 {
664   /* Verify that aux field is clear.  */
665   gcc_assert (!bb->aux && first_block_aux_obj);
666   bb->aux = obstack_alloc (&block_aux_obstack, size);
667   memset (bb->aux, 0, size);
668 }
669
670 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
671    alloc_aux_for_block for each basic block.  */
672
673 void
674 alloc_aux_for_blocks (int size)
675 {
676   static int initialized;
677
678   if (!initialized)
679     {
680       gcc_obstack_init (&block_aux_obstack);
681       initialized = 1;
682     }
683   else
684     /* Check whether AUX data are still allocated.  */
685     gcc_assert (!first_block_aux_obj);
686   
687   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
688   if (size)
689     {
690       basic_block bb;
691
692       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
693         alloc_aux_for_block (bb, size);
694     }
695 }
696
697 /* Clear AUX pointers of all blocks.  */
698
699 void
700 clear_aux_for_blocks (void)
701 {
702   basic_block bb;
703
704   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
705     bb->aux = NULL;
706 }
707
708 /* Free data allocated in block_aux_obstack and clear AUX pointers
709    of all blocks.  */
710
711 void
712 free_aux_for_blocks (void)
713 {
714   gcc_assert (first_block_aux_obj);
715   obstack_free (&block_aux_obstack, first_block_aux_obj);
716   first_block_aux_obj = NULL;
717
718   clear_aux_for_blocks ();
719 }
720
721 /* Allocate a memory edge of SIZE as BB->aux.  The obstack must
722    be first initialized by alloc_aux_for_edges.  */
723
724 inline void
725 alloc_aux_for_edge (edge e, int size)
726 {
727   /* Verify that aux field is clear.  */
728   gcc_assert (!e->aux && first_edge_aux_obj);
729   e->aux = obstack_alloc (&edge_aux_obstack, size);
730   memset (e->aux, 0, size);
731 }
732
733 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
734    alloc_aux_for_edge for each basic edge.  */
735
736 void
737 alloc_aux_for_edges (int size)
738 {
739   static int initialized;
740
741   if (!initialized)
742     {
743       gcc_obstack_init (&edge_aux_obstack);
744       initialized = 1;
745     }
746   else
747     /* Check whether AUX data are still allocated.  */
748     gcc_assert (!first_edge_aux_obj);
749
750   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
751   if (size)
752     {
753       basic_block bb;
754
755       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
756         {
757           edge e;
758           edge_iterator ei;
759
760           FOR_EACH_EDGE (e, ei, bb->succs)
761             alloc_aux_for_edge (e, size);
762         }
763     }
764 }
765
766 /* Clear AUX pointers of all edges.  */
767
768 void
769 clear_aux_for_edges (void)
770 {
771   basic_block bb;
772   edge e;
773
774   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
775     {
776       edge_iterator ei;
777       FOR_EACH_EDGE (e, ei, bb->succs)
778         e->aux = NULL;
779     }
780 }
781
782 /* Free data allocated in edge_aux_obstack and clear AUX pointers
783    of all edges.  */
784
785 void
786 free_aux_for_edges (void)
787 {
788   gcc_assert (first_edge_aux_obj);
789   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
790   first_edge_aux_obj = NULL;
791
792   clear_aux_for_edges ();
793 }
794
795 void
796 debug_bb (basic_block bb)
797 {
798   dump_bb (bb, stderr, 0);
799 }
800
801 basic_block
802 debug_bb_n (int n)
803 {
804   basic_block bb = BASIC_BLOCK (n);
805   dump_bb (bb, stderr, 0);
806   return bb;
807 }
808
809 /* Dumps cfg related information about basic block BB to FILE.  */
810
811 static void
812 dump_cfg_bb_info (FILE *file, basic_block bb)
813 {
814   unsigned i;
815   edge_iterator ei;
816   bool first = true;
817   static const char * const bb_bitnames[] =
818     {
819       "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock"
820     };
821   const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
822   edge e;
823
824   fprintf (file, "Basic block %d", bb->index);
825   for (i = 0; i < n_bitnames; i++)
826     if (bb->flags & (1 << i))
827       {
828         if (first)
829           fprintf (file, " (");
830         else
831           fprintf (file, ", ");
832         first = false;
833         fprintf (file, bb_bitnames[i]);
834       }
835   if (!first)
836     fprintf (file, ")");
837   fprintf (file, "\n");
838
839   fprintf (file, "Predecessors: ");
840   FOR_EACH_EDGE (e, ei, bb->preds)
841     dump_edge_info (file, e, 0);
842
843   fprintf (file, "\nSuccessors: ");
844   FOR_EACH_EDGE (e, ei, bb->succs)
845     dump_edge_info (file, e, 1);
846   fprintf (file, "\n\n");
847 }
848
849 /* Dumps a brief description of cfg to FILE.  */
850
851 void
852 brief_dump_cfg (FILE *file)
853 {
854   basic_block bb;
855
856   FOR_EACH_BB (bb)
857     {
858       dump_cfg_bb_info (file, bb);
859     }
860 }
861
862 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
863    leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
864    redirected to destination of TAKEN_EDGE. 
865
866    This function may leave the profile inconsistent in the case TAKEN_EDGE
867    frequency or count is believed to be lower than FREQUENCY or COUNT
868    respectively.  */
869 void
870 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
871                                  gcov_type count, edge taken_edge)
872 {
873   edge c;
874   int prob;
875   edge_iterator ei;
876
877   bb->count -= count;
878   if (bb->count < 0)
879     {
880       if (dump_file)
881         fprintf (dump_file, "bb %i count became negative after threading",
882                  bb->index);
883       bb->count = 0;
884     }
885
886   /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
887      Watch for overflows.  */
888   if (bb->frequency)
889     prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
890   else
891     prob = 0;
892   if (prob > taken_edge->probability)
893     {
894       if (dump_file)
895         fprintf (dump_file, "Jump threading proved probability of edge "
896                  "%i->%i too small (it is %i, should be %i).\n",
897                  taken_edge->src->index, taken_edge->dest->index,
898                  taken_edge->probability, prob);
899       prob = taken_edge->probability;
900     }
901
902   /* Now rescale the probabilities.  */
903   taken_edge->probability -= prob;
904   prob = REG_BR_PROB_BASE - prob;
905   bb->frequency -= edge_frequency;
906   if (bb->frequency < 0)
907     bb->frequency = 0;
908   if (prob <= 0)
909     {
910       if (dump_file)
911         fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
912                  "frequency of block should end up being 0, it is %i\n",
913                  bb->index, bb->frequency);
914       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
915       ei = ei_start (bb->succs);
916       ei_next (&ei);
917       for (; (c = ei_safe_edge (ei)); ei_next (&ei))
918         c->probability = 0;
919     }
920   else if (prob != REG_BR_PROB_BASE)
921     {
922       int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
923
924       FOR_EACH_EDGE (c, ei, bb->succs)
925         {
926           c->probability = RDIV (c->probability * scale, 65536);
927           if (c->probability > REG_BR_PROB_BASE)
928             c->probability = REG_BR_PROB_BASE;
929         }
930     }
931
932   gcc_assert (bb == taken_edge->src);
933   taken_edge->count -= count;
934   if (taken_edge->count < 0)
935     {
936       if (dump_file)
937         fprintf (dump_file, "edge %i->%i count became negative after threading",
938                  taken_edge->src->index, taken_edge->dest->index);
939       taken_edge->count = 0;
940     }
941 }
942
943 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
944    by NUM/DEN, in int arithmetic.  May lose some accuracy.  */
945 void
946 scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
947 {
948   int i;
949   edge e;
950   if (num < 0)
951     num = 0;
952   if (num > den)
953     return;
954   /* Assume that the users are producing the fraction from frequencies
955      that never grow far enough to risk arithmetic overflow.  */
956   gcc_assert (num < 65536);
957   for (i = 0; i < nbbs; i++)
958     {
959       edge_iterator ei;
960       bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
961       bbs[i]->count = RDIV (bbs[i]->count * num, den);
962       FOR_EACH_EDGE (e, ei, bbs[i]->succs)
963         e->count = RDIV (e->count * num, den);
964     }
965 }
966
967 /* numbers smaller than this value are safe to multiply without getting
968    64bit overflow.  */
969 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
970
971 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
972    by NUM/DEN, in gcov_type arithmetic.  More accurate than previous
973    function but considerably slower.  */
974 void
975 scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num, 
976                                  gcov_type den)
977 {
978   int i;
979   edge e;
980   gcov_type fraction = RDIV (num * 65536, den);
981
982   gcc_assert (fraction >= 0);
983
984   if (num < MAX_SAFE_MULTIPLIER)
985     for (i = 0; i < nbbs; i++)
986       {
987         edge_iterator ei;
988         bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
989         if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
990           bbs[i]->count = RDIV (bbs[i]->count * num, den);
991         else
992           bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
993         FOR_EACH_EDGE (e, ei, bbs[i]->succs)
994           if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
995             e->count = RDIV (e->count * num, den);
996           else
997             e->count = RDIV (e->count * fraction, 65536);
998       }
999    else
1000     for (i = 0; i < nbbs; i++)
1001       {
1002         edge_iterator ei;
1003         if (sizeof (gcov_type) > sizeof (int))
1004           bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1005         else
1006           bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
1007         bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1008         FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1009           e->count = RDIV (e->count * fraction, 65536);
1010       }
1011 }
1012
1013 /* Data structures used to maintain mapping between basic blocks and
1014    copies.  */
1015 static htab_t bb_original;
1016 static htab_t bb_copy;
1017 static alloc_pool original_copy_bb_pool;
1018
1019 struct htab_bb_copy_original_entry
1020 {
1021   /* Block we are attaching info to.  */
1022   int index1;
1023   /* Index of original or copy (depending on the hashtable) */
1024   int index2;
1025 };
1026
1027 static hashval_t
1028 bb_copy_original_hash (const void *p)
1029 {
1030   struct htab_bb_copy_original_entry *data
1031     = ((struct htab_bb_copy_original_entry *)p);
1032
1033   return data->index1;
1034 }
1035 static int
1036 bb_copy_original_eq (const void *p, const void *q)
1037 {
1038   struct htab_bb_copy_original_entry *data
1039     = ((struct htab_bb_copy_original_entry *)p);
1040   struct htab_bb_copy_original_entry *data2
1041     = ((struct htab_bb_copy_original_entry *)q);
1042
1043   return data->index1 == data2->index1;
1044 }
1045
1046 /* Initialize the data structures to maintain mapping between blocks
1047    and its copies.  */
1048 void
1049 initialize_original_copy_tables (void)
1050 {
1051   gcc_assert (!original_copy_bb_pool);
1052   original_copy_bb_pool
1053     = create_alloc_pool ("original_copy",
1054                          sizeof (struct htab_bb_copy_original_entry), 10);
1055   bb_original = htab_create (10, bb_copy_original_hash,
1056                              bb_copy_original_eq, NULL);
1057   bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1058 }
1059
1060 /* Free the data structures to maintain mapping between blocks and
1061    its copies.  */
1062 void
1063 free_original_copy_tables (void)
1064 {
1065   gcc_assert (original_copy_bb_pool);
1066   htab_delete (bb_copy);
1067   htab_delete (bb_original);
1068   free_alloc_pool (original_copy_bb_pool);
1069   bb_copy = NULL;
1070   bb_original = NULL;
1071   original_copy_bb_pool = NULL;
1072 }
1073
1074 /* Set original for basic block.  Do nothing when data structures are not
1075    initialized so passes not needing this don't need to care.  */
1076 void
1077 set_bb_original (basic_block bb, basic_block original)
1078 {
1079   if (original_copy_bb_pool)
1080     {
1081       struct htab_bb_copy_original_entry **slot;
1082       struct htab_bb_copy_original_entry key;
1083
1084       key.index1 = bb->index;
1085       slot =
1086         (struct htab_bb_copy_original_entry **) htab_find_slot (bb_original,
1087                                                                &key, INSERT);
1088       if (*slot)
1089         (*slot)->index2 = original->index;
1090       else
1091         {
1092           *slot = pool_alloc (original_copy_bb_pool);
1093           (*slot)->index1 = bb->index;
1094           (*slot)->index2 = original->index;
1095         }
1096     }
1097 }
1098
1099 /* Get the original basic block.  */
1100 basic_block
1101 get_bb_original (basic_block bb)
1102 {
1103   struct htab_bb_copy_original_entry *entry;
1104   struct htab_bb_copy_original_entry key;
1105
1106   gcc_assert (original_copy_bb_pool);
1107
1108   key.index1 = bb->index;
1109   entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
1110   if (entry)
1111     return BASIC_BLOCK (entry->index2);
1112   else
1113     return NULL;
1114 }
1115
1116 /* Set copy for basic block.  Do nothing when data structures are not
1117    initialized so passes not needing this don't need to care.  */
1118 void
1119 set_bb_copy (basic_block bb, basic_block copy)
1120 {
1121   if (original_copy_bb_pool)
1122     {
1123       struct htab_bb_copy_original_entry **slot;
1124       struct htab_bb_copy_original_entry key;
1125
1126       key.index1 = bb->index;
1127       slot =
1128         (struct htab_bb_copy_original_entry **) htab_find_slot (bb_copy,
1129                                                                &key, INSERT);
1130       if (*slot)
1131         (*slot)->index2 = copy->index;
1132       else
1133         {
1134           *slot = pool_alloc (original_copy_bb_pool);
1135           (*slot)->index1 = bb->index;
1136           (*slot)->index2 = copy->index;
1137         }
1138     }
1139 }
1140
1141 /* Get the copy of basic block.  */
1142 basic_block
1143 get_bb_copy (basic_block bb)
1144 {
1145   struct htab_bb_copy_original_entry *entry;
1146   struct htab_bb_copy_original_entry key;
1147
1148   gcc_assert (original_copy_bb_pool);
1149
1150   key.index1 = bb->index;
1151   entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
1152   if (entry)
1153     return BASIC_BLOCK (entry->index2);
1154   else
1155     return NULL;
1156 }