152284Sobrien/* Definitions for computing resource usage of specific insns. 2169689Skan Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005 3132718Skan Free Software Foundation, Inc. 452284Sobrien 590075SobrienThis file is part of GCC. 652284Sobrien 790075SobrienGCC is free software; you can redistribute it and/or modify it under 890075Sobrienthe terms of the GNU General Public License as published by the Free 990075SobrienSoftware Foundation; either version 2, or (at your option) any later 1090075Sobrienversion. 1152284Sobrien 1290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1590075Sobrienfor more details. 1652284Sobrien 1752284SobrienYou should have received a copy of the GNU General Public License 1890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 2152284Sobrien 2252284Sobrien#include "config.h" 2390075Sobrien#include "system.h" 24132718Skan#include "coretypes.h" 25132718Skan#include "tm.h" 2652284Sobrien#include "toplev.h" 2752284Sobrien#include "rtl.h" 2890075Sobrien#include "tm_p.h" 2952284Sobrien#include "hard-reg-set.h" 3090075Sobrien#include "function.h" 3152284Sobrien#include "regs.h" 3252284Sobrien#include "flags.h" 3352284Sobrien#include "output.h" 3452284Sobrien#include "resource.h" 3590075Sobrien#include "except.h" 3690075Sobrien#include "insn-attr.h" 3790075Sobrien#include "params.h" 3852284Sobrien 3952284Sobrien/* This structure is used to record liveness information at the targets or 4052284Sobrien fallthrough insns of branches. We will most likely need the information 4152284Sobrien at targets again, so save them in a hash table rather than recomputing them 4252284Sobrien each time. */ 4352284Sobrien 4452284Sobrienstruct target_info 4552284Sobrien{ 4652284Sobrien int uid; /* INSN_UID of target. */ 4752284Sobrien struct target_info *next; /* Next info for same hash bucket. */ 4852284Sobrien HARD_REG_SET live_regs; /* Registers live at target. */ 4952284Sobrien int block; /* Basic block number containing target. */ 5052284Sobrien int bb_tick; /* Generation count of basic block info. */ 5152284Sobrien}; 5252284Sobrien 5352284Sobrien#define TARGET_HASH_PRIME 257 5452284Sobrien 5552284Sobrien/* Indicates what resources are required at the beginning of the epilogue. */ 5652284Sobrienstatic struct resources start_of_epilogue_needs; 5752284Sobrien 5852284Sobrien/* Indicates what resources are required at function end. */ 5952284Sobrienstatic struct resources end_of_function_needs; 6052284Sobrien 6152284Sobrien/* Define the hash table itself. */ 6252284Sobrienstatic struct target_info **target_hash_table = NULL; 6352284Sobrien 6452284Sobrien/* For each basic block, we maintain a generation number of its basic 6552284Sobrien block info, which is updated each time we move an insn from the 6652284Sobrien target of a jump. This is the generation number indexed by block 6752284Sobrien number. */ 6852284Sobrien 6952284Sobrienstatic int *bb_ticks; 7052284Sobrien 7152284Sobrien/* Marks registers possibly live at the current place being scanned by 7290075Sobrien mark_target_live_regs. Also used by update_live_status. */ 7352284Sobrien 7452284Sobrienstatic HARD_REG_SET current_live_regs; 7552284Sobrien 7652284Sobrien/* Marks registers for which we have seen a REG_DEAD note but no assignment. 7752284Sobrien Also only used by the next two functions. */ 7852284Sobrien 7952284Sobrienstatic HARD_REG_SET pending_dead_regs; 8052284Sobrien 81132718Skanstatic void update_live_status (rtx, rtx, void *); 82132718Skanstatic int find_basic_block (rtx, int); 83132718Skanstatic rtx next_insn_no_annul (rtx); 84132718Skanstatic rtx find_dead_or_set_registers (rtx, struct resources*, 85132718Skan rtx*, int, struct resources, 86132718Skan struct resources); 8752284Sobrien 8852284Sobrien/* Utility function called from mark_target_live_regs via note_stores. 8952284Sobrien It deadens any CLOBBERed registers and livens any SET registers. */ 9052284Sobrien 9152284Sobrienstatic void 92132718Skanupdate_live_status (rtx dest, rtx x, void *data ATTRIBUTE_UNUSED) 9352284Sobrien{ 9452284Sobrien int first_regno, last_regno; 9552284Sobrien int i; 9652284Sobrien 97169689Skan if (!REG_P (dest) 98169689Skan && (GET_CODE (dest) != SUBREG || !REG_P (SUBREG_REG (dest)))) 9952284Sobrien return; 10052284Sobrien 10152284Sobrien if (GET_CODE (dest) == SUBREG) 10290075Sobrien first_regno = subreg_regno (dest); 10352284Sobrien else 10452284Sobrien first_regno = REGNO (dest); 10552284Sobrien 106169689Skan last_regno = first_regno + hard_regno_nregs[first_regno][GET_MODE (dest)]; 10752284Sobrien 10852284Sobrien if (GET_CODE (x) == CLOBBER) 10952284Sobrien for (i = first_regno; i < last_regno; i++) 11052284Sobrien CLEAR_HARD_REG_BIT (current_live_regs, i); 11152284Sobrien else 11252284Sobrien for (i = first_regno; i < last_regno; i++) 11352284Sobrien { 11452284Sobrien SET_HARD_REG_BIT (current_live_regs, i); 11552284Sobrien CLEAR_HARD_REG_BIT (pending_dead_regs, i); 11652284Sobrien } 11752284Sobrien} 11852284Sobrien 11990075Sobrien/* Find the number of the basic block with correct live register 12090075Sobrien information that starts closest to INSN. Return -1 if we couldn't 12190075Sobrien find such a basic block or the beginning is more than 12290075Sobrien SEARCH_LIMIT instructions before INSN. Use SEARCH_LIMIT = -1 for 12390075Sobrien an unlimited search. 12490075Sobrien 12590075Sobrien The delay slot filling code destroys the control-flow graph so, 12690075Sobrien instead of finding the basic block containing INSN, we search 12790075Sobrien backwards toward a BARRIER where the live register information is 12890075Sobrien correct. */ 12990075Sobrien 13052284Sobrienstatic int 131132718Skanfind_basic_block (rtx insn, int search_limit) 13252284Sobrien{ 133117395Skan basic_block bb; 13452284Sobrien 13552284Sobrien /* Scan backwards to the previous BARRIER. Then see if we can find a 13652284Sobrien label that starts a basic block. Return the basic block number. */ 13752284Sobrien for (insn = prev_nonnote_insn (insn); 138169689Skan insn && !BARRIER_P (insn) && search_limit != 0; 13990075Sobrien insn = prev_nonnote_insn (insn), --search_limit) 14052284Sobrien ; 14152284Sobrien 14290075Sobrien /* The closest BARRIER is too far away. */ 14390075Sobrien if (search_limit == 0) 14490075Sobrien return -1; 14590075Sobrien 146117395Skan /* The start of the function. */ 14790075Sobrien else if (insn == 0) 148117395Skan return ENTRY_BLOCK_PTR->next_bb->index; 14952284Sobrien 15052284Sobrien /* See if any of the upcoming CODE_LABELs start a basic block. If we reach 15152284Sobrien anything other than a CODE_LABEL or note, we can't find this code. */ 15252284Sobrien for (insn = next_nonnote_insn (insn); 153169689Skan insn && LABEL_P (insn); 15452284Sobrien insn = next_nonnote_insn (insn)) 15552284Sobrien { 156117395Skan FOR_EACH_BB (bb) 157132718Skan if (insn == BB_HEAD (bb)) 158117395Skan return bb->index; 15952284Sobrien } 16052284Sobrien 16152284Sobrien return -1; 16252284Sobrien} 16352284Sobrien 16452284Sobrien/* Similar to next_insn, but ignores insns in the delay slots of 16552284Sobrien an annulled branch. */ 16652284Sobrien 16752284Sobrienstatic rtx 168132718Skannext_insn_no_annul (rtx insn) 16952284Sobrien{ 17052284Sobrien if (insn) 17152284Sobrien { 17252284Sobrien /* If INSN is an annulled branch, skip any insns from the target 17352284Sobrien of the branch. */ 174169689Skan if (INSN_P (insn) 175117395Skan && INSN_ANNULLED_BRANCH_P (insn) 17652284Sobrien && NEXT_INSN (PREV_INSN (insn)) != insn) 177117395Skan { 178117395Skan rtx next = NEXT_INSN (insn); 179117395Skan enum rtx_code code = GET_CODE (next); 18052284Sobrien 181117395Skan while ((code == INSN || code == JUMP_INSN || code == CALL_INSN) 182117395Skan && INSN_FROM_TARGET_P (next)) 183117395Skan { 184117395Skan insn = next; 185117395Skan next = NEXT_INSN (insn); 186117395Skan code = GET_CODE (next); 187117395Skan } 188117395Skan } 189117395Skan 19052284Sobrien insn = NEXT_INSN (insn); 191169689Skan if (insn && NONJUMP_INSN_P (insn) 19252284Sobrien && GET_CODE (PATTERN (insn)) == SEQUENCE) 19352284Sobrien insn = XVECEXP (PATTERN (insn), 0, 0); 19452284Sobrien } 19552284Sobrien 19652284Sobrien return insn; 19752284Sobrien} 19852284Sobrien 19952284Sobrien/* Given X, some rtl, and RES, a pointer to a `struct resource', mark 20090075Sobrien which resources are referenced by the insn. If INCLUDE_DELAYED_EFFECTS 20152284Sobrien is TRUE, resources used by the called routine will be included for 20252284Sobrien CALL_INSNs. */ 20352284Sobrien 20452284Sobrienvoid 205132718Skanmark_referenced_resources (rtx x, struct resources *res, 206132718Skan int include_delayed_effects) 20752284Sobrien{ 20890075Sobrien enum rtx_code code = GET_CODE (x); 20990075Sobrien int i, j; 21090075Sobrien unsigned int r; 21190075Sobrien const char *format_ptr; 21252284Sobrien 21352284Sobrien /* Handle leaf items for which we set resource flags. Also, special-case 21452284Sobrien CALL, SET and CLOBBER operators. */ 21552284Sobrien switch (code) 21652284Sobrien { 21752284Sobrien case CONST: 21852284Sobrien case CONST_INT: 21952284Sobrien case CONST_DOUBLE: 22096263Sobrien case CONST_VECTOR: 22152284Sobrien case PC: 22252284Sobrien case SYMBOL_REF: 22352284Sobrien case LABEL_REF: 22452284Sobrien return; 22552284Sobrien 22652284Sobrien case SUBREG: 227169689Skan if (!REG_P (SUBREG_REG (x))) 22852284Sobrien mark_referenced_resources (SUBREG_REG (x), res, 0); 22952284Sobrien else 23052284Sobrien { 23190075Sobrien unsigned int regno = subreg_regno (x); 23290075Sobrien unsigned int last_regno 233169689Skan = regno + hard_regno_nregs[regno][GET_MODE (x)]; 23490075Sobrien 235169689Skan gcc_assert (last_regno <= FIRST_PSEUDO_REGISTER); 23690075Sobrien for (r = regno; r < last_regno; r++) 23790075Sobrien SET_HARD_REG_BIT (res->regs, r); 23852284Sobrien } 23952284Sobrien return; 24052284Sobrien 24152284Sobrien case REG: 24290075Sobrien { 24390075Sobrien unsigned int regno = REGNO (x); 24490075Sobrien unsigned int last_regno 245169689Skan = regno + hard_regno_nregs[regno][GET_MODE (x)]; 24690075Sobrien 247169689Skan gcc_assert (last_regno <= FIRST_PSEUDO_REGISTER); 24890075Sobrien for (r = regno; r < last_regno; r++) 24990075Sobrien SET_HARD_REG_BIT (res->regs, r); 25090075Sobrien } 25152284Sobrien return; 25252284Sobrien 25352284Sobrien case MEM: 25452284Sobrien /* If this memory shouldn't change, it really isn't referencing 25552284Sobrien memory. */ 256169689Skan if (MEM_READONLY_P (x)) 25752284Sobrien res->unch_memory = 1; 25852284Sobrien else 25952284Sobrien res->memory = 1; 26052284Sobrien res->volatil |= MEM_VOLATILE_P (x); 26152284Sobrien 26252284Sobrien /* Mark registers used to access memory. */ 26352284Sobrien mark_referenced_resources (XEXP (x, 0), res, 0); 26452284Sobrien return; 26552284Sobrien 26652284Sobrien case CC0: 26752284Sobrien res->cc = 1; 26852284Sobrien return; 26952284Sobrien 27052284Sobrien case UNSPEC_VOLATILE: 27152284Sobrien case ASM_INPUT: 27252284Sobrien /* Traditional asm's are always volatile. */ 27352284Sobrien res->volatil = 1; 27452284Sobrien return; 27552284Sobrien 27652284Sobrien case TRAP_IF: 27752284Sobrien res->volatil = 1; 27852284Sobrien break; 27952284Sobrien 28052284Sobrien case ASM_OPERANDS: 28152284Sobrien res->volatil |= MEM_VOLATILE_P (x); 28252284Sobrien 28352284Sobrien /* For all ASM_OPERANDS, we must traverse the vector of input operands. 28452284Sobrien We can not just fall through here since then we would be confused 28552284Sobrien by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate 28652284Sobrien traditional asms unlike their normal usage. */ 287117395Skan 28852284Sobrien for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++) 28952284Sobrien mark_referenced_resources (ASM_OPERANDS_INPUT (x, i), res, 0); 29052284Sobrien return; 29152284Sobrien 29252284Sobrien case CALL: 29352284Sobrien /* The first operand will be a (MEM (xxx)) but doesn't really reference 29452284Sobrien memory. The second operand may be referenced, though. */ 29552284Sobrien mark_referenced_resources (XEXP (XEXP (x, 0), 0), res, 0); 29652284Sobrien mark_referenced_resources (XEXP (x, 1), res, 0); 29752284Sobrien return; 29852284Sobrien 29952284Sobrien case SET: 30052284Sobrien /* Usually, the first operand of SET is set, not referenced. But 30152284Sobrien registers used to access memory are referenced. SET_DEST is 302169689Skan also referenced if it is a ZERO_EXTRACT. */ 30352284Sobrien 30452284Sobrien mark_referenced_resources (SET_SRC (x), res, 0); 30552284Sobrien 30652284Sobrien x = SET_DEST (x); 307169689Skan if (GET_CODE (x) == ZERO_EXTRACT 30890075Sobrien || GET_CODE (x) == STRICT_LOW_PART) 30952284Sobrien mark_referenced_resources (x, res, 0); 31052284Sobrien else if (GET_CODE (x) == SUBREG) 31152284Sobrien x = SUBREG_REG (x); 312169689Skan if (MEM_P (x)) 31352284Sobrien mark_referenced_resources (XEXP (x, 0), res, 0); 31452284Sobrien return; 31552284Sobrien 31652284Sobrien case CLOBBER: 31752284Sobrien return; 31852284Sobrien 31952284Sobrien case CALL_INSN: 32052284Sobrien if (include_delayed_effects) 32152284Sobrien { 32252284Sobrien /* A CALL references memory, the frame pointer if it exists, the 32352284Sobrien stack pointer, any global registers and any registers given in 32452284Sobrien USE insns immediately in front of the CALL. 32552284Sobrien 32652284Sobrien However, we may have moved some of the parameter loading insns 32752284Sobrien into the delay slot of this CALL. If so, the USE's for them 32852284Sobrien don't count and should be skipped. */ 32952284Sobrien rtx insn = PREV_INSN (x); 33052284Sobrien rtx sequence = 0; 33152284Sobrien int seq_size = 0; 33252284Sobrien int i; 33352284Sobrien 33452284Sobrien /* If we are part of a delay slot sequence, point at the SEQUENCE. */ 33552284Sobrien if (NEXT_INSN (insn) != x) 33652284Sobrien { 33752284Sobrien sequence = PATTERN (NEXT_INSN (insn)); 33852284Sobrien seq_size = XVECLEN (sequence, 0); 339169689Skan gcc_assert (GET_CODE (sequence) == SEQUENCE); 34052284Sobrien } 34152284Sobrien 34252284Sobrien res->memory = 1; 34352284Sobrien SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM); 34452284Sobrien if (frame_pointer_needed) 34552284Sobrien { 34652284Sobrien SET_HARD_REG_BIT (res->regs, FRAME_POINTER_REGNUM); 34752284Sobrien#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 34852284Sobrien SET_HARD_REG_BIT (res->regs, HARD_FRAME_POINTER_REGNUM); 34952284Sobrien#endif 35052284Sobrien } 35152284Sobrien 35252284Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 35352284Sobrien if (global_regs[i]) 35452284Sobrien SET_HARD_REG_BIT (res->regs, i); 35552284Sobrien 35690075Sobrien /* Check for a REG_SETJMP. If it exists, then we must 35752284Sobrien assume that this call can need any register. 35852284Sobrien 35952284Sobrien This is done to be more conservative about how we handle setjmp. 36052284Sobrien We assume that they both use and set all registers. Using all 36152284Sobrien registers ensures that a register will not be considered dead 36252284Sobrien just because it crosses a setjmp call. A register should be 363117395Skan considered dead only if the setjmp call returns nonzero. */ 36490075Sobrien if (find_reg_note (x, REG_SETJMP, NULL)) 36552284Sobrien SET_HARD_REG_SET (res->regs); 36652284Sobrien 36752284Sobrien { 36852284Sobrien rtx link; 36952284Sobrien 37052284Sobrien for (link = CALL_INSN_FUNCTION_USAGE (x); 37152284Sobrien link; 37252284Sobrien link = XEXP (link, 1)) 37352284Sobrien if (GET_CODE (XEXP (link, 0)) == USE) 37452284Sobrien { 37552284Sobrien for (i = 1; i < seq_size; i++) 37652284Sobrien { 37752284Sobrien rtx slot_pat = PATTERN (XVECEXP (sequence, 0, i)); 37852284Sobrien if (GET_CODE (slot_pat) == SET 37952284Sobrien && rtx_equal_p (SET_DEST (slot_pat), 38090075Sobrien XEXP (XEXP (link, 0), 0))) 38152284Sobrien break; 38252284Sobrien } 38352284Sobrien if (i >= seq_size) 38490075Sobrien mark_referenced_resources (XEXP (XEXP (link, 0), 0), 38552284Sobrien res, 0); 38652284Sobrien } 38752284Sobrien } 38852284Sobrien } 38952284Sobrien 39052284Sobrien /* ... fall through to other INSN processing ... */ 39152284Sobrien 39252284Sobrien case INSN: 39352284Sobrien case JUMP_INSN: 39452284Sobrien 39552284Sobrien#ifdef INSN_REFERENCES_ARE_DELAYED 39652284Sobrien if (! include_delayed_effects 39752284Sobrien && INSN_REFERENCES_ARE_DELAYED (x)) 39852284Sobrien return; 39952284Sobrien#endif 40052284Sobrien 40152284Sobrien /* No special processing, just speed up. */ 40252284Sobrien mark_referenced_resources (PATTERN (x), res, include_delayed_effects); 40352284Sobrien return; 40452284Sobrien 40552284Sobrien default: 40652284Sobrien break; 40752284Sobrien } 40852284Sobrien 40952284Sobrien /* Process each sub-expression and flag what it needs. */ 41052284Sobrien format_ptr = GET_RTX_FORMAT (code); 41152284Sobrien for (i = 0; i < GET_RTX_LENGTH (code); i++) 41252284Sobrien switch (*format_ptr++) 41352284Sobrien { 41452284Sobrien case 'e': 41552284Sobrien mark_referenced_resources (XEXP (x, i), res, include_delayed_effects); 41652284Sobrien break; 41752284Sobrien 41852284Sobrien case 'E': 41952284Sobrien for (j = 0; j < XVECLEN (x, i); j++) 42052284Sobrien mark_referenced_resources (XVECEXP (x, i, j), res, 42152284Sobrien include_delayed_effects); 42252284Sobrien break; 42352284Sobrien } 42452284Sobrien} 42552284Sobrien 42652284Sobrien/* A subroutine of mark_target_live_regs. Search forward from TARGET 427117395Skan looking for registers that are set before they are used. These are dead. 42852284Sobrien Stop after passing a few conditional jumps, and/or a small 42952284Sobrien number of unconditional branches. */ 43052284Sobrien 43152284Sobrienstatic rtx 432132718Skanfind_dead_or_set_registers (rtx target, struct resources *res, 433132718Skan rtx *jump_target, int jump_count, 434132718Skan struct resources set, struct resources needed) 43552284Sobrien{ 43652284Sobrien HARD_REG_SET scratch; 43752284Sobrien rtx insn, next; 43852284Sobrien rtx jump_insn = 0; 43952284Sobrien int i; 44052284Sobrien 44152284Sobrien for (insn = target; insn; insn = next) 44252284Sobrien { 44352284Sobrien rtx this_jump_insn = insn; 44452284Sobrien 44552284Sobrien next = NEXT_INSN (insn); 44690075Sobrien 44790075Sobrien /* If this instruction can throw an exception, then we don't 44890075Sobrien know where we might end up next. That means that we have to 44990075Sobrien assume that whatever we have already marked as live really is 45090075Sobrien live. */ 45190075Sobrien if (can_throw_internal (insn)) 45290075Sobrien break; 45390075Sobrien 45452284Sobrien switch (GET_CODE (insn)) 45552284Sobrien { 45652284Sobrien case CODE_LABEL: 45752284Sobrien /* After a label, any pending dead registers that weren't yet 45852284Sobrien used can be made dead. */ 45952284Sobrien AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs); 46052284Sobrien AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs); 46152284Sobrien CLEAR_HARD_REG_SET (pending_dead_regs); 46252284Sobrien 46352284Sobrien continue; 46452284Sobrien 46552284Sobrien case BARRIER: 46652284Sobrien case NOTE: 46752284Sobrien continue; 46852284Sobrien 46952284Sobrien case INSN: 47052284Sobrien if (GET_CODE (PATTERN (insn)) == USE) 47152284Sobrien { 47252284Sobrien /* If INSN is a USE made by update_block, we care about the 47352284Sobrien underlying insn. Any registers set by the underlying insn 47452284Sobrien are live since the insn is being done somewhere else. */ 47590075Sobrien if (INSN_P (XEXP (PATTERN (insn), 0))) 47690075Sobrien mark_set_resources (XEXP (PATTERN (insn), 0), res, 0, 47790075Sobrien MARK_SRC_DEST_CALL); 47852284Sobrien 47952284Sobrien /* All other USE insns are to be ignored. */ 48052284Sobrien continue; 48152284Sobrien } 48252284Sobrien else if (GET_CODE (PATTERN (insn)) == CLOBBER) 48352284Sobrien continue; 48452284Sobrien else if (GET_CODE (PATTERN (insn)) == SEQUENCE) 48552284Sobrien { 48652284Sobrien /* An unconditional jump can be used to fill the delay slot 48752284Sobrien of a call, so search for a JUMP_INSN in any position. */ 48852284Sobrien for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++) 48952284Sobrien { 49052284Sobrien this_jump_insn = XVECEXP (PATTERN (insn), 0, i); 491169689Skan if (JUMP_P (this_jump_insn)) 49252284Sobrien break; 49352284Sobrien } 49452284Sobrien } 49552284Sobrien 49652284Sobrien default: 49752284Sobrien break; 49852284Sobrien } 49952284Sobrien 500169689Skan if (JUMP_P (this_jump_insn)) 50152284Sobrien { 50252284Sobrien if (jump_count++ < 10) 50352284Sobrien { 50490075Sobrien if (any_uncondjump_p (this_jump_insn) 50552284Sobrien || GET_CODE (PATTERN (this_jump_insn)) == RETURN) 50652284Sobrien { 50752284Sobrien next = JUMP_LABEL (this_jump_insn); 50852284Sobrien if (jump_insn == 0) 50952284Sobrien { 51052284Sobrien jump_insn = insn; 51152284Sobrien if (jump_target) 51252284Sobrien *jump_target = JUMP_LABEL (this_jump_insn); 51352284Sobrien } 51452284Sobrien } 51590075Sobrien else if (any_condjump_p (this_jump_insn)) 51652284Sobrien { 51752284Sobrien struct resources target_set, target_res; 51852284Sobrien struct resources fallthrough_res; 51952284Sobrien 52052284Sobrien /* We can handle conditional branches here by following 52152284Sobrien both paths, and then IOR the results of the two paths 52252284Sobrien together, which will give us registers that are dead 52352284Sobrien on both paths. Since this is expensive, we give it 52452284Sobrien a much higher cost than unconditional branches. The 52552284Sobrien cost was chosen so that we will follow at most 1 52652284Sobrien conditional branch. */ 52752284Sobrien 52852284Sobrien jump_count += 4; 52952284Sobrien if (jump_count >= 10) 53052284Sobrien break; 53152284Sobrien 53252284Sobrien mark_referenced_resources (insn, &needed, 1); 53352284Sobrien 53452284Sobrien /* For an annulled branch, mark_set_resources ignores slots 53552284Sobrien filled by instructions from the target. This is correct 53652284Sobrien if the branch is not taken. Since we are following both 53752284Sobrien paths from the branch, we must also compute correct info 53852284Sobrien if the branch is taken. We do this by inverting all of 53952284Sobrien the INSN_FROM_TARGET_P bits, calling mark_set_resources, 54052284Sobrien and then inverting the INSN_FROM_TARGET_P bits again. */ 54152284Sobrien 54252284Sobrien if (GET_CODE (PATTERN (insn)) == SEQUENCE 54352284Sobrien && INSN_ANNULLED_BRANCH_P (this_jump_insn)) 54452284Sobrien { 54552284Sobrien for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++) 54652284Sobrien INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) 54752284Sobrien = ! INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)); 54852284Sobrien 54952284Sobrien target_set = set; 55090075Sobrien mark_set_resources (insn, &target_set, 0, 55190075Sobrien MARK_SRC_DEST_CALL); 55252284Sobrien 55352284Sobrien for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++) 55452284Sobrien INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) 55552284Sobrien = ! INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)); 55652284Sobrien 55790075Sobrien mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL); 55852284Sobrien } 55952284Sobrien else 56052284Sobrien { 56190075Sobrien mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL); 56252284Sobrien target_set = set; 56352284Sobrien } 56452284Sobrien 56552284Sobrien target_res = *res; 56652284Sobrien COPY_HARD_REG_SET (scratch, target_set.regs); 56752284Sobrien AND_COMPL_HARD_REG_SET (scratch, needed.regs); 56852284Sobrien AND_COMPL_HARD_REG_SET (target_res.regs, scratch); 56952284Sobrien 57052284Sobrien fallthrough_res = *res; 57152284Sobrien COPY_HARD_REG_SET (scratch, set.regs); 57252284Sobrien AND_COMPL_HARD_REG_SET (scratch, needed.regs); 57352284Sobrien AND_COMPL_HARD_REG_SET (fallthrough_res.regs, scratch); 57452284Sobrien 57552284Sobrien find_dead_or_set_registers (JUMP_LABEL (this_jump_insn), 57652284Sobrien &target_res, 0, jump_count, 57752284Sobrien target_set, needed); 57852284Sobrien find_dead_or_set_registers (next, 57952284Sobrien &fallthrough_res, 0, jump_count, 58052284Sobrien set, needed); 58152284Sobrien IOR_HARD_REG_SET (fallthrough_res.regs, target_res.regs); 58252284Sobrien AND_HARD_REG_SET (res->regs, fallthrough_res.regs); 58352284Sobrien break; 58452284Sobrien } 58552284Sobrien else 58652284Sobrien break; 58752284Sobrien } 58852284Sobrien else 58952284Sobrien { 59052284Sobrien /* Don't try this optimization if we expired our jump count 59152284Sobrien above, since that would mean there may be an infinite loop 59252284Sobrien in the function being compiled. */ 59352284Sobrien jump_insn = 0; 59452284Sobrien break; 59552284Sobrien } 59652284Sobrien } 59752284Sobrien 59852284Sobrien mark_referenced_resources (insn, &needed, 1); 59990075Sobrien mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL); 60052284Sobrien 60152284Sobrien COPY_HARD_REG_SET (scratch, set.regs); 60252284Sobrien AND_COMPL_HARD_REG_SET (scratch, needed.regs); 60352284Sobrien AND_COMPL_HARD_REG_SET (res->regs, scratch); 60452284Sobrien } 60552284Sobrien 60652284Sobrien return jump_insn; 60752284Sobrien} 60852284Sobrien 60952284Sobrien/* Given X, a part of an insn, and a pointer to a `struct resource', 61052284Sobrien RES, indicate which resources are modified by the insn. If 61190075Sobrien MARK_TYPE is MARK_SRC_DEST_CALL, also mark resources potentially 612132718Skan set by the called routine. 61352284Sobrien 61452284Sobrien If IN_DEST is nonzero, it means we are inside a SET. Otherwise, 61552284Sobrien objects are being referenced instead of set. 61652284Sobrien 61752284Sobrien We never mark the insn as modifying the condition code unless it explicitly 61852284Sobrien SETs CC0 even though this is not totally correct. The reason for this is 61952284Sobrien that we require a SET of CC0 to immediately precede the reference to CC0. 62052284Sobrien So if some other insn sets CC0 as a side-effect, we know it cannot affect 62190075Sobrien our computation and thus may be placed in a delay slot. */ 62252284Sobrien 62352284Sobrienvoid 624132718Skanmark_set_resources (rtx x, struct resources *res, int in_dest, 625132718Skan enum mark_resource_type mark_type) 62652284Sobrien{ 62790075Sobrien enum rtx_code code; 62890075Sobrien int i, j; 62990075Sobrien unsigned int r; 63090075Sobrien const char *format_ptr; 63152284Sobrien 63252284Sobrien restart: 63352284Sobrien 63452284Sobrien code = GET_CODE (x); 63552284Sobrien 63652284Sobrien switch (code) 63752284Sobrien { 63852284Sobrien case NOTE: 63952284Sobrien case BARRIER: 64052284Sobrien case CODE_LABEL: 64152284Sobrien case USE: 64252284Sobrien case CONST_INT: 64352284Sobrien case CONST_DOUBLE: 64496263Sobrien case CONST_VECTOR: 64552284Sobrien case LABEL_REF: 64652284Sobrien case SYMBOL_REF: 64752284Sobrien case CONST: 64852284Sobrien case PC: 64952284Sobrien /* These don't set any resources. */ 65052284Sobrien return; 65152284Sobrien 65252284Sobrien case CC0: 65352284Sobrien if (in_dest) 65452284Sobrien res->cc = 1; 65552284Sobrien return; 65652284Sobrien 65752284Sobrien case CALL_INSN: 65852284Sobrien /* Called routine modifies the condition code, memory, any registers 65952284Sobrien that aren't saved across calls, global registers and anything 66052284Sobrien explicitly CLOBBERed immediately after the CALL_INSN. */ 66152284Sobrien 66290075Sobrien if (mark_type == MARK_SRC_DEST_CALL) 66352284Sobrien { 66452284Sobrien rtx link; 66552284Sobrien 66652284Sobrien res->cc = res->memory = 1; 66790075Sobrien for (r = 0; r < FIRST_PSEUDO_REGISTER; r++) 66890075Sobrien if (call_used_regs[r] || global_regs[r]) 66990075Sobrien SET_HARD_REG_BIT (res->regs, r); 67052284Sobrien 67152284Sobrien for (link = CALL_INSN_FUNCTION_USAGE (x); 67252284Sobrien link; link = XEXP (link, 1)) 67352284Sobrien if (GET_CODE (XEXP (link, 0)) == CLOBBER) 67490075Sobrien mark_set_resources (SET_DEST (XEXP (link, 0)), res, 1, 67590075Sobrien MARK_SRC_DEST); 67652284Sobrien 67790075Sobrien /* Check for a REG_SETJMP. If it exists, then we must 67852284Sobrien assume that this call can clobber any register. */ 67990075Sobrien if (find_reg_note (x, REG_SETJMP, NULL)) 68052284Sobrien SET_HARD_REG_SET (res->regs); 68152284Sobrien } 68252284Sobrien 68352284Sobrien /* ... and also what its RTL says it modifies, if anything. */ 68452284Sobrien 68552284Sobrien case JUMP_INSN: 68652284Sobrien case INSN: 68752284Sobrien 68852284Sobrien /* An insn consisting of just a CLOBBER (or USE) is just for flow 68952284Sobrien and doesn't actually do anything, so we ignore it. */ 69052284Sobrien 69152284Sobrien#ifdef INSN_SETS_ARE_DELAYED 69290075Sobrien if (mark_type != MARK_SRC_DEST_CALL 69352284Sobrien && INSN_SETS_ARE_DELAYED (x)) 69452284Sobrien return; 69552284Sobrien#endif 69652284Sobrien 69752284Sobrien x = PATTERN (x); 69852284Sobrien if (GET_CODE (x) != USE && GET_CODE (x) != CLOBBER) 69952284Sobrien goto restart; 70052284Sobrien return; 70152284Sobrien 70252284Sobrien case SET: 70352284Sobrien /* If the source of a SET is a CALL, this is actually done by 70452284Sobrien the called routine. So only include it if we are to include the 70552284Sobrien effects of the calling routine. */ 70652284Sobrien 70752284Sobrien mark_set_resources (SET_DEST (x), res, 70890075Sobrien (mark_type == MARK_SRC_DEST_CALL 70952284Sobrien || GET_CODE (SET_SRC (x)) != CALL), 71090075Sobrien mark_type); 71152284Sobrien 712132718Skan mark_set_resources (SET_SRC (x), res, 0, MARK_SRC_DEST); 71352284Sobrien return; 71452284Sobrien 71552284Sobrien case CLOBBER: 71690075Sobrien mark_set_resources (XEXP (x, 0), res, 1, MARK_SRC_DEST); 71752284Sobrien return; 718117395Skan 71952284Sobrien case SEQUENCE: 72052284Sobrien for (i = 0; i < XVECLEN (x, 0); i++) 72152284Sobrien if (! (INSN_ANNULLED_BRANCH_P (XVECEXP (x, 0, 0)) 72252284Sobrien && INSN_FROM_TARGET_P (XVECEXP (x, 0, i)))) 72390075Sobrien mark_set_resources (XVECEXP (x, 0, i), res, 0, mark_type); 72452284Sobrien return; 72552284Sobrien 72652284Sobrien case POST_INC: 72752284Sobrien case PRE_INC: 72852284Sobrien case POST_DEC: 72952284Sobrien case PRE_DEC: 73090075Sobrien mark_set_resources (XEXP (x, 0), res, 1, MARK_SRC_DEST); 73152284Sobrien return; 73252284Sobrien 73390075Sobrien case PRE_MODIFY: 73490075Sobrien case POST_MODIFY: 73590075Sobrien mark_set_resources (XEXP (x, 0), res, 1, MARK_SRC_DEST); 73690075Sobrien mark_set_resources (XEXP (XEXP (x, 1), 0), res, 0, MARK_SRC_DEST); 73790075Sobrien mark_set_resources (XEXP (XEXP (x, 1), 1), res, 0, MARK_SRC_DEST); 73890075Sobrien return; 73990075Sobrien 74090075Sobrien case SIGN_EXTRACT: 74152284Sobrien case ZERO_EXTRACT: 742132718Skan mark_set_resources (XEXP (x, 0), res, in_dest, MARK_SRC_DEST); 743132718Skan mark_set_resources (XEXP (x, 1), res, 0, MARK_SRC_DEST); 744132718Skan mark_set_resources (XEXP (x, 2), res, 0, MARK_SRC_DEST); 74552284Sobrien return; 74652284Sobrien 74752284Sobrien case MEM: 74852284Sobrien if (in_dest) 74952284Sobrien { 75052284Sobrien res->memory = 1; 751169689Skan res->unch_memory |= MEM_READONLY_P (x); 75252284Sobrien res->volatil |= MEM_VOLATILE_P (x); 75352284Sobrien } 75452284Sobrien 75590075Sobrien mark_set_resources (XEXP (x, 0), res, 0, MARK_SRC_DEST); 75652284Sobrien return; 75752284Sobrien 75852284Sobrien case SUBREG: 75952284Sobrien if (in_dest) 76052284Sobrien { 761169689Skan if (!REG_P (SUBREG_REG (x))) 76290075Sobrien mark_set_resources (SUBREG_REG (x), res, in_dest, mark_type); 76352284Sobrien else 76452284Sobrien { 76590075Sobrien unsigned int regno = subreg_regno (x); 76690075Sobrien unsigned int last_regno 767169689Skan = regno + hard_regno_nregs[regno][GET_MODE (x)]; 76890075Sobrien 769169689Skan gcc_assert (last_regno <= FIRST_PSEUDO_REGISTER); 77090075Sobrien for (r = regno; r < last_regno; r++) 77190075Sobrien SET_HARD_REG_BIT (res->regs, r); 77252284Sobrien } 77352284Sobrien } 77452284Sobrien return; 77552284Sobrien 77652284Sobrien case REG: 77752284Sobrien if (in_dest) 77890075Sobrien { 77990075Sobrien unsigned int regno = REGNO (x); 78090075Sobrien unsigned int last_regno 781169689Skan = regno + hard_regno_nregs[regno][GET_MODE (x)]; 78290075Sobrien 783169689Skan gcc_assert (last_regno <= FIRST_PSEUDO_REGISTER); 78490075Sobrien for (r = regno; r < last_regno; r++) 78590075Sobrien SET_HARD_REG_BIT (res->regs, r); 78690075Sobrien } 78752284Sobrien return; 78852284Sobrien 78952284Sobrien case UNSPEC_VOLATILE: 79052284Sobrien case ASM_INPUT: 79152284Sobrien /* Traditional asm's are always volatile. */ 79252284Sobrien res->volatil = 1; 79352284Sobrien return; 79452284Sobrien 79552284Sobrien case TRAP_IF: 79652284Sobrien res->volatil = 1; 79752284Sobrien break; 79852284Sobrien 79952284Sobrien case ASM_OPERANDS: 80052284Sobrien res->volatil |= MEM_VOLATILE_P (x); 80152284Sobrien 80252284Sobrien /* For all ASM_OPERANDS, we must traverse the vector of input operands. 80352284Sobrien We can not just fall through here since then we would be confused 80452284Sobrien by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate 80552284Sobrien traditional asms unlike their normal usage. */ 806117395Skan 80752284Sobrien for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++) 80890075Sobrien mark_set_resources (ASM_OPERANDS_INPUT (x, i), res, in_dest, 80990075Sobrien MARK_SRC_DEST); 81052284Sobrien return; 81152284Sobrien 81252284Sobrien default: 81352284Sobrien break; 81452284Sobrien } 81552284Sobrien 81652284Sobrien /* Process each sub-expression and flag what it needs. */ 81752284Sobrien format_ptr = GET_RTX_FORMAT (code); 81852284Sobrien for (i = 0; i < GET_RTX_LENGTH (code); i++) 81952284Sobrien switch (*format_ptr++) 82052284Sobrien { 82152284Sobrien case 'e': 82290075Sobrien mark_set_resources (XEXP (x, i), res, in_dest, mark_type); 82352284Sobrien break; 82452284Sobrien 82552284Sobrien case 'E': 82652284Sobrien for (j = 0; j < XVECLEN (x, i); j++) 82790075Sobrien mark_set_resources (XVECEXP (x, i, j), res, in_dest, mark_type); 82852284Sobrien break; 82952284Sobrien } 83052284Sobrien} 83152284Sobrien 832169689Skan/* Return TRUE if INSN is a return, possibly with a filled delay slot. */ 833169689Skan 834169689Skanstatic bool 835169689Skanreturn_insn_p (rtx insn) 836169689Skan{ 837169689Skan if (JUMP_P (insn) && GET_CODE (PATTERN (insn)) == RETURN) 838169689Skan return true; 839169689Skan 840169689Skan if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == SEQUENCE) 841169689Skan return return_insn_p (XVECEXP (PATTERN (insn), 0, 0)); 842169689Skan 843169689Skan return false; 844169689Skan} 845169689Skan 84652284Sobrien/* Set the resources that are live at TARGET. 84752284Sobrien 84852284Sobrien If TARGET is zero, we refer to the end of the current function and can 84952284Sobrien return our precomputed value. 85052284Sobrien 85152284Sobrien Otherwise, we try to find out what is live by consulting the basic block 85252284Sobrien information. This is tricky, because we must consider the actions of 85352284Sobrien reload and jump optimization, which occur after the basic block information 85452284Sobrien has been computed. 85552284Sobrien 85652284Sobrien Accordingly, we proceed as follows:: 85752284Sobrien 85852284Sobrien We find the previous BARRIER and look at all immediately following labels 85952284Sobrien (with no intervening active insns) to see if any of them start a basic 86052284Sobrien block. If we hit the start of the function first, we use block 0. 86152284Sobrien 86252284Sobrien Once we have found a basic block and a corresponding first insns, we can 86352284Sobrien accurately compute the live status from basic_block_live_regs and 86452284Sobrien reg_renumber. (By starting at a label following a BARRIER, we are immune 86552284Sobrien to actions taken by reload and jump.) Then we scan all insns between 86652284Sobrien that point and our target. For each CLOBBER (or for call-clobbered regs 86752284Sobrien when we pass a CALL_INSN), mark the appropriate registers are dead. For 86852284Sobrien a SET, mark them as live. 86952284Sobrien 87052284Sobrien We have to be careful when using REG_DEAD notes because they are not 87152284Sobrien updated by such things as find_equiv_reg. So keep track of registers 87252284Sobrien marked as dead that haven't been assigned to, and mark them dead at the 87352284Sobrien next CODE_LABEL since reload and jump won't propagate values across labels. 87452284Sobrien 87552284Sobrien If we cannot find the start of a basic block (should be a very rare 87652284Sobrien case, if it can happen at all), mark everything as potentially live. 87752284Sobrien 87852284Sobrien Next, scan forward from TARGET looking for things set or clobbered 87952284Sobrien before they are used. These are not live. 88052284Sobrien 88152284Sobrien Because we can be called many times on the same target, save our results 88252284Sobrien in a hash table indexed by INSN_UID. This is only done if the function 88352284Sobrien init_resource_info () was invoked before we are called. */ 88452284Sobrien 88552284Sobrienvoid 886132718Skanmark_target_live_regs (rtx insns, rtx target, struct resources *res) 88752284Sobrien{ 88852284Sobrien int b = -1; 88990075Sobrien unsigned int i; 89052284Sobrien struct target_info *tinfo = NULL; 89152284Sobrien rtx insn; 89252284Sobrien rtx jump_insn = 0; 89352284Sobrien rtx jump_target; 89452284Sobrien HARD_REG_SET scratch; 89552284Sobrien struct resources set, needed; 89652284Sobrien 89752284Sobrien /* Handle end of function. */ 89852284Sobrien if (target == 0) 89952284Sobrien { 90052284Sobrien *res = end_of_function_needs; 90152284Sobrien return; 90252284Sobrien } 90352284Sobrien 904169689Skan /* Handle return insn. */ 905169689Skan else if (return_insn_p (target)) 906169689Skan { 907169689Skan *res = end_of_function_needs; 908169689Skan mark_referenced_resources (target, res, 0); 909169689Skan return; 910169689Skan } 911169689Skan 91252284Sobrien /* We have to assume memory is needed, but the CC isn't. */ 91352284Sobrien res->memory = 1; 91452284Sobrien res->volatil = res->unch_memory = 0; 91552284Sobrien res->cc = 0; 91652284Sobrien 91752284Sobrien /* See if we have computed this value already. */ 91852284Sobrien if (target_hash_table != NULL) 91952284Sobrien { 92052284Sobrien for (tinfo = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME]; 92152284Sobrien tinfo; tinfo = tinfo->next) 92252284Sobrien if (tinfo->uid == INSN_UID (target)) 92352284Sobrien break; 92452284Sobrien 92552284Sobrien /* Start by getting the basic block number. If we have saved 92652284Sobrien information, we can get it from there unless the insn at the 92752284Sobrien start of the basic block has been deleted. */ 92852284Sobrien if (tinfo && tinfo->block != -1 929132718Skan && ! INSN_DELETED_P (BB_HEAD (BASIC_BLOCK (tinfo->block)))) 93052284Sobrien b = tinfo->block; 93152284Sobrien } 93252284Sobrien 93352284Sobrien if (b == -1) 93490075Sobrien b = find_basic_block (target, MAX_DELAY_SLOT_LIVE_SEARCH); 93552284Sobrien 93652284Sobrien if (target_hash_table != NULL) 93752284Sobrien { 93852284Sobrien if (tinfo) 93952284Sobrien { 94052284Sobrien /* If the information is up-to-date, use it. Otherwise, we will 94152284Sobrien update it below. */ 94252284Sobrien if (b == tinfo->block && b != -1 && tinfo->bb_tick == bb_ticks[b]) 94352284Sobrien { 94452284Sobrien COPY_HARD_REG_SET (res->regs, tinfo->live_regs); 94552284Sobrien return; 94652284Sobrien } 94752284Sobrien } 94852284Sobrien else 94952284Sobrien { 950117395Skan /* Allocate a place to put our results and chain it into the 95152284Sobrien hash table. */ 952169689Skan tinfo = XNEW (struct target_info); 95352284Sobrien tinfo->uid = INSN_UID (target); 95452284Sobrien tinfo->block = b; 95590075Sobrien tinfo->next 95690075Sobrien = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME]; 95752284Sobrien target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME] = tinfo; 95852284Sobrien } 95952284Sobrien } 96052284Sobrien 96152284Sobrien CLEAR_HARD_REG_SET (pending_dead_regs); 96252284Sobrien 96352284Sobrien /* If we found a basic block, get the live registers from it and update 96452284Sobrien them with anything set or killed between its start and the insn before 96552284Sobrien TARGET. Otherwise, we must assume everything is live. */ 96652284Sobrien if (b != -1) 96752284Sobrien { 968169689Skan regset regs_live = BASIC_BLOCK (b)->il.rtl->global_live_at_start; 96990075Sobrien unsigned int j; 97090075Sobrien unsigned int regno; 97152284Sobrien rtx start_insn, stop_insn; 972169689Skan reg_set_iterator rsi; 97352284Sobrien 97452284Sobrien /* Compute hard regs live at start of block -- this is the real hard regs 97552284Sobrien marked live, plus live pseudo regs that have been renumbered to 97652284Sobrien hard regs. */ 97752284Sobrien 97852284Sobrien REG_SET_TO_HARD_REG_SET (current_live_regs, regs_live); 97952284Sobrien 980169689Skan EXECUTE_IF_SET_IN_REG_SET (regs_live, FIRST_PSEUDO_REGISTER, i, rsi) 981169689Skan { 982169689Skan if (reg_renumber[i] >= 0) 983169689Skan { 984169689Skan regno = reg_renumber[i]; 985169689Skan for (j = regno; 986169689Skan j < regno + hard_regno_nregs[regno][PSEUDO_REGNO_MODE (i)]; 987169689Skan j++) 988169689Skan SET_HARD_REG_BIT (current_live_regs, j); 989169689Skan } 990169689Skan } 99152284Sobrien 99252284Sobrien /* Get starting and ending insn, handling the case where each might 99352284Sobrien be a SEQUENCE. */ 994132718Skan start_insn = (b == 0 ? insns : BB_HEAD (BASIC_BLOCK (b))); 99552284Sobrien stop_insn = target; 99652284Sobrien 997169689Skan if (NONJUMP_INSN_P (start_insn) 99852284Sobrien && GET_CODE (PATTERN (start_insn)) == SEQUENCE) 99952284Sobrien start_insn = XVECEXP (PATTERN (start_insn), 0, 0); 100052284Sobrien 1001169689Skan if (NONJUMP_INSN_P (stop_insn) 100252284Sobrien && GET_CODE (PATTERN (stop_insn)) == SEQUENCE) 100352284Sobrien stop_insn = next_insn (PREV_INSN (stop_insn)); 100452284Sobrien 100552284Sobrien for (insn = start_insn; insn != stop_insn; 100652284Sobrien insn = next_insn_no_annul (insn)) 100752284Sobrien { 100852284Sobrien rtx link; 100952284Sobrien rtx real_insn = insn; 1010117395Skan enum rtx_code code = GET_CODE (insn); 101152284Sobrien 101252284Sobrien /* If this insn is from the target of a branch, it isn't going to 101352284Sobrien be used in the sequel. If it is used in both cases, this 101452284Sobrien test will not be true. */ 1015117395Skan if ((code == INSN || code == JUMP_INSN || code == CALL_INSN) 1016117395Skan && INSN_FROM_TARGET_P (insn)) 101752284Sobrien continue; 101852284Sobrien 101952284Sobrien /* If this insn is a USE made by update_block, we care about the 102052284Sobrien underlying insn. */ 1021117395Skan if (code == INSN && GET_CODE (PATTERN (insn)) == USE 102290075Sobrien && INSN_P (XEXP (PATTERN (insn), 0))) 102352284Sobrien real_insn = XEXP (PATTERN (insn), 0); 102452284Sobrien 1025169689Skan if (CALL_P (real_insn)) 102652284Sobrien { 102752284Sobrien /* CALL clobbers all call-used regs that aren't fixed except 102852284Sobrien sp, ap, and fp. Do this before setting the result of the 102952284Sobrien call live. */ 103090075Sobrien AND_COMPL_HARD_REG_SET (current_live_regs, 103190075Sobrien regs_invalidated_by_call); 103252284Sobrien 103352284Sobrien /* A CALL_INSN sets any global register live, since it may 103452284Sobrien have been modified by the call. */ 103552284Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 103652284Sobrien if (global_regs[i]) 103752284Sobrien SET_HARD_REG_BIT (current_live_regs, i); 103852284Sobrien } 103952284Sobrien 104052284Sobrien /* Mark anything killed in an insn to be deadened at the next 104152284Sobrien label. Ignore USE insns; the only REG_DEAD notes will be for 104252284Sobrien parameters. But they might be early. A CALL_INSN will usually 104352284Sobrien clobber registers used for parameters. It isn't worth bothering 104452284Sobrien with the unlikely case when it won't. */ 1045169689Skan if ((NONJUMP_INSN_P (real_insn) 104652284Sobrien && GET_CODE (PATTERN (real_insn)) != USE 104752284Sobrien && GET_CODE (PATTERN (real_insn)) != CLOBBER) 1048169689Skan || JUMP_P (real_insn) 1049169689Skan || CALL_P (real_insn)) 105052284Sobrien { 105152284Sobrien for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1)) 105252284Sobrien if (REG_NOTE_KIND (link) == REG_DEAD 1053169689Skan && REG_P (XEXP (link, 0)) 105452284Sobrien && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER) 105552284Sobrien { 105690075Sobrien unsigned int first_regno = REGNO (XEXP (link, 0)); 105790075Sobrien unsigned int last_regno 105852284Sobrien = (first_regno 1059169689Skan + hard_regno_nregs[first_regno] 1060169689Skan [GET_MODE (XEXP (link, 0))]); 1061117395Skan 106252284Sobrien for (i = first_regno; i < last_regno; i++) 106352284Sobrien SET_HARD_REG_BIT (pending_dead_regs, i); 106452284Sobrien } 106552284Sobrien 106690075Sobrien note_stores (PATTERN (real_insn), update_live_status, NULL); 106752284Sobrien 106852284Sobrien /* If any registers were unused after this insn, kill them. 106952284Sobrien These notes will always be accurate. */ 107052284Sobrien for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1)) 107152284Sobrien if (REG_NOTE_KIND (link) == REG_UNUSED 1072169689Skan && REG_P (XEXP (link, 0)) 107352284Sobrien && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER) 107452284Sobrien { 107590075Sobrien unsigned int first_regno = REGNO (XEXP (link, 0)); 107690075Sobrien unsigned int last_regno 107752284Sobrien = (first_regno 1078169689Skan + hard_regno_nregs[first_regno] 1079169689Skan [GET_MODE (XEXP (link, 0))]); 1080117395Skan 108152284Sobrien for (i = first_regno; i < last_regno; i++) 108252284Sobrien CLEAR_HARD_REG_BIT (current_live_regs, i); 108352284Sobrien } 108452284Sobrien } 108552284Sobrien 1086169689Skan else if (LABEL_P (real_insn)) 108752284Sobrien { 108852284Sobrien /* A label clobbers the pending dead registers since neither 108952284Sobrien reload nor jump will propagate a value across a label. */ 109052284Sobrien AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs); 109152284Sobrien CLEAR_HARD_REG_SET (pending_dead_regs); 109252284Sobrien } 109352284Sobrien 109452284Sobrien /* The beginning of the epilogue corresponds to the end of the 109552284Sobrien RTL chain when there are no epilogue insns. Certain resources 109652284Sobrien are implicitly required at that point. */ 1097169689Skan else if (NOTE_P (real_insn) 1098117395Skan && NOTE_LINE_NUMBER (real_insn) == NOTE_INSN_EPILOGUE_BEG) 109952284Sobrien IOR_HARD_REG_SET (current_live_regs, start_of_epilogue_needs.regs); 110052284Sobrien } 110152284Sobrien 110252284Sobrien COPY_HARD_REG_SET (res->regs, current_live_regs); 110352284Sobrien if (tinfo != NULL) 110452284Sobrien { 110552284Sobrien tinfo->block = b; 110652284Sobrien tinfo->bb_tick = bb_ticks[b]; 110752284Sobrien } 110852284Sobrien } 110952284Sobrien else 111052284Sobrien /* We didn't find the start of a basic block. Assume everything 111152284Sobrien in use. This should happen only extremely rarely. */ 111252284Sobrien SET_HARD_REG_SET (res->regs); 111352284Sobrien 111452284Sobrien CLEAR_RESOURCE (&set); 111552284Sobrien CLEAR_RESOURCE (&needed); 111652284Sobrien 111752284Sobrien jump_insn = find_dead_or_set_registers (target, res, &jump_target, 0, 111852284Sobrien set, needed); 111952284Sobrien 112052284Sobrien /* If we hit an unconditional branch, we have another way of finding out 112152284Sobrien what is live: we can see what is live at the branch target and include 112290075Sobrien anything used but not set before the branch. We add the live 112390075Sobrien resources found using the test below to those found until now. */ 112452284Sobrien 112552284Sobrien if (jump_insn) 112652284Sobrien { 112752284Sobrien struct resources new_resources; 112852284Sobrien rtx stop_insn = next_active_insn (jump_insn); 112952284Sobrien 113052284Sobrien mark_target_live_regs (insns, next_active_insn (jump_target), 113152284Sobrien &new_resources); 113252284Sobrien CLEAR_RESOURCE (&set); 113352284Sobrien CLEAR_RESOURCE (&needed); 113452284Sobrien 113552284Sobrien /* Include JUMP_INSN in the needed registers. */ 113652284Sobrien for (insn = target; insn != stop_insn; insn = next_active_insn (insn)) 113752284Sobrien { 113852284Sobrien mark_referenced_resources (insn, &needed, 1); 113952284Sobrien 114052284Sobrien COPY_HARD_REG_SET (scratch, needed.regs); 114152284Sobrien AND_COMPL_HARD_REG_SET (scratch, set.regs); 114252284Sobrien IOR_HARD_REG_SET (new_resources.regs, scratch); 114352284Sobrien 114490075Sobrien mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL); 114552284Sobrien } 114652284Sobrien 114790075Sobrien IOR_HARD_REG_SET (res->regs, new_resources.regs); 114852284Sobrien } 114952284Sobrien 115052284Sobrien if (tinfo != NULL) 115152284Sobrien { 115252284Sobrien COPY_HARD_REG_SET (tinfo->live_regs, res->regs); 115352284Sobrien } 115452284Sobrien} 115552284Sobrien 115652284Sobrien/* Initialize the resources required by mark_target_live_regs (). 115752284Sobrien This should be invoked before the first call to mark_target_live_regs. */ 115852284Sobrien 115952284Sobrienvoid 1160132718Skaninit_resource_info (rtx epilogue_insn) 116152284Sobrien{ 116252284Sobrien int i; 116352284Sobrien 116452284Sobrien /* Indicate what resources are required to be valid at the end of the current 116552284Sobrien function. The condition code never is and memory always is. If the 116652284Sobrien frame pointer is needed, it is and so is the stack pointer unless 1167117395Skan EXIT_IGNORE_STACK is nonzero. If the frame pointer is not needed, the 116852284Sobrien stack pointer is. Registers used to return the function value are 116952284Sobrien needed. Registers holding global variables are needed. */ 117052284Sobrien 117152284Sobrien end_of_function_needs.cc = 0; 117252284Sobrien end_of_function_needs.memory = 1; 117352284Sobrien end_of_function_needs.unch_memory = 0; 117452284Sobrien CLEAR_HARD_REG_SET (end_of_function_needs.regs); 117552284Sobrien 117652284Sobrien if (frame_pointer_needed) 117752284Sobrien { 117852284Sobrien SET_HARD_REG_BIT (end_of_function_needs.regs, FRAME_POINTER_REGNUM); 117952284Sobrien#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 118052284Sobrien SET_HARD_REG_BIT (end_of_function_needs.regs, HARD_FRAME_POINTER_REGNUM); 118152284Sobrien#endif 118252284Sobrien if (! EXIT_IGNORE_STACK 118352284Sobrien || current_function_sp_is_unchanging) 118452284Sobrien SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM); 118552284Sobrien } 118652284Sobrien else 118752284Sobrien SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM); 118852284Sobrien 118952284Sobrien if (current_function_return_rtx != 0) 119052284Sobrien mark_referenced_resources (current_function_return_rtx, 119152284Sobrien &end_of_function_needs, 1); 119252284Sobrien 119352284Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 119452284Sobrien if (global_regs[i] 119552284Sobrien#ifdef EPILOGUE_USES 119652284Sobrien || EPILOGUE_USES (i) 119752284Sobrien#endif 119852284Sobrien ) 119952284Sobrien SET_HARD_REG_BIT (end_of_function_needs.regs, i); 120052284Sobrien 120152284Sobrien /* The registers required to be live at the end of the function are 120252284Sobrien represented in the flow information as being dead just prior to 120352284Sobrien reaching the end of the function. For example, the return of a value 120452284Sobrien might be represented by a USE of the return register immediately 120552284Sobrien followed by an unconditional jump to the return label where the 120652284Sobrien return label is the end of the RTL chain. The end of the RTL chain 120752284Sobrien is then taken to mean that the return register is live. 120852284Sobrien 120952284Sobrien This sequence is no longer maintained when epilogue instructions are 121052284Sobrien added to the RTL chain. To reconstruct the original meaning, the 121152284Sobrien start of the epilogue (NOTE_INSN_EPILOGUE_BEG) is regarded as the 121252284Sobrien point where these registers become live (start_of_epilogue_needs). 121352284Sobrien If epilogue instructions are present, the registers set by those 121452284Sobrien instructions won't have been processed by flow. Thus, those 121552284Sobrien registers are additionally required at the end of the RTL chain 121652284Sobrien (end_of_function_needs). */ 121752284Sobrien 121852284Sobrien start_of_epilogue_needs = end_of_function_needs; 121952284Sobrien 122052284Sobrien while ((epilogue_insn = next_nonnote_insn (epilogue_insn))) 1221169689Skan { 1222169689Skan mark_set_resources (epilogue_insn, &end_of_function_needs, 0, 1223169689Skan MARK_SRC_DEST_CALL); 1224169689Skan if (return_insn_p (epilogue_insn)) 1225169689Skan break; 1226169689Skan } 122752284Sobrien 122852284Sobrien /* Allocate and initialize the tables used by mark_target_live_regs. */ 1229169689Skan target_hash_table = XCNEWVEC (struct target_info *, TARGET_HASH_PRIME); 1230169689Skan bb_ticks = XCNEWVEC (int, last_basic_block); 123152284Sobrien} 123252284Sobrien 1233132718Skan/* Free up the resources allocated to mark_target_live_regs (). This 123452284Sobrien should be invoked after the last call to mark_target_live_regs (). */ 123552284Sobrien 123652284Sobrienvoid 1237132718Skanfree_resource_info (void) 123852284Sobrien{ 123952284Sobrien if (target_hash_table != NULL) 124052284Sobrien { 124190075Sobrien int i; 1242117395Skan 1243117395Skan for (i = 0; i < TARGET_HASH_PRIME; ++i) 124490075Sobrien { 124590075Sobrien struct target_info *ti = target_hash_table[i]; 124690075Sobrien 1247117395Skan while (ti) 124890075Sobrien { 124990075Sobrien struct target_info *next = ti->next; 125090075Sobrien free (ti); 125190075Sobrien ti = next; 125290075Sobrien } 125390075Sobrien } 125490075Sobrien 125552284Sobrien free (target_hash_table); 125652284Sobrien target_hash_table = NULL; 125752284Sobrien } 125852284Sobrien 125952284Sobrien if (bb_ticks != NULL) 126052284Sobrien { 126152284Sobrien free (bb_ticks); 126252284Sobrien bb_ticks = NULL; 126352284Sobrien } 126452284Sobrien} 126552284Sobrien 126652284Sobrien/* Clear any hashed information that we have stored for INSN. */ 126752284Sobrien 126852284Sobrienvoid 1269132718Skanclear_hashed_info_for_insn (rtx insn) 127052284Sobrien{ 127152284Sobrien struct target_info *tinfo; 1272117395Skan 127352284Sobrien if (target_hash_table != NULL) 127452284Sobrien { 127552284Sobrien for (tinfo = target_hash_table[INSN_UID (insn) % TARGET_HASH_PRIME]; 127652284Sobrien tinfo; tinfo = tinfo->next) 127752284Sobrien if (tinfo->uid == INSN_UID (insn)) 127852284Sobrien break; 127952284Sobrien 128052284Sobrien if (tinfo) 128152284Sobrien tinfo->block = -1; 128252284Sobrien } 128352284Sobrien} 128452284Sobrien 128552284Sobrien/* Increment the tick count for the basic block that contains INSN. */ 128652284Sobrien 128752284Sobrienvoid 1288132718Skanincr_ticks_for_insn (rtx insn) 128952284Sobrien{ 129090075Sobrien int b = find_basic_block (insn, MAX_DELAY_SLOT_LIVE_SEARCH); 129152284Sobrien 129252284Sobrien if (b != -1) 129352284Sobrien bb_ticks[b]++; 129452284Sobrien} 129552284Sobrien 129652284Sobrien/* Add TRIAL to the set of resources used at the end of the current 129790075Sobrien function. */ 129852284Sobrienvoid 1299132718Skanmark_end_of_function_resources (rtx trial, int include_delayed_effects) 130052284Sobrien{ 130152284Sobrien mark_referenced_resources (trial, &end_of_function_needs, 130252284Sobrien include_delayed_effects); 130352284Sobrien} 1304