1169689Skan/* Control flow optimization code for GNU compiler. 2169689Skan Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3169689Skan 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21169689Skan 22169689Skan/* Try to match two basic blocks - or their ends - for structural equivalence. 23169689Skan We scan the blocks from their ends backwards, and expect that insns are 24169689Skan identical, except for certain cases involving registers. A mismatch 25169689Skan We scan the blocks from their ends backwards, hoping to find a match, I.e. 26169689Skan insns are identical, except for certain cases involving registers. A 27169689Skan mismatch between register number RX (used in block X) and RY (used in the 28169689Skan same way in block Y) can be handled in one of the following cases: 29169689Skan 1. RX and RY are local to their respective blocks; they are set there and 30169689Skan die there. If so, they can effectively be ignored. 31169689Skan 2. RX and RY die in their blocks, but live at the start. If any path 32169689Skan gets redirected through X instead of Y, the caller must emit 33169689Skan compensation code to move RY to RX. If there are overlapping inputs, 34169689Skan the function resolve_input_conflict ensures that this can be done. 35169689Skan Information about these registers are tracked in the X_LOCAL, Y_LOCAL, 36169689Skan LOCAL_COUNT and LOCAL_RVALUE fields. 37169689Skan 3. RX and RY live throughout their blocks, including the start and the end. 38169689Skan Either RX and RY must be identical, or we have to replace all uses in 39169689Skan block X with a new pseudo, which is stored in the INPUT_REG field. The 40169689Skan caller can then use block X instead of block Y by copying RY to the new 41169689Skan pseudo. 42169689Skan 43169689Skan The main entry point to this file is struct_equiv_block_eq. This function 44169689Skan uses a struct equiv_info to accept some of its inputs, to keep track of its 45169689Skan internal state, to pass down to its helper functions, and to communicate 46169689Skan some of the results back to the caller. 47169689Skan 48169689Skan Most scans will result in a failure to match a sufficient number of insns 49169689Skan to make any optimization worth while, therefore the process is geared more 50169689Skan to quick scanning rather than the ability to exactly backtrack when we 51169689Skan find a mismatch. The information gathered is still meaningful to make a 52169689Skan preliminary decision if we want to do an optimization, we might only 53169689Skan slightly overestimate the number of matchable insns, and underestimate 54169689Skan the number of inputs an miss an input conflict. Sufficient information 55169689Skan is gathered so that when we make another pass, we won't have to backtrack 56169689Skan at the same point. 57169689Skan Another issue is that information in memory attributes and/or REG_NOTES 58169689Skan might have to be merged or discarded to make a valid match. We don't want 59169689Skan to discard such information when we are not certain that we want to merge 60169689Skan the two (partial) blocks. 61169689Skan For these reasons, struct_equiv_block_eq has to be called first with the 62169689Skan STRUCT_EQUIV_START bit set in the mode parameter. This will calculate the 63169689Skan number of matched insns and the number and types of inputs. If the 64169689Skan need_rerun field is set, the results are only tentative, and the caller 65169689Skan has to call again with STRUCT_EQUIV_RERUN till need_rerun is false in 66169689Skan order to get a reliable match. 67169689Skan To install the changes necessary for the match, the function has to be 68169689Skan called again with STRUCT_EQUIV_FINAL. 69169689Skan 70169689Skan While scanning an insn, we process first all the SET_DESTs, then the 71169689Skan SET_SRCes, then the REG_NOTES, in order to keep the register liveness 72169689Skan information consistent. 73169689Skan If we were to mix up the order for sources / destinations in an insn where 74169689Skan a source is also a destination, we'd end up being mistaken to think that 75169689Skan the register is not live in the preceding insn. */ 76169689Skan 77169689Skan#include "config.h" 78169689Skan#include "system.h" 79169689Skan#include "coretypes.h" 80169689Skan#include "tm.h" 81169689Skan#include "rtl.h" 82169689Skan#include "regs.h" 83169689Skan#include "output.h" 84169689Skan#include "insn-config.h" 85169689Skan#include "flags.h" 86169689Skan#include "recog.h" 87169689Skan#include "tm_p.h" 88169689Skan#include "target.h" 89169689Skan#include "emit-rtl.h" 90169689Skan#include "reload.h" 91169689Skan 92169689Skanstatic void merge_memattrs (rtx, rtx); 93169689Skanstatic bool set_dest_equiv_p (rtx x, rtx y, struct equiv_info *info); 94169689Skanstatic bool set_dest_addr_equiv_p (rtx x, rtx y, struct equiv_info *info); 95169689Skanstatic void find_dying_inputs (struct equiv_info *info); 96169689Skanstatic bool resolve_input_conflict (struct equiv_info *info); 97169689Skan 98169689Skan/* After reload, some moves, as indicated by SECONDARY_RELOAD_CLASS and 99169689Skan SECONDARY_MEMORY_NEEDED, cannot be done directly. For our purposes, we 100169689Skan consider them impossible to generate after reload (even though some 101169689Skan might be synthesized when you throw enough code at them). 102169689Skan Since we don't know while processing a cross-jump if a local register 103169689Skan that is currently live will eventually be live and thus be an input, 104169689Skan we keep track of potential inputs that would require an impossible move 105169689Skan by using a prohibitively high cost for them. 106169689Skan This number, multiplied with the larger of STRUCT_EQUIV_MAX_LOCAL and 107169689Skan FIRST_PSEUDO_REGISTER, must fit in the input_cost field of 108169689Skan struct equiv_info. */ 109169689Skan#define IMPOSSIBLE_MOVE_FACTOR 20000 110169689Skan 111169689Skan 112169689Skan 113169689Skan/* Removes the memory attributes of MEM expression 114169689Skan if they are not equal. */ 115169689Skan 116169689Skanvoid 117169689Skanmerge_memattrs (rtx x, rtx y) 118169689Skan{ 119169689Skan int i; 120169689Skan int j; 121169689Skan enum rtx_code code; 122169689Skan const char *fmt; 123169689Skan 124169689Skan if (x == y) 125169689Skan return; 126169689Skan if (x == 0 || y == 0) 127169689Skan return; 128169689Skan 129169689Skan code = GET_CODE (x); 130169689Skan 131169689Skan if (code != GET_CODE (y)) 132169689Skan return; 133169689Skan 134169689Skan if (GET_MODE (x) != GET_MODE (y)) 135169689Skan return; 136169689Skan 137169689Skan if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y)) 138169689Skan { 139169689Skan if (! MEM_ATTRS (x)) 140169689Skan MEM_ATTRS (y) = 0; 141169689Skan else if (! MEM_ATTRS (y)) 142169689Skan MEM_ATTRS (x) = 0; 143169689Skan else 144169689Skan { 145169689Skan rtx mem_size; 146169689Skan 147169689Skan if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y)) 148169689Skan { 149169689Skan set_mem_alias_set (x, 0); 150169689Skan set_mem_alias_set (y, 0); 151169689Skan } 152169689Skan 153169689Skan if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y))) 154169689Skan { 155169689Skan set_mem_expr (x, 0); 156169689Skan set_mem_expr (y, 0); 157169689Skan set_mem_offset (x, 0); 158169689Skan set_mem_offset (y, 0); 159169689Skan } 160169689Skan else if (MEM_OFFSET (x) != MEM_OFFSET (y)) 161169689Skan { 162169689Skan set_mem_offset (x, 0); 163169689Skan set_mem_offset (y, 0); 164169689Skan } 165169689Skan 166169689Skan if (!MEM_SIZE (x)) 167169689Skan mem_size = NULL_RTX; 168169689Skan else if (!MEM_SIZE (y)) 169169689Skan mem_size = NULL_RTX; 170169689Skan else 171169689Skan mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)), 172169689Skan INTVAL (MEM_SIZE (y)))); 173169689Skan set_mem_size (x, mem_size); 174169689Skan set_mem_size (y, mem_size); 175169689Skan 176169689Skan set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y))); 177169689Skan set_mem_align (y, MEM_ALIGN (x)); 178169689Skan } 179169689Skan } 180169689Skan 181169689Skan fmt = GET_RTX_FORMAT (code); 182169689Skan for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 183169689Skan { 184169689Skan switch (fmt[i]) 185169689Skan { 186169689Skan case 'E': 187169689Skan /* Two vectors must have the same length. */ 188169689Skan if (XVECLEN (x, i) != XVECLEN (y, i)) 189169689Skan return; 190169689Skan 191169689Skan for (j = 0; j < XVECLEN (x, i); j++) 192169689Skan merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j)); 193169689Skan 194169689Skan break; 195169689Skan 196169689Skan case 'e': 197169689Skan merge_memattrs (XEXP (x, i), XEXP (y, i)); 198169689Skan } 199169689Skan } 200169689Skan return; 201169689Skan} 202169689Skan 203169689Skan/* In SET, assign the bit for the register number of REG the value VALUE. 204169689Skan If REG is a hard register, do so for all its constituent registers. 205169689Skan Return the number of registers that have become included (as a positive 206169689Skan number) or excluded (as a negative number). */ 207169689Skanstatic int 208169689Skanassign_reg_reg_set (regset set, rtx reg, int value) 209169689Skan{ 210169689Skan unsigned regno = REGNO (reg); 211169689Skan int nregs, i, old; 212169689Skan 213169689Skan if (regno >= FIRST_PSEUDO_REGISTER) 214169689Skan { 215169689Skan gcc_assert (!reload_completed); 216169689Skan nregs = 1; 217169689Skan } 218169689Skan else 219169689Skan nregs = hard_regno_nregs[regno][GET_MODE (reg)]; 220169689Skan for (old = 0, i = nregs; --i >= 0; regno++) 221169689Skan { 222169689Skan if ((value != 0) == REGNO_REG_SET_P (set, regno)) 223169689Skan continue; 224169689Skan if (value) 225169689Skan old++, SET_REGNO_REG_SET (set, regno); 226169689Skan else 227169689Skan old--, CLEAR_REGNO_REG_SET (set, regno); 228169689Skan } 229169689Skan return old; 230169689Skan} 231169689Skan 232169689Skan/* Record state about current inputs / local registers / liveness 233169689Skan in *P. */ 234169689Skanstatic inline void 235169689Skanstruct_equiv_make_checkpoint (struct struct_equiv_checkpoint *p, 236169689Skan struct equiv_info *info) 237169689Skan{ 238169689Skan *p = info->cur; 239169689Skan} 240169689Skan 241169689Skan/* Call struct_equiv_make_checkpoint (P, INFO) if the current partial block 242169689Skan is suitable to split off - i.e. there is no dangling cc0 user - and 243169689Skan if the current cost of the common instructions, minus the cost for 244169689Skan setting up the inputs, is higher than what has been recorded before 245169689Skan in CHECKPOINT[N]. Also, if we do so, confirm or cancel any pending 246169689Skan changes. */ 247169689Skanstatic void 248169689Skanstruct_equiv_improve_checkpoint (struct struct_equiv_checkpoint *p, 249169689Skan struct equiv_info *info) 250169689Skan{ 251169689Skan#ifdef HAVE_cc0 252169689Skan if (reg_mentioned_p (cc0_rtx, info->cur.x_start) 253169689Skan && !sets_cc0_p (info->cur.x_start)) 254169689Skan return; 255169689Skan#endif 256169689Skan if (info->cur.input_count >= IMPOSSIBLE_MOVE_FACTOR) 257169689Skan return; 258169689Skan if (info->input_cost >= 0 259169689Skan ? (COSTS_N_INSNS(info->cur.ninsns - p->ninsns) 260169689Skan > info->input_cost * (info->cur.input_count - p->input_count)) 261169689Skan : info->cur.ninsns > p->ninsns && !info->cur.input_count) 262169689Skan { 263169689Skan if (info->check_input_conflict && ! resolve_input_conflict (info)) 264169689Skan return; 265169689Skan /* We have a profitable set of changes. If this is the final pass, 266169689Skan commit them now. Otherwise, we don't know yet if we can make any 267169689Skan change, so put the old code back for now. */ 268169689Skan if (info->mode & STRUCT_EQUIV_FINAL) 269169689Skan confirm_change_group (); 270169689Skan else 271169689Skan cancel_changes (0); 272169689Skan struct_equiv_make_checkpoint (p, info); 273169689Skan } 274169689Skan} 275169689Skan 276169689Skan/* Restore state about current inputs / local registers / liveness 277169689Skan from P. */ 278169689Skanstatic void 279169689Skanstruct_equiv_restore_checkpoint (struct struct_equiv_checkpoint *p, 280169689Skan struct equiv_info *info) 281169689Skan{ 282169689Skan info->cur.ninsns = p->ninsns; 283169689Skan info->cur.x_start = p->x_start; 284169689Skan info->cur.y_start = p->y_start; 285169689Skan info->cur.input_count = p->input_count; 286169689Skan info->cur.input_valid = p->input_valid; 287169689Skan while (info->cur.local_count > p->local_count) 288169689Skan { 289169689Skan info->cur.local_count--; 290169689Skan info->cur.version--; 291169689Skan if (REGNO_REG_SET_P (info->x_local_live, 292169689Skan REGNO (info->x_local[info->cur.local_count]))) 293169689Skan { 294169689Skan assign_reg_reg_set (info->x_local_live, 295169689Skan info->x_local[info->cur.local_count], 0); 296169689Skan assign_reg_reg_set (info->y_local_live, 297169689Skan info->y_local[info->cur.local_count], 0); 298169689Skan info->cur.version--; 299169689Skan } 300169689Skan } 301169689Skan if (info->cur.version != p->version) 302169689Skan info->need_rerun = true; 303169689Skan} 304169689Skan 305169689Skan 306169689Skan/* Update register liveness to reflect that X is now life (if rvalue is 307169689Skan nonzero) or dead (if rvalue is zero) in INFO->x_block, and likewise Y 308169689Skan in INFO->y_block. Return the number of registers the liveness of which 309169689Skan changed in each block (as a negative number if registers became dead). */ 310169689Skanstatic int 311169689Skannote_local_live (struct equiv_info *info, rtx x, rtx y, int rvalue) 312169689Skan{ 313169689Skan unsigned x_regno = REGNO (x); 314169689Skan unsigned y_regno = REGNO (y); 315169689Skan int x_nominal_nregs = (x_regno >= FIRST_PSEUDO_REGISTER 316169689Skan ? 1 : hard_regno_nregs[x_regno][GET_MODE (x)]); 317169689Skan int y_nominal_nregs = (y_regno >= FIRST_PSEUDO_REGISTER 318169689Skan ? 1 : hard_regno_nregs[y_regno][GET_MODE (y)]); 319169689Skan int x_change = assign_reg_reg_set (info->x_local_live, x, rvalue); 320169689Skan int y_change = assign_reg_reg_set (info->y_local_live, y, rvalue); 321169689Skan 322169689Skan gcc_assert (x_nominal_nregs && y_nominal_nregs); 323169689Skan gcc_assert (x_change * y_nominal_nregs == y_change * x_nominal_nregs); 324169689Skan if (y_change) 325169689Skan { 326169689Skan if (reload_completed) 327169689Skan { 328169689Skan unsigned x_regno ATTRIBUTE_UNUSED = REGNO (x); 329169689Skan unsigned y_regno = REGNO (y); 330169689Skan enum machine_mode x_mode = GET_MODE (x); 331169689Skan 332169689Skan if (secondary_reload_class (0, REGNO_REG_CLASS (y_regno), x_mode, x) 333169689Skan != NO_REGS 334169689Skan#ifdef SECONDARY_MEMORY_NEEDED 335169689Skan || SECONDARY_MEMORY_NEEDED (REGNO_REG_CLASS (y_regno), 336169689Skan REGNO_REG_CLASS (x_regno), x_mode) 337169689Skan#endif 338169689Skan ) 339169689Skan y_change *= IMPOSSIBLE_MOVE_FACTOR; 340169689Skan } 341169689Skan info->cur.input_count += y_change; 342169689Skan info->cur.version++; 343169689Skan } 344169689Skan return x_change; 345169689Skan} 346169689Skan 347169689Skan/* Check if *XP is equivalent to Y. Until an an unreconcilable difference is 348169689Skan found, use in-group changes with validate_change on *XP to make register 349169689Skan assignments agree. It is the (not necessarily direct) callers 350169689Skan responsibility to verify / confirm / cancel these changes, as appropriate. 351169689Skan RVALUE indicates if the processed piece of rtl is used as a destination, in 352169689Skan which case we can't have different registers being an input. Returns 353169689Skan nonzero if the two blocks have been identified as equivalent, zero otherwise. 354169689Skan RVALUE == 0: destination 355169689Skan RVALUE == 1: source 356169689Skan RVALUE == -1: source, ignore SET_DEST of SET / clobber. */ 357169689Skanbool 358169689Skanrtx_equiv_p (rtx *xp, rtx y, int rvalue, struct equiv_info *info) 359169689Skan{ 360169689Skan rtx x = *xp; 361169689Skan enum rtx_code code; 362169689Skan int length; 363169689Skan const char *format; 364169689Skan int i; 365169689Skan 366169689Skan if (!y || !x) 367169689Skan return x == y; 368169689Skan code = GET_CODE (y); 369169689Skan if (code != REG && x == y) 370169689Skan return true; 371169689Skan if (GET_CODE (x) != code 372169689Skan || GET_MODE (x) != GET_MODE (y)) 373169689Skan return false; 374169689Skan 375169689Skan /* ??? could extend to allow CONST_INT inputs. */ 376169689Skan switch (code) 377169689Skan { 378169689Skan case REG: 379169689Skan { 380169689Skan unsigned x_regno = REGNO (x); 381169689Skan unsigned y_regno = REGNO (y); 382169689Skan int x_common_live, y_common_live; 383169689Skan 384169689Skan if (reload_completed 385169689Skan && (x_regno >= FIRST_PSEUDO_REGISTER 386169689Skan || y_regno >= FIRST_PSEUDO_REGISTER)) 387169689Skan { 388169689Skan /* We should only see this in REG_NOTEs. */ 389169689Skan gcc_assert (!info->live_update); 390169689Skan /* Returning false will cause us to remove the notes. */ 391169689Skan return false; 392169689Skan } 393169689Skan#ifdef STACK_REGS 394169689Skan /* After reg-stack, can only accept literal matches of stack regs. */ 395169689Skan if (info->mode & CLEANUP_POST_REGSTACK 396169689Skan && (IN_RANGE (x_regno, FIRST_STACK_REG, LAST_STACK_REG) 397169689Skan || IN_RANGE (y_regno, FIRST_STACK_REG, LAST_STACK_REG))) 398169689Skan return x_regno == y_regno; 399169689Skan#endif 400169689Skan 401169689Skan /* If the register is a locally live one in one block, the 402169689Skan corresponding one must be locally live in the other, too, and 403169689Skan match of identical regnos doesn't apply. */ 404169689Skan if (REGNO_REG_SET_P (info->x_local_live, x_regno)) 405169689Skan { 406169689Skan if (!REGNO_REG_SET_P (info->y_local_live, y_regno)) 407169689Skan return false; 408169689Skan } 409169689Skan else if (REGNO_REG_SET_P (info->y_local_live, y_regno)) 410169689Skan return false; 411169689Skan else if (x_regno == y_regno) 412169689Skan { 413169689Skan if (!rvalue && info->cur.input_valid 414169689Skan && (reg_overlap_mentioned_p (x, info->x_input) 415169689Skan || reg_overlap_mentioned_p (x, info->y_input))) 416169689Skan return false; 417169689Skan 418169689Skan /* Update liveness information. */ 419169689Skan if (info->live_update 420169689Skan && assign_reg_reg_set (info->common_live, x, rvalue)) 421169689Skan info->cur.version++; 422169689Skan 423169689Skan return true; 424169689Skan } 425169689Skan 426169689Skan x_common_live = REGNO_REG_SET_P (info->common_live, x_regno); 427169689Skan y_common_live = REGNO_REG_SET_P (info->common_live, y_regno); 428169689Skan if (x_common_live != y_common_live) 429169689Skan return false; 430169689Skan else if (x_common_live) 431169689Skan { 432169689Skan if (! rvalue || info->input_cost < 0 || no_new_pseudos) 433169689Skan return false; 434169689Skan /* If info->live_update is not set, we are processing notes. 435169689Skan We then allow a match with x_input / y_input found in a 436169689Skan previous pass. */ 437169689Skan if (info->live_update && !info->cur.input_valid) 438169689Skan { 439169689Skan info->cur.input_valid = true; 440169689Skan info->x_input = x; 441169689Skan info->y_input = y; 442169689Skan info->cur.input_count += optimize_size ? 2 : 1; 443169689Skan if (info->input_reg 444169689Skan && GET_MODE (info->input_reg) != GET_MODE (info->x_input)) 445169689Skan info->input_reg = NULL_RTX; 446169689Skan if (!info->input_reg) 447169689Skan info->input_reg = gen_reg_rtx (GET_MODE (info->x_input)); 448169689Skan } 449169689Skan else if ((info->live_update 450169689Skan ? ! info->cur.input_valid : ! info->x_input) 451169689Skan || ! rtx_equal_p (x, info->x_input) 452169689Skan || ! rtx_equal_p (y, info->y_input)) 453169689Skan return false; 454169689Skan validate_change (info->cur.x_start, xp, info->input_reg, 1); 455169689Skan } 456169689Skan else 457169689Skan { 458169689Skan int x_nregs = (x_regno >= FIRST_PSEUDO_REGISTER 459169689Skan ? 1 : hard_regno_nregs[x_regno][GET_MODE (x)]); 460169689Skan int y_nregs = (y_regno >= FIRST_PSEUDO_REGISTER 461169689Skan ? 1 : hard_regno_nregs[y_regno][GET_MODE (y)]); 462169689Skan int size = GET_MODE_SIZE (GET_MODE (x)); 463169689Skan enum machine_mode x_mode = GET_MODE (x); 464169689Skan unsigned x_regno_i, y_regno_i; 465169689Skan int x_nregs_i, y_nregs_i, size_i; 466169689Skan int local_count = info->cur.local_count; 467169689Skan 468169689Skan /* This might be a register local to each block. See if we have 469169689Skan it already registered. */ 470169689Skan for (i = local_count - 1; i >= 0; i--) 471169689Skan { 472169689Skan x_regno_i = REGNO (info->x_local[i]); 473169689Skan x_nregs_i = (x_regno_i >= FIRST_PSEUDO_REGISTER 474169689Skan ? 1 : hard_regno_nregs[x_regno_i][GET_MODE (x)]); 475169689Skan y_regno_i = REGNO (info->y_local[i]); 476169689Skan y_nregs_i = (y_regno_i >= FIRST_PSEUDO_REGISTER 477169689Skan ? 1 : hard_regno_nregs[y_regno_i][GET_MODE (y)]); 478169689Skan size_i = GET_MODE_SIZE (GET_MODE (info->x_local[i])); 479169689Skan 480169689Skan /* If we have a new pair of registers that is wider than an 481169689Skan old pair and enclosing it with matching offsets, 482169689Skan remove the old pair. If we find a matching, wider, old 483169689Skan pair, use the old one. If the width is the same, use the 484169689Skan old one if the modes match, but the new if they don't. 485169689Skan We don't want to get too fancy with subreg_regno_offset 486169689Skan here, so we just test two straightforward cases each. */ 487169689Skan if (info->live_update 488169689Skan && (x_mode != GET_MODE (info->x_local[i]) 489169689Skan ? size >= size_i : size > size_i)) 490169689Skan { 491169689Skan /* If the new pair is fully enclosing a matching 492169689Skan existing pair, remove the old one. N.B. because 493169689Skan we are removing one entry here, the check below 494169689Skan if we have space for a new entry will succeed. */ 495169689Skan if ((x_regno <= x_regno_i 496169689Skan && x_regno + x_nregs >= x_regno_i + x_nregs_i 497169689Skan && x_nregs == y_nregs && x_nregs_i == y_nregs_i 498169689Skan && x_regno - x_regno_i == y_regno - y_regno_i) 499169689Skan || (x_regno == x_regno_i && y_regno == y_regno_i 500169689Skan && x_nregs >= x_nregs_i && y_nregs >= y_nregs_i)) 501169689Skan { 502169689Skan info->cur.local_count = --local_count; 503169689Skan info->x_local[i] = info->x_local[local_count]; 504169689Skan info->y_local[i] = info->y_local[local_count]; 505169689Skan continue; 506169689Skan } 507169689Skan } 508169689Skan else 509169689Skan { 510169689Skan 511169689Skan /* If the new pair is fully enclosed within a matching 512169689Skan existing pair, succeed. */ 513169689Skan if (x_regno >= x_regno_i 514169689Skan && x_regno + x_nregs <= x_regno_i + x_nregs_i 515169689Skan && x_nregs == y_nregs && x_nregs_i == y_nregs_i 516169689Skan && x_regno - x_regno_i == y_regno - y_regno_i) 517169689Skan break; 518169689Skan if (x_regno == x_regno_i && y_regno == y_regno_i 519169689Skan && x_nregs <= x_nregs_i && y_nregs <= y_nregs_i) 520169689Skan break; 521169689Skan } 522169689Skan 523169689Skan /* Any other overlap causes a match failure. */ 524169689Skan if (x_regno + x_nregs > x_regno_i 525169689Skan && x_regno_i + x_nregs_i > x_regno) 526169689Skan return false; 527169689Skan if (y_regno + y_nregs > y_regno_i 528169689Skan && y_regno_i + y_nregs_i > y_regno) 529169689Skan return false; 530169689Skan } 531169689Skan if (i < 0) 532169689Skan { 533169689Skan /* Not found. Create a new entry if possible. */ 534169689Skan if (!info->live_update 535169689Skan || info->cur.local_count >= STRUCT_EQUIV_MAX_LOCAL) 536169689Skan return false; 537169689Skan info->x_local[info->cur.local_count] = x; 538169689Skan info->y_local[info->cur.local_count] = y; 539169689Skan info->cur.local_count++; 540169689Skan info->cur.version++; 541169689Skan } 542169689Skan note_local_live (info, x, y, rvalue); 543169689Skan } 544169689Skan return true; 545169689Skan } 546169689Skan case SET: 547169689Skan gcc_assert (rvalue < 0); 548169689Skan /* Ignore the destinations role as a destination. Still, we have 549169689Skan to consider input registers embedded in the addresses of a MEM. 550169689Skan N.B., we process the rvalue aspect of STRICT_LOW_PART / 551169689Skan ZERO_EXTEND / SIGN_EXTEND along with their lvalue aspect. */ 552169689Skan if(!set_dest_addr_equiv_p (SET_DEST (x), SET_DEST (y), info)) 553169689Skan return false; 554169689Skan /* Process source. */ 555169689Skan return rtx_equiv_p (&SET_SRC (x), SET_SRC (y), 1, info); 556169689Skan case PRE_MODIFY: 557169689Skan /* Process destination. */ 558169689Skan if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info)) 559169689Skan return false; 560169689Skan /* Process source. */ 561169689Skan return rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), 1, info); 562169689Skan case POST_MODIFY: 563169689Skan { 564169689Skan rtx x_dest0, x_dest1; 565169689Skan 566169689Skan /* Process destination. */ 567169689Skan x_dest0 = XEXP (x, 0); 568169689Skan gcc_assert (REG_P (x_dest0)); 569169689Skan if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info)) 570169689Skan return false; 571169689Skan x_dest1 = XEXP (x, 0); 572169689Skan /* validate_change might have changed the destination. Put it back 573169689Skan so that we can do a proper match for its role a an input. */ 574169689Skan XEXP (x, 0) = x_dest0; 575169689Skan if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info)) 576169689Skan return false; 577169689Skan gcc_assert (x_dest1 == XEXP (x, 0)); 578169689Skan /* Process source. */ 579169689Skan return rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), 1, info); 580169689Skan } 581169689Skan case CLOBBER: 582169689Skan gcc_assert (rvalue < 0); 583169689Skan return true; 584169689Skan /* Some special forms are also rvalues when they appear in lvalue 585169689Skan positions. However, we must ont try to match a register after we 586169689Skan have already altered it with validate_change, consider the rvalue 587169689Skan aspect while we process the lvalue. */ 588169689Skan case STRICT_LOW_PART: 589169689Skan case ZERO_EXTEND: 590169689Skan case SIGN_EXTEND: 591169689Skan { 592169689Skan rtx x_inner, y_inner; 593169689Skan enum rtx_code code; 594169689Skan int change; 595169689Skan 596169689Skan if (rvalue) 597169689Skan break; 598169689Skan x_inner = XEXP (x, 0); 599169689Skan y_inner = XEXP (y, 0); 600169689Skan if (GET_MODE (x_inner) != GET_MODE (y_inner)) 601169689Skan return false; 602169689Skan code = GET_CODE (x_inner); 603169689Skan if (code != GET_CODE (y_inner)) 604169689Skan return false; 605169689Skan /* The address of a MEM is an input that will be processed during 606169689Skan rvalue == -1 processing. */ 607169689Skan if (code == SUBREG) 608169689Skan { 609169689Skan if (SUBREG_BYTE (x_inner) != SUBREG_BYTE (y_inner)) 610169689Skan return false; 611169689Skan x = x_inner; 612169689Skan x_inner = SUBREG_REG (x_inner); 613169689Skan y_inner = SUBREG_REG (y_inner); 614169689Skan if (GET_MODE (x_inner) != GET_MODE (y_inner)) 615169689Skan return false; 616169689Skan code = GET_CODE (x_inner); 617169689Skan if (code != GET_CODE (y_inner)) 618169689Skan return false; 619169689Skan } 620169689Skan if (code == MEM) 621169689Skan return true; 622169689Skan gcc_assert (code == REG); 623169689Skan if (! rtx_equiv_p (&XEXP (x, 0), y_inner, rvalue, info)) 624169689Skan return false; 625169689Skan if (REGNO (x_inner) == REGNO (y_inner)) 626169689Skan { 627169689Skan change = assign_reg_reg_set (info->common_live, x_inner, 1); 628169689Skan info->cur.version++; 629169689Skan } 630169689Skan else 631169689Skan change = note_local_live (info, x_inner, y_inner, 1); 632169689Skan gcc_assert (change); 633169689Skan return true; 634169689Skan } 635169689Skan /* The AUTO_INC / POST_MODIFY / PRE_MODIFY sets are modelled to take 636169689Skan place during input processing, however, that is benign, since they 637169689Skan are paired with reads. */ 638169689Skan case MEM: 639169689Skan return !rvalue || rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), rvalue, info); 640169689Skan case POST_INC: case POST_DEC: case PRE_INC: case PRE_DEC: 641169689Skan return (rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info) 642169689Skan && rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info)); 643169689Skan case PARALLEL: 644169689Skan /* If this is a top-level PATTERN PARALLEL, we expect the caller to 645169689Skan have handled the SET_DESTs. A complex or vector PARALLEL can be 646169689Skan identified by having a mode. */ 647169689Skan gcc_assert (rvalue < 0 || GET_MODE (x) != VOIDmode); 648169689Skan break; 649169689Skan case LABEL_REF: 650169689Skan /* Check special tablejump match case. */ 651169689Skan if (XEXP (y, 0) == info->y_label) 652169689Skan return (XEXP (x, 0) == info->x_label); 653169689Skan /* We can't assume nonlocal labels have their following insns yet. */ 654169689Skan if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y)) 655169689Skan return XEXP (x, 0) == XEXP (y, 0); 656169689Skan 657169689Skan /* Two label-refs are equivalent if they point at labels 658169689Skan in the same position in the instruction stream. */ 659169689Skan return (next_real_insn (XEXP (x, 0)) 660169689Skan == next_real_insn (XEXP (y, 0))); 661169689Skan case SYMBOL_REF: 662169689Skan return XSTR (x, 0) == XSTR (y, 0); 663169689Skan /* Some rtl is guaranteed to be shared, or unique; If we didn't match 664169689Skan EQ equality above, they aren't the same. */ 665169689Skan case CONST_INT: 666169689Skan case CODE_LABEL: 667169689Skan return false; 668169689Skan default: 669169689Skan break; 670169689Skan } 671169689Skan 672169689Skan /* For commutative operations, the RTX match if the operands match in any 673169689Skan order. */ 674169689Skan if (targetm.commutative_p (x, UNKNOWN)) 675169689Skan return ((rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), rvalue, info) 676169689Skan && rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), rvalue, info)) 677169689Skan || (rtx_equiv_p (&XEXP (x, 0), XEXP (y, 1), rvalue, info) 678169689Skan && rtx_equiv_p (&XEXP (x, 1), XEXP (y, 0), rvalue, info))); 679169689Skan 680169689Skan /* Process subexpressions - this is similar to rtx_equal_p. */ 681169689Skan length = GET_RTX_LENGTH (code); 682169689Skan format = GET_RTX_FORMAT (code); 683169689Skan 684169689Skan for (i = 0; i < length; ++i) 685169689Skan { 686169689Skan switch (format[i]) 687169689Skan { 688169689Skan case 'w': 689169689Skan if (XWINT (x, i) != XWINT (y, i)) 690169689Skan return false; 691169689Skan break; 692169689Skan case 'n': 693169689Skan case 'i': 694169689Skan if (XINT (x, i) != XINT (y, i)) 695169689Skan return false; 696169689Skan break; 697169689Skan case 'V': 698169689Skan case 'E': 699169689Skan if (XVECLEN (x, i) != XVECLEN (y, i)) 700169689Skan return false; 701169689Skan if (XVEC (x, i) != 0) 702169689Skan { 703169689Skan int j; 704169689Skan for (j = 0; j < XVECLEN (x, i); ++j) 705169689Skan { 706169689Skan if (! rtx_equiv_p (&XVECEXP (x, i, j), XVECEXP (y, i, j), 707169689Skan rvalue, info)) 708169689Skan return false; 709169689Skan } 710169689Skan } 711169689Skan break; 712169689Skan case 'e': 713169689Skan if (! rtx_equiv_p (&XEXP (x, i), XEXP (y, i), rvalue, info)) 714169689Skan return false; 715169689Skan break; 716169689Skan case 'S': 717169689Skan case 's': 718169689Skan if ((XSTR (x, i) || XSTR (y, i)) 719169689Skan && (! XSTR (x, i) || ! XSTR (y, i) 720169689Skan || strcmp (XSTR (x, i), XSTR (y, i)))) 721169689Skan return false; 722169689Skan break; 723169689Skan case 'u': 724169689Skan /* These are just backpointers, so they don't matter. */ 725169689Skan break; 726169689Skan case '0': 727169689Skan case 't': 728169689Skan break; 729169689Skan /* It is believed that rtx's at this level will never 730169689Skan contain anything but integers and other rtx's, 731169689Skan except for within LABEL_REFs and SYMBOL_REFs. */ 732169689Skan default: 733169689Skan gcc_unreachable (); 734169689Skan } 735169689Skan } 736169689Skan return true; 737169689Skan} 738169689Skan 739169689Skan/* Do only the rtx_equiv_p SET_DEST processing for SETs and CLOBBERs. 740169689Skan Since we are scanning backwards, this the first step in processing each 741169689Skan insn. Return true for success. */ 742169689Skanstatic bool 743169689Skanset_dest_equiv_p (rtx x, rtx y, struct equiv_info *info) 744169689Skan{ 745169689Skan if (!x || !y) 746169689Skan return x == y; 747169689Skan if (GET_CODE (x) != GET_CODE (y)) 748169689Skan return false; 749169689Skan else if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER) 750169689Skan return rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info); 751169689Skan else if (GET_CODE (x) == PARALLEL) 752169689Skan { 753169689Skan int j; 754169689Skan 755169689Skan if (XVECLEN (x, 0) != XVECLEN (y, 0)) 756169689Skan return false; 757169689Skan for (j = 0; j < XVECLEN (x, 0); ++j) 758169689Skan { 759169689Skan rtx xe = XVECEXP (x, 0, j); 760169689Skan rtx ye = XVECEXP (y, 0, j); 761169689Skan 762169689Skan if (GET_CODE (xe) != GET_CODE (ye)) 763169689Skan return false; 764169689Skan if ((GET_CODE (xe) == SET || GET_CODE (xe) == CLOBBER) 765169689Skan && ! rtx_equiv_p (&XEXP (xe, 0), XEXP (ye, 0), 0, info)) 766169689Skan return false; 767169689Skan } 768169689Skan } 769169689Skan return true; 770169689Skan} 771169689Skan 772169689Skan/* Process MEMs in SET_DEST destinations. We must not process this together 773169689Skan with REG SET_DESTs, but must do it separately, lest when we see 774169689Skan [(set (reg:SI foo) (bar)) 775169689Skan (set (mem:SI (reg:SI foo) (baz)))] 776169689Skan struct_equiv_block_eq could get confused to assume that (reg:SI foo) 777169689Skan is not live before this instruction. */ 778169689Skanstatic bool 779169689Skanset_dest_addr_equiv_p (rtx x, rtx y, struct equiv_info *info) 780169689Skan{ 781169689Skan enum rtx_code code = GET_CODE (x); 782169689Skan int length; 783169689Skan const char *format; 784169689Skan int i; 785169689Skan 786169689Skan if (code != GET_CODE (y)) 787169689Skan return false; 788169689Skan if (code == MEM) 789169689Skan return rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info); 790169689Skan 791169689Skan /* Process subexpressions. */ 792169689Skan length = GET_RTX_LENGTH (code); 793169689Skan format = GET_RTX_FORMAT (code); 794169689Skan 795169689Skan for (i = 0; i < length; ++i) 796169689Skan { 797169689Skan switch (format[i]) 798169689Skan { 799169689Skan case 'V': 800169689Skan case 'E': 801169689Skan if (XVECLEN (x, i) != XVECLEN (y, i)) 802169689Skan return false; 803169689Skan if (XVEC (x, i) != 0) 804169689Skan { 805169689Skan int j; 806169689Skan for (j = 0; j < XVECLEN (x, i); ++j) 807169689Skan { 808169689Skan if (! set_dest_addr_equiv_p (XVECEXP (x, i, j), 809169689Skan XVECEXP (y, i, j), info)) 810169689Skan return false; 811169689Skan } 812169689Skan } 813169689Skan break; 814169689Skan case 'e': 815169689Skan if (! set_dest_addr_equiv_p (XEXP (x, i), XEXP (y, i), info)) 816169689Skan return false; 817169689Skan break; 818169689Skan default: 819169689Skan break; 820169689Skan } 821169689Skan } 822169689Skan return true; 823169689Skan} 824169689Skan 825169689Skan/* Check if the set of REG_DEAD notes attached to I1 and I2 allows us to 826169689Skan go ahead with merging I1 and I2, which otherwise look fine. 827169689Skan Inputs / local registers for the inputs of I1 and I2 have already been 828169689Skan set up. */ 829169689Skanstatic bool 830169689Skandeath_notes_match_p (rtx i1 ATTRIBUTE_UNUSED, rtx i2 ATTRIBUTE_UNUSED, 831169689Skan struct equiv_info *info ATTRIBUTE_UNUSED) 832169689Skan{ 833169689Skan#ifdef STACK_REGS 834169689Skan /* If cross_jump_death_matters is not 0, the insn's mode 835169689Skan indicates whether or not the insn contains any stack-like regs. */ 836169689Skan 837169689Skan if ((info->mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1)) 838169689Skan { 839169689Skan /* If register stack conversion has already been done, then 840169689Skan death notes must also be compared before it is certain that 841169689Skan the two instruction streams match. */ 842169689Skan 843169689Skan rtx note; 844169689Skan HARD_REG_SET i1_regset, i2_regset; 845169689Skan 846169689Skan CLEAR_HARD_REG_SET (i1_regset); 847169689Skan CLEAR_HARD_REG_SET (i2_regset); 848169689Skan 849169689Skan for (note = REG_NOTES (i1); note; note = XEXP (note, 1)) 850169689Skan if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0))) 851169689Skan SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0))); 852169689Skan 853169689Skan for (note = REG_NOTES (i2); note; note = XEXP (note, 1)) 854169689Skan if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0))) 855169689Skan { 856169689Skan unsigned regno = REGNO (XEXP (note, 0)); 857169689Skan int i; 858169689Skan 859169689Skan for (i = info->cur.local_count - 1; i >= 0; i--) 860169689Skan if (regno == REGNO (info->y_local[i])) 861169689Skan { 862169689Skan regno = REGNO (info->x_local[i]); 863169689Skan break; 864169689Skan } 865169689Skan SET_HARD_REG_BIT (i2_regset, regno); 866169689Skan } 867169689Skan 868169689Skan GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done); 869169689Skan 870169689Skan return false; 871169689Skan 872169689Skan done: 873169689Skan ; 874169689Skan } 875169689Skan#endif 876169689Skan return true; 877169689Skan} 878169689Skan 879169689Skan/* Return true if I1 and I2 are equivalent and thus can be crossjumped. */ 880169689Skan 881169689Skanbool 882169689Skaninsns_match_p (rtx i1, rtx i2, struct equiv_info *info) 883169689Skan{ 884169689Skan int rvalue_change_start; 885169689Skan struct struct_equiv_checkpoint before_rvalue_change; 886169689Skan 887169689Skan /* Verify that I1 and I2 are equivalent. */ 888169689Skan if (GET_CODE (i1) != GET_CODE (i2)) 889169689Skan return false; 890169689Skan 891169689Skan info->cur.x_start = i1; 892169689Skan info->cur.y_start = i2; 893169689Skan 894169689Skan /* If this is a CALL_INSN, compare register usage information. 895169689Skan If we don't check this on stack register machines, the two 896169689Skan CALL_INSNs might be merged leaving reg-stack.c with mismatching 897169689Skan numbers of stack registers in the same basic block. 898169689Skan If we don't check this on machines with delay slots, a delay slot may 899169689Skan be filled that clobbers a parameter expected by the subroutine. 900169689Skan 901169689Skan ??? We take the simple route for now and assume that if they're 902169689Skan equal, they were constructed identically. */ 903169689Skan 904169689Skan if (CALL_P (i1)) 905169689Skan { 906169689Skan if (SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2) 907169689Skan || ! set_dest_equiv_p (PATTERN (i1), PATTERN (i2), info) 908169689Skan || ! set_dest_equiv_p (CALL_INSN_FUNCTION_USAGE (i1), 909169689Skan CALL_INSN_FUNCTION_USAGE (i2), info) 910169689Skan || ! rtx_equiv_p (&CALL_INSN_FUNCTION_USAGE (i1), 911169689Skan CALL_INSN_FUNCTION_USAGE (i2), -1, info)) 912169689Skan { 913169689Skan cancel_changes (0); 914169689Skan return false; 915169689Skan } 916169689Skan } 917169689Skan else if (INSN_P (i1)) 918169689Skan { 919169689Skan if (! set_dest_equiv_p (PATTERN (i1), PATTERN (i2), info)) 920169689Skan { 921169689Skan cancel_changes (0); 922169689Skan return false; 923169689Skan } 924169689Skan } 925169689Skan rvalue_change_start = num_validated_changes (); 926169689Skan struct_equiv_make_checkpoint (&before_rvalue_change, info); 927169689Skan /* Check death_notes_match_p *after* the inputs have been processed, 928169689Skan so that local inputs will already have been set up. */ 929169689Skan if (! INSN_P (i1) 930169689Skan || (!bitmap_bit_p (info->equiv_used, info->cur.ninsns) 931169689Skan && rtx_equiv_p (&PATTERN (i1), PATTERN (i2), -1, info) 932169689Skan && death_notes_match_p (i1, i2, info) 933169689Skan && verify_changes (0))) 934169689Skan return true; 935169689Skan 936169689Skan /* Do not do EQUIV substitution after reload. First, we're undoing the 937169689Skan work of reload_cse. Second, we may be undoing the work of the post- 938169689Skan reload splitting pass. */ 939169689Skan /* ??? Possibly add a new phase switch variable that can be used by 940169689Skan targets to disallow the troublesome insns after splitting. */ 941169689Skan if (!reload_completed) 942169689Skan { 943169689Skan rtx equiv1, equiv2; 944169689Skan 945169689Skan cancel_changes (rvalue_change_start); 946169689Skan struct_equiv_restore_checkpoint (&before_rvalue_change, info); 947169689Skan 948169689Skan /* The following code helps take care of G++ cleanups. */ 949169689Skan equiv1 = find_reg_equal_equiv_note (i1); 950169689Skan equiv2 = find_reg_equal_equiv_note (i2); 951169689Skan if (equiv1 && equiv2 952169689Skan /* If the equivalences are not to a constant, they may 953169689Skan reference pseudos that no longer exist, so we can't 954169689Skan use them. */ 955169689Skan && (! reload_completed 956169689Skan || (CONSTANT_P (XEXP (equiv1, 0)) 957169689Skan && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0))))) 958169689Skan { 959169689Skan rtx s1 = single_set (i1); 960169689Skan rtx s2 = single_set (i2); 961169689Skan 962169689Skan if (s1 != 0 && s2 != 0) 963169689Skan { 964169689Skan validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1); 965169689Skan validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1); 966169689Skan /* Only inspecting the new SET_SRC is not good enough, 967169689Skan because there may also be bare USEs in a single_set 968169689Skan PARALLEL. */ 969169689Skan if (rtx_equiv_p (&PATTERN (i1), PATTERN (i2), -1, info) 970169689Skan && death_notes_match_p (i1, i2, info) 971169689Skan && verify_changes (0)) 972169689Skan { 973169689Skan /* Mark this insn so that we'll use the equivalence in 974169689Skan all subsequent passes. */ 975169689Skan bitmap_set_bit (info->equiv_used, info->cur.ninsns); 976169689Skan return true; 977169689Skan } 978169689Skan } 979169689Skan } 980169689Skan } 981169689Skan 982169689Skan cancel_changes (0); 983169689Skan return false; 984169689Skan} 985169689Skan 986169689Skan/* Set up mode and register information in INFO. Return true for success. */ 987169689Skanbool 988169689Skanstruct_equiv_init (int mode, struct equiv_info *info) 989169689Skan{ 990169689Skan if ((info->x_block->flags | info->y_block->flags) & BB_DIRTY) 991169689Skan update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES, 992169689Skan (PROP_DEATH_NOTES 993169689Skan | ((mode & CLEANUP_POST_REGSTACK) 994169689Skan ? PROP_POST_REGSTACK : 0))); 995169689Skan if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end, 996169689Skan info->y_block->il.rtl->global_live_at_end)) 997169689Skan { 998169689Skan#ifdef STACK_REGS 999169689Skan unsigned rn; 1000169689Skan 1001169689Skan if (!(mode & CLEANUP_POST_REGSTACK)) 1002169689Skan return false; 1003169689Skan /* After reg-stack. Remove bogus live info about stack regs. N.B. 1004169689Skan these regs are not necessarily all dead - we swap random bogosity 1005169689Skan against constant bogosity. However, clearing these bits at 1006169689Skan least makes the regsets comparable. */ 1007169689Skan for (rn = FIRST_STACK_REG; rn <= LAST_STACK_REG; rn++) 1008169689Skan { 1009169689Skan CLEAR_REGNO_REG_SET (info->x_block->il.rtl->global_live_at_end, rn); 1010169689Skan CLEAR_REGNO_REG_SET (info->y_block->il.rtl->global_live_at_end, rn); 1011169689Skan } 1012169689Skan if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end, 1013169689Skan info->y_block->il.rtl->global_live_at_end)) 1014169689Skan#endif 1015169689Skan return false; 1016169689Skan } 1017169689Skan info->mode = mode; 1018169689Skan if (mode & STRUCT_EQUIV_START) 1019169689Skan { 1020169689Skan info->x_input = info->y_input = info->input_reg = NULL_RTX; 1021169689Skan info->equiv_used = ALLOC_REG_SET (®_obstack); 1022169689Skan info->check_input_conflict = false; 1023169689Skan } 1024169689Skan info->had_input_conflict = false; 1025169689Skan info->cur.ninsns = info->cur.version = 0; 1026169689Skan info->cur.local_count = info->cur.input_count = 0; 1027169689Skan info->cur.x_start = info->cur.y_start = NULL_RTX; 1028169689Skan info->x_label = info->y_label = NULL_RTX; 1029169689Skan info->need_rerun = false; 1030169689Skan info->live_update = true; 1031169689Skan info->cur.input_valid = false; 1032169689Skan info->common_live = ALLOC_REG_SET (®_obstack); 1033169689Skan info->x_local_live = ALLOC_REG_SET (®_obstack); 1034169689Skan info->y_local_live = ALLOC_REG_SET (®_obstack); 1035169689Skan COPY_REG_SET (info->common_live, info->x_block->il.rtl->global_live_at_end); 1036169689Skan struct_equiv_make_checkpoint (&info->best_match, info); 1037169689Skan return true; 1038169689Skan} 1039169689Skan 1040169689Skan/* Insns XI and YI have been matched. Merge memory attributes and reg 1041169689Skan notes. */ 1042169689Skanstatic void 1043169689Skanstruct_equiv_merge (rtx xi, rtx yi, struct equiv_info *info) 1044169689Skan{ 1045169689Skan rtx equiv1, equiv2; 1046169689Skan 1047169689Skan merge_memattrs (xi, yi); 1048169689Skan 1049169689Skan /* If the merged insns have different REG_EQUAL notes, then 1050169689Skan remove them. */ 1051169689Skan info->live_update = false; 1052169689Skan equiv1 = find_reg_equal_equiv_note (xi); 1053169689Skan equiv2 = find_reg_equal_equiv_note (yi); 1054169689Skan if (equiv1 && !equiv2) 1055169689Skan remove_note (xi, equiv1); 1056169689Skan else if (!equiv1 && equiv2) 1057169689Skan remove_note (yi, equiv2); 1058169689Skan else if (equiv1 && equiv2 1059169689Skan && !rtx_equiv_p (&XEXP (equiv1, 0), XEXP (equiv2, 0), 1060169689Skan 1, info)) 1061169689Skan { 1062169689Skan remove_note (xi, equiv1); 1063169689Skan remove_note (yi, equiv2); 1064169689Skan } 1065169689Skan info->live_update = true; 1066169689Skan} 1067169689Skan 1068169689Skan/* Return number of matched insns. 1069169689Skan This function must be called up to three times for a successful cross-jump 1070169689Skan match: 1071169689Skan first to find out which instructions do match. While trying to match 1072169689Skan another instruction that doesn't match, we destroy information in info 1073169689Skan about the actual inputs. So if there have been any before the last 1074169689Skan match attempt, we need to call this function again to recompute the 1075169689Skan actual inputs up to the actual start of the matching sequence. 1076169689Skan When we are then satisfied that the cross-jump is worthwhile, we 1077169689Skan call this function a third time to make any changes needed to make the 1078169689Skan sequences match: apply equivalences, remove non-matching 1079169689Skan notes and merge memory attributes. */ 1080169689Skanint 1081169689Skanstruct_equiv_block_eq (int mode, struct equiv_info *info) 1082169689Skan{ 1083169689Skan rtx x_stop, y_stop; 1084169689Skan rtx xi, yi; 1085169689Skan int i; 1086169689Skan 1087169689Skan if (mode & STRUCT_EQUIV_START) 1088169689Skan { 1089169689Skan x_stop = BB_HEAD (info->x_block); 1090169689Skan y_stop = BB_HEAD (info->y_block); 1091169689Skan if (!x_stop || !y_stop) 1092169689Skan return 0; 1093169689Skan } 1094169689Skan else 1095169689Skan { 1096169689Skan x_stop = info->cur.x_start; 1097169689Skan y_stop = info->cur.y_start; 1098169689Skan } 1099169689Skan if (!struct_equiv_init (mode, info)) 1100169689Skan gcc_unreachable (); 1101169689Skan 1102169689Skan /* Skip simple jumps at the end of the blocks. Complex jumps still 1103169689Skan need to be compared for equivalence, which we'll do below. */ 1104169689Skan 1105169689Skan xi = BB_END (info->x_block); 1106169689Skan if (onlyjump_p (xi) 1107169689Skan || (returnjump_p (xi) && !side_effects_p (PATTERN (xi)))) 1108169689Skan { 1109169689Skan info->cur.x_start = xi; 1110169689Skan xi = PREV_INSN (xi); 1111169689Skan } 1112169689Skan 1113169689Skan yi = BB_END (info->y_block); 1114169689Skan if (onlyjump_p (yi) 1115169689Skan || (returnjump_p (yi) && !side_effects_p (PATTERN (yi)))) 1116169689Skan { 1117169689Skan info->cur.y_start = yi; 1118169689Skan /* Count everything except for unconditional jump as insn. */ 1119169689Skan /* ??? Is it right to count unconditional jumps with a clobber? 1120169689Skan Should we count conditional returns? */ 1121169689Skan if (!simplejump_p (yi) && !returnjump_p (yi) && info->cur.x_start) 1122169689Skan info->cur.ninsns++; 1123169689Skan yi = PREV_INSN (yi); 1124169689Skan } 1125169689Skan 1126169689Skan if (mode & STRUCT_EQUIV_MATCH_JUMPS) 1127169689Skan { 1128169689Skan /* The caller is expected to have compared the jumps already, but we 1129169689Skan need to match them again to get any local registers and inputs. */ 1130169689Skan gcc_assert (!info->cur.x_start == !info->cur.y_start); 1131169689Skan if (info->cur.x_start) 1132169689Skan { 1133169689Skan if (any_condjump_p (info->cur.x_start) 1134169689Skan ? !condjump_equiv_p (info, false) 1135169689Skan : !insns_match_p (info->cur.x_start, info->cur.y_start, info)) 1136169689Skan gcc_unreachable (); 1137169689Skan } 1138169689Skan else if (any_condjump_p (xi) && any_condjump_p (yi)) 1139169689Skan { 1140169689Skan info->cur.x_start = xi; 1141169689Skan info->cur.y_start = yi; 1142169689Skan xi = PREV_INSN (xi); 1143169689Skan yi = PREV_INSN (yi); 1144169689Skan info->cur.ninsns++; 1145169689Skan if (!condjump_equiv_p (info, false)) 1146169689Skan gcc_unreachable (); 1147169689Skan } 1148169689Skan if (info->cur.x_start && info->mode & STRUCT_EQUIV_FINAL) 1149169689Skan struct_equiv_merge (info->cur.x_start, info->cur.y_start, info); 1150169689Skan } 1151169689Skan 1152169689Skan struct_equiv_improve_checkpoint (&info->best_match, info); 1153169689Skan info->x_end = xi; 1154169689Skan info->y_end = yi; 1155169689Skan if (info->cur.x_start != x_stop) 1156169689Skan for (;;) 1157169689Skan { 1158169689Skan /* Ignore notes. */ 1159169689Skan while (!INSN_P (xi) && xi != x_stop) 1160169689Skan xi = PREV_INSN (xi); 1161169689Skan 1162169689Skan while (!INSN_P (yi) && yi != y_stop) 1163169689Skan yi = PREV_INSN (yi); 1164169689Skan 1165169689Skan if (!insns_match_p (xi, yi, info)) 1166169689Skan break; 1167169689Skan if (INSN_P (xi)) 1168169689Skan { 1169169689Skan if (info->mode & STRUCT_EQUIV_FINAL) 1170169689Skan struct_equiv_merge (xi, yi, info); 1171169689Skan info->cur.ninsns++; 1172169689Skan struct_equiv_improve_checkpoint (&info->best_match, info); 1173169689Skan } 1174169689Skan if (xi == x_stop || yi == y_stop) 1175169689Skan { 1176169689Skan /* If we reached the start of at least one of the blocks, but 1177169689Skan best_match hasn't been advanced back to the first valid insn 1178169689Skan yet, represent the increased benefit of completing the block 1179169689Skan as an increased instruction count. */ 1180169689Skan if (info->best_match.x_start != info->cur.x_start 1181169689Skan && (xi == BB_HEAD (info->x_block) 1182169689Skan || yi == BB_HEAD (info->y_block))) 1183169689Skan { 1184169689Skan info->cur.ninsns++; 1185169689Skan struct_equiv_improve_checkpoint (&info->best_match, info); 1186169689Skan info->cur.ninsns--; 1187169689Skan if (info->best_match.ninsns > info->cur.ninsns) 1188169689Skan info->best_match.ninsns = info->cur.ninsns; 1189169689Skan } 1190169689Skan break; 1191169689Skan } 1192169689Skan xi = PREV_INSN (xi); 1193169689Skan yi = PREV_INSN (yi); 1194169689Skan } 1195169689Skan 1196169689Skan /* If we failed to match an insn, but had some changes registered from 1197169689Skan trying to make the insns match, we need to cancel these changes now. */ 1198169689Skan cancel_changes (0); 1199169689Skan /* Restore to best_match to get the sequence with the best known-so-far 1200169689Skan cost-benefit difference. */ 1201169689Skan struct_equiv_restore_checkpoint (&info->best_match, info); 1202169689Skan 1203169689Skan /* Include preceding notes and labels in the cross-jump / if-conversion. 1204169689Skan One, this may bring us to the head of the blocks. 1205169689Skan Two, it keeps line number notes as matched as may be. */ 1206169689Skan if (info->cur.ninsns) 1207169689Skan { 1208169689Skan xi = info->cur.x_start; 1209169689Skan yi = info->cur.y_start; 1210169689Skan while (xi != x_stop && !INSN_P (PREV_INSN (xi))) 1211169689Skan xi = PREV_INSN (xi); 1212169689Skan 1213169689Skan while (yi != y_stop && !INSN_P (PREV_INSN (yi))) 1214169689Skan yi = PREV_INSN (yi); 1215169689Skan 1216169689Skan info->cur.x_start = xi; 1217169689Skan info->cur.y_start = yi; 1218169689Skan } 1219169689Skan 1220169689Skan if (!info->cur.input_valid) 1221169689Skan info->x_input = info->y_input = info->input_reg = NULL_RTX; 1222169689Skan if (!info->need_rerun) 1223169689Skan { 1224169689Skan find_dying_inputs (info); 1225169689Skan if (info->mode & STRUCT_EQUIV_FINAL) 1226169689Skan { 1227169689Skan if (info->check_input_conflict && ! resolve_input_conflict (info)) 1228169689Skan gcc_unreachable (); 1229169689Skan } 1230169689Skan else 1231169689Skan { 1232169689Skan bool input_conflict = info->had_input_conflict; 1233169689Skan 1234169689Skan if (!input_conflict 1235169689Skan && info->dying_inputs > 1 1236169689Skan && bitmap_intersect_p (info->x_local_live, info->y_local_live)) 1237169689Skan { 1238169689Skan regset_head clobbered_regs; 1239169689Skan 1240169689Skan INIT_REG_SET (&clobbered_regs); 1241169689Skan for (i = 0; i < info->cur.local_count; i++) 1242169689Skan { 1243169689Skan if (assign_reg_reg_set (&clobbered_regs, info->y_local[i], 0)) 1244169689Skan { 1245169689Skan input_conflict = true; 1246169689Skan break; 1247169689Skan } 1248169689Skan assign_reg_reg_set (&clobbered_regs, info->x_local[i], 1); 1249169689Skan } 1250169689Skan CLEAR_REG_SET (&clobbered_regs); 1251169689Skan } 1252169689Skan if (input_conflict && !info->check_input_conflict) 1253169689Skan info->need_rerun = true; 1254169689Skan info->check_input_conflict = input_conflict; 1255169689Skan } 1256169689Skan } 1257169689Skan 1258169689Skan if (info->mode & STRUCT_EQUIV_NEED_FULL_BLOCK 1259169689Skan && (info->cur.x_start != x_stop || info->cur.y_start != y_stop)) 1260169689Skan return 0; 1261169689Skan return info->cur.ninsns; 1262169689Skan} 1263169689Skan 1264169689Skan/* For each local register, set info->local_rvalue to true iff the register 1265169689Skan is a dying input. Store the total number of these in info->dying_inputs. */ 1266169689Skanstatic void 1267169689Skanfind_dying_inputs (struct equiv_info *info) 1268169689Skan{ 1269169689Skan int i; 1270169689Skan 1271169689Skan info->dying_inputs = 0; 1272169689Skan for (i = info->cur.local_count-1; i >=0; i--) 1273169689Skan { 1274169689Skan rtx x = info->x_local[i]; 1275169689Skan unsigned regno = REGNO (x); 1276169689Skan int nregs = (regno >= FIRST_PSEUDO_REGISTER 1277169689Skan ? 1 : hard_regno_nregs[regno][GET_MODE (x)]); 1278169689Skan 1279169689Skan for (info->local_rvalue[i] = false; nregs > 0; regno++, --nregs) 1280169689Skan if (REGNO_REG_SET_P (info->x_local_live, regno)) 1281169689Skan { 1282169689Skan info->dying_inputs++; 1283169689Skan info->local_rvalue[i] = true; 1284169689Skan break; 1285169689Skan } 1286169689Skan } 1287169689Skan} 1288169689Skan 1289169689Skan/* For each local register that is a dying input, y_local[i] will be 1290169689Skan copied to x_local[i]. We'll do this in ascending order. Try to 1291169689Skan re-order the locals to avoid conflicts like r3 = r2; r4 = r3; . 1292169689Skan Return true iff the re-ordering is successful, or not necessary. */ 1293169689Skanstatic bool 1294169689Skanresolve_input_conflict (struct equiv_info *info) 1295169689Skan{ 1296169689Skan int i, j, end; 1297169689Skan int nswaps = 0; 1298169689Skan rtx save_x_local[STRUCT_EQUIV_MAX_LOCAL]; 1299169689Skan rtx save_y_local[STRUCT_EQUIV_MAX_LOCAL]; 1300169689Skan 1301169689Skan find_dying_inputs (info); 1302169689Skan if (info->dying_inputs <= 1) 1303169689Skan return true; 1304169689Skan memcpy (save_x_local, info->x_local, sizeof save_x_local); 1305169689Skan memcpy (save_y_local, info->y_local, sizeof save_y_local); 1306169689Skan end = info->cur.local_count - 1; 1307169689Skan for (i = 0; i <= end; i++) 1308169689Skan { 1309169689Skan /* Cycle detection with regsets is expensive, so we just check that 1310169689Skan we don't exceed the maximum number of swaps needed in the acyclic 1311169689Skan case. */ 1312169689Skan int max_swaps = end - i; 1313169689Skan 1314169689Skan /* Check if x_local[i] will be clobbered. */ 1315169689Skan if (!info->local_rvalue[i]) 1316169689Skan continue; 1317169689Skan /* Check if any later value needs to be copied earlier. */ 1318169689Skan for (j = i + 1; j <= end; j++) 1319169689Skan { 1320169689Skan rtx tmp; 1321169689Skan 1322169689Skan if (!info->local_rvalue[j]) 1323169689Skan continue; 1324169689Skan if (!reg_overlap_mentioned_p (info->x_local[i], info->y_local[j])) 1325169689Skan continue; 1326169689Skan if (--max_swaps < 0) 1327169689Skan { 1328169689Skan memcpy (info->x_local, save_x_local, sizeof save_x_local); 1329169689Skan memcpy (info->y_local, save_y_local, sizeof save_y_local); 1330169689Skan return false; 1331169689Skan } 1332169689Skan nswaps++; 1333169689Skan tmp = info->x_local[i]; 1334169689Skan info->x_local[i] = info->x_local[j]; 1335169689Skan info->x_local[j] = tmp; 1336169689Skan tmp = info->y_local[i]; 1337169689Skan info->y_local[i] = info->y_local[j]; 1338169689Skan info->y_local[j] = tmp; 1339169689Skan j = i; 1340169689Skan } 1341169689Skan } 1342169689Skan info->had_input_conflict = true; 1343169689Skan if (dump_file && nswaps) 1344169689Skan fprintf (dump_file, "Resolved input conflict, %d %s.\n", 1345169689Skan nswaps, nswaps == 1 ? "swap" : "swaps"); 1346169689Skan return true; 1347169689Skan} 1348