contrib/gcc-4.4/gcc/auto-inc-dec.c

   1 /* Discovery of auto-inc and auto-dec instructions.
   2    Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
   3    Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "insn-config.h"
  31 #include "regs.h"
  32 #include "flags.h"
  33 #include "output.h"
  34 #include "function.h"
  35 #include "except.h"
  36 #include "toplev.h"
  37 #include "recog.h"
  38 #include "expr.h"
  39 #include "timevar.h"
  40 #include "tree-pass.h"
  41 #include "df.h"
  42 #include "dbgcnt.h"
  43
  44 /* This pass was originally removed from flow.c. However there is
  45    almost nothing that remains of that code.
  46
  47    There are (4) basic forms that are matched:
  48
  49            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   bool speed = optimize_bb_for_speed_p (bb);
 519
 520   PUT_MODE (mem_tmp, mode);
 521   XEXP (mem_tmp, 0) = new_addr;
 522
 523   old_cost = rtx_cost (mem, 0, speed)
 524     + rtx_cost (PATTERN (inc_insn.insn), 0, speed);
 525   new_cost = rtx_cost (mem_tmp, 0, speed);
 526
 527   /* The first item of business is to see if this is profitable.  */
 528   if (old_cost < new_cost)
 529     {
 530       if (dump_file)
 531         fprintf (dump_file, "cost failure old=%d new=%d\n", old_cost, new_cost);
 532       return false;
 533     }
 534
 535   /* Jump thru a lot of hoops to keep the attributes up to date.  We
 536      do not want to call one of the change address variants that take
 537      an offset even though we know the offset in many cases.  These
 538      assume you are changing where the address is pointing by the
 539      offset.  */
 540   new_mem = replace_equiv_address_nv (mem, new_addr);
 541   if (! validate_change (mem_insn.insn, mem_insn.mem_loc, new_mem, 0))
 542     {
 543       if (dump_file)
 544         fprintf (dump_file, "validation failure\n");
 545       return false;
 546     }
 547
 548   /* From here to the end of the function we are committed to the
 549      change, i.e. nothing fails.  Generate any necessary movs, move
 550      any regnotes, and fix up the reg_next_{use,inc_use,def}.  */
 551   switch (inc_insn.form)
 552     {
 553     case FORM_PRE_ADD:
 554       /* Replace the addition with a move.  Do it at the location of
 555          the addition since the operand of the addition may change
 556          before the memory reference.  */
 557       mov_insn = insert_move_insn_before (inc_insn.insn,
 558                                           inc_insn.reg_res, inc_insn.reg0);
 559       move_dead_notes (mov_insn, inc_insn.insn, inc_insn.reg0);
 560
 561       regno = REGNO (inc_insn.reg_res);
 562       reg_next_def[regno] = mov_insn;
 563       reg_next_use[regno] = NULL;
 564       regno = REGNO (inc_insn.reg0);
 565       reg_next_use[regno] = mov_insn;
 566       df_recompute_luids (bb);
 567       break;
 568
 569     case FORM_POST_INC:
 570       regno = REGNO (inc_insn.reg_res);
 571       if (reg_next_use[regno] == reg_next_inc_use[regno])
 572         reg_next_inc_use[regno] = NULL;
 573
 574       /* Fallthru.  */
 575     case FORM_PRE_INC:
 576       regno = REGNO (inc_insn.reg_res);
 577       reg_next_def[regno] = mem_insn.insn;
 578       reg_next_use[regno] = NULL;
 579
 580       break;
 581
 582     case FORM_POST_ADD:
 583       mov_insn = insert_move_insn_before (mem_insn.insn,
 584                                           inc_insn.reg_res, inc_insn.reg0);
 585       move_dead_notes (mov_insn, inc_insn.insn, inc_insn.reg0);
 586
 587       /* Do not move anything to the mov insn because the instruction
 588          pointer for the main iteration has not yet hit that.  It is
 589          still pointing to the mem insn. */
 590       regno = REGNO (inc_insn.reg_res);
 591       reg_next_def[regno] = mem_insn.insn;
 592       reg_next_use[regno] = NULL;
 593
 594       regno = REGNO (inc_insn.reg0);
 595       reg_next_use[regno] = mem_insn.insn;
 596       if ((reg_next_use[regno] == reg_next_inc_use[regno])
 597           || (reg_next_inc_use[regno] == inc_insn.insn))
 598         reg_next_inc_use[regno] = NULL;
 599       df_recompute_luids (bb);
 600       break;
 601
 602     case FORM_last:
 603     default:
 604       gcc_unreachable ();
 605     }
 606
 607   if (!inc_insn.reg1_is_const)
 608     {
 609       regno = REGNO (inc_insn.reg1);
 610       reg_next_use[regno] = mem_insn.insn;
 611       if ((reg_next_use[regno] == reg_next_inc_use[regno])
 612           || (reg_next_inc_use[regno] == inc_insn.insn))
 613         reg_next_inc_use[regno] = NULL;
 614     }
 615
 616   delete_insn (inc_insn.insn);
 617
 618   if (dump_file && mov_insn)
 619     {
 620       fprintf (dump_file, "inserting mov ");
 621       dump_insn_slim (dump_file, mov_insn);
 622     }
 623
 624   /* Record that this insn has an implicit side effect.  */
 625   add_reg_note (mem_insn.insn, REG_INC, inc_reg);
 626
 627   if (dump_file)
 628     {
 629       fprintf (dump_file, "****success ");
 630       dump_insn_slim (dump_file, mem_insn.insn);
 631     }
 632
 633   return true;
 634 }
 635
 636
 637 /* Try to combine the instruction in INC_INSN with the instruction in
 638    MEM_INSN.  First the form is determined using the DECISION_TABLE
 639    and the results of parsing the INC_INSN and the MEM_INSN.
 640    Assuming the form is ok, a prototype new address is built which is
 641    passed to ATTEMPT_CHANGE for final processing.  */
 642
 643 static bool
 644 try_merge (void)
 645 {
 646   enum gen_form gen_form;
 647   rtx mem = *mem_insn.mem_loc;
 648   rtx inc_reg = inc_insn.form == FORM_POST_ADD ?
 649     inc_insn.reg_res : mem_insn.reg0;
 650
 651   /* The width of the mem being accessed.  */
 652   int size = GET_MODE_SIZE (GET_MODE (mem));
 653   rtx last_insn = NULL;
 654
 655   switch (inc_insn.form)
 656     {
 657     case FORM_PRE_ADD:
 658     case FORM_PRE_INC:
 659       last_insn = mem_insn.insn;
 660       break;
 661     case FORM_POST_INC:
 662     case FORM_POST_ADD:
 663       last_insn = inc_insn.insn;
 664       break;
 665     case FORM_last:
 666     default:
 667       gcc_unreachable ();
 668     }
 669
 670   /* Cannot handle auto inc of the stack.  */
 671   if (inc_reg == stack_pointer_rtx)
 672     {
 673       if (dump_file)
 674         fprintf (dump_file, "cannot inc stack %d failure\n", REGNO (inc_reg));
 675       return false;
 676     }
 677
 678   /* Look to see if the inc register is dead after the memory
 679      reference.  If it is, do not do the combination.  */
 680   if (find_regno_note (last_insn, REG_DEAD, REGNO (inc_reg)))
 681     {
 682       if (dump_file)
 683         fprintf (dump_file, "dead failure %d\n", REGNO (inc_reg));
 684       return false;
 685     }
 686
 687   mem_insn.reg1_state = (mem_insn.reg1_is_const)
 688     ? set_inc_state (mem_insn.reg1_val, size) : INC_REG;
 689   inc_insn.reg1_state = (inc_insn.reg1_is_const)
 690     ? set_inc_state (inc_insn.reg1_val, size) : INC_REG;
 691
 692   /* Now get the form that we are generating.  */
 693   gen_form = decision_table
 694     [inc_insn.reg1_state][mem_insn.reg1_state][inc_insn.form];
 695
 696   if (dbg_cnt (auto_inc_dec) == false)
 697     return false;
 698
 699   switch (gen_form)
 700     {
 701     default:
 702     case NOTHING:
 703       return false;
 704
 705     case SIMPLE_PRE_INC:     /* ++size  */
 706       if (dump_file)
 707         fprintf (dump_file, "trying SIMPLE_PRE_INC\n");
 708       return attempt_change (gen_rtx_PRE_INC (Pmode, inc_reg), inc_reg);
 709       break;
 710
 711     case SIMPLE_POST_INC:    /* size++  */
 712       if (dump_file)
 713         fprintf (dump_file, "trying SIMPLE_POST_INC\n");
 714       return attempt_change (gen_rtx_POST_INC (Pmode, inc_reg), inc_reg);
 715       break;
 716
 717     case SIMPLE_PRE_DEC:     /* --size  */
 718       if (dump_file)
 719         fprintf (dump_file, "trying SIMPLE_PRE_DEC\n");
 720       return attempt_change (gen_rtx_PRE_DEC (Pmode, inc_reg), inc_reg);
 721       break;
 722
 723     case SIMPLE_POST_DEC:    /* size--  */
 724       if (dump_file)
 725         fprintf (dump_file, "trying SIMPLE_POST_DEC\n");
 726       return attempt_change (gen_rtx_POST_DEC (Pmode, inc_reg), inc_reg);
 727       break;
 728
 729     case DISP_PRE:           /* ++con   */
 730       if (dump_file)
 731         fprintf (dump_file, "trying DISP_PRE\n");
 732       return attempt_change (gen_rtx_PRE_MODIFY (Pmode,
 733                                                  inc_reg,
 734                                                  gen_rtx_PLUS (Pmode,
 735                                                                inc_reg,
 736                                                                inc_insn.reg1)),
 737                              inc_reg);
 738       break;
 739
 740     case DISP_POST:          /* con++   */
 741       if (dump_file)
 742         fprintf (dump_file, "trying POST_DISP\n");
 743       return attempt_change (gen_rtx_POST_MODIFY (Pmode,
 744                                                   inc_reg,
 745                                                   gen_rtx_PLUS (Pmode,
 746                                                                 inc_reg,
 747                                                                 inc_insn.reg1)),
 748                              inc_reg);
 749       break;
 750
 751     case REG_PRE:            /* ++reg   */
 752       if (dump_file)
 753         fprintf (dump_file, "trying PRE_REG\n");
 754       return attempt_change (gen_rtx_PRE_MODIFY (Pmode,
 755                                                  inc_reg,
 756                                                  gen_rtx_PLUS (Pmode,
 757                                                                inc_reg,
 758                                                                inc_insn.reg1)),
 759                              inc_reg);
 760       break;
 761
 762     case REG_POST:            /* reg++   */
 763       if (dump_file)
 764         fprintf (dump_file, "trying POST_REG\n");
 765       return attempt_change (gen_rtx_POST_MODIFY (Pmode,
 766                                                   inc_reg,
 767                                                   gen_rtx_PLUS (Pmode,
 768                                                                 inc_reg,
 769                                                                 inc_insn.reg1)),
 770                              inc_reg);
 771       break;
 772     }
 773 }
 774
 775 /* Return the next insn that uses (if reg_next_use is passed in
 776    NEXT_ARRAY) or defines (if reg_next_def is passed in NEXT_ARRAY)
 777    REGNO in BB.  */
 778
 779 static rtx
 780 get_next_ref (int regno, basic_block bb, rtx *next_array)
 781 {
 782   rtx insn = next_array[regno];
 783
 784   /* Lazy about cleaning out the next_arrays.  */
 785   if (insn && BASIC_BLOCK (BLOCK_NUM (insn)) != bb)
 786     {
 787       next_array[regno] = NULL;
 788       insn = NULL;
 789     }
 790
 791   return insn;
 792 }
 793
 794
 795 /* Reverse the operands in a mem insn.  */
 796
 797 static void
 798 reverse_mem (void)
 799 {
 800   rtx tmp = mem_insn.reg1;
 801   mem_insn.reg1 = mem_insn.reg0;
 802   mem_insn.reg0 = tmp;
 803 }
 804
 805
 806 /* Reverse the operands in a inc insn.  */
 807
 808 static void
 809 reverse_inc (void)
 810 {
 811   rtx tmp = inc_insn.reg1;
 812   inc_insn.reg1 = inc_insn.reg0;
 813   inc_insn.reg0 = tmp;
 814 }
 815
 816
 817 /* Return true if INSN is of a form "a = b op c" where a and b are
 818    regs.  op is + if c is a reg and +|- if c is a const.  Fill in
 819    INC_INSN with what is found.
 820
 821    This function is called in two contexts, if BEFORE_MEM is true,
 822    this is called for each insn in the basic block.  If BEFORE_MEM is
 823    false, it is called for the instruction in the block that uses the
 824    index register for some memory reference that is currently being
 825    processed.  */
 826
 827 static bool
 828 parse_add_or_inc (rtx insn, bool before_mem)
 829 {
 830   rtx pat = single_set (insn);
 831   if (!pat)
 832     return false;
 833
 834   /* Result must be single reg.  */
 835   if (!REG_P (SET_DEST (pat)))
 836     return false;
 837
 838   if ((GET_CODE (SET_SRC (pat)) != PLUS)
 839       && (GET_CODE (SET_SRC (pat)) != MINUS))
 840     return false;
 841
 842   if (!REG_P (XEXP (SET_SRC (pat), 0)))
 843     return false;
 844
 845   inc_insn.insn = insn;
 846   inc_insn.pat = pat;
 847   inc_insn.reg_res = SET_DEST (pat);
 848   inc_insn.reg0 = XEXP (SET_SRC (pat), 0);
 849   if (rtx_equal_p (inc_insn.reg_res, inc_insn.reg0))
 850     inc_insn.form = before_mem ? FORM_PRE_INC : FORM_POST_INC;
 851   else
 852     inc_insn.form = before_mem ? FORM_PRE_ADD : FORM_POST_ADD;
 853
 854   if (GET_CODE (XEXP (SET_SRC (pat), 1)) == CONST_INT)
 855     {
 856       /* Process a = b + c where c is a const.  */
 857       inc_insn.reg1_is_const = true;
 858       if (GET_CODE (SET_SRC (pat)) == PLUS)
 859         {
 860           inc_insn.reg1 = XEXP (SET_SRC (pat), 1);
 861           inc_insn.reg1_val = INTVAL (inc_insn.reg1);
 862         }
 863       else
 864         {
 865           inc_insn.reg1_val = -INTVAL (XEXP (SET_SRC (pat), 1));
 866           inc_insn.reg1 = GEN_INT (inc_insn.reg1_val);
 867         }
 868       return true;
 869     }
 870   else if ((HAVE_PRE_MODIFY_REG || HAVE_POST_MODIFY_REG)
 871            && (REG_P (XEXP (SET_SRC (pat), 1)))
 872            && GET_CODE (SET_SRC (pat)) == PLUS)
 873     {
 874       /* Process a = b + c where c is a reg.  */
 875       inc_insn.reg1 = XEXP (SET_SRC (pat), 1);
 876       inc_insn.reg1_is_const = false;
 877
 878       if (inc_insn.form == FORM_PRE_INC
 879           || inc_insn.form == FORM_POST_INC)
 880         return true;
 881       else if (rtx_equal_p (inc_insn.reg_res, inc_insn.reg1))
 882         {
 883           /* Reverse the two operands and turn *_ADD into *_INC since
 884              a = c + a.  */
 885           reverse_inc ();
 886           inc_insn.form = before_mem ? FORM_PRE_INC : FORM_POST_INC;
 887           return true;
 888         }
 889       else
 890         return true;
 891     }
 892
 893   return false;
 894 }
 895
 896
 897 /* A recursive function that checks all of the mem uses in
 898    ADDRESS_OF_X to see if any single one of them is compatible with
 899    what has been found in inc_insn.
 900
 901    -1 is returned for success.  0 is returned if nothing was found and
 902    1 is returned for failure. */
 903
 904 static int
 905 find_address (rtx *address_of_x)
 906 {
 907   rtx x = *address_of_x;
 908   enum rtx_code code = GET_CODE (x);
 909   const char *const fmt = GET_RTX_FORMAT (code);
 910   int i;
 911   int value = 0;
 912   int tem;
 913
 914   if (code == MEM && rtx_equal_p (XEXP (x, 0), inc_insn.reg_res))
 915     {
 916       /* Match with *reg0.  */
 917       mem_insn.mem_loc = address_of_x;
 918       mem_insn.reg0 = inc_insn.reg_res;
 919       mem_insn.reg1_is_const = true;
 920       mem_insn.reg1_val = 0;
 921       mem_insn.reg1 = GEN_INT (0);
 922       return -1;
 923     }
 924   if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
 925       && rtx_equal_p (XEXP (XEXP (x, 0), 0), inc_insn.reg_res))
 926     {
 927       rtx b = XEXP (XEXP (x, 0), 1);
 928       mem_insn.mem_loc = address_of_x;
 929       mem_insn.reg0 = inc_insn.reg_res;
 930       mem_insn.reg1 = b;
 931       mem_insn.reg1_is_const = inc_insn.reg1_is_const;
 932       if (GET_CODE (b) == CONST_INT)
 933         {
 934           /* Match with *(reg0 + reg1) where reg1 is a const. */
 935           HOST_WIDE_INT val = INTVAL (b);
 936           if (inc_insn.reg1_is_const
 937               && (inc_insn.reg1_val == val || inc_insn.reg1_val == -val))
 938             {
 939               mem_insn.reg1_val = val;
 940               return -1;
 941             }
 942         }
 943       else if (!inc_insn.reg1_is_const
 944                && rtx_equal_p (inc_insn.reg1, b))
 945         /* Match with *(reg0 + reg1). */
 946         return -1;
 947     }
 948
 949   if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
 950     {
 951       /* If REG occurs inside a MEM used in a bit-field reference,
 952          that is unacceptable.  */
 953       if (find_address (&XEXP (x, 0)))
 954         return 1;
 955     }
 956
 957   if (x == inc_insn.reg_res)
 958     return 1;
 959
 960   /* Time for some deep diving.  */
 961   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 962     {
 963       if (fmt[i] == 'e')
 964         {
 965           tem = find_address (&XEXP (x, i));
 966           /* If this is the first use, let it go so the rest of the
 967              insn can be checked.  */
 968           if (value == 0)
 969             value = tem;
 970           else if (tem != 0)
 971             /* More than one match was found.  */
 972             return 1;
 973         }
 974       else if (fmt[i] == 'E')
 975         {
 976           int j;
 977           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 978             {
 979               tem = find_address (&XVECEXP (x, i, j));
 980               /* If this is the first use, let it go so the rest of
 981                  the insn can be checked.  */
 982               if (value == 0)
 983                 value = tem;
 984               else if (tem != 0)
 985                 /* More than one match was found.  */
 986                 return 1;
 987             }
 988         }
 989     }
 990   return value;
 991 }
 992
 993 /* Once a suitable mem reference has been found and the MEM_INSN
 994    structure has been filled in, FIND_INC is called to see if there is
 995    a suitable add or inc insn that follows the mem reference and
 996    determine if it is suitable to merge.
 997
 998    In the case where the MEM_INSN has two registers in the reference,
 999    this function may be called recursively.  The first time looking
1000    for an add of the first register, and if that fails, looking for an
1001    add of the second register.  The FIRST_TRY parameter is used to
1002    only allow the parameters to be reversed once.  */
1003
1004 static bool
1005 find_inc (bool first_try)
1006 {
1007   rtx insn;
1008   basic_block bb = BASIC_BLOCK (BLOCK_NUM (mem_insn.insn));
1009   rtx other_insn;
1010   df_ref *def_rec;
1011
1012   /* Make sure this reg appears only once in this insn.  */
1013   if (count_occurrences (PATTERN (mem_insn.insn), mem_insn.reg0, 1) != 1)
1014     {
1015       if (dump_file)
1016         fprintf (dump_file, "mem count failure\n");
1017       return false;
1018     }
1019
1020   if (dump_file)
1021     dump_mem_insn (dump_file);
1022
1023   /* Find the next use that is an inc.  */
1024   insn = get_next_ref (REGNO (mem_insn.reg0),
1025                        BASIC_BLOCK (BLOCK_NUM (mem_insn.insn)),
1026                        reg_next_inc_use);
1027   if (!insn)
1028     return false;
1029
1030   /* Even though we know the next use is an add or inc because it came
1031      from the reg_next_inc_use, we must still reparse.  */
1032   if (!parse_add_or_inc (insn, false))
1033     {
1034       /* Next use was not an add.  Look for one extra case. It could be
1035          that we have:
1036
1037          *(a + b)
1038          ...= a;
1039          ...= b + a
1040
1041          if we reverse the operands in the mem ref we would
1042          find this.  Only try it once though.  */
1043       if (first_try && !mem_insn.reg1_is_const)
1044         {
1045           reverse_mem ();
1046           return find_inc (false);
1047         }
1048       else
1049         return false;
1050     }
1051
1052   /* Need to assure that none of the operands of the inc instruction are
1053      assigned to by the mem insn.  */
1054   for (def_rec = DF_INSN_DEFS (mem_insn.insn); *def_rec; def_rec++)
1055     {
1056       df_ref def = *def_rec;
1057       unsigned int regno = DF_REF_REGNO (def);
1058       if ((regno == REGNO (inc_insn.reg0))
1059           || (regno == REGNO (inc_insn.reg_res)))
1060         {
1061           if (dump_file)
1062             fprintf (dump_file, "inc conflicts with store failure.\n");
1063           return false;
1064         }
1065       if (!inc_insn.reg1_is_const && (regno == REGNO (inc_insn.reg1)))
1066         {
1067           if (dump_file)
1068             fprintf (dump_file, "inc conflicts with store failure.\n");
1069           return false;
1070         }
1071     }
1072
1073   if (dump_file)
1074     dump_inc_insn (dump_file);
1075
1076   if (inc_insn.form == FORM_POST_ADD)
1077     {
1078       /* Make sure that there is no insn that assigns to inc_insn.res
1079          between the mem_insn and the inc_insn.  */
1080       rtx other_insn = get_next_ref (REGNO (inc_insn.reg_res),
1081                                      BASIC_BLOCK (BLOCK_NUM (mem_insn.insn)),
1082                                      reg_next_def);
1083       if (other_insn != inc_insn.insn)
1084         {
1085           if (dump_file)
1086             fprintf (dump_file,
1087                      "result of add is assigned to between mem and inc insns.\n");
1088           return false;
1089         }
1090
1091       other_insn = get_next_ref (REGNO (inc_insn.reg_res),
1092                                  BASIC_BLOCK (BLOCK_NUM (mem_insn.insn)),
1093                                  reg_next_use);
1094       if (other_insn
1095           && (other_insn != inc_insn.insn)
1096           && (DF_INSN_LUID (inc_insn.insn) > DF_INSN_LUID (other_insn)))
1097         {
1098           if (dump_file)
1099             fprintf (dump_file,
1100                      "result of add is used between mem and inc insns.\n");
1101           return false;
1102         }
1103
1104       /* For the post_add to work, the result_reg of the inc must not be
1105          used in the mem insn since this will become the new index
1106          register.  */
1107       if (count_occurrences (PATTERN (mem_insn.insn), inc_insn.reg_res, 1) != 0)
1108         {
1109           if (dump_file)
1110             fprintf (dump_file, "base reg replacement failure.\n");
1111           return false;
1112         }
1113     }
1114
1115   if (mem_insn.reg1_is_const)
1116     {
1117       if (mem_insn.reg1_val == 0)
1118         {
1119           if (!inc_insn.reg1_is_const)
1120             {
1121               /* The mem looks like *r0 and the rhs of the add has two
1122                  registers.  */
1123               int luid = DF_INSN_LUID (inc_insn.insn);
1124               if (inc_insn.form == FORM_POST_ADD)
1125                 {
1126                   /* The trick is that we are not going to increment r0,
1127                      we are going to increment the result of the add insn.
1128                      For this trick to be correct, the result reg of
1129                      the inc must be a valid addressing reg.  */
1130                   if (GET_MODE (inc_insn.reg_res) != Pmode)
1131                     {
1132                       if (dump_file)
1133                         fprintf (dump_file, "base reg mode failure.\n");
1134                       return false;
1135                     }
1136
1137                   /* We also need to make sure that the next use of
1138                      inc result is after the inc.  */
1139                   other_insn
1140                     = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_use);
1141                   if (other_insn && luid > DF_INSN_LUID (other_insn))
1142                     return false;
1143
1144                   if (!rtx_equal_p (mem_insn.reg0, inc_insn.reg0))
1145                     reverse_inc ();
1146                 }
1147
1148               other_insn
1149                 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1150               if (other_insn && luid > DF_INSN_LUID (other_insn))
1151                 return false;
1152             }
1153         }
1154       /* Both the inc/add and the mem have a constant.  Need to check
1155          that the constants are ok. */
1156       else if ((mem_insn.reg1_val != inc_insn.reg1_val)
1157                && (mem_insn.reg1_val != -inc_insn.reg1_val))
1158         return false;
1159     }
1160   else
1161     {
1162       /* The mem insn is of the form *(a + b) where a and b are both
1163          regs.  It may be that in order to match the add or inc we
1164          need to treat it as if it was *(b + a).  It may also be that
1165          the add is of the form a + c where c does not match b and
1166          then we just abandon this.  */
1167
1168       int luid = DF_INSN_LUID (inc_insn.insn);
1169       rtx other_insn;
1170
1171       /* Make sure this reg appears only once in this insn.  */
1172       if (count_occurrences (PATTERN (mem_insn.insn), mem_insn.reg1, 1) != 1)
1173         return false;
1174
1175       if (inc_insn.form == FORM_POST_ADD)
1176         {
1177           /* For this trick to be correct, the result reg of the inc
1178              must be a valid addressing reg.  */
1179           if (GET_MODE (inc_insn.reg_res) != Pmode)
1180             {
1181               if (dump_file)
1182                 fprintf (dump_file, "base reg mode failure.\n");
1183               return false;
1184             }
1185
1186           if (rtx_equal_p (mem_insn.reg0, inc_insn.reg0))
1187             {
1188               if (!rtx_equal_p (mem_insn.reg1, inc_insn.reg1))
1189                 {
1190                   /* See comment above on find_inc (false) call.  */
1191                   if (first_try)
1192                     {
1193                       reverse_mem ();
1194                       return find_inc (false);
1195                     }
1196                   else
1197                     return false;
1198                 }
1199
1200               /* Need to check that there are no assignments to b
1201                  before the add insn.  */
1202               other_insn
1203                 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1204               if (other_insn && luid > DF_INSN_LUID (other_insn))
1205                 return false;
1206               /* All ok for the next step.  */
1207             }
1208           else
1209             {
1210               /* We know that mem_insn.reg0 must equal inc_insn.reg1
1211                  or else we would not have found the inc insn.  */
1212               reverse_mem ();
1213               if (!rtx_equal_p (mem_insn.reg0, inc_insn.reg0))
1214                 {
1215                   /* See comment above on find_inc (false) call.  */
1216                   if (first_try)
1217                     return find_inc (false);
1218                   else
1219                     return false;
1220                 }
1221               /* To have gotten here know that.
1222                *(b + a)
1223
1224                ... = (b + a)
1225
1226                We also know that the lhs of the inc is not b or a.  We
1227                need to make sure that there are no assignments to b
1228                between the mem ref and the inc.  */
1229
1230               other_insn
1231                 = get_next_ref (REGNO (inc_insn.reg0), bb, reg_next_def);
1232               if (other_insn && luid > DF_INSN_LUID (other_insn))
1233                 return false;
1234             }
1235
1236           /* Need to check that the next use of the add result is later than
1237              add insn since this will be the reg incremented.  */
1238           other_insn
1239             = get_next_ref (REGNO (inc_insn.reg_res), bb, reg_next_use);
1240           if (other_insn && luid > DF_INSN_LUID (other_insn))
1241             return false;
1242         }
1243       else /* FORM_POST_INC.  There is less to check here because we
1244               know that operands must line up.  */
1245         {
1246           if (!rtx_equal_p (mem_insn.reg1, inc_insn.reg1))
1247             /* See comment above on find_inc (false) call.  */
1248             {
1249               if (first_try)
1250                 {
1251                   reverse_mem ();
1252                   return find_inc (false);
1253                 }
1254               else
1255                 return false;
1256             }
1257
1258           /* To have gotten here know that.
1259            *(a + b)
1260
1261            ... = (a + b)
1262
1263            We also know that the lhs of the inc is not b.  We need to make
1264            sure that there are no assignments to b between the mem ref and
1265            the inc.  */
1266           other_insn
1267             = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1268           if (other_insn && luid > DF_INSN_LUID (other_insn))
1269             return false;
1270         }
1271     }
1272
1273   if (inc_insn.form == FORM_POST_INC)
1274     {
1275       other_insn
1276         = get_next_ref (REGNO (inc_insn.reg0), bb, reg_next_use);
1277       /* When we found inc_insn, we were looking for the
1278          next add or inc, not the next insn that used the
1279          reg.  Because we are going to increment the reg
1280          in this form, we need to make sure that there
1281          were no intervening uses of reg.  */
1282       if (inc_insn.insn != other_insn)
1283         return false;
1284     }
1285
1286   return try_merge ();
1287 }
1288
1289
1290 /* A recursive function that walks ADDRESS_OF_X to find all of the mem
1291    uses in pat that could be used as an auto inc or dec.  It then
1292    calls FIND_INC for each one.  */
1293
1294 static bool
1295 find_mem (rtx *address_of_x)
1296 {
1297   rtx x = *address_of_x;
1298   enum rtx_code code = GET_CODE (x);
1299   const char *const fmt = GET_RTX_FORMAT (code);
1300   int i;
1301
1302   if (code == MEM && REG_P (XEXP (x, 0)))
1303     {
1304       /* Match with *reg0.  */
1305       mem_insn.mem_loc = address_of_x;
1306       mem_insn.reg0 = XEXP (x, 0);
1307       mem_insn.reg1_is_const = true;
1308       mem_insn.reg1_val = 0;
1309       mem_insn.reg1 = GEN_INT (0);
1310       if (find_inc (true))
1311         return true;
1312     }
1313   if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
1314       && REG_P (XEXP (XEXP (x, 0), 0)))
1315     {
1316       rtx reg1 = XEXP (XEXP (x, 0), 1);
1317       mem_insn.mem_loc = address_of_x;
1318       mem_insn.reg0 = XEXP (XEXP (x, 0), 0);
1319       mem_insn.reg1 = reg1;
1320       if (GET_CODE (reg1) == CONST_INT)
1321         {
1322           mem_insn.reg1_is_const = true;
1323           /* Match with *(reg0 + c) where c is a const. */
1324           mem_insn.reg1_val = INTVAL (reg1);
1325           if (find_inc (true))
1326             return true;
1327         }
1328       else if (REG_P (reg1))
1329         {
1330           /* Match with *(reg0 + reg1).  */
1331           mem_insn.reg1_is_const = false;
1332           if (find_inc (true))
1333             return true;
1334         }
1335     }
1336
1337   if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
1338     {
1339       /* If REG occurs inside a MEM used in a bit-field reference,
1340          that is unacceptable.  */
1341       return false;
1342     }
1343
1344   /* Time for some deep diving.  */
1345   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1346     {
1347       if (fmt[i] == 'e')
1348         {
1349           if (find_mem (&XEXP (x, i)))
1350             return true;
1351         }
1352       else if (fmt[i] == 'E')
1353         {
1354           int j;
1355           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1356             if (find_mem (&XVECEXP (x, i, j)))
1357               return true;
1358         }
1359     }
1360   return false;
1361 }
1362
1363
1364 /* Try to combine all incs and decs by constant values with memory
1365    references in BB.  */
1366
1367 static void
1368 merge_in_block (int max_reg, basic_block bb)
1369 {
1370   rtx insn;
1371   rtx curr;
1372   int success_in_block = 0;
1373
1374   if (dump_file)
1375     fprintf (dump_file, "\n\nstarting bb %d\n", bb->index);
1376
1377   FOR_BB_INSNS_REVERSE_SAFE (bb, insn, curr)
1378     {
1379       unsigned int uid = INSN_UID (insn);
1380       bool insn_is_add_or_inc = true;
1381
1382       if (!INSN_P (insn))
1383         continue;
1384
1385       /* This continue is deliberate.  We do not want the uses of the
1386          jump put into reg_next_use because it is not considered safe to
1387          combine a preincrement with a jump.  */
1388       if (JUMP_P (insn))
1389         continue;
1390
1391       if (dump_file)
1392         dump_insn_slim (dump_file, insn);
1393
1394       /* Does this instruction increment or decrement a register?  */
1395       if (parse_add_or_inc (insn, true))
1396         {
1397           int regno = REGNO (inc_insn.reg_res);
1398           /* Cannot handle case where there are three separate regs
1399              before a mem ref.  Too many moves would be needed to be
1400              profitable.  */
1401           if ((inc_insn.form == FORM_PRE_INC) || inc_insn.reg1_is_const)
1402             {
1403               mem_insn.insn = get_next_ref (regno, bb, reg_next_use);
1404               if (mem_insn.insn)
1405                 {
1406                   bool ok = true;
1407                   if (!inc_insn.reg1_is_const)
1408                     {
1409                       /* We are only here if we are going to try a
1410                          HAVE_*_MODIFY_REG type transformation.  c is a
1411                          reg and we must sure that the path from the
1412                          inc_insn to the mem_insn.insn is both def and use
1413                          clear of c because the inc insn is going to move
1414                          into the mem_insn.insn.  */
1415                       int luid = DF_INSN_LUID (mem_insn.insn);
1416                       rtx other_insn
1417                         = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_use);
1418
1419                       if (other_insn && luid > DF_INSN_LUID (other_insn))
1420                         ok = false;
1421
1422                       other_insn
1423                         = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1424
1425                       if (other_insn && luid > DF_INSN_LUID (other_insn))
1426                         ok = false;
1427                     }
1428
1429                   if (dump_file)
1430                     dump_inc_insn (dump_file);
1431
1432                   if (ok && find_address (&PATTERN (mem_insn.insn)) == -1)
1433                     {
1434                       if (dump_file)
1435                         dump_mem_insn (dump_file);
1436                       if (try_merge ())
1437                         {
1438                           success_in_block++;
1439                           insn_is_add_or_inc = false;
1440                         }
1441                     }
1442                 }
1443             }
1444         }
1445       else
1446         {
1447           insn_is_add_or_inc = false;
1448           mem_insn.insn = insn;
1449           if (find_mem (&PATTERN (insn)))
1450             success_in_block++;
1451         }
1452
1453       /* If the inc insn was merged with a mem, the inc insn is gone
1454          and there is noting to update.  */
1455       if (DF_INSN_UID_GET(uid))
1456         {
1457           df_ref *def_rec;
1458           df_ref *use_rec;
1459           /* Need to update next use.  */
1460           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1461             {
1462               df_ref def = *def_rec;
1463               reg_next_use[DF_REF_REGNO (def)] = NULL;
1464               reg_next_inc_use[DF_REF_REGNO (def)] = NULL;
1465               reg_next_def[DF_REF_REGNO (def)] = insn;
1466             }
1467
1468           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1469             {
1470               df_ref use = *use_rec;
1471               reg_next_use[DF_REF_REGNO (use)] = insn;
1472               if (insn_is_add_or_inc)
1473                 reg_next_inc_use[DF_REF_REGNO (use)] = insn;
1474               else
1475                 reg_next_inc_use[DF_REF_REGNO (use)] = NULL;
1476             }
1477         }
1478       else if (dump_file)
1479         fprintf (dump_file, "skipping update of deleted insn %d\n", uid);
1480     }
1481
1482   /* If we were successful, try again.  There may have been several
1483      opportunities that were interleaved.  This is rare but
1484      gcc.c-torture/compile/pr17273.c actually exhibits this.  */
1485   if (success_in_block)
1486     {
1487       /* In this case, we must clear these vectors since the trick of
1488          testing if the stale insn in the block will not work.  */
1489       memset (reg_next_use, 0, max_reg * sizeof(rtx));
1490       memset (reg_next_inc_use, 0, max_reg * sizeof(rtx));
1491       memset (reg_next_def, 0, max_reg * sizeof(rtx));
1492       df_recompute_luids (bb);
1493       merge_in_block (max_reg, bb);
1494     }
1495 }
1496
1497 #endif
1498
1499 static unsigned int
1500 rest_of_handle_auto_inc_dec (void)
1501 {
1502 #ifdef AUTO_INC_DEC
1503   basic_block bb;
1504   int max_reg = max_reg_num ();
1505
1506   if (!initialized)
1507     init_decision_table ();
1508
1509   mem_tmp = gen_rtx_MEM (Pmode, NULL_RTX);
1510
1511   df_note_add_problem ();
1512   df_analyze ();
1513
1514   reg_next_use = XCNEWVEC (rtx, max_reg);
1515   reg_next_inc_use = XCNEWVEC (rtx, max_reg);
1516   reg_next_def = XCNEWVEC (rtx, max_reg);
1517   FOR_EACH_BB (bb)
1518     merge_in_block (max_reg, bb);
1519
1520   free (reg_next_use);
1521   free (reg_next_inc_use);
1522   free (reg_next_def);
1523
1524   mem_tmp = NULL;
1525 #endif
1526   return 0;
1527 }
1528
1529
1530 /* Discover auto-inc auto-dec instructions.  */
1531
1532 static bool
1533 gate_auto_inc_dec (void)
1534 {
1535 #ifdef AUTO_INC_DEC
1536   return (optimize > 0 && flag_auto_inc_dec);
1537 #else
1538   return false;
1539 #endif
1540 }
1541
1542
1543 struct rtl_opt_pass pass_inc_dec =
1544 {
1545  {
1546   RTL_PASS,
1547   "auto_inc_dec",                       /* name */
1548   gate_auto_inc_dec,                    /* gate */
1549   rest_of_handle_auto_inc_dec,          /* execute */
1550   NULL,                                 /* sub */
1551   NULL,                                 /* next */
1552   0,                                    /* static_pass_number */
1553   TV_AUTO_INC_DEC,                      /* tv_id */
1554   0,                                    /* properties_required */
1555   0,                                    /* properties_provided */
1556   0,                                    /* properties_destroyed */
1557   0,                                    /* todo_flags_start */
1558   TODO_dump_func |
1559   TODO_df_finish,                       /* todo_flags_finish */
1560  }
1561 };
1562