OSDN Git Service

* cfg.c (dump_cfg_bb_info): Update bb_bitnames to match enum.
[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       "new", "reachable", "irreducible_loop", "superblock",
885       "nosched", "hot", "cold", "dup", "xlabel", "rtl",
886       "fwdr", "nothrd"
887     };
888   const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
889   edge e;
890
891   fprintf (file, "Basic block %d", bb->index);
892   for (i = 0; i < n_bitnames; i++)
893     if (bb->flags & (1 << i))
894       {
895         if (first)
896           fprintf (file, " (");
897         else
898           fprintf (file, ", ");
899         first = false;
900         fprintf (file, bb_bitnames[i]);
901       }
902   if (!first)
903     fprintf (file, ")");
904   fprintf (file, "\n");
905
906   fprintf (file, "Predecessors: ");
907   FOR_EACH_EDGE (e, ei, bb->preds)
908     dump_edge_info (file, e, 0);
909
910   fprintf (file, "\nSuccessors: ");
911   FOR_EACH_EDGE (e, ei, bb->succs)
912     dump_edge_info (file, e, 1);
913   fprintf (file, "\n\n");
914 }
915
916 /* Dumps a brief description of cfg to FILE.  */
917
918 void
919 brief_dump_cfg (FILE *file)
920 {
921   basic_block bb;
922
923   FOR_EACH_BB (bb)
924     {
925       dump_cfg_bb_info (file, bb);
926     }
927 }
928
929 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
930    leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
931    redirected to destination of TAKEN_EDGE.
932
933    This function may leave the profile inconsistent in the case TAKEN_EDGE
934    frequency or count is believed to be lower than FREQUENCY or COUNT
935    respectively.  */
936 void
937 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
938                                  gcov_type count, edge taken_edge)
939 {
940   edge c;
941   int prob;
942   edge_iterator ei;
943
944   bb->count -= count;
945   if (bb->count < 0)
946     {
947       if (dump_file)
948         fprintf (dump_file, "bb %i count became negative after threading",
949                  bb->index);
950       bb->count = 0;
951     }
952
953   /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
954      Watch for overflows.  */
955   if (bb->frequency)
956     prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
957   else
958     prob = 0;
959   if (prob > taken_edge->probability)
960     {
961       if (dump_file)
962         fprintf (dump_file, "Jump threading proved probability of edge "
963                  "%i->%i too small (it is %i, should be %i).\n",
964                  taken_edge->src->index, taken_edge->dest->index,
965                  taken_edge->probability, prob);
966       prob = taken_edge->probability;
967     }
968
969   /* Now rescale the probabilities.  */
970   taken_edge->probability -= prob;
971   prob = REG_BR_PROB_BASE - prob;
972   bb->frequency -= edge_frequency;
973   if (bb->frequency < 0)
974     bb->frequency = 0;
975   if (prob <= 0)
976     {
977       if (dump_file)
978         fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
979                  "frequency of block should end up being 0, it is %i\n",
980                  bb->index, bb->frequency);
981       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
982       ei = ei_start (bb->succs);
983       ei_next (&ei);
984       for (; (c = ei_safe_edge (ei)); ei_next (&ei))
985         c->probability = 0;
986     }
987   else if (prob != REG_BR_PROB_BASE)
988     {
989       int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
990
991       FOR_EACH_EDGE (c, ei, bb->succs)
992         {
993           c->probability = RDIV (c->probability * scale, 65536);
994           if (c->probability > REG_BR_PROB_BASE)
995             c->probability = REG_BR_PROB_BASE;
996         }
997     }
998
999   gcc_assert (bb == taken_edge->src);
1000   taken_edge->count -= count;
1001   if (taken_edge->count < 0)
1002     {
1003       if (dump_file)
1004         fprintf (dump_file, "edge %i->%i count became negative after threading",
1005                  taken_edge->src->index, taken_edge->dest->index);
1006       taken_edge->count = 0;
1007     }
1008 }
1009
1010 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1011    by NUM/DEN, in int arithmetic.  May lose some accuracy.  */
1012 void
1013 scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
1014 {
1015   int i;
1016   edge e;
1017   if (num < 0)
1018     num = 0;
1019
1020   /* Scale NUM and DEN to avoid overflows.  Frequencies are in order of
1021      10^4, if we make DEN <= 10^3, we can afford to upscale by 100
1022      and still safely fit in int during calculations.  */
1023   if (den > 1000)
1024     {
1025       if (num > 1000000)
1026         return;
1027
1028       num = RDIV (1000 * num, den);
1029       den = 1000;
1030     }
1031   if (num > 100 * den)
1032     return;
1033
1034   for (i = 0; i < nbbs; i++)
1035     {
1036       edge_iterator ei;
1037       bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1038       /* Make sure the frequencies do not grow over BB_FREQ_MAX.  */
1039       if (bbs[i]->frequency > BB_FREQ_MAX)
1040         bbs[i]->frequency = BB_FREQ_MAX;
1041       bbs[i]->count = RDIV (bbs[i]->count * num, den);
1042       FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1043         e->count = RDIV (e->count * num, den);
1044     }
1045 }
1046
1047 /* numbers smaller than this value are safe to multiply without getting
1048    64bit overflow.  */
1049 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
1050
1051 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1052    by NUM/DEN, in gcov_type arithmetic.  More accurate than previous
1053    function but considerably slower.  */
1054 void
1055 scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
1056                                  gcov_type den)
1057 {
1058   int i;
1059   edge e;
1060   gcov_type fraction = RDIV (num * 65536, den);
1061
1062   gcc_assert (fraction >= 0);
1063
1064   if (num < MAX_SAFE_MULTIPLIER)
1065     for (i = 0; i < nbbs; i++)
1066       {
1067         edge_iterator ei;
1068         bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1069         if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1070           bbs[i]->count = RDIV (bbs[i]->count * num, den);
1071         else
1072           bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1073         FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1074           if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1075             e->count = RDIV (e->count * num, den);
1076           else
1077             e->count = RDIV (e->count * fraction, 65536);
1078       }
1079    else
1080     for (i = 0; i < nbbs; i++)
1081       {
1082         edge_iterator ei;
1083         if (sizeof (gcov_type) > sizeof (int))
1084           bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1085         else
1086           bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
1087         bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1088         FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1089           e->count = RDIV (e->count * fraction, 65536);
1090       }
1091 }
1092
1093 /* Data structures used to maintain mapping between basic blocks and
1094    copies.  */
1095 static htab_t bb_original;
1096 static htab_t bb_copy;
1097
1098 /* And between loops and copies.  */
1099 static htab_t loop_copy;
1100 static alloc_pool original_copy_bb_pool;
1101
1102 struct htab_bb_copy_original_entry
1103 {
1104   /* Block we are attaching info to.  */
1105   int index1;
1106   /* Index of original or copy (depending on the hashtable) */
1107   int index2;
1108 };
1109
1110 static hashval_t
1111 bb_copy_original_hash (const void *p)
1112 {
1113   const struct htab_bb_copy_original_entry *data
1114     = ((const struct htab_bb_copy_original_entry *)p);
1115
1116   return data->index1;
1117 }
1118 static int
1119 bb_copy_original_eq (const void *p, const void *q)
1120 {
1121   const struct htab_bb_copy_original_entry *data
1122     = ((const struct htab_bb_copy_original_entry *)p);
1123   const struct htab_bb_copy_original_entry *data2
1124     = ((const struct htab_bb_copy_original_entry *)q);
1125
1126   return data->index1 == data2->index1;
1127 }
1128
1129 /* Initialize the data structures to maintain mapping between blocks
1130    and its copies.  */
1131 void
1132 initialize_original_copy_tables (void)
1133 {
1134   gcc_assert (!original_copy_bb_pool);
1135   original_copy_bb_pool
1136     = create_alloc_pool ("original_copy",
1137                          sizeof (struct htab_bb_copy_original_entry), 10);
1138   bb_original = htab_create (10, bb_copy_original_hash,
1139                              bb_copy_original_eq, NULL);
1140   bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1141   loop_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1142 }
1143
1144 /* Free the data structures to maintain mapping between blocks and
1145    its copies.  */
1146 void
1147 free_original_copy_tables (void)
1148 {
1149   gcc_assert (original_copy_bb_pool);
1150   htab_delete (bb_copy);
1151   htab_delete (bb_original);
1152   htab_delete (loop_copy);
1153   free_alloc_pool (original_copy_bb_pool);
1154   bb_copy = NULL;
1155   bb_original = NULL;
1156   loop_copy = NULL;
1157   original_copy_bb_pool = NULL;
1158 }
1159
1160 /* Removes the value associated with OBJ from table TAB.  */
1161
1162 static void
1163 copy_original_table_clear (htab_t tab, unsigned obj)
1164 {
1165   void **slot;
1166   struct htab_bb_copy_original_entry key, *elt;
1167
1168   if (!original_copy_bb_pool)
1169     return;
1170
1171   key.index1 = obj;
1172   slot = htab_find_slot (tab, &key, NO_INSERT);
1173   if (!slot)
1174     return;
1175
1176   elt = (struct htab_bb_copy_original_entry *) *slot;
1177   htab_clear_slot (tab, slot);
1178   pool_free (original_copy_bb_pool, elt);
1179 }
1180
1181 /* Sets the value associated with OBJ in table TAB to VAL.
1182    Do nothing when data structures are not initialized.  */
1183
1184 static void
1185 copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
1186 {
1187   struct htab_bb_copy_original_entry **slot;
1188   struct htab_bb_copy_original_entry key;
1189
1190   if (!original_copy_bb_pool)
1191     return;
1192
1193   key.index1 = obj;
1194   slot = (struct htab_bb_copy_original_entry **)
1195                 htab_find_slot (tab, &key, INSERT);
1196   if (!*slot)
1197     {
1198       *slot = (struct htab_bb_copy_original_entry *)
1199                 pool_alloc (original_copy_bb_pool);
1200       (*slot)->index1 = obj;
1201     }
1202   (*slot)->index2 = val;
1203 }
1204
1205 /* Set original for basic block.  Do nothing when data structures are not
1206    initialized so passes not needing this don't need to care.  */
1207 void
1208 set_bb_original (basic_block bb, basic_block original)
1209 {
1210   copy_original_table_set (bb_original, bb->index, original->index);
1211 }
1212
1213 /* Get the original basic block.  */
1214 basic_block
1215 get_bb_original (basic_block bb)
1216 {
1217   struct htab_bb_copy_original_entry *entry;
1218   struct htab_bb_copy_original_entry key;
1219
1220   gcc_assert (original_copy_bb_pool);
1221
1222   key.index1 = bb->index;
1223   entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
1224   if (entry)
1225     return BASIC_BLOCK (entry->index2);
1226   else
1227     return NULL;
1228 }
1229
1230 /* Set copy for basic block.  Do nothing when data structures are not
1231    initialized so passes not needing this don't need to care.  */
1232 void
1233 set_bb_copy (basic_block bb, basic_block copy)
1234 {
1235   copy_original_table_set (bb_copy, bb->index, copy->index);
1236 }
1237
1238 /* Get the copy of basic block.  */
1239 basic_block
1240 get_bb_copy (basic_block bb)
1241 {
1242   struct htab_bb_copy_original_entry *entry;
1243   struct htab_bb_copy_original_entry key;
1244
1245   gcc_assert (original_copy_bb_pool);
1246
1247   key.index1 = bb->index;
1248   entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
1249   if (entry)
1250     return BASIC_BLOCK (entry->index2);
1251   else
1252     return NULL;
1253 }
1254
1255 /* Set copy for LOOP to COPY.  Do nothing when data structures are not
1256    initialized so passes not needing this don't need to care.  */
1257
1258 void
1259 set_loop_copy (struct loop *loop, struct loop *copy)
1260 {
1261   if (!copy)
1262     copy_original_table_clear (loop_copy, loop->num);
1263   else
1264     copy_original_table_set (loop_copy, loop->num, copy->num);
1265 }
1266
1267 /* Get the copy of LOOP.  */
1268
1269 struct loop *
1270 get_loop_copy (struct loop *loop)
1271 {
1272   struct htab_bb_copy_original_entry *entry;
1273   struct htab_bb_copy_original_entry key;
1274
1275   gcc_assert (original_copy_bb_pool);
1276
1277   key.index1 = loop->num;
1278   entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy, &key);
1279   if (entry)
1280     return get_loop (entry->index2);
1281   else
1282     return NULL;
1283 }