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"
107 #include "hard-reg-set.h"
111 #include "insn-config.h"
112 #include "insn-codes.h"
115 #include "addresses.h"
118 #include "hash-set.h"
121 #include "function.h"
126 #include "statistics.h"
132 #include "emit-rtl.h"
137 #include "dominance.h"
140 #include "cfgbuild.h"
141 #include "basic-block.h"
143 #include "tree-pass.h"
147 #include "alloc-pool.h"
151 /* Dump bitmap SET with TITLE and BB INDEX. */
153 lra_dump_bitmap_with_title (const char *title
, bitmap set
, int index
)
158 static const int max_nums_on_line
= 10;
160 if (bitmap_empty_p (set
))
162 fprintf (lra_dump_file
, " %s %d:", title
, index
);
163 fprintf (lra_dump_file
, "\n");
164 count
= max_nums_on_line
+ 1;
165 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
167 if (count
> max_nums_on_line
)
169 fprintf (lra_dump_file
, "\n ");
172 fprintf (lra_dump_file
, " %4u", i
);
175 fprintf (lra_dump_file
, "\n");
178 /* Hard registers currently not available for allocation. It can
179 changed after some hard registers become not eliminable. */
180 HARD_REG_SET lra_no_alloc_regs
;
182 static int get_new_reg_value (void);
183 static void expand_reg_info (void);
184 static void invalidate_insn_recog_data (int);
185 static int get_insn_freq (rtx_insn
*);
186 static void invalidate_insn_data_regno_info (lra_insn_recog_data_t
,
189 /* Expand all regno related info needed for LRA. */
191 expand_reg_data (int old
)
195 ira_expand_reg_equiv ();
196 for (int i
= (int) max_reg_num () - 1; i
>= old
; i
--)
197 lra_change_class (i
, ALL_REGS
, " Set", true);
200 /* Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL
201 or of VOIDmode, use MD_MODE for the new reg. Initialize its
202 register class to RCLASS. Print message about assigning class
203 RCLASS containing new register name TITLE unless it is NULL. Use
204 attributes of ORIGINAL if it is a register. The created register
205 will have unique held value. */
207 lra_create_new_reg_with_unique_value (machine_mode md_mode
, rtx original
,
208 enum reg_class rclass
, const char *title
)
213 if (original
== NULL_RTX
|| (mode
= GET_MODE (original
)) == VOIDmode
)
215 lra_assert (mode
!= VOIDmode
);
216 new_reg
= gen_reg_rtx (mode
);
217 if (original
== NULL_RTX
|| ! REG_P (original
))
219 if (lra_dump_file
!= NULL
)
220 fprintf (lra_dump_file
, " Creating newreg=%i", REGNO (new_reg
));
224 if (ORIGINAL_REGNO (original
) >= FIRST_PSEUDO_REGISTER
)
225 ORIGINAL_REGNO (new_reg
) = ORIGINAL_REGNO (original
);
226 REG_USERVAR_P (new_reg
) = REG_USERVAR_P (original
);
227 REG_POINTER (new_reg
) = REG_POINTER (original
);
228 REG_ATTRS (new_reg
) = REG_ATTRS (original
);
229 if (lra_dump_file
!= NULL
)
230 fprintf (lra_dump_file
, " Creating newreg=%i from oldreg=%i",
231 REGNO (new_reg
), REGNO (original
));
233 if (lra_dump_file
!= NULL
)
236 fprintf (lra_dump_file
, ", assigning class %s to%s%s r%d",
237 reg_class_names
[rclass
], *title
== '\0' ? "" : " ",
238 title
, REGNO (new_reg
));
239 fprintf (lra_dump_file
, "\n");
241 expand_reg_data (max_reg_num ());
242 setup_reg_classes (REGNO (new_reg
), rclass
, NO_REGS
, rclass
);
246 /* Analogous to the previous function but also inherits value of
249 lra_create_new_reg (machine_mode md_mode
, rtx original
,
250 enum reg_class rclass
, const char *title
)
255 = lra_create_new_reg_with_unique_value (md_mode
, original
, rclass
, title
);
256 if (original
!= NULL_RTX
&& REG_P (original
))
257 lra_assign_reg_val (REGNO (original
), REGNO (new_reg
));
261 /* Set up for REGNO unique hold value. */
263 lra_set_regno_unique_value (int regno
)
265 lra_reg_info
[regno
].val
= get_new_reg_value ();
268 /* Invalidate INSN related info used by LRA. The info should never be
271 lra_invalidate_insn_data (rtx_insn
*insn
)
273 lra_invalidate_insn_regno_info (insn
);
274 invalidate_insn_recog_data (INSN_UID (insn
));
277 /* Mark INSN deleted and invalidate the insn related info used by
280 lra_set_insn_deleted (rtx_insn
*insn
)
282 lra_invalidate_insn_data (insn
);
283 SET_INSN_DELETED (insn
);
286 /* Delete an unneeded INSN and any previous insns who sole purpose is
287 loading data that is dead in INSN. */
289 lra_delete_dead_insn (rtx_insn
*insn
)
291 rtx_insn
*prev
= prev_real_insn (insn
);
294 /* If the previous insn sets a register that dies in our insn,
296 if (prev
&& GET_CODE (PATTERN (prev
)) == SET
297 && (prev_dest
= SET_DEST (PATTERN (prev
)), REG_P (prev_dest
))
298 && reg_mentioned_p (prev_dest
, PATTERN (insn
))
299 && find_regno_note (insn
, REG_DEAD
, REGNO (prev_dest
))
300 && ! side_effects_p (SET_SRC (PATTERN (prev
))))
301 lra_delete_dead_insn (prev
);
303 lra_set_insn_deleted (insn
);
306 /* Emit insn x = y + z. Return NULL if we failed to do it.
307 Otherwise, return the insn. We don't use gen_add3_insn as it might
310 emit_add3_insn (rtx x
, rtx y
, rtx z
)
314 last
= get_last_insn ();
316 if (have_addptr3_insn (x
, y
, z
))
318 rtx_insn
*insn
= gen_addptr3_insn (x
, y
, z
);
320 /* If the target provides an "addptr" pattern it hopefully does
321 for a reason. So falling back to the normal add would be
323 lra_assert (insn
!= NULL_RTX
);
328 rtx_insn
*insn
= emit_insn (gen_rtx_SET (x
, gen_rtx_PLUS (GET_MODE (y
),
330 if (recog_memoized (insn
) < 0)
332 delete_insns_since (last
);
338 /* Emit insn x = x + y. Return the insn. We use gen_add2_insn as the
341 emit_add2_insn (rtx x
, rtx y
)
343 rtx_insn
*insn
= emit_add3_insn (x
, x
, y
);
344 if (insn
== NULL_RTX
)
346 insn
= gen_add2_insn (x
, y
);
347 if (insn
!= NULL_RTX
)
353 /* Target checks operands through operand predicates to recognize an
354 insn. We should have a special precaution to generate add insns
355 which are frequent results of elimination.
357 Emit insns for x = y + z. X can be used to store intermediate
358 values and should be not in Y and Z when we use X to store an
359 intermediate value. Y + Z should form [base] [+ index[ * scale]] [
360 + disp] where base and index are registers, disp and scale are
361 constants. Y should contain base if it is present, Z should
362 contain disp if any. index[*scale] can be part of Y or Z. */
364 lra_emit_add (rtx x
, rtx y
, rtx z
)
368 rtx a1
, a2
, base
, index
, disp
, scale
, index_scale
;
371 rtx_insn
*add3_insn
= emit_add3_insn (x
, y
, z
);
372 old
= max_reg_num ();
373 if (add3_insn
!= NULL
)
377 disp
= a2
= NULL_RTX
;
378 if (GET_CODE (y
) == PLUS
)
392 index_scale
= scale
= NULL_RTX
;
393 if (GET_CODE (a1
) == MULT
)
396 index
= XEXP (a1
, 0);
397 scale
= XEXP (a1
, 1);
400 else if (a2
!= NULL_RTX
&& GET_CODE (a2
) == MULT
)
403 index
= XEXP (a2
, 0);
404 scale
= XEXP (a2
, 1);
412 if (! (REG_P (base
) || GET_CODE (base
) == SUBREG
)
413 || (index
!= NULL_RTX
414 && ! (REG_P (index
) || GET_CODE (index
) == SUBREG
))
415 || (disp
!= NULL_RTX
&& ! CONSTANT_P (disp
))
416 || (scale
!= NULL_RTX
&& ! CONSTANT_P (scale
)))
418 /* Probably we have no 3 op add. Last chance is to use 2-op
419 add insn. To succeed, don't move Z to X as an address
420 segment always comes in Y. Otherwise, we might fail when
421 adding the address segment to register. */
422 lra_assert (x
!= y
&& x
!= z
);
423 emit_move_insn (x
, y
);
424 rtx_insn
*insn
= emit_add2_insn (x
, z
);
425 lra_assert (insn
!= NULL_RTX
);
429 if (index_scale
== NULL_RTX
)
431 if (disp
== NULL_RTX
)
433 /* Generate x = index_scale; x = x + base. */
434 lra_assert (index_scale
!= NULL_RTX
&& base
!= NULL_RTX
);
435 emit_move_insn (x
, index_scale
);
436 rtx_insn
*insn
= emit_add2_insn (x
, base
);
437 lra_assert (insn
!= NULL_RTX
);
439 else if (scale
== NULL_RTX
)
441 /* Try x = base + disp. */
442 lra_assert (base
!= NULL_RTX
);
443 last
= get_last_insn ();
444 rtx_insn
*move_insn
=
445 emit_move_insn (x
, gen_rtx_PLUS (GET_MODE (base
), base
, disp
));
446 if (recog_memoized (move_insn
) < 0)
448 delete_insns_since (last
);
449 /* Generate x = disp; x = x + base. */
450 emit_move_insn (x
, disp
);
451 rtx_insn
*add2_insn
= emit_add2_insn (x
, base
);
452 lra_assert (add2_insn
!= NULL_RTX
);
454 /* Generate x = x + index. */
455 if (index
!= NULL_RTX
)
457 rtx_insn
*insn
= emit_add2_insn (x
, index
);
458 lra_assert (insn
!= NULL_RTX
);
463 /* Try x = index_scale; x = x + disp; x = x + base. */
464 last
= get_last_insn ();
465 rtx_insn
*move_insn
= emit_move_insn (x
, index_scale
);
467 if (recog_memoized (move_insn
) >= 0)
469 rtx_insn
*insn
= emit_add2_insn (x
, disp
);
470 if (insn
!= NULL_RTX
)
472 insn
= emit_add2_insn (x
, base
);
473 if (insn
!= NULL_RTX
)
479 delete_insns_since (last
);
480 /* Generate x = disp; x = x + base; x = x + index_scale. */
481 emit_move_insn (x
, disp
);
482 rtx_insn
*insn
= emit_add2_insn (x
, base
);
483 lra_assert (insn
!= NULL_RTX
);
484 insn
= emit_add2_insn (x
, index_scale
);
485 lra_assert (insn
!= NULL_RTX
);
490 /* Functions emit_... can create pseudos -- so expand the pseudo
492 if (old
!= max_reg_num ())
493 expand_reg_data (old
);
496 /* The number of emitted reload insns so far. */
497 int lra_curr_reload_num
;
499 /* Emit x := y, processing special case when y = u + v or y = u + v *
500 scale + w through emit_add (Y can be an address which is base +
501 index reg * scale + displacement in general case). X may be used
502 as intermediate result therefore it should be not in Y. */
504 lra_emit_move (rtx x
, rtx y
)
508 if (GET_CODE (y
) != PLUS
)
510 if (rtx_equal_p (x
, y
))
512 old
= max_reg_num ();
513 emit_move_insn (x
, y
);
515 lra_reg_info
[ORIGINAL_REGNO (x
)].last_reload
= ++lra_curr_reload_num
;
516 /* Function emit_move can create pseudos -- so expand the pseudo
518 if (old
!= max_reg_num ())
519 expand_reg_data (old
);
522 lra_emit_add (x
, XEXP (y
, 0), XEXP (y
, 1));
525 /* Update insn operands which are duplication of operands whose
526 numbers are in array of NOPS (with end marker -1). The insn is
527 represented by its LRA internal representation ID. */
529 lra_update_dups (lra_insn_recog_data_t id
, signed char *nops
)
532 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
534 for (i
= 0; i
< static_id
->n_dups
; i
++)
535 for (j
= 0; (nop
= nops
[j
]) >= 0; j
++)
536 if (static_id
->dup_num
[i
] == nop
)
537 *id
->dup_loc
[i
] = *id
->operand_loc
[nop
];
542 /* This page contains code dealing with info about registers in the
545 /* Pools for insn reg info. */
546 pool_allocator
<lra_insn_reg
> lra_insn_reg::pool ("insn regs", 100);
548 /* Create LRA insn related info about a reference to REGNO in INSN with
549 TYPE (in/out/inout), biggest reference mode MODE, flag that it is
550 reference through subreg (SUBREG_P), flag that is early clobbered
551 in the insn (EARLY_CLOBBER), and reference to the next insn reg
553 static struct lra_insn_reg
*
554 new_insn_reg (rtx_insn
*insn
, int regno
, enum op_type type
,
556 bool subreg_p
, bool early_clobber
, struct lra_insn_reg
*next
)
558 lra_insn_reg
*ir
= new lra_insn_reg ();
560 ir
->biggest_mode
= mode
;
561 if (GET_MODE_SIZE (mode
) > GET_MODE_SIZE (lra_reg_info
[regno
].biggest_mode
)
562 && NONDEBUG_INSN_P (insn
))
563 lra_reg_info
[regno
].biggest_mode
= mode
;
564 ir
->subreg_p
= subreg_p
;
565 ir
->early_clobber
= early_clobber
;
571 /* Free insn reg info list IR. */
573 free_insn_regs (struct lra_insn_reg
*ir
)
575 struct lra_insn_reg
*next_ir
;
577 for (; ir
!= NULL
; ir
= next_ir
)
584 /* Finish pool for insn reg info. */
586 finish_insn_regs (void)
588 lra_insn_reg::pool
.release ();
593 /* This page contains code dealing LRA insn info (or in other words
594 LRA internal insn representation). */
596 /* Map INSN_CODE -> the static insn data. This info is valid during
597 all translation unit. */
598 struct lra_static_insn_data
*insn_code_data
[LAST_INSN_CODE
];
600 /* Debug insns are represented as a special insn with one input
601 operand which is RTL expression in var_location. */
603 /* The following data are used as static insn operand data for all
604 debug insns. If structure lra_operand_data is changed, the
605 initializer should be changed too. */
606 static struct lra_operand_data debug_operand_data
=
608 NULL
, /* alternative */
609 VOIDmode
, /* We are not interesting in the operand mode. */
614 /* The following data are used as static insn data for all debug
615 insns. If structure lra_static_insn_data is changed, the
616 initializer should be changed too. */
617 static struct lra_static_insn_data debug_insn_static_data
=
620 0, /* Duplication operands #. */
621 -1, /* Commutative operand #. */
622 1, /* Operands #. There is only one operand which is debug RTL
624 0, /* Duplications #. */
625 0, /* Alternatives #. We are not interesting in alternatives
626 because we does not proceed debug_insns for reloads. */
627 NULL
, /* Hard registers referenced in machine description. */
628 NULL
/* Descriptions of operands in alternatives. */
631 /* Called once per compiler work to initialize some LRA data related
634 init_insn_code_data_once (void)
636 memset (insn_code_data
, 0, sizeof (insn_code_data
));
639 /* Called once per compiler work to finalize some LRA data related to
642 finish_insn_code_data_once (void)
646 for (i
= 0; i
< LAST_INSN_CODE
; i
++)
648 if (insn_code_data
[i
] != NULL
)
649 free (insn_code_data
[i
]);
653 /* Return static insn data, allocate and setup if necessary. Although
654 dup_num is static data (it depends only on icode), to set it up we
655 need to extract insn first. So recog_data should be valid for
656 normal insn (ICODE >= 0) before the call. */
657 static struct lra_static_insn_data
*
658 get_static_insn_data (int icode
, int nop
, int ndup
, int nalt
)
660 struct lra_static_insn_data
*data
;
663 lra_assert (icode
< LAST_INSN_CODE
);
664 if (icode
>= 0 && (data
= insn_code_data
[icode
]) != NULL
)
666 lra_assert (nop
>= 0 && ndup
>= 0 && nalt
>= 0);
667 n_bytes
= sizeof (struct lra_static_insn_data
)
668 + sizeof (struct lra_operand_data
) * nop
669 + sizeof (int) * ndup
;
670 data
= XNEWVAR (struct lra_static_insn_data
, n_bytes
);
671 data
->operand_alternative
= NULL
;
672 data
->n_operands
= nop
;
674 data
->n_alternatives
= nalt
;
675 data
->operand
= ((struct lra_operand_data
*)
676 ((char *) data
+ sizeof (struct lra_static_insn_data
)));
677 data
->dup_num
= ((int *) ((char *) data
->operand
678 + sizeof (struct lra_operand_data
) * nop
));
683 insn_code_data
[icode
] = data
;
684 for (i
= 0; i
< nop
; i
++)
686 data
->operand
[i
].constraint
687 = insn_data
[icode
].operand
[i
].constraint
;
688 data
->operand
[i
].mode
= insn_data
[icode
].operand
[i
].mode
;
689 data
->operand
[i
].strict_low
= insn_data
[icode
].operand
[i
].strict_low
;
690 data
->operand
[i
].is_operator
691 = insn_data
[icode
].operand
[i
].is_operator
;
692 data
->operand
[i
].type
693 = (data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
694 : data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
696 data
->operand
[i
].is_address
= false;
698 for (i
= 0; i
< ndup
; i
++)
699 data
->dup_num
[i
] = recog_data
.dup_num
[i
];
704 /* The current length of the following array. */
705 int lra_insn_recog_data_len
;
707 /* Map INSN_UID -> the insn recog data (NULL if unknown). */
708 lra_insn_recog_data_t
*lra_insn_recog_data
;
710 /* Initialize LRA data about insns. */
712 init_insn_recog_data (void)
714 lra_insn_recog_data_len
= 0;
715 lra_insn_recog_data
= NULL
;
718 /* Expand, if necessary, LRA data about insns. */
720 check_and_expand_insn_recog_data (int index
)
724 if (lra_insn_recog_data_len
> index
)
726 old
= lra_insn_recog_data_len
;
727 lra_insn_recog_data_len
= index
* 3 / 2 + 1;
728 lra_insn_recog_data
= XRESIZEVEC (lra_insn_recog_data_t
,
730 lra_insn_recog_data_len
);
731 for (i
= old
; i
< lra_insn_recog_data_len
; i
++)
732 lra_insn_recog_data
[i
] = NULL
;
735 /* Finish LRA DATA about insn. */
737 free_insn_recog_data (lra_insn_recog_data_t data
)
739 if (data
->operand_loc
!= NULL
)
740 free (data
->operand_loc
);
741 if (data
->dup_loc
!= NULL
)
742 free (data
->dup_loc
);
743 if (data
->arg_hard_regs
!= NULL
)
744 free (data
->arg_hard_regs
);
745 if (data
->icode
< 0 && NONDEBUG_INSN_P (data
->insn
))
747 if (data
->insn_static_data
->operand_alternative
!= NULL
)
748 free (const_cast <operand_alternative
*>
749 (data
->insn_static_data
->operand_alternative
));
750 free_insn_regs (data
->insn_static_data
->hard_regs
);
751 free (data
->insn_static_data
);
753 free_insn_regs (data
->regs
);
758 /* Finish LRA data about all insns. */
760 finish_insn_recog_data (void)
763 lra_insn_recog_data_t data
;
765 for (i
= 0; i
< lra_insn_recog_data_len
; i
++)
766 if ((data
= lra_insn_recog_data
[i
]) != NULL
)
767 free_insn_recog_data (data
);
769 lra_copy::pool
.release ();
770 lra_insn_reg::pool
.release ();
771 free (lra_insn_recog_data
);
774 /* Setup info about operands in alternatives of LRA DATA of insn. */
776 setup_operand_alternative (lra_insn_recog_data_t data
,
777 const operand_alternative
*op_alt
)
780 int icode
= data
->icode
;
781 struct lra_static_insn_data
*static_data
= data
->insn_static_data
;
783 static_data
->commutative
= -1;
784 nop
= static_data
->n_operands
;
785 nalt
= static_data
->n_alternatives
;
786 static_data
->operand_alternative
= op_alt
;
787 for (i
= 0; i
< nop
; i
++)
789 static_data
->operand
[i
].early_clobber
= false;
790 static_data
->operand
[i
].is_address
= false;
791 if (static_data
->operand
[i
].constraint
[0] == '%')
793 /* We currently only support one commutative pair of operands. */
794 if (static_data
->commutative
< 0)
795 static_data
->commutative
= i
;
797 lra_assert (icode
< 0); /* Asm */
798 /* The last operand should not be marked commutative. */
799 lra_assert (i
!= nop
- 1);
802 for (j
= 0; j
< nalt
; j
++)
803 for (i
= 0; i
< nop
; i
++, op_alt
++)
805 static_data
->operand
[i
].early_clobber
|= op_alt
->earlyclobber
;
806 static_data
->operand
[i
].is_address
|= op_alt
->is_address
;
810 /* Recursively process X and collect info about registers, which are
811 not the insn operands, in X with TYPE (in/out/inout) and flag that
812 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
813 to LIST. X is a part of insn given by DATA. Return the result
815 static struct lra_insn_reg
*
816 collect_non_operand_hard_regs (rtx
*x
, lra_insn_recog_data_t data
,
817 struct lra_insn_reg
*list
,
818 enum op_type type
, bool early_clobber
)
820 int i
, j
, regno
, last
;
823 struct lra_insn_reg
*curr
;
825 enum rtx_code code
= GET_CODE (op
);
826 const char *fmt
= GET_RTX_FORMAT (code
);
828 for (i
= 0; i
< data
->insn_static_data
->n_operands
; i
++)
829 if (x
== data
->operand_loc
[i
])
830 /* It is an operand loc. Stop here. */
832 for (i
= 0; i
< data
->insn_static_data
->n_dups
; i
++)
833 if (x
== data
->dup_loc
[i
])
834 /* It is a dup loc. Stop here. */
836 mode
= GET_MODE (op
);
840 op
= SUBREG_REG (op
);
841 code
= GET_CODE (op
);
842 if (GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (op
)))
844 mode
= GET_MODE (op
);
845 if (GET_MODE_SIZE (mode
) > REGMODE_NATURAL_SIZE (mode
))
851 if ((regno
= REGNO (op
)) >= FIRST_PSEUDO_REGISTER
)
853 /* Process all regs even unallocatable ones as we need info
854 about all regs for rematerialization pass. */
855 for (last
= regno
+ hard_regno_nregs
[regno
][mode
];
859 for (curr
= list
; curr
!= NULL
; curr
= curr
->next
)
860 if (curr
->regno
== regno
&& curr
->subreg_p
== subreg_p
861 && curr
->biggest_mode
== mode
)
863 if (curr
->type
!= type
)
864 curr
->type
= OP_INOUT
;
865 if (curr
->early_clobber
!= early_clobber
)
866 curr
->early_clobber
= true;
871 /* This is a new hard regno or the info can not be
872 integrated into the found structure. */
876 /* This clobber is to inform popping floating
878 && ! (FIRST_STACK_REG
<= regno
879 && regno
<= LAST_STACK_REG
));
881 list
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
882 early_clobber
, list
);
890 list
= collect_non_operand_hard_regs (&SET_DEST (op
), data
,
891 list
, OP_OUT
, false);
892 list
= collect_non_operand_hard_regs (&SET_SRC (op
), data
,
896 /* We treat clobber of non-operand hard registers as early
897 clobber (the behavior is expected from asm). */
898 list
= collect_non_operand_hard_regs (&XEXP (op
, 0), data
,
901 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
902 list
= collect_non_operand_hard_regs (&XEXP (op
, 0), data
,
903 list
, OP_INOUT
, false);
905 case PRE_MODIFY
: case POST_MODIFY
:
906 list
= collect_non_operand_hard_regs (&XEXP (op
, 0), data
,
907 list
, OP_INOUT
, false);
908 list
= collect_non_operand_hard_regs (&XEXP (op
, 1), data
,
912 fmt
= GET_RTX_FORMAT (code
);
913 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
916 list
= collect_non_operand_hard_regs (&XEXP (op
, i
), data
,
918 else if (fmt
[i
] == 'E')
919 for (j
= XVECLEN (op
, i
) - 1; j
>= 0; j
--)
920 list
= collect_non_operand_hard_regs (&XVECEXP (op
, i
, j
), data
,
927 /* Set up and return info about INSN. Set up the info if it is not set up
929 lra_insn_recog_data_t
930 lra_set_insn_recog_data (rtx_insn
*insn
)
932 lra_insn_recog_data_t data
;
935 unsigned int uid
= INSN_UID (insn
);
936 struct lra_static_insn_data
*insn_static_data
;
938 check_and_expand_insn_recog_data (uid
);
939 if (DEBUG_INSN_P (insn
))
943 icode
= INSN_CODE (insn
);
945 /* It might be a new simple insn which is not recognized yet. */
946 INSN_CODE (insn
) = icode
= recog_memoized (insn
);
948 data
= XNEW (struct lra_insn_recog_data
);
949 lra_insn_recog_data
[uid
] = data
;
951 data
->used_insn_alternative
= -1;
954 if (DEBUG_INSN_P (insn
))
956 data
->insn_static_data
= &debug_insn_static_data
;
957 data
->dup_loc
= NULL
;
958 data
->arg_hard_regs
= NULL
;
959 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
960 data
->operand_loc
= XNEWVEC (rtx
*, 1);
961 data
->operand_loc
[0] = &INSN_VAR_LOCATION_LOC (insn
);
967 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
968 const char *constraints
[MAX_RECOG_OPERANDS
];
970 nop
= asm_noperands (PATTERN (insn
));
971 data
->operand_loc
= data
->dup_loc
= NULL
;
975 /* It is a special insn like USE or CLOBBER. We should
976 recognize any regular insn otherwise LRA can do nothing
978 gcc_assert (GET_CODE (PATTERN (insn
)) == USE
979 || GET_CODE (PATTERN (insn
)) == CLOBBER
980 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
981 data
->insn_static_data
= insn_static_data
982 = get_static_insn_data (-1, 0, 0, nalt
);
986 /* expand_asm_operands makes sure there aren't too many
988 lra_assert (nop
<= MAX_RECOG_OPERANDS
);
990 data
->operand_loc
= XNEWVEC (rtx
*, nop
);
991 /* Now get the operand values and constraints out of the
993 decode_asm_operands (PATTERN (insn
), NULL
,
995 constraints
, operand_mode
, NULL
);
998 const char *p
= recog_data
.constraints
[0];
1000 for (p
= constraints
[0]; *p
; p
++)
1003 data
->insn_static_data
= insn_static_data
1004 = get_static_insn_data (-1, nop
, 0, nalt
);
1005 for (i
= 0; i
< nop
; i
++)
1007 insn_static_data
->operand
[i
].mode
= operand_mode
[i
];
1008 insn_static_data
->operand
[i
].constraint
= constraints
[i
];
1009 insn_static_data
->operand
[i
].strict_low
= false;
1010 insn_static_data
->operand
[i
].is_operator
= false;
1011 insn_static_data
->operand
[i
].is_address
= false;
1014 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1015 insn_static_data
->operand
[i
].type
1016 = (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1017 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1019 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
1022 operand_alternative
*op_alt
= XCNEWVEC (operand_alternative
,
1024 preprocess_constraints (nop
, nalt
, constraints
, op_alt
);
1025 setup_operand_alternative (data
, op_alt
);
1030 insn_extract (insn
);
1031 data
->insn_static_data
= insn_static_data
1032 = get_static_insn_data (icode
, insn_data
[icode
].n_operands
,
1033 insn_data
[icode
].n_dups
,
1034 insn_data
[icode
].n_alternatives
);
1035 n
= insn_static_data
->n_operands
;
1040 locs
= XNEWVEC (rtx
*, n
);
1041 memcpy (locs
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1043 data
->operand_loc
= locs
;
1044 n
= insn_static_data
->n_dups
;
1049 locs
= XNEWVEC (rtx
*, n
);
1050 memcpy (locs
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1052 data
->dup_loc
= locs
;
1053 data
->preferred_alternatives
= get_preferred_alternatives (insn
);
1054 const operand_alternative
*op_alt
= preprocess_insn_constraints (icode
);
1055 if (!insn_static_data
->operand_alternative
)
1056 setup_operand_alternative (data
, op_alt
);
1057 else if (op_alt
!= insn_static_data
->operand_alternative
)
1058 insn_static_data
->operand_alternative
= op_alt
;
1060 if (GET_CODE (PATTERN (insn
)) == CLOBBER
|| GET_CODE (PATTERN (insn
)) == USE
)
1061 insn_static_data
->hard_regs
= NULL
;
1063 insn_static_data
->hard_regs
1064 = collect_non_operand_hard_regs (&PATTERN (insn
), data
,
1065 NULL
, OP_IN
, false);
1066 data
->arg_hard_regs
= NULL
;
1070 int n_hard_regs
, regno
, arg_hard_regs
[FIRST_PSEUDO_REGISTER
];
1073 /* Finding implicit hard register usage. We believe it will be
1074 not changed whatever transformations are used. Call insns
1075 are such example. */
1076 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1078 link
= XEXP (link
, 1))
1079 if (GET_CODE (XEXP (link
, 0)) == USE
1080 && REG_P (XEXP (XEXP (link
, 0), 0)))
1082 regno
= REGNO (XEXP (XEXP (link
, 0), 0));
1083 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
1084 /* It is an argument register. */
1085 for (i
= REG_NREGS (XEXP (XEXP (link
, 0), 0)) - 1; i
>= 0; i
--)
1086 arg_hard_regs
[n_hard_regs
++] = regno
+ i
;
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
);
1207 #ifdef ENABLE_CHECKING
1211 for (i
= 0; i
< nop
; i
++)
1213 (insn_static_data
->operand
[i
].mode
== operand_mode
[i
]
1214 && insn_static_data
->operand
[i
].constraint
== constraints
[i
]
1215 && ! insn_static_data
->operand
[i
].is_operator
);
1219 #ifdef ENABLE_CHECKING
1223 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1225 (insn_static_data
->operand
[i
].type
1226 == (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1227 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1234 insn_extract (insn
);
1235 n
= insn_static_data
->n_operands
;
1237 memcpy (data
->operand_loc
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1238 n
= insn_static_data
->n_dups
;
1240 memcpy (data
->dup_loc
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1241 lra_assert (check_bool_attrs (insn
));
1246 /* Set up that INSN is using alternative ALT now. */
1248 lra_set_used_insn_alternative (rtx_insn
*insn
, int alt
)
1250 lra_insn_recog_data_t data
;
1252 data
= lra_get_insn_recog_data (insn
);
1253 data
->used_insn_alternative
= alt
;
1256 /* Set up that insn with UID is using alternative ALT now. The insn
1257 info should be already set up. */
1259 lra_set_used_insn_alternative_by_uid (int uid
, int alt
)
1261 lra_insn_recog_data_t data
;
1263 check_and_expand_insn_recog_data (uid
);
1264 data
= lra_insn_recog_data
[uid
];
1265 lra_assert (data
!= NULL
);
1266 data
->used_insn_alternative
= alt
;
1271 /* This page contains code dealing with common register info and
1274 /* The size of the following array. */
1275 static int reg_info_size
;
1276 /* Common info about each register. */
1277 struct lra_reg
*lra_reg_info
;
1279 /* Last register value. */
1280 static int last_reg_value
;
1282 /* Return new register value. */
1284 get_new_reg_value (void)
1286 return ++last_reg_value
;
1289 /* Pools for copies. */
1290 pool_allocator
<lra_copy
> lra_copy::pool ("lra copies", 100);
1292 /* Vec referring to pseudo copies. */
1293 static vec
<lra_copy_t
> copy_vec
;
1295 /* Initialize I-th element of lra_reg_info. */
1297 initialize_lra_reg_info_element (int i
)
1299 bitmap_initialize (&lra_reg_info
[i
].insn_bitmap
, ®_obstack
);
1301 lra_reg_info
[i
].no_stack_p
= false;
1303 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
1304 CLEAR_HARD_REG_SET (lra_reg_info
[i
].actual_call_used_reg_set
);
1305 lra_reg_info
[i
].preferred_hard_regno1
= -1;
1306 lra_reg_info
[i
].preferred_hard_regno2
= -1;
1307 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
1308 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
1309 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
1310 lra_reg_info
[i
].live_ranges
= NULL
;
1311 lra_reg_info
[i
].nrefs
= lra_reg_info
[i
].freq
= 0;
1312 lra_reg_info
[i
].last_reload
= 0;
1313 lra_reg_info
[i
].restore_regno
= -1;
1314 lra_reg_info
[i
].val
= get_new_reg_value ();
1315 lra_reg_info
[i
].offset
= 0;
1316 lra_reg_info
[i
].copies
= NULL
;
1319 /* Initialize common reg info and copies. */
1321 init_reg_info (void)
1326 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1327 lra_reg_info
= XNEWVEC (struct lra_reg
, reg_info_size
);
1328 for (i
= 0; i
< reg_info_size
; i
++)
1329 initialize_lra_reg_info_element (i
);
1330 copy_vec
.create (100);
1334 /* Finish common reg info and copies. */
1336 finish_reg_info (void)
1340 for (i
= 0; i
< reg_info_size
; i
++)
1341 bitmap_clear (&lra_reg_info
[i
].insn_bitmap
);
1342 free (lra_reg_info
);
1346 /* Expand common reg info if it is necessary. */
1348 expand_reg_info (void)
1350 int i
, old
= reg_info_size
;
1352 if (reg_info_size
> max_reg_num ())
1354 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1355 lra_reg_info
= XRESIZEVEC (struct lra_reg
, lra_reg_info
, reg_info_size
);
1356 for (i
= old
; i
< reg_info_size
; i
++)
1357 initialize_lra_reg_info_element (i
);
1360 /* Free all copies. */
1362 lra_free_copies (void)
1366 while (copy_vec
.length () != 0)
1368 cp
= copy_vec
.pop ();
1369 lra_reg_info
[cp
->regno1
].copies
= lra_reg_info
[cp
->regno2
].copies
= NULL
;
1374 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1375 frequency is FREQ. */
1377 lra_create_copy (int regno1
, int regno2
, int freq
)
1382 lra_assert (regno1
!= regno2
);
1383 regno1_dest_p
= true;
1384 if (regno1
> regno2
)
1388 regno1_dest_p
= false;
1392 cp
= new lra_copy ();
1393 copy_vec
.safe_push (cp
);
1394 cp
->regno1_dest_p
= regno1_dest_p
;
1396 cp
->regno1
= regno1
;
1397 cp
->regno2
= regno2
;
1398 cp
->regno1_next
= lra_reg_info
[regno1
].copies
;
1399 lra_reg_info
[regno1
].copies
= cp
;
1400 cp
->regno2_next
= lra_reg_info
[regno2
].copies
;
1401 lra_reg_info
[regno2
].copies
= cp
;
1402 if (lra_dump_file
!= NULL
)
1403 fprintf (lra_dump_file
, " Creating copy r%d%sr%d@%d\n",
1404 regno1
, regno1_dest_p
? "<-" : "->", regno2
, freq
);
1407 /* Return N-th (0, 1, ...) copy. If there is no copy, return
1410 lra_get_copy (int n
)
1412 if (n
>= (int) copy_vec
.length ())
1419 /* This page contains code dealing with info about registers in
1422 /* Process X of insn UID recursively and add info (operand type is
1423 given by TYPE, flag of that it is early clobber is EARLY_CLOBBER)
1424 about registers in X to the insn DATA. */
1426 add_regs_to_insn_regno_info (lra_insn_recog_data_t data
, rtx x
, int uid
,
1427 enum op_type type
, bool early_clobber
)
1434 struct lra_insn_reg
*curr
;
1436 code
= GET_CODE (x
);
1437 mode
= GET_MODE (x
);
1439 if (GET_CODE (x
) == SUBREG
)
1442 code
= GET_CODE (x
);
1443 if (GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (x
)))
1445 mode
= GET_MODE (x
);
1446 if (GET_MODE_SIZE (mode
) > REGMODE_NATURAL_SIZE (mode
))
1453 /* Process all regs even unallocatable ones as we need info about
1454 all regs for rematerialization pass. */
1456 if (bitmap_set_bit (&lra_reg_info
[regno
].insn_bitmap
, uid
))
1458 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
1459 early_clobber
, data
->regs
);
1464 for (curr
= data
->regs
; curr
!= NULL
; curr
= curr
->next
)
1465 if (curr
->regno
== regno
)
1467 if (curr
->subreg_p
!= subreg_p
|| curr
->biggest_mode
!= mode
)
1468 /* The info can not be integrated into the found
1470 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
,
1471 subreg_p
, early_clobber
,
1475 if (curr
->type
!= type
)
1476 curr
->type
= OP_INOUT
;
1477 if (curr
->early_clobber
!= early_clobber
)
1478 curr
->early_clobber
= true;
1489 add_regs_to_insn_regno_info (data
, SET_DEST (x
), uid
, OP_OUT
, false);
1490 add_regs_to_insn_regno_info (data
, SET_SRC (x
), uid
, OP_IN
, false);
1493 /* We treat clobber of non-operand hard registers as early
1494 clobber (the behavior is expected from asm). */
1495 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), uid
, OP_OUT
, true);
1497 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
1498 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), uid
, OP_INOUT
, false);
1500 case PRE_MODIFY
: case POST_MODIFY
:
1501 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), uid
, OP_INOUT
, false);
1502 add_regs_to_insn_regno_info (data
, XEXP (x
, 1), uid
, OP_IN
, false);
1505 if ((code
!= PARALLEL
&& code
!= EXPR_LIST
) || type
!= OP_OUT
)
1506 /* Some targets place small structures in registers for return
1507 values of functions, and those registers are wrapped in
1508 PARALLEL that we may see as the destination of a SET. Here
1511 (call_insn 13 12 14 2 (set (parallel:BLK [
1512 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1514 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1515 (const_int 8 [0x8]))
1517 (call (mem:QI (symbol_ref:DI (... */
1519 fmt
= GET_RTX_FORMAT (code
);
1520 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1523 add_regs_to_insn_regno_info (data
, XEXP (x
, i
), uid
, type
, false);
1524 else if (fmt
[i
] == 'E')
1526 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1527 add_regs_to_insn_regno_info (data
, XVECEXP (x
, i
, j
), uid
,
1534 /* Return execution frequency of INSN. */
1536 get_insn_freq (rtx_insn
*insn
)
1538 basic_block bb
= BLOCK_FOR_INSN (insn
);
1540 gcc_checking_assert (bb
!= NULL
);
1541 return REG_FREQ_FROM_BB (bb
);
1544 /* Invalidate all reg info of INSN with DATA and execution frequency
1545 FREQ. Update common info about the invalidated registers. */
1547 invalidate_insn_data_regno_info (lra_insn_recog_data_t data
, rtx_insn
*insn
,
1553 struct lra_insn_reg
*ir
, *next_ir
;
1555 uid
= INSN_UID (insn
);
1556 debug_p
= DEBUG_INSN_P (insn
);
1557 for (ir
= data
->regs
; ir
!= NULL
; ir
= next_ir
)
1562 bitmap_clear_bit (&lra_reg_info
[i
].insn_bitmap
, uid
);
1563 if (i
>= FIRST_PSEUDO_REGISTER
&& ! debug_p
)
1565 lra_reg_info
[i
].nrefs
--;
1566 lra_reg_info
[i
].freq
-= freq
;
1567 lra_assert (lra_reg_info
[i
].nrefs
>= 0 && lra_reg_info
[i
].freq
>= 0);
1573 /* Invalidate all reg info of INSN. Update common info about the
1574 invalidated registers. */
1576 lra_invalidate_insn_regno_info (rtx_insn
*insn
)
1578 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn
), insn
,
1579 get_insn_freq (insn
));
1582 /* Update common reg info from reg info of insn given by its DATA and
1583 execution frequency FREQ. */
1585 setup_insn_reg_info (lra_insn_recog_data_t data
, int freq
)
1588 struct lra_insn_reg
*ir
;
1590 for (ir
= data
->regs
; ir
!= NULL
; ir
= ir
->next
)
1591 if ((i
= ir
->regno
) >= FIRST_PSEUDO_REGISTER
)
1593 lra_reg_info
[i
].nrefs
++;
1594 lra_reg_info
[i
].freq
+= freq
;
1598 /* Set up insn reg info of INSN. Update common reg info from reg info
1601 lra_update_insn_regno_info (rtx_insn
*insn
)
1604 lra_insn_recog_data_t data
;
1605 struct lra_static_insn_data
*static_data
;
1609 if (! INSN_P (insn
))
1611 data
= lra_get_insn_recog_data (insn
);
1612 static_data
= data
->insn_static_data
;
1613 freq
= get_insn_freq (insn
);
1614 invalidate_insn_data_regno_info (data
, insn
, freq
);
1615 uid
= INSN_UID (insn
);
1616 for (i
= static_data
->n_operands
- 1; i
>= 0; i
--)
1617 add_regs_to_insn_regno_info (data
, *data
->operand_loc
[i
], uid
,
1618 static_data
->operand
[i
].type
,
1619 static_data
->operand
[i
].early_clobber
);
1620 if ((code
= GET_CODE (PATTERN (insn
))) == CLOBBER
|| code
== USE
)
1621 add_regs_to_insn_regno_info (data
, XEXP (PATTERN (insn
), 0), uid
,
1622 code
== USE
? OP_IN
: OP_OUT
, false);
1624 /* On some targets call insns can refer to pseudos in memory in
1625 CALL_INSN_FUNCTION_USAGE list. Process them in order to
1626 consider their occurrences in calls for different
1627 transformations (e.g. inheritance) with given pseudos. */
1628 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1630 link
= XEXP (link
, 1))
1631 if (((code
= GET_CODE (XEXP (link
, 0))) == USE
|| code
== CLOBBER
)
1632 && MEM_P (XEXP (XEXP (link
, 0), 0)))
1633 add_regs_to_insn_regno_info (data
, XEXP (XEXP (link
, 0), 0), uid
,
1634 code
== USE
? OP_IN
: OP_OUT
, false);
1635 if (NONDEBUG_INSN_P (insn
))
1636 setup_insn_reg_info (data
, freq
);
1639 /* Return reg info of insn given by it UID. */
1640 struct lra_insn_reg
*
1641 lra_get_insn_regs (int uid
)
1643 lra_insn_recog_data_t data
;
1645 data
= get_insn_recog_data_by_uid (uid
);
1651 /* This page contains code dealing with stack of the insns which
1652 should be processed by the next constraint pass. */
1654 /* Bitmap used to put an insn on the stack only in one exemplar. */
1655 static sbitmap lra_constraint_insn_stack_bitmap
;
1657 /* The stack itself. */
1658 vec
<rtx_insn
*> lra_constraint_insn_stack
;
1660 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1661 info for INSN, otherwise only update it if INSN is not already on the
1664 lra_push_insn_1 (rtx_insn
*insn
, bool always_update
)
1666 unsigned int uid
= INSN_UID (insn
);
1668 lra_update_insn_regno_info (insn
);
1669 if (uid
>= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap
))
1670 lra_constraint_insn_stack_bitmap
=
1671 sbitmap_resize (lra_constraint_insn_stack_bitmap
, 3 * uid
/ 2, 0);
1672 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap
, uid
))
1674 bitmap_set_bit (lra_constraint_insn_stack_bitmap
, uid
);
1675 if (! always_update
)
1676 lra_update_insn_regno_info (insn
);
1677 lra_constraint_insn_stack
.safe_push (insn
);
1680 /* Put INSN on the stack. */
1682 lra_push_insn (rtx_insn
*insn
)
1684 lra_push_insn_1 (insn
, false);
1687 /* Put INSN on the stack and update its reg info. */
1689 lra_push_insn_and_update_insn_regno_info (rtx_insn
*insn
)
1691 lra_push_insn_1 (insn
, true);
1694 /* Put insn with UID on the stack. */
1696 lra_push_insn_by_uid (unsigned int uid
)
1698 lra_push_insn (lra_insn_recog_data
[uid
]->insn
);
1701 /* Take the last-inserted insns off the stack and return it. */
1705 rtx_insn
*insn
= lra_constraint_insn_stack
.pop ();
1706 bitmap_clear_bit (lra_constraint_insn_stack_bitmap
, INSN_UID (insn
));
1710 /* Return the current size of the insn stack. */
1712 lra_insn_stack_length (void)
1714 return lra_constraint_insn_stack
.length ();
1717 /* Push insns FROM to TO (excluding it) going in reverse order. */
1719 push_insns (rtx_insn
*from
, rtx_insn
*to
)
1723 if (from
== NULL_RTX
)
1725 for (insn
= from
; insn
!= to
; insn
= PREV_INSN (insn
))
1727 lra_push_insn (insn
);
1730 /* Set up sp offset for insn in range [FROM, LAST]. The offset is
1731 taken from the next BB insn after LAST or zero if there in such
1734 setup_sp_offset (rtx_insn
*from
, rtx_insn
*last
)
1736 rtx_insn
*before
= next_nonnote_insn_bb (last
);
1737 HOST_WIDE_INT offset
= (before
== NULL_RTX
|| ! INSN_P (before
)
1738 ? 0 : lra_get_insn_recog_data (before
)->sp_offset
);
1740 for (rtx_insn
*insn
= from
; insn
!= NEXT_INSN (last
); insn
= NEXT_INSN (insn
))
1741 lra_get_insn_recog_data (insn
)->sp_offset
= offset
;
1744 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1745 insns onto the stack. Print about emitting the insns with
1748 lra_process_new_insns (rtx_insn
*insn
, rtx_insn
*before
, rtx_insn
*after
,
1753 if (before
== NULL_RTX
&& after
== NULL_RTX
)
1755 if (lra_dump_file
!= NULL
)
1757 dump_insn_slim (lra_dump_file
, insn
);
1758 if (before
!= NULL_RTX
)
1760 fprintf (lra_dump_file
," %s before:\n", title
);
1761 dump_rtl_slim (lra_dump_file
, before
, NULL
, -1, 0);
1763 if (after
!= NULL_RTX
)
1765 fprintf (lra_dump_file
, " %s after:\n", title
);
1766 dump_rtl_slim (lra_dump_file
, after
, NULL
, -1, 0);
1768 fprintf (lra_dump_file
, "\n");
1770 if (before
!= NULL_RTX
)
1772 emit_insn_before (before
, insn
);
1773 push_insns (PREV_INSN (insn
), PREV_INSN (before
));
1774 setup_sp_offset (before
, PREV_INSN (insn
));
1776 if (after
!= NULL_RTX
)
1778 for (last
= after
; NEXT_INSN (last
) != NULL_RTX
; last
= NEXT_INSN (last
))
1780 emit_insn_after (after
, insn
);
1781 push_insns (last
, insn
);
1782 setup_sp_offset (after
, last
);
1788 /* Replace all references to register OLD_REGNO in *LOC with pseudo
1789 register NEW_REG. Return true if any change was made. */
1791 lra_substitute_pseudo (rtx
*loc
, int old_regno
, rtx new_reg
)
1794 bool result
= false;
1802 code
= GET_CODE (x
);
1803 if (code
== REG
&& (int) REGNO (x
) == old_regno
)
1805 machine_mode mode
= GET_MODE (*loc
);
1806 machine_mode inner_mode
= GET_MODE (new_reg
);
1808 if (mode
!= inner_mode
1809 && ! (CONST_INT_P (new_reg
) && SCALAR_INT_MODE_P (mode
)))
1811 if (GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (inner_mode
)
1812 || ! SCALAR_INT_MODE_P (inner_mode
))
1813 new_reg
= gen_rtx_SUBREG (mode
, new_reg
, 0);
1815 new_reg
= gen_lowpart_SUBREG (mode
, new_reg
);
1821 /* Scan all the operand sub-expressions. */
1822 fmt
= GET_RTX_FORMAT (code
);
1823 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1827 if (lra_substitute_pseudo (&XEXP (x
, i
), old_regno
, new_reg
))
1830 else if (fmt
[i
] == 'E')
1832 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1833 if (lra_substitute_pseudo (&XVECEXP (x
, i
, j
), old_regno
, new_reg
))
1840 /* Call lra_substitute_pseudo within an insn. This won't update the insn ptr,
1841 just the contents of the insn. */
1843 lra_substitute_pseudo_within_insn (rtx_insn
*insn
, int old_regno
, rtx new_reg
)
1846 return lra_substitute_pseudo (&loc
, old_regno
, new_reg
);
1851 /* This page contains code dealing with scratches (changing them onto
1852 pseudos and restoring them from the pseudos).
1854 We change scratches into pseudos at the beginning of LRA to
1855 simplify dealing with them (conflicts, hard register assignments).
1857 If the pseudo denoting scratch was spilled it means that we do need
1858 a hard register for it. Such pseudos are transformed back to
1859 scratches at the end of LRA. */
1861 /* Description of location of a former scratch operand. */
1864 rtx_insn
*insn
; /* Insn where the scratch was. */
1865 int nop
; /* Number of the operand which was a scratch. */
1868 typedef struct sloc
*sloc_t
;
1870 /* Locations of the former scratches. */
1871 static vec
<sloc_t
> scratches
;
1873 /* Bitmap of scratch regnos. */
1874 static bitmap_head scratch_bitmap
;
1876 /* Bitmap of scratch operands. */
1877 static bitmap_head scratch_operand_bitmap
;
1879 /* Return true if pseudo REGNO is made of SCRATCH. */
1881 lra_former_scratch_p (int regno
)
1883 return bitmap_bit_p (&scratch_bitmap
, regno
);
1886 /* Return true if the operand NOP of INSN is a former scratch. */
1888 lra_former_scratch_operand_p (rtx_insn
*insn
, int nop
)
1890 return bitmap_bit_p (&scratch_operand_bitmap
,
1891 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
) != 0;
1894 /* Register operand NOP in INSN as a former scratch. It will be
1895 changed to scratch back, if it is necessary, at the LRA end. */
1897 lra_register_new_scratch_op (rtx_insn
*insn
, int nop
)
1899 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
1900 rtx op
= *id
->operand_loc
[nop
];
1901 sloc_t loc
= XNEW (struct sloc
);
1902 lra_assert (REG_P (op
));
1905 scratches
.safe_push (loc
);
1906 bitmap_set_bit (&scratch_bitmap
, REGNO (op
));
1907 bitmap_set_bit (&scratch_operand_bitmap
,
1908 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
);
1909 add_reg_note (insn
, REG_UNUSED
, op
);
1912 /* Change scratches onto pseudos and save their location. */
1914 remove_scratches (void)
1917 bool insn_changed_p
;
1921 lra_insn_recog_data_t id
;
1922 struct lra_static_insn_data
*static_id
;
1924 scratches
.create (get_max_uid ());
1925 bitmap_initialize (&scratch_bitmap
, ®_obstack
);
1926 bitmap_initialize (&scratch_operand_bitmap
, ®_obstack
);
1927 FOR_EACH_BB_FN (bb
, cfun
)
1928 FOR_BB_INSNS (bb
, insn
)
1931 id
= lra_get_insn_recog_data (insn
);
1932 static_id
= id
->insn_static_data
;
1933 insn_changed_p
= false;
1934 for (i
= 0; i
< static_id
->n_operands
; i
++)
1935 if (GET_CODE (*id
->operand_loc
[i
]) == SCRATCH
1936 && GET_MODE (*id
->operand_loc
[i
]) != VOIDmode
)
1938 insn_changed_p
= true;
1939 *id
->operand_loc
[i
] = reg
1940 = lra_create_new_reg (static_id
->operand
[i
].mode
,
1941 *id
->operand_loc
[i
], ALL_REGS
, NULL
);
1942 lra_register_new_scratch_op (insn
, i
);
1943 if (lra_dump_file
!= NULL
)
1944 fprintf (lra_dump_file
,
1945 "Removing SCRATCH in insn #%u (nop %d)\n",
1946 INSN_UID (insn
), i
);
1949 /* Because we might use DF right after caller-saves sub-pass
1950 we need to keep DF info up to date. */
1951 df_insn_rescan (insn
);
1955 /* Changes pseudos created by function remove_scratches onto scratches. */
1957 restore_scratches (void)
1962 rtx_insn
*last
= NULL
;
1963 lra_insn_recog_data_t id
= NULL
;
1965 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
1967 if (last
!= loc
->insn
)
1970 id
= lra_get_insn_recog_data (last
);
1972 if (REG_P (*id
->operand_loc
[loc
->nop
])
1973 && ((regno
= REGNO (*id
->operand_loc
[loc
->nop
]))
1974 >= FIRST_PSEUDO_REGISTER
)
1975 && lra_get_regno_hard_regno (regno
) < 0)
1977 /* It should be only case when scratch register with chosen
1978 constraint 'X' did not get memory or hard register. */
1979 lra_assert (lra_former_scratch_p (regno
));
1980 *id
->operand_loc
[loc
->nop
]
1981 = gen_rtx_SCRATCH (GET_MODE (*id
->operand_loc
[loc
->nop
]));
1982 lra_update_dup (id
, loc
->nop
);
1983 if (lra_dump_file
!= NULL
)
1984 fprintf (lra_dump_file
, "Restoring SCRATCH in insn #%u(nop %d)\n",
1985 INSN_UID (loc
->insn
), loc
->nop
);
1988 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
1990 scratches
.release ();
1991 bitmap_clear (&scratch_bitmap
);
1992 bitmap_clear (&scratch_operand_bitmap
);
1997 #ifdef ENABLE_CHECKING
1999 /* Function checks RTL for correctness. If FINAL_P is true, it is
2000 done at the end of LRA and the check is more rigorous. */
2002 check_rtl (bool final_p
)
2007 lra_assert (! final_p
|| reload_completed
);
2008 FOR_EACH_BB_FN (bb
, cfun
)
2009 FOR_BB_INSNS (bb
, insn
)
2010 if (NONDEBUG_INSN_P (insn
)
2011 && GET_CODE (PATTERN (insn
)) != USE
2012 && GET_CODE (PATTERN (insn
)) != CLOBBER
2013 && GET_CODE (PATTERN (insn
)) != ASM_INPUT
)
2017 #ifdef ENABLED_CHECKING
2018 extract_constrain_insn (insn
);
2022 /* LRA code is based on assumption that all addresses can be
2023 correctly decomposed. LRA can generate reloads for
2024 decomposable addresses. The decomposition code checks the
2025 correctness of the addresses. So we don't need to check
2026 the addresses here. Don't call insn_invalid_p here, it can
2027 change the code at this stage. */
2028 if (recog_memoized (insn
) < 0 && asm_noperands (PATTERN (insn
)) < 0)
2029 fatal_insn_not_found (insn
);
2032 #endif /* #ifdef ENABLE_CHECKING */
2034 /* Determine if the current function has an exception receiver block
2035 that reaches the exit block via non-exceptional edges */
2037 has_nonexceptional_receiver (void)
2041 basic_block
*tos
, *worklist
, bb
;
2043 /* If we're not optimizing, then just err on the safe side. */
2047 /* First determine which blocks can reach exit via normal paths. */
2048 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
) + 1);
2050 FOR_EACH_BB_FN (bb
, cfun
)
2051 bb
->flags
&= ~BB_REACHABLE
;
2053 /* Place the exit block on our worklist. */
2054 EXIT_BLOCK_PTR_FOR_FN (cfun
)->flags
|= BB_REACHABLE
;
2055 *tos
++ = EXIT_BLOCK_PTR_FOR_FN (cfun
);
2057 /* Iterate: find everything reachable from what we've already seen. */
2058 while (tos
!= worklist
)
2062 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2063 if (e
->flags
& EDGE_ABNORMAL
)
2070 basic_block src
= e
->src
;
2072 if (!(src
->flags
& BB_REACHABLE
))
2074 src
->flags
|= BB_REACHABLE
;
2080 /* No exceptional block reached exit unexceptionally. */
2086 /* Process recursively X of INSN and add REG_INC notes if necessary. */
2088 add_auto_inc_notes (rtx_insn
*insn
, rtx x
)
2090 enum rtx_code code
= GET_CODE (x
);
2094 if (code
== MEM
&& auto_inc_p (XEXP (x
, 0)))
2096 add_reg_note (insn
, REG_INC
, XEXP (XEXP (x
, 0), 0));
2100 /* Scan all X sub-expressions. */
2101 fmt
= GET_RTX_FORMAT (code
);
2102 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2105 add_auto_inc_notes (insn
, XEXP (x
, i
));
2106 else if (fmt
[i
] == 'E')
2107 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2108 add_auto_inc_notes (insn
, XVECEXP (x
, i
, j
));
2114 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2115 We change pseudos by hard registers without notification of DF and
2116 that can make the notes obsolete. DF-infrastructure does not deal
2117 with REG_INC notes -- so we should regenerate them here. */
2119 update_inc_notes (void)
2125 FOR_EACH_BB_FN (bb
, cfun
)
2126 FOR_BB_INSNS (bb
, insn
)
2127 if (NONDEBUG_INSN_P (insn
))
2129 pnote
= ®_NOTES (insn
);
2132 if (REG_NOTE_KIND (*pnote
) == REG_DEAD
2133 || REG_NOTE_KIND (*pnote
) == REG_UNUSED
2134 || REG_NOTE_KIND (*pnote
) == REG_INC
)
2135 *pnote
= XEXP (*pnote
, 1);
2137 pnote
= &XEXP (*pnote
, 1);
2140 add_auto_inc_notes (insn
, PATTERN (insn
));
2145 /* Set to 1 while in lra. */
2146 int lra_in_progress
;
2148 /* Start of pseudo regnos before the LRA. */
2149 int lra_new_regno_start
;
2151 /* Start of reload pseudo regnos before the new spill pass. */
2152 int lra_constraint_new_regno_start
;
2154 /* Avoid spilling pseudos with regno more than the following value if
2156 int lra_bad_spill_regno_start
;
2158 /* Inheritance pseudo regnos before the new spill pass. */
2159 bitmap_head lra_inheritance_pseudos
;
2161 /* Split regnos before the new spill pass. */
2162 bitmap_head lra_split_regs
;
2164 /* Reload pseudo regnos before the new assignmnet pass which still can
2165 be spilled after the assinment pass as memory is also accepted in
2166 insns for the reload pseudos. */
2167 bitmap_head lra_optional_reload_pseudos
;
2169 /* Pseudo regnos used for subreg reloads before the new assignment
2170 pass. Such pseudos still can be spilled after the assinment
2172 bitmap_head lra_subreg_reload_pseudos
;
2174 /* File used for output of LRA debug information. */
2175 FILE *lra_dump_file
;
2177 /* True if we should try spill into registers of different classes
2178 instead of memory. */
2179 bool lra_reg_spill_p
;
2181 /* Set up value LRA_REG_SPILL_P. */
2183 setup_reg_spill_flag (void)
2187 if (targetm
.spill_class
!= NULL
)
2188 for (cl
= 0; cl
< (int) LIM_REG_CLASSES
; cl
++)
2189 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
2190 if (targetm
.spill_class ((enum reg_class
) cl
,
2191 (machine_mode
) mode
) != NO_REGS
)
2193 lra_reg_spill_p
= true;
2196 lra_reg_spill_p
= false;
2199 /* True if the current function is too big to use regular algorithms
2200 in LRA. In other words, we should use simpler and faster algorithms
2201 in LRA. It also means we should not worry about generation code
2202 for caller saves. The value is set up in IRA. */
2205 /* Major LRA entry function. F is a file should be used to dump LRA
2211 bool live_p
, scratch_p
, inserted_p
;
2215 timevar_push (TV_LRA
);
2217 /* Make sure that the last insn is a note. Some subsequent passes
2219 emit_note (NOTE_INSN_DELETED
);
2221 COPY_HARD_REG_SET (lra_no_alloc_regs
, ira_no_alloc_regs
);
2226 init_insn_recog_data ();
2228 #ifdef ENABLE_CHECKING
2229 /* Some quick check on RTL generated by previous passes. */
2233 lra_in_progress
= 1;
2235 lra_live_range_iter
= lra_coalesce_iter
= lra_constraint_iter
= 0;
2236 lra_assignment_iter
= lra_assignment_iter_after_spill
= 0;
2237 lra_inheritance_iter
= lra_undo_inheritance_iter
= 0;
2238 lra_rematerialization_iter
= 0;
2240 setup_reg_spill_flag ();
2242 /* Function remove_scratches can creates new pseudos for clobbers --
2243 so set up lra_constraint_new_regno_start before its call to
2244 permit changing reg classes for pseudos created by this
2246 lra_constraint_new_regno_start
= lra_new_regno_start
= max_reg_num ();
2247 lra_bad_spill_regno_start
= INT_MAX
;
2248 remove_scratches ();
2249 scratch_p
= lra_constraint_new_regno_start
!= max_reg_num ();
2251 /* A function that has a non-local label that can reach the exit
2252 block via non-exceptional paths must save all call-saved
2254 if (cfun
->has_nonlocal_label
&& has_nonexceptional_receiver ())
2255 crtl
->saves_all_registers
= 1;
2257 if (crtl
->saves_all_registers
)
2258 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2259 if (! call_used_regs
[i
] && ! fixed_regs
[i
] && ! LOCAL_REGNO (i
))
2260 df_set_regs_ever_live (i
, true);
2262 /* We don't DF from now and avoid its using because it is to
2263 expensive when a lot of RTL changes are made. */
2264 df_set_flags (DF_NO_INSN_RESCAN
);
2265 lra_constraint_insn_stack
.create (get_max_uid ());
2266 lra_constraint_insn_stack_bitmap
= sbitmap_alloc (get_max_uid ());
2267 bitmap_clear (lra_constraint_insn_stack_bitmap
);
2268 lra_live_ranges_init ();
2269 lra_constraints_init ();
2270 lra_curr_reload_num
= 0;
2271 push_insns (get_last_insn (), NULL
);
2272 /* It is needed for the 1st coalescing. */
2273 bitmap_initialize (&lra_inheritance_pseudos
, ®_obstack
);
2274 bitmap_initialize (&lra_split_regs
, ®_obstack
);
2275 bitmap_initialize (&lra_optional_reload_pseudos
, ®_obstack
);
2276 bitmap_initialize (&lra_subreg_reload_pseudos
, ®_obstack
);
2278 if (get_frame_size () != 0 && crtl
->stack_alignment_needed
)
2279 /* If we have a stack frame, we must align it now. The stack size
2280 may be a part of the offset computation for register
2282 assign_stack_local (BLKmode
, 0, crtl
->stack_alignment_needed
);
2288 /* We should try to assign hard registers to scratches even
2289 if there were no RTL transformations in
2291 if (! lra_constraints (lra_constraint_iter
== 0)
2292 && (lra_constraint_iter
> 1
2293 || (! scratch_p
&& ! caller_save_needed
)))
2295 /* Constraint transformations may result in that eliminable
2296 hard regs become uneliminable and pseudos which use them
2297 should be spilled. It is better to do it before pseudo
2300 For example, rs6000 can make
2301 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2302 to use a constant pool. */
2303 lra_eliminate (false, false);
2304 /* Do inheritance only for regular algorithms. */
2310 lra_clear_live_ranges ();
2311 /* As a side-effect of lra_create_live_ranges, we calculate
2312 actual_call_used_reg_set, which is needed during
2314 lra_create_live_ranges (true, true);
2320 lra_clear_live_ranges ();
2321 /* We need live ranges for lra_assign -- so build them. But
2322 don't remove dead insns or change global live info as we
2323 can undo inheritance transformations after inheritance
2324 pseudo assigning. */
2325 lra_create_live_ranges (true, false);
2327 /* If we don't spill non-reload and non-inheritance pseudos,
2328 there is no sense to run memory-memory move coalescing.
2329 If inheritance pseudos were spilled, the memory-memory
2330 moves involving them will be removed by pass undoing
2336 bool spill_p
= !lra_assign ();
2338 if (lra_undo_inheritance ())
2344 lra_create_live_ranges (true, true);
2347 if (lra_coalesce ())
2351 lra_clear_live_ranges ();
2354 /* Don't clear optional reloads bitmap until all constraints are
2355 satisfied as we need to differ them from regular reloads. */
2356 bitmap_clear (&lra_optional_reload_pseudos
);
2357 bitmap_clear (&lra_subreg_reload_pseudos
);
2358 bitmap_clear (&lra_inheritance_pseudos
);
2359 bitmap_clear (&lra_split_regs
);
2362 /* We need full live info for spilling pseudos into
2363 registers instead of memory. */
2364 lra_create_live_ranges (lra_reg_spill_p
, true);
2367 /* We should check necessity for spilling here as the above live
2368 range pass can remove spilled pseudos. */
2369 if (! lra_need_for_spills_p ())
2371 /* Now we know what pseudos should be spilled. Try to
2372 rematerialize them first. */
2375 /* We need full live info -- see the comment above. */
2376 lra_create_live_ranges (lra_reg_spill_p
, true);
2378 if (! lra_need_for_spills_p ())
2382 /* Assignment of stack slots changes elimination offsets for
2383 some eliminations. So update the offsets here. */
2384 lra_eliminate (false, false);
2385 lra_constraint_new_regno_start
= max_reg_num ();
2386 if (lra_bad_spill_regno_start
== INT_MAX
2387 && lra_inheritance_iter
> LRA_MAX_INHERITANCE_PASSES
2388 && lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
2389 /* After switching off inheritance and rematerialization
2390 passes, avoid spilling reload pseudos will be created to
2391 prevent LRA cycling in some complicated cases. */
2392 lra_bad_spill_regno_start
= lra_constraint_new_regno_start
;
2393 lra_assignment_iter_after_spill
= 0;
2395 restore_scratches ();
2396 lra_eliminate (true, false);
2397 lra_final_code_change ();
2398 lra_in_progress
= 0;
2400 lra_clear_live_ranges ();
2401 lra_live_ranges_finish ();
2402 lra_constraints_finish ();
2404 sbitmap_free (lra_constraint_insn_stack_bitmap
);
2405 lra_constraint_insn_stack
.release ();
2406 finish_insn_recog_data ();
2407 regstat_free_n_sets_and_refs ();
2409 reload_completed
= 1;
2410 update_inc_notes ();
2412 inserted_p
= fixup_abnormal_edges ();
2414 /* We've possibly turned single trapping insn into multiple ones. */
2415 if (cfun
->can_throw_non_call_exceptions
)
2418 blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
2419 bitmap_ones (blocks
);
2420 find_many_sub_basic_blocks (blocks
);
2421 sbitmap_free (blocks
);
2425 commit_edge_insertions ();
2427 /* Replacing pseudos with their memory equivalents might have
2428 created shared rtx. Subsequent passes would get confused
2429 by this, so unshare everything here. */
2430 unshare_all_rtl_again (get_insns ());
2432 #ifdef ENABLE_CHECKING
2436 timevar_pop (TV_LRA
);
2439 /* Called once per compiler to initialize LRA data once. */
2441 lra_init_once (void)
2443 init_insn_code_data_once ();
2446 /* Called once per compiler to finish LRA data which are initialize
2449 lra_finish_once (void)
2451 finish_insn_code_data_once ();