1 /* Discovery of auto-inc and auto-dec instructions.
2 Copyright (C) 2006, 2007 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
31 #include "insn-config.h"
41 #include "tree-pass.h"
45 /* This pass was originally removed from flow.c. However there is
46 almost nothing that remains of that code.
48 There are (4) basic forms that are matched:
70 for this case to be true, b must not be assigned or used between
71 the *a and the assignment to b. B must also be a Pmode reg.
86 There are three types of values of c.
88 1) c is a constant equal to the width of the value being accessed by
89 the pointer. This is useful for machines that have
90 HAVE_PRE_INCREMENT, HAVE_POST_INCREMENT, HAVE_PRE_DECREMENT or
91 HAVE_POST_DECREMENT defined.
93 2) c is a constant not equal to the width of the value being accessed
94 by the pointer. This is useful for machines that have
95 HAVE_PRE_MODIFY_DISP, HAVE_POST_MODIFY_DISP defined.
97 3) c is a register. This is useful for machines that have
98 HAVE_PRE_MODIFY_REG, HAVE_POST_MODIFY_REG
100 The is one special case: if a already had an offset equal to it +-
101 its width and that offset is equal to -c when the increment was
102 before the ref or +c if the increment was after the ref, then if we
103 can do the combination but switch the pre/post bit.
133 for this case to be true, b must not be assigned or used between
134 the *a and the assignment to b. B must also be a Pmode reg.
164 /* The states of the second operands of mem refs and inc insns. If no
165 second operand of the mem_ref was found, it is assumed to just be
166 ZERO. SIZE is the size of the mode accessed in the memref. The
167 ANY is used for constants that are not +-size or 0. REG is used if
168 the forms are reg1 + reg2. */
173 INC_NEG_SIZE
, /* == +size */
174 INC_POS_SIZE
, /* == -size */
175 INC_NEG_ANY
, /* == some -constant */
176 INC_POS_ANY
, /* == some +constant */
177 INC_REG
, /* == some register */
181 /* The eight forms that pre/post inc/dec can take. */
185 SIMPLE_PRE_INC
, /* ++size */
186 SIMPLE_POST_INC
, /* size++ */
187 SIMPLE_PRE_DEC
, /* --size */
188 SIMPLE_POST_DEC
, /* size-- */
189 DISP_PRE
, /* ++con */
190 DISP_POST
, /* con++ */
195 /* Tmp mem rtx for use in cost modeling. */
198 static enum inc_state
199 set_inc_state (HOST_WIDE_INT val
, int size
)
204 return (val
== -size
) ? INC_NEG_SIZE
: INC_NEG_ANY
;
206 return (val
== size
) ? INC_POS_SIZE
: INC_POS_ANY
;
209 /* The DECISION_TABLE that describes what form, if any, the increment
210 or decrement will take. It is a three dimensional table. The first
211 index is the type of constant or register found as the second
212 operand of the inc insn. The second index is the type of constant
213 or register found as the second operand of the memory reference (if
214 no second operand exists, 0 is used). The third index is the form
215 and location (relative to the mem reference) of inc insn. */
217 static bool initialized
= false;
218 static enum gen_form decision_table
[INC_last
][INC_last
][FORM_last
];
221 init_decision_table (void)
225 if (HAVE_PRE_INCREMENT
|| HAVE_PRE_MODIFY_DISP
)
227 /* Prefer the simple form if both are available. */
228 value
= (HAVE_PRE_INCREMENT
) ? SIMPLE_PRE_INC
: DISP_PRE
;
230 decision_table
[INC_POS_SIZE
][INC_ZERO
][FORM_PRE_ADD
] = value
;
231 decision_table
[INC_POS_SIZE
][INC_ZERO
][FORM_PRE_INC
] = value
;
233 decision_table
[INC_POS_SIZE
][INC_POS_SIZE
][FORM_POST_ADD
] = value
;
234 decision_table
[INC_POS_SIZE
][INC_POS_SIZE
][FORM_POST_INC
] = value
;
237 if (HAVE_POST_INCREMENT
|| HAVE_POST_MODIFY_DISP
)
239 /* Prefer the simple form if both are available. */
240 value
= (HAVE_POST_INCREMENT
) ? SIMPLE_POST_INC
: DISP_POST
;
242 decision_table
[INC_POS_SIZE
][INC_ZERO
][FORM_POST_ADD
] = value
;
243 decision_table
[INC_POS_SIZE
][INC_ZERO
][FORM_POST_INC
] = value
;
245 decision_table
[INC_POS_SIZE
][INC_NEG_SIZE
][FORM_PRE_ADD
] = value
;
246 decision_table
[INC_POS_SIZE
][INC_NEG_SIZE
][FORM_PRE_INC
] = value
;
249 if (HAVE_PRE_DECREMENT
|| HAVE_PRE_MODIFY_DISP
)
251 /* Prefer the simple form if both are available. */
252 value
= (HAVE_PRE_DECREMENT
) ? SIMPLE_PRE_DEC
: DISP_PRE
;
254 decision_table
[INC_NEG_SIZE
][INC_ZERO
][FORM_PRE_ADD
] = value
;
255 decision_table
[INC_NEG_SIZE
][INC_ZERO
][FORM_PRE_INC
] = value
;
257 decision_table
[INC_NEG_SIZE
][INC_NEG_SIZE
][FORM_POST_ADD
] = value
;
258 decision_table
[INC_NEG_SIZE
][INC_NEG_SIZE
][FORM_POST_INC
] = value
;
261 if (HAVE_POST_DECREMENT
|| HAVE_POST_MODIFY_DISP
)
263 /* Prefer the simple form if both are available. */
264 value
= (HAVE_POST_DECREMENT
) ? SIMPLE_POST_DEC
: DISP_POST
;
266 decision_table
[INC_NEG_SIZE
][INC_ZERO
][FORM_POST_ADD
] = value
;
267 decision_table
[INC_NEG_SIZE
][INC_ZERO
][FORM_POST_INC
] = value
;
269 decision_table
[INC_NEG_SIZE
][INC_POS_SIZE
][FORM_PRE_ADD
] = value
;
270 decision_table
[INC_NEG_SIZE
][INC_POS_SIZE
][FORM_PRE_INC
] = value
;
273 if (HAVE_PRE_MODIFY_DISP
)
275 decision_table
[INC_POS_ANY
][INC_ZERO
][FORM_PRE_ADD
] = DISP_PRE
;
276 decision_table
[INC_POS_ANY
][INC_ZERO
][FORM_PRE_INC
] = DISP_PRE
;
278 decision_table
[INC_POS_ANY
][INC_POS_ANY
][FORM_POST_ADD
] = DISP_PRE
;
279 decision_table
[INC_POS_ANY
][INC_POS_ANY
][FORM_POST_INC
] = DISP_PRE
;
281 decision_table
[INC_NEG_ANY
][INC_ZERO
][FORM_PRE_ADD
] = DISP_PRE
;
282 decision_table
[INC_NEG_ANY
][INC_ZERO
][FORM_PRE_INC
] = DISP_PRE
;
284 decision_table
[INC_NEG_ANY
][INC_NEG_ANY
][FORM_POST_ADD
] = DISP_PRE
;
285 decision_table
[INC_NEG_ANY
][INC_NEG_ANY
][FORM_POST_INC
] = DISP_PRE
;
288 if (HAVE_POST_MODIFY_DISP
)
290 decision_table
[INC_POS_ANY
][INC_ZERO
][FORM_POST_ADD
] = DISP_POST
;
291 decision_table
[INC_POS_ANY
][INC_ZERO
][FORM_POST_INC
] = DISP_POST
;
293 decision_table
[INC_POS_ANY
][INC_NEG_ANY
][FORM_PRE_ADD
] = DISP_POST
;
294 decision_table
[INC_POS_ANY
][INC_NEG_ANY
][FORM_PRE_INC
] = DISP_POST
;
296 decision_table
[INC_NEG_ANY
][INC_ZERO
][FORM_POST_ADD
] = DISP_POST
;
297 decision_table
[INC_NEG_ANY
][INC_ZERO
][FORM_POST_INC
] = DISP_POST
;
299 decision_table
[INC_NEG_ANY
][INC_POS_ANY
][FORM_PRE_ADD
] = DISP_POST
;
300 decision_table
[INC_NEG_ANY
][INC_POS_ANY
][FORM_PRE_INC
] = DISP_POST
;
303 /* This is much simpler than the other cases because we do not look
304 for the reg1-reg2 case. Note that we do not have a INC_POS_REG
305 and INC_NEG_REG states. Most of the use of such states would be
306 on a target that had an R1 - R2 update address form.
308 There is the remote possibility that you could also catch a = a +
309 b; *(a - b) as a postdecrement of (a + b). However, it is
310 unclear if *(a - b) would ever be generated on a machine that did
311 not have that kind of addressing mode. The IA-64 and RS6000 will
312 not do this, and I cannot speak for any other. If any
313 architecture does have an a-b update for, these cases should be
315 if (HAVE_PRE_MODIFY_REG
)
317 decision_table
[INC_REG
][INC_ZERO
][FORM_PRE_ADD
] = REG_PRE
;
318 decision_table
[INC_REG
][INC_ZERO
][FORM_PRE_INC
] = REG_PRE
;
320 decision_table
[INC_REG
][INC_REG
][FORM_POST_ADD
] = REG_PRE
;
321 decision_table
[INC_REG
][INC_REG
][FORM_POST_INC
] = REG_PRE
;
324 if (HAVE_POST_MODIFY_REG
)
326 decision_table
[INC_REG
][INC_ZERO
][FORM_POST_ADD
] = REG_POST
;
327 decision_table
[INC_REG
][INC_ZERO
][FORM_POST_INC
] = REG_POST
;
333 /* Parsed fields of an inc insn of the form "reg_res = reg0+reg1" or
334 "reg_res = reg0+c". */
336 static struct inc_insn
338 rtx insn
; /* The insn being parsed. */
339 rtx pat
; /* The pattern of the insn. */
340 bool reg1_is_const
; /* True if reg1 is const, false if reg1 is a reg. */
345 enum inc_state reg1_state
;/* The form of the const if reg1 is a const. */
346 HOST_WIDE_INT reg1_val
;/* Value if reg1 is const. */
350 /* Dump the parsed inc insn to FILE. */
353 dump_inc_insn (FILE *file
)
355 const char *f
= ((inc_insn
.form
== FORM_PRE_ADD
)
356 || (inc_insn
.form
== FORM_PRE_INC
)) ? "pre" : "post";
358 dump_insn_slim (file
, inc_insn
.insn
);
360 switch (inc_insn
.form
)
364 if (inc_insn
.reg1_is_const
)
365 fprintf (file
, "found %s add(%d) r[%d]=r[%d]+%d\n",
366 f
, INSN_UID (inc_insn
.insn
),
367 REGNO (inc_insn
.reg_res
),
368 REGNO (inc_insn
.reg0
), (int) inc_insn
.reg1_val
);
370 fprintf (file
, "found %s add(%d) r[%d]=r[%d]+r[%d]\n",
371 f
, INSN_UID (inc_insn
.insn
),
372 REGNO (inc_insn
.reg_res
),
373 REGNO (inc_insn
.reg0
), REGNO (inc_insn
.reg1
));
378 if (inc_insn
.reg1_is_const
)
379 fprintf (file
, "found %s inc(%d) r[%d]+=%d\n",
380 f
, INSN_UID (inc_insn
.insn
),
381 REGNO (inc_insn
.reg_res
), (int) inc_insn
.reg1_val
);
383 fprintf (file
, "found %s inc(%d) r[%d]+=r[%d]\n",
384 f
, INSN_UID (inc_insn
.insn
),
385 REGNO (inc_insn
.reg_res
), REGNO (inc_insn
.reg1
));
394 /* Parsed fields of a mem ref of the form "*(reg0+reg1)" or "*(reg0+c)". */
396 static struct mem_insn
398 rtx insn
; /* The insn being parsed. */
399 rtx pat
; /* The pattern of the insn. */
400 rtx
*mem_loc
; /* The address of the field that holds the mem */
401 /* that is to be replaced. */
402 bool reg1_is_const
; /* True if reg1 is const, false if reg1 is a reg. */
404 rtx reg1
; /* This is either a reg or a const depending on
406 enum inc_state reg1_state
;/* The form of the const if reg1 is a const. */
407 HOST_WIDE_INT reg1_val
;/* Value if reg1 is const. */
411 /* Dump the parsed mem insn to FILE. */
414 dump_mem_insn (FILE *file
)
416 dump_insn_slim (file
, mem_insn
.insn
);
418 if (mem_insn
.reg1_is_const
)
419 fprintf (file
, "found mem(%d) *(r[%d]+%d)\n",
420 INSN_UID (mem_insn
.insn
),
421 REGNO (mem_insn
.reg0
), (int) mem_insn
.reg1_val
);
423 fprintf (file
, "found mem(%d) *(r[%d]+r[%d])\n",
424 INSN_UID (mem_insn
.insn
),
425 REGNO (mem_insn
.reg0
), REGNO (mem_insn
.reg1
));
429 /* The following three arrays contain pointers to instructions. They
430 are indexed by REGNO. At any point in the basic block where we are
431 looking these three arrays contain, respectively, the next insn
432 that uses REGNO, the next inc or add insn that uses REGNO and the
433 next insn that sets REGNO.
435 The arrays are not cleared when we move from block to block so
436 whenever an insn is retrieved from these arrays, it's block number
437 must be compared with the current block.
440 static rtx
*reg_next_use
= NULL
;
441 static rtx
*reg_next_inc_use
= NULL
;
442 static rtx
*reg_next_def
= NULL
;
445 /* Move dead note that match PATTERN to TO_INSN from FROM_INSN. We do
446 not really care about moving any other notes from the inc or add
447 insn. Moving the REG_EQUAL and REG_EQUIV is clearly wrong and it
448 does not appear that there are any other kinds of relevant notes. */
451 move_dead_notes (rtx to_insn
, rtx from_insn
, rtx pattern
)
455 rtx prev_note
= NULL
;
457 for (note
= REG_NOTES (from_insn
); note
; note
= next_note
)
459 next_note
= XEXP (note
, 1);
461 if ((REG_NOTE_KIND (note
) == REG_DEAD
)
462 && pattern
== XEXP (note
, 0))
464 XEXP (note
, 1) = REG_NOTES (to_insn
);
465 REG_NOTES (to_insn
) = note
;
467 XEXP (prev_note
, 1) = next_note
;
469 REG_NOTES (from_insn
) = next_note
;
471 else prev_note
= note
;
476 /* Create a mov insn DEST_REG <- SRC_REG and insert it before
480 insert_move_insn_before (rtx next_insn
, rtx dest_reg
, rtx src_reg
)
485 emit_move_insn (dest_reg
, src_reg
);
486 insns
= get_insns ();
488 emit_insn_before (insns
, next_insn
);
493 /* Change mem_insn.mem_loc so that uses NEW_ADDR which has an
494 increment of INC_REG. To have reached this point, the change is a
495 legitimate one from a dataflow point of view. The only questions
496 are is this a valid change to the instruction and is this a
497 profitable change to the instruction. */
500 attempt_change (rtx new_addr
, rtx inc_reg
)
502 /* There are four cases: For the two cases that involve an add
503 instruction, we are going to have to delete the add and insert a
504 mov. We are going to assume that the mov is free. This is
505 fairly early in the backend and there are a lot of opportunities
506 for removing that move later. In particular, there is the case
507 where the move may be dead, this is what dead code elimination
508 passes are for. The two cases where we have an inc insn will be
511 basic_block bb
= BASIC_BLOCK (BLOCK_NUM (mem_insn
.insn
));
514 rtx mem
= *mem_insn
.mem_loc
;
515 enum machine_mode mode
= GET_MODE (mem
);
520 PUT_MODE (mem_tmp
, mode
);
521 XEXP (mem_tmp
, 0) = new_addr
;
523 old_cost
= rtx_cost (mem
, 0)
524 + rtx_cost (PATTERN (inc_insn
.insn
), 0);
525 new_cost
= rtx_cost (mem_tmp
, 0);
527 /* The first item of business is to see if this is profitable. */
528 if (old_cost
< new_cost
)
531 fprintf (dump_file
, "cost failure old=%d new=%d\n", old_cost
, new_cost
);
535 /* Jump thru a lot of hoops to keep the attributes up to date. We
536 do not want to call one of the change address variants that take
537 an offset even though we know the offset in many cases. These
538 assume you are changing where the address is pointing by the
540 new_mem
= replace_equiv_address_nv (mem
, new_addr
);
541 if (! validate_change (mem_insn
.insn
, mem_insn
.mem_loc
, new_mem
, 0))
544 fprintf (dump_file
, "validation failure\n");
548 /* From here to the end of the function we are committed to the
549 change, i.e. nothing fails. Generate any necessary movs, move
550 any regnotes, and fix up the reg_next_{use,inc_use,def}. */
551 switch (inc_insn
.form
)
554 mov_insn
= insert_move_insn_before (mem_insn
.insn
,
555 inc_insn
.reg_res
, inc_insn
.reg0
);
556 move_dead_notes (mov_insn
, inc_insn
.insn
, inc_insn
.reg0
);
558 regno
= REGNO (inc_insn
.reg_res
);
559 reg_next_def
[regno
] = mov_insn
;
560 reg_next_use
[regno
] = NULL
;
561 regno
= REGNO (inc_insn
.reg0
);
562 reg_next_use
[regno
] = mov_insn
;
563 df_recompute_luids (bb
);
567 regno
= REGNO (inc_insn
.reg_res
);
568 if (reg_next_use
[regno
] == reg_next_inc_use
[regno
])
569 reg_next_inc_use
[regno
] = NULL
;
573 regno
= REGNO (inc_insn
.reg_res
);
574 reg_next_def
[regno
] = mem_insn
.insn
;
575 reg_next_use
[regno
] = NULL
;
580 mov_insn
= insert_move_insn_before (mem_insn
.insn
,
581 inc_insn
.reg_res
, inc_insn
.reg0
);
582 move_dead_notes (mov_insn
, inc_insn
.insn
, inc_insn
.reg0
);
584 /* Do not move anything to the mov insn because the instruction
585 pointer for the main iteration has not yet hit that. It is
586 still pointing to the mem insn. */
587 regno
= REGNO (inc_insn
.reg_res
);
588 reg_next_def
[regno
] = mem_insn
.insn
;
589 reg_next_use
[regno
] = NULL
;
591 regno
= REGNO (inc_insn
.reg0
);
592 reg_next_use
[regno
] = mem_insn
.insn
;
593 if ((reg_next_use
[regno
] == reg_next_inc_use
[regno
])
594 || (reg_next_inc_use
[regno
] == inc_insn
.insn
))
595 reg_next_inc_use
[regno
] = NULL
;
596 df_recompute_luids (bb
);
604 if (!inc_insn
.reg1_is_const
)
606 regno
= REGNO (inc_insn
.reg1
);
607 reg_next_use
[regno
] = mem_insn
.insn
;
608 if ((reg_next_use
[regno
] == reg_next_inc_use
[regno
])
609 || (reg_next_inc_use
[regno
] == inc_insn
.insn
))
610 reg_next_inc_use
[regno
] = NULL
;
613 delete_insn (inc_insn
.insn
);
615 if (dump_file
&& mov_insn
)
617 fprintf (dump_file
, "inserting mov ");
618 dump_insn_slim (dump_file
, mov_insn
);
621 /* Record that this insn has an implicit side effect. */
622 REG_NOTES (mem_insn
.insn
)
623 = alloc_EXPR_LIST (REG_INC
, inc_reg
, REG_NOTES (mem_insn
.insn
));
627 fprintf (dump_file
, "****success ");
628 dump_insn_slim (dump_file
, mem_insn
.insn
);
635 /* Try to combine the instruction in INC_INSN with the instruction in
636 MEM_INSN. First the form is determined using the DECISION_TABLE
637 and and the results of parsing the INC_INSN and the MEM_INSN.
638 Assuming the form is ok, a prototype new address is built which is
639 passed to ATTEMPT_CHANGE for final processing. */
644 enum gen_form gen_form
;
645 rtx mem
= *mem_insn
.mem_loc
;
646 rtx inc_reg
= inc_insn
.form
== FORM_POST_ADD
?
647 inc_insn
.reg_res
: mem_insn
.reg0
;
649 /* The width of the mem being accessed. */
650 int size
= GET_MODE_SIZE (GET_MODE (mem
));
651 rtx last_insn
= NULL
;
653 switch (inc_insn
.form
)
657 last_insn
= mem_insn
.insn
;
661 last_insn
= inc_insn
.insn
;
668 /* Cannot handle auto inc of the stack. */
669 if (inc_reg
== stack_pointer_rtx
)
672 fprintf (dump_file
, "cannot inc stack %d failure\n", REGNO (inc_reg
));
676 /* Look to see if the inc register is dead after the memory
677 reference. If it is do not do the combination. */
678 if (find_regno_note (last_insn
, REG_DEAD
, REGNO (inc_reg
)))
681 fprintf (dump_file
, "dead failure %d\n", REGNO (inc_reg
));
685 mem_insn
.reg1_state
= (mem_insn
.reg1_is_const
)
686 ? set_inc_state (mem_insn
.reg1_val
, size
) : INC_REG
;
687 inc_insn
.reg1_state
= (inc_insn
.reg1_is_const
)
688 ? set_inc_state (inc_insn
.reg1_val
, size
) : INC_REG
;
690 /* Now get the form that we are generating. */
691 gen_form
= decision_table
692 [inc_insn
.reg1_state
][mem_insn
.reg1_state
][inc_insn
.form
];
694 if (dbg_cnt (auto_inc_dec
) == false)
703 case SIMPLE_PRE_INC
: /* ++size */
705 fprintf (dump_file
, "trying SIMPLE_PRE_INC\n");
706 return attempt_change (gen_rtx_PRE_INC (Pmode
, inc_reg
), inc_reg
);
709 case SIMPLE_POST_INC
: /* size++ */
711 fprintf (dump_file
, "trying SIMPLE_POST_INC\n");
712 return attempt_change (gen_rtx_POST_INC (Pmode
, inc_reg
), inc_reg
);
715 case SIMPLE_PRE_DEC
: /* --size */
717 fprintf (dump_file
, "trying SIMPLE_PRE_DEC\n");
718 return attempt_change (gen_rtx_PRE_DEC (Pmode
, inc_reg
), inc_reg
);
721 case SIMPLE_POST_DEC
: /* size-- */
723 fprintf (dump_file
, "trying SIMPLE_POST_DEC\n");
724 return attempt_change (gen_rtx_POST_DEC (Pmode
, inc_reg
), inc_reg
);
727 case DISP_PRE
: /* ++con */
729 fprintf (dump_file
, "trying DISP_PRE\n");
730 return attempt_change (gen_rtx_PRE_MODIFY (Pmode
,
738 case DISP_POST
: /* con++ */
740 fprintf (dump_file
, "trying POST_DISP\n");
741 return attempt_change (gen_rtx_POST_MODIFY (Pmode
,
749 case REG_PRE
: /* ++reg */
751 fprintf (dump_file
, "trying PRE_REG\n");
752 return attempt_change (gen_rtx_PRE_MODIFY (Pmode
,
760 case REG_POST
: /* reg++ */
762 fprintf (dump_file
, "trying POST_REG\n");
763 return attempt_change (gen_rtx_POST_MODIFY (Pmode
,
773 /* Return the next insn that uses (if reg_next_use is passed in
774 NEXT_ARRAY) or defines (if reg_next_def is passed in NEXT_ARRAY)
778 get_next_ref (int regno
, basic_block bb
, rtx
*next_array
)
780 rtx insn
= next_array
[regno
];
782 /* Lazy about cleaning out the next_arrays. */
783 if (insn
&& BASIC_BLOCK (BLOCK_NUM (insn
)) != bb
)
785 next_array
[regno
] = NULL
;
793 /* Reverse the operands in a mem insn. */
798 rtx tmp
= mem_insn
.reg1
;
799 mem_insn
.reg1
= mem_insn
.reg0
;
804 /* Reverse the operands in a inc insn. */
809 rtx tmp
= inc_insn
.reg1
;
810 inc_insn
.reg1
= inc_insn
.reg0
;
815 /* Return true if INSN is of a form "a = b op c" where a and b are
816 regs. op is + if c is a reg and +|- if c is a const. Fill in
817 INC_INSN with what is found.
819 This function is called in two contexts, if BEFORE_MEM is true,
820 this is called for each insn in the basic block. If BEFORE_MEM is
821 false, it is called for the instruction in the block that uses the
822 index register for some memory reference that is currently being
826 parse_add_or_inc (rtx insn
, bool before_mem
)
828 rtx pat
= single_set (insn
);
832 /* Result must be single reg. */
833 if (!REG_P (SET_DEST (pat
)))
836 if ((GET_CODE (SET_SRC (pat
)) != PLUS
)
837 && (GET_CODE (SET_SRC (pat
)) != MINUS
))
840 if (!REG_P (XEXP (SET_SRC (pat
), 0)))
843 inc_insn
.insn
= insn
;
845 inc_insn
.reg_res
= SET_DEST (pat
);
846 inc_insn
.reg0
= XEXP (SET_SRC (pat
), 0);
847 if (rtx_equal_p (inc_insn
.reg_res
, inc_insn
.reg0
))
848 inc_insn
.form
= before_mem
? FORM_PRE_INC
: FORM_POST_INC
;
850 inc_insn
.form
= before_mem
? FORM_PRE_ADD
: FORM_POST_ADD
;
852 if (GET_CODE (XEXP (SET_SRC (pat
), 1)) == CONST_INT
)
854 /* Process a = b + c where c is a const. */
855 inc_insn
.reg1_is_const
= true;
856 if (GET_CODE (SET_SRC (pat
)) == PLUS
)
858 inc_insn
.reg1
= XEXP (SET_SRC (pat
), 1);
859 inc_insn
.reg1_val
= INTVAL (inc_insn
.reg1
);
863 inc_insn
.reg1_val
= -INTVAL (XEXP (SET_SRC (pat
), 1));
864 inc_insn
.reg1
= GEN_INT (inc_insn
.reg1_val
);
868 else if ((HAVE_PRE_MODIFY_REG
|| HAVE_POST_MODIFY_REG
)
869 && (REG_P (XEXP (SET_SRC (pat
), 1)))
870 && GET_CODE (SET_SRC (pat
)) == PLUS
)
872 /* Process a = b + c where c is a reg. */
873 inc_insn
.reg1
= XEXP (SET_SRC (pat
), 1);
874 inc_insn
.reg1_is_const
= false;
876 if (inc_insn
.form
== FORM_PRE_INC
877 || inc_insn
.form
== FORM_POST_INC
)
879 else if (rtx_equal_p (inc_insn
.reg_res
, inc_insn
.reg1
))
881 /* Reverse the two operands and turn *_ADD into *_INC since
884 inc_insn
.form
= before_mem
? FORM_PRE_INC
: FORM_POST_INC
;
895 /* A recursive function that checks all of the mem uses in
896 ADDRESS_OF_X to see if any single one of them is compatible with
897 what has been found in inc_insn.
899 -1 is returned for success. 0 is returned if nothing was found and
900 1 is returned for failure. */
903 find_address (rtx
*address_of_x
)
905 rtx x
= *address_of_x
;
906 enum rtx_code code
= GET_CODE (x
);
907 const char *const fmt
= GET_RTX_FORMAT (code
);
912 if (code
== MEM
&& rtx_equal_p (XEXP (x
, 0), inc_insn
.reg_res
))
914 /* Match with *reg0. */
915 mem_insn
.mem_loc
= address_of_x
;
916 mem_insn
.reg0
= inc_insn
.reg_res
;
917 mem_insn
.reg1_is_const
= true;
918 mem_insn
.reg1_val
= 0;
919 mem_insn
.reg1
= GEN_INT (0);
922 if (code
== MEM
&& GET_CODE (XEXP (x
, 0)) == PLUS
923 && rtx_equal_p (XEXP (XEXP (x
, 0), 0), inc_insn
.reg_res
))
925 rtx b
= XEXP (XEXP (x
, 0), 1);
926 mem_insn
.mem_loc
= address_of_x
;
927 mem_insn
.reg0
= inc_insn
.reg_res
;
929 mem_insn
.reg1_is_const
= inc_insn
.reg1_is_const
;
930 if (GET_CODE (b
) == CONST_INT
)
932 /* Match with *(reg0 + reg1) where reg1 is a const. */
933 HOST_WIDE_INT val
= INTVAL (b
);
934 if (inc_insn
.reg1_is_const
935 && (inc_insn
.reg1_val
== val
|| inc_insn
.reg1_val
== -val
))
937 mem_insn
.reg1_val
= val
;
941 else if (!inc_insn
.reg1_is_const
942 && rtx_equal_p (inc_insn
.reg1
, b
))
943 /* Match with *(reg0 + reg1). */
947 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
949 /* If REG occurs inside a MEM used in a bit-field reference,
950 that is unacceptable. */
951 if (find_address (&XEXP (x
, 0)))
955 if (x
== inc_insn
.reg_res
)
958 /* Time for some deep diving. */
959 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
963 tem
= find_address (&XEXP (x
, i
));
964 /* If this is the first use, let it go so the rest of the
965 insn can be checked. */
969 /* More than one match was found. */
972 else if (fmt
[i
] == 'E')
975 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
977 tem
= find_address (&XVECEXP (x
, i
, j
));
978 /* If this is the first use, let it go so the rest of
979 the insn can be checked. */
983 /* More than one match was found. */
991 /* Once a suitable mem reference has been found and the MEM_INSN
992 structure has been filled in, FIND_INC is called to see if there is
993 a suitable add or inc insn that follows the mem reference and
994 determine if it is suitable to merge.
996 In the case where the MEM_INSN has two registers in the reference,
997 this function may be called recursively. The first time looking
998 for an add of the first register, and if that fails, looking for an
999 add of the second register. The FIRST_TRY parameter is used to
1000 only allow the parameters to be reversed once. */
1003 find_inc (bool first_try
)
1006 basic_block bb
= BASIC_BLOCK (BLOCK_NUM (mem_insn
.insn
));
1008 struct df_ref
**def_rec
;
1010 /* Make sure this reg appears only once in this insn. */
1011 if (count_occurrences (PATTERN (mem_insn
.insn
), mem_insn
.reg0
, 1) != 1)
1014 fprintf (dump_file
, "mem count failure\n");
1019 dump_mem_insn (dump_file
);
1021 /* Find the next use that is an inc. */
1022 insn
= get_next_ref (REGNO (mem_insn
.reg0
),
1023 BASIC_BLOCK (BLOCK_NUM (mem_insn
.insn
)),
1028 /* Even though we know the next use is an add or inc because it came
1029 from the reg_next_inc_use, we must still reparse. */
1030 if (!parse_add_or_inc (insn
, false))
1032 /* Next use was not an add. Look for one extra case. It could be
1039 if we reverse the operands in the mem ref we would
1040 find this. Only try it once though. */
1041 if (first_try
&& !mem_insn
.reg1_is_const
)
1044 return find_inc (false);
1050 /* Need to assure that none of the operands of the inc instruction are
1051 assigned to by the mem insn. */
1052 for (def_rec
= DF_INSN_DEFS (mem_insn
.insn
); *def_rec
; def_rec
++)
1054 struct df_ref
*def
= *def_rec
;
1055 unsigned int regno
= DF_REF_REGNO (def
);
1056 if ((regno
== REGNO (inc_insn
.reg0
))
1057 || (regno
== REGNO (inc_insn
.reg_res
)))
1060 fprintf (dump_file
, "inc conflicts with store failure.\n");
1063 if (!inc_insn
.reg1_is_const
&& (regno
== REGNO (inc_insn
.reg1
)))
1066 fprintf (dump_file
, "inc conflicts with store failure.\n");
1072 dump_inc_insn (dump_file
);
1074 if (inc_insn
.form
== FORM_POST_ADD
)
1076 /* Make sure that there is no insn that assigns to inc_insn.res
1077 between the mem_insn and the inc_insn. */
1078 rtx other_insn
= get_next_ref (REGNO (inc_insn
.reg_res
),
1079 BASIC_BLOCK (BLOCK_NUM (mem_insn
.insn
)),
1081 if (other_insn
!= inc_insn
.insn
)
1085 "result of add is assigned to between mem and inc insns.\n");
1089 other_insn
= get_next_ref (REGNO (inc_insn
.reg_res
),
1090 BASIC_BLOCK (BLOCK_NUM (mem_insn
.insn
)),
1093 && (other_insn
!= inc_insn
.insn
)
1094 && (DF_INSN_LUID (inc_insn
.insn
) > DF_INSN_LUID (other_insn
)))
1098 "result of add is used between mem and inc insns.\n");
1102 /* For the post_add to work, the result_reg of the inc must not be
1103 used in the mem insn since this will become the new index
1105 if (count_occurrences (PATTERN (mem_insn
.insn
), inc_insn
.reg_res
, 1) != 0)
1108 fprintf (dump_file
, "base reg replacement failure.\n");
1113 if (mem_insn
.reg1_is_const
)
1115 if (mem_insn
.reg1_val
== 0)
1117 if (!inc_insn
.reg1_is_const
)
1119 /* The mem looks like *r0 and the rhs of the add has two
1121 int luid
= DF_INSN_LUID (inc_insn
.insn
);
1122 if (inc_insn
.form
== FORM_POST_ADD
)
1124 /* The trick is that we are not going to increment r0,
1125 we are going to increment the result of the add insn.
1126 For this trick to be correct, the result reg of
1127 the inc must be a valid addressing reg. */
1128 if (GET_MODE (inc_insn
.reg_res
) != Pmode
)
1131 fprintf (dump_file
, "base reg mode failure.\n");
1135 /* We also need to make sure that the next use of
1136 inc result is after the inc. */
1138 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_use
);
1139 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1142 if (!rtx_equal_p (mem_insn
.reg0
, inc_insn
.reg0
))
1147 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_def
);
1148 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1152 /* Both the inc/add and the mem have a constant. Need to check
1153 that the constants are ok. */
1154 else if ((mem_insn
.reg1_val
!= inc_insn
.reg1_val
)
1155 && (mem_insn
.reg1_val
!= -inc_insn
.reg1_val
))
1160 /* The mem insn is of the form *(a + b) where a and b are both
1161 regs. It may be that in order to match the add or inc we
1162 need to treat it as if it was *(b + a). It may also be that
1163 the add is of the form a + c where c does not match b and
1164 then we just abandon this. */
1166 int luid
= DF_INSN_LUID (inc_insn
.insn
);
1169 /* Make sure this reg appears only once in this insn. */
1170 if (count_occurrences (PATTERN (mem_insn
.insn
), mem_insn
.reg1
, 1) != 1)
1173 if (inc_insn
.form
== FORM_POST_ADD
)
1175 /* For this trick to be correct, the result reg of the inc
1176 must be a valid addressing reg. */
1177 if (GET_MODE (inc_insn
.reg_res
) != Pmode
)
1180 fprintf (dump_file
, "base reg mode failure.\n");
1184 if (rtx_equal_p (mem_insn
.reg0
, inc_insn
.reg0
))
1186 if (!rtx_equal_p (mem_insn
.reg1
, inc_insn
.reg1
))
1188 /* See comment above on find_inc (false) call. */
1192 return find_inc (false);
1198 /* Need to check that there are no assignments to b
1199 before the add insn. */
1201 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_def
);
1202 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1204 /* All ok for the next step. */
1208 /* We know that mem_insn.reg0 must equal inc_insn.reg1
1209 or else we would not have found the inc insn. */
1211 if (!rtx_equal_p (mem_insn
.reg0
, inc_insn
.reg0
))
1213 /* See comment above on find_inc (false) call. */
1215 return find_inc (false);
1219 /* To have gotten here know that.
1224 We also know that the lhs of the inc is not b or a. We
1225 need to make sure that there are no assignments to b
1226 between the mem ref and the inc. */
1229 = get_next_ref (REGNO (inc_insn
.reg0
), bb
, reg_next_def
);
1230 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1234 /* Need to check that the next use of the add result is later than
1235 add insn since this will be the reg incremented. */
1237 = get_next_ref (REGNO (inc_insn
.reg_res
), bb
, reg_next_use
);
1238 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1241 else /* FORM_POST_INC. There is less to check here because we
1242 know that operands must line up. */
1244 if (!rtx_equal_p (mem_insn
.reg1
, inc_insn
.reg1
))
1245 /* See comment above on find_inc (false) call. */
1250 return find_inc (false);
1256 /* To have gotten here know that.
1261 We also know that the lhs of the inc is not b. We need to make
1262 sure that there are no assignments to b between the mem ref and
1265 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_def
);
1266 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1271 if (inc_insn
.form
== FORM_POST_INC
)
1274 = get_next_ref (REGNO (inc_insn
.reg0
), bb
, reg_next_use
);
1275 /* When we found inc_insn, we were looking for the
1276 next add or inc, not the next insn that used the
1277 reg. Because we are going to increment the reg
1278 in this form, we need to make sure that there
1279 were no interveining uses of reg. */
1280 if (inc_insn
.insn
!= other_insn
)
1284 return try_merge ();
1288 /* A recursive function that walks ADDRESS_OF_X to find all of the mem
1289 uses in pat that could be used as an auto inc or dec. It then
1290 calls FIND_INC for each one. */
1293 find_mem (rtx
*address_of_x
)
1295 rtx x
= *address_of_x
;
1296 enum rtx_code code
= GET_CODE (x
);
1297 const char *const fmt
= GET_RTX_FORMAT (code
);
1300 if (code
== MEM
&& REG_P (XEXP (x
, 0)))
1302 /* Match with *reg0. */
1303 mem_insn
.mem_loc
= address_of_x
;
1304 mem_insn
.reg0
= XEXP (x
, 0);
1305 mem_insn
.reg1_is_const
= true;
1306 mem_insn
.reg1_val
= 0;
1307 mem_insn
.reg1
= GEN_INT (0);
1308 if (find_inc (true))
1311 if (code
== MEM
&& GET_CODE (XEXP (x
, 0)) == PLUS
1312 && REG_P (XEXP (XEXP (x
, 0), 0)))
1314 rtx reg1
= XEXP (XEXP (x
, 0), 1);
1315 mem_insn
.mem_loc
= address_of_x
;
1316 mem_insn
.reg0
= XEXP (XEXP (x
, 0), 0);
1317 mem_insn
.reg1
= reg1
;
1318 if (GET_CODE (reg1
) == CONST_INT
)
1320 mem_insn
.reg1_is_const
= true;
1321 /* Match with *(reg0 + c) where c is a const. */
1322 mem_insn
.reg1_val
= INTVAL (reg1
);
1323 if (find_inc (true))
1326 else if (REG_P (reg1
))
1328 /* Match with *(reg0 + reg1). */
1329 mem_insn
.reg1_is_const
= false;
1330 if (find_inc (true))
1335 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
1337 /* If REG occurs inside a MEM used in a bit-field reference,
1338 that is unacceptable. */
1342 /* Time for some deep diving. */
1343 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1347 if (find_mem (&XEXP (x
, i
)))
1350 else if (fmt
[i
] == 'E')
1353 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1354 if (find_mem (&XVECEXP (x
, i
, j
)))
1362 /* Try to combine all incs and decs by constant values with memory
1363 references in BB. */
1366 merge_in_block (int max_reg
, basic_block bb
)
1370 int success_in_block
= 0;
1373 fprintf (dump_file
, "\n\nstarting bb %d\n", bb
->index
);
1375 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, curr
)
1377 unsigned int uid
= INSN_UID (insn
);
1378 bool insn_is_add_or_inc
= true;
1383 /* This continue is deliberate. We do not want the uses of the
1384 jump put into reg_next_use because it is not considered safe to
1385 combine a preincrement with a jump. */
1390 dump_insn_slim (dump_file
, insn
);
1392 /* Does this instruction increment or decrement a register? */
1393 if (parse_add_or_inc (insn
, true))
1395 int regno
= REGNO (inc_insn
.reg_res
);
1396 /* Cannot handle case where there are three separate regs
1397 before a mem ref. Too many moves would be needed to be
1399 if ((inc_insn
.form
== FORM_PRE_INC
) || inc_insn
.reg1_is_const
)
1401 mem_insn
.insn
= get_next_ref (regno
, bb
, reg_next_use
);
1405 if (!inc_insn
.reg1_is_const
)
1407 /* We are only here if we are going to try a
1408 HAVE_*_MODIFY_REG type transformation. c is a
1409 reg and we must sure that the path from the
1410 inc_insn to the mem_insn.insn is both def and use
1411 clear of c because the inc insn is going to move
1412 into the mem_insn.insn. */
1413 int luid
= DF_INSN_LUID (mem_insn
.insn
);
1415 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_use
);
1417 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1421 = get_next_ref (REGNO (inc_insn
.reg1
), bb
, reg_next_def
);
1423 if (other_insn
&& luid
> DF_INSN_LUID (other_insn
))
1428 dump_inc_insn (dump_file
);
1430 if (ok
&& find_address (&PATTERN (mem_insn
.insn
)) == -1)
1433 dump_mem_insn (dump_file
);
1437 insn_is_add_or_inc
= false;
1445 insn_is_add_or_inc
= false;
1446 mem_insn
.insn
= insn
;
1447 if (find_mem (&PATTERN (insn
)))
1451 /* If the inc insn was merged with a mem, the inc insn is gone
1452 and there is noting to update. */
1453 if (DF_INSN_UID_GET(uid
))
1455 struct df_ref
**def_rec
;
1456 struct df_ref
**use_rec
;
1457 /* Need to update next use. */
1458 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
1460 struct df_ref
*def
= *def_rec
;
1461 reg_next_use
[DF_REF_REGNO (def
)] = NULL
;
1462 reg_next_inc_use
[DF_REF_REGNO (def
)] = NULL
;
1463 reg_next_def
[DF_REF_REGNO (def
)] = insn
;
1466 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
1468 struct df_ref
*use
= *use_rec
;
1469 reg_next_use
[DF_REF_REGNO (use
)] = insn
;
1470 if (insn_is_add_or_inc
)
1471 reg_next_inc_use
[DF_REF_REGNO (use
)] = insn
;
1473 reg_next_inc_use
[DF_REF_REGNO (use
)] = NULL
;
1477 fprintf (dump_file
, "skipping update of deleted insn %d\n", uid
);
1480 /* If we were successful, try again. There may have been several
1481 opportunities that were interleaved. This is rare but
1482 gcc.c-torture/compile/pr17273.c actually exhibits this. */
1483 if (success_in_block
)
1485 /* In this case, we must clear these vectors since the trick of
1486 testing if the stale insn in the block will not work. */
1487 memset (reg_next_use
, 0, max_reg
* sizeof(rtx
));
1488 memset (reg_next_inc_use
, 0, max_reg
* sizeof(rtx
));
1489 memset (reg_next_def
, 0, max_reg
* sizeof(rtx
));
1490 df_recompute_luids (bb
);
1491 merge_in_block (max_reg
, bb
);
1498 rest_of_handle_auto_inc_dec (void)
1502 int max_reg
= max_reg_num ();
1505 init_decision_table ();
1507 mem_tmp
= gen_rtx_MEM (Pmode
, NULL_RTX
);
1509 df_note_add_problem ();
1512 reg_next_use
= XCNEWVEC (rtx
, max_reg
);
1513 reg_next_inc_use
= XCNEWVEC (rtx
, max_reg
);
1514 reg_next_def
= XCNEWVEC (rtx
, max_reg
);
1516 merge_in_block (max_reg
, bb
);
1518 free (reg_next_use
);
1519 free (reg_next_inc_use
);
1520 free (reg_next_def
);
1528 /* Discover auto-inc auto-dec instructions. */
1531 gate_auto_inc_dec (void)
1534 return (optimize
> 0 && flag_auto_inc_dec
);
1541 struct tree_opt_pass pass_inc_dec
=
1543 "auto-inc-dec", /* name */
1544 gate_auto_inc_dec
, /* gate */
1545 rest_of_handle_auto_inc_dec
, /* execute */
1548 0, /* static_pass_number */
1549 TV_AUTO_INC_DEC
, /* tv_id */
1550 0, /* properties_required */
1551 0, /* properties_provided */
1552 0, /* properties_destroyed */
1553 0, /* todo_flags_start */
1555 TODO_df_finish
, /* todo_flags_finish */