1 /* Code for RTL register eliminations.
2 Copyright (C) 2010-2013 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.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/>. */
21 /* Eliminable registers (like a soft argument or frame pointer) are
22 widely used in RTL. These eliminable registers should be replaced
23 by real hard registers (like the stack pointer or hard frame
24 pointer) plus some offset. The offsets usually change whenever the
25 stack is expanded. We know the final offsets only at the very end
28 Within LRA, we usually keep the RTL in such a state that the
29 eliminable registers can be replaced by just the corresponding hard
30 register (without any offset). To achieve this we should add the
31 initial elimination offset at the beginning of LRA and update the
32 offsets whenever the stack is expanded. We need to do this before
33 every constraint pass because the choice of offset often affects
34 whether a particular address or memory constraint is satisfied.
36 We keep RTL code at most time in such state that the virtual
37 registers can be changed by just the corresponding hard registers
38 (with zero offsets) and we have the right RTL code. To achieve this
39 we should add initial offset at the beginning of LRA work and update
40 offsets after each stack expanding. But actually we update virtual
41 registers to the same virtual registers + corresponding offsets
42 before every constraint pass because it affects constraint
43 satisfaction (e.g. an address displacement became too big for some
46 The final change of eliminable registers to the corresponding hard
47 registers are done at the very end of LRA when there were no change
56 #include "coretypes.h"
58 #include "hard-reg-set.h"
62 #include "insn-config.h"
63 #include "insn-codes.h"
66 #include "addresses.h"
70 #include "basic-block.h"
75 #include "rtl-error.h"
78 /* This structure is used to record information about hard register
82 /* Hard register number to be eliminated. */
84 /* Hard register number used as replacement. */
86 /* Difference between values of the two hard registers above on
87 previous iteration. */
88 HOST_WIDE_INT previous_offset
;
89 /* Difference between the values on the current iteration. */
91 /* Nonzero if this elimination can be done. */
93 /* CAN_ELIMINATE since the last check. */
94 bool prev_can_eliminate
;
95 /* REG rtx for the register to be eliminated. We cannot simply
96 compare the number since we might then spuriously replace a hard
97 register corresponding to a pseudo assigned to the reg to be
100 /* REG rtx for the replacement. */
104 /* The elimination table. Each array entry describes one possible way
105 of eliminating a register in favor of another. If there is more
106 than one way of eliminating a particular register, the most
107 preferred should be specified first. */
108 static struct elim_table
*reg_eliminate
= 0;
110 /* This is an intermediate structure to initialize the table. It has
111 exactly the members provided by ELIMINABLE_REGS. */
112 static const struct elim_table_1
116 } reg_eliminate_1
[] =
118 /* If a set of eliminable hard registers was specified, define the
119 table from it. Otherwise, default to the normal case of the frame
120 pointer being replaced by the stack pointer. */
122 #ifdef ELIMINABLE_REGS
125 {{ FRAME_POINTER_REGNUM
, STACK_POINTER_REGNUM
}};
128 #define NUM_ELIMINABLE_REGS ARRAY_SIZE (reg_eliminate_1)
130 /* Print info about elimination table to file F. */
132 print_elim_table (FILE *f
)
134 struct elim_table
*ep
;
136 for (ep
= reg_eliminate
; ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
]; ep
++)
137 fprintf (f
, "%s eliminate %d to %d (offset=" HOST_WIDE_INT_PRINT_DEC
138 ", prev_offset=" HOST_WIDE_INT_PRINT_DEC
")\n",
139 ep
->can_eliminate
? "Can" : "Can't",
140 ep
->from
, ep
->to
, ep
->offset
, ep
->previous_offset
);
143 /* Print info about elimination table to stderr. */
145 lra_debug_elim_table (void)
147 print_elim_table (stderr
);
150 /* Setup possibility of elimination in elimination table element EP to
151 VALUE. Setup FRAME_POINTER_NEEDED if elimination from frame
152 pointer to stack pointer is not possible anymore. */
154 setup_can_eliminate (struct elim_table
*ep
, bool value
)
156 ep
->can_eliminate
= ep
->prev_can_eliminate
= value
;
158 && ep
->from
== FRAME_POINTER_REGNUM
&& ep
->to
== STACK_POINTER_REGNUM
)
159 frame_pointer_needed
= 1;
162 /* Map: eliminable "from" register -> its current elimination,
163 or NULL if none. The elimination table may contain more than
164 one elimination for the same hard register, but this map specifies
165 the one that we are currently using. */
166 static struct elim_table
*elimination_map
[FIRST_PSEUDO_REGISTER
];
168 /* When an eliminable hard register becomes not eliminable, we use the
169 following special structure to restore original offsets for the
171 static struct elim_table self_elim_table
;
173 /* Offsets should be used to restore original offsets for eliminable
174 hard register which just became not eliminable. Zero,
176 static HOST_WIDE_INT self_elim_offsets
[FIRST_PSEUDO_REGISTER
];
178 /* Map: hard regno -> RTL presentation. RTL presentations of all
179 potentially eliminable hard registers are stored in the map. */
180 static rtx eliminable_reg_rtx
[FIRST_PSEUDO_REGISTER
];
182 /* Set up ELIMINATION_MAP of the currently used eliminations. */
184 setup_elimination_map (void)
187 struct elim_table
*ep
;
189 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
190 elimination_map
[i
] = NULL
;
191 for (ep
= reg_eliminate
; ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
]; ep
++)
192 if (ep
->can_eliminate
&& elimination_map
[ep
->from
] == NULL
)
193 elimination_map
[ep
->from
] = ep
;
198 /* Compute the sum of X and Y, making canonicalizations assumed in an
199 address, namely: sum constant integers, surround the sum of two
200 constants with a CONST, put the constant as the second operand, and
201 group the constant on the outermost sum.
203 This routine assumes both inputs are already in canonical form. */
205 form_sum (rtx x
, rtx y
)
208 enum machine_mode mode
= GET_MODE (x
);
210 if (mode
== VOIDmode
)
213 if (mode
== VOIDmode
)
217 return plus_constant (mode
, y
, INTVAL (x
));
218 else if (CONST_INT_P (y
))
219 return plus_constant (mode
, x
, INTVAL (y
));
220 else if (CONSTANT_P (x
))
221 tem
= x
, x
= y
, y
= tem
;
223 if (GET_CODE (x
) == PLUS
&& CONSTANT_P (XEXP (x
, 1)))
224 return form_sum (XEXP (x
, 0), form_sum (XEXP (x
, 1), y
));
226 /* Note that if the operands of Y are specified in the opposite
227 order in the recursive calls below, infinite recursion will
229 if (GET_CODE (y
) == PLUS
&& CONSTANT_P (XEXP (y
, 1)))
230 return form_sum (form_sum (x
, XEXP (y
, 0)), XEXP (y
, 1));
232 /* If both constant, encapsulate sum. Otherwise, just form sum. A
233 constant will have been placed second. */
234 if (CONSTANT_P (x
) && CONSTANT_P (y
))
236 if (GET_CODE (x
) == CONST
)
238 if (GET_CODE (y
) == CONST
)
241 return gen_rtx_CONST (VOIDmode
, gen_rtx_PLUS (mode
, x
, y
));
244 return gen_rtx_PLUS (mode
, x
, y
);
247 /* Return the current substitution hard register of the elimination of
248 HARD_REGNO. If HARD_REGNO is not eliminable, return itself. */
250 lra_get_elimination_hard_regno (int hard_regno
)
252 struct elim_table
*ep
;
254 if (hard_regno
< 0 || hard_regno
>= FIRST_PSEUDO_REGISTER
)
256 if ((ep
= elimination_map
[hard_regno
]) == NULL
)
261 /* Return elimination which will be used for hard reg REG, NULL
263 static struct elim_table
*
264 get_elimination (rtx reg
)
267 struct elim_table
*ep
;
268 HOST_WIDE_INT offset
;
270 lra_assert (REG_P (reg
));
271 if ((hard_regno
= REGNO (reg
)) < 0 || hard_regno
>= FIRST_PSEUDO_REGISTER
)
273 if ((ep
= elimination_map
[hard_regno
]) != NULL
)
274 return ep
->from_rtx
!= reg
? NULL
: ep
;
275 if ((offset
= self_elim_offsets
[hard_regno
]) == 0)
277 /* This is an iteration to restore offsets just after HARD_REGNO
278 stopped to be eliminable. */
279 self_elim_table
.from
= self_elim_table
.to
= hard_regno
;
280 self_elim_table
.from_rtx
281 = self_elim_table
.to_rtx
282 = eliminable_reg_rtx
[hard_regno
];
283 lra_assert (self_elim_table
.from_rtx
!= NULL
);
284 self_elim_table
.offset
= offset
;
285 return &self_elim_table
;
288 /* Scan X and replace any eliminable registers (such as fp) with a
289 replacement (such as sp) if SUBST_P, plus an offset. The offset is
290 a change in the offset between the eliminable register and its
291 substitution if UPDATE_P, or the full offset if FULL_P, or
294 MEM_MODE is the mode of an enclosing MEM. We need this to know how
295 much to adjust a register for, e.g., PRE_DEC. Also, if we are
296 inside a MEM, we are allowed to replace a sum of a hard register
297 and the constant zero with the hard register, which we cannot do
298 outside a MEM. In addition, we need to record the fact that a
299 hard register is referenced outside a MEM.
301 Alternatively, INSN may be a note (an EXPR_LIST or INSN_LIST).
302 That's used when we eliminate in expressions stored in notes. */
304 lra_eliminate_regs_1 (rtx x
, enum machine_mode mem_mode
,
305 bool subst_p
, bool update_p
, bool full_p
)
307 enum rtx_code code
= GET_CODE (x
);
308 struct elim_table
*ep
;
314 if (! current_function_decl
)
332 /* First handle the case where we encounter a bare hard register
333 that is eliminable. Replace it with a PLUS. */
334 if ((ep
= get_elimination (x
)) != NULL
)
336 rtx to
= subst_p
? ep
->to_rtx
: ep
->from_rtx
;
339 return plus_constant (Pmode
, to
, ep
->offset
- ep
->previous_offset
);
341 return plus_constant (Pmode
, to
, ep
->offset
);
348 /* If this is the sum of an eliminable register and a constant, rework
350 if (REG_P (XEXP (x
, 0)) && CONSTANT_P (XEXP (x
, 1)))
352 if ((ep
= get_elimination (XEXP (x
, 0))) != NULL
)
354 HOST_WIDE_INT offset
;
355 rtx to
= subst_p
? ep
->to_rtx
: ep
->from_rtx
;
357 if (! update_p
&& ! full_p
)
358 return gen_rtx_PLUS (Pmode
, to
, XEXP (x
, 1));
361 ? ep
->offset
- ep
->previous_offset
: ep
->offset
);
362 if (CONST_INT_P (XEXP (x
, 1))
363 && INTVAL (XEXP (x
, 1)) == -offset
)
366 return gen_rtx_PLUS (Pmode
, to
,
367 plus_constant (Pmode
,
368 XEXP (x
, 1), offset
));
371 /* If the hard register is not eliminable, we are done since
372 the other operand is a constant. */
376 /* If this is part of an address, we want to bring any constant
377 to the outermost PLUS. We will do this by doing hard
378 register replacement in our operands and seeing if a constant
379 shows up in one of them.
381 Note that there is no risk of modifying the structure of the
382 insn, since we only get called for its operands, thus we are
383 either modifying the address inside a MEM, or something like
384 an address operand of a load-address insn. */
387 rtx new0
= lra_eliminate_regs_1 (XEXP (x
, 0), mem_mode
,
388 subst_p
, update_p
, full_p
);
389 rtx new1
= lra_eliminate_regs_1 (XEXP (x
, 1), mem_mode
,
390 subst_p
, update_p
, full_p
);
392 if (new0
!= XEXP (x
, 0) || new1
!= XEXP (x
, 1))
393 return form_sum (new0
, new1
);
398 /* If this is the product of an eliminable hard register and a
399 constant, apply the distribute law and move the constant out
400 so that we have (plus (mult ..) ..). This is needed in order
401 to keep load-address insns valid. This case is pathological.
402 We ignore the possibility of overflow here. */
403 if (REG_P (XEXP (x
, 0)) && CONST_INT_P (XEXP (x
, 1))
404 && (ep
= get_elimination (XEXP (x
, 0))) != NULL
)
406 rtx to
= subst_p
? ep
->to_rtx
: ep
->from_rtx
;
410 plus_constant (Pmode
,
411 gen_rtx_MULT (Pmode
, to
, XEXP (x
, 1)),
412 (ep
->offset
- ep
->previous_offset
)
413 * INTVAL (XEXP (x
, 1)));
416 plus_constant (Pmode
,
417 gen_rtx_MULT (Pmode
, to
, XEXP (x
, 1)),
418 ep
->offset
* INTVAL (XEXP (x
, 1)));
420 return gen_rtx_MULT (Pmode
, to
, XEXP (x
, 1));
423 /* ... fall through ... */
427 /* See comments before PLUS about handling MINUS. */
431 case AND
: case IOR
: case XOR
:
432 case ROTATERT
: case ROTATE
:
433 case ASHIFTRT
: case LSHIFTRT
: case ASHIFT
:
435 case GE
: case GT
: case GEU
: case GTU
:
436 case LE
: case LT
: case LEU
: case LTU
:
438 rtx new0
= lra_eliminate_regs_1 (XEXP (x
, 0), mem_mode
,
439 subst_p
, update_p
, full_p
);
440 rtx new1
= XEXP (x
, 1)
441 ? lra_eliminate_regs_1 (XEXP (x
, 1), mem_mode
,
442 subst_p
, update_p
, full_p
) : 0;
444 if (new0
!= XEXP (x
, 0) || new1
!= XEXP (x
, 1))
445 return gen_rtx_fmt_ee (code
, GET_MODE (x
), new0
, new1
);
450 /* If we have something in XEXP (x, 0), the usual case,
454 new_rtx
= lra_eliminate_regs_1 (XEXP (x
, 0), mem_mode
,
455 subst_p
, update_p
, full_p
);
456 if (new_rtx
!= XEXP (x
, 0))
458 /* If this is a REG_DEAD note, it is not valid anymore.
459 Using the eliminated version could result in creating a
460 REG_DEAD note for the stack or frame pointer. */
461 if (REG_NOTE_KIND (x
) == REG_DEAD
)
463 ? lra_eliminate_regs_1 (XEXP (x
, 1), mem_mode
,
464 subst_p
, update_p
, full_p
)
467 x
= alloc_reg_note (REG_NOTE_KIND (x
), new_rtx
, XEXP (x
, 1));
471 /* ... fall through ... */
474 /* Now do eliminations in the rest of the chain. If this was
475 an EXPR_LIST, this might result in allocating more memory than is
476 strictly needed, but it simplifies the code. */
479 new_rtx
= lra_eliminate_regs_1 (XEXP (x
, 1), mem_mode
,
480 subst_p
, update_p
, full_p
);
481 if (new_rtx
!= XEXP (x
, 1))
483 gen_rtx_fmt_ee (GET_CODE (x
), GET_MODE (x
),
484 XEXP (x
, 0), new_rtx
);
492 /* We do not support elimination of a register that is modified.
493 elimination_effects has already make sure that this does not
499 /* We do not support elimination of a hard register that is
500 modified. LRA has already make sure that this does not
501 happen. The only remaining case we need to consider here is
502 that the increment value may be an eliminable register. */
503 if (GET_CODE (XEXP (x
, 1)) == PLUS
504 && XEXP (XEXP (x
, 1), 0) == XEXP (x
, 0))
506 rtx new_rtx
= lra_eliminate_regs_1 (XEXP (XEXP (x
, 1), 1), mem_mode
,
507 subst_p
, update_p
, full_p
);
509 if (new_rtx
!= XEXP (XEXP (x
, 1), 1))
510 return gen_rtx_fmt_ee (code
, GET_MODE (x
), XEXP (x
, 0),
511 gen_rtx_PLUS (GET_MODE (x
),
512 XEXP (x
, 0), new_rtx
));
516 case STRICT_LOW_PART
:
518 case SIGN_EXTEND
: case ZERO_EXTEND
:
519 case TRUNCATE
: case FLOAT_EXTEND
: case FLOAT_TRUNCATE
:
520 case FLOAT
: case FIX
:
521 case UNSIGNED_FIX
: case UNSIGNED_FLOAT
:
530 new_rtx
= lra_eliminate_regs_1 (XEXP (x
, 0), mem_mode
,
531 subst_p
, update_p
, full_p
);
532 if (new_rtx
!= XEXP (x
, 0))
533 return gen_rtx_fmt_e (code
, GET_MODE (x
), new_rtx
);
537 new_rtx
= lra_eliminate_regs_1 (SUBREG_REG (x
), mem_mode
,
538 subst_p
, update_p
, full_p
);
540 if (new_rtx
!= SUBREG_REG (x
))
542 int x_size
= GET_MODE_SIZE (GET_MODE (x
));
543 int new_size
= GET_MODE_SIZE (GET_MODE (new_rtx
));
545 if (MEM_P (new_rtx
) && x_size
<= new_size
)
547 SUBREG_REG (x
) = new_rtx
;
548 alter_subreg (&x
, false);
552 return simplify_gen_subreg (GET_MODE (x
), new_rtx
,
553 GET_MODE (new_rtx
), SUBREG_BYTE (x
));
559 /* Our only special processing is to pass the mode of the MEM to our
560 recursive call and copy the flags. While we are here, handle this
561 case more efficiently. */
563 replace_equiv_address_nv
565 lra_eliminate_regs_1 (XEXP (x
, 0), GET_MODE (x
),
566 subst_p
, update_p
, full_p
));
569 /* Handle insn_list USE that a call to a pure function may generate. */
570 new_rtx
= lra_eliminate_regs_1 (XEXP (x
, 0), VOIDmode
,
571 subst_p
, update_p
, full_p
);
572 if (new_rtx
!= XEXP (x
, 0))
573 return gen_rtx_USE (GET_MODE (x
), new_rtx
);
584 /* Process each of our operands recursively. If any have changed, make a
586 fmt
= GET_RTX_FORMAT (code
);
587 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++, fmt
++)
591 new_rtx
= lra_eliminate_regs_1 (XEXP (x
, i
), mem_mode
,
592 subst_p
, update_p
, full_p
);
593 if (new_rtx
!= XEXP (x
, i
) && ! copied
)
595 x
= shallow_copy_rtx (x
);
598 XEXP (x
, i
) = new_rtx
;
600 else if (*fmt
== 'E')
603 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
605 new_rtx
= lra_eliminate_regs_1 (XVECEXP (x
, i
, j
), mem_mode
,
606 subst_p
, update_p
, full_p
);
607 if (new_rtx
!= XVECEXP (x
, i
, j
) && ! copied_vec
)
609 rtvec new_v
= gen_rtvec_v (XVECLEN (x
, i
),
613 x
= shallow_copy_rtx (x
);
619 XVECEXP (x
, i
, j
) = new_rtx
;
627 /* This function is used externally in subsequent passes of GCC. It
628 always does a full elimination of X. */
630 lra_eliminate_regs (rtx x
, enum machine_mode mem_mode
,
631 rtx insn ATTRIBUTE_UNUSED
)
633 return lra_eliminate_regs_1 (x
, mem_mode
, true, false, true);
636 /* Scan rtx X for references to elimination source or target registers
637 in contexts that would prevent the elimination from happening.
638 Update the table of eliminables to reflect the changed state.
639 MEM_MODE is the mode of an enclosing MEM rtx, or VOIDmode if not
642 mark_not_eliminable (rtx x
)
644 enum rtx_code code
= GET_CODE (x
);
645 struct elim_table
*ep
;
657 if (REG_P (XEXP (x
, 0)) && REGNO (XEXP (x
, 0)) < FIRST_PSEUDO_REGISTER
)
658 /* If we modify the source of an elimination rule, disable
659 it. Do the same if it is the source and not the hard frame
661 for (ep
= reg_eliminate
;
662 ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
];
664 if (ep
->from_rtx
== XEXP (x
, 0)
665 || (ep
->to_rtx
== XEXP (x
, 0)
666 && ep
->to_rtx
!= hard_frame_pointer_rtx
))
667 setup_can_eliminate (ep
, false);
671 if (REG_P (XEXP (x
, 0)) && REGNO (XEXP (x
, 0)) < FIRST_PSEUDO_REGISTER
)
672 /* If using a hard register that is the source of an eliminate
673 we still think can be performed, note it cannot be
674 performed since we don't know how this hard register is
676 for (ep
= reg_eliminate
;
677 ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
];
679 if (ep
->from_rtx
== XEXP (x
, 0)
680 && ep
->to_rtx
!= hard_frame_pointer_rtx
)
681 setup_can_eliminate (ep
, false);
685 if (REG_P (XEXP (x
, 0)) && REGNO (XEXP (x
, 0)) < FIRST_PSEUDO_REGISTER
)
686 /* If clobbering a hard register that is the replacement
687 register for an elimination we still think can be
688 performed, note that it cannot be performed. Otherwise, we
689 need not be concerned about it. */
690 for (ep
= reg_eliminate
;
691 ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
];
693 if (ep
->to_rtx
== XEXP (x
, 0)
694 && ep
->to_rtx
!= hard_frame_pointer_rtx
)
695 setup_can_eliminate (ep
, false);
699 /* Check for setting a hard register that we know about. */
700 if (REG_P (SET_DEST (x
)) && REGNO (SET_DEST (x
)) < FIRST_PSEUDO_REGISTER
)
702 /* See if this is setting the replacement hard register for
705 If DEST is the hard frame pointer, we do nothing because
706 we assume that all assignments to the frame pointer are
707 for non-local gotos and are being done at a time when
708 they are valid and do not disturb anything else. Some
709 machines want to eliminate a fake argument pointer (or
710 even a fake frame pointer) with either the real frame
711 pointer or the stack pointer. Assignments to the hard
712 frame pointer must not prevent this elimination. */
714 for (ep
= reg_eliminate
;
715 ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
];
717 if (ep
->to_rtx
== SET_DEST (x
)
718 && SET_DEST (x
) != hard_frame_pointer_rtx
719 && (! (SUPPORTS_STACK_ALIGNMENT
&& stack_realign_fp
720 && REGNO (ep
->to_rtx
) == STACK_POINTER_REGNUM
)
721 || GET_CODE (SET_SRC (x
)) != PLUS
722 || XEXP (SET_SRC (x
), 0) != SET_DEST (x
)
723 || ! CONST_INT_P (XEXP (SET_SRC (x
), 1))))
724 setup_can_eliminate (ep
, false);
727 mark_not_eliminable (SET_DEST (x
));
728 mark_not_eliminable (SET_SRC (x
));
735 fmt
= GET_RTX_FORMAT (code
);
736 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++, fmt
++)
739 mark_not_eliminable (XEXP (x
, i
));
740 else if (*fmt
== 'E')
741 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
742 mark_not_eliminable (XVECEXP (x
, i
, j
));
748 #ifdef HARD_FRAME_POINTER_REGNUM
750 /* Find offset equivalence note for reg WHAT in INSN and return the
751 found elmination offset. If the note is not found, return NULL.
752 Remove the found note. */
754 remove_reg_equal_offset_note (rtx insn
, rtx what
)
758 for (link_loc
= ®_NOTES (insn
);
759 (link
= *link_loc
) != NULL_RTX
;
760 link_loc
= &XEXP (link
, 1))
761 if (REG_NOTE_KIND (link
) == REG_EQUAL
762 && GET_CODE (XEXP (link
, 0)) == PLUS
763 && XEXP (XEXP (link
, 0), 0) == what
764 && CONST_INT_P (XEXP (XEXP (link
, 0), 1)))
766 *link_loc
= XEXP (link
, 1);
767 return XEXP (XEXP (link
, 0), 1);
774 /* Scan INSN and eliminate all eliminable hard registers in it.
776 If REPLACE_P is true, do the replacement destructively. Also
777 delete the insn as dead it if it is setting an eliminable register.
779 If REPLACE_P is false, just update the offsets while keeping the
780 base register the same. Attach the note about used elimination for
781 insns setting frame pointer to update elimination easy (without
782 parsing already generated elimination insns to find offset
783 previously used) in future. */
786 eliminate_regs_in_insn (rtx insn
, bool replace_p
)
788 int icode
= recog_memoized (insn
);
789 rtx old_set
= single_set (insn
);
792 rtx substed_operand
[MAX_RECOG_OPERANDS
];
793 rtx orig_operand
[MAX_RECOG_OPERANDS
];
794 struct elim_table
*ep
;
795 rtx plus_src
, plus_cst_src
;
796 lra_insn_recog_data_t id
;
797 struct lra_static_insn_data
*static_id
;
799 if (icode
< 0 && asm_noperands (PATTERN (insn
)) < 0 && ! DEBUG_INSN_P (insn
))
801 lra_assert (GET_CODE (PATTERN (insn
)) == USE
802 || GET_CODE (PATTERN (insn
)) == CLOBBER
803 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
807 /* Check for setting an eliminable register. */
808 if (old_set
!= 0 && REG_P (SET_DEST (old_set
))
809 && (ep
= get_elimination (SET_DEST (old_set
))) != NULL
)
811 bool delete_p
= replace_p
;
813 #ifdef HARD_FRAME_POINTER_REGNUM
814 /* If this is setting the frame pointer register to the hardware
815 frame pointer register and this is an elimination that will
816 be done (tested above), this insn is really adjusting the
817 frame pointer downward to compensate for the adjustment done
818 before a nonlocal goto. */
819 if (ep
->from
== FRAME_POINTER_REGNUM
820 && ep
->to
== HARD_FRAME_POINTER_REGNUM
)
822 rtx src
= SET_SRC (old_set
);
823 rtx off
= remove_reg_equal_offset_note (insn
, ep
->to_rtx
);
827 SET_DEST (old_set
) = ep
->to_rtx
;
828 lra_update_insn_recog_data (insn
);
831 else if (off
!= NULL_RTX
833 || (GET_CODE (src
) == PLUS
834 && XEXP (src
, 1) == ep
->to_rtx
835 && CONST_INT_P (XEXP (src
, 1))))
837 HOST_WIDE_INT offset
= (off
!= NULL_RTX
840 ? 0 : INTVAL (XEXP (src
, 1)));
842 offset
-= (ep
->offset
- ep
->previous_offset
);
843 src
= plus_constant (Pmode
, ep
->to_rtx
, offset
);
845 /* First see if this insn remains valid when we make
846 the change. If not, keep the INSN_CODE the same
847 and let the constraint pass fit it up. */
848 validate_change (insn
, &SET_SRC (old_set
), src
, 1);
849 validate_change (insn
, &SET_DEST (old_set
),
851 if (! apply_change_group ())
853 SET_SRC (old_set
) = src
;
854 SET_DEST (old_set
) = ep
->from_rtx
;
856 lra_update_insn_recog_data (insn
);
857 /* Add offset note for future updates. */
858 add_reg_note (insn
, REG_EQUAL
, src
);
863 /* We can't delete this insn, but needn't process it
864 since it won't be used unless something changes. */
869 /* This insn isn't serving a useful purpose. We delete it
870 when REPLACE is set. */
872 lra_delete_dead_insn (insn
);
876 /* We allow one special case which happens to work on all machines we
877 currently support: a single set with the source or a REG_EQUAL
878 note being a PLUS of an eliminable register and a constant. */
879 plus_src
= plus_cst_src
= 0;
880 if (old_set
&& REG_P (SET_DEST (old_set
)))
882 if (GET_CODE (SET_SRC (old_set
)) == PLUS
)
883 plus_src
= SET_SRC (old_set
);
884 /* First see if the source is of the form (plus (...) CST). */
886 && CONST_INT_P (XEXP (plus_src
, 1)))
887 plus_cst_src
= plus_src
;
888 /* Check that the first operand of the PLUS is a hard reg or
889 the lowpart subreg of one. */
892 rtx reg
= XEXP (plus_cst_src
, 0);
894 if (GET_CODE (reg
) == SUBREG
&& subreg_lowpart_p (reg
))
895 reg
= SUBREG_REG (reg
);
897 if (!REG_P (reg
) || REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
903 rtx reg
= XEXP (plus_cst_src
, 0);
904 HOST_WIDE_INT offset
= INTVAL (XEXP (plus_cst_src
, 1));
906 if (GET_CODE (reg
) == SUBREG
)
907 reg
= SUBREG_REG (reg
);
909 if (REG_P (reg
) && (ep
= get_elimination (reg
)) != NULL
)
911 rtx to_rtx
= replace_p
? ep
->to_rtx
: ep
->from_rtx
;
915 offset
+= (ep
->offset
- ep
->previous_offset
);
916 offset
= trunc_int_for_mode (offset
, GET_MODE (plus_cst_src
));
919 if (GET_CODE (XEXP (plus_cst_src
, 0)) == SUBREG
)
920 to_rtx
= gen_lowpart (GET_MODE (XEXP (plus_cst_src
, 0)), to_rtx
);
921 /* If we have a nonzero offset, and the source is already a
922 simple REG, the following transformation would increase
923 the cost of the insn by replacing a simple REG with (plus
924 (reg sp) CST). So try only when we already had a PLUS
926 if (offset
== 0 || plus_src
)
928 rtx new_src
= plus_constant (GET_MODE (to_rtx
), to_rtx
, offset
);
930 old_set
= single_set (insn
);
932 /* First see if this insn remains valid when we make the
933 change. If not, try to replace the whole pattern
934 with a simple set (this may help if the original insn
935 was a PARALLEL that was only recognized as single_set
936 due to REG_UNUSED notes). If this isn't valid
937 either, keep the INSN_CODE the same and let the
938 constraint pass fix it up. */
939 if (! validate_change (insn
, &SET_SRC (old_set
), new_src
, 0))
941 rtx new_pat
= gen_rtx_SET (VOIDmode
,
942 SET_DEST (old_set
), new_src
);
944 if (! validate_change (insn
, &PATTERN (insn
), new_pat
, 0))
945 SET_SRC (old_set
) = new_src
;
947 lra_update_insn_recog_data (insn
);
948 /* This can't have an effect on elimination offsets, so skip
955 /* Eliminate all eliminable registers occurring in operands that
956 can be handled by the constraint pass. */
957 id
= lra_get_insn_recog_data (insn
);
958 static_id
= id
->insn_static_data
;
960 for (i
= 0; i
< static_id
->n_operands
; i
++)
962 orig_operand
[i
] = *id
->operand_loc
[i
];
963 substed_operand
[i
] = *id
->operand_loc
[i
];
965 /* For an asm statement, every operand is eliminable. */
966 if (icode
< 0 || insn_data
[icode
].operand
[i
].eliminable
)
968 /* Check for setting a hard register that we know about. */
969 if (static_id
->operand
[i
].type
!= OP_IN
970 && REG_P (orig_operand
[i
]))
972 /* If we are assigning to a hard register that can be
973 eliminated, it must be as part of a PARALLEL, since
974 the code above handles single SETs. This reg can not
975 be longer eliminated -- it is forced by
976 mark_not_eliminable. */
977 for (ep
= reg_eliminate
;
978 ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
];
980 lra_assert (ep
->from_rtx
!= orig_operand
[i
]
981 || ! ep
->can_eliminate
);
984 /* Companion to the above plus substitution, we can allow
985 invariants as the source of a plain move. */
987 = lra_eliminate_regs_1 (*id
->operand_loc
[i
], VOIDmode
,
988 replace_p
, ! replace_p
, false);
989 if (substed_operand
[i
] != orig_operand
[i
])
997 /* Substitute the operands; the new values are in the substed_operand
999 for (i
= 0; i
< static_id
->n_operands
; i
++)
1000 *id
->operand_loc
[i
] = substed_operand
[i
];
1001 for (i
= 0; i
< static_id
->n_dups
; i
++)
1002 *id
->dup_loc
[i
] = substed_operand
[(int) static_id
->dup_num
[i
]];
1004 /* If we had a move insn but now we don't, re-recognize it.
1005 This will cause spurious re-recognition if the old move had a
1006 PARALLEL since the new one still will, but we can't call
1007 single_set without having put new body into the insn and the
1008 re-recognition won't hurt in this rare case. */
1009 id
= lra_update_insn_recog_data (insn
);
1010 static_id
= id
->insn_static_data
;
1013 /* Spill pseudos which are assigned to hard registers in SET. Add
1014 affected insns for processing in the subsequent constraint
1017 spill_pseudos (HARD_REG_SET set
)
1020 bitmap_head to_process
;
1023 if (hard_reg_set_empty_p (set
))
1025 if (lra_dump_file
!= NULL
)
1027 fprintf (lra_dump_file
, " Spilling non-eliminable hard regs:");
1028 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1029 if (TEST_HARD_REG_BIT (set
, i
))
1030 fprintf (lra_dump_file
, " %d", i
);
1031 fprintf (lra_dump_file
, "\n");
1033 bitmap_initialize (&to_process
, ®_obstack
);
1034 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_reg_num (); i
++)
1035 if (lra_reg_info
[i
].nrefs
!= 0 && reg_renumber
[i
] >= 0
1036 && overlaps_hard_reg_set_p (set
,
1037 PSEUDO_REGNO_MODE (i
), reg_renumber
[i
]))
1039 if (lra_dump_file
!= NULL
)
1040 fprintf (lra_dump_file
, " Spilling r%d(%d)\n",
1041 i
, reg_renumber
[i
]);
1042 reg_renumber
[i
] = -1;
1043 bitmap_ior_into (&to_process
, &lra_reg_info
[i
].insn_bitmap
);
1045 IOR_HARD_REG_SET (lra_no_alloc_regs
, set
);
1046 for (insn
= get_insns (); insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
1047 if (bitmap_bit_p (&to_process
, INSN_UID (insn
)))
1049 lra_push_insn (insn
);
1050 lra_set_used_insn_alternative (insn
, -1);
1052 bitmap_clear (&to_process
);
1055 /* Update all offsets and possibility for elimination on eliminable
1056 registers. Spill pseudos assigned to registers which became
1057 uneliminable, update LRA_NO_ALLOC_REGS and ELIMINABLE_REG_SET. Add
1058 insns to INSNS_WITH_CHANGED_OFFSETS containing eliminable hard
1059 registers whose offsets should be changed. Return true if any
1060 elimination offset changed. */
1062 update_reg_eliminate (bitmap insns_with_changed_offsets
)
1065 struct elim_table
*ep
, *ep1
;
1066 HARD_REG_SET temp_hard_reg_set
;
1068 /* Clear self elimination offsets. */
1069 for (ep
= reg_eliminate
; ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
]; ep
++)
1070 self_elim_offsets
[ep
->from
] = 0;
1071 CLEAR_HARD_REG_SET (temp_hard_reg_set
);
1072 for (ep
= reg_eliminate
; ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
]; ep
++)
1074 /* If it is a currently used elimination: update the previous
1076 if (elimination_map
[ep
->from
] == ep
)
1077 ep
->previous_offset
= ep
->offset
;
1079 prev
= ep
->prev_can_eliminate
;
1080 setup_can_eliminate (ep
, targetm
.can_eliminate (ep
->from
, ep
->to
));
1081 if (ep
->can_eliminate
&& ! prev
)
1083 /* It is possible that not eliminable register becomes
1084 eliminable because we took other reasons into account to
1085 set up eliminable regs in the initial set up. Just
1086 ignore new eliminable registers. */
1087 setup_can_eliminate (ep
, false);
1090 if (ep
->can_eliminate
!= prev
&& elimination_map
[ep
->from
] == ep
)
1092 /* We cannot use this elimination anymore -- find another
1094 if (lra_dump_file
!= NULL
)
1095 fprintf (lra_dump_file
,
1096 " Elimination %d to %d is not possible anymore\n",
1098 /* Mark that is not eliminable anymore. */
1099 elimination_map
[ep
->from
] = NULL
;
1100 for (ep1
= ep
+ 1; ep1
< ®_eliminate
[NUM_ELIMINABLE_REGS
]; ep1
++)
1101 if (ep1
->can_eliminate
&& ep1
->from
== ep
->from
)
1103 if (ep1
< ®_eliminate
[NUM_ELIMINABLE_REGS
])
1105 if (lra_dump_file
!= NULL
)
1106 fprintf (lra_dump_file
, " Using elimination %d to %d now\n",
1107 ep1
->from
, ep1
->to
);
1108 /* Prevent the hard register into which we eliminate now
1109 from the usage for pseudos. */
1110 SET_HARD_REG_BIT (temp_hard_reg_set
, ep1
->to
);
1111 lra_assert (ep1
->previous_offset
== 0);
1112 ep1
->previous_offset
= ep
->offset
;
1116 /* There is no elimination anymore just use the hard
1117 register `from' itself. Setup self elimination
1118 offset to restore the original offset values. */
1119 if (lra_dump_file
!= NULL
)
1120 fprintf (lra_dump_file
, " %d is not eliminable at all\n",
1122 self_elim_offsets
[ep
->from
] = -ep
->offset
;
1123 SET_HARD_REG_BIT (temp_hard_reg_set
, ep
->from
);
1124 if (ep
->offset
!= 0)
1125 bitmap_ior_into (insns_with_changed_offsets
,
1126 &lra_reg_info
[ep
->from
].insn_bitmap
);
1130 #ifdef ELIMINABLE_REGS
1131 INITIAL_ELIMINATION_OFFSET (ep
->from
, ep
->to
, ep
->offset
);
1133 INITIAL_FRAME_POINTER_OFFSET (ep
->offset
);
1136 IOR_HARD_REG_SET (lra_no_alloc_regs
, temp_hard_reg_set
);
1137 AND_COMPL_HARD_REG_SET (eliminable_regset
, temp_hard_reg_set
);
1138 spill_pseudos (temp_hard_reg_set
);
1139 setup_elimination_map ();
1141 for (ep
= reg_eliminate
; ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
]; ep
++)
1142 if (elimination_map
[ep
->from
] == ep
&& ep
->previous_offset
!= ep
->offset
)
1144 bitmap_ior_into (insns_with_changed_offsets
,
1145 &lra_reg_info
[ep
->from
].insn_bitmap
);
1147 /* Update offset when the eliminate offset have been
1149 lra_update_reg_val_offset (lra_reg_info
[ep
->from
].val
,
1150 ep
->offset
- ep
->previous_offset
);
1156 /* Initialize the table of hard registers to eliminate.
1157 Pre-condition: global flag frame_pointer_needed has been set before
1158 calling this function. */
1160 init_elim_table (void)
1163 struct elim_table
*ep
;
1164 #ifdef ELIMINABLE_REGS
1165 const struct elim_table_1
*ep1
;
1169 reg_eliminate
= XCNEWVEC (struct elim_table
, NUM_ELIMINABLE_REGS
);
1171 memset (self_elim_offsets
, 0, sizeof (self_elim_offsets
));
1172 /* Initiate member values which will be never changed. */
1173 self_elim_table
.can_eliminate
= self_elim_table
.prev_can_eliminate
= true;
1174 self_elim_table
.previous_offset
= 0;
1175 #ifdef ELIMINABLE_REGS
1176 for (ep
= reg_eliminate
, ep1
= reg_eliminate_1
;
1177 ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
]; ep
++, ep1
++)
1179 ep
->offset
= ep
->previous_offset
= 0;
1180 ep
->from
= ep1
->from
;
1182 value_p
= (targetm
.can_eliminate (ep
->from
, ep
->to
)
1183 && ! (ep
->to
== STACK_POINTER_REGNUM
1184 && frame_pointer_needed
1185 && (! SUPPORTS_STACK_ALIGNMENT
1186 || ! stack_realign_fp
)));
1187 setup_can_eliminate (ep
, value_p
);
1190 reg_eliminate
[0].offset
= reg_eliminate
[0].previous_offset
= 0;
1191 reg_eliminate
[0].from
= reg_eliminate_1
[0].from
;
1192 reg_eliminate
[0].to
= reg_eliminate_1
[0].to
;
1193 setup_can_eliminate (®_eliminate
[0], ! frame_pointer_needed
);
1196 /* Count the number of eliminable registers and build the FROM and TO
1197 REG rtx's. Note that code in gen_rtx_REG will cause, e.g.,
1198 gen_rtx_REG (Pmode, STACK_POINTER_REGNUM) to equal stack_pointer_rtx.
1199 We depend on this. */
1200 for (ep
= reg_eliminate
; ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
]; ep
++)
1202 ep
->from_rtx
= gen_rtx_REG (Pmode
, ep
->from
);
1203 ep
->to_rtx
= gen_rtx_REG (Pmode
, ep
->to
);
1204 eliminable_reg_rtx
[ep
->from
] = ep
->from_rtx
;
1208 /* Entry function for initialization of elimination once per
1211 lra_init_elimination (void)
1218 FOR_BB_INSNS (bb
, insn
)
1219 if (NONDEBUG_INSN_P (insn
))
1220 mark_not_eliminable (PATTERN (insn
));
1221 setup_elimination_map ();
1224 /* Eliminate hard reg given by its location LOC. */
1226 lra_eliminate_reg_if_possible (rtx
*loc
)
1229 struct elim_table
*ep
;
1231 lra_assert (REG_P (*loc
));
1232 if ((regno
= REGNO (*loc
)) >= FIRST_PSEUDO_REGISTER
1233 || ! TEST_HARD_REG_BIT (lra_no_alloc_regs
, regno
))
1235 if ((ep
= get_elimination (*loc
)) != NULL
)
1239 /* Do (final if FINAL_P) elimination in INSN. Add the insn for
1240 subsequent processing in the constraint pass, update the insn info. */
1242 process_insn_for_elimination (rtx insn
, bool final_p
)
1244 eliminate_regs_in_insn (insn
, final_p
);
1247 /* Check that insn changed its code. This is a case when a move
1248 insn becomes an add insn and we do not want to process the
1249 insn as a move anymore. */
1250 int icode
= recog (PATTERN (insn
), insn
, 0);
1252 if (icode
>= 0 && icode
!= INSN_CODE (insn
))
1254 INSN_CODE (insn
) = icode
;
1255 lra_update_insn_recog_data (insn
);
1257 lra_update_insn_regno_info (insn
);
1258 lra_push_insn (insn
);
1259 lra_set_used_insn_alternative (insn
, -1);
1263 /* Entry function to do final elimination if FINAL_P or to update
1264 elimination register offsets. */
1266 lra_eliminate (bool final_p
)
1270 rtx mem_loc
, invariant
;
1271 bitmap_head insns_with_changed_offsets
;
1273 struct elim_table
*ep
;
1274 int regs_num
= max_reg_num ();
1276 timevar_push (TV_LRA_ELIMINATE
);
1278 bitmap_initialize (&insns_with_changed_offsets
, ®_obstack
);
1281 #ifdef ENABLE_CHECKING
1282 update_reg_eliminate (&insns_with_changed_offsets
);
1283 if (! bitmap_empty_p (&insns_with_changed_offsets
))
1286 /* We change eliminable hard registers in insns so we should do
1287 this for all insns containing any eliminable hard
1289 for (ep
= reg_eliminate
; ep
< ®_eliminate
[NUM_ELIMINABLE_REGS
]; ep
++)
1290 if (elimination_map
[ep
->from
] != NULL
)
1291 bitmap_ior_into (&insns_with_changed_offsets
,
1292 &lra_reg_info
[ep
->from
].insn_bitmap
);
1294 else if (! update_reg_eliminate (&insns_with_changed_offsets
))
1295 goto lra_eliminate_done
;
1296 if (lra_dump_file
!= NULL
)
1298 fprintf (lra_dump_file
, "New elimination table:\n");
1299 print_elim_table (lra_dump_file
);
1301 for (i
= FIRST_PSEUDO_REGISTER
; i
< regs_num
; i
++)
1302 if (lra_reg_info
[i
].nrefs
!= 0)
1304 mem_loc
= ira_reg_equiv
[i
].memory
;
1305 if (mem_loc
!= NULL_RTX
)
1306 mem_loc
= lra_eliminate_regs_1 (mem_loc
, VOIDmode
,
1307 final_p
, ! final_p
, false);
1308 ira_reg_equiv
[i
].memory
= mem_loc
;
1309 invariant
= ira_reg_equiv
[i
].invariant
;
1310 if (invariant
!= NULL_RTX
)
1311 invariant
= lra_eliminate_regs_1 (invariant
, VOIDmode
,
1312 final_p
, ! final_p
, false);
1313 ira_reg_equiv
[i
].invariant
= invariant
;
1314 if (lra_dump_file
!= NULL
1315 && (mem_loc
!= NULL_RTX
|| invariant
!= NULL
))
1316 fprintf (lra_dump_file
,
1317 "Updating elimination of equiv for reg %d\n", i
);
1319 EXECUTE_IF_SET_IN_BITMAP (&insns_with_changed_offsets
, 0, uid
, bi
)
1320 process_insn_for_elimination (lra_insn_recog_data
[uid
]->insn
, final_p
);
1321 bitmap_clear (&insns_with_changed_offsets
);
1324 timevar_pop (TV_LRA_ELIMINATE
);