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