]>
Commit | Line | Data |
---|---|---|
a6540cbf | 1 | /* Basic block reordering routines for the GNU compiler. |
2 | Copyright (C) 2000 Free Software Foundation, Inc. | |
3 | ||
f12b58b3 | 4 | This file is part of GCC. |
a6540cbf | 5 | |
f12b58b3 | 6 | GCC is free software; you can redistribute it and/or modify it |
7 | under the terms of the GNU General Public License as published by | |
a6540cbf | 8 | the Free Software Foundation; either version 2, or (at your option) |
9 | any later version. | |
10 | ||
f12b58b3 | 11 | GCC is distributed in the hope that it will be useful, but WITHOUT |
12 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
13 | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public | |
14 | License for more details. | |
a6540cbf | 15 | |
16 | You should have received a copy of the GNU General Public License | |
f12b58b3 | 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. */ | |
a6540cbf | 20 | |
21 | /* References: | |
22 | ||
23 | "Profile Guided Code Positioning" | |
24 | Pettis and Hanson; PLDI '90. | |
075d20cf | 25 | |
26 | TODO: | |
27 | ||
28 | (1) Consider: | |
29 | ||
30 | if (p) goto A; // predict taken | |
31 | foo (); | |
32 | A: | |
33 | if (q) goto B; // predict taken | |
34 | bar (); | |
35 | B: | |
36 | baz (); | |
37 | return; | |
38 | ||
39 | We'll currently reorder this as | |
40 | ||
41 | if (!p) goto C; | |
42 | A: | |
43 | if (!q) goto D; | |
44 | B: | |
45 | baz (); | |
46 | return; | |
47 | D: | |
48 | bar (); | |
49 | goto B; | |
50 | C: | |
51 | foo (); | |
52 | goto A; | |
53 | ||
54 | A better ordering is | |
55 | ||
56 | if (!p) goto C; | |
57 | if (!q) goto D; | |
58 | B: | |
59 | baz (); | |
60 | return; | |
61 | C: | |
62 | foo (); | |
63 | if (q) goto B; | |
64 | D: | |
65 | bar (); | |
66 | goto B; | |
67 | ||
68 | This requires that we be able to duplicate the jump at A, and | |
69 | adjust the graph traversal such that greedy placement doesn't | |
70 | fix D before C is considered. | |
71 | ||
72 | (2) Coordinate with shorten_branches to minimize the number of | |
73 | long branches. | |
74 | ||
75 | (3) Invent a method by which sufficiently non-predicted code can | |
76 | be moved to either the end of the section or another section | |
77 | entirely. Some sort of NOTE_INSN note would work fine. | |
78 | ||
79 | This completely scroggs all debugging formats, so the user | |
80 | would have to explicitly ask for it. | |
a6540cbf | 81 | */ |
82 | ||
83 | #include "config.h" | |
84 | #include "system.h" | |
85 | #include "tree.h" | |
86 | #include "rtl.h" | |
87 | #include "tm_p.h" | |
d6cb6164 | 88 | #include "hard-reg-set.h" |
a6540cbf | 89 | #include "basic-block.h" |
90 | #include "insn-config.h" | |
91 | #include "regs.h" | |
a6540cbf | 92 | #include "flags.h" |
93 | #include "output.h" | |
94 | #include "function.h" | |
a6540cbf | 95 | #include "toplev.h" |
96 | #include "recog.h" | |
a6540cbf | 97 | #include "expr.h" |
98 | #include "obstack.h" | |
99 | ||
100 | ||
075d20cf | 101 | #ifndef HAVE_epilogue |
102 | #define HAVE_epilogue 0 | |
103 | #endif | |
104 | ||
105 | ||
a6540cbf | 106 | /* The contents of the current function definition are allocated |
107 | in this obstack, and all are freed at the end of the function. | |
108 | For top-level functions, this is temporary_obstack. | |
109 | Separate obstacks are made for nested functions. */ | |
110 | ||
d7c47c0e | 111 | extern struct obstack flow_obstack; |
a6540cbf | 112 | |
113 | ||
a8edab65 | 114 | /* Structure to hold information about lexical scopes. */ |
115 | typedef struct scope_def | |
116 | { | |
117 | int level; | |
118 | ||
119 | /* The NOTE_INSN_BLOCK_BEG that started this scope. */ | |
120 | rtx note_beg; | |
121 | ||
122 | /* The NOTE_INSN_BLOCK_END that ended this scope. */ | |
123 | rtx note_end; | |
124 | ||
125 | /* The bb containing note_beg (if any). */ | |
126 | basic_block bb_beg; | |
127 | ||
128 | /* The bb containing note_end (if any). */ | |
129 | basic_block bb_end; | |
130 | ||
131 | /* List of basic blocks contained within this scope. */ | |
132 | basic_block *bbs; | |
133 | ||
134 | /* Number of blocks contained within this scope. */ | |
135 | int num_bbs; | |
136 | ||
137 | /* The outer scope or NULL if outermost scope. */ | |
138 | struct scope_def *outer; | |
139 | ||
140 | /* The first inner scope or NULL if innermost scope. */ | |
141 | struct scope_def *inner; | |
142 | ||
143 | /* The last inner scope or NULL if innermost scope. */ | |
144 | struct scope_def *inner_last; | |
145 | ||
146 | /* Link to the next (sibling) scope. */ | |
147 | struct scope_def *next; | |
148 | } *scope; | |
149 | ||
075d20cf | 150 | |
a8edab65 | 151 | /* Structure to hold information about the scope forest. */ |
152 | typedef struct | |
153 | { | |
154 | /* Number of trees in forest. */ | |
155 | int num_trees; | |
156 | ||
157 | /* List of tree roots. */ | |
158 | scope *trees; | |
159 | } scope_forest_info; | |
160 | ||
075d20cf | 161 | /* Structure to hold information about the blocks during reordering. */ |
162 | typedef struct reorder_block_def | |
163 | { | |
afe4711a | 164 | rtx eff_head; |
165 | rtx eff_end; | |
a8edab65 | 166 | scope scope; |
075d20cf | 167 | basic_block next; |
168 | int index; | |
169 | int visited; | |
a6540cbf | 170 | } *reorder_block_def; |
171 | ||
075d20cf | 172 | #define RBI(BB) ((reorder_block_def) (BB)->aux) |
a6540cbf | 173 | |
a6540cbf | 174 | |
175 | /* Local function prototypes. */ | |
050ad704 | 176 | static rtx skip_insns_after_block PARAMS ((basic_block)); |
075d20cf | 177 | static void record_effective_endpoints PARAMS ((void)); |
178 | static void make_reorder_chain PARAMS ((void)); | |
179 | static basic_block make_reorder_chain_1 PARAMS ((basic_block, basic_block)); | |
180 | static rtx label_for_bb PARAMS ((basic_block)); | |
181 | static rtx emit_jump_to_block_after PARAMS ((basic_block, rtx)); | |
a6540cbf | 182 | static void fixup_reorder_chain PARAMS ((void)); |
a8edab65 | 183 | static void relate_bbs_with_scopes PARAMS ((scope)); |
184 | static scope make_new_scope PARAMS ((int, rtx)); | |
185 | static void build_scope_forest PARAMS ((scope_forest_info *)); | |
186 | static void remove_scope_notes PARAMS ((void)); | |
187 | static void insert_intra_1 PARAMS ((scope, rtx *)); | |
188 | static void insert_intra_bb_scope_notes PARAMS ((basic_block)); | |
189 | static void insert_inter_bb_scope_notes PARAMS ((basic_block, basic_block)); | |
190 | static void rebuild_scope_notes PARAMS ((scope_forest_info *)); | |
191 | static void free_scope_forest_1 PARAMS ((scope)); | |
192 | static void free_scope_forest PARAMS ((scope_forest_info *)); | |
193 | void dump_scope_forest PARAMS ((scope_forest_info *)); | |
194 | static void dump_scope_forest_1 PARAMS ((scope, int)); | |
2f5d30d9 | 195 | static rtx get_next_bb_note PARAMS ((rtx)); |
196 | static rtx get_prev_bb_note PARAMS ((rtx)); | |
a6540cbf | 197 | |
075d20cf | 198 | void verify_insn_chain PARAMS ((void)); |
199 | \f | |
050ad704 | 200 | /* Skip over inter-block insns occurring after BB which are typically |
201 | associated with BB (e.g., barriers). If there are any such insns, | |
202 | we return the last one. Otherwise, we return the end of BB. */ | |
a6540cbf | 203 | |
204 | static rtx | |
050ad704 | 205 | skip_insns_after_block (bb) |
a6540cbf | 206 | basic_block bb; |
a6540cbf | 207 | { |
ee8f4738 | 208 | rtx insn, last_insn, next_head, prev; |
a6540cbf | 209 | |
075d20cf | 210 | next_head = NULL_RTX; |
211 | if (bb->index + 1 != n_basic_blocks) | |
212 | next_head = BASIC_BLOCK (bb->index + 1)->head; | |
a6540cbf | 213 | |
0c07445c | 214 | for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)); ) |
050ad704 | 215 | { |
075d20cf | 216 | if (insn == next_head) |
050ad704 | 217 | break; |
218 | ||
075d20cf | 219 | switch (GET_CODE (insn)) |
a6540cbf | 220 | { |
075d20cf | 221 | case BARRIER: |
0c07445c | 222 | last_insn = insn; |
050ad704 | 223 | continue; |
a6540cbf | 224 | |
075d20cf | 225 | case NOTE: |
226 | switch (NOTE_LINE_NUMBER (insn)) | |
227 | { | |
228 | case NOTE_INSN_LOOP_END: | |
229 | case NOTE_INSN_BLOCK_END: | |
0c07445c | 230 | last_insn = insn; |
231 | continue; | |
075d20cf | 232 | case NOTE_INSN_DELETED: |
233 | case NOTE_INSN_DELETED_LABEL: | |
234 | continue; | |
235 | ||
236 | default: | |
ee8f4738 | 237 | continue; |
075d20cf | 238 | break; |
239 | } | |
240 | break; | |
241 | ||
242 | case CODE_LABEL: | |
243 | if (NEXT_INSN (insn) | |
244 | && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN | |
245 | && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC | |
246 | || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC)) | |
247 | { | |
248 | insn = NEXT_INSN (insn); | |
0c07445c | 249 | last_insn = insn; |
075d20cf | 250 | continue; |
251 | } | |
252 | break; | |
253 | ||
254 | default: | |
255 | break; | |
256 | } | |
a6540cbf | 257 | |
050ad704 | 258 | break; |
a6540cbf | 259 | } |
ee8f4738 | 260 | /* It is possible to hit contradicting sequence. For instance: |
261 | ||
262 | jump_insn | |
263 | NOTE_INSN_LOOP_BEG | |
264 | barrier | |
265 | ||
266 | Where barrier belongs to jump_insn, but the note does not. | |
267 | This can be created by removing the basic block originally | |
268 | following NOTE_INSN_LOOP_BEG. | |
269 | ||
270 | In such case reorder the notes. */ | |
271 | for (insn = last_insn; insn != bb->end; insn = prev) | |
272 | { | |
273 | prev = PREV_INSN (insn); | |
274 | if (GET_CODE (insn) == NOTE) | |
275 | switch (NOTE_LINE_NUMBER (insn)) | |
276 | { | |
277 | case NOTE_INSN_LOOP_END: | |
278 | case NOTE_INSN_BLOCK_END: | |
279 | case NOTE_INSN_DELETED: | |
280 | case NOTE_INSN_DELETED_LABEL: | |
281 | continue; | |
282 | default: | |
283 | reorder_insns (insn, insn, last_insn); | |
284 | } | |
285 | } | |
a6540cbf | 286 | |
287 | return last_insn; | |
288 | } | |
289 | ||
290 | ||
075d20cf | 291 | /* Locate the effective beginning and end of the insn chain for each |
292 | block, as defined by skip_insns_after_block above. */ | |
a6540cbf | 293 | |
075d20cf | 294 | static void |
295 | record_effective_endpoints () | |
a6540cbf | 296 | { |
075d20cf | 297 | rtx next_insn = get_insns (); |
298 | int i; | |
299 | ||
300 | for (i = 0; i < n_basic_blocks; ++i) | |
a6540cbf | 301 | { |
075d20cf | 302 | basic_block bb = BASIC_BLOCK (i); |
303 | rtx end; | |
304 | ||
305 | RBI (bb)->eff_head = next_insn; | |
306 | end = skip_insns_after_block (bb); | |
307 | RBI (bb)->eff_end = end; | |
308 | next_insn = NEXT_INSN (end); | |
a6540cbf | 309 | } |
a6540cbf | 310 | } |
311 | ||
312 | ||
075d20cf | 313 | /* Compute an ordering for a subgraph beginning with block BB. Record the |
314 | ordering in RBI()->index and chained through RBI()->next. */ | |
a6540cbf | 315 | |
075d20cf | 316 | static void |
317 | make_reorder_chain () | |
a6540cbf | 318 | { |
075d20cf | 319 | basic_block last_block = NULL; |
320 | basic_block prev = NULL; | |
321 | int nbb_m1 = n_basic_blocks - 1; | |
322 | ||
323 | /* If we've not got epilogue in RTL, we must fallthru to the exit. | |
324 | Force the last block to be at the end. */ | |
325 | /* ??? Some ABIs (e.g. MIPS) require the return insn to be at the | |
326 | end of the function for stack unwinding purposes. */ | |
327 | if (! HAVE_epilogue) | |
a6540cbf | 328 | { |
075d20cf | 329 | last_block = BASIC_BLOCK (nbb_m1); |
330 | RBI (last_block)->visited = 1; | |
331 | nbb_m1 -= 1; | |
332 | } | |
364e846c | 333 | |
075d20cf | 334 | /* Loop until we've placed every block. */ |
335 | do | |
336 | { | |
337 | int i; | |
338 | basic_block next = NULL; | |
a6540cbf | 339 | |
075d20cf | 340 | /* Find the next unplaced block. */ |
341 | /* ??? Get rid of this loop, and track which blocks are not yet | |
342 | placed more directly, so as to avoid the O(N^2) worst case. | |
343 | Perhaps keep a doubly-linked list of all to-be-placed blocks; | |
344 | remove from the list as we place. The head of that list is | |
345 | what we're looking for here. */ | |
346 | ||
347 | for (i = 0; i <= nbb_m1; ++i) | |
a6540cbf | 348 | { |
075d20cf | 349 | basic_block bb = BASIC_BLOCK (i); |
350 | if (! RBI (bb)->visited) | |
a6540cbf | 351 | { |
075d20cf | 352 | next = bb; |
353 | break; | |
a6540cbf | 354 | } |
355 | } | |
075d20cf | 356 | if (! next) |
357 | abort (); | |
358 | ||
359 | prev = make_reorder_chain_1 (next, prev); | |
a6540cbf | 360 | } |
075d20cf | 361 | while (RBI (prev)->index < nbb_m1); |
362 | ||
363 | /* Terminate the chain. */ | |
364 | if (! HAVE_epilogue) | |
a6540cbf | 365 | { |
075d20cf | 366 | RBI (prev)->next = last_block; |
367 | RBI (last_block)->index = RBI (prev)->index + 1; | |
368 | prev = last_block; | |
a6540cbf | 369 | } |
075d20cf | 370 | RBI (prev)->next = NULL; |
371 | } | |
a6540cbf | 372 | |
075d20cf | 373 | /* A helper function for make_reorder_chain. |
a6540cbf | 374 | |
075d20cf | 375 | We do not follow EH edges, or non-fallthru edges to noreturn blocks. |
376 | These are assumed to be the error condition and we wish to cluster | |
377 | all of them at the very end of the function for the benefit of cache | |
378 | locality for the rest of the function. | |
a6540cbf | 379 | |
075d20cf | 380 | ??? We could do slightly better by noticing earlier that some subgraph |
381 | has all paths leading to noreturn functions, but for there to be more | |
382 | than one block in such a subgraph is rare. */ | |
a6540cbf | 383 | |
075d20cf | 384 | static basic_block |
385 | make_reorder_chain_1 (bb, prev) | |
386 | basic_block bb; | |
387 | basic_block prev; | |
388 | { | |
389 | edge e; | |
390 | basic_block next; | |
391 | rtx note; | |
392 | ||
393 | /* Mark this block visited. */ | |
394 | if (prev) | |
a6540cbf | 395 | { |
075d20cf | 396 | int new_index; |
a6540cbf | 397 | |
075d20cf | 398 | restart: |
399 | RBI (prev)->next = bb; | |
400 | new_index = RBI (prev)->index + 1; | |
401 | RBI (bb)->index = new_index; | |
a6540cbf | 402 | |
075d20cf | 403 | if (rtl_dump_file && prev->index + 1 != bb->index) |
404 | fprintf (rtl_dump_file, "Reordering block %d (%d) after %d (%d)\n", | |
405 | bb->index, RBI (bb)->index, prev->index, RBI (prev)->index); | |
a6540cbf | 406 | } |
075d20cf | 407 | else |
408 | RBI (bb)->index = 0; | |
409 | RBI (bb)->visited = 1; | |
410 | prev = bb; | |
a6540cbf | 411 | |
075d20cf | 412 | if (bb->succ == NULL) |
413 | return prev; | |
414 | ||
415 | /* Find the most probable block. */ | |
416 | ||
417 | next = NULL; | |
418 | if (any_condjump_p (bb->end) | |
419 | && (note = find_reg_note (bb->end, REG_BR_PROB, 0)) != NULL) | |
a6540cbf | 420 | { |
075d20cf | 421 | int taken, probability; |
422 | edge e_taken, e_fall; | |
a6540cbf | 423 | |
075d20cf | 424 | probability = INTVAL (XEXP (note, 0)); |
425 | taken = probability > REG_BR_PROB_BASE / 2; | |
426 | ||
427 | /* Find the normal taken edge and the normal fallthru edge. | |
5dac3693 | 428 | |
429 | Note, conditional jumps with other side effects may not | |
430 | be fully optimized. In this case it is possible for | |
431 | the conditional jump to branch to the same location as | |
432 | the fallthru path. | |
433 | ||
434 | We should probably work to improve optimization of that | |
435 | case; however, it seems silly not to also deal with such | |
436 | problems here if they happen to occur. */ | |
075d20cf | 437 | |
438 | e_taken = e_fall = NULL; | |
439 | for (e = bb->succ; e ; e = e->succ_next) | |
5dac3693 | 440 | { |
441 | if (e->flags & EDGE_FALLTHRU) | |
442 | e_fall = e; | |
b21ae3ff | 443 | else if (! (e->flags & EDGE_EH)) |
5dac3693 | 444 | e_taken = e; |
445 | } | |
075d20cf | 446 | |
447 | next = (taken ? e_taken : e_fall)->dest; | |
a6540cbf | 448 | } |
449 | ||
075d20cf | 450 | /* In the absence of a prediction, disturb things as little as possible |
451 | by selecting the old "next" block from the list of successors. If | |
452 | there had been a fallthru edge, that will be the one. */ | |
453 | if (! next) | |
454 | { | |
455 | for (e = bb->succ; e ; e = e->succ_next) | |
456 | if (e->dest->index == bb->index + 1) | |
457 | { | |
458 | if ((e->flags & EDGE_FALLTHRU) | |
459 | || (e->dest->succ | |
460 | && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))) | |
461 | next = e->dest; | |
462 | break; | |
463 | } | |
464 | } | |
a6540cbf | 465 | |
075d20cf | 466 | /* Make sure we didn't select a silly next block. */ |
467 | if (! next || next == EXIT_BLOCK_PTR || RBI (next)->visited) | |
468 | next = NULL; | |
a6540cbf | 469 | |
075d20cf | 470 | /* Recurse on the successors. Unroll the last call, as the normal |
471 | case is exactly one or two edges, and we can tail recurse. */ | |
472 | for (e = bb->succ; e; e = e->succ_next) | |
473 | if (e->dest != EXIT_BLOCK_PTR | |
474 | && ! RBI (e->dest)->visited | |
475 | && e->dest->succ | |
476 | && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))) | |
477 | { | |
478 | if (next) | |
479 | { | |
480 | prev = make_reorder_chain_1 (next, prev); | |
481 | next = RBI (e->dest)->visited ? NULL : e->dest; | |
482 | } | |
483 | else | |
484 | next = e->dest; | |
485 | } | |
486 | if (next) | |
487 | { | |
488 | bb = next; | |
489 | goto restart; | |
490 | } | |
a6540cbf | 491 | |
075d20cf | 492 | return prev; |
a6540cbf | 493 | } |
494 | ||
495 | ||
075d20cf | 496 | /* Locate or create a label for a given basic block. */ |
a6540cbf | 497 | |
075d20cf | 498 | static rtx |
499 | label_for_bb (bb) | |
a6540cbf | 500 | basic_block bb; |
501 | { | |
075d20cf | 502 | rtx label = bb->head; |
a6540cbf | 503 | |
075d20cf | 504 | if (GET_CODE (label) != CODE_LABEL) |
a6540cbf | 505 | { |
075d20cf | 506 | if (rtl_dump_file) |
507 | fprintf (rtl_dump_file, "Emitting label for block %d (%d)\n", | |
508 | bb->index, RBI (bb)->index); | |
a6540cbf | 509 | |
075d20cf | 510 | label = emit_label_before (gen_label_rtx (), label); |
511 | if (bb->head == RBI (bb)->eff_head) | |
512 | RBI (bb)->eff_head = label; | |
513 | bb->head = label; | |
a6540cbf | 514 | } |
515 | ||
075d20cf | 516 | return label; |
517 | } | |
a6540cbf | 518 | |
a6540cbf | 519 | |
075d20cf | 520 | /* Emit a jump to BB after insn AFTER. */ |
a6540cbf | 521 | |
075d20cf | 522 | static rtx |
523 | emit_jump_to_block_after (bb, after) | |
524 | basic_block bb; | |
525 | rtx after; | |
526 | { | |
527 | rtx jump; | |
528 | ||
529 | if (bb != EXIT_BLOCK_PTR) | |
a6540cbf | 530 | { |
075d20cf | 531 | rtx label = label_for_bb (bb); |
532 | jump = emit_jump_insn_after (gen_jump (label), after); | |
533 | JUMP_LABEL (jump) = label; | |
534 | LABEL_NUSES (label) += 1; | |
0c07445c | 535 | if (basic_block_for_insn) |
536 | set_block_for_new_insns (jump, bb); | |
a6540cbf | 537 | |
075d20cf | 538 | if (rtl_dump_file) |
539 | fprintf (rtl_dump_file, "Emitting jump to block %d (%d)\n", | |
540 | bb->index, RBI (bb)->index); | |
541 | } | |
542 | else | |
a6540cbf | 543 | { |
66d9dc73 | 544 | #ifdef HAVE_return |
075d20cf | 545 | if (! HAVE_return) |
546 | abort (); | |
547 | jump = emit_jump_insn_after (gen_return (), after); | |
a6540cbf | 548 | |
075d20cf | 549 | if (rtl_dump_file) |
550 | fprintf (rtl_dump_file, "Emitting return\n"); | |
66d9dc73 | 551 | #else |
552 | abort (); | |
553 | #endif | |
a6540cbf | 554 | } |
075d20cf | 555 | |
556 | return jump; | |
a6540cbf | 557 | } |
558 | ||
559 | ||
075d20cf | 560 | /* Given a reorder chain, rearrange the code to match. */ |
a6540cbf | 561 | |
562 | static void | |
563 | fixup_reorder_chain () | |
564 | { | |
075d20cf | 565 | basic_block bb, last_bb; |
a6540cbf | 566 | |
075d20cf | 567 | /* First do the bulk reordering -- rechain the blocks without regard to |
568 | the needed changes to jumps and labels. */ | |
569 | ||
570 | last_bb = BASIC_BLOCK (0); | |
571 | bb = RBI (last_bb)->next; | |
572 | while (bb) | |
a6540cbf | 573 | { |
075d20cf | 574 | rtx last_e = RBI (last_bb)->eff_end; |
575 | rtx curr_h = RBI (bb)->eff_head; | |
a6540cbf | 576 | |
075d20cf | 577 | NEXT_INSN (last_e) = curr_h; |
578 | PREV_INSN (curr_h) = last_e; | |
afe4711a | 579 | |
075d20cf | 580 | last_bb = bb; |
581 | bb = RBI (bb)->next; | |
582 | } | |
583 | NEXT_INSN (RBI (last_bb)->eff_end) = NULL_RTX; | |
584 | set_last_insn (RBI (last_bb)->eff_end); | |
585 | ||
586 | /* Now add jumps and labels as needed to match the blocks new | |
587 | outgoing edges. */ | |
588 | ||
589 | for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next) | |
590 | { | |
591 | edge e_fall, e_taken, e; | |
b2929403 | 592 | rtx jump_insn, barrier_insn, bb_end_insn; |
075d20cf | 593 | basic_block nb; |
594 | ||
595 | if (bb->succ == NULL) | |
596 | continue; | |
597 | ||
598 | /* Find the old fallthru edge, and another non-EH edge for | |
599 | a taken jump. */ | |
600 | e_taken = e_fall = NULL; | |
601 | for (e = bb->succ; e ; e = e->succ_next) | |
602 | if (e->flags & EDGE_FALLTHRU) | |
603 | e_fall = e; | |
604 | else if (! (e->flags & EDGE_EH)) | |
605 | e_taken = e; | |
606 | ||
b2929403 | 607 | bb_end_insn = bb->end; |
608 | if (GET_CODE (bb_end_insn) == JUMP_INSN) | |
075d20cf | 609 | { |
b2929403 | 610 | if (any_uncondjump_p (bb_end_insn)) |
afe4711a | 611 | { |
075d20cf | 612 | /* If the destination is still not next, nothing to do. */ |
613 | if (RBI (bb)->index + 1 != RBI (e_taken->dest)->index) | |
614 | continue; | |
615 | ||
616 | /* Otherwise, we can remove the jump and cleanup the edge. */ | |
617 | tidy_fallthru_edge (e_taken, bb, e_taken->dest); | |
618 | RBI (bb)->eff_end = skip_insns_after_block (bb); | |
619 | RBI (e_taken->dest)->eff_head = NEXT_INSN (RBI (bb)->eff_end); | |
620 | ||
621 | if (rtl_dump_file) | |
622 | fprintf (rtl_dump_file, "Removing jump in block %d (%d)\n", | |
623 | bb->index, RBI (bb)->index); | |
624 | continue; | |
afe4711a | 625 | } |
b2929403 | 626 | else if (any_condjump_p (bb_end_insn)) |
afe4711a | 627 | { |
075d20cf | 628 | /* If the old fallthru is still next, nothing to do. */ |
629 | if (RBI (bb)->index + 1 == RBI (e_fall->dest)->index | |
630 | || (RBI (bb)->index == n_basic_blocks - 1 | |
631 | && e_fall->dest == EXIT_BLOCK_PTR)) | |
632 | continue; | |
633 | ||
634 | /* There is one special case: if *neither* block is next, | |
635 | such as happens at the very end of a function, then we'll | |
636 | need to add a new unconditional jump. Choose the taken | |
637 | edge based on known or assumed probability. */ | |
638 | if (RBI (bb)->index + 1 != RBI (e_taken->dest)->index) | |
639 | { | |
b2929403 | 640 | rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0); |
075d20cf | 641 | if (note |
642 | && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2 | |
b2929403 | 643 | && invert_jump (bb_end_insn, |
644 | label_for_bb (e_fall->dest), 0)) | |
075d20cf | 645 | { |
646 | e_fall->flags &= ~EDGE_FALLTHRU; | |
647 | e_taken->flags |= EDGE_FALLTHRU; | |
648 | e = e_fall, e_fall = e_taken, e_taken = e; | |
649 | } | |
650 | } | |
afe4711a | 651 | |
075d20cf | 652 | /* Otherwise we can try to invert the jump. This will |
653 | basically never fail, however, keep up the pretense. */ | |
b2929403 | 654 | else if (invert_jump (bb_end_insn, |
655 | label_for_bb (e_fall->dest), 0)) | |
a6540cbf | 656 | { |
075d20cf | 657 | e_fall->flags &= ~EDGE_FALLTHRU; |
658 | e_taken->flags |= EDGE_FALLTHRU; | |
659 | continue; | |
a6540cbf | 660 | } |
661 | } | |
b2929403 | 662 | else if (returnjump_p (bb_end_insn)) |
075d20cf | 663 | continue; |
a8edab65 | 664 | else |
075d20cf | 665 | { |
666 | /* Otherwise we have some switch or computed jump. In the | |
667 | 99% case, there should not have been a fallthru edge. */ | |
668 | if (! e_fall) | |
669 | continue; | |
670 | #ifdef CASE_DROPS_THROUGH | |
671 | /* Except for VAX. Since we didn't have predication for the | |
672 | tablejump, the fallthru block should not have moved. */ | |
673 | if (RBI (bb)->index + 1 == RBI (e_fall->dest)->index) | |
674 | continue; | |
b2929403 | 675 | bb_end_insn = skip_insns_after_block (bb); |
676 | #else | |
075d20cf | 677 | abort (); |
b2929403 | 678 | #endif |
075d20cf | 679 | } |
a6540cbf | 680 | } |
075d20cf | 681 | else |
682 | { | |
683 | /* No fallthru implies a noreturn function with EH edges, or | |
684 | something similarly bizarre. In any case, we don't need to | |
685 | do anything. */ | |
686 | if (! e_fall) | |
687 | continue; | |
688 | ||
689 | /* If the fallthru block is still next, nothing to do. */ | |
690 | if (RBI (bb)->index + 1 == RBI (e_fall->dest)->index | |
691 | || (RBI (bb)->index == n_basic_blocks - 1 | |
692 | && e_fall->dest == EXIT_BLOCK_PTR)) | |
693 | continue; | |
694 | ||
695 | /* We need a new jump insn. If the block has only one outgoing | |
696 | edge, then we can stuff the new jump insn in directly. */ | |
697 | if (bb->succ->succ_next == NULL) | |
698 | { | |
699 | e_fall->flags &= ~EDGE_FALLTHRU; | |
700 | ||
b2929403 | 701 | jump_insn = emit_jump_to_block_after (e_fall->dest, bb_end_insn); |
075d20cf | 702 | bb->end = jump_insn; |
703 | barrier_insn = emit_barrier_after (jump_insn); | |
704 | RBI (bb)->eff_end = barrier_insn; | |
705 | continue; | |
706 | } | |
707 | } | |
708 | ||
709 | /* We got here if we need to add a new jump insn in a new block | |
710 | across the edge e_fall. */ | |
711 | ||
b2929403 | 712 | jump_insn = emit_jump_to_block_after (e_fall->dest, bb_end_insn); |
075d20cf | 713 | barrier_insn = emit_barrier_after (jump_insn); |
714 | ||
715 | VARRAY_GROW (basic_block_info, ++n_basic_blocks); | |
716 | create_basic_block (n_basic_blocks - 1, jump_insn, jump_insn, NULL); | |
717 | ||
718 | nb = BASIC_BLOCK (n_basic_blocks - 1); | |
d7c47c0e | 719 | nb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack); |
720 | nb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack); | |
075d20cf | 721 | nb->local_set = 0; |
eb429644 | 722 | nb->count = e_fall->count; |
723 | nb->frequency = EDGE_FREQUENCY (e_fall); | |
075d20cf | 724 | |
725 | COPY_REG_SET (nb->global_live_at_start, bb->global_live_at_start); | |
726 | COPY_REG_SET (nb->global_live_at_end, bb->global_live_at_start); | |
727 | ||
728 | nb->aux = xmalloc (sizeof (struct reorder_block_def)); | |
729 | RBI (nb)->eff_head = nb->head; | |
730 | RBI (nb)->eff_end = barrier_insn; | |
731 | RBI (nb)->scope = RBI (bb)->scope; | |
732 | RBI (nb)->index = RBI (bb)->index + 1; | |
733 | RBI (nb)->visited = 1; | |
734 | RBI (nb)->next = RBI (bb)->next; | |
735 | RBI (bb)->next = nb; | |
736 | ||
737 | /* Link to new block. */ | |
738 | make_edge (NULL, nb, e_fall->dest, 0); | |
739 | redirect_edge_succ (e_fall, nb); | |
eb429644 | 740 | nb->succ->count = e_fall->count; |
741 | nb->succ->probability = REG_BR_PROB_BASE; | |
075d20cf | 742 | |
743 | /* Don't process this new block. */ | |
744 | bb = nb; | |
745 | ||
746 | /* Fix subsequent reorder block indices to reflect new block. */ | |
747 | while ((nb = RBI (nb)->next) != NULL) | |
748 | RBI (nb)->index += 1; | |
749 | } | |
750 | ||
751 | /* Put basic_block_info in the new order. */ | |
752 | for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next) | |
753 | { | |
754 | bb->index = RBI (bb)->index; | |
755 | BASIC_BLOCK (bb->index) = bb; | |
a6540cbf | 756 | } |
757 | } | |
758 | ||
759 | ||
afe4711a | 760 | /* Perform sanity checks on the insn chain. |
761 | 1. Check that next/prev pointers are consistent in both the forward and | |
762 | reverse direction. | |
763 | 2. Count insns in chain, going both directions, and check if equal. | |
764 | 3. Check that get_last_insn () returns the actual end of chain. */ | |
075d20cf | 765 | |
766 | void | |
afe4711a | 767 | verify_insn_chain () |
768 | { | |
769 | rtx x, | |
770 | prevx, | |
771 | nextx; | |
772 | int insn_cnt1, | |
773 | insn_cnt2; | |
774 | ||
775 | prevx = NULL; | |
776 | insn_cnt1 = 1; | |
777 | for (x = get_insns (); x; x = NEXT_INSN (x)) | |
778 | { | |
779 | if (PREV_INSN (x) != prevx) | |
780 | { | |
781 | fprintf (stderr, "Forward traversal: insn chain corrupt.\n"); | |
782 | fprintf (stderr, "previous insn:\n"); | |
783 | debug_rtx (prevx); | |
784 | fprintf (stderr, "current insn:\n"); | |
785 | debug_rtx (x); | |
786 | abort (); | |
787 | } | |
788 | ++insn_cnt1; | |
789 | prevx = x; | |
790 | } | |
791 | ||
792 | if (prevx != get_last_insn ()) | |
793 | { | |
794 | fprintf (stderr, "last_insn corrupt.\n"); | |
795 | abort (); | |
796 | } | |
797 | ||
798 | nextx = NULL; | |
799 | insn_cnt2 = 1; | |
800 | for (x = get_last_insn (); x; x = PREV_INSN (x)) | |
801 | { | |
802 | if (NEXT_INSN (x) != nextx) | |
803 | { | |
804 | fprintf (stderr, "Reverse traversal: insn chain corrupt.\n"); | |
805 | fprintf (stderr, "current insn:\n"); | |
806 | debug_rtx (x); | |
807 | fprintf (stderr, "next insn:\n"); | |
808 | debug_rtx (nextx); | |
809 | abort (); | |
810 | } | |
811 | ++insn_cnt2; | |
812 | nextx = x; | |
813 | } | |
814 | ||
815 | if (insn_cnt1 != insn_cnt2) | |
816 | { | |
817 | fprintf (stderr, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n", | |
818 | insn_cnt1, insn_cnt2); | |
819 | abort (); | |
820 | } | |
821 | } | |
afe4711a | 822 | |
a8edab65 | 823 | static rtx |
824 | get_next_bb_note (x) | |
825 | rtx x; | |
826 | { | |
827 | while (x) | |
828 | { | |
83458610 | 829 | if (NOTE_INSN_BASIC_BLOCK_P (x)) |
a8edab65 | 830 | return x; |
831 | x = NEXT_INSN (x); | |
832 | } | |
833 | return NULL; | |
834 | } | |
835 | ||
836 | ||
837 | static rtx | |
838 | get_prev_bb_note (x) | |
839 | rtx x; | |
840 | { | |
841 | while (x) | |
842 | { | |
83458610 | 843 | if (NOTE_INSN_BASIC_BLOCK_P (x)) |
a8edab65 | 844 | return x; |
845 | x = PREV_INSN (x); | |
846 | } | |
847 | return NULL; | |
848 | } | |
849 | ||
850 | ||
851 | /* Determine and record the relationships between basic blocks and | |
852 | scopes in scope tree S. */ | |
853 | ||
854 | static void | |
855 | relate_bbs_with_scopes (s) | |
856 | scope s; | |
857 | { | |
858 | scope p; | |
859 | int i, bbi1, bbi2, bbs_spanned; | |
860 | rtx bbnote; | |
861 | ||
862 | for (p = s->inner; p; p = p->next) | |
863 | relate_bbs_with_scopes (p); | |
864 | ||
865 | bbi1 = bbi2 = -1; | |
866 | bbs_spanned = 0; | |
867 | ||
868 | /* If the begin and end notes are both inside the same basic block, | |
869 | or if they are both outside of basic blocks, then we know immediately | |
870 | how they are related. Otherwise, we need to poke around to make the | |
871 | determination. */ | |
872 | if (s->bb_beg != s->bb_end) | |
873 | { | |
874 | if (s->bb_beg && s->bb_end) | |
875 | { | |
876 | /* Both notes are in different bbs. This implies that all the | |
877 | basic blocks spanned by the pair of notes are contained in | |
878 | this scope. */ | |
879 | bbi1 = s->bb_beg->index; | |
880 | bbi2 = s->bb_end->index; | |
881 | bbs_spanned = 1; | |
882 | } | |
883 | else if (! s->bb_beg) | |
884 | { | |
885 | /* First note is outside of a bb. If the scope spans more than | |
886 | one basic block, then they all are contained within this | |
887 | scope. Otherwise, this scope is contained within the basic | |
888 | block. */ | |
889 | bbnote = get_next_bb_note (s->note_beg); | |
890 | if (! bbnote) | |
891 | abort (); | |
892 | if (NOTE_BASIC_BLOCK (bbnote) == s->bb_end) | |
893 | { | |
894 | bbs_spanned = 0; | |
895 | s->bb_beg = NOTE_BASIC_BLOCK (bbnote); | |
896 | } | |
897 | else | |
898 | { | |
899 | bbi1 = NOTE_BASIC_BLOCK (bbnote)->index; | |
900 | bbi2 = s->bb_end->index; | |
901 | s->bb_end = NULL; | |
902 | bbs_spanned = 1; | |
903 | } | |
904 | } | |
905 | else /* ! s->bb_end */ | |
906 | { | |
907 | /* Second note is outside of a bb. If the scope spans more than | |
908 | one basic block, then they all are contained within this | |
909 | scope. Otherwise, this scope is contained within the basic | |
910 | block. */ | |
911 | bbnote = get_prev_bb_note (s->note_end); | |
912 | if (! bbnote) | |
913 | abort (); | |
914 | if (NOTE_BASIC_BLOCK (bbnote) == s->bb_beg) | |
915 | { | |
916 | bbs_spanned = 0; | |
917 | s->bb_end = NOTE_BASIC_BLOCK (bbnote); | |
918 | } | |
919 | else | |
920 | { | |
921 | bbi1 = s->bb_beg->index; | |
922 | bbi2 = NOTE_BASIC_BLOCK (bbnote)->index; | |
923 | s->bb_beg = NULL; | |
924 | bbs_spanned = 1; | |
925 | } | |
926 | } | |
927 | } | |
928 | else | |
929 | { | |
930 | if (s->bb_beg) | |
931 | /* Both notes are in the same bb, which implies the block | |
932 | contains this scope. */ | |
933 | bbs_spanned = 0; | |
934 | else | |
935 | { | |
936 | rtx x1, x2; | |
937 | /* Both notes are outside of any bbs. This implies that all the | |
938 | basic blocks spanned by the pair of notes are contained in | |
939 | this scope. | |
940 | There is a degenerate case to consider. If the notes do not | |
941 | span any basic blocks, then it is an empty scope that can | |
942 | safely be deleted or ignored. Mark these with level = -1. */ | |
943 | ||
944 | x1 = get_next_bb_note (s->note_beg); | |
945 | x2 = get_prev_bb_note (s->note_end); | |
946 | if (! (x1 && x2)) | |
947 | { | |
948 | s->level = -1; | |
949 | bbs_spanned = 0; | |
950 | } | |
951 | else | |
952 | { | |
953 | bbi1 = NOTE_BASIC_BLOCK (x1)->index; | |
954 | bbi2 = NOTE_BASIC_BLOCK (x2)->index; | |
955 | bbs_spanned = 1; | |
956 | } | |
957 | } | |
958 | } | |
959 | ||
a8edab65 | 960 | /* If the scope spans one or more basic blocks, we record them. We |
961 | only record the bbs that are immediately contained within this | |
962 | scope. Note that if a scope is contained within a bb, we can tell | |
963 | by checking that bb_beg = bb_end and that they are non-null. */ | |
964 | if (bbs_spanned) | |
965 | { | |
966 | int j = 0; | |
967 | ||
968 | s->num_bbs = 0; | |
969 | for (i = bbi1; i <= bbi2; i++) | |
075d20cf | 970 | if (! RBI (BASIC_BLOCK (i))->scope) |
a8edab65 | 971 | s->num_bbs++; |
972 | ||
075d20cf | 973 | s->bbs = xmalloc (s->num_bbs * sizeof (basic_block)); |
a8edab65 | 974 | for (i = bbi1; i <= bbi2; i++) |
975 | { | |
976 | basic_block curr_bb = BASIC_BLOCK (i); | |
075d20cf | 977 | if (! RBI (curr_bb)->scope) |
a8edab65 | 978 | { |
979 | s->bbs[j++] = curr_bb; | |
075d20cf | 980 | RBI (curr_bb)->scope = s; |
a8edab65 | 981 | } |
982 | } | |
983 | } | |
984 | else | |
985 | s->num_bbs = 0; | |
986 | } | |
987 | ||
988 | ||
989 | /* Allocate and initialize a new scope structure with scope level LEVEL, | |
990 | and record the NOTE beginning the scope. */ | |
991 | ||
992 | static scope | |
993 | make_new_scope (level, note) | |
994 | int level; | |
995 | rtx note; | |
996 | { | |
997 | scope new_scope = xcalloc (1, sizeof (struct scope_def)); | |
998 | new_scope->level = level; | |
999 | new_scope->note_beg = note; | |
a8edab65 | 1000 | return new_scope; |
1001 | } | |
1002 | ||
1003 | ||
1004 | /* Build a forest representing the scope structure of the function. | |
1005 | Return a pointer to a structure describing the forest. */ | |
1006 | ||
1007 | static void | |
1008 | build_scope_forest (forest) | |
1009 | scope_forest_info *forest; | |
1010 | { | |
1011 | rtx x; | |
1012 | int level, bbi, i; | |
1013 | basic_block curr_bb; | |
9a5bbcc2 | 1014 | scope root, curr_scope = 0; |
a8edab65 | 1015 | |
1016 | forest->num_trees = 0; | |
1017 | forest->trees = NULL; | |
1018 | level = -1; | |
1019 | root = NULL; | |
1020 | curr_bb = NULL; | |
1021 | bbi = 0; | |
1022 | for (x = get_insns (); x; x = NEXT_INSN (x)) | |
1023 | { | |
1024 | if (bbi < n_basic_blocks && x == BASIC_BLOCK (bbi)->head) | |
1025 | curr_bb = BASIC_BLOCK (bbi); | |
1026 | ||
1027 | if (GET_CODE (x) == NOTE) | |
1028 | { | |
1029 | if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG) | |
1030 | { | |
1031 | if (root) | |
1032 | { | |
1033 | scope new_scope; | |
1034 | if (! curr_scope) | |
1035 | abort(); | |
1036 | level++; | |
1037 | new_scope = make_new_scope (level, x); | |
1038 | new_scope->outer = curr_scope; | |
1039 | new_scope->next = NULL; | |
1040 | if (! curr_scope->inner) | |
1041 | { | |
1042 | curr_scope->inner = new_scope; | |
1043 | curr_scope->inner_last = new_scope; | |
1044 | } | |
1045 | else | |
1046 | { | |
1047 | curr_scope->inner_last->next = new_scope; | |
1048 | curr_scope->inner_last = new_scope; | |
1049 | } | |
1050 | curr_scope = curr_scope->inner_last; | |
1051 | } | |
1052 | else | |
1053 | { | |
1054 | int ntrees = forest->num_trees; | |
1055 | level++; | |
1056 | curr_scope = make_new_scope (level, x); | |
1057 | root = curr_scope; | |
075d20cf | 1058 | forest->trees = xrealloc (forest->trees, |
1059 | sizeof (scope) * (ntrees + 1)); | |
a8edab65 | 1060 | forest->trees[forest->num_trees++] = root; |
1061 | } | |
1062 | curr_scope->bb_beg = curr_bb; | |
1063 | } | |
1064 | else if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END) | |
1065 | { | |
1066 | curr_scope->bb_end = curr_bb; | |
1067 | curr_scope->note_end = x; | |
1068 | level--; | |
1069 | curr_scope = curr_scope->outer; | |
1070 | if (level == -1) | |
1071 | root = NULL; | |
1072 | } | |
1073 | } /* if note */ | |
1074 | ||
1075 | if (curr_bb && curr_bb->end == x) | |
1076 | { | |
1077 | curr_bb = NULL; | |
1078 | bbi++; | |
1079 | } | |
1080 | ||
1081 | } /* for */ | |
1082 | ||
1083 | for (i = 0; i < forest->num_trees; i++) | |
1084 | relate_bbs_with_scopes (forest->trees[i]); | |
1085 | } | |
1086 | ||
1087 | ||
1088 | /* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from | |
1089 | the insn chain. */ | |
1090 | ||
1091 | static void | |
1092 | remove_scope_notes () | |
1093 | { | |
1094 | rtx x, next; | |
1095 | basic_block currbb = NULL; | |
1096 | ||
1097 | for (x = get_insns (); x; x = next) | |
1098 | { | |
1099 | next = NEXT_INSN (x); | |
83458610 | 1100 | if (NOTE_INSN_BASIC_BLOCK_P (x)) |
a8edab65 | 1101 | currbb = NOTE_BASIC_BLOCK (x); |
1102 | ||
1103 | if (GET_CODE (x) == NOTE | |
1104 | && (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG | |
1105 | || NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END)) | |
1106 | { | |
6521ac3d | 1107 | /* Check if the scope note happens to be the end of a bb. */ |
1108 | if (currbb && x == currbb->end) | |
a8edab65 | 1109 | currbb->end = PREV_INSN (x); |
6521ac3d | 1110 | if (currbb && x == currbb->head) |
1111 | abort (); | |
a8edab65 | 1112 | |
1113 | if (PREV_INSN (x)) | |
1114 | { | |
1115 | NEXT_INSN (PREV_INSN (x)) = next; | |
1116 | PREV_INSN (next) = PREV_INSN (x); | |
1117 | ||
1118 | NEXT_INSN (x) = NULL; | |
1119 | PREV_INSN (x) = NULL; | |
1120 | } | |
1121 | else | |
1122 | abort (); | |
1123 | } | |
1124 | } | |
1125 | } | |
1126 | ||
1127 | ||
1128 | /* Insert scope note pairs for a contained scope tree S after insn IP. */ | |
075d20cf | 1129 | |
a8edab65 | 1130 | static void |
1131 | insert_intra_1 (s, ip) | |
1132 | scope s; | |
1133 | rtx *ip; | |
1134 | { | |
1135 | scope p; | |
1136 | ||
1137 | if (NOTE_BLOCK (s->note_beg)) | |
1138 | { | |
1139 | *ip = emit_note_after (NOTE_INSN_BLOCK_BEG, *ip); | |
1140 | NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg); | |
1141 | } | |
1142 | ||
1143 | for (p = s->inner; p; p = p->next) | |
1144 | insert_intra_1 (p, ip); | |
1145 | ||
1146 | if (NOTE_BLOCK (s->note_beg)) | |
1147 | { | |
1148 | *ip = emit_note_after (NOTE_INSN_BLOCK_END, *ip); | |
1149 | NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end); | |
1150 | } | |
1151 | } | |
1152 | ||
1153 | ||
1154 | /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for | |
1155 | scopes that are contained within BB. */ | |
1156 | ||
1157 | static void | |
1158 | insert_intra_bb_scope_notes (bb) | |
1159 | basic_block bb; | |
1160 | { | |
075d20cf | 1161 | scope s = RBI (bb)->scope; |
a8edab65 | 1162 | scope p; |
1163 | rtx ip; | |
1164 | ||
1165 | if (! s) | |
1166 | return; | |
1167 | ||
1168 | ip = bb->head; | |
1169 | if (GET_CODE (ip) == CODE_LABEL) | |
1170 | ip = NEXT_INSN (ip); | |
1171 | ||
1172 | for (p = s->inner; p; p = p->next) | |
1173 | { | |
1174 | if (p->bb_beg != NULL && p->bb_beg == p->bb_end && p->bb_beg == bb) | |
1175 | insert_intra_1 (p, &ip); | |
1176 | } | |
1177 | } | |
1178 | ||
1179 | ||
1180 | /* Given two consecutive basic blocks BB1 and BB2 with different scopes, | |
1181 | insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG | |
1182 | notes before BB2 such that the notes are correctly balanced. If BB1 or | |
1183 | BB2 is NULL, we are inserting scope notes for the first and last basic | |
1184 | blocks, respectively. */ | |
1185 | ||
1186 | static void | |
1187 | insert_inter_bb_scope_notes (bb1, bb2) | |
1188 | basic_block bb1; | |
1189 | basic_block bb2; | |
1190 | { | |
1191 | rtx ip; | |
1192 | scope com; | |
1193 | ||
1194 | /* It is possible that a basic block is not contained in any scope. | |
1195 | In that case, we either open or close a scope but not both. */ | |
1196 | if (bb1 && bb2) | |
1197 | { | |
075d20cf | 1198 | scope s1 = RBI (bb1)->scope; |
1199 | scope s2 = RBI (bb2)->scope; | |
a8edab65 | 1200 | if (! s1 && ! s2) |
1201 | return; | |
1202 | if (! s1) | |
1203 | bb1 = NULL; | |
1204 | else if (! s2) | |
1205 | bb2 = NULL; | |
1206 | } | |
1207 | ||
1208 | /* Find common ancestor scope. */ | |
1209 | if (bb1 && bb2) | |
1210 | { | |
075d20cf | 1211 | scope s1 = RBI (bb1)->scope; |
1212 | scope s2 = RBI (bb2)->scope; | |
a8edab65 | 1213 | while (s1 != s2) |
1214 | { | |
1215 | if (! (s1 && s2)) | |
1216 | abort (); | |
1217 | if (s1->level > s2->level) | |
1218 | s1 = s1->outer; | |
1219 | else if (s2->level > s1->level) | |
1220 | s2 = s2->outer; | |
1221 | else | |
1222 | { | |
1223 | s1 = s1->outer; | |
1224 | s2 = s2->outer; | |
1225 | } | |
1226 | } | |
1227 | com = s1; | |
1228 | } | |
1229 | else | |
1230 | com = NULL; | |
1231 | ||
1232 | /* Close scopes. */ | |
1233 | if (bb1) | |
1234 | { | |
075d20cf | 1235 | scope s = RBI (bb1)->scope; |
1236 | ip = RBI (bb1)->eff_end; | |
a8edab65 | 1237 | while (s != com) |
1238 | { | |
1239 | if (NOTE_BLOCK (s->note_beg)) | |
1240 | { | |
1241 | ip = emit_note_after (NOTE_INSN_BLOCK_END, ip); | |
1242 | NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_end); | |
1243 | } | |
1244 | s = s->outer; | |
1245 | } | |
1246 | } | |
1247 | ||
1248 | /* Open scopes. */ | |
1249 | if (bb2) | |
1250 | { | |
075d20cf | 1251 | scope s = RBI (bb2)->scope; |
a8edab65 | 1252 | ip = bb2->head; |
1253 | while (s != com) | |
1254 | { | |
1255 | if (NOTE_BLOCK (s->note_beg)) | |
1256 | { | |
1257 | ip = emit_note_before (NOTE_INSN_BLOCK_BEG, ip); | |
1258 | NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_beg); | |
1259 | } | |
1260 | s = s->outer; | |
1261 | } | |
1262 | } | |
1263 | } | |
1264 | ||
1265 | ||
1266 | /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based | |
1267 | on the scope forest and the newly reordered basic blocks. */ | |
1268 | ||
1269 | static void | |
1270 | rebuild_scope_notes (forest) | |
1271 | scope_forest_info *forest; | |
1272 | { | |
1273 | int i; | |
1274 | ||
1275 | if (forest->num_trees == 0) | |
1276 | return; | |
1277 | ||
1278 | /* Start by opening the scopes before the first basic block. */ | |
1279 | insert_inter_bb_scope_notes (NULL, BASIC_BLOCK (0)); | |
1280 | ||
1281 | /* Then, open and close scopes as needed between blocks. */ | |
1282 | for (i = 0; i < n_basic_blocks - 1; i++) | |
1283 | { | |
1284 | basic_block bb1 = BASIC_BLOCK (i); | |
1285 | basic_block bb2 = BASIC_BLOCK (i + 1); | |
075d20cf | 1286 | if (RBI (bb1)->scope != RBI (bb2)->scope) |
a8edab65 | 1287 | insert_inter_bb_scope_notes (bb1, bb2); |
1288 | insert_intra_bb_scope_notes (bb1); | |
1289 | } | |
1290 | ||
1291 | /* Finally, close the scopes after the last basic block. */ | |
1292 | insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1), NULL); | |
1293 | insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1)); | |
1294 | } | |
1295 | ||
1296 | ||
1297 | /* Free the storage associated with the scope tree at S. */ | |
1298 | ||
1299 | static void | |
1300 | free_scope_forest_1 (s) | |
1301 | scope s; | |
1302 | { | |
1303 | scope p, next; | |
1304 | ||
1305 | for (p = s->inner; p; p = next) | |
1306 | { | |
1307 | next = p->next; | |
1308 | free_scope_forest_1 (p); | |
1309 | } | |
1310 | ||
1311 | if (s->bbs) | |
1312 | free (s->bbs); | |
1313 | free (s); | |
1314 | } | |
1315 | ||
1316 | ||
1317 | /* Free the storage associated with the scope forest. */ | |
1318 | ||
1319 | static void | |
1320 | free_scope_forest (forest) | |
1321 | scope_forest_info *forest; | |
1322 | { | |
1323 | int i; | |
1324 | for (i = 0; i < forest->num_trees; i++) | |
1325 | free_scope_forest_1 (forest->trees[i]); | |
1326 | } | |
1327 | ||
1328 | ||
1329 | /* Visualize the scope forest. */ | |
1330 | ||
1331 | void | |
1332 | dump_scope_forest (forest) | |
1333 | scope_forest_info *forest; | |
1334 | { | |
1335 | if (forest->num_trees == 0) | |
1336 | fprintf (stderr, "\n< Empty scope forest >\n"); | |
1337 | else | |
1338 | { | |
1339 | int i; | |
1340 | fprintf (stderr, "\n< Scope forest >\n"); | |
1341 | for (i = 0; i < forest->num_trees; i++) | |
1342 | dump_scope_forest_1 (forest->trees[i], 0); | |
1343 | } | |
1344 | } | |
1345 | ||
1346 | ||
1347 | /* Recursive portion of dump_scope_forest. */ | |
1348 | ||
1349 | static void | |
1350 | dump_scope_forest_1 (s, indent) | |
1351 | scope s; | |
1352 | int indent; | |
1353 | { | |
1354 | scope p; | |
1355 | int i; | |
1356 | ||
1357 | if (s->bb_beg != NULL && s->bb_beg == s->bb_end | |
075d20cf | 1358 | && RBI (s->bb_beg)->scope |
1359 | && RBI (s->bb_beg)->scope->level + 1 == s->level) | |
a8edab65 | 1360 | { |
1361 | fprintf (stderr, "%*s", indent, ""); | |
1362 | fprintf (stderr, "BB%d:\n", s->bb_beg->index); | |
1363 | } | |
1364 | ||
1365 | fprintf (stderr, "%*s", indent, ""); | |
1366 | fprintf (stderr, "{ level %d (block %p)\n", s->level, | |
f8cb9479 | 1367 | (PTR) NOTE_BLOCK (s->note_beg)); |
a8edab65 | 1368 | |
1369 | fprintf (stderr, "%*s%s", indent, "", "bbs:"); | |
1370 | for (i = 0; i < s->num_bbs; i++) | |
1371 | fprintf (stderr, " %d", s->bbs[i]->index); | |
1372 | fprintf (stderr, "\n"); | |
1373 | ||
1374 | for (p = s->inner; p; p = p->next) | |
1375 | dump_scope_forest_1 (p, indent + 2); | |
1376 | ||
1377 | fprintf (stderr, "%*s", indent, ""); | |
1378 | fprintf (stderr, "}\n"); | |
1379 | } | |
1380 | ||
1381 | ||
075d20cf | 1382 | /* Reorder basic blocks. The main entry point to this file. */ |
a6540cbf | 1383 | |
1384 | void | |
1385 | reorder_basic_blocks () | |
1386 | { | |
a8edab65 | 1387 | scope_forest_info forest; |
075d20cf | 1388 | int i; |
a6540cbf | 1389 | |
1390 | if (n_basic_blocks <= 1) | |
1391 | return; | |
1392 | ||
a6540cbf | 1393 | for (i = 0; i < n_basic_blocks; i++) |
075d20cf | 1394 | BASIC_BLOCK (i)->aux = xcalloc (1, sizeof (struct reorder_block_def)); |
a8edab65 | 1395 | |
d4e8df9e | 1396 | EXIT_BLOCK_PTR->aux = xcalloc (1, sizeof (struct reorder_block_def)); |
1397 | ||
a8edab65 | 1398 | build_scope_forest (&forest); |
1399 | remove_scope_notes (); | |
1400 | ||
075d20cf | 1401 | record_effective_endpoints (); |
1402 | make_reorder_chain (); | |
a6540cbf | 1403 | fixup_reorder_chain (); |
1404 | ||
1405 | #ifdef ENABLE_CHECKING | |
afe4711a | 1406 | verify_insn_chain (); |
a6540cbf | 1407 | #endif |
1408 | ||
a8edab65 | 1409 | rebuild_scope_notes (&forest); |
1410 | free_scope_forest (&forest); | |
1411 | reorder_blocks (); | |
1412 | ||
a6540cbf | 1413 | for (i = 0; i < n_basic_blocks; i++) |
1414 | free (BASIC_BLOCK (i)->aux); | |
1415 | ||
d4e8df9e | 1416 | free (EXIT_BLOCK_PTR->aux); |
1417 | ||
075d20cf | 1418 | #ifdef ENABLE_CHECKING |
1419 | verify_flow_info (); | |
1420 | #endif | |
a6540cbf | 1421 | } |