]>
Commit | Line | Data |
---|---|---|
9ee634e3 | 1 | /* Hooks for cfg representation specific functions. |
283334f0 | 2 | Copyright (C) 2003, 2004 Free Software Foundation, Inc. |
9ee634e3 JH |
3 | Contributed by Sebastian Pop <s.pop@laposte.net> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 2, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License 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 | |
19 | the Free Software Foundation, 59 Temple Place - Suite 330, | |
20 | Boston, MA 02111-1307, USA. */ | |
21 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "tm.h" | |
26 | #include "tree.h" | |
27 | #include "rtl.h" | |
28 | #include "basic-block.h" | |
f470c378 ZD |
29 | #include "timevar.h" |
30 | #include "toplev.h" | |
9ee634e3 JH |
31 | |
32 | /* A pointer to one of the hooks containers. */ | |
f470c378 | 33 | static struct cfg_hooks *cfg_hooks; |
9ee634e3 JH |
34 | |
35 | /* Initialization of functions specific to the rtl IR. */ | |
d329e058 AJ |
36 | void |
37 | rtl_register_cfg_hooks (void) | |
9ee634e3 JH |
38 | { |
39 | cfg_hooks = &rtl_cfg_hooks; | |
40 | } | |
41 | ||
42 | /* Initialization of functions specific to the rtl IR. */ | |
d329e058 AJ |
43 | void |
44 | cfg_layout_rtl_register_cfg_hooks (void) | |
9ee634e3 JH |
45 | { |
46 | cfg_hooks = &cfg_layout_rtl_cfg_hooks; | |
47 | } | |
f470c378 ZD |
48 | |
49 | /* Verify the CFG consistency. | |
50 | ||
51 | Currently it does following: checks edge and basic block list correctness | |
52 | and calls into IL dependent checking then. */ | |
53 | ||
54 | void | |
55 | verify_flow_info (void) | |
56 | { | |
57 | size_t *edge_checksum; | |
58 | int num_bb_notes, err = 0; | |
59 | basic_block bb, last_bb_seen; | |
60 | basic_block *last_visited; | |
61 | ||
62 | timevar_push (TV_CFG_VERIFY); | |
63 | last_visited = xcalloc (last_basic_block + 2, sizeof (basic_block)); | |
64 | edge_checksum = xcalloc (last_basic_block + 2, sizeof (size_t)); | |
65 | ||
66 | /* Check bb chain & numbers. */ | |
67 | last_bb_seen = ENTRY_BLOCK_PTR; | |
68 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) | |
69 | { | |
70 | if (bb != EXIT_BLOCK_PTR | |
71 | && bb != BASIC_BLOCK (bb->index)) | |
72 | { | |
73 | error ("bb %d on wrong place", bb->index); | |
74 | err = 1; | |
75 | } | |
76 | ||
77 | if (bb->prev_bb != last_bb_seen) | |
78 | { | |
79 | error ("prev_bb of %d should be %d, not %d", | |
80 | bb->index, last_bb_seen->index, bb->prev_bb->index); | |
81 | err = 1; | |
82 | } | |
83 | ||
84 | last_bb_seen = bb; | |
85 | } | |
86 | ||
87 | /* Now check the basic blocks (boundaries etc.) */ | |
88 | FOR_EACH_BB_REVERSE (bb) | |
89 | { | |
90 | int n_fallthru = 0; | |
91 | edge e; | |
92 | ||
93 | if (bb->count < 0) | |
94 | { | |
95 | error ("verify_flow_info: Wrong count of block %i %i", | |
96 | bb->index, (int)bb->count); | |
97 | err = 1; | |
98 | } | |
99 | if (bb->frequency < 0) | |
100 | { | |
101 | error ("verify_flow_info: Wrong frequency of block %i %i", | |
102 | bb->index, bb->frequency); | |
103 | err = 1; | |
104 | } | |
105 | for (e = bb->succ; e; e = e->succ_next) | |
106 | { | |
107 | if (last_visited [e->dest->index + 2] == bb) | |
108 | { | |
109 | error ("verify_flow_info: Duplicate edge %i->%i", | |
110 | e->src->index, e->dest->index); | |
111 | err = 1; | |
112 | } | |
113 | if (e->probability < 0 || e->probability > REG_BR_PROB_BASE) | |
114 | { | |
115 | error ("verify_flow_info: Wrong probability of edge %i->%i %i", | |
116 | e->src->index, e->dest->index, e->probability); | |
117 | err = 1; | |
118 | } | |
119 | if (e->count < 0) | |
120 | { | |
121 | error ("verify_flow_info: Wrong count of edge %i->%i %i", | |
122 | e->src->index, e->dest->index, (int)e->count); | |
123 | err = 1; | |
124 | } | |
125 | ||
126 | last_visited [e->dest->index + 2] = bb; | |
127 | ||
128 | if (e->flags & EDGE_FALLTHRU) | |
129 | n_fallthru++; | |
130 | ||
131 | if (e->src != bb) | |
132 | { | |
133 | error ("verify_flow_info: Basic block %d succ edge is corrupted", | |
134 | bb->index); | |
135 | fprintf (stderr, "Predecessor: "); | |
136 | dump_edge_info (stderr, e, 0); | |
137 | fprintf (stderr, "\nSuccessor: "); | |
138 | dump_edge_info (stderr, e, 1); | |
139 | fprintf (stderr, "\n"); | |
140 | err = 1; | |
141 | } | |
142 | ||
143 | edge_checksum[e->dest->index + 2] += (size_t) e; | |
144 | } | |
145 | if (n_fallthru > 1) | |
146 | { | |
147 | error ("Wrong amount of branch edges after unconditional jump %i", bb->index); | |
148 | err = 1; | |
149 | } | |
150 | ||
151 | for (e = bb->pred; e; e = e->pred_next) | |
152 | { | |
153 | if (e->dest != bb) | |
154 | { | |
155 | error ("basic block %d pred edge is corrupted", bb->index); | |
156 | fputs ("Predecessor: ", stderr); | |
157 | dump_edge_info (stderr, e, 0); | |
158 | fputs ("\nSuccessor: ", stderr); | |
159 | dump_edge_info (stderr, e, 1); | |
160 | fputc ('\n', stderr); | |
161 | err = 1; | |
162 | } | |
163 | edge_checksum[e->dest->index + 2] -= (size_t) e; | |
164 | } | |
165 | } | |
166 | ||
167 | /* Complete edge checksumming for ENTRY and EXIT. */ | |
168 | { | |
169 | edge e; | |
170 | ||
171 | for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next) | |
172 | edge_checksum[e->dest->index + 2] += (size_t) e; | |
173 | ||
174 | for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next) | |
175 | edge_checksum[e->dest->index + 2] -= (size_t) e; | |
176 | } | |
177 | ||
178 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
179 | if (edge_checksum[bb->index + 2]) | |
180 | { | |
181 | error ("basic block %i edge lists are corrupted", bb->index); | |
182 | err = 1; | |
183 | } | |
184 | ||
185 | num_bb_notes = 0; | |
186 | last_bb_seen = ENTRY_BLOCK_PTR; | |
187 | ||
188 | /* Clean up. */ | |
189 | free (last_visited); | |
190 | free (edge_checksum); | |
191 | ||
192 | if (cfg_hooks->verify_flow_info) | |
193 | err |= cfg_hooks->verify_flow_info (); | |
194 | if (err) | |
195 | internal_error ("verify_flow_info failed"); | |
196 | timevar_pop (TV_CFG_VERIFY); | |
197 | } | |
198 | ||
199 | /* Print out one basic block. This function takes care of the purely | |
200 | graph related information. The cfg hook for the active representation | |
201 | should dump representation-specific information. */ | |
202 | ||
203 | void | |
204 | dump_bb (basic_block bb, FILE *outf, int indent) | |
205 | { | |
206 | edge e; | |
207 | char *s_indent; | |
208 | ||
209 | s_indent = (char *) alloca ((size_t) indent + 1); | |
210 | memset ((void *) s_indent, ' ', (size_t) indent); | |
211 | s_indent[indent] = '\0'; | |
212 | ||
213 | fprintf (outf, ";;%s basic block %d, loop depth %d, count ", | |
214 | s_indent, bb->index, bb->loop_depth); | |
215 | fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count); | |
216 | putc ('\n', outf); | |
217 | ||
218 | fprintf (outf, ";;%s prev block ", s_indent); | |
219 | if (bb->prev_bb) | |
220 | fprintf (outf, "%d, ", bb->prev_bb->index); | |
221 | else | |
222 | fprintf (outf, "(nil), "); | |
223 | fprintf (outf, "next block "); | |
224 | if (bb->next_bb) | |
225 | fprintf (outf, "%d", bb->next_bb->index); | |
226 | else | |
227 | fprintf (outf, "(nil)"); | |
228 | putc ('\n', outf); | |
229 | ||
230 | fprintf (outf, ";;%s pred: ", s_indent); | |
231 | for (e = bb->pred; e; e = e->pred_next) | |
232 | dump_edge_info (outf, e, 0); | |
233 | putc ('\n', outf); | |
234 | ||
235 | fprintf (outf, ";;%s succ: ", s_indent); | |
236 | for (e = bb->succ; e; e = e->succ_next) | |
237 | dump_edge_info (outf, e, 1); | |
238 | putc ('\n', outf); | |
239 | ||
240 | if (cfg_hooks->dump_bb) | |
241 | cfg_hooks->dump_bb (bb, outf, indent); | |
242 | } | |
243 | ||
244 | /* Redirect edge E to the given basic block DEST and update underlying program | |
245 | representation. Returns edge representing redirected branch (that may not | |
246 | be equivalent to E in the case of duplicate edges being removed) or NULL | |
247 | if edge is not easily redirectable for whatever reason. */ | |
248 | ||
249 | bool | |
250 | redirect_edge_and_branch (edge e, basic_block dest) | |
251 | { | |
252 | bool ret; | |
253 | ||
254 | if (!cfg_hooks->redirect_edge_and_branch) | |
255 | internal_error ("%s does not support redirect_edge_and_branch.", | |
256 | cfg_hooks->name); | |
257 | ||
258 | ret = cfg_hooks->redirect_edge_and_branch (e, dest); | |
259 | ||
260 | return ret; | |
261 | } | |
262 | ||
263 | /* Redirect the edge E to basic block DEST even if it requires creating | |
264 | of a new basic block; then it returns the newly created basic block. | |
265 | Aborts when redirection is impossible. */ | |
266 | ||
267 | basic_block | |
268 | redirect_edge_and_branch_force (edge e, basic_block dest) | |
269 | { | |
270 | basic_block ret; | |
271 | ||
272 | if (!cfg_hooks->redirect_edge_and_branch_force) | |
273 | internal_error ("%s does not support redirect_edge_and_branch_force.", | |
274 | cfg_hooks->name); | |
275 | ||
276 | ret = cfg_hooks->redirect_edge_and_branch_force (e, dest); | |
277 | ||
278 | return ret; | |
279 | } | |
280 | ||
281 | /* Splits basic block BB after the specified instruction I (but at least after | |
282 | the labels). If I is NULL, splits just after labels. The newly created edge | |
283 | is returned. The new basic block is created just after the old one. */ | |
284 | ||
285 | edge | |
286 | split_block (basic_block bb, void *i) | |
287 | { | |
288 | basic_block new_bb; | |
3ae4a5b1 | 289 | edge e; |
f470c378 ZD |
290 | |
291 | if (!cfg_hooks->split_block) | |
292 | internal_error ("%s does not support split_block.", cfg_hooks->name); | |
293 | ||
294 | new_bb = cfg_hooks->split_block (bb, i); | |
295 | if (!new_bb) | |
296 | return NULL; | |
297 | ||
298 | new_bb->count = bb->count; | |
299 | new_bb->frequency = bb->frequency; | |
300 | new_bb->loop_depth = bb->loop_depth; | |
301 | ||
302 | if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK) | |
303 | { | |
304 | redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb); | |
305 | set_immediate_dominator (CDI_DOMINATORS, new_bb, bb); | |
306 | } | |
307 | ||
3ae4a5b1 ZD |
308 | e = make_edge (bb, new_bb, EDGE_FALLTHRU); |
309 | e->probability = REG_BR_PROB_BASE; | |
310 | e->count = bb->count; | |
311 | ||
312 | return e; | |
f470c378 ZD |
313 | } |
314 | ||
315 | /* Splits block BB just after labels. The newly created edge is returned. */ | |
316 | ||
317 | edge | |
318 | split_block_after_labels (basic_block bb) | |
319 | { | |
320 | return split_block (bb, NULL); | |
321 | } | |
322 | ||
323 | /* Moves block BB immediatelly after block AFTER. Returns false if the | |
324 | movement was impossible. */ | |
325 | ||
326 | bool | |
327 | move_block_after (basic_block bb, basic_block after) | |
328 | { | |
329 | bool ret; | |
330 | ||
331 | if (!cfg_hooks->move_block_after) | |
332 | internal_error ("%s does not support move_block_after.", cfg_hooks->name); | |
333 | ||
334 | ret = cfg_hooks->move_block_after (bb, after); | |
335 | ||
336 | return ret; | |
337 | } | |
338 | ||
339 | /* Deletes the basic block BB. */ | |
340 | ||
341 | void | |
342 | delete_basic_block (basic_block bb) | |
343 | { | |
344 | if (!cfg_hooks->delete_basic_block) | |
345 | internal_error ("%s does not support delete_basic_block.", cfg_hooks->name); | |
346 | ||
347 | cfg_hooks->delete_basic_block (bb); | |
348 | ||
349 | /* Remove the edges into and out of this block. Note that there may | |
350 | indeed be edges in, if we are removing an unreachable loop. */ | |
351 | while (bb->pred != NULL) | |
352 | remove_edge (bb->pred); | |
353 | while (bb->succ != NULL) | |
354 | remove_edge (bb->succ); | |
355 | ||
356 | bb->pred = NULL; | |
357 | bb->succ = NULL; | |
358 | ||
359 | if (dom_computed[CDI_DOMINATORS]) | |
360 | delete_from_dominance_info (CDI_DOMINATORS, bb); | |
361 | if (dom_computed[CDI_POST_DOMINATORS]) | |
362 | delete_from_dominance_info (CDI_POST_DOMINATORS, bb); | |
363 | ||
364 | /* Remove the basic block from the array. */ | |
365 | expunge_block (bb); | |
366 | } | |
367 | ||
368 | /* Splits edge E and returns the newly created basic block. */ | |
369 | ||
370 | basic_block | |
371 | split_edge (edge e) | |
372 | { | |
373 | basic_block ret; | |
374 | gcov_type count = e->count; | |
375 | int freq = EDGE_FREQUENCY (e); | |
376 | ||
377 | if (!cfg_hooks->split_edge) | |
378 | internal_error ("%s does not support split_edge.", cfg_hooks->name); | |
379 | ||
380 | ret = cfg_hooks->split_edge (e); | |
381 | ret->count = count; | |
382 | ret->frequency = freq; | |
383 | ret->succ->probability = REG_BR_PROB_BASE; | |
384 | ret->succ->count = count; | |
385 | ||
386 | if (dom_computed[CDI_DOMINATORS]) | |
387 | set_immediate_dominator (CDI_DOMINATORS, ret, ret->pred->src); | |
388 | ||
389 | if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY) | |
390 | set_immediate_dominator (CDI_DOMINATORS, ret->succ->dest, | |
391 | recount_dominator (CDI_DOMINATORS, | |
392 | ret->succ->dest)); | |
393 | ||
394 | return ret; | |
395 | } | |
396 | ||
397 | /* Creates a new basic block just after the basic block AFTER. | |
398 | HEAD and END are the first and the last statement belonging | |
399 | to the block. If both are NULL, an empty block is created. */ | |
400 | ||
401 | basic_block | |
402 | create_basic_block (void *head, void *end, basic_block after) | |
403 | { | |
404 | basic_block ret; | |
405 | ||
406 | if (!cfg_hooks->create_basic_block) | |
407 | internal_error ("%s does not support create_basic_block.", cfg_hooks->name); | |
408 | ||
409 | ret = cfg_hooks->create_basic_block (head, end, after); | |
410 | ||
411 | if (dom_computed[CDI_DOMINATORS]) | |
412 | add_to_dominance_info (CDI_DOMINATORS, ret); | |
413 | if (dom_computed[CDI_POST_DOMINATORS]) | |
414 | add_to_dominance_info (CDI_POST_DOMINATORS, ret); | |
415 | ||
416 | return ret; | |
417 | } | |
418 | ||
419 | /* Creates an empty basic block just after basic block AFTER. */ | |
420 | ||
421 | basic_block | |
422 | create_empty_bb (basic_block after) | |
423 | { | |
424 | return create_basic_block (NULL, NULL, after); | |
425 | } | |
426 | ||
427 | /* Checks whether we may merge blocks BB1 and BB2. */ | |
428 | ||
429 | bool | |
430 | can_merge_blocks_p (basic_block bb1, basic_block bb2) | |
431 | { | |
432 | bool ret; | |
433 | ||
434 | if (!cfg_hooks->can_merge_blocks_p) | |
435 | internal_error ("%s does not support can_merge_blocks_p.", cfg_hooks->name); | |
436 | ||
437 | ret = cfg_hooks->can_merge_blocks_p (bb1, bb2); | |
438 | ||
439 | return ret; | |
440 | } | |
441 | ||
442 | /* Merges basic block B into basic block A. */ | |
443 | ||
444 | void | |
445 | merge_blocks (basic_block a, basic_block b) | |
446 | { | |
447 | edge e; | |
448 | ||
449 | if (!cfg_hooks->merge_blocks) | |
450 | internal_error ("%s does not support merge_blocks.", cfg_hooks->name); | |
451 | ||
452 | cfg_hooks->merge_blocks (a, b); | |
453 | ||
454 | /* Normally there should only be one successor of A and that is B, but | |
455 | partway though the merge of blocks for conditional_execution we'll | |
456 | be merging a TEST block with THEN and ELSE successors. Free the | |
457 | whole lot of them and hope the caller knows what they're doing. */ | |
458 | while (a->succ) | |
459 | remove_edge (a->succ); | |
460 | ||
461 | /* Adjust the edges out of B for the new owner. */ | |
462 | for (e = b->succ; e; e = e->succ_next) | |
463 | e->src = a; | |
464 | a->succ = b->succ; | |
465 | a->flags |= b->flags; | |
466 | ||
467 | /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */ | |
468 | b->pred = b->succ = NULL; | |
469 | a->global_live_at_end = b->global_live_at_end; | |
470 | ||
471 | if (dom_computed[CDI_DOMINATORS]) | |
472 | redirect_immediate_dominators (CDI_DOMINATORS, b, a); | |
473 | ||
474 | if (dom_computed[CDI_DOMINATORS]) | |
475 | delete_from_dominance_info (CDI_DOMINATORS, b); | |
476 | if (dom_computed[CDI_POST_DOMINATORS]) | |
477 | delete_from_dominance_info (CDI_POST_DOMINATORS, b); | |
478 | ||
479 | expunge_block (b); | |
480 | } | |
481 | ||
482 | /* Split BB into entry part and the rest (the rest is the newly created block). | |
483 | Redirect those edges for that REDIRECT_EDGE_P returns true to the entry | |
484 | part. Returns the edge connecting the entry part to the rest. */ | |
485 | ||
486 | edge | |
487 | make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge), | |
488 | void (*new_bb_cbk) (basic_block)) | |
489 | { | |
490 | edge e, next_e, fallthru; | |
491 | basic_block dummy, jump; | |
492 | ||
493 | if (!cfg_hooks->make_forwarder_block) | |
494 | internal_error ("%s does not support make_forwarder_block.", | |
495 | cfg_hooks->name); | |
496 | ||
497 | fallthru = split_block_after_labels (bb); | |
498 | dummy = fallthru->src; | |
499 | bb = fallthru->dest; | |
500 | ||
501 | /* Redirect back edges we want to keep. */ | |
502 | for (e = dummy->pred; e; e = next_e) | |
503 | { | |
504 | next_e = e->pred_next; | |
505 | if (redirect_edge_p (e)) | |
506 | continue; | |
507 | ||
508 | dummy->frequency -= EDGE_FREQUENCY (e); | |
509 | dummy->count -= e->count; | |
510 | if (dummy->frequency < 0) | |
511 | dummy->frequency = 0; | |
512 | if (dummy->count < 0) | |
513 | dummy->count = 0; | |
514 | ||
515 | jump = redirect_edge_and_branch_force (e, bb); | |
516 | if (jump) | |
517 | new_bb_cbk (jump); | |
518 | } | |
519 | ||
520 | if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK) | |
521 | { | |
522 | basic_block doms_to_fix[2]; | |
523 | ||
524 | doms_to_fix[0] = dummy; | |
525 | doms_to_fix[1] = bb; | |
526 | iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, 2); | |
527 | } | |
528 | ||
529 | cfg_hooks->make_forwarder_block (fallthru); | |
530 | ||
531 | return fallthru; | |
532 | } | |
533 | ||
534 | void | |
535 | tidy_fallthru_edge (edge e) | |
536 | { | |
537 | if (cfg_hooks->tidy_fallthru_edge) | |
538 | cfg_hooks->tidy_fallthru_edge (e); | |
539 | } | |
540 | ||
541 | /* Fix up edges that now fall through, or rather should now fall through | |
542 | but previously required a jump around now deleted blocks. Simplify | |
543 | the search by only examining blocks numerically adjacent, since this | |
544 | is how find_basic_blocks created them. */ | |
545 | ||
546 | void | |
547 | tidy_fallthru_edges (void) | |
548 | { | |
549 | basic_block b, c; | |
550 | ||
551 | if (!cfg_hooks->tidy_fallthru_edge) | |
552 | return; | |
553 | ||
554 | if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) | |
555 | return; | |
556 | ||
557 | FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb) | |
558 | { | |
559 | edge s; | |
560 | ||
561 | c = b->next_bb; | |
562 | ||
563 | /* We care about simple conditional or unconditional jumps with | |
564 | a single successor. | |
565 | ||
566 | If we had a conditional branch to the next instruction when | |
567 | find_basic_blocks was called, then there will only be one | |
568 | out edge for the block which ended with the conditional | |
569 | branch (since we do not create duplicate edges). | |
570 | ||
571 | Furthermore, the edge will be marked as a fallthru because we | |
572 | merge the flags for the duplicate edges. So we do not want to | |
573 | check that the edge is not a FALLTHRU edge. */ | |
574 | ||
575 | if ((s = b->succ) != NULL | |
576 | && ! (s->flags & EDGE_COMPLEX) | |
577 | && s->succ_next == NULL | |
578 | && s->dest == c) | |
579 | tidy_fallthru_edge (s); | |
580 | } | |
581 | } |