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

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