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