Daily bump.
[official-gcc.git] / gcc / auto-inc-dec.c
blobe6dc1c30d716fcfe44b7a09eeb0dfe5fa1c86c3b
1 /* Discovery of auto-inc and auto-dec instructions.
2 Copyright (C) 2006-2018 Free Software Foundation, Inc.
3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
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"
40 /* This pass was originally removed from flow.c. However there is
41 almost nothing that remains of that code.
43 There are (4) basic forms that are matched:
45 (1) FORM_PRE_ADD
46 a <- b + c
47 ...
50 becomes
52 a <- b
53 ...
54 *(a += c) pre
57 (2) FORM_PRE_INC
58 a += c
59 ...
62 becomes
64 *(a += c) pre
67 (3) FORM_POST_ADD
69 ...
70 b <- a + c
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.)
75 becomes
77 b <- a
78 ...
79 *(b += c) post
82 (4) FORM_POST_INC
84 ...
85 a <- a + c
87 becomes
89 *(a += c) post
91 There are three types of values of c.
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.
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.
102 3) c is a register. This is useful for machines that have
103 HAVE_PRE_MODIFY_REG, HAVE_POST_MODIFY_REG
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. */
111 enum form
113 FORM_PRE_ADD,
114 FORM_PRE_INC,
115 FORM_POST_ADD,
116 FORM_POST_INC,
117 FORM_last
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. */
126 enum inc_state
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
137 /* The eight forms that pre/post inc/dec can take. */
138 enum gen_form
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++ */
151 /* Tmp mem rtx for use in cost modeling. */
152 static rtx mem_tmp;
154 static enum inc_state
155 set_inc_state (HOST_WIDE_INT val, poly_int64 size)
157 if (val == 0)
158 return INC_ZERO;
159 if (val < 0)
160 return known_eq (val, -size) ? INC_NEG_SIZE : INC_NEG_ANY;
161 else
162 return known_eq (val, size) ? INC_POS_SIZE : INC_POS_ANY;
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. */
173 static bool initialized = false;
174 static enum gen_form decision_table[INC_last][INC_last][FORM_last];
176 static void
177 init_decision_table (void)
179 enum gen_form value;
181 if (HAVE_PRE_INCREMENT || HAVE_PRE_MODIFY_DISP)
183 /* Prefer the simple form if both are available. */
184 value = (HAVE_PRE_INCREMENT) ? SIMPLE_PRE_INC : DISP_PRE;
186 decision_table[INC_POS_SIZE][INC_ZERO][FORM_PRE_ADD] = value;
187 decision_table[INC_POS_SIZE][INC_ZERO][FORM_PRE_INC] = value;
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;
193 if (HAVE_POST_INCREMENT || HAVE_POST_MODIFY_DISP)
195 /* Prefer the simple form if both are available. */
196 value = (HAVE_POST_INCREMENT) ? SIMPLE_POST_INC : DISP_POST;
198 decision_table[INC_POS_SIZE][INC_ZERO][FORM_POST_ADD] = value;
199 decision_table[INC_POS_SIZE][INC_ZERO][FORM_POST_INC] = value;
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;
205 if (HAVE_PRE_DECREMENT || HAVE_PRE_MODIFY_DISP)
207 /* Prefer the simple form if both are available. */
208 value = (HAVE_PRE_DECREMENT) ? SIMPLE_PRE_DEC : DISP_PRE;
210 decision_table[INC_NEG_SIZE][INC_ZERO][FORM_PRE_ADD] = value;
211 decision_table[INC_NEG_SIZE][INC_ZERO][FORM_PRE_INC] = value;
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;
217 if (HAVE_POST_DECREMENT || HAVE_POST_MODIFY_DISP)
219 /* Prefer the simple form if both are available. */
220 value = (HAVE_POST_DECREMENT) ? SIMPLE_POST_DEC : DISP_POST;
222 decision_table[INC_NEG_SIZE][INC_ZERO][FORM_POST_ADD] = value;
223 decision_table[INC_NEG_SIZE][INC_ZERO][FORM_POST_INC] = value;
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;
229 if (HAVE_PRE_MODIFY_DISP)
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;
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;
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;
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;
244 if (HAVE_POST_MODIFY_DISP)
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;
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;
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;
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;
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.
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)
273 decision_table[INC_REG][INC_ZERO][FORM_PRE_ADD] = REG_PRE;
274 decision_table[INC_REG][INC_ZERO][FORM_PRE_INC] = REG_PRE;
276 decision_table[INC_REG][INC_REG][FORM_POST_ADD] = REG_PRE;
277 decision_table[INC_REG][INC_REG][FORM_POST_INC] = REG_PRE;
280 if (HAVE_POST_MODIFY_REG)
282 decision_table[INC_REG][INC_ZERO][FORM_POST_ADD] = REG_POST;
283 decision_table[INC_REG][INC_ZERO][FORM_POST_INC] = REG_POST;
286 initialized = true;
289 /* Parsed fields of an inc insn of the form "reg_res = reg0+reg1" or
290 "reg_res = reg0+c". */
292 static struct inc_insn
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;
306 /* Dump the parsed inc insn to FILE. */
308 static void
309 dump_inc_insn (FILE *file)
311 const char *f = ((inc_insn.form == FORM_PRE_ADD)
312 || (inc_insn.form == FORM_PRE_INC)) ? "pre" : "post";
314 dump_insn_slim (file, inc_insn.insn);
316 switch (inc_insn.form)
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;
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;
344 default:
345 break;
350 /* Parsed fields of a mem ref of the form "*(reg0+reg1)" or "*(reg0+c)". */
352 static struct mem_insn
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;
367 /* Dump the parsed mem insn to FILE. */
369 static void
370 dump_mem_insn (FILE *file)
372 dump_insn_slim (file, mem_insn.insn);
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));
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.
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.
396 static rtx_insn **reg_next_use = NULL;
397 static rtx_insn **reg_next_inc_use = NULL;
398 static rtx_insn **reg_next_def = NULL;
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. */
406 static void
407 move_dead_notes (rtx_insn *to_insn, rtx_insn *from_insn, rtx pattern)
409 rtx note;
410 rtx next_note;
411 rtx prev_note = NULL;
413 for (note = REG_NOTES (from_insn); note; note = next_note)
415 next_note = XEXP (note, 1);
417 if ((REG_NOTE_KIND (note) == REG_DEAD)
418 && pattern == XEXP (note, 0))
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;
427 else prev_note = note;
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. */
437 static bool
438 attempt_change (rtx new_addr, rtx inc_reg)
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. */
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);
459 PUT_MODE (mem_tmp, mode);
460 XEXP (mem_tmp, 0) = new_addr;
462 old_cost = (set_src_cost (mem, mode, speed)
463 + set_rtx_cost (PATTERN (inc_insn.insn), speed));
465 new_cost = set_src_cost (mem_tmp, mode, speed);
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)
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);
479 /* The first item of business is to see if this is profitable. */
480 if (old_cost < new_cost)
482 if (dump_file)
483 fprintf (dump_file, "cost failure old=%d new=%d\n", old_cost, new_cost);
484 return false;
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))
495 if (dump_file)
496 fprintf (dump_file, "validation failure\n");
497 return false;
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)
505 case FORM_PRE_ADD:
506 /* Replace the addition with a move. Do it at the location of
507 the addition since the operand of the addition may change
508 before the memory reference. */
509 gcc_assert (mov_insn);
510 emit_insn_before (mov_insn, inc_insn.insn);
511 regno = REGNO (inc_insn.reg0);
512 if (reg_next_use[regno] == mem_insn.insn)
513 move_dead_notes (mov_insn, mem_insn.insn, inc_insn.reg0);
514 else
515 move_dead_notes (mov_insn, inc_insn.insn, inc_insn.reg0);
517 regno = REGNO (inc_insn.reg_res);
518 reg_next_def[regno] = mov_insn;
519 reg_next_use[regno] = NULL;
520 regno = REGNO (inc_insn.reg0);
521 reg_next_use[regno] = mov_insn;
522 df_recompute_luids (bb);
523 break;
525 case FORM_POST_INC:
526 regno = REGNO (inc_insn.reg_res);
527 if (reg_next_use[regno] == reg_next_inc_use[regno])
528 reg_next_inc_use[regno] = NULL;
530 /* Fallthru. */
531 case FORM_PRE_INC:
532 regno = REGNO (inc_insn.reg_res);
533 reg_next_def[regno] = mem_insn.insn;
534 reg_next_use[regno] = NULL;
536 break;
538 case FORM_POST_ADD:
539 gcc_assert (mov_insn);
540 emit_insn_before (mov_insn, mem_insn.insn);
541 move_dead_notes (mov_insn, inc_insn.insn, inc_insn.reg0);
543 /* Do not move anything to the mov insn because the instruction
544 pointer for the main iteration has not yet hit that. It is
545 still pointing to the mem insn. */
546 regno = REGNO (inc_insn.reg_res);
547 reg_next_def[regno] = mem_insn.insn;
548 reg_next_use[regno] = NULL;
550 regno = REGNO (inc_insn.reg0);
551 reg_next_use[regno] = mem_insn.insn;
552 if ((reg_next_use[regno] == reg_next_inc_use[regno])
553 || (reg_next_inc_use[regno] == inc_insn.insn))
554 reg_next_inc_use[regno] = NULL;
555 df_recompute_luids (bb);
556 break;
558 case FORM_last:
559 default:
560 gcc_unreachable ();
563 if (!inc_insn.reg1_is_const)
565 regno = REGNO (inc_insn.reg1);
566 reg_next_use[regno] = mem_insn.insn;
567 if ((reg_next_use[regno] == reg_next_inc_use[regno])
568 || (reg_next_inc_use[regno] == inc_insn.insn))
569 reg_next_inc_use[regno] = NULL;
572 delete_insn (inc_insn.insn);
574 if (dump_file && mov_insn)
576 fprintf (dump_file, "inserting mov ");
577 dump_insn_slim (dump_file, mov_insn);
580 /* Record that this insn has an implicit side effect. */
581 add_reg_note (mem_insn.insn, REG_INC, inc_reg);
583 if (dump_file)
585 fprintf (dump_file, "****success ");
586 dump_insn_slim (dump_file, mem_insn.insn);
589 return true;
593 /* Try to combine the instruction in INC_INSN with the instruction in
594 MEM_INSN. First the form is determined using the DECISION_TABLE
595 and the results of parsing the INC_INSN and the MEM_INSN.
596 Assuming the form is ok, a prototype new address is built which is
597 passed to ATTEMPT_CHANGE for final processing. */
599 static bool
600 try_merge (void)
602 enum gen_form gen_form;
603 rtx mem = *mem_insn.mem_loc;
604 rtx inc_reg = inc_insn.form == FORM_POST_ADD ?
605 inc_insn.reg_res : mem_insn.reg0;
607 /* The width of the mem being accessed. */
608 poly_int64 size = GET_MODE_SIZE (GET_MODE (mem));
609 rtx_insn *last_insn = NULL;
610 machine_mode reg_mode = GET_MODE (inc_reg);
612 switch (inc_insn.form)
614 case FORM_PRE_ADD:
615 case FORM_PRE_INC:
616 last_insn = mem_insn.insn;
617 break;
618 case FORM_POST_INC:
619 case FORM_POST_ADD:
620 last_insn = inc_insn.insn;
621 break;
622 case FORM_last:
623 default:
624 gcc_unreachable ();
627 /* Cannot handle auto inc of the stack. */
628 if (inc_reg == stack_pointer_rtx)
630 if (dump_file)
631 fprintf (dump_file, "cannot inc stack %d failure\n", REGNO (inc_reg));
632 return false;
635 /* Look to see if the inc register is dead after the memory
636 reference. If it is, do not do the combination. */
637 if (find_regno_note (last_insn, REG_DEAD, REGNO (inc_reg)))
639 if (dump_file)
640 fprintf (dump_file, "dead failure %d\n", REGNO (inc_reg));
641 return false;
644 mem_insn.reg1_state = (mem_insn.reg1_is_const)
645 ? set_inc_state (mem_insn.reg1_val, size) : INC_REG;
646 inc_insn.reg1_state = (inc_insn.reg1_is_const)
647 ? set_inc_state (inc_insn.reg1_val, size) : INC_REG;
649 /* Now get the form that we are generating. */
650 gen_form = decision_table
651 [inc_insn.reg1_state][mem_insn.reg1_state][inc_insn.form];
653 if (dbg_cnt (auto_inc_dec) == false)
654 return false;
656 switch (gen_form)
658 default:
659 case NOTHING:
660 return false;
662 case SIMPLE_PRE_INC: /* ++size */
663 if (dump_file)
664 fprintf (dump_file, "trying SIMPLE_PRE_INC\n");
665 return attempt_change (gen_rtx_PRE_INC (reg_mode, inc_reg), inc_reg);
667 case SIMPLE_POST_INC: /* size++ */
668 if (dump_file)
669 fprintf (dump_file, "trying SIMPLE_POST_INC\n");
670 return attempt_change (gen_rtx_POST_INC (reg_mode, inc_reg), inc_reg);
672 case SIMPLE_PRE_DEC: /* --size */
673 if (dump_file)
674 fprintf (dump_file, "trying SIMPLE_PRE_DEC\n");
675 return attempt_change (gen_rtx_PRE_DEC (reg_mode, inc_reg), inc_reg);
677 case SIMPLE_POST_DEC: /* size-- */
678 if (dump_file)
679 fprintf (dump_file, "trying SIMPLE_POST_DEC\n");
680 return attempt_change (gen_rtx_POST_DEC (reg_mode, inc_reg), inc_reg);
682 case DISP_PRE: /* ++con */
683 if (dump_file)
684 fprintf (dump_file, "trying DISP_PRE\n");
685 return attempt_change (gen_rtx_PRE_MODIFY (reg_mode,
686 inc_reg,
687 gen_rtx_PLUS (reg_mode,
688 inc_reg,
689 inc_insn.reg1)),
690 inc_reg);
692 case DISP_POST: /* con++ */
693 if (dump_file)
694 fprintf (dump_file, "trying POST_DISP\n");
695 return attempt_change (gen_rtx_POST_MODIFY (reg_mode,
696 inc_reg,
697 gen_rtx_PLUS (reg_mode,
698 inc_reg,
699 inc_insn.reg1)),
700 inc_reg);
702 case REG_PRE: /* ++reg */
703 if (dump_file)
704 fprintf (dump_file, "trying PRE_REG\n");
705 return attempt_change (gen_rtx_PRE_MODIFY (reg_mode,
706 inc_reg,
707 gen_rtx_PLUS (reg_mode,
708 inc_reg,
709 inc_insn.reg1)),
710 inc_reg);
712 case REG_POST: /* reg++ */
713 if (dump_file)
714 fprintf (dump_file, "trying POST_REG\n");
715 return attempt_change (gen_rtx_POST_MODIFY (reg_mode,
716 inc_reg,
717 gen_rtx_PLUS (reg_mode,
718 inc_reg,
719 inc_insn.reg1)),
720 inc_reg);
724 /* Return the next insn that uses (if reg_next_use is passed in
725 NEXT_ARRAY) or defines (if reg_next_def is passed in NEXT_ARRAY)
726 REGNO in BB. */
728 static rtx_insn *
729 get_next_ref (int regno, basic_block bb, rtx_insn **next_array)
731 rtx_insn *insn = next_array[regno];
733 /* Lazy about cleaning out the next_arrays. */
734 if (insn && BLOCK_FOR_INSN (insn) != bb)
736 next_array[regno] = NULL;
737 insn = NULL;
740 return insn;
744 /* Return true if INSN is of a form "a = b op c" where a and b are
745 regs. op is + if c is a reg and +|- if c is a const. Fill in
746 INC_INSN with what is found.
748 This function is called in two contexts, if BEFORE_MEM is true,
749 this is called for each insn in the basic block. If BEFORE_MEM is
750 false, it is called for the instruction in the block that uses the
751 index register for some memory reference that is currently being
752 processed. */
754 static bool
755 parse_add_or_inc (rtx_insn *insn, bool before_mem)
757 rtx pat = single_set (insn);
758 if (!pat)
759 return false;
761 /* Result must be single reg. */
762 if (!REG_P (SET_DEST (pat)))
763 return false;
765 if ((GET_CODE (SET_SRC (pat)) != PLUS)
766 && (GET_CODE (SET_SRC (pat)) != MINUS))
767 return false;
769 if (!REG_P (XEXP (SET_SRC (pat), 0)))
770 return false;
772 inc_insn.insn = insn;
773 inc_insn.pat = pat;
774 inc_insn.reg_res = SET_DEST (pat);
775 inc_insn.reg0 = XEXP (SET_SRC (pat), 0);
777 /* Block any auto increment of the frame pointer since it expands into
778 an addition and cannot be removed by copy propagation. */
779 if (inc_insn.reg0 == frame_pointer_rtx)
780 return false;
782 if (rtx_equal_p (inc_insn.reg_res, inc_insn.reg0))
783 inc_insn.form = before_mem ? FORM_PRE_INC : FORM_POST_INC;
784 else
785 inc_insn.form = before_mem ? FORM_PRE_ADD : FORM_POST_ADD;
787 if (CONST_INT_P (XEXP (SET_SRC (pat), 1)))
789 /* Process a = b + c where c is a const. */
790 inc_insn.reg1_is_const = true;
791 if (GET_CODE (SET_SRC (pat)) == PLUS)
793 inc_insn.reg1 = XEXP (SET_SRC (pat), 1);
794 inc_insn.reg1_val = INTVAL (inc_insn.reg1);
796 else
798 inc_insn.reg1_val = -INTVAL (XEXP (SET_SRC (pat), 1));
799 inc_insn.reg1 = GEN_INT (inc_insn.reg1_val);
801 return true;
803 else if ((HAVE_PRE_MODIFY_REG || HAVE_POST_MODIFY_REG)
804 && (REG_P (XEXP (SET_SRC (pat), 1)))
805 && GET_CODE (SET_SRC (pat)) == PLUS)
807 /* Process a = b + c where c is a reg. */
808 inc_insn.reg1 = XEXP (SET_SRC (pat), 1);
809 inc_insn.reg1_is_const = false;
811 if (inc_insn.form == FORM_PRE_INC
812 || inc_insn.form == FORM_POST_INC)
813 return true;
814 else if (rtx_equal_p (inc_insn.reg_res, inc_insn.reg1))
816 /* Reverse the two operands and turn *_ADD into *_INC since
817 a = c + a. */
818 std::swap (inc_insn.reg0, inc_insn.reg1);
819 inc_insn.form = before_mem ? FORM_PRE_INC : FORM_POST_INC;
820 return true;
822 else
823 return true;
826 return false;
830 /* A recursive function that checks all of the mem uses in
831 ADDRESS_OF_X to see if any single one of them is compatible with
832 what has been found in inc_insn. To avoid accidental matches, we
833 will only find MEMs with FINDREG, be it inc_insn.reg_res, be it
834 inc_insn.reg0.
836 -1 is returned for success. 0 is returned if nothing was found and
837 1 is returned for failure. */
839 static int
840 find_address (rtx *address_of_x, rtx findreg)
842 rtx x = *address_of_x;
843 enum rtx_code code = GET_CODE (x);
844 const char *const fmt = GET_RTX_FORMAT (code);
845 int i;
846 int value = 0;
847 int tem;
849 if (code == MEM && findreg == inc_insn.reg_res
850 && rtx_equal_p (XEXP (x, 0), inc_insn.reg_res))
852 /* Match with *reg_res. */
853 mem_insn.mem_loc = address_of_x;
854 mem_insn.reg0 = inc_insn.reg_res;
855 mem_insn.reg1_is_const = true;
856 mem_insn.reg1_val = 0;
857 mem_insn.reg1 = GEN_INT (0);
858 return -1;
860 if (code == MEM && inc_insn.reg1_is_const && inc_insn.reg0
861 && findreg == inc_insn.reg0
862 && rtx_equal_p (XEXP (x, 0), inc_insn.reg0))
864 /* Match with *reg0, assumed to be equivalent to
865 *(reg_res - reg1_val); callers must check whether this is the case. */
866 mem_insn.mem_loc = address_of_x;
867 mem_insn.reg0 = inc_insn.reg_res;
868 mem_insn.reg1_is_const = true;
869 mem_insn.reg1_val = -inc_insn.reg1_val;
870 mem_insn.reg1 = GEN_INT (mem_insn.reg1_val);
871 return -1;
873 if (code == MEM && findreg == inc_insn.reg_res
874 && GET_CODE (XEXP (x, 0)) == PLUS
875 && rtx_equal_p (XEXP (XEXP (x, 0), 0), inc_insn.reg_res))
877 rtx b = XEXP (XEXP (x, 0), 1);
878 mem_insn.mem_loc = address_of_x;
879 mem_insn.reg0 = inc_insn.reg_res;
880 mem_insn.reg1 = b;
881 mem_insn.reg1_is_const = inc_insn.reg1_is_const;
882 if (CONST_INT_P (b))
884 /* Match with *(reg0 + reg1) where reg1 is a const. */
885 HOST_WIDE_INT val = INTVAL (b);
886 if (inc_insn.reg1_is_const
887 && (inc_insn.reg1_val == val || inc_insn.reg1_val == -val))
889 mem_insn.reg1_val = val;
890 return -1;
893 else if (!inc_insn.reg1_is_const
894 && rtx_equal_p (inc_insn.reg1, b))
895 /* Match with *(reg0 + reg1). */
896 return -1;
899 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
901 /* If REG occurs inside a MEM used in a bit-field reference,
902 that is unacceptable. */
903 if (find_address (&XEXP (x, 0), findreg))
904 return 1;
907 if (x == inc_insn.reg_res)
908 return 1;
910 /* Time for some deep diving. */
911 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
913 if (fmt[i] == 'e')
915 tem = find_address (&XEXP (x, i), findreg);
916 /* If this is the first use, let it go so the rest of the
917 insn can be checked. */
918 if (value == 0)
919 value = tem;
920 else if (tem != 0)
921 /* More than one match was found. */
922 return 1;
924 else if (fmt[i] == 'E')
926 int j;
927 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
929 tem = find_address (&XVECEXP (x, i, j), findreg);
930 /* If this is the first use, let it go so the rest of
931 the insn can be checked. */
932 if (value == 0)
933 value = tem;
934 else if (tem != 0)
935 /* More than one match was found. */
936 return 1;
940 return value;
943 /* Once a suitable mem reference has been found and the MEM_INSN
944 structure has been filled in, FIND_INC is called to see if there is
945 a suitable add or inc insn that follows the mem reference and
946 determine if it is suitable to merge.
948 In the case where the MEM_INSN has two registers in the reference,
949 this function may be called recursively. The first time looking
950 for an add of the first register, and if that fails, looking for an
951 add of the second register. The FIRST_TRY parameter is used to
952 only allow the parameters to be reversed once. */
954 static bool
955 find_inc (bool first_try)
957 rtx_insn *insn;
958 basic_block bb = BLOCK_FOR_INSN (mem_insn.insn);
959 rtx_insn *other_insn;
960 df_ref def;
962 /* Make sure this reg appears only once in this insn. */
963 if (count_occurrences (PATTERN (mem_insn.insn), mem_insn.reg0, 1) != 1)
965 if (dump_file)
966 fprintf (dump_file, "mem count failure\n");
967 return false;
970 if (dump_file)
971 dump_mem_insn (dump_file);
973 /* Find the next use that is an inc. */
974 insn = get_next_ref (REGNO (mem_insn.reg0),
975 BLOCK_FOR_INSN (mem_insn.insn),
976 reg_next_inc_use);
977 if (!insn)
978 return false;
980 /* Even though we know the next use is an add or inc because it came
981 from the reg_next_inc_use, we must still reparse. */
982 if (!parse_add_or_inc (insn, false))
984 /* Next use was not an add. Look for one extra case. It could be
985 that we have:
987 *(a + b)
988 ...= a;
989 ...= b + a
991 if we reverse the operands in the mem ref we would
992 find this. Only try it once though. */
993 if (first_try && !mem_insn.reg1_is_const)
995 std::swap (mem_insn.reg0, mem_insn.reg1);
996 return find_inc (false);
998 else
999 return false;
1002 /* Need to assure that none of the operands of the inc instruction are
1003 assigned to by the mem insn. */
1004 FOR_EACH_INSN_DEF (def, mem_insn.insn)
1006 unsigned int regno = DF_REF_REGNO (def);
1007 if ((regno == REGNO (inc_insn.reg0))
1008 || (regno == REGNO (inc_insn.reg_res)))
1010 if (dump_file)
1011 fprintf (dump_file, "inc conflicts with store failure.\n");
1012 return false;
1014 if (!inc_insn.reg1_is_const && (regno == REGNO (inc_insn.reg1)))
1016 if (dump_file)
1017 fprintf (dump_file, "inc conflicts with store failure.\n");
1018 return false;
1022 if (dump_file)
1023 dump_inc_insn (dump_file);
1025 if (inc_insn.form == FORM_POST_ADD)
1027 /* Make sure that there is no insn that assigns to inc_insn.res
1028 between the mem_insn and the inc_insn. */
1029 rtx_insn *other_insn = get_next_ref (REGNO (inc_insn.reg_res),
1030 BLOCK_FOR_INSN (mem_insn.insn),
1031 reg_next_def);
1032 if (other_insn != inc_insn.insn)
1034 if (dump_file)
1035 fprintf (dump_file,
1036 "result of add is assigned to between mem and inc insns.\n");
1037 return false;
1040 other_insn = get_next_ref (REGNO (inc_insn.reg_res),
1041 BLOCK_FOR_INSN (mem_insn.insn),
1042 reg_next_use);
1043 if (other_insn
1044 && (other_insn != inc_insn.insn)
1045 && (DF_INSN_LUID (inc_insn.insn) > DF_INSN_LUID (other_insn)))
1047 if (dump_file)
1048 fprintf (dump_file,
1049 "result of add is used between mem and inc insns.\n");
1050 return false;
1053 /* For the post_add to work, the result_reg of the inc must not be
1054 used in the mem insn since this will become the new index
1055 register. */
1056 if (reg_overlap_mentioned_p (inc_insn.reg_res, PATTERN (mem_insn.insn)))
1058 if (dump_file)
1059 fprintf (dump_file, "base reg replacement failure.\n");
1060 return false;
1064 if (mem_insn.reg1_is_const)
1066 if (mem_insn.reg1_val == 0)
1068 if (!inc_insn.reg1_is_const)
1070 /* The mem looks like *r0 and the rhs of the add has two
1071 registers. */
1072 int luid = DF_INSN_LUID (inc_insn.insn);
1073 if (inc_insn.form == FORM_POST_ADD)
1075 /* The trick is that we are not going to increment r0,
1076 we are going to increment the result of the add insn.
1077 For this trick to be correct, the result reg of
1078 the inc must be a valid addressing reg. */
1079 addr_space_t as = MEM_ADDR_SPACE (*mem_insn.mem_loc);
1080 if (GET_MODE (inc_insn.reg_res)
1081 != targetm.addr_space.address_mode (as))
1083 if (dump_file)
1084 fprintf (dump_file, "base reg mode failure.\n");
1085 return false;
1088 /* We also need to make sure that the next use of
1089 inc result is after the inc. */
1090 other_insn
1091 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_use);
1092 if (other_insn && luid > DF_INSN_LUID (other_insn))
1093 return false;
1095 if (!rtx_equal_p (mem_insn.reg0, inc_insn.reg0))
1096 std::swap (inc_insn.reg0, inc_insn.reg1);
1099 other_insn
1100 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1101 if (other_insn && luid > DF_INSN_LUID (other_insn))
1102 return false;
1105 /* Both the inc/add and the mem have a constant. Need to check
1106 that the constants are ok. */
1107 else if ((mem_insn.reg1_val != inc_insn.reg1_val)
1108 && (mem_insn.reg1_val != -inc_insn.reg1_val))
1109 return false;
1111 else
1113 /* The mem insn is of the form *(a + b) where a and b are both
1114 regs. It may be that in order to match the add or inc we
1115 need to treat it as if it was *(b + a). It may also be that
1116 the add is of the form a + c where c does not match b and
1117 then we just abandon this. */
1119 int luid = DF_INSN_LUID (inc_insn.insn);
1120 rtx_insn *other_insn;
1122 /* Make sure this reg appears only once in this insn. */
1123 if (count_occurrences (PATTERN (mem_insn.insn), mem_insn.reg1, 1) != 1)
1124 return false;
1126 if (inc_insn.form == FORM_POST_ADD)
1128 /* For this trick to be correct, the result reg of the inc
1129 must be a valid addressing reg. */
1130 addr_space_t as = MEM_ADDR_SPACE (*mem_insn.mem_loc);
1131 if (GET_MODE (inc_insn.reg_res)
1132 != targetm.addr_space.address_mode (as))
1134 if (dump_file)
1135 fprintf (dump_file, "base reg mode failure.\n");
1136 return false;
1139 if (rtx_equal_p (mem_insn.reg0, inc_insn.reg0))
1141 if (!rtx_equal_p (mem_insn.reg1, inc_insn.reg1))
1143 /* See comment above on find_inc (false) call. */
1144 if (first_try)
1146 std::swap (mem_insn.reg0, mem_insn.reg1);
1147 return find_inc (false);
1149 else
1150 return false;
1153 /* Need to check that there are no assignments to b
1154 before the add insn. */
1155 other_insn
1156 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1157 if (other_insn && luid > DF_INSN_LUID (other_insn))
1158 return false;
1159 /* All ok for the next step. */
1161 else
1163 /* We know that mem_insn.reg0 must equal inc_insn.reg1
1164 or else we would not have found the inc insn. */
1165 std::swap (mem_insn.reg0, mem_insn.reg1);
1166 if (!rtx_equal_p (mem_insn.reg0, inc_insn.reg0))
1168 /* See comment above on find_inc (false) call. */
1169 if (first_try)
1170 return find_inc (false);
1171 else
1172 return false;
1174 /* To have gotten here know that.
1175 *(b + a)
1177 ... = (b + a)
1179 We also know that the lhs of the inc is not b or a. We
1180 need to make sure that there are no assignments to b
1181 between the mem ref and the inc. */
1183 other_insn
1184 = get_next_ref (REGNO (inc_insn.reg0), bb, reg_next_def);
1185 if (other_insn && luid > DF_INSN_LUID (other_insn))
1186 return false;
1189 /* Need to check that the next use of the add result is later than
1190 add insn since this will be the reg incremented. */
1191 other_insn
1192 = get_next_ref (REGNO (inc_insn.reg_res), bb, reg_next_use);
1193 if (other_insn && luid > DF_INSN_LUID (other_insn))
1194 return false;
1196 else /* FORM_POST_INC. There is less to check here because we
1197 know that operands must line up. */
1199 if (!rtx_equal_p (mem_insn.reg1, inc_insn.reg1))
1200 /* See comment above on find_inc (false) call. */
1202 if (first_try)
1204 std::swap (mem_insn.reg0, mem_insn.reg1);
1205 return find_inc (false);
1207 else
1208 return false;
1211 /* To have gotten here know that.
1212 *(a + b)
1214 ... = (a + b)
1216 We also know that the lhs of the inc is not b. We need to make
1217 sure that there are no assignments to b between the mem ref and
1218 the inc. */
1219 other_insn
1220 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1221 if (other_insn && luid > DF_INSN_LUID (other_insn))
1222 return false;
1226 if (inc_insn.form == FORM_POST_INC)
1228 other_insn
1229 = get_next_ref (REGNO (inc_insn.reg0), bb, reg_next_use);
1230 /* When we found inc_insn, we were looking for the
1231 next add or inc, not the next insn that used the
1232 reg. Because we are going to increment the reg
1233 in this form, we need to make sure that there
1234 were no intervening uses of reg. */
1235 if (inc_insn.insn != other_insn)
1236 return false;
1239 return try_merge ();
1243 /* A recursive function that walks ADDRESS_OF_X to find all of the mem
1244 uses in pat that could be used as an auto inc or dec. It then
1245 calls FIND_INC for each one. */
1247 static bool
1248 find_mem (rtx *address_of_x)
1250 rtx x = *address_of_x;
1251 enum rtx_code code = GET_CODE (x);
1252 const char *const fmt = GET_RTX_FORMAT (code);
1253 int i;
1255 if (code == MEM && REG_P (XEXP (x, 0)))
1257 /* Match with *reg0. */
1258 mem_insn.mem_loc = address_of_x;
1259 mem_insn.reg0 = XEXP (x, 0);
1260 mem_insn.reg1_is_const = true;
1261 mem_insn.reg1_val = 0;
1262 mem_insn.reg1 = GEN_INT (0);
1263 if (find_inc (true))
1264 return true;
1266 if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
1267 && REG_P (XEXP (XEXP (x, 0), 0)))
1269 rtx reg1 = XEXP (XEXP (x, 0), 1);
1270 mem_insn.mem_loc = address_of_x;
1271 mem_insn.reg0 = XEXP (XEXP (x, 0), 0);
1272 mem_insn.reg1 = reg1;
1273 if (CONST_INT_P (reg1))
1275 mem_insn.reg1_is_const = true;
1276 /* Match with *(reg0 + c) where c is a const. */
1277 mem_insn.reg1_val = INTVAL (reg1);
1278 if (find_inc (true))
1279 return true;
1281 else if (REG_P (reg1))
1283 /* Match with *(reg0 + reg1). */
1284 mem_insn.reg1_is_const = false;
1285 if (find_inc (true))
1286 return true;
1290 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
1292 /* If REG occurs inside a MEM used in a bit-field reference,
1293 that is unacceptable. */
1294 return false;
1297 /* Time for some deep diving. */
1298 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1300 if (fmt[i] == 'e')
1302 if (find_mem (&XEXP (x, i)))
1303 return true;
1305 else if (fmt[i] == 'E')
1307 int j;
1308 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1309 if (find_mem (&XVECEXP (x, i, j)))
1310 return true;
1313 return false;
1317 /* Try to combine all incs and decs by constant values with memory
1318 references in BB. */
1320 static void
1321 merge_in_block (int max_reg, basic_block bb)
1323 rtx_insn *insn;
1324 rtx_insn *curr;
1325 int success_in_block = 0;
1327 if (dump_file)
1328 fprintf (dump_file, "\n\nstarting bb %d\n", bb->index);
1330 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, curr)
1332 bool insn_is_add_or_inc = true;
1334 if (!NONDEBUG_INSN_P (insn))
1335 continue;
1337 /* This continue is deliberate. We do not want the uses of the
1338 jump put into reg_next_use because it is not considered safe to
1339 combine a preincrement with a jump. */
1340 if (JUMP_P (insn))
1341 continue;
1343 if (dump_file)
1344 dump_insn_slim (dump_file, insn);
1346 /* Does this instruction increment or decrement a register? */
1347 if (parse_add_or_inc (insn, true))
1349 int regno = REGNO (inc_insn.reg_res);
1350 /* Cannot handle case where there are three separate regs
1351 before a mem ref. Too many moves would be needed to be
1352 profitable. */
1353 if ((inc_insn.form == FORM_PRE_INC) || inc_insn.reg1_is_const)
1355 mem_insn.insn = get_next_ref (regno, bb, reg_next_use);
1356 if (mem_insn.insn)
1358 bool ok = true;
1359 if (!inc_insn.reg1_is_const)
1361 /* We are only here if we are going to try a
1362 HAVE_*_MODIFY_REG type transformation. c is a
1363 reg and we must sure that the path from the
1364 inc_insn to the mem_insn.insn is both def and use
1365 clear of c because the inc insn is going to move
1366 into the mem_insn.insn. */
1367 int luid = DF_INSN_LUID (mem_insn.insn);
1368 rtx_insn *other_insn
1369 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_use);
1371 if (other_insn && luid > DF_INSN_LUID (other_insn))
1372 ok = false;
1374 other_insn
1375 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1377 if (other_insn && luid > DF_INSN_LUID (other_insn))
1378 ok = false;
1381 if (dump_file)
1382 dump_inc_insn (dump_file);
1384 if (ok && find_address (&PATTERN (mem_insn.insn),
1385 inc_insn.reg_res) == -1)
1387 if (dump_file)
1388 dump_mem_insn (dump_file);
1389 if (try_merge ())
1391 success_in_block++;
1392 insn_is_add_or_inc = false;
1397 if (insn_is_add_or_inc
1398 /* find_address will only recognize an address
1399 with a reg0 that's not reg_res when
1400 reg1_is_const, so cut it off early if we
1401 already know it won't match. */
1402 && inc_insn.reg1_is_const
1403 && inc_insn.reg0
1404 && inc_insn.reg0 != inc_insn.reg_res)
1406 /* If we identified an inc_insn that uses two
1407 different pseudos, it's of the form
1409 (set reg_res (plus reg0 reg1))
1411 where reg1 is a constant (*).
1413 The next use of reg_res was not idenfied by
1414 find_address as a mem_insn that we could turn
1415 into auto-inc, so see if we find a suitable
1416 MEM in the next use of reg0, as long as it's
1417 before any subsequent use of reg_res:
1419 ... (mem (... reg0 ...)) ...
1421 ... reg_res ...
1423 In this case, we can turn the plus into a
1424 copy, and the reg0 in the MEM address into a
1425 post_inc of reg_res:
1427 (set reg_res reg0)
1429 ... (mem (... (post_add reg_res reg1) ...)) ...
1431 reg_res will then have the correct value at
1432 subsequent uses, and reg0 will remain
1433 unchanged.
1435 (*) We could support non-const reg1, but then
1436 we'd have to check that reg1 remains
1437 unchanged all the way to the modified MEM,
1438 and we'd have to extend find_address to
1439 represent a non-const negated reg1. */
1440 regno = REGNO (inc_insn.reg0);
1441 rtx_insn *reg0_use = get_next_ref (regno, bb,
1442 reg_next_use);
1444 /* Give up if the next use of reg0 is after the next
1445 use of reg_res (same insn is ok; we might have
1446 found a MEM with reg_res before, and that failed,
1447 but now we try reg0, which might work), or defs
1448 of reg_res (same insn is not ok, we'd introduce
1449 another def in the same insn) or reg0. */
1450 if (reg0_use)
1452 int luid = DF_INSN_LUID (reg0_use);
1454 /* It might seem pointless to introduce an
1455 auto-inc if there's no subsequent use of
1456 reg_res (i.e., mem_insn.insn == NULL), but
1457 the next use might be in the next iteration
1458 of a loop, and it won't hurt if we make the
1459 change even if it's not needed. */
1460 if (mem_insn.insn
1461 && luid > DF_INSN_LUID (mem_insn.insn))
1462 reg0_use = NULL;
1464 rtx_insn *other_insn
1465 = get_next_ref (REGNO (inc_insn.reg_res), bb,
1466 reg_next_def);
1468 if (other_insn && luid >= DF_INSN_LUID (other_insn))
1469 reg0_use = NULL;
1471 other_insn
1472 = get_next_ref (REGNO (inc_insn.reg0), bb,
1473 reg_next_def);
1475 if (other_insn && luid > DF_INSN_LUID (other_insn))
1476 reg0_use = NULL;
1479 mem_insn.insn = reg0_use;
1481 if (mem_insn.insn
1482 && find_address (&PATTERN (mem_insn.insn),
1483 inc_insn.reg0) == -1)
1485 if (dump_file)
1486 dump_mem_insn (dump_file);
1487 if (try_merge ())
1489 success_in_block++;
1490 insn_is_add_or_inc = false;
1496 else
1498 insn_is_add_or_inc = false;
1499 mem_insn.insn = insn;
1500 if (find_mem (&PATTERN (insn)))
1501 success_in_block++;
1504 /* If the inc insn was merged with a mem, the inc insn is gone
1505 and there is noting to update. */
1506 if (df_insn_info *insn_info = DF_INSN_INFO_GET (insn))
1508 df_ref def, use;
1510 /* Need to update next use. */
1511 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1513 reg_next_use[DF_REF_REGNO (def)] = NULL;
1514 reg_next_inc_use[DF_REF_REGNO (def)] = NULL;
1515 reg_next_def[DF_REF_REGNO (def)] = insn;
1518 FOR_EACH_INSN_INFO_USE (use, insn_info)
1520 reg_next_use[DF_REF_REGNO (use)] = insn;
1521 if (insn_is_add_or_inc)
1522 reg_next_inc_use[DF_REF_REGNO (use)] = insn;
1523 else
1524 reg_next_inc_use[DF_REF_REGNO (use)] = NULL;
1527 else if (dump_file)
1528 fprintf (dump_file, "skipping update of deleted insn %d\n",
1529 INSN_UID (insn));
1532 /* If we were successful, try again. There may have been several
1533 opportunities that were interleaved. This is rare but
1534 gcc.c-torture/compile/pr17273.c actually exhibits this. */
1535 if (success_in_block)
1537 /* In this case, we must clear these vectors since the trick of
1538 testing if the stale insn in the block will not work. */
1539 memset (reg_next_use, 0, max_reg * sizeof (rtx));
1540 memset (reg_next_inc_use, 0, max_reg * sizeof (rtx));
1541 memset (reg_next_def, 0, max_reg * sizeof (rtx));
1542 df_recompute_luids (bb);
1543 merge_in_block (max_reg, bb);
1547 /* Discover auto-inc auto-dec instructions. */
1549 namespace {
1551 const pass_data pass_data_inc_dec =
1553 RTL_PASS, /* type */
1554 "auto_inc_dec", /* name */
1555 OPTGROUP_NONE, /* optinfo_flags */
1556 TV_AUTO_INC_DEC, /* tv_id */
1557 0, /* properties_required */
1558 0, /* properties_provided */
1559 0, /* properties_destroyed */
1560 0, /* todo_flags_start */
1561 TODO_df_finish, /* todo_flags_finish */
1564 class pass_inc_dec : public rtl_opt_pass
1566 public:
1567 pass_inc_dec (gcc::context *ctxt)
1568 : rtl_opt_pass (pass_data_inc_dec, ctxt)
1571 /* opt_pass methods: */
1572 virtual bool gate (function *)
1574 if (!AUTO_INC_DEC)
1575 return false;
1577 return (optimize > 0 && flag_auto_inc_dec);
1581 unsigned int execute (function *);
1583 }; // class pass_inc_dec
1585 unsigned int
1586 pass_inc_dec::execute (function *fun ATTRIBUTE_UNUSED)
1588 if (!AUTO_INC_DEC)
1589 return 0;
1591 basic_block bb;
1592 int max_reg = max_reg_num ();
1594 if (!initialized)
1595 init_decision_table ();
1597 mem_tmp = gen_rtx_MEM (Pmode, NULL_RTX);
1599 df_note_add_problem ();
1600 df_analyze ();
1602 reg_next_use = XCNEWVEC (rtx_insn *, max_reg);
1603 reg_next_inc_use = XCNEWVEC (rtx_insn *, max_reg);
1604 reg_next_def = XCNEWVEC (rtx_insn *, max_reg);
1605 FOR_EACH_BB_FN (bb, fun)
1606 merge_in_block (max_reg, bb);
1608 free (reg_next_use);
1609 free (reg_next_inc_use);
1610 free (reg_next_def);
1612 mem_tmp = NULL;
1614 return 0;
1617 } // anon namespace
1619 rtl_opt_pass *
1620 make_pass_inc_dec (gcc::context *ctxt)
1622 return new pass_inc_dec (ctxt);