1/* Perform instruction reorganizations for delay slot filling. 2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 4 Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu). 5 Hacked by Michael Tiemann (tiemann@cygnus.com). 6 7This file is part of GCC. 8 9GCC is free software; you can redistribute it and/or modify it under 10the terms of the GNU General Public License as published by the Free 11Software Foundation; either version 2, or (at your option) any later 12version. 13 14GCC is distributed in the hope that it will be useful, but WITHOUT ANY 15WARRANTY; without even the implied warranty of MERCHANTABILITY or 16FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17for more details. 18 19You should have received a copy of the GNU General Public License 20along with GCC; see the file COPYING. If not, write to the Free 21Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2202110-1301, USA. */ 23 24/* Instruction reorganization pass. 25 26 This pass runs after register allocation and final jump 27 optimization. It should be the last pass to run before peephole. 28 It serves primarily to fill delay slots of insns, typically branch 29 and call insns. Other insns typically involve more complicated 30 interactions of data dependencies and resource constraints, and 31 are better handled by scheduling before register allocation (by the 32 function `schedule_insns'). 33 34 The Branch Penalty is the number of extra cycles that are needed to 35 execute a branch insn. On an ideal machine, branches take a single 36 cycle, and the Branch Penalty is 0. Several RISC machines approach 37 branch delays differently: 38 39 The MIPS has a single branch delay slot. Most insns 40 (except other branches) can be used to fill this slot. When the 41 slot is filled, two insns execute in two cycles, reducing the 42 branch penalty to zero. 43 44 The SPARC always has a branch delay slot, but its effects can be 45 annulled when the branch is not taken. This means that failing to 46 find other sources of insns, we can hoist an insn from the branch 47 target that would only be safe to execute knowing that the branch 48 is taken. 49 50 The HP-PA always has a branch delay slot. For unconditional branches 51 its effects can be annulled when the branch is taken. The effects 52 of the delay slot in a conditional branch can be nullified for forward 53 taken branches, or for untaken backward branches. This means 54 we can hoist insns from the fall-through path for forward branches or 55 steal insns from the target of backward branches. 56 57 The TMS320C3x and C4x have three branch delay slots. When the three 58 slots are filled, the branch penalty is zero. Most insns can fill the 59 delay slots except jump insns. 60 61 Three techniques for filling delay slots have been implemented so far: 62 63 (1) `fill_simple_delay_slots' is the simplest, most efficient way 64 to fill delay slots. This pass first looks for insns which come 65 from before the branch and which are safe to execute after the 66 branch. Then it searches after the insn requiring delay slots or, 67 in the case of a branch, for insns that are after the point at 68 which the branch merges into the fallthrough code, if such a point 69 exists. When such insns are found, the branch penalty decreases 70 and no code expansion takes place. 71 72 (2) `fill_eager_delay_slots' is more complicated: it is used for 73 scheduling conditional jumps, or for scheduling jumps which cannot 74 be filled using (1). A machine need not have annulled jumps to use 75 this strategy, but it helps (by keeping more options open). 76 `fill_eager_delay_slots' tries to guess the direction the branch 77 will go; if it guesses right 100% of the time, it can reduce the 78 branch penalty as much as `fill_simple_delay_slots' does. If it 79 guesses wrong 100% of the time, it might as well schedule nops. When 80 `fill_eager_delay_slots' takes insns from the fall-through path of 81 the jump, usually there is no code expansion; when it takes insns 82 from the branch target, there is code expansion if it is not the 83 only way to reach that target. 84 85 (3) `relax_delay_slots' uses a set of rules to simplify code that 86 has been reorganized by (1) and (2). It finds cases where 87 conditional test can be eliminated, jumps can be threaded, extra 88 insns can be eliminated, etc. It is the job of (1) and (2) to do a 89 good job of scheduling locally; `relax_delay_slots' takes care of 90 making the various individual schedules work well together. It is 91 especially tuned to handle the control flow interactions of branch 92 insns. It does nothing for insns with delay slots that do not 93 branch. 94 95 On machines that use CC0, we are very conservative. We will not make 96 a copy of an insn involving CC0 since we want to maintain a 1-1 97 correspondence between the insn that sets and uses CC0. The insns are 98 allowed to be separated by placing an insn that sets CC0 (but not an insn 99 that uses CC0; we could do this, but it doesn't seem worthwhile) in a 100 delay slot. In that case, we point each insn at the other with REG_CC_USER 101 and REG_CC_SETTER notes. Note that these restrictions affect very few 102 machines because most RISC machines with delay slots will not use CC0 103 (the RT is the only known exception at this point). 104 105 Not yet implemented: 106 107 The Acorn Risc Machine can conditionally execute most insns, so 108 it is profitable to move single insns into a position to execute 109 based on the condition code of the previous insn. 110 111 The HP-PA can conditionally nullify insns, providing a similar 112 effect to the ARM, differing mostly in which insn is "in charge". */ 113 114#include "config.h" 115#include "system.h" 116#include "coretypes.h" 117#include "tm.h" 118#include "toplev.h" 119#include "rtl.h" 120#include "tm_p.h" 121#include "expr.h" 122#include "function.h" 123#include "insn-config.h" 124#include "conditions.h" 125#include "hard-reg-set.h" 126#include "basic-block.h" 127#include "regs.h" 128#include "recog.h" 129#include "flags.h" 130#include "output.h" 131#include "obstack.h" 132#include "insn-attr.h" 133#include "resource.h" 134#include "except.h" 135#include "params.h" 136#include "timevar.h" 137#include "target.h" 138#include "tree-pass.h" 139 140#ifdef DELAY_SLOTS 141 142#ifndef ANNUL_IFTRUE_SLOTS 143#define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0 144#endif 145#ifndef ANNUL_IFFALSE_SLOTS 146#define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0 147#endif 148 149/* Insns which have delay slots that have not yet been filled. */ 150 151static struct obstack unfilled_slots_obstack; 152static rtx *unfilled_firstobj; 153 154/* Define macros to refer to the first and last slot containing unfilled 155 insns. These are used because the list may move and its address 156 should be recomputed at each use. */ 157 158#define unfilled_slots_base \ 159 ((rtx *) obstack_base (&unfilled_slots_obstack)) 160 161#define unfilled_slots_next \ 162 ((rtx *) obstack_next_free (&unfilled_slots_obstack)) 163 164/* Points to the label before the end of the function. */ 165static rtx end_of_function_label; 166 167/* Mapping between INSN_UID's and position in the code since INSN_UID's do 168 not always monotonically increase. */ 169static int *uid_to_ruid; 170 171/* Highest valid index in `uid_to_ruid'. */ 172static int max_uid; 173 174static int stop_search_p (rtx, int); 175static int resource_conflicts_p (struct resources *, struct resources *); 176static int insn_references_resource_p (rtx, struct resources *, int); 177static int insn_sets_resource_p (rtx, struct resources *, int); 178static rtx find_end_label (void); 179static rtx emit_delay_sequence (rtx, rtx, int); 180static rtx add_to_delay_list (rtx, rtx); 181static rtx delete_from_delay_slot (rtx); 182static void delete_scheduled_jump (rtx); 183static void note_delay_statistics (int, int); 184#if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS) 185static rtx optimize_skip (rtx); 186#endif 187static int get_jump_flags (rtx, rtx); 188static int rare_destination (rtx); 189static int mostly_true_jump (rtx, rtx); 190static rtx get_branch_condition (rtx, rtx); 191static int condition_dominates_p (rtx, rtx); 192static int redirect_with_delay_slots_safe_p (rtx, rtx, rtx); 193static int redirect_with_delay_list_safe_p (rtx, rtx, rtx); 194static int check_annul_list_true_false (int, rtx); 195static rtx steal_delay_list_from_target (rtx, rtx, rtx, rtx, 196 struct resources *, 197 struct resources *, 198 struct resources *, 199 int, int *, int *, rtx *); 200static rtx steal_delay_list_from_fallthrough (rtx, rtx, rtx, rtx, 201 struct resources *, 202 struct resources *, 203 struct resources *, 204 int, int *, int *); 205static void try_merge_delay_insns (rtx, rtx); 206static rtx redundant_insn (rtx, rtx, rtx); 207static int own_thread_p (rtx, rtx, int); 208static void update_block (rtx, rtx); 209static int reorg_redirect_jump (rtx, rtx); 210static void update_reg_dead_notes (rtx, rtx); 211static void fix_reg_dead_note (rtx, rtx); 212static void update_reg_unused_notes (rtx, rtx); 213static void fill_simple_delay_slots (int); 214static rtx fill_slots_from_thread (rtx, rtx, rtx, rtx, int, int, int, int, 215 int *, rtx); 216static void fill_eager_delay_slots (void); 217static void relax_delay_slots (rtx); 218#ifdef HAVE_return 219static void make_return_insns (rtx); 220#endif 221 222/* Return TRUE if this insn should stop the search for insn to fill delay 223 slots. LABELS_P indicates that labels should terminate the search. 224 In all cases, jumps terminate the search. */ 225 226static int 227stop_search_p (rtx insn, int labels_p) 228{ 229 if (insn == 0) 230 return 1; 231 232 /* If the insn can throw an exception that is caught within the function, 233 it may effectively perform a jump from the viewpoint of the function. 234 Therefore act like for a jump. */ 235 if (can_throw_internal (insn)) 236 return 1; 237 238 switch (GET_CODE (insn)) 239 { 240 case NOTE: 241 case CALL_INSN: 242 return 0; 243 244 case CODE_LABEL: 245 return labels_p; 246 247 case JUMP_INSN: 248 case BARRIER: 249 return 1; 250 251 case INSN: 252 /* OK unless it contains a delay slot or is an `asm' insn of some type. 253 We don't know anything about these. */ 254 return (GET_CODE (PATTERN (insn)) == SEQUENCE 255 || GET_CODE (PATTERN (insn)) == ASM_INPUT 256 || asm_noperands (PATTERN (insn)) >= 0); 257 258 default: 259 gcc_unreachable (); 260 } 261} 262 263/* Return TRUE if any resources are marked in both RES1 and RES2 or if either 264 resource set contains a volatile memory reference. Otherwise, return FALSE. */ 265 266static int 267resource_conflicts_p (struct resources *res1, struct resources *res2) 268{ 269 if ((res1->cc && res2->cc) || (res1->memory && res2->memory) 270 || (res1->unch_memory && res2->unch_memory) 271 || res1->volatil || res2->volatil) 272 return 1; 273 274#ifdef HARD_REG_SET 275 return (res1->regs & res2->regs) != HARD_CONST (0); 276#else 277 { 278 int i; 279 280 for (i = 0; i < HARD_REG_SET_LONGS; i++) 281 if ((res1->regs[i] & res2->regs[i]) != 0) 282 return 1; 283 return 0; 284 } 285#endif 286} 287 288/* Return TRUE if any resource marked in RES, a `struct resources', is 289 referenced by INSN. If INCLUDE_DELAYED_EFFECTS is set, return if the called 290 routine is using those resources. 291 292 We compute this by computing all the resources referenced by INSN and 293 seeing if this conflicts with RES. It might be faster to directly check 294 ourselves, and this is the way it used to work, but it means duplicating 295 a large block of complex code. */ 296 297static int 298insn_references_resource_p (rtx insn, struct resources *res, 299 int include_delayed_effects) 300{ 301 struct resources insn_res; 302 303 CLEAR_RESOURCE (&insn_res); 304 mark_referenced_resources (insn, &insn_res, include_delayed_effects); 305 return resource_conflicts_p (&insn_res, res); 306} 307 308/* Return TRUE if INSN modifies resources that are marked in RES. 309 INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be 310 included. CC0 is only modified if it is explicitly set; see comments 311 in front of mark_set_resources for details. */ 312 313static int 314insn_sets_resource_p (rtx insn, struct resources *res, 315 int include_delayed_effects) 316{ 317 struct resources insn_sets; 318 319 CLEAR_RESOURCE (&insn_sets); 320 mark_set_resources (insn, &insn_sets, 0, include_delayed_effects); 321 return resource_conflicts_p (&insn_sets, res); 322} 323 324/* Find a label at the end of the function or before a RETURN. If there 325 is none, try to make one. If that fails, returns 0. 326 327 The property of such a label is that it is placed just before the 328 epilogue or a bare RETURN insn, so that another bare RETURN can be 329 turned into a jump to the label unconditionally. In particular, the 330 label cannot be placed before a RETURN insn with a filled delay slot. 331 332 ??? There may be a problem with the current implementation. Suppose 333 we start with a bare RETURN insn and call find_end_label. It may set 334 end_of_function_label just before the RETURN. Suppose the machinery 335 is able to fill the delay slot of the RETURN insn afterwards. Then 336 end_of_function_label is no longer valid according to the property 337 described above and find_end_label will still return it unmodified. 338 Note that this is probably mitigated by the following observation: 339 once end_of_function_label is made, it is very likely the target of 340 a jump, so filling the delay slot of the RETURN will be much more 341 difficult. */ 342 343static rtx 344find_end_label (void) 345{ 346 rtx insn; 347 348 /* If we found one previously, return it. */ 349 if (end_of_function_label) 350 return end_of_function_label; 351 352 /* Otherwise, see if there is a label at the end of the function. If there 353 is, it must be that RETURN insns aren't needed, so that is our return 354 label and we don't have to do anything else. */ 355 356 insn = get_last_insn (); 357 while (NOTE_P (insn) 358 || (NONJUMP_INSN_P (insn) 359 && (GET_CODE (PATTERN (insn)) == USE 360 || GET_CODE (PATTERN (insn)) == CLOBBER))) 361 insn = PREV_INSN (insn); 362 363 /* When a target threads its epilogue we might already have a 364 suitable return insn. If so put a label before it for the 365 end_of_function_label. */ 366 if (BARRIER_P (insn) 367 && JUMP_P (PREV_INSN (insn)) 368 && GET_CODE (PATTERN (PREV_INSN (insn))) == RETURN) 369 { 370 rtx temp = PREV_INSN (PREV_INSN (insn)); 371 end_of_function_label = gen_label_rtx (); 372 LABEL_NUSES (end_of_function_label) = 0; 373 374 /* Put the label before an USE insns that may precede the RETURN insn. */ 375 while (GET_CODE (temp) == USE) 376 temp = PREV_INSN (temp); 377 378 emit_label_after (end_of_function_label, temp); 379 } 380 381 else if (LABEL_P (insn)) 382 end_of_function_label = insn; 383 else 384 { 385 end_of_function_label = gen_label_rtx (); 386 LABEL_NUSES (end_of_function_label) = 0; 387 /* If the basic block reorder pass moves the return insn to 388 some other place try to locate it again and put our 389 end_of_function_label there. */ 390 while (insn && ! (JUMP_P (insn) 391 && (GET_CODE (PATTERN (insn)) == RETURN))) 392 insn = PREV_INSN (insn); 393 if (insn) 394 { 395 insn = PREV_INSN (insn); 396 397 /* Put the label before an USE insns that may proceed the 398 RETURN insn. */ 399 while (GET_CODE (insn) == USE) 400 insn = PREV_INSN (insn); 401 402 emit_label_after (end_of_function_label, insn); 403 } 404 else 405 { 406#ifdef HAVE_epilogue 407 if (HAVE_epilogue 408#ifdef HAVE_return 409 && ! HAVE_return 410#endif 411 ) 412 { 413 /* The RETURN insn has its delay slot filled so we cannot 414 emit the label just before it. Since we already have 415 an epilogue and cannot emit a new RETURN, we cannot 416 emit the label at all. */ 417 end_of_function_label = NULL_RTX; 418 return end_of_function_label; 419 } 420#endif /* HAVE_epilogue */ 421 422 /* Otherwise, make a new label and emit a RETURN and BARRIER, 423 if needed. */ 424 emit_label (end_of_function_label); 425#ifdef HAVE_return 426 /* We don't bother trying to create a return insn if the 427 epilogue has filled delay-slots; we would have to try and 428 move the delay-slot fillers to the delay-slots for the new 429 return insn or in front of the new return insn. */ 430 if (current_function_epilogue_delay_list == NULL 431 && HAVE_return) 432 { 433 /* The return we make may have delay slots too. */ 434 rtx insn = gen_return (); 435 insn = emit_jump_insn (insn); 436 emit_barrier (); 437 if (num_delay_slots (insn) > 0) 438 obstack_ptr_grow (&unfilled_slots_obstack, insn); 439 } 440#endif 441 } 442 } 443 444 /* Show one additional use for this label so it won't go away until 445 we are done. */ 446 ++LABEL_NUSES (end_of_function_label); 447 448 return end_of_function_label; 449} 450 451/* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace 452 the pattern of INSN with the SEQUENCE. 453 454 Chain the insns so that NEXT_INSN of each insn in the sequence points to 455 the next and NEXT_INSN of the last insn in the sequence points to 456 the first insn after the sequence. Similarly for PREV_INSN. This makes 457 it easier to scan all insns. 458 459 Returns the SEQUENCE that replaces INSN. */ 460 461static rtx 462emit_delay_sequence (rtx insn, rtx list, int length) 463{ 464 int i = 1; 465 rtx li; 466 int had_barrier = 0; 467 468 /* Allocate the rtvec to hold the insns and the SEQUENCE. */ 469 rtvec seqv = rtvec_alloc (length + 1); 470 rtx seq = gen_rtx_SEQUENCE (VOIDmode, seqv); 471 rtx seq_insn = make_insn_raw (seq); 472 rtx first = get_insns (); 473 rtx last = get_last_insn (); 474 475 /* Make a copy of the insn having delay slots. */ 476 rtx delay_insn = copy_rtx (insn); 477 478 /* If INSN is followed by a BARRIER, delete the BARRIER since it will only 479 confuse further processing. Update LAST in case it was the last insn. 480 We will put the BARRIER back in later. */ 481 if (NEXT_INSN (insn) && BARRIER_P (NEXT_INSN (insn))) 482 { 483 delete_related_insns (NEXT_INSN (insn)); 484 last = get_last_insn (); 485 had_barrier = 1; 486 } 487 488 /* Splice our SEQUENCE into the insn stream where INSN used to be. */ 489 NEXT_INSN (seq_insn) = NEXT_INSN (insn); 490 PREV_INSN (seq_insn) = PREV_INSN (insn); 491 492 if (insn != last) 493 PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn; 494 495 if (insn != first) 496 NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn; 497 498 /* Note the calls to set_new_first_and_last_insn must occur after 499 SEQ_INSN has been completely spliced into the insn stream. 500 501 Otherwise CUR_INSN_UID will get set to an incorrect value because 502 set_new_first_and_last_insn will not find SEQ_INSN in the chain. */ 503 if (insn == last) 504 set_new_first_and_last_insn (first, seq_insn); 505 506 if (insn == first) 507 set_new_first_and_last_insn (seq_insn, last); 508 509 /* Build our SEQUENCE and rebuild the insn chain. */ 510 XVECEXP (seq, 0, 0) = delay_insn; 511 INSN_DELETED_P (delay_insn) = 0; 512 PREV_INSN (delay_insn) = PREV_INSN (seq_insn); 513 514 for (li = list; li; li = XEXP (li, 1), i++) 515 { 516 rtx tem = XEXP (li, 0); 517 rtx note, next; 518 519 /* Show that this copy of the insn isn't deleted. */ 520 INSN_DELETED_P (tem) = 0; 521 522 XVECEXP (seq, 0, i) = tem; 523 PREV_INSN (tem) = XVECEXP (seq, 0, i - 1); 524 NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem; 525 526 /* SPARC assembler, for instance, emit warning when debug info is output 527 into the delay slot. */ 528 if (INSN_LOCATOR (tem) && !INSN_LOCATOR (seq_insn)) 529 INSN_LOCATOR (seq_insn) = INSN_LOCATOR (tem); 530 INSN_LOCATOR (tem) = 0; 531 532 for (note = REG_NOTES (tem); note; note = next) 533 { 534 next = XEXP (note, 1); 535 switch (REG_NOTE_KIND (note)) 536 { 537 case REG_DEAD: 538 /* Remove any REG_DEAD notes because we can't rely on them now 539 that the insn has been moved. */ 540 remove_note (tem, note); 541 break; 542 543 case REG_LABEL: 544 /* Keep the label reference count up to date. */ 545 if (LABEL_P (XEXP (note, 0))) 546 LABEL_NUSES (XEXP (note, 0)) ++; 547 break; 548 549 default: 550 break; 551 } 552 } 553 } 554 555 NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn); 556 557 /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the 558 last insn in that SEQUENCE to point to us. Similarly for the first 559 insn in the following insn if it is a SEQUENCE. */ 560 561 if (PREV_INSN (seq_insn) && NONJUMP_INSN_P (PREV_INSN (seq_insn)) 562 && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE) 563 NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0, 564 XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1)) 565 = seq_insn; 566 567 if (NEXT_INSN (seq_insn) && NONJUMP_INSN_P (NEXT_INSN (seq_insn)) 568 && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE) 569 PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn; 570 571 /* If there used to be a BARRIER, put it back. */ 572 if (had_barrier) 573 emit_barrier_after (seq_insn); 574 575 gcc_assert (i == length + 1); 576 577 return seq_insn; 578} 579 580/* Add INSN to DELAY_LIST and return the head of the new list. The list must 581 be in the order in which the insns are to be executed. */ 582 583static rtx 584add_to_delay_list (rtx insn, rtx delay_list) 585{ 586 /* If we have an empty list, just make a new list element. If 587 INSN has its block number recorded, clear it since we may 588 be moving the insn to a new block. */ 589 590 if (delay_list == 0) 591 { 592 clear_hashed_info_for_insn (insn); 593 return gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX); 594 } 595 596 /* Otherwise this must be an INSN_LIST. Add INSN to the end of the 597 list. */ 598 XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1)); 599 600 return delay_list; 601} 602 603/* Delete INSN from the delay slot of the insn that it is in, which may 604 produce an insn with no delay slots. Return the new insn. */ 605 606static rtx 607delete_from_delay_slot (rtx insn) 608{ 609 rtx trial, seq_insn, seq, prev; 610 rtx delay_list = 0; 611 int i; 612 int had_barrier = 0; 613 614 /* We first must find the insn containing the SEQUENCE with INSN in its 615 delay slot. Do this by finding an insn, TRIAL, where 616 PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */ 617 618 for (trial = insn; 619 PREV_INSN (NEXT_INSN (trial)) == trial; 620 trial = NEXT_INSN (trial)) 621 ; 622 623 seq_insn = PREV_INSN (NEXT_INSN (trial)); 624 seq = PATTERN (seq_insn); 625 626 if (NEXT_INSN (seq_insn) && BARRIER_P (NEXT_INSN (seq_insn))) 627 had_barrier = 1; 628 629 /* Create a delay list consisting of all the insns other than the one 630 we are deleting (unless we were the only one). */ 631 if (XVECLEN (seq, 0) > 2) 632 for (i = 1; i < XVECLEN (seq, 0); i++) 633 if (XVECEXP (seq, 0, i) != insn) 634 delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list); 635 636 /* Delete the old SEQUENCE, re-emit the insn that used to have the delay 637 list, and rebuild the delay list if non-empty. */ 638 prev = PREV_INSN (seq_insn); 639 trial = XVECEXP (seq, 0, 0); 640 delete_related_insns (seq_insn); 641 add_insn_after (trial, prev); 642 643 /* If there was a barrier after the old SEQUENCE, remit it. */ 644 if (had_barrier) 645 emit_barrier_after (trial); 646 647 /* If there are any delay insns, remit them. Otherwise clear the 648 annul flag. */ 649 if (delay_list) 650 trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2); 651 else if (INSN_P (trial)) 652 INSN_ANNULLED_BRANCH_P (trial) = 0; 653 654 INSN_FROM_TARGET_P (insn) = 0; 655 656 /* Show we need to fill this insn again. */ 657 obstack_ptr_grow (&unfilled_slots_obstack, trial); 658 659 return trial; 660} 661 662/* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down 663 the insn that sets CC0 for it and delete it too. */ 664 665static void 666delete_scheduled_jump (rtx insn) 667{ 668 /* Delete the insn that sets cc0 for us. On machines without cc0, we could 669 delete the insn that sets the condition code, but it is hard to find it. 670 Since this case is rare anyway, don't bother trying; there would likely 671 be other insns that became dead anyway, which we wouldn't know to 672 delete. */ 673 674#ifdef HAVE_cc0 675 if (reg_mentioned_p (cc0_rtx, insn)) 676 { 677 rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX); 678 679 /* If a reg-note was found, it points to an insn to set CC0. This 680 insn is in the delay list of some other insn. So delete it from 681 the delay list it was in. */ 682 if (note) 683 { 684 if (! FIND_REG_INC_NOTE (XEXP (note, 0), NULL_RTX) 685 && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1) 686 delete_from_delay_slot (XEXP (note, 0)); 687 } 688 else 689 { 690 /* The insn setting CC0 is our previous insn, but it may be in 691 a delay slot. It will be the last insn in the delay slot, if 692 it is. */ 693 rtx trial = previous_insn (insn); 694 if (NOTE_P (trial)) 695 trial = prev_nonnote_insn (trial); 696 if (sets_cc0_p (PATTERN (trial)) != 1 697 || FIND_REG_INC_NOTE (trial, NULL_RTX)) 698 return; 699 if (PREV_INSN (NEXT_INSN (trial)) == trial) 700 delete_related_insns (trial); 701 else 702 delete_from_delay_slot (trial); 703 } 704 } 705#endif 706 707 delete_related_insns (insn); 708} 709 710/* Counters for delay-slot filling. */ 711 712#define NUM_REORG_FUNCTIONS 2 713#define MAX_DELAY_HISTOGRAM 3 714#define MAX_REORG_PASSES 2 715 716static int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES]; 717 718static int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES]; 719 720static int reorg_pass_number; 721 722static void 723note_delay_statistics (int slots_filled, int index) 724{ 725 num_insns_needing_delays[index][reorg_pass_number]++; 726 if (slots_filled > MAX_DELAY_HISTOGRAM) 727 slots_filled = MAX_DELAY_HISTOGRAM; 728 num_filled_delays[index][slots_filled][reorg_pass_number]++; 729} 730 731#if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS) 732 733/* Optimize the following cases: 734 735 1. When a conditional branch skips over only one instruction, 736 use an annulling branch and put that insn in the delay slot. 737 Use either a branch that annuls when the condition if true or 738 invert the test with a branch that annuls when the condition is 739 false. This saves insns, since otherwise we must copy an insn 740 from the L1 target. 741 742 (orig) (skip) (otherwise) 743 Bcc.n L1 Bcc',a L1 Bcc,a L1' 744 insn insn insn2 745 L1: L1: L1: 746 insn2 insn2 insn2 747 insn3 insn3 L1': 748 insn3 749 750 2. When a conditional branch skips over only one instruction, 751 and after that, it unconditionally branches somewhere else, 752 perform the similar optimization. This saves executing the 753 second branch in the case where the inverted condition is true. 754 755 Bcc.n L1 Bcc',a L2 756 insn insn 757 L1: L1: 758 Bra L2 Bra L2 759 760 INSN is a JUMP_INSN. 761 762 This should be expanded to skip over N insns, where N is the number 763 of delay slots required. */ 764 765static rtx 766optimize_skip (rtx insn) 767{ 768 rtx trial = next_nonnote_insn (insn); 769 rtx next_trial = next_active_insn (trial); 770 rtx delay_list = 0; 771 int flags; 772 773 flags = get_jump_flags (insn, JUMP_LABEL (insn)); 774 775 if (trial == 0 776 || !NONJUMP_INSN_P (trial) 777 || GET_CODE (PATTERN (trial)) == SEQUENCE 778 || recog_memoized (trial) < 0 779 || (! eligible_for_annul_false (insn, 0, trial, flags) 780 && ! eligible_for_annul_true (insn, 0, trial, flags)) 781 || can_throw_internal (trial)) 782 return 0; 783 784 /* There are two cases where we are just executing one insn (we assume 785 here that a branch requires only one insn; this should be generalized 786 at some point): Where the branch goes around a single insn or where 787 we have one insn followed by a branch to the same label we branch to. 788 In both of these cases, inverting the jump and annulling the delay 789 slot give the same effect in fewer insns. */ 790 if ((next_trial == next_active_insn (JUMP_LABEL (insn)) 791 && ! (next_trial == 0 && current_function_epilogue_delay_list != 0)) 792 || (next_trial != 0 793 && JUMP_P (next_trial) 794 && JUMP_LABEL (insn) == JUMP_LABEL (next_trial) 795 && (simplejump_p (next_trial) 796 || GET_CODE (PATTERN (next_trial)) == RETURN))) 797 { 798 if (eligible_for_annul_false (insn, 0, trial, flags)) 799 { 800 if (invert_jump (insn, JUMP_LABEL (insn), 1)) 801 INSN_FROM_TARGET_P (trial) = 1; 802 else if (! eligible_for_annul_true (insn, 0, trial, flags)) 803 return 0; 804 } 805 806 delay_list = add_to_delay_list (trial, NULL_RTX); 807 next_trial = next_active_insn (trial); 808 update_block (trial, trial); 809 delete_related_insns (trial); 810 811 /* Also, if we are targeting an unconditional 812 branch, thread our jump to the target of that branch. Don't 813 change this into a RETURN here, because it may not accept what 814 we have in the delay slot. We'll fix this up later. */ 815 if (next_trial && JUMP_P (next_trial) 816 && (simplejump_p (next_trial) 817 || GET_CODE (PATTERN (next_trial)) == RETURN)) 818 { 819 rtx target_label = JUMP_LABEL (next_trial); 820 if (target_label == 0) 821 target_label = find_end_label (); 822 823 if (target_label) 824 { 825 /* Recompute the flags based on TARGET_LABEL since threading 826 the jump to TARGET_LABEL may change the direction of the 827 jump (which may change the circumstances in which the 828 delay slot is nullified). */ 829 flags = get_jump_flags (insn, target_label); 830 if (eligible_for_annul_true (insn, 0, trial, flags)) 831 reorg_redirect_jump (insn, target_label); 832 } 833 } 834 835 INSN_ANNULLED_BRANCH_P (insn) = 1; 836 } 837 838 return delay_list; 839} 840#endif 841 842/* Encode and return branch direction and prediction information for 843 INSN assuming it will jump to LABEL. 844 845 Non conditional branches return no direction information and 846 are predicted as very likely taken. */ 847 848static int 849get_jump_flags (rtx insn, rtx label) 850{ 851 int flags; 852 853 /* get_jump_flags can be passed any insn with delay slots, these may 854 be INSNs, CALL_INSNs, or JUMP_INSNs. Only JUMP_INSNs have branch 855 direction information, and only if they are conditional jumps. 856 857 If LABEL is zero, then there is no way to determine the branch 858 direction. */ 859 if (JUMP_P (insn) 860 && (condjump_p (insn) || condjump_in_parallel_p (insn)) 861 && INSN_UID (insn) <= max_uid 862 && label != 0 863 && INSN_UID (label) <= max_uid) 864 flags 865 = (uid_to_ruid[INSN_UID (label)] > uid_to_ruid[INSN_UID (insn)]) 866 ? ATTR_FLAG_forward : ATTR_FLAG_backward; 867 /* No valid direction information. */ 868 else 869 flags = 0; 870 871 /* If insn is a conditional branch call mostly_true_jump to get 872 determine the branch prediction. 873 874 Non conditional branches are predicted as very likely taken. */ 875 if (JUMP_P (insn) 876 && (condjump_p (insn) || condjump_in_parallel_p (insn))) 877 { 878 int prediction; 879 880 prediction = mostly_true_jump (insn, get_branch_condition (insn, label)); 881 switch (prediction) 882 { 883 case 2: 884 flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely); 885 break; 886 case 1: 887 flags |= ATTR_FLAG_likely; 888 break; 889 case 0: 890 flags |= ATTR_FLAG_unlikely; 891 break; 892 case -1: 893 flags |= (ATTR_FLAG_very_unlikely | ATTR_FLAG_unlikely); 894 break; 895 896 default: 897 gcc_unreachable (); 898 } 899 } 900 else 901 flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely); 902 903 return flags; 904} 905 906/* Return 1 if INSN is a destination that will be branched to rarely (the 907 return point of a function); return 2 if DEST will be branched to very 908 rarely (a call to a function that doesn't return). Otherwise, 909 return 0. */ 910 911static int 912rare_destination (rtx insn) 913{ 914 int jump_count = 0; 915 rtx next; 916 917 for (; insn; insn = next) 918 { 919 if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == SEQUENCE) 920 insn = XVECEXP (PATTERN (insn), 0, 0); 921 922 next = NEXT_INSN (insn); 923 924 switch (GET_CODE (insn)) 925 { 926 case CODE_LABEL: 927 return 0; 928 case BARRIER: 929 /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN. We 930 don't scan past JUMP_INSNs, so any barrier we find here must 931 have been after a CALL_INSN and hence mean the call doesn't 932 return. */ 933 return 2; 934 case JUMP_INSN: 935 if (GET_CODE (PATTERN (insn)) == RETURN) 936 return 1; 937 else if (simplejump_p (insn) 938 && jump_count++ < 10) 939 next = JUMP_LABEL (insn); 940 else 941 return 0; 942 943 default: 944 break; 945 } 946 } 947 948 /* If we got here it means we hit the end of the function. So this 949 is an unlikely destination. */ 950 951 return 1; 952} 953 954/* Return truth value of the statement that this branch 955 is mostly taken. If we think that the branch is extremely likely 956 to be taken, we return 2. If the branch is slightly more likely to be 957 taken, return 1. If the branch is slightly less likely to be taken, 958 return 0 and if the branch is highly unlikely to be taken, return -1. 959 960 CONDITION, if nonzero, is the condition that JUMP_INSN is testing. */ 961 962static int 963mostly_true_jump (rtx jump_insn, rtx condition) 964{ 965 rtx target_label = JUMP_LABEL (jump_insn); 966 rtx insn, note; 967 int rare_dest = rare_destination (target_label); 968 int rare_fallthrough = rare_destination (NEXT_INSN (jump_insn)); 969 970 /* If branch probabilities are available, then use that number since it 971 always gives a correct answer. */ 972 note = find_reg_note (jump_insn, REG_BR_PROB, 0); 973 if (note) 974 { 975 int prob = INTVAL (XEXP (note, 0)); 976 977 if (prob >= REG_BR_PROB_BASE * 9 / 10) 978 return 2; 979 else if (prob >= REG_BR_PROB_BASE / 2) 980 return 1; 981 else if (prob >= REG_BR_PROB_BASE / 10) 982 return 0; 983 else 984 return -1; 985 } 986 987 /* ??? Ought to use estimate_probability instead. */ 988 989 /* If this is a branch outside a loop, it is highly unlikely. */ 990 if (GET_CODE (PATTERN (jump_insn)) == SET 991 && GET_CODE (SET_SRC (PATTERN (jump_insn))) == IF_THEN_ELSE 992 && ((GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 1)) == LABEL_REF 993 && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 1))) 994 || (GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 2)) == LABEL_REF 995 && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 2))))) 996 return -1; 997 998 if (target_label) 999 { 1000 /* If this is the test of a loop, it is very likely true. We scan 1001 backwards from the target label. If we find a NOTE_INSN_LOOP_BEG 1002 before the next real insn, we assume the branch is to the top of 1003 the loop. */ 1004 for (insn = PREV_INSN (target_label); 1005 insn && NOTE_P (insn); 1006 insn = PREV_INSN (insn)) 1007 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 1008 return 2; 1009 } 1010 1011 /* Look at the relative rarities of the fallthrough and destination. If 1012 they differ, we can predict the branch that way. */ 1013 1014 switch (rare_fallthrough - rare_dest) 1015 { 1016 case -2: 1017 return -1; 1018 case -1: 1019 return 0; 1020 case 0: 1021 break; 1022 case 1: 1023 return 1; 1024 case 2: 1025 return 2; 1026 } 1027 1028 /* If we couldn't figure out what this jump was, assume it won't be 1029 taken. This should be rare. */ 1030 if (condition == 0) 1031 return 0; 1032 1033 /* EQ tests are usually false and NE tests are usually true. Also, 1034 most quantities are positive, so we can make the appropriate guesses 1035 about signed comparisons against zero. */ 1036 switch (GET_CODE (condition)) 1037 { 1038 case CONST_INT: 1039 /* Unconditional branch. */ 1040 return 1; 1041 case EQ: 1042 return 0; 1043 case NE: 1044 return 1; 1045 case LE: 1046 case LT: 1047 if (XEXP (condition, 1) == const0_rtx) 1048 return 0; 1049 break; 1050 case GE: 1051 case GT: 1052 if (XEXP (condition, 1) == const0_rtx) 1053 return 1; 1054 break; 1055 1056 default: 1057 break; 1058 } 1059 1060 /* Predict backward branches usually take, forward branches usually not. If 1061 we don't know whether this is forward or backward, assume the branch 1062 will be taken, since most are. */ 1063 return (target_label == 0 || INSN_UID (jump_insn) > max_uid 1064 || INSN_UID (target_label) > max_uid 1065 || (uid_to_ruid[INSN_UID (jump_insn)] 1066 > uid_to_ruid[INSN_UID (target_label)])); 1067} 1068 1069/* Return the condition under which INSN will branch to TARGET. If TARGET 1070 is zero, return the condition under which INSN will return. If INSN is 1071 an unconditional branch, return const_true_rtx. If INSN isn't a simple 1072 type of jump, or it doesn't go to TARGET, return 0. */ 1073 1074static rtx 1075get_branch_condition (rtx insn, rtx target) 1076{ 1077 rtx pat = PATTERN (insn); 1078 rtx src; 1079 1080 if (condjump_in_parallel_p (insn)) 1081 pat = XVECEXP (pat, 0, 0); 1082 1083 if (GET_CODE (pat) == RETURN) 1084 return target == 0 ? const_true_rtx : 0; 1085 1086 else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx) 1087 return 0; 1088 1089 src = SET_SRC (pat); 1090 if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target) 1091 return const_true_rtx; 1092 1093 else if (GET_CODE (src) == IF_THEN_ELSE 1094 && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN) 1095 || (GET_CODE (XEXP (src, 1)) == LABEL_REF 1096 && XEXP (XEXP (src, 1), 0) == target)) 1097 && XEXP (src, 2) == pc_rtx) 1098 return XEXP (src, 0); 1099 1100 else if (GET_CODE (src) == IF_THEN_ELSE 1101 && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN) 1102 || (GET_CODE (XEXP (src, 2)) == LABEL_REF 1103 && XEXP (XEXP (src, 2), 0) == target)) 1104 && XEXP (src, 1) == pc_rtx) 1105 { 1106 enum rtx_code rev; 1107 rev = reversed_comparison_code (XEXP (src, 0), insn); 1108 if (rev != UNKNOWN) 1109 return gen_rtx_fmt_ee (rev, GET_MODE (XEXP (src, 0)), 1110 XEXP (XEXP (src, 0), 0), 1111 XEXP (XEXP (src, 0), 1)); 1112 } 1113 1114 return 0; 1115} 1116 1117/* Return nonzero if CONDITION is more strict than the condition of 1118 INSN, i.e., if INSN will always branch if CONDITION is true. */ 1119 1120static int 1121condition_dominates_p (rtx condition, rtx insn) 1122{ 1123 rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn)); 1124 enum rtx_code code = GET_CODE (condition); 1125 enum rtx_code other_code; 1126 1127 if (rtx_equal_p (condition, other_condition) 1128 || other_condition == const_true_rtx) 1129 return 1; 1130 1131 else if (condition == const_true_rtx || other_condition == 0) 1132 return 0; 1133 1134 other_code = GET_CODE (other_condition); 1135 if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2 1136 || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0)) 1137 || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1))) 1138 return 0; 1139 1140 return comparison_dominates_p (code, other_code); 1141} 1142 1143/* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate 1144 any insns already in the delay slot of JUMP. */ 1145 1146static int 1147redirect_with_delay_slots_safe_p (rtx jump, rtx newlabel, rtx seq) 1148{ 1149 int flags, i; 1150 rtx pat = PATTERN (seq); 1151 1152 /* Make sure all the delay slots of this jump would still 1153 be valid after threading the jump. If they are still 1154 valid, then return nonzero. */ 1155 1156 flags = get_jump_flags (jump, newlabel); 1157 for (i = 1; i < XVECLEN (pat, 0); i++) 1158 if (! ( 1159#ifdef ANNUL_IFFALSE_SLOTS 1160 (INSN_ANNULLED_BRANCH_P (jump) 1161 && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i))) 1162 ? eligible_for_annul_false (jump, i - 1, 1163 XVECEXP (pat, 0, i), flags) : 1164#endif 1165#ifdef ANNUL_IFTRUE_SLOTS 1166 (INSN_ANNULLED_BRANCH_P (jump) 1167 && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i))) 1168 ? eligible_for_annul_true (jump, i - 1, 1169 XVECEXP (pat, 0, i), flags) : 1170#endif 1171 eligible_for_delay (jump, i - 1, XVECEXP (pat, 0, i), flags))) 1172 break; 1173 1174 return (i == XVECLEN (pat, 0)); 1175} 1176 1177/* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate 1178 any insns we wish to place in the delay slot of JUMP. */ 1179 1180static int 1181redirect_with_delay_list_safe_p (rtx jump, rtx newlabel, rtx delay_list) 1182{ 1183 int flags, i; 1184 rtx li; 1185 1186 /* Make sure all the insns in DELAY_LIST would still be 1187 valid after threading the jump. If they are still 1188 valid, then return nonzero. */ 1189 1190 flags = get_jump_flags (jump, newlabel); 1191 for (li = delay_list, i = 0; li; li = XEXP (li, 1), i++) 1192 if (! ( 1193#ifdef ANNUL_IFFALSE_SLOTS 1194 (INSN_ANNULLED_BRANCH_P (jump) 1195 && INSN_FROM_TARGET_P (XEXP (li, 0))) 1196 ? eligible_for_annul_false (jump, i, XEXP (li, 0), flags) : 1197#endif 1198#ifdef ANNUL_IFTRUE_SLOTS 1199 (INSN_ANNULLED_BRANCH_P (jump) 1200 && ! INSN_FROM_TARGET_P (XEXP (li, 0))) 1201 ? eligible_for_annul_true (jump, i, XEXP (li, 0), flags) : 1202#endif 1203 eligible_for_delay (jump, i, XEXP (li, 0), flags))) 1204 break; 1205 1206 return (li == NULL); 1207} 1208 1209/* DELAY_LIST is a list of insns that have already been placed into delay 1210 slots. See if all of them have the same annulling status as ANNUL_TRUE_P. 1211 If not, return 0; otherwise return 1. */ 1212 1213static int 1214check_annul_list_true_false (int annul_true_p, rtx delay_list) 1215{ 1216 rtx temp; 1217 1218 if (delay_list) 1219 { 1220 for (temp = delay_list; temp; temp = XEXP (temp, 1)) 1221 { 1222 rtx trial = XEXP (temp, 0); 1223 1224 if ((annul_true_p && INSN_FROM_TARGET_P (trial)) 1225 || (!annul_true_p && !INSN_FROM_TARGET_P (trial))) 1226 return 0; 1227 } 1228 } 1229 1230 return 1; 1231} 1232 1233/* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that 1234 the condition tested by INSN is CONDITION and the resources shown in 1235 OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns 1236 from SEQ's delay list, in addition to whatever insns it may execute 1237 (in DELAY_LIST). SETS and NEEDED are denote resources already set and 1238 needed while searching for delay slot insns. Return the concatenated 1239 delay list if possible, otherwise, return 0. 1240 1241 SLOTS_TO_FILL is the total number of slots required by INSN, and 1242 PSLOTS_FILLED points to the number filled so far (also the number of 1243 insns in DELAY_LIST). It is updated with the number that have been 1244 filled from the SEQUENCE, if any. 1245 1246 PANNUL_P points to a nonzero value if we already know that we need 1247 to annul INSN. If this routine determines that annulling is needed, 1248 it may set that value nonzero. 1249 1250 PNEW_THREAD points to a location that is to receive the place at which 1251 execution should continue. */ 1252 1253static rtx 1254steal_delay_list_from_target (rtx insn, rtx condition, rtx seq, 1255 rtx delay_list, struct resources *sets, 1256 struct resources *needed, 1257 struct resources *other_needed, 1258 int slots_to_fill, int *pslots_filled, 1259 int *pannul_p, rtx *pnew_thread) 1260{ 1261 rtx temp; 1262 int slots_remaining = slots_to_fill - *pslots_filled; 1263 int total_slots_filled = *pslots_filled; 1264 rtx new_delay_list = 0; 1265 int must_annul = *pannul_p; 1266 int used_annul = 0; 1267 int i; 1268 struct resources cc_set; 1269 1270 /* We can't do anything if there are more delay slots in SEQ than we 1271 can handle, or if we don't know that it will be a taken branch. 1272 We know that it will be a taken branch if it is either an unconditional 1273 branch or a conditional branch with a stricter branch condition. 1274 1275 Also, exit if the branch has more than one set, since then it is computing 1276 other results that can't be ignored, e.g. the HPPA mov&branch instruction. 1277 ??? It may be possible to move other sets into INSN in addition to 1278 moving the instructions in the delay slots. 1279 1280 We can not steal the delay list if one of the instructions in the 1281 current delay_list modifies the condition codes and the jump in the 1282 sequence is a conditional jump. We can not do this because we can 1283 not change the direction of the jump because the condition codes 1284 will effect the direction of the jump in the sequence. */ 1285 1286 CLEAR_RESOURCE (&cc_set); 1287 for (temp = delay_list; temp; temp = XEXP (temp, 1)) 1288 { 1289 rtx trial = XEXP (temp, 0); 1290 1291 mark_set_resources (trial, &cc_set, 0, MARK_SRC_DEST_CALL); 1292 if (insn_references_resource_p (XVECEXP (seq , 0, 0), &cc_set, 0)) 1293 return delay_list; 1294 } 1295 1296 if (XVECLEN (seq, 0) - 1 > slots_remaining 1297 || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0)) 1298 || ! single_set (XVECEXP (seq, 0, 0))) 1299 return delay_list; 1300 1301#ifdef MD_CAN_REDIRECT_BRANCH 1302 /* On some targets, branches with delay slots can have a limited 1303 displacement. Give the back end a chance to tell us we can't do 1304 this. */ 1305 if (! MD_CAN_REDIRECT_BRANCH (insn, XVECEXP (seq, 0, 0))) 1306 return delay_list; 1307#endif 1308 1309 for (i = 1; i < XVECLEN (seq, 0); i++) 1310 { 1311 rtx trial = XVECEXP (seq, 0, i); 1312 int flags; 1313 1314 if (insn_references_resource_p (trial, sets, 0) 1315 || insn_sets_resource_p (trial, needed, 0) 1316 || insn_sets_resource_p (trial, sets, 0) 1317#ifdef HAVE_cc0 1318 /* If TRIAL sets CC0, we can't copy it, so we can't steal this 1319 delay list. */ 1320 || find_reg_note (trial, REG_CC_USER, NULL_RTX) 1321#endif 1322 /* If TRIAL is from the fallthrough code of an annulled branch insn 1323 in SEQ, we cannot use it. */ 1324 || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0)) 1325 && ! INSN_FROM_TARGET_P (trial))) 1326 return delay_list; 1327 1328 /* If this insn was already done (usually in a previous delay slot), 1329 pretend we put it in our delay slot. */ 1330 if (redundant_insn (trial, insn, new_delay_list)) 1331 continue; 1332 1333 /* We will end up re-vectoring this branch, so compute flags 1334 based on jumping to the new label. */ 1335 flags = get_jump_flags (insn, JUMP_LABEL (XVECEXP (seq, 0, 0))); 1336 1337 if (! must_annul 1338 && ((condition == const_true_rtx 1339 || (! insn_sets_resource_p (trial, other_needed, 0) 1340 && ! may_trap_or_fault_p (PATTERN (trial))))) 1341 ? eligible_for_delay (insn, total_slots_filled, trial, flags) 1342 : (must_annul || (delay_list == NULL && new_delay_list == NULL)) 1343 && (must_annul = 1, 1344 check_annul_list_true_false (0, delay_list) 1345 && check_annul_list_true_false (0, new_delay_list) 1346 && eligible_for_annul_false (insn, total_slots_filled, 1347 trial, flags))) 1348 { 1349 if (must_annul) 1350 used_annul = 1; 1351 temp = copy_rtx (trial); 1352 INSN_FROM_TARGET_P (temp) = 1; 1353 new_delay_list = add_to_delay_list (temp, new_delay_list); 1354 total_slots_filled++; 1355 1356 if (--slots_remaining == 0) 1357 break; 1358 } 1359 else 1360 return delay_list; 1361 } 1362 1363 /* Show the place to which we will be branching. */ 1364 *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0))); 1365 1366 /* Add any new insns to the delay list and update the count of the 1367 number of slots filled. */ 1368 *pslots_filled = total_slots_filled; 1369 if (used_annul) 1370 *pannul_p = 1; 1371 1372 if (delay_list == 0) 1373 return new_delay_list; 1374 1375 for (temp = new_delay_list; temp; temp = XEXP (temp, 1)) 1376 delay_list = add_to_delay_list (XEXP (temp, 0), delay_list); 1377 1378 return delay_list; 1379} 1380 1381/* Similar to steal_delay_list_from_target except that SEQ is on the 1382 fallthrough path of INSN. Here we only do something if the delay insn 1383 of SEQ is an unconditional branch. In that case we steal its delay slot 1384 for INSN since unconditional branches are much easier to fill. */ 1385 1386static rtx 1387steal_delay_list_from_fallthrough (rtx insn, rtx condition, rtx seq, 1388 rtx delay_list, struct resources *sets, 1389 struct resources *needed, 1390 struct resources *other_needed, 1391 int slots_to_fill, int *pslots_filled, 1392 int *pannul_p) 1393{ 1394 int i; 1395 int flags; 1396 int must_annul = *pannul_p; 1397 int used_annul = 0; 1398 1399 flags = get_jump_flags (insn, JUMP_LABEL (insn)); 1400 1401 /* We can't do anything if SEQ's delay insn isn't an 1402 unconditional branch. */ 1403 1404 if (! simplejump_p (XVECEXP (seq, 0, 0)) 1405 && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN) 1406 return delay_list; 1407 1408 for (i = 1; i < XVECLEN (seq, 0); i++) 1409 { 1410 rtx trial = XVECEXP (seq, 0, i); 1411 1412 /* If TRIAL sets CC0, stealing it will move it too far from the use 1413 of CC0. */ 1414 if (insn_references_resource_p (trial, sets, 0) 1415 || insn_sets_resource_p (trial, needed, 0) 1416 || insn_sets_resource_p (trial, sets, 0) 1417#ifdef HAVE_cc0 1418 || sets_cc0_p (PATTERN (trial)) 1419#endif 1420 ) 1421 1422 break; 1423 1424 /* If this insn was already done, we don't need it. */ 1425 if (redundant_insn (trial, insn, delay_list)) 1426 { 1427 delete_from_delay_slot (trial); 1428 continue; 1429 } 1430 1431 if (! must_annul 1432 && ((condition == const_true_rtx 1433 || (! insn_sets_resource_p (trial, other_needed, 0) 1434 && ! may_trap_or_fault_p (PATTERN (trial))))) 1435 ? eligible_for_delay (insn, *pslots_filled, trial, flags) 1436 : (must_annul || delay_list == NULL) && (must_annul = 1, 1437 check_annul_list_true_false (1, delay_list) 1438 && eligible_for_annul_true (insn, *pslots_filled, trial, flags))) 1439 { 1440 if (must_annul) 1441 used_annul = 1; 1442 delete_from_delay_slot (trial); 1443 delay_list = add_to_delay_list (trial, delay_list); 1444 1445 if (++(*pslots_filled) == slots_to_fill) 1446 break; 1447 } 1448 else 1449 break; 1450 } 1451 1452 if (used_annul) 1453 *pannul_p = 1; 1454 return delay_list; 1455} 1456 1457/* Try merging insns starting at THREAD which match exactly the insns in 1458 INSN's delay list. 1459 1460 If all insns were matched and the insn was previously annulling, the 1461 annul bit will be cleared. 1462 1463 For each insn that is merged, if the branch is or will be non-annulling, 1464 we delete the merged insn. */ 1465 1466static void 1467try_merge_delay_insns (rtx insn, rtx thread) 1468{ 1469 rtx trial, next_trial; 1470 rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0); 1471 int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn); 1472 int slot_number = 1; 1473 int num_slots = XVECLEN (PATTERN (insn), 0); 1474 rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number); 1475 struct resources set, needed; 1476 rtx merged_insns = 0; 1477 int i; 1478 int flags; 1479 1480 flags = get_jump_flags (delay_insn, JUMP_LABEL (delay_insn)); 1481 1482 CLEAR_RESOURCE (&needed); 1483 CLEAR_RESOURCE (&set); 1484 1485 /* If this is not an annulling branch, take into account anything needed in 1486 INSN's delay slot. This prevents two increments from being incorrectly 1487 folded into one. If we are annulling, this would be the correct 1488 thing to do. (The alternative, looking at things set in NEXT_TO_MATCH 1489 will essentially disable this optimization. This method is somewhat of 1490 a kludge, but I don't see a better way.) */ 1491 if (! annul_p) 1492 for (i = 1 ; i < num_slots; i++) 1493 if (XVECEXP (PATTERN (insn), 0, i)) 1494 mark_referenced_resources (XVECEXP (PATTERN (insn), 0, i), &needed, 1); 1495 1496 for (trial = thread; !stop_search_p (trial, 1); trial = next_trial) 1497 { 1498 rtx pat = PATTERN (trial); 1499 rtx oldtrial = trial; 1500 1501 next_trial = next_nonnote_insn (trial); 1502 1503 /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */ 1504 if (NONJUMP_INSN_P (trial) 1505 && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)) 1506 continue; 1507 1508 if (GET_CODE (next_to_match) == GET_CODE (trial) 1509#ifdef HAVE_cc0 1510 /* We can't share an insn that sets cc0. */ 1511 && ! sets_cc0_p (pat) 1512#endif 1513 && ! insn_references_resource_p (trial, &set, 1) 1514 && ! insn_sets_resource_p (trial, &set, 1) 1515 && ! insn_sets_resource_p (trial, &needed, 1) 1516 && (trial = try_split (pat, trial, 0)) != 0 1517 /* Update next_trial, in case try_split succeeded. */ 1518 && (next_trial = next_nonnote_insn (trial)) 1519 /* Likewise THREAD. */ 1520 && (thread = oldtrial == thread ? trial : thread) 1521 && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial)) 1522 /* Have to test this condition if annul condition is different 1523 from (and less restrictive than) non-annulling one. */ 1524 && eligible_for_delay (delay_insn, slot_number - 1, trial, flags)) 1525 { 1526 1527 if (! annul_p) 1528 { 1529 update_block (trial, thread); 1530 if (trial == thread) 1531 thread = next_active_insn (thread); 1532 1533 delete_related_insns (trial); 1534 INSN_FROM_TARGET_P (next_to_match) = 0; 1535 } 1536 else 1537 merged_insns = gen_rtx_INSN_LIST (VOIDmode, trial, merged_insns); 1538 1539 if (++slot_number == num_slots) 1540 break; 1541 1542 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number); 1543 } 1544 1545 mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL); 1546 mark_referenced_resources (trial, &needed, 1); 1547 } 1548 1549 /* See if we stopped on a filled insn. If we did, try to see if its 1550 delay slots match. */ 1551 if (slot_number != num_slots 1552 && trial && NONJUMP_INSN_P (trial) 1553 && GET_CODE (PATTERN (trial)) == SEQUENCE 1554 && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0))) 1555 { 1556 rtx pat = PATTERN (trial); 1557 rtx filled_insn = XVECEXP (pat, 0, 0); 1558 1559 /* Account for resources set/needed by the filled insn. */ 1560 mark_set_resources (filled_insn, &set, 0, MARK_SRC_DEST_CALL); 1561 mark_referenced_resources (filled_insn, &needed, 1); 1562 1563 for (i = 1; i < XVECLEN (pat, 0); i++) 1564 { 1565 rtx dtrial = XVECEXP (pat, 0, i); 1566 1567 if (! insn_references_resource_p (dtrial, &set, 1) 1568 && ! insn_sets_resource_p (dtrial, &set, 1) 1569 && ! insn_sets_resource_p (dtrial, &needed, 1) 1570#ifdef HAVE_cc0 1571 && ! sets_cc0_p (PATTERN (dtrial)) 1572#endif 1573 && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial)) 1574 && eligible_for_delay (delay_insn, slot_number - 1, dtrial, flags)) 1575 { 1576 if (! annul_p) 1577 { 1578 rtx new; 1579 1580 update_block (dtrial, thread); 1581 new = delete_from_delay_slot (dtrial); 1582 if (INSN_DELETED_P (thread)) 1583 thread = new; 1584 INSN_FROM_TARGET_P (next_to_match) = 0; 1585 } 1586 else 1587 merged_insns = gen_rtx_INSN_LIST (SImode, dtrial, 1588 merged_insns); 1589 1590 if (++slot_number == num_slots) 1591 break; 1592 1593 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number); 1594 } 1595 else 1596 { 1597 /* Keep track of the set/referenced resources for the delay 1598 slots of any trial insns we encounter. */ 1599 mark_set_resources (dtrial, &set, 0, MARK_SRC_DEST_CALL); 1600 mark_referenced_resources (dtrial, &needed, 1); 1601 } 1602 } 1603 } 1604 1605 /* If all insns in the delay slot have been matched and we were previously 1606 annulling the branch, we need not any more. In that case delete all the 1607 merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn in 1608 the delay list so that we know that it isn't only being used at the 1609 target. */ 1610 if (slot_number == num_slots && annul_p) 1611 { 1612 for (; merged_insns; merged_insns = XEXP (merged_insns, 1)) 1613 { 1614 if (GET_MODE (merged_insns) == SImode) 1615 { 1616 rtx new; 1617 1618 update_block (XEXP (merged_insns, 0), thread); 1619 new = delete_from_delay_slot (XEXP (merged_insns, 0)); 1620 if (INSN_DELETED_P (thread)) 1621 thread = new; 1622 } 1623 else 1624 { 1625 update_block (XEXP (merged_insns, 0), thread); 1626 delete_related_insns (XEXP (merged_insns, 0)); 1627 } 1628 } 1629 1630 INSN_ANNULLED_BRANCH_P (delay_insn) = 0; 1631 1632 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++) 1633 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0; 1634 } 1635} 1636 1637/* See if INSN is redundant with an insn in front of TARGET. Often this 1638 is called when INSN is a candidate for a delay slot of TARGET. 1639 DELAY_LIST are insns that will be placed in delay slots of TARGET in front 1640 of INSN. Often INSN will be redundant with an insn in a delay slot of 1641 some previous insn. This happens when we have a series of branches to the 1642 same label; in that case the first insn at the target might want to go 1643 into each of the delay slots. 1644 1645 If we are not careful, this routine can take up a significant fraction 1646 of the total compilation time (4%), but only wins rarely. Hence we 1647 speed this routine up by making two passes. The first pass goes back 1648 until it hits a label and sees if it finds an insn with an identical 1649 pattern. Only in this (relatively rare) event does it check for 1650 data conflicts. 1651 1652 We do not split insns we encounter. This could cause us not to find a 1653 redundant insn, but the cost of splitting seems greater than the possible 1654 gain in rare cases. */ 1655 1656static rtx 1657redundant_insn (rtx insn, rtx target, rtx delay_list) 1658{ 1659 rtx target_main = target; 1660 rtx ipat = PATTERN (insn); 1661 rtx trial, pat; 1662 struct resources needed, set; 1663 int i; 1664 unsigned insns_to_search; 1665 1666 /* If INSN has any REG_UNUSED notes, it can't match anything since we 1667 are allowed to not actually assign to such a register. */ 1668 if (find_reg_note (insn, REG_UNUSED, NULL_RTX) != 0) 1669 return 0; 1670 1671 /* Scan backwards looking for a match. */ 1672 for (trial = PREV_INSN (target), 1673 insns_to_search = MAX_DELAY_SLOT_INSN_SEARCH; 1674 trial && insns_to_search > 0; 1675 trial = PREV_INSN (trial), --insns_to_search) 1676 { 1677 if (LABEL_P (trial)) 1678 return 0; 1679 1680 if (! INSN_P (trial)) 1681 continue; 1682 1683 pat = PATTERN (trial); 1684 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 1685 continue; 1686 1687 if (GET_CODE (pat) == SEQUENCE) 1688 { 1689 /* Stop for a CALL and its delay slots because it is difficult to 1690 track its resource needs correctly. */ 1691 if (CALL_P (XVECEXP (pat, 0, 0))) 1692 return 0; 1693 1694 /* Stop for an INSN or JUMP_INSN with delayed effects and its delay 1695 slots because it is difficult to track its resource needs 1696 correctly. */ 1697 1698#ifdef INSN_SETS_ARE_DELAYED 1699 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0))) 1700 return 0; 1701#endif 1702 1703#ifdef INSN_REFERENCES_ARE_DELAYED 1704 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0))) 1705 return 0; 1706#endif 1707 1708 /* See if any of the insns in the delay slot match, updating 1709 resource requirements as we go. */ 1710 for (i = XVECLEN (pat, 0) - 1; i > 0; i--) 1711 if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn) 1712 && rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat) 1713 && ! find_reg_note (XVECEXP (pat, 0, i), REG_UNUSED, NULL_RTX)) 1714 break; 1715 1716 /* If found a match, exit this loop early. */ 1717 if (i > 0) 1718 break; 1719 } 1720 1721 else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat) 1722 && ! find_reg_note (trial, REG_UNUSED, NULL_RTX)) 1723 break; 1724 } 1725 1726 /* If we didn't find an insn that matches, return 0. */ 1727 if (trial == 0) 1728 return 0; 1729 1730 /* See what resources this insn sets and needs. If they overlap, or 1731 if this insn references CC0, it can't be redundant. */ 1732 1733 CLEAR_RESOURCE (&needed); 1734 CLEAR_RESOURCE (&set); 1735 mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL); 1736 mark_referenced_resources (insn, &needed, 1); 1737 1738 /* If TARGET is a SEQUENCE, get the main insn. */ 1739 if (NONJUMP_INSN_P (target) && GET_CODE (PATTERN (target)) == SEQUENCE) 1740 target_main = XVECEXP (PATTERN (target), 0, 0); 1741 1742 if (resource_conflicts_p (&needed, &set) 1743#ifdef HAVE_cc0 1744 || reg_mentioned_p (cc0_rtx, ipat) 1745#endif 1746 /* The insn requiring the delay may not set anything needed or set by 1747 INSN. */ 1748 || insn_sets_resource_p (target_main, &needed, 1) 1749 || insn_sets_resource_p (target_main, &set, 1)) 1750 return 0; 1751 1752 /* Insns we pass may not set either NEEDED or SET, so merge them for 1753 simpler tests. */ 1754 needed.memory |= set.memory; 1755 needed.unch_memory |= set.unch_memory; 1756 IOR_HARD_REG_SET (needed.regs, set.regs); 1757 1758 /* This insn isn't redundant if it conflicts with an insn that either is 1759 or will be in a delay slot of TARGET. */ 1760 1761 while (delay_list) 1762 { 1763 if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1)) 1764 return 0; 1765 delay_list = XEXP (delay_list, 1); 1766 } 1767 1768 if (NONJUMP_INSN_P (target) && GET_CODE (PATTERN (target)) == SEQUENCE) 1769 for (i = 1; i < XVECLEN (PATTERN (target), 0); i++) 1770 if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1)) 1771 return 0; 1772 1773 /* Scan backwards until we reach a label or an insn that uses something 1774 INSN sets or sets something insn uses or sets. */ 1775 1776 for (trial = PREV_INSN (target), 1777 insns_to_search = MAX_DELAY_SLOT_INSN_SEARCH; 1778 trial && !LABEL_P (trial) && insns_to_search > 0; 1779 trial = PREV_INSN (trial), --insns_to_search) 1780 { 1781 if (!INSN_P (trial)) 1782 continue; 1783 1784 pat = PATTERN (trial); 1785 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 1786 continue; 1787 1788 if (GET_CODE (pat) == SEQUENCE) 1789 { 1790 /* If this is a CALL_INSN and its delay slots, it is hard to track 1791 the resource needs properly, so give up. */ 1792 if (CALL_P (XVECEXP (pat, 0, 0))) 1793 return 0; 1794 1795 /* If this is an INSN or JUMP_INSN with delayed effects, it 1796 is hard to track the resource needs properly, so give up. */ 1797 1798#ifdef INSN_SETS_ARE_DELAYED 1799 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0))) 1800 return 0; 1801#endif 1802 1803#ifdef INSN_REFERENCES_ARE_DELAYED 1804 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0))) 1805 return 0; 1806#endif 1807 1808 /* See if any of the insns in the delay slot match, updating 1809 resource requirements as we go. */ 1810 for (i = XVECLEN (pat, 0) - 1; i > 0; i--) 1811 { 1812 rtx candidate = XVECEXP (pat, 0, i); 1813 1814 /* If an insn will be annulled if the branch is false, it isn't 1815 considered as a possible duplicate insn. */ 1816 if (rtx_equal_p (PATTERN (candidate), ipat) 1817 && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0)) 1818 && INSN_FROM_TARGET_P (candidate))) 1819 { 1820 /* Show that this insn will be used in the sequel. */ 1821 INSN_FROM_TARGET_P (candidate) = 0; 1822 return candidate; 1823 } 1824 1825 /* Unless this is an annulled insn from the target of a branch, 1826 we must stop if it sets anything needed or set by INSN. */ 1827 if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0)) 1828 || ! INSN_FROM_TARGET_P (candidate)) 1829 && insn_sets_resource_p (candidate, &needed, 1)) 1830 return 0; 1831 } 1832 1833 /* If the insn requiring the delay slot conflicts with INSN, we 1834 must stop. */ 1835 if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1)) 1836 return 0; 1837 } 1838 else 1839 { 1840 /* See if TRIAL is the same as INSN. */ 1841 pat = PATTERN (trial); 1842 if (rtx_equal_p (pat, ipat)) 1843 return trial; 1844 1845 /* Can't go any further if TRIAL conflicts with INSN. */ 1846 if (insn_sets_resource_p (trial, &needed, 1)) 1847 return 0; 1848 } 1849 } 1850 1851 return 0; 1852} 1853 1854/* Return 1 if THREAD can only be executed in one way. If LABEL is nonzero, 1855 it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH 1856 is nonzero, we are allowed to fall into this thread; otherwise, we are 1857 not. 1858 1859 If LABEL is used more than one or we pass a label other than LABEL before 1860 finding an active insn, we do not own this thread. */ 1861 1862static int 1863own_thread_p (rtx thread, rtx label, int allow_fallthrough) 1864{ 1865 rtx active_insn; 1866 rtx insn; 1867 1868 /* We don't own the function end. */ 1869 if (thread == 0) 1870 return 0; 1871 1872 /* Get the first active insn, or THREAD, if it is an active insn. */ 1873 active_insn = next_active_insn (PREV_INSN (thread)); 1874 1875 for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn)) 1876 if (LABEL_P (insn) 1877 && (insn != label || LABEL_NUSES (insn) != 1)) 1878 return 0; 1879 1880 if (allow_fallthrough) 1881 return 1; 1882 1883 /* Ensure that we reach a BARRIER before any insn or label. */ 1884 for (insn = prev_nonnote_insn (thread); 1885 insn == 0 || !BARRIER_P (insn); 1886 insn = prev_nonnote_insn (insn)) 1887 if (insn == 0 1888 || LABEL_P (insn) 1889 || (NONJUMP_INSN_P (insn) 1890 && GET_CODE (PATTERN (insn)) != USE 1891 && GET_CODE (PATTERN (insn)) != CLOBBER)) 1892 return 0; 1893 1894 return 1; 1895} 1896 1897/* Called when INSN is being moved from a location near the target of a jump. 1898 We leave a marker of the form (use (INSN)) immediately in front 1899 of WHERE for mark_target_live_regs. These markers will be deleted when 1900 reorg finishes. 1901 1902 We used to try to update the live status of registers if WHERE is at 1903 the start of a basic block, but that can't work since we may remove a 1904 BARRIER in relax_delay_slots. */ 1905 1906static void 1907update_block (rtx insn, rtx where) 1908{ 1909 /* Ignore if this was in a delay slot and it came from the target of 1910 a branch. */ 1911 if (INSN_FROM_TARGET_P (insn)) 1912 return; 1913 1914 emit_insn_before (gen_rtx_USE (VOIDmode, insn), where); 1915 1916 /* INSN might be making a value live in a block where it didn't use to 1917 be. So recompute liveness information for this block. */ 1918 1919 incr_ticks_for_insn (insn); 1920} 1921 1922/* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for 1923 the basic block containing the jump. */ 1924 1925static int 1926reorg_redirect_jump (rtx jump, rtx nlabel) 1927{ 1928 incr_ticks_for_insn (jump); 1929 return redirect_jump (jump, nlabel, 1); 1930} 1931 1932/* Called when INSN is being moved forward into a delay slot of DELAYED_INSN. 1933 We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes 1934 that reference values used in INSN. If we find one, then we move the 1935 REG_DEAD note to INSN. 1936 1937 This is needed to handle the case where a later insn (after INSN) has a 1938 REG_DEAD note for a register used by INSN, and this later insn subsequently 1939 gets moved before a CODE_LABEL because it is a redundant insn. In this 1940 case, mark_target_live_regs may be confused into thinking the register 1941 is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */ 1942 1943static void 1944update_reg_dead_notes (rtx insn, rtx delayed_insn) 1945{ 1946 rtx p, link, next; 1947 1948 for (p = next_nonnote_insn (insn); p != delayed_insn; 1949 p = next_nonnote_insn (p)) 1950 for (link = REG_NOTES (p); link; link = next) 1951 { 1952 next = XEXP (link, 1); 1953 1954 if (REG_NOTE_KIND (link) != REG_DEAD 1955 || !REG_P (XEXP (link, 0))) 1956 continue; 1957 1958 if (reg_referenced_p (XEXP (link, 0), PATTERN (insn))) 1959 { 1960 /* Move the REG_DEAD note from P to INSN. */ 1961 remove_note (p, link); 1962 XEXP (link, 1) = REG_NOTES (insn); 1963 REG_NOTES (insn) = link; 1964 } 1965 } 1966} 1967 1968/* Called when an insn redundant with start_insn is deleted. If there 1969 is a REG_DEAD note for the target of start_insn between start_insn 1970 and stop_insn, then the REG_DEAD note needs to be deleted since the 1971 value no longer dies there. 1972 1973 If the REG_DEAD note isn't deleted, then mark_target_live_regs may be 1974 confused into thinking the register is dead. */ 1975 1976static void 1977fix_reg_dead_note (rtx start_insn, rtx stop_insn) 1978{ 1979 rtx p, link, next; 1980 1981 for (p = next_nonnote_insn (start_insn); p != stop_insn; 1982 p = next_nonnote_insn (p)) 1983 for (link = REG_NOTES (p); link; link = next) 1984 { 1985 next = XEXP (link, 1); 1986 1987 if (REG_NOTE_KIND (link) != REG_DEAD 1988 || !REG_P (XEXP (link, 0))) 1989 continue; 1990 1991 if (reg_set_p (XEXP (link, 0), PATTERN (start_insn))) 1992 { 1993 remove_note (p, link); 1994 return; 1995 } 1996 } 1997} 1998 1999/* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN. 2000 2001 This handles the case of udivmodXi4 instructions which optimize their 2002 output depending on whether any REG_UNUSED notes are present. 2003 we must make sure that INSN calculates as many results as REDUNDANT_INSN 2004 does. */ 2005 2006static void 2007update_reg_unused_notes (rtx insn, rtx redundant_insn) 2008{ 2009 rtx link, next; 2010 2011 for (link = REG_NOTES (insn); link; link = next) 2012 { 2013 next = XEXP (link, 1); 2014 2015 if (REG_NOTE_KIND (link) != REG_UNUSED 2016 || !REG_P (XEXP (link, 0))) 2017 continue; 2018 2019 if (! find_regno_note (redundant_insn, REG_UNUSED, 2020 REGNO (XEXP (link, 0)))) 2021 remove_note (insn, link); 2022 } 2023} 2024 2025/* Scan a function looking for insns that need a delay slot and find insns to 2026 put into the delay slot. 2027 2028 NON_JUMPS_P is nonzero if we are to only try to fill non-jump insns (such 2029 as calls). We do these first since we don't want jump insns (that are 2030 easier to fill) to get the only insns that could be used for non-jump insns. 2031 When it is zero, only try to fill JUMP_INSNs. 2032 2033 When slots are filled in this manner, the insns (including the 2034 delay_insn) are put together in a SEQUENCE rtx. In this fashion, 2035 it is possible to tell whether a delay slot has really been filled 2036 or not. `final' knows how to deal with this, by communicating 2037 through FINAL_SEQUENCE. */ 2038 2039static void 2040fill_simple_delay_slots (int non_jumps_p) 2041{ 2042 rtx insn, pat, trial, next_trial; 2043 int i; 2044 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base; 2045 struct resources needed, set; 2046 int slots_to_fill, slots_filled; 2047 rtx delay_list; 2048 2049 for (i = 0; i < num_unfilled_slots; i++) 2050 { 2051 int flags; 2052 /* Get the next insn to fill. If it has already had any slots assigned, 2053 we can't do anything with it. Maybe we'll improve this later. */ 2054 2055 insn = unfilled_slots_base[i]; 2056 if (insn == 0 2057 || INSN_DELETED_P (insn) 2058 || (NONJUMP_INSN_P (insn) 2059 && GET_CODE (PATTERN (insn)) == SEQUENCE) 2060 || (JUMP_P (insn) && non_jumps_p) 2061 || (!JUMP_P (insn) && ! non_jumps_p)) 2062 continue; 2063 2064 /* It may have been that this insn used to need delay slots, but 2065 now doesn't; ignore in that case. This can happen, for example, 2066 on the HP PA RISC, where the number of delay slots depends on 2067 what insns are nearby. */ 2068 slots_to_fill = num_delay_slots (insn); 2069 2070 /* Some machine description have defined instructions to have 2071 delay slots only in certain circumstances which may depend on 2072 nearby insns (which change due to reorg's actions). 2073 2074 For example, the PA port normally has delay slots for unconditional 2075 jumps. 2076 2077 However, the PA port claims such jumps do not have a delay slot 2078 if they are immediate successors of certain CALL_INSNs. This 2079 allows the port to favor filling the delay slot of the call with 2080 the unconditional jump. */ 2081 if (slots_to_fill == 0) 2082 continue; 2083 2084 /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL 2085 says how many. After initialization, first try optimizing 2086 2087 call _foo call _foo 2088 nop add %o7,.-L1,%o7 2089 b,a L1 2090 nop 2091 2092 If this case applies, the delay slot of the call is filled with 2093 the unconditional jump. This is done first to avoid having the 2094 delay slot of the call filled in the backward scan. Also, since 2095 the unconditional jump is likely to also have a delay slot, that 2096 insn must exist when it is subsequently scanned. 2097 2098 This is tried on each insn with delay slots as some machines 2099 have insns which perform calls, but are not represented as 2100 CALL_INSNs. */ 2101 2102 slots_filled = 0; 2103 delay_list = 0; 2104 2105 if (JUMP_P (insn)) 2106 flags = get_jump_flags (insn, JUMP_LABEL (insn)); 2107 else 2108 flags = get_jump_flags (insn, NULL_RTX); 2109 2110 if ((trial = next_active_insn (insn)) 2111 && JUMP_P (trial) 2112 && simplejump_p (trial) 2113 && eligible_for_delay (insn, slots_filled, trial, flags) 2114 && no_labels_between_p (insn, trial) 2115 && ! can_throw_internal (trial)) 2116 { 2117 rtx *tmp; 2118 slots_filled++; 2119 delay_list = add_to_delay_list (trial, delay_list); 2120 2121 /* TRIAL may have had its delay slot filled, then unfilled. When 2122 the delay slot is unfilled, TRIAL is placed back on the unfilled 2123 slots obstack. Unfortunately, it is placed on the end of the 2124 obstack, not in its original location. Therefore, we must search 2125 from entry i + 1 to the end of the unfilled slots obstack to 2126 try and find TRIAL. */ 2127 tmp = &unfilled_slots_base[i + 1]; 2128 while (*tmp != trial && tmp != unfilled_slots_next) 2129 tmp++; 2130 2131 /* Remove the unconditional jump from consideration for delay slot 2132 filling and unthread it. */ 2133 if (*tmp == trial) 2134 *tmp = 0; 2135 { 2136 rtx next = NEXT_INSN (trial); 2137 rtx prev = PREV_INSN (trial); 2138 if (prev) 2139 NEXT_INSN (prev) = next; 2140 if (next) 2141 PREV_INSN (next) = prev; 2142 } 2143 } 2144 2145 /* Now, scan backwards from the insn to search for a potential 2146 delay-slot candidate. Stop searching when a label or jump is hit. 2147 2148 For each candidate, if it is to go into the delay slot (moved 2149 forward in execution sequence), it must not need or set any resources 2150 that were set by later insns and must not set any resources that 2151 are needed for those insns. 2152 2153 The delay slot insn itself sets resources unless it is a call 2154 (in which case the called routine, not the insn itself, is doing 2155 the setting). */ 2156 2157 if (slots_filled < slots_to_fill) 2158 { 2159 CLEAR_RESOURCE (&needed); 2160 CLEAR_RESOURCE (&set); 2161 mark_set_resources (insn, &set, 0, MARK_SRC_DEST); 2162 mark_referenced_resources (insn, &needed, 0); 2163 2164 for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1); 2165 trial = next_trial) 2166 { 2167 next_trial = prev_nonnote_insn (trial); 2168 2169 /* This must be an INSN or CALL_INSN. */ 2170 pat = PATTERN (trial); 2171 2172 /* USE and CLOBBER at this level was just for flow; ignore it. */ 2173 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 2174 continue; 2175 2176 /* Check for resource conflict first, to avoid unnecessary 2177 splitting. */ 2178 if (! insn_references_resource_p (trial, &set, 1) 2179 && ! insn_sets_resource_p (trial, &set, 1) 2180 && ! insn_sets_resource_p (trial, &needed, 1) 2181#ifdef HAVE_cc0 2182 /* Can't separate set of cc0 from its use. */ 2183 && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat)) 2184#endif 2185 && ! can_throw_internal (trial)) 2186 { 2187 trial = try_split (pat, trial, 1); 2188 next_trial = prev_nonnote_insn (trial); 2189 if (eligible_for_delay (insn, slots_filled, trial, flags)) 2190 { 2191 /* In this case, we are searching backward, so if we 2192 find insns to put on the delay list, we want 2193 to put them at the head, rather than the 2194 tail, of the list. */ 2195 2196 update_reg_dead_notes (trial, insn); 2197 delay_list = gen_rtx_INSN_LIST (VOIDmode, 2198 trial, delay_list); 2199 update_block (trial, trial); 2200 delete_related_insns (trial); 2201 if (slots_to_fill == ++slots_filled) 2202 break; 2203 continue; 2204 } 2205 } 2206 2207 mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL); 2208 mark_referenced_resources (trial, &needed, 1); 2209 } 2210 } 2211 2212 /* If all needed slots haven't been filled, we come here. */ 2213 2214 /* Try to optimize case of jumping around a single insn. */ 2215#if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS) 2216 if (slots_filled != slots_to_fill 2217 && delay_list == 0 2218 && JUMP_P (insn) 2219 && (condjump_p (insn) || condjump_in_parallel_p (insn))) 2220 { 2221 delay_list = optimize_skip (insn); 2222 if (delay_list) 2223 slots_filled += 1; 2224 } 2225#endif 2226 2227 /* Try to get insns from beyond the insn needing the delay slot. 2228 These insns can neither set or reference resources set in insns being 2229 skipped, cannot set resources in the insn being skipped, and, if this 2230 is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the 2231 call might not return). 2232 2233 There used to be code which continued past the target label if 2234 we saw all uses of the target label. This code did not work, 2235 because it failed to account for some instructions which were 2236 both annulled and marked as from the target. This can happen as a 2237 result of optimize_skip. Since this code was redundant with 2238 fill_eager_delay_slots anyways, it was just deleted. */ 2239 2240 if (slots_filled != slots_to_fill 2241 /* If this instruction could throw an exception which is 2242 caught in the same function, then it's not safe to fill 2243 the delay slot with an instruction from beyond this 2244 point. For example, consider: 2245 2246 int i = 2; 2247 2248 try { 2249 f(); 2250 i = 3; 2251 } catch (...) {} 2252 2253 return i; 2254 2255 Even though `i' is a local variable, we must be sure not 2256 to put `i = 3' in the delay slot if `f' might throw an 2257 exception. 2258 2259 Presumably, we should also check to see if we could get 2260 back to this function via `setjmp'. */ 2261 && ! can_throw_internal (insn) 2262 && (!JUMP_P (insn) 2263 || ((condjump_p (insn) || condjump_in_parallel_p (insn)) 2264 && ! simplejump_p (insn) 2265 && JUMP_LABEL (insn) != 0))) 2266 { 2267 /* Invariant: If insn is a JUMP_INSN, the insn's jump 2268 label. Otherwise, zero. */ 2269 rtx target = 0; 2270 int maybe_never = 0; 2271 rtx pat, trial_delay; 2272 2273 CLEAR_RESOURCE (&needed); 2274 CLEAR_RESOURCE (&set); 2275 2276 if (CALL_P (insn)) 2277 { 2278 mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL); 2279 mark_referenced_resources (insn, &needed, 1); 2280 maybe_never = 1; 2281 } 2282 else 2283 { 2284 mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL); 2285 mark_referenced_resources (insn, &needed, 1); 2286 if (JUMP_P (insn)) 2287 target = JUMP_LABEL (insn); 2288 } 2289 2290 if (target == 0) 2291 for (trial = next_nonnote_insn (insn); trial; trial = next_trial) 2292 { 2293 next_trial = next_nonnote_insn (trial); 2294 2295 if (LABEL_P (trial) 2296 || BARRIER_P (trial)) 2297 break; 2298 2299 /* We must have an INSN, JUMP_INSN, or CALL_INSN. */ 2300 pat = PATTERN (trial); 2301 2302 /* Stand-alone USE and CLOBBER are just for flow. */ 2303 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 2304 continue; 2305 2306 /* If this already has filled delay slots, get the insn needing 2307 the delay slots. */ 2308 if (GET_CODE (pat) == SEQUENCE) 2309 trial_delay = XVECEXP (pat, 0, 0); 2310 else 2311 trial_delay = trial; 2312 2313 /* Stop our search when seeing an unconditional jump. */ 2314 if (JUMP_P (trial_delay)) 2315 break; 2316 2317 /* See if we have a resource problem before we try to 2318 split. */ 2319 if (GET_CODE (pat) != SEQUENCE 2320 && ! insn_references_resource_p (trial, &set, 1) 2321 && ! insn_sets_resource_p (trial, &set, 1) 2322 && ! insn_sets_resource_p (trial, &needed, 1) 2323#ifdef HAVE_cc0 2324 && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat)) 2325#endif 2326 && ! (maybe_never && may_trap_or_fault_p (pat)) 2327 && (trial = try_split (pat, trial, 0)) 2328 && eligible_for_delay (insn, slots_filled, trial, flags) 2329 && ! can_throw_internal(trial)) 2330 { 2331 next_trial = next_nonnote_insn (trial); 2332 delay_list = add_to_delay_list (trial, delay_list); 2333 2334#ifdef HAVE_cc0 2335 if (reg_mentioned_p (cc0_rtx, pat)) 2336 link_cc0_insns (trial); 2337#endif 2338 2339 delete_related_insns (trial); 2340 if (slots_to_fill == ++slots_filled) 2341 break; 2342 continue; 2343 } 2344 2345 mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL); 2346 mark_referenced_resources (trial, &needed, 1); 2347 2348 /* Ensure we don't put insns between the setting of cc and the 2349 comparison by moving a setting of cc into an earlier delay 2350 slot since these insns could clobber the condition code. */ 2351 set.cc = 1; 2352 2353 /* If this is a call or jump, we might not get here. */ 2354 if (CALL_P (trial_delay) 2355 || JUMP_P (trial_delay)) 2356 maybe_never = 1; 2357 } 2358 2359 /* If there are slots left to fill and our search was stopped by an 2360 unconditional branch, try the insn at the branch target. We can 2361 redirect the branch if it works. 2362 2363 Don't do this if the insn at the branch target is a branch. */ 2364 if (slots_to_fill != slots_filled 2365 && trial 2366 && JUMP_P (trial) 2367 && simplejump_p (trial) 2368 && (target == 0 || JUMP_LABEL (trial) == target) 2369 && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0 2370 && ! (NONJUMP_INSN_P (next_trial) 2371 && GET_CODE (PATTERN (next_trial)) == SEQUENCE) 2372 && !JUMP_P (next_trial) 2373 && ! insn_references_resource_p (next_trial, &set, 1) 2374 && ! insn_sets_resource_p (next_trial, &set, 1) 2375 && ! insn_sets_resource_p (next_trial, &needed, 1) 2376#ifdef HAVE_cc0 2377 && ! reg_mentioned_p (cc0_rtx, PATTERN (next_trial)) 2378#endif 2379 && ! (maybe_never && may_trap_or_fault_p (PATTERN (next_trial))) 2380 && (next_trial = try_split (PATTERN (next_trial), next_trial, 0)) 2381 && eligible_for_delay (insn, slots_filled, next_trial, flags) 2382 && ! can_throw_internal (trial)) 2383 { 2384 /* See comment in relax_delay_slots about necessity of using 2385 next_real_insn here. */ 2386 rtx new_label = next_real_insn (next_trial); 2387 2388 if (new_label != 0) 2389 new_label = get_label_before (new_label); 2390 else 2391 new_label = find_end_label (); 2392 2393 if (new_label) 2394 { 2395 delay_list 2396 = add_to_delay_list (copy_rtx (next_trial), delay_list); 2397 slots_filled++; 2398 reorg_redirect_jump (trial, new_label); 2399 2400 /* If we merged because we both jumped to the same place, 2401 redirect the original insn also. */ 2402 if (target) 2403 reorg_redirect_jump (insn, new_label); 2404 } 2405 } 2406 } 2407 2408 /* If this is an unconditional jump, then try to get insns from the 2409 target of the jump. */ 2410 if (JUMP_P (insn) 2411 && simplejump_p (insn) 2412 && slots_filled != slots_to_fill) 2413 delay_list 2414 = fill_slots_from_thread (insn, const_true_rtx, 2415 next_active_insn (JUMP_LABEL (insn)), 2416 NULL, 1, 1, 2417 own_thread_p (JUMP_LABEL (insn), 2418 JUMP_LABEL (insn), 0), 2419 slots_to_fill, &slots_filled, 2420 delay_list); 2421 2422 if (delay_list) 2423 unfilled_slots_base[i] 2424 = emit_delay_sequence (insn, delay_list, slots_filled); 2425 2426 if (slots_to_fill == slots_filled) 2427 unfilled_slots_base[i] = 0; 2428 2429 note_delay_statistics (slots_filled, 0); 2430 } 2431 2432#ifdef DELAY_SLOTS_FOR_EPILOGUE 2433 /* See if the epilogue needs any delay slots. Try to fill them if so. 2434 The only thing we can do is scan backwards from the end of the 2435 function. If we did this in a previous pass, it is incorrect to do it 2436 again. */ 2437 if (current_function_epilogue_delay_list) 2438 return; 2439 2440 slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE; 2441 if (slots_to_fill == 0) 2442 return; 2443 2444 slots_filled = 0; 2445 CLEAR_RESOURCE (&set); 2446 2447 /* The frame pointer and stack pointer are needed at the beginning of 2448 the epilogue, so instructions setting them can not be put in the 2449 epilogue delay slot. However, everything else needed at function 2450 end is safe, so we don't want to use end_of_function_needs here. */ 2451 CLEAR_RESOURCE (&needed); 2452 if (frame_pointer_needed) 2453 { 2454 SET_HARD_REG_BIT (needed.regs, FRAME_POINTER_REGNUM); 2455#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 2456 SET_HARD_REG_BIT (needed.regs, HARD_FRAME_POINTER_REGNUM); 2457#endif 2458 if (! EXIT_IGNORE_STACK 2459 || current_function_sp_is_unchanging) 2460 SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM); 2461 } 2462 else 2463 SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM); 2464 2465#ifdef EPILOGUE_USES 2466 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 2467 { 2468 if (EPILOGUE_USES (i)) 2469 SET_HARD_REG_BIT (needed.regs, i); 2470 } 2471#endif 2472 2473 for (trial = get_last_insn (); ! stop_search_p (trial, 1); 2474 trial = PREV_INSN (trial)) 2475 { 2476 if (NOTE_P (trial)) 2477 continue; 2478 pat = PATTERN (trial); 2479 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 2480 continue; 2481 2482 if (! insn_references_resource_p (trial, &set, 1) 2483 && ! insn_sets_resource_p (trial, &needed, 1) 2484 && ! insn_sets_resource_p (trial, &set, 1) 2485#ifdef HAVE_cc0 2486 /* Don't want to mess with cc0 here. */ 2487 && ! reg_mentioned_p (cc0_rtx, pat) 2488#endif 2489 && ! can_throw_internal (trial)) 2490 { 2491 trial = try_split (pat, trial, 1); 2492 if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled)) 2493 { 2494 /* Here as well we are searching backward, so put the 2495 insns we find on the head of the list. */ 2496 2497 current_function_epilogue_delay_list 2498 = gen_rtx_INSN_LIST (VOIDmode, trial, 2499 current_function_epilogue_delay_list); 2500 mark_end_of_function_resources (trial, 1); 2501 update_block (trial, trial); 2502 delete_related_insns (trial); 2503 2504 /* Clear deleted bit so final.c will output the insn. */ 2505 INSN_DELETED_P (trial) = 0; 2506 2507 if (slots_to_fill == ++slots_filled) 2508 break; 2509 continue; 2510 } 2511 } 2512 2513 mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL); 2514 mark_referenced_resources (trial, &needed, 1); 2515 } 2516 2517 note_delay_statistics (slots_filled, 0); 2518#endif 2519} 2520 2521/* Try to find insns to place in delay slots. 2522 2523 INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION 2524 or is an unconditional branch if CONDITION is const_true_rtx. 2525 *PSLOTS_FILLED is updated with the number of slots that we have filled. 2526 2527 THREAD is a flow-of-control, either the insns to be executed if the 2528 branch is true or if the branch is false, THREAD_IF_TRUE says which. 2529 2530 OPPOSITE_THREAD is the thread in the opposite direction. It is used 2531 to see if any potential delay slot insns set things needed there. 2532 2533 LIKELY is nonzero if it is extremely likely that the branch will be 2534 taken and THREAD_IF_TRUE is set. This is used for the branch at the 2535 end of a loop back up to the top. 2536 2537 OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the 2538 thread. I.e., it is the fallthrough code of our jump or the target of the 2539 jump when we are the only jump going there. 2540 2541 If OWN_THREAD is false, it must be the "true" thread of a jump. In that 2542 case, we can only take insns from the head of the thread for our delay 2543 slot. We then adjust the jump to point after the insns we have taken. */ 2544 2545static rtx 2546fill_slots_from_thread (rtx insn, rtx condition, rtx thread, 2547 rtx opposite_thread, int likely, int thread_if_true, 2548 int own_thread, int slots_to_fill, 2549 int *pslots_filled, rtx delay_list) 2550{ 2551 rtx new_thread; 2552 struct resources opposite_needed, set, needed; 2553 rtx trial; 2554 int lose = 0; 2555 int must_annul = 0; 2556 int flags; 2557 2558 /* Validate our arguments. */ 2559 gcc_assert(condition != const_true_rtx || thread_if_true); 2560 gcc_assert(own_thread || thread_if_true); 2561 2562 flags = get_jump_flags (insn, JUMP_LABEL (insn)); 2563 2564 /* If our thread is the end of subroutine, we can't get any delay 2565 insns from that. */ 2566 if (thread == 0) 2567 return delay_list; 2568 2569 /* If this is an unconditional branch, nothing is needed at the 2570 opposite thread. Otherwise, compute what is needed there. */ 2571 if (condition == const_true_rtx) 2572 CLEAR_RESOURCE (&opposite_needed); 2573 else 2574 mark_target_live_regs (get_insns (), opposite_thread, &opposite_needed); 2575 2576 /* If the insn at THREAD can be split, do it here to avoid having to 2577 update THREAD and NEW_THREAD if it is done in the loop below. Also 2578 initialize NEW_THREAD. */ 2579 2580 new_thread = thread = try_split (PATTERN (thread), thread, 0); 2581 2582 /* Scan insns at THREAD. We are looking for an insn that can be removed 2583 from THREAD (it neither sets nor references resources that were set 2584 ahead of it and it doesn't set anything needs by the insns ahead of 2585 it) and that either can be placed in an annulling insn or aren't 2586 needed at OPPOSITE_THREAD. */ 2587 2588 CLEAR_RESOURCE (&needed); 2589 CLEAR_RESOURCE (&set); 2590 2591 /* If we do not own this thread, we must stop as soon as we find 2592 something that we can't put in a delay slot, since all we can do 2593 is branch into THREAD at a later point. Therefore, labels stop 2594 the search if this is not the `true' thread. */ 2595 2596 for (trial = thread; 2597 ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread); 2598 trial = next_nonnote_insn (trial)) 2599 { 2600 rtx pat, old_trial; 2601 2602 /* If we have passed a label, we no longer own this thread. */ 2603 if (LABEL_P (trial)) 2604 { 2605 own_thread = 0; 2606 continue; 2607 } 2608 2609 pat = PATTERN (trial); 2610 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 2611 continue; 2612 2613 /* If TRIAL conflicts with the insns ahead of it, we lose. Also, 2614 don't separate or copy insns that set and use CC0. */ 2615 if (! insn_references_resource_p (trial, &set, 1) 2616 && ! insn_sets_resource_p (trial, &set, 1) 2617 && ! insn_sets_resource_p (trial, &needed, 1) 2618#ifdef HAVE_cc0 2619 && ! (reg_mentioned_p (cc0_rtx, pat) 2620 && (! own_thread || ! sets_cc0_p (pat))) 2621#endif 2622 && ! can_throw_internal (trial)) 2623 { 2624 rtx prior_insn; 2625 2626 /* If TRIAL is redundant with some insn before INSN, we don't 2627 actually need to add it to the delay list; we can merely pretend 2628 we did. */ 2629 if ((prior_insn = redundant_insn (trial, insn, delay_list))) 2630 { 2631 fix_reg_dead_note (prior_insn, insn); 2632 if (own_thread) 2633 { 2634 update_block (trial, thread); 2635 if (trial == thread) 2636 { 2637 thread = next_active_insn (thread); 2638 if (new_thread == trial) 2639 new_thread = thread; 2640 } 2641 2642 delete_related_insns (trial); 2643 } 2644 else 2645 { 2646 update_reg_unused_notes (prior_insn, trial); 2647 new_thread = next_active_insn (trial); 2648 } 2649 2650 continue; 2651 } 2652 2653 /* There are two ways we can win: If TRIAL doesn't set anything 2654 needed at the opposite thread and can't trap, or if it can 2655 go into an annulled delay slot. */ 2656 if (!must_annul 2657 && (condition == const_true_rtx 2658 || (! insn_sets_resource_p (trial, &opposite_needed, 1) 2659 && ! may_trap_or_fault_p (pat)))) 2660 { 2661 old_trial = trial; 2662 trial = try_split (pat, trial, 0); 2663 if (new_thread == old_trial) 2664 new_thread = trial; 2665 if (thread == old_trial) 2666 thread = trial; 2667 pat = PATTERN (trial); 2668 if (eligible_for_delay (insn, *pslots_filled, trial, flags)) 2669 goto winner; 2670 } 2671 else if (0 2672#ifdef ANNUL_IFTRUE_SLOTS 2673 || ! thread_if_true 2674#endif 2675#ifdef ANNUL_IFFALSE_SLOTS 2676 || thread_if_true 2677#endif 2678 ) 2679 { 2680 old_trial = trial; 2681 trial = try_split (pat, trial, 0); 2682 if (new_thread == old_trial) 2683 new_thread = trial; 2684 if (thread == old_trial) 2685 thread = trial; 2686 pat = PATTERN (trial); 2687 if ((must_annul || delay_list == NULL) && (thread_if_true 2688 ? check_annul_list_true_false (0, delay_list) 2689 && eligible_for_annul_false (insn, *pslots_filled, trial, flags) 2690 : check_annul_list_true_false (1, delay_list) 2691 && eligible_for_annul_true (insn, *pslots_filled, trial, flags))) 2692 { 2693 rtx temp; 2694 2695 must_annul = 1; 2696 winner: 2697 2698#ifdef HAVE_cc0 2699 if (reg_mentioned_p (cc0_rtx, pat)) 2700 link_cc0_insns (trial); 2701#endif 2702 2703 /* If we own this thread, delete the insn. If this is the 2704 destination of a branch, show that a basic block status 2705 may have been updated. In any case, mark the new 2706 starting point of this thread. */ 2707 if (own_thread) 2708 { 2709 rtx note; 2710 2711 update_block (trial, thread); 2712 if (trial == thread) 2713 { 2714 thread = next_active_insn (thread); 2715 if (new_thread == trial) 2716 new_thread = thread; 2717 } 2718 2719 /* We are moving this insn, not deleting it. We must 2720 temporarily increment the use count on any referenced 2721 label lest it be deleted by delete_related_insns. */ 2722 note = find_reg_note (trial, REG_LABEL, 0); 2723 /* REG_LABEL could be NOTE_INSN_DELETED_LABEL too. */ 2724 if (note && LABEL_P (XEXP (note, 0))) 2725 LABEL_NUSES (XEXP (note, 0))++; 2726 2727 delete_related_insns (trial); 2728 2729 if (note && LABEL_P (XEXP (note, 0))) 2730 LABEL_NUSES (XEXP (note, 0))--; 2731 } 2732 else 2733 new_thread = next_active_insn (trial); 2734 2735 temp = own_thread ? trial : copy_rtx (trial); 2736 if (thread_if_true) 2737 INSN_FROM_TARGET_P (temp) = 1; 2738 2739 delay_list = add_to_delay_list (temp, delay_list); 2740 2741 if (slots_to_fill == ++(*pslots_filled)) 2742 { 2743 /* Even though we have filled all the slots, we 2744 may be branching to a location that has a 2745 redundant insn. Skip any if so. */ 2746 while (new_thread && ! own_thread 2747 && ! insn_sets_resource_p (new_thread, &set, 1) 2748 && ! insn_sets_resource_p (new_thread, &needed, 1) 2749 && ! insn_references_resource_p (new_thread, 2750 &set, 1) 2751 && (prior_insn 2752 = redundant_insn (new_thread, insn, 2753 delay_list))) 2754 { 2755 /* We know we do not own the thread, so no need 2756 to call update_block and delete_insn. */ 2757 fix_reg_dead_note (prior_insn, insn); 2758 update_reg_unused_notes (prior_insn, new_thread); 2759 new_thread = next_active_insn (new_thread); 2760 } 2761 break; 2762 } 2763 2764 continue; 2765 } 2766 } 2767 } 2768 2769 /* This insn can't go into a delay slot. */ 2770 lose = 1; 2771 mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL); 2772 mark_referenced_resources (trial, &needed, 1); 2773 2774 /* Ensure we don't put insns between the setting of cc and the comparison 2775 by moving a setting of cc into an earlier delay slot since these insns 2776 could clobber the condition code. */ 2777 set.cc = 1; 2778 2779 /* If this insn is a register-register copy and the next insn has 2780 a use of our destination, change it to use our source. That way, 2781 it will become a candidate for our delay slot the next time 2782 through this loop. This case occurs commonly in loops that 2783 scan a list. 2784 2785 We could check for more complex cases than those tested below, 2786 but it doesn't seem worth it. It might also be a good idea to try 2787 to swap the two insns. That might do better. 2788 2789 We can't do this if the next insn modifies our destination, because 2790 that would make the replacement into the insn invalid. We also can't 2791 do this if it modifies our source, because it might be an earlyclobber 2792 operand. This latter test also prevents updating the contents of 2793 a PRE_INC. We also can't do this if there's overlap of source and 2794 destination. Overlap may happen for larger-than-register-size modes. */ 2795 2796 if (NONJUMP_INSN_P (trial) && GET_CODE (pat) == SET 2797 && REG_P (SET_SRC (pat)) 2798 && REG_P (SET_DEST (pat)) 2799 && !reg_overlap_mentioned_p (SET_DEST (pat), SET_SRC (pat))) 2800 { 2801 rtx next = next_nonnote_insn (trial); 2802 2803 if (next && NONJUMP_INSN_P (next) 2804 && GET_CODE (PATTERN (next)) != USE 2805 && ! reg_set_p (SET_DEST (pat), next) 2806 && ! reg_set_p (SET_SRC (pat), next) 2807 && reg_referenced_p (SET_DEST (pat), PATTERN (next)) 2808 && ! modified_in_p (SET_DEST (pat), next)) 2809 validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next); 2810 } 2811 } 2812 2813 /* If we stopped on a branch insn that has delay slots, see if we can 2814 steal some of the insns in those slots. */ 2815 if (trial && NONJUMP_INSN_P (trial) 2816 && GET_CODE (PATTERN (trial)) == SEQUENCE 2817 && JUMP_P (XVECEXP (PATTERN (trial), 0, 0))) 2818 { 2819 /* If this is the `true' thread, we will want to follow the jump, 2820 so we can only do this if we have taken everything up to here. */ 2821 if (thread_if_true && trial == new_thread) 2822 { 2823 delay_list 2824 = steal_delay_list_from_target (insn, condition, PATTERN (trial), 2825 delay_list, &set, &needed, 2826 &opposite_needed, slots_to_fill, 2827 pslots_filled, &must_annul, 2828 &new_thread); 2829 /* If we owned the thread and are told that it branched 2830 elsewhere, make sure we own the thread at the new location. */ 2831 if (own_thread && trial != new_thread) 2832 own_thread = own_thread_p (new_thread, new_thread, 0); 2833 } 2834 else if (! thread_if_true) 2835 delay_list 2836 = steal_delay_list_from_fallthrough (insn, condition, 2837 PATTERN (trial), 2838 delay_list, &set, &needed, 2839 &opposite_needed, slots_to_fill, 2840 pslots_filled, &must_annul); 2841 } 2842 2843 /* If we haven't found anything for this delay slot and it is very 2844 likely that the branch will be taken, see if the insn at our target 2845 increments or decrements a register with an increment that does not 2846 depend on the destination register. If so, try to place the opposite 2847 arithmetic insn after the jump insn and put the arithmetic insn in the 2848 delay slot. If we can't do this, return. */ 2849 if (delay_list == 0 && likely && new_thread 2850 && NONJUMP_INSN_P (new_thread) 2851 && GET_CODE (PATTERN (new_thread)) != ASM_INPUT 2852 && asm_noperands (PATTERN (new_thread)) < 0) 2853 { 2854 rtx pat = PATTERN (new_thread); 2855 rtx dest; 2856 rtx src; 2857 2858 trial = new_thread; 2859 pat = PATTERN (trial); 2860 2861 if (!NONJUMP_INSN_P (trial) 2862 || GET_CODE (pat) != SET 2863 || ! eligible_for_delay (insn, 0, trial, flags) 2864 || can_throw_internal (trial)) 2865 return 0; 2866 2867 dest = SET_DEST (pat), src = SET_SRC (pat); 2868 if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS) 2869 && rtx_equal_p (XEXP (src, 0), dest) 2870 && (!FLOAT_MODE_P (GET_MODE (src)) 2871 || flag_unsafe_math_optimizations) 2872 && ! reg_overlap_mentioned_p (dest, XEXP (src, 1)) 2873 && ! side_effects_p (pat)) 2874 { 2875 rtx other = XEXP (src, 1); 2876 rtx new_arith; 2877 rtx ninsn; 2878 2879 /* If this is a constant adjustment, use the same code with 2880 the negated constant. Otherwise, reverse the sense of the 2881 arithmetic. */ 2882 if (GET_CODE (other) == CONST_INT) 2883 new_arith = gen_rtx_fmt_ee (GET_CODE (src), GET_MODE (src), dest, 2884 negate_rtx (GET_MODE (src), other)); 2885 else 2886 new_arith = gen_rtx_fmt_ee (GET_CODE (src) == PLUS ? MINUS : PLUS, 2887 GET_MODE (src), dest, other); 2888 2889 ninsn = emit_insn_after (gen_rtx_SET (VOIDmode, dest, new_arith), 2890 insn); 2891 2892 if (recog_memoized (ninsn) < 0 2893 || (extract_insn (ninsn), ! constrain_operands (1))) 2894 { 2895 delete_related_insns (ninsn); 2896 return 0; 2897 } 2898 2899 if (own_thread) 2900 { 2901 update_block (trial, thread); 2902 if (trial == thread) 2903 { 2904 thread = next_active_insn (thread); 2905 if (new_thread == trial) 2906 new_thread = thread; 2907 } 2908 delete_related_insns (trial); 2909 } 2910 else 2911 new_thread = next_active_insn (trial); 2912 2913 ninsn = own_thread ? trial : copy_rtx (trial); 2914 if (thread_if_true) 2915 INSN_FROM_TARGET_P (ninsn) = 1; 2916 2917 delay_list = add_to_delay_list (ninsn, NULL_RTX); 2918 (*pslots_filled)++; 2919 } 2920 } 2921 2922 if (delay_list && must_annul) 2923 INSN_ANNULLED_BRANCH_P (insn) = 1; 2924 2925 /* If we are to branch into the middle of this thread, find an appropriate 2926 label or make a new one if none, and redirect INSN to it. If we hit the 2927 end of the function, use the end-of-function label. */ 2928 if (new_thread != thread) 2929 { 2930 rtx label; 2931 2932 gcc_assert (thread_if_true); 2933 2934 if (new_thread && JUMP_P (new_thread) 2935 && (simplejump_p (new_thread) 2936 || GET_CODE (PATTERN (new_thread)) == RETURN) 2937 && redirect_with_delay_list_safe_p (insn, 2938 JUMP_LABEL (new_thread), 2939 delay_list)) 2940 new_thread = follow_jumps (JUMP_LABEL (new_thread)); 2941 2942 if (new_thread == 0) 2943 label = find_end_label (); 2944 else if (LABEL_P (new_thread)) 2945 label = new_thread; 2946 else 2947 label = get_label_before (new_thread); 2948 2949 if (label) 2950 reorg_redirect_jump (insn, label); 2951 } 2952 2953 return delay_list; 2954} 2955 2956/* Make another attempt to find insns to place in delay slots. 2957 2958 We previously looked for insns located in front of the delay insn 2959 and, for non-jump delay insns, located behind the delay insn. 2960 2961 Here only try to schedule jump insns and try to move insns from either 2962 the target or the following insns into the delay slot. If annulling is 2963 supported, we will be likely to do this. Otherwise, we can do this only 2964 if safe. */ 2965 2966static void 2967fill_eager_delay_slots (void) 2968{ 2969 rtx insn; 2970 int i; 2971 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base; 2972 2973 for (i = 0; i < num_unfilled_slots; i++) 2974 { 2975 rtx condition; 2976 rtx target_label, insn_at_target, fallthrough_insn; 2977 rtx delay_list = 0; 2978 int own_target; 2979 int own_fallthrough; 2980 int prediction, slots_to_fill, slots_filled; 2981 2982 insn = unfilled_slots_base[i]; 2983 if (insn == 0 2984 || INSN_DELETED_P (insn) 2985 || !JUMP_P (insn) 2986 || ! (condjump_p (insn) || condjump_in_parallel_p (insn))) 2987 continue; 2988 2989 slots_to_fill = num_delay_slots (insn); 2990 /* Some machine description have defined instructions to have 2991 delay slots only in certain circumstances which may depend on 2992 nearby insns (which change due to reorg's actions). 2993 2994 For example, the PA port normally has delay slots for unconditional 2995 jumps. 2996 2997 However, the PA port claims such jumps do not have a delay slot 2998 if they are immediate successors of certain CALL_INSNs. This 2999 allows the port to favor filling the delay slot of the call with 3000 the unconditional jump. */ 3001 if (slots_to_fill == 0) 3002 continue; 3003 3004 slots_filled = 0; 3005 target_label = JUMP_LABEL (insn); 3006 condition = get_branch_condition (insn, target_label); 3007 3008 if (condition == 0) 3009 continue; 3010 3011 /* Get the next active fallthrough and target insns and see if we own 3012 them. Then see whether the branch is likely true. We don't need 3013 to do a lot of this for unconditional branches. */ 3014 3015 insn_at_target = next_active_insn (target_label); 3016 own_target = own_thread_p (target_label, target_label, 0); 3017 3018 if (condition == const_true_rtx) 3019 { 3020 own_fallthrough = 0; 3021 fallthrough_insn = 0; 3022 prediction = 2; 3023 } 3024 else 3025 { 3026 fallthrough_insn = next_active_insn (insn); 3027 own_fallthrough = own_thread_p (NEXT_INSN (insn), NULL_RTX, 1); 3028 prediction = mostly_true_jump (insn, condition); 3029 } 3030 3031 /* If this insn is expected to branch, first try to get insns from our 3032 target, then our fallthrough insns. If it is not expected to branch, 3033 try the other order. */ 3034 3035 if (prediction > 0) 3036 { 3037 delay_list 3038 = fill_slots_from_thread (insn, condition, insn_at_target, 3039 fallthrough_insn, prediction == 2, 1, 3040 own_target, 3041 slots_to_fill, &slots_filled, delay_list); 3042 3043 if (delay_list == 0 && own_fallthrough) 3044 { 3045 /* Even though we didn't find anything for delay slots, 3046 we might have found a redundant insn which we deleted 3047 from the thread that was filled. So we have to recompute 3048 the next insn at the target. */ 3049 target_label = JUMP_LABEL (insn); 3050 insn_at_target = next_active_insn (target_label); 3051 3052 delay_list 3053 = fill_slots_from_thread (insn, condition, fallthrough_insn, 3054 insn_at_target, 0, 0, 3055 own_fallthrough, 3056 slots_to_fill, &slots_filled, 3057 delay_list); 3058 } 3059 } 3060 else 3061 { 3062 if (own_fallthrough) 3063 delay_list 3064 = fill_slots_from_thread (insn, condition, fallthrough_insn, 3065 insn_at_target, 0, 0, 3066 own_fallthrough, 3067 slots_to_fill, &slots_filled, 3068 delay_list); 3069 3070 if (delay_list == 0) 3071 delay_list 3072 = fill_slots_from_thread (insn, condition, insn_at_target, 3073 next_active_insn (insn), 0, 1, 3074 own_target, 3075 slots_to_fill, &slots_filled, 3076 delay_list); 3077 } 3078 3079 if (delay_list) 3080 unfilled_slots_base[i] 3081 = emit_delay_sequence (insn, delay_list, slots_filled); 3082 3083 if (slots_to_fill == slots_filled) 3084 unfilled_slots_base[i] = 0; 3085 3086 note_delay_statistics (slots_filled, 1); 3087 } 3088} 3089 3090/* Once we have tried two ways to fill a delay slot, make a pass over the 3091 code to try to improve the results and to do such things as more jump 3092 threading. */ 3093 3094static void 3095relax_delay_slots (rtx first) 3096{ 3097 rtx insn, next, pat; 3098 rtx trial, delay_insn, target_label; 3099 3100 /* Look at every JUMP_INSN and see if we can improve it. */ 3101 for (insn = first; insn; insn = next) 3102 { 3103 rtx other; 3104 3105 next = next_active_insn (insn); 3106 3107 /* If this is a jump insn, see if it now jumps to a jump, jumps to 3108 the next insn, or jumps to a label that is not the last of a 3109 group of consecutive labels. */ 3110 if (JUMP_P (insn) 3111 && (condjump_p (insn) || condjump_in_parallel_p (insn)) 3112 && (target_label = JUMP_LABEL (insn)) != 0) 3113 { 3114 target_label = skip_consecutive_labels (follow_jumps (target_label)); 3115 if (target_label == 0) 3116 target_label = find_end_label (); 3117 3118 if (target_label && next_active_insn (target_label) == next 3119 && ! condjump_in_parallel_p (insn)) 3120 { 3121 delete_jump (insn); 3122 continue; 3123 } 3124 3125 if (target_label && target_label != JUMP_LABEL (insn)) 3126 reorg_redirect_jump (insn, target_label); 3127 3128 /* See if this jump conditionally branches around an unconditional 3129 jump. If so, invert this jump and point it to the target of the 3130 second jump. */ 3131 if (next && JUMP_P (next) 3132 && any_condjump_p (insn) 3133 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN) 3134 && target_label 3135 && next_active_insn (target_label) == next_active_insn (next) 3136 && no_labels_between_p (insn, next)) 3137 { 3138 rtx label = JUMP_LABEL (next); 3139 3140 /* Be careful how we do this to avoid deleting code or 3141 labels that are momentarily dead. See similar optimization 3142 in jump.c. 3143 3144 We also need to ensure we properly handle the case when 3145 invert_jump fails. */ 3146 3147 ++LABEL_NUSES (target_label); 3148 if (label) 3149 ++LABEL_NUSES (label); 3150 3151 if (invert_jump (insn, label, 1)) 3152 { 3153 delete_related_insns (next); 3154 next = insn; 3155 } 3156 3157 if (label) 3158 --LABEL_NUSES (label); 3159 3160 if (--LABEL_NUSES (target_label) == 0) 3161 delete_related_insns (target_label); 3162 3163 continue; 3164 } 3165 } 3166 3167 /* If this is an unconditional jump and the previous insn is a 3168 conditional jump, try reversing the condition of the previous 3169 insn and swapping our targets. The next pass might be able to 3170 fill the slots. 3171 3172 Don't do this if we expect the conditional branch to be true, because 3173 we would then be making the more common case longer. */ 3174 3175 if (JUMP_P (insn) 3176 && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN) 3177 && (other = prev_active_insn (insn)) != 0 3178 && any_condjump_p (other) 3179 && no_labels_between_p (other, insn) 3180 && 0 > mostly_true_jump (other, 3181 get_branch_condition (other, 3182 JUMP_LABEL (other)))) 3183 { 3184 rtx other_target = JUMP_LABEL (other); 3185 target_label = JUMP_LABEL (insn); 3186 3187 if (invert_jump (other, target_label, 0)) 3188 reorg_redirect_jump (insn, other_target); 3189 } 3190 3191 /* Now look only at cases where we have filled a delay slot. */ 3192 if (!NONJUMP_INSN_P (insn) 3193 || GET_CODE (PATTERN (insn)) != SEQUENCE) 3194 continue; 3195 3196 pat = PATTERN (insn); 3197 delay_insn = XVECEXP (pat, 0, 0); 3198 3199 /* See if the first insn in the delay slot is redundant with some 3200 previous insn. Remove it from the delay slot if so; then set up 3201 to reprocess this insn. */ 3202 if (redundant_insn (XVECEXP (pat, 0, 1), delay_insn, 0)) 3203 { 3204 delete_from_delay_slot (XVECEXP (pat, 0, 1)); 3205 next = prev_active_insn (next); 3206 continue; 3207 } 3208 3209 /* See if we have a RETURN insn with a filled delay slot followed 3210 by a RETURN insn with an unfilled a delay slot. If so, we can delete 3211 the first RETURN (but not its delay insn). This gives the same 3212 effect in fewer instructions. 3213 3214 Only do so if optimizing for size since this results in slower, but 3215 smaller code. */ 3216 if (optimize_size 3217 && GET_CODE (PATTERN (delay_insn)) == RETURN 3218 && next 3219 && JUMP_P (next) 3220 && GET_CODE (PATTERN (next)) == RETURN) 3221 { 3222 rtx after; 3223 int i; 3224 3225 /* Delete the RETURN and just execute the delay list insns. 3226 3227 We do this by deleting the INSN containing the SEQUENCE, then 3228 re-emitting the insns separately, and then deleting the RETURN. 3229 This allows the count of the jump target to be properly 3230 decremented. */ 3231 3232 /* Clear the from target bit, since these insns are no longer 3233 in delay slots. */ 3234 for (i = 0; i < XVECLEN (pat, 0); i++) 3235 INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0; 3236 3237 trial = PREV_INSN (insn); 3238 delete_related_insns (insn); 3239 gcc_assert (GET_CODE (pat) == SEQUENCE); 3240 after = trial; 3241 for (i = 0; i < XVECLEN (pat, 0); i++) 3242 { 3243 rtx this_insn = XVECEXP (pat, 0, i); 3244 add_insn_after (this_insn, after); 3245 after = this_insn; 3246 } 3247 delete_scheduled_jump (delay_insn); 3248 continue; 3249 } 3250 3251 /* Now look only at the cases where we have a filled JUMP_INSN. */ 3252 if (!JUMP_P (XVECEXP (PATTERN (insn), 0, 0)) 3253 || ! (condjump_p (XVECEXP (PATTERN (insn), 0, 0)) 3254 || condjump_in_parallel_p (XVECEXP (PATTERN (insn), 0, 0)))) 3255 continue; 3256 3257 target_label = JUMP_LABEL (delay_insn); 3258 3259 if (target_label) 3260 { 3261 /* If this jump goes to another unconditional jump, thread it, but 3262 don't convert a jump into a RETURN here. */ 3263 trial = skip_consecutive_labels (follow_jumps (target_label)); 3264 if (trial == 0) 3265 trial = find_end_label (); 3266 3267 if (trial && trial != target_label 3268 && redirect_with_delay_slots_safe_p (delay_insn, trial, insn)) 3269 { 3270 reorg_redirect_jump (delay_insn, trial); 3271 target_label = trial; 3272 } 3273 3274 /* If the first insn at TARGET_LABEL is redundant with a previous 3275 insn, redirect the jump to the following insn process again. */ 3276 trial = next_active_insn (target_label); 3277 if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE 3278 && redundant_insn (trial, insn, 0) 3279 && ! can_throw_internal (trial)) 3280 { 3281 /* Figure out where to emit the special USE insn so we don't 3282 later incorrectly compute register live/death info. */ 3283 rtx tmp = next_active_insn (trial); 3284 if (tmp == 0) 3285 tmp = find_end_label (); 3286 3287 if (tmp) 3288 { 3289 /* Insert the special USE insn and update dataflow info. */ 3290 update_block (trial, tmp); 3291 3292 /* Now emit a label before the special USE insn, and 3293 redirect our jump to the new label. */ 3294 target_label = get_label_before (PREV_INSN (tmp)); 3295 reorg_redirect_jump (delay_insn, target_label); 3296 next = insn; 3297 continue; 3298 } 3299 } 3300 3301 /* Similarly, if it is an unconditional jump with one insn in its 3302 delay list and that insn is redundant, thread the jump. */ 3303 if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE 3304 && XVECLEN (PATTERN (trial), 0) == 2 3305 && JUMP_P (XVECEXP (PATTERN (trial), 0, 0)) 3306 && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0)) 3307 || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN) 3308 && redundant_insn (XVECEXP (PATTERN (trial), 0, 1), insn, 0)) 3309 { 3310 target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0)); 3311 if (target_label == 0) 3312 target_label = find_end_label (); 3313 3314 if (target_label 3315 && redirect_with_delay_slots_safe_p (delay_insn, target_label, 3316 insn)) 3317 { 3318 reorg_redirect_jump (delay_insn, target_label); 3319 next = insn; 3320 continue; 3321 } 3322 } 3323 } 3324 3325 if (! INSN_ANNULLED_BRANCH_P (delay_insn) 3326 && prev_active_insn (target_label) == insn 3327 && ! condjump_in_parallel_p (delay_insn) 3328#ifdef HAVE_cc0 3329 /* If the last insn in the delay slot sets CC0 for some insn, 3330 various code assumes that it is in a delay slot. We could 3331 put it back where it belonged and delete the register notes, 3332 but it doesn't seem worthwhile in this uncommon case. */ 3333 && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1), 3334 REG_CC_USER, NULL_RTX) 3335#endif 3336 ) 3337 { 3338 rtx after; 3339 int i; 3340 3341 /* All this insn does is execute its delay list and jump to the 3342 following insn. So delete the jump and just execute the delay 3343 list insns. 3344 3345 We do this by deleting the INSN containing the SEQUENCE, then 3346 re-emitting the insns separately, and then deleting the jump. 3347 This allows the count of the jump target to be properly 3348 decremented. */ 3349 3350 /* Clear the from target bit, since these insns are no longer 3351 in delay slots. */ 3352 for (i = 0; i < XVECLEN (pat, 0); i++) 3353 INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0; 3354 3355 trial = PREV_INSN (insn); 3356 delete_related_insns (insn); 3357 gcc_assert (GET_CODE (pat) == SEQUENCE); 3358 after = trial; 3359 for (i = 0; i < XVECLEN (pat, 0); i++) 3360 { 3361 rtx this_insn = XVECEXP (pat, 0, i); 3362 add_insn_after (this_insn, after); 3363 after = this_insn; 3364 } 3365 delete_scheduled_jump (delay_insn); 3366 continue; 3367 } 3368 3369 /* See if this is an unconditional jump around a single insn which is 3370 identical to the one in its delay slot. In this case, we can just 3371 delete the branch and the insn in its delay slot. */ 3372 if (next && NONJUMP_INSN_P (next) 3373 && prev_label (next_active_insn (next)) == target_label 3374 && simplejump_p (insn) 3375 && XVECLEN (pat, 0) == 2 3376 && rtx_equal_p (PATTERN (next), PATTERN (XVECEXP (pat, 0, 1)))) 3377 { 3378 delete_related_insns (insn); 3379 continue; 3380 } 3381 3382 /* See if this jump (with its delay slots) conditionally branches 3383 around an unconditional jump (without delay slots). If so, invert 3384 this jump and point it to the target of the second jump. We cannot 3385 do this for annulled jumps, though. Again, don't convert a jump to 3386 a RETURN here. */ 3387 if (! INSN_ANNULLED_BRANCH_P (delay_insn) 3388 && any_condjump_p (delay_insn) 3389 && next && JUMP_P (next) 3390 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN) 3391 && next_active_insn (target_label) == next_active_insn (next) 3392 && no_labels_between_p (insn, next)) 3393 { 3394 rtx label = JUMP_LABEL (next); 3395 rtx old_label = JUMP_LABEL (delay_insn); 3396 3397 if (label == 0) 3398 label = find_end_label (); 3399 3400 /* find_end_label can generate a new label. Check this first. */ 3401 if (label 3402 && no_labels_between_p (insn, next) 3403 && redirect_with_delay_slots_safe_p (delay_insn, label, insn)) 3404 { 3405 /* Be careful how we do this to avoid deleting code or labels 3406 that are momentarily dead. See similar optimization in 3407 jump.c */ 3408 if (old_label) 3409 ++LABEL_NUSES (old_label); 3410 3411 if (invert_jump (delay_insn, label, 1)) 3412 { 3413 int i; 3414 3415 /* Must update the INSN_FROM_TARGET_P bits now that 3416 the branch is reversed, so that mark_target_live_regs 3417 will handle the delay slot insn correctly. */ 3418 for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++) 3419 { 3420 rtx slot = XVECEXP (PATTERN (insn), 0, i); 3421 INSN_FROM_TARGET_P (slot) = ! INSN_FROM_TARGET_P (slot); 3422 } 3423 3424 delete_related_insns (next); 3425 next = insn; 3426 } 3427 3428 if (old_label && --LABEL_NUSES (old_label) == 0) 3429 delete_related_insns (old_label); 3430 continue; 3431 } 3432 } 3433 3434 /* If we own the thread opposite the way this insn branches, see if we 3435 can merge its delay slots with following insns. */ 3436 if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1)) 3437 && own_thread_p (NEXT_INSN (insn), 0, 1)) 3438 try_merge_delay_insns (insn, next); 3439 else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1)) 3440 && own_thread_p (target_label, target_label, 0)) 3441 try_merge_delay_insns (insn, next_active_insn (target_label)); 3442 3443 /* If we get here, we haven't deleted INSN. But we may have deleted 3444 NEXT, so recompute it. */ 3445 next = next_active_insn (insn); 3446 } 3447} 3448 3449#ifdef HAVE_return 3450 3451/* Look for filled jumps to the end of function label. We can try to convert 3452 them into RETURN insns if the insns in the delay slot are valid for the 3453 RETURN as well. */ 3454 3455static void 3456make_return_insns (rtx first) 3457{ 3458 rtx insn, jump_insn, pat; 3459 rtx real_return_label = end_of_function_label; 3460 int slots, i; 3461 3462#ifdef DELAY_SLOTS_FOR_EPILOGUE 3463 /* If a previous pass filled delay slots in the epilogue, things get a 3464 bit more complicated, as those filler insns would generally (without 3465 data flow analysis) have to be executed after any existing branch 3466 delay slot filler insns. It is also unknown whether such a 3467 transformation would actually be profitable. Note that the existing 3468 code only cares for branches with (some) filled delay slots. */ 3469 if (current_function_epilogue_delay_list != NULL) 3470 return; 3471#endif 3472 3473 /* See if there is a RETURN insn in the function other than the one we 3474 made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change 3475 into a RETURN to jump to it. */ 3476 for (insn = first; insn; insn = NEXT_INSN (insn)) 3477 if (JUMP_P (insn) && GET_CODE (PATTERN (insn)) == RETURN) 3478 { 3479 real_return_label = get_label_before (insn); 3480 break; 3481 } 3482 3483 /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it 3484 was equal to END_OF_FUNCTION_LABEL. */ 3485 LABEL_NUSES (real_return_label)++; 3486 3487 /* Clear the list of insns to fill so we can use it. */ 3488 obstack_free (&unfilled_slots_obstack, unfilled_firstobj); 3489 3490 for (insn = first; insn; insn = NEXT_INSN (insn)) 3491 { 3492 int flags; 3493 3494 /* Only look at filled JUMP_INSNs that go to the end of function 3495 label. */ 3496 if (!NONJUMP_INSN_P (insn) 3497 || GET_CODE (PATTERN (insn)) != SEQUENCE 3498 || !JUMP_P (XVECEXP (PATTERN (insn), 0, 0)) 3499 || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label) 3500 continue; 3501 3502 pat = PATTERN (insn); 3503 jump_insn = XVECEXP (pat, 0, 0); 3504 3505 /* If we can't make the jump into a RETURN, try to redirect it to the best 3506 RETURN and go on to the next insn. */ 3507 if (! reorg_redirect_jump (jump_insn, NULL_RTX)) 3508 { 3509 /* Make sure redirecting the jump will not invalidate the delay 3510 slot insns. */ 3511 if (redirect_with_delay_slots_safe_p (jump_insn, 3512 real_return_label, 3513 insn)) 3514 reorg_redirect_jump (jump_insn, real_return_label); 3515 continue; 3516 } 3517 3518 /* See if this RETURN can accept the insns current in its delay slot. 3519 It can if it has more or an equal number of slots and the contents 3520 of each is valid. */ 3521 3522 flags = get_jump_flags (jump_insn, JUMP_LABEL (jump_insn)); 3523 slots = num_delay_slots (jump_insn); 3524 if (slots >= XVECLEN (pat, 0) - 1) 3525 { 3526 for (i = 1; i < XVECLEN (pat, 0); i++) 3527 if (! ( 3528#ifdef ANNUL_IFFALSE_SLOTS 3529 (INSN_ANNULLED_BRANCH_P (jump_insn) 3530 && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i))) 3531 ? eligible_for_annul_false (jump_insn, i - 1, 3532 XVECEXP (pat, 0, i), flags) : 3533#endif 3534#ifdef ANNUL_IFTRUE_SLOTS 3535 (INSN_ANNULLED_BRANCH_P (jump_insn) 3536 && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i))) 3537 ? eligible_for_annul_true (jump_insn, i - 1, 3538 XVECEXP (pat, 0, i), flags) : 3539#endif 3540 eligible_for_delay (jump_insn, i - 1, 3541 XVECEXP (pat, 0, i), flags))) 3542 break; 3543 } 3544 else 3545 i = 0; 3546 3547 if (i == XVECLEN (pat, 0)) 3548 continue; 3549 3550 /* We have to do something with this insn. If it is an unconditional 3551 RETURN, delete the SEQUENCE and output the individual insns, 3552 followed by the RETURN. Then set things up so we try to find 3553 insns for its delay slots, if it needs some. */ 3554 if (GET_CODE (PATTERN (jump_insn)) == RETURN) 3555 { 3556 rtx prev = PREV_INSN (insn); 3557 3558 delete_related_insns (insn); 3559 for (i = 1; i < XVECLEN (pat, 0); i++) 3560 prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev); 3561 3562 insn = emit_jump_insn_after (PATTERN (jump_insn), prev); 3563 emit_barrier_after (insn); 3564 3565 if (slots) 3566 obstack_ptr_grow (&unfilled_slots_obstack, insn); 3567 } 3568 else 3569 /* It is probably more efficient to keep this with its current 3570 delay slot as a branch to a RETURN. */ 3571 reorg_redirect_jump (jump_insn, real_return_label); 3572 } 3573 3574 /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any 3575 new delay slots we have created. */ 3576 if (--LABEL_NUSES (real_return_label) == 0) 3577 delete_related_insns (real_return_label); 3578 3579 fill_simple_delay_slots (1); 3580 fill_simple_delay_slots (0); 3581} 3582#endif 3583 3584/* Try to find insns to place in delay slots. */ 3585 3586void 3587dbr_schedule (rtx first, FILE *file) 3588{ 3589 rtx insn, next, epilogue_insn = 0; 3590 int i; 3591 3592 /* If the current function has no insns other than the prologue and 3593 epilogue, then do not try to fill any delay slots. */ 3594 if (n_basic_blocks == 0) 3595 return; 3596 3597 /* Find the highest INSN_UID and allocate and initialize our map from 3598 INSN_UID's to position in code. */ 3599 for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn)) 3600 { 3601 if (INSN_UID (insn) > max_uid) 3602 max_uid = INSN_UID (insn); 3603 if (NOTE_P (insn) 3604 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EPILOGUE_BEG) 3605 epilogue_insn = insn; 3606 } 3607 3608 uid_to_ruid = xmalloc ((max_uid + 1) * sizeof (int)); 3609 for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn)) 3610 uid_to_ruid[INSN_UID (insn)] = i; 3611 3612 /* Initialize the list of insns that need filling. */ 3613 if (unfilled_firstobj == 0) 3614 { 3615 gcc_obstack_init (&unfilled_slots_obstack); 3616 unfilled_firstobj = obstack_alloc (&unfilled_slots_obstack, 0); 3617 } 3618 3619 for (insn = next_active_insn (first); insn; insn = next_active_insn (insn)) 3620 { 3621 rtx target; 3622 3623 INSN_ANNULLED_BRANCH_P (insn) = 0; 3624 INSN_FROM_TARGET_P (insn) = 0; 3625 3626 /* Skip vector tables. We can't get attributes for them. */ 3627 if (JUMP_P (insn) 3628 && (GET_CODE (PATTERN (insn)) == ADDR_VEC 3629 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)) 3630 continue; 3631 3632 if (num_delay_slots (insn) > 0) 3633 obstack_ptr_grow (&unfilled_slots_obstack, insn); 3634 3635 /* Ensure all jumps go to the last of a set of consecutive labels. */ 3636 if (JUMP_P (insn) 3637 && (condjump_p (insn) || condjump_in_parallel_p (insn)) 3638 && JUMP_LABEL (insn) != 0 3639 && ((target = skip_consecutive_labels (JUMP_LABEL (insn))) 3640 != JUMP_LABEL (insn))) 3641 redirect_jump (insn, target, 1); 3642 } 3643 3644 init_resource_info (epilogue_insn); 3645 3646 /* Show we haven't computed an end-of-function label yet. */ 3647 end_of_function_label = 0; 3648 3649 /* Initialize the statistics for this function. */ 3650 memset (num_insns_needing_delays, 0, sizeof num_insns_needing_delays); 3651 memset (num_filled_delays, 0, sizeof num_filled_delays); 3652 3653 /* Now do the delay slot filling. Try everything twice in case earlier 3654 changes make more slots fillable. */ 3655 3656 for (reorg_pass_number = 0; 3657 reorg_pass_number < MAX_REORG_PASSES; 3658 reorg_pass_number++) 3659 { 3660 fill_simple_delay_slots (1); 3661 fill_simple_delay_slots (0); 3662 fill_eager_delay_slots (); 3663 relax_delay_slots (first); 3664 } 3665 3666 /* Delete any USE insns made by update_block; subsequent passes don't need 3667 them or know how to deal with them. */ 3668 for (insn = first; insn; insn = next) 3669 { 3670 next = NEXT_INSN (insn); 3671 3672 if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == USE 3673 && INSN_P (XEXP (PATTERN (insn), 0))) 3674 next = delete_related_insns (insn); 3675 } 3676 3677 /* If we made an end of function label, indicate that it is now 3678 safe to delete it by undoing our prior adjustment to LABEL_NUSES. 3679 If it is now unused, delete it. */ 3680 if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0) 3681 delete_related_insns (end_of_function_label); 3682 3683#ifdef HAVE_return 3684 if (HAVE_return && end_of_function_label != 0) 3685 make_return_insns (first); 3686#endif 3687 3688 obstack_free (&unfilled_slots_obstack, unfilled_firstobj); 3689 3690 /* It is not clear why the line below is needed, but it does seem to be. */ 3691 unfilled_firstobj = obstack_alloc (&unfilled_slots_obstack, 0); 3692 3693 if (file) 3694 { 3695 int i, j, need_comma; 3696 int total_delay_slots[MAX_DELAY_HISTOGRAM + 1]; 3697 int total_annul_slots[MAX_DELAY_HISTOGRAM + 1]; 3698 3699 for (reorg_pass_number = 0; 3700 reorg_pass_number < MAX_REORG_PASSES; 3701 reorg_pass_number++) 3702 { 3703 fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1); 3704 for (i = 0; i < NUM_REORG_FUNCTIONS; i++) 3705 { 3706 need_comma = 0; 3707 fprintf (file, ";; Reorg function #%d\n", i); 3708 3709 fprintf (file, ";; %d insns needing delay slots\n;; ", 3710 num_insns_needing_delays[i][reorg_pass_number]); 3711 3712 for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++) 3713 if (num_filled_delays[i][j][reorg_pass_number]) 3714 { 3715 if (need_comma) 3716 fprintf (file, ", "); 3717 need_comma = 1; 3718 fprintf (file, "%d got %d delays", 3719 num_filled_delays[i][j][reorg_pass_number], j); 3720 } 3721 fprintf (file, "\n"); 3722 } 3723 } 3724 memset (total_delay_slots, 0, sizeof total_delay_slots); 3725 memset (total_annul_slots, 0, sizeof total_annul_slots); 3726 for (insn = first; insn; insn = NEXT_INSN (insn)) 3727 { 3728 if (! INSN_DELETED_P (insn) 3729 && NONJUMP_INSN_P (insn) 3730 && GET_CODE (PATTERN (insn)) != USE 3731 && GET_CODE (PATTERN (insn)) != CLOBBER) 3732 { 3733 if (GET_CODE (PATTERN (insn)) == SEQUENCE) 3734 { 3735 j = XVECLEN (PATTERN (insn), 0) - 1; 3736 if (j > MAX_DELAY_HISTOGRAM) 3737 j = MAX_DELAY_HISTOGRAM; 3738 if (INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (insn), 0, 0))) 3739 total_annul_slots[j]++; 3740 else 3741 total_delay_slots[j]++; 3742 } 3743 else if (num_delay_slots (insn) > 0) 3744 total_delay_slots[0]++; 3745 } 3746 } 3747 fprintf (file, ";; Reorg totals: "); 3748 need_comma = 0; 3749 for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++) 3750 { 3751 if (total_delay_slots[j]) 3752 { 3753 if (need_comma) 3754 fprintf (file, ", "); 3755 need_comma = 1; 3756 fprintf (file, "%d got %d delays", total_delay_slots[j], j); 3757 } 3758 } 3759 fprintf (file, "\n"); 3760#if defined (ANNUL_IFTRUE_SLOTS) || defined (ANNUL_IFFALSE_SLOTS) 3761 fprintf (file, ";; Reorg annuls: "); 3762 need_comma = 0; 3763 for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++) 3764 { 3765 if (total_annul_slots[j]) 3766 { 3767 if (need_comma) 3768 fprintf (file, ", "); 3769 need_comma = 1; 3770 fprintf (file, "%d got %d delays", total_annul_slots[j], j); 3771 } 3772 } 3773 fprintf (file, "\n"); 3774#endif 3775 fprintf (file, "\n"); 3776 } 3777 3778 /* For all JUMP insns, fill in branch prediction notes, so that during 3779 assembler output a target can set branch prediction bits in the code. 3780 We have to do this now, as up until this point the destinations of 3781 JUMPS can be moved around and changed, but past right here that cannot 3782 happen. */ 3783 for (insn = first; insn; insn = NEXT_INSN (insn)) 3784 { 3785 int pred_flags; 3786 3787 if (NONJUMP_INSN_P (insn)) 3788 { 3789 rtx pat = PATTERN (insn); 3790 3791 if (GET_CODE (pat) == SEQUENCE) 3792 insn = XVECEXP (pat, 0, 0); 3793 } 3794 if (!JUMP_P (insn)) 3795 continue; 3796 3797 pred_flags = get_jump_flags (insn, JUMP_LABEL (insn)); 3798 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_BR_PRED, 3799 GEN_INT (pred_flags), 3800 REG_NOTES (insn)); 3801 } 3802 free_resource_info (); 3803 free (uid_to_ruid); 3804#ifdef DELAY_SLOTS_FOR_EPILOGUE 3805 /* SPARC assembler, for instance, emit warning when debug info is output 3806 into the delay slot. */ 3807 { 3808 rtx link; 3809 3810 for (link = current_function_epilogue_delay_list; 3811 link; 3812 link = XEXP (link, 1)) 3813 INSN_LOCATOR (XEXP (link, 0)) = 0; 3814 } 3815#endif 3816} 3817#endif /* DELAY_SLOTS */ 3818 3819static bool 3820gate_handle_delay_slots (void) 3821{ 3822#ifdef DELAY_SLOTS 3823 return flag_delayed_branch; 3824#else 3825 return 0; 3826#endif 3827} 3828 3829/* Run delay slot optimization. */ 3830static void 3831rest_of_handle_delay_slots (void) 3832{ 3833#ifdef DELAY_SLOTS 3834 dbr_schedule (get_insns (), dump_file); 3835#endif 3836} 3837 3838struct tree_opt_pass pass_delay_slots = 3839{ 3840 "dbr", /* name */ 3841 gate_handle_delay_slots, /* gate */ 3842 rest_of_handle_delay_slots, /* execute */ 3843 NULL, /* sub */ 3844 NULL, /* next */ 3845 0, /* static_pass_number */ 3846 TV_DBR_SCHED, /* tv_id */ 3847 0, /* properties_required */ 3848 0, /* properties_provided */ 3849 0, /* properties_destroyed */ 3850 0, /* todo_flags_start */ 3851 TODO_dump_func | 3852 TODO_ggc_collect, /* todo_flags_finish */ 3853 'd' /* letter */ 3854}; 3855 3856/* Machine dependent reorg pass. */ 3857static bool 3858gate_handle_machine_reorg (void) 3859{ 3860 return targetm.machine_dependent_reorg != 0; 3861} 3862 3863 3864static void 3865rest_of_handle_machine_reorg (void) 3866{ 3867 targetm.machine_dependent_reorg (); 3868} 3869 3870struct tree_opt_pass pass_machine_reorg = 3871{ 3872 "mach", /* name */ 3873 gate_handle_machine_reorg, /* gate */ 3874 rest_of_handle_machine_reorg, /* execute */ 3875 NULL, /* sub */ 3876 NULL, /* next */ 3877 0, /* static_pass_number */ 3878 TV_MACH_DEP, /* tv_id */ 3879 0, /* properties_required */ 3880 0, /* properties_provided */ 3881 0, /* properties_destroyed */ 3882 0, /* todo_flags_start */ 3883 TODO_dump_func | 3884 TODO_ggc_collect, /* todo_flags_finish */ 3885 'M' /* letter */ 3886}; 3887 3888