]>
Commit | Line | Data |
---|---|---|
402209ff JH |
1 | /* Control flow graph manipulation code for GNU compiler. |
2 | Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, | |
d329e058 | 3 | 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc. |
402209ff JH |
4 | |
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it under | |
8 | the terms of the GNU General Public License as published by the Free | |
9 | Software Foundation; either version 2, or (at your option) any later | |
10 | version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING. If not, write to the Free | |
19 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
20 | 02111-1307, USA. */ | |
21 | ||
9d083c8c | 22 | /* This file contains low level functions to manipulate the CFG and |
4d6922ee | 23 | analyze it. All other modules should not transform the data structure |
9d083c8c RS |
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). | |
402209ff JH |
27 | |
28 | Available functionality: | |
29 | - Initialization/deallocation | |
30 | init_flow, clear_edges | |
ca6c03ca JH |
31 | - Low level basic block manipulation |
32 | alloc_block, expunge_block | |
402209ff | 33 | - Edge manipulation |
7ded4467 | 34 | make_edge, make_single_succ_edge, cached_make_edge, remove_edge |
402209ff JH |
35 | - Low level edge redirection (without updating instruction chain) |
36 | redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred | |
eaec9b3d | 37 | - Dumping and debugging |
ca6c03ca JH |
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 | |
38c1593d | 41 | - clear_bb_flags |
10e9fecc JH |
42 | - Consistency checking |
43 | verify_flow_info | |
44 | - Dumping and debugging | |
45 | print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n | |
402209ff JH |
46 | */ |
47 | \f | |
48 | #include "config.h" | |
49 | #include "system.h" | |
4977bab6 ZW |
50 | #include "coretypes.h" |
51 | #include "tm.h" | |
402209ff JH |
52 | #include "tree.h" |
53 | #include "rtl.h" | |
54 | #include "hard-reg-set.h" | |
55 | #include "basic-block.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" | |
3d9339a9 | 62 | #include "tm_p.h" |
402209ff | 63 | #include "obstack.h" |
f6cb56fa | 64 | #include "alloc-pool.h" |
402209ff JH |
65 | |
66 | /* The obstack on which the flow graph components are allocated. */ | |
67 | ||
68 | struct obstack flow_obstack; | |
69 | static char *flow_firstobj; | |
70 | ||
f6cb56fa DB |
71 | /* Basic block object pool. */ |
72 | ||
73 | static alloc_pool bb_pool; | |
74 | ||
75 | /* Edge object pool. */ | |
76 | ||
77 | static alloc_pool edge_pool; | |
78 | ||
402209ff JH |
79 | /* Number of basic blocks in the current function. */ |
80 | ||
0b17ab2f | 81 | int n_basic_blocks; |
402209ff | 82 | |
bf77398c ZD |
83 | /* First free basic block number. */ |
84 | ||
85 | int last_basic_block; | |
86 | ||
402209ff JH |
87 | /* Number of edges in the current function. */ |
88 | ||
89 | int n_edges; | |
90 | ||
91 | /* The basic block array. */ | |
92 | ||
93 | varray_type basic_block_info; | |
94 | ||
95 | /* The special entry and exit blocks. */ | |
96 | ||
97 | struct basic_block_def entry_exit_blocks[2] | |
98 | = {{NULL, /* head */ | |
99 | NULL, /* end */ | |
100 | NULL, /* head_tree */ | |
101 | NULL, /* end_tree */ | |
102 | NULL, /* pred */ | |
103 | NULL, /* succ */ | |
104 | NULL, /* local_set */ | |
105 | NULL, /* cond_local_set */ | |
106 | NULL, /* global_live_at_start */ | |
107 | NULL, /* global_live_at_end */ | |
108 | NULL, /* aux */ | |
109 | ENTRY_BLOCK, /* index */ | |
918ed612 ZD |
110 | NULL, /* prev_bb */ |
111 | EXIT_BLOCK_PTR, /* next_bb */ | |
402209ff | 112 | 0, /* loop_depth */ |
2ecfd709 | 113 | NULL, /* loop_father */ |
402209ff JH |
114 | 0, /* count */ |
115 | 0, /* frequency */ | |
bc35512f JH |
116 | 0, /* flags */ |
117 | NULL /* rbi */ | |
402209ff JH |
118 | }, |
119 | { | |
120 | NULL, /* head */ | |
121 | NULL, /* end */ | |
122 | NULL, /* head_tree */ | |
123 | NULL, /* end_tree */ | |
124 | NULL, /* pred */ | |
125 | NULL, /* succ */ | |
126 | NULL, /* local_set */ | |
127 | NULL, /* cond_local_set */ | |
128 | NULL, /* global_live_at_start */ | |
129 | NULL, /* global_live_at_end */ | |
130 | NULL, /* aux */ | |
131 | EXIT_BLOCK, /* index */ | |
918ed612 ZD |
132 | ENTRY_BLOCK_PTR, /* prev_bb */ |
133 | NULL, /* next_bb */ | |
402209ff | 134 | 0, /* loop_depth */ |
2ecfd709 | 135 | NULL, /* loop_father */ |
402209ff JH |
136 | 0, /* count */ |
137 | 0, /* frequency */ | |
bc35512f JH |
138 | 0, /* flags */ |
139 | NULL /* rbi */ | |
402209ff JH |
140 | } |
141 | }; | |
142 | ||
d329e058 AJ |
143 | void debug_flow_info (void); |
144 | static void free_edge (edge); | |
402209ff | 145 | \f |
eaec9b3d | 146 | /* Called once at initialization time. */ |
402209ff JH |
147 | |
148 | void | |
d329e058 | 149 | init_flow (void) |
402209ff JH |
150 | { |
151 | static int initialized; | |
152 | ||
7ded4467 JH |
153 | n_edges = 0; |
154 | ||
402209ff JH |
155 | if (!initialized) |
156 | { | |
157 | gcc_obstack_init (&flow_obstack); | |
158 | flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0); | |
159 | initialized = 1; | |
160 | } | |
161 | else | |
162 | { | |
f6cb56fa DB |
163 | free_alloc_pool (bb_pool); |
164 | free_alloc_pool (edge_pool); | |
402209ff JH |
165 | obstack_free (&flow_obstack, flow_firstobj); |
166 | flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0); | |
167 | } | |
d329e058 | 168 | bb_pool = create_alloc_pool ("Basic block pool", |
f6cb56fa DB |
169 | sizeof (struct basic_block_def), 100); |
170 | edge_pool = create_alloc_pool ("Edge pool", | |
171 | sizeof (struct edge_def), 100); | |
402209ff JH |
172 | } |
173 | \f | |
d39ac0fd JH |
174 | /* Helper function for remove_edge and clear_edges. Frees edge structure |
175 | without actually unlinking it from the pred/succ lists. */ | |
176 | ||
177 | static void | |
d329e058 | 178 | free_edge (edge e) |
d39ac0fd JH |
179 | { |
180 | n_edges--; | |
f6cb56fa | 181 | pool_free (edge_pool, e); |
d39ac0fd JH |
182 | } |
183 | ||
402209ff JH |
184 | /* Free the memory associated with the edge structures. */ |
185 | ||
186 | void | |
d329e058 | 187 | clear_edges (void) |
402209ff | 188 | { |
e0082a72 | 189 | basic_block bb; |
d39ac0fd | 190 | edge e; |
402209ff | 191 | |
e0082a72 | 192 | FOR_EACH_BB (bb) |
402209ff | 193 | { |
d39ac0fd | 194 | edge e = bb->succ; |
402209ff | 195 | |
d39ac0fd JH |
196 | while (e) |
197 | { | |
198 | edge next = e->succ_next; | |
199 | ||
200 | free_edge (e); | |
201 | e = next; | |
202 | } | |
4891442b | 203 | |
d39ac0fd JH |
204 | bb->succ = NULL; |
205 | bb->pred = NULL; | |
402209ff JH |
206 | } |
207 | ||
d39ac0fd JH |
208 | e = ENTRY_BLOCK_PTR->succ; |
209 | while (e) | |
210 | { | |
211 | edge next = e->succ_next; | |
212 | ||
213 | free_edge (e); | |
214 | e = next; | |
215 | } | |
4891442b | 216 | |
d39ac0fd JH |
217 | EXIT_BLOCK_PTR->pred = NULL; |
218 | ENTRY_BLOCK_PTR->succ = NULL; | |
402209ff | 219 | |
7ded4467 JH |
220 | if (n_edges) |
221 | abort (); | |
402209ff JH |
222 | } |
223 | \f | |
ca6c03ca | 224 | /* Allocate memory for basic_block. */ |
402209ff | 225 | |
4262e623 | 226 | basic_block |
d329e058 | 227 | alloc_block (void) |
402209ff JH |
228 | { |
229 | basic_block bb; | |
f6cb56fa DB |
230 | bb = pool_alloc (bb_pool); |
231 | memset (bb, 0, sizeof (*bb)); | |
4262e623 | 232 | return bb; |
402209ff JH |
233 | } |
234 | ||
918ed612 ZD |
235 | /* Link block B to chain after AFTER. */ |
236 | void | |
d329e058 | 237 | link_block (basic_block b, basic_block after) |
918ed612 ZD |
238 | { |
239 | b->next_bb = after->next_bb; | |
240 | b->prev_bb = after; | |
241 | after->next_bb = b; | |
242 | b->next_bb->prev_bb = b; | |
243 | } | |
f87c27b4 | 244 | |
918ed612 ZD |
245 | /* Unlink block B from chain. */ |
246 | void | |
d329e058 | 247 | unlink_block (basic_block b) |
918ed612 ZD |
248 | { |
249 | b->next_bb->prev_bb = b->prev_bb; | |
250 | b->prev_bb->next_bb = b->next_bb; | |
251 | } | |
f87c27b4 | 252 | |
bf77398c ZD |
253 | /* Sequentially order blocks and compact the arrays. */ |
254 | void | |
d329e058 | 255 | compact_blocks (void) |
bf77398c ZD |
256 | { |
257 | int i; | |
258 | basic_block bb; | |
d329e058 | 259 | |
bf77398c ZD |
260 | i = 0; |
261 | FOR_EACH_BB (bb) | |
262 | { | |
263 | BASIC_BLOCK (i) = bb; | |
264 | bb->index = i; | |
265 | i++; | |
266 | } | |
267 | ||
268 | if (i != n_basic_blocks) | |
269 | abort (); | |
270 | ||
271 | last_basic_block = n_basic_blocks; | |
272 | } | |
273 | ||
bf77398c | 274 | /* Remove block B from the basic block array. */ |
402209ff | 275 | |
6a58eee9 | 276 | void |
d329e058 | 277 | expunge_block (basic_block b) |
6a58eee9 | 278 | { |
918ed612 | 279 | unlink_block (b); |
bf77398c ZD |
280 | BASIC_BLOCK (b->index) = NULL; |
281 | n_basic_blocks--; | |
f6cb56fa | 282 | pool_free (bb_pool, b); |
6a58eee9 | 283 | } |
402209ff | 284 | \f |
e0fd3e7a MM |
285 | /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly |
286 | created edge. Use this only if you are sure that this edge can't | |
287 | possibly already exist. */ | |
288 | ||
289 | edge | |
d329e058 | 290 | unchecked_make_edge (basic_block src, basic_block dst, int flags) |
e0fd3e7a MM |
291 | { |
292 | edge e; | |
293 | e = pool_alloc (edge_pool); | |
294 | memset (e, 0, sizeof (*e)); | |
295 | n_edges++; | |
296 | ||
297 | e->succ_next = src->succ; | |
298 | e->pred_next = dst->pred; | |
299 | e->src = src; | |
300 | e->dest = dst; | |
301 | e->flags = flags; | |
302 | ||
303 | src->succ = e; | |
304 | dst->pred = e; | |
305 | ||
306 | return e; | |
307 | } | |
308 | ||
7ded4467 | 309 | /* Create an edge connecting SRC and DST with FLAGS optionally using |
2ba84f36 | 310 | edge cache CACHE. Return the new edge, NULL if already exist. */ |
4262e623 | 311 | |
7ded4467 | 312 | edge |
d329e058 | 313 | cached_make_edge (sbitmap *edge_cache, basic_block src, basic_block dst, int flags) |
402209ff JH |
314 | { |
315 | int use_edge_cache; | |
316 | edge e; | |
317 | ||
4891442b RK |
318 | /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that |
319 | many edges to them, or we didn't allocate memory for it. */ | |
402209ff | 320 | use_edge_cache = (edge_cache |
4891442b | 321 | && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR); |
402209ff JH |
322 | |
323 | /* Make sure we don't add duplicate edges. */ | |
324 | switch (use_edge_cache) | |
325 | { | |
326 | default: | |
ff7cc307 | 327 | /* Quick test for non-existence of the edge. */ |
0b17ab2f | 328 | if (! TEST_BIT (edge_cache[src->index], dst->index)) |
402209ff JH |
329 | break; |
330 | ||
331 | /* The edge exists; early exit if no work to do. */ | |
332 | if (flags == 0) | |
7ded4467 | 333 | return NULL; |
402209ff JH |
334 | |
335 | /* FALLTHRU */ | |
336 | case 0: | |
337 | for (e = src->succ; e; e = e->succ_next) | |
338 | if (e->dest == dst) | |
339 | { | |
340 | e->flags |= flags; | |
7ded4467 | 341 | return NULL; |
402209ff JH |
342 | } |
343 | break; | |
344 | } | |
d329e058 | 345 | |
e0fd3e7a | 346 | e = unchecked_make_edge (src, dst, flags); |
402209ff JH |
347 | |
348 | if (use_edge_cache) | |
0b17ab2f | 349 | SET_BIT (edge_cache[src->index], dst->index); |
7ded4467 JH |
350 | |
351 | return e; | |
352 | } | |
353 | ||
354 | /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly | |
355 | created edge or NULL if already exist. */ | |
356 | ||
357 | edge | |
d329e058 | 358 | make_edge (basic_block src, basic_block dest, int flags) |
7ded4467 JH |
359 | { |
360 | return cached_make_edge (NULL, src, dest, flags); | |
361 | } | |
362 | ||
eaec9b3d | 363 | /* Create an edge connecting SRC to DEST and set probability by knowing |
7ded4467 JH |
364 | that it is the single edge leaving SRC. */ |
365 | ||
366 | edge | |
d329e058 | 367 | make_single_succ_edge (basic_block src, basic_block dest, int flags) |
7ded4467 JH |
368 | { |
369 | edge e = make_edge (src, dest, flags); | |
370 | ||
371 | e->probability = REG_BR_PROB_BASE; | |
372 | e->count = src->count; | |
373 | return e; | |
402209ff JH |
374 | } |
375 | ||
376 | /* This function will remove an edge from the flow graph. */ | |
377 | ||
378 | void | |
d329e058 | 379 | remove_edge (edge e) |
402209ff JH |
380 | { |
381 | edge last_pred = NULL; | |
382 | edge last_succ = NULL; | |
383 | edge tmp; | |
384 | basic_block src, dest; | |
4891442b | 385 | |
402209ff JH |
386 | src = e->src; |
387 | dest = e->dest; | |
388 | for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next) | |
389 | last_succ = tmp; | |
390 | ||
391 | if (!tmp) | |
392 | abort (); | |
393 | if (last_succ) | |
394 | last_succ->succ_next = e->succ_next; | |
395 | else | |
396 | src->succ = e->succ_next; | |
397 | ||
398 | for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next) | |
399 | last_pred = tmp; | |
400 | ||
401 | if (!tmp) | |
402 | abort (); | |
403 | if (last_pred) | |
404 | last_pred->pred_next = e->pred_next; | |
405 | else | |
406 | dest->pred = e->pred_next; | |
407 | ||
d39ac0fd | 408 | free_edge (e); |
402209ff JH |
409 | } |
410 | ||
411 | /* Redirect an edge's successor from one block to another. */ | |
412 | ||
413 | void | |
d329e058 | 414 | redirect_edge_succ (edge e, basic_block new_succ) |
402209ff JH |
415 | { |
416 | edge *pe; | |
417 | ||
418 | /* Disconnect the edge from the old successor block. */ | |
419 | for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next) | |
420 | continue; | |
421 | *pe = (*pe)->pred_next; | |
422 | ||
423 | /* Reconnect the edge to the new successor block. */ | |
424 | e->pred_next = new_succ->pred; | |
425 | new_succ->pred = e; | |
426 | e->dest = new_succ; | |
427 | } | |
428 | ||
eaec9b3d | 429 | /* Like previous but avoid possible duplicate edge. */ |
402209ff JH |
430 | |
431 | edge | |
d329e058 | 432 | redirect_edge_succ_nodup (edge e, basic_block new_succ) |
402209ff JH |
433 | { |
434 | edge s; | |
4891442b | 435 | |
402209ff JH |
436 | /* Check whether the edge is already present. */ |
437 | for (s = e->src->succ; s; s = s->succ_next) | |
438 | if (s->dest == new_succ && s != e) | |
439 | break; | |
4891442b | 440 | |
402209ff JH |
441 | if (s) |
442 | { | |
443 | s->flags |= e->flags; | |
444 | s->probability += e->probability; | |
77abb5d8 JH |
445 | if (s->probability > REG_BR_PROB_BASE) |
446 | s->probability = REG_BR_PROB_BASE; | |
402209ff JH |
447 | s->count += e->count; |
448 | remove_edge (e); | |
449 | e = s; | |
450 | } | |
451 | else | |
452 | redirect_edge_succ (e, new_succ); | |
4891442b | 453 | |
402209ff JH |
454 | return e; |
455 | } | |
456 | ||
457 | /* Redirect an edge's predecessor from one block to another. */ | |
458 | ||
459 | void | |
d329e058 | 460 | redirect_edge_pred (edge e, basic_block new_pred) |
402209ff JH |
461 | { |
462 | edge *pe; | |
463 | ||
464 | /* Disconnect the edge from the old predecessor block. */ | |
465 | for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next) | |
466 | continue; | |
4891442b | 467 | |
402209ff JH |
468 | *pe = (*pe)->succ_next; |
469 | ||
470 | /* Reconnect the edge to the new predecessor block. */ | |
471 | e->succ_next = new_pred->succ; | |
472 | new_pred->succ = e; | |
473 | e->src = new_pred; | |
474 | } | |
38c1593d JH |
475 | |
476 | void | |
d329e058 | 477 | clear_bb_flags (void) |
38c1593d | 478 | { |
e0082a72 ZD |
479 | basic_block bb; |
480 | ||
481 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
482 | bb->flags = 0; | |
38c1593d | 483 | } |
402209ff | 484 | \f |
ca6c03ca | 485 | void |
d329e058 | 486 | dump_flow_info (FILE *file) |
402209ff | 487 | { |
b3694847 | 488 | int i; |
0816bcd2 | 489 | int max_regno = max_reg_num (); |
e0082a72 | 490 | basic_block bb; |
ca6c03ca JH |
491 | static const char * const reg_class_names[] = REG_CLASS_NAMES; |
492 | ||
493 | fprintf (file, "%d registers.\n", max_regno); | |
494 | for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) | |
495 | if (REG_N_REFS (i)) | |
496 | { | |
497 | enum reg_class class, altclass; | |
4891442b | 498 | |
ca6c03ca JH |
499 | fprintf (file, "\nRegister %d used %d times across %d insns", |
500 | i, REG_N_REFS (i), REG_LIVE_LENGTH (i)); | |
501 | if (REG_BASIC_BLOCK (i) >= 0) | |
502 | fprintf (file, " in block %d", REG_BASIC_BLOCK (i)); | |
503 | if (REG_N_SETS (i)) | |
504 | fprintf (file, "; set %d time%s", REG_N_SETS (i), | |
505 | (REG_N_SETS (i) == 1) ? "" : "s"); | |
a106c875 | 506 | if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i])) |
ca6c03ca JH |
507 | fprintf (file, "; user var"); |
508 | if (REG_N_DEATHS (i) != 1) | |
509 | fprintf (file, "; dies in %d places", REG_N_DEATHS (i)); | |
510 | if (REG_N_CALLS_CROSSED (i) == 1) | |
511 | fprintf (file, "; crosses 1 call"); | |
512 | else if (REG_N_CALLS_CROSSED (i)) | |
513 | fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i)); | |
a106c875 HPN |
514 | if (regno_reg_rtx[i] != NULL |
515 | && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD) | |
ca6c03ca | 516 | fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i)); |
4891442b | 517 | |
ca6c03ca JH |
518 | class = reg_preferred_class (i); |
519 | altclass = reg_alternate_class (i); | |
520 | if (class != GENERAL_REGS || altclass != ALL_REGS) | |
521 | { | |
522 | if (altclass == ALL_REGS || class == ALL_REGS) | |
523 | fprintf (file, "; pref %s", reg_class_names[(int) class]); | |
524 | else if (altclass == NO_REGS) | |
525 | fprintf (file, "; %s or none", reg_class_names[(int) class]); | |
526 | else | |
527 | fprintf (file, "; pref %s, else %s", | |
528 | reg_class_names[(int) class], | |
529 | reg_class_names[(int) altclass]); | |
530 | } | |
4891442b | 531 | |
a106c875 | 532 | if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i])) |
ca6c03ca JH |
533 | fprintf (file, "; pointer"); |
534 | fprintf (file, ".\n"); | |
535 | } | |
536 | ||
0b17ab2f | 537 | fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges); |
e0082a72 | 538 | FOR_EACH_BB (bb) |
ca6c03ca | 539 | { |
b3694847 | 540 | edge e; |
5a1a3e5e JH |
541 | int sum; |
542 | gcov_type lsum; | |
ca6c03ca | 543 | |
4891442b | 544 | fprintf (file, "\nBasic block %d: first insn %d, last %d, ", |
04653686 | 545 | bb->index, INSN_UID (bb->head), INSN_UID (bb->end)); |
918ed612 ZD |
546 | fprintf (file, "prev %d, next %d, ", |
547 | bb->prev_bb->index, bb->next_bb->index); | |
4891442b RK |
548 | fprintf (file, "loop_depth %d, count ", bb->loop_depth); |
549 | fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count); | |
0f72964f JH |
550 | fprintf (file, ", freq %i", bb->frequency); |
551 | if (maybe_hot_bb_p (bb)) | |
552 | fprintf (file, ", maybe hot"); | |
553 | if (probably_never_executed_bb_p (bb)) | |
554 | fprintf (file, ", probably never executed"); | |
291cc0fe | 555 | fprintf (file, ".\n"); |
402209ff | 556 | |
ca6c03ca JH |
557 | fprintf (file, "Predecessors: "); |
558 | for (e = bb->pred; e; e = e->pred_next) | |
559 | dump_edge_info (file, e, 0); | |
402209ff | 560 | |
ca6c03ca JH |
561 | fprintf (file, "\nSuccessors: "); |
562 | for (e = bb->succ; e; e = e->succ_next) | |
563 | dump_edge_info (file, e, 1); | |
402209ff | 564 | |
ca6c03ca JH |
565 | fprintf (file, "\nRegisters live at start:"); |
566 | dump_regset (bb->global_live_at_start, file); | |
402209ff | 567 | |
ca6c03ca JH |
568 | fprintf (file, "\nRegisters live at end:"); |
569 | dump_regset (bb->global_live_at_end, file); | |
7ded4467 | 570 | |
ca6c03ca | 571 | putc ('\n', file); |
5a1a3e5e JH |
572 | |
573 | /* Check the consistency of profile information. We can't do that | |
574 | in verify_flow_info, as the counts may get invalid for incompletely | |
95bd1dd7 | 575 | solved graphs, later eliminating of conditionals or roundoff errors. |
5a1a3e5e JH |
576 | It is still practical to have them reported for debugging of simple |
577 | testcases. */ | |
578 | sum = 0; | |
579 | for (e = bb->succ; e; e = e->succ_next) | |
580 | sum += e->probability; | |
581 | if (bb->succ && abs (sum - REG_BR_PROB_BASE) > 100) | |
582 | fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n", | |
583 | sum * 100.0 / REG_BR_PROB_BASE); | |
584 | sum = 0; | |
585 | for (e = bb->pred; e; e = e->pred_next) | |
586 | sum += EDGE_FREQUENCY (e); | |
587 | if (abs (sum - bb->frequency) > 100) | |
588 | fprintf (file, | |
589 | "Invalid sum of incomming frequencies %i, should be %i\n", | |
590 | sum, bb->frequency); | |
591 | lsum = 0; | |
592 | for (e = bb->pred; e; e = e->pred_next) | |
593 | lsum += e->count; | |
594 | if (lsum - bb->count > 100 || lsum - bb->count < -100) | |
595 | fprintf (file, "Invalid sum of incomming counts %i, should be %i\n", | |
596 | (int)lsum, (int)bb->count); | |
597 | lsum = 0; | |
598 | for (e = bb->succ; e; e = e->succ_next) | |
599 | lsum += e->count; | |
600 | if (bb->succ && (lsum - bb->count > 100 || lsum - bb->count < -100)) | |
601 | fprintf (file, "Invalid sum of incomming counts %i, should be %i\n", | |
602 | (int)lsum, (int)bb->count); | |
402209ff JH |
603 | } |
604 | ||
ca6c03ca | 605 | putc ('\n', file); |
402209ff JH |
606 | } |
607 | ||
ca6c03ca | 608 | void |
d329e058 | 609 | debug_flow_info (void) |
ca6c03ca JH |
610 | { |
611 | dump_flow_info (stderr); | |
612 | } | |
402209ff JH |
613 | |
614 | void | |
d329e058 | 615 | dump_edge_info (FILE *file, edge e, int do_succ) |
402209ff | 616 | { |
ca6c03ca JH |
617 | basic_block side = (do_succ ? e->dest : e->src); |
618 | ||
619 | if (side == ENTRY_BLOCK_PTR) | |
620 | fputs (" ENTRY", file); | |
621 | else if (side == EXIT_BLOCK_PTR) | |
622 | fputs (" EXIT", file); | |
623 | else | |
0b17ab2f | 624 | fprintf (file, " %d", side->index); |
ca6c03ca JH |
625 | |
626 | if (e->probability) | |
627 | fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE); | |
402209ff | 628 | |
ca6c03ca | 629 | if (e->count) |
402209ff | 630 | { |
ca6c03ca | 631 | fprintf (file, " count:"); |
4891442b | 632 | fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count); |
402209ff JH |
633 | } |
634 | ||
ca6c03ca | 635 | if (e->flags) |
402209ff | 636 | { |
1722c2c8 RH |
637 | static const char * const bitnames[] = { |
638 | "fallthru", "ab", "abcall", "eh", "fake", "dfs_back", | |
639 | "can_fallthru", "irreducible", "sibcall" | |
640 | }; | |
ca6c03ca JH |
641 | int comma = 0; |
642 | int i, flags = e->flags; | |
402209ff | 643 | |
4891442b | 644 | fputs (" (", file); |
402209ff JH |
645 | for (i = 0; flags; i++) |
646 | if (flags & (1 << i)) | |
647 | { | |
648 | flags &= ~(1 << i); | |
649 | ||
650 | if (comma) | |
651 | fputc (',', file); | |
652 | if (i < (int) ARRAY_SIZE (bitnames)) | |
653 | fputs (bitnames[i], file); | |
654 | else | |
655 | fprintf (file, "%d", i); | |
656 | comma = 1; | |
657 | } | |
4891442b | 658 | |
402209ff JH |
659 | fputc (')', file); |
660 | } | |
661 | } | |
662 | \f | |
ff7cc307 | 663 | /* Simple routines to easily allocate AUX fields of basic blocks. */ |
4891442b | 664 | |
ca6c03ca JH |
665 | static struct obstack block_aux_obstack; |
666 | static void *first_block_aux_obj = 0; | |
667 | static struct obstack edge_aux_obstack; | |
668 | static void *first_edge_aux_obj = 0; | |
402209ff | 669 | |
09da1532 | 670 | /* Allocate a memory block of SIZE as BB->aux. The obstack must |
ca6c03ca | 671 | be first initialized by alloc_aux_for_blocks. */ |
402209ff | 672 | |
ca6c03ca | 673 | inline void |
d329e058 | 674 | alloc_aux_for_block (basic_block bb, int size) |
402209ff | 675 | { |
ca6c03ca JH |
676 | /* Verify that aux field is clear. */ |
677 | if (bb->aux || !first_block_aux_obj) | |
678 | abort (); | |
679 | bb->aux = obstack_alloc (&block_aux_obstack, size); | |
680 | memset (bb->aux, 0, size); | |
402209ff JH |
681 | } |
682 | ||
ca6c03ca JH |
683 | /* Initialize the block_aux_obstack and if SIZE is nonzero, call |
684 | alloc_aux_for_block for each basic block. */ | |
402209ff JH |
685 | |
686 | void | |
d329e058 | 687 | alloc_aux_for_blocks (int size) |
402209ff | 688 | { |
ca6c03ca | 689 | static int initialized; |
402209ff | 690 | |
ca6c03ca | 691 | if (!initialized) |
402209ff | 692 | { |
ca6c03ca JH |
693 | gcc_obstack_init (&block_aux_obstack); |
694 | initialized = 1; | |
402209ff | 695 | } |
4891442b | 696 | |
ca6c03ca JH |
697 | /* Check whether AUX data are still allocated. */ |
698 | else if (first_block_aux_obj) | |
699 | abort (); | |
700 | first_block_aux_obj = (char *) obstack_alloc (&block_aux_obstack, 0); | |
701 | if (size) | |
402209ff | 702 | { |
e0082a72 | 703 | basic_block bb; |
4891442b | 704 | |
e0082a72 ZD |
705 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) |
706 | alloc_aux_for_block (bb, size); | |
402209ff JH |
707 | } |
708 | } | |
ca6c03ca | 709 | |
108c1afc | 710 | /* Clear AUX pointers of all blocks. */ |
402209ff JH |
711 | |
712 | void | |
d329e058 | 713 | clear_aux_for_blocks (void) |
402209ff | 714 | { |
e0082a72 | 715 | basic_block bb; |
4891442b | 716 | |
e0082a72 ZD |
717 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) |
718 | bb->aux = NULL; | |
108c1afc RH |
719 | } |
720 | ||
721 | /* Free data allocated in block_aux_obstack and clear AUX pointers | |
722 | of all blocks. */ | |
723 | ||
724 | void | |
d329e058 | 725 | free_aux_for_blocks (void) |
108c1afc RH |
726 | { |
727 | if (!first_block_aux_obj) | |
728 | abort (); | |
729 | obstack_free (&block_aux_obstack, first_block_aux_obj); | |
ca6c03ca | 730 | first_block_aux_obj = NULL; |
108c1afc RH |
731 | |
732 | clear_aux_for_blocks (); | |
ca6c03ca | 733 | } |
402209ff | 734 | |
09da1532 | 735 | /* Allocate a memory edge of SIZE as BB->aux. The obstack must |
ca6c03ca | 736 | be first initialized by alloc_aux_for_edges. */ |
402209ff | 737 | |
ca6c03ca | 738 | inline void |
d329e058 | 739 | alloc_aux_for_edge (edge e, int size) |
ca6c03ca JH |
740 | { |
741 | /* Verify that aux field is clear. */ | |
742 | if (e->aux || !first_edge_aux_obj) | |
743 | abort (); | |
744 | e->aux = obstack_alloc (&edge_aux_obstack, size); | |
745 | memset (e->aux, 0, size); | |
746 | } | |
402209ff | 747 | |
ca6c03ca JH |
748 | /* Initialize the edge_aux_obstack and if SIZE is nonzero, call |
749 | alloc_aux_for_edge for each basic edge. */ | |
402209ff | 750 | |
ca6c03ca | 751 | void |
d329e058 | 752 | alloc_aux_for_edges (int size) |
ca6c03ca JH |
753 | { |
754 | static int initialized; | |
402209ff | 755 | |
ca6c03ca JH |
756 | if (!initialized) |
757 | { | |
758 | gcc_obstack_init (&edge_aux_obstack); | |
759 | initialized = 1; | |
402209ff | 760 | } |
4891442b | 761 | |
ca6c03ca JH |
762 | /* Check whether AUX data are still allocated. */ |
763 | else if (first_edge_aux_obj) | |
764 | abort (); | |
4891442b | 765 | |
ca6c03ca JH |
766 | first_edge_aux_obj = (char *) obstack_alloc (&edge_aux_obstack, 0); |
767 | if (size) | |
402209ff | 768 | { |
e0082a72 ZD |
769 | basic_block bb; |
770 | ||
771 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) | |
402209ff | 772 | { |
ca6c03ca JH |
773 | edge e; |
774 | ||
ca6c03ca JH |
775 | for (e = bb->succ; e; e = e->succ_next) |
776 | alloc_aux_for_edge (e, size); | |
402209ff | 777 | } |
402209ff | 778 | } |
402209ff | 779 | } |
402209ff | 780 | |
108c1afc | 781 | /* Clear AUX pointers of all edges. */ |
ca6c03ca JH |
782 | |
783 | void | |
d329e058 | 784 | clear_aux_for_edges (void) |
402209ff | 785 | { |
e0082a72 ZD |
786 | basic_block bb; |
787 | edge e; | |
402209ff | 788 | |
e0082a72 | 789 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) |
402209ff | 790 | { |
ca6c03ca JH |
791 | for (e = bb->succ; e; e = e->succ_next) |
792 | e->aux = NULL; | |
402209ff | 793 | } |
108c1afc RH |
794 | } |
795 | ||
796 | /* Free data allocated in edge_aux_obstack and clear AUX pointers | |
797 | of all edges. */ | |
798 | ||
799 | void | |
d329e058 | 800 | free_aux_for_edges (void) |
108c1afc RH |
801 | { |
802 | if (!first_edge_aux_obj) | |
803 | abort (); | |
804 | obstack_free (&edge_aux_obstack, first_edge_aux_obj); | |
ca6c03ca | 805 | first_edge_aux_obj = NULL; |
108c1afc RH |
806 | |
807 | clear_aux_for_edges (); | |
402209ff | 808 | } |
9ee634e3 | 809 | |
d329e058 AJ |
810 | /* Verify the CFG consistency. |
811 | ||
10e9fecc JH |
812 | Currently it does following checks edge and basic block list correctness |
813 | and calls into IL dependent checking then. */ | |
9ee634e3 | 814 | void |
d329e058 | 815 | verify_flow_info (void) |
9ee634e3 | 816 | { |
10e9fecc JH |
817 | size_t *edge_checksum; |
818 | int num_bb_notes, err = 0; | |
819 | basic_block bb, last_bb_seen; | |
820 | basic_block *last_visited; | |
821 | ||
822 | last_visited = (basic_block *) xcalloc (last_basic_block + 2, | |
823 | sizeof (basic_block)); | |
824 | edge_checksum = (size_t *) xcalloc (last_basic_block + 2, sizeof (size_t)); | |
825 | ||
826 | /* Check bb chain & numbers. */ | |
827 | last_bb_seen = ENTRY_BLOCK_PTR; | |
828 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) | |
829 | { | |
830 | if (bb != EXIT_BLOCK_PTR | |
831 | && bb != BASIC_BLOCK (bb->index)) | |
832 | { | |
833 | error ("bb %d on wrong place", bb->index); | |
834 | err = 1; | |
835 | } | |
836 | ||
837 | if (bb->prev_bb != last_bb_seen) | |
838 | { | |
839 | error ("prev_bb of %d should be %d, not %d", | |
840 | bb->index, last_bb_seen->index, bb->prev_bb->index); | |
841 | err = 1; | |
842 | } | |
843 | ||
844 | last_bb_seen = bb; | |
845 | } | |
846 | ||
847 | /* Now check the basic blocks (boundaries etc.) */ | |
848 | FOR_EACH_BB_REVERSE (bb) | |
849 | { | |
850 | int n_fallthru = 0; | |
851 | edge e; | |
852 | ||
853 | if (bb->count < 0) | |
854 | { | |
855 | error ("verify_flow_info: Wrong count of block %i %i", | |
856 | bb->index, (int)bb->count); | |
857 | err = 1; | |
858 | } | |
859 | if (bb->frequency < 0) | |
860 | { | |
861 | error ("verify_flow_info: Wrong frequency of block %i %i", | |
862 | bb->index, bb->frequency); | |
863 | err = 1; | |
864 | } | |
865 | for (e = bb->succ; e; e = e->succ_next) | |
866 | { | |
867 | if (last_visited [e->dest->index + 2] == bb) | |
868 | { | |
869 | error ("verify_flow_info: Duplicate edge %i->%i", | |
870 | e->src->index, e->dest->index); | |
871 | err = 1; | |
872 | } | |
873 | if (e->probability < 0 || e->probability > REG_BR_PROB_BASE) | |
874 | { | |
875 | error ("verify_flow_info: Wrong probability of edge %i->%i %i", | |
876 | e->src->index, e->dest->index, e->probability); | |
877 | err = 1; | |
878 | } | |
879 | if (e->count < 0) | |
880 | { | |
881 | error ("verify_flow_info: Wrong count of edge %i->%i %i", | |
882 | e->src->index, e->dest->index, (int)e->count); | |
883 | err = 1; | |
884 | } | |
885 | ||
886 | last_visited [e->dest->index + 2] = bb; | |
887 | ||
888 | if (e->flags & EDGE_FALLTHRU) | |
889 | n_fallthru++; | |
890 | ||
891 | if (e->src != bb) | |
892 | { | |
893 | error ("verify_flow_info: Basic block %d succ edge is corrupted", | |
894 | bb->index); | |
895 | fprintf (stderr, "Predecessor: "); | |
896 | dump_edge_info (stderr, e, 0); | |
897 | fprintf (stderr, "\nSuccessor: "); | |
898 | dump_edge_info (stderr, e, 1); | |
899 | fprintf (stderr, "\n"); | |
900 | err = 1; | |
901 | } | |
902 | ||
903 | edge_checksum[e->dest->index + 2] += (size_t) e; | |
904 | } | |
905 | if (n_fallthru > 1) | |
906 | { | |
907 | error ("Wrong amount of branch edges after unconditional jump %i", bb->index); | |
908 | err = 1; | |
909 | } | |
910 | ||
911 | for (e = bb->pred; e; e = e->pred_next) | |
912 | { | |
913 | if (e->dest != bb) | |
914 | { | |
915 | error ("basic block %d pred edge is corrupted", bb->index); | |
916 | fputs ("Predecessor: ", stderr); | |
917 | dump_edge_info (stderr, e, 0); | |
918 | fputs ("\nSuccessor: ", stderr); | |
919 | dump_edge_info (stderr, e, 1); | |
920 | fputc ('\n', stderr); | |
921 | err = 1; | |
922 | } | |
923 | edge_checksum[e->dest->index + 2] -= (size_t) e; | |
924 | } | |
925 | } | |
926 | ||
927 | /* Complete edge checksumming for ENTRY and EXIT. */ | |
928 | { | |
929 | edge e; | |
930 | ||
931 | for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next) | |
932 | edge_checksum[e->dest->index + 2] += (size_t) e; | |
933 | ||
934 | for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next) | |
935 | edge_checksum[e->dest->index + 2] -= (size_t) e; | |
936 | } | |
937 | ||
938 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
939 | if (edge_checksum[bb->index + 2]) | |
940 | { | |
941 | error ("basic block %i edge lists are corrupted", bb->index); | |
942 | err = 1; | |
943 | } | |
944 | ||
945 | num_bb_notes = 0; | |
946 | last_bb_seen = ENTRY_BLOCK_PTR; | |
947 | ||
948 | /* Clean up. */ | |
949 | free (last_visited); | |
950 | free (edge_checksum); | |
951 | err |= cfg_hooks->cfgh_verify_flow_info (); | |
952 | if (err) | |
953 | internal_error ("verify_flow_info failed"); | |
954 | } | |
955 | ||
956 | /* Print out one basic block with live information at start and end. */ | |
957 | ||
958 | void | |
d329e058 | 959 | dump_bb (basic_block bb, FILE *outf) |
10e9fecc JH |
960 | { |
961 | edge e; | |
962 | ||
963 | fprintf (outf, ";; Basic block %d, loop depth %d, count ", | |
964 | bb->index, bb->loop_depth); | |
965 | fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count); | |
966 | putc ('\n', outf); | |
967 | ||
968 | cfg_hooks->dump_bb (bb, outf); | |
969 | ||
970 | fputs (";; Successors: ", outf); | |
971 | for (e = bb->succ; e; e = e->succ_next) | |
972 | dump_edge_info (outf, e, 1); | |
973 | putc ('\n', outf); | |
974 | } | |
975 | ||
976 | void | |
d329e058 | 977 | debug_bb (basic_block bb) |
10e9fecc JH |
978 | { |
979 | dump_bb (bb, stderr); | |
980 | } | |
981 | ||
982 | basic_block | |
d329e058 | 983 | debug_bb_n (int n) |
10e9fecc JH |
984 | { |
985 | basic_block bb = BASIC_BLOCK (n); | |
986 | dump_bb (bb, stderr); | |
987 | return bb; | |
9ee634e3 | 988 | } |