Mercurial > hg > CbC > CbC_gcc

comparison gcc/cfg.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
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
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
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
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
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
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
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
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
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 }