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