gcc/auto-inc-dec.c

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