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