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                   class = (int) NO_REGS;
 579                   break;
 580                 }
 581               p += CONSTRAINT_LEN (c, p);
 582
 583               if (c == '\0')
 584                 break;
 585             }
 586         }
 587     }
 588
 589   /* Record all alternatives which are better or equal to the currently
 590      matching one in the alternative_order array.  */
 591   for (i = j = 0; i < recog_data.n_alternatives; i++)
 592     if (alternative_reject[i] <= alternative_reject[which_alternative])
 593       alternative_order[j++] = i;
 594   recog_data.n_alternatives = j;
 595
 596   /* Sort it.  Given a small number of alternatives, a dumb algorithm
 597      won't hurt too much.  */
 598   for (i = 0; i < recog_data.n_alternatives - 1; i++)
 599     {
 600       int best = i;
 601       int best_reject = alternative_reject[alternative_order[i]];
 602       int best_nregs = alternative_nregs[alternative_order[i]];
 603       int tmp;
 604
 605       for (j = i + 1; j < recog_data.n_alternatives; j++)
 606         {
 607           int this_reject = alternative_reject[alternative_order[j]];
 608           int this_nregs = alternative_nregs[alternative_order[j]];
 609
 610           if (this_reject < best_reject
 611               || (this_reject == best_reject && this_nregs > best_nregs))
 612             {
 613               best = j;
 614               best_reject = this_reject;
 615               best_nregs = this_nregs;
 616             }
 617         }
 618
 619       tmp = alternative_order[best];
 620       alternative_order[best] = alternative_order[i];
 621       alternative_order[i] = tmp;
 622     }
 623
 624   /* Substitute the operands as determined by op_alt_regno for the best
 625      alternative.  */
 626   j = alternative_order[0];
 627
 628   for (i = 0; i < recog_data.n_operands; i++)
 629     {
 630       enum machine_mode mode = recog_data.operand_mode[i];
 631       if (op_alt_regno[i][j] == -1)
 632         continue;
 633
 634       validate_change (insn, recog_data.operand_loc[i],
 635                        gen_rtx_REG (mode, op_alt_regno[i][j]), 1);
 636     }
 637
 638   for (i = recog_data.n_dups - 1; i >= 0; i--)
 639     {
 640       int op = recog_data.dup_num[i];
 641       enum machine_mode mode = recog_data.operand_mode[op];
 642
 643       if (op_alt_regno[op][j] == -1)
 644         continue;
 645
 646       validate_change (insn, recog_data.dup_loc[i],
 647                        gen_rtx_REG (mode, op_alt_regno[op][j]), 1);
 648     }
 649
 650   return apply_change_group ();
 651 }
 652 \f
 653 /* If reload couldn't use reg+reg+offset addressing, try to use reg+reg
 654    addressing now.
 655    This code might also be useful when reload gave up on reg+reg addressing
 656    because of clashes between the return register and INDEX_REG_CLASS.  */
 657
 658 /* The maximum number of uses of a register we can keep track of to
 659    replace them with reg+reg addressing.  */
 660 #define RELOAD_COMBINE_MAX_USES 6
 661
 662 /* INSN is the insn where a register has ben used, and USEP points to the
 663    location of the register within the rtl.  */
 664 struct reg_use { rtx insn, *usep; };
 665
 666 /* If the register is used in some unknown fashion, USE_INDEX is negative.
 667    If it is dead, USE_INDEX is RELOAD_COMBINE_MAX_USES, and STORE_RUID
 668    indicates where it becomes live again.
 669    Otherwise, USE_INDEX is the index of the last encountered use of the
 670    register (which is first among these we have seen since we scan backwards),
 671    OFFSET contains the constant offset that is added to the register in
 672    all encountered uses, and USE_RUID indicates the first encountered, i.e.
 673    last, of these uses.
 674    STORE_RUID is always meaningful if we only want to use a value in a
 675    register in a different place: it denotes the next insn in the insn
 676    stream (i.e. the last encountered) that sets or clobbers the register.  */
 677 static struct
 678   {
 679     struct reg_use reg_use[RELOAD_COMBINE_MAX_USES];
 680     int use_index;
 681     rtx offset;
 682     int store_ruid;
 683     int use_ruid;
 684   } reg_state[FIRST_PSEUDO_REGISTER];
 685
 686 /* Reverse linear uid.  This is increased in reload_combine while scanning
 687    the instructions from last to first.  It is used to set last_label_ruid
 688    and the store_ruid / use_ruid fields in reg_state.  */
 689 static int reload_combine_ruid;
 690
 691 #define LABEL_LIVE(LABEL) \
 692   (label_live[CODE_LABEL_NUMBER (LABEL) - min_labelno])
 693
 694 static void
 695 reload_combine (void)
 696 {
 697   rtx insn, set;
 698   int first_index_reg = -1;
 699   int last_index_reg = 0;
 700   int i;
 701   basic_block bb;
 702   unsigned int r;
 703   int last_label_ruid;
 704   int min_labelno, n_labels;
 705   HARD_REG_SET ever_live_at_start, *label_live;
 706
 707   /* If reg+reg can be used in offsetable memory addresses, the main chunk of
 708      reload has already used it where appropriate, so there is no use in
 709      trying to generate it now.  */
 710   if (double_reg_address_ok && INDEX_REG_CLASS != NO_REGS)
 711     return;
 712
 713   /* To avoid wasting too much time later searching for an index register,
 714      determine the minimum and maximum index register numbers.  */
 715   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 716     if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], r))
 717       {
 718         if (first_index_reg == -1)
 719           first_index_reg = r;
 720
 721         last_index_reg = r;
 722       }
 723
 724   /* If no index register is available, we can quit now.  */
 725   if (first_index_reg == -1)
 726     return;
 727
 728   /* Set up LABEL_LIVE and EVER_LIVE_AT_START.  The register lifetime
 729      information is a bit fuzzy immediately after reload, but it's
 730      still good enough to determine which registers are live at a jump
 731      destination.  */
 732   min_labelno = get_first_label_num ();
 733   n_labels = max_label_num () - min_labelno;
 734   label_live = XNEWVEC (HARD_REG_SET, n_labels);
 735   CLEAR_HARD_REG_SET (ever_live_at_start);
 736
 737   FOR_EACH_BB_REVERSE (bb)
 738     {
 739       insn = BB_HEAD (bb);
 740       if (LABEL_P (insn))
 741         {
 742           HARD_REG_SET live;
 743
 744           REG_SET_TO_HARD_REG_SET (live,
 745                                    bb->il.rtl->global_live_at_start);
 746           compute_use_by_pseudos (&live,
 747                                   bb->il.rtl->global_live_at_start);
 748           COPY_HARD_REG_SET (LABEL_LIVE (insn), live);
 749           IOR_HARD_REG_SET (ever_live_at_start, live);
 750         }
 751     }
 752
 753   /* Initialize last_label_ruid, reload_combine_ruid and reg_state.  */
 754   last_label_ruid = reload_combine_ruid = 0;
 755   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 756     {
 757       reg_state[r].store_ruid = reload_combine_ruid;
 758       if (fixed_regs[r])
 759         reg_state[r].use_index = -1;
 760       else
 761         reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
 762     }
 763
 764   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
 765     {
 766       rtx note;
 767
 768       /* We cannot do our optimization across labels.  Invalidating all the use
 769          information we have would be costly, so we just note where the label
 770          is and then later disable any optimization that would cross it.  */
 771       if (LABEL_P (insn))
 772         last_label_ruid = reload_combine_ruid;
 773       else if (BARRIER_P (insn))
 774         for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 775           if (! fixed_regs[r])
 776               reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
 777
 778       if (! INSN_P (insn))
 779         continue;
 780
 781       reload_combine_ruid++;
 782
 783       /* Look for (set (REGX) (CONST_INT))
 784          (set (REGX) (PLUS (REGX) (REGY)))
 785          ...
 786          ... (MEM (REGX)) ...
 787          and convert it to
 788          (set (REGZ) (CONST_INT))
 789          ...
 790          ... (MEM (PLUS (REGZ) (REGY)))... .
 791
 792          First, check that we have (set (REGX) (PLUS (REGX) (REGY)))
 793          and that we know all uses of REGX before it dies.
 794          Also, explicitly check that REGX != REGY; our life information
 795          does not yet show whether REGY changes in this insn.  */
 796       set = single_set (insn);
 797       if (set != NULL_RTX
 798           && REG_P (SET_DEST (set))
 799           && (hard_regno_nregs[REGNO (SET_DEST (set))]
 800                               [GET_MODE (SET_DEST (set))]
 801               == 1)
 802           && GET_CODE (SET_SRC (set)) == PLUS
 803           && REG_P (XEXP (SET_SRC (set), 1))
 804           && rtx_equal_p (XEXP (SET_SRC (set), 0), SET_DEST (set))
 805           && !rtx_equal_p (XEXP (SET_SRC (set), 1), SET_DEST (set))
 806           && last_label_ruid < reg_state[REGNO (SET_DEST (set))].use_ruid)
 807         {
 808           rtx reg = SET_DEST (set);
 809           rtx plus = SET_SRC (set);
 810           rtx base = XEXP (plus, 1);
 811           rtx prev = prev_nonnote_insn (insn);
 812           rtx prev_set = prev ? single_set (prev) : NULL_RTX;
 813           unsigned int regno = REGNO (reg);
 814           rtx const_reg = NULL_RTX;
 815           rtx reg_sum = NULL_RTX;
 816
 817           /* Now, we need an index register.
 818              We'll set index_reg to this index register, const_reg to the
 819              register that is to be loaded with the constant
 820              (denoted as REGZ in the substitution illustration above),
 821              and reg_sum to the register-register that we want to use to
 822              substitute uses of REG (typically in MEMs) with.
 823              First check REG and BASE for being index registers;
 824              we can use them even if they are not dead.  */
 825           if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], regno)
 826               || TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS],
 827                                     REGNO (base)))
 828             {
 829               const_reg = reg;
 830               reg_sum = plus;
 831             }
 832           else
 833             {
 834               /* Otherwise, look for a free index register.  Since we have
 835                  checked above that neither REG nor BASE are index registers,
 836                  if we find anything at all, it will be different from these
 837                  two registers.  */
 838               for (i = first_index_reg; i <= last_index_reg; i++)
 839                 {
 840                   if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS],
 841                                          i)
 842                       && reg_state[i].use_index == RELOAD_COMBINE_MAX_USES
 843                       && reg_state[i].store_ruid <= reg_state[regno].use_ruid
 844                       && hard_regno_nregs[i][GET_MODE (reg)] == 1)
 845                     {
 846                       rtx index_reg = gen_rtx_REG (GET_MODE (reg), i);
 847
 848                       const_reg = index_reg;
 849                       reg_sum = gen_rtx_PLUS (GET_MODE (reg), index_reg, base);
 850                       break;
 851                     }
 852                 }
 853             }
 854
 855           /* Check that PREV_SET is indeed (set (REGX) (CONST_INT)) and that
 856              (REGY), i.e. BASE, is not clobbered before the last use we'll
 857              create.  */
 858           if (prev_set != 0
 859               && GET_CODE (SET_SRC (prev_set)) == CONST_INT
 860               && rtx_equal_p (SET_DEST (prev_set), reg)
 861               && reg_state[regno].use_index >= 0
 862               && (reg_state[REGNO (base)].store_ruid
 863                   <= reg_state[regno].use_ruid)
 864               && reg_sum != 0)
 865             {
 866               int i;
 867
 868               /* Change destination register and, if necessary, the
 869                  constant value in PREV, the constant loading instruction.  */
 870               validate_change (prev, &SET_DEST (prev_set), const_reg, 1);
 871               if (reg_state[regno].offset != const0_rtx)
 872                 validate_change (prev,
 873                                  &SET_SRC (prev_set),
 874                                  GEN_INT (INTVAL (SET_SRC (prev_set))
 875                                           + INTVAL (reg_state[regno].offset)),
 876                                  1);
 877
 878               /* Now for every use of REG that we have recorded, replace REG
 879                  with REG_SUM.  */
 880               for (i = reg_state[regno].use_index;
 881                    i < RELOAD_COMBINE_MAX_USES; i++)
 882                 validate_change (reg_state[regno].reg_use[i].insn,
 883                                  reg_state[regno].reg_use[i].usep,
 884                                  /* Each change must have its own
 885                                     replacement.  */
 886                                  copy_rtx (reg_sum), 1);
 887
 888               if (apply_change_group ())
 889                 {
 890                   rtx *np;
 891
 892                   /* Delete the reg-reg addition.  */
 893                   delete_insn (insn);
 894
 895                   if (reg_state[regno].offset != const0_rtx)
 896                     /* Previous REG_EQUIV / REG_EQUAL notes for PREV
 897                        are now invalid.  */
 898                     for (np = &REG_NOTES (prev); *np;)
 899                       {
 900                         if (REG_NOTE_KIND (*np) == REG_EQUAL
 901                             || REG_NOTE_KIND (*np) == REG_EQUIV)
 902                           *np = XEXP (*np, 1);
 903                         else
 904                           np = &XEXP (*np, 1);
 905                       }
 906
 907                   reg_state[regno].use_index = RELOAD_COMBINE_MAX_USES;
 908                   reg_state[REGNO (const_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, 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           || GET_CODE (XEXP (x, 1)) != CONST_INT)
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             {
1233               /* Try to transform (set (REGX) (CONST_INT A))
1234                                   ...
1235                                   (set (REGX) (CONST_INT B))
1236                  to
1237                                   (set (REGX) (CONST_INT A))
1238                                   ...
1239                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))
1240                  or
1241                                   (set (REGX) (CONST_INT A))
1242                                   ...
1243                                   (set (STRICT_LOW_PART (REGX)) (CONST_INT B))
1244               */
1245
1246               if (GET_CODE (src) == CONST_INT && reg_base_reg[regno] < 0)
1247                 {
1248                   rtx new_src = gen_int_mode (INTVAL (src) - reg_offset[regno],
1249                                               GET_MODE (reg));
1250                   /* (set (reg) (plus (reg) (const_int 0))) is not canonical;
1251                      use (set (reg) (reg)) instead.
1252                      We don't delete this insn, nor do we convert it into a
1253                      note, to avoid losing register notes or the return
1254                      value flag.  jump2 already knows how to get rid of
1255                      no-op moves.  */
1256                   if (new_src == const0_rtx)
1257                     {
1258                       /* If the constants are different, this is a
1259                          truncation, that, if turned into (set (reg)
1260                          (reg)), would be discarded.  Maybe we should
1261                          try a truncMN pattern?  */
1262                       if (INTVAL (src) == reg_offset [regno])
1263                         validate_change (insn, &SET_SRC (pat), reg, 0);
1264                     }
1265                   else if (rtx_cost (new_src, PLUS) < rtx_cost (src, SET)
1266                            && have_add2_insn (reg, new_src))
1267                     {
1268                       rtx tem = gen_rtx_PLUS (GET_MODE (reg), reg, new_src);
1269                       validate_change (insn, &SET_SRC (pat), tem, 0);
1270                     }
1271                   else if (GET_MODE (reg) != BImode)
1272                     {
1273                       enum machine_mode narrow_mode;
1274                       for (narrow_mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
1275                            narrow_mode != VOIDmode
1276                            && narrow_mode != GET_MODE (reg);
1277                            narrow_mode = GET_MODE_WIDER_MODE (narrow_mode))
1278                         {
1279                           if (have_insn_for (STRICT_LOW_PART, narrow_mode)
1280                               && ((reg_offset[regno]
1281                                    & ~GET_MODE_MASK (narrow_mode))
1282                                   == (INTVAL (src)
1283                                       & ~GET_MODE_MASK (narrow_mode))))
1284                             {
1285                               rtx narrow_reg = gen_rtx_REG (narrow_mode,
1286                                                             REGNO (reg));
1287                               rtx narrow_src = gen_int_mode (INTVAL (src),
1288                                                              narrow_mode);
1289                               rtx new_set =
1290                                 gen_rtx_SET (VOIDmode,
1291                                              gen_rtx_STRICT_LOW_PART (VOIDmode,
1292                                                                       narrow_reg),
1293                                              narrow_src);
1294                               if (validate_change (insn, &PATTERN (insn),
1295                                                    new_set, 0))
1296                                 break;
1297                             }
1298                         }
1299                     }
1300                   reg_set_luid[regno] = move2add_luid;
1301                   reg_mode[regno] = GET_MODE (reg);
1302                   reg_offset[regno] = INTVAL (src);
1303                   continue;
1304                 }
1305
1306               /* Try to transform (set (REGX) (REGY))
1307                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1308                                   ...
1309                                   (set (REGX) (REGY))
1310                                   (set (REGX) (PLUS (REGX) (CONST_INT B)))
1311                  to
1312                                   (set (REGX) (REGY))
1313                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1314                                   ...
1315                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))  */
1316               else if (REG_P (src)
1317                        && reg_set_luid[regno] == reg_set_luid[REGNO (src)]
1318                        && reg_base_reg[regno] == reg_base_reg[REGNO (src)]
1319                        && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg),
1320                                                  reg_mode[REGNO (src)]))
1321                 {
1322                   rtx next = next_nonnote_insn (insn);
1323                   rtx set = NULL_RTX;
1324                   if (next)
1325                     set = single_set (next);
1326                   if (set
1327                       && SET_DEST (set) == reg
1328                       && GET_CODE (SET_SRC (set)) == PLUS
1329                       && XEXP (SET_SRC (set), 0) == reg
1330                       && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1331                     {
1332                       rtx src3 = XEXP (SET_SRC (set), 1);
1333                       HOST_WIDE_INT added_offset = INTVAL (src3);
1334                       HOST_WIDE_INT base_offset = reg_offset[REGNO (src)];
1335                       HOST_WIDE_INT regno_offset = reg_offset[regno];
1336                       rtx new_src =
1337                         gen_int_mode (added_offset
1338                                       + base_offset
1339                                       - regno_offset,
1340                                       GET_MODE (reg));
1341                       int success = 0;
1342
1343                       if (new_src == const0_rtx)
1344                         /* See above why we create (set (reg) (reg)) here.  */
1345                         success
1346                           = validate_change (next, &SET_SRC (set), reg, 0);
1347                       else if ((rtx_cost (new_src, PLUS)
1348                                 < COSTS_N_INSNS (1) + rtx_cost (src3, SET))
1349                                && have_add2_insn (reg, new_src))
1350                         {
1351                           rtx newpat = gen_rtx_SET (VOIDmode,
1352                                                     reg,
1353                                                     gen_rtx_PLUS (GET_MODE (reg),
1354                                                                   reg,
1355                                                                   new_src));
1356                           success
1357                             = validate_change (next, &PATTERN (next),
1358                                                newpat, 0);
1359                         }
1360                       if (success)
1361                         delete_insn (insn);
1362                       insn = next;
1363                       reg_mode[regno] = GET_MODE (reg);
1364                       reg_offset[regno] =
1365                         trunc_int_for_mode (added_offset + base_offset,
1366                                             GET_MODE (reg));
1367                       continue;
1368                     }
1369                 }
1370             }
1371         }
1372
1373       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1374         {
1375           if (REG_NOTE_KIND (note) == REG_INC
1376               && REG_P (XEXP (note, 0)))
1377             {
1378               /* Reset the information about this register.  */
1379               int regno = REGNO (XEXP (note, 0));
1380               if (regno < FIRST_PSEUDO_REGISTER)
1381                 reg_set_luid[regno] = 0;
1382             }
1383         }
1384       note_stores (PATTERN (insn), move2add_note_store, NULL);
1385
1386       /* If INSN is a conditional branch, we try to extract an
1387          implicit set out of it.  */
1388       if (any_condjump_p (insn))
1389         {
1390           rtx cnd = fis_get_condition (insn);
1391
1392           if (cnd != NULL_RTX
1393               && GET_CODE (cnd) == NE
1394               && REG_P (XEXP (cnd, 0))
1395               && !reg_set_p (XEXP (cnd, 0), insn)
1396               /* The following two checks, which are also in
1397                  move2add_note_store, are intended to reduce the
1398                  number of calls to gen_rtx_SET to avoid memory
1399                  allocation if possible.  */
1400               && SCALAR_INT_MODE_P (GET_MODE (XEXP (cnd, 0)))
1401               && hard_regno_nregs[REGNO (XEXP (cnd, 0))][GET_MODE (XEXP (cnd, 0))] == 1
1402               && GET_CODE (XEXP (cnd, 1)) == CONST_INT)
1403             {
1404               rtx implicit_set =
1405                 gen_rtx_SET (VOIDmode, XEXP (cnd, 0), XEXP (cnd, 1));
1406               move2add_note_store (SET_DEST (implicit_set), implicit_set, 0);
1407             }
1408         }
1409
1410       /* If this is a CALL_INSN, all call used registers are stored with
1411          unknown values.  */
1412       if (CALL_P (insn))
1413         {
1414           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1415             {
1416               if (call_used_regs[i])
1417                 /* Reset the information about this register.  */
1418                 reg_set_luid[i] = 0;
1419             }
1420         }
1421     }
1422 }
1423
1424 /* SET is a SET or CLOBBER that sets DST.
1425    Update reg_set_luid, reg_offset and reg_base_reg accordingly.
1426    Called from reload_cse_move2add via note_stores.  */
1427
1428 static void
1429 move2add_note_store (rtx dst, rtx set, void *data ATTRIBUTE_UNUSED)
1430 {
1431   unsigned int regno = 0;
1432   unsigned int i;
1433   enum machine_mode mode = GET_MODE (dst);
1434
1435   if (GET_CODE (dst) == SUBREG)
1436     {
1437       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
1438                                    GET_MODE (SUBREG_REG (dst)),
1439                                    SUBREG_BYTE (dst),
1440                                    GET_MODE (dst));
1441       dst = SUBREG_REG (dst);
1442     }
1443
1444   /* Some targets do argument pushes without adding REG_INC notes.  */
1445
1446   if (MEM_P (dst))
1447     {
1448       dst = XEXP (dst, 0);
1449       if (GET_CODE (dst) == PRE_INC || GET_CODE (dst) == POST_INC
1450           || GET_CODE (dst) == PRE_DEC || GET_CODE (dst) == POST_DEC)
1451         reg_set_luid[REGNO (XEXP (dst, 0))] = 0;
1452       return;
1453     }
1454   if (!REG_P (dst))
1455     return;
1456
1457   regno += REGNO (dst);
1458
1459   if (SCALAR_INT_MODE_P (GET_MODE (dst))
1460       && hard_regno_nregs[regno][mode] == 1 && GET_CODE (set) == SET
1461       && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
1462       && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
1463     {
1464       rtx src = SET_SRC (set);
1465       rtx base_reg;
1466       HOST_WIDE_INT offset;
1467       int base_regno;
1468       /* This may be different from mode, if SET_DEST (set) is a
1469          SUBREG.  */
1470       enum machine_mode dst_mode = GET_MODE (dst);
1471
1472       switch (GET_CODE (src))
1473         {
1474         case PLUS:
1475           if (REG_P (XEXP (src, 0)))
1476             {
1477               base_reg = XEXP (src, 0);
1478
1479               if (GET_CODE (XEXP (src, 1)) == CONST_INT)
1480                 offset = INTVAL (XEXP (src, 1));
1481               else if (REG_P (XEXP (src, 1))
1482                        && (reg_set_luid[REGNO (XEXP (src, 1))]
1483                            > move2add_last_label_luid)
1484                        && (MODES_OK_FOR_MOVE2ADD
1485                            (dst_mode, reg_mode[REGNO (XEXP (src, 1))])))
1486                 {
1487                   if (reg_base_reg[REGNO (XEXP (src, 1))] < 0)
1488                     offset = reg_offset[REGNO (XEXP (src, 1))];
1489                   /* Maybe the first register is known to be a
1490                      constant.  */
1491                   else if (reg_set_luid[REGNO (base_reg)]
1492                            > move2add_last_label_luid
1493                            && (MODES_OK_FOR_MOVE2ADD
1494                                (dst_mode, reg_mode[REGNO (XEXP (src, 1))]))
1495                            && reg_base_reg[REGNO (base_reg)] < 0)
1496                     {
1497                       offset = reg_offset[REGNO (base_reg)];
1498                       base_reg = XEXP (src, 1);
1499                     }
1500                   else
1501                     goto invalidate;
1502                 }
1503               else
1504                 goto invalidate;
1505
1506               break;
1507             }
1508
1509           goto invalidate;
1510
1511         case REG:
1512           base_reg = src;
1513           offset = 0;
1514           break;
1515
1516         case CONST_INT:
1517           /* Start tracking the register as a constant.  */
1518           reg_base_reg[regno] = -1;
1519           reg_offset[regno] = INTVAL (SET_SRC (set));
1520           /* We assign the same luid to all registers set to constants.  */
1521           reg_set_luid[regno] = move2add_last_label_luid + 1;
1522           reg_mode[regno] = mode;
1523           return;
1524
1525         default:
1526         invalidate:
1527           /* Invalidate the contents of the register.  */
1528           reg_set_luid[regno] = 0;
1529           return;
1530         }
1531
1532       base_regno = REGNO (base_reg);
1533       /* If information about the base register is not valid, set it
1534          up as a new base register, pretending its value is known
1535          starting from the current insn.  */
1536       if (reg_set_luid[base_regno] <= move2add_last_label_luid)
1537         {
1538           reg_base_reg[base_regno] = base_regno;
1539           reg_offset[base_regno] = 0;
1540           reg_set_luid[base_regno] = move2add_luid;
1541           reg_mode[base_regno] = mode;
1542         }
1543       else if (! MODES_OK_FOR_MOVE2ADD (dst_mode,
1544                                         reg_mode[base_regno]))
1545         goto invalidate;
1546
1547       reg_mode[regno] = mode;
1548
1549       /* Copy base information from our base register.  */
1550       reg_set_luid[regno] = reg_set_luid[base_regno];
1551       reg_base_reg[regno] = reg_base_reg[base_regno];
1552
1553       /* Compute the sum of the offsets or constants.  */
1554       reg_offset[regno] = trunc_int_for_mode (offset
1555                                               + reg_offset[base_regno],
1556                                               dst_mode);
1557     }
1558   else
1559     {
1560       unsigned int endregno = regno + hard_regno_nregs[regno][mode];
1561
1562       for (i = regno; i < endregno; i++)
1563         /* Reset the information about this register.  */
1564         reg_set_luid[i] = 0;
1565     }
1566 }
1567 \f
1568 static bool
1569 gate_handle_postreload (void)
1570 {
1571   return (optimize > 0);
1572 }
1573
1574
1575 static unsigned int
1576 rest_of_handle_postreload (void)
1577 {
1578   /* Do a very simple CSE pass over just the hard registers.  */
1579   reload_cse_regs (get_insns ());
1580   /* reload_cse_regs can eliminate potentially-trapping MEMs.
1581      Remove any EH edges associated with them.  */
1582   if (flag_non_call_exceptions)
1583     purge_all_dead_edges ();
1584   return 0;
1585 }
1586
1587 struct tree_opt_pass pass_postreload_cse =
1588 {
1589   "postreload",                         /* name */
1590   gate_handle_postreload,               /* gate */
1591   rest_of_handle_postreload,            /* execute */
1592   NULL,                                 /* sub */
1593   NULL,                                 /* next */
1594   0,                                    /* static_pass_number */
1595   TV_RELOAD_CSE_REGS,                   /* tv_id */
1596   0,                                    /* properties_required */
1597   0,                                    /* properties_provided */
1598   0,                                    /* properties_destroyed */
1599   0,                                    /* todo_flags_start */
1600   TODO_dump_func,                       /* todo_flags_finish */
1601   'o'                                   /* letter */
1602 };
1603