]>
Commit | Line | Data |
---|---|---|
d56a8211 | 1 | /* Basic block reordering routines for the GNU compiler. |
d0225025 | 2 | Copyright (C) 2000, 2001 Free Software Foundation, Inc. |
d56a8211 | 3 | |
5f0d2358 | 4 | This file is part of GCC. |
d56a8211 | 5 | |
5f0d2358 RK |
6 | GCC is free software; you can redistribute it and/or modify it under |
7 | the terms of the GNU General Public License as published by the Free | |
8 | Software Foundation; either version 2, or (at your option) any later | |
9 | version. | |
d56a8211 | 10 | |
5f0d2358 RK |
11 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
12 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | for more details. | |
d56a8211 | 15 | |
5f0d2358 RK |
16 | You should have received a copy of the GNU General Public License |
17 | along with GCC; see the file COPYING. If not, write to the Free | |
18 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
d56a8211 JH |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
4977bab6 ZW |
23 | #include "coretypes.h" |
24 | #include "tm.h" | |
d73b1f07 | 25 | #include "tree.h" |
d56a8211 JH |
26 | #include "rtl.h" |
27 | #include "hard-reg-set.h" | |
28 | #include "basic-block.h" | |
29 | #include "insn-config.h" | |
30 | #include "output.h" | |
31 | #include "function.h" | |
32 | #include "obstack.h" | |
33 | #include "cfglayout.h" | |
34 | ||
35 | /* The contents of the current function definition are allocated | |
5f0d2358 | 36 | in this obstack, and all are freed at the end of the function. */ |
d56a8211 JH |
37 | extern struct obstack flow_obstack; |
38 | ||
d56a8211 | 39 | /* Holds the interesting trailing notes for the function. */ |
969d70ca | 40 | static rtx function_footer; |
d56a8211 | 41 | |
d56a8211 JH |
42 | static rtx skip_insns_after_block PARAMS ((basic_block)); |
43 | static void record_effective_endpoints PARAMS ((void)); | |
44 | static rtx label_for_bb PARAMS ((basic_block)); | |
45 | static void fixup_reorder_chain PARAMS ((void)); | |
46 | ||
d73b1f07 RH |
47 | static void set_block_levels PARAMS ((tree, int)); |
48 | static void change_scope PARAMS ((rtx, tree, tree)); | |
d56a8211 JH |
49 | |
50 | void verify_insn_chain PARAMS ((void)); | |
6c81a490 | 51 | static void cleanup_unconditional_jumps PARAMS ((void)); |
d0225025 | 52 | static void fixup_fallthru_exit_predecessor PARAMS ((void)); |
969d70ca JH |
53 | static rtx unlink_insn_chain PARAMS ((rtx, rtx)); |
54 | static rtx duplicate_insn_chain PARAMS ((rtx, rtx)); | |
d56a8211 | 55 | \f |
969d70ca JH |
56 | static rtx |
57 | unlink_insn_chain (first, last) | |
58 | rtx first; | |
59 | rtx last; | |
60 | { | |
61 | rtx prevfirst = PREV_INSN (first); | |
62 | rtx nextlast = NEXT_INSN (last); | |
63 | ||
64 | PREV_INSN (first) = NULL; | |
65 | NEXT_INSN (last) = NULL; | |
66 | if (prevfirst) | |
67 | NEXT_INSN (prevfirst) = nextlast; | |
68 | if (nextlast) | |
69 | PREV_INSN (nextlast) = prevfirst; | |
70 | else | |
71 | set_last_insn (prevfirst); | |
72 | if (!prevfirst) | |
73 | set_first_insn (nextlast); | |
74 | return first; | |
75 | } | |
76 | \f | |
d56a8211 JH |
77 | /* Skip over inter-block insns occurring after BB which are typically |
78 | associated with BB (e.g., barriers). If there are any such insns, | |
79 | we return the last one. Otherwise, we return the end of BB. */ | |
80 | ||
81 | static rtx | |
82 | skip_insns_after_block (bb) | |
83 | basic_block bb; | |
84 | { | |
85 | rtx insn, last_insn, next_head, prev; | |
86 | ||
87 | next_head = NULL_RTX; | |
f6366fc7 ZD |
88 | if (bb->next_bb != EXIT_BLOCK_PTR) |
89 | next_head = bb->next_bb->head; | |
d56a8211 | 90 | |
5f0d2358 | 91 | for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)) != 0; ) |
d56a8211 JH |
92 | { |
93 | if (insn == next_head) | |
94 | break; | |
95 | ||
96 | switch (GET_CODE (insn)) | |
97 | { | |
98 | case BARRIER: | |
99 | last_insn = insn; | |
100 | continue; | |
101 | ||
102 | case NOTE: | |
103 | switch (NOTE_LINE_NUMBER (insn)) | |
104 | { | |
105 | case NOTE_INSN_LOOP_END: | |
106 | case NOTE_INSN_BLOCK_END: | |
107 | last_insn = insn; | |
108 | continue; | |
109 | case NOTE_INSN_DELETED: | |
110 | case NOTE_INSN_DELETED_LABEL: | |
111 | continue; | |
112 | ||
113 | default: | |
114 | continue; | |
115 | break; | |
116 | } | |
117 | break; | |
118 | ||
119 | case CODE_LABEL: | |
120 | if (NEXT_INSN (insn) | |
121 | && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN | |
122 | && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC | |
123 | || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC)) | |
124 | { | |
125 | insn = NEXT_INSN (insn); | |
126 | last_insn = insn; | |
127 | continue; | |
128 | } | |
f87c27b4 | 129 | break; |
d56a8211 JH |
130 | |
131 | default: | |
132 | break; | |
133 | } | |
134 | ||
135 | break; | |
136 | } | |
5f0d2358 RK |
137 | |
138 | /* It is possible to hit contradictory sequence. For instance: | |
f87c27b4 | 139 | |
d56a8211 JH |
140 | jump_insn |
141 | NOTE_INSN_LOOP_BEG | |
142 | barrier | |
143 | ||
5f0d2358 RK |
144 | Where barrier belongs to jump_insn, but the note does not. This can be |
145 | created by removing the basic block originally following | |
146 | NOTE_INSN_LOOP_BEG. In such case reorder the notes. */ | |
d56a8211 | 147 | |
d56a8211 JH |
148 | for (insn = last_insn; insn != bb->end; insn = prev) |
149 | { | |
5f0d2358 RK |
150 | prev = PREV_INSN (insn); |
151 | if (GET_CODE (insn) == NOTE) | |
152 | switch (NOTE_LINE_NUMBER (insn)) | |
153 | { | |
f87c27b4 KH |
154 | case NOTE_INSN_LOOP_END: |
155 | case NOTE_INSN_BLOCK_END: | |
156 | case NOTE_INSN_DELETED: | |
157 | case NOTE_INSN_DELETED_LABEL: | |
5f0d2358 | 158 | continue; |
f87c27b4 | 159 | default: |
5f0d2358 | 160 | reorder_insns (insn, insn, last_insn); |
f87c27b4 | 161 | } |
d56a8211 JH |
162 | } |
163 | ||
164 | return last_insn; | |
165 | } | |
166 | ||
167 | /* Locate or create a label for a given basic block. */ | |
168 | ||
169 | static rtx | |
170 | label_for_bb (bb) | |
171 | basic_block bb; | |
172 | { | |
173 | rtx label = bb->head; | |
174 | ||
175 | if (GET_CODE (label) != CODE_LABEL) | |
176 | { | |
177 | if (rtl_dump_file) | |
0b17ab2f | 178 | fprintf (rtl_dump_file, "Emitting label for block %d\n", bb->index); |
d56a8211 JH |
179 | |
180 | label = block_label (bb); | |
d56a8211 JH |
181 | } |
182 | ||
183 | return label; | |
184 | } | |
185 | ||
186 | /* Locate the effective beginning and end of the insn chain for each | |
187 | block, as defined by skip_insns_after_block above. */ | |
188 | ||
189 | static void | |
190 | record_effective_endpoints () | |
191 | { | |
192 | rtx next_insn = get_insns (); | |
e0082a72 | 193 | basic_block bb; |
f87c27b4 | 194 | |
e0082a72 | 195 | FOR_EACH_BB (bb) |
d56a8211 | 196 | { |
d56a8211 JH |
197 | rtx end; |
198 | ||
969d70ca JH |
199 | if (PREV_INSN (bb->head) && next_insn != bb->head) |
200 | RBI (bb)->header = unlink_insn_chain (next_insn, | |
201 | PREV_INSN (bb->head)); | |
d56a8211 | 202 | end = skip_insns_after_block (bb); |
969d70ca | 203 | if (NEXT_INSN (bb->end) && bb->end != end) |
f87c27b4 | 204 | RBI (bb)->footer = unlink_insn_chain (NEXT_INSN (bb->end), end); |
969d70ca | 205 | next_insn = NEXT_INSN (bb->end); |
d56a8211 | 206 | } |
5f0d2358 | 207 | |
969d70ca JH |
208 | function_footer = next_insn; |
209 | if (function_footer) | |
210 | function_footer = unlink_insn_chain (function_footer, get_last_insn ()); | |
d56a8211 JH |
211 | } |
212 | \f | |
d73b1f07 | 213 | /* Build a varray mapping INSN_UID to lexical block. Return it. */ |
5f0d2358 | 214 | |
d73b1f07 RH |
215 | void |
216 | scope_to_insns_initialize () | |
d56a8211 | 217 | { |
d73b1f07 RH |
218 | tree block = NULL; |
219 | rtx insn, next; | |
d56a8211 | 220 | |
d73b1f07 | 221 | for (insn = get_insns (); insn; insn = next) |
d56a8211 | 222 | { |
d73b1f07 | 223 | next = NEXT_INSN (insn); |
d56a8211 | 224 | |
d73b1f07 RH |
225 | if (active_insn_p (insn) |
226 | && GET_CODE (PATTERN (insn)) != ADDR_VEC | |
227 | && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC) | |
ba4f7968 | 228 | INSN_SCOPE (insn) = block; |
d73b1f07 | 229 | else if (GET_CODE (insn) == NOTE) |
d56a8211 | 230 | { |
d73b1f07 | 231 | switch (NOTE_LINE_NUMBER (insn)) |
d56a8211 | 232 | { |
d73b1f07 RH |
233 | case NOTE_INSN_BLOCK_BEG: |
234 | block = NOTE_BLOCK (insn); | |
235 | delete_insn (insn); | |
236 | break; | |
237 | case NOTE_INSN_BLOCK_END: | |
238 | block = BLOCK_SUPERCONTEXT (block); | |
239 | delete_insn (insn); | |
240 | break; | |
241 | default: | |
242 | break; | |
d56a8211 | 243 | } |
d56a8211 JH |
244 | } |
245 | } | |
1292ec0c JH |
246 | |
247 | /* Tag the blocks with a depth number so that change_scope can find | |
248 | the common parent easily. */ | |
249 | set_block_levels (DECL_INITIAL (cfun->decl), 0); | |
d56a8211 | 250 | } |
d56a8211 | 251 | |
d73b1f07 RH |
252 | /* For each lexical block, set BLOCK_NUMBER to the depth at which it is |
253 | found in the block tree. */ | |
54561457 JJ |
254 | |
255 | static void | |
d73b1f07 RH |
256 | set_block_levels (block, level) |
257 | tree block; | |
258 | int level; | |
d56a8211 | 259 | { |
d73b1f07 | 260 | while (block) |
d56a8211 | 261 | { |
d73b1f07 RH |
262 | BLOCK_NUMBER (block) = level; |
263 | set_block_levels (BLOCK_SUBBLOCKS (block), level + 1); | |
264 | block = BLOCK_CHAIN (block); | |
d56a8211 JH |
265 | } |
266 | } | |
969d70ca | 267 | \f |
1292ec0c JH |
268 | /* Return sope resulting from combination of S1 and S2. */ |
269 | tree | |
270 | choose_inner_scope (s1, s2) | |
271 | tree s1, s2; | |
272 | { | |
273 | if (!s1) | |
274 | return s2; | |
275 | if (!s2) | |
276 | return s1; | |
277 | if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2)) | |
278 | return s1; | |
279 | return s2; | |
280 | } | |
281 | \f | |
d73b1f07 | 282 | /* Emit lexical block notes needed to change scope from S1 to S2. */ |
d56a8211 JH |
283 | |
284 | static void | |
d73b1f07 RH |
285 | change_scope (orig_insn, s1, s2) |
286 | rtx orig_insn; | |
287 | tree s1, s2; | |
d56a8211 | 288 | { |
d73b1f07 RH |
289 | rtx insn = orig_insn; |
290 | tree com = NULL_TREE; | |
291 | tree ts1 = s1, ts2 = s2; | |
292 | tree s; | |
5f0d2358 | 293 | |
d73b1f07 | 294 | while (ts1 != ts2) |
d56a8211 | 295 | { |
d73b1f07 RH |
296 | if (ts1 == NULL || ts2 == NULL) |
297 | abort (); | |
298 | if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2)) | |
299 | ts1 = BLOCK_SUPERCONTEXT (ts1); | |
300 | else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2)) | |
301 | ts2 = BLOCK_SUPERCONTEXT (ts2); | |
302 | else | |
d56a8211 | 303 | { |
d73b1f07 RH |
304 | ts1 = BLOCK_SUPERCONTEXT (ts1); |
305 | ts2 = BLOCK_SUPERCONTEXT (ts2); | |
d56a8211 | 306 | } |
d56a8211 | 307 | } |
d73b1f07 | 308 | com = ts1; |
d56a8211 JH |
309 | |
310 | /* Close scopes. */ | |
d73b1f07 RH |
311 | s = s1; |
312 | while (s != com) | |
d56a8211 | 313 | { |
d73b1f07 RH |
314 | rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn); |
315 | NOTE_BLOCK (note) = s; | |
316 | s = BLOCK_SUPERCONTEXT (s); | |
d56a8211 JH |
317 | } |
318 | ||
319 | /* Open scopes. */ | |
d73b1f07 RH |
320 | s = s2; |
321 | while (s != com) | |
d56a8211 | 322 | { |
d73b1f07 RH |
323 | insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn); |
324 | NOTE_BLOCK (insn) = s; | |
325 | s = BLOCK_SUPERCONTEXT (s); | |
d56a8211 JH |
326 | } |
327 | } | |
328 | ||
d56a8211 | 329 | /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based |
d73b1f07 | 330 | on the scope tree and the newly reordered instructions. */ |
d56a8211 JH |
331 | |
332 | void | |
d73b1f07 | 333 | scope_to_insns_finalize () |
d56a8211 | 334 | { |
d73b1f07 RH |
335 | tree cur_block = DECL_INITIAL (cfun->decl); |
336 | rtx insn, note; | |
5f0d2358 | 337 | |
ba4f7968 JH |
338 | insn = get_insns (); |
339 | if (!active_insn_p (insn)) | |
340 | insn = next_active_insn (insn); | |
341 | for (; insn; insn = next_active_insn (insn)) | |
d73b1f07 RH |
342 | { |
343 | tree this_block; | |
d56a8211 | 344 | |
ba4f7968 | 345 | this_block = INSN_SCOPE (insn); |
1292ec0c | 346 | /* For sequences compute scope resulting from merging all scopes |
4b7e68e7 | 347 | of instructions nested inside. */ |
1292ec0c JH |
348 | if (GET_CODE (PATTERN (insn)) == SEQUENCE) |
349 | { | |
350 | int i; | |
351 | rtx body = PATTERN (insn); | |
352 | ||
353 | this_block = NULL; | |
354 | for (i = 0; i < XVECLEN (body, 0); i++) | |
355 | this_block = choose_inner_scope (this_block, | |
356 | INSN_SCOPE (XVECEXP (body, 0, i))); | |
357 | } | |
d73b1f07 RH |
358 | if (! this_block) |
359 | continue; | |
d56a8211 | 360 | |
d73b1f07 RH |
361 | if (this_block != cur_block) |
362 | { | |
363 | change_scope (insn, cur_block, this_block); | |
364 | cur_block = this_block; | |
365 | } | |
d56a8211 JH |
366 | } |
367 | ||
d73b1f07 RH |
368 | /* change_scope emits before the insn, not after. */ |
369 | note = emit_note (NULL, NOTE_INSN_DELETED); | |
370 | change_scope (note, cur_block, DECL_INITIAL (cfun->decl)); | |
371 | delete_insn (note); | |
d56a8211 | 372 | |
d73b1f07 | 373 | reorder_blocks (); |
d56a8211 JH |
374 | } |
375 | \f | |
376 | /* Given a reorder chain, rearrange the code to match. */ | |
377 | ||
378 | static void | |
379 | fixup_reorder_chain () | |
380 | { | |
918ed612 | 381 | basic_block bb, prev_bb; |
d56a8211 | 382 | int index; |
969d70ca | 383 | rtx insn = NULL; |
d56a8211 JH |
384 | |
385 | /* First do the bulk reordering -- rechain the blocks without regard to | |
386 | the needed changes to jumps and labels. */ | |
387 | ||
f6366fc7 | 388 | for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0; |
0b17ab2f | 389 | bb != 0; |
969d70ca | 390 | bb = RBI (bb)->next, index++) |
d56a8211 | 391 | { |
969d70ca JH |
392 | if (RBI (bb)->header) |
393 | { | |
394 | if (insn) | |
395 | NEXT_INSN (insn) = RBI (bb)->header; | |
396 | else | |
397 | set_first_insn (RBI (bb)->header); | |
398 | PREV_INSN (RBI (bb)->header) = insn; | |
399 | insn = RBI (bb)->header; | |
400 | while (NEXT_INSN (insn)) | |
401 | insn = NEXT_INSN (insn); | |
402 | } | |
403 | if (insn) | |
404 | NEXT_INSN (insn) = bb->head; | |
405 | else | |
406 | set_first_insn (bb->head); | |
407 | PREV_INSN (bb->head) = insn; | |
408 | insn = bb->end; | |
409 | if (RBI (bb)->footer) | |
410 | { | |
411 | NEXT_INSN (insn) = RBI (bb)->footer; | |
412 | PREV_INSN (RBI (bb)->footer) = insn; | |
413 | while (NEXT_INSN (insn)) | |
414 | insn = NEXT_INSN (insn); | |
415 | } | |
d56a8211 JH |
416 | } |
417 | ||
0b17ab2f | 418 | if (index != n_basic_blocks) |
d56a8211 JH |
419 | abort (); |
420 | ||
969d70ca JH |
421 | NEXT_INSN (insn) = function_footer; |
422 | if (function_footer) | |
423 | PREV_INSN (function_footer) = insn; | |
d56a8211 JH |
424 | |
425 | while (NEXT_INSN (insn)) | |
426 | insn = NEXT_INSN (insn); | |
5f0d2358 | 427 | |
d56a8211 JH |
428 | set_last_insn (insn); |
429 | #ifdef ENABLE_CHECKING | |
430 | verify_insn_chain (); | |
431 | #endif | |
432 | ||
433 | /* Now add jumps and labels as needed to match the blocks new | |
434 | outgoing edges. */ | |
435 | ||
f6366fc7 | 436 | for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = RBI (bb)->next) |
d56a8211 JH |
437 | { |
438 | edge e_fall, e_taken, e; | |
439 | rtx bb_end_insn; | |
440 | basic_block nb; | |
441 | ||
442 | if (bb->succ == NULL) | |
443 | continue; | |
444 | ||
445 | /* Find the old fallthru edge, and another non-EH edge for | |
446 | a taken jump. */ | |
447 | e_taken = e_fall = NULL; | |
448 | for (e = bb->succ; e ; e = e->succ_next) | |
449 | if (e->flags & EDGE_FALLTHRU) | |
450 | e_fall = e; | |
451 | else if (! (e->flags & EDGE_EH)) | |
452 | e_taken = e; | |
453 | ||
454 | bb_end_insn = bb->end; | |
455 | if (GET_CODE (bb_end_insn) == JUMP_INSN) | |
456 | { | |
457 | if (any_condjump_p (bb_end_insn)) | |
458 | { | |
459 | /* If the old fallthru is still next, nothing to do. */ | |
460 | if (RBI (bb)->next == e_fall->dest | |
461 | || (!RBI (bb)->next | |
462 | && e_fall->dest == EXIT_BLOCK_PTR)) | |
463 | continue; | |
464 | ||
465 | /* There is one special case: if *neither* block is next, | |
466 | such as happens at the very end of a function, then we'll | |
467 | need to add a new unconditional jump. Choose the taken | |
468 | edge based on known or assumed probability. */ | |
469 | if (RBI (bb)->next != e_taken->dest) | |
470 | { | |
471 | rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0); | |
5f0d2358 | 472 | |
d56a8211 JH |
473 | if (note |
474 | && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2 | |
475 | && invert_jump (bb_end_insn, | |
476 | label_for_bb (e_fall->dest), 0)) | |
477 | { | |
478 | e_fall->flags &= ~EDGE_FALLTHRU; | |
479 | e_taken->flags |= EDGE_FALLTHRU; | |
b446e5a2 | 480 | update_br_prob_note (bb); |
d56a8211 JH |
481 | e = e_fall, e_fall = e_taken, e_taken = e; |
482 | } | |
483 | } | |
484 | ||
f87c27b4 | 485 | /* Otherwise we can try to invert the jump. This will |
d56a8211 JH |
486 | basically never fail, however, keep up the pretense. */ |
487 | else if (invert_jump (bb_end_insn, | |
488 | label_for_bb (e_fall->dest), 0)) | |
489 | { | |
490 | e_fall->flags &= ~EDGE_FALLTHRU; | |
491 | e_taken->flags |= EDGE_FALLTHRU; | |
b446e5a2 | 492 | update_br_prob_note (bb); |
d56a8211 JH |
493 | continue; |
494 | } | |
495 | } | |
496 | else if (returnjump_p (bb_end_insn)) | |
497 | continue; | |
498 | else | |
499 | { | |
500 | /* Otherwise we have some switch or computed jump. In the | |
501 | 99% case, there should not have been a fallthru edge. */ | |
502 | if (! e_fall) | |
503 | continue; | |
5f0d2358 | 504 | |
d56a8211 JH |
505 | #ifdef CASE_DROPS_THROUGH |
506 | /* Except for VAX. Since we didn't have predication for the | |
507 | tablejump, the fallthru block should not have moved. */ | |
508 | if (RBI (bb)->next == e_fall->dest) | |
509 | continue; | |
510 | bb_end_insn = skip_insns_after_block (bb); | |
511 | #else | |
512 | abort (); | |
513 | #endif | |
514 | } | |
515 | } | |
516 | else | |
517 | { | |
518 | /* No fallthru implies a noreturn function with EH edges, or | |
519 | something similarly bizarre. In any case, we don't need to | |
520 | do anything. */ | |
521 | if (! e_fall) | |
522 | continue; | |
523 | ||
524 | /* If the fallthru block is still next, nothing to do. */ | |
525 | if (RBI (bb)->next == e_fall->dest) | |
526 | continue; | |
527 | ||
5f0d2358 | 528 | /* A fallthru to exit block. */ |
d56a8211 JH |
529 | if (!RBI (bb)->next && e_fall->dest == EXIT_BLOCK_PTR) |
530 | continue; | |
531 | } | |
532 | ||
533 | /* We got here if we need to add a new jump insn. */ | |
d56a8211 | 534 | nb = force_nonfallthru (e_fall); |
d56a8211 JH |
535 | if (nb) |
536 | { | |
537 | alloc_aux_for_block (nb, sizeof (struct reorder_block_def)); | |
d56a8211 JH |
538 | RBI (nb)->visited = 1; |
539 | RBI (nb)->next = RBI (bb)->next; | |
540 | RBI (bb)->next = nb; | |
541 | /* Don't process this new block. */ | |
542 | bb = nb; | |
543 | } | |
544 | } | |
545 | ||
546 | /* Put basic_block_info in the new order. */ | |
0b17ab2f | 547 | |
d56a8211 | 548 | if (rtl_dump_file) |
d56a8211 | 549 | { |
969d70ca | 550 | fprintf (rtl_dump_file, "Reordered sequence:\n"); |
f6366fc7 | 551 | for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0; bb; bb = RBI (bb)->next, index ++) |
969d70ca JH |
552 | { |
553 | fprintf (rtl_dump_file, " %i ", index); | |
554 | if (RBI (bb)->original) | |
555 | fprintf (rtl_dump_file, "duplicate of %i ", | |
0b17ab2f | 556 | RBI (bb)->original->index); |
969d70ca JH |
557 | else if (forwarder_block_p (bb) && GET_CODE (bb->head) != CODE_LABEL) |
558 | fprintf (rtl_dump_file, "compensation "); | |
559 | else | |
0b17ab2f | 560 | fprintf (rtl_dump_file, "bb %i ", bb->index); |
969d70ca JH |
561 | fprintf (rtl_dump_file, " [%i]\n", bb->frequency); |
562 | } | |
563 | } | |
5f0d2358 | 564 | |
918ed612 | 565 | prev_bb = ENTRY_BLOCK_PTR; |
f6366fc7 | 566 | bb = ENTRY_BLOCK_PTR->next_bb; |
918ed612 ZD |
567 | index = 0; |
568 | ||
569 | for (; bb; prev_bb = bb, bb = RBI (bb)->next, index ++) | |
969d70ca | 570 | { |
0b17ab2f | 571 | bb->index = index; |
d56a8211 | 572 | BASIC_BLOCK (index) = bb; |
918ed612 ZD |
573 | |
574 | bb->prev_bb = prev_bb; | |
575 | prev_bb->next_bb = bb; | |
d56a8211 | 576 | } |
918ed612 ZD |
577 | prev_bb->next_bb = EXIT_BLOCK_PTR; |
578 | EXIT_BLOCK_PTR->prev_bb = prev_bb; | |
d56a8211 JH |
579 | } |
580 | \f | |
581 | /* Perform sanity checks on the insn chain. | |
582 | 1. Check that next/prev pointers are consistent in both the forward and | |
583 | reverse direction. | |
584 | 2. Count insns in chain, going both directions, and check if equal. | |
585 | 3. Check that get_last_insn () returns the actual end of chain. */ | |
586 | ||
587 | void | |
588 | verify_insn_chain () | |
589 | { | |
5f0d2358 RK |
590 | rtx x, prevx, nextx; |
591 | int insn_cnt1, insn_cnt2; | |
d56a8211 | 592 | |
5f0d2358 RK |
593 | for (prevx = NULL, insn_cnt1 = 1, x = get_insns (); |
594 | x != 0; | |
595 | prevx = x, insn_cnt1++, x = NEXT_INSN (x)) | |
596 | if (PREV_INSN (x) != prevx) | |
d56a8211 | 597 | abort (); |
d56a8211 | 598 | |
5f0d2358 RK |
599 | if (prevx != get_last_insn ()) |
600 | abort (); | |
d56a8211 | 601 | |
5f0d2358 RK |
602 | for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn (); |
603 | x != 0; | |
604 | nextx = x, insn_cnt2++, x = PREV_INSN (x)) | |
605 | if (NEXT_INSN (x) != nextx) | |
d56a8211 | 606 | abort (); |
5f0d2358 RK |
607 | |
608 | if (insn_cnt1 != insn_cnt2) | |
609 | abort (); | |
d56a8211 | 610 | } |
969d70ca | 611 | \f |
6c81a490 | 612 | /* Remove any unconditional jumps and forwarder block creating fallthru |
31a78298 | 613 | edges instead. During BB reordering, fallthru edges are not required |
6c81a490 | 614 | to target next basic block in the linear CFG layout, so the unconditional |
31a78298 | 615 | jumps are not needed. */ |
6c81a490 JH |
616 | |
617 | static void | |
618 | cleanup_unconditional_jumps () | |
619 | { | |
e0082a72 | 620 | basic_block bb; |
0b17ab2f | 621 | |
e0082a72 ZD |
622 | FOR_EACH_BB (bb) |
623 | { | |
6c81a490 JH |
624 | if (!bb->succ) |
625 | continue; | |
626 | if (bb->succ->flags & EDGE_FALLTHRU) | |
627 | continue; | |
628 | if (!bb->succ->succ_next) | |
629 | { | |
630 | rtx insn; | |
e0082a72 ZD |
631 | if (GET_CODE (bb->head) != CODE_LABEL && forwarder_block_p (bb) |
632 | && bb->prev_bb != ENTRY_BLOCK_PTR) | |
6c81a490 | 633 | { |
f6366fc7 ZD |
634 | basic_block prev = bb->prev_bb; |
635 | ||
6c81a490 JH |
636 | if (rtl_dump_file) |
637 | fprintf (rtl_dump_file, "Removing forwarder BB %i\n", | |
0b17ab2f | 638 | bb->index); |
6c81a490 | 639 | |
31a78298 | 640 | redirect_edge_succ_nodup (bb->pred, bb->succ->dest); |
6c81a490 JH |
641 | flow_delete_block (bb); |
642 | bb = prev; | |
643 | } | |
644 | else if (simplejump_p (bb->end)) | |
645 | { | |
646 | rtx jump = bb->end; | |
647 | ||
648 | if (rtl_dump_file) | |
649 | fprintf (rtl_dump_file, "Removing jump %i in BB %i\n", | |
0b17ab2f | 650 | INSN_UID (jump), bb->index); |
6c81a490 JH |
651 | delete_insn (jump); |
652 | bb->succ->flags |= EDGE_FALLTHRU; | |
653 | } | |
654 | else | |
655 | continue; | |
656 | ||
6c81a490 JH |
657 | insn = NEXT_INSN (bb->end); |
658 | while (insn | |
659 | && (GET_CODE (insn) != NOTE | |
660 | || NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)) | |
661 | { | |
662 | rtx next = NEXT_INSN (insn); | |
663 | ||
664 | if (GET_CODE (insn) == BARRIER) | |
665 | delete_barrier (insn); | |
6c81a490 JH |
666 | |
667 | insn = next; | |
668 | } | |
669 | } | |
670 | } | |
671 | } | |
672 | \f | |
969d70ca JH |
673 | /* The block falling through to exit must be the last one in the |
674 | reordered chain. Ensure that this condition is met. */ | |
d0225025 AJ |
675 | static void |
676 | fixup_fallthru_exit_predecessor () | |
49778644 JH |
677 | { |
678 | edge e; | |
679 | basic_block bb = NULL; | |
680 | ||
681 | for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next) | |
682 | if (e->flags & EDGE_FALLTHRU) | |
683 | bb = e->src; | |
5f0d2358 | 684 | |
49778644 JH |
685 | if (bb && RBI (bb)->next) |
686 | { | |
f6366fc7 | 687 | basic_block c = ENTRY_BLOCK_PTR->next_bb; |
5f0d2358 | 688 | |
49778644 JH |
689 | while (RBI (c)->next != bb) |
690 | c = RBI (c)->next; | |
5f0d2358 | 691 | |
49778644 JH |
692 | RBI (c)->next = RBI (bb)->next; |
693 | while (RBI (c)->next) | |
694 | c = RBI (c)->next; | |
5f0d2358 | 695 | |
49778644 JH |
696 | RBI (c)->next = bb; |
697 | RBI (bb)->next = NULL; | |
698 | } | |
699 | } | |
d56a8211 | 700 | \f |
969d70ca JH |
701 | /* Return true in case it is possible to duplicate the basic block BB. */ |
702 | ||
703 | bool | |
704 | cfg_layout_can_duplicate_bb_p (bb) | |
705 | basic_block bb; | |
706 | { | |
707 | rtx next; | |
708 | edge s; | |
709 | ||
710 | if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR) | |
711 | return false; | |
712 | ||
09da1532 | 713 | /* Duplicating fallthru block to exit would require adding a jump |
969d70ca JH |
714 | and splitting the real last BB. */ |
715 | for (s = bb->succ; s; s = s->succ_next) | |
716 | if (s->dest == EXIT_BLOCK_PTR && s->flags & EDGE_FALLTHRU) | |
717 | return false; | |
718 | ||
719 | /* Do not attempt to duplicate tablejumps, as we need to unshare | |
720 | the dispatch table. This is dificult to do, as the instructions | |
721 | computing jump destination may be hoisted outside the basic block. */ | |
722 | if (GET_CODE (bb->end) == JUMP_INSN && JUMP_LABEL (bb->end) | |
723 | && (next = next_nonnote_insn (JUMP_LABEL (bb->end))) | |
724 | && GET_CODE (next) == JUMP_INSN | |
725 | && (GET_CODE (PATTERN (next)) == ADDR_VEC | |
726 | || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC)) | |
727 | return false; | |
728 | return true; | |
729 | } | |
730 | ||
731 | static rtx | |
732 | duplicate_insn_chain (from, to) | |
733 | rtx from, to; | |
734 | { | |
735 | rtx insn, last; | |
736 | ||
737 | /* Avoid updating of boundaries of previous basic block. The | |
738 | note will get removed from insn stream in fixup. */ | |
739 | last = emit_note (NULL, NOTE_INSN_DELETED); | |
740 | ||
741 | /* Create copy at the end of INSN chain. The chain will | |
742 | be reordered later. */ | |
743 | for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn)) | |
744 | { | |
969d70ca JH |
745 | switch (GET_CODE (insn)) |
746 | { | |
747 | case INSN: | |
748 | case CALL_INSN: | |
749 | case JUMP_INSN: | |
750 | /* Avoid copying of dispatch tables. We never duplicate | |
751 | tablejumps, so this can hit only in case the table got | |
752 | moved far from original jump. */ | |
753 | if (GET_CODE (PATTERN (insn)) == ADDR_VEC | |
754 | || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC) | |
755 | break; | |
4977bab6 | 756 | emit_copy_of_insn_after (insn, get_last_insn ()); |
969d70ca JH |
757 | break; |
758 | ||
759 | case CODE_LABEL: | |
760 | break; | |
761 | ||
762 | case BARRIER: | |
763 | emit_barrier (); | |
764 | break; | |
765 | ||
766 | case NOTE: | |
767 | switch (NOTE_LINE_NUMBER (insn)) | |
768 | { | |
769 | /* In case prologue is empty and function contain label | |
770 | in first BB, we may want to copy the block. */ | |
771 | case NOTE_INSN_PROLOGUE_END: | |
772 | ||
773 | case NOTE_INSN_LOOP_VTOP: | |
774 | case NOTE_INSN_LOOP_CONT: | |
775 | case NOTE_INSN_LOOP_BEG: | |
776 | case NOTE_INSN_LOOP_END: | |
777 | /* Strip down the loop notes - we don't really want to keep | |
778 | them consistent in loop copies. */ | |
779 | case NOTE_INSN_DELETED: | |
780 | case NOTE_INSN_DELETED_LABEL: | |
781 | /* No problem to strip these. */ | |
782 | case NOTE_INSN_EPILOGUE_BEG: | |
783 | case NOTE_INSN_FUNCTION_END: | |
784 | /* Debug code expect these notes to exist just once. | |
785 | Keep them in the master copy. | |
786 | ??? It probably makes more sense to duplicate them for each | |
787 | epilogue copy. */ | |
788 | case NOTE_INSN_FUNCTION_BEG: | |
789 | /* There is always just single entry to function. */ | |
790 | case NOTE_INSN_BASIC_BLOCK: | |
791 | break; | |
792 | ||
793 | /* There is no purpose to duplicate prologue. */ | |
794 | case NOTE_INSN_BLOCK_BEG: | |
795 | case NOTE_INSN_BLOCK_END: | |
796 | /* The BLOCK_BEG/BLOCK_END notes should be eliminated when BB | |
797 | reordering is in the progress. */ | |
798 | case NOTE_INSN_EH_REGION_BEG: | |
799 | case NOTE_INSN_EH_REGION_END: | |
969d70ca JH |
800 | /* Should never exist at BB duplication time. */ |
801 | abort (); | |
802 | break; | |
803 | case NOTE_INSN_REPEATED_LINE_NUMBER: | |
804 | emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn)); | |
805 | break; | |
806 | ||
807 | default: | |
808 | if (NOTE_LINE_NUMBER (insn) < 0) | |
809 | abort (); | |
810 | /* It is possible that no_line_number is set and the note | |
811 | won't be emitted. */ | |
812 | emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn)); | |
813 | } | |
814 | break; | |
815 | default: | |
816 | abort (); | |
817 | } | |
818 | } | |
819 | insn = NEXT_INSN (last); | |
820 | delete_insn (last); | |
821 | return insn; | |
822 | } | |
823 | ||
824 | /* Redirect Edge to DEST. */ | |
825 | void | |
826 | cfg_layout_redirect_edge (e, dest) | |
827 | edge e; | |
828 | basic_block dest; | |
829 | { | |
969d70ca | 830 | basic_block src = e->src; |
f6366fc7 | 831 | basic_block old_next_bb = src->next_bb; |
969d70ca JH |
832 | |
833 | /* Redirect_edge_and_branch may decide to turn branch into fallthru edge | |
834 | in the case the basic block appears to be in sequence. Avoid this | |
835 | transformation. */ | |
836 | ||
f6366fc7 | 837 | src->next_bb = NULL; |
969d70ca JH |
838 | if (e->flags & EDGE_FALLTHRU) |
839 | { | |
840 | /* In case we are redirecting fallthru edge to the branch edge | |
841 | of conditional jump, remove it. */ | |
842 | if (src->succ->succ_next | |
843 | && !src->succ->succ_next->succ_next) | |
844 | { | |
845 | edge s = e->succ_next ? e->succ_next : src->succ; | |
846 | if (s->dest == dest | |
847 | && any_condjump_p (src->end) | |
848 | && onlyjump_p (src->end)) | |
849 | delete_insn (src->end); | |
850 | } | |
851 | redirect_edge_succ_nodup (e, dest); | |
852 | } | |
853 | else | |
854 | redirect_edge_and_branch (e, dest); | |
6c81a490 JH |
855 | |
856 | /* We don't want simplejumps in the insn stream during cfglayout. */ | |
857 | if (simplejump_p (src->end)) | |
858 | { | |
859 | delete_insn (src->end); | |
860 | delete_barrier (NEXT_INSN (src->end)); | |
861 | src->succ->flags |= EDGE_FALLTHRU; | |
862 | } | |
f6366fc7 | 863 | src->next_bb = old_next_bb; |
969d70ca JH |
864 | } |
865 | ||
09da1532 | 866 | /* Create a duplicate of the basic block BB and redirect edge E into it. */ |
969d70ca JH |
867 | |
868 | basic_block | |
869 | cfg_layout_duplicate_bb (bb, e) | |
870 | basic_block bb; | |
871 | edge e; | |
872 | { | |
873 | rtx insn; | |
874 | edge s, n; | |
875 | basic_block new_bb; | |
876 | gcov_type new_count = e ? e->count : 0; | |
877 | ||
878 | if (bb->count < new_count) | |
879 | new_count = bb->count; | |
880 | if (!bb->pred) | |
881 | abort (); | |
882 | #ifdef ENABLE_CHECKING | |
883 | if (!cfg_layout_can_duplicate_bb_p (bb)) | |
884 | abort (); | |
885 | #endif | |
886 | ||
887 | insn = duplicate_insn_chain (bb->head, bb->end); | |
918ed612 | 888 | new_bb = create_basic_block (insn, |
f87c27b4 | 889 | insn ? get_last_insn () : NULL, |
918ed612 | 890 | EXIT_BLOCK_PTR->prev_bb); |
969d70ca JH |
891 | alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def)); |
892 | ||
893 | if (RBI (bb)->header) | |
894 | { | |
895 | insn = RBI (bb)->header; | |
896 | while (NEXT_INSN (insn)) | |
897 | insn = NEXT_INSN (insn); | |
898 | insn = duplicate_insn_chain (RBI (bb)->header, insn); | |
899 | if (insn) | |
900 | RBI (new_bb)->header = unlink_insn_chain (insn, get_last_insn ()); | |
901 | } | |
902 | ||
903 | if (RBI (bb)->footer) | |
904 | { | |
905 | insn = RBI (bb)->footer; | |
906 | while (NEXT_INSN (insn)) | |
907 | insn = NEXT_INSN (insn); | |
908 | insn = duplicate_insn_chain (RBI (bb)->footer, insn); | |
909 | if (insn) | |
910 | RBI (new_bb)->footer = unlink_insn_chain (insn, get_last_insn ()); | |
911 | } | |
912 | ||
913 | if (bb->global_live_at_start) | |
914 | { | |
915 | new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack); | |
916 | new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack); | |
917 | COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_start); | |
918 | COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end); | |
919 | } | |
920 | ||
921 | new_bb->loop_depth = bb->loop_depth; | |
922 | new_bb->flags = bb->flags; | |
923 | for (s = bb->succ; s; s = s->succ_next) | |
924 | { | |
925 | n = make_edge (new_bb, s->dest, s->flags); | |
926 | n->probability = s->probability; | |
927 | if (new_count) | |
928 | /* Take care for overflows! */ | |
929 | n->count = s->count * (new_count * 10000 / bb->count) / 10000; | |
930 | else | |
931 | n->count = 0; | |
932 | s->count -= n->count; | |
933 | } | |
934 | ||
935 | new_bb->count = new_count; | |
936 | bb->count -= new_count; | |
937 | ||
938 | if (e) | |
f87c27b4 KH |
939 | { |
940 | new_bb->frequency = EDGE_FREQUENCY (e); | |
941 | bb->frequency -= EDGE_FREQUENCY (e); | |
969d70ca | 942 | |
f87c27b4 KH |
943 | cfg_layout_redirect_edge (e, new_bb); |
944 | } | |
969d70ca JH |
945 | |
946 | if (bb->count < 0) | |
947 | bb->count = 0; | |
948 | if (bb->frequency < 0) | |
949 | bb->frequency = 0; | |
950 | ||
951 | RBI (new_bb)->original = bb; | |
952 | return new_bb; | |
953 | } | |
954 | \f | |
955 | /* Main entry point to this module - initialize the datastructures for | |
956 | CFG layout changes. It keeps LOOPS up-to-date if not null. */ | |
d56a8211 JH |
957 | |
958 | void | |
959 | cfg_layout_initialize () | |
960 | { | |
969d70ca JH |
961 | /* Our algorithm depends on fact that there are now dead jumptables |
962 | around the code. */ | |
d56a8211 JH |
963 | alloc_aux_for_blocks (sizeof (struct reorder_block_def)); |
964 | ||
6c81a490 JH |
965 | cleanup_unconditional_jumps (); |
966 | ||
d56a8211 JH |
967 | record_effective_endpoints (); |
968 | } | |
969 | ||
5f0d2358 RK |
970 | /* Finalize the changes: reorder insn list according to the sequence, enter |
971 | compensation code, rebuild scope forest. */ | |
d56a8211 JH |
972 | |
973 | void | |
974 | cfg_layout_finalize () | |
975 | { | |
d0225025 | 976 | fixup_fallthru_exit_predecessor (); |
d56a8211 | 977 | fixup_reorder_chain (); |
5f0d2358 | 978 | |
d56a8211 JH |
979 | #ifdef ENABLE_CHECKING |
980 | verify_insn_chain (); | |
981 | #endif | |
982 | ||
d56a8211 JH |
983 | free_aux_for_blocks (); |
984 | ||
985 | #ifdef ENABLE_CHECKING | |
986 | verify_flow_info (); | |
987 | #endif | |
988 | } |