gcc/auto-inc-dec.c

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