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, 2007, 2008
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
39 static void make_edges (basic_block
, basic_block
, int);
40 static void make_label_edge (sbitmap
, basic_block
, rtx
, int);
41 static void find_bb_boundaries (basic_block
);
42 static void compute_outgoing_frequencies (basic_block
);
44 /* Return true if insn is something that should be contained inside basic
48 inside_basic_block_p (const_rtx insn
)
50 switch (GET_CODE (insn
))
53 /* Avoid creating of basic block for jumptables. */
54 return (NEXT_INSN (insn
) == 0
55 || !JUMP_P (NEXT_INSN (insn
))
56 || (GET_CODE (PATTERN (NEXT_INSN (insn
))) != ADDR_VEC
57 && GET_CODE (PATTERN (NEXT_INSN (insn
))) != ADDR_DIFF_VEC
));
60 return (GET_CODE (PATTERN (insn
)) != ADDR_VEC
61 && GET_CODE (PATTERN (insn
)) != ADDR_DIFF_VEC
);
76 /* Return true if INSN may cause control flow transfer, so it should be last in
80 control_flow_insn_p (const_rtx insn
)
84 switch (GET_CODE (insn
))
91 /* Jump insn always causes control transfer except for tablejumps. */
92 return (GET_CODE (PATTERN (insn
)) != ADDR_VEC
93 && GET_CODE (PATTERN (insn
)) != ADDR_DIFF_VEC
);
96 /* Noreturn and sibling call instructions terminate the basic blocks
97 (but only if they happen unconditionally). */
98 if ((SIBLING_CALL_P (insn
)
99 || find_reg_note (insn
, REG_NORETURN
, 0))
100 && GET_CODE (PATTERN (insn
)) != COND_EXEC
)
102 /* Call insn may return to the nonlocal goto handler. */
103 return ((nonlocal_goto_handler_labels
104 && (0 == (note
= find_reg_note (insn
, REG_EH_REGION
,
106 || INTVAL (XEXP (note
, 0)) >= 0))
108 || can_throw_internal (insn
));
111 /* Treat trap instructions like noreturn calls (same provision). */
112 if (GET_CODE (PATTERN (insn
)) == TRAP_IF
113 && XEXP (PATTERN (insn
), 0) == const1_rtx
)
116 return (flag_non_call_exceptions
&& can_throw_internal (insn
));
119 /* It is nonsense to reach barrier when looking for the
120 end of basic block, but before dead code is eliminated
130 /* Create an edge between two basic blocks. FLAGS are auxiliary information
131 about the edge that is accumulated between calls. */
133 /* Create an edge from a basic block to a label. */
136 make_label_edge (sbitmap edge_cache
, basic_block src
, rtx label
, int flags
)
138 gcc_assert (LABEL_P (label
));
140 /* If the label was never emitted, this insn is junk, but avoid a
141 crash trying to refer to BLOCK_FOR_INSN (label). This can happen
142 as a result of a syntax error and a diagnostic has already been
145 if (INSN_UID (label
) == 0)
148 cached_make_edge (edge_cache
, src
, BLOCK_FOR_INSN (label
), flags
);
151 /* Create the edges generated by INSN in REGION. */
154 rtl_make_eh_edge (sbitmap edge_cache
, basic_block src
, rtx insn
)
156 int is_call
= CALL_P (insn
) ? EDGE_ABNORMAL_CALL
: 0;
159 handlers
= reachable_handlers (insn
);
161 for (i
= handlers
; i
; i
= XEXP (i
, 1))
162 make_label_edge (edge_cache
, src
, XEXP (i
, 0),
163 EDGE_ABNORMAL
| EDGE_EH
| is_call
);
165 free_INSN_LIST_list (&handlers
);
168 /* States of basic block as seen by find_many_sub_basic_blocks. */
170 /* Basic blocks created via split_block belong to this state.
171 make_edges will examine these basic blocks to see if we need to
172 create edges going out of them. */
175 /* Basic blocks that do not need examining belong to this state.
176 These blocks will be left intact. In particular, make_edges will
177 not create edges going out of these basic blocks. */
180 /* Basic blocks that may need splitting (due to a label appearing in
181 the middle, etc) belong to this state. After splitting them,
182 make_edges will create edges going out of them as needed. */
186 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
187 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
189 /* Used internally by purge_dead_tablejump_edges, ORed into state. */
190 #define BLOCK_USED_BY_TABLEJUMP 32
191 #define FULL_STATE(BB) ((size_t) (BB)->aux)
193 /* Identify the edges going out of basic blocks between MIN and MAX,
194 inclusive, that have their states set to BLOCK_NEW or
197 UPDATE_P should be nonzero if we are updating CFG and zero if we
198 are building CFG from scratch. */
201 make_edges (basic_block min
, basic_block max
, int update_p
)
204 sbitmap edge_cache
= NULL
;
206 /* Heavy use of computed goto in machine-generated code can lead to
207 nearly fully-connected CFGs. In that case we spend a significant
208 amount of time searching the edge lists for duplicates. */
209 if (forced_labels
|| cfun
->cfg
->max_jumptable_ents
> 100)
210 edge_cache
= sbitmap_alloc (last_basic_block
);
212 /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block
213 is always the entry. */
214 if (min
== ENTRY_BLOCK_PTR
->next_bb
)
215 make_edge (ENTRY_BLOCK_PTR
, min
, EDGE_FALLTHRU
);
217 FOR_BB_BETWEEN (bb
, min
, max
->next_bb
, next_bb
)
224 if (STATE (bb
) == BLOCK_ORIGINAL
)
227 /* If we have an edge cache, cache edges going out of BB. */
230 sbitmap_zero (edge_cache
);
233 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
234 if (e
->dest
!= EXIT_BLOCK_PTR
)
235 SET_BIT (edge_cache
, e
->dest
->index
);
239 if (LABEL_P (BB_HEAD (bb
))
240 && LABEL_ALT_ENTRY_P (BB_HEAD (bb
)))
241 cached_make_edge (NULL
, ENTRY_BLOCK_PTR
, bb
, 0);
243 /* Examine the last instruction of the block, and discover the
244 ways we can leave the block. */
247 code
= GET_CODE (insn
);
250 if (code
== JUMP_INSN
)
254 /* Recognize exception handling placeholders. */
255 if (GET_CODE (PATTERN (insn
)) == RESX
)
256 rtl_make_eh_edge (edge_cache
, bb
, insn
);
258 /* Recognize a non-local goto as a branch outside the
260 else if (find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
263 /* Recognize a tablejump and do the right thing. */
264 else if (tablejump_p (insn
, NULL
, &tmp
))
269 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
270 vec
= XVEC (PATTERN (tmp
), 0);
272 vec
= XVEC (PATTERN (tmp
), 1);
274 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
275 make_label_edge (edge_cache
, bb
,
276 XEXP (RTVEC_ELT (vec
, j
), 0), 0);
278 /* Some targets (eg, ARM) emit a conditional jump that also
279 contains the out-of-range target. Scan for these and
280 add an edge if necessary. */
281 if ((tmp
= single_set (insn
)) != NULL
282 && SET_DEST (tmp
) == pc_rtx
283 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
284 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
)
285 make_label_edge (edge_cache
, bb
,
286 XEXP (XEXP (SET_SRC (tmp
), 2), 0), 0);
289 /* If this is a computed jump, then mark it as reaching
290 everything on the forced_labels list. */
291 else if (computed_jump_p (insn
))
293 for (x
= forced_labels
; x
; x
= XEXP (x
, 1))
294 make_label_edge (edge_cache
, bb
, XEXP (x
, 0), EDGE_ABNORMAL
);
297 /* Returns create an exit out. */
298 else if (returnjump_p (insn
))
299 cached_make_edge (edge_cache
, bb
, EXIT_BLOCK_PTR
, 0);
301 /* Otherwise, we have a plain conditional or unconditional jump. */
304 gcc_assert (JUMP_LABEL (insn
));
305 make_label_edge (edge_cache
, bb
, JUMP_LABEL (insn
), 0);
309 /* If this is a sibling call insn, then this is in effect a combined call
310 and return, and so we need an edge to the exit block. No need to
311 worry about EH edges, since we wouldn't have created the sibling call
312 in the first place. */
313 if (code
== CALL_INSN
&& SIBLING_CALL_P (insn
))
314 cached_make_edge (edge_cache
, bb
, EXIT_BLOCK_PTR
,
315 EDGE_SIBCALL
| EDGE_ABNORMAL
);
317 /* If this is a CALL_INSN, then mark it as reaching the active EH
318 handler for this CALL_INSN. If we're handling non-call
319 exceptions then any insn can reach any of the active handlers.
320 Also mark the CALL_INSN as reaching any nonlocal goto handler. */
321 else if (code
== CALL_INSN
|| flag_non_call_exceptions
)
323 /* Add any appropriate EH edges. */
324 rtl_make_eh_edge (edge_cache
, bb
, insn
);
326 if (code
== CALL_INSN
&& nonlocal_goto_handler_labels
)
328 /* ??? This could be made smarter: in some cases it's possible
329 to tell that certain calls will not do a nonlocal goto.
330 For example, if the nested functions that do the nonlocal
331 gotos do not have their addresses taken, then only calls to
332 those functions or to other nested functions that use them
333 could possibly do nonlocal gotos. */
335 /* We do know that a REG_EH_REGION note with a value less
336 than 0 is guaranteed not to perform a non-local goto. */
337 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
339 if (!note
|| INTVAL (XEXP (note
, 0)) >= 0)
340 for (x
= nonlocal_goto_handler_labels
; x
; x
= XEXP (x
, 1))
341 make_label_edge (edge_cache
, bb
, XEXP (x
, 0),
342 EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
);
346 /* Find out if we can drop through to the next block. */
347 insn
= NEXT_INSN (insn
);
348 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
349 if (e
&& e
->flags
& EDGE_FALLTHRU
)
354 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
)
355 insn
= NEXT_INSN (insn
);
358 cached_make_edge (edge_cache
, bb
, EXIT_BLOCK_PTR
, EDGE_FALLTHRU
);
359 else if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
361 if (insn
== BB_HEAD (bb
->next_bb
))
362 cached_make_edge (edge_cache
, bb
, bb
->next_bb
, EDGE_FALLTHRU
);
367 sbitmap_vector_free (edge_cache
);
371 mark_tablejump_edge (rtx label
)
375 gcc_assert (LABEL_P (label
));
376 /* See comment in make_label_edge. */
377 if (INSN_UID (label
) == 0)
379 bb
= BLOCK_FOR_INSN (label
);
380 SET_STATE (bb
, FULL_STATE (bb
) | BLOCK_USED_BY_TABLEJUMP
);
384 purge_dead_tablejump_edges (basic_block bb
, rtx table
)
386 rtx insn
= BB_END (bb
), tmp
;
392 if (GET_CODE (PATTERN (table
)) == ADDR_VEC
)
393 vec
= XVEC (PATTERN (table
), 0);
395 vec
= XVEC (PATTERN (table
), 1);
397 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
398 mark_tablejump_edge (XEXP (RTVEC_ELT (vec
, j
), 0));
400 /* Some targets (eg, ARM) emit a conditional jump that also
401 contains the out-of-range target. Scan for these and
402 add an edge if necessary. */
403 if ((tmp
= single_set (insn
)) != NULL
404 && SET_DEST (tmp
) == pc_rtx
405 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
406 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
)
407 mark_tablejump_edge (XEXP (XEXP (SET_SRC (tmp
), 2), 0));
409 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
411 if (FULL_STATE (e
->dest
) & BLOCK_USED_BY_TABLEJUMP
)
412 SET_STATE (e
->dest
, FULL_STATE (e
->dest
)
413 & ~(size_t) BLOCK_USED_BY_TABLEJUMP
);
414 else if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
)))
423 /* Scan basic block BB for possible BB boundaries inside the block
424 and create new basic blocks in the progress. */
427 find_bb_boundaries (basic_block bb
)
429 basic_block orig_bb
= bb
;
430 rtx insn
= BB_HEAD (bb
);
431 rtx end
= BB_END (bb
), x
;
433 rtx flow_transfer_insn
= NULL_RTX
;
434 edge fallthru
= NULL
;
436 if (insn
== BB_END (bb
))
440 insn
= NEXT_INSN (insn
);
442 /* Scan insn chain and try to find new basic block boundaries. */
445 enum rtx_code code
= GET_CODE (insn
);
447 /* On code label, split current basic block. */
448 if (code
== CODE_LABEL
)
450 fallthru
= split_block (bb
, PREV_INSN (insn
));
451 if (flow_transfer_insn
)
453 BB_END (bb
) = flow_transfer_insn
;
455 /* Clean up the bb field for the insns between the blocks. */
456 for (x
= NEXT_INSN (flow_transfer_insn
);
457 x
!= BB_HEAD (fallthru
->dest
);
460 set_block_for_insn (x
, NULL
);
464 remove_edge (fallthru
);
465 flow_transfer_insn
= NULL_RTX
;
466 if (LABEL_ALT_ENTRY_P (insn
))
467 make_edge (ENTRY_BLOCK_PTR
, bb
, 0);
470 /* In case we've previously seen an insn that effects a control
471 flow transfer, split the block. */
472 if (flow_transfer_insn
&& inside_basic_block_p (insn
))
474 fallthru
= split_block (bb
, PREV_INSN (insn
));
475 BB_END (bb
) = flow_transfer_insn
;
477 /* Clean up the bb field for the insns between the blocks. */
478 for (x
= NEXT_INSN (flow_transfer_insn
);
479 x
!= BB_HEAD (fallthru
->dest
);
482 set_block_for_insn (x
, NULL
);
485 remove_edge (fallthru
);
486 flow_transfer_insn
= NULL_RTX
;
489 if (control_flow_insn_p (insn
))
490 flow_transfer_insn
= insn
;
493 insn
= NEXT_INSN (insn
);
496 /* In case expander replaced normal insn by sequence terminating by
497 return and barrier, or possibly other sequence not behaving like
498 ordinary jump, we need to take care and move basic block boundary. */
499 if (flow_transfer_insn
)
501 BB_END (bb
) = flow_transfer_insn
;
503 /* Clean up the bb field for the insns that do not belong to BB. */
504 x
= flow_transfer_insn
;
509 set_block_for_insn (x
, NULL
);
513 /* We've possibly replaced the conditional jump by conditional jump
514 followed by cleanup at fallthru edge, so the outgoing edges may
516 purge_dead_edges (bb
);
518 /* purge_dead_edges doesn't handle tablejump's, but if we have split the
519 basic block, we might need to kill some edges. */
520 if (bb
!= orig_bb
&& tablejump_p (BB_END (bb
), NULL
, &table
))
521 purge_dead_tablejump_edges (bb
, table
);
524 /* Assume that frequency of basic block B is known. Compute frequencies
525 and probabilities of outgoing edges. */
528 compute_outgoing_frequencies (basic_block b
)
533 if (EDGE_COUNT (b
->succs
) == 2)
535 rtx note
= find_reg_note (BB_END (b
), REG_BR_PROB
, NULL
);
540 probability
= INTVAL (XEXP (note
, 0));
542 e
->probability
= probability
;
543 e
->count
= ((b
->count
* probability
+ REG_BR_PROB_BASE
/ 2)
545 f
= FALLTHRU_EDGE (b
);
546 f
->probability
= REG_BR_PROB_BASE
- probability
;
547 f
->count
= b
->count
- e
->count
;
552 if (single_succ_p (b
))
554 e
= single_succ_edge (b
);
555 e
->probability
= REG_BR_PROB_BASE
;
559 guess_outgoing_edge_probabilities (b
);
561 FOR_EACH_EDGE (e
, ei
, b
->succs
)
562 e
->count
= ((b
->count
* e
->probability
+ REG_BR_PROB_BASE
/ 2)
566 /* Assume that some pass has inserted labels or control flow
567 instructions within a basic block. Split basic blocks as needed
571 find_many_sub_basic_blocks (sbitmap blocks
)
573 basic_block bb
, min
, max
;
577 TEST_BIT (blocks
, bb
->index
) ? BLOCK_TO_SPLIT
: BLOCK_ORIGINAL
);
580 if (STATE (bb
) == BLOCK_TO_SPLIT
)
581 find_bb_boundaries (bb
);
584 if (STATE (bb
) != BLOCK_ORIGINAL
)
588 for (; bb
!= EXIT_BLOCK_PTR
; bb
= bb
->next_bb
)
589 if (STATE (bb
) != BLOCK_ORIGINAL
)
592 /* Now re-scan and wire in all edges. This expect simple (conditional)
593 jumps at the end of each new basic blocks. */
594 make_edges (min
, max
, 1);
596 /* Update branch probabilities. Expect only (un)conditional jumps
597 to be created with only the forward edges. */
598 if (profile_status
!= PROFILE_ABSENT
)
599 FOR_BB_BETWEEN (bb
, min
, max
->next_bb
, next_bb
)
604 if (STATE (bb
) == BLOCK_ORIGINAL
)
606 if (STATE (bb
) == BLOCK_NEW
)
610 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
612 bb
->count
+= e
->count
;
613 bb
->frequency
+= EDGE_FREQUENCY (e
);
617 compute_outgoing_frequencies (bb
);