]>
Commit | Line | Data |
---|---|---|
402209ff JH |
1 | /* Control flow graph building code for GNU compiler. |
2 | Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, | |
66647d44 JJ |
3 | 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008 |
4 | Free Software Foundation, Inc. | |
402209ff JH |
5 | |
6 | This file is part of GCC. | |
7 | ||
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 | |
9dcd6f09 | 10 | Software Foundation; either version 3, or (at your option) any later |
402209ff JH |
11 | version. |
12 | ||
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 | |
16 | for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ | |
402209ff | 21 | |
402209ff JH |
22 | \f |
23 | #include "config.h" | |
24 | #include "system.h" | |
4977bab6 ZW |
25 | #include "coretypes.h" |
26 | #include "tm.h" | |
402209ff JH |
27 | #include "tree.h" |
28 | #include "rtl.h" | |
29 | #include "hard-reg-set.h" | |
30 | #include "basic-block.h" | |
31 | #include "regs.h" | |
32 | #include "flags.h" | |
33 | #include "output.h" | |
34 | #include "function.h" | |
35 | #include "except.h" | |
1d65f45c | 36 | #include "expr.h" |
402209ff JH |
37 | #include "toplev.h" |
38 | #include "timevar.h" | |
4891442b | 39 | |
2df6cea5 | 40 | static void make_edges (basic_block, basic_block, int); |
a6ee1a15 | 41 | static void make_label_edge (sbitmap, basic_block, rtx, int); |
d329e058 AJ |
42 | static void find_bb_boundaries (basic_block); |
43 | static void compute_outgoing_frequencies (basic_block); | |
4891442b | 44 | \f |
9cd56be1 JH |
45 | /* Return true if insn is something that should be contained inside basic |
46 | block. */ | |
47 | ||
8f62128d | 48 | bool |
ed7a4b4b | 49 | inside_basic_block_p (const_rtx insn) |
9cd56be1 JH |
50 | { |
51 | switch (GET_CODE (insn)) | |
52 | { | |
53 | case CODE_LABEL: | |
54 | /* Avoid creating of basic block for jumptables. */ | |
4891442b | 55 | return (NEXT_INSN (insn) == 0 |
4b4bf941 | 56 | || !JUMP_P (NEXT_INSN (insn)) |
4891442b RK |
57 | || (GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_VEC |
58 | && GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_DIFF_VEC)); | |
9cd56be1 JH |
59 | |
60 | case JUMP_INSN: | |
4891442b RK |
61 | return (GET_CODE (PATTERN (insn)) != ADDR_VEC |
62 | && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC); | |
9cd56be1 JH |
63 | |
64 | case CALL_INSN: | |
65 | case INSN: | |
b5b8b0ac | 66 | case DEBUG_INSN: |
9cd56be1 JH |
67 | return true; |
68 | ||
69 | case BARRIER: | |
70 | case NOTE: | |
71 | return false; | |
72 | ||
73 | default: | |
341c100f | 74 | gcc_unreachable (); |
9cd56be1 JH |
75 | } |
76 | } | |
77 | ||
4891442b RK |
78 | /* Return true if INSN may cause control flow transfer, so it should be last in |
79 | the basic block. */ | |
9cd56be1 | 80 | |
4a69cf79 | 81 | bool |
ed7a4b4b | 82 | control_flow_insn_p (const_rtx insn) |
9cd56be1 | 83 | { |
9cd56be1 JH |
84 | switch (GET_CODE (insn)) |
85 | { | |
f87c27b4 KH |
86 | case NOTE: |
87 | case CODE_LABEL: | |
b5b8b0ac | 88 | case DEBUG_INSN: |
f87c27b4 KH |
89 | return false; |
90 | ||
91 | case JUMP_INSN: | |
92 | /* Jump insn always causes control transfer except for tablejumps. */ | |
93 | return (GET_CODE (PATTERN (insn)) != ADDR_VEC | |
94 | && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC); | |
95 | ||
96 | case CALL_INSN: | |
baf8706c JH |
97 | /* Noreturn and sibling call instructions terminate the basic blocks |
98 | (but only if they happen unconditionally). */ | |
99 | if ((SIBLING_CALL_P (insn) | |
100 | || find_reg_note (insn, REG_NORETURN, 0)) | |
101 | && GET_CODE (PATTERN (insn)) != COND_EXEC) | |
102 | return true; | |
1d65f45c | 103 | |
f87c27b4 | 104 | /* Call insn may return to the nonlocal goto handler. */ |
1d65f45c RH |
105 | if (can_nonlocal_goto (insn)) |
106 | return true; | |
107 | break; | |
f87c27b4 KH |
108 | |
109 | case INSN: | |
d47a8b83 EB |
110 | /* Treat trap instructions like noreturn calls (same provision). */ |
111 | if (GET_CODE (PATTERN (insn)) == TRAP_IF | |
112 | && XEXP (PATTERN (insn), 0) == const1_rtx) | |
113 | return true; | |
1d65f45c RH |
114 | if (!flag_non_call_exceptions) |
115 | return false; | |
116 | break; | |
f87c27b4 KH |
117 | |
118 | case BARRIER: | |
a98ebe2e | 119 | /* It is nonsense to reach barrier when looking for the |
c22cacf3 MS |
120 | end of basic block, but before dead code is eliminated |
121 | this may happen. */ | |
f87c27b4 KH |
122 | return false; |
123 | ||
124 | default: | |
341c100f | 125 | gcc_unreachable (); |
9cd56be1 | 126 | } |
1d65f45c RH |
127 | |
128 | return can_throw_internal (insn); | |
9cd56be1 | 129 | } |
402209ff | 130 | |
402209ff JH |
131 | \f |
132 | /* Create an edge between two basic blocks. FLAGS are auxiliary information | |
133 | about the edge that is accumulated between calls. */ | |
134 | ||
135 | /* Create an edge from a basic block to a label. */ | |
136 | ||
137 | static void | |
a6ee1a15 | 138 | make_label_edge (sbitmap edge_cache, basic_block src, rtx label, int flags) |
402209ff | 139 | { |
341c100f | 140 | gcc_assert (LABEL_P (label)); |
402209ff JH |
141 | |
142 | /* If the label was never emitted, this insn is junk, but avoid a | |
143 | crash trying to refer to BLOCK_FOR_INSN (label). This can happen | |
144 | as a result of a syntax error and a diagnostic has already been | |
145 | printed. */ | |
146 | ||
147 | if (INSN_UID (label) == 0) | |
148 | return; | |
149 | ||
7ded4467 | 150 | cached_make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags); |
402209ff JH |
151 | } |
152 | ||
153 | /* Create the edges generated by INSN in REGION. */ | |
154 | ||
12c3874e | 155 | void |
a6ee1a15 | 156 | rtl_make_eh_edge (sbitmap edge_cache, basic_block src, rtx insn) |
402209ff | 157 | { |
1d65f45c | 158 | eh_landing_pad lp = get_eh_landing_pad_from_rtx (insn); |
402209ff | 159 | |
1d65f45c RH |
160 | if (lp) |
161 | { | |
162 | rtx label = lp->landing_pad; | |
402209ff | 163 | |
1d65f45c RH |
164 | /* During initial rtl generation, use the post_landing_pad. */ |
165 | if (label == NULL) | |
166 | { | |
167 | gcc_assert (lp->post_landing_pad); | |
168 | label = label_rtx (lp->post_landing_pad); | |
169 | } | |
402209ff | 170 | |
1d65f45c RH |
171 | make_label_edge (edge_cache, src, label, |
172 | EDGE_ABNORMAL | EDGE_EH | |
173 | | (CALL_P (insn) ? EDGE_ABNORMAL_CALL : 0)); | |
174 | } | |
402209ff | 175 | } |
4891442b | 176 | |
55b18c19 KH |
177 | /* States of basic block as seen by find_many_sub_basic_blocks. */ |
178 | enum state { | |
179 | /* Basic blocks created via split_block belong to this state. | |
180 | make_edges will examine these basic blocks to see if we need to | |
181 | create edges going out of them. */ | |
182 | BLOCK_NEW = 0, | |
183 | ||
184 | /* Basic blocks that do not need examining belong to this state. | |
185 | These blocks will be left intact. In particular, make_edges will | |
186 | not create edges going out of these basic blocks. */ | |
187 | BLOCK_ORIGINAL, | |
188 | ||
189 | /* Basic blocks that may need splitting (due to a label appearing in | |
190 | the middle, etc) belong to this state. After splitting them, | |
0fa2e4df | 191 | make_edges will create edges going out of them as needed. */ |
55b18c19 KH |
192 | BLOCK_TO_SPLIT |
193 | }; | |
5e91f7a3 KH |
194 | |
195 | #define STATE(BB) (enum state) ((size_t) (BB)->aux) | |
196 | #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE)) | |
197 | ||
198 | /* Used internally by purge_dead_tablejump_edges, ORed into state. */ | |
199 | #define BLOCK_USED_BY_TABLEJUMP 32 | |
200 | #define FULL_STATE(BB) ((size_t) (BB)->aux) | |
201 | ||
55b18c19 KH |
202 | /* Identify the edges going out of basic blocks between MIN and MAX, |
203 | inclusive, that have their states set to BLOCK_NEW or | |
204 | BLOCK_TO_SPLIT. | |
402209ff | 205 | |
55b18c19 KH |
206 | UPDATE_P should be nonzero if we are updating CFG and zero if we |
207 | are building CFG from scratch. */ | |
402209ff JH |
208 | |
209 | static void | |
2df6cea5 | 210 | make_edges (basic_block min, basic_block max, int update_p) |
402209ff | 211 | { |
e0082a72 | 212 | basic_block bb; |
a6ee1a15 | 213 | sbitmap edge_cache = NULL; |
402209ff | 214 | |
402209ff JH |
215 | /* Heavy use of computed goto in machine-generated code can lead to |
216 | nearly fully-connected CFGs. In that case we spend a significant | |
217 | amount of time searching the edge lists for duplicates. */ | |
cb91fab0 | 218 | if (forced_labels || cfun->cfg->max_jumptable_ents > 100) |
a6ee1a15 | 219 | edge_cache = sbitmap_alloc (last_basic_block); |
402209ff | 220 | |
e0082a72 ZD |
221 | /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block |
222 | is always the entry. */ | |
f6366fc7 | 223 | if (min == ENTRY_BLOCK_PTR->next_bb) |
a6ee1a15 | 224 | make_edge (ENTRY_BLOCK_PTR, min, EDGE_FALLTHRU); |
402209ff | 225 | |
e0082a72 | 226 | FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb) |
402209ff | 227 | { |
402209ff JH |
228 | rtx insn, x; |
229 | enum rtx_code code; | |
623a66fa | 230 | edge e; |
a6ee1a15 | 231 | edge_iterator ei; |
402209ff | 232 | |
5e91f7a3 KH |
233 | if (STATE (bb) == BLOCK_ORIGINAL) |
234 | continue; | |
235 | ||
a6ee1a15 KH |
236 | /* If we have an edge cache, cache edges going out of BB. */ |
237 | if (edge_cache) | |
238 | { | |
239 | sbitmap_zero (edge_cache); | |
240 | if (update_p) | |
241 | { | |
242 | FOR_EACH_EDGE (e, ei, bb->succs) | |
243 | if (e->dest != EXIT_BLOCK_PTR) | |
244 | SET_BIT (edge_cache, e->dest->index); | |
245 | } | |
246 | } | |
247 | ||
4b4bf941 | 248 | if (LABEL_P (BB_HEAD (bb)) |
a813c111 | 249 | && LABEL_ALT_ENTRY_P (BB_HEAD (bb))) |
7ded4467 | 250 | cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0); |
402209ff JH |
251 | |
252 | /* Examine the last instruction of the block, and discover the | |
253 | ways we can leave the block. */ | |
254 | ||
a813c111 | 255 | insn = BB_END (bb); |
402209ff JH |
256 | code = GET_CODE (insn); |
257 | ||
258 | /* A branch. */ | |
259 | if (code == JUMP_INSN) | |
260 | { | |
261 | rtx tmp; | |
262 | ||
402209ff JH |
263 | /* Recognize a non-local goto as a branch outside the |
264 | current function. */ | |
1d65f45c | 265 | if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX)) |
402209ff JH |
266 | ; |
267 | ||
e1233a7d RH |
268 | /* Recognize a tablejump and do the right thing. */ |
269 | else if (tablejump_p (insn, NULL, &tmp)) | |
402209ff JH |
270 | { |
271 | rtvec vec; | |
272 | int j; | |
273 | ||
274 | if (GET_CODE (PATTERN (tmp)) == ADDR_VEC) | |
275 | vec = XVEC (PATTERN (tmp), 0); | |
276 | else | |
277 | vec = XVEC (PATTERN (tmp), 1); | |
278 | ||
279 | for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) | |
280 | make_label_edge (edge_cache, bb, | |
281 | XEXP (RTVEC_ELT (vec, j), 0), 0); | |
282 | ||
283 | /* Some targets (eg, ARM) emit a conditional jump that also | |
284 | contains the out-of-range target. Scan for these and | |
285 | add an edge if necessary. */ | |
286 | if ((tmp = single_set (insn)) != NULL | |
287 | && SET_DEST (tmp) == pc_rtx | |
288 | && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE | |
289 | && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF) | |
290 | make_label_edge (edge_cache, bb, | |
291 | XEXP (XEXP (SET_SRC (tmp), 2), 0), 0); | |
402209ff JH |
292 | } |
293 | ||
294 | /* If this is a computed jump, then mark it as reaching | |
2df6cea5 | 295 | everything on the forced_labels list. */ |
402209ff JH |
296 | else if (computed_jump_p (insn)) |
297 | { | |
402209ff JH |
298 | for (x = forced_labels; x; x = XEXP (x, 1)) |
299 | make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL); | |
300 | } | |
301 | ||
302 | /* Returns create an exit out. */ | |
303 | else if (returnjump_p (insn)) | |
7ded4467 | 304 | cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0); |
402209ff | 305 | |
1c384bf1 RH |
306 | /* Recognize asm goto and do the right thing. */ |
307 | else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL) | |
308 | { | |
309 | int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp); | |
310 | for (i = 0; i < n; ++i) | |
311 | make_label_edge (edge_cache, bb, | |
312 | XEXP (ASM_OPERANDS_LABEL (tmp, i), 0), 0); | |
313 | } | |
314 | ||
402209ff JH |
315 | /* Otherwise, we have a plain conditional or unconditional jump. */ |
316 | else | |
317 | { | |
341c100f | 318 | gcc_assert (JUMP_LABEL (insn)); |
402209ff JH |
319 | make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0); |
320 | } | |
321 | } | |
322 | ||
4891442b RK |
323 | /* If this is a sibling call insn, then this is in effect a combined call |
324 | and return, and so we need an edge to the exit block. No need to | |
325 | worry about EH edges, since we wouldn't have created the sibling call | |
326 | in the first place. */ | |
402209ff | 327 | if (code == CALL_INSN && SIBLING_CALL_P (insn)) |
792bb204 RH |
328 | cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, |
329 | EDGE_SIBCALL | EDGE_ABNORMAL); | |
402209ff JH |
330 | |
331 | /* If this is a CALL_INSN, then mark it as reaching the active EH | |
332 | handler for this CALL_INSN. If we're handling non-call | |
333 | exceptions then any insn can reach any of the active handlers. | |
402209ff | 334 | Also mark the CALL_INSN as reaching any nonlocal goto handler. */ |
402209ff JH |
335 | else if (code == CALL_INSN || flag_non_call_exceptions) |
336 | { | |
337 | /* Add any appropriate EH edges. */ | |
6de9cd9a | 338 | rtl_make_eh_edge (edge_cache, bb, insn); |
402209ff JH |
339 | |
340 | if (code == CALL_INSN && nonlocal_goto_handler_labels) | |
341 | { | |
342 | /* ??? This could be made smarter: in some cases it's possible | |
343 | to tell that certain calls will not do a nonlocal goto. | |
402209ff JH |
344 | For example, if the nested functions that do the nonlocal |
345 | gotos do not have their addresses taken, then only calls to | |
346 | those functions or to other nested functions that use them | |
347 | could possibly do nonlocal gotos. */ | |
1d65f45c | 348 | if (can_nonlocal_goto (insn)) |
402209ff JH |
349 | for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1)) |
350 | make_label_edge (edge_cache, bb, XEXP (x, 0), | |
351 | EDGE_ABNORMAL | EDGE_ABNORMAL_CALL); | |
352 | } | |
353 | } | |
354 | ||
355 | /* Find out if we can drop through to the next block. */ | |
26f74aa3 | 356 | insn = NEXT_INSN (insn); |
9ff3d2de JL |
357 | e = find_edge (bb, EXIT_BLOCK_PTR); |
358 | if (e && e->flags & EDGE_FALLTHRU) | |
359 | insn = NULL; | |
360 | ||
26f74aa3 | 361 | while (insn |
4b4bf941 | 362 | && NOTE_P (insn) |
a38e7aa5 | 363 | && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK) |
26f74aa3 JH |
364 | insn = NEXT_INSN (insn); |
365 | ||
6be85b25 | 366 | if (!insn) |
7ded4467 | 367 | cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU); |
f6366fc7 | 368 | else if (bb->next_bb != EXIT_BLOCK_PTR) |
402209ff | 369 | { |
6be85b25 | 370 | if (insn == BB_HEAD (bb->next_bb)) |
f6366fc7 | 371 | cached_make_edge (edge_cache, bb, bb->next_bb, EDGE_FALLTHRU); |
402209ff JH |
372 | } |
373 | } | |
374 | ||
375 | if (edge_cache) | |
376 | sbitmap_vector_free (edge_cache); | |
377 | } | |
378 | \f | |
0210ae14 JJ |
379 | static void |
380 | mark_tablejump_edge (rtx label) | |
381 | { | |
382 | basic_block bb; | |
383 | ||
384 | gcc_assert (LABEL_P (label)); | |
385 | /* See comment in make_label_edge. */ | |
386 | if (INSN_UID (label) == 0) | |
387 | return; | |
388 | bb = BLOCK_FOR_INSN (label); | |
389 | SET_STATE (bb, FULL_STATE (bb) | BLOCK_USED_BY_TABLEJUMP); | |
390 | } | |
391 | ||
392 | static void | |
393 | purge_dead_tablejump_edges (basic_block bb, rtx table) | |
394 | { | |
395 | rtx insn = BB_END (bb), tmp; | |
396 | rtvec vec; | |
397 | int j; | |
398 | edge_iterator ei; | |
399 | edge e; | |
400 | ||
401 | if (GET_CODE (PATTERN (table)) == ADDR_VEC) | |
402 | vec = XVEC (PATTERN (table), 0); | |
403 | else | |
404 | vec = XVEC (PATTERN (table), 1); | |
405 | ||
406 | for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) | |
407 | mark_tablejump_edge (XEXP (RTVEC_ELT (vec, j), 0)); | |
408 | ||
409 | /* Some targets (eg, ARM) emit a conditional jump that also | |
410 | contains the out-of-range target. Scan for these and | |
411 | add an edge if necessary. */ | |
412 | if ((tmp = single_set (insn)) != NULL | |
413 | && SET_DEST (tmp) == pc_rtx | |
414 | && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE | |
415 | && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF) | |
416 | mark_tablejump_edge (XEXP (XEXP (SET_SRC (tmp), 2), 0)); | |
417 | ||
418 | for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) | |
419 | { | |
420 | if (FULL_STATE (e->dest) & BLOCK_USED_BY_TABLEJUMP) | |
c22cacf3 MS |
421 | SET_STATE (e->dest, FULL_STATE (e->dest) |
422 | & ~(size_t) BLOCK_USED_BY_TABLEJUMP); | |
0210ae14 | 423 | else if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH))) |
c22cacf3 MS |
424 | { |
425 | remove_edge (e); | |
426 | continue; | |
427 | } | |
0210ae14 JJ |
428 | ei_next (&ei); |
429 | } | |
430 | } | |
431 | ||
b932f770 JH |
432 | /* Scan basic block BB for possible BB boundaries inside the block |
433 | and create new basic blocks in the progress. */ | |
434 | ||
435 | static void | |
d329e058 | 436 | find_bb_boundaries (basic_block bb) |
402209ff | 437 | { |
0210ae14 | 438 | basic_block orig_bb = bb; |
a813c111 | 439 | rtx insn = BB_HEAD (bb); |
a7b87f73 | 440 | rtx end = BB_END (bb), x; |
0210ae14 | 441 | rtx table; |
f068df3f RH |
442 | rtx flow_transfer_insn = NULL_RTX; |
443 | edge fallthru = NULL; | |
402209ff | 444 | |
a813c111 | 445 | if (insn == BB_END (bb)) |
402209ff JH |
446 | return; |
447 | ||
4b4bf941 | 448 | if (LABEL_P (insn)) |
402209ff JH |
449 | insn = NEXT_INSN (insn); |
450 | ||
451 | /* Scan insn chain and try to find new basic block boundaries. */ | |
452 | while (1) | |
453 | { | |
454 | enum rtx_code code = GET_CODE (insn); | |
f068df3f | 455 | |
1d65f45c RH |
456 | /* In case we've previously seen an insn that effects a control |
457 | flow transfer, split the block. */ | |
458 | if ((flow_transfer_insn || code == CODE_LABEL) | |
459 | && inside_basic_block_p (insn)) | |
402209ff | 460 | { |
f068df3f RH |
461 | fallthru = split_block (bb, PREV_INSN (insn)); |
462 | if (flow_transfer_insn) | |
a7b87f73 ZD |
463 | { |
464 | BB_END (bb) = flow_transfer_insn; | |
465 | ||
466 | /* Clean up the bb field for the insns between the blocks. */ | |
467 | for (x = NEXT_INSN (flow_transfer_insn); | |
468 | x != BB_HEAD (fallthru->dest); | |
469 | x = NEXT_INSN (x)) | |
470 | if (!BARRIER_P (x)) | |
471 | set_block_for_insn (x, NULL); | |
472 | } | |
4891442b | 473 | |
f068df3f RH |
474 | bb = fallthru->dest; |
475 | remove_edge (fallthru); | |
476 | flow_transfer_insn = NULL_RTX; | |
1d65f45c | 477 | if (code == CODE_LABEL && LABEL_ALT_ENTRY_P (insn)) |
7ded4467 | 478 | make_edge (ENTRY_BLOCK_PTR, bb, 0); |
402209ff | 479 | } |
79876307 RH |
480 | else if (code == BARRIER) |
481 | { | |
482 | /* __builtin_unreachable () may cause a barrier to be emitted in | |
483 | the middle of a BB. We need to split it in the same manner as | |
484 | if the barrier were preceded by a control_flow_insn_p insn. */ | |
485 | if (!flow_transfer_insn) | |
486 | flow_transfer_insn = prev_nonnote_insn_bb (insn); | |
487 | } | |
79876307 | 488 | |
27b4689f RH |
489 | if (control_flow_insn_p (insn)) |
490 | flow_transfer_insn = insn; | |
402209ff JH |
491 | if (insn == end) |
492 | break; | |
493 | insn = NEXT_INSN (insn); | |
494 | } | |
495 | ||
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. */ | |
f068df3f | 499 | if (flow_transfer_insn) |
a7b87f73 ZD |
500 | { |
501 | BB_END (bb) = flow_transfer_insn; | |
502 | ||
503 | /* Clean up the bb field for the insns that do not belong to BB. */ | |
504 | x = flow_transfer_insn; | |
505 | while (x != end) | |
506 | { | |
507 | x = NEXT_INSN (x); | |
508 | if (!BARRIER_P (x)) | |
509 | set_block_for_insn (x, NULL); | |
510 | } | |
511 | } | |
402209ff JH |
512 | |
513 | /* We've possibly replaced the conditional jump by conditional jump | |
514 | followed by cleanup at fallthru edge, so the outgoing edges may | |
515 | be dead. */ | |
516 | purge_dead_edges (bb); | |
0210ae14 JJ |
517 | |
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); | |
b932f770 JH |
522 | } |
523 | ||
524 | /* Assume that frequency of basic block B is known. Compute frequencies | |
525 | and probabilities of outgoing edges. */ | |
526 | ||
527 | static void | |
d329e058 | 528 | compute_outgoing_frequencies (basic_block b) |
b932f770 JH |
529 | { |
530 | edge e, f; | |
628f6a4e | 531 | edge_iterator ei; |
4891442b | 532 | |
628f6a4e | 533 | if (EDGE_COUNT (b->succs) == 2) |
b932f770 | 534 | { |
a813c111 | 535 | rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL); |
b932f770 JH |
536 | int probability; |
537 | ||
87022a6b JH |
538 | if (note) |
539 | { | |
540 | probability = INTVAL (XEXP (note, 0)); | |
541 | e = BRANCH_EDGE (b); | |
542 | e->probability = probability; | |
543 | e->count = ((b->count * probability + REG_BR_PROB_BASE / 2) | |
544 | / REG_BR_PROB_BASE); | |
545 | f = FALLTHRU_EDGE (b); | |
546 | f->probability = REG_BR_PROB_BASE - probability; | |
547 | f->count = b->count - e->count; | |
548 | return; | |
549 | } | |
b932f770 | 550 | } |
4891442b | 551 | |
c5cbcccf | 552 | if (single_succ_p (b)) |
b932f770 | 553 | { |
c5cbcccf | 554 | e = single_succ_edge (b); |
b932f770 JH |
555 | e->probability = REG_BR_PROB_BASE; |
556 | e->count = b->count; | |
87022a6b | 557 | return; |
b932f770 | 558 | } |
87022a6b JH |
559 | guess_outgoing_edge_probabilities (b); |
560 | if (b->count) | |
628f6a4e | 561 | FOR_EACH_EDGE (e, ei, b->succs) |
87022a6b JH |
562 | e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2) |
563 | / REG_BR_PROB_BASE); | |
b932f770 JH |
564 | } |
565 | ||
55b18c19 KH |
566 | /* Assume that some pass has inserted labels or control flow |
567 | instructions within a basic block. Split basic blocks as needed | |
568 | and create edges. */ | |
b932f770 JH |
569 | |
570 | void | |
d329e058 | 571 | find_many_sub_basic_blocks (sbitmap blocks) |
b932f770 | 572 | { |
e0082a72 | 573 | basic_block bb, min, max; |
b932f770 | 574 | |
e0082a72 ZD |
575 | FOR_EACH_BB (bb) |
576 | SET_STATE (bb, | |
577 | TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL); | |
b932f770 | 578 | |
e0082a72 ZD |
579 | FOR_EACH_BB (bb) |
580 | if (STATE (bb) == BLOCK_TO_SPLIT) | |
581 | find_bb_boundaries (bb); | |
b932f770 | 582 | |
e0082a72 ZD |
583 | FOR_EACH_BB (bb) |
584 | if (STATE (bb) != BLOCK_ORIGINAL) | |
b932f770 | 585 | break; |
4891442b | 586 | |
e0082a72 ZD |
587 | min = max = bb; |
588 | for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb) | |
589 | if (STATE (bb) != BLOCK_ORIGINAL) | |
590 | max = bb; | |
402209ff JH |
591 | |
592 | /* Now re-scan and wire in all edges. This expect simple (conditional) | |
593 | jumps at the end of each new basic blocks. */ | |
2df6cea5 | 594 | make_edges (min, max, 1); |
402209ff JH |
595 | |
596 | /* Update branch probabilities. Expect only (un)conditional jumps | |
597 | to be created with only the forward edges. */ | |
87022a6b JH |
598 | if (profile_status != PROFILE_ABSENT) |
599 | FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb) | |
600 | { | |
601 | edge e; | |
628f6a4e | 602 | edge_iterator ei; |
87022a6b JH |
603 | |
604 | if (STATE (bb) == BLOCK_ORIGINAL) | |
605 | continue; | |
606 | if (STATE (bb) == BLOCK_NEW) | |
607 | { | |
608 | bb->count = 0; | |
609 | bb->frequency = 0; | |
628f6a4e | 610 | FOR_EACH_EDGE (e, ei, bb->preds) |
87022a6b JH |
611 | { |
612 | bb->count += e->count; | |
613 | bb->frequency += EDGE_FREQUENCY (e); | |
614 | } | |
615 | } | |
4891442b | 616 | |
87022a6b JH |
617 | compute_outgoing_frequencies (bb); |
618 | } | |
4891442b | 619 | |
e0082a72 ZD |
620 | FOR_EACH_BB (bb) |
621 | SET_STATE (bb, 0); | |
b932f770 | 622 | } |