118334Speter/* Perform instruction reorganizations for delay slot filling. 290075Sobrien Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3169689Skan 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 418334Speter Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu). 518334Speter Hacked by Michael Tiemann (tiemann@cygnus.com). 618334Speter 790075SobrienThis file is part of GCC. 818334Speter 990075SobrienGCC is free software; you can redistribute it and/or modify it under 1090075Sobrienthe terms of the GNU General Public License as published by the Free 1190075SobrienSoftware Foundation; either version 2, or (at your option) any later 1290075Sobrienversion. 1318334Speter 1490075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1590075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1690075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1790075Sobrienfor more details. 1818334Speter 1918334SpeterYou should have received a copy of the GNU General Public License 2090075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 21169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 22169689Skan02110-1301, USA. */ 2318334Speter 2418334Speter/* Instruction reorganization pass. 2518334Speter 2618334Speter This pass runs after register allocation and final jump 2718334Speter optimization. It should be the last pass to run before peephole. 2818334Speter It serves primarily to fill delay slots of insns, typically branch 2918334Speter and call insns. Other insns typically involve more complicated 3018334Speter interactions of data dependencies and resource constraints, and 3118334Speter are better handled by scheduling before register allocation (by the 3218334Speter function `schedule_insns'). 3318334Speter 3418334Speter The Branch Penalty is the number of extra cycles that are needed to 3518334Speter execute a branch insn. On an ideal machine, branches take a single 3618334Speter cycle, and the Branch Penalty is 0. Several RISC machines approach 3718334Speter branch delays differently: 3818334Speter 39169689Skan The MIPS has a single branch delay slot. Most insns 4018334Speter (except other branches) can be used to fill this slot. When the 4118334Speter slot is filled, two insns execute in two cycles, reducing the 4218334Speter branch penalty to zero. 4318334Speter 4418334Speter The SPARC always has a branch delay slot, but its effects can be 4518334Speter annulled when the branch is not taken. This means that failing to 4618334Speter find other sources of insns, we can hoist an insn from the branch 4718334Speter target that would only be safe to execute knowing that the branch 4818334Speter is taken. 4918334Speter 5018334Speter The HP-PA always has a branch delay slot. For unconditional branches 5190075Sobrien its effects can be annulled when the branch is taken. The effects 5218334Speter of the delay slot in a conditional branch can be nullified for forward 5318334Speter taken branches, or for untaken backward branches. This means 5418334Speter we can hoist insns from the fall-through path for forward branches or 5518334Speter steal insns from the target of backward branches. 5618334Speter 5752284Sobrien The TMS320C3x and C4x have three branch delay slots. When the three 5852284Sobrien slots are filled, the branch penalty is zero. Most insns can fill the 5952284Sobrien delay slots except jump insns. 6052284Sobrien 6118334Speter Three techniques for filling delay slots have been implemented so far: 6218334Speter 6318334Speter (1) `fill_simple_delay_slots' is the simplest, most efficient way 6418334Speter to fill delay slots. This pass first looks for insns which come 6518334Speter from before the branch and which are safe to execute after the 6618334Speter branch. Then it searches after the insn requiring delay slots or, 6718334Speter in the case of a branch, for insns that are after the point at 6818334Speter which the branch merges into the fallthrough code, if such a point 6918334Speter exists. When such insns are found, the branch penalty decreases 7018334Speter and no code expansion takes place. 7118334Speter 7218334Speter (2) `fill_eager_delay_slots' is more complicated: it is used for 7318334Speter scheduling conditional jumps, or for scheduling jumps which cannot 7418334Speter be filled using (1). A machine need not have annulled jumps to use 7518334Speter this strategy, but it helps (by keeping more options open). 7618334Speter `fill_eager_delay_slots' tries to guess the direction the branch 7718334Speter will go; if it guesses right 100% of the time, it can reduce the 7818334Speter branch penalty as much as `fill_simple_delay_slots' does. If it 79169689Skan guesses wrong 100% of the time, it might as well schedule nops. When 8018334Speter `fill_eager_delay_slots' takes insns from the fall-through path of 8118334Speter the jump, usually there is no code expansion; when it takes insns 8218334Speter from the branch target, there is code expansion if it is not the 8318334Speter only way to reach that target. 8418334Speter 8518334Speter (3) `relax_delay_slots' uses a set of rules to simplify code that 8618334Speter has been reorganized by (1) and (2). It finds cases where 8718334Speter conditional test can be eliminated, jumps can be threaded, extra 8818334Speter insns can be eliminated, etc. It is the job of (1) and (2) to do a 8918334Speter good job of scheduling locally; `relax_delay_slots' takes care of 9018334Speter making the various individual schedules work well together. It is 9118334Speter especially tuned to handle the control flow interactions of branch 9218334Speter insns. It does nothing for insns with delay slots that do not 9318334Speter branch. 9418334Speter 9518334Speter On machines that use CC0, we are very conservative. We will not make 9618334Speter a copy of an insn involving CC0 since we want to maintain a 1-1 9718334Speter correspondence between the insn that sets and uses CC0. The insns are 9818334Speter allowed to be separated by placing an insn that sets CC0 (but not an insn 9918334Speter that uses CC0; we could do this, but it doesn't seem worthwhile) in a 10018334Speter delay slot. In that case, we point each insn at the other with REG_CC_USER 10118334Speter and REG_CC_SETTER notes. Note that these restrictions affect very few 10218334Speter machines because most RISC machines with delay slots will not use CC0 10318334Speter (the RT is the only known exception at this point). 10418334Speter 10518334Speter Not yet implemented: 10618334Speter 10718334Speter The Acorn Risc Machine can conditionally execute most insns, so 10818334Speter it is profitable to move single insns into a position to execute 10918334Speter based on the condition code of the previous insn. 11018334Speter 11118334Speter The HP-PA can conditionally nullify insns, providing a similar 11290075Sobrien effect to the ARM, differing mostly in which insn is "in charge". */ 11318334Speter 11418334Speter#include "config.h" 11550397Sobrien#include "system.h" 116132718Skan#include "coretypes.h" 117132718Skan#include "tm.h" 11852284Sobrien#include "toplev.h" 11918334Speter#include "rtl.h" 12090075Sobrien#include "tm_p.h" 12150397Sobrien#include "expr.h" 12290075Sobrien#include "function.h" 12318334Speter#include "insn-config.h" 12418334Speter#include "conditions.h" 12518334Speter#include "hard-reg-set.h" 12618334Speter#include "basic-block.h" 12718334Speter#include "regs.h" 12818334Speter#include "recog.h" 12918334Speter#include "flags.h" 13018334Speter#include "output.h" 13118334Speter#include "obstack.h" 13218334Speter#include "insn-attr.h" 13352284Sobrien#include "resource.h" 13490075Sobrien#include "except.h" 13590075Sobrien#include "params.h" 136169689Skan#include "timevar.h" 137169689Skan#include "target.h" 138169689Skan#include "tree-pass.h" 13918334Speter 14018334Speter#ifdef DELAY_SLOTS 14118334Speter 14218334Speter#ifndef ANNUL_IFTRUE_SLOTS 14318334Speter#define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0 14418334Speter#endif 14518334Speter#ifndef ANNUL_IFFALSE_SLOTS 14618334Speter#define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0 14718334Speter#endif 14818334Speter 14918334Speter/* Insns which have delay slots that have not yet been filled. */ 15018334Speter 15118334Speterstatic struct obstack unfilled_slots_obstack; 15218334Speterstatic rtx *unfilled_firstobj; 15318334Speter 15418334Speter/* Define macros to refer to the first and last slot containing unfilled 15518334Speter insns. These are used because the list may move and its address 15618334Speter should be recomputed at each use. */ 15718334Speter 15818334Speter#define unfilled_slots_base \ 15918334Speter ((rtx *) obstack_base (&unfilled_slots_obstack)) 16018334Speter 16118334Speter#define unfilled_slots_next \ 16218334Speter ((rtx *) obstack_next_free (&unfilled_slots_obstack)) 16318334Speter 16418334Speter/* Points to the label before the end of the function. */ 16518334Speterstatic rtx end_of_function_label; 16618334Speter 16718334Speter/* Mapping between INSN_UID's and position in the code since INSN_UID's do 16818334Speter not always monotonically increase. */ 16918334Speterstatic int *uid_to_ruid; 17018334Speter 17118334Speter/* Highest valid index in `uid_to_ruid'. */ 17218334Speterstatic int max_uid; 17318334Speter 174132718Skanstatic int stop_search_p (rtx, int); 175132718Skanstatic int resource_conflicts_p (struct resources *, struct resources *); 176132718Skanstatic int insn_references_resource_p (rtx, struct resources *, int); 177132718Skanstatic int insn_sets_resource_p (rtx, struct resources *, int); 178132718Skanstatic rtx find_end_label (void); 179132718Skanstatic rtx emit_delay_sequence (rtx, rtx, int); 180132718Skanstatic rtx add_to_delay_list (rtx, rtx); 181132718Skanstatic rtx delete_from_delay_slot (rtx); 182132718Skanstatic void delete_scheduled_jump (rtx); 183132718Skanstatic void note_delay_statistics (int, int); 18490075Sobrien#if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS) 185132718Skanstatic rtx optimize_skip (rtx); 18690075Sobrien#endif 187132718Skanstatic int get_jump_flags (rtx, rtx); 188132718Skanstatic int rare_destination (rtx); 189132718Skanstatic int mostly_true_jump (rtx, rtx); 190132718Skanstatic rtx get_branch_condition (rtx, rtx); 191132718Skanstatic int condition_dominates_p (rtx, rtx); 192132718Skanstatic int redirect_with_delay_slots_safe_p (rtx, rtx, rtx); 193132718Skanstatic int redirect_with_delay_list_safe_p (rtx, rtx, rtx); 194132718Skanstatic int check_annul_list_true_false (int, rtx); 195132718Skanstatic rtx steal_delay_list_from_target (rtx, rtx, rtx, rtx, 196132718Skan struct resources *, 197132718Skan struct resources *, 198132718Skan struct resources *, 199132718Skan int, int *, int *, rtx *); 200132718Skanstatic rtx steal_delay_list_from_fallthrough (rtx, rtx, rtx, rtx, 201132718Skan struct resources *, 202132718Skan struct resources *, 203132718Skan struct resources *, 204132718Skan int, int *, int *); 205132718Skanstatic void try_merge_delay_insns (rtx, rtx); 206132718Skanstatic rtx redundant_insn (rtx, rtx, rtx); 207132718Skanstatic int own_thread_p (rtx, rtx, int); 208132718Skanstatic void update_block (rtx, rtx); 209132718Skanstatic int reorg_redirect_jump (rtx, rtx); 210132718Skanstatic void update_reg_dead_notes (rtx, rtx); 211132718Skanstatic void fix_reg_dead_note (rtx, rtx); 212132718Skanstatic void update_reg_unused_notes (rtx, rtx); 213132718Skanstatic void fill_simple_delay_slots (int); 214132718Skanstatic rtx fill_slots_from_thread (rtx, rtx, rtx, rtx, int, int, int, int, 215132718Skan int *, rtx); 216132718Skanstatic void fill_eager_delay_slots (void); 217132718Skanstatic void relax_delay_slots (rtx); 21890075Sobrien#ifdef HAVE_return 219132718Skanstatic void make_return_insns (rtx); 22090075Sobrien#endif 22118334Speter 22218334Speter/* Return TRUE if this insn should stop the search for insn to fill delay 22318334Speter slots. LABELS_P indicates that labels should terminate the search. 22418334Speter In all cases, jumps terminate the search. */ 22518334Speter 22618334Speterstatic int 227132718Skanstop_search_p (rtx insn, int labels_p) 22818334Speter{ 22918334Speter if (insn == 0) 23018334Speter return 1; 23118334Speter 232122180Skan /* If the insn can throw an exception that is caught within the function, 233122180Skan it may effectively perform a jump from the viewpoint of the function. 234122180Skan Therefore act like for a jump. */ 235122180Skan if (can_throw_internal (insn)) 236122180Skan return 1; 237122180Skan 23818334Speter switch (GET_CODE (insn)) 23918334Speter { 24018334Speter case NOTE: 24118334Speter case CALL_INSN: 24218334Speter return 0; 24318334Speter 24418334Speter case CODE_LABEL: 24518334Speter return labels_p; 24618334Speter 24718334Speter case JUMP_INSN: 24818334Speter case BARRIER: 24918334Speter return 1; 25018334Speter 25118334Speter case INSN: 25218334Speter /* OK unless it contains a delay slot or is an `asm' insn of some type. 25318334Speter We don't know anything about these. */ 25418334Speter return (GET_CODE (PATTERN (insn)) == SEQUENCE 25518334Speter || GET_CODE (PATTERN (insn)) == ASM_INPUT 25618334Speter || asm_noperands (PATTERN (insn)) >= 0); 25718334Speter 25818334Speter default: 259169689Skan gcc_unreachable (); 26018334Speter } 26118334Speter} 26218334Speter 26318334Speter/* Return TRUE if any resources are marked in both RES1 and RES2 or if either 26418334Speter resource set contains a volatile memory reference. Otherwise, return FALSE. */ 26518334Speter 26618334Speterstatic int 267132718Skanresource_conflicts_p (struct resources *res1, struct resources *res2) 26818334Speter{ 26918334Speter if ((res1->cc && res2->cc) || (res1->memory && res2->memory) 27018334Speter || (res1->unch_memory && res2->unch_memory) 27118334Speter || res1->volatil || res2->volatil) 27218334Speter return 1; 27318334Speter 27418334Speter#ifdef HARD_REG_SET 27518334Speter return (res1->regs & res2->regs) != HARD_CONST (0); 27618334Speter#else 27718334Speter { 27818334Speter int i; 27918334Speter 28018334Speter for (i = 0; i < HARD_REG_SET_LONGS; i++) 28118334Speter if ((res1->regs[i] & res2->regs[i]) != 0) 28218334Speter return 1; 28318334Speter return 0; 28418334Speter } 28518334Speter#endif 28618334Speter} 28718334Speter 28818334Speter/* Return TRUE if any resource marked in RES, a `struct resources', is 28950397Sobrien referenced by INSN. If INCLUDE_DELAYED_EFFECTS is set, return if the called 29018334Speter routine is using those resources. 29118334Speter 29218334Speter We compute this by computing all the resources referenced by INSN and 29318334Speter seeing if this conflicts with RES. It might be faster to directly check 29418334Speter ourselves, and this is the way it used to work, but it means duplicating 29518334Speter a large block of complex code. */ 29618334Speter 29718334Speterstatic int 298132718Skaninsn_references_resource_p (rtx insn, struct resources *res, 299132718Skan int include_delayed_effects) 30018334Speter{ 30118334Speter struct resources insn_res; 30218334Speter 30318334Speter CLEAR_RESOURCE (&insn_res); 30418334Speter mark_referenced_resources (insn, &insn_res, include_delayed_effects); 30518334Speter return resource_conflicts_p (&insn_res, res); 30618334Speter} 30718334Speter 30818334Speter/* Return TRUE if INSN modifies resources that are marked in RES. 30950397Sobrien INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be 31018334Speter included. CC0 is only modified if it is explicitly set; see comments 31118334Speter in front of mark_set_resources for details. */ 31218334Speter 31318334Speterstatic int 314132718Skaninsn_sets_resource_p (rtx insn, struct resources *res, 315132718Skan int include_delayed_effects) 31618334Speter{ 31718334Speter struct resources insn_sets; 31818334Speter 31918334Speter CLEAR_RESOURCE (&insn_sets); 32018334Speter mark_set_resources (insn, &insn_sets, 0, include_delayed_effects); 32118334Speter return resource_conflicts_p (&insn_sets, res); 32218334Speter} 32318334Speter 324169689Skan/* Find a label at the end of the function or before a RETURN. If there 325169689Skan is none, try to make one. If that fails, returns 0. 32618334Speter 327169689Skan The property of such a label is that it is placed just before the 328169689Skan epilogue or a bare RETURN insn, so that another bare RETURN can be 329169689Skan turned into a jump to the label unconditionally. In particular, the 330169689Skan label cannot be placed before a RETURN insn with a filled delay slot. 331169689Skan 332169689Skan ??? There may be a problem with the current implementation. Suppose 333169689Skan we start with a bare RETURN insn and call find_end_label. It may set 334169689Skan end_of_function_label just before the RETURN. Suppose the machinery 335169689Skan is able to fill the delay slot of the RETURN insn afterwards. Then 336169689Skan end_of_function_label is no longer valid according to the property 337169689Skan described above and find_end_label will still return it unmodified. 338169689Skan Note that this is probably mitigated by the following observation: 339169689Skan once end_of_function_label is made, it is very likely the target of 340169689Skan a jump, so filling the delay slot of the RETURN will be much more 341169689Skan difficult. */ 342169689Skan 34318334Speterstatic rtx 344132718Skanfind_end_label (void) 34518334Speter{ 34618334Speter rtx insn; 34718334Speter 34818334Speter /* If we found one previously, return it. */ 34918334Speter if (end_of_function_label) 35018334Speter return end_of_function_label; 35118334Speter 35218334Speter /* Otherwise, see if there is a label at the end of the function. If there 35318334Speter is, it must be that RETURN insns aren't needed, so that is our return 35418334Speter label and we don't have to do anything else. */ 35518334Speter 35618334Speter insn = get_last_insn (); 357169689Skan while (NOTE_P (insn) 358169689Skan || (NONJUMP_INSN_P (insn) 35918334Speter && (GET_CODE (PATTERN (insn)) == USE 36018334Speter || GET_CODE (PATTERN (insn)) == CLOBBER))) 36118334Speter insn = PREV_INSN (insn); 36218334Speter 36390075Sobrien /* When a target threads its epilogue we might already have a 36418334Speter suitable return insn. If so put a label before it for the 36518334Speter end_of_function_label. */ 366169689Skan if (BARRIER_P (insn) 367169689Skan && JUMP_P (PREV_INSN (insn)) 36818334Speter && GET_CODE (PATTERN (PREV_INSN (insn))) == RETURN) 36918334Speter { 37018334Speter rtx temp = PREV_INSN (PREV_INSN (insn)); 37118334Speter end_of_function_label = gen_label_rtx (); 37218334Speter LABEL_NUSES (end_of_function_label) = 0; 37318334Speter 374169689Skan /* Put the label before an USE insns that may precede the RETURN insn. */ 37518334Speter while (GET_CODE (temp) == USE) 37618334Speter temp = PREV_INSN (temp); 37718334Speter 37818334Speter emit_label_after (end_of_function_label, temp); 37918334Speter } 38018334Speter 381169689Skan else if (LABEL_P (insn)) 38218334Speter end_of_function_label = insn; 38318334Speter else 38418334Speter { 38518334Speter end_of_function_label = gen_label_rtx (); 38618334Speter LABEL_NUSES (end_of_function_label) = 0; 38790075Sobrien /* If the basic block reorder pass moves the return insn to 38890075Sobrien some other place try to locate it again and put our 38990075Sobrien end_of_function_label there. */ 390169689Skan while (insn && ! (JUMP_P (insn) 39190075Sobrien && (GET_CODE (PATTERN (insn)) == RETURN))) 39290075Sobrien insn = PREV_INSN (insn); 39390075Sobrien if (insn) 39418334Speter { 39590075Sobrien insn = PREV_INSN (insn); 39690075Sobrien 39790075Sobrien /* Put the label before an USE insns that may proceed the 39890075Sobrien RETURN insn. */ 39990075Sobrien while (GET_CODE (insn) == USE) 40090075Sobrien insn = PREV_INSN (insn); 40190075Sobrien 40290075Sobrien emit_label_after (end_of_function_label, insn); 40318334Speter } 40490075Sobrien else 40590075Sobrien { 406169689Skan#ifdef HAVE_epilogue 407169689Skan if (HAVE_epilogue 408169689Skan#ifdef HAVE_return 409169689Skan && ! HAVE_return 410169689Skan#endif 411169689Skan ) 412169689Skan { 413169689Skan /* The RETURN insn has its delay slot filled so we cannot 414169689Skan emit the label just before it. Since we already have 415169689Skan an epilogue and cannot emit a new RETURN, we cannot 416169689Skan emit the label at all. */ 417169689Skan end_of_function_label = NULL_RTX; 418169689Skan return end_of_function_label; 419169689Skan } 420169689Skan#endif /* HAVE_epilogue */ 421169689Skan 42290075Sobrien /* Otherwise, make a new label and emit a RETURN and BARRIER, 42390075Sobrien if needed. */ 42490075Sobrien emit_label (end_of_function_label); 42590075Sobrien#ifdef HAVE_return 426169689Skan /* We don't bother trying to create a return insn if the 427169689Skan epilogue has filled delay-slots; we would have to try and 428169689Skan move the delay-slot fillers to the delay-slots for the new 429169689Skan return insn or in front of the new return insn. */ 430169689Skan if (current_function_epilogue_delay_list == NULL 431169689Skan && HAVE_return) 43290075Sobrien { 43390075Sobrien /* The return we make may have delay slots too. */ 43490075Sobrien rtx insn = gen_return (); 43590075Sobrien insn = emit_jump_insn (insn); 43690075Sobrien emit_barrier (); 43790075Sobrien if (num_delay_slots (insn) > 0) 43890075Sobrien obstack_ptr_grow (&unfilled_slots_obstack, insn); 43990075Sobrien } 44018334Speter#endif 44190075Sobrien } 44218334Speter } 44318334Speter 44418334Speter /* Show one additional use for this label so it won't go away until 44518334Speter we are done. */ 44618334Speter ++LABEL_NUSES (end_of_function_label); 44718334Speter 44818334Speter return end_of_function_label; 44918334Speter} 45018334Speter 45118334Speter/* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace 45218334Speter the pattern of INSN with the SEQUENCE. 45318334Speter 45418334Speter Chain the insns so that NEXT_INSN of each insn in the sequence points to 45518334Speter the next and NEXT_INSN of the last insn in the sequence points to 45618334Speter the first insn after the sequence. Similarly for PREV_INSN. This makes 45718334Speter it easier to scan all insns. 45818334Speter 45918334Speter Returns the SEQUENCE that replaces INSN. */ 46018334Speter 46118334Speterstatic rtx 462132718Skanemit_delay_sequence (rtx insn, rtx list, int length) 46318334Speter{ 46490075Sobrien int i = 1; 46590075Sobrien rtx li; 46618334Speter int had_barrier = 0; 46718334Speter 46850397Sobrien /* Allocate the rtvec to hold the insns and the SEQUENCE. */ 46918334Speter rtvec seqv = rtvec_alloc (length + 1); 47050397Sobrien rtx seq = gen_rtx_SEQUENCE (VOIDmode, seqv); 47118334Speter rtx seq_insn = make_insn_raw (seq); 47218334Speter rtx first = get_insns (); 47318334Speter rtx last = get_last_insn (); 47418334Speter 47550397Sobrien /* Make a copy of the insn having delay slots. */ 47618334Speter rtx delay_insn = copy_rtx (insn); 47718334Speter 47818334Speter /* If INSN is followed by a BARRIER, delete the BARRIER since it will only 47990075Sobrien confuse further processing. Update LAST in case it was the last insn. 48018334Speter We will put the BARRIER back in later. */ 481169689Skan if (NEXT_INSN (insn) && BARRIER_P (NEXT_INSN (insn))) 48218334Speter { 48390075Sobrien delete_related_insns (NEXT_INSN (insn)); 48418334Speter last = get_last_insn (); 48518334Speter had_barrier = 1; 48618334Speter } 48718334Speter 48818334Speter /* Splice our SEQUENCE into the insn stream where INSN used to be. */ 48918334Speter NEXT_INSN (seq_insn) = NEXT_INSN (insn); 49018334Speter PREV_INSN (seq_insn) = PREV_INSN (insn); 49118334Speter 49250397Sobrien if (insn != last) 49350397Sobrien PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn; 49450397Sobrien 49550397Sobrien if (insn != first) 49650397Sobrien NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn; 49750397Sobrien 49850397Sobrien /* Note the calls to set_new_first_and_last_insn must occur after 49950397Sobrien SEQ_INSN has been completely spliced into the insn stream. 50050397Sobrien 50150397Sobrien Otherwise CUR_INSN_UID will get set to an incorrect value because 50250397Sobrien set_new_first_and_last_insn will not find SEQ_INSN in the chain. */ 50318334Speter if (insn == last) 50418334Speter set_new_first_and_last_insn (first, seq_insn); 50518334Speter 50618334Speter if (insn == first) 50718334Speter set_new_first_and_last_insn (seq_insn, last); 50818334Speter 50918334Speter /* Build our SEQUENCE and rebuild the insn chain. */ 51018334Speter XVECEXP (seq, 0, 0) = delay_insn; 51118334Speter INSN_DELETED_P (delay_insn) = 0; 51218334Speter PREV_INSN (delay_insn) = PREV_INSN (seq_insn); 51318334Speter 51418334Speter for (li = list; li; li = XEXP (li, 1), i++) 51518334Speter { 51618334Speter rtx tem = XEXP (li, 0); 51790075Sobrien rtx note, next; 51818334Speter 51918334Speter /* Show that this copy of the insn isn't deleted. */ 52018334Speter INSN_DELETED_P (tem) = 0; 52118334Speter 52218334Speter XVECEXP (seq, 0, i) = tem; 52318334Speter PREV_INSN (tem) = XVECEXP (seq, 0, i - 1); 52418334Speter NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem; 52518334Speter 526132718Skan /* SPARC assembler, for instance, emit warning when debug info is output 527132718Skan into the delay slot. */ 528132718Skan if (INSN_LOCATOR (tem) && !INSN_LOCATOR (seq_insn)) 529132718Skan INSN_LOCATOR (seq_insn) = INSN_LOCATOR (tem); 530132718Skan INSN_LOCATOR (tem) = 0; 531132718Skan 53290075Sobrien for (note = REG_NOTES (tem); note; note = next) 53390075Sobrien { 53490075Sobrien next = XEXP (note, 1); 53590075Sobrien switch (REG_NOTE_KIND (note)) 53690075Sobrien { 53790075Sobrien case REG_DEAD: 53890075Sobrien /* Remove any REG_DEAD notes because we can't rely on them now 53990075Sobrien that the insn has been moved. */ 54090075Sobrien remove_note (tem, note); 54190075Sobrien break; 54290075Sobrien 54390075Sobrien case REG_LABEL: 54490075Sobrien /* Keep the label reference count up to date. */ 545169689Skan if (LABEL_P (XEXP (note, 0))) 54696263Sobrien LABEL_NUSES (XEXP (note, 0)) ++; 54790075Sobrien break; 54890075Sobrien 54990075Sobrien default: 55090075Sobrien break; 55190075Sobrien } 55290075Sobrien } 55318334Speter } 55418334Speter 55518334Speter NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn); 55618334Speter 55718334Speter /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the 55818334Speter last insn in that SEQUENCE to point to us. Similarly for the first 55918334Speter insn in the following insn if it is a SEQUENCE. */ 56018334Speter 561169689Skan if (PREV_INSN (seq_insn) && NONJUMP_INSN_P (PREV_INSN (seq_insn)) 56218334Speter && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE) 56318334Speter NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0, 56418334Speter XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1)) 56518334Speter = seq_insn; 56618334Speter 567169689Skan if (NEXT_INSN (seq_insn) && NONJUMP_INSN_P (NEXT_INSN (seq_insn)) 56818334Speter && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE) 56918334Speter PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn; 57090075Sobrien 57118334Speter /* If there used to be a BARRIER, put it back. */ 57218334Speter if (had_barrier) 57318334Speter emit_barrier_after (seq_insn); 57418334Speter 575169689Skan gcc_assert (i == length + 1); 57618334Speter 57718334Speter return seq_insn; 57818334Speter} 57918334Speter 58018334Speter/* Add INSN to DELAY_LIST and return the head of the new list. The list must 58118334Speter be in the order in which the insns are to be executed. */ 58218334Speter 58318334Speterstatic rtx 584132718Skanadd_to_delay_list (rtx insn, rtx delay_list) 58518334Speter{ 58618334Speter /* If we have an empty list, just make a new list element. If 58750397Sobrien INSN has its block number recorded, clear it since we may 58818334Speter be moving the insn to a new block. */ 58918334Speter 59018334Speter if (delay_list == 0) 59118334Speter { 59252284Sobrien clear_hashed_info_for_insn (insn); 59350397Sobrien return gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX); 59418334Speter } 59518334Speter 59618334Speter /* Otherwise this must be an INSN_LIST. Add INSN to the end of the 59718334Speter list. */ 59818334Speter XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1)); 59918334Speter 60018334Speter return delay_list; 60190075Sobrien} 60218334Speter 60352284Sobrien/* Delete INSN from the delay slot of the insn that it is in, which may 60452284Sobrien produce an insn with no delay slots. Return the new insn. */ 60518334Speter 60652284Sobrienstatic rtx 607132718Skandelete_from_delay_slot (rtx insn) 60818334Speter{ 60918334Speter rtx trial, seq_insn, seq, prev; 61018334Speter rtx delay_list = 0; 61118334Speter int i; 612169689Skan int had_barrier = 0; 61318334Speter 61418334Speter /* We first must find the insn containing the SEQUENCE with INSN in its 61518334Speter delay slot. Do this by finding an insn, TRIAL, where 61618334Speter PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */ 61718334Speter 61818334Speter for (trial = insn; 61918334Speter PREV_INSN (NEXT_INSN (trial)) == trial; 62018334Speter trial = NEXT_INSN (trial)) 62118334Speter ; 62218334Speter 62318334Speter seq_insn = PREV_INSN (NEXT_INSN (trial)); 62418334Speter seq = PATTERN (seq_insn); 62518334Speter 626169689Skan if (NEXT_INSN (seq_insn) && BARRIER_P (NEXT_INSN (seq_insn))) 627169689Skan had_barrier = 1; 628169689Skan 62918334Speter /* Create a delay list consisting of all the insns other than the one 63018334Speter we are deleting (unless we were the only one). */ 63118334Speter if (XVECLEN (seq, 0) > 2) 63218334Speter for (i = 1; i < XVECLEN (seq, 0); i++) 63318334Speter if (XVECEXP (seq, 0, i) != insn) 63418334Speter delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list); 63518334Speter 63618334Speter /* Delete the old SEQUENCE, re-emit the insn that used to have the delay 63718334Speter list, and rebuild the delay list if non-empty. */ 63818334Speter prev = PREV_INSN (seq_insn); 63918334Speter trial = XVECEXP (seq, 0, 0); 64090075Sobrien delete_related_insns (seq_insn); 64118334Speter add_insn_after (trial, prev); 64218334Speter 643169689Skan /* If there was a barrier after the old SEQUENCE, remit it. */ 644169689Skan if (had_barrier) 64518334Speter emit_barrier_after (trial); 64618334Speter 64718334Speter /* If there are any delay insns, remit them. Otherwise clear the 64818334Speter annul flag. */ 64918334Speter if (delay_list) 65050397Sobrien trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2); 651169689Skan else if (INSN_P (trial)) 65218334Speter INSN_ANNULLED_BRANCH_P (trial) = 0; 65318334Speter 65418334Speter INSN_FROM_TARGET_P (insn) = 0; 65518334Speter 65618334Speter /* Show we need to fill this insn again. */ 65718334Speter obstack_ptr_grow (&unfilled_slots_obstack, trial); 65852284Sobrien 65952284Sobrien return trial; 66018334Speter} 66118334Speter 66218334Speter/* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down 66318334Speter the insn that sets CC0 for it and delete it too. */ 66418334Speter 66518334Speterstatic void 666132718Skandelete_scheduled_jump (rtx insn) 66718334Speter{ 66818334Speter /* Delete the insn that sets cc0 for us. On machines without cc0, we could 66918334Speter delete the insn that sets the condition code, but it is hard to find it. 67018334Speter Since this case is rare anyway, don't bother trying; there would likely 67118334Speter be other insns that became dead anyway, which we wouldn't know to 67218334Speter delete. */ 67318334Speter 67418334Speter#ifdef HAVE_cc0 67518334Speter if (reg_mentioned_p (cc0_rtx, insn)) 67618334Speter { 67718334Speter rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX); 67818334Speter 67918334Speter /* If a reg-note was found, it points to an insn to set CC0. This 68018334Speter insn is in the delay list of some other insn. So delete it from 68118334Speter the delay list it was in. */ 68218334Speter if (note) 68318334Speter { 68418334Speter if (! FIND_REG_INC_NOTE (XEXP (note, 0), NULL_RTX) 68518334Speter && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1) 68618334Speter delete_from_delay_slot (XEXP (note, 0)); 68718334Speter } 68818334Speter else 68918334Speter { 69018334Speter /* The insn setting CC0 is our previous insn, but it may be in 69118334Speter a delay slot. It will be the last insn in the delay slot, if 69218334Speter it is. */ 69318334Speter rtx trial = previous_insn (insn); 694169689Skan if (NOTE_P (trial)) 69518334Speter trial = prev_nonnote_insn (trial); 69618334Speter if (sets_cc0_p (PATTERN (trial)) != 1 69790075Sobrien || FIND_REG_INC_NOTE (trial, NULL_RTX)) 69818334Speter return; 69918334Speter if (PREV_INSN (NEXT_INSN (trial)) == trial) 70090075Sobrien delete_related_insns (trial); 70118334Speter else 70218334Speter delete_from_delay_slot (trial); 70318334Speter } 70418334Speter } 70518334Speter#endif 70618334Speter 70790075Sobrien delete_related_insns (insn); 70818334Speter} 70918334Speter 71018334Speter/* Counters for delay-slot filling. */ 71118334Speter 71218334Speter#define NUM_REORG_FUNCTIONS 2 71318334Speter#define MAX_DELAY_HISTOGRAM 3 71418334Speter#define MAX_REORG_PASSES 2 71518334Speter 71618334Speterstatic int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES]; 71718334Speter 71818334Speterstatic int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES]; 71918334Speter 72018334Speterstatic int reorg_pass_number; 72118334Speter 72218334Speterstatic void 723132718Skannote_delay_statistics (int slots_filled, int index) 72418334Speter{ 72518334Speter num_insns_needing_delays[index][reorg_pass_number]++; 72618334Speter if (slots_filled > MAX_DELAY_HISTOGRAM) 72718334Speter slots_filled = MAX_DELAY_HISTOGRAM; 72818334Speter num_filled_delays[index][slots_filled][reorg_pass_number]++; 72918334Speter} 73018334Speter 73118334Speter#if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS) 73218334Speter 73318334Speter/* Optimize the following cases: 73418334Speter 73518334Speter 1. When a conditional branch skips over only one instruction, 73618334Speter use an annulling branch and put that insn in the delay slot. 73718334Speter Use either a branch that annuls when the condition if true or 73818334Speter invert the test with a branch that annuls when the condition is 73918334Speter false. This saves insns, since otherwise we must copy an insn 74018334Speter from the L1 target. 74118334Speter 74218334Speter (orig) (skip) (otherwise) 74318334Speter Bcc.n L1 Bcc',a L1 Bcc,a L1' 74418334Speter insn insn insn2 74518334Speter L1: L1: L1: 74618334Speter insn2 insn2 insn2 74718334Speter insn3 insn3 L1': 74818334Speter insn3 74918334Speter 75018334Speter 2. When a conditional branch skips over only one instruction, 75118334Speter and after that, it unconditionally branches somewhere else, 75218334Speter perform the similar optimization. This saves executing the 75318334Speter second branch in the case where the inverted condition is true. 75418334Speter 75518334Speter Bcc.n L1 Bcc',a L2 75618334Speter insn insn 75718334Speter L1: L1: 75818334Speter Bra L2 Bra L2 75918334Speter 76018334Speter INSN is a JUMP_INSN. 76118334Speter 76218334Speter This should be expanded to skip over N insns, where N is the number 76318334Speter of delay slots required. */ 76418334Speter 76518334Speterstatic rtx 766132718Skanoptimize_skip (rtx insn) 76718334Speter{ 76890075Sobrien rtx trial = next_nonnote_insn (insn); 76918334Speter rtx next_trial = next_active_insn (trial); 77018334Speter rtx delay_list = 0; 77118334Speter int flags; 77218334Speter 77318334Speter flags = get_jump_flags (insn, JUMP_LABEL (insn)); 77418334Speter 77518334Speter if (trial == 0 776169689Skan || !NONJUMP_INSN_P (trial) 77718334Speter || GET_CODE (PATTERN (trial)) == SEQUENCE 77818334Speter || recog_memoized (trial) < 0 77918334Speter || (! eligible_for_annul_false (insn, 0, trial, flags) 78096263Sobrien && ! eligible_for_annul_true (insn, 0, trial, flags)) 78196263Sobrien || can_throw_internal (trial)) 78218334Speter return 0; 78318334Speter 78418334Speter /* There are two cases where we are just executing one insn (we assume 78518334Speter here that a branch requires only one insn; this should be generalized 78618334Speter at some point): Where the branch goes around a single insn or where 78718334Speter we have one insn followed by a branch to the same label we branch to. 78818334Speter In both of these cases, inverting the jump and annulling the delay 78918334Speter slot give the same effect in fewer insns. */ 79090075Sobrien if ((next_trial == next_active_insn (JUMP_LABEL (insn)) 79190075Sobrien && ! (next_trial == 0 && current_function_epilogue_delay_list != 0)) 79218334Speter || (next_trial != 0 793169689Skan && JUMP_P (next_trial) 79418334Speter && JUMP_LABEL (insn) == JUMP_LABEL (next_trial) 79518334Speter && (simplejump_p (next_trial) 79618334Speter || GET_CODE (PATTERN (next_trial)) == RETURN))) 79718334Speter { 79818334Speter if (eligible_for_annul_false (insn, 0, trial, flags)) 79918334Speter { 80090075Sobrien if (invert_jump (insn, JUMP_LABEL (insn), 1)) 80118334Speter INSN_FROM_TARGET_P (trial) = 1; 80218334Speter else if (! eligible_for_annul_true (insn, 0, trial, flags)) 80318334Speter return 0; 80418334Speter } 80518334Speter 80618334Speter delay_list = add_to_delay_list (trial, NULL_RTX); 80718334Speter next_trial = next_active_insn (trial); 80818334Speter update_block (trial, trial); 80990075Sobrien delete_related_insns (trial); 81018334Speter 81118334Speter /* Also, if we are targeting an unconditional 81218334Speter branch, thread our jump to the target of that branch. Don't 81318334Speter change this into a RETURN here, because it may not accept what 81418334Speter we have in the delay slot. We'll fix this up later. */ 815169689Skan if (next_trial && JUMP_P (next_trial) 81618334Speter && (simplejump_p (next_trial) 81718334Speter || GET_CODE (PATTERN (next_trial)) == RETURN)) 81818334Speter { 819169689Skan rtx target_label = JUMP_LABEL (next_trial); 82018334Speter if (target_label == 0) 82118334Speter target_label = find_end_label (); 82218334Speter 823169689Skan if (target_label) 824169689Skan { 825169689Skan /* Recompute the flags based on TARGET_LABEL since threading 826169689Skan the jump to TARGET_LABEL may change the direction of the 827169689Skan jump (which may change the circumstances in which the 828169689Skan delay slot is nullified). */ 829169689Skan flags = get_jump_flags (insn, target_label); 830169689Skan if (eligible_for_annul_true (insn, 0, trial, flags)) 831169689Skan reorg_redirect_jump (insn, target_label); 832169689Skan } 83318334Speter } 83418334Speter 83518334Speter INSN_ANNULLED_BRANCH_P (insn) = 1; 83618334Speter } 83718334Speter 83818334Speter return delay_list; 83918334Speter} 84018334Speter#endif 84118334Speter 84218334Speter/* Encode and return branch direction and prediction information for 84318334Speter INSN assuming it will jump to LABEL. 84418334Speter 84518334Speter Non conditional branches return no direction information and 84618334Speter are predicted as very likely taken. */ 84750397Sobrien 84818334Speterstatic int 849132718Skanget_jump_flags (rtx insn, rtx label) 85018334Speter{ 85118334Speter int flags; 85218334Speter 85318334Speter /* get_jump_flags can be passed any insn with delay slots, these may 85418334Speter be INSNs, CALL_INSNs, or JUMP_INSNs. Only JUMP_INSNs have branch 85518334Speter direction information, and only if they are conditional jumps. 85618334Speter 85718334Speter If LABEL is zero, then there is no way to determine the branch 85818334Speter direction. */ 859169689Skan if (JUMP_P (insn) 86018334Speter && (condjump_p (insn) || condjump_in_parallel_p (insn)) 86118334Speter && INSN_UID (insn) <= max_uid 86218334Speter && label != 0 86318334Speter && INSN_UID (label) <= max_uid) 86490075Sobrien flags 86518334Speter = (uid_to_ruid[INSN_UID (label)] > uid_to_ruid[INSN_UID (insn)]) 86618334Speter ? ATTR_FLAG_forward : ATTR_FLAG_backward; 86718334Speter /* No valid direction information. */ 86818334Speter else 86918334Speter flags = 0; 87090075Sobrien 87118334Speter /* If insn is a conditional branch call mostly_true_jump to get 87290075Sobrien determine the branch prediction. 87318334Speter 87418334Speter Non conditional branches are predicted as very likely taken. */ 875169689Skan if (JUMP_P (insn) 87618334Speter && (condjump_p (insn) || condjump_in_parallel_p (insn))) 87718334Speter { 87818334Speter int prediction; 87918334Speter 88018334Speter prediction = mostly_true_jump (insn, get_branch_condition (insn, label)); 88118334Speter switch (prediction) 88218334Speter { 88390075Sobrien case 2: 88490075Sobrien flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely); 88590075Sobrien break; 88690075Sobrien case 1: 88790075Sobrien flags |= ATTR_FLAG_likely; 88890075Sobrien break; 88990075Sobrien case 0: 89090075Sobrien flags |= ATTR_FLAG_unlikely; 89190075Sobrien break; 89290075Sobrien case -1: 89390075Sobrien flags |= (ATTR_FLAG_very_unlikely | ATTR_FLAG_unlikely); 89490075Sobrien break; 89518334Speter 89690075Sobrien default: 897169689Skan gcc_unreachable (); 89818334Speter } 89918334Speter } 90018334Speter else 90118334Speter flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely); 90218334Speter 90318334Speter return flags; 90418334Speter} 90518334Speter 90618334Speter/* Return 1 if INSN is a destination that will be branched to rarely (the 90718334Speter return point of a function); return 2 if DEST will be branched to very 90818334Speter rarely (a call to a function that doesn't return). Otherwise, 90918334Speter return 0. */ 91018334Speter 91118334Speterstatic int 912132718Skanrare_destination (rtx insn) 91318334Speter{ 91418334Speter int jump_count = 0; 91518334Speter rtx next; 91618334Speter 91718334Speter for (; insn; insn = next) 91818334Speter { 919169689Skan if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == SEQUENCE) 92018334Speter insn = XVECEXP (PATTERN (insn), 0, 0); 92118334Speter 92218334Speter next = NEXT_INSN (insn); 92318334Speter 92418334Speter switch (GET_CODE (insn)) 92518334Speter { 92618334Speter case CODE_LABEL: 92718334Speter return 0; 92818334Speter case BARRIER: 92990075Sobrien /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN. We 93018334Speter don't scan past JUMP_INSNs, so any barrier we find here must 93118334Speter have been after a CALL_INSN and hence mean the call doesn't 93218334Speter return. */ 93318334Speter return 2; 93418334Speter case JUMP_INSN: 93518334Speter if (GET_CODE (PATTERN (insn)) == RETURN) 93618334Speter return 1; 93718334Speter else if (simplejump_p (insn) 93818334Speter && jump_count++ < 10) 93918334Speter next = JUMP_LABEL (insn); 94018334Speter else 94118334Speter return 0; 94250397Sobrien 94350397Sobrien default: 94450397Sobrien break; 94518334Speter } 94618334Speter } 94718334Speter 94818334Speter /* If we got here it means we hit the end of the function. So this 94918334Speter is an unlikely destination. */ 95018334Speter 95118334Speter return 1; 95218334Speter} 95318334Speter 95418334Speter/* Return truth value of the statement that this branch 95518334Speter is mostly taken. If we think that the branch is extremely likely 95618334Speter to be taken, we return 2. If the branch is slightly more likely to be 95718334Speter taken, return 1. If the branch is slightly less likely to be taken, 95818334Speter return 0 and if the branch is highly unlikely to be taken, return -1. 95918334Speter 960117395Skan CONDITION, if nonzero, is the condition that JUMP_INSN is testing. */ 96118334Speter 96218334Speterstatic int 963132718Skanmostly_true_jump (rtx jump_insn, rtx condition) 96418334Speter{ 96518334Speter rtx target_label = JUMP_LABEL (jump_insn); 966169689Skan rtx note; 967169689Skan int rare_dest, rare_fallthrough; 96818334Speter 96950397Sobrien /* If branch probabilities are available, then use that number since it 97050397Sobrien always gives a correct answer. */ 97190075Sobrien note = find_reg_note (jump_insn, REG_BR_PROB, 0); 97290075Sobrien if (note) 97350397Sobrien { 97490075Sobrien int prob = INTVAL (XEXP (note, 0)); 97550397Sobrien 97690075Sobrien if (prob >= REG_BR_PROB_BASE * 9 / 10) 97790075Sobrien return 2; 97890075Sobrien else if (prob >= REG_BR_PROB_BASE / 2) 97990075Sobrien return 1; 98090075Sobrien else if (prob >= REG_BR_PROB_BASE / 10) 98190075Sobrien return 0; 98290075Sobrien else 98390075Sobrien return -1; 98450397Sobrien } 98550397Sobrien 98618334Speter /* Look at the relative rarities of the fallthrough and destination. If 98750397Sobrien they differ, we can predict the branch that way. */ 988169689Skan rare_dest = rare_destination (target_label); 989169689Skan rare_fallthrough = rare_destination (NEXT_INSN (jump_insn)); 99018334Speter 99118334Speter switch (rare_fallthrough - rare_dest) 99218334Speter { 99318334Speter case -2: 99418334Speter return -1; 99518334Speter case -1: 99618334Speter return 0; 99718334Speter case 0: 99818334Speter break; 99918334Speter case 1: 100018334Speter return 1; 100118334Speter case 2: 100218334Speter return 2; 100318334Speter } 100418334Speter 100590075Sobrien /* If we couldn't figure out what this jump was, assume it won't be 100618334Speter taken. This should be rare. */ 100718334Speter if (condition == 0) 100818334Speter return 0; 100918334Speter 101018334Speter /* Predict backward branches usually take, forward branches usually not. If 101118334Speter we don't know whether this is forward or backward, assume the branch 101218334Speter will be taken, since most are. */ 101318334Speter return (target_label == 0 || INSN_UID (jump_insn) > max_uid 101418334Speter || INSN_UID (target_label) > max_uid 101518334Speter || (uid_to_ruid[INSN_UID (jump_insn)] 101690075Sobrien > uid_to_ruid[INSN_UID (target_label)])); 101718334Speter} 101818334Speter 101918334Speter/* Return the condition under which INSN will branch to TARGET. If TARGET 102018334Speter is zero, return the condition under which INSN will return. If INSN is 102118334Speter an unconditional branch, return const_true_rtx. If INSN isn't a simple 102218334Speter type of jump, or it doesn't go to TARGET, return 0. */ 102318334Speter 102418334Speterstatic rtx 1025132718Skanget_branch_condition (rtx insn, rtx target) 102618334Speter{ 102718334Speter rtx pat = PATTERN (insn); 102818334Speter rtx src; 102990075Sobrien 103018334Speter if (condjump_in_parallel_p (insn)) 103118334Speter pat = XVECEXP (pat, 0, 0); 103218334Speter 103318334Speter if (GET_CODE (pat) == RETURN) 103418334Speter return target == 0 ? const_true_rtx : 0; 103518334Speter 103618334Speter else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx) 103718334Speter return 0; 103818334Speter 103918334Speter src = SET_SRC (pat); 104018334Speter if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target) 104118334Speter return const_true_rtx; 104218334Speter 104318334Speter else if (GET_CODE (src) == IF_THEN_ELSE 104418334Speter && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN) 104518334Speter || (GET_CODE (XEXP (src, 1)) == LABEL_REF 104618334Speter && XEXP (XEXP (src, 1), 0) == target)) 104718334Speter && XEXP (src, 2) == pc_rtx) 104818334Speter return XEXP (src, 0); 104918334Speter 105018334Speter else if (GET_CODE (src) == IF_THEN_ELSE 105118334Speter && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN) 105218334Speter || (GET_CODE (XEXP (src, 2)) == LABEL_REF 105318334Speter && XEXP (XEXP (src, 2), 0) == target)) 105418334Speter && XEXP (src, 1) == pc_rtx) 105596263Sobrien { 105696263Sobrien enum rtx_code rev; 105796263Sobrien rev = reversed_comparison_code (XEXP (src, 0), insn); 105896263Sobrien if (rev != UNKNOWN) 105996263Sobrien return gen_rtx_fmt_ee (rev, GET_MODE (XEXP (src, 0)), 106096263Sobrien XEXP (XEXP (src, 0), 0), 106196263Sobrien XEXP (XEXP (src, 0), 1)); 106296263Sobrien } 106318334Speter 106418334Speter return 0; 106518334Speter} 106618334Speter 1067117395Skan/* Return nonzero if CONDITION is more strict than the condition of 106818334Speter INSN, i.e., if INSN will always branch if CONDITION is true. */ 106918334Speter 107018334Speterstatic int 1071132718Skancondition_dominates_p (rtx condition, rtx insn) 107218334Speter{ 107318334Speter rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn)); 107418334Speter enum rtx_code code = GET_CODE (condition); 107518334Speter enum rtx_code other_code; 107618334Speter 107718334Speter if (rtx_equal_p (condition, other_condition) 107818334Speter || other_condition == const_true_rtx) 107918334Speter return 1; 108018334Speter 108118334Speter else if (condition == const_true_rtx || other_condition == 0) 108218334Speter return 0; 108318334Speter 108418334Speter other_code = GET_CODE (other_condition); 108518334Speter if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2 108618334Speter || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0)) 108718334Speter || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1))) 108818334Speter return 0; 108918334Speter 109018334Speter return comparison_dominates_p (code, other_code); 109118334Speter} 109218334Speter 1093117395Skan/* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate 109418334Speter any insns already in the delay slot of JUMP. */ 109518334Speter 109618334Speterstatic int 1097132718Skanredirect_with_delay_slots_safe_p (rtx jump, rtx newlabel, rtx seq) 109818334Speter{ 109950397Sobrien int flags, i; 110018334Speter rtx pat = PATTERN (seq); 110118334Speter 110218334Speter /* Make sure all the delay slots of this jump would still 110318334Speter be valid after threading the jump. If they are still 1104117395Skan valid, then return nonzero. */ 110518334Speter 110618334Speter flags = get_jump_flags (jump, newlabel); 110718334Speter for (i = 1; i < XVECLEN (pat, 0); i++) 110818334Speter if (! ( 110918334Speter#ifdef ANNUL_IFFALSE_SLOTS 111018334Speter (INSN_ANNULLED_BRANCH_P (jump) 111118334Speter && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i))) 111218334Speter ? eligible_for_annul_false (jump, i - 1, 111318334Speter XVECEXP (pat, 0, i), flags) : 111418334Speter#endif 111518334Speter#ifdef ANNUL_IFTRUE_SLOTS 111618334Speter (INSN_ANNULLED_BRANCH_P (jump) 111718334Speter && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i))) 111818334Speter ? eligible_for_annul_true (jump, i - 1, 111918334Speter XVECEXP (pat, 0, i), flags) : 112018334Speter#endif 112190075Sobrien eligible_for_delay (jump, i - 1, XVECEXP (pat, 0, i), flags))) 112218334Speter break; 112318334Speter 112418334Speter return (i == XVECLEN (pat, 0)); 112518334Speter} 112618334Speter 1127117395Skan/* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate 112818334Speter any insns we wish to place in the delay slot of JUMP. */ 112918334Speter 113018334Speterstatic int 1131132718Skanredirect_with_delay_list_safe_p (rtx jump, rtx newlabel, rtx delay_list) 113218334Speter{ 113318334Speter int flags, i; 113418334Speter rtx li; 113518334Speter 113618334Speter /* Make sure all the insns in DELAY_LIST would still be 113718334Speter valid after threading the jump. If they are still 1138117395Skan valid, then return nonzero. */ 113918334Speter 114018334Speter flags = get_jump_flags (jump, newlabel); 114118334Speter for (li = delay_list, i = 0; li; li = XEXP (li, 1), i++) 114218334Speter if (! ( 114318334Speter#ifdef ANNUL_IFFALSE_SLOTS 114418334Speter (INSN_ANNULLED_BRANCH_P (jump) 114518334Speter && INSN_FROM_TARGET_P (XEXP (li, 0))) 114618334Speter ? eligible_for_annul_false (jump, i, XEXP (li, 0), flags) : 114718334Speter#endif 114818334Speter#ifdef ANNUL_IFTRUE_SLOTS 114918334Speter (INSN_ANNULLED_BRANCH_P (jump) 115018334Speter && ! INSN_FROM_TARGET_P (XEXP (li, 0))) 115118334Speter ? eligible_for_annul_true (jump, i, XEXP (li, 0), flags) : 115218334Speter#endif 115318334Speter eligible_for_delay (jump, i, XEXP (li, 0), flags))) 115418334Speter break; 115518334Speter 115618334Speter return (li == NULL); 115718334Speter} 115818334Speter 115952284Sobrien/* DELAY_LIST is a list of insns that have already been placed into delay 116052284Sobrien slots. See if all of them have the same annulling status as ANNUL_TRUE_P. 116152284Sobrien If not, return 0; otherwise return 1. */ 116252284Sobrien 116352284Sobrienstatic int 1164132718Skancheck_annul_list_true_false (int annul_true_p, rtx delay_list) 116552284Sobrien{ 116652284Sobrien rtx temp; 116752284Sobrien 116852284Sobrien if (delay_list) 116952284Sobrien { 117052284Sobrien for (temp = delay_list; temp; temp = XEXP (temp, 1)) 117190075Sobrien { 117290075Sobrien rtx trial = XEXP (temp, 0); 117390075Sobrien 117490075Sobrien if ((annul_true_p && INSN_FROM_TARGET_P (trial)) 117552284Sobrien || (!annul_true_p && !INSN_FROM_TARGET_P (trial))) 117652284Sobrien return 0; 117790075Sobrien } 117852284Sobrien } 117952284Sobrien 118052284Sobrien return 1; 118152284Sobrien} 118218334Speter 118318334Speter/* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that 118418334Speter the condition tested by INSN is CONDITION and the resources shown in 118518334Speter OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns 118618334Speter from SEQ's delay list, in addition to whatever insns it may execute 118718334Speter (in DELAY_LIST). SETS and NEEDED are denote resources already set and 118818334Speter needed while searching for delay slot insns. Return the concatenated 118918334Speter delay list if possible, otherwise, return 0. 119018334Speter 119118334Speter SLOTS_TO_FILL is the total number of slots required by INSN, and 119218334Speter PSLOTS_FILLED points to the number filled so far (also the number of 119318334Speter insns in DELAY_LIST). It is updated with the number that have been 119418334Speter filled from the SEQUENCE, if any. 119518334Speter 1196117395Skan PANNUL_P points to a nonzero value if we already know that we need 119718334Speter to annul INSN. If this routine determines that annulling is needed, 1198117395Skan it may set that value nonzero. 119918334Speter 120018334Speter PNEW_THREAD points to a location that is to receive the place at which 120118334Speter execution should continue. */ 120218334Speter 120318334Speterstatic rtx 1204132718Skansteal_delay_list_from_target (rtx insn, rtx condition, rtx seq, 1205132718Skan rtx delay_list, struct resources *sets, 1206132718Skan struct resources *needed, 1207132718Skan struct resources *other_needed, 1208132718Skan int slots_to_fill, int *pslots_filled, 1209132718Skan int *pannul_p, rtx *pnew_thread) 121018334Speter{ 121118334Speter rtx temp; 121218334Speter int slots_remaining = slots_to_fill - *pslots_filled; 121318334Speter int total_slots_filled = *pslots_filled; 121418334Speter rtx new_delay_list = 0; 121518334Speter int must_annul = *pannul_p; 121652284Sobrien int used_annul = 0; 121718334Speter int i; 121852284Sobrien struct resources cc_set; 121918334Speter 122018334Speter /* We can't do anything if there are more delay slots in SEQ than we 122118334Speter can handle, or if we don't know that it will be a taken branch. 122218334Speter We know that it will be a taken branch if it is either an unconditional 122318334Speter branch or a conditional branch with a stricter branch condition. 122418334Speter 122518334Speter Also, exit if the branch has more than one set, since then it is computing 122618334Speter other results that can't be ignored, e.g. the HPPA mov&branch instruction. 122718334Speter ??? It may be possible to move other sets into INSN in addition to 122852284Sobrien moving the instructions in the delay slots. 122918334Speter 123052284Sobrien We can not steal the delay list if one of the instructions in the 123190075Sobrien current delay_list modifies the condition codes and the jump in the 123252284Sobrien sequence is a conditional jump. We can not do this because we can 123352284Sobrien not change the direction of the jump because the condition codes 123490075Sobrien will effect the direction of the jump in the sequence. */ 123552284Sobrien 123652284Sobrien CLEAR_RESOURCE (&cc_set); 123752284Sobrien for (temp = delay_list; temp; temp = XEXP (temp, 1)) 123852284Sobrien { 123952284Sobrien rtx trial = XEXP (temp, 0); 124052284Sobrien 124190075Sobrien mark_set_resources (trial, &cc_set, 0, MARK_SRC_DEST_CALL); 124252284Sobrien if (insn_references_resource_p (XVECEXP (seq , 0, 0), &cc_set, 0)) 124390075Sobrien return delay_list; 124452284Sobrien } 124552284Sobrien 124618334Speter if (XVECLEN (seq, 0) - 1 > slots_remaining 124718334Speter || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0)) 124818334Speter || ! single_set (XVECEXP (seq, 0, 0))) 124918334Speter return delay_list; 125018334Speter 125190075Sobrien#ifdef MD_CAN_REDIRECT_BRANCH 125290075Sobrien /* On some targets, branches with delay slots can have a limited 125390075Sobrien displacement. Give the back end a chance to tell us we can't do 125490075Sobrien this. */ 125590075Sobrien if (! MD_CAN_REDIRECT_BRANCH (insn, XVECEXP (seq, 0, 0))) 125690075Sobrien return delay_list; 125790075Sobrien#endif 125890075Sobrien 125918334Speter for (i = 1; i < XVECLEN (seq, 0); i++) 126018334Speter { 126118334Speter rtx trial = XVECEXP (seq, 0, i); 126218334Speter int flags; 126318334Speter 126418334Speter if (insn_references_resource_p (trial, sets, 0) 126518334Speter || insn_sets_resource_p (trial, needed, 0) 126618334Speter || insn_sets_resource_p (trial, sets, 0) 126718334Speter#ifdef HAVE_cc0 126818334Speter /* If TRIAL sets CC0, we can't copy it, so we can't steal this 126918334Speter delay list. */ 127018334Speter || find_reg_note (trial, REG_CC_USER, NULL_RTX) 127118334Speter#endif 127218334Speter /* If TRIAL is from the fallthrough code of an annulled branch insn 127318334Speter in SEQ, we cannot use it. */ 127418334Speter || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0)) 127518334Speter && ! INSN_FROM_TARGET_P (trial))) 127618334Speter return delay_list; 127718334Speter 127818334Speter /* If this insn was already done (usually in a previous delay slot), 127918334Speter pretend we put it in our delay slot. */ 128018334Speter if (redundant_insn (trial, insn, new_delay_list)) 128118334Speter continue; 128218334Speter 128318334Speter /* We will end up re-vectoring this branch, so compute flags 128418334Speter based on jumping to the new label. */ 128518334Speter flags = get_jump_flags (insn, JUMP_LABEL (XVECEXP (seq, 0, 0))); 128618334Speter 128718334Speter if (! must_annul 128818334Speter && ((condition == const_true_rtx 128918334Speter || (! insn_sets_resource_p (trial, other_needed, 0) 1290169689Skan && ! may_trap_or_fault_p (PATTERN (trial))))) 129118334Speter ? eligible_for_delay (insn, total_slots_filled, trial, flags) 129252284Sobrien : (must_annul || (delay_list == NULL && new_delay_list == NULL)) 129352284Sobrien && (must_annul = 1, 129452284Sobrien check_annul_list_true_false (0, delay_list) 129552284Sobrien && check_annul_list_true_false (0, new_delay_list) 129652284Sobrien && eligible_for_annul_false (insn, total_slots_filled, 129752284Sobrien trial, flags))) 129818334Speter { 129952284Sobrien if (must_annul) 130052284Sobrien used_annul = 1; 130118334Speter temp = copy_rtx (trial); 130218334Speter INSN_FROM_TARGET_P (temp) = 1; 130318334Speter new_delay_list = add_to_delay_list (temp, new_delay_list); 130418334Speter total_slots_filled++; 130518334Speter 130618334Speter if (--slots_remaining == 0) 130718334Speter break; 130818334Speter } 130918334Speter else 131018334Speter return delay_list; 131118334Speter } 131218334Speter 131318334Speter /* Show the place to which we will be branching. */ 131418334Speter *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0))); 131518334Speter 131618334Speter /* Add any new insns to the delay list and update the count of the 131718334Speter number of slots filled. */ 131818334Speter *pslots_filled = total_slots_filled; 131952284Sobrien if (used_annul) 132052284Sobrien *pannul_p = 1; 132118334Speter 132218334Speter if (delay_list == 0) 132318334Speter return new_delay_list; 132418334Speter 132518334Speter for (temp = new_delay_list; temp; temp = XEXP (temp, 1)) 132618334Speter delay_list = add_to_delay_list (XEXP (temp, 0), delay_list); 132718334Speter 132818334Speter return delay_list; 132918334Speter} 133018334Speter 133190075Sobrien/* Similar to steal_delay_list_from_target except that SEQ is on the 133218334Speter fallthrough path of INSN. Here we only do something if the delay insn 133318334Speter of SEQ is an unconditional branch. In that case we steal its delay slot 133418334Speter for INSN since unconditional branches are much easier to fill. */ 133518334Speter 133618334Speterstatic rtx 1337132718Skansteal_delay_list_from_fallthrough (rtx insn, rtx condition, rtx seq, 1338132718Skan rtx delay_list, struct resources *sets, 1339132718Skan struct resources *needed, 1340132718Skan struct resources *other_needed, 1341132718Skan int slots_to_fill, int *pslots_filled, 1342132718Skan int *pannul_p) 134318334Speter{ 134418334Speter int i; 134518334Speter int flags; 134652284Sobrien int must_annul = *pannul_p; 134752284Sobrien int used_annul = 0; 134818334Speter 134918334Speter flags = get_jump_flags (insn, JUMP_LABEL (insn)); 135018334Speter 135118334Speter /* We can't do anything if SEQ's delay insn isn't an 135218334Speter unconditional branch. */ 135318334Speter 135418334Speter if (! simplejump_p (XVECEXP (seq, 0, 0)) 135518334Speter && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN) 135618334Speter return delay_list; 135718334Speter 135818334Speter for (i = 1; i < XVECLEN (seq, 0); i++) 135918334Speter { 136018334Speter rtx trial = XVECEXP (seq, 0, i); 136118334Speter 136218334Speter /* If TRIAL sets CC0, stealing it will move it too far from the use 136318334Speter of CC0. */ 136418334Speter if (insn_references_resource_p (trial, sets, 0) 136518334Speter || insn_sets_resource_p (trial, needed, 0) 136618334Speter || insn_sets_resource_p (trial, sets, 0) 136718334Speter#ifdef HAVE_cc0 136818334Speter || sets_cc0_p (PATTERN (trial)) 136918334Speter#endif 137018334Speter ) 137118334Speter 137218334Speter break; 137318334Speter 137418334Speter /* If this insn was already done, we don't need it. */ 137518334Speter if (redundant_insn (trial, insn, delay_list)) 137618334Speter { 137718334Speter delete_from_delay_slot (trial); 137818334Speter continue; 137918334Speter } 138018334Speter 138152284Sobrien if (! must_annul 138218334Speter && ((condition == const_true_rtx 138318334Speter || (! insn_sets_resource_p (trial, other_needed, 0) 1384169689Skan && ! may_trap_or_fault_p (PATTERN (trial))))) 138518334Speter ? eligible_for_delay (insn, *pslots_filled, trial, flags) 138652284Sobrien : (must_annul || delay_list == NULL) && (must_annul = 1, 138752284Sobrien check_annul_list_true_false (1, delay_list) 138852284Sobrien && eligible_for_annul_true (insn, *pslots_filled, trial, flags))) 138918334Speter { 139052284Sobrien if (must_annul) 139152284Sobrien used_annul = 1; 139218334Speter delete_from_delay_slot (trial); 139318334Speter delay_list = add_to_delay_list (trial, delay_list); 139418334Speter 139518334Speter if (++(*pslots_filled) == slots_to_fill) 139618334Speter break; 139718334Speter } 139818334Speter else 139918334Speter break; 140018334Speter } 140118334Speter 140252284Sobrien if (used_annul) 140352284Sobrien *pannul_p = 1; 140418334Speter return delay_list; 140518334Speter} 140618334Speter 140718334Speter/* Try merging insns starting at THREAD which match exactly the insns in 140818334Speter INSN's delay list. 140918334Speter 141018334Speter If all insns were matched and the insn was previously annulling, the 141118334Speter annul bit will be cleared. 141218334Speter 141318334Speter For each insn that is merged, if the branch is or will be non-annulling, 141418334Speter we delete the merged insn. */ 141518334Speter 141618334Speterstatic void 1417132718Skantry_merge_delay_insns (rtx insn, rtx thread) 141818334Speter{ 141918334Speter rtx trial, next_trial; 142018334Speter rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0); 142118334Speter int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn); 142218334Speter int slot_number = 1; 142318334Speter int num_slots = XVECLEN (PATTERN (insn), 0); 142418334Speter rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number); 142518334Speter struct resources set, needed; 142618334Speter rtx merged_insns = 0; 142718334Speter int i; 142818334Speter int flags; 142918334Speter 143018334Speter flags = get_jump_flags (delay_insn, JUMP_LABEL (delay_insn)); 143118334Speter 143218334Speter CLEAR_RESOURCE (&needed); 143318334Speter CLEAR_RESOURCE (&set); 143418334Speter 143518334Speter /* If this is not an annulling branch, take into account anything needed in 143652284Sobrien INSN's delay slot. This prevents two increments from being incorrectly 143718334Speter folded into one. If we are annulling, this would be the correct 143818334Speter thing to do. (The alternative, looking at things set in NEXT_TO_MATCH 143918334Speter will essentially disable this optimization. This method is somewhat of 144018334Speter a kludge, but I don't see a better way.) */ 144118334Speter if (! annul_p) 144290075Sobrien for (i = 1 ; i < num_slots; i++) 144352284Sobrien if (XVECEXP (PATTERN (insn), 0, i)) 144490075Sobrien mark_referenced_resources (XVECEXP (PATTERN (insn), 0, i), &needed, 1); 144518334Speter 144618334Speter for (trial = thread; !stop_search_p (trial, 1); trial = next_trial) 144718334Speter { 144818334Speter rtx pat = PATTERN (trial); 144918334Speter rtx oldtrial = trial; 145018334Speter 145118334Speter next_trial = next_nonnote_insn (trial); 145218334Speter 145318334Speter /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */ 1454169689Skan if (NONJUMP_INSN_P (trial) 145518334Speter && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)) 145618334Speter continue; 145718334Speter 145818334Speter if (GET_CODE (next_to_match) == GET_CODE (trial) 145918334Speter#ifdef HAVE_cc0 146018334Speter /* We can't share an insn that sets cc0. */ 146118334Speter && ! sets_cc0_p (pat) 146218334Speter#endif 146318334Speter && ! insn_references_resource_p (trial, &set, 1) 146418334Speter && ! insn_sets_resource_p (trial, &set, 1) 146518334Speter && ! insn_sets_resource_p (trial, &needed, 1) 146618334Speter && (trial = try_split (pat, trial, 0)) != 0 146718334Speter /* Update next_trial, in case try_split succeeded. */ 146818334Speter && (next_trial = next_nonnote_insn (trial)) 146918334Speter /* Likewise THREAD. */ 147018334Speter && (thread = oldtrial == thread ? trial : thread) 147118334Speter && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial)) 147218334Speter /* Have to test this condition if annul condition is different 147318334Speter from (and less restrictive than) non-annulling one. */ 147418334Speter && eligible_for_delay (delay_insn, slot_number - 1, trial, flags)) 147518334Speter { 147618334Speter 147718334Speter if (! annul_p) 147818334Speter { 147918334Speter update_block (trial, thread); 148018334Speter if (trial == thread) 148118334Speter thread = next_active_insn (thread); 148218334Speter 148390075Sobrien delete_related_insns (trial); 148418334Speter INSN_FROM_TARGET_P (next_to_match) = 0; 148518334Speter } 148618334Speter else 148750397Sobrien merged_insns = gen_rtx_INSN_LIST (VOIDmode, trial, merged_insns); 148818334Speter 148918334Speter if (++slot_number == num_slots) 149018334Speter break; 149118334Speter 149218334Speter next_to_match = XVECEXP (PATTERN (insn), 0, slot_number); 149318334Speter } 149418334Speter 149590075Sobrien mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL); 149618334Speter mark_referenced_resources (trial, &needed, 1); 149718334Speter } 149818334Speter 149918334Speter /* See if we stopped on a filled insn. If we did, try to see if its 150018334Speter delay slots match. */ 150118334Speter if (slot_number != num_slots 1502169689Skan && trial && NONJUMP_INSN_P (trial) 150318334Speter && GET_CODE (PATTERN (trial)) == SEQUENCE 150418334Speter && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0))) 150518334Speter { 150618334Speter rtx pat = PATTERN (trial); 150718334Speter rtx filled_insn = XVECEXP (pat, 0, 0); 150818334Speter 150918334Speter /* Account for resources set/needed by the filled insn. */ 151090075Sobrien mark_set_resources (filled_insn, &set, 0, MARK_SRC_DEST_CALL); 151118334Speter mark_referenced_resources (filled_insn, &needed, 1); 151218334Speter 151318334Speter for (i = 1; i < XVECLEN (pat, 0); i++) 151418334Speter { 151518334Speter rtx dtrial = XVECEXP (pat, 0, i); 151618334Speter 151718334Speter if (! insn_references_resource_p (dtrial, &set, 1) 151818334Speter && ! insn_sets_resource_p (dtrial, &set, 1) 151918334Speter && ! insn_sets_resource_p (dtrial, &needed, 1) 152018334Speter#ifdef HAVE_cc0 152118334Speter && ! sets_cc0_p (PATTERN (dtrial)) 152218334Speter#endif 152318334Speter && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial)) 152418334Speter && eligible_for_delay (delay_insn, slot_number - 1, dtrial, flags)) 152518334Speter { 152618334Speter if (! annul_p) 152718334Speter { 152852284Sobrien rtx new; 152952284Sobrien 153018334Speter update_block (dtrial, thread); 153152284Sobrien new = delete_from_delay_slot (dtrial); 153252284Sobrien if (INSN_DELETED_P (thread)) 153352284Sobrien thread = new; 153418334Speter INSN_FROM_TARGET_P (next_to_match) = 0; 153518334Speter } 153618334Speter else 153750397Sobrien merged_insns = gen_rtx_INSN_LIST (SImode, dtrial, 153850397Sobrien merged_insns); 153918334Speter 154018334Speter if (++slot_number == num_slots) 154118334Speter break; 154218334Speter 154318334Speter next_to_match = XVECEXP (PATTERN (insn), 0, slot_number); 154418334Speter } 154552284Sobrien else 154652284Sobrien { 154752284Sobrien /* Keep track of the set/referenced resources for the delay 154852284Sobrien slots of any trial insns we encounter. */ 154990075Sobrien mark_set_resources (dtrial, &set, 0, MARK_SRC_DEST_CALL); 155090075Sobrien mark_referenced_resources (dtrial, &needed, 1); 155152284Sobrien } 155218334Speter } 155318334Speter } 155418334Speter 155518334Speter /* If all insns in the delay slot have been matched and we were previously 155618334Speter annulling the branch, we need not any more. In that case delete all the 155750397Sobrien merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn in 155818334Speter the delay list so that we know that it isn't only being used at the 155918334Speter target. */ 156018334Speter if (slot_number == num_slots && annul_p) 156118334Speter { 156218334Speter for (; merged_insns; merged_insns = XEXP (merged_insns, 1)) 156318334Speter { 156418334Speter if (GET_MODE (merged_insns) == SImode) 156518334Speter { 156652284Sobrien rtx new; 156752284Sobrien 156818334Speter update_block (XEXP (merged_insns, 0), thread); 156952284Sobrien new = delete_from_delay_slot (XEXP (merged_insns, 0)); 157052284Sobrien if (INSN_DELETED_P (thread)) 157152284Sobrien thread = new; 157218334Speter } 157318334Speter else 157418334Speter { 157518334Speter update_block (XEXP (merged_insns, 0), thread); 157690075Sobrien delete_related_insns (XEXP (merged_insns, 0)); 157718334Speter } 157818334Speter } 157918334Speter 158018334Speter INSN_ANNULLED_BRANCH_P (delay_insn) = 0; 158118334Speter 158218334Speter for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++) 158318334Speter INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0; 158418334Speter } 158518334Speter} 158618334Speter 158718334Speter/* See if INSN is redundant with an insn in front of TARGET. Often this 158818334Speter is called when INSN is a candidate for a delay slot of TARGET. 158918334Speter DELAY_LIST are insns that will be placed in delay slots of TARGET in front 159018334Speter of INSN. Often INSN will be redundant with an insn in a delay slot of 159118334Speter some previous insn. This happens when we have a series of branches to the 159218334Speter same label; in that case the first insn at the target might want to go 159318334Speter into each of the delay slots. 159418334Speter 159518334Speter If we are not careful, this routine can take up a significant fraction 159618334Speter of the total compilation time (4%), but only wins rarely. Hence we 159718334Speter speed this routine up by making two passes. The first pass goes back 1598132718Skan until it hits a label and sees if it finds an insn with an identical 159918334Speter pattern. Only in this (relatively rare) event does it check for 160018334Speter data conflicts. 160118334Speter 160218334Speter We do not split insns we encounter. This could cause us not to find a 160318334Speter redundant insn, but the cost of splitting seems greater than the possible 160418334Speter gain in rare cases. */ 160518334Speter 160618334Speterstatic rtx 1607132718Skanredundant_insn (rtx insn, rtx target, rtx delay_list) 160818334Speter{ 160918334Speter rtx target_main = target; 161018334Speter rtx ipat = PATTERN (insn); 161118334Speter rtx trial, pat; 161218334Speter struct resources needed, set; 161318334Speter int i; 161490075Sobrien unsigned insns_to_search; 161518334Speter 161650397Sobrien /* If INSN has any REG_UNUSED notes, it can't match anything since we 161750397Sobrien are allowed to not actually assign to such a register. */ 161850397Sobrien if (find_reg_note (insn, REG_UNUSED, NULL_RTX) != 0) 161950397Sobrien return 0; 162050397Sobrien 162118334Speter /* Scan backwards looking for a match. */ 162290075Sobrien for (trial = PREV_INSN (target), 162390075Sobrien insns_to_search = MAX_DELAY_SLOT_INSN_SEARCH; 162490075Sobrien trial && insns_to_search > 0; 162590075Sobrien trial = PREV_INSN (trial), --insns_to_search) 162618334Speter { 1627169689Skan if (LABEL_P (trial)) 162818334Speter return 0; 162918334Speter 163090075Sobrien if (! INSN_P (trial)) 163118334Speter continue; 163218334Speter 163318334Speter pat = PATTERN (trial); 163418334Speter if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 163518334Speter continue; 163618334Speter 163718334Speter if (GET_CODE (pat) == SEQUENCE) 163818334Speter { 163918334Speter /* Stop for a CALL and its delay slots because it is difficult to 164018334Speter track its resource needs correctly. */ 1641169689Skan if (CALL_P (XVECEXP (pat, 0, 0))) 164218334Speter return 0; 164318334Speter 164418334Speter /* Stop for an INSN or JUMP_INSN with delayed effects and its delay 164590075Sobrien slots because it is difficult to track its resource needs 164618334Speter correctly. */ 164718334Speter 164818334Speter#ifdef INSN_SETS_ARE_DELAYED 164918334Speter if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0))) 165090075Sobrien return 0; 165118334Speter#endif 165218334Speter 165318334Speter#ifdef INSN_REFERENCES_ARE_DELAYED 165418334Speter if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0))) 165590075Sobrien return 0; 165618334Speter#endif 165718334Speter 165818334Speter /* See if any of the insns in the delay slot match, updating 165918334Speter resource requirements as we go. */ 166018334Speter for (i = XVECLEN (pat, 0) - 1; i > 0; i--) 166118334Speter if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn) 166250397Sobrien && rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat) 166350397Sobrien && ! find_reg_note (XVECEXP (pat, 0, i), REG_UNUSED, NULL_RTX)) 166418334Speter break; 166518334Speter 166618334Speter /* If found a match, exit this loop early. */ 166718334Speter if (i > 0) 166818334Speter break; 166918334Speter } 167018334Speter 167150397Sobrien else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat) 167250397Sobrien && ! find_reg_note (trial, REG_UNUSED, NULL_RTX)) 167318334Speter break; 167418334Speter } 167518334Speter 167618334Speter /* If we didn't find an insn that matches, return 0. */ 167718334Speter if (trial == 0) 167818334Speter return 0; 167918334Speter 168018334Speter /* See what resources this insn sets and needs. If they overlap, or 168118334Speter if this insn references CC0, it can't be redundant. */ 168218334Speter 168318334Speter CLEAR_RESOURCE (&needed); 168418334Speter CLEAR_RESOURCE (&set); 168590075Sobrien mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL); 168618334Speter mark_referenced_resources (insn, &needed, 1); 168718334Speter 168818334Speter /* If TARGET is a SEQUENCE, get the main insn. */ 1689169689Skan if (NONJUMP_INSN_P (target) && GET_CODE (PATTERN (target)) == SEQUENCE) 169018334Speter target_main = XVECEXP (PATTERN (target), 0, 0); 169118334Speter 169218334Speter if (resource_conflicts_p (&needed, &set) 169318334Speter#ifdef HAVE_cc0 169418334Speter || reg_mentioned_p (cc0_rtx, ipat) 169518334Speter#endif 169618334Speter /* The insn requiring the delay may not set anything needed or set by 169718334Speter INSN. */ 169818334Speter || insn_sets_resource_p (target_main, &needed, 1) 169918334Speter || insn_sets_resource_p (target_main, &set, 1)) 170018334Speter return 0; 170118334Speter 170218334Speter /* Insns we pass may not set either NEEDED or SET, so merge them for 170318334Speter simpler tests. */ 170418334Speter needed.memory |= set.memory; 170518334Speter needed.unch_memory |= set.unch_memory; 170618334Speter IOR_HARD_REG_SET (needed.regs, set.regs); 170718334Speter 170818334Speter /* This insn isn't redundant if it conflicts with an insn that either is 170918334Speter or will be in a delay slot of TARGET. */ 171018334Speter 171118334Speter while (delay_list) 171218334Speter { 171318334Speter if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1)) 171418334Speter return 0; 171518334Speter delay_list = XEXP (delay_list, 1); 171618334Speter } 171718334Speter 1718169689Skan if (NONJUMP_INSN_P (target) && GET_CODE (PATTERN (target)) == SEQUENCE) 171918334Speter for (i = 1; i < XVECLEN (PATTERN (target), 0); i++) 172018334Speter if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1)) 172118334Speter return 0; 172218334Speter 172318334Speter /* Scan backwards until we reach a label or an insn that uses something 172418334Speter INSN sets or sets something insn uses or sets. */ 172518334Speter 172690075Sobrien for (trial = PREV_INSN (target), 172790075Sobrien insns_to_search = MAX_DELAY_SLOT_INSN_SEARCH; 1728169689Skan trial && !LABEL_P (trial) && insns_to_search > 0; 172990075Sobrien trial = PREV_INSN (trial), --insns_to_search) 173018334Speter { 1731169689Skan if (!INSN_P (trial)) 173218334Speter continue; 173318334Speter 173418334Speter pat = PATTERN (trial); 173518334Speter if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 173618334Speter continue; 173718334Speter 173818334Speter if (GET_CODE (pat) == SEQUENCE) 173918334Speter { 174018334Speter /* If this is a CALL_INSN and its delay slots, it is hard to track 174118334Speter the resource needs properly, so give up. */ 1742169689Skan if (CALL_P (XVECEXP (pat, 0, 0))) 174318334Speter return 0; 174418334Speter 174550397Sobrien /* If this is an INSN or JUMP_INSN with delayed effects, it 174618334Speter is hard to track the resource needs properly, so give up. */ 174718334Speter 174818334Speter#ifdef INSN_SETS_ARE_DELAYED 174918334Speter if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0))) 175090075Sobrien return 0; 175118334Speter#endif 175218334Speter 175318334Speter#ifdef INSN_REFERENCES_ARE_DELAYED 175418334Speter if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0))) 175590075Sobrien return 0; 175618334Speter#endif 175718334Speter 175818334Speter /* See if any of the insns in the delay slot match, updating 175918334Speter resource requirements as we go. */ 176018334Speter for (i = XVECLEN (pat, 0) - 1; i > 0; i--) 176118334Speter { 176218334Speter rtx candidate = XVECEXP (pat, 0, i); 176318334Speter 176418334Speter /* If an insn will be annulled if the branch is false, it isn't 176518334Speter considered as a possible duplicate insn. */ 176618334Speter if (rtx_equal_p (PATTERN (candidate), ipat) 176718334Speter && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0)) 176818334Speter && INSN_FROM_TARGET_P (candidate))) 176918334Speter { 177018334Speter /* Show that this insn will be used in the sequel. */ 177118334Speter INSN_FROM_TARGET_P (candidate) = 0; 177218334Speter return candidate; 177318334Speter } 177418334Speter 177518334Speter /* Unless this is an annulled insn from the target of a branch, 177618334Speter we must stop if it sets anything needed or set by INSN. */ 177718334Speter if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0)) 177818334Speter || ! INSN_FROM_TARGET_P (candidate)) 177918334Speter && insn_sets_resource_p (candidate, &needed, 1)) 178018334Speter return 0; 178118334Speter } 178218334Speter 178390075Sobrien /* If the insn requiring the delay slot conflicts with INSN, we 178418334Speter must stop. */ 178518334Speter if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1)) 178618334Speter return 0; 178718334Speter } 178818334Speter else 178918334Speter { 179018334Speter /* See if TRIAL is the same as INSN. */ 179118334Speter pat = PATTERN (trial); 179218334Speter if (rtx_equal_p (pat, ipat)) 179318334Speter return trial; 179418334Speter 179518334Speter /* Can't go any further if TRIAL conflicts with INSN. */ 179618334Speter if (insn_sets_resource_p (trial, &needed, 1)) 179718334Speter return 0; 179818334Speter } 179918334Speter } 180018334Speter 180118334Speter return 0; 180218334Speter} 180318334Speter 1804117395Skan/* Return 1 if THREAD can only be executed in one way. If LABEL is nonzero, 180518334Speter it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH 1806117395Skan is nonzero, we are allowed to fall into this thread; otherwise, we are 180718334Speter not. 180818334Speter 180918334Speter If LABEL is used more than one or we pass a label other than LABEL before 181018334Speter finding an active insn, we do not own this thread. */ 181118334Speter 181218334Speterstatic int 1813132718Skanown_thread_p (rtx thread, rtx label, int allow_fallthrough) 181418334Speter{ 181518334Speter rtx active_insn; 181618334Speter rtx insn; 181718334Speter 181818334Speter /* We don't own the function end. */ 181918334Speter if (thread == 0) 182018334Speter return 0; 182118334Speter 182218334Speter /* Get the first active insn, or THREAD, if it is an active insn. */ 182318334Speter active_insn = next_active_insn (PREV_INSN (thread)); 182418334Speter 182518334Speter for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn)) 1826169689Skan if (LABEL_P (insn) 182718334Speter && (insn != label || LABEL_NUSES (insn) != 1)) 182818334Speter return 0; 182918334Speter 183018334Speter if (allow_fallthrough) 183118334Speter return 1; 183218334Speter 183318334Speter /* Ensure that we reach a BARRIER before any insn or label. */ 183418334Speter for (insn = prev_nonnote_insn (thread); 1835169689Skan insn == 0 || !BARRIER_P (insn); 183618334Speter insn = prev_nonnote_insn (insn)) 183718334Speter if (insn == 0 1838169689Skan || LABEL_P (insn) 1839169689Skan || (NONJUMP_INSN_P (insn) 184018334Speter && GET_CODE (PATTERN (insn)) != USE 184118334Speter && GET_CODE (PATTERN (insn)) != CLOBBER)) 184218334Speter return 0; 184318334Speter 184418334Speter return 1; 184518334Speter} 184618334Speter 184718334Speter/* Called when INSN is being moved from a location near the target of a jump. 184818334Speter We leave a marker of the form (use (INSN)) immediately in front 184918334Speter of WHERE for mark_target_live_regs. These markers will be deleted when 185018334Speter reorg finishes. 185118334Speter 185218334Speter We used to try to update the live status of registers if WHERE is at 185318334Speter the start of a basic block, but that can't work since we may remove a 185418334Speter BARRIER in relax_delay_slots. */ 185518334Speter 185618334Speterstatic void 1857132718Skanupdate_block (rtx insn, rtx where) 185818334Speter{ 185990075Sobrien /* Ignore if this was in a delay slot and it came from the target of 186018334Speter a branch. */ 186118334Speter if (INSN_FROM_TARGET_P (insn)) 186218334Speter return; 186318334Speter 186450397Sobrien emit_insn_before (gen_rtx_USE (VOIDmode, insn), where); 186518334Speter 186618334Speter /* INSN might be making a value live in a block where it didn't use to 186718334Speter be. So recompute liveness information for this block. */ 186818334Speter 186952284Sobrien incr_ticks_for_insn (insn); 187018334Speter} 187118334Speter 187218334Speter/* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for 187318334Speter the basic block containing the jump. */ 187418334Speter 187518334Speterstatic int 1876132718Skanreorg_redirect_jump (rtx jump, rtx nlabel) 187718334Speter{ 187852284Sobrien incr_ticks_for_insn (jump); 187990075Sobrien return redirect_jump (jump, nlabel, 1); 188018334Speter} 188118334Speter 188218334Speter/* Called when INSN is being moved forward into a delay slot of DELAYED_INSN. 188318334Speter We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes 188418334Speter that reference values used in INSN. If we find one, then we move the 188518334Speter REG_DEAD note to INSN. 188618334Speter 1887169689Skan This is needed to handle the case where a later insn (after INSN) has a 188818334Speter REG_DEAD note for a register used by INSN, and this later insn subsequently 188918334Speter gets moved before a CODE_LABEL because it is a redundant insn. In this 189018334Speter case, mark_target_live_regs may be confused into thinking the register 189118334Speter is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */ 189218334Speter 189318334Speterstatic void 1894132718Skanupdate_reg_dead_notes (rtx insn, rtx delayed_insn) 189518334Speter{ 189618334Speter rtx p, link, next; 189718334Speter 189818334Speter for (p = next_nonnote_insn (insn); p != delayed_insn; 189918334Speter p = next_nonnote_insn (p)) 190018334Speter for (link = REG_NOTES (p); link; link = next) 190118334Speter { 190218334Speter next = XEXP (link, 1); 190318334Speter 190418334Speter if (REG_NOTE_KIND (link) != REG_DEAD 1905169689Skan || !REG_P (XEXP (link, 0))) 190618334Speter continue; 190718334Speter 190818334Speter if (reg_referenced_p (XEXP (link, 0), PATTERN (insn))) 190918334Speter { 191018334Speter /* Move the REG_DEAD note from P to INSN. */ 191118334Speter remove_note (p, link); 191218334Speter XEXP (link, 1) = REG_NOTES (insn); 191318334Speter REG_NOTES (insn) = link; 191418334Speter } 191518334Speter } 191618334Speter} 191718334Speter 191850397Sobrien/* Called when an insn redundant with start_insn is deleted. If there 191950397Sobrien is a REG_DEAD note for the target of start_insn between start_insn 192050397Sobrien and stop_insn, then the REG_DEAD note needs to be deleted since the 192150397Sobrien value no longer dies there. 192250397Sobrien 192350397Sobrien If the REG_DEAD note isn't deleted, then mark_target_live_regs may be 192450397Sobrien confused into thinking the register is dead. */ 192550397Sobrien 192650397Sobrienstatic void 1927132718Skanfix_reg_dead_note (rtx start_insn, rtx stop_insn) 192850397Sobrien{ 192950397Sobrien rtx p, link, next; 193050397Sobrien 193150397Sobrien for (p = next_nonnote_insn (start_insn); p != stop_insn; 193250397Sobrien p = next_nonnote_insn (p)) 193350397Sobrien for (link = REG_NOTES (p); link; link = next) 193450397Sobrien { 193550397Sobrien next = XEXP (link, 1); 193650397Sobrien 193750397Sobrien if (REG_NOTE_KIND (link) != REG_DEAD 1938169689Skan || !REG_P (XEXP (link, 0))) 193950397Sobrien continue; 194050397Sobrien 194150397Sobrien if (reg_set_p (XEXP (link, 0), PATTERN (start_insn))) 194250397Sobrien { 194350397Sobrien remove_note (p, link); 194450397Sobrien return; 194550397Sobrien } 194650397Sobrien } 194750397Sobrien} 194850397Sobrien 194918334Speter/* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN. 195018334Speter 195118334Speter This handles the case of udivmodXi4 instructions which optimize their 195218334Speter output depending on whether any REG_UNUSED notes are present. 195318334Speter we must make sure that INSN calculates as many results as REDUNDANT_INSN 195418334Speter does. */ 195518334Speter 195618334Speterstatic void 1957132718Skanupdate_reg_unused_notes (rtx insn, rtx redundant_insn) 195818334Speter{ 195950397Sobrien rtx link, next; 196018334Speter 196118334Speter for (link = REG_NOTES (insn); link; link = next) 196218334Speter { 196318334Speter next = XEXP (link, 1); 196418334Speter 196518334Speter if (REG_NOTE_KIND (link) != REG_UNUSED 1966169689Skan || !REG_P (XEXP (link, 0))) 196718334Speter continue; 196818334Speter 196918334Speter if (! find_regno_note (redundant_insn, REG_UNUSED, 197018334Speter REGNO (XEXP (link, 0)))) 197118334Speter remove_note (insn, link); 197218334Speter } 197318334Speter} 197418334Speter 197518334Speter/* Scan a function looking for insns that need a delay slot and find insns to 197618334Speter put into the delay slot. 197718334Speter 1978117395Skan NON_JUMPS_P is nonzero if we are to only try to fill non-jump insns (such 197918334Speter as calls). We do these first since we don't want jump insns (that are 198018334Speter easier to fill) to get the only insns that could be used for non-jump insns. 198118334Speter When it is zero, only try to fill JUMP_INSNs. 198218334Speter 198318334Speter When slots are filled in this manner, the insns (including the 198418334Speter delay_insn) are put together in a SEQUENCE rtx. In this fashion, 198518334Speter it is possible to tell whether a delay slot has really been filled 198618334Speter or not. `final' knows how to deal with this, by communicating 198718334Speter through FINAL_SEQUENCE. */ 198818334Speter 198918334Speterstatic void 1990132718Skanfill_simple_delay_slots (int non_jumps_p) 199118334Speter{ 199290075Sobrien rtx insn, pat, trial, next_trial; 199390075Sobrien int i; 199418334Speter int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base; 199518334Speter struct resources needed, set; 199650397Sobrien int slots_to_fill, slots_filled; 199718334Speter rtx delay_list; 199818334Speter 199918334Speter for (i = 0; i < num_unfilled_slots; i++) 200018334Speter { 200118334Speter int flags; 200218334Speter /* Get the next insn to fill. If it has already had any slots assigned, 200318334Speter we can't do anything with it. Maybe we'll improve this later. */ 200418334Speter 200518334Speter insn = unfilled_slots_base[i]; 200618334Speter if (insn == 0 200718334Speter || INSN_DELETED_P (insn) 2008169689Skan || (NONJUMP_INSN_P (insn) 200918334Speter && GET_CODE (PATTERN (insn)) == SEQUENCE) 2010169689Skan || (JUMP_P (insn) && non_jumps_p) 2011169689Skan || (!JUMP_P (insn) && ! non_jumps_p)) 201218334Speter continue; 201390075Sobrien 201490075Sobrien /* It may have been that this insn used to need delay slots, but 201590075Sobrien now doesn't; ignore in that case. This can happen, for example, 201690075Sobrien on the HP PA RISC, where the number of delay slots depends on 201790075Sobrien what insns are nearby. */ 201818334Speter slots_to_fill = num_delay_slots (insn); 201950397Sobrien 202050397Sobrien /* Some machine description have defined instructions to have 202150397Sobrien delay slots only in certain circumstances which may depend on 202250397Sobrien nearby insns (which change due to reorg's actions). 202350397Sobrien 202450397Sobrien For example, the PA port normally has delay slots for unconditional 202550397Sobrien jumps. 202650397Sobrien 202750397Sobrien However, the PA port claims such jumps do not have a delay slot 202850397Sobrien if they are immediate successors of certain CALL_INSNs. This 202950397Sobrien allows the port to favor filling the delay slot of the call with 203050397Sobrien the unconditional jump. */ 203118334Speter if (slots_to_fill == 0) 203250397Sobrien continue; 203318334Speter 203418334Speter /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL 203518334Speter says how many. After initialization, first try optimizing 203618334Speter 203718334Speter call _foo call _foo 203818334Speter nop add %o7,.-L1,%o7 203918334Speter b,a L1 204018334Speter nop 204118334Speter 204218334Speter If this case applies, the delay slot of the call is filled with 204318334Speter the unconditional jump. This is done first to avoid having the 204418334Speter delay slot of the call filled in the backward scan. Also, since 204518334Speter the unconditional jump is likely to also have a delay slot, that 204618334Speter insn must exist when it is subsequently scanned. 204718334Speter 204818334Speter This is tried on each insn with delay slots as some machines 204990075Sobrien have insns which perform calls, but are not represented as 205018334Speter CALL_INSNs. */ 205118334Speter 205218334Speter slots_filled = 0; 205318334Speter delay_list = 0; 205418334Speter 2055169689Skan if (JUMP_P (insn)) 205690075Sobrien flags = get_jump_flags (insn, JUMP_LABEL (insn)); 205790075Sobrien else 205890075Sobrien flags = get_jump_flags (insn, NULL_RTX); 205990075Sobrien 206018334Speter if ((trial = next_active_insn (insn)) 2061169689Skan && JUMP_P (trial) 206218334Speter && simplejump_p (trial) 206318334Speter && eligible_for_delay (insn, slots_filled, trial, flags) 206496263Sobrien && no_labels_between_p (insn, trial) 206596263Sobrien && ! can_throw_internal (trial)) 206618334Speter { 206718334Speter rtx *tmp; 206818334Speter slots_filled++; 206918334Speter delay_list = add_to_delay_list (trial, delay_list); 207018334Speter 207118334Speter /* TRIAL may have had its delay slot filled, then unfilled. When 207218334Speter the delay slot is unfilled, TRIAL is placed back on the unfilled 207318334Speter slots obstack. Unfortunately, it is placed on the end of the 207418334Speter obstack, not in its original location. Therefore, we must search 207518334Speter from entry i + 1 to the end of the unfilled slots obstack to 207618334Speter try and find TRIAL. */ 207718334Speter tmp = &unfilled_slots_base[i + 1]; 207818334Speter while (*tmp != trial && tmp != unfilled_slots_next) 207918334Speter tmp++; 208018334Speter 208118334Speter /* Remove the unconditional jump from consideration for delay slot 208290075Sobrien filling and unthread it. */ 208318334Speter if (*tmp == trial) 208418334Speter *tmp = 0; 208518334Speter { 208618334Speter rtx next = NEXT_INSN (trial); 208718334Speter rtx prev = PREV_INSN (trial); 208818334Speter if (prev) 208918334Speter NEXT_INSN (prev) = next; 209018334Speter if (next) 209118334Speter PREV_INSN (next) = prev; 209218334Speter } 209318334Speter } 209418334Speter 209518334Speter /* Now, scan backwards from the insn to search for a potential 209618334Speter delay-slot candidate. Stop searching when a label or jump is hit. 209718334Speter 209818334Speter For each candidate, if it is to go into the delay slot (moved 209918334Speter forward in execution sequence), it must not need or set any resources 210018334Speter that were set by later insns and must not set any resources that 210118334Speter are needed for those insns. 210290075Sobrien 210318334Speter The delay slot insn itself sets resources unless it is a call 210418334Speter (in which case the called routine, not the insn itself, is doing 210518334Speter the setting). */ 210618334Speter 210718334Speter if (slots_filled < slots_to_fill) 210818334Speter { 210918334Speter CLEAR_RESOURCE (&needed); 211018334Speter CLEAR_RESOURCE (&set); 211190075Sobrien mark_set_resources (insn, &set, 0, MARK_SRC_DEST); 211218334Speter mark_referenced_resources (insn, &needed, 0); 211318334Speter 211418334Speter for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1); 211518334Speter trial = next_trial) 211618334Speter { 211718334Speter next_trial = prev_nonnote_insn (trial); 211818334Speter 211918334Speter /* This must be an INSN or CALL_INSN. */ 212018334Speter pat = PATTERN (trial); 212118334Speter 212218334Speter /* USE and CLOBBER at this level was just for flow; ignore it. */ 212318334Speter if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 212418334Speter continue; 212518334Speter 212690075Sobrien /* Check for resource conflict first, to avoid unnecessary 212718334Speter splitting. */ 212818334Speter if (! insn_references_resource_p (trial, &set, 1) 212918334Speter && ! insn_sets_resource_p (trial, &set, 1) 213018334Speter && ! insn_sets_resource_p (trial, &needed, 1) 213118334Speter#ifdef HAVE_cc0 213218334Speter /* Can't separate set of cc0 from its use. */ 213390075Sobrien && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat)) 213418334Speter#endif 213596263Sobrien && ! can_throw_internal (trial)) 213618334Speter { 213718334Speter trial = try_split (pat, trial, 1); 213818334Speter next_trial = prev_nonnote_insn (trial); 213918334Speter if (eligible_for_delay (insn, slots_filled, trial, flags)) 214018334Speter { 214118334Speter /* In this case, we are searching backward, so if we 214218334Speter find insns to put on the delay list, we want 214318334Speter to put them at the head, rather than the 214418334Speter tail, of the list. */ 214518334Speter 214618334Speter update_reg_dead_notes (trial, insn); 214750397Sobrien delay_list = gen_rtx_INSN_LIST (VOIDmode, 214850397Sobrien trial, delay_list); 214918334Speter update_block (trial, trial); 215090075Sobrien delete_related_insns (trial); 215118334Speter if (slots_to_fill == ++slots_filled) 215218334Speter break; 215318334Speter continue; 215418334Speter } 215518334Speter } 215618334Speter 215790075Sobrien mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL); 215818334Speter mark_referenced_resources (trial, &needed, 1); 215918334Speter } 216018334Speter } 216118334Speter 216218334Speter /* If all needed slots haven't been filled, we come here. */ 216318334Speter 216418334Speter /* Try to optimize case of jumping around a single insn. */ 216518334Speter#if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS) 216618334Speter if (slots_filled != slots_to_fill 216718334Speter && delay_list == 0 2168169689Skan && JUMP_P (insn) 216918334Speter && (condjump_p (insn) || condjump_in_parallel_p (insn))) 217018334Speter { 217118334Speter delay_list = optimize_skip (insn); 217218334Speter if (delay_list) 217318334Speter slots_filled += 1; 217418334Speter } 217518334Speter#endif 217618334Speter 217718334Speter /* Try to get insns from beyond the insn needing the delay slot. 217818334Speter These insns can neither set or reference resources set in insns being 217918334Speter skipped, cannot set resources in the insn being skipped, and, if this 218018334Speter is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the 218118334Speter call might not return). 218218334Speter 218318334Speter There used to be code which continued past the target label if 218418334Speter we saw all uses of the target label. This code did not work, 218518334Speter because it failed to account for some instructions which were 218618334Speter both annulled and marked as from the target. This can happen as a 218718334Speter result of optimize_skip. Since this code was redundant with 218818334Speter fill_eager_delay_slots anyways, it was just deleted. */ 218918334Speter 219018334Speter if (slots_filled != slots_to_fill 219190075Sobrien /* If this instruction could throw an exception which is 219290075Sobrien caught in the same function, then it's not safe to fill 219390075Sobrien the delay slot with an instruction from beyond this 219490075Sobrien point. For example, consider: 219590075Sobrien 219690075Sobrien int i = 2; 219790075Sobrien 219890075Sobrien try { 219990075Sobrien f(); 220090075Sobrien i = 3; 220190075Sobrien } catch (...) {} 220290075Sobrien 220390075Sobrien return i; 220490075Sobrien 220590075Sobrien Even though `i' is a local variable, we must be sure not 220690075Sobrien to put `i = 3' in the delay slot if `f' might throw an 220790075Sobrien exception. 220890075Sobrien 220990075Sobrien Presumably, we should also check to see if we could get 221090075Sobrien back to this function via `setjmp'. */ 221196263Sobrien && ! can_throw_internal (insn) 2212169689Skan && (!JUMP_P (insn) 221318334Speter || ((condjump_p (insn) || condjump_in_parallel_p (insn)) 221490075Sobrien && ! simplejump_p (insn) 221590075Sobrien && JUMP_LABEL (insn) != 0))) 221618334Speter { 221790075Sobrien /* Invariant: If insn is a JUMP_INSN, the insn's jump 221890075Sobrien label. Otherwise, zero. */ 221918334Speter rtx target = 0; 222018334Speter int maybe_never = 0; 222190075Sobrien rtx pat, trial_delay; 222218334Speter 222318334Speter CLEAR_RESOURCE (&needed); 222418334Speter CLEAR_RESOURCE (&set); 222518334Speter 2226169689Skan if (CALL_P (insn)) 222718334Speter { 222890075Sobrien mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL); 222918334Speter mark_referenced_resources (insn, &needed, 1); 223018334Speter maybe_never = 1; 223118334Speter } 223290075Sobrien else 223318334Speter { 223490075Sobrien mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL); 223518334Speter mark_referenced_resources (insn, &needed, 1); 2236169689Skan if (JUMP_P (insn)) 223718334Speter target = JUMP_LABEL (insn); 223818334Speter } 223918334Speter 224090075Sobrien if (target == 0) 224190075Sobrien for (trial = next_nonnote_insn (insn); trial; trial = next_trial) 224290075Sobrien { 224390075Sobrien next_trial = next_nonnote_insn (trial); 224418334Speter 2245169689Skan if (LABEL_P (trial) 2246169689Skan || BARRIER_P (trial)) 224790075Sobrien break; 224818334Speter 224990075Sobrien /* We must have an INSN, JUMP_INSN, or CALL_INSN. */ 225090075Sobrien pat = PATTERN (trial); 225118334Speter 225290075Sobrien /* Stand-alone USE and CLOBBER are just for flow. */ 225390075Sobrien if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 225490075Sobrien continue; 225518334Speter 225690075Sobrien /* If this already has filled delay slots, get the insn needing 225790075Sobrien the delay slots. */ 225890075Sobrien if (GET_CODE (pat) == SEQUENCE) 225990075Sobrien trial_delay = XVECEXP (pat, 0, 0); 226090075Sobrien else 226190075Sobrien trial_delay = trial; 226218334Speter 226390075Sobrien /* Stop our search when seeing an unconditional jump. */ 2264169689Skan if (JUMP_P (trial_delay)) 226590075Sobrien break; 226618334Speter 226790075Sobrien /* See if we have a resource problem before we try to 226890075Sobrien split. */ 226990075Sobrien if (GET_CODE (pat) != SEQUENCE 227090075Sobrien && ! insn_references_resource_p (trial, &set, 1) 227190075Sobrien && ! insn_sets_resource_p (trial, &set, 1) 227290075Sobrien && ! insn_sets_resource_p (trial, &needed, 1) 227318334Speter#ifdef HAVE_cc0 227490075Sobrien && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat)) 227518334Speter#endif 2276169689Skan && ! (maybe_never && may_trap_or_fault_p (pat)) 227790075Sobrien && (trial = try_split (pat, trial, 0)) 227896263Sobrien && eligible_for_delay (insn, slots_filled, trial, flags) 227996263Sobrien && ! can_throw_internal(trial)) 228090075Sobrien { 228190075Sobrien next_trial = next_nonnote_insn (trial); 228290075Sobrien delay_list = add_to_delay_list (trial, delay_list); 228318334Speter 228418334Speter#ifdef HAVE_cc0 228590075Sobrien if (reg_mentioned_p (cc0_rtx, pat)) 228690075Sobrien link_cc0_insns (trial); 228718334Speter#endif 228818334Speter 228990075Sobrien delete_related_insns (trial); 229090075Sobrien if (slots_to_fill == ++slots_filled) 229190075Sobrien break; 229290075Sobrien continue; 229390075Sobrien } 229418334Speter 229590075Sobrien mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL); 229690075Sobrien mark_referenced_resources (trial, &needed, 1); 229718334Speter 229890075Sobrien /* Ensure we don't put insns between the setting of cc and the 229990075Sobrien comparison by moving a setting of cc into an earlier delay 230090075Sobrien slot since these insns could clobber the condition code. */ 230190075Sobrien set.cc = 1; 230218334Speter 230390075Sobrien /* If this is a call or jump, we might not get here. */ 2304169689Skan if (CALL_P (trial_delay) 2305169689Skan || JUMP_P (trial_delay)) 230690075Sobrien maybe_never = 1; 230790075Sobrien } 230818334Speter 230918334Speter /* If there are slots left to fill and our search was stopped by an 231018334Speter unconditional branch, try the insn at the branch target. We can 231190075Sobrien redirect the branch if it works. 231218334Speter 231318334Speter Don't do this if the insn at the branch target is a branch. */ 231418334Speter if (slots_to_fill != slots_filled 231518334Speter && trial 2316169689Skan && JUMP_P (trial) 231718334Speter && simplejump_p (trial) 231818334Speter && (target == 0 || JUMP_LABEL (trial) == target) 231918334Speter && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0 2320169689Skan && ! (NONJUMP_INSN_P (next_trial) 232118334Speter && GET_CODE (PATTERN (next_trial)) == SEQUENCE) 2322169689Skan && !JUMP_P (next_trial) 232318334Speter && ! insn_references_resource_p (next_trial, &set, 1) 232418334Speter && ! insn_sets_resource_p (next_trial, &set, 1) 232518334Speter && ! insn_sets_resource_p (next_trial, &needed, 1) 232618334Speter#ifdef HAVE_cc0 232718334Speter && ! reg_mentioned_p (cc0_rtx, PATTERN (next_trial)) 232818334Speter#endif 2329169689Skan && ! (maybe_never && may_trap_or_fault_p (PATTERN (next_trial))) 233018334Speter && (next_trial = try_split (PATTERN (next_trial), next_trial, 0)) 233196263Sobrien && eligible_for_delay (insn, slots_filled, next_trial, flags) 233296263Sobrien && ! can_throw_internal (trial)) 233318334Speter { 2334132718Skan /* See comment in relax_delay_slots about necessity of using 2335132718Skan next_real_insn here. */ 2336132718Skan rtx new_label = next_real_insn (next_trial); 233718334Speter 233818334Speter if (new_label != 0) 233918334Speter new_label = get_label_before (new_label); 234018334Speter else 234118334Speter new_label = find_end_label (); 234218334Speter 2343169689Skan if (new_label) 2344169689Skan { 2345169689Skan delay_list 2346169689Skan = add_to_delay_list (copy_rtx (next_trial), delay_list); 2347169689Skan slots_filled++; 2348169689Skan reorg_redirect_jump (trial, new_label); 234918334Speter 2350169689Skan /* If we merged because we both jumped to the same place, 2351169689Skan redirect the original insn also. */ 2352169689Skan if (target) 2353169689Skan reorg_redirect_jump (insn, new_label); 2354169689Skan } 235518334Speter } 235618334Speter } 235718334Speter 235850397Sobrien /* If this is an unconditional jump, then try to get insns from the 235950397Sobrien target of the jump. */ 2360169689Skan if (JUMP_P (insn) 236150397Sobrien && simplejump_p (insn) 236250397Sobrien && slots_filled != slots_to_fill) 236350397Sobrien delay_list 236450397Sobrien = fill_slots_from_thread (insn, const_true_rtx, 236550397Sobrien next_active_insn (JUMP_LABEL (insn)), 236650397Sobrien NULL, 1, 1, 236750397Sobrien own_thread_p (JUMP_LABEL (insn), 236850397Sobrien JUMP_LABEL (insn), 0), 236950397Sobrien slots_to_fill, &slots_filled, 237050397Sobrien delay_list); 237150397Sobrien 237218334Speter if (delay_list) 237318334Speter unfilled_slots_base[i] 237450397Sobrien = emit_delay_sequence (insn, delay_list, slots_filled); 237518334Speter 237618334Speter if (slots_to_fill == slots_filled) 237718334Speter unfilled_slots_base[i] = 0; 237818334Speter 237918334Speter note_delay_statistics (slots_filled, 0); 238018334Speter } 238118334Speter 238218334Speter#ifdef DELAY_SLOTS_FOR_EPILOGUE 238318334Speter /* See if the epilogue needs any delay slots. Try to fill them if so. 238490075Sobrien The only thing we can do is scan backwards from the end of the 238518334Speter function. If we did this in a previous pass, it is incorrect to do it 238618334Speter again. */ 238718334Speter if (current_function_epilogue_delay_list) 238818334Speter return; 238918334Speter 239018334Speter slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE; 239118334Speter if (slots_to_fill == 0) 239218334Speter return; 239318334Speter 239418334Speter slots_filled = 0; 239518334Speter CLEAR_RESOURCE (&set); 239618334Speter 239718334Speter /* The frame pointer and stack pointer are needed at the beginning of 239818334Speter the epilogue, so instructions setting them can not be put in the 239918334Speter epilogue delay slot. However, everything else needed at function 240018334Speter end is safe, so we don't want to use end_of_function_needs here. */ 240118334Speter CLEAR_RESOURCE (&needed); 240218334Speter if (frame_pointer_needed) 240318334Speter { 240418334Speter SET_HARD_REG_BIT (needed.regs, FRAME_POINTER_REGNUM); 240518334Speter#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 240618334Speter SET_HARD_REG_BIT (needed.regs, HARD_FRAME_POINTER_REGNUM); 240718334Speter#endif 240852284Sobrien if (! EXIT_IGNORE_STACK 240952284Sobrien || current_function_sp_is_unchanging) 241018334Speter SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM); 241118334Speter } 241218334Speter else 241318334Speter SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM); 241418334Speter 241550397Sobrien#ifdef EPILOGUE_USES 241690075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 241750397Sobrien { 241850397Sobrien if (EPILOGUE_USES (i)) 241950397Sobrien SET_HARD_REG_BIT (needed.regs, i); 242050397Sobrien } 242150397Sobrien#endif 242250397Sobrien 242318334Speter for (trial = get_last_insn (); ! stop_search_p (trial, 1); 242418334Speter trial = PREV_INSN (trial)) 242518334Speter { 2426169689Skan if (NOTE_P (trial)) 242718334Speter continue; 242818334Speter pat = PATTERN (trial); 242918334Speter if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 243018334Speter continue; 243118334Speter 243218334Speter if (! insn_references_resource_p (trial, &set, 1) 243318334Speter && ! insn_sets_resource_p (trial, &needed, 1) 243418334Speter && ! insn_sets_resource_p (trial, &set, 1) 243518334Speter#ifdef HAVE_cc0 243618334Speter /* Don't want to mess with cc0 here. */ 243718334Speter && ! reg_mentioned_p (cc0_rtx, pat) 243818334Speter#endif 243996263Sobrien && ! can_throw_internal (trial)) 244018334Speter { 244118334Speter trial = try_split (pat, trial, 1); 244218334Speter if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled)) 244318334Speter { 244418334Speter /* Here as well we are searching backward, so put the 244518334Speter insns we find on the head of the list. */ 244618334Speter 244718334Speter current_function_epilogue_delay_list 244850397Sobrien = gen_rtx_INSN_LIST (VOIDmode, trial, 244950397Sobrien current_function_epilogue_delay_list); 245052284Sobrien mark_end_of_function_resources (trial, 1); 245118334Speter update_block (trial, trial); 245290075Sobrien delete_related_insns (trial); 245318334Speter 245418334Speter /* Clear deleted bit so final.c will output the insn. */ 245518334Speter INSN_DELETED_P (trial) = 0; 245618334Speter 245718334Speter if (slots_to_fill == ++slots_filled) 245818334Speter break; 245918334Speter continue; 246018334Speter } 246118334Speter } 246218334Speter 246390075Sobrien mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL); 246418334Speter mark_referenced_resources (trial, &needed, 1); 246518334Speter } 246618334Speter 246718334Speter note_delay_statistics (slots_filled, 0); 246818334Speter#endif 246918334Speter} 247018334Speter 247118334Speter/* Try to find insns to place in delay slots. 247218334Speter 247318334Speter INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION 247418334Speter or is an unconditional branch if CONDITION is const_true_rtx. 247518334Speter *PSLOTS_FILLED is updated with the number of slots that we have filled. 247618334Speter 247718334Speter THREAD is a flow-of-control, either the insns to be executed if the 247818334Speter branch is true or if the branch is false, THREAD_IF_TRUE says which. 247918334Speter 248018334Speter OPPOSITE_THREAD is the thread in the opposite direction. It is used 248118334Speter to see if any potential delay slot insns set things needed there. 248218334Speter 2483117395Skan LIKELY is nonzero if it is extremely likely that the branch will be 248418334Speter taken and THREAD_IF_TRUE is set. This is used for the branch at the 248518334Speter end of a loop back up to the top. 248618334Speter 248718334Speter OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the 248818334Speter thread. I.e., it is the fallthrough code of our jump or the target of the 248918334Speter jump when we are the only jump going there. 249018334Speter 249118334Speter If OWN_THREAD is false, it must be the "true" thread of a jump. In that 249218334Speter case, we can only take insns from the head of the thread for our delay 249318334Speter slot. We then adjust the jump to point after the insns we have taken. */ 249418334Speter 249518334Speterstatic rtx 2496132718Skanfill_slots_from_thread (rtx insn, rtx condition, rtx thread, 2497132718Skan rtx opposite_thread, int likely, int thread_if_true, 2498132718Skan int own_thread, int slots_to_fill, 2499132718Skan int *pslots_filled, rtx delay_list) 250018334Speter{ 250118334Speter rtx new_thread; 250218334Speter struct resources opposite_needed, set, needed; 250318334Speter rtx trial; 250418334Speter int lose = 0; 250518334Speter int must_annul = 0; 250618334Speter int flags; 250718334Speter 250818334Speter /* Validate our arguments. */ 2509169689Skan gcc_assert(condition != const_true_rtx || thread_if_true); 2510169689Skan gcc_assert(own_thread || thread_if_true); 251118334Speter 251218334Speter flags = get_jump_flags (insn, JUMP_LABEL (insn)); 251318334Speter 251418334Speter /* If our thread is the end of subroutine, we can't get any delay 251518334Speter insns from that. */ 251618334Speter if (thread == 0) 251790075Sobrien return delay_list; 251818334Speter 251918334Speter /* If this is an unconditional branch, nothing is needed at the 252018334Speter opposite thread. Otherwise, compute what is needed there. */ 252118334Speter if (condition == const_true_rtx) 252218334Speter CLEAR_RESOURCE (&opposite_needed); 252318334Speter else 252452284Sobrien mark_target_live_regs (get_insns (), opposite_thread, &opposite_needed); 252518334Speter 252618334Speter /* If the insn at THREAD can be split, do it here to avoid having to 252718334Speter update THREAD and NEW_THREAD if it is done in the loop below. Also 252818334Speter initialize NEW_THREAD. */ 252918334Speter 253018334Speter new_thread = thread = try_split (PATTERN (thread), thread, 0); 253118334Speter 253218334Speter /* Scan insns at THREAD. We are looking for an insn that can be removed 253318334Speter from THREAD (it neither sets nor references resources that were set 253418334Speter ahead of it and it doesn't set anything needs by the insns ahead of 253518334Speter it) and that either can be placed in an annulling insn or aren't 253618334Speter needed at OPPOSITE_THREAD. */ 253718334Speter 253818334Speter CLEAR_RESOURCE (&needed); 253918334Speter CLEAR_RESOURCE (&set); 254018334Speter 254118334Speter /* If we do not own this thread, we must stop as soon as we find 254218334Speter something that we can't put in a delay slot, since all we can do 254318334Speter is branch into THREAD at a later point. Therefore, labels stop 254418334Speter the search if this is not the `true' thread. */ 254518334Speter 254618334Speter for (trial = thread; 254718334Speter ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread); 254818334Speter trial = next_nonnote_insn (trial)) 254918334Speter { 255018334Speter rtx pat, old_trial; 255118334Speter 255218334Speter /* If we have passed a label, we no longer own this thread. */ 2553169689Skan if (LABEL_P (trial)) 255418334Speter { 255518334Speter own_thread = 0; 255618334Speter continue; 255718334Speter } 255818334Speter 255918334Speter pat = PATTERN (trial); 256018334Speter if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 256118334Speter continue; 256218334Speter 256318334Speter /* If TRIAL conflicts with the insns ahead of it, we lose. Also, 256418334Speter don't separate or copy insns that set and use CC0. */ 256518334Speter if (! insn_references_resource_p (trial, &set, 1) 256618334Speter && ! insn_sets_resource_p (trial, &set, 1) 256718334Speter && ! insn_sets_resource_p (trial, &needed, 1) 256818334Speter#ifdef HAVE_cc0 256918334Speter && ! (reg_mentioned_p (cc0_rtx, pat) 257018334Speter && (! own_thread || ! sets_cc0_p (pat))) 257118334Speter#endif 257296263Sobrien && ! can_throw_internal (trial)) 257318334Speter { 257418334Speter rtx prior_insn; 257518334Speter 257618334Speter /* If TRIAL is redundant with some insn before INSN, we don't 257718334Speter actually need to add it to the delay list; we can merely pretend 257818334Speter we did. */ 257950397Sobrien if ((prior_insn = redundant_insn (trial, insn, delay_list))) 258018334Speter { 258150397Sobrien fix_reg_dead_note (prior_insn, insn); 258218334Speter if (own_thread) 258318334Speter { 258418334Speter update_block (trial, thread); 258518334Speter if (trial == thread) 258618334Speter { 258718334Speter thread = next_active_insn (thread); 258818334Speter if (new_thread == trial) 258918334Speter new_thread = thread; 259018334Speter } 259118334Speter 259290075Sobrien delete_related_insns (trial); 259318334Speter } 259418334Speter else 259518334Speter { 259618334Speter update_reg_unused_notes (prior_insn, trial); 259718334Speter new_thread = next_active_insn (trial); 259818334Speter } 259918334Speter 260018334Speter continue; 260118334Speter } 260218334Speter 260318334Speter /* There are two ways we can win: If TRIAL doesn't set anything 260418334Speter needed at the opposite thread and can't trap, or if it can 260518334Speter go into an annulled delay slot. */ 260652284Sobrien if (!must_annul 260752284Sobrien && (condition == const_true_rtx 260852284Sobrien || (! insn_sets_resource_p (trial, &opposite_needed, 1) 2609169689Skan && ! may_trap_or_fault_p (pat)))) 261018334Speter { 261118334Speter old_trial = trial; 261218334Speter trial = try_split (pat, trial, 0); 261318334Speter if (new_thread == old_trial) 261418334Speter new_thread = trial; 261518334Speter if (thread == old_trial) 261618334Speter thread = trial; 261718334Speter pat = PATTERN (trial); 261818334Speter if (eligible_for_delay (insn, *pslots_filled, trial, flags)) 261918334Speter goto winner; 262018334Speter } 262118334Speter else if (0 262218334Speter#ifdef ANNUL_IFTRUE_SLOTS 262318334Speter || ! thread_if_true 262418334Speter#endif 262518334Speter#ifdef ANNUL_IFFALSE_SLOTS 262618334Speter || thread_if_true 262718334Speter#endif 262818334Speter ) 262918334Speter { 263018334Speter old_trial = trial; 263118334Speter trial = try_split (pat, trial, 0); 263218334Speter if (new_thread == old_trial) 263318334Speter new_thread = trial; 263418334Speter if (thread == old_trial) 263518334Speter thread = trial; 263618334Speter pat = PATTERN (trial); 263752284Sobrien if ((must_annul || delay_list == NULL) && (thread_if_true 263852284Sobrien ? check_annul_list_true_false (0, delay_list) 263952284Sobrien && eligible_for_annul_false (insn, *pslots_filled, trial, flags) 264052284Sobrien : check_annul_list_true_false (1, delay_list) 264152284Sobrien && eligible_for_annul_true (insn, *pslots_filled, trial, flags))) 264218334Speter { 264318334Speter rtx temp; 264418334Speter 264518334Speter must_annul = 1; 264618334Speter winner: 264718334Speter 264818334Speter#ifdef HAVE_cc0 264918334Speter if (reg_mentioned_p (cc0_rtx, pat)) 265018334Speter link_cc0_insns (trial); 265118334Speter#endif 265218334Speter 265318334Speter /* If we own this thread, delete the insn. If this is the 265418334Speter destination of a branch, show that a basic block status 265518334Speter may have been updated. In any case, mark the new 265618334Speter starting point of this thread. */ 265718334Speter if (own_thread) 265818334Speter { 265990075Sobrien rtx note; 266090075Sobrien 266118334Speter update_block (trial, thread); 266250397Sobrien if (trial == thread) 266350397Sobrien { 266450397Sobrien thread = next_active_insn (thread); 266550397Sobrien if (new_thread == trial) 266650397Sobrien new_thread = thread; 266750397Sobrien } 266890075Sobrien 266990075Sobrien /* We are moving this insn, not deleting it. We must 267090075Sobrien temporarily increment the use count on any referenced 267190075Sobrien label lest it be deleted by delete_related_insns. */ 267290075Sobrien note = find_reg_note (trial, REG_LABEL, 0); 267396263Sobrien /* REG_LABEL could be NOTE_INSN_DELETED_LABEL too. */ 2674169689Skan if (note && LABEL_P (XEXP (note, 0))) 267590075Sobrien LABEL_NUSES (XEXP (note, 0))++; 267690075Sobrien 267790075Sobrien delete_related_insns (trial); 267890075Sobrien 2679169689Skan if (note && LABEL_P (XEXP (note, 0))) 268090075Sobrien LABEL_NUSES (XEXP (note, 0))--; 268118334Speter } 268218334Speter else 268318334Speter new_thread = next_active_insn (trial); 268418334Speter 268518334Speter temp = own_thread ? trial : copy_rtx (trial); 268618334Speter if (thread_if_true) 268718334Speter INSN_FROM_TARGET_P (temp) = 1; 268818334Speter 268918334Speter delay_list = add_to_delay_list (temp, delay_list); 269018334Speter 269118334Speter if (slots_to_fill == ++(*pslots_filled)) 269218334Speter { 269318334Speter /* Even though we have filled all the slots, we 269418334Speter may be branching to a location that has a 269518334Speter redundant insn. Skip any if so. */ 269618334Speter while (new_thread && ! own_thread 269718334Speter && ! insn_sets_resource_p (new_thread, &set, 1) 269818334Speter && ! insn_sets_resource_p (new_thread, &needed, 1) 269918334Speter && ! insn_references_resource_p (new_thread, 270018334Speter &set, 1) 270150397Sobrien && (prior_insn 270250397Sobrien = redundant_insn (new_thread, insn, 270350397Sobrien delay_list))) 270450397Sobrien { 270550397Sobrien /* We know we do not own the thread, so no need 270650397Sobrien to call update_block and delete_insn. */ 270750397Sobrien fix_reg_dead_note (prior_insn, insn); 270850397Sobrien update_reg_unused_notes (prior_insn, new_thread); 270950397Sobrien new_thread = next_active_insn (new_thread); 271050397Sobrien } 271118334Speter break; 271218334Speter } 271318334Speter 271418334Speter continue; 271518334Speter } 271618334Speter } 271718334Speter } 271818334Speter 271918334Speter /* This insn can't go into a delay slot. */ 272018334Speter lose = 1; 272190075Sobrien mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL); 272218334Speter mark_referenced_resources (trial, &needed, 1); 272318334Speter 272418334Speter /* Ensure we don't put insns between the setting of cc and the comparison 272518334Speter by moving a setting of cc into an earlier delay slot since these insns 272618334Speter could clobber the condition code. */ 272718334Speter set.cc = 1; 272818334Speter 272918334Speter /* If this insn is a register-register copy and the next insn has 273018334Speter a use of our destination, change it to use our source. That way, 273118334Speter it will become a candidate for our delay slot the next time 273218334Speter through this loop. This case occurs commonly in loops that 273318334Speter scan a list. 273418334Speter 273518334Speter We could check for more complex cases than those tested below, 273618334Speter but it doesn't seem worth it. It might also be a good idea to try 273718334Speter to swap the two insns. That might do better. 273818334Speter 273918334Speter We can't do this if the next insn modifies our destination, because 274018334Speter that would make the replacement into the insn invalid. We also can't 274118334Speter do this if it modifies our source, because it might be an earlyclobber 274218334Speter operand. This latter test also prevents updating the contents of 2743132718Skan a PRE_INC. We also can't do this if there's overlap of source and 2744132718Skan destination. Overlap may happen for larger-than-register-size modes. */ 274518334Speter 2746169689Skan if (NONJUMP_INSN_P (trial) && GET_CODE (pat) == SET 2747169689Skan && REG_P (SET_SRC (pat)) 2748169689Skan && REG_P (SET_DEST (pat)) 2749132718Skan && !reg_overlap_mentioned_p (SET_DEST (pat), SET_SRC (pat))) 275018334Speter { 275118334Speter rtx next = next_nonnote_insn (trial); 275218334Speter 2753169689Skan if (next && NONJUMP_INSN_P (next) 275418334Speter && GET_CODE (PATTERN (next)) != USE 275518334Speter && ! reg_set_p (SET_DEST (pat), next) 275618334Speter && ! reg_set_p (SET_SRC (pat), next) 275790075Sobrien && reg_referenced_p (SET_DEST (pat), PATTERN (next)) 275890075Sobrien && ! modified_in_p (SET_DEST (pat), next)) 275918334Speter validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next); 276018334Speter } 276118334Speter } 276218334Speter 276318334Speter /* If we stopped on a branch insn that has delay slots, see if we can 276418334Speter steal some of the insns in those slots. */ 2765169689Skan if (trial && NONJUMP_INSN_P (trial) 276618334Speter && GET_CODE (PATTERN (trial)) == SEQUENCE 2767169689Skan && JUMP_P (XVECEXP (PATTERN (trial), 0, 0))) 276818334Speter { 276918334Speter /* If this is the `true' thread, we will want to follow the jump, 277018334Speter so we can only do this if we have taken everything up to here. */ 277152284Sobrien if (thread_if_true && trial == new_thread) 277290075Sobrien { 277390075Sobrien delay_list 277490075Sobrien = steal_delay_list_from_target (insn, condition, PATTERN (trial), 277590075Sobrien delay_list, &set, &needed, 277690075Sobrien &opposite_needed, slots_to_fill, 277790075Sobrien pslots_filled, &must_annul, 277890075Sobrien &new_thread); 277990075Sobrien /* If we owned the thread and are told that it branched 278090075Sobrien elsewhere, make sure we own the thread at the new location. */ 278190075Sobrien if (own_thread && trial != new_thread) 278290075Sobrien own_thread = own_thread_p (new_thread, new_thread, 0); 278390075Sobrien } 278418334Speter else if (! thread_if_true) 278518334Speter delay_list 278618334Speter = steal_delay_list_from_fallthrough (insn, condition, 278718334Speter PATTERN (trial), 278818334Speter delay_list, &set, &needed, 278918334Speter &opposite_needed, slots_to_fill, 279018334Speter pslots_filled, &must_annul); 279118334Speter } 279218334Speter 279318334Speter /* If we haven't found anything for this delay slot and it is very 279418334Speter likely that the branch will be taken, see if the insn at our target 279518334Speter increments or decrements a register with an increment that does not 279618334Speter depend on the destination register. If so, try to place the opposite 279718334Speter arithmetic insn after the jump insn and put the arithmetic insn in the 279818334Speter delay slot. If we can't do this, return. */ 279950397Sobrien if (delay_list == 0 && likely && new_thread 2800169689Skan && NONJUMP_INSN_P (new_thread) 280150397Sobrien && GET_CODE (PATTERN (new_thread)) != ASM_INPUT 280250397Sobrien && asm_noperands (PATTERN (new_thread)) < 0) 280318334Speter { 280418334Speter rtx pat = PATTERN (new_thread); 280518334Speter rtx dest; 280618334Speter rtx src; 280718334Speter 280818334Speter trial = new_thread; 280918334Speter pat = PATTERN (trial); 281018334Speter 2811169689Skan if (!NONJUMP_INSN_P (trial) 281296263Sobrien || GET_CODE (pat) != SET 281396263Sobrien || ! eligible_for_delay (insn, 0, trial, flags) 281496263Sobrien || can_throw_internal (trial)) 281518334Speter return 0; 281618334Speter 281718334Speter dest = SET_DEST (pat), src = SET_SRC (pat); 281818334Speter if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS) 281918334Speter && rtx_equal_p (XEXP (src, 0), dest) 2820169689Skan && (!FLOAT_MODE_P (GET_MODE (src)) 2821169689Skan || flag_unsafe_math_optimizations) 282290075Sobrien && ! reg_overlap_mentioned_p (dest, XEXP (src, 1)) 282390075Sobrien && ! side_effects_p (pat)) 282418334Speter { 282518334Speter rtx other = XEXP (src, 1); 282618334Speter rtx new_arith; 282718334Speter rtx ninsn; 282818334Speter 282918334Speter /* If this is a constant adjustment, use the same code with 283018334Speter the negated constant. Otherwise, reverse the sense of the 283118334Speter arithmetic. */ 283218334Speter if (GET_CODE (other) == CONST_INT) 283350397Sobrien new_arith = gen_rtx_fmt_ee (GET_CODE (src), GET_MODE (src), dest, 283450397Sobrien negate_rtx (GET_MODE (src), other)); 283518334Speter else 283650397Sobrien new_arith = gen_rtx_fmt_ee (GET_CODE (src) == PLUS ? MINUS : PLUS, 283750397Sobrien GET_MODE (src), dest, other); 283818334Speter 283950397Sobrien ninsn = emit_insn_after (gen_rtx_SET (VOIDmode, dest, new_arith), 284018334Speter insn); 284118334Speter 284218334Speter if (recog_memoized (ninsn) < 0 284352284Sobrien || (extract_insn (ninsn), ! constrain_operands (1))) 284418334Speter { 284590075Sobrien delete_related_insns (ninsn); 284618334Speter return 0; 284718334Speter } 284818334Speter 284918334Speter if (own_thread) 285018334Speter { 285118334Speter update_block (trial, thread); 285250397Sobrien if (trial == thread) 285350397Sobrien { 285450397Sobrien thread = next_active_insn (thread); 285550397Sobrien if (new_thread == trial) 285650397Sobrien new_thread = thread; 285750397Sobrien } 285890075Sobrien delete_related_insns (trial); 285918334Speter } 286018334Speter else 286118334Speter new_thread = next_active_insn (trial); 286218334Speter 286318334Speter ninsn = own_thread ? trial : copy_rtx (trial); 286418334Speter if (thread_if_true) 286518334Speter INSN_FROM_TARGET_P (ninsn) = 1; 286618334Speter 286718334Speter delay_list = add_to_delay_list (ninsn, NULL_RTX); 286818334Speter (*pslots_filled)++; 286918334Speter } 287018334Speter } 287118334Speter 287218334Speter if (delay_list && must_annul) 287318334Speter INSN_ANNULLED_BRANCH_P (insn) = 1; 287418334Speter 287518334Speter /* If we are to branch into the middle of this thread, find an appropriate 287618334Speter label or make a new one if none, and redirect INSN to it. If we hit the 287718334Speter end of the function, use the end-of-function label. */ 287818334Speter if (new_thread != thread) 287918334Speter { 288018334Speter rtx label; 288118334Speter 2882169689Skan gcc_assert (thread_if_true); 288318334Speter 2884169689Skan if (new_thread && JUMP_P (new_thread) 288518334Speter && (simplejump_p (new_thread) 288618334Speter || GET_CODE (PATTERN (new_thread)) == RETURN) 288718334Speter && redirect_with_delay_list_safe_p (insn, 288818334Speter JUMP_LABEL (new_thread), 288918334Speter delay_list)) 289018334Speter new_thread = follow_jumps (JUMP_LABEL (new_thread)); 289118334Speter 289218334Speter if (new_thread == 0) 289318334Speter label = find_end_label (); 2894169689Skan else if (LABEL_P (new_thread)) 289518334Speter label = new_thread; 289618334Speter else 289718334Speter label = get_label_before (new_thread); 289818334Speter 2899169689Skan if (label) 2900169689Skan reorg_redirect_jump (insn, label); 290118334Speter } 290218334Speter 290318334Speter return delay_list; 290418334Speter} 290518334Speter 290618334Speter/* Make another attempt to find insns to place in delay slots. 290718334Speter 290818334Speter We previously looked for insns located in front of the delay insn 290918334Speter and, for non-jump delay insns, located behind the delay insn. 291018334Speter 291118334Speter Here only try to schedule jump insns and try to move insns from either 291218334Speter the target or the following insns into the delay slot. If annulling is 291318334Speter supported, we will be likely to do this. Otherwise, we can do this only 291418334Speter if safe. */ 291518334Speter 291618334Speterstatic void 2917132718Skanfill_eager_delay_slots (void) 291818334Speter{ 291990075Sobrien rtx insn; 292090075Sobrien int i; 292118334Speter int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base; 292218334Speter 292318334Speter for (i = 0; i < num_unfilled_slots; i++) 292418334Speter { 292518334Speter rtx condition; 292618334Speter rtx target_label, insn_at_target, fallthrough_insn; 292718334Speter rtx delay_list = 0; 292818334Speter int own_target; 292918334Speter int own_fallthrough; 293018334Speter int prediction, slots_to_fill, slots_filled; 293118334Speter 293218334Speter insn = unfilled_slots_base[i]; 293318334Speter if (insn == 0 293418334Speter || INSN_DELETED_P (insn) 2935169689Skan || !JUMP_P (insn) 293618334Speter || ! (condjump_p (insn) || condjump_in_parallel_p (insn))) 293718334Speter continue; 293818334Speter 293918334Speter slots_to_fill = num_delay_slots (insn); 294050397Sobrien /* Some machine description have defined instructions to have 294150397Sobrien delay slots only in certain circumstances which may depend on 294250397Sobrien nearby insns (which change due to reorg's actions). 294350397Sobrien 2944132718Skan For example, the PA port normally has delay slots for unconditional 294550397Sobrien jumps. 294650397Sobrien 294750397Sobrien However, the PA port claims such jumps do not have a delay slot 294850397Sobrien if they are immediate successors of certain CALL_INSNs. This 294950397Sobrien allows the port to favor filling the delay slot of the call with 295050397Sobrien the unconditional jump. */ 295118334Speter if (slots_to_fill == 0) 295290075Sobrien continue; 295318334Speter 295418334Speter slots_filled = 0; 295518334Speter target_label = JUMP_LABEL (insn); 295618334Speter condition = get_branch_condition (insn, target_label); 295718334Speter 295818334Speter if (condition == 0) 295918334Speter continue; 296018334Speter 296118334Speter /* Get the next active fallthrough and target insns and see if we own 296218334Speter them. Then see whether the branch is likely true. We don't need 296318334Speter to do a lot of this for unconditional branches. */ 296418334Speter 296518334Speter insn_at_target = next_active_insn (target_label); 296618334Speter own_target = own_thread_p (target_label, target_label, 0); 296718334Speter 296818334Speter if (condition == const_true_rtx) 296918334Speter { 297018334Speter own_fallthrough = 0; 297118334Speter fallthrough_insn = 0; 297218334Speter prediction = 2; 297318334Speter } 297418334Speter else 297518334Speter { 297618334Speter fallthrough_insn = next_active_insn (insn); 297718334Speter own_fallthrough = own_thread_p (NEXT_INSN (insn), NULL_RTX, 1); 297818334Speter prediction = mostly_true_jump (insn, condition); 297918334Speter } 298018334Speter 298118334Speter /* If this insn is expected to branch, first try to get insns from our 298290075Sobrien target, then our fallthrough insns. If it is not expected to branch, 298318334Speter try the other order. */ 298418334Speter 298518334Speter if (prediction > 0) 298618334Speter { 298718334Speter delay_list 298818334Speter = fill_slots_from_thread (insn, condition, insn_at_target, 298918334Speter fallthrough_insn, prediction == 2, 1, 299050397Sobrien own_target, 299150397Sobrien slots_to_fill, &slots_filled, delay_list); 299218334Speter 299318334Speter if (delay_list == 0 && own_fallthrough) 299418334Speter { 299518334Speter /* Even though we didn't find anything for delay slots, 299618334Speter we might have found a redundant insn which we deleted 299718334Speter from the thread that was filled. So we have to recompute 299818334Speter the next insn at the target. */ 299918334Speter target_label = JUMP_LABEL (insn); 300018334Speter insn_at_target = next_active_insn (target_label); 300118334Speter 300218334Speter delay_list 300318334Speter = fill_slots_from_thread (insn, condition, fallthrough_insn, 300418334Speter insn_at_target, 0, 0, 300550397Sobrien own_fallthrough, 300650397Sobrien slots_to_fill, &slots_filled, 300750397Sobrien delay_list); 300818334Speter } 300918334Speter } 301018334Speter else 301118334Speter { 301218334Speter if (own_fallthrough) 301318334Speter delay_list 301418334Speter = fill_slots_from_thread (insn, condition, fallthrough_insn, 301518334Speter insn_at_target, 0, 0, 301650397Sobrien own_fallthrough, 301750397Sobrien slots_to_fill, &slots_filled, 301850397Sobrien delay_list); 301918334Speter 302018334Speter if (delay_list == 0) 302118334Speter delay_list 302218334Speter = fill_slots_from_thread (insn, condition, insn_at_target, 302318334Speter next_active_insn (insn), 0, 1, 302450397Sobrien own_target, 302550397Sobrien slots_to_fill, &slots_filled, 302650397Sobrien delay_list); 302718334Speter } 302818334Speter 302918334Speter if (delay_list) 303018334Speter unfilled_slots_base[i] 303150397Sobrien = emit_delay_sequence (insn, delay_list, slots_filled); 303218334Speter 303318334Speter if (slots_to_fill == slots_filled) 303418334Speter unfilled_slots_base[i] = 0; 303518334Speter 303618334Speter note_delay_statistics (slots_filled, 1); 303718334Speter } 303818334Speter} 303918334Speter 304018334Speter/* Once we have tried two ways to fill a delay slot, make a pass over the 304118334Speter code to try to improve the results and to do such things as more jump 304218334Speter threading. */ 304318334Speter 304418334Speterstatic void 3045132718Skanrelax_delay_slots (rtx first) 304618334Speter{ 304790075Sobrien rtx insn, next, pat; 304890075Sobrien rtx trial, delay_insn, target_label; 304918334Speter 305018334Speter /* Look at every JUMP_INSN and see if we can improve it. */ 305118334Speter for (insn = first; insn; insn = next) 305218334Speter { 305318334Speter rtx other; 305418334Speter 305518334Speter next = next_active_insn (insn); 305618334Speter 305718334Speter /* If this is a jump insn, see if it now jumps to a jump, jumps to 305818334Speter the next insn, or jumps to a label that is not the last of a 305918334Speter group of consecutive labels. */ 3060169689Skan if (JUMP_P (insn) 306118334Speter && (condjump_p (insn) || condjump_in_parallel_p (insn)) 306218334Speter && (target_label = JUMP_LABEL (insn)) != 0) 306318334Speter { 3064169689Skan target_label = skip_consecutive_labels (follow_jumps (target_label)); 306518334Speter if (target_label == 0) 306618334Speter target_label = find_end_label (); 306718334Speter 3068169689Skan if (target_label && next_active_insn (target_label) == next 306918334Speter && ! condjump_in_parallel_p (insn)) 307018334Speter { 307118334Speter delete_jump (insn); 307218334Speter continue; 307318334Speter } 307418334Speter 3075169689Skan if (target_label && target_label != JUMP_LABEL (insn)) 307618334Speter reorg_redirect_jump (insn, target_label); 307718334Speter 3078169689Skan /* See if this jump conditionally branches around an unconditional 3079169689Skan jump. If so, invert this jump and point it to the target of the 308018334Speter second jump. */ 3081169689Skan if (next && JUMP_P (next) 3082169689Skan && any_condjump_p (insn) 308318334Speter && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN) 3084169689Skan && target_label 308518334Speter && next_active_insn (target_label) == next_active_insn (next) 308618334Speter && no_labels_between_p (insn, next)) 308718334Speter { 308818334Speter rtx label = JUMP_LABEL (next); 308918334Speter 309018334Speter /* Be careful how we do this to avoid deleting code or 309118334Speter labels that are momentarily dead. See similar optimization 309218334Speter in jump.c. 309318334Speter 309418334Speter We also need to ensure we properly handle the case when 309518334Speter invert_jump fails. */ 309618334Speter 309718334Speter ++LABEL_NUSES (target_label); 309818334Speter if (label) 309918334Speter ++LABEL_NUSES (label); 310018334Speter 310190075Sobrien if (invert_jump (insn, label, 1)) 310218334Speter { 310390075Sobrien delete_related_insns (next); 310418334Speter next = insn; 310518334Speter } 310618334Speter 310718334Speter if (label) 310818334Speter --LABEL_NUSES (label); 310918334Speter 311018334Speter if (--LABEL_NUSES (target_label) == 0) 311190075Sobrien delete_related_insns (target_label); 311218334Speter 311318334Speter continue; 311418334Speter } 311518334Speter } 311690075Sobrien 311718334Speter /* If this is an unconditional jump and the previous insn is a 311818334Speter conditional jump, try reversing the condition of the previous 311918334Speter insn and swapping our targets. The next pass might be able to 312018334Speter fill the slots. 312118334Speter 312218334Speter Don't do this if we expect the conditional branch to be true, because 312318334Speter we would then be making the more common case longer. */ 312418334Speter 3125169689Skan if (JUMP_P (insn) 312618334Speter && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN) 312718334Speter && (other = prev_active_insn (insn)) != 0 3128169689Skan && any_condjump_p (other) 312918334Speter && no_labels_between_p (other, insn) 313052284Sobrien && 0 > mostly_true_jump (other, 313118334Speter get_branch_condition (other, 313218334Speter JUMP_LABEL (other)))) 313318334Speter { 313418334Speter rtx other_target = JUMP_LABEL (other); 313518334Speter target_label = JUMP_LABEL (insn); 313618334Speter 313790075Sobrien if (invert_jump (other, target_label, 0)) 313818334Speter reorg_redirect_jump (insn, other_target); 313918334Speter } 314018334Speter 314118334Speter /* Now look only at cases where we have filled a delay slot. */ 3142169689Skan if (!NONJUMP_INSN_P (insn) 314318334Speter || GET_CODE (PATTERN (insn)) != SEQUENCE) 314418334Speter continue; 314518334Speter 314618334Speter pat = PATTERN (insn); 314718334Speter delay_insn = XVECEXP (pat, 0, 0); 314818334Speter 314918334Speter /* See if the first insn in the delay slot is redundant with some 315018334Speter previous insn. Remove it from the delay slot if so; then set up 315118334Speter to reprocess this insn. */ 315218334Speter if (redundant_insn (XVECEXP (pat, 0, 1), delay_insn, 0)) 315318334Speter { 315418334Speter delete_from_delay_slot (XVECEXP (pat, 0, 1)); 315518334Speter next = prev_active_insn (next); 315618334Speter continue; 315718334Speter } 315818334Speter 315952284Sobrien /* See if we have a RETURN insn with a filled delay slot followed 316052284Sobrien by a RETURN insn with an unfilled a delay slot. If so, we can delete 3161169689Skan the first RETURN (but not its delay insn). This gives the same 316252284Sobrien effect in fewer instructions. 316352284Sobrien 316452284Sobrien Only do so if optimizing for size since this results in slower, but 316552284Sobrien smaller code. */ 316652284Sobrien if (optimize_size 316752284Sobrien && GET_CODE (PATTERN (delay_insn)) == RETURN 316852284Sobrien && next 3169169689Skan && JUMP_P (next) 317052284Sobrien && GET_CODE (PATTERN (next)) == RETURN) 317152284Sobrien { 3172117395Skan rtx after; 317352284Sobrien int i; 317452284Sobrien 317552284Sobrien /* Delete the RETURN and just execute the delay list insns. 317652284Sobrien 317752284Sobrien We do this by deleting the INSN containing the SEQUENCE, then 317852284Sobrien re-emitting the insns separately, and then deleting the RETURN. 317952284Sobrien This allows the count of the jump target to be properly 318052284Sobrien decremented. */ 318152284Sobrien 318252284Sobrien /* Clear the from target bit, since these insns are no longer 318352284Sobrien in delay slots. */ 318452284Sobrien for (i = 0; i < XVECLEN (pat, 0); i++) 318552284Sobrien INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0; 318652284Sobrien 318752284Sobrien trial = PREV_INSN (insn); 318890075Sobrien delete_related_insns (insn); 3189169689Skan gcc_assert (GET_CODE (pat) == SEQUENCE); 3190117395Skan after = trial; 3191117395Skan for (i = 0; i < XVECLEN (pat, 0); i++) 3192117395Skan { 3193117395Skan rtx this_insn = XVECEXP (pat, 0, i); 3194117395Skan add_insn_after (this_insn, after); 3195117395Skan after = this_insn; 3196117395Skan } 319752284Sobrien delete_scheduled_jump (delay_insn); 319852284Sobrien continue; 319952284Sobrien } 320052284Sobrien 320118334Speter /* Now look only at the cases where we have a filled JUMP_INSN. */ 3202169689Skan if (!JUMP_P (XVECEXP (PATTERN (insn), 0, 0)) 320318334Speter || ! (condjump_p (XVECEXP (PATTERN (insn), 0, 0)) 320418334Speter || condjump_in_parallel_p (XVECEXP (PATTERN (insn), 0, 0)))) 320518334Speter continue; 320618334Speter 320718334Speter target_label = JUMP_LABEL (delay_insn); 320818334Speter 320918334Speter if (target_label) 321018334Speter { 321118334Speter /* If this jump goes to another unconditional jump, thread it, but 321218334Speter don't convert a jump into a RETURN here. */ 3213169689Skan trial = skip_consecutive_labels (follow_jumps (target_label)); 3214169689Skan if (trial == 0) 321518334Speter trial = find_end_label (); 321618334Speter 3217169689Skan if (trial && trial != target_label 321818334Speter && redirect_with_delay_slots_safe_p (delay_insn, trial, insn)) 321918334Speter { 322018334Speter reorg_redirect_jump (delay_insn, trial); 322118334Speter target_label = trial; 322218334Speter } 322318334Speter 322418334Speter /* If the first insn at TARGET_LABEL is redundant with a previous 322518334Speter insn, redirect the jump to the following insn process again. */ 322618334Speter trial = next_active_insn (target_label); 322718334Speter if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE 322896263Sobrien && redundant_insn (trial, insn, 0) 322996263Sobrien && ! can_throw_internal (trial)) 323018334Speter { 323150397Sobrien /* Figure out where to emit the special USE insn so we don't 323250397Sobrien later incorrectly compute register live/death info. */ 3233169689Skan rtx tmp = next_active_insn (trial); 323450397Sobrien if (tmp == 0) 323550397Sobrien tmp = find_end_label (); 323650397Sobrien 3237169689Skan if (tmp) 3238169689Skan { 3239169689Skan /* Insert the special USE insn and update dataflow info. */ 3240169689Skan update_block (trial, tmp); 324150397Sobrien 3242169689Skan /* Now emit a label before the special USE insn, and 3243169689Skan redirect our jump to the new label. */ 3244169689Skan target_label = get_label_before (PREV_INSN (tmp)); 3245169689Skan reorg_redirect_jump (delay_insn, target_label); 3246169689Skan next = insn; 3247169689Skan continue; 3248169689Skan } 324918334Speter } 325018334Speter 325118334Speter /* Similarly, if it is an unconditional jump with one insn in its 325218334Speter delay list and that insn is redundant, thread the jump. */ 325318334Speter if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE 325418334Speter && XVECLEN (PATTERN (trial), 0) == 2 3255169689Skan && JUMP_P (XVECEXP (PATTERN (trial), 0, 0)) 325618334Speter && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0)) 325718334Speter || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN) 325818334Speter && redundant_insn (XVECEXP (PATTERN (trial), 0, 1), insn, 0)) 325918334Speter { 326018334Speter target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0)); 326118334Speter if (target_label == 0) 326218334Speter target_label = find_end_label (); 326318334Speter 3264169689Skan if (target_label 3265169689Skan && redirect_with_delay_slots_safe_p (delay_insn, target_label, 3266169689Skan insn)) 326718334Speter { 326818334Speter reorg_redirect_jump (delay_insn, target_label); 326918334Speter next = insn; 327018334Speter continue; 327118334Speter } 327218334Speter } 327318334Speter } 327418334Speter 327518334Speter if (! INSN_ANNULLED_BRANCH_P (delay_insn) 327618334Speter && prev_active_insn (target_label) == insn 327718334Speter && ! condjump_in_parallel_p (delay_insn) 327818334Speter#ifdef HAVE_cc0 327918334Speter /* If the last insn in the delay slot sets CC0 for some insn, 328018334Speter various code assumes that it is in a delay slot. We could 328118334Speter put it back where it belonged and delete the register notes, 328218334Speter but it doesn't seem worthwhile in this uncommon case. */ 328318334Speter && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1), 328418334Speter REG_CC_USER, NULL_RTX) 328518334Speter#endif 328618334Speter ) 328718334Speter { 3288117395Skan rtx after; 328918334Speter int i; 329018334Speter 329118334Speter /* All this insn does is execute its delay list and jump to the 329218334Speter following insn. So delete the jump and just execute the delay 329318334Speter list insns. 329418334Speter 329518334Speter We do this by deleting the INSN containing the SEQUENCE, then 329618334Speter re-emitting the insns separately, and then deleting the jump. 329718334Speter This allows the count of the jump target to be properly 329818334Speter decremented. */ 329918334Speter 330018334Speter /* Clear the from target bit, since these insns are no longer 330118334Speter in delay slots. */ 330218334Speter for (i = 0; i < XVECLEN (pat, 0); i++) 330318334Speter INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0; 330418334Speter 330518334Speter trial = PREV_INSN (insn); 330690075Sobrien delete_related_insns (insn); 3307169689Skan gcc_assert (GET_CODE (pat) == SEQUENCE); 3308117395Skan after = trial; 3309117395Skan for (i = 0; i < XVECLEN (pat, 0); i++) 3310117395Skan { 3311117395Skan rtx this_insn = XVECEXP (pat, 0, i); 3312117395Skan add_insn_after (this_insn, after); 3313117395Skan after = this_insn; 3314117395Skan } 331518334Speter delete_scheduled_jump (delay_insn); 331618334Speter continue; 331718334Speter } 331818334Speter 331918334Speter /* See if this is an unconditional jump around a single insn which is 332018334Speter identical to the one in its delay slot. In this case, we can just 332118334Speter delete the branch and the insn in its delay slot. */ 3322169689Skan if (next && NONJUMP_INSN_P (next) 332318334Speter && prev_label (next_active_insn (next)) == target_label 332418334Speter && simplejump_p (insn) 332518334Speter && XVECLEN (pat, 0) == 2 332618334Speter && rtx_equal_p (PATTERN (next), PATTERN (XVECEXP (pat, 0, 1)))) 332718334Speter { 332890075Sobrien delete_related_insns (insn); 332918334Speter continue; 333018334Speter } 333118334Speter 3332169689Skan /* See if this jump (with its delay slots) conditionally branches 3333169689Skan around an unconditional jump (without delay slots). If so, invert 3334169689Skan this jump and point it to the target of the second jump. We cannot 3335169689Skan do this for annulled jumps, though. Again, don't convert a jump to 3336169689Skan a RETURN here. */ 333718334Speter if (! INSN_ANNULLED_BRANCH_P (delay_insn) 3338169689Skan && any_condjump_p (delay_insn) 3339169689Skan && next && JUMP_P (next) 334018334Speter && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN) 334118334Speter && next_active_insn (target_label) == next_active_insn (next) 334218334Speter && no_labels_between_p (insn, next)) 334318334Speter { 334418334Speter rtx label = JUMP_LABEL (next); 334518334Speter rtx old_label = JUMP_LABEL (delay_insn); 334618334Speter 334718334Speter if (label == 0) 334818334Speter label = find_end_label (); 334918334Speter 335090075Sobrien /* find_end_label can generate a new label. Check this first. */ 3351169689Skan if (label 3352169689Skan && no_labels_between_p (insn, next) 335390075Sobrien && redirect_with_delay_slots_safe_p (delay_insn, label, insn)) 335418334Speter { 335518334Speter /* Be careful how we do this to avoid deleting code or labels 335618334Speter that are momentarily dead. See similar optimization in 335718334Speter jump.c */ 335818334Speter if (old_label) 335918334Speter ++LABEL_NUSES (old_label); 336018334Speter 336190075Sobrien if (invert_jump (delay_insn, label, 1)) 336218334Speter { 336318334Speter int i; 336418334Speter 336518334Speter /* Must update the INSN_FROM_TARGET_P bits now that 336618334Speter the branch is reversed, so that mark_target_live_regs 336718334Speter will handle the delay slot insn correctly. */ 336818334Speter for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++) 336918334Speter { 337018334Speter rtx slot = XVECEXP (PATTERN (insn), 0, i); 337118334Speter INSN_FROM_TARGET_P (slot) = ! INSN_FROM_TARGET_P (slot); 337218334Speter } 337318334Speter 337490075Sobrien delete_related_insns (next); 337518334Speter next = insn; 337618334Speter } 337718334Speter 337818334Speter if (old_label && --LABEL_NUSES (old_label) == 0) 337990075Sobrien delete_related_insns (old_label); 338018334Speter continue; 338118334Speter } 338218334Speter } 338318334Speter 338418334Speter /* If we own the thread opposite the way this insn branches, see if we 338518334Speter can merge its delay slots with following insns. */ 338618334Speter if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1)) 338718334Speter && own_thread_p (NEXT_INSN (insn), 0, 1)) 338818334Speter try_merge_delay_insns (insn, next); 338918334Speter else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1)) 339018334Speter && own_thread_p (target_label, target_label, 0)) 339118334Speter try_merge_delay_insns (insn, next_active_insn (target_label)); 339218334Speter 339318334Speter /* If we get here, we haven't deleted INSN. But we may have deleted 339418334Speter NEXT, so recompute it. */ 339518334Speter next = next_active_insn (insn); 339618334Speter } 339718334Speter} 339818334Speter 339918334Speter#ifdef HAVE_return 340018334Speter 340118334Speter/* Look for filled jumps to the end of function label. We can try to convert 340218334Speter them into RETURN insns if the insns in the delay slot are valid for the 340318334Speter RETURN as well. */ 340418334Speter 340518334Speterstatic void 3406132718Skanmake_return_insns (rtx first) 340718334Speter{ 340818334Speter rtx insn, jump_insn, pat; 340918334Speter rtx real_return_label = end_of_function_label; 341018334Speter int slots, i; 341118334Speter 3412117395Skan#ifdef DELAY_SLOTS_FOR_EPILOGUE 3413117395Skan /* If a previous pass filled delay slots in the epilogue, things get a 3414117395Skan bit more complicated, as those filler insns would generally (without 3415117395Skan data flow analysis) have to be executed after any existing branch 3416117395Skan delay slot filler insns. It is also unknown whether such a 3417117395Skan transformation would actually be profitable. Note that the existing 3418117395Skan code only cares for branches with (some) filled delay slots. */ 3419117395Skan if (current_function_epilogue_delay_list != NULL) 3420117395Skan return; 3421117395Skan#endif 3422117395Skan 342318334Speter /* See if there is a RETURN insn in the function other than the one we 342418334Speter made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change 342518334Speter into a RETURN to jump to it. */ 342618334Speter for (insn = first; insn; insn = NEXT_INSN (insn)) 3427169689Skan if (JUMP_P (insn) && GET_CODE (PATTERN (insn)) == RETURN) 342818334Speter { 342918334Speter real_return_label = get_label_before (insn); 343018334Speter break; 343118334Speter } 343290075Sobrien 343318334Speter /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it 343418334Speter was equal to END_OF_FUNCTION_LABEL. */ 343518334Speter LABEL_NUSES (real_return_label)++; 343618334Speter 343718334Speter /* Clear the list of insns to fill so we can use it. */ 343818334Speter obstack_free (&unfilled_slots_obstack, unfilled_firstobj); 343918334Speter 344018334Speter for (insn = first; insn; insn = NEXT_INSN (insn)) 344118334Speter { 344218334Speter int flags; 344318334Speter 344418334Speter /* Only look at filled JUMP_INSNs that go to the end of function 344518334Speter label. */ 3446169689Skan if (!NONJUMP_INSN_P (insn) 344718334Speter || GET_CODE (PATTERN (insn)) != SEQUENCE 3448169689Skan || !JUMP_P (XVECEXP (PATTERN (insn), 0, 0)) 344918334Speter || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label) 345018334Speter continue; 345118334Speter 345218334Speter pat = PATTERN (insn); 345318334Speter jump_insn = XVECEXP (pat, 0, 0); 345418334Speter 345518334Speter /* If we can't make the jump into a RETURN, try to redirect it to the best 345618334Speter RETURN and go on to the next insn. */ 345718334Speter if (! reorg_redirect_jump (jump_insn, NULL_RTX)) 345818334Speter { 345918334Speter /* Make sure redirecting the jump will not invalidate the delay 346018334Speter slot insns. */ 346118334Speter if (redirect_with_delay_slots_safe_p (jump_insn, 346218334Speter real_return_label, 346318334Speter insn)) 346418334Speter reorg_redirect_jump (jump_insn, real_return_label); 346518334Speter continue; 346618334Speter } 346718334Speter 346818334Speter /* See if this RETURN can accept the insns current in its delay slot. 346918334Speter It can if it has more or an equal number of slots and the contents 347018334Speter of each is valid. */ 347118334Speter 347218334Speter flags = get_jump_flags (jump_insn, JUMP_LABEL (jump_insn)); 347318334Speter slots = num_delay_slots (jump_insn); 347418334Speter if (slots >= XVECLEN (pat, 0) - 1) 347518334Speter { 347618334Speter for (i = 1; i < XVECLEN (pat, 0); i++) 347718334Speter if (! ( 347818334Speter#ifdef ANNUL_IFFALSE_SLOTS 347918334Speter (INSN_ANNULLED_BRANCH_P (jump_insn) 348018334Speter && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i))) 348118334Speter ? eligible_for_annul_false (jump_insn, i - 1, 348218334Speter XVECEXP (pat, 0, i), flags) : 348318334Speter#endif 348418334Speter#ifdef ANNUL_IFTRUE_SLOTS 348518334Speter (INSN_ANNULLED_BRANCH_P (jump_insn) 348618334Speter && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i))) 348718334Speter ? eligible_for_annul_true (jump_insn, i - 1, 348818334Speter XVECEXP (pat, 0, i), flags) : 348918334Speter#endif 349090075Sobrien eligible_for_delay (jump_insn, i - 1, 349190075Sobrien XVECEXP (pat, 0, i), flags))) 349218334Speter break; 349318334Speter } 349418334Speter else 349518334Speter i = 0; 349618334Speter 349718334Speter if (i == XVECLEN (pat, 0)) 349818334Speter continue; 349918334Speter 350018334Speter /* We have to do something with this insn. If it is an unconditional 350118334Speter RETURN, delete the SEQUENCE and output the individual insns, 350218334Speter followed by the RETURN. Then set things up so we try to find 350318334Speter insns for its delay slots, if it needs some. */ 350418334Speter if (GET_CODE (PATTERN (jump_insn)) == RETURN) 350518334Speter { 350618334Speter rtx prev = PREV_INSN (insn); 350718334Speter 350890075Sobrien delete_related_insns (insn); 350918334Speter for (i = 1; i < XVECLEN (pat, 0); i++) 351018334Speter prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev); 351118334Speter 351218334Speter insn = emit_jump_insn_after (PATTERN (jump_insn), prev); 351318334Speter emit_barrier_after (insn); 351418334Speter 351518334Speter if (slots) 351618334Speter obstack_ptr_grow (&unfilled_slots_obstack, insn); 351718334Speter } 351818334Speter else 351918334Speter /* It is probably more efficient to keep this with its current 352018334Speter delay slot as a branch to a RETURN. */ 352118334Speter reorg_redirect_jump (jump_insn, real_return_label); 352218334Speter } 352318334Speter 352418334Speter /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any 352518334Speter new delay slots we have created. */ 352618334Speter if (--LABEL_NUSES (real_return_label) == 0) 352790075Sobrien delete_related_insns (real_return_label); 352818334Speter 352950397Sobrien fill_simple_delay_slots (1); 353050397Sobrien fill_simple_delay_slots (0); 353118334Speter} 353218334Speter#endif 353318334Speter 353418334Speter/* Try to find insns to place in delay slots. */ 353518334Speter 353618334Spetervoid 3537169689Skandbr_schedule (rtx first) 353818334Speter{ 353918334Speter rtx insn, next, epilogue_insn = 0; 354018334Speter int i; 354118334Speter 354290075Sobrien /* If the current function has no insns other than the prologue and 354318334Speter epilogue, then do not try to fill any delay slots. */ 3544169689Skan if (n_basic_blocks == NUM_FIXED_BLOCKS) 354518334Speter return; 354618334Speter 354718334Speter /* Find the highest INSN_UID and allocate and initialize our map from 354818334Speter INSN_UID's to position in code. */ 354918334Speter for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn)) 355018334Speter { 355118334Speter if (INSN_UID (insn) > max_uid) 355218334Speter max_uid = INSN_UID (insn); 3553169689Skan if (NOTE_P (insn) 355418334Speter && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EPILOGUE_BEG) 355518334Speter epilogue_insn = insn; 355618334Speter } 355718334Speter 3558132718Skan uid_to_ruid = xmalloc ((max_uid + 1) * sizeof (int)); 355918334Speter for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn)) 356018334Speter uid_to_ruid[INSN_UID (insn)] = i; 356190075Sobrien 356218334Speter /* Initialize the list of insns that need filling. */ 356318334Speter if (unfilled_firstobj == 0) 356418334Speter { 356518334Speter gcc_obstack_init (&unfilled_slots_obstack); 3566132718Skan unfilled_firstobj = obstack_alloc (&unfilled_slots_obstack, 0); 356718334Speter } 356818334Speter 356918334Speter for (insn = next_active_insn (first); insn; insn = next_active_insn (insn)) 357018334Speter { 357118334Speter rtx target; 357218334Speter 357318334Speter INSN_ANNULLED_BRANCH_P (insn) = 0; 357418334Speter INSN_FROM_TARGET_P (insn) = 0; 357518334Speter 357618334Speter /* Skip vector tables. We can't get attributes for them. */ 3577169689Skan if (JUMP_P (insn) 357818334Speter && (GET_CODE (PATTERN (insn)) == ADDR_VEC 357918334Speter || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)) 358018334Speter continue; 358190075Sobrien 358218334Speter if (num_delay_slots (insn) > 0) 358318334Speter obstack_ptr_grow (&unfilled_slots_obstack, insn); 358418334Speter 358518334Speter /* Ensure all jumps go to the last of a set of consecutive labels. */ 3586169689Skan if (JUMP_P (insn) 358718334Speter && (condjump_p (insn) || condjump_in_parallel_p (insn)) 358818334Speter && JUMP_LABEL (insn) != 0 3589169689Skan && ((target = skip_consecutive_labels (JUMP_LABEL (insn))) 359018334Speter != JUMP_LABEL (insn))) 359190075Sobrien redirect_jump (insn, target, 1); 359218334Speter } 359318334Speter 359452284Sobrien init_resource_info (epilogue_insn); 359518334Speter 359618334Speter /* Show we haven't computed an end-of-function label yet. */ 359718334Speter end_of_function_label = 0; 359818334Speter 359918334Speter /* Initialize the statistics for this function. */ 3600132718Skan memset (num_insns_needing_delays, 0, sizeof num_insns_needing_delays); 3601132718Skan memset (num_filled_delays, 0, sizeof num_filled_delays); 360218334Speter 360318334Speter /* Now do the delay slot filling. Try everything twice in case earlier 360418334Speter changes make more slots fillable. */ 360518334Speter 360618334Speter for (reorg_pass_number = 0; 360718334Speter reorg_pass_number < MAX_REORG_PASSES; 360818334Speter reorg_pass_number++) 360918334Speter { 361050397Sobrien fill_simple_delay_slots (1); 361150397Sobrien fill_simple_delay_slots (0); 361250397Sobrien fill_eager_delay_slots (); 361318334Speter relax_delay_slots (first); 361418334Speter } 361518334Speter 361618334Speter /* Delete any USE insns made by update_block; subsequent passes don't need 361718334Speter them or know how to deal with them. */ 361818334Speter for (insn = first; insn; insn = next) 361918334Speter { 362018334Speter next = NEXT_INSN (insn); 362118334Speter 3622169689Skan if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == USE 362390075Sobrien && INSN_P (XEXP (PATTERN (insn), 0))) 362490075Sobrien next = delete_related_insns (insn); 362518334Speter } 362618334Speter 362718334Speter /* If we made an end of function label, indicate that it is now 362818334Speter safe to delete it by undoing our prior adjustment to LABEL_NUSES. 362918334Speter If it is now unused, delete it. */ 363018334Speter if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0) 363190075Sobrien delete_related_insns (end_of_function_label); 363218334Speter 363318334Speter#ifdef HAVE_return 363418334Speter if (HAVE_return && end_of_function_label != 0) 363518334Speter make_return_insns (first); 363618334Speter#endif 363718334Speter 363818334Speter obstack_free (&unfilled_slots_obstack, unfilled_firstobj); 363918334Speter 364018334Speter /* It is not clear why the line below is needed, but it does seem to be. */ 3641132718Skan unfilled_firstobj = obstack_alloc (&unfilled_slots_obstack, 0); 364218334Speter 3643169689Skan if (dump_file) 364418334Speter { 364590075Sobrien int i, j, need_comma; 364690075Sobrien int total_delay_slots[MAX_DELAY_HISTOGRAM + 1]; 364790075Sobrien int total_annul_slots[MAX_DELAY_HISTOGRAM + 1]; 364818334Speter 364918334Speter for (reorg_pass_number = 0; 365018334Speter reorg_pass_number < MAX_REORG_PASSES; 365118334Speter reorg_pass_number++) 365218334Speter { 3653169689Skan fprintf (dump_file, ";; Reorg pass #%d:\n", reorg_pass_number + 1); 365418334Speter for (i = 0; i < NUM_REORG_FUNCTIONS; i++) 365518334Speter { 365618334Speter need_comma = 0; 3657169689Skan fprintf (dump_file, ";; Reorg function #%d\n", i); 365818334Speter 3659169689Skan fprintf (dump_file, ";; %d insns needing delay slots\n;; ", 366018334Speter num_insns_needing_delays[i][reorg_pass_number]); 366118334Speter 366290075Sobrien for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++) 366318334Speter if (num_filled_delays[i][j][reorg_pass_number]) 366418334Speter { 366518334Speter if (need_comma) 3666169689Skan fprintf (dump_file, ", "); 366718334Speter need_comma = 1; 3668169689Skan fprintf (dump_file, "%d got %d delays", 366918334Speter num_filled_delays[i][j][reorg_pass_number], j); 367018334Speter } 3671169689Skan fprintf (dump_file, "\n"); 367218334Speter } 367318334Speter } 3674132718Skan memset (total_delay_slots, 0, sizeof total_delay_slots); 3675132718Skan memset (total_annul_slots, 0, sizeof total_annul_slots); 367690075Sobrien for (insn = first; insn; insn = NEXT_INSN (insn)) 367790075Sobrien { 367890075Sobrien if (! INSN_DELETED_P (insn) 3679169689Skan && NONJUMP_INSN_P (insn) 368090075Sobrien && GET_CODE (PATTERN (insn)) != USE 368190075Sobrien && GET_CODE (PATTERN (insn)) != CLOBBER) 368290075Sobrien { 368390075Sobrien if (GET_CODE (PATTERN (insn)) == SEQUENCE) 368490075Sobrien { 368590075Sobrien j = XVECLEN (PATTERN (insn), 0) - 1; 368690075Sobrien if (j > MAX_DELAY_HISTOGRAM) 368790075Sobrien j = MAX_DELAY_HISTOGRAM; 368890075Sobrien if (INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (insn), 0, 0))) 368990075Sobrien total_annul_slots[j]++; 369090075Sobrien else 369190075Sobrien total_delay_slots[j]++; 369290075Sobrien } 369390075Sobrien else if (num_delay_slots (insn) > 0) 369490075Sobrien total_delay_slots[0]++; 369590075Sobrien } 369690075Sobrien } 3697169689Skan fprintf (dump_file, ";; Reorg totals: "); 369890075Sobrien need_comma = 0; 369990075Sobrien for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++) 370090075Sobrien { 370190075Sobrien if (total_delay_slots[j]) 370290075Sobrien { 370390075Sobrien if (need_comma) 3704169689Skan fprintf (dump_file, ", "); 370590075Sobrien need_comma = 1; 3706169689Skan fprintf (dump_file, "%d got %d delays", total_delay_slots[j], j); 370790075Sobrien } 370890075Sobrien } 3709169689Skan fprintf (dump_file, "\n"); 371090075Sobrien#if defined (ANNUL_IFTRUE_SLOTS) || defined (ANNUL_IFFALSE_SLOTS) 3711169689Skan fprintf (dump_file, ";; Reorg annuls: "); 371290075Sobrien need_comma = 0; 371390075Sobrien for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++) 371490075Sobrien { 371590075Sobrien if (total_annul_slots[j]) 371690075Sobrien { 371790075Sobrien if (need_comma) 3718169689Skan fprintf (dump_file, ", "); 371990075Sobrien need_comma = 1; 3720169689Skan fprintf (dump_file, "%d got %d delays", total_annul_slots[j], j); 372190075Sobrien } 372290075Sobrien } 3723169689Skan fprintf (dump_file, "\n"); 372490075Sobrien#endif 3725169689Skan fprintf (dump_file, "\n"); 372618334Speter } 372750397Sobrien 372850397Sobrien /* For all JUMP insns, fill in branch prediction notes, so that during 372950397Sobrien assembler output a target can set branch prediction bits in the code. 373050397Sobrien We have to do this now, as up until this point the destinations of 373150397Sobrien JUMPS can be moved around and changed, but past right here that cannot 373250397Sobrien happen. */ 373350397Sobrien for (insn = first; insn; insn = NEXT_INSN (insn)) 373450397Sobrien { 373550397Sobrien int pred_flags; 373650397Sobrien 3737169689Skan if (NONJUMP_INSN_P (insn)) 373890075Sobrien { 373952284Sobrien rtx pat = PATTERN (insn); 374052284Sobrien 374152284Sobrien if (GET_CODE (pat) == SEQUENCE) 374252284Sobrien insn = XVECEXP (pat, 0, 0); 374352284Sobrien } 3744169689Skan if (!JUMP_P (insn)) 374550397Sobrien continue; 374650397Sobrien 374750397Sobrien pred_flags = get_jump_flags (insn, JUMP_LABEL (insn)); 374850397Sobrien REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_BR_PRED, 374950397Sobrien GEN_INT (pred_flags), 375050397Sobrien REG_NOTES (insn)); 375150397Sobrien } 375252284Sobrien free_resource_info (); 375390075Sobrien free (uid_to_ruid); 3754132718Skan#ifdef DELAY_SLOTS_FOR_EPILOGUE 3755132718Skan /* SPARC assembler, for instance, emit warning when debug info is output 3756132718Skan into the delay slot. */ 3757132718Skan { 3758132718Skan rtx link; 3759132718Skan 3760132718Skan for (link = current_function_epilogue_delay_list; 3761132718Skan link; 3762132718Skan link = XEXP (link, 1)) 3763132718Skan INSN_LOCATOR (XEXP (link, 0)) = 0; 3764132718Skan } 3765132718Skan#endif 376618334Speter} 376718334Speter#endif /* DELAY_SLOTS */ 3768169689Skan 3769169689Skanstatic bool 3770169689Skangate_handle_delay_slots (void) 3771169689Skan{ 3772169689Skan#ifdef DELAY_SLOTS 3773169689Skan return flag_delayed_branch; 3774169689Skan#else 3775169689Skan return 0; 3776169689Skan#endif 3777169689Skan} 3778169689Skan 3779169689Skan/* Run delay slot optimization. */ 3780169689Skanstatic unsigned int 3781169689Skanrest_of_handle_delay_slots (void) 3782169689Skan{ 3783169689Skan#ifdef DELAY_SLOTS 3784169689Skan dbr_schedule (get_insns ()); 3785169689Skan#endif 3786169689Skan return 0; 3787169689Skan} 3788169689Skan 3789169689Skanstruct tree_opt_pass pass_delay_slots = 3790169689Skan{ 3791169689Skan "dbr", /* name */ 3792169689Skan gate_handle_delay_slots, /* gate */ 3793169689Skan rest_of_handle_delay_slots, /* execute */ 3794169689Skan NULL, /* sub */ 3795169689Skan NULL, /* next */ 3796169689Skan 0, /* static_pass_number */ 3797169689Skan TV_DBR_SCHED, /* tv_id */ 3798169689Skan 0, /* properties_required */ 3799169689Skan 0, /* properties_provided */ 3800169689Skan 0, /* properties_destroyed */ 3801169689Skan 0, /* todo_flags_start */ 3802169689Skan TODO_dump_func | 3803169689Skan TODO_ggc_collect, /* todo_flags_finish */ 3804169689Skan 'd' /* letter */ 3805169689Skan}; 3806169689Skan 3807169689Skan/* Machine dependent reorg pass. */ 3808169689Skanstatic bool 3809169689Skangate_handle_machine_reorg (void) 3810169689Skan{ 3811169689Skan return targetm.machine_dependent_reorg != 0; 3812169689Skan} 3813169689Skan 3814169689Skan 3815169689Skanstatic unsigned int 3816169689Skanrest_of_handle_machine_reorg (void) 3817169689Skan{ 3818169689Skan targetm.machine_dependent_reorg (); 3819169689Skan return 0; 3820169689Skan} 3821169689Skan 3822169689Skanstruct tree_opt_pass pass_machine_reorg = 3823169689Skan{ 3824169689Skan "mach", /* name */ 3825169689Skan gate_handle_machine_reorg, /* gate */ 3826169689Skan rest_of_handle_machine_reorg, /* execute */ 3827169689Skan NULL, /* sub */ 3828169689Skan NULL, /* next */ 3829169689Skan 0, /* static_pass_number */ 3830169689Skan TV_MACH_DEP, /* tv_id */ 3831169689Skan 0, /* properties_required */ 3832169689Skan 0, /* properties_provided */ 3833169689Skan 0, /* properties_destroyed */ 3834169689Skan 0, /* todo_flags_start */ 3835169689Skan TODO_dump_func | 3836169689Skan TODO_ggc_collect, /* todo_flags_finish */ 3837169689Skan 'M' /* letter */ 3838169689Skan}; 3839169689Skan 3840