gcc/auto-inc-dec.c

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