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 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:
32 - Local CFG construction
33 find_sub_basic_blocks */
37 #include "coretypes.h"
41 #include "hard-reg-set.h"
42 #include "basic-block.h"
51 static int count_basic_blocks (rtx
);
52 static void find_basic_blocks_1 (rtx
);
53 static void make_edges (rtx
, basic_block
, basic_block
, int);
54 static void make_label_edge (sbitmap
*, basic_block
, rtx
, int);
55 static void find_bb_boundaries (basic_block
);
56 static void compute_outgoing_frequencies (basic_block
);
58 /* Return true if insn is something that should be contained inside basic
62 inside_basic_block_p (rtx insn
)
64 switch (GET_CODE (insn
))
67 /* Avoid creating of basic block for jumptables. */
68 return (NEXT_INSN (insn
) == 0
69 || GET_CODE (NEXT_INSN (insn
)) != JUMP_INSN
70 || (GET_CODE (PATTERN (NEXT_INSN (insn
))) != ADDR_VEC
71 && GET_CODE (PATTERN (NEXT_INSN (insn
))) != ADDR_DIFF_VEC
));
74 return (GET_CODE (PATTERN (insn
)) != ADDR_VEC
75 && GET_CODE (PATTERN (insn
)) != ADDR_DIFF_VEC
);
90 /* Return true if INSN may cause control flow transfer, so it should be last in
94 control_flow_insn_p (rtx insn
)
98 switch (GET_CODE (insn
))
105 /* Jump insn always causes control transfer except for tablejumps. */
106 return (GET_CODE (PATTERN (insn
)) != ADDR_VEC
107 && GET_CODE (PATTERN (insn
)) != ADDR_DIFF_VEC
);
110 /* Noreturn and sibling call instructions terminate the basic blocks
111 (but only if they happen unconditionally). */
112 if ((SIBLING_CALL_P (insn
)
113 || find_reg_note (insn
, REG_NORETURN
, 0))
114 && GET_CODE (PATTERN (insn
)) != COND_EXEC
)
116 /* Call insn may return to the nonlocal goto handler. */
117 return ((nonlocal_goto_handler_labels
118 && (0 == (note
= find_reg_note (insn
, REG_EH_REGION
,
120 || INTVAL (XEXP (note
, 0)) >= 0))
122 || can_throw_internal (insn
));
125 return (flag_non_call_exceptions
&& can_throw_internal (insn
));
128 /* It is nonsense to reach barrier when looking for the
129 end of basic block, but before dead code is eliminated
138 /* Count the basic blocks of the function. */
141 count_basic_blocks (rtx f
)
144 bool saw_insn
= false;
147 for (insn
= f
; insn
; insn
= NEXT_INSN (insn
))
149 /* Code labels and barriers causes current basic block to be
150 terminated at previous real insn. */
151 if ((GET_CODE (insn
) == CODE_LABEL
|| GET_CODE (insn
) == BARRIER
)
153 count
++, saw_insn
= false;
155 /* Start basic block if needed. */
156 if (!saw_insn
&& inside_basic_block_p (insn
))
159 /* Control flow insn causes current basic block to be terminated. */
160 if (saw_insn
&& control_flow_insn_p (insn
))
161 count
++, saw_insn
= false;
167 /* The rest of the compiler works a bit smoother when we don't have to
168 check for the edge case of do-nothing functions with no basic blocks. */
171 emit_insn (gen_rtx_USE (VOIDmode
, const0_rtx
));
178 /* Create an edge between two basic blocks. FLAGS are auxiliary information
179 about the edge that is accumulated between calls. */
181 /* Create an edge from a basic block to a label. */
184 make_label_edge (sbitmap
*edge_cache
, basic_block src
, rtx label
, int flags
)
186 if (GET_CODE (label
) != CODE_LABEL
)
189 /* If the label was never emitted, this insn is junk, but avoid a
190 crash trying to refer to BLOCK_FOR_INSN (label). This can happen
191 as a result of a syntax error and a diagnostic has already been
194 if (INSN_UID (label
) == 0)
197 cached_make_edge (edge_cache
, src
, BLOCK_FOR_INSN (label
), flags
);
200 /* Create the edges generated by INSN in REGION. */
203 rtl_make_eh_edge (sbitmap
*edge_cache
, basic_block src
, rtx insn
)
205 int is_call
= GET_CODE (insn
) == CALL_INSN
? EDGE_ABNORMAL_CALL
: 0;
208 handlers
= reachable_handlers (insn
);
210 for (i
= handlers
; i
; i
= XEXP (i
, 1))
211 make_label_edge (edge_cache
, src
, XEXP (i
, 0),
212 EDGE_ABNORMAL
| EDGE_EH
| is_call
);
214 free_INSN_LIST_list (&handlers
);
217 /* Identify the edges between basic blocks MIN to MAX.
219 NONLOCAL_LABEL_LIST is a list of non-local labels in the function. Blocks
220 that are otherwise unreachable may be reachable with a non-local goto.
222 BB_EH_END is an array indexed by basic block number in which we record
223 the list of exception regions active at the end of the basic block. */
226 make_edges (rtx label_value_list
, basic_block min
, basic_block max
, int update_p
)
229 sbitmap
*edge_cache
= NULL
;
231 /* Assume no computed jump; revise as we create edges. */
232 current_function_has_computed_jump
= 0;
234 /* If we are partitioning hot and cold basic blocks into separate
235 sections, we cannot assume there is no computed jump. */
237 if (flag_reorder_blocks_and_partition
)
238 current_function_has_computed_jump
= 1;
240 /* Heavy use of computed goto in machine-generated code can lead to
241 nearly fully-connected CFGs. In that case we spend a significant
242 amount of time searching the edge lists for duplicates. */
243 if (forced_labels
|| label_value_list
|| cfun
->max_jumptable_ents
> 100)
245 edge_cache
= sbitmap_vector_alloc (last_basic_block
, last_basic_block
);
246 sbitmap_vector_zero (edge_cache
, last_basic_block
);
249 FOR_BB_BETWEEN (bb
, min
, max
->next_bb
, next_bb
)
253 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
254 if (e
->dest
!= EXIT_BLOCK_PTR
)
255 SET_BIT (edge_cache
[bb
->index
], e
->dest
->index
);
259 /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block
260 is always the entry. */
261 if (min
== ENTRY_BLOCK_PTR
->next_bb
)
262 cached_make_edge (edge_cache
, ENTRY_BLOCK_PTR
, min
,
265 FOR_BB_BETWEEN (bb
, min
, max
->next_bb
, next_bb
)
269 int force_fallthru
= 0;
272 if (GET_CODE (BB_HEAD (bb
)) == CODE_LABEL
273 && LABEL_ALT_ENTRY_P (BB_HEAD (bb
)))
274 cached_make_edge (NULL
, ENTRY_BLOCK_PTR
, bb
, 0);
276 /* Examine the last instruction of the block, and discover the
277 ways we can leave the block. */
280 code
= GET_CODE (insn
);
283 if (code
== JUMP_INSN
)
287 /* Recognize exception handling placeholders. */
288 if (GET_CODE (PATTERN (insn
)) == RESX
)
289 rtl_make_eh_edge (edge_cache
, bb
, insn
);
291 /* Recognize a non-local goto as a branch outside the
293 else if (find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
296 /* Recognize a tablejump and do the right thing. */
297 else if (tablejump_p (insn
, NULL
, &tmp
))
302 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
303 vec
= XVEC (PATTERN (tmp
), 0);
305 vec
= XVEC (PATTERN (tmp
), 1);
307 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
308 make_label_edge (edge_cache
, bb
,
309 XEXP (RTVEC_ELT (vec
, j
), 0), 0);
311 /* Some targets (eg, ARM) emit a conditional jump that also
312 contains the out-of-range target. Scan for these and
313 add an edge if necessary. */
314 if ((tmp
= single_set (insn
)) != NULL
315 && SET_DEST (tmp
) == pc_rtx
316 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
317 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
)
318 make_label_edge (edge_cache
, bb
,
319 XEXP (XEXP (SET_SRC (tmp
), 2), 0), 0);
321 #ifdef CASE_DROPS_THROUGH
322 /* Silly VAXen. The ADDR_VEC is going to be in the way of
323 us naturally detecting fallthru into the next block. */
328 /* If this is a computed jump, then mark it as reaching
329 everything on the label_value_list and forced_labels list. */
330 else if (computed_jump_p (insn
))
332 current_function_has_computed_jump
= 1;
334 for (x
= label_value_list
; x
; x
= XEXP (x
, 1))
335 make_label_edge (edge_cache
, bb
, XEXP (x
, 0), EDGE_ABNORMAL
);
337 for (x
= forced_labels
; x
; x
= XEXP (x
, 1))
338 make_label_edge (edge_cache
, bb
, XEXP (x
, 0), EDGE_ABNORMAL
);
341 /* Returns create an exit out. */
342 else if (returnjump_p (insn
))
343 cached_make_edge (edge_cache
, bb
, EXIT_BLOCK_PTR
, 0);
345 /* Otherwise, we have a plain conditional or unconditional jump. */
348 if (! JUMP_LABEL (insn
))
350 make_label_edge (edge_cache
, bb
, JUMP_LABEL (insn
), 0);
354 /* If this is a sibling call insn, then this is in effect a combined call
355 and return, and so we need an edge to the exit block. No need to
356 worry about EH edges, since we wouldn't have created the sibling call
357 in the first place. */
358 if (code
== CALL_INSN
&& SIBLING_CALL_P (insn
))
359 cached_make_edge (edge_cache
, bb
, EXIT_BLOCK_PTR
,
360 EDGE_SIBCALL
| EDGE_ABNORMAL
);
362 /* If this is a CALL_INSN, then mark it as reaching the active EH
363 handler for this CALL_INSN. If we're handling non-call
364 exceptions then any insn can reach any of the active handlers.
365 Also mark the CALL_INSN as reaching any nonlocal goto handler. */
366 else if (code
== CALL_INSN
|| flag_non_call_exceptions
)
368 /* Add any appropriate EH edges. */
369 rtl_make_eh_edge (edge_cache
, bb
, insn
);
371 if (code
== CALL_INSN
&& nonlocal_goto_handler_labels
)
373 /* ??? This could be made smarter: in some cases it's possible
374 to tell that certain calls will not do a nonlocal goto.
375 For example, if the nested functions that do the nonlocal
376 gotos do not have their addresses taken, then only calls to
377 those functions or to other nested functions that use them
378 could possibly do nonlocal gotos. */
380 /* We do know that a REG_EH_REGION note with a value less
381 than 0 is guaranteed not to perform a non-local goto. */
382 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
384 if (!note
|| INTVAL (XEXP (note
, 0)) >= 0)
385 for (x
= nonlocal_goto_handler_labels
; x
; x
= XEXP (x
, 1))
386 make_label_edge (edge_cache
, bb
, XEXP (x
, 0),
387 EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
);
391 /* Find out if we can drop through to the next block. */
392 insn
= NEXT_INSN (insn
);
393 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
394 if (e
->dest
== EXIT_BLOCK_PTR
&& e
->flags
& EDGE_FALLTHRU
)
400 && GET_CODE (insn
) == NOTE
401 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
)
402 insn
= NEXT_INSN (insn
);
404 if (!insn
|| (bb
->next_bb
== EXIT_BLOCK_PTR
&& force_fallthru
))
405 cached_make_edge (edge_cache
, bb
, EXIT_BLOCK_PTR
, EDGE_FALLTHRU
);
406 else if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
408 if (force_fallthru
|| insn
== BB_HEAD (bb
->next_bb
))
409 cached_make_edge (edge_cache
, bb
, bb
->next_bb
, EDGE_FALLTHRU
);
414 sbitmap_vector_free (edge_cache
);
417 /* Find all basic blocks of the function whose first insn is F.
419 Collect and return a list of labels whose addresses are taken. This
420 will be used in make_edges for use with computed gotos. */
423 find_basic_blocks_1 (rtx f
)
426 rtx bb_note
= NULL_RTX
;
430 basic_block prev
= ENTRY_BLOCK_PTR
;
432 /* We process the instructions in a slightly different way than we did
433 previously. This is so that we see a NOTE_BASIC_BLOCK after we have
434 closed out the previous block, so that it gets attached at the proper
435 place. Since this form should be equivalent to the previous,
436 count_basic_blocks continues to use the old form as a check. */
438 for (insn
= f
; insn
; insn
= next
)
440 enum rtx_code code
= GET_CODE (insn
);
442 next
= NEXT_INSN (insn
);
444 if ((GET_CODE (insn
) == CODE_LABEL
|| GET_CODE (insn
) == BARRIER
)
447 prev
= create_basic_block_structure (head
, end
, bb_note
, prev
);
448 head
= end
= NULL_RTX
;
452 if (inside_basic_block_p (insn
))
454 if (head
== NULL_RTX
)
459 if (head
&& control_flow_insn_p (insn
))
461 prev
= create_basic_block_structure (head
, end
, bb_note
, prev
);
462 head
= end
= NULL_RTX
;
470 int kind
= NOTE_LINE_NUMBER (insn
);
472 /* Look for basic block notes with which to keep the
473 basic_block_info pointers stable. Unthread the note now;
474 we'll put it back at the right place in create_basic_block.
475 Or not at all if we've already found a note in this block. */
476 if (kind
== NOTE_INSN_BASIC_BLOCK
)
478 if (bb_note
== NULL_RTX
)
481 next
= delete_insn (insn
);
497 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == CALL_INSN
)
501 /* Make a list of all labels referred to other than by jumps.
503 Make a special exception for labels followed by an ADDR*VEC,
504 as this would be a part of the tablejump setup code.
506 Make a special exception to registers loaded with label
507 values just before jump insns that use them. */
509 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
510 if (REG_NOTE_KIND (note
) == REG_LABEL
)
512 rtx lab
= XEXP (note
, 0), next
;
514 if ((next
= next_nonnote_insn (lab
)) != NULL
515 && GET_CODE (next
) == JUMP_INSN
516 && (GET_CODE (PATTERN (next
)) == ADDR_VEC
517 || GET_CODE (PATTERN (next
)) == ADDR_DIFF_VEC
))
519 else if (GET_CODE (lab
) == NOTE
)
521 else if (GET_CODE (NEXT_INSN (insn
)) == JUMP_INSN
522 && find_reg_note (NEXT_INSN (insn
), REG_LABEL
, lab
))
525 lvl
= alloc_EXPR_LIST (0, XEXP (note
, 0), lvl
);
530 if (head
!= NULL_RTX
)
531 create_basic_block_structure (head
, end
, bb_note
, prev
);
533 delete_insn (bb_note
);
535 if (last_basic_block
!= n_basic_blocks
)
538 label_value_list
= lvl
;
539 clear_aux_for_blocks ();
543 /* Find basic blocks of the current function.
544 F is the first insn of the function and NREGS the number of register
548 find_basic_blocks (rtx f
, int nregs ATTRIBUTE_UNUSED
,
549 FILE *file ATTRIBUTE_UNUSED
)
553 timevar_push (TV_CFG
);
555 /* Flush out existing data. */
556 if (basic_block_info
!= NULL
)
560 /* Clear bb->aux on all extant basic blocks. We'll use this as a
561 tag for reuse during create_basic_block, just in case some pass
562 copies around basic block notes improperly. */
566 basic_block_info
= NULL
;
569 n_basic_blocks
= count_basic_blocks (f
);
570 last_basic_block
= 0;
571 ENTRY_BLOCK_PTR
->next_bb
= EXIT_BLOCK_PTR
;
572 EXIT_BLOCK_PTR
->prev_bb
= ENTRY_BLOCK_PTR
;
574 /* Size the basic block table. The actual structures will be allocated
575 by find_basic_blocks_1, since we want to keep the structure pointers
576 stable across calls to find_basic_blocks. */
577 /* ??? This whole issue would be much simpler if we called find_basic_blocks
578 exactly once, and thereafter we don't have a single long chain of
579 instructions at all until close to the end of compilation when we
580 actually lay them out. */
582 VARRAY_BB_INIT (basic_block_info
, n_basic_blocks
, "basic_block_info");
584 find_basic_blocks_1 (f
);
586 /* Discover the edges of our cfg. */
587 make_edges (label_value_list
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, 0);
589 /* Do very simple cleanup now, for the benefit of code that runs between
590 here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns. */
591 tidy_fallthru_edges ();
593 #ifdef ENABLE_CHECKING
596 timevar_pop (TV_CFG
);
599 /* State of basic block as seen by find_sub_basic_blocks. */
600 enum state
{BLOCK_NEW
= 0, BLOCK_ORIGINAL
, BLOCK_TO_SPLIT
};
602 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
603 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
605 /* Scan basic block BB for possible BB boundaries inside the block
606 and create new basic blocks in the progress. */
609 find_bb_boundaries (basic_block bb
)
611 rtx insn
= BB_HEAD (bb
);
612 rtx end
= BB_END (bb
);
613 rtx flow_transfer_insn
= NULL_RTX
;
614 edge fallthru
= NULL
;
616 if (insn
== BB_END (bb
))
619 if (GET_CODE (insn
) == CODE_LABEL
)
620 insn
= NEXT_INSN (insn
);
622 /* Scan insn chain and try to find new basic block boundaries. */
625 enum rtx_code code
= GET_CODE (insn
);
627 /* On code label, split current basic block. */
628 if (code
== CODE_LABEL
)
630 fallthru
= split_block (bb
, PREV_INSN (insn
));
631 if (flow_transfer_insn
)
632 BB_END (bb
) = flow_transfer_insn
;
635 remove_edge (fallthru
);
636 flow_transfer_insn
= NULL_RTX
;
637 if (LABEL_ALT_ENTRY_P (insn
))
638 make_edge (ENTRY_BLOCK_PTR
, bb
, 0);
641 /* In case we've previously seen an insn that effects a control
642 flow transfer, split the block. */
643 if (flow_transfer_insn
&& inside_basic_block_p (insn
))
645 fallthru
= split_block (bb
, PREV_INSN (insn
));
646 BB_END (bb
) = flow_transfer_insn
;
648 remove_edge (fallthru
);
649 flow_transfer_insn
= NULL_RTX
;
652 if (control_flow_insn_p (insn
))
653 flow_transfer_insn
= insn
;
656 insn
= NEXT_INSN (insn
);
659 /* In case expander replaced normal insn by sequence terminating by
660 return and barrier, or possibly other sequence not behaving like
661 ordinary jump, we need to take care and move basic block boundary. */
662 if (flow_transfer_insn
)
663 BB_END (bb
) = flow_transfer_insn
;
665 /* We've possibly replaced the conditional jump by conditional jump
666 followed by cleanup at fallthru edge, so the outgoing edges may
668 purge_dead_edges (bb
);
671 /* Assume that frequency of basic block B is known. Compute frequencies
672 and probabilities of outgoing edges. */
675 compute_outgoing_frequencies (basic_block b
)
679 if (b
->succ
&& b
->succ
->succ_next
&& !b
->succ
->succ_next
->succ_next
)
681 rtx note
= find_reg_note (BB_END (b
), REG_BR_PROB
, NULL
);
687 probability
= INTVAL (XEXP (note
, 0));
689 e
->probability
= probability
;
690 e
->count
= ((b
->count
* probability
+ REG_BR_PROB_BASE
/ 2)
692 f
= FALLTHRU_EDGE (b
);
693 f
->probability
= REG_BR_PROB_BASE
- probability
;
694 f
->count
= b
->count
- e
->count
;
697 if (b
->succ
&& !b
->succ
->succ_next
)
700 e
->probability
= REG_BR_PROB_BASE
;
705 /* Assume that someone emitted code with control flow instructions to the
706 basic block. Update the data structure. */
709 find_many_sub_basic_blocks (sbitmap blocks
)
711 basic_block bb
, min
, max
;
715 TEST_BIT (blocks
, bb
->index
) ? BLOCK_TO_SPLIT
: BLOCK_ORIGINAL
);
718 if (STATE (bb
) == BLOCK_TO_SPLIT
)
719 find_bb_boundaries (bb
);
722 if (STATE (bb
) != BLOCK_ORIGINAL
)
726 for (; bb
!= EXIT_BLOCK_PTR
; bb
= bb
->next_bb
)
727 if (STATE (bb
) != BLOCK_ORIGINAL
)
730 /* Now re-scan and wire in all edges. This expect simple (conditional)
731 jumps at the end of each new basic blocks. */
732 make_edges (NULL
, min
, max
, 1);
734 /* Update branch probabilities. Expect only (un)conditional jumps
735 to be created with only the forward edges. */
736 FOR_BB_BETWEEN (bb
, min
, max
->next_bb
, next_bb
)
740 if (STATE (bb
) == BLOCK_ORIGINAL
)
742 if (STATE (bb
) == BLOCK_NEW
)
746 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
748 bb
->count
+= e
->count
;
749 bb
->frequency
+= EDGE_FREQUENCY (e
);
753 compute_outgoing_frequencies (bb
);
760 /* Like above but for single basic block only. */
763 find_sub_basic_blocks (basic_block bb
)
765 basic_block min
, max
, b
;
766 basic_block next
= bb
->next_bb
;
769 find_bb_boundaries (bb
);
772 /* Now re-scan and wire in all edges. This expect simple (conditional)
773 jumps at the end of each new basic blocks. */
774 make_edges (NULL
, min
, max
, 1);
776 /* Update branch probabilities. Expect only (un)conditional jumps
777 to be created with only the forward edges. */
778 FOR_BB_BETWEEN (b
, min
, max
->next_bb
, next_bb
)
786 for (e
= b
->pred
; e
; e
= e
->pred_next
)
788 b
->count
+= e
->count
;
789 b
->frequency
+= EDGE_FREQUENCY (e
);
793 compute_outgoing_frequencies (b
);