gcc/auto-inc-dec.c

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