OSDN Git Service

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