OSDN Git Service

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