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