gcc/auto-inc-dec.c

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