1 /* Discovery of auto-inc and auto-dec instructions.
2 Copyright (C) 2006-2014 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"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "insn-config.h"
40 #include "diagnostic-core.h"
43 #include "tree-pass.h"
48 /* This pass was originally removed from flow.c. However there is
49 almost nothing that remains of that code.
51 There are (4) basic forms that are matched:
80 (For this case to be true, b must not be assigned or used between
81 the *a and the assignment to b. B must also be a Pmode reg.)
99 There are three types of values of c.
101 1) c is a constant equal to the width of the value being accessed by
102 the pointer. This is useful for machines that have
103 HAVE_PRE_INCREMENT, HAVE_POST_INCREMENT, HAVE_PRE_DECREMENT or
104 HAVE_POST_DECREMENT defined.
106 2) c is a constant not equal to the width of the value being accessed
107 by the pointer. This is useful for machines that have
108 HAVE_PRE_MODIFY_DISP, HAVE_POST_MODIFY_DISP defined.
110 3) c is a register. This is useful for machines that have
111 HAVE_PRE_MODIFY_REG, HAVE_POST_MODIFY_REG
113 The is one special case: if a already had an offset equal to it +-
114 its width and that offset is equal to -c when the increment was
115 before the ref or +c if the increment was after the ref, then if we
116 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 enum 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
, speed
)
490 + set_rtx_cost (PATTERN (inc_insn
.insn
), speed
));
491 new_cost
= set_src_cost (mem_tmp
, 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 enum 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 /* Reverse the operands in a mem insn. */
767 rtx tmp
= mem_insn
.reg1
;
768 mem_insn
.reg1
= mem_insn
.reg0
;
773 /* Reverse the operands in a inc insn. */
778 rtx tmp
= inc_insn
.reg1
;
779 inc_insn
.reg1
= inc_insn
.reg0
;
784 /* Return true if INSN is of a form "a = b op c" where a and b are
785 regs. op is + if c is a reg and +|- if c is a const. Fill in
786 INC_INSN with what is found.
788 This function is called in two contexts, if BEFORE_MEM is true,
789 this is called for each insn in the basic block. If BEFORE_MEM is
790 false, it is called for the instruction in the block that uses the
791 index register for some memory reference that is currently being
795 parse_add_or_inc (rtx_insn
*insn
, bool before_mem
)
797 rtx pat
= single_set (insn
);
801 /* Result must be single reg. */
802 if (!REG_P (SET_DEST (pat
)))
805 if ((GET_CODE (SET_SRC (pat
)) != PLUS
)
806 && (GET_CODE (SET_SRC (pat
)) != MINUS
))
809 if (!REG_P (XEXP (SET_SRC (pat
), 0)))
812 inc_insn
.insn
= insn
;
814 inc_insn
.reg_res
= SET_DEST (pat
);
815 inc_insn
.reg0
= XEXP (SET_SRC (pat
), 0);
816 if (rtx_equal_p (inc_insn
.reg_res
, inc_insn
.reg0
))
817 inc_insn
.form
= before_mem
? FORM_PRE_INC
: FORM_POST_INC
;
819 inc_insn
.form
= before_mem
? FORM_PRE_ADD
: FORM_POST_ADD
;
821 if (CONST_INT_P (XEXP (SET_SRC (pat
), 1)))
823 /* Process a = b + c where c is a const. */
824 inc_insn
.reg1_is_const
= true;
825 if (GET_CODE (SET_SRC (pat
)) == PLUS
)
827 inc_insn
.reg1
= XEXP (SET_SRC (pat
), 1);
828 inc_insn
.reg1_val
= INTVAL (inc_insn
.reg1
);
832 inc_insn
.reg1_val
= -INTVAL (XEXP (SET_SRC (pat
), 1));
833 inc_insn
.reg1
= GEN_INT (inc_insn
.reg1_val
);
837 else if ((HAVE_PRE_MODIFY_REG
|| HAVE_POST_MODIFY_REG
)
838 && (REG_P (XEXP (SET_SRC (pat
), 1)))
839 && GET_CODE (SET_SRC (pat
)) == PLUS
)
841 /* Process a = b + c where c is a reg. */
842 inc_insn
.reg1
= XEXP (SET_SRC (pat
), 1);
843 inc_insn
.reg1_is_const
= false;
845 if (inc_insn
.form
== FORM_PRE_INC
846 || inc_insn
.form
== FORM_POST_INC
)
848 else if (rtx_equal_p (inc_insn
.reg_res
, inc_insn
.reg1
))
850 /* Reverse the two operands and turn *_ADD into *_INC since
853 inc_insn
.form
= before_mem
? FORM_PRE_INC
: FORM_POST_INC
;
864 /* A recursive function that checks all of the mem uses in
865 ADDRESS_OF_X to see if any single one of them is compatible with
866 what has been found in inc_insn.
868 -1 is returned for success. 0 is returned if nothing was found and
869 1 is returned for failure. */
872 find_address (rtx
*address_of_x
)
874 rtx x
= *address_of_x
;
875 enum rtx_code code
= GET_CODE (x
);
876 const char *const fmt
= GET_RTX_FORMAT (code
);
881 if (code
== MEM
&& rtx_equal_p (XEXP (x
, 0), inc_insn
.reg_res
))
883 /* Match with *reg0. */
884 mem_insn
.mem_loc
= address_of_x
;
885 mem_insn
.reg0
= inc_insn
.reg_res
;
886 mem_insn
.reg1_is_const
= true;
887 mem_insn
.reg1_val
= 0;
888 mem_insn
.reg1
= GEN_INT (0);
891 if (code
== MEM
&& GET_CODE (XEXP (x
, 0)) == PLUS
892 && rtx_equal_p (XEXP (XEXP (x
, 0), 0), inc_insn
.reg_res
))
894 rtx b
= XEXP (XEXP (x
, 0), 1);
895 mem_insn
.mem_loc
= address_of_x
;
896 mem_insn
.reg0
= inc_insn
.reg_res
;
898 mem_insn
.reg1_is_const
= inc_insn
.reg1_is_const
;
901 /* Match with *(reg0 + reg1) where reg1 is a const. */
902 HOST_WIDE_INT val
= INTVAL (b
);
903 if (inc_insn
.reg1_is_const
904 && (inc_insn
.reg1_val
== val
|| inc_insn
.reg1_val
== -val
))
906 mem_insn
.reg1_val
= val
;
910 else if (!inc_insn
.reg1_is_const
911 && rtx_equal_p (inc_insn
.reg1
, b
))
912 /* Match with *(reg0 + reg1). */
916 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
918 /* If REG occurs inside a MEM used in a bit-field reference,
919 that is unacceptable. */
920 if (find_address (&XEXP (x
, 0)))
924 if (x
== inc_insn
.reg_res
)
927 /* Time for some deep diving. */
928 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
932 tem
= find_address (&XEXP (x
, i
));
933 /* If this is the first use, let it go so the rest of the
934 insn can be checked. */
938 /* More than one match was found. */
941 else if (fmt
[i
] == 'E')
944 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
946 tem
= find_address (&XVECEXP (x
, i
, j
));
947 /* If this is the first use, let it go so the rest of
948 the insn can be checked. */
952 /* More than one match was found. */
960 /* Once a suitable mem reference has been found and the MEM_INSN
961 structure has been filled in, FIND_INC is called to see if there is
962 a suitable add or inc insn that follows the mem reference and
963 determine if it is suitable to merge.
965 In the case where the MEM_INSN has two registers in the reference,
966 this function may be called recursively. The first time looking
967 for an add of the first register, and if that fails, looking for an
968 add of the second register. The FIRST_TRY parameter is used to
969 only allow the parameters to be reversed once. */
972 find_inc (bool first_try
)
975 basic_block bb
= BLOCK_FOR_INSN (mem_insn
.insn
);
976 rtx_insn
*other_insn
;
979 /* Make sure this reg appears only once in this insn. */
980 if (count_occurrences (PATTERN (mem_insn
.insn
), mem_insn
.reg0
, 1) != 1)
983 fprintf (dump_file
, "mem count failure\n");
988 dump_mem_insn (dump_file
);
990 /* Find the next use that is an inc. */
991 insn
= get_next_ref (REGNO (mem_insn
.reg0
),
992 BLOCK_FOR_INSN (mem_insn
.insn
),
997 /* Even though we know the next use is an add or inc because it came
998 from the reg_next_inc_use, we must still reparse. */
999 if (!parse_add_or_inc (insn
, false))
1001 /* Next use was not an add. Look for one extra case. It could be
1008 if we reverse the operands in the mem ref we would
1009 find this. Only try it once though. */
1010 if (first_try
&& !mem_insn
.reg1_is_const
)
1013 return find_inc (false);
1019 /* Need to assure that none of the operands of the inc instruction are
1020 assigned to by the mem insn. */
1021 FOR_EACH_INSN_DEF (def
, mem_insn
.insn
)
1023 unsigned int regno
= DF_REF_REGNO (def
);
1024 if ((regno
== REGNO (inc_insn
.reg0
))
1025 || (regno
== REGNO (inc_insn
.reg_res
)))
1028 fprintf (dump_file
, "inc conflicts with store failure.\n");
1031 if (!inc_insn
.reg1_is_const
&& (regno
== REGNO (inc_insn
.reg1
)))
1034 fprintf (dump_file
, "inc conflicts with store failure.\n");
1040 dump_inc_insn (dump_file
);
1042 if (inc_insn
.form
== FORM_POST_ADD
)
1044 /* Make sure that there is no insn that assigns to inc_insn.res
1045 between the mem_insn and the inc_insn. */
1046 rtx_insn
*other_insn
= get_next_ref (REGNO (inc_insn
.reg_res
),
1047 BLOCK_FOR_INSN (mem_insn
.insn
),
1049 if (other_insn
!= inc_insn
.insn
)
1053 "result of add is assigned to between mem and inc insns.\n");
1057 other_insn
= get_next_ref (REGNO (inc_insn
.reg_res
),
1058 BLOCK_FOR_INSN (mem_insn
.insn
),
1061 && (other_insn
!= inc_insn
.insn
)
1062 && (DF_INSN_LUID (inc_insn
.insn
) > DF_INSN_LUID (other_insn
)))
1066 "result of add is used between mem and inc insns.\n");
1070 /* For the post_add to work, the result_reg of the inc must not be
1071 used in the mem insn since this will become the new index
1073 if (reg_overlap_mentioned_p (inc_insn
.reg_res
, PATTERN (mem_insn
.insn
)))
1076 fprintf (dump_file
, "base reg replacement failure.\n");
1081 if (mem_insn
.reg1_is_const
)
1083 if (mem_insn
.reg1_val
== 0)
1085 if (!inc_insn
.reg1_is_const
)
1087 /* The mem looks like *r0 and the rhs of the add has two
1089 int luid
= DF_INSN_LUID (inc_insn
.insn
);
1090 if (inc_insn
.form
== FORM_POST_ADD
)
1092 /* The trick is that we are not going to increment r0,
1093 we are going to increment the result of the add insn.
1094 For this trick to be correct, the result reg of
1095 the inc must be a valid addressing reg. */
1096 addr_space_t as
= MEM_ADDR_SPACE (*mem_insn
.mem_loc
);
1097 if (GET_MODE (inc_insn
.reg_res
)
1098 != targetm
.addr_space
.address_mode (as
))
1101 fprintf (dump_file
, "base reg mode failure.\n");
1105 /* We also need to make sure that the next use of
1106 inc result is after the inc. */
1108 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_use
);
1109 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1112 if (!rtx_equal_p (mem_insn
.reg0
, inc_insn
.reg0
))
1117 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_def
);
1118 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1122 /* Both the inc/add and the mem have a constant. Need to check
1123 that the constants are ok. */
1124 else if ((mem_insn
.reg1_val
!= inc_insn
.reg1_val
)
1125 && (mem_insn
.reg1_val
!= -inc_insn
.reg1_val
))
1130 /* The mem insn is of the form *(a + b) where a and b are both
1131 regs. It may be that in order to match the add or inc we
1132 need to treat it as if it was *(b + a). It may also be that
1133 the add is of the form a + c where c does not match b and
1134 then we just abandon this. */
1136 int luid
= DF_INSN_LUID (inc_insn
.insn
);
1137 rtx_insn
*other_insn
;
1139 /* Make sure this reg appears only once in this insn. */
1140 if (count_occurrences (PATTERN (mem_insn
.insn
), mem_insn
.reg1
, 1) != 1)
1143 if (inc_insn
.form
== FORM_POST_ADD
)
1145 /* For this trick to be correct, the result reg of the inc
1146 must be a valid addressing reg. */
1147 addr_space_t as
= MEM_ADDR_SPACE (*mem_insn
.mem_loc
);
1148 if (GET_MODE (inc_insn
.reg_res
)
1149 != targetm
.addr_space
.address_mode (as
))
1152 fprintf (dump_file
, "base reg mode failure.\n");
1156 if (rtx_equal_p (mem_insn
.reg0
, inc_insn
.reg0
))
1158 if (!rtx_equal_p (mem_insn
.reg1
, inc_insn
.reg1
))
1160 /* See comment above on find_inc (false) call. */
1164 return find_inc (false);
1170 /* Need to check that there are no assignments to b
1171 before the add insn. */
1173 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_def
);
1174 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1176 /* All ok for the next step. */
1180 /* We know that mem_insn.reg0 must equal inc_insn.reg1
1181 or else we would not have found the inc insn. */
1183 if (!rtx_equal_p (mem_insn
.reg0
, inc_insn
.reg0
))
1185 /* See comment above on find_inc (false) call. */
1187 return find_inc (false);
1191 /* To have gotten here know that.
1196 We also know that the lhs of the inc is not b or a. We
1197 need to make sure that there are no assignments to b
1198 between the mem ref and the inc. */
1201 = get_next_ref (REGNO (inc_insn
.reg0
), bb
, reg_next_def
);
1202 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1206 /* Need to check that the next use of the add result is later than
1207 add insn since this will be the reg incremented. */
1209 = get_next_ref (REGNO (inc_insn
.reg_res
), bb
, reg_next_use
);
1210 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1213 else /* FORM_POST_INC. There is less to check here because we
1214 know that operands must line up. */
1216 if (!rtx_equal_p (mem_insn
.reg1
, inc_insn
.reg1
))
1217 /* See comment above on find_inc (false) call. */
1222 return find_inc (false);
1228 /* To have gotten here know that.
1233 We also know that the lhs of the inc is not b. We need to make
1234 sure that there are no assignments to b between the mem ref and
1237 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_def
);
1238 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1243 if (inc_insn
.form
== FORM_POST_INC
)
1246 = get_next_ref (REGNO (inc_insn
.reg0
), bb
, reg_next_use
);
1247 /* When we found inc_insn, we were looking for the
1248 next add or inc, not the next insn that used the
1249 reg. Because we are going to increment the reg
1250 in this form, we need to make sure that there
1251 were no intervening uses of reg. */
1252 if (inc_insn
.insn
!= other_insn
)
1256 return try_merge ();
1260 /* A recursive function that walks ADDRESS_OF_X to find all of the mem
1261 uses in pat that could be used as an auto inc or dec. It then
1262 calls FIND_INC for each one. */
1265 find_mem (rtx
*address_of_x
)
1267 rtx x
= *address_of_x
;
1268 enum rtx_code code
= GET_CODE (x
);
1269 const char *const fmt
= GET_RTX_FORMAT (code
);
1272 if (code
== MEM
&& REG_P (XEXP (x
, 0)))
1274 /* Match with *reg0. */
1275 mem_insn
.mem_loc
= address_of_x
;
1276 mem_insn
.reg0
= XEXP (x
, 0);
1277 mem_insn
.reg1_is_const
= true;
1278 mem_insn
.reg1_val
= 0;
1279 mem_insn
.reg1
= GEN_INT (0);
1280 if (find_inc (true))
1283 if (code
== MEM
&& GET_CODE (XEXP (x
, 0)) == PLUS
1284 && REG_P (XEXP (XEXP (x
, 0), 0)))
1286 rtx reg1
= XEXP (XEXP (x
, 0), 1);
1287 mem_insn
.mem_loc
= address_of_x
;
1288 mem_insn
.reg0
= XEXP (XEXP (x
, 0), 0);
1289 mem_insn
.reg1
= reg1
;
1290 if (CONST_INT_P (reg1
))
1292 mem_insn
.reg1_is_const
= true;
1293 /* Match with *(reg0 + c) where c is a const. */
1294 mem_insn
.reg1_val
= INTVAL (reg1
);
1295 if (find_inc (true))
1298 else if (REG_P (reg1
))
1300 /* Match with *(reg0 + reg1). */
1301 mem_insn
.reg1_is_const
= false;
1302 if (find_inc (true))
1307 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
1309 /* If REG occurs inside a MEM used in a bit-field reference,
1310 that is unacceptable. */
1314 /* Time for some deep diving. */
1315 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1319 if (find_mem (&XEXP (x
, i
)))
1322 else if (fmt
[i
] == 'E')
1325 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1326 if (find_mem (&XVECEXP (x
, i
, j
)))
1334 /* Try to combine all incs and decs by constant values with memory
1335 references in BB. */
1338 merge_in_block (int max_reg
, basic_block bb
)
1342 int success_in_block
= 0;
1345 fprintf (dump_file
, "\n\nstarting bb %d\n", bb
->index
);
1347 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, curr
)
1349 bool insn_is_add_or_inc
= true;
1351 if (!NONDEBUG_INSN_P (insn
))
1354 /* This continue is deliberate. We do not want the uses of the
1355 jump put into reg_next_use because it is not considered safe to
1356 combine a preincrement with a jump. */
1361 dump_insn_slim (dump_file
, insn
);
1363 /* Does this instruction increment or decrement a register? */
1364 if (parse_add_or_inc (insn
, true))
1366 int regno
= REGNO (inc_insn
.reg_res
);
1367 /* Cannot handle case where there are three separate regs
1368 before a mem ref. Too many moves would be needed to be
1370 if ((inc_insn
.form
== FORM_PRE_INC
) || inc_insn
.reg1_is_const
)
1372 mem_insn
.insn
= get_next_ref (regno
, bb
, reg_next_use
);
1376 if (!inc_insn
.reg1_is_const
)
1378 /* We are only here if we are going to try a
1379 HAVE_*_MODIFY_REG type transformation. c is a
1380 reg and we must sure that the path from the
1381 inc_insn to the mem_insn.insn is both def and use
1382 clear of c because the inc insn is going to move
1383 into the mem_insn.insn. */
1384 int luid
= DF_INSN_LUID (mem_insn
.insn
);
1385 rtx_insn
*other_insn
1386 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_use
);
1388 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1392 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_def
);
1394 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1399 dump_inc_insn (dump_file
);
1401 if (ok
&& find_address (&PATTERN (mem_insn
.insn
)) == -1)
1404 dump_mem_insn (dump_file
);
1408 insn_is_add_or_inc
= false;
1416 insn_is_add_or_inc
= false;
1417 mem_insn
.insn
= insn
;
1418 if (find_mem (&PATTERN (insn
)))
1422 /* If the inc insn was merged with a mem, the inc insn is gone
1423 and there is noting to update. */
1424 if (df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
))
1428 /* Need to update next use. */
1429 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
1431 reg_next_use
[DF_REF_REGNO (def
)] = NULL
;
1432 reg_next_inc_use
[DF_REF_REGNO (def
)] = NULL
;
1433 reg_next_def
[DF_REF_REGNO (def
)] = insn
;
1436 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
1438 reg_next_use
[DF_REF_REGNO (use
)] = insn
;
1439 if (insn_is_add_or_inc
)
1440 reg_next_inc_use
[DF_REF_REGNO (use
)] = insn
;
1442 reg_next_inc_use
[DF_REF_REGNO (use
)] = NULL
;
1446 fprintf (dump_file
, "skipping update of deleted insn %d\n",
1450 /* If we were successful, try again. There may have been several
1451 opportunities that were interleaved. This is rare but
1452 gcc.c-torture/compile/pr17273.c actually exhibits this. */
1453 if (success_in_block
)
1455 /* In this case, we must clear these vectors since the trick of
1456 testing if the stale insn in the block will not work. */
1457 memset (reg_next_use
, 0, max_reg
* sizeof (rtx
));
1458 memset (reg_next_inc_use
, 0, max_reg
* sizeof (rtx
));
1459 memset (reg_next_def
, 0, max_reg
* sizeof (rtx
));
1460 df_recompute_luids (bb
);
1461 merge_in_block (max_reg
, bb
);
1467 /* Discover auto-inc auto-dec instructions. */
1471 const pass_data pass_data_inc_dec
=
1473 RTL_PASS
, /* type */
1474 "auto_inc_dec", /* name */
1475 OPTGROUP_NONE
, /* optinfo_flags */
1476 TV_AUTO_INC_DEC
, /* tv_id */
1477 0, /* properties_required */
1478 0, /* properties_provided */
1479 0, /* properties_destroyed */
1480 0, /* todo_flags_start */
1481 TODO_df_finish
, /* todo_flags_finish */
1484 class pass_inc_dec
: public rtl_opt_pass
1487 pass_inc_dec (gcc::context
*ctxt
)
1488 : rtl_opt_pass (pass_data_inc_dec
, ctxt
)
1491 /* opt_pass methods: */
1492 virtual bool gate (function
*)
1495 return (optimize
> 0 && flag_auto_inc_dec
);
1502 unsigned int execute (function
*);
1504 }; // class pass_inc_dec
1507 pass_inc_dec::execute (function
*fun ATTRIBUTE_UNUSED
)
1511 int max_reg
= max_reg_num ();
1514 init_decision_table ();
1516 mem_tmp
= gen_rtx_MEM (Pmode
, NULL_RTX
);
1518 df_note_add_problem ();
1521 reg_next_use
= XCNEWVEC (rtx_insn
*, max_reg
);
1522 reg_next_inc_use
= XCNEWVEC (rtx_insn
*, max_reg
);
1523 reg_next_def
= XCNEWVEC (rtx_insn
*, max_reg
);
1524 FOR_EACH_BB_FN (bb
, fun
)
1525 merge_in_block (max_reg
, bb
);
1527 free (reg_next_use
);
1528 free (reg_next_inc_use
);
1529 free (reg_next_def
);
1539 make_pass_inc_dec (gcc::context
*ctxt
)
1541 return new pass_inc_dec (ctxt
);