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