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                   /* Delete the reg-reg addition.  */
 891                   delete_insn (insn);
 892
 893                   if (reg_state[regno].offset != const0_rtx)
 894                     /* Previous REG_EQUIV / REG_EQUAL notes for PREV
 895                        are now invalid.  */
 896                     remove_reg_equal_equiv_notes (prev);
 897
 898                   reg_state[regno].use_index = RELOAD_COMBINE_MAX_USES;
 899                   reg_state[REGNO (const_reg)].store_ruid
 900                     = reload_combine_ruid;
 901                   continue;
 902                 }
 903             }
 904         }
 905
 906       note_stores (PATTERN (insn), reload_combine_note_store, NULL);
 907
 908       if (CALL_P (insn))
 909         {
 910           rtx link;
 911
 912           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 913             if (call_used_regs[r])
 914               {
 915                 reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
 916                 reg_state[r].store_ruid = reload_combine_ruid;
 917               }
 918
 919           for (link = CALL_INSN_FUNCTION_USAGE (insn); link;
 920                link = XEXP (link, 1))
 921             {
 922               rtx usage_rtx = XEXP (XEXP (link, 0), 0);
 923               if (REG_P (usage_rtx))
 924                 {
 925                   unsigned int i;
 926                   unsigned int start_reg = REGNO (usage_rtx);
 927                   unsigned int num_regs =
 928                         hard_regno_nregs[start_reg][GET_MODE (usage_rtx)];
 929                   unsigned int end_reg  = start_reg + num_regs - 1;
 930                   for (i = start_reg; i <= end_reg; i++)
 931                     if (GET_CODE (XEXP (link, 0)) == CLOBBER)
 932                       {
 933                         reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
 934                         reg_state[i].store_ruid = reload_combine_ruid;
 935                       }
 936                     else
 937                       reg_state[i].use_index = -1;
 938                  }
 939              }
 940
 941         }
 942       else if (JUMP_P (insn)
 943                && GET_CODE (PATTERN (insn)) != RETURN)
 944         {
 945           /* Non-spill registers might be used at the call destination in
 946              some unknown fashion, so we have to mark the unknown use.  */
 947           HARD_REG_SET *live;
 948
 949           if ((condjump_p (insn) || condjump_in_parallel_p (insn))
 950               && JUMP_LABEL (insn))
 951             live = &LABEL_LIVE (JUMP_LABEL (insn));
 952           else
 953             live = &ever_live_at_start;
 954
 955           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; --i)
 956             if (TEST_HARD_REG_BIT (*live, i))
 957               reg_state[i].use_index = -1;
 958         }
 959
 960       reload_combine_note_use (&PATTERN (insn), insn);
 961       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 962         {
 963           if (REG_NOTE_KIND (note) == REG_INC
 964               && REG_P (XEXP (note, 0)))
 965             {
 966               int regno = REGNO (XEXP (note, 0));
 967
 968               reg_state[regno].store_ruid = reload_combine_ruid;
 969               reg_state[regno].use_index = -1;
 970             }
 971         }
 972     }
 973
 974   free (label_live);
 975 }
 976
 977 /* Check if DST is a register or a subreg of a register; if it is,
 978    update reg_state[regno].store_ruid and reg_state[regno].use_index
 979    accordingly.  Called via note_stores from reload_combine.  */
 980
 981 static void
 982 reload_combine_note_store (rtx dst, rtx set, void *data ATTRIBUTE_UNUSED)
 983 {
 984   int regno = 0;
 985   int i;
 986   enum machine_mode mode = GET_MODE (dst);
 987
 988   if (GET_CODE (dst) == SUBREG)
 989     {
 990       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
 991                                    GET_MODE (SUBREG_REG (dst)),
 992                                    SUBREG_BYTE (dst),
 993                                    GET_MODE (dst));
 994       dst = SUBREG_REG (dst);
 995     }
 996   if (!REG_P (dst))
 997     return;
 998   regno += REGNO (dst);
 999
