1 /* Hooks for cfg representation specific functions.
2 Copyright (C) 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
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)
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.
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. */
24 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "tree-flow.h"
33 /* A pointer to one of the hooks containers. */
34 static struct cfg_hooks
*cfg_hooks
;
36 /* Initialization of functions specific to the rtl IR. */
38 rtl_register_cfg_hooks (void)
40 cfg_hooks
= &rtl_cfg_hooks
;
43 /* Initialization of functions specific to the rtl IR. */
45 cfg_layout_rtl_register_cfg_hooks (void)
47 cfg_hooks
= &cfg_layout_rtl_cfg_hooks
;
50 /* Initialization of functions specific to the tree IR. */
53 tree_register_cfg_hooks (void)
55 cfg_hooks
= &tree_cfg_hooks
;
58 /* Returns current ir type (rtl = 0, trees = 1). */
63 return cfg_hooks
== &tree_cfg_hooks
? 1 : 0;
66 /* Verify the CFG consistency.
68 Currently it does following: checks edge and basic block list correctness
69 and calls into IL dependent checking then. */
72 verify_flow_info (void)
74 size_t *edge_checksum
;
75 int num_bb_notes
, err
= 0;
76 basic_block bb
, last_bb_seen
;
77 basic_block
*last_visited
;
79 timevar_push (TV_CFG_VERIFY
);
80 last_visited
= xcalloc (last_basic_block
+ 2, sizeof (basic_block
));
81 edge_checksum
= xcalloc (last_basic_block
+ 2, sizeof (size_t));
83 /* Check bb chain & numbers. */
84 last_bb_seen
= ENTRY_BLOCK_PTR
;
85 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
87 if (bb
!= EXIT_BLOCK_PTR
88 && bb
!= BASIC_BLOCK (bb
->index
))
90 error ("bb %d on wrong place", bb
->index
);
94 if (bb
->prev_bb
!= last_bb_seen
)
96 error ("prev_bb of %d should be %d, not %d",
97 bb
->index
, last_bb_seen
->index
, bb
->prev_bb
->index
);
104 /* Now check the basic blocks (boundaries etc.) */
105 FOR_EACH_BB_REVERSE (bb
)
113 error ("verify_flow_info: Wrong count of block %i %i",
114 bb
->index
, (int)bb
->count
);
117 if (bb
->frequency
< 0)
119 error ("verify_flow_info: Wrong frequency of block %i %i",
120 bb
->index
, bb
->frequency
);
123 FOR_EACH_EDGE (e
, bb
->succ
, ix
)
125 if (last_visited
[e
->dest
->index
+ 2] == bb
)
127 error ("verify_flow_info: Duplicate edge %i->%i",
128 e
->src
->index
, e
->dest
->index
);
131 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
133 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
134 e
->src
->index
, e
->dest
->index
, e
->probability
);
139 error ("verify_flow_info: Wrong count of edge %i->%i %i",
140 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
144 last_visited
[e
->dest
->index
+ 2] = bb
;
146 if (e
->flags
& EDGE_FALLTHRU
)
151 error ("verify_flow_info: Basic block %d succ edge is corrupted",
153 fprintf (stderr
, "Predecessor: ");
154 dump_edge_info (stderr
, e
, 0);
155 fprintf (stderr
, "\nSuccessor: ");
156 dump_edge_info (stderr
, e
, 1);
157 fprintf (stderr
, "\n");
161 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
165 error ("Wrong amount of branch edges after unconditional jump %i", bb
->index
);
169 FOR_EACH_EDGE (e
, bb
->pred
, ix
)
173 error ("basic block %d pred edge is corrupted", bb
->index
);
174 fputs ("Predecessor: ", stderr
);
175 dump_edge_info (stderr
, e
, 0);
176 fputs ("\nSuccessor: ", stderr
);
177 dump_edge_info (stderr
, e
, 1);
178 fputc ('\n', stderr
);
181 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
185 /* Complete edge checksumming for ENTRY and EXIT. */
190 FOR_EACH_EDGE (e
, ENTRY_BLOCK_PTR
->succ
, ix
)
191 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
193 FOR_EACH_EDGE (e
, EXIT_BLOCK_PTR
->pred
, ix
)
194 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
197 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
198 if (edge_checksum
[bb
->index
+ 2])
200 error ("basic block %i edge lists are corrupted", bb
->index
);
205 last_bb_seen
= ENTRY_BLOCK_PTR
;
209 free (edge_checksum
);
211 if (cfg_hooks
->verify_flow_info
)
212 err
|= cfg_hooks
->verify_flow_info ();
214 internal_error ("verify_flow_info failed");
215 timevar_pop (TV_CFG_VERIFY
);
218 /* Print out one basic block. This function takes care of the purely
219 graph related information. The cfg hook for the active representation
220 should dump representation-specific information. */
223 dump_bb (basic_block bb
, FILE *outf
, int indent
)
229 s_indent
= alloca ((size_t) indent
+ 1);
230 memset (s_indent
, ' ', (size_t) indent
);
231 s_indent
[indent
] = '\0';
233 fprintf (outf
, ";;%s basic block %d, loop depth %d, count ",
234 s_indent
, bb
->index
, bb
->loop_depth
);
235 fprintf (outf
, HOST_WIDEST_INT_PRINT_DEC
, (HOST_WIDEST_INT
) bb
->count
);
238 fprintf (outf
, ";;%s prev block ", s_indent
);
240 fprintf (outf
, "%d, ", bb
->prev_bb
->index
);
242 fprintf (outf
, "(nil), ");
243 fprintf (outf
, "next block ");
245 fprintf (outf
, "%d", bb
->next_bb
->index
);
247 fprintf (outf
, "(nil)");
250 fprintf (outf
, ";;%s pred: ", s_indent
);
251 FOR_EACH_EDGE (e
, bb
->pred
, ix
)
252 dump_edge_info (outf
, e
, 0);
255 fprintf (outf
, ";;%s succ: ", s_indent
);
256 FOR_EACH_EDGE (e
, bb
->succ
, ix
)
257 dump_edge_info (outf
, e
, 1);
260 if (cfg_hooks
->dump_bb
)
261 cfg_hooks
->dump_bb (bb
, outf
, indent
);
264 /* Redirect edge E to the given basic block DEST and update underlying program
265 representation. Returns edge representing redirected branch (that may not
266 be equivalent to E in the case of duplicate edges being removed) or NULL
267 if edge is not easily redirectable for whatever reason. */
270 redirect_edge_and_branch (edge e
, basic_block dest
)
274 if (!cfg_hooks
->redirect_edge_and_branch
)
275 internal_error ("%s does not support redirect_edge_and_branch.",
278 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
283 /* Redirect the edge E to basic block DEST even if it requires creating
284 of a new basic block; then it returns the newly created basic block.
285 Aborts when redirection is impossible. */
288 redirect_edge_and_branch_force (edge e
, basic_block dest
)
292 if (!cfg_hooks
->redirect_edge_and_branch_force
)
293 internal_error ("%s does not support redirect_edge_and_branch_force.",
296 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
301 /* Splits basic block BB after the specified instruction I (but at least after
302 the labels). If I is NULL, splits just after labels. The newly created edge
303 is returned. The new basic block is created just after the old one. */
306 split_block (basic_block bb
, void *i
)
310 if (!cfg_hooks
->split_block
)
311 internal_error ("%s does not support split_block.", cfg_hooks
->name
);
313 new_bb
= cfg_hooks
->split_block (bb
, i
);
317 new_bb
->count
= bb
->count
;
318 new_bb
->frequency
= bb
->frequency
;
319 new_bb
->loop_depth
= bb
->loop_depth
;
321 if (dom_computed
[CDI_DOMINATORS
] >= DOM_CONS_OK
)
323 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
324 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
327 return make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
330 /* Splits block BB just after labels. The newly created edge is returned. */
333 split_block_after_labels (basic_block bb
)
335 return split_block (bb
, NULL
);
338 /* Moves block BB immediately after block AFTER. Returns false if the
339 movement was impossible. */
342 move_block_after (basic_block bb
, basic_block after
)
346 if (!cfg_hooks
->move_block_after
)
347 internal_error ("%s does not support move_block_after.", cfg_hooks
->name
);
349 ret
= cfg_hooks
->move_block_after (bb
, after
);
354 /* Deletes the basic block BB. */
357 delete_basic_block (basic_block bb
)
362 if (!cfg_hooks
->delete_basic_block
)
363 internal_error ("%s does not support delete_basic_block.", cfg_hooks
->name
);
365 cfg_hooks
->delete_basic_block (bb
);
367 /* Remove the edges into and out of this block. Note that there may
368 indeed be edges in, if we are removing an unreachable loop. */
369 FOR_EACH_EDGE (e
, bb
->pred
, ix
)
370 remove_edge (EDGE_I (bb
->pred
, ix
));
371 FOR_EACH_EDGE (e
, bb
->succ
, ix
)
372 remove_edge (EDGE_I (bb
->succ
, ix
));
374 if (EDGE_COUNT (bb
->pred
) > 0)
375 VEC_truncate (edge
, bb
->pred
, 0);
376 if (EDGE_COUNT (bb
->succ
) > 0)
377 VEC_truncate (edge
, bb
->succ
, 0);
379 if (dom_computed
[CDI_DOMINATORS
])
380 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
381 if (dom_computed
[CDI_POST_DOMINATORS
])
382 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
384 /* Remove the basic block from the array. */
388 /* Splits edge E and returns the newly created basic block. */
394 gcov_type count
= e
->count
;
395 int freq
= EDGE_FREQUENCY (e
);
399 if (!cfg_hooks
->split_edge
)
400 internal_error ("%s does not support split_edge.", cfg_hooks
->name
);
402 ret
= cfg_hooks
->split_edge (e
);
404 ret
->frequency
= freq
;
405 EDGE_0 (ret
->succ
)->probability
= REG_BR_PROB_BASE
;
406 EDGE_0 (ret
->succ
)->count
= count
;
408 if (dom_computed
[CDI_DOMINATORS
])
409 set_immediate_dominator (CDI_DOMINATORS
, ret
, EDGE_0 (ret
->pred
)->src
);
411 if (dom_computed
[CDI_DOMINATORS
] >= DOM_NO_FAST_QUERY
)
413 /* There are two cases:
415 If the immediate dominator of e->dest is not e->src, it
418 If immediate dominator of e->dest is e->src, it may become
419 ret, provided that all other predecessors of e->dest are
420 dominated by e->dest. */
422 if (get_immediate_dominator (CDI_DOMINATORS
, EDGE_0 (ret
->succ
)->dest
)
423 == EDGE_0 (ret
->pred
)->src
)
425 FOR_EACH_EDGE (f
, EDGE_0 (ret
->succ
)->dest
->pred
, ix
)
427 if (f
== EDGE_0 (ret
->succ
))
430 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
431 EDGE_0 (ret
->succ
)->dest
))
436 set_immediate_dominator (CDI_DOMINATORS
, EDGE_0 (ret
->succ
)->dest
, ret
);
443 /* Creates a new basic block just after the basic block AFTER.
444 HEAD and END are the first and the last statement belonging
445 to the block. If both are NULL, an empty block is created. */
448 create_basic_block (void *head
, void *end
, basic_block after
)
452 if (!cfg_hooks
->create_basic_block
)
453 internal_error ("%s does not support create_basic_block.", cfg_hooks
->name
);
455 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
457 if (dom_computed
[CDI_DOMINATORS
])
458 add_to_dominance_info (CDI_DOMINATORS
, ret
);
459 if (dom_computed
[CDI_POST_DOMINATORS
])
460 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
465 /* Creates an empty basic block just after basic block AFTER. */
468 create_empty_bb (basic_block after
)
470 return create_basic_block (NULL
, NULL
, after
);
473 /* Checks whether we may merge blocks BB1 and BB2. */
476 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
480 if (!cfg_hooks
->can_merge_blocks_p
)
481 internal_error ("%s does not support can_merge_blocks_p.", cfg_hooks
->name
);
483 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
489 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
491 if (!cfg_hooks
->predict_edge
)
492 internal_error ("%s does not support predict_edge.", cfg_hooks
->name
);
494 cfg_hooks
->predict_edge (e
, predictor
, probability
);
498 predicted_by_p (basic_block bb
, enum br_predictor predictor
)
500 if (!cfg_hooks
->predict_edge
)
501 internal_error ("%s does not support predicted_by_p.", cfg_hooks
->name
);
503 return cfg_hooks
->predicted_by_p (bb
, predictor
);
506 /* Merges basic block B into basic block A. */
509 merge_blocks (basic_block a
, basic_block b
)
514 if (!cfg_hooks
->merge_blocks
)
515 internal_error ("%s does not support merge_blocks.", cfg_hooks
->name
);
517 cfg_hooks
->merge_blocks (a
, b
);
519 /* Normally there should only be one successor of A and that is B, but
520 partway though the merge of blocks for conditional_execution we'll
521 be merging a TEST block with THEN and ELSE successors. Free the
522 whole lot of them and hope the caller knows what they're doing. */
524 FOR_EACH_EDGE (e
, a
->succ
, ix
)
525 remove_edge (EDGE_I (a
->succ
, ix
));
527 /* Adjust the edges out of B for the new owner. */
528 FOR_EACH_EDGE (e
, b
->succ
, ix
)
531 a
->flags
|= b
->flags
;
533 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
534 b
->pred
= b
->succ
= NULL
;
535 a
->global_live_at_end
= b
->global_live_at_end
;
537 if (dom_computed
[CDI_DOMINATORS
])
538 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
540 if (dom_computed
[CDI_DOMINATORS
])
541 delete_from_dominance_info (CDI_DOMINATORS
, b
);
542 if (dom_computed
[CDI_POST_DOMINATORS
])
543 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
548 /* Split BB into entry part and the rest (the rest is the newly created block).
549 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
550 part. Returns the edge connecting the entry part to the rest. */
553 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
554 void (*new_bb_cbk
) (basic_block
))
557 basic_block dummy
, jump
;
560 if (!cfg_hooks
->make_forwarder_block
)
561 internal_error ("%s does not support make_forwarder_block.",
564 fallthru
= split_block_after_labels (bb
);
565 dummy
= fallthru
->src
;
568 /* Redirect back edges we want to keep. */
569 FOR_EACH_EDGE (e
, dummy
->pred
, ix
)
571 if (redirect_edge_p (e
))
574 dummy
->frequency
-= EDGE_FREQUENCY (e
);
575 dummy
->count
-= e
->count
;
576 if (dummy
->frequency
< 0)
577 dummy
->frequency
= 0;
578 if (dummy
->count
< 0)
580 fallthru
->count
-= e
->count
;
581 if (fallthru
->count
< 0)
584 jump
= redirect_edge_and_branch_force (e
, bb
);
589 if (dom_computed
[CDI_DOMINATORS
] >= DOM_CONS_OK
)
591 basic_block doms_to_fix
[2];
593 doms_to_fix
[0] = dummy
;
595 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, 2);
598 cfg_hooks
->make_forwarder_block (fallthru
);
604 tidy_fallthru_edge (edge e
)
606 if (cfg_hooks
->tidy_fallthru_edge
)
607 cfg_hooks
->tidy_fallthru_edge (e
);
610 /* Fix up edges that now fall through, or rather should now fall through
611 but previously required a jump around now deleted blocks. Simplify
612 the search by only examining blocks numerically adjacent, since this
613 is how find_basic_blocks created them. */
616 tidy_fallthru_edges (void)
620 if (!cfg_hooks
->tidy_fallthru_edge
)
623 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
626 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, next_bb
)
632 /* We care about simple conditional or unconditional jumps with
635 If we had a conditional branch to the next instruction when
636 find_basic_blocks was called, then there will only be one
637 out edge for the block which ended with the conditional
638 branch (since we do not create duplicate edges).
640 Furthermore, the edge will be marked as a fallthru because we
641 merge the flags for the duplicate edges. So we do not want to
642 check that the edge is not a FALLTHRU edge. */
644 if (EDGE_COUNT (b
->succ
) == 1)
646 s
= EDGE_0 (b
->succ
);
647 if (! (s
->flags
& EDGE_COMPLEX
)
649 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
650 tidy_fallthru_edge (s
);
655 /* Returns true if we can duplicate basic block BB. */
658 can_duplicate_block_p (basic_block bb
)
663 if (!cfg_hooks
->can_duplicate_block_p
)
664 internal_error ("%s does not support can_duplicate_block_p.",
667 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
)
670 /* Duplicating fallthru block to exit would require adding a jump
671 and splitting the real last BB. */
672 FOR_EACH_EDGE (e
, bb
->succ
, ix
)
673 if (e
->dest
== EXIT_BLOCK_PTR
&& e
->flags
& EDGE_FALLTHRU
)
676 return cfg_hooks
->can_duplicate_block_p (bb
);
679 /* Duplicates basic block BB and redirects edge E to it. Returns the
683 duplicate_block (basic_block bb
, edge e
)
688 gcov_type new_count
= e
? e
->count
: 0;
690 if (!cfg_hooks
->duplicate_block
)
691 internal_error ("%s does not support duplicate_block.",
694 if (bb
->count
< new_count
)
695 new_count
= bb
->count
;
698 #ifdef ENABLE_CHECKING
699 if (!can_duplicate_block_p (bb
))
703 new_bb
= cfg_hooks
->duplicate_block (bb
);
705 new_bb
->loop_depth
= bb
->loop_depth
;
706 new_bb
->flags
= bb
->flags
;
707 FOR_EACH_EDGE (s
, bb
->succ
, ix
)
709 /* Since we are creating edges from a new block to successors
710 of another block (which therefore are known to be disjoint), there
711 is no need to actually check for duplicated edges. */
712 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
713 n
->probability
= s
->probability
;
716 /* Take care for overflows! */
717 n
->count
= s
->count
* (new_count
* 10000 / bb
->count
) / 10000;
718 s
->count
-= n
->count
;
727 new_bb
->count
= new_count
;
728 bb
->count
-= new_count
;
730 new_bb
->frequency
= EDGE_FREQUENCY (e
);
731 bb
->frequency
-= EDGE_FREQUENCY (e
);
733 redirect_edge_and_branch_force (e
, new_bb
);
737 if (bb
->frequency
< 0)
742 new_bb
->count
= bb
->count
;
743 new_bb
->frequency
= bb
->frequency
;
746 new_bb
->rbi
->original
= bb
;
747 bb
->rbi
->copy
= new_bb
;
752 /* Return 1 if BB ends with a call, possibly followed by some
753 instructions that must stay with the call, 0 otherwise. */
756 block_ends_with_call_p (basic_block bb
)
758 if (!cfg_hooks
->block_ends_with_call_p
)
759 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
761 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
764 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
767 block_ends_with_condjump_p (basic_block bb
)
769 if (!cfg_hooks
->block_ends_with_condjump_p
)
770 internal_error ("%s does not support block_ends_with_condjump_p",
773 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
776 /* Add fake edges to the function exit for any non constant and non noreturn
777 calls, volatile inline assembly in the bitmap of blocks specified by
778 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
781 The goal is to expose cases in which entering a basic block does not imply
782 that all subsequent instructions must be executed. */
785 flow_call_edges_add (sbitmap blocks
)
787 if (!cfg_hooks
->flow_call_edges_add
)
788 internal_error ("%s does not support flow_call_edges_add",
791 return (cfg_hooks
->flow_call_edges_add
) (blocks
);