]> gcc.gnu.org Git - gcc.git/blame - gcc/cfglayout.c
delete some extraneous characters accidentally included in last change.
[gcc.git] / gcc / cfglayout.c
CommitLineData
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 4This file is part of GCC.
d56a8211 5
5f0d2358
RK
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 2, or (at your option) any later
9version.
d56a8211 10
5f0d2358
RK
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
d56a8211 15
5f0d2358
RK
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING. If not, write to the Free
18Software Foundation, 59 Temple Place - Suite 330, Boston, MA
1902111-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
41extern struct obstack flow_obstack;
42
bc35512f
JH
43alloc_pool cfg_layout_pool;
44
d56a8211 45/* Holds the interesting trailing notes for the function. */
bc35512f 46rtx cfg_layout_function_footer, cfg_layout_function_header;
d56a8211 47
d329e058
AJ
48static rtx skip_insns_after_block (basic_block);
49static void record_effective_endpoints (void);
50static rtx label_for_bb (basic_block);
51static void fixup_reorder_chain (void);
d56a8211 52
d329e058
AJ
53static void set_block_levels (tree, int);
54static void change_scope (rtx, tree, tree);
d56a8211 55
d329e058 56void verify_insn_chain (void);
d329e058
AJ
57static void fixup_fallthru_exit_predecessor (void);
58static rtx duplicate_insn_chain (rtx, rtx);
d329e058 59static tree insn_scope (rtx);
d56a8211 60\f
9ee634e3 61rtx
d329e058 62unlink_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
84static rtx
d329e058 85skip_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
171static rtx
d329e058 172label_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
190static void
d329e058 191record_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. */
237static GTY(()) varray_type block_locators_locs;
238static GTY(()) varray_type block_locators_blocks;
239static GTY(()) varray_type line_locators_locs;
240static GTY(()) varray_type line_locators_lines;
241static GTY(()) varray_type file_locators_locs;
242static GTY(()) varray_type file_locators_files;
243int prologue_locator;
244int 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 250void
d329e058 251insn_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
340static void
d329e058 341set_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. */
352tree
d329e058 353choose_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
366static void
d329e058 367change_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. */
410static tree
d329e058 411insn_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 450int
9ae130f8 451locator_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. */
477int
478insn_line (rtx insn)
479{
480 return locator_line (INSN_LOCATOR (insn));
481}
482
483/* Return source file of the statement specified by LOC. */
0435312e 484const char *
9ae130f8 485locator_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. */
511const char *
512insn_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
520void
d329e058 521reemit_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
566static void
d329e058 567fixup_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
829void
d329e058 830verify_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 856static void
d329e058 857fixup_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
884bool
d329e058 885cfg_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
921static rtx
d329e058 922duplicate_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
1016basic_block
d329e058 1017cfg_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 1113void
7e51717c 1114cfg_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
1125void
7e51717c 1126cfg_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 1146void
d329e058 1147break_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
1176void
d329e058 1177cfg_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. */
1204bool
1205can_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
1232end:
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
1254void
1255copy_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"
This page took 0.710361 seconds and 5 git commands to generate.