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