1 /* LRA (local register allocator) driver and LRA utilities.
2 Copyright (C) 2010-2019 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 /* The Local Register Allocator (LRA) is a replacement of former
23 reload pass. It is focused to simplify code solving the reload
24 pass tasks, to make the code maintenance easier, and to implement new
25 perspective optimizations.
27 The major LRA design solutions are:
28 o division small manageable, separated sub-tasks
29 o reflection of all transformations and decisions in RTL as more
31 o insn constraints as a primary source of the info (minimizing
32 number of target-depended macros/hooks)
34 In brief LRA works by iterative insn process with the final goal is
35 to satisfy all insn and address constraints:
36 o New reload insns (in brief reloads) and reload pseudos might be
38 o Some pseudos might be spilled to assign hard registers to
40 o Recalculating spilled pseudo values (rematerialization);
41 o Changing spilled pseudos to stack memory or their equivalences;
42 o Allocation stack memory changes the address displacement and
43 new iteration is needed.
45 Here is block diagram of LRA passes:
47 ------------------------
48 --------------- | Undo inheritance for | ---------------
49 | Memory-memory | | spilled pseudos, | | New (and old) |
50 | move coalesce |<---| splits for pseudos got |<-- | pseudos |
51 --------------- | the same hard regs, | | assignment |
52 Start | | and optional reloads | ---------------
53 | | ------------------------ ^
54 V | ---------------- |
55 ----------- V | Update virtual | |
56 | Remove |----> ------------>| register | |
57 | scratches | ^ | displacements | |
58 ----------- | ---------------- |
61 | ------------ pseudos -------------------
62 | |Constraints:| or insns | Inheritance/split |
63 | | RTL |--------->| transformations |
64 | | transfor- | | in EBB scope |
65 | substi- | mations | -------------------
66 | tutions ------------
69 | Spilled pseudo | -------------------
70 | to memory |<----| Rematerialization |
71 | substitution | -------------------
75 -------------------------
76 | Hard regs substitution, |
77 | devirtalization, and |------> Finish
78 | restoring scratches got |
80 -------------------------
82 To speed up the process:
83 o We process only insns affected by changes on previous
85 o We don't use DFA-infrastructure because it results in much slower
86 compiler speed than a special IR described below does;
87 o We use a special insn representation for quick access to insn
88 info which is always *synchronized* with the current RTL;
89 o Insn IR is minimized by memory. It is divided on three parts:
90 o one specific for each insn in RTL (only operand locations);
91 o one common for all insns in RTL with the same insn code
92 (different operand attributes from machine descriptions);
93 o one oriented for maintenance of live info (list of pseudos).
95 o all insns where the pseudo is referenced;
96 o live info (conflicting hard regs, live ranges, # of
98 o data used for assigning (preferred hard regs, costs etc).
100 This file contains LRA driver, LRA utility functions and data, and
101 code for dealing with scratches. */
105 #include "coretypes.h"
112 #include "memmodel.h"
120 #include "cfgbuild.h"
123 #include "print-rtl.h"
125 /* Dump bitmap SET with TITLE and BB INDEX. */
127 lra_dump_bitmap_with_title (const char *title
, bitmap set
, int index
)
132 static const int max_nums_on_line
= 10;
134 if (bitmap_empty_p (set
))
136 fprintf (lra_dump_file
, " %s %d:", title
, index
);
137 fprintf (lra_dump_file
, "\n");
138 count
= max_nums_on_line
+ 1;
139 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
141 if (count
> max_nums_on_line
)
143 fprintf (lra_dump_file
, "\n ");
146 fprintf (lra_dump_file
, " %4u", i
);
149 fprintf (lra_dump_file
, "\n");
152 /* Hard registers currently not available for allocation. It can
153 changed after some hard registers become not eliminable. */
154 HARD_REG_SET lra_no_alloc_regs
;
156 static int get_new_reg_value (void);
157 static void expand_reg_info (void);
158 static void invalidate_insn_recog_data (int);
159 static int get_insn_freq (rtx_insn
*);
160 static void invalidate_insn_data_regno_info (lra_insn_recog_data_t
,
162 static void remove_scratches_1 (rtx_insn
*);
164 /* Expand all regno related info needed for LRA. */
166 expand_reg_data (int old
)
170 ira_expand_reg_equiv ();
171 for (int i
= (int) max_reg_num () - 1; i
>= old
; i
--)
172 lra_change_class (i
, ALL_REGS
, " Set", true);
175 /* Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL
176 or of VOIDmode, use MD_MODE for the new reg. Initialize its
177 register class to RCLASS. Print message about assigning class
178 RCLASS containing new register name TITLE unless it is NULL. Use
179 attributes of ORIGINAL if it is a register. The created register
180 will have unique held value. */
182 lra_create_new_reg_with_unique_value (machine_mode md_mode
, rtx original
,
183 enum reg_class rclass
, const char *title
)
188 if (original
== NULL_RTX
|| (mode
= GET_MODE (original
)) == VOIDmode
)
190 lra_assert (mode
!= VOIDmode
);
191 new_reg
= gen_reg_rtx (mode
);
192 if (original
== NULL_RTX
|| ! REG_P (original
))
194 if (lra_dump_file
!= NULL
)
195 fprintf (lra_dump_file
, " Creating newreg=%i", REGNO (new_reg
));
199 if (ORIGINAL_REGNO (original
) >= FIRST_PSEUDO_REGISTER
)
200 ORIGINAL_REGNO (new_reg
) = ORIGINAL_REGNO (original
);
201 REG_USERVAR_P (new_reg
) = REG_USERVAR_P (original
);
202 REG_POINTER (new_reg
) = REG_POINTER (original
);
203 REG_ATTRS (new_reg
) = REG_ATTRS (original
);
204 if (lra_dump_file
!= NULL
)
205 fprintf (lra_dump_file
, " Creating newreg=%i from oldreg=%i",
206 REGNO (new_reg
), REGNO (original
));
208 if (lra_dump_file
!= NULL
)
211 fprintf (lra_dump_file
, ", assigning class %s to%s%s r%d",
212 reg_class_names
[rclass
], *title
== '\0' ? "" : " ",
213 title
, REGNO (new_reg
));
214 fprintf (lra_dump_file
, "\n");
216 expand_reg_data (max_reg_num ());
217 setup_reg_classes (REGNO (new_reg
), rclass
, NO_REGS
, rclass
);
221 /* Analogous to the previous function but also inherits value of
224 lra_create_new_reg (machine_mode md_mode
, rtx original
,
225 enum reg_class rclass
, const char *title
)
230 = lra_create_new_reg_with_unique_value (md_mode
, original
, rclass
, title
);
231 if (original
!= NULL_RTX
&& REG_P (original
))
232 lra_assign_reg_val (REGNO (original
), REGNO (new_reg
));
236 /* Set up for REGNO unique hold value. */
238 lra_set_regno_unique_value (int regno
)
240 lra_reg_info
[regno
].val
= get_new_reg_value ();
243 /* Invalidate INSN related info used by LRA. The info should never be
246 lra_invalidate_insn_data (rtx_insn
*insn
)
248 lra_invalidate_insn_regno_info (insn
);
249 invalidate_insn_recog_data (INSN_UID (insn
));
252 /* Mark INSN deleted and invalidate the insn related info used by
255 lra_set_insn_deleted (rtx_insn
*insn
)
257 lra_invalidate_insn_data (insn
);
258 SET_INSN_DELETED (insn
);
261 /* Delete an unneeded INSN and any previous insns who sole purpose is
262 loading data that is dead in INSN. */
264 lra_delete_dead_insn (rtx_insn
*insn
)
266 rtx_insn
*prev
= prev_real_insn (insn
);
269 /* If the previous insn sets a register that dies in our insn,
271 if (prev
&& GET_CODE (PATTERN (prev
)) == SET
272 && (prev_dest
= SET_DEST (PATTERN (prev
)), REG_P (prev_dest
))
273 && reg_mentioned_p (prev_dest
, PATTERN (insn
))
274 && find_regno_note (insn
, REG_DEAD
, REGNO (prev_dest
))
275 && ! side_effects_p (SET_SRC (PATTERN (prev
))))
276 lra_delete_dead_insn (prev
);
278 lra_set_insn_deleted (insn
);
281 /* Emit insn x = y + z. Return NULL if we failed to do it.
282 Otherwise, return the insn. We don't use gen_add3_insn as it might
285 emit_add3_insn (rtx x
, rtx y
, rtx z
)
289 last
= get_last_insn ();
291 if (have_addptr3_insn (x
, y
, z
))
293 rtx_insn
*insn
= gen_addptr3_insn (x
, y
, z
);
295 /* If the target provides an "addptr" pattern it hopefully does
296 for a reason. So falling back to the normal add would be
298 lra_assert (insn
!= NULL_RTX
);
303 rtx_insn
*insn
= emit_insn (gen_rtx_SET (x
, gen_rtx_PLUS (GET_MODE (y
),
305 if (recog_memoized (insn
) < 0)
307 delete_insns_since (last
);
313 /* Emit insn x = x + y. Return the insn. We use gen_add2_insn as the
316 emit_add2_insn (rtx x
, rtx y
)
318 rtx_insn
*insn
= emit_add3_insn (x
, x
, y
);
319 if (insn
== NULL_RTX
)
321 insn
= gen_add2_insn (x
, y
);
322 if (insn
!= NULL_RTX
)
328 /* Target checks operands through operand predicates to recognize an
329 insn. We should have a special precaution to generate add insns
330 which are frequent results of elimination.
332 Emit insns for x = y + z. X can be used to store intermediate
333 values and should be not in Y and Z when we use X to store an
334 intermediate value. Y + Z should form [base] [+ index[ * scale]] [
335 + disp] where base and index are registers, disp and scale are
336 constants. Y should contain base if it is present, Z should
337 contain disp if any. index[*scale] can be part of Y or Z. */
339 lra_emit_add (rtx x
, rtx y
, rtx z
)
343 rtx a1
, a2
, base
, index
, disp
, scale
, index_scale
;
346 rtx_insn
*add3_insn
= emit_add3_insn (x
, y
, z
);
347 old
= max_reg_num ();
348 if (add3_insn
!= NULL
)
352 disp
= a2
= NULL_RTX
;
353 if (GET_CODE (y
) == PLUS
)
367 index_scale
= scale
= NULL_RTX
;
368 if (GET_CODE (a1
) == MULT
)
371 index
= XEXP (a1
, 0);
372 scale
= XEXP (a1
, 1);
375 else if (a2
!= NULL_RTX
&& GET_CODE (a2
) == MULT
)
378 index
= XEXP (a2
, 0);
379 scale
= XEXP (a2
, 1);
387 if ((base
!= NULL_RTX
&& ! (REG_P (base
) || GET_CODE (base
) == SUBREG
))
388 || (index
!= NULL_RTX
389 && ! (REG_P (index
) || GET_CODE (index
) == SUBREG
))
390 || (disp
!= NULL_RTX
&& ! CONSTANT_P (disp
))
391 || (scale
!= NULL_RTX
&& ! CONSTANT_P (scale
)))
393 /* Probably we have no 3 op add. Last chance is to use 2-op
394 add insn. To succeed, don't move Z to X as an address
395 segment always comes in Y. Otherwise, we might fail when
396 adding the address segment to register. */
397 lra_assert (x
!= y
&& x
!= z
);
398 emit_move_insn (x
, y
);
399 rtx_insn
*insn
= emit_add2_insn (x
, z
);
400 lra_assert (insn
!= NULL_RTX
);
404 if (index_scale
== NULL_RTX
)
406 if (disp
== NULL_RTX
)
408 /* Generate x = index_scale; x = x + base. */
409 lra_assert (index_scale
!= NULL_RTX
&& base
!= NULL_RTX
);
410 emit_move_insn (x
, index_scale
);
411 rtx_insn
*insn
= emit_add2_insn (x
, base
);
412 lra_assert (insn
!= NULL_RTX
);
414 else if (scale
== NULL_RTX
)
416 /* Try x = base + disp. */
417 lra_assert (base
!= NULL_RTX
);
418 last
= get_last_insn ();
419 rtx_insn
*move_insn
=
420 emit_move_insn (x
, gen_rtx_PLUS (GET_MODE (base
), base
, disp
));
421 if (recog_memoized (move_insn
) < 0)
423 delete_insns_since (last
);
424 /* Generate x = disp; x = x + base. */
425 emit_move_insn (x
, disp
);
426 rtx_insn
*add2_insn
= emit_add2_insn (x
, base
);
427 lra_assert (add2_insn
!= NULL_RTX
);
429 /* Generate x = x + index. */
430 if (index
!= NULL_RTX
)
432 rtx_insn
*insn
= emit_add2_insn (x
, index
);
433 lra_assert (insn
!= NULL_RTX
);
438 /* Try x = index_scale; x = x + disp; x = x + base. */
439 last
= get_last_insn ();
440 rtx_insn
*move_insn
= emit_move_insn (x
, index_scale
);
442 if (recog_memoized (move_insn
) >= 0)
444 rtx_insn
*insn
= emit_add2_insn (x
, disp
);
445 if (insn
!= NULL_RTX
)
447 if (base
== NULL_RTX
)
451 insn
= emit_add2_insn (x
, base
);
452 if (insn
!= NULL_RTX
)
461 delete_insns_since (last
);
462 /* Generate x = disp; x = x + base; x = x + index_scale. */
463 emit_move_insn (x
, disp
);
464 if (base
!= NULL_RTX
)
466 insn
= emit_add2_insn (x
, base
);
467 lra_assert (insn
!= NULL_RTX
);
469 insn
= emit_add2_insn (x
, index_scale
);
470 lra_assert (insn
!= NULL_RTX
);
475 /* Functions emit_... can create pseudos -- so expand the pseudo
477 if (old
!= max_reg_num ())
478 expand_reg_data (old
);
481 /* The number of emitted reload insns so far. */
482 int lra_curr_reload_num
;
484 /* Emit x := y, processing special case when y = u + v or y = u + v *
485 scale + w through emit_add (Y can be an address which is base +
486 index reg * scale + displacement in general case). X may be used
487 as intermediate result therefore it should be not in Y. */
489 lra_emit_move (rtx x
, rtx y
)
493 if (GET_CODE (y
) != PLUS
)
495 if (rtx_equal_p (x
, y
))
497 old
= max_reg_num ();
498 rtx_insn
*insn
= emit_move_insn (x
, y
);
499 /* The move pattern may require scratch registers, so convert them
500 into real registers now. */
501 if (insn
!= NULL_RTX
)
502 remove_scratches_1 (insn
);
504 lra_reg_info
[ORIGINAL_REGNO (x
)].last_reload
= ++lra_curr_reload_num
;
505 /* Function emit_move can create pseudos -- so expand the pseudo
507 if (old
!= max_reg_num ())
508 expand_reg_data (old
);
511 lra_emit_add (x
, XEXP (y
, 0), XEXP (y
, 1));
514 /* Update insn operands which are duplication of operands whose
515 numbers are in array of NOPS (with end marker -1). The insn is
516 represented by its LRA internal representation ID. */
518 lra_update_dups (lra_insn_recog_data_t id
, signed char *nops
)
521 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
523 for (i
= 0; i
< static_id
->n_dups
; i
++)
524 for (j
= 0; (nop
= nops
[j
]) >= 0; j
++)
525 if (static_id
->dup_num
[i
] == nop
)
526 *id
->dup_loc
[i
] = *id
->operand_loc
[nop
];
531 /* This page contains code dealing with info about registers in the
534 /* Pools for insn reg info. */
535 object_allocator
<lra_insn_reg
> lra_insn_reg_pool ("insn regs");
537 /* Create LRA insn related info about a reference to REGNO in INSN
538 with TYPE (in/out/inout), biggest reference mode MODE, flag that it
539 is reference through subreg (SUBREG_P), and reference to the next
540 insn reg info (NEXT). If REGNO can be early clobbered,
541 alternatives in which it can be early clobbered are given by
542 EARLY_CLOBBER_ALTS. CLOBBER_HIGH marks if reference is a clobber
544 static struct lra_insn_reg
*
545 new_insn_reg (rtx_insn
*insn
, int regno
, enum op_type type
,
546 machine_mode mode
, bool subreg_p
,
547 alternative_mask early_clobber_alts
,
548 struct lra_insn_reg
*next
, bool clobber_high
)
550 lra_insn_reg
*ir
= lra_insn_reg_pool
.allocate ();
552 ir
->biggest_mode
= mode
;
553 if (NONDEBUG_INSN_P (insn
)
554 && partial_subreg_p (lra_reg_info
[regno
].biggest_mode
, mode
))
555 lra_reg_info
[regno
].biggest_mode
= mode
;
556 ir
->subreg_p
= subreg_p
;
557 ir
->early_clobber_alts
= early_clobber_alts
;
558 ir
->clobber_high
= clobber_high
;
564 /* Free insn reg info list IR. */
566 free_insn_regs (struct lra_insn_reg
*ir
)
568 struct lra_insn_reg
*next_ir
;
570 for (; ir
!= NULL
; ir
= next_ir
)
573 lra_insn_reg_pool
.remove (ir
);
577 /* Finish pool for insn reg info. */
579 finish_insn_regs (void)
581 lra_insn_reg_pool
.release ();
586 /* This page contains code dealing LRA insn info (or in other words
587 LRA internal insn representation). */
589 /* Map INSN_CODE -> the static insn data. This info is valid during
590 all translation unit. */
591 struct lra_static_insn_data
*insn_code_data
[NUM_INSN_CODES
];
593 /* Debug insns are represented as a special insn with one input
594 operand which is RTL expression in var_location. */
596 /* The following data are used as static insn operand data for all
597 debug insns. If structure lra_operand_data is changed, the
598 initializer should be changed too. */
599 static struct lra_operand_data debug_operand_data
=
601 NULL
, /* alternative */
602 0, /* early_clobber_alts */
603 E_VOIDmode
, /* We are not interesting in the operand mode. */
608 /* The following data are used as static insn data for all debug
609 bind insns. If structure lra_static_insn_data is changed, the
610 initializer should be changed too. */
611 static struct lra_static_insn_data debug_bind_static_data
=
614 0, /* Duplication operands #. */
615 -1, /* Commutative operand #. */
616 1, /* Operands #. There is only one operand which is debug RTL
618 0, /* Duplications #. */
619 0, /* Alternatives #. We are not interesting in alternatives
620 because we does not proceed debug_insns for reloads. */
621 NULL
, /* Hard registers referenced in machine description. */
622 NULL
/* Descriptions of operands in alternatives. */
625 /* The following data are used as static insn data for all debug
626 marker insns. If structure lra_static_insn_data is changed, the
627 initializer should be changed too. */
628 static struct lra_static_insn_data debug_marker_static_data
=
631 0, /* Duplication operands #. */
632 -1, /* Commutative operand #. */
633 0, /* Operands #. There isn't any operand. */
634 0, /* Duplications #. */
635 0, /* Alternatives #. We are not interesting in alternatives
636 because we does not proceed debug_insns for reloads. */
637 NULL
, /* Hard registers referenced in machine description. */
638 NULL
/* Descriptions of operands in alternatives. */
641 /* Called once per compiler work to initialize some LRA data related
644 init_insn_code_data_once (void)
646 memset (insn_code_data
, 0, sizeof (insn_code_data
));
649 /* Called once per compiler work to finalize some LRA data related to
652 finish_insn_code_data_once (void)
654 for (unsigned int i
= 0; i
< NUM_INSN_CODES
; i
++)
656 if (insn_code_data
[i
] != NULL
)
657 free (insn_code_data
[i
]);
661 /* Return static insn data, allocate and setup if necessary. Although
662 dup_num is static data (it depends only on icode), to set it up we
663 need to extract insn first. So recog_data should be valid for
664 normal insn (ICODE >= 0) before the call. */
665 static struct lra_static_insn_data
*
666 get_static_insn_data (int icode
, int nop
, int ndup
, int nalt
)
668 struct lra_static_insn_data
*data
;
671 lra_assert (icode
< (int) NUM_INSN_CODES
);
672 if (icode
>= 0 && (data
= insn_code_data
[icode
]) != NULL
)
674 lra_assert (nop
>= 0 && ndup
>= 0 && nalt
>= 0);
675 n_bytes
= sizeof (struct lra_static_insn_data
)
676 + sizeof (struct lra_operand_data
) * nop
677 + sizeof (int) * ndup
;
678 data
= XNEWVAR (struct lra_static_insn_data
, n_bytes
);
679 data
->operand_alternative
= NULL
;
680 data
->n_operands
= nop
;
682 data
->n_alternatives
= nalt
;
683 data
->operand
= ((struct lra_operand_data
*)
684 ((char *) data
+ sizeof (struct lra_static_insn_data
)));
685 data
->dup_num
= ((int *) ((char *) data
->operand
686 + sizeof (struct lra_operand_data
) * nop
));
691 insn_code_data
[icode
] = data
;
692 for (i
= 0; i
< nop
; i
++)
694 data
->operand
[i
].constraint
695 = insn_data
[icode
].operand
[i
].constraint
;
696 data
->operand
[i
].mode
= insn_data
[icode
].operand
[i
].mode
;
697 data
->operand
[i
].strict_low
= insn_data
[icode
].operand
[i
].strict_low
;
698 data
->operand
[i
].is_operator
699 = insn_data
[icode
].operand
[i
].is_operator
;
700 data
->operand
[i
].type
701 = (data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
702 : data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
704 data
->operand
[i
].is_address
= false;
706 for (i
= 0; i
< ndup
; i
++)
707 data
->dup_num
[i
] = recog_data
.dup_num
[i
];
712 /* The current length of the following array. */
713 int lra_insn_recog_data_len
;
715 /* Map INSN_UID -> the insn recog data (NULL if unknown). */
716 lra_insn_recog_data_t
*lra_insn_recog_data
;
718 /* Initialize LRA data about insns. */
720 init_insn_recog_data (void)
722 lra_insn_recog_data_len
= 0;
723 lra_insn_recog_data
= NULL
;
726 /* Expand, if necessary, LRA data about insns. */
728 check_and_expand_insn_recog_data (int index
)
732 if (lra_insn_recog_data_len
> index
)
734 old
= lra_insn_recog_data_len
;
735 lra_insn_recog_data_len
= index
* 3 / 2 + 1;
736 lra_insn_recog_data
= XRESIZEVEC (lra_insn_recog_data_t
,
738 lra_insn_recog_data_len
);
739 for (i
= old
; i
< lra_insn_recog_data_len
; i
++)
740 lra_insn_recog_data
[i
] = NULL
;
743 /* Finish LRA DATA about insn. */
745 free_insn_recog_data (lra_insn_recog_data_t data
)
747 if (data
->operand_loc
!= NULL
)
748 free (data
->operand_loc
);
749 if (data
->dup_loc
!= NULL
)
750 free (data
->dup_loc
);
751 if (data
->arg_hard_regs
!= NULL
)
752 free (data
->arg_hard_regs
);
753 if (data
->icode
< 0 && NONDEBUG_INSN_P (data
->insn
))
755 if (data
->insn_static_data
->operand_alternative
!= NULL
)
756 free (const_cast <operand_alternative
*>
757 (data
->insn_static_data
->operand_alternative
));
758 free_insn_regs (data
->insn_static_data
->hard_regs
);
759 free (data
->insn_static_data
);
761 free_insn_regs (data
->regs
);
766 /* Pools for copies. */
767 static object_allocator
<lra_copy
> lra_copy_pool ("lra copies");
769 /* Finish LRA data about all insns. */
771 finish_insn_recog_data (void)
774 lra_insn_recog_data_t data
;
776 for (i
= 0; i
< lra_insn_recog_data_len
; i
++)
777 if ((data
= lra_insn_recog_data
[i
]) != NULL
)
778 free_insn_recog_data (data
);
780 lra_copy_pool
.release ();
781 lra_insn_reg_pool
.release ();
782 free (lra_insn_recog_data
);
785 /* Setup info about operands in alternatives of LRA DATA of insn. */
787 setup_operand_alternative (lra_insn_recog_data_t data
,
788 const operand_alternative
*op_alt
)
791 int icode
= data
->icode
;
792 struct lra_static_insn_data
*static_data
= data
->insn_static_data
;
794 static_data
->commutative
= -1;
795 nop
= static_data
->n_operands
;
796 nalt
= static_data
->n_alternatives
;
797 static_data
->operand_alternative
= op_alt
;
798 for (i
= 0; i
< nop
; i
++)
800 static_data
->operand
[i
].early_clobber_alts
= 0;
801 static_data
->operand
[i
].is_address
= false;
802 if (static_data
->operand
[i
].constraint
[0] == '%')
804 /* We currently only support one commutative pair of operands. */
805 if (static_data
->commutative
< 0)
806 static_data
->commutative
= i
;
808 lra_assert (icode
< 0); /* Asm */
809 /* The last operand should not be marked commutative. */
810 lra_assert (i
!= nop
- 1);
813 for (j
= 0; j
< nalt
; j
++)
814 for (i
= 0; i
< nop
; i
++, op_alt
++)
816 if (op_alt
->earlyclobber
)
817 static_data
->operand
[i
].early_clobber_alts
|= (alternative_mask
) 1 << j
;
818 static_data
->operand
[i
].is_address
|= op_alt
->is_address
;
822 /* Recursively process X and collect info about registers, which are
823 not the insn operands, in X with TYPE (in/out/inout) and flag that
824 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
825 to LIST. X is a part of insn given by DATA. Return the result
826 list. CLOBBER_HIGH marks if X is a clobber high. */
827 static struct lra_insn_reg
*
828 collect_non_operand_hard_regs (rtx_insn
*insn
, rtx
*x
,
829 lra_insn_recog_data_t data
,
830 struct lra_insn_reg
*list
,
831 enum op_type type
, bool early_clobber
,
834 int i
, j
, regno
, last
;
837 struct lra_insn_reg
*curr
;
839 enum rtx_code code
= GET_CODE (op
);
840 const char *fmt
= GET_RTX_FORMAT (code
);
842 for (i
= 0; i
< data
->insn_static_data
->n_operands
; i
++)
843 if (! data
->insn_static_data
->operand
[i
].is_operator
844 && x
== data
->operand_loc
[i
])
845 /* It is an operand loc. Stop here. */
847 for (i
= 0; i
< data
->insn_static_data
->n_dups
; i
++)
848 if (x
== data
->dup_loc
[i
])
849 /* It is a dup loc. Stop here. */
851 mode
= GET_MODE (op
);
855 mode
= wider_subreg_mode (op
);
856 if (read_modify_subreg_p (op
))
858 op
= SUBREG_REG (op
);
859 code
= GET_CODE (op
);
863 if ((regno
= REGNO (op
)) >= FIRST_PSEUDO_REGISTER
)
865 /* Process all regs even unallocatable ones as we need info
866 about all regs for rematerialization pass. */
867 for (last
= end_hard_regno (mode
, regno
); regno
< last
; regno
++)
869 for (curr
= list
; curr
!= NULL
; curr
= curr
->next
)
870 if (curr
->regno
== regno
&& curr
->subreg_p
== subreg_p
871 && curr
->biggest_mode
== mode
)
873 if (curr
->type
!= type
)
874 curr
->type
= OP_INOUT
;
876 curr
->early_clobber_alts
= ALL_ALTERNATIVES
;
881 /* This is a new hard regno or the info cannot be
882 integrated into the found structure. */
886 /* This clobber is to inform popping floating
888 && ! (FIRST_STACK_REG
<= regno
889 && regno
<= LAST_STACK_REG
));
891 list
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
892 early_clobber
? ALL_ALTERNATIVES
: 0, list
,
901 list
= collect_non_operand_hard_regs (insn
, &SET_DEST (op
), data
,
902 list
, OP_OUT
, false, false);
903 list
= collect_non_operand_hard_regs (insn
, &SET_SRC (op
), data
,
904 list
, OP_IN
, false, false);
907 /* We treat clobber of non-operand hard registers as early clobber. */
908 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
909 list
, OP_OUT
, true, false);
912 /* Clobber high should always span exactly one register. */
913 gcc_assert (REG_NREGS (XEXP (op
, 0)) == 1);
914 /* We treat clobber of non-operand hard registers as early clobber. */
915 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
916 list
, OP_OUT
, true, true);
918 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
919 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
920 list
, OP_INOUT
, false, false);
922 case PRE_MODIFY
: case POST_MODIFY
:
923 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
924 list
, OP_INOUT
, false, false);
925 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 1), data
,
926 list
, OP_IN
, false, false);
929 fmt
= GET_RTX_FORMAT (code
);
930 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
933 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, i
), data
,
934 list
, OP_IN
, false, false);
935 else if (fmt
[i
] == 'E')
936 for (j
= XVECLEN (op
, i
) - 1; j
>= 0; j
--)
937 list
= collect_non_operand_hard_regs (insn
, &XVECEXP (op
, i
, j
),
938 data
, list
, OP_IN
, false,
945 /* Set up and return info about INSN. Set up the info if it is not set up
947 lra_insn_recog_data_t
948 lra_set_insn_recog_data (rtx_insn
*insn
)
950 lra_insn_recog_data_t data
;
953 unsigned int uid
= INSN_UID (insn
);
954 struct lra_static_insn_data
*insn_static_data
;
956 check_and_expand_insn_recog_data (uid
);
957 if (DEBUG_INSN_P (insn
))
961 icode
= INSN_CODE (insn
);
963 /* It might be a new simple insn which is not recognized yet. */
964 INSN_CODE (insn
) = icode
= recog_memoized (insn
);
966 data
= XNEW (class lra_insn_recog_data
);
967 lra_insn_recog_data
[uid
] = data
;
969 data
->used_insn_alternative
= LRA_UNKNOWN_ALT
;
972 if (DEBUG_INSN_P (insn
))
974 data
->dup_loc
= NULL
;
975 data
->arg_hard_regs
= NULL
;
976 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
977 if (DEBUG_BIND_INSN_P (insn
))
979 data
->insn_static_data
= &debug_bind_static_data
;
980 data
->operand_loc
= XNEWVEC (rtx
*, 1);
981 data
->operand_loc
[0] = &INSN_VAR_LOCATION_LOC (insn
);
983 else if (DEBUG_MARKER_INSN_P (insn
))
985 data
->insn_static_data
= &debug_marker_static_data
;
986 data
->operand_loc
= NULL
;
993 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
994 const char *constraints
[MAX_RECOG_OPERANDS
];
996 nop
= asm_noperands (PATTERN (insn
));
997 data
->operand_loc
= data
->dup_loc
= NULL
;
1001 /* It is a special insn like USE or CLOBBER. We should
1002 recognize any regular insn otherwise LRA can do nothing
1004 gcc_assert (GET_CODE (PATTERN (insn
)) == USE
1005 || GET_CODE (PATTERN (insn
)) == CLOBBER
1006 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
1007 data
->insn_static_data
= insn_static_data
1008 = get_static_insn_data (-1, 0, 0, nalt
);
1012 /* expand_asm_operands makes sure there aren't too many
1014 lra_assert (nop
<= MAX_RECOG_OPERANDS
);
1016 data
->operand_loc
= XNEWVEC (rtx
*, nop
);
1017 /* Now get the operand values and constraints out of the
1019 decode_asm_operands (PATTERN (insn
), NULL
,
1021 constraints
, operand_mode
, NULL
);
1023 for (const char *p
=constraints
[0]; *p
; p
++)
1025 data
->insn_static_data
= insn_static_data
1026 = get_static_insn_data (-1, nop
, 0, nalt
);
1027 for (i
= 0; i
< nop
; i
++)
1029 insn_static_data
->operand
[i
].mode
= operand_mode
[i
];
1030 insn_static_data
->operand
[i
].constraint
= constraints
[i
];
1031 insn_static_data
->operand
[i
].strict_low
= false;
1032 insn_static_data
->operand
[i
].is_operator
= false;
1033 insn_static_data
->operand
[i
].is_address
= false;
1036 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1037 insn_static_data
->operand
[i
].type
1038 = (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1039 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1041 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
1044 operand_alternative
*op_alt
= XCNEWVEC (operand_alternative
,
1046 preprocess_constraints (nop
, nalt
, constraints
, op_alt
,
1048 setup_operand_alternative (data
, op_alt
);
1053 insn_extract (insn
);
1054 data
->insn_static_data
= insn_static_data
1055 = get_static_insn_data (icode
, insn_data
[icode
].n_operands
,
1056 insn_data
[icode
].n_dups
,
1057 insn_data
[icode
].n_alternatives
);
1058 n
= insn_static_data
->n_operands
;
1063 locs
= XNEWVEC (rtx
*, n
);
1064 memcpy (locs
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1066 data
->operand_loc
= locs
;
1067 n
= insn_static_data
->n_dups
;
1072 locs
= XNEWVEC (rtx
*, n
);
1073 memcpy (locs
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1075 data
->dup_loc
= locs
;
1076 data
->preferred_alternatives
= get_preferred_alternatives (insn
);
1077 const operand_alternative
*op_alt
= preprocess_insn_constraints (icode
);
1078 if (!insn_static_data
->operand_alternative
)
1079 setup_operand_alternative (data
, op_alt
);
1080 else if (op_alt
!= insn_static_data
->operand_alternative
)
1081 insn_static_data
->operand_alternative
= op_alt
;
1083 if (GET_CODE (PATTERN (insn
)) == CLOBBER
|| GET_CODE (PATTERN (insn
)) == USE
)
1084 insn_static_data
->hard_regs
= NULL
;
1086 insn_static_data
->hard_regs
1087 = collect_non_operand_hard_regs (insn
, &PATTERN (insn
), data
,
1088 NULL
, OP_IN
, false, false);
1089 data
->arg_hard_regs
= NULL
;
1094 int n_hard_regs
, regno
, arg_hard_regs
[FIRST_PSEUDO_REGISTER
];
1097 /* Finding implicit hard register usage. We believe it will be
1098 not changed whatever transformations are used. Call insns
1099 are such example. */
1100 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1102 link
= XEXP (link
, 1))
1103 if (((use_p
= GET_CODE (XEXP (link
, 0)) == USE
)
1104 || GET_CODE (XEXP (link
, 0)) == CLOBBER
)
1105 && REG_P (XEXP (XEXP (link
, 0), 0)))
1107 regno
= REGNO (XEXP (XEXP (link
, 0), 0));
1108 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
1109 /* It is an argument register. */
1110 for (i
= REG_NREGS (XEXP (XEXP (link
, 0), 0)) - 1; i
>= 0; i
--)
1111 arg_hard_regs
[n_hard_regs
++]
1112 = regno
+ i
+ (use_p
? 0 : FIRST_PSEUDO_REGISTER
);
1114 else if (GET_CODE (XEXP (link
, 0)) == CLOBBER_HIGH
)
1115 /* We could support CLOBBER_HIGH and treat it in the same way as
1116 HARD_REGNO_CALL_PART_CLOBBERED, but no port needs that yet. */
1119 if (n_hard_regs
!= 0)
1121 arg_hard_regs
[n_hard_regs
++] = -1;
1122 data
->arg_hard_regs
= XNEWVEC (int, n_hard_regs
);
1123 memcpy (data
->arg_hard_regs
, arg_hard_regs
,
1124 sizeof (int) * n_hard_regs
);
1127 /* Some output operand can be recognized only from the context not
1128 from the constraints which are empty in this case. Call insn may
1129 contain a hard register in set destination with empty constraint
1130 and extract_insn treats them as an input. */
1131 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1135 struct lra_operand_data
*operand
= &insn_static_data
->operand
[i
];
1137 /* ??? Should we treat 'X' the same way. It looks to me that
1138 'X' means anything and empty constraint means we do not
1140 if (operand
->type
!= OP_IN
|| *operand
->constraint
!= '\0'
1141 || operand
->is_operator
)
1143 pat
= PATTERN (insn
);
1144 if (GET_CODE (pat
) == SET
)
1146 if (data
->operand_loc
[i
] != &SET_DEST (pat
))
1149 else if (GET_CODE (pat
) == PARALLEL
)
1151 for (j
= XVECLEN (pat
, 0) - 1; j
>= 0; j
--)
1153 set
= XVECEXP (PATTERN (insn
), 0, j
);
1154 if (GET_CODE (set
) == SET
1155 && &SET_DEST (set
) == data
->operand_loc
[i
])
1163 operand
->type
= OP_OUT
;
1168 /* Return info about insn give by UID. The info should be already set
1170 static lra_insn_recog_data_t
1171 get_insn_recog_data_by_uid (int uid
)
1173 lra_insn_recog_data_t data
;
1175 data
= lra_insn_recog_data
[uid
];
1176 lra_assert (data
!= NULL
);
1180 /* Invalidate all info about insn given by its UID. */
1182 invalidate_insn_recog_data (int uid
)
1184 lra_insn_recog_data_t data
;
1186 data
= lra_insn_recog_data
[uid
];
1187 lra_assert (data
!= NULL
);
1188 free_insn_recog_data (data
);
1189 lra_insn_recog_data
[uid
] = NULL
;
1192 /* Update all the insn info about INSN. It is usually called when
1193 something in the insn was changed. Return the updated info. */
1194 lra_insn_recog_data_t
1195 lra_update_insn_recog_data (rtx_insn
*insn
)
1197 lra_insn_recog_data_t data
;
1199 unsigned int uid
= INSN_UID (insn
);
1200 struct lra_static_insn_data
*insn_static_data
;
1201 poly_int64 sp_offset
= 0;
1203 check_and_expand_insn_recog_data (uid
);
1204 if ((data
= lra_insn_recog_data
[uid
]) != NULL
1205 && data
->icode
!= INSN_CODE (insn
))
1207 sp_offset
= data
->sp_offset
;
1208 invalidate_insn_data_regno_info (data
, insn
, get_insn_freq (insn
));
1209 invalidate_insn_recog_data (uid
);
1214 data
= lra_get_insn_recog_data (insn
);
1215 /* Initiate or restore SP offset. */
1216 data
->sp_offset
= sp_offset
;
1219 insn_static_data
= data
->insn_static_data
;
1220 data
->used_insn_alternative
= LRA_UNKNOWN_ALT
;
1221 if (DEBUG_INSN_P (insn
))
1223 if (data
->icode
< 0)
1226 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
1227 const char *constraints
[MAX_RECOG_OPERANDS
];
1229 nop
= asm_noperands (PATTERN (insn
));
1232 lra_assert (nop
== data
->insn_static_data
->n_operands
);
1233 /* Now get the operand values and constraints out of the
1235 decode_asm_operands (PATTERN (insn
), NULL
,
1237 constraints
, operand_mode
, NULL
);
1240 for (int i
= 0; i
< nop
; i
++)
1242 (insn_static_data
->operand
[i
].mode
== operand_mode
[i
]
1243 && insn_static_data
->operand
[i
].constraint
== constraints
[i
]
1244 && ! insn_static_data
->operand
[i
].is_operator
);
1248 for (int i
= 0; i
< insn_static_data
->n_operands
; i
++)
1250 (insn_static_data
->operand
[i
].type
1251 == (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1252 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1257 insn_extract (insn
);
1258 n
= insn_static_data
->n_operands
;
1260 memcpy (data
->operand_loc
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1261 n
= insn_static_data
->n_dups
;
1263 memcpy (data
->dup_loc
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1264 lra_assert (check_bool_attrs (insn
));
1269 /* Set up that INSN is using alternative ALT now. */
1271 lra_set_used_insn_alternative (rtx_insn
*insn
, int alt
)
1273 lra_insn_recog_data_t data
;
1275 data
= lra_get_insn_recog_data (insn
);
1276 data
->used_insn_alternative
= alt
;
1279 /* Set up that insn with UID is using alternative ALT now. The insn
1280 info should be already set up. */
1282 lra_set_used_insn_alternative_by_uid (int uid
, int alt
)
1284 lra_insn_recog_data_t data
;
1286 check_and_expand_insn_recog_data (uid
);
1287 data
= lra_insn_recog_data
[uid
];
1288 lra_assert (data
!= NULL
);
1289 data
->used_insn_alternative
= alt
;
1294 /* This page contains code dealing with common register info and
1297 /* The size of the following array. */
1298 static int reg_info_size
;
1299 /* Common info about each register. */
1300 class lra_reg
*lra_reg_info
;
1302 HARD_REG_SET hard_regs_spilled_into
;
1304 /* Last register value. */
1305 static int last_reg_value
;
1307 /* Return new register value. */
1309 get_new_reg_value (void)
1311 return ++last_reg_value
;
1314 /* Vec referring to pseudo copies. */
1315 static vec
<lra_copy_t
> copy_vec
;
1317 /* Initialize I-th element of lra_reg_info. */
1319 initialize_lra_reg_info_element (int i
)
1321 bitmap_initialize (&lra_reg_info
[i
].insn_bitmap
, ®_obstack
);
1323 lra_reg_info
[i
].no_stack_p
= false;
1325 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
1326 CLEAR_HARD_REG_SET (lra_reg_info
[i
].actual_call_used_reg_set
);
1327 lra_reg_info
[i
].preferred_hard_regno1
= -1;
1328 lra_reg_info
[i
].preferred_hard_regno2
= -1;
1329 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
1330 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
1331 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
1332 lra_reg_info
[i
].live_ranges
= NULL
;
1333 lra_reg_info
[i
].nrefs
= lra_reg_info
[i
].freq
= 0;
1334 lra_reg_info
[i
].last_reload
= 0;
1335 lra_reg_info
[i
].restore_rtx
= NULL_RTX
;
1336 lra_reg_info
[i
].val
= get_new_reg_value ();
1337 lra_reg_info
[i
].offset
= 0;
1338 lra_reg_info
[i
].copies
= NULL
;
1339 lra_reg_info
[i
].call_insn
= NULL
;
1342 /* Initialize common reg info and copies. */
1344 init_reg_info (void)
1349 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1350 lra_reg_info
= XNEWVEC (class lra_reg
, reg_info_size
);
1351 for (i
= 0; i
< reg_info_size
; i
++)
1352 initialize_lra_reg_info_element (i
);
1353 copy_vec
.truncate (0);
1354 CLEAR_HARD_REG_SET (hard_regs_spilled_into
);
1358 /* Finish common reg info and copies. */
1360 finish_reg_info (void)
1364 for (i
= 0; i
< reg_info_size
; i
++)
1365 bitmap_clear (&lra_reg_info
[i
].insn_bitmap
);
1366 free (lra_reg_info
);
1370 /* Expand common reg info if it is necessary. */
1372 expand_reg_info (void)
1374 int i
, old
= reg_info_size
;
1376 if (reg_info_size
> max_reg_num ())
1378 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1379 lra_reg_info
= XRESIZEVEC (class lra_reg
, lra_reg_info
, reg_info_size
);
1380 for (i
= old
; i
< reg_info_size
; i
++)
1381 initialize_lra_reg_info_element (i
);
1384 /* Free all copies. */
1386 lra_free_copies (void)
1390 while (copy_vec
.length () != 0)
1392 cp
= copy_vec
.pop ();
1393 lra_reg_info
[cp
->regno1
].copies
= lra_reg_info
[cp
->regno2
].copies
= NULL
;
1394 lra_copy_pool
.remove (cp
);
1398 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1399 frequency is FREQ. */
1401 lra_create_copy (int regno1
, int regno2
, int freq
)
1406 lra_assert (regno1
!= regno2
);
1407 regno1_dest_p
= true;
1408 if (regno1
> regno2
)
1410 std::swap (regno1
, regno2
);
1411 regno1_dest_p
= false;
1413 cp
= lra_copy_pool
.allocate ();
1414 copy_vec
.safe_push (cp
);
1415 cp
->regno1_dest_p
= regno1_dest_p
;
1417 cp
->regno1
= regno1
;
1418 cp
->regno2
= regno2
;
1419 cp
->regno1_next
= lra_reg_info
[regno1
].copies
;
1420 lra_reg_info
[regno1
].copies
= cp
;
1421 cp
->regno2_next
= lra_reg_info
[regno2
].copies
;
1422 lra_reg_info
[regno2
].copies
= cp
;
1423 if (lra_dump_file
!= NULL
)
1424 fprintf (lra_dump_file
, " Creating copy r%d%sr%d@%d\n",
1425 regno1
, regno1_dest_p
? "<-" : "->", regno2
, freq
);
1428 /* Return N-th (0, 1, ...) copy. If there is no copy, return
1431 lra_get_copy (int n
)
1433 if (n
>= (int) copy_vec
.length ())
1440 /* This page contains code dealing with info about registers in
1443 /* Process X of INSN recursively and add info (operand type is given
1444 by TYPE) about registers in X to the insn DATA. If X can be early
1445 clobbered, alternatives in which it can be early clobbered are given
1446 by EARLY_CLOBBER_ALTS. */
1448 add_regs_to_insn_regno_info (lra_insn_recog_data_t data
, rtx x
,
1449 rtx_insn
*insn
, enum op_type type
,
1450 alternative_mask early_clobber_alts
)
1457 struct lra_insn_reg
*curr
;
1459 code
= GET_CODE (x
);
1460 mode
= GET_MODE (x
);
1462 if (GET_CODE (x
) == SUBREG
)
1464 mode
= wider_subreg_mode (x
);
1465 if (read_modify_subreg_p (x
))
1468 code
= GET_CODE (x
);
1473 /* Process all regs even unallocatable ones as we need info about
1474 all regs for rematerialization pass. */
1476 if (bitmap_set_bit (&lra_reg_info
[regno
].insn_bitmap
, INSN_UID (insn
)))
1478 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
1479 early_clobber_alts
, data
->regs
, false);
1484 for (curr
= data
->regs
; curr
!= NULL
; curr
= curr
->next
)
1485 if (curr
->regno
== regno
)
1487 if (curr
->subreg_p
!= subreg_p
|| curr
->biggest_mode
!= mode
)
1488 /* The info cannot be integrated into the found
1490 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
,
1491 subreg_p
, early_clobber_alts
,
1495 if (curr
->type
!= type
)
1496 curr
->type
= OP_INOUT
;
1497 curr
->early_clobber_alts
|= early_clobber_alts
;
1508 add_regs_to_insn_regno_info (data
, SET_DEST (x
), insn
, OP_OUT
, 0);
1509 add_regs_to_insn_regno_info (data
, SET_SRC (x
), insn
, OP_IN
, 0);
1512 /* We treat clobber of non-operand hard registers as early
1514 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), insn
, OP_OUT
,
1519 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
1520 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), insn
, OP_INOUT
, 0);
1522 case PRE_MODIFY
: case POST_MODIFY
:
1523 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), insn
, OP_INOUT
, 0);
1524 add_regs_to_insn_regno_info (data
, XEXP (x
, 1), insn
, OP_IN
, 0);
1527 if ((code
!= PARALLEL
&& code
!= EXPR_LIST
) || type
!= OP_OUT
)
1528 /* Some targets place small structures in registers for return
1529 values of functions, and those registers are wrapped in
1530 PARALLEL that we may see as the destination of a SET. Here
1533 (call_insn 13 12 14 2 (set (parallel:BLK [
1534 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1536 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1537 (const_int 8 [0x8]))
1539 (call (mem:QI (symbol_ref:DI (... */
1541 fmt
= GET_RTX_FORMAT (code
);
1542 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1545 add_regs_to_insn_regno_info (data
, XEXP (x
, i
), insn
, type
, 0);
1546 else if (fmt
[i
] == 'E')
1548 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1549 add_regs_to_insn_regno_info (data
, XVECEXP (x
, i
, j
), insn
,
1556 /* Return execution frequency of INSN. */
1558 get_insn_freq (rtx_insn
*insn
)
1560 basic_block bb
= BLOCK_FOR_INSN (insn
);
1562 gcc_checking_assert (bb
!= NULL
);
1563 return REG_FREQ_FROM_BB (bb
);
1566 /* Invalidate all reg info of INSN with DATA and execution frequency
1567 FREQ. Update common info about the invalidated registers. */
1569 invalidate_insn_data_regno_info (lra_insn_recog_data_t data
, rtx_insn
*insn
,
1575 struct lra_insn_reg
*ir
, *next_ir
;
1577 uid
= INSN_UID (insn
);
1578 debug_p
= DEBUG_INSN_P (insn
);
1579 for (ir
= data
->regs
; ir
!= NULL
; ir
= next_ir
)
1583 lra_insn_reg_pool
.remove (ir
);
1584 bitmap_clear_bit (&lra_reg_info
[i
].insn_bitmap
, uid
);
1585 if (i
>= FIRST_PSEUDO_REGISTER
&& ! debug_p
)
1587 lra_reg_info
[i
].nrefs
--;
1588 lra_reg_info
[i
].freq
-= freq
;
1589 lra_assert (lra_reg_info
[i
].nrefs
>= 0 && lra_reg_info
[i
].freq
>= 0);
1595 /* Invalidate all reg info of INSN. Update common info about the
1596 invalidated registers. */
1598 lra_invalidate_insn_regno_info (rtx_insn
*insn
)
1600 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn
), insn
,
1601 get_insn_freq (insn
));
1604 /* Update common reg info from reg info of insn given by its DATA and
1605 execution frequency FREQ. */
1607 setup_insn_reg_info (lra_insn_recog_data_t data
, int freq
)
1610 struct lra_insn_reg
*ir
;
1612 for (ir
= data
->regs
; ir
!= NULL
; ir
= ir
->next
)
1613 if ((i
= ir
->regno
) >= FIRST_PSEUDO_REGISTER
)
1615 lra_reg_info
[i
].nrefs
++;
1616 lra_reg_info
[i
].freq
+= freq
;
1620 /* Set up insn reg info of INSN. Update common reg info from reg info
1623 lra_update_insn_regno_info (rtx_insn
*insn
)
1626 lra_insn_recog_data_t data
;
1627 struct lra_static_insn_data
*static_data
;
1631 if (! INSN_P (insn
))
1633 data
= lra_get_insn_recog_data (insn
);
1634 static_data
= data
->insn_static_data
;
1635 freq
= NONDEBUG_INSN_P (insn
) ? get_insn_freq (insn
) : 0;
1636 invalidate_insn_data_regno_info (data
, insn
, freq
);
1637 for (i
= static_data
->n_operands
- 1; i
>= 0; i
--)
1638 add_regs_to_insn_regno_info (data
, *data
->operand_loc
[i
], insn
,
1639 static_data
->operand
[i
].type
,
1640 static_data
->operand
[i
].early_clobber_alts
);
1641 if ((code
= GET_CODE (PATTERN (insn
))) == CLOBBER
|| code
== USE
)
1642 add_regs_to_insn_regno_info (data
, XEXP (PATTERN (insn
), 0), insn
,
1643 code
== USE
? OP_IN
: OP_OUT
, 0);
1645 /* On some targets call insns can refer to pseudos in memory in
1646 CALL_INSN_FUNCTION_USAGE list. Process them in order to
1647 consider their occurrences in calls for different
1648 transformations (e.g. inheritance) with given pseudos. */
1649 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1651 link
= XEXP (link
, 1))
1653 code
= GET_CODE (XEXP (link
, 0));
1654 /* We could support CLOBBER_HIGH and treat it in the same way as
1655 HARD_REGNO_CALL_PART_CLOBBERED, but no port needs that yet. */
1656 gcc_assert (code
!= CLOBBER_HIGH
);
1657 if ((code
== USE
|| code
== CLOBBER
)
1658 && MEM_P (XEXP (XEXP (link
, 0), 0)))
1659 add_regs_to_insn_regno_info (data
, XEXP (XEXP (link
, 0), 0), insn
,
1660 code
== USE
? OP_IN
: OP_OUT
, 0);
1662 if (NONDEBUG_INSN_P (insn
))
1663 setup_insn_reg_info (data
, freq
);
1666 /* Return reg info of insn given by it UID. */
1667 struct lra_insn_reg
*
1668 lra_get_insn_regs (int uid
)
1670 lra_insn_recog_data_t data
;
1672 data
= get_insn_recog_data_by_uid (uid
);
1678 /* Recursive hash function for RTL X. */
1680 lra_rtx_hash (rtx x
)
1690 code
= GET_CODE (x
);
1691 val
+= (int) code
+ 4095;
1693 /* Some RTL can be compared nonrecursively. */
1697 return val
+ REGNO (x
);
1700 return iterative_hash_object (XEXP (x
, 0), val
);
1703 return iterative_hash_object (XSTR (x
, 0), val
);
1711 return val
+ UINTVAL (x
);
1717 /* Hash the elements. */
1718 fmt
= GET_RTX_FORMAT (code
);
1719 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1724 val
+= XWINT (x
, i
);
1734 val
+= XVECLEN (x
, i
);
1736 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1737 val
+= lra_rtx_hash (XVECEXP (x
, i
, j
));
1741 val
+= lra_rtx_hash (XEXP (x
, i
));
1746 val
+= htab_hash_string (XSTR (x
, i
));
1754 /* It is believed that rtx's at this level will never
1755 contain anything but integers and other rtx's, except for
1756 within LABEL_REFs and SYMBOL_REFs. */
1766 /* This page contains code dealing with stack of the insns which
1767 should be processed by the next constraint pass. */
1769 /* Bitmap used to put an insn on the stack only in one exemplar. */
1770 static sbitmap lra_constraint_insn_stack_bitmap
;
1772 /* The stack itself. */
1773 vec
<rtx_insn
*> lra_constraint_insn_stack
;
1775 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1776 info for INSN, otherwise only update it if INSN is not already on the
1779 lra_push_insn_1 (rtx_insn
*insn
, bool always_update
)
1781 unsigned int uid
= INSN_UID (insn
);
1783 lra_update_insn_regno_info (insn
);
1784 if (uid
>= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap
))
1785 lra_constraint_insn_stack_bitmap
=
1786 sbitmap_resize (lra_constraint_insn_stack_bitmap
, 3 * uid
/ 2, 0);
1787 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap
, uid
))
1789 bitmap_set_bit (lra_constraint_insn_stack_bitmap
, uid
);
1790 if (! always_update
)
1791 lra_update_insn_regno_info (insn
);
1792 lra_constraint_insn_stack
.safe_push (insn
);
1795 /* Put INSN on the stack. */
1797 lra_push_insn (rtx_insn
*insn
)
1799 lra_push_insn_1 (insn
, false);
1802 /* Put INSN on the stack and update its reg info. */
1804 lra_push_insn_and_update_insn_regno_info (rtx_insn
*insn
)
1806 lra_push_insn_1 (insn
, true);
1809 /* Put insn with UID on the stack. */
1811 lra_push_insn_by_uid (unsigned int uid
)
1813 lra_push_insn (lra_insn_recog_data
[uid
]->insn
);
1816 /* Take the last-inserted insns off the stack and return it. */
1820 rtx_insn
*insn
= lra_constraint_insn_stack
.pop ();
1821 bitmap_clear_bit (lra_constraint_insn_stack_bitmap
, INSN_UID (insn
));
1825 /* Return the current size of the insn stack. */
1827 lra_insn_stack_length (void)
1829 return lra_constraint_insn_stack
.length ();
1832 /* Push insns FROM to TO (excluding it) going in reverse order. */
1834 push_insns (rtx_insn
*from
, rtx_insn
*to
)
1838 if (from
== NULL_RTX
)
1840 for (insn
= from
; insn
!= to
; insn
= PREV_INSN (insn
))
1842 lra_push_insn (insn
);
1845 /* Set up sp offset for insn in range [FROM, LAST]. The offset is
1846 taken from the next BB insn after LAST or zero if there in such
1849 setup_sp_offset (rtx_insn
*from
, rtx_insn
*last
)
1851 rtx_insn
*before
= next_nonnote_nondebug_insn_bb (last
);
1852 poly_int64 offset
= (before
== NULL_RTX
|| ! INSN_P (before
)
1853 ? 0 : lra_get_insn_recog_data (before
)->sp_offset
);
1855 for (rtx_insn
*insn
= from
; insn
!= NEXT_INSN (last
); insn
= NEXT_INSN (insn
))
1856 lra_get_insn_recog_data (insn
)->sp_offset
= offset
;
1859 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1860 insns onto the stack. Print about emitting the insns with
1863 lra_process_new_insns (rtx_insn
*insn
, rtx_insn
*before
, rtx_insn
*after
,
1868 if (before
== NULL_RTX
&& after
== NULL_RTX
)
1870 if (lra_dump_file
!= NULL
)
1872 dump_insn_slim (lra_dump_file
, insn
);
1873 if (before
!= NULL_RTX
)
1875 fprintf (lra_dump_file
," %s before:\n", title
);
1876 dump_rtl_slim (lra_dump_file
, before
, NULL
, -1, 0);
1878 if (after
!= NULL_RTX
)
1880 fprintf (lra_dump_file
, " %s after:\n", title
);
1881 dump_rtl_slim (lra_dump_file
, after
, NULL
, -1, 0);
1883 fprintf (lra_dump_file
, "\n");
1885 if (before
!= NULL_RTX
)
1887 if (cfun
->can_throw_non_call_exceptions
)
1888 copy_reg_eh_region_note_forward (insn
, before
, NULL
);
1889 emit_insn_before (before
, insn
);
1890 push_insns (PREV_INSN (insn
), PREV_INSN (before
));
1891 setup_sp_offset (before
, PREV_INSN (insn
));
1893 if (after
!= NULL_RTX
)
1895 if (cfun
->can_throw_non_call_exceptions
)
1896 copy_reg_eh_region_note_forward (insn
, after
, NULL
);
1897 for (last
= after
; NEXT_INSN (last
) != NULL_RTX
; last
= NEXT_INSN (last
))
1899 emit_insn_after (after
, insn
);
1900 push_insns (last
, insn
);
1901 setup_sp_offset (after
, last
);
1903 if (cfun
->can_throw_non_call_exceptions
)
1905 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
1906 if (note
&& !insn_could_throw_p (insn
))
1907 remove_note (insn
, note
);
1912 /* Replace all references to register OLD_REGNO in *LOC with pseudo
1913 register NEW_REG. Try to simplify subreg of constant if SUBREG_P.
1914 DEBUG_P is if LOC is within a DEBUG_INSN. Return true if any
1917 lra_substitute_pseudo (rtx
*loc
, int old_regno
, rtx new_reg
, bool subreg_p
,
1921 bool result
= false;
1929 code
= GET_CODE (x
);
1930 if (code
== SUBREG
&& subreg_p
)
1932 rtx subst
, inner
= SUBREG_REG (x
);
1933 /* Transform subreg of constant while we still have inner mode
1934 of the subreg. The subreg internal should not be an insn
1936 if (REG_P (inner
) && (int) REGNO (inner
) == old_regno
1937 && CONSTANT_P (new_reg
)
1938 && (subst
= simplify_subreg (GET_MODE (x
), new_reg
, GET_MODE (inner
),
1939 SUBREG_BYTE (x
))) != NULL_RTX
)
1946 else if (code
== REG
&& (int) REGNO (x
) == old_regno
)
1948 machine_mode mode
= GET_MODE (x
);
1949 machine_mode inner_mode
= GET_MODE (new_reg
);
1951 if (mode
!= inner_mode
1952 && ! (CONST_SCALAR_INT_P (new_reg
) && SCALAR_INT_MODE_P (mode
)))
1954 poly_uint64 offset
= 0;
1955 if (partial_subreg_p (mode
, inner_mode
)
1956 && SCALAR_INT_MODE_P (inner_mode
))
1957 offset
= subreg_lowpart_offset (mode
, inner_mode
);
1959 new_reg
= gen_rtx_raw_SUBREG (mode
, new_reg
, offset
);
1961 new_reg
= gen_rtx_SUBREG (mode
, new_reg
, offset
);
1967 /* Scan all the operand sub-expressions. */
1968 fmt
= GET_RTX_FORMAT (code
);
1969 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1973 if (lra_substitute_pseudo (&XEXP (x
, i
), old_regno
,
1974 new_reg
, subreg_p
, debug_p
))
1977 else if (fmt
[i
] == 'E')
1979 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1980 if (lra_substitute_pseudo (&XVECEXP (x
, i
, j
), old_regno
,
1981 new_reg
, subreg_p
, debug_p
))
1988 /* Call lra_substitute_pseudo within an insn. Try to simplify subreg
1989 of constant if SUBREG_P. This won't update the insn ptr, just the
1990 contents of the insn. */
1992 lra_substitute_pseudo_within_insn (rtx_insn
*insn
, int old_regno
,
1993 rtx new_reg
, bool subreg_p
)
1996 return lra_substitute_pseudo (&loc
, old_regno
, new_reg
, subreg_p
,
1997 DEBUG_INSN_P (insn
));
2002 /* This page contains code dealing with scratches (changing them onto
2003 pseudos and restoring them from the pseudos).
2005 We change scratches into pseudos at the beginning of LRA to
2006 simplify dealing with them (conflicts, hard register assignments).
2008 If the pseudo denoting scratch was spilled it means that we do need
2009 a hard register for it. Such pseudos are transformed back to
2010 scratches at the end of LRA. */
2012 /* Description of location of a former scratch operand. */
2015 rtx_insn
*insn
; /* Insn where the scratch was. */
2016 int nop
; /* Number of the operand which was a scratch. */
2017 int icode
; /* Original icode from which scratch was removed. */
2020 typedef struct sloc
*sloc_t
;
2022 /* Locations of the former scratches. */
2023 static vec
<sloc_t
> scratches
;
2025 /* Bitmap of scratch regnos. */
2026 static bitmap_head scratch_bitmap
;
2028 /* Bitmap of scratch operands. */
2029 static bitmap_head scratch_operand_bitmap
;
2031 /* Return true if pseudo REGNO is made of SCRATCH. */
2033 lra_former_scratch_p (int regno
)
2035 return bitmap_bit_p (&scratch_bitmap
, regno
);
2038 /* Return true if the operand NOP of INSN is a former scratch. */
2040 lra_former_scratch_operand_p (rtx_insn
*insn
, int nop
)
2042 return bitmap_bit_p (&scratch_operand_bitmap
,
2043 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
) != 0;
2046 /* Register operand NOP in INSN as a former scratch. It will be
2047 changed to scratch back, if it is necessary, at the LRA end. */
2049 lra_register_new_scratch_op (rtx_insn
*insn
, int nop
, int icode
)
2051 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
2052 rtx op
= *id
->operand_loc
[nop
];
2053 sloc_t loc
= XNEW (struct sloc
);
2054 lra_assert (REG_P (op
));
2058 scratches
.safe_push (loc
);
2059 bitmap_set_bit (&scratch_bitmap
, REGNO (op
));
2060 bitmap_set_bit (&scratch_operand_bitmap
,
2061 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
);
2062 add_reg_note (insn
, REG_UNUSED
, op
);
2065 /* Change INSN's scratches into pseudos and save their location. */
2067 remove_scratches_1 (rtx_insn
*insn
)
2070 bool insn_changed_p
;
2072 lra_insn_recog_data_t id
;
2073 struct lra_static_insn_data
*static_id
;
2075 id
= lra_get_insn_recog_data (insn
);
2076 static_id
= id
->insn_static_data
;
2077 insn_changed_p
= false;
2078 for (i
= 0; i
< static_id
->n_operands
; i
++)
2079 if (GET_CODE (*id
->operand_loc
[i
]) == SCRATCH
2080 && GET_MODE (*id
->operand_loc
[i
]) != VOIDmode
)
2082 insn_changed_p
= true;
2083 *id
->operand_loc
[i
] = reg
2084 = lra_create_new_reg (static_id
->operand
[i
].mode
,
2085 *id
->operand_loc
[i
], ALL_REGS
, NULL
);
2086 lra_register_new_scratch_op (insn
, i
, id
->icode
);
2087 if (lra_dump_file
!= NULL
)
2088 fprintf (lra_dump_file
,
2089 "Removing SCRATCH in insn #%u (nop %d)\n",
2090 INSN_UID (insn
), i
);
2093 /* Because we might use DF right after caller-saves sub-pass
2094 we need to keep DF info up to date. */
2095 df_insn_rescan (insn
);
2098 /* Change scratches into pseudos and save their location. */
2100 remove_scratches (void)
2105 scratches
.create (get_max_uid ());
2106 bitmap_initialize (&scratch_bitmap
, ®_obstack
);
2107 bitmap_initialize (&scratch_operand_bitmap
, ®_obstack
);
2108 FOR_EACH_BB_FN (bb
, cfun
)
2109 FOR_BB_INSNS (bb
, insn
)
2111 remove_scratches_1 (insn
);
2114 /* Changes pseudos created by function remove_scratches onto scratches. */
2116 restore_scratches (void)
2121 rtx_insn
*last
= NULL
;
2122 lra_insn_recog_data_t id
= NULL
;
2124 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
2126 /* Ignore already deleted insns. */
2127 if (NOTE_P (loc
->insn
)
2128 && NOTE_KIND (loc
->insn
) == NOTE_INSN_DELETED
)
2130 if (last
!= loc
->insn
)
2133 id
= lra_get_insn_recog_data (last
);
2135 if (loc
->icode
!= id
->icode
)
2137 /* The icode doesn't match, which means the insn has been modified
2138 (e.g. register elimination). The scratch cannot be restored. */
2141 if (REG_P (*id
->operand_loc
[loc
->nop
])
2142 && ((regno
= REGNO (*id
->operand_loc
[loc
->nop
]))
2143 >= FIRST_PSEUDO_REGISTER
)
2144 && lra_get_regno_hard_regno (regno
) < 0)
2146 /* It should be only case when scratch register with chosen
2147 constraint 'X' did not get memory or hard register. */
2148 lra_assert (lra_former_scratch_p (regno
));
2149 *id
->operand_loc
[loc
->nop
]
2150 = gen_rtx_SCRATCH (GET_MODE (*id
->operand_loc
[loc
->nop
]));
2151 lra_update_dup (id
, loc
->nop
);
2152 if (lra_dump_file
!= NULL
)
2153 fprintf (lra_dump_file
, "Restoring SCRATCH in insn #%u(nop %d)\n",
2154 INSN_UID (loc
->insn
), loc
->nop
);
2157 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
2159 scratches
.release ();
2160 bitmap_clear (&scratch_bitmap
);
2161 bitmap_clear (&scratch_operand_bitmap
);
2166 /* Function checks RTL for correctness. If FINAL_P is true, it is
2167 done at the end of LRA and the check is more rigorous. */
2169 check_rtl (bool final_p
)
2174 lra_assert (! final_p
|| reload_completed
);
2175 FOR_EACH_BB_FN (bb
, cfun
)
2176 FOR_BB_INSNS (bb
, insn
)
2177 if (NONDEBUG_INSN_P (insn
)
2178 && GET_CODE (PATTERN (insn
)) != USE
2179 && GET_CODE (PATTERN (insn
)) != CLOBBER
2180 && GET_CODE (PATTERN (insn
)) != ASM_INPUT
)
2184 extract_constrain_insn (insn
);
2187 /* LRA code is based on assumption that all addresses can be
2188 correctly decomposed. LRA can generate reloads for
2189 decomposable addresses. The decomposition code checks the
2190 correctness of the addresses. So we don't need to check
2191 the addresses here. Don't call insn_invalid_p here, it can
2192 change the code at this stage. */
2193 if (recog_memoized (insn
) < 0 && asm_noperands (PATTERN (insn
)) < 0)
2194 fatal_insn_not_found (insn
);
2198 /* Determine if the current function has an exception receiver block
2199 that reaches the exit block via non-exceptional edges */
2201 has_nonexceptional_receiver (void)
2205 basic_block
*tos
, *worklist
, bb
;
2207 /* If we're not optimizing, then just err on the safe side. */
2211 /* First determine which blocks can reach exit via normal paths. */
2212 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
) + 1);
2214 FOR_EACH_BB_FN (bb
, cfun
)
2215 bb
->flags
&= ~BB_REACHABLE
;
2217 /* Place the exit block on our worklist. */
2218 EXIT_BLOCK_PTR_FOR_FN (cfun
)->flags
|= BB_REACHABLE
;
2219 *tos
++ = EXIT_BLOCK_PTR_FOR_FN (cfun
);
2221 /* Iterate: find everything reachable from what we've already seen. */
2222 while (tos
!= worklist
)
2226 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2227 if (e
->flags
& EDGE_ABNORMAL
)
2234 basic_block src
= e
->src
;
2236 if (!(src
->flags
& BB_REACHABLE
))
2238 src
->flags
|= BB_REACHABLE
;
2244 /* No exceptional block reached exit unexceptionally. */
2249 /* Process recursively X of INSN and add REG_INC notes if necessary. */
2251 add_auto_inc_notes (rtx_insn
*insn
, rtx x
)
2253 enum rtx_code code
= GET_CODE (x
);
2257 if (code
== MEM
&& auto_inc_p (XEXP (x
, 0)))
2259 add_reg_note (insn
, REG_INC
, XEXP (XEXP (x
, 0), 0));
2263 /* Scan all X sub-expressions. */
2264 fmt
= GET_RTX_FORMAT (code
);
2265 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2268 add_auto_inc_notes (insn
, XEXP (x
, i
));
2269 else if (fmt
[i
] == 'E')
2270 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2271 add_auto_inc_notes (insn
, XVECEXP (x
, i
, j
));
2276 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2277 We change pseudos by hard registers without notification of DF and
2278 that can make the notes obsolete. DF-infrastructure does not deal
2279 with REG_INC notes -- so we should regenerate them here. */
2281 update_inc_notes (void)
2287 FOR_EACH_BB_FN (bb
, cfun
)
2288 FOR_BB_INSNS (bb
, insn
)
2289 if (NONDEBUG_INSN_P (insn
))
2291 pnote
= ®_NOTES (insn
);
2294 if (REG_NOTE_KIND (*pnote
) == REG_DEAD
2295 || REG_NOTE_KIND (*pnote
) == REG_UNUSED
2296 || REG_NOTE_KIND (*pnote
) == REG_INC
)
2297 *pnote
= XEXP (*pnote
, 1);
2299 pnote
= &XEXP (*pnote
, 1);
2303 add_auto_inc_notes (insn
, PATTERN (insn
));
2307 /* Set to 1 while in lra. */
2308 int lra_in_progress
;
2310 /* Start of pseudo regnos before the LRA. */
2311 int lra_new_regno_start
;
2313 /* Start of reload pseudo regnos before the new spill pass. */
2314 int lra_constraint_new_regno_start
;
2316 /* Avoid spilling pseudos with regno more than the following value if
2318 int lra_bad_spill_regno_start
;
2320 /* Inheritance pseudo regnos before the new spill pass. */
2321 bitmap_head lra_inheritance_pseudos
;
2323 /* Split regnos before the new spill pass. */
2324 bitmap_head lra_split_regs
;
2326 /* Reload pseudo regnos before the new assignment pass which still can
2327 be spilled after the assignment pass as memory is also accepted in
2328 insns for the reload pseudos. */
2329 bitmap_head lra_optional_reload_pseudos
;
2331 /* Pseudo regnos used for subreg reloads before the new assignment
2332 pass. Such pseudos still can be spilled after the assignment
2334 bitmap_head lra_subreg_reload_pseudos
;
2336 /* File used for output of LRA debug information. */
2337 FILE *lra_dump_file
;
2339 /* True if we found an asm error. */
2340 bool lra_asm_error_p
;
2342 /* True if we should try spill into registers of different classes
2343 instead of memory. */
2344 bool lra_reg_spill_p
;
2346 /* Set up value LRA_REG_SPILL_P. */
2348 setup_reg_spill_flag (void)
2352 if (targetm
.spill_class
!= NULL
)
2353 for (cl
= 0; cl
< (int) LIM_REG_CLASSES
; cl
++)
2354 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
2355 if (targetm
.spill_class ((enum reg_class
) cl
,
2356 (machine_mode
) mode
) != NO_REGS
)
2358 lra_reg_spill_p
= true;
2361 lra_reg_spill_p
= false;
2364 /* True if the current function is too big to use regular algorithms
2365 in LRA. In other words, we should use simpler and faster algorithms
2366 in LRA. It also means we should not worry about generation code
2367 for caller saves. The value is set up in IRA. */
2370 /* Major LRA entry function. F is a file should be used to dump LRA
2376 bool live_p
, inserted_p
;
2379 lra_asm_error_p
= false;
2381 timevar_push (TV_LRA
);
2383 /* Make sure that the last insn is a note. Some subsequent passes
2385 emit_note (NOTE_INSN_DELETED
);
2387 lra_no_alloc_regs
= ira_no_alloc_regs
;
2392 init_insn_recog_data ();
2394 /* Some quick check on RTL generated by previous passes. */
2398 lra_in_progress
= 1;
2400 lra_live_range_iter
= lra_coalesce_iter
= lra_constraint_iter
= 0;
2401 lra_assignment_iter
= lra_assignment_iter_after_spill
= 0;
2402 lra_inheritance_iter
= lra_undo_inheritance_iter
= 0;
2403 lra_rematerialization_iter
= 0;
2405 setup_reg_spill_flag ();
2407 /* Function remove_scratches can creates new pseudos for clobbers --
2408 so set up lra_constraint_new_regno_start before its call to
2409 permit changing reg classes for pseudos created by this
2411 lra_constraint_new_regno_start
= lra_new_regno_start
= max_reg_num ();
2412 lra_bad_spill_regno_start
= INT_MAX
;
2413 remove_scratches ();
2415 /* A function that has a non-local label that can reach the exit
2416 block via non-exceptional paths must save all call-saved
2418 if (cfun
->has_nonlocal_label
&& has_nonexceptional_receiver ())
2419 crtl
->saves_all_registers
= 1;
2421 if (crtl
->saves_all_registers
)
2422 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2423 if (! call_used_regs
[i
] && ! fixed_regs
[i
] && ! LOCAL_REGNO (i
))
2424 df_set_regs_ever_live (i
, true);
2426 /* We don't DF from now and avoid its using because it is to
2427 expensive when a lot of RTL changes are made. */
2428 df_set_flags (DF_NO_INSN_RESCAN
);
2429 lra_constraint_insn_stack
.create (get_max_uid ());
2430 lra_constraint_insn_stack_bitmap
= sbitmap_alloc (get_max_uid ());
2431 bitmap_clear (lra_constraint_insn_stack_bitmap
);
2432 lra_live_ranges_init ();
2433 lra_constraints_init ();
2434 lra_curr_reload_num
= 0;
2435 push_insns (get_last_insn (), NULL
);
2436 /* It is needed for the 1st coalescing. */
2437 bitmap_initialize (&lra_inheritance_pseudos
, ®_obstack
);
2438 bitmap_initialize (&lra_split_regs
, ®_obstack
);
2439 bitmap_initialize (&lra_optional_reload_pseudos
, ®_obstack
);
2440 bitmap_initialize (&lra_subreg_reload_pseudos
, ®_obstack
);
2442 if (maybe_ne (get_frame_size (), 0) && crtl
->stack_alignment_needed
)
2443 /* If we have a stack frame, we must align it now. The stack size
2444 may be a part of the offset computation for register
2446 assign_stack_local (BLKmode
, 0, crtl
->stack_alignment_needed
);
2452 bool reloads_p
= lra_constraints (lra_constraint_iter
== 0);
2453 /* Constraint transformations may result in that eliminable
2454 hard regs become uneliminable and pseudos which use them
2455 should be spilled. It is better to do it before pseudo
2458 For example, rs6000 can make
2459 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2460 to use a constant pool. */
2461 lra_eliminate (false, false);
2462 /* We should try to assign hard registers to scratches even
2463 if there were no RTL transformations in lra_constraints.
2464 Also we should check IRA assignments on the first
2465 iteration as they can be wrong because of early clobbers
2466 operands which are ignored in IRA. */
2467 if (! reloads_p
&& lra_constraint_iter
> 1)
2469 /* Stack is not empty here only when there are changes
2470 during the elimination sub-pass. */
2471 if (bitmap_empty_p (lra_constraint_insn_stack_bitmap
))
2474 /* If there are no reloads but changing due
2475 elimination, restart the constraint sub-pass
2479 /* Do inheritance only for regular algorithms. */
2485 lra_clear_live_ranges ();
2486 /* As a side-effect of lra_create_live_ranges, we calculate
2487 actual_call_used_reg_set, which is needed during
2489 lra_create_live_ranges (true, true);
2495 lra_clear_live_ranges ();
2499 /* We need live ranges for lra_assign -- so build them.
2500 But don't remove dead insns or change global live
2501 info as we can undo inheritance transformations after
2502 inheritance pseudo assigning. */
2503 lra_create_live_ranges (true, false);
2505 /* If we don't spill non-reload and non-inheritance
2506 pseudos, there is no sense to run memory-memory move
2507 coalescing. If inheritance pseudos were spilled, the
2508 memory-memory moves involving them will be removed by
2509 pass undoing inheritance. */
2511 lra_assign (fails_p
);
2514 bool spill_p
= !lra_assign (fails_p
);
2516 if (lra_undo_inheritance ())
2518 if (spill_p
&& ! fails_p
)
2522 lra_create_live_ranges (true, true);
2525 if (lra_coalesce ())
2529 lra_clear_live_ranges ();
2533 /* It is a very rare case. It is the last hope to
2534 split a hard regno live range for a reload
2537 lra_clear_live_ranges ();
2539 if (! lra_split_hard_reg_for ())
2545 /* Don't clear optional reloads bitmap until all constraints are
2546 satisfied as we need to differ them from regular reloads. */
2547 bitmap_clear (&lra_optional_reload_pseudos
);
2548 bitmap_clear (&lra_subreg_reload_pseudos
);
2549 bitmap_clear (&lra_inheritance_pseudos
);
2550 bitmap_clear (&lra_split_regs
);
2553 /* We need full live info for spilling pseudos into
2554 registers instead of memory. */
2555 lra_create_live_ranges (lra_reg_spill_p
, true);
2558 /* We should check necessity for spilling here as the above live
2559 range pass can remove spilled pseudos. */
2560 if (! lra_need_for_spills_p ())
2562 /* Now we know what pseudos should be spilled. Try to
2563 rematerialize them first. */
2566 /* We need full live info -- see the comment above. */
2567 lra_create_live_ranges (lra_reg_spill_p
, true);
2569 if (! lra_need_for_spills_p ())
2571 if (lra_need_for_scratch_reg_p ())
2577 /* Assignment of stack slots changes elimination offsets for
2578 some eliminations. So update the offsets here. */
2579 lra_eliminate (false, false);
2580 lra_constraint_new_regno_start
= max_reg_num ();
2581 if (lra_bad_spill_regno_start
== INT_MAX
2582 && lra_inheritance_iter
> LRA_MAX_INHERITANCE_PASSES
2583 && lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
2584 /* After switching off inheritance and rematerialization
2585 passes, avoid spilling reload pseudos will be created to
2586 prevent LRA cycling in some complicated cases. */
2587 lra_bad_spill_regno_start
= lra_constraint_new_regno_start
;
2588 lra_assignment_iter_after_spill
= 0;
2590 restore_scratches ();
2591 lra_eliminate (true, false);
2592 lra_final_code_change ();
2593 lra_in_progress
= 0;
2595 lra_clear_live_ranges ();
2596 lra_live_ranges_finish ();
2597 lra_constraints_finish ();
2599 sbitmap_free (lra_constraint_insn_stack_bitmap
);
2600 lra_constraint_insn_stack
.release ();
2601 finish_insn_recog_data ();
2602 regstat_free_n_sets_and_refs ();
2604 reload_completed
= 1;
2605 update_inc_notes ();
2607 inserted_p
= fixup_abnormal_edges ();
2609 /* We've possibly turned single trapping insn into multiple ones. */
2610 if (cfun
->can_throw_non_call_exceptions
)
2612 auto_sbitmap
blocks (last_basic_block_for_fn (cfun
));
2613 bitmap_ones (blocks
);
2614 find_many_sub_basic_blocks (blocks
);
2618 commit_edge_insertions ();
2620 /* Replacing pseudos with their memory equivalents might have
2621 created shared rtx. Subsequent passes would get confused
2622 by this, so unshare everything here. */
2623 unshare_all_rtl_again (get_insns ());
2628 timevar_pop (TV_LRA
);
2631 /* Called once per compiler to initialize LRA data once. */
2633 lra_init_once (void)
2635 init_insn_code_data_once ();
2638 /* Called once per compiler to finish LRA data which are initialize
2641 lra_finish_once (void)
2643 finish_insn_code_data_once ();