gcc/postreload.c

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