1 /* Discovery of auto-inc and auto-dec instructions.
2 Copyright (C) 2006-2015 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
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
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/>. */
23 #include "coretypes.h"
31 #include "insn-config.h"
35 #include "diagnostic-core.h"
45 #include "tree-pass.h"
49 /* This pass was originally removed from flow.c. However there is
50 almost nothing that remains of that code.
52 There are (4) basic forms that are matched:
81 (For this case to be true, b must not be assigned or used between
82 the *a and the assignment to b. B must also be a Pmode reg.)
100 There are three types of values of c.
102 1) c is a constant equal to the width of the value being accessed by
103 the pointer. This is useful for machines that have
104 HAVE_PRE_INCREMENT, HAVE_POST_INCREMENT, HAVE_PRE_DECREMENT or
105 HAVE_POST_DECREMENT defined.
107 2) c is a constant not equal to the width of the value being accessed
108 by the pointer. This is useful for machines that have
109 HAVE_PRE_MODIFY_DISP, HAVE_POST_MODIFY_DISP defined.
111 3) c is a register. This is useful for machines that have
112 HAVE_PRE_MODIFY_REG, HAVE_POST_MODIFY_REG
114 The is one special case: if a already had an offset equal to it +-
115 its width and that offset is equal to -c when the increment was
116 before the ref or +c if the increment was after the ref, then if we
117 can do the combination but switch the pre/post bit. */
129 /* The states of the second operands of mem refs and inc insns. If no
130 second operand of the mem_ref was found, it is assumed to just be
131 ZERO. SIZE is the size of the mode accessed in the memref. The
132 ANY is used for constants that are not +-size or 0. REG is used if
133 the forms are reg1 + reg2. */
138 INC_NEG_SIZE
, /* == +size */
139 INC_POS_SIZE
, /* == -size */
140 INC_NEG_ANY
, /* == some -constant */
141 INC_POS_ANY
, /* == some +constant */
142 INC_REG
, /* == some register */
146 /* The eight forms that pre/post inc/dec can take. */
150 SIMPLE_PRE_INC
, /* ++size */
151 SIMPLE_POST_INC
, /* size++ */
152 SIMPLE_PRE_DEC
, /* --size */
153 SIMPLE_POST_DEC
, /* size-- */
154 DISP_PRE
, /* ++con */
155 DISP_POST
, /* con++ */
160 /* Tmp mem rtx for use in cost modeling. */
163 static enum inc_state
164 set_inc_state (HOST_WIDE_INT val
, int size
)
169 return (val
== -size
) ? INC_NEG_SIZE
: INC_NEG_ANY
;
171 return (val
== size
) ? INC_POS_SIZE
: INC_POS_ANY
;
174 /* The DECISION_TABLE that describes what form, if any, the increment
175 or decrement will take. It is a three dimensional table. The first
176 index is the type of constant or register found as the second
177 operand of the inc insn. The second index is the type of constant
178 or register found as the second operand of the memory reference (if
179 no second operand exists, 0 is used). The third index is the form
180 and location (relative to the mem reference) of inc insn. */
182 static bool initialized
= false;
183 static enum gen_form decision_table
[INC_last
][INC_last
][FORM_last
];
186 init_decision_table (void)
190 if (HAVE_PRE_INCREMENT
|| HAVE_PRE_MODIFY_DISP
)
192 /* Prefer the simple form if both are available. */
193 value
= (HAVE_PRE_INCREMENT
) ? SIMPLE_PRE_INC
: DISP_PRE
;
195 decision_table
[INC_POS_SIZE
][INC_ZERO
][FORM_PRE_ADD
] = value
;
196 decision_table
[INC_POS_SIZE
][INC_ZERO
][FORM_PRE_INC
] = value
;
198 decision_table
[INC_POS_SIZE
][INC_POS_SIZE
][FORM_POST_ADD
] = value
;
199 decision_table
[INC_POS_SIZE
][INC_POS_SIZE
][FORM_POST_INC
] = value
;
202 if (HAVE_POST_INCREMENT
|| HAVE_POST_MODIFY_DISP
)
204 /* Prefer the simple form if both are available. */
205 value
= (HAVE_POST_INCREMENT
) ? SIMPLE_POST_INC
: DISP_POST
;
207 decision_table
[INC_POS_SIZE
][INC_ZERO
][FORM_POST_ADD
] = value
;
208 decision_table
[INC_POS_SIZE
][INC_ZERO
][FORM_POST_INC
] = value
;
210 decision_table
[INC_POS_SIZE
][INC_NEG_SIZE
][FORM_PRE_ADD
] = value
;
211 decision_table
[INC_POS_SIZE
][INC_NEG_SIZE
][FORM_PRE_INC
] = value
;
214 if (HAVE_PRE_DECREMENT
|| HAVE_PRE_MODIFY_DISP
)
216 /* Prefer the simple form if both are available. */
217 value
= (HAVE_PRE_DECREMENT
) ? SIMPLE_PRE_DEC
: DISP_PRE
;
219 decision_table
[INC_NEG_SIZE
][INC_ZERO
][FORM_PRE_ADD
] = value
;
220 decision_table
[INC_NEG_SIZE
][INC_ZERO
][FORM_PRE_INC
] = value
;
222 decision_table
[INC_NEG_SIZE
][INC_NEG_SIZE
][FORM_POST_ADD
] = value
;
223 decision_table
[INC_NEG_SIZE
][INC_NEG_SIZE
][FORM_POST_INC
] = value
;
226 if (HAVE_POST_DECREMENT
|| HAVE_POST_MODIFY_DISP
)
228 /* Prefer the simple form if both are available. */
229 value
= (HAVE_POST_DECREMENT
) ? SIMPLE_POST_DEC
: DISP_POST
;
231 decision_table
[INC_NEG_SIZE
][INC_ZERO
][FORM_POST_ADD
] = value
;
232 decision_table
[INC_NEG_SIZE
][INC_ZERO
][FORM_POST_INC
] = value
;
234 decision_table
[INC_NEG_SIZE
][INC_POS_SIZE
][FORM_PRE_ADD
] = value
;
235 decision_table
[INC_NEG_SIZE
][INC_POS_SIZE
][FORM_PRE_INC
] = value
;
238 if (HAVE_PRE_MODIFY_DISP
)
240 decision_table
[INC_POS_ANY
][INC_ZERO
][FORM_PRE_ADD
] = DISP_PRE
;
241 decision_table
[INC_POS_ANY
][INC_ZERO
][FORM_PRE_INC
] = DISP_PRE
;
243 decision_table
[INC_POS_ANY
][INC_POS_ANY
][FORM_POST_ADD
] = DISP_PRE
;
244 decision_table
[INC_POS_ANY
][INC_POS_ANY
][FORM_POST_INC
] = DISP_PRE
;
246 decision_table
[INC_NEG_ANY
][INC_ZERO
][FORM_PRE_ADD
] = DISP_PRE
;
247 decision_table
[INC_NEG_ANY
][INC_ZERO
][FORM_PRE_INC
] = DISP_PRE
;
249 decision_table
[INC_NEG_ANY
][INC_NEG_ANY
][FORM_POST_ADD
] = DISP_PRE
;
250 decision_table
[INC_NEG_ANY
][INC_NEG_ANY
][FORM_POST_INC
] = DISP_PRE
;
253 if (HAVE_POST_MODIFY_DISP
)
255 decision_table
[INC_POS_ANY
][INC_ZERO
][FORM_POST_ADD
] = DISP_POST
;
256 decision_table
[INC_POS_ANY
][INC_ZERO
][FORM_POST_INC
] = DISP_POST
;
258 decision_table
[INC_POS_ANY
][INC_NEG_ANY
][FORM_PRE_ADD
] = DISP_POST
;
259 decision_table
[INC_POS_ANY
][INC_NEG_ANY
][FORM_PRE_INC
] = DISP_POST
;
261 decision_table
[INC_NEG_ANY
][INC_ZERO
][FORM_POST_ADD
] = DISP_POST
;
262 decision_table
[INC_NEG_ANY
][INC_ZERO
][FORM_POST_INC
] = DISP_POST
;
264 decision_table
[INC_NEG_ANY
][INC_POS_ANY
][FORM_PRE_ADD
] = DISP_POST
;
265 decision_table
[INC_NEG_ANY
][INC_POS_ANY
][FORM_PRE_INC
] = DISP_POST
;
268 /* This is much simpler than the other cases because we do not look
269 for the reg1-reg2 case. Note that we do not have a INC_POS_REG
270 and INC_NEG_REG states. Most of the use of such states would be
271 on a target that had an R1 - R2 update address form.
273 There is the remote possibility that you could also catch a = a +
274 b; *(a - b) as a postdecrement of (a + b). However, it is
275 unclear if *(a - b) would ever be generated on a machine that did
276 not have that kind of addressing mode. The IA-64 and RS6000 will
277 not do this, and I cannot speak for any other. If any
278 architecture does have an a-b update for, these cases should be
280 if (HAVE_PRE_MODIFY_REG
)
282 decision_table
[INC_REG
][INC_ZERO
][FORM_PRE_ADD
] = REG_PRE
;
283 decision_table
[INC_REG
][INC_ZERO
][FORM_PRE_INC
] = REG_PRE
;
285 decision_table
[INC_REG
][INC_REG
][FORM_POST_ADD
] = REG_PRE
;
286 decision_table
[INC_REG
][INC_REG
][FORM_POST_INC
] = REG_PRE
;
289 if (HAVE_POST_MODIFY_REG
)
291 decision_table
[INC_REG
][INC_ZERO
][FORM_POST_ADD
] = REG_POST
;
292 decision_table
[INC_REG
][INC_ZERO
][FORM_POST_INC
] = REG_POST
;
298 /* Parsed fields of an inc insn of the form "reg_res = reg0+reg1" or
299 "reg_res = reg0+c". */
301 static struct inc_insn
303 rtx_insn
*insn
; /* The insn being parsed. */
304 rtx pat
; /* The pattern of the insn. */
305 bool reg1_is_const
; /* True if reg1 is const, false if reg1 is a reg. */
310 enum inc_state reg1_state
;/* The form of the const if reg1 is a const. */
311 HOST_WIDE_INT reg1_val
;/* Value if reg1 is const. */
315 /* Dump the parsed inc insn to FILE. */
318 dump_inc_insn (FILE *file
)
320 const char *f
= ((inc_insn
.form
== FORM_PRE_ADD
)
321 || (inc_insn
.form
== FORM_PRE_INC
)) ? "pre" : "post";
323 dump_insn_slim (file
, inc_insn
.insn
);
325 switch (inc_insn
.form
)
329 if (inc_insn
.reg1_is_const
)
330 fprintf (file
, "found %s add(%d) r[%d]=r[%d]+%d\n",
331 f
, INSN_UID (inc_insn
.insn
),
332 REGNO (inc_insn
.reg_res
),
333 REGNO (inc_insn
.reg0
), (int) inc_insn
.reg1_val
);
335 fprintf (file
, "found %s add(%d) r[%d]=r[%d]+r[%d]\n",
336 f
, INSN_UID (inc_insn
.insn
),
337 REGNO (inc_insn
.reg_res
),
338 REGNO (inc_insn
.reg0
), REGNO (inc_insn
.reg1
));
343 if (inc_insn
.reg1_is_const
)
344 fprintf (file
, "found %s inc(%d) r[%d]+=%d\n",
345 f
, INSN_UID (inc_insn
.insn
),
346 REGNO (inc_insn
.reg_res
), (int) inc_insn
.reg1_val
);
348 fprintf (file
, "found %s inc(%d) r[%d]+=r[%d]\n",
349 f
, INSN_UID (inc_insn
.insn
),
350 REGNO (inc_insn
.reg_res
), REGNO (inc_insn
.reg1
));
359 /* Parsed fields of a mem ref of the form "*(reg0+reg1)" or "*(reg0+c)". */
361 static struct mem_insn
363 rtx_insn
*insn
; /* The insn being parsed. */
364 rtx pat
; /* The pattern of the insn. */
365 rtx
*mem_loc
; /* The address of the field that holds the mem */
366 /* that is to be replaced. */
367 bool reg1_is_const
; /* True if reg1 is const, false if reg1 is a reg. */
369 rtx reg1
; /* This is either a reg or a const depending on
371 enum inc_state reg1_state
;/* The form of the const if reg1 is a const. */
372 HOST_WIDE_INT reg1_val
;/* Value if reg1 is const. */
376 /* Dump the parsed mem insn to FILE. */
379 dump_mem_insn (FILE *file
)
381 dump_insn_slim (file
, mem_insn
.insn
);
383 if (mem_insn
.reg1_is_const
)
384 fprintf (file
, "found mem(%d) *(r[%d]+%d)\n",
385 INSN_UID (mem_insn
.insn
),
386 REGNO (mem_insn
.reg0
), (int) mem_insn
.reg1_val
);
388 fprintf (file
, "found mem(%d) *(r[%d]+r[%d])\n",
389 INSN_UID (mem_insn
.insn
),
390 REGNO (mem_insn
.reg0
), REGNO (mem_insn
.reg1
));
394 /* The following three arrays contain pointers to instructions. They
395 are indexed by REGNO. At any point in the basic block where we are
396 looking these three arrays contain, respectively, the next insn
397 that uses REGNO, the next inc or add insn that uses REGNO and the
398 next insn that sets REGNO.
400 The arrays are not cleared when we move from block to block so
401 whenever an insn is retrieved from these arrays, it's block number
402 must be compared with the current block.
405 static rtx_insn
**reg_next_use
= NULL
;
406 static rtx_insn
**reg_next_inc_use
= NULL
;
407 static rtx_insn
**reg_next_def
= NULL
;
410 /* Move dead note that match PATTERN to TO_INSN from FROM_INSN. We do
411 not really care about moving any other notes from the inc or add
412 insn. Moving the REG_EQUAL and REG_EQUIV is clearly wrong and it
413 does not appear that there are any other kinds of relevant notes. */
416 move_dead_notes (rtx_insn
*to_insn
, rtx_insn
*from_insn
, rtx pattern
)
420 rtx prev_note
= NULL
;
422 for (note
= REG_NOTES (from_insn
); note
; note
= next_note
)
424 next_note
= XEXP (note
, 1);
426 if ((REG_NOTE_KIND (note
) == REG_DEAD
)
427 && pattern
== XEXP (note
, 0))
429 XEXP (note
, 1) = REG_NOTES (to_insn
);
430 REG_NOTES (to_insn
) = note
;
432 XEXP (prev_note
, 1) = next_note
;
434 REG_NOTES (from_insn
) = next_note
;
436 else prev_note
= note
;
441 /* Create a mov insn DEST_REG <- SRC_REG and insert it before
445 insert_move_insn_before (rtx_insn
*next_insn
, rtx dest_reg
, rtx src_reg
)
450 emit_move_insn (dest_reg
, src_reg
);
451 insns
= get_insns ();
453 emit_insn_before (insns
, next_insn
);
458 /* Change mem_insn.mem_loc so that uses NEW_ADDR which has an
459 increment of INC_REG. To have reached this point, the change is a
460 legitimate one from a dataflow point of view. The only questions
461 are is this a valid change to the instruction and is this a
462 profitable change to the instruction. */
465 attempt_change (rtx new_addr
, rtx inc_reg
)
467 /* There are four cases: For the two cases that involve an add
468 instruction, we are going to have to delete the add and insert a
469 mov. We are going to assume that the mov is free. This is
470 fairly early in the backend and there are a lot of opportunities
471 for removing that move later. In particular, there is the case
472 where the move may be dead, this is what dead code elimination
473 passes are for. The two cases where we have an inc insn will be
476 basic_block bb
= BLOCK_FOR_INSN (mem_insn
.insn
);
477 rtx_insn
*mov_insn
= NULL
;
479 rtx mem
= *mem_insn
.mem_loc
;
480 machine_mode mode
= GET_MODE (mem
);
484 bool speed
= optimize_bb_for_speed_p (bb
);
486 PUT_MODE (mem_tmp
, mode
);
487 XEXP (mem_tmp
, 0) = new_addr
;
489 old_cost
= (set_src_cost (mem
, mode
, speed
)
490 + set_rtx_cost (PATTERN (inc_insn
.insn
), speed
));
491 new_cost
= set_src_cost (mem_tmp
, mode
, speed
);
493 /* The first item of business is to see if this is profitable. */
494 if (old_cost
< new_cost
)
497 fprintf (dump_file
, "cost failure old=%d new=%d\n", old_cost
, new_cost
);
501 /* Jump through a lot of hoops to keep the attributes up to date. We
502 do not want to call one of the change address variants that take
503 an offset even though we know the offset in many cases. These
504 assume you are changing where the address is pointing by the
506 new_mem
= replace_equiv_address_nv (mem
, new_addr
);
507 if (! validate_change (mem_insn
.insn
, mem_insn
.mem_loc
, new_mem
, 0))
510 fprintf (dump_file
, "validation failure\n");
514 /* From here to the end of the function we are committed to the
515 change, i.e. nothing fails. Generate any necessary movs, move
516 any regnotes, and fix up the reg_next_{use,inc_use,def}. */
517 switch (inc_insn
.form
)
520 /* Replace the addition with a move. Do it at the location of
521 the addition since the operand of the addition may change
522 before the memory reference. */
523 mov_insn
= insert_move_insn_before (inc_insn
.insn
,
524 inc_insn
.reg_res
, inc_insn
.reg0
);
525 move_dead_notes (mov_insn
, inc_insn
.insn
, inc_insn
.reg0
);
527 regno
= REGNO (inc_insn
.reg_res
);
528 reg_next_def
[regno
] = mov_insn
;
529 reg_next_use
[regno
] = NULL
;
530 regno
= REGNO (inc_insn
.reg0
);
531 reg_next_use
[regno
] = mov_insn
;
532 df_recompute_luids (bb
);
536 regno
= REGNO (inc_insn
.reg_res
);
537 if (reg_next_use
[regno
] == reg_next_inc_use
[regno
])
538 reg_next_inc_use
[regno
] = NULL
;
542 regno
= REGNO (inc_insn
.reg_res
);
543 reg_next_def
[regno
] = mem_insn
.insn
;
544 reg_next_use
[regno
] = NULL
;
549 mov_insn
= insert_move_insn_before (mem_insn
.insn
,
550 inc_insn
.reg_res
, inc_insn
.reg0
);
551 move_dead_notes (mov_insn
, inc_insn
.insn
, inc_insn
.reg0
);
553 /* Do not move anything to the mov insn because the instruction
554 pointer for the main iteration has not yet hit that. It is
555 still pointing to the mem insn. */
556 regno
= REGNO (inc_insn
.reg_res
);
557 reg_next_def
[regno
] = mem_insn
.insn
;
558 reg_next_use
[regno
] = NULL
;
560 regno
= REGNO (inc_insn
.reg0
);
561 reg_next_use
[regno
] = mem_insn
.insn
;
562 if ((reg_next_use
[regno
] == reg_next_inc_use
[regno
])
563 || (reg_next_inc_use
[regno
] == inc_insn
.insn
))
564 reg_next_inc_use
[regno
] = NULL
;
565 df_recompute_luids (bb
);
573 if (!inc_insn
.reg1_is_const
)
575 regno
= REGNO (inc_insn
.reg1
);
576 reg_next_use
[regno
] = mem_insn
.insn
;
577 if ((reg_next_use
[regno
] == reg_next_inc_use
[regno
])
578 || (reg_next_inc_use
[regno
] == inc_insn
.insn
))
579 reg_next_inc_use
[regno
] = NULL
;
582 delete_insn (inc_insn
.insn
);
584 if (dump_file
&& mov_insn
)
586 fprintf (dump_file
, "inserting mov ");
587 dump_insn_slim (dump_file
, mov_insn
);
590 /* Record that this insn has an implicit side effect. */
591 add_reg_note (mem_insn
.insn
, REG_INC
, inc_reg
);
595 fprintf (dump_file
, "****success ");
596 dump_insn_slim (dump_file
, mem_insn
.insn
);
603 /* Try to combine the instruction in INC_INSN with the instruction in
604 MEM_INSN. First the form is determined using the DECISION_TABLE
605 and the results of parsing the INC_INSN and the MEM_INSN.
606 Assuming the form is ok, a prototype new address is built which is
607 passed to ATTEMPT_CHANGE for final processing. */
612 enum gen_form gen_form
;
613 rtx mem
= *mem_insn
.mem_loc
;
614 rtx inc_reg
= inc_insn
.form
== FORM_POST_ADD
?
615 inc_insn
.reg_res
: mem_insn
.reg0
;
617 /* The width of the mem being accessed. */
618 int size
= GET_MODE_SIZE (GET_MODE (mem
));
619 rtx_insn
*last_insn
= NULL
;
620 machine_mode reg_mode
= GET_MODE (inc_reg
);
622 switch (inc_insn
.form
)
626 last_insn
= mem_insn
.insn
;
630 last_insn
= inc_insn
.insn
;
637 /* Cannot handle auto inc of the stack. */
638 if (inc_reg
== stack_pointer_rtx
)
641 fprintf (dump_file
, "cannot inc stack %d failure\n", REGNO (inc_reg
));
645 /* Look to see if the inc register is dead after the memory
646 reference. If it is, do not do the combination. */
647 if (find_regno_note (last_insn
, REG_DEAD
, REGNO (inc_reg
)))
650 fprintf (dump_file
, "dead failure %d\n", REGNO (inc_reg
));
654 mem_insn
.reg1_state
= (mem_insn
.reg1_is_const
)
655 ? set_inc_state (mem_insn
.reg1_val
, size
) : INC_REG
;
656 inc_insn
.reg1_state
= (inc_insn
.reg1_is_const
)
657 ? set_inc_state (inc_insn
.reg1_val
, size
) : INC_REG
;
659 /* Now get the form that we are generating. */
660 gen_form
= decision_table
661 [inc_insn
.reg1_state
][mem_insn
.reg1_state
][inc_insn
.form
];
663 if (dbg_cnt (auto_inc_dec
) == false)
672 case SIMPLE_PRE_INC
: /* ++size */
674 fprintf (dump_file
, "trying SIMPLE_PRE_INC\n");
675 return attempt_change (gen_rtx_PRE_INC (reg_mode
, inc_reg
), inc_reg
);
678 case SIMPLE_POST_INC
: /* size++ */
680 fprintf (dump_file
, "trying SIMPLE_POST_INC\n");
681 return attempt_change (gen_rtx_POST_INC (reg_mode
, inc_reg
), inc_reg
);
684 case SIMPLE_PRE_DEC
: /* --size */
686 fprintf (dump_file
, "trying SIMPLE_PRE_DEC\n");
687 return attempt_change (gen_rtx_PRE_DEC (reg_mode
, inc_reg
), inc_reg
);
690 case SIMPLE_POST_DEC
: /* size-- */
692 fprintf (dump_file
, "trying SIMPLE_POST_DEC\n");
693 return attempt_change (gen_rtx_POST_DEC (reg_mode
, inc_reg
), inc_reg
);
696 case DISP_PRE
: /* ++con */
698 fprintf (dump_file
, "trying DISP_PRE\n");
699 return attempt_change (gen_rtx_PRE_MODIFY (reg_mode
,
701 gen_rtx_PLUS (reg_mode
,
707 case DISP_POST
: /* con++ */
709 fprintf (dump_file
, "trying POST_DISP\n");
710 return attempt_change (gen_rtx_POST_MODIFY (reg_mode
,
712 gen_rtx_PLUS (reg_mode
,
718 case REG_PRE
: /* ++reg */
720 fprintf (dump_file
, "trying PRE_REG\n");
721 return attempt_change (gen_rtx_PRE_MODIFY (reg_mode
,
723 gen_rtx_PLUS (reg_mode
,
729 case REG_POST
: /* reg++ */
731 fprintf (dump_file
, "trying POST_REG\n");
732 return attempt_change (gen_rtx_POST_MODIFY (reg_mode
,
734 gen_rtx_PLUS (reg_mode
,
742 /* Return the next insn that uses (if reg_next_use is passed in
743 NEXT_ARRAY) or defines (if reg_next_def is passed in NEXT_ARRAY)
747 get_next_ref (int regno
, basic_block bb
, rtx_insn
**next_array
)
749 rtx_insn
*insn
= next_array
[regno
];
751 /* Lazy about cleaning out the next_arrays. */
752 if (insn
&& BLOCK_FOR_INSN (insn
) != bb
)
754 next_array
[regno
] = NULL
;
762 /* Return true if INSN is of a form "a = b op c" where a and b are
763 regs. op is + if c is a reg and +|- if c is a const. Fill in
764 INC_INSN with what is found.
766 This function is called in two contexts, if BEFORE_MEM is true,
767 this is called for each insn in the basic block. If BEFORE_MEM is
768 false, it is called for the instruction in the block that uses the
769 index register for some memory reference that is currently being
773 parse_add_or_inc (rtx_insn
*insn
, bool before_mem
)
775 rtx pat
= single_set (insn
);
779 /* Result must be single reg. */
780 if (!REG_P (SET_DEST (pat
)))
783 if ((GET_CODE (SET_SRC (pat
)) != PLUS
)
784 && (GET_CODE (SET_SRC (pat
)) != MINUS
))
787 if (!REG_P (XEXP (SET_SRC (pat
), 0)))
790 inc_insn
.insn
= insn
;
792 inc_insn
.reg_res
= SET_DEST (pat
);
793 inc_insn
.reg0
= XEXP (SET_SRC (pat
), 0);
794 if (rtx_equal_p (inc_insn
.reg_res
, inc_insn
.reg0
))
795 inc_insn
.form
= before_mem
? FORM_PRE_INC
: FORM_POST_INC
;
797 inc_insn
.form
= before_mem
? FORM_PRE_ADD
: FORM_POST_ADD
;
799 if (CONST_INT_P (XEXP (SET_SRC (pat
), 1)))
801 /* Process a = b + c where c is a const. */
802 inc_insn
.reg1_is_const
= true;
803 if (GET_CODE (SET_SRC (pat
)) == PLUS
)
805 inc_insn
.reg1
= XEXP (SET_SRC (pat
), 1);
806 inc_insn
.reg1_val
= INTVAL (inc_insn
.reg1
);
810 inc_insn
.reg1_val
= -INTVAL (XEXP (SET_SRC (pat
), 1));
811 inc_insn
.reg1
= GEN_INT (inc_insn
.reg1_val
);
815 else if ((HAVE_PRE_MODIFY_REG
|| HAVE_POST_MODIFY_REG
)
816 && (REG_P (XEXP (SET_SRC (pat
), 1)))
817 && GET_CODE (SET_SRC (pat
)) == PLUS
)
819 /* Process a = b + c where c is a reg. */
820 inc_insn
.reg1
= XEXP (SET_SRC (pat
), 1);
821 inc_insn
.reg1_is_const
= false;
823 if (inc_insn
.form
== FORM_PRE_INC
824 || inc_insn
.form
== FORM_POST_INC
)
826 else if (rtx_equal_p (inc_insn
.reg_res
, inc_insn
.reg1
))
828 /* Reverse the two operands and turn *_ADD into *_INC since
830 std::swap (inc_insn
.reg0
, inc_insn
.reg1
);
831 inc_insn
.form
= before_mem
? FORM_PRE_INC
: FORM_POST_INC
;
842 /* A recursive function that checks all of the mem uses in
843 ADDRESS_OF_X to see if any single one of them is compatible with
844 what has been found in inc_insn.
846 -1 is returned for success. 0 is returned if nothing was found and
847 1 is returned for failure. */
850 find_address (rtx
*address_of_x
)
852 rtx x
= *address_of_x
;
853 enum rtx_code code
= GET_CODE (x
);
854 const char *const fmt
= GET_RTX_FORMAT (code
);
859 if (code
== MEM
&& rtx_equal_p (XEXP (x
, 0), inc_insn
.reg_res
))
861 /* Match with *reg0. */
862 mem_insn
.mem_loc
= address_of_x
;
863 mem_insn
.reg0
= inc_insn
.reg_res
;
864 mem_insn
.reg1_is_const
= true;
865 mem_insn
.reg1_val
= 0;
866 mem_insn
.reg1
= GEN_INT (0);
869 if (code
== MEM
&& GET_CODE (XEXP (x
, 0)) == PLUS
870 && rtx_equal_p (XEXP (XEXP (x
, 0), 0), inc_insn
.reg_res
))
872 rtx b
= XEXP (XEXP (x
, 0), 1);
873 mem_insn
.mem_loc
= address_of_x
;
874 mem_insn
.reg0
= inc_insn
.reg_res
;
876 mem_insn
.reg1_is_const
= inc_insn
.reg1_is_const
;
879 /* Match with *(reg0 + reg1) where reg1 is a const. */
880 HOST_WIDE_INT val
= INTVAL (b
);
881 if (inc_insn
.reg1_is_const
882 && (inc_insn
.reg1_val
== val
|| inc_insn
.reg1_val
== -val
))
884 mem_insn
.reg1_val
= val
;
888 else if (!inc_insn
.reg1_is_const
889 && rtx_equal_p (inc_insn
.reg1
, b
))
890 /* Match with *(reg0 + reg1). */
894 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
896 /* If REG occurs inside a MEM used in a bit-field reference,
897 that is unacceptable. */
898 if (find_address (&XEXP (x
, 0)))
902 if (x
== inc_insn
.reg_res
)
905 /* Time for some deep diving. */
906 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
910 tem
= find_address (&XEXP (x
, i
));
911 /* If this is the first use, let it go so the rest of the
912 insn can be checked. */
916 /* More than one match was found. */
919 else if (fmt
[i
] == 'E')
922 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
924 tem
= find_address (&XVECEXP (x
, i
, j
));
925 /* If this is the first use, let it go so the rest of
926 the insn can be checked. */
930 /* More than one match was found. */
938 /* Once a suitable mem reference has been found and the MEM_INSN
939 structure has been filled in, FIND_INC is called to see if there is
940 a suitable add or inc insn that follows the mem reference and
941 determine if it is suitable to merge.
943 In the case where the MEM_INSN has two registers in the reference,
944 this function may be called recursively. The first time looking
945 for an add of the first register, and if that fails, looking for an
946 add of the second register. The FIRST_TRY parameter is used to
947 only allow the parameters to be reversed once. */
950 find_inc (bool first_try
)
953 basic_block bb
= BLOCK_FOR_INSN (mem_insn
.insn
);
954 rtx_insn
*other_insn
;
957 /* Make sure this reg appears only once in this insn. */
958 if (count_occurrences (PATTERN (mem_insn
.insn
), mem_insn
.reg0
, 1) != 1)
961 fprintf (dump_file
, "mem count failure\n");
966 dump_mem_insn (dump_file
);
968 /* Find the next use that is an inc. */
969 insn
= get_next_ref (REGNO (mem_insn
.reg0
),
970 BLOCK_FOR_INSN (mem_insn
.insn
),
975 /* Even though we know the next use is an add or inc because it came
976 from the reg_next_inc_use, we must still reparse. */
977 if (!parse_add_or_inc (insn
, false))
979 /* Next use was not an add. Look for one extra case. It could be
986 if we reverse the operands in the mem ref we would
987 find this. Only try it once though. */
988 if (first_try
&& !mem_insn
.reg1_is_const
)
990 std::swap (mem_insn
.reg0
, mem_insn
.reg1
);
991 return find_inc (false);
997 /* Need to assure that none of the operands of the inc instruction are
998 assigned to by the mem insn. */
999 FOR_EACH_INSN_DEF (def
, mem_insn
.insn
)
1001 unsigned int regno
= DF_REF_REGNO (def
);
1002 if ((regno
== REGNO (inc_insn
.reg0
))
1003 || (regno
== REGNO (inc_insn
.reg_res
)))
1006 fprintf (dump_file
, "inc conflicts with store failure.\n");
1009 if (!inc_insn
.reg1_is_const
&& (regno
== REGNO (inc_insn
.reg1
)))
1012 fprintf (dump_file
, "inc conflicts with store failure.\n");
1018 dump_inc_insn (dump_file
);
1020 if (inc_insn
.form
== FORM_POST_ADD
)
1022 /* Make sure that there is no insn that assigns to inc_insn.res
1023 between the mem_insn and the inc_insn. */
1024 rtx_insn
*other_insn
= get_next_ref (REGNO (inc_insn
.reg_res
),
1025 BLOCK_FOR_INSN (mem_insn
.insn
),
1027 if (other_insn
!= inc_insn
.insn
)
1031 "result of add is assigned to between mem and inc insns.\n");
1035 other_insn
= get_next_ref (REGNO (inc_insn
.reg_res
),
1036 BLOCK_FOR_INSN (mem_insn
.insn
),
1039 && (other_insn
!= inc_insn
.insn
)
1040 && (DF_INSN_LUID (inc_insn
.insn
) > DF_INSN_LUID (other_insn
)))
1044 "result of add is used between mem and inc insns.\n");
1048 /* For the post_add to work, the result_reg of the inc must not be
1049 used in the mem insn since this will become the new index
1051 if (reg_overlap_mentioned_p (inc_insn
.reg_res
, PATTERN (mem_insn
.insn
)))
1054 fprintf (dump_file
, "base reg replacement failure.\n");
1059 if (mem_insn
.reg1_is_const
)
1061 if (mem_insn
.reg1_val
== 0)
1063 if (!inc_insn
.reg1_is_const
)
1065 /* The mem looks like *r0 and the rhs of the add has two
1067 int luid
= DF_INSN_LUID (inc_insn
.insn
);
1068 if (inc_insn
.form
== FORM_POST_ADD
)
1070 /* The trick is that we are not going to increment r0,
1071 we are going to increment the result of the add insn.
1072 For this trick to be correct, the result reg of
1073 the inc must be a valid addressing reg. */
1074 addr_space_t as
= MEM_ADDR_SPACE (*mem_insn
.mem_loc
);
1075 if (GET_MODE (inc_insn
.reg_res
)
1076 != targetm
.addr_space
.address_mode (as
))
1079 fprintf (dump_file
, "base reg mode failure.\n");
1083 /* We also need to make sure that the next use of
1084 inc result is after the inc. */
1086 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_use
);
1087 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1090 if (!rtx_equal_p (mem_insn
.reg0
, inc_insn
.reg0
))
1091 std::swap (inc_insn
.reg0
, inc_insn
.reg1
);
1095 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_def
);
1096 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1100 /* Both the inc/add and the mem have a constant. Need to check
1101 that the constants are ok. */
1102 else if ((mem_insn
.reg1_val
!= inc_insn
.reg1_val
)
1103 && (mem_insn
.reg1_val
!= -inc_insn
.reg1_val
))
1108 /* The mem insn is of the form *(a + b) where a and b are both
1109 regs. It may be that in order to match the add or inc we
1110 need to treat it as if it was *(b + a). It may also be that
1111 the add is of the form a + c where c does not match b and
1112 then we just abandon this. */
1114 int luid
= DF_INSN_LUID (inc_insn
.insn
);
1115 rtx_insn
*other_insn
;
1117 /* Make sure this reg appears only once in this insn. */
1118 if (count_occurrences (PATTERN (mem_insn
.insn
), mem_insn
.reg1
, 1) != 1)
1121 if (inc_insn
.form
== FORM_POST_ADD
)
1123 /* For this trick to be correct, the result reg of the inc
1124 must be a valid addressing reg. */
1125 addr_space_t as
= MEM_ADDR_SPACE (*mem_insn
.mem_loc
);
1126 if (GET_MODE (inc_insn
.reg_res
)
1127 != targetm
.addr_space
.address_mode (as
))
1130 fprintf (dump_file
, "base reg mode failure.\n");
1134 if (rtx_equal_p (mem_insn
.reg0
, inc_insn
.reg0
))
1136 if (!rtx_equal_p (mem_insn
.reg1
, inc_insn
.reg1
))
1138 /* See comment above on find_inc (false) call. */
1141 std::swap (mem_insn
.reg0
, mem_insn
.reg1
);
1142 return find_inc (false);
1148 /* Need to check that there are no assignments to b
1149 before the add insn. */
1151 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_def
);
1152 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1154 /* All ok for the next step. */
1158 /* We know that mem_insn.reg0 must equal inc_insn.reg1
1159 or else we would not have found the inc insn. */
1160 std::swap (mem_insn
.reg0
, mem_insn
.reg1
);
1161 if (!rtx_equal_p (mem_insn
.reg0
, inc_insn
.reg0
))
1163 /* See comment above on find_inc (false) call. */
1165 return find_inc (false);
1169 /* To have gotten here know that.
1174 We also know that the lhs of the inc is not b or a. We
1175 need to make sure that there are no assignments to b
1176 between the mem ref and the inc. */
1179 = get_next_ref (REGNO (inc_insn
.reg0
), bb
, reg_next_def
);
1180 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1184 /* Need to check that the next use of the add result is later than
1185 add insn since this will be the reg incremented. */
1187 = get_next_ref (REGNO (inc_insn
.reg_res
), bb
, reg_next_use
);
1188 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1191 else /* FORM_POST_INC. There is less to check here because we
1192 know that operands must line up. */
1194 if (!rtx_equal_p (mem_insn
.reg1
, inc_insn
.reg1
))
1195 /* See comment above on find_inc (false) call. */
1199 std::swap (mem_insn
.reg0
, mem_insn
.reg1
);
1200 return find_inc (false);
1206 /* To have gotten here know that.
1211 We also know that the lhs of the inc is not b. We need to make
1212 sure that there are no assignments to b between the mem ref and
1215 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_def
);
1216 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1221 if (inc_insn
.form
== FORM_POST_INC
)
1224 = get_next_ref (REGNO (inc_insn
.reg0
), bb
, reg_next_use
);
1225 /* When we found inc_insn, we were looking for the
1226 next add or inc, not the next insn that used the
1227 reg. Because we are going to increment the reg
1228 in this form, we need to make sure that there
1229 were no intervening uses of reg. */
1230 if (inc_insn
.insn
!= other_insn
)
1234 return try_merge ();
1238 /* A recursive function that walks ADDRESS_OF_X to find all of the mem
1239 uses in pat that could be used as an auto inc or dec. It then
1240 calls FIND_INC for each one. */
1243 find_mem (rtx
*address_of_x
)
1245 rtx x
= *address_of_x
;
1246 enum rtx_code code
= GET_CODE (x
);
1247 const char *const fmt
= GET_RTX_FORMAT (code
);
1250 if (code
== MEM
&& REG_P (XEXP (x
, 0)))
1252 /* Match with *reg0. */
1253 mem_insn
.mem_loc
= address_of_x
;
1254 mem_insn
.reg0
= XEXP (x
, 0);
1255 mem_insn
.reg1_is_const
= true;
1256 mem_insn
.reg1_val
= 0;
1257 mem_insn
.reg1
= GEN_INT (0);
1258 if (find_inc (true))
1261 if (code
== MEM
&& GET_CODE (XEXP (x
, 0)) == PLUS
1262 && REG_P (XEXP (XEXP (x
, 0), 0)))
1264 rtx reg1
= XEXP (XEXP (x
, 0), 1);
1265 mem_insn
.mem_loc
= address_of_x
;
1266 mem_insn
.reg0
= XEXP (XEXP (x
, 0), 0);
1267 mem_insn
.reg1
= reg1
;
1268 if (CONST_INT_P (reg1
))
1270 mem_insn
.reg1_is_const
= true;
1271 /* Match with *(reg0 + c) where c is a const. */
1272 mem_insn
.reg1_val
= INTVAL (reg1
);
1273 if (find_inc (true))
1276 else if (REG_P (reg1
))
1278 /* Match with *(reg0 + reg1). */
1279 mem_insn
.reg1_is_const
= false;
1280 if (find_inc (true))
1285 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
1287 /* If REG occurs inside a MEM used in a bit-field reference,
1288 that is unacceptable. */
1292 /* Time for some deep diving. */
1293 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1297 if (find_mem (&XEXP (x
, i
)))
1300 else if (fmt
[i
] == 'E')
1303 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1304 if (find_mem (&XVECEXP (x
, i
, j
)))
1312 /* Try to combine all incs and decs by constant values with memory
1313 references in BB. */
1316 merge_in_block (int max_reg
, basic_block bb
)
1320 int success_in_block
= 0;
1323 fprintf (dump_file
, "\n\nstarting bb %d\n", bb
->index
);
1325 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, curr
)
1327 bool insn_is_add_or_inc
= true;
1329 if (!NONDEBUG_INSN_P (insn
))
1332 /* This continue is deliberate. We do not want the uses of the
1333 jump put into reg_next_use because it is not considered safe to
1334 combine a preincrement with a jump. */
1339 dump_insn_slim (dump_file
, insn
);
1341 /* Does this instruction increment or decrement a register? */
1342 if (parse_add_or_inc (insn
, true))
1344 int regno
= REGNO (inc_insn
.reg_res
);
1345 /* Cannot handle case where there are three separate regs
1346 before a mem ref. Too many moves would be needed to be
1348 if ((inc_insn
.form
== FORM_PRE_INC
) || inc_insn
.reg1_is_const
)
1350 mem_insn
.insn
= get_next_ref (regno
, bb
, reg_next_use
);
1354 if (!inc_insn
.reg1_is_const
)
1356 /* We are only here if we are going to try a
1357 HAVE_*_MODIFY_REG type transformation. c is a
1358 reg and we must sure that the path from the
1359 inc_insn to the mem_insn.insn is both def and use
1360 clear of c because the inc insn is going to move
1361 into the mem_insn.insn. */
1362 int luid
= DF_INSN_LUID (mem_insn
.insn
);
1363 rtx_insn
*other_insn
1364 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_use
);
1366 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1370 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_def
);
1372 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1377 dump_inc_insn (dump_file
);
1379 if (ok
&& find_address (&PATTERN (mem_insn
.insn
)) == -1)
1382 dump_mem_insn (dump_file
);
1386 insn_is_add_or_inc
= false;
1394 insn_is_add_or_inc
= false;
1395 mem_insn
.insn
= insn
;
1396 if (find_mem (&PATTERN (insn
)))
1400 /* If the inc insn was merged with a mem, the inc insn is gone
1401 and there is noting to update. */
1402 if (df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
))
1406 /* Need to update next use. */
1407 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
1409 reg_next_use
[DF_REF_REGNO (def
)] = NULL
;
1410 reg_next_inc_use
[DF_REF_REGNO (def
)] = NULL
;
1411 reg_next_def
[DF_REF_REGNO (def
)] = insn
;
1414 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
1416 reg_next_use
[DF_REF_REGNO (use
)] = insn
;
1417 if (insn_is_add_or_inc
)
1418 reg_next_inc_use
[DF_REF_REGNO (use
)] = insn
;
1420 reg_next_inc_use
[DF_REF_REGNO (use
)] = NULL
;
1424 fprintf (dump_file
, "skipping update of deleted insn %d\n",
1428 /* If we were successful, try again. There may have been several
1429 opportunities that were interleaved. This is rare but
1430 gcc.c-torture/compile/pr17273.c actually exhibits this. */
1431 if (success_in_block
)
1433 /* In this case, we must clear these vectors since the trick of
1434 testing if the stale insn in the block will not work. */
1435 memset (reg_next_use
, 0, max_reg
* sizeof (rtx
));
1436 memset (reg_next_inc_use
, 0, max_reg
* sizeof (rtx
));
1437 memset (reg_next_def
, 0, max_reg
* sizeof (rtx
));
1438 df_recompute_luids (bb
);
1439 merge_in_block (max_reg
, bb
);
1443 /* Discover auto-inc auto-dec instructions. */
1447 const pass_data pass_data_inc_dec
=
1449 RTL_PASS
, /* type */
1450 "auto_inc_dec", /* name */
1451 OPTGROUP_NONE
, /* optinfo_flags */
1452 TV_AUTO_INC_DEC
, /* tv_id */
1453 0, /* properties_required */
1454 0, /* properties_provided */
1455 0, /* properties_destroyed */
1456 0, /* todo_flags_start */
1457 TODO_df_finish
, /* todo_flags_finish */
1460 class pass_inc_dec
: public rtl_opt_pass
1463 pass_inc_dec (gcc::context
*ctxt
)
1464 : rtl_opt_pass (pass_data_inc_dec
, ctxt
)
1467 /* opt_pass methods: */
1468 virtual bool gate (function
*)
1473 return (optimize
> 0 && flag_auto_inc_dec
);
1477 unsigned int execute (function
*);
1479 }; // class pass_inc_dec
1482 pass_inc_dec::execute (function
*fun ATTRIBUTE_UNUSED
)
1488 int max_reg
= max_reg_num ();
1491 init_decision_table ();
1493 mem_tmp
= gen_rtx_MEM (Pmode
, NULL_RTX
);
1495 df_note_add_problem ();
1498 reg_next_use
= XCNEWVEC (rtx_insn
*, max_reg
);
1499 reg_next_inc_use
= XCNEWVEC (rtx_insn
*, max_reg
);
1500 reg_next_def
= XCNEWVEC (rtx_insn
*, max_reg
);
1501 FOR_EACH_BB_FN (bb
, fun
)
1502 merge_in_block (max_reg
, bb
);
1504 free (reg_next_use
);
1505 free (reg_next_inc_use
);
1506 free (reg_next_def
);
1516 make_pass_inc_dec (gcc::context
*ctxt
)
1518 return new pass_inc_dec (ctxt
);