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 (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 || !JUMP_P (NEXT_INSN (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 ((LABEL_P (insn
) || BARRIER_P (insn
))
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 (!LABEL_P (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
= CALL_P (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 (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
|| 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_EACH_EDGE (e
, bb
->succs
)
255 if (e
->dest
!= EXIT_BLOCK_PTR
)
256 SET_BIT (edge_cache
[bb
->index
], e
->dest
->index
);
262 /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block
263 is always the entry. */
264 if (min
== ENTRY_BLOCK_PTR
->next_bb
)
265 cached_make_edge (edge_cache
, ENTRY_BLOCK_PTR
, min
,
268 FOR_BB_BETWEEN (bb
, min
, max
->next_bb
, next_bb
)
272 int force_fallthru
= 0;
275 if (LABEL_P (BB_HEAD (bb
))
276 && LABEL_ALT_ENTRY_P (BB_HEAD (bb
)))
277 cached_make_edge (NULL
, ENTRY_BLOCK_PTR
, bb
, 0);
279 /* Examine the last instruction of the block, and discover the
280 ways we can leave the block. */
283 code
= GET_CODE (insn
);
286 if (code
== JUMP_INSN
)
290 /* Recognize exception handling placeholders. */
291 if (GET_CODE (PATTERN (insn
)) == RESX
)
292 rtl_make_eh_edge (edge_cache
, bb
, insn
);
294 /* Recognize a non-local goto as a branch outside the
296 else if (find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
299 /* Recognize a tablejump and do the right thing. */
300 else if (tablejump_p (insn
, NULL
, &tmp
))
305 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
306 vec
= XVEC (PATTERN (tmp
), 0);
308 vec
= XVEC (PATTERN (tmp
), 1);
310 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
311 make_label_edge (edge_cache
, bb
,
312 XEXP (RTVEC_ELT (vec
, j
), 0), 0);
314 /* Some targets (eg, ARM) emit a conditional jump that also
315 contains the out-of-range target. Scan for these and
316 add an edge if necessary. */
317 if ((tmp
= single_set (insn
)) != NULL
318 && SET_DEST (tmp
) == pc_rtx
319 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
320 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
)
321 make_label_edge (edge_cache
, bb
,
322 XEXP (XEXP (SET_SRC (tmp
), 2), 0), 0);
324 #ifdef CASE_DROPS_THROUGH
325 /* Silly VAXen. The ADDR_VEC is going to be in the way of
326 us naturally detecting fallthru into the next block. */
331 /* If this is a computed jump, then mark it as reaching
332 everything on the forced_labels list. */
333 else if (computed_jump_p (insn
))
335 current_function_has_computed_jump
= 1;
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_EACH_EDGE (e
, bb
->succs
)
395 if (e
->dest
== EXIT_BLOCK_PTR
&& e
->flags
& EDGE_FALLTHRU
)
405 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
)
406 insn
= NEXT_INSN (insn
);
408 if (!insn
|| (bb
->next_bb
== EXIT_BLOCK_PTR
&& force_fallthru
))
409 cached_make_edge (edge_cache
, bb
, EXIT_BLOCK_PTR
, EDGE_FALLTHRU
);
410 else if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
412 if (force_fallthru
|| insn
== BB_HEAD (bb
->next_bb
))
413 cached_make_edge (edge_cache
, bb
, bb
->next_bb
, EDGE_FALLTHRU
);
418 sbitmap_vector_free (edge_cache
);
421 /* Find all basic blocks of the function whose first insn is F.
423 Collect and return a list of labels whose addresses are taken. This
424 will be used in make_edges for use with computed gotos. */
427 find_basic_blocks_1 (rtx f
)
430 rtx bb_note
= NULL_RTX
;
433 basic_block prev
= ENTRY_BLOCK_PTR
;
435 /* We process the instructions in a slightly different way than we did
436 previously. This is so that we see a NOTE_BASIC_BLOCK after we have
437 closed out the previous block, so that it gets attached at the proper
438 place. Since this form should be equivalent to the previous,
439 count_basic_blocks continues to use the old form as a check. */
441 for (insn
= f
; insn
; insn
= next
)
443 enum rtx_code code
= GET_CODE (insn
);
445 next
= NEXT_INSN (insn
);
447 if ((LABEL_P (insn
) || BARRIER_P (insn
))
450 prev
= create_basic_block_structure (head
, end
, bb_note
, prev
);
451 head
= end
= NULL_RTX
;
455 if (inside_basic_block_p (insn
))
457 if (head
== NULL_RTX
)
462 if (head
&& control_flow_insn_p (insn
))
464 prev
= create_basic_block_structure (head
, end
, bb_note
, prev
);
465 head
= end
= NULL_RTX
;
473 int kind
= NOTE_LINE_NUMBER (insn
);
475 /* Look for basic block notes with which to keep the
476 basic_block_info pointers stable. Unthread the note now;
477 we'll put it back at the right place in create_basic_block.
478 Or not at all if we've already found a note in this block. */
479 if (kind
== NOTE_INSN_BASIC_BLOCK
)
481 if (bb_note
== NULL_RTX
)
484 next
= delete_insn (insn
);
501 if (head
!= NULL_RTX
)
502 create_basic_block_structure (head
, end
, bb_note
, prev
);
504 delete_insn (bb_note
);
506 if (last_basic_block
!= n_basic_blocks
)
509 clear_aux_for_blocks ();
513 /* Find basic blocks of the current function.
514 F is the first insn of the function and NREGS the number of register
518 find_basic_blocks (rtx f
, int nregs ATTRIBUTE_UNUSED
,
519 FILE *file ATTRIBUTE_UNUSED
)
523 timevar_push (TV_CFG
);
525 /* Flush out existing data. */
526 if (basic_block_info
!= NULL
)
530 /* Clear bb->aux on all extant basic blocks. We'll use this as a
531 tag for reuse during create_basic_block, just in case some pass
532 copies around basic block notes improperly. */
536 basic_block_info
= NULL
;
539 n_basic_blocks
= count_basic_blocks (f
);
540 last_basic_block
= 0;
541 ENTRY_BLOCK_PTR
->next_bb
= EXIT_BLOCK_PTR
;
542 EXIT_BLOCK_PTR
->prev_bb
= ENTRY_BLOCK_PTR
;
544 /* Size the basic block table. The actual structures will be allocated
545 by find_basic_blocks_1, since we want to keep the structure pointers
546 stable across calls to find_basic_blocks. */
547 /* ??? This whole issue would be much simpler if we called find_basic_blocks
548 exactly once, and thereafter we don't have a single long chain of
549 instructions at all until close to the end of compilation when we
550 actually lay them out. */
552 VARRAY_BB_INIT (basic_block_info
, n_basic_blocks
, "basic_block_info");
554 find_basic_blocks_1 (f
);
556 /* Discover the edges of our cfg. */
557 make_edges (ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, 0);
559 /* Do very simple cleanup now, for the benefit of code that runs between
560 here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns. */
561 tidy_fallthru_edges ();
563 #ifdef ENABLE_CHECKING
566 timevar_pop (TV_CFG
);
569 /* State of basic block as seen by find_sub_basic_blocks. */
570 enum state
{BLOCK_NEW
= 0, BLOCK_ORIGINAL
, BLOCK_TO_SPLIT
};
572 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
573 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
575 /* Scan basic block BB for possible BB boundaries inside the block
576 and create new basic blocks in the progress. */
579 find_bb_boundaries (basic_block bb
)
581 rtx insn
= BB_HEAD (bb
);
582 rtx end
= BB_END (bb
);
583 rtx flow_transfer_insn
= NULL_RTX
;
584 edge fallthru
= NULL
;
586 if (insn
== BB_END (bb
))
590 insn
= NEXT_INSN (insn
);
592 /* Scan insn chain and try to find new basic block boundaries. */
595 enum rtx_code code
= GET_CODE (insn
);
597 /* On code label, split current basic block. */
598 if (code
== CODE_LABEL
)
600 fallthru
= split_block (bb
, PREV_INSN (insn
));
601 if (flow_transfer_insn
)
602 BB_END (bb
) = flow_transfer_insn
;
605 remove_edge (fallthru
);
606 flow_transfer_insn
= NULL_RTX
;
607 if (LABEL_ALT_ENTRY_P (insn
))
608 make_edge (ENTRY_BLOCK_PTR
, bb
, 0);
611 /* In case we've previously seen an insn that effects a control
612 flow transfer, split the block. */
613 if (flow_transfer_insn
&& inside_basic_block_p (insn
))
615 fallthru
= split_block (bb
, PREV_INSN (insn
));
616 BB_END (bb
) = flow_transfer_insn
;
618 remove_edge (fallthru
);
619 flow_transfer_insn
= NULL_RTX
;
622 if (control_flow_insn_p (insn
))
623 flow_transfer_insn
= insn
;
626 insn
= NEXT_INSN (insn
);
629 /* In case expander replaced normal insn by sequence terminating by
630 return and barrier, or possibly other sequence not behaving like
631 ordinary jump, we need to take care and move basic block boundary. */
632 if (flow_transfer_insn
)
633 BB_END (bb
) = flow_transfer_insn
;
635 /* We've possibly replaced the conditional jump by conditional jump
636 followed by cleanup at fallthru edge, so the outgoing edges may
638 purge_dead_edges (bb
);
641 /* Assume that frequency of basic block B is known. Compute frequencies
642 and probabilities of outgoing edges. */
645 compute_outgoing_frequencies (basic_block b
)
649 if (EDGE_COUNT (b
->succs
) == 2)
651 rtx note
= find_reg_note (BB_END (b
), REG_BR_PROB
, NULL
);
657 probability
= INTVAL (XEXP (note
, 0));
659 e
->probability
= probability
;
660 e
->count
= ((b
->count
* probability
+ REG_BR_PROB_BASE
/ 2)
662 f
= FALLTHRU_EDGE (b
);
663 f
->probability
= REG_BR_PROB_BASE
- probability
;
664 f
->count
= b
->count
- e
->count
;
667 if (EDGE_COUNT (b
->succs
) == 1)
669 e
= EDGE_SUCC (b
, 0);
670 e
->probability
= REG_BR_PROB_BASE
;
675 /* Assume that someone emitted code with control flow instructions to the
676 basic block. Update the data structure. */
679 find_many_sub_basic_blocks (sbitmap blocks
)
681 basic_block bb
, min
, max
;
685 TEST_BIT (blocks
, bb
->index
) ? BLOCK_TO_SPLIT
: BLOCK_ORIGINAL
);
688 if (STATE (bb
) == BLOCK_TO_SPLIT
)
689 find_bb_boundaries (bb
);
692 if (STATE (bb
) != BLOCK_ORIGINAL
)
696 for (; bb
!= EXIT_BLOCK_PTR
; bb
= bb
->next_bb
)
697 if (STATE (bb
) != BLOCK_ORIGINAL
)
700 /* Now re-scan and wire in all edges. This expect simple (conditional)
701 jumps at the end of each new basic blocks. */
702 make_edges (min
, max
, 1);
704 /* Update branch probabilities. Expect only (un)conditional jumps
705 to be created with only the forward edges. */
706 FOR_BB_BETWEEN (bb
, min
, max
->next_bb
, next_bb
)
710 if (STATE (bb
) == BLOCK_ORIGINAL
)
712 if (STATE (bb
) == BLOCK_NEW
)
716 FOR_EACH_EDGE (e
, bb
->preds
)
718 bb
->count
+= e
->count
;
719 bb
->frequency
+= EDGE_FREQUENCY (e
);
724 compute_outgoing_frequencies (bb
);
731 /* Like above but for single basic block only. */
734 find_sub_basic_blocks (basic_block bb
)
736 basic_block min
, max
, b
;
737 basic_block next
= bb
->next_bb
;
740 find_bb_boundaries (bb
);
743 /* Now re-scan and wire in all edges. This expect simple (conditional)
744 jumps at the end of each new basic blocks. */
745 make_edges (min
, max
, 1);
747 /* Update branch probabilities. Expect only (un)conditional jumps
748 to be created with only the forward edges. */
749 FOR_BB_BETWEEN (b
, min
, max
->next_bb
, next_bb
)
757 FOR_EACH_EDGE (e
, b
->preds
)
759 b
->count
+= e
->count
;
760 b
->frequency
+= EDGE_FREQUENCY (e
);
765 compute_outgoing_frequencies (b
);