OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [auto-inc-dec.c] - Blame information for rev 859

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.