gcc/postreload.c

   1 /* Perform simple optimizations to clean up the result of reload.
   2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
   3    1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
   4    2010 Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26
  27 #include "machmode.h"
  28 #include "hard-reg-set.h"
  29 #include "rtl.h"
  30 #include "tm_p.h"
  31 #include "obstack.h"
  32 #include "insn-config.h"
  33 #include "flags.h"
  34 #include "function.h"
  35 #include "expr.h"
  36 #include "optabs.h"
  37 #include "regs.h"
  38 #include "basic-block.h"
  39 #include "reload.h"
  40 #include "recog.h"
  41 #include "output.h"
  42 #include "cselib.h"
  43 #include "diagnostic-core.h"
  44 #include "except.h"
  45 #include "tree.h"
  46 #include "target.h"
  47 #include "timevar.h"
  48 #include "tree-pass.h"
  49 #include "df.h"
  50 #include "dbgcnt.h"
  51
  52 static int reload_cse_noop_set_p (rtx);
  53 static void reload_cse_simplify (rtx, rtx);
  54 static void reload_cse_regs_1 (rtx);
  55 static int reload_cse_simplify_set (rtx, rtx);
  56 static int reload_cse_simplify_operands (rtx, rtx);
  57
  58 static void reload_combine (void);
  59 static void reload_combine_note_use (rtx *, rtx, int, rtx);
  60 static void reload_combine_note_store (rtx, const_rtx, void *);
  61
  62 static bool reload_cse_move2add (rtx);
  63 static void move2add_note_store (rtx, const_rtx, void *);
  64
  65 /* Call cse / combine like post-reload optimization phases.
  66    FIRST is the first instruction.  */
  67 void
  68 reload_cse_regs (rtx first ATTRIBUTE_UNUSED)
  69 {
  70   bool moves_converted;
  71   reload_cse_regs_1 (first);
  72   reload_combine ();
  73   moves_converted = reload_cse_move2add (first);
  74   if (flag_expensive_optimizations)
  75     {
  76       if (moves_converted)
  77         reload_combine ();
  78       reload_cse_regs_1 (first);
  79     }
  80 }
  81
  82 /* See whether a single set SET is a noop.  */
  83 static int
  84 reload_cse_noop_set_p (rtx set)
  85 {
  86   if (cselib_reg_set_mode (SET_DEST (set)) != GET_MODE (SET_DEST (set)))
  87     return 0;
  88
  89   return rtx_equal_for_cselib_p (SET_DEST (set), SET_SRC (set));
  90 }
  91
  92 /* Try to simplify INSN.  */
  93 static void
  94 reload_cse_simplify (rtx insn, rtx testreg)
  95 {
  96   rtx body = PATTERN (insn);
  97
  98   if (GET_CODE (body) == SET)
  99     {
 100       int count = 0;
 101
 102       /* Simplify even if we may think it is a no-op.
 103          We may think a memory load of a value smaller than WORD_SIZE
 104          is redundant because we haven't taken into account possible
 105          implicit extension.  reload_cse_simplify_set() will bring
 106          this out, so it's safer to simplify before we delete.  */
 107       count += reload_cse_simplify_set (body, insn);
 108
 109       if (!count && reload_cse_noop_set_p (body))
 110         {
 111           rtx value = SET_DEST (body);
 112           if (REG_P (value)
 113               && ! REG_FUNCTION_VALUE_P (value))
 114             value = 0;
 115           delete_insn_and_edges (insn);
 116           return;
 117         }
 118
 119       if (count > 0)
 120         apply_change_group ();
 121       else
 122         reload_cse_simplify_operands (insn, testreg);
 123     }
 124   else if (GET_CODE (body) == PARALLEL)
 125     {
 126       int i;
 127       int count = 0;
 128       rtx value = NULL_RTX;
 129
 130       /* Registers mentioned in the clobber list for an asm cannot be reused
 131          within the body of the asm.  Invalidate those registers now so that
 132          we don't try to substitute values for them.  */
 133       if (asm_noperands (body) >= 0)
 134         {
 135           for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
 136             {
 137               rtx part = XVECEXP (body, 0, i);
 138               if (GET_CODE (part) == CLOBBER && REG_P (XEXP (part, 0)))
 139                 cselib_invalidate_rtx (XEXP (part, 0));
 140             }
 141         }
 142
 143       /* If every action in a PARALLEL is a noop, we can delete
 144          the entire PARALLEL.  */
 145       for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
 146         {
 147           rtx part = XVECEXP (body, 0, i);
 148           if (GET_CODE (part) == SET)
 149             {
 150               if (! reload_cse_noop_set_p (part))
 151                 break;
 152               if (REG_P (SET_DEST (part))
 153                   && REG_FUNCTION_VALUE_P (SET_DEST (part)))
 154                 {
 155                   if (value)
 156                     break;
 157                   value = SET_DEST (part);
 158                 }
 159             }
 160           else if (GET_CODE (part) != CLOBBER)
 161             break;
 162         }
 163
 164       if (i < 0)
 165         {
 166           delete_insn_and_edges (insn);
 167           /* We're done with this insn.  */
 168           return;
 169         }
 170
 171       /* It's not a no-op, but we can try to simplify it.  */
 172       for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
 173         if (GET_CODE (XVECEXP (body, 0, i)) == SET)
 174           count += reload_cse_simplify_set (XVECEXP (body, 0, i), insn);
 175
 176       if (count > 0)
 177         apply_change_group ();
 178       else
 179         reload_cse_simplify_operands (insn, testreg);
 180     }
 181 }
 182
 183 /* Do a very simple CSE pass over the hard registers.
 184
 185    This function detects no-op moves where we happened to assign two
 186    different pseudo-registers to the same hard register, and then
 187    copied one to the other.  Reload will generate a useless
 188    instruction copying a register to itself.
 189
 190    This function also detects cases where we load a value from memory
 191    into two different registers, and (if memory is more expensive than
 192    registers) changes it to simply copy the first register into the
 193    second register.
 194
 195    Another optimization is performed that scans the operands of each
 196    instruction to see whether the value is already available in a
 197    hard register.  It then replaces the operand with the hard register
 198    if possible, much like an optional reload would.  */
 199
 200 static void
 201 reload_cse_regs_1 (rtx first)
 202 {
 203   rtx insn;
 204   rtx testreg = gen_rtx_REG (VOIDmode, -1);
 205
 206   cselib_init (CSELIB_RECORD_MEMORY);
 207   init_alias_analysis ();
 208
 209   for (insn = first; insn; insn = NEXT_INSN (insn))
 210     {
 211       if (INSN_P (insn))
 212         reload_cse_simplify (insn, testreg);
 213
 214       cselib_process_insn (insn);
 215     }
 216
 217   /* Clean up.  */
 218   end_alias_analysis ();
 219   cselib_finish ();
 220 }
 221
 222 /* Try to simplify a single SET instruction.  SET is the set pattern.
 223    INSN is the instruction it came from.
 224    This function only handles one case: if we set a register to a value
 225    which is not a register, we try to find that value in some other register
 226    and change the set into a register copy.  */
 227
 228 static int
 229 reload_cse_simplify_set (rtx set, rtx insn)
 230 {
 231   int did_change = 0;
 232   int dreg;
 233   rtx src;
 234   enum reg_class dclass;
 235   int old_cost;
 236   cselib_val *val;
 237   struct elt_loc_list *l;
 238 #ifdef LOAD_EXTEND_OP
 239   enum rtx_code extend_op = UNKNOWN;
 240 #endif
 241   bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
 242
 243   dreg = true_regnum (SET_DEST (set));
 244   if (dreg < 0)
 245     return 0;
 246
 247   src = SET_SRC (set);
 248   if (side_effects_p (src) || true_regnum (src) >= 0)
 249     return 0;
 250
 251   dclass = REGNO_REG_CLASS (dreg);
 252
 253 #ifdef LOAD_EXTEND_OP
 254   /* When replacing a memory with a register, we need to honor assumptions
 255      that combine made wrt the contents of sign bits.  We'll do this by
 256      generating an extend instruction instead of a reg->reg copy.  Thus
 257      the destination must be a register that we can widen.  */
 258   if (MEM_P (src)
 259       && GET_MODE_BITSIZE (GET_MODE (src)) < BITS_PER_WORD
 260       && (extend_op = LOAD_EXTEND_OP (GET_MODE (src))) != UNKNOWN
 261       && !REG_P (SET_DEST (set)))
 262     return 0;
 263 #endif
 264
 265   val = cselib_lookup (src, GET_MODE (SET_DEST (set)), 0);
 266   if (! val)
 267     return 0;
 268
 269   /* If memory loads are cheaper than register copies, don't change them.  */
 270   if (MEM_P (src))
 271     old_cost = memory_move_cost (GET_MODE (src), dclass, true);
 272   else if (REG_P (src))
 273     old_cost = register_move_cost (GET_MODE (src),
 274                                    REGNO_REG_CLASS (REGNO (src)), dclass);
 275   else
 276     old_cost = rtx_cost (src, SET, speed);
 277
 278   for (l = val->locs; l; l = l->next)
 279     {
 280       rtx this_rtx = l->loc;
 281       int this_cost;
 282
 283       if (CONSTANT_P (this_rtx) && ! references_value_p (this_rtx, 0))
 284         {
 285 #ifdef LOAD_EXTEND_OP
 286           if (extend_op != UNKNOWN)
 287             {
 288               HOST_WIDE_INT this_val;
 289
 290               /* ??? I'm lazy and don't wish to handle CONST_DOUBLE.  Other
 291                  constants, such as SYMBOL_REF, cannot be extended.  */
 292               if (!CONST_INT_P (this_rtx))
 293                 continue;
 294
 295               this_val = INTVAL (this_rtx);
 296               switch (extend_op)
 297                 {
 298                 case ZERO_EXTEND:
 299                   this_val &= GET_MODE_MASK (GET_MODE (src));
 300                   break;
 301                 case SIGN_EXTEND:
 302                   /* ??? In theory we're already extended.  */
 303                   if (this_val == trunc_int_for_mode (this_val, GET_MODE (src)))
 304                     break;
 305                 default:
 306                   gcc_unreachable ();
 307                 }
 308               this_rtx = GEN_INT (this_val);
 309             }
 310 #endif
 311           this_cost = rtx_cost (this_rtx, SET, speed);
 312         }
 313       else if (REG_P (this_rtx))
 314         {
 315 #ifdef LOAD_EXTEND_OP
 316           if (extend_op != UNKNOWN)
 317             {
 318               this_rtx = gen_rtx_fmt_e (extend_op, word_mode, this_rtx);
 319               this_cost = rtx_cost (this_rtx, SET, speed);
 320             }
 321           else
 322 #endif
 323             this_cost = register_move_cost (GET_MODE (this_rtx),
 324                                             REGNO_REG_CLASS (REGNO (this_rtx)),
 325                                             dclass);
 326         }
 327       else
 328         continue;
 329
 330       /* If equal costs, prefer registers over anything else.  That
 331          tends to lead to smaller instructions on some machines.  */
 332       if (this_cost < old_cost
 333           || (this_cost == old_cost
 334               && REG_P (this_rtx)
 335               && !REG_P (SET_SRC (set))))
 336         {
 337 #ifdef LOAD_EXTEND_OP
 338           if (GET_MODE_BITSIZE (GET_MODE (SET_DEST (set))) < BITS_PER_WORD
 339               && extend_op != UNKNOWN
 340 #ifdef CANNOT_CHANGE_MODE_CLASS
 341               && !CANNOT_CHANGE_MODE_CLASS (GET_MODE (SET_DEST (set)),
 342                                             word_mode,
 343                                             REGNO_REG_CLASS (REGNO (SET_DEST (set))))
 344 #endif
 345               )
 346             {
 347               rtx wide_dest = gen_rtx_REG (word_mode, REGNO (SET_DEST (set)));
 348               ORIGINAL_REGNO (wide_dest) = ORIGINAL_REGNO (SET_DEST (set));
 349               validate_change (insn, &SET_DEST (set), wide_dest, 1);
 350             }
 351 #endif
 352
 353           validate_unshare_change (insn, &SET_SRC (set), this_rtx, 1);
 354           old_cost = this_cost, did_change = 1;
 355         }
 356     }
 357
 358   return did_change;
 359 }
 360
 361 /* Try to replace operands in INSN with equivalent values that are already
 362    in registers.  This can be viewed as optional reloading.
 363
 364    For each non-register operand in the insn, see if any hard regs are
 365    known to be equivalent to that operand.  Record the alternatives which
 366    can accept these hard registers.  Among all alternatives, select the
 367    ones which are better or equal to the one currently matching, where
 368    "better" is in terms of '?' and '!' constraints.  Among the remaining
 369    alternatives, select the one which replaces most operands with
 370    hard registers.  */
 371
 372 static int
 373 reload_cse_simplify_operands (rtx insn, rtx testreg)
 374 {
 375   int i, j;
 376
 377   /* For each operand, all registers that are equivalent to it.  */
 378   HARD_REG_SET equiv_regs[MAX_RECOG_OPERANDS];
 379
 380   const char *constraints[MAX_RECOG_OPERANDS];
 381
 382   /* Vector recording how bad an alternative is.  */
 383   int *alternative_reject;
 384   /* Vector recording how many registers can be introduced by choosing
 385      this alternative.  */
 386   int *alternative_nregs;
 387   /* Array of vectors recording, for each operand and each alternative,
 388      which hard register to substitute, or -1 if the operand should be
 389      left as it is.  */
 390   int *op_alt_regno[MAX_RECOG_OPERANDS];
 391   /* Array of alternatives, sorted in order of decreasing desirability.  */
 392   int *alternative_order;
 393
 394   extract_insn (insn);
 395
 396   if (recog_data.n_alternatives == 0 || recog_data.n_operands == 0)
 397     return 0;
 398
 399   /* Figure out which alternative currently matches.  */
 400   if (! constrain_operands (1))
 401     fatal_insn_not_found (insn);
 402
 403   alternative_reject = XALLOCAVEC (int, recog_data.n_alternatives);
 404   alternative_nregs = XALLOCAVEC (int, recog_data.n_alternatives);
 405   alternative_order = XALLOCAVEC (int, recog_data.n_alternatives);
 406   memset (alternative_reject, 0, recog_data.n_alternatives * sizeof (int));
 407   memset (alternative_nregs, 0, recog_data.n_alternatives * sizeof (int));
 408
 409   /* For each operand, find out which regs are equivalent.  */
 410   for (i = 0; i < recog_data.n_operands; i++)
 411     {
 412       cselib_val *v;
 413       struct elt_loc_list *l;
 414       rtx op;
 415
 416       CLEAR_HARD_REG_SET (equiv_regs[i]);
 417
 418       /* cselib blows up on CODE_LABELs.  Trying to fix that doesn't seem
 419          right, so avoid the problem here.  Likewise if we have a constant
 420          and the insn pattern doesn't tell us the mode we need.  */
 421       if (LABEL_P (recog_data.operand[i])
 422           || (CONSTANT_P (recog_data.operand[i])
 423               && recog_data.operand_mode[i] == VOIDmode))
 424         continue;
 425
 426       op = recog_data.operand[i];
 427 #ifdef LOAD_EXTEND_OP
 428       if (MEM_P (op)
 429           && GET_MODE_BITSIZE (GET_MODE (op)) < BITS_PER_WORD
 430           && LOAD_EXTEND_OP (GET_MODE (op)) != UNKNOWN)
 431         {
 432           rtx set = single_set (insn);
 433
 434           /* We might have multiple sets, some of which do implicit
 435              extension.  Punt on this for now.  */
 436           if (! set)
 437             continue;
 438           /* If the destination is also a MEM or a STRICT_LOW_PART, no
 439              extension applies.
 440              Also, if there is an explicit extension, we don't have to
 441              worry about an implicit one.  */
 442           else if (MEM_P (SET_DEST (set))
 443                    || GET_CODE (SET_DEST (set)) == STRICT_LOW_PART
 444                    || GET_CODE (SET_SRC (set)) == ZERO_EXTEND
 445                    || GET_CODE (SET_SRC (set)) == SIGN_EXTEND)
 446             ; /* Continue ordinary processing.  */
 447 #ifdef CANNOT_CHANGE_MODE_CLASS
 448           /* If the register cannot change mode to word_mode, it follows that
 449              it cannot have been used in word_mode.  */
 450           else if (REG_P (SET_DEST (set))
 451                    && CANNOT_CHANGE_MODE_CLASS (GET_MODE (SET_DEST (set)),
 452                                                 word_mode,
 453                                                 REGNO_REG_CLASS (REGNO (SET_DEST (set)))))
 454             ; /* Continue ordinary processing.  */
 455 #endif
 456           /* If this is a straight load, make the extension explicit.  */
 457           else if (REG_P (SET_DEST (set))
 458                    && recog_data.n_operands == 2
 459                    && SET_SRC (set) == op
 460                    && SET_DEST (set) == recog_data.operand[1-i])
 461             {
 462               validate_change (insn, recog_data.operand_loc[i],
 463                                gen_rtx_fmt_e (LOAD_EXTEND_OP (GET_MODE (op)),
 464                                               word_mode, op),
 465                                1);
 466               validate_change (insn, recog_data.operand_loc[1-i],
 467                                gen_rtx_REG (word_mode, REGNO (SET_DEST (set))),
 468                                1);
 469               if (! apply_change_group ())
 470                 return 0;
 471               return reload_cse_simplify_operands (insn, testreg);
 472             }
 473           else
 474             /* ??? There might be arithmetic operations with memory that are
 475                safe to optimize, but is it worth the trouble?  */
 476             continue;
 477         }
 478 #endif /* LOAD_EXTEND_OP */
 479       v = cselib_lookup (op, recog_data.operand_mode[i], 0);
 480       if (! v)
 481         continue;
 482
 483       for (l = v->locs; l; l = l->next)
 484         if (REG_P (l->loc))
 485           SET_HARD_REG_BIT (equiv_regs[i], REGNO (l->loc));
 486     }
 487
 488   for (i = 0; i < recog_data.n_operands; i++)
 489     {
 490       enum machine_mode mode;
 491       int regno;
 492       const char *p;
 493
 494       op_alt_regno[i] = XALLOCAVEC (int, recog_data.n_alternatives);
 495       for (j = 0; j < recog_data.n_alternatives; j++)
 496         op_alt_regno[i][j] = -1;
 497
 498       p = constraints[i] = recog_data.constraints[i];
 499       mode = recog_data.operand_mode[i];
 500
 501       /* Add the reject values for each alternative given by the constraints
 502          for this operand.  */
 503       j = 0;
 504       while (*p != '\0')
 505         {
 506           char c = *p++;
 507           if (c == ',')
 508             j++;
 509           else if (c == '?')
 510             alternative_reject[j] += 3;
 511           else if (c == '!')
 512             alternative_reject[j] += 300;
 513         }
 514
 515       /* We won't change operands which are already registers.  We
 516          also don't want to modify output operands.  */
 517       regno = true_regnum (recog_data.operand[i]);
 518       if (regno >= 0
 519           || constraints[i][0] == '='
 520           || constraints[i][0] == '+')
 521         continue;
 522
 523       for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
 524         {
 525           enum reg_class rclass = NO_REGS;
 526
 527           if (! TEST_HARD_REG_BIT (equiv_regs[i], regno))
 528             continue;
 529
 530           SET_REGNO_RAW (testreg, regno);
 531           PUT_MODE (testreg, mode);
 532
 533           /* We found a register equal to this operand.  Now look for all
 534              alternatives that can accept this register and have not been
 535              assigned a register they can use yet.  */
 536           j = 0;
 537           p = constraints[i];
 538           for (;;)
 539             {
 540               char c = *p;
 541
 542               switch (c)
 543                 {
 544                 case '=':  case '+':  case '?':
 545                 case '#':  case '&':  case '!':
 546                 case '*':  case '%':
 547                 case '0':  case '1':  case '2':  case '3':  case '4':
 548                 case '5':  case '6':  case '7':  case '8':  case '9':
 549                 case '<':  case '>':  case 'V':  case 'o':
 550                 case 'E':  case 'F':  case 'G':  case 'H':
 551                 case 's':  case 'i':  case 'n':
 552                 case 'I':  case 'J':  case 'K':  case 'L':
 553                 case 'M':  case 'N':  case 'O':  case 'P':
 554                 case 'p':  case 'X':  case TARGET_MEM_CONSTRAINT:
 555                   /* These don't say anything we care about.  */
 556                   break;
 557
 558                 case 'g': case 'r':
 559                   rclass = reg_class_subunion[(int) rclass][(int) GENERAL_REGS];
 560                   break;
 561
 562                 default:
 563                   rclass
 564                     = (reg_class_subunion
 565                        [(int) rclass]
 566                        [(int) REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p)]);
 567                   break;
 568
 569                 case ',': case '\0':
 570                   /* See if REGNO fits this alternative, and set it up as the
 571                      replacement register if we don't have one for this
 572                      alternative yet and the operand being replaced is not
 573                      a cheap CONST_INT.  */
 574                   if (op_alt_regno[i][j] == -1
 575                       && recog_data.alternative_enabled_p[j]
 576                       && reg_fits_class_p (testreg, rclass, 0, mode)
 577                       && (!CONST_INT_P (recog_data.operand[i])
 578                           || (rtx_cost (recog_data.operand[i], SET,
 579                                         optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn)))
 580                               > rtx_cost (testreg, SET,
 581                                         optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn))))))
 582                     {
 583                       alternative_nregs[j]++;
 584                       op_alt_regno[i][j] = regno;
 585                     }
 586                   j++;
 587                   rclass = NO_REGS;
 588                   break;
 589                 }
 590               p += CONSTRAINT_LEN (c, p);
 591
 592               if (c == '\0')
 593                 break;
 594             }
 595         }
 596     }
 597
 598   /* Record all alternatives which are better or equal to the currently
 599      matching one in the alternative_order array.  */
 600   for (i = j = 0; i < recog_data.n_alternatives; i++)
 601     if (alternative_reject[i] <= alternative_reject[which_alternative])
 602       alternative_order[j++] = i;
 603   recog_data.n_alternatives = j;
 604
 605   /* Sort it.  Given a small number of alternatives, a dumb algorithm
 606      won't hurt too much.  */
 607   for (i = 0; i < recog_data.n_alternatives - 1; i++)
 608     {
 609       int best = i;
 610       int best_reject = alternative_reject[alternative_order[i]];
 611       int best_nregs = alternative_nregs[alternative_order[i]];
 612       int tmp;
 613
 614       for (j = i + 1; j < recog_data.n_alternatives; j++)
 615         {
 616           int this_reject = alternative_reject[alternative_order[j]];
 617           int this_nregs = alternative_nregs[alternative_order[j]];
 618
 619           if (this_reject < best_reject
 620               || (this_reject == best_reject && this_nregs > best_nregs))
 621             {
 622               best = j;
 623               best_reject = this_reject;
 624               best_nregs = this_nregs;
 625             }
 626         }
 627
 628       tmp = alternative_order[best];
 629       alternative_order[best] = alternative_order[i];
 630       alternative_order[i] = tmp;
 631     }
 632
 633   /* Substitute the operands as determined by op_alt_regno for the best
 634      alternative.  */
 635   j = alternative_order[0];
 636
 637   for (i = 0; i < recog_data.n_operands; i++)
 638     {
 639       enum machine_mode mode = recog_data.operand_mode[i];
 640       if (op_alt_regno[i][j] == -1)
 641         continue;
 642
 643       validate_change (insn, recog_data.operand_loc[i],
 644                        gen_rtx_REG (mode, op_alt_regno[i][j]), 1);
 645     }
 646
 647   for (i = recog_data.n_dups - 1; i >= 0; i--)
 648     {
 649       int op = recog_data.dup_num[i];
 650       enum machine_mode mode = recog_data.operand_mode[op];
 651
 652       if (op_alt_regno[op][j] == -1)
 653         continue;
 654
 655       validate_change (insn, recog_data.dup_loc[i],
 656                        gen_rtx_REG (mode, op_alt_regno[op][j]), 1);
 657     }
 658
 659   return apply_change_group ();
 660 }
 661 \f
 662 /* If reload couldn't use reg+reg+offset addressing, try to use reg+reg
 663    addressing now.
 664    This code might also be useful when reload gave up on reg+reg addressing
 665    because of clashes between the return register and INDEX_REG_CLASS.  */
 666
 667 /* The maximum number of uses of a register we can keep track of to
 668    replace them with reg+reg addressing.  */
 669 #define RELOAD_COMBINE_MAX_USES 16
 670
 671 /* Describes a recorded use of a register.  */
 672 struct reg_use
 673 {
 674   /* The insn where a register has been used.  */
 675   rtx insn;
 676   /* Points to the memory reference enclosing the use, if any, NULL_RTX
 677      otherwise.  */
 678   rtx containing_mem;
 679   /* Location of the register withing INSN.  */
 680   rtx *usep;
 681   /* The reverse uid of the insn.  */
 682   int ruid;
 683 };
 684
 685 /* If the register is used in some unknown fashion, USE_INDEX is negative.
 686    If it is dead, USE_INDEX is RELOAD_COMBINE_MAX_USES, and STORE_RUID
 687    indicates where it is first set or clobbered.
 688    Otherwise, USE_INDEX is the index of the last encountered use of the
 689    register (which is first among these we have seen since we scan backwards).
 690    USE_RUID indicates the first encountered, i.e. last, of these uses.
 691    If ALL_OFFSETS_MATCH is true, all encountered uses were inside a PLUS
 692    with a constant offset; OFFSET contains this constant in that case.
 693    STORE_RUID is always meaningful if we only want to use a value in a
 694    register in a different place: it denotes the next insn in the insn
 695    stream (i.e. the last encountered) that sets or clobbers the register.
 696    REAL_STORE_RUID is similar, but clobbers are ignored when updating it.  */
 697 static struct
 698   {
 699     struct reg_use reg_use[RELOAD_COMBINE_MAX_USES];
 700     rtx offset;
 701     int use_index;
 702     int store_ruid;
 703     int real_store_ruid;
 704     int use_ruid;
 705     bool all_offsets_match;
 706   } reg_state[FIRST_PSEUDO_REGISTER];
 707
 708 /* Reverse linear uid.  This is increased in reload_combine while scanning
 709    the instructions from last to first.  It is used to set last_label_ruid
 710    and the store_ruid / use_ruid fields in reg_state.  */
 711 static int reload_combine_ruid;
 712
 713 /* The RUID of the last label we encountered in reload_combine.  */
 714 static int last_label_ruid;
 715
 716 /* The RUID of the last jump we encountered in reload_combine.  */
 717 static int last_jump_ruid;
 718
 719 /* The register numbers of the first and last index register.  A value of
 720    -1 in LAST_INDEX_REG indicates that we've previously computed these
 721    values and found no suitable index registers.  */
 722 static int first_index_reg = -1;
 723 static int last_index_reg;
 724
 725 #define LABEL_LIVE(LABEL) \
 726   (label_live[CODE_LABEL_NUMBER (LABEL) - min_labelno])
 727
 728 /* Subroutine of reload_combine_split_ruids, called to fix up a single
 729    ruid pointed to by *PRUID if it is higher than SPLIT_RUID.  */
 730
 731 static inline void
 732 reload_combine_split_one_ruid (int *pruid, int split_ruid)
 733 {
 734   if (*pruid > split_ruid)
 735     (*pruid)++;
 736 }
 737
 738 /* Called when we insert a new insn in a position we've already passed in
 739    the scan.  Examine all our state, increasing all ruids that are higher
 740    than SPLIT_RUID by one in order to make room for a new insn.  */
 741
 742 static void
 743 reload_combine_split_ruids (int split_ruid)
 744 {
 745   unsigned i;
 746
 747   reload_combine_split_one_ruid (&reload_combine_ruid, split_ruid);
 748   reload_combine_split_one_ruid (&last_label_ruid, split_ruid);
 749   reload_combine_split_one_ruid (&last_jump_ruid, split_ruid);
 750
 751   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 752     {
 753       int j, idx = reg_state[i].use_index;
 754       reload_combine_split_one_ruid (&reg_state[i].use_ruid, split_ruid);
 755       reload_combine_split_one_ruid (&reg_state[i].store_ruid, split_ruid);
 756       reload_combine_split_one_ruid (&reg_state[i].real_store_ruid,
 757                                      split_ruid);
 758       if (idx < 0)
 759         continue;
 760       for (j = idx; j < RELOAD_COMBINE_MAX_USES; j++)
 761         {
 762           reload_combine_split_one_ruid (&reg_state[i].reg_use[j].ruid,
 763                                          split_ruid);
 764         }
 765     }
 766 }
 767
 768 /* Called when we are about to rescan a previously encountered insn with
 769    reload_combine_note_use after modifying some part of it.  This clears all
 770    information about uses in that particular insn.  */
 771
 772 static void
 773 reload_combine_purge_insn_uses (rtx insn)
 774 {
 775   unsigned i;
 776
 777   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 778     {
 779       int j, k, idx = reg_state[i].use_index;
 780       if (idx < 0)
 781         continue;
 782       j = k = RELOAD_COMBINE_MAX_USES;
 783       while (j-- > idx)
 784         {
 785           if (reg_state[i].reg_use[j].insn != insn)
 786             {
 787               k--;
 788               if (k != j)
 789                 reg_state[i].reg_use[k] = reg_state[i].reg_use[j];
 790             }
 791         }
 792       reg_state[i].use_index = k;
 793     }
 794 }
 795
 796 /* Called when we need to forget about all uses of REGNO after an insn
 797    which is identified by RUID.  */
 798
 799 static void
 800 reload_combine_purge_reg_uses_after_ruid (unsigned regno, int ruid)
 801 {
 802   int j, k, idx = reg_state[regno].use_index;
 803   if (idx < 0)
 804     return;
 805   j = k = RELOAD_COMBINE_MAX_USES;
 806   while (j-- > idx)
 807     {
 808       if (reg_state[regno].reg_use[j].ruid >= ruid)
 809         {
 810           k--;
 811           if (k != j)
 812             reg_state[regno].reg_use[k] = reg_state[regno].reg_use[j];
 813         }
 814     }
 815   reg_state[regno].use_index = k;
 816 }
 817
 818 /* Find the use of REGNO with the ruid that is highest among those
 819    lower than RUID_LIMIT, and return it if it is the only use of this
 820    reg in the insn.  Return NULL otherwise.  */
 821
 822 static struct reg_use *
 823 reload_combine_closest_single_use (unsigned regno, int ruid_limit)
 824 {
 825   int i, best_ruid = 0;
 826   int use_idx = reg_state[regno].use_index;
 827   struct reg_use *retval;
 828
 829   if (use_idx < 0)
 830     return NULL;
 831   retval = NULL;
 832   for (i = use_idx; i < RELOAD_COMBINE_MAX_USES; i++)
 833     {
 834       struct reg_use *use = reg_state[regno].reg_use + i;
 835       int this_ruid = use->ruid;
 836       if (this_ruid >= ruid_limit)
 837         continue;
 838       if (this_ruid > best_ruid)
 839         {
 840           best_ruid = this_ruid;
 841           retval = use;
 842         }
 843       else if (this_ruid == best_ruid)
 844         retval = NULL;
 845     }
 846   if (last_label_ruid >= best_ruid)
 847     return NULL;
 848   return retval;
 849 }
 850
 851 /* After we've moved an add insn, fix up any debug insns that occur
 852    between the old location of the add and the new location.  REG is
 853    the destination register of the add insn; REPLACEMENT is the
 854    SET_SRC of the add.  FROM and TO specify the range in which we
 855    should make this change on debug insns.  */
 856
 857 static void
 858 fixup_debug_insns (rtx reg, rtx replacement, rtx from, rtx to)
 859 {
 860   rtx insn;
 861   for (insn = from; insn != to; insn = NEXT_INSN (insn))
 862     {
 863       rtx t;
 864
 865       if (!DEBUG_INSN_P (insn))
 866         continue;
 867
 868       t = INSN_VAR_LOCATION_LOC (insn);
 869       t = simplify_replace_rtx (t, reg, replacement);
 870       validate_change (insn, &INSN_VAR_LOCATION_LOC (insn), t, 0);
 871     }
 872 }
 873
 874 /* Subroutine of reload_combine_recognize_const_pattern.  Try to replace REG
 875    with SRC in the insn described by USE, taking costs into account.  Return
 876    true if we made the replacement.  */
 877
 878 static bool
 879 try_replace_in_use (struct reg_use *use, rtx reg, rtx src)
 880 {
 881   rtx use_insn = use->insn;
 882   rtx mem = use->containing_mem;
 883   bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
 884
 885   if (mem != NULL_RTX)
 886     {
 887       addr_space_t as = MEM_ADDR_SPACE (mem);
 888       rtx oldaddr = XEXP (mem, 0);
 889       rtx newaddr = NULL_RTX;
 890       int old_cost = address_cost (oldaddr, GET_MODE (mem), as, speed);
 891       int new_cost;
 892
 893       newaddr = simplify_replace_rtx (oldaddr, reg, src);
 894       if (memory_address_addr_space_p (GET_MODE (mem), newaddr, as))
 895         {
 896           XEXP (mem, 0) = newaddr;
 897           new_cost = address_cost (newaddr, GET_MODE (mem), as, speed);
 898           XEXP (mem, 0) = oldaddr;
 899           if (new_cost <= old_cost
 900               && validate_change (use_insn,
 901                                   &XEXP (mem, 0), newaddr, 0))
 902             return true;
 903         }
 904     }
 905   else
 906     {
 907       rtx new_set = single_set (use_insn);
 908       if (new_set
 909           && REG_P (SET_DEST (new_set))
 910           && GET_CODE (SET_SRC (new_set)) == PLUS
 911           && REG_P (XEXP (SET_SRC (new_set), 0))
 912           && CONSTANT_P (XEXP (SET_SRC (new_set), 1)))
 913         {
 914           rtx new_src;
 915           int old_cost = rtx_cost (SET_SRC (new_set), SET, speed);
 916
 917           gcc_assert (rtx_equal_p (XEXP (SET_SRC (new_set), 0), reg));
 918           new_src = simplify_replace_rtx (SET_SRC (new_set), reg, src);
 919
 920           if (rtx_cost (new_src, SET, speed) <= old_cost
 921               && validate_change (use_insn, &SET_SRC (new_set),
 922                                   new_src, 0))
 923             return true;
 924         }
 925     }
 926   return false;
 927 }
 928
 929 /* Called by reload_combine when scanning INSN.  This function tries to detect
 930    patterns where a constant is added to a register, and the result is used
 931    in an address.
 932    Return true if no further processing is needed on INSN; false if it wasn't
 933    recognized and should be handled normally.  */
 934
 935 static bool
 936 reload_combine_recognize_const_pattern (rtx insn)
 937 {
 938   int from_ruid = reload_combine_ruid;
 939   rtx set, pat, reg, src, addreg;
 940   unsigned int regno;
 941   struct reg_use *use;
 942   bool must_move_add;
 943   rtx add_moved_after_insn = NULL_RTX;
 944   int add_moved_after_ruid = 0;
 945   int clobbered_regno = -1;
 946
 947   set = single_set (insn);
 948   if (set == NULL_RTX)
 949     return false;
 950
 951   reg = SET_DEST (set);
 952   src = SET_SRC (set);
 953   if (!REG_P (reg)
 954       || hard_regno_nregs[REGNO (reg)][GET_MODE (reg)] != 1
 955       || GET_MODE (reg) != Pmode
 956       || reg == stack_pointer_rtx)
 957     return false;
 958
 959   regno = REGNO (reg);
 960
 961   /* We look for a REG1 = REG2 + CONSTANT insn, followed by either
 962      uses of REG1 inside an address, or inside another add insn.  If
 963      possible and profitable, merge the addition into subsequent
 964      uses.  */
 965   if (GET_CODE (src) != PLUS
 966       || !REG_P (XEXP (src, 0))
 967       || !CONSTANT_P (XEXP (src, 1)))
 968     return false;
 969
 970   addreg = XEXP (src, 0);
 971   must_move_add = rtx_equal_p (reg, addreg);
 972
 973   pat = PATTERN (insn);
 974   if (must_move_add && set != pat)
 975     {
 976       /* We have to be careful when moving the add; apart from the
 977          single_set there may also be clobbers.  Recognize one special
 978          case, that of one clobber alongside the set (likely a clobber
 979          of the CC register).  */
 980       gcc_assert (GET_CODE (PATTERN (insn)) == PARALLEL);
 981       if (XVECLEN (pat, 0) != 2 || XVECEXP (pat, 0, 0) != set
 982           || GET_CODE (XVECEXP (pat, 0, 1)) != CLOBBER
 983           || !REG_P (XEXP (XVECEXP (pat, 0, 1), 0)))
 984         return false;
 985       clobbered_regno = REGNO (XEXP (XVECEXP (pat, 0, 1), 0));
 986     }
 987
 988   do
 989     {
 990       use = reload_combine_closest_single_use (regno, from_ruid);
 991
 992       if (use)
 993         /* Start the search for the next use from here.  */
 994         from_ruid = use->ruid;
 995
 996       if (use && GET_MODE (*use->usep) == Pmode)
 997         {
 998           bool delete_add = false;
 999           rtx use_insn = use->insn;
1000           int use_ruid = use->ruid;
1001
1002           /* Avoid moving the add insn past a jump.  */
1003           if (must_move_add && use_ruid <= last_jump_ruid)
1004             break;
1005
1006           /* If the add clobbers another hard reg in parallel, don't move
1007              it past a real set of this hard reg.  */
1008           if (must_move_add && clobbered_regno >= 0
1009               && reg_state[clobbered_regno].real_store_ruid >= use_ruid)
1010             break;
1011
1012           gcc_assert (reg_state[regno].store_ruid <= use_ruid);
1013           /* Avoid moving a use of ADDREG past a point where it is stored.  */
1014           if (reg_state[REGNO (addreg)].store_ruid > use_ruid)
1015             break;
1016
1017           /* We also must not move the addition past an insn that sets
1018              the same register, unless we can combine two add insns.  */
1019           if (must_move_add && reg_state[regno].store_ruid == use_ruid)
1020             {
1021               if (use->containing_mem == NULL_RTX)
1022                 delete_add = true;
1023               else
1024                 break;
1025             }
1026
1027           if (try_replace_in_use (use, reg, src))
1028             {
1029               reload_combine_purge_insn_uses (use_insn);
1030               reload_combine_note_use (&PATTERN (use_insn), use_insn,
1031                                        use_ruid, NULL_RTX);
1032
1033               if (delete_add)
1034                 {
1035                   fixup_debug_insns (reg, src, insn, use_insn);
1036                   delete_insn (insn);
1037                   return true;
1038                 }
1039               if (must_move_add)
1040                 {
1041                   add_moved_after_insn = use_insn;
1042                   add_moved_after_ruid = use_ruid;
1043                 }
1044               continue;
1045             }
1046         }
1047       /* If we get here, we couldn't handle this use.  */
1048       if (must_move_add)
1049         break;
1050     }
1051   while (use);
1052
1053   if (!must_move_add || add_moved_after_insn == NULL_RTX)
1054     /* Process the add normally.  */
1055     return false;
1056
1057   fixup_debug_insns (reg, src, insn, add_moved_after_insn);
1058
1059   reorder_insns (insn, insn, add_moved_after_insn);
1060   reload_combine_purge_reg_uses_after_ruid (regno, add_moved_after_ruid);
1061   reload_combine_split_ruids (add_moved_after_ruid - 1);
1062   reload_combine_note_use (&PATTERN (insn), insn,
1063                            add_moved_after_ruid, NULL_RTX);
1064   reg_state[regno].store_ruid = add_moved_after_ruid;
1065
1066   return true;
1067 }
1068
1069 /* Called by reload_combine when scanning INSN.  Try to detect a pattern we
1070    can handle and improve.  Return true if no further processing is needed on
1071    INSN; false if it wasn't recognized and should be handled normally.  */
1072
1073 static bool
1074 reload_combine_recognize_pattern (rtx insn)
1075 {
1076   rtx set, reg, src;
1077   unsigned int regno;
1078
1079   set = single_set (insn);
1080   if (set == NULL_RTX)
1081     return false;
1082
1083   reg = SET_DEST (set);
1084   src = SET_SRC (set);
1085   if (!REG_P (reg)
1086       || hard_regno_nregs[REGNO (reg)][GET_MODE (reg)] != 1)
1087     return false;
1088
1089   regno = REGNO (reg);
1090
1091   /* Look for (set (REGX) (CONST_INT))
1092      (set (REGX) (PLUS (REGX) (REGY)))
1093      ...
1094      ... (MEM (REGX)) ...
1095      and convert it to
1096      (set (REGZ) (CONST_INT))
1097      ...
1098      ... (MEM (PLUS (REGZ) (REGY)))... .
1099
1100      First, check that we have (set (REGX) (PLUS (REGX) (REGY)))
1101      and that we know all uses of REGX before it dies.
1102      Also, explicitly check that REGX != REGY; our life information
1103      does not yet show whether REGY changes in this insn.  */
1104
1105   if (GET_CODE (src) == PLUS
1106       && reg_state[regno].all_offsets_match
1107       && last_index_reg != -1
1108       && REG_P (XEXP (src, 1))
1109       && rtx_equal_p (XEXP (src, 0), reg)
1110       && !rtx_equal_p (XEXP (src, 1), reg)
1111       && reg_state[regno].use_index >= 0
1112       && reg_state[regno].use_index < RELOAD_COMBINE_MAX_USES
1113       && last_label_ruid < reg_state[regno].use_ruid)
1114     {
1115       rtx base = XEXP (src, 1);
1116       rtx prev = prev_nonnote_nondebug_insn (insn);
1117       rtx prev_set = prev ? single_set (prev) : NULL_RTX;
1118       rtx index_reg = NULL_RTX;
1119       rtx reg_sum = NULL_RTX;
1120       int i;
1121
1122       /* Now we need to set INDEX_REG to an index register (denoted as
1123          REGZ in the illustration above) and REG_SUM to the expression
1124          register+register that we want to use to substitute uses of REG
1125          (typically in MEMs) with.  First check REG and BASE for being
1126          index registers; we can use them even if they are not dead.  */
1127       if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], regno)
1128           || TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS],
1129                                 REGNO (base)))
1130         {
1131           index_reg = reg;
1132           reg_sum = src;
1133         }
1134       else
1135         {
1136           /* Otherwise, look for a free index register.  Since we have
1137              checked above that neither REG nor BASE are index registers,
1138              if we find anything at all, it will be different from these
1139              two registers.  */
1140           for (i = first_index_reg; i <= last_index_reg; i++)
1141             {
1142               if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], i)
1143                   && reg_state[i].use_index == RELOAD_COMBINE_MAX_USES
1144                   && reg_state[i].store_ruid <= reg_state[regno].use_ruid
1145                   && (call_used_regs[i] || df_regs_ever_live_p (i))
1146                   && (!frame_pointer_needed || i != HARD_FRAME_POINTER_REGNUM)
1147                   && !fixed_regs[i] && !global_regs[i]
1148                   && hard_regno_nregs[i][GET_MODE (reg)] == 1
1149                   && targetm.hard_regno_scratch_ok (i))
1150                 {
1151                   index_reg = gen_rtx_REG (GET_MODE (reg), i);
1152                   reg_sum = gen_rtx_PLUS (GET_MODE (reg), index_reg, base);
1153                   break;
1154                 }
1155             }
1156         }
1157
1158       /* Check that PREV_SET is indeed (set (REGX) (CONST_INT)) and that
1159          (REGY), i.e. BASE, is not clobbered before the last use we'll
1160          create.  */
1161       if (reg_sum
1162           && prev_set
1163           && CONST_INT_P (SET_SRC (prev_set))
1164           && rtx_equal_p (SET_DEST (prev_set), reg)
1165           && (reg_state[REGNO (base)].store_ruid
1166               <= reg_state[regno].use_ruid))
1167         {
1168           /* Change destination register and, if necessary, the constant
1169              value in PREV, the constant loading instruction.  */
1170           validate_change (prev, &SET_DEST (prev_set), index_reg, 1);
1171           if (reg_state[regno].offset != const0_rtx)
1172             validate_change (prev,
1173                              &SET_SRC (prev_set),
1174                              GEN_INT (INTVAL (SET_SRC (prev_set))
1175                                       + INTVAL (reg_state[regno].offset)),
1176                              1);
1177
1178           /* Now for every use of REG that we have recorded, replace REG
1179              with REG_SUM.  */
1180           for (i = reg_state[regno].use_index;
1181                i < RELOAD_COMBINE_MAX_USES; i++)
1182             validate_unshare_change (reg_state[regno].reg_use[i].insn,
1183                                      reg_state[regno].reg_use[i].usep,
1184                                      /* Each change must have its own
1185                                         replacement.  */
1186                                      reg_sum, 1);
1187
1188           if (apply_change_group ())
1189             {
1190               struct reg_use *lowest_ruid = NULL;
1191
1192               /* For every new use of REG_SUM, we have to record the use
1193                  of BASE therein, i.e. operand 1.  */
1194               for (i = reg_state[regno].use_index;
1195                    i < RELOAD_COMBINE_MAX_USES; i++)
1196                 {
1197                   struct reg_use *use = reg_state[regno].reg_use + i;
1198                   reload_combine_note_use (&XEXP (*use->usep, 1), use->insn,
1199                                            use->ruid, use->containing_mem);
1200                   if (lowest_ruid == NULL || use->ruid < lowest_ruid->ruid)
1201                     lowest_ruid = use;
1202                 }
1203
1204               fixup_debug_insns (reg, reg_sum, insn, lowest_ruid->insn);
1205
1206               /* Delete the reg-reg addition.  */
1207               delete_insn (insn);
1208
1209               if (reg_state[regno].offset != const0_rtx)
1210                 /* Previous REG_EQUIV / REG_EQUAL notes for PREV
1211                    are now invalid.  */
1212                 remove_reg_equal_equiv_notes (prev);
1213
1214               reg_state[regno].use_index = RELOAD_COMBINE_MAX_USES;
1215               return true;
1216             }
1217         }
1218     }
1219   return false;
1220 }
1221
1222 static void
1223 reload_combine (void)
1224 {
1225   rtx insn, prev;
1226   basic_block bb;
1227   unsigned int r;
1228   int min_labelno, n_labels;
1229   HARD_REG_SET ever_live_at_start, *label_live;
1230
1231   /* To avoid wasting too much time later searching for an index register,
1232      determine the minimum and maximum index register numbers.  */
1233   if (INDEX_REG_CLASS == NO_REGS)
1234     last_index_reg = -1;
1235   else if (first_index_reg == -1 && last_index_reg == 0)
1236     {
1237       for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1238         if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], r))
1239           {
1240             if (first_index_reg == -1)
1241               first_index_reg = r;
1242
1243             last_index_reg = r;
1244           }
1245
1246       /* If no index register is available, we can quit now.  Set LAST_INDEX_REG
1247          to -1 so we'll know to quit early the next time we get here.  */
1248       if (first_index_reg == -1)
1249         {
1250           last_index_reg = -1;
1251           return;
1252         }
1253     }
1254
1255   /* Set up LABEL_LIVE and EVER_LIVE_AT_START.  The register lifetime
1256      information is a bit fuzzy immediately after reload, but it's
1257      still good enough to determine which registers are live at a jump
1258      destination.  */
1259   min_labelno = get_first_label_num ();
1260   n_labels = max_label_num () - min_labelno;
1261   label_live = XNEWVEC (HARD_REG_SET, n_labels);
1262   CLEAR_HARD_REG_SET (ever_live_at_start);
1263
1264   FOR_EACH_BB_REVERSE (bb)
1265     {
1266       insn = BB_HEAD (bb);
1267       if (LABEL_P (insn))
1268         {
1269           HARD_REG_SET live;
1270           bitmap live_in = df_get_live_in (bb);
1271
1272           REG_SET_TO_HARD_REG_SET (live, live_in);
1273           compute_use_by_pseudos (&live, live_in);
1274           COPY_HARD_REG_SET (LABEL_LIVE (insn), live);
1275           IOR_HARD_REG_SET (ever_live_at_start, live);
1276         }
1277     }
1278
1279   /* Initialize last_label_ruid, reload_combine_ruid and reg_state.  */
1280   last_label_ruid = last_jump_ruid = reload_combine_ruid = 0;
1281   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1282     {
1283       reg_state[r].store_ruid = 0;
1284       reg_state[r].real_store_ruid = 0;
1285       if (fixed_regs[r])
1286         reg_state[r].use_index = -1;
1287       else
1288         reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
1289     }
1290
1291   for (insn = get_last_insn (); insn; insn = prev)
1292     {
1293       bool control_flow_insn;
1294       rtx note;
1295
1296       prev = PREV_INSN (insn);
1297
1298       /* We cannot do our optimization across labels.  Invalidating all the use
1299          information we have would be costly, so we just note where the label
1300          is and then later disable any optimization that would cross it.  */
1301       if (LABEL_P (insn))
1302         last_label_ruid = reload_combine_ruid;
1303       else if (BARRIER_P (insn))
1304         for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1305           if (! fixed_regs[r])
1306               reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
1307
1308       if (! NONDEBUG_INSN_P (insn))
1309         continue;
1310
1311       reload_combine_ruid++;
1312
1313       control_flow_insn = control_flow_insn_p (insn);
1314       if (control_flow_insn)
1315         last_jump_ruid = reload_combine_ruid;
1316
1317       if (reload_combine_recognize_const_pattern (insn)
1318           || reload_combine_recognize_pattern (insn))
1319         continue;
1320
1321       note_stores (PATTERN (insn), reload_combine_note_store, NULL);
1322
1323       if (CALL_P (insn))
1324         {
1325           rtx link;
1326
1327           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1328             if (call_used_regs[r])
1329               {
1330                 reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
1331                 reg_state[r].store_ruid = reload_combine_ruid;
1332               }
1333
1334           for (link = CALL_INSN_FUNCTION_USAGE (insn); link;
1335                link = XEXP (link, 1))
1336             {
1337               rtx usage_rtx = XEXP (XEXP (link, 0), 0);
1338               if (REG_P (usage_rtx))
1339                 {
1340                   unsigned int i;
1341                   unsigned int start_reg = REGNO (usage_rtx);
1342                   unsigned int num_regs
1343                     = hard_regno_nregs[start_reg][GET_MODE (usage_rtx)];
1344                   unsigned int end_reg = start_reg + num_regs - 1;
1345                   for (i = start_reg; i <= end_reg; i++)
1346                     if (GET_CODE (XEXP (link, 0)) == CLOBBER)
1347                       {
1348                         reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
1349                         reg_state[i].store_ruid = reload_combine_ruid;
1350                       }
1351                     else
1352                       reg_state[i].use_index = -1;
1353                  }
1354              }
1355         }
1356
1357       if (control_flow_insn && GET_CODE (PATTERN (insn)) != RETURN)
1358         {
1359           /* Non-spill registers might be used at the call destination in
1360              some unknown fashion, so we have to mark the unknown use.  */
1361           HARD_REG_SET *live;
1362
1363           if ((condjump_p (insn) || condjump_in_parallel_p (insn))
1364               && JUMP_LABEL (insn))
1365             live = &LABEL_LIVE (JUMP_LABEL (insn));
1366           else
1367             live = &ever_live_at_start;
1368
1369           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1370             if (TEST_HARD_REG_BIT (*live, r))
1371               reg_state[r].use_index = -1;
1372         }
1373
1374       reload_combine_note_use (&PATTERN (insn), insn, reload_combine_ruid,
1375                                NULL_RTX);
1376
1377       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1378         {
1379           if (REG_NOTE_KIND (note) == REG_INC && REG_P (XEXP (note, 0)))
1380             {
1381               int regno = REGNO (XEXP (note, 0));
1382               reg_state[regno].store_ruid = reload_combine_ruid;
1383               reg_state[regno].real_store_ruid = reload_combine_ruid;
1384               reg_state[regno].use_index = -1;
1385             }
1386         }
1387     }
1388
1389   free (label_live);
1390 }
1391
1392 /* Check if DST is a register or a subreg of a register; if it is,
1393    update store_ruid, real_store_ruid and use_index in the reg_state
1394    structure accordingly.  Called via note_stores from reload_combine.  */
1395
1396 static void
1397 reload_combine_note_store (rtx dst, const_rtx set, void *data ATTRIBUTE_UNUSED)
1398 {
1399   int regno = 0;
1400   int i;
1401   enum machine_mode mode = GET_MODE (dst);
1402
1403   if (GET_CODE (dst) == SUBREG)
1404     {
1405       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
1406                                    GET_MODE (SUBREG_REG (dst)),
1407                                    SUBREG_BYTE (dst),
1408                                    GET_MODE (dst));
1409       dst = SUBREG_REG (dst);
1410     }
1411
1412   /* Some targets do argument pushes without adding REG_INC notes.  */
1413
1414   if (MEM_P (dst))
1415     {
1416       dst = XEXP (dst, 0);
1417       if (GET_CODE (dst) == PRE_INC || GET_CODE (dst) == POST_INC
1418           || GET_CODE (dst) == PRE_DEC || GET_CODE (dst) == POST_DEC)
1419         {
1420           regno = REGNO (XEXP (dst, 0));
1421           mode = GET_MODE (XEXP (dst, 0));
1422           for (i = hard_regno_nregs[regno][mode] - 1 + regno; i >= regno; i--)
1423             {
1424               /* We could probably do better, but for now mark the register
1425                  as used in an unknown fashion and set/clobbered at this
1426                  insn.  */
1427               reg_state[i].use_index = -1;
1428               reg_state[i].store_ruid = reload_combine_ruid;
1429               reg_state[i].real_store_ruid = reload_combine_ruid;
1430             }
1431         }
1432       else
1433         return;
1434     }
1435
1436   if (!REG_P (dst))
1437     return;
1438   regno += REGNO (dst);
1439
1440   /* note_stores might have stripped a STRICT_LOW_PART, so we have to be
1441      careful with registers / register parts that are not full words.
1442      Similarly for ZERO_EXTRACT.  */
1443   if (GET_CODE (SET_DEST (set)) == ZERO_EXTRACT
1444       || GET_CODE (SET_DEST (set)) == STRICT_LOW_PART)
1445     {
1446       for (i = hard_regno_nregs[regno][mode] - 1 + regno; i >= regno; i--)
1447         {
1448           reg_state[i].use_index = -1;
1449           reg_state[i].store_ruid = reload_combine_ruid;
1450           reg_state[i].real_store_ruid = reload_combine_ruid;
1451         }
1452     }
1453   else
1454     {
1455       for (i = hard_regno_nregs[regno][mode] - 1 + regno; i >= regno; i--)
1456         {
1457           reg_state[i].store_ruid = reload_combine_ruid;
1458           if (GET_CODE (set) == SET)
1459             reg_state[i].real_store_ruid = reload_combine_ruid;
1460           reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
1461         }
1462     }
1463 }
1464
1465 /* XP points to a piece of rtl that has to be checked for any uses of
1466    registers.
1467    *XP is the pattern of INSN, or a part of it.
1468    Called from reload_combine, and recursively by itself.  */
1469 static void
1470 reload_combine_note_use (rtx *xp, rtx insn, int ruid, rtx containing_mem)
1471 {
1472   rtx x = *xp;
1473   enum rtx_code code = x->code;
1474   const char *fmt;
1475   int i, j;
1476   rtx offset = const0_rtx; /* For the REG case below.  */
1477
1478   switch (code)
1479     {
1480     case SET:
1481       if (REG_P (SET_DEST (x)))
1482         {
1483           reload_combine_note_use (&SET_SRC (x), insn, ruid, NULL_RTX);
1484           return;
1485         }
1486       break;
1487
1488     case USE:
1489       /* If this is the USE of a return value, we can't change it.  */
1490       if (REG_P (XEXP (x, 0)) && REG_FUNCTION_VALUE_P (XEXP (x, 0)))
1491         {
1492         /* Mark the return register as used in an unknown fashion.  */
1493           rtx reg = XEXP (x, 0);
1494           int regno = REGNO (reg);
1495           int nregs = hard_regno_nregs[regno][GET_MODE (reg)];
1496
1497           while (--nregs >= 0)
1498             reg_state[regno + nregs].use_index = -1;
1499           return;
1500         }
1501       break;
1502
1503     case CLOBBER:
1504       if (REG_P (SET_DEST (x)))
1505         {
1506           /* No spurious CLOBBERs of pseudo registers may remain.  */
1507           gcc_assert (REGNO (SET_DEST (x)) < FIRST_PSEUDO_REGISTER);
1508           return;
1509         }
1510       break;
1511
1512     case PLUS:
1513       /* We are interested in (plus (reg) (const_int)) .  */
1514       if (!REG_P (XEXP (x, 0))
1515           || !CONST_INT_P (XEXP (x, 1)))
1516         break;
1517       offset = XEXP (x, 1);
1518       x = XEXP (x, 0);
1519       /* Fall through.  */
1520     case REG:
1521       {
1522         int regno = REGNO (x);
1523         int use_index;
1524         int nregs;
1525
1526         /* No spurious USEs of pseudo registers may remain.  */
1527         gcc_assert (regno < FIRST_PSEUDO_REGISTER);
1528
1529         nregs = hard_regno_nregs[regno][GET_MODE (x)];
1530
1531         /* We can't substitute into multi-hard-reg uses.  */
1532         if (nregs > 1)
1533           {
1534             while (--nregs >= 0)
1535               reg_state[regno + nregs].use_index = -1;
1536             return;
1537           }
1538
1539         /* We may be called to update uses in previously seen insns.
1540            Don't add uses beyond the last store we saw.  */
1541         if (ruid < reg_state[regno].store_ruid)
1542           return;
1543
1544         /* If this register is already used in some unknown fashion, we
1545            can't do anything.
1546            If we decrement the index from zero to -1, we can't store more
1547            uses, so this register becomes used in an unknown fashion.  */
1548         use_index = --reg_state[regno].use_index;
1549         if (use_index < 0)
1550           return;
1551
1552         if (use_index == RELOAD_COMBINE_MAX_USES - 1)
1553           {
1554             /* This is the first use of this register we have seen since we
1555                marked it as dead.  */
1556             reg_state[regno].offset = offset;
1557             reg_state[regno].all_offsets_match = true;
1558             reg_state[regno].use_ruid = ruid;
1559           }
1560         else
1561           {
1562             if (reg_state[regno].use_ruid > ruid)
1563               reg_state[regno].use_ruid = ruid;
1564
1565             if (! rtx_equal_p (offset, reg_state[regno].offset))
1566               reg_state[regno].all_offsets_match = false;
1567           }
1568
1569         reg_state[regno].reg_use[use_index].insn = insn;
1570         reg_state[regno].reg_use[use_index].ruid = ruid;
1571         reg_state[regno].reg_use[use_index].containing_mem = containing_mem;
1572         reg_state[regno].reg_use[use_index].usep = xp;
1573         return;
1574       }
1575
1576     case MEM:
1577       containing_mem = x;
1578       break;
1579
1580     default:
1581       break;
1582     }
1583
1584   /* Recursively process the components of X.  */
1585   fmt = GET_RTX_FORMAT (code);
1586   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1587     {
1588       if (fmt[i] == 'e')
1589         reload_combine_note_use (&XEXP (x, i), insn, ruid, containing_mem);
1590       else if (fmt[i] == 'E')
1591         {
1592           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1593             reload_combine_note_use (&XVECEXP (x, i, j), insn, ruid,
1594                                      containing_mem);
1595         }
1596     }
1597 }
1598 \f
1599 /* See if we can reduce the cost of a constant by replacing a move
1600    with an add.  We track situations in which a register is set to a
1601    constant or to a register plus a constant.  */
1602 /* We cannot do our optimization across labels.  Invalidating all the
1603    information about register contents we have would be costly, so we
1604    use move2add_last_label_luid to note where the label is and then
1605    later disable any optimization that would cross it.
1606    reg_offset[n] / reg_base_reg[n] / reg_symbol_ref[n] / reg_mode[n]
1607    are only valid if reg_set_luid[n] is greater than
1608    move2add_last_label_luid.  */
1609 static int reg_set_luid[FIRST_PSEUDO_REGISTER];
1610
1611 /* If reg_base_reg[n] is negative, register n has been set to
1612    reg_offset[n] or reg_symbol_ref[n] + reg_offset[n] in mode reg_mode[n].
1613    If reg_base_reg[n] is non-negative, register n has been set to the
1614    sum of reg_offset[n] and the value of register reg_base_reg[n]
1615    before reg_set_luid[n], calculated in mode reg_mode[n] .  */
1616 static HOST_WIDE_INT reg_offset[FIRST_PSEUDO_REGISTER];
1617 static int reg_base_reg[FIRST_PSEUDO_REGISTER];
1618 static rtx reg_symbol_ref[FIRST_PSEUDO_REGISTER];
1619 static enum machine_mode reg_mode[FIRST_PSEUDO_REGISTER];
1620
1621 /* move2add_luid is linearly increased while scanning the instructions
1622    from first to last.  It is used to set reg_set_luid in
1623    reload_cse_move2add and move2add_note_store.  */
1624 static int move2add_luid;
1625
1626 /* move2add_last_label_luid is set whenever a label is found.  Labels
1627    invalidate all previously collected reg_offset data.  */
1628 static int move2add_last_label_luid;
1629
1630 /* ??? We don't know how zero / sign extension is handled, hence we
1631    can't go from a narrower to a wider mode.  */
1632 #define MODES_OK_FOR_MOVE2ADD(OUTMODE, INMODE) \
1633   (GET_MODE_SIZE (OUTMODE) == GET_MODE_SIZE (INMODE) \
1634    || (GET_MODE_SIZE (OUTMODE) <= GET_MODE_SIZE (INMODE) \
1635        && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (OUTMODE), \
1636                                  GET_MODE_BITSIZE (INMODE))))
1637
1638 /* This function is called with INSN that sets REG to (SYM + OFF),
1639    while REG is known to already have value (SYM + offset).
1640    This function tries to change INSN into an add instruction
1641    (set (REG) (plus (REG) (OFF - offset))) using the known value.
1642    It also updates the information about REG's known value.
1643    Return true if we made a change.  */
1644
1645 static bool
1646 move2add_use_add2_insn (rtx reg, rtx sym, rtx off, rtx insn)
1647 {
1648   rtx pat = PATTERN (insn);
1649   rtx src = SET_SRC (pat);
1650   int regno = REGNO (reg);
1651   rtx new_src = gen_int_mode (INTVAL (off) - reg_offset[regno],
1652                               GET_MODE (reg));
1653   bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
1654   bool changed = false;
1655
1656   /* (set (reg) (plus (reg) (const_int 0))) is not canonical;
1657      use (set (reg) (reg)) instead.
1658      We don't delete this insn, nor do we convert it into a
1659      note, to avoid losing register notes or the return
1660      value flag.  jump2 already knows how to get rid of
1661      no-op moves.  */
1662   if (new_src == const0_rtx)
1663     {
1664       /* If the constants are different, this is a
1665          truncation, that, if turned into (set (reg)
1666          (reg)), would be discarded.  Maybe we should
1667          try a truncMN pattern?  */
1668       if (INTVAL (off) == reg_offset [regno])
1669         changed = validate_change (insn, &SET_SRC (pat), reg, 0);
1670     }
1671   else
1672     {
1673       struct full_rtx_costs oldcst, newcst;
1674       rtx tem = gen_rtx_PLUS (GET_MODE (reg), reg, new_src);
1675
1676       get_full_rtx_cost (pat, SET, &oldcst);
1677       SET_SRC (pat) = tem;
1678       get_full_rtx_cost (pat, SET, &newcst);
1679       SET_SRC (pat) = src;
1680
1681       if (costs_lt_p (&newcst, &oldcst, speed)
1682           && have_add2_insn (reg, new_src))
1683         changed = validate_change (insn, &SET_SRC (pat), tem, 0);
1684       else if (sym == NULL_RTX && GET_MODE (reg) != BImode)
1685         {
1686           enum machine_mode narrow_mode;
1687           for (narrow_mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
1688                narrow_mode != VOIDmode
1689                  && narrow_mode != GET_MODE (reg);
1690                narrow_mode = GET_MODE_WIDER_MODE (narrow_mode))
1691             {
1692               if (have_insn_for (STRICT_LOW_PART, narrow_mode)
1693                   && ((reg_offset[regno] & ~GET_MODE_MASK (narrow_mode))
1694                       == (INTVAL (off) & ~GET_MODE_MASK (narrow_mode))))
1695                 {
1696                   rtx narrow_reg = gen_rtx_REG (narrow_mode,
1697                                                 REGNO (reg));
1698                   rtx narrow_src = gen_int_mode (INTVAL (off),
1699                                                  narrow_mode);
1700                   rtx new_set
1701                     = gen_rtx_SET (VOIDmode,
1702                                    gen_rtx_STRICT_LOW_PART (VOIDmode,
1703                                                             narrow_reg),
1704                                    narrow_src);
1705                   changed = validate_change (insn, &PATTERN (insn),
1706                                              new_set, 0);
1707                   if (changed)
1708                     break;
1709                 }
1710             }
1711         }
1712     }
1713   reg_set_luid[regno] = move2add_luid;
1714   reg_base_reg[regno] = -1;
1715   reg_mode[regno] = GET_MODE (reg);
1716   reg_symbol_ref[regno] = sym;
1717   reg_offset[regno] = INTVAL (off);
1718   return changed;
1719 }
1720
1721
1722 /* This function is called with INSN that sets REG to (SYM + OFF),
1723    but REG doesn't have known value (SYM + offset).  This function
1724    tries to find another register which is known to already have
1725    value (SYM + offset) and change INSN into an add instruction
1726    (set (REG) (plus (the found register) (OFF - offset))) if such
1727    a register is found.  It also updates the information about
1728    REG's known value.
1729    Return true iff we made a change.  */
1730
1731 static bool
1732 move2add_use_add3_insn (rtx reg, rtx sym, rtx off, rtx insn)
1733 {
1734   rtx pat = PATTERN (insn);
1735   rtx src = SET_SRC (pat);
1736   int regno = REGNO (reg);
1737   int min_regno = 0;
1738   bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
1739   int i;
1740   bool changed = false;
1741   struct full_rtx_costs oldcst, newcst, mincst;
1742   rtx plus_expr;
1743
1744   init_costs_to_max (&mincst);
1745   get_full_rtx_cost (pat, SET, &oldcst);
1746
1747   plus_expr = gen_rtx_PLUS (GET_MODE (reg), reg, const0_rtx);
1748   SET_SRC (pat) = plus_expr;
1749
1750   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1751     if (reg_set_luid[i] > move2add_last_label_luid
1752         && reg_mode[i] == GET_MODE (reg)
1753         && reg_base_reg[i] < 0
1754         && reg_symbol_ref[i] != NULL_RTX
1755         && rtx_equal_p (sym, reg_symbol_ref[i]))
1756       {
1757         rtx new_src = gen_int_mode (INTVAL (off) - reg_offset[i],
1758                                     GET_MODE (reg));
1759         /* (set (reg) (plus (reg) (const_int 0))) is not canonical;
1760            use (set (reg) (reg)) instead.
1761            We don't delete this insn, nor do we convert it into a
1762            note, to avoid losing register notes or the return
1763            value flag.  jump2 already knows how to get rid of
1764            no-op moves.  */
1765         if (new_src == const0_rtx)
1766           {
1767             init_costs_to_zero (&mincst);
1768             min_regno = i;
1769             break;
1770           }
1771         else
1772           {
1773             XEXP (plus_expr, 1) = new_src;
1774             get_full_rtx_cost (pat, SET, &newcst);
1775
1776             if (costs_lt_p (&newcst, &mincst, speed))
1777               {
1778                 mincst = newcst;
1779                 min_regno = i;
1780               }
1781           }
1782       }
1783   SET_SRC (pat) = src;
1784
1785   if (costs_lt_p (&mincst, &oldcst, speed))
1786     {
1787       rtx tem;
1788
1789       tem = gen_rtx_REG (GET_MODE (reg), min_regno);
1790       if (i != min_regno)
1791         {
1792           rtx new_src = gen_int_mode (INTVAL (off) - reg_offset[min_regno],
1793                                       GET_MODE (reg));
1794           tem = gen_rtx_PLUS (GET_MODE (reg), tem, new_src);
1795         }
1796       if (validate_change (insn, &SET_SRC (pat), tem, 0))
1797         changed = true;
1798     }
1799   reg_set_luid[regno] = move2add_luid;
1800   reg_base_reg[regno] = -1;
1801   reg_mode[regno] = GET_MODE (reg);
1802   reg_symbol_ref[regno] = sym;
1803   reg_offset[regno] = INTVAL (off);
1804   return changed;
1805 }
1806
1807 /* Convert move insns with constant inputs to additions if they are cheaper.
1808    Return true if any changes were made.  */
1809 static bool
1810 reload_cse_move2add (rtx first)
1811 {
1812   int i;
1813   rtx insn;
1814   bool changed = false;
1815
1816   for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1817     {
1818       reg_set_luid[i] = 0;
1819       reg_offset[i] = 0;
1820       reg_base_reg[i] = 0;
1821       reg_symbol_ref[i] = NULL_RTX;
1822       reg_mode[i] = VOIDmode;
1823     }
1824
1825   move2add_last_label_luid = 0;
1826   move2add_luid = 2;
1827   for (insn = first; insn; insn = NEXT_INSN (insn), move2add_luid++)
1828     {
1829       rtx pat, note;
1830
1831       if (LABEL_P (insn))
1832         {
1833           move2add_last_label_luid = move2add_luid;
1834           /* We're going to increment move2add_luid twice after a
1835              label, so that we can use move2add_last_label_luid + 1 as
1836              the luid for constants.  */
1837           move2add_luid++;
1838           continue;
1839         }
1840       if (! INSN_P (insn))
1841         continue;
1842       pat = PATTERN (insn);
1843       /* For simplicity, we only perform this optimization on
1844          straightforward SETs.  */
1845       if (GET_CODE (pat) == SET
1846           && REG_P (SET_DEST (pat)))
1847         {
1848           rtx reg = SET_DEST (pat);
1849           int regno = REGNO (reg);
1850           rtx src = SET_SRC (pat);
1851
1852           /* Check if we have valid information on the contents of this
1853              register in the mode of REG.  */
1854           if (reg_set_luid[regno] > move2add_last_label_luid
1855               && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg), reg_mode[regno])
1856               && dbg_cnt (cse2_move2add))
1857             {
1858               /* Try to transform (set (REGX) (CONST_INT A))
1859                                   ...
1860                                   (set (REGX) (CONST_INT B))
1861                  to
1862                                   (set (REGX) (CONST_INT A))
1863                                   ...
1864                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))
1865                  or
1866                                   (set (REGX) (CONST_INT A))
1867                                   ...
1868                                   (set (STRICT_LOW_PART (REGX)) (CONST_INT B))
1869               */
1870
1871               if (CONST_INT_P (src)
1872                   && reg_base_reg[regno] < 0
1873                   && reg_symbol_ref[regno] == NULL_RTX)
1874                 {
1875                   changed |= move2add_use_add2_insn (reg, NULL_RTX, src, insn);
1876                   continue;
1877                 }
1878
1879               /* Try to transform (set (REGX) (REGY))
1880                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1881                                   ...
1882                                   (set (REGX) (REGY))
1883                                   (set (REGX) (PLUS (REGX) (CONST_INT B)))
1884                  to
1885                                   (set (REGX) (REGY))
1886                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1887                                   ...
1888                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))  */
1889               else if (REG_P (src)
1890                        && reg_set_luid[regno] == reg_set_luid[REGNO (src)]
1891                        && reg_base_reg[regno] == reg_base_reg[REGNO (src)]
1892                        && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg),
1893                                                  reg_mode[REGNO (src)]))
1894                 {
1895                   rtx next = next_nonnote_nondebug_insn (insn);
1896                   rtx set = NULL_RTX;
1897                   if (next)
1898                     set = single_set (next);
1899                   if (set
1900                       && SET_DEST (set) == reg
1901                       && GET_CODE (SET_SRC (set)) == PLUS
1902                       && XEXP (SET_SRC (set), 0) == reg
1903                       && CONST_INT_P (XEXP (SET_SRC (set), 1)))
1904                     {
1905                       rtx src3 = XEXP (SET_SRC (set), 1);
1906                       HOST_WIDE_INT added_offset = INTVAL (src3);
1907                       HOST_WIDE_INT base_offset = reg_offset[REGNO (src)];
1908                       HOST_WIDE_INT regno_offset = reg_offset[regno];
1909                       rtx new_src =
1910                         gen_int_mode (added_offset
1911                                       + base_offset
1912                                       - regno_offset,
1913                                       GET_MODE (reg));
1914                       bool success = false;
1915                       bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
1916
1917                       if (new_src == const0_rtx)
1918                         /* See above why we create (set (reg) (reg)) here.  */
1919                         success
1920                           = validate_change (next, &SET_SRC (set), reg, 0);
1921                       else
1922                         {
1923                           rtx old_src = SET_SRC (set);
1924                           struct full_rtx_costs oldcst, newcst;
1925                           rtx tem = gen_rtx_PLUS (GET_MODE (reg), reg, new_src);
1926
1927                           get_full_rtx_cost (set, SET, &oldcst);
1928                           SET_SRC (set) = tem;
1929                           get_full_rtx_cost (tem, SET, &newcst);
1930                           SET_SRC (set) = old_src;
1931                           costs_add_n_insns (&oldcst, 1);
1932
1933                           if (costs_lt_p (&newcst, &oldcst, speed)
1934                               && have_add2_insn (reg, new_src))
1935                             {
1936                               rtx newpat = gen_rtx_SET (VOIDmode, reg, tem);
1937                               success
1938                                 = validate_change (next, &PATTERN (next),
1939                                                    newpat, 0);
1940                             }
1941                         }
1942                       if (success)
1943                         delete_insn (insn);
1944                       changed |= success;
1945                       insn = next;
1946                       reg_mode[regno] = GET_MODE (reg);
1947                       reg_offset[regno] =
1948                         trunc_int_for_mode (added_offset + base_offset,
1949                                             GET_MODE (reg));
1950                       continue;
1951                     }
1952                 }
1953             }
1954
1955           /* Try to transform
1956              (set (REGX) (CONST (PLUS (SYMBOL_REF) (CONST_INT A))))
1957              ...
1958              (set (REGY) (CONST (PLUS (SYMBOL_REF) (CONST_INT B))))
1959              to
1960              (set (REGX) (CONST (PLUS (SYMBOL_REF) (CONST_INT A))))
1961              ...
1962              (set (REGY) (CONST (PLUS (REGX) (CONST_INT B-A))))  */
1963           if ((GET_CODE (src) == SYMBOL_REF
1964                || (GET_CODE (src) == CONST
1965                    && GET_CODE (XEXP (src, 0)) == PLUS
1966                    && GET_CODE (XEXP (XEXP (src, 0), 0)) == SYMBOL_REF
1967                    && CONST_INT_P (XEXP (XEXP (src, 0), 1))))
1968               && dbg_cnt (cse2_move2add))
1969             {
1970               rtx sym, off;
1971
1972               if (GET_CODE (src) == SYMBOL_REF)
1973                 {
1974                   sym = src;
1975                   off = const0_rtx;
1976                 }
1977               else
1978                 {
1979                   sym = XEXP (XEXP (src, 0), 0);
1980                   off = XEXP (XEXP (src, 0), 1);
1981                 }
1982
1983               /* If the reg already contains the value which is sum of
1984                  sym and some constant value, we can use an add2 insn.  */
1985               if (reg_set_luid[regno] > move2add_last_label_luid
1986                   && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg), reg_mode[regno])
1987                   && reg_base_reg[regno] < 0
1988                   && reg_symbol_ref[regno] != NULL_RTX
1989                   && rtx_equal_p (sym, reg_symbol_ref[regno]))
1990                 changed |= move2add_use_add2_insn (reg, sym, off, insn);
1991
1992               /* Otherwise, we have to find a register whose value is sum
1993                  of sym and some constant value.  */
1994               else
1995                 changed |= move2add_use_add3_insn (reg, sym, off, insn);
1996
1997               continue;
1998             }
1999         }
2000
2001       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2002         {
2003           if (REG_NOTE_KIND (note) == REG_INC
2004               && REG_P (XEXP (note, 0)))
2005             {
2006               /* Reset the information about this register.  */
2007               int regno = REGNO (XEXP (note, 0));
2008               if (regno < FIRST_PSEUDO_REGISTER)
2009                 reg_set_luid[regno] = 0;
2010             }
2011         }
2012       note_stores (PATTERN (insn), move2add_note_store, insn);
2013
2014       /* If INSN is a conditional branch, we try to extract an
2015          implicit set out of it.  */
2016       if (any_condjump_p (insn))
2017         {
2018           rtx cnd = fis_get_condition (insn);
2019
2020           if (cnd != NULL_RTX
2021               && GET_CODE (cnd) == NE
2022               && REG_P (XEXP (cnd, 0))
2023               && !reg_set_p (XEXP (cnd, 0), insn)
2024               /* The following two checks, which are also in
2025                  move2add_note_store, are intended to reduce the
2026                  number of calls to gen_rtx_SET to avoid memory
2027                  allocation if possible.  */
2028               && SCALAR_INT_MODE_P (GET_MODE (XEXP (cnd, 0)))
2029               && hard_regno_nregs[REGNO (XEXP (cnd, 0))][GET_MODE (XEXP (cnd, 0))] == 1
2030               && CONST_INT_P (XEXP (cnd, 1)))
2031             {
2032               rtx implicit_set =
2033                 gen_rtx_SET (VOIDmode, XEXP (cnd, 0), XEXP (cnd, 1));
2034               move2add_note_store (SET_DEST (implicit_set), implicit_set, insn);
2035             }
2036         }
2037
2038       /* If this is a CALL_INSN, all call used registers are stored with
2039          unknown values.  */
2040       if (CALL_P (insn))
2041         {
2042           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
2043             {
2044               if (call_used_regs[i])
2045                 /* Reset the information about this register.  */
2046                 reg_set_luid[i] = 0;
2047             }
2048         }
2049     }
2050   return changed;
2051 }
2052
2053 /* SET is a SET or CLOBBER that sets DST.  DATA is the insn which
2054    contains SET.
2055    Update reg_set_luid, reg_offset and reg_base_reg accordingly.
2056    Called from reload_cse_move2add via note_stores.  */
2057
2058 static void
2059 move2add_note_store (rtx dst, const_rtx set, void *data)
2060 {
2061   rtx insn = (rtx) data;
2062   unsigned int regno = 0;
2063   unsigned int nregs = 0;
2064   unsigned int i;
2065   enum machine_mode mode = GET_MODE (dst);
2066
2067   if (GET_CODE (dst) == SUBREG)
2068     {
2069       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
2070                                    GET_MODE (SUBREG_REG (dst)),
2071                                    SUBREG_BYTE (dst),
2072                                    GET_MODE (dst));
2073       nregs = subreg_nregs (dst);
2074       dst = SUBREG_REG (dst);
2075     }
2076
2077   /* Some targets do argument pushes without adding REG_INC notes.  */
2078
2079   if (MEM_P (dst))
2080     {
2081       dst = XEXP (dst, 0);
2082       if (GET_CODE (dst) == PRE_INC || GET_CODE (dst) == POST_INC
2083           || GET_CODE (dst) == PRE_DEC || GET_CODE (dst) == POST_DEC)
2084         reg_set_luid[REGNO (XEXP (dst, 0))] = 0;
2085       return;
2086     }
2087   if (!REG_P (dst))
2088     return;
2089
2090   regno += REGNO (dst);
2091   if (!nregs)
2092     nregs = hard_regno_nregs[regno][mode];
2093
2094   if (SCALAR_INT_MODE_P (GET_MODE (dst))
2095       && nregs == 1 && GET_CODE (set) == SET)
2096     {
2097       rtx note, sym = NULL_RTX;
2098       HOST_WIDE_INT off;
2099
2100       note = find_reg_equal_equiv_note (insn);
2101       if (note && GET_CODE (XEXP (note, 0)) == SYMBOL_REF)
2102         {
2103           sym = XEXP (note, 0);
2104           off = 0;
2105         }
2106       else if (note && GET_CODE (XEXP (note, 0)) == CONST
2107                && GET_CODE (XEXP (XEXP (note, 0), 0)) == PLUS
2108                && GET_CODE (XEXP (XEXP (XEXP (note, 0), 0), 0)) == SYMBOL_REF
2109                && CONST_INT_P (XEXP (XEXP (XEXP (note, 0), 0), 1)))
2110         {
2111           sym = XEXP (XEXP (XEXP (note, 0), 0), 0);
2112           off = INTVAL (XEXP (XEXP (XEXP (note, 0), 0), 1));
2113         }
2114
2115       if (sym != NULL_RTX)
2116         {
2117           reg_base_reg[regno] = -1;
2118           reg_symbol_ref[regno] = sym;
2119           reg_offset[regno] = off;
2120           reg_mode[regno] = mode;
2121           reg_set_luid[regno] = move2add_luid;
2122           return;
2123         }
2124     }
2125
2126   if (SCALAR_INT_MODE_P (GET_MODE (dst))
2127       && nregs == 1 && GET_CODE (set) == SET
2128       && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
2129       && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
2130     {
2131       rtx src = SET_SRC (set);
2132       rtx base_reg;
2133       HOST_WIDE_INT offset;
2134       int base_regno;
2135       /* This may be different from mode, if SET_DEST (set) is a
2136          SUBREG.  */
2137       enum machine_mode dst_mode = GET_MODE (dst);
2138
2139       switch (GET_CODE (src))
2140         {
2141         case PLUS:
2142           if (REG_P (XEXP (src, 0)))
2143             {
2144               base_reg = XEXP (src, 0);
2145
2146               if (CONST_INT_P (XEXP (src, 1)))
2147                 offset = INTVAL (XEXP (src, 1));
2148               else if (REG_P (XEXP (src, 1))
2149                        && (reg_set_luid[REGNO (XEXP (src, 1))]
2150                            > move2add_last_label_luid)
2151                        && (MODES_OK_FOR_MOVE2ADD
2152                            (dst_mode, reg_mode[REGNO (XEXP (src, 1))])))
2153                 {
2154                   if (reg_base_reg[REGNO (XEXP (src, 1))] < 0
2155                       && reg_symbol_ref[REGNO (XEXP (src, 1))] == NULL_RTX)
2156                     offset = reg_offset[REGNO (XEXP (src, 1))];
2157                   /* Maybe the first register is known to be a
2158                      constant.  */
2159                   else if (reg_set_luid[REGNO (base_reg)]
2160                            > move2add_last_label_luid
2161                            && (MODES_OK_FOR_MOVE2ADD
2162                                (dst_mode, reg_mode[REGNO (base_reg)]))
2163                            && reg_base_reg[REGNO (base_reg)] < 0
2164                            && reg_symbol_ref[REGNO (base_reg)] == NULL_RTX)
2165                     {
2166                       offset = reg_offset[REGNO (base_reg)];
2167                       base_reg = XEXP (src, 1);
2168                     }
2169                   else
2170                     goto invalidate;
2171                 }
2172               else
2173                 goto invalidate;
2174
2175               break;
2176             }
2177
2178           goto invalidate;
2179
2180         case REG:
2181           base_reg = src;
2182           offset = 0;
2183           break;
2184
2185         case CONST_INT:
2186           /* Start tracking the register as a constant.  */
2187           reg_base_reg[regno] = -1;
2188           reg_symbol_ref[regno] = NULL_RTX;
2189           reg_offset[regno] = INTVAL (SET_SRC (set));
2190           /* We assign the same luid to all registers set to constants.  */
2191           reg_set_luid[regno] = move2add_last_label_luid + 1;
2192           reg_mode[regno] = mode;
2193           return;
2194
2195         default:
2196         invalidate:
2197           /* Invalidate the contents of the register.  */
2198           reg_set_luid[regno] = 0;
2199           return;
2200         }
2201
2202       base_regno = REGNO (base_reg);
2203       /* If information about the base register is not valid, set it
2204          up as a new base register, pretending its value is known
2205          starting from the current insn.  */
2206       if (reg_set_luid[base_regno] <= move2add_last_label_luid)
2207         {
2208           reg_base_reg[base_regno] = base_regno;
2209           reg_symbol_ref[base_regno] = NULL_RTX;
2210           reg_offset[base_regno] = 0;
2211           reg_set_luid[base_regno] = move2add_luid;
2212           reg_mode[base_regno] = mode;
2213         }
2214       else if (! MODES_OK_FOR_MOVE2ADD (dst_mode,
2215                                         reg_mode[base_regno]))
2216         goto invalidate;
2217
2218       reg_mode[regno] = mode;
2219
2220       /* Copy base information from our base register.  */
2221       reg_set_luid[regno] = reg_set_luid[base_regno];
2222       reg_base_reg[regno] = reg_base_reg[base_regno];
2223       reg_symbol_ref[regno] = reg_symbol_ref[base_regno];
2224
2225       /* Compute the sum of the offsets or constants.  */
2226       reg_offset[regno] = trunc_int_for_mode (offset
2227                                               + reg_offset[base_regno],
2228                                               dst_mode);
2229     }
2230   else
2231     {
2232       unsigned int endregno = regno + nregs;
2233
2234       for (i = regno; i < endregno; i++)
2235         /* Reset the information about this register.  */
2236         reg_set_luid[i] = 0;
2237     }
2238 }
2239 \f
2240 static bool
2241 gate_handle_postreload (void)
2242 {
2243   return (optimize > 0 && reload_completed);
2244 }
2245
2246
2247 static unsigned int
2248 rest_of_handle_postreload (void)
2249 {
2250   if (!dbg_cnt (postreload_cse))
2251     return 0;
2252
2253   /* Do a very simple CSE pass over just the hard registers.  */
2254   reload_cse_regs (get_insns ());
2255   /* Reload_cse_regs can eliminate potentially-trapping MEMs.
2256      Remove any EH edges associated with them.  */
2257   if (cfun->can_throw_non_call_exceptions)
2258     purge_all_dead_edges ();
2259
2260   return 0;
2261 }
2262
2263 struct rtl_opt_pass pass_postreload_cse =
2264 {
2265  {
2266   RTL_PASS,
2267   "postreload",                         /* name */
2268   gate_handle_postreload,               /* gate */
2269   rest_of_handle_postreload,            /* execute */
2270   NULL,                                 /* sub */
2271   NULL,                                 /* next */
2272   0,                                    /* static_pass_number */
2273   TV_RELOAD_CSE_REGS,                   /* tv_id */
2274   0,                                    /* properties_required */
2275   0,                                    /* properties_provided */
2276   0,                                    /* properties_destroyed */
2277   0,                                    /* todo_flags_start */
2278   TODO_df_finish | TODO_verify_rtl_sharing |
2279   TODO_dump_func                        /* todo_flags_finish */
2280  }
2281 };