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       set = single_set (insn);
 723       if (set != NULL_RTX
 724           && GET_CODE (SET_DEST (set)) == REG
 725           && (HARD_REGNO_NREGS (REGNO (SET_DEST (set)),
 726                                 GET_MODE (SET_DEST (set)))
 727               == 1)
 728           && GET_CODE (SET_SRC (set)) == PLUS
 729           && GET_CODE (XEXP (SET_SRC (set), 1)) == REG
 730           && rtx_equal_p (XEXP (SET_SRC (set), 0), SET_DEST (set))
 731           && last_label_ruid < reg_state[REGNO (SET_DEST (set))].use_ruid)
 732         {
 733           rtx reg = SET_DEST (set);
 734           rtx plus = SET_SRC (set);
 735           rtx base = XEXP (plus, 1);
 736           rtx prev = prev_nonnote_insn (insn);
 737           rtx prev_set = prev ? single_set (prev) : NULL_RTX;
 738           unsigned int regno = REGNO (reg);
 739           rtx const_reg = NULL_RTX;
 740           rtx reg_sum = NULL_RTX;
 741
 742           /* Now, we need an index register.
 743              We'll set index_reg to this index register, const_reg to the
 744              register that is to be loaded with the constant
 745              (denoted as REGZ in the substitution illustration above),
 746              and reg_sum to the register-register that we want to use to
 747              substitute uses of REG (typically in MEMs) with.
 748              First check REG and BASE for being index registers;
 749              we can use them even if they are not dead.  */
 750           if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], regno)
 751               || TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS],
 752                                     REGNO (base)))
 753             {
 754               const_reg = reg;
 755               reg_sum = plus;
 756             }
 757           else
 758             {
 759               /* Otherwise, look for a free index register.  Since we have
 760                  checked above that neither REG nor BASE are index registers,
 761                  if we find anything at all, it will be different from these
 762                  two registers.  */
 763               for (i = first_index_reg; i <= last_index_reg; i++)
 764                 {
 765                   if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS],
 766                                          i)
 767                       && reg_state[i].use_index == RELOAD_COMBINE_MAX_USES
 768                       && reg_state[i].store_ruid <= reg_state[regno].use_ruid
 769                       && HARD_REGNO_NREGS (i, GET_MODE (reg)) == 1)
 770                     {
 771                       rtx index_reg = gen_rtx_REG (GET_MODE (reg), i);
 772
 773                       const_reg = index_reg;
 774                       reg_sum = gen_rtx_PLUS (GET_MODE (reg), index_reg, base);
 775                       break;
 776                     }
 777                 }
 778             }
 779
 780           /* Check that PREV_SET is indeed (set (REGX) (CONST_INT)) and that
 781              (REGY), i.e. BASE, is not clobbered before the last use we'll
 782              create.  */
 783           if (prev_set != 0
 784               && GET_CODE (SET_SRC (prev_set)) == CONST_INT
 785               && rtx_equal_p (SET_DEST (prev_set), reg)
 786               && reg_state[regno].use_index >= 0
 787               && (reg_state[REGNO (base)].store_ruid
 788                   <= reg_state[regno].use_ruid)
 789               && reg_sum != 0)
 790             {
 791               int i;
 792
 793               /* Change destination register and, if necessary, the
 794                  constant value in PREV, the constant loading instruction.  */
 795               validate_change (prev, &SET_DEST (prev_set), const_reg, 1);
 796               if (reg_state[regno].offset != const0_rtx)
 797                 validate_change (prev,
 798                                  &SET_SRC (prev_set),
 799                                  GEN_INT (INTVAL (SET_SRC (prev_set))
 800                                           + INTVAL (reg_state[regno].offset)),
 801                                  1);
 802
 803               /* Now for every use of REG that we have recorded, replace REG
 804                  with REG_SUM.  */
 805               for (i = reg_state[regno].use_index;
 806                    i < RELOAD_COMBINE_MAX_USES; i++)
 807                 validate_change (reg_state[regno].reg_use[i].insn,
 808                                  reg_state[regno].reg_use[i].usep,
 809                                  /* Each change must have its own
 810                                     replacement.  */
 811                                  copy_rtx (reg_sum), 1);
 812
 813               if (apply_change_group ())
 814                 {
 815                   rtx *np;
 816
 817                   /* Delete the reg-reg addition.  */
 818                   delete_insn (insn);
 819
 820                   if (reg_state[regno].offset != const0_rtx)
 821                     /* Previous REG_EQUIV / REG_EQUAL notes for PREV
 822                        are now invalid.  */
 823                     for (np = &REG_NOTES (prev); *np;)
 824                       {
 825                         if (REG_NOTE_KIND (*np) == REG_EQUAL
 826                             || REG_NOTE_KIND (*np) == REG_EQUIV)
 827                           *np = XEXP (*np, 1);
 828                         else
 829                           np = &XEXP (*np, 1);
 830                       }
 831
 832                   reg_state[regno].use_index = RELOAD_COMBINE_MAX_USES;
 833                   reg_state[REGNO (const_reg)].store_ruid
 834                     = reload_combine_ruid;
 835                   continue;
 836                 }
 837             }
 838         }
 839
 840       note_stores (PATTERN (insn), reload_combine_note_store, NULL);
 841
 842       if (GET_CODE (insn) == CALL_INSN)
 843         {
 844           rtx link;
 845
 846           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 847             if (call_used_regs[r])
 848               {
 849                 reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
 850                 reg_state[r].store_ruid = reload_combine_ruid;
 851               }
 852
 853           for (link = CALL_INSN_FUNCTION_USAGE (insn); link;
 854                link = XEXP (link, 1))
 855             {
 856               rtx usage_rtx = XEXP (XEXP (link, 0), 0);
 857               if (GET_CODE (usage_rtx) == REG)
 858                 {
 859                   unsigned int i;
 860                   unsigned int start_reg = REGNO (usage_rtx);
 861                   unsigned int num_regs =
 862                         HARD_REGNO_NREGS (start_reg, GET_MODE (usage_rtx));
 863                   unsigned int end_reg  = start_reg + num_regs - 1;
 864                   for (i = start_reg; i <= end_reg; i++)
 865                     if (GET_CODE (XEXP (link, 0)) == CLOBBER)
 866                       {
 867                         reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
 868                         reg_state[i].store_ruid = reload_combine_ruid;
 869                       }
 870                     else
 871                       reg_state[i].use_index = -1;
 872                  }
 873              }
 874
 875         }
 876       else if (GET_CODE (insn) == JUMP_INSN
 877                && GET_CODE (PATTERN (insn)) != RETURN)
 878         {
 879           /* Non-spill registers might be used at the call destination in
 880              some unknown fashion, so we have to mark the unknown use.  */
 881           HARD_REG_SET *live;
 882
 883           if ((condjump_p (insn) || condjump_in_parallel_p (insn))
 884               && JUMP_LABEL (insn))
 885             live = &LABEL_LIVE (JUMP_LABEL (insn));
 886           else
 887             live = &ever_live_at_start;
 888
 889           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; --i)
 890             if (TEST_HARD_REG_BIT (*live, i))
 891               reg_state[i].use_index = -1;
 892         }
 893
 894       reload_combine_note_use (&PATTERN (insn), insn);
 895       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 896         {
 897           if (REG_NOTE_KIND (note) == REG_INC
 898               && GET_CODE (XEXP (note, 0)) == REG)
 899             {
 900               int regno = REGNO (XEXP (note, 0));
 901
 902               reg_state[regno].store_ruid = reload_combine_ruid;
 903               reg_state[regno].use_index = -1;
 904             }
 905         }
 906     }
 907
 908   free (label_live);
 909 }
 910
 911 /* Check if DST is a register or a subreg of a register; if it is,
 912    update reg_state[regno].store_ruid and reg_state[regno].use_index
 913    accordingly.  Called via note_stores from reload_combine.  */
 914
 915 static void
 916 reload_combine_note_store (rtx dst, rtx set, void *data ATTRIBUTE_UNUSED)
 917 {
 918   int regno = 0;
 919   int i;
 920   enum machine_mode mode = GET_MODE (dst);
 921
 922   if (GET_CODE (dst) == SUBREG)
 923     {
 924       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
 925                                    GET_MODE (SUBREG_REG (dst)),
 926                                    SUBREG_BYTE (dst),
 927                                    GET_MODE (dst));
 928       dst = SUBREG_REG (dst);
 929     }
 930   if (GET_CODE (dst) != REG)
 931     return;
 932   regno += REGNO (dst);
 933
 934   /* note_stores might have stripped a STRICT_LOW_PART, so we have to be
 935      careful with registers / register parts that are not full words.
 936
 937      Similarly for ZERO_EXTRACT and SIGN_EXTRACT.  */
 938   if (GET_CODE (set) != SET
 939       || GET_CODE (SET_DEST (set)) == ZERO_EXTRACT
 940       || GET_CODE (SET_DEST (set)) == SIGN_EXTRACT
 941       || GET_CODE (SET_DEST (set)) == STRICT_LOW_PART)
 942     {
 943       for (i = HARD_REGNO_NREGS (regno, mode) - 1 + regno; i >= regno; i--)
 944         {
 945           reg_state[i].use_index = -1;
 946           reg_state[i].store_ruid = reload_combine_ruid;
 947         }
 948     }
 949   else
 950     {
 951       for (i = HARD_REGNO_NREGS (regno, mode) - 1 + regno; i >= regno; i--)
 952         {
 953           reg_state[i].store_ruid = reload_combine_ruid;
 954           reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
 955         }
 956     }
 957 }
 958
 959 /* XP points to a piece of rtl that has to be checked for any uses of
 960    registers.
 961    *XP is the pattern of INSN, or a part of it.
 962    Called from reload_combine, and recursively by itself.  */
 963 static void
 964 reload_combine_note_use (rtx *xp, rtx insn)
 965 {
 966   rtx x = *xp;
 967   enum rtx_code code = x->code;
 968   const char *fmt;
 969   int i, j;
 970   rtx offset = const0_rtx; /* For the REG case below.  */
 971
 972   switch (code)
 973     {
 974     case SET:
 975       if (GET_CODE (SET_DEST (x)) == REG)
 976         {
 977           reload_combine_note_use (&SET_SRC (x), insn);
 978           return;
 979         }
 980       break;
 981
 982     case USE:
 983       /* If this is the USE of a return value, we can't change it.  */
 984       if (GET_CODE (XEXP (x, 0)) == REG && REG_FUNCTION_VALUE_P (XEXP (x, 0)))
 985         {
 986         /* Mark the return register as used in an unknown fashion.  */
 987           rtx reg = XEXP (x, 0);
 988           int regno = REGNO (reg);
 989           int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
 990
 991           while (--nregs >= 0)
 992             reg_state[regno + nregs].use_index = -1;
 993           return;
 994         }
 995       break;
 996
 997     case CLOBBER:
 998       if (GET_CODE (SET_DEST (x)) == REG)
 999         {
1000           /* No spurious CLOBBERs of pseudo registers may remain.  */
1001           if (REGNO (SET_DEST (x)) >= FIRST_PSEUDO_REGISTER)
1002             abort ();
1003           return;
1004         }
1005       break;
1006
1007     case PLUS:
1008       /* We are interested in (plus (reg) (const_int)) .  */
1009       if (GET_CODE (XEXP (x, 0)) != REG
1010           || GET_CODE (XEXP (x, 1)) != CONST_INT)
1011         break;
1012       offset = XEXP (x, 1);
1013       x = XEXP (x, 0);
1014       /* Fall through.  */
1015     case REG:
1016       {
1017         int regno = REGNO (x);
1018         int use_index;
1019         int nregs;
1020
1021         /* No spurious USEs of pseudo registers may remain.  */
1022         if (regno >= FIRST_PSEUDO_REGISTER)
1023           abort ();
1024
1025         nregs = HARD_REGNO_NREGS (regno, GET_MODE (x));
1026
1027         /* We can't substitute into multi-hard-reg uses.  */
1028         if (nregs > 1)
1029           {
1030             while (--nregs >= 0)
1031               reg_state[regno + nregs].use_index = -1;
1032             return;
1033           }
1034
1035         /* If this register is already used in some unknown fashion, we
1036            can't do anything.
1037            If we decrement the index from zero to -1, we can't store more
1038            uses, so this register becomes used in an unknown fashion.  */
1039         use_index = --reg_state[regno].use_index;
1040         if (use_index < 0)
1041           return;
1042
1043         if (use_index != RELOAD_COMBINE_MAX_USES - 1)
1044           {
1045             /* We have found another use for a register that is already
1046                used later.  Check if the offsets match; if not, mark the
1047                register as used in an unknown fashion.  */
1048             if (! rtx_equal_p (offset, reg_state[regno].offset))
1049               {
1050                 reg_state[regno].use_index = -1;
1051                 return;
1052               }
1053           }
1054         else
1055           {
1056             /* This is the first use of this register we have seen since we
1057                marked it as dead.  */
1058             reg_state[regno].offset = offset;
1059             reg_state[regno].use_ruid = reload_combine_ruid;
1060           }
1061         reg_state[regno].reg_use[use_index].insn = insn;
1062         reg_state[regno].reg_use[use_index].usep = xp;
1063         return;
1064       }
1065
1066     default:
1067       break;
1068     }
1069
1070   /* Recursively process the components of X.  */
1071   fmt = GET_RTX_FORMAT (code);
1072   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1073     {
1074       if (fmt[i] == 'e')
1075         reload_combine_note_use (&XEXP (x, i), insn);
1076       else if (fmt[i] == 'E')
1077         {
1078           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1079             reload_combine_note_use (&XVECEXP (x, i, j), insn);
1080         }
1081     }
1082 }
1083 \f
1084 /* See if we can reduce the cost of a constant by replacing a move
1085    with an add.  We track situations in which a register is set to a
1086    constant or to a register plus a constant.  */
1087 /* We cannot do our optimization across labels.  Invalidating all the
1088    information about register contents we have would be costly, so we
1089    use move2add_last_label_luid to note where the label is and then
1090    later disable any optimization that would cross it.
1091    reg_offset[n] / reg_base_reg[n] / reg_mode[n] are only valid if
1092    reg_set_luid[n] is greater than move2add_last_label_luid.  */
1093 static int reg_set_luid[FIRST_PSEUDO_REGISTER];
1094
1095 /* If reg_base_reg[n] is negative, register n has been set to
1096    reg_offset[n] in mode reg_mode[n] .
1097    If reg_base_reg[n] is non-negative, register n has been set to the
1098    sum of reg_offset[n] and the value of register reg_base_reg[n]
1099    before reg_set_luid[n], calculated in mode reg_mode[n] .  */
1100 static HOST_WIDE_INT reg_offset[FIRST_PSEUDO_REGISTER];
1101 static int reg_base_reg[FIRST_PSEUDO_REGISTER];
1102 static enum machine_mode reg_mode[FIRST_PSEUDO_REGISTER];
1103
1104 /* move2add_luid is linearly increased while scanning the instructions
1105    from first to last.  It is used to set reg_set_luid in
1106    reload_cse_move2add and move2add_note_store.  */
1107 static int move2add_luid;
1108
1109 /* move2add_last_label_luid is set whenever a label is found.  Labels
1110    invalidate all previously collected reg_offset data.  */
1111 static int move2add_last_label_luid;
1112
1113 /* ??? We don't know how zero / sign extension is handled, hence we
1114    can't go from a narrower to a wider mode.  */
1115 #define MODES_OK_FOR_MOVE2ADD(OUTMODE, INMODE) \
1116   (GET_MODE_SIZE (OUTMODE) == GET_MODE_SIZE (INMODE) \
1117    || (GET_MODE_SIZE (OUTMODE) <= GET_MODE_SIZE (INMODE) \
1118        && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (OUTMODE), \
1119                                  GET_MODE_BITSIZE (INMODE))))
1120
1121 static void
1122 reload_cse_move2add (rtx first)
1123 {
1124   int i;
1125   rtx insn;
1126
1127   for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1128     reg_set_luid[i] = 0;
1129
1130   move2add_last_label_luid = 0;
1131   move2add_luid = 2;
1132   for (insn = first; insn; insn = NEXT_INSN (insn), move2add_luid++)
1133     {
1134       rtx pat, note;
1135
1136       if (GET_CODE (insn) == CODE_LABEL)
1137         {
1138           move2add_last_label_luid = move2add_luid;
1139           /* We're going to increment move2add_luid twice after a
1140              label, so that we can use move2add_last_label_luid + 1 as
1141              the luid for constants.  */
1142           move2add_luid++;
1143           continue;
1144         }
1145       if (! INSN_P (insn))
1146         continue;
1147       pat = PATTERN (insn);
1148       /* For simplicity, we only perform this optimization on
1149          straightforward SETs.  */
1150       if (GET_CODE (pat) == SET
1151           && GET_CODE (SET_DEST (pat)) == REG)
1152         {
1153           rtx reg = SET_DEST (pat);
1154           int regno = REGNO (reg);
1155           rtx src = SET_SRC (pat);
1156
1157           /* Check if we have valid information on the contents of this
1158              register in the mode of REG.  */
1159           if (reg_set_luid[regno] > move2add_last_label_luid
1160               && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg), reg_mode[regno]))
1161             {
1162               /* Try to transform (set (REGX) (CONST_INT A))
1163                                   ...
1164                                   (set (REGX) (CONST_INT B))
1165                  to
1166                                   (set (REGX) (CONST_INT A))
1167                                   ...
1168                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))
1169                  or
1170                                   (set (REGX) (CONST_INT A))
1171                                   ...
1172                                   (set (STRICT_LOW_PART (REGX)) (CONST_INT B))
1173               */
1174
1175               if (GET_CODE (src) == CONST_INT && reg_base_reg[regno] < 0)
1176                 {
1177                   rtx new_src =
1178                     GEN_INT (trunc_int_for_mode (INTVAL (src)
1179                                                  - reg_offset[regno],
1180                                                  GET_MODE (reg)));
1181                   /* (set (reg) (plus (reg) (const_int 0))) is not canonical;
1182                      use (set (reg) (reg)) instead.
1183                      We don't delete this insn, nor do we convert it into a
1184                      note, to avoid losing register notes or the return
1185                      value flag.  jump2 already knows how to get rid of
1186                      no-op moves.  */
1187                   if (new_src == const0_rtx)
1188                     {
1189                       /* If the constants are different, this is a
1190                          truncation, that, if turned into (set (reg)
1191                          (reg)), would be discarded.  Maybe we should
1192                          try a truncMN pattern?  */
1193                       if (INTVAL (src) == reg_offset [regno])
1194                         validate_change (insn, &SET_SRC (pat), reg, 0);
1195                     }
1196                   else if (rtx_cost (new_src, PLUS) < rtx_cost (src, SET)
1197                            && have_add2_insn (reg, new_src))
1198                     {
1199                       rtx newpat = gen_add2_insn (reg, new_src);
1200                       if (INSN_P (newpat) && NEXT_INSN (newpat) == NULL_RTX)
1201                         newpat = PATTERN (newpat);
1202                       /* If it was the first insn of a sequence or
1203                          some other emitted insn, validate_change will
1204                          reject it.  */
1205                       validate_change (insn, &PATTERN (insn),
1206                                        newpat, 0);
1207                     }
1208                   else
1209                     {
1210                       enum machine_mode narrow_mode;
1211                       for (narrow_mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
1212                            narrow_mode != GET_MODE (reg);
1213                            narrow_mode = GET_MODE_WIDER_MODE (narrow_mode))
1214                         {
1215                           if (have_insn_for (STRICT_LOW_PART, narrow_mode)
1216                               && ((reg_offset[regno]
1217                                    & ~GET_MODE_MASK (narrow_mode))
1218                                   == (INTVAL (src)
1219                                       & ~GET_MODE_MASK (narrow_mode))))
1220                             {
1221                               rtx narrow_reg = gen_rtx_REG (narrow_mode,
1222                                                             REGNO (reg));
1223                               rtx narrow_src =
1224                                 GEN_INT (trunc_int_for_mode (INTVAL (src),
1225                                                              narrow_mode));
1226                               rtx new_set =
1227                                 gen_rtx_SET (VOIDmode,
1228                                              gen_rtx_STRICT_LOW_PART (VOIDmode,
1229                                                                       narrow_reg),
1230                                              narrow_src);
1231                               if (validate_change (insn, &PATTERN (insn),
1232                                                    new_set, 0))
1233                                 break;
1234                             }
1235                         }
1236                     }
1237                   reg_set_luid[regno] = move2add_luid;
1238                   reg_mode[regno] = GET_MODE (reg);
1239                   reg_offset[regno] = INTVAL (src);
1240                   continue;
1241                 }
1242
1243               /* Try to transform (set (REGX) (REGY))
1244                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1245                                   ...
1246                                   (set (REGX) (REGY))
1247                                   (set (REGX) (PLUS (REGX) (CONST_INT B)))
1248                  to
1249                                   (set (REGX) (REGY))
1250                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1251                                   ...
1252                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))  */
1253               else if (GET_CODE (src) == REG
1254                        && reg_set_luid[regno] == reg_set_luid[REGNO (src)]
1255                        && reg_base_reg[regno] == reg_base_reg[REGNO (src)]
1256                        && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg),
1257                                                  reg_mode[REGNO (src)]))
1258                 {
1259                   rtx next = next_nonnote_insn (insn);
1260                   rtx set = NULL_RTX;
1261                   if (next)
1262                     set = single_set (next);
1263                   if (set
1264                       && SET_DEST (set) == reg
1265                       && GET_CODE (SET_SRC (set)) == PLUS
1266                       && XEXP (SET_SRC (set), 0) == reg
1267                       && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1268                     {
1269                       rtx src3 = XEXP (SET_SRC (set), 1);
1270                       HOST_WIDE_INT added_offset = INTVAL (src3);
1271                       HOST_WIDE_INT base_offset = reg_offset[REGNO (src)];
1272                       HOST_WIDE_INT regno_offset = reg_offset[regno];
1273                       rtx new_src =
1274                         GEN_INT (trunc_int_for_mode (added_offset
1275                                                      + base_offset
1276                                                      - regno_offset,
1277                                                      GET_MODE (reg)));
1278                       int success = 0;
1279
1280                       if (new_src == const0_rtx)
1281                         /* See above why we create (set (reg) (reg)) here.  */
1282                         success
1283                           = validate_change (next, &SET_SRC (set), reg, 0);
1284                       else if ((rtx_cost (new_src, PLUS)
1285                                 < COSTS_N_INSNS (1) + rtx_cost (src3, SET))
1286                                && have_add2_insn (reg, new_src))
1287                         {
1288                           rtx newpat = gen_add2_insn (reg, new_src);
1289                           if (INSN_P (newpat)
1290                               && NEXT_INSN (newpat) == NULL_RTX)
1291                             newpat = PATTERN (newpat);
1292                           success
1293                             = validate_change (next, &PATTERN (next),
1294                                                newpat, 0);
1295                         }
1296                       if (success)
1297                         delete_insn (insn);
1298                       insn = next;
1299                       reg_mode[regno] = GET_MODE (reg);
1300                       reg_offset[regno] =
1301                         trunc_int_for_mode (added_offset + base_offset,
1302                                             GET_MODE (reg));
1303                       continue;
1304                     }
1305                 }
1306             }
1307         }
1308
1309       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1310         {
1311           if (REG_NOTE_KIND (note) == REG_INC
1312               && GET_CODE (XEXP (note, 0)) == REG)
1313             {
1314               /* Reset the information about this register.  */
1315               int regno = REGNO (XEXP (note, 0));
1316               if (regno < FIRST_PSEUDO_REGISTER)
1317                 reg_set_luid[regno] = 0;
1318             }
1319         }
1320       note_stores (PATTERN (insn), move2add_note_store, NULL);
1321
1322       /* If INSN is a conditional branch, we try to extract an
1323          implicit set out of it.  */
1324       if (any_condjump_p (insn) && onlyjump_p (insn))
1325         {
1326           rtx cnd = fis_get_condition (insn);
1327
1328           if (cnd != NULL_RTX
1329               && GET_CODE (cnd) == NE
1330               && GET_CODE (XEXP (cnd, 0)) == REG
1331               /* The following two checks, which are also in
1332                  move2add_note_store, are intended to reduce the
1333                  number of calls to gen_rtx_SET to avoid memory
1334                  allocation if possible.  */
1335               && SCALAR_INT_MODE_P (GET_MODE (XEXP (cnd, 0)))
1336               && HARD_REGNO_NREGS (REGNO (XEXP (cnd, 0)), GET_MODE (XEXP (cnd, 0))) == 1
1337               && GET_CODE (XEXP (cnd, 1)) == CONST_INT)
1338             {
1339               rtx implicit_set =
1340                 gen_rtx_SET (VOIDmode, XEXP (cnd, 0), XEXP (cnd, 1));
1341               move2add_note_store (SET_DEST (implicit_set), implicit_set, 0);
1342             }
1343         }
1344
1345       /* If this is a CALL_INSN, all call used registers are stored with
1346          unknown values.  */
1347       if (GET_CODE (insn) == CALL_INSN)
1348         {
1349           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1350             {
1351               if (call_used_regs[i])
1352                 /* Reset the information about this register.  */
1353                 reg_set_luid[i] = 0;
1354             }
1355         }
1356     }
1357 }
1358
1359 /* SET is a SET or CLOBBER that sets DST.
1360    Update reg_set_luid, reg_offset and reg_base_reg accordingly.
1361    Called from reload_cse_move2add via note_stores.  */
1362
1363 static void
1364 move2add_note_store (rtx dst, rtx set, void *data ATTRIBUTE_UNUSED)
1365 {
1366   unsigned int regno = 0;
1367   unsigned int i;
1368   enum machine_mode mode = GET_MODE (dst);
1369
1370   if (GET_CODE (dst) == SUBREG)
1371     {
1372       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
1373                                    GET_MODE (SUBREG_REG (dst)),
1374                                    SUBREG_BYTE (dst),
1375                                    GET_MODE (dst));
1376       dst = SUBREG_REG (dst);
1377     }
1378
1379   /* Some targets do argument pushes without adding REG_INC notes.  */
1380
1381   if (GET_CODE (dst) == MEM)
1382     {
1383       dst = XEXP (dst, 0);
1384       if (GET_CODE (dst) == PRE_INC || GET_CODE (dst) == POST_INC
1385           || GET_CODE (dst) == PRE_DEC || GET_CODE (dst) == POST_DEC)
1386         reg_set_luid[REGNO (XEXP (dst, 0))] = 0;
1387       return;
1388     }
1389   if (GET_CODE (dst) != REG)
1390     return;
1391
1392   regno += REGNO (dst);
1393
1394   if (SCALAR_INT_MODE_P (mode)
1395       && HARD_REGNO_NREGS (regno, mode) == 1 && GET_CODE (set) == SET
1396       && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
1397       && GET_CODE (SET_DEST (set)) != SIGN_EXTRACT
1398       && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
1399     {
1400       rtx src = SET_SRC (set);
1401       rtx base_reg;
1402       HOST_WIDE_INT offset;
1403       int base_regno;
1404       /* This may be different from mode, if SET_DEST (set) is a
1405          SUBREG.  */
1406       enum machine_mode dst_mode = GET_MODE (dst);
1407
1408       switch (GET_CODE (src))
1409         {
1410         case PLUS:
1411           if (GET_CODE (XEXP (src, 0)) == REG)
1412             {
1413               base_reg = XEXP (src, 0);
1414
1415               if (GET_CODE (XEXP (src, 1)) == CONST_INT)
1416                 offset = INTVAL (XEXP (src, 1));
1417               else if (GET_CODE (XEXP (src, 1)) == REG
1418                        && (reg_set_luid[REGNO (XEXP (src, 1))]
1419                            > move2add_last_label_luid)
1420                        && (MODES_OK_FOR_MOVE2ADD
1421                            (dst_mode, reg_mode[REGNO (XEXP (src, 1))])))
1422                 {
1423                   if (reg_base_reg[REGNO (XEXP (src, 1))] < 0)
1424                     offset = reg_offset[REGNO (XEXP (src, 1))];
1425                   /* Maybe the first register is known to be a
1426                      constant.  */
1427                   else if (reg_set_luid[REGNO (base_reg)]
1428                            > move2add_last_label_luid
1429                            && (MODES_OK_FOR_MOVE2ADD
1430                                (dst_mode, reg_mode[REGNO (XEXP (src, 1))]))
1431                            && reg_base_reg[REGNO (base_reg)] < 0)
1432                     {
1433                       offset = reg_offset[REGNO (base_reg)];
1434                       base_reg = XEXP (src, 1);
1435                     }
1436                   else
1437                     goto invalidate;
1438                 }
1439               else
1440                 goto invalidate;
1441
1442               break;
1443             }
1444
1445           goto invalidate;
1446
1447         case REG:
1448           base_reg = src;
1449           offset = 0;
1450           break;
1451
1452         case CONST_INT:
1453           /* Start tracking the register as a constant.  */
1454           reg_base_reg[regno] = -1;
1455           reg_offset[regno] = INTVAL (SET_SRC (set));
1456           /* We assign the same luid to all registers set to constants.  */
1457           reg_set_luid[regno] = move2add_last_label_luid + 1;
1458           reg_mode[regno] = mode;
1459           return;
1460
1461         default:
1462         invalidate:
1463           /* Invalidate the contents of the register.  */
1464           reg_set_luid[regno] = 0;
1465           return;
1466         }
1467
1468       base_regno = REGNO (base_reg);
1469       /* If information about the base register is not valid, set it
1470          up as a new base register, pretending its value is known
1471          starting from the current insn.  */
1472       if (reg_set_luid[base_regno] <= move2add_last_label_luid)
1473         {
1474           reg_base_reg[base_regno] = base_regno;
1475           reg_offset[base_regno] = 0;
1476           reg_set_luid[base_regno] = move2add_luid;
1477           reg_mode[base_regno] = mode;
1478         }
1479       else if (! MODES_OK_FOR_MOVE2ADD (dst_mode,
1480                                         reg_mode[base_regno]))
1481         goto invalidate;
1482
1483       reg_mode[regno] = mode;
1484
1485       /* Copy base information from our base register.  */
1486       reg_set_luid[regno] = reg_set_luid[base_regno];
1487       reg_base_reg[regno] = reg_base_reg[base_regno];
1488
1489       /* Compute the sum of the offsets or constants.  */
1490       reg_offset[regno] = trunc_int_for_mode (offset
1491                                               + reg_offset[base_regno],
1492                                               dst_mode);
1493     }
1494   else
1495     {
1496       unsigned int endregno = regno + HARD_REGNO_NREGS (regno, mode);
1497
1498       for (i = regno; i < endregno; i++)
1499         /* Reset the information about this register.  */
1500         reg_set_luid[i] = 0;
1501     }
1502 }