gcc/auto-inc-dec.c

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