Split can_vec_perm_p into can_vec_perm_{var,const}_p
[official-gcc.git] / gcc / lra-constraints.c
blob73ffba2c75fc2cd85c42e275224013f05d35e337
1 /* Code for RTL transformations to satisfy insn constraints.
2 Copyright (C) 2010-2017 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
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 /* This file contains code for 3 passes: constraint pass,
23 inheritance/split pass, and pass for undoing failed inheritance and
24 split.
26 The major goal of constraint pass is to transform RTL to satisfy
27 insn and address constraints by:
28 o choosing insn alternatives;
29 o generating *reload insns* (or reloads in brief) and *reload
30 pseudos* which will get necessary hard registers later;
31 o substituting pseudos with equivalent values and removing the
32 instructions that initialized those pseudos.
34 The constraint pass has biggest and most complicated code in LRA.
35 There are a lot of important details like:
36 o reuse of input reload pseudos to simplify reload pseudo
37 allocations;
38 o some heuristics to choose insn alternative to improve the
39 inheritance;
40 o early clobbers etc.
42 The pass is mimicking former reload pass in alternative choosing
43 because the reload pass is oriented to current machine description
44 model. It might be changed if the machine description model is
45 changed.
47 There is special code for preventing all LRA and this pass cycling
48 in case of bugs.
50 On the first iteration of the pass we process every instruction and
51 choose an alternative for each one. On subsequent iterations we try
52 to avoid reprocessing instructions if we can be sure that the old
53 choice is still valid.
55 The inheritance/spilt pass is to transform code to achieve
56 ineheritance and live range splitting. It is done on backward
57 traversal of EBBs.
59 The inheritance optimization goal is to reuse values in hard
60 registers. There is analogous optimization in old reload pass. The
61 inheritance is achieved by following transformation:
63 reload_p1 <- p reload_p1 <- p
64 ... new_p <- reload_p1
65 ... => ...
66 reload_p2 <- p reload_p2 <- new_p
68 where p is spilled and not changed between the insns. Reload_p1 is
69 also called *original pseudo* and new_p is called *inheritance
70 pseudo*.
72 The subsequent assignment pass will try to assign the same (or
73 another if it is not possible) hard register to new_p as to
74 reload_p1 or reload_p2.
76 If the assignment pass fails to assign a hard register to new_p,
77 this file will undo the inheritance and restore the original code.
78 This is because implementing the above sequence with a spilled
79 new_p would make the code much worse. The inheritance is done in
80 EBB scope. The above is just a simplified example to get an idea
81 of the inheritance as the inheritance is also done for non-reload
82 insns.
84 Splitting (transformation) is also done in EBB scope on the same
85 pass as the inheritance:
87 r <- ... or ... <- r r <- ... or ... <- r
88 ... s <- r (new insn -- save)
89 ... =>
90 ... r <- s (new insn -- restore)
91 ... <- r ... <- r
93 The *split pseudo* s is assigned to the hard register of the
94 original pseudo or hard register r.
96 Splitting is done:
97 o In EBBs with high register pressure for global pseudos (living
98 in at least 2 BBs) and assigned to hard registers when there
99 are more one reloads needing the hard registers;
100 o for pseudos needing save/restore code around calls.
102 If the split pseudo still has the same hard register as the
103 original pseudo after the subsequent assignment pass or the
104 original pseudo was split, the opposite transformation is done on
105 the same pass for undoing inheritance. */
107 #undef REG_OK_STRICT
109 #include "config.h"
110 #include "system.h"
111 #include "coretypes.h"
112 #include "backend.h"
113 #include "target.h"
114 #include "rtl.h"
115 #include "tree.h"
116 #include "predict.h"
117 #include "df.h"
118 #include "memmodel.h"
119 #include "tm_p.h"
120 #include "expmed.h"
121 #include "optabs.h"
122 #include "regs.h"
123 #include "ira.h"
124 #include "recog.h"
125 #include "output.h"
126 #include "addresses.h"
127 #include "expr.h"
128 #include "cfgrtl.h"
129 #include "rtl-error.h"
130 #include "params.h"
131 #include "lra.h"
132 #include "lra-int.h"
133 #include "print-rtl.h"
135 /* Value of LRA_CURR_RELOAD_NUM at the beginning of BB of the current
136 insn. Remember that LRA_CURR_RELOAD_NUM is the number of emitted
137 reload insns. */
138 static int bb_reload_num;
140 /* The current insn being processed and corresponding its single set
141 (NULL otherwise), its data (basic block, the insn data, the insn
142 static data, and the mode of each operand). */
143 static rtx_insn *curr_insn;
144 static rtx curr_insn_set;
145 static basic_block curr_bb;
146 static lra_insn_recog_data_t curr_id;
147 static struct lra_static_insn_data *curr_static_id;
148 static machine_mode curr_operand_mode[MAX_RECOG_OPERANDS];
149 /* Mode of the register substituted by its equivalence with VOIDmode
150 (e.g. constant) and whose subreg is given operand of the current
151 insn. VOIDmode in all other cases. */
152 static machine_mode original_subreg_reg_mode[MAX_RECOG_OPERANDS];
156 /* Start numbers for new registers and insns at the current constraints
157 pass start. */
158 static int new_regno_start;
159 static int new_insn_uid_start;
161 /* If LOC is nonnull, strip any outer subreg from it. */
162 static inline rtx *
163 strip_subreg (rtx *loc)
165 return loc && GET_CODE (*loc) == SUBREG ? &SUBREG_REG (*loc) : loc;
168 /* Return hard regno of REGNO or if it is was not assigned to a hard
169 register, use a hard register from its allocno class. */
170 static int
171 get_try_hard_regno (int regno)
173 int hard_regno;
174 enum reg_class rclass;
176 if ((hard_regno = regno) >= FIRST_PSEUDO_REGISTER)
177 hard_regno = lra_get_regno_hard_regno (regno);
178 if (hard_regno >= 0)
179 return hard_regno;
180 rclass = lra_get_allocno_class (regno);
181 if (rclass == NO_REGS)
182 return -1;
183 return ira_class_hard_regs[rclass][0];
186 /* Return the hard regno of X after removing its subreg. If X is not
187 a register or a subreg of a register, return -1. If X is a pseudo,
188 use its assignment. If FINAL_P return the final hard regno which will
189 be after elimination. */
190 static int
191 get_hard_regno (rtx x, bool final_p)
193 rtx reg;
194 int hard_regno;
196 reg = x;
197 if (SUBREG_P (x))
198 reg = SUBREG_REG (x);
199 if (! REG_P (reg))
200 return -1;
201 if (! HARD_REGISTER_NUM_P (hard_regno = REGNO (reg)))
202 hard_regno = lra_get_regno_hard_regno (hard_regno);
203 if (hard_regno < 0)
204 return -1;
205 if (final_p)
206 hard_regno = lra_get_elimination_hard_regno (hard_regno);
207 if (SUBREG_P (x))
208 hard_regno += subreg_regno_offset (hard_regno, GET_MODE (reg),
209 SUBREG_BYTE (x), GET_MODE (x));
210 return hard_regno;
213 /* If REGNO is a hard register or has been allocated a hard register,
214 return the class of that register. If REGNO is a reload pseudo
215 created by the current constraints pass, return its allocno class.
216 Return NO_REGS otherwise. */
217 static enum reg_class
218 get_reg_class (int regno)
220 int hard_regno;
222 if (! HARD_REGISTER_NUM_P (hard_regno = regno))
223 hard_regno = lra_get_regno_hard_regno (regno);
224 if (hard_regno >= 0)
226 hard_regno = lra_get_elimination_hard_regno (hard_regno);
227 return REGNO_REG_CLASS (hard_regno);
229 if (regno >= new_regno_start)
230 return lra_get_allocno_class (regno);
231 return NO_REGS;
234 /* Return true if REG satisfies (or will satisfy) reg class constraint
235 CL. Use elimination first if REG is a hard register. If REG is a
236 reload pseudo created by this constraints pass, assume that it will
237 be allocated a hard register from its allocno class, but allow that
238 class to be narrowed to CL if it is currently a superset of CL.
240 If NEW_CLASS is nonnull, set *NEW_CLASS to the new allocno class of
241 REGNO (reg), or NO_REGS if no change in its class was needed. */
242 static bool
243 in_class_p (rtx reg, enum reg_class cl, enum reg_class *new_class)
245 enum reg_class rclass, common_class;
246 machine_mode reg_mode;
247 int class_size, hard_regno, nregs, i, j;
248 int regno = REGNO (reg);
250 if (new_class != NULL)
251 *new_class = NO_REGS;
252 if (regno < FIRST_PSEUDO_REGISTER)
254 rtx final_reg = reg;
255 rtx *final_loc = &final_reg;
257 lra_eliminate_reg_if_possible (final_loc);
258 return TEST_HARD_REG_BIT (reg_class_contents[cl], REGNO (*final_loc));
260 reg_mode = GET_MODE (reg);
261 rclass = get_reg_class (regno);
262 if (regno < new_regno_start
263 /* Do not allow the constraints for reload instructions to
264 influence the classes of new pseudos. These reloads are
265 typically moves that have many alternatives, and restricting
266 reload pseudos for one alternative may lead to situations
267 where other reload pseudos are no longer allocatable. */
268 || (INSN_UID (curr_insn) >= new_insn_uid_start
269 && curr_insn_set != NULL
270 && ((OBJECT_P (SET_SRC (curr_insn_set))
271 && ! CONSTANT_P (SET_SRC (curr_insn_set)))
272 || (GET_CODE (SET_SRC (curr_insn_set)) == SUBREG
273 && OBJECT_P (SUBREG_REG (SET_SRC (curr_insn_set)))
274 && ! CONSTANT_P (SUBREG_REG (SET_SRC (curr_insn_set)))))))
275 /* When we don't know what class will be used finally for reload
276 pseudos, we use ALL_REGS. */
277 return ((regno >= new_regno_start && rclass == ALL_REGS)
278 || (rclass != NO_REGS && ira_class_subset_p[rclass][cl]
279 && ! hard_reg_set_subset_p (reg_class_contents[cl],
280 lra_no_alloc_regs)));
281 else
283 common_class = ira_reg_class_subset[rclass][cl];
284 if (new_class != NULL)
285 *new_class = common_class;
286 if (hard_reg_set_subset_p (reg_class_contents[common_class],
287 lra_no_alloc_regs))
288 return false;
289 /* Check that there are enough allocatable regs. */
290 class_size = ira_class_hard_regs_num[common_class];
291 for (i = 0; i < class_size; i++)
293 hard_regno = ira_class_hard_regs[common_class][i];
294 nregs = hard_regno_nregs (hard_regno, reg_mode);
295 if (nregs == 1)
296 return true;
297 for (j = 0; j < nregs; j++)
298 if (TEST_HARD_REG_BIT (lra_no_alloc_regs, hard_regno + j)
299 || ! TEST_HARD_REG_BIT (reg_class_contents[common_class],
300 hard_regno + j))
301 break;
302 if (j >= nregs)
303 return true;
305 return false;
309 /* Return true if REGNO satisfies a memory constraint. */
310 static bool
311 in_mem_p (int regno)
313 return get_reg_class (regno) == NO_REGS;
316 /* Return 1 if ADDR is a valid memory address for mode MODE in address
317 space AS, and check that each pseudo has the proper kind of hard
318 reg. */
319 static int
320 valid_address_p (machine_mode mode ATTRIBUTE_UNUSED,
321 rtx addr, addr_space_t as)
323 #ifdef GO_IF_LEGITIMATE_ADDRESS
324 lra_assert (ADDR_SPACE_GENERIC_P (as));
325 GO_IF_LEGITIMATE_ADDRESS (mode, addr, win);
326 return 0;
328 win:
329 return 1;
330 #else
331 return targetm.addr_space.legitimate_address_p (mode, addr, 0, as);
332 #endif
335 namespace {
336 /* Temporarily eliminates registers in an address (for the lifetime of
337 the object). */
338 class address_eliminator {
339 public:
340 address_eliminator (struct address_info *ad);
341 ~address_eliminator ();
343 private:
344 struct address_info *m_ad;
345 rtx *m_base_loc;
346 rtx m_base_reg;
347 rtx *m_index_loc;
348 rtx m_index_reg;
352 address_eliminator::address_eliminator (struct address_info *ad)
353 : m_ad (ad),
354 m_base_loc (strip_subreg (ad->base_term)),
355 m_base_reg (NULL_RTX),
356 m_index_loc (strip_subreg (ad->index_term)),
357 m_index_reg (NULL_RTX)
359 if (m_base_loc != NULL)
361 m_base_reg = *m_base_loc;
362 lra_eliminate_reg_if_possible (m_base_loc);
363 if (m_ad->base_term2 != NULL)
364 *m_ad->base_term2 = *m_ad->base_term;
366 if (m_index_loc != NULL)
368 m_index_reg = *m_index_loc;
369 lra_eliminate_reg_if_possible (m_index_loc);
373 address_eliminator::~address_eliminator ()
375 if (m_base_loc && *m_base_loc != m_base_reg)
377 *m_base_loc = m_base_reg;
378 if (m_ad->base_term2 != NULL)
379 *m_ad->base_term2 = *m_ad->base_term;
381 if (m_index_loc && *m_index_loc != m_index_reg)
382 *m_index_loc = m_index_reg;
385 /* Return true if the eliminated form of AD is a legitimate target address. */
386 static bool
387 valid_address_p (struct address_info *ad)
389 address_eliminator eliminator (ad);
390 return valid_address_p (ad->mode, *ad->outer, ad->as);
393 /* Return true if the eliminated form of memory reference OP satisfies
394 extra (special) memory constraint CONSTRAINT. */
395 static bool
396 satisfies_memory_constraint_p (rtx op, enum constraint_num constraint)
398 struct address_info ad;
400 decompose_mem_address (&ad, op);
401 address_eliminator eliminator (&ad);
402 return constraint_satisfied_p (op, constraint);
405 /* Return true if the eliminated form of address AD satisfies extra
406 address constraint CONSTRAINT. */
407 static bool
408 satisfies_address_constraint_p (struct address_info *ad,
409 enum constraint_num constraint)
411 address_eliminator eliminator (ad);
412 return constraint_satisfied_p (*ad->outer, constraint);
415 /* Return true if the eliminated form of address OP satisfies extra
416 address constraint CONSTRAINT. */
417 static bool
418 satisfies_address_constraint_p (rtx op, enum constraint_num constraint)
420 struct address_info ad;
422 decompose_lea_address (&ad, &op);
423 return satisfies_address_constraint_p (&ad, constraint);
426 /* Initiate equivalences for LRA. As we keep original equivalences
427 before any elimination, we need to make copies otherwise any change
428 in insns might change the equivalences. */
429 void
430 lra_init_equiv (void)
432 ira_expand_reg_equiv ();
433 for (int i = FIRST_PSEUDO_REGISTER; i < max_reg_num (); i++)
435 rtx res;
437 if ((res = ira_reg_equiv[i].memory) != NULL_RTX)
438 ira_reg_equiv[i].memory = copy_rtx (res);
439 if ((res = ira_reg_equiv[i].invariant) != NULL_RTX)
440 ira_reg_equiv[i].invariant = copy_rtx (res);
444 static rtx loc_equivalence_callback (rtx, const_rtx, void *);
446 /* Update equivalence for REGNO. We need to this as the equivalence
447 might contain other pseudos which are changed by their
448 equivalences. */
449 static void
450 update_equiv (int regno)
452 rtx x;
454 if ((x = ira_reg_equiv[regno].memory) != NULL_RTX)
455 ira_reg_equiv[regno].memory
456 = simplify_replace_fn_rtx (x, NULL_RTX, loc_equivalence_callback,
457 NULL_RTX);
458 if ((x = ira_reg_equiv[regno].invariant) != NULL_RTX)
459 ira_reg_equiv[regno].invariant
460 = simplify_replace_fn_rtx (x, NULL_RTX, loc_equivalence_callback,
461 NULL_RTX);
464 /* If we have decided to substitute X with another value, return that
465 value, otherwise return X. */
466 static rtx
467 get_equiv (rtx x)
469 int regno;
470 rtx res;
472 if (! REG_P (x) || (regno = REGNO (x)) < FIRST_PSEUDO_REGISTER
473 || ! ira_reg_equiv[regno].defined_p
474 || ! ira_reg_equiv[regno].profitable_p
475 || lra_get_regno_hard_regno (regno) >= 0)
476 return x;
477 if ((res = ira_reg_equiv[regno].memory) != NULL_RTX)
479 if (targetm.cannot_substitute_mem_equiv_p (res))
480 return x;
481 return res;
483 if ((res = ira_reg_equiv[regno].constant) != NULL_RTX)
484 return res;
485 if ((res = ira_reg_equiv[regno].invariant) != NULL_RTX)
486 return res;
487 gcc_unreachable ();
490 /* If we have decided to substitute X with the equivalent value,
491 return that value after elimination for INSN, otherwise return
492 X. */
493 static rtx
494 get_equiv_with_elimination (rtx x, rtx_insn *insn)
496 rtx res = get_equiv (x);
498 if (x == res || CONSTANT_P (res))
499 return res;
500 return lra_eliminate_regs_1 (insn, res, GET_MODE (res),
501 false, false, 0, true);
504 /* Set up curr_operand_mode. */
505 static void
506 init_curr_operand_mode (void)
508 int nop = curr_static_id->n_operands;
509 for (int i = 0; i < nop; i++)
511 machine_mode mode = GET_MODE (*curr_id->operand_loc[i]);
512 if (mode == VOIDmode)
514 /* The .md mode for address operands is the mode of the
515 addressed value rather than the mode of the address itself. */
516 if (curr_id->icode >= 0 && curr_static_id->operand[i].is_address)
517 mode = Pmode;
518 else
519 mode = curr_static_id->operand[i].mode;
521 curr_operand_mode[i] = mode;
527 /* The page contains code to reuse input reloads. */
529 /* Structure describes input reload of the current insns. */
530 struct input_reload
532 /* True for input reload of matched operands. */
533 bool match_p;
534 /* Reloaded value. */
535 rtx input;
536 /* Reload pseudo used. */
537 rtx reg;
540 /* The number of elements in the following array. */
541 static int curr_insn_input_reloads_num;
542 /* Array containing info about input reloads. It is used to find the
543 same input reload and reuse the reload pseudo in this case. */
544 static struct input_reload curr_insn_input_reloads[LRA_MAX_INSN_RELOADS];
546 /* Initiate data concerning reuse of input reloads for the current
547 insn. */
548 static void
549 init_curr_insn_input_reloads (void)
551 curr_insn_input_reloads_num = 0;
554 /* Create a new pseudo using MODE, RCLASS, ORIGINAL or reuse already
555 created input reload pseudo (only if TYPE is not OP_OUT). Don't
556 reuse pseudo if IN_SUBREG_P is true and the reused pseudo should be
557 wrapped up in SUBREG. The result pseudo is returned through
558 RESULT_REG. Return TRUE if we created a new pseudo, FALSE if we
559 reused the already created input reload pseudo. Use TITLE to
560 describe new registers for debug purposes. */
561 static bool
562 get_reload_reg (enum op_type type, machine_mode mode, rtx original,
563 enum reg_class rclass, bool in_subreg_p,
564 const char *title, rtx *result_reg)
566 int i, regno;
567 enum reg_class new_class;
568 bool unique_p = false;
570 if (type == OP_OUT)
572 *result_reg
573 = lra_create_new_reg_with_unique_value (mode, original, rclass, title);
574 return true;
576 /* Prevent reuse value of expression with side effects,
577 e.g. volatile memory. */
578 if (! side_effects_p (original))
579 for (i = 0; i < curr_insn_input_reloads_num; i++)
581 if (! curr_insn_input_reloads[i].match_p
582 && rtx_equal_p (curr_insn_input_reloads[i].input, original)
583 && in_class_p (curr_insn_input_reloads[i].reg, rclass, &new_class))
585 rtx reg = curr_insn_input_reloads[i].reg;
586 regno = REGNO (reg);
587 /* If input is equal to original and both are VOIDmode,
588 GET_MODE (reg) might be still different from mode.
589 Ensure we don't return *result_reg with wrong mode. */
590 if (GET_MODE (reg) != mode)
592 if (in_subreg_p)
593 continue;
594 if (GET_MODE_SIZE (GET_MODE (reg)) < GET_MODE_SIZE (mode))
595 continue;
596 reg = lowpart_subreg (mode, reg, GET_MODE (reg));
597 if (reg == NULL_RTX || GET_CODE (reg) != SUBREG)
598 continue;
600 *result_reg = reg;
601 if (lra_dump_file != NULL)
603 fprintf (lra_dump_file, " Reuse r%d for reload ", regno);
604 dump_value_slim (lra_dump_file, original, 1);
606 if (new_class != lra_get_allocno_class (regno))
607 lra_change_class (regno, new_class, ", change to", false);
608 if (lra_dump_file != NULL)
609 fprintf (lra_dump_file, "\n");
610 return false;
612 /* If we have an input reload with a different mode, make sure it
613 will get a different hard reg. */
614 else if (REG_P (original)
615 && REG_P (curr_insn_input_reloads[i].input)
616 && REGNO (original) == REGNO (curr_insn_input_reloads[i].input)
617 && (GET_MODE (original)
618 != GET_MODE (curr_insn_input_reloads[i].input)))
619 unique_p = true;
621 *result_reg = (unique_p
622 ? lra_create_new_reg_with_unique_value
623 : lra_create_new_reg) (mode, original, rclass, title);
624 lra_assert (curr_insn_input_reloads_num < LRA_MAX_INSN_RELOADS);
625 curr_insn_input_reloads[curr_insn_input_reloads_num].input = original;
626 curr_insn_input_reloads[curr_insn_input_reloads_num].match_p = false;
627 curr_insn_input_reloads[curr_insn_input_reloads_num++].reg = *result_reg;
628 return true;
633 /* The page contains code to extract memory address parts. */
635 /* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudos. */
636 static inline bool
637 ok_for_index_p_nonstrict (rtx reg)
639 unsigned regno = REGNO (reg);
641 return regno >= FIRST_PSEUDO_REGISTER || REGNO_OK_FOR_INDEX_P (regno);
644 /* A version of regno_ok_for_base_p for use here, when all pseudos
645 should count as OK. Arguments as for regno_ok_for_base_p. */
646 static inline bool
647 ok_for_base_p_nonstrict (rtx reg, machine_mode mode, addr_space_t as,
648 enum rtx_code outer_code, enum rtx_code index_code)
650 unsigned regno = REGNO (reg);
652 if (regno >= FIRST_PSEUDO_REGISTER)
653 return true;
654 return ok_for_base_p_1 (regno, mode, as, outer_code, index_code);
659 /* The page contains major code to choose the current insn alternative
660 and generate reloads for it. */
662 /* Return the offset from REGNO of the least significant register
663 in (reg:MODE REGNO).
665 This function is used to tell whether two registers satisfy
666 a matching constraint. (reg:MODE1 REGNO1) matches (reg:MODE2 REGNO2) if:
668 REGNO1 + lra_constraint_offset (REGNO1, MODE1)
669 == REGNO2 + lra_constraint_offset (REGNO2, MODE2) */
671 lra_constraint_offset (int regno, machine_mode mode)
673 lra_assert (regno < FIRST_PSEUDO_REGISTER);
675 scalar_int_mode int_mode;
676 if (WORDS_BIG_ENDIAN
677 && is_a <scalar_int_mode> (mode, &int_mode)
678 && GET_MODE_SIZE (int_mode) > UNITS_PER_WORD)
679 return hard_regno_nregs (regno, mode) - 1;
680 return 0;
683 /* Like rtx_equal_p except that it allows a REG and a SUBREG to match
684 if they are the same hard reg, and has special hacks for
685 auto-increment and auto-decrement. This is specifically intended for
686 process_alt_operands to use in determining whether two operands
687 match. X is the operand whose number is the lower of the two.
689 It is supposed that X is the output operand and Y is the input
690 operand. Y_HARD_REGNO is the final hard regno of register Y or
691 register in subreg Y as we know it now. Otherwise, it is a
692 negative value. */
693 static bool
694 operands_match_p (rtx x, rtx y, int y_hard_regno)
696 int i;
697 RTX_CODE code = GET_CODE (x);
698 const char *fmt;
700 if (x == y)
701 return true;
702 if ((code == REG || (code == SUBREG && REG_P (SUBREG_REG (x))))
703 && (REG_P (y) || (GET_CODE (y) == SUBREG && REG_P (SUBREG_REG (y)))))
705 int j;
707 i = get_hard_regno (x, false);
708 if (i < 0)
709 goto slow;
711 if ((j = y_hard_regno) < 0)
712 goto slow;
714 i += lra_constraint_offset (i, GET_MODE (x));
715 j += lra_constraint_offset (j, GET_MODE (y));
717 return i == j;
720 /* If two operands must match, because they are really a single
721 operand of an assembler insn, then two post-increments are invalid
722 because the assembler insn would increment only once. On the
723 other hand, a post-increment matches ordinary indexing if the
724 post-increment is the output operand. */
725 if (code == POST_DEC || code == POST_INC || code == POST_MODIFY)
726 return operands_match_p (XEXP (x, 0), y, y_hard_regno);
728 /* Two pre-increments are invalid because the assembler insn would
729 increment only once. On the other hand, a pre-increment matches
730 ordinary indexing if the pre-increment is the input operand. */
731 if (GET_CODE (y) == PRE_DEC || GET_CODE (y) == PRE_INC
732 || GET_CODE (y) == PRE_MODIFY)
733 return operands_match_p (x, XEXP (y, 0), -1);
735 slow:
737 if (code == REG && REG_P (y))
738 return REGNO (x) == REGNO (y);
740 if (code == REG && GET_CODE (y) == SUBREG && REG_P (SUBREG_REG (y))
741 && x == SUBREG_REG (y))
742 return true;
743 if (GET_CODE (y) == REG && code == SUBREG && REG_P (SUBREG_REG (x))
744 && SUBREG_REG (x) == y)
745 return true;
747 /* Now we have disposed of all the cases in which different rtx
748 codes can match. */
749 if (code != GET_CODE (y))
750 return false;
752 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
753 if (GET_MODE (x) != GET_MODE (y))
754 return false;
756 switch (code)
758 CASE_CONST_UNIQUE:
759 return false;
761 case LABEL_REF:
762 return label_ref_label (x) == label_ref_label (y);
763 case SYMBOL_REF:
764 return XSTR (x, 0) == XSTR (y, 0);
766 default:
767 break;
770 /* Compare the elements. If any pair of corresponding elements fail
771 to match, return false for the whole things. */
773 fmt = GET_RTX_FORMAT (code);
774 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
776 int val, j;
777 switch (fmt[i])
779 case 'w':
780 if (XWINT (x, i) != XWINT (y, i))
781 return false;
782 break;
784 case 'i':
785 if (XINT (x, i) != XINT (y, i))
786 return false;
787 break;
789 case 'p':
790 if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y)))
791 return false;
792 break;
794 case 'e':
795 val = operands_match_p (XEXP (x, i), XEXP (y, i), -1);
796 if (val == 0)
797 return false;
798 break;
800 case '0':
801 break;
803 case 'E':
804 if (XVECLEN (x, i) != XVECLEN (y, i))
805 return false;
806 for (j = XVECLEN (x, i) - 1; j >= 0; --j)
808 val = operands_match_p (XVECEXP (x, i, j), XVECEXP (y, i, j), -1);
809 if (val == 0)
810 return false;
812 break;
814 /* It is believed that rtx's at this level will never
815 contain anything but integers and other rtx's, except for
816 within LABEL_REFs and SYMBOL_REFs. */
817 default:
818 gcc_unreachable ();
821 return true;
824 /* True if X is a constant that can be forced into the constant pool.
825 MODE is the mode of the operand, or VOIDmode if not known. */
826 #define CONST_POOL_OK_P(MODE, X) \
827 ((MODE) != VOIDmode \
828 && CONSTANT_P (X) \
829 && GET_CODE (X) != HIGH \
830 && !targetm.cannot_force_const_mem (MODE, X))
832 /* True if C is a non-empty register class that has too few registers
833 to be safely used as a reload target class. */
834 #define SMALL_REGISTER_CLASS_P(C) \
835 (ira_class_hard_regs_num [(C)] == 1 \
836 || (ira_class_hard_regs_num [(C)] >= 1 \
837 && targetm.class_likely_spilled_p (C)))
839 /* If REG is a reload pseudo, try to make its class satisfying CL. */
840 static void
841 narrow_reload_pseudo_class (rtx reg, enum reg_class cl)
843 enum reg_class rclass;
845 /* Do not make more accurate class from reloads generated. They are
846 mostly moves with a lot of constraints. Making more accurate
847 class may results in very narrow class and impossibility of find
848 registers for several reloads of one insn. */
849 if (INSN_UID (curr_insn) >= new_insn_uid_start)
850 return;
851 if (GET_CODE (reg) == SUBREG)
852 reg = SUBREG_REG (reg);
853 if (! REG_P (reg) || (int) REGNO (reg) < new_regno_start)
854 return;
855 if (in_class_p (reg, cl, &rclass) && rclass != cl)
856 lra_change_class (REGNO (reg), rclass, " Change to", true);
859 /* Searches X for any reference to a reg with the same value as REGNO,
860 returning the rtx of the reference found if any. Otherwise,
861 returns NULL_RTX. */
862 static rtx
863 regno_val_use_in (unsigned int regno, rtx x)
865 const char *fmt;
866 int i, j;
867 rtx tem;
869 if (REG_P (x) && lra_reg_info[REGNO (x)].val == lra_reg_info[regno].val)
870 return x;
872 fmt = GET_RTX_FORMAT (GET_CODE (x));
873 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
875 if (fmt[i] == 'e')
877 if ((tem = regno_val_use_in (regno, XEXP (x, i))))
878 return tem;
880 else if (fmt[i] == 'E')
881 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
882 if ((tem = regno_val_use_in (regno , XVECEXP (x, i, j))))
883 return tem;
886 return NULL_RTX;
889 /* Return true if all current insn non-output operands except INS (it
890 has a negaitve end marker) do not use pseudos with the same value
891 as REGNO. */
892 static bool
893 check_conflict_input_operands (int regno, signed char *ins)
895 int in;
896 int n_operands = curr_static_id->n_operands;
898 for (int nop = 0; nop < n_operands; nop++)
899 if (! curr_static_id->operand[nop].is_operator
900 && curr_static_id->operand[nop].type != OP_OUT)
902 for (int i = 0; (in = ins[i]) >= 0; i++)
903 if (in == nop)
904 break;
905 if (in < 0
906 && regno_val_use_in (regno, *curr_id->operand_loc[nop]) != NULL_RTX)
907 return false;
909 return true;
912 /* Generate reloads for matching OUT and INS (array of input operand
913 numbers with end marker -1) with reg class GOAL_CLASS, considering
914 output operands OUTS (similar array to INS) needing to be in different
915 registers. Add input and output reloads correspondingly to the lists
916 *BEFORE and *AFTER. OUT might be negative. In this case we generate
917 input reloads for matched input operands INS. EARLY_CLOBBER_P is a flag
918 that the output operand is early clobbered for chosen alternative. */
919 static void
920 match_reload (signed char out, signed char *ins, signed char *outs,
921 enum reg_class goal_class, rtx_insn **before,
922 rtx_insn **after, bool early_clobber_p)
924 bool out_conflict;
925 int i, in;
926 rtx new_in_reg, new_out_reg, reg;
927 machine_mode inmode, outmode;
928 rtx in_rtx = *curr_id->operand_loc[ins[0]];
929 rtx out_rtx = out < 0 ? in_rtx : *curr_id->operand_loc[out];
931 inmode = curr_operand_mode[ins[0]];
932 outmode = out < 0 ? inmode : curr_operand_mode[out];
933 push_to_sequence (*before);
934 if (inmode != outmode)
936 if (partial_subreg_p (outmode, inmode))
938 reg = new_in_reg
939 = lra_create_new_reg_with_unique_value (inmode, in_rtx,
940 goal_class, "");
941 if (SCALAR_INT_MODE_P (inmode))
942 new_out_reg = gen_lowpart_SUBREG (outmode, reg);
943 else
944 new_out_reg = gen_rtx_SUBREG (outmode, reg, 0);
945 LRA_SUBREG_P (new_out_reg) = 1;
946 /* If the input reg is dying here, we can use the same hard
947 register for REG and IN_RTX. We do it only for original
948 pseudos as reload pseudos can die although original
949 pseudos still live where reload pseudos dies. */
950 if (REG_P (in_rtx) && (int) REGNO (in_rtx) < lra_new_regno_start
951 && find_regno_note (curr_insn, REG_DEAD, REGNO (in_rtx))
952 && (!early_clobber_p
953 || check_conflict_input_operands(REGNO (in_rtx), ins)))
954 lra_assign_reg_val (REGNO (in_rtx), REGNO (reg));
956 else
958 reg = new_out_reg
959 = lra_create_new_reg_with_unique_value (outmode, out_rtx,
960 goal_class, "");
961 if (SCALAR_INT_MODE_P (outmode))
962 new_in_reg = gen_lowpart_SUBREG (inmode, reg);
963 else
964 new_in_reg = gen_rtx_SUBREG (inmode, reg, 0);
965 /* NEW_IN_REG is non-paradoxical subreg. We don't want
966 NEW_OUT_REG living above. We add clobber clause for
967 this. This is just a temporary clobber. We can remove
968 it at the end of LRA work. */
969 rtx_insn *clobber = emit_clobber (new_out_reg);
970 LRA_TEMP_CLOBBER_P (PATTERN (clobber)) = 1;
971 LRA_SUBREG_P (new_in_reg) = 1;
972 if (GET_CODE (in_rtx) == SUBREG)
974 rtx subreg_reg = SUBREG_REG (in_rtx);
976 /* If SUBREG_REG is dying here and sub-registers IN_RTX
977 and NEW_IN_REG are similar, we can use the same hard
978 register for REG and SUBREG_REG. */
979 if (REG_P (subreg_reg)
980 && (int) REGNO (subreg_reg) < lra_new_regno_start
981 && GET_MODE (subreg_reg) == outmode
982 && known_eq (SUBREG_BYTE (in_rtx), SUBREG_BYTE (new_in_reg))
983 && find_regno_note (curr_insn, REG_DEAD, REGNO (subreg_reg))
984 && (! early_clobber_p
985 || check_conflict_input_operands (REGNO (subreg_reg),
986 ins)))
987 lra_assign_reg_val (REGNO (subreg_reg), REGNO (reg));
991 else
993 /* Pseudos have values -- see comments for lra_reg_info.
994 Different pseudos with the same value do not conflict even if
995 they live in the same place. When we create a pseudo we
996 assign value of original pseudo (if any) from which we
997 created the new pseudo. If we create the pseudo from the
998 input pseudo, the new pseudo will have no conflict with the
999 input pseudo which is wrong when the input pseudo lives after
1000 the insn and as the new pseudo value is changed by the insn
1001 output. Therefore we create the new pseudo from the output
1002 except the case when we have single matched dying input
1003 pseudo.
1005 We cannot reuse the current output register because we might
1006 have a situation like "a <- a op b", where the constraints
1007 force the second input operand ("b") to match the output
1008 operand ("a"). "b" must then be copied into a new register
1009 so that it doesn't clobber the current value of "a".
1011 We can not use the same value if the output pseudo is
1012 early clobbered or the input pseudo is mentioned in the
1013 output, e.g. as an address part in memory, because
1014 output reload will actually extend the pseudo liveness.
1015 We don't care about eliminable hard regs here as we are
1016 interesting only in pseudos. */
1018 /* Matching input's register value is the same as one of the other
1019 output operand. Output operands in a parallel insn must be in
1020 different registers. */
1021 out_conflict = false;
1022 if (REG_P (in_rtx))
1024 for (i = 0; outs[i] >= 0; i++)
1026 rtx other_out_rtx = *curr_id->operand_loc[outs[i]];
1027 if (REG_P (other_out_rtx)
1028 && (regno_val_use_in (REGNO (in_rtx), other_out_rtx)
1029 != NULL_RTX))
1031 out_conflict = true;
1032 break;
1037 new_in_reg = new_out_reg
1038 = (! early_clobber_p && ins[1] < 0 && REG_P (in_rtx)
1039 && (int) REGNO (in_rtx) < lra_new_regno_start
1040 && find_regno_note (curr_insn, REG_DEAD, REGNO (in_rtx))
1041 && (! early_clobber_p
1042 || check_conflict_input_operands (REGNO (in_rtx), ins))
1043 && (out < 0
1044 || regno_val_use_in (REGNO (in_rtx), out_rtx) == NULL_RTX)
1045 && !out_conflict
1046 ? lra_create_new_reg (inmode, in_rtx, goal_class, "")
1047 : lra_create_new_reg_with_unique_value (outmode, out_rtx,
1048 goal_class, ""));
1050 /* In operand can be got from transformations before processing insn
1051 constraints. One example of such transformations is subreg
1052 reloading (see function simplify_operand_subreg). The new
1053 pseudos created by the transformations might have inaccurate
1054 class (ALL_REGS) and we should make their classes more
1055 accurate. */
1056 narrow_reload_pseudo_class (in_rtx, goal_class);
1057 lra_emit_move (copy_rtx (new_in_reg), in_rtx);
1058 *before = get_insns ();
1059 end_sequence ();
1060 /* Add the new pseudo to consider values of subsequent input reload
1061 pseudos. */
1062 lra_assert (curr_insn_input_reloads_num < LRA_MAX_INSN_RELOADS);
1063 curr_insn_input_reloads[curr_insn_input_reloads_num].input = in_rtx;
1064 curr_insn_input_reloads[curr_insn_input_reloads_num].match_p = true;
1065 curr_insn_input_reloads[curr_insn_input_reloads_num++].reg = new_in_reg;
1066 for (i = 0; (in = ins[i]) >= 0; i++)
1068 lra_assert
1069 (GET_MODE (*curr_id->operand_loc[in]) == VOIDmode
1070 || GET_MODE (new_in_reg) == GET_MODE (*curr_id->operand_loc[in]));
1071 *curr_id->operand_loc[in] = new_in_reg;
1073 lra_update_dups (curr_id, ins);
1074 if (out < 0)
1075 return;
1076 /* See a comment for the input operand above. */
1077 narrow_reload_pseudo_class (out_rtx, goal_class);
1078 if (find_reg_note (curr_insn, REG_UNUSED, out_rtx) == NULL_RTX)
1080 start_sequence ();
1081 lra_emit_move (out_rtx, copy_rtx (new_out_reg));
1082 emit_insn (*after);
1083 *after = get_insns ();
1084 end_sequence ();
1086 *curr_id->operand_loc[out] = new_out_reg;
1087 lra_update_dup (curr_id, out);
1090 /* Return register class which is union of all reg classes in insn
1091 constraint alternative string starting with P. */
1092 static enum reg_class
1093 reg_class_from_constraints (const char *p)
1095 int c, len;
1096 enum reg_class op_class = NO_REGS;
1099 switch ((c = *p, len = CONSTRAINT_LEN (c, p)), c)
1101 case '#':
1102 case ',':
1103 return op_class;
1105 case 'g':
1106 op_class = reg_class_subunion[op_class][GENERAL_REGS];
1107 break;
1109 default:
1110 enum constraint_num cn = lookup_constraint (p);
1111 enum reg_class cl = reg_class_for_constraint (cn);
1112 if (cl == NO_REGS)
1114 if (insn_extra_address_constraint (cn))
1115 op_class
1116 = (reg_class_subunion
1117 [op_class][base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
1118 ADDRESS, SCRATCH)]);
1119 break;
1122 op_class = reg_class_subunion[op_class][cl];
1123 break;
1125 while ((p += len), c);
1126 return op_class;
1129 /* If OP is a register, return the class of the register as per
1130 get_reg_class, otherwise return NO_REGS. */
1131 static inline enum reg_class
1132 get_op_class (rtx op)
1134 return REG_P (op) ? get_reg_class (REGNO (op)) : NO_REGS;
1137 /* Return generated insn mem_pseudo:=val if TO_P or val:=mem_pseudo
1138 otherwise. If modes of MEM_PSEUDO and VAL are different, use
1139 SUBREG for VAL to make them equal. */
1140 static rtx_insn *
1141 emit_spill_move (bool to_p, rtx mem_pseudo, rtx val)
1143 if (GET_MODE (mem_pseudo) != GET_MODE (val))
1145 /* Usually size of mem_pseudo is greater than val size but in
1146 rare cases it can be less as it can be defined by target
1147 dependent macro HARD_REGNO_CALLER_SAVE_MODE. */
1148 if (! MEM_P (val))
1150 val = gen_lowpart_SUBREG (GET_MODE (mem_pseudo),
1151 GET_CODE (val) == SUBREG
1152 ? SUBREG_REG (val) : val);
1153 LRA_SUBREG_P (val) = 1;
1155 else
1157 mem_pseudo = gen_lowpart_SUBREG (GET_MODE (val), mem_pseudo);
1158 LRA_SUBREG_P (mem_pseudo) = 1;
1161 return to_p ? gen_move_insn (mem_pseudo, val)
1162 : gen_move_insn (val, mem_pseudo);
1165 /* Process a special case insn (register move), return true if we
1166 don't need to process it anymore. INSN should be a single set
1167 insn. Set up that RTL was changed through CHANGE_P and that hook
1168 TARGET_SECONDARY_MEMORY_NEEDED says to use secondary memory through
1169 SEC_MEM_P. */
1170 static bool
1171 check_and_process_move (bool *change_p, bool *sec_mem_p ATTRIBUTE_UNUSED)
1173 int sregno, dregno;
1174 rtx dest, src, dreg, sreg, new_reg, scratch_reg;
1175 rtx_insn *before;
1176 enum reg_class dclass, sclass, secondary_class;
1177 secondary_reload_info sri;
1179 lra_assert (curr_insn_set != NULL_RTX);
1180 dreg = dest = SET_DEST (curr_insn_set);
1181 sreg = src = SET_SRC (curr_insn_set);
1182 if (GET_CODE (dest) == SUBREG)
1183 dreg = SUBREG_REG (dest);
1184 if (GET_CODE (src) == SUBREG)
1185 sreg = SUBREG_REG (src);
1186 if (! (REG_P (dreg) || MEM_P (dreg)) || ! (REG_P (sreg) || MEM_P (sreg)))
1187 return false;
1188 sclass = dclass = NO_REGS;
1189 if (REG_P (dreg))
1190 dclass = get_reg_class (REGNO (dreg));
1191 gcc_assert (dclass < LIM_REG_CLASSES);
1192 if (dclass == ALL_REGS)
1193 /* ALL_REGS is used for new pseudos created by transformations
1194 like reload of SUBREG_REG (see function
1195 simplify_operand_subreg). We don't know their class yet. We
1196 should figure out the class from processing the insn
1197 constraints not in this fast path function. Even if ALL_REGS
1198 were a right class for the pseudo, secondary_... hooks usually
1199 are not define for ALL_REGS. */
1200 return false;
1201 if (REG_P (sreg))
1202 sclass = get_reg_class (REGNO (sreg));
1203 gcc_assert (sclass < LIM_REG_CLASSES);
1204 if (sclass == ALL_REGS)
1205 /* See comments above. */
1206 return false;
1207 if (sclass == NO_REGS && dclass == NO_REGS)
1208 return false;
1209 if (targetm.secondary_memory_needed (GET_MODE (src), sclass, dclass)
1210 && ((sclass != NO_REGS && dclass != NO_REGS)
1211 || (GET_MODE (src)
1212 != targetm.secondary_memory_needed_mode (GET_MODE (src)))))
1214 *sec_mem_p = true;
1215 return false;
1217 if (! REG_P (dreg) || ! REG_P (sreg))
1218 return false;
1219 sri.prev_sri = NULL;
1220 sri.icode = CODE_FOR_nothing;
1221 sri.extra_cost = 0;
1222 secondary_class = NO_REGS;
1223 /* Set up hard register for a reload pseudo for hook
1224 secondary_reload because some targets just ignore unassigned
1225 pseudos in the hook. */
1226 if (dclass != NO_REGS && lra_get_regno_hard_regno (REGNO (dreg)) < 0)
1228 dregno = REGNO (dreg);
1229 reg_renumber[dregno] = ira_class_hard_regs[dclass][0];
1231 else
1232 dregno = -1;
1233 if (sclass != NO_REGS && lra_get_regno_hard_regno (REGNO (sreg)) < 0)
1235 sregno = REGNO (sreg);
1236 reg_renumber[sregno] = ira_class_hard_regs[sclass][0];
1238 else
1239 sregno = -1;
1240 if (sclass != NO_REGS)
1241 secondary_class
1242 = (enum reg_class) targetm.secondary_reload (false, dest,
1243 (reg_class_t) sclass,
1244 GET_MODE (src), &sri);
1245 if (sclass == NO_REGS
1246 || ((secondary_class != NO_REGS || sri.icode != CODE_FOR_nothing)
1247 && dclass != NO_REGS))
1249 enum reg_class old_sclass = secondary_class;
1250 secondary_reload_info old_sri = sri;
1252 sri.prev_sri = NULL;
1253 sri.icode = CODE_FOR_nothing;
1254 sri.extra_cost = 0;
1255 secondary_class
1256 = (enum reg_class) targetm.secondary_reload (true, src,
1257 (reg_class_t) dclass,
1258 GET_MODE (src), &sri);
1259 /* Check the target hook consistency. */
1260 lra_assert
1261 ((secondary_class == NO_REGS && sri.icode == CODE_FOR_nothing)
1262 || (old_sclass == NO_REGS && old_sri.icode == CODE_FOR_nothing)
1263 || (secondary_class == old_sclass && sri.icode == old_sri.icode));
1265 if (sregno >= 0)
1266 reg_renumber [sregno] = -1;
1267 if (dregno >= 0)
1268 reg_renumber [dregno] = -1;
1269 if (secondary_class == NO_REGS && sri.icode == CODE_FOR_nothing)
1270 return false;
1271 *change_p = true;
1272 new_reg = NULL_RTX;
1273 if (secondary_class != NO_REGS)
1274 new_reg = lra_create_new_reg_with_unique_value (GET_MODE (src), NULL_RTX,
1275 secondary_class,
1276 "secondary");
1277 start_sequence ();
1278 if (sri.icode == CODE_FOR_nothing)
1279 lra_emit_move (new_reg, src);
1280 else
1282 enum reg_class scratch_class;
1284 scratch_class = (reg_class_from_constraints
1285 (insn_data[sri.icode].operand[2].constraint));
1286 scratch_reg = (lra_create_new_reg_with_unique_value
1287 (insn_data[sri.icode].operand[2].mode, NULL_RTX,
1288 scratch_class, "scratch"));
1289 emit_insn (GEN_FCN (sri.icode) (new_reg != NULL_RTX ? new_reg : dest,
1290 src, scratch_reg));
1292 before = get_insns ();
1293 end_sequence ();
1294 lra_process_new_insns (curr_insn, before, NULL, "Inserting the move");
1295 if (new_reg != NULL_RTX)
1296 SET_SRC (curr_insn_set) = new_reg;
1297 else
1299 if (lra_dump_file != NULL)
1301 fprintf (lra_dump_file, "Deleting move %u\n", INSN_UID (curr_insn));
1302 dump_insn_slim (lra_dump_file, curr_insn);
1304 lra_set_insn_deleted (curr_insn);
1305 return true;
1307 return false;
1310 /* The following data describe the result of process_alt_operands.
1311 The data are used in curr_insn_transform to generate reloads. */
1313 /* The chosen reg classes which should be used for the corresponding
1314 operands. */
1315 static enum reg_class goal_alt[MAX_RECOG_OPERANDS];
1316 /* True if the operand should be the same as another operand and that
1317 other operand does not need a reload. */
1318 static bool goal_alt_match_win[MAX_RECOG_OPERANDS];
1319 /* True if the operand does not need a reload. */
1320 static bool goal_alt_win[MAX_RECOG_OPERANDS];
1321 /* True if the operand can be offsetable memory. */
1322 static bool goal_alt_offmemok[MAX_RECOG_OPERANDS];
1323 /* The number of an operand to which given operand can be matched to. */
1324 static int goal_alt_matches[MAX_RECOG_OPERANDS];
1325 /* The number of elements in the following array. */
1326 static int goal_alt_dont_inherit_ops_num;
1327 /* Numbers of operands whose reload pseudos should not be inherited. */
1328 static int goal_alt_dont_inherit_ops[MAX_RECOG_OPERANDS];
1329 /* True if the insn commutative operands should be swapped. */
1330 static bool goal_alt_swapped;
1331 /* The chosen insn alternative. */
1332 static int goal_alt_number;
1334 /* True if the corresponding operand is the result of an equivalence
1335 substitution. */
1336 static bool equiv_substition_p[MAX_RECOG_OPERANDS];
1338 /* The following five variables are used to choose the best insn
1339 alternative. They reflect final characteristics of the best
1340 alternative. */
1342 /* Number of necessary reloads and overall cost reflecting the
1343 previous value and other unpleasantness of the best alternative. */
1344 static int best_losers, best_overall;
1345 /* Overall number hard registers used for reloads. For example, on
1346 some targets we need 2 general registers to reload DFmode and only
1347 one floating point register. */
1348 static int best_reload_nregs;
1349 /* Overall number reflecting distances of previous reloading the same
1350 value. The distances are counted from the current BB start. It is
1351 used to improve inheritance chances. */
1352 static int best_reload_sum;
1354 /* True if the current insn should have no correspondingly input or
1355 output reloads. */
1356 static bool no_input_reloads_p, no_output_reloads_p;
1358 /* True if we swapped the commutative operands in the current
1359 insn. */
1360 static int curr_swapped;
1362 /* if CHECK_ONLY_P is false, arrange for address element *LOC to be a
1363 register of class CL. Add any input reloads to list BEFORE. AFTER
1364 is nonnull if *LOC is an automodified value; handle that case by
1365 adding the required output reloads to list AFTER. Return true if
1366 the RTL was changed.
1368 if CHECK_ONLY_P is true, check that the *LOC is a correct address
1369 register. Return false if the address register is correct. */
1370 static bool
1371 process_addr_reg (rtx *loc, bool check_only_p, rtx_insn **before, rtx_insn **after,
1372 enum reg_class cl)
1374 int regno;
1375 enum reg_class rclass, new_class;
1376 rtx reg;
1377 rtx new_reg;
1378 machine_mode mode;
1379 bool subreg_p, before_p = false;
1381 subreg_p = GET_CODE (*loc) == SUBREG;
1382 if (subreg_p)
1384 reg = SUBREG_REG (*loc);
1385 mode = GET_MODE (reg);
1387 /* For mode with size bigger than ptr_mode, there unlikely to be "mov"
1388 between two registers with different classes, but there normally will
1389 be "mov" which transfers element of vector register into the general
1390 register, and this normally will be a subreg which should be reloaded
1391 as a whole. This is particularly likely to be triggered when
1392 -fno-split-wide-types specified. */
1393 if (!REG_P (reg)
1394 || in_class_p (reg, cl, &new_class)
1395 || GET_MODE_SIZE (mode) <= GET_MODE_SIZE (ptr_mode))
1396 loc = &SUBREG_REG (*loc);
1399 reg = *loc;
1400 mode = GET_MODE (reg);
1401 if (! REG_P (reg))
1403 if (check_only_p)
1404 return true;
1405 /* Always reload memory in an address even if the target supports
1406 such addresses. */
1407 new_reg = lra_create_new_reg_with_unique_value (mode, reg, cl, "address");
1408 before_p = true;
1410 else
1412 regno = REGNO (reg);
1413 rclass = get_reg_class (regno);
1414 if (! check_only_p
1415 && (*loc = get_equiv_with_elimination (reg, curr_insn)) != reg)
1417 if (lra_dump_file != NULL)
1419 fprintf (lra_dump_file,
1420 "Changing pseudo %d in address of insn %u on equiv ",
1421 REGNO (reg), INSN_UID (curr_insn));
1422 dump_value_slim (lra_dump_file, *loc, 1);
1423 fprintf (lra_dump_file, "\n");
1425 *loc = copy_rtx (*loc);
1427 if (*loc != reg || ! in_class_p (reg, cl, &new_class))
1429 if (check_only_p)
1430 return true;
1431 reg = *loc;
1432 if (get_reload_reg (after == NULL ? OP_IN : OP_INOUT,
1433 mode, reg, cl, subreg_p, "address", &new_reg))
1434 before_p = true;
1436 else if (new_class != NO_REGS && rclass != new_class)
1438 if (check_only_p)
1439 return true;
1440 lra_change_class (regno, new_class, " Change to", true);
1441 return false;
1443 else
1444 return false;
1446 if (before_p)
1448 push_to_sequence (*before);
1449 lra_emit_move (new_reg, reg);
1450 *before = get_insns ();
1451 end_sequence ();
1453 *loc = new_reg;
1454 if (after != NULL)
1456 start_sequence ();
1457 lra_emit_move (before_p ? copy_rtx (reg) : reg, new_reg);
1458 emit_insn (*after);
1459 *after = get_insns ();
1460 end_sequence ();
1462 return true;
1465 /* Insert move insn in simplify_operand_subreg. BEFORE returns
1466 the insn to be inserted before curr insn. AFTER returns the
1467 the insn to be inserted after curr insn. ORIGREG and NEWREG
1468 are the original reg and new reg for reload. */
1469 static void
1470 insert_move_for_subreg (rtx_insn **before, rtx_insn **after, rtx origreg,
1471 rtx newreg)
1473 if (before)
1475 push_to_sequence (*before);
1476 lra_emit_move (newreg, origreg);
1477 *before = get_insns ();
1478 end_sequence ();
1480 if (after)
1482 start_sequence ();
1483 lra_emit_move (origreg, newreg);
1484 emit_insn (*after);
1485 *after = get_insns ();
1486 end_sequence ();
1490 static int valid_address_p (machine_mode mode, rtx addr, addr_space_t as);
1491 static bool process_address (int, bool, rtx_insn **, rtx_insn **);
1493 /* Make reloads for subreg in operand NOP with internal subreg mode
1494 REG_MODE, add new reloads for further processing. Return true if
1495 any change was done. */
1496 static bool
1497 simplify_operand_subreg (int nop, machine_mode reg_mode)
1499 int hard_regno;
1500 rtx_insn *before, *after;
1501 machine_mode mode, innermode;
1502 rtx reg, new_reg;
1503 rtx operand = *curr_id->operand_loc[nop];
1504 enum reg_class regclass;
1505 enum op_type type;
1507 before = after = NULL;
1509 if (GET_CODE (operand) != SUBREG)
1510 return false;
1512 mode = GET_MODE (operand);
1513 reg = SUBREG_REG (operand);
1514 innermode = GET_MODE (reg);
1515 type = curr_static_id->operand[nop].type;
1516 if (MEM_P (reg))
1518 const bool addr_was_valid
1519 = valid_address_p (innermode, XEXP (reg, 0), MEM_ADDR_SPACE (reg));
1520 alter_subreg (curr_id->operand_loc[nop], false);
1521 rtx subst = *curr_id->operand_loc[nop];
1522 lra_assert (MEM_P (subst));
1524 if (!addr_was_valid
1525 || valid_address_p (GET_MODE (subst), XEXP (subst, 0),
1526 MEM_ADDR_SPACE (subst))
1527 || ((get_constraint_type (lookup_constraint
1528 (curr_static_id->operand[nop].constraint))
1529 != CT_SPECIAL_MEMORY)
1530 /* We still can reload address and if the address is
1531 valid, we can remove subreg without reloading its
1532 inner memory. */
1533 && valid_address_p (GET_MODE (subst),
1534 regno_reg_rtx
1535 [ira_class_hard_regs
1536 [base_reg_class (GET_MODE (subst),
1537 MEM_ADDR_SPACE (subst),
1538 ADDRESS, SCRATCH)][0]],
1539 MEM_ADDR_SPACE (subst))))
1541 /* If we change the address for a paradoxical subreg of memory, the
1542 new address might violate the necessary alignment or the access
1543 might be slow; take this into consideration. We need not worry
1544 about accesses beyond allocated memory for paradoxical memory
1545 subregs as we don't substitute such equiv memory (see processing
1546 equivalences in function lra_constraints) and because for spilled
1547 pseudos we allocate stack memory enough for the biggest
1548 corresponding paradoxical subreg.
1550 However, do not blindly simplify a (subreg (mem ...)) for
1551 WORD_REGISTER_OPERATIONS targets as this may lead to loading junk
1552 data into a register when the inner is narrower than outer or
1553 missing important data from memory when the inner is wider than
1554 outer. This rule only applies to modes that are no wider than
1555 a word. */
1556 if (!(GET_MODE_PRECISION (mode) != GET_MODE_PRECISION (innermode)
1557 && GET_MODE_SIZE (mode) <= UNITS_PER_WORD
1558 && GET_MODE_SIZE (innermode) <= UNITS_PER_WORD
1559 && WORD_REGISTER_OPERATIONS)
1560 && (!(MEM_ALIGN (subst) < GET_MODE_ALIGNMENT (mode)
1561 && targetm.slow_unaligned_access (mode, MEM_ALIGN (subst)))
1562 || (MEM_ALIGN (reg) < GET_MODE_ALIGNMENT (innermode)
1563 && targetm.slow_unaligned_access (innermode,
1564 MEM_ALIGN (reg)))))
1565 return true;
1567 *curr_id->operand_loc[nop] = operand;
1569 /* But if the address was not valid, we cannot reload the MEM without
1570 reloading the address first. */
1571 if (!addr_was_valid)
1572 process_address (nop, false, &before, &after);
1574 /* INNERMODE is fast, MODE slow. Reload the mem in INNERMODE. */
1575 enum reg_class rclass
1576 = (enum reg_class) targetm.preferred_reload_class (reg, ALL_REGS);
1577 if (get_reload_reg (curr_static_id->operand[nop].type, innermode,
1578 reg, rclass, TRUE, "slow mem", &new_reg))
1580 bool insert_before, insert_after;
1581 bitmap_set_bit (&lra_subreg_reload_pseudos, REGNO (new_reg));
1583 insert_before = (type != OP_OUT
1584 || partial_subreg_p (mode, innermode));
1585 insert_after = type != OP_IN;
1586 insert_move_for_subreg (insert_before ? &before : NULL,
1587 insert_after ? &after : NULL,
1588 reg, new_reg);
1590 SUBREG_REG (operand) = new_reg;
1592 /* Convert to MODE. */
1593 reg = operand;
1594 rclass
1595 = (enum reg_class) targetm.preferred_reload_class (reg, ALL_REGS);
1596 if (get_reload_reg (curr_static_id->operand[nop].type, mode, reg,
1597 rclass, TRUE, "slow mem", &new_reg))
1599 bool insert_before, insert_after;
1600 bitmap_set_bit (&lra_subreg_reload_pseudos, REGNO (new_reg));
1602 insert_before = type != OP_OUT;
1603 insert_after = type != OP_IN;
1604 insert_move_for_subreg (insert_before ? &before : NULL,
1605 insert_after ? &after : NULL,
1606 reg, new_reg);
1608 *curr_id->operand_loc[nop] = new_reg;
1609 lra_process_new_insns (curr_insn, before, after,
1610 "Inserting slow mem reload");
1611 return true;
1614 /* If the address was valid and became invalid, prefer to reload
1615 the memory. Typical case is when the index scale should
1616 correspond the memory. */
1617 *curr_id->operand_loc[nop] = operand;
1618 /* Do not return false here as the MEM_P (reg) will be processed
1619 later in this function. */
1621 else if (REG_P (reg) && REGNO (reg) < FIRST_PSEUDO_REGISTER)
1623 alter_subreg (curr_id->operand_loc[nop], false);
1624 return true;
1626 else if (CONSTANT_P (reg))
1628 /* Try to simplify subreg of constant. It is usually result of
1629 equivalence substitution. */
1630 if (innermode == VOIDmode
1631 && (innermode = original_subreg_reg_mode[nop]) == VOIDmode)
1632 innermode = curr_static_id->operand[nop].mode;
1633 if ((new_reg = simplify_subreg (mode, reg, innermode,
1634 SUBREG_BYTE (operand))) != NULL_RTX)
1636 *curr_id->operand_loc[nop] = new_reg;
1637 return true;
1640 /* Put constant into memory when we have mixed modes. It generates
1641 a better code in most cases as it does not need a secondary
1642 reload memory. It also prevents LRA looping when LRA is using
1643 secondary reload memory again and again. */
1644 if (CONSTANT_P (reg) && CONST_POOL_OK_P (reg_mode, reg)
1645 && SCALAR_INT_MODE_P (reg_mode) != SCALAR_INT_MODE_P (mode))
1647 SUBREG_REG (operand) = force_const_mem (reg_mode, reg);
1648 alter_subreg (curr_id->operand_loc[nop], false);
1649 return true;
1651 /* Force a reload of the SUBREG_REG if this is a constant or PLUS or
1652 if there may be a problem accessing OPERAND in the outer
1653 mode. */
1654 if ((REG_P (reg)
1655 && REGNO (reg) >= FIRST_PSEUDO_REGISTER
1656 && (hard_regno = lra_get_regno_hard_regno (REGNO (reg))) >= 0
1657 /* Don't reload paradoxical subregs because we could be looping
1658 having repeatedly final regno out of hard regs range. */
1659 && (hard_regno_nregs (hard_regno, innermode)
1660 >= hard_regno_nregs (hard_regno, mode))
1661 && simplify_subreg_regno (hard_regno, innermode,
1662 SUBREG_BYTE (operand), mode) < 0
1663 /* Don't reload subreg for matching reload. It is actually
1664 valid subreg in LRA. */
1665 && ! LRA_SUBREG_P (operand))
1666 || CONSTANT_P (reg) || GET_CODE (reg) == PLUS || MEM_P (reg))
1668 enum reg_class rclass;
1670 if (REG_P (reg))
1671 /* There is a big probability that we will get the same class
1672 for the new pseudo and we will get the same insn which
1673 means infinite looping. So spill the new pseudo. */
1674 rclass = NO_REGS;
1675 else
1676 /* The class will be defined later in curr_insn_transform. */
1677 rclass
1678 = (enum reg_class) targetm.preferred_reload_class (reg, ALL_REGS);
1680 if (get_reload_reg (curr_static_id->operand[nop].type, reg_mode, reg,
1681 rclass, TRUE, "subreg reg", &new_reg))
1683 bool insert_before, insert_after;
1684 bitmap_set_bit (&lra_subreg_reload_pseudos, REGNO (new_reg));
1686 insert_before = (type != OP_OUT
1687 || read_modify_subreg_p (operand));
1688 insert_after = (type != OP_IN);
1689 insert_move_for_subreg (insert_before ? &before : NULL,
1690 insert_after ? &after : NULL,
1691 reg, new_reg);
1693 SUBREG_REG (operand) = new_reg;
1694 lra_process_new_insns (curr_insn, before, after,
1695 "Inserting subreg reload");
1696 return true;
1698 /* Force a reload for a paradoxical subreg. For paradoxical subreg,
1699 IRA allocates hardreg to the inner pseudo reg according to its mode
1700 instead of the outermode, so the size of the hardreg may not be enough
1701 to contain the outermode operand, in that case we may need to insert
1702 reload for the reg. For the following two types of paradoxical subreg,
1703 we need to insert reload:
1704 1. If the op_type is OP_IN, and the hardreg could not be paired with
1705 other hardreg to contain the outermode operand
1706 (checked by in_hard_reg_set_p), we need to insert the reload.
1707 2. If the op_type is OP_OUT or OP_INOUT.
1709 Here is a paradoxical subreg example showing how the reload is generated:
1711 (insn 5 4 7 2 (set (reg:TI 106 [ __comp ])
1712 (subreg:TI (reg:DI 107 [ __comp ]) 0)) {*movti_internal_rex64}
1714 In IRA, reg107 is allocated to a DImode hardreg. We use x86-64 as example
1715 here, if reg107 is assigned to hardreg R15, because R15 is the last
1716 hardreg, compiler cannot find another hardreg to pair with R15 to
1717 contain TImode data. So we insert a TImode reload reg180 for it.
1718 After reload is inserted:
1720 (insn 283 0 0 (set (subreg:DI (reg:TI 180 [orig:107 __comp ] [107]) 0)
1721 (reg:DI 107 [ __comp ])) -1
1722 (insn 5 4 7 2 (set (reg:TI 106 [ __comp ])
1723 (subreg:TI (reg:TI 180 [orig:107 __comp ] [107]) 0)) {*movti_internal_rex64}
1725 Two reload hard registers will be allocated to reg180 to save TImode data
1726 in LRA_assign. */
1727 else if (REG_P (reg)
1728 && REGNO (reg) >= FIRST_PSEUDO_REGISTER
1729 && (hard_regno = lra_get_regno_hard_regno (REGNO (reg))) >= 0
1730 && (hard_regno_nregs (hard_regno, innermode)
1731 < hard_regno_nregs (hard_regno, mode))
1732 && (regclass = lra_get_allocno_class (REGNO (reg)))
1733 && (type != OP_IN
1734 || !in_hard_reg_set_p (reg_class_contents[regclass],
1735 mode, hard_regno)))
1737 /* The class will be defined later in curr_insn_transform. */
1738 enum reg_class rclass
1739 = (enum reg_class) targetm.preferred_reload_class (reg, ALL_REGS);
1741 if (get_reload_reg (curr_static_id->operand[nop].type, mode, reg,
1742 rclass, TRUE, "paradoxical subreg", &new_reg))
1744 rtx subreg;
1745 bool insert_before, insert_after;
1747 PUT_MODE (new_reg, mode);
1748 subreg = gen_lowpart_SUBREG (innermode, new_reg);
1749 bitmap_set_bit (&lra_subreg_reload_pseudos, REGNO (new_reg));
1751 insert_before = (type != OP_OUT);
1752 insert_after = (type != OP_IN);
1753 insert_move_for_subreg (insert_before ? &before : NULL,
1754 insert_after ? &after : NULL,
1755 reg, subreg);
1757 SUBREG_REG (operand) = new_reg;
1758 lra_process_new_insns (curr_insn, before, after,
1759 "Inserting paradoxical subreg reload");
1760 return true;
1762 return false;
1765 /* Return TRUE if X refers for a hard register from SET. */
1766 static bool
1767 uses_hard_regs_p (rtx x, HARD_REG_SET set)
1769 int i, j, x_hard_regno;
1770 machine_mode mode;
1771 const char *fmt;
1772 enum rtx_code code;
1774 if (x == NULL_RTX)
1775 return false;
1776 code = GET_CODE (x);
1777 mode = GET_MODE (x);
1778 if (code == SUBREG)
1780 mode = wider_subreg_mode (x);
1781 x = SUBREG_REG (x);
1782 code = GET_CODE (x);
1785 if (REG_P (x))
1787 x_hard_regno = get_hard_regno (x, true);
1788 return (x_hard_regno >= 0
1789 && overlaps_hard_reg_set_p (set, mode, x_hard_regno));
1791 if (MEM_P (x))
1793 struct address_info ad;
1795 decompose_mem_address (&ad, x);
1796 if (ad.base_term != NULL && uses_hard_regs_p (*ad.base_term, set))
1797 return true;
1798 if (ad.index_term != NULL && uses_hard_regs_p (*ad.index_term, set))
1799 return true;
1801 fmt = GET_RTX_FORMAT (code);
1802 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1804 if (fmt[i] == 'e')
1806 if (uses_hard_regs_p (XEXP (x, i), set))
1807 return true;
1809 else if (fmt[i] == 'E')
1811 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1812 if (uses_hard_regs_p (XVECEXP (x, i, j), set))
1813 return true;
1816 return false;
1819 /* Return true if OP is a spilled pseudo. */
1820 static inline bool
1821 spilled_pseudo_p (rtx op)
1823 return (REG_P (op)
1824 && REGNO (op) >= FIRST_PSEUDO_REGISTER && in_mem_p (REGNO (op)));
1827 /* Return true if X is a general constant. */
1828 static inline bool
1829 general_constant_p (rtx x)
1831 return CONSTANT_P (x) && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (x));
1834 static bool
1835 reg_in_class_p (rtx reg, enum reg_class cl)
1837 if (cl == NO_REGS)
1838 return get_reg_class (REGNO (reg)) == NO_REGS;
1839 return in_class_p (reg, cl, NULL);
1842 /* Return true if SET of RCLASS contains no hard regs which can be
1843 used in MODE. */
1844 static bool
1845 prohibited_class_reg_set_mode_p (enum reg_class rclass,
1846 HARD_REG_SET &set,
1847 machine_mode mode)
1849 HARD_REG_SET temp;
1851 lra_assert (hard_reg_set_subset_p (reg_class_contents[rclass], set));
1852 COPY_HARD_REG_SET (temp, set);
1853 AND_COMPL_HARD_REG_SET (temp, lra_no_alloc_regs);
1854 return (hard_reg_set_subset_p
1855 (temp, ira_prohibited_class_mode_regs[rclass][mode]));
1859 /* Used to check validity info about small class input operands. It
1860 should be incremented at start of processing an insn
1861 alternative. */
1862 static unsigned int curr_small_class_check = 0;
1864 /* Update number of used inputs of class OP_CLASS for operand NOP.
1865 Return true if we have more such class operands than the number of
1866 available regs. */
1867 static bool
1868 update_and_check_small_class_inputs (int nop, enum reg_class op_class)
1870 static unsigned int small_class_check[LIM_REG_CLASSES];
1871 static int small_class_input_nums[LIM_REG_CLASSES];
1873 if (SMALL_REGISTER_CLASS_P (op_class)
1874 /* We are interesting in classes became small because of fixing
1875 some hard regs, e.g. by an user through GCC options. */
1876 && hard_reg_set_intersect_p (reg_class_contents[op_class],
1877 ira_no_alloc_regs)
1878 && (curr_static_id->operand[nop].type != OP_OUT
1879 || curr_static_id->operand[nop].early_clobber))
1881 if (small_class_check[op_class] == curr_small_class_check)
1882 small_class_input_nums[op_class]++;
1883 else
1885 small_class_check[op_class] = curr_small_class_check;
1886 small_class_input_nums[op_class] = 1;
1888 if (small_class_input_nums[op_class] > ira_class_hard_regs_num[op_class])
1889 return true;
1891 return false;
1894 /* Major function to choose the current insn alternative and what
1895 operands should be reloaded and how. If ONLY_ALTERNATIVE is not
1896 negative we should consider only this alternative. Return false if
1897 we can not choose the alternative or find how to reload the
1898 operands. */
1899 static bool
1900 process_alt_operands (int only_alternative)
1902 bool ok_p = false;
1903 int nop, overall, nalt;
1904 int n_alternatives = curr_static_id->n_alternatives;
1905 int n_operands = curr_static_id->n_operands;
1906 /* LOSERS counts the operands that don't fit this alternative and
1907 would require loading. */
1908 int losers;
1909 int addr_losers;
1910 /* REJECT is a count of how undesirable this alternative says it is
1911 if any reloading is required. If the alternative matches exactly
1912 then REJECT is ignored, but otherwise it gets this much counted
1913 against it in addition to the reloading needed. */
1914 int reject;
1915 /* This is defined by '!' or '?' alternative constraint and added to
1916 reject. But in some cases it can be ignored. */
1917 int static_reject;
1918 int op_reject;
1919 /* The number of elements in the following array. */
1920 int early_clobbered_regs_num;
1921 /* Numbers of operands which are early clobber registers. */
1922 int early_clobbered_nops[MAX_RECOG_OPERANDS];
1923 enum reg_class curr_alt[MAX_RECOG_OPERANDS];
1924 HARD_REG_SET curr_alt_set[MAX_RECOG_OPERANDS];
1925 bool curr_alt_match_win[MAX_RECOG_OPERANDS];
1926 bool curr_alt_win[MAX_RECOG_OPERANDS];
1927 bool curr_alt_offmemok[MAX_RECOG_OPERANDS];
1928 int curr_alt_matches[MAX_RECOG_OPERANDS];
1929 /* The number of elements in the following array. */
1930 int curr_alt_dont_inherit_ops_num;
1931 /* Numbers of operands whose reload pseudos should not be inherited. */
1932 int curr_alt_dont_inherit_ops[MAX_RECOG_OPERANDS];
1933 rtx op;
1934 /* The register when the operand is a subreg of register, otherwise the
1935 operand itself. */
1936 rtx no_subreg_reg_operand[MAX_RECOG_OPERANDS];
1937 /* The register if the operand is a register or subreg of register,
1938 otherwise NULL. */
1939 rtx operand_reg[MAX_RECOG_OPERANDS];
1940 int hard_regno[MAX_RECOG_OPERANDS];
1941 machine_mode biggest_mode[MAX_RECOG_OPERANDS];
1942 int reload_nregs, reload_sum;
1943 bool costly_p;
1944 enum reg_class cl;
1946 /* Calculate some data common for all alternatives to speed up the
1947 function. */
1948 for (nop = 0; nop < n_operands; nop++)
1950 rtx reg;
1952 op = no_subreg_reg_operand[nop] = *curr_id->operand_loc[nop];
1953 /* The real hard regno of the operand after the allocation. */
1954 hard_regno[nop] = get_hard_regno (op, true);
1956 operand_reg[nop] = reg = op;
1957 biggest_mode[nop] = GET_MODE (op);
1958 if (GET_CODE (op) == SUBREG)
1960 biggest_mode[nop] = wider_subreg_mode (op);
1961 operand_reg[nop] = reg = SUBREG_REG (op);
1963 if (! REG_P (reg))
1964 operand_reg[nop] = NULL_RTX;
1965 else if (REGNO (reg) >= FIRST_PSEUDO_REGISTER
1966 || ((int) REGNO (reg)
1967 == lra_get_elimination_hard_regno (REGNO (reg))))
1968 no_subreg_reg_operand[nop] = reg;
1969 else
1970 operand_reg[nop] = no_subreg_reg_operand[nop]
1971 /* Just use natural mode for elimination result. It should
1972 be enough for extra constraints hooks. */
1973 = regno_reg_rtx[hard_regno[nop]];
1976 /* The constraints are made of several alternatives. Each operand's
1977 constraint looks like foo,bar,... with commas separating the
1978 alternatives. The first alternatives for all operands go
1979 together, the second alternatives go together, etc.
1981 First loop over alternatives. */
1982 alternative_mask preferred = curr_id->preferred_alternatives;
1983 if (only_alternative >= 0)
1984 preferred &= ALTERNATIVE_BIT (only_alternative);
1986 for (nalt = 0; nalt < n_alternatives; nalt++)
1988 /* Loop over operands for one constraint alternative. */
1989 if (!TEST_BIT (preferred, nalt))
1990 continue;
1992 curr_small_class_check++;
1993 overall = losers = addr_losers = 0;
1994 static_reject = reject = reload_nregs = reload_sum = 0;
1995 for (nop = 0; nop < n_operands; nop++)
1997 int inc = (curr_static_id
1998 ->operand_alternative[nalt * n_operands + nop].reject);
1999 if (lra_dump_file != NULL && inc != 0)
2000 fprintf (lra_dump_file,
2001 " Staticly defined alt reject+=%d\n", inc);
2002 static_reject += inc;
2004 reject += static_reject;
2005 early_clobbered_regs_num = 0;
2007 for (nop = 0; nop < n_operands; nop++)
2009 const char *p;
2010 char *end;
2011 int len, c, m, i, opalt_num, this_alternative_matches;
2012 bool win, did_match, offmemok, early_clobber_p;
2013 /* false => this operand can be reloaded somehow for this
2014 alternative. */
2015 bool badop;
2016 /* true => this operand can be reloaded if the alternative
2017 allows regs. */
2018 bool winreg;
2019 /* True if a constant forced into memory would be OK for
2020 this operand. */
2021 bool constmemok;
2022 enum reg_class this_alternative, this_costly_alternative;
2023 HARD_REG_SET this_alternative_set, this_costly_alternative_set;
2024 bool this_alternative_match_win, this_alternative_win;
2025 bool this_alternative_offmemok;
2026 bool scratch_p;
2027 machine_mode mode;
2028 enum constraint_num cn;
2030 opalt_num = nalt * n_operands + nop;
2031 if (curr_static_id->operand_alternative[opalt_num].anything_ok)
2033 /* Fast track for no constraints at all. */
2034 curr_alt[nop] = NO_REGS;
2035 CLEAR_HARD_REG_SET (curr_alt_set[nop]);
2036 curr_alt_win[nop] = true;
2037 curr_alt_match_win[nop] = false;
2038 curr_alt_offmemok[nop] = false;
2039 curr_alt_matches[nop] = -1;
2040 continue;
2043 op = no_subreg_reg_operand[nop];
2044 mode = curr_operand_mode[nop];
2046 win = did_match = winreg = offmemok = constmemok = false;
2047 badop = true;
2049 early_clobber_p = false;
2050 p = curr_static_id->operand_alternative[opalt_num].constraint;
2052 this_costly_alternative = this_alternative = NO_REGS;
2053 /* We update set of possible hard regs besides its class
2054 because reg class might be inaccurate. For example,
2055 union of LO_REGS (l), HI_REGS(h), and STACK_REG(k) in ARM
2056 is translated in HI_REGS because classes are merged by
2057 pairs and there is no accurate intermediate class. */
2058 CLEAR_HARD_REG_SET (this_alternative_set);
2059 CLEAR_HARD_REG_SET (this_costly_alternative_set);
2060 this_alternative_win = false;
2061 this_alternative_match_win = false;
2062 this_alternative_offmemok = false;
2063 this_alternative_matches = -1;
2065 /* An empty constraint should be excluded by the fast
2066 track. */
2067 lra_assert (*p != 0 && *p != ',');
2069 op_reject = 0;
2070 /* Scan this alternative's specs for this operand; set WIN
2071 if the operand fits any letter in this alternative.
2072 Otherwise, clear BADOP if this operand could fit some
2073 letter after reloads, or set WINREG if this operand could
2074 fit after reloads provided the constraint allows some
2075 registers. */
2076 costly_p = false;
2079 switch ((c = *p, len = CONSTRAINT_LEN (c, p)), c)
2081 case '\0':
2082 len = 0;
2083 break;
2084 case ',':
2085 c = '\0';
2086 break;
2088 case '&':
2089 early_clobber_p = true;
2090 break;
2092 case '$':
2093 op_reject += LRA_MAX_REJECT;
2094 break;
2095 case '^':
2096 op_reject += LRA_LOSER_COST_FACTOR;
2097 break;
2099 case '#':
2100 /* Ignore rest of this alternative. */
2101 c = '\0';
2102 break;
2104 case '0': case '1': case '2': case '3': case '4':
2105 case '5': case '6': case '7': case '8': case '9':
2107 int m_hregno;
2108 bool match_p;
2110 m = strtoul (p, &end, 10);
2111 p = end;
2112 len = 0;
2113 lra_assert (nop > m);
2115 this_alternative_matches = m;
2116 m_hregno = get_hard_regno (*curr_id->operand_loc[m], false);
2117 /* We are supposed to match a previous operand.
2118 If we do, we win if that one did. If we do
2119 not, count both of the operands as losers.
2120 (This is too conservative, since most of the
2121 time only a single reload insn will be needed
2122 to make the two operands win. As a result,
2123 this alternative may be rejected when it is
2124 actually desirable.) */
2125 match_p = false;
2126 if (operands_match_p (*curr_id->operand_loc[nop],
2127 *curr_id->operand_loc[m], m_hregno))
2129 /* We should reject matching of an early
2130 clobber operand if the matching operand is
2131 not dying in the insn. */
2132 if (! curr_static_id->operand[m].early_clobber
2133 || operand_reg[nop] == NULL_RTX
2134 || (find_regno_note (curr_insn, REG_DEAD,
2135 REGNO (op))
2136 || REGNO (op) == REGNO (operand_reg[m])))
2137 match_p = true;
2139 if (match_p)
2141 /* If we are matching a non-offsettable
2142 address where an offsettable address was
2143 expected, then we must reject this
2144 combination, because we can't reload
2145 it. */
2146 if (curr_alt_offmemok[m]
2147 && MEM_P (*curr_id->operand_loc[m])
2148 && curr_alt[m] == NO_REGS && ! curr_alt_win[m])
2149 continue;
2151 else
2153 /* Operands don't match. Both operands must
2154 allow a reload register, otherwise we
2155 cannot make them match. */
2156 if (curr_alt[m] == NO_REGS)
2157 break;
2158 /* Retroactively mark the operand we had to
2159 match as a loser, if it wasn't already and
2160 it wasn't matched to a register constraint
2161 (e.g it might be matched by memory). */
2162 if (curr_alt_win[m]
2163 && (operand_reg[m] == NULL_RTX
2164 || hard_regno[m] < 0))
2166 losers++;
2167 reload_nregs
2168 += (ira_reg_class_max_nregs[curr_alt[m]]
2169 [GET_MODE (*curr_id->operand_loc[m])]);
2172 /* Prefer matching earlyclobber alternative as
2173 it results in less hard regs required for
2174 the insn than a non-matching earlyclobber
2175 alternative. */
2176 if (curr_static_id->operand[m].early_clobber)
2178 if (lra_dump_file != NULL)
2179 fprintf
2180 (lra_dump_file,
2181 " %d Matching earlyclobber alt:"
2182 " reject--\n",
2183 nop);
2184 reject--;
2186 /* Otherwise we prefer no matching
2187 alternatives because it gives more freedom
2188 in RA. */
2189 else if (operand_reg[nop] == NULL_RTX
2190 || (find_regno_note (curr_insn, REG_DEAD,
2191 REGNO (operand_reg[nop]))
2192 == NULL_RTX))
2194 if (lra_dump_file != NULL)
2195 fprintf
2196 (lra_dump_file,
2197 " %d Matching alt: reject+=2\n",
2198 nop);
2199 reject += 2;
2202 /* If we have to reload this operand and some
2203 previous operand also had to match the same
2204 thing as this operand, we don't know how to do
2205 that. */
2206 if (!match_p || !curr_alt_win[m])
2208 for (i = 0; i < nop; i++)
2209 if (curr_alt_matches[i] == m)
2210 break;
2211 if (i < nop)
2212 break;
2214 else
2215 did_match = true;
2217 /* This can be fixed with reloads if the operand
2218 we are supposed to match can be fixed with
2219 reloads. */
2220 badop = false;
2221 this_alternative = curr_alt[m];
2222 COPY_HARD_REG_SET (this_alternative_set, curr_alt_set[m]);
2223 winreg = this_alternative != NO_REGS;
2224 break;
2227 case 'g':
2228 if (MEM_P (op)
2229 || general_constant_p (op)
2230 || spilled_pseudo_p (op))
2231 win = true;
2232 cl = GENERAL_REGS;
2233 goto reg;
2235 default:
2236 cn = lookup_constraint (p);
2237 switch (get_constraint_type (cn))
2239 case CT_REGISTER:
2240 cl = reg_class_for_constraint (cn);
2241 if (cl != NO_REGS)
2242 goto reg;
2243 break;
2245 case CT_CONST_INT:
2246 if (CONST_INT_P (op)
2247 && insn_const_int_ok_for_constraint (INTVAL (op), cn))
2248 win = true;
2249 break;
2251 case CT_MEMORY:
2252 if (MEM_P (op)
2253 && satisfies_memory_constraint_p (op, cn))
2254 win = true;
2255 else if (spilled_pseudo_p (op))
2256 win = true;
2258 /* If we didn't already win, we can reload constants
2259 via force_const_mem or put the pseudo value into
2260 memory, or make other memory by reloading the
2261 address like for 'o'. */
2262 if (CONST_POOL_OK_P (mode, op)
2263 || MEM_P (op) || REG_P (op)
2264 /* We can restore the equiv insn by a
2265 reload. */
2266 || equiv_substition_p[nop])
2267 badop = false;
2268 constmemok = true;
2269 offmemok = true;
2270 break;
2272 case CT_ADDRESS:
2273 /* If we didn't already win, we can reload the address
2274 into a base register. */
2275 if (satisfies_address_constraint_p (op, cn))
2276 win = true;
2277 cl = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
2278 ADDRESS, SCRATCH);
2279 badop = false;
2280 goto reg;
2282 case CT_FIXED_FORM:
2283 if (constraint_satisfied_p (op, cn))
2284 win = true;
2285 break;
2287 case CT_SPECIAL_MEMORY:
2288 if (MEM_P (op)
2289 && satisfies_memory_constraint_p (op, cn))
2290 win = true;
2291 else if (spilled_pseudo_p (op))
2292 win = true;
2293 break;
2295 break;
2297 reg:
2298 this_alternative = reg_class_subunion[this_alternative][cl];
2299 IOR_HARD_REG_SET (this_alternative_set,
2300 reg_class_contents[cl]);
2301 if (costly_p)
2303 this_costly_alternative
2304 = reg_class_subunion[this_costly_alternative][cl];
2305 IOR_HARD_REG_SET (this_costly_alternative_set,
2306 reg_class_contents[cl]);
2308 if (mode == BLKmode)
2309 break;
2310 winreg = true;
2311 if (REG_P (op))
2313 if (hard_regno[nop] >= 0
2314 && in_hard_reg_set_p (this_alternative_set,
2315 mode, hard_regno[nop]))
2316 win = true;
2317 else if (hard_regno[nop] < 0
2318 && in_class_p (op, this_alternative, NULL))
2319 win = true;
2321 break;
2323 if (c != ' ' && c != '\t')
2324 costly_p = c == '*';
2326 while ((p += len), c);
2328 scratch_p = (operand_reg[nop] != NULL_RTX
2329 && lra_former_scratch_p (REGNO (operand_reg[nop])));
2330 /* Record which operands fit this alternative. */
2331 if (win)
2333 this_alternative_win = true;
2334 if (operand_reg[nop] != NULL_RTX)
2336 if (hard_regno[nop] >= 0)
2338 if (in_hard_reg_set_p (this_costly_alternative_set,
2339 mode, hard_regno[nop]))
2341 if (lra_dump_file != NULL)
2342 fprintf (lra_dump_file,
2343 " %d Costly set: reject++\n",
2344 nop);
2345 reject++;
2348 else
2350 /* Prefer won reg to spilled pseudo under other
2351 equal conditions for possibe inheritance. */
2352 if (! scratch_p)
2354 if (lra_dump_file != NULL)
2355 fprintf
2356 (lra_dump_file,
2357 " %d Non pseudo reload: reject++\n",
2358 nop);
2359 reject++;
2361 if (in_class_p (operand_reg[nop],
2362 this_costly_alternative, NULL))
2364 if (lra_dump_file != NULL)
2365 fprintf
2366 (lra_dump_file,
2367 " %d Non pseudo costly reload:"
2368 " reject++\n",
2369 nop);
2370 reject++;
2373 /* We simulate the behavior of old reload here.
2374 Although scratches need hard registers and it
2375 might result in spilling other pseudos, no reload
2376 insns are generated for the scratches. So it
2377 might cost something but probably less than old
2378 reload pass believes. */
2379 if (scratch_p)
2381 if (lra_dump_file != NULL)
2382 fprintf (lra_dump_file,
2383 " %d Scratch win: reject+=2\n",
2384 nop);
2385 reject += 2;
2389 else if (did_match)
2390 this_alternative_match_win = true;
2391 else
2393 int const_to_mem = 0;
2394 bool no_regs_p;
2396 reject += op_reject;
2397 /* Never do output reload of stack pointer. It makes
2398 impossible to do elimination when SP is changed in
2399 RTL. */
2400 if (op == stack_pointer_rtx && ! frame_pointer_needed
2401 && curr_static_id->operand[nop].type != OP_IN)
2402 goto fail;
2404 /* If this alternative asks for a specific reg class, see if there
2405 is at least one allocatable register in that class. */
2406 no_regs_p
2407 = (this_alternative == NO_REGS
2408 || (hard_reg_set_subset_p
2409 (reg_class_contents[this_alternative],
2410 lra_no_alloc_regs)));
2412 /* For asms, verify that the class for this alternative is possible
2413 for the mode that is specified. */
2414 if (!no_regs_p && INSN_CODE (curr_insn) < 0)
2416 int i;
2417 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2418 if (targetm.hard_regno_mode_ok (i, mode)
2419 && in_hard_reg_set_p (reg_class_contents[this_alternative],
2420 mode, i))
2421 break;
2422 if (i == FIRST_PSEUDO_REGISTER)
2423 winreg = false;
2426 /* If this operand accepts a register, and if the
2427 register class has at least one allocatable register,
2428 then this operand can be reloaded. */
2429 if (winreg && !no_regs_p)
2430 badop = false;
2432 if (badop)
2434 if (lra_dump_file != NULL)
2435 fprintf (lra_dump_file,
2436 " alt=%d: Bad operand -- refuse\n",
2437 nalt);
2438 goto fail;
2441 if (this_alternative != NO_REGS)
2443 HARD_REG_SET available_regs;
2445 COPY_HARD_REG_SET (available_regs,
2446 reg_class_contents[this_alternative]);
2447 AND_COMPL_HARD_REG_SET
2448 (available_regs,
2449 ira_prohibited_class_mode_regs[this_alternative][mode]);
2450 AND_COMPL_HARD_REG_SET (available_regs, lra_no_alloc_regs);
2451 if (hard_reg_set_empty_p (available_regs))
2453 /* There are no hard regs holding a value of given
2454 mode. */
2455 if (offmemok)
2457 this_alternative = NO_REGS;
2458 if (lra_dump_file != NULL)
2459 fprintf (lra_dump_file,
2460 " %d Using memory because of"
2461 " a bad mode: reject+=2\n",
2462 nop);
2463 reject += 2;
2465 else
2467 if (lra_dump_file != NULL)
2468 fprintf (lra_dump_file,
2469 " alt=%d: Wrong mode -- refuse\n",
2470 nalt);
2471 goto fail;
2476 /* If not assigned pseudo has a class which a subset of
2477 required reg class, it is a less costly alternative
2478 as the pseudo still can get a hard reg of necessary
2479 class. */
2480 if (! no_regs_p && REG_P (op) && hard_regno[nop] < 0
2481 && (cl = get_reg_class (REGNO (op))) != NO_REGS
2482 && ira_class_subset_p[this_alternative][cl])
2484 if (lra_dump_file != NULL)
2485 fprintf
2486 (lra_dump_file,
2487 " %d Super set class reg: reject-=3\n", nop);
2488 reject -= 3;
2491 this_alternative_offmemok = offmemok;
2492 if (this_costly_alternative != NO_REGS)
2494 if (lra_dump_file != NULL)
2495 fprintf (lra_dump_file,
2496 " %d Costly loser: reject++\n", nop);
2497 reject++;
2499 /* If the operand is dying, has a matching constraint,
2500 and satisfies constraints of the matched operand
2501 which failed to satisfy the own constraints, most probably
2502 the reload for this operand will be gone. */
2503 if (this_alternative_matches >= 0
2504 && !curr_alt_win[this_alternative_matches]
2505 && REG_P (op)
2506 && find_regno_note (curr_insn, REG_DEAD, REGNO (op))
2507 && (hard_regno[nop] >= 0
2508 ? in_hard_reg_set_p (this_alternative_set,
2509 mode, hard_regno[nop])
2510 : in_class_p (op, this_alternative, NULL)))
2512 if (lra_dump_file != NULL)
2513 fprintf
2514 (lra_dump_file,
2515 " %d Dying matched operand reload: reject++\n",
2516 nop);
2517 reject++;
2519 else
2521 /* Strict_low_part requires to reload the register
2522 not the sub-register. In this case we should
2523 check that a final reload hard reg can hold the
2524 value mode. */
2525 if (curr_static_id->operand[nop].strict_low
2526 && REG_P (op)
2527 && hard_regno[nop] < 0
2528 && GET_CODE (*curr_id->operand_loc[nop]) == SUBREG
2529 && ira_class_hard_regs_num[this_alternative] > 0
2530 && (!targetm.hard_regno_mode_ok
2531 (ira_class_hard_regs[this_alternative][0],
2532 GET_MODE (*curr_id->operand_loc[nop]))))
2534 if (lra_dump_file != NULL)
2535 fprintf
2536 (lra_dump_file,
2537 " alt=%d: Strict low subreg reload -- refuse\n",
2538 nalt);
2539 goto fail;
2541 losers++;
2543 if (operand_reg[nop] != NULL_RTX
2544 /* Output operands and matched input operands are
2545 not inherited. The following conditions do not
2546 exactly describe the previous statement but they
2547 are pretty close. */
2548 && curr_static_id->operand[nop].type != OP_OUT
2549 && (this_alternative_matches < 0
2550 || curr_static_id->operand[nop].type != OP_IN))
2552 int last_reload = (lra_reg_info[ORIGINAL_REGNO
2553 (operand_reg[nop])]
2554 .last_reload);
2556 /* The value of reload_sum has sense only if we
2557 process insns in their order. It happens only on
2558 the first constraints sub-pass when we do most of
2559 reload work. */
2560 if (lra_constraint_iter == 1 && last_reload > bb_reload_num)
2561 reload_sum += last_reload - bb_reload_num;
2563 /* If this is a constant that is reloaded into the
2564 desired class by copying it to memory first, count
2565 that as another reload. This is consistent with
2566 other code and is required to avoid choosing another
2567 alternative when the constant is moved into memory.
2568 Note that the test here is precisely the same as in
2569 the code below that calls force_const_mem. */
2570 if (CONST_POOL_OK_P (mode, op)
2571 && ((targetm.preferred_reload_class
2572 (op, this_alternative) == NO_REGS)
2573 || no_input_reloads_p))
2575 const_to_mem = 1;
2576 if (! no_regs_p)
2577 losers++;
2580 /* Alternative loses if it requires a type of reload not
2581 permitted for this insn. We can always reload
2582 objects with a REG_UNUSED note. */
2583 if ((curr_static_id->operand[nop].type != OP_IN
2584 && no_output_reloads_p
2585 && ! find_reg_note (curr_insn, REG_UNUSED, op))
2586 || (curr_static_id->operand[nop].type != OP_OUT
2587 && no_input_reloads_p && ! const_to_mem)
2588 || (this_alternative_matches >= 0
2589 && (no_input_reloads_p
2590 || (no_output_reloads_p
2591 && (curr_static_id->operand
2592 [this_alternative_matches].type != OP_IN)
2593 && ! find_reg_note (curr_insn, REG_UNUSED,
2594 no_subreg_reg_operand
2595 [this_alternative_matches])))))
2597 if (lra_dump_file != NULL)
2598 fprintf
2599 (lra_dump_file,
2600 " alt=%d: No input/otput reload -- refuse\n",
2601 nalt);
2602 goto fail;
2605 /* Alternative loses if it required class pseudo can not
2606 hold value of required mode. Such insns can be
2607 described by insn definitions with mode iterators. */
2608 if (GET_MODE (*curr_id->operand_loc[nop]) != VOIDmode
2609 && ! hard_reg_set_empty_p (this_alternative_set)
2610 /* It is common practice for constraints to use a
2611 class which does not have actually enough regs to
2612 hold the value (e.g. x86 AREG for mode requiring
2613 more one general reg). Therefore we have 2
2614 conditions to check that the reload pseudo can
2615 not hold the mode value. */
2616 && (!targetm.hard_regno_mode_ok
2617 (ira_class_hard_regs[this_alternative][0],
2618 GET_MODE (*curr_id->operand_loc[nop])))
2619 /* The above condition is not enough as the first
2620 reg in ira_class_hard_regs can be not aligned for
2621 multi-words mode values. */
2622 && (prohibited_class_reg_set_mode_p
2623 (this_alternative, this_alternative_set,
2624 GET_MODE (*curr_id->operand_loc[nop]))))
2626 if (lra_dump_file != NULL)
2627 fprintf (lra_dump_file,
2628 " alt=%d: reload pseudo for op %d "
2629 " can not hold the mode value -- refuse\n",
2630 nalt, nop);
2631 goto fail;
2634 /* Check strong discouragement of reload of non-constant
2635 into class THIS_ALTERNATIVE. */
2636 if (! CONSTANT_P (op) && ! no_regs_p
2637 && (targetm.preferred_reload_class
2638 (op, this_alternative) == NO_REGS
2639 || (curr_static_id->operand[nop].type == OP_OUT
2640 && (targetm.preferred_output_reload_class
2641 (op, this_alternative) == NO_REGS))))
2643 if (lra_dump_file != NULL)
2644 fprintf (lra_dump_file,
2645 " %d Non-prefered reload: reject+=%d\n",
2646 nop, LRA_MAX_REJECT);
2647 reject += LRA_MAX_REJECT;
2650 if (! (MEM_P (op) && offmemok)
2651 && ! (const_to_mem && constmemok))
2653 /* We prefer to reload pseudos over reloading other
2654 things, since such reloads may be able to be
2655 eliminated later. So bump REJECT in other cases.
2656 Don't do this in the case where we are forcing a
2657 constant into memory and it will then win since
2658 we don't want to have a different alternative
2659 match then. */
2660 if (! (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER))
2662 if (lra_dump_file != NULL)
2663 fprintf
2664 (lra_dump_file,
2665 " %d Non-pseudo reload: reject+=2\n",
2666 nop);
2667 reject += 2;
2670 if (! no_regs_p)
2671 reload_nregs
2672 += ira_reg_class_max_nregs[this_alternative][mode];
2674 if (SMALL_REGISTER_CLASS_P (this_alternative))
2676 if (lra_dump_file != NULL)
2677 fprintf
2678 (lra_dump_file,
2679 " %d Small class reload: reject+=%d\n",
2680 nop, LRA_LOSER_COST_FACTOR / 2);
2681 reject += LRA_LOSER_COST_FACTOR / 2;
2685 /* We are trying to spill pseudo into memory. It is
2686 usually more costly than moving to a hard register
2687 although it might takes the same number of
2688 reloads.
2690 Non-pseudo spill may happen also. Suppose a target allows both
2691 register and memory in the operand constraint alternatives,
2692 then it's typical that an eliminable register has a substition
2693 of "base + offset" which can either be reloaded by a simple
2694 "new_reg <= base + offset" which will match the register
2695 constraint, or a similar reg addition followed by further spill
2696 to and reload from memory which will match the memory
2697 constraint, but this memory spill will be much more costly
2698 usually.
2700 Code below increases the reject for both pseudo and non-pseudo
2701 spill. */
2702 if (no_regs_p
2703 && !(MEM_P (op) && offmemok)
2704 && !(REG_P (op) && hard_regno[nop] < 0))
2706 if (lra_dump_file != NULL)
2707 fprintf
2708 (lra_dump_file,
2709 " %d Spill %spseudo into memory: reject+=3\n",
2710 nop, REG_P (op) ? "" : "Non-");
2711 reject += 3;
2712 if (VECTOR_MODE_P (mode))
2714 /* Spilling vectors into memory is usually more
2715 costly as they contain big values. */
2716 if (lra_dump_file != NULL)
2717 fprintf
2718 (lra_dump_file,
2719 " %d Spill vector pseudo: reject+=2\n",
2720 nop);
2721 reject += 2;
2725 /* When we use an operand requiring memory in given
2726 alternative, the insn should write *and* read the
2727 value to/from memory it is costly in comparison with
2728 an insn alternative which does not use memory
2729 (e.g. register or immediate operand). We exclude
2730 memory operand for such case as we can satisfy the
2731 memory constraints by reloading address. */
2732 if (no_regs_p && offmemok && !MEM_P (op))
2734 if (lra_dump_file != NULL)
2735 fprintf
2736 (lra_dump_file,
2737 " Using memory insn operand %d: reject+=3\n",
2738 nop);
2739 reject += 3;
2742 /* If reload requires moving value through secondary
2743 memory, it will need one more insn at least. */
2744 if (this_alternative != NO_REGS
2745 && REG_P (op) && (cl = get_reg_class (REGNO (op))) != NO_REGS
2746 && ((curr_static_id->operand[nop].type != OP_OUT
2747 && targetm.secondary_memory_needed (GET_MODE (op), cl,
2748 this_alternative))
2749 || (curr_static_id->operand[nop].type != OP_IN
2750 && (targetm.secondary_memory_needed
2751 (GET_MODE (op), this_alternative, cl)))))
2752 losers++;
2754 /* Input reloads can be inherited more often than output
2755 reloads can be removed, so penalize output
2756 reloads. */
2757 if (!REG_P (op) || curr_static_id->operand[nop].type != OP_IN)
2759 if (lra_dump_file != NULL)
2760 fprintf
2761 (lra_dump_file,
2762 " %d Non input pseudo reload: reject++\n",
2763 nop);
2764 reject++;
2767 if (MEM_P (op) && offmemok)
2768 addr_losers++;
2769 else if (curr_static_id->operand[nop].type == OP_INOUT)
2771 if (lra_dump_file != NULL)
2772 fprintf
2773 (lra_dump_file,
2774 " %d Input/Output reload: reject+=%d\n",
2775 nop, LRA_LOSER_COST_FACTOR);
2776 reject += LRA_LOSER_COST_FACTOR;
2780 if (early_clobber_p && ! scratch_p)
2782 if (lra_dump_file != NULL)
2783 fprintf (lra_dump_file,
2784 " %d Early clobber: reject++\n", nop);
2785 reject++;
2787 /* ??? We check early clobbers after processing all operands
2788 (see loop below) and there we update the costs more.
2789 Should we update the cost (may be approximately) here
2790 because of early clobber register reloads or it is a rare
2791 or non-important thing to be worth to do it. */
2792 overall = (losers * LRA_LOSER_COST_FACTOR + reject
2793 - (addr_losers == losers ? static_reject : 0));
2794 if ((best_losers == 0 || losers != 0) && best_overall < overall)
2796 if (lra_dump_file != NULL)
2797 fprintf (lra_dump_file,
2798 " alt=%d,overall=%d,losers=%d -- refuse\n",
2799 nalt, overall, losers);
2800 goto fail;
2803 if (update_and_check_small_class_inputs (nop, this_alternative))
2805 if (lra_dump_file != NULL)
2806 fprintf (lra_dump_file,
2807 " alt=%d, not enough small class regs -- refuse\n",
2808 nalt);
2809 goto fail;
2811 curr_alt[nop] = this_alternative;
2812 COPY_HARD_REG_SET (curr_alt_set[nop], this_alternative_set);
2813 curr_alt_win[nop] = this_alternative_win;
2814 curr_alt_match_win[nop] = this_alternative_match_win;
2815 curr_alt_offmemok[nop] = this_alternative_offmemok;
2816 curr_alt_matches[nop] = this_alternative_matches;
2818 if (this_alternative_matches >= 0
2819 && !did_match && !this_alternative_win)
2820 curr_alt_win[this_alternative_matches] = false;
2822 if (early_clobber_p && operand_reg[nop] != NULL_RTX)
2823 early_clobbered_nops[early_clobbered_regs_num++] = nop;
2826 if (curr_insn_set != NULL_RTX && n_operands == 2
2827 /* Prevent processing non-move insns. */
2828 && (GET_CODE (SET_SRC (curr_insn_set)) == SUBREG
2829 || SET_SRC (curr_insn_set) == no_subreg_reg_operand[1])
2830 && ((! curr_alt_win[0] && ! curr_alt_win[1]
2831 && REG_P (no_subreg_reg_operand[0])
2832 && REG_P (no_subreg_reg_operand[1])
2833 && (reg_in_class_p (no_subreg_reg_operand[0], curr_alt[1])
2834 || reg_in_class_p (no_subreg_reg_operand[1], curr_alt[0])))
2835 || (! curr_alt_win[0] && curr_alt_win[1]
2836 && REG_P (no_subreg_reg_operand[1])
2837 /* Check that we reload memory not the memory
2838 address. */
2839 && ! (curr_alt_offmemok[0]
2840 && MEM_P (no_subreg_reg_operand[0]))
2841 && reg_in_class_p (no_subreg_reg_operand[1], curr_alt[0]))
2842 || (curr_alt_win[0] && ! curr_alt_win[1]
2843 && REG_P (no_subreg_reg_operand[0])
2844 /* Check that we reload memory not the memory
2845 address. */
2846 && ! (curr_alt_offmemok[1]
2847 && MEM_P (no_subreg_reg_operand[1]))
2848 && reg_in_class_p (no_subreg_reg_operand[0], curr_alt[1])
2849 && (! CONST_POOL_OK_P (curr_operand_mode[1],
2850 no_subreg_reg_operand[1])
2851 || (targetm.preferred_reload_class
2852 (no_subreg_reg_operand[1],
2853 (enum reg_class) curr_alt[1]) != NO_REGS))
2854 /* If it is a result of recent elimination in move
2855 insn we can transform it into an add still by
2856 using this alternative. */
2857 && GET_CODE (no_subreg_reg_operand[1]) != PLUS)))
2859 /* We have a move insn and a new reload insn will be similar
2860 to the current insn. We should avoid such situation as
2861 it results in LRA cycling. */
2862 if (lra_dump_file != NULL)
2863 fprintf (lra_dump_file,
2864 " Cycle danger: overall += LRA_MAX_REJECT\n");
2865 overall += LRA_MAX_REJECT;
2867 ok_p = true;
2868 curr_alt_dont_inherit_ops_num = 0;
2869 for (nop = 0; nop < early_clobbered_regs_num; nop++)
2871 int i, j, clobbered_hard_regno, first_conflict_j, last_conflict_j;
2872 HARD_REG_SET temp_set;
2874 i = early_clobbered_nops[nop];
2875 if ((! curr_alt_win[i] && ! curr_alt_match_win[i])
2876 || hard_regno[i] < 0)
2877 continue;
2878 lra_assert (operand_reg[i] != NULL_RTX);
2879 clobbered_hard_regno = hard_regno[i];
2880 CLEAR_HARD_REG_SET (temp_set);
2881 add_to_hard_reg_set (&temp_set, biggest_mode[i], clobbered_hard_regno);
2882 first_conflict_j = last_conflict_j = -1;
2883 for (j = 0; j < n_operands; j++)
2884 if (j == i
2885 /* We don't want process insides of match_operator and
2886 match_parallel because otherwise we would process
2887 their operands once again generating a wrong
2888 code. */
2889 || curr_static_id->operand[j].is_operator)
2890 continue;
2891 else if ((curr_alt_matches[j] == i && curr_alt_match_win[j])
2892 || (curr_alt_matches[i] == j && curr_alt_match_win[i]))
2893 continue;
2894 /* If we don't reload j-th operand, check conflicts. */
2895 else if ((curr_alt_win[j] || curr_alt_match_win[j])
2896 && uses_hard_regs_p (*curr_id->operand_loc[j], temp_set))
2898 if (first_conflict_j < 0)
2899 first_conflict_j = j;
2900 last_conflict_j = j;
2902 if (last_conflict_j < 0)
2903 continue;
2904 /* If earlyclobber operand conflicts with another
2905 non-matching operand which is actually the same register
2906 as the earlyclobber operand, it is better to reload the
2907 another operand as an operand matching the earlyclobber
2908 operand can be also the same. */
2909 if (first_conflict_j == last_conflict_j
2910 && operand_reg[last_conflict_j] != NULL_RTX
2911 && ! curr_alt_match_win[last_conflict_j]
2912 && REGNO (operand_reg[i]) == REGNO (operand_reg[last_conflict_j]))
2914 curr_alt_win[last_conflict_j] = false;
2915 curr_alt_dont_inherit_ops[curr_alt_dont_inherit_ops_num++]
2916 = last_conflict_j;
2917 losers++;
2918 /* Early clobber was already reflected in REJECT. */
2919 lra_assert (reject > 0);
2920 if (lra_dump_file != NULL)
2921 fprintf
2922 (lra_dump_file,
2923 " %d Conflict early clobber reload: reject--\n",
2925 reject--;
2926 overall += LRA_LOSER_COST_FACTOR - 1;
2928 else
2930 /* We need to reload early clobbered register and the
2931 matched registers. */
2932 for (j = 0; j < n_operands; j++)
2933 if (curr_alt_matches[j] == i)
2935 curr_alt_match_win[j] = false;
2936 losers++;
2937 overall += LRA_LOSER_COST_FACTOR;
2939 if (! curr_alt_match_win[i])
2940 curr_alt_dont_inherit_ops[curr_alt_dont_inherit_ops_num++] = i;
2941 else
2943 /* Remember pseudos used for match reloads are never
2944 inherited. */
2945 lra_assert (curr_alt_matches[i] >= 0);
2946 curr_alt_win[curr_alt_matches[i]] = false;
2948 curr_alt_win[i] = curr_alt_match_win[i] = false;
2949 losers++;
2950 /* Early clobber was already reflected in REJECT. */
2951 lra_assert (reject > 0);
2952 if (lra_dump_file != NULL)
2953 fprintf
2954 (lra_dump_file,
2955 " %d Matched conflict early clobber reloads: "
2956 "reject--\n",
2958 reject--;
2959 overall += LRA_LOSER_COST_FACTOR - 1;
2962 if (lra_dump_file != NULL)
2963 fprintf (lra_dump_file, " alt=%d,overall=%d,losers=%d,rld_nregs=%d\n",
2964 nalt, overall, losers, reload_nregs);
2966 /* If this alternative can be made to work by reloading, and it
2967 needs less reloading than the others checked so far, record
2968 it as the chosen goal for reloading. */
2969 if ((best_losers != 0 && losers == 0)
2970 || (((best_losers == 0 && losers == 0)
2971 || (best_losers != 0 && losers != 0))
2972 && (best_overall > overall
2973 || (best_overall == overall
2974 /* If the cost of the reloads is the same,
2975 prefer alternative which requires minimal
2976 number of reload regs. */
2977 && (reload_nregs < best_reload_nregs
2978 || (reload_nregs == best_reload_nregs
2979 && (best_reload_sum < reload_sum
2980 || (best_reload_sum == reload_sum
2981 && nalt < goal_alt_number))))))))
2983 for (nop = 0; nop < n_operands; nop++)
2985 goal_alt_win[nop] = curr_alt_win[nop];
2986 goal_alt_match_win[nop] = curr_alt_match_win[nop];
2987 goal_alt_matches[nop] = curr_alt_matches[nop];
2988 goal_alt[nop] = curr_alt[nop];
2989 goal_alt_offmemok[nop] = curr_alt_offmemok[nop];
2991 goal_alt_dont_inherit_ops_num = curr_alt_dont_inherit_ops_num;
2992 for (nop = 0; nop < curr_alt_dont_inherit_ops_num; nop++)
2993 goal_alt_dont_inherit_ops[nop] = curr_alt_dont_inherit_ops[nop];
2994 goal_alt_swapped = curr_swapped;
2995 best_overall = overall;
2996 best_losers = losers;
2997 best_reload_nregs = reload_nregs;
2998 best_reload_sum = reload_sum;
2999 goal_alt_number = nalt;
3001 if (losers == 0)
3002 /* Everything is satisfied. Do not process alternatives
3003 anymore. */
3004 break;
3005 fail:
3008 return ok_p;
3011 /* Make reload base reg from address AD. */
3012 static rtx
3013 base_to_reg (struct address_info *ad)
3015 enum reg_class cl;
3016 int code = -1;
3017 rtx new_inner = NULL_RTX;
3018 rtx new_reg = NULL_RTX;
3019 rtx_insn *insn;
3020 rtx_insn *last_insn = get_last_insn();
3022 lra_assert (ad->disp == ad->disp_term);
3023 cl = base_reg_class (ad->mode, ad->as, ad->base_outer_code,
3024 get_index_code (ad));
3025 new_reg = lra_create_new_reg (GET_MODE (*ad->base), NULL_RTX,
3026 cl, "base");
3027 new_inner = simplify_gen_binary (PLUS, GET_MODE (new_reg), new_reg,
3028 ad->disp_term == NULL
3029 ? const0_rtx
3030 : *ad->disp_term);
3031 if (!valid_address_p (ad->mode, new_inner, ad->as))
3032 return NULL_RTX;
3033 insn = emit_insn (gen_rtx_SET (new_reg, *ad->base));
3034 code = recog_memoized (insn);
3035 if (code < 0)
3037 delete_insns_since (last_insn);
3038 return NULL_RTX;
3041 return new_inner;
3044 /* Make reload base reg + disp from address AD. Return the new pseudo. */
3045 static rtx
3046 base_plus_disp_to_reg (struct address_info *ad)
3048 enum reg_class cl;
3049 rtx new_reg;
3051 lra_assert (ad->base == ad->base_term && ad->disp == ad->disp_term);
3052 cl = base_reg_class (ad->mode, ad->as, ad->base_outer_code,
3053 get_index_code (ad));
3054 new_reg = lra_create_new_reg (GET_MODE (*ad->base_term), NULL_RTX,
3055 cl, "base + disp");
3056 lra_emit_add (new_reg, *ad->base_term, *ad->disp_term);
3057 return new_reg;
3060 /* Make reload of index part of address AD. Return the new
3061 pseudo. */
3062 static rtx
3063 index_part_to_reg (struct address_info *ad)
3065 rtx new_reg;
3067 new_reg = lra_create_new_reg (GET_MODE (*ad->index), NULL_RTX,
3068 INDEX_REG_CLASS, "index term");
3069 expand_mult (GET_MODE (*ad->index), *ad->index_term,
3070 GEN_INT (get_index_scale (ad)), new_reg, 1);
3071 return new_reg;
3074 /* Return true if we can add a displacement to address AD, even if that
3075 makes the address invalid. The fix-up code requires any new address
3076 to be the sum of the BASE_TERM, INDEX and DISP_TERM fields. */
3077 static bool
3078 can_add_disp_p (struct address_info *ad)
3080 return (!ad->autoinc_p
3081 && ad->segment == NULL
3082 && ad->base == ad->base_term
3083 && ad->disp == ad->disp_term);
3086 /* Make equiv substitution in address AD. Return true if a substitution
3087 was made. */
3088 static bool
3089 equiv_address_substitution (struct address_info *ad)
3091 rtx base_reg, new_base_reg, index_reg, new_index_reg, *base_term, *index_term;
3092 poly_int64 disp;
3093 HOST_WIDE_INT scale;
3094 bool change_p;
3096 base_term = strip_subreg (ad->base_term);
3097 if (base_term == NULL)
3098 base_reg = new_base_reg = NULL_RTX;
3099 else
3101 base_reg = *base_term;
3102 new_base_reg = get_equiv_with_elimination (base_reg, curr_insn);
3104 index_term = strip_subreg (ad->index_term);
3105 if (index_term == NULL)
3106 index_reg = new_index_reg = NULL_RTX;
3107 else
3109 index_reg = *index_term;
3110 new_index_reg = get_equiv_with_elimination (index_reg, curr_insn);
3112 if (base_reg == new_base_reg && index_reg == new_index_reg)
3113 return false;
3114 disp = 0;
3115 change_p = false;
3116 if (lra_dump_file != NULL)
3118 fprintf (lra_dump_file, "Changing address in insn %d ",
3119 INSN_UID (curr_insn));
3120 dump_value_slim (lra_dump_file, *ad->outer, 1);
3122 if (base_reg != new_base_reg)
3124 poly_int64 offset;
3125 if (REG_P (new_base_reg))
3127 *base_term = new_base_reg;
3128 change_p = true;
3130 else if (GET_CODE (new_base_reg) == PLUS
3131 && REG_P (XEXP (new_base_reg, 0))
3132 && poly_int_rtx_p (XEXP (new_base_reg, 1), &offset)
3133 && can_add_disp_p (ad))
3135 disp += offset;
3136 *base_term = XEXP (new_base_reg, 0);
3137 change_p = true;
3139 if (ad->base_term2 != NULL)
3140 *ad->base_term2 = *ad->base_term;
3142 if (index_reg != new_index_reg)
3144 poly_int64 offset;
3145 if (REG_P (new_index_reg))
3147 *index_term = new_index_reg;
3148 change_p = true;
3150 else if (GET_CODE (new_index_reg) == PLUS
3151 && REG_P (XEXP (new_index_reg, 0))
3152 && poly_int_rtx_p (XEXP (new_index_reg, 1), &offset)
3153 && can_add_disp_p (ad)
3154 && (scale = get_index_scale (ad)))
3156 disp += offset * scale;
3157 *index_term = XEXP (new_index_reg, 0);
3158 change_p = true;
3161 if (maybe_ne (disp, 0))
3163 if (ad->disp != NULL)
3164 *ad->disp = plus_constant (GET_MODE (*ad->inner), *ad->disp, disp);
3165 else
3167 *ad->inner = plus_constant (GET_MODE (*ad->inner), *ad->inner, disp);
3168 update_address (ad);
3170 change_p = true;
3172 if (lra_dump_file != NULL)
3174 if (! change_p)
3175 fprintf (lra_dump_file, " -- no change\n");
3176 else
3178 fprintf (lra_dump_file, " on equiv ");
3179 dump_value_slim (lra_dump_file, *ad->outer, 1);
3180 fprintf (lra_dump_file, "\n");
3183 return change_p;
3186 /* Major function to make reloads for an address in operand NOP or
3187 check its correctness (If CHECK_ONLY_P is true). The supported
3188 cases are:
3190 1) an address that existed before LRA started, at which point it
3191 must have been valid. These addresses are subject to elimination
3192 and may have become invalid due to the elimination offset being out
3193 of range.
3195 2) an address created by forcing a constant to memory
3196 (force_const_to_mem). The initial form of these addresses might
3197 not be valid, and it is this function's job to make them valid.
3199 3) a frame address formed from a register and a (possibly zero)
3200 constant offset. As above, these addresses might not be valid and
3201 this function must make them so.
3203 Add reloads to the lists *BEFORE and *AFTER. We might need to add
3204 reloads to *AFTER because of inc/dec, {pre, post} modify in the
3205 address. Return true for any RTL change.
3207 The function is a helper function which does not produce all
3208 transformations (when CHECK_ONLY_P is false) which can be
3209 necessary. It does just basic steps. To do all necessary
3210 transformations use function process_address. */
3211 static bool
3212 process_address_1 (int nop, bool check_only_p,
3213 rtx_insn **before, rtx_insn **after)
3215 struct address_info ad;
3216 rtx new_reg;
3217 HOST_WIDE_INT scale;
3218 rtx op = *curr_id->operand_loc[nop];
3219 const char *constraint = curr_static_id->operand[nop].constraint;
3220 enum constraint_num cn = lookup_constraint (constraint);
3221 bool change_p = false;
3223 if (MEM_P (op)
3224 && GET_MODE (op) == BLKmode
3225 && GET_CODE (XEXP (op, 0)) == SCRATCH)
3226 return false;
3228 if (insn_extra_address_constraint (cn))
3229 decompose_lea_address (&ad, curr_id->operand_loc[nop]);
3230 /* Do not attempt to decompose arbitrary addresses generated by combine
3231 for asm operands with loose constraints, e.g 'X'. */
3232 else if (MEM_P (op)
3233 && !(INSN_CODE (curr_insn) < 0
3234 && get_constraint_type (cn) == CT_FIXED_FORM
3235 && constraint_satisfied_p (op, cn)))
3236 decompose_mem_address (&ad, op);
3237 else if (GET_CODE (op) == SUBREG
3238 && MEM_P (SUBREG_REG (op)))
3239 decompose_mem_address (&ad, SUBREG_REG (op));
3240 else
3241 return false;
3242 /* If INDEX_REG_CLASS is assigned to base_term already and isn't to
3243 index_term, swap them so to avoid assigning INDEX_REG_CLASS to both
3244 when INDEX_REG_CLASS is a single register class. */
3245 if (ad.base_term != NULL
3246 && ad.index_term != NULL
3247 && ira_class_hard_regs_num[INDEX_REG_CLASS] == 1
3248 && REG_P (*ad.base_term)
3249 && REG_P (*ad.index_term)
3250 && in_class_p (*ad.base_term, INDEX_REG_CLASS, NULL)
3251 && ! in_class_p (*ad.index_term, INDEX_REG_CLASS, NULL))
3253 std::swap (ad.base, ad.index);
3254 std::swap (ad.base_term, ad.index_term);
3256 if (! check_only_p)
3257 change_p = equiv_address_substitution (&ad);
3258 if (ad.base_term != NULL
3259 && (process_addr_reg
3260 (ad.base_term, check_only_p, before,
3261 (ad.autoinc_p
3262 && !(REG_P (*ad.base_term)
3263 && find_regno_note (curr_insn, REG_DEAD,
3264 REGNO (*ad.base_term)) != NULL_RTX)
3265 ? after : NULL),
3266 base_reg_class (ad.mode, ad.as, ad.base_outer_code,
3267 get_index_code (&ad)))))
3269 change_p = true;
3270 if (ad.base_term2 != NULL)
3271 *ad.base_term2 = *ad.base_term;
3273 if (ad.index_term != NULL
3274 && process_addr_reg (ad.index_term, check_only_p,
3275 before, NULL, INDEX_REG_CLASS))
3276 change_p = true;
3278 /* Target hooks sometimes don't treat extra-constraint addresses as
3279 legitimate address_operands, so handle them specially. */
3280 if (insn_extra_address_constraint (cn)
3281 && satisfies_address_constraint_p (&ad, cn))
3282 return change_p;
3284 if (check_only_p)
3285 return change_p;
3287 /* There are three cases where the shape of *AD.INNER may now be invalid:
3289 1) the original address was valid, but either elimination or
3290 equiv_address_substitution was applied and that made
3291 the address invalid.
3293 2) the address is an invalid symbolic address created by
3294 force_const_to_mem.
3296 3) the address is a frame address with an invalid offset.
3298 4) the address is a frame address with an invalid base.
3300 All these cases involve a non-autoinc address, so there is no
3301 point revalidating other types. */
3302 if (ad.autoinc_p || valid_address_p (&ad))
3303 return change_p;
3305 /* Any index existed before LRA started, so we can assume that the
3306 presence and shape of the index is valid. */
3307 push_to_sequence (*before);
3308 lra_assert (ad.disp == ad.disp_term);
3309 if (ad.base == NULL)
3311 if (ad.index == NULL)
3313 rtx_insn *insn;
3314 rtx_insn *last = get_last_insn ();
3315 int code = -1;
3316 enum reg_class cl = base_reg_class (ad.mode, ad.as,
3317 SCRATCH, SCRATCH);
3318 rtx addr = *ad.inner;
3320 new_reg = lra_create_new_reg (Pmode, NULL_RTX, cl, "addr");
3321 if (HAVE_lo_sum)
3323 /* addr => lo_sum (new_base, addr), case (2) above. */
3324 insn = emit_insn (gen_rtx_SET
3325 (new_reg,
3326 gen_rtx_HIGH (Pmode, copy_rtx (addr))));
3327 code = recog_memoized (insn);
3328 if (code >= 0)
3330 *ad.inner = gen_rtx_LO_SUM (Pmode, new_reg, addr);
3331 if (! valid_address_p (ad.mode, *ad.outer, ad.as))
3333 /* Try to put lo_sum into register. */
3334 insn = emit_insn (gen_rtx_SET
3335 (new_reg,
3336 gen_rtx_LO_SUM (Pmode, new_reg, addr)));
3337 code = recog_memoized (insn);
3338 if (code >= 0)
3340 *ad.inner = new_reg;
3341 if (! valid_address_p (ad.mode, *ad.outer, ad.as))
3343 *ad.inner = addr;
3344 code = -1;
3350 if (code < 0)
3351 delete_insns_since (last);
3354 if (code < 0)
3356 /* addr => new_base, case (2) above. */
3357 lra_emit_move (new_reg, addr);
3359 for (insn = last == NULL_RTX ? get_insns () : NEXT_INSN (last);
3360 insn != NULL_RTX;
3361 insn = NEXT_INSN (insn))
3362 if (recog_memoized (insn) < 0)
3363 break;
3364 if (insn != NULL_RTX)
3366 /* Do nothing if we cannot generate right insns.
3367 This is analogous to reload pass behavior. */
3368 delete_insns_since (last);
3369 end_sequence ();
3370 return false;
3372 *ad.inner = new_reg;
3375 else
3377 /* index * scale + disp => new base + index * scale,
3378 case (1) above. */
3379 enum reg_class cl = base_reg_class (ad.mode, ad.as, PLUS,
3380 GET_CODE (*ad.index));
3382 lra_assert (INDEX_REG_CLASS != NO_REGS);
3383 new_reg = lra_create_new_reg (Pmode, NULL_RTX, cl, "disp");
3384 lra_emit_move (new_reg, *ad.disp);
3385 *ad.inner = simplify_gen_binary (PLUS, GET_MODE (new_reg),
3386 new_reg, *ad.index);
3389 else if (ad.index == NULL)
3391 int regno;
3392 enum reg_class cl;
3393 rtx set;
3394 rtx_insn *insns, *last_insn;
3395 /* Try to reload base into register only if the base is invalid
3396 for the address but with valid offset, case (4) above. */
3397 start_sequence ();
3398 new_reg = base_to_reg (&ad);
3400 /* base + disp => new base, cases (1) and (3) above. */
3401 /* Another option would be to reload the displacement into an
3402 index register. However, postreload has code to optimize
3403 address reloads that have the same base and different
3404 displacements, so reloading into an index register would
3405 not necessarily be a win. */
3406 if (new_reg == NULL_RTX)
3407 new_reg = base_plus_disp_to_reg (&ad);
3408 insns = get_insns ();
3409 last_insn = get_last_insn ();
3410 /* If we generated at least two insns, try last insn source as
3411 an address. If we succeed, we generate one less insn. */
3412 if (last_insn != insns && (set = single_set (last_insn)) != NULL_RTX
3413 && GET_CODE (SET_SRC (set)) == PLUS
3414 && REG_P (XEXP (SET_SRC (set), 0))
3415 && CONSTANT_P (XEXP (SET_SRC (set), 1)))
3417 *ad.inner = SET_SRC (set);
3418 if (valid_address_p (ad.mode, *ad.outer, ad.as))
3420 *ad.base_term = XEXP (SET_SRC (set), 0);
3421 *ad.disp_term = XEXP (SET_SRC (set), 1);
3422 cl = base_reg_class (ad.mode, ad.as, ad.base_outer_code,
3423 get_index_code (&ad));
3424 regno = REGNO (*ad.base_term);
3425 if (regno >= FIRST_PSEUDO_REGISTER
3426 && cl != lra_get_allocno_class (regno))
3427 lra_change_class (regno, cl, " Change to", true);
3428 new_reg = SET_SRC (set);
3429 delete_insns_since (PREV_INSN (last_insn));
3432 /* Try if target can split displacement into legitimite new disp
3433 and offset. If it's the case, we replace the last insn with
3434 insns for base + offset => new_reg and set new_reg + new disp
3435 to *ad.inner. */
3436 last_insn = get_last_insn ();
3437 if ((set = single_set (last_insn)) != NULL_RTX
3438 && GET_CODE (SET_SRC (set)) == PLUS
3439 && REG_P (XEXP (SET_SRC (set), 0))
3440 && REGNO (XEXP (SET_SRC (set), 0)) < FIRST_PSEUDO_REGISTER
3441 && CONST_INT_P (XEXP (SET_SRC (set), 1)))
3443 rtx addend, disp = XEXP (SET_SRC (set), 1);
3444 if (targetm.legitimize_address_displacement (&disp, &addend,
3445 ad.mode))
3447 rtx_insn *new_insns;
3448 start_sequence ();
3449 lra_emit_add (new_reg, XEXP (SET_SRC (set), 0), addend);
3450 new_insns = get_insns ();
3451 end_sequence ();
3452 new_reg = gen_rtx_PLUS (Pmode, new_reg, disp);
3453 delete_insns_since (PREV_INSN (last_insn));
3454 add_insn (new_insns);
3455 insns = get_insns ();
3458 end_sequence ();
3459 emit_insn (insns);
3460 *ad.inner = new_reg;
3462 else if (ad.disp_term != NULL)
3464 /* base + scale * index + disp => new base + scale * index,
3465 case (1) above. */
3466 new_reg = base_plus_disp_to_reg (&ad);
3467 *ad.inner = simplify_gen_binary (PLUS, GET_MODE (new_reg),
3468 new_reg, *ad.index);
3470 else if ((scale = get_index_scale (&ad)) == 1)
3472 /* The last transformation to one reg will be made in
3473 curr_insn_transform function. */
3474 end_sequence ();
3475 return false;
3477 else if (scale != 0)
3479 /* base + scale * index => base + new_reg,
3480 case (1) above.
3481 Index part of address may become invalid. For example, we
3482 changed pseudo on the equivalent memory and a subreg of the
3483 pseudo onto the memory of different mode for which the scale is
3484 prohibitted. */
3485 new_reg = index_part_to_reg (&ad);
3486 *ad.inner = simplify_gen_binary (PLUS, GET_MODE (new_reg),
3487 *ad.base_term, new_reg);
3489 else
3491 enum reg_class cl = base_reg_class (ad.mode, ad.as,
3492 SCRATCH, SCRATCH);
3493 rtx addr = *ad.inner;
3495 new_reg = lra_create_new_reg (Pmode, NULL_RTX, cl, "addr");
3496 /* addr => new_base. */
3497 lra_emit_move (new_reg, addr);
3498 *ad.inner = new_reg;
3500 *before = get_insns ();
3501 end_sequence ();
3502 return true;
3505 /* If CHECK_ONLY_P is false, do address reloads until it is necessary.
3506 Use process_address_1 as a helper function. Return true for any
3507 RTL changes.
3509 If CHECK_ONLY_P is true, just check address correctness. Return
3510 false if the address correct. */
3511 static bool
3512 process_address (int nop, bool check_only_p,
3513 rtx_insn **before, rtx_insn **after)
3515 bool res = false;
3517 while (process_address_1 (nop, check_only_p, before, after))
3519 if (check_only_p)
3520 return true;
3521 res = true;
3523 return res;
3526 /* Emit insns to reload VALUE into a new register. VALUE is an
3527 auto-increment or auto-decrement RTX whose operand is a register or
3528 memory location; so reloading involves incrementing that location.
3529 IN is either identical to VALUE, or some cheaper place to reload
3530 value being incremented/decremented from.
3532 INC_AMOUNT is the number to increment or decrement by (always
3533 positive and ignored for POST_MODIFY/PRE_MODIFY).
3535 Return pseudo containing the result. */
3536 static rtx
3537 emit_inc (enum reg_class new_rclass, rtx in, rtx value, poly_int64 inc_amount)
3539 /* REG or MEM to be copied and incremented. */
3540 rtx incloc = XEXP (value, 0);
3541 /* Nonzero if increment after copying. */
3542 int post = (GET_CODE (value) == POST_DEC || GET_CODE (value) == POST_INC
3543 || GET_CODE (value) == POST_MODIFY);
3544 rtx_insn *last;
3545 rtx inc;
3546 rtx_insn *add_insn;
3547 int code;
3548 rtx real_in = in == value ? incloc : in;
3549 rtx result;
3550 bool plus_p = true;
3552 if (GET_CODE (value) == PRE_MODIFY || GET_CODE (value) == POST_MODIFY)
3554 lra_assert (GET_CODE (XEXP (value, 1)) == PLUS
3555 || GET_CODE (XEXP (value, 1)) == MINUS);
3556 lra_assert (rtx_equal_p (XEXP (XEXP (value, 1), 0), XEXP (value, 0)));
3557 plus_p = GET_CODE (XEXP (value, 1)) == PLUS;
3558 inc = XEXP (XEXP (value, 1), 1);
3560 else
3562 if (GET_CODE (value) == PRE_DEC || GET_CODE (value) == POST_DEC)
3563 inc_amount = -inc_amount;
3565 inc = gen_int_mode (inc_amount, GET_MODE (value));
3568 if (! post && REG_P (incloc))
3569 result = incloc;
3570 else
3571 result = lra_create_new_reg (GET_MODE (value), value, new_rclass,
3572 "INC/DEC result");
3574 if (real_in != result)
3576 /* First copy the location to the result register. */
3577 lra_assert (REG_P (result));
3578 emit_insn (gen_move_insn (result, real_in));
3581 /* We suppose that there are insns to add/sub with the constant
3582 increment permitted in {PRE/POST)_{DEC/INC/MODIFY}. At least the
3583 old reload worked with this assumption. If the assumption
3584 becomes wrong, we should use approach in function
3585 base_plus_disp_to_reg. */
3586 if (in == value)
3588 /* See if we can directly increment INCLOC. */
3589 last = get_last_insn ();
3590 add_insn = emit_insn (plus_p
3591 ? gen_add2_insn (incloc, inc)
3592 : gen_sub2_insn (incloc, inc));
3594 code = recog_memoized (add_insn);
3595 if (code >= 0)
3597 if (! post && result != incloc)
3598 emit_insn (gen_move_insn (result, incloc));
3599 return result;
3601 delete_insns_since (last);
3604 /* If couldn't do the increment directly, must increment in RESULT.
3605 The way we do this depends on whether this is pre- or
3606 post-increment. For pre-increment, copy INCLOC to the reload
3607 register, increment it there, then save back. */
3608 if (! post)
3610 if (real_in != result)
3611 emit_insn (gen_move_insn (result, real_in));
3612 if (plus_p)
3613 emit_insn (gen_add2_insn (result, inc));
3614 else
3615 emit_insn (gen_sub2_insn (result, inc));
3616 if (result != incloc)
3617 emit_insn (gen_move_insn (incloc, result));
3619 else
3621 /* Post-increment.
3623 Because this might be a jump insn or a compare, and because
3624 RESULT may not be available after the insn in an input
3625 reload, we must do the incrementing before the insn being
3626 reloaded for.
3628 We have already copied IN to RESULT. Increment the copy in
3629 RESULT, save that back, then decrement RESULT so it has
3630 the original value. */
3631 if (plus_p)
3632 emit_insn (gen_add2_insn (result, inc));
3633 else
3634 emit_insn (gen_sub2_insn (result, inc));
3635 emit_insn (gen_move_insn (incloc, result));
3636 /* Restore non-modified value for the result. We prefer this
3637 way because it does not require an additional hard
3638 register. */
3639 if (plus_p)
3641 poly_int64 offset;
3642 if (poly_int_rtx_p (inc, &offset))
3643 emit_insn (gen_add2_insn (result,
3644 gen_int_mode (-offset,
3645 GET_MODE (result))));
3646 else
3647 emit_insn (gen_sub2_insn (result, inc));
3649 else
3650 emit_insn (gen_add2_insn (result, inc));
3652 return result;
3655 /* Return true if the current move insn does not need processing as we
3656 already know that it satisfies its constraints. */
3657 static bool
3658 simple_move_p (void)
3660 rtx dest, src;
3661 enum reg_class dclass, sclass;
3663 lra_assert (curr_insn_set != NULL_RTX);
3664 dest = SET_DEST (curr_insn_set);
3665 src = SET_SRC (curr_insn_set);
3667 /* If the instruction has multiple sets we need to process it even if it
3668 is single_set. This can happen if one or more of the SETs are dead.
3669 See PR73650. */
3670 if (multiple_sets (curr_insn))
3671 return false;
3673 return ((dclass = get_op_class (dest)) != NO_REGS
3674 && (sclass = get_op_class (src)) != NO_REGS
3675 /* The backend guarantees that register moves of cost 2
3676 never need reloads. */
3677 && targetm.register_move_cost (GET_MODE (src), sclass, dclass) == 2);
3680 /* Swap operands NOP and NOP + 1. */
3681 static inline void
3682 swap_operands (int nop)
3684 std::swap (curr_operand_mode[nop], curr_operand_mode[nop + 1]);
3685 std::swap (original_subreg_reg_mode[nop], original_subreg_reg_mode[nop + 1]);
3686 std::swap (*curr_id->operand_loc[nop], *curr_id->operand_loc[nop + 1]);
3687 std::swap (equiv_substition_p[nop], equiv_substition_p[nop + 1]);
3688 /* Swap the duplicates too. */
3689 lra_update_dup (curr_id, nop);
3690 lra_update_dup (curr_id, nop + 1);
3693 /* Main entry point of the constraint code: search the body of the
3694 current insn to choose the best alternative. It is mimicking insn
3695 alternative cost calculation model of former reload pass. That is
3696 because machine descriptions were written to use this model. This
3697 model can be changed in future. Make commutative operand exchange
3698 if it is chosen.
3700 if CHECK_ONLY_P is false, do RTL changes to satisfy the
3701 constraints. Return true if any change happened during function
3702 call.
3704 If CHECK_ONLY_P is true then don't do any transformation. Just
3705 check that the insn satisfies all constraints. If the insn does
3706 not satisfy any constraint, return true. */
3707 static bool
3708 curr_insn_transform (bool check_only_p)
3710 int i, j, k;
3711 int n_operands;
3712 int n_alternatives;
3713 int n_outputs;
3714 int commutative;
3715 signed char goal_alt_matched[MAX_RECOG_OPERANDS][MAX_RECOG_OPERANDS];
3716 signed char match_inputs[MAX_RECOG_OPERANDS + 1];
3717 signed char outputs[MAX_RECOG_OPERANDS + 1];
3718 rtx_insn *before, *after;
3719 bool alt_p = false;
3720 /* Flag that the insn has been changed through a transformation. */
3721 bool change_p;
3722 bool sec_mem_p;
3723 bool use_sec_mem_p;
3724 int max_regno_before;
3725 int reused_alternative_num;
3727 curr_insn_set = single_set (curr_insn);
3728 if (curr_insn_set != NULL_RTX && simple_move_p ())
3729 return false;
3731 no_input_reloads_p = no_output_reloads_p = false;
3732 goal_alt_number = -1;
3733 change_p = sec_mem_p = false;
3734 /* JUMP_INSNs and CALL_INSNs are not allowed to have any output
3735 reloads; neither are insns that SET cc0. Insns that use CC0 are
3736 not allowed to have any input reloads. */
3737 if (JUMP_P (curr_insn) || CALL_P (curr_insn))
3738 no_output_reloads_p = true;
3740 if (HAVE_cc0 && reg_referenced_p (cc0_rtx, PATTERN (curr_insn)))
3741 no_input_reloads_p = true;
3742 if (HAVE_cc0 && reg_set_p (cc0_rtx, PATTERN (curr_insn)))
3743 no_output_reloads_p = true;
3745 n_operands = curr_static_id->n_operands;
3746 n_alternatives = curr_static_id->n_alternatives;
3748 /* Just return "no reloads" if insn has no operands with
3749 constraints. */
3750 if (n_operands == 0 || n_alternatives == 0)
3751 return false;
3753 max_regno_before = max_reg_num ();
3755 for (i = 0; i < n_operands; i++)
3757 goal_alt_matched[i][0] = -1;
3758 goal_alt_matches[i] = -1;
3761 commutative = curr_static_id->commutative;
3763 /* Now see what we need for pseudos that didn't get hard regs or got
3764 the wrong kind of hard reg. For this, we must consider all the
3765 operands together against the register constraints. */
3767 best_losers = best_overall = INT_MAX;
3768 best_reload_sum = 0;
3770 curr_swapped = false;
3771 goal_alt_swapped = false;
3773 if (! check_only_p)
3774 /* Make equivalence substitution and memory subreg elimination
3775 before address processing because an address legitimacy can
3776 depend on memory mode. */
3777 for (i = 0; i < n_operands; i++)
3779 rtx op, subst, old;
3780 bool op_change_p = false;
3782 if (curr_static_id->operand[i].is_operator)
3783 continue;
3785 old = op = *curr_id->operand_loc[i];
3786 if (GET_CODE (old) == SUBREG)
3787 old = SUBREG_REG (old);
3788 subst = get_equiv_with_elimination (old, curr_insn);
3789 original_subreg_reg_mode[i] = VOIDmode;
3790 equiv_substition_p[i] = false;
3791 if (subst != old)
3793 equiv_substition_p[i] = true;
3794 subst = copy_rtx (subst);
3795 lra_assert (REG_P (old));
3796 if (GET_CODE (op) != SUBREG)
3797 *curr_id->operand_loc[i] = subst;
3798 else
3800 SUBREG_REG (op) = subst;
3801 if (GET_MODE (subst) == VOIDmode)
3802 original_subreg_reg_mode[i] = GET_MODE (old);
3804 if (lra_dump_file != NULL)
3806 fprintf (lra_dump_file,
3807 "Changing pseudo %d in operand %i of insn %u on equiv ",
3808 REGNO (old), i, INSN_UID (curr_insn));
3809 dump_value_slim (lra_dump_file, subst, 1);
3810 fprintf (lra_dump_file, "\n");
3812 op_change_p = change_p = true;
3814 if (simplify_operand_subreg (i, GET_MODE (old)) || op_change_p)
3816 change_p = true;
3817 lra_update_dup (curr_id, i);
3821 /* Reload address registers and displacements. We do it before
3822 finding an alternative because of memory constraints. */
3823 before = after = NULL;
3824 for (i = 0; i < n_operands; i++)
3825 if (! curr_static_id->operand[i].is_operator
3826 && process_address (i, check_only_p, &before, &after))
3828 if (check_only_p)
3829 return true;
3830 change_p = true;
3831 lra_update_dup (curr_id, i);
3834 if (change_p)
3835 /* If we've changed the instruction then any alternative that
3836 we chose previously may no longer be valid. */
3837 lra_set_used_insn_alternative (curr_insn, -1);
3839 if (! check_only_p && curr_insn_set != NULL_RTX
3840 && check_and_process_move (&change_p, &sec_mem_p))
3841 return change_p;
3843 try_swapped:
3845 reused_alternative_num = check_only_p ? -1 : curr_id->used_insn_alternative;
3846 if (lra_dump_file != NULL && reused_alternative_num >= 0)
3847 fprintf (lra_dump_file, "Reusing alternative %d for insn #%u\n",
3848 reused_alternative_num, INSN_UID (curr_insn));
3850 if (process_alt_operands (reused_alternative_num))
3851 alt_p = true;
3853 if (check_only_p)
3854 return ! alt_p || best_losers != 0;
3856 /* If insn is commutative (it's safe to exchange a certain pair of
3857 operands) then we need to try each alternative twice, the second
3858 time matching those two operands as if we had exchanged them. To
3859 do this, really exchange them in operands.
3861 If we have just tried the alternatives the second time, return
3862 operands to normal and drop through. */
3864 if (reused_alternative_num < 0 && commutative >= 0)
3866 curr_swapped = !curr_swapped;
3867 if (curr_swapped)
3869 swap_operands (commutative);
3870 goto try_swapped;
3872 else
3873 swap_operands (commutative);
3876 if (! alt_p && ! sec_mem_p)
3878 /* No alternative works with reloads?? */
3879 if (INSN_CODE (curr_insn) >= 0)
3880 fatal_insn ("unable to generate reloads for:", curr_insn);
3881 error_for_asm (curr_insn,
3882 "inconsistent operand constraints in an %<asm%>");
3883 /* Avoid further trouble with this insn. Don't generate use
3884 pattern here as we could use the insn SP offset. */
3885 lra_set_insn_deleted (curr_insn);
3886 return true;
3889 /* If the best alternative is with operands 1 and 2 swapped, swap
3890 them. Update the operand numbers of any reloads already
3891 pushed. */
3893 if (goal_alt_swapped)
3895 if (lra_dump_file != NULL)
3896 fprintf (lra_dump_file, " Commutative operand exchange in insn %u\n",
3897 INSN_UID (curr_insn));
3899 /* Swap the duplicates too. */
3900 swap_operands (commutative);
3901 change_p = true;
3904 /* Some targets' TARGET_SECONDARY_MEMORY_NEEDED (e.g. x86) are defined
3905 too conservatively. So we use the secondary memory only if there
3906 is no any alternative without reloads. */
3907 use_sec_mem_p = false;
3908 if (! alt_p)
3909 use_sec_mem_p = true;
3910 else if (sec_mem_p)
3912 for (i = 0; i < n_operands; i++)
3913 if (! goal_alt_win[i] && ! goal_alt_match_win[i])
3914 break;
3915 use_sec_mem_p = i < n_operands;
3918 if (use_sec_mem_p)
3920 int in = -1, out = -1;
3921 rtx new_reg, src, dest, rld;
3922 machine_mode sec_mode, rld_mode;
3924 lra_assert (curr_insn_set != NULL_RTX && sec_mem_p);
3925 dest = SET_DEST (curr_insn_set);
3926 src = SET_SRC (curr_insn_set);
3927 for (i = 0; i < n_operands; i++)
3928 if (*curr_id->operand_loc[i] == dest)
3929 out = i;
3930 else if (*curr_id->operand_loc[i] == src)
3931 in = i;
3932 for (i = 0; i < curr_static_id->n_dups; i++)
3933 if (out < 0 && *curr_id->dup_loc[i] == dest)
3934 out = curr_static_id->dup_num[i];
3935 else if (in < 0 && *curr_id->dup_loc[i] == src)
3936 in = curr_static_id->dup_num[i];
3937 lra_assert (out >= 0 && in >= 0
3938 && curr_static_id->operand[out].type == OP_OUT
3939 && curr_static_id->operand[in].type == OP_IN);
3940 rld = partial_subreg_p (GET_MODE (src), GET_MODE (dest)) ? src : dest;
3941 rld_mode = GET_MODE (rld);
3942 sec_mode = targetm.secondary_memory_needed_mode (rld_mode);
3943 new_reg = lra_create_new_reg (sec_mode, NULL_RTX,
3944 NO_REGS, "secondary");
3945 /* If the mode is changed, it should be wider. */
3946 lra_assert (!partial_subreg_p (sec_mode, rld_mode));
3947 if (sec_mode != rld_mode)
3949 /* If the target says specifically to use another mode for
3950 secondary memory moves we can not reuse the original
3951 insn. */
3952 after = emit_spill_move (false, new_reg, dest);
3953 lra_process_new_insns (curr_insn, NULL, after,
3954 "Inserting the sec. move");
3955 /* We may have non null BEFORE here (e.g. after address
3956 processing. */
3957 push_to_sequence (before);
3958 before = emit_spill_move (true, new_reg, src);
3959 emit_insn (before);
3960 before = get_insns ();
3961 end_sequence ();
3962 lra_process_new_insns (curr_insn, before, NULL, "Changing on");
3963 lra_set_insn_deleted (curr_insn);
3965 else if (dest == rld)
3967 *curr_id->operand_loc[out] = new_reg;
3968 lra_update_dup (curr_id, out);
3969 after = emit_spill_move (false, new_reg, dest);
3970 lra_process_new_insns (curr_insn, NULL, after,
3971 "Inserting the sec. move");
3973 else
3975 *curr_id->operand_loc[in] = new_reg;
3976 lra_update_dup (curr_id, in);
3977 /* See comments above. */
3978 push_to_sequence (before);
3979 before = emit_spill_move (true, new_reg, src);
3980 emit_insn (before);
3981 before = get_insns ();
3982 end_sequence ();
3983 lra_process_new_insns (curr_insn, before, NULL,
3984 "Inserting the sec. move");
3986 lra_update_insn_regno_info (curr_insn);
3987 return true;
3990 lra_assert (goal_alt_number >= 0);
3991 lra_set_used_insn_alternative (curr_insn, goal_alt_number);
3993 if (lra_dump_file != NULL)
3995 const char *p;
3997 fprintf (lra_dump_file, " Choosing alt %d in insn %u:",
3998 goal_alt_number, INSN_UID (curr_insn));
3999 for (i = 0; i < n_operands; i++)
4001 p = (curr_static_id->operand_alternative
4002 [goal_alt_number * n_operands + i].constraint);
4003 if (*p == '\0')
4004 continue;
4005 fprintf (lra_dump_file, " (%d) ", i);
4006 for (; *p != '\0' && *p != ',' && *p != '#'; p++)
4007 fputc (*p, lra_dump_file);
4009 if (INSN_CODE (curr_insn) >= 0
4010 && (p = get_insn_name (INSN_CODE (curr_insn))) != NULL)
4011 fprintf (lra_dump_file, " {%s}", p);
4012 if (maybe_ne (curr_id->sp_offset, 0))
4014 fprintf (lra_dump_file, " (sp_off=");
4015 print_dec (curr_id->sp_offset, lra_dump_file);
4016 fprintf (lra_dump_file, ")");
4018 fprintf (lra_dump_file, "\n");
4021 /* Right now, for any pair of operands I and J that are required to
4022 match, with J < I, goal_alt_matches[I] is J. Add I to
4023 goal_alt_matched[J]. */
4025 for (i = 0; i < n_operands; i++)
4026 if ((j = goal_alt_matches[i]) >= 0)
4028 for (k = 0; goal_alt_matched[j][k] >= 0; k++)
4030 /* We allow matching one output operand and several input
4031 operands. */
4032 lra_assert (k == 0
4033 || (curr_static_id->operand[j].type == OP_OUT
4034 && curr_static_id->operand[i].type == OP_IN
4035 && (curr_static_id->operand
4036 [goal_alt_matched[j][0]].type == OP_IN)));
4037 goal_alt_matched[j][k] = i;
4038 goal_alt_matched[j][k + 1] = -1;
4041 for (i = 0; i < n_operands; i++)
4042 goal_alt_win[i] |= goal_alt_match_win[i];
4044 /* Any constants that aren't allowed and can't be reloaded into
4045 registers are here changed into memory references. */
4046 for (i = 0; i < n_operands; i++)
4047 if (goal_alt_win[i])
4049 int regno;
4050 enum reg_class new_class;
4051 rtx reg = *curr_id->operand_loc[i];
4053 if (GET_CODE (reg) == SUBREG)
4054 reg = SUBREG_REG (reg);
4056 if (REG_P (reg) && (regno = REGNO (reg)) >= FIRST_PSEUDO_REGISTER)
4058 bool ok_p = in_class_p (reg, goal_alt[i], &new_class);
4060 if (new_class != NO_REGS && get_reg_class (regno) != new_class)
4062 lra_assert (ok_p);
4063 lra_change_class (regno, new_class, " Change to", true);
4067 else
4069 const char *constraint;
4070 char c;
4071 rtx op = *curr_id->operand_loc[i];
4072 rtx subreg = NULL_RTX;
4073 machine_mode mode = curr_operand_mode[i];
4075 if (GET_CODE (op) == SUBREG)
4077 subreg = op;
4078 op = SUBREG_REG (op);
4079 mode = GET_MODE (op);
4082 if (CONST_POOL_OK_P (mode, op)
4083 && ((targetm.preferred_reload_class
4084 (op, (enum reg_class) goal_alt[i]) == NO_REGS)
4085 || no_input_reloads_p))
4087 rtx tem = force_const_mem (mode, op);
4089 change_p = true;
4090 if (subreg != NULL_RTX)
4091 tem = gen_rtx_SUBREG (mode, tem, SUBREG_BYTE (subreg));
4093 *curr_id->operand_loc[i] = tem;
4094 lra_update_dup (curr_id, i);
4095 process_address (i, false, &before, &after);
4097 /* If the alternative accepts constant pool refs directly
4098 there will be no reload needed at all. */
4099 if (subreg != NULL_RTX)
4100 continue;
4101 /* Skip alternatives before the one requested. */
4102 constraint = (curr_static_id->operand_alternative
4103 [goal_alt_number * n_operands + i].constraint);
4104 for (;
4105 (c = *constraint) && c != ',' && c != '#';
4106 constraint += CONSTRAINT_LEN (c, constraint))
4108 enum constraint_num cn = lookup_constraint (constraint);
4109 if ((insn_extra_memory_constraint (cn)
4110 || insn_extra_special_memory_constraint (cn))
4111 && satisfies_memory_constraint_p (tem, cn))
4112 break;
4114 if (c == '\0' || c == ',' || c == '#')
4115 continue;
4117 goal_alt_win[i] = true;
4121 n_outputs = 0;
4122 outputs[0] = -1;
4123 for (i = 0; i < n_operands; i++)
4125 int regno;
4126 bool optional_p = false;
4127 rtx old, new_reg;
4128 rtx op = *curr_id->operand_loc[i];
4130 if (goal_alt_win[i])
4132 if (goal_alt[i] == NO_REGS
4133 && REG_P (op)
4134 /* When we assign NO_REGS it means that we will not
4135 assign a hard register to the scratch pseudo by
4136 assigment pass and the scratch pseudo will be
4137 spilled. Spilled scratch pseudos are transformed
4138 back to scratches at the LRA end. */
4139 && lra_former_scratch_operand_p (curr_insn, i)
4140 && lra_former_scratch_p (REGNO (op)))
4142 int regno = REGNO (op);
4143 lra_change_class (regno, NO_REGS, " Change to", true);
4144 if (lra_get_regno_hard_regno (regno) >= 0)
4145 /* We don't have to mark all insn affected by the
4146 spilled pseudo as there is only one such insn, the
4147 current one. */
4148 reg_renumber[regno] = -1;
4149 lra_assert (bitmap_single_bit_set_p
4150 (&lra_reg_info[REGNO (op)].insn_bitmap));
4152 /* We can do an optional reload. If the pseudo got a hard
4153 reg, we might improve the code through inheritance. If
4154 it does not get a hard register we coalesce memory/memory
4155 moves later. Ignore move insns to avoid cycling. */
4156 if (! lra_simple_p
4157 && lra_undo_inheritance_iter < LRA_MAX_INHERITANCE_PASSES
4158 && goal_alt[i] != NO_REGS && REG_P (op)
4159 && (regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER
4160 && regno < new_regno_start
4161 && ! lra_former_scratch_p (regno)
4162 && reg_renumber[regno] < 0
4163 /* Check that the optional reload pseudo will be able to
4164 hold given mode value. */
4165 && ! (prohibited_class_reg_set_mode_p
4166 (goal_alt[i], reg_class_contents[goal_alt[i]],
4167 PSEUDO_REGNO_MODE (regno)))
4168 && (curr_insn_set == NULL_RTX
4169 || !((REG_P (SET_SRC (curr_insn_set))
4170 || MEM_P (SET_SRC (curr_insn_set))
4171 || GET_CODE (SET_SRC (curr_insn_set)) == SUBREG)
4172 && (REG_P (SET_DEST (curr_insn_set))
4173 || MEM_P (SET_DEST (curr_insn_set))
4174 || GET_CODE (SET_DEST (curr_insn_set)) == SUBREG))))
4175 optional_p = true;
4176 else
4177 continue;
4180 /* Operands that match previous ones have already been handled. */
4181 if (goal_alt_matches[i] >= 0)
4182 continue;
4184 /* We should not have an operand with a non-offsettable address
4185 appearing where an offsettable address will do. It also may
4186 be a case when the address should be special in other words
4187 not a general one (e.g. it needs no index reg). */
4188 if (goal_alt_matched[i][0] == -1 && goal_alt_offmemok[i] && MEM_P (op))
4190 enum reg_class rclass;
4191 rtx *loc = &XEXP (op, 0);
4192 enum rtx_code code = GET_CODE (*loc);
4194 push_to_sequence (before);
4195 rclass = base_reg_class (GET_MODE (op), MEM_ADDR_SPACE (op),
4196 MEM, SCRATCH);
4197 if (GET_RTX_CLASS (code) == RTX_AUTOINC)
4198 new_reg = emit_inc (rclass, *loc, *loc,
4199 /* This value does not matter for MODIFY. */
4200 GET_MODE_SIZE (GET_MODE (op)));
4201 else if (get_reload_reg (OP_IN, Pmode, *loc, rclass, FALSE,
4202 "offsetable address", &new_reg))
4203 lra_emit_move (new_reg, *loc);
4204 before = get_insns ();
4205 end_sequence ();
4206 *loc = new_reg;
4207 lra_update_dup (curr_id, i);
4209 else if (goal_alt_matched[i][0] == -1)
4211 machine_mode mode;
4212 rtx reg, *loc;
4213 int hard_regno;
4214 enum op_type type = curr_static_id->operand[i].type;
4216 loc = curr_id->operand_loc[i];
4217 mode = curr_operand_mode[i];
4218 if (GET_CODE (*loc) == SUBREG)
4220 reg = SUBREG_REG (*loc);
4221 poly_int64 byte = SUBREG_BYTE (*loc);
4222 if (REG_P (reg)
4223 /* Strict_low_part requires reloading the register and not
4224 just the subreg. Likewise for a strict subreg no wider
4225 than a word for WORD_REGISTER_OPERATIONS targets. */
4226 && (curr_static_id->operand[i].strict_low
4227 || (!paradoxical_subreg_p (mode, GET_MODE (reg))
4228 && (hard_regno
4229 = get_try_hard_regno (REGNO (reg))) >= 0
4230 && (simplify_subreg_regno
4231 (hard_regno,
4232 GET_MODE (reg), byte, mode) < 0)
4233 && (goal_alt[i] == NO_REGS
4234 || (simplify_subreg_regno
4235 (ira_class_hard_regs[goal_alt[i]][0],
4236 GET_MODE (reg), byte, mode) >= 0)))
4237 || (GET_MODE_PRECISION (mode)
4238 < GET_MODE_PRECISION (GET_MODE (reg))
4239 && GET_MODE_SIZE (GET_MODE (reg)) <= UNITS_PER_WORD
4240 && WORD_REGISTER_OPERATIONS)))
4242 /* An OP_INOUT is required when reloading a subreg of a
4243 mode wider than a word to ensure that data beyond the
4244 word being reloaded is preserved. Also automatically
4245 ensure that strict_low_part reloads are made into
4246 OP_INOUT which should already be true from the backend
4247 constraints. */
4248 if (type == OP_OUT
4249 && (curr_static_id->operand[i].strict_low
4250 || read_modify_subreg_p (*loc)))
4251 type = OP_INOUT;
4252 loc = &SUBREG_REG (*loc);
4253 mode = GET_MODE (*loc);
4256 old = *loc;
4257 if (get_reload_reg (type, mode, old, goal_alt[i],
4258 loc != curr_id->operand_loc[i], "", &new_reg)
4259 && type != OP_OUT)
4261 push_to_sequence (before);
4262 lra_emit_move (new_reg, old);
4263 before = get_insns ();
4264 end_sequence ();
4266 *loc = new_reg;
4267 if (type != OP_IN
4268 && find_reg_note (curr_insn, REG_UNUSED, old) == NULL_RTX)
4270 start_sequence ();
4271 lra_emit_move (type == OP_INOUT ? copy_rtx (old) : old, new_reg);
4272 emit_insn (after);
4273 after = get_insns ();
4274 end_sequence ();
4275 *loc = new_reg;
4277 for (j = 0; j < goal_alt_dont_inherit_ops_num; j++)
4278 if (goal_alt_dont_inherit_ops[j] == i)
4280 lra_set_regno_unique_value (REGNO (new_reg));
4281 break;
4283 lra_update_dup (curr_id, i);
4285 else if (curr_static_id->operand[i].type == OP_IN
4286 && (curr_static_id->operand[goal_alt_matched[i][0]].type
4287 == OP_OUT
4288 || (curr_static_id->operand[goal_alt_matched[i][0]].type
4289 == OP_INOUT
4290 && (operands_match_p
4291 (*curr_id->operand_loc[i],
4292 *curr_id->operand_loc[goal_alt_matched[i][0]],
4293 -1)))))
4295 /* generate reloads for input and matched outputs. */
4296 match_inputs[0] = i;
4297 match_inputs[1] = -1;
4298 match_reload (goal_alt_matched[i][0], match_inputs, outputs,
4299 goal_alt[i], &before, &after,
4300 curr_static_id->operand_alternative
4301 [goal_alt_number * n_operands + goal_alt_matched[i][0]]
4302 .earlyclobber);
4304 else if ((curr_static_id->operand[i].type == OP_OUT
4305 || (curr_static_id->operand[i].type == OP_INOUT
4306 && (operands_match_p
4307 (*curr_id->operand_loc[i],
4308 *curr_id->operand_loc[goal_alt_matched[i][0]],
4309 -1))))
4310 && (curr_static_id->operand[goal_alt_matched[i][0]].type
4311 == OP_IN))
4312 /* Generate reloads for output and matched inputs. */
4313 match_reload (i, goal_alt_matched[i], outputs, goal_alt[i], &before,
4314 &after, curr_static_id->operand_alternative
4315 [goal_alt_number * n_operands + i].earlyclobber);
4316 else if (curr_static_id->operand[i].type == OP_IN
4317 && (curr_static_id->operand[goal_alt_matched[i][0]].type
4318 == OP_IN))
4320 /* Generate reloads for matched inputs. */
4321 match_inputs[0] = i;
4322 for (j = 0; (k = goal_alt_matched[i][j]) >= 0; j++)
4323 match_inputs[j + 1] = k;
4324 match_inputs[j + 1] = -1;
4325 match_reload (-1, match_inputs, outputs, goal_alt[i], &before,
4326 &after, false);
4328 else
4329 /* We must generate code in any case when function
4330 process_alt_operands decides that it is possible. */
4331 gcc_unreachable ();
4333 /* Memorise processed outputs so that output remaining to be processed
4334 can avoid using the same register value (see match_reload). */
4335 if (curr_static_id->operand[i].type == OP_OUT)
4337 outputs[n_outputs++] = i;
4338 outputs[n_outputs] = -1;
4341 if (optional_p)
4343 rtx reg = op;
4345 lra_assert (REG_P (reg));
4346 regno = REGNO (reg);
4347 op = *curr_id->operand_loc[i]; /* Substitution. */
4348 if (GET_CODE (op) == SUBREG)
4349 op = SUBREG_REG (op);
4350 gcc_assert (REG_P (op) && (int) REGNO (op) >= new_regno_start);
4351 bitmap_set_bit (&lra_optional_reload_pseudos, REGNO (op));
4352 lra_reg_info[REGNO (op)].restore_rtx = reg;
4353 if (lra_dump_file != NULL)
4354 fprintf (lra_dump_file,
4355 " Making reload reg %d for reg %d optional\n",
4356 REGNO (op), regno);
4359 if (before != NULL_RTX || after != NULL_RTX
4360 || max_regno_before != max_reg_num ())
4361 change_p = true;
4362 if (change_p)
4364 lra_update_operator_dups (curr_id);
4365 /* Something changes -- process the insn. */
4366 lra_update_insn_regno_info (curr_insn);
4368 lra_process_new_insns (curr_insn, before, after, "Inserting insn reload");
4369 return change_p;
4372 /* Return true if INSN satisfies all constraints. In other words, no
4373 reload insns are needed. */
4374 bool
4375 lra_constrain_insn (rtx_insn *insn)
4377 int saved_new_regno_start = new_regno_start;
4378 int saved_new_insn_uid_start = new_insn_uid_start;
4379 bool change_p;
4381 curr_insn = insn;
4382 curr_id = lra_get_insn_recog_data (curr_insn);
4383 curr_static_id = curr_id->insn_static_data;
4384 new_insn_uid_start = get_max_uid ();
4385 new_regno_start = max_reg_num ();
4386 change_p = curr_insn_transform (true);
4387 new_regno_start = saved_new_regno_start;
4388 new_insn_uid_start = saved_new_insn_uid_start;
4389 return ! change_p;
4392 /* Return true if X is in LIST. */
4393 static bool
4394 in_list_p (rtx x, rtx list)
4396 for (; list != NULL_RTX; list = XEXP (list, 1))
4397 if (XEXP (list, 0) == x)
4398 return true;
4399 return false;
4402 /* Return true if X contains an allocatable hard register (if
4403 HARD_REG_P) or a (spilled if SPILLED_P) pseudo. */
4404 static bool
4405 contains_reg_p (rtx x, bool hard_reg_p, bool spilled_p)
4407 int i, j;
4408 const char *fmt;
4409 enum rtx_code code;
4411 code = GET_CODE (x);
4412 if (REG_P (x))
4414 int regno = REGNO (x);
4415 HARD_REG_SET alloc_regs;
4417 if (hard_reg_p)
4419 if (regno >= FIRST_PSEUDO_REGISTER)
4420 regno = lra_get_regno_hard_regno (regno);
4421 if (regno < 0)
4422 return false;
4423 COMPL_HARD_REG_SET (alloc_regs, lra_no_alloc_regs);
4424 return overlaps_hard_reg_set_p (alloc_regs, GET_MODE (x), regno);
4426 else
4428 if (regno < FIRST_PSEUDO_REGISTER)
4429 return false;
4430 if (! spilled_p)
4431 return true;
4432 return lra_get_regno_hard_regno (regno) < 0;
4435 fmt = GET_RTX_FORMAT (code);
4436 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4438 if (fmt[i] == 'e')
4440 if (contains_reg_p (XEXP (x, i), hard_reg_p, spilled_p))
4441 return true;
4443 else if (fmt[i] == 'E')
4445 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4446 if (contains_reg_p (XVECEXP (x, i, j), hard_reg_p, spilled_p))
4447 return true;
4450 return false;
4453 /* Process all regs in location *LOC and change them on equivalent
4454 substitution. Return true if any change was done. */
4455 static bool
4456 loc_equivalence_change_p (rtx *loc)
4458 rtx subst, reg, x = *loc;
4459 bool result = false;
4460 enum rtx_code code = GET_CODE (x);
4461 const char *fmt;
4462 int i, j;
4464 if (code == SUBREG)
4466 reg = SUBREG_REG (x);
4467 if ((subst = get_equiv_with_elimination (reg, curr_insn)) != reg
4468 && GET_MODE (subst) == VOIDmode)
4470 /* We cannot reload debug location. Simplify subreg here
4471 while we know the inner mode. */
4472 *loc = simplify_gen_subreg (GET_MODE (x), subst,
4473 GET_MODE (reg), SUBREG_BYTE (x));
4474 return true;
4477 if (code == REG && (subst = get_equiv_with_elimination (x, curr_insn)) != x)
4479 *loc = subst;
4480 return true;
4483 /* Scan all the operand sub-expressions. */
4484 fmt = GET_RTX_FORMAT (code);
4485 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4487 if (fmt[i] == 'e')
4488 result = loc_equivalence_change_p (&XEXP (x, i)) || result;
4489 else if (fmt[i] == 'E')
4490 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4491 result
4492 = loc_equivalence_change_p (&XVECEXP (x, i, j)) || result;
4494 return result;
4497 /* Similar to loc_equivalence_change_p, but for use as
4498 simplify_replace_fn_rtx callback. DATA is insn for which the
4499 elimination is done. If it null we don't do the elimination. */
4500 static rtx
4501 loc_equivalence_callback (rtx loc, const_rtx, void *data)
4503 if (!REG_P (loc))
4504 return NULL_RTX;
4506 rtx subst = (data == NULL
4507 ? get_equiv (loc) : get_equiv_with_elimination (loc, (rtx_insn *) data));
4508 if (subst != loc)
4509 return subst;
4511 return NULL_RTX;
4514 /* Maximum number of generated reload insns per an insn. It is for
4515 preventing this pass cycling in a bug case. */
4516 #define MAX_RELOAD_INSNS_NUMBER LRA_MAX_INSN_RELOADS
4518 /* The current iteration number of this LRA pass. */
4519 int lra_constraint_iter;
4521 /* True if we substituted equiv which needs checking register
4522 allocation correctness because the equivalent value contains
4523 allocatable hard registers or when we restore multi-register
4524 pseudo. */
4525 bool lra_risky_transformations_p;
4527 /* Return true if REGNO is referenced in more than one block. */
4528 static bool
4529 multi_block_pseudo_p (int regno)
4531 basic_block bb = NULL;
4532 unsigned int uid;
4533 bitmap_iterator bi;
4535 if (regno < FIRST_PSEUDO_REGISTER)
4536 return false;
4538 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
4539 if (bb == NULL)
4540 bb = BLOCK_FOR_INSN (lra_insn_recog_data[uid]->insn);
4541 else if (BLOCK_FOR_INSN (lra_insn_recog_data[uid]->insn) != bb)
4542 return true;
4543 return false;
4546 /* Return true if LIST contains a deleted insn. */
4547 static bool
4548 contains_deleted_insn_p (rtx_insn_list *list)
4550 for (; list != NULL_RTX; list = list->next ())
4551 if (NOTE_P (list->insn ())
4552 && NOTE_KIND (list->insn ()) == NOTE_INSN_DELETED)
4553 return true;
4554 return false;
4557 /* Return true if X contains a pseudo dying in INSN. */
4558 static bool
4559 dead_pseudo_p (rtx x, rtx_insn *insn)
4561 int i, j;
4562 const char *fmt;
4563 enum rtx_code code;
4565 if (REG_P (x))
4566 return (insn != NULL_RTX
4567 && find_regno_note (insn, REG_DEAD, REGNO (x)) != NULL_RTX);
4568 code = GET_CODE (x);
4569 fmt = GET_RTX_FORMAT (code);
4570 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4572 if (fmt[i] == 'e')
4574 if (dead_pseudo_p (XEXP (x, i), insn))
4575 return true;
4577 else if (fmt[i] == 'E')
4579 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4580 if (dead_pseudo_p (XVECEXP (x, i, j), insn))
4581 return true;
4584 return false;
4587 /* Return true if INSN contains a dying pseudo in INSN right hand
4588 side. */
4589 static bool
4590 insn_rhs_dead_pseudo_p (rtx_insn *insn)
4592 rtx set = single_set (insn);
4594 gcc_assert (set != NULL);
4595 return dead_pseudo_p (SET_SRC (set), insn);
4598 /* Return true if any init insn of REGNO contains a dying pseudo in
4599 insn right hand side. */
4600 static bool
4601 init_insn_rhs_dead_pseudo_p (int regno)
4603 rtx_insn_list *insns = ira_reg_equiv[regno].init_insns;
4605 if (insns == NULL)
4606 return false;
4607 for (; insns != NULL_RTX; insns = insns->next ())
4608 if (insn_rhs_dead_pseudo_p (insns->insn ()))
4609 return true;
4610 return false;
4613 /* Return TRUE if REGNO has a reverse equivalence. The equivalence is
4614 reverse only if we have one init insn with given REGNO as a
4615 source. */
4616 static bool
4617 reverse_equiv_p (int regno)
4619 rtx_insn_list *insns = ira_reg_equiv[regno].init_insns;
4620 rtx set;
4622 if (insns == NULL)
4623 return false;
4624 if (! INSN_P (insns->insn ())
4625 || insns->next () != NULL)
4626 return false;
4627 if ((set = single_set (insns->insn ())) == NULL_RTX)
4628 return false;
4629 return REG_P (SET_SRC (set)) && (int) REGNO (SET_SRC (set)) == regno;
4632 /* Return TRUE if REGNO was reloaded in an equivalence init insn. We
4633 call this function only for non-reverse equivalence. */
4634 static bool
4635 contains_reloaded_insn_p (int regno)
4637 rtx set;
4638 rtx_insn_list *list = ira_reg_equiv[regno].init_insns;
4640 for (; list != NULL; list = list->next ())
4641 if ((set = single_set (list->insn ())) == NULL_RTX
4642 || ! REG_P (SET_DEST (set))
4643 || (int) REGNO (SET_DEST (set)) != regno)
4644 return true;
4645 return false;
4648 /* Entry function of LRA constraint pass. Return true if the
4649 constraint pass did change the code. */
4650 bool
4651 lra_constraints (bool first_p)
4653 bool changed_p;
4654 int i, hard_regno, new_insns_num;
4655 unsigned int min_len, new_min_len, uid;
4656 rtx set, x, reg, dest_reg;
4657 basic_block last_bb;
4658 bitmap_iterator bi;
4660 lra_constraint_iter++;
4661 if (lra_dump_file != NULL)
4662 fprintf (lra_dump_file, "\n********** Local #%d: **********\n\n",
4663 lra_constraint_iter);
4664 changed_p = false;
4665 if (pic_offset_table_rtx
4666 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
4667 lra_risky_transformations_p = true;
4668 else
4669 /* On the first iteration we should check IRA assignment
4670 correctness. In rare cases, the assignments can be wrong as
4671 early clobbers operands are ignored in IRA. */
4672 lra_risky_transformations_p = first_p;
4673 new_insn_uid_start = get_max_uid ();
4674 new_regno_start = first_p ? lra_constraint_new_regno_start : max_reg_num ();
4675 /* Mark used hard regs for target stack size calulations. */
4676 for (i = FIRST_PSEUDO_REGISTER; i < new_regno_start; i++)
4677 if (lra_reg_info[i].nrefs != 0
4678 && (hard_regno = lra_get_regno_hard_regno (i)) >= 0)
4680 int j, nregs;
4682 nregs = hard_regno_nregs (hard_regno, lra_reg_info[i].biggest_mode);
4683 for (j = 0; j < nregs; j++)
4684 df_set_regs_ever_live (hard_regno + j, true);
4686 /* Do elimination before the equivalence processing as we can spill
4687 some pseudos during elimination. */
4688 lra_eliminate (false, first_p);
4689 auto_bitmap equiv_insn_bitmap (&reg_obstack);
4690 for (i = FIRST_PSEUDO_REGISTER; i < new_regno_start; i++)
4691 if (lra_reg_info[i].nrefs != 0)
4693 ira_reg_equiv[i].profitable_p = true;
4694 reg = regno_reg_rtx[i];
4695 if (lra_get_regno_hard_regno (i) < 0 && (x = get_equiv (reg)) != reg)
4697 bool pseudo_p = contains_reg_p (x, false, false);
4699 /* After RTL transformation, we can not guarantee that
4700 pseudo in the substitution was not reloaded which might
4701 make equivalence invalid. For example, in reverse
4702 equiv of p0
4704 p0 <- ...
4706 equiv_mem <- p0
4708 the memory address register was reloaded before the 2nd
4709 insn. */
4710 if ((! first_p && pseudo_p)
4711 /* We don't use DF for compilation speed sake. So it
4712 is problematic to update live info when we use an
4713 equivalence containing pseudos in more than one
4714 BB. */
4715 || (pseudo_p && multi_block_pseudo_p (i))
4716 /* If an init insn was deleted for some reason, cancel
4717 the equiv. We could update the equiv insns after
4718 transformations including an equiv insn deletion
4719 but it is not worthy as such cases are extremely
4720 rare. */
4721 || contains_deleted_insn_p (ira_reg_equiv[i].init_insns)
4722 /* If it is not a reverse equivalence, we check that a
4723 pseudo in rhs of the init insn is not dying in the
4724 insn. Otherwise, the live info at the beginning of
4725 the corresponding BB might be wrong after we
4726 removed the insn. When the equiv can be a
4727 constant, the right hand side of the init insn can
4728 be a pseudo. */
4729 || (! reverse_equiv_p (i)
4730 && (init_insn_rhs_dead_pseudo_p (i)
4731 /* If we reloaded the pseudo in an equivalence
4732 init insn, we can not remove the equiv init
4733 insns and the init insns might write into
4734 const memory in this case. */
4735 || contains_reloaded_insn_p (i)))
4736 /* Prevent access beyond equivalent memory for
4737 paradoxical subregs. */
4738 || (MEM_P (x)
4739 && (GET_MODE_SIZE (lra_reg_info[i].biggest_mode)
4740 > GET_MODE_SIZE (GET_MODE (x))))
4741 || (pic_offset_table_rtx
4742 && ((CONST_POOL_OK_P (PSEUDO_REGNO_MODE (i), x)
4743 && (targetm.preferred_reload_class
4744 (x, lra_get_allocno_class (i)) == NO_REGS))
4745 || contains_symbol_ref_p (x))))
4746 ira_reg_equiv[i].defined_p = false;
4747 if (contains_reg_p (x, false, true))
4748 ira_reg_equiv[i].profitable_p = false;
4749 if (get_equiv (reg) != reg)
4750 bitmap_ior_into (equiv_insn_bitmap, &lra_reg_info[i].insn_bitmap);
4753 for (i = FIRST_PSEUDO_REGISTER; i < new_regno_start; i++)
4754 update_equiv (i);
4755 /* We should add all insns containing pseudos which should be
4756 substituted by their equivalences. */
4757 EXECUTE_IF_SET_IN_BITMAP (equiv_insn_bitmap, 0, uid, bi)
4758 lra_push_insn_by_uid (uid);
4759 min_len = lra_insn_stack_length ();
4760 new_insns_num = 0;
4761 last_bb = NULL;
4762 changed_p = false;
4763 while ((new_min_len = lra_insn_stack_length ()) != 0)
4765 curr_insn = lra_pop_insn ();
4766 --new_min_len;
4767 curr_bb = BLOCK_FOR_INSN (curr_insn);
4768 if (curr_bb != last_bb)
4770 last_bb = curr_bb;
4771 bb_reload_num = lra_curr_reload_num;
4773 if (min_len > new_min_len)
4775 min_len = new_min_len;
4776 new_insns_num = 0;
4778 if (new_insns_num > MAX_RELOAD_INSNS_NUMBER)
4779 internal_error
4780 ("Max. number of generated reload insns per insn is achieved (%d)\n",
4781 MAX_RELOAD_INSNS_NUMBER);
4782 new_insns_num++;
4783 if (DEBUG_INSN_P (curr_insn))
4785 /* We need to check equivalence in debug insn and change
4786 pseudo to the equivalent value if necessary. */
4787 curr_id = lra_get_insn_recog_data (curr_insn);
4788 if (bitmap_bit_p (equiv_insn_bitmap, INSN_UID (curr_insn)))
4790 rtx old = *curr_id->operand_loc[0];
4791 *curr_id->operand_loc[0]
4792 = simplify_replace_fn_rtx (old, NULL_RTX,
4793 loc_equivalence_callback, curr_insn);
4794 if (old != *curr_id->operand_loc[0])
4796 lra_update_insn_regno_info (curr_insn);
4797 changed_p = true;
4801 else if (INSN_P (curr_insn))
4803 if ((set = single_set (curr_insn)) != NULL_RTX)
4805 dest_reg = SET_DEST (set);
4806 /* The equivalence pseudo could be set up as SUBREG in a
4807 case when it is a call restore insn in a mode
4808 different from the pseudo mode. */
4809 if (GET_CODE (dest_reg) == SUBREG)
4810 dest_reg = SUBREG_REG (dest_reg);
4811 if ((REG_P (dest_reg)
4812 && (x = get_equiv (dest_reg)) != dest_reg
4813 /* Remove insns which set up a pseudo whose value
4814 can not be changed. Such insns might be not in
4815 init_insns because we don't update equiv data
4816 during insn transformations.
4818 As an example, let suppose that a pseudo got
4819 hard register and on the 1st pass was not
4820 changed to equivalent constant. We generate an
4821 additional insn setting up the pseudo because of
4822 secondary memory movement. Then the pseudo is
4823 spilled and we use the equiv constant. In this
4824 case we should remove the additional insn and
4825 this insn is not init_insns list. */
4826 && (! MEM_P (x) || MEM_READONLY_P (x)
4827 /* Check that this is actually an insn setting
4828 up the equivalence. */
4829 || in_list_p (curr_insn,
4830 ira_reg_equiv
4831 [REGNO (dest_reg)].init_insns)))
4832 || (((x = get_equiv (SET_SRC (set))) != SET_SRC (set))
4833 && in_list_p (curr_insn,
4834 ira_reg_equiv
4835 [REGNO (SET_SRC (set))].init_insns)))
4837 /* This is equiv init insn of pseudo which did not get a
4838 hard register -- remove the insn. */
4839 if (lra_dump_file != NULL)
4841 fprintf (lra_dump_file,
4842 " Removing equiv init insn %i (freq=%d)\n",
4843 INSN_UID (curr_insn),
4844 REG_FREQ_FROM_BB (BLOCK_FOR_INSN (curr_insn)));
4845 dump_insn_slim (lra_dump_file, curr_insn);
4847 if (contains_reg_p (x, true, false))
4848 lra_risky_transformations_p = true;
4849 lra_set_insn_deleted (curr_insn);
4850 continue;
4853 curr_id = lra_get_insn_recog_data (curr_insn);
4854 curr_static_id = curr_id->insn_static_data;
4855 init_curr_insn_input_reloads ();
4856 init_curr_operand_mode ();
4857 if (curr_insn_transform (false))
4858 changed_p = true;
4859 /* Check non-transformed insns too for equiv change as USE
4860 or CLOBBER don't need reloads but can contain pseudos
4861 being changed on their equivalences. */
4862 else if (bitmap_bit_p (equiv_insn_bitmap, INSN_UID (curr_insn))
4863 && loc_equivalence_change_p (&PATTERN (curr_insn)))
4865 lra_update_insn_regno_info (curr_insn);
4866 changed_p = true;
4871 /* If we used a new hard regno, changed_p should be true because the
4872 hard reg is assigned to a new pseudo. */
4873 if (flag_checking && !changed_p)
4875 for (i = FIRST_PSEUDO_REGISTER; i < new_regno_start; i++)
4876 if (lra_reg_info[i].nrefs != 0
4877 && (hard_regno = lra_get_regno_hard_regno (i)) >= 0)
4879 int j, nregs = hard_regno_nregs (hard_regno,
4880 PSEUDO_REGNO_MODE (i));
4882 for (j = 0; j < nregs; j++)
4883 lra_assert (df_regs_ever_live_p (hard_regno + j));
4886 return changed_p;
4889 static void initiate_invariants (void);
4890 static void finish_invariants (void);
4892 /* Initiate the LRA constraint pass. It is done once per
4893 function. */
4894 void
4895 lra_constraints_init (void)
4897 initiate_invariants ();
4900 /* Finalize the LRA constraint pass. It is done once per
4901 function. */
4902 void
4903 lra_constraints_finish (void)
4905 finish_invariants ();
4910 /* Structure describes invariants for ineheritance. */
4911 struct lra_invariant
4913 /* The order number of the invariant. */
4914 int num;
4915 /* The invariant RTX. */
4916 rtx invariant_rtx;
4917 /* The origin insn of the invariant. */
4918 rtx_insn *insn;
4921 typedef lra_invariant invariant_t;
4922 typedef invariant_t *invariant_ptr_t;
4923 typedef const invariant_t *const_invariant_ptr_t;
4925 /* Pointer to the inheritance invariants. */
4926 static vec<invariant_ptr_t> invariants;
4928 /* Allocation pool for the invariants. */
4929 static object_allocator<lra_invariant> *invariants_pool;
4931 /* Hash table for the invariants. */
4932 static htab_t invariant_table;
4934 /* Hash function for INVARIANT. */
4935 static hashval_t
4936 invariant_hash (const void *invariant)
4938 rtx inv = ((const_invariant_ptr_t) invariant)->invariant_rtx;
4939 return lra_rtx_hash (inv);
4942 /* Equal function for invariants INVARIANT1 and INVARIANT2. */
4943 static int
4944 invariant_eq_p (const void *invariant1, const void *invariant2)
4946 rtx inv1 = ((const_invariant_ptr_t) invariant1)->invariant_rtx;
4947 rtx inv2 = ((const_invariant_ptr_t) invariant2)->invariant_rtx;
4949 return rtx_equal_p (inv1, inv2);
4952 /* Insert INVARIANT_RTX into the table if it is not there yet. Return
4953 invariant which is in the table. */
4954 static invariant_ptr_t
4955 insert_invariant (rtx invariant_rtx)
4957 void **entry_ptr;
4958 invariant_t invariant;
4959 invariant_ptr_t invariant_ptr;
4961 invariant.invariant_rtx = invariant_rtx;
4962 entry_ptr = htab_find_slot (invariant_table, &invariant, INSERT);
4963 if (*entry_ptr == NULL)
4965 invariant_ptr = invariants_pool->allocate ();
4966 invariant_ptr->invariant_rtx = invariant_rtx;
4967 invariant_ptr->insn = NULL;
4968 invariants.safe_push (invariant_ptr);
4969 *entry_ptr = (void *) invariant_ptr;
4971 return (invariant_ptr_t) *entry_ptr;
4974 /* Initiate the invariant table. */
4975 static void
4976 initiate_invariants (void)
4978 invariants.create (100);
4979 invariants_pool
4980 = new object_allocator<lra_invariant> ("Inheritance invariants");
4981 invariant_table = htab_create (100, invariant_hash, invariant_eq_p, NULL);
4984 /* Finish the invariant table. */
4985 static void
4986 finish_invariants (void)
4988 htab_delete (invariant_table);
4989 delete invariants_pool;
4990 invariants.release ();
4993 /* Make the invariant table empty. */
4994 static void
4995 clear_invariants (void)
4997 htab_empty (invariant_table);
4998 invariants_pool->release ();
4999 invariants.truncate (0);
5004 /* This page contains code to do inheritance/split
5005 transformations. */
5007 /* Number of reloads passed so far in current EBB. */
5008 static int reloads_num;
5010 /* Number of calls passed so far in current EBB. */
5011 static int calls_num;
5013 /* Current reload pseudo check for validity of elements in
5014 USAGE_INSNS. */
5015 static int curr_usage_insns_check;
5017 /* Info about last usage of registers in EBB to do inheritance/split
5018 transformation. Inheritance transformation is done from a spilled
5019 pseudo and split transformations from a hard register or a pseudo
5020 assigned to a hard register. */
5021 struct usage_insns
5023 /* If the value is equal to CURR_USAGE_INSNS_CHECK, then the member
5024 value INSNS is valid. The insns is chain of optional debug insns
5025 and a finishing non-debug insn using the corresponding reg. The
5026 value is also used to mark the registers which are set up in the
5027 current insn. The negated insn uid is used for this. */
5028 int check;
5029 /* Value of global reloads_num at the last insn in INSNS. */
5030 int reloads_num;
5031 /* Value of global reloads_nums at the last insn in INSNS. */
5032 int calls_num;
5033 /* It can be true only for splitting. And it means that the restore
5034 insn should be put after insn given by the following member. */
5035 bool after_p;
5036 /* Next insns in the current EBB which use the original reg and the
5037 original reg value is not changed between the current insn and
5038 the next insns. In order words, e.g. for inheritance, if we need
5039 to use the original reg value again in the next insns we can try
5040 to use the value in a hard register from a reload insn of the
5041 current insn. */
5042 rtx insns;
5045 /* Map: regno -> corresponding pseudo usage insns. */
5046 static struct usage_insns *usage_insns;
5048 static void
5049 setup_next_usage_insn (int regno, rtx insn, int reloads_num, bool after_p)
5051 usage_insns[regno].check = curr_usage_insns_check;
5052 usage_insns[regno].insns = insn;
5053 usage_insns[regno].reloads_num = reloads_num;
5054 usage_insns[regno].calls_num = calls_num;
5055 usage_insns[regno].after_p = after_p;
5058 /* The function is used to form list REGNO usages which consists of
5059 optional debug insns finished by a non-debug insn using REGNO.
5060 RELOADS_NUM is current number of reload insns processed so far. */
5061 static void
5062 add_next_usage_insn (int regno, rtx_insn *insn, int reloads_num)
5064 rtx next_usage_insns;
5066 if (usage_insns[regno].check == curr_usage_insns_check
5067 && (next_usage_insns = usage_insns[regno].insns) != NULL_RTX
5068 && DEBUG_INSN_P (insn))
5070 /* Check that we did not add the debug insn yet. */
5071 if (next_usage_insns != insn
5072 && (GET_CODE (next_usage_insns) != INSN_LIST
5073 || XEXP (next_usage_insns, 0) != insn))
5074 usage_insns[regno].insns = gen_rtx_INSN_LIST (VOIDmode, insn,
5075 next_usage_insns);
5077 else if (NONDEBUG_INSN_P (insn))
5078 setup_next_usage_insn (regno, insn, reloads_num, false);
5079 else
5080 usage_insns[regno].check = 0;
5083 /* Return first non-debug insn in list USAGE_INSNS. */
5084 static rtx_insn *
5085 skip_usage_debug_insns (rtx usage_insns)
5087 rtx insn;
5089 /* Skip debug insns. */
5090 for (insn = usage_insns;
5091 insn != NULL_RTX && GET_CODE (insn) == INSN_LIST;
5092 insn = XEXP (insn, 1))
5094 return safe_as_a <rtx_insn *> (insn);
5097 /* Return true if we need secondary memory moves for insn in
5098 USAGE_INSNS after inserting inherited pseudo of class INHER_CL
5099 into the insn. */
5100 static bool
5101 check_secondary_memory_needed_p (enum reg_class inher_cl ATTRIBUTE_UNUSED,
5102 rtx usage_insns ATTRIBUTE_UNUSED)
5104 rtx_insn *insn;
5105 rtx set, dest;
5106 enum reg_class cl;
5108 if (inher_cl == ALL_REGS
5109 || (insn = skip_usage_debug_insns (usage_insns)) == NULL_RTX)
5110 return false;
5111 lra_assert (INSN_P (insn));
5112 if ((set = single_set (insn)) == NULL_RTX || ! REG_P (SET_DEST (set)))
5113 return false;
5114 dest = SET_DEST (set);
5115 if (! REG_P (dest))
5116 return false;
5117 lra_assert (inher_cl != NO_REGS);
5118 cl = get_reg_class (REGNO (dest));
5119 return (cl != NO_REGS && cl != ALL_REGS
5120 && targetm.secondary_memory_needed (GET_MODE (dest), inher_cl, cl));
5123 /* Registers involved in inheritance/split in the current EBB
5124 (inheritance/split pseudos and original registers). */
5125 static bitmap_head check_only_regs;
5127 /* Reload pseudos can not be involded in invariant inheritance in the
5128 current EBB. */
5129 static bitmap_head invalid_invariant_regs;
5131 /* Do inheritance transformations for insn INSN, which defines (if
5132 DEF_P) or uses ORIGINAL_REGNO. NEXT_USAGE_INSNS specifies which
5133 instruction in the EBB next uses ORIGINAL_REGNO; it has the same
5134 form as the "insns" field of usage_insns. Return true if we
5135 succeed in such transformation.
5137 The transformations look like:
5139 p <- ... i <- ...
5140 ... p <- i (new insn)
5141 ... =>
5142 <- ... p ... <- ... i ...
5144 ... i <- p (new insn)
5145 <- ... p ... <- ... i ...
5146 ... =>
5147 <- ... p ... <- ... i ...
5148 where p is a spilled original pseudo and i is a new inheritance pseudo.
5151 The inheritance pseudo has the smallest class of two classes CL and
5152 class of ORIGINAL REGNO. */
5153 static bool
5154 inherit_reload_reg (bool def_p, int original_regno,
5155 enum reg_class cl, rtx_insn *insn, rtx next_usage_insns)
5157 if (optimize_function_for_size_p (cfun))
5158 return false;
5160 enum reg_class rclass = lra_get_allocno_class (original_regno);
5161 rtx original_reg = regno_reg_rtx[original_regno];
5162 rtx new_reg, usage_insn;
5163 rtx_insn *new_insns;
5165 lra_assert (! usage_insns[original_regno].after_p);
5166 if (lra_dump_file != NULL)
5167 fprintf (lra_dump_file,
5168 " <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n");
5169 if (! ira_reg_classes_intersect_p[cl][rclass])
5171 if (lra_dump_file != NULL)
5173 fprintf (lra_dump_file,
5174 " Rejecting inheritance for %d "
5175 "because of disjoint classes %s and %s\n",
5176 original_regno, reg_class_names[cl],
5177 reg_class_names[rclass]);
5178 fprintf (lra_dump_file,
5179 " >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
5181 return false;
5183 if ((ira_class_subset_p[cl][rclass] && cl != rclass)
5184 /* We don't use a subset of two classes because it can be
5185 NO_REGS. This transformation is still profitable in most
5186 cases even if the classes are not intersected as register
5187 move is probably cheaper than a memory load. */
5188 || ira_class_hard_regs_num[cl] < ira_class_hard_regs_num[rclass])
5190 if (lra_dump_file != NULL)
5191 fprintf (lra_dump_file, " Use smallest class of %s and %s\n",
5192 reg_class_names[cl], reg_class_names[rclass]);
5194 rclass = cl;
5196 if (check_secondary_memory_needed_p (rclass, next_usage_insns))
5198 /* Reject inheritance resulting in secondary memory moves.
5199 Otherwise, there is a danger in LRA cycling. Also such
5200 transformation will be unprofitable. */
5201 if (lra_dump_file != NULL)
5203 rtx_insn *insn = skip_usage_debug_insns (next_usage_insns);
5204 rtx set = single_set (insn);
5206 lra_assert (set != NULL_RTX);
5208 rtx dest = SET_DEST (set);
5210 lra_assert (REG_P (dest));
5211 fprintf (lra_dump_file,
5212 " Rejecting inheritance for insn %d(%s)<-%d(%s) "
5213 "as secondary mem is needed\n",
5214 REGNO (dest), reg_class_names[get_reg_class (REGNO (dest))],
5215 original_regno, reg_class_names[rclass]);
5216 fprintf (lra_dump_file,
5217 " >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
5219 return false;
5221 new_reg = lra_create_new_reg (GET_MODE (original_reg), original_reg,
5222 rclass, "inheritance");
5223 start_sequence ();
5224 if (def_p)
5225 lra_emit_move (original_reg, new_reg);
5226 else
5227 lra_emit_move (new_reg, original_reg);
5228 new_insns = get_insns ();
5229 end_sequence ();
5230 if (NEXT_INSN (new_insns) != NULL_RTX)
5232 if (lra_dump_file != NULL)
5234 fprintf (lra_dump_file,
5235 " Rejecting inheritance %d->%d "
5236 "as it results in 2 or more insns:\n",
5237 original_regno, REGNO (new_reg));
5238 dump_rtl_slim (lra_dump_file, new_insns, NULL, -1, 0);
5239 fprintf (lra_dump_file,
5240 " >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
5242 return false;
5244 lra_substitute_pseudo_within_insn (insn, original_regno, new_reg, false);
5245 lra_update_insn_regno_info (insn);
5246 if (! def_p)
5247 /* We now have a new usage insn for original regno. */
5248 setup_next_usage_insn (original_regno, new_insns, reloads_num, false);
5249 if (lra_dump_file != NULL)
5250 fprintf (lra_dump_file, " Original reg change %d->%d (bb%d):\n",
5251 original_regno, REGNO (new_reg), BLOCK_FOR_INSN (insn)->index);
5252 lra_reg_info[REGNO (new_reg)].restore_rtx = regno_reg_rtx[original_regno];
5253 bitmap_set_bit (&check_only_regs, REGNO (new_reg));
5254 bitmap_set_bit (&check_only_regs, original_regno);
5255 bitmap_set_bit (&lra_inheritance_pseudos, REGNO (new_reg));
5256 if (def_p)
5257 lra_process_new_insns (insn, NULL, new_insns,
5258 "Add original<-inheritance");
5259 else
5260 lra_process_new_insns (insn, new_insns, NULL,
5261 "Add inheritance<-original");
5262 while (next_usage_insns != NULL_RTX)
5264 if (GET_CODE (next_usage_insns) != INSN_LIST)
5266 usage_insn = next_usage_insns;
5267 lra_assert (NONDEBUG_INSN_P (usage_insn));
5268 next_usage_insns = NULL;
5270 else
5272 usage_insn = XEXP (next_usage_insns, 0);
5273 lra_assert (DEBUG_INSN_P (usage_insn));
5274 next_usage_insns = XEXP (next_usage_insns, 1);
5276 lra_substitute_pseudo (&usage_insn, original_regno, new_reg, false);
5277 lra_update_insn_regno_info (as_a <rtx_insn *> (usage_insn));
5278 if (lra_dump_file != NULL)
5280 basic_block bb = BLOCK_FOR_INSN (usage_insn);
5281 fprintf (lra_dump_file,
5282 " Inheritance reuse change %d->%d (bb%d):\n",
5283 original_regno, REGNO (new_reg),
5284 bb ? bb->index : -1);
5285 dump_insn_slim (lra_dump_file, as_a <rtx_insn *> (usage_insn));
5288 if (lra_dump_file != NULL)
5289 fprintf (lra_dump_file,
5290 " >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
5291 return true;
5294 /* Return true if we need a caller save/restore for pseudo REGNO which
5295 was assigned to a hard register. */
5296 static inline bool
5297 need_for_call_save_p (int regno)
5299 lra_assert (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] >= 0);
5300 return (usage_insns[regno].calls_num < calls_num
5301 && (overlaps_hard_reg_set_p
5302 ((flag_ipa_ra &&
5303 ! hard_reg_set_empty_p (lra_reg_info[regno].actual_call_used_reg_set))
5304 ? lra_reg_info[regno].actual_call_used_reg_set
5305 : call_used_reg_set,
5306 PSEUDO_REGNO_MODE (regno), reg_renumber[regno])
5307 || (targetm.hard_regno_call_part_clobbered
5308 (reg_renumber[regno], PSEUDO_REGNO_MODE (regno)))));
5311 /* Global registers occurring in the current EBB. */
5312 static bitmap_head ebb_global_regs;
5314 /* Return true if we need a split for hard register REGNO or pseudo
5315 REGNO which was assigned to a hard register.
5316 POTENTIAL_RELOAD_HARD_REGS contains hard registers which might be
5317 used for reloads since the EBB end. It is an approximation of the
5318 used hard registers in the split range. The exact value would
5319 require expensive calculations. If we were aggressive with
5320 splitting because of the approximation, the split pseudo will save
5321 the same hard register assignment and will be removed in the undo
5322 pass. We still need the approximation because too aggressive
5323 splitting would result in too inaccurate cost calculation in the
5324 assignment pass because of too many generated moves which will be
5325 probably removed in the undo pass. */
5326 static inline bool
5327 need_for_split_p (HARD_REG_SET potential_reload_hard_regs, int regno)
5329 int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
5331 lra_assert (hard_regno >= 0);
5332 return ((TEST_HARD_REG_BIT (potential_reload_hard_regs, hard_regno)
5333 /* Don't split eliminable hard registers, otherwise we can
5334 split hard registers like hard frame pointer, which
5335 lives on BB start/end according to DF-infrastructure,
5336 when there is a pseudo assigned to the register and
5337 living in the same BB. */
5338 && (regno >= FIRST_PSEUDO_REGISTER
5339 || ! TEST_HARD_REG_BIT (eliminable_regset, hard_regno))
5340 && ! TEST_HARD_REG_BIT (lra_no_alloc_regs, hard_regno)
5341 /* Don't split call clobbered hard regs living through
5342 calls, otherwise we might have a check problem in the
5343 assign sub-pass as in the most cases (exception is a
5344 situation when lra_risky_transformations_p value is
5345 true) the assign pass assumes that all pseudos living
5346 through calls are assigned to call saved hard regs. */
5347 && (regno >= FIRST_PSEUDO_REGISTER
5348 || ! TEST_HARD_REG_BIT (call_used_reg_set, regno)
5349 || usage_insns[regno].calls_num == calls_num)
5350 /* We need at least 2 reloads to make pseudo splitting
5351 profitable. We should provide hard regno splitting in
5352 any case to solve 1st insn scheduling problem when
5353 moving hard register definition up might result in
5354 impossibility to find hard register for reload pseudo of
5355 small register class. */
5356 && (usage_insns[regno].reloads_num
5357 + (regno < FIRST_PSEUDO_REGISTER ? 0 : 3) < reloads_num)
5358 && (regno < FIRST_PSEUDO_REGISTER
5359 /* For short living pseudos, spilling + inheritance can
5360 be considered a substitution for splitting.
5361 Therefore we do not splitting for local pseudos. It
5362 decreases also aggressiveness of splitting. The
5363 minimal number of references is chosen taking into
5364 account that for 2 references splitting has no sense
5365 as we can just spill the pseudo. */
5366 || (regno >= FIRST_PSEUDO_REGISTER
5367 && lra_reg_info[regno].nrefs > 3
5368 && bitmap_bit_p (&ebb_global_regs, regno))))
5369 || (regno >= FIRST_PSEUDO_REGISTER && need_for_call_save_p (regno)));
5372 /* Return class for the split pseudo created from original pseudo with
5373 ALLOCNO_CLASS and MODE which got a hard register HARD_REGNO. We
5374 choose subclass of ALLOCNO_CLASS which contains HARD_REGNO and
5375 results in no secondary memory movements. */
5376 static enum reg_class
5377 choose_split_class (enum reg_class allocno_class,
5378 int hard_regno ATTRIBUTE_UNUSED,
5379 machine_mode mode ATTRIBUTE_UNUSED)
5381 int i;
5382 enum reg_class cl, best_cl = NO_REGS;
5383 enum reg_class hard_reg_class ATTRIBUTE_UNUSED
5384 = REGNO_REG_CLASS (hard_regno);
5386 if (! targetm.secondary_memory_needed (mode, allocno_class, allocno_class)
5387 && TEST_HARD_REG_BIT (reg_class_contents[allocno_class], hard_regno))
5388 return allocno_class;
5389 for (i = 0;
5390 (cl = reg_class_subclasses[allocno_class][i]) != LIM_REG_CLASSES;
5391 i++)
5392 if (! targetm.secondary_memory_needed (mode, cl, hard_reg_class)
5393 && ! targetm.secondary_memory_needed (mode, hard_reg_class, cl)
5394 && TEST_HARD_REG_BIT (reg_class_contents[cl], hard_regno)
5395 && (best_cl == NO_REGS
5396 || ira_class_hard_regs_num[best_cl] < ira_class_hard_regs_num[cl]))
5397 best_cl = cl;
5398 return best_cl;
5401 /* Copy any equivalence information from ORIGINAL_REGNO to NEW_REGNO.
5402 It only makes sense to call this function if NEW_REGNO is always
5403 equal to ORIGINAL_REGNO. */
5405 static void
5406 lra_copy_reg_equiv (unsigned int new_regno, unsigned int original_regno)
5408 if (!ira_reg_equiv[original_regno].defined_p)
5409 return;
5411 ira_expand_reg_equiv ();
5412 ira_reg_equiv[new_regno].defined_p = true;
5413 if (ira_reg_equiv[original_regno].memory)
5414 ira_reg_equiv[new_regno].memory
5415 = copy_rtx (ira_reg_equiv[original_regno].memory);
5416 if (ira_reg_equiv[original_regno].constant)
5417 ira_reg_equiv[new_regno].constant
5418 = copy_rtx (ira_reg_equiv[original_regno].constant);
5419 if (ira_reg_equiv[original_regno].invariant)
5420 ira_reg_equiv[new_regno].invariant
5421 = copy_rtx (ira_reg_equiv[original_regno].invariant);
5424 /* Do split transformations for insn INSN, which defines or uses
5425 ORIGINAL_REGNO. NEXT_USAGE_INSNS specifies which instruction in
5426 the EBB next uses ORIGINAL_REGNO; it has the same form as the
5427 "insns" field of usage_insns.
5429 The transformations look like:
5431 p <- ... p <- ...
5432 ... s <- p (new insn -- save)
5433 ... =>
5434 ... p <- s (new insn -- restore)
5435 <- ... p ... <- ... p ...
5437 <- ... p ... <- ... p ...
5438 ... s <- p (new insn -- save)
5439 ... =>
5440 ... p <- s (new insn -- restore)
5441 <- ... p ... <- ... p ...
5443 where p is an original pseudo got a hard register or a hard
5444 register and s is a new split pseudo. The save is put before INSN
5445 if BEFORE_P is true. Return true if we succeed in such
5446 transformation. */
5447 static bool
5448 split_reg (bool before_p, int original_regno, rtx_insn *insn,
5449 rtx next_usage_insns)
5451 enum reg_class rclass;
5452 rtx original_reg;
5453 int hard_regno, nregs;
5454 rtx new_reg, usage_insn;
5455 rtx_insn *restore, *save;
5456 bool after_p;
5457 bool call_save_p;
5458 machine_mode mode;
5460 if (original_regno < FIRST_PSEUDO_REGISTER)
5462 rclass = ira_allocno_class_translate[REGNO_REG_CLASS (original_regno)];
5463 hard_regno = original_regno;
5464 call_save_p = false;
5465 nregs = 1;
5466 mode = lra_reg_info[hard_regno].biggest_mode;
5467 machine_mode reg_rtx_mode = GET_MODE (regno_reg_rtx[hard_regno]);
5468 /* A reg can have a biggest_mode of VOIDmode if it was only ever seen
5469 as part of a multi-word register. In that case, or if the biggest
5470 mode was larger than a register, just use the reg_rtx. Otherwise,
5471 limit the size to that of the biggest access in the function. */
5472 if (mode == VOIDmode
5473 || paradoxical_subreg_p (mode, reg_rtx_mode))
5475 original_reg = regno_reg_rtx[hard_regno];
5476 mode = reg_rtx_mode;
5478 else
5479 original_reg = gen_rtx_REG (mode, hard_regno);
5481 else
5483 mode = PSEUDO_REGNO_MODE (original_regno);
5484 hard_regno = reg_renumber[original_regno];
5485 nregs = hard_regno_nregs (hard_regno, mode);
5486 rclass = lra_get_allocno_class (original_regno);
5487 original_reg = regno_reg_rtx[original_regno];
5488 call_save_p = need_for_call_save_p (original_regno);
5490 lra_assert (hard_regno >= 0);
5491 if (lra_dump_file != NULL)
5492 fprintf (lra_dump_file,
5493 " ((((((((((((((((((((((((((((((((((((((((((((((((\n");
5495 if (call_save_p)
5497 mode = HARD_REGNO_CALLER_SAVE_MODE (hard_regno,
5498 hard_regno_nregs (hard_regno, mode),
5499 mode);
5500 new_reg = lra_create_new_reg (mode, NULL_RTX, NO_REGS, "save");
5502 else
5504 rclass = choose_split_class (rclass, hard_regno, mode);
5505 if (rclass == NO_REGS)
5507 if (lra_dump_file != NULL)
5509 fprintf (lra_dump_file,
5510 " Rejecting split of %d(%s): "
5511 "no good reg class for %d(%s)\n",
5512 original_regno,
5513 reg_class_names[lra_get_allocno_class (original_regno)],
5514 hard_regno,
5515 reg_class_names[REGNO_REG_CLASS (hard_regno)]);
5516 fprintf
5517 (lra_dump_file,
5518 " ))))))))))))))))))))))))))))))))))))))))))))))))\n");
5520 return false;
5522 /* Split_if_necessary can split hard registers used as part of a
5523 multi-register mode but splits each register individually. The
5524 mode used for each independent register may not be supported
5525 so reject the split. Splitting the wider mode should theoretically
5526 be possible but is not implemented. */
5527 if (!targetm.hard_regno_mode_ok (hard_regno, mode))
5529 if (lra_dump_file != NULL)
5531 fprintf (lra_dump_file,
5532 " Rejecting split of %d(%s): unsuitable mode %s\n",
5533 original_regno,
5534 reg_class_names[lra_get_allocno_class (original_regno)],
5535 GET_MODE_NAME (mode));
5536 fprintf
5537 (lra_dump_file,
5538 " ))))))))))))))))))))))))))))))))))))))))))))))))\n");
5540 return false;
5542 new_reg = lra_create_new_reg (mode, original_reg, rclass, "split");
5543 reg_renumber[REGNO (new_reg)] = hard_regno;
5545 int new_regno = REGNO (new_reg);
5546 save = emit_spill_move (true, new_reg, original_reg);
5547 if (NEXT_INSN (save) != NULL_RTX && !call_save_p)
5549 if (lra_dump_file != NULL)
5551 fprintf
5552 (lra_dump_file,
5553 " Rejecting split %d->%d resulting in > 2 save insns:\n",
5554 original_regno, new_regno);
5555 dump_rtl_slim (lra_dump_file, save, NULL, -1, 0);
5556 fprintf (lra_dump_file,
5557 " ))))))))))))))))))))))))))))))))))))))))))))))))\n");
5559 return false;
5561 restore = emit_spill_move (false, new_reg, original_reg);
5562 if (NEXT_INSN (restore) != NULL_RTX && !call_save_p)
5564 if (lra_dump_file != NULL)
5566 fprintf (lra_dump_file,
5567 " Rejecting split %d->%d "
5568 "resulting in > 2 restore insns:\n",
5569 original_regno, new_regno);
5570 dump_rtl_slim (lra_dump_file, restore, NULL, -1, 0);
5571 fprintf (lra_dump_file,
5572 " ))))))))))))))))))))))))))))))))))))))))))))))))\n");
5574 return false;
5576 /* Transfer equivalence information to the spill register, so that
5577 if we fail to allocate the spill register, we have the option of
5578 rematerializing the original value instead of spilling to the stack. */
5579 if (!HARD_REGISTER_NUM_P (original_regno)
5580 && mode == PSEUDO_REGNO_MODE (original_regno))
5581 lra_copy_reg_equiv (new_regno, original_regno);
5582 after_p = usage_insns[original_regno].after_p;
5583 lra_reg_info[new_regno].restore_rtx = regno_reg_rtx[original_regno];
5584 bitmap_set_bit (&check_only_regs, new_regno);
5585 bitmap_set_bit (&check_only_regs, original_regno);
5586 bitmap_set_bit (&lra_split_regs, new_regno);
5587 for (;;)
5589 if (GET_CODE (next_usage_insns) != INSN_LIST)
5591 usage_insn = next_usage_insns;
5592 break;
5594 usage_insn = XEXP (next_usage_insns, 0);
5595 lra_assert (DEBUG_INSN_P (usage_insn));
5596 next_usage_insns = XEXP (next_usage_insns, 1);
5597 lra_substitute_pseudo (&usage_insn, original_regno, new_reg, false);
5598 lra_update_insn_regno_info (as_a <rtx_insn *> (usage_insn));
5599 if (lra_dump_file != NULL)
5601 fprintf (lra_dump_file, " Split reuse change %d->%d:\n",
5602 original_regno, new_regno);
5603 dump_insn_slim (lra_dump_file, as_a <rtx_insn *> (usage_insn));
5606 lra_assert (NOTE_P (usage_insn) || NONDEBUG_INSN_P (usage_insn));
5607 lra_assert (usage_insn != insn || (after_p && before_p));
5608 lra_process_new_insns (as_a <rtx_insn *> (usage_insn),
5609 after_p ? NULL : restore,
5610 after_p ? restore : NULL,
5611 call_save_p
5612 ? "Add reg<-save" : "Add reg<-split");
5613 lra_process_new_insns (insn, before_p ? save : NULL,
5614 before_p ? NULL : save,
5615 call_save_p
5616 ? "Add save<-reg" : "Add split<-reg");
5617 if (nregs > 1)
5618 /* If we are trying to split multi-register. We should check
5619 conflicts on the next assignment sub-pass. IRA can allocate on
5620 sub-register levels, LRA do this on pseudos level right now and
5621 this discrepancy may create allocation conflicts after
5622 splitting. */
5623 lra_risky_transformations_p = true;
5624 if (lra_dump_file != NULL)
5625 fprintf (lra_dump_file,
5626 " ))))))))))))))))))))))))))))))))))))))))))))))))\n");
5627 return true;
5630 /* Recognize that we need a split transformation for insn INSN, which
5631 defines or uses REGNO in its insn biggest MODE (we use it only if
5632 REGNO is a hard register). POTENTIAL_RELOAD_HARD_REGS contains
5633 hard registers which might be used for reloads since the EBB end.
5634 Put the save before INSN if BEFORE_P is true. MAX_UID is maximla
5635 uid before starting INSN processing. Return true if we succeed in
5636 such transformation. */
5637 static bool
5638 split_if_necessary (int regno, machine_mode mode,
5639 HARD_REG_SET potential_reload_hard_regs,
5640 bool before_p, rtx_insn *insn, int max_uid)
5642 bool res = false;
5643 int i, nregs = 1;
5644 rtx next_usage_insns;
5646 if (regno < FIRST_PSEUDO_REGISTER)
5647 nregs = hard_regno_nregs (regno, mode);
5648 for (i = 0; i < nregs; i++)
5649 if (usage_insns[regno + i].check == curr_usage_insns_check
5650 && (next_usage_insns = usage_insns[regno + i].insns) != NULL_RTX
5651 /* To avoid processing the register twice or more. */
5652 && ((GET_CODE (next_usage_insns) != INSN_LIST
5653 && INSN_UID (next_usage_insns) < max_uid)
5654 || (GET_CODE (next_usage_insns) == INSN_LIST
5655 && (INSN_UID (XEXP (next_usage_insns, 0)) < max_uid)))
5656 && need_for_split_p (potential_reload_hard_regs, regno + i)
5657 && split_reg (before_p, regno + i, insn, next_usage_insns))
5658 res = true;
5659 return res;
5662 /* Return TRUE if rtx X is considered as an invariant for
5663 inheritance. */
5664 static bool
5665 invariant_p (const_rtx x)
5667 machine_mode mode;
5668 const char *fmt;
5669 enum rtx_code code;
5670 int i, j;
5672 code = GET_CODE (x);
5673 mode = GET_MODE (x);
5674 if (code == SUBREG)
5676 x = SUBREG_REG (x);
5677 code = GET_CODE (x);
5678 mode = wider_subreg_mode (mode, GET_MODE (x));
5681 if (MEM_P (x))
5682 return false;
5684 if (REG_P (x))
5686 int i, nregs, regno = REGNO (x);
5688 if (regno >= FIRST_PSEUDO_REGISTER || regno == STACK_POINTER_REGNUM
5689 || TEST_HARD_REG_BIT (eliminable_regset, regno)
5690 || GET_MODE_CLASS (GET_MODE (x)) == MODE_CC)
5691 return false;
5692 nregs = hard_regno_nregs (regno, mode);
5693 for (i = 0; i < nregs; i++)
5694 if (! fixed_regs[regno + i]
5695 /* A hard register may be clobbered in the current insn
5696 but we can ignore this case because if the hard
5697 register is used it should be set somewhere after the
5698 clobber. */
5699 || bitmap_bit_p (&invalid_invariant_regs, regno + i))
5700 return false;
5702 fmt = GET_RTX_FORMAT (code);
5703 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5705 if (fmt[i] == 'e')
5707 if (! invariant_p (XEXP (x, i)))
5708 return false;
5710 else if (fmt[i] == 'E')
5712 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5713 if (! invariant_p (XVECEXP (x, i, j)))
5714 return false;
5717 return true;
5720 /* We have 'dest_reg <- invariant'. Let us try to make an invariant
5721 inheritance transformation (using dest_reg instead invariant in a
5722 subsequent insn). */
5723 static bool
5724 process_invariant_for_inheritance (rtx dst_reg, rtx invariant_rtx)
5726 invariant_ptr_t invariant_ptr;
5727 rtx_insn *insn, *new_insns;
5728 rtx insn_set, insn_reg, new_reg;
5729 int insn_regno;
5730 bool succ_p = false;
5731 int dst_regno = REGNO (dst_reg);
5732 machine_mode dst_mode = GET_MODE (dst_reg);
5733 enum reg_class cl = lra_get_allocno_class (dst_regno), insn_reg_cl;
5735 invariant_ptr = insert_invariant (invariant_rtx);
5736 if ((insn = invariant_ptr->insn) != NULL_RTX)
5738 /* We have a subsequent insn using the invariant. */
5739 insn_set = single_set (insn);
5740 lra_assert (insn_set != NULL);
5741 insn_reg = SET_DEST (insn_set);
5742 lra_assert (REG_P (insn_reg));
5743 insn_regno = REGNO (insn_reg);
5744 insn_reg_cl = lra_get_allocno_class (insn_regno);
5746 if (dst_mode == GET_MODE (insn_reg)
5747 /* We should consider only result move reg insns which are
5748 cheap. */
5749 && targetm.register_move_cost (dst_mode, cl, insn_reg_cl) == 2
5750 && targetm.register_move_cost (dst_mode, cl, cl) == 2)
5752 if (lra_dump_file != NULL)
5753 fprintf (lra_dump_file,
5754 " [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[\n");
5755 new_reg = lra_create_new_reg (dst_mode, dst_reg,
5756 cl, "invariant inheritance");
5757 bitmap_set_bit (&lra_inheritance_pseudos, REGNO (new_reg));
5758 bitmap_set_bit (&check_only_regs, REGNO (new_reg));
5759 lra_reg_info[REGNO (new_reg)].restore_rtx = PATTERN (insn);
5760 start_sequence ();
5761 lra_emit_move (new_reg, dst_reg);
5762 new_insns = get_insns ();
5763 end_sequence ();
5764 lra_process_new_insns (curr_insn, NULL, new_insns,
5765 "Add invariant inheritance<-original");
5766 start_sequence ();
5767 lra_emit_move (SET_DEST (insn_set), new_reg);
5768 new_insns = get_insns ();
5769 end_sequence ();
5770 lra_process_new_insns (insn, NULL, new_insns,
5771 "Changing reload<-inheritance");
5772 lra_set_insn_deleted (insn);
5773 succ_p = true;
5774 if (lra_dump_file != NULL)
5776 fprintf (lra_dump_file,
5777 " Invariant inheritance reuse change %d (bb%d):\n",
5778 REGNO (new_reg), BLOCK_FOR_INSN (insn)->index);
5779 dump_insn_slim (lra_dump_file, insn);
5780 fprintf (lra_dump_file,
5781 " ]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]\n");
5785 invariant_ptr->insn = curr_insn;
5786 return succ_p;
5789 /* Check only registers living at the current program point in the
5790 current EBB. */
5791 static bitmap_head live_regs;
5793 /* Update live info in EBB given by its HEAD and TAIL insns after
5794 inheritance/split transformation. The function removes dead moves
5795 too. */
5796 static void
5797 update_ebb_live_info (rtx_insn *head, rtx_insn *tail)
5799 unsigned int j;
5800 int i, regno;
5801 bool live_p;
5802 rtx_insn *prev_insn;
5803 rtx set;
5804 bool remove_p;
5805 basic_block last_bb, prev_bb, curr_bb;
5806 bitmap_iterator bi;
5807 struct lra_insn_reg *reg;
5808 edge e;
5809 edge_iterator ei;
5811 last_bb = BLOCK_FOR_INSN (tail);
5812 prev_bb = NULL;
5813 for (curr_insn = tail;
5814 curr_insn != PREV_INSN (head);
5815 curr_insn = prev_insn)
5817 prev_insn = PREV_INSN (curr_insn);
5818 /* We need to process empty blocks too. They contain
5819 NOTE_INSN_BASIC_BLOCK referring for the basic block. */
5820 if (NOTE_P (curr_insn) && NOTE_KIND (curr_insn) != NOTE_INSN_BASIC_BLOCK)
5821 continue;
5822 curr_bb = BLOCK_FOR_INSN (curr_insn);
5823 if (curr_bb != prev_bb)
5825 if (prev_bb != NULL)
5827 /* Update df_get_live_in (prev_bb): */
5828 EXECUTE_IF_SET_IN_BITMAP (&check_only_regs, 0, j, bi)
5829 if (bitmap_bit_p (&live_regs, j))
5830 bitmap_set_bit (df_get_live_in (prev_bb), j);
5831 else
5832 bitmap_clear_bit (df_get_live_in (prev_bb), j);
5834 if (curr_bb != last_bb)
5836 /* Update df_get_live_out (curr_bb): */
5837 EXECUTE_IF_SET_IN_BITMAP (&check_only_regs, 0, j, bi)
5839 live_p = bitmap_bit_p (&live_regs, j);
5840 if (! live_p)
5841 FOR_EACH_EDGE (e, ei, curr_bb->succs)
5842 if (bitmap_bit_p (df_get_live_in (e->dest), j))
5844 live_p = true;
5845 break;
5847 if (live_p)
5848 bitmap_set_bit (df_get_live_out (curr_bb), j);
5849 else
5850 bitmap_clear_bit (df_get_live_out (curr_bb), j);
5853 prev_bb = curr_bb;
5854 bitmap_and (&live_regs, &check_only_regs, df_get_live_out (curr_bb));
5856 if (! NONDEBUG_INSN_P (curr_insn))
5857 continue;
5858 curr_id = lra_get_insn_recog_data (curr_insn);
5859 curr_static_id = curr_id->insn_static_data;
5860 remove_p = false;
5861 if ((set = single_set (curr_insn)) != NULL_RTX
5862 && REG_P (SET_DEST (set))
5863 && (regno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
5864 && SET_DEST (set) != pic_offset_table_rtx
5865 && bitmap_bit_p (&check_only_regs, regno)
5866 && ! bitmap_bit_p (&live_regs, regno))
5867 remove_p = true;
5868 /* See which defined values die here. */
5869 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
5870 if (reg->type == OP_OUT && ! reg->subreg_p)
5871 bitmap_clear_bit (&live_regs, reg->regno);
5872 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
5873 if (reg->type == OP_OUT && ! reg->subreg_p)
5874 bitmap_clear_bit (&live_regs, reg->regno);
5875 if (curr_id->arg_hard_regs != NULL)
5876 /* Make clobbered argument hard registers die. */
5877 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
5878 if (regno >= FIRST_PSEUDO_REGISTER)
5879 bitmap_clear_bit (&live_regs, regno - FIRST_PSEUDO_REGISTER);
5880 /* Mark each used value as live. */
5881 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
5882 if (reg->type != OP_OUT
5883 && bitmap_bit_p (&check_only_regs, reg->regno))
5884 bitmap_set_bit (&live_regs, reg->regno);
5885 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
5886 if (reg->type != OP_OUT
5887 && bitmap_bit_p (&check_only_regs, reg->regno))
5888 bitmap_set_bit (&live_regs, reg->regno);
5889 if (curr_id->arg_hard_regs != NULL)
5890 /* Make used argument hard registers live. */
5891 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
5892 if (regno < FIRST_PSEUDO_REGISTER
5893 && bitmap_bit_p (&check_only_regs, regno))
5894 bitmap_set_bit (&live_regs, regno);
5895 /* It is quite important to remove dead move insns because it
5896 means removing dead store. We don't need to process them for
5897 constraints. */
5898 if (remove_p)
5900 if (lra_dump_file != NULL)
5902 fprintf (lra_dump_file, " Removing dead insn:\n ");
5903 dump_insn_slim (lra_dump_file, curr_insn);
5905 lra_set_insn_deleted (curr_insn);
5910 /* The structure describes info to do an inheritance for the current
5911 insn. We need to collect such info first before doing the
5912 transformations because the transformations change the insn
5913 internal representation. */
5914 struct to_inherit
5916 /* Original regno. */
5917 int regno;
5918 /* Subsequent insns which can inherit original reg value. */
5919 rtx insns;
5922 /* Array containing all info for doing inheritance from the current
5923 insn. */
5924 static struct to_inherit to_inherit[LRA_MAX_INSN_RELOADS];
5926 /* Number elements in the previous array. */
5927 static int to_inherit_num;
5929 /* Add inheritance info REGNO and INSNS. Their meaning is described in
5930 structure to_inherit. */
5931 static void
5932 add_to_inherit (int regno, rtx insns)
5934 int i;
5936 for (i = 0; i < to_inherit_num; i++)
5937 if (to_inherit[i].regno == regno)
5938 return;
5939 lra_assert (to_inherit_num < LRA_MAX_INSN_RELOADS);
5940 to_inherit[to_inherit_num].regno = regno;
5941 to_inherit[to_inherit_num++].insns = insns;
5944 /* Return the last non-debug insn in basic block BB, or the block begin
5945 note if none. */
5946 static rtx_insn *
5947 get_last_insertion_point (basic_block bb)
5949 rtx_insn *insn;
5951 FOR_BB_INSNS_REVERSE (bb, insn)
5952 if (NONDEBUG_INSN_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
5953 return insn;
5954 gcc_unreachable ();
5957 /* Set up RES by registers living on edges FROM except the edge (FROM,
5958 TO) or by registers set up in a jump insn in BB FROM. */
5959 static void
5960 get_live_on_other_edges (basic_block from, basic_block to, bitmap res)
5962 rtx_insn *last;
5963 struct lra_insn_reg *reg;
5964 edge e;
5965 edge_iterator ei;
5967 lra_assert (to != NULL);
5968 bitmap_clear (res);
5969 FOR_EACH_EDGE (e, ei, from->succs)
5970 if (e->dest != to)
5971 bitmap_ior_into (res, df_get_live_in (e->dest));
5972 last = get_last_insertion_point (from);
5973 if (! JUMP_P (last))
5974 return;
5975 curr_id = lra_get_insn_recog_data (last);
5976 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
5977 if (reg->type != OP_IN)
5978 bitmap_set_bit (res, reg->regno);
5981 /* Used as a temporary results of some bitmap calculations. */
5982 static bitmap_head temp_bitmap;
5984 /* We split for reloads of small class of hard regs. The following
5985 defines how many hard regs the class should have to be qualified as
5986 small. The code is mostly oriented to x86/x86-64 architecture
5987 where some insns need to use only specific register or pair of
5988 registers and these register can live in RTL explicitly, e.g. for
5989 parameter passing. */
5990 static const int max_small_class_regs_num = 2;
5992 /* Do inheritance/split transformations in EBB starting with HEAD and
5993 finishing on TAIL. We process EBB insns in the reverse order.
5994 Return true if we did any inheritance/split transformation in the
5995 EBB.
5997 We should avoid excessive splitting which results in worse code
5998 because of inaccurate cost calculations for spilling new split
5999 pseudos in such case. To achieve this we do splitting only if
6000 register pressure is high in given basic block and there are reload
6001 pseudos requiring hard registers. We could do more register
6002 pressure calculations at any given program point to avoid necessary
6003 splitting even more but it is to expensive and the current approach
6004 works well enough. */
6005 static bool
6006 inherit_in_ebb (rtx_insn *head, rtx_insn *tail)
6008 int i, src_regno, dst_regno, nregs;
6009 bool change_p, succ_p, update_reloads_num_p;
6010 rtx_insn *prev_insn, *last_insn;
6011 rtx next_usage_insns, curr_set;
6012 enum reg_class cl;
6013 struct lra_insn_reg *reg;
6014 basic_block last_processed_bb, curr_bb = NULL;
6015 HARD_REG_SET potential_reload_hard_regs, live_hard_regs;
6016 bitmap to_process;
6017 unsigned int j;
6018 bitmap_iterator bi;
6019 bool head_p, after_p;
6021 change_p = false;
6022 curr_usage_insns_check++;
6023 clear_invariants ();
6024 reloads_num = calls_num = 0;
6025 bitmap_clear (&check_only_regs);
6026 bitmap_clear (&invalid_invariant_regs);
6027 last_processed_bb = NULL;
6028 CLEAR_HARD_REG_SET (potential_reload_hard_regs);
6029 COPY_HARD_REG_SET (live_hard_regs, eliminable_regset);
6030 IOR_HARD_REG_SET (live_hard_regs, lra_no_alloc_regs);
6031 /* We don't process new insns generated in the loop. */
6032 for (curr_insn = tail; curr_insn != PREV_INSN (head); curr_insn = prev_insn)
6034 prev_insn = PREV_INSN (curr_insn);
6035 if (BLOCK_FOR_INSN (curr_insn) != NULL)
6036 curr_bb = BLOCK_FOR_INSN (curr_insn);
6037 if (last_processed_bb != curr_bb)
6039 /* We are at the end of BB. Add qualified living
6040 pseudos for potential splitting. */
6041 to_process = df_get_live_out (curr_bb);
6042 if (last_processed_bb != NULL)
6044 /* We are somewhere in the middle of EBB. */
6045 get_live_on_other_edges (curr_bb, last_processed_bb,
6046 &temp_bitmap);
6047 to_process = &temp_bitmap;
6049 last_processed_bb = curr_bb;
6050 last_insn = get_last_insertion_point (curr_bb);
6051 after_p = (! JUMP_P (last_insn)
6052 && (! CALL_P (last_insn)
6053 || (find_reg_note (last_insn,
6054 REG_NORETURN, NULL_RTX) == NULL_RTX
6055 && ! SIBLING_CALL_P (last_insn))));
6056 CLEAR_HARD_REG_SET (potential_reload_hard_regs);
6057 EXECUTE_IF_SET_IN_BITMAP (to_process, 0, j, bi)
6059 if ((int) j >= lra_constraint_new_regno_start)
6060 break;
6061 if (j < FIRST_PSEUDO_REGISTER || reg_renumber[j] >= 0)
6063 if (j < FIRST_PSEUDO_REGISTER)
6064 SET_HARD_REG_BIT (live_hard_regs, j);
6065 else
6066 add_to_hard_reg_set (&live_hard_regs,
6067 PSEUDO_REGNO_MODE (j),
6068 reg_renumber[j]);
6069 setup_next_usage_insn (j, last_insn, reloads_num, after_p);
6073 src_regno = dst_regno = -1;
6074 curr_set = single_set (curr_insn);
6075 if (curr_set != NULL_RTX && REG_P (SET_DEST (curr_set)))
6076 dst_regno = REGNO (SET_DEST (curr_set));
6077 if (curr_set != NULL_RTX && REG_P (SET_SRC (curr_set)))
6078 src_regno = REGNO (SET_SRC (curr_set));
6079 update_reloads_num_p = true;
6080 if (src_regno < lra_constraint_new_regno_start
6081 && src_regno >= FIRST_PSEUDO_REGISTER
6082 && reg_renumber[src_regno] < 0
6083 && dst_regno >= lra_constraint_new_regno_start
6084 && (cl = lra_get_allocno_class (dst_regno)) != NO_REGS)
6086 /* 'reload_pseudo <- original_pseudo'. */
6087 if (ira_class_hard_regs_num[cl] <= max_small_class_regs_num)
6088 reloads_num++;
6089 update_reloads_num_p = false;
6090 succ_p = false;
6091 if (usage_insns[src_regno].check == curr_usage_insns_check
6092 && (next_usage_insns = usage_insns[src_regno].insns) != NULL_RTX)
6093 succ_p = inherit_reload_reg (false, src_regno, cl,
6094 curr_insn, next_usage_insns);
6095 if (succ_p)
6096 change_p = true;
6097 else
6098 setup_next_usage_insn (src_regno, curr_insn, reloads_num, false);
6099 if (hard_reg_set_subset_p (reg_class_contents[cl], live_hard_regs))
6100 IOR_HARD_REG_SET (potential_reload_hard_regs,
6101 reg_class_contents[cl]);
6103 else if (src_regno < 0
6104 && dst_regno >= lra_constraint_new_regno_start
6105 && invariant_p (SET_SRC (curr_set))
6106 && (cl = lra_get_allocno_class (dst_regno)) != NO_REGS
6107 && ! bitmap_bit_p (&invalid_invariant_regs, dst_regno)
6108 && ! bitmap_bit_p (&invalid_invariant_regs,
6109 ORIGINAL_REGNO(regno_reg_rtx[dst_regno])))
6111 /* 'reload_pseudo <- invariant'. */
6112 if (ira_class_hard_regs_num[cl] <= max_small_class_regs_num)
6113 reloads_num++;
6114 update_reloads_num_p = false;
6115 if (process_invariant_for_inheritance (SET_DEST (curr_set), SET_SRC (curr_set)))
6116 change_p = true;
6117 if (hard_reg_set_subset_p (reg_class_contents[cl], live_hard_regs))
6118 IOR_HARD_REG_SET (potential_reload_hard_regs,
6119 reg_class_contents[cl]);
6121 else if (src_regno >= lra_constraint_new_regno_start
6122 && dst_regno < lra_constraint_new_regno_start
6123 && dst_regno >= FIRST_PSEUDO_REGISTER
6124 && reg_renumber[dst_regno] < 0
6125 && (cl = lra_get_allocno_class (src_regno)) != NO_REGS
6126 && usage_insns[dst_regno].check == curr_usage_insns_check
6127 && (next_usage_insns
6128 = usage_insns[dst_regno].insns) != NULL_RTX)
6130 if (ira_class_hard_regs_num[cl] <= max_small_class_regs_num)
6131 reloads_num++;
6132 update_reloads_num_p = false;
6133 /* 'original_pseudo <- reload_pseudo'. */
6134 if (! JUMP_P (curr_insn)
6135 && inherit_reload_reg (true, dst_regno, cl,
6136 curr_insn, next_usage_insns))
6137 change_p = true;
6138 /* Invalidate. */
6139 usage_insns[dst_regno].check = 0;
6140 if (hard_reg_set_subset_p (reg_class_contents[cl], live_hard_regs))
6141 IOR_HARD_REG_SET (potential_reload_hard_regs,
6142 reg_class_contents[cl]);
6144 else if (INSN_P (curr_insn))
6146 int iter;
6147 int max_uid = get_max_uid ();
6149 curr_id = lra_get_insn_recog_data (curr_insn);
6150 curr_static_id = curr_id->insn_static_data;
6151 to_inherit_num = 0;
6152 /* Process insn definitions. */
6153 for (iter = 0; iter < 2; iter++)
6154 for (reg = iter == 0 ? curr_id->regs : curr_static_id->hard_regs;
6155 reg != NULL;
6156 reg = reg->next)
6157 if (reg->type != OP_IN
6158 && (dst_regno = reg->regno) < lra_constraint_new_regno_start)
6160 if (dst_regno >= FIRST_PSEUDO_REGISTER && reg->type == OP_OUT
6161 && reg_renumber[dst_regno] < 0 && ! reg->subreg_p
6162 && usage_insns[dst_regno].check == curr_usage_insns_check
6163 && (next_usage_insns
6164 = usage_insns[dst_regno].insns) != NULL_RTX)
6166 struct lra_insn_reg *r;
6168 for (r = curr_id->regs; r != NULL; r = r->next)
6169 if (r->type != OP_OUT && r->regno == dst_regno)
6170 break;
6171 /* Don't do inheritance if the pseudo is also
6172 used in the insn. */
6173 if (r == NULL)
6174 /* We can not do inheritance right now
6175 because the current insn reg info (chain
6176 regs) can change after that. */
6177 add_to_inherit (dst_regno, next_usage_insns);
6179 /* We can not process one reg twice here because of
6180 usage_insns invalidation. */
6181 if ((dst_regno < FIRST_PSEUDO_REGISTER
6182 || reg_renumber[dst_regno] >= 0)
6183 && ! reg->subreg_p && reg->type != OP_IN)
6185 HARD_REG_SET s;
6187 if (split_if_necessary (dst_regno, reg->biggest_mode,
6188 potential_reload_hard_regs,
6189 false, curr_insn, max_uid))
6190 change_p = true;
6191 CLEAR_HARD_REG_SET (s);
6192 if (dst_regno < FIRST_PSEUDO_REGISTER)
6193 add_to_hard_reg_set (&s, reg->biggest_mode, dst_regno);
6194 else
6195 add_to_hard_reg_set (&s, PSEUDO_REGNO_MODE (dst_regno),
6196 reg_renumber[dst_regno]);
6197 AND_COMPL_HARD_REG_SET (live_hard_regs, s);
6199 /* We should invalidate potential inheritance or
6200 splitting for the current insn usages to the next
6201 usage insns (see code below) as the output pseudo
6202 prevents this. */
6203 if ((dst_regno >= FIRST_PSEUDO_REGISTER
6204 && reg_renumber[dst_regno] < 0)
6205 || (reg->type == OP_OUT && ! reg->subreg_p
6206 && (dst_regno < FIRST_PSEUDO_REGISTER
6207 || reg_renumber[dst_regno] >= 0)))
6209 /* Invalidate and mark definitions. */
6210 if (dst_regno >= FIRST_PSEUDO_REGISTER)
6211 usage_insns[dst_regno].check = -(int) INSN_UID (curr_insn);
6212 else
6214 nregs = hard_regno_nregs (dst_regno,
6215 reg->biggest_mode);
6216 for (i = 0; i < nregs; i++)
6217 usage_insns[dst_regno + i].check
6218 = -(int) INSN_UID (curr_insn);
6222 /* Process clobbered call regs. */
6223 if (curr_id->arg_hard_regs != NULL)
6224 for (i = 0; (dst_regno = curr_id->arg_hard_regs[i]) >= 0; i++)
6225 if (dst_regno >= FIRST_PSEUDO_REGISTER)
6226 usage_insns[dst_regno - FIRST_PSEUDO_REGISTER].check
6227 = -(int) INSN_UID (curr_insn);
6228 if (! JUMP_P (curr_insn))
6229 for (i = 0; i < to_inherit_num; i++)
6230 if (inherit_reload_reg (true, to_inherit[i].regno,
6231 ALL_REGS, curr_insn,
6232 to_inherit[i].insns))
6233 change_p = true;
6234 if (CALL_P (curr_insn))
6236 rtx cheap, pat, dest;
6237 rtx_insn *restore;
6238 int regno, hard_regno;
6240 calls_num++;
6241 if ((cheap = find_reg_note (curr_insn,
6242 REG_RETURNED, NULL_RTX)) != NULL_RTX
6243 && ((cheap = XEXP (cheap, 0)), true)
6244 && (regno = REGNO (cheap)) >= FIRST_PSEUDO_REGISTER
6245 && (hard_regno = reg_renumber[regno]) >= 0
6246 && usage_insns[regno].check == curr_usage_insns_check
6247 /* If there are pending saves/restores, the
6248 optimization is not worth. */
6249 && usage_insns[regno].calls_num == calls_num - 1
6250 && TEST_HARD_REG_BIT (call_used_reg_set, hard_regno))
6252 /* Restore the pseudo from the call result as
6253 REG_RETURNED note says that the pseudo value is
6254 in the call result and the pseudo is an argument
6255 of the call. */
6256 pat = PATTERN (curr_insn);
6257 if (GET_CODE (pat) == PARALLEL)
6258 pat = XVECEXP (pat, 0, 0);
6259 dest = SET_DEST (pat);
6260 /* For multiple return values dest is PARALLEL.
6261 Currently we handle only single return value case. */
6262 if (REG_P (dest))
6264 start_sequence ();
6265 emit_move_insn (cheap, copy_rtx (dest));
6266 restore = get_insns ();
6267 end_sequence ();
6268 lra_process_new_insns (curr_insn, NULL, restore,
6269 "Inserting call parameter restore");
6270 /* We don't need to save/restore of the pseudo from
6271 this call. */
6272 usage_insns[regno].calls_num = calls_num;
6273 bitmap_set_bit (&check_only_regs, regno);
6277 to_inherit_num = 0;
6278 /* Process insn usages. */
6279 for (iter = 0; iter < 2; iter++)
6280 for (reg = iter == 0 ? curr_id->regs : curr_static_id->hard_regs;
6281 reg != NULL;
6282 reg = reg->next)
6283 if ((reg->type != OP_OUT
6284 || (reg->type == OP_OUT && reg->subreg_p))
6285 && (src_regno = reg->regno) < lra_constraint_new_regno_start)
6287 if (src_regno >= FIRST_PSEUDO_REGISTER
6288 && reg_renumber[src_regno] < 0 && reg->type == OP_IN)
6290 if (usage_insns[src_regno].check == curr_usage_insns_check
6291 && (next_usage_insns
6292 = usage_insns[src_regno].insns) != NULL_RTX
6293 && NONDEBUG_INSN_P (curr_insn))
6294 add_to_inherit (src_regno, next_usage_insns);
6295 else if (usage_insns[src_regno].check
6296 != -(int) INSN_UID (curr_insn))
6297 /* Add usages but only if the reg is not set up
6298 in the same insn. */
6299 add_next_usage_insn (src_regno, curr_insn, reloads_num);
6301 else if (src_regno < FIRST_PSEUDO_REGISTER
6302 || reg_renumber[src_regno] >= 0)
6304 bool before_p;
6305 rtx_insn *use_insn = curr_insn;
6307 before_p = (JUMP_P (curr_insn)
6308 || (CALL_P (curr_insn) && reg->type == OP_IN));
6309 if (NONDEBUG_INSN_P (curr_insn)
6310 && (! JUMP_P (curr_insn) || reg->type == OP_IN)
6311 && split_if_necessary (src_regno, reg->biggest_mode,
6312 potential_reload_hard_regs,
6313 before_p, curr_insn, max_uid))
6315 if (reg->subreg_p)
6316 lra_risky_transformations_p = true;
6317 change_p = true;
6318 /* Invalidate. */
6319 usage_insns[src_regno].check = 0;
6320 if (before_p)
6321 use_insn = PREV_INSN (curr_insn);
6323 if (NONDEBUG_INSN_P (curr_insn))
6325 if (src_regno < FIRST_PSEUDO_REGISTER)
6326 add_to_hard_reg_set (&live_hard_regs,
6327 reg->biggest_mode, src_regno);
6328 else
6329 add_to_hard_reg_set (&live_hard_regs,
6330 PSEUDO_REGNO_MODE (src_regno),
6331 reg_renumber[src_regno]);
6333 add_next_usage_insn (src_regno, use_insn, reloads_num);
6336 /* Process used call regs. */
6337 if (curr_id->arg_hard_regs != NULL)
6338 for (i = 0; (src_regno = curr_id->arg_hard_regs[i]) >= 0; i++)
6339 if (src_regno < FIRST_PSEUDO_REGISTER)
6341 SET_HARD_REG_BIT (live_hard_regs, src_regno);
6342 add_next_usage_insn (src_regno, curr_insn, reloads_num);
6344 for (i = 0; i < to_inherit_num; i++)
6346 src_regno = to_inherit[i].regno;
6347 if (inherit_reload_reg (false, src_regno, ALL_REGS,
6348 curr_insn, to_inherit[i].insns))
6349 change_p = true;
6350 else
6351 setup_next_usage_insn (src_regno, curr_insn, reloads_num, false);
6354 if (update_reloads_num_p
6355 && NONDEBUG_INSN_P (curr_insn) && curr_set != NULL_RTX)
6357 int regno = -1;
6358 if ((REG_P (SET_DEST (curr_set))
6359 && (regno = REGNO (SET_DEST (curr_set))) >= lra_constraint_new_regno_start
6360 && reg_renumber[regno] < 0
6361 && (cl = lra_get_allocno_class (regno)) != NO_REGS)
6362 || (REG_P (SET_SRC (curr_set))
6363 && (regno = REGNO (SET_SRC (curr_set))) >= lra_constraint_new_regno_start
6364 && reg_renumber[regno] < 0
6365 && (cl = lra_get_allocno_class (regno)) != NO_REGS))
6367 if (ira_class_hard_regs_num[cl] <= max_small_class_regs_num)
6368 reloads_num++;
6369 if (hard_reg_set_subset_p (reg_class_contents[cl], live_hard_regs))
6370 IOR_HARD_REG_SET (potential_reload_hard_regs,
6371 reg_class_contents[cl]);
6374 if (NONDEBUG_INSN_P (curr_insn))
6376 int regno;
6378 /* Invalidate invariants with changed regs. */
6379 curr_id = lra_get_insn_recog_data (curr_insn);
6380 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
6381 if (reg->type != OP_IN)
6383 bitmap_set_bit (&invalid_invariant_regs, reg->regno);
6384 bitmap_set_bit (&invalid_invariant_regs,
6385 ORIGINAL_REGNO (regno_reg_rtx[reg->regno]));
6387 curr_static_id = curr_id->insn_static_data;
6388 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
6389 if (reg->type != OP_IN)
6390 bitmap_set_bit (&invalid_invariant_regs, reg->regno);
6391 if (curr_id->arg_hard_regs != NULL)
6392 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
6393 if (regno >= FIRST_PSEUDO_REGISTER)
6394 bitmap_set_bit (&invalid_invariant_regs,
6395 regno - FIRST_PSEUDO_REGISTER);
6397 /* We reached the start of the current basic block. */
6398 if (prev_insn == NULL_RTX || prev_insn == PREV_INSN (head)
6399 || BLOCK_FOR_INSN (prev_insn) != curr_bb)
6401 /* We reached the beginning of the current block -- do
6402 rest of spliting in the current BB. */
6403 to_process = df_get_live_in (curr_bb);
6404 if (BLOCK_FOR_INSN (head) != curr_bb)
6406 /* We are somewhere in the middle of EBB. */
6407 get_live_on_other_edges (EDGE_PRED (curr_bb, 0)->src,
6408 curr_bb, &temp_bitmap);
6409 to_process = &temp_bitmap;
6411 head_p = true;
6412 EXECUTE_IF_SET_IN_BITMAP (to_process, 0, j, bi)
6414 if ((int) j >= lra_constraint_new_regno_start)
6415 break;
6416 if (((int) j < FIRST_PSEUDO_REGISTER || reg_renumber[j] >= 0)
6417 && usage_insns[j].check == curr_usage_insns_check
6418 && (next_usage_insns = usage_insns[j].insns) != NULL_RTX)
6420 if (need_for_split_p (potential_reload_hard_regs, j))
6422 if (lra_dump_file != NULL && head_p)
6424 fprintf (lra_dump_file,
6425 " ----------------------------------\n");
6426 head_p = false;
6428 if (split_reg (false, j, bb_note (curr_bb),
6429 next_usage_insns))
6430 change_p = true;
6432 usage_insns[j].check = 0;
6437 return change_p;
6440 /* This value affects EBB forming. If probability of edge from EBB to
6441 a BB is not greater than the following value, we don't add the BB
6442 to EBB. */
6443 #define EBB_PROBABILITY_CUTOFF \
6444 ((REG_BR_PROB_BASE * LRA_INHERITANCE_EBB_PROBABILITY_CUTOFF) / 100)
6446 /* Current number of inheritance/split iteration. */
6447 int lra_inheritance_iter;
6449 /* Entry function for inheritance/split pass. */
6450 void
6451 lra_inheritance (void)
6453 int i;
6454 basic_block bb, start_bb;
6455 edge e;
6457 lra_inheritance_iter++;
6458 if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
6459 return;
6460 timevar_push (TV_LRA_INHERITANCE);
6461 if (lra_dump_file != NULL)
6462 fprintf (lra_dump_file, "\n********** Inheritance #%d: **********\n\n",
6463 lra_inheritance_iter);
6464 curr_usage_insns_check = 0;
6465 usage_insns = XNEWVEC (struct usage_insns, lra_constraint_new_regno_start);
6466 for (i = 0; i < lra_constraint_new_regno_start; i++)
6467 usage_insns[i].check = 0;
6468 bitmap_initialize (&check_only_regs, &reg_obstack);
6469 bitmap_initialize (&invalid_invariant_regs, &reg_obstack);
6470 bitmap_initialize (&live_regs, &reg_obstack);
6471 bitmap_initialize (&temp_bitmap, &reg_obstack);
6472 bitmap_initialize (&ebb_global_regs, &reg_obstack);
6473 FOR_EACH_BB_FN (bb, cfun)
6475 start_bb = bb;
6476 if (lra_dump_file != NULL)
6477 fprintf (lra_dump_file, "EBB");
6478 /* Form a EBB starting with BB. */
6479 bitmap_clear (&ebb_global_regs);
6480 bitmap_ior_into (&ebb_global_regs, df_get_live_in (bb));
6481 for (;;)
6483 if (lra_dump_file != NULL)
6484 fprintf (lra_dump_file, " %d", bb->index);
6485 if (bb->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
6486 || LABEL_P (BB_HEAD (bb->next_bb)))
6487 break;
6488 e = find_fallthru_edge (bb->succs);
6489 if (! e)
6490 break;
6491 if (e->probability.initialized_p ()
6492 && e->probability.to_reg_br_prob_base () < EBB_PROBABILITY_CUTOFF)
6493 break;
6494 bb = bb->next_bb;
6496 bitmap_ior_into (&ebb_global_regs, df_get_live_out (bb));
6497 if (lra_dump_file != NULL)
6498 fprintf (lra_dump_file, "\n");
6499 if (inherit_in_ebb (BB_HEAD (start_bb), BB_END (bb)))
6500 /* Remember that the EBB head and tail can change in
6501 inherit_in_ebb. */
6502 update_ebb_live_info (BB_HEAD (start_bb), BB_END (bb));
6504 bitmap_clear (&ebb_global_regs);
6505 bitmap_clear (&temp_bitmap);
6506 bitmap_clear (&live_regs);
6507 bitmap_clear (&invalid_invariant_regs);
6508 bitmap_clear (&check_only_regs);
6509 free (usage_insns);
6511 timevar_pop (TV_LRA_INHERITANCE);
6516 /* This page contains code to undo failed inheritance/split
6517 transformations. */
6519 /* Current number of iteration undoing inheritance/split. */
6520 int lra_undo_inheritance_iter;
6522 /* Fix BB live info LIVE after removing pseudos created on pass doing
6523 inheritance/split which are REMOVED_PSEUDOS. */
6524 static void
6525 fix_bb_live_info (bitmap live, bitmap removed_pseudos)
6527 unsigned int regno;
6528 bitmap_iterator bi;
6530 EXECUTE_IF_SET_IN_BITMAP (removed_pseudos, 0, regno, bi)
6531 if (bitmap_clear_bit (live, regno)
6532 && REG_P (lra_reg_info[regno].restore_rtx))
6533 bitmap_set_bit (live, REGNO (lra_reg_info[regno].restore_rtx));
6536 /* Return regno of the (subreg of) REG. Otherwise, return a negative
6537 number. */
6538 static int
6539 get_regno (rtx reg)
6541 if (GET_CODE (reg) == SUBREG)
6542 reg = SUBREG_REG (reg);
6543 if (REG_P (reg))
6544 return REGNO (reg);
6545 return -1;
6548 /* Delete a move INSN with destination reg DREGNO and a previous
6549 clobber insn with the same regno. The inheritance/split code can
6550 generate moves with preceding clobber and when we delete such moves
6551 we should delete the clobber insn too to keep the correct life
6552 info. */
6553 static void
6554 delete_move_and_clobber (rtx_insn *insn, int dregno)
6556 rtx_insn *prev_insn = PREV_INSN (insn);
6558 lra_set_insn_deleted (insn);
6559 lra_assert (dregno >= 0);
6560 if (prev_insn != NULL && NONDEBUG_INSN_P (prev_insn)
6561 && GET_CODE (PATTERN (prev_insn)) == CLOBBER
6562 && dregno == get_regno (XEXP (PATTERN (prev_insn), 0)))
6563 lra_set_insn_deleted (prev_insn);
6566 /* Remove inheritance/split pseudos which are in REMOVE_PSEUDOS and
6567 return true if we did any change. The undo transformations for
6568 inheritance looks like
6569 i <- i2
6570 p <- i => p <- i2
6571 or removing
6572 p <- i, i <- p, and i <- i3
6573 where p is original pseudo from which inheritance pseudo i was
6574 created, i and i3 are removed inheritance pseudos, i2 is another
6575 not removed inheritance pseudo. All split pseudos or other
6576 occurrences of removed inheritance pseudos are changed on the
6577 corresponding original pseudos.
6579 The function also schedules insns changed and created during
6580 inheritance/split pass for processing by the subsequent constraint
6581 pass. */
6582 static bool
6583 remove_inheritance_pseudos (bitmap remove_pseudos)
6585 basic_block bb;
6586 int regno, sregno, prev_sregno, dregno;
6587 rtx restore_rtx;
6588 rtx set, prev_set;
6589 rtx_insn *prev_insn;
6590 bool change_p, done_p;
6592 change_p = ! bitmap_empty_p (remove_pseudos);
6593 /* We can not finish the function right away if CHANGE_P is true
6594 because we need to marks insns affected by previous
6595 inheritance/split pass for processing by the subsequent
6596 constraint pass. */
6597 FOR_EACH_BB_FN (bb, cfun)
6599 fix_bb_live_info (df_get_live_in (bb), remove_pseudos);
6600 fix_bb_live_info (df_get_live_out (bb), remove_pseudos);
6601 FOR_BB_INSNS_REVERSE (bb, curr_insn)
6603 if (! INSN_P (curr_insn))
6604 continue;
6605 done_p = false;
6606 sregno = dregno = -1;
6607 if (change_p && NONDEBUG_INSN_P (curr_insn)
6608 && (set = single_set (curr_insn)) != NULL_RTX)
6610 dregno = get_regno (SET_DEST (set));
6611 sregno = get_regno (SET_SRC (set));
6614 if (sregno >= 0 && dregno >= 0)
6616 if (bitmap_bit_p (remove_pseudos, dregno)
6617 && ! REG_P (lra_reg_info[dregno].restore_rtx))
6619 /* invariant inheritance pseudo <- original pseudo */
6620 if (lra_dump_file != NULL)
6622 fprintf (lra_dump_file, " Removing invariant inheritance:\n");
6623 dump_insn_slim (lra_dump_file, curr_insn);
6624 fprintf (lra_dump_file, "\n");
6626 delete_move_and_clobber (curr_insn, dregno);
6627 done_p = true;
6629 else if (bitmap_bit_p (remove_pseudos, sregno)
6630 && ! REG_P (lra_reg_info[sregno].restore_rtx))
6632 /* reload pseudo <- invariant inheritance pseudo */
6633 start_sequence ();
6634 /* We can not just change the source. It might be
6635 an insn different from the move. */
6636 emit_insn (lra_reg_info[sregno].restore_rtx);
6637 rtx_insn *new_insns = get_insns ();
6638 end_sequence ();
6639 lra_assert (single_set (new_insns) != NULL
6640 && SET_DEST (set) == SET_DEST (single_set (new_insns)));
6641 lra_process_new_insns (curr_insn, NULL, new_insns,
6642 "Changing reload<-invariant inheritance");
6643 delete_move_and_clobber (curr_insn, dregno);
6644 done_p = true;
6646 else if ((bitmap_bit_p (remove_pseudos, sregno)
6647 && (get_regno (lra_reg_info[sregno].restore_rtx) == dregno
6648 || (bitmap_bit_p (remove_pseudos, dregno)
6649 && get_regno (lra_reg_info[sregno].restore_rtx) >= 0
6650 && (get_regno (lra_reg_info[sregno].restore_rtx)
6651 == get_regno (lra_reg_info[dregno].restore_rtx)))))
6652 || (bitmap_bit_p (remove_pseudos, dregno)
6653 && get_regno (lra_reg_info[dregno].restore_rtx) == sregno))
6654 /* One of the following cases:
6655 original <- removed inheritance pseudo
6656 removed inherit pseudo <- another removed inherit pseudo
6657 removed inherit pseudo <- original pseudo
6659 removed_split_pseudo <- original_reg
6660 original_reg <- removed_split_pseudo */
6662 if (lra_dump_file != NULL)
6664 fprintf (lra_dump_file, " Removing %s:\n",
6665 bitmap_bit_p (&lra_split_regs, sregno)
6666 || bitmap_bit_p (&lra_split_regs, dregno)
6667 ? "split" : "inheritance");
6668 dump_insn_slim (lra_dump_file, curr_insn);
6670 delete_move_and_clobber (curr_insn, dregno);
6671 done_p = true;
6673 else if (bitmap_bit_p (remove_pseudos, sregno)
6674 && bitmap_bit_p (&lra_inheritance_pseudos, sregno))
6676 /* Search the following pattern:
6677 inherit_or_split_pseudo1 <- inherit_or_split_pseudo2
6678 original_pseudo <- inherit_or_split_pseudo1
6679 where the 2nd insn is the current insn and
6680 inherit_or_split_pseudo2 is not removed. If it is found,
6681 change the current insn onto:
6682 original_pseudo <- inherit_or_split_pseudo2. */
6683 for (prev_insn = PREV_INSN (curr_insn);
6684 prev_insn != NULL_RTX && ! NONDEBUG_INSN_P (prev_insn);
6685 prev_insn = PREV_INSN (prev_insn))
6687 if (prev_insn != NULL_RTX && BLOCK_FOR_INSN (prev_insn) == bb
6688 && (prev_set = single_set (prev_insn)) != NULL_RTX
6689 /* There should be no subregs in insn we are
6690 searching because only the original reg might
6691 be in subreg when we changed the mode of
6692 load/store for splitting. */
6693 && REG_P (SET_DEST (prev_set))
6694 && REG_P (SET_SRC (prev_set))
6695 && (int) REGNO (SET_DEST (prev_set)) == sregno
6696 && ((prev_sregno = REGNO (SET_SRC (prev_set)))
6697 >= FIRST_PSEUDO_REGISTER)
6698 && (lra_reg_info[prev_sregno].restore_rtx == NULL_RTX
6700 /* As we consider chain of inheritance or
6701 splitting described in above comment we should
6702 check that sregno and prev_sregno were
6703 inheritance/split pseudos created from the
6704 same original regno. */
6705 (get_regno (lra_reg_info[sregno].restore_rtx) >= 0
6706 && (get_regno (lra_reg_info[sregno].restore_rtx)
6707 == get_regno (lra_reg_info[prev_sregno].restore_rtx))))
6708 && ! bitmap_bit_p (remove_pseudos, prev_sregno))
6710 lra_assert (GET_MODE (SET_SRC (prev_set))
6711 == GET_MODE (regno_reg_rtx[sregno]));
6712 if (GET_CODE (SET_SRC (set)) == SUBREG)
6713 SUBREG_REG (SET_SRC (set)) = SET_SRC (prev_set);
6714 else
6715 SET_SRC (set) = SET_SRC (prev_set);
6716 /* As we are finishing with processing the insn
6717 here, check the destination too as it might
6718 inheritance pseudo for another pseudo. */
6719 if (bitmap_bit_p (remove_pseudos, dregno)
6720 && bitmap_bit_p (&lra_inheritance_pseudos, dregno)
6721 && (restore_rtx
6722 = lra_reg_info[dregno].restore_rtx) != NULL_RTX)
6724 if (GET_CODE (SET_DEST (set)) == SUBREG)
6725 SUBREG_REG (SET_DEST (set)) = restore_rtx;
6726 else
6727 SET_DEST (set) = restore_rtx;
6729 lra_push_insn_and_update_insn_regno_info (curr_insn);
6730 lra_set_used_insn_alternative_by_uid
6731 (INSN_UID (curr_insn), -1);
6732 done_p = true;
6733 if (lra_dump_file != NULL)
6735 fprintf (lra_dump_file, " Change reload insn:\n");
6736 dump_insn_slim (lra_dump_file, curr_insn);
6741 if (! done_p)
6743 struct lra_insn_reg *reg;
6744 bool restored_regs_p = false;
6745 bool kept_regs_p = false;
6747 curr_id = lra_get_insn_recog_data (curr_insn);
6748 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
6750 regno = reg->regno;
6751 restore_rtx = lra_reg_info[regno].restore_rtx;
6752 if (restore_rtx != NULL_RTX)
6754 if (change_p && bitmap_bit_p (remove_pseudos, regno))
6756 lra_substitute_pseudo_within_insn
6757 (curr_insn, regno, restore_rtx, false);
6758 restored_regs_p = true;
6760 else
6761 kept_regs_p = true;
6764 if (NONDEBUG_INSN_P (curr_insn) && kept_regs_p)
6766 /* The instruction has changed since the previous
6767 constraints pass. */
6768 lra_push_insn_and_update_insn_regno_info (curr_insn);
6769 lra_set_used_insn_alternative_by_uid
6770 (INSN_UID (curr_insn), -1);
6772 else if (restored_regs_p)
6773 /* The instruction has been restored to the form that
6774 it had during the previous constraints pass. */
6775 lra_update_insn_regno_info (curr_insn);
6776 if (restored_regs_p && lra_dump_file != NULL)
6778 fprintf (lra_dump_file, " Insn after restoring regs:\n");
6779 dump_insn_slim (lra_dump_file, curr_insn);
6784 return change_p;
6787 /* If optional reload pseudos failed to get a hard register or was not
6788 inherited, it is better to remove optional reloads. We do this
6789 transformation after undoing inheritance to figure out necessity to
6790 remove optional reloads easier. Return true if we do any
6791 change. */
6792 static bool
6793 undo_optional_reloads (void)
6795 bool change_p, keep_p;
6796 unsigned int regno, uid;
6797 bitmap_iterator bi, bi2;
6798 rtx_insn *insn;
6799 rtx set, src, dest;
6800 auto_bitmap removed_optional_reload_pseudos (&reg_obstack);
6802 bitmap_copy (removed_optional_reload_pseudos, &lra_optional_reload_pseudos);
6803 EXECUTE_IF_SET_IN_BITMAP (&lra_optional_reload_pseudos, 0, regno, bi)
6805 keep_p = false;
6806 /* Keep optional reloads from previous subpasses. */
6807 if (lra_reg_info[regno].restore_rtx == NULL_RTX
6808 /* If the original pseudo changed its allocation, just
6809 removing the optional pseudo is dangerous as the original
6810 pseudo will have longer live range. */
6811 || reg_renumber[REGNO (lra_reg_info[regno].restore_rtx)] >= 0)
6812 keep_p = true;
6813 else if (reg_renumber[regno] >= 0)
6814 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi2)
6816 insn = lra_insn_recog_data[uid]->insn;
6817 if ((set = single_set (insn)) == NULL_RTX)
6818 continue;
6819 src = SET_SRC (set);
6820 dest = SET_DEST (set);
6821 if (! REG_P (src) || ! REG_P (dest))
6822 continue;
6823 if (REGNO (dest) == regno
6824 /* Ignore insn for optional reloads itself. */
6825 && REGNO (lra_reg_info[regno].restore_rtx) != REGNO (src)
6826 /* Check only inheritance on last inheritance pass. */
6827 && (int) REGNO (src) >= new_regno_start
6828 /* Check that the optional reload was inherited. */
6829 && bitmap_bit_p (&lra_inheritance_pseudos, REGNO (src)))
6831 keep_p = true;
6832 break;
6835 if (keep_p)
6837 bitmap_clear_bit (removed_optional_reload_pseudos, regno);
6838 if (lra_dump_file != NULL)
6839 fprintf (lra_dump_file, "Keep optional reload reg %d\n", regno);
6842 change_p = ! bitmap_empty_p (removed_optional_reload_pseudos);
6843 auto_bitmap insn_bitmap (&reg_obstack);
6844 EXECUTE_IF_SET_IN_BITMAP (removed_optional_reload_pseudos, 0, regno, bi)
6846 if (lra_dump_file != NULL)
6847 fprintf (lra_dump_file, "Remove optional reload reg %d\n", regno);
6848 bitmap_copy (insn_bitmap, &lra_reg_info[regno].insn_bitmap);
6849 EXECUTE_IF_SET_IN_BITMAP (insn_bitmap, 0, uid, bi2)
6851 insn = lra_insn_recog_data[uid]->insn;
6852 if ((set = single_set (insn)) != NULL_RTX)
6854 src = SET_SRC (set);
6855 dest = SET_DEST (set);
6856 if (REG_P (src) && REG_P (dest)
6857 && ((REGNO (src) == regno
6858 && (REGNO (lra_reg_info[regno].restore_rtx)
6859 == REGNO (dest)))
6860 || (REGNO (dest) == regno
6861 && (REGNO (lra_reg_info[regno].restore_rtx)
6862 == REGNO (src)))))
6864 if (lra_dump_file != NULL)
6866 fprintf (lra_dump_file, " Deleting move %u\n",
6867 INSN_UID (insn));
6868 dump_insn_slim (lra_dump_file, insn);
6870 delete_move_and_clobber (insn, REGNO (dest));
6871 continue;
6873 /* We should not worry about generation memory-memory
6874 moves here as if the corresponding inheritance did
6875 not work (inheritance pseudo did not get a hard reg),
6876 we remove the inheritance pseudo and the optional
6877 reload. */
6879 lra_substitute_pseudo_within_insn
6880 (insn, regno, lra_reg_info[regno].restore_rtx, false);
6881 lra_update_insn_regno_info (insn);
6882 if (lra_dump_file != NULL)
6884 fprintf (lra_dump_file,
6885 " Restoring original insn:\n");
6886 dump_insn_slim (lra_dump_file, insn);
6890 /* Clear restore_regnos. */
6891 EXECUTE_IF_SET_IN_BITMAP (&lra_optional_reload_pseudos, 0, regno, bi)
6892 lra_reg_info[regno].restore_rtx = NULL_RTX;
6893 return change_p;
6896 /* Entry function for undoing inheritance/split transformation. Return true
6897 if we did any RTL change in this pass. */
6898 bool
6899 lra_undo_inheritance (void)
6901 unsigned int regno;
6902 int hard_regno;
6903 int n_all_inherit, n_inherit, n_all_split, n_split;
6904 rtx restore_rtx;
6905 bitmap_iterator bi;
6906 bool change_p;
6908 lra_undo_inheritance_iter++;
6909 if (lra_undo_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
6910 return false;
6911 if (lra_dump_file != NULL)
6912 fprintf (lra_dump_file,
6913 "\n********** Undoing inheritance #%d: **********\n\n",
6914 lra_undo_inheritance_iter);
6915 auto_bitmap remove_pseudos (&reg_obstack);
6916 n_inherit = n_all_inherit = 0;
6917 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, regno, bi)
6918 if (lra_reg_info[regno].restore_rtx != NULL_RTX)
6920 n_all_inherit++;
6921 if (reg_renumber[regno] < 0
6922 /* If the original pseudo changed its allocation, just
6923 removing inheritance is dangerous as for changing
6924 allocation we used shorter live-ranges. */
6925 && (! REG_P (lra_reg_info[regno].restore_rtx)
6926 || reg_renumber[REGNO (lra_reg_info[regno].restore_rtx)] < 0))
6927 bitmap_set_bit (remove_pseudos, regno);
6928 else
6929 n_inherit++;
6931 if (lra_dump_file != NULL && n_all_inherit != 0)
6932 fprintf (lra_dump_file, "Inherit %d out of %d (%.2f%%)\n",
6933 n_inherit, n_all_inherit,
6934 (double) n_inherit / n_all_inherit * 100);
6935 n_split = n_all_split = 0;
6936 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, regno, bi)
6937 if ((restore_rtx = lra_reg_info[regno].restore_rtx) != NULL_RTX)
6939 int restore_regno = REGNO (restore_rtx);
6941 n_all_split++;
6942 hard_regno = (restore_regno >= FIRST_PSEUDO_REGISTER
6943 ? reg_renumber[restore_regno] : restore_regno);
6944 if (hard_regno < 0 || reg_renumber[regno] == hard_regno)
6945 bitmap_set_bit (remove_pseudos, regno);
6946 else
6948 n_split++;
6949 if (lra_dump_file != NULL)
6950 fprintf (lra_dump_file, " Keep split r%d (orig=r%d)\n",
6951 regno, restore_regno);
6954 if (lra_dump_file != NULL && n_all_split != 0)
6955 fprintf (lra_dump_file, "Split %d out of %d (%.2f%%)\n",
6956 n_split, n_all_split,
6957 (double) n_split / n_all_split * 100);
6958 change_p = remove_inheritance_pseudos (remove_pseudos);
6959 /* Clear restore_regnos. */
6960 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, regno, bi)
6961 lra_reg_info[regno].restore_rtx = NULL_RTX;
6962 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, regno, bi)
6963 lra_reg_info[regno].restore_rtx = NULL_RTX;
6964 change_p = undo_optional_reloads () || change_p;
6965 return change_p;