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 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 a also 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
1009      Similarly for ZERO_EXTRACT and SIGN_EXTRACT.  */
1010   if (GET_CODE (set) != SET
1011       || GET_CODE (SET_DEST (set)) == ZERO_EXTRACT
1012       || GET_CODE (SET_DEST (set)) == SIGN_EXTRACT
1013       || GET_CODE (SET_DEST (set)) == STRICT_LOW_PART)
1014     {
1015       for (i = hard_regno_nregs[regno][mode] - 1 + regno; i >= regno; i--)
1016         {
1017           reg_state[i].use_index = -1;
1018           reg_state[i].store_ruid = reload_combine_ruid;
1019         }
1020     }
1021   else
1022     {
1023       for (i = hard_regno_nregs[regno][mode] - 1 + regno; i >= regno; i--)
1024         {
1025           reg_state[i].store_ruid = reload_combine_ruid;
1026           reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
1027         }
1028     }
1029 }
1030
1031 /* XP points to a piece of rtl that has to be checked for any uses of
1032    registers.
1033    *XP is the pattern of INSN, or a part of it.
1034    Called from reload_combine, and recursively by itself.  */
1035 static void
1036 reload_combine_note_use (rtx *xp, rtx insn)
1037 {
1038   rtx x = *xp;
1039   enum rtx_code code = x->code;
1040   const char *fmt;
1041   int i, j;
1042   rtx offset = const0_rtx; /* For the REG case below.  */
1043
1044   switch (code)
1045     {
1046     case SET:
1047       if (REG_P (SET_DEST (x)))
1048         {
1049           reload_combine_note_use (&SET_SRC (x), insn);
1050           return;
1051         }
1052       break;
1053
1054     case USE:
1055       /* If this is the USE of a return value, we can't change it.  */
1056       if (REG_P (XEXP (x, 0)) && REG_FUNCTION_VALUE_P (XEXP (x, 0)))
1057         {
1058         /* Mark the return register as used in an unknown fashion.  */
1059           rtx reg = XEXP (x, 0);
1060           int regno = REGNO (reg);
1061           int nregs = hard_regno_nregs[regno][GET_MODE (reg)];
1062
1063           while (--nregs >= 0)
1064             reg_state[regno + nregs].use_index = -1;
1065           return;
1066         }
1067       break;
1068
1069     case CLOBBER:
1070       if (REG_P (SET_DEST (x)))
1071         {
1072           /* No spurious CLOBBERs of pseudo registers may remain.  */
1073           if (REGNO (SET_DEST (x)) >= FIRST_PSEUDO_REGISTER)
1074             abort ();
1075           return;
1076         }
1077       break;
1078
1079     case PLUS:
1080       /* We are interested in (plus (reg) (const_int)) .  */
1081       if (!REG_P (XEXP (x, 0))
1082           || GET_CODE (XEXP (x, 1)) != CONST_INT)
1083         break;
1084       offset = XEXP (x, 1);
1085       x = XEXP (x, 0);
1086       /* Fall through.  */
1087     case REG:
1088       {
1089         int regno = REGNO (x);
1090         int use_index;
1091         int nregs;
1092
1093         /* No spurious USEs of pseudo registers may remain.  */
1094         if (regno >= FIRST_PSEUDO_REGISTER)
1095           abort ();
1096
1097         nregs = hard_regno_nregs[regno][GET_MODE (x)];
1098
1099         /* We can't substitute into multi-hard-reg uses.  */
1100         if (nregs > 1)
1101           {
1102             while (--nregs >= 0)
1103               reg_state[regno + nregs].use_index = -1;
1104             return;
1105           }
1106
1107         /* If this register is already used in some unknown fashion, we
1108            can't do anything.
1109            If we decrement the index from zero to -1, we can't store more
1110            uses, so this register becomes used in an unknown fashion.  */
1111         use_index = --reg_state[regno].use_index;
1112         if (use_index < 0)
1113           return;
1114
1115         if (use_index != RELOAD_COMBINE_MAX_USES - 1)
1116           {
1117             /* We have found another use for a register that is already
1118                used later.  Check if the offsets match; if not, mark the
1119                register as used in an unknown fashion.  */
1120             if (! rtx_equal_p (offset, reg_state[regno].offset))
1121               {
1122                 reg_state[regno].use_index = -1;
1123                 return;
1124               }
1125           }
1126         else
1127           {
1128             /* This is the first use of this register we have seen since we
1129                marked it as dead.  */
1130             reg_state[regno].offset = offset;
1131             reg_state[regno].use_ruid = reload_combine_ruid;
1132           }
1133         reg_state[regno].reg_use[use_index].insn = insn;
1134         reg_state[regno].reg_use[use_index].usep = xp;
1135         return;
1136       }
1137
1138     default:
1139       break;
1140     }
1141
1142   /* Recursively process the components of X.  */
1143   fmt = GET_RTX_FORMAT (code);
1144   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1145     {
1146       if (fmt[i] == 'e')
1147         reload_combine_note_use (&XEXP (x, i), insn);
1148       else if (fmt[i] == 'E')
1149         {
1150           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1151             reload_combine_note_use (&XVECEXP (x, i, j), insn);
1152         }
1153     }
1154 }
1155 \f
1156 /* See if we can reduce the cost of a constant by replacing a move
1157    with an add.  We track situations in which a register is set to a
1158    constant or to a register plus a constant.  */
1159 /* We cannot do our optimization across labels.  Invalidating all the
1160    information about register contents we have would be costly, so we
1161    use move2add_last_label_luid to note where the label is and then
1162    later disable any optimization that would cross it.
1163    reg_offset[n] / reg_base_reg[n] / reg_mode[n] are only valid if
1164    reg_set_luid[n] is greater than move2add_last_label_luid.  */
1165 static int reg_set_luid[FIRST_PSEUDO_REGISTER];
1166
1167 /* If reg_base_reg[n] is negative, register n has been set to
1168    reg_offset[n] in mode reg_mode[n] .
1169    If reg_base_reg[n] is non-negative, register n has been set to the
1170    sum of reg_offset[n] and the value of register reg_base_reg[n]
1171    before reg_set_luid[n], calculated in mode reg_mode[n] .  */
1172 static HOST_WIDE_INT reg_offset[FIRST_PSEUDO_REGISTER];
1173 static int reg_base_reg[FIRST_PSEUDO_REGISTER];
1174 static enum machine_mode reg_mode[FIRST_PSEUDO_REGISTER];
1175
1176 /* move2add_luid is linearly increased while scanning the instructions
1177    from first to last.  It is used to set reg_set_luid in
1178    reload_cse_move2add and move2add_note_store.  */
1179 static int move2add_luid;
1180
1181 /* move2add_last_label_luid is set whenever a label is found.  Labels
1182    invalidate all previously collected reg_offset data.  */
1183 static int move2add_last_label_luid;
1184
1185 /* ??? We don't know how zero / sign extension is handled, hence we
1186    can't go from a narrower to a wider mode.  */
1187 #define MODES_OK_FOR_MOVE2ADD(OUTMODE, INMODE) \
1188   (GET_MODE_SIZE (OUTMODE) == GET_MODE_SIZE (INMODE) \
1189    || (GET_MODE_SIZE (OUTMODE) <= GET_MODE_SIZE (INMODE) \
1190        && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (OUTMODE), \
1191                                  GET_MODE_BITSIZE (INMODE))))
1192
1193 static void
1194 reload_cse_move2add (rtx first)
1195 {
1196   int i;
1197   rtx insn;
1198
1199   for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1200     reg_set_luid[i] = 0;
1201
1202   move2add_last_label_luid = 0;
1203   move2add_luid = 2;
1204   for (insn = first; insn; insn = NEXT_INSN (insn), move2add_luid++)
1205     {
1206       rtx pat, note;
1207
1208       if (LABEL_P (insn))
1209         {
1210           move2add_last_label_luid = move2add_luid;
1211           /* We're going to increment move2add_luid twice after a
1212              label, so that we can use move2add_last_label_luid + 1 as
1213              the luid for constants.  */
1214           move2add_luid++;
1215           continue;
1216         }
1217       if (! INSN_P (insn))
1218         continue;
1219       pat = PATTERN (insn);
1220       /* For simplicity, we only perform this optimization on
1221          straightforward SETs.  */
1222       if (GET_CODE (pat) == SET
1223           && REG_P (SET_DEST (pat)))
1224         {
1225           rtx reg = SET_DEST (pat);
1226           int regno = REGNO (reg);
1227           rtx src = SET_SRC (pat);
1228
1229           /* Check if we have valid information on the contents of this
1230              register in the mode of REG.  */
1231           if (reg_set_luid[regno] > move2add_last_label_luid
1232               && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg), reg_mode[regno]))
1233             {
1234               /* Try to transform (set (REGX) (CONST_INT A))
1235                                   ...
1236                                   (set (REGX) (CONST_INT B))
1237                  to
1238                                   (set (REGX) (CONST_INT A))
1239                                   ...
1240                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))
1241                  or
1242                                   (set (REGX) (CONST_INT A))
1243                                   ...
1244                                   (set (STRICT_LOW_PART (REGX)) (CONST_INT B))
1245               */
1246
1247               if (GET_CODE (src) == CONST_INT && reg_base_reg[regno] < 0)
1248                 {
1249                   rtx new_src =
1250                     GEN_INT (trunc_int_for_mode (INTVAL (src)
1251                                                  - reg_offset[regno],
1252                                                  GET_MODE (reg)));
1253                   /* (set (reg) (plus (reg) (const_int 0))) is not canonical;
1254                      use (set (reg) (reg)) instead.
1255                      We don't delete this insn, nor do we convert it into a
1256                      note, to avoid losing register notes or the return
1257                      value flag.  jump2 already knows how to get rid of
1258                      no-op moves.  */
1259                   if (new_src == const0_rtx)
1260                     {
1261                       /* If the constants are different, this is a
1262                          truncation, that, if turned into (set (reg)
1263                          (reg)), would be discarded.  Maybe we should
1264                          try a truncMN pattern?  */
1265                       if (INTVAL (src) == reg_offset [regno])
1266                         validate_change (insn, &SET_SRC (pat), reg, 0);
1267                     }
1268                   else if (rtx_cost (new_src, PLUS) < rtx_cost (src, SET)
1269                            && have_add2_insn (reg, new_src))
1270                     {
1271                       rtx tem = gen_rtx_PLUS (GET_MODE (reg), reg, new_src);
1272                       validate_change (insn, &SET_SRC (pat), tem, 0);
1273                     }
1274                   else
1275                     {
1276                       enum machine_mode narrow_mode;
1277                       for (narrow_mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
1278                            narrow_mode != GET_MODE (reg);
1279                            narrow_mode = GET_MODE_WIDER_MODE (narrow_mode))
1280                         {
1281                           if (have_insn_for (STRICT_LOW_PART, narrow_mode)
1282                               && ((reg_offset[regno]
1283                                    & ~GET_MODE_MASK (narrow_mode))
1284                                   == (INTVAL (src)
1285                                       & ~GET_MODE_MASK (narrow_mode))))
1286                             {
1287                               rtx narrow_reg = gen_rtx_REG (narrow_mode,
1288                                                             REGNO (reg));
1289                               rtx narrow_src =
1290                                 GEN_INT (trunc_int_for_mode (INTVAL (src),
1291                                                              narrow_mode));
1292                               rtx new_set =
1293                                 gen_rtx_SET (VOIDmode,
1294                                              gen_rtx_STRICT_LOW_PART (VOIDmode,
1295                                                                       narrow_reg),
1296                                              narrow_src);
1297                               if (validate_change (insn, &PATTERN (insn),
1298                                                    new_set, 0))
1299                                 break;
1300                             }
1301                         }
1302                     }
1303                   reg_set_luid[regno] = move2add_luid;
1304                   reg_mode[regno] = GET_MODE (reg);
1305                   reg_offset[regno] = INTVAL (src);
1306                   continue;
1307                 }
1308
1309               /* Try to transform (set (REGX) (REGY))
1310                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1311                                   ...
1312                                   (set (REGX) (REGY))
1313                                   (set (REGX) (PLUS (REGX) (CONST_INT B)))
1314                  to
1315                                   (set (REGX) (REGY))
1316                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1317                                   ...
1318                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))  */
1319               else if (REG_P (src)
1320                        && reg_set_luid[regno] == reg_set_luid[REGNO (src)]
1321                        && reg_base_reg[regno] == reg_base_reg[REGNO (src)]
1322                        && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg),
1323                                                  reg_mode[REGNO (src)]))
1324                 {
1325                   rtx next = next_nonnote_insn (insn);
1326                   rtx set = NULL_RTX;
1327                   if (next)
1328                     set = single_set (next);
1329                   if (set
1330                       && SET_DEST (set) == reg
1331                       && GET_CODE (SET_SRC (set)) == PLUS
1332                       && XEXP (SET_SRC (set), 0) == reg
1333                       && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1334                     {
1335                       rtx src3 = XEXP (SET_SRC (set), 1);
1336                       HOST_WIDE_INT added_offset = INTVAL (src3);
1337                       HOST_WIDE_INT base_offset = reg_offset[REGNO (src)];
1338                       HOST_WIDE_INT regno_offset = reg_offset[regno];
1339                       rtx new_src =
1340                         GEN_INT (trunc_int_for_mode (added_offset
1341                                                      + base_offset
1342                                                      - regno_offset,
1343                                                      GET_MODE (reg)));
1344                       int success = 0;
1345
1346                       if (new_src == const0_rtx)
1347                         /* See above why we create (set (reg) (reg)) here.  */
1348                         success
1349                           = validate_change (next, &SET_SRC (set), reg, 0);
1350                       else if ((rtx_cost (new_src, PLUS)
1351                                 < COSTS_N_INSNS (1) + rtx_cost (src3, SET))
1352                                && have_add2_insn (reg, new_src))
1353                         {
1354                           rtx newpat = gen_rtx_SET (VOIDmode,
1355                                                     reg,
1356                                                     gen_rtx_PLUS (GET_MODE (reg),
1357                                                                   reg,
1358                                                                   new_src));
1359                           success
1360                             = validate_change (next, &PATTERN (next),
1361                                                newpat, 0);
1362                         }
1363                       if (success)
1364                         delete_insn (insn);
1365                       insn = next;
1366                       reg_mode[regno] = GET_MODE (reg);
1367                       reg_offset[regno] =
1368                         trunc_int_for_mode (added_offset + base_offset,
1369                                             GET_MODE (reg));
1370                       continue;
1371                     }
1372                 }
1373             }
1374         }
1375
1376       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1377         {
1378           if (REG_NOTE_KIND (note) == REG_INC
1379               && REG_P (XEXP (note, 0)))
1380             {
1381               /* Reset the information about this register.  */
1382               int regno = REGNO (XEXP (note, 0));
1383               if (regno < FIRST_PSEUDO_REGISTER)
1384                 reg_set_luid[regno] = 0;
1385             }
1386         }
1387       note_stores (PATTERN (insn), move2add_note_store, NULL);
1388
1389       /* If INSN is a conditional branch, we try to extract an
1390          implicit set out of it.  */
1391       if (any_condjump_p (insn))
1392         {
1393           rtx cnd = fis_get_condition (insn);
1394
1395           if (cnd != NULL_RTX
1396               && GET_CODE (cnd) == NE
1397               && REG_P (XEXP (cnd, 0))
1398               && !reg_set_p (XEXP (cnd, 0), insn)
1399               /* The following two checks, which are also in
1400                  move2add_note_store, are intended to reduce the
1401                  number of calls to gen_rtx_SET to avoid memory
1402                  allocation if possible.  */
1403               && SCALAR_INT_MODE_P (GET_MODE (XEXP (cnd, 0)))
1404               && hard_regno_nregs[REGNO (XEXP (cnd, 0))][GET_MODE (XEXP (cnd, 0))] == 1
1405               && GET_CODE (XEXP (cnd, 1)) == CONST_INT)
1406             {
1407               rtx implicit_set =
1408                 gen_rtx_SET (VOIDmode, XEXP (cnd, 0), XEXP (cnd, 1));
1409               move2add_note_store (SET_DEST (implicit_set), implicit_set, 0);
1410             }
1411         }
1412
1413       /* If this is a CALL_INSN, all call used registers are stored with
1414          unknown values.  */
1415       if (CALL_P (insn))
1416         {
1417           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1418             {
1419               if (call_used_regs[i])
1420                 /* Reset the information about this register.  */
1421                 reg_set_luid[i] = 0;
1422             }
1423         }
1424     }
1425 }
1426
1427 /* SET is a SET or CLOBBER that sets DST.
1428    Update reg_set_luid, reg_offset and reg_base_reg accordingly.
1429    Called from reload_cse_move2add via note_stores.  */
1430
1431 static void
1432 move2add_note_store (rtx dst, rtx set, void *data ATTRIBUTE_UNUSED)
1433 {
1434   unsigned int regno = 0;
1435   unsigned int i;
1436   enum machine_mode mode = GET_MODE (dst);
1437
1438   if (GET_CODE (dst) == SUBREG)
1439     {
1440       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
1441                                    GET_MODE (SUBREG_REG (dst)),
1442                                    SUBREG_BYTE (dst),
1443                                    GET_MODE (dst));
1444       dst = SUBREG_REG (dst);
1445     }
1446
1447   /* Some targets do argument pushes without adding REG_INC notes.  */
1448
1449   if (MEM_P (dst))
1450     {
1451       dst = XEXP (dst, 0);
1452       if (GET_CODE (dst) == PRE_INC || GET_CODE (dst) == POST_INC
1453           || GET_CODE (dst) == PRE_DEC || GET_CODE (dst) == POST_DEC)
1454         reg_set_luid[REGNO (XEXP (dst, 0))] = 0;
1455       return;
1456     }
1457   if (!REG_P (dst))
1458     return;
1459
1460   regno += REGNO (dst);
1461
1462   if (SCALAR_INT_MODE_P (mode)
1463       && hard_regno_nregs[regno][mode] == 1 && GET_CODE (set) == SET
1464       && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
1465       && GET_CODE (SET_DEST (set)) != SIGN_EXTRACT
1466       && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
1467     {
1468       rtx src = SET_SRC (set);
1469       rtx base_reg;
1470       HOST_WIDE_INT offset;
1471       int base_regno;
1472       /* This may be different from mode, if SET_DEST (set) is a
1473          SUBREG.  */
1474       enum machine_mode dst_mode = GET_MODE (dst);
1475
1476       switch (GET_CODE (src))
1477         {
1478         case PLUS:
1479           if (REG_P (XEXP (src, 0)))
1480             {
1481               base_reg = XEXP (src, 0);
1482
1483               if (GET_CODE (XEXP (src, 1)) == CONST_INT)
1484                 offset = INTVAL (XEXP (src, 1));
1485               else if (REG_P (XEXP (src, 1))
1486                        && (reg_set_luid[REGNO (XEXP (src, 1))]
1487                            > move2add_last_label_luid)
1488                        && (MODES_OK_FOR_MOVE2ADD
1489                            (dst_mode, reg_mode[REGNO (XEXP (src, 1))])))
1490                 {
1491                   if (reg_base_reg[REGNO (XEXP (src, 1))] < 0)
1492                     offset = reg_offset[REGNO (XEXP (src, 1))];
1493                   /* Maybe the first register is known to be a
1494                      constant.  */
1495                   else if (reg_set_luid[REGNO (base_reg)]
1496                            > move2add_last_label_luid
1497                            && (MODES_OK_FOR_MOVE2ADD
1498                                (dst_mode, reg_mode[REGNO (XEXP (src, 1))]))
1499                            && reg_base_reg[REGNO (base_reg)] < 0)
1500                     {
1501                       offset = reg_offset[REGNO (base_reg)];
1502                       base_reg = XEXP (src, 1);
1503                     }
1504                   else
1505                     goto invalidate;
1506                 }
1507               else
1508                 goto invalidate;
1509
1510               break;
1511             }
1512
1513           goto invalidate;
1514
1515         case REG:
1516           base_reg = src;
1517           offset = 0;
1518           break;
1519
1520         case CONST_INT:
1521           /* Start tracking the register as a constant.  */
1522           reg_base_reg[regno] = -1;
1523           reg_offset[regno] = INTVAL (SET_SRC (set));
1524           /* We assign the same luid to all registers set to constants.  */
1525           reg_set_luid[regno] = move2add_last_label_luid + 1;
1526           reg_mode[regno] = mode;
1527           return;
1528
1529         default:
1530         invalidate:
1531           /* Invalidate the contents of the register.  */
1532           reg_set_luid[regno] = 0;
1533           return;
1534         }
1535
1536       base_regno = REGNO (base_reg);
1537       /* If information about the base register is not valid, set it
1538          up as a new base register, pretending its value is known
1539          starting from the current insn.  */
1540       if (reg_set_luid[base_regno] <= move2add_last_label_luid)
1541         {
1542           reg_base_reg[base_regno] = base_regno;
1543           reg_offset[base_regno] = 0;
1544           reg_set_luid[base_regno] = move2add_luid;
1545           reg_mode[base_regno] = mode;
1546         }
1547       else if (! MODES_OK_FOR_MOVE2ADD (dst_mode,
1548                                         reg_mode[base_regno]))
1549         goto invalidate;
1550
1551       reg_mode[regno] = mode;
1552
1553       /* Copy base information from our base register.  */
1554       reg_set_luid[regno] = reg_set_luid[base_regno];
1555       reg_base_reg[regno] = reg_base_reg[base_regno];
1556
1557       /* Compute the sum of the offsets or constants.  */
1558       reg_offset[regno] = trunc_int_for_mode (offset
1559                                               + reg_offset[base_regno],
1560                                               dst_mode);
1561     }
1562   else
1563     {
1564       unsigned int endregno = regno + hard_regno_nregs[regno][mode];
1565
1566       for (i = regno; i < endregno; i++)
1567         /* Reset the information about this register.  */
1568         reg_set_luid[i] = 0;
1569     }
1570 }