contrib/gcc-4.0/gcc/postreload.c

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