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