1 /* LRA (local register allocator) driver and LRA utilities.
2 Copyright (C) 2010-2017 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 /* The Local Register Allocator (LRA) is a replacement of former
23 reload pass. It is focused to simplify code solving the reload
24 pass tasks, to make the code maintenance easier, and to implement new
25 perspective optimizations.
27 The major LRA design solutions are:
28 o division small manageable, separated sub-tasks
29 o reflection of all transformations and decisions in RTL as more
31 o insn constraints as a primary source of the info (minimizing
32 number of target-depended macros/hooks)
34 In brief LRA works by iterative insn process with the final goal is
35 to satisfy all insn and address constraints:
36 o New reload insns (in brief reloads) and reload pseudos might be
38 o Some pseudos might be spilled to assign hard registers to
40 o Recalculating spilled pseudo values (rematerialization);
41 o Changing spilled pseudos to stack memory or their equivalences;
42 o Allocation stack memory changes the address displacement and
43 new iteration is needed.
45 Here is block diagram of LRA passes:
47 ------------------------
48 --------------- | Undo inheritance for | ---------------
49 | Memory-memory | | spilled pseudos, | | New (and old) |
50 | move coalesce |<---| splits for pseudos got |<-- | pseudos |
51 --------------- | the same hard regs, | | assignment |
52 Start | | and optional reloads | ---------------
53 | | ------------------------ ^
54 V | ---------------- |
55 ----------- V | Update virtual | |
56 | Remove |----> ------------>| register | |
57 | scratches | ^ | displacements | |
58 ----------- | ---------------- |
61 | ------------ pseudos -------------------
62 | |Constraints:| or insns | Inheritance/split |
63 | | RTL |--------->| transformations |
64 | | transfor- | | in EBB scope |
65 | substi- | mations | -------------------
66 | tutions ------------
69 | Spilled pseudo | -------------------
70 | to memory |<----| Rematerialization |
71 | substitution | -------------------
75 -------------------------
76 | Hard regs substitution, |
77 | devirtalization, and |------> Finish
78 | restoring scratches got |
80 -------------------------
82 To speed up the process:
83 o We process only insns affected by changes on previous
85 o We don't use DFA-infrastructure because it results in much slower
86 compiler speed than a special IR described below does;
87 o We use a special insn representation for quick access to insn
88 info which is always *synchronized* with the current RTL;
89 o Insn IR is minimized by memory. It is divided on three parts:
90 o one specific for each insn in RTL (only operand locations);
91 o one common for all insns in RTL with the same insn code
92 (different operand attributes from machine descriptions);
93 o one oriented for maintenance of live info (list of pseudos).
95 o all insns where the pseudo is referenced;
96 o live info (conflicting hard regs, live ranges, # of
98 o data used for assigning (preferred hard regs, costs etc).
100 This file contains LRA driver, LRA utility functions and data, and
101 code for dealing with scratches. */
105 #include "coretypes.h"
112 #include "memmodel.h"
120 #include "cfgbuild.h"
123 #include "print-rtl.h"
125 /* Dump bitmap SET with TITLE and BB INDEX. */
127 lra_dump_bitmap_with_title (const char *title
, bitmap set
, int index
)
132 static const int max_nums_on_line
= 10;
134 if (bitmap_empty_p (set
))
136 fprintf (lra_dump_file
, " %s %d:", title
, index
);
137 fprintf (lra_dump_file
, "\n");
138 count
= max_nums_on_line
+ 1;
139 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
141 if (count
> max_nums_on_line
)
143 fprintf (lra_dump_file
, "\n ");
146 fprintf (lra_dump_file
, " %4u", i
);
149 fprintf (lra_dump_file
, "\n");
152 /* Hard registers currently not available for allocation. It can
153 changed after some hard registers become not eliminable. */
154 HARD_REG_SET lra_no_alloc_regs
;
156 static int get_new_reg_value (void);
157 static void expand_reg_info (void);
158 static void invalidate_insn_recog_data (int);
159 static int get_insn_freq (rtx_insn
*);
160 static void invalidate_insn_data_regno_info (lra_insn_recog_data_t
,
163 /* Expand all regno related info needed for LRA. */
165 expand_reg_data (int old
)
169 ira_expand_reg_equiv ();
170 for (int i
= (int) max_reg_num () - 1; i
>= old
; i
--)
171 lra_change_class (i
, ALL_REGS
, " Set", true);
174 /* Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL
175 or of VOIDmode, use MD_MODE for the new reg. Initialize its
176 register class to RCLASS. Print message about assigning class
177 RCLASS containing new register name TITLE unless it is NULL. Use
178 attributes of ORIGINAL if it is a register. The created register
179 will have unique held value. */
181 lra_create_new_reg_with_unique_value (machine_mode md_mode
, rtx original
,
182 enum reg_class rclass
, const char *title
)
187 if (original
== NULL_RTX
|| (mode
= GET_MODE (original
)) == VOIDmode
)
189 lra_assert (mode
!= VOIDmode
);
190 new_reg
= gen_reg_rtx (mode
);
191 if (original
== NULL_RTX
|| ! REG_P (original
))
193 if (lra_dump_file
!= NULL
)
194 fprintf (lra_dump_file
, " Creating newreg=%i", REGNO (new_reg
));
198 if (ORIGINAL_REGNO (original
) >= FIRST_PSEUDO_REGISTER
)
199 ORIGINAL_REGNO (new_reg
) = ORIGINAL_REGNO (original
);
200 REG_USERVAR_P (new_reg
) = REG_USERVAR_P (original
);
201 REG_POINTER (new_reg
) = REG_POINTER (original
);
202 REG_ATTRS (new_reg
) = REG_ATTRS (original
);
203 if (lra_dump_file
!= NULL
)
204 fprintf (lra_dump_file
, " Creating newreg=%i from oldreg=%i",
205 REGNO (new_reg
), REGNO (original
));
207 if (lra_dump_file
!= NULL
)
210 fprintf (lra_dump_file
, ", assigning class %s to%s%s r%d",
211 reg_class_names
[rclass
], *title
== '\0' ? "" : " ",
212 title
, REGNO (new_reg
));
213 fprintf (lra_dump_file
, "\n");
215 expand_reg_data (max_reg_num ());
216 setup_reg_classes (REGNO (new_reg
), rclass
, NO_REGS
, rclass
);
220 /* Analogous to the previous function but also inherits value of
223 lra_create_new_reg (machine_mode md_mode
, rtx original
,
224 enum reg_class rclass
, const char *title
)
229 = lra_create_new_reg_with_unique_value (md_mode
, original
, rclass
, title
);
230 if (original
!= NULL_RTX
&& REG_P (original
))
231 lra_assign_reg_val (REGNO (original
), REGNO (new_reg
));
235 /* Set up for REGNO unique hold value. */
237 lra_set_regno_unique_value (int regno
)
239 lra_reg_info
[regno
].val
= get_new_reg_value ();
242 /* Invalidate INSN related info used by LRA. The info should never be
245 lra_invalidate_insn_data (rtx_insn
*insn
)
247 lra_invalidate_insn_regno_info (insn
);
248 invalidate_insn_recog_data (INSN_UID (insn
));
251 /* Mark INSN deleted and invalidate the insn related info used by
254 lra_set_insn_deleted (rtx_insn
*insn
)
256 lra_invalidate_insn_data (insn
);
257 SET_INSN_DELETED (insn
);
260 /* Delete an unneeded INSN and any previous insns who sole purpose is
261 loading data that is dead in INSN. */
263 lra_delete_dead_insn (rtx_insn
*insn
)
265 rtx_insn
*prev
= prev_real_insn (insn
);
268 /* If the previous insn sets a register that dies in our insn,
270 if (prev
&& GET_CODE (PATTERN (prev
)) == SET
271 && (prev_dest
= SET_DEST (PATTERN (prev
)), REG_P (prev_dest
))
272 && reg_mentioned_p (prev_dest
, PATTERN (insn
))
273 && find_regno_note (insn
, REG_DEAD
, REGNO (prev_dest
))
274 && ! side_effects_p (SET_SRC (PATTERN (prev
))))
275 lra_delete_dead_insn (prev
);
277 lra_set_insn_deleted (insn
);
280 /* Emit insn x = y + z. Return NULL if we failed to do it.
281 Otherwise, return the insn. We don't use gen_add3_insn as it might
284 emit_add3_insn (rtx x
, rtx y
, rtx z
)
288 last
= get_last_insn ();
290 if (have_addptr3_insn (x
, y
, z
))
292 rtx_insn
*insn
= gen_addptr3_insn (x
, y
, z
);
294 /* If the target provides an "addptr" pattern it hopefully does
295 for a reason. So falling back to the normal add would be
297 lra_assert (insn
!= NULL_RTX
);
302 rtx_insn
*insn
= emit_insn (gen_rtx_SET (x
, gen_rtx_PLUS (GET_MODE (y
),
304 if (recog_memoized (insn
) < 0)
306 delete_insns_since (last
);
312 /* Emit insn x = x + y. Return the insn. We use gen_add2_insn as the
315 emit_add2_insn (rtx x
, rtx y
)
317 rtx_insn
*insn
= emit_add3_insn (x
, x
, y
);
318 if (insn
== NULL_RTX
)
320 insn
= gen_add2_insn (x
, y
);
321 if (insn
!= NULL_RTX
)
327 /* Target checks operands through operand predicates to recognize an
328 insn. We should have a special precaution to generate add insns
329 which are frequent results of elimination.
331 Emit insns for x = y + z. X can be used to store intermediate
332 values and should be not in Y and Z when we use X to store an
333 intermediate value. Y + Z should form [base] [+ index[ * scale]] [
334 + disp] where base and index are registers, disp and scale are
335 constants. Y should contain base if it is present, Z should
336 contain disp if any. index[*scale] can be part of Y or Z. */
338 lra_emit_add (rtx x
, rtx y
, rtx z
)
342 rtx a1
, a2
, base
, index
, disp
, scale
, index_scale
;
345 rtx_insn
*add3_insn
= emit_add3_insn (x
, y
, z
);
346 old
= max_reg_num ();
347 if (add3_insn
!= NULL
)
351 disp
= a2
= NULL_RTX
;
352 if (GET_CODE (y
) == PLUS
)
366 index_scale
= scale
= NULL_RTX
;
367 if (GET_CODE (a1
) == MULT
)
370 index
= XEXP (a1
, 0);
371 scale
= XEXP (a1
, 1);
374 else if (a2
!= NULL_RTX
&& GET_CODE (a2
) == MULT
)
377 index
= XEXP (a2
, 0);
378 scale
= XEXP (a2
, 1);
386 if ((base
!= NULL_RTX
&& ! (REG_P (base
) || GET_CODE (base
) == SUBREG
))
387 || (index
!= NULL_RTX
388 && ! (REG_P (index
) || GET_CODE (index
) == SUBREG
))
389 || (disp
!= NULL_RTX
&& ! CONSTANT_P (disp
))
390 || (scale
!= NULL_RTX
&& ! CONSTANT_P (scale
)))
392 /* Probably we have no 3 op add. Last chance is to use 2-op
393 add insn. To succeed, don't move Z to X as an address
394 segment always comes in Y. Otherwise, we might fail when
395 adding the address segment to register. */
396 lra_assert (x
!= y
&& x
!= z
);
397 emit_move_insn (x
, y
);
398 rtx_insn
*insn
= emit_add2_insn (x
, z
);
399 lra_assert (insn
!= NULL_RTX
);
403 if (index_scale
== NULL_RTX
)
405 if (disp
== NULL_RTX
)
407 /* Generate x = index_scale; x = x + base. */
408 lra_assert (index_scale
!= NULL_RTX
&& base
!= NULL_RTX
);
409 emit_move_insn (x
, index_scale
);
410 rtx_insn
*insn
= emit_add2_insn (x
, base
);
411 lra_assert (insn
!= NULL_RTX
);
413 else if (scale
== NULL_RTX
)
415 /* Try x = base + disp. */
416 lra_assert (base
!= NULL_RTX
);
417 last
= get_last_insn ();
418 rtx_insn
*move_insn
=
419 emit_move_insn (x
, gen_rtx_PLUS (GET_MODE (base
), base
, disp
));
420 if (recog_memoized (move_insn
) < 0)
422 delete_insns_since (last
);
423 /* Generate x = disp; x = x + base. */
424 emit_move_insn (x
, disp
);
425 rtx_insn
*add2_insn
= emit_add2_insn (x
, base
);
426 lra_assert (add2_insn
!= NULL_RTX
);
428 /* Generate x = x + index. */
429 if (index
!= NULL_RTX
)
431 rtx_insn
*insn
= emit_add2_insn (x
, index
);
432 lra_assert (insn
!= NULL_RTX
);
437 /* Try x = index_scale; x = x + disp; x = x + base. */
438 last
= get_last_insn ();
439 rtx_insn
*move_insn
= emit_move_insn (x
, index_scale
);
441 if (recog_memoized (move_insn
) >= 0)
443 rtx_insn
*insn
= emit_add2_insn (x
, disp
);
444 if (insn
!= NULL_RTX
)
446 if (base
== NULL_RTX
)
450 insn
= emit_add2_insn (x
, base
);
451 if (insn
!= NULL_RTX
)
460 delete_insns_since (last
);
461 /* Generate x = disp; x = x + base; x = x + index_scale. */
462 emit_move_insn (x
, disp
);
463 if (base
!= NULL_RTX
)
465 insn
= emit_add2_insn (x
, base
);
466 lra_assert (insn
!= NULL_RTX
);
468 insn
= emit_add2_insn (x
, index_scale
);
469 lra_assert (insn
!= NULL_RTX
);
474 /* Functions emit_... can create pseudos -- so expand the pseudo
476 if (old
!= max_reg_num ())
477 expand_reg_data (old
);
480 /* The number of emitted reload insns so far. */
481 int lra_curr_reload_num
;
483 /* Emit x := y, processing special case when y = u + v or y = u + v *
484 scale + w through emit_add (Y can be an address which is base +
485 index reg * scale + displacement in general case). X may be used
486 as intermediate result therefore it should be not in Y. */
488 lra_emit_move (rtx x
, rtx y
)
492 if (GET_CODE (y
) != PLUS
)
494 if (rtx_equal_p (x
, y
))
496 old
= max_reg_num ();
497 emit_move_insn (x
, y
);
499 lra_reg_info
[ORIGINAL_REGNO (x
)].last_reload
= ++lra_curr_reload_num
;
500 /* Function emit_move can create pseudos -- so expand the pseudo
502 if (old
!= max_reg_num ())
503 expand_reg_data (old
);
506 lra_emit_add (x
, XEXP (y
, 0), XEXP (y
, 1));
509 /* Update insn operands which are duplication of operands whose
510 numbers are in array of NOPS (with end marker -1). The insn is
511 represented by its LRA internal representation ID. */
513 lra_update_dups (lra_insn_recog_data_t id
, signed char *nops
)
516 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
518 for (i
= 0; i
< static_id
->n_dups
; i
++)
519 for (j
= 0; (nop
= nops
[j
]) >= 0; j
++)
520 if (static_id
->dup_num
[i
] == nop
)
521 *id
->dup_loc
[i
] = *id
->operand_loc
[nop
];
526 /* This page contains code dealing with info about registers in the
529 /* Pools for insn reg info. */
530 object_allocator
<lra_insn_reg
> lra_insn_reg_pool ("insn regs");
532 /* Create LRA insn related info about a reference to REGNO in INSN
533 with TYPE (in/out/inout), biggest reference mode MODE, flag that it
534 is reference through subreg (SUBREG_P), flag that is early
535 clobbered in the insn (EARLY_CLOBBER), and reference to the next
536 insn reg info (NEXT). If REGNO can be early clobbered,
537 alternatives in which it can be early clobbered are given by
538 EARLY_CLOBBER_ALTS. */
539 static struct lra_insn_reg
*
540 new_insn_reg (rtx_insn
*insn
, int regno
, enum op_type type
,
542 bool subreg_p
, bool early_clobber
,
543 alternative_mask early_clobber_alts
,
544 struct lra_insn_reg
*next
)
546 lra_insn_reg
*ir
= lra_insn_reg_pool
.allocate ();
548 ir
->biggest_mode
= mode
;
549 if (NONDEBUG_INSN_P (insn
)
550 && partial_subreg_p (lra_reg_info
[regno
].biggest_mode
, mode
))
551 lra_reg_info
[regno
].biggest_mode
= mode
;
552 ir
->subreg_p
= subreg_p
;
553 ir
->early_clobber
= early_clobber
;
554 ir
->early_clobber_alts
= early_clobber_alts
;
560 /* Free insn reg info list IR. */
562 free_insn_regs (struct lra_insn_reg
*ir
)
564 struct lra_insn_reg
*next_ir
;
566 for (; ir
!= NULL
; ir
= next_ir
)
569 lra_insn_reg_pool
.remove (ir
);
573 /* Finish pool for insn reg info. */
575 finish_insn_regs (void)
577 lra_insn_reg_pool
.release ();
582 /* This page contains code dealing LRA insn info (or in other words
583 LRA internal insn representation). */
585 /* Map INSN_CODE -> the static insn data. This info is valid during
586 all translation unit. */
587 struct lra_static_insn_data
*insn_code_data
[NUM_INSN_CODES
];
589 /* Debug insns are represented as a special insn with one input
590 operand which is RTL expression in var_location. */
592 /* The following data are used as static insn operand data for all
593 debug insns. If structure lra_operand_data is changed, the
594 initializer should be changed too. */
595 static struct lra_operand_data debug_operand_data
=
597 NULL
, /* alternative */
598 0, /* early_clobber_alts */
599 E_VOIDmode
, /* We are not interesting in the operand mode. */
604 /* The following data are used as static insn data for all debug
605 insns. If structure lra_static_insn_data is changed, the
606 initializer should be changed too. */
607 static struct lra_static_insn_data debug_insn_static_data
=
610 0, /* Duplication operands #. */
611 -1, /* Commutative operand #. */
612 1, /* Operands #. There is only one operand which is debug RTL
614 0, /* Duplications #. */
615 0, /* Alternatives #. We are not interesting in alternatives
616 because we does not proceed debug_insns for reloads. */
617 NULL
, /* Hard registers referenced in machine description. */
618 NULL
/* Descriptions of operands in alternatives. */
621 /* Called once per compiler work to initialize some LRA data related
624 init_insn_code_data_once (void)
626 memset (insn_code_data
, 0, sizeof (insn_code_data
));
629 /* Called once per compiler work to finalize some LRA data related to
632 finish_insn_code_data_once (void)
634 for (unsigned int i
= 0; i
< NUM_INSN_CODES
; i
++)
636 if (insn_code_data
[i
] != NULL
)
637 free (insn_code_data
[i
]);
641 /* Return static insn data, allocate and setup if necessary. Although
642 dup_num is static data (it depends only on icode), to set it up we
643 need to extract insn first. So recog_data should be valid for
644 normal insn (ICODE >= 0) before the call. */
645 static struct lra_static_insn_data
*
646 get_static_insn_data (int icode
, int nop
, int ndup
, int nalt
)
648 struct lra_static_insn_data
*data
;
651 lra_assert (icode
< (int) NUM_INSN_CODES
);
652 if (icode
>= 0 && (data
= insn_code_data
[icode
]) != NULL
)
654 lra_assert (nop
>= 0 && ndup
>= 0 && nalt
>= 0);
655 n_bytes
= sizeof (struct lra_static_insn_data
)
656 + sizeof (struct lra_operand_data
) * nop
657 + sizeof (int) * ndup
;
658 data
= XNEWVAR (struct lra_static_insn_data
, n_bytes
);
659 data
->operand_alternative
= NULL
;
660 data
->n_operands
= nop
;
662 data
->n_alternatives
= nalt
;
663 data
->operand
= ((struct lra_operand_data
*)
664 ((char *) data
+ sizeof (struct lra_static_insn_data
)));
665 data
->dup_num
= ((int *) ((char *) data
->operand
666 + sizeof (struct lra_operand_data
) * nop
));
671 insn_code_data
[icode
] = data
;
672 for (i
= 0; i
< nop
; i
++)
674 data
->operand
[i
].constraint
675 = insn_data
[icode
].operand
[i
].constraint
;
676 data
->operand
[i
].mode
= insn_data
[icode
].operand
[i
].mode
;
677 data
->operand
[i
].strict_low
= insn_data
[icode
].operand
[i
].strict_low
;
678 data
->operand
[i
].is_operator
679 = insn_data
[icode
].operand
[i
].is_operator
;
680 data
->operand
[i
].type
681 = (data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
682 : data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
684 data
->operand
[i
].is_address
= false;
686 for (i
= 0; i
< ndup
; i
++)
687 data
->dup_num
[i
] = recog_data
.dup_num
[i
];
692 /* The current length of the following array. */
693 int lra_insn_recog_data_len
;
695 /* Map INSN_UID -> the insn recog data (NULL if unknown). */
696 lra_insn_recog_data_t
*lra_insn_recog_data
;
698 /* Initialize LRA data about insns. */
700 init_insn_recog_data (void)
702 lra_insn_recog_data_len
= 0;
703 lra_insn_recog_data
= NULL
;
706 /* Expand, if necessary, LRA data about insns. */
708 check_and_expand_insn_recog_data (int index
)
712 if (lra_insn_recog_data_len
> index
)
714 old
= lra_insn_recog_data_len
;
715 lra_insn_recog_data_len
= index
* 3 / 2 + 1;
716 lra_insn_recog_data
= XRESIZEVEC (lra_insn_recog_data_t
,
718 lra_insn_recog_data_len
);
719 for (i
= old
; i
< lra_insn_recog_data_len
; i
++)
720 lra_insn_recog_data
[i
] = NULL
;
723 /* Finish LRA DATA about insn. */
725 free_insn_recog_data (lra_insn_recog_data_t data
)
727 if (data
->operand_loc
!= NULL
)
728 free (data
->operand_loc
);
729 if (data
->dup_loc
!= NULL
)
730 free (data
->dup_loc
);
731 if (data
->arg_hard_regs
!= NULL
)
732 free (data
->arg_hard_regs
);
733 if (data
->icode
< 0 && NONDEBUG_INSN_P (data
->insn
))
735 if (data
->insn_static_data
->operand_alternative
!= NULL
)
736 free (const_cast <operand_alternative
*>
737 (data
->insn_static_data
->operand_alternative
));
738 free_insn_regs (data
->insn_static_data
->hard_regs
);
739 free (data
->insn_static_data
);
741 free_insn_regs (data
->regs
);
746 /* Pools for copies. */
747 static object_allocator
<lra_copy
> lra_copy_pool ("lra copies");
749 /* Finish LRA data about all insns. */
751 finish_insn_recog_data (void)
754 lra_insn_recog_data_t data
;
756 for (i
= 0; i
< lra_insn_recog_data_len
; i
++)
757 if ((data
= lra_insn_recog_data
[i
]) != NULL
)
758 free_insn_recog_data (data
);
760 lra_copy_pool
.release ();
761 lra_insn_reg_pool
.release ();
762 free (lra_insn_recog_data
);
765 /* Setup info about operands in alternatives of LRA DATA of insn. */
767 setup_operand_alternative (lra_insn_recog_data_t data
,
768 const operand_alternative
*op_alt
)
771 int icode
= data
->icode
;
772 struct lra_static_insn_data
*static_data
= data
->insn_static_data
;
774 static_data
->commutative
= -1;
775 nop
= static_data
->n_operands
;
776 nalt
= static_data
->n_alternatives
;
777 static_data
->operand_alternative
= op_alt
;
778 for (i
= 0; i
< nop
; i
++)
780 static_data
->operand
[i
].early_clobber_alts
= 0;
781 static_data
->operand
[i
].early_clobber
= false;
782 static_data
->operand
[i
].is_address
= false;
783 if (static_data
->operand
[i
].constraint
[0] == '%')
785 /* We currently only support one commutative pair of operands. */
786 if (static_data
->commutative
< 0)
787 static_data
->commutative
= i
;
789 lra_assert (icode
< 0); /* Asm */
790 /* The last operand should not be marked commutative. */
791 lra_assert (i
!= nop
- 1);
794 for (j
= 0; j
< nalt
; j
++)
795 for (i
= 0; i
< nop
; i
++, op_alt
++)
797 static_data
->operand
[i
].early_clobber
|= op_alt
->earlyclobber
;
798 if (op_alt
->earlyclobber
)
799 static_data
->operand
[i
].early_clobber_alts
|= (alternative_mask
) 1 << j
;
800 static_data
->operand
[i
].is_address
|= op_alt
->is_address
;
804 /* Recursively process X and collect info about registers, which are
805 not the insn operands, in X with TYPE (in/out/inout) and flag that
806 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
807 to LIST. X is a part of insn given by DATA. Return the result
809 static struct lra_insn_reg
*
810 collect_non_operand_hard_regs (rtx
*x
, lra_insn_recog_data_t data
,
811 struct lra_insn_reg
*list
,
812 enum op_type type
, bool early_clobber
)
814 int i
, j
, regno
, last
;
817 struct lra_insn_reg
*curr
;
819 enum rtx_code code
= GET_CODE (op
);
820 const char *fmt
= GET_RTX_FORMAT (code
);
822 for (i
= 0; i
< data
->insn_static_data
->n_operands
; i
++)
823 if (! data
->insn_static_data
->operand
[i
].is_operator
824 && x
== data
->operand_loc
[i
])
825 /* It is an operand loc. Stop here. */
827 for (i
= 0; i
< data
->insn_static_data
->n_dups
; i
++)
828 if (x
== data
->dup_loc
[i
])
829 /* It is a dup loc. Stop here. */
831 mode
= GET_MODE (op
);
835 op
= SUBREG_REG (op
);
836 code
= GET_CODE (op
);
837 if (GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (op
)))
839 mode
= GET_MODE (op
);
840 if (GET_MODE_SIZE (mode
) > REGMODE_NATURAL_SIZE (mode
))
846 if ((regno
= REGNO (op
)) >= FIRST_PSEUDO_REGISTER
)
848 /* Process all regs even unallocatable ones as we need info
849 about all regs for rematerialization pass. */
850 for (last
= end_hard_regno (mode
, regno
); regno
< last
; regno
++)
852 for (curr
= list
; curr
!= NULL
; curr
= curr
->next
)
853 if (curr
->regno
== regno
&& curr
->subreg_p
== subreg_p
854 && curr
->biggest_mode
== mode
)
856 if (curr
->type
!= type
)
857 curr
->type
= OP_INOUT
;
860 curr
->early_clobber
= true;
861 curr
->early_clobber_alts
= ALL_ALTERNATIVES
;
867 /* This is a new hard regno or the info can not be
868 integrated into the found structure. */
872 /* This clobber is to inform popping floating
874 && ! (FIRST_STACK_REG
<= regno
875 && regno
<= LAST_STACK_REG
));
877 list
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
879 early_clobber
? ALL_ALTERNATIVES
: 0, list
);
887 list
= collect_non_operand_hard_regs (&SET_DEST (op
), data
,
888 list
, OP_OUT
, false);
889 list
= collect_non_operand_hard_regs (&SET_SRC (op
), data
,
893 /* We treat clobber of non-operand hard registers as early
894 clobber (the behavior is expected from asm). */
895 list
= collect_non_operand_hard_regs (&XEXP (op
, 0), data
,
898 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
899 list
= collect_non_operand_hard_regs (&XEXP (op
, 0), data
,
900 list
, OP_INOUT
, false);
902 case PRE_MODIFY
: case POST_MODIFY
:
903 list
= collect_non_operand_hard_regs (&XEXP (op
, 0), data
,
904 list
, OP_INOUT
, false);
905 list
= collect_non_operand_hard_regs (&XEXP (op
, 1), data
,
909 fmt
= GET_RTX_FORMAT (code
);
910 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
913 list
= collect_non_operand_hard_regs (&XEXP (op
, i
), data
,
915 else if (fmt
[i
] == 'E')
916 for (j
= XVECLEN (op
, i
) - 1; j
>= 0; j
--)
917 list
= collect_non_operand_hard_regs (&XVECEXP (op
, i
, j
), data
,
924 /* Set up and return info about INSN. Set up the info if it is not set up
926 lra_insn_recog_data_t
927 lra_set_insn_recog_data (rtx_insn
*insn
)
929 lra_insn_recog_data_t data
;
932 unsigned int uid
= INSN_UID (insn
);
933 struct lra_static_insn_data
*insn_static_data
;
935 check_and_expand_insn_recog_data (uid
);
936 if (DEBUG_INSN_P (insn
))
940 icode
= INSN_CODE (insn
);
942 /* It might be a new simple insn which is not recognized yet. */
943 INSN_CODE (insn
) = icode
= recog_memoized (insn
);
945 data
= XNEW (struct lra_insn_recog_data
);
946 lra_insn_recog_data
[uid
] = data
;
948 data
->used_insn_alternative
= -1;
951 if (DEBUG_INSN_P (insn
))
953 data
->insn_static_data
= &debug_insn_static_data
;
954 data
->dup_loc
= NULL
;
955 data
->arg_hard_regs
= NULL
;
956 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
957 data
->operand_loc
= XNEWVEC (rtx
*, 1);
958 data
->operand_loc
[0] = &INSN_VAR_LOCATION_LOC (insn
);
964 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
965 const char *constraints
[MAX_RECOG_OPERANDS
];
967 nop
= asm_noperands (PATTERN (insn
));
968 data
->operand_loc
= data
->dup_loc
= NULL
;
972 /* It is a special insn like USE or CLOBBER. We should
973 recognize any regular insn otherwise LRA can do nothing
975 gcc_assert (GET_CODE (PATTERN (insn
)) == USE
976 || GET_CODE (PATTERN (insn
)) == CLOBBER
977 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
978 data
->insn_static_data
= insn_static_data
979 = get_static_insn_data (-1, 0, 0, nalt
);
983 /* expand_asm_operands makes sure there aren't too many
985 lra_assert (nop
<= MAX_RECOG_OPERANDS
);
987 data
->operand_loc
= XNEWVEC (rtx
*, nop
);
988 /* Now get the operand values and constraints out of the
990 decode_asm_operands (PATTERN (insn
), NULL
,
992 constraints
, operand_mode
, NULL
);
995 const char *p
= recog_data
.constraints
[0];
997 for (p
= constraints
[0]; *p
; p
++)
1000 data
->insn_static_data
= insn_static_data
1001 = get_static_insn_data (-1, nop
, 0, nalt
);
1002 for (i
= 0; i
< nop
; i
++)
1004 insn_static_data
->operand
[i
].mode
= operand_mode
[i
];
1005 insn_static_data
->operand
[i
].constraint
= constraints
[i
];
1006 insn_static_data
->operand
[i
].strict_low
= false;
1007 insn_static_data
->operand
[i
].is_operator
= false;
1008 insn_static_data
->operand
[i
].is_address
= false;
1011 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1012 insn_static_data
->operand
[i
].type
1013 = (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1014 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1016 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
1019 operand_alternative
*op_alt
= XCNEWVEC (operand_alternative
,
1021 preprocess_constraints (nop
, nalt
, constraints
, op_alt
);
1022 setup_operand_alternative (data
, op_alt
);
1027 insn_extract (insn
);
1028 data
->insn_static_data
= insn_static_data
1029 = get_static_insn_data (icode
, insn_data
[icode
].n_operands
,
1030 insn_data
[icode
].n_dups
,
1031 insn_data
[icode
].n_alternatives
);
1032 n
= insn_static_data
->n_operands
;
1037 locs
= XNEWVEC (rtx
*, n
);
1038 memcpy (locs
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1040 data
->operand_loc
= locs
;
1041 n
= insn_static_data
->n_dups
;
1046 locs
= XNEWVEC (rtx
*, n
);
1047 memcpy (locs
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1049 data
->dup_loc
= locs
;
1050 data
->preferred_alternatives
= get_preferred_alternatives (insn
);
1051 const operand_alternative
*op_alt
= preprocess_insn_constraints (icode
);
1052 if (!insn_static_data
->operand_alternative
)
1053 setup_operand_alternative (data
, op_alt
);
1054 else if (op_alt
!= insn_static_data
->operand_alternative
)
1055 insn_static_data
->operand_alternative
= op_alt
;
1057 if (GET_CODE (PATTERN (insn
)) == CLOBBER
|| GET_CODE (PATTERN (insn
)) == USE
)
1058 insn_static_data
->hard_regs
= NULL
;
1060 insn_static_data
->hard_regs
1061 = collect_non_operand_hard_regs (&PATTERN (insn
), data
,
1062 NULL
, OP_IN
, false);
1063 data
->arg_hard_regs
= NULL
;
1068 int n_hard_regs
, regno
, arg_hard_regs
[FIRST_PSEUDO_REGISTER
];
1071 /* Finding implicit hard register usage. We believe it will be
1072 not changed whatever transformations are used. Call insns
1073 are such example. */
1074 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1076 link
= XEXP (link
, 1))
1077 if (((use_p
= GET_CODE (XEXP (link
, 0)) == USE
)
1078 || GET_CODE (XEXP (link
, 0)) == CLOBBER
)
1079 && REG_P (XEXP (XEXP (link
, 0), 0)))
1081 regno
= REGNO (XEXP (XEXP (link
, 0), 0));
1082 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
1083 /* It is an argument register. */
1084 for (i
= REG_NREGS (XEXP (XEXP (link
, 0), 0)) - 1; i
>= 0; i
--)
1085 arg_hard_regs
[n_hard_regs
++]
1086 = regno
+ i
+ (use_p
? 0 : FIRST_PSEUDO_REGISTER
);
1088 if (n_hard_regs
!= 0)
1090 arg_hard_regs
[n_hard_regs
++] = -1;
1091 data
->arg_hard_regs
= XNEWVEC (int, n_hard_regs
);
1092 memcpy (data
->arg_hard_regs
, arg_hard_regs
,
1093 sizeof (int) * n_hard_regs
);
1096 /* Some output operand can be recognized only from the context not
1097 from the constraints which are empty in this case. Call insn may
1098 contain a hard register in set destination with empty constraint
1099 and extract_insn treats them as an input. */
1100 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1104 struct lra_operand_data
*operand
= &insn_static_data
->operand
[i
];
1106 /* ??? Should we treat 'X' the same way. It looks to me that
1107 'X' means anything and empty constraint means we do not
1109 if (operand
->type
!= OP_IN
|| *operand
->constraint
!= '\0'
1110 || operand
->is_operator
)
1112 pat
= PATTERN (insn
);
1113 if (GET_CODE (pat
) == SET
)
1115 if (data
->operand_loc
[i
] != &SET_DEST (pat
))
1118 else if (GET_CODE (pat
) == PARALLEL
)
1120 for (j
= XVECLEN (pat
, 0) - 1; j
>= 0; j
--)
1122 set
= XVECEXP (PATTERN (insn
), 0, j
);
1123 if (GET_CODE (set
) == SET
1124 && &SET_DEST (set
) == data
->operand_loc
[i
])
1132 operand
->type
= OP_OUT
;
1137 /* Return info about insn give by UID. The info should be already set
1139 static lra_insn_recog_data_t
1140 get_insn_recog_data_by_uid (int uid
)
1142 lra_insn_recog_data_t data
;
1144 data
= lra_insn_recog_data
[uid
];
1145 lra_assert (data
!= NULL
);
1149 /* Invalidate all info about insn given by its UID. */
1151 invalidate_insn_recog_data (int uid
)
1153 lra_insn_recog_data_t data
;
1155 data
= lra_insn_recog_data
[uid
];
1156 lra_assert (data
!= NULL
);
1157 free_insn_recog_data (data
);
1158 lra_insn_recog_data
[uid
] = NULL
;
1161 /* Update all the insn info about INSN. It is usually called when
1162 something in the insn was changed. Return the updated info. */
1163 lra_insn_recog_data_t
1164 lra_update_insn_recog_data (rtx_insn
*insn
)
1166 lra_insn_recog_data_t data
;
1168 unsigned int uid
= INSN_UID (insn
);
1169 struct lra_static_insn_data
*insn_static_data
;
1170 HOST_WIDE_INT sp_offset
= 0;
1172 check_and_expand_insn_recog_data (uid
);
1173 if ((data
= lra_insn_recog_data
[uid
]) != NULL
1174 && data
->icode
!= INSN_CODE (insn
))
1176 sp_offset
= data
->sp_offset
;
1177 invalidate_insn_data_regno_info (data
, insn
, get_insn_freq (insn
));
1178 invalidate_insn_recog_data (uid
);
1183 data
= lra_get_insn_recog_data (insn
);
1184 /* Initiate or restore SP offset. */
1185 data
->sp_offset
= sp_offset
;
1188 insn_static_data
= data
->insn_static_data
;
1189 data
->used_insn_alternative
= -1;
1190 if (DEBUG_INSN_P (insn
))
1192 if (data
->icode
< 0)
1195 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
1196 const char *constraints
[MAX_RECOG_OPERANDS
];
1198 nop
= asm_noperands (PATTERN (insn
));
1201 lra_assert (nop
== data
->insn_static_data
->n_operands
);
1202 /* Now get the operand values and constraints out of the
1204 decode_asm_operands (PATTERN (insn
), NULL
,
1206 constraints
, operand_mode
, NULL
);
1209 for (int i
= 0; i
< nop
; i
++)
1211 (insn_static_data
->operand
[i
].mode
== operand_mode
[i
]
1212 && insn_static_data
->operand
[i
].constraint
== constraints
[i
]
1213 && ! insn_static_data
->operand
[i
].is_operator
);
1217 for (int i
= 0; i
< insn_static_data
->n_operands
; i
++)
1219 (insn_static_data
->operand
[i
].type
1220 == (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1221 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1226 insn_extract (insn
);
1227 n
= insn_static_data
->n_operands
;
1229 memcpy (data
->operand_loc
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1230 n
= insn_static_data
->n_dups
;
1232 memcpy (data
->dup_loc
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1233 lra_assert (check_bool_attrs (insn
));
1238 /* Set up that INSN is using alternative ALT now. */
1240 lra_set_used_insn_alternative (rtx_insn
*insn
, int alt
)
1242 lra_insn_recog_data_t data
;
1244 data
= lra_get_insn_recog_data (insn
);
1245 data
->used_insn_alternative
= alt
;
1248 /* Set up that insn with UID is using alternative ALT now. The insn
1249 info should be already set up. */
1251 lra_set_used_insn_alternative_by_uid (int uid
, int alt
)
1253 lra_insn_recog_data_t data
;
1255 check_and_expand_insn_recog_data (uid
);
1256 data
= lra_insn_recog_data
[uid
];
1257 lra_assert (data
!= NULL
);
1258 data
->used_insn_alternative
= alt
;
1263 /* This page contains code dealing with common register info and
1266 /* The size of the following array. */
1267 static int reg_info_size
;
1268 /* Common info about each register. */
1269 struct lra_reg
*lra_reg_info
;
1271 /* Last register value. */
1272 static int last_reg_value
;
1274 /* Return new register value. */
1276 get_new_reg_value (void)
1278 return ++last_reg_value
;
1281 /* Vec referring to pseudo copies. */
1282 static vec
<lra_copy_t
> copy_vec
;
1284 /* Initialize I-th element of lra_reg_info. */
1286 initialize_lra_reg_info_element (int i
)
1288 bitmap_initialize (&lra_reg_info
[i
].insn_bitmap
, ®_obstack
);
1290 lra_reg_info
[i
].no_stack_p
= false;
1292 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
1293 CLEAR_HARD_REG_SET (lra_reg_info
[i
].actual_call_used_reg_set
);
1294 lra_reg_info
[i
].preferred_hard_regno1
= -1;
1295 lra_reg_info
[i
].preferred_hard_regno2
= -1;
1296 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
1297 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
1298 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
1299 lra_reg_info
[i
].live_ranges
= NULL
;
1300 lra_reg_info
[i
].nrefs
= lra_reg_info
[i
].freq
= 0;
1301 lra_reg_info
[i
].last_reload
= 0;
1302 lra_reg_info
[i
].restore_rtx
= NULL_RTX
;
1303 lra_reg_info
[i
].val
= get_new_reg_value ();
1304 lra_reg_info
[i
].offset
= 0;
1305 lra_reg_info
[i
].copies
= NULL
;
1308 /* Initialize common reg info and copies. */
1310 init_reg_info (void)
1315 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1316 lra_reg_info
= XNEWVEC (struct lra_reg
, reg_info_size
);
1317 for (i
= 0; i
< reg_info_size
; i
++)
1318 initialize_lra_reg_info_element (i
);
1319 copy_vec
.truncate (0);
1323 /* Finish common reg info and copies. */
1325 finish_reg_info (void)
1329 for (i
= 0; i
< reg_info_size
; i
++)
1330 bitmap_clear (&lra_reg_info
[i
].insn_bitmap
);
1331 free (lra_reg_info
);
1335 /* Expand common reg info if it is necessary. */
1337 expand_reg_info (void)
1339 int i
, old
= reg_info_size
;
1341 if (reg_info_size
> max_reg_num ())
1343 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1344 lra_reg_info
= XRESIZEVEC (struct lra_reg
, lra_reg_info
, reg_info_size
);
1345 for (i
= old
; i
< reg_info_size
; i
++)
1346 initialize_lra_reg_info_element (i
);
1349 /* Free all copies. */
1351 lra_free_copies (void)
1355 while (copy_vec
.length () != 0)
1357 cp
= copy_vec
.pop ();
1358 lra_reg_info
[cp
->regno1
].copies
= lra_reg_info
[cp
->regno2
].copies
= NULL
;
1359 lra_copy_pool
.remove (cp
);
1363 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1364 frequency is FREQ. */
1366 lra_create_copy (int regno1
, int regno2
, int freq
)
1371 lra_assert (regno1
!= regno2
);
1372 regno1_dest_p
= true;
1373 if (regno1
> regno2
)
1375 std::swap (regno1
, regno2
);
1376 regno1_dest_p
= false;
1378 cp
= lra_copy_pool
.allocate ();
1379 copy_vec
.safe_push (cp
);
1380 cp
->regno1_dest_p
= regno1_dest_p
;
1382 cp
->regno1
= regno1
;
1383 cp
->regno2
= regno2
;
1384 cp
->regno1_next
= lra_reg_info
[regno1
].copies
;
1385 lra_reg_info
[regno1
].copies
= cp
;
1386 cp
->regno2_next
= lra_reg_info
[regno2
].copies
;
1387 lra_reg_info
[regno2
].copies
= cp
;
1388 if (lra_dump_file
!= NULL
)
1389 fprintf (lra_dump_file
, " Creating copy r%d%sr%d@%d\n",
1390 regno1
, regno1_dest_p
? "<-" : "->", regno2
, freq
);
1393 /* Return N-th (0, 1, ...) copy. If there is no copy, return
1396 lra_get_copy (int n
)
1398 if (n
>= (int) copy_vec
.length ())
1405 /* This page contains code dealing with info about registers in
1408 /* Process X of insn UID recursively and add info (operand type is
1409 given by TYPE, flag of that it is early clobber is EARLY_CLOBBER)
1410 about registers in X to the insn DATA. If X can be early clobbered,
1411 alternatives in which it can be early clobbered are given by
1412 EARLY_CLOBBER_ALTS. */
1414 add_regs_to_insn_regno_info (lra_insn_recog_data_t data
, rtx x
, int uid
,
1415 enum op_type type
, bool early_clobber
,
1416 alternative_mask early_clobber_alts
)
1423 struct lra_insn_reg
*curr
;
1425 code
= GET_CODE (x
);
1426 mode
= GET_MODE (x
);
1428 if (GET_CODE (x
) == SUBREG
)
1431 code
= GET_CODE (x
);
1432 if (GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (x
)))
1434 mode
= GET_MODE (x
);
1435 if (GET_MODE_SIZE (mode
) > REGMODE_NATURAL_SIZE (mode
))
1442 /* Process all regs even unallocatable ones as we need info about
1443 all regs for rematerialization pass. */
1445 if (bitmap_set_bit (&lra_reg_info
[regno
].insn_bitmap
, uid
))
1447 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
1448 early_clobber
, early_clobber_alts
,
1454 for (curr
= data
->regs
; curr
!= NULL
; curr
= curr
->next
)
1455 if (curr
->regno
== regno
)
1457 if (curr
->subreg_p
!= subreg_p
|| curr
->biggest_mode
!= mode
)
1458 /* The info can not be integrated into the found
1460 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
,
1461 subreg_p
, early_clobber
,
1462 early_clobber_alts
, data
->regs
);
1465 if (curr
->type
!= type
)
1466 curr
->type
= OP_INOUT
;
1467 if (curr
->early_clobber
!= early_clobber
)
1468 curr
->early_clobber
= true;
1469 curr
->early_clobber_alts
|= early_clobber_alts
;
1480 add_regs_to_insn_regno_info (data
, SET_DEST (x
), uid
, OP_OUT
, false, 0);
1481 add_regs_to_insn_regno_info (data
, SET_SRC (x
), uid
, OP_IN
, false, 0);
1484 /* We treat clobber of non-operand hard registers as early
1485 clobber (the behavior is expected from asm). */
1486 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), uid
, OP_OUT
, true, ALL_ALTERNATIVES
);
1488 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
1489 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), uid
, OP_INOUT
, false, 0);
1491 case PRE_MODIFY
: case POST_MODIFY
:
1492 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), uid
, OP_INOUT
, false, 0);
1493 add_regs_to_insn_regno_info (data
, XEXP (x
, 1), uid
, OP_IN
, false, 0);
1496 if ((code
!= PARALLEL
&& code
!= EXPR_LIST
) || type
!= OP_OUT
)
1497 /* Some targets place small structures in registers for return
1498 values of functions, and those registers are wrapped in
1499 PARALLEL that we may see as the destination of a SET. Here
1502 (call_insn 13 12 14 2 (set (parallel:BLK [
1503 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1505 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1506 (const_int 8 [0x8]))
1508 (call (mem:QI (symbol_ref:DI (... */
1510 fmt
= GET_RTX_FORMAT (code
);
1511 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1514 add_regs_to_insn_regno_info (data
, XEXP (x
, i
), uid
, type
, false, 0);
1515 else if (fmt
[i
] == 'E')
1517 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1518 add_regs_to_insn_regno_info (data
, XVECEXP (x
, i
, j
), uid
,
1525 /* Return execution frequency of INSN. */
1527 get_insn_freq (rtx_insn
*insn
)
1529 basic_block bb
= BLOCK_FOR_INSN (insn
);
1531 gcc_checking_assert (bb
!= NULL
);
1532 return REG_FREQ_FROM_BB (bb
);
1535 /* Invalidate all reg info of INSN with DATA and execution frequency
1536 FREQ. Update common info about the invalidated registers. */
1538 invalidate_insn_data_regno_info (lra_insn_recog_data_t data
, rtx_insn
*insn
,
1544 struct lra_insn_reg
*ir
, *next_ir
;
1546 uid
= INSN_UID (insn
);
1547 debug_p
= DEBUG_INSN_P (insn
);
1548 for (ir
= data
->regs
; ir
!= NULL
; ir
= next_ir
)
1552 lra_insn_reg_pool
.remove (ir
);
1553 bitmap_clear_bit (&lra_reg_info
[i
].insn_bitmap
, uid
);
1554 if (i
>= FIRST_PSEUDO_REGISTER
&& ! debug_p
)
1556 lra_reg_info
[i
].nrefs
--;
1557 lra_reg_info
[i
].freq
-= freq
;
1558 lra_assert (lra_reg_info
[i
].nrefs
>= 0 && lra_reg_info
[i
].freq
>= 0);
1564 /* Invalidate all reg info of INSN. Update common info about the
1565 invalidated registers. */
1567 lra_invalidate_insn_regno_info (rtx_insn
*insn
)
1569 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn
), insn
,
1570 get_insn_freq (insn
));
1573 /* Update common reg info from reg info of insn given by its DATA and
1574 execution frequency FREQ. */
1576 setup_insn_reg_info (lra_insn_recog_data_t data
, int freq
)
1579 struct lra_insn_reg
*ir
;
1581 for (ir
= data
->regs
; ir
!= NULL
; ir
= ir
->next
)
1582 if ((i
= ir
->regno
) >= FIRST_PSEUDO_REGISTER
)
1584 lra_reg_info
[i
].nrefs
++;
1585 lra_reg_info
[i
].freq
+= freq
;
1589 /* Set up insn reg info of INSN. Update common reg info from reg info
1592 lra_update_insn_regno_info (rtx_insn
*insn
)
1595 lra_insn_recog_data_t data
;
1596 struct lra_static_insn_data
*static_data
;
1600 if (! INSN_P (insn
))
1602 data
= lra_get_insn_recog_data (insn
);
1603 static_data
= data
->insn_static_data
;
1604 freq
= get_insn_freq (insn
);
1605 invalidate_insn_data_regno_info (data
, insn
, freq
);
1606 uid
= INSN_UID (insn
);
1607 for (i
= static_data
->n_operands
- 1; i
>= 0; i
--)
1608 add_regs_to_insn_regno_info (data
, *data
->operand_loc
[i
], uid
,
1609 static_data
->operand
[i
].type
,
1610 static_data
->operand
[i
].early_clobber
,
1611 static_data
->operand
[i
].early_clobber_alts
);
1612 if ((code
= GET_CODE (PATTERN (insn
))) == CLOBBER
|| code
== USE
)
1613 add_regs_to_insn_regno_info (data
, XEXP (PATTERN (insn
), 0), uid
,
1614 code
== USE
? OP_IN
: OP_OUT
, false, 0);
1616 /* On some targets call insns can refer to pseudos in memory in
1617 CALL_INSN_FUNCTION_USAGE list. Process them in order to
1618 consider their occurrences in calls for different
1619 transformations (e.g. inheritance) with given pseudos. */
1620 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1622 link
= XEXP (link
, 1))
1623 if (((code
= GET_CODE (XEXP (link
, 0))) == USE
|| code
== CLOBBER
)
1624 && MEM_P (XEXP (XEXP (link
, 0), 0)))
1625 add_regs_to_insn_regno_info (data
, XEXP (XEXP (link
, 0), 0), uid
,
1626 code
== USE
? OP_IN
: OP_OUT
, false, 0);
1627 if (NONDEBUG_INSN_P (insn
))
1628 setup_insn_reg_info (data
, freq
);
1631 /* Return reg info of insn given by it UID. */
1632 struct lra_insn_reg
*
1633 lra_get_insn_regs (int uid
)
1635 lra_insn_recog_data_t data
;
1637 data
= get_insn_recog_data_by_uid (uid
);
1643 /* Recursive hash function for RTL X. */
1645 lra_rtx_hash (rtx x
)
1655 code
= GET_CODE (x
);
1656 val
+= (int) code
+ 4095;
1658 /* Some RTL can be compared nonrecursively. */
1662 return val
+ REGNO (x
);
1665 return iterative_hash_object (XEXP (x
, 0), val
);
1668 return iterative_hash_object (XSTR (x
, 0), val
);
1680 /* Hash the elements. */
1681 fmt
= GET_RTX_FORMAT (code
);
1682 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1687 val
+= XWINT (x
, i
);
1697 val
+= XVECLEN (x
, i
);
1699 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1700 val
+= lra_rtx_hash (XVECEXP (x
, i
, j
));
1704 val
+= lra_rtx_hash (XEXP (x
, i
));
1709 val
+= htab_hash_string (XSTR (x
, i
));
1717 /* It is believed that rtx's at this level will never
1718 contain anything but integers and other rtx's, except for
1719 within LABEL_REFs and SYMBOL_REFs. */
1729 /* This page contains code dealing with stack of the insns which
1730 should be processed by the next constraint pass. */
1732 /* Bitmap used to put an insn on the stack only in one exemplar. */
1733 static sbitmap lra_constraint_insn_stack_bitmap
;
1735 /* The stack itself. */
1736 vec
<rtx_insn
*> lra_constraint_insn_stack
;
1738 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1739 info for INSN, otherwise only update it if INSN is not already on the
1742 lra_push_insn_1 (rtx_insn
*insn
, bool always_update
)
1744 unsigned int uid
= INSN_UID (insn
);
1746 lra_update_insn_regno_info (insn
);
1747 if (uid
>= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap
))
1748 lra_constraint_insn_stack_bitmap
=
1749 sbitmap_resize (lra_constraint_insn_stack_bitmap
, 3 * uid
/ 2, 0);
1750 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap
, uid
))
1752 bitmap_set_bit (lra_constraint_insn_stack_bitmap
, uid
);
1753 if (! always_update
)
1754 lra_update_insn_regno_info (insn
);
1755 lra_constraint_insn_stack
.safe_push (insn
);
1758 /* Put INSN on the stack. */
1760 lra_push_insn (rtx_insn
*insn
)
1762 lra_push_insn_1 (insn
, false);
1765 /* Put INSN on the stack and update its reg info. */
1767 lra_push_insn_and_update_insn_regno_info (rtx_insn
*insn
)
1769 lra_push_insn_1 (insn
, true);
1772 /* Put insn with UID on the stack. */
1774 lra_push_insn_by_uid (unsigned int uid
)
1776 lra_push_insn (lra_insn_recog_data
[uid
]->insn
);
1779 /* Take the last-inserted insns off the stack and return it. */
1783 rtx_insn
*insn
= lra_constraint_insn_stack
.pop ();
1784 bitmap_clear_bit (lra_constraint_insn_stack_bitmap
, INSN_UID (insn
));
1788 /* Return the current size of the insn stack. */
1790 lra_insn_stack_length (void)
1792 return lra_constraint_insn_stack
.length ();
1795 /* Push insns FROM to TO (excluding it) going in reverse order. */
1797 push_insns (rtx_insn
*from
, rtx_insn
*to
)
1801 if (from
== NULL_RTX
)
1803 for (insn
= from
; insn
!= to
; insn
= PREV_INSN (insn
))
1805 lra_push_insn (insn
);
1808 /* Set up sp offset for insn in range [FROM, LAST]. The offset is
1809 taken from the next BB insn after LAST or zero if there in such
1812 setup_sp_offset (rtx_insn
*from
, rtx_insn
*last
)
1814 rtx_insn
*before
= next_nonnote_insn_bb (last
);
1815 HOST_WIDE_INT offset
= (before
== NULL_RTX
|| ! INSN_P (before
)
1816 ? 0 : lra_get_insn_recog_data (before
)->sp_offset
);
1818 for (rtx_insn
*insn
= from
; insn
!= NEXT_INSN (last
); insn
= NEXT_INSN (insn
))
1819 lra_get_insn_recog_data (insn
)->sp_offset
= offset
;
1822 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1823 insns onto the stack. Print about emitting the insns with
1826 lra_process_new_insns (rtx_insn
*insn
, rtx_insn
*before
, rtx_insn
*after
,
1831 if (before
== NULL_RTX
&& after
== NULL_RTX
)
1833 if (lra_dump_file
!= NULL
)
1835 dump_insn_slim (lra_dump_file
, insn
);
1836 if (before
!= NULL_RTX
)
1838 fprintf (lra_dump_file
," %s before:\n", title
);
1839 dump_rtl_slim (lra_dump_file
, before
, NULL
, -1, 0);
1841 if (after
!= NULL_RTX
)
1843 fprintf (lra_dump_file
, " %s after:\n", title
);
1844 dump_rtl_slim (lra_dump_file
, after
, NULL
, -1, 0);
1846 fprintf (lra_dump_file
, "\n");
1848 if (before
!= NULL_RTX
)
1850 if (cfun
->can_throw_non_call_exceptions
)
1851 copy_reg_eh_region_note_forward (insn
, before
, NULL
);
1852 emit_insn_before (before
, insn
);
1853 push_insns (PREV_INSN (insn
), PREV_INSN (before
));
1854 setup_sp_offset (before
, PREV_INSN (insn
));
1856 if (after
!= NULL_RTX
)
1858 if (cfun
->can_throw_non_call_exceptions
)
1859 copy_reg_eh_region_note_forward (insn
, after
, NULL
);
1860 for (last
= after
; NEXT_INSN (last
) != NULL_RTX
; last
= NEXT_INSN (last
))
1862 emit_insn_after (after
, insn
);
1863 push_insns (last
, insn
);
1864 setup_sp_offset (after
, last
);
1866 if (cfun
->can_throw_non_call_exceptions
)
1868 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
1869 if (note
&& !insn_could_throw_p (insn
))
1870 remove_note (insn
, note
);
1875 /* Replace all references to register OLD_REGNO in *LOC with pseudo
1876 register NEW_REG. Try to simplify subreg of constant if SUBREG_P.
1877 Return true if any change was made. */
1879 lra_substitute_pseudo (rtx
*loc
, int old_regno
, rtx new_reg
, bool subreg_p
)
1882 bool result
= false;
1890 code
= GET_CODE (x
);
1891 if (code
== SUBREG
&& subreg_p
)
1893 rtx subst
, inner
= SUBREG_REG (x
);
1894 /* Transform subreg of constant while we still have inner mode
1895 of the subreg. The subreg internal should not be an insn
1897 if (REG_P (inner
) && (int) REGNO (inner
) == old_regno
1898 && CONSTANT_P (new_reg
)
1899 && (subst
= simplify_subreg (GET_MODE (x
), new_reg
, GET_MODE (inner
),
1900 SUBREG_BYTE (x
))) != NULL_RTX
)
1907 else if (code
== REG
&& (int) REGNO (x
) == old_regno
)
1909 machine_mode mode
= GET_MODE (x
);
1910 machine_mode inner_mode
= GET_MODE (new_reg
);
1912 if (mode
!= inner_mode
1913 && ! (CONST_INT_P (new_reg
) && SCALAR_INT_MODE_P (mode
)))
1915 if (!partial_subreg_p (mode
, inner_mode
)
1916 || ! SCALAR_INT_MODE_P (inner_mode
))
1917 new_reg
= gen_rtx_SUBREG (mode
, new_reg
, 0);
1919 new_reg
= gen_lowpart_SUBREG (mode
, new_reg
);
1925 /* Scan all the operand sub-expressions. */
1926 fmt
= GET_RTX_FORMAT (code
);
1927 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1931 if (lra_substitute_pseudo (&XEXP (x
, i
), old_regno
,
1935 else if (fmt
[i
] == 'E')
1937 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1938 if (lra_substitute_pseudo (&XVECEXP (x
, i
, j
), old_regno
,
1946 /* Call lra_substitute_pseudo within an insn. Try to simplify subreg
1947 of constant if SUBREG_P. This won't update the insn ptr, just the
1948 contents of the insn. */
1950 lra_substitute_pseudo_within_insn (rtx_insn
*insn
, int old_regno
,
1951 rtx new_reg
, bool subreg_p
)
1954 return lra_substitute_pseudo (&loc
, old_regno
, new_reg
, subreg_p
);
1959 /* This page contains code dealing with scratches (changing them onto
1960 pseudos and restoring them from the pseudos).
1962 We change scratches into pseudos at the beginning of LRA to
1963 simplify dealing with them (conflicts, hard register assignments).
1965 If the pseudo denoting scratch was spilled it means that we do need
1966 a hard register for it. Such pseudos are transformed back to
1967 scratches at the end of LRA. */
1969 /* Description of location of a former scratch operand. */
1972 rtx_insn
*insn
; /* Insn where the scratch was. */
1973 int nop
; /* Number of the operand which was a scratch. */
1976 typedef struct sloc
*sloc_t
;
1978 /* Locations of the former scratches. */
1979 static vec
<sloc_t
> scratches
;
1981 /* Bitmap of scratch regnos. */
1982 static bitmap_head scratch_bitmap
;
1984 /* Bitmap of scratch operands. */
1985 static bitmap_head scratch_operand_bitmap
;
1987 /* Return true if pseudo REGNO is made of SCRATCH. */
1989 lra_former_scratch_p (int regno
)
1991 return bitmap_bit_p (&scratch_bitmap
, regno
);
1994 /* Return true if the operand NOP of INSN is a former scratch. */
1996 lra_former_scratch_operand_p (rtx_insn
*insn
, int nop
)
1998 return bitmap_bit_p (&scratch_operand_bitmap
,
1999 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
) != 0;
2002 /* Register operand NOP in INSN as a former scratch. It will be
2003 changed to scratch back, if it is necessary, at the LRA end. */
2005 lra_register_new_scratch_op (rtx_insn
*insn
, int nop
)
2007 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
2008 rtx op
= *id
->operand_loc
[nop
];
2009 sloc_t loc
= XNEW (struct sloc
);
2010 lra_assert (REG_P (op
));
2013 scratches
.safe_push (loc
);
2014 bitmap_set_bit (&scratch_bitmap
, REGNO (op
));
2015 bitmap_set_bit (&scratch_operand_bitmap
,
2016 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
);
2017 add_reg_note (insn
, REG_UNUSED
, op
);
2020 /* Change scratches onto pseudos and save their location. */
2022 remove_scratches (void)
2025 bool insn_changed_p
;
2029 lra_insn_recog_data_t id
;
2030 struct lra_static_insn_data
*static_id
;
2032 scratches
.create (get_max_uid ());
2033 bitmap_initialize (&scratch_bitmap
, ®_obstack
);
2034 bitmap_initialize (&scratch_operand_bitmap
, ®_obstack
);
2035 FOR_EACH_BB_FN (bb
, cfun
)
2036 FOR_BB_INSNS (bb
, insn
)
2039 id
= lra_get_insn_recog_data (insn
);
2040 static_id
= id
->insn_static_data
;
2041 insn_changed_p
= false;
2042 for (i
= 0; i
< static_id
->n_operands
; i
++)
2043 if (GET_CODE (*id
->operand_loc
[i
]) == SCRATCH
2044 && GET_MODE (*id
->operand_loc
[i
]) != VOIDmode
)
2046 insn_changed_p
= true;
2047 *id
->operand_loc
[i
] = reg
2048 = lra_create_new_reg (static_id
->operand
[i
].mode
,
2049 *id
->operand_loc
[i
], ALL_REGS
, NULL
);
2050 lra_register_new_scratch_op (insn
, i
);
2051 if (lra_dump_file
!= NULL
)
2052 fprintf (lra_dump_file
,
2053 "Removing SCRATCH in insn #%u (nop %d)\n",
2054 INSN_UID (insn
), i
);
2057 /* Because we might use DF right after caller-saves sub-pass
2058 we need to keep DF info up to date. */
2059 df_insn_rescan (insn
);
2063 /* Changes pseudos created by function remove_scratches onto scratches. */
2065 restore_scratches (void)
2070 rtx_insn
*last
= NULL
;
2071 lra_insn_recog_data_t id
= NULL
;
2073 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
2075 /* Ignore already deleted insns. */
2076 if (NOTE_P (loc
->insn
)
2077 && NOTE_KIND (loc
->insn
) == NOTE_INSN_DELETED
)
2079 if (last
!= loc
->insn
)
2082 id
= lra_get_insn_recog_data (last
);
2084 if (REG_P (*id
->operand_loc
[loc
->nop
])
2085 && ((regno
= REGNO (*id
->operand_loc
[loc
->nop
]))
2086 >= FIRST_PSEUDO_REGISTER
)
2087 && lra_get_regno_hard_regno (regno
) < 0)
2089 /* It should be only case when scratch register with chosen
2090 constraint 'X' did not get memory or hard register. */
2091 lra_assert (lra_former_scratch_p (regno
));
2092 *id
->operand_loc
[loc
->nop
]
2093 = gen_rtx_SCRATCH (GET_MODE (*id
->operand_loc
[loc
->nop
]));
2094 lra_update_dup (id
, loc
->nop
);
2095 if (lra_dump_file
!= NULL
)
2096 fprintf (lra_dump_file
, "Restoring SCRATCH in insn #%u(nop %d)\n",
2097 INSN_UID (loc
->insn
), loc
->nop
);
2100 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
2102 scratches
.release ();
2103 bitmap_clear (&scratch_bitmap
);
2104 bitmap_clear (&scratch_operand_bitmap
);
2109 /* Function checks RTL for correctness. If FINAL_P is true, it is
2110 done at the end of LRA and the check is more rigorous. */
2112 check_rtl (bool final_p
)
2117 lra_assert (! final_p
|| reload_completed
);
2118 FOR_EACH_BB_FN (bb
, cfun
)
2119 FOR_BB_INSNS (bb
, insn
)
2120 if (NONDEBUG_INSN_P (insn
)
2121 && GET_CODE (PATTERN (insn
)) != USE
2122 && GET_CODE (PATTERN (insn
)) != CLOBBER
2123 && GET_CODE (PATTERN (insn
)) != ASM_INPUT
)
2127 extract_constrain_insn (insn
);
2130 /* LRA code is based on assumption that all addresses can be
2131 correctly decomposed. LRA can generate reloads for
2132 decomposable addresses. The decomposition code checks the
2133 correctness of the addresses. So we don't need to check
2134 the addresses here. Don't call insn_invalid_p here, it can
2135 change the code at this stage. */
2136 if (recog_memoized (insn
) < 0 && asm_noperands (PATTERN (insn
)) < 0)
2137 fatal_insn_not_found (insn
);
2141 /* Determine if the current function has an exception receiver block
2142 that reaches the exit block via non-exceptional edges */
2144 has_nonexceptional_receiver (void)
2148 basic_block
*tos
, *worklist
, bb
;
2150 /* If we're not optimizing, then just err on the safe side. */
2154 /* First determine which blocks can reach exit via normal paths. */
2155 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
) + 1);
2157 FOR_EACH_BB_FN (bb
, cfun
)
2158 bb
->flags
&= ~BB_REACHABLE
;
2160 /* Place the exit block on our worklist. */
2161 EXIT_BLOCK_PTR_FOR_FN (cfun
)->flags
|= BB_REACHABLE
;
2162 *tos
++ = EXIT_BLOCK_PTR_FOR_FN (cfun
);
2164 /* Iterate: find everything reachable from what we've already seen. */
2165 while (tos
!= worklist
)
2169 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2170 if (e
->flags
& EDGE_ABNORMAL
)
2177 basic_block src
= e
->src
;
2179 if (!(src
->flags
& BB_REACHABLE
))
2181 src
->flags
|= BB_REACHABLE
;
2187 /* No exceptional block reached exit unexceptionally. */
2192 /* Process recursively X of INSN and add REG_INC notes if necessary. */
2194 add_auto_inc_notes (rtx_insn
*insn
, rtx x
)
2196 enum rtx_code code
= GET_CODE (x
);
2200 if (code
== MEM
&& auto_inc_p (XEXP (x
, 0)))
2202 add_reg_note (insn
, REG_INC
, XEXP (XEXP (x
, 0), 0));
2206 /* Scan all X sub-expressions. */
2207 fmt
= GET_RTX_FORMAT (code
);
2208 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2211 add_auto_inc_notes (insn
, XEXP (x
, i
));
2212 else if (fmt
[i
] == 'E')
2213 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2214 add_auto_inc_notes (insn
, XVECEXP (x
, i
, j
));
2219 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2220 We change pseudos by hard registers without notification of DF and
2221 that can make the notes obsolete. DF-infrastructure does not deal
2222 with REG_INC notes -- so we should regenerate them here. */
2224 update_inc_notes (void)
2230 FOR_EACH_BB_FN (bb
, cfun
)
2231 FOR_BB_INSNS (bb
, insn
)
2232 if (NONDEBUG_INSN_P (insn
))
2234 pnote
= ®_NOTES (insn
);
2237 if (REG_NOTE_KIND (*pnote
) == REG_DEAD
2238 || REG_NOTE_KIND (*pnote
) == REG_UNUSED
2239 || REG_NOTE_KIND (*pnote
) == REG_INC
)
2240 *pnote
= XEXP (*pnote
, 1);
2242 pnote
= &XEXP (*pnote
, 1);
2246 add_auto_inc_notes (insn
, PATTERN (insn
));
2250 /* Set to 1 while in lra. */
2251 int lra_in_progress
;
2253 /* Start of pseudo regnos before the LRA. */
2254 int lra_new_regno_start
;
2256 /* Start of reload pseudo regnos before the new spill pass. */
2257 int lra_constraint_new_regno_start
;
2259 /* Avoid spilling pseudos with regno more than the following value if
2261 int lra_bad_spill_regno_start
;
2263 /* Inheritance pseudo regnos before the new spill pass. */
2264 bitmap_head lra_inheritance_pseudos
;
2266 /* Split regnos before the new spill pass. */
2267 bitmap_head lra_split_regs
;
2269 /* Reload pseudo regnos before the new assignment pass which still can
2270 be spilled after the assignment pass as memory is also accepted in
2271 insns for the reload pseudos. */
2272 bitmap_head lra_optional_reload_pseudos
;
2274 /* Pseudo regnos used for subreg reloads before the new assignment
2275 pass. Such pseudos still can be spilled after the assignment
2277 bitmap_head lra_subreg_reload_pseudos
;
2279 /* File used for output of LRA debug information. */
2280 FILE *lra_dump_file
;
2282 /* True if we should try spill into registers of different classes
2283 instead of memory. */
2284 bool lra_reg_spill_p
;
2286 /* Set up value LRA_REG_SPILL_P. */
2288 setup_reg_spill_flag (void)
2292 if (targetm
.spill_class
!= NULL
)
2293 for (cl
= 0; cl
< (int) LIM_REG_CLASSES
; cl
++)
2294 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
2295 if (targetm
.spill_class ((enum reg_class
) cl
,
2296 (machine_mode
) mode
) != NO_REGS
)
2298 lra_reg_spill_p
= true;
2301 lra_reg_spill_p
= false;
2304 /* True if the current function is too big to use regular algorithms
2305 in LRA. In other words, we should use simpler and faster algorithms
2306 in LRA. It also means we should not worry about generation code
2307 for caller saves. The value is set up in IRA. */
2310 /* Major LRA entry function. F is a file should be used to dump LRA
2316 bool live_p
, inserted_p
;
2320 timevar_push (TV_LRA
);
2322 /* Make sure that the last insn is a note. Some subsequent passes
2324 emit_note (NOTE_INSN_DELETED
);
2326 COPY_HARD_REG_SET (lra_no_alloc_regs
, ira_no_alloc_regs
);
2331 init_insn_recog_data ();
2333 /* Some quick check on RTL generated by previous passes. */
2337 lra_in_progress
= 1;
2339 lra_live_range_iter
= lra_coalesce_iter
= lra_constraint_iter
= 0;
2340 lra_assignment_iter
= lra_assignment_iter_after_spill
= 0;
2341 lra_inheritance_iter
= lra_undo_inheritance_iter
= 0;
2342 lra_rematerialization_iter
= 0;
2344 setup_reg_spill_flag ();
2346 /* Function remove_scratches can creates new pseudos for clobbers --
2347 so set up lra_constraint_new_regno_start before its call to
2348 permit changing reg classes for pseudos created by this
2350 lra_constraint_new_regno_start
= lra_new_regno_start
= max_reg_num ();
2351 lra_bad_spill_regno_start
= INT_MAX
;
2352 remove_scratches ();
2354 /* A function that has a non-local label that can reach the exit
2355 block via non-exceptional paths must save all call-saved
2357 if (cfun
->has_nonlocal_label
&& has_nonexceptional_receiver ())
2358 crtl
->saves_all_registers
= 1;
2360 if (crtl
->saves_all_registers
)
2361 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2362 if (! call_used_regs
[i
] && ! fixed_regs
[i
] && ! LOCAL_REGNO (i
))
2363 df_set_regs_ever_live (i
, true);
2365 /* We don't DF from now and avoid its using because it is to
2366 expensive when a lot of RTL changes are made. */
2367 df_set_flags (DF_NO_INSN_RESCAN
);
2368 lra_constraint_insn_stack
.create (get_max_uid ());
2369 lra_constraint_insn_stack_bitmap
= sbitmap_alloc (get_max_uid ());
2370 bitmap_clear (lra_constraint_insn_stack_bitmap
);
2371 lra_live_ranges_init ();
2372 lra_constraints_init ();
2373 lra_curr_reload_num
= 0;
2374 push_insns (get_last_insn (), NULL
);
2375 /* It is needed for the 1st coalescing. */
2376 bitmap_initialize (&lra_inheritance_pseudos
, ®_obstack
);
2377 bitmap_initialize (&lra_split_regs
, ®_obstack
);
2378 bitmap_initialize (&lra_optional_reload_pseudos
, ®_obstack
);
2379 bitmap_initialize (&lra_subreg_reload_pseudos
, ®_obstack
);
2381 if (get_frame_size () != 0 && crtl
->stack_alignment_needed
)
2382 /* If we have a stack frame, we must align it now. The stack size
2383 may be a part of the offset computation for register
2385 assign_stack_local (BLKmode
, 0, crtl
->stack_alignment_needed
);
2391 bool reloads_p
= lra_constraints (lra_constraint_iter
== 0);
2392 /* Constraint transformations may result in that eliminable
2393 hard regs become uneliminable and pseudos which use them
2394 should be spilled. It is better to do it before pseudo
2397 For example, rs6000 can make
2398 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2399 to use a constant pool. */
2400 lra_eliminate (false, false);
2401 /* We should try to assign hard registers to scratches even
2402 if there were no RTL transformations in lra_constraints.
2403 Also we should check IRA assignments on the first
2404 iteration as they can be wrong because of early clobbers
2405 operands which are ignored in IRA. */
2406 if (! reloads_p
&& lra_constraint_iter
> 1)
2408 /* Stack is not empty here only when there are changes
2409 during the elimination sub-pass. */
2410 if (bitmap_empty_p (lra_constraint_insn_stack_bitmap
))
2413 /* If there are no reloads but changing due
2414 elimination, restart the constraint sub-pass
2418 /* Do inheritance only for regular algorithms. */
2424 lra_clear_live_ranges ();
2425 /* As a side-effect of lra_create_live_ranges, we calculate
2426 actual_call_used_reg_set, which is needed during
2428 lra_create_live_ranges (true, true);
2434 lra_clear_live_ranges ();
2435 /* We need live ranges for lra_assign -- so build them. But
2436 don't remove dead insns or change global live info as we
2437 can undo inheritance transformations after inheritance
2438 pseudo assigning. */
2439 lra_create_live_ranges (true, false);
2441 /* If we don't spill non-reload and non-inheritance pseudos,
2442 there is no sense to run memory-memory move coalescing.
2443 If inheritance pseudos were spilled, the memory-memory
2444 moves involving them will be removed by pass undoing
2450 bool spill_p
= !lra_assign ();
2452 if (lra_undo_inheritance ())
2458 lra_create_live_ranges (true, true);
2461 if (lra_coalesce ())
2465 lra_clear_live_ranges ();
2468 /* Don't clear optional reloads bitmap until all constraints are
2469 satisfied as we need to differ them from regular reloads. */
2470 bitmap_clear (&lra_optional_reload_pseudos
);
2471 bitmap_clear (&lra_subreg_reload_pseudos
);
2472 bitmap_clear (&lra_inheritance_pseudos
);
2473 bitmap_clear (&lra_split_regs
);
2476 /* We need full live info for spilling pseudos into
2477 registers instead of memory. */
2478 lra_create_live_ranges (lra_reg_spill_p
, true);
2481 /* We should check necessity for spilling here as the above live
2482 range pass can remove spilled pseudos. */
2483 if (! lra_need_for_spills_p ())
2485 /* Now we know what pseudos should be spilled. Try to
2486 rematerialize them first. */
2489 /* We need full live info -- see the comment above. */
2490 lra_create_live_ranges (lra_reg_spill_p
, true);
2492 if (! lra_need_for_spills_p ())
2496 /* Assignment of stack slots changes elimination offsets for
2497 some eliminations. So update the offsets here. */
2498 lra_eliminate (false, false);
2499 lra_constraint_new_regno_start
= max_reg_num ();
2500 if (lra_bad_spill_regno_start
== INT_MAX
2501 && lra_inheritance_iter
> LRA_MAX_INHERITANCE_PASSES
2502 && lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
2503 /* After switching off inheritance and rematerialization
2504 passes, avoid spilling reload pseudos will be created to
2505 prevent LRA cycling in some complicated cases. */
2506 lra_bad_spill_regno_start
= lra_constraint_new_regno_start
;
2507 lra_assignment_iter_after_spill
= 0;
2509 restore_scratches ();
2510 lra_eliminate (true, false);
2511 lra_final_code_change ();
2512 lra_in_progress
= 0;
2514 lra_clear_live_ranges ();
2515 lra_live_ranges_finish ();
2516 lra_constraints_finish ();
2518 sbitmap_free (lra_constraint_insn_stack_bitmap
);
2519 lra_constraint_insn_stack
.release ();
2520 finish_insn_recog_data ();
2521 regstat_free_n_sets_and_refs ();
2523 reload_completed
= 1;
2524 update_inc_notes ();
2526 inserted_p
= fixup_abnormal_edges ();
2528 /* We've possibly turned single trapping insn into multiple ones. */
2529 if (cfun
->can_throw_non_call_exceptions
)
2531 auto_sbitmap
blocks (last_basic_block_for_fn (cfun
));
2532 bitmap_ones (blocks
);
2533 find_many_sub_basic_blocks (blocks
);
2537 commit_edge_insertions ();
2539 /* Replacing pseudos with their memory equivalents might have
2540 created shared rtx. Subsequent passes would get confused
2541 by this, so unshare everything here. */
2542 unshare_all_rtl_again (get_insns ());
2547 timevar_pop (TV_LRA
);
2550 /* Called once per compiler to initialize LRA data once. */
2552 lra_init_once (void)
2554 init_insn_code_data_once ();
2557 /* Called once per compiler to finish LRA data which are initialize
2560 lra_finish_once (void)
2562 finish_insn_code_data_once ();