regrename.c revision 146895
190075Sobrien/* Register renaming for the GNU compiler. 2132718Skan Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. 390075Sobrien 490075Sobrien This file is part of GCC. 590075Sobrien 690075Sobrien GCC is free software; you can redistribute it and/or modify it 790075Sobrien under the terms of the GNU General Public License as published by 890075Sobrien the Free Software Foundation; either version 2, or (at your option) 990075Sobrien any later version. 1090075Sobrien 1190075Sobrien GCC is distributed in the hope that it will be useful, but WITHOUT 1290075Sobrien ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 1390075Sobrien or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 1490075Sobrien License for more details. 1590075Sobrien 1690075Sobrien You should have received a copy of the GNU General Public License 1790075Sobrien along with GCC; see the file COPYING. If not, write to the Free 1890075Sobrien Software Foundation, 59 Temple Place - Suite 330, Boston, MA 1990075Sobrien 02111-1307, USA. */ 2090075Sobrien 2190075Sobrien#define REG_OK_STRICT 2290075Sobrien 2390075Sobrien#include "config.h" 2490075Sobrien#include "system.h" 25132718Skan#include "coretypes.h" 26132718Skan#include "tm.h" 2790075Sobrien#include "rtl.h" 2890075Sobrien#include "tm_p.h" 2990075Sobrien#include "insn-config.h" 3090075Sobrien#include "regs.h" 3190075Sobrien#include "hard-reg-set.h" 3290075Sobrien#include "basic-block.h" 3390075Sobrien#include "reload.h" 3490075Sobrien#include "output.h" 3590075Sobrien#include "function.h" 3690075Sobrien#include "recog.h" 3790075Sobrien#include "flags.h" 3890075Sobrien#include "toplev.h" 3990075Sobrien#include "obstack.h" 4090075Sobrien 4190075Sobrien#ifndef REG_MODE_OK_FOR_BASE_P 4290075Sobrien#define REG_MODE_OK_FOR_BASE_P(REGNO, MODE) REG_OK_FOR_BASE_P (REGNO) 4390075Sobrien#endif 4490075Sobrien 4590075Sobrienstatic const char *const reg_class_names[] = REG_CLASS_NAMES; 4690075Sobrien 4790075Sobrienstruct du_chain 4890075Sobrien{ 4990075Sobrien struct du_chain *next_chain; 5090075Sobrien struct du_chain *next_use; 5190075Sobrien 5290075Sobrien rtx insn; 5390075Sobrien rtx *loc; 54132718Skan ENUM_BITFIELD(reg_class) class : 16; 5590075Sobrien unsigned int need_caller_save_reg:1; 5690075Sobrien unsigned int earlyclobber:1; 5790075Sobrien}; 5890075Sobrien 5990075Sobrienenum scan_actions 6090075Sobrien{ 6190075Sobrien terminate_all_read, 6290075Sobrien terminate_overlapping_read, 6390075Sobrien terminate_write, 6490075Sobrien terminate_dead, 6590075Sobrien mark_read, 6690075Sobrien mark_write 6790075Sobrien}; 6890075Sobrien 6990075Sobrienstatic const char * const scan_actions_name[] = 7090075Sobrien{ 7190075Sobrien "terminate_all_read", 7290075Sobrien "terminate_overlapping_read", 7390075Sobrien "terminate_write", 7490075Sobrien "terminate_dead", 7590075Sobrien "mark_read", 7690075Sobrien "mark_write" 7790075Sobrien}; 7890075Sobrien 7990075Sobrienstatic struct obstack rename_obstack; 8090075Sobrien 81132718Skanstatic void do_replace (struct du_chain *, int); 82132718Skanstatic void scan_rtx_reg (rtx, rtx *, enum reg_class, 83132718Skan enum scan_actions, enum op_type, int); 84132718Skanstatic void scan_rtx_address (rtx, rtx *, enum reg_class, 85132718Skan enum scan_actions, enum machine_mode); 86132718Skanstatic void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions, 87132718Skan enum op_type, int); 88132718Skanstatic struct du_chain *build_def_use (basic_block); 89132718Skanstatic void dump_def_use_chain (struct du_chain *); 90132718Skanstatic void note_sets (rtx, rtx, void *); 91132718Skanstatic void clear_dead_regs (HARD_REG_SET *, enum machine_mode, rtx); 92132718Skanstatic void merge_overlapping_regs (basic_block, HARD_REG_SET *, 93132718Skan struct du_chain *); 9490075Sobrien 9590075Sobrien/* Called through note_stores from update_life. Find sets of registers, and 9690075Sobrien record them in *DATA (which is actually a HARD_REG_SET *). */ 9790075Sobrien 9890075Sobrienstatic void 99132718Skannote_sets (rtx x, rtx set ATTRIBUTE_UNUSED, void *data) 10090075Sobrien{ 10190075Sobrien HARD_REG_SET *pset = (HARD_REG_SET *) data; 10290075Sobrien unsigned int regno; 10390075Sobrien int nregs; 104146895Skan 105146895Skan if (GET_CODE (x) == SUBREG) 106146895Skan x = SUBREG_REG (x); 10790075Sobrien if (GET_CODE (x) != REG) 10890075Sobrien return; 109146895Skan 11090075Sobrien regno = REGNO (x); 11190075Sobrien nregs = HARD_REGNO_NREGS (regno, GET_MODE (x)); 11290075Sobrien 11390075Sobrien /* There must not be pseudos at this point. */ 11490075Sobrien if (regno + nregs > FIRST_PSEUDO_REGISTER) 11590075Sobrien abort (); 11690075Sobrien 11790075Sobrien while (nregs-- > 0) 11890075Sobrien SET_HARD_REG_BIT (*pset, regno + nregs); 11990075Sobrien} 12090075Sobrien 12190075Sobrien/* Clear all registers from *PSET for which a note of kind KIND can be found 12290075Sobrien in the list NOTES. */ 12390075Sobrien 12490075Sobrienstatic void 125132718Skanclear_dead_regs (HARD_REG_SET *pset, enum machine_mode kind, rtx notes) 12690075Sobrien{ 12790075Sobrien rtx note; 12890075Sobrien for (note = notes; note; note = XEXP (note, 1)) 12990075Sobrien if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0))) 13090075Sobrien { 13190075Sobrien rtx reg = XEXP (note, 0); 13290075Sobrien unsigned int regno = REGNO (reg); 13390075Sobrien int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg)); 13490075Sobrien 13590075Sobrien /* There must not be pseudos at this point. */ 13690075Sobrien if (regno + nregs > FIRST_PSEUDO_REGISTER) 13790075Sobrien abort (); 13890075Sobrien 13990075Sobrien while (nregs-- > 0) 14090075Sobrien CLEAR_HARD_REG_BIT (*pset, regno + nregs); 14190075Sobrien } 14290075Sobrien} 14390075Sobrien 14490075Sobrien/* For a def-use chain CHAIN in basic block B, find which registers overlap 14590075Sobrien its lifetime and set the corresponding bits in *PSET. */ 14690075Sobrien 14790075Sobrienstatic void 148132718Skanmerge_overlapping_regs (basic_block b, HARD_REG_SET *pset, 149132718Skan struct du_chain *chain) 15090075Sobrien{ 15190075Sobrien struct du_chain *t = chain; 15290075Sobrien rtx insn; 15390075Sobrien HARD_REG_SET live; 15490075Sobrien 15590075Sobrien REG_SET_TO_HARD_REG_SET (live, b->global_live_at_start); 156132718Skan insn = BB_HEAD (b); 15790075Sobrien while (t) 15890075Sobrien { 15990075Sobrien /* Search forward until the next reference to the register to be 16090075Sobrien renamed. */ 16190075Sobrien while (insn != t->insn) 16290075Sobrien { 16390075Sobrien if (INSN_P (insn)) 16490075Sobrien { 16590075Sobrien clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn)); 16690075Sobrien note_stores (PATTERN (insn), note_sets, (void *) &live); 16790075Sobrien /* Only record currently live regs if we are inside the 16890075Sobrien reg's live range. */ 16990075Sobrien if (t != chain) 17090075Sobrien IOR_HARD_REG_SET (*pset, live); 171117395Skan clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn)); 17290075Sobrien } 17390075Sobrien insn = NEXT_INSN (insn); 17490075Sobrien } 17590075Sobrien 17690075Sobrien IOR_HARD_REG_SET (*pset, live); 17790075Sobrien 17890075Sobrien /* For the last reference, also merge in all registers set in the 17990075Sobrien same insn. 18090075Sobrien @@@ We only have take earlyclobbered sets into account. */ 18190075Sobrien if (! t->next_use) 18290075Sobrien note_stores (PATTERN (insn), note_sets, (void *) pset); 18390075Sobrien 18490075Sobrien t = t->next_use; 18590075Sobrien } 18690075Sobrien} 18790075Sobrien 18890075Sobrien/* Perform register renaming on the current function. */ 18990075Sobrien 19090075Sobrienvoid 191132718Skanregrename_optimize (void) 19290075Sobrien{ 19390075Sobrien int tick[FIRST_PSEUDO_REGISTER]; 19490075Sobrien int this_tick = 0; 195117395Skan basic_block bb; 19690075Sobrien char *first_obj; 19790075Sobrien 19890075Sobrien memset (tick, 0, sizeof tick); 19990075Sobrien 20090075Sobrien gcc_obstack_init (&rename_obstack); 201132718Skan first_obj = obstack_alloc (&rename_obstack, 0); 20290075Sobrien 203117395Skan FOR_EACH_BB (bb) 20490075Sobrien { 20590075Sobrien struct du_chain *all_chains = 0; 20690075Sobrien HARD_REG_SET unavailable; 20790075Sobrien HARD_REG_SET regs_seen; 20890075Sobrien 20990075Sobrien CLEAR_HARD_REG_SET (unavailable); 21090075Sobrien 21190075Sobrien if (rtl_dump_file) 212117395Skan fprintf (rtl_dump_file, "\nBasic block %d:\n", bb->index); 21390075Sobrien 21490075Sobrien all_chains = build_def_use (bb); 21590075Sobrien 21690075Sobrien if (rtl_dump_file) 21790075Sobrien dump_def_use_chain (all_chains); 21890075Sobrien 21990075Sobrien CLEAR_HARD_REG_SET (unavailable); 22090075Sobrien /* Don't clobber traceback for noreturn functions. */ 22190075Sobrien if (frame_pointer_needed) 22290075Sobrien { 22390075Sobrien int i; 224117395Skan 22590075Sobrien for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;) 22690075Sobrien SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM + i); 227117395Skan 22890075Sobrien#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 22990075Sobrien for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;) 23090075Sobrien SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM + i); 23190075Sobrien#endif 23290075Sobrien } 23390075Sobrien 23490075Sobrien CLEAR_HARD_REG_SET (regs_seen); 23590075Sobrien while (all_chains) 23690075Sobrien { 237132718Skan int new_reg, best_new_reg; 23890075Sobrien int n_uses; 23990075Sobrien struct du_chain *this = all_chains; 24090075Sobrien struct du_chain *tmp, *last; 24190075Sobrien HARD_REG_SET this_unavailable; 24290075Sobrien int reg = REGNO (*this->loc); 24390075Sobrien int i; 24490075Sobrien 24590075Sobrien all_chains = this->next_chain; 246117395Skan 247132718Skan best_new_reg = reg; 248132718Skan 24990075Sobrien#if 0 /* This just disables optimization opportunities. */ 25090075Sobrien /* Only rename once we've seen the reg more than once. */ 25190075Sobrien if (! TEST_HARD_REG_BIT (regs_seen, reg)) 25290075Sobrien { 25390075Sobrien SET_HARD_REG_BIT (regs_seen, reg); 25490075Sobrien continue; 25590075Sobrien } 25690075Sobrien#endif 25790075Sobrien 25890075Sobrien if (fixed_regs[reg] || global_regs[reg] 25990075Sobrien#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 26090075Sobrien || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM) 26190075Sobrien#else 26290075Sobrien || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM) 26390075Sobrien#endif 26490075Sobrien ) 26590075Sobrien continue; 26690075Sobrien 26790075Sobrien COPY_HARD_REG_SET (this_unavailable, unavailable); 26890075Sobrien 26990075Sobrien /* Find last entry on chain (which has the need_caller_save bit), 27090075Sobrien count number of uses, and narrow the set of registers we can 27190075Sobrien use for renaming. */ 27290075Sobrien n_uses = 0; 27390075Sobrien for (last = this; last->next_use; last = last->next_use) 27490075Sobrien { 27590075Sobrien n_uses++; 27690075Sobrien IOR_COMPL_HARD_REG_SET (this_unavailable, 27790075Sobrien reg_class_contents[last->class]); 27890075Sobrien } 27990075Sobrien if (n_uses < 1) 28090075Sobrien continue; 28190075Sobrien 28290075Sobrien IOR_COMPL_HARD_REG_SET (this_unavailable, 28390075Sobrien reg_class_contents[last->class]); 28490075Sobrien 28590075Sobrien if (this->need_caller_save_reg) 28690075Sobrien IOR_HARD_REG_SET (this_unavailable, call_used_reg_set); 28790075Sobrien 28890075Sobrien merge_overlapping_regs (bb, &this_unavailable, this); 28990075Sobrien 29090075Sobrien /* Now potential_regs is a reasonable approximation, let's 29190075Sobrien have a closer look at each register still in there. */ 29290075Sobrien for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++) 29390075Sobrien { 29490075Sobrien int nregs = HARD_REGNO_NREGS (new_reg, GET_MODE (*this->loc)); 29590075Sobrien 29690075Sobrien for (i = nregs - 1; i >= 0; --i) 29790075Sobrien if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i) 29890075Sobrien || fixed_regs[new_reg + i] 29990075Sobrien || global_regs[new_reg + i] 30090075Sobrien /* Can't use regs which aren't saved by the prologue. */ 30190075Sobrien || (! regs_ever_live[new_reg + i] 30290075Sobrien && ! call_used_regs[new_reg + i]) 30390075Sobrien#ifdef LEAF_REGISTERS 304117395Skan /* We can't use a non-leaf register if we're in a 30590075Sobrien leaf function. */ 306117395Skan || (current_function_is_leaf 30790075Sobrien && !LEAF_REGISTERS[new_reg + i]) 30890075Sobrien#endif 30990075Sobrien#ifdef HARD_REGNO_RENAME_OK 31090075Sobrien || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i) 31190075Sobrien#endif 31290075Sobrien ) 31390075Sobrien break; 31490075Sobrien if (i >= 0) 31590075Sobrien continue; 31690075Sobrien 31790075Sobrien /* See whether it accepts all modes that occur in 31890075Sobrien definition and uses. */ 31990075Sobrien for (tmp = this; tmp; tmp = tmp->next_use) 32096263Sobrien if (! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc)) 32196263Sobrien || (tmp->need_caller_save_reg 32296263Sobrien && ! (HARD_REGNO_CALL_PART_CLOBBERED 32396263Sobrien (reg, GET_MODE (*tmp->loc))) 32496263Sobrien && (HARD_REGNO_CALL_PART_CLOBBERED 32596263Sobrien (new_reg, GET_MODE (*tmp->loc))))) 32690075Sobrien break; 32790075Sobrien if (! tmp) 32890075Sobrien { 329132718Skan if (tick[best_new_reg] > tick[new_reg]) 33090075Sobrien best_new_reg = new_reg; 33190075Sobrien } 33290075Sobrien } 33390075Sobrien 33490075Sobrien if (rtl_dump_file) 33590075Sobrien { 33690075Sobrien fprintf (rtl_dump_file, "Register %s in insn %d", 33790075Sobrien reg_names[reg], INSN_UID (last->insn)); 33890075Sobrien if (last->need_caller_save_reg) 33990075Sobrien fprintf (rtl_dump_file, " crosses a call"); 340117395Skan } 34190075Sobrien 342132718Skan if (best_new_reg == reg) 34390075Sobrien { 344132718Skan tick[reg] = ++this_tick; 34590075Sobrien if (rtl_dump_file) 346132718Skan fprintf (rtl_dump_file, "; no available better choice\n"); 34790075Sobrien continue; 34890075Sobrien } 34990075Sobrien 35090075Sobrien do_replace (this, best_new_reg); 351132718Skan tick[best_new_reg] = ++this_tick; 35290075Sobrien 35390075Sobrien if (rtl_dump_file) 35490075Sobrien fprintf (rtl_dump_file, ", renamed as %s\n", reg_names[best_new_reg]); 35590075Sobrien } 35690075Sobrien 35790075Sobrien obstack_free (&rename_obstack, first_obj); 35890075Sobrien } 35990075Sobrien 36090075Sobrien obstack_free (&rename_obstack, NULL); 36190075Sobrien 36290075Sobrien if (rtl_dump_file) 36390075Sobrien fputc ('\n', rtl_dump_file); 36490075Sobrien 36590075Sobrien count_or_remove_death_notes (NULL, 1); 36690075Sobrien update_life_info (NULL, UPDATE_LIFE_LOCAL, 36790075Sobrien PROP_REG_INFO | PROP_DEATH_NOTES); 36890075Sobrien} 36990075Sobrien 37090075Sobrienstatic void 371132718Skando_replace (struct du_chain *chain, int reg) 37290075Sobrien{ 37390075Sobrien while (chain) 37490075Sobrien { 37590075Sobrien unsigned int regno = ORIGINAL_REGNO (*chain->loc); 376132718Skan struct reg_attrs * attr = REG_ATTRS (*chain->loc); 377132718Skan 37890075Sobrien *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg); 37990075Sobrien if (regno >= FIRST_PSEUDO_REGISTER) 38090075Sobrien ORIGINAL_REGNO (*chain->loc) = regno; 381132718Skan REG_ATTRS (*chain->loc) = attr; 38290075Sobrien chain = chain->next_use; 38390075Sobrien } 38490075Sobrien} 38590075Sobrien 38690075Sobrien 38790075Sobrienstatic struct du_chain *open_chains; 38890075Sobrienstatic struct du_chain *closed_chains; 38990075Sobrien 39090075Sobrienstatic void 391132718Skanscan_rtx_reg (rtx insn, rtx *loc, enum reg_class class, 392132718Skan enum scan_actions action, enum op_type type, int earlyclobber) 39390075Sobrien{ 39490075Sobrien struct du_chain **p; 39590075Sobrien rtx x = *loc; 39690075Sobrien enum machine_mode mode = GET_MODE (x); 39790075Sobrien int this_regno = REGNO (x); 39890075Sobrien int this_nregs = HARD_REGNO_NREGS (this_regno, mode); 39990075Sobrien 40090075Sobrien if (action == mark_write) 40190075Sobrien { 40290075Sobrien if (type == OP_OUT) 40390075Sobrien { 404132718Skan struct du_chain *this 405132718Skan = obstack_alloc (&rename_obstack, sizeof (struct du_chain)); 40690075Sobrien this->next_use = 0; 40790075Sobrien this->next_chain = open_chains; 40890075Sobrien this->loc = loc; 40990075Sobrien this->insn = insn; 41090075Sobrien this->class = class; 41190075Sobrien this->need_caller_save_reg = 0; 41290075Sobrien this->earlyclobber = earlyclobber; 41390075Sobrien open_chains = this; 41490075Sobrien } 41590075Sobrien return; 41690075Sobrien } 41790075Sobrien 41890075Sobrien if ((type == OP_OUT && action != terminate_write) 41990075Sobrien || (type != OP_OUT && action == terminate_write)) 42090075Sobrien return; 42190075Sobrien 42290075Sobrien for (p = &open_chains; *p;) 42390075Sobrien { 42490075Sobrien struct du_chain *this = *p; 42590075Sobrien 42690075Sobrien /* Check if the chain has been terminated if it has then skip to 42790075Sobrien the next chain. 42890075Sobrien 42990075Sobrien This can happen when we've already appended the location to 43090075Sobrien the chain in Step 3, but are trying to hide in-out operands 43190075Sobrien from terminate_write in Step 5. */ 43290075Sobrien 43390075Sobrien if (*this->loc == cc0_rtx) 43490075Sobrien p = &this->next_chain; 43590075Sobrien else 436117395Skan { 43790075Sobrien int regno = REGNO (*this->loc); 43890075Sobrien int nregs = HARD_REGNO_NREGS (regno, GET_MODE (*this->loc)); 43990075Sobrien int exact_match = (regno == this_regno && nregs == this_nregs); 44090075Sobrien 44190075Sobrien if (regno + nregs <= this_regno 44290075Sobrien || this_regno + this_nregs <= regno) 44390075Sobrien { 44490075Sobrien p = &this->next_chain; 44590075Sobrien continue; 44690075Sobrien } 44790075Sobrien 44890075Sobrien if (action == mark_read) 44990075Sobrien { 45090075Sobrien if (! exact_match) 45190075Sobrien abort (); 45290075Sobrien 453117395Skan /* ??? Class NO_REGS can happen if the md file makes use of 45490075Sobrien EXTRA_CONSTRAINTS to match registers. Which is arguably 45590075Sobrien wrong, but there we are. Since we know not what this may 45690075Sobrien be replaced with, terminate the chain. */ 45790075Sobrien if (class != NO_REGS) 45890075Sobrien { 459132718Skan this = obstack_alloc (&rename_obstack, sizeof (struct du_chain)); 46090075Sobrien this->next_use = 0; 46190075Sobrien this->next_chain = (*p)->next_chain; 46290075Sobrien this->loc = loc; 46390075Sobrien this->insn = insn; 46490075Sobrien this->class = class; 46590075Sobrien this->need_caller_save_reg = 0; 46690075Sobrien while (*p) 46790075Sobrien p = &(*p)->next_use; 46890075Sobrien *p = this; 46990075Sobrien return; 47090075Sobrien } 47190075Sobrien } 47290075Sobrien 47390075Sobrien if (action != terminate_overlapping_read || ! exact_match) 47490075Sobrien { 47590075Sobrien struct du_chain *next = this->next_chain; 47690075Sobrien 47790075Sobrien /* Whether the terminated chain can be used for renaming 47890075Sobrien depends on the action and this being an exact match. 47990075Sobrien In either case, we remove this element from open_chains. */ 48090075Sobrien 48190075Sobrien if ((action == terminate_dead || action == terminate_write) 48290075Sobrien && exact_match) 48390075Sobrien { 48490075Sobrien this->next_chain = closed_chains; 48590075Sobrien closed_chains = this; 48690075Sobrien if (rtl_dump_file) 48790075Sobrien fprintf (rtl_dump_file, 48890075Sobrien "Closing chain %s at insn %d (%s)\n", 48990075Sobrien reg_names[REGNO (*this->loc)], INSN_UID (insn), 49090075Sobrien scan_actions_name[(int) action]); 49190075Sobrien } 49290075Sobrien else 49390075Sobrien { 49490075Sobrien if (rtl_dump_file) 49590075Sobrien fprintf (rtl_dump_file, 49690075Sobrien "Discarding chain %s at insn %d (%s)\n", 49790075Sobrien reg_names[REGNO (*this->loc)], INSN_UID (insn), 49890075Sobrien scan_actions_name[(int) action]); 49990075Sobrien } 50090075Sobrien *p = next; 50190075Sobrien } 50290075Sobrien else 50390075Sobrien p = &this->next_chain; 50490075Sobrien } 50590075Sobrien } 50690075Sobrien} 50790075Sobrien 50890075Sobrien/* Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or 50990075Sobrien BASE_REG_CLASS depending on how the register is being considered. */ 51090075Sobrien 51190075Sobrienstatic void 512132718Skanscan_rtx_address (rtx insn, rtx *loc, enum reg_class class, 513132718Skan enum scan_actions action, enum machine_mode mode) 51490075Sobrien{ 51590075Sobrien rtx x = *loc; 51690075Sobrien RTX_CODE code = GET_CODE (x); 51790075Sobrien const char *fmt; 51890075Sobrien int i, j; 51990075Sobrien 52090075Sobrien if (action == mark_write) 52190075Sobrien return; 52290075Sobrien 52390075Sobrien switch (code) 52490075Sobrien { 52590075Sobrien case PLUS: 52690075Sobrien { 52790075Sobrien rtx orig_op0 = XEXP (x, 0); 52890075Sobrien rtx orig_op1 = XEXP (x, 1); 52990075Sobrien RTX_CODE code0 = GET_CODE (orig_op0); 53090075Sobrien RTX_CODE code1 = GET_CODE (orig_op1); 53190075Sobrien rtx op0 = orig_op0; 53290075Sobrien rtx op1 = orig_op1; 53390075Sobrien rtx *locI = NULL; 53490075Sobrien rtx *locB = NULL; 53590075Sobrien 53690075Sobrien if (GET_CODE (op0) == SUBREG) 53790075Sobrien { 53890075Sobrien op0 = SUBREG_REG (op0); 53990075Sobrien code0 = GET_CODE (op0); 54090075Sobrien } 54190075Sobrien 54290075Sobrien if (GET_CODE (op1) == SUBREG) 54390075Sobrien { 54490075Sobrien op1 = SUBREG_REG (op1); 54590075Sobrien code1 = GET_CODE (op1); 54690075Sobrien } 54790075Sobrien 54890075Sobrien if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE 54990075Sobrien || code0 == ZERO_EXTEND || code1 == MEM) 55090075Sobrien { 55190075Sobrien locI = &XEXP (x, 0); 55290075Sobrien locB = &XEXP (x, 1); 55390075Sobrien } 55490075Sobrien else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE 55590075Sobrien || code1 == ZERO_EXTEND || code0 == MEM) 55690075Sobrien { 55790075Sobrien locI = &XEXP (x, 1); 55890075Sobrien locB = &XEXP (x, 0); 55990075Sobrien } 56090075Sobrien else if (code0 == CONST_INT || code0 == CONST 56190075Sobrien || code0 == SYMBOL_REF || code0 == LABEL_REF) 56290075Sobrien locB = &XEXP (x, 1); 56390075Sobrien else if (code1 == CONST_INT || code1 == CONST 56490075Sobrien || code1 == SYMBOL_REF || code1 == LABEL_REF) 56590075Sobrien locB = &XEXP (x, 0); 56690075Sobrien else if (code0 == REG && code1 == REG) 56790075Sobrien { 56890075Sobrien int index_op; 56990075Sobrien 57090075Sobrien if (REG_OK_FOR_INDEX_P (op0) 57190075Sobrien && REG_MODE_OK_FOR_BASE_P (op1, mode)) 57290075Sobrien index_op = 0; 57390075Sobrien else if (REG_OK_FOR_INDEX_P (op1) 57490075Sobrien && REG_MODE_OK_FOR_BASE_P (op0, mode)) 57590075Sobrien index_op = 1; 57690075Sobrien else if (REG_MODE_OK_FOR_BASE_P (op1, mode)) 57790075Sobrien index_op = 0; 57890075Sobrien else if (REG_MODE_OK_FOR_BASE_P (op0, mode)) 57990075Sobrien index_op = 1; 58090075Sobrien else if (REG_OK_FOR_INDEX_P (op1)) 58190075Sobrien index_op = 1; 58290075Sobrien else 58390075Sobrien index_op = 0; 58490075Sobrien 58590075Sobrien locI = &XEXP (x, index_op); 58690075Sobrien locB = &XEXP (x, !index_op); 58790075Sobrien } 58890075Sobrien else if (code0 == REG) 58990075Sobrien { 59090075Sobrien locI = &XEXP (x, 0); 59190075Sobrien locB = &XEXP (x, 1); 59290075Sobrien } 59390075Sobrien else if (code1 == REG) 59490075Sobrien { 59590075Sobrien locI = &XEXP (x, 1); 59690075Sobrien locB = &XEXP (x, 0); 59790075Sobrien } 59890075Sobrien 59990075Sobrien if (locI) 60090075Sobrien scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode); 60190075Sobrien if (locB) 60290075Sobrien scan_rtx_address (insn, locB, MODE_BASE_REG_CLASS (mode), action, mode); 60390075Sobrien return; 60490075Sobrien } 60590075Sobrien 60690075Sobrien case POST_INC: 60790075Sobrien case POST_DEC: 60890075Sobrien case POST_MODIFY: 60990075Sobrien case PRE_INC: 61090075Sobrien case PRE_DEC: 61190075Sobrien case PRE_MODIFY: 61290075Sobrien#ifndef AUTO_INC_DEC 61390075Sobrien /* If the target doesn't claim to handle autoinc, this must be 61490075Sobrien something special, like a stack push. Kill this chain. */ 61590075Sobrien action = terminate_all_read; 61690075Sobrien#endif 61790075Sobrien break; 61890075Sobrien 61990075Sobrien case MEM: 62090075Sobrien scan_rtx_address (insn, &XEXP (x, 0), 62190075Sobrien MODE_BASE_REG_CLASS (GET_MODE (x)), action, 62290075Sobrien GET_MODE (x)); 62390075Sobrien return; 62490075Sobrien 62590075Sobrien case REG: 62690075Sobrien scan_rtx_reg (insn, loc, class, action, OP_IN, 0); 62790075Sobrien return; 62890075Sobrien 62990075Sobrien default: 63090075Sobrien break; 63190075Sobrien } 63290075Sobrien 63390075Sobrien fmt = GET_RTX_FORMAT (code); 63490075Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 63590075Sobrien { 63690075Sobrien if (fmt[i] == 'e') 63790075Sobrien scan_rtx_address (insn, &XEXP (x, i), class, action, mode); 63890075Sobrien else if (fmt[i] == 'E') 63990075Sobrien for (j = XVECLEN (x, i) - 1; j >= 0; j--) 64090075Sobrien scan_rtx_address (insn, &XVECEXP (x, i, j), class, action, mode); 64190075Sobrien } 64290075Sobrien} 64390075Sobrien 64490075Sobrienstatic void 645132718Skanscan_rtx (rtx insn, rtx *loc, enum reg_class class, 646132718Skan enum scan_actions action, enum op_type type, int earlyclobber) 64790075Sobrien{ 64890075Sobrien const char *fmt; 64990075Sobrien rtx x = *loc; 65090075Sobrien enum rtx_code code = GET_CODE (x); 65190075Sobrien int i, j; 65290075Sobrien 65390075Sobrien code = GET_CODE (x); 65490075Sobrien switch (code) 65590075Sobrien { 65690075Sobrien case CONST: 65790075Sobrien case CONST_INT: 65890075Sobrien case CONST_DOUBLE: 65996263Sobrien case CONST_VECTOR: 66090075Sobrien case SYMBOL_REF: 66190075Sobrien case LABEL_REF: 66290075Sobrien case CC0: 66390075Sobrien case PC: 66490075Sobrien return; 66590075Sobrien 66690075Sobrien case REG: 66790075Sobrien scan_rtx_reg (insn, loc, class, action, type, earlyclobber); 66890075Sobrien return; 66990075Sobrien 67090075Sobrien case MEM: 67190075Sobrien scan_rtx_address (insn, &XEXP (x, 0), 67290075Sobrien MODE_BASE_REG_CLASS (GET_MODE (x)), action, 67390075Sobrien GET_MODE (x)); 67490075Sobrien return; 67590075Sobrien 67690075Sobrien case SET: 67790075Sobrien scan_rtx (insn, &SET_SRC (x), class, action, OP_IN, 0); 67890075Sobrien scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 0); 67990075Sobrien return; 68090075Sobrien 68190075Sobrien case STRICT_LOW_PART: 68290075Sobrien scan_rtx (insn, &XEXP (x, 0), class, action, OP_INOUT, earlyclobber); 68390075Sobrien return; 68490075Sobrien 68590075Sobrien case ZERO_EXTRACT: 686117395Skan case SIGN_EXTRACT: 68790075Sobrien scan_rtx (insn, &XEXP (x, 0), class, action, 68890075Sobrien type == OP_IN ? OP_IN : OP_INOUT, earlyclobber); 68990075Sobrien scan_rtx (insn, &XEXP (x, 1), class, action, OP_IN, 0); 69090075Sobrien scan_rtx (insn, &XEXP (x, 2), class, action, OP_IN, 0); 69190075Sobrien return; 69290075Sobrien 69390075Sobrien case POST_INC: 69490075Sobrien case PRE_INC: 69590075Sobrien case POST_DEC: 69690075Sobrien case PRE_DEC: 69790075Sobrien case POST_MODIFY: 69890075Sobrien case PRE_MODIFY: 69990075Sobrien /* Should only happen inside MEM. */ 70090075Sobrien abort (); 70190075Sobrien 70290075Sobrien case CLOBBER: 70390075Sobrien scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 1); 70490075Sobrien return; 70590075Sobrien 70690075Sobrien case EXPR_LIST: 70790075Sobrien scan_rtx (insn, &XEXP (x, 0), class, action, type, 0); 70890075Sobrien if (XEXP (x, 1)) 70990075Sobrien scan_rtx (insn, &XEXP (x, 1), class, action, type, 0); 71090075Sobrien return; 71190075Sobrien 71290075Sobrien default: 71390075Sobrien break; 71490075Sobrien } 71590075Sobrien 71690075Sobrien fmt = GET_RTX_FORMAT (code); 71790075Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 71890075Sobrien { 71990075Sobrien if (fmt[i] == 'e') 72090075Sobrien scan_rtx (insn, &XEXP (x, i), class, action, type, 0); 72190075Sobrien else if (fmt[i] == 'E') 72290075Sobrien for (j = XVECLEN (x, i) - 1; j >= 0; j--) 72390075Sobrien scan_rtx (insn, &XVECEXP (x, i, j), class, action, type, 0); 72490075Sobrien } 72590075Sobrien} 72690075Sobrien 727117395Skan/* Build def/use chain. */ 72890075Sobrien 72990075Sobrienstatic struct du_chain * 730132718Skanbuild_def_use (basic_block bb) 73190075Sobrien{ 73290075Sobrien rtx insn; 73390075Sobrien 73490075Sobrien open_chains = closed_chains = NULL; 73590075Sobrien 736132718Skan for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 73790075Sobrien { 73890075Sobrien if (INSN_P (insn)) 73990075Sobrien { 74090075Sobrien int n_ops; 74190075Sobrien rtx note; 74290075Sobrien rtx old_operands[MAX_RECOG_OPERANDS]; 74390075Sobrien rtx old_dups[MAX_DUP_OPERANDS]; 74496263Sobrien int i, icode; 74590075Sobrien int alt; 74690075Sobrien int predicated; 74790075Sobrien 74890075Sobrien /* Process the insn, determining its effect on the def-use 74990075Sobrien chains. We perform the following steps with the register 75090075Sobrien references in the insn: 75190075Sobrien (1) Any read that overlaps an open chain, but doesn't exactly 75290075Sobrien match, causes that chain to be closed. We can't deal 75390075Sobrien with overlaps yet. 75490075Sobrien (2) Any read outside an operand causes any chain it overlaps 75590075Sobrien with to be closed, since we can't replace it. 75690075Sobrien (3) Any read inside an operand is added if there's already 75790075Sobrien an open chain for it. 75890075Sobrien (4) For any REG_DEAD note we find, close open chains that 75990075Sobrien overlap it. 76090075Sobrien (5) For any write we find, close open chains that overlap it. 76190075Sobrien (6) For any write we find in an operand, make a new chain. 76290075Sobrien (7) For any REG_UNUSED, close any chains we just opened. */ 76390075Sobrien 76496263Sobrien icode = recog_memoized (insn); 76590075Sobrien extract_insn (insn); 766117395Skan if (! constrain_operands (1)) 767117395Skan fatal_insn_not_found (insn); 76890075Sobrien preprocess_constraints (); 76990075Sobrien alt = which_alternative; 77090075Sobrien n_ops = recog_data.n_operands; 77190075Sobrien 77290075Sobrien /* Simplify the code below by rewriting things to reflect 77390075Sobrien matching constraints. Also promote OP_OUT to OP_INOUT 77490075Sobrien in predicated instructions. */ 77590075Sobrien 77690075Sobrien predicated = GET_CODE (PATTERN (insn)) == COND_EXEC; 77790075Sobrien for (i = 0; i < n_ops; ++i) 77890075Sobrien { 77990075Sobrien int matches = recog_op_alt[i][alt].matches; 78090075Sobrien if (matches >= 0) 78190075Sobrien recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class; 78290075Sobrien if (matches >= 0 || recog_op_alt[i][alt].matched >= 0 78390075Sobrien || (predicated && recog_data.operand_type[i] == OP_OUT)) 78490075Sobrien recog_data.operand_type[i] = OP_INOUT; 78590075Sobrien } 78690075Sobrien 78790075Sobrien /* Step 1: Close chains for which we have overlapping reads. */ 78890075Sobrien for (i = 0; i < n_ops; i++) 78990075Sobrien scan_rtx (insn, recog_data.operand_loc[i], 79090075Sobrien NO_REGS, terminate_overlapping_read, 79190075Sobrien recog_data.operand_type[i], 0); 79290075Sobrien 79390075Sobrien /* Step 2: Close chains for which we have reads outside operands. 794117395Skan We do this by munging all operands into CC0, and closing 79590075Sobrien everything remaining. */ 79690075Sobrien 79790075Sobrien for (i = 0; i < n_ops; i++) 79890075Sobrien { 79990075Sobrien old_operands[i] = recog_data.operand[i]; 80090075Sobrien /* Don't squash match_operator or match_parallel here, since 801117395Skan we don't know that all of the contained registers are 80290075Sobrien reachable by proper operands. */ 80390075Sobrien if (recog_data.constraints[i][0] == '\0') 80490075Sobrien continue; 80590075Sobrien *recog_data.operand_loc[i] = cc0_rtx; 80690075Sobrien } 80790075Sobrien for (i = 0; i < recog_data.n_dups; i++) 80890075Sobrien { 80996263Sobrien int dup_num = recog_data.dup_num[i]; 81096263Sobrien 81190075Sobrien old_dups[i] = *recog_data.dup_loc[i]; 81290075Sobrien *recog_data.dup_loc[i] = cc0_rtx; 81396263Sobrien 81496263Sobrien /* For match_dup of match_operator or match_parallel, share 81596263Sobrien them, so that we don't miss changes in the dup. */ 81696263Sobrien if (icode >= 0 81796263Sobrien && insn_data[icode].operand[dup_num].eliminable == 0) 81896263Sobrien old_dups[i] = recog_data.operand[dup_num]; 81990075Sobrien } 82090075Sobrien 82190075Sobrien scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read, 82290075Sobrien OP_IN, 0); 82390075Sobrien 82490075Sobrien for (i = 0; i < recog_data.n_dups; i++) 82590075Sobrien *recog_data.dup_loc[i] = old_dups[i]; 82690075Sobrien for (i = 0; i < n_ops; i++) 82790075Sobrien *recog_data.operand_loc[i] = old_operands[i]; 82890075Sobrien 82990075Sobrien /* Step 2B: Can't rename function call argument registers. */ 83090075Sobrien if (GET_CODE (insn) == CALL_INSN && CALL_INSN_FUNCTION_USAGE (insn)) 83190075Sobrien scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn), 83290075Sobrien NO_REGS, terminate_all_read, OP_IN, 0); 83390075Sobrien 83490075Sobrien /* Step 2C: Can't rename asm operands that were originally 83590075Sobrien hard registers. */ 83690075Sobrien if (asm_noperands (PATTERN (insn)) > 0) 83790075Sobrien for (i = 0; i < n_ops; i++) 83890075Sobrien { 83990075Sobrien rtx *loc = recog_data.operand_loc[i]; 84090075Sobrien rtx op = *loc; 84190075Sobrien 84290075Sobrien if (GET_CODE (op) == REG 84390075Sobrien && REGNO (op) == ORIGINAL_REGNO (op) 84490075Sobrien && (recog_data.operand_type[i] == OP_IN 84590075Sobrien || recog_data.operand_type[i] == OP_INOUT)) 84690075Sobrien scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0); 84790075Sobrien } 84890075Sobrien 84990075Sobrien /* Step 3: Append to chains for reads inside operands. */ 85090075Sobrien for (i = 0; i < n_ops + recog_data.n_dups; i++) 85190075Sobrien { 85290075Sobrien int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; 85390075Sobrien rtx *loc = (i < n_ops 85490075Sobrien ? recog_data.operand_loc[opn] 85590075Sobrien : recog_data.dup_loc[i - n_ops]); 85690075Sobrien enum reg_class class = recog_op_alt[opn][alt].class; 85790075Sobrien enum op_type type = recog_data.operand_type[opn]; 85890075Sobrien 85990075Sobrien /* Don't scan match_operand here, since we've no reg class 86090075Sobrien information to pass down. Any operands that we could 86190075Sobrien substitute in will be represented elsewhere. */ 86290075Sobrien if (recog_data.constraints[opn][0] == '\0') 86390075Sobrien continue; 86490075Sobrien 86590075Sobrien if (recog_op_alt[opn][alt].is_address) 86690075Sobrien scan_rtx_address (insn, loc, class, mark_read, VOIDmode); 86790075Sobrien else 86890075Sobrien scan_rtx (insn, loc, class, mark_read, type, 0); 86990075Sobrien } 87090075Sobrien 87190075Sobrien /* Step 4: Close chains for registers that die here. 87290075Sobrien Also record updates for REG_INC notes. */ 87390075Sobrien for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 87490075Sobrien { 87590075Sobrien if (REG_NOTE_KIND (note) == REG_DEAD) 87690075Sobrien scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, 87790075Sobrien OP_IN, 0); 87890075Sobrien else if (REG_NOTE_KIND (note) == REG_INC) 87990075Sobrien scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read, 88090075Sobrien OP_INOUT, 0); 88190075Sobrien } 88290075Sobrien 88390075Sobrien /* Step 4B: If this is a call, any chain live at this point 88490075Sobrien requires a caller-saved reg. */ 88590075Sobrien if (GET_CODE (insn) == CALL_INSN) 88690075Sobrien { 88790075Sobrien struct du_chain *p; 88890075Sobrien for (p = open_chains; p; p = p->next_chain) 88990075Sobrien p->need_caller_save_reg = 1; 89090075Sobrien } 89190075Sobrien 89290075Sobrien /* Step 5: Close open chains that overlap writes. Similar to 89390075Sobrien step 2, we hide in-out operands, since we do not want to 89490075Sobrien close these chains. */ 89590075Sobrien 89690075Sobrien for (i = 0; i < n_ops; i++) 89790075Sobrien { 89890075Sobrien old_operands[i] = recog_data.operand[i]; 89990075Sobrien if (recog_data.operand_type[i] == OP_INOUT) 90090075Sobrien *recog_data.operand_loc[i] = cc0_rtx; 90190075Sobrien } 90290075Sobrien for (i = 0; i < recog_data.n_dups; i++) 90390075Sobrien { 90490075Sobrien int opn = recog_data.dup_num[i]; 90590075Sobrien old_dups[i] = *recog_data.dup_loc[i]; 90690075Sobrien if (recog_data.operand_type[opn] == OP_INOUT) 90790075Sobrien *recog_data.dup_loc[i] = cc0_rtx; 90890075Sobrien } 90990075Sobrien 91090075Sobrien scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0); 91190075Sobrien 91290075Sobrien for (i = 0; i < recog_data.n_dups; i++) 91390075Sobrien *recog_data.dup_loc[i] = old_dups[i]; 91490075Sobrien for (i = 0; i < n_ops; i++) 91590075Sobrien *recog_data.operand_loc[i] = old_operands[i]; 91690075Sobrien 91790075Sobrien /* Step 6: Begin new chains for writes inside operands. */ 91890075Sobrien /* ??? Many targets have output constraints on the SET_DEST 91990075Sobrien of a call insn, which is stupid, since these are certainly 92090075Sobrien ABI defined hard registers. Don't change calls at all. 92190075Sobrien Similarly take special care for asm statement that originally 92290075Sobrien referenced hard registers. */ 92390075Sobrien if (asm_noperands (PATTERN (insn)) > 0) 92490075Sobrien { 92590075Sobrien for (i = 0; i < n_ops; i++) 92690075Sobrien if (recog_data.operand_type[i] == OP_OUT) 92790075Sobrien { 92890075Sobrien rtx *loc = recog_data.operand_loc[i]; 92990075Sobrien rtx op = *loc; 93090075Sobrien enum reg_class class = recog_op_alt[i][alt].class; 93190075Sobrien 93290075Sobrien if (GET_CODE (op) == REG 933117395Skan && REGNO (op) == ORIGINAL_REGNO (op)) 93490075Sobrien continue; 93590075Sobrien 93690075Sobrien scan_rtx (insn, loc, class, mark_write, OP_OUT, 93790075Sobrien recog_op_alt[i][alt].earlyclobber); 93890075Sobrien } 93990075Sobrien } 94090075Sobrien else if (GET_CODE (insn) != CALL_INSN) 94190075Sobrien for (i = 0; i < n_ops + recog_data.n_dups; i++) 94290075Sobrien { 94390075Sobrien int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; 94490075Sobrien rtx *loc = (i < n_ops 94590075Sobrien ? recog_data.operand_loc[opn] 94690075Sobrien : recog_data.dup_loc[i - n_ops]); 94790075Sobrien enum reg_class class = recog_op_alt[opn][alt].class; 94890075Sobrien 94990075Sobrien if (recog_data.operand_type[opn] == OP_OUT) 95090075Sobrien scan_rtx (insn, loc, class, mark_write, OP_OUT, 95190075Sobrien recog_op_alt[opn][alt].earlyclobber); 95290075Sobrien } 95390075Sobrien 95490075Sobrien /* Step 7: Close chains for registers that were never 95590075Sobrien really used here. */ 95690075Sobrien for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 95790075Sobrien if (REG_NOTE_KIND (note) == REG_UNUSED) 95890075Sobrien scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, 95990075Sobrien OP_IN, 0); 96090075Sobrien } 961132718Skan if (insn == BB_END (bb)) 96290075Sobrien break; 96390075Sobrien } 96490075Sobrien 96590075Sobrien /* Since we close every chain when we find a REG_DEAD note, anything that 96690075Sobrien is still open lives past the basic block, so it can't be renamed. */ 96790075Sobrien return closed_chains; 96890075Sobrien} 96990075Sobrien 97090075Sobrien/* Dump all def/use chains in CHAINS to RTL_DUMP_FILE. They are 97190075Sobrien printed in reverse order as that's how we build them. */ 97290075Sobrien 97390075Sobrienstatic void 974132718Skandump_def_use_chain (struct du_chain *chains) 97590075Sobrien{ 97690075Sobrien while (chains) 97790075Sobrien { 97890075Sobrien struct du_chain *this = chains; 97990075Sobrien int r = REGNO (*this->loc); 98090075Sobrien int nregs = HARD_REGNO_NREGS (r, GET_MODE (*this->loc)); 98190075Sobrien fprintf (rtl_dump_file, "Register %s (%d):", reg_names[r], nregs); 98290075Sobrien while (this) 98390075Sobrien { 98490075Sobrien fprintf (rtl_dump_file, " %d [%s]", INSN_UID (this->insn), 98590075Sobrien reg_class_names[this->class]); 98690075Sobrien this = this->next_use; 98790075Sobrien } 98890075Sobrien fprintf (rtl_dump_file, "\n"); 98990075Sobrien chains = chains->next_chain; 99090075Sobrien } 99190075Sobrien} 99290075Sobrien 99390075Sobrien/* The following code does forward propagation of hard register copies. 99490075Sobrien The object is to eliminate as many dependencies as possible, so that 99590075Sobrien we have the most scheduling freedom. As a side effect, we also clean 996117395Skan up some silly register allocation decisions made by reload. This 99790075Sobrien code may be obsoleted by a new register allocator. */ 99890075Sobrien 99990075Sobrien/* For each register, we have a list of registers that contain the same 1000117395Skan value. The OLDEST_REGNO field points to the head of the list, and 100190075Sobrien the NEXT_REGNO field runs through the list. The MODE field indicates 100290075Sobrien what mode the data is known to be in; this field is VOIDmode when the 100390075Sobrien register is not known to contain valid data. */ 100490075Sobrien 100590075Sobrienstruct value_data_entry 100690075Sobrien{ 100790075Sobrien enum machine_mode mode; 100890075Sobrien unsigned int oldest_regno; 100990075Sobrien unsigned int next_regno; 101090075Sobrien}; 101190075Sobrien 101290075Sobrienstruct value_data 101390075Sobrien{ 101490075Sobrien struct value_data_entry e[FIRST_PSEUDO_REGISTER]; 101590075Sobrien unsigned int max_value_regs; 101690075Sobrien}; 101790075Sobrien 1018132718Skanstatic void kill_value_regno (unsigned, struct value_data *); 1019132718Skanstatic void kill_value (rtx, struct value_data *); 1020132718Skanstatic void set_value_regno (unsigned, enum machine_mode, struct value_data *); 1021132718Skanstatic void init_value_data (struct value_data *); 1022132718Skanstatic void kill_clobbered_value (rtx, rtx, void *); 1023132718Skanstatic void kill_set_value (rtx, rtx, void *); 1024132718Skanstatic int kill_autoinc_value (rtx *, void *); 1025132718Skanstatic void copy_value (rtx, rtx, struct value_data *); 1026132718Skanstatic bool mode_change_ok (enum machine_mode, enum machine_mode, 1027132718Skan unsigned int); 1028132718Skanstatic rtx maybe_mode_change (enum machine_mode, enum machine_mode, 1029132718Skan enum machine_mode, unsigned int, unsigned int); 1030132718Skanstatic rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *); 1031132718Skanstatic bool replace_oldest_value_reg (rtx *, enum reg_class, rtx, 1032132718Skan struct value_data *); 1033132718Skanstatic bool replace_oldest_value_addr (rtx *, enum reg_class, 1034132718Skan enum machine_mode, rtx, 1035132718Skan struct value_data *); 1036132718Skanstatic bool replace_oldest_value_mem (rtx, rtx, struct value_data *); 1037132718Skanstatic bool copyprop_hardreg_forward_1 (basic_block, struct value_data *); 1038132718Skanextern void debug_value_data (struct value_data *); 103990075Sobrien#ifdef ENABLE_CHECKING 1040132718Skanstatic void validate_value_data (struct value_data *); 104190075Sobrien#endif 104290075Sobrien 104390075Sobrien/* Kill register REGNO. This involves removing it from any value lists, 104490075Sobrien and resetting the value mode to VOIDmode. */ 104590075Sobrien 104690075Sobrienstatic void 1047132718Skankill_value_regno (unsigned int regno, struct value_data *vd) 104890075Sobrien{ 104990075Sobrien unsigned int i, next; 105090075Sobrien 105190075Sobrien if (vd->e[regno].oldest_regno != regno) 105290075Sobrien { 105390075Sobrien for (i = vd->e[regno].oldest_regno; 105490075Sobrien vd->e[i].next_regno != regno; 105590075Sobrien i = vd->e[i].next_regno) 105690075Sobrien continue; 105790075Sobrien vd->e[i].next_regno = vd->e[regno].next_regno; 105890075Sobrien } 105990075Sobrien else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM) 106090075Sobrien { 106190075Sobrien for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno) 1062117395Skan vd->e[i].oldest_regno = next; 106390075Sobrien } 106490075Sobrien 106590075Sobrien vd->e[regno].mode = VOIDmode; 106690075Sobrien vd->e[regno].oldest_regno = regno; 106790075Sobrien vd->e[regno].next_regno = INVALID_REGNUM; 106890075Sobrien 106990075Sobrien#ifdef ENABLE_CHECKING 107090075Sobrien validate_value_data (vd); 107190075Sobrien#endif 107290075Sobrien} 107390075Sobrien 107490075Sobrien/* Kill X. This is a convenience function for kill_value_regno 107590075Sobrien so that we mind the mode the register is in. */ 107690075Sobrien 107790075Sobrienstatic void 1078132718Skankill_value (rtx x, struct value_data *vd) 107990075Sobrien{ 108096263Sobrien /* SUBREGS are supposed to have been eliminated by now. But some 108196263Sobrien ports, e.g. i386 sse, use them to smuggle vector type information 108296263Sobrien through to instruction selection. Each such SUBREG should simplify, 1083117395Skan so if we get a NULL we've done something wrong elsewhere. */ 108496263Sobrien 108596263Sobrien if (GET_CODE (x) == SUBREG) 108696263Sobrien x = simplify_subreg (GET_MODE (x), SUBREG_REG (x), 108796263Sobrien GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x)); 108890075Sobrien if (REG_P (x)) 108990075Sobrien { 109090075Sobrien unsigned int regno = REGNO (x); 109190075Sobrien unsigned int n = HARD_REGNO_NREGS (regno, GET_MODE (x)); 109290075Sobrien unsigned int i, j; 109390075Sobrien 109490075Sobrien /* Kill the value we're told to kill. */ 109590075Sobrien for (i = 0; i < n; ++i) 109690075Sobrien kill_value_regno (regno + i, vd); 109790075Sobrien 109890075Sobrien /* Kill everything that overlapped what we're told to kill. */ 109990075Sobrien if (regno < vd->max_value_regs) 110090075Sobrien j = 0; 110190075Sobrien else 110290075Sobrien j = regno - vd->max_value_regs; 110390075Sobrien for (; j < regno; ++j) 110490075Sobrien { 110590075Sobrien if (vd->e[j].mode == VOIDmode) 110690075Sobrien continue; 110790075Sobrien n = HARD_REGNO_NREGS (j, vd->e[j].mode); 110890075Sobrien if (j + n > regno) 110990075Sobrien for (i = 0; i < n; ++i) 111090075Sobrien kill_value_regno (j + i, vd); 111190075Sobrien } 111290075Sobrien } 111390075Sobrien} 111490075Sobrien 111590075Sobrien/* Remember that REGNO is valid in MODE. */ 111690075Sobrien 111790075Sobrienstatic void 1118132718Skanset_value_regno (unsigned int regno, enum machine_mode mode, 1119132718Skan struct value_data *vd) 112090075Sobrien{ 112190075Sobrien unsigned int nregs; 112290075Sobrien 112390075Sobrien vd->e[regno].mode = mode; 112490075Sobrien 112590075Sobrien nregs = HARD_REGNO_NREGS (regno, mode); 112690075Sobrien if (nregs > vd->max_value_regs) 112790075Sobrien vd->max_value_regs = nregs; 112890075Sobrien} 112990075Sobrien 113090075Sobrien/* Initialize VD such that there are no known relationships between regs. */ 113190075Sobrien 113290075Sobrienstatic void 1133132718Skaninit_value_data (struct value_data *vd) 113490075Sobrien{ 113590075Sobrien int i; 113690075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 113790075Sobrien { 113890075Sobrien vd->e[i].mode = VOIDmode; 113990075Sobrien vd->e[i].oldest_regno = i; 114090075Sobrien vd->e[i].next_regno = INVALID_REGNUM; 114190075Sobrien } 114290075Sobrien vd->max_value_regs = 0; 114390075Sobrien} 114490075Sobrien 114590075Sobrien/* Called through note_stores. If X is clobbered, kill its value. */ 114690075Sobrien 114790075Sobrienstatic void 1148132718Skankill_clobbered_value (rtx x, rtx set, void *data) 114990075Sobrien{ 115090075Sobrien struct value_data *vd = data; 115190075Sobrien if (GET_CODE (set) == CLOBBER) 115290075Sobrien kill_value (x, vd); 115390075Sobrien} 115490075Sobrien 1155117395Skan/* Called through note_stores. If X is set, not clobbered, kill its 115690075Sobrien current value and install it as the root of its own value list. */ 115790075Sobrien 115890075Sobrienstatic void 1159132718Skankill_set_value (rtx x, rtx set, void *data) 116090075Sobrien{ 116190075Sobrien struct value_data *vd = data; 116296263Sobrien if (GET_CODE (set) != CLOBBER) 116390075Sobrien { 116490075Sobrien kill_value (x, vd); 116596263Sobrien if (REG_P (x)) 1166117395Skan set_value_regno (REGNO (x), GET_MODE (x), vd); 116790075Sobrien } 116890075Sobrien} 116990075Sobrien 117090075Sobrien/* Called through for_each_rtx. Kill any register used as the base of an 117190075Sobrien auto-increment expression, and install that register as the root of its 117290075Sobrien own value list. */ 117390075Sobrien 117490075Sobrienstatic int 1175132718Skankill_autoinc_value (rtx *px, void *data) 117690075Sobrien{ 117790075Sobrien rtx x = *px; 117890075Sobrien struct value_data *vd = data; 117990075Sobrien 118090075Sobrien if (GET_RTX_CLASS (GET_CODE (x)) == 'a') 118190075Sobrien { 118290075Sobrien x = XEXP (x, 0); 118390075Sobrien kill_value (x, vd); 118490075Sobrien set_value_regno (REGNO (x), Pmode, vd); 118590075Sobrien return -1; 118690075Sobrien } 118790075Sobrien 118890075Sobrien return 0; 118990075Sobrien} 119090075Sobrien 119190075Sobrien/* Assert that SRC has been copied to DEST. Adjust the data structures 119290075Sobrien to reflect that SRC contains an older copy of the shared value. */ 119390075Sobrien 119490075Sobrienstatic void 1195132718Skancopy_value (rtx dest, rtx src, struct value_data *vd) 119690075Sobrien{ 119790075Sobrien unsigned int dr = REGNO (dest); 119890075Sobrien unsigned int sr = REGNO (src); 119990075Sobrien unsigned int dn, sn; 120090075Sobrien unsigned int i; 120190075Sobrien 120290075Sobrien /* ??? At present, it's possible to see noop sets. It'd be nice if 120390075Sobrien this were cleaned up beforehand... */ 120490075Sobrien if (sr == dr) 120590075Sobrien return; 120690075Sobrien 120790075Sobrien /* Do not propagate copies to the stack pointer, as that can leave 1208117395Skan memory accesses with no scheduling dependency on the stack update. */ 120990075Sobrien if (dr == STACK_POINTER_REGNUM) 121090075Sobrien return; 121190075Sobrien 121290075Sobrien /* Likewise with the frame pointer, if we're using one. */ 121390075Sobrien if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM) 121490075Sobrien return; 121590075Sobrien 121690075Sobrien /* If SRC and DEST overlap, don't record anything. */ 121790075Sobrien dn = HARD_REGNO_NREGS (dr, GET_MODE (dest)); 121890075Sobrien sn = HARD_REGNO_NREGS (sr, GET_MODE (dest)); 121990075Sobrien if ((dr > sr && dr < sr + sn) 122090075Sobrien || (sr > dr && sr < dr + dn)) 122190075Sobrien return; 122290075Sobrien 122390075Sobrien /* If SRC had no assigned mode (i.e. we didn't know it was live) 122490075Sobrien assign it now and assume the value came from an input argument 122590075Sobrien or somesuch. */ 122690075Sobrien if (vd->e[sr].mode == VOIDmode) 122790075Sobrien set_value_regno (sr, vd->e[dr].mode, vd); 122890075Sobrien 1229117395Skan /* If we are narrowing the input to a smaller number of hard regs, 1230117395Skan and it is in big endian, we are really extracting a high part. 1231117395Skan Since we generally associate a low part of a value with the value itself, 1232117395Skan we must not do the same for the high part. 1233117395Skan Note we can still get low parts for the same mode combination through 1234117395Skan a two-step copy involving differently sized hard regs. 1235117395Skan Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each: 1236117395Skan (set (reg:DI r0) (reg:DI fr0)) 1237117395Skan (set (reg:SI fr2) (reg:SI r0)) 1238117395Skan loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while: 1239117395Skan (set (reg:SI fr2) (reg:SI fr0)) 1240117395Skan loads the high part of (reg:DI fr0) into fr2. 1241117395Skan 1242117395Skan We can't properly represent the latter case in our tables, so don't 1243117395Skan record anything then. */ 1244117395Skan else if (sn < (unsigned int) HARD_REGNO_NREGS (sr, vd->e[sr].mode) 1245117395Skan && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD 1246117395Skan ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN)) 1247117395Skan return; 1248117395Skan 124990075Sobrien /* If SRC had been assigned a mode narrower than the copy, we can't 125090075Sobrien link DEST into the chain, because not all of the pieces of the 125190075Sobrien copy came from oldest_regno. */ 125290075Sobrien else if (sn > (unsigned int) HARD_REGNO_NREGS (sr, vd->e[sr].mode)) 125390075Sobrien return; 125490075Sobrien 125590075Sobrien /* Link DR at the end of the value chain used by SR. */ 125690075Sobrien 125790075Sobrien vd->e[dr].oldest_regno = vd->e[sr].oldest_regno; 125890075Sobrien 125990075Sobrien for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno) 126090075Sobrien continue; 126190075Sobrien vd->e[i].next_regno = dr; 126290075Sobrien 126390075Sobrien#ifdef ENABLE_CHECKING 126490075Sobrien validate_value_data (vd); 126590075Sobrien#endif 126690075Sobrien} 126790075Sobrien 126890075Sobrien/* Return true if a mode change from ORIG to NEW is allowed for REGNO. */ 126990075Sobrien 127090075Sobrienstatic bool 1271132718Skanmode_change_ok (enum machine_mode orig_mode, enum machine_mode new_mode, 1272132718Skan unsigned int regno ATTRIBUTE_UNUSED) 127390075Sobrien{ 127490075Sobrien if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode)) 127590075Sobrien return false; 127690075Sobrien 1277117395Skan#ifdef CANNOT_CHANGE_MODE_CLASS 1278117395Skan return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode); 127990075Sobrien#endif 128090075Sobrien 128190075Sobrien return true; 128290075Sobrien} 128390075Sobrien 1284117395Skan/* Register REGNO was originally set in ORIG_MODE. It - or a copy of it - 1285117395Skan was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed 1286117395Skan in NEW_MODE. 1287117395Skan Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */ 1288117395Skan 1289117395Skanstatic rtx 1290132718Skanmaybe_mode_change (enum machine_mode orig_mode, enum machine_mode copy_mode, 1291132718Skan enum machine_mode new_mode, unsigned int regno, 1292132718Skan unsigned int copy_regno ATTRIBUTE_UNUSED) 1293117395Skan{ 1294117395Skan if (orig_mode == new_mode) 1295117395Skan return gen_rtx_raw_REG (new_mode, regno); 1296117395Skan else if (mode_change_ok (orig_mode, new_mode, regno)) 1297117395Skan { 1298117395Skan int copy_nregs = HARD_REGNO_NREGS (copy_regno, copy_mode); 1299117395Skan int use_nregs = HARD_REGNO_NREGS (copy_regno, new_mode); 1300117395Skan int copy_offset 1301117395Skan = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs); 1302117395Skan int offset 1303117395Skan = GET_MODE_SIZE (orig_mode) - GET_MODE_SIZE (new_mode) - copy_offset; 1304117395Skan int byteoffset = offset % UNITS_PER_WORD; 1305117395Skan int wordoffset = offset - byteoffset; 1306117395Skan 1307117395Skan offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0) 1308117395Skan + (BYTES_BIG_ENDIAN ? byteoffset : 0)); 1309117395Skan return gen_rtx_raw_REG (new_mode, 1310117395Skan regno + subreg_regno_offset (regno, orig_mode, 1311117395Skan offset, 1312117395Skan new_mode)); 1313117395Skan } 1314117395Skan return NULL_RTX; 1315117395Skan} 1316117395Skan 131790075Sobrien/* Find the oldest copy of the value contained in REGNO that is in 131890075Sobrien register class CLASS and has mode MODE. If found, return an rtx 131990075Sobrien of that oldest register, otherwise return NULL. */ 132090075Sobrien 132190075Sobrienstatic rtx 1322132718Skanfind_oldest_value_reg (enum reg_class class, rtx reg, struct value_data *vd) 132390075Sobrien{ 132490075Sobrien unsigned int regno = REGNO (reg); 132590075Sobrien enum machine_mode mode = GET_MODE (reg); 132690075Sobrien unsigned int i; 132790075Sobrien 132890075Sobrien /* If we are accessing REG in some mode other that what we set it in, 132990075Sobrien make sure that the replacement is valid. In particular, consider 133090075Sobrien (set (reg:DI r11) (...)) 133190075Sobrien (set (reg:SI r9) (reg:SI r11)) 133290075Sobrien (set (reg:SI r10) (...)) 133390075Sobrien (set (...) (reg:DI r9)) 133490075Sobrien Replacing r9 with r11 is invalid. */ 133590075Sobrien if (mode != vd->e[regno].mode) 133690075Sobrien { 133790075Sobrien if (HARD_REGNO_NREGS (regno, mode) 133890075Sobrien > HARD_REGNO_NREGS (regno, vd->e[regno].mode)) 133990075Sobrien return NULL_RTX; 134090075Sobrien } 134190075Sobrien 134290075Sobrien for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno) 1343117395Skan { 1344117395Skan enum machine_mode oldmode = vd->e[i].mode; 1345117395Skan rtx new; 1346132718Skan unsigned int last; 1347117395Skan 1348132718Skan for (last = i; last < i + HARD_REGNO_NREGS (i, mode); last++) 1349132718Skan if (!TEST_HARD_REG_BIT (reg_class_contents[class], last)) 1350132718Skan return NULL_RTX; 1351132718Skan 1352132718Skan new = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno); 1353132718Skan if (new) 1354132718Skan { 1355132718Skan ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg); 1356132718Skan REG_ATTRS (new) = REG_ATTRS (reg); 1357132718Skan return new; 1358132718Skan } 1359117395Skan } 136090075Sobrien 136190075Sobrien return NULL_RTX; 136290075Sobrien} 136390075Sobrien 136490075Sobrien/* If possible, replace the register at *LOC with the oldest register 136590075Sobrien in register class CLASS. Return true if successfully replaced. */ 136690075Sobrien 136790075Sobrienstatic bool 1368132718Skanreplace_oldest_value_reg (rtx *loc, enum reg_class class, rtx insn, 1369132718Skan struct value_data *vd) 137090075Sobrien{ 137190075Sobrien rtx new = find_oldest_value_reg (class, *loc, vd); 137290075Sobrien if (new) 137390075Sobrien { 137490075Sobrien if (rtl_dump_file) 137590075Sobrien fprintf (rtl_dump_file, "insn %u: replaced reg %u with %u\n", 137690075Sobrien INSN_UID (insn), REGNO (*loc), REGNO (new)); 137790075Sobrien 137890075Sobrien *loc = new; 137990075Sobrien return true; 138090075Sobrien } 138190075Sobrien return false; 138290075Sobrien} 138390075Sobrien 138490075Sobrien/* Similar to replace_oldest_value_reg, but *LOC contains an address. 138590075Sobrien Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or 138690075Sobrien BASE_REG_CLASS depending on how the register is being considered. */ 138790075Sobrien 138890075Sobrienstatic bool 1389132718Skanreplace_oldest_value_addr (rtx *loc, enum reg_class class, 1390132718Skan enum machine_mode mode, rtx insn, 1391132718Skan struct value_data *vd) 139290075Sobrien{ 139390075Sobrien rtx x = *loc; 139490075Sobrien RTX_CODE code = GET_CODE (x); 139590075Sobrien const char *fmt; 139690075Sobrien int i, j; 139790075Sobrien bool changed = false; 139890075Sobrien 139990075Sobrien switch (code) 140090075Sobrien { 140190075Sobrien case PLUS: 140290075Sobrien { 140390075Sobrien rtx orig_op0 = XEXP (x, 0); 140490075Sobrien rtx orig_op1 = XEXP (x, 1); 140590075Sobrien RTX_CODE code0 = GET_CODE (orig_op0); 140690075Sobrien RTX_CODE code1 = GET_CODE (orig_op1); 140790075Sobrien rtx op0 = orig_op0; 140890075Sobrien rtx op1 = orig_op1; 140990075Sobrien rtx *locI = NULL; 141090075Sobrien rtx *locB = NULL; 141190075Sobrien 141290075Sobrien if (GET_CODE (op0) == SUBREG) 141390075Sobrien { 141490075Sobrien op0 = SUBREG_REG (op0); 141590075Sobrien code0 = GET_CODE (op0); 141690075Sobrien } 141790075Sobrien 141890075Sobrien if (GET_CODE (op1) == SUBREG) 141990075Sobrien { 142090075Sobrien op1 = SUBREG_REG (op1); 142190075Sobrien code1 = GET_CODE (op1); 142290075Sobrien } 142390075Sobrien 142490075Sobrien if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE 142590075Sobrien || code0 == ZERO_EXTEND || code1 == MEM) 142690075Sobrien { 142790075Sobrien locI = &XEXP (x, 0); 142890075Sobrien locB = &XEXP (x, 1); 142990075Sobrien } 143090075Sobrien else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE 143190075Sobrien || code1 == ZERO_EXTEND || code0 == MEM) 143290075Sobrien { 143390075Sobrien locI = &XEXP (x, 1); 143490075Sobrien locB = &XEXP (x, 0); 143590075Sobrien } 143690075Sobrien else if (code0 == CONST_INT || code0 == CONST 143790075Sobrien || code0 == SYMBOL_REF || code0 == LABEL_REF) 143890075Sobrien locB = &XEXP (x, 1); 143990075Sobrien else if (code1 == CONST_INT || code1 == CONST 144090075Sobrien || code1 == SYMBOL_REF || code1 == LABEL_REF) 144190075Sobrien locB = &XEXP (x, 0); 144290075Sobrien else if (code0 == REG && code1 == REG) 144390075Sobrien { 144490075Sobrien int index_op; 144590075Sobrien 144690075Sobrien if (REG_OK_FOR_INDEX_P (op0) 144790075Sobrien && REG_MODE_OK_FOR_BASE_P (op1, mode)) 144890075Sobrien index_op = 0; 144990075Sobrien else if (REG_OK_FOR_INDEX_P (op1) 145090075Sobrien && REG_MODE_OK_FOR_BASE_P (op0, mode)) 145190075Sobrien index_op = 1; 145290075Sobrien else if (REG_MODE_OK_FOR_BASE_P (op1, mode)) 145390075Sobrien index_op = 0; 145490075Sobrien else if (REG_MODE_OK_FOR_BASE_P (op0, mode)) 145590075Sobrien index_op = 1; 145690075Sobrien else if (REG_OK_FOR_INDEX_P (op1)) 145790075Sobrien index_op = 1; 145890075Sobrien else 145990075Sobrien index_op = 0; 146090075Sobrien 146190075Sobrien locI = &XEXP (x, index_op); 146290075Sobrien locB = &XEXP (x, !index_op); 146390075Sobrien } 146490075Sobrien else if (code0 == REG) 146590075Sobrien { 146690075Sobrien locI = &XEXP (x, 0); 146790075Sobrien locB = &XEXP (x, 1); 146890075Sobrien } 146990075Sobrien else if (code1 == REG) 147090075Sobrien { 147190075Sobrien locI = &XEXP (x, 1); 147290075Sobrien locB = &XEXP (x, 0); 147390075Sobrien } 147490075Sobrien 147590075Sobrien if (locI) 147690075Sobrien changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode, 1477117395Skan insn, vd); 147890075Sobrien if (locB) 147990075Sobrien changed |= replace_oldest_value_addr (locB, 148090075Sobrien MODE_BASE_REG_CLASS (mode), 148190075Sobrien mode, insn, vd); 148290075Sobrien return changed; 148390075Sobrien } 148490075Sobrien 148590075Sobrien case POST_INC: 148690075Sobrien case POST_DEC: 148790075Sobrien case POST_MODIFY: 148890075Sobrien case PRE_INC: 148990075Sobrien case PRE_DEC: 149090075Sobrien case PRE_MODIFY: 149190075Sobrien return false; 149290075Sobrien 149390075Sobrien case MEM: 149490075Sobrien return replace_oldest_value_mem (x, insn, vd); 149590075Sobrien 149690075Sobrien case REG: 149790075Sobrien return replace_oldest_value_reg (loc, class, insn, vd); 149890075Sobrien 149990075Sobrien default: 150090075Sobrien break; 150190075Sobrien } 150290075Sobrien 150390075Sobrien fmt = GET_RTX_FORMAT (code); 150490075Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 150590075Sobrien { 150690075Sobrien if (fmt[i] == 'e') 150790075Sobrien changed |= replace_oldest_value_addr (&XEXP (x, i), class, mode, 150890075Sobrien insn, vd); 150990075Sobrien else if (fmt[i] == 'E') 151090075Sobrien for (j = XVECLEN (x, i) - 1; j >= 0; j--) 151190075Sobrien changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), class, 1512117395Skan mode, insn, vd); 151390075Sobrien } 151490075Sobrien 151590075Sobrien return changed; 151690075Sobrien} 151790075Sobrien 151890075Sobrien/* Similar to replace_oldest_value_reg, but X contains a memory. */ 151990075Sobrien 152090075Sobrienstatic bool 1521132718Skanreplace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd) 152290075Sobrien{ 152390075Sobrien return replace_oldest_value_addr (&XEXP (x, 0), 152490075Sobrien MODE_BASE_REG_CLASS (GET_MODE (x)), 152590075Sobrien GET_MODE (x), insn, vd); 152690075Sobrien} 152790075Sobrien 152890075Sobrien/* Perform the forward copy propagation on basic block BB. */ 152990075Sobrien 153090075Sobrienstatic bool 1531132718Skancopyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd) 153290075Sobrien{ 153390075Sobrien bool changed = false; 153490075Sobrien rtx insn; 153590075Sobrien 1536132718Skan for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 153790075Sobrien { 153890075Sobrien int n_ops, i, alt, predicated; 153990075Sobrien bool is_asm; 154090075Sobrien rtx set; 154190075Sobrien 154290075Sobrien if (! INSN_P (insn)) 154390075Sobrien { 1544132718Skan if (insn == BB_END (bb)) 154590075Sobrien break; 154690075Sobrien else 154790075Sobrien continue; 154890075Sobrien } 154990075Sobrien 155090075Sobrien set = single_set (insn); 155190075Sobrien extract_insn (insn); 1552117395Skan if (! constrain_operands (1)) 1553117395Skan fatal_insn_not_found (insn); 155490075Sobrien preprocess_constraints (); 155590075Sobrien alt = which_alternative; 155690075Sobrien n_ops = recog_data.n_operands; 155790075Sobrien is_asm = asm_noperands (PATTERN (insn)) >= 0; 155890075Sobrien 155990075Sobrien /* Simplify the code below by rewriting things to reflect 156090075Sobrien matching constraints. Also promote OP_OUT to OP_INOUT 156190075Sobrien in predicated instructions. */ 156290075Sobrien 156390075Sobrien predicated = GET_CODE (PATTERN (insn)) == COND_EXEC; 156490075Sobrien for (i = 0; i < n_ops; ++i) 156590075Sobrien { 156690075Sobrien int matches = recog_op_alt[i][alt].matches; 156790075Sobrien if (matches >= 0) 156890075Sobrien recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class; 156990075Sobrien if (matches >= 0 || recog_op_alt[i][alt].matched >= 0 157090075Sobrien || (predicated && recog_data.operand_type[i] == OP_OUT)) 157190075Sobrien recog_data.operand_type[i] = OP_INOUT; 157290075Sobrien } 157390075Sobrien 157490075Sobrien /* For each earlyclobber operand, zap the value data. */ 157590075Sobrien for (i = 0; i < n_ops; i++) 157690075Sobrien if (recog_op_alt[i][alt].earlyclobber) 157790075Sobrien kill_value (recog_data.operand[i], vd); 157890075Sobrien 157990075Sobrien /* Within asms, a clobber cannot overlap inputs or outputs. 158090075Sobrien I wouldn't think this were true for regular insns, but 158190075Sobrien scan_rtx treats them like that... */ 158290075Sobrien note_stores (PATTERN (insn), kill_clobbered_value, vd); 158390075Sobrien 158490075Sobrien /* Kill all auto-incremented values. */ 158590075Sobrien /* ??? REG_INC is useless, since stack pushes aren't done that way. */ 158690075Sobrien for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd); 158790075Sobrien 158890075Sobrien /* Kill all early-clobbered operands. */ 158990075Sobrien for (i = 0; i < n_ops; i++) 159090075Sobrien if (recog_op_alt[i][alt].earlyclobber) 159190075Sobrien kill_value (recog_data.operand[i], vd); 159290075Sobrien 159390075Sobrien /* Special-case plain move instructions, since we may well 159490075Sobrien be able to do the move from a different register class. */ 159590075Sobrien if (set && REG_P (SET_SRC (set))) 159690075Sobrien { 159790075Sobrien rtx src = SET_SRC (set); 159890075Sobrien unsigned int regno = REGNO (src); 159990075Sobrien enum machine_mode mode = GET_MODE (src); 160090075Sobrien unsigned int i; 160190075Sobrien rtx new; 160290075Sobrien 160390075Sobrien /* If we are accessing SRC in some mode other that what we 160490075Sobrien set it in, make sure that the replacement is valid. */ 160590075Sobrien if (mode != vd->e[regno].mode) 160690075Sobrien { 160790075Sobrien if (HARD_REGNO_NREGS (regno, mode) 160890075Sobrien > HARD_REGNO_NREGS (regno, vd->e[regno].mode)) 160990075Sobrien goto no_move_special_case; 161090075Sobrien } 161190075Sobrien 161290075Sobrien /* If the destination is also a register, try to find a source 161390075Sobrien register in the same class. */ 161490075Sobrien if (REG_P (SET_DEST (set))) 161590075Sobrien { 161690075Sobrien new = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd); 161790075Sobrien if (new && validate_change (insn, &SET_SRC (set), new, 0)) 161890075Sobrien { 161990075Sobrien if (rtl_dump_file) 162090075Sobrien fprintf (rtl_dump_file, 162190075Sobrien "insn %u: replaced reg %u with %u\n", 162290075Sobrien INSN_UID (insn), regno, REGNO (new)); 1623117395Skan changed = true; 162490075Sobrien goto did_replacement; 162590075Sobrien } 162690075Sobrien } 162790075Sobrien 162890075Sobrien /* Otherwise, try all valid registers and see if its valid. */ 162990075Sobrien for (i = vd->e[regno].oldest_regno; i != regno; 163090075Sobrien i = vd->e[i].next_regno) 1631117395Skan { 1632117395Skan new = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode, 1633117395Skan mode, i, regno); 1634117395Skan if (new != NULL_RTX) 1635117395Skan { 1636117395Skan if (validate_change (insn, &SET_SRC (set), new, 0)) 1637117395Skan { 1638117395Skan ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src); 1639132718Skan REG_ATTRS (new) = REG_ATTRS (src); 1640117395Skan if (rtl_dump_file) 1641117395Skan fprintf (rtl_dump_file, 1642117395Skan "insn %u: replaced reg %u with %u\n", 1643117395Skan INSN_UID (insn), regno, REGNO (new)); 1644117395Skan changed = true; 1645117395Skan goto did_replacement; 1646117395Skan } 1647117395Skan } 1648117395Skan } 164990075Sobrien } 165090075Sobrien no_move_special_case: 165190075Sobrien 165290075Sobrien /* For each input operand, replace a hard register with the 165390075Sobrien eldest live copy that's in an appropriate register class. */ 165490075Sobrien for (i = 0; i < n_ops; i++) 165590075Sobrien { 165690075Sobrien bool replaced = false; 165790075Sobrien 165890075Sobrien /* Don't scan match_operand here, since we've no reg class 165990075Sobrien information to pass down. Any operands that we could 166090075Sobrien substitute in will be represented elsewhere. */ 166190075Sobrien if (recog_data.constraints[i][0] == '\0') 166290075Sobrien continue; 166390075Sobrien 166490075Sobrien /* Don't replace in asms intentionally referencing hard regs. */ 166590075Sobrien if (is_asm && GET_CODE (recog_data.operand[i]) == REG 166690075Sobrien && (REGNO (recog_data.operand[i]) 166790075Sobrien == ORIGINAL_REGNO (recog_data.operand[i]))) 166890075Sobrien continue; 166990075Sobrien 167090075Sobrien if (recog_data.operand_type[i] == OP_IN) 167190075Sobrien { 167290075Sobrien if (recog_op_alt[i][alt].is_address) 167390075Sobrien replaced 167490075Sobrien = replace_oldest_value_addr (recog_data.operand_loc[i], 167590075Sobrien recog_op_alt[i][alt].class, 167690075Sobrien VOIDmode, insn, vd); 167790075Sobrien else if (REG_P (recog_data.operand[i])) 167890075Sobrien replaced 167990075Sobrien = replace_oldest_value_reg (recog_data.operand_loc[i], 168090075Sobrien recog_op_alt[i][alt].class, 168190075Sobrien insn, vd); 168290075Sobrien else if (GET_CODE (recog_data.operand[i]) == MEM) 168390075Sobrien replaced = replace_oldest_value_mem (recog_data.operand[i], 168490075Sobrien insn, vd); 168590075Sobrien } 168690075Sobrien else if (GET_CODE (recog_data.operand[i]) == MEM) 168790075Sobrien replaced = replace_oldest_value_mem (recog_data.operand[i], 1688117395Skan insn, vd); 168990075Sobrien 169090075Sobrien /* If we performed any replacement, update match_dups. */ 169190075Sobrien if (replaced) 169290075Sobrien { 169390075Sobrien int j; 169490075Sobrien rtx new; 169590075Sobrien 169690075Sobrien changed = true; 169790075Sobrien 169890075Sobrien new = *recog_data.operand_loc[i]; 169990075Sobrien recog_data.operand[i] = new; 170090075Sobrien for (j = 0; j < recog_data.n_dups; j++) 170190075Sobrien if (recog_data.dup_num[j] == i) 170290075Sobrien *recog_data.dup_loc[j] = new; 170390075Sobrien } 170490075Sobrien } 170590075Sobrien 170690075Sobrien did_replacement: 170790075Sobrien /* Clobber call-clobbered registers. */ 170890075Sobrien if (GET_CODE (insn) == CALL_INSN) 170990075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 171090075Sobrien if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 171190075Sobrien kill_value_regno (i, vd); 171290075Sobrien 171390075Sobrien /* Notice stores. */ 171490075Sobrien note_stores (PATTERN (insn), kill_set_value, vd); 171590075Sobrien 171690075Sobrien /* Notice copies. */ 171790075Sobrien if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))) 171890075Sobrien copy_value (SET_DEST (set), SET_SRC (set), vd); 171990075Sobrien 1720132718Skan if (insn == BB_END (bb)) 172190075Sobrien break; 172290075Sobrien } 172390075Sobrien 172490075Sobrien return changed; 172590075Sobrien} 172690075Sobrien 172790075Sobrien/* Main entry point for the forward copy propagation optimization. */ 172890075Sobrien 172990075Sobrienvoid 1730132718Skancopyprop_hardreg_forward (void) 173190075Sobrien{ 173290075Sobrien struct value_data *all_vd; 173390075Sobrien bool need_refresh; 1734117395Skan basic_block bb, bbp = 0; 173590075Sobrien 173690075Sobrien need_refresh = false; 173790075Sobrien 1738117395Skan all_vd = xmalloc (sizeof (struct value_data) * last_basic_block); 173990075Sobrien 1740117395Skan FOR_EACH_BB (bb) 174190075Sobrien { 174290075Sobrien /* If a block has a single predecessor, that we've already 174390075Sobrien processed, begin with the value data that was live at 174490075Sobrien the end of the predecessor block. */ 1745132718Skan /* ??? Ought to use more intelligent queuing of blocks. */ 1746117395Skan if (bb->pred) 1747117395Skan for (bbp = bb; bbp && bbp != bb->pred->src; bbp = bbp->prev_bb); 174890075Sobrien if (bb->pred 1749117395Skan && ! bb->pred->pred_next 175090075Sobrien && ! (bb->pred->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) 1751117395Skan && bb->pred->src != ENTRY_BLOCK_PTR 1752117395Skan && bbp) 1753117395Skan all_vd[bb->index] = all_vd[bb->pred->src->index]; 175490075Sobrien else 1755117395Skan init_value_data (all_vd + bb->index); 175690075Sobrien 1757117395Skan if (copyprop_hardreg_forward_1 (bb, all_vd + bb->index)) 175890075Sobrien need_refresh = true; 175990075Sobrien } 176090075Sobrien 176190075Sobrien if (need_refresh) 176290075Sobrien { 176390075Sobrien if (rtl_dump_file) 176490075Sobrien fputs ("\n\n", rtl_dump_file); 176590075Sobrien 176690075Sobrien /* ??? Irritatingly, delete_noop_moves does not take a set of blocks 176790075Sobrien to scan, so we have to do a life update with no initial set of 176890075Sobrien blocks Just In Case. */ 176990075Sobrien delete_noop_moves (get_insns ()); 177090075Sobrien update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES, 177190075Sobrien PROP_DEATH_NOTES 177290075Sobrien | PROP_SCAN_DEAD_CODE 177390075Sobrien | PROP_KILL_DEAD_CODE); 177490075Sobrien } 177590075Sobrien 177690075Sobrien free (all_vd); 177790075Sobrien} 177890075Sobrien 177990075Sobrien/* Dump the value chain data to stderr. */ 178090075Sobrien 178190075Sobrienvoid 1782132718Skandebug_value_data (struct value_data *vd) 178390075Sobrien{ 178490075Sobrien HARD_REG_SET set; 178590075Sobrien unsigned int i, j; 178690075Sobrien 178790075Sobrien CLEAR_HARD_REG_SET (set); 178890075Sobrien 178990075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 179090075Sobrien if (vd->e[i].oldest_regno == i) 179190075Sobrien { 179290075Sobrien if (vd->e[i].mode == VOIDmode) 179390075Sobrien { 179490075Sobrien if (vd->e[i].next_regno != INVALID_REGNUM) 179590075Sobrien fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n", 179690075Sobrien i, vd->e[i].next_regno); 179790075Sobrien continue; 179890075Sobrien } 179990075Sobrien 180090075Sobrien SET_HARD_REG_BIT (set, i); 180190075Sobrien fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode)); 180290075Sobrien 180390075Sobrien for (j = vd->e[i].next_regno; 180490075Sobrien j != INVALID_REGNUM; 180590075Sobrien j = vd->e[j].next_regno) 180690075Sobrien { 180790075Sobrien if (TEST_HARD_REG_BIT (set, j)) 180890075Sobrien { 180990075Sobrien fprintf (stderr, "[%u] Loop in regno chain\n", j); 181090075Sobrien return; 181190075Sobrien } 181290075Sobrien 181390075Sobrien if (vd->e[j].oldest_regno != i) 181490075Sobrien { 181590075Sobrien fprintf (stderr, "[%u] Bad oldest_regno (%u)\n", 181690075Sobrien j, vd->e[j].oldest_regno); 181790075Sobrien return; 181890075Sobrien } 181990075Sobrien SET_HARD_REG_BIT (set, j); 182090075Sobrien fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode)); 182190075Sobrien } 182290075Sobrien fputc ('\n', stderr); 182390075Sobrien } 182490075Sobrien 182590075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 182690075Sobrien if (! TEST_HARD_REG_BIT (set, i) 182790075Sobrien && (vd->e[i].mode != VOIDmode 182890075Sobrien || vd->e[i].oldest_regno != i 182990075Sobrien || vd->e[i].next_regno != INVALID_REGNUM)) 183090075Sobrien fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n", 183190075Sobrien i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno, 183290075Sobrien vd->e[i].next_regno); 183390075Sobrien} 183490075Sobrien 183590075Sobrien#ifdef ENABLE_CHECKING 183690075Sobrienstatic void 1837132718Skanvalidate_value_data (struct value_data *vd) 183890075Sobrien{ 183990075Sobrien HARD_REG_SET set; 184090075Sobrien unsigned int i, j; 184190075Sobrien 184290075Sobrien CLEAR_HARD_REG_SET (set); 184390075Sobrien 184490075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 184590075Sobrien if (vd->e[i].oldest_regno == i) 184690075Sobrien { 184790075Sobrien if (vd->e[i].mode == VOIDmode) 184890075Sobrien { 184990075Sobrien if (vd->e[i].next_regno != INVALID_REGNUM) 185090075Sobrien internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)", 185190075Sobrien i, vd->e[i].next_regno); 185290075Sobrien continue; 185390075Sobrien } 185490075Sobrien 185590075Sobrien SET_HARD_REG_BIT (set, i); 185690075Sobrien 185790075Sobrien for (j = vd->e[i].next_regno; 185890075Sobrien j != INVALID_REGNUM; 185990075Sobrien j = vd->e[j].next_regno) 186090075Sobrien { 186190075Sobrien if (TEST_HARD_REG_BIT (set, j)) 186290075Sobrien internal_error ("validate_value_data: Loop in regno chain (%u)", 186390075Sobrien j); 186490075Sobrien if (vd->e[j].oldest_regno != i) 186590075Sobrien internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)", 186690075Sobrien j, vd->e[j].oldest_regno); 186790075Sobrien 186890075Sobrien SET_HARD_REG_BIT (set, j); 186990075Sobrien } 187090075Sobrien } 187190075Sobrien 187290075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 187390075Sobrien if (! TEST_HARD_REG_BIT (set, i) 187490075Sobrien && (vd->e[i].mode != VOIDmode 187590075Sobrien || vd->e[i].oldest_regno != i 187690075Sobrien || vd->e[i].next_regno != INVALID_REGNUM)) 187790075Sobrien internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)", 187890075Sobrien i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno, 187990075Sobrien vd->e[i].next_regno); 188090075Sobrien} 188190075Sobrien#endif 1882