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, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  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 "real.h"
  44 #include "toplev.h"
  45 #include "except.h"
  46 #include "tree.h"
  47 #include "timevar.h"
  48 #include "tree-pass.h"
  49
  50 static int reload_cse_noop_set_p (rtx);
  51 static void reload_cse_simplify (rtx, rtx);
  52 static void reload_cse_regs_1 (rtx);
  53 static int reload_cse_simplify_set (rtx, rtx);
  54 static int reload_cse_simplify_operands (rtx, rtx);
  55
  56 static void reload_combine (void);
  57 static void reload_combine_note_use (rtx *, rtx);
  58 static void reload_combine_note_store (rtx, rtx, void *);
  59
  60 static void reload_cse_move2add (rtx);
  61 static void move2add_note_store (rtx, rtx, void *);
  62
  63 /* Call cse / combine like post-reload optimization phases.
  64    FIRST is the first instruction.  */
  65 void
  66 reload_cse_regs (rtx first ATTRIBUTE_UNUSED)
  67 {
  68   reload_cse_regs_1 (first);
  69   reload_combine ();
  70   reload_cse_move2add (first);
  71   if (flag_expensive_optimizations)
  72     reload_cse_regs_1 (first);
  73 }
  74
  75 /* See whether a single set SET is a noop.  */
  76 static int
  77 reload_cse_noop_set_p (rtx set)
  78 {
  79   if (cselib_reg_set_mode (SET_DEST (set)) != GET_MODE (SET_DEST (set)))
  80     return 0;
  81
  82   return rtx_equal_for_cselib_p (SET_DEST (set), SET_SRC (set));
  83 }
  84
  85 /* Try to simplify INSN.  */
  86 static void
  87 reload_cse_simplify (rtx insn, rtx testreg)
  88 {
  89   rtx body = PATTERN (insn);
  90
  91   if (GET_CODE (body) == SET)
  92     {
  93       int count = 0;
  94
  95       /* Simplify even if we may think it is a no-op.
  96          We may think a memory load of a value smaller than WORD_SIZE
  97          is redundant because we haven't taken into account possible
  98          implicit extension.  reload_cse_simplify_set() will bring
  99          this out, so it's safer to simplify before we delete.  */
 100       count += reload_cse_simplify_set (body, insn);
 101
 102       if (!count && reload_cse_noop_set_p (body))
 103         {
 104           rtx value = SET_DEST (body);
 105           if (REG_P (value)
 106               && ! REG_FUNCTION_VALUE_P (value))
 107             value = 0;
 108           delete_insn_and_edges (insn);
 109           return;
 110         }
 111
 112       if (count > 0)
 113         apply_change_group ();
 114       else
 115         reload_cse_simplify_operands (insn, testreg);
 116     }
 117   else if (GET_CODE (body) == PARALLEL)
 118     {
 119       int i;
 120       int count = 0;
 121       rtx value = NULL_RTX;
 122
 123       /* Registers mentioned in the clobber list for an asm cannot be reused
 124          within the body of the asm.  Invalidate those registers now so that
 125          we don't try to substitute values for them.  */
 126       if (asm_noperands (body) >= 0)
 127         {
 128           for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
 129             {
 130               rtx part = XVECEXP (body, 0, i);
 131               if (GET_CODE (part) == CLOBBER && REG_P (XEXP (part, 0)))
 132                 cselib_invalidate_rtx (XEXP (part, 0));
 133             }
 134         }
 135
 136       /* If every action in a PARALLEL is a noop, we can delete
 137          the entire PARALLEL.  */
 138       for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
 139         {
 140           rtx part = XVECEXP (body, 0, i);
 141           if (GET_CODE (part) == SET)
 142             {
 143               if (! reload_cse_noop_set_p (part))
 144                 break;
 145               if (REG_P (SET_DEST (part))
 146                   && REG_FUNCTION_VALUE_P (SET_DEST (part)))
 147                 {
 148                   if (value)
 149                     break;
 150                   value = SET_DEST (part);
 151                 }
 152             }
 153           else if (GET_CODE (part) != CLOBBER)
 154             break;
 155         }
 156
 157       if (i < 0)
 158         {
 159           delete_insn_and_edges (insn);
 160           /* We're done with this insn.  */
 161           return;
 162         }
 163
 164       /* It's not a no-op, but we can try to simplify it.  */
 165       for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
 166         if (GET_CODE (XVECEXP (body, 0, i)) == SET)
 167           count += reload_cse_simplify_set (XVECEXP (body, 0, i), insn);
 168
 169       if (count > 0)
 170         apply_change_group ();
 171       else
 172         reload_cse_simplify_operands (insn, testreg);
 173     }
 174 }
 175
 176 /* Do a very simple CSE pass over the hard registers.
 177
 178    This function detects no-op moves where we happened to assign two
 179    different pseudo-registers to the same hard register, and then
 180    copied one to the other.  Reload will generate a useless
 181    instruction copying a register to itself.
 182
 183    This function also detects cases where we load a value from memory
 184    into two different registers, and (if memory is more expensive than
 185    registers) changes it to simply copy the first register into the
 186    second register.
 187
 188    Another optimization is performed that scans the operands of each
 189    instruction to see whether the value is already available in a
 190    hard register.  It then replaces the operand with the hard register
 191    if possible, much like an optional reload would.  */
 192
 193 static void
 194 reload_cse_regs_1 (rtx first)
 195 {
 196   rtx insn;
 197   rtx testreg = gen_rtx_REG (VOIDmode, -1);
 198
 199   cselib_init (true);
 200   init_alias_analysis ();
 201
 202   for (insn = first; insn; insn = NEXT_INSN (insn))
 203     {
 204       if (INSN_P (insn))
 205         reload_cse_simplify (insn, testreg);
 206
 207       cselib_process_insn (insn);
 208     }
 209
 210   /* Clean up.  */
 211   end_alias_analysis ();
 212   cselib_finish ();
 213 }
 214
 215 /* Try to simplify a single SET instruction.  SET is the set pattern.
 216    INSN is the instruction it came from.
 217    This function only handles one case: if we set a register to a value
 218    which is not a register, we try to find that value in some other register
 219    and change the set into a register copy.  */
 220
 221 static int
 222 reload_cse_simplify_set (rtx set, rtx insn)
 223 {
 224   int did_change = 0;
 225   int dreg;
 226   rtx src;
 227   enum reg_class dclass;
 228   int old_cost;
 229   cselib_val *val;
 230   struct elt_loc_list *l;
 231 #ifdef LOAD_EXTEND_OP
 232   enum rtx_code extend_op = UNKNOWN;
 233 #endif
 234
 235   dreg = true_regnum (SET_DEST (set));
 236   if (dreg < 0)
 237     return 0;
 238
 239   src = SET_SRC (set);
 240   if (side_effects_p (src) || true_regnum (src) >= 0)
 241     return 0;
 242
 243   dclass = REGNO_REG_CLASS (dreg);
 244
 245 #ifdef LOAD_EXTEND_OP
 246   /* When replacing a memory with a register, we need to honor assumptions
 247      that combine made wrt the contents of sign bits.  We'll do this by
 248      generating an extend instruction instead of a reg->reg copy.  Thus
 249      the destination must be a register that we can widen.  */
 250   if (MEM_P (src)
 251       && GET_MODE_BITSIZE (GET_MODE (src)) < BITS_PER_WORD
 252       && (extend_op = LOAD_EXTEND_OP (GET_MODE (src))) != UNKNOWN
 253       && !REG_P (SET_DEST (set)))
 254     return 0;
 255 #endif
 256
 257   val = cselib_lookup (src, GET_MODE (SET_DEST (set)), 0);
 258   if (! val)
 259     return 0;
 260
 261   /* If memory loads are cheaper than register copies, don't change them.  */
 262   if (MEM_P (src))
 263     old_cost = MEMORY_MOVE_COST (GET_MODE (src), dclass, 1);
 264   else if (REG_P (src))
 265     old_cost = REGISTER_MOVE_COST (GET_MODE (src),
 266                                    REGNO_REG_CLASS (REGNO (src)), dclass);
 267   else
 268     old_cost = rtx_cost (src, SET);
 269
 270   for (l = val->locs; l; l = l->next)
 271     {
 272       rtx this_rtx = l->loc;
 273       int this_cost;
 274
 275       if (CONSTANT_P (this_rtx) && ! references_value_p (this_rtx, 0))
 276         {
 277 #ifdef LOAD_EXTEND_OP
 278           if (extend_op != UNKNOWN)
 279             {
 280               HOST_WIDE_INT this_val;
 281
 282               /* ??? I'm lazy and don't wish to handle CONST_DOUBLE.  Other
 283                  constants, such as SYMBOL_REF, cannot be extended.  */
 284               if (GET_CODE (this_rtx) != CONST_INT)
 285                 continue;
 286
 287               this_val = INTVAL (this_rtx);
 288               switch (extend_op)
 289                 {
 290                 case ZERO_EXTEND:
 291                   this_val &= GET_MODE_MASK (GET_MODE (src));
 292                   break;
 293                 case SIGN_EXTEND:
 294                   /* ??? In theory we're already extended.  */
 295                   if (this_val == trunc_int_for_mode (this_val, GET_MODE (src)))
 296                     break;
 297                 default:
 298                   gcc_unreachable ();
 299                 }
 300               this_rtx = GEN_INT (this_val);
 301             }
 302 #endif
 303           this_cost = rtx_cost (this_rtx, SET);
 304         }
 305       else if (REG_P (this_rtx))
 306         {
 307 #ifdef LOAD_EXTEND_OP
 308           if (extend_op != UNKNOWN)
 309             {
 310               this_rtx = gen_rtx_fmt_e (extend_op, word_mode, this_rtx);
 311               this_cost = rtx_cost (this_rtx, SET);
 312             }
 313           else
 314 #endif
 315             this_cost = REGISTER_MOVE_COST (GET_MODE (this_rtx),
 316                                             REGNO_REG_CLASS (REGNO (this_rtx)),
 317                                             dclass);
 318         }
 319       else
 320         continue;
 321
 322       /* If equal costs, prefer registers over anything else.  That
 323          tends to lead to smaller instructions on some machines.  */
 324       if (this_cost < old_cost
 325           || (this_cost == old_cost
 326               && REG_P (this_rtx)
 327               && !REG_P (SET_SRC (set))))
 328         {
 329 #ifdef LOAD_EXTEND_OP
 330           if (GET_MODE_BITSIZE (GET_MODE (SET_DEST (set))) < BITS_PER_WORD
 331               && extend_op != UNKNOWN
 332 #ifdef CANNOT_CHANGE_MODE_CLASS
 333               && !CANNOT_CHANGE_MODE_CLASS (GET_MODE (SET_DEST (set)),
 334                                             word_mode,
 335                                             REGNO_REG_CLASS (REGNO (SET_DEST (set))))
 336 #endif
 337               )
 338             {
 339               rtx wide_dest = gen_rtx_REG (word_mode, REGNO (SET_DEST (set)));
 340               ORIGINAL_REGNO (wide_dest) = ORIGINAL_REGNO (SET_DEST (set));
 341               validate_change (insn, &SET_DEST (set), wide_dest, 1);
 342             }
 343 #endif
 344
 345           validate_change (insn, &SET_SRC (set), copy_rtx (this_rtx), 1);
 346           old_cost = this_cost, did_change = 1;
 347         }
 348     }
 349
 350   return did_change;
 351 }
 352
 353 /* Try to replace operands in INSN with equivalent values that are already
 354    in registers.  This can be viewed as optional reloading.
 355
 356    For each non-register operand in the insn, see if any hard regs are
 357    known to be equivalent to that operand.  Record the alternatives which
 358    can accept these hard registers.  Among all alternatives, select the
 359    ones which are better or equal to the one currently matching, where
 360    "better" is in terms of '?' and '!' constraints.  Among the remaining
 361    alternatives, select the one which replaces most operands with
 362    hard registers.  */
 363
 364 static int
 365 reload_cse_simplify_operands (rtx insn, rtx testreg)
 366 {
 367   int i, j;
 368
 369   /* For each operand, all registers that are equivalent to it.  */
 370   HARD_REG_SET equiv_regs[MAX_RECOG_OPERANDS];
 371
 372   const char *constraints[MAX_RECOG_OPERANDS];
 373
 374   /* Vector recording how bad an alternative is.  */
 375   int *alternative_reject;
 376   /* Vector recording how many registers can be introduced by choosing
 377      this alternative.  */
 378   int *alternative_nregs;
 379   /* Array of vectors recording, for each operand and each alternative,
 380      which hard register to substitute, or -1 if the operand should be
 381      left as it is.  */
 382   int *op_alt_regno[MAX_RECOG_OPERANDS];
 383   /* Array of alternatives, sorted in order of decreasing desirability.  */
 384   int *alternative_order;
 385
 386   extract_insn (insn);
 387
 388   if (recog_data.n_alternatives == 0 || recog_data.n_operands == 0)
 389     return 0;
 390
 391   /* Figure out which alternative currently matches.  */
 392   if (! constrain_operands (1))
 393     fatal_insn_not_found (insn);
 394
 395   alternative_reject = alloca (recog_data.n_alternatives * sizeof (int));
 396   alternative_nregs = alloca (recog_data.n_alternatives * sizeof (int));
 397   alternative_order = alloca (recog_data.n_alternatives * sizeof (int));
 398   memset (alternative_reject, 0, recog_data.n_alternatives * sizeof (int));
 399   memset (alternative_nregs, 0, recog_data.n_alternatives * sizeof (int));
 400
 401   /* For each operand, find out which regs are equivalent.  */
 402   for (i = 0; i < recog_data.n_operands; i++)
 403     {
 404       cselib_val *v;
 405       struct elt_loc_list *l;
 406       rtx op;
 407       enum machine_mode mode;
 408
 409       CLEAR_HARD_REG_SET (equiv_regs[i]);
 410
 411       /* cselib blows up on CODE_LABELs.  Trying to fix that doesn't seem
 412          right, so avoid the problem here.  Likewise if we have a constant
 413          and the insn pattern doesn't tell us the mode we need.  */
 414       if (LABEL_P (recog_data.operand[i])
 415           || (CONSTANT_P (recog_data.operand[i])
 416               && recog_data.operand_mode[i] == VOIDmode))
 417         continue;
 418
 419       op = recog_data.operand[i];
 420       mode = GET_MODE (op);
 421 #ifdef LOAD_EXTEND_OP
 422       if (MEM_P (op)
 423           && GET_MODE_BITSIZE (mode) < BITS_PER_WORD
 424           && LOAD_EXTEND_OP (mode) != UNKNOWN)
 425         {
 426           rtx set = single_set (insn);
 427
 428           /* We might have multiple sets, some of which do implicit
 429              extension.  Punt on this for now.  */
 430           if (! set)
 431             continue;
 432           /* If the destination is also a MEM or a STRICT_LOW_PART, no
 433              extension applies.
 434              Also, if there is an explicit extension, we don't have to
 435              worry about an implicit one.  */
 436           else if (MEM_P (SET_DEST (set))
 437                    || GET_CODE (SET_DEST (set)) == STRICT_LOW_PART
 438                    || GET_CODE (SET_SRC (set)) == ZERO_EXTEND
 439                    || GET_CODE (SET_SRC (set)) == SIGN_EXTEND)
 440             ; /* Continue ordinary processing.  */
 441 #ifdef CANNOT_CHANGE_MODE_CLASS
 442           /* If the register cannot change mode to word_mode, it follows that
 443              it cannot have been used in word_mode.  */
 444           else if (REG_P (SET_DEST (set))
 445                    && CANNOT_CHANGE_MODE_CLASS (GET_MODE (SET_DEST (set)),
 446                                                 word_mode,
 447                                                 REGNO_REG_CLASS (REGNO (SET_DEST (set)))))
 448             ; /* Continue ordinary processing.  */
 449 #endif
 450           /* If this is a straight load, make the extension explicit.  */
 451           else if (REG_P (SET_DEST (set))
 452                    && recog_data.n_operands == 2
 453                    && SET_SRC (set) == op
 454                    && SET_DEST (set) == recog_data.operand[1-i])
 455             {
 456               validate_change (insn, recog_data.operand_loc[i],
 457                                gen_rtx_fmt_e (LOAD_EXTEND_OP (mode),
 458                                               word_mode, op),
 459                                1);
 460               validate_change (insn, recog_data.operand_loc[1-i],
 461                                gen_rtx_REG (word_mode, REGNO (SET_DEST (set))),
 462                                1);
 463               if (! apply_change_group ())
 464                 return 0;
 465               return reload_cse_simplify_operands (insn, testreg);
 466             }
 467           else
 468             /* ??? There might be arithmetic operations with memory that are
 469                safe to optimize, but is it worth the trouble?  */
 470             continue;
 471         }
 472 #endif /* LOAD_EXTEND_OP */
 473       v = cselib_lookup (op, recog_data.operand_mode[i], 0);
 474       if (! v)
 475         continue;
 476
 477       for (l = v->locs; l; l = l->next)
 478         if (REG_P (l->loc))
 479           SET_HARD_REG_BIT (equiv_regs[i], REGNO (l->loc));
 480     }
 481
 482   for (i = 0; i < recog_data.n_operands; i++)
 483     {
 484       enum machine_mode mode;
 485       int regno;
 486       const char *p;
 487
 488       op_alt_regno[i] = alloca (recog_data.n_alternatives * sizeof (int));
 489       for (j = 0; j < recog_data.n_alternatives; j++)
 490         op_alt_regno[i][j] = -1;
 491
 492       p = constraints[i] = recog_data.constraints[i];
 493       mode = recog_data.operand_mode[i];
 494
 495       /* Add the reject values for each alternative given by the constraints
 496          for this operand.  */
 497       j = 0;
 498       while (*p != '\0')
 499         {
 500           char c = *p++;
 501           if (c == ',')
 502             j++;
 503           else if (c == '?')
 504             alternative_reject[j] += 3;
 505           else if (c == '!')
 506             alternative_reject[j] += 300;
 507         }
 508
 509       /* We won't change operands which are already registers.  We
 510          also don't want to modify output operands.  */
 511       regno = true_regnum (recog_data.operand[i]);
 512       if (regno >= 0
 513           || constraints[i][0] == '='
 514           || constraints[i][0] == '+')
 515         continue;
 516
 517       for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
 518         {
 519           int class = (int) NO_REGS;
 520
 521           if (! TEST_HARD_REG_BIT (equiv_regs[i], regno))
 522             continue;
 523
 524           REGNO (testreg) = regno;
 525           PUT_MODE (testreg, mode);
 526
 527           /* We found a register equal to this operand.  Now look for all
 528              alternatives that can accept this register and have not been
 529              assigned a register they can use yet.  */
 530           j = 0;
 531           p = constraints[i];
 532           for (;;)
 533             {
 534               char c = *p;
 535
 536               switch (c)
 537                 {
 538                 case '=':  case '+':  case '?':
 539                 case '#':  case '&':  case '!':
 540                 case '*':  case '%':
 541                 case '0':  case '1':  case '2':  case '3':  case '4':
 542                 case '5':  case '6':  case '7':  case '8':  case '9':
 543                 case 'm':  case '<':  case '>':  case 'V':  case 'o':
 544                 case 'E':  case 'F':  case 'G':  case 'H':
 545                 case 's':  case 'i':  case 'n':
 546                 case 'I':  case 'J':  case 'K':  case 'L':
 547                 case 'M':  case 'N':  case 'O':  case 'P':
 548                 case 'p': case 'X':
 549                   /* These don't say anything we care about.  */
 550                   break;
 551
 552                 case 'g': case 'r':
 553                   class = reg_class_subunion[(int) class][(int) GENERAL_REGS];
 554                   break;
 555
 556                 default:
 557                   class
 558                     = (reg_class_subunion
 559                        [(int) class]
 560                        [(int) REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p)]);
 561                   break;
 562
 563                 case ',': case '\0':
 564                   /* See if REGNO fits this alternative, and set it up as the
 565                      replacement register if we don't have one for this
 566                      alternative yet and the operand being replaced is not
 567                      a cheap CONST_INT.  */
 568                   if (op_alt_regno[i][j] == -1
 569                       && reg_fits_class_p (testreg, class, 0, mode)
 570                       && (GET_CODE (recog_data.operand[i]) != CONST_INT
 571                           || (rtx_cost (recog_data.operand[i], SET)
 572                               > rtx_cost (testreg, SET))))
 573                     {
 574                       alternative_nregs[j]++;
 575                       op_alt_regno[i][j] = regno;
 576                     }
 577                   j++;
 578                   break;
 579                 }
 580               p += CONSTRAINT_LEN (c, p);
 581
 582               if (c == '\0')
 583                 break;
 584             }
 585         }
 586     }
 587
 588   /* Record all alternatives which are better or equal to the currently
 589      matching one in the alternative_order array.  */
 590   for (i = j = 0; i < recog_data.n_alternatives; i++)
 591     if (alternative_reject[i] <= alternative_reject[which_alternative])
 592       alternative_order[j++] = i;
 593   recog_data.n_alternatives = j;
 594
 595   /* Sort it.  Given a small number of alternatives, a dumb algorithm
 596      won't hurt too much.  */
 597   for (i = 0; i < recog_data.n_alternatives - 1; i++)
 598     {
 599       int best = i;
 600       int best_reject = alternative_reject[alternative_order[i]];
 601       int best_nregs = alternative_nregs[alternative_order[i]];
 602       int tmp;
 603
 604       for (j = i + 1; j < recog_data.n_alternatives; j++)
 605         {
 606           int this_reject = alternative_reject[alternative_order[j]];
 607           int this_nregs = alternative_nregs[alternative_order[j]];
 608
 609           if (this_reject < best_reject
 610               || (this_reject == best_reject && this_nregs < best_nregs))
 611             {
 612               best = j;
 613               best_reject = this_reject;
 614               best_nregs = this_nregs;
 615             }
 616         }
 617
 618       tmp = alternative_order[best];
 619       alternative_order[best] = alternative_order[i];
 620       alternative_order[i] = tmp;
 621     }
 622
 623   /* Substitute the operands as determined by op_alt_regno for the best
 624      alternative.  */
 625   j = alternative_order[0];
 626
 627   for (i = 0; i < recog_data.n_operands; i++)
 628     {
 629       enum machine_mode mode = recog_data.operand_mode[i];
 630       if (op_alt_regno[i][j] == -1)
 631         continue;
 632
 633       validate_change (insn, recog_data.operand_loc[i],
 634                        gen_rtx_REG (mode, op_alt_regno[i][j]), 1);
 635     }
 636
 637   for (i = recog_data.n_dups - 1; i >= 0; i--)
 638     {
 639       int op = recog_data.dup_num[i];
 640       enum machine_mode mode = recog_data.operand_mode[op];
 641
 642       if (op_alt_regno[op][j] == -1)
 643         continue;
 644
 645       validate_change (insn, recog_data.dup_loc[i],
 646                        gen_rtx_REG (mode, op_alt_regno[op][j]), 1);
 647     }
 648
 649   return apply_change_group ();
 650 }
 651 \f
 652 /* If reload couldn't use reg+reg+offset addressing, try to use reg+reg
 653    addressing now.
 654    This code might also be useful when reload gave up on reg+reg addressing
 655    because of clashes between the return register and INDEX_REG_CLASS.  */
 656
 657 /* The maximum number of uses of a register we can keep track of to
 658    replace them with reg+reg addressing.  */
 659 #define RELOAD_COMBINE_MAX_USES 6
 660
 661 /* INSN is the insn where a register has ben used, and USEP points to the
 662    location of the register within the rtl.  */
 663 struct reg_use { rtx insn, *usep; };
 664
 665 /* If the register is used in some unknown fashion, USE_INDEX is negative.
 666    If it is dead, USE_INDEX is RELOAD_COMBINE_MAX_USES, and STORE_RUID
 667    indicates where it becomes live again.
 668    Otherwise, USE_INDEX is the index of the last encountered use of the
 669    register (which is first among these we have seen since we scan backwards),
 670    OFFSET contains the constant offset that is added to the register in
 671    all encountered uses, and USE_RUID indicates the first encountered, i.e.
 672    last, of these uses.
 673    STORE_RUID is always meaningful if we only want to use a value in a
 674    register in a different place: it denotes the next insn in the insn
 675    stream (i.e. the last encountered) that sets or clobbers the register.  */
 676 static struct
 677   {
 678     struct reg_use reg_use[RELOAD_COMBINE_MAX_USES];
 679     int use_index;
 680     rtx offset;
 681     int store_ruid;
 682     int use_ruid;
 683   } reg_state[FIRST_PSEUDO_REGISTER];
 684
 685 /* Reverse linear uid.  This is increased in reload_combine while scanning
 686    the instructions from last to first.  It is used to set last_label_ruid
 687    and the store_ruid / use_ruid fields in reg_state.  */
 688 static int reload_combine_ruid;
 689
 690 #define LABEL_LIVE(LABEL) \
 691   (label_live[CODE_LABEL_NUMBER (LABEL) - min_labelno])
 692
 693 static void
 694 reload_combine (void)
 695 {
 696   rtx insn, set;
 697   int first_index_reg = -1;
 698   int last_index_reg = 0;
 699   int i;
 700   basic_block bb;
 701   unsigned int r;
 702   int last_label_ruid;
 703   int min_labelno, n_labels;
 704   HARD_REG_SET ever_live_at_start, *label_live;
 705
 706   /* If reg+reg can be used in offsetable memory addresses, the main chunk of
 707      reload has already used it where appropriate, so there is no use in
 708      trying to generate it now.  */
 709   if (double_reg_address_ok && INDEX_REG_CLASS != NO_REGS)
 710     return;
 711
 712   /* To avoid wasting too much time later searching for an index register,
 713      determine the minimum and maximum index register numbers.  */
 714   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 715     if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], r))
 716       {
 717         if (first_index_reg == -1)
 718           first_index_reg = r;
 719
 720         last_index_reg = r;
 721       }
 722
 723   /* If no index register is available, we can quit now.  */
 724   if (first_index_reg == -1)
 725     return;
 726
 727   /* Set up LABEL_LIVE and EVER_LIVE_AT_START.  The register lifetime
 728      information is a bit fuzzy immediately after reload, but it's
 729      still good enough to determine which registers are live at a jump
 730      destination.  */
 731   min_labelno = get_first_label_num ();
 732   n_labels = max_label_num () - min_labelno;
 733   label_live = xmalloc (n_labels * sizeof (HARD_REG_SET));
 734   CLEAR_HARD_REG_SET (ever_live_at_start);
 735
 736   FOR_EACH_BB_REVERSE (bb)
 737     {
 738       insn = BB_HEAD (bb);
 739       if (LABEL_P (insn))
 740         {
 741           HARD_REG_SET live;
 742
 743           REG_SET_TO_HARD_REG_SET (live,
 744                                    bb->il.rtl->global_live_at_start);
 745           compute_use_by_pseudos (&live,
 746                                   bb->il.rtl->global_live_at_start);
 747           COPY_HARD_REG_SET (LABEL_LIVE (insn), live);
 748           IOR_HARD_REG_SET (ever_live_at_start, live);
 749         }
 750     }
 751
 752   /* Initialize last_label_ruid, reload_combine_ruid and reg_state.  */
 753   last_label_ruid = reload_combine_ruid = 0;
 754   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 755     {
 756       reg_state[r].store_ruid = reload_combine_ruid;
 757       if (fixed_regs[r])
 758         reg_state[r].use_index = -1;
 759       else
 760         reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
 761     }
 762
 763   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
 764     {
 765       rtx note;
 766
 767       /* We cannot do our optimization across labels.  Invalidating all the use
 768          information we have would be costly, so we just note where the label
 769          is and then later disable any optimization that would cross it.  */
 770       if (LABEL_P (insn))
 771         last_label_ruid = reload_combine_ruid;
 772       else if (BARRIER_P (insn))
 773         for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 774           if (! fixed_regs[r])
 775               reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
 776
 777       if (! INSN_P (insn))
 778         continue;
 779
 780       reload_combine_ruid++;
 781
 782       /* Look for (set (REGX) (CONST_INT))
 783          (set (REGX) (PLUS (REGX) (REGY)))
 784          ...
 785          ... (MEM (REGX)) ...
 786          and convert it to
 787          (set (REGZ) (CONST_INT))
 788          ...
 789          ... (MEM (PLUS (REGZ) (REGY)))... .
 790
 791          First, check that we have (set (REGX) (PLUS (REGX) (REGY)))
 792          and that we know all uses of REGX before it dies.
 793          Also, explicitly check that REGX != REGY; our life information
 794          does not yet show whether REGY changes in this insn.  */
 795       set = single_set (insn);
 796       if (set != NULL_RTX
 797           && REG_P (SET_DEST (set))
 798           && (hard_regno_nregs[REGNO (SET_DEST (set))]
 799                               [GET_MODE (SET_DEST (set))]
 800               == 1)
 801           && GET_CODE (SET_SRC (set)) == PLUS
 802           && REG_P (XEXP (SET_SRC (set), 1))
 803           && rtx_equal_p (XEXP (SET_SRC (set), 0), SET_DEST (set))
 804           && !rtx_equal_p (XEXP (SET_SRC (set), 1), SET_DEST (set))
 805           && last_label_ruid < reg_state[REGNO (SET_DEST (set))].use_ruid)
 806         {
 807           rtx reg = SET_DEST (set);
 808           rtx plus = SET_SRC (set);
 809           rtx base = XEXP (plus, 1);
 810           rtx prev = prev_nonnote_insn (insn);
 811           rtx prev_set = prev ? single_set (prev) : NULL_RTX;
 812           unsigned int regno = REGNO (reg);
 813           rtx const_reg = NULL_RTX;
 814           rtx reg_sum = NULL_RTX;
 815
 816           /* Now, we need an index register.
 817              We'll set index_reg to this index register, const_reg to the
 818              register that is to be loaded with the constant
 819              (denoted as REGZ in the substitution illustration above),
 820              and reg_sum to the register-register that we want to use to
 821              substitute uses of REG (typically in MEMs) with.
 822              First check REG and BASE for being index registers;
 823              we can use them even if they are not dead.  */
 824           if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], regno)
 825               || TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS],
 826                                     REGNO (base)))
 827             {
 828               const_reg = reg;
 829               reg_sum = plus;
 830             }
 831           else
 832             {
 833               /* Otherwise, look for a free index register.  Since we have
 834                  checked above that neither REG nor BASE are index registers,
 835                  if we find anything at all, it will be different from these
 836                  two registers.  */
 837               for (i = first_index_reg; i <= last_index_reg; i++)
 838                 {
 839                   if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS],
 840                                          i)
 841                       && reg_state[i].use_index == RELOAD_COMBINE_MAX_USES
 842                       && reg_state[i].store_ruid <= reg_state[regno].use_ruid
 843                       && hard_regno_nregs[i][GET_MODE (reg)] == 1)
 844                     {
 845                       rtx index_reg = gen_rtx_REG (GET_MODE (reg), i);
 846
 847                       const_reg = index_reg;
 848                       reg_sum = gen_rtx_PLUS (GET_MODE (reg), index_reg, base);
 849                       break;
 850                     }
 851                 }
 852             }
 853
 854           /* Check that PREV_SET is indeed (set (REGX) (CONST_INT)) and that
 855              (REGY), i.e. BASE, is not clobbered before the last use we'll
 856              create.  */
 857           if (prev_set != 0
 858               && GET_CODE (SET_SRC (prev_set)) == CONST_INT
 859               && rtx_equal_p (SET_DEST (prev_set), reg)
 860               && reg_state[regno].use_index >= 0
 861               && (reg_state[REGNO (base)].store_ruid
 862                   <= reg_state[regno].use_ruid)
 863               && reg_sum != 0)
 864             {
 865               int i;
 866
 867               /* Change destination register and, if necessary, the
 868                  constant value in PREV, the constant loading instruction.  */
 869               validate_change (prev, &SET_DEST (prev_set), const_reg, 1);
 870               if (reg_state[regno].offset != const0_rtx)
 871                 validate_change (prev,
 872                                  &SET_SRC (prev_set),
 873                                  GEN_INT (INTVAL (SET_SRC (prev_set))
 874                                           + INTVAL (reg_state[regno].offset)),
 875                                  1);
 876
 877               /* Now for every use of REG that we have recorded, replace REG
 878                  with REG_SUM.  */
 879               for (i = reg_state[regno].use_index;
 880                    i < RELOAD_COMBINE_MAX_USES; i++)
 881                 validate_change (reg_state[regno].reg_use[i].insn,
 882                                  reg_state[regno].reg_use[i].usep,
 883                                  /* Each change must have its own
 884                                     replacement.  */
 885                                  copy_rtx (reg_sum), 1);
 886
 887               if (apply_change_group ())
 888                 {
 889                   rtx *np;
 890
 891                   /* Delete the reg-reg addition.  */
 892                   delete_insn (insn);
 893
 894                   if (reg_state[regno].offset != const0_rtx)
 895                     /* Previous REG_EQUIV / REG_EQUAL notes for PREV
 896                        are now invalid.  */
 897                     for (np = &REG_NOTES (prev); *np;)
 898                       {
 899                         if (REG_NOTE_KIND (*np) == REG_EQUAL
 900                             || REG_NOTE_KIND (*np) == REG_EQUIV)
 901                           *np = XEXP (*np, 1);
 902                         else
 903                           np = &XEXP (*np, 1);
 904                       }
 905
 906                   reg_state[regno].use_index = RELOAD_COMBINE_MAX_USES;
 907                   reg_state[REGNO (const_reg)].store_ruid
 908                     = reload_combine_ruid;
 909                   continue;
 910                 }
 911             }
 912         }
 913
 914       note_stores (PATTERN (insn), reload_combine_note_store, NULL);
 915
 916       if (CALL_P (insn))
 917         {
 918           rtx link;
 919
 920           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 921             if (call_used_regs[r])
 922               {
 923                 reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
 924                 reg_state[r].store_ruid = reload_combine_ruid;
 925               }
 926
 927           for (link = CALL_INSN_FUNCTION_USAGE (insn); link;
 928                link = XEXP (link, 1))
 929             {
 930               rtx usage_rtx = XEXP (XEXP (link, 0), 0);
 931               if (REG_P (usage_rtx))
 932                 {
 933                   unsigned int i;
 934                   unsigned int start_reg = REGNO (usage_rtx);
 935                   unsigned int num_regs =
 936                         hard_regno_nregs[start_reg][GET_MODE (usage_rtx)];
 937                   unsigned int end_reg  = start_reg + num_regs - 1;
 938                   for (i = start_reg; i <= end_reg; i++)
 939                     if (GET_CODE (XEXP (link, 0)) == CLOBBER)
 940                       {
 941                         reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
 942                         reg_state[i].store_ruid = reload_combine_ruid;
 943                       }
 944                     else
 945                       reg_state[i].use_index = -1;
 946                  }
 947              }
 948
 949         }
 950       else if (JUMP_P (insn)
 951                && GET_CODE (PATTERN (insn)) != RETURN)
 952         {
 953           /* Non-spill registers might be used at the call destination in
 954              some unknown fashion, so we have to mark the unknown use.  */
 955           HARD_REG_SET *live;
 956
 957           if ((condjump_p (insn) || condjump_in_parallel_p (insn))
 958               && JUMP_LABEL (insn))
 959             live = &LABEL_LIVE (JUMP_LABEL (insn));
 960           else
 961             live = &ever_live_at_start;
 962
 963           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; --i)
 964             if (TEST_HARD_REG_BIT (*live, i))
 965               reg_state[i].use_index = -1;
 966         }
 967
 968       reload_combine_note_use (&PATTERN (insn), insn);
 969       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 970         {
 971           if (REG_NOTE_KIND (note) == REG_INC
 972               && REG_P (XEXP (note, 0)))
 973             {
 974               int regno = REGNO (XEXP (note, 0));
 975
 976               reg_state[regno].store_ruid = reload_combine_ruid;
 977               reg_state[regno].use_index = -1;
 978             }
 979         }
 980     }
 981
 982   free (label_live);
 983 }
 984
 985 /* Check if DST is a register or a subreg of a register; if it is,
 986    update reg_state[regno].store_ruid and reg_state[regno].use_index
 987    accordingly.  Called via note_stores from reload_combine.  */
 988
 989 static void
 990 reload_combine_note_store (rtx dst, rtx set, void *data ATTRIBUTE_UNUSED)
 991 {
 992   int regno = 0;
 993   int i;
 994   enum machine_mode mode = GET_MODE (dst);
 995
 996   if (GET_CODE (dst) == SUBREG)
 997     {
 998       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
 999                                    GET_MODE (SUBREG_REG (dst)),
1000                                    SUBREG_BYTE (dst),
1001                                    GET_MODE (dst));
1002       dst = SUBREG_REG (dst);
1003     }
1004   if (!REG_P (dst))
1005     return;
1006   regno += REGNO (dst);
1007
1008   /* note_stores might have stripped a STRICT_LOW_PART, so we have to be
1009      careful with registers / register parts that are not full words.
1010      Similarly for ZERO_EXTRACT.  */
1011   if (GET_CODE (set) != SET
1012       || GET_CODE (SET_DEST (set)) == ZERO_EXTRACT
1013       || GET_CODE (SET_DEST (set)) == STRICT_LOW_PART)
1014     {
1015       for (i = hard_regno_nregs[regno][mode] - 1 + regno; i >= regno; i--)
1016         {
1017           reg_state[i].use_index = -1;
1018           reg_state[i].store_ruid = reload_combine_ruid;
1019         }
1020     }
1021   else
1022     {
1023       for (i = hard_regno_nregs[regno][mode] - 1 + regno; i >= regno; i--)
1024         {
1025           reg_state[i].store_ruid = reload_combine_ruid;
1026           reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
1027         }
1028     }
1029 }
1030
1031 /* XP points to a piece of rtl that has to be checked for any uses of
1032    registers.
1033    *XP is the pattern of INSN, or a part of it.
1034    Called from reload_combine, and recursively by itself.  */
1035 static void
1036 reload_combine_note_use (rtx *xp, rtx insn)
1037 {
1038   rtx x = *xp;
1039   enum rtx_code code = x->code;
1040   const char *fmt;
1041   int i, j;
1042   rtx offset = const0_rtx; /* For the REG case below.  */
1043
1044   switch (code)
1045     {
1046     case SET:
1047       if (REG_P (SET_DEST (x)))
1048         {
1049           reload_combine_note_use (&SET_SRC (x), insn);
1050           return;
1051         }
1052       break;
1053
1054     case USE:
1055       /* If this is the USE of a return value, we can't change it.  */
1056       if (REG_P (XEXP (x, 0)) && REG_FUNCTION_VALUE_P (XEXP (x, 0)))
1057         {
1058         /* Mark the return register as used in an unknown fashion.  */
1059           rtx reg = XEXP (x, 0);
1060           int regno = REGNO (reg);
1061           int nregs = hard_regno_nregs[regno][GET_MODE (reg)];
1062
1063           while (--nregs >= 0)
1064             reg_state[regno + nregs].use_index = -1;
1065           return;
1066         }
1067       break;
1068
1069     case CLOBBER:
1070       if (REG_P (SET_DEST (x)))
1071         {
1072           /* No spurious CLOBBERs of pseudo registers may remain.  */
1073           gcc_assert (REGNO (SET_DEST (x)) < FIRST_PSEUDO_REGISTER);
1074           return;
1075         }
1076       break;
1077
1078     case PLUS:
1079       /* We are interested in (plus (reg) (const_int)) .  */
1080       if (!REG_P (XEXP (x, 0))
1081           || GET_CODE (XEXP (x, 1)) != CONST_INT)
1082         break;
1083       offset = XEXP (x, 1);
1084       x = XEXP (x, 0);
1085       /* Fall through.  */
1086     case REG:
1087       {
1088         int regno = REGNO (x);
1089         int use_index;
1090         int nregs;
1091
1092         /* No spurious USEs of pseudo registers may remain.  */
1093         gcc_assert (regno < FIRST_PSEUDO_REGISTER);
1094
1095         nregs = hard_regno_nregs[regno][GET_MODE (x)];
1096
1097         /* We can't substitute into multi-hard-reg uses.  */
1098         if (nregs > 1)
1099           {
1100             while (--nregs >= 0)
1101               reg_state[regno + nregs].use_index = -1;
1102             return;
1103           }
1104
1105         /* If this register is already used in some unknown fashion, we
1106            can't do anything.
1107            If we decrement the index from zero to -1, we can't store more
1108            uses, so this register becomes used in an unknown fashion.  */
1109         use_index = --reg_state[regno].use_index;
1110         if (use_index < 0)
1111           return;
1112
1113         if (use_index != RELOAD_COMBINE_MAX_USES - 1)
1114           {
1115             /* We have found another use for a register that is already
1116                used later.  Check if the offsets match; if not, mark the
1117                register as used in an unknown fashion.  */
1118             if (! rtx_equal_p (offset, reg_state[regno].offset))
1119               {
1120                 reg_state[regno].use_index = -1;
1121                 return;
1122               }
1123           }
1124         else
1125           {
1126             /* This is the first use of this register we have seen since we
1127                marked it as dead.  */
1128             reg_state[regno].offset = offset;
1129             reg_state[regno].use_ruid = reload_combine_ruid;
1130           }
1131         reg_state[regno].reg_use[use_index].insn = insn;
1132         reg_state[regno].reg_use[use_index].usep = xp;
1133         return;
1134       }
1135
1136     default:
1137       break;
1138     }
1139
1140   /* Recursively process the components of X.  */
1141   fmt = GET_RTX_FORMAT (code);
1142   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1143     {
1144       if (fmt[i] == 'e')
1145         reload_combine_note_use (&XEXP (x, i), insn);
1146       else if (fmt[i] == 'E')
1147         {
1148           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1149             reload_combine_note_use (&XVECEXP (x, i, j), insn);
1150         }
1151     }
1152 }
1153 \f
1154 /* See if we can reduce the cost of a constant by replacing a move
1155    with an add.  We track situations in which a register is set to a
1156    constant or to a register plus a constant.  */
1157 /* We cannot do our optimization across labels.  Invalidating all the
1158    information about register contents we have would be costly, so we
1159    use move2add_last_label_luid to note where the label is and then
1160    later disable any optimization that would cross it.
1161    reg_offset[n] / reg_base_reg[n] / reg_mode[n] are only valid if
1162    reg_set_luid[n] is greater than move2add_last_label_luid.  */
1163 static int reg_set_luid[FIRST_PSEUDO_REGISTER];
1164
1165 /* If reg_base_reg[n] is negative, register n has been set to
1166    reg_offset[n] in mode reg_mode[n] .
1167    If reg_base_reg[n] is non-negative, register n has been set to the
1168    sum of reg_offset[n] and the value of register reg_base_reg[n]
1169    before reg_set_luid[n], calculated in mode reg_mode[n] .  */
1170 static HOST_WIDE_INT reg_offset[FIRST_PSEUDO_REGISTER];
1171 static int reg_base_reg[FIRST_PSEUDO_REGISTER];
1172 static enum machine_mode reg_mode[FIRST_PSEUDO_REGISTER];
1173
1174 /* move2add_luid is linearly increased while scanning the instructions
1175    from first to last.  It is used to set reg_set_luid in
1176    reload_cse_move2add and move2add_note_store.  */
1177 static int move2add_luid;
1178
1179 /* move2add_last_label_luid is set whenever a label is found.  Labels
1180    invalidate all previously collected reg_offset data.  */
1181 static int move2add_last_label_luid;
1182
1183 /* ??? We don't know how zero / sign extension is handled, hence we
1184    can't go from a narrower to a wider mode.  */
1185 #define MODES_OK_FOR_MOVE2ADD(OUTMODE, INMODE) \
1186   (GET_MODE_SIZE (OUTMODE) == GET_MODE_SIZE (INMODE) \
1187    || (GET_MODE_SIZE (OUTMODE) <= GET_MODE_SIZE (INMODE) \
1188        && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (OUTMODE), \
1189                                  GET_MODE_BITSIZE (INMODE))))
1190
1191 static void
1192 reload_cse_move2add (rtx first)
1193 {
1194   int i;
1195   rtx insn;
1196
1197   for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1198     reg_set_luid[i] = 0;
1199
1200   move2add_last_label_luid = 0;
1201   move2add_luid = 2;
1202   for (insn = first; insn; insn = NEXT_INSN (insn), move2add_luid++)
1203     {
1204       rtx pat, note;
1205
1206       if (LABEL_P (insn))
1207         {
1208           move2add_last_label_luid = move2add_luid;
1209           /* We're going to increment move2add_luid twice after a
1210              label, so that we can use move2add_last_label_luid + 1 as
1211              the luid for constants.  */
1212           move2add_luid++;
1213           continue;
1214         }
1215       if (! INSN_P (insn))
1216         continue;
1217       pat = PATTERN (insn);
1218       /* For simplicity, we only perform this optimization on
1219          straightforward SETs.  */
1220       if (GET_CODE (pat) == SET
1221           && REG_P (SET_DEST (pat)))
1222         {
1223           rtx reg = SET_DEST (pat);
1224           int regno = REGNO (reg);
1225           rtx src = SET_SRC (pat);
1226
1227           /* Check if we have valid information on the contents of this
1228              register in the mode of REG.  */
1229           if (reg_set_luid[regno] > move2add_last_label_luid
1230               && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg), reg_mode[regno]))
1231             {
1232               /* Try to transform (set (REGX) (CONST_INT A))
1233                                   ...
1234                                   (set (REGX) (CONST_INT B))
1235                  to
1236                                   (set (REGX) (CONST_INT A))
1237                                   ...
1238                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))
1239                  or
1240                                   (set (REGX) (CONST_INT A))
1241                                   ...
1242                                   (set (STRICT_LOW_PART (REGX)) (CONST_INT B))
1243               */
1244
1245               if (GET_CODE (src) == CONST_INT && reg_base_reg[regno] < 0)
1246                 {
1247                   rtx new_src = gen_int_mode (INTVAL (src) - reg_offset[regno],
1248                                               GET_MODE (reg));
1249                   /* (set (reg) (plus (reg) (const_int 0))) is not canonical;
1250                      use (set (reg) (reg)) instead.
1251                      We don't delete this insn, nor do we convert it into a
1252                      note, to avoid losing register notes or the return
1253                      value flag.  jump2 already knows how to get rid of
1254                      no-op moves.  */
1255                   if (new_src == const0_rtx)
1256                     {
1257                       /* If the constants are different, this is a
1258                          truncation, that, if turned into (set (reg)
1259                          (reg)), would be discarded.  Maybe we should
1260                          try a truncMN pattern?  */
1261                       if (INTVAL (src) == reg_offset [regno])
1262                         validate_change (insn, &SET_SRC (pat), reg, 0);
1263                     }
1264                   else if (rtx_cost (new_src, PLUS) < rtx_cost (src, SET)
1265                            && have_add2_insn (reg, new_src))
1266                     {
1267                       rtx tem = gen_rtx_PLUS (GET_MODE (reg), reg, new_src);
1268                       validate_change (insn, &SET_SRC (pat), tem, 0);
1269                     }
1270                   else
1271                     {
1272                       enum machine_mode narrow_mode;
1273                       for (narrow_mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
1274                            narrow_mode != VOIDmode
1275                            && narrow_mode != GET_MODE (reg);
1276                            narrow_mode = GET_MODE_WIDER_MODE (narrow_mode))
1277                         {
1278                           if (have_insn_for (STRICT_LOW_PART, narrow_mode)
1279                               && ((reg_offset[regno]
1280                                    & ~GET_MODE_MASK (narrow_mode))
1281                                   == (INTVAL (src)
1282                                       & ~GET_MODE_MASK (narrow_mode))))
1283                             {
1284                               rtx narrow_reg = gen_rtx_REG (narrow_mode,
1285                                                             REGNO (reg));
1286                               rtx narrow_src = gen_int_mode (INTVAL (src),
1287                                                              narrow_mode);
1288                               rtx new_set =
1289                                 gen_rtx_SET (VOIDmode,
1290                                              gen_rtx_STRICT_LOW_PART (VOIDmode,
1291                                                                       narrow_reg),
1292                                              narrow_src);
1293                               if (validate_change (insn, &PATTERN (insn),
1294                                                    new_set, 0))
1295                                 break;
1296                             }
1297                         }
1298                     }
1299                   reg_set_luid[regno] = move2add_luid;
1300                   reg_mode[regno] = GET_MODE (reg);
1301                   reg_offset[regno] = INTVAL (src);
1302                   continue;
1303                 }
1304
1305               /* Try to transform (set (REGX) (REGY))
1306                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1307                                   ...
1308                                   (set (REGX) (REGY))
1309                                   (set (REGX) (PLUS (REGX) (CONST_INT B)))
1310                  to
1311                                   (set (REGX) (REGY))
1312                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1313                                   ...
1314                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))  */
1315               else if (REG_P (src)
1316                        && reg_set_luid[regno] == reg_set_luid[REGNO (src)]
1317                        && reg_base_reg[regno] == reg_base_reg[REGNO (src)]
1318                        && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg),
1319                                                  reg_mode[REGNO (src)]))
1320                 {
1321                   rtx next = next_nonnote_insn (insn);
1322                   rtx set = NULL_RTX;
1323                   if (next)
1324                     set = single_set (next);
1325                   if (set
1326                       && SET_DEST (set) == reg
1327                       && GET_CODE (SET_SRC (set)) == PLUS
1328                       && XEXP (SET_SRC (set), 0) == reg
1329                       && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1330                     {
1331                       rtx src3 = XEXP (SET_SRC (set), 1);
1332                       HOST_WIDE_INT added_offset = INTVAL (src3);
1333                       HOST_WIDE_INT base_offset = reg_offset[REGNO (src)];
1334                       HOST_WIDE_INT regno_offset = reg_offset[regno];
1335                       rtx new_src =
1336                         gen_int_mode (added_offset
1337                                       + base_offset
1338                                       - regno_offset,
1339                                       GET_MODE (reg));
1340                       int success = 0;
1341
1342                       if (new_src == const0_rtx)
1343                         /* See above why we create (set (reg) (reg)) here.  */
1344                         success
1345                           = validate_change (next, &SET_SRC (set), reg, 0);
1346                       else if ((rtx_cost (new_src, PLUS)
1347                                 < COSTS_N_INSNS (1) + rtx_cost (src3, SET))
1348                                && have_add2_insn (reg, new_src))
1349                         {
1350                           rtx newpat = gen_rtx_SET (VOIDmode,
1351                                                     reg,
1352                                                     gen_rtx_PLUS (GET_MODE (reg),
1353                                                                   reg,
1354                                                                   new_src));
1355                           success
1356                             = validate_change (next, &PATTERN (next),
1357                                                newpat, 0);
1358                         }
1359                       if (success)
1360                         delete_insn (insn);
1361                       insn = next;
1362                       reg_mode[regno] = GET_MODE (reg);
1363                       reg_offset[regno] =
1364                         trunc_int_for_mode (added_offset + base_offset,
1365                                             GET_MODE (reg));
1366                       continue;
1367                     }
1368                 }
1369             }
1370         }
1371
1372       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1373         {
1374           if (REG_NOTE_KIND (note) == REG_INC
1375               && REG_P (XEXP (note, 0)))
1376             {
1377               /* Reset the information about this register.  */
1378               int regno = REGNO (XEXP (note, 0));
1379               if (regno < FIRST_PSEUDO_REGISTER)
1380                 reg_set_luid[regno] = 0;
1381             }
1382         }
1383       note_stores (PATTERN (insn), move2add_note_store, NULL);
1384
1385       /* If INSN is a conditional branch, we try to extract an
1386          implicit set out of it.  */
1387       if (any_condjump_p (insn))
1388         {
1389           rtx cnd = fis_get_condition (insn);
1390
1391           if (cnd != NULL_RTX
1392               && GET_CODE (cnd) == NE
1393               && REG_P (XEXP (cnd, 0))
1394               && !reg_set_p (XEXP (cnd, 0), insn)
1395               /* The following two checks, which are also in
1396                  move2add_note_store, are intended to reduce the
1397                  number of calls to gen_rtx_SET to avoid memory
1398                  allocation if possible.  */
1399               && SCALAR_INT_MODE_P (GET_MODE (XEXP (cnd, 0)))
1400               && hard_regno_nregs[REGNO (XEXP (cnd, 0))][GET_MODE (XEXP (cnd, 0))] == 1
1401               && GET_CODE (XEXP (cnd, 1)) == CONST_INT)
1402             {
1403               rtx implicit_set =
1404                 gen_rtx_SET (VOIDmode, XEXP (cnd, 0), XEXP (cnd, 1));
1405               move2add_note_store (SET_DEST (implicit_set), implicit_set, 0);
1406             }
1407         }
1408
1409       /* If this is a CALL_INSN, all call used registers are stored with
1410          unknown values.  */
1411       if (CALL_P (insn))
1412         {
1413           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1414             {
1415               if (call_used_regs[i])
1416                 /* Reset the information about this register.  */
1417                 reg_set_luid[i] = 0;
1418             }
1419         }
1420     }
1421 }
1422
1423 /* SET is a SET or CLOBBER that sets DST.
1424    Update reg_set_luid, reg_offset and reg_base_reg accordingly.
1425    Called from reload_cse_move2add via note_stores.  */
1426
1427 static void
1428 move2add_note_store (rtx dst, rtx set, void *data ATTRIBUTE_UNUSED)
1429 {
1430   unsigned int regno = 0;
1431   unsigned int i;
1432   enum machine_mode mode = GET_MODE (dst);
1433
1434   if (GET_CODE (dst) == SUBREG)
1435     {
1436       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
1437                                    GET_MODE (SUBREG_REG (dst)),
1438                                    SUBREG_BYTE (dst),
1439                                    GET_MODE (dst));
1440       dst = SUBREG_REG (dst);
1441     }
1442
1443   /* Some targets do argument pushes without adding REG_INC notes.  */
1444
1445   if (MEM_P (dst))
1446     {
1447       dst = XEXP (dst, 0);
1448       if (GET_CODE (dst) == PRE_INC || GET_CODE (dst) == POST_INC
1449           || GET_CODE (dst) == PRE_DEC || GET_CODE (dst) == POST_DEC)
1450         reg_set_luid[REGNO (XEXP (dst, 0))] = 0;
1451       return;
1452     }
1453   if (!REG_P (dst))
1454     return;
1455
1456   regno += REGNO (dst);
1457
1458   if (SCALAR_INT_MODE_P (GET_MODE (dst))
1459       && hard_regno_nregs[regno][mode] == 1 && GET_CODE (set) == SET
1460       && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
1461       && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
1462     {
1463       rtx src = SET_SRC (set);
1464       rtx base_reg;
1465       HOST_WIDE_INT offset;
1466       int base_regno;
1467       /* This may be different from mode, if SET_DEST (set) is a
1468          SUBREG.  */
1469       enum machine_mode dst_mode = GET_MODE (dst);
1470
1471       switch (GET_CODE (src))
1472         {
1473         case PLUS:
1474           if (REG_P (XEXP (src, 0)))
1475             {
1476               base_reg = XEXP (src, 0);
1477
1478               if (GET_CODE (XEXP (src, 1)) == CONST_INT)
1479                 offset = INTVAL (XEXP (src, 1));
1480               else if (REG_P (XEXP (src, 1))
1481                        && (reg_set_luid[REGNO (XEXP (src, 1))]
1482                            > move2add_last_label_luid)
1483                        && (MODES_OK_FOR_MOVE2ADD
1484                            (dst_mode, reg_mode[REGNO (XEXP (src, 1))])))
1485                 {
1486                   if (reg_base_reg[REGNO (XEXP (src, 1))] < 0)
1487                     offset = reg_offset[REGNO (XEXP (src, 1))];
1488                   /* Maybe the first register is known to be a
1489                      constant.  */
1490                   else if (reg_set_luid[REGNO (base_reg)]
1491                            > move2add_last_label_luid
1492                            && (MODES_OK_FOR_MOVE2ADD
1493                                (dst_mode, reg_mode[REGNO (XEXP (src, 1))]))
1494                            && reg_base_reg[REGNO (base_reg)] < 0)
1495                     {
1496                       offset = reg_offset[REGNO (base_reg)];
1497                       base_reg = XEXP (src, 1);
1498                     }
1499                   else
1500                     goto invalidate;
1501                 }
1502               else
1503                 goto invalidate;
1504
1505               break;
1506             }
1507
1508           goto invalidate;
1509
1510         case REG:
1511           base_reg = src;
1512           offset = 0;
1513           break;
1514
1515         case CONST_INT:
1516           /* Start tracking the register as a constant.  */
1517           reg_base_reg[regno] = -1;
1518           reg_offset[regno] = INTVAL (SET_SRC (set));
1519           /* We assign the same luid to all registers set to constants.  */
1520           reg_set_luid[regno] = move2add_last_label_luid + 1;
1521           reg_mode[regno] = mode;
1522           return;
1523
1524         default:
1525         invalidate:
1526           /* Invalidate the contents of the register.  */
1527           reg_set_luid[regno] = 0;
1528           return;
1529         }
1530
1531       base_regno = REGNO (base_reg);
1532       /* If information about the base register is not valid, set it
1533          up as a new base register, pretending its value is known
1534          starting from the current insn.  */
1535       if (reg_set_luid[base_regno] <= move2add_last_label_luid)
1536         {
1537           reg_base_reg[base_regno] = base_regno;
1538           reg_offset[base_regno] = 0;
1539           reg_set_luid[base_regno] = move2add_luid;
1540           reg_mode[base_regno] = mode;
1541         }
1542       else if (! MODES_OK_FOR_MOVE2ADD (dst_mode,
1543                                         reg_mode[base_regno]))
1544         goto invalidate;
1545
1546       reg_mode[regno] = mode;
1547
1548       /* Copy base information from our base register.  */
1549       reg_set_luid[regno] = reg_set_luid[base_regno];
1550       reg_base_reg[regno] = reg_base_reg[base_regno];
1551
1552       /* Compute the sum of the offsets or constants.  */
1553       reg_offset[regno] = trunc_int_for_mode (offset
1554                                               + reg_offset[base_regno],
1555                                               dst_mode);
1556     }
1557   else
1558     {
1559       unsigned int endregno = regno + hard_regno_nregs[regno][mode];
1560
1561       for (i = regno; i < endregno; i++)
1562         /* Reset the information about this register.  */
1563         reg_set_luid[i] = 0;
1564     }
1565 }
1566 \f
1567 static bool
1568 gate_handle_postreload (void)
1569 {
1570   return (optimize > 0);
1571 }
1572
1573
1574 static void
1575 rest_of_handle_postreload (void)
1576 {
1577   /* Do a very simple CSE pass over just the hard registers.  */
1578   reload_cse_regs (get_insns ());
1579   /* reload_cse_regs can eliminate potentially-trapping MEMs.
1580      Remove any EH edges associated with them.  */
1581   if (flag_non_call_exceptions)
1582     purge_all_dead_edges ();
1583 }
1584
1585 struct tree_opt_pass pass_postreload_cse =
1586 {
1587   "postreload",                         /* name */
1588   gate_handle_postreload,               /* gate */
1589   rest_of_handle_postreload,            /* execute */
1590   NULL,                                 /* sub */
1591   NULL,                                 /* next */
1592   0,                                    /* static_pass_number */
1593   TV_RELOAD_CSE_REGS,                   /* tv_id */
1594   0,                                    /* properties_required */
1595   0,                                    /* properties_provided */
1596   0,                                    /* properties_destroyed */
1597   0,                                    /* todo_flags_start */
1598   TODO_dump_func,                       /* todo_flags_finish */
1599   'o'                                   /* letter */
1600 };
1601