118334Speter/* Data flow analysis for GNU compiler. 272562Sobrien Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3169689Skan 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, 4169689Skan Inc. 518334Speter 690075SobrienThis file is part of GCC. 718334Speter 890075SobrienGCC is free software; you can redistribute it and/or modify it under 990075Sobrienthe terms of the GNU General Public License as published by the Free 1090075SobrienSoftware Foundation; either version 2, or (at your option) any later 1190075Sobrienversion. 1218334Speter 1390075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1490075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1590075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1690075Sobrienfor more details. 1718334Speter 1818334SpeterYou should have received a copy of the GNU General Public License 1990075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 20169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 21169689Skan02110-1301, USA. */ 2218334Speter 2352284Sobrien/* This file contains the data flow analysis pass of the compiler. It 2452284Sobrien computes data flow information which tells combine_instructions 2552284Sobrien which insns to consider combining and controls register allocation. 2618334Speter 2752284Sobrien Additional data flow information that is too bulky to record is 2852284Sobrien generated during the analysis, and is used at that time to create 2952284Sobrien autoincrement and autodecrement addressing. 3018334Speter 3118334Speter The first step is dividing the function into basic blocks. 3218334Speter find_basic_blocks does this. Then life_analysis determines 3318334Speter where each register is live and where it is dead. 3418334Speter 3518334Speter ** find_basic_blocks ** 3618334Speter 3752284Sobrien find_basic_blocks divides the current function's rtl into basic 3852284Sobrien blocks and constructs the CFG. The blocks are recorded in the 3952284Sobrien basic_block_info array; the CFG exists in the edge structures 4052284Sobrien referenced by the blocks. 4118334Speter 4252284Sobrien find_basic_blocks also finds any unreachable loops and deletes them. 4318334Speter 4418334Speter ** life_analysis ** 4518334Speter 4618334Speter life_analysis is called immediately after find_basic_blocks. 4718334Speter It uses the basic block information to determine where each 4818334Speter hard or pseudo register is live. 4918334Speter 5018334Speter ** live-register info ** 5118334Speter 5218334Speter The information about where each register is live is in two parts: 5352284Sobrien the REG_NOTES of insns, and the vector basic_block->global_live_at_start. 5418334Speter 5552284Sobrien basic_block->global_live_at_start has an element for each basic 5652284Sobrien block, and the element is a bit-vector with a bit for each hard or 5752284Sobrien pseudo register. The bit is 1 if the register is live at the 5852284Sobrien beginning of the basic block. 5918334Speter 6090075Sobrien Two types of elements can be added to an insn's REG_NOTES. 6118334Speter A REG_DEAD note is added to an insn's REG_NOTES for any register 6218334Speter that meets both of two conditions: The value in the register is not 6318334Speter needed in subsequent insns and the insn does not replace the value in 6418334Speter the register (in the case of multi-word hard registers, the value in 6518334Speter each register must be replaced by the insn to avoid a REG_DEAD note). 6618334Speter 6718334Speter In the vast majority of cases, an object in a REG_DEAD note will be 6818334Speter used somewhere in the insn. The (rare) exception to this is if an 6918334Speter insn uses a multi-word hard register and only some of the registers are 7018334Speter needed in subsequent insns. In that case, REG_DEAD notes will be 7118334Speter provided for those hard registers that are not subsequently needed. 7218334Speter Partial REG_DEAD notes of this type do not occur when an insn sets 7318334Speter only some of the hard registers used in such a multi-word operand; 7418334Speter omitting REG_DEAD notes for objects stored in an insn is optional and 7518334Speter the desire to do so does not justify the complexity of the partial 7618334Speter REG_DEAD notes. 7718334Speter 7818334Speter REG_UNUSED notes are added for each register that is set by the insn 7918334Speter but is unused subsequently (if every register set by the insn is unused 8018334Speter and the insn does not reference memory or have some other side-effect, 8118334Speter the insn is deleted instead). If only part of a multi-word hard 8218334Speter register is used in a subsequent insn, REG_UNUSED notes are made for 8318334Speter the parts that will not be used. 8418334Speter 8518334Speter To determine which registers are live after any insn, one can 8618334Speter start from the beginning of the basic block and scan insns, noting 8718334Speter which registers are set by each insn and which die there. 8818334Speter 8918334Speter ** Other actions of life_analysis ** 9018334Speter 9118334Speter life_analysis sets up the LOG_LINKS fields of insns because the 9218334Speter information needed to do so is readily available. 9318334Speter 9418334Speter life_analysis deletes insns whose only effect is to store a value 9518334Speter that is never used. 9618334Speter 9718334Speter life_analysis notices cases where a reference to a register as 9818334Speter a memory address can be combined with a preceding or following 9918334Speter incrementation or decrementation of the register. The separate 10018334Speter instruction to increment or decrement is deleted and the address 10118334Speter is changed to a POST_INC or similar rtx. 10218334Speter 10318334Speter Each time an incrementing or decrementing address is created, 10418334Speter a REG_INC element is added to the insn's REG_NOTES list. 10518334Speter 10618334Speter life_analysis fills in certain vectors containing information about 10790075Sobrien register usage: REG_N_REFS, REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH, 108161651Skan REG_N_CALLS_CROSSED, REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK. 10952284Sobrien 11052284Sobrien life_analysis sets current_function_sp_is_unchanging if the function 11152284Sobrien doesn't modify the stack pointer. */ 11252284Sobrien 11390075Sobrien/* TODO: 11452284Sobrien 11552284Sobrien Split out from life_analysis: 116169689Skan - local property discovery 11752284Sobrien - global property computation 11852284Sobrien - log links creation 11952284Sobrien - pre/post modify transformation 12052284Sobrien*/ 12118334Speter 12218334Speter#include "config.h" 12350397Sobrien#include "system.h" 124132718Skan#include "coretypes.h" 125132718Skan#include "tm.h" 12690075Sobrien#include "tree.h" 12718334Speter#include "rtl.h" 12890075Sobrien#include "tm_p.h" 12990075Sobrien#include "hard-reg-set.h" 13018334Speter#include "basic-block.h" 13118334Speter#include "insn-config.h" 13218334Speter#include "regs.h" 13318334Speter#include "flags.h" 13418334Speter#include "output.h" 13590075Sobrien#include "function.h" 13650397Sobrien#include "except.h" 13750397Sobrien#include "toplev.h" 13852284Sobrien#include "recog.h" 13990075Sobrien#include "expr.h" 14090075Sobrien#include "timevar.h" 14118334Speter 14218334Speter#include "obstack.h" 14390075Sobrien#include "splay-tree.h" 144169689Skan#include "tree-pass.h" 145169689Skan#include "params.h" 14690075Sobrien 14790075Sobrien#ifndef HAVE_epilogue 14890075Sobrien#define HAVE_epilogue 0 14990075Sobrien#endif 15090075Sobrien#ifndef HAVE_prologue 15190075Sobrien#define HAVE_prologue 0 15290075Sobrien#endif 15390075Sobrien#ifndef HAVE_sibcall_epilogue 15490075Sobrien#define HAVE_sibcall_epilogue 0 15590075Sobrien#endif 15652284Sobrien 15790075Sobrien#ifndef EPILOGUE_USES 15890075Sobrien#define EPILOGUE_USES(REGNO) 0 15990075Sobrien#endif 16096263Sobrien#ifndef EH_USES 16196263Sobrien#define EH_USES(REGNO) 0 16296263Sobrien#endif 16350397Sobrien 16490075Sobrien#ifdef HAVE_conditional_execution 16590075Sobrien#ifndef REVERSE_CONDEXEC_PREDICATES_P 166169689Skan#define REVERSE_CONDEXEC_PREDICATES_P(x, y) \ 167169689Skan (GET_CODE ((x)) == reversed_comparison_code ((y), NULL)) 16890075Sobrien#endif 16990075Sobrien#endif 17050397Sobrien 171169689Skan/* This is the maximum number of times we process any given block if the 172169689Skan latest loop depth count is smaller than this number. Only used for the 173169689Skan failure strategy to avoid infinite loops in calculate_global_regs_live. */ 174169689Skan#define MAX_LIVENESS_ROUNDS 20 175169689Skan 17652284Sobrien/* Nonzero if the second flow pass has completed. */ 17752284Sobrienint flow2_completed; 17818334Speter 17918334Speter/* Maximum register number used in this function, plus one. */ 18018334Speter 18118334Speterint max_regno; 18218334Speter 18350397Sobrien/* Indexed by n, giving various register information */ 18418334Speter 185169689SkanVEC(reg_info_p,heap) *reg_n_info; 18618334Speter 18718334Speter/* Regset of regs live when calls to `setjmp'-like functions happen. */ 18852284Sobrien/* ??? Does this exist only for the setjmp-clobbered warning message? */ 18918334Speter 190169689Skanstatic regset regs_live_at_setjmp; 19118334Speter 19218334Speter/* List made of EXPR_LIST rtx's which gives pairs of pseudo registers 19318334Speter that have to go in the same hard reg. 19418334Speter The first two regs in the list are a pair, and the next two 19518334Speter are another pair, etc. */ 19618334Speterrtx regs_may_share; 19718334Speter 19818334Speter/* Set of registers that may be eliminable. These are handled specially 19918334Speter in updating regs_ever_live. */ 20018334Speter 20118334Speterstatic HARD_REG_SET elim_reg_set; 20218334Speter 20390075Sobrien/* Holds information for tracking conditional register life information. */ 20490075Sobrienstruct reg_cond_life_info 20590075Sobrien{ 20690075Sobrien /* A boolean expression of conditions under which a register is dead. */ 20790075Sobrien rtx condition; 20890075Sobrien /* Conditions under which a register is dead at the basic block end. */ 20990075Sobrien rtx orig_condition; 21052284Sobrien 21190075Sobrien /* A boolean expression of conditions under which a register has been 21290075Sobrien stored into. */ 21390075Sobrien rtx stores; 21452284Sobrien 21590075Sobrien /* ??? Could store mask of bytes that are dead, so that we could finally 21690075Sobrien track lifetimes of multi-word registers accessed via subregs. */ 21790075Sobrien}; 21852284Sobrien 21990075Sobrien/* For use in communicating between propagate_block and its subroutines. 22090075Sobrien Holds all information needed to compute life and def-use information. */ 22152284Sobrien 22290075Sobrienstruct propagate_block_info 22318334Speter{ 22490075Sobrien /* The basic block we're considering. */ 22590075Sobrien basic_block bb; 22618334Speter 22790075Sobrien /* Bit N is set if register N is conditionally or unconditionally live. */ 22890075Sobrien regset reg_live; 22918334Speter 23090075Sobrien /* Bit N is set if register N is set this insn. */ 23190075Sobrien regset new_set; 23218334Speter 23390075Sobrien /* Element N is the next insn that uses (hard or pseudo) register N 23490075Sobrien within the current basic block; or zero, if there is no such insn. */ 23590075Sobrien rtx *reg_next_use; 23618334Speter 23790075Sobrien /* Contains a list of all the MEMs we are tracking for dead store 23890075Sobrien elimination. */ 23990075Sobrien rtx mem_set_list; 24050397Sobrien 24190075Sobrien /* If non-null, record the set of registers set unconditionally in the 24290075Sobrien basic block. */ 24390075Sobrien regset local_set; 24450397Sobrien 24590075Sobrien /* If non-null, record the set of registers set conditionally in the 24690075Sobrien basic block. */ 24790075Sobrien regset cond_local_set; 24850397Sobrien 24990075Sobrien#ifdef HAVE_conditional_execution 25090075Sobrien /* Indexed by register number, holds a reg_cond_life_info for each 25190075Sobrien register that is not unconditionally live or dead. */ 25290075Sobrien splay_tree reg_cond_dead; 25350397Sobrien 25490075Sobrien /* Bit N is set if register N is in an expression in reg_cond_dead. */ 25590075Sobrien regset reg_cond_reg; 25618334Speter#endif 25718334Speter 25890075Sobrien /* The length of mem_set_list. */ 25990075Sobrien int mem_set_list_len; 26018334Speter 261117395Skan /* Nonzero if the value of CC0 is live. */ 26290075Sobrien int cc0_live; 26318334Speter 264132718Skan /* Flags controlling the set of information propagate_block collects. */ 26590075Sobrien int flags; 266169689Skan /* Index of instruction being processed. */ 267169689Skan int insn_num; 26890075Sobrien}; 26952284Sobrien 270117395Skan/* Number of dead insns removed. */ 271117395Skanstatic int ndead; 272117395Skan 273169689Skan/* When PROP_REG_INFO set, array contains pbi->insn_num of instruction 274169689Skan where given register died. When the register is marked alive, we use the 275169689Skan information to compute amount of instructions life range cross. 276169689Skan (remember, we are walking backward). This can be computed as current 277169689Skan pbi->insn_num - reg_deaths[regno]. 278169689Skan At the end of processing each basic block, the remaining live registers 279169689Skan are inspected and live ranges are increased same way so liverange of global 280169689Skan registers are computed correctly. 281169689Skan 282169689Skan The array is maintained clear for dead registers, so it can be safely reused 283169689Skan for next basic block without expensive memset of the whole array after 284169689Skan reseting pbi->insn_num to 0. */ 28552284Sobrien 286169689Skanstatic int *reg_deaths; 287169689Skan 28890075Sobrien/* Forward declarations */ 289132718Skanstatic int verify_wide_reg_1 (rtx *, void *); 290132718Skanstatic void verify_wide_reg (int, basic_block); 291132718Skanstatic void verify_local_live_at_start (regset, basic_block); 292132718Skanstatic void notice_stack_pointer_modification_1 (rtx, rtx, void *); 293169689Skanstatic void notice_stack_pointer_modification (void); 294132718Skanstatic void mark_reg (rtx, void *); 295132718Skanstatic void mark_regs_live_at_end (regset); 296132718Skanstatic void calculate_global_regs_live (sbitmap, sbitmap, int); 297132718Skanstatic void propagate_block_delete_insn (rtx); 298132718Skanstatic rtx propagate_block_delete_libcall (rtx, rtx); 299132718Skanstatic int insn_dead_p (struct propagate_block_info *, rtx, int, rtx); 300132718Skanstatic int libcall_dead_p (struct propagate_block_info *, rtx, rtx); 301132718Skanstatic void mark_set_regs (struct propagate_block_info *, rtx, rtx); 302132718Skanstatic void mark_set_1 (struct propagate_block_info *, enum rtx_code, rtx, 303132718Skan rtx, rtx, int); 304132718Skanstatic int find_regno_partial (rtx *, void *); 30552284Sobrien 30690075Sobrien#ifdef HAVE_conditional_execution 307132718Skanstatic int mark_regno_cond_dead (struct propagate_block_info *, int, rtx); 308132718Skanstatic void free_reg_cond_life_info (splay_tree_value); 309132718Skanstatic int flush_reg_cond_reg_1 (splay_tree_node, void *); 310132718Skanstatic void flush_reg_cond_reg (struct propagate_block_info *, int); 311132718Skanstatic rtx elim_reg_cond (rtx, unsigned int); 312132718Skanstatic rtx ior_reg_cond (rtx, rtx, int); 313132718Skanstatic rtx not_reg_cond (rtx); 314132718Skanstatic rtx and_reg_cond (rtx, rtx, int); 31552284Sobrien#endif 31690075Sobrien#ifdef AUTO_INC_DEC 317132718Skanstatic void attempt_auto_inc (struct propagate_block_info *, rtx, rtx, rtx, 318132718Skan rtx, rtx); 319132718Skanstatic void find_auto_inc (struct propagate_block_info *, rtx, rtx); 320132718Skanstatic int try_pre_increment_1 (struct propagate_block_info *, rtx); 321132718Skanstatic int try_pre_increment (rtx, rtx, HOST_WIDE_INT); 32290075Sobrien#endif 323132718Skanstatic void mark_used_reg (struct propagate_block_info *, rtx, rtx, rtx); 324132718Skanstatic void mark_used_regs (struct propagate_block_info *, rtx, rtx, rtx); 325132718Skanvoid debug_flow_info (void); 326132718Skanstatic void add_to_mem_set_list (struct propagate_block_info *, rtx); 327132718Skanstatic int invalidate_mems_from_autoinc (rtx *, void *); 328132718Skanstatic void invalidate_mems_from_set (struct propagate_block_info *, rtx); 329132718Skanstatic void clear_log_links (sbitmap); 330132718Skanstatic int count_or_remove_death_notes_bb (basic_block, int); 331169689Skanstatic void allocate_bb_life_data (void); 33290075Sobrien 33390075Sobrien/* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK 33490075Sobrien note associated with the BLOCK. */ 33552284Sobrien 33690075Sobrienrtx 337132718Skanfirst_insn_after_basic_block_note (basic_block block) 33890075Sobrien{ 33990075Sobrien rtx insn; 34052284Sobrien 34190075Sobrien /* Get the first instruction in the block. */ 342132718Skan insn = BB_HEAD (block); 34352284Sobrien 34490075Sobrien if (insn == NULL_RTX) 34590075Sobrien return NULL_RTX; 346169689Skan if (LABEL_P (insn)) 34790075Sobrien insn = NEXT_INSN (insn); 348169689Skan gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn)); 34952284Sobrien 35090075Sobrien return NEXT_INSN (insn); 35152284Sobrien} 35290075Sobrien 353169689Skan/* Perform data flow analysis for the whole control flow graph. 354169689Skan FLAGS is a set of PROP_* flags to be used in accumulating flow info. */ 35552284Sobrien 35690075Sobrienvoid 357169689Skanlife_analysis (int flags) 35852284Sobrien{ 35990075Sobrien#ifdef ELIMINABLE_REGS 36090075Sobrien int i; 36190075Sobrien static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS; 36290075Sobrien#endif 36352284Sobrien 36490075Sobrien /* Record which registers will be eliminated. We use this in 36590075Sobrien mark_used_regs. */ 36652284Sobrien 36790075Sobrien CLEAR_HARD_REG_SET (elim_reg_set); 36852284Sobrien 36990075Sobrien#ifdef ELIMINABLE_REGS 37090075Sobrien for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++) 37190075Sobrien SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from); 37290075Sobrien#else 37390075Sobrien SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM); 37490075Sobrien#endif 37552284Sobrien 376117395Skan 377117395Skan#ifdef CANNOT_CHANGE_MODE_CLASS 378132718Skan if (flags & PROP_REG_INFO) 379146895Skan init_subregs_of_mode (); 380117395Skan#endif 381117395Skan 38290075Sobrien if (! optimize) 38390075Sobrien flags &= ~(PROP_LOG_LINKS | PROP_AUTOINC | PROP_ALLOW_CFG_CHANGES); 38452284Sobrien 38590075Sobrien /* The post-reload life analysis have (on a global basis) the same 38690075Sobrien registers live as was computed by reload itself. elimination 38790075Sobrien Otherwise offsets and such may be incorrect. 38852284Sobrien 38990075Sobrien Reload will make some registers as live even though they do not 39090075Sobrien appear in the rtl. 39152284Sobrien 39290075Sobrien We don't want to create new auto-incs after reload, since they 39390075Sobrien are unlikely to be useful and can cause problems with shared 39490075Sobrien stack slots. */ 39590075Sobrien if (reload_completed) 39690075Sobrien flags &= ~(PROP_REG_INFO | PROP_AUTOINC); 39752284Sobrien 39890075Sobrien /* We want alias analysis information for local dead store elimination. */ 399117395Skan if (optimize && (flags & PROP_SCAN_DEAD_STORES)) 40090075Sobrien init_alias_analysis (); 40152284Sobrien 40290075Sobrien /* Always remove no-op moves. Do this before other processing so 40390075Sobrien that we don't have to keep re-scanning them. */ 404169689Skan delete_noop_moves (); 40552284Sobrien 40690075Sobrien /* Some targets can emit simpler epilogues if they know that sp was 40790075Sobrien not ever modified during the function. After reload, of course, 40890075Sobrien we've already emitted the epilogue so there's no sense searching. */ 40990075Sobrien if (! reload_completed) 410169689Skan notice_stack_pointer_modification (); 41152284Sobrien 41290075Sobrien /* Allocate and zero out data structures that will record the 41390075Sobrien data from lifetime analysis. */ 41490075Sobrien allocate_reg_life_data (); 41590075Sobrien allocate_bb_life_data (); 41652284Sobrien 41790075Sobrien /* Find the set of registers live on function exit. */ 418169689Skan mark_regs_live_at_end (EXIT_BLOCK_PTR->il.rtl->global_live_at_start); 41952284Sobrien 42090075Sobrien /* "Update" life info from zero. It'd be nice to begin the 42190075Sobrien relaxation with just the exit and noreturn blocks, but that set 42290075Sobrien is not immediately handy. */ 42352284Sobrien 42490075Sobrien if (flags & PROP_REG_INFO) 425132718Skan { 426132718Skan memset (regs_ever_live, 0, sizeof (regs_ever_live)); 427132718Skan memset (regs_asm_clobbered, 0, sizeof (regs_asm_clobbered)); 428132718Skan } 42990075Sobrien update_life_info (NULL, UPDATE_LIFE_GLOBAL, flags); 430169689Skan if (reg_deaths) 431169689Skan { 432169689Skan free (reg_deaths); 433169689Skan reg_deaths = NULL; 434169689Skan } 43552284Sobrien 43690075Sobrien /* Clean up. */ 437117395Skan if (optimize && (flags & PROP_SCAN_DEAD_STORES)) 43890075Sobrien end_alias_analysis (); 43952284Sobrien 440169689Skan if (dump_file) 441169689Skan dump_flow_info (dump_file, dump_flags); 44252284Sobrien 443169689Skan /* Removing dead insns should have made jumptables really dead. */ 44490075Sobrien delete_dead_jumptables (); 44590075Sobrien} 44652284Sobrien 44790075Sobrien/* A subroutine of verify_wide_reg, called through for_each_rtx. 44890075Sobrien Search for REGNO. If found, return 2 if it is not wider than 44990075Sobrien word_mode. */ 45052284Sobrien 45190075Sobrienstatic int 452132718Skanverify_wide_reg_1 (rtx *px, void *pregno) 45390075Sobrien{ 45490075Sobrien rtx x = *px; 45590075Sobrien unsigned int regno = *(int *) pregno; 45652284Sobrien 457169689Skan if (REG_P (x) && REGNO (x) == regno) 45852284Sobrien { 45990075Sobrien if (GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD) 46090075Sobrien return 2; 46190075Sobrien return 1; 46252284Sobrien } 46390075Sobrien return 0; 46452284Sobrien} 46552284Sobrien 46690075Sobrien/* A subroutine of verify_local_live_at_start. Search through insns 46790075Sobrien of BB looking for register REGNO. */ 46852284Sobrien 46918334Speterstatic void 470132718Skanverify_wide_reg (int regno, basic_block bb) 47118334Speter{ 472132718Skan rtx head = BB_HEAD (bb), end = BB_END (bb); 47318334Speter 47490075Sobrien while (1) 47552284Sobrien { 47690075Sobrien if (INSN_P (head)) 47752284Sobrien { 47890075Sobrien int r = for_each_rtx (&PATTERN (head), verify_wide_reg_1, ®no); 47990075Sobrien if (r == 1) 48090075Sobrien return; 48190075Sobrien if (r == 2) 48290075Sobrien break; 48352284Sobrien } 48490075Sobrien if (head == end) 48590075Sobrien break; 48690075Sobrien head = NEXT_INSN (head); 48752284Sobrien } 488169689Skan if (dump_file) 48952284Sobrien { 490169689Skan fprintf (dump_file, "Register %d died unexpectedly.\n", regno); 491169689Skan dump_bb (bb, dump_file, 0); 49252284Sobrien } 493169689Skan internal_error ("internal consistency failure"); 49490075Sobrien} 49518334Speter 49690075Sobrien/* A subroutine of update_life_info. Verify that there are no untoward 49790075Sobrien changes in live_at_start during a local update. */ 49852284Sobrien 49952284Sobrienstatic void 500132718Skanverify_local_live_at_start (regset new_live_at_start, basic_block bb) 50152284Sobrien{ 50290075Sobrien if (reload_completed) 50318334Speter { 50490075Sobrien /* After reload, there are no pseudos, nor subregs of multi-word 50590075Sobrien registers. The regsets should exactly match. */ 506169689Skan if (! REG_SET_EQUAL_P (new_live_at_start, 507169689Skan bb->il.rtl->global_live_at_start)) 50852284Sobrien { 509169689Skan if (dump_file) 51090075Sobrien { 511169689Skan fprintf (dump_file, 51290075Sobrien "live_at_start mismatch in bb %d, aborting\nNew:\n", 51390075Sobrien bb->index); 514169689Skan debug_bitmap_file (dump_file, new_live_at_start); 515169689Skan fputs ("Old:\n", dump_file); 516169689Skan dump_bb (bb, dump_file, 0); 51790075Sobrien } 518169689Skan internal_error ("internal consistency failure"); 51952284Sobrien } 52052284Sobrien } 52190075Sobrien else 52290075Sobrien { 523169689Skan unsigned i; 524169689Skan reg_set_iterator rsi; 52550397Sobrien 52690075Sobrien /* Find the set of changed registers. */ 527169689Skan XOR_REG_SET (new_live_at_start, bb->il.rtl->global_live_at_start); 52852284Sobrien 529169689Skan EXECUTE_IF_SET_IN_REG_SET (new_live_at_start, 0, i, rsi) 53018334Speter { 531117395Skan /* No registers should die. */ 532169689Skan if (REGNO_REG_SET_P (bb->il.rtl->global_live_at_start, i)) 53390075Sobrien { 534169689Skan if (dump_file) 53590075Sobrien { 536169689Skan fprintf (dump_file, 53790075Sobrien "Register %d died unexpectedly.\n", i); 538169689Skan dump_bb (bb, dump_file, 0); 53990075Sobrien } 540169689Skan internal_error ("internal consistency failure"); 54190075Sobrien } 542117395Skan /* Verify that the now-live register is wider than word_mode. */ 54390075Sobrien verify_wide_reg (i, bb); 544169689Skan } 54552284Sobrien } 54690075Sobrien} 54752284Sobrien 54890075Sobrien/* Updates life information starting with the basic blocks set in BLOCKS. 54990075Sobrien If BLOCKS is null, consider it to be the universal set. 55052284Sobrien 551132718Skan If EXTENT is UPDATE_LIFE_LOCAL, such as after splitting or peepholing, 55290075Sobrien we are only expecting local modifications to basic blocks. If we find 55390075Sobrien extra registers live at the beginning of a block, then we either killed 55490075Sobrien useful data, or we have a broken split that wants data not provided. 55590075Sobrien If we find registers removed from live_at_start, that means we have 55690075Sobrien a broken peephole that is killing a register it shouldn't. 55752284Sobrien 55890075Sobrien ??? This is not true in one situation -- when a pre-reload splitter 55990075Sobrien generates subregs of a multi-word pseudo, current life analysis will 56090075Sobrien lose the kill. So we _can_ have a pseudo go live. How irritating. 56152284Sobrien 562132718Skan It is also not true when a peephole decides that it doesn't need one 563132718Skan or more of the inputs. 564132718Skan 56590075Sobrien Including PROP_REG_INFO does not properly refresh regs_ever_live 56690075Sobrien unless the caller resets it to zero. */ 56752284Sobrien 568117395Skanint 569169689Skanupdate_life_info (sbitmap blocks, enum update_life_extent extent, 570169689Skan int prop_flags) 57152284Sobrien{ 57290075Sobrien regset tmp; 573169689Skan unsigned i = 0; 57496263Sobrien int stabilized_prop_flags = prop_flags; 575117395Skan basic_block bb; 57652284Sobrien 577169689Skan tmp = ALLOC_REG_SET (®_obstack); 578117395Skan ndead = 0; 57952284Sobrien 580169689Skan if ((prop_flags & PROP_REG_INFO) && !reg_deaths) 581169689Skan reg_deaths = XCNEWVEC (int, max_regno); 582169689Skan 58390075Sobrien timevar_push ((extent == UPDATE_LIFE_LOCAL || blocks) 58490075Sobrien ? TV_LIFE_UPDATE : TV_LIFE); 58552284Sobrien 58690075Sobrien /* Changes to the CFG are only allowed when 58790075Sobrien doing a global update for the entire CFG. */ 588169689Skan gcc_assert (!(prop_flags & PROP_ALLOW_CFG_CHANGES) 589169689Skan || (extent != UPDATE_LIFE_LOCAL && !blocks)); 59052284Sobrien 59190075Sobrien /* For a global update, we go through the relaxation process again. */ 59290075Sobrien if (extent != UPDATE_LIFE_LOCAL) 59390075Sobrien { 59490075Sobrien for ( ; ; ) 59518334Speter { 59690075Sobrien int changed = 0; 59718334Speter 59890075Sobrien calculate_global_regs_live (blocks, blocks, 59990075Sobrien prop_flags & (PROP_SCAN_DEAD_CODE 600117395Skan | PROP_SCAN_DEAD_STORES 60190075Sobrien | PROP_ALLOW_CFG_CHANGES)); 60252284Sobrien 60390075Sobrien if ((prop_flags & (PROP_KILL_DEAD_CODE | PROP_ALLOW_CFG_CHANGES)) 60490075Sobrien != (PROP_KILL_DEAD_CODE | PROP_ALLOW_CFG_CHANGES)) 60590075Sobrien break; 60652284Sobrien 60790075Sobrien /* Removing dead code may allow the CFG to be simplified which 60890075Sobrien in turn may allow for further dead code detection / removal. */ 609117395Skan FOR_EACH_BB_REVERSE (bb) 61018334Speter { 611169689Skan COPY_REG_SET (tmp, bb->il.rtl->global_live_at_end); 61290075Sobrien changed |= propagate_block (bb, tmp, NULL, NULL, 61390075Sobrien prop_flags & (PROP_SCAN_DEAD_CODE 614117395Skan | PROP_SCAN_DEAD_STORES 61590075Sobrien | PROP_KILL_DEAD_CODE)); 61652284Sobrien } 61752284Sobrien 61896263Sobrien /* Don't pass PROP_SCAN_DEAD_CODE or PROP_KILL_DEAD_CODE to 61996263Sobrien subsequent propagate_block calls, since removing or acting as 62096263Sobrien removing dead code can affect global register liveness, which 62196263Sobrien is supposed to be finalized for this call after this loop. */ 62296263Sobrien stabilized_prop_flags 623117395Skan &= ~(PROP_SCAN_DEAD_CODE | PROP_SCAN_DEAD_STORES 624117395Skan | PROP_KILL_DEAD_CODE); 62596263Sobrien 62696263Sobrien if (! changed) 62790075Sobrien break; 62896263Sobrien 62996263Sobrien /* We repeat regardless of what cleanup_cfg says. If there were 63096263Sobrien instructions deleted above, that might have been only a 631169689Skan partial improvement (see PARAM_MAX_FLOW_MEMORY_LOCATIONS usage). 63296263Sobrien Further improvement may be possible. */ 63396263Sobrien cleanup_cfg (CLEANUP_EXPENSIVE); 634132718Skan 635132718Skan /* Zap the life information from the last round. If we don't 636132718Skan do this, we can wind up with registers that no longer appear 637169689Skan in the code being marked live at entry. */ 638132718Skan FOR_EACH_BB (bb) 639132718Skan { 640169689Skan CLEAR_REG_SET (bb->il.rtl->global_live_at_start); 641169689Skan CLEAR_REG_SET (bb->il.rtl->global_live_at_end); 642132718Skan } 64318334Speter } 64418334Speter 64590075Sobrien /* If asked, remove notes from the blocks we'll update. */ 64690075Sobrien if (extent == UPDATE_LIFE_GLOBAL_RM_NOTES) 647169689Skan count_or_remove_death_notes (blocks, 648169689Skan prop_flags & PROP_POST_REGSTACK ? -1 : 1); 64990075Sobrien } 650169689Skan else 651169689Skan { 652169689Skan /* FIXME: This can go when the dataflow branch has been merged in. */ 653169689Skan /* For a local update, if we are creating new REG_DEAD notes, then we 654169689Skan must delete the old ones first to avoid conflicts if they are 655169689Skan different. */ 656169689Skan if (prop_flags & PROP_DEATH_NOTES) 657169689Skan count_or_remove_death_notes (blocks, 658169689Skan prop_flags & PROP_POST_REGSTACK ? -1 : 1); 659169689Skan } 660169689Skan 66152284Sobrien 662117395Skan /* Clear log links in case we are asked to (re)compute them. */ 663117395Skan if (prop_flags & PROP_LOG_LINKS) 664117395Skan clear_log_links (blocks); 665117395Skan 66690075Sobrien if (blocks) 66790075Sobrien { 668169689Skan sbitmap_iterator sbi; 669169689Skan 670169689Skan EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i, sbi) 67118334Speter { 672117395Skan bb = BASIC_BLOCK (i); 673169689Skan if (bb) 674169689Skan { 675169689Skan /* The bitmap may be flawed in that one of the basic 676169689Skan blocks may have been deleted before you get here. */ 677169689Skan COPY_REG_SET (tmp, bb->il.rtl->global_live_at_end); 678169689Skan propagate_block (bb, tmp, NULL, NULL, stabilized_prop_flags); 679169689Skan 680169689Skan if (extent == UPDATE_LIFE_LOCAL) 681169689Skan verify_local_live_at_start (tmp, bb); 682169689Skan } 683169689Skan }; 68490075Sobrien } 68590075Sobrien else 68690075Sobrien { 687117395Skan FOR_EACH_BB_REVERSE (bb) 68890075Sobrien { 689169689Skan COPY_REG_SET (tmp, bb->il.rtl->global_live_at_end); 69052284Sobrien 69196263Sobrien propagate_block (bb, tmp, NULL, NULL, stabilized_prop_flags); 69296263Sobrien 69390075Sobrien if (extent == UPDATE_LIFE_LOCAL) 69490075Sobrien verify_local_live_at_start (tmp, bb); 69518334Speter } 69652284Sobrien } 69718334Speter 69890075Sobrien FREE_REG_SET (tmp); 69952284Sobrien 70090075Sobrien if (prop_flags & PROP_REG_INFO) 70190075Sobrien { 702169689Skan reg_set_iterator rsi; 703169689Skan 70490075Sobrien /* The only pseudos that are live at the beginning of the function 70590075Sobrien are those that were not set anywhere in the function. local-alloc 70690075Sobrien doesn't know how to handle these correctly, so mark them as not 70790075Sobrien local to any one basic block. */ 708169689Skan EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->il.rtl->global_live_at_end, 709169689Skan FIRST_PSEUDO_REGISTER, i, rsi) 710169689Skan REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; 71152284Sobrien 71290075Sobrien /* We have a problem with any pseudoreg that lives across the setjmp. 71390075Sobrien ANSI says that if a user variable does not change in value between 71490075Sobrien the setjmp and the longjmp, then the longjmp preserves it. This 71590075Sobrien includes longjmp from a place where the pseudo appears dead. 71690075Sobrien (In principle, the value still exists if it is in scope.) 71790075Sobrien If the pseudo goes in a hard reg, some other value may occupy 71890075Sobrien that hard reg where this pseudo is dead, thus clobbering the pseudo. 71990075Sobrien Conclusion: such a pseudo must not go in a hard reg. */ 72090075Sobrien EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp, 721169689Skan FIRST_PSEUDO_REGISTER, i, rsi) 722169689Skan { 723169689Skan if (regno_reg_rtx[i] != 0) 724169689Skan { 725169689Skan REG_LIVE_LENGTH (i) = -1; 726169689Skan REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN; 727169689Skan } 728169689Skan } 72990075Sobrien } 730169689Skan if (reg_deaths) 731169689Skan { 732169689Skan free (reg_deaths); 733169689Skan reg_deaths = NULL; 734169689Skan } 73590075Sobrien timevar_pop ((extent == UPDATE_LIFE_LOCAL || blocks) 73690075Sobrien ? TV_LIFE_UPDATE : TV_LIFE); 737169689Skan if (ndead && dump_file) 738169689Skan fprintf (dump_file, "deleted %i dead insns\n", ndead); 739117395Skan return ndead; 74052284Sobrien} 74152284Sobrien 742117395Skan/* Update life information in all blocks where BB_DIRTY is set. */ 743117395Skan 744117395Skanint 745132718Skanupdate_life_info_in_dirty_blocks (enum update_life_extent extent, int prop_flags) 746117395Skan{ 747117395Skan sbitmap update_life_blocks = sbitmap_alloc (last_basic_block); 748117395Skan int n = 0; 749117395Skan basic_block bb; 750117395Skan int retval = 0; 751117395Skan 752117395Skan sbitmap_zero (update_life_blocks); 753117395Skan FOR_EACH_BB (bb) 754117395Skan { 755169689Skan if (bb->flags & BB_DIRTY) 756117395Skan { 757117395Skan SET_BIT (update_life_blocks, bb->index); 758169689Skan n++; 759117395Skan } 760117395Skan } 761117395Skan 762117395Skan if (n) 763117395Skan retval = update_life_info (update_life_blocks, extent, prop_flags); 764117395Skan 765117395Skan sbitmap_free (update_life_blocks); 766117395Skan return retval; 767117395Skan} 768117395Skan 769169689Skan/* Free the variables allocated by find_basic_blocks. */ 77052284Sobrien 77190075Sobrienvoid 772169689Skanfree_basic_block_vars (void) 77352284Sobrien{ 774169689Skan if (basic_block_info) 77552284Sobrien { 776169689Skan clear_edges (); 777169689Skan basic_block_info = NULL; 778169689Skan } 779169689Skan n_basic_blocks = 0; 780169689Skan last_basic_block = 0; 781169689Skan n_edges = 0; 78250397Sobrien 783169689Skan label_to_block_map = NULL; 784169689Skan 785169689Skan ENTRY_BLOCK_PTR->aux = NULL; 786169689Skan ENTRY_BLOCK_PTR->il.rtl->global_live_at_end = NULL; 787169689Skan EXIT_BLOCK_PTR->aux = NULL; 788169689Skan EXIT_BLOCK_PTR->il.rtl->global_live_at_start = NULL; 78952284Sobrien} 79018334Speter 79190075Sobrien/* Delete any insns that copy a register to itself. */ 79250397Sobrien 793117395Skanint 794169689Skandelete_noop_moves (void) 79552284Sobrien{ 79690075Sobrien rtx insn, next; 79790075Sobrien basic_block bb; 798117395Skan int nnoops = 0; 79952284Sobrien 800117395Skan FOR_EACH_BB (bb) 80152284Sobrien { 802132718Skan for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); insn = next) 80352284Sobrien { 80490075Sobrien next = NEXT_INSN (insn); 80590075Sobrien if (INSN_P (insn) && noop_move_p (insn)) 80652284Sobrien { 80790075Sobrien rtx note; 80852284Sobrien 80990075Sobrien /* If we're about to remove the first insn of a libcall 81090075Sobrien then move the libcall note to the next real insn and 81190075Sobrien update the retval note. */ 81290075Sobrien if ((note = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) 81390075Sobrien && XEXP (note, 0) != insn) 81490075Sobrien { 81590075Sobrien rtx new_libcall_insn = next_real_insn (insn); 81690075Sobrien rtx retval_note = find_reg_note (XEXP (note, 0), 81790075Sobrien REG_RETVAL, NULL_RTX); 81890075Sobrien REG_NOTES (new_libcall_insn) 81990075Sobrien = gen_rtx_INSN_LIST (REG_LIBCALL, XEXP (note, 0), 82090075Sobrien REG_NOTES (new_libcall_insn)); 82190075Sobrien XEXP (retval_note, 0) = new_libcall_insn; 82290075Sobrien } 82352284Sobrien 824117395Skan delete_insn_and_edges (insn); 825117395Skan nnoops++; 82690075Sobrien } 82752284Sobrien } 82818334Speter } 829169689Skan 830169689Skan if (nnoops && dump_file) 831169689Skan fprintf (dump_file, "deleted %i noop moves\n", nnoops); 832169689Skan 833117395Skan return nnoops; 83490075Sobrien} 83518334Speter 83690075Sobrien/* Delete any jump tables never referenced. We can't delete them at the 83790075Sobrien time of removing tablejump insn as they are referenced by the preceding 83890075Sobrien insns computing the destination, so we delay deleting and garbagecollect 83990075Sobrien them once life information is computed. */ 840117395Skanvoid 841132718Skandelete_dead_jumptables (void) 84290075Sobrien{ 843169689Skan basic_block bb; 844169689Skan 845169689Skan /* A dead jump table does not belong to any basic block. Scan insns 846169689Skan between two adjacent basic blocks. */ 847169689Skan FOR_EACH_BB (bb) 84852284Sobrien { 849169689Skan rtx insn, next; 850169689Skan 851169689Skan for (insn = NEXT_INSN (BB_END (bb)); 852169689Skan insn && !NOTE_INSN_BASIC_BLOCK_P (insn); 853169689Skan insn = next) 85418334Speter { 855169689Skan next = NEXT_INSN (insn); 856169689Skan if (LABEL_P (insn) 857169689Skan && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn) 858169689Skan && JUMP_P (next) 859169689Skan && (GET_CODE (PATTERN (next)) == ADDR_VEC 860169689Skan || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC)) 861169689Skan { 862169689Skan rtx label = insn, jump = next; 863169689Skan 864169689Skan if (dump_file) 865169689Skan fprintf (dump_file, "Dead jumptable %i removed\n", 866169689Skan INSN_UID (insn)); 867169689Skan 868169689Skan next = NEXT_INSN (next); 869169689Skan delete_insn (jump); 870169689Skan delete_insn (label); 871169689Skan } 87252284Sobrien } 87352284Sobrien } 87452284Sobrien} 87550397Sobrien 87690075Sobrien/* Determine if the stack pointer is constant over the life of the function. 87790075Sobrien Only useful before prologues have been emitted. */ 87850397Sobrien 87990075Sobrienstatic void 880132718Skannotice_stack_pointer_modification_1 (rtx x, rtx pat ATTRIBUTE_UNUSED, 881132718Skan void *data ATTRIBUTE_UNUSED) 88252284Sobrien{ 88390075Sobrien if (x == stack_pointer_rtx 88490075Sobrien /* The stack pointer is only modified indirectly as the result 88590075Sobrien of a push until later in flow. See the comments in rtl.texi 88690075Sobrien regarding Embedded Side-Effects on Addresses. */ 887169689Skan || (MEM_P (x) 888169689Skan && GET_RTX_CLASS (GET_CODE (XEXP (x, 0))) == RTX_AUTOINC 88990075Sobrien && XEXP (XEXP (x, 0), 0) == stack_pointer_rtx)) 89090075Sobrien current_function_sp_is_unchanging = 0; 89152284Sobrien} 89252284Sobrien 89352284Sobrienstatic void 894169689Skannotice_stack_pointer_modification (void) 89552284Sobrien{ 896169689Skan basic_block bb; 89790075Sobrien rtx insn; 89852284Sobrien 89990075Sobrien /* Assume that the stack pointer is unchanging if alloca hasn't 90090075Sobrien been used. */ 90190075Sobrien current_function_sp_is_unchanging = !current_function_calls_alloca; 90290075Sobrien if (! current_function_sp_is_unchanging) 90390075Sobrien return; 90452284Sobrien 905169689Skan FOR_EACH_BB (bb) 906169689Skan FOR_BB_INSNS (bb, insn) 907169689Skan { 908169689Skan if (INSN_P (insn)) 909169689Skan { 910169689Skan /* Check if insn modifies the stack pointer. */ 911169689Skan note_stores (PATTERN (insn), 912169689Skan notice_stack_pointer_modification_1, 913169689Skan NULL); 914169689Skan if (! current_function_sp_is_unchanging) 915169689Skan return; 916169689Skan } 917169689Skan } 91852284Sobrien} 91918334Speter 92090075Sobrien/* Mark a register in SET. Hard registers in large modes get all 92190075Sobrien of their component registers set as well. */ 92252284Sobrien 92390075Sobrienstatic void 924132718Skanmark_reg (rtx reg, void *xset) 92552284Sobrien{ 92690075Sobrien regset set = (regset) xset; 92790075Sobrien int regno = REGNO (reg); 92852284Sobrien 929169689Skan gcc_assert (GET_MODE (reg) != BLKmode); 93090075Sobrien 93190075Sobrien SET_REGNO_REG_SET (set, regno); 93290075Sobrien if (regno < FIRST_PSEUDO_REGISTER) 93352284Sobrien { 934169689Skan int n = hard_regno_nregs[regno][GET_MODE (reg)]; 93590075Sobrien while (--n > 0) 93690075Sobrien SET_REGNO_REG_SET (set, regno + n); 93752284Sobrien } 93852284Sobrien} 93952284Sobrien 94090075Sobrien/* Mark those regs which are needed at the end of the function as live 94190075Sobrien at the end of the last basic block. */ 94290075Sobrien 94352284Sobrienstatic void 944132718Skanmark_regs_live_at_end (regset set) 94552284Sobrien{ 94690075Sobrien unsigned int i; 94752284Sobrien 94890075Sobrien /* If exiting needs the right stack value, consider the stack pointer 94990075Sobrien live at the end of the function. */ 950132718Skan if ((HAVE_epilogue && epilogue_completed) 95190075Sobrien || ! EXIT_IGNORE_STACK 95290075Sobrien || (! FRAME_POINTER_REQUIRED 95390075Sobrien && ! current_function_calls_alloca 95490075Sobrien && flag_omit_frame_pointer) 95590075Sobrien || current_function_sp_is_unchanging) 95652284Sobrien { 95790075Sobrien SET_REGNO_REG_SET (set, STACK_POINTER_REGNUM); 95852284Sobrien } 95952284Sobrien 96090075Sobrien /* Mark the frame pointer if needed at the end of the function. If 96190075Sobrien we end up eliminating it, it will be removed from the live list 96290075Sobrien of each basic block by reload. */ 96390075Sobrien 96490075Sobrien if (! reload_completed || frame_pointer_needed) 96552284Sobrien { 96690075Sobrien SET_REGNO_REG_SET (set, FRAME_POINTER_REGNUM); 96790075Sobrien#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 96890075Sobrien /* If they are different, also mark the hard frame pointer as live. */ 96990075Sobrien if (! LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM)) 970117395Skan SET_REGNO_REG_SET (set, HARD_FRAME_POINTER_REGNUM); 97190075Sobrien#endif 97252284Sobrien } 97318334Speter 97490075Sobrien#ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED 97590075Sobrien /* Many architectures have a GP register even without flag_pic. 97690075Sobrien Assume the pic register is not in use, or will be handled by 97790075Sobrien other means, if it is not fixed. */ 978132718Skan if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM 97990075Sobrien && fixed_regs[PIC_OFFSET_TABLE_REGNUM]) 98090075Sobrien SET_REGNO_REG_SET (set, PIC_OFFSET_TABLE_REGNUM); 98190075Sobrien#endif 98250397Sobrien 98390075Sobrien /* Mark all global registers, and all registers used by the epilogue 98490075Sobrien as being live at the end of the function since they may be 98590075Sobrien referenced by our caller. */ 98690075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 98790075Sobrien if (global_regs[i] || EPILOGUE_USES (i)) 98890075Sobrien SET_REGNO_REG_SET (set, i); 98950397Sobrien 990132718Skan if (HAVE_epilogue && epilogue_completed) 99152284Sobrien { 99290075Sobrien /* Mark all call-saved registers that we actually used. */ 99390075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 99490075Sobrien if (regs_ever_live[i] && ! LOCAL_REGNO (i) 99590075Sobrien && ! TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 99690075Sobrien SET_REGNO_REG_SET (set, i); 99752284Sobrien } 99850397Sobrien 99990075Sobrien#ifdef EH_RETURN_DATA_REGNO 100090075Sobrien /* Mark the registers that will contain data for the handler. */ 100190075Sobrien if (reload_completed && current_function_calls_eh_return) 100290075Sobrien for (i = 0; ; ++i) 100390075Sobrien { 100490075Sobrien unsigned regno = EH_RETURN_DATA_REGNO(i); 100590075Sobrien if (regno == INVALID_REGNUM) 100690075Sobrien break; 100790075Sobrien SET_REGNO_REG_SET (set, regno); 100890075Sobrien } 100990075Sobrien#endif 101090075Sobrien#ifdef EH_RETURN_STACKADJ_RTX 1011132718Skan if ((! HAVE_epilogue || ! epilogue_completed) 101290075Sobrien && current_function_calls_eh_return) 101352284Sobrien { 101490075Sobrien rtx tmp = EH_RETURN_STACKADJ_RTX; 101590075Sobrien if (tmp && REG_P (tmp)) 101690075Sobrien mark_reg (tmp, set); 101752284Sobrien } 101890075Sobrien#endif 101990075Sobrien#ifdef EH_RETURN_HANDLER_RTX 1020132718Skan if ((! HAVE_epilogue || ! epilogue_completed) 102190075Sobrien && current_function_calls_eh_return) 102252284Sobrien { 102390075Sobrien rtx tmp = EH_RETURN_HANDLER_RTX; 102490075Sobrien if (tmp && REG_P (tmp)) 102590075Sobrien mark_reg (tmp, set); 102652284Sobrien } 102790075Sobrien#endif 102852284Sobrien 102990075Sobrien /* Mark function return value. */ 103090075Sobrien diddle_return_value (mark_reg, set); 103152284Sobrien} 103252284Sobrien 103390075Sobrien/* Propagate global life info around the graph of basic blocks. Begin 103490075Sobrien considering blocks with their corresponding bit set in BLOCKS_IN. 103590075Sobrien If BLOCKS_IN is null, consider it the universal set. 103618334Speter 103790075Sobrien BLOCKS_OUT is set for every block that was changed. */ 103850397Sobrien 103952284Sobrienstatic void 1040132718Skancalculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags) 104152284Sobrien{ 1042117395Skan basic_block *queue, *qhead, *qtail, *qend, bb; 1043169689Skan regset tmp, new_live_at_end, invalidated_by_eh_edge; 1044169689Skan regset registers_made_dead; 1045169689Skan bool failure_strategy_required = false; 1046169689Skan int *block_accesses; 104718334Speter 1048169689Skan /* The registers that are modified within this in block. */ 1049169689Skan regset *local_sets; 1050169689Skan 1051169689Skan /* The registers that are conditionally modified within this block. 1052169689Skan In other words, regs that are set only as part of a COND_EXEC. */ 1053169689Skan regset *cond_local_sets; 1054169689Skan 1055169689Skan unsigned int i; 1056169689Skan 1057117395Skan /* Some passes used to forget clear aux field of basic block causing 1058117395Skan sick behavior here. */ 1059117395Skan#ifdef ENABLE_CHECKING 1060117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1061169689Skan gcc_assert (!bb->aux); 1062117395Skan#endif 1063117395Skan 1064169689Skan tmp = ALLOC_REG_SET (®_obstack); 1065169689Skan new_live_at_end = ALLOC_REG_SET (®_obstack); 1066169689Skan invalidated_by_eh_edge = ALLOC_REG_SET (®_obstack); 1067169689Skan registers_made_dead = ALLOC_REG_SET (®_obstack); 106852284Sobrien 106990075Sobrien /* Inconveniently, this is only readily available in hard reg set form. */ 107090075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1071117395Skan if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 1072169689Skan SET_REGNO_REG_SET (invalidated_by_eh_edge, i); 107352284Sobrien 1074169689Skan /* The exception handling registers die at eh edges. */ 1075169689Skan#ifdef EH_RETURN_DATA_REGNO 1076169689Skan for (i = 0; ; ++i) 1077169689Skan { 1078169689Skan unsigned regno = EH_RETURN_DATA_REGNO (i); 1079169689Skan if (regno == INVALID_REGNUM) 1080169689Skan break; 1081169689Skan SET_REGNO_REG_SET (invalidated_by_eh_edge, regno); 1082169689Skan } 1083169689Skan#endif 1084169689Skan 1085169689Skan /* Allocate space for the sets of local properties. */ 1086169689Skan local_sets = XCNEWVEC (bitmap, last_basic_block); 1087169689Skan cond_local_sets = XCNEWVEC (bitmap, last_basic_block); 1088169689Skan 1089169689Skan /* Create a worklist. Allocate an extra slot for the `head == tail' 1090169689Skan style test for an empty queue doesn't work with a full queue. */ 1091169689Skan queue = XNEWVEC (basic_block, n_basic_blocks + 1); 109290075Sobrien qtail = queue; 1093169689Skan qhead = qend = queue + n_basic_blocks; 109452284Sobrien 109590075Sobrien /* Queue the blocks set in the initial mask. Do this in reverse block 109690075Sobrien number order so that we are more likely for the first round to do 109790075Sobrien useful work. We use AUX non-null to flag that the block is queued. */ 109890075Sobrien if (blocks_in) 109952284Sobrien { 1100117395Skan FOR_EACH_BB (bb) 1101117395Skan if (TEST_BIT (blocks_in, bb->index)) 1102117395Skan { 1103117395Skan *--qhead = bb; 1104117395Skan bb->aux = bb; 1105117395Skan } 110690075Sobrien } 110790075Sobrien else 110890075Sobrien { 1109117395Skan FOR_EACH_BB (bb) 111052284Sobrien { 111190075Sobrien *--qhead = bb; 111290075Sobrien bb->aux = bb; 111352284Sobrien } 111418334Speter } 111552284Sobrien 1116169689Skan block_accesses = XCNEWVEC (int, last_basic_block); 1117169689Skan 111896263Sobrien /* We clean aux when we remove the initially-enqueued bbs, but we 111996263Sobrien don't enqueue ENTRY and EXIT initially, so clean them upfront and 112096263Sobrien unconditionally. */ 112196263Sobrien ENTRY_BLOCK_PTR->aux = EXIT_BLOCK_PTR->aux = NULL; 112296263Sobrien 112390075Sobrien if (blocks_out) 112490075Sobrien sbitmap_zero (blocks_out); 112570635Sobrien 112690075Sobrien /* We work through the queue until there are no more blocks. What 112790075Sobrien is live at the end of this block is precisely the union of what 112890075Sobrien is live at the beginning of all its successors. So, we set its 112990075Sobrien GLOBAL_LIVE_AT_END field based on the GLOBAL_LIVE_AT_START field 113090075Sobrien for its successors. Then, we compute GLOBAL_LIVE_AT_START for 113190075Sobrien this block by walking through the instructions in this block in 113290075Sobrien reverse order and updating as we go. If that changed 113390075Sobrien GLOBAL_LIVE_AT_START, we add the predecessors of the block to the 113490075Sobrien queue; they will now need to recalculate GLOBAL_LIVE_AT_END. 113570635Sobrien 113690075Sobrien We are guaranteed to terminate, because GLOBAL_LIVE_AT_START 113790075Sobrien never shrinks. If a register appears in GLOBAL_LIVE_AT_START, it 113890075Sobrien must either be live at the end of the block, or used within the 113990075Sobrien block. In the latter case, it will certainly never disappear 114090075Sobrien from GLOBAL_LIVE_AT_START. In the former case, the register 114190075Sobrien could go away only if it disappeared from GLOBAL_LIVE_AT_START 114290075Sobrien for one of the successor blocks. By induction, that cannot 1143169689Skan occur. 1144169689Skan 1145169689Skan ??? This reasoning doesn't work if we start from non-empty initial 1146169689Skan GLOBAL_LIVE_AT_START sets. And there are actually two problems: 1147169689Skan 1) Updating may not terminate (endless oscillation). 1148169689Skan 2) Even if it does (and it usually does), the resulting information 1149169689Skan may be inaccurate. Consider for example the following case: 1150169689Skan 1151169689Skan a = ...; 1152169689Skan while (...) {...} -- 'a' not mentioned at all 1153169689Skan ... = a; 1154169689Skan 1155169689Skan If the use of 'a' is deleted between two calculations of liveness 1156169689Skan information and the initial sets are not cleared, the information 1157169689Skan about a's liveness will get stuck inside the loop and the set will 1158169689Skan appear not to be dead. 1159169689Skan 1160169689Skan We do not attempt to solve 2) -- the information is conservatively 1161169689Skan correct (i.e. we never claim that something live is dead) and the 1162169689Skan amount of optimization opportunities missed due to this problem is 1163169689Skan not significant. 1164169689Skan 1165169689Skan 1) is more serious. In order to fix it, we monitor the number of times 1166169689Skan each block is processed. Once one of the blocks has been processed more 1167169689Skan times than the maximum number of rounds, we use the following strategy: 1168169689Skan When a register disappears from one of the sets, we add it to a MAKE_DEAD 1169169689Skan set, remove all registers in this set from all GLOBAL_LIVE_AT_* sets and 1170169689Skan add the blocks with changed sets into the queue. Thus we are guaranteed 1171169689Skan to terminate (the worst case corresponds to all registers in MADE_DEAD, 1172169689Skan in which case the original reasoning above is valid), but in general we 1173169689Skan only fix up a few offending registers. 1174169689Skan 1175169689Skan The maximum number of rounds for computing liveness is the largest of 1176169689Skan MAX_LIVENESS_ROUNDS and the latest loop depth count for this function. */ 1177169689Skan 117890075Sobrien while (qhead != qtail) 117918334Speter { 118090075Sobrien int rescan, changed; 118190075Sobrien basic_block bb; 118290075Sobrien edge e; 1183169689Skan edge_iterator ei; 118452284Sobrien 118590075Sobrien bb = *qhead++; 118690075Sobrien if (qhead == qend) 118790075Sobrien qhead = queue; 118890075Sobrien bb->aux = NULL; 118918334Speter 1190169689Skan /* Should we start using the failure strategy? */ 1191169689Skan if (bb != ENTRY_BLOCK_PTR) 1192169689Skan { 1193169689Skan int max_liveness_rounds = 1194169689Skan MAX (MAX_LIVENESS_ROUNDS, cfun->max_loop_depth); 1195169689Skan 1196169689Skan block_accesses[bb->index]++; 1197169689Skan if (block_accesses[bb->index] > max_liveness_rounds) 1198169689Skan failure_strategy_required = true; 1199169689Skan } 1200169689Skan 120190075Sobrien /* Begin by propagating live_at_start from the successor blocks. */ 120290075Sobrien CLEAR_REG_SET (new_live_at_end); 120396263Sobrien 1204169689Skan if (EDGE_COUNT (bb->succs) > 0) 1205169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 120696263Sobrien { 120796263Sobrien basic_block sb = e->dest; 120896263Sobrien 120996263Sobrien /* Call-clobbered registers die across exception and 121096263Sobrien call edges. */ 121196263Sobrien /* ??? Abnormal call edges ignored for the moment, as this gets 121296263Sobrien confused by sibling call edges, which crashes reg-stack. */ 121396263Sobrien if (e->flags & EDGE_EH) 1214169689Skan bitmap_ior_and_compl_into (new_live_at_end, 1215169689Skan sb->il.rtl->global_live_at_start, 1216169689Skan invalidated_by_eh_edge); 121796263Sobrien else 1218169689Skan IOR_REG_SET (new_live_at_end, sb->il.rtl->global_live_at_start); 121996263Sobrien 122096263Sobrien /* If a target saves one register in another (instead of on 122196263Sobrien the stack) the save register will need to be live for EH. */ 122296263Sobrien if (e->flags & EDGE_EH) 122396263Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 122496263Sobrien if (EH_USES (i)) 122596263Sobrien SET_REGNO_REG_SET (new_live_at_end, i); 122696263Sobrien } 122796263Sobrien else 122890075Sobrien { 122996263Sobrien /* This might be a noreturn function that throws. And 123096263Sobrien even if it isn't, getting the unwind info right helps 123196263Sobrien debugging. */ 123296263Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 123396263Sobrien if (EH_USES (i)) 123496263Sobrien SET_REGNO_REG_SET (new_live_at_end, i); 123590075Sobrien } 123618334Speter 123790075Sobrien /* The all-important stack pointer must always be live. */ 123890075Sobrien SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM); 123918334Speter 124090075Sobrien /* Before reload, there are a few registers that must be forced 124190075Sobrien live everywhere -- which might not already be the case for 124290075Sobrien blocks within infinite loops. */ 124390075Sobrien if (! reload_completed) 124490075Sobrien { 124590075Sobrien /* Any reference to any pseudo before reload is a potential 124690075Sobrien reference of the frame pointer. */ 124790075Sobrien SET_REGNO_REG_SET (new_live_at_end, FRAME_POINTER_REGNUM); 124852284Sobrien 124990075Sobrien#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 125090075Sobrien /* Pseudos with argument area equivalences may require 125190075Sobrien reloading via the argument pointer. */ 125290075Sobrien if (fixed_regs[ARG_POINTER_REGNUM]) 125390075Sobrien SET_REGNO_REG_SET (new_live_at_end, ARG_POINTER_REGNUM); 125490075Sobrien#endif 125552284Sobrien 125690075Sobrien /* Any constant, or pseudo with constant equivalences, may 125790075Sobrien require reloading from memory using the pic register. */ 1258132718Skan if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM 125990075Sobrien && fixed_regs[PIC_OFFSET_TABLE_REGNUM]) 126090075Sobrien SET_REGNO_REG_SET (new_live_at_end, PIC_OFFSET_TABLE_REGNUM); 126190075Sobrien } 126252284Sobrien 126390075Sobrien if (bb == ENTRY_BLOCK_PTR) 126490075Sobrien { 1265169689Skan COPY_REG_SET (bb->il.rtl->global_live_at_end, new_live_at_end); 126690075Sobrien continue; 126790075Sobrien } 126852284Sobrien 126990075Sobrien /* On our first pass through this block, we'll go ahead and continue. 1270169689Skan Recognize first pass by checking if local_set is NULL for this 1271169689Skan basic block. On subsequent passes, we get to skip out early if 1272169689Skan live_at_end wouldn't have changed. */ 127352284Sobrien 1274169689Skan if (local_sets[bb->index] == NULL) 127590075Sobrien { 1276169689Skan local_sets[bb->index] = ALLOC_REG_SET (®_obstack); 1277169689Skan cond_local_sets[bb->index] = ALLOC_REG_SET (®_obstack); 127890075Sobrien rescan = 1; 127990075Sobrien } 128090075Sobrien else 128190075Sobrien { 128290075Sobrien /* If any bits were removed from live_at_end, we'll have to 128390075Sobrien rescan the block. This wouldn't be necessary if we had 128490075Sobrien precalculated local_live, however with PROP_SCAN_DEAD_CODE 128590075Sobrien local_live is really dependent on live_at_end. */ 1286169689Skan rescan = bitmap_intersect_compl_p (bb->il.rtl->global_live_at_end, 1287169689Skan new_live_at_end); 128852284Sobrien 1289169689Skan if (!rescan) 129090075Sobrien { 1291169689Skan regset cond_local_set; 1292169689Skan 1293169689Skan /* If any of the registers in the new live_at_end set are 1294169689Skan conditionally set in this basic block, we must rescan. 1295169689Skan This is because conditional lifetimes at the end of the 1296169689Skan block do not just take the live_at_end set into 1297169689Skan account, but also the liveness at the start of each 1298169689Skan successor block. We can miss changes in those sets if 1299169689Skan we only compare the new live_at_end against the 1300169689Skan previous one. */ 1301169689Skan cond_local_set = cond_local_sets[bb->index]; 1302169689Skan rescan = bitmap_intersect_p (new_live_at_end, cond_local_set); 130390075Sobrien } 130452284Sobrien 1305169689Skan if (!rescan) 130690075Sobrien { 1307169689Skan regset local_set; 1308169689Skan 130990075Sobrien /* Find the set of changed bits. Take this opportunity 131090075Sobrien to notice that this set is empty and early out. */ 1311169689Skan bitmap_xor (tmp, bb->il.rtl->global_live_at_end, new_live_at_end); 1312169689Skan if (bitmap_empty_p (tmp)) 131390075Sobrien continue; 1314169689Skan 1315169689Skan /* If any of the changed bits overlap with local_sets[bb], 1316169689Skan we'll have to rescan the block. */ 1317169689Skan local_set = local_sets[bb->index]; 1318169689Skan rescan = bitmap_intersect_p (tmp, local_set); 131990075Sobrien } 132090075Sobrien } 132152284Sobrien 132290075Sobrien /* Let our caller know that BB changed enough to require its 132390075Sobrien death notes updated. */ 132490075Sobrien if (blocks_out) 132590075Sobrien SET_BIT (blocks_out, bb->index); 132652284Sobrien 132790075Sobrien if (! rescan) 132890075Sobrien { 132990075Sobrien /* Add to live_at_start the set of all registers in 133090075Sobrien new_live_at_end that aren't in the old live_at_end. */ 1331169689Skan 1332169689Skan changed = bitmap_ior_and_compl_into (bb->il.rtl->global_live_at_start, 1333169689Skan new_live_at_end, 1334169689Skan bb->il.rtl->global_live_at_end); 1335169689Skan COPY_REG_SET (bb->il.rtl->global_live_at_end, new_live_at_end); 133690075Sobrien if (! changed) 133790075Sobrien continue; 133890075Sobrien } 133990075Sobrien else 134090075Sobrien { 1341169689Skan COPY_REG_SET (bb->il.rtl->global_live_at_end, new_live_at_end); 134218334Speter 134390075Sobrien /* Rescan the block insn by insn to turn (a copy of) live_at_end 134490075Sobrien into live_at_start. */ 1345169689Skan propagate_block (bb, new_live_at_end, 1346169689Skan local_sets[bb->index], 1347169689Skan cond_local_sets[bb->index], 1348169689Skan flags); 134952284Sobrien 135090075Sobrien /* If live_at start didn't change, no need to go farther. */ 1351169689Skan if (REG_SET_EQUAL_P (bb->il.rtl->global_live_at_start, 1352169689Skan new_live_at_end)) 135390075Sobrien continue; 135452284Sobrien 1355169689Skan if (failure_strategy_required) 1356169689Skan { 1357169689Skan /* Get the list of registers that were removed from the 1358169689Skan bb->global_live_at_start set. */ 1359169689Skan bitmap_and_compl (tmp, bb->il.rtl->global_live_at_start, 1360169689Skan new_live_at_end); 1361169689Skan if (!bitmap_empty_p (tmp)) 1362169689Skan { 1363169689Skan bool pbb_changed; 1364169689Skan basic_block pbb; 1365169689Skan 1366169689Skan /* It should not happen that one of registers we have 1367169689Skan removed last time is disappears again before any other 1368169689Skan register does. */ 1369169689Skan pbb_changed = bitmap_ior_into (registers_made_dead, tmp); 1370169689Skan gcc_assert (pbb_changed); 1371169689Skan 1372169689Skan /* Now remove the registers from all sets. */ 1373169689Skan FOR_EACH_BB (pbb) 1374169689Skan { 1375169689Skan pbb_changed = false; 1376169689Skan 1377169689Skan pbb_changed 1378169689Skan |= bitmap_and_compl_into 1379169689Skan (pbb->il.rtl->global_live_at_start, 1380169689Skan registers_made_dead); 1381169689Skan pbb_changed 1382169689Skan |= bitmap_and_compl_into 1383169689Skan (pbb->il.rtl->global_live_at_end, 1384169689Skan registers_made_dead); 1385169689Skan if (!pbb_changed) 1386169689Skan continue; 1387169689Skan 1388169689Skan /* Note the (possible) change. */ 1389169689Skan if (blocks_out) 1390169689Skan SET_BIT (blocks_out, pbb->index); 1391169689Skan 1392169689Skan /* Makes sure to really rescan the block. */ 1393169689Skan if (local_sets[pbb->index]) 1394169689Skan { 1395169689Skan FREE_REG_SET (local_sets[pbb->index]); 1396169689Skan FREE_REG_SET (cond_local_sets[pbb->index]); 1397169689Skan local_sets[pbb->index] = 0; 1398169689Skan } 1399169689Skan 1400169689Skan /* Add it to the queue. */ 1401169689Skan if (pbb->aux == NULL) 1402169689Skan { 1403169689Skan *qtail++ = pbb; 1404169689Skan if (qtail == qend) 1405169689Skan qtail = queue; 1406169689Skan pbb->aux = pbb; 1407169689Skan } 1408169689Skan } 1409169689Skan continue; 1410169689Skan } 1411169689Skan } /* end of failure_strategy_required */ 1412169689Skan 1413169689Skan COPY_REG_SET (bb->il.rtl->global_live_at_start, new_live_at_end); 141490075Sobrien } 141552284Sobrien 141690075Sobrien /* Queue all predecessors of BB so that we may re-examine 141790075Sobrien their live_at_end. */ 1418169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 141918334Speter { 142090075Sobrien basic_block pb = e->src; 1421169689Skan 1422169689Skan gcc_assert ((e->flags & EDGE_FAKE) == 0); 1423169689Skan 142490075Sobrien if (pb->aux == NULL) 142590075Sobrien { 142690075Sobrien *qtail++ = pb; 142790075Sobrien if (qtail == qend) 142890075Sobrien qtail = queue; 142990075Sobrien pb->aux = pb; 143090075Sobrien } 143118334Speter } 143218334Speter } 143352284Sobrien 143490075Sobrien FREE_REG_SET (tmp); 143590075Sobrien FREE_REG_SET (new_live_at_end); 1436169689Skan FREE_REG_SET (invalidated_by_eh_edge); 1437169689Skan FREE_REG_SET (registers_made_dead); 143852284Sobrien 143990075Sobrien if (blocks_out) 144052284Sobrien { 1441169689Skan sbitmap_iterator sbi; 1442169689Skan 1443169689Skan EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i, sbi) 144452284Sobrien { 144590075Sobrien basic_block bb = BASIC_BLOCK (i); 1446169689Skan FREE_REG_SET (local_sets[bb->index]); 1447169689Skan FREE_REG_SET (cond_local_sets[bb->index]); 1448169689Skan }; 144952284Sobrien } 145090075Sobrien else 145152284Sobrien { 1452117395Skan FOR_EACH_BB (bb) 145390075Sobrien { 1454169689Skan FREE_REG_SET (local_sets[bb->index]); 1455169689Skan FREE_REG_SET (cond_local_sets[bb->index]); 145690075Sobrien } 145752284Sobrien } 145852284Sobrien 1459169689Skan free (block_accesses); 146090075Sobrien free (queue); 1461169689Skan free (cond_local_sets); 1462169689Skan free (local_sets); 146318334Speter} 146452284Sobrien 146590075Sobrien 1466117395Skan/* This structure is used to pass parameters to and from the 146790075Sobrien the function find_regno_partial(). It is used to pass in the 146890075Sobrien register number we are looking, as well as to return any rtx 146990075Sobrien we find. */ 147052284Sobrien 147190075Sobrientypedef struct { 147290075Sobrien unsigned regno_to_find; 147390075Sobrien rtx retval; 147490075Sobrien} find_regno_partial_param; 147552284Sobrien 147652284Sobrien 147790075Sobrien/* Find the rtx for the reg numbers specified in 'data' if it is 147890075Sobrien part of an expression which only uses part of the register. Return 147990075Sobrien it in the structure passed in. */ 148090075Sobrienstatic int 1481132718Skanfind_regno_partial (rtx *ptr, void *data) 148290075Sobrien{ 148390075Sobrien find_regno_partial_param *param = (find_regno_partial_param *)data; 148490075Sobrien unsigned reg = param->regno_to_find; 148590075Sobrien param->retval = NULL_RTX; 148652284Sobrien 148790075Sobrien if (*ptr == NULL_RTX) 148890075Sobrien return 0; 148952284Sobrien 149090075Sobrien switch (GET_CODE (*ptr)) 149152284Sobrien { 149290075Sobrien case ZERO_EXTRACT: 149390075Sobrien case SIGN_EXTRACT: 149490075Sobrien case STRICT_LOW_PART: 1495169689Skan if (REG_P (XEXP (*ptr, 0)) && REGNO (XEXP (*ptr, 0)) == reg) 149690075Sobrien { 149790075Sobrien param->retval = XEXP (*ptr, 0); 149890075Sobrien return 1; 149990075Sobrien } 150090075Sobrien break; 150152284Sobrien 150290075Sobrien case SUBREG: 1503169689Skan if (REG_P (SUBREG_REG (*ptr)) 150490075Sobrien && REGNO (SUBREG_REG (*ptr)) == reg) 150552284Sobrien { 150690075Sobrien param->retval = SUBREG_REG (*ptr); 150790075Sobrien return 1; 150852284Sobrien } 150990075Sobrien break; 151090075Sobrien 151190075Sobrien default: 151290075Sobrien break; 151352284Sobrien } 151452284Sobrien 151590075Sobrien return 0; 151652284Sobrien} 151752284Sobrien 151890075Sobrien/* Process all immediate successors of the entry block looking for pseudo 151990075Sobrien registers which are live on entry. Find all of those whose first 152090075Sobrien instance is a partial register reference of some kind, and initialize 152190075Sobrien them to 0 after the entry block. This will prevent bit sets within 152290075Sobrien registers whose value is unknown, and may contain some kind of sticky 152390075Sobrien bits we don't want. */ 152452284Sobrien 1525169689Skanstatic int 1526132718Skaninitialize_uninitialized_subregs (void) 152752284Sobrien{ 152852284Sobrien rtx insn; 152990075Sobrien edge e; 1530169689Skan unsigned reg, did_something = 0; 153190075Sobrien find_regno_partial_param param; 1532169689Skan edge_iterator ei; 153352284Sobrien 1534169689Skan FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 153552284Sobrien { 153690075Sobrien basic_block bb = e->dest; 1537169689Skan regset map = bb->il.rtl->global_live_at_start; 1538169689Skan reg_set_iterator rsi; 1539169689Skan 1540169689Skan EXECUTE_IF_SET_IN_REG_SET (map, FIRST_PSEUDO_REGISTER, reg, rsi) 154152284Sobrien { 154290075Sobrien int uid = REGNO_FIRST_UID (reg); 154390075Sobrien rtx i; 154452284Sobrien 154590075Sobrien /* Find an insn which mentions the register we are looking for. 154690075Sobrien Its preferable to have an instance of the register's rtl since 154790075Sobrien there may be various flags set which we need to duplicate. 154890075Sobrien If we can't find it, its probably an automatic whose initial 154990075Sobrien value doesn't matter, or hopefully something we don't care about. */ 155090075Sobrien for (i = get_insns (); i && INSN_UID (i) != uid; i = NEXT_INSN (i)) 155190075Sobrien ; 155290075Sobrien if (i != NULL_RTX) 155390075Sobrien { 155490075Sobrien /* Found the insn, now get the REG rtx, if we can. */ 155590075Sobrien param.regno_to_find = reg; 155690075Sobrien for_each_rtx (&i, find_regno_partial, ¶m); 155790075Sobrien if (param.retval != NULL_RTX) 155890075Sobrien { 1559117395Skan start_sequence (); 1560117395Skan emit_move_insn (param.retval, 1561117395Skan CONST0_RTX (GET_MODE (param.retval))); 1562117395Skan insn = get_insns (); 1563117395Skan end_sequence (); 156490075Sobrien insert_insn_on_edge (insn, e); 156590075Sobrien did_something = 1; 156690075Sobrien } 156790075Sobrien } 1568169689Skan } 156990075Sobrien } 157052284Sobrien 157190075Sobrien if (did_something) 157290075Sobrien commit_edge_insertions (); 157390075Sobrien return did_something; 157452284Sobrien} 157590075Sobrien 157618334Speter 157790075Sobrien/* Subroutines of life analysis. */ 157850397Sobrien 157990075Sobrien/* Allocate the permanent data structures that represent the results 1580169689Skan of life analysis. */ 158190075Sobrien 1582169689Skanstatic void 1583132718Skanallocate_bb_life_data (void) 158450397Sobrien{ 1585117395Skan basic_block bb; 158650397Sobrien 1587117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 158890075Sobrien { 1589169689Skan if (bb->il.rtl->global_live_at_start) 1590169689Skan { 1591169689Skan CLEAR_REG_SET (bb->il.rtl->global_live_at_start); 1592169689Skan CLEAR_REG_SET (bb->il.rtl->global_live_at_end); 1593169689Skan } 1594169689Skan else 1595169689Skan { 1596169689Skan bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 1597169689Skan bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 1598169689Skan } 159990075Sobrien } 160050397Sobrien 1601169689Skan regs_live_at_setjmp = ALLOC_REG_SET (®_obstack); 160250397Sobrien} 160350397Sobrien 160450397Sobrienvoid 1605132718Skanallocate_reg_life_data (void) 160650397Sobrien{ 160790075Sobrien int i; 160852284Sobrien 160990075Sobrien max_regno = max_reg_num (); 1610169689Skan gcc_assert (!reg_deaths); 1611169689Skan reg_deaths = XCNEWVEC (int, max_regno); 161290075Sobrien 161390075Sobrien /* Recalculate the register space, in case it has grown. Old style 161490075Sobrien vector oriented regsets would set regset_{size,bytes} here also. */ 161590075Sobrien allocate_reg_info (max_regno, FALSE, FALSE); 161690075Sobrien 161790075Sobrien /* Reset all the data we'll collect in propagate_block and its 161890075Sobrien subroutines. */ 161990075Sobrien for (i = 0; i < max_regno; i++) 162050397Sobrien { 162190075Sobrien REG_N_SETS (i) = 0; 162290075Sobrien REG_N_REFS (i) = 0; 162390075Sobrien REG_N_DEATHS (i) = 0; 162490075Sobrien REG_N_CALLS_CROSSED (i) = 0; 1625161651Skan REG_N_THROWING_CALLS_CROSSED (i) = 0; 162690075Sobrien REG_LIVE_LENGTH (i) = 0; 1627132718Skan REG_FREQ (i) = 0; 162890075Sobrien REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN; 162950397Sobrien } 163050397Sobrien} 163150397Sobrien 163290075Sobrien/* Delete dead instructions for propagate_block. */ 163318334Speter 163490075Sobrienstatic void 1635132718Skanpropagate_block_delete_insn (rtx insn) 163618334Speter{ 163790075Sobrien rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX); 163818334Speter 163990075Sobrien /* If the insn referred to a label, and that label was attached to 164090075Sobrien an ADDR_VEC, it's safe to delete the ADDR_VEC. In fact, it's 164190075Sobrien pretty much mandatory to delete it, because the ADDR_VEC may be 164290075Sobrien referencing labels that no longer exist. 164318334Speter 164490075Sobrien INSN may reference a deleted label, particularly when a jump 164590075Sobrien table has been optimized into a direct jump. There's no 164690075Sobrien real good way to fix up the reference to the deleted label 1647117395Skan when the label is deleted, so we just allow it here. */ 164818334Speter 1649169689Skan if (inote && LABEL_P (inote)) 165052284Sobrien { 165190075Sobrien rtx label = XEXP (inote, 0); 165290075Sobrien rtx next; 165390075Sobrien 165490075Sobrien /* The label may be forced if it has been put in the constant 165590075Sobrien pool. If that is the only use we must discard the table 165690075Sobrien jump following it, but not the label itself. */ 165790075Sobrien if (LABEL_NUSES (label) == 1 + LABEL_PRESERVE_P (label) 165890075Sobrien && (next = next_nonnote_insn (label)) != NULL 1659169689Skan && JUMP_P (next) 166090075Sobrien && (GET_CODE (PATTERN (next)) == ADDR_VEC 166190075Sobrien || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC)) 166252284Sobrien { 166390075Sobrien rtx pat = PATTERN (next); 166490075Sobrien int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC; 166590075Sobrien int len = XVECLEN (pat, diff_vec_p); 166690075Sobrien int i; 166718334Speter 166890075Sobrien for (i = 0; i < len; i++) 166990075Sobrien LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--; 167018334Speter 1671117395Skan delete_insn_and_edges (next); 1672117395Skan ndead++; 167352284Sobrien } 167452284Sobrien } 167518334Speter 1676117395Skan delete_insn_and_edges (insn); 1677117395Skan ndead++; 167852284Sobrien} 167918334Speter 168090075Sobrien/* Delete dead libcalls for propagate_block. Return the insn 168190075Sobrien before the libcall. */ 168290075Sobrien 168390075Sobrienstatic rtx 1684132718Skanpropagate_block_delete_libcall (rtx insn, rtx note) 168552284Sobrien{ 168690075Sobrien rtx first = XEXP (note, 0); 168790075Sobrien rtx before = PREV_INSN (first); 168818334Speter 1689117395Skan delete_insn_chain_and_edges (first, insn); 1690117395Skan ndead++; 169190075Sobrien return before; 169290075Sobrien} 169352284Sobrien 169490075Sobrien/* Update the life-status of regs for one insn. Return the previous insn. */ 169552284Sobrien 169690075Sobrienrtx 1697132718Skanpropagate_one_insn (struct propagate_block_info *pbi, rtx insn) 169852284Sobrien{ 169990075Sobrien rtx prev = PREV_INSN (insn); 170090075Sobrien int flags = pbi->flags; 170190075Sobrien int insn_is_dead = 0; 170290075Sobrien int libcall_is_dead = 0; 170390075Sobrien rtx note; 1704169689Skan unsigned i; 170518334Speter 170690075Sobrien if (! INSN_P (insn)) 170790075Sobrien return prev; 170818334Speter 170990075Sobrien note = find_reg_note (insn, REG_RETVAL, NULL_RTX); 171090075Sobrien if (flags & PROP_SCAN_DEAD_CODE) 171118334Speter { 171290075Sobrien insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0, REG_NOTES (insn)); 171390075Sobrien libcall_is_dead = (insn_is_dead && note != 0 171490075Sobrien && libcall_dead_p (pbi, note, insn)); 171552284Sobrien } 171618334Speter 171790075Sobrien /* If an instruction consists of just dead store(s) on final pass, 171890075Sobrien delete it. */ 171990075Sobrien if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead) 172090075Sobrien { 172190075Sobrien /* If we're trying to delete a prologue or epilogue instruction 172290075Sobrien that isn't flagged as possibly being dead, something is wrong. 172390075Sobrien But if we are keeping the stack pointer depressed, we might well 172490075Sobrien be deleting insns that are used to compute the amount to update 172590075Sobrien it by, so they are fine. */ 172690075Sobrien if (reload_completed 172790075Sobrien && !(TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE 172890075Sobrien && (TYPE_RETURNS_STACK_DEPRESSED 172990075Sobrien (TREE_TYPE (current_function_decl)))) 173090075Sobrien && (((HAVE_epilogue || HAVE_prologue) 173190075Sobrien && prologue_epilogue_contains (insn)) 173290075Sobrien || (HAVE_sibcall_epilogue 173390075Sobrien && sibcall_epilogue_contains (insn))) 173490075Sobrien && find_reg_note (insn, REG_MAYBE_DEAD, NULL_RTX) == 0) 173590075Sobrien fatal_insn ("Attempt to delete prologue/epilogue insn:", insn); 173618334Speter 173790075Sobrien /* Record sets. Do this even for dead instructions, since they 1738169689Skan would have killed the values if they hadn't been deleted. To 1739169689Skan be consistent, we also have to emit a clobber when we delete 1740169689Skan an insn that clobbers a live register. */ 1741169689Skan pbi->flags |= PROP_DEAD_INSN; 174290075Sobrien mark_set_regs (pbi, PATTERN (insn), insn); 1743169689Skan pbi->flags &= ~PROP_DEAD_INSN; 174452284Sobrien 174590075Sobrien /* CC0 is now known to be dead. Either this insn used it, 174690075Sobrien in which case it doesn't anymore, or clobbered it, 174790075Sobrien so the next insn can't use it. */ 174890075Sobrien pbi->cc0_live = 0; 174952284Sobrien 175090075Sobrien if (libcall_is_dead) 1751146895Skan prev = propagate_block_delete_libcall (insn, note); 175290075Sobrien else 1753102780Skan { 175452284Sobrien 1755117395Skan /* If INSN contains a RETVAL note and is dead, but the libcall 1756117395Skan as a whole is not dead, then we want to remove INSN, but 1757117395Skan not the whole libcall sequence. 1758102780Skan 1759132718Skan However, we need to also remove the dangling REG_LIBCALL 1760117395Skan note so that we do not have mis-matched LIBCALL/RETVAL 1761117395Skan notes. In theory we could find a new location for the 1762132718Skan REG_RETVAL note, but it hardly seems worth the effort. 1763102780Skan 1764117395Skan NOTE at this point will be the RETVAL note if it exists. */ 1765102780Skan if (note) 1766102780Skan { 1767102780Skan rtx libcall_note; 1768132718Skan 1769102780Skan libcall_note 1770102780Skan = find_reg_note (XEXP (note, 0), REG_LIBCALL, NULL_RTX); 1771102780Skan remove_note (XEXP (note, 0), libcall_note); 1772102780Skan } 1773102780Skan 1774102780Skan /* Similarly if INSN contains a LIBCALL note, remove the 1775132718Skan dangling REG_RETVAL note. */ 1776102780Skan note = find_reg_note (insn, REG_LIBCALL, NULL_RTX); 1777102780Skan if (note) 1778102780Skan { 1779102780Skan rtx retval_note; 1780102780Skan 1781102780Skan retval_note 1782102780Skan = find_reg_note (XEXP (note, 0), REG_RETVAL, NULL_RTX); 1783102780Skan remove_note (XEXP (note, 0), retval_note); 1784102780Skan } 1785102780Skan 1786102780Skan /* Now delete INSN. */ 1787117395Skan propagate_block_delete_insn (insn); 1788102780Skan } 1789102780Skan 179090075Sobrien return prev; 179190075Sobrien } 179252284Sobrien 179390075Sobrien /* See if this is an increment or decrement that can be merged into 179490075Sobrien a following memory address. */ 179590075Sobrien#ifdef AUTO_INC_DEC 179690075Sobrien { 179790075Sobrien rtx x = single_set (insn); 179852284Sobrien 179990075Sobrien /* Does this instruction increment or decrement a register? */ 180090075Sobrien if ((flags & PROP_AUTOINC) 180190075Sobrien && x != 0 1802169689Skan && REG_P (SET_DEST (x)) 180390075Sobrien && (GET_CODE (SET_SRC (x)) == PLUS 180490075Sobrien || GET_CODE (SET_SRC (x)) == MINUS) 180590075Sobrien && XEXP (SET_SRC (x), 0) == SET_DEST (x) 180690075Sobrien && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT 180790075Sobrien /* Ok, look for a following memory ref we can combine with. 180890075Sobrien If one is found, change the memory ref to a PRE_INC 180990075Sobrien or PRE_DEC, cancel this insn, and return 1. 181090075Sobrien Return 0 if nothing has been done. */ 181190075Sobrien && try_pre_increment_1 (pbi, insn)) 181290075Sobrien return prev; 181390075Sobrien } 181490075Sobrien#endif /* AUTO_INC_DEC */ 181552284Sobrien 181690075Sobrien CLEAR_REG_SET (pbi->new_set); 181752284Sobrien 181890075Sobrien /* If this is not the final pass, and this insn is copying the value of 181990075Sobrien a library call and it's dead, don't scan the insns that perform the 182090075Sobrien library call, so that the call's arguments are not marked live. */ 182190075Sobrien if (libcall_is_dead) 182252284Sobrien { 182390075Sobrien /* Record the death of the dest reg. */ 182490075Sobrien mark_set_regs (pbi, PATTERN (insn), insn); 182552284Sobrien 182690075Sobrien insn = XEXP (note, 0); 182790075Sobrien return PREV_INSN (insn); 182852284Sobrien } 182990075Sobrien else if (GET_CODE (PATTERN (insn)) == SET 183090075Sobrien && SET_DEST (PATTERN (insn)) == stack_pointer_rtx 183190075Sobrien && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS 183290075Sobrien && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx 183390075Sobrien && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT) 1834169689Skan { 1835169689Skan /* We have an insn to pop a constant amount off the stack. 1836169689Skan (Such insns use PLUS regardless of the direction of the stack, 1837169689Skan and any insn to adjust the stack by a constant is always a pop 1838169689Skan or part of a push.) 1839169689Skan These insns, if not dead stores, have no effect on life, though 1840169689Skan they do have an effect on the memory stores we are tracking. */ 1841169689Skan invalidate_mems_from_set (pbi, stack_pointer_rtx); 1842169689Skan /* Still, we need to update local_set, lest ifcvt.c:dead_or_predicable 1843169689Skan concludes that the stack pointer is not modified. */ 1844169689Skan mark_set_regs (pbi, PATTERN (insn), insn); 1845169689Skan } 184690075Sobrien else 184790075Sobrien { 184890075Sobrien /* Any regs live at the time of a call instruction must not go 184990075Sobrien in a register clobbered by calls. Find all regs now live and 185090075Sobrien record this for them. */ 185118334Speter 1852169689Skan if (CALL_P (insn) && (flags & PROP_REG_INFO)) 1853161651Skan { 1854169689Skan reg_set_iterator rsi; 1855169689Skan EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, rsi) 1856169689Skan REG_N_CALLS_CROSSED (i)++; 1857169689Skan if (can_throw_internal (insn)) 1858169689Skan EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, rsi) 1859169689Skan REG_N_THROWING_CALLS_CROSSED (i)++; 1860161651Skan } 186152284Sobrien 186290075Sobrien /* Record sets. Do this even for dead instructions, since they 186390075Sobrien would have killed the values if they hadn't been deleted. */ 186490075Sobrien mark_set_regs (pbi, PATTERN (insn), insn); 186552284Sobrien 1866169689Skan if (CALL_P (insn)) 186718334Speter { 1868119256Skan regset live_at_end; 1869119256Skan bool sibcall_p; 1870119256Skan rtx note, cond; 187190075Sobrien int i; 187218334Speter 187390075Sobrien cond = NULL_RTX; 187490075Sobrien if (GET_CODE (PATTERN (insn)) == COND_EXEC) 187590075Sobrien cond = COND_EXEC_TEST (PATTERN (insn)); 187618334Speter 1877117395Skan /* Non-constant calls clobber memory, constant calls do not 1878117395Skan clobber memory, though they may clobber outgoing arguments 1879117395Skan on the stack. */ 188090075Sobrien if (! CONST_OR_PURE_CALL_P (insn)) 188118334Speter { 188290075Sobrien free_EXPR_LIST_list (&pbi->mem_set_list); 188390075Sobrien pbi->mem_set_list_len = 0; 188418334Speter } 1885117395Skan else 1886117395Skan invalidate_mems_from_set (pbi, stack_pointer_rtx); 188718334Speter 188890075Sobrien /* There may be extra registers to be clobbered. */ 188990075Sobrien for (note = CALL_INSN_FUNCTION_USAGE (insn); 189090075Sobrien note; 189190075Sobrien note = XEXP (note, 1)) 189290075Sobrien if (GET_CODE (XEXP (note, 0)) == CLOBBER) 189390075Sobrien mark_set_1 (pbi, CLOBBER, XEXP (XEXP (note, 0), 0), 189490075Sobrien cond, insn, pbi->flags); 189518334Speter 1896119256Skan /* Calls change all call-used and global registers; sibcalls do not 1897119256Skan clobber anything that must be preserved at end-of-function, 1898119256Skan except for return values. */ 1899119256Skan 1900119256Skan sibcall_p = SIBLING_CALL_P (insn); 1901169689Skan live_at_end = EXIT_BLOCK_PTR->il.rtl->global_live_at_start; 190290075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1903119256Skan if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i) 1904119256Skan && ! (sibcall_p 1905119256Skan && REGNO_REG_SET_P (live_at_end, i) 1906119256Skan && ! refers_to_regno_p (i, i+1, 1907119256Skan current_function_return_rtx, 1908119256Skan (rtx *) 0))) 190990075Sobrien { 1910132718Skan enum rtx_code code = global_regs[i] ? SET : CLOBBER; 191190075Sobrien /* We do not want REG_UNUSED notes for these registers. */ 1912132718Skan mark_set_1 (pbi, code, regno_reg_rtx[i], cond, insn, 191390075Sobrien pbi->flags & ~(PROP_DEATH_NOTES | PROP_REG_INFO)); 191490075Sobrien } 191518334Speter } 191618334Speter 191790075Sobrien /* If an insn doesn't use CC0, it becomes dead since we assume 191890075Sobrien that every insn clobbers it. So show it dead here; 191990075Sobrien mark_used_regs will set it live if it is referenced. */ 192090075Sobrien pbi->cc0_live = 0; 192118334Speter 192290075Sobrien /* Record uses. */ 192390075Sobrien if (! insn_is_dead) 192490075Sobrien mark_used_regs (pbi, PATTERN (insn), NULL_RTX, insn); 192518334Speter 192690075Sobrien /* Sometimes we may have inserted something before INSN (such as a move) 192790075Sobrien when we make an auto-inc. So ensure we will scan those insns. */ 192890075Sobrien#ifdef AUTO_INC_DEC 192990075Sobrien prev = PREV_INSN (insn); 193018334Speter#endif 193118334Speter 1932169689Skan if (! insn_is_dead && CALL_P (insn)) 193390075Sobrien { 193490075Sobrien int i; 193590075Sobrien rtx note, cond; 193618334Speter 193790075Sobrien cond = NULL_RTX; 193890075Sobrien if (GET_CODE (PATTERN (insn)) == COND_EXEC) 193990075Sobrien cond = COND_EXEC_TEST (PATTERN (insn)); 194050397Sobrien 1941132718Skan /* Calls use their arguments, and may clobber memory which 1942132718Skan address involves some register. */ 194390075Sobrien for (note = CALL_INSN_FUNCTION_USAGE (insn); 194490075Sobrien note; 194590075Sobrien note = XEXP (note, 1)) 1946132718Skan /* We find USE or CLOBBER entities in a FUNCTION_USAGE list: both 1947132718Skan of which mark_used_regs knows how to handle. */ 1948132718Skan mark_used_regs (pbi, XEXP (XEXP (note, 0), 0), cond, insn); 194950397Sobrien 195090075Sobrien /* The stack ptr is used (honorarily) by a CALL insn. */ 1951169689Skan if ((flags & PROP_REG_INFO) 1952169689Skan && !REGNO_REG_SET_P (pbi->reg_live, STACK_POINTER_REGNUM)) 1953169689Skan reg_deaths[STACK_POINTER_REGNUM] = pbi->insn_num; 195490075Sobrien SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM); 195518334Speter 195690075Sobrien /* Calls may also reference any of the global registers, 195790075Sobrien so they are made live. */ 195890075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 195990075Sobrien if (global_regs[i]) 1960117395Skan mark_used_reg (pbi, regno_reg_rtx[i], cond, insn); 196190075Sobrien } 196252284Sobrien } 196352284Sobrien 1964169689Skan pbi->insn_num++; 196552284Sobrien 196690075Sobrien return prev; 196752284Sobrien} 196852284Sobrien 196990075Sobrien/* Initialize a propagate_block_info struct for public consumption. 197090075Sobrien Note that the structure itself is opaque to this file, but that 197190075Sobrien the user can use the regsets provided here. */ 197252284Sobrien 197390075Sobrienstruct propagate_block_info * 1974132718Skaninit_propagate_block_info (basic_block bb, regset live, regset local_set, 1975132718Skan regset cond_local_set, int flags) 197618334Speter{ 1977169689Skan struct propagate_block_info *pbi = XNEW (struct propagate_block_info); 197818334Speter 197990075Sobrien pbi->bb = bb; 198090075Sobrien pbi->reg_live = live; 198190075Sobrien pbi->mem_set_list = NULL_RTX; 198290075Sobrien pbi->mem_set_list_len = 0; 198390075Sobrien pbi->local_set = local_set; 198490075Sobrien pbi->cond_local_set = cond_local_set; 198590075Sobrien pbi->cc0_live = 0; 198690075Sobrien pbi->flags = flags; 1987169689Skan pbi->insn_num = 0; 198818334Speter 198990075Sobrien if (flags & (PROP_LOG_LINKS | PROP_AUTOINC)) 1990169689Skan pbi->reg_next_use = XCNEWVEC (rtx, max_reg_num ()); 199190075Sobrien else 199290075Sobrien pbi->reg_next_use = NULL; 199350397Sobrien 1994169689Skan pbi->new_set = BITMAP_ALLOC (NULL); 199550397Sobrien 199690075Sobrien#ifdef HAVE_conditional_execution 199790075Sobrien pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL, 199890075Sobrien free_reg_cond_life_info); 1999169689Skan pbi->reg_cond_reg = BITMAP_ALLOC (NULL); 200050397Sobrien 2001132718Skan /* If this block ends in a conditional branch, for each register 2002132718Skan live from one side of the branch and not the other, record the 2003132718Skan register as conditionally dead. */ 2004169689Skan if (JUMP_P (BB_END (bb)) 2005132718Skan && any_condjump_p (BB_END (bb))) 200618334Speter { 2007169689Skan regset diff = ALLOC_REG_SET (®_obstack); 200890075Sobrien basic_block bb_true, bb_false; 2009169689Skan unsigned i; 201018334Speter 201190075Sobrien /* Identify the successor blocks. */ 2012169689Skan bb_true = EDGE_SUCC (bb, 0)->dest; 2013169689Skan if (!single_succ_p (bb)) 201490075Sobrien { 2015169689Skan bb_false = EDGE_SUCC (bb, 1)->dest; 201618334Speter 2017169689Skan if (EDGE_SUCC (bb, 0)->flags & EDGE_FALLTHRU) 201890075Sobrien { 201990075Sobrien basic_block t = bb_false; 202090075Sobrien bb_false = bb_true; 202190075Sobrien bb_true = t; 202290075Sobrien } 2023169689Skan else 2024169689Skan gcc_assert (EDGE_SUCC (bb, 1)->flags & EDGE_FALLTHRU); 202590075Sobrien } 202690075Sobrien else 202790075Sobrien { 202890075Sobrien /* This can happen with a conditional jump to the next insn. */ 2029169689Skan gcc_assert (JUMP_LABEL (BB_END (bb)) == BB_HEAD (bb_true)); 203018334Speter 203190075Sobrien /* Simplest way to do nothing. */ 203290075Sobrien bb_false = bb_true; 203390075Sobrien } 203418334Speter 203590075Sobrien /* Compute which register lead different lives in the successors. */ 2036169689Skan bitmap_xor (diff, bb_true->il.rtl->global_live_at_start, 2037169689Skan bb_false->il.rtl->global_live_at_start); 2038169689Skan 2039169689Skan if (!bitmap_empty_p (diff)) 2040169689Skan { 2041132718Skan /* Extract the condition from the branch. */ 2042132718Skan rtx set_src = SET_SRC (pc_set (BB_END (bb))); 2043132718Skan rtx cond_true = XEXP (set_src, 0); 204490075Sobrien rtx reg = XEXP (cond_true, 0); 2045169689Skan enum rtx_code inv_cond; 204618334Speter 204790075Sobrien if (GET_CODE (reg) == SUBREG) 204890075Sobrien reg = SUBREG_REG (reg); 204952284Sobrien 2050132718Skan /* We can only track conditional lifetimes if the condition is 2051169689Skan in the form of a reversible comparison of a register against 2052169689Skan zero. If the condition is more complex than that, then it is 2053169689Skan safe not to record any information. */ 2054169689Skan inv_cond = reversed_comparison_code (cond_true, BB_END (bb)); 2055169689Skan if (inv_cond != UNKNOWN 2056169689Skan && REG_P (reg) 2057132718Skan && XEXP (cond_true, 1) == const0_rtx) 2058132718Skan { 2059132718Skan rtx cond_false 2060169689Skan = gen_rtx_fmt_ee (inv_cond, 2061132718Skan GET_MODE (cond_true), XEXP (cond_true, 0), 2062132718Skan XEXP (cond_true, 1)); 2063169689Skan reg_set_iterator rsi; 2064169689Skan 2065132718Skan if (GET_CODE (XEXP (set_src, 1)) == PC) 2066132718Skan { 2067132718Skan rtx t = cond_false; 2068132718Skan cond_false = cond_true; 2069132718Skan cond_true = t; 2070132718Skan } 207170635Sobrien 2072132718Skan SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (reg)); 207370635Sobrien 2074132718Skan /* For each such register, mark it conditionally dead. */ 2075169689Skan EXECUTE_IF_SET_IN_REG_SET (diff, 0, i, rsi) 2076169689Skan { 2077169689Skan struct reg_cond_life_info *rcli; 2078169689Skan rtx cond; 207970635Sobrien 2080169689Skan rcli = XNEW (struct reg_cond_life_info); 208118334Speter 2082169689Skan if (REGNO_REG_SET_P (bb_true->il.rtl->global_live_at_start, 2083169689Skan i)) 2084169689Skan cond = cond_false; 2085169689Skan else 2086169689Skan cond = cond_true; 2087169689Skan rcli->condition = cond; 2088169689Skan rcli->stores = const0_rtx; 2089169689Skan rcli->orig_condition = cond; 209018334Speter 2091169689Skan splay_tree_insert (pbi->reg_cond_dead, i, 2092169689Skan (splay_tree_value) rcli); 2093169689Skan } 2094132718Skan } 209590075Sobrien } 209618334Speter 209790075Sobrien FREE_REG_SET (diff); 209890075Sobrien } 209990075Sobrien#endif 210018334Speter 210190075Sobrien /* If this block has no successors, any stores to the frame that aren't 210290075Sobrien used later in the block are dead. So make a pass over the block 210390075Sobrien recording any such that are made and show them dead at the end. We do 210490075Sobrien a very conservative and simple job here. */ 210590075Sobrien if (optimize 210690075Sobrien && ! (TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE 210790075Sobrien && (TYPE_RETURNS_STACK_DEPRESSED 210890075Sobrien (TREE_TYPE (current_function_decl)))) 2109117395Skan && (flags & PROP_SCAN_DEAD_STORES) 2110169689Skan && (EDGE_COUNT (bb->succs) == 0 2111169689Skan || (single_succ_p (bb) 2112169689Skan && single_succ (bb) == EXIT_BLOCK_PTR 211390075Sobrien && ! current_function_calls_eh_return))) 211490075Sobrien { 211590075Sobrien rtx insn, set; 2116132718Skan for (insn = BB_END (bb); insn != BB_HEAD (bb); insn = PREV_INSN (insn)) 2117169689Skan if (NONJUMP_INSN_P (insn) 211890075Sobrien && (set = single_set (insn)) 2119169689Skan && MEM_P (SET_DEST (set))) 212018334Speter { 212190075Sobrien rtx mem = SET_DEST (set); 212290075Sobrien rtx canon_mem = canon_rtx (mem); 212350397Sobrien 212490075Sobrien if (XEXP (canon_mem, 0) == frame_pointer_rtx 212590075Sobrien || (GET_CODE (XEXP (canon_mem, 0)) == PLUS 212690075Sobrien && XEXP (XEXP (canon_mem, 0), 0) == frame_pointer_rtx 212790075Sobrien && GET_CODE (XEXP (XEXP (canon_mem, 0), 1)) == CONST_INT)) 212890075Sobrien add_to_mem_set_list (pbi, canon_mem); 212918334Speter } 213090075Sobrien } 213118334Speter 213290075Sobrien return pbi; 213390075Sobrien} 213418334Speter 213590075Sobrien/* Release a propagate_block_info struct. */ 213652284Sobrien 213790075Sobrienvoid 2138132718Skanfree_propagate_block_info (struct propagate_block_info *pbi) 213990075Sobrien{ 214090075Sobrien free_EXPR_LIST_list (&pbi->mem_set_list); 214152284Sobrien 2142169689Skan BITMAP_FREE (pbi->new_set); 214318334Speter 214490075Sobrien#ifdef HAVE_conditional_execution 214590075Sobrien splay_tree_delete (pbi->reg_cond_dead); 2146169689Skan BITMAP_FREE (pbi->reg_cond_reg); 214790075Sobrien#endif 214818334Speter 2149169689Skan if (pbi->flags & PROP_REG_INFO) 2150169689Skan { 2151169689Skan int num = pbi->insn_num; 2152169689Skan unsigned i; 2153169689Skan reg_set_iterator rsi; 2154169689Skan 2155169689Skan EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, rsi) 2156169689Skan { 2157169689Skan REG_LIVE_LENGTH (i) += num - reg_deaths[i]; 2158169689Skan reg_deaths[i] = 0; 2159169689Skan } 2160169689Skan } 216190075Sobrien if (pbi->reg_next_use) 216290075Sobrien free (pbi->reg_next_use); 216318334Speter 216490075Sobrien free (pbi); 216590075Sobrien} 216618334Speter 216790075Sobrien/* Compute the registers live at the beginning of a basic block BB from 216890075Sobrien those live at the end. 216918334Speter 217090075Sobrien When called, REG_LIVE contains those live at the end. On return, it 217190075Sobrien contains those live at the beginning. 217218334Speter 217390075Sobrien LOCAL_SET, if non-null, will be set with all registers killed 217490075Sobrien unconditionally by this basic block. 217590075Sobrien Likewise, COND_LOCAL_SET, if non-null, will be set with all registers 217690075Sobrien killed conditionally by this basic block. If there is any unconditional 217790075Sobrien set of a register, then the corresponding bit will be set in LOCAL_SET 217890075Sobrien and cleared in COND_LOCAL_SET. 217990075Sobrien It is valid for LOCAL_SET and COND_LOCAL_SET to be the same set. In this 218090075Sobrien case, the resulting set will be equal to the union of the two sets that 218190075Sobrien would otherwise be computed. 218218334Speter 2183117395Skan Return nonzero if an INSN is deleted (i.e. by dead code removal). */ 218418334Speter 218590075Sobrienint 2186132718Skanpropagate_block (basic_block bb, regset live, regset local_set, 2187132718Skan regset cond_local_set, int flags) 218890075Sobrien{ 218990075Sobrien struct propagate_block_info *pbi; 219090075Sobrien rtx insn, prev; 219190075Sobrien int changed; 219218334Speter 219390075Sobrien pbi = init_propagate_block_info (bb, live, local_set, cond_local_set, flags); 219418334Speter 219590075Sobrien if (flags & PROP_REG_INFO) 219690075Sobrien { 2197169689Skan unsigned i; 2198169689Skan reg_set_iterator rsi; 219918334Speter 220090075Sobrien /* Process the regs live at the end of the block. 220190075Sobrien Mark them as not local to any one basic block. */ 2202169689Skan EXECUTE_IF_SET_IN_REG_SET (live, 0, i, rsi) 2203169689Skan REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; 220490075Sobrien } 220518334Speter 220690075Sobrien /* Scan the block an insn at a time from end to beginning. */ 220718334Speter 220890075Sobrien changed = 0; 2209132718Skan for (insn = BB_END (bb); ; insn = prev) 221090075Sobrien { 221190075Sobrien /* If this is a call to `setjmp' et al, warn if any 221290075Sobrien non-volatile datum is live. */ 221390075Sobrien if ((flags & PROP_REG_INFO) 2214169689Skan && CALL_P (insn) 221590075Sobrien && find_reg_note (insn, REG_SETJMP, NULL)) 221690075Sobrien IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live); 221718334Speter 221890075Sobrien prev = propagate_one_insn (pbi, insn); 2219132718Skan if (!prev) 2220132718Skan changed |= insn != get_insns (); 2221132718Skan else 2222132718Skan changed |= NEXT_INSN (prev) != insn; 222318334Speter 2224132718Skan if (insn == BB_HEAD (bb)) 222518334Speter break; 222618334Speter } 222718334Speter 2228169689Skan#ifdef EH_RETURN_DATA_REGNO 2229169689Skan if (bb_has_eh_pred (bb)) 2230169689Skan { 2231169689Skan unsigned int i; 2232169689Skan for (i = 0; ; ++i) 2233169689Skan { 2234169689Skan unsigned regno = EH_RETURN_DATA_REGNO (i); 2235169689Skan if (regno == INVALID_REGNUM) 2236169689Skan break; 2237169689Skan if (pbi->local_set) 2238169689Skan { 2239169689Skan CLEAR_REGNO_REG_SET (pbi->cond_local_set, regno); 2240169689Skan SET_REGNO_REG_SET (pbi->local_set, regno); 2241169689Skan } 2242169689Skan if (REGNO_REG_SET_P (pbi->reg_live, regno)) 2243169689Skan SET_REGNO_REG_SET (pbi->new_set, regno); 2244169689Skan 2245169689Skan regs_ever_live[regno] = 1; 2246169689Skan } 2247169689Skan } 2248169689Skan#endif 2249169689Skan 225090075Sobrien free_propagate_block_info (pbi); 225190075Sobrien 225290075Sobrien return changed; 225318334Speter} 225418334Speter 225518334Speter/* Return 1 if X (the body of an insn, or part of it) is just dead stores 225618334Speter (SET expressions whose destinations are registers dead after the insn). 225718334Speter NEEDED is the regset that says which regs are alive after the insn. 225818334Speter 2259117395Skan Unless CALL_OK is nonzero, an insn is needed if it contains a CALL. 226018334Speter 226152284Sobrien If X is the entire body of an insn, NOTES contains the reg notes 226252284Sobrien pertaining to the insn. */ 226352284Sobrien 226418334Speterstatic int 2265132718Skaninsn_dead_p (struct propagate_block_info *pbi, rtx x, int call_ok, 2266132718Skan rtx notes ATTRIBUTE_UNUSED) 226718334Speter{ 226850397Sobrien enum rtx_code code = GET_CODE (x); 226950397Sobrien 2270117395Skan /* Don't eliminate insns that may trap. */ 2271117395Skan if (flag_non_call_exceptions && may_trap_p (x)) 2272117395Skan return 0; 2273117395Skan 227452284Sobrien#ifdef AUTO_INC_DEC 227590075Sobrien /* As flow is invoked after combine, we must take existing AUTO_INC 227690075Sobrien expressions into account. */ 227790075Sobrien for (; notes; notes = XEXP (notes, 1)) 227852284Sobrien { 227990075Sobrien if (REG_NOTE_KIND (notes) == REG_INC) 228052284Sobrien { 228190075Sobrien int regno = REGNO (XEXP (notes, 0)); 228252284Sobrien 228390075Sobrien /* Don't delete insns to set global regs. */ 228490075Sobrien if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno]) 228590075Sobrien || REGNO_REG_SET_P (pbi->reg_live, regno)) 228690075Sobrien return 0; 228752284Sobrien } 228852284Sobrien } 228952284Sobrien#endif 229052284Sobrien 229118334Speter /* If setting something that's a reg or part of one, 229218334Speter see if that register's altered value will be live. */ 229318334Speter 229418334Speter if (code == SET) 229518334Speter { 229650397Sobrien rtx r = SET_DEST (x); 229750397Sobrien 229818334Speter#ifdef HAVE_cc0 229918334Speter if (GET_CODE (r) == CC0) 230090075Sobrien return ! pbi->cc0_live; 230118334Speter#endif 230290075Sobrien 230390075Sobrien /* A SET that is a subroutine call cannot be dead. */ 230490075Sobrien if (GET_CODE (SET_SRC (x)) == CALL) 230552284Sobrien { 230690075Sobrien if (! call_ok) 230790075Sobrien return 0; 230890075Sobrien } 230990075Sobrien 231090075Sobrien /* Don't eliminate loads from volatile memory or volatile asms. */ 231190075Sobrien else if (volatile_refs_p (SET_SRC (x))) 231290075Sobrien return 0; 231390075Sobrien 2314169689Skan if (MEM_P (r)) 231590075Sobrien { 231690075Sobrien rtx temp, canon_r; 231790075Sobrien 231890075Sobrien if (MEM_VOLATILE_P (r) || GET_MODE (r) == BLKmode) 231990075Sobrien return 0; 232090075Sobrien 232190075Sobrien canon_r = canon_rtx (r); 232290075Sobrien 232352284Sobrien /* Walk the set of memory locations we are currently tracking 232452284Sobrien and see if one is an identical match to this memory location. 232552284Sobrien If so, this memory write is dead (remember, we're walking 232690075Sobrien backwards from the end of the block to the start). Since 232790075Sobrien rtx_equal_p does not check the alias set or flags, we also 232890075Sobrien must have the potential for them to conflict (anti_dependence). */ 232990075Sobrien for (temp = pbi->mem_set_list; temp != 0; temp = XEXP (temp, 1)) 2330169689Skan if (anti_dependence (r, XEXP (temp, 0))) 233190075Sobrien { 233290075Sobrien rtx mem = XEXP (temp, 0); 233318334Speter 233490075Sobrien if (rtx_equal_p (XEXP (canon_r, 0), XEXP (mem, 0)) 233590075Sobrien && (GET_MODE_SIZE (GET_MODE (canon_r)) 233690075Sobrien <= GET_MODE_SIZE (GET_MODE (mem)))) 233790075Sobrien return 1; 233818334Speter 233990075Sobrien#ifdef AUTO_INC_DEC 234090075Sobrien /* Check if memory reference matches an auto increment. Only 234190075Sobrien post increment/decrement or modify are valid. */ 234290075Sobrien if (GET_MODE (mem) == GET_MODE (r) 234390075Sobrien && (GET_CODE (XEXP (mem, 0)) == POST_DEC 234490075Sobrien || GET_CODE (XEXP (mem, 0)) == POST_INC 234590075Sobrien || GET_CODE (XEXP (mem, 0)) == POST_MODIFY) 234690075Sobrien && GET_MODE (XEXP (mem, 0)) == GET_MODE (r) 234790075Sobrien && rtx_equal_p (XEXP (XEXP (mem, 0), 0), XEXP (r, 0))) 234890075Sobrien return 1; 234990075Sobrien#endif 235090075Sobrien } 235190075Sobrien } 235290075Sobrien else 235318334Speter { 235490075Sobrien while (GET_CODE (r) == SUBREG 235590075Sobrien || GET_CODE (r) == STRICT_LOW_PART 235690075Sobrien || GET_CODE (r) == ZERO_EXTRACT) 235790075Sobrien r = XEXP (r, 0); 235818334Speter 2359169689Skan if (REG_P (r)) 236090075Sobrien { 236190075Sobrien int regno = REGNO (r); 236290075Sobrien 236390075Sobrien /* Obvious. */ 236490075Sobrien if (REGNO_REG_SET_P (pbi->reg_live, regno)) 236590075Sobrien return 0; 236690075Sobrien 236790075Sobrien /* If this is a hard register, verify that subsequent 236890075Sobrien words are not needed. */ 236990075Sobrien if (regno < FIRST_PSEUDO_REGISTER) 237090075Sobrien { 2371169689Skan int n = hard_regno_nregs[regno][GET_MODE (r)]; 237290075Sobrien 237390075Sobrien while (--n > 0) 237490075Sobrien if (REGNO_REG_SET_P (pbi->reg_live, regno+n)) 237590075Sobrien return 0; 237690075Sobrien } 237790075Sobrien 237890075Sobrien /* Don't delete insns to set global regs. */ 237990075Sobrien if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]) 238090075Sobrien return 0; 238190075Sobrien 238290075Sobrien /* Make sure insns to set the stack pointer aren't deleted. */ 238390075Sobrien if (regno == STACK_POINTER_REGNUM) 238490075Sobrien return 0; 238590075Sobrien 238690075Sobrien /* ??? These bits might be redundant with the force live bits 238790075Sobrien in calculate_global_regs_live. We would delete from 238890075Sobrien sequential sets; whether this actually affects real code 238990075Sobrien for anything but the stack pointer I don't know. */ 239090075Sobrien /* Make sure insns to set the frame pointer aren't deleted. */ 239190075Sobrien if (regno == FRAME_POINTER_REGNUM 239252284Sobrien && (! reload_completed || frame_pointer_needed)) 239390075Sobrien return 0; 239418334Speter#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 239590075Sobrien if (regno == HARD_FRAME_POINTER_REGNUM 239652284Sobrien && (! reload_completed || frame_pointer_needed)) 239790075Sobrien return 0; 239818334Speter#endif 239990075Sobrien 240018334Speter#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 240118334Speter /* Make sure insns to set arg pointer are never deleted 240290075Sobrien (if the arg pointer isn't fixed, there will be a USE 240390075Sobrien for it, so we can treat it normally). */ 240490075Sobrien if (regno == ARG_POINTER_REGNUM && fixed_regs[regno]) 240590075Sobrien return 0; 240618334Speter#endif 240718334Speter 240890075Sobrien /* Otherwise, the set is dead. */ 240990075Sobrien return 1; 241018334Speter } 241118334Speter } 241218334Speter } 241350397Sobrien 241490075Sobrien /* If performing several activities, insn is dead if each activity 241590075Sobrien is individually dead. Also, CLOBBERs and USEs can be ignored; a 241690075Sobrien CLOBBER or USE that's inside a PARALLEL doesn't make the insn 241790075Sobrien worth keeping. */ 241818334Speter else if (code == PARALLEL) 241918334Speter { 242050397Sobrien int i = XVECLEN (x, 0); 242150397Sobrien 242218334Speter for (i--; i >= 0; i--) 242350397Sobrien if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER 242450397Sobrien && GET_CODE (XVECEXP (x, 0, i)) != USE 242590075Sobrien && ! insn_dead_p (pbi, XVECEXP (x, 0, i), call_ok, NULL_RTX)) 242650397Sobrien return 0; 242750397Sobrien 242818334Speter return 1; 242918334Speter } 243050397Sobrien 243150397Sobrien /* A CLOBBER of a pseudo-register that is dead serves no purpose. That 2432132718Skan is not necessarily true for hard registers until after reload. */ 2433132718Skan else if (code == CLOBBER) 2434132718Skan { 2435169689Skan if (REG_P (XEXP (x, 0)) 2436132718Skan && (REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER 2437132718Skan || reload_completed) 2438132718Skan && ! REGNO_REG_SET_P (pbi->reg_live, REGNO (XEXP (x, 0)))) 2439132718Skan return 1; 2440132718Skan } 244150397Sobrien 2442132718Skan /* ??? A base USE is a historical relic. It ought not be needed anymore. 2443132718Skan Instances where it is still used are either (1) temporary and the USE 2444132718Skan escaped the pass, (2) cruft and the USE need not be emitted anymore, 2445132718Skan or (3) hiding bugs elsewhere that are not properly representing data 2446132718Skan flow. */ 2447132718Skan 244818334Speter return 0; 244918334Speter} 245018334Speter 245190075Sobrien/* If INSN is the last insn in a libcall, and assuming INSN is dead, 245218334Speter return 1 if the entire library call is dead. 245390075Sobrien This is true if INSN copies a register (hard or pseudo) 245490075Sobrien and if the hard return reg of the call insn is dead. 245590075Sobrien (The caller should have tested the destination of the SET inside 245690075Sobrien INSN already for death.) 245718334Speter 245818334Speter If this insn doesn't just copy a register, then we don't 245918334Speter have an ordinary libcall. In that case, cse could not have 246018334Speter managed to substitute the source for the dest later on, 246118334Speter so we can assume the libcall is dead. 246218334Speter 246390075Sobrien PBI is the block info giving pseudoregs live before this insn. 246490075Sobrien NOTE is the REG_RETVAL note of the insn. */ 246518334Speter 246618334Speterstatic int 2467132718Skanlibcall_dead_p (struct propagate_block_info *pbi, rtx note, rtx insn) 246818334Speter{ 246990075Sobrien rtx x = single_set (insn); 247018334Speter 247190075Sobrien if (x) 247218334Speter { 247390075Sobrien rtx r = SET_SRC (x); 247490075Sobrien 2475169689Skan if (REG_P (r) || GET_CODE (r) == SUBREG) 247618334Speter { 247718334Speter rtx call = XEXP (note, 0); 247852284Sobrien rtx call_pat; 247990075Sobrien int i; 248018334Speter 248118334Speter /* Find the call insn. */ 2482169689Skan while (call != insn && !CALL_P (call)) 248318334Speter call = NEXT_INSN (call); 248418334Speter 248518334Speter /* If there is none, do nothing special, 248618334Speter since ordinary death handling can understand these insns. */ 248718334Speter if (call == insn) 248818334Speter return 0; 248918334Speter 249018334Speter /* See if the hard reg holding the value is dead. 249118334Speter If this is a PARALLEL, find the call within it. */ 249252284Sobrien call_pat = PATTERN (call); 249352284Sobrien if (GET_CODE (call_pat) == PARALLEL) 249418334Speter { 249552284Sobrien for (i = XVECLEN (call_pat, 0) - 1; i >= 0; i--) 249652284Sobrien if (GET_CODE (XVECEXP (call_pat, 0, i)) == SET 249752284Sobrien && GET_CODE (SET_SRC (XVECEXP (call_pat, 0, i))) == CALL) 249818334Speter break; 249918334Speter 250018334Speter /* This may be a library call that is returning a value 250118334Speter via invisible pointer. Do nothing special, since 250218334Speter ordinary death handling can understand these insns. */ 250318334Speter if (i < 0) 250418334Speter return 0; 250518334Speter 250652284Sobrien call_pat = XVECEXP (call_pat, 0, i); 250718334Speter } 250818334Speter 2509146895Skan if (! insn_dead_p (pbi, call_pat, 1, REG_NOTES (call))) 2510146895Skan return 0; 2511146895Skan 2512146895Skan while ((insn = PREV_INSN (insn)) != call) 2513146895Skan { 2514146895Skan if (! INSN_P (insn)) 2515146895Skan continue; 2516146895Skan if (! insn_dead_p (pbi, PATTERN (insn), 0, REG_NOTES (insn))) 2517146895Skan return 0; 2518146895Skan } 2519146895Skan return 1; 252018334Speter } 252118334Speter } 2522146895Skan return 0; 252318334Speter} 252418334Speter 252518334Speter/* 1 if register REGNO was alive at a place where `setjmp' was called 252618334Speter and was set more than once or is an argument. 252718334Speter Such regs may be clobbered by `longjmp'. */ 252818334Speter 252918334Speterint 2530132718Skanregno_clobbered_at_setjmp (int regno) 253118334Speter{ 2532169689Skan if (n_basic_blocks == NUM_FIXED_BLOCKS) 253318334Speter return 0; 253418334Speter 253550397Sobrien return ((REG_N_SETS (regno) > 1 2536169689Skan || REGNO_REG_SET_P (ENTRY_BLOCK_PTR->il.rtl->global_live_at_end, 2537169689Skan regno)) 253850397Sobrien && REGNO_REG_SET_P (regs_live_at_setjmp, regno)); 253918334Speter} 254018334Speter 254190075Sobrien/* Add MEM to PBI->MEM_SET_LIST. MEM should be canonical. Respect the 254290075Sobrien maximal list size; look for overlaps in mode and select the largest. */ 254352284Sobrienstatic void 2544132718Skanadd_to_mem_set_list (struct propagate_block_info *pbi, rtx mem) 254552284Sobrien{ 254690075Sobrien rtx i; 254790075Sobrien 254890075Sobrien /* We don't know how large a BLKmode store is, so we must not 254990075Sobrien take them into consideration. */ 255090075Sobrien if (GET_MODE (mem) == BLKmode) 255190075Sobrien return; 255290075Sobrien 255390075Sobrien for (i = pbi->mem_set_list; i ; i = XEXP (i, 1)) 255452284Sobrien { 255590075Sobrien rtx e = XEXP (i, 0); 255690075Sobrien if (rtx_equal_p (XEXP (mem, 0), XEXP (e, 0))) 255790075Sobrien { 255890075Sobrien if (GET_MODE_SIZE (GET_MODE (mem)) > GET_MODE_SIZE (GET_MODE (e))) 255952284Sobrien { 256090075Sobrien#ifdef AUTO_INC_DEC 256190075Sobrien /* If we must store a copy of the mem, we can just modify 256290075Sobrien the mode of the stored copy. */ 256390075Sobrien if (pbi->flags & PROP_AUTOINC) 256490075Sobrien PUT_MODE (e, GET_MODE (mem)); 256552284Sobrien else 256690075Sobrien#endif 256790075Sobrien XEXP (i, 0) = mem; 256852284Sobrien } 256990075Sobrien return; 257052284Sobrien } 257152284Sobrien } 257290075Sobrien 2573169689Skan if (pbi->mem_set_list_len < PARAM_VALUE (PARAM_MAX_FLOW_MEMORY_LOCATIONS)) 257490075Sobrien { 257590075Sobrien#ifdef AUTO_INC_DEC 257690075Sobrien /* Store a copy of mem, otherwise the address may be 257790075Sobrien scrogged by find_auto_inc. */ 257890075Sobrien if (pbi->flags & PROP_AUTOINC) 257990075Sobrien mem = shallow_copy_rtx (mem); 258090075Sobrien#endif 258190075Sobrien pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list); 258290075Sobrien pbi->mem_set_list_len++; 258390075Sobrien } 258452284Sobrien} 258552284Sobrien 258690075Sobrien/* INSN references memory, possibly using autoincrement addressing modes. 258790075Sobrien Find any entries on the mem_set_list that need to be invalidated due 258890075Sobrien to an address change. */ 258918334Speter 2590117395Skanstatic int 2591132718Skaninvalidate_mems_from_autoinc (rtx *px, void *data) 259218334Speter{ 2593117395Skan rtx x = *px; 2594117395Skan struct propagate_block_info *pbi = data; 2595117395Skan 2596169689Skan if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC) 2597117395Skan { 2598117395Skan invalidate_mems_from_set (pbi, XEXP (x, 0)); 2599117395Skan return -1; 2600117395Skan } 2601117395Skan 2602117395Skan return 0; 260390075Sobrien} 260418334Speter 2605169689Skan/* EXP is a REG or MEM. Remove any dependent entries from 2606169689Skan pbi->mem_set_list. */ 260790075Sobrien 260890075Sobrienstatic void 2609132718Skaninvalidate_mems_from_set (struct propagate_block_info *pbi, rtx exp) 261090075Sobrien{ 261190075Sobrien rtx temp = pbi->mem_set_list; 261290075Sobrien rtx prev = NULL_RTX; 261390075Sobrien rtx next; 261490075Sobrien 261590075Sobrien while (temp) 261618334Speter { 261790075Sobrien next = XEXP (temp, 1); 2618169689Skan if ((REG_P (exp) && reg_overlap_mentioned_p (exp, XEXP (temp, 0))) 2619169689Skan /* When we get an EXP that is a mem here, we want to check if EXP 2620169689Skan overlaps the *address* of any of the mems in the list (i.e. not 2621169689Skan whether the mems actually overlap; that's done elsewhere). */ 2622169689Skan || (MEM_P (exp) 2623169689Skan && reg_overlap_mentioned_p (exp, XEXP (XEXP (temp, 0), 0)))) 262418334Speter { 262590075Sobrien /* Splice this entry out of the list. */ 262690075Sobrien if (prev) 262790075Sobrien XEXP (prev, 1) = next; 262890075Sobrien else 262990075Sobrien pbi->mem_set_list = next; 263090075Sobrien free_EXPR_LIST_node (temp); 263190075Sobrien pbi->mem_set_list_len--; 263218334Speter } 263390075Sobrien else 263490075Sobrien prev = temp; 263590075Sobrien temp = next; 263618334Speter } 263718334Speter} 263818334Speter 263990075Sobrien/* Process the registers that are set within X. Their bits are set to 264090075Sobrien 1 in the regset DEAD, because they are dead prior to this insn. 264118334Speter 264290075Sobrien If INSN is nonzero, it is the insn being processed. 264390075Sobrien 264490075Sobrien FLAGS is the set of operations to perform. */ 264590075Sobrien 264618334Speterstatic void 2647132718Skanmark_set_regs (struct propagate_block_info *pbi, rtx x, rtx insn) 264818334Speter{ 264990075Sobrien rtx cond = NULL_RTX; 265090075Sobrien rtx link; 265190075Sobrien enum rtx_code code; 2652132718Skan int flags = pbi->flags; 265318334Speter 265490075Sobrien if (insn) 265590075Sobrien for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 265690075Sobrien { 265790075Sobrien if (REG_NOTE_KIND (link) == REG_INC) 265890075Sobrien mark_set_1 (pbi, SET, XEXP (link, 0), 265990075Sobrien (GET_CODE (x) == COND_EXEC 266090075Sobrien ? COND_EXEC_TEST (x) : NULL_RTX), 2661132718Skan insn, flags); 266290075Sobrien } 266390075Sobrien retry: 266490075Sobrien switch (code = GET_CODE (x)) 266552284Sobrien { 266690075Sobrien case SET: 2667132718Skan if (GET_CODE (XEXP (x, 1)) == ASM_OPERANDS) 2668132718Skan flags |= PROP_ASM_SCAN; 2669132718Skan /* Fall through */ 267090075Sobrien case CLOBBER: 2671132718Skan mark_set_1 (pbi, code, SET_DEST (x), cond, insn, flags); 267290075Sobrien return; 267352284Sobrien 267490075Sobrien case COND_EXEC: 267590075Sobrien cond = COND_EXEC_TEST (x); 267690075Sobrien x = COND_EXEC_CODE (x); 267790075Sobrien goto retry; 267890075Sobrien 267990075Sobrien case PARALLEL: 268090075Sobrien { 268190075Sobrien int i; 268290075Sobrien 2683132718Skan /* We must scan forwards. If we have an asm, we need to set 2684132718Skan the PROP_ASM_SCAN flag before scanning the clobbers. */ 2685132718Skan for (i = 0; i < XVECLEN (x, 0); i++) 268690075Sobrien { 268790075Sobrien rtx sub = XVECEXP (x, 0, i); 268890075Sobrien switch (code = GET_CODE (sub)) 268990075Sobrien { 269090075Sobrien case COND_EXEC: 2691169689Skan gcc_assert (!cond); 269290075Sobrien 269390075Sobrien cond = COND_EXEC_TEST (sub); 269490075Sobrien sub = COND_EXEC_CODE (sub); 2695132718Skan if (GET_CODE (sub) == SET) 2696132718Skan goto mark_set; 2697132718Skan if (GET_CODE (sub) == CLOBBER) 2698132718Skan goto mark_clob; 2699132718Skan break; 270090075Sobrien 270190075Sobrien case SET: 2702132718Skan mark_set: 2703132718Skan if (GET_CODE (XEXP (sub, 1)) == ASM_OPERANDS) 2704132718Skan flags |= PROP_ASM_SCAN; 2705132718Skan /* Fall through */ 270690075Sobrien case CLOBBER: 2707132718Skan mark_clob: 2708132718Skan mark_set_1 (pbi, code, SET_DEST (sub), cond, insn, flags); 270990075Sobrien break; 271090075Sobrien 2711132718Skan case ASM_OPERANDS: 2712132718Skan flags |= PROP_ASM_SCAN; 2713132718Skan break; 2714132718Skan 271590075Sobrien default: 271690075Sobrien break; 271790075Sobrien } 271890075Sobrien } 271990075Sobrien break; 272090075Sobrien } 272190075Sobrien 272290075Sobrien default: 272390075Sobrien break; 272452284Sobrien } 272590075Sobrien} 272652284Sobrien 272790075Sobrien/* Process a single set, which appears in INSN. REG (which may not 272890075Sobrien actually be a REG, it may also be a SUBREG, PARALLEL, etc.) is 272990075Sobrien being set using the CODE (which may be SET, CLOBBER, or COND_EXEC). 273090075Sobrien If the set is conditional (because it appear in a COND_EXEC), COND 273190075Sobrien will be the condition. */ 273218334Speter 273390075Sobrienstatic void 2734132718Skanmark_set_1 (struct propagate_block_info *pbi, enum rtx_code code, rtx reg, rtx cond, rtx insn, int flags) 273590075Sobrien{ 273690075Sobrien int regno_first = -1, regno_last = -1; 273790075Sobrien unsigned long not_dead = 0; 273890075Sobrien int i; 273918334Speter 274090075Sobrien /* Modifying just one hardware register of a multi-reg value or just a 274190075Sobrien byte field of a register does not mean the value from before this insn 274290075Sobrien is now dead. Of course, if it was dead after it's unused now. */ 274318334Speter 274490075Sobrien switch (GET_CODE (reg)) 274552284Sobrien { 274690075Sobrien case PARALLEL: 274790075Sobrien /* Some targets place small structures in registers for return values of 274890075Sobrien functions. We have to detect this case specially here to get correct 274990075Sobrien flow information. */ 275090075Sobrien for (i = XVECLEN (reg, 0) - 1; i >= 0; i--) 275190075Sobrien if (XEXP (XVECEXP (reg, 0, i), 0) != 0) 275290075Sobrien mark_set_1 (pbi, code, XEXP (XVECEXP (reg, 0, i), 0), cond, insn, 275390075Sobrien flags); 275490075Sobrien return; 275552284Sobrien 2756169689Skan case SIGN_EXTRACT: 2757169689Skan /* SIGN_EXTRACT cannot be an lvalue. */ 2758169689Skan gcc_unreachable (); 2759169689Skan 276090075Sobrien case ZERO_EXTRACT: 276190075Sobrien case STRICT_LOW_PART: 276290075Sobrien /* ??? Assumes STRICT_LOW_PART not used on multi-word registers. */ 276390075Sobrien do 276490075Sobrien reg = XEXP (reg, 0); 276590075Sobrien while (GET_CODE (reg) == SUBREG 276690075Sobrien || GET_CODE (reg) == ZERO_EXTRACT 276790075Sobrien || GET_CODE (reg) == STRICT_LOW_PART); 2768169689Skan if (MEM_P (reg)) 276990075Sobrien break; 277090075Sobrien not_dead = (unsigned long) REGNO_REG_SET_P (pbi->reg_live, REGNO (reg)); 277190075Sobrien /* Fall through. */ 277290075Sobrien 277390075Sobrien case REG: 277490075Sobrien regno_last = regno_first = REGNO (reg); 277590075Sobrien if (regno_first < FIRST_PSEUDO_REGISTER) 2776169689Skan regno_last += hard_regno_nregs[regno_first][GET_MODE (reg)] - 1; 277790075Sobrien break; 277890075Sobrien 277990075Sobrien case SUBREG: 2780169689Skan if (REG_P (SUBREG_REG (reg))) 278152284Sobrien { 278290075Sobrien enum machine_mode outer_mode = GET_MODE (reg); 278390075Sobrien enum machine_mode inner_mode = GET_MODE (SUBREG_REG (reg)); 278490075Sobrien 278590075Sobrien /* Identify the range of registers affected. This is moderately 278690075Sobrien tricky for hard registers. See alter_subreg. */ 278790075Sobrien 278890075Sobrien regno_last = regno_first = REGNO (SUBREG_REG (reg)); 278990075Sobrien if (regno_first < FIRST_PSEUDO_REGISTER) 279052284Sobrien { 279190075Sobrien regno_first += subreg_regno_offset (regno_first, inner_mode, 279290075Sobrien SUBREG_BYTE (reg), 279390075Sobrien outer_mode); 279490075Sobrien regno_last = (regno_first 2795169689Skan + hard_regno_nregs[regno_first][outer_mode] - 1); 279690075Sobrien 279790075Sobrien /* Since we've just adjusted the register number ranges, make 279890075Sobrien sure REG matches. Otherwise some_was_live will be clear 279990075Sobrien when it shouldn't have been, and we'll create incorrect 280090075Sobrien REG_UNUSED notes. */ 280190075Sobrien reg = gen_rtx_REG (outer_mode, regno_first); 280252284Sobrien } 280352284Sobrien else 280490075Sobrien { 280590075Sobrien /* If the number of words in the subreg is less than the number 280690075Sobrien of words in the full register, we have a well-defined partial 280790075Sobrien set. Otherwise the high bits are undefined. 280890075Sobrien 280990075Sobrien This is only really applicable to pseudos, since we just took 281090075Sobrien care of multi-word hard registers. */ 281190075Sobrien if (((GET_MODE_SIZE (outer_mode) 281290075Sobrien + UNITS_PER_WORD - 1) / UNITS_PER_WORD) 281390075Sobrien < ((GET_MODE_SIZE (inner_mode) 281490075Sobrien + UNITS_PER_WORD - 1) / UNITS_PER_WORD)) 281590075Sobrien not_dead = (unsigned long) REGNO_REG_SET_P (pbi->reg_live, 281690075Sobrien regno_first); 281790075Sobrien 281890075Sobrien reg = SUBREG_REG (reg); 281990075Sobrien } 282052284Sobrien } 282190075Sobrien else 282290075Sobrien reg = SUBREG_REG (reg); 282390075Sobrien break; 282490075Sobrien 282590075Sobrien default: 282690075Sobrien break; 282752284Sobrien } 282852284Sobrien 2829169689Skan /* If this set is a MEM, then it kills any aliased writes and any 2830169689Skan other MEMs which use it. 283190075Sobrien If this set is a REG, then it kills any MEMs which use the reg. */ 2832117395Skan if (optimize && (flags & PROP_SCAN_DEAD_STORES)) 283390075Sobrien { 2834169689Skan if (REG_P (reg) || MEM_P (reg)) 283590075Sobrien invalidate_mems_from_set (pbi, reg); 283652284Sobrien 283790075Sobrien /* If the memory reference had embedded side effects (autoincrement 2838169689Skan address modes) then we may need to kill some entries on the 283990075Sobrien memory set list. */ 2840169689Skan if (insn && MEM_P (reg)) 2841117395Skan for_each_rtx (&PATTERN (insn), invalidate_mems_from_autoinc, pbi); 284218334Speter 2843169689Skan if (MEM_P (reg) && ! side_effects_p (reg) 284490075Sobrien /* ??? With more effort we could track conditional memory life. */ 2845117395Skan && ! cond) 2846117395Skan add_to_mem_set_list (pbi, canon_rtx (reg)); 284790075Sobrien } 284890075Sobrien 2849169689Skan if (REG_P (reg) 285090075Sobrien && ! (regno_first == FRAME_POINTER_REGNUM 285190075Sobrien && (! reload_completed || frame_pointer_needed)) 285218334Speter#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 285390075Sobrien && ! (regno_first == HARD_FRAME_POINTER_REGNUM 285452284Sobrien && (! reload_completed || frame_pointer_needed)) 285518334Speter#endif 285618334Speter#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 285790075Sobrien && ! (regno_first == ARG_POINTER_REGNUM && fixed_regs[regno_first]) 285818334Speter#endif 285990075Sobrien ) 286018334Speter { 286190075Sobrien int some_was_live = 0, some_was_dead = 0; 286218334Speter 286390075Sobrien for (i = regno_first; i <= regno_last; ++i) 286490075Sobrien { 286590075Sobrien int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i); 286690075Sobrien if (pbi->local_set) 286790075Sobrien { 286890075Sobrien /* Order of the set operation matters here since both 286990075Sobrien sets may be the same. */ 287090075Sobrien CLEAR_REGNO_REG_SET (pbi->cond_local_set, i); 287190075Sobrien if (cond != NULL_RTX 287290075Sobrien && ! REGNO_REG_SET_P (pbi->local_set, i)) 287390075Sobrien SET_REGNO_REG_SET (pbi->cond_local_set, i); 287490075Sobrien else 287590075Sobrien SET_REGNO_REG_SET (pbi->local_set, i); 287690075Sobrien } 2877169689Skan if (code != CLOBBER || needed_regno) 287890075Sobrien SET_REGNO_REG_SET (pbi->new_set, i); 287918334Speter 288090075Sobrien some_was_live |= needed_regno; 288190075Sobrien some_was_dead |= ! needed_regno; 288290075Sobrien } 288318334Speter 288490075Sobrien#ifdef HAVE_conditional_execution 288590075Sobrien /* Consider conditional death in deciding that the register needs 288690075Sobrien a death note. */ 288790075Sobrien if (some_was_live && ! not_dead 288890075Sobrien /* The stack pointer is never dead. Well, not strictly true, 288990075Sobrien but it's very difficult to tell from here. Hopefully 289090075Sobrien combine_stack_adjustments will fix up the most egregious 289190075Sobrien errors. */ 289290075Sobrien && regno_first != STACK_POINTER_REGNUM) 289318334Speter { 289490075Sobrien for (i = regno_first; i <= regno_last; ++i) 289590075Sobrien if (! mark_regno_cond_dead (pbi, i, cond)) 289690075Sobrien not_dead |= ((unsigned long) 1) << (i - regno_first); 289790075Sobrien } 289890075Sobrien#endif 289918334Speter 290090075Sobrien /* Additional data to record if this is the final pass. */ 290190075Sobrien if (flags & (PROP_LOG_LINKS | PROP_REG_INFO 290290075Sobrien | PROP_DEATH_NOTES | PROP_AUTOINC)) 290390075Sobrien { 290490075Sobrien rtx y; 290590075Sobrien int blocknum = pbi->bb->index; 290618334Speter 290790075Sobrien y = NULL_RTX; 290890075Sobrien if (flags & (PROP_LOG_LINKS | PROP_AUTOINC)) 290918334Speter { 291090075Sobrien y = pbi->reg_next_use[regno_first]; 291150397Sobrien 291290075Sobrien /* The next use is no longer next, since a store intervenes. */ 291390075Sobrien for (i = regno_first; i <= regno_last; ++i) 291490075Sobrien pbi->reg_next_use[i] = 0; 291518334Speter } 291618334Speter 291790075Sobrien if (flags & PROP_REG_INFO) 291818334Speter { 291990075Sobrien for (i = regno_first; i <= regno_last; ++i) 292018334Speter { 292190075Sobrien /* Count (weighted) references, stores, etc. This counts a 292290075Sobrien register twice if it is modified, but that is correct. */ 292390075Sobrien REG_N_SETS (i) += 1; 292490075Sobrien REG_N_REFS (i) += 1; 292590075Sobrien REG_FREQ (i) += REG_FREQ_FROM_BB (pbi->bb); 292618334Speter 292790075Sobrien /* The insns where a reg is live are normally counted 292890075Sobrien elsewhere, but we want the count to include the insn 292990075Sobrien where the reg is set, and the normal counting mechanism 293090075Sobrien would not count it. */ 293190075Sobrien REG_LIVE_LENGTH (i) += 1; 293218334Speter } 293318334Speter 293490075Sobrien /* If this is a hard reg, record this function uses the reg. */ 293590075Sobrien if (regno_first < FIRST_PSEUDO_REGISTER) 293690075Sobrien { 293790075Sobrien for (i = regno_first; i <= regno_last; i++) 293890075Sobrien regs_ever_live[i] = 1; 2939132718Skan if (flags & PROP_ASM_SCAN) 2940132718Skan for (i = regno_first; i <= regno_last; i++) 2941132718Skan regs_asm_clobbered[i] = 1; 294290075Sobrien } 294390075Sobrien else 294490075Sobrien { 294590075Sobrien /* Keep track of which basic blocks each reg appears in. */ 294690075Sobrien if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN) 294790075Sobrien REG_BASIC_BLOCK (regno_first) = blocknum; 294890075Sobrien else if (REG_BASIC_BLOCK (regno_first) != blocknum) 294990075Sobrien REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL; 295090075Sobrien } 295118334Speter } 295218334Speter 295390075Sobrien if (! some_was_dead) 295418334Speter { 295590075Sobrien if (flags & PROP_LOG_LINKS) 295690075Sobrien { 295790075Sobrien /* Make a logical link from the next following insn 295890075Sobrien that uses this register, back to this insn. 295990075Sobrien The following insns have already been processed. 296018334Speter 296190075Sobrien We don't build a LOG_LINK for hard registers containing 296290075Sobrien in ASM_OPERANDs. If these registers get replaced, 296390075Sobrien we might wind up changing the semantics of the insn, 296490075Sobrien even if reload can make what appear to be valid 2965132718Skan assignments later. 2966132718Skan 2967132718Skan We don't build a LOG_LINK for global registers to 2968132718Skan or from a function call. We don't want to let 2969132718Skan combine think that it knows what is going on with 2970132718Skan global registers. */ 297190075Sobrien if (y && (BLOCK_NUM (y) == blocknum) 297290075Sobrien && (regno_first >= FIRST_PSEUDO_REGISTER 2973132718Skan || (asm_noperands (PATTERN (y)) < 0 2974169689Skan && ! ((CALL_P (insn) 2975169689Skan || CALL_P (y)) 2976132718Skan && global_regs[regno_first])))) 297790075Sobrien LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y)); 297890075Sobrien } 297918334Speter } 298090075Sobrien else if (not_dead) 298190075Sobrien ; 298290075Sobrien else if (! some_was_live) 298318334Speter { 298490075Sobrien if (flags & PROP_REG_INFO) 298590075Sobrien REG_N_DEATHS (regno_first) += 1; 298690075Sobrien 2987169689Skan if (flags & PROP_DEATH_NOTES 2988169689Skan#ifdef STACK_REGS 2989169689Skan && (!(flags & PROP_POST_REGSTACK) 2990169689Skan || !IN_RANGE (REGNO (reg), FIRST_STACK_REG, 2991169689Skan LAST_STACK_REG)) 2992169689Skan#endif 2993169689Skan ) 299490075Sobrien { 299590075Sobrien /* Note that dead stores have already been deleted 299690075Sobrien when possible. If we get here, we have found a 299790075Sobrien dead store that cannot be eliminated (because the 299890075Sobrien same insn does something useful). Indicate this 299990075Sobrien by marking the reg being set as dying here. */ 300090075Sobrien REG_NOTES (insn) 300190075Sobrien = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn)); 300290075Sobrien } 300318334Speter } 300418334Speter else 300518334Speter { 3006169689Skan if (flags & PROP_DEATH_NOTES 3007169689Skan#ifdef STACK_REGS 3008169689Skan && (!(flags & PROP_POST_REGSTACK) 3009169689Skan || !IN_RANGE (REGNO (reg), FIRST_STACK_REG, 3010169689Skan LAST_STACK_REG)) 3011169689Skan#endif 3012169689Skan ) 301390075Sobrien { 301490075Sobrien /* This is a case where we have a multi-word hard register 301590075Sobrien and some, but not all, of the words of the register are 301690075Sobrien needed in subsequent insns. Write REG_UNUSED notes 301790075Sobrien for those parts that were not needed. This case should 301890075Sobrien be rare. */ 301918334Speter 302090075Sobrien for (i = regno_first; i <= regno_last; ++i) 302190075Sobrien if (! REGNO_REG_SET_P (pbi->reg_live, i)) 302290075Sobrien REG_NOTES (insn) 302390075Sobrien = alloc_EXPR_LIST (REG_UNUSED, 3024117395Skan regno_reg_rtx[i], 302590075Sobrien REG_NOTES (insn)); 302690075Sobrien } 302718334Speter } 302818334Speter } 302990075Sobrien 303090075Sobrien /* Mark the register as being dead. */ 303190075Sobrien if (some_was_live 303290075Sobrien /* The stack pointer is never dead. Well, not strictly true, 303390075Sobrien but it's very difficult to tell from here. Hopefully 303490075Sobrien combine_stack_adjustments will fix up the most egregious 303590075Sobrien errors. */ 303690075Sobrien && regno_first != STACK_POINTER_REGNUM) 303790075Sobrien { 303890075Sobrien for (i = regno_first; i <= regno_last; ++i) 303990075Sobrien if (!(not_dead & (((unsigned long) 1) << (i - regno_first)))) 3040169689Skan { 3041169689Skan if ((pbi->flags & PROP_REG_INFO) 3042169689Skan && REGNO_REG_SET_P (pbi->reg_live, i)) 3043169689Skan { 3044169689Skan REG_LIVE_LENGTH (i) += pbi->insn_num - reg_deaths[i]; 3045169689Skan reg_deaths[i] = 0; 3046169689Skan } 3047169689Skan CLEAR_REGNO_REG_SET (pbi->reg_live, i); 3048169689Skan } 3049169689Skan if (flags & PROP_DEAD_INSN) 3050169689Skan emit_insn_after (gen_rtx_CLOBBER (VOIDmode, reg), insn); 305190075Sobrien } 305218334Speter } 3053169689Skan else if (REG_P (reg)) 305490075Sobrien { 305590075Sobrien if (flags & (PROP_LOG_LINKS | PROP_AUTOINC)) 305690075Sobrien pbi->reg_next_use[regno_first] = 0; 3057132718Skan 3058132718Skan if ((flags & PROP_REG_INFO) != 0 3059132718Skan && (flags & PROP_ASM_SCAN) != 0 3060132718Skan && regno_first < FIRST_PSEUDO_REGISTER) 3061132718Skan { 3062132718Skan for (i = regno_first; i <= regno_last; i++) 3063132718Skan regs_asm_clobbered[i] = 1; 3064132718Skan } 306590075Sobrien } 306618334Speter 306718334Speter /* If this is the last pass and this is a SCRATCH, show it will be dying 306818334Speter here and count it. */ 306990075Sobrien else if (GET_CODE (reg) == SCRATCH) 307018334Speter { 3071169689Skan if (flags & PROP_DEATH_NOTES 3072169689Skan#ifdef STACK_REGS 3073169689Skan && (!(flags & PROP_POST_REGSTACK) 3074169689Skan || !IN_RANGE (REGNO (reg), FIRST_STACK_REG, LAST_STACK_REG)) 3075169689Skan#endif 3076169689Skan ) 307790075Sobrien REG_NOTES (insn) 307890075Sobrien = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn)); 307918334Speter } 308018334Speter} 308118334Speter 308290075Sobrien#ifdef HAVE_conditional_execution 308390075Sobrien/* Mark REGNO conditionally dead. 308490075Sobrien Return true if the register is now unconditionally dead. */ 308590075Sobrien 308690075Sobrienstatic int 3087132718Skanmark_regno_cond_dead (struct propagate_block_info *pbi, int regno, rtx cond) 308890075Sobrien{ 308990075Sobrien /* If this is a store to a predicate register, the value of the 309090075Sobrien predicate is changing, we don't know that the predicate as seen 309190075Sobrien before is the same as that seen after. Flush all dependent 309290075Sobrien conditions from reg_cond_dead. This will make all such 309390075Sobrien conditionally live registers unconditionally live. */ 309490075Sobrien if (REGNO_REG_SET_P (pbi->reg_cond_reg, regno)) 309590075Sobrien flush_reg_cond_reg (pbi, regno); 309690075Sobrien 309790075Sobrien /* If this is an unconditional store, remove any conditional 309890075Sobrien life that may have existed. */ 309990075Sobrien if (cond == NULL_RTX) 310090075Sobrien splay_tree_remove (pbi->reg_cond_dead, regno); 310190075Sobrien else 310290075Sobrien { 310390075Sobrien splay_tree_node node; 310490075Sobrien struct reg_cond_life_info *rcli; 310590075Sobrien rtx ncond; 310690075Sobrien 310790075Sobrien /* Otherwise this is a conditional set. Record that fact. 310890075Sobrien It may have been conditionally used, or there may be a 3109169689Skan subsequent set with a complementary condition. */ 311090075Sobrien 311190075Sobrien node = splay_tree_lookup (pbi->reg_cond_dead, regno); 311290075Sobrien if (node == NULL) 311390075Sobrien { 311490075Sobrien /* The register was unconditionally live previously. 311590075Sobrien Record the current condition as the condition under 311690075Sobrien which it is dead. */ 3117169689Skan rcli = XNEW (struct reg_cond_life_info); 311890075Sobrien rcli->condition = cond; 311990075Sobrien rcli->stores = cond; 312090075Sobrien rcli->orig_condition = const0_rtx; 312190075Sobrien splay_tree_insert (pbi->reg_cond_dead, regno, 312290075Sobrien (splay_tree_value) rcli); 312390075Sobrien 312490075Sobrien SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0))); 312590075Sobrien 312690075Sobrien /* Not unconditionally dead. */ 312790075Sobrien return 0; 312890075Sobrien } 312990075Sobrien else 313090075Sobrien { 313190075Sobrien /* The register was conditionally live previously. 313290075Sobrien Add the new condition to the old. */ 313390075Sobrien rcli = (struct reg_cond_life_info *) node->value; 313490075Sobrien ncond = rcli->condition; 313590075Sobrien ncond = ior_reg_cond (ncond, cond, 1); 313690075Sobrien if (rcli->stores == const0_rtx) 313790075Sobrien rcli->stores = cond; 313890075Sobrien else if (rcli->stores != const1_rtx) 313990075Sobrien rcli->stores = ior_reg_cond (rcli->stores, cond, 1); 314090075Sobrien 314190075Sobrien /* If the register is now unconditionally dead, remove the entry 314290075Sobrien in the splay_tree. A register is unconditionally dead if the 314390075Sobrien dead condition ncond is true. A register is also unconditionally 314490075Sobrien dead if the sum of all conditional stores is an unconditional 314590075Sobrien store (stores is true), and the dead condition is identically the 314690075Sobrien same as the original dead condition initialized at the end of 314790075Sobrien the block. This is a pointer compare, not an rtx_equal_p 314890075Sobrien compare. */ 314990075Sobrien if (ncond == const1_rtx 315090075Sobrien || (ncond == rcli->orig_condition && rcli->stores == const1_rtx)) 315190075Sobrien splay_tree_remove (pbi->reg_cond_dead, regno); 315290075Sobrien else 315390075Sobrien { 315490075Sobrien rcli->condition = ncond; 315590075Sobrien 315690075Sobrien SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0))); 315790075Sobrien 315890075Sobrien /* Not unconditionally dead. */ 315990075Sobrien return 0; 316090075Sobrien } 316190075Sobrien } 316290075Sobrien } 316390075Sobrien 316490075Sobrien return 1; 316590075Sobrien} 316690075Sobrien 316790075Sobrien/* Called from splay_tree_delete for pbi->reg_cond_life. */ 316890075Sobrien 316990075Sobrienstatic void 3170132718Skanfree_reg_cond_life_info (splay_tree_value value) 317190075Sobrien{ 317290075Sobrien struct reg_cond_life_info *rcli = (struct reg_cond_life_info *) value; 317390075Sobrien free (rcli); 317490075Sobrien} 317590075Sobrien 317690075Sobrien/* Helper function for flush_reg_cond_reg. */ 317790075Sobrien 317890075Sobrienstatic int 3179132718Skanflush_reg_cond_reg_1 (splay_tree_node node, void *data) 318090075Sobrien{ 318190075Sobrien struct reg_cond_life_info *rcli; 318290075Sobrien int *xdata = (int *) data; 318390075Sobrien unsigned int regno = xdata[0]; 318490075Sobrien 318590075Sobrien /* Don't need to search if last flushed value was farther on in 318690075Sobrien the in-order traversal. */ 318790075Sobrien if (xdata[1] >= (int) node->key) 318890075Sobrien return 0; 318990075Sobrien 319090075Sobrien /* Splice out portions of the expression that refer to regno. */ 319190075Sobrien rcli = (struct reg_cond_life_info *) node->value; 319290075Sobrien rcli->condition = elim_reg_cond (rcli->condition, regno); 319390075Sobrien if (rcli->stores != const0_rtx && rcli->stores != const1_rtx) 319490075Sobrien rcli->stores = elim_reg_cond (rcli->stores, regno); 319590075Sobrien 319690075Sobrien /* If the entire condition is now false, signal the node to be removed. */ 319790075Sobrien if (rcli->condition == const0_rtx) 319890075Sobrien { 319990075Sobrien xdata[1] = node->key; 320090075Sobrien return -1; 320190075Sobrien } 3202169689Skan else 3203169689Skan gcc_assert (rcli->condition != const1_rtx); 320490075Sobrien 320590075Sobrien return 0; 320690075Sobrien} 320790075Sobrien 320890075Sobrien/* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE. */ 320990075Sobrien 321090075Sobrienstatic void 3211132718Skanflush_reg_cond_reg (struct propagate_block_info *pbi, int regno) 321290075Sobrien{ 321390075Sobrien int pair[2]; 321490075Sobrien 321590075Sobrien pair[0] = regno; 321690075Sobrien pair[1] = -1; 321790075Sobrien while (splay_tree_foreach (pbi->reg_cond_dead, 321890075Sobrien flush_reg_cond_reg_1, pair) == -1) 321990075Sobrien splay_tree_remove (pbi->reg_cond_dead, pair[1]); 322090075Sobrien 322190075Sobrien CLEAR_REGNO_REG_SET (pbi->reg_cond_reg, regno); 322290075Sobrien} 322390075Sobrien 322490075Sobrien/* Logical arithmetic on predicate conditions. IOR, NOT and AND. 322590075Sobrien For ior/and, the ADD flag determines whether we want to add the new 322690075Sobrien condition X to the old one unconditionally. If it is zero, we will 322790075Sobrien only return a new expression if X allows us to simplify part of 322890075Sobrien OLD, otherwise we return NULL to the caller. 322990075Sobrien If ADD is nonzero, we will return a new condition in all cases. The 323090075Sobrien toplevel caller of one of these functions should always pass 1 for 323190075Sobrien ADD. */ 323290075Sobrien 323390075Sobrienstatic rtx 3234132718Skanior_reg_cond (rtx old, rtx x, int add) 323590075Sobrien{ 323690075Sobrien rtx op0, op1; 323790075Sobrien 3238169689Skan if (COMPARISON_P (old)) 323990075Sobrien { 3240169689Skan if (COMPARISON_P (x) 3241169689Skan && REVERSE_CONDEXEC_PREDICATES_P (x, old) 324290075Sobrien && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0))) 324390075Sobrien return const1_rtx; 324490075Sobrien if (GET_CODE (x) == GET_CODE (old) 324590075Sobrien && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0))) 324690075Sobrien return old; 324790075Sobrien if (! add) 324890075Sobrien return NULL; 324990075Sobrien return gen_rtx_IOR (0, old, x); 325090075Sobrien } 325190075Sobrien 325290075Sobrien switch (GET_CODE (old)) 325390075Sobrien { 325490075Sobrien case IOR: 325590075Sobrien op0 = ior_reg_cond (XEXP (old, 0), x, 0); 325690075Sobrien op1 = ior_reg_cond (XEXP (old, 1), x, 0); 325790075Sobrien if (op0 != NULL || op1 != NULL) 325890075Sobrien { 325990075Sobrien if (op0 == const0_rtx) 326090075Sobrien return op1 ? op1 : gen_rtx_IOR (0, XEXP (old, 1), x); 326190075Sobrien if (op1 == const0_rtx) 326290075Sobrien return op0 ? op0 : gen_rtx_IOR (0, XEXP (old, 0), x); 326390075Sobrien if (op0 == const1_rtx || op1 == const1_rtx) 326490075Sobrien return const1_rtx; 326590075Sobrien if (op0 == NULL) 326690075Sobrien op0 = gen_rtx_IOR (0, XEXP (old, 0), x); 326790075Sobrien else if (rtx_equal_p (x, op0)) 326890075Sobrien /* (x | A) | x ~ (x | A). */ 326990075Sobrien return old; 327090075Sobrien if (op1 == NULL) 327190075Sobrien op1 = gen_rtx_IOR (0, XEXP (old, 1), x); 327290075Sobrien else if (rtx_equal_p (x, op1)) 327390075Sobrien /* (A | x) | x ~ (A | x). */ 327490075Sobrien return old; 327590075Sobrien return gen_rtx_IOR (0, op0, op1); 327690075Sobrien } 327790075Sobrien if (! add) 327890075Sobrien return NULL; 327990075Sobrien return gen_rtx_IOR (0, old, x); 328090075Sobrien 328190075Sobrien case AND: 328290075Sobrien op0 = ior_reg_cond (XEXP (old, 0), x, 0); 328390075Sobrien op1 = ior_reg_cond (XEXP (old, 1), x, 0); 328490075Sobrien if (op0 != NULL || op1 != NULL) 328590075Sobrien { 328690075Sobrien if (op0 == const1_rtx) 328790075Sobrien return op1 ? op1 : gen_rtx_IOR (0, XEXP (old, 1), x); 328890075Sobrien if (op1 == const1_rtx) 328990075Sobrien return op0 ? op0 : gen_rtx_IOR (0, XEXP (old, 0), x); 329090075Sobrien if (op0 == const0_rtx || op1 == const0_rtx) 329190075Sobrien return const0_rtx; 329290075Sobrien if (op0 == NULL) 329390075Sobrien op0 = gen_rtx_IOR (0, XEXP (old, 0), x); 329490075Sobrien else if (rtx_equal_p (x, op0)) 329590075Sobrien /* (x & A) | x ~ x. */ 329690075Sobrien return op0; 329790075Sobrien if (op1 == NULL) 329890075Sobrien op1 = gen_rtx_IOR (0, XEXP (old, 1), x); 329990075Sobrien else if (rtx_equal_p (x, op1)) 330090075Sobrien /* (A & x) | x ~ x. */ 330190075Sobrien return op1; 330290075Sobrien return gen_rtx_AND (0, op0, op1); 330390075Sobrien } 330490075Sobrien if (! add) 330590075Sobrien return NULL; 330690075Sobrien return gen_rtx_IOR (0, old, x); 330790075Sobrien 330890075Sobrien case NOT: 330990075Sobrien op0 = and_reg_cond (XEXP (old, 0), not_reg_cond (x), 0); 331090075Sobrien if (op0 != NULL) 331190075Sobrien return not_reg_cond (op0); 331290075Sobrien if (! add) 331390075Sobrien return NULL; 331490075Sobrien return gen_rtx_IOR (0, old, x); 331590075Sobrien 331690075Sobrien default: 3317169689Skan gcc_unreachable (); 331890075Sobrien } 331990075Sobrien} 332090075Sobrien 332190075Sobrienstatic rtx 3322132718Skannot_reg_cond (rtx x) 332390075Sobrien{ 332490075Sobrien if (x == const0_rtx) 332590075Sobrien return const1_rtx; 332690075Sobrien else if (x == const1_rtx) 332790075Sobrien return const0_rtx; 3328169689Skan if (GET_CODE (x) == NOT) 332990075Sobrien return XEXP (x, 0); 3330169689Skan if (COMPARISON_P (x) 3331169689Skan && REG_P (XEXP (x, 0))) 333290075Sobrien { 3333169689Skan gcc_assert (XEXP (x, 1) == const0_rtx); 333490075Sobrien 3335169689Skan return gen_rtx_fmt_ee (reversed_comparison_code (x, NULL), 333690075Sobrien VOIDmode, XEXP (x, 0), const0_rtx); 333790075Sobrien } 333890075Sobrien return gen_rtx_NOT (0, x); 333990075Sobrien} 334090075Sobrien 334190075Sobrienstatic rtx 3342132718Skanand_reg_cond (rtx old, rtx x, int add) 334390075Sobrien{ 334490075Sobrien rtx op0, op1; 334590075Sobrien 3346169689Skan if (COMPARISON_P (old)) 334790075Sobrien { 3348169689Skan if (COMPARISON_P (x) 3349169689Skan && GET_CODE (x) == reversed_comparison_code (old, NULL) 335090075Sobrien && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0))) 335190075Sobrien return const0_rtx; 335290075Sobrien if (GET_CODE (x) == GET_CODE (old) 335390075Sobrien && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0))) 335490075Sobrien return old; 335590075Sobrien if (! add) 335690075Sobrien return NULL; 335790075Sobrien return gen_rtx_AND (0, old, x); 335890075Sobrien } 335990075Sobrien 336090075Sobrien switch (GET_CODE (old)) 336190075Sobrien { 336290075Sobrien case IOR: 336390075Sobrien op0 = and_reg_cond (XEXP (old, 0), x, 0); 336490075Sobrien op1 = and_reg_cond (XEXP (old, 1), x, 0); 336590075Sobrien if (op0 != NULL || op1 != NULL) 336690075Sobrien { 336790075Sobrien if (op0 == const0_rtx) 336890075Sobrien return op1 ? op1 : gen_rtx_AND (0, XEXP (old, 1), x); 336990075Sobrien if (op1 == const0_rtx) 337090075Sobrien return op0 ? op0 : gen_rtx_AND (0, XEXP (old, 0), x); 337190075Sobrien if (op0 == const1_rtx || op1 == const1_rtx) 337290075Sobrien return const1_rtx; 337390075Sobrien if (op0 == NULL) 337490075Sobrien op0 = gen_rtx_AND (0, XEXP (old, 0), x); 337590075Sobrien else if (rtx_equal_p (x, op0)) 337690075Sobrien /* (x | A) & x ~ x. */ 337790075Sobrien return op0; 337890075Sobrien if (op1 == NULL) 337990075Sobrien op1 = gen_rtx_AND (0, XEXP (old, 1), x); 338090075Sobrien else if (rtx_equal_p (x, op1)) 338190075Sobrien /* (A | x) & x ~ x. */ 338290075Sobrien return op1; 338390075Sobrien return gen_rtx_IOR (0, op0, op1); 338490075Sobrien } 338590075Sobrien if (! add) 338690075Sobrien return NULL; 338790075Sobrien return gen_rtx_AND (0, old, x); 338890075Sobrien 338990075Sobrien case AND: 339090075Sobrien op0 = and_reg_cond (XEXP (old, 0), x, 0); 339190075Sobrien op1 = and_reg_cond (XEXP (old, 1), x, 0); 339290075Sobrien if (op0 != NULL || op1 != NULL) 339390075Sobrien { 339490075Sobrien if (op0 == const1_rtx) 339590075Sobrien return op1 ? op1 : gen_rtx_AND (0, XEXP (old, 1), x); 339690075Sobrien if (op1 == const1_rtx) 339790075Sobrien return op0 ? op0 : gen_rtx_AND (0, XEXP (old, 0), x); 339890075Sobrien if (op0 == const0_rtx || op1 == const0_rtx) 339990075Sobrien return const0_rtx; 340090075Sobrien if (op0 == NULL) 340190075Sobrien op0 = gen_rtx_AND (0, XEXP (old, 0), x); 340290075Sobrien else if (rtx_equal_p (x, op0)) 340390075Sobrien /* (x & A) & x ~ (x & A). */ 340490075Sobrien return old; 340590075Sobrien if (op1 == NULL) 340690075Sobrien op1 = gen_rtx_AND (0, XEXP (old, 1), x); 340790075Sobrien else if (rtx_equal_p (x, op1)) 340890075Sobrien /* (A & x) & x ~ (A & x). */ 340990075Sobrien return old; 341090075Sobrien return gen_rtx_AND (0, op0, op1); 341190075Sobrien } 341290075Sobrien if (! add) 341390075Sobrien return NULL; 341490075Sobrien return gen_rtx_AND (0, old, x); 341590075Sobrien 341690075Sobrien case NOT: 341790075Sobrien op0 = ior_reg_cond (XEXP (old, 0), not_reg_cond (x), 0); 341890075Sobrien if (op0 != NULL) 341990075Sobrien return not_reg_cond (op0); 342090075Sobrien if (! add) 342190075Sobrien return NULL; 342290075Sobrien return gen_rtx_AND (0, old, x); 342390075Sobrien 342490075Sobrien default: 3425169689Skan gcc_unreachable (); 342690075Sobrien } 342790075Sobrien} 342890075Sobrien 342990075Sobrien/* Given a condition X, remove references to reg REGNO and return the 343090075Sobrien new condition. The removal will be done so that all conditions 343190075Sobrien involving REGNO are considered to evaluate to false. This function 343290075Sobrien is used when the value of REGNO changes. */ 343390075Sobrien 343490075Sobrienstatic rtx 3435132718Skanelim_reg_cond (rtx x, unsigned int regno) 343690075Sobrien{ 343790075Sobrien rtx op0, op1; 343890075Sobrien 3439169689Skan if (COMPARISON_P (x)) 344090075Sobrien { 344190075Sobrien if (REGNO (XEXP (x, 0)) == regno) 344290075Sobrien return const0_rtx; 344390075Sobrien return x; 344490075Sobrien } 344590075Sobrien 344690075Sobrien switch (GET_CODE (x)) 344790075Sobrien { 344890075Sobrien case AND: 344990075Sobrien op0 = elim_reg_cond (XEXP (x, 0), regno); 345090075Sobrien op1 = elim_reg_cond (XEXP (x, 1), regno); 345190075Sobrien if (op0 == const0_rtx || op1 == const0_rtx) 345290075Sobrien return const0_rtx; 345390075Sobrien if (op0 == const1_rtx) 345490075Sobrien return op1; 345590075Sobrien if (op1 == const1_rtx) 345690075Sobrien return op0; 345790075Sobrien if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1)) 345890075Sobrien return x; 345990075Sobrien return gen_rtx_AND (0, op0, op1); 346090075Sobrien 346190075Sobrien case IOR: 346290075Sobrien op0 = elim_reg_cond (XEXP (x, 0), regno); 346390075Sobrien op1 = elim_reg_cond (XEXP (x, 1), regno); 346490075Sobrien if (op0 == const1_rtx || op1 == const1_rtx) 346590075Sobrien return const1_rtx; 346690075Sobrien if (op0 == const0_rtx) 346790075Sobrien return op1; 346890075Sobrien if (op1 == const0_rtx) 346990075Sobrien return op0; 347090075Sobrien if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1)) 347190075Sobrien return x; 347290075Sobrien return gen_rtx_IOR (0, op0, op1); 347390075Sobrien 347490075Sobrien case NOT: 347590075Sobrien op0 = elim_reg_cond (XEXP (x, 0), regno); 347690075Sobrien if (op0 == const0_rtx) 347790075Sobrien return const1_rtx; 347890075Sobrien if (op0 == const1_rtx) 347990075Sobrien return const0_rtx; 348090075Sobrien if (op0 != XEXP (x, 0)) 348190075Sobrien return not_reg_cond (op0); 348290075Sobrien return x; 348390075Sobrien 348490075Sobrien default: 3485169689Skan gcc_unreachable (); 348690075Sobrien } 348790075Sobrien} 348890075Sobrien#endif /* HAVE_conditional_execution */ 348990075Sobrien 349018334Speter#ifdef AUTO_INC_DEC 349118334Speter 349290075Sobrien/* Try to substitute the auto-inc expression INC as the address inside 349390075Sobrien MEM which occurs in INSN. Currently, the address of MEM is an expression 349490075Sobrien involving INCR_REG, and INCR is the next use of INCR_REG; it is an insn 349590075Sobrien that has a single set whose source is a PLUS of INCR_REG and something 349690075Sobrien else. */ 349790075Sobrien 349890075Sobrienstatic void 3499132718Skanattempt_auto_inc (struct propagate_block_info *pbi, rtx inc, rtx insn, 3500132718Skan rtx mem, rtx incr, rtx incr_reg) 350190075Sobrien{ 350290075Sobrien int regno = REGNO (incr_reg); 350390075Sobrien rtx set = single_set (incr); 350490075Sobrien rtx q = SET_DEST (set); 350590075Sobrien rtx y = SET_SRC (set); 350690075Sobrien int opnum = XEXP (y, 0) == incr_reg ? 0 : 1; 3507169689Skan int changed; 350890075Sobrien 350990075Sobrien /* Make sure this reg appears only once in this insn. */ 351090075Sobrien if (count_occurrences (PATTERN (insn), incr_reg, 1) != 1) 351190075Sobrien return; 351290075Sobrien 351390075Sobrien if (dead_or_set_p (incr, incr_reg) 351490075Sobrien /* Mustn't autoinc an eliminable register. */ 351590075Sobrien && (regno >= FIRST_PSEUDO_REGISTER 351690075Sobrien || ! TEST_HARD_REG_BIT (elim_reg_set, regno))) 351790075Sobrien { 351890075Sobrien /* This is the simple case. Try to make the auto-inc. If 351990075Sobrien we can't, we are done. Otherwise, we will do any 352090075Sobrien needed updates below. */ 352190075Sobrien if (! validate_change (insn, &XEXP (mem, 0), inc, 0)) 352290075Sobrien return; 352390075Sobrien } 3524169689Skan else if (REG_P (q) 352590075Sobrien /* PREV_INSN used here to check the semi-open interval 352690075Sobrien [insn,incr). */ 352790075Sobrien && ! reg_used_between_p (q, PREV_INSN (insn), incr) 352890075Sobrien /* We must also check for sets of q as q may be 352990075Sobrien a call clobbered hard register and there may 353090075Sobrien be a call between PREV_INSN (insn) and incr. */ 353190075Sobrien && ! reg_set_between_p (q, PREV_INSN (insn), incr)) 353290075Sobrien { 353390075Sobrien /* We have *p followed sometime later by q = p+size. 353490075Sobrien Both p and q must be live afterward, 353590075Sobrien and q is not used between INSN and its assignment. 353690075Sobrien Change it to q = p, ...*q..., q = q+size. 353790075Sobrien Then fall into the usual case. */ 353890075Sobrien rtx insns, temp; 353990075Sobrien 354090075Sobrien start_sequence (); 354190075Sobrien emit_move_insn (q, incr_reg); 354290075Sobrien insns = get_insns (); 354390075Sobrien end_sequence (); 354490075Sobrien 354590075Sobrien /* If we can't make the auto-inc, or can't make the 354690075Sobrien replacement into Y, exit. There's no point in making 354790075Sobrien the change below if we can't do the auto-inc and doing 354890075Sobrien so is not correct in the pre-inc case. */ 354990075Sobrien 355090075Sobrien XEXP (inc, 0) = q; 355190075Sobrien validate_change (insn, &XEXP (mem, 0), inc, 1); 355290075Sobrien validate_change (incr, &XEXP (y, opnum), q, 1); 355390075Sobrien if (! apply_change_group ()) 355490075Sobrien return; 355590075Sobrien 355690075Sobrien /* We now know we'll be doing this change, so emit the 355790075Sobrien new insn(s) and do the updates. */ 3558117395Skan emit_insn_before (insns, insn); 355990075Sobrien 3560132718Skan if (BB_HEAD (pbi->bb) == insn) 3561132718Skan BB_HEAD (pbi->bb) = insns; 356290075Sobrien 356390075Sobrien /* INCR will become a NOTE and INSN won't contain a 356490075Sobrien use of INCR_REG. If a use of INCR_REG was just placed in 356590075Sobrien the insn before INSN, make that the next use. 356690075Sobrien Otherwise, invalidate it. */ 3567169689Skan if (NONJUMP_INSN_P (PREV_INSN (insn)) 356890075Sobrien && GET_CODE (PATTERN (PREV_INSN (insn))) == SET 356990075Sobrien && SET_SRC (PATTERN (PREV_INSN (insn))) == incr_reg) 357090075Sobrien pbi->reg_next_use[regno] = PREV_INSN (insn); 357190075Sobrien else 357290075Sobrien pbi->reg_next_use[regno] = 0; 357390075Sobrien 357490075Sobrien incr_reg = q; 357590075Sobrien regno = REGNO (q); 357690075Sobrien 3577169689Skan if ((pbi->flags & PROP_REG_INFO) 3578169689Skan && !REGNO_REG_SET_P (pbi->reg_live, regno)) 3579169689Skan reg_deaths[regno] = pbi->insn_num; 3580169689Skan 358190075Sobrien /* REGNO is now used in INCR which is below INSN, but 358290075Sobrien it previously wasn't live here. If we don't mark 358390075Sobrien it as live, we'll put a REG_DEAD note for it 358490075Sobrien on this insn, which is incorrect. */ 358590075Sobrien SET_REGNO_REG_SET (pbi->reg_live, regno); 358690075Sobrien 358790075Sobrien /* If there are any calls between INSN and INCR, show 358890075Sobrien that REGNO now crosses them. */ 358990075Sobrien for (temp = insn; temp != incr; temp = NEXT_INSN (temp)) 3590169689Skan if (CALL_P (temp)) 3591161651Skan { 3592161651Skan REG_N_CALLS_CROSSED (regno)++; 3593161651Skan if (can_throw_internal (temp)) 3594161651Skan REG_N_THROWING_CALLS_CROSSED (regno)++; 3595161651Skan } 359690075Sobrien 359790075Sobrien /* Invalidate alias info for Q since we just changed its value. */ 359890075Sobrien clear_reg_alias_info (q); 359990075Sobrien } 360090075Sobrien else 360190075Sobrien return; 360290075Sobrien 360390075Sobrien /* If we haven't returned, it means we were able to make the 360490075Sobrien auto-inc, so update the status. First, record that this insn 360590075Sobrien has an implicit side effect. */ 360690075Sobrien 360790075Sobrien REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, incr_reg, REG_NOTES (insn)); 360890075Sobrien 360990075Sobrien /* Modify the old increment-insn to simply copy 361090075Sobrien the already-incremented value of our register. */ 3611169689Skan changed = validate_change (incr, &SET_SRC (set), incr_reg, 0); 3612169689Skan gcc_assert (changed); 361390075Sobrien 361490075Sobrien /* If that makes it a no-op (copying the register into itself) delete 361590075Sobrien it so it won't appear to be a "use" and a "set" of this 361690075Sobrien register. */ 361790075Sobrien if (REGNO (SET_DEST (set)) == REGNO (incr_reg)) 361890075Sobrien { 361990075Sobrien /* If the original source was dead, it's dead now. */ 362090075Sobrien rtx note; 362190075Sobrien 362290075Sobrien while ((note = find_reg_note (incr, REG_DEAD, NULL_RTX)) != NULL_RTX) 362390075Sobrien { 362490075Sobrien remove_note (incr, note); 362590075Sobrien if (XEXP (note, 0) != incr_reg) 3626169689Skan { 3627169689Skan unsigned int regno = REGNO (XEXP (note, 0)); 3628169689Skan 3629169689Skan if ((pbi->flags & PROP_REG_INFO) 3630169689Skan && REGNO_REG_SET_P (pbi->reg_live, regno)) 3631169689Skan { 3632169689Skan REG_LIVE_LENGTH (regno) += pbi->insn_num - reg_deaths[regno]; 3633169689Skan reg_deaths[regno] = 0; 3634169689Skan } 3635169689Skan CLEAR_REGNO_REG_SET (pbi->reg_live, REGNO (XEXP (note, 0))); 3636169689Skan } 363790075Sobrien } 363890075Sobrien 3639169689Skan SET_INSN_DELETED (incr); 364090075Sobrien } 364190075Sobrien 364290075Sobrien if (regno >= FIRST_PSEUDO_REGISTER) 364390075Sobrien { 364490075Sobrien /* Count an extra reference to the reg. When a reg is 364590075Sobrien incremented, spilling it is worse, so we want to make 364690075Sobrien that less likely. */ 364790075Sobrien REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb); 364890075Sobrien 364990075Sobrien /* Count the increment as a setting of the register, 365090075Sobrien even though it isn't a SET in rtl. */ 365190075Sobrien REG_N_SETS (regno)++; 365290075Sobrien } 365390075Sobrien} 365490075Sobrien 365518334Speter/* X is a MEM found in INSN. See if we can convert it into an auto-increment 365618334Speter reference. */ 365718334Speter 365818334Speterstatic void 3659132718Skanfind_auto_inc (struct propagate_block_info *pbi, rtx x, rtx insn) 366018334Speter{ 366118334Speter rtx addr = XEXP (x, 0); 366218334Speter HOST_WIDE_INT offset = 0; 366390075Sobrien rtx set, y, incr, inc_val; 366490075Sobrien int regno; 366590075Sobrien int size = GET_MODE_SIZE (GET_MODE (x)); 366618334Speter 3667169689Skan if (JUMP_P (insn)) 366890075Sobrien return; 366990075Sobrien 367018334Speter /* Here we detect use of an index register which might be good for 367118334Speter postincrement, postdecrement, preincrement, or predecrement. */ 367218334Speter 367318334Speter if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT) 367418334Speter offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0); 367518334Speter 3676169689Skan if (!REG_P (addr)) 367790075Sobrien return; 367890075Sobrien 367990075Sobrien regno = REGNO (addr); 368090075Sobrien 368190075Sobrien /* Is the next use an increment that might make auto-increment? */ 368290075Sobrien incr = pbi->reg_next_use[regno]; 368390075Sobrien if (incr == 0 || BLOCK_NUM (incr) != BLOCK_NUM (insn)) 368490075Sobrien return; 368590075Sobrien set = single_set (incr); 368690075Sobrien if (set == 0 || GET_CODE (set) != SET) 368790075Sobrien return; 368890075Sobrien y = SET_SRC (set); 368990075Sobrien 369090075Sobrien if (GET_CODE (y) != PLUS) 369190075Sobrien return; 369290075Sobrien 369390075Sobrien if (REG_P (XEXP (y, 0)) && REGNO (XEXP (y, 0)) == REGNO (addr)) 369490075Sobrien inc_val = XEXP (y, 1); 369590075Sobrien else if (REG_P (XEXP (y, 1)) && REGNO (XEXP (y, 1)) == REGNO (addr)) 369690075Sobrien inc_val = XEXP (y, 0); 369790075Sobrien else 369890075Sobrien return; 369990075Sobrien 370090075Sobrien if (GET_CODE (inc_val) == CONST_INT) 370118334Speter { 370290075Sobrien if (HAVE_POST_INCREMENT 370390075Sobrien && (INTVAL (inc_val) == size && offset == 0)) 370490075Sobrien attempt_auto_inc (pbi, gen_rtx_POST_INC (Pmode, addr), insn, x, 370590075Sobrien incr, addr); 370690075Sobrien else if (HAVE_POST_DECREMENT 370790075Sobrien && (INTVAL (inc_val) == -size && offset == 0)) 370890075Sobrien attempt_auto_inc (pbi, gen_rtx_POST_DEC (Pmode, addr), insn, x, 370990075Sobrien incr, addr); 371090075Sobrien else if (HAVE_PRE_INCREMENT 371190075Sobrien && (INTVAL (inc_val) == size && offset == size)) 371290075Sobrien attempt_auto_inc (pbi, gen_rtx_PRE_INC (Pmode, addr), insn, x, 371390075Sobrien incr, addr); 371490075Sobrien else if (HAVE_PRE_DECREMENT 371590075Sobrien && (INTVAL (inc_val) == -size && offset == -size)) 371690075Sobrien attempt_auto_inc (pbi, gen_rtx_PRE_DEC (Pmode, addr), insn, x, 371790075Sobrien incr, addr); 371890075Sobrien else if (HAVE_POST_MODIFY_DISP && offset == 0) 371990075Sobrien attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr, 372090075Sobrien gen_rtx_PLUS (Pmode, 372190075Sobrien addr, 372290075Sobrien inc_val)), 372390075Sobrien insn, x, incr, addr); 3724132718Skan else if (HAVE_PRE_MODIFY_DISP && offset == INTVAL (inc_val)) 3725132718Skan attempt_auto_inc (pbi, gen_rtx_PRE_MODIFY (Pmode, addr, 3726132718Skan gen_rtx_PLUS (Pmode, 3727132718Skan addr, 3728132718Skan inc_val)), 3729132718Skan insn, x, incr, addr); 373090075Sobrien } 3731169689Skan else if (REG_P (inc_val) 373290075Sobrien && ! reg_set_between_p (inc_val, PREV_INSN (insn), 373390075Sobrien NEXT_INSN (incr))) 373418334Speter 373590075Sobrien { 373690075Sobrien if (HAVE_POST_MODIFY_REG && offset == 0) 373790075Sobrien attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr, 373890075Sobrien gen_rtx_PLUS (Pmode, 373990075Sobrien addr, 374090075Sobrien inc_val)), 374190075Sobrien insn, x, incr, addr); 374290075Sobrien } 374390075Sobrien} 374418334Speter 374590075Sobrien#endif /* AUTO_INC_DEC */ 374690075Sobrien 374790075Sobrienstatic void 3748132718Skanmark_used_reg (struct propagate_block_info *pbi, rtx reg, 3749132718Skan rtx cond ATTRIBUTE_UNUSED, rtx insn) 375090075Sobrien{ 375190075Sobrien unsigned int regno_first, regno_last, i; 375290075Sobrien int some_was_live, some_was_dead, some_not_set; 375318334Speter 375490075Sobrien regno_last = regno_first = REGNO (reg); 375590075Sobrien if (regno_first < FIRST_PSEUDO_REGISTER) 3756169689Skan regno_last += hard_regno_nregs[regno_first][GET_MODE (reg)] - 1; 375718334Speter 375890075Sobrien /* Find out if any of this register is live after this instruction. */ 375990075Sobrien some_was_live = some_was_dead = 0; 376090075Sobrien for (i = regno_first; i <= regno_last; ++i) 376190075Sobrien { 376290075Sobrien int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i); 376390075Sobrien some_was_live |= needed_regno; 376490075Sobrien some_was_dead |= ! needed_regno; 376590075Sobrien } 376618334Speter 376790075Sobrien /* Find out if any of the register was set this insn. */ 376890075Sobrien some_not_set = 0; 376990075Sobrien for (i = regno_first; i <= regno_last; ++i) 377090075Sobrien some_not_set |= ! REGNO_REG_SET_P (pbi->new_set, i); 377118334Speter 377290075Sobrien if (pbi->flags & (PROP_LOG_LINKS | PROP_AUTOINC)) 377390075Sobrien { 377490075Sobrien /* Record where each reg is used, so when the reg is set we know 377590075Sobrien the next insn that uses it. */ 377690075Sobrien pbi->reg_next_use[regno_first] = insn; 377790075Sobrien } 377818334Speter 377990075Sobrien if (pbi->flags & PROP_REG_INFO) 378090075Sobrien { 378190075Sobrien if (regno_first < FIRST_PSEUDO_REGISTER) 378290075Sobrien { 378390075Sobrien /* If this is a register we are going to try to eliminate, 378490075Sobrien don't mark it live here. If we are successful in 378590075Sobrien eliminating it, it need not be live unless it is used for 378690075Sobrien pseudos, in which case it will have been set live when it 378790075Sobrien was allocated to the pseudos. If the register will not 378890075Sobrien be eliminated, reload will set it live at that point. 378918334Speter 379090075Sobrien Otherwise, record that this function uses this register. */ 379190075Sobrien /* ??? The PPC backend tries to "eliminate" on the pic 379290075Sobrien register to itself. This should be fixed. In the mean 379390075Sobrien time, hack around it. */ 379418334Speter 379590075Sobrien if (! (TEST_HARD_REG_BIT (elim_reg_set, regno_first) 379690075Sobrien && (regno_first == FRAME_POINTER_REGNUM 379790075Sobrien || regno_first == ARG_POINTER_REGNUM))) 379890075Sobrien for (i = regno_first; i <= regno_last; ++i) 379990075Sobrien regs_ever_live[i] = 1; 380090075Sobrien } 380190075Sobrien else 380290075Sobrien { 380390075Sobrien /* Keep track of which basic block each reg appears in. */ 380418334Speter 380590075Sobrien int blocknum = pbi->bb->index; 380690075Sobrien if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN) 380790075Sobrien REG_BASIC_BLOCK (regno_first) = blocknum; 380890075Sobrien else if (REG_BASIC_BLOCK (regno_first) != blocknum) 380990075Sobrien REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL; 381018334Speter 381190075Sobrien /* Count (weighted) number of uses of each reg. */ 381290075Sobrien REG_FREQ (regno_first) += REG_FREQ_FROM_BB (pbi->bb); 381390075Sobrien REG_N_REFS (regno_first)++; 381490075Sobrien } 3815169689Skan for (i = regno_first; i <= regno_last; ++i) 3816169689Skan if (! REGNO_REG_SET_P (pbi->reg_live, i)) 3817169689Skan { 3818169689Skan gcc_assert (!reg_deaths[i]); 3819169689Skan reg_deaths[i] = pbi->insn_num; 3820169689Skan } 382190075Sobrien } 382218334Speter 382390075Sobrien /* Record and count the insns in which a reg dies. If it is used in 382490075Sobrien this insn and was dead below the insn then it dies in this insn. 382590075Sobrien If it was set in this insn, we do not make a REG_DEAD note; 382690075Sobrien likewise if we already made such a note. */ 382790075Sobrien if ((pbi->flags & (PROP_DEATH_NOTES | PROP_REG_INFO)) 382890075Sobrien && some_was_dead 382990075Sobrien && some_not_set) 383090075Sobrien { 383190075Sobrien /* Check for the case where the register dying partially 383290075Sobrien overlaps the register set by this insn. */ 383390075Sobrien if (regno_first != regno_last) 383490075Sobrien for (i = regno_first; i <= regno_last; ++i) 383590075Sobrien some_was_live |= REGNO_REG_SET_P (pbi->new_set, i); 383618334Speter 383790075Sobrien /* If none of the words in X is needed, make a REG_DEAD note. 383890075Sobrien Otherwise, we must make partial REG_DEAD notes. */ 383990075Sobrien if (! some_was_live) 384090075Sobrien { 384190075Sobrien if ((pbi->flags & PROP_DEATH_NOTES) 3842169689Skan#ifdef STACK_REGS 3843169689Skan && (!(pbi->flags & PROP_POST_REGSTACK) 3844169689Skan || !IN_RANGE (REGNO (reg), FIRST_STACK_REG, LAST_STACK_REG)) 3845169689Skan#endif 384690075Sobrien && ! find_regno_note (insn, REG_DEAD, regno_first)) 384790075Sobrien REG_NOTES (insn) 384890075Sobrien = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn)); 384918334Speter 385090075Sobrien if (pbi->flags & PROP_REG_INFO) 385190075Sobrien REG_N_DEATHS (regno_first)++; 385290075Sobrien } 385390075Sobrien else 385490075Sobrien { 385590075Sobrien /* Don't make a REG_DEAD note for a part of a register 385690075Sobrien that is set in the insn. */ 385790075Sobrien for (i = regno_first; i <= regno_last; ++i) 385890075Sobrien if (! REGNO_REG_SET_P (pbi->reg_live, i) 385990075Sobrien && ! dead_or_set_regno_p (insn, i)) 386090075Sobrien REG_NOTES (insn) 386190075Sobrien = alloc_EXPR_LIST (REG_DEAD, 3862117395Skan regno_reg_rtx[i], 386390075Sobrien REG_NOTES (insn)); 386490075Sobrien } 386590075Sobrien } 386618334Speter 386790075Sobrien /* Mark the register as being live. */ 386890075Sobrien for (i = regno_first; i <= regno_last; ++i) 386990075Sobrien { 387096263Sobrien#ifdef HAVE_conditional_execution 387196263Sobrien int this_was_live = REGNO_REG_SET_P (pbi->reg_live, i); 387296263Sobrien#endif 387396263Sobrien 387490075Sobrien SET_REGNO_REG_SET (pbi->reg_live, i); 387518334Speter 387690075Sobrien#ifdef HAVE_conditional_execution 387790075Sobrien /* If this is a conditional use, record that fact. If it is later 387890075Sobrien conditionally set, we'll know to kill the register. */ 387990075Sobrien if (cond != NULL_RTX) 388090075Sobrien { 388190075Sobrien splay_tree_node node; 388290075Sobrien struct reg_cond_life_info *rcli; 388390075Sobrien rtx ncond; 388490075Sobrien 388596263Sobrien if (this_was_live) 388618334Speter { 388790075Sobrien node = splay_tree_lookup (pbi->reg_cond_dead, i); 388890075Sobrien if (node == NULL) 388990075Sobrien { 389090075Sobrien /* The register was unconditionally live previously. 389190075Sobrien No need to do anything. */ 389290075Sobrien } 389390075Sobrien else 389490075Sobrien { 389590075Sobrien /* The register was conditionally live previously. 389690075Sobrien Subtract the new life cond from the old death cond. */ 389790075Sobrien rcli = (struct reg_cond_life_info *) node->value; 389890075Sobrien ncond = rcli->condition; 389990075Sobrien ncond = and_reg_cond (ncond, not_reg_cond (cond), 1); 390090075Sobrien 390190075Sobrien /* If the register is now unconditionally live, 390290075Sobrien remove the entry in the splay_tree. */ 390390075Sobrien if (ncond == const0_rtx) 390490075Sobrien splay_tree_remove (pbi->reg_cond_dead, i); 390590075Sobrien else 390690075Sobrien { 390790075Sobrien rcli->condition = ncond; 390890075Sobrien SET_REGNO_REG_SET (pbi->reg_cond_reg, 390990075Sobrien REGNO (XEXP (cond, 0))); 391090075Sobrien } 391190075Sobrien } 391218334Speter } 391390075Sobrien else 391418334Speter { 391590075Sobrien /* The register was not previously live at all. Record 391690075Sobrien the condition under which it is still dead. */ 3917169689Skan rcli = XNEW (struct reg_cond_life_info); 391890075Sobrien rcli->condition = not_reg_cond (cond); 391990075Sobrien rcli->stores = const0_rtx; 392090075Sobrien rcli->orig_condition = const0_rtx; 392190075Sobrien splay_tree_insert (pbi->reg_cond_dead, i, 392290075Sobrien (splay_tree_value) rcli); 392318334Speter 392490075Sobrien SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0))); 392518334Speter } 392618334Speter } 392796263Sobrien else if (this_was_live) 392890075Sobrien { 392990075Sobrien /* The register may have been conditionally live previously, but 393090075Sobrien is now unconditionally live. Remove it from the conditionally 393190075Sobrien dead list, so that a conditional set won't cause us to think 393290075Sobrien it dead. */ 393390075Sobrien splay_tree_remove (pbi->reg_cond_dead, i); 393490075Sobrien } 393590075Sobrien#endif 393618334Speter } 393718334Speter} 393818334Speter 3939169689Skan/* Scan expression X for registers which have to be marked used in PBI. 3940169689Skan X is considered to be the SET_DEST rtx of SET. TRUE is returned if 3941169689Skan X could be handled by this function. */ 3942169689Skan 3943169689Skanstatic bool 3944169689Skanmark_used_dest_regs (struct propagate_block_info *pbi, rtx x, rtx cond, rtx insn) 3945169689Skan{ 3946169689Skan int regno; 3947169689Skan bool mark_dest = false; 3948169689Skan rtx dest = x; 3949169689Skan 3950169689Skan /* On some platforms calls return values spread over several 3951169689Skan locations. These locations are wrapped in a EXPR_LIST rtx 3952169689Skan together with a CONST_INT offset. */ 3953169689Skan if (GET_CODE (x) == EXPR_LIST 3954169689Skan && GET_CODE (XEXP (x, 1)) == CONST_INT) 3955169689Skan x = XEXP (x, 0); 3956169689Skan 3957169689Skan if (x == NULL_RTX) 3958169689Skan return false; 3959169689Skan 3960169689Skan /* If storing into MEM, don't show it as being used. But do 3961169689Skan show the address as being used. */ 3962169689Skan if (MEM_P (x)) 3963169689Skan { 3964169689Skan#ifdef AUTO_INC_DEC 3965169689Skan if (pbi->flags & PROP_AUTOINC) 3966169689Skan find_auto_inc (pbi, x, insn); 3967169689Skan#endif 3968169689Skan mark_used_regs (pbi, XEXP (x, 0), cond, insn); 3969169689Skan return true; 3970169689Skan } 3971169689Skan 3972169689Skan /* Storing in STRICT_LOW_PART is like storing in a reg 3973169689Skan in that this SET might be dead, so ignore it in TESTREG. 3974169689Skan but in some other ways it is like using the reg. 3975169689Skan 3976169689Skan Storing in a SUBREG or a bit field is like storing the entire 3977169689Skan register in that if the register's value is not used 3978169689Skan then this SET is not needed. */ 3979169689Skan while (GET_CODE (x) == STRICT_LOW_PART 3980169689Skan || GET_CODE (x) == ZERO_EXTRACT 3981169689Skan || GET_CODE (x) == SUBREG) 3982169689Skan { 3983169689Skan#ifdef CANNOT_CHANGE_MODE_CLASS 3984169689Skan if ((pbi->flags & PROP_REG_INFO) && GET_CODE (x) == SUBREG) 3985169689Skan record_subregs_of_mode (x); 3986169689Skan#endif 3987169689Skan 3988169689Skan /* Modifying a single register in an alternate mode 3989169689Skan does not use any of the old value. But these other 3990169689Skan ways of storing in a register do use the old value. */ 3991169689Skan if (GET_CODE (x) == SUBREG 3992169689Skan && !((REG_BYTES (SUBREG_REG (x)) 3993169689Skan + UNITS_PER_WORD - 1) / UNITS_PER_WORD 3994169689Skan > (REG_BYTES (x) 3995169689Skan + UNITS_PER_WORD - 1) / UNITS_PER_WORD)) 3996169689Skan ; 3997169689Skan else 3998169689Skan mark_dest = true; 3999169689Skan 4000169689Skan x = XEXP (x, 0); 4001169689Skan } 4002169689Skan 4003169689Skan /* If this is a store into a register or group of registers, 4004169689Skan recursively scan the value being stored. */ 4005169689Skan if (REG_P (x) 4006169689Skan && (regno = REGNO (x), 4007169689Skan !(regno == FRAME_POINTER_REGNUM 4008169689Skan && (!reload_completed || frame_pointer_needed))) 4009169689Skan#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 4010169689Skan && !(regno == HARD_FRAME_POINTER_REGNUM 4011169689Skan && (!reload_completed || frame_pointer_needed)) 4012169689Skan#endif 4013169689Skan#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 4014169689Skan && !(regno == ARG_POINTER_REGNUM && fixed_regs[regno]) 4015169689Skan#endif 4016169689Skan ) 4017169689Skan { 4018169689Skan if (mark_dest) 4019169689Skan mark_used_regs (pbi, dest, cond, insn); 4020169689Skan return true; 4021169689Skan } 4022169689Skan return false; 4023169689Skan} 4024169689Skan 402590075Sobrien/* Scan expression X and store a 1-bit in NEW_LIVE for each reg it uses. 402690075Sobrien This is done assuming the registers needed from X are those that 402790075Sobrien have 1-bits in PBI->REG_LIVE. 402818334Speter 402990075Sobrien INSN is the containing instruction. If INSN is dead, this function 403090075Sobrien is not called. */ 403118334Speter 403218334Speterstatic void 4033132718Skanmark_used_regs (struct propagate_block_info *pbi, rtx x, rtx cond, rtx insn) 403418334Speter{ 403590075Sobrien RTX_CODE code; 403690075Sobrien int flags = pbi->flags; 403718334Speter 403818334Speter retry: 403990075Sobrien if (!x) 404090075Sobrien return; 404118334Speter code = GET_CODE (x); 404218334Speter switch (code) 404318334Speter { 404418334Speter case LABEL_REF: 404518334Speter case SYMBOL_REF: 404618334Speter case CONST_INT: 404718334Speter case CONST: 404818334Speter case CONST_DOUBLE: 404996263Sobrien case CONST_VECTOR: 405018334Speter case PC: 405118334Speter case ADDR_VEC: 405218334Speter case ADDR_DIFF_VEC: 405318334Speter return; 405418334Speter 405518334Speter#ifdef HAVE_cc0 405618334Speter case CC0: 405790075Sobrien pbi->cc0_live = 1; 405818334Speter return; 405918334Speter#endif 406018334Speter 406118334Speter case CLOBBER: 406218334Speter /* If we are clobbering a MEM, mark any registers inside the address 406318334Speter as being used. */ 4064169689Skan if (MEM_P (XEXP (x, 0))) 406590075Sobrien mark_used_regs (pbi, XEXP (XEXP (x, 0), 0), cond, insn); 406618334Speter return; 406718334Speter 406818334Speter case MEM: 406990075Sobrien /* Don't bother watching stores to mems if this is not the 407090075Sobrien final pass. We'll not be deleting dead stores this round. */ 4071117395Skan if (optimize && (flags & PROP_SCAN_DEAD_STORES)) 407252284Sobrien { 407390075Sobrien /* Invalidate the data for the last MEM stored, but only if MEM is 407490075Sobrien something that can be stored into. */ 407590075Sobrien if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF 407690075Sobrien && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0))) 407790075Sobrien /* Needn't clear the memory set list. */ 407890075Sobrien ; 407990075Sobrien else 408090075Sobrien { 408190075Sobrien rtx temp = pbi->mem_set_list; 408290075Sobrien rtx prev = NULL_RTX; 408390075Sobrien rtx next; 408418334Speter 408590075Sobrien while (temp) 408652284Sobrien { 408790075Sobrien next = XEXP (temp, 1); 4088169689Skan if (anti_dependence (XEXP (temp, 0), x)) 408990075Sobrien { 409090075Sobrien /* Splice temp out of the list. */ 409190075Sobrien if (prev) 409290075Sobrien XEXP (prev, 1) = next; 409390075Sobrien else 409490075Sobrien pbi->mem_set_list = next; 409590075Sobrien free_EXPR_LIST_node (temp); 409690075Sobrien pbi->mem_set_list_len--; 409790075Sobrien } 409852284Sobrien else 409990075Sobrien prev = temp; 410090075Sobrien temp = next; 410152284Sobrien } 410252284Sobrien } 410390075Sobrien 410490075Sobrien /* If the memory reference had embedded side effects (autoincrement 410590075Sobrien address modes. Then we may need to kill some entries on the 410690075Sobrien memory set list. */ 410790075Sobrien if (insn) 4108117395Skan for_each_rtx (&PATTERN (insn), invalidate_mems_from_autoinc, pbi); 410952284Sobrien } 411052284Sobrien 411118334Speter#ifdef AUTO_INC_DEC 411290075Sobrien if (flags & PROP_AUTOINC) 4113117395Skan find_auto_inc (pbi, x, insn); 411418334Speter#endif 411518334Speter break; 411618334Speter 411718334Speter case SUBREG: 4118117395Skan#ifdef CANNOT_CHANGE_MODE_CLASS 4119146895Skan if (flags & PROP_REG_INFO) 4120146895Skan record_subregs_of_mode (x); 412190075Sobrien#endif 412218334Speter 412318334Speter /* While we're here, optimize this case. */ 412418334Speter x = SUBREG_REG (x); 4125169689Skan if (!REG_P (x)) 412690075Sobrien goto retry; 412790075Sobrien /* Fall through. */ 412818334Speter 412918334Speter case REG: 413090075Sobrien /* See a register other than being set => mark it as needed. */ 413190075Sobrien mark_used_reg (pbi, x, cond, insn); 413218334Speter return; 413318334Speter 413418334Speter case SET: 413518334Speter { 4136169689Skan rtx dest = SET_DEST (x); 4137169689Skan int i; 4138169689Skan bool ret = false; 413918334Speter 4140169689Skan if (GET_CODE (dest) == PARALLEL) 4141169689Skan for (i = 0; i < XVECLEN (dest, 0); i++) 4142169689Skan ret |= mark_used_dest_regs (pbi, XVECEXP (dest, 0, i), cond, insn); 4143169689Skan else 4144169689Skan ret = mark_used_dest_regs (pbi, dest, cond, insn); 4145169689Skan 4146169689Skan if (ret) 414718334Speter { 414890075Sobrien mark_used_regs (pbi, SET_SRC (x), cond, insn); 414918334Speter return; 415018334Speter } 415118334Speter } 415218334Speter break; 415318334Speter 415452284Sobrien case ASM_OPERANDS: 415552284Sobrien case UNSPEC_VOLATILE: 415652284Sobrien case TRAP_IF: 415752284Sobrien case ASM_INPUT: 415852284Sobrien { 415952284Sobrien /* Traditional and volatile asm instructions must be considered to use 416052284Sobrien and clobber all hard registers, all pseudo-registers and all of 416152284Sobrien memory. So must TRAP_IF and UNSPEC_VOLATILE operations. 416252284Sobrien 416352284Sobrien Consider for instance a volatile asm that changes the fpu rounding 416452284Sobrien mode. An insn should not be moved across this even if it only uses 416590075Sobrien pseudo-regs because it might give an incorrectly rounded result. 416652284Sobrien 416752284Sobrien ?!? Unfortunately, marking all hard registers as live causes massive 416852284Sobrien problems for the register allocator and marking all pseudos as live 416952284Sobrien creates mountains of uninitialized variable warnings. 417052284Sobrien 417152284Sobrien So for now, just clear the memory set list and mark any regs 417252284Sobrien we can find in ASM_OPERANDS as used. */ 417352284Sobrien if (code != ASM_OPERANDS || MEM_VOLATILE_P (x)) 417490075Sobrien { 417590075Sobrien free_EXPR_LIST_list (&pbi->mem_set_list); 417690075Sobrien pbi->mem_set_list_len = 0; 417790075Sobrien } 417852284Sobrien 417990075Sobrien /* For all ASM_OPERANDS, we must traverse the vector of input operands. 418052284Sobrien We can not just fall through here since then we would be confused 418152284Sobrien by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate 418252284Sobrien traditional asms unlike their normal usage. */ 418352284Sobrien if (code == ASM_OPERANDS) 418452284Sobrien { 418552284Sobrien int j; 418652284Sobrien 418752284Sobrien for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++) 418890075Sobrien mark_used_regs (pbi, ASM_OPERANDS_INPUT (x, j), cond, insn); 418952284Sobrien } 419052284Sobrien break; 419152284Sobrien } 419252284Sobrien 419390075Sobrien case COND_EXEC: 4194169689Skan gcc_assert (!cond); 419552284Sobrien 419690075Sobrien mark_used_regs (pbi, COND_EXEC_TEST (x), NULL_RTX, insn); 419790075Sobrien 419890075Sobrien cond = COND_EXEC_TEST (x); 419990075Sobrien x = COND_EXEC_CODE (x); 420090075Sobrien goto retry; 420190075Sobrien 420250397Sobrien default: 420350397Sobrien break; 420418334Speter } 420518334Speter 420618334Speter /* Recursively scan the operands of this expression. */ 420718334Speter 420818334Speter { 420990075Sobrien const char * const fmt = GET_RTX_FORMAT (code); 421090075Sobrien int i; 421190075Sobrien 421218334Speter for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 421318334Speter { 421418334Speter if (fmt[i] == 'e') 421518334Speter { 421618334Speter /* Tail recursive case: save a function call level. */ 421718334Speter if (i == 0) 421818334Speter { 421918334Speter x = XEXP (x, 0); 422018334Speter goto retry; 422118334Speter } 422290075Sobrien mark_used_regs (pbi, XEXP (x, i), cond, insn); 422318334Speter } 422418334Speter else if (fmt[i] == 'E') 422518334Speter { 422690075Sobrien int j; 422718334Speter for (j = 0; j < XVECLEN (x, i); j++) 422890075Sobrien mark_used_regs (pbi, XVECEXP (x, i, j), cond, insn); 422918334Speter } 423018334Speter } 423118334Speter } 423218334Speter} 423318334Speter 423418334Speter#ifdef AUTO_INC_DEC 423518334Speter 423618334Speterstatic int 4237132718Skantry_pre_increment_1 (struct propagate_block_info *pbi, rtx insn) 423818334Speter{ 423918334Speter /* Find the next use of this reg. If in same basic block, 424018334Speter make it do pre-increment or pre-decrement if appropriate. */ 424150397Sobrien rtx x = single_set (insn); 424218334Speter HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1) 424390075Sobrien * INTVAL (XEXP (SET_SRC (x), 1))); 424418334Speter int regno = REGNO (SET_DEST (x)); 424590075Sobrien rtx y = pbi->reg_next_use[regno]; 424618334Speter if (y != 0 424790075Sobrien && SET_DEST (x) != stack_pointer_rtx 424818334Speter && BLOCK_NUM (y) == BLOCK_NUM (insn) 424918334Speter /* Don't do this if the reg dies, or gets set in y; a standard addressing 425050397Sobrien mode would be better. */ 425118334Speter && ! dead_or_set_p (y, SET_DEST (x)) 425250397Sobrien && try_pre_increment (y, SET_DEST (x), amount)) 425318334Speter { 425490075Sobrien /* We have found a suitable auto-increment and already changed 425590075Sobrien insn Y to do it. So flush this increment instruction. */ 4256117395Skan propagate_block_delete_insn (insn); 425790075Sobrien 425890075Sobrien /* Count a reference to this reg for the increment insn we are 425990075Sobrien deleting. When a reg is incremented, spilling it is worse, 426090075Sobrien so we want to make that less likely. */ 426118334Speter if (regno >= FIRST_PSEUDO_REGISTER) 426218334Speter { 426390075Sobrien REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb); 426450397Sobrien REG_N_SETS (regno)++; 426518334Speter } 426690075Sobrien 426790075Sobrien /* Flush any remembered memories depending on the value of 426890075Sobrien the incremented register. */ 426990075Sobrien invalidate_mems_from_set (pbi, SET_DEST (x)); 427090075Sobrien 427118334Speter return 1; 427218334Speter } 427318334Speter return 0; 427418334Speter} 427518334Speter 427618334Speter/* Try to change INSN so that it does pre-increment or pre-decrement 427718334Speter addressing on register REG in order to add AMOUNT to REG. 427818334Speter AMOUNT is negative for pre-decrement. 427918334Speter Returns 1 if the change could be made. 428018334Speter This checks all about the validity of the result of modifying INSN. */ 428118334Speter 428218334Speterstatic int 4283132718Skantry_pre_increment (rtx insn, rtx reg, HOST_WIDE_INT amount) 428418334Speter{ 428590075Sobrien rtx use; 428618334Speter 428718334Speter /* Nonzero if we can try to make a pre-increment or pre-decrement. 428818334Speter For example, addl $4,r1; movl (r1),... can become movl +(r1),... */ 428918334Speter int pre_ok = 0; 429018334Speter /* Nonzero if we can try to make a post-increment or post-decrement. 429118334Speter For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,... 429218334Speter It is possible for both PRE_OK and POST_OK to be nonzero if the machine 429318334Speter supports both pre-inc and post-inc, or both pre-dec and post-dec. */ 429418334Speter int post_ok = 0; 429518334Speter 429618334Speter /* Nonzero if the opportunity actually requires post-inc or post-dec. */ 429718334Speter int do_post = 0; 429818334Speter 429918334Speter /* From the sign of increment, see which possibilities are conceivable 430018334Speter on this target machine. */ 430152284Sobrien if (HAVE_PRE_INCREMENT && amount > 0) 430218334Speter pre_ok = 1; 430352284Sobrien if (HAVE_POST_INCREMENT && amount > 0) 430418334Speter post_ok = 1; 430518334Speter 430652284Sobrien if (HAVE_PRE_DECREMENT && amount < 0) 430718334Speter pre_ok = 1; 430852284Sobrien if (HAVE_POST_DECREMENT && amount < 0) 430918334Speter post_ok = 1; 431018334Speter 431118334Speter if (! (pre_ok || post_ok)) 431218334Speter return 0; 431318334Speter 431418334Speter /* It is not safe to add a side effect to a jump insn 431518334Speter because if the incremented register is spilled and must be reloaded 431618334Speter there would be no way to store the incremented value back in memory. */ 431718334Speter 4318169689Skan if (JUMP_P (insn)) 431918334Speter return 0; 432018334Speter 432118334Speter use = 0; 432218334Speter if (pre_ok) 432318334Speter use = find_use_as_address (PATTERN (insn), reg, 0); 432490075Sobrien if (post_ok && (use == 0 || use == (rtx) (size_t) 1)) 432518334Speter { 432618334Speter use = find_use_as_address (PATTERN (insn), reg, -amount); 432718334Speter do_post = 1; 432818334Speter } 432918334Speter 433090075Sobrien if (use == 0 || use == (rtx) (size_t) 1) 433118334Speter return 0; 433218334Speter 433318334Speter if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount)) 433418334Speter return 0; 433518334Speter 433618334Speter /* See if this combination of instruction and addressing mode exists. */ 433718334Speter if (! validate_change (insn, &XEXP (use, 0), 433850397Sobrien gen_rtx_fmt_e (amount > 0 433950397Sobrien ? (do_post ? POST_INC : PRE_INC) 434050397Sobrien : (do_post ? POST_DEC : PRE_DEC), 434150397Sobrien Pmode, reg), 0)) 434218334Speter return 0; 434318334Speter 434418334Speter /* Record that this insn now has an implicit side effect on X. */ 434590075Sobrien REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, reg, REG_NOTES (insn)); 434618334Speter return 1; 434718334Speter} 434818334Speter 434918334Speter#endif /* AUTO_INC_DEC */ 435018334Speter 435118334Speter/* Find the place in the rtx X where REG is used as a memory address. 435218334Speter Return the MEM rtx that so uses it. 435318334Speter If PLUSCONST is nonzero, search instead for a memory address equivalent to 435418334Speter (plus REG (const_int PLUSCONST)). 435518334Speter 435618334Speter If such an address does not appear, return 0. 435718334Speter If REG appears more than once, or is used other than in such an address, 435890075Sobrien return (rtx) 1. */ 435918334Speter 436050397Sobrienrtx 4361132718Skanfind_use_as_address (rtx x, rtx reg, HOST_WIDE_INT plusconst) 436218334Speter{ 436318334Speter enum rtx_code code = GET_CODE (x); 436490075Sobrien const char * const fmt = GET_RTX_FORMAT (code); 436590075Sobrien int i; 436690075Sobrien rtx value = 0; 436790075Sobrien rtx tem; 436818334Speter 436918334Speter if (code == MEM && XEXP (x, 0) == reg && plusconst == 0) 437018334Speter return x; 437118334Speter 437218334Speter if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS 437318334Speter && XEXP (XEXP (x, 0), 0) == reg 437418334Speter && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT 437518334Speter && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst) 437618334Speter return x; 437718334Speter 437818334Speter if (code == SIGN_EXTRACT || code == ZERO_EXTRACT) 437918334Speter { 438018334Speter /* If REG occurs inside a MEM used in a bit-field reference, 438118334Speter that is unacceptable. */ 438218334Speter if (find_use_as_address (XEXP (x, 0), reg, 0) != 0) 438390075Sobrien return (rtx) (size_t) 1; 438418334Speter } 438518334Speter 438618334Speter if (x == reg) 438790075Sobrien return (rtx) (size_t) 1; 438818334Speter 438918334Speter for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 439018334Speter { 439118334Speter if (fmt[i] == 'e') 439218334Speter { 439318334Speter tem = find_use_as_address (XEXP (x, i), reg, plusconst); 439418334Speter if (value == 0) 439518334Speter value = tem; 439618334Speter else if (tem != 0) 439790075Sobrien return (rtx) (size_t) 1; 439818334Speter } 439990075Sobrien else if (fmt[i] == 'E') 440018334Speter { 440190075Sobrien int j; 440218334Speter for (j = XVECLEN (x, i) - 1; j >= 0; j--) 440318334Speter { 440418334Speter tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst); 440518334Speter if (value == 0) 440618334Speter value = tem; 440718334Speter else if (tem != 0) 440890075Sobrien return (rtx) (size_t) 1; 440918334Speter } 441018334Speter } 441118334Speter } 441218334Speter 441318334Speter return value; 441418334Speter} 441518334Speter 441618334Speter/* Write information about registers and basic blocks into FILE. 441718334Speter This is part of making a debugging dump. */ 441818334Speter 441918334Spetervoid 4420132718Skandump_regset (regset r, FILE *outf) 442150397Sobrien{ 4422169689Skan unsigned i; 4423169689Skan reg_set_iterator rsi; 4424169689Skan 442590075Sobrien if (r == NULL) 442650397Sobrien { 442790075Sobrien fputs (" (nil)", outf); 442890075Sobrien return; 442950397Sobrien } 443050397Sobrien 4431169689Skan EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi) 443250397Sobrien { 443390075Sobrien fprintf (outf, " %d", i); 443490075Sobrien if (i < FIRST_PSEUDO_REGISTER) 443590075Sobrien fprintf (outf, " [%s]", 443690075Sobrien reg_names[i]); 4437169689Skan } 443850397Sobrien} 443950397Sobrien 4440132718Skan/* Print a human-readable representation of R on the standard error 444190075Sobrien stream. This function is designed to be used from within the 444290075Sobrien debugger. */ 444350397Sobrien 444450397Sobrienvoid 4445132718Skandebug_regset (regset r) 444650397Sobrien{ 444790075Sobrien dump_regset (r, stderr); 444890075Sobrien putc ('\n', stderr); 444950397Sobrien} 445050397Sobrien 445150397Sobrien/* Recompute register set/reference counts immediately prior to register 445250397Sobrien allocation. 445350397Sobrien 445450397Sobrien This avoids problems with set/reference counts changing to/from values 445550397Sobrien which have special meanings to the register allocators. 445650397Sobrien 445750397Sobrien Additionally, the reference counts are the primary component used by the 445850397Sobrien register allocators to prioritize pseudos for allocation to hard regs. 445950397Sobrien More accurate reference counts generally lead to better register allocation. 446050397Sobrien 446150397Sobrien It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and 446250397Sobrien possibly other information which is used by the register allocators. */ 446350397Sobrien 4464169689Skanstatic unsigned int 4465169689Skanrecompute_reg_usage (void) 446650397Sobrien{ 446790075Sobrien allocate_reg_life_data (); 4468169689Skan /* distribute_notes in combiner fails to convert some of the 4469169689Skan REG_UNUSED notes to REG_DEAD notes. This causes CHECK_DEAD_NOTES 4470169689Skan in sched1 to die. To solve this update the DEATH_NOTES 4471169689Skan here. */ 4472169689Skan update_life_info (NULL, UPDATE_LIFE_LOCAL, PROP_REG_INFO | PROP_DEATH_NOTES); 4473169689Skan 4474169689Skan if (dump_file) 4475169689Skan dump_flow_info (dump_file, dump_flags); 4476169689Skan return 0; 447790075Sobrien} 447850397Sobrien 4479169689Skanstruct tree_opt_pass pass_recompute_reg_usage = 4480169689Skan{ 4481169689Skan "life2", /* name */ 4482169689Skan NULL, /* gate */ 4483169689Skan recompute_reg_usage, /* execute */ 4484169689Skan NULL, /* sub */ 4485169689Skan NULL, /* next */ 4486169689Skan 0, /* static_pass_number */ 4487169689Skan 0, /* tv_id */ 4488169689Skan 0, /* properties_required */ 4489169689Skan 0, /* properties_provided */ 4490169689Skan 0, /* properties_destroyed */ 4491169689Skan 0, /* todo_flags_start */ 4492169689Skan TODO_dump_func, /* todo_flags_finish */ 4493169689Skan 'f' /* letter */ 4494169689Skan}; 4495169689Skan 449690075Sobrien/* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of 449790075Sobrien blocks. If BLOCKS is NULL, assume the universal set. Returns a count 4498169689Skan of the number of registers that died. 4499169689Skan If KILL is 1, remove old REG_DEAD / REG_UNUSED notes. If it is 0, don't. 4500169689Skan if it is -1, remove them unless they pertain to a stack reg. */ 450150397Sobrien 450290075Sobrienint 4503132718Skancount_or_remove_death_notes (sbitmap blocks, int kill) 450490075Sobrien{ 4505117395Skan int count = 0; 4506169689Skan unsigned int i = 0; 4507117395Skan basic_block bb; 450890075Sobrien 4509132718Skan /* This used to be a loop over all the blocks with a membership test 4510132718Skan inside the loop. That can be amazingly expensive on a large CFG 4511132718Skan when only a small number of bits are set in BLOCKs (for example, 4512132718Skan the calls from the scheduler typically have very few bits set). 4513132718Skan 4514132718Skan For extra credit, someone should convert BLOCKS to a bitmap rather 4515132718Skan than an sbitmap. */ 4516132718Skan if (blocks) 451750397Sobrien { 4518169689Skan sbitmap_iterator sbi; 4519169689Skan 4520169689Skan EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i, sbi) 4521132718Skan { 4522169689Skan basic_block bb = BASIC_BLOCK (i); 4523169689Skan /* The bitmap may be flawed in that one of the basic blocks 4524169689Skan may have been deleted before you get here. */ 4525169689Skan if (bb) 4526169689Skan count += count_or_remove_death_notes_bb (bb, kill); 4527169689Skan }; 4528132718Skan } 4529132718Skan else 4530132718Skan { 4531132718Skan FOR_EACH_BB (bb) 4532132718Skan { 4533132718Skan count += count_or_remove_death_notes_bb (bb, kill); 4534132718Skan } 4535132718Skan } 453650397Sobrien 4537132718Skan return count; 4538132718Skan} 4539132718Skan 4540132718Skan/* Optionally removes all the REG_DEAD and REG_UNUSED notes from basic 4541132718Skan block BB. Returns a count of the number of registers that died. */ 454250397Sobrien 4543132718Skanstatic int 4544132718Skancount_or_remove_death_notes_bb (basic_block bb, int kill) 4545132718Skan{ 4546132718Skan int count = 0; 4547132718Skan rtx insn; 4548132718Skan 4549132718Skan for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 4550132718Skan { 4551132718Skan if (INSN_P (insn)) 455290075Sobrien { 4553132718Skan rtx *pprev = ®_NOTES (insn); 4554132718Skan rtx link = *pprev; 4555132718Skan 4556132718Skan while (link) 455750397Sobrien { 4558132718Skan switch (REG_NOTE_KIND (link)) 455990075Sobrien { 4560132718Skan case REG_DEAD: 4561169689Skan if (REG_P (XEXP (link, 0))) 456290075Sobrien { 4563132718Skan rtx reg = XEXP (link, 0); 4564132718Skan int n; 456550397Sobrien 4566132718Skan if (REGNO (reg) >= FIRST_PSEUDO_REGISTER) 4567132718Skan n = 1; 4568132718Skan else 4569169689Skan n = hard_regno_nregs[REGNO (reg)][GET_MODE (reg)]; 4570132718Skan count += n; 4571132718Skan } 457250397Sobrien 4573132718Skan /* Fall through. */ 457490075Sobrien 4575132718Skan case REG_UNUSED: 4576169689Skan if (kill > 0 4577169689Skan || (kill 4578169689Skan#ifdef STACK_REGS 4579169689Skan && (!REG_P (XEXP (link, 0)) 4580169689Skan || !IN_RANGE (REGNO (XEXP (link, 0)), 4581169689Skan FIRST_STACK_REG, LAST_STACK_REG)) 4582169689Skan#endif 4583169689Skan )) 4584132718Skan { 4585132718Skan rtx next = XEXP (link, 1); 4586132718Skan free_EXPR_LIST_node (link); 4587132718Skan *pprev = link = next; 458890075Sobrien break; 458990075Sobrien } 4590132718Skan /* Fall through. */ 4591132718Skan 4592132718Skan default: 4593132718Skan pprev = &XEXP (link, 1); 4594132718Skan link = *pprev; 4595132718Skan break; 459690075Sobrien } 459750397Sobrien } 4598132718Skan } 459990075Sobrien 4600132718Skan if (insn == BB_END (bb)) 4601132718Skan break; 460250397Sobrien } 460390075Sobrien 460490075Sobrien return count; 460550397Sobrien} 4606132718Skan 460790075Sobrien/* Clear LOG_LINKS fields of insns in a selected blocks or whole chain 460890075Sobrien if blocks is NULL. */ 460952284Sobrien 461090075Sobrienstatic void 4611132718Skanclear_log_links (sbitmap blocks) 461290075Sobrien{ 461390075Sobrien rtx insn; 461452284Sobrien 461590075Sobrien if (!blocks) 461652284Sobrien { 461790075Sobrien for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 461890075Sobrien if (INSN_P (insn)) 461990075Sobrien free_INSN_LIST_list (&LOG_LINKS (insn)); 462052284Sobrien } 462190075Sobrien else 4622169689Skan { 4623169689Skan unsigned int i = 0; 4624169689Skan sbitmap_iterator sbi; 462552284Sobrien 4626169689Skan EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i, sbi) 4627169689Skan { 4628169689Skan basic_block bb = BASIC_BLOCK (i); 4629169689Skan 4630169689Skan for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 4631169689Skan insn = NEXT_INSN (insn)) 4632169689Skan if (INSN_P (insn)) 4633169689Skan free_INSN_LIST_list (&LOG_LINKS (insn)); 4634169689Skan } 4635169689Skan } 463652284Sobrien} 463752284Sobrien 463890075Sobrien/* Given a register bitmap, turn on the bits in a HARD_REG_SET that 463990075Sobrien correspond to the hard registers, if any, set in that map. This 464090075Sobrien could be done far more efficiently by having all sorts of special-cases 464190075Sobrien with moving single words, but probably isn't worth the trouble. */ 464252284Sobrien 464352284Sobrienvoid 4644132718Skanreg_set_to_hard_reg_set (HARD_REG_SET *to, bitmap from) 464552284Sobrien{ 4646169689Skan unsigned i; 4647169689Skan bitmap_iterator bi; 464852284Sobrien 4649169689Skan EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi) 4650169689Skan { 4651169689Skan if (i >= FIRST_PSEUDO_REGISTER) 4652169689Skan return; 4653169689Skan SET_HARD_REG_BIT (*to, i); 4654169689Skan } 465552284Sobrien} 4656169689Skan 4657169689Skan 4658169689Skanstatic bool 4659169689Skangate_remove_death_notes (void) 4660169689Skan{ 4661169689Skan return flag_profile_values; 4662169689Skan} 4663169689Skan 4664169689Skanstatic unsigned int 4665169689Skanrest_of_handle_remove_death_notes (void) 4666169689Skan{ 4667169689Skan count_or_remove_death_notes (NULL, 1); 4668169689Skan return 0; 4669169689Skan} 4670169689Skan 4671169689Skanstruct tree_opt_pass pass_remove_death_notes = 4672169689Skan{ 4673169689Skan "ednotes", /* name */ 4674169689Skan gate_remove_death_notes, /* gate */ 4675169689Skan rest_of_handle_remove_death_notes, /* execute */ 4676169689Skan NULL, /* sub */ 4677169689Skan NULL, /* next */ 4678169689Skan 0, /* static_pass_number */ 4679169689Skan 0, /* tv_id */ 4680169689Skan 0, /* properties_required */ 4681169689Skan 0, /* properties_provided */ 4682169689Skan 0, /* properties_destroyed */ 4683169689Skan 0, /* todo_flags_start */ 4684169689Skan 0, /* todo_flags_finish */ 4685169689Skan 0 /* letter */ 4686169689Skan}; 4687169689Skan 4688169689Skan/* Perform life analysis. */ 4689169689Skanstatic unsigned int 4690169689Skanrest_of_handle_life (void) 4691169689Skan{ 4692169689Skan regclass_init (); 4693169689Skan 4694169689Skan life_analysis (PROP_FINAL); 4695169689Skan if (optimize) 4696169689Skan cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_UPDATE_LIFE | CLEANUP_LOG_LINKS 4697169689Skan | (flag_thread_jumps ? CLEANUP_THREADING : 0)); 4698169689Skan 4699169689Skan if (extra_warnings) 4700169689Skan { 4701169689Skan setjmp_vars_warning (DECL_INITIAL (current_function_decl)); 4702169689Skan setjmp_args_warning (); 4703169689Skan } 4704169689Skan 4705169689Skan if (optimize) 4706169689Skan { 4707169689Skan if (initialize_uninitialized_subregs ()) 4708169689Skan { 4709169689Skan /* Insns were inserted, and possibly pseudos created, so 4710169689Skan things might look a bit different. */ 4711169689Skan allocate_reg_life_data (); 4712169689Skan update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES, 4713169689Skan PROP_LOG_LINKS | PROP_REG_INFO | PROP_DEATH_NOTES); 4714169689Skan } 4715169689Skan } 4716169689Skan 4717169689Skan no_new_pseudos = 1; 4718169689Skan return 0; 4719169689Skan} 4720169689Skan 4721169689Skanstruct tree_opt_pass pass_life = 4722169689Skan{ 4723169689Skan "life1", /* name */ 4724169689Skan NULL, /* gate */ 4725169689Skan rest_of_handle_life, /* execute */ 4726169689Skan NULL, /* sub */ 4727169689Skan NULL, /* next */ 4728169689Skan 0, /* static_pass_number */ 4729169689Skan TV_FLOW, /* tv_id */ 4730169689Skan 0, /* properties_required */ 4731169689Skan 0, /* properties_provided */ 4732169689Skan 0, /* properties_destroyed */ 4733169689Skan TODO_verify_flow, /* todo_flags_start */ 4734169689Skan TODO_dump_func | 4735169689Skan TODO_ggc_collect, /* todo_flags_finish */ 4736169689Skan 'f' /* letter */ 4737169689Skan}; 4738169689Skan 4739169689Skanstatic unsigned int 4740169689Skanrest_of_handle_flow2 (void) 4741169689Skan{ 4742169689Skan /* If optimizing, then go ahead and split insns now. */ 4743169689Skan#ifndef STACK_REGS 4744169689Skan if (optimize > 0) 4745169689Skan#endif 4746169689Skan split_all_insns (0); 4747169689Skan 4748169689Skan if (flag_branch_target_load_optimize) 4749169689Skan branch_target_load_optimize (epilogue_completed); 4750169689Skan 4751169689Skan if (optimize) 4752169689Skan cleanup_cfg (CLEANUP_EXPENSIVE); 4753169689Skan 4754169689Skan /* On some machines, the prologue and epilogue code, or parts thereof, 4755169689Skan can be represented as RTL. Doing so lets us schedule insns between 4756169689Skan it and the rest of the code and also allows delayed branch 4757169689Skan scheduling to operate in the epilogue. */ 4758169689Skan thread_prologue_and_epilogue_insns (get_insns ()); 4759169689Skan epilogue_completed = 1; 4760169689Skan flow2_completed = 1; 4761169689Skan return 0; 4762169689Skan} 4763169689Skan 4764169689Skanstruct tree_opt_pass pass_flow2 = 4765169689Skan{ 4766169689Skan "flow2", /* name */ 4767169689Skan NULL, /* gate */ 4768169689Skan rest_of_handle_flow2, /* execute */ 4769169689Skan NULL, /* sub */ 4770169689Skan NULL, /* next */ 4771169689Skan 0, /* static_pass_number */ 4772169689Skan TV_FLOW2, /* tv_id */ 4773169689Skan 0, /* properties_required */ 4774169689Skan 0, /* properties_provided */ 4775169689Skan 0, /* properties_destroyed */ 4776169689Skan TODO_verify_flow, /* todo_flags_start */ 4777169689Skan TODO_dump_func | 4778169689Skan TODO_ggc_collect, /* todo_flags_finish */ 4779169689Skan 'w' /* letter */ 4780169689Skan}; 4781169689Skan 4782