1 /* LRA (local register allocator) driver and LRA utilities.
2 Copyright (C) 2010-2015 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"
119 #include "addresses.h"
129 #include "cfgbuild.h"
131 #include "tree-pass.h"
133 #include "insn-attr.h"
135 #include "print-rtl.h"
137 /* Dump bitmap SET with TITLE and BB INDEX. */
139 lra_dump_bitmap_with_title (const char *title
, bitmap set
, int index
)
144 static const int max_nums_on_line
= 10;
146 if (bitmap_empty_p (set
))
148 fprintf (lra_dump_file
, " %s %d:", title
, index
);
149 fprintf (lra_dump_file
, "\n");
150 count
= max_nums_on_line
+ 1;
151 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
153 if (count
> max_nums_on_line
)
155 fprintf (lra_dump_file
, "\n ");
158 fprintf (lra_dump_file
, " %4u", i
);
161 fprintf (lra_dump_file
, "\n");
164 /* Hard registers currently not available for allocation. It can
165 changed after some hard registers become not eliminable. */
166 HARD_REG_SET lra_no_alloc_regs
;
168 static int get_new_reg_value (void);
169 static void expand_reg_info (void);
170 static void invalidate_insn_recog_data (int);
171 static int get_insn_freq (rtx_insn
*);
172 static void invalidate_insn_data_regno_info (lra_insn_recog_data_t
,
175 /* Expand all regno related info needed for LRA. */
177 expand_reg_data (int old
)
181 ira_expand_reg_equiv ();
182 for (int i
= (int) max_reg_num () - 1; i
>= old
; i
--)
183 lra_change_class (i
, ALL_REGS
, " Set", true);
186 /* Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL
187 or of VOIDmode, use MD_MODE for the new reg. Initialize its
188 register class to RCLASS. Print message about assigning class
189 RCLASS containing new register name TITLE unless it is NULL. Use
190 attributes of ORIGINAL if it is a register. The created register
191 will have unique held value. */
193 lra_create_new_reg_with_unique_value (machine_mode md_mode
, rtx original
,
194 enum reg_class rclass
, const char *title
)
199 if (original
== NULL_RTX
|| (mode
= GET_MODE (original
)) == VOIDmode
)
201 lra_assert (mode
!= VOIDmode
);
202 new_reg
= gen_reg_rtx (mode
);
203 if (original
== NULL_RTX
|| ! REG_P (original
))
205 if (lra_dump_file
!= NULL
)
206 fprintf (lra_dump_file
, " Creating newreg=%i", REGNO (new_reg
));
210 if (ORIGINAL_REGNO (original
) >= FIRST_PSEUDO_REGISTER
)
211 ORIGINAL_REGNO (new_reg
) = ORIGINAL_REGNO (original
);
212 REG_USERVAR_P (new_reg
) = REG_USERVAR_P (original
);
213 REG_POINTER (new_reg
) = REG_POINTER (original
);
214 REG_ATTRS (new_reg
) = REG_ATTRS (original
);
215 if (lra_dump_file
!= NULL
)
216 fprintf (lra_dump_file
, " Creating newreg=%i from oldreg=%i",
217 REGNO (new_reg
), REGNO (original
));
219 if (lra_dump_file
!= NULL
)
222 fprintf (lra_dump_file
, ", assigning class %s to%s%s r%d",
223 reg_class_names
[rclass
], *title
== '\0' ? "" : " ",
224 title
, REGNO (new_reg
));
225 fprintf (lra_dump_file
, "\n");
227 expand_reg_data (max_reg_num ());
228 setup_reg_classes (REGNO (new_reg
), rclass
, NO_REGS
, rclass
);
232 /* Analogous to the previous function but also inherits value of
235 lra_create_new_reg (machine_mode md_mode
, rtx original
,
236 enum reg_class rclass
, const char *title
)
241 = lra_create_new_reg_with_unique_value (md_mode
, original
, rclass
, title
);
242 if (original
!= NULL_RTX
&& REG_P (original
))
243 lra_assign_reg_val (REGNO (original
), REGNO (new_reg
));
247 /* Set up for REGNO unique hold value. */
249 lra_set_regno_unique_value (int regno
)
251 lra_reg_info
[regno
].val
= get_new_reg_value ();
254 /* Invalidate INSN related info used by LRA. The info should never be
257 lra_invalidate_insn_data (rtx_insn
*insn
)
259 lra_invalidate_insn_regno_info (insn
);
260 invalidate_insn_recog_data (INSN_UID (insn
));
263 /* Mark INSN deleted and invalidate the insn related info used by
266 lra_set_insn_deleted (rtx_insn
*insn
)
268 lra_invalidate_insn_data (insn
);
269 SET_INSN_DELETED (insn
);
272 /* Delete an unneeded INSN and any previous insns who sole purpose is
273 loading data that is dead in INSN. */
275 lra_delete_dead_insn (rtx_insn
*insn
)
277 rtx_insn
*prev
= prev_real_insn (insn
);
280 /* If the previous insn sets a register that dies in our insn,
282 if (prev
&& GET_CODE (PATTERN (prev
)) == SET
283 && (prev_dest
= SET_DEST (PATTERN (prev
)), REG_P (prev_dest
))
284 && reg_mentioned_p (prev_dest
, PATTERN (insn
))
285 && find_regno_note (insn
, REG_DEAD
, REGNO (prev_dest
))
286 && ! side_effects_p (SET_SRC (PATTERN (prev
))))
287 lra_delete_dead_insn (prev
);
289 lra_set_insn_deleted (insn
);
292 /* Emit insn x = y + z. Return NULL if we failed to do it.
293 Otherwise, return the insn. We don't use gen_add3_insn as it might
296 emit_add3_insn (rtx x
, rtx y
, rtx z
)
300 last
= get_last_insn ();
302 if (have_addptr3_insn (x
, y
, z
))
304 rtx_insn
*insn
= gen_addptr3_insn (x
, y
, z
);
306 /* If the target provides an "addptr" pattern it hopefully does
307 for a reason. So falling back to the normal add would be
309 lra_assert (insn
!= NULL_RTX
);
314 rtx_insn
*insn
= emit_insn (gen_rtx_SET (x
, gen_rtx_PLUS (GET_MODE (y
),
316 if (recog_memoized (insn
) < 0)
318 delete_insns_since (last
);
324 /* Emit insn x = x + y. Return the insn. We use gen_add2_insn as the
327 emit_add2_insn (rtx x
, rtx y
)
329 rtx_insn
*insn
= emit_add3_insn (x
, x
, y
);
330 if (insn
== NULL_RTX
)
332 insn
= gen_add2_insn (x
, y
);
333 if (insn
!= NULL_RTX
)
339 /* Target checks operands through operand predicates to recognize an
340 insn. We should have a special precaution to generate add insns
341 which are frequent results of elimination.
343 Emit insns for x = y + z. X can be used to store intermediate
344 values and should be not in Y and Z when we use X to store an
345 intermediate value. Y + Z should form [base] [+ index[ * scale]] [
346 + disp] where base and index are registers, disp and scale are
347 constants. Y should contain base if it is present, Z should
348 contain disp if any. index[*scale] can be part of Y or Z. */
350 lra_emit_add (rtx x
, rtx y
, rtx z
)
354 rtx a1
, a2
, base
, index
, disp
, scale
, index_scale
;
357 rtx_insn
*add3_insn
= emit_add3_insn (x
, y
, z
);
358 old
= max_reg_num ();
359 if (add3_insn
!= NULL
)
363 disp
= a2
= NULL_RTX
;
364 if (GET_CODE (y
) == PLUS
)
378 index_scale
= scale
= NULL_RTX
;
379 if (GET_CODE (a1
) == MULT
)
382 index
= XEXP (a1
, 0);
383 scale
= XEXP (a1
, 1);
386 else if (a2
!= NULL_RTX
&& GET_CODE (a2
) == MULT
)
389 index
= XEXP (a2
, 0);
390 scale
= XEXP (a2
, 1);
398 if (! (REG_P (base
) || GET_CODE (base
) == SUBREG
)
399 || (index
!= NULL_RTX
400 && ! (REG_P (index
) || GET_CODE (index
) == SUBREG
))
401 || (disp
!= NULL_RTX
&& ! CONSTANT_P (disp
))
402 || (scale
!= NULL_RTX
&& ! CONSTANT_P (scale
)))
404 /* Probably we have no 3 op add. Last chance is to use 2-op
405 add insn. To succeed, don't move Z to X as an address
406 segment always comes in Y. Otherwise, we might fail when
407 adding the address segment to register. */
408 lra_assert (x
!= y
&& x
!= z
);
409 emit_move_insn (x
, y
);
410 rtx_insn
*insn
= emit_add2_insn (x
, z
);
411 lra_assert (insn
!= NULL_RTX
);
415 if (index_scale
== NULL_RTX
)
417 if (disp
== NULL_RTX
)
419 /* Generate x = index_scale; x = x + base. */
420 lra_assert (index_scale
!= NULL_RTX
&& base
!= NULL_RTX
);
421 emit_move_insn (x
, index_scale
);
422 rtx_insn
*insn
= emit_add2_insn (x
, base
);
423 lra_assert (insn
!= NULL_RTX
);
425 else if (scale
== NULL_RTX
)
427 /* Try x = base + disp. */
428 lra_assert (base
!= NULL_RTX
);
429 last
= get_last_insn ();
430 rtx_insn
*move_insn
=
431 emit_move_insn (x
, gen_rtx_PLUS (GET_MODE (base
), base
, disp
));
432 if (recog_memoized (move_insn
) < 0)
434 delete_insns_since (last
);
435 /* Generate x = disp; x = x + base. */
436 emit_move_insn (x
, disp
);
437 rtx_insn
*add2_insn
= emit_add2_insn (x
, base
);
438 lra_assert (add2_insn
!= NULL_RTX
);
440 /* Generate x = x + index. */
441 if (index
!= NULL_RTX
)
443 rtx_insn
*insn
= emit_add2_insn (x
, index
);
444 lra_assert (insn
!= NULL_RTX
);
449 /* Try x = index_scale; x = x + disp; x = x + base. */
450 last
= get_last_insn ();
451 rtx_insn
*move_insn
= emit_move_insn (x
, index_scale
);
453 if (recog_memoized (move_insn
) >= 0)
455 rtx_insn
*insn
= emit_add2_insn (x
, disp
);
456 if (insn
!= NULL_RTX
)
458 insn
= emit_add2_insn (x
, base
);
459 if (insn
!= NULL_RTX
)
465 delete_insns_since (last
);
466 /* Generate x = disp; x = x + base; x = x + index_scale. */
467 emit_move_insn (x
, disp
);
468 rtx_insn
*insn
= emit_add2_insn (x
, base
);
469 lra_assert (insn
!= NULL_RTX
);
470 insn
= emit_add2_insn (x
, index_scale
);
471 lra_assert (insn
!= NULL_RTX
);
476 /* Functions emit_... can create pseudos -- so expand the pseudo
478 if (old
!= max_reg_num ())
479 expand_reg_data (old
);
482 /* The number of emitted reload insns so far. */
483 int lra_curr_reload_num
;
485 /* Emit x := y, processing special case when y = u + v or y = u + v *
486 scale + w through emit_add (Y can be an address which is base +
487 index reg * scale + displacement in general case). X may be used
488 as intermediate result therefore it should be not in Y. */
490 lra_emit_move (rtx x
, rtx y
)
494 if (GET_CODE (y
) != PLUS
)
496 if (rtx_equal_p (x
, y
))
498 old
= max_reg_num ();
499 emit_move_insn (x
, y
);
501 lra_reg_info
[ORIGINAL_REGNO (x
)].last_reload
= ++lra_curr_reload_num
;
502 /* Function emit_move can create pseudos -- so expand the pseudo
504 if (old
!= max_reg_num ())
505 expand_reg_data (old
);
508 lra_emit_add (x
, XEXP (y
, 0), XEXP (y
, 1));
511 /* Update insn operands which are duplication of operands whose
512 numbers are in array of NOPS (with end marker -1). The insn is
513 represented by its LRA internal representation ID. */
515 lra_update_dups (lra_insn_recog_data_t id
, signed char *nops
)
518 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
520 for (i
= 0; i
< static_id
->n_dups
; i
++)
521 for (j
= 0; (nop
= nops
[j
]) >= 0; j
++)
522 if (static_id
->dup_num
[i
] == nop
)
523 *id
->dup_loc
[i
] = *id
->operand_loc
[nop
];
528 /* This page contains code dealing with info about registers in the
531 /* Pools for insn reg info. */
532 object_allocator
<lra_insn_reg
> lra_insn_reg_pool ("insn regs");
534 /* Create LRA insn related info about a reference to REGNO in INSN with
535 TYPE (in/out/inout), biggest reference mode MODE, flag that it is
536 reference through subreg (SUBREG_P), flag that is early clobbered
537 in the insn (EARLY_CLOBBER), and reference to the next insn reg
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
, struct lra_insn_reg
*next
)
544 lra_insn_reg
*ir
= lra_insn_reg_pool
.allocate ();
546 ir
->biggest_mode
= mode
;
547 if (GET_MODE_SIZE (mode
) > GET_MODE_SIZE (lra_reg_info
[regno
].biggest_mode
)
548 && NONDEBUG_INSN_P (insn
))
549 lra_reg_info
[regno
].biggest_mode
= mode
;
550 ir
->subreg_p
= subreg_p
;
551 ir
->early_clobber
= early_clobber
;
557 /* Free insn reg info list IR. */
559 free_insn_regs (struct lra_insn_reg
*ir
)
561 struct lra_insn_reg
*next_ir
;
563 for (; ir
!= NULL
; ir
= next_ir
)
566 lra_insn_reg_pool
.remove (ir
);
570 /* Finish pool for insn reg info. */
572 finish_insn_regs (void)
574 lra_insn_reg_pool
.release ();
579 /* This page contains code dealing LRA insn info (or in other words
580 LRA internal insn representation). */
582 /* Map INSN_CODE -> the static insn data. This info is valid during
583 all translation unit. */
584 struct lra_static_insn_data
*insn_code_data
[NUM_INSN_CODES
];
586 /* Debug insns are represented as a special insn with one input
587 operand which is RTL expression in var_location. */
589 /* The following data are used as static insn operand data for all
590 debug insns. If structure lra_operand_data is changed, the
591 initializer should be changed too. */
592 static struct lra_operand_data debug_operand_data
=
594 NULL
, /* alternative */
595 VOIDmode
, /* We are not interesting in the operand mode. */
600 /* The following data are used as static insn data for all debug
601 insns. If structure lra_static_insn_data is changed, the
602 initializer should be changed too. */
603 static struct lra_static_insn_data debug_insn_static_data
=
606 0, /* Duplication operands #. */
607 -1, /* Commutative operand #. */
608 1, /* Operands #. There is only one operand which is debug RTL
610 0, /* Duplications #. */
611 0, /* Alternatives #. We are not interesting in alternatives
612 because we does not proceed debug_insns for reloads. */
613 NULL
, /* Hard registers referenced in machine description. */
614 NULL
/* Descriptions of operands in alternatives. */
617 /* Called once per compiler work to initialize some LRA data related
620 init_insn_code_data_once (void)
622 memset (insn_code_data
, 0, sizeof (insn_code_data
));
625 /* Called once per compiler work to finalize some LRA data related to
628 finish_insn_code_data_once (void)
630 for (unsigned int i
= 0; i
< NUM_INSN_CODES
; i
++)
632 if (insn_code_data
[i
] != NULL
)
633 free (insn_code_data
[i
]);
637 /* Return static insn data, allocate and setup if necessary. Although
638 dup_num is static data (it depends only on icode), to set it up we
639 need to extract insn first. So recog_data should be valid for
640 normal insn (ICODE >= 0) before the call. */
641 static struct lra_static_insn_data
*
642 get_static_insn_data (int icode
, int nop
, int ndup
, int nalt
)
644 struct lra_static_insn_data
*data
;
647 lra_assert (icode
< (int) NUM_INSN_CODES
);
648 if (icode
>= 0 && (data
= insn_code_data
[icode
]) != NULL
)
650 lra_assert (nop
>= 0 && ndup
>= 0 && nalt
>= 0);
651 n_bytes
= sizeof (struct lra_static_insn_data
)
652 + sizeof (struct lra_operand_data
) * nop
653 + sizeof (int) * ndup
;
654 data
= XNEWVAR (struct lra_static_insn_data
, n_bytes
);
655 data
->operand_alternative
= NULL
;
656 data
->n_operands
= nop
;
658 data
->n_alternatives
= nalt
;
659 data
->operand
= ((struct lra_operand_data
*)
660 ((char *) data
+ sizeof (struct lra_static_insn_data
)));
661 data
->dup_num
= ((int *) ((char *) data
->operand
662 + sizeof (struct lra_operand_data
) * nop
));
667 insn_code_data
[icode
] = data
;
668 for (i
= 0; i
< nop
; i
++)
670 data
->operand
[i
].constraint
671 = insn_data
[icode
].operand
[i
].constraint
;
672 data
->operand
[i
].mode
= insn_data
[icode
].operand
[i
].mode
;
673 data
->operand
[i
].strict_low
= insn_data
[icode
].operand
[i
].strict_low
;
674 data
->operand
[i
].is_operator
675 = insn_data
[icode
].operand
[i
].is_operator
;
676 data
->operand
[i
].type
677 = (data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
678 : data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
680 data
->operand
[i
].is_address
= false;
682 for (i
= 0; i
< ndup
; i
++)
683 data
->dup_num
[i
] = recog_data
.dup_num
[i
];
688 /* The current length of the following array. */
689 int lra_insn_recog_data_len
;
691 /* Map INSN_UID -> the insn recog data (NULL if unknown). */
692 lra_insn_recog_data_t
*lra_insn_recog_data
;
694 /* Initialize LRA data about insns. */
696 init_insn_recog_data (void)
698 lra_insn_recog_data_len
= 0;
699 lra_insn_recog_data
= NULL
;
702 /* Expand, if necessary, LRA data about insns. */
704 check_and_expand_insn_recog_data (int index
)
708 if (lra_insn_recog_data_len
> index
)
710 old
= lra_insn_recog_data_len
;
711 lra_insn_recog_data_len
= index
* 3 / 2 + 1;
712 lra_insn_recog_data
= XRESIZEVEC (lra_insn_recog_data_t
,
714 lra_insn_recog_data_len
);
715 for (i
= old
; i
< lra_insn_recog_data_len
; i
++)
716 lra_insn_recog_data
[i
] = NULL
;
719 /* Finish LRA DATA about insn. */
721 free_insn_recog_data (lra_insn_recog_data_t data
)
723 if (data
->operand_loc
!= NULL
)
724 free (data
->operand_loc
);
725 if (data
->dup_loc
!= NULL
)
726 free (data
->dup_loc
);
727 if (data
->arg_hard_regs
!= NULL
)
728 free (data
->arg_hard_regs
);
729 if (data
->icode
< 0 && NONDEBUG_INSN_P (data
->insn
))
731 if (data
->insn_static_data
->operand_alternative
!= NULL
)
732 free (const_cast <operand_alternative
*>
733 (data
->insn_static_data
->operand_alternative
));
734 free_insn_regs (data
->insn_static_data
->hard_regs
);
735 free (data
->insn_static_data
);
737 free_insn_regs (data
->regs
);
742 /* Pools for copies. */
743 static object_allocator
<lra_copy
> lra_copy_pool ("lra copies");
745 /* Finish LRA data about all insns. */
747 finish_insn_recog_data (void)
750 lra_insn_recog_data_t data
;
752 for (i
= 0; i
< lra_insn_recog_data_len
; i
++)
753 if ((data
= lra_insn_recog_data
[i
]) != NULL
)
754 free_insn_recog_data (data
);
756 lra_copy_pool
.release ();
757 lra_insn_reg_pool
.release ();
758 free (lra_insn_recog_data
);
761 /* Setup info about operands in alternatives of LRA DATA of insn. */
763 setup_operand_alternative (lra_insn_recog_data_t data
,
764 const operand_alternative
*op_alt
)
767 int icode
= data
->icode
;
768 struct lra_static_insn_data
*static_data
= data
->insn_static_data
;
770 static_data
->commutative
= -1;
771 nop
= static_data
->n_operands
;
772 nalt
= static_data
->n_alternatives
;
773 static_data
->operand_alternative
= op_alt
;
774 for (i
= 0; i
< nop
; i
++)
776 static_data
->operand
[i
].early_clobber
= false;
777 static_data
->operand
[i
].is_address
= false;
778 if (static_data
->operand
[i
].constraint
[0] == '%')
780 /* We currently only support one commutative pair of operands. */
781 if (static_data
->commutative
< 0)
782 static_data
->commutative
= i
;
784 lra_assert (icode
< 0); /* Asm */
785 /* The last operand should not be marked commutative. */
786 lra_assert (i
!= nop
- 1);
789 for (j
= 0; j
< nalt
; j
++)
790 for (i
= 0; i
< nop
; i
++, op_alt
++)
792 static_data
->operand
[i
].early_clobber
|= op_alt
->earlyclobber
;
793 static_data
->operand
[i
].is_address
|= op_alt
->is_address
;
797 /* Recursively process X and collect info about registers, which are
798 not the insn operands, in X with TYPE (in/out/inout) and flag that
799 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
800 to LIST. X is a part of insn given by DATA. Return the result
802 static struct lra_insn_reg
*
803 collect_non_operand_hard_regs (rtx
*x
, lra_insn_recog_data_t data
,
804 struct lra_insn_reg
*list
,
805 enum op_type type
, bool early_clobber
)
807 int i
, j
, regno
, last
;
810 struct lra_insn_reg
*curr
;
812 enum rtx_code code
= GET_CODE (op
);
813 const char *fmt
= GET_RTX_FORMAT (code
);
815 for (i
= 0; i
< data
->insn_static_data
->n_operands
; i
++)
816 if (x
== data
->operand_loc
[i
])
817 /* It is an operand loc. Stop here. */
819 for (i
= 0; i
< data
->insn_static_data
->n_dups
; i
++)
820 if (x
== data
->dup_loc
[i
])
821 /* It is a dup loc. Stop here. */
823 mode
= GET_MODE (op
);
827 op
= SUBREG_REG (op
);
828 code
= GET_CODE (op
);
829 if (GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (op
)))
831 mode
= GET_MODE (op
);
832 if (GET_MODE_SIZE (mode
) > REGMODE_NATURAL_SIZE (mode
))
838 if ((regno
= REGNO (op
)) >= FIRST_PSEUDO_REGISTER
)
840 /* Process all regs even unallocatable ones as we need info
841 about all regs for rematerialization pass. */
842 for (last
= regno
+ hard_regno_nregs
[regno
][mode
];
846 for (curr
= list
; curr
!= NULL
; curr
= curr
->next
)
847 if (curr
->regno
== regno
&& curr
->subreg_p
== subreg_p
848 && curr
->biggest_mode
== mode
)
850 if (curr
->type
!= type
)
851 curr
->type
= OP_INOUT
;
852 if (curr
->early_clobber
!= early_clobber
)
853 curr
->early_clobber
= true;
858 /* This is a new hard regno or the info can not be
859 integrated into the found structure. */
863 /* This clobber is to inform popping floating
865 && ! (FIRST_STACK_REG
<= regno
866 && regno
<= LAST_STACK_REG
));
868 list
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
869 early_clobber
, list
);
877 list
= collect_non_operand_hard_regs (&SET_DEST (op
), data
,
878 list
, OP_OUT
, false);
879 list
= collect_non_operand_hard_regs (&SET_SRC (op
), data
,
883 /* We treat clobber of non-operand hard registers as early
884 clobber (the behavior is expected from asm). */
885 list
= collect_non_operand_hard_regs (&XEXP (op
, 0), data
,
888 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
889 list
= collect_non_operand_hard_regs (&XEXP (op
, 0), data
,
890 list
, OP_INOUT
, false);
892 case PRE_MODIFY
: case POST_MODIFY
:
893 list
= collect_non_operand_hard_regs (&XEXP (op
, 0), data
,
894 list
, OP_INOUT
, false);
895 list
= collect_non_operand_hard_regs (&XEXP (op
, 1), data
,
899 fmt
= GET_RTX_FORMAT (code
);
900 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
903 list
= collect_non_operand_hard_regs (&XEXP (op
, i
), data
,
905 else if (fmt
[i
] == 'E')
906 for (j
= XVECLEN (op
, i
) - 1; j
>= 0; j
--)
907 list
= collect_non_operand_hard_regs (&XVECEXP (op
, i
, j
), data
,
914 /* Set up and return info about INSN. Set up the info if it is not set up
916 lra_insn_recog_data_t
917 lra_set_insn_recog_data (rtx_insn
*insn
)
919 lra_insn_recog_data_t data
;
922 unsigned int uid
= INSN_UID (insn
);
923 struct lra_static_insn_data
*insn_static_data
;
925 check_and_expand_insn_recog_data (uid
);
926 if (DEBUG_INSN_P (insn
))
930 icode
= INSN_CODE (insn
);
932 /* It might be a new simple insn which is not recognized yet. */
933 INSN_CODE (insn
) = icode
= recog_memoized (insn
);
935 data
= XNEW (struct lra_insn_recog_data
);
936 lra_insn_recog_data
[uid
] = data
;
938 data
->used_insn_alternative
= -1;
941 if (DEBUG_INSN_P (insn
))
943 data
->insn_static_data
= &debug_insn_static_data
;
944 data
->dup_loc
= NULL
;
945 data
->arg_hard_regs
= NULL
;
946 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
947 data
->operand_loc
= XNEWVEC (rtx
*, 1);
948 data
->operand_loc
[0] = &INSN_VAR_LOCATION_LOC (insn
);
954 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
955 const char *constraints
[MAX_RECOG_OPERANDS
];
957 nop
= asm_noperands (PATTERN (insn
));
958 data
->operand_loc
= data
->dup_loc
= NULL
;
962 /* It is a special insn like USE or CLOBBER. We should
963 recognize any regular insn otherwise LRA can do nothing
965 gcc_assert (GET_CODE (PATTERN (insn
)) == USE
966 || GET_CODE (PATTERN (insn
)) == CLOBBER
967 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
968 data
->insn_static_data
= insn_static_data
969 = get_static_insn_data (-1, 0, 0, nalt
);
973 /* expand_asm_operands makes sure there aren't too many
975 lra_assert (nop
<= MAX_RECOG_OPERANDS
);
977 data
->operand_loc
= XNEWVEC (rtx
*, nop
);
978 /* Now get the operand values and constraints out of the
980 decode_asm_operands (PATTERN (insn
), NULL
,
982 constraints
, operand_mode
, NULL
);
985 const char *p
= recog_data
.constraints
[0];
987 for (p
= constraints
[0]; *p
; p
++)
990 data
->insn_static_data
= insn_static_data
991 = get_static_insn_data (-1, nop
, 0, nalt
);
992 for (i
= 0; i
< nop
; i
++)
994 insn_static_data
->operand
[i
].mode
= operand_mode
[i
];
995 insn_static_data
->operand
[i
].constraint
= constraints
[i
];
996 insn_static_data
->operand
[i
].strict_low
= false;
997 insn_static_data
->operand
[i
].is_operator
= false;
998 insn_static_data
->operand
[i
].is_address
= false;
1001 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1002 insn_static_data
->operand
[i
].type
1003 = (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1004 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1006 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
1009 operand_alternative
*op_alt
= XCNEWVEC (operand_alternative
,
1011 preprocess_constraints (nop
, nalt
, constraints
, op_alt
);
1012 setup_operand_alternative (data
, op_alt
);
1017 insn_extract (insn
);
1018 data
->insn_static_data
= insn_static_data
1019 = get_static_insn_data (icode
, insn_data
[icode
].n_operands
,
1020 insn_data
[icode
].n_dups
,
1021 insn_data
[icode
].n_alternatives
);
1022 n
= insn_static_data
->n_operands
;
1027 locs
= XNEWVEC (rtx
*, n
);
1028 memcpy (locs
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1030 data
->operand_loc
= locs
;
1031 n
= insn_static_data
->n_dups
;
1036 locs
= XNEWVEC (rtx
*, n
);
1037 memcpy (locs
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1039 data
->dup_loc
= locs
;
1040 data
->preferred_alternatives
= get_preferred_alternatives (insn
);
1041 const operand_alternative
*op_alt
= preprocess_insn_constraints (icode
);
1042 if (!insn_static_data
->operand_alternative
)
1043 setup_operand_alternative (data
, op_alt
);
1044 else if (op_alt
!= insn_static_data
->operand_alternative
)
1045 insn_static_data
->operand_alternative
= op_alt
;
1047 if (GET_CODE (PATTERN (insn
)) == CLOBBER
|| GET_CODE (PATTERN (insn
)) == USE
)
1048 insn_static_data
->hard_regs
= NULL
;
1050 insn_static_data
->hard_regs
1051 = collect_non_operand_hard_regs (&PATTERN (insn
), data
,
1052 NULL
, OP_IN
, false);
1053 data
->arg_hard_regs
= NULL
;
1058 int n_hard_regs
, regno
, arg_hard_regs
[FIRST_PSEUDO_REGISTER
];
1061 /* Finding implicit hard register usage. We believe it will be
1062 not changed whatever transformations are used. Call insns
1063 are such example. */
1064 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1066 link
= XEXP (link
, 1))
1067 if (((use_p
= GET_CODE (XEXP (link
, 0)) == USE
)
1068 || GET_CODE (XEXP (link
, 0)) == CLOBBER
)
1069 && REG_P (XEXP (XEXP (link
, 0), 0)))
1071 regno
= REGNO (XEXP (XEXP (link
, 0), 0));
1072 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
1073 /* It is an argument register. */
1074 for (i
= REG_NREGS (XEXP (XEXP (link
, 0), 0)) - 1; i
>= 0; i
--)
1075 arg_hard_regs
[n_hard_regs
++]
1076 = regno
+ i
+ (use_p
? 0 : FIRST_PSEUDO_REGISTER
);
1078 if (n_hard_regs
!= 0)
1080 arg_hard_regs
[n_hard_regs
++] = -1;
1081 data
->arg_hard_regs
= XNEWVEC (int, n_hard_regs
);
1082 memcpy (data
->arg_hard_regs
, arg_hard_regs
,
1083 sizeof (int) * n_hard_regs
);
1086 /* Some output operand can be recognized only from the context not
1087 from the constraints which are empty in this case. Call insn may
1088 contain a hard register in set destination with empty constraint
1089 and extract_insn treats them as an input. */
1090 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1094 struct lra_operand_data
*operand
= &insn_static_data
->operand
[i
];
1096 /* ??? Should we treat 'X' the same way. It looks to me that
1097 'X' means anything and empty constraint means we do not
1099 if (operand
->type
!= OP_IN
|| *operand
->constraint
!= '\0'
1100 || operand
->is_operator
)
1102 pat
= PATTERN (insn
);
1103 if (GET_CODE (pat
) == SET
)
1105 if (data
->operand_loc
[i
] != &SET_DEST (pat
))
1108 else if (GET_CODE (pat
) == PARALLEL
)
1110 for (j
= XVECLEN (pat
, 0) - 1; j
>= 0; j
--)
1112 set
= XVECEXP (PATTERN (insn
), 0, j
);
1113 if (GET_CODE (set
) == SET
1114 && &SET_DEST (set
) == data
->operand_loc
[i
])
1122 operand
->type
= OP_OUT
;
1127 /* Return info about insn give by UID. The info should be already set
1129 static lra_insn_recog_data_t
1130 get_insn_recog_data_by_uid (int uid
)
1132 lra_insn_recog_data_t data
;
1134 data
= lra_insn_recog_data
[uid
];
1135 lra_assert (data
!= NULL
);
1139 /* Invalidate all info about insn given by its UID. */
1141 invalidate_insn_recog_data (int uid
)
1143 lra_insn_recog_data_t data
;
1145 data
= lra_insn_recog_data
[uid
];
1146 lra_assert (data
!= NULL
);
1147 free_insn_recog_data (data
);
1148 lra_insn_recog_data
[uid
] = NULL
;
1151 /* Update all the insn info about INSN. It is usually called when
1152 something in the insn was changed. Return the updated info. */
1153 lra_insn_recog_data_t
1154 lra_update_insn_recog_data (rtx_insn
*insn
)
1156 lra_insn_recog_data_t data
;
1158 unsigned int uid
= INSN_UID (insn
);
1159 struct lra_static_insn_data
*insn_static_data
;
1160 HOST_WIDE_INT sp_offset
= 0;
1162 check_and_expand_insn_recog_data (uid
);
1163 if ((data
= lra_insn_recog_data
[uid
]) != NULL
1164 && data
->icode
!= INSN_CODE (insn
))
1166 sp_offset
= data
->sp_offset
;
1167 invalidate_insn_data_regno_info (data
, insn
, get_insn_freq (insn
));
1168 invalidate_insn_recog_data (uid
);
1173 data
= lra_get_insn_recog_data (insn
);
1174 /* Initiate or restore SP offset. */
1175 data
->sp_offset
= sp_offset
;
1178 insn_static_data
= data
->insn_static_data
;
1179 data
->used_insn_alternative
= -1;
1180 if (DEBUG_INSN_P (insn
))
1182 if (data
->icode
< 0)
1185 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
1186 const char *constraints
[MAX_RECOG_OPERANDS
];
1188 nop
= asm_noperands (PATTERN (insn
));
1191 lra_assert (nop
== data
->insn_static_data
->n_operands
);
1192 /* Now get the operand values and constraints out of the
1194 decode_asm_operands (PATTERN (insn
), NULL
,
1196 constraints
, operand_mode
, NULL
);
1199 for (int i
= 0; i
< nop
; i
++)
1201 (insn_static_data
->operand
[i
].mode
== operand_mode
[i
]
1202 && insn_static_data
->operand
[i
].constraint
== constraints
[i
]
1203 && ! insn_static_data
->operand
[i
].is_operator
);
1207 for (int i
= 0; i
< insn_static_data
->n_operands
; i
++)
1209 (insn_static_data
->operand
[i
].type
1210 == (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1211 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1216 insn_extract (insn
);
1217 n
= insn_static_data
->n_operands
;
1219 memcpy (data
->operand_loc
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1220 n
= insn_static_data
->n_dups
;
1222 memcpy (data
->dup_loc
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1223 lra_assert (check_bool_attrs (insn
));
1228 /* Set up that INSN is using alternative ALT now. */
1230 lra_set_used_insn_alternative (rtx_insn
*insn
, int alt
)
1232 lra_insn_recog_data_t data
;
1234 data
= lra_get_insn_recog_data (insn
);
1235 data
->used_insn_alternative
= alt
;
1238 /* Set up that insn with UID is using alternative ALT now. The insn
1239 info should be already set up. */
1241 lra_set_used_insn_alternative_by_uid (int uid
, int alt
)
1243 lra_insn_recog_data_t data
;
1245 check_and_expand_insn_recog_data (uid
);
1246 data
= lra_insn_recog_data
[uid
];
1247 lra_assert (data
!= NULL
);
1248 data
->used_insn_alternative
= alt
;
1253 /* This page contains code dealing with common register info and
1256 /* The size of the following array. */
1257 static int reg_info_size
;
1258 /* Common info about each register. */
1259 struct lra_reg
*lra_reg_info
;
1261 /* Last register value. */
1262 static int last_reg_value
;
1264 /* Return new register value. */
1266 get_new_reg_value (void)
1268 return ++last_reg_value
;
1271 /* Vec referring to pseudo copies. */
1272 static vec
<lra_copy_t
> copy_vec
;
1274 /* Initialize I-th element of lra_reg_info. */
1276 initialize_lra_reg_info_element (int i
)
1278 bitmap_initialize (&lra_reg_info
[i
].insn_bitmap
, ®_obstack
);
1280 lra_reg_info
[i
].no_stack_p
= false;
1282 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
1283 CLEAR_HARD_REG_SET (lra_reg_info
[i
].actual_call_used_reg_set
);
1284 lra_reg_info
[i
].preferred_hard_regno1
= -1;
1285 lra_reg_info
[i
].preferred_hard_regno2
= -1;
1286 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
1287 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
1288 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
1289 lra_reg_info
[i
].live_ranges
= NULL
;
1290 lra_reg_info
[i
].nrefs
= lra_reg_info
[i
].freq
= 0;
1291 lra_reg_info
[i
].last_reload
= 0;
1292 lra_reg_info
[i
].restore_regno
= -1;
1293 lra_reg_info
[i
].val
= get_new_reg_value ();
1294 lra_reg_info
[i
].offset
= 0;
1295 lra_reg_info
[i
].copies
= NULL
;
1298 /* Initialize common reg info and copies. */
1300 init_reg_info (void)
1305 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1306 lra_reg_info
= XNEWVEC (struct lra_reg
, reg_info_size
);
1307 for (i
= 0; i
< reg_info_size
; i
++)
1308 initialize_lra_reg_info_element (i
);
1309 copy_vec
.create (100);
1313 /* Finish common reg info and copies. */
1315 finish_reg_info (void)
1319 for (i
= 0; i
< reg_info_size
; i
++)
1320 bitmap_clear (&lra_reg_info
[i
].insn_bitmap
);
1321 free (lra_reg_info
);
1325 /* Expand common reg info if it is necessary. */
1327 expand_reg_info (void)
1329 int i
, old
= reg_info_size
;
1331 if (reg_info_size
> max_reg_num ())
1333 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1334 lra_reg_info
= XRESIZEVEC (struct lra_reg
, lra_reg_info
, reg_info_size
);
1335 for (i
= old
; i
< reg_info_size
; i
++)
1336 initialize_lra_reg_info_element (i
);
1339 /* Free all copies. */
1341 lra_free_copies (void)
1345 while (copy_vec
.length () != 0)
1347 cp
= copy_vec
.pop ();
1348 lra_reg_info
[cp
->regno1
].copies
= lra_reg_info
[cp
->regno2
].copies
= NULL
;
1349 lra_copy_pool
.remove (cp
);
1353 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1354 frequency is FREQ. */
1356 lra_create_copy (int regno1
, int regno2
, int freq
)
1361 lra_assert (regno1
!= regno2
);
1362 regno1_dest_p
= true;
1363 if (regno1
> regno2
)
1365 std::swap (regno1
, regno2
);
1366 regno1_dest_p
= false;
1368 cp
= lra_copy_pool
.allocate ();
1369 copy_vec
.safe_push (cp
);
1370 cp
->regno1_dest_p
= regno1_dest_p
;
1372 cp
->regno1
= regno1
;
1373 cp
->regno2
= regno2
;
1374 cp
->regno1_next
= lra_reg_info
[regno1
].copies
;
1375 lra_reg_info
[regno1
].copies
= cp
;
1376 cp
->regno2_next
= lra_reg_info
[regno2
].copies
;
1377 lra_reg_info
[regno2
].copies
= cp
;
1378 if (lra_dump_file
!= NULL
)
1379 fprintf (lra_dump_file
, " Creating copy r%d%sr%d@%d\n",
1380 regno1
, regno1_dest_p
? "<-" : "->", regno2
, freq
);
1383 /* Return N-th (0, 1, ...) copy. If there is no copy, return
1386 lra_get_copy (int n
)
1388 if (n
>= (int) copy_vec
.length ())
1395 /* This page contains code dealing with info about registers in
1398 /* Process X of insn UID recursively and add info (operand type is
1399 given by TYPE, flag of that it is early clobber is EARLY_CLOBBER)
1400 about registers in X to the insn DATA. */
1402 add_regs_to_insn_regno_info (lra_insn_recog_data_t data
, rtx x
, int uid
,
1403 enum op_type type
, bool early_clobber
)
1410 struct lra_insn_reg
*curr
;
1412 code
= GET_CODE (x
);
1413 mode
= GET_MODE (x
);
1415 if (GET_CODE (x
) == SUBREG
)
1418 code
= GET_CODE (x
);
1419 if (GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (x
)))
1421 mode
= GET_MODE (x
);
1422 if (GET_MODE_SIZE (mode
) > REGMODE_NATURAL_SIZE (mode
))
1429 /* Process all regs even unallocatable ones as we need info about
1430 all regs for rematerialization pass. */
1432 if (bitmap_set_bit (&lra_reg_info
[regno
].insn_bitmap
, uid
))
1434 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
1435 early_clobber
, data
->regs
);
1440 for (curr
= data
->regs
; curr
!= NULL
; curr
= curr
->next
)
1441 if (curr
->regno
== regno
)
1443 if (curr
->subreg_p
!= subreg_p
|| curr
->biggest_mode
!= mode
)
1444 /* The info can not be integrated into the found
1446 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
,
1447 subreg_p
, early_clobber
,
1451 if (curr
->type
!= type
)
1452 curr
->type
= OP_INOUT
;
1453 if (curr
->early_clobber
!= early_clobber
)
1454 curr
->early_clobber
= true;
1465 add_regs_to_insn_regno_info (data
, SET_DEST (x
), uid
, OP_OUT
, false);
1466 add_regs_to_insn_regno_info (data
, SET_SRC (x
), uid
, OP_IN
, false);
1469 /* We treat clobber of non-operand hard registers as early
1470 clobber (the behavior is expected from asm). */
1471 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), uid
, OP_OUT
, true);
1473 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
1474 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), uid
, OP_INOUT
, false);
1476 case PRE_MODIFY
: case POST_MODIFY
:
1477 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), uid
, OP_INOUT
, false);
1478 add_regs_to_insn_regno_info (data
, XEXP (x
, 1), uid
, OP_IN
, false);
1481 if ((code
!= PARALLEL
&& code
!= EXPR_LIST
) || type
!= OP_OUT
)
1482 /* Some targets place small structures in registers for return
1483 values of functions, and those registers are wrapped in
1484 PARALLEL that we may see as the destination of a SET. Here
1487 (call_insn 13 12 14 2 (set (parallel:BLK [
1488 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1490 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1491 (const_int 8 [0x8]))
1493 (call (mem:QI (symbol_ref:DI (... */
1495 fmt
= GET_RTX_FORMAT (code
);
1496 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1499 add_regs_to_insn_regno_info (data
, XEXP (x
, i
), uid
, type
, false);
1500 else if (fmt
[i
] == 'E')
1502 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1503 add_regs_to_insn_regno_info (data
, XVECEXP (x
, i
, j
), uid
,
1510 /* Return execution frequency of INSN. */
1512 get_insn_freq (rtx_insn
*insn
)
1514 basic_block bb
= BLOCK_FOR_INSN (insn
);
1516 gcc_checking_assert (bb
!= NULL
);
1517 return REG_FREQ_FROM_BB (bb
);
1520 /* Invalidate all reg info of INSN with DATA and execution frequency
1521 FREQ. Update common info about the invalidated registers. */
1523 invalidate_insn_data_regno_info (lra_insn_recog_data_t data
, rtx_insn
*insn
,
1529 struct lra_insn_reg
*ir
, *next_ir
;
1531 uid
= INSN_UID (insn
);
1532 debug_p
= DEBUG_INSN_P (insn
);
1533 for (ir
= data
->regs
; ir
!= NULL
; ir
= next_ir
)
1537 lra_insn_reg_pool
.remove (ir
);
1538 bitmap_clear_bit (&lra_reg_info
[i
].insn_bitmap
, uid
);
1539 if (i
>= FIRST_PSEUDO_REGISTER
&& ! debug_p
)
1541 lra_reg_info
[i
].nrefs
--;
1542 lra_reg_info
[i
].freq
-= freq
;
1543 lra_assert (lra_reg_info
[i
].nrefs
>= 0 && lra_reg_info
[i
].freq
>= 0);
1549 /* Invalidate all reg info of INSN. Update common info about the
1550 invalidated registers. */
1552 lra_invalidate_insn_regno_info (rtx_insn
*insn
)
1554 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn
), insn
,
1555 get_insn_freq (insn
));
1558 /* Update common reg info from reg info of insn given by its DATA and
1559 execution frequency FREQ. */
1561 setup_insn_reg_info (lra_insn_recog_data_t data
, int freq
)
1564 struct lra_insn_reg
*ir
;
1566 for (ir
= data
->regs
; ir
!= NULL
; ir
= ir
->next
)
1567 if ((i
= ir
->regno
) >= FIRST_PSEUDO_REGISTER
)
1569 lra_reg_info
[i
].nrefs
++;
1570 lra_reg_info
[i
].freq
+= freq
;
1574 /* Set up insn reg info of INSN. Update common reg info from reg info
1577 lra_update_insn_regno_info (rtx_insn
*insn
)
1580 lra_insn_recog_data_t data
;
1581 struct lra_static_insn_data
*static_data
;
1585 if (! INSN_P (insn
))
1587 data
= lra_get_insn_recog_data (insn
);
1588 static_data
= data
->insn_static_data
;
1589 freq
= get_insn_freq (insn
);
1590 invalidate_insn_data_regno_info (data
, insn
, freq
);
1591 uid
= INSN_UID (insn
);
1592 for (i
= static_data
->n_operands
- 1; i
>= 0; i
--)
1593 add_regs_to_insn_regno_info (data
, *data
->operand_loc
[i
], uid
,
1594 static_data
->operand
[i
].type
,
1595 static_data
->operand
[i
].early_clobber
);
1596 if ((code
= GET_CODE (PATTERN (insn
))) == CLOBBER
|| code
== USE
)
1597 add_regs_to_insn_regno_info (data
, XEXP (PATTERN (insn
), 0), uid
,
1598 code
== USE
? OP_IN
: OP_OUT
, false);
1600 /* On some targets call insns can refer to pseudos in memory in
1601 CALL_INSN_FUNCTION_USAGE list. Process them in order to
1602 consider their occurrences in calls for different
1603 transformations (e.g. inheritance) with given pseudos. */
1604 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1606 link
= XEXP (link
, 1))
1607 if (((code
= GET_CODE (XEXP (link
, 0))) == USE
|| code
== CLOBBER
)
1608 && MEM_P (XEXP (XEXP (link
, 0), 0)))
1609 add_regs_to_insn_regno_info (data
, XEXP (XEXP (link
, 0), 0), uid
,
1610 code
== USE
? OP_IN
: OP_OUT
, false);
1611 if (NONDEBUG_INSN_P (insn
))
1612 setup_insn_reg_info (data
, freq
);
1615 /* Return reg info of insn given by it UID. */
1616 struct lra_insn_reg
*
1617 lra_get_insn_regs (int uid
)
1619 lra_insn_recog_data_t data
;
1621 data
= get_insn_recog_data_by_uid (uid
);
1627 /* This page contains code dealing with stack of the insns which
1628 should be processed by the next constraint pass. */
1630 /* Bitmap used to put an insn on the stack only in one exemplar. */
1631 static sbitmap lra_constraint_insn_stack_bitmap
;
1633 /* The stack itself. */
1634 vec
<rtx_insn
*> lra_constraint_insn_stack
;
1636 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1637 info for INSN, otherwise only update it if INSN is not already on the
1640 lra_push_insn_1 (rtx_insn
*insn
, bool always_update
)
1642 unsigned int uid
= INSN_UID (insn
);
1644 lra_update_insn_regno_info (insn
);
1645 if (uid
>= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap
))
1646 lra_constraint_insn_stack_bitmap
=
1647 sbitmap_resize (lra_constraint_insn_stack_bitmap
, 3 * uid
/ 2, 0);
1648 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap
, uid
))
1650 bitmap_set_bit (lra_constraint_insn_stack_bitmap
, uid
);
1651 if (! always_update
)
1652 lra_update_insn_regno_info (insn
);
1653 lra_constraint_insn_stack
.safe_push (insn
);
1656 /* Put INSN on the stack. */
1658 lra_push_insn (rtx_insn
*insn
)
1660 lra_push_insn_1 (insn
, false);
1663 /* Put INSN on the stack and update its reg info. */
1665 lra_push_insn_and_update_insn_regno_info (rtx_insn
*insn
)
1667 lra_push_insn_1 (insn
, true);
1670 /* Put insn with UID on the stack. */
1672 lra_push_insn_by_uid (unsigned int uid
)
1674 lra_push_insn (lra_insn_recog_data
[uid
]->insn
);
1677 /* Take the last-inserted insns off the stack and return it. */
1681 rtx_insn
*insn
= lra_constraint_insn_stack
.pop ();
1682 bitmap_clear_bit (lra_constraint_insn_stack_bitmap
, INSN_UID (insn
));
1686 /* Return the current size of the insn stack. */
1688 lra_insn_stack_length (void)
1690 return lra_constraint_insn_stack
.length ();
1693 /* Push insns FROM to TO (excluding it) going in reverse order. */
1695 push_insns (rtx_insn
*from
, rtx_insn
*to
)
1699 if (from
== NULL_RTX
)
1701 for (insn
= from
; insn
!= to
; insn
= PREV_INSN (insn
))
1703 lra_push_insn (insn
);
1706 /* Set up sp offset for insn in range [FROM, LAST]. The offset is
1707 taken from the next BB insn after LAST or zero if there in such
1710 setup_sp_offset (rtx_insn
*from
, rtx_insn
*last
)
1712 rtx_insn
*before
= next_nonnote_insn_bb (last
);
1713 HOST_WIDE_INT offset
= (before
== NULL_RTX
|| ! INSN_P (before
)
1714 ? 0 : lra_get_insn_recog_data (before
)->sp_offset
);
1716 for (rtx_insn
*insn
= from
; insn
!= NEXT_INSN (last
); insn
= NEXT_INSN (insn
))
1717 lra_get_insn_recog_data (insn
)->sp_offset
= offset
;
1720 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1721 insns onto the stack. Print about emitting the insns with
1724 lra_process_new_insns (rtx_insn
*insn
, rtx_insn
*before
, rtx_insn
*after
,
1729 if (before
== NULL_RTX
&& after
== NULL_RTX
)
1731 if (lra_dump_file
!= NULL
)
1733 dump_insn_slim (lra_dump_file
, insn
);
1734 if (before
!= NULL_RTX
)
1736 fprintf (lra_dump_file
," %s before:\n", title
);
1737 dump_rtl_slim (lra_dump_file
, before
, NULL
, -1, 0);
1739 if (after
!= NULL_RTX
)
1741 fprintf (lra_dump_file
, " %s after:\n", title
);
1742 dump_rtl_slim (lra_dump_file
, after
, NULL
, -1, 0);
1744 fprintf (lra_dump_file
, "\n");
1746 if (before
!= NULL_RTX
)
1748 emit_insn_before (before
, insn
);
1749 push_insns (PREV_INSN (insn
), PREV_INSN (before
));
1750 setup_sp_offset (before
, PREV_INSN (insn
));
1752 if (after
!= NULL_RTX
)
1754 for (last
= after
; NEXT_INSN (last
) != NULL_RTX
; last
= NEXT_INSN (last
))
1756 emit_insn_after (after
, insn
);
1757 push_insns (last
, insn
);
1758 setup_sp_offset (after
, last
);
1764 /* Replace all references to register OLD_REGNO in *LOC with pseudo
1765 register NEW_REG. Try to simplify subreg of constant if SUBREG_P.
1766 Return true if any change was made. */
1768 lra_substitute_pseudo (rtx
*loc
, int old_regno
, rtx new_reg
, bool subreg_p
)
1771 bool result
= false;
1779 code
= GET_CODE (x
);
1780 if (code
== SUBREG
&& subreg_p
)
1782 rtx subst
, inner
= SUBREG_REG (x
);
1783 /* Transform subreg of constant while we still have inner mode
1784 of the subreg. The subreg internal should not be an insn
1786 if (REG_P (inner
) && (int) REGNO (inner
) == old_regno
1787 && CONSTANT_P (new_reg
)
1788 && (subst
= simplify_subreg (GET_MODE (x
), new_reg
, GET_MODE (inner
),
1789 SUBREG_BYTE (x
))) != NULL_RTX
)
1796 else if (code
== REG
&& (int) REGNO (x
) == old_regno
)
1798 machine_mode mode
= GET_MODE (x
);
1799 machine_mode inner_mode
= GET_MODE (new_reg
);
1801 if (mode
!= inner_mode
1802 && ! (CONST_INT_P (new_reg
) && SCALAR_INT_MODE_P (mode
)))
1804 if (GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (inner_mode
)
1805 || ! SCALAR_INT_MODE_P (inner_mode
))
1806 new_reg
= gen_rtx_SUBREG (mode
, new_reg
, 0);
1808 new_reg
= gen_lowpart_SUBREG (mode
, new_reg
);
1814 /* Scan all the operand sub-expressions. */
1815 fmt
= GET_RTX_FORMAT (code
);
1816 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1820 if (lra_substitute_pseudo (&XEXP (x
, i
), old_regno
,
1824 else if (fmt
[i
] == 'E')
1826 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1827 if (lra_substitute_pseudo (&XVECEXP (x
, i
, j
), old_regno
,
1835 /* Call lra_substitute_pseudo within an insn. Try to simplify subreg
1836 of constant if SUBREG_P. This won't update the insn ptr, just the
1837 contents of the insn. */
1839 lra_substitute_pseudo_within_insn (rtx_insn
*insn
, int old_regno
,
1840 rtx new_reg
, bool subreg_p
)
1843 return lra_substitute_pseudo (&loc
, old_regno
, new_reg
, subreg_p
);
1848 /* This page contains code dealing with scratches (changing them onto
1849 pseudos and restoring them from the pseudos).
1851 We change scratches into pseudos at the beginning of LRA to
1852 simplify dealing with them (conflicts, hard register assignments).
1854 If the pseudo denoting scratch was spilled it means that we do need
1855 a hard register for it. Such pseudos are transformed back to
1856 scratches at the end of LRA. */
1858 /* Description of location of a former scratch operand. */
1861 rtx_insn
*insn
; /* Insn where the scratch was. */
1862 int nop
; /* Number of the operand which was a scratch. */
1865 typedef struct sloc
*sloc_t
;
1867 /* Locations of the former scratches. */
1868 static vec
<sloc_t
> scratches
;
1870 /* Bitmap of scratch regnos. */
1871 static bitmap_head scratch_bitmap
;
1873 /* Bitmap of scratch operands. */
1874 static bitmap_head scratch_operand_bitmap
;
1876 /* Return true if pseudo REGNO is made of SCRATCH. */
1878 lra_former_scratch_p (int regno
)
1880 return bitmap_bit_p (&scratch_bitmap
, regno
);
1883 /* Return true if the operand NOP of INSN is a former scratch. */
1885 lra_former_scratch_operand_p (rtx_insn
*insn
, int nop
)
1887 return bitmap_bit_p (&scratch_operand_bitmap
,
1888 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
) != 0;
1891 /* Register operand NOP in INSN as a former scratch. It will be
1892 changed to scratch back, if it is necessary, at the LRA end. */
1894 lra_register_new_scratch_op (rtx_insn
*insn
, int nop
)
1896 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
1897 rtx op
= *id
->operand_loc
[nop
];
1898 sloc_t loc
= XNEW (struct sloc
);
1899 lra_assert (REG_P (op
));
1902 scratches
.safe_push (loc
);
1903 bitmap_set_bit (&scratch_bitmap
, REGNO (op
));
1904 bitmap_set_bit (&scratch_operand_bitmap
,
1905 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
);
1906 add_reg_note (insn
, REG_UNUSED
, op
);
1909 /* Change scratches onto pseudos and save their location. */
1911 remove_scratches (void)
1914 bool insn_changed_p
;
1918 lra_insn_recog_data_t id
;
1919 struct lra_static_insn_data
*static_id
;
1921 scratches
.create (get_max_uid ());
1922 bitmap_initialize (&scratch_bitmap
, ®_obstack
);
1923 bitmap_initialize (&scratch_operand_bitmap
, ®_obstack
);
1924 FOR_EACH_BB_FN (bb
, cfun
)
1925 FOR_BB_INSNS (bb
, insn
)
1928 id
= lra_get_insn_recog_data (insn
);
1929 static_id
= id
->insn_static_data
;
1930 insn_changed_p
= false;
1931 for (i
= 0; i
< static_id
->n_operands
; i
++)
1932 if (GET_CODE (*id
->operand_loc
[i
]) == SCRATCH
1933 && GET_MODE (*id
->operand_loc
[i
]) != VOIDmode
)
1935 insn_changed_p
= true;
1936 *id
->operand_loc
[i
] = reg
1937 = lra_create_new_reg (static_id
->operand
[i
].mode
,
1938 *id
->operand_loc
[i
], ALL_REGS
, NULL
);
1939 lra_register_new_scratch_op (insn
, i
);
1940 if (lra_dump_file
!= NULL
)
1941 fprintf (lra_dump_file
,
1942 "Removing SCRATCH in insn #%u (nop %d)\n",
1943 INSN_UID (insn
), i
);
1946 /* Because we might use DF right after caller-saves sub-pass
1947 we need to keep DF info up to date. */
1948 df_insn_rescan (insn
);
1952 /* Changes pseudos created by function remove_scratches onto scratches. */
1954 restore_scratches (void)
1959 rtx_insn
*last
= NULL
;
1960 lra_insn_recog_data_t id
= NULL
;
1962 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
1964 if (last
!= loc
->insn
)
1967 id
= lra_get_insn_recog_data (last
);
1969 if (REG_P (*id
->operand_loc
[loc
->nop
])
1970 && ((regno
= REGNO (*id
->operand_loc
[loc
->nop
]))
1971 >= FIRST_PSEUDO_REGISTER
)
1972 && lra_get_regno_hard_regno (regno
) < 0)
1974 /* It should be only case when scratch register with chosen
1975 constraint 'X' did not get memory or hard register. */
1976 lra_assert (lra_former_scratch_p (regno
));
1977 *id
->operand_loc
[loc
->nop
]
1978 = gen_rtx_SCRATCH (GET_MODE (*id
->operand_loc
[loc
->nop
]));
1979 lra_update_dup (id
, loc
->nop
);
1980 if (lra_dump_file
!= NULL
)
1981 fprintf (lra_dump_file
, "Restoring SCRATCH in insn #%u(nop %d)\n",
1982 INSN_UID (loc
->insn
), loc
->nop
);
1985 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
1987 scratches
.release ();
1988 bitmap_clear (&scratch_bitmap
);
1989 bitmap_clear (&scratch_operand_bitmap
);
1994 /* Function checks RTL for correctness. If FINAL_P is true, it is
1995 done at the end of LRA and the check is more rigorous. */
1997 check_rtl (bool final_p
)
2002 lra_assert (! final_p
|| reload_completed
);
2003 FOR_EACH_BB_FN (bb
, cfun
)
2004 FOR_BB_INSNS (bb
, insn
)
2005 if (NONDEBUG_INSN_P (insn
)
2006 && GET_CODE (PATTERN (insn
)) != USE
2007 && GET_CODE (PATTERN (insn
)) != CLOBBER
2008 && GET_CODE (PATTERN (insn
)) != ASM_INPUT
)
2012 extract_constrain_insn (insn
);
2015 /* LRA code is based on assumption that all addresses can be
2016 correctly decomposed. LRA can generate reloads for
2017 decomposable addresses. The decomposition code checks the
2018 correctness of the addresses. So we don't need to check
2019 the addresses here. Don't call insn_invalid_p here, it can
2020 change the code at this stage. */
2021 if (recog_memoized (insn
) < 0 && asm_noperands (PATTERN (insn
)) < 0)
2022 fatal_insn_not_found (insn
);
2026 /* Determine if the current function has an exception receiver block
2027 that reaches the exit block via non-exceptional edges */
2029 has_nonexceptional_receiver (void)
2033 basic_block
*tos
, *worklist
, bb
;
2035 /* If we're not optimizing, then just err on the safe side. */
2039 /* First determine which blocks can reach exit via normal paths. */
2040 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
) + 1);
2042 FOR_EACH_BB_FN (bb
, cfun
)
2043 bb
->flags
&= ~BB_REACHABLE
;
2045 /* Place the exit block on our worklist. */
2046 EXIT_BLOCK_PTR_FOR_FN (cfun
)->flags
|= BB_REACHABLE
;
2047 *tos
++ = EXIT_BLOCK_PTR_FOR_FN (cfun
);
2049 /* Iterate: find everything reachable from what we've already seen. */
2050 while (tos
!= worklist
)
2054 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2055 if (e
->flags
& EDGE_ABNORMAL
)
2062 basic_block src
= e
->src
;
2064 if (!(src
->flags
& BB_REACHABLE
))
2066 src
->flags
|= BB_REACHABLE
;
2072 /* No exceptional block reached exit unexceptionally. */
2077 /* Process recursively X of INSN and add REG_INC notes if necessary. */
2079 add_auto_inc_notes (rtx_insn
*insn
, rtx x
)
2081 enum rtx_code code
= GET_CODE (x
);
2085 if (code
== MEM
&& auto_inc_p (XEXP (x
, 0)))
2087 add_reg_note (insn
, REG_INC
, XEXP (XEXP (x
, 0), 0));
2091 /* Scan all X sub-expressions. */
2092 fmt
= GET_RTX_FORMAT (code
);
2093 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2096 add_auto_inc_notes (insn
, XEXP (x
, i
));
2097 else if (fmt
[i
] == 'E')
2098 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2099 add_auto_inc_notes (insn
, XVECEXP (x
, i
, j
));
2104 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2105 We change pseudos by hard registers without notification of DF and
2106 that can make the notes obsolete. DF-infrastructure does not deal
2107 with REG_INC notes -- so we should regenerate them here. */
2109 update_inc_notes (void)
2115 FOR_EACH_BB_FN (bb
, cfun
)
2116 FOR_BB_INSNS (bb
, insn
)
2117 if (NONDEBUG_INSN_P (insn
))
2119 pnote
= ®_NOTES (insn
);
2122 if (REG_NOTE_KIND (*pnote
) == REG_DEAD
2123 || REG_NOTE_KIND (*pnote
) == REG_UNUSED
2124 || REG_NOTE_KIND (*pnote
) == REG_INC
)
2125 *pnote
= XEXP (*pnote
, 1);
2127 pnote
= &XEXP (*pnote
, 1);
2131 add_auto_inc_notes (insn
, PATTERN (insn
));
2135 /* Set to 1 while in lra. */
2136 int lra_in_progress
;
2138 /* Start of pseudo regnos before the LRA. */
2139 int lra_new_regno_start
;
2141 /* Start of reload pseudo regnos before the new spill pass. */
2142 int lra_constraint_new_regno_start
;
2144 /* Avoid spilling pseudos with regno more than the following value if
2146 int lra_bad_spill_regno_start
;
2148 /* Inheritance pseudo regnos before the new spill pass. */
2149 bitmap_head lra_inheritance_pseudos
;
2151 /* Split regnos before the new spill pass. */
2152 bitmap_head lra_split_regs
;
2154 /* Reload pseudo regnos before the new assignmnet pass which still can
2155 be spilled after the assinment pass as memory is also accepted in
2156 insns for the reload pseudos. */
2157 bitmap_head lra_optional_reload_pseudos
;
2159 /* Pseudo regnos used for subreg reloads before the new assignment
2160 pass. Such pseudos still can be spilled after the assinment
2162 bitmap_head lra_subreg_reload_pseudos
;
2164 /* File used for output of LRA debug information. */
2165 FILE *lra_dump_file
;
2167 /* True if we should try spill into registers of different classes
2168 instead of memory. */
2169 bool lra_reg_spill_p
;
2171 /* Set up value LRA_REG_SPILL_P. */
2173 setup_reg_spill_flag (void)
2177 if (targetm
.spill_class
!= NULL
)
2178 for (cl
= 0; cl
< (int) LIM_REG_CLASSES
; cl
++)
2179 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
2180 if (targetm
.spill_class ((enum reg_class
) cl
,
2181 (machine_mode
) mode
) != NO_REGS
)
2183 lra_reg_spill_p
= true;
2186 lra_reg_spill_p
= false;
2189 /* True if the current function is too big to use regular algorithms
2190 in LRA. In other words, we should use simpler and faster algorithms
2191 in LRA. It also means we should not worry about generation code
2192 for caller saves. The value is set up in IRA. */
2195 /* Major LRA entry function. F is a file should be used to dump LRA
2201 bool live_p
, scratch_p
, inserted_p
;
2205 timevar_push (TV_LRA
);
2207 /* Make sure that the last insn is a note. Some subsequent passes
2209 emit_note (NOTE_INSN_DELETED
);
2211 COPY_HARD_REG_SET (lra_no_alloc_regs
, ira_no_alloc_regs
);
2216 init_insn_recog_data ();
2218 /* Some quick check on RTL generated by previous passes. */
2222 lra_in_progress
= 1;
2224 lra_live_range_iter
= lra_coalesce_iter
= lra_constraint_iter
= 0;
2225 lra_assignment_iter
= lra_assignment_iter_after_spill
= 0;
2226 lra_inheritance_iter
= lra_undo_inheritance_iter
= 0;
2227 lra_rematerialization_iter
= 0;
2229 setup_reg_spill_flag ();
2231 /* Function remove_scratches can creates new pseudos for clobbers --
2232 so set up lra_constraint_new_regno_start before its call to
2233 permit changing reg classes for pseudos created by this
2235 lra_constraint_new_regno_start
= lra_new_regno_start
= max_reg_num ();
2236 lra_bad_spill_regno_start
= INT_MAX
;
2237 remove_scratches ();
2238 scratch_p
= lra_constraint_new_regno_start
!= max_reg_num ();
2240 /* A function that has a non-local label that can reach the exit
2241 block via non-exceptional paths must save all call-saved
2243 if (cfun
->has_nonlocal_label
&& has_nonexceptional_receiver ())
2244 crtl
->saves_all_registers
= 1;
2246 if (crtl
->saves_all_registers
)
2247 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2248 if (! call_used_regs
[i
] && ! fixed_regs
[i
] && ! LOCAL_REGNO (i
))
2249 df_set_regs_ever_live (i
, true);
2251 /* We don't DF from now and avoid its using because it is to
2252 expensive when a lot of RTL changes are made. */
2253 df_set_flags (DF_NO_INSN_RESCAN
);
2254 lra_constraint_insn_stack
.create (get_max_uid ());
2255 lra_constraint_insn_stack_bitmap
= sbitmap_alloc (get_max_uid ());
2256 bitmap_clear (lra_constraint_insn_stack_bitmap
);
2257 lra_live_ranges_init ();
2258 lra_constraints_init ();
2259 lra_curr_reload_num
= 0;
2260 push_insns (get_last_insn (), NULL
);
2261 /* It is needed for the 1st coalescing. */
2262 bitmap_initialize (&lra_inheritance_pseudos
, ®_obstack
);
2263 bitmap_initialize (&lra_split_regs
, ®_obstack
);
2264 bitmap_initialize (&lra_optional_reload_pseudos
, ®_obstack
);
2265 bitmap_initialize (&lra_subreg_reload_pseudos
, ®_obstack
);
2267 if (get_frame_size () != 0 && crtl
->stack_alignment_needed
)
2268 /* If we have a stack frame, we must align it now. The stack size
2269 may be a part of the offset computation for register
2271 assign_stack_local (BLKmode
, 0, crtl
->stack_alignment_needed
);
2277 /* We should try to assign hard registers to scratches even
2278 if there were no RTL transformations in
2280 if (! lra_constraints (lra_constraint_iter
== 0)
2281 && (lra_constraint_iter
> 1
2282 || (! scratch_p
&& ! caller_save_needed
)))
2284 /* Constraint transformations may result in that eliminable
2285 hard regs become uneliminable and pseudos which use them
2286 should be spilled. It is better to do it before pseudo
2289 For example, rs6000 can make
2290 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2291 to use a constant pool. */
2292 lra_eliminate (false, false);
2293 /* Do inheritance only for regular algorithms. */
2299 lra_clear_live_ranges ();
2300 /* As a side-effect of lra_create_live_ranges, we calculate
2301 actual_call_used_reg_set, which is needed during
2303 lra_create_live_ranges (true, true);
2309 lra_clear_live_ranges ();
2310 /* We need live ranges for lra_assign -- so build them. But
2311 don't remove dead insns or change global live info as we
2312 can undo inheritance transformations after inheritance
2313 pseudo assigning. */
2314 lra_create_live_ranges (true, false);
2316 /* If we don't spill non-reload and non-inheritance pseudos,
2317 there is no sense to run memory-memory move coalescing.
2318 If inheritance pseudos were spilled, the memory-memory
2319 moves involving them will be removed by pass undoing
2325 bool spill_p
= !lra_assign ();
2327 if (lra_undo_inheritance ())
2333 lra_create_live_ranges (true, true);
2336 if (lra_coalesce ())
2340 lra_clear_live_ranges ();
2343 /* Don't clear optional reloads bitmap until all constraints are
2344 satisfied as we need to differ them from regular reloads. */
2345 bitmap_clear (&lra_optional_reload_pseudos
);
2346 bitmap_clear (&lra_subreg_reload_pseudos
);
2347 bitmap_clear (&lra_inheritance_pseudos
);
2348 bitmap_clear (&lra_split_regs
);
2351 /* We need full live info for spilling pseudos into
2352 registers instead of memory. */
2353 lra_create_live_ranges (lra_reg_spill_p
, true);
2356 /* We should check necessity for spilling here as the above live
2357 range pass can remove spilled pseudos. */
2358 if (! lra_need_for_spills_p ())
2360 /* Now we know what pseudos should be spilled. Try to
2361 rematerialize them first. */
2364 /* We need full live info -- see the comment above. */
2365 lra_create_live_ranges (lra_reg_spill_p
, true);
2367 if (! lra_need_for_spills_p ())
2371 /* Assignment of stack slots changes elimination offsets for
2372 some eliminations. So update the offsets here. */
2373 lra_eliminate (false, false);
2374 lra_constraint_new_regno_start
= max_reg_num ();
2375 if (lra_bad_spill_regno_start
== INT_MAX
2376 && lra_inheritance_iter
> LRA_MAX_INHERITANCE_PASSES
2377 && lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
2378 /* After switching off inheritance and rematerialization
2379 passes, avoid spilling reload pseudos will be created to
2380 prevent LRA cycling in some complicated cases. */
2381 lra_bad_spill_regno_start
= lra_constraint_new_regno_start
;
2382 lra_assignment_iter_after_spill
= 0;
2384 restore_scratches ();
2385 lra_eliminate (true, false);
2386 lra_final_code_change ();
2387 lra_in_progress
= 0;
2389 lra_clear_live_ranges ();
2390 lra_live_ranges_finish ();
2391 lra_constraints_finish ();
2393 sbitmap_free (lra_constraint_insn_stack_bitmap
);
2394 lra_constraint_insn_stack
.release ();
2395 finish_insn_recog_data ();
2396 regstat_free_n_sets_and_refs ();
2398 reload_completed
= 1;
2399 update_inc_notes ();
2401 inserted_p
= fixup_abnormal_edges ();
2403 /* We've possibly turned single trapping insn into multiple ones. */
2404 if (cfun
->can_throw_non_call_exceptions
)
2407 blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
2408 bitmap_ones (blocks
);
2409 find_many_sub_basic_blocks (blocks
);
2410 sbitmap_free (blocks
);
2414 commit_edge_insertions ();
2416 /* Replacing pseudos with their memory equivalents might have
2417 created shared rtx. Subsequent passes would get confused
2418 by this, so unshare everything here. */
2419 unshare_all_rtl_again (get_insns ());
2424 timevar_pop (TV_LRA
);
2427 /* Called once per compiler to initialize LRA data once. */
2429 lra_init_once (void)
2431 init_insn_code_data_once ();
2434 /* Called once per compiler to finish LRA data which are initialize
2437 lra_finish_once (void)
2439 finish_insn_code_data_once ();