gcc/postreload.c

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