gcc/postreload.c

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