]>
Commit | Line | Data |
---|---|---|
d56a8211 | 1 | /* Basic block reordering routines for the GNU compiler. |
283334f0 | 2 | Copyright (C) 2000, 2001, 2003, 2004 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" | |
3d436d2a | 34 | #include "cfgloop.h" |
0b077eac | 35 | #include "target.h" |
0435312e | 36 | #include "ggc.h" |
bc35512f | 37 | #include "alloc-pool.h" |
d56a8211 JH |
38 | |
39 | /* The contents of the current function definition are allocated | |
5f0d2358 | 40 | in this obstack, and all are freed at the end of the function. */ |
d56a8211 JH |
41 | extern struct obstack flow_obstack; |
42 | ||
bc35512f JH |
43 | alloc_pool cfg_layout_pool; |
44 | ||
d56a8211 | 45 | /* Holds the interesting trailing notes for the function. */ |
bc35512f | 46 | rtx cfg_layout_function_footer, cfg_layout_function_header; |
d56a8211 | 47 | |
d329e058 AJ |
48 | static rtx skip_insns_after_block (basic_block); |
49 | static void record_effective_endpoints (void); | |
50 | static rtx label_for_bb (basic_block); | |
51 | static void fixup_reorder_chain (void); | |
d56a8211 | 52 | |
d329e058 AJ |
53 | static void set_block_levels (tree, int); |
54 | static void change_scope (rtx, tree, tree); | |
d56a8211 | 55 | |
d329e058 | 56 | void verify_insn_chain (void); |
d329e058 AJ |
57 | static void fixup_fallthru_exit_predecessor (void); |
58 | static rtx duplicate_insn_chain (rtx, rtx); | |
d329e058 | 59 | static tree insn_scope (rtx); |
d56a8211 | 60 | \f |
9ee634e3 | 61 | rtx |
d329e058 | 62 | unlink_insn_chain (rtx first, rtx last) |
969d70ca JH |
63 | { |
64 | rtx prevfirst = PREV_INSN (first); | |
65 | rtx nextlast = NEXT_INSN (last); | |
66 | ||
67 | PREV_INSN (first) = NULL; | |
68 | NEXT_INSN (last) = NULL; | |
69 | if (prevfirst) | |
70 | NEXT_INSN (prevfirst) = nextlast; | |
71 | if (nextlast) | |
72 | PREV_INSN (nextlast) = prevfirst; | |
73 | else | |
74 | set_last_insn (prevfirst); | |
75 | if (!prevfirst) | |
76 | set_first_insn (nextlast); | |
77 | return first; | |
78 | } | |
79 | \f | |
d56a8211 JH |
80 | /* Skip over inter-block insns occurring after BB which are typically |
81 | associated with BB (e.g., barriers). If there are any such insns, | |
82 | we return the last one. Otherwise, we return the end of BB. */ | |
83 | ||
84 | static rtx | |
d329e058 | 85 | skip_insns_after_block (basic_block bb) |
d56a8211 JH |
86 | { |
87 | rtx insn, last_insn, next_head, prev; | |
88 | ||
89 | next_head = NULL_RTX; | |
f6366fc7 | 90 | if (bb->next_bb != EXIT_BLOCK_PTR) |
a813c111 | 91 | next_head = BB_HEAD (bb->next_bb); |
d56a8211 | 92 | |
a813c111 | 93 | for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; ) |
d56a8211 JH |
94 | { |
95 | if (insn == next_head) | |
96 | break; | |
97 | ||
98 | switch (GET_CODE (insn)) | |
99 | { | |
100 | case BARRIER: | |
101 | last_insn = insn; | |
102 | continue; | |
103 | ||
104 | case NOTE: | |
105 | switch (NOTE_LINE_NUMBER (insn)) | |
106 | { | |
107 | case NOTE_INSN_LOOP_END: | |
108 | case NOTE_INSN_BLOCK_END: | |
109 | last_insn = insn; | |
110 | continue; | |
111 | case NOTE_INSN_DELETED: | |
112 | case NOTE_INSN_DELETED_LABEL: | |
113 | continue; | |
114 | ||
115 | default: | |
116 | continue; | |
117 | break; | |
118 | } | |
119 | break; | |
120 | ||
121 | case CODE_LABEL: | |
122 | if (NEXT_INSN (insn) | |
123 | && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN | |
124 | && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC | |
125 | || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC)) | |
126 | { | |
127 | insn = NEXT_INSN (insn); | |
128 | last_insn = insn; | |
129 | continue; | |
130 | } | |
f87c27b4 | 131 | break; |
d56a8211 JH |
132 | |
133 | default: | |
134 | break; | |
135 | } | |
136 | ||
137 | break; | |
138 | } | |
5f0d2358 RK |
139 | |
140 | /* It is possible to hit contradictory sequence. For instance: | |
f87c27b4 | 141 | |
d56a8211 JH |
142 | jump_insn |
143 | NOTE_INSN_LOOP_BEG | |
144 | barrier | |
145 | ||
5f0d2358 RK |
146 | Where barrier belongs to jump_insn, but the note does not. This can be |
147 | created by removing the basic block originally following | |
148 | NOTE_INSN_LOOP_BEG. In such case reorder the notes. */ | |
d56a8211 | 149 | |
a813c111 | 150 | for (insn = last_insn; insn != BB_END (bb); insn = prev) |
d56a8211 | 151 | { |
5f0d2358 RK |
152 | prev = PREV_INSN (insn); |
153 | if (GET_CODE (insn) == NOTE) | |
154 | switch (NOTE_LINE_NUMBER (insn)) | |
155 | { | |
f87c27b4 KH |
156 | case NOTE_INSN_LOOP_END: |
157 | case NOTE_INSN_BLOCK_END: | |
158 | case NOTE_INSN_DELETED: | |
159 | case NOTE_INSN_DELETED_LABEL: | |
5f0d2358 | 160 | continue; |
f87c27b4 | 161 | default: |
5f0d2358 | 162 | reorder_insns (insn, insn, last_insn); |
f87c27b4 | 163 | } |
d56a8211 JH |
164 | } |
165 | ||
166 | return last_insn; | |
167 | } | |
168 | ||
169 | /* Locate or create a label for a given basic block. */ | |
170 | ||
171 | static rtx | |
d329e058 | 172 | label_for_bb (basic_block bb) |
d56a8211 | 173 | { |
a813c111 | 174 | rtx label = BB_HEAD (bb); |
d56a8211 JH |
175 | |
176 | if (GET_CODE (label) != CODE_LABEL) | |
177 | { | |
c263766c RH |
178 | if (dump_file) |
179 | fprintf (dump_file, "Emitting label for block %d\n", bb->index); | |
d56a8211 JH |
180 | |
181 | label = block_label (bb); | |
d56a8211 JH |
182 | } |
183 | ||
184 | return label; | |
185 | } | |
186 | ||
187 | /* Locate the effective beginning and end of the insn chain for each | |
188 | block, as defined by skip_insns_after_block above. */ | |
189 | ||
190 | static void | |
d329e058 | 191 | record_effective_endpoints (void) |
d56a8211 | 192 | { |
bc35512f | 193 | rtx next_insn; |
e0082a72 | 194 | basic_block bb; |
bc35512f JH |
195 | rtx insn; |
196 | ||
197 | for (insn = get_insns (); | |
65c6f1b4 ZD |
198 | insn |
199 | && GET_CODE (insn) == NOTE | |
200 | && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK; | |
bc35512f | 201 | insn = NEXT_INSN (insn)) |
65c6f1b4 ZD |
202 | continue; |
203 | if (!insn) | |
204 | abort (); /* No basic blocks at all? */ | |
205 | if (PREV_INSN (insn)) | |
206 | cfg_layout_function_header = | |
207 | unlink_insn_chain (get_insns (), PREV_INSN (insn)); | |
bc35512f JH |
208 | else |
209 | cfg_layout_function_header = NULL_RTX; | |
f87c27b4 | 210 | |
bc35512f | 211 | next_insn = get_insns (); |
e0082a72 | 212 | FOR_EACH_BB (bb) |
d56a8211 | 213 | { |
d56a8211 JH |
214 | rtx end; |
215 | ||
a813c111 | 216 | if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb)) |
bc35512f | 217 | bb->rbi->header = unlink_insn_chain (next_insn, |
a813c111 | 218 | PREV_INSN (BB_HEAD (bb))); |
d56a8211 | 219 | end = skip_insns_after_block (bb); |
a813c111 SB |
220 | if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end) |
221 | bb->rbi->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end); | |
222 | next_insn = NEXT_INSN (BB_END (bb)); | |
d56a8211 | 223 | } |
5f0d2358 | 224 | |
9ee634e3 JH |
225 | cfg_layout_function_footer = next_insn; |
226 | if (cfg_layout_function_footer) | |
227 | cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ()); | |
d56a8211 JH |
228 | } |
229 | \f | |
0435312e JH |
230 | /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line |
231 | numbers and files. In order to be GGC friendly we need to use separate | |
232 | varrays. This also slightly improve the memory locality in binary search. | |
233 | The _locs array contains locators where the given property change. The | |
234 | block_locators_blocks contains the scope block that is used for all insn | |
235 | locator greater than corresponding block_locators_locs value and smaller | |
236 | than the following one. Similarly for the other properties. */ | |
237 | static GTY(()) varray_type block_locators_locs; | |
238 | static GTY(()) varray_type block_locators_blocks; | |
239 | static GTY(()) varray_type line_locators_locs; | |
240 | static GTY(()) varray_type line_locators_lines; | |
241 | static GTY(()) varray_type file_locators_locs; | |
242 | static GTY(()) varray_type file_locators_files; | |
243 | int prologue_locator; | |
244 | int epilogue_locator; | |
245 | ||
246 | /* During the RTL expansion the lexical blocks and line numbers are | |
247 | represented via INSN_NOTEs. Replace them by representation using | |
248 | INSN_LOCATORs. */ | |
5f0d2358 | 249 | |
d73b1f07 | 250 | void |
d329e058 | 251 | insn_locators_initialize (void) |
d56a8211 | 252 | { |
d73b1f07 | 253 | tree block = NULL; |
0435312e | 254 | tree last_block = NULL; |
d73b1f07 | 255 | rtx insn, next; |
0435312e JH |
256 | int loc = 0; |
257 | int line_number = 0, last_line_number = 0; | |
258 | char *file_name = NULL, *last_file_name = NULL; | |
259 | ||
260 | prologue_locator = epilogue_locator = 0; | |
261 | ||
262 | VARRAY_INT_INIT (block_locators_locs, 32, "block_locators_locs"); | |
263 | VARRAY_TREE_INIT (block_locators_blocks, 32, "block_locators_blocks"); | |
264 | VARRAY_INT_INIT (line_locators_locs, 32, "line_locators_locs"); | |
265 | VARRAY_INT_INIT (line_locators_lines, 32, "line_locators_lines"); | |
266 | VARRAY_INT_INIT (file_locators_locs, 32, "file_locators_locs"); | |
267 | VARRAY_CHAR_PTR_INIT (file_locators_files, 32, "file_locators_files"); | |
d56a8211 | 268 | |
d73b1f07 | 269 | for (insn = get_insns (); insn; insn = next) |
d56a8211 | 270 | { |
d73b1f07 | 271 | next = NEXT_INSN (insn); |
d56a8211 | 272 | |
0435312e JH |
273 | if ((active_insn_p (insn) |
274 | && GET_CODE (PATTERN (insn)) != ADDR_VEC | |
275 | && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC) | |
276 | || !NEXT_INSN (insn) | |
277 | || (!prologue_locator && file_name)) | |
278 | { | |
279 | if (last_block != block) | |
280 | { | |
281 | loc++; | |
282 | VARRAY_PUSH_INT (block_locators_locs, loc); | |
283 | VARRAY_PUSH_TREE (block_locators_blocks, block); | |
284 | last_block = block; | |
285 | } | |
286 | if (last_line_number != line_number) | |
287 | { | |
288 | loc++; | |
289 | VARRAY_PUSH_INT (line_locators_locs, loc); | |
290 | VARRAY_PUSH_INT (line_locators_lines, line_number); | |
291 | last_line_number = line_number; | |
292 | } | |
293 | if (last_file_name != file_name) | |
294 | { | |
295 | loc++; | |
296 | VARRAY_PUSH_INT (file_locators_locs, loc); | |
297 | VARRAY_PUSH_CHAR_PTR (file_locators_files, file_name); | |
298 | last_file_name = file_name; | |
299 | } | |
300 | } | |
301 | if (!prologue_locator && file_name) | |
302 | prologue_locator = loc; | |
303 | if (!NEXT_INSN (insn)) | |
304 | epilogue_locator = loc; | |
305 | if (active_insn_p (insn)) | |
306 | INSN_LOCATOR (insn) = loc; | |
d73b1f07 | 307 | else if (GET_CODE (insn) == NOTE) |
d56a8211 | 308 | { |
d73b1f07 | 309 | switch (NOTE_LINE_NUMBER (insn)) |
d56a8211 | 310 | { |
d73b1f07 RH |
311 | case NOTE_INSN_BLOCK_BEG: |
312 | block = NOTE_BLOCK (insn); | |
313 | delete_insn (insn); | |
314 | break; | |
315 | case NOTE_INSN_BLOCK_END: | |
316 | block = BLOCK_SUPERCONTEXT (block); | |
339a28b9 ZW |
317 | if (block && TREE_CODE (block) == FUNCTION_DECL) |
318 | block = 0; | |
d73b1f07 RH |
319 | delete_insn (insn); |
320 | break; | |
321 | default: | |
0435312e JH |
322 | if (NOTE_LINE_NUMBER (insn) > 0) |
323 | { | |
324 | line_number = NOTE_LINE_NUMBER (insn); | |
325 | file_name = (char *)NOTE_SOURCE_FILE (insn); | |
326 | } | |
d73b1f07 | 327 | break; |
d56a8211 | 328 | } |
d56a8211 JH |
329 | } |
330 | } | |
1292ec0c JH |
331 | |
332 | /* Tag the blocks with a depth number so that change_scope can find | |
333 | the common parent easily. */ | |
334 | set_block_levels (DECL_INITIAL (cfun->decl), 0); | |
d56a8211 | 335 | } |
d56a8211 | 336 | |
d73b1f07 RH |
337 | /* For each lexical block, set BLOCK_NUMBER to the depth at which it is |
338 | found in the block tree. */ | |
54561457 JJ |
339 | |
340 | static void | |
d329e058 | 341 | set_block_levels (tree block, int level) |
d56a8211 | 342 | { |
d73b1f07 | 343 | while (block) |
d56a8211 | 344 | { |
d73b1f07 RH |
345 | BLOCK_NUMBER (block) = level; |
346 | set_block_levels (BLOCK_SUBBLOCKS (block), level + 1); | |
347 | block = BLOCK_CHAIN (block); | |
d56a8211 JH |
348 | } |
349 | } | |
969d70ca | 350 | \f |
1292ec0c JH |
351 | /* Return sope resulting from combination of S1 and S2. */ |
352 | tree | |
d329e058 | 353 | choose_inner_scope (tree s1, tree s2) |
1292ec0c JH |
354 | { |
355 | if (!s1) | |
356 | return s2; | |
357 | if (!s2) | |
358 | return s1; | |
359 | if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2)) | |
360 | return s1; | |
361 | return s2; | |
362 | } | |
363 | \f | |
d73b1f07 | 364 | /* Emit lexical block notes needed to change scope from S1 to S2. */ |
d56a8211 JH |
365 | |
366 | static void | |
d329e058 | 367 | change_scope (rtx orig_insn, tree s1, tree s2) |
d56a8211 | 368 | { |
d73b1f07 RH |
369 | rtx insn = orig_insn; |
370 | tree com = NULL_TREE; | |
371 | tree ts1 = s1, ts2 = s2; | |
372 | tree s; | |
5f0d2358 | 373 | |
d73b1f07 | 374 | while (ts1 != ts2) |
d56a8211 | 375 | { |
d73b1f07 RH |
376 | if (ts1 == NULL || ts2 == NULL) |
377 | abort (); | |
378 | if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2)) | |
379 | ts1 = BLOCK_SUPERCONTEXT (ts1); | |
380 | else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2)) | |
381 | ts2 = BLOCK_SUPERCONTEXT (ts2); | |
382 | else | |
d56a8211 | 383 | { |
d73b1f07 RH |
384 | ts1 = BLOCK_SUPERCONTEXT (ts1); |
385 | ts2 = BLOCK_SUPERCONTEXT (ts2); | |
d56a8211 | 386 | } |
d56a8211 | 387 | } |
d73b1f07 | 388 | com = ts1; |
d56a8211 JH |
389 | |
390 | /* Close scopes. */ | |
d73b1f07 RH |
391 | s = s1; |
392 | while (s != com) | |
d56a8211 | 393 | { |
d73b1f07 RH |
394 | rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn); |
395 | NOTE_BLOCK (note) = s; | |
396 | s = BLOCK_SUPERCONTEXT (s); | |
d56a8211 JH |
397 | } |
398 | ||
399 | /* Open scopes. */ | |
d73b1f07 RH |
400 | s = s2; |
401 | while (s != com) | |
d56a8211 | 402 | { |
d73b1f07 RH |
403 | insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn); |
404 | NOTE_BLOCK (insn) = s; | |
405 | s = BLOCK_SUPERCONTEXT (s); | |
d56a8211 JH |
406 | } |
407 | } | |
408 | ||
0435312e JH |
409 | /* Return lexical scope block insn belong to. */ |
410 | static tree | |
d329e058 | 411 | insn_scope (rtx insn) |
0435312e JH |
412 | { |
413 | int max = VARRAY_ACTIVE_SIZE (block_locators_locs); | |
414 | int min = 0; | |
415 | int loc = INSN_LOCATOR (insn); | |
416 | ||
b82c4660 CW |
417 | /* When block_locators_locs was initialized, the pro- and epilogue |
418 | insns didn't exist yet and can therefore not be found this way. | |
419 | But we know that they belong to the outer most block of the | |
420 | current function. | |
421 | Without this test, the prologue would be put inside the block of | |
422 | the first valid instruction in the function and when that first | |
423 | insn is part of an inlined function then the low_pc of that | |
424 | inlined function is messed up. Likewise for the epilogue and | |
0ee55ad8 | 425 | the last valid instruction. */ |
b82c4660 CW |
426 | if (loc == prologue_locator || loc == epilogue_locator) |
427 | return DECL_INITIAL (cfun->decl); | |
428 | ||
0435312e JH |
429 | if (!max || !loc) |
430 | return NULL; | |
431 | while (1) | |
432 | { | |
433 | int pos = (min + max) / 2; | |
434 | int tmp = VARRAY_INT (block_locators_locs, pos); | |
435 | ||
436 | if (tmp <= loc && min != pos) | |
437 | min = pos; | |
438 | else if (tmp > loc && max != pos) | |
439 | max = pos; | |
440 | else | |
441 | { | |
442 | min = pos; | |
443 | break; | |
444 | } | |
445 | } | |
446 | return VARRAY_TREE (block_locators_blocks, min); | |
447 | } | |
448 | ||
9ae130f8 | 449 | /* Return line number of the statement specified by the locator. */ |
0435312e | 450 | int |
9ae130f8 | 451 | locator_line (int loc) |
0435312e JH |
452 | { |
453 | int max = VARRAY_ACTIVE_SIZE (line_locators_locs); | |
454 | int min = 0; | |
0435312e JH |
455 | |
456 | if (!max || !loc) | |
457 | return 0; | |
458 | while (1) | |
459 | { | |
460 | int pos = (min + max) / 2; | |
461 | int tmp = VARRAY_INT (line_locators_locs, pos); | |
462 | ||
463 | if (tmp <= loc && min != pos) | |
464 | min = pos; | |
465 | else if (tmp > loc && max != pos) | |
466 | max = pos; | |
467 | else | |
468 | { | |
469 | min = pos; | |
470 | break; | |
471 | } | |
472 | } | |
473 | return VARRAY_INT (line_locators_lines, min); | |
474 | } | |
475 | ||
9ae130f8 JH |
476 | /* Return line number of the statement that produced this insn. */ |
477 | int | |
478 | insn_line (rtx insn) | |
479 | { | |
480 | return locator_line (INSN_LOCATOR (insn)); | |
481 | } | |
482 | ||
483 | /* Return source file of the statement specified by LOC. */ | |
0435312e | 484 | const char * |
9ae130f8 | 485 | locator_file (int loc) |
0435312e JH |
486 | { |
487 | int max = VARRAY_ACTIVE_SIZE (file_locators_locs); | |
488 | int min = 0; | |
0435312e JH |
489 | |
490 | if (!max || !loc) | |
491 | return NULL; | |
492 | while (1) | |
493 | { | |
494 | int pos = (min + max) / 2; | |
495 | int tmp = VARRAY_INT (file_locators_locs, pos); | |
496 | ||
497 | if (tmp <= loc && min != pos) | |
498 | min = pos; | |
499 | else if (tmp > loc && max != pos) | |
500 | max = pos; | |
501 | else | |
502 | { | |
503 | min = pos; | |
504 | break; | |
505 | } | |
506 | } | |
507 | return VARRAY_CHAR_PTR (file_locators_files, min); | |
508 | } | |
509 | ||
9ae130f8 JH |
510 | /* Return source file of the statement that produced this insn. */ |
511 | const char * | |
512 | insn_file (rtx insn) | |
513 | { | |
514 | return locator_file (INSN_LOCATOR (insn)); | |
515 | } | |
516 | ||
d56a8211 | 517 | /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based |
d73b1f07 | 518 | on the scope tree and the newly reordered instructions. */ |
d56a8211 JH |
519 | |
520 | void | |
d329e058 | 521 | reemit_insn_block_notes (void) |
d56a8211 | 522 | { |
d73b1f07 RH |
523 | tree cur_block = DECL_INITIAL (cfun->decl); |
524 | rtx insn, note; | |
5f0d2358 | 525 | |
ba4f7968 JH |
526 | insn = get_insns (); |
527 | if (!active_insn_p (insn)) | |
528 | insn = next_active_insn (insn); | |
529 | for (; insn; insn = next_active_insn (insn)) | |
d73b1f07 RH |
530 | { |
531 | tree this_block; | |
d56a8211 | 532 | |
0435312e | 533 | this_block = insn_scope (insn); |
1292ec0c | 534 | /* For sequences compute scope resulting from merging all scopes |
4b7e68e7 | 535 | of instructions nested inside. */ |
1292ec0c JH |
536 | if (GET_CODE (PATTERN (insn)) == SEQUENCE) |
537 | { | |
538 | int i; | |
539 | rtx body = PATTERN (insn); | |
540 | ||
541 | this_block = NULL; | |
542 | for (i = 0; i < XVECLEN (body, 0); i++) | |
543 | this_block = choose_inner_scope (this_block, | |
d329e058 | 544 | insn_scope (XVECEXP (body, 0, i))); |
1292ec0c | 545 | } |
d73b1f07 RH |
546 | if (! this_block) |
547 | continue; | |
d56a8211 | 548 | |
d73b1f07 RH |
549 | if (this_block != cur_block) |
550 | { | |
551 | change_scope (insn, cur_block, this_block); | |
552 | cur_block = this_block; | |
553 | } | |
d56a8211 JH |
554 | } |
555 | ||
d73b1f07 | 556 | /* change_scope emits before the insn, not after. */ |
2e040219 | 557 | note = emit_note (NOTE_INSN_DELETED); |
d73b1f07 RH |
558 | change_scope (note, cur_block, DECL_INITIAL (cfun->decl)); |
559 | delete_insn (note); | |
d56a8211 | 560 | |
d73b1f07 | 561 | reorder_blocks (); |
d56a8211 JH |
562 | } |
563 | \f | |
564 | /* Given a reorder chain, rearrange the code to match. */ | |
565 | ||
566 | static void | |
d329e058 | 567 | fixup_reorder_chain (void) |
d56a8211 | 568 | { |
918ed612 | 569 | basic_block bb, prev_bb; |
d56a8211 | 570 | int index; |
969d70ca | 571 | rtx insn = NULL; |
d56a8211 | 572 | |
bc35512f JH |
573 | if (cfg_layout_function_header) |
574 | { | |
575 | set_first_insn (cfg_layout_function_header); | |
576 | insn = cfg_layout_function_header; | |
577 | while (NEXT_INSN (insn)) | |
578 | insn = NEXT_INSN (insn); | |
579 | } | |
580 | ||
d56a8211 JH |
581 | /* First do the bulk reordering -- rechain the blocks without regard to |
582 | the needed changes to jumps and labels. */ | |
583 | ||
f6366fc7 | 584 | for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0; |
0b17ab2f | 585 | bb != 0; |
bc35512f | 586 | bb = bb->rbi->next, index++) |
d56a8211 | 587 | { |
bc35512f | 588 | if (bb->rbi->header) |
969d70ca JH |
589 | { |
590 | if (insn) | |
bc35512f | 591 | NEXT_INSN (insn) = bb->rbi->header; |
969d70ca | 592 | else |
bc35512f JH |
593 | set_first_insn (bb->rbi->header); |
594 | PREV_INSN (bb->rbi->header) = insn; | |
595 | insn = bb->rbi->header; | |
969d70ca JH |
596 | while (NEXT_INSN (insn)) |
597 | insn = NEXT_INSN (insn); | |
598 | } | |
599 | if (insn) | |
a813c111 | 600 | NEXT_INSN (insn) = BB_HEAD (bb); |
969d70ca | 601 | else |
a813c111 SB |
602 | set_first_insn (BB_HEAD (bb)); |
603 | PREV_INSN (BB_HEAD (bb)) = insn; | |
604 | insn = BB_END (bb); | |
bc35512f | 605 | if (bb->rbi->footer) |
969d70ca | 606 | { |
bc35512f JH |
607 | NEXT_INSN (insn) = bb->rbi->footer; |
608 | PREV_INSN (bb->rbi->footer) = insn; | |
969d70ca JH |
609 | while (NEXT_INSN (insn)) |
610 | insn = NEXT_INSN (insn); | |
611 | } | |
d56a8211 JH |
612 | } |
613 | ||
0b17ab2f | 614 | if (index != n_basic_blocks) |
d56a8211 JH |
615 | abort (); |
616 | ||
9ee634e3 JH |
617 | NEXT_INSN (insn) = cfg_layout_function_footer; |
618 | if (cfg_layout_function_footer) | |
619 | PREV_INSN (cfg_layout_function_footer) = insn; | |
d56a8211 JH |
620 | |
621 | while (NEXT_INSN (insn)) | |
622 | insn = NEXT_INSN (insn); | |
5f0d2358 | 623 | |
d56a8211 JH |
624 | set_last_insn (insn); |
625 | #ifdef ENABLE_CHECKING | |
626 | verify_insn_chain (); | |
627 | #endif | |
9efd34a5 | 628 | delete_dead_jumptables (); |
d56a8211 JH |
629 | |
630 | /* Now add jumps and labels as needed to match the blocks new | |
631 | outgoing edges. */ | |
632 | ||
bc35512f | 633 | for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->rbi->next) |
d56a8211 JH |
634 | { |
635 | edge e_fall, e_taken, e; | |
636 | rtx bb_end_insn; | |
637 | basic_block nb; | |
638 | ||
639 | if (bb->succ == NULL) | |
640 | continue; | |
641 | ||
642 | /* Find the old fallthru edge, and another non-EH edge for | |
643 | a taken jump. */ | |
644 | e_taken = e_fall = NULL; | |
645 | for (e = bb->succ; e ; e = e->succ_next) | |
646 | if (e->flags & EDGE_FALLTHRU) | |
647 | e_fall = e; | |
648 | else if (! (e->flags & EDGE_EH)) | |
649 | e_taken = e; | |
650 | ||
a813c111 | 651 | bb_end_insn = BB_END (bb); |
d56a8211 JH |
652 | if (GET_CODE (bb_end_insn) == JUMP_INSN) |
653 | { | |
654 | if (any_condjump_p (bb_end_insn)) | |
655 | { | |
656 | /* If the old fallthru is still next, nothing to do. */ | |
bc35512f JH |
657 | if (bb->rbi->next == e_fall->dest |
658 | || (!bb->rbi->next | |
d56a8211 JH |
659 | && e_fall->dest == EXIT_BLOCK_PTR)) |
660 | continue; | |
661 | ||
cb9a1d9b JH |
662 | /* The degenerated case of conditional jump jumping to the next |
663 | instruction can happen on target having jumps with side | |
d329e058 | 664 | effects. |
cb9a1d9b JH |
665 | |
666 | Create temporarily the duplicated edge representing branch. | |
667 | It will get unidentified by force_nonfallthru_and_redirect | |
668 | that would otherwise get confused by fallthru edge not pointing | |
669 | to the next basic block. */ | |
670 | if (!e_taken) | |
671 | { | |
672 | rtx note; | |
673 | edge e_fake; | |
674 | ||
675 | e_fake = unchecked_make_edge (bb, e_fall->dest, 0); | |
676 | ||
a813c111 | 677 | if (!redirect_jump (BB_END (bb), block_label (bb), 0)) |
cb9a1d9b | 678 | abort (); |
a813c111 | 679 | note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX); |
cb9a1d9b JH |
680 | if (note) |
681 | { | |
682 | int prob = INTVAL (XEXP (note, 0)); | |
683 | ||
684 | e_fake->probability = prob; | |
685 | e_fake->count = e_fall->count * prob / REG_BR_PROB_BASE; | |
686 | e_fall->probability -= e_fall->probability; | |
687 | e_fall->count -= e_fake->count; | |
688 | if (e_fall->probability < 0) | |
689 | e_fall->probability = 0; | |
690 | if (e_fall->count < 0) | |
691 | e_fall->count = 0; | |
692 | } | |
693 | } | |
d56a8211 JH |
694 | /* There is one special case: if *neither* block is next, |
695 | such as happens at the very end of a function, then we'll | |
696 | need to add a new unconditional jump. Choose the taken | |
697 | edge based on known or assumed probability. */ | |
bc35512f | 698 | else if (bb->rbi->next != e_taken->dest) |
d56a8211 JH |
699 | { |
700 | rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0); | |
5f0d2358 | 701 | |
d56a8211 JH |
702 | if (note |
703 | && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2 | |
704 | && invert_jump (bb_end_insn, | |
705 | label_for_bb (e_fall->dest), 0)) | |
706 | { | |
707 | e_fall->flags &= ~EDGE_FALLTHRU; | |
708 | e_taken->flags |= EDGE_FALLTHRU; | |
b446e5a2 | 709 | update_br_prob_note (bb); |
d56a8211 JH |
710 | e = e_fall, e_fall = e_taken, e_taken = e; |
711 | } | |
712 | } | |
713 | ||
f87c27b4 | 714 | /* Otherwise we can try to invert the jump. This will |
d56a8211 JH |
715 | basically never fail, however, keep up the pretense. */ |
716 | else if (invert_jump (bb_end_insn, | |
717 | label_for_bb (e_fall->dest), 0)) | |
718 | { | |
719 | e_fall->flags &= ~EDGE_FALLTHRU; | |
720 | e_taken->flags |= EDGE_FALLTHRU; | |
b446e5a2 | 721 | update_br_prob_note (bb); |
d56a8211 JH |
722 | continue; |
723 | } | |
724 | } | |
725 | else if (returnjump_p (bb_end_insn)) | |
726 | continue; | |
727 | else | |
728 | { | |
729 | /* Otherwise we have some switch or computed jump. In the | |
730 | 99% case, there should not have been a fallthru edge. */ | |
731 | if (! e_fall) | |
732 | continue; | |
5f0d2358 | 733 | |
d56a8211 JH |
734 | #ifdef CASE_DROPS_THROUGH |
735 | /* Except for VAX. Since we didn't have predication for the | |
736 | tablejump, the fallthru block should not have moved. */ | |
bc35512f | 737 | if (bb->rbi->next == e_fall->dest) |
d56a8211 JH |
738 | continue; |
739 | bb_end_insn = skip_insns_after_block (bb); | |
740 | #else | |
741 | abort (); | |
742 | #endif | |
743 | } | |
744 | } | |
745 | else | |
746 | { | |
747 | /* No fallthru implies a noreturn function with EH edges, or | |
748 | something similarly bizarre. In any case, we don't need to | |
749 | do anything. */ | |
750 | if (! e_fall) | |
751 | continue; | |
752 | ||
753 | /* If the fallthru block is still next, nothing to do. */ | |
bc35512f | 754 | if (bb->rbi->next == e_fall->dest) |
d56a8211 JH |
755 | continue; |
756 | ||
5f0d2358 | 757 | /* A fallthru to exit block. */ |
bc35512f | 758 | if (!bb->rbi->next && e_fall->dest == EXIT_BLOCK_PTR) |
d56a8211 JH |
759 | continue; |
760 | } | |
761 | ||
762 | /* We got here if we need to add a new jump insn. */ | |
d56a8211 | 763 | nb = force_nonfallthru (e_fall); |
d56a8211 JH |
764 | if (nb) |
765 | { | |
bc35512f JH |
766 | cfg_layout_initialize_rbi (nb); |
767 | nb->rbi->visited = 1; | |
768 | nb->rbi->next = bb->rbi->next; | |
769 | bb->rbi->next = nb; | |
d56a8211 JH |
770 | /* Don't process this new block. */ |
771 | bb = nb; | |
772 | } | |
773 | } | |
774 | ||
775 | /* Put basic_block_info in the new order. */ | |
0b17ab2f | 776 | |
c263766c | 777 | if (dump_file) |
d56a8211 | 778 | { |
c263766c RH |
779 | fprintf (dump_file, "Reordered sequence:\n"); |
780 | for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0; | |
781 | bb; | |
782 | bb = bb->rbi->next, index++) | |
969d70ca | 783 | { |
c263766c | 784 | fprintf (dump_file, " %i ", index); |
bc35512f | 785 | if (bb->rbi->original) |
c263766c | 786 | fprintf (dump_file, "duplicate of %i ", |
bc35512f | 787 | bb->rbi->original->index); |
c263766c RH |
788 | else if (forwarder_block_p (bb) |
789 | && GET_CODE (BB_HEAD (bb)) != CODE_LABEL) | |
790 | fprintf (dump_file, "compensation "); | |
969d70ca | 791 | else |
c263766c RH |
792 | fprintf (dump_file, "bb %i ", bb->index); |
793 | fprintf (dump_file, " [%i]\n", bb->frequency); | |
969d70ca JH |
794 | } |
795 | } | |
5f0d2358 | 796 | |
918ed612 | 797 | prev_bb = ENTRY_BLOCK_PTR; |
f6366fc7 | 798 | bb = ENTRY_BLOCK_PTR->next_bb; |
918ed612 ZD |
799 | index = 0; |
800 | ||
bc35512f | 801 | for (; bb; prev_bb = bb, bb = bb->rbi->next, index ++) |
969d70ca | 802 | { |
0b17ab2f | 803 | bb->index = index; |
d56a8211 | 804 | BASIC_BLOCK (index) = bb; |
918ed612 ZD |
805 | |
806 | bb->prev_bb = prev_bb; | |
807 | prev_bb->next_bb = bb; | |
d56a8211 | 808 | } |
918ed612 ZD |
809 | prev_bb->next_bb = EXIT_BLOCK_PTR; |
810 | EXIT_BLOCK_PTR->prev_bb = prev_bb; | |
bc35512f | 811 | |
a98ebe2e | 812 | /* Annoying special case - jump around dead jumptables left in the code. */ |
bc35512f JH |
813 | FOR_EACH_BB (bb) |
814 | { | |
815 | edge e; | |
816 | for (e = bb->succ; e && !(e->flags & EDGE_FALLTHRU); e = e->succ_next) | |
817 | continue; | |
818 | if (e && !can_fallthru (e->src, e->dest)) | |
819 | force_nonfallthru (e); | |
820 | } | |
d56a8211 JH |
821 | } |
822 | \f | |
823 | /* Perform sanity checks on the insn chain. | |
824 | 1. Check that next/prev pointers are consistent in both the forward and | |
825 | reverse direction. | |
826 | 2. Count insns in chain, going both directions, and check if equal. | |
827 | 3. Check that get_last_insn () returns the actual end of chain. */ | |
828 | ||
829 | void | |
d329e058 | 830 | verify_insn_chain (void) |
d56a8211 | 831 | { |
5f0d2358 RK |
832 | rtx x, prevx, nextx; |
833 | int insn_cnt1, insn_cnt2; | |
d56a8211 | 834 | |
5f0d2358 RK |
835 | for (prevx = NULL, insn_cnt1 = 1, x = get_insns (); |
836 | x != 0; | |
837 | prevx = x, insn_cnt1++, x = NEXT_INSN (x)) | |
838 | if (PREV_INSN (x) != prevx) | |
d56a8211 | 839 | abort (); |
d56a8211 | 840 | |
5f0d2358 RK |
841 | if (prevx != get_last_insn ()) |
842 | abort (); | |
d56a8211 | 843 | |
5f0d2358 RK |
844 | for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn (); |
845 | x != 0; | |
846 | nextx = x, insn_cnt2++, x = PREV_INSN (x)) | |
847 | if (NEXT_INSN (x) != nextx) | |
d56a8211 | 848 | abort (); |
5f0d2358 RK |
849 | |
850 | if (insn_cnt1 != insn_cnt2) | |
851 | abort (); | |
d56a8211 | 852 | } |
969d70ca JH |
853 | \f |
854 | /* The block falling through to exit must be the last one in the | |
855 | reordered chain. Ensure that this condition is met. */ | |
d0225025 | 856 | static void |
d329e058 | 857 | fixup_fallthru_exit_predecessor (void) |
49778644 JH |
858 | { |
859 | edge e; | |
860 | basic_block bb = NULL; | |
861 | ||
862 | for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next) | |
863 | if (e->flags & EDGE_FALLTHRU) | |
864 | bb = e->src; | |
5f0d2358 | 865 | |
bc35512f | 866 | if (bb && bb->rbi->next) |
49778644 | 867 | { |
f6366fc7 | 868 | basic_block c = ENTRY_BLOCK_PTR->next_bb; |
5f0d2358 | 869 | |
bc35512f JH |
870 | while (c->rbi->next != bb) |
871 | c = c->rbi->next; | |
5f0d2358 | 872 | |
bc35512f JH |
873 | c->rbi->next = bb->rbi->next; |
874 | while (c->rbi->next) | |
875 | c = c->rbi->next; | |
5f0d2358 | 876 | |
bc35512f JH |
877 | c->rbi->next = bb; |
878 | bb->rbi->next = NULL; | |
49778644 JH |
879 | } |
880 | } | |
d56a8211 | 881 | \f |
969d70ca JH |
882 | /* Return true in case it is possible to duplicate the basic block BB. */ |
883 | ||
884 | bool | |
d329e058 | 885 | cfg_layout_can_duplicate_bb_p (basic_block bb) |
969d70ca | 886 | { |
969d70ca JH |
887 | edge s; |
888 | ||
889 | if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR) | |
890 | return false; | |
891 | ||
09da1532 | 892 | /* Duplicating fallthru block to exit would require adding a jump |
969d70ca JH |
893 | and splitting the real last BB. */ |
894 | for (s = bb->succ; s; s = s->succ_next) | |
895 | if (s->dest == EXIT_BLOCK_PTR && s->flags & EDGE_FALLTHRU) | |
896 | return false; | |
897 | ||
898 | /* Do not attempt to duplicate tablejumps, as we need to unshare | |
95bd1dd7 | 899 | the dispatch table. This is difficult to do, as the instructions |
969d70ca | 900 | computing jump destination may be hoisted outside the basic block. */ |
a813c111 | 901 | if (tablejump_p (BB_END (bb), NULL, NULL)) |
969d70ca | 902 | return false; |
0b077eac RH |
903 | |
904 | /* Do not duplicate blocks containing insns that can't be copied. */ | |
905 | if (targetm.cannot_copy_insn_p) | |
906 | { | |
a813c111 | 907 | rtx insn = BB_HEAD (bb); |
0b077eac RH |
908 | while (1) |
909 | { | |
5fd9b178 | 910 | if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn)) |
0b077eac | 911 | return false; |
a813c111 | 912 | if (insn == BB_END (bb)) |
0b077eac RH |
913 | break; |
914 | insn = NEXT_INSN (insn); | |
915 | } | |
916 | } | |
917 | ||
969d70ca JH |
918 | return true; |
919 | } | |
920 | ||
921 | static rtx | |
d329e058 | 922 | duplicate_insn_chain (rtx from, rtx to) |
969d70ca JH |
923 | { |
924 | rtx insn, last; | |
925 | ||
926 | /* Avoid updating of boundaries of previous basic block. The | |
927 | note will get removed from insn stream in fixup. */ | |
2e040219 | 928 | last = emit_note (NOTE_INSN_DELETED); |
969d70ca JH |
929 | |
930 | /* Create copy at the end of INSN chain. The chain will | |
931 | be reordered later. */ | |
932 | for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn)) | |
933 | { | |
969d70ca JH |
934 | switch (GET_CODE (insn)) |
935 | { | |
936 | case INSN: | |
937 | case CALL_INSN: | |
938 | case JUMP_INSN: | |
939 | /* Avoid copying of dispatch tables. We never duplicate | |
940 | tablejumps, so this can hit only in case the table got | |
941 | moved far from original jump. */ | |
942 | if (GET_CODE (PATTERN (insn)) == ADDR_VEC | |
943 | || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC) | |
944 | break; | |
4977bab6 | 945 | emit_copy_of_insn_after (insn, get_last_insn ()); |
969d70ca JH |
946 | break; |
947 | ||
948 | case CODE_LABEL: | |
949 | break; | |
950 | ||
951 | case BARRIER: | |
952 | emit_barrier (); | |
953 | break; | |
954 | ||
955 | case NOTE: | |
956 | switch (NOTE_LINE_NUMBER (insn)) | |
957 | { | |
958 | /* In case prologue is empty and function contain label | |
959 | in first BB, we may want to copy the block. */ | |
960 | case NOTE_INSN_PROLOGUE_END: | |
961 | ||
962 | case NOTE_INSN_LOOP_VTOP: | |
963 | case NOTE_INSN_LOOP_CONT: | |
964 | case NOTE_INSN_LOOP_BEG: | |
965 | case NOTE_INSN_LOOP_END: | |
966 | /* Strip down the loop notes - we don't really want to keep | |
967 | them consistent in loop copies. */ | |
968 | case NOTE_INSN_DELETED: | |
969 | case NOTE_INSN_DELETED_LABEL: | |
970 | /* No problem to strip these. */ | |
971 | case NOTE_INSN_EPILOGUE_BEG: | |
972 | case NOTE_INSN_FUNCTION_END: | |
973 | /* Debug code expect these notes to exist just once. | |
974 | Keep them in the master copy. | |
975 | ??? It probably makes more sense to duplicate them for each | |
976 | epilogue copy. */ | |
977 | case NOTE_INSN_FUNCTION_BEG: | |
978 | /* There is always just single entry to function. */ | |
979 | case NOTE_INSN_BASIC_BLOCK: | |
980 | break; | |
981 | ||
982 | /* There is no purpose to duplicate prologue. */ | |
983 | case NOTE_INSN_BLOCK_BEG: | |
984 | case NOTE_INSN_BLOCK_END: | |
985 | /* The BLOCK_BEG/BLOCK_END notes should be eliminated when BB | |
986 | reordering is in the progress. */ | |
987 | case NOTE_INSN_EH_REGION_BEG: | |
988 | case NOTE_INSN_EH_REGION_END: | |
969d70ca JH |
989 | /* Should never exist at BB duplication time. */ |
990 | abort (); | |
991 | break; | |
992 | case NOTE_INSN_REPEATED_LINE_NUMBER: | |
5f2fc772 | 993 | emit_note_copy (insn); |
969d70ca JH |
994 | break; |
995 | ||
996 | default: | |
997 | if (NOTE_LINE_NUMBER (insn) < 0) | |
998 | abort (); | |
999 | /* It is possible that no_line_number is set and the note | |
1000 | won't be emitted. */ | |
5f2fc772 | 1001 | emit_note_copy (insn); |
969d70ca JH |
1002 | } |
1003 | break; | |
1004 | default: | |
1005 | abort (); | |
1006 | } | |
1007 | } | |
1008 | insn = NEXT_INSN (last); | |
1009 | delete_insn (last); | |
1010 | return insn; | |
1011 | } | |
8d28e87d ZD |
1012 | /* Create a duplicate of the basic block BB and redirect edge E into it. |
1013 | If E is not specified, BB is just copied, but updating the frequencies | |
1014 | etc. is left to the caller. */ | |
969d70ca JH |
1015 | |
1016 | basic_block | |
d329e058 | 1017 | cfg_layout_duplicate_bb (basic_block bb, edge e) |
969d70ca JH |
1018 | { |
1019 | rtx insn; | |
1020 | edge s, n; | |
1021 | basic_block new_bb; | |
1022 | gcov_type new_count = e ? e->count : 0; | |
1023 | ||
1024 | if (bb->count < new_count) | |
1025 | new_count = bb->count; | |
1026 | if (!bb->pred) | |
1027 | abort (); | |
1028 | #ifdef ENABLE_CHECKING | |
1029 | if (!cfg_layout_can_duplicate_bb_p (bb)) | |
1030 | abort (); | |
1031 | #endif | |
1032 | ||
a813c111 | 1033 | insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb)); |
918ed612 | 1034 | new_bb = create_basic_block (insn, |
f87c27b4 | 1035 | insn ? get_last_insn () : NULL, |
918ed612 | 1036 | EXIT_BLOCK_PTR->prev_bb); |
969d70ca | 1037 | |
bc35512f | 1038 | if (bb->rbi->header) |
969d70ca | 1039 | { |
bc35512f | 1040 | insn = bb->rbi->header; |
969d70ca JH |
1041 | while (NEXT_INSN (insn)) |
1042 | insn = NEXT_INSN (insn); | |
bc35512f | 1043 | insn = duplicate_insn_chain (bb->rbi->header, insn); |
969d70ca | 1044 | if (insn) |
bc35512f | 1045 | new_bb->rbi->header = unlink_insn_chain (insn, get_last_insn ()); |
969d70ca JH |
1046 | } |
1047 | ||
bc35512f | 1048 | if (bb->rbi->footer) |
969d70ca | 1049 | { |
bc35512f | 1050 | insn = bb->rbi->footer; |
969d70ca JH |
1051 | while (NEXT_INSN (insn)) |
1052 | insn = NEXT_INSN (insn); | |
bc35512f | 1053 | insn = duplicate_insn_chain (bb->rbi->footer, insn); |
969d70ca | 1054 | if (insn) |
bc35512f | 1055 | new_bb->rbi->footer = unlink_insn_chain (insn, get_last_insn ()); |
969d70ca JH |
1056 | } |
1057 | ||
1058 | if (bb->global_live_at_start) | |
1059 | { | |
1060 | new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack); | |
1061 | new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack); | |
1062 | COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_start); | |
1063 | COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end); | |
1064 | } | |
1065 | ||
1066 | new_bb->loop_depth = bb->loop_depth; | |
1067 | new_bb->flags = bb->flags; | |
1068 | for (s = bb->succ; s; s = s->succ_next) | |
1069 | { | |
e0fd3e7a MM |
1070 | /* Since we are creating edges from a new block to successors |
1071 | of another block (which therefore are known to be disjoint), there | |
1072 | is no need to actually check for duplicated edges. */ | |
1073 | n = unchecked_make_edge (new_bb, s->dest, s->flags); | |
969d70ca | 1074 | n->probability = s->probability; |
8d28e87d ZD |
1075 | if (e && bb->count) |
1076 | { | |
1077 | /* Take care for overflows! */ | |
1078 | n->count = s->count * (new_count * 10000 / bb->count) / 10000; | |
1079 | s->count -= n->count; | |
1080 | } | |
969d70ca | 1081 | else |
8d28e87d ZD |
1082 | n->count = s->count; |
1083 | n->aux = s->aux; | |
969d70ca JH |
1084 | } |
1085 | ||
969d70ca | 1086 | if (e) |
f87c27b4 | 1087 | { |
8d28e87d ZD |
1088 | new_bb->count = new_count; |
1089 | bb->count -= new_count; | |
1090 | ||
f87c27b4 KH |
1091 | new_bb->frequency = EDGE_FREQUENCY (e); |
1092 | bb->frequency -= EDGE_FREQUENCY (e); | |
969d70ca | 1093 | |
9ee634e3 | 1094 | redirect_edge_and_branch_force (e, new_bb); |
969d70ca | 1095 | |
8d28e87d ZD |
1096 | if (bb->count < 0) |
1097 | bb->count = 0; | |
1098 | if (bb->frequency < 0) | |
1099 | bb->frequency = 0; | |
1100 | } | |
1101 | else | |
1102 | { | |
1103 | new_bb->count = bb->count; | |
1104 | new_bb->frequency = bb->frequency; | |
1105 | } | |
969d70ca | 1106 | |
bc35512f JH |
1107 | new_bb->rbi->original = bb; |
1108 | bb->rbi->copy = new_bb; | |
8d28e87d | 1109 | |
969d70ca JH |
1110 | return new_bb; |
1111 | } | |
1112 | \f | |
bc35512f | 1113 | void |
7e51717c | 1114 | cfg_layout_initialize_rbi (basic_block bb) |
bc35512f JH |
1115 | { |
1116 | if (bb->rbi) | |
1117 | abort (); | |
1118 | bb->rbi = pool_alloc (cfg_layout_pool); | |
1119 | memset (bb->rbi, 0, sizeof (struct reorder_block_def)); | |
1120 | } | |
1121 | \f | |
969d70ca JH |
1122 | /* Main entry point to this module - initialize the datastructures for |
1123 | CFG layout changes. It keeps LOOPS up-to-date if not null. */ | |
d56a8211 JH |
1124 | |
1125 | void | |
7e51717c | 1126 | cfg_layout_initialize (void) |
d56a8211 | 1127 | { |
bc35512f JH |
1128 | basic_block bb; |
1129 | ||
969d70ca JH |
1130 | /* Our algorithm depends on fact that there are now dead jumptables |
1131 | around the code. */ | |
bc35512f JH |
1132 | cfg_layout_pool = |
1133 | create_alloc_pool ("cfg layout pool", sizeof (struct reorder_block_def), | |
1134 | n_basic_blocks + 2); | |
1135 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
1136 | cfg_layout_initialize_rbi (bb); | |
d56a8211 | 1137 | |
bc35512f | 1138 | cfg_layout_rtl_register_cfg_hooks (); |
6c81a490 | 1139 | |
d56a8211 | 1140 | record_effective_endpoints (); |
bc35512f JH |
1141 | |
1142 | cleanup_cfg (CLEANUP_CFGLAYOUT); | |
d56a8211 JH |
1143 | } |
1144 | ||
3d436d2a | 1145 | /* Splits superblocks. */ |
12c3874e | 1146 | void |
d329e058 | 1147 | break_superblocks (void) |
3d436d2a ZD |
1148 | { |
1149 | sbitmap superblocks; | |
12c3874e JH |
1150 | bool need = false; |
1151 | basic_block bb; | |
3d436d2a | 1152 | |
12c3874e | 1153 | superblocks = sbitmap_alloc (last_basic_block); |
3d436d2a ZD |
1154 | sbitmap_zero (superblocks); |
1155 | ||
12c3874e JH |
1156 | FOR_EACH_BB (bb) |
1157 | if (bb->flags & BB_SUPERBLOCK) | |
3d436d2a | 1158 | { |
12c3874e JH |
1159 | bb->flags &= ~BB_SUPERBLOCK; |
1160 | SET_BIT (superblocks, bb->index); | |
1161 | need = true; | |
3d436d2a ZD |
1162 | } |
1163 | ||
1164 | if (need) | |
1165 | { | |
1166 | rebuild_jump_labels (get_insns ()); | |
1167 | find_many_sub_basic_blocks (superblocks); | |
1168 | } | |
1169 | ||
1170 | free (superblocks); | |
1171 | } | |
1172 | ||
5f0d2358 RK |
1173 | /* Finalize the changes: reorder insn list according to the sequence, enter |
1174 | compensation code, rebuild scope forest. */ | |
d56a8211 JH |
1175 | |
1176 | void | |
d329e058 | 1177 | cfg_layout_finalize (void) |
d56a8211 | 1178 | { |
bc35512f JH |
1179 | basic_block bb; |
1180 | ||
10e9fecc JH |
1181 | #ifdef ENABLE_CHECKING |
1182 | verify_flow_info (); | |
1183 | #endif | |
9ee634e3 | 1184 | rtl_register_cfg_hooks (); |
d0225025 | 1185 | fixup_fallthru_exit_predecessor (); |
d56a8211 | 1186 | fixup_reorder_chain (); |
5f0d2358 | 1187 | |
d56a8211 JH |
1188 | #ifdef ENABLE_CHECKING |
1189 | verify_insn_chain (); | |
1190 | #endif | |
1191 | ||
bc35512f JH |
1192 | free_alloc_pool (cfg_layout_pool); |
1193 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
1194 | bb->rbi = NULL; | |
d56a8211 | 1195 | |
3d436d2a ZD |
1196 | break_superblocks (); |
1197 | ||
d56a8211 JH |
1198 | #ifdef ENABLE_CHECKING |
1199 | verify_flow_info (); | |
1200 | #endif | |
1201 | } | |
0435312e | 1202 | |
8d28e87d ZD |
1203 | /* Checks whether all N blocks in BBS array can be copied. */ |
1204 | bool | |
1205 | can_copy_bbs_p (basic_block *bbs, unsigned n) | |
1206 | { | |
1207 | unsigned i; | |
1208 | edge e; | |
1209 | int ret = true; | |
1210 | ||
1211 | for (i = 0; i < n; i++) | |
1212 | bbs[i]->rbi->duplicated = 1; | |
1213 | ||
1214 | for (i = 0; i < n; i++) | |
1215 | { | |
1216 | /* In case we should redirect abnormal edge during duplication, fail. */ | |
1217 | for (e = bbs[i]->succ; e; e = e->succ_next) | |
1218 | if ((e->flags & EDGE_ABNORMAL) | |
1219 | && e->dest->rbi->duplicated) | |
1220 | { | |
1221 | ret = false; | |
1222 | goto end; | |
1223 | } | |
1224 | ||
1225 | if (!cfg_layout_can_duplicate_bb_p (bbs[i])) | |
1226 | { | |
1227 | ret = false; | |
1228 | break; | |
1229 | } | |
1230 | } | |
1231 | ||
1232 | end: | |
1233 | for (i = 0; i < n; i++) | |
1234 | bbs[i]->rbi->duplicated = 0; | |
1235 | ||
1236 | return ret; | |
1237 | } | |
1238 | ||
1239 | /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks | |
1240 | are placed into array NEW_BBS in the same order. Edges from basic blocks | |
1241 | in BBS are also duplicated and copies of those of them | |
1242 | that lead into BBS are redirected to appropriate newly created block. The | |
1243 | function assigns bbs into loops (copy of basic block bb is assigned to | |
1244 | bb->loop_father->copy loop, so this must be set up correctly in advance) | |
1245 | and updates dominators locally (LOOPS structure that contains the information | |
1246 | about dominators is passed to enable this). | |
1247 | ||
1248 | BASE is the superloop to that basic block belongs; if its header or latch | |
1249 | is copied, we do not set the new blocks as header or latch. | |
1250 | ||
1251 | Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES, | |
1252 | also in the same order. */ | |
1253 | ||
1254 | void | |
1255 | copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs, | |
1256 | edge *edges, unsigned n_edges, edge *new_edges, | |
d47cc544 | 1257 | struct loop *base) |
8d28e87d ZD |
1258 | { |
1259 | unsigned i, j; | |
1260 | basic_block bb, new_bb, dom_bb; | |
1261 | edge e; | |
1262 | ||
1263 | /* Duplicate bbs, update dominators, assign bbs to loops. */ | |
1264 | for (i = 0; i < n; i++) | |
1265 | { | |
1266 | /* Duplicate. */ | |
1267 | bb = bbs[i]; | |
1268 | new_bb = new_bbs[i] = cfg_layout_duplicate_bb (bb, NULL); | |
1269 | bb->rbi->duplicated = 1; | |
1270 | /* Add to loop. */ | |
1271 | add_bb_to_loop (new_bb, bb->loop_father->copy); | |
8d28e87d ZD |
1272 | /* Possibly set header. */ |
1273 | if (bb->loop_father->header == bb && bb->loop_father != base) | |
1274 | new_bb->loop_father->header = new_bb; | |
1275 | /* Or latch. */ | |
1276 | if (bb->loop_father->latch == bb && bb->loop_father != base) | |
1277 | new_bb->loop_father->latch = new_bb; | |
1278 | } | |
1279 | ||
1280 | /* Set dominators. */ | |
1281 | for (i = 0; i < n; i++) | |
1282 | { | |
1283 | bb = bbs[i]; | |
1284 | new_bb = new_bbs[i]; | |
1285 | ||
d47cc544 | 1286 | dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); |
8d28e87d ZD |
1287 | if (dom_bb->rbi->duplicated) |
1288 | { | |
1289 | dom_bb = dom_bb->rbi->copy; | |
d47cc544 | 1290 | set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb); |
8d28e87d ZD |
1291 | } |
1292 | } | |
1293 | ||
1294 | /* Redirect edges. */ | |
1295 | for (j = 0; j < n_edges; j++) | |
1296 | new_edges[j] = NULL; | |
1297 | for (i = 0; i < n; i++) | |
1298 | { | |
1299 | new_bb = new_bbs[i]; | |
1300 | bb = bbs[i]; | |
1301 | ||
1302 | for (e = new_bb->succ; e; e = e->succ_next) | |
1303 | { | |
1304 | for (j = 0; j < n_edges; j++) | |
1305 | if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest) | |
1306 | new_edges[j] = e; | |
1307 | ||
1308 | if (!e->dest->rbi->duplicated) | |
1309 | continue; | |
1310 | redirect_edge_and_branch_force (e, e->dest->rbi->copy); | |
1311 | } | |
1312 | } | |
1313 | ||
1314 | /* Clear information about duplicates. */ | |
1315 | for (i = 0; i < n; i++) | |
1316 | bbs[i]->rbi->duplicated = 0; | |
1317 | } | |
1318 | ||
0435312e | 1319 | #include "gt-cfglayout.h" |