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

source code of gcc/auto-inc-dec.cc