1000   /* note_stores might have stripped a STRICT_LOW_PART, so we have to be
1001      careful with registers / register parts that are not full words.
1002      Similarly for ZERO_EXTRACT.  */
1003   if (GET_CODE (set) != SET
1004       || GET_CODE (SET_DEST (set)) == ZERO_EXTRACT
1005       || GET_CODE (SET_DEST (set)) == STRICT_LOW_PART)
1006     {
1007       for (i = hard_regno_nregs[regno][mode] - 1 + regno; i >= regno; i--)
1008         {
1009           reg_state[i].use_index = -1;
1010           reg_state[i].store_ruid = reload_combine_ruid;
1011         }
1012     }
1013   else
1014     {
1015       for (i = hard_regno_nregs[regno][mode] - 1 + regno; i >= regno; i--)
1016         {
1017           reg_state[i].store_ruid = reload_combine_ruid;
1018           reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
1019         }
1020     }
1021 }
1022
1023 /* XP points to a piece of rtl that has to be checked for any uses of
1024    registers.
1025    *XP is the pattern of INSN, or a part of it.
1026    Called from reload_combine, and recursively by itself.  */
1027 static void
1028 reload_combine_note_use (rtx *xp, rtx insn)
1029 {
1030   rtx x = *xp;
1031   enum rtx_code code = x->code;
1032   const char *fmt;
1033   int i, j;
1034   rtx offset = const0_rtx; /* For the REG case below.  */
1035
1036   switch (code)
1037     {
1038     case SET:
1039       if (REG_P (SET_DEST (x)))
1040         {
1041           reload_combine_note_use (&SET_SRC (x), insn);
1042           return;
1043         }
1044       break;
1045
1046     case USE:
1047       /* If this is the USE of a return value, we can't change it.  */
1048       if (REG_P (XEXP (x, 0)) && REG_FUNCTION_VALUE_P (XEXP (x, 0)))
1049         {
1050         /* Mark the return register as used in an unknown fashion.  */
1051           rtx reg = XEXP (x, 0);
1052           int regno = REGNO (reg);
1053           int nregs = hard_regno_nregs[regno][GET_MODE (reg)];
1054
1055           while (--nregs >= 0)
1056             reg_state[regno + nregs].use_index = -1;
1057           return;
1058         }
1059       break;
1060
1061     case CLOBBER:
1062       if (REG_P (SET_DEST (x)))
1063         {
1064           /* No spurious CLOBBERs of pseudo registers may remain.  */
1065           gcc_assert (REGNO (SET_DEST (x)) < FIRST_PSEUDO_REGISTER);
1066           return;
1067         }
1068       break;
1069
1070     case PLUS:
1071       /* We are interested in (plus (reg) (const_int)) .  */
1072       if (!REG_P (XEXP (x, 0))
1073           || GET_CODE (XEXP (x, 1)) != CONST_INT)
1074         break;
1075       offset = XEXP (x, 1);
1076       x = XEXP (x, 0);
1077       /* Fall through.  */
1078     case REG:
1079       {
1080         int regno = REGNO (x);
1081         int use_index;
1082         int nregs;
1083
1084         /* No spurious USEs of pseudo registers may remain.  */
1085         gcc_assert (regno < FIRST_PSEUDO_REGISTER);
1086
1087         nregs = hard_regno_nregs[regno][GET_MODE (x)];
1088
1089         /* We can't substitute into multi-hard-reg uses.  */
1090         if (nregs > 1)
1091           {
1092             while (--nregs >= 0)
1093               reg_state[regno + nregs].use_index = -1;
1094             return;
1095           }
1096
1097         /* If this register is already used in some unknown fashion, we
1098            can't do anything.
1099            If we decrement the index from zero to -1, we can't store more
1100            uses, so this register becomes used in an unknown fashion.  */
1101         use_index = --reg_state[regno].use_index;
1102         if (use_index < 0)
1103           return;
1104
1105         if (use_index != RELOAD_COMBINE_MAX_USES - 1)
1106           {
1107             /* We have found another use for a register that is already
1108                used later.  Check if the offsets match; if not, mark the
1109                register as used in an unknown fashion.  */
1110             if (! rtx_equal_p (offset, reg_state[regno].offset))
1111               {
1112                 reg_state[regno].use_index = -1;
1113                 return;
1114               }
1115           }
1116         else
1117           {
1118             /* This is the first use of this register we have seen since we
1119                marked it as dead.  */
1120             reg_state[regno].offset = offset;
1121             reg_state[regno].use_ruid = reload_combine_ruid;
1122           }
1123         reg_state[regno].reg_use[use_index].insn = insn;
1124         reg_state[regno].reg_use[use_index].usep = xp;
1125         return;
1126       }
1127
1128     default:
1129       break;
1130     }
1131
1132   /* Recursively process the components of X.  */
1133   fmt = GET_RTX_FORMAT (code);
1134   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1135     {
1136       if (fmt[i] == 'e')
1137         reload_combine_note_use (&XEXP (x, i), insn);
1138       else if (fmt[i] == 'E')
1139         {
1140           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1141             reload_combine_note_use (&XVECEXP (x, i, j), insn);
1142         }
1143     }
1144 }
1145 \f
1146 /* See if we can reduce the cost of a constant by replacing a move
1147    with an add.  We track situations in which a register is set to a
1148    constant or to a register plus a constant.  */
1149 /* We cannot do our optimization across labels.  Invalidating all the
1150    information about register contents we have would be costly, so we
1151    use move2add_last_label_luid to note where the label is and then
1152    later disable any optimization that would cross it.
1153    reg_offset[n] / reg_base_reg[n] / reg_mode[n] are only valid if
1154    reg_set_luid[n] is greater than move2add_last_label_luid.  */
1155 static int reg_set_luid[FIRST_PSEUDO_REGISTER];
1156
1157 /* If reg_base_reg[n] is negative, register n has been set to
1158    reg_offset[n] in mode reg_mode[n] .
1159    If reg_base_reg[n] is non-negative, register n has been set to the
1160    sum of reg_offset[n] and the value of register reg_base_reg[n]
1161    before reg_set_luid[n], calculated in mode reg_mode[n] .  */
1162 static HOST_WIDE_INT reg_offset[FIRST_PSEUDO_REGISTER];
1163 static int reg_base_reg[FIRST_PSEUDO_REGISTER];
1164 static enum machine_mode reg_mode[FIRST_PSEUDO_REGISTER];
1165
1166 /* move2add_luid is linearly increased while scanning the instructions
1167    from first to last.  It is used to set reg_set_luid in
1168    reload_cse_move2add and move2add_note_store.  */
1169 static int move2add_luid;
1170
1171 /* move2add_last_label_luid is set whenever a label is found.  Labels
1172    invalidate all previously collected reg_offset data.  */
1173 static int move2add_last_label_luid;
1174
1175 /* ??? We don't know how zero / sign extension is handled, hence we
1176    can't go from a narrower to a wider mode.  */
1177 #define MODES_OK_FOR_MOVE2ADD(OUTMODE, INMODE) \
1178   (GET_MODE_SIZE (OUTMODE) == GET_MODE_SIZE (INMODE) \
1179    || (GET_MODE_SIZE (OUTMODE) <= GET_MODE_SIZE (INMODE) \
1180        && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (OUTMODE), \
1181                                  GET_MODE_BITSIZE (INMODE))))
1182
1183 static void
1184 reload_cse_move2add (rtx first)
1185 {
1186   int i;
1187   rtx insn;
1188
1189   for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1190     reg_set_luid[i] = 0;
1191
1192   move2add_last_label_luid = 0;
1193   move2add_luid = 2;
1194   for (insn = first; insn; insn = NEXT_INSN (insn), move2add_luid++)
1195     {
1196       rtx pat, note;
1197
1198       if (LABEL_P (insn))
1199         {
1200           move2add_last_label_luid = move2add_luid;
1201           /* We're going to increment move2add_luid twice after a
1202              label, so that we can use move2add_last_label_luid + 1 as
1203              the luid for constants.  */
1204           move2add_luid++;
1205           continue;
1206         }
1207       if (! INSN_P (insn))
1208         continue;
1209       pat = PATTERN (insn);
1210       /* For simplicity, we only perform this optimization on
1211          straightforward SETs.  */
1212       if (GET_CODE (pat) == SET
1213           && REG_P (SET_DEST (pat)))
1214         {
1215           rtx reg = SET_DEST (pat);
1216           int regno = REGNO (reg);
1217           rtx src = SET_SRC (pat);
1218
1219           /* Check if we have valid information on the contents of this
1220              register in the mode of REG.  */
1221           if (reg_set_luid[regno] > move2add_last_label_luid
1222               && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg), reg_mode[regno]))
1223             {
1224               /* Try to transform (set (REGX) (CONST_INT A))
1225                                   ...
1226                                   (set (REGX) (CONST_INT B))
1227                  to
1228                                   (set (REGX) (CONST_INT A))
1229                                   ...
1230                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))
1231                  or
1232                                   (set (REGX) (CONST_INT A))
1233                                   ...
1234                                   (set (STRICT_LOW_PART (REGX)) (CONST_INT B))
1235               */
1236
1237               if (GET_CODE (src) == CONST_INT && reg_base_reg[regno] < 0)
1238                 {
1239                   rtx new_src = gen_int_mode (INTVAL (src) - reg_offset[regno],
1240                                               GET_MODE (reg));
1241                   /* (set (reg) (plus (reg) (const_int 0))) is not canonical;
1242                      use (set (reg) (reg)) instead.
1243                      We don't delete this insn, nor do we convert it into a
1244                      note, to avoid losing register notes or the return
1245                      value flag.  jump2 already knows how to get rid of
1246                      no-op moves.  */
1247                   if (new_src == const0_rtx)
1248                     {
1249                       /* If the constants are different, this is a
1250                          truncation, that, if turned into (set (reg)
1251                          (reg)), would be discarded.  Maybe we should
1252                          try a truncMN pattern?  */
1253                       if (INTVAL (src) == reg_offset [regno])
1254                         validate_change (insn, &SET_SRC (pat), reg, 0);
1255                     }
1256                   else if (rtx_cost (new_src, PLUS) < rtx_cost (src, SET)
1257                            && have_add2_insn (reg, new_src))
1258                     {
1259                       rtx tem = gen_rtx_PLUS (GET_MODE (reg), reg, new_src);
1260                       validate_change (insn, &SET_SRC (pat), tem, 0);
1261                     }
1262                   else if (GET_MODE (reg) != BImode)
1263                     {
1264                       enum machine_mode narrow_mode;
1265                       for (narrow_mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
1266                            narrow_mode != VOIDmode
1267                            && narrow_mode != GET_MODE (reg);
1268                            narrow_mode = GET_MODE_WIDER_MODE (narrow_mode))
1269                         {
1270                           if (have_insn_for (STRICT_LOW_PART, narrow_mode)
1271                               && ((reg_offset[regno]
1272                                    & ~GET_MODE_MASK (narrow_mode))
1273                                   == (INTVAL (src)
1274                                       & ~GET_MODE_MASK (narrow_mode))))
1275                             {
1276                               rtx narrow_reg = gen_rtx_REG (narrow_mode,
1277                                                             REGNO (reg));
1278                               rtx narrow_src = gen_int_mode (INTVAL (src),
1279                                                              narrow_mode);
1280                               rtx new_set =
1281                                 gen_rtx_SET (VOIDmode,
1282                                              gen_rtx_STRICT_LOW_PART (VOIDmode,
1283                                                                       narrow_reg),
1284                                              narrow_src);
1285                               if (validate_change (insn, &PATTERN (insn),
1286                                                    new_set, 0))
1287                                 break;
1288                             }
1289                         }
1290                     }
1291                   reg_set_luid[regno] = move2add_luid;
1292                   reg_mode[regno] = GET_MODE (reg);
1293                   reg_offset[regno] = INTVAL (src);
1294                   continue;
1295                 }
1296
1297               /* Try to transform (set (REGX) (REGY))
1298                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1299                                   ...
1300                                   (set (REGX) (REGY))
1301                                   (set (REGX) (PLUS (REGX) (CONST_INT B)))
1302                  to
1303                                   (set (REGX) (REGY))
1304                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1305                                   ...
1306                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))  */
1307               else if (REG_P (src)
1308                        && reg_set_luid[regno] == reg_set_luid[REGNO (src)]
1309                        && reg_base_reg[regno] == reg_base_reg[REGNO (src)]
1310                        && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg),
1311                                                  reg_mode[REGNO (src)]))
1312                 {
1313                   rtx next = next_nonnote_insn (insn);
1314                   rtx set = NULL_RTX;
1315                   if (next)
1316                     set = single_set (next);
1317                   if (set
1318                       && SET_DEST (set) == reg
1319                       && GET_CODE (SET_SRC (set)) == PLUS
1320                       && XEXP (SET_SRC (set), 0) == reg
1321                       && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1322                     {
1323                       rtx src3 = XEXP (SET_SRC (set), 1);
1324                       HOST_WIDE_INT added_offset = INTVAL (src3);
1325                       HOST_WIDE_INT base_offset = reg_offset[REGNO (src)];
1326                       HOST_WIDE_INT regno_offset = reg_offset[regno];
1327                       rtx new_src =
1328                         gen_int_mode (added_offset
1329                                       + base_offset
1330                                       - regno_offset,
1331                                       GET_MODE (reg));
1332                       int success = 0;
1333
1334                       if (new_src == const0_rtx)
1335                         /* See above why we create (set (reg) (reg)) here.  */
1336                         success
1337                           = validate_change (next, &SET_SRC (set), reg, 0);
1338                       else if ((rtx_cost (new_src, PLUS)
1339                                 < COSTS_N_INSNS (1) + rtx_cost (src3, SET))
1340                                && have_add2_insn (reg, new_src))
1341                         {
1342                           rtx newpat = gen_rtx_SET (VOIDmode,
1343                                                     reg,
1344                                                     gen_rtx_PLUS (GET_MODE (reg),
1345                                                                   reg,
1346                                                                   new_src));
1347                           success
1348                             = validate_change (next, &PATTERN (next),
1349                                                newpat, 0);
1350                         }
1351                       if (success)
1352                         delete_insn (insn);
1353                       insn = next;
1354                       reg_mode[regno] = GET_MODE (reg);
1355                       reg_offset[regno] =
1356                         trunc_int_for_mode (added_offset + base_offset,
1357                                             GET_MODE (reg));
1358                       continue;
1359                     }
1360                 }
1361             }
1362         }
1363
1364       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1365         {
1366           if (REG_NOTE_KIND (note) == REG_INC
1367               && REG_P (XEXP (note, 0)))
1368             {
1369               /* Reset the information about this register.  */
1370               int regno = REGNO (XEXP (note, 0));
1371               if (regno < FIRST_PSEUDO_REGISTER)
1372                 reg_set_luid[regno] = 0;
1373             }
1374         }
1375       note_stores (PATTERN (insn), move2add_note_store, NULL);
1376
1377       /* If INSN is a conditional branch, we try to extract an
1378          implicit set out of it.  */
1379       if (any_condjump_p (insn))
1380         {
1381           rtx cnd = fis_get_condition (insn);
1382
1383           if (cnd != NULL_RTX
1384               && GET_CODE (cnd) == NE
1385               && REG_P (XEXP (cnd, 0))
1386               && !reg_set_p (XEXP (cnd, 0), insn)
1387               /* The following two checks, which are also in
1388                  move2add_note_store, are intended to reduce the
1389                  number of calls to gen_rtx_SET to avoid memory
1390                  allocation if possible.  */
1391               && SCALAR_INT_MODE_P (GET_MODE (XEXP (cnd, 0)))
1392               && hard_regno_nregs[REGNO (XEXP (cnd, 0))][GET_MODE (XEXP (cnd, 0))] == 1
1393               && GET_CODE (XEXP (cnd, 1)) == CONST_INT)
1394             {
1395               rtx implicit_set =
1396                 gen_rtx_SET (VOIDmode, XEXP (cnd, 0), XEXP (cnd, 1));
1397               move2add_note_store (SET_DEST (implicit_set), implicit_set, 0);
1398             }
1399         }
1400
1401       /* If this is a CALL_INSN, all call used registers are stored with
1402          unknown values.  */
1403       if (CALL_P (insn))
1404         {
1405           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1406             {
1407               if (call_used_regs[i])
1408                 /* Reset the information about this register.  */
1409                 reg_set_luid[i] = 0;
1410             }
1411         }
1412     }
1413 }
1414
1415 /* SET is a SET or CLOBBER that sets DST.
1416    Update reg_set_luid, reg_offset and reg_base_reg accordingly.
1417    Called from reload_cse_move2add via note_stores.  */
1418
1419 static void
1420 move2add_note_store (rtx dst, rtx set, void *data ATTRIBUTE_UNUSED)
1421 {
1422   unsigned int regno = 0;
1423   unsigned int nregs = 0;
1424   unsigned int i;
1425   enum machine_mode mode = GET_MODE (dst);
1426
1427   if (GET_CODE (dst) == SUBREG)
1428     {
1429       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
1430                                    GET_MODE (SUBREG_REG (dst)),
1431                                    SUBREG_BYTE (dst),
1432                                    GET_MODE (dst));
1433       nregs = subreg_nregs (dst);
1434       dst = SUBREG_REG (dst);
1435     }
1436
1437   /* Some targets do argument pushes without adding REG_INC notes.  */
1438
1439   if (MEM_P (dst))
1440     {
1441       dst = XEXP (dst, 0);
1442       if (GET_CODE (dst) == PRE_INC || GET_CODE (dst) == POST_INC
1443           || GET_CODE (dst) == PRE_DEC || GET_CODE (dst) == POST_DEC)
1444         reg_set_luid[REGNO (XEXP (dst, 0))] = 0;
1445       return;
1446     }
1447   if (!REG_P (dst))
1448     return;
1449
1450   regno += REGNO (dst);
1451   if (!nregs)
1452     nregs = hard_regno_nregs[regno][mode];
1453
1454   if (SCALAR_INT_MODE_P (GET_MODE (dst))
1455       && nregs == 1 && GET_CODE (set) == SET
1456       && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
1457       && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
1458     {
1459       rtx src = SET_SRC (set);
1460       rtx base_reg;
1461       HOST_WIDE_INT offset;
1462       int base_regno;
1463       /* This may be different from mode, if SET_DEST (set) is a
1464          SUBREG.  */
1465       enum machine_mode dst_mode = GET_MODE (dst);
1466
1467       switch (GET_CODE (src))
1468         {
1469         case PLUS:
1470           if (REG_P (XEXP (src, 0)))
1471             {
1472               base_reg = XEXP (src, 0);
1473
1474               if (GET_CODE (XEXP (src, 1)) == CONST_INT)
1475                 offset = INTVAL (XEXP (src, 1));
1476               else if (REG_P (XEXP (src, 1))
1477                        && (reg_set_luid[REGNO (XEXP (src, 1))]
1478                            > move2add_last_label_luid)
1479                        && (MODES_OK_FOR_MOVE2ADD
1480                            (dst_mode, reg_mode[REGNO (XEXP (src, 1))])))
1481                 {
1482                   if (reg_base_reg[REGNO (XEXP (src, 1))] < 0)
1483                     offset = reg_offset[REGNO (XEXP (src, 1))];
1484                   /* Maybe the first register is known to be a
1485                      constant.  */
1486                   else if (reg_set_luid[REGNO (base_reg)]
1487                            > move2add_last_label_luid
1488                            && (MODES_OK_FOR_MOVE2ADD
1489                                (dst_mode, reg_mode[REGNO (XEXP (src, 1))]))
1490                            && reg_base_reg[REGNO (base_reg)] < 0)
1491                     {
1492                       offset = reg_offset[REGNO (base_reg)];
1493                       base_reg = XEXP (src, 1);
1494                     }
1495                   else
1496                     goto invalidate;
1497                 }
1498               else
1499                 goto invalidate;
1500
1501               break;
1502             }
1503
1504           goto invalidate;
1505
1506         case REG:
1507           base_reg = src;
1508           offset = 0;
1509           break;
1510
1511         case CONST_INT:
1512           /* Start tracking the register as a constant.  */
1513           reg_base_reg[regno] = -1;
1514           reg_offset[regno] = INTVAL (SET_SRC (set));
1515           /* We assign the same luid to all registers set to constants.  */
1516           reg_set_luid[regno] = move2add_last_label_luid + 1;
1517           reg_mode[regno] = mode;
1518           return;
1519
1520         default:
1521         invalidate:
1522           /* Invalidate the contents of the register.  */
1523           reg_set_luid[regno] = 0;
1524           return;
1525         }
1526
1527       base_regno = REGNO (base_reg);
1528       /* If information about the base register is not valid, set it
1529          up as a new base register, pretending its value is known
1530          starting from the current insn.  */
1531       if (reg_set_luid[base_regno] <= move2add_last_label_luid)
1532         {
1533           reg_base_reg[base_regno] = base_regno;
1534           reg_offset[base_regno] = 0;
1535           reg_set_luid[base_regno] = move2add_luid;
1536           reg_mode[base_regno] = mode;
1537         }
1538       else if (! MODES_OK_FOR_MOVE2ADD (dst_mode,
1539                                         reg_mode[base_regno]))
1540         goto invalidate;
1541
1542       reg_mode[regno] = mode;
1543
1544       /* Copy base information from our base register.  */
1545       reg_set_luid[regno] = reg_set_luid[base_regno];
1546       reg_base_reg[regno] = reg_base_reg[base_regno];
1547
1548       /* Compute the sum of the offsets or constants.  */
1549       reg_offset[regno] = trunc_int_for_mode (offset
1550                                               + reg_offset[base_regno],
1551                                               dst_mode);
1552     }
1553   else
1554     {
1555       unsigned int endregno = regno + nregs;
1556
1557       for (i = regno; i < endregno; i++)
1558         /* Reset the information about this register.  */
1559         reg_set_luid[i] = 0;
1560     }
1561 }
1562 \f
1563 static bool
1564 gate_handle_postreload (void)
1565 {
1566   return (optimize > 0);
1567 }
1568
1569
1570 static unsigned int
1571 rest_of_handle_postreload (void)
1572 {
1573   /* Do a very simple CSE pass over just the hard registers.  */
1574   reload_cse_regs (get_insns ());
1575   /* reload_cse_regs can eliminate potentially-trapping MEMs.
1576      Remove any EH edges associated with them.  */
1577   if (flag_non_call_exceptions)
1578     purge_all_dead_edges ();
1579   return 0;
1580 }
1581
1582 struct tree_opt_pass pass_postreload_cse =
1583 {
1584   "postreload",                         /* name */
1585   gate_handle_postreload,               /* gate */
1586   rest_of_handle_postreload,            /* execute */
1587   NULL,                                 /* sub */
1588   NULL,                                 /* next */
1589   0,                                    /* static_pass_number */
1590   TV_RELOAD_CSE_REGS,                   /* tv_id */
1591   0,                                    /* properties_required */
1592   0,                                    /* properties_provided */
1593   0,                                    /* properties_destroyed */
1594   0,                                    /* todo_flags_start */
1595   TODO_dump_func,                       /* todo_flags_finish */
1596   'o'                                   /* letter */
1597 };
1598