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
)
112 error ("verify_flow_info: Wrong count of block %i %i",
113 bb
->index
, (int)bb
->count
);
116 if (bb
->frequency
< 0)
118 error ("verify_flow_info: Wrong frequency of block %i %i",
119 bb
->index
, bb
->frequency
);
122 FOR_EACH_EDGE (e
, bb
->succs
)
124 if (last_visited
[e
->dest
->index
+ 2] == bb
)
126 error ("verify_flow_info: Duplicate edge %i->%i",
127 e
->src
->index
, e
->dest
->index
);
130 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
132 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
133 e
->src
->index
, e
->dest
->index
, e
->probability
);
138 error ("verify_flow_info: Wrong count of edge %i->%i %i",
139 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
143 last_visited
[e
->dest
->index
+ 2] = bb
;
145 if (e
->flags
& EDGE_FALLTHRU
)
150 error ("verify_flow_info: Basic block %d succ edge is corrupted",
152 fprintf (stderr
, "Predecessor: ");
153 dump_edge_info (stderr
, e
, 0);
154 fprintf (stderr
, "\nSuccessor: ");
155 dump_edge_info (stderr
, e
, 1);
156 fprintf (stderr
, "\n");
160 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
166 error ("Wrong amount of branch edges after unconditional jump %i", bb
->index
);
170 FOR_EACH_EDGE (e
, bb
->preds
)
174 error ("basic block %d pred edge is corrupted", bb
->index
);
175 fputs ("Predecessor: ", stderr
);
176 dump_edge_info (stderr
, e
, 0);
177 fputs ("\nSuccessor: ", stderr
);
178 dump_edge_info (stderr
, e
, 1);
179 fputc ('\n', stderr
);
182 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
187 /* Complete edge checksumming for ENTRY and EXIT. */
191 FOR_EACH_EDGE (e
, ENTRY_BLOCK_PTR
->succs
)
193 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
197 FOR_EACH_EDGE (e
, EXIT_BLOCK_PTR
->preds
)
199 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
204 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
205 if (edge_checksum
[bb
->index
+ 2])
207 error ("basic block %i edge lists are corrupted", bb
->index
);
212 last_bb_seen
= ENTRY_BLOCK_PTR
;
216 free (edge_checksum
);
218 if (cfg_hooks
->verify_flow_info
)
219 err
|= cfg_hooks
->verify_flow_info ();
221 internal_error ("verify_flow_info failed");
222 timevar_pop (TV_CFG_VERIFY
);
225 /* Print out one basic block. This function takes care of the purely
226 graph related information. The cfg hook for the active representation
227 should dump representation-specific information. */
230 dump_bb (basic_block bb
, FILE *outf
, int indent
)
235 s_indent
= alloca ((size_t) indent
+ 1);
236 memset (s_indent
, ' ', (size_t) indent
);
237 s_indent
[indent
] = '\0';
239 fprintf (outf
, ";;%s basic block %d, loop depth %d, count ",
240 s_indent
, bb
->index
, bb
->loop_depth
);
241 fprintf (outf
, HOST_WIDEST_INT_PRINT_DEC
, (HOST_WIDEST_INT
) bb
->count
);
244 fprintf (outf
, ";;%s prev block ", s_indent
);
246 fprintf (outf
, "%d, ", bb
->prev_bb
->index
);
248 fprintf (outf
, "(nil), ");
249 fprintf (outf
, "next block ");
251 fprintf (outf
, "%d", bb
->next_bb
->index
);
253 fprintf (outf
, "(nil)");
256 fprintf (outf
, ";;%s pred: ", s_indent
);
257 FOR_EACH_EDGE (e
, bb
->preds
)
259 dump_edge_info (outf
, e
, 0);
264 fprintf (outf
, ";;%s succ: ", s_indent
);
265 FOR_EACH_EDGE (e
, bb
->succs
)
267 dump_edge_info (outf
, e
, 1);
272 if (cfg_hooks
->dump_bb
)
273 cfg_hooks
->dump_bb (bb
, outf
, indent
);
276 /* Redirect edge E to the given basic block DEST and update underlying program
277 representation. Returns edge representing redirected branch (that may not
278 be equivalent to E in the case of duplicate edges being removed) or NULL
279 if edge is not easily redirectable for whatever reason. */
282 redirect_edge_and_branch (edge e
, basic_block dest
)
286 if (!cfg_hooks
->redirect_edge_and_branch
)
287 internal_error ("%s does not support redirect_edge_and_branch.",
290 ret
= cfg_hooks
->redirect_edge_and_branch (e
, dest
);
295 /* Redirect the edge E to basic block DEST even if it requires creating
296 of a new basic block; then it returns the newly created basic block.
297 Aborts when redirection is impossible. */
300 redirect_edge_and_branch_force (edge e
, basic_block dest
)
304 if (!cfg_hooks
->redirect_edge_and_branch_force
)
305 internal_error ("%s does not support redirect_edge_and_branch_force.",
308 ret
= cfg_hooks
->redirect_edge_and_branch_force (e
, dest
);
313 /* Splits basic block BB after the specified instruction I (but at least after
314 the labels). If I is NULL, splits just after labels. The newly created edge
315 is returned. The new basic block is created just after the old one. */
318 split_block (basic_block bb
, void *i
)
322 if (!cfg_hooks
->split_block
)
323 internal_error ("%s does not support split_block.", cfg_hooks
->name
);
325 new_bb
= cfg_hooks
->split_block (bb
, i
);
329 new_bb
->count
= bb
->count
;
330 new_bb
->frequency
= bb
->frequency
;
331 new_bb
->loop_depth
= bb
->loop_depth
;
333 if (dom_computed
[CDI_DOMINATORS
] >= DOM_CONS_OK
)
335 redirect_immediate_dominators (CDI_DOMINATORS
, bb
, new_bb
);
336 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, bb
);
339 return make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
342 /* Splits block BB just after labels. The newly created edge is returned. */
345 split_block_after_labels (basic_block bb
)
347 return split_block (bb
, NULL
);
350 /* Moves block BB immediately after block AFTER. Returns false if the
351 movement was impossible. */
354 move_block_after (basic_block bb
, basic_block after
)
358 if (!cfg_hooks
->move_block_after
)
359 internal_error ("%s does not support move_block_after.", cfg_hooks
->name
);
361 ret
= cfg_hooks
->move_block_after (bb
, after
);
366 /* Deletes the basic block BB. */
369 delete_basic_block (basic_block bb
)
371 if (!cfg_hooks
->delete_basic_block
)
372 internal_error ("%s does not support delete_basic_block.", cfg_hooks
->name
);
374 cfg_hooks
->delete_basic_block (bb
);
376 /* Remove the edges into and out of this block. Note that there may
377 indeed be edges in, if we are removing an unreachable loop. */
378 while (EDGE_COUNT (bb
->preds
) != 0)
379 remove_edge (EDGE_PRED (bb
, 0));
380 while (EDGE_COUNT (bb
->succs
) != 0)
381 remove_edge (EDGE_SUCC (bb
, 0));
383 VEC_truncate (edge
, bb
->preds
, 0);
384 VEC_truncate (edge
, bb
->succs
, 0);
386 if (dom_computed
[CDI_DOMINATORS
])
387 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
388 if (dom_computed
[CDI_POST_DOMINATORS
])
389 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
391 /* Remove the basic block from the array. */
395 /* Splits edge E and returns the newly created basic block. */
401 gcov_type count
= e
->count
;
402 int freq
= EDGE_FREQUENCY (e
);
405 if (!cfg_hooks
->split_edge
)
406 internal_error ("%s does not support split_edge.", cfg_hooks
->name
);
408 ret
= cfg_hooks
->split_edge (e
);
410 ret
->frequency
= freq
;
411 EDGE_SUCC (ret
, 0)->probability
= REG_BR_PROB_BASE
;
412 EDGE_SUCC (ret
, 0)->count
= count
;
414 if (dom_computed
[CDI_DOMINATORS
])
415 set_immediate_dominator (CDI_DOMINATORS
, ret
, EDGE_PRED (ret
, 0)->src
);
417 if (dom_computed
[CDI_DOMINATORS
] >= DOM_NO_FAST_QUERY
)
419 /* There are two cases:
421 If the immediate dominator of e->dest is not e->src, it
424 If immediate dominator of e->dest is e->src, it may become
425 ret, provided that all other predecessors of e->dest are
426 dominated by e->dest. */
428 if (get_immediate_dominator (CDI_DOMINATORS
, EDGE_SUCC (ret
, 0)->dest
)
429 == EDGE_PRED (ret
, 0)->src
)
431 FOR_EACH_EDGE (f
, EDGE_SUCC (ret
, 0)->dest
->preds
)
433 if (f
== EDGE_SUCC (ret
, 0))
436 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
,
437 EDGE_SUCC (ret
, 0)->dest
))
443 set_immediate_dominator (CDI_DOMINATORS
, EDGE_SUCC (ret
, 0)->dest
, ret
);
450 /* Creates a new basic block just after the basic block AFTER.
451 HEAD and END are the first and the last statement belonging
452 to the block. If both are NULL, an empty block is created. */
455 create_basic_block (void *head
, void *end
, basic_block after
)
459 if (!cfg_hooks
->create_basic_block
)
460 internal_error ("%s does not support create_basic_block.", cfg_hooks
->name
);
462 ret
= cfg_hooks
->create_basic_block (head
, end
, after
);
464 if (dom_computed
[CDI_DOMINATORS
])
465 add_to_dominance_info (CDI_DOMINATORS
, ret
);
466 if (dom_computed
[CDI_POST_DOMINATORS
])
467 add_to_dominance_info (CDI_POST_DOMINATORS
, ret
);
472 /* Creates an empty basic block just after basic block AFTER. */
475 create_empty_bb (basic_block after
)
477 return create_basic_block (NULL
, NULL
, after
);
480 /* Checks whether we may merge blocks BB1 and BB2. */
483 can_merge_blocks_p (basic_block bb1
, basic_block bb2
)
487 if (!cfg_hooks
->can_merge_blocks_p
)
488 internal_error ("%s does not support can_merge_blocks_p.", cfg_hooks
->name
);
490 ret
= cfg_hooks
->can_merge_blocks_p (bb1
, bb2
);
496 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
498 if (!cfg_hooks
->predict_edge
)
499 internal_error ("%s does not support predict_edge.", cfg_hooks
->name
);
501 cfg_hooks
->predict_edge (e
, predictor
, probability
);
505 predicted_by_p (basic_block bb
, enum br_predictor predictor
)
507 if (!cfg_hooks
->predict_edge
)
508 internal_error ("%s does not support predicted_by_p.", cfg_hooks
->name
);
510 return cfg_hooks
->predicted_by_p (bb
, predictor
);
513 /* Merges basic block B into basic block A. */
516 merge_blocks (basic_block a
, basic_block b
)
520 if (!cfg_hooks
->merge_blocks
)
521 internal_error ("%s does not support merge_blocks.", cfg_hooks
->name
);
523 cfg_hooks
->merge_blocks (a
, b
);
525 /* Normally there should only be one successor of A and that is B, but
526 partway though the merge of blocks for conditional_execution we'll
527 be merging a TEST block with THEN and ELSE successors. Free the
528 whole lot of them and hope the caller knows what they're doing. */
530 while (EDGE_COUNT (a
->succs
) != 0)
531 remove_edge (EDGE_SUCC (a
, 0));
533 /* Adjust the edges out of B for the new owner. */
534 FOR_EACH_EDGE (e
, b
->succs
)
540 a
->flags
|= b
->flags
;
542 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
543 b
->preds
= b
->succs
= NULL
;
544 a
->global_live_at_end
= b
->global_live_at_end
;
546 if (dom_computed
[CDI_DOMINATORS
])
547 redirect_immediate_dominators (CDI_DOMINATORS
, b
, a
);
549 if (dom_computed
[CDI_DOMINATORS
])
550 delete_from_dominance_info (CDI_DOMINATORS
, b
);
551 if (dom_computed
[CDI_POST_DOMINATORS
])
552 delete_from_dominance_info (CDI_POST_DOMINATORS
, b
);
557 /* Split BB into entry part and the rest (the rest is the newly created block).
558 Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
559 part. Returns the edge connecting the entry part to the rest. */
562 make_forwarder_block (basic_block bb
, bool (*redirect_edge_p
) (edge
),
563 void (*new_bb_cbk
) (basic_block
))
566 basic_block dummy
, jump
;
568 if (!cfg_hooks
->make_forwarder_block
)
569 internal_error ("%s does not support make_forwarder_block.",
572 fallthru
= split_block_after_labels (bb
);
573 dummy
= fallthru
->src
;
576 /* Redirect back edges we want to keep. */
577 FOR_EACH_EDGE (e
, dummy
->preds
)
579 if (redirect_edge_p (e
))
582 dummy
->frequency
-= EDGE_FREQUENCY (e
);
583 dummy
->count
-= e
->count
;
584 if (dummy
->frequency
< 0)
585 dummy
->frequency
= 0;
586 if (dummy
->count
< 0)
588 fallthru
->count
-= e
->count
;
589 if (fallthru
->count
< 0)
592 jump
= redirect_edge_and_branch_force (e
, bb
);
598 if (dom_computed
[CDI_DOMINATORS
] >= DOM_CONS_OK
)
600 basic_block doms_to_fix
[2];
602 doms_to_fix
[0] = dummy
;
604 iterate_fix_dominators (CDI_DOMINATORS
, doms_to_fix
, 2);
607 cfg_hooks
->make_forwarder_block (fallthru
);
613 tidy_fallthru_edge (edge e
)
615 if (cfg_hooks
->tidy_fallthru_edge
)
616 cfg_hooks
->tidy_fallthru_edge (e
);
619 /* Fix up edges that now fall through, or rather should now fall through
620 but previously required a jump around now deleted blocks. Simplify
621 the search by only examining blocks numerically adjacent, since this
622 is how find_basic_blocks created them. */
625 tidy_fallthru_edges (void)
629 if (!cfg_hooks
->tidy_fallthru_edge
)
632 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
635 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, next_bb
)
641 /* We care about simple conditional or unconditional jumps with
644 If we had a conditional branch to the next instruction when
645 find_basic_blocks was called, then there will only be one
646 out edge for the block which ended with the conditional
647 branch (since we do not create duplicate edges).
649 Furthermore, the edge will be marked as a fallthru because we
650 merge the flags for the duplicate edges. So we do not want to
651 check that the edge is not a FALLTHRU edge. */
653 if (EDGE_COUNT (b
->succs
) == 1)
655 s
= EDGE_SUCC (b
, 0);
656 if (! (s
->flags
& EDGE_COMPLEX
)
658 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
659 tidy_fallthru_edge (s
);
664 /* Returns true if we can duplicate basic block BB. */
667 can_duplicate_block_p (basic_block bb
)
671 if (!cfg_hooks
->can_duplicate_block_p
)
672 internal_error ("%s does not support can_duplicate_block_p.",
675 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
)
678 /* Duplicating fallthru block to exit would require adding a jump
679 and splitting the real last BB. */
680 FOR_EACH_EDGE (e
, bb
->succs
)
682 if (e
->dest
== EXIT_BLOCK_PTR
&& e
->flags
& EDGE_FALLTHRU
)
687 return cfg_hooks
->can_duplicate_block_p (bb
);
690 /* Duplicates basic block BB and redirects edge E to it. Returns the
694 duplicate_block (basic_block bb
, edge e
)
698 gcov_type new_count
= e
? e
->count
: 0;
700 if (!cfg_hooks
->duplicate_block
)
701 internal_error ("%s does not support duplicate_block.",
704 if (bb
->count
< new_count
)
705 new_count
= bb
->count
;
706 if (EDGE_COUNT (bb
->preds
) == 0)
708 #ifdef ENABLE_CHECKING
709 if (!can_duplicate_block_p (bb
))
713 new_bb
= cfg_hooks
->duplicate_block (bb
);
715 new_bb
->loop_depth
= bb
->loop_depth
;
716 new_bb
->flags
= bb
->flags
;
717 FOR_EACH_EDGE (s
, bb
->succs
)
719 /* Since we are creating edges from a new block to successors
720 of another block (which therefore are known to be disjoint), there
721 is no need to actually check for duplicated edges. */
722 n
= unchecked_make_edge (new_bb
, s
->dest
, s
->flags
);
723 n
->probability
= s
->probability
;
726 /* Take care for overflows! */
727 n
->count
= s
->count
* (new_count
* 10000 / bb
->count
) / 10000;
728 s
->count
-= n
->count
;
738 new_bb
->count
= new_count
;
739 bb
->count
-= new_count
;
741 new_bb
->frequency
= EDGE_FREQUENCY (e
);
742 bb
->frequency
-= EDGE_FREQUENCY (e
);
744 redirect_edge_and_branch_force (e
, new_bb
);
748 if (bb
->frequency
< 0)
753 new_bb
->count
= bb
->count
;
754 new_bb
->frequency
= bb
->frequency
;
757 new_bb
->rbi
->original
= bb
;
758 bb
->rbi
->copy
= new_bb
;
763 /* Return 1 if BB ends with a call, possibly followed by some
764 instructions that must stay with the call, 0 otherwise. */
767 block_ends_with_call_p (basic_block bb
)
769 if (!cfg_hooks
->block_ends_with_call_p
)
770 internal_error ("%s does not support block_ends_with_call_p", cfg_hooks
->name
);
772 return (cfg_hooks
->block_ends_with_call_p
) (bb
);
775 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
778 block_ends_with_condjump_p (basic_block bb
)
780 if (!cfg_hooks
->block_ends_with_condjump_p
)
781 internal_error ("%s does not support block_ends_with_condjump_p",
784 return (cfg_hooks
->block_ends_with_condjump_p
) (bb
);
787 /* Add fake edges to the function exit for any non constant and non noreturn
788 calls, volatile inline assembly in the bitmap of blocks specified by
789 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
792 The goal is to expose cases in which entering a basic block does not imply
793 that all subsequent instructions must be executed. */
796 flow_call_edges_add (sbitmap blocks
)
798 if (!cfg_hooks
->flow_call_edges_add
)
799 internal_error ("%s does not support flow_call_edges_add",
802 return (cfg_hooks
->flow_call_edges_add
) (blocks
);