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