2012-11-28 Vladimir Makarov <vmakarov@redhat.com>
[official-gcc.git] / gcc / lra-constraints.c
blob128401f1b92aa19d6a6d7a85bdd4c1f75712f60c
1 /* Code for RTL transformations to satisfy insn constraints.
2 Copyright (C) 2010, 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
23 /* This file contains code for 3 passes: constraint pass,
24 inheritance/split pass, and pass for undoing failed inheritance and
25 split.
27 The major goal of constraint pass is to transform RTL to satisfy
28 insn and address constraints by:
29 o choosing insn alternatives;
30 o generating *reload insns* (or reloads in brief) and *reload
31 pseudos* which will get necessary hard registers later;
32 o substituting pseudos with equivalent values and removing the
33 instructions that initialized those pseudos.
35 The constraint pass has biggest and most complicated code in LRA.
36 There are a lot of important details like:
37 o reuse of input reload pseudos to simplify reload pseudo
38 allocations;
39 o some heuristics to choose insn alternative to improve the
40 inheritance;
41 o early clobbers etc.
43 The pass is mimicking former reload pass in alternative choosing
44 because the reload pass is oriented to current machine description
45 model. It might be changed if the machine description model is
46 changed.
48 There is special code for preventing all LRA and this pass cycling
49 in case of bugs.
51 On the first iteration of the pass we process every instruction and
52 choose an alternative for each one. On subsequent iterations we try
53 to avoid reprocessing instructions if we can be sure that the old
54 choice is still valid.
56 The inheritance/spilt pass is to transform code to achieve
57 ineheritance and live range splitting. It is done on backward
58 traversal of EBBs.
60 The inheritance optimization goal is to reuse values in hard
61 registers. There is analogous optimization in old reload pass. The
62 inheritance is achieved by following transformation:
64 reload_p1 <- p reload_p1 <- p
65 ... new_p <- reload_p1
66 ... => ...
67 reload_p2 <- p reload_p2 <- new_p
69 where p is spilled and not changed between the insns. Reload_p1 is
70 also called *original pseudo* and new_p is called *inheritance
71 pseudo*.
73 The subsequent assignment pass will try to assign the same (or
74 another if it is not possible) hard register to new_p as to
75 reload_p1 or reload_p2.
77 If the assignment pass fails to assign a hard register to new_p,
78 this file will undo the inheritance and restore the original code.
79 This is because implementing the above sequence with a spilled
80 new_p would make the code much worse. The inheritance is done in
81 EBB scope. The above is just a simplified example to get an idea
82 of the inheritance as the inheritance is also done for non-reload
83 insns.
85 Splitting (transformation) is also done in EBB scope on the same
86 pass as the inheritance:
88 r <- ... or ... <- r r <- ... or ... <- r
89 ... s <- r (new insn -- save)
90 ... =>
91 ... r <- s (new insn -- restore)
92 ... <- r ... <- r
94 The *split pseudo* s is assigned to the hard register of the
95 original pseudo or hard register r.
97 Splitting is done:
98 o In EBBs with high register pressure for global pseudos (living
99 in at least 2 BBs) and assigned to hard registers when there
100 are more one reloads needing the hard registers;
101 o for pseudos needing save/restore code around calls.
103 If the split pseudo still has the same hard register as the
104 original pseudo after the subsequent assignment pass or the
105 original pseudo was split, the opposite transformation is done on
106 the same pass for undoing inheritance. */
108 #undef REG_OK_STRICT
110 #include "config.h"
111 #include "system.h"
112 #include "coretypes.h"
113 #include "tm.h"
114 #include "hard-reg-set.h"
115 #include "rtl.h"
116 #include "tm_p.h"
117 #include "regs.h"
118 #include "insn-config.h"
119 #include "insn-codes.h"
120 #include "recog.h"
121 #include "output.h"
122 #include "addresses.h"
123 #include "target.h"
124 #include "function.h"
125 #include "expr.h"
126 #include "basic-block.h"
127 #include "except.h"
128 #include "optabs.h"
129 #include "df.h"
130 #include "ira.h"
131 #include "rtl-error.h"
132 #include "lra-int.h"
134 /* Value of LRA_CURR_RELOAD_NUM at the beginning of BB of the current
135 insn. Remember that LRA_CURR_RELOAD_NUM is the number of emitted
136 reload insns. */
137 static int bb_reload_num;
139 /* The current insn being processed and corresponding its data (basic
140 block, the insn data, the insn static data, and the mode of each
141 operand). */
142 static rtx curr_insn;
143 static basic_block curr_bb;
144 static lra_insn_recog_data_t curr_id;
145 static struct lra_static_insn_data *curr_static_id;
146 static enum machine_mode curr_operand_mode[MAX_RECOG_OPERANDS];
150 /* Start numbers for new registers and insns at the current constraints
151 pass start. */
152 static int new_regno_start;
153 static int new_insn_uid_start;
155 /* If LOC is nonnull, strip any outer subreg from it. */
156 static inline rtx *
157 strip_subreg (rtx *loc)
159 return loc && GET_CODE (*loc) == SUBREG ? &SUBREG_REG (*loc) : loc;
162 /* Return hard regno of REGNO or if it is was not assigned to a hard
163 register, use a hard register from its allocno class. */
164 static int
165 get_try_hard_regno (int regno)
167 int hard_regno;
168 enum reg_class rclass;
170 if ((hard_regno = regno) >= FIRST_PSEUDO_REGISTER)
171 hard_regno = lra_get_regno_hard_regno (regno);
172 if (hard_regno >= 0)
173 return hard_regno;
174 rclass = lra_get_allocno_class (regno);
175 if (rclass == NO_REGS)
176 return -1;
177 return ira_class_hard_regs[rclass][0];
180 /* Return final hard regno (plus offset) which will be after
181 elimination. We do this for matching constraints because the final
182 hard regno could have a different class. */
183 static int
184 get_final_hard_regno (int hard_regno, int offset)
186 if (hard_regno < 0)
187 return hard_regno;
188 hard_regno = lra_get_elimination_hard_regno (hard_regno);
189 return hard_regno + offset;
192 /* Return hard regno of X after removing subreg and making
193 elimination. If X is not a register or subreg of register, return
194 -1. For pseudo use its assignment. */
195 static int
196 get_hard_regno (rtx x)
198 rtx reg;
199 int offset, hard_regno;
201 reg = x;
202 if (GET_CODE (x) == SUBREG)
203 reg = SUBREG_REG (x);
204 if (! REG_P (reg))
205 return -1;
206 if ((hard_regno = REGNO (reg)) >= FIRST_PSEUDO_REGISTER)
207 hard_regno = lra_get_regno_hard_regno (hard_regno);
208 if (hard_regno < 0)
209 return -1;
210 offset = 0;
211 if (GET_CODE (x) == SUBREG)
212 offset += subreg_regno_offset (hard_regno, GET_MODE (reg),
213 SUBREG_BYTE (x), GET_MODE (x));
214 return get_final_hard_regno (hard_regno, offset);
217 /* If REGNO is a hard register or has been allocated a hard register,
218 return the class of that register. If REGNO is a reload pseudo
219 created by the current constraints pass, return its allocno class.
220 Return NO_REGS otherwise. */
221 static enum reg_class
222 get_reg_class (int regno)
224 int hard_regno;
226 if ((hard_regno = regno) >= FIRST_PSEUDO_REGISTER)
227 hard_regno = lra_get_regno_hard_regno (regno);
228 if (hard_regno >= 0)
230 hard_regno = get_final_hard_regno (hard_regno, 0);
231 return REGNO_REG_CLASS (hard_regno);
233 if (regno >= new_regno_start)
234 return lra_get_allocno_class (regno);
235 return NO_REGS;
238 /* Return true if REG satisfies (or will satisfy) reg class constraint
239 CL. Use elimination first if REG is a hard register. If REG is a
240 reload pseudo created by this constraints pass, assume that it will
241 be allocated a hard register from its allocno class, but allow that
242 class to be narrowed to CL if it is currently a superset of CL.
244 If NEW_CLASS is nonnull, set *NEW_CLASS to the new allocno class of
245 REGNO (reg), or NO_REGS if no change in its class was needed. */
246 static bool
247 in_class_p (rtx reg, enum reg_class cl, enum reg_class *new_class)
249 enum reg_class rclass, common_class;
250 enum machine_mode reg_mode;
251 int class_size, hard_regno, nregs, i, j;
252 int regno = REGNO (reg);
254 if (new_class != NULL)
255 *new_class = NO_REGS;
256 if (regno < FIRST_PSEUDO_REGISTER)
258 rtx final_reg = reg;
259 rtx *final_loc = &final_reg;
261 lra_eliminate_reg_if_possible (final_loc);
262 return TEST_HARD_REG_BIT (reg_class_contents[cl], REGNO (*final_loc));
264 reg_mode = GET_MODE (reg);
265 rclass = get_reg_class (regno);
266 if (regno < new_regno_start
267 /* Do not allow the constraints for reload instructions to
268 influence the classes of new pseudos. These reloads are
269 typically moves that have many alternatives, and restricting
270 reload pseudos for one alternative may lead to situations
271 where other reload pseudos are no longer allocatable. */
272 || INSN_UID (curr_insn) >= new_insn_uid_start)
273 /* When we don't know what class will be used finally for reload
274 pseudos, we use ALL_REGS. */
275 return ((regno >= new_regno_start && rclass == ALL_REGS)
276 || (rclass != NO_REGS && ira_class_subset_p[rclass][cl]
277 && ! hard_reg_set_subset_p (reg_class_contents[cl],
278 lra_no_alloc_regs)));
279 else
281 common_class = ira_reg_class_subset[rclass][cl];
282 if (new_class != NULL)
283 *new_class = common_class;
284 if (hard_reg_set_subset_p (reg_class_contents[common_class],
285 lra_no_alloc_regs))
286 return false;
287 /* Check that there are enough allocatable regs. */
288 class_size = ira_class_hard_regs_num[common_class];
289 for (i = 0; i < class_size; i++)
291 hard_regno = ira_class_hard_regs[common_class][i];
292 nregs = hard_regno_nregs[hard_regno][reg_mode];
293 if (nregs == 1)
294 return true;
295 for (j = 0; j < nregs; j++)
296 if (TEST_HARD_REG_BIT (lra_no_alloc_regs, hard_regno + j)
297 || ! TEST_HARD_REG_BIT (reg_class_contents[common_class],
298 hard_regno + j))
299 break;
300 if (j >= nregs)
301 return true;
303 return false;
307 /* Return true if REGNO satisfies a memory constraint. */
308 static bool
309 in_mem_p (int regno)
311 return get_reg_class (regno) == NO_REGS;
314 /* If we have decided to substitute X with another value, return that
315 value, otherwise return X. */
316 static rtx
317 get_equiv_substitution (rtx x)
319 int regno;
320 rtx res;
322 if (! REG_P (x) || (regno = REGNO (x)) < FIRST_PSEUDO_REGISTER
323 || ! ira_reg_equiv[regno].defined_p
324 || ! ira_reg_equiv[regno].profitable_p
325 || lra_get_regno_hard_regno (regno) >= 0)
326 return x;
327 if ((res = ira_reg_equiv[regno].memory) != NULL_RTX)
328 return res;
329 if ((res = ira_reg_equiv[regno].constant) != NULL_RTX)
330 return res;
331 if ((res = ira_reg_equiv[regno].invariant) != NULL_RTX)
332 return res;
333 gcc_unreachable ();
336 /* Set up curr_operand_mode. */
337 static void
338 init_curr_operand_mode (void)
340 int nop = curr_static_id->n_operands;
341 for (int i = 0; i < nop; i++)
343 enum machine_mode mode = GET_MODE (*curr_id->operand_loc[i]);
344 if (mode == VOIDmode)
346 /* The .md mode for address operands is the mode of the
347 addressed value rather than the mode of the address itself. */
348 if (curr_id->icode >= 0 && curr_static_id->operand[i].is_address)
349 mode = Pmode;
350 else
351 mode = curr_static_id->operand[i].mode;
353 curr_operand_mode[i] = mode;
359 /* The page contains code to reuse input reloads. */
361 /* Structure describes input reload of the current insns. */
362 struct input_reload
364 /* Reloaded value. */
365 rtx input;
366 /* Reload pseudo used. */
367 rtx reg;
370 /* The number of elements in the following array. */
371 static int curr_insn_input_reloads_num;
372 /* Array containing info about input reloads. It is used to find the
373 same input reload and reuse the reload pseudo in this case. */
374 static struct input_reload curr_insn_input_reloads[LRA_MAX_INSN_RELOADS];
376 /* Initiate data concerning reuse of input reloads for the current
377 insn. */
378 static void
379 init_curr_insn_input_reloads (void)
381 curr_insn_input_reloads_num = 0;
384 /* Change class of pseudo REGNO to NEW_CLASS. Print info about it
385 using TITLE. Output a new line if NL_P. */
386 static void
387 change_class (int regno, enum reg_class new_class,
388 const char *title, bool nl_p)
390 lra_assert (regno >= FIRST_PSEUDO_REGISTER);
391 if (lra_dump_file != NULL)
392 fprintf (lra_dump_file, "%s to class %s for r%d",
393 title, reg_class_names[new_class], regno);
394 setup_reg_classes (regno, new_class, NO_REGS, new_class);
395 if (lra_dump_file != NULL && nl_p)
396 fprintf (lra_dump_file, "\n");
399 /* Create a new pseudo using MODE, RCLASS, ORIGINAL or reuse already
400 created input reload pseudo (only if TYPE is not OP_OUT). The
401 result pseudo is returned through RESULT_REG. Return TRUE if we
402 created a new pseudo, FALSE if we reused the already created input
403 reload pseudo. Use TITLE to describe new registers for debug
404 purposes. */
405 static bool
406 get_reload_reg (enum op_type type, enum machine_mode mode, rtx original,
407 enum reg_class rclass, const char *title, rtx *result_reg)
409 int i, regno;
410 enum reg_class new_class;
412 if (type == OP_OUT)
414 *result_reg
415 = lra_create_new_reg_with_unique_value (mode, original, rclass, title);
416 return true;
418 for (i = 0; i < curr_insn_input_reloads_num; i++)
419 if (rtx_equal_p (curr_insn_input_reloads[i].input, original)
420 && in_class_p (curr_insn_input_reloads[i].reg, rclass, &new_class))
422 lra_assert (! side_effects_p (original));
423 *result_reg = curr_insn_input_reloads[i].reg;
424 regno = REGNO (*result_reg);
425 if (lra_dump_file != NULL)
427 fprintf (lra_dump_file, " Reuse r%d for reload ", regno);
428 dump_value_slim (lra_dump_file, original, 1);
430 if (new_class != lra_get_allocno_class (regno))
431 change_class (regno, new_class, ", change", false);
432 if (lra_dump_file != NULL)
433 fprintf (lra_dump_file, "\n");
434 return false;
436 *result_reg = lra_create_new_reg (mode, original, rclass, title);
437 lra_assert (curr_insn_input_reloads_num < LRA_MAX_INSN_RELOADS);
438 curr_insn_input_reloads[curr_insn_input_reloads_num].input = original;
439 curr_insn_input_reloads[curr_insn_input_reloads_num++].reg = *result_reg;
440 return true;
445 /* The page contains code to extract memory address parts. */
447 /* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudos. */
448 static inline bool
449 ok_for_index_p_nonstrict (rtx reg)
451 unsigned regno = REGNO (reg);
453 return regno >= FIRST_PSEUDO_REGISTER || REGNO_OK_FOR_INDEX_P (regno);
456 /* A version of regno_ok_for_base_p for use here, when all pseudos
457 should count as OK. Arguments as for regno_ok_for_base_p. */
458 static inline bool
459 ok_for_base_p_nonstrict (rtx reg, enum machine_mode mode, addr_space_t as,
460 enum rtx_code outer_code, enum rtx_code index_code)
462 unsigned regno = REGNO (reg);
464 if (regno >= FIRST_PSEUDO_REGISTER)
465 return true;
466 return ok_for_base_p_1 (regno, mode, as, outer_code, index_code);
471 /* The page contains major code to choose the current insn alternative
472 and generate reloads for it. */
474 /* Return the offset from REGNO of the least significant register
475 in (reg:MODE REGNO).
477 This function is used to tell whether two registers satisfy
478 a matching constraint. (reg:MODE1 REGNO1) matches (reg:MODE2 REGNO2) if:
480 REGNO1 + lra_constraint_offset (REGNO1, MODE1)
481 == REGNO2 + lra_constraint_offset (REGNO2, MODE2) */
483 lra_constraint_offset (int regno, enum machine_mode mode)
485 lra_assert (regno < FIRST_PSEUDO_REGISTER);
486 if (WORDS_BIG_ENDIAN && GET_MODE_SIZE (mode) > UNITS_PER_WORD
487 && SCALAR_INT_MODE_P (mode))
488 return hard_regno_nregs[regno][mode] - 1;
489 return 0;
492 /* Like rtx_equal_p except that it allows a REG and a SUBREG to match
493 if they are the same hard reg, and has special hacks for
494 auto-increment and auto-decrement. This is specifically intended for
495 process_alt_operands to use in determining whether two operands
496 match. X is the operand whose number is the lower of the two.
498 It is supposed that X is the output operand and Y is the input
499 operand. Y_HARD_REGNO is the final hard regno of register Y or
500 register in subreg Y as we know it now. Otherwise, it is a
501 negative value. */
502 static bool
503 operands_match_p (rtx x, rtx y, int y_hard_regno)
505 int i;
506 RTX_CODE code = GET_CODE (x);
507 const char *fmt;
509 if (x == y)
510 return true;
511 if ((code == REG || (code == SUBREG && REG_P (SUBREG_REG (x))))
512 && (REG_P (y) || (GET_CODE (y) == SUBREG && REG_P (SUBREG_REG (y)))))
514 int j;
516 i = get_hard_regno (x);
517 if (i < 0)
518 goto slow;
520 if ((j = y_hard_regno) < 0)
521 goto slow;
523 i += lra_constraint_offset (i, GET_MODE (x));
524 j += lra_constraint_offset (j, GET_MODE (y));
526 return i == j;
529 /* If two operands must match, because they are really a single
530 operand of an assembler insn, then two post-increments are invalid
531 because the assembler insn would increment only once. On the
532 other hand, a post-increment matches ordinary indexing if the
533 post-increment is the output operand. */
534 if (code == POST_DEC || code == POST_INC || code == POST_MODIFY)
535 return operands_match_p (XEXP (x, 0), y, y_hard_regno);
537 /* Two pre-increments are invalid because the assembler insn would
538 increment only once. On the other hand, a pre-increment matches
539 ordinary indexing if the pre-increment is the input operand. */
540 if (GET_CODE (y) == PRE_DEC || GET_CODE (y) == PRE_INC
541 || GET_CODE (y) == PRE_MODIFY)
542 return operands_match_p (x, XEXP (y, 0), -1);
544 slow:
546 if (code == REG && GET_CODE (y) == SUBREG && REG_P (SUBREG_REG (y))
547 && x == SUBREG_REG (y))
548 return true;
549 if (GET_CODE (y) == REG && code == SUBREG && REG_P (SUBREG_REG (x))
550 && SUBREG_REG (x) == y)
551 return true;
553 /* Now we have disposed of all the cases in which different rtx
554 codes can match. */
555 if (code != GET_CODE (y))
556 return false;
558 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
559 if (GET_MODE (x) != GET_MODE (y))
560 return false;
562 switch (code)
564 CASE_CONST_UNIQUE:
565 return false;
567 case LABEL_REF:
568 return XEXP (x, 0) == XEXP (y, 0);
569 case SYMBOL_REF:
570 return XSTR (x, 0) == XSTR (y, 0);
572 default:
573 break;
576 /* Compare the elements. If any pair of corresponding elements fail
577 to match, return false for the whole things. */
579 fmt = GET_RTX_FORMAT (code);
580 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
582 int val, j;
583 switch (fmt[i])
585 case 'w':
586 if (XWINT (x, i) != XWINT (y, i))
587 return false;
588 break;
590 case 'i':
591 if (XINT (x, i) != XINT (y, i))
592 return false;
593 break;
595 case 'e':
596 val = operands_match_p (XEXP (x, i), XEXP (y, i), -1);
597 if (val == 0)
598 return false;
599 break;
601 case '0':
602 break;
604 case 'E':
605 if (XVECLEN (x, i) != XVECLEN (y, i))
606 return false;
607 for (j = XVECLEN (x, i) - 1; j >= 0; --j)
609 val = operands_match_p (XVECEXP (x, i, j), XVECEXP (y, i, j), -1);
610 if (val == 0)
611 return false;
613 break;
615 /* It is believed that rtx's at this level will never
616 contain anything but integers and other rtx's, except for
617 within LABEL_REFs and SYMBOL_REFs. */
618 default:
619 gcc_unreachable ();
622 return true;
625 /* True if X is a constant that can be forced into the constant pool.
626 MODE is the mode of the operand, or VOIDmode if not known. */
627 #define CONST_POOL_OK_P(MODE, X) \
628 ((MODE) != VOIDmode \
629 && CONSTANT_P (X) \
630 && GET_CODE (X) != HIGH \
631 && !targetm.cannot_force_const_mem (MODE, X))
633 /* True if C is a non-empty register class that has too few registers
634 to be safely used as a reload target class. */
635 #define SMALL_REGISTER_CLASS_P(C) \
636 (reg_class_size [(C)] == 1 \
637 || (reg_class_size [(C)] >= 1 && targetm.class_likely_spilled_p (C)))
639 /* If REG is a reload pseudo, try to make its class satisfying CL. */
640 static void
641 narrow_reload_pseudo_class (rtx reg, enum reg_class cl)
643 enum reg_class rclass;
645 /* Do not make more accurate class from reloads generated. They are
646 mostly moves with a lot of constraints. Making more accurate
647 class may results in very narrow class and impossibility of find
648 registers for several reloads of one insn. */
649 if (INSN_UID (curr_insn) >= new_insn_uid_start)
650 return;
651 if (GET_CODE (reg) == SUBREG)
652 reg = SUBREG_REG (reg);
653 if (! REG_P (reg) || (int) REGNO (reg) < new_regno_start)
654 return;
655 if (in_class_p (reg, cl, &rclass) && rclass != cl)
656 change_class (REGNO (reg), rclass, " Change", true);
659 /* Generate reloads for matching OUT and INS (array of input operand
660 numbers with end marker -1) with reg class GOAL_CLASS. Add input
661 and output reloads correspondingly to the lists *BEFORE and
662 *AFTER. */
663 static void
664 match_reload (signed char out, signed char *ins, enum reg_class goal_class,
665 rtx *before, rtx *after)
667 int i, in;
668 rtx new_in_reg, new_out_reg, reg, clobber;
669 enum machine_mode inmode, outmode;
670 rtx in_rtx = *curr_id->operand_loc[ins[0]];
671 rtx out_rtx = *curr_id->operand_loc[out];
673 outmode = curr_operand_mode[out];
674 inmode = curr_operand_mode[ins[0]];
675 push_to_sequence (*before);
676 if (inmode != outmode)
678 if (GET_MODE_SIZE (inmode) > GET_MODE_SIZE (outmode))
680 reg = new_in_reg
681 = lra_create_new_reg_with_unique_value (inmode, in_rtx,
682 goal_class, "");
683 if (SCALAR_INT_MODE_P (inmode))
684 new_out_reg = gen_lowpart_SUBREG (outmode, reg);
685 else
686 new_out_reg = gen_rtx_SUBREG (outmode, reg, 0);
687 /* If the input reg is dying here, we can use the same hard
688 register for REG and IN_RTX. */
689 if (REG_P (in_rtx)
690 && find_regno_note (curr_insn, REG_DEAD, REGNO (in_rtx)))
691 lra_reg_info[REGNO (reg)].val = lra_reg_info[REGNO (in_rtx)].val;
693 else
695 reg = new_out_reg
696 = lra_create_new_reg_with_unique_value (outmode, out_rtx,
697 goal_class, "");
698 if (SCALAR_INT_MODE_P (outmode))
699 new_in_reg = gen_lowpart_SUBREG (inmode, reg);
700 else
701 new_in_reg = gen_rtx_SUBREG (inmode, reg, 0);
702 /* NEW_IN_REG is non-paradoxical subreg. We don't want
703 NEW_OUT_REG living above. We add clobber clause for
704 this. This is just a temporary clobber. We can remove
705 it at the end of LRA work. */
706 clobber = emit_clobber (new_out_reg);
707 LRA_TEMP_CLOBBER_P (PATTERN (clobber)) = 1;
708 if (GET_CODE (in_rtx) == SUBREG)
710 rtx subreg_reg = SUBREG_REG (in_rtx);
712 /* If SUBREG_REG is dying here and sub-registers IN_RTX
713 and NEW_IN_REG are similar, we can use the same hard
714 register for REG and SUBREG_REG. */
715 if (REG_P (subreg_reg) && GET_MODE (subreg_reg) == outmode
716 && SUBREG_BYTE (in_rtx) == SUBREG_BYTE (new_in_reg)
717 && find_regno_note (curr_insn, REG_DEAD, REGNO (subreg_reg)))
718 lra_reg_info[REGNO (reg)].val
719 = lra_reg_info[REGNO (subreg_reg)].val;
723 else
725 /* Pseudos have values -- see comments for lra_reg_info.
726 Different pseudos with the same value do not conflict even if
727 they live in the same place. When we create a pseudo we
728 assign value of original pseudo (if any) from which we
729 created the new pseudo. If we create the pseudo from the
730 input pseudo, the new pseudo will no conflict with the input
731 pseudo which is wrong when the input pseudo lives after the
732 insn and as the new pseudo value is changed by the insn
733 output. Therefore we create the new pseudo from the output.
735 We cannot reuse the current output register because we might
736 have a situation like "a <- a op b", where the constraints
737 force the second input operand ("b") to match the output
738 operand ("a"). "b" must then be copied into a new register
739 so that it doesn't clobber the current value of "a". */
741 new_in_reg = new_out_reg
742 = lra_create_new_reg_with_unique_value (outmode, out_rtx,
743 goal_class, "");
745 /* In and out operand can be got from transformations before
746 processing insn constraints. One example of such transformations
747 is subreg reloading (see function simplify_operand_subreg). The
748 new pseudos created by the transformations might have inaccurate
749 class (ALL_REGS) and we should make their classes more
750 accurate. */
751 narrow_reload_pseudo_class (in_rtx, goal_class);
752 narrow_reload_pseudo_class (out_rtx, goal_class);
753 lra_emit_move (copy_rtx (new_in_reg), in_rtx);
754 *before = get_insns ();
755 end_sequence ();
756 for (i = 0; (in = ins[i]) >= 0; i++)
758 lra_assert
759 (GET_MODE (*curr_id->operand_loc[in]) == VOIDmode
760 || GET_MODE (new_in_reg) == GET_MODE (*curr_id->operand_loc[in]));
761 *curr_id->operand_loc[in] = new_in_reg;
763 lra_update_dups (curr_id, ins);
764 if (find_reg_note (curr_insn, REG_UNUSED, out_rtx) == NULL_RTX)
766 start_sequence ();
767 lra_emit_move (out_rtx, copy_rtx (new_out_reg));
768 emit_insn (*after);
769 *after = get_insns ();
770 end_sequence ();
772 *curr_id->operand_loc[out] = new_out_reg;
773 lra_update_dup (curr_id, out);
776 /* Return register class which is union of all reg classes in insn
777 constraint alternative string starting with P. */
778 static enum reg_class
779 reg_class_from_constraints (const char *p)
781 int c, len;
782 enum reg_class op_class = NO_REGS;
785 switch ((c = *p, len = CONSTRAINT_LEN (c, p)), c)
787 case '#':
788 case ',':
789 return op_class;
791 case 'p':
792 op_class = (reg_class_subunion
793 [op_class][base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
794 ADDRESS, SCRATCH)]);
795 break;
797 case 'g':
798 case 'r':
799 op_class = reg_class_subunion[op_class][GENERAL_REGS];
800 break;
802 default:
803 if (REG_CLASS_FROM_CONSTRAINT (c, p) == NO_REGS)
805 #ifdef EXTRA_CONSTRAINT_STR
806 if (EXTRA_ADDRESS_CONSTRAINT (c, p))
807 op_class
808 = (reg_class_subunion
809 [op_class][base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
810 ADDRESS, SCRATCH)]);
811 #endif
812 break;
815 op_class
816 = reg_class_subunion[op_class][REG_CLASS_FROM_CONSTRAINT (c, p)];
817 break;
819 while ((p += len), c);
820 return op_class;
823 /* If OP is a register, return the class of the register as per
824 get_reg_class, otherwise return NO_REGS. */
825 static inline enum reg_class
826 get_op_class (rtx op)
828 return REG_P (op) ? get_reg_class (REGNO (op)) : NO_REGS;
831 /* Return generated insn mem_pseudo:=val if TO_P or val:=mem_pseudo
832 otherwise. If modes of MEM_PSEUDO and VAL are different, use
833 SUBREG for VAL to make them equal. */
834 static rtx
835 emit_spill_move (bool to_p, rtx mem_pseudo, rtx val)
837 if (GET_MODE (mem_pseudo) != GET_MODE (val))
838 val = gen_rtx_SUBREG (GET_MODE (mem_pseudo),
839 GET_CODE (val) == SUBREG ? SUBREG_REG (val) : val,
841 return (to_p
842 ? gen_move_insn (mem_pseudo, val)
843 : gen_move_insn (val, mem_pseudo));
846 /* Process a special case insn (register move), return true if we
847 don't need to process it anymore. Return that RTL was changed
848 through CHANGE_P and macro SECONDARY_MEMORY_NEEDED says to use
849 secondary memory through SEC_MEM_P. */
850 static bool
851 check_and_process_move (bool *change_p, bool *sec_mem_p)
853 int sregno, dregno;
854 rtx set, dest, src, dreg, sreg, old_sreg, new_reg, before, scratch_reg;
855 enum reg_class dclass, sclass, secondary_class;
856 enum machine_mode sreg_mode;
857 secondary_reload_info sri;
859 *sec_mem_p = *change_p = false;
860 if ((set = single_set (curr_insn)) == NULL)
861 return false;
862 dreg = dest = SET_DEST (set);
863 sreg = src = SET_SRC (set);
864 /* Quick check on the right move insn which does not need
865 reloads. */
866 if ((dclass = get_op_class (dest)) != NO_REGS
867 && (sclass = get_op_class (src)) != NO_REGS
868 /* The backend guarantees that register moves of cost 2 never
869 need reloads. */
870 && targetm.register_move_cost (GET_MODE (src), dclass, sclass) == 2)
871 return true;
872 if (GET_CODE (dest) == SUBREG)
873 dreg = SUBREG_REG (dest);
874 if (GET_CODE (src) == SUBREG)
875 sreg = SUBREG_REG (src);
876 if (! REG_P (dreg) || ! REG_P (sreg))
877 return false;
878 sclass = dclass = NO_REGS;
879 dreg = get_equiv_substitution (dreg);
880 if (REG_P (dreg))
881 dclass = get_reg_class (REGNO (dreg));
882 if (dclass == ALL_REGS)
883 /* ALL_REGS is used for new pseudos created by transformations
884 like reload of SUBREG_REG (see function
885 simplify_operand_subreg). We don't know their class yet. We
886 should figure out the class from processing the insn
887 constraints not in this fast path function. Even if ALL_REGS
888 were a right class for the pseudo, secondary_... hooks usually
889 are not define for ALL_REGS. */
890 return false;
891 sreg_mode = GET_MODE (sreg);
892 old_sreg = sreg;
893 sreg = get_equiv_substitution (sreg);
894 if (REG_P (sreg))
895 sclass = get_reg_class (REGNO (sreg));
896 if (sclass == ALL_REGS)
897 /* See comments above. */
898 return false;
899 #ifdef SECONDARY_MEMORY_NEEDED
900 if (dclass != NO_REGS && sclass != NO_REGS
901 && SECONDARY_MEMORY_NEEDED (sclass, dclass, GET_MODE (src)))
903 *sec_mem_p = true;
904 return false;
906 #endif
907 sri.prev_sri = NULL;
908 sri.icode = CODE_FOR_nothing;
909 sri.extra_cost = 0;
910 secondary_class = NO_REGS;
911 /* Set up hard register for a reload pseudo for hook
912 secondary_reload because some targets just ignore unassigned
913 pseudos in the hook. */
914 if (dclass != NO_REGS && lra_get_regno_hard_regno (REGNO (dreg)) < 0)
916 dregno = REGNO (dreg);
917 reg_renumber[dregno] = ira_class_hard_regs[dclass][0];
919 else
920 dregno = -1;
921 if (sclass != NO_REGS && lra_get_regno_hard_regno (REGNO (sreg)) < 0)
923 sregno = REGNO (sreg);
924 reg_renumber[sregno] = ira_class_hard_regs[sclass][0];
926 else
927 sregno = -1;
928 if (sclass != NO_REGS)
929 secondary_class
930 = (enum reg_class) targetm.secondary_reload (false, dest,
931 (reg_class_t) sclass,
932 GET_MODE (src), &sri);
933 if (sclass == NO_REGS
934 || ((secondary_class != NO_REGS || sri.icode != CODE_FOR_nothing)
935 && dclass != NO_REGS))
937 enum reg_class old_sclass = secondary_class;
938 secondary_reload_info old_sri = sri;
940 sri.prev_sri = NULL;
941 sri.icode = CODE_FOR_nothing;
942 sri.extra_cost = 0;
943 secondary_class
944 = (enum reg_class) targetm.secondary_reload (true, sreg,
945 (reg_class_t) dclass,
946 sreg_mode, &sri);
947 /* Check the target hook consistency. */
948 lra_assert
949 ((secondary_class == NO_REGS && sri.icode == CODE_FOR_nothing)
950 || (old_sclass == NO_REGS && old_sri.icode == CODE_FOR_nothing)
951 || (secondary_class == old_sclass && sri.icode == old_sri.icode));
953 if (sregno >= 0)
954 reg_renumber [sregno] = -1;
955 if (dregno >= 0)
956 reg_renumber [dregno] = -1;
957 if (secondary_class == NO_REGS && sri.icode == CODE_FOR_nothing)
958 return false;
959 *change_p = true;
960 new_reg = NULL_RTX;
961 if (secondary_class != NO_REGS)
962 new_reg = lra_create_new_reg_with_unique_value (sreg_mode, NULL_RTX,
963 secondary_class,
964 "secondary");
965 start_sequence ();
966 if (old_sreg != sreg)
967 sreg = copy_rtx (sreg);
968 if (sri.icode == CODE_FOR_nothing)
969 lra_emit_move (new_reg, sreg);
970 else
972 enum reg_class scratch_class;
974 scratch_class = (reg_class_from_constraints
975 (insn_data[sri.icode].operand[2].constraint));
976 scratch_reg = (lra_create_new_reg_with_unique_value
977 (insn_data[sri.icode].operand[2].mode, NULL_RTX,
978 scratch_class, "scratch"));
979 emit_insn (GEN_FCN (sri.icode) (new_reg != NULL_RTX ? new_reg : dest,
980 sreg, scratch_reg));
982 before = get_insns ();
983 end_sequence ();
984 lra_process_new_insns (curr_insn, before, NULL_RTX, "Inserting the move");
985 if (new_reg != NULL_RTX)
987 if (GET_CODE (src) == SUBREG)
988 SUBREG_REG (src) = new_reg;
989 else
990 SET_SRC (set) = new_reg;
992 else
994 if (lra_dump_file != NULL)
996 fprintf (lra_dump_file, "Deleting move %u\n", INSN_UID (curr_insn));
997 dump_insn_slim (lra_dump_file, curr_insn);
999 lra_set_insn_deleted (curr_insn);
1000 return true;
1002 return false;
1005 /* The following data describe the result of process_alt_operands.
1006 The data are used in curr_insn_transform to generate reloads. */
1008 /* The chosen reg classes which should be used for the corresponding
1009 operands. */
1010 static enum reg_class goal_alt[MAX_RECOG_OPERANDS];
1011 /* True if the operand should be the same as another operand and that
1012 other operand does not need a reload. */
1013 static bool goal_alt_match_win[MAX_RECOG_OPERANDS];
1014 /* True if the operand does not need a reload. */
1015 static bool goal_alt_win[MAX_RECOG_OPERANDS];
1016 /* True if the operand can be offsetable memory. */
1017 static bool goal_alt_offmemok[MAX_RECOG_OPERANDS];
1018 /* The number of an operand to which given operand can be matched to. */
1019 static int goal_alt_matches[MAX_RECOG_OPERANDS];
1020 /* The number of elements in the following array. */
1021 static int goal_alt_dont_inherit_ops_num;
1022 /* Numbers of operands whose reload pseudos should not be inherited. */
1023 static int goal_alt_dont_inherit_ops[MAX_RECOG_OPERANDS];
1024 /* True if the insn commutative operands should be swapped. */
1025 static bool goal_alt_swapped;
1026 /* The chosen insn alternative. */
1027 static int goal_alt_number;
1029 /* The following five variables are used to choose the best insn
1030 alternative. They reflect final characteristics of the best
1031 alternative. */
1033 /* Number of necessary reloads and overall cost reflecting the
1034 previous value and other unpleasantness of the best alternative. */
1035 static int best_losers, best_overall;
1036 /* Number of small register classes used for operands of the best
1037 alternative. */
1038 static int best_small_class_operands_num;
1039 /* Overall number hard registers used for reloads. For example, on
1040 some targets we need 2 general registers to reload DFmode and only
1041 one floating point register. */
1042 static int best_reload_nregs;
1043 /* Overall number reflecting distances of previous reloading the same
1044 value. The distances are counted from the current BB start. It is
1045 used to improve inheritance chances. */
1046 static int best_reload_sum;
1048 /* True if the current insn should have no correspondingly input or
1049 output reloads. */
1050 static bool no_input_reloads_p, no_output_reloads_p;
1052 /* True if we swapped the commutative operands in the current
1053 insn. */
1054 static int curr_swapped;
1056 /* Arrange for address element *LOC to be a register of class CL.
1057 Add any input reloads to list BEFORE. AFTER is nonnull if *LOC is an
1058 automodified value; handle that case by adding the required output
1059 reloads to list AFTER. Return true if the RTL was changed. */
1060 static bool
1061 process_addr_reg (rtx *loc, rtx *before, rtx *after, enum reg_class cl)
1063 int regno;
1064 enum reg_class rclass, new_class;
1065 rtx reg;
1066 rtx new_reg;
1067 enum machine_mode mode;
1068 bool before_p = false;
1070 loc = strip_subreg (loc);
1071 reg = *loc;
1072 mode = GET_MODE (reg);
1073 if (! REG_P (reg))
1075 /* Always reload memory in an address even if the target supports
1076 such addresses. */
1077 new_reg = lra_create_new_reg_with_unique_value (mode, reg, cl, "address");
1078 before_p = true;
1080 else
1082 regno = REGNO (reg);
1083 rclass = get_reg_class (regno);
1084 if ((*loc = get_equiv_substitution (reg)) != reg)
1086 if (lra_dump_file != NULL)
1088 fprintf (lra_dump_file,
1089 "Changing pseudo %d in address of insn %u on equiv ",
1090 REGNO (reg), INSN_UID (curr_insn));
1091 dump_value_slim (lra_dump_file, *loc, 1);
1092 fprintf (lra_dump_file, "\n");
1094 *loc = copy_rtx (*loc);
1096 if (*loc != reg || ! in_class_p (reg, cl, &new_class))
1098 reg = *loc;
1099 if (get_reload_reg (after == NULL ? OP_IN : OP_INOUT,
1100 mode, reg, cl, "address", &new_reg))
1101 before_p = true;
1103 else if (new_class != NO_REGS && rclass != new_class)
1105 change_class (regno, new_class, " Change", true);
1106 return false;
1108 else
1109 return false;
1111 if (before_p)
1113 push_to_sequence (*before);
1114 lra_emit_move (new_reg, reg);
1115 *before = get_insns ();
1116 end_sequence ();
1118 *loc = new_reg;
1119 if (after != NULL)
1121 start_sequence ();
1122 lra_emit_move (reg, new_reg);
1123 emit_insn (*after);
1124 *after = get_insns ();
1125 end_sequence ();
1127 return true;
1130 /* Make reloads for subreg in operand NOP with internal subreg mode
1131 REG_MODE, add new reloads for further processing. Return true if
1132 any reload was generated. */
1133 static bool
1134 simplify_operand_subreg (int nop, enum machine_mode reg_mode)
1136 int hard_regno;
1137 rtx before, after;
1138 enum machine_mode mode;
1139 rtx reg, new_reg;
1140 rtx operand = *curr_id->operand_loc[nop];
1142 before = after = NULL_RTX;
1144 if (GET_CODE (operand) != SUBREG)
1145 return false;
1147 mode = GET_MODE (operand);
1148 reg = SUBREG_REG (operand);
1149 /* If we change address for paradoxical subreg of memory, the
1150 address might violate the necessary alignment or the access might
1151 be slow. So take this into consideration. We should not worry
1152 about access beyond allocated memory for paradoxical memory
1153 subregs as we don't substitute such equiv memory (see processing
1154 equivalences in function lra_constraints) and because for spilled
1155 pseudos we allocate stack memory enough for the biggest
1156 corresponding paradoxical subreg. */
1157 if ((MEM_P (reg)
1158 && (! SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (reg))
1159 || MEM_ALIGN (reg) >= GET_MODE_ALIGNMENT (mode)))
1160 || (REG_P (reg) && REGNO (reg) < FIRST_PSEUDO_REGISTER))
1162 alter_subreg (curr_id->operand_loc[nop], false);
1163 return true;
1165 /* Put constant into memory when we have mixed modes. It generates
1166 a better code in most cases as it does not need a secondary
1167 reload memory. It also prevents LRA looping when LRA is using
1168 secondary reload memory again and again. */
1169 if (CONSTANT_P (reg) && CONST_POOL_OK_P (reg_mode, reg)
1170 && SCALAR_INT_MODE_P (reg_mode) != SCALAR_INT_MODE_P (mode))
1172 SUBREG_REG (operand) = force_const_mem (reg_mode, reg);
1173 alter_subreg (curr_id->operand_loc[nop], false);
1174 return true;
1176 /* Force a reload of the SUBREG_REG if this is a constant or PLUS or
1177 if there may be a problem accessing OPERAND in the outer
1178 mode. */
1179 if ((REG_P (reg)
1180 && REGNO (reg) >= FIRST_PSEUDO_REGISTER
1181 && (hard_regno = lra_get_regno_hard_regno (REGNO (reg))) >= 0
1182 /* Don't reload paradoxical subregs because we could be looping
1183 having repeatedly final regno out of hard regs range. */
1184 && (hard_regno_nregs[hard_regno][GET_MODE (reg)]
1185 >= hard_regno_nregs[hard_regno][mode])
1186 && simplify_subreg_regno (hard_regno, GET_MODE (reg),
1187 SUBREG_BYTE (operand), mode) < 0)
1188 || CONSTANT_P (reg) || GET_CODE (reg) == PLUS || MEM_P (reg))
1190 enum op_type type = curr_static_id->operand[nop].type;
1191 /* The class will be defined later in curr_insn_transform. */
1192 enum reg_class rclass
1193 = (enum reg_class) targetm.preferred_reload_class (reg, ALL_REGS);
1195 new_reg = lra_create_new_reg_with_unique_value (reg_mode, reg, rclass,
1196 "subreg reg");
1197 bitmap_set_bit (&lra_optional_reload_pseudos, REGNO (new_reg));
1198 if (type != OP_OUT
1199 || GET_MODE_SIZE (GET_MODE (reg)) > GET_MODE_SIZE (mode))
1201 push_to_sequence (before);
1202 lra_emit_move (new_reg, reg);
1203 before = get_insns ();
1204 end_sequence ();
1206 if (type != OP_IN)
1208 start_sequence ();
1209 lra_emit_move (reg, new_reg);
1210 emit_insn (after);
1211 after = get_insns ();
1212 end_sequence ();
1214 SUBREG_REG (operand) = new_reg;
1215 lra_process_new_insns (curr_insn, before, after,
1216 "Inserting subreg reload");
1217 return true;
1219 return false;
1222 /* Return TRUE if X refers for a hard register from SET. */
1223 static bool
1224 uses_hard_regs_p (rtx x, HARD_REG_SET set)
1226 int i, j, x_hard_regno;
1227 enum machine_mode mode;
1228 const char *fmt;
1229 enum rtx_code code;
1231 if (x == NULL_RTX)
1232 return false;
1233 code = GET_CODE (x);
1234 mode = GET_MODE (x);
1235 if (code == SUBREG)
1237 x = SUBREG_REG (x);
1238 code = GET_CODE (x);
1239 if (GET_MODE_SIZE (GET_MODE (x)) > GET_MODE_SIZE (mode))
1240 mode = GET_MODE (x);
1243 if (REG_P (x))
1245 x_hard_regno = get_hard_regno (x);
1246 return (x_hard_regno >= 0
1247 && overlaps_hard_reg_set_p (set, mode, x_hard_regno));
1249 if (MEM_P (x))
1251 struct address_info ad;
1253 decompose_mem_address (&ad, x);
1254 if (ad.base_term != NULL && uses_hard_regs_p (*ad.base_term, set))
1255 return true;
1256 if (ad.index_term != NULL && uses_hard_regs_p (*ad.index_term, set))
1257 return true;
1259 fmt = GET_RTX_FORMAT (code);
1260 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1262 if (fmt[i] == 'e')
1264 if (uses_hard_regs_p (XEXP (x, i), set))
1265 return true;
1267 else if (fmt[i] == 'E')
1269 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1270 if (uses_hard_regs_p (XVECEXP (x, i, j), set))
1271 return true;
1274 return false;
1277 /* Return true if OP is a spilled pseudo. */
1278 static inline bool
1279 spilled_pseudo_p (rtx op)
1281 return (REG_P (op)
1282 && REGNO (op) >= FIRST_PSEUDO_REGISTER && in_mem_p (REGNO (op)));
1285 /* Return true if X is a general constant. */
1286 static inline bool
1287 general_constant_p (rtx x)
1289 return CONSTANT_P (x) && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (x));
1292 /* Major function to choose the current insn alternative and what
1293 operands should be reloaded and how. If ONLY_ALTERNATIVE is not
1294 negative we should consider only this alternative. Return false if
1295 we can not choose the alternative or find how to reload the
1296 operands. */
1297 static bool
1298 process_alt_operands (int only_alternative)
1300 bool ok_p = false;
1301 int nop, small_class_operands_num, overall, nalt;
1302 int n_alternatives = curr_static_id->n_alternatives;
1303 int n_operands = curr_static_id->n_operands;
1304 /* LOSERS counts the operands that don't fit this alternative and
1305 would require loading. */
1306 int losers;
1307 /* REJECT is a count of how undesirable this alternative says it is
1308 if any reloading is required. If the alternative matches exactly
1309 then REJECT is ignored, but otherwise it gets this much counted
1310 against it in addition to the reloading needed. */
1311 int reject;
1312 /* The number of elements in the following array. */
1313 int early_clobbered_regs_num;
1314 /* Numbers of operands which are early clobber registers. */
1315 int early_clobbered_nops[MAX_RECOG_OPERANDS];
1316 enum reg_class curr_alt[MAX_RECOG_OPERANDS];
1317 HARD_REG_SET curr_alt_set[MAX_RECOG_OPERANDS];
1318 bool curr_alt_match_win[MAX_RECOG_OPERANDS];
1319 bool curr_alt_win[MAX_RECOG_OPERANDS];
1320 bool curr_alt_offmemok[MAX_RECOG_OPERANDS];
1321 int curr_alt_matches[MAX_RECOG_OPERANDS];
1322 /* The number of elements in the following array. */
1323 int curr_alt_dont_inherit_ops_num;
1324 /* Numbers of operands whose reload pseudos should not be inherited. */
1325 int curr_alt_dont_inherit_ops[MAX_RECOG_OPERANDS];
1326 rtx op;
1327 /* The register when the operand is a subreg of register, otherwise the
1328 operand itself. */
1329 rtx no_subreg_reg_operand[MAX_RECOG_OPERANDS];
1330 /* The register if the operand is a register or subreg of register,
1331 otherwise NULL. */
1332 rtx operand_reg[MAX_RECOG_OPERANDS];
1333 int hard_regno[MAX_RECOG_OPERANDS];
1334 enum machine_mode biggest_mode[MAX_RECOG_OPERANDS];
1335 int reload_nregs, reload_sum;
1336 bool costly_p;
1337 enum reg_class cl;
1339 /* Calculate some data common for all alternatives to speed up the
1340 function. */
1341 for (nop = 0; nop < n_operands; nop++)
1343 op = no_subreg_reg_operand[nop] = *curr_id->operand_loc[nop];
1344 /* The real hard regno of the operand after the allocation. */
1345 hard_regno[nop] = get_hard_regno (op);
1347 operand_reg[nop] = op;
1348 biggest_mode[nop] = GET_MODE (operand_reg[nop]);
1349 if (GET_CODE (operand_reg[nop]) == SUBREG)
1351 operand_reg[nop] = SUBREG_REG (operand_reg[nop]);
1352 if (GET_MODE_SIZE (biggest_mode[nop])
1353 < GET_MODE_SIZE (GET_MODE (operand_reg[nop])))
1354 biggest_mode[nop] = GET_MODE (operand_reg[nop]);
1356 if (REG_P (operand_reg[nop]))
1357 no_subreg_reg_operand[nop] = operand_reg[nop];
1358 else
1359 operand_reg[nop] = NULL_RTX;
1362 /* The constraints are made of several alternatives. Each operand's
1363 constraint looks like foo,bar,... with commas separating the
1364 alternatives. The first alternatives for all operands go
1365 together, the second alternatives go together, etc.
1367 First loop over alternatives. */
1368 for (nalt = 0; nalt < n_alternatives; nalt++)
1370 /* Loop over operands for one constraint alternative. */
1371 #ifdef HAVE_ATTR_enabled
1372 if (curr_id->alternative_enabled_p != NULL
1373 && ! curr_id->alternative_enabled_p[nalt])
1374 continue;
1375 #endif
1377 if (only_alternative >= 0 && nalt != only_alternative)
1378 continue;
1380 overall = losers = reject = reload_nregs = reload_sum = 0;
1381 for (nop = 0; nop < n_operands; nop++)
1382 reject += (curr_static_id
1383 ->operand_alternative[nalt * n_operands + nop].reject);
1384 early_clobbered_regs_num = 0;
1386 for (nop = 0; nop < n_operands; nop++)
1388 const char *p;
1389 char *end;
1390 int len, c, m, i, opalt_num, this_alternative_matches;
1391 bool win, did_match, offmemok, early_clobber_p;
1392 /* false => this operand can be reloaded somehow for this
1393 alternative. */
1394 bool badop;
1395 /* true => this operand can be reloaded if the alternative
1396 allows regs. */
1397 bool winreg;
1398 /* True if a constant forced into memory would be OK for
1399 this operand. */
1400 bool constmemok;
1401 enum reg_class this_alternative, this_costly_alternative;
1402 HARD_REG_SET this_alternative_set, this_costly_alternative_set;
1403 bool this_alternative_match_win, this_alternative_win;
1404 bool this_alternative_offmemok;
1405 enum machine_mode mode;
1407 opalt_num = nalt * n_operands + nop;
1408 if (curr_static_id->operand_alternative[opalt_num].anything_ok)
1410 /* Fast track for no constraints at all. */
1411 curr_alt[nop] = NO_REGS;
1412 CLEAR_HARD_REG_SET (curr_alt_set[nop]);
1413 curr_alt_win[nop] = true;
1414 curr_alt_match_win[nop] = false;
1415 curr_alt_offmemok[nop] = false;
1416 curr_alt_matches[nop] = -1;
1417 continue;
1420 op = no_subreg_reg_operand[nop];
1421 mode = curr_operand_mode[nop];
1423 win = did_match = winreg = offmemok = constmemok = false;
1424 badop = true;
1426 early_clobber_p = false;
1427 p = curr_static_id->operand_alternative[opalt_num].constraint;
1429 this_costly_alternative = this_alternative = NO_REGS;
1430 /* We update set of possible hard regs besides its class
1431 because reg class might be inaccurate. For example,
1432 union of LO_REGS (l), HI_REGS(h), and STACK_REG(k) in ARM
1433 is translated in HI_REGS because classes are merged by
1434 pairs and there is no accurate intermediate class. */
1435 CLEAR_HARD_REG_SET (this_alternative_set);
1436 CLEAR_HARD_REG_SET (this_costly_alternative_set);
1437 this_alternative_win = false;
1438 this_alternative_match_win = false;
1439 this_alternative_offmemok = false;
1440 this_alternative_matches = -1;
1442 /* An empty constraint should be excluded by the fast
1443 track. */
1444 lra_assert (*p != 0 && *p != ',');
1446 /* Scan this alternative's specs for this operand; set WIN
1447 if the operand fits any letter in this alternative.
1448 Otherwise, clear BADOP if this operand could fit some
1449 letter after reloads, or set WINREG if this operand could
1450 fit after reloads provided the constraint allows some
1451 registers. */
1452 costly_p = false;
1455 switch ((c = *p, len = CONSTRAINT_LEN (c, p)), c)
1457 case '\0':
1458 len = 0;
1459 break;
1460 case ',':
1461 c = '\0';
1462 break;
1464 case '=': case '+': case '?': case '*': case '!':
1465 case ' ': case '\t':
1466 break;
1468 case '%':
1469 /* We only support one commutative marker, the first
1470 one. We already set commutative above. */
1471 break;
1473 case '&':
1474 early_clobber_p = true;
1475 break;
1477 case '#':
1478 /* Ignore rest of this alternative. */
1479 c = '\0';
1480 break;
1482 case '0': case '1': case '2': case '3': case '4':
1483 case '5': case '6': case '7': case '8': case '9':
1485 int m_hregno;
1486 bool match_p;
1488 m = strtoul (p, &end, 10);
1489 p = end;
1490 len = 0;
1491 lra_assert (nop > m);
1493 this_alternative_matches = m;
1494 m_hregno = get_hard_regno (*curr_id->operand_loc[m]);
1495 /* We are supposed to match a previous operand.
1496 If we do, we win if that one did. If we do
1497 not, count both of the operands as losers.
1498 (This is too conservative, since most of the
1499 time only a single reload insn will be needed
1500 to make the two operands win. As a result,
1501 this alternative may be rejected when it is
1502 actually desirable.) */
1503 match_p = false;
1504 if (operands_match_p (*curr_id->operand_loc[nop],
1505 *curr_id->operand_loc[m], m_hregno))
1507 /* We should reject matching of an early
1508 clobber operand if the matching operand is
1509 not dying in the insn. */
1510 if (! curr_static_id->operand[m].early_clobber
1511 || operand_reg[nop] == NULL_RTX
1512 || (find_regno_note (curr_insn, REG_DEAD,
1513 REGNO (operand_reg[nop]))
1514 != NULL_RTX))
1515 match_p = true;
1517 if (match_p)
1519 /* If we are matching a non-offsettable
1520 address where an offsettable address was
1521 expected, then we must reject this
1522 combination, because we can't reload
1523 it. */
1524 if (curr_alt_offmemok[m]
1525 && MEM_P (*curr_id->operand_loc[m])
1526 && curr_alt[m] == NO_REGS && ! curr_alt_win[m])
1527 continue;
1530 else
1532 /* Operands don't match. Both operands must
1533 allow a reload register, otherwise we
1534 cannot make them match. */
1535 if (curr_alt[m] == NO_REGS)
1536 break;
1537 /* Retroactively mark the operand we had to
1538 match as a loser, if it wasn't already and
1539 it wasn't matched to a register constraint
1540 (e.g it might be matched by memory). */
1541 if (curr_alt_win[m]
1542 && (operand_reg[m] == NULL_RTX
1543 || hard_regno[m] < 0))
1545 losers++;
1546 reload_nregs
1547 += (ira_reg_class_max_nregs[curr_alt[m]]
1548 [GET_MODE (*curr_id->operand_loc[m])]);
1551 /* We prefer no matching alternatives because
1552 it gives more freedom in RA. */
1553 if (operand_reg[nop] == NULL_RTX
1554 || (find_regno_note (curr_insn, REG_DEAD,
1555 REGNO (operand_reg[nop]))
1556 == NULL_RTX))
1557 reject += 2;
1559 /* If we have to reload this operand and some
1560 previous operand also had to match the same
1561 thing as this operand, we don't know how to do
1562 that. */
1563 if (!match_p || !curr_alt_win[m])
1565 for (i = 0; i < nop; i++)
1566 if (curr_alt_matches[i] == m)
1567 break;
1568 if (i < nop)
1569 break;
1571 else
1572 did_match = true;
1574 /* This can be fixed with reloads if the operand
1575 we are supposed to match can be fixed with
1576 reloads. */
1577 badop = false;
1578 this_alternative = curr_alt[m];
1579 COPY_HARD_REG_SET (this_alternative_set, curr_alt_set[m]);
1580 winreg = this_alternative != NO_REGS;
1581 break;
1584 case 'p':
1585 cl = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
1586 ADDRESS, SCRATCH);
1587 this_alternative = reg_class_subunion[this_alternative][cl];
1588 IOR_HARD_REG_SET (this_alternative_set,
1589 reg_class_contents[cl]);
1590 if (costly_p)
1592 this_costly_alternative
1593 = reg_class_subunion[this_costly_alternative][cl];
1594 IOR_HARD_REG_SET (this_costly_alternative_set,
1595 reg_class_contents[cl]);
1597 win = true;
1598 badop = false;
1599 break;
1601 case TARGET_MEM_CONSTRAINT:
1602 if (MEM_P (op) || spilled_pseudo_p (op))
1603 win = true;
1604 /* We can put constant or pseudo value into memory
1605 to satisfy the constraint. */
1606 if (CONST_POOL_OK_P (mode, op) || REG_P (op))
1607 badop = false;
1608 constmemok = true;
1609 break;
1611 case '<':
1612 if (MEM_P (op)
1613 && (GET_CODE (XEXP (op, 0)) == PRE_DEC
1614 || GET_CODE (XEXP (op, 0)) == POST_DEC))
1615 win = true;
1616 break;
1618 case '>':
1619 if (MEM_P (op)
1620 && (GET_CODE (XEXP (op, 0)) == PRE_INC
1621 || GET_CODE (XEXP (op, 0)) == POST_INC))
1622 win = true;
1623 break;
1625 /* Memory op whose address is not offsettable. */
1626 case 'V':
1627 if (MEM_P (op)
1628 && ! offsettable_nonstrict_memref_p (op))
1629 win = true;
1630 break;
1632 /* Memory operand whose address is offsettable. */
1633 case 'o':
1634 if ((MEM_P (op)
1635 && offsettable_nonstrict_memref_p (op))
1636 || spilled_pseudo_p (op))
1637 win = true;
1638 /* We can put constant or pseudo value into memory
1639 or make memory address offsetable to satisfy the
1640 constraint. */
1641 if (CONST_POOL_OK_P (mode, op) || MEM_P (op) || REG_P (op))
1642 badop = false;
1643 constmemok = true;
1644 offmemok = true;
1645 break;
1647 case 'E':
1648 case 'F':
1649 if (GET_CODE (op) == CONST_DOUBLE
1650 || (GET_CODE (op) == CONST_VECTOR
1651 && (GET_MODE_CLASS (mode) == MODE_VECTOR_FLOAT)))
1652 win = true;
1653 break;
1655 case 'G':
1656 case 'H':
1657 if (GET_CODE (op) == CONST_DOUBLE
1658 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, p))
1659 win = true;
1660 break;
1662 case 's':
1663 if (CONST_INT_P (op)
1664 || (GET_CODE (op) == CONST_DOUBLE && mode == VOIDmode))
1665 break;
1667 case 'i':
1668 if (general_constant_p (op))
1669 win = true;
1670 break;
1672 case 'n':
1673 if (CONST_INT_P (op)
1674 || (GET_CODE (op) == CONST_DOUBLE && mode == VOIDmode))
1675 win = true;
1676 break;
1678 case 'I':
1679 case 'J':
1680 case 'K':
1681 case 'L':
1682 case 'M':
1683 case 'N':
1684 case 'O':
1685 case 'P':
1686 if (CONST_INT_P (op)
1687 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, p))
1688 win = true;
1689 break;
1691 case 'X':
1692 /* This constraint should be excluded by the fast
1693 track. */
1694 gcc_unreachable ();
1695 break;
1697 case 'g':
1698 if (MEM_P (op)
1699 || general_constant_p (op)
1700 || spilled_pseudo_p (op))
1701 win = true;
1702 /* Drop through into 'r' case. */
1704 case 'r':
1705 this_alternative
1706 = reg_class_subunion[this_alternative][GENERAL_REGS];
1707 IOR_HARD_REG_SET (this_alternative_set,
1708 reg_class_contents[GENERAL_REGS]);
1709 if (costly_p)
1711 this_costly_alternative
1712 = (reg_class_subunion
1713 [this_costly_alternative][GENERAL_REGS]);
1714 IOR_HARD_REG_SET (this_costly_alternative_set,
1715 reg_class_contents[GENERAL_REGS]);
1717 goto reg;
1719 default:
1720 if (REG_CLASS_FROM_CONSTRAINT (c, p) == NO_REGS)
1722 #ifdef EXTRA_CONSTRAINT_STR
1723 if (EXTRA_MEMORY_CONSTRAINT (c, p))
1725 if (EXTRA_CONSTRAINT_STR (op, c, p))
1726 win = true;
1727 else if (spilled_pseudo_p (op))
1728 win = true;
1730 /* If we didn't already win, we can reload
1731 constants via force_const_mem or put the
1732 pseudo value into memory, or make other
1733 memory by reloading the address like for
1734 'o'. */
1735 if (CONST_POOL_OK_P (mode, op)
1736 || MEM_P (op) || REG_P (op))
1737 badop = false;
1738 constmemok = true;
1739 offmemok = true;
1740 break;
1742 if (EXTRA_ADDRESS_CONSTRAINT (c, p))
1744 if (EXTRA_CONSTRAINT_STR (op, c, p))
1745 win = true;
1747 /* If we didn't already win, we can reload
1748 the address into a base register. */
1749 cl = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
1750 ADDRESS, SCRATCH);
1751 this_alternative
1752 = reg_class_subunion[this_alternative][cl];
1753 IOR_HARD_REG_SET (this_alternative_set,
1754 reg_class_contents[cl]);
1755 if (costly_p)
1757 this_costly_alternative
1758 = (reg_class_subunion
1759 [this_costly_alternative][cl]);
1760 IOR_HARD_REG_SET (this_costly_alternative_set,
1761 reg_class_contents[cl]);
1763 badop = false;
1764 break;
1767 if (EXTRA_CONSTRAINT_STR (op, c, p))
1768 win = true;
1769 #endif
1770 break;
1773 cl = REG_CLASS_FROM_CONSTRAINT (c, p);
1774 this_alternative = reg_class_subunion[this_alternative][cl];
1775 IOR_HARD_REG_SET (this_alternative_set,
1776 reg_class_contents[cl]);
1777 if (costly_p)
1779 this_costly_alternative
1780 = reg_class_subunion[this_costly_alternative][cl];
1781 IOR_HARD_REG_SET (this_costly_alternative_set,
1782 reg_class_contents[cl]);
1784 reg:
1785 if (mode == BLKmode)
1786 break;
1787 winreg = true;
1788 if (REG_P (op))
1790 if (hard_regno[nop] >= 0
1791 && in_hard_reg_set_p (this_alternative_set,
1792 mode, hard_regno[nop]))
1793 win = true;
1794 else if (hard_regno[nop] < 0
1795 && in_class_p (op, this_alternative, NULL))
1796 win = true;
1798 break;
1800 if (c != ' ' && c != '\t')
1801 costly_p = c == '*';
1803 while ((p += len), c);
1805 /* Record which operands fit this alternative. */
1806 if (win)
1808 this_alternative_win = true;
1809 if (operand_reg[nop] != NULL_RTX)
1811 if (hard_regno[nop] >= 0)
1813 if (in_hard_reg_set_p (this_costly_alternative_set,
1814 mode, hard_regno[nop]))
1815 reject++;
1817 else
1819 /* Prefer won reg to spilled pseudo under other equal
1820 conditions. */
1821 reject++;
1822 if (in_class_p (operand_reg[nop],
1823 this_costly_alternative, NULL))
1824 reject++;
1826 /* We simulate the behaviour of old reload here.
1827 Although scratches need hard registers and it
1828 might result in spilling other pseudos, no reload
1829 insns are generated for the scratches. So it
1830 might cost something but probably less than old
1831 reload pass believes. */
1832 if (lra_former_scratch_p (REGNO (operand_reg[nop])))
1833 reject += LRA_LOSER_COST_FACTOR;
1836 else if (did_match)
1837 this_alternative_match_win = true;
1838 else
1840 int const_to_mem = 0;
1841 bool no_regs_p;
1843 no_regs_p
1844 = (this_alternative == NO_REGS
1845 || (hard_reg_set_subset_p
1846 (reg_class_contents[this_alternative],
1847 lra_no_alloc_regs)));
1848 /* If this operand accepts a register, and if the
1849 register class has at least one allocatable register,
1850 then this operand can be reloaded. */
1851 if (winreg && !no_regs_p)
1852 badop = false;
1854 if (badop)
1855 goto fail;
1857 this_alternative_offmemok = offmemok;
1858 if (this_costly_alternative != NO_REGS)
1859 reject++;
1860 /* If the operand is dying, has a matching constraint,
1861 and satisfies constraints of the matched operand
1862 which failed to satisfy the own constraints, we do
1863 not need to generate a reload insn for this
1864 operand. */
1865 if (!(this_alternative_matches >= 0
1866 && !curr_alt_win[this_alternative_matches]
1867 && REG_P (op)
1868 && find_regno_note (curr_insn, REG_DEAD, REGNO (op))
1869 && (hard_regno[nop] >= 0
1870 ? in_hard_reg_set_p (this_alternative_set,
1871 mode, hard_regno[nop])
1872 : in_class_p (op, this_alternative, NULL))))
1873 losers++;
1874 if (operand_reg[nop] != NULL_RTX
1875 /* Output operands and matched input operands are
1876 not inherited. The following conditions do not
1877 exactly describe the previous statement but they
1878 are pretty close. */
1879 && curr_static_id->operand[nop].type != OP_OUT
1880 && (this_alternative_matches < 0
1881 || curr_static_id->operand[nop].type != OP_IN))
1883 int last_reload = (lra_reg_info[ORIGINAL_REGNO
1884 (operand_reg[nop])]
1885 .last_reload);
1887 if (last_reload > bb_reload_num)
1888 reload_sum += last_reload - bb_reload_num;
1890 /* If this is a constant that is reloaded into the
1891 desired class by copying it to memory first, count
1892 that as another reload. This is consistent with
1893 other code and is required to avoid choosing another
1894 alternative when the constant is moved into memory.
1895 Note that the test here is precisely the same as in
1896 the code below that calls force_const_mem. */
1897 if (CONST_POOL_OK_P (mode, op)
1898 && ((targetm.preferred_reload_class
1899 (op, this_alternative) == NO_REGS)
1900 || no_input_reloads_p))
1902 const_to_mem = 1;
1903 if (! no_regs_p)
1904 losers++;
1907 /* Alternative loses if it requires a type of reload not
1908 permitted for this insn. We can always reload
1909 objects with a REG_UNUSED note. */
1910 if ((curr_static_id->operand[nop].type != OP_IN
1911 && no_output_reloads_p
1912 && ! find_reg_note (curr_insn, REG_UNUSED, op))
1913 || (curr_static_id->operand[nop].type != OP_OUT
1914 && no_input_reloads_p && ! const_to_mem))
1915 goto fail;
1917 /* Check strong discouragement of reload of non-constant
1918 into class THIS_ALTERNATIVE. */
1919 if (! CONSTANT_P (op) && ! no_regs_p
1920 && (targetm.preferred_reload_class
1921 (op, this_alternative) == NO_REGS
1922 || (curr_static_id->operand[nop].type == OP_OUT
1923 && (targetm.preferred_output_reload_class
1924 (op, this_alternative) == NO_REGS))))
1925 reject += LRA_MAX_REJECT;
1927 if (! ((const_to_mem && constmemok)
1928 || (MEM_P (op) && offmemok)))
1930 /* We prefer to reload pseudos over reloading other
1931 things, since such reloads may be able to be
1932 eliminated later. So bump REJECT in other cases.
1933 Don't do this in the case where we are forcing a
1934 constant into memory and it will then win since
1935 we don't want to have a different alternative
1936 match then. */
1937 if (! (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER))
1938 reject += 2;
1940 if (! no_regs_p)
1941 reload_nregs
1942 += ira_reg_class_max_nregs[this_alternative][mode];
1945 /* We are trying to spill pseudo into memory. It is
1946 usually more costly than moving to a hard register
1947 although it might takes the same number of
1948 reloads. */
1949 if (no_regs_p && REG_P (op))
1950 reject++;
1952 #ifdef SECONDARY_MEMORY_NEEDED
1953 /* If reload requires moving value through secondary
1954 memory, it will need one more insn at least. */
1955 if (this_alternative != NO_REGS
1956 && REG_P (op) && (cl = get_reg_class (REGNO (op))) != NO_REGS
1957 && ((curr_static_id->operand[nop].type != OP_OUT
1958 && SECONDARY_MEMORY_NEEDED (cl, this_alternative,
1959 GET_MODE (op)))
1960 || (curr_static_id->operand[nop].type != OP_IN
1961 && SECONDARY_MEMORY_NEEDED (this_alternative, cl,
1962 GET_MODE (op)))))
1963 losers++;
1964 #endif
1965 /* Input reloads can be inherited more often than output
1966 reloads can be removed, so penalize output
1967 reloads. */
1968 if (!REG_P (op) || curr_static_id->operand[nop].type != OP_IN)
1969 reject++;
1972 if (early_clobber_p)
1973 reject++;
1974 /* ??? We check early clobbers after processing all operands
1975 (see loop below) and there we update the costs more.
1976 Should we update the cost (may be approximately) here
1977 because of early clobber register reloads or it is a rare
1978 or non-important thing to be worth to do it. */
1979 overall = losers * LRA_LOSER_COST_FACTOR + reject;
1980 if ((best_losers == 0 || losers != 0) && best_overall < overall)
1981 goto fail;
1983 curr_alt[nop] = this_alternative;
1984 COPY_HARD_REG_SET (curr_alt_set[nop], this_alternative_set);
1985 curr_alt_win[nop] = this_alternative_win;
1986 curr_alt_match_win[nop] = this_alternative_match_win;
1987 curr_alt_offmemok[nop] = this_alternative_offmemok;
1988 curr_alt_matches[nop] = this_alternative_matches;
1990 if (this_alternative_matches >= 0
1991 && !did_match && !this_alternative_win)
1992 curr_alt_win[this_alternative_matches] = false;
1994 if (early_clobber_p && operand_reg[nop] != NULL_RTX)
1995 early_clobbered_nops[early_clobbered_regs_num++] = nop;
1997 ok_p = true;
1998 curr_alt_dont_inherit_ops_num = 0;
1999 for (nop = 0; nop < early_clobbered_regs_num; nop++)
2001 int i, j, clobbered_hard_regno;
2002 HARD_REG_SET temp_set;
2004 i = early_clobbered_nops[nop];
2005 if ((! curr_alt_win[i] && ! curr_alt_match_win[i])
2006 || hard_regno[i] < 0)
2007 continue;
2008 clobbered_hard_regno = hard_regno[i];
2009 CLEAR_HARD_REG_SET (temp_set);
2010 add_to_hard_reg_set (&temp_set, biggest_mode[i], clobbered_hard_regno);
2011 for (j = 0; j < n_operands; j++)
2012 if (j == i
2013 /* We don't want process insides of match_operator and
2014 match_parallel because otherwise we would process
2015 their operands once again generating a wrong
2016 code. */
2017 || curr_static_id->operand[j].is_operator)
2018 continue;
2019 else if ((curr_alt_matches[j] == i && curr_alt_match_win[j])
2020 || (curr_alt_matches[i] == j && curr_alt_match_win[i]))
2021 continue;
2022 else if (uses_hard_regs_p (*curr_id->operand_loc[j], temp_set))
2023 break;
2024 if (j >= n_operands)
2025 continue;
2026 /* We need to reload early clobbered register. */
2027 for (j = 0; j < n_operands; j++)
2028 if (curr_alt_matches[j] == i)
2030 curr_alt_match_win[j] = false;
2031 losers++;
2032 overall += LRA_LOSER_COST_FACTOR;
2034 if (! curr_alt_match_win[i])
2035 curr_alt_dont_inherit_ops[curr_alt_dont_inherit_ops_num++] = i;
2036 else
2038 /* Remember pseudos used for match reloads are never
2039 inherited. */
2040 lra_assert (curr_alt_matches[i] >= 0);
2041 curr_alt_win[curr_alt_matches[i]] = false;
2043 curr_alt_win[i] = curr_alt_match_win[i] = false;
2044 losers++;
2045 overall += LRA_LOSER_COST_FACTOR;
2047 small_class_operands_num = 0;
2048 for (nop = 0; nop < n_operands; nop++)
2049 small_class_operands_num
2050 += SMALL_REGISTER_CLASS_P (curr_alt[nop]) ? 1 : 0;
2052 /* If this alternative can be made to work by reloading, and it
2053 needs less reloading than the others checked so far, record
2054 it as the chosen goal for reloading. */
2055 if ((best_losers != 0 && losers == 0)
2056 || (((best_losers == 0 && losers == 0)
2057 || (best_losers != 0 && losers != 0))
2058 && (best_overall > overall
2059 || (best_overall == overall
2060 /* If the cost of the reloads is the same,
2061 prefer alternative which requires minimal
2062 number of small register classes for the
2063 operands. This improves chances of reloads
2064 for insn requiring small register
2065 classes. */
2066 && (small_class_operands_num
2067 < best_small_class_operands_num
2068 || (small_class_operands_num
2069 == best_small_class_operands_num
2070 && (reload_nregs < best_reload_nregs
2071 || (reload_nregs == best_reload_nregs
2072 && best_reload_sum < reload_sum))))))))
2074 for (nop = 0; nop < n_operands; nop++)
2076 goal_alt_win[nop] = curr_alt_win[nop];
2077 goal_alt_match_win[nop] = curr_alt_match_win[nop];
2078 goal_alt_matches[nop] = curr_alt_matches[nop];
2079 goal_alt[nop] = curr_alt[nop];
2080 goal_alt_offmemok[nop] = curr_alt_offmemok[nop];
2082 goal_alt_dont_inherit_ops_num = curr_alt_dont_inherit_ops_num;
2083 for (nop = 0; nop < curr_alt_dont_inherit_ops_num; nop++)
2084 goal_alt_dont_inherit_ops[nop] = curr_alt_dont_inherit_ops[nop];
2085 goal_alt_swapped = curr_swapped;
2086 best_overall = overall;
2087 best_losers = losers;
2088 best_small_class_operands_num = small_class_operands_num;
2089 best_reload_nregs = reload_nregs;
2090 best_reload_sum = reload_sum;
2091 goal_alt_number = nalt;
2093 if (losers == 0)
2094 /* Everything is satisfied. Do not process alternatives
2095 anymore. */
2096 break;
2097 fail:
2100 return ok_p;
2103 /* Return 1 if ADDR is a valid memory address for mode MODE in address
2104 space AS, and check that each pseudo has the proper kind of hard
2105 reg. */
2106 static int
2107 valid_address_p (enum machine_mode mode ATTRIBUTE_UNUSED,
2108 rtx addr, addr_space_t as)
2110 #ifdef GO_IF_LEGITIMATE_ADDRESS
2111 lra_assert (ADDR_SPACE_GENERIC_P (as));
2112 GO_IF_LEGITIMATE_ADDRESS (mode, addr, win);
2113 return 0;
2115 win:
2116 return 1;
2117 #else
2118 return targetm.addr_space.legitimate_address_p (mode, addr, 0, as);
2119 #endif
2122 /* Return whether address AD is valid. */
2124 static bool
2125 valid_address_p (struct address_info *ad)
2127 /* Some ports do not check displacements for eliminable registers,
2128 so we replace them temporarily with the elimination target. */
2129 rtx saved_base_reg = NULL_RTX;
2130 rtx saved_index_reg = NULL_RTX;
2131 rtx *base_term = strip_subreg (ad->base_term);
2132 rtx *index_term = strip_subreg (ad->index_term);
2133 if (base_term != NULL)
2135 saved_base_reg = *base_term;
2136 lra_eliminate_reg_if_possible (base_term);
2137 if (ad->base_term2 != NULL)
2138 *ad->base_term2 = *ad->base_term;
2140 if (index_term != NULL)
2142 saved_index_reg = *index_term;
2143 lra_eliminate_reg_if_possible (index_term);
2145 bool ok_p = valid_address_p (ad->mode, *ad->outer, ad->as);
2146 if (saved_base_reg != NULL_RTX)
2148 *base_term = saved_base_reg;
2149 if (ad->base_term2 != NULL)
2150 *ad->base_term2 = *ad->base_term;
2152 if (saved_index_reg != NULL_RTX)
2153 *index_term = saved_index_reg;
2154 return ok_p;
2157 /* Make reload base reg + disp from address AD. Return the new pseudo. */
2158 static rtx
2159 base_plus_disp_to_reg (struct address_info *ad)
2161 enum reg_class cl;
2162 rtx new_reg;
2164 lra_assert (ad->base == ad->base_term && ad->disp == ad->disp_term);
2165 cl = base_reg_class (ad->mode, ad->as, ad->base_outer_code,
2166 get_index_code (ad));
2167 new_reg = lra_create_new_reg (GET_MODE (*ad->base_term), NULL_RTX,
2168 cl, "base + disp");
2169 lra_emit_add (new_reg, *ad->base_term, *ad->disp_term);
2170 return new_reg;
2173 /* Return true if we can add a displacement to address AD, even if that
2174 makes the address invalid. The fix-up code requires any new address
2175 to be the sum of the BASE_TERM, INDEX and DISP_TERM fields. */
2176 static bool
2177 can_add_disp_p (struct address_info *ad)
2179 return (!ad->autoinc_p
2180 && ad->segment == NULL
2181 && ad->base == ad->base_term
2182 && ad->disp == ad->disp_term);
2185 /* Make equiv substitution in address AD. Return true if a substitution
2186 was made. */
2187 static bool
2188 equiv_address_substitution (struct address_info *ad)
2190 rtx base_reg, new_base_reg, index_reg, new_index_reg, *base_term, *index_term;
2191 HOST_WIDE_INT disp, scale;
2192 bool change_p;
2194 base_term = strip_subreg (ad->base_term);
2195 if (base_term == NULL)
2196 base_reg = new_base_reg = NULL_RTX;
2197 else
2199 base_reg = *base_term;
2200 new_base_reg = get_equiv_substitution (base_reg);
2202 index_term = strip_subreg (ad->index_term);
2203 if (index_term == NULL)
2204 index_reg = new_index_reg = NULL_RTX;
2205 else
2207 index_reg = *index_term;
2208 new_index_reg = get_equiv_substitution (index_reg);
2210 if (base_reg == new_base_reg && index_reg == new_index_reg)
2211 return false;
2212 disp = 0;
2213 change_p = false;
2214 if (lra_dump_file != NULL)
2216 fprintf (lra_dump_file, "Changing address in insn %d ",
2217 INSN_UID (curr_insn));
2218 dump_value_slim (lra_dump_file, *ad->outer, 1);
2220 if (base_reg != new_base_reg)
2222 if (REG_P (new_base_reg))
2224 *base_term = new_base_reg;
2225 change_p = true;
2227 else if (GET_CODE (new_base_reg) == PLUS
2228 && REG_P (XEXP (new_base_reg, 0))
2229 && CONST_INT_P (XEXP (new_base_reg, 1))
2230 && can_add_disp_p (ad))
2232 disp += INTVAL (XEXP (new_base_reg, 1));
2233 *base_term = XEXP (new_base_reg, 0);
2234 change_p = true;
2236 if (ad->base_term2 != NULL)
2237 *ad->base_term2 = *ad->base_term;
2239 if (index_reg != new_index_reg)
2241 if (REG_P (new_index_reg))
2243 *index_term = new_index_reg;
2244 change_p = true;
2246 else if (GET_CODE (new_index_reg) == PLUS
2247 && REG_P (XEXP (new_index_reg, 0))
2248 && CONST_INT_P (XEXP (new_index_reg, 1))
2249 && can_add_disp_p (ad)
2250 && (scale = get_index_scale (ad)))
2252 disp += INTVAL (XEXP (new_index_reg, 1)) * scale;
2253 *index_term = XEXP (new_index_reg, 0);
2254 change_p = true;
2257 if (disp != 0)
2259 if (ad->disp != NULL)
2260 *ad->disp = plus_constant (GET_MODE (*ad->inner), *ad->disp, disp);
2261 else
2263 *ad->inner = plus_constant (GET_MODE (*ad->inner), *ad->inner, disp);
2264 update_address (ad);
2266 change_p = true;
2268 if (lra_dump_file != NULL)
2270 if (! change_p)
2271 fprintf (lra_dump_file, " -- no change\n");
2272 else
2274 fprintf (lra_dump_file, " on equiv ");
2275 dump_value_slim (lra_dump_file, *ad->outer, 1);
2276 fprintf (lra_dump_file, "\n");
2279 return change_p;
2282 /* Major function to make reloads for an address in operand NOP.
2283 The supported cases are:
2285 1) an address that existed before LRA started, at which point it must
2286 have been valid. These addresses are subject to elimination and
2287 may have become invalid due to the elimination offset being out
2288 of range.
2290 2) an address created by forcing a constant to memory (force_const_to_mem).
2291 The initial form of these addresses might not be valid, and it is this
2292 function's job to make them valid.
2294 3) a frame address formed from a register and a (possibly zero)
2295 constant offset. As above, these addresses might not be valid
2296 and this function must make them so.
2298 Add reloads to the lists *BEFORE and *AFTER. We might need to add
2299 reloads to *AFTER because of inc/dec, {pre, post} modify in the
2300 address. Return true for any RTL change. */
2301 static bool
2302 process_address (int nop, rtx *before, rtx *after)
2304 struct address_info ad;
2305 rtx new_reg;
2306 rtx op = *curr_id->operand_loc[nop];
2307 const char *constraint = curr_static_id->operand[nop].constraint;
2308 bool change_p;
2310 if (constraint[0] == 'p'
2311 || EXTRA_ADDRESS_CONSTRAINT (constraint[0], constraint))
2312 decompose_lea_address (&ad, curr_id->operand_loc[nop]);
2313 else if (MEM_P (op))
2314 decompose_mem_address (&ad, op);
2315 else if (GET_CODE (op) == SUBREG
2316 && MEM_P (SUBREG_REG (op)))
2317 decompose_mem_address (&ad, SUBREG_REG (op));
2318 else
2319 return false;
2320 change_p = equiv_address_substitution (&ad);
2321 if (ad.base_term != NULL
2322 && (process_addr_reg
2323 (ad.base_term, before,
2324 (ad.autoinc_p
2325 && !(REG_P (*ad.base_term)
2326 && find_regno_note (curr_insn, REG_DEAD,
2327 REGNO (*ad.base_term)) != NULL_RTX)
2328 ? after : NULL),
2329 base_reg_class (ad.mode, ad.as, ad.base_outer_code,
2330 get_index_code (&ad)))))
2332 change_p = true;
2333 if (ad.base_term2 != NULL)
2334 *ad.base_term2 = *ad.base_term;
2336 if (ad.index_term != NULL
2337 && process_addr_reg (ad.index_term, before, NULL, INDEX_REG_CLASS))
2338 change_p = true;
2340 /* There are three cases where the shape of *AD.INNER may now be invalid:
2342 1) the original address was valid, but either elimination or
2343 equiv_address_substitution applied a displacement that made
2344 it invalid.
2346 2) the address is an invalid symbolic address created by
2347 force_const_to_mem.
2349 3) the address is a frame address with an invalid offset.
2351 All these cases involve a displacement and a non-autoinc address,
2352 so there is no point revalidating other types. */
2353 if (ad.disp == NULL || ad.autoinc_p || valid_address_p (&ad))
2354 return change_p;
2356 /* Any index existed before LRA started, so we can assume that the
2357 presence and shape of the index is valid. */
2358 push_to_sequence (*before);
2359 gcc_assert (ad.segment == NULL);
2360 gcc_assert (ad.disp == ad.disp_term);
2361 if (ad.base == NULL)
2363 if (ad.index == NULL)
2365 int code = -1;
2366 enum reg_class cl = base_reg_class (ad.mode, ad.as,
2367 SCRATCH, SCRATCH);
2368 rtx disp = *ad.disp;
2370 new_reg = lra_create_new_reg (Pmode, NULL_RTX, cl, "disp");
2371 #ifdef HAVE_lo_sum
2373 rtx insn;
2374 rtx last = get_last_insn ();
2376 /* disp => lo_sum (new_base, disp), case (2) above. */
2377 insn = emit_insn (gen_rtx_SET
2378 (VOIDmode, new_reg,
2379 gen_rtx_HIGH (Pmode, copy_rtx (disp))));
2380 code = recog_memoized (insn);
2381 if (code >= 0)
2383 *ad.disp = gen_rtx_LO_SUM (Pmode, new_reg, disp);
2384 if (! valid_address_p (ad.mode, *ad.outer, ad.as))
2386 *ad.disp = disp;
2387 code = -1;
2390 if (code < 0)
2391 delete_insns_since (last);
2393 #endif
2394 if (code < 0)
2396 /* disp => new_base, case (2) above. */
2397 lra_emit_move (new_reg, disp);
2398 *ad.disp = new_reg;
2401 else
2403 /* index * scale + disp => new base + index * scale,
2404 case (1) above. */
2405 enum reg_class cl = base_reg_class (ad.mode, ad.as, PLUS,
2406 GET_CODE (*ad.index));
2408 lra_assert (INDEX_REG_CLASS != NO_REGS);
2409 new_reg = lra_create_new_reg (Pmode, NULL_RTX, cl, "disp");
2410 lra_emit_move (new_reg, *ad.disp);
2411 *ad.inner = simplify_gen_binary (PLUS, GET_MODE (new_reg),
2412 new_reg, *ad.index);
2415 else if (ad.index == NULL)
2417 /* base + disp => new base, cases (1) and (3) above. */
2418 /* Another option would be to reload the displacement into an
2419 index register. However, postreload has code to optimize
2420 address reloads that have the same base and different
2421 displacements, so reloading into an index register would
2422 not necessarily be a win. */
2423 new_reg = base_plus_disp_to_reg (&ad);
2424 *ad.inner = new_reg;
2426 else
2428 /* base + scale * index + disp => new base + scale * index,
2429 case (1) above. */
2430 new_reg = base_plus_disp_to_reg (&ad);
2431 *ad.inner = simplify_gen_binary (PLUS, GET_MODE (new_reg),
2432 new_reg, *ad.index);
2434 *before = get_insns ();
2435 end_sequence ();
2436 return true;
2439 /* Emit insns to reload VALUE into a new register. VALUE is an
2440 auto-increment or auto-decrement RTX whose operand is a register or
2441 memory location; so reloading involves incrementing that location.
2442 IN is either identical to VALUE, or some cheaper place to reload
2443 value being incremented/decremented from.
2445 INC_AMOUNT is the number to increment or decrement by (always
2446 positive and ignored for POST_MODIFY/PRE_MODIFY).
2448 Return pseudo containing the result. */
2449 static rtx
2450 emit_inc (enum reg_class new_rclass, rtx in, rtx value, int inc_amount)
2452 /* REG or MEM to be copied and incremented. */
2453 rtx incloc = XEXP (value, 0);
2454 /* Nonzero if increment after copying. */
2455 int post = (GET_CODE (value) == POST_DEC || GET_CODE (value) == POST_INC
2456 || GET_CODE (value) == POST_MODIFY);
2457 rtx last;
2458 rtx inc;
2459 rtx add_insn;
2460 int code;
2461 rtx real_in = in == value ? incloc : in;
2462 rtx result;
2463 bool plus_p = true;
2465 if (GET_CODE (value) == PRE_MODIFY || GET_CODE (value) == POST_MODIFY)
2467 lra_assert (GET_CODE (XEXP (value, 1)) == PLUS
2468 || GET_CODE (XEXP (value, 1)) == MINUS);
2469 lra_assert (rtx_equal_p (XEXP (XEXP (value, 1), 0), XEXP (value, 0)));
2470 plus_p = GET_CODE (XEXP (value, 1)) == PLUS;
2471 inc = XEXP (XEXP (value, 1), 1);
2473 else
2475 if (GET_CODE (value) == PRE_DEC || GET_CODE (value) == POST_DEC)
2476 inc_amount = -inc_amount;
2478 inc = GEN_INT (inc_amount);
2481 if (! post && REG_P (incloc))
2482 result = incloc;
2483 else
2484 result = lra_create_new_reg (GET_MODE (value), value, new_rclass,
2485 "INC/DEC result");
2487 if (real_in != result)
2489 /* First copy the location to the result register. */
2490 lra_assert (REG_P (result));
2491 emit_insn (gen_move_insn (result, real_in));
2494 /* We suppose that there are insns to add/sub with the constant
2495 increment permitted in {PRE/POST)_{DEC/INC/MODIFY}. At least the
2496 old reload worked with this assumption. If the assumption
2497 becomes wrong, we should use approach in function
2498 base_plus_disp_to_reg. */
2499 if (in == value)
2501 /* See if we can directly increment INCLOC. */
2502 last = get_last_insn ();
2503 add_insn = emit_insn (plus_p
2504 ? gen_add2_insn (incloc, inc)
2505 : gen_sub2_insn (incloc, inc));
2507 code = recog_memoized (add_insn);
2508 if (code >= 0)
2510 if (! post && result != incloc)
2511 emit_insn (gen_move_insn (result, incloc));
2512 return result;
2514 delete_insns_since (last);
2517 /* If couldn't do the increment directly, must increment in RESULT.
2518 The way we do this depends on whether this is pre- or
2519 post-increment. For pre-increment, copy INCLOC to the reload
2520 register, increment it there, then save back. */
2521 if (! post)
2523 if (real_in != result)
2524 emit_insn (gen_move_insn (result, real_in));
2525 if (plus_p)
2526 emit_insn (gen_add2_insn (result, inc));
2527 else
2528 emit_insn (gen_sub2_insn (result, inc));
2529 if (result != incloc)
2530 emit_insn (gen_move_insn (incloc, result));
2532 else
2534 /* Post-increment.
2536 Because this might be a jump insn or a compare, and because
2537 RESULT may not be available after the insn in an input
2538 reload, we must do the incrementing before the insn being
2539 reloaded for.
2541 We have already copied IN to RESULT. Increment the copy in
2542 RESULT, save that back, then decrement RESULT so it has
2543 the original value. */
2544 if (plus_p)
2545 emit_insn (gen_add2_insn (result, inc));
2546 else
2547 emit_insn (gen_sub2_insn (result, inc));
2548 emit_insn (gen_move_insn (incloc, result));
2549 /* Restore non-modified value for the result. We prefer this
2550 way because it does not require an additional hard
2551 register. */
2552 if (plus_p)
2554 if (CONST_INT_P (inc))
2555 emit_insn (gen_add2_insn (result, GEN_INT (-INTVAL (inc))));
2556 else
2557 emit_insn (gen_sub2_insn (result, inc));
2559 else
2560 emit_insn (gen_add2_insn (result, inc));
2562 return result;
2565 /* Swap operands NOP and NOP + 1. */
2566 static inline void
2567 swap_operands (int nop)
2569 enum machine_mode mode = curr_operand_mode[nop];
2570 curr_operand_mode[nop] = curr_operand_mode[nop + 1];
2571 curr_operand_mode[nop + 1] = mode;
2572 rtx x = *curr_id->operand_loc[nop];
2573 *curr_id->operand_loc[nop] = *curr_id->operand_loc[nop + 1];
2574 *curr_id->operand_loc[nop + 1] = x;
2575 /* Swap the duplicates too. */
2576 lra_update_dup (curr_id, nop);
2577 lra_update_dup (curr_id, nop + 1);
2580 /* Main entry point of the constraint code: search the body of the
2581 current insn to choose the best alternative. It is mimicking insn
2582 alternative cost calculation model of former reload pass. That is
2583 because machine descriptions were written to use this model. This
2584 model can be changed in future. Make commutative operand exchange
2585 if it is chosen.
2587 Return true if some RTL changes happened during function call. */
2588 static bool
2589 curr_insn_transform (void)
2591 int i, j, k;
2592 int n_operands;
2593 int n_alternatives;
2594 int commutative;
2595 signed char goal_alt_matched[MAX_RECOG_OPERANDS][MAX_RECOG_OPERANDS];
2596 rtx before, after;
2597 bool alt_p = false;
2598 /* Flag that the insn has been changed through a transformation. */
2599 bool change_p;
2600 bool sec_mem_p;
2601 #ifdef SECONDARY_MEMORY_NEEDED
2602 bool use_sec_mem_p;
2603 #endif
2604 int max_regno_before;
2605 int reused_alternative_num;
2607 no_input_reloads_p = no_output_reloads_p = false;
2608 goal_alt_number = -1;
2610 if (check_and_process_move (&change_p, &sec_mem_p))
2611 return change_p;
2613 /* JUMP_INSNs and CALL_INSNs are not allowed to have any output
2614 reloads; neither are insns that SET cc0. Insns that use CC0 are
2615 not allowed to have any input reloads. */
2616 if (JUMP_P (curr_insn) || CALL_P (curr_insn))
2617 no_output_reloads_p = true;
2619 #ifdef HAVE_cc0
2620 if (reg_referenced_p (cc0_rtx, PATTERN (curr_insn)))
2621 no_input_reloads_p = true;
2622 if (reg_set_p (cc0_rtx, PATTERN (curr_insn)))
2623 no_output_reloads_p = true;
2624 #endif
2626 n_operands = curr_static_id->n_operands;
2627 n_alternatives = curr_static_id->n_alternatives;
2629 /* Just return "no reloads" if insn has no operands with
2630 constraints. */
2631 if (n_operands == 0 || n_alternatives == 0)
2632 return false;
2634 max_regno_before = max_reg_num ();
2636 for (i = 0; i < n_operands; i++)
2638 goal_alt_matched[i][0] = -1;
2639 goal_alt_matches[i] = -1;
2642 commutative = curr_static_id->commutative;
2644 /* Now see what we need for pseudos that didn't get hard regs or got
2645 the wrong kind of hard reg. For this, we must consider all the
2646 operands together against the register constraints. */
2648 best_losers = best_overall = INT_MAX;
2649 best_small_class_operands_num = best_reload_sum = 0;
2651 curr_swapped = false;
2652 goal_alt_swapped = false;
2654 /* Make equivalence substitution and memory subreg elimination
2655 before address processing because an address legitimacy can
2656 depend on memory mode. */
2657 for (i = 0; i < n_operands; i++)
2659 rtx op = *curr_id->operand_loc[i];
2660 rtx subst, old = op;
2661 bool op_change_p = false;
2663 if (GET_CODE (old) == SUBREG)
2664 old = SUBREG_REG (old);
2665 subst = get_equiv_substitution (old);
2666 if (subst != old)
2668 subst = copy_rtx (subst);
2669 lra_assert (REG_P (old));
2670 if (GET_CODE (op) == SUBREG)
2671 SUBREG_REG (op) = subst;
2672 else
2673 *curr_id->operand_loc[i] = subst;
2674 if (lra_dump_file != NULL)
2676 fprintf (lra_dump_file,
2677 "Changing pseudo %d in operand %i of insn %u on equiv ",
2678 REGNO (old), i, INSN_UID (curr_insn));
2679 dump_value_slim (lra_dump_file, subst, 1);
2680 fprintf (lra_dump_file, "\n");
2682 op_change_p = change_p = true;
2684 if (simplify_operand_subreg (i, GET_MODE (old)) || op_change_p)
2686 change_p = true;
2687 lra_update_dup (curr_id, i);
2691 /* Reload address registers and displacements. We do it before
2692 finding an alternative because of memory constraints. */
2693 before = after = NULL_RTX;
2694 for (i = 0; i < n_operands; i++)
2695 if (! curr_static_id->operand[i].is_operator
2696 && process_address (i, &before, &after))
2698 change_p = true;
2699 lra_update_dup (curr_id, i);
2702 if (change_p)
2703 /* If we've changed the instruction then any alternative that
2704 we chose previously may no longer be valid. */
2705 lra_set_used_insn_alternative (curr_insn, -1);
2707 try_swapped:
2709 reused_alternative_num = curr_id->used_insn_alternative;
2710 if (lra_dump_file != NULL && reused_alternative_num >= 0)
2711 fprintf (lra_dump_file, "Reusing alternative %d for insn #%u\n",
2712 reused_alternative_num, INSN_UID (curr_insn));
2714 if (process_alt_operands (reused_alternative_num))
2715 alt_p = true;
2717 /* If insn is commutative (it's safe to exchange a certain pair of
2718 operands) then we need to try each alternative twice, the second
2719 time matching those two operands as if we had exchanged them. To
2720 do this, really exchange them in operands.
2722 If we have just tried the alternatives the second time, return
2723 operands to normal and drop through. */
2725 if (reused_alternative_num < 0 && commutative >= 0)
2727 curr_swapped = !curr_swapped;
2728 if (curr_swapped)
2730 swap_operands (commutative);
2731 goto try_swapped;
2733 else
2734 swap_operands (commutative);
2737 /* The operands don't meet the constraints. goal_alt describes the
2738 alternative that we could reach by reloading the fewest operands.
2739 Reload so as to fit it. */
2741 if (! alt_p && ! sec_mem_p)
2743 /* No alternative works with reloads?? */
2744 if (INSN_CODE (curr_insn) >= 0)
2745 fatal_insn ("unable to generate reloads for:", curr_insn);
2746 error_for_asm (curr_insn,
2747 "inconsistent operand constraints in an %<asm%>");
2748 /* Avoid further trouble with this insn. */
2749 PATTERN (curr_insn) = gen_rtx_USE (VOIDmode, const0_rtx);
2750 lra_invalidate_insn_data (curr_insn);
2751 return true;
2754 /* If the best alternative is with operands 1 and 2 swapped, swap
2755 them. Update the operand numbers of any reloads already
2756 pushed. */
2758 if (goal_alt_swapped)
2760 if (lra_dump_file != NULL)
2761 fprintf (lra_dump_file, " Commutative operand exchange in insn %u\n",
2762 INSN_UID (curr_insn));
2764 /* Swap the duplicates too. */
2765 swap_operands (commutative);
2766 change_p = true;
2769 #ifdef SECONDARY_MEMORY_NEEDED
2770 /* Some target macros SECONDARY_MEMORY_NEEDED (e.g. x86) are defined
2771 too conservatively. So we use the secondary memory only if there
2772 is no any alternative without reloads. */
2773 use_sec_mem_p = false;
2774 if (! alt_p)
2775 use_sec_mem_p = true;
2776 else if (sec_mem_p)
2778 for (i = 0; i < n_operands; i++)
2779 if (! goal_alt_win[i] && ! goal_alt_match_win[i])
2780 break;
2781 use_sec_mem_p = i < n_operands;
2784 if (use_sec_mem_p)
2786 rtx new_reg, set, src, dest;
2787 enum machine_mode sec_mode;
2789 lra_assert (sec_mem_p);
2790 set = single_set (curr_insn);
2791 lra_assert (set != NULL_RTX && ! side_effects_p (set));
2792 dest = SET_DEST (set);
2793 src = SET_SRC (set);
2794 #ifdef SECONDARY_MEMORY_NEEDED_MODE
2795 sec_mode = SECONDARY_MEMORY_NEEDED_MODE (GET_MODE (src));
2796 #else
2797 sec_mode = GET_MODE (src);
2798 #endif
2799 new_reg = lra_create_new_reg (sec_mode, NULL_RTX,
2800 NO_REGS, "secondary");
2801 /* If the mode is changed, it should be wider. */
2802 lra_assert (GET_MODE_SIZE (GET_MODE (new_reg))
2803 >= GET_MODE_SIZE (GET_MODE (src)));
2804 after = emit_spill_move (false, new_reg, dest);
2805 lra_process_new_insns (curr_insn, NULL_RTX, after,
2806 "Inserting the sec. move");
2807 before = emit_spill_move (true, new_reg, src);
2808 lra_process_new_insns (curr_insn, before, NULL_RTX, "Changing on");
2809 lra_set_insn_deleted (curr_insn);
2810 return true;
2812 #endif
2814 lra_assert (goal_alt_number >= 0);
2815 lra_set_used_insn_alternative (curr_insn, goal_alt_number);
2817 if (lra_dump_file != NULL)
2819 const char *p;
2821 fprintf (lra_dump_file, " Choosing alt %d in insn %u:",
2822 goal_alt_number, INSN_UID (curr_insn));
2823 for (i = 0; i < n_operands; i++)
2825 p = (curr_static_id->operand_alternative
2826 [goal_alt_number * n_operands + i].constraint);
2827 if (*p == '\0')
2828 continue;
2829 fprintf (lra_dump_file, " (%d) ", i);
2830 for (; *p != '\0' && *p != ',' && *p != '#'; p++)
2831 fputc (*p, lra_dump_file);
2833 fprintf (lra_dump_file, "\n");
2836 /* Right now, for any pair of operands I and J that are required to
2837 match, with J < I, goal_alt_matches[I] is J. Add I to
2838 goal_alt_matched[J]. */
2840 for (i = 0; i < n_operands; i++)
2841 if ((j = goal_alt_matches[i]) >= 0)
2843 for (k = 0; goal_alt_matched[j][k] >= 0; k++)
2845 /* We allow matching one output operand and several input
2846 operands. */
2847 lra_assert (k == 0
2848 || (curr_static_id->operand[j].type == OP_OUT
2849 && curr_static_id->operand[i].type == OP_IN
2850 && (curr_static_id->operand
2851 [goal_alt_matched[j][0]].type == OP_IN)));
2852 goal_alt_matched[j][k] = i;
2853 goal_alt_matched[j][k + 1] = -1;
2856 for (i = 0; i < n_operands; i++)
2857 goal_alt_win[i] |= goal_alt_match_win[i];
2859 /* Any constants that aren't allowed and can't be reloaded into
2860 registers are here changed into memory references. */
2861 for (i = 0; i < n_operands; i++)
2862 if (goal_alt_win[i])
2864 int regno;
2865 enum reg_class new_class;
2866 rtx reg = *curr_id->operand_loc[i];
2868 if (GET_CODE (reg) == SUBREG)
2869 reg = SUBREG_REG (reg);
2871 if (REG_P (reg) && (regno = REGNO (reg)) >= FIRST_PSEUDO_REGISTER)
2873 bool ok_p = in_class_p (reg, goal_alt[i], &new_class);
2875 if (new_class != NO_REGS && get_reg_class (regno) != new_class)
2877 lra_assert (ok_p);
2878 change_class (regno, new_class, " Change", true);
2882 else
2884 const char *constraint;
2885 char c;
2886 rtx op = *curr_id->operand_loc[i];
2887 rtx subreg = NULL_RTX;
2888 enum machine_mode mode = curr_operand_mode[i];
2890 if (GET_CODE (op) == SUBREG)
2892 subreg = op;
2893 op = SUBREG_REG (op);
2894 mode = GET_MODE (op);
2897 if (CONST_POOL_OK_P (mode, op)
2898 && ((targetm.preferred_reload_class
2899 (op, (enum reg_class) goal_alt[i]) == NO_REGS)
2900 || no_input_reloads_p))
2902 rtx tem = force_const_mem (mode, op);
2904 change_p = true;
2905 if (subreg != NULL_RTX)
2906 tem = gen_rtx_SUBREG (mode, tem, SUBREG_BYTE (subreg));
2908 *curr_id->operand_loc[i] = tem;
2909 lra_update_dup (curr_id, i);
2910 process_address (i, &before, &after);
2912 /* If the alternative accepts constant pool refs directly
2913 there will be no reload needed at all. */
2914 if (subreg != NULL_RTX)
2915 continue;
2916 /* Skip alternatives before the one requested. */
2917 constraint = (curr_static_id->operand_alternative
2918 [goal_alt_number * n_operands + i].constraint);
2919 for (;
2920 (c = *constraint) && c != ',' && c != '#';
2921 constraint += CONSTRAINT_LEN (c, constraint))
2923 if (c == TARGET_MEM_CONSTRAINT || c == 'o')
2924 break;
2925 #ifdef EXTRA_CONSTRAINT_STR
2926 if (EXTRA_MEMORY_CONSTRAINT (c, constraint)
2927 && EXTRA_CONSTRAINT_STR (tem, c, constraint))
2928 break;
2929 #endif
2931 if (c == '\0' || c == ',' || c == '#')
2932 continue;
2934 goal_alt_win[i] = true;
2938 for (i = 0; i < n_operands; i++)
2940 rtx old, new_reg;
2941 rtx op = *curr_id->operand_loc[i];
2943 if (goal_alt_win[i])
2945 if (goal_alt[i] == NO_REGS
2946 && REG_P (op)
2947 /* When we assign NO_REGS it means that we will not
2948 assign a hard register to the scratch pseudo by
2949 assigment pass and the scratch pseudo will be
2950 spilled. Spilled scratch pseudos are transformed
2951 back to scratches at the LRA end. */
2952 && lra_former_scratch_operand_p (curr_insn, i))
2953 change_class (REGNO (op), NO_REGS, " Change", true);
2954 continue;
2957 /* Operands that match previous ones have already been handled. */
2958 if (goal_alt_matches[i] >= 0)
2959 continue;
2961 /* We should not have an operand with a non-offsettable address
2962 appearing where an offsettable address will do. It also may
2963 be a case when the address should be special in other words
2964 not a general one (e.g. it needs no index reg). */
2965 if (goal_alt_matched[i][0] == -1 && goal_alt_offmemok[i] && MEM_P (op))
2967 enum reg_class rclass;
2968 rtx *loc = &XEXP (op, 0);
2969 enum rtx_code code = GET_CODE (*loc);
2971 push_to_sequence (before);
2972 rclass = base_reg_class (GET_MODE (op), MEM_ADDR_SPACE (op),
2973 MEM, SCRATCH);
2974 if (GET_RTX_CLASS (code) == RTX_AUTOINC)
2975 new_reg = emit_inc (rclass, *loc, *loc,
2976 /* This value does not matter for MODIFY. */
2977 GET_MODE_SIZE (GET_MODE (op)));
2978 else if (get_reload_reg (OP_IN, Pmode, *loc, rclass,
2979 "offsetable address", &new_reg))
2980 lra_emit_move (new_reg, *loc);
2981 before = get_insns ();
2982 end_sequence ();
2983 *loc = new_reg;
2984 lra_update_dup (curr_id, i);
2986 else if (goal_alt_matched[i][0] == -1)
2988 enum machine_mode mode;
2989 rtx reg, *loc;
2990 int hard_regno, byte;
2991 enum op_type type = curr_static_id->operand[i].type;
2993 loc = curr_id->operand_loc[i];
2994 mode = curr_operand_mode[i];
2995 if (GET_CODE (*loc) == SUBREG)
2997 reg = SUBREG_REG (*loc);
2998 byte = SUBREG_BYTE (*loc);
2999 if (REG_P (reg)
3000 /* Strict_low_part requires reload the register not
3001 the sub-register. */
3002 && (curr_static_id->operand[i].strict_low
3003 || (GET_MODE_SIZE (mode)
3004 <= GET_MODE_SIZE (GET_MODE (reg))
3005 && (hard_regno
3006 = get_try_hard_regno (REGNO (reg))) >= 0
3007 && (simplify_subreg_regno
3008 (hard_regno,
3009 GET_MODE (reg), byte, mode) < 0)
3010 && (goal_alt[i] == NO_REGS
3011 || (simplify_subreg_regno
3012 (ira_class_hard_regs[goal_alt[i]][0],
3013 GET_MODE (reg), byte, mode) >= 0)))))
3015 loc = &SUBREG_REG (*loc);
3016 mode = GET_MODE (*loc);
3019 old = *loc;
3020 if (get_reload_reg (type, mode, old, goal_alt[i], "", &new_reg)
3021 && type != OP_OUT)
3023 push_to_sequence (before);
3024 lra_emit_move (new_reg, old);
3025 before = get_insns ();
3026 end_sequence ();
3028 *loc = new_reg;
3029 if (type != OP_IN
3030 && find_reg_note (curr_insn, REG_UNUSED, old) == NULL_RTX)
3032 start_sequence ();
3033 lra_emit_move (type == OP_INOUT ? copy_rtx (old) : old, new_reg);
3034 emit_insn (after);
3035 after = get_insns ();
3036 end_sequence ();
3037 *loc = new_reg;
3039 for (j = 0; j < goal_alt_dont_inherit_ops_num; j++)
3040 if (goal_alt_dont_inherit_ops[j] == i)
3042 lra_set_regno_unique_value (REGNO (new_reg));
3043 break;
3045 lra_update_dup (curr_id, i);
3047 else if (curr_static_id->operand[i].type == OP_IN
3048 && (curr_static_id->operand[goal_alt_matched[i][0]].type
3049 == OP_OUT))
3051 signed char arr[2];
3053 arr[0] = i;
3054 arr[1] = -1;
3055 match_reload (goal_alt_matched[i][0], arr,
3056 goal_alt[i], &before, &after);
3058 else if (curr_static_id->operand[i].type == OP_OUT
3059 && (curr_static_id->operand[goal_alt_matched[i][0]].type
3060 == OP_IN))
3061 match_reload (i, goal_alt_matched[i], goal_alt[i], &before, &after);
3062 else
3063 /* We must generate code in any case when function
3064 process_alt_operands decides that it is possible. */
3065 gcc_unreachable ();
3067 if (before != NULL_RTX || after != NULL_RTX
3068 || max_regno_before != max_reg_num ())
3069 change_p = true;
3070 if (change_p)
3072 lra_update_operator_dups (curr_id);
3073 /* Something changes -- process the insn. */
3074 lra_update_insn_regno_info (curr_insn);
3076 lra_process_new_insns (curr_insn, before, after, "Inserting insn reload");
3077 return change_p;
3080 /* Return true if X is in LIST. */
3081 static bool
3082 in_list_p (rtx x, rtx list)
3084 for (; list != NULL_RTX; list = XEXP (list, 1))
3085 if (XEXP (list, 0) == x)
3086 return true;
3087 return false;
3090 /* Return true if X contains an allocatable hard register (if
3091 HARD_REG_P) or a (spilled if SPILLED_P) pseudo. */
3092 static bool
3093 contains_reg_p (rtx x, bool hard_reg_p, bool spilled_p)
3095 int i, j;
3096 const char *fmt;
3097 enum rtx_code code;
3099 code = GET_CODE (x);
3100 if (REG_P (x))
3102 int regno = REGNO (x);
3103 HARD_REG_SET alloc_regs;
3105 if (hard_reg_p)
3107 if (regno >= FIRST_PSEUDO_REGISTER)
3108 regno = lra_get_regno_hard_regno (regno);
3109 if (regno < 0)
3110 return false;
3111 COMPL_HARD_REG_SET (alloc_regs, lra_no_alloc_regs);
3112 return overlaps_hard_reg_set_p (alloc_regs, GET_MODE (x), regno);
3114 else
3116 if (regno < FIRST_PSEUDO_REGISTER)
3117 return false;
3118 if (! spilled_p)
3119 return true;
3120 return lra_get_regno_hard_regno (regno) < 0;
3123 fmt = GET_RTX_FORMAT (code);
3124 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3126 if (fmt[i] == 'e')
3128 if (contains_reg_p (XEXP (x, i), hard_reg_p, spilled_p))
3129 return true;
3131 else if (fmt[i] == 'E')
3133 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3134 if (contains_reg_p (XVECEXP (x, i, j), hard_reg_p, spilled_p))
3135 return true;
3138 return false;
3141 /* Process all regs in location *LOC and change them on equivalent
3142 substitution. Return true if any change was done. */
3143 static bool
3144 loc_equivalence_change_p (rtx *loc)
3146 rtx subst, reg, x = *loc;
3147 bool result = false;
3148 enum rtx_code code = GET_CODE (x);
3149 const char *fmt;
3150 int i, j;
3152 if (code == SUBREG)
3154 reg = SUBREG_REG (x);
3155 if ((subst = get_equiv_substitution (reg)) != reg
3156 && GET_MODE (subst) == VOIDmode)
3158 /* We cannot reload debug location. Simplify subreg here
3159 while we know the inner mode. */
3160 *loc = simplify_gen_subreg (GET_MODE (x), subst,
3161 GET_MODE (reg), SUBREG_BYTE (x));
3162 return true;
3165 if (code == REG && (subst = get_equiv_substitution (x)) != x)
3167 *loc = subst;
3168 return true;
3171 /* Scan all the operand sub-expressions. */
3172 fmt = GET_RTX_FORMAT (code);
3173 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3175 if (fmt[i] == 'e')
3176 result = loc_equivalence_change_p (&XEXP (x, i)) || result;
3177 else if (fmt[i] == 'E')
3178 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3179 result
3180 = loc_equivalence_change_p (&XVECEXP (x, i, j)) || result;
3182 return result;
3185 /* Maximum allowed number of constraint pass iterations after the last
3186 spill pass. It is for preventing LRA cycling in a bug case. */
3187 #define MAX_CONSTRAINT_ITERATION_NUMBER 30
3189 /* Maximum number of generated reload insns per an insn. It is for
3190 preventing this pass cycling in a bug case. */
3191 #define MAX_RELOAD_INSNS_NUMBER LRA_MAX_INSN_RELOADS
3193 /* The current iteration number of this LRA pass. */
3194 int lra_constraint_iter;
3196 /* The current iteration number of this LRA pass after the last spill
3197 pass. */
3198 int lra_constraint_iter_after_spill;
3200 /* True if we substituted equiv which needs checking register
3201 allocation correctness because the equivalent value contains
3202 allocatable hard registers or when we restore multi-register
3203 pseudo. */
3204 bool lra_risky_transformations_p;
3206 /* Return true if REGNO is referenced in more than one block. */
3207 static bool
3208 multi_block_pseudo_p (int regno)
3210 basic_block bb = NULL;
3211 unsigned int uid;
3212 bitmap_iterator bi;
3214 if (regno < FIRST_PSEUDO_REGISTER)
3215 return false;
3217 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
3218 if (bb == NULL)
3219 bb = BLOCK_FOR_INSN (lra_insn_recog_data[uid]->insn);
3220 else if (BLOCK_FOR_INSN (lra_insn_recog_data[uid]->insn) != bb)
3221 return true;
3222 return false;
3225 /* Return true if LIST contains a deleted insn. */
3226 static bool
3227 contains_deleted_insn_p (rtx list)
3229 for (; list != NULL_RTX; list = XEXP (list, 1))
3230 if (NOTE_P (XEXP (list, 0))
3231 && NOTE_KIND (XEXP (list, 0)) == NOTE_INSN_DELETED)
3232 return true;
3233 return false;
3236 /* Return true if X contains a pseudo dying in INSN. */
3237 static bool
3238 dead_pseudo_p (rtx x, rtx insn)
3240 int i, j;
3241 const char *fmt;
3242 enum rtx_code code;
3244 if (REG_P (x))
3245 return (insn != NULL_RTX
3246 && find_regno_note (insn, REG_DEAD, REGNO (x)) != NULL_RTX);
3247 code = GET_CODE (x);
3248 fmt = GET_RTX_FORMAT (code);
3249 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3251 if (fmt[i] == 'e')
3253 if (dead_pseudo_p (XEXP (x, i), insn))
3254 return true;
3256 else if (fmt[i] == 'E')
3258 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3259 if (dead_pseudo_p (XVECEXP (x, i, j), insn))
3260 return true;
3263 return false;
3266 /* Return true if INSN contains a dying pseudo in INSN right hand
3267 side. */
3268 static bool
3269 insn_rhs_dead_pseudo_p (rtx insn)
3271 rtx set = single_set (insn);
3273 gcc_assert (set != NULL);
3274 return dead_pseudo_p (SET_SRC (set), insn);
3277 /* Return true if any init insn of REGNO contains a dying pseudo in
3278 insn right hand side. */
3279 static bool
3280 init_insn_rhs_dead_pseudo_p (int regno)
3282 rtx insns = ira_reg_equiv[regno].init_insns;
3284 if (insns == NULL)
3285 return false;
3286 if (INSN_P (insns))
3287 return insn_rhs_dead_pseudo_p (insns);
3288 for (; insns != NULL_RTX; insns = XEXP (insns, 1))
3289 if (insn_rhs_dead_pseudo_p (XEXP (insns, 0)))
3290 return true;
3291 return false;
3294 /* Entry function of LRA constraint pass. Return true if the
3295 constraint pass did change the code. */
3296 bool
3297 lra_constraints (bool first_p)
3299 bool changed_p;
3300 int i, hard_regno, new_insns_num;
3301 unsigned int min_len, new_min_len, uid;
3302 rtx set, x, reg, dest_reg;
3303 basic_block last_bb;
3304 bitmap_head equiv_insn_bitmap;
3305 bitmap_iterator bi;
3307 lra_constraint_iter++;
3308 if (lra_dump_file != NULL)
3309 fprintf (lra_dump_file, "\n********** Local #%d: **********\n\n",
3310 lra_constraint_iter);
3311 lra_constraint_iter_after_spill++;
3312 if (lra_constraint_iter_after_spill > MAX_CONSTRAINT_ITERATION_NUMBER)
3313 internal_error
3314 ("Maximum number of LRA constraint passes is achieved (%d)\n",
3315 MAX_CONSTRAINT_ITERATION_NUMBER);
3316 changed_p = false;
3317 lra_risky_transformations_p = false;
3318 new_insn_uid_start = get_max_uid ();
3319 new_regno_start = first_p ? lra_constraint_new_regno_start : max_reg_num ();
3320 bitmap_initialize (&equiv_insn_bitmap, &reg_obstack);
3321 for (i = FIRST_PSEUDO_REGISTER; i < new_regno_start; i++)
3322 if (lra_reg_info[i].nrefs != 0)
3324 ira_reg_equiv[i].profitable_p = true;
3325 reg = regno_reg_rtx[i];
3326 if ((hard_regno = lra_get_regno_hard_regno (i)) >= 0)
3328 int j, nregs = hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (i)];
3330 for (j = 0; j < nregs; j++)
3331 df_set_regs_ever_live (hard_regno + j, true);
3333 else if ((x = get_equiv_substitution (reg)) != reg)
3335 bool pseudo_p = contains_reg_p (x, false, false);
3336 rtx set, insn;
3338 /* After RTL transformation, we can not guarantee that
3339 pseudo in the substitution was not reloaded which might
3340 make equivalence invalid. For example, in reverse
3341 equiv of p0
3343 p0 <- ...
3345 equiv_mem <- p0
3347 the memory address register was reloaded before the 2nd
3348 insn. */
3349 if ((! first_p && pseudo_p)
3350 /* We don't use DF for compilation speed sake. So it
3351 is problematic to update live info when we use an
3352 equivalence containing pseudos in more than one
3353 BB. */
3354 || (pseudo_p && multi_block_pseudo_p (i))
3355 /* If an init insn was deleted for some reason, cancel
3356 the equiv. We could update the equiv insns after
3357 transformations including an equiv insn deletion
3358 but it is not worthy as such cases are extremely
3359 rare. */
3360 || contains_deleted_insn_p (ira_reg_equiv[i].init_insns)
3361 /* If it is not a reverse equivalence, we check that a
3362 pseudo in rhs of the init insn is not dying in the
3363 insn. Otherwise, the live info at the beginning of
3364 the corresponding BB might be wrong after we
3365 removed the insn. When the equiv can be a
3366 constant, the right hand side of the init insn can
3367 be a pseudo. */
3368 || (! ((insn = ira_reg_equiv[i].init_insns) != NULL_RTX
3369 && INSN_P (insn)
3370 && (set = single_set (insn)) != NULL_RTX
3371 && REG_P (SET_DEST (set))
3372 && (int) REGNO (SET_DEST (set)) == i)
3373 && init_insn_rhs_dead_pseudo_p (i))
3374 /* Prevent access beyond equivalent memory for
3375 paradoxical subregs. */
3376 || (MEM_P (x)
3377 && (GET_MODE_SIZE (lra_reg_info[i].biggest_mode)
3378 > GET_MODE_SIZE (GET_MODE (x)))))
3379 ira_reg_equiv[i].defined_p = false;
3380 if (contains_reg_p (x, false, true))
3381 ira_reg_equiv[i].profitable_p = false;
3382 if (get_equiv_substitution (reg) != reg)
3383 bitmap_ior_into (&equiv_insn_bitmap, &lra_reg_info[i].insn_bitmap);
3386 /* We should add all insns containing pseudos which should be
3387 substituted by their equivalences. */
3388 EXECUTE_IF_SET_IN_BITMAP (&equiv_insn_bitmap, 0, uid, bi)
3389 lra_push_insn_by_uid (uid);
3390 lra_eliminate (false);
3391 min_len = lra_insn_stack_length ();
3392 new_insns_num = 0;
3393 last_bb = NULL;
3394 changed_p = false;
3395 while ((new_min_len = lra_insn_stack_length ()) != 0)
3397 curr_insn = lra_pop_insn ();
3398 --new_min_len;
3399 curr_bb = BLOCK_FOR_INSN (curr_insn);
3400 if (curr_bb != last_bb)
3402 last_bb = curr_bb;
3403 bb_reload_num = lra_curr_reload_num;
3405 if (min_len > new_min_len)
3407 min_len = new_min_len;
3408 new_insns_num = 0;
3410 if (new_insns_num > MAX_RELOAD_INSNS_NUMBER)
3411 internal_error
3412 ("Max. number of generated reload insns per insn is achieved (%d)\n",
3413 MAX_RELOAD_INSNS_NUMBER);
3414 new_insns_num++;
3415 if (DEBUG_INSN_P (curr_insn))
3417 /* We need to check equivalence in debug insn and change
3418 pseudo to the equivalent value if necessary. */
3419 curr_id = lra_get_insn_recog_data (curr_insn);
3420 if (bitmap_bit_p (&equiv_insn_bitmap, INSN_UID (curr_insn))
3421 && loc_equivalence_change_p (curr_id->operand_loc[0]))
3423 lra_update_insn_regno_info (curr_insn);
3424 changed_p = true;
3427 else if (INSN_P (curr_insn))
3429 if ((set = single_set (curr_insn)) != NULL_RTX)
3431 dest_reg = SET_DEST (set);
3432 /* The equivalence pseudo could be set up as SUBREG in a
3433 case when it is a call restore insn in a mode
3434 different from the pseudo mode. */
3435 if (GET_CODE (dest_reg) == SUBREG)
3436 dest_reg = SUBREG_REG (dest_reg);
3437 if ((REG_P (dest_reg)
3438 && (x = get_equiv_substitution (dest_reg)) != dest_reg
3439 /* Remove insns which set up a pseudo whose value
3440 can not be changed. Such insns might be not in
3441 init_insns because we don't update equiv data
3442 during insn transformations.
3444 As an example, let suppose that a pseudo got
3445 hard register and on the 1st pass was not
3446 changed to equivalent constant. We generate an
3447 additional insn setting up the pseudo because of
3448 secondary memory movement. Then the pseudo is
3449 spilled and we use the equiv constant. In this
3450 case we should remove the additional insn and
3451 this insn is not init_insns list. */
3452 && (! MEM_P (x) || MEM_READONLY_P (x)
3453 || in_list_p (curr_insn,
3454 ira_reg_equiv
3455 [REGNO (dest_reg)].init_insns)))
3456 || (((x = get_equiv_substitution (SET_SRC (set)))
3457 != SET_SRC (set))
3458 && in_list_p (curr_insn,
3459 ira_reg_equiv
3460 [REGNO (SET_SRC (set))].init_insns)))
3462 /* This is equiv init insn of pseudo which did not get a
3463 hard register -- remove the insn. */
3464 if (lra_dump_file != NULL)
3466 fprintf (lra_dump_file,
3467 " Removing equiv init insn %i (freq=%d)\n",
3468 INSN_UID (curr_insn),
3469 BLOCK_FOR_INSN (curr_insn)->frequency);
3470 dump_insn_slim (lra_dump_file, curr_insn);
3472 if (contains_reg_p (x, true, false))
3473 lra_risky_transformations_p = true;
3474 lra_set_insn_deleted (curr_insn);
3475 continue;
3478 curr_id = lra_get_insn_recog_data (curr_insn);
3479 curr_static_id = curr_id->insn_static_data;
3480 init_curr_insn_input_reloads ();
3481 init_curr_operand_mode ();
3482 if (curr_insn_transform ())
3483 changed_p = true;
3484 /* Check non-transformed insns too for equiv change as USE
3485 or CLOBBER don't need reloads but can contain pseudos
3486 being changed on their equivalences. */
3487 else if (bitmap_bit_p (&equiv_insn_bitmap, INSN_UID (curr_insn))
3488 && loc_equivalence_change_p (&PATTERN (curr_insn)))
3490 lra_update_insn_regno_info (curr_insn);
3491 changed_p = true;
3495 bitmap_clear (&equiv_insn_bitmap);
3496 /* If we used a new hard regno, changed_p should be true because the
3497 hard reg is assigned to a new pseudo. */
3498 #ifdef ENABLE_CHECKING
3499 if (! changed_p)
3501 for (i = FIRST_PSEUDO_REGISTER; i < new_regno_start; i++)
3502 if (lra_reg_info[i].nrefs != 0
3503 && (hard_regno = lra_get_regno_hard_regno (i)) >= 0)
3505 int j, nregs = hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (i)];
3507 for (j = 0; j < nregs; j++)
3508 lra_assert (df_regs_ever_live_p (hard_regno + j));
3511 #endif
3512 return changed_p;
3515 /* Initiate the LRA constraint pass. It is done once per
3516 function. */
3517 void
3518 lra_constraints_init (void)
3522 /* Finalize the LRA constraint pass. It is done once per
3523 function. */
3524 void
3525 lra_constraints_finish (void)
3531 /* This page contains code to do inheritance/split
3532 transformations. */
3534 /* Number of reloads passed so far in current EBB. */
3535 static int reloads_num;
3537 /* Number of calls passed so far in current EBB. */
3538 static int calls_num;
3540 /* Current reload pseudo check for validity of elements in
3541 USAGE_INSNS. */
3542 static int curr_usage_insns_check;
3544 /* Info about last usage of registers in EBB to do inheritance/split
3545 transformation. Inheritance transformation is done from a spilled
3546 pseudo and split transformations from a hard register or a pseudo
3547 assigned to a hard register. */
3548 struct usage_insns
3550 /* If the value is equal to CURR_USAGE_INSNS_CHECK, then the member
3551 value INSNS is valid. The insns is chain of optional debug insns
3552 and a finishing non-debug insn using the corresponding reg. */
3553 int check;
3554 /* Value of global reloads_num at the last insn in INSNS. */
3555 int reloads_num;
3556 /* Value of global reloads_nums at the last insn in INSNS. */
3557 int calls_num;
3558 /* It can be true only for splitting. And it means that the restore
3559 insn should be put after insn given by the following member. */
3560 bool after_p;
3561 /* Next insns in the current EBB which use the original reg and the
3562 original reg value is not changed between the current insn and
3563 the next insns. In order words, e.g. for inheritance, if we need
3564 to use the original reg value again in the next insns we can try
3565 to use the value in a hard register from a reload insn of the
3566 current insn. */
3567 rtx insns;
3570 /* Map: regno -> corresponding pseudo usage insns. */
3571 static struct usage_insns *usage_insns;
3573 static void
3574 setup_next_usage_insn (int regno, rtx insn, int reloads_num, bool after_p)
3576 usage_insns[regno].check = curr_usage_insns_check;
3577 usage_insns[regno].insns = insn;
3578 usage_insns[regno].reloads_num = reloads_num;
3579 usage_insns[regno].calls_num = calls_num;
3580 usage_insns[regno].after_p = after_p;
3583 /* The function is used to form list REGNO usages which consists of
3584 optional debug insns finished by a non-debug insn using REGNO.
3585 RELOADS_NUM is current number of reload insns processed so far. */
3586 static void
3587 add_next_usage_insn (int regno, rtx insn, int reloads_num)
3589 rtx next_usage_insns;
3591 if (usage_insns[regno].check == curr_usage_insns_check
3592 && (next_usage_insns = usage_insns[regno].insns) != NULL_RTX
3593 && DEBUG_INSN_P (insn))
3595 /* Check that we did not add the debug insn yet. */
3596 if (next_usage_insns != insn
3597 && (GET_CODE (next_usage_insns) != INSN_LIST
3598 || XEXP (next_usage_insns, 0) != insn))
3599 usage_insns[regno].insns = gen_rtx_INSN_LIST (VOIDmode, insn,
3600 next_usage_insns);
3602 else if (NONDEBUG_INSN_P (insn))
3603 setup_next_usage_insn (regno, insn, reloads_num, false);
3604 else
3605 usage_insns[regno].check = 0;
3608 /* Replace all references to register OLD_REGNO in *LOC with pseudo
3609 register NEW_REG. Return true if any change was made. */
3610 static bool
3611 substitute_pseudo (rtx *loc, int old_regno, rtx new_reg)
3613 rtx x = *loc;
3614 bool result = false;
3615 enum rtx_code code;
3616 const char *fmt;
3617 int i, j;
3619 if (x == NULL_RTX)
3620 return false;
3622 code = GET_CODE (x);
3623 if (code == REG && (int) REGNO (x) == old_regno)
3625 enum machine_mode mode = GET_MODE (*loc);
3626 enum machine_mode inner_mode = GET_MODE (new_reg);
3628 if (mode != inner_mode)
3630 if (GET_MODE_SIZE (mode) >= GET_MODE_SIZE (inner_mode)
3631 || ! SCALAR_INT_MODE_P (inner_mode))
3632 new_reg = gen_rtx_SUBREG (mode, new_reg, 0);
3633 else
3634 new_reg = gen_lowpart_SUBREG (mode, new_reg);
3636 *loc = new_reg;
3637 return true;
3640 /* Scan all the operand sub-expressions. */
3641 fmt = GET_RTX_FORMAT (code);
3642 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3644 if (fmt[i] == 'e')
3646 if (substitute_pseudo (&XEXP (x, i), old_regno, new_reg))
3647 result = true;
3649 else if (fmt[i] == 'E')
3651 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3652 if (substitute_pseudo (&XVECEXP (x, i, j), old_regno, new_reg))
3653 result = true;
3656 return result;
3659 /* Return first non-debug insn in list USAGE_INSNS. */
3660 static rtx
3661 skip_usage_debug_insns (rtx usage_insns)
3663 rtx insn;
3665 /* Skip debug insns. */
3666 for (insn = usage_insns;
3667 insn != NULL_RTX && GET_CODE (insn) == INSN_LIST;
3668 insn = XEXP (insn, 1))
3670 return insn;
3673 /* Return true if we need secondary memory moves for insn in
3674 USAGE_INSNS after inserting inherited pseudo of class INHER_CL
3675 into the insn. */
3676 static bool
3677 check_secondary_memory_needed_p (enum reg_class inher_cl ATTRIBUTE_UNUSED,
3678 rtx usage_insns ATTRIBUTE_UNUSED)
3680 #ifndef SECONDARY_MEMORY_NEEDED
3681 return false;
3682 #else
3683 rtx insn, set, dest;
3684 enum reg_class cl;
3686 if (inher_cl == ALL_REGS
3687 || (insn = skip_usage_debug_insns (usage_insns)) == NULL_RTX)
3688 return false;
3689 lra_assert (INSN_P (insn));
3690 if ((set = single_set (insn)) == NULL_RTX || ! REG_P (SET_DEST (set)))
3691 return false;
3692 dest = SET_DEST (set);
3693 if (! REG_P (dest))
3694 return false;
3695 lra_assert (inher_cl != NO_REGS);
3696 cl = get_reg_class (REGNO (dest));
3697 return (cl != NO_REGS && cl != ALL_REGS
3698 && SECONDARY_MEMORY_NEEDED (inher_cl, cl, GET_MODE (dest)));
3699 #endif
3702 /* Registers involved in inheritance/split in the current EBB
3703 (inheritance/split pseudos and original registers). */
3704 static bitmap_head check_only_regs;
3706 /* Do inheritance transformations for insn INSN, which defines (if
3707 DEF_P) or uses ORIGINAL_REGNO. NEXT_USAGE_INSNS specifies which
3708 instruction in the EBB next uses ORIGINAL_REGNO; it has the same
3709 form as the "insns" field of usage_insns. Return true if we
3710 succeed in such transformation.
3712 The transformations look like:
3714 p <- ... i <- ...
3715 ... p <- i (new insn)
3716 ... =>
3717 <- ... p ... <- ... i ...
3719 ... i <- p (new insn)
3720 <- ... p ... <- ... i ...
3721 ... =>
3722 <- ... p ... <- ... i ...
3723 where p is a spilled original pseudo and i is a new inheritance pseudo.
3726 The inheritance pseudo has the smallest class of two classes CL and
3727 class of ORIGINAL REGNO. */
3728 static bool
3729 inherit_reload_reg (bool def_p, int original_regno,
3730 enum reg_class cl, rtx insn, rtx next_usage_insns)
3732 enum reg_class rclass = lra_get_allocno_class (original_regno);
3733 rtx original_reg = regno_reg_rtx[original_regno];
3734 rtx new_reg, new_insns, usage_insn;
3736 lra_assert (! usage_insns[original_regno].after_p);
3737 if (lra_dump_file != NULL)
3738 fprintf (lra_dump_file,
3739 " <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n");
3740 if (! ira_reg_classes_intersect_p[cl][rclass])
3742 if (lra_dump_file != NULL)
3744 fprintf (lra_dump_file,
3745 " Rejecting inheritance for %d "
3746 "because of disjoint classes %s and %s\n",
3747 original_regno, reg_class_names[cl],
3748 reg_class_names[rclass]);
3749 fprintf (lra_dump_file,
3750 " >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
3752 return false;
3754 if ((ira_class_subset_p[cl][rclass] && cl != rclass)
3755 /* We don't use a subset of two classes because it can be
3756 NO_REGS. This transformation is still profitable in most
3757 cases even if the classes are not intersected as register
3758 move is probably cheaper than a memory load. */
3759 || ira_class_hard_regs_num[cl] < ira_class_hard_regs_num[rclass])
3761 if (lra_dump_file != NULL)
3762 fprintf (lra_dump_file, " Use smallest class of %s and %s\n",
3763 reg_class_names[cl], reg_class_names[rclass]);
3765 rclass = cl;
3767 if (check_secondary_memory_needed_p (cl, next_usage_insns))
3769 /* Reject inheritance resulting in secondary memory moves.
3770 Otherwise, there is a danger in LRA cycling. Also such
3771 transformation will be unprofitable. */
3772 if (lra_dump_file != NULL)
3774 rtx insn = skip_usage_debug_insns (next_usage_insns);
3775 rtx set = single_set (insn);
3777 lra_assert (set != NULL_RTX);
3779 rtx dest = SET_DEST (set);
3781 lra_assert (REG_P (dest));
3782 fprintf (lra_dump_file,
3783 " Rejecting inheritance for insn %d(%s)<-%d(%s) "
3784 "as secondary mem is needed\n",
3785 REGNO (dest), reg_class_names[get_reg_class (REGNO (dest))],
3786 original_regno, reg_class_names[cl]);
3787 fprintf (lra_dump_file,
3788 " >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
3790 return false;
3792 new_reg = lra_create_new_reg (GET_MODE (original_reg), original_reg,
3793 rclass, "inheritance");
3794 start_sequence ();
3795 if (def_p)
3796 emit_move_insn (original_reg, new_reg);
3797 else
3798 emit_move_insn (new_reg, original_reg);
3799 new_insns = get_insns ();
3800 end_sequence ();
3801 if (NEXT_INSN (new_insns) != NULL_RTX)
3803 if (lra_dump_file != NULL)
3805 fprintf (lra_dump_file,
3806 " Rejecting inheritance %d->%d "
3807 "as it results in 2 or more insns:\n",
3808 original_regno, REGNO (new_reg));
3809 dump_rtl_slim (lra_dump_file, new_insns, NULL_RTX, -1, 0);
3810 fprintf (lra_dump_file,
3811 " >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
3813 return false;
3815 substitute_pseudo (&insn, original_regno, new_reg);
3816 lra_update_insn_regno_info (insn);
3817 if (! def_p)
3818 /* We now have a new usage insn for original regno. */
3819 setup_next_usage_insn (original_regno, new_insns, reloads_num, false);
3820 if (lra_dump_file != NULL)
3821 fprintf (lra_dump_file, " Original reg change %d->%d (bb%d):\n",
3822 original_regno, REGNO (new_reg), BLOCK_FOR_INSN (insn)->index);
3823 lra_reg_info[REGNO (new_reg)].restore_regno = original_regno;
3824 bitmap_set_bit (&check_only_regs, REGNO (new_reg));
3825 bitmap_set_bit (&check_only_regs, original_regno);
3826 bitmap_set_bit (&lra_inheritance_pseudos, REGNO (new_reg));
3827 if (def_p)
3828 lra_process_new_insns (insn, NULL_RTX, new_insns,
3829 "Add original<-inheritance");
3830 else
3831 lra_process_new_insns (insn, new_insns, NULL_RTX,
3832 "Add inheritance<-original");
3833 while (next_usage_insns != NULL_RTX)
3835 if (GET_CODE (next_usage_insns) != INSN_LIST)
3837 usage_insn = next_usage_insns;
3838 lra_assert (NONDEBUG_INSN_P (usage_insn));
3839 next_usage_insns = NULL;
3841 else
3843 usage_insn = XEXP (next_usage_insns, 0);
3844 lra_assert (DEBUG_INSN_P (usage_insn));
3845 next_usage_insns = XEXP (next_usage_insns, 1);
3847 substitute_pseudo (&usage_insn, original_regno, new_reg);
3848 lra_update_insn_regno_info (usage_insn);
3849 if (lra_dump_file != NULL)
3851 fprintf (lra_dump_file,
3852 " Inheritance reuse change %d->%d (bb%d):\n",
3853 original_regno, REGNO (new_reg),
3854 BLOCK_FOR_INSN (usage_insn)->index);
3855 dump_insn_slim (lra_dump_file, usage_insn);
3858 if (lra_dump_file != NULL)
3859 fprintf (lra_dump_file,
3860 " >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
3861 return true;
3864 /* Return true if we need a caller save/restore for pseudo REGNO which
3865 was assigned to a hard register. */
3866 static inline bool
3867 need_for_call_save_p (int regno)
3869 lra_assert (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] >= 0);
3870 return (usage_insns[regno].calls_num < calls_num
3871 && (overlaps_hard_reg_set_p
3872 (call_used_reg_set,
3873 PSEUDO_REGNO_MODE (regno), reg_renumber[regno])));
3876 /* Global registers occuring in the current EBB. */
3877 static bitmap_head ebb_global_regs;
3879 /* Return true if we need a split for hard register REGNO or pseudo
3880 REGNO which was assigned to a hard register.
3881 POTENTIAL_RELOAD_HARD_REGS contains hard registers which might be
3882 used for reloads since the EBB end. It is an approximation of the
3883 used hard registers in the split range. The exact value would
3884 require expensive calculations. If we were aggressive with
3885 splitting because of the approximation, the split pseudo will save
3886 the same hard register assignment and will be removed in the undo
3887 pass. We still need the approximation because too aggressive
3888 splitting would result in too inaccurate cost calculation in the
3889 assignment pass because of too many generated moves which will be
3890 probably removed in the undo pass. */
3891 static inline bool
3892 need_for_split_p (HARD_REG_SET potential_reload_hard_regs, int regno)
3894 int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
3896 lra_assert (hard_regno >= 0);
3897 return ((TEST_HARD_REG_BIT (potential_reload_hard_regs, hard_regno)
3898 /* Don't split eliminable hard registers, otherwise we can
3899 split hard registers like hard frame pointer, which
3900 lives on BB start/end according to DF-infrastructure,
3901 when there is a pseudo assigned to the register and
3902 living in the same BB. */
3903 && (regno >= FIRST_PSEUDO_REGISTER
3904 || ! TEST_HARD_REG_BIT (eliminable_regset, hard_regno))
3905 && ! TEST_HARD_REG_BIT (lra_no_alloc_regs, hard_regno)
3906 /* We need at least 2 reloads to make pseudo splitting
3907 profitable. We should provide hard regno splitting in
3908 any case to solve 1st insn scheduling problem when
3909 moving hard register definition up might result in
3910 impossibility to find hard register for reload pseudo of
3911 small register class. */
3912 && (usage_insns[regno].reloads_num
3913 + (regno < FIRST_PSEUDO_REGISTER ? 0 : 2) < reloads_num)
3914 && (regno < FIRST_PSEUDO_REGISTER
3915 /* For short living pseudos, spilling + inheritance can
3916 be considered a substitution for splitting.
3917 Therefore we do not splitting for local pseudos. It
3918 decreases also aggressiveness of splitting. The
3919 minimal number of references is chosen taking into
3920 account that for 2 references splitting has no sense
3921 as we can just spill the pseudo. */
3922 || (regno >= FIRST_PSEUDO_REGISTER
3923 && lra_reg_info[regno].nrefs > 3
3924 && bitmap_bit_p (&ebb_global_regs, regno))))
3925 || (regno >= FIRST_PSEUDO_REGISTER && need_for_call_save_p (regno)));
3928 /* Return class for the split pseudo created from original pseudo with
3929 ALLOCNO_CLASS and MODE which got a hard register HARD_REGNO. We
3930 choose subclass of ALLOCNO_CLASS which contains HARD_REGNO and
3931 results in no secondary memory movements. */
3932 static enum reg_class
3933 choose_split_class (enum reg_class allocno_class,
3934 int hard_regno ATTRIBUTE_UNUSED,
3935 enum machine_mode mode ATTRIBUTE_UNUSED)
3937 #ifndef SECONDARY_MEMORY_NEEDED
3938 return allocno_class;
3939 #else
3940 int i;
3941 enum reg_class cl, best_cl = NO_REGS;
3942 enum reg_class hard_reg_class ATTRIBUTE_UNUSED
3943 = REGNO_REG_CLASS (hard_regno);
3945 if (! SECONDARY_MEMORY_NEEDED (allocno_class, allocno_class, mode)
3946 && TEST_HARD_REG_BIT (reg_class_contents[allocno_class], hard_regno))
3947 return allocno_class;
3948 for (i = 0;
3949 (cl = reg_class_subclasses[allocno_class][i]) != LIM_REG_CLASSES;
3950 i++)
3951 if (! SECONDARY_MEMORY_NEEDED (cl, hard_reg_class, mode)
3952 && ! SECONDARY_MEMORY_NEEDED (hard_reg_class, cl, mode)
3953 && TEST_HARD_REG_BIT (reg_class_contents[cl], hard_regno)
3954 && (best_cl == NO_REGS
3955 || ira_class_hard_regs_num[best_cl] < ira_class_hard_regs_num[cl]))
3956 best_cl = cl;
3957 return best_cl;
3958 #endif
3961 /* Do split transformations for insn INSN, which defines or uses
3962 ORIGINAL_REGNO. NEXT_USAGE_INSNS specifies which instruction in
3963 the EBB next uses ORIGINAL_REGNO; it has the same form as the
3964 "insns" field of usage_insns.
3966 The transformations look like:
3968 p <- ... p <- ...
3969 ... s <- p (new insn -- save)
3970 ... =>
3971 ... p <- s (new insn -- restore)
3972 <- ... p ... <- ... p ...
3974 <- ... p ... <- ... p ...
3975 ... s <- p (new insn -- save)
3976 ... =>
3977 ... p <- s (new insn -- restore)
3978 <- ... p ... <- ... p ...
3980 where p is an original pseudo got a hard register or a hard
3981 register and s is a new split pseudo. The save is put before INSN
3982 if BEFORE_P is true. Return true if we succeed in such
3983 transformation. */
3984 static bool
3985 split_reg (bool before_p, int original_regno, rtx insn, rtx next_usage_insns)
3987 enum reg_class rclass;
3988 rtx original_reg;
3989 int hard_regno;
3990 rtx new_reg, save, restore, usage_insn;
3991 bool after_p;
3992 bool call_save_p;
3994 if (original_regno < FIRST_PSEUDO_REGISTER)
3996 rclass = ira_allocno_class_translate[REGNO_REG_CLASS (original_regno)];
3997 hard_regno = original_regno;
3998 call_save_p = false;
4000 else
4002 hard_regno = reg_renumber[original_regno];
4003 rclass = lra_get_allocno_class (original_regno);
4004 original_reg = regno_reg_rtx[original_regno];
4005 call_save_p = need_for_call_save_p (original_regno);
4007 original_reg = regno_reg_rtx[original_regno];
4008 lra_assert (hard_regno >= 0);
4009 if (lra_dump_file != NULL)
4010 fprintf (lra_dump_file,
4011 " ((((((((((((((((((((((((((((((((((((((((((((((((\n");
4012 if (call_save_p)
4014 enum machine_mode sec_mode;
4016 #ifdef SECONDARY_MEMORY_NEEDED_MODE
4017 sec_mode = SECONDARY_MEMORY_NEEDED_MODE (GET_MODE (original_reg));
4018 #else
4019 sec_mode = GET_MODE (original_reg);
4020 #endif
4021 new_reg = lra_create_new_reg (sec_mode, NULL_RTX,
4022 NO_REGS, "save");
4024 else
4026 rclass = choose_split_class (rclass, hard_regno,
4027 GET_MODE (original_reg));
4028 if (rclass == NO_REGS)
4030 if (lra_dump_file != NULL)
4032 fprintf (lra_dump_file,
4033 " Rejecting split of %d(%s): "
4034 "no good reg class for %d(%s)\n",
4035 original_regno,
4036 reg_class_names[lra_get_allocno_class (original_regno)],
4037 hard_regno,
4038 reg_class_names[REGNO_REG_CLASS (hard_regno)]);
4039 fprintf
4040 (lra_dump_file,
4041 " ))))))))))))))))))))))))))))))))))))))))))))))))\n");
4043 return false;
4045 new_reg = lra_create_new_reg (GET_MODE (original_reg), original_reg,
4046 rclass, "split");
4047 reg_renumber[REGNO (new_reg)] = hard_regno;
4049 save = emit_spill_move (true, new_reg, original_reg);
4050 if (NEXT_INSN (save) != NULL_RTX)
4052 lra_assert (! call_save_p);
4053 if (lra_dump_file != NULL)
4055 fprintf
4056 (lra_dump_file,
4057 " Rejecting split %d->%d resulting in > 2 %s save insns:\n",
4058 original_regno, REGNO (new_reg), call_save_p ? "call" : "");
4059 dump_rtl_slim (lra_dump_file, save, NULL_RTX, -1, 0);
4060 fprintf (lra_dump_file,
4061 " ))))))))))))))))))))))))))))))))))))))))))))))))\n");
4063 return false;
4065 restore = emit_spill_move (false, new_reg, original_reg);
4066 if (NEXT_INSN (restore) != NULL_RTX)
4068 lra_assert (! call_save_p);
4069 if (lra_dump_file != NULL)
4071 fprintf (lra_dump_file,
4072 " Rejecting split %d->%d "
4073 "resulting in > 2 %s restore insns:\n",
4074 original_regno, REGNO (new_reg), call_save_p ? "call" : "");
4075 dump_rtl_slim (lra_dump_file, restore, NULL_RTX, -1, 0);
4076 fprintf (lra_dump_file,
4077 " ))))))))))))))))))))))))))))))))))))))))))))))))\n");
4079 return false;
4081 after_p = usage_insns[original_regno].after_p;
4082 lra_reg_info[REGNO (new_reg)].restore_regno = original_regno;
4083 bitmap_set_bit (&check_only_regs, REGNO (new_reg));
4084 bitmap_set_bit (&check_only_regs, original_regno);
4085 bitmap_set_bit (&lra_split_regs, REGNO (new_reg));
4086 for (;;)
4088 if (GET_CODE (next_usage_insns) != INSN_LIST)
4090 usage_insn = next_usage_insns;
4091 break;
4093 usage_insn = XEXP (next_usage_insns, 0);
4094 lra_assert (DEBUG_INSN_P (usage_insn));
4095 next_usage_insns = XEXP (next_usage_insns, 1);
4096 substitute_pseudo (&usage_insn, original_regno, new_reg);
4097 lra_update_insn_regno_info (usage_insn);
4098 if (lra_dump_file != NULL)
4100 fprintf (lra_dump_file, " Split reuse change %d->%d:\n",
4101 original_regno, REGNO (new_reg));
4102 dump_insn_slim (lra_dump_file, usage_insn);
4105 lra_assert (NOTE_P (usage_insn) || NONDEBUG_INSN_P (usage_insn));
4106 lra_assert (usage_insn != insn || (after_p && before_p));
4107 lra_process_new_insns (usage_insn, after_p ? NULL_RTX : restore,
4108 after_p ? restore : NULL_RTX,
4109 call_save_p
4110 ? "Add reg<-save" : "Add reg<-split");
4111 lra_process_new_insns (insn, before_p ? save : NULL_RTX,
4112 before_p ? NULL_RTX : save,
4113 call_save_p
4114 ? "Add save<-reg" : "Add split<-reg");
4115 if (lra_dump_file != NULL)
4116 fprintf (lra_dump_file,
4117 " ))))))))))))))))))))))))))))))))))))))))))))))))\n");
4118 return true;
4121 /* Recognize that we need a split transformation for insn INSN, which
4122 defines or uses REGNO in its insn biggest MODE (we use it only if
4123 REGNO is a hard register). POTENTIAL_RELOAD_HARD_REGS contains
4124 hard registers which might be used for reloads since the EBB end.
4125 Put the save before INSN if BEFORE_P is true. MAX_UID is maximla
4126 uid before starting INSN processing. Return true if we succeed in
4127 such transformation. */
4128 static bool
4129 split_if_necessary (int regno, enum machine_mode mode,
4130 HARD_REG_SET potential_reload_hard_regs,
4131 bool before_p, rtx insn, int max_uid)
4133 bool res = false;
4134 int i, nregs = 1;
4135 rtx next_usage_insns;
4137 if (regno < FIRST_PSEUDO_REGISTER)
4138 nregs = hard_regno_nregs[regno][mode];
4139 for (i = 0; i < nregs; i++)
4140 if (usage_insns[regno + i].check == curr_usage_insns_check
4141 && (next_usage_insns = usage_insns[regno + i].insns) != NULL_RTX
4142 /* To avoid processing the register twice or more. */
4143 && ((GET_CODE (next_usage_insns) != INSN_LIST
4144 && INSN_UID (next_usage_insns) < max_uid)
4145 || (GET_CODE (next_usage_insns) == INSN_LIST
4146 && (INSN_UID (XEXP (next_usage_insns, 0)) < max_uid)))
4147 && need_for_split_p (potential_reload_hard_regs, regno + i)
4148 && split_reg (before_p, regno + i, insn, next_usage_insns))
4149 res = true;
4150 return res;
4153 /* Check only registers living at the current program point in the
4154 current EBB. */
4155 static bitmap_head live_regs;
4157 /* Update live info in EBB given by its HEAD and TAIL insns after
4158 inheritance/split transformation. The function removes dead moves
4159 too. */
4160 static void
4161 update_ebb_live_info (rtx head, rtx tail)
4163 unsigned int j;
4164 int regno;
4165 bool live_p;
4166 rtx prev_insn, set;
4167 bool remove_p;
4168 basic_block last_bb, prev_bb, curr_bb;
4169 bitmap_iterator bi;
4170 struct lra_insn_reg *reg;
4171 edge e;
4172 edge_iterator ei;
4174 last_bb = BLOCK_FOR_INSN (tail);
4175 prev_bb = NULL;
4176 for (curr_insn = tail;
4177 curr_insn != PREV_INSN (head);
4178 curr_insn = prev_insn)
4180 prev_insn = PREV_INSN (curr_insn);
4181 /* We need to process empty blocks too. They contain
4182 NOTE_INSN_BASIC_BLOCK referring for the basic block. */
4183 if (NOTE_P (curr_insn) && NOTE_KIND (curr_insn) != NOTE_INSN_BASIC_BLOCK)
4184 continue;
4185 curr_bb = BLOCK_FOR_INSN (curr_insn);
4186 if (curr_bb != prev_bb)
4188 if (prev_bb != NULL)
4190 /* Update df_get_live_in (prev_bb): */
4191 EXECUTE_IF_SET_IN_BITMAP (&check_only_regs, 0, j, bi)
4192 if (bitmap_bit_p (&live_regs, j))
4193 bitmap_set_bit (df_get_live_in (prev_bb), j);
4194 else
4195 bitmap_clear_bit (df_get_live_in (prev_bb), j);
4197 if (curr_bb != last_bb)
4199 /* Update df_get_live_out (curr_bb): */
4200 EXECUTE_IF_SET_IN_BITMAP (&check_only_regs, 0, j, bi)
4202 live_p = bitmap_bit_p (&live_regs, j);
4203 if (! live_p)
4204 FOR_EACH_EDGE (e, ei, curr_bb->succs)
4205 if (bitmap_bit_p (df_get_live_in (e->dest), j))
4207 live_p = true;
4208 break;
4210 if (live_p)
4211 bitmap_set_bit (df_get_live_out (curr_bb), j);
4212 else
4213 bitmap_clear_bit (df_get_live_out (curr_bb), j);
4216 prev_bb = curr_bb;
4217 bitmap_and (&live_regs, &check_only_regs, df_get_live_out (curr_bb));
4219 if (! NONDEBUG_INSN_P (curr_insn))
4220 continue;
4221 curr_id = lra_get_insn_recog_data (curr_insn);
4222 remove_p = false;
4223 if ((set = single_set (curr_insn)) != NULL_RTX && REG_P (SET_DEST (set))
4224 && (regno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
4225 && bitmap_bit_p (&check_only_regs, regno)
4226 && ! bitmap_bit_p (&live_regs, regno))
4227 remove_p = true;
4228 /* See which defined values die here. */
4229 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
4230 if (reg->type == OP_OUT && ! reg->subreg_p)
4231 bitmap_clear_bit (&live_regs, reg->regno);
4232 /* Mark each used value as live. */
4233 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
4234 if (reg->type == OP_IN
4235 && bitmap_bit_p (&check_only_regs, reg->regno))
4236 bitmap_set_bit (&live_regs, reg->regno);
4237 /* It is quite important to remove dead move insns because it
4238 means removing dead store. We don't need to process them for
4239 constraints. */
4240 if (remove_p)
4242 if (lra_dump_file != NULL)
4244 fprintf (lra_dump_file, " Removing dead insn:\n ");
4245 dump_insn_slim (lra_dump_file, curr_insn);
4247 lra_set_insn_deleted (curr_insn);
4252 /* The structure describes info to do an inheritance for the current
4253 insn. We need to collect such info first before doing the
4254 transformations because the transformations change the insn
4255 internal representation. */
4256 struct to_inherit
4258 /* Original regno. */
4259 int regno;
4260 /* Subsequent insns which can inherit original reg value. */
4261 rtx insns;
4264 /* Array containing all info for doing inheritance from the current
4265 insn. */
4266 static struct to_inherit to_inherit[LRA_MAX_INSN_RELOADS];
4268 /* Number elements in the previous array. */
4269 static int to_inherit_num;
4271 /* Add inheritance info REGNO and INSNS. Their meaning is described in
4272 structure to_inherit. */
4273 static void
4274 add_to_inherit (int regno, rtx insns)
4276 int i;
4278 for (i = 0; i < to_inherit_num; i++)
4279 if (to_inherit[i].regno == regno)
4280 return;
4281 lra_assert (to_inherit_num < LRA_MAX_INSN_RELOADS);
4282 to_inherit[to_inherit_num].regno = regno;
4283 to_inherit[to_inherit_num++].insns = insns;
4286 /* Return the last non-debug insn in basic block BB, or the block begin
4287 note if none. */
4288 static rtx
4289 get_last_insertion_point (basic_block bb)
4291 rtx insn;
4293 FOR_BB_INSNS_REVERSE (bb, insn)
4294 if (NONDEBUG_INSN_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
4295 return insn;
4296 gcc_unreachable ();
4299 /* Set up RES by registers living on edges FROM except the edge (FROM,
4300 TO) or by registers set up in a jump insn in BB FROM. */
4301 static void
4302 get_live_on_other_edges (basic_block from, basic_block to, bitmap res)
4304 rtx last;
4305 struct lra_insn_reg *reg;
4306 edge e;
4307 edge_iterator ei;
4309 lra_assert (to != NULL);
4310 bitmap_clear (res);
4311 FOR_EACH_EDGE (e, ei, from->succs)
4312 if (e->dest != to)
4313 bitmap_ior_into (res, df_get_live_in (e->dest));
4314 last = get_last_insertion_point (from);
4315 if (! JUMP_P (last))
4316 return;
4317 curr_id = lra_get_insn_recog_data (last);
4318 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
4319 if (reg->type != OP_IN)
4320 bitmap_set_bit (res, reg->regno);
4323 /* Used as a temporary results of some bitmap calculations. */
4324 static bitmap_head temp_bitmap;
4326 /* Do inheritance/split transformations in EBB starting with HEAD and
4327 finishing on TAIL. We process EBB insns in the reverse order.
4328 Return true if we did any inheritance/split transformation in the
4329 EBB.
4331 We should avoid excessive splitting which results in worse code
4332 because of inaccurate cost calculations for spilling new split
4333 pseudos in such case. To achieve this we do splitting only if
4334 register pressure is high in given basic block and there are reload
4335 pseudos requiring hard registers. We could do more register
4336 pressure calculations at any given program point to avoid necessary
4337 splitting even more but it is to expensive and the current approach
4338 works well enough. */
4339 static bool
4340 inherit_in_ebb (rtx head, rtx tail)
4342 int i, src_regno, dst_regno, nregs;
4343 bool change_p, succ_p;
4344 rtx prev_insn, next_usage_insns, set, last_insn;
4345 enum reg_class cl;
4346 struct lra_insn_reg *reg;
4347 basic_block last_processed_bb, curr_bb = NULL;
4348 HARD_REG_SET potential_reload_hard_regs, live_hard_regs;
4349 bitmap to_process;
4350 unsigned int j;
4351 bitmap_iterator bi;
4352 bool head_p, after_p;
4354 change_p = false;
4355 curr_usage_insns_check++;
4356 reloads_num = calls_num = 0;
4357 bitmap_clear (&check_only_regs);
4358 last_processed_bb = NULL;
4359 CLEAR_HARD_REG_SET (potential_reload_hard_regs);
4360 CLEAR_HARD_REG_SET (live_hard_regs);
4361 /* We don't process new insns generated in the loop. */
4362 for (curr_insn = tail; curr_insn != PREV_INSN (head); curr_insn = prev_insn)
4364 prev_insn = PREV_INSN (curr_insn);
4365 if (BLOCK_FOR_INSN (curr_insn) != NULL)
4366 curr_bb = BLOCK_FOR_INSN (curr_insn);
4367 if (last_processed_bb != curr_bb)
4369 /* We are at the end of BB. Add qualified living
4370 pseudos for potential splitting. */
4371 to_process = df_get_live_out (curr_bb);
4372 if (last_processed_bb != NULL)
4374 /* We are somewhere in the middle of EBB. */
4375 get_live_on_other_edges (curr_bb, last_processed_bb,
4376 &temp_bitmap);
4377 to_process = &temp_bitmap;
4379 last_processed_bb = curr_bb;
4380 last_insn = get_last_insertion_point (curr_bb);
4381 after_p = (! JUMP_P (last_insn)
4382 && (! CALL_P (last_insn)
4383 || (find_reg_note (last_insn,
4384 REG_NORETURN, NULL_RTX) == NULL_RTX
4385 && ! SIBLING_CALL_P (last_insn))));
4386 REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_out (curr_bb));
4387 IOR_HARD_REG_SET (live_hard_regs, eliminable_regset);
4388 IOR_HARD_REG_SET (live_hard_regs, lra_no_alloc_regs);
4389 CLEAR_HARD_REG_SET (potential_reload_hard_regs);
4390 EXECUTE_IF_SET_IN_BITMAP (to_process, 0, j, bi)
4392 if ((int) j >= lra_constraint_new_regno_start)
4393 break;
4394 if (j < FIRST_PSEUDO_REGISTER || reg_renumber[j] >= 0)
4396 if (j < FIRST_PSEUDO_REGISTER)
4397 SET_HARD_REG_BIT (live_hard_regs, j);
4398 else
4399 add_to_hard_reg_set (&live_hard_regs,
4400 PSEUDO_REGNO_MODE (j),
4401 reg_renumber[j]);
4402 setup_next_usage_insn (j, last_insn, reloads_num, after_p);
4406 src_regno = dst_regno = -1;
4407 if (NONDEBUG_INSN_P (curr_insn)
4408 && (set = single_set (curr_insn)) != NULL_RTX
4409 && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
4411 src_regno = REGNO (SET_SRC (set));
4412 dst_regno = REGNO (SET_DEST (set));
4414 if (src_regno < lra_constraint_new_regno_start
4415 && src_regno >= FIRST_PSEUDO_REGISTER
4416 && reg_renumber[src_regno] < 0
4417 && dst_regno >= lra_constraint_new_regno_start
4418 && (cl = lra_get_allocno_class (dst_regno)) != NO_REGS)
4420 /* 'reload_pseudo <- original_pseudo'. */
4421 reloads_num++;
4422 succ_p = false;
4423 if (usage_insns[src_regno].check == curr_usage_insns_check
4424 && (next_usage_insns = usage_insns[src_regno].insns) != NULL_RTX)
4425 succ_p = inherit_reload_reg (false, src_regno, cl,
4426 curr_insn, next_usage_insns);
4427 if (succ_p)
4428 change_p = true;
4429 else
4430 setup_next_usage_insn (src_regno, curr_insn, reloads_num, false);
4431 if (hard_reg_set_subset_p (reg_class_contents[cl], live_hard_regs))
4432 IOR_HARD_REG_SET (potential_reload_hard_regs,
4433 reg_class_contents[cl]);
4435 else if (src_regno >= lra_constraint_new_regno_start
4436 && dst_regno < lra_constraint_new_regno_start
4437 && dst_regno >= FIRST_PSEUDO_REGISTER
4438 && reg_renumber[dst_regno] < 0
4439 && (cl = lra_get_allocno_class (src_regno)) != NO_REGS
4440 && usage_insns[dst_regno].check == curr_usage_insns_check
4441 && (next_usage_insns
4442 = usage_insns[dst_regno].insns) != NULL_RTX)
4444 reloads_num++;
4445 /* 'original_pseudo <- reload_pseudo'. */
4446 if (! JUMP_P (curr_insn)
4447 && inherit_reload_reg (true, dst_regno, cl,
4448 curr_insn, next_usage_insns))
4449 change_p = true;
4450 /* Invalidate. */
4451 usage_insns[dst_regno].check = 0;
4452 if (hard_reg_set_subset_p (reg_class_contents[cl], live_hard_regs))
4453 IOR_HARD_REG_SET (potential_reload_hard_regs,
4454 reg_class_contents[cl]);
4456 else if (INSN_P (curr_insn))
4458 int max_uid = get_max_uid ();
4460 curr_id = lra_get_insn_recog_data (curr_insn);
4461 to_inherit_num = 0;
4462 /* Process insn definitions. */
4463 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
4464 if (reg->type != OP_IN
4465 && (dst_regno = reg->regno) < lra_constraint_new_regno_start)
4467 if (dst_regno >= FIRST_PSEUDO_REGISTER && reg->type == OP_OUT
4468 && reg_renumber[dst_regno] < 0 && ! reg->subreg_p
4469 && usage_insns[dst_regno].check == curr_usage_insns_check
4470 && (next_usage_insns
4471 = usage_insns[dst_regno].insns) != NULL_RTX)
4473 struct lra_insn_reg *r;
4475 for (r = curr_id->regs; r != NULL; r = r->next)
4476 if (r->type != OP_OUT && r->regno == dst_regno)
4477 break;
4478 /* Don't do inheritance if the pseudo is also
4479 used in the insn. */
4480 if (r == NULL)
4481 /* We can not do inheritance right now
4482 because the current insn reg info (chain
4483 regs) can change after that. */
4484 add_to_inherit (dst_regno, next_usage_insns);
4486 /* We can not process one reg twice here because of
4487 usage_insns invalidation. */
4488 if ((dst_regno < FIRST_PSEUDO_REGISTER
4489 || reg_renumber[dst_regno] >= 0)
4490 && ! reg->subreg_p && reg->type == OP_OUT)
4492 HARD_REG_SET s;
4494 if (split_if_necessary (dst_regno, reg->biggest_mode,
4495 potential_reload_hard_regs,
4496 false, curr_insn, max_uid))
4497 change_p = true;
4498 CLEAR_HARD_REG_SET (s);
4499 if (dst_regno < FIRST_PSEUDO_REGISTER)
4500 add_to_hard_reg_set (&s, reg->biggest_mode, dst_regno);
4501 else
4502 add_to_hard_reg_set (&s, PSEUDO_REGNO_MODE (dst_regno),
4503 reg_renumber[dst_regno]);
4504 AND_COMPL_HARD_REG_SET (live_hard_regs, s);
4506 /* We should invalidate potential inheritance or
4507 splitting for the current insn usages to the next
4508 usage insns (see code below) as the output pseudo
4509 prevents this. */
4510 if ((dst_regno >= FIRST_PSEUDO_REGISTER
4511 && reg_renumber[dst_regno] < 0)
4512 || (reg->type == OP_OUT && ! reg->subreg_p
4513 && (dst_regno < FIRST_PSEUDO_REGISTER
4514 || reg_renumber[dst_regno] >= 0)))
4516 /* Invalidate. */
4517 if (dst_regno >= FIRST_PSEUDO_REGISTER)
4518 usage_insns[dst_regno].check = 0;
4519 else
4521 nregs = hard_regno_nregs[dst_regno][reg->biggest_mode];
4522 for (i = 0; i < nregs; i++)
4523 usage_insns[dst_regno + i].check = 0;
4527 if (! JUMP_P (curr_insn))
4528 for (i = 0; i < to_inherit_num; i++)
4529 if (inherit_reload_reg (true, to_inherit[i].regno,
4530 ALL_REGS, curr_insn,
4531 to_inherit[i].insns))
4532 change_p = true;
4533 if (CALL_P (curr_insn))
4535 rtx cheap, pat, dest, restore;
4536 int regno, hard_regno;
4538 calls_num++;
4539 if ((cheap = find_reg_note (curr_insn,
4540 REG_RETURNED, NULL_RTX)) != NULL_RTX
4541 && ((cheap = XEXP (cheap, 0)), true)
4542 && (regno = REGNO (cheap)) >= FIRST_PSEUDO_REGISTER
4543 && (hard_regno = reg_renumber[regno]) >= 0
4544 /* If there are pending saves/restores, the
4545 optimization is not worth. */
4546 && usage_insns[regno].calls_num == calls_num - 1
4547 && TEST_HARD_REG_BIT (call_used_reg_set, hard_regno))
4549 /* Restore the pseudo from the call result as
4550 REG_RETURNED note says that the pseudo value is
4551 in the call result and the pseudo is an argument
4552 of the call. */
4553 pat = PATTERN (curr_insn);
4554 if (GET_CODE (pat) == PARALLEL)
4555 pat = XVECEXP (pat, 0, 0);
4556 dest = SET_DEST (pat);
4557 start_sequence ();
4558 emit_move_insn (cheap, copy_rtx (dest));
4559 restore = get_insns ();
4560 end_sequence ();
4561 lra_process_new_insns (curr_insn, NULL, restore,
4562 "Inserting call parameter restore");
4563 /* We don't need to save/restore of the pseudo from
4564 this call. */
4565 usage_insns[regno].calls_num = calls_num;
4566 bitmap_set_bit (&check_only_regs, regno);
4569 to_inherit_num = 0;
4570 /* Process insn usages. */
4571 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
4572 if ((reg->type != OP_OUT
4573 || (reg->type == OP_OUT && reg->subreg_p))
4574 && (src_regno = reg->regno) < lra_constraint_new_regno_start)
4576 if (src_regno >= FIRST_PSEUDO_REGISTER
4577 && reg_renumber[src_regno] < 0 && reg->type == OP_IN)
4579 if (usage_insns[src_regno].check == curr_usage_insns_check
4580 && (next_usage_insns
4581 = usage_insns[src_regno].insns) != NULL_RTX
4582 && NONDEBUG_INSN_P (curr_insn))
4583 add_to_inherit (src_regno, next_usage_insns);
4584 else
4585 /* Add usages. */
4586 add_next_usage_insn (src_regno, curr_insn, reloads_num);
4588 else if (src_regno < FIRST_PSEUDO_REGISTER
4589 || reg_renumber[src_regno] >= 0)
4591 bool before_p;
4592 rtx use_insn = curr_insn;
4594 before_p = (JUMP_P (curr_insn)
4595 || (CALL_P (curr_insn) && reg->type == OP_IN));
4596 if (NONDEBUG_INSN_P (curr_insn)
4597 && split_if_necessary (src_regno, reg->biggest_mode,
4598 potential_reload_hard_regs,
4599 before_p, curr_insn, max_uid))
4601 if (reg->subreg_p)
4602 lra_risky_transformations_p = true;
4603 change_p = true;
4604 /* Invalidate. */
4605 usage_insns[src_regno].check = 0;
4606 if (before_p)
4607 use_insn = PREV_INSN (curr_insn);
4609 if (NONDEBUG_INSN_P (curr_insn))
4611 if (src_regno < FIRST_PSEUDO_REGISTER)
4612 add_to_hard_reg_set (&live_hard_regs,
4613 reg->biggest_mode, src_regno);
4614 else
4615 add_to_hard_reg_set (&live_hard_regs,
4616 PSEUDO_REGNO_MODE (src_regno),
4617 reg_renumber[src_regno]);
4619 add_next_usage_insn (src_regno, use_insn, reloads_num);
4622 for (i = 0; i < to_inherit_num; i++)
4624 src_regno = to_inherit[i].regno;
4625 if (inherit_reload_reg (false, src_regno, ALL_REGS,
4626 curr_insn, to_inherit[i].insns))
4627 change_p = true;
4628 else
4629 setup_next_usage_insn (src_regno, curr_insn, reloads_num, false);
4632 /* We reached the start of the current basic block. */
4633 if (prev_insn == NULL_RTX || prev_insn == PREV_INSN (head)
4634 || BLOCK_FOR_INSN (prev_insn) != curr_bb)
4636 /* We reached the beginning of the current block -- do
4637 rest of spliting in the current BB. */
4638 to_process = df_get_live_in (curr_bb);
4639 if (BLOCK_FOR_INSN (head) != curr_bb)
4641 /* We are somewhere in the middle of EBB. */
4642 get_live_on_other_edges (EDGE_PRED (curr_bb, 0)->src,
4643 curr_bb, &temp_bitmap);
4644 to_process = &temp_bitmap;
4646 head_p = true;
4647 EXECUTE_IF_SET_IN_BITMAP (to_process, 0, j, bi)
4649 if ((int) j >= lra_constraint_new_regno_start)
4650 break;
4651 if (((int) j < FIRST_PSEUDO_REGISTER || reg_renumber[j] >= 0)
4652 && usage_insns[j].check == curr_usage_insns_check
4653 && (next_usage_insns = usage_insns[j].insns) != NULL_RTX)
4655 if (need_for_split_p (potential_reload_hard_regs, j))
4657 if (lra_dump_file != NULL && head_p)
4659 fprintf (lra_dump_file,
4660 " ----------------------------------\n");
4661 head_p = false;
4663 if (split_reg (false, j, bb_note (curr_bb),
4664 next_usage_insns))
4665 change_p = true;
4667 usage_insns[j].check = 0;
4672 return change_p;
4675 /* The maximal number of inheritance/split passes in LRA. It should
4676 be more 1 in order to perform caller saves transformations and much
4677 less MAX_CONSTRAINT_ITERATION_NUMBER to prevent LRA to do as many
4678 as permitted constraint passes in some complicated cases. The
4679 first inheritance/split pass has a biggest impact on generated code
4680 quality. Each subsequent affects generated code in less degree.
4681 For example, the 3rd pass does not change generated SPEC2000 code
4682 at all on x86-64. */
4683 #define MAX_INHERITANCE_PASSES 2
4685 #if MAX_INHERITANCE_PASSES <= 0 \
4686 || MAX_INHERITANCE_PASSES >= MAX_CONSTRAINT_ITERATION_NUMBER - 8
4687 #error wrong MAX_INHERITANCE_PASSES value
4688 #endif
4690 /* This value affects EBB forming. If probability of edge from EBB to
4691 a BB is not greater than the following value, we don't add the BB
4692 to EBB. */
4693 #define EBB_PROBABILITY_CUTOFF (REG_BR_PROB_BASE / 2)
4695 /* Current number of inheritance/split iteration. */
4696 int lra_inheritance_iter;
4698 /* Entry function for inheritance/split pass. */
4699 void
4700 lra_inheritance (void)
4702 int i;
4703 basic_block bb, start_bb;
4704 edge e;
4706 lra_inheritance_iter++;
4707 if (lra_inheritance_iter > MAX_INHERITANCE_PASSES)
4708 return;
4709 timevar_push (TV_LRA_INHERITANCE);
4710 if (lra_dump_file != NULL)
4711 fprintf (lra_dump_file, "\n********** Inheritance #%d: **********\n\n",
4712 lra_inheritance_iter);
4713 curr_usage_insns_check = 0;
4714 usage_insns = XNEWVEC (struct usage_insns, lra_constraint_new_regno_start);
4715 for (i = 0; i < lra_constraint_new_regno_start; i++)
4716 usage_insns[i].check = 0;
4717 bitmap_initialize (&check_only_regs, &reg_obstack);
4718 bitmap_initialize (&live_regs, &reg_obstack);
4719 bitmap_initialize (&temp_bitmap, &reg_obstack);
4720 bitmap_initialize (&ebb_global_regs, &reg_obstack);
4721 FOR_EACH_BB (bb)
4723 start_bb = bb;
4724 if (lra_dump_file != NULL)
4725 fprintf (lra_dump_file, "EBB");
4726 /* Form a EBB starting with BB. */
4727 bitmap_clear (&ebb_global_regs);
4728 bitmap_ior_into (&ebb_global_regs, df_get_live_in (bb));
4729 for (;;)
4731 if (lra_dump_file != NULL)
4732 fprintf (lra_dump_file, " %d", bb->index);
4733 if (bb->next_bb == EXIT_BLOCK_PTR || LABEL_P (BB_HEAD (bb->next_bb)))
4734 break;
4735 e = find_fallthru_edge (bb->succs);
4736 if (! e)
4737 break;
4738 if (e->probability <= EBB_PROBABILITY_CUTOFF)
4739 break;
4740 bb = bb->next_bb;
4742 bitmap_ior_into (&ebb_global_regs, df_get_live_out (bb));
4743 if (lra_dump_file != NULL)
4744 fprintf (lra_dump_file, "\n");
4745 if (inherit_in_ebb (BB_HEAD (start_bb), BB_END (bb)))
4746 /* Remember that the EBB head and tail can change in
4747 inherit_in_ebb. */
4748 update_ebb_live_info (BB_HEAD (start_bb), BB_END (bb));
4750 bitmap_clear (&ebb_global_regs);
4751 bitmap_clear (&temp_bitmap);
4752 bitmap_clear (&live_regs);
4753 bitmap_clear (&check_only_regs);
4754 free (usage_insns);
4756 timevar_pop (TV_LRA_INHERITANCE);
4761 /* This page contains code to undo failed inheritance/split
4762 transformations. */
4764 /* Current number of iteration undoing inheritance/split. */
4765 int lra_undo_inheritance_iter;
4767 /* Fix BB live info LIVE after removing pseudos created on pass doing
4768 inheritance/split which are REMOVED_PSEUDOS. */
4769 static void
4770 fix_bb_live_info (bitmap live, bitmap removed_pseudos)
4772 unsigned int regno;
4773 bitmap_iterator bi;
4775 EXECUTE_IF_SET_IN_BITMAP (removed_pseudos, 0, regno, bi)
4776 if (bitmap_clear_bit (live, regno))
4777 bitmap_set_bit (live, lra_reg_info[regno].restore_regno);
4780 /* Return regno of the (subreg of) REG. Otherwise, return a negative
4781 number. */
4782 static int
4783 get_regno (rtx reg)
4785 if (GET_CODE (reg) == SUBREG)
4786 reg = SUBREG_REG (reg);
4787 if (REG_P (reg))
4788 return REGNO (reg);
4789 return -1;
4792 /* Remove inheritance/split pseudos which are in REMOVE_PSEUDOS and
4793 return true if we did any change. The undo transformations for
4794 inheritance looks like
4795 i <- i2
4796 p <- i => p <- i2
4797 or removing
4798 p <- i, i <- p, and i <- i3
4799 where p is original pseudo from which inheritance pseudo i was
4800 created, i and i3 are removed inheritance pseudos, i2 is another
4801 not removed inheritance pseudo. All split pseudos or other
4802 occurrences of removed inheritance pseudos are changed on the
4803 corresponding original pseudos.
4805 The function also schedules insns changed and created during
4806 inheritance/split pass for processing by the subsequent constraint
4807 pass. */
4808 static bool
4809 remove_inheritance_pseudos (bitmap remove_pseudos)
4811 basic_block bb;
4812 int regno, sregno, prev_sregno, dregno, restore_regno;
4813 rtx set, prev_set, prev_insn;
4814 bool change_p, done_p;
4816 change_p = ! bitmap_empty_p (remove_pseudos);
4817 /* We can not finish the function right away if CHANGE_P is true
4818 because we need to marks insns affected by previous
4819 inheritance/split pass for processing by the subsequent
4820 constraint pass. */
4821 FOR_EACH_BB (bb)
4823 fix_bb_live_info (df_get_live_in (bb), remove_pseudos);
4824 fix_bb_live_info (df_get_live_out (bb), remove_pseudos);
4825 FOR_BB_INSNS_REVERSE (bb, curr_insn)
4827 if (! INSN_P (curr_insn))
4828 continue;
4829 done_p = false;
4830 sregno = dregno = -1;
4831 if (change_p && NONDEBUG_INSN_P (curr_insn)
4832 && (set = single_set (curr_insn)) != NULL_RTX)
4834 dregno = get_regno (SET_DEST (set));
4835 sregno = get_regno (SET_SRC (set));
4838 if (sregno >= 0 && dregno >= 0)
4840 if ((bitmap_bit_p (remove_pseudos, sregno)
4841 && (lra_reg_info[sregno].restore_regno == dregno
4842 || (bitmap_bit_p (remove_pseudos, dregno)
4843 && (lra_reg_info[sregno].restore_regno
4844 == lra_reg_info[dregno].restore_regno))))
4845 || (bitmap_bit_p (remove_pseudos, dregno)
4846 && lra_reg_info[dregno].restore_regno == sregno))
4847 /* One of the following cases:
4848 original <- removed inheritance pseudo
4849 removed inherit pseudo <- another removed inherit pseudo
4850 removed inherit pseudo <- original pseudo
4852 removed_split_pseudo <- original_reg
4853 original_reg <- removed_split_pseudo */
4855 if (lra_dump_file != NULL)
4857 fprintf (lra_dump_file, " Removing %s:\n",
4858 bitmap_bit_p (&lra_split_regs, sregno)
4859 || bitmap_bit_p (&lra_split_regs, dregno)
4860 ? "split" : "inheritance");
4861 dump_insn_slim (lra_dump_file, curr_insn);
4863 lra_set_insn_deleted (curr_insn);
4864 done_p = true;
4866 else if (bitmap_bit_p (remove_pseudos, sregno)
4867 && bitmap_bit_p (&lra_inheritance_pseudos, sregno))
4869 /* Search the following pattern:
4870 inherit_or_split_pseudo1 <- inherit_or_split_pseudo2
4871 original_pseudo <- inherit_or_split_pseudo1
4872 where the 2nd insn is the current insn and
4873 inherit_or_split_pseudo2 is not removed. If it is found,
4874 change the current insn onto:
4875 original_pseudo <- inherit_or_split_pseudo2. */
4876 for (prev_insn = PREV_INSN (curr_insn);
4877 prev_insn != NULL_RTX && ! NONDEBUG_INSN_P (prev_insn);
4878 prev_insn = PREV_INSN (prev_insn))
4880 if (prev_insn != NULL_RTX && BLOCK_FOR_INSN (prev_insn) == bb
4881 && (prev_set = single_set (prev_insn)) != NULL_RTX
4882 /* There should be no subregs in insn we are
4883 searching because only the original reg might
4884 be in subreg when we changed the mode of
4885 load/store for splitting. */
4886 && REG_P (SET_DEST (prev_set))
4887 && REG_P (SET_SRC (prev_set))
4888 && (int) REGNO (SET_DEST (prev_set)) == sregno
4889 && ((prev_sregno = REGNO (SET_SRC (prev_set)))
4890 >= FIRST_PSEUDO_REGISTER)
4891 /* As we consider chain of inheritance or
4892 splitting described in above comment we should
4893 check that sregno and prev_sregno were
4894 inheritance/split pseudos created from the
4895 same original regno. */
4896 && (lra_reg_info[sregno].restore_regno
4897 == lra_reg_info[prev_sregno].restore_regno)
4898 && ! bitmap_bit_p (remove_pseudos, prev_sregno))
4900 lra_assert (GET_MODE (SET_SRC (prev_set))
4901 == GET_MODE (regno_reg_rtx[sregno]));
4902 if (GET_CODE (SET_SRC (set)) == SUBREG)
4903 SUBREG_REG (SET_SRC (set)) = SET_SRC (prev_set);
4904 else
4905 SET_SRC (set) = SET_SRC (prev_set);
4906 lra_push_insn_and_update_insn_regno_info (curr_insn);
4907 lra_set_used_insn_alternative_by_uid
4908 (INSN_UID (curr_insn), -1);
4909 done_p = true;
4910 if (lra_dump_file != NULL)
4912 fprintf (lra_dump_file, " Change reload insn:\n");
4913 dump_insn_slim (lra_dump_file, curr_insn);
4918 if (! done_p)
4920 struct lra_insn_reg *reg;
4921 bool restored_regs_p = false;
4922 bool kept_regs_p = false;
4924 curr_id = lra_get_insn_recog_data (curr_insn);
4925 for (reg = curr_id->regs; reg != NULL; reg = reg->next)
4927 regno = reg->regno;
4928 restore_regno = lra_reg_info[regno].restore_regno;
4929 if (restore_regno >= 0)
4931 if (change_p && bitmap_bit_p (remove_pseudos, regno))
4933 substitute_pseudo (&curr_insn, regno,
4934 regno_reg_rtx[restore_regno]);
4935 restored_regs_p = true;
4937 else
4938 kept_regs_p = true;
4941 if (NONDEBUG_INSN_P (curr_insn) && kept_regs_p)
4943 /* The instruction has changed since the previous
4944 constraints pass. */
4945 lra_push_insn_and_update_insn_regno_info (curr_insn);
4946 lra_set_used_insn_alternative_by_uid
4947 (INSN_UID (curr_insn), -1);
4949 else if (restored_regs_p)
4950 /* The instruction has been restored to the form that
4951 it had during the previous constraints pass. */
4952 lra_update_insn_regno_info (curr_insn);
4953 if (restored_regs_p && lra_dump_file != NULL)
4955 fprintf (lra_dump_file, " Insn after restoring regs:\n");
4956 dump_insn_slim (lra_dump_file, curr_insn);
4961 return change_p;
4964 /* Entry function for undoing inheritance/split transformation. Return true
4965 if we did any RTL change in this pass. */
4966 bool
4967 lra_undo_inheritance (void)
4969 unsigned int regno;
4970 int restore_regno, hard_regno;
4971 int n_all_inherit, n_inherit, n_all_split, n_split;
4972 bitmap_head remove_pseudos;
4973 bitmap_iterator bi;
4974 bool change_p;
4976 lra_undo_inheritance_iter++;
4977 if (lra_undo_inheritance_iter > MAX_INHERITANCE_PASSES)
4978 return false;
4979 if (lra_dump_file != NULL)
4980 fprintf (lra_dump_file,
4981 "\n********** Undoing inheritance #%d: **********\n\n",
4982 lra_undo_inheritance_iter);
4983 bitmap_initialize (&remove_pseudos, &reg_obstack);
4984 n_inherit = n_all_inherit = 0;
4985 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, regno, bi)
4986 if (lra_reg_info[regno].restore_regno >= 0)
4988 n_all_inherit++;
4989 if (reg_renumber[regno] < 0)
4990 bitmap_set_bit (&remove_pseudos, regno);
4991 else
4992 n_inherit++;
4994 if (lra_dump_file != NULL && n_all_inherit != 0)
4995 fprintf (lra_dump_file, "Inherit %d out of %d (%.2f%%)\n",
4996 n_inherit, n_all_inherit,
4997 (double) n_inherit / n_all_inherit * 100);
4998 n_split = n_all_split = 0;
4999 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, regno, bi)
5000 if ((restore_regno = lra_reg_info[regno].restore_regno) >= 0)
5002 n_all_split++;
5003 hard_regno = (restore_regno >= FIRST_PSEUDO_REGISTER
5004 ? reg_renumber[restore_regno] : restore_regno);
5005 if (hard_regno < 0 || reg_renumber[regno] == hard_regno)
5006 bitmap_set_bit (&remove_pseudos, regno);
5007 else
5009 n_split++;
5010 if (lra_dump_file != NULL)
5011 fprintf (lra_dump_file, " Keep split r%d (orig=r%d)\n",
5012 regno, restore_regno);
5015 if (lra_dump_file != NULL && n_all_split != 0)
5016 fprintf (lra_dump_file, "Split %d out of %d (%.2f%%)\n",
5017 n_split, n_all_split,
5018 (double) n_split / n_all_split * 100);
5019 change_p = remove_inheritance_pseudos (&remove_pseudos);
5020 bitmap_clear (&remove_pseudos);
5021 /* Clear restore_regnos. */
5022 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, regno, bi)
5023 lra_reg_info[regno].restore_regno = -1;
5024 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, regno, bi)
5025 lra_reg_info[regno].restore_regno = -1;
5026 return change_p;