gcc/auto-inc-dec.c

   1 /* Discovery of auto-inc and auto-dec instructions.
   2    Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
   3    Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
   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 3, 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "insn-config.h"
  31 #include "regs.h"
  32 #include "flags.h"
  33 #include "output.h"
  34 #include "function.h"
  35 #include "except.h"
  36 #include "toplev.h"
  37 #include "recog.h"
  38 #include "expr.h"
  39 #include "timevar.h"
  40 #include "tree-pass.h"
  41 #include "df.h"
  42 #include "dbgcnt.h"
  43
  44 /* This pass was originally removed from flow.c. However there is
  45    almost nothing that remains of that code.
  46
  47    There are (4) basic forms that are matched:
  48
  49            a <- b + c
  50            ...
  51            *a
  52
  53         becomes
  54
  55            a <- b
  56            ...
  57            *(a += c) pre
  58            a += c
  59            ...
  60            *a
  61
  62         becomes
  63
  64            *(a += c) pre
  65            *a
  66            ...
  67            b <- a + c
  68
  69            for this case to be true, b must not be assigned or used between
  70            the *a and the assignment to b.  B must also be a Pmode reg.
  71
  72         becomes
  73
  74            b <- a
  75            ...
  76            *(b += c) post
  77            *a
  78            ...
  79            a <- a + c
  80
  81         becomes
  82
  83            *(a += c) post
  84
  85   There are three types of values of c.
  86
  87     1) c is a constant equal to the width of the value being accessed by
  88        the pointer.  This is useful for machines that have
  89        HAVE_PRE_INCREMENT, HAVE_POST_INCREMENT, HAVE_PRE_DECREMENT or
  90        HAVE_POST_DECREMENT defined.
  91
  92     2) c is a constant not equal to the width of the value being accessed
  93        by the pointer.  This is useful for machines that have
  94        HAVE_PRE_MODIFY_DISP, HAVE_POST_MODIFY_DISP defined.
  95
  96     3) c is a register.  This is useful for machines that have
  97        HAVE_PRE_MODIFY_REG,  HAVE_POST_MODIFY_REG
  98
  99   The is one special case: if a already had an offset equal to it +-
 100   its width and that offset is equal to -c when the increment was
 101   before the ref or +c if the increment was after the ref, then if we
 102   can do the combination but switch the pre/post bit.
 103
 104         (1) FORM_PRE_ADD
 105
 106            a <- b + c
 107            ...
 108            *(a - c)
 109
 110         becomes
 111
 112            a <- b
 113            ...
 114            *(a += c) post
 115
 116         (2) FORM_PRE_INC
 117
 118            a += c
 119            ...
 120            *(a - c)
 121
 122         becomes
 123
 124            *(a += c) post
 125
 126         (3) FORM_POST_ADD
 127
 128            *(a + c)
 129            ...
 130            b <- a + c
 131
 132            for this case to be true, b must not be assigned or used between
 133            the *a and the assignment to b. B must also be a Pmode reg.
 134
 135         becomes
 136
 137            b <- a
 138            ...
 139            *(b += c) pre
 140
 141
 142         (4) FORM_POST_INC
 143
 144            *(a + c)
 145            ...
 146            a <- a + c
 147
 148         becomes
 149
 150            *(a += c) pre
 151 */
 152 #ifdef AUTO_INC_DEC
 153
 154 enum form
 155 {
 156   FORM_PRE_ADD,
 157   FORM_PRE_INC,
 158   FORM_POST_ADD,
 159   FORM_POST_INC,
 160   FORM_last
 161 };
 162
 163 /* The states of the second operands of mem refs and inc insns.  If no
 164    second operand of the mem_ref was found, it is assumed to just be
 165    ZERO.  SIZE is the size of the mode accessed in the memref.  The
 166    ANY is used for constants that are not +-size or 0.  REG is used if
 167    the forms are reg1 + reg2.  */
 168
 169 enum inc_state
 170 {
 171   INC_ZERO,           /* == 0  */
 172   INC_NEG_SIZE,       /* == +size  */
 173   INC_POS_SIZE,       /* == -size */
 174   INC_NEG_ANY,        /* == some -constant  */
 175   INC_POS_ANY,        /* == some +constant  */
 176   INC_REG,            /* == some register  */
 177   INC_last
 178 };
 179
 180 /* The eight forms that pre/post inc/dec can take.  */
 181 enum gen_form
 182 {
 183   NOTHING,
 184   SIMPLE_PRE_INC,     /* ++size  */
 185   SIMPLE_POST_INC,    /* size++  */
 186   SIMPLE_PRE_DEC,     /* --size  */
 187   SIMPLE_POST_DEC,    /* size--  */
 188   DISP_PRE,           /* ++con   */
 189   DISP_POST,          /* con++   */
 190   REG_PRE,            /* ++reg   */
 191   REG_POST            /* reg++   */
 192 };
 193
 194 /* Tmp mem rtx for use in cost modeling.  */
 195 static rtx mem_tmp;
 196
 197 static enum inc_state
 198 set_inc_state (HOST_WIDE_INT val, int size)
 199 {
 200   if (val == 0)
 201     return INC_ZERO;
 202   if (val < 0)
 203     return (val == -size) ? INC_NEG_SIZE : INC_NEG_ANY;
 204   else
 205     return (val == size) ? INC_POS_SIZE : INC_POS_ANY;
 206 }
 207
 208 /* The DECISION_TABLE that describes what form, if any, the increment
 209    or decrement will take. It is a three dimensional table.  The first
 210    index is the type of constant or register found as the second
 211    operand of the inc insn.  The second index is the type of constant
 212    or register found as the second operand of the memory reference (if
 213    no second operand exists, 0 is used).  The third index is the form
 214    and location (relative to the mem reference) of inc insn.  */
 215
 216 static bool initialized = false;
 217 static enum gen_form decision_table[INC_last][INC_last][FORM_last];
 218
 219 static void
 220 init_decision_table (void)
 221 {
 222   enum gen_form value;
 223
 224   if (HAVE_PRE_INCREMENT || HAVE_PRE_MODIFY_DISP)
 225     {
 226       /* Prefer the simple form if both are available.  */
 227       value = (HAVE_PRE_INCREMENT) ? SIMPLE_PRE_INC : DISP_PRE;
 228
 229       decision_table[INC_POS_SIZE][INC_ZERO][FORM_PRE_ADD] = value;
 230       decision_table[INC_POS_SIZE][INC_ZERO][FORM_PRE_INC] = value;
 231
 232       decision_table[INC_POS_SIZE][INC_POS_SIZE][FORM_POST_ADD] = value;
 233       decision_table[INC_POS_SIZE][INC_POS_SIZE][FORM_POST_INC] = value;
 234     }
 235
 236   if (HAVE_POST_INCREMENT || HAVE_POST_MODIFY_DISP)
 237     {
 238       /* Prefer the simple form if both are available.  */
 239       value = (HAVE_POST_INCREMENT) ? SIMPLE_POST_INC : DISP_POST;
 240
 241       decision_table[INC_POS_SIZE][INC_ZERO][FORM_POST_ADD] = value;
 242       decision_table[INC_POS_SIZE][INC_ZERO][FORM_POST_INC] = value;
 243
 244       decision_table[INC_POS_SIZE][INC_NEG_SIZE][FORM_PRE_ADD] = value;
 245       decision_table[INC_POS_SIZE][INC_NEG_SIZE][FORM_PRE_INC] = value;
 246     }
 247
 248   if (HAVE_PRE_DECREMENT || HAVE_PRE_MODIFY_DISP)
 249     {
 250       /* Prefer the simple form if both are available.  */
 251       value = (HAVE_PRE_DECREMENT) ? SIMPLE_PRE_DEC : DISP_PRE;
 252
 253       decision_table[INC_NEG_SIZE][INC_ZERO][FORM_PRE_ADD] = value;
 254       decision_table[INC_NEG_SIZE][INC_ZERO][FORM_PRE_INC] = value;
 255
 256       decision_table[INC_NEG_SIZE][INC_NEG_SIZE][FORM_POST_ADD] = value;
 257       decision_table[INC_NEG_SIZE][INC_NEG_SIZE][FORM_POST_INC] = value;
 258     }
 259
 260   if (HAVE_POST_DECREMENT || HAVE_POST_MODIFY_DISP)
 261     {
 262       /* Prefer the simple form if both are available.  */
 263       value = (HAVE_POST_DECREMENT) ? SIMPLE_POST_DEC : DISP_POST;
 264
 265       decision_table[INC_NEG_SIZE][INC_ZERO][FORM_POST_ADD] = value;
 266       decision_table[INC_NEG_SIZE][INC_ZERO][FORM_POST_INC] = value;
 267
 268       decision_table[INC_NEG_SIZE][INC_POS_SIZE][FORM_PRE_ADD] = value;
 269       decision_table[INC_NEG_SIZE][INC_POS_SIZE][FORM_PRE_INC] = value;
 270     }
 271
 272   if (HAVE_PRE_MODIFY_DISP)
 273     {
 274       decision_table[INC_POS_ANY][INC_ZERO][FORM_PRE_ADD] = DISP_PRE;
 275       decision_table[INC_POS_ANY][INC_ZERO][FORM_PRE_INC] = DISP_PRE;
 276
 277       decision_table[INC_POS_ANY][INC_POS_ANY][FORM_POST_ADD] = DISP_PRE;
 278       decision_table[INC_POS_ANY][INC_POS_ANY][FORM_POST_INC] = DISP_PRE;
 279
 280       decision_table[INC_NEG_ANY][INC_ZERO][FORM_PRE_ADD] = DISP_PRE;
 281       decision_table[INC_NEG_ANY][INC_ZERO][FORM_PRE_INC] = DISP_PRE;
 282
 283       decision_table[INC_NEG_ANY][INC_NEG_ANY][FORM_POST_ADD] = DISP_PRE;
 284       decision_table[INC_NEG_ANY][INC_NEG_ANY][FORM_POST_INC] = DISP_PRE;
 285     }
 286
 287   if (HAVE_POST_MODIFY_DISP)
 288     {
 289       decision_table[INC_POS_ANY][INC_ZERO][FORM_POST_ADD] = DISP_POST;
 290       decision_table[INC_POS_ANY][INC_ZERO][FORM_POST_INC] = DISP_POST;
 291
 292       decision_table[INC_POS_ANY][INC_NEG_ANY][FORM_PRE_ADD] = DISP_POST;
 293       decision_table[INC_POS_ANY][INC_NEG_ANY][FORM_PRE_INC] = DISP_POST;
 294
 295       decision_table[INC_NEG_ANY][INC_ZERO][FORM_POST_ADD] = DISP_POST;
 296       decision_table[INC_NEG_ANY][INC_ZERO][FORM_POST_INC] = DISP_POST;
 297
 298       decision_table[INC_NEG_ANY][INC_POS_ANY][FORM_PRE_ADD] = DISP_POST;
 299       decision_table[INC_NEG_ANY][INC_POS_ANY][FORM_PRE_INC] = DISP_POST;
 300     }
 301
 302   /* This is much simpler than the other cases because we do not look
 303      for the reg1-reg2 case.  Note that we do not have a INC_POS_REG
 304      and INC_NEG_REG states.  Most of the use of such states would be
 305      on a target that had an R1 - R2 update address form.
 306
 307      There is the remote possibility that you could also catch a = a +
 308      b; *(a - b) as a postdecrement of (a + b).  However, it is
 309      unclear if *(a - b) would ever be generated on a machine that did
 310      not have that kind of addressing mode.  The IA-64 and RS6000 will
 311      not do this, and I cannot speak for any other.  If any
 312      architecture does have an a-b update for, these cases should be
 313      added.  */
 314   if (HAVE_PRE_MODIFY_REG)
 315     {
 316       decision_table[INC_REG][INC_ZERO][FORM_PRE_ADD] = REG_PRE;
 317       decision_table[INC_REG][INC_ZERO][FORM_PRE_INC] = REG_PRE;
 318
 319       decision_table[INC_REG][INC_REG][FORM_POST_ADD] = REG_PRE;
 320       decision_table[INC_REG][INC_REG][FORM_POST_INC] = REG_PRE;
 321     }
 322
 323   if (HAVE_POST_MODIFY_REG)
 324     {
 325       decision_table[INC_REG][INC_ZERO][FORM_POST_ADD] = REG_POST;
 326       decision_table[INC_REG][INC_ZERO][FORM_POST_INC] = REG_POST;
 327     }
 328
 329   initialized = true;
 330 }
 331
 332 /* Parsed fields of an inc insn of the form "reg_res = reg0+reg1" or
 333    "reg_res = reg0+c".  */
 334
 335 static struct inc_insn
 336 {
 337   rtx insn;           /* The insn being parsed.  */
 338   rtx pat;            /* The pattern of the insn.  */
 339   bool reg1_is_const; /* True if reg1 is const, false if reg1 is a reg.  */
 340   enum form form;
 341   rtx reg_res;
 342   rtx reg0;
 343   rtx reg1;
 344   enum inc_state reg1_state;/* The form of the const if reg1 is a const.  */
 345   HOST_WIDE_INT reg1_val;/* Value if reg1 is const.  */
 346 } inc_insn;
 347
 348
 349 /* Dump the parsed inc insn to FILE.  */
 350
 351 static void
 352 dump_inc_insn (FILE *file)
 353 {
 354   const char *f = ((inc_insn.form == FORM_PRE_ADD)
 355               || (inc_insn.form == FORM_PRE_INC)) ? "pre" : "post";
 356
 357   dump_insn_slim (file, inc_insn.insn);
 358
 359   switch (inc_insn.form)
 360     {
 361     case FORM_PRE_ADD:
 362     case FORM_POST_ADD:
 363       if (inc_insn.reg1_is_const)
 364         fprintf (file, "found %s add(%d) r[%d]=r[%d]+%d\n",
 365                  f, INSN_UID (inc_insn.insn),
 366                  REGNO (inc_insn.reg_res),
 367                  REGNO (inc_insn.reg0), (int) inc_insn.reg1_val);
 368       else
 369         fprintf (file, "found %s add(%d) r[%d]=r[%d]+r[%d]\n",
 370                  f, INSN_UID (inc_insn.insn),
 371                  REGNO (inc_insn.reg_res),
 372                  REGNO (inc_insn.reg0), REGNO (inc_insn.reg1));
 373       break;
 374
 375     case FORM_PRE_INC:
 376     case FORM_POST_INC:
 377       if (inc_insn.reg1_is_const)
 378         fprintf (file, "found %s inc(%d) r[%d]+=%d\n",
 379                  f, INSN_UID (inc_insn.insn),
 380                  REGNO (inc_insn.reg_res), (int) inc_insn.reg1_val);
 381       else
 382         fprintf (file, "found %s inc(%d) r[%d]+=r[%d]\n",
 383                  f, INSN_UID (inc_insn.insn),
 384                  REGNO (inc_insn.reg_res), REGNO (inc_insn.reg1));
 385       break;
 386
 387     default:
 388       break;
 389     }
 390 }
 391
 392
 393 /* Parsed fields of a mem ref of the form "*(reg0+reg1)" or "*(reg0+c)".  */
 394
 395 static struct mem_insn
 396 {
 397   rtx insn;           /* The insn being parsed.  */
 398   rtx pat;            /* The pattern of the insn.  */
 399   rtx *mem_loc;       /* The address of the field that holds the mem */
 400                       /* that is to be replaced.  */
 401   bool reg1_is_const; /* True if reg1 is const, false if reg1 is a reg.  */
 402   rtx reg0;
 403   rtx reg1;           /* This is either a reg or a const depending on
 404                          reg1_is_const.  */
 405   enum inc_state reg1_state;/* The form of the const if reg1 is a const.  */
 406   HOST_WIDE_INT reg1_val;/* Value if reg1 is const.  */
 407 } mem_insn;
 408
 409
 410 /* Dump the parsed mem insn to FILE.  */
 411
 412 static void
 413 dump_mem_insn (FILE *file)
 414 {
 415   dump_insn_slim (file, mem_insn.insn);
 416
 417   if (mem_insn.reg1_is_const)
 418     fprintf (file, "found mem(%d) *(r[%d]+%d)\n",
 419              INSN_UID (mem_insn.insn),
 420              REGNO (mem_insn.reg0), (int) mem_insn.reg1_val);
 421   else
 422     fprintf (file, "found mem(%d) *(r[%d]+r[%d])\n",
 423              INSN_UID (mem_insn.insn),
 424              REGNO (mem_insn.reg0), REGNO (mem_insn.reg1));
 425 }
 426
 427
 428 /* The following three arrays contain pointers to instructions. They
 429    are indexed by REGNO.  At any point in the basic block where we are
 430    looking these three arrays contain, respectively, the next insn
 431    that uses REGNO, the next inc or add insn that uses REGNO and the
 432    next insn that sets REGNO.
 433
 434    The arrays are not cleared when we move from block to block so
 435    whenever an insn is retrieved from these arrays, it's block number
 436    must be compared with the current block.
 437 */
 438
 439 static rtx *reg_next_use = NULL;
 440 static rtx *reg_next_inc_use = NULL;
 441 static rtx *reg_next_def = NULL;
 442
 443
 444 /* Move dead note that match PATTERN to TO_INSN from FROM_INSN.  We do
 445    not really care about moving any other notes from the inc or add
 446    insn.  Moving the REG_EQUAL and REG_EQUIV is clearly wrong and it
 447    does not appear that there are any other kinds of relevant notes.  */
 448
 449 static void
 450 move_dead_notes (rtx to_insn, rtx from_insn, rtx pattern)
 451 {
 452   rtx note;
 453   rtx next_note;
 454   rtx prev_note = NULL;
 455
 456   for (note = REG_NOTES (from_insn); note; note = next_note)
 457     {
 458       next_note = XEXP (note, 1);
 459
 460       if ((REG_NOTE_KIND (note) == REG_DEAD)
 461           && pattern == XEXP (note, 0))
 462         {
 463           XEXP (note, 1) = REG_NOTES (to_insn);
 464           REG_NOTES (to_insn) = note;
 465           if (prev_note)
 466             XEXP (prev_note, 1) = next_note;
 467           else
 468             REG_NOTES (from_insn) = next_note;
 469         }
 470       else prev_note = note;
 471     }
 472 }
 473
 474
 475 /* Create a mov insn DEST_REG <- SRC_REG and insert it before
 476    NEXT_INSN.  */
 477
 478 static rtx
 479 insert_move_insn_before (rtx next_insn, rtx dest_reg, rtx src_reg)
 480 {
 481   rtx insns;
 482
 483   start_sequence ();
 484   emit_move_insn (dest_reg, src_reg);
 485   insns = get_insns ();
 486   end_sequence ();
 487   emit_insn_before (insns, next_insn);
 488   return insns;
 489 }
 490
 491
 492 /* Change mem_insn.mem_loc so that uses NEW_ADDR which has an
 493    increment of INC_REG.  To have reached this point, the change is a
 494    legitimate one from a dataflow point of view.  The only questions
 495    are is this a valid change to the instruction and is this a
 496    profitable change to the instruction.  */
 497
 498 static bool
 499 attempt_change (rtx new_addr, rtx inc_reg)
 500 {
 501   /* There are four cases: For the two cases that involve an add
 502      instruction, we are going to have to delete the add and insert a
 503      mov.  We are going to assume that the mov is free.  This is
 504      fairly early in the backend and there are a lot of opportunities
 505      for removing that move later.  In particular, there is the case
 506      where the move may be dead, this is what dead code elimination
 507      passes are for.  The two cases where we have an inc insn will be
 508      handled mov free.  */
 509
 510   basic_block bb = BASIC_BLOCK (BLOCK_NUM (mem_insn.insn));
 511   rtx mov_insn = NULL;
 512   int regno;
 513   rtx mem = *mem_insn.mem_loc;
 514   enum machine_mode mode = GET_MODE (mem);
 515   rtx new_mem;
 516   int old_cost = 0;
 517   int new_cost = 0;
 518
 519   PUT_MODE (mem_tmp, mode);
 520   XEXP (mem_tmp, 0) = new_addr;
 521
 522   old_cost = rtx_cost (mem, 0)
 523     + rtx_cost (PATTERN (inc_insn.insn), 0);
 524   new_cost = rtx_cost (mem_tmp, 0);
 525
 526   /* The first item of business is to see if this is profitable.  */
 527   if (old_cost < new_cost)
 528     {
 529       if (dump_file)
 530         fprintf (dump_file, "cost failure old=%d new=%d\n", old_cost, new_cost);
 531       return false;
 532     }
 533
 534   /* Jump thru a lot of hoops to keep the attributes up to date.  We
 535      do not want to call one of the change address variants that take
 536      an offset even though we know the offset in many cases.  These
 537      assume you are changing where the address is pointing by the
 538      offset.  */
 539   new_mem = replace_equiv_address_nv (mem, new_addr);
 540   if (! validate_change (mem_insn.insn, mem_insn.mem_loc, new_mem, 0))
 541     {
 542       if (dump_file)
 543         fprintf (dump_file, "validation failure\n");
 544       return false;
 545     }
 546
 547   /* From here to the end of the function we are committed to the
 548      change, i.e. nothing fails.  Generate any necessary movs, move
 549      any regnotes, and fix up the reg_next_{use,inc_use,def}.  */
 550   switch (inc_insn.form)
 551     {
 552     case FORM_PRE_ADD:
 553       /* Replace the addition with a move.  Do it at the location of
 554          the addition since the operand of the addition may change
 555          before the memory reference.  */
 556       mov_insn = insert_move_insn_before (inc_insn.insn,
 557                                           inc_insn.reg_res, inc_insn.reg0);
 558       move_dead_notes (mov_insn, inc_insn.insn, inc_insn.reg0);
 559
 560       regno = REGNO (inc_insn.reg_res);
 561       reg_next_def[regno] = mov_insn;
 562       reg_next_use[regno] = NULL;
 563       regno = REGNO (inc_insn.reg0);
 564       reg_next_use[regno] = mov_insn;
 565       df_recompute_luids (bb);
 566       break;
 567
 568     case FORM_POST_INC:
 569       regno = REGNO (inc_insn.reg_res);
 570       if (reg_next_use[regno] == reg_next_inc_use[regno])
 571         reg_next_inc_use[regno] = NULL;
 572
 573       /* Fallthru.  */
 574     case FORM_PRE_INC:
 575       regno = REGNO (inc_insn.reg_res);
 576       reg_next_def[regno] = mem_insn.insn;
 577       reg_next_use[regno] = NULL;
 578
 579       break;
 580
 581     case FORM_POST_ADD:
 582       mov_insn = insert_move_insn_before (mem_insn.insn,
 583                                           inc_insn.reg_res, inc_insn.reg0);
 584       move_dead_notes (mov_insn, inc_insn.insn, inc_insn.reg0);
 585
 586       /* Do not move anything to the mov insn because the instruction
 587          pointer for the main iteration has not yet hit that.  It is
 588          still pointing to the mem insn. */
 589       regno = REGNO (inc_insn.reg_res);
 590       reg_next_def[regno] = mem_insn.insn;
 591       reg_next_use[regno] = NULL;
 592
 593       regno = REGNO (inc_insn.reg0);
 594       reg_next_use[regno] = mem_insn.insn;
 595       if ((reg_next_use[regno] == reg_next_inc_use[regno])
 596           || (reg_next_inc_use[regno] == inc_insn.insn))
 597         reg_next_inc_use[regno] = NULL;
 598       df_recompute_luids (bb);
 599       break;
 600
 601     case FORM_last:
 602     default:
 603       gcc_unreachable ();
 604     }
 605
 606   if (!inc_insn.reg1_is_const)
 607     {
 608       regno = REGNO (inc_insn.reg1);
 609       reg_next_use[regno] = mem_insn.insn;
 610       if ((reg_next_use[regno] == reg_next_inc_use[regno])
 611           || (reg_next_inc_use[regno] == inc_insn.insn))
 612         reg_next_inc_use[regno] = NULL;
 613     }
 614
 615   delete_insn (inc_insn.insn);
 616
 617   if (dump_file && mov_insn)
 618     {
 619       fprintf (dump_file, "inserting mov ");
 620       dump_insn_slim (dump_file, mov_insn);
 621     }
 622
 623   /* Record that this insn has an implicit side effect.  */
 624   add_reg_note (mem_insn.insn, REG_INC, inc_reg);
 625
 626   if (dump_file)
 627     {
 628       fprintf (dump_file, "****success ");
 629       dump_insn_slim (dump_file, mem_insn.insn);
 630     }
 631
 632   return true;
 633 }
 634
 635
 636 /* Try to combine the instruction in INC_INSN with the instruction in
 637    MEM_INSN.  First the form is determined using the DECISION_TABLE
 638    and the results of parsing the INC_INSN and the MEM_INSN.
 639    Assuming the form is ok, a prototype new address is built which is
 640    passed to ATTEMPT_CHANGE for final processing.  */
 641
 642 static bool
 643 try_merge (void)
 644 {
 645   enum gen_form gen_form;
 646   rtx mem = *mem_insn.mem_loc;
 647   rtx inc_reg = inc_insn.form == FORM_POST_ADD ?
 648     inc_insn.reg_res : mem_insn.reg0;
 649
 650   /* The width of the mem being accessed.  */
 651   int size = GET_MODE_SIZE (GET_MODE (mem));
 652   rtx last_insn = NULL;
 653
 654   switch (inc_insn.form)
 655     {
 656     case FORM_PRE_ADD:
 657     case FORM_PRE_INC:
 658       last_insn = mem_insn.insn;
 659       break;
 660     case FORM_POST_INC:
 661     case FORM_POST_ADD:
 662       last_insn = inc_insn.insn;
 663       break;
 664     case FORM_last:
 665     default:
 666       gcc_unreachable ();
 667     }
 668
 669   /* Cannot handle auto inc of the stack.  */
 670   if (inc_reg == stack_pointer_rtx)
 671     {
 672       if (dump_file)
 673         fprintf (dump_file, "cannot inc stack %d failure\n", REGNO (inc_reg));
 674       return false;
 675     }
 676
 677   /* Look to see if the inc register is dead after the memory
 678      reference.  If it is, do not do the combination.  */
 679   if (find_regno_note (last_insn, REG_DEAD, REGNO (inc_reg)))
 680     {
 681       if (dump_file)
 682         fprintf (dump_file, "dead failure %d\n", REGNO (inc_reg));
 683       return false;
 684     }
 685
 686   mem_insn.reg1_state = (mem_insn.reg1_is_const)
 687     ? set_inc_state (mem_insn.reg1_val, size) : INC_REG;
 688   inc_insn.reg1_state = (inc_insn.reg1_is_const)
 689     ? set_inc_state (inc_insn.reg1_val, size) : INC_REG;
 690
 691   /* Now get the form that we are generating.  */
 692   gen_form = decision_table
 693     [inc_insn.reg1_state][mem_insn.reg1_state][inc_insn.form];
 694
 695   if (dbg_cnt (auto_inc_dec) == false)
 696     return false;
 697
 698   switch (gen_form)
 699     {
 700     default:
 701     case NOTHING:
 702       return false;
 703
 704     case SIMPLE_PRE_INC:     /* ++size  */
 705       if (dump_file)
 706         fprintf (dump_file, "trying SIMPLE_PRE_INC\n");
 707       return attempt_change (gen_rtx_PRE_INC (Pmode, inc_reg), inc_reg);
 708       break;
 709
 710     case SIMPLE_POST_INC:    /* size++  */
 711       if (dump_file)
 712         fprintf (dump_file, "trying SIMPLE_POST_INC\n");
 713       return attempt_change (gen_rtx_POST_INC (Pmode, inc_reg), inc_reg);
 714       break;
 715
 716     case SIMPLE_PRE_DEC:     /* --size  */
 717       if (dump_file)
 718         fprintf (dump_file, "trying SIMPLE_PRE_DEC\n");
 719       return attempt_change (gen_rtx_PRE_DEC (Pmode, inc_reg), inc_reg);
 720       break;
 721
 722     case SIMPLE_POST_DEC:    /* size--  */
 723       if (dump_file)
 724         fprintf (dump_file, "trying SIMPLE_POST_DEC\n");
 725       return attempt_change (gen_rtx_POST_DEC (Pmode, inc_reg), inc_reg);
 726       break;
 727
 728     case DISP_PRE:           /* ++con   */
 729       if (dump_file)
 730         fprintf (dump_file, "trying DISP_PRE\n");
 731       return attempt_change (gen_rtx_PRE_MODIFY (Pmode,
 732                                                  inc_reg,
 733                                                  gen_rtx_PLUS (Pmode,
 734                                                                inc_reg,
 735                                                                inc_insn.reg1)),
 736                              inc_reg);
 737       break;
 738
 739     case DISP_POST:          /* con++   */
 740       if (dump_file)
 741         fprintf (dump_file, "trying POST_DISP\n");
 742       return attempt_change (gen_rtx_POST_MODIFY (Pmode,
 743                                                   inc_reg,
 744                                                   gen_rtx_PLUS (Pmode,
 745                                                                 inc_reg,
 746                                                                 inc_insn.reg1)),
 747                              inc_reg);
 748       break;
 749
 750     case REG_PRE:            /* ++reg   */
 751       if (dump_file)
 752         fprintf (dump_file, "trying PRE_REG\n");
 753       return attempt_change (gen_rtx_PRE_MODIFY (Pmode,
 754                                                  inc_reg,
 755                                                  gen_rtx_PLUS (Pmode,
 756                                                                inc_reg,
 757                                                                inc_insn.reg1)),
 758                              inc_reg);
 759       break;
 760
 761     case REG_POST:            /* reg++   */
 762       if (dump_file)
 763         fprintf (dump_file, "trying POST_REG\n");
 764       return attempt_change (gen_rtx_POST_MODIFY (Pmode,
 765                                                   inc_reg,
 766                                                   gen_rtx_PLUS (Pmode,
 767                                                                 inc_reg,
 768                                                                 inc_insn.reg1)),
 769                              inc_reg);
 770       break;
 771     }
 772 }
 773
 774 /* Return the next insn that uses (if reg_next_use is passed in
 775    NEXT_ARRAY) or defines (if reg_next_def is passed in NEXT_ARRAY)
 776    REGNO in BB.  */
 777
 778 static rtx
 779 get_next_ref (int regno, basic_block bb, rtx *next_array)
 780 {
 781   rtx insn = next_array[regno];
 782
 783   /* Lazy about cleaning out the next_arrays.  */
 784   if (insn && BASIC_BLOCK (BLOCK_NUM (insn)) != bb)
 785     {
 786       next_array[regno] = NULL;
 787       insn = NULL;
 788     }
 789
 790   return insn;
 791 }
 792
 793
 794 /* Reverse the operands in a mem insn.  */
 795
 796 static void
 797 reverse_mem (void)
 798 {
 799   rtx tmp = mem_insn.reg1;
 800   mem_insn.reg1 = mem_insn.reg0;
 801   mem_insn.reg0 = tmp;
 802 }
 803
 804
 805 /* Reverse the operands in a inc insn.  */
 806
 807 static void
 808 reverse_inc (void)
 809 {
 810   rtx tmp = inc_insn.reg1;
 811   inc_insn.reg1 = inc_insn.reg0;
 812   inc_insn.reg0 = tmp;
 813 }
 814
 815
 816 /* Return true if INSN is of a form "a = b op c" where a and b are
 817    regs.  op is + if c is a reg and +|- if c is a const.  Fill in
 818    INC_INSN with what is found.
 819
 820    This function is called in two contexts, if BEFORE_MEM is true,
 821    this is called for each insn in the basic block.  If BEFORE_MEM is
 822    false, it is called for the instruction in the block that uses the
 823    index register for some memory reference that is currently being
 824    processed.  */
 825
 826 static bool
 827 parse_add_or_inc (rtx insn, bool before_mem)
 828 {
 829   rtx pat = single_set (insn);
 830   if (!pat)
 831     return false;
 832
 833   /* Result must be single reg.  */
 834   if (!REG_P (SET_DEST (pat)))
 835     return false;
 836
 837   if ((GET_CODE (SET_SRC (pat)) != PLUS)
 838       && (GET_CODE (SET_SRC (pat)) != MINUS))
 839     return false;
 840
 841   if (!REG_P (XEXP (SET_SRC (pat), 0)))
 842     return false;
 843
 844   inc_insn.insn = insn;
 845   inc_insn.pat = pat;
 846   inc_insn.reg_res = SET_DEST (pat);
 847   inc_insn.reg0 = XEXP (SET_SRC (pat), 0);
 848   if (rtx_equal_p (inc_insn.reg_res, inc_insn.reg0))
 849     inc_insn.form = before_mem ? FORM_PRE_INC : FORM_POST_INC;
 850   else
 851     inc_insn.form = before_mem ? FORM_PRE_ADD : FORM_POST_ADD;
 852
 853   if (GET_CODE (XEXP (SET_SRC (pat), 1)) == CONST_INT)
 854     {
 855       /* Process a = b + c where c is a const.  */
 856       inc_insn.reg1_is_const = true;
 857       if (GET_CODE (SET_SRC (pat)) == PLUS)
 858         {
 859           inc_insn.reg1 = XEXP (SET_SRC (pat), 1);
 860           inc_insn.reg1_val = INTVAL (inc_insn.reg1);
 861         }
 862       else
 863         {
 864           inc_insn.reg1_val = -INTVAL (XEXP (SET_SRC (pat), 1));
 865           inc_insn.reg1 = GEN_INT (inc_insn.reg1_val);
 866         }
 867       return true;
 868     }
 869   else if ((HAVE_PRE_MODIFY_REG || HAVE_POST_MODIFY_REG)
 870            && (REG_P (XEXP (SET_SRC (pat), 1)))
 871            && GET_CODE (SET_SRC (pat)) == PLUS)
 872     {
 873       /* Process a = b + c where c is a reg.  */
 874       inc_insn.reg1 = XEXP (SET_SRC (pat), 1);
 875       inc_insn.reg1_is_const = false;
 876
 877       if (inc_insn.form == FORM_PRE_INC
 878           || inc_insn.form == FORM_POST_INC)
 879         return true;
 880       else if (rtx_equal_p (inc_insn.reg_res, inc_insn.reg1))
 881         {
 882           /* Reverse the two operands and turn *_ADD into *_INC since
 883              a = c + a.  */
 884           reverse_inc ();
 885           inc_insn.form = before_mem ? FORM_PRE_INC : FORM_POST_INC;
 886           return true;
 887         }
 888       else
 889         return true;
 890     }
 891
 892   return false;
 893 }
 894
 895
 896 /* A recursive function that checks all of the mem uses in
 897    ADDRESS_OF_X to see if any single one of them is compatible with
 898    what has been found in inc_insn.
 899
 900    -1 is returned for success.  0 is returned if nothing was found and
 901    1 is returned for failure. */
 902
 903 static int
 904 find_address (rtx *address_of_x)
 905 {
 906   rtx x = *address_of_x;
 907   enum rtx_code code = GET_CODE (x);
 908   const char *const fmt = GET_RTX_FORMAT (code);
 909   int i;
 910   int value = 0;
 911   int tem;
 912
 913   if (code == MEM && rtx_equal_p (XEXP (x, 0), inc_insn.reg_res))
 914     {
 915       /* Match with *reg0.  */
 916       mem_insn.mem_loc = address_of_x;
 917       mem_insn.reg0 = inc_insn.reg_res;
 918       mem_insn.reg1_is_const = true;
 919       mem_insn.reg1_val = 0;
 920       mem_insn.reg1 = GEN_INT (0);
 921       return -1;
 922     }
 923   if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
 924       && rtx_equal_p (XEXP (XEXP (x, 0), 0), inc_insn.reg_res))
 925     {
 926       rtx b = XEXP (XEXP (x, 0), 1);
 927       mem_insn.mem_loc = address_of_x;
 928       mem_insn.reg0 = inc_insn.reg_res;
 929       mem_insn.reg1 = b;
 930       mem_insn.reg1_is_const = inc_insn.reg1_is_const;
 931       if (GET_CODE (b) == CONST_INT)
 932         {
 933           /* Match with *(reg0 + reg1) where reg1 is a const. */
 934           HOST_WIDE_INT val = INTVAL (b);
 935           if (inc_insn.reg1_is_const
 936               && (inc_insn.reg1_val == val || inc_insn.reg1_val == -val))
 937             {
 938               mem_insn.reg1_val = val;
 939               return -1;
 940             }
 941         }
 942       else if (!inc_insn.reg1_is_const
 943                && rtx_equal_p (inc_insn.reg1, b))
 944         /* Match with *(reg0 + reg1). */
 945         return -1;
 946     }
 947
 948   if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
 949     {
 950       /* If REG occurs inside a MEM used in a bit-field reference,
 951          that is unacceptable.  */
 952       if (find_address (&XEXP (x, 0)))
 953         return 1;
 954     }
 955
 956   if (x == inc_insn.reg_res)
 957     return 1;
 958
 959   /* Time for some deep diving.  */
 960   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 961     {
 962       if (fmt[i] == 'e')
 963         {
 964           tem = find_address (&XEXP (x, i));
 965           /* If this is the first use, let it go so the rest of the
 966              insn can be checked.  */
 967           if (value == 0)
 968             value = tem;
 969           else if (tem != 0)
 970             /* More than one match was found.  */
 971             return 1;
 972         }
 973       else if (fmt[i] == 'E')
 974         {
 975           int j;
 976           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 977             {
 978               tem = find_address (&XVECEXP (x, i, j));
 979               /* If this is the first use, let it go so the rest of
 980                  the insn can be checked.  */
 981               if (value == 0)
 982                 value = tem;
 983               else if (tem != 0)
 984                 /* More than one match was found.  */
 985                 return 1;
 986             }
 987         }
 988     }
 989   return value;
 990 }
 991
 992 /* Once a suitable mem reference has been found and the MEM_INSN
 993    structure has been filled in, FIND_INC is called to see if there is
 994    a suitable add or inc insn that follows the mem reference and
 995    determine if it is suitable to merge.
 996
 997    In the case where the MEM_INSN has two registers in the reference,
 998    this function may be called recursively.  The first time looking
 999    for an add of the first register, and if that fails, looking for an
1000    add of the second register.  The FIRST_TRY parameter is used to
1001    only allow the parameters to be reversed once.  */
1002
1003 static bool
1004 find_inc (bool first_try)
1005 {
1006   rtx insn;
1007   basic_block bb = BASIC_BLOCK (BLOCK_NUM (mem_insn.insn));
1008   rtx other_insn;
1009   struct df_ref **def_rec;
1010
1011   /* Make sure this reg appears only once in this insn.  */
1012   if (count_occurrences (PATTERN (mem_insn.insn), mem_insn.reg0, 1) != 1)
1013     {
1014       if (dump_file)
1015         fprintf (dump_file, "mem count failure\n");
1016       return false;
1017     }
1018
1019   if (dump_file)
1020     dump_mem_insn (dump_file);
1021
1022   /* Find the next use that is an inc.  */
1023   insn = get_next_ref (REGNO (mem_insn.reg0),
1024                        BASIC_BLOCK (BLOCK_NUM (mem_insn.insn)),
1025                        reg_next_inc_use);
1026   if (!insn)
1027     return false;
1028
1029   /* Even though we know the next use is an add or inc because it came
1030      from the reg_next_inc_use, we must still reparse.  */
1031   if (!parse_add_or_inc (insn, false))
1032     {
1033       /* Next use was not an add.  Look for one extra case. It could be
1034          that we have:
1035
1036          *(a + b)
1037          ...= a;
1038          ...= b + a
1039
1040          if we reverse the operands in the mem ref we would
1041          find this.  Only try it once though.  */
1042       if (first_try && !mem_insn.reg1_is_const)
1043         {
1044           reverse_mem ();
1045           return find_inc (false);
1046         }
1047       else
1048         return false;
1049     }
1050
1051   /* Need to assure that none of the operands of the inc instruction are
1052      assigned to by the mem insn.  */
1053   for (def_rec = DF_INSN_DEFS (mem_insn.insn); *def_rec; def_rec++)
1054     {
1055       struct df_ref *def = *def_rec;
1056       unsigned int regno = DF_REF_REGNO (def);
1057       if ((regno == REGNO (inc_insn.reg0))
1058           || (regno == REGNO (inc_insn.reg_res)))
1059         {
1060           if (dump_file)
1061             fprintf (dump_file, "inc conflicts with store failure.\n");
1062           return false;
1063         }
1064       if (!inc_insn.reg1_is_const && (regno == REGNO (inc_insn.reg1)))
1065         {
1066           if (dump_file)
1067             fprintf (dump_file, "inc conflicts with store failure.\n");
1068           return false;
1069         }
1070     }
1071
1072   if (dump_file)
1073     dump_inc_insn (dump_file);
1074
1075   if (inc_insn.form == FORM_POST_ADD)
1076     {
1077       /* Make sure that there is no insn that assigns to inc_insn.res
1078          between the mem_insn and the inc_insn.  */
1079       rtx other_insn = get_next_ref (REGNO (inc_insn.reg_res),
1080                                      BASIC_BLOCK (BLOCK_NUM (mem_insn.insn)),
1081                                      reg_next_def);
1082       if (other_insn != inc_insn.insn)
1083         {
1084           if (dump_file)
1085             fprintf (dump_file,
1086                      "result of add is assigned to between mem and inc insns.\n");
1087           return false;
1088         }
1089
1090       other_insn = get_next_ref (REGNO (inc_insn.reg_res),
1091                                  BASIC_BLOCK (BLOCK_NUM (mem_insn.insn)),
1092                                  reg_next_use);
1093       if (other_insn
1094           && (other_insn != inc_insn.insn)
1095           && (DF_INSN_LUID (inc_insn.insn) > DF_INSN_LUID (other_insn)))
1096         {
1097           if (dump_file)
1098             fprintf (dump_file,
1099                      "result of add is used between mem and inc insns.\n");
1100           return false;
1101         }
1102
1103       /* For the post_add to work, the result_reg of the inc must not be
1104          used in the mem insn since this will become the new index
1105          register.  */
1106       if (count_occurrences (PATTERN (mem_insn.insn), inc_insn.reg_res, 1) != 0)
1107         {
1108           if (dump_file)
1109             fprintf (dump_file, "base reg replacement failure.\n");
1110           return false;
1111         }
1112     }
1113
1114   if (mem_insn.reg1_is_const)
1115     {
1116       if (mem_insn.reg1_val == 0)
1117         {
1118           if (!inc_insn.reg1_is_const)
1119             {
1120               /* The mem looks like *r0 and the rhs of the add has two
1121                  registers.  */
1122               int luid = DF_INSN_LUID (inc_insn.insn);
1123               if (inc_insn.form == FORM_POST_ADD)
1124                 {
1125                   /* The trick is that we are not going to increment r0,
1126                      we are going to increment the result of the add insn.
1127                      For this trick to be correct, the result reg of
1128                      the inc must be a valid addressing reg.  */
1129                   if (GET_MODE (inc_insn.reg_res) != Pmode)
1130                     {
1131                       if (dump_file)
1132                         fprintf (dump_file, "base reg mode failure.\n");
1133                       return false;
1134                     }
1135
1136                   /* We also need to make sure that the next use of
1137                      inc result is after the inc.  */
1138                   other_insn
1139                     = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_use);
1140                   if (other_insn && luid > DF_INSN_LUID (other_insn))
1141                     return false;
1142
1143                   if (!rtx_equal_p (mem_insn.reg0, inc_insn.reg0))
1144                     reverse_inc ();
1145                 }
1146
1147               other_insn
1148                 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1149               if (other_insn && luid > DF_INSN_LUID (other_insn))
1150                 return false;
1151             }
1152         }
1153       /* Both the inc/add and the mem have a constant.  Need to check
1154          that the constants are ok. */
1155       else if ((mem_insn.reg1_val != inc_insn.reg1_val)
1156                && (mem_insn.reg1_val != -inc_insn.reg1_val))
1157         return false;
1158     }
1159   else
1160     {
1161       /* The mem insn is of the form *(a + b) where a and b are both
1162          regs.  It may be that in order to match the add or inc we
1163          need to treat it as if it was *(b + a).  It may also be that
1164          the add is of the form a + c where c does not match b and
1165          then we just abandon this.  */
1166
1167       int luid = DF_INSN_LUID (inc_insn.insn);
1168       rtx other_insn;
1169
1170       /* Make sure this reg appears only once in this insn.  */
1171       if (count_occurrences (PATTERN (mem_insn.insn), mem_insn.reg1, 1) != 1)
1172         return false;
1173
1174       if (inc_insn.form == FORM_POST_ADD)
1175         {
1176           /* For this trick to be correct, the result reg of the inc
1177              must be a valid addressing reg.  */
1178           if (GET_MODE (inc_insn.reg_res) != Pmode)
1179             {
1180               if (dump_file)
1181                 fprintf (dump_file, "base reg mode failure.\n");
1182               return false;
1183             }
1184
1185           if (rtx_equal_p (mem_insn.reg0, inc_insn.reg0))
1186             {
1187               if (!rtx_equal_p (mem_insn.reg1, inc_insn.reg1))
1188                 {
1189                   /* See comment above on find_inc (false) call.  */
1190                   if (first_try)
1191                     {
1192                       reverse_mem ();
1193                       return find_inc (false);
1194                     }
1195                   else
1196                     return false;
1197                 }
1198
1199               /* Need to check that there are no assignments to b
1200                  before the add insn.  */
1201               other_insn
1202                 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1203               if (other_insn && luid > DF_INSN_LUID (other_insn))
1204                 return false;
1205               /* All ok for the next step.  */
1206             }
1207           else
1208             {
1209               /* We know that mem_insn.reg0 must equal inc_insn.reg1
1210                  or else we would not have found the inc insn.  */
1211               reverse_mem ();
1212               if (!rtx_equal_p (mem_insn.reg0, inc_insn.reg0))
1213                 {
1214                   /* See comment above on find_inc (false) call.  */
1215                   if (first_try)
1216                     return find_inc (false);
1217                   else
1218                     return false;
1219                 }
1220               /* To have gotten here know that.
1221                *(b + a)
1222
1223                ... = (b + a)
1224
1225                We also know that the lhs of the inc is not b or a.  We
1226                need to make sure that there are no assignments to b
1227                between the mem ref and the inc.  */
1228
1229               other_insn
1230                 = get_next_ref (REGNO (inc_insn.reg0), bb, reg_next_def);
1231               if (other_insn && luid > DF_INSN_LUID (other_insn))
1232                 return false;
1233             }
1234
1235           /* Need to check that the next use of the add result is later than
1236              add insn since this will be the reg incremented.  */
1237           other_insn
1238             = get_next_ref (REGNO (inc_insn.reg_res), bb, reg_next_use);
1239           if (other_insn && luid > DF_INSN_LUID (other_insn))
1240             return false;
1241         }
1242       else /* FORM_POST_INC.  There is less to check here because we
1243               know that operands must line up.  */
1244         {
1245           if (!rtx_equal_p (mem_insn.reg1, inc_insn.reg1))
1246             /* See comment above on find_inc (false) call.  */
1247             {
1248               if (first_try)
1249                 {
1250                   reverse_mem ();
1251                   return find_inc (false);
1252                 }
1253               else
1254                 return false;
1255             }
1256
1257           /* To have gotten here know that.
1258            *(a + b)
1259
1260            ... = (a + b)
1261
1262            We also know that the lhs of the inc is not b.  We need to make
1263            sure that there are no assignments to b between the mem ref and
1264            the inc.  */
1265           other_insn
1266             = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1267           if (other_insn && luid > DF_INSN_LUID (other_insn))
1268             return false;
1269         }
1270     }
1271
1272   if (inc_insn.form == FORM_POST_INC)
1273     {
1274       other_insn
1275         = get_next_ref (REGNO (inc_insn.reg0), bb, reg_next_use);
1276       /* When we found inc_insn, we were looking for the
1277          next add or inc, not the next insn that used the
1278          reg.  Because we are going to increment the reg
1279          in this form, we need to make sure that there
1280          were no intervening uses of reg.  */
1281       if (inc_insn.insn != other_insn)
1282         return false;
1283     }
1284
1285   return try_merge ();
1286 }
1287
1288
1289 /* A recursive function that walks ADDRESS_OF_X to find all of the mem
1290    uses in pat that could be used as an auto inc or dec.  It then
1291    calls FIND_INC for each one.  */
1292
1293 static bool
1294 find_mem (rtx *address_of_x)
1295 {
1296   rtx x = *address_of_x;
1297   enum rtx_code code = GET_CODE (x);
1298   const char *const fmt = GET_RTX_FORMAT (code);
1299   int i;
1300
1301   if (code == MEM && REG_P (XEXP (x, 0)))
1302     {
1303       /* Match with *reg0.  */
1304       mem_insn.mem_loc = address_of_x;
1305       mem_insn.reg0 = XEXP (x, 0);
1306       mem_insn.reg1_is_const = true;
1307       mem_insn.reg1_val = 0;
1308       mem_insn.reg1 = GEN_INT (0);
1309       if (find_inc (true))
1310         return true;
1311     }
1312   if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
1313       && REG_P (XEXP (XEXP (x, 0), 0)))
1314     {
1315       rtx reg1 = XEXP (XEXP (x, 0), 1);
1316       mem_insn.mem_loc = address_of_x;
1317       mem_insn.reg0 = XEXP (XEXP (x, 0), 0);
1318       mem_insn.reg1 = reg1;
1319       if (GET_CODE (reg1) == CONST_INT)
1320         {
1321           mem_insn.reg1_is_const = true;
1322           /* Match with *(reg0 + c) where c is a const. */
1323           mem_insn.reg1_val = INTVAL (reg1);
1324           if (find_inc (true))
1325             return true;
1326         }
1327       else if (REG_P (reg1))
1328         {
1329           /* Match with *(reg0 + reg1).  */
1330           mem_insn.reg1_is_const = false;
1331           if (find_inc (true))
1332             return true;
1333         }
1334     }
1335
1336   if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
1337     {
1338       /* If REG occurs inside a MEM used in a bit-field reference,
1339          that is unacceptable.  */
1340       return false;
1341     }
1342
1343   /* Time for some deep diving.  */
1344   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1345     {
1346       if (fmt[i] == 'e')
1347         {
1348           if (find_mem (&XEXP (x, i)))
1349             return true;
1350         }
1351       else if (fmt[i] == 'E')
1352         {
1353           int j;
1354           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1355             if (find_mem (&XVECEXP (x, i, j)))
1356               return true;
1357         }
1358     }
1359   return false;
1360 }
1361
1362
1363 /* Try to combine all incs and decs by constant values with memory
1364    references in BB.  */
1365
1366 static void
1367 merge_in_block (int max_reg, basic_block bb)
1368 {
1369   rtx insn;
1370   rtx curr;
1371   int success_in_block = 0;
1372
1373   if (dump_file)
1374     fprintf (dump_file, "\n\nstarting bb %d\n", bb->index);
1375
1376   FOR_BB_INSNS_REVERSE_SAFE (bb, insn, curr)
1377     {
1378       unsigned int uid = INSN_UID (insn);
1379       bool insn_is_add_or_inc = true;
1380
1381       if (!INSN_P (insn))
1382         continue;
1383
1384       /* This continue is deliberate.  We do not want the uses of the
1385          jump put into reg_next_use because it is not considered safe to
1386          combine a preincrement with a jump.  */
1387       if (JUMP_P (insn))
1388         continue;
1389
1390       if (dump_file)
1391         dump_insn_slim (dump_file, insn);
1392
1393       /* Does this instruction increment or decrement a register?  */
1394       if (parse_add_or_inc (insn, true))
1395         {
1396           int regno = REGNO (inc_insn.reg_res);
1397           /* Cannot handle case where there are three separate regs
1398              before a mem ref.  Too many moves would be needed to be
1399              profitable.  */
1400           if ((inc_insn.form == FORM_PRE_INC) || inc_insn.reg1_is_const)
1401             {
1402               mem_insn.insn = get_next_ref (regno, bb, reg_next_use);
1403               if (mem_insn.insn)
1404                 {
1405                   bool ok = true;
1406                   if (!inc_insn.reg1_is_const)
1407                     {
1408                       /* We are only here if we are going to try a
1409                          HAVE_*_MODIFY_REG type transformation.  c is a
1410                          reg and we must sure that the path from the
1411                          inc_insn to the mem_insn.insn is both def and use
1412                          clear of c because the inc insn is going to move
1413                          into the mem_insn.insn.  */
1414                       int luid = DF_INSN_LUID (mem_insn.insn);
1415                       rtx other_insn
1416                         = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_use);
1417
1418                       if (other_insn && luid > DF_INSN_LUID (other_insn))
1419                         ok = false;
1420
1421                       other_insn
1422                         = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1423
1424                       if (other_insn && luid > DF_INSN_LUID (other_insn))
1425                         ok = false;
1426                     }
1427
1428                   if (dump_file)
1429                     dump_inc_insn (dump_file);
1430
1431                   if (ok && find_address (&PATTERN (mem_insn.insn)) == -1)
1432                     {
1433                       if (dump_file)
1434                         dump_mem_insn (dump_file);
1435                       if (try_merge ())
1436                         {
1437                           success_in_block++;
1438                           insn_is_add_or_inc = false;
1439                         }
1440                     }
1441                 }
1442             }
1443         }
1444       else
1445         {
1446           insn_is_add_or_inc = false;
1447           mem_insn.insn = insn;
1448           if (find_mem (&PATTERN (insn)))
1449             success_in_block++;
1450         }
1451
1452       /* If the inc insn was merged with a mem, the inc insn is gone
1453          and there is noting to update.  */
1454       if (DF_INSN_UID_GET(uid))
1455         {
1456           struct df_ref **def_rec;
1457           struct df_ref **use_rec;
1458           /* Need to update next use.  */
1459           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1460             {
1461               struct df_ref *def = *def_rec;
1462               reg_next_use[DF_REF_REGNO (def)] = NULL;
1463               reg_next_inc_use[DF_REF_REGNO (def)] = NULL;
1464               reg_next_def[DF_REF_REGNO (def)] = insn;
1465             }
1466
1467           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1468             {
1469               struct df_ref *use = *use_rec;
1470               reg_next_use[DF_REF_REGNO (use)] = insn;
1471               if (insn_is_add_or_inc)
1472                 reg_next_inc_use[DF_REF_REGNO (use)] = insn;
1473               else
1474                 reg_next_inc_use[DF_REF_REGNO (use)] = NULL;
1475             }
1476         }
1477       else if (dump_file)
1478         fprintf (dump_file, "skipping update of deleted insn %d\n", uid);
1479     }
1480
1481   /* If we were successful, try again.  There may have been several
1482      opportunities that were interleaved.  This is rare but
1483      gcc.c-torture/compile/pr17273.c actually exhibits this.  */
1484   if (success_in_block)
1485     {
1486       /* In this case, we must clear these vectors since the trick of
1487          testing if the stale insn in the block will not work.  */
1488       memset (reg_next_use, 0, max_reg * sizeof(rtx));
1489       memset (reg_next_inc_use, 0, max_reg * sizeof(rtx));
1490       memset (reg_next_def, 0, max_reg * sizeof(rtx));
1491       df_recompute_luids (bb);
1492       merge_in_block (max_reg, bb);
1493     }
1494 }
1495
1496 #endif
1497
1498 static unsigned int
1499 rest_of_handle_auto_inc_dec (void)
1500 {
1501 #ifdef AUTO_INC_DEC
1502   basic_block bb;
1503   int max_reg = max_reg_num ();
1504
1505   if (!initialized)
1506     init_decision_table ();
1507
1508   mem_tmp = gen_rtx_MEM (Pmode, NULL_RTX);
1509
1510   df_note_add_problem ();
1511   df_analyze ();
1512
1513   reg_next_use = XCNEWVEC (rtx, max_reg);
1514   reg_next_inc_use = XCNEWVEC (rtx, max_reg);
1515   reg_next_def = XCNEWVEC (rtx, max_reg);
1516   FOR_EACH_BB (bb)
1517     merge_in_block (max_reg, bb);
1518
1519   free (reg_next_use);
1520   free (reg_next_inc_use);
1521   free (reg_next_def);
1522
1523   mem_tmp = NULL;
1524 #endif
1525   return 0;
1526 }
1527
1528
1529 /* Discover auto-inc auto-dec instructions.  */
1530
1531 static bool
1532 gate_auto_inc_dec (void)
1533 {
1534 #ifdef AUTO_INC_DEC
1535   return (optimize > 0 && flag_auto_inc_dec);
1536 #else
1537   return false;
1538 #endif
1539 }
1540
1541
1542 struct rtl_opt_pass pass_inc_dec =
1543 {
1544  {
1545   RTL_PASS,
1546   "auto-inc-dec",                       /* name */
1547   gate_auto_inc_dec,                    /* gate */
1548   rest_of_handle_auto_inc_dec,          /* execute */
1549   NULL,                                 /* sub */
1550   NULL,                                 /* next */
1551   0,                                    /* static_pass_number */
1552   TV_AUTO_INC_DEC,                      /* tv_id */
1553   0,                                    /* properties_required */
1554   0,                                    /* properties_provided */
1555   0,                                    /* properties_destroyed */
1556   0,                                    /* todo_flags_start */
1557   TODO_dump_func |
1558   TODO_df_finish,                       /* todo_flags_finish */
1559  }
1560 };
1561