1 /* Control flow graph building code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
5 This file is part of GCC.
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
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
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
22 /* find_basic_blocks divides the current function's rtl into basic
23 blocks and constructs the CFG. The blocks are recorded in the
24 basic_block_info array; the CFG exists in the edge structures
25 referenced by the blocks.
27 find_basic_blocks also finds any unreachable loops and deletes them.
29 Available functionality:
35 #include "coretypes.h"
39 #include "hard-reg-set.h"
40 #include "basic-block.h"
49 static int count_basic_blocks (rtx
);
50 static void find_basic_blocks_1 (rtx
);
51 static void make_edges (basic_block
, basic_block
, int);
52 static void make_label_edge (sbitmap
*, basic_block
, rtx
, int);
53 static void find_bb_boundaries (basic_block
);
54 static void compute_outgoing_frequencies (basic_block
);
56 /* Return true if insn is something that should be contained inside basic
60 inside_basic_block_p (rtx insn
)
62 switch (GET_CODE (insn
))
65 /* Avoid creating of basic block for jumptables. */
66 return (NEXT_INSN (insn
) == 0
67 || !JUMP_P (NEXT_INSN (insn
))
68 || (GET_CODE (PATTERN (NEXT_INSN (insn
))) != ADDR_VEC
69 && GET_CODE (PATTERN (NEXT_INSN (insn
))) != ADDR_DIFF_VEC
));
72 return (GET_CODE (PATTERN (insn
)) != ADDR_VEC
73 && GET_CODE (PATTERN (insn
)) != ADDR_DIFF_VEC
);
88 /* Return true if INSN may cause control flow transfer, so it should be last in
92 control_flow_insn_p (rtx insn
)
96 switch (GET_CODE (insn
))
103 /* Jump insn always causes control transfer except for tablejumps. */
104 return (GET_CODE (PATTERN (insn
)) != ADDR_VEC
105 && GET_CODE (PATTERN (insn
)) != ADDR_DIFF_VEC
);
108 /* Noreturn and sibling call instructions terminate the basic blocks
109 (but only if they happen unconditionally). */
110 if ((SIBLING_CALL_P (insn
)
111 || find_reg_note (insn
, REG_NORETURN
, 0))
112 && GET_CODE (PATTERN (insn
)) != COND_EXEC
)
114 /* Call insn may return to the nonlocal goto handler. */
115 return ((nonlocal_goto_handler_labels
116 && (0 == (note
= find_reg_note (insn
, REG_EH_REGION
,
118 || INTVAL (XEXP (note
, 0)) >= 0))
120 || can_throw_internal (insn
));
123 return (flag_non_call_exceptions
&& can_throw_internal (insn
));
126 /* It is nonsense to reach barrier when looking for the
127 end of basic block, but before dead code is eliminated
136 /* Count the basic blocks of the function. */
139 count_basic_blocks (rtx f
)
142 bool saw_insn
= false;
145 for (insn
= f
; insn
; insn
= NEXT_INSN (insn
))
147 /* Code labels and barriers causes current basic block to be
148 terminated at previous real insn. */
149 if ((LABEL_P (insn
) || BARRIER_P (insn
))
151 count
++, saw_insn
= false;
153 /* Start basic block if needed. */
154 if (!saw_insn
&& inside_basic_block_p (insn
))
157 /* Control flow insn causes current basic block to be terminated. */
158 if (saw_insn
&& control_flow_insn_p (insn
))
159 count
++, saw_insn
= false;
165 /* The rest of the compiler works a bit smoother when we don't have to
166 check for the edge case of do-nothing functions with no basic blocks. */
169 emit_insn (gen_rtx_USE (VOIDmode
, const0_rtx
));
176 /* Create an edge between two basic blocks. FLAGS are auxiliary information
177 about the edge that is accumulated between calls. */
179 /* Create an edge from a basic block to a label. */
182 make_label_edge (sbitmap
*edge_cache
, basic_block src
, rtx label
, int flags
)
184 gcc_assert (LABEL_P (label
));
186 /* If the label was never emitted, this insn is junk, but avoid a
187 crash trying to refer to BLOCK_FOR_INSN (label). This can happen
188 as a result of a syntax error and a diagnostic has already been
191 if (INSN_UID (label
) == 0)
194 cached_make_edge (edge_cache
, src
, BLOCK_FOR_INSN (label
), flags
);
197 /* Create the edges generated by INSN in REGION. */
200 rtl_make_eh_edge (sbitmap
*edge_cache
, basic_block src
, rtx insn
)
202 int is_call
= CALL_P (insn
) ? EDGE_ABNORMAL_CALL
: 0;
205 handlers
= reachable_handlers (insn
);
207 for (i
= handlers
; i
; i
= XEXP (i
, 1))
208 make_label_edge (edge_cache
, src
, XEXP (i
, 0),
209 EDGE_ABNORMAL
| EDGE_EH
| is_call
);
211 free_INSN_LIST_list (&handlers
);
214 /* Identify the edges between basic blocks MIN to MAX.
216 NONLOCAL_LABEL_LIST is a list of non-local labels in the function. Blocks
217 that are otherwise unreachable may be reachable with a non-local goto.
219 BB_EH_END is an array indexed by basic block number in which we record
220 the list of exception regions active at the end of the basic block. */
223 make_edges (basic_block min
, basic_block max
, int update_p
)
226 sbitmap
*edge_cache
= NULL
;
228 /* Heavy use of computed goto in machine-generated code can lead to
229 nearly fully-connected CFGs. In that case we spend a significant
230 amount of time searching the edge lists for duplicates. */
231 if (forced_labels
|| cfun
->max_jumptable_ents
> 100)
233 edge_cache
= sbitmap_vector_alloc (last_basic_block
, last_basic_block
);
234 sbitmap_vector_zero (edge_cache
, last_basic_block
);
237 FOR_BB_BETWEEN (bb
, min
, max
->next_bb
, next_bb
)
242 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
243 if (e
->dest
!= EXIT_BLOCK_PTR
)
244 SET_BIT (edge_cache
[bb
->index
], e
->dest
->index
);
248 /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block
249 is always the entry. */
250 if (min
== ENTRY_BLOCK_PTR
->next_bb
)
251 cached_make_edge (edge_cache
, ENTRY_BLOCK_PTR
, min
,
254 FOR_BB_BETWEEN (bb
, min
, max
->next_bb
, next_bb
)
260 if (LABEL_P (BB_HEAD (bb
))
261 && LABEL_ALT_ENTRY_P (BB_HEAD (bb
)))
262 cached_make_edge (NULL
, ENTRY_BLOCK_PTR
, bb
, 0);
264 /* Examine the last instruction of the block, and discover the
265 ways we can leave the block. */
268 code
= GET_CODE (insn
);
271 if (code
== JUMP_INSN
)
275 /* Recognize exception handling placeholders. */
276 if (GET_CODE (PATTERN (insn
)) == RESX
)
277 rtl_make_eh_edge (edge_cache
, bb
, insn
);
279 /* Recognize a non-local goto as a branch outside the
281 else if (find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
284 /* Recognize a tablejump and do the right thing. */
285 else if (tablejump_p (insn
, NULL
, &tmp
))
290 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
291 vec
= XVEC (PATTERN (tmp
), 0);
293 vec
= XVEC (PATTERN (tmp
), 1);
295 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
296 make_label_edge (edge_cache
, bb
,
297 XEXP (RTVEC_ELT (vec
, j
), 0), 0);
299 /* Some targets (eg, ARM) emit a conditional jump that also
300 contains the out-of-range target. Scan for these and
301 add an edge if necessary. */
302 if ((tmp
= single_set (insn
)) != NULL
303 && SET_DEST (tmp
) == pc_rtx
304 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
305 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
)
306 make_label_edge (edge_cache
, bb
,
307 XEXP (XEXP (SET_SRC (tmp
), 2), 0), 0);
310 /* If this is a computed jump, then mark it as reaching
311 everything on the forced_labels list. */
312 else if (computed_jump_p (insn
))
314 for (x
= forced_labels
; x
; x
= XEXP (x
, 1))
315 make_label_edge (edge_cache
, bb
, XEXP (x
, 0), EDGE_ABNORMAL
);
318 /* Returns create an exit out. */
319 else if (returnjump_p (insn
))
320 cached_make_edge (edge_cache
, bb
, EXIT_BLOCK_PTR
, 0);
322 /* Otherwise, we have a plain conditional or unconditional jump. */
325 gcc_assert (JUMP_LABEL (insn
));
326 make_label_edge (edge_cache
, bb
, JUMP_LABEL (insn
), 0);
330 /* If this is a sibling call insn, then this is in effect a combined call
331 and return, and so we need an edge to the exit block. No need to
332 worry about EH edges, since we wouldn't have created the sibling call
333 in the first place. */
334 if (code
== CALL_INSN
&& SIBLING_CALL_P (insn
))
335 cached_make_edge (edge_cache
, bb
, EXIT_BLOCK_PTR
,
336 EDGE_SIBCALL
| EDGE_ABNORMAL
);
338 /* If this is a CALL_INSN, then mark it as reaching the active EH
339 handler for this CALL_INSN. If we're handling non-call
340 exceptions then any insn can reach any of the active handlers.
341 Also mark the CALL_INSN as reaching any nonlocal goto handler. */
342 else if (code
== CALL_INSN
|| flag_non_call_exceptions
)
344 /* Add any appropriate EH edges. */
345 rtl_make_eh_edge (edge_cache
, bb
, insn
);
347 if (code
== CALL_INSN
&& nonlocal_goto_handler_labels
)
349 /* ??? This could be made smarter: in some cases it's possible
350 to tell that certain calls will not do a nonlocal goto.
351 For example, if the nested functions that do the nonlocal
352 gotos do not have their addresses taken, then only calls to
353 those functions or to other nested functions that use them
354 could possibly do nonlocal gotos. */
356 /* We do know that a REG_EH_REGION note with a value less
357 than 0 is guaranteed not to perform a non-local goto. */
358 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
360 if (!note
|| INTVAL (XEXP (note
, 0)) >= 0)
361 for (x
= nonlocal_goto_handler_labels
; x
; x
= XEXP (x
, 1))
362 make_label_edge (edge_cache
, bb
, XEXP (x
, 0),
363 EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
);
367 /* Find out if we can drop through to the next block. */
368 insn
= NEXT_INSN (insn
);
369 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
370 if (e
&& e
->flags
& EDGE_FALLTHRU
)
375 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
)
376 insn
= NEXT_INSN (insn
);
379 cached_make_edge (edge_cache
, bb
, EXIT_BLOCK_PTR
, EDGE_FALLTHRU
);
380 else if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
382 if (insn
== BB_HEAD (bb
->next_bb
))
383 cached_make_edge (edge_cache
, bb
, bb
->next_bb
, EDGE_FALLTHRU
);
388 sbitmap_vector_free (edge_cache
);
391 /* Find all basic blocks of the function whose first insn is F.
393 Collect and return a list of labels whose addresses are taken. This
394 will be used in make_edges for use with computed gotos. */
397 find_basic_blocks_1 (rtx f
)
400 rtx bb_note
= NULL_RTX
;
403 basic_block prev
= ENTRY_BLOCK_PTR
;
405 /* We process the instructions in a slightly different way than we did
406 previously. This is so that we see a NOTE_BASIC_BLOCK after we have
407 closed out the previous block, so that it gets attached at the proper
408 place. Since this form should be equivalent to the previous,
409 count_basic_blocks continues to use the old form as a check. */
411 for (insn
= f
; insn
; insn
= next
)
413 enum rtx_code code
= GET_CODE (insn
);
415 next
= NEXT_INSN (insn
);
417 if ((LABEL_P (insn
) || BARRIER_P (insn
))
420 prev
= create_basic_block_structure (head
, end
, bb_note
, prev
);
421 head
= end
= NULL_RTX
;
425 if (inside_basic_block_p (insn
))
427 if (head
== NULL_RTX
)
432 if (head
&& control_flow_insn_p (insn
))
434 prev
= create_basic_block_structure (head
, end
, bb_note
, prev
);
435 head
= end
= NULL_RTX
;
443 int kind
= NOTE_LINE_NUMBER (insn
);
445 /* Look for basic block notes with which to keep the
446 basic_block_info pointers stable. Unthread the note now;
447 we'll put it back at the right place in create_basic_block.
448 Or not at all if we've already found a note in this block. */
449 if (kind
== NOTE_INSN_BASIC_BLOCK
)
451 if (bb_note
== NULL_RTX
)
454 next
= delete_insn (insn
);
471 if (head
!= NULL_RTX
)
472 create_basic_block_structure (head
, end
, bb_note
, prev
);
474 delete_insn (bb_note
);
476 gcc_assert (last_basic_block
== n_basic_blocks
);
478 clear_aux_for_blocks ();
482 /* Find basic blocks of the current function.
483 F is the first insn of the function. */
486 find_basic_blocks (rtx f
)
490 timevar_push (TV_CFG
);
492 /* Flush out existing data. */
493 if (basic_block_info
!= NULL
)
497 /* Clear bb->aux on all extant basic blocks. We'll use this as a
498 tag for reuse during create_basic_block, just in case some pass
499 copies around basic block notes improperly. */
503 basic_block_info
= NULL
;
506 n_basic_blocks
= count_basic_blocks (f
);
507 last_basic_block
= 0;
508 ENTRY_BLOCK_PTR
->next_bb
= EXIT_BLOCK_PTR
;
509 EXIT_BLOCK_PTR
->prev_bb
= ENTRY_BLOCK_PTR
;
511 /* Size the basic block table. The actual structures will be allocated
512 by find_basic_blocks_1, since we want to keep the structure pointers
513 stable across calls to find_basic_blocks. */
514 /* ??? This whole issue would be much simpler if we called find_basic_blocks
515 exactly once, and thereafter we don't have a single long chain of
516 instructions at all until close to the end of compilation when we
517 actually lay them out. */
519 VARRAY_BB_INIT (basic_block_info
, n_basic_blocks
, "basic_block_info");
521 find_basic_blocks_1 (f
);
523 profile_status
= PROFILE_ABSENT
;
525 /* Discover the edges of our cfg. */
526 make_edges (ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, 0);
528 /* Do very simple cleanup now, for the benefit of code that runs between
529 here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns. */
530 tidy_fallthru_edges ();
532 #ifdef ENABLE_CHECKING
535 timevar_pop (TV_CFG
);
538 /* State of basic block as seen by find_many_sub_basic_blocks. */
539 enum state
{BLOCK_NEW
= 0, BLOCK_ORIGINAL
, BLOCK_TO_SPLIT
};
541 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
542 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
544 /* Used internally by purge_dead_tablejump_edges, ORed into state. */
545 #define BLOCK_USED_BY_TABLEJUMP 32
546 #define FULL_STATE(BB) ((size_t) (BB)->aux)
549 mark_tablejump_edge (rtx label
)
553 gcc_assert (LABEL_P (label
));
554 /* See comment in make_label_edge. */
555 if (INSN_UID (label
) == 0)
557 bb
= BLOCK_FOR_INSN (label
);
558 SET_STATE (bb
, FULL_STATE (bb
) | BLOCK_USED_BY_TABLEJUMP
);
562 purge_dead_tablejump_edges (basic_block bb
, rtx table
)
564 rtx insn
= BB_END (bb
), tmp
;
570 if (GET_CODE (PATTERN (table
)) == ADDR_VEC
)
571 vec
= XVEC (PATTERN (table
), 0);
573 vec
= XVEC (PATTERN (table
), 1);
575 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
576 mark_tablejump_edge (XEXP (RTVEC_ELT (vec
, j
), 0));
578 /* Some targets (eg, ARM) emit a conditional jump that also
579 contains the out-of-range target. Scan for these and
580 add an edge if necessary. */
581 if ((tmp
= single_set (insn
)) != NULL
582 && SET_DEST (tmp
) == pc_rtx
583 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
584 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
)
585 mark_tablejump_edge (XEXP (XEXP (SET_SRC (tmp
), 2), 0));
587 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
589 if (FULL_STATE (e
->dest
) & BLOCK_USED_BY_TABLEJUMP
)
590 SET_STATE (e
->dest
, FULL_STATE (e
->dest
)
591 & ~(size_t) BLOCK_USED_BY_TABLEJUMP
);
592 else if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
)))
601 /* Scan basic block BB for possible BB boundaries inside the block
602 and create new basic blocks in the progress. */
605 find_bb_boundaries (basic_block bb
)
607 basic_block orig_bb
= bb
;
608 rtx insn
= BB_HEAD (bb
);
609 rtx end
= BB_END (bb
);
611 rtx flow_transfer_insn
= NULL_RTX
;
612 edge fallthru
= NULL
;
614 if (insn
== BB_END (bb
))
618 insn
= NEXT_INSN (insn
);
620 /* Scan insn chain and try to find new basic block boundaries. */
623 enum rtx_code code
= GET_CODE (insn
);
625 /* On code label, split current basic block. */
626 if (code
== CODE_LABEL
)
628 fallthru
= split_block (bb
, PREV_INSN (insn
));
629 if (flow_transfer_insn
)
630 BB_END (bb
) = flow_transfer_insn
;
633 remove_edge (fallthru
);
634 flow_transfer_insn
= NULL_RTX
;
635 if (LABEL_ALT_ENTRY_P (insn
))
636 make_edge (ENTRY_BLOCK_PTR
, bb
, 0);
639 /* In case we've previously seen an insn that effects a control
640 flow transfer, split the block. */
641 if (flow_transfer_insn
&& inside_basic_block_p (insn
))
643 fallthru
= split_block (bb
, PREV_INSN (insn
));
644 BB_END (bb
) = flow_transfer_insn
;
646 remove_edge (fallthru
);
647 flow_transfer_insn
= NULL_RTX
;
650 if (control_flow_insn_p (insn
))
651 flow_transfer_insn
= insn
;
654 insn
= NEXT_INSN (insn
);
657 /* In case expander replaced normal insn by sequence terminating by
658 return and barrier, or possibly other sequence not behaving like
659 ordinary jump, we need to take care and move basic block boundary. */
660 if (flow_transfer_insn
)
661 BB_END (bb
) = flow_transfer_insn
;
663 /* We've possibly replaced the conditional jump by conditional jump
664 followed by cleanup at fallthru edge, so the outgoing edges may
666 purge_dead_edges (bb
);
668 /* purge_dead_edges doesn't handle tablejump's, but if we have split the
669 basic block, we might need to kill some edges. */
670 if (bb
!= orig_bb
&& tablejump_p (BB_END (bb
), NULL
, &table
))
671 purge_dead_tablejump_edges (bb
, table
);
674 /* Assume that frequency of basic block B is known. Compute frequencies
675 and probabilities of outgoing edges. */
678 compute_outgoing_frequencies (basic_block b
)
683 if (EDGE_COUNT (b
->succs
) == 2)
685 rtx note
= find_reg_note (BB_END (b
), REG_BR_PROB
, NULL
);
690 probability
= INTVAL (XEXP (note
, 0));
692 e
->probability
= probability
;
693 e
->count
= ((b
->count
* probability
+ REG_BR_PROB_BASE
/ 2)
695 f
= FALLTHRU_EDGE (b
);
696 f
->probability
= REG_BR_PROB_BASE
- probability
;
697 f
->count
= b
->count
- e
->count
;
702 if (EDGE_COUNT (b
->succs
) == 1)
704 e
= EDGE_SUCC (b
, 0);
705 e
->probability
= REG_BR_PROB_BASE
;
709 guess_outgoing_edge_probabilities (b
);
711 FOR_EACH_EDGE (e
, ei
, b
->succs
)
712 e
->count
= ((b
->count
* e
->probability
+ REG_BR_PROB_BASE
/ 2)
716 /* Assume that someone emitted code with control flow instructions to the
717 basic block. Update the data structure. */
720 find_many_sub_basic_blocks (sbitmap blocks
)
722 basic_block bb
, min
, max
;
726 TEST_BIT (blocks
, bb
->index
) ? BLOCK_TO_SPLIT
: BLOCK_ORIGINAL
);
729 if (STATE (bb
) == BLOCK_TO_SPLIT
)
730 find_bb_boundaries (bb
);
733 if (STATE (bb
) != BLOCK_ORIGINAL
)
737 for (; bb
!= EXIT_BLOCK_PTR
; bb
= bb
->next_bb
)
738 if (STATE (bb
) != BLOCK_ORIGINAL
)
741 /* Now re-scan and wire in all edges. This expect simple (conditional)
742 jumps at the end of each new basic blocks. */
743 make_edges (min
, max
, 1);
745 /* Update branch probabilities. Expect only (un)conditional jumps
746 to be created with only the forward edges. */
747 if (profile_status
!= PROFILE_ABSENT
)
748 FOR_BB_BETWEEN (bb
, min
, max
->next_bb
, next_bb
)
753 if (STATE (bb
) == BLOCK_ORIGINAL
)
755 if (STATE (bb
) == BLOCK_NEW
)
759 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
761 bb
->count
+= e
->count
;
762 bb
->frequency
+= EDGE_FREQUENCY (e
);
766 compute_outgoing_frequencies (bb
);