]>
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, | |
88462c42 | 3 | 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. |
402209ff JH |
4 | |
5 | This file is part of GCC. | |
6 | ||
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 | |
10 | version. | |
11 | ||
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 | |
15 | for more details. | |
16 | ||
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 | |
20 | 02111-1307, USA. */ | |
21 | ||
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. | |
26 | ||
27 | find_basic_blocks also finds any unreachable loops and deletes them. | |
28 | ||
29 | Available functionality: | |
30 | - CFG construction | |
31 | find_basic_blocks | |
32 | - Local CFG construction | |
4891442b | 33 | find_sub_basic_blocks */ |
402209ff JH |
34 | \f |
35 | #include "config.h" | |
36 | #include "system.h" | |
4977bab6 ZW |
37 | #include "coretypes.h" |
38 | #include "tm.h" | |
402209ff JH |
39 | #include "tree.h" |
40 | #include "rtl.h" | |
41 | #include "hard-reg-set.h" | |
42 | #include "basic-block.h" | |
43 | #include "regs.h" | |
44 | #include "flags.h" | |
45 | #include "output.h" | |
46 | #include "function.h" | |
47 | #include "except.h" | |
48 | #include "toplev.h" | |
49 | #include "timevar.h" | |
4891442b | 50 | |
d329e058 AJ |
51 | static int count_basic_blocks (rtx); |
52 | static void find_basic_blocks_1 (rtx); | |
2df6cea5 | 53 | static void make_edges (basic_block, basic_block, int); |
d329e058 | 54 | static void make_label_edge (sbitmap *, basic_block, rtx, int); |
d329e058 AJ |
55 | static void find_bb_boundaries (basic_block); |
56 | static void compute_outgoing_frequencies (basic_block); | |
4891442b | 57 | \f |
9cd56be1 JH |
58 | /* Return true if insn is something that should be contained inside basic |
59 | block. */ | |
60 | ||
8f62128d | 61 | bool |
d329e058 | 62 | inside_basic_block_p (rtx insn) |
9cd56be1 JH |
63 | { |
64 | switch (GET_CODE (insn)) | |
65 | { | |
66 | case CODE_LABEL: | |
67 | /* Avoid creating of basic block for jumptables. */ | |
4891442b | 68 | return (NEXT_INSN (insn) == 0 |
4b4bf941 | 69 | || !JUMP_P (NEXT_INSN (insn)) |
4891442b RK |
70 | || (GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_VEC |
71 | && GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_DIFF_VEC)); | |
9cd56be1 JH |
72 | |
73 | case JUMP_INSN: | |
4891442b RK |
74 | return (GET_CODE (PATTERN (insn)) != ADDR_VEC |
75 | && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC); | |
9cd56be1 JH |
76 | |
77 | case CALL_INSN: | |
78 | case INSN: | |
79 | return true; | |
80 | ||
81 | case BARRIER: | |
82 | case NOTE: | |
83 | return false; | |
84 | ||
85 | default: | |
341c100f | 86 | gcc_unreachable (); |
9cd56be1 JH |
87 | } |
88 | } | |
89 | ||
4891442b RK |
90 | /* Return true if INSN may cause control flow transfer, so it should be last in |
91 | the basic block. */ | |
9cd56be1 | 92 | |
4a69cf79 | 93 | bool |
d329e058 | 94 | control_flow_insn_p (rtx insn) |
9cd56be1 JH |
95 | { |
96 | rtx note; | |
4891442b | 97 | |
9cd56be1 JH |
98 | switch (GET_CODE (insn)) |
99 | { | |
f87c27b4 KH |
100 | case NOTE: |
101 | case CODE_LABEL: | |
102 | return false; | |
103 | ||
104 | case JUMP_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); | |
108 | ||
109 | case CALL_INSN: | |
baf8706c JH |
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) | |
115 | return true; | |
f87c27b4 KH |
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, | |
119 | NULL_RTX)) | |
120 | || INTVAL (XEXP (note, 0)) >= 0)) | |
121 | /* Or may trap. */ | |
122 | || can_throw_internal (insn)); | |
123 | ||
124 | case INSN: | |
125 | return (flag_non_call_exceptions && can_throw_internal (insn)); | |
126 | ||
127 | case BARRIER: | |
a98ebe2e | 128 | /* It is nonsense to reach barrier when looking for the |
f87c27b4 KH |
129 | end of basic block, but before dead code is eliminated |
130 | this may happen. */ | |
131 | return false; | |
132 | ||
133 | default: | |
341c100f | 134 | gcc_unreachable (); |
9cd56be1 JH |
135 | } |
136 | } | |
402209ff JH |
137 | |
138 | /* Count the basic blocks of the function. */ | |
139 | ||
140 | static int | |
d329e058 | 141 | count_basic_blocks (rtx f) |
402209ff | 142 | { |
b3694847 | 143 | int count = 0; |
9cd56be1 JH |
144 | bool saw_insn = false; |
145 | rtx insn; | |
402209ff | 146 | |
402209ff JH |
147 | for (insn = f; insn; insn = NEXT_INSN (insn)) |
148 | { | |
95bd1dd7 | 149 | /* Code labels and barriers causes current basic block to be |
9cd56be1 | 150 | terminated at previous real insn. */ |
4b4bf941 | 151 | if ((LABEL_P (insn) || BARRIER_P (insn)) |
9cd56be1 JH |
152 | && saw_insn) |
153 | count++, saw_insn = false; | |
402209ff | 154 | |
9cd56be1 JH |
155 | /* Start basic block if needed. */ |
156 | if (!saw_insn && inside_basic_block_p (insn)) | |
157 | saw_insn = true; | |
402209ff | 158 | |
9cd56be1 JH |
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; | |
402209ff | 162 | } |
4891442b | 163 | |
9cd56be1 JH |
164 | if (saw_insn) |
165 | count++; | |
402209ff JH |
166 | |
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. */ | |
169 | if (count == 0) | |
170 | { | |
171 | emit_insn (gen_rtx_USE (VOIDmode, const0_rtx)); | |
172 | count = 1; | |
173 | } | |
174 | ||
175 | return count; | |
176 | } | |
402209ff JH |
177 | \f |
178 | /* Create an edge between two basic blocks. FLAGS are auxiliary information | |
179 | about the edge that is accumulated between calls. */ | |
180 | ||
181 | /* Create an edge from a basic block to a label. */ | |
182 | ||
183 | static void | |
d329e058 | 184 | make_label_edge (sbitmap *edge_cache, basic_block src, rtx label, int flags) |
402209ff | 185 | { |
341c100f | 186 | gcc_assert (LABEL_P (label)); |
402209ff JH |
187 | |
188 | /* If the label was never emitted, this insn is junk, but avoid a | |
189 | crash trying to refer to BLOCK_FOR_INSN (label). This can happen | |
190 | as a result of a syntax error and a diagnostic has already been | |
191 | printed. */ | |
192 | ||
193 | if (INSN_UID (label) == 0) | |
194 | return; | |
195 | ||
7ded4467 | 196 | cached_make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags); |
402209ff JH |
197 | } |
198 | ||
199 | /* Create the edges generated by INSN in REGION. */ | |
200 | ||
12c3874e | 201 | void |
6de9cd9a | 202 | rtl_make_eh_edge (sbitmap *edge_cache, basic_block src, rtx insn) |
402209ff | 203 | { |
4b4bf941 | 204 | int is_call = CALL_P (insn) ? EDGE_ABNORMAL_CALL : 0; |
402209ff JH |
205 | rtx handlers, i; |
206 | ||
207 | handlers = reachable_handlers (insn); | |
208 | ||
209 | for (i = handlers; i; i = XEXP (i, 1)) | |
210 | make_label_edge (edge_cache, src, XEXP (i, 0), | |
211 | EDGE_ABNORMAL | EDGE_EH | is_call); | |
212 | ||
213 | free_INSN_LIST_list (&handlers); | |
214 | } | |
4891442b | 215 | |
402209ff JH |
216 | /* Identify the edges between basic blocks MIN to MAX. |
217 | ||
218 | NONLOCAL_LABEL_LIST is a list of non-local labels in the function. Blocks | |
219 | that are otherwise unreachable may be reachable with a non-local goto. | |
220 | ||
221 | BB_EH_END is an array indexed by basic block number in which we record | |
222 | the list of exception regions active at the end of the basic block. */ | |
223 | ||
224 | static void | |
2df6cea5 | 225 | make_edges (basic_block min, basic_block max, int update_p) |
402209ff | 226 | { |
e0082a72 | 227 | basic_block bb; |
402209ff JH |
228 | sbitmap *edge_cache = NULL; |
229 | ||
230 | /* Assume no computed jump; revise as we create edges. */ | |
231 | current_function_has_computed_jump = 0; | |
232 | ||
750054a2 | 233 | /* If we are partitioning hot and cold basic blocks into separate |
8e8d5162 CT |
234 | sections, we cannot assume there is no computed jump (partitioning |
235 | sometimes requires the use of indirect jumps; see comments about | |
236 | partitioning at the top of bb-reorder.c:partition_hot_cold_basic_blocks | |
237 | for complete details). */ | |
750054a2 CT |
238 | |
239 | if (flag_reorder_blocks_and_partition) | |
240 | current_function_has_computed_jump = 1; | |
241 | ||
402209ff JH |
242 | /* Heavy use of computed goto in machine-generated code can lead to |
243 | nearly fully-connected CFGs. In that case we spend a significant | |
244 | amount of time searching the edge lists for duplicates. */ | |
2df6cea5 | 245 | if (forced_labels || cfun->max_jumptable_ents > 100) |
402209ff | 246 | { |
d55bc081 ZD |
247 | edge_cache = sbitmap_vector_alloc (last_basic_block, last_basic_block); |
248 | sbitmap_vector_zero (edge_cache, last_basic_block); | |
402209ff JH |
249 | |
250 | if (update_p) | |
e0082a72 | 251 | FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb) |
402209ff JH |
252 | { |
253 | edge e; | |
628f6a4e | 254 | edge_iterator ei; |
4891442b | 255 | |
628f6a4e | 256 | FOR_EACH_EDGE (e, ei, bb->succs) |
402209ff | 257 | if (e->dest != EXIT_BLOCK_PTR) |
e0082a72 | 258 | SET_BIT (edge_cache[bb->index], e->dest->index); |
402209ff JH |
259 | } |
260 | } | |
261 | ||
e0082a72 ZD |
262 | /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block |
263 | is always the entry. */ | |
f6366fc7 ZD |
264 | if (min == ENTRY_BLOCK_PTR->next_bb) |
265 | cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, min, | |
4891442b | 266 | EDGE_FALLTHRU); |
402209ff | 267 | |
e0082a72 | 268 | FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb) |
402209ff | 269 | { |
402209ff JH |
270 | rtx insn, x; |
271 | enum rtx_code code; | |
272 | int force_fallthru = 0; | |
623a66fa | 273 | edge e; |
628f6a4e | 274 | edge_iterator ei; |
402209ff | 275 | |
4b4bf941 | 276 | if (LABEL_P (BB_HEAD (bb)) |
a813c111 | 277 | && LABEL_ALT_ENTRY_P (BB_HEAD (bb))) |
7ded4467 | 278 | cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0); |
402209ff JH |
279 | |
280 | /* Examine the last instruction of the block, and discover the | |
281 | ways we can leave the block. */ | |
282 | ||
a813c111 | 283 | insn = BB_END (bb); |
402209ff JH |
284 | code = GET_CODE (insn); |
285 | ||
286 | /* A branch. */ | |
287 | if (code == JUMP_INSN) | |
288 | { | |
289 | rtx tmp; | |
290 | ||
291 | /* Recognize exception handling placeholders. */ | |
292 | if (GET_CODE (PATTERN (insn)) == RESX) | |
6de9cd9a | 293 | rtl_make_eh_edge (edge_cache, bb, insn); |
402209ff JH |
294 | |
295 | /* Recognize a non-local goto as a branch outside the | |
296 | current function. */ | |
297 | else if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX)) | |
298 | ; | |
299 | ||
e1233a7d RH |
300 | /* Recognize a tablejump and do the right thing. */ |
301 | else if (tablejump_p (insn, NULL, &tmp)) | |
402209ff JH |
302 | { |
303 | rtvec vec; | |
304 | int j; | |
305 | ||
306 | if (GET_CODE (PATTERN (tmp)) == ADDR_VEC) | |
307 | vec = XVEC (PATTERN (tmp), 0); | |
308 | else | |
309 | vec = XVEC (PATTERN (tmp), 1); | |
310 | ||
311 | for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) | |
312 | make_label_edge (edge_cache, bb, | |
313 | XEXP (RTVEC_ELT (vec, j), 0), 0); | |
314 | ||
315 | /* Some targets (eg, ARM) emit a conditional jump that also | |
316 | contains the out-of-range target. Scan for these and | |
317 | add an edge if necessary. */ | |
318 | if ((tmp = single_set (insn)) != NULL | |
319 | && SET_DEST (tmp) == pc_rtx | |
320 | && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE | |
321 | && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF) | |
322 | make_label_edge (edge_cache, bb, | |
323 | XEXP (XEXP (SET_SRC (tmp), 2), 0), 0); | |
324 | ||
325 | #ifdef CASE_DROPS_THROUGH | |
326 | /* Silly VAXen. The ADDR_VEC is going to be in the way of | |
327 | us naturally detecting fallthru into the next block. */ | |
328 | force_fallthru = 1; | |
329 | #endif | |
330 | } | |
331 | ||
332 | /* If this is a computed jump, then mark it as reaching | |
2df6cea5 | 333 | everything on the forced_labels list. */ |
402209ff JH |
334 | else if (computed_jump_p (insn)) |
335 | { | |
336 | current_function_has_computed_jump = 1; | |
337 | ||
402209ff JH |
338 | for (x = forced_labels; x; x = XEXP (x, 1)) |
339 | make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL); | |
340 | } | |
341 | ||
342 | /* Returns create an exit out. */ | |
343 | else if (returnjump_p (insn)) | |
7ded4467 | 344 | cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0); |
402209ff JH |
345 | |
346 | /* Otherwise, we have a plain conditional or unconditional jump. */ | |
347 | else | |
348 | { | |
341c100f | 349 | gcc_assert (JUMP_LABEL (insn)); |
402209ff JH |
350 | make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0); |
351 | } | |
352 | } | |
353 | ||
4891442b RK |
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. */ | |
402209ff | 358 | if (code == CALL_INSN && SIBLING_CALL_P (insn)) |
792bb204 RH |
359 | cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, |
360 | EDGE_SIBCALL | EDGE_ABNORMAL); | |
402209ff JH |
361 | |
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. | |
402209ff | 365 | Also mark the CALL_INSN as reaching any nonlocal goto handler. */ |
402209ff JH |
366 | else if (code == CALL_INSN || flag_non_call_exceptions) |
367 | { | |
368 | /* Add any appropriate EH edges. */ | |
6de9cd9a | 369 | rtl_make_eh_edge (edge_cache, bb, insn); |
402209ff JH |
370 | |
371 | if (code == CALL_INSN && nonlocal_goto_handler_labels) | |
372 | { | |
373 | /* ??? This could be made smarter: in some cases it's possible | |
374 | to tell that certain calls will not do a nonlocal goto. | |
402209ff JH |
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. */ | |
4891442b | 379 | |
402209ff JH |
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); | |
4891442b | 383 | |
402209ff JH |
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); | |
388 | } | |
389 | } | |
390 | ||
391 | /* Find out if we can drop through to the next block. */ | |
26f74aa3 | 392 | insn = NEXT_INSN (insn); |
628f6a4e | 393 | FOR_EACH_EDGE (e, ei, bb->succs) |
623a66fa R |
394 | if (e->dest == EXIT_BLOCK_PTR && e->flags & EDGE_FALLTHRU) |
395 | { | |
396 | insn = 0; | |
397 | break; | |
398 | } | |
26f74aa3 | 399 | while (insn |
4b4bf941 | 400 | && NOTE_P (insn) |
26f74aa3 JH |
401 | && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK) |
402 | insn = NEXT_INSN (insn); | |
403 | ||
f6366fc7 | 404 | if (!insn || (bb->next_bb == EXIT_BLOCK_PTR && force_fallthru)) |
7ded4467 | 405 | cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU); |
f6366fc7 | 406 | else if (bb->next_bb != EXIT_BLOCK_PTR) |
402209ff | 407 | { |
a813c111 | 408 | if (force_fallthru || insn == BB_HEAD (bb->next_bb)) |
f6366fc7 | 409 | cached_make_edge (edge_cache, bb, bb->next_bb, EDGE_FALLTHRU); |
402209ff JH |
410 | } |
411 | } | |
412 | ||
413 | if (edge_cache) | |
414 | sbitmap_vector_free (edge_cache); | |
415 | } | |
416 | \f | |
417 | /* Find all basic blocks of the function whose first insn is F. | |
418 | ||
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. */ | |
421 | ||
422 | static void | |
d329e058 | 423 | find_basic_blocks_1 (rtx f) |
402209ff | 424 | { |
b3694847 | 425 | rtx insn, next; |
402209ff | 426 | rtx bb_note = NULL_RTX; |
402209ff JH |
427 | rtx head = NULL_RTX; |
428 | rtx end = NULL_RTX; | |
918ed612 | 429 | basic_block prev = ENTRY_BLOCK_PTR; |
402209ff JH |
430 | |
431 | /* We process the instructions in a slightly different way than we did | |
432 | previously. This is so that we see a NOTE_BASIC_BLOCK after we have | |
433 | closed out the previous block, so that it gets attached at the proper | |
434 | place. Since this form should be equivalent to the previous, | |
435 | count_basic_blocks continues to use the old form as a check. */ | |
436 | ||
437 | for (insn = f; insn; insn = next) | |
438 | { | |
439 | enum rtx_code code = GET_CODE (insn); | |
440 | ||
441 | next = NEXT_INSN (insn); | |
442 | ||
4b4bf941 | 443 | if ((LABEL_P (insn) || BARRIER_P (insn)) |
9cd56be1 JH |
444 | && head) |
445 | { | |
852c6ec7 | 446 | prev = create_basic_block_structure (head, end, bb_note, prev); |
9cd56be1 JH |
447 | head = end = NULL_RTX; |
448 | bb_note = NULL_RTX; | |
449 | } | |
4891442b | 450 | |
9cd56be1 JH |
451 | if (inside_basic_block_p (insn)) |
452 | { | |
453 | if (head == NULL_RTX) | |
454 | head = insn; | |
455 | end = insn; | |
456 | } | |
4891442b | 457 | |
9cd56be1 JH |
458 | if (head && control_flow_insn_p (insn)) |
459 | { | |
852c6ec7 | 460 | prev = create_basic_block_structure (head, end, bb_note, prev); |
9cd56be1 JH |
461 | head = end = NULL_RTX; |
462 | bb_note = NULL_RTX; | |
463 | } | |
464 | ||
402209ff JH |
465 | switch (code) |
466 | { | |
467 | case NOTE: | |
468 | { | |
469 | int kind = NOTE_LINE_NUMBER (insn); | |
470 | ||
471 | /* Look for basic block notes with which to keep the | |
472 | basic_block_info pointers stable. Unthread the note now; | |
473 | we'll put it back at the right place in create_basic_block. | |
474 | Or not at all if we've already found a note in this block. */ | |
475 | if (kind == NOTE_INSN_BASIC_BLOCK) | |
476 | { | |
477 | if (bb_note == NULL_RTX) | |
478 | bb_note = insn; | |
479 | else | |
53c17031 | 480 | next = delete_insn (insn); |
402209ff JH |
481 | } |
482 | break; | |
483 | } | |
484 | ||
485 | case CODE_LABEL: | |
402209ff | 486 | case JUMP_INSN: |
6ce2bcb7 | 487 | case CALL_INSN: |
9cd56be1 | 488 | case INSN: |
402209ff | 489 | case BARRIER: |
9cd56be1 | 490 | break; |
402209ff | 491 | |
402209ff | 492 | default: |
341c100f | 493 | gcc_unreachable (); |
402209ff | 494 | } |
402209ff JH |
495 | } |
496 | ||
497 | if (head != NULL_RTX) | |
852c6ec7 | 498 | create_basic_block_structure (head, end, bb_note, prev); |
402209ff | 499 | else if (bb_note) |
53c17031 | 500 | delete_insn (bb_note); |
402209ff | 501 | |
341c100f | 502 | gcc_assert (last_basic_block == n_basic_blocks); |
402209ff | 503 | |
4ab95d82 | 504 | clear_aux_for_blocks (); |
402209ff JH |
505 | } |
506 | ||
507 | ||
508 | /* Find basic blocks of the current function. | |
509 | F is the first insn of the function and NREGS the number of register | |
510 | numbers in use. */ | |
511 | ||
512 | void | |
d329e058 AJ |
513 | find_basic_blocks (rtx f, int nregs ATTRIBUTE_UNUSED, |
514 | FILE *file ATTRIBUTE_UNUSED) | |
402209ff | 515 | { |
e0082a72 ZD |
516 | basic_block bb; |
517 | ||
402209ff JH |
518 | timevar_push (TV_CFG); |
519 | ||
520 | /* Flush out existing data. */ | |
521 | if (basic_block_info != NULL) | |
522 | { | |
402209ff JH |
523 | clear_edges (); |
524 | ||
525 | /* Clear bb->aux on all extant basic blocks. We'll use this as a | |
526 | tag for reuse during create_basic_block, just in case some pass | |
527 | copies around basic block notes improperly. */ | |
e0082a72 | 528 | FOR_EACH_BB (bb) |
d329e058 | 529 | bb->aux = NULL; |
402209ff | 530 | |
6de9cd9a | 531 | basic_block_info = NULL; |
402209ff JH |
532 | } |
533 | ||
0b17ab2f | 534 | n_basic_blocks = count_basic_blocks (f); |
bf77398c | 535 | last_basic_block = 0; |
918ed612 ZD |
536 | ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR; |
537 | EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR; | |
402209ff JH |
538 | |
539 | /* Size the basic block table. The actual structures will be allocated | |
540 | by find_basic_blocks_1, since we want to keep the structure pointers | |
541 | stable across calls to find_basic_blocks. */ | |
542 | /* ??? This whole issue would be much simpler if we called find_basic_blocks | |
543 | exactly once, and thereafter we don't have a single long chain of | |
544 | instructions at all until close to the end of compilation when we | |
545 | actually lay them out. */ | |
546 | ||
0b17ab2f | 547 | VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info"); |
402209ff JH |
548 | |
549 | find_basic_blocks_1 (f); | |
550 | ||
878f99d2 JH |
551 | profile_status = PROFILE_ABSENT; |
552 | ||
402209ff | 553 | /* Discover the edges of our cfg. */ |
2df6cea5 | 554 | make_edges (ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0); |
402209ff JH |
555 | |
556 | /* Do very simple cleanup now, for the benefit of code that runs between | |
557 | here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns. */ | |
558 | tidy_fallthru_edges (); | |
559 | ||
402209ff JH |
560 | #ifdef ENABLE_CHECKING |
561 | verify_flow_info (); | |
562 | #endif | |
563 | timevar_pop (TV_CFG); | |
564 | } | |
565 | \f | |
b932f770 | 566 | /* State of basic block as seen by find_sub_basic_blocks. */ |
4891442b RK |
567 | enum state {BLOCK_NEW = 0, BLOCK_ORIGINAL, BLOCK_TO_SPLIT}; |
568 | ||
569 | #define STATE(BB) (enum state) ((size_t) (BB)->aux) | |
570 | #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE)) | |
b932f770 JH |
571 | |
572 | /* Scan basic block BB for possible BB boundaries inside the block | |
573 | and create new basic blocks in the progress. */ | |
574 | ||
575 | static void | |
d329e058 | 576 | find_bb_boundaries (basic_block bb) |
402209ff | 577 | { |
a813c111 SB |
578 | rtx insn = BB_HEAD (bb); |
579 | rtx end = BB_END (bb); | |
f068df3f RH |
580 | rtx flow_transfer_insn = NULL_RTX; |
581 | edge fallthru = NULL; | |
402209ff | 582 | |
a813c111 | 583 | if (insn == BB_END (bb)) |
402209ff JH |
584 | return; |
585 | ||
4b4bf941 | 586 | if (LABEL_P (insn)) |
402209ff JH |
587 | insn = NEXT_INSN (insn); |
588 | ||
589 | /* Scan insn chain and try to find new basic block boundaries. */ | |
590 | while (1) | |
591 | { | |
592 | enum rtx_code code = GET_CODE (insn); | |
f068df3f | 593 | |
9cd56be1 JH |
594 | /* On code label, split current basic block. */ |
595 | if (code == CODE_LABEL) | |
402209ff | 596 | { |
f068df3f RH |
597 | fallthru = split_block (bb, PREV_INSN (insn)); |
598 | if (flow_transfer_insn) | |
a813c111 | 599 | BB_END (bb) = flow_transfer_insn; |
4891442b | 600 | |
f068df3f RH |
601 | bb = fallthru->dest; |
602 | remove_edge (fallthru); | |
603 | flow_transfer_insn = NULL_RTX; | |
0dc36574 | 604 | if (LABEL_ALT_ENTRY_P (insn)) |
7ded4467 | 605 | make_edge (ENTRY_BLOCK_PTR, bb, 0); |
402209ff | 606 | } |
4891442b | 607 | |
9cd56be1 JH |
608 | /* In case we've previously seen an insn that effects a control |
609 | flow transfer, split the block. */ | |
610 | if (flow_transfer_insn && inside_basic_block_p (insn)) | |
611 | { | |
612 | fallthru = split_block (bb, PREV_INSN (insn)); | |
a813c111 | 613 | BB_END (bb) = flow_transfer_insn; |
9cd56be1 JH |
614 | bb = fallthru->dest; |
615 | remove_edge (fallthru); | |
616 | flow_transfer_insn = NULL_RTX; | |
617 | } | |
4891442b | 618 | |
9cd56be1 JH |
619 | if (control_flow_insn_p (insn)) |
620 | flow_transfer_insn = insn; | |
402209ff JH |
621 | if (insn == end) |
622 | break; | |
623 | insn = NEXT_INSN (insn); | |
624 | } | |
625 | ||
626 | /* In case expander replaced normal insn by sequence terminating by | |
627 | return and barrier, or possibly other sequence not behaving like | |
628 | ordinary jump, we need to take care and move basic block boundary. */ | |
f068df3f | 629 | if (flow_transfer_insn) |
a813c111 | 630 | BB_END (bb) = flow_transfer_insn; |
402209ff JH |
631 | |
632 | /* We've possibly replaced the conditional jump by conditional jump | |
633 | followed by cleanup at fallthru edge, so the outgoing edges may | |
634 | be dead. */ | |
635 | purge_dead_edges (bb); | |
b932f770 JH |
636 | } |
637 | ||
638 | /* Assume that frequency of basic block B is known. Compute frequencies | |
639 | and probabilities of outgoing edges. */ | |
640 | ||
641 | static void | |
d329e058 | 642 | compute_outgoing_frequencies (basic_block b) |
b932f770 JH |
643 | { |
644 | edge e, f; | |
628f6a4e | 645 | edge_iterator ei; |
4891442b | 646 | |
628f6a4e | 647 | if (EDGE_COUNT (b->succs) == 2) |
b932f770 | 648 | { |
a813c111 | 649 | rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL); |
b932f770 JH |
650 | int probability; |
651 | ||
87022a6b JH |
652 | if (note) |
653 | { | |
654 | probability = INTVAL (XEXP (note, 0)); | |
655 | e = BRANCH_EDGE (b); | |
656 | e->probability = probability; | |
657 | e->count = ((b->count * probability + REG_BR_PROB_BASE / 2) | |
658 | / REG_BR_PROB_BASE); | |
659 | f = FALLTHRU_EDGE (b); | |
660 | f->probability = REG_BR_PROB_BASE - probability; | |
661 | f->count = b->count - e->count; | |
662 | return; | |
663 | } | |
b932f770 | 664 | } |
4891442b | 665 | |
628f6a4e | 666 | if (EDGE_COUNT (b->succs) == 1) |
b932f770 | 667 | { |
628f6a4e | 668 | e = EDGE_SUCC (b, 0); |
b932f770 JH |
669 | e->probability = REG_BR_PROB_BASE; |
670 | e->count = b->count; | |
87022a6b | 671 | return; |
b932f770 | 672 | } |
87022a6b JH |
673 | guess_outgoing_edge_probabilities (b); |
674 | if (b->count) | |
628f6a4e | 675 | FOR_EACH_EDGE (e, ei, b->succs) |
87022a6b JH |
676 | e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2) |
677 | / REG_BR_PROB_BASE); | |
b932f770 JH |
678 | } |
679 | ||
680 | /* Assume that someone emitted code with control flow instructions to the | |
681 | basic block. Update the data structure. */ | |
682 | ||
683 | void | |
d329e058 | 684 | find_many_sub_basic_blocks (sbitmap blocks) |
b932f770 | 685 | { |
e0082a72 | 686 | basic_block bb, min, max; |
b932f770 | 687 | |
e0082a72 ZD |
688 | FOR_EACH_BB (bb) |
689 | SET_STATE (bb, | |
690 | TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL); | |
b932f770 | 691 | |
e0082a72 ZD |
692 | FOR_EACH_BB (bb) |
693 | if (STATE (bb) == BLOCK_TO_SPLIT) | |
694 | find_bb_boundaries (bb); | |
b932f770 | 695 | |
e0082a72 ZD |
696 | FOR_EACH_BB (bb) |
697 | if (STATE (bb) != BLOCK_ORIGINAL) | |
b932f770 | 698 | break; |
4891442b | 699 | |
e0082a72 ZD |
700 | min = max = bb; |
701 | for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb) | |
702 | if (STATE (bb) != BLOCK_ORIGINAL) | |
703 | max = bb; | |
402209ff JH |
704 | |
705 | /* Now re-scan and wire in all edges. This expect simple (conditional) | |
706 | jumps at the end of each new basic blocks. */ | |
2df6cea5 | 707 | make_edges (min, max, 1); |
402209ff JH |
708 | |
709 | /* Update branch probabilities. Expect only (un)conditional jumps | |
710 | to be created with only the forward edges. */ | |
87022a6b JH |
711 | if (profile_status != PROFILE_ABSENT) |
712 | FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb) | |
713 | { | |
714 | edge e; | |
628f6a4e | 715 | edge_iterator ei; |
87022a6b JH |
716 | |
717 | if (STATE (bb) == BLOCK_ORIGINAL) | |
718 | continue; | |
719 | if (STATE (bb) == BLOCK_NEW) | |
720 | { | |
721 | bb->count = 0; | |
722 | bb->frequency = 0; | |
628f6a4e | 723 | FOR_EACH_EDGE (e, ei, bb->preds) |
87022a6b JH |
724 | { |
725 | bb->count += e->count; | |
726 | bb->frequency += EDGE_FREQUENCY (e); | |
727 | } | |
728 | } | |
4891442b | 729 | |
87022a6b JH |
730 | compute_outgoing_frequencies (bb); |
731 | } | |
4891442b | 732 | |
e0082a72 ZD |
733 | FOR_EACH_BB (bb) |
734 | SET_STATE (bb, 0); | |
b932f770 JH |
735 | } |
736 | ||
737 | /* Like above but for single basic block only. */ | |
738 | ||
739 | void | |
d329e058 | 740 | find_sub_basic_blocks (basic_block bb) |
b932f770 | 741 | { |
e0082a72 | 742 | basic_block min, max, b; |
f6366fc7 | 743 | basic_block next = bb->next_bb; |
b932f770 | 744 | |
e0082a72 | 745 | min = bb; |
b932f770 | 746 | find_bb_boundaries (bb); |
e0082a72 | 747 | max = next->prev_bb; |
b932f770 JH |
748 | |
749 | /* Now re-scan and wire in all edges. This expect simple (conditional) | |
750 | jumps at the end of each new basic blocks. */ | |
2df6cea5 | 751 | make_edges (min, max, 1); |
b932f770 JH |
752 | |
753 | /* Update branch probabilities. Expect only (un)conditional jumps | |
754 | to be created with only the forward edges. */ | |
e0082a72 | 755 | FOR_BB_BETWEEN (b, min, max->next_bb, next_bb) |
b932f770 JH |
756 | { |
757 | edge e; | |
628f6a4e | 758 | edge_iterator ei; |
b932f770 | 759 | |
e0082a72 | 760 | if (b != min) |
402209ff | 761 | { |
b932f770 JH |
762 | b->count = 0; |
763 | b->frequency = 0; | |
628f6a4e | 764 | FOR_EACH_EDGE (e, ei, b->preds) |
b932f770 JH |
765 | { |
766 | b->count += e->count; | |
767 | b->frequency += EDGE_FREQUENCY (e); | |
768 | } | |
402209ff | 769 | } |
4891442b | 770 | |
b932f770 | 771 | compute_outgoing_frequencies (b); |
402209ff JH |
772 | } |
773 | } |