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"
124 #include "function-abi.h"
126 /* Dump bitmap SET with TITLE and BB INDEX. */
128 lra_dump_bitmap_with_title (const char *title
, bitmap set
, int index
)
133 static const int max_nums_on_line
= 10;
135 if (bitmap_empty_p (set
))
137 fprintf (lra_dump_file
, " %s %d:", title
, index
);
138 fprintf (lra_dump_file
, "\n");
139 count
= max_nums_on_line
+ 1;
140 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
142 if (count
> max_nums_on_line
)
144 fprintf (lra_dump_file
, "\n ");
147 fprintf (lra_dump_file
, " %4u", i
);
150 fprintf (lra_dump_file
, "\n");
153 /* Hard registers currently not available for allocation. It can
154 changed after some hard registers become not eliminable. */
155 HARD_REG_SET lra_no_alloc_regs
;
157 static int get_new_reg_value (void);
158 static void expand_reg_info (void);
159 static void invalidate_insn_recog_data (int);
160 static int get_insn_freq (rtx_insn
*);
161 static void invalidate_insn_data_regno_info (lra_insn_recog_data_t
,
163 static void remove_scratches_1 (rtx_insn
*);
165 /* Expand all regno related info needed for LRA. */
167 expand_reg_data (int old
)
171 ira_expand_reg_equiv ();
172 for (int i
= (int) max_reg_num () - 1; i
>= old
; i
--)
173 lra_change_class (i
, ALL_REGS
, " Set", true);
176 /* Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL
177 or of VOIDmode, use MD_MODE for the new reg. Initialize its
178 register class to RCLASS. Print message about assigning class
179 RCLASS containing new register name TITLE unless it is NULL. Use
180 attributes of ORIGINAL if it is a register. The created register
181 will have unique held value. */
183 lra_create_new_reg_with_unique_value (machine_mode md_mode
, rtx original
,
184 enum reg_class rclass
, const char *title
)
189 if (original
== NULL_RTX
|| (mode
= GET_MODE (original
)) == VOIDmode
)
191 lra_assert (mode
!= VOIDmode
);
192 new_reg
= gen_reg_rtx (mode
);
193 if (original
== NULL_RTX
|| ! REG_P (original
))
195 if (lra_dump_file
!= NULL
)
196 fprintf (lra_dump_file
, " Creating newreg=%i", REGNO (new_reg
));
200 if (ORIGINAL_REGNO (original
) >= FIRST_PSEUDO_REGISTER
)
201 ORIGINAL_REGNO (new_reg
) = ORIGINAL_REGNO (original
);
202 REG_USERVAR_P (new_reg
) = REG_USERVAR_P (original
);
203 REG_POINTER (new_reg
) = REG_POINTER (original
);
204 REG_ATTRS (new_reg
) = REG_ATTRS (original
);
205 if (lra_dump_file
!= NULL
)
206 fprintf (lra_dump_file
, " Creating newreg=%i from oldreg=%i",
207 REGNO (new_reg
), REGNO (original
));
209 if (lra_dump_file
!= NULL
)
212 fprintf (lra_dump_file
, ", assigning class %s to%s%s r%d",
213 reg_class_names
[rclass
], *title
== '\0' ? "" : " ",
214 title
, REGNO (new_reg
));
215 fprintf (lra_dump_file
, "\n");
217 expand_reg_data (max_reg_num ());
218 setup_reg_classes (REGNO (new_reg
), rclass
, NO_REGS
, rclass
);
222 /* Analogous to the previous function but also inherits value of
225 lra_create_new_reg (machine_mode md_mode
, rtx original
,
226 enum reg_class rclass
, const char *title
)
231 = lra_create_new_reg_with_unique_value (md_mode
, original
, rclass
, title
);
232 if (original
!= NULL_RTX
&& REG_P (original
))
233 lra_assign_reg_val (REGNO (original
), REGNO (new_reg
));
237 /* Set up for REGNO unique hold value. */
239 lra_set_regno_unique_value (int regno
)
241 lra_reg_info
[regno
].val
= get_new_reg_value ();
244 /* Invalidate INSN related info used by LRA. The info should never be
247 lra_invalidate_insn_data (rtx_insn
*insn
)
249 lra_invalidate_insn_regno_info (insn
);
250 invalidate_insn_recog_data (INSN_UID (insn
));
253 /* Mark INSN deleted and invalidate the insn related info used by
256 lra_set_insn_deleted (rtx_insn
*insn
)
258 lra_invalidate_insn_data (insn
);
259 SET_INSN_DELETED (insn
);
262 /* Delete an unneeded INSN and any previous insns who sole purpose is
263 loading data that is dead in INSN. */
265 lra_delete_dead_insn (rtx_insn
*insn
)
267 rtx_insn
*prev
= prev_real_insn (insn
);
270 /* If the previous insn sets a register that dies in our insn,
272 if (prev
&& GET_CODE (PATTERN (prev
)) == SET
273 && (prev_dest
= SET_DEST (PATTERN (prev
)), REG_P (prev_dest
))
274 && reg_mentioned_p (prev_dest
, PATTERN (insn
))
275 && find_regno_note (insn
, REG_DEAD
, REGNO (prev_dest
))
276 && ! side_effects_p (SET_SRC (PATTERN (prev
))))
277 lra_delete_dead_insn (prev
);
279 lra_set_insn_deleted (insn
);
282 /* Emit insn x = y + z. Return NULL if we failed to do it.
283 Otherwise, return the insn. We don't use gen_add3_insn as it might
286 emit_add3_insn (rtx x
, rtx y
, rtx z
)
290 last
= get_last_insn ();
292 if (have_addptr3_insn (x
, y
, z
))
294 rtx_insn
*insn
= gen_addptr3_insn (x
, y
, z
);
296 /* If the target provides an "addptr" pattern it hopefully does
297 for a reason. So falling back to the normal add would be
299 lra_assert (insn
!= NULL_RTX
);
304 rtx_insn
*insn
= emit_insn (gen_rtx_SET (x
, gen_rtx_PLUS (GET_MODE (y
),
306 if (recog_memoized (insn
) < 0)
308 delete_insns_since (last
);
314 /* Emit insn x = x + y. Return the insn. We use gen_add2_insn as the
317 emit_add2_insn (rtx x
, rtx y
)
319 rtx_insn
*insn
= emit_add3_insn (x
, x
, y
);
320 if (insn
== NULL_RTX
)
322 insn
= gen_add2_insn (x
, y
);
323 if (insn
!= NULL_RTX
)
329 /* Target checks operands through operand predicates to recognize an
330 insn. We should have a special precaution to generate add insns
331 which are frequent results of elimination.
333 Emit insns for x = y + z. X can be used to store intermediate
334 values and should be not in Y and Z when we use X to store an
335 intermediate value. Y + Z should form [base] [+ index[ * scale]] [
336 + disp] where base and index are registers, disp and scale are
337 constants. Y should contain base if it is present, Z should
338 contain disp if any. index[*scale] can be part of Y or Z. */
340 lra_emit_add (rtx x
, rtx y
, rtx z
)
344 rtx a1
, a2
, base
, index
, disp
, scale
, index_scale
;
347 rtx_insn
*add3_insn
= emit_add3_insn (x
, y
, z
);
348 old
= max_reg_num ();
349 if (add3_insn
!= NULL
)
353 disp
= a2
= NULL_RTX
;
354 if (GET_CODE (y
) == PLUS
)
368 index_scale
= scale
= NULL_RTX
;
369 if (GET_CODE (a1
) == MULT
)
372 index
= XEXP (a1
, 0);
373 scale
= XEXP (a1
, 1);
376 else if (a2
!= NULL_RTX
&& GET_CODE (a2
) == MULT
)
379 index
= XEXP (a2
, 0);
380 scale
= XEXP (a2
, 1);
388 if ((base
!= NULL_RTX
&& ! (REG_P (base
) || GET_CODE (base
) == SUBREG
))
389 || (index
!= NULL_RTX
390 && ! (REG_P (index
) || GET_CODE (index
) == SUBREG
))
391 || (disp
!= NULL_RTX
&& ! CONSTANT_P (disp
))
392 || (scale
!= NULL_RTX
&& ! CONSTANT_P (scale
)))
394 /* Probably we have no 3 op add. Last chance is to use 2-op
395 add insn. To succeed, don't move Z to X as an address
396 segment always comes in Y. Otherwise, we might fail when
397 adding the address segment to register. */
398 lra_assert (x
!= y
&& x
!= z
);
399 emit_move_insn (x
, y
);
400 rtx_insn
*insn
= emit_add2_insn (x
, z
);
401 lra_assert (insn
!= NULL_RTX
);
405 if (index_scale
== NULL_RTX
)
407 if (disp
== NULL_RTX
)
409 /* Generate x = index_scale; x = x + base. */
410 lra_assert (index_scale
!= NULL_RTX
&& base
!= NULL_RTX
);
411 emit_move_insn (x
, index_scale
);
412 rtx_insn
*insn
= emit_add2_insn (x
, base
);
413 lra_assert (insn
!= NULL_RTX
);
415 else if (scale
== NULL_RTX
)
417 /* Try x = base + disp. */
418 lra_assert (base
!= NULL_RTX
);
419 last
= get_last_insn ();
420 rtx_insn
*move_insn
=
421 emit_move_insn (x
, gen_rtx_PLUS (GET_MODE (base
), base
, disp
));
422 if (recog_memoized (move_insn
) < 0)
424 delete_insns_since (last
);
425 /* Generate x = disp; x = x + base. */
426 emit_move_insn (x
, disp
);
427 rtx_insn
*add2_insn
= emit_add2_insn (x
, base
);
428 lra_assert (add2_insn
!= NULL_RTX
);
430 /* Generate x = x + index. */
431 if (index
!= NULL_RTX
)
433 rtx_insn
*insn
= emit_add2_insn (x
, index
);
434 lra_assert (insn
!= NULL_RTX
);
439 /* Try x = index_scale; x = x + disp; x = x + base. */
440 last
= get_last_insn ();
441 rtx_insn
*move_insn
= emit_move_insn (x
, index_scale
);
443 if (recog_memoized (move_insn
) >= 0)
445 rtx_insn
*insn
= emit_add2_insn (x
, disp
);
446 if (insn
!= NULL_RTX
)
448 if (base
== NULL_RTX
)
452 insn
= emit_add2_insn (x
, base
);
453 if (insn
!= NULL_RTX
)
462 delete_insns_since (last
);
463 /* Generate x = disp; x = x + base; x = x + index_scale. */
464 emit_move_insn (x
, disp
);
465 if (base
!= NULL_RTX
)
467 insn
= emit_add2_insn (x
, base
);
468 lra_assert (insn
!= NULL_RTX
);
470 insn
= emit_add2_insn (x
, index_scale
);
471 lra_assert (insn
!= NULL_RTX
);
476 /* Functions emit_... can create pseudos -- so expand the pseudo
478 if (old
!= max_reg_num ())
479 expand_reg_data (old
);
482 /* The number of emitted reload insns so far. */
483 int lra_curr_reload_num
;
485 /* Emit x := y, processing special case when y = u + v or y = u + v *
486 scale + w through emit_add (Y can be an address which is base +
487 index reg * scale + displacement in general case). X may be used
488 as intermediate result therefore it should be not in Y. */
490 lra_emit_move (rtx x
, rtx y
)
494 if (GET_CODE (y
) != PLUS
)
496 if (rtx_equal_p (x
, y
))
498 old
= max_reg_num ();
499 rtx_insn
*insn
= emit_move_insn (x
, y
);
500 /* The move pattern may require scratch registers, so convert them
501 into real registers now. */
502 if (insn
!= NULL_RTX
)
503 remove_scratches_1 (insn
);
505 lra_reg_info
[ORIGINAL_REGNO (x
)].last_reload
= ++lra_curr_reload_num
;
506 /* Function emit_move can create pseudos -- so expand the pseudo
508 if (old
!= max_reg_num ())
509 expand_reg_data (old
);
512 lra_emit_add (x
, XEXP (y
, 0), XEXP (y
, 1));
515 /* Update insn operands which are duplication of operands whose
516 numbers are in array of NOPS (with end marker -1). The insn is
517 represented by its LRA internal representation ID. */
519 lra_update_dups (lra_insn_recog_data_t id
, signed char *nops
)
522 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
524 for (i
= 0; i
< static_id
->n_dups
; i
++)
525 for (j
= 0; (nop
= nops
[j
]) >= 0; j
++)
526 if (static_id
->dup_num
[i
] == nop
)
527 *id
->dup_loc
[i
] = *id
->operand_loc
[nop
];
532 /* This page contains code dealing with info about registers in the
535 /* Pools for insn reg info. */
536 object_allocator
<lra_insn_reg
> lra_insn_reg_pool ("insn regs");
538 /* Create LRA insn related info about a reference to REGNO in INSN
539 with TYPE (in/out/inout), biggest reference mode MODE, flag that it
540 is reference through subreg (SUBREG_P), and reference to the next
541 insn reg info (NEXT). If REGNO can be early clobbered,
542 alternatives in which it can be early clobbered are given by
543 EARLY_CLOBBER_ALTS. */
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
)
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
;
563 /* Free insn reg info list IR. */
565 free_insn_regs (struct lra_insn_reg
*ir
)
567 struct lra_insn_reg
*next_ir
;
569 for (; ir
!= NULL
; ir
= next_ir
)
572 lra_insn_reg_pool
.remove (ir
);
576 /* Finish pool for insn reg info. */
578 finish_insn_regs (void)
580 lra_insn_reg_pool
.release ();
585 /* This page contains code dealing LRA insn info (or in other words
586 LRA internal insn representation). */
588 /* Map INSN_CODE -> the static insn data. This info is valid during
589 all translation unit. */
590 struct lra_static_insn_data
*insn_code_data
[NUM_INSN_CODES
];
592 /* Debug insns are represented as a special insn with one input
593 operand which is RTL expression in var_location. */
595 /* The following data are used as static insn operand data for all
596 debug insns. If structure lra_operand_data is changed, the
597 initializer should be changed too. */
598 static struct lra_operand_data debug_operand_data
=
600 NULL
, /* alternative */
601 0, /* early_clobber_alts */
602 E_VOIDmode
, /* We are not interesting in the operand mode. */
607 /* The following data are used as static insn data for all debug
608 bind insns. If structure lra_static_insn_data is changed, the
609 initializer should be changed too. */
610 static struct lra_static_insn_data debug_bind_static_data
=
613 0, /* Duplication operands #. */
614 -1, /* Commutative operand #. */
615 1, /* Operands #. There is only one operand which is debug RTL
617 0, /* Duplications #. */
618 0, /* Alternatives #. We are not interesting in alternatives
619 because we does not proceed debug_insns for reloads. */
620 NULL
, /* Hard registers referenced in machine description. */
621 NULL
/* Descriptions of operands in alternatives. */
624 /* The following data are used as static insn data for all debug
625 marker insns. If structure lra_static_insn_data is changed, the
626 initializer should be changed too. */
627 static struct lra_static_insn_data debug_marker_static_data
=
630 0, /* Duplication operands #. */
631 -1, /* Commutative operand #. */
632 0, /* Operands #. There isn't any operand. */
633 0, /* Duplications #. */
634 0, /* Alternatives #. We are not interesting in alternatives
635 because we does not proceed debug_insns for reloads. */
636 NULL
, /* Hard registers referenced in machine description. */
637 NULL
/* Descriptions of operands in alternatives. */
640 /* Called once per compiler work to initialize some LRA data related
643 init_insn_code_data_once (void)
645 memset (insn_code_data
, 0, sizeof (insn_code_data
));
648 /* Called once per compiler work to finalize some LRA data related to
651 finish_insn_code_data_once (void)
653 for (unsigned int i
= 0; i
< NUM_INSN_CODES
; i
++)
655 if (insn_code_data
[i
] != NULL
)
656 free (insn_code_data
[i
]);
660 /* Return static insn data, allocate and setup if necessary. Although
661 dup_num is static data (it depends only on icode), to set it up we
662 need to extract insn first. So recog_data should be valid for
663 normal insn (ICODE >= 0) before the call. */
664 static struct lra_static_insn_data
*
665 get_static_insn_data (int icode
, int nop
, int ndup
, int nalt
)
667 struct lra_static_insn_data
*data
;
670 lra_assert (icode
< (int) NUM_INSN_CODES
);
671 if (icode
>= 0 && (data
= insn_code_data
[icode
]) != NULL
)
673 lra_assert (nop
>= 0 && ndup
>= 0 && nalt
>= 0);
674 n_bytes
= sizeof (struct lra_static_insn_data
)
675 + sizeof (struct lra_operand_data
) * nop
676 + sizeof (int) * ndup
;
677 data
= XNEWVAR (struct lra_static_insn_data
, n_bytes
);
678 data
->operand_alternative
= NULL
;
679 data
->n_operands
= nop
;
681 data
->n_alternatives
= nalt
;
682 data
->operand
= ((struct lra_operand_data
*)
683 ((char *) data
+ sizeof (struct lra_static_insn_data
)));
684 data
->dup_num
= ((int *) ((char *) data
->operand
685 + sizeof (struct lra_operand_data
) * nop
));
690 insn_code_data
[icode
] = data
;
691 for (i
= 0; i
< nop
; i
++)
693 data
->operand
[i
].constraint
694 = insn_data
[icode
].operand
[i
].constraint
;
695 data
->operand
[i
].mode
= insn_data
[icode
].operand
[i
].mode
;
696 data
->operand
[i
].strict_low
= insn_data
[icode
].operand
[i
].strict_low
;
697 data
->operand
[i
].is_operator
698 = insn_data
[icode
].operand
[i
].is_operator
;
699 data
->operand
[i
].type
700 = (data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
701 : data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
703 data
->operand
[i
].is_address
= false;
705 for (i
= 0; i
< ndup
; i
++)
706 data
->dup_num
[i
] = recog_data
.dup_num
[i
];
711 /* The current length of the following array. */
712 int lra_insn_recog_data_len
;
714 /* Map INSN_UID -> the insn recog data (NULL if unknown). */
715 lra_insn_recog_data_t
*lra_insn_recog_data
;
717 /* Initialize LRA data about insns. */
719 init_insn_recog_data (void)
721 lra_insn_recog_data_len
= 0;
722 lra_insn_recog_data
= NULL
;
725 /* Expand, if necessary, LRA data about insns. */
727 check_and_expand_insn_recog_data (int index
)
731 if (lra_insn_recog_data_len
> index
)
733 old
= lra_insn_recog_data_len
;
734 lra_insn_recog_data_len
= index
* 3 / 2 + 1;
735 lra_insn_recog_data
= XRESIZEVEC (lra_insn_recog_data_t
,
737 lra_insn_recog_data_len
);
738 for (i
= old
; i
< lra_insn_recog_data_len
; i
++)
739 lra_insn_recog_data
[i
] = NULL
;
742 /* Finish LRA DATA about insn. */
744 free_insn_recog_data (lra_insn_recog_data_t data
)
746 if (data
->operand_loc
!= NULL
)
747 free (data
->operand_loc
);
748 if (data
->dup_loc
!= NULL
)
749 free (data
->dup_loc
);
750 if (data
->arg_hard_regs
!= NULL
)
751 free (data
->arg_hard_regs
);
752 if (data
->icode
< 0 && NONDEBUG_INSN_P (data
->insn
))
754 if (data
->insn_static_data
->operand_alternative
!= NULL
)
755 free (const_cast <operand_alternative
*>
756 (data
->insn_static_data
->operand_alternative
));
757 free_insn_regs (data
->insn_static_data
->hard_regs
);
758 free (data
->insn_static_data
);
760 free_insn_regs (data
->regs
);
765 /* Pools for copies. */
766 static object_allocator
<lra_copy
> lra_copy_pool ("lra copies");
768 /* Finish LRA data about all insns. */
770 finish_insn_recog_data (void)
773 lra_insn_recog_data_t data
;
775 for (i
= 0; i
< lra_insn_recog_data_len
; i
++)
776 if ((data
= lra_insn_recog_data
[i
]) != NULL
)
777 free_insn_recog_data (data
);
779 lra_copy_pool
.release ();
780 lra_insn_reg_pool
.release ();
781 free (lra_insn_recog_data
);
784 /* Setup info about operands in alternatives of LRA DATA of insn. */
786 setup_operand_alternative (lra_insn_recog_data_t data
,
787 const operand_alternative
*op_alt
)
790 int icode
= data
->icode
;
791 struct lra_static_insn_data
*static_data
= data
->insn_static_data
;
793 static_data
->commutative
= -1;
794 nop
= static_data
->n_operands
;
795 nalt
= static_data
->n_alternatives
;
796 static_data
->operand_alternative
= op_alt
;
797 for (i
= 0; i
< nop
; i
++)
799 static_data
->operand
[i
].early_clobber_alts
= 0;
800 static_data
->operand
[i
].is_address
= false;
801 if (static_data
->operand
[i
].constraint
[0] == '%')
803 /* We currently only support one commutative pair of operands. */
804 if (static_data
->commutative
< 0)
805 static_data
->commutative
= i
;
807 lra_assert (icode
< 0); /* Asm */
808 /* The last operand should not be marked commutative. */
809 lra_assert (i
!= nop
- 1);
812 for (j
= 0; j
< nalt
; j
++)
813 for (i
= 0; i
< nop
; i
++, op_alt
++)
815 if (op_alt
->earlyclobber
)
816 static_data
->operand
[i
].early_clobber_alts
|= (alternative_mask
) 1 << j
;
817 static_data
->operand
[i
].is_address
|= op_alt
->is_address
;
821 /* Recursively process X and collect info about registers, which are
822 not the insn operands, in X with TYPE (in/out/inout) and flag that
823 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
824 to LIST. X is a part of insn given by DATA. Return the result
826 static struct lra_insn_reg
*
827 collect_non_operand_hard_regs (rtx_insn
*insn
, rtx
*x
,
828 lra_insn_recog_data_t data
,
829 struct lra_insn_reg
*list
,
830 enum op_type type
, bool early_clobber
)
832 int i
, j
, regno
, last
;
835 struct lra_insn_reg
*curr
;
837 enum rtx_code code
= GET_CODE (op
);
838 const char *fmt
= GET_RTX_FORMAT (code
);
840 for (i
= 0; i
< data
->insn_static_data
->n_operands
; i
++)
841 if (! data
->insn_static_data
->operand
[i
].is_operator
842 && x
== data
->operand_loc
[i
])
843 /* It is an operand loc. Stop here. */
845 for (i
= 0; i
< data
->insn_static_data
->n_dups
; i
++)
846 if (x
== data
->dup_loc
[i
])
847 /* It is a dup loc. Stop here. */
849 mode
= GET_MODE (op
);
853 mode
= wider_subreg_mode (op
);
854 if (read_modify_subreg_p (op
))
856 op
= SUBREG_REG (op
);
857 code
= GET_CODE (op
);
861 if ((regno
= REGNO (op
)) >= FIRST_PSEUDO_REGISTER
)
863 /* Process all regs even unallocatable ones as we need info
864 about all regs for rematerialization pass. */
865 for (last
= end_hard_regno (mode
, regno
); regno
< last
; regno
++)
867 for (curr
= list
; curr
!= NULL
; curr
= curr
->next
)
868 if (curr
->regno
== regno
&& curr
->subreg_p
== subreg_p
869 && curr
->biggest_mode
== mode
)
871 if (curr
->type
!= type
)
872 curr
->type
= OP_INOUT
;
874 curr
->early_clobber_alts
= ALL_ALTERNATIVES
;
879 /* This is a new hard regno or the info cannot be
880 integrated into the found structure. */
884 /* This clobber is to inform popping floating
886 && ! (FIRST_STACK_REG
<= regno
887 && regno
<= LAST_STACK_REG
));
889 list
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
890 early_clobber
? ALL_ALTERNATIVES
: 0, list
);
898 list
= collect_non_operand_hard_regs (insn
, &SET_DEST (op
), data
,
899 list
, OP_OUT
, false);
900 list
= collect_non_operand_hard_regs (insn
, &SET_SRC (op
), data
,
904 /* We treat clobber of non-operand hard registers as early clobber. */
905 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
908 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
909 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
910 list
, OP_INOUT
, false);
912 case PRE_MODIFY
: case POST_MODIFY
:
913 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
914 list
, OP_INOUT
, false);
915 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 1), data
,
919 fmt
= GET_RTX_FORMAT (code
);
920 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
923 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, i
), data
,
925 else if (fmt
[i
] == 'E')
926 for (j
= XVECLEN (op
, i
) - 1; j
>= 0; j
--)
927 list
= collect_non_operand_hard_regs (insn
, &XVECEXP (op
, i
, j
),
928 data
, list
, OP_IN
, false);
934 /* Set up and return info about INSN. Set up the info if it is not set up
936 lra_insn_recog_data_t
937 lra_set_insn_recog_data (rtx_insn
*insn
)
939 lra_insn_recog_data_t data
;
942 unsigned int uid
= INSN_UID (insn
);
943 struct lra_static_insn_data
*insn_static_data
;
945 check_and_expand_insn_recog_data (uid
);
946 if (DEBUG_INSN_P (insn
))
950 icode
= INSN_CODE (insn
);
952 /* It might be a new simple insn which is not recognized yet. */
953 INSN_CODE (insn
) = icode
= recog_memoized (insn
);
955 data
= XNEW (class lra_insn_recog_data
);
956 lra_insn_recog_data
[uid
] = data
;
958 data
->used_insn_alternative
= LRA_UNKNOWN_ALT
;
961 if (DEBUG_INSN_P (insn
))
963 data
->dup_loc
= NULL
;
964 data
->arg_hard_regs
= NULL
;
965 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
966 if (DEBUG_BIND_INSN_P (insn
))
968 data
->insn_static_data
= &debug_bind_static_data
;
969 data
->operand_loc
= XNEWVEC (rtx
*, 1);
970 data
->operand_loc
[0] = &INSN_VAR_LOCATION_LOC (insn
);
972 else if (DEBUG_MARKER_INSN_P (insn
))
974 data
->insn_static_data
= &debug_marker_static_data
;
975 data
->operand_loc
= NULL
;
982 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
983 const char *constraints
[MAX_RECOG_OPERANDS
];
985 nop
= asm_noperands (PATTERN (insn
));
986 data
->operand_loc
= data
->dup_loc
= NULL
;
990 /* It is a special insn like USE or CLOBBER. We should
991 recognize any regular insn otherwise LRA can do nothing
993 gcc_assert (GET_CODE (PATTERN (insn
)) == USE
994 || GET_CODE (PATTERN (insn
)) == CLOBBER
995 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
996 data
->insn_static_data
= insn_static_data
997 = get_static_insn_data (-1, 0, 0, nalt
);
1001 /* expand_asm_operands makes sure there aren't too many
1003 lra_assert (nop
<= MAX_RECOG_OPERANDS
);
1005 data
->operand_loc
= XNEWVEC (rtx
*, nop
);
1006 /* Now get the operand values and constraints out of the
1008 decode_asm_operands (PATTERN (insn
), NULL
,
1010 constraints
, operand_mode
, NULL
);
1012 for (const char *p
=constraints
[0]; *p
; p
++)
1014 data
->insn_static_data
= insn_static_data
1015 = get_static_insn_data (-1, nop
, 0, nalt
);
1016 for (i
= 0; i
< nop
; i
++)
1018 insn_static_data
->operand
[i
].mode
= operand_mode
[i
];
1019 insn_static_data
->operand
[i
].constraint
= constraints
[i
];
1020 insn_static_data
->operand
[i
].strict_low
= false;
1021 insn_static_data
->operand
[i
].is_operator
= false;
1022 insn_static_data
->operand
[i
].is_address
= false;
1025 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1026 insn_static_data
->operand
[i
].type
1027 = (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1028 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1030 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
1033 operand_alternative
*op_alt
= XCNEWVEC (operand_alternative
,
1035 preprocess_constraints (nop
, nalt
, constraints
, op_alt
,
1037 setup_operand_alternative (data
, op_alt
);
1042 insn_extract (insn
);
1043 data
->insn_static_data
= insn_static_data
1044 = get_static_insn_data (icode
, insn_data
[icode
].n_operands
,
1045 insn_data
[icode
].n_dups
,
1046 insn_data
[icode
].n_alternatives
);
1047 n
= insn_static_data
->n_operands
;
1052 locs
= XNEWVEC (rtx
*, n
);
1053 memcpy (locs
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1055 data
->operand_loc
= locs
;
1056 n
= insn_static_data
->n_dups
;
1061 locs
= XNEWVEC (rtx
*, n
);
1062 memcpy (locs
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1064 data
->dup_loc
= locs
;
1065 data
->preferred_alternatives
= get_preferred_alternatives (insn
);
1066 const operand_alternative
*op_alt
= preprocess_insn_constraints (icode
);
1067 if (!insn_static_data
->operand_alternative
)
1068 setup_operand_alternative (data
, op_alt
);
1069 else if (op_alt
!= insn_static_data
->operand_alternative
)
1070 insn_static_data
->operand_alternative
= op_alt
;
1072 if (GET_CODE (PATTERN (insn
)) == CLOBBER
|| GET_CODE (PATTERN (insn
)) == USE
)
1073 insn_static_data
->hard_regs
= NULL
;
1075 insn_static_data
->hard_regs
1076 = collect_non_operand_hard_regs (insn
, &PATTERN (insn
), data
,
1077 NULL
, OP_IN
, false);
1078 data
->arg_hard_regs
= NULL
;
1083 int n_hard_regs
, regno
, arg_hard_regs
[FIRST_PSEUDO_REGISTER
];
1086 /* Finding implicit hard register usage. We believe it will be
1087 not changed whatever transformations are used. Call insns
1088 are such example. */
1089 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1091 link
= XEXP (link
, 1))
1092 if (((use_p
= GET_CODE (XEXP (link
, 0)) == USE
)
1093 || GET_CODE (XEXP (link
, 0)) == CLOBBER
)
1094 && REG_P (XEXP (XEXP (link
, 0), 0)))
1096 regno
= REGNO (XEXP (XEXP (link
, 0), 0));
1097 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
1098 /* It is an argument register. */
1099 for (i
= REG_NREGS (XEXP (XEXP (link
, 0), 0)) - 1; i
>= 0; i
--)
1100 arg_hard_regs
[n_hard_regs
++]
1101 = regno
+ i
+ (use_p
? 0 : FIRST_PSEUDO_REGISTER
);
1104 if (n_hard_regs
!= 0)
1106 arg_hard_regs
[n_hard_regs
++] = -1;
1107 data
->arg_hard_regs
= XNEWVEC (int, n_hard_regs
);
1108 memcpy (data
->arg_hard_regs
, arg_hard_regs
,
1109 sizeof (int) * n_hard_regs
);
1112 /* Some output operand can be recognized only from the context not
1113 from the constraints which are empty in this case. Call insn may
1114 contain a hard register in set destination with empty constraint
1115 and extract_insn treats them as an input. */
1116 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1120 struct lra_operand_data
*operand
= &insn_static_data
->operand
[i
];
1122 /* ??? Should we treat 'X' the same way. It looks to me that
1123 'X' means anything and empty constraint means we do not
1125 if (operand
->type
!= OP_IN
|| *operand
->constraint
!= '\0'
1126 || operand
->is_operator
)
1128 pat
= PATTERN (insn
);
1129 if (GET_CODE (pat
) == SET
)
1131 if (data
->operand_loc
[i
] != &SET_DEST (pat
))
1134 else if (GET_CODE (pat
) == PARALLEL
)
1136 for (j
= XVECLEN (pat
, 0) - 1; j
>= 0; j
--)
1138 set
= XVECEXP (PATTERN (insn
), 0, j
);
1139 if (GET_CODE (set
) == SET
1140 && &SET_DEST (set
) == data
->operand_loc
[i
])
1148 operand
->type
= OP_OUT
;
1153 /* Return info about insn give by UID. The info should be already set
1155 static lra_insn_recog_data_t
1156 get_insn_recog_data_by_uid (int uid
)
1158 lra_insn_recog_data_t data
;
1160 data
= lra_insn_recog_data
[uid
];
1161 lra_assert (data
!= NULL
);
1165 /* Invalidate all info about insn given by its UID. */
1167 invalidate_insn_recog_data (int uid
)
1169 lra_insn_recog_data_t data
;
1171 data
= lra_insn_recog_data
[uid
];
1172 lra_assert (data
!= NULL
);
1173 free_insn_recog_data (data
);
1174 lra_insn_recog_data
[uid
] = NULL
;
1177 /* Update all the insn info about INSN. It is usually called when
1178 something in the insn was changed. Return the updated info. */
1179 lra_insn_recog_data_t
1180 lra_update_insn_recog_data (rtx_insn
*insn
)
1182 lra_insn_recog_data_t data
;
1184 unsigned int uid
= INSN_UID (insn
);
1185 struct lra_static_insn_data
*insn_static_data
;
1186 poly_int64 sp_offset
= 0;
1188 check_and_expand_insn_recog_data (uid
);
1189 if ((data
= lra_insn_recog_data
[uid
]) != NULL
1190 && data
->icode
!= INSN_CODE (insn
))
1192 sp_offset
= data
->sp_offset
;
1193 invalidate_insn_data_regno_info (data
, insn
, get_insn_freq (insn
));
1194 invalidate_insn_recog_data (uid
);
1199 data
= lra_get_insn_recog_data (insn
);
1200 /* Initiate or restore SP offset. */
1201 data
->sp_offset
= sp_offset
;
1204 insn_static_data
= data
->insn_static_data
;
1205 data
->used_insn_alternative
= LRA_UNKNOWN_ALT
;
1206 if (DEBUG_INSN_P (insn
))
1208 if (data
->icode
< 0)
1211 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
1212 const char *constraints
[MAX_RECOG_OPERANDS
];
1214 nop
= asm_noperands (PATTERN (insn
));
1217 lra_assert (nop
== data
->insn_static_data
->n_operands
);
1218 /* Now get the operand values and constraints out of the
1220 decode_asm_operands (PATTERN (insn
), NULL
,
1222 constraints
, operand_mode
, NULL
);
1225 for (int i
= 0; i
< nop
; i
++)
1227 (insn_static_data
->operand
[i
].mode
== operand_mode
[i
]
1228 && insn_static_data
->operand
[i
].constraint
== constraints
[i
]
1229 && ! insn_static_data
->operand
[i
].is_operator
);
1233 for (int i
= 0; i
< insn_static_data
->n_operands
; i
++)
1235 (insn_static_data
->operand
[i
].type
1236 == (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1237 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1242 insn_extract (insn
);
1243 n
= insn_static_data
->n_operands
;
1245 memcpy (data
->operand_loc
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1246 n
= insn_static_data
->n_dups
;
1248 memcpy (data
->dup_loc
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1249 lra_assert (check_bool_attrs (insn
));
1254 /* Set up that INSN is using alternative ALT now. */
1256 lra_set_used_insn_alternative (rtx_insn
*insn
, int alt
)
1258 lra_insn_recog_data_t data
;
1260 data
= lra_get_insn_recog_data (insn
);
1261 data
->used_insn_alternative
= alt
;
1264 /* Set up that insn with UID is using alternative ALT now. The insn
1265 info should be already set up. */
1267 lra_set_used_insn_alternative_by_uid (int uid
, int alt
)
1269 lra_insn_recog_data_t data
;
1271 check_and_expand_insn_recog_data (uid
);
1272 data
= lra_insn_recog_data
[uid
];
1273 lra_assert (data
!= NULL
);
1274 data
->used_insn_alternative
= alt
;
1279 /* This page contains code dealing with common register info and
1282 /* The size of the following array. */
1283 static int reg_info_size
;
1284 /* Common info about each register. */
1285 class lra_reg
*lra_reg_info
;
1287 HARD_REG_SET hard_regs_spilled_into
;
1289 /* Last register value. */
1290 static int last_reg_value
;
1292 /* Return new register value. */
1294 get_new_reg_value (void)
1296 return ++last_reg_value
;
1299 /* Vec referring to pseudo copies. */
1300 static vec
<lra_copy_t
> copy_vec
;
1302 /* Initialize I-th element of lra_reg_info. */
1304 initialize_lra_reg_info_element (int i
)
1306 bitmap_initialize (&lra_reg_info
[i
].insn_bitmap
, ®_obstack
);
1308 lra_reg_info
[i
].no_stack_p
= false;
1310 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
1311 lra_reg_info
[i
].preferred_hard_regno1
= -1;
1312 lra_reg_info
[i
].preferred_hard_regno2
= -1;
1313 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
1314 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
1315 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
1316 lra_reg_info
[i
].live_ranges
= NULL
;
1317 lra_reg_info
[i
].nrefs
= lra_reg_info
[i
].freq
= 0;
1318 lra_reg_info
[i
].last_reload
= 0;
1319 lra_reg_info
[i
].restore_rtx
= NULL_RTX
;
1320 lra_reg_info
[i
].val
= get_new_reg_value ();
1321 lra_reg_info
[i
].offset
= 0;
1322 lra_reg_info
[i
].copies
= NULL
;
1325 /* Initialize common reg info and copies. */
1327 init_reg_info (void)
1332 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1333 lra_reg_info
= XNEWVEC (class lra_reg
, reg_info_size
);
1334 for (i
= 0; i
< reg_info_size
; i
++)
1335 initialize_lra_reg_info_element (i
);
1336 copy_vec
.truncate (0);
1337 CLEAR_HARD_REG_SET (hard_regs_spilled_into
);
1341 /* Finish common reg info and copies. */
1343 finish_reg_info (void)
1347 for (i
= 0; i
< reg_info_size
; i
++)
1348 bitmap_clear (&lra_reg_info
[i
].insn_bitmap
);
1349 free (lra_reg_info
);
1353 /* Expand common reg info if it is necessary. */
1355 expand_reg_info (void)
1357 int i
, old
= reg_info_size
;
1359 if (reg_info_size
> max_reg_num ())
1361 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1362 lra_reg_info
= XRESIZEVEC (class lra_reg
, lra_reg_info
, reg_info_size
);
1363 for (i
= old
; i
< reg_info_size
; i
++)
1364 initialize_lra_reg_info_element (i
);
1367 /* Free all copies. */
1369 lra_free_copies (void)
1373 while (copy_vec
.length () != 0)
1375 cp
= copy_vec
.pop ();
1376 lra_reg_info
[cp
->regno1
].copies
= lra_reg_info
[cp
->regno2
].copies
= NULL
;
1377 lra_copy_pool
.remove (cp
);
1381 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1382 frequency is FREQ. */
1384 lra_create_copy (int regno1
, int regno2
, int freq
)
1389 lra_assert (regno1
!= regno2
);
1390 regno1_dest_p
= true;
1391 if (regno1
> regno2
)
1393 std::swap (regno1
, regno2
);
1394 regno1_dest_p
= false;
1396 cp
= lra_copy_pool
.allocate ();
1397 copy_vec
.safe_push (cp
);
1398 cp
->regno1_dest_p
= regno1_dest_p
;
1400 cp
->regno1
= regno1
;
1401 cp
->regno2
= regno2
;
1402 cp
->regno1_next
= lra_reg_info
[regno1
].copies
;
1403 lra_reg_info
[regno1
].copies
= cp
;
1404 cp
->regno2_next
= lra_reg_info
[regno2
].copies
;
1405 lra_reg_info
[regno2
].copies
= cp
;
1406 if (lra_dump_file
!= NULL
)
1407 fprintf (lra_dump_file
, " Creating copy r%d%sr%d@%d\n",
1408 regno1
, regno1_dest_p
? "<-" : "->", regno2
, freq
);
1411 /* Return N-th (0, 1, ...) copy. If there is no copy, return
1414 lra_get_copy (int n
)
1416 if (n
>= (int) copy_vec
.length ())
1423 /* This page contains code dealing with info about registers in
1426 /* Process X of INSN recursively and add info (operand type is given
1427 by TYPE) about registers in X to the insn DATA. If X can be early
1428 clobbered, alternatives in which it can be early clobbered are given
1429 by EARLY_CLOBBER_ALTS. */
1431 add_regs_to_insn_regno_info (lra_insn_recog_data_t data
, rtx x
,
1432 rtx_insn
*insn
, enum op_type type
,
1433 alternative_mask early_clobber_alts
)
1440 struct lra_insn_reg
*curr
;
1442 code
= GET_CODE (x
);
1443 mode
= GET_MODE (x
);
1445 if (GET_CODE (x
) == SUBREG
)
1447 mode
= wider_subreg_mode (x
);
1448 if (read_modify_subreg_p (x
))
1451 code
= GET_CODE (x
);
1456 /* Process all regs even unallocatable ones as we need info about
1457 all regs for rematerialization pass. */
1459 if (bitmap_set_bit (&lra_reg_info
[regno
].insn_bitmap
, INSN_UID (insn
)))
1461 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
1462 early_clobber_alts
, data
->regs
);
1467 for (curr
= data
->regs
; curr
!= NULL
; curr
= curr
->next
)
1468 if (curr
->regno
== regno
)
1470 if (curr
->subreg_p
!= subreg_p
|| curr
->biggest_mode
!= mode
)
1471 /* The info cannot be integrated into the found
1473 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
,
1474 subreg_p
, early_clobber_alts
,
1478 if (curr
->type
!= type
)
1479 curr
->type
= OP_INOUT
;
1480 curr
->early_clobber_alts
|= early_clobber_alts
;
1491 add_regs_to_insn_regno_info (data
, SET_DEST (x
), insn
, OP_OUT
, 0);
1492 add_regs_to_insn_regno_info (data
, SET_SRC (x
), insn
, OP_IN
, 0);
1495 /* We treat clobber of non-operand hard registers as early
1497 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), insn
, OP_OUT
,
1500 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
1501 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), insn
, OP_INOUT
, 0);
1503 case PRE_MODIFY
: case POST_MODIFY
:
1504 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), insn
, OP_INOUT
, 0);
1505 add_regs_to_insn_regno_info (data
, XEXP (x
, 1), insn
, OP_IN
, 0);
1508 if ((code
!= PARALLEL
&& code
!= EXPR_LIST
) || type
!= OP_OUT
)
1509 /* Some targets place small structures in registers for return
1510 values of functions, and those registers are wrapped in
1511 PARALLEL that we may see as the destination of a SET. Here
1514 (call_insn 13 12 14 2 (set (parallel:BLK [
1515 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1517 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1518 (const_int 8 [0x8]))
1520 (call (mem:QI (symbol_ref:DI (... */
1522 fmt
= GET_RTX_FORMAT (code
);
1523 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1526 add_regs_to_insn_regno_info (data
, XEXP (x
, i
), insn
, type
, 0);
1527 else if (fmt
[i
] == 'E')
1529 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1530 add_regs_to_insn_regno_info (data
, XVECEXP (x
, i
, j
), insn
,
1537 /* Return execution frequency of INSN. */
1539 get_insn_freq (rtx_insn
*insn
)
1541 basic_block bb
= BLOCK_FOR_INSN (insn
);
1543 gcc_checking_assert (bb
!= NULL
);
1544 return REG_FREQ_FROM_BB (bb
);
1547 /* Invalidate all reg info of INSN with DATA and execution frequency
1548 FREQ. Update common info about the invalidated registers. */
1550 invalidate_insn_data_regno_info (lra_insn_recog_data_t data
, rtx_insn
*insn
,
1556 struct lra_insn_reg
*ir
, *next_ir
;
1558 uid
= INSN_UID (insn
);
1559 debug_p
= DEBUG_INSN_P (insn
);
1560 for (ir
= data
->regs
; ir
!= NULL
; ir
= next_ir
)
1564 lra_insn_reg_pool
.remove (ir
);
1565 bitmap_clear_bit (&lra_reg_info
[i
].insn_bitmap
, uid
);
1566 if (i
>= FIRST_PSEUDO_REGISTER
&& ! debug_p
)
1568 lra_reg_info
[i
].nrefs
--;
1569 lra_reg_info
[i
].freq
-= freq
;
1570 lra_assert (lra_reg_info
[i
].nrefs
>= 0 && lra_reg_info
[i
].freq
>= 0);
1576 /* Invalidate all reg info of INSN. Update common info about the
1577 invalidated registers. */
1579 lra_invalidate_insn_regno_info (rtx_insn
*insn
)
1581 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn
), insn
,
1582 get_insn_freq (insn
));
1585 /* Update common reg info from reg info of insn given by its DATA and
1586 execution frequency FREQ. */
1588 setup_insn_reg_info (lra_insn_recog_data_t data
, int freq
)
1591 struct lra_insn_reg
*ir
;
1593 for (ir
= data
->regs
; ir
!= NULL
; ir
= ir
->next
)
1594 if ((i
= ir
->regno
) >= FIRST_PSEUDO_REGISTER
)
1596 lra_reg_info
[i
].nrefs
++;
1597 lra_reg_info
[i
].freq
+= freq
;
1601 /* Set up insn reg info of INSN. Update common reg info from reg info
1604 lra_update_insn_regno_info (rtx_insn
*insn
)
1607 lra_insn_recog_data_t data
;
1608 struct lra_static_insn_data
*static_data
;
1612 if (! INSN_P (insn
))
1614 data
= lra_get_insn_recog_data (insn
);
1615 static_data
= data
->insn_static_data
;
1616 freq
= NONDEBUG_INSN_P (insn
) ? get_insn_freq (insn
) : 0;
1617 invalidate_insn_data_regno_info (data
, insn
, freq
);
1618 for (i
= static_data
->n_operands
- 1; i
>= 0; i
--)
1619 add_regs_to_insn_regno_info (data
, *data
->operand_loc
[i
], insn
,
1620 static_data
->operand
[i
].type
,
1621 static_data
->operand
[i
].early_clobber_alts
);
1622 if ((code
= GET_CODE (PATTERN (insn
))) == CLOBBER
|| code
== USE
)
1623 add_regs_to_insn_regno_info (data
, XEXP (PATTERN (insn
), 0), insn
,
1624 code
== USE
? OP_IN
: OP_OUT
, 0);
1626 /* On some targets call insns can refer to pseudos in memory in
1627 CALL_INSN_FUNCTION_USAGE list. Process them in order to
1628 consider their occurrences in calls for different
1629 transformations (e.g. inheritance) with given pseudos. */
1630 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1632 link
= XEXP (link
, 1))
1634 code
= GET_CODE (XEXP (link
, 0));
1635 if ((code
== USE
|| code
== CLOBBER
)
1636 && MEM_P (XEXP (XEXP (link
, 0), 0)))
1637 add_regs_to_insn_regno_info (data
, XEXP (XEXP (link
, 0), 0), insn
,
1638 code
== USE
? OP_IN
: OP_OUT
, 0);
1640 if (NONDEBUG_INSN_P (insn
))
1641 setup_insn_reg_info (data
, freq
);
1644 /* Return reg info of insn given by it UID. */
1645 struct lra_insn_reg
*
1646 lra_get_insn_regs (int uid
)
1648 lra_insn_recog_data_t data
;
1650 data
= get_insn_recog_data_by_uid (uid
);
1656 /* Recursive hash function for RTL X. */
1658 lra_rtx_hash (rtx x
)
1668 code
= GET_CODE (x
);
1669 val
+= (int) code
+ 4095;
1671 /* Some RTL can be compared nonrecursively. */
1675 return val
+ REGNO (x
);
1678 return iterative_hash_object (XEXP (x
, 0), val
);
1681 return iterative_hash_object (XSTR (x
, 0), val
);
1689 return val
+ UINTVAL (x
);
1695 /* Hash the elements. */
1696 fmt
= GET_RTX_FORMAT (code
);
1697 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1702 val
+= XWINT (x
, i
);
1712 val
+= XVECLEN (x
, i
);
1714 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1715 val
+= lra_rtx_hash (XVECEXP (x
, i
, j
));
1719 val
+= lra_rtx_hash (XEXP (x
, i
));
1724 val
+= htab_hash_string (XSTR (x
, i
));
1732 /* It is believed that rtx's at this level will never
1733 contain anything but integers and other rtx's, except for
1734 within LABEL_REFs and SYMBOL_REFs. */
1744 /* This page contains code dealing with stack of the insns which
1745 should be processed by the next constraint pass. */
1747 /* Bitmap used to put an insn on the stack only in one exemplar. */
1748 static sbitmap lra_constraint_insn_stack_bitmap
;
1750 /* The stack itself. */
1751 vec
<rtx_insn
*> lra_constraint_insn_stack
;
1753 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1754 info for INSN, otherwise only update it if INSN is not already on the
1757 lra_push_insn_1 (rtx_insn
*insn
, bool always_update
)
1759 unsigned int uid
= INSN_UID (insn
);
1761 lra_update_insn_regno_info (insn
);
1762 if (uid
>= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap
))
1763 lra_constraint_insn_stack_bitmap
=
1764 sbitmap_resize (lra_constraint_insn_stack_bitmap
, 3 * uid
/ 2, 0);
1765 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap
, uid
))
1767 bitmap_set_bit (lra_constraint_insn_stack_bitmap
, uid
);
1768 if (! always_update
)
1769 lra_update_insn_regno_info (insn
);
1770 lra_constraint_insn_stack
.safe_push (insn
);
1773 /* Put INSN on the stack. */
1775 lra_push_insn (rtx_insn
*insn
)
1777 lra_push_insn_1 (insn
, false);
1780 /* Put INSN on the stack and update its reg info. */
1782 lra_push_insn_and_update_insn_regno_info (rtx_insn
*insn
)
1784 lra_push_insn_1 (insn
, true);
1787 /* Put insn with UID on the stack. */
1789 lra_push_insn_by_uid (unsigned int uid
)
1791 lra_push_insn (lra_insn_recog_data
[uid
]->insn
);
1794 /* Take the last-inserted insns off the stack and return it. */
1798 rtx_insn
*insn
= lra_constraint_insn_stack
.pop ();
1799 bitmap_clear_bit (lra_constraint_insn_stack_bitmap
, INSN_UID (insn
));
1803 /* Return the current size of the insn stack. */
1805 lra_insn_stack_length (void)
1807 return lra_constraint_insn_stack
.length ();
1810 /* Push insns FROM to TO (excluding it) going in reverse order. */
1812 push_insns (rtx_insn
*from
, rtx_insn
*to
)
1816 if (from
== NULL_RTX
)
1818 for (insn
= from
; insn
!= to
; insn
= PREV_INSN (insn
))
1820 lra_push_insn (insn
);
1823 /* Set up sp offset for insn in range [FROM, LAST]. The offset is
1824 taken from the next BB insn after LAST or zero if there in such
1827 setup_sp_offset (rtx_insn
*from
, rtx_insn
*last
)
1829 rtx_insn
*before
= next_nonnote_nondebug_insn_bb (last
);
1830 poly_int64 offset
= (before
== NULL_RTX
|| ! INSN_P (before
)
1831 ? 0 : lra_get_insn_recog_data (before
)->sp_offset
);
1833 for (rtx_insn
*insn
= from
; insn
!= NEXT_INSN (last
); insn
= NEXT_INSN (insn
))
1834 lra_get_insn_recog_data (insn
)->sp_offset
= offset
;
1837 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1838 insns onto the stack. Print about emitting the insns with
1841 lra_process_new_insns (rtx_insn
*insn
, rtx_insn
*before
, rtx_insn
*after
,
1846 if (before
== NULL_RTX
&& after
== NULL_RTX
)
1848 if (lra_dump_file
!= NULL
)
1850 dump_insn_slim (lra_dump_file
, insn
);
1851 if (before
!= NULL_RTX
)
1853 fprintf (lra_dump_file
," %s before:\n", title
);
1854 dump_rtl_slim (lra_dump_file
, before
, NULL
, -1, 0);
1856 if (after
!= NULL_RTX
)
1858 fprintf (lra_dump_file
, " %s after:\n", title
);
1859 dump_rtl_slim (lra_dump_file
, after
, NULL
, -1, 0);
1861 fprintf (lra_dump_file
, "\n");
1863 if (before
!= NULL_RTX
)
1865 if (cfun
->can_throw_non_call_exceptions
)
1866 copy_reg_eh_region_note_forward (insn
, before
, NULL
);
1867 emit_insn_before (before
, insn
);
1868 push_insns (PREV_INSN (insn
), PREV_INSN (before
));
1869 setup_sp_offset (before
, PREV_INSN (insn
));
1871 if (after
!= NULL_RTX
)
1873 if (cfun
->can_throw_non_call_exceptions
)
1874 copy_reg_eh_region_note_forward (insn
, after
, NULL
);
1875 for (last
= after
; NEXT_INSN (last
) != NULL_RTX
; last
= NEXT_INSN (last
))
1877 emit_insn_after (after
, insn
);
1878 push_insns (last
, insn
);
1879 setup_sp_offset (after
, last
);
1881 if (cfun
->can_throw_non_call_exceptions
)
1883 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
1884 if (note
&& !insn_could_throw_p (insn
))
1885 remove_note (insn
, note
);
1890 /* Replace all references to register OLD_REGNO in *LOC with pseudo
1891 register NEW_REG. Try to simplify subreg of constant if SUBREG_P.
1892 DEBUG_P is if LOC is within a DEBUG_INSN. Return true if any
1895 lra_substitute_pseudo (rtx
*loc
, int old_regno
, rtx new_reg
, bool subreg_p
,
1899 bool result
= false;
1907 code
= GET_CODE (x
);
1908 if (code
== SUBREG
&& subreg_p
)
1910 rtx subst
, inner
= SUBREG_REG (x
);
1911 /* Transform subreg of constant while we still have inner mode
1912 of the subreg. The subreg internal should not be an insn
1914 if (REG_P (inner
) && (int) REGNO (inner
) == old_regno
1915 && CONSTANT_P (new_reg
)
1916 && (subst
= simplify_subreg (GET_MODE (x
), new_reg
, GET_MODE (inner
),
1917 SUBREG_BYTE (x
))) != NULL_RTX
)
1924 else if (code
== REG
&& (int) REGNO (x
) == old_regno
)
1926 machine_mode mode
= GET_MODE (x
);
1927 machine_mode inner_mode
= GET_MODE (new_reg
);
1929 if (mode
!= inner_mode
1930 && ! (CONST_SCALAR_INT_P (new_reg
) && SCALAR_INT_MODE_P (mode
)))
1932 poly_uint64 offset
= 0;
1933 if (partial_subreg_p (mode
, inner_mode
)
1934 && SCALAR_INT_MODE_P (inner_mode
))
1935 offset
= subreg_lowpart_offset (mode
, inner_mode
);
1937 new_reg
= gen_rtx_raw_SUBREG (mode
, new_reg
, offset
);
1939 new_reg
= gen_rtx_SUBREG (mode
, new_reg
, offset
);
1945 /* Scan all the operand sub-expressions. */
1946 fmt
= GET_RTX_FORMAT (code
);
1947 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1951 if (lra_substitute_pseudo (&XEXP (x
, i
), old_regno
,
1952 new_reg
, subreg_p
, debug_p
))
1955 else if (fmt
[i
] == 'E')
1957 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1958 if (lra_substitute_pseudo (&XVECEXP (x
, i
, j
), old_regno
,
1959 new_reg
, subreg_p
, debug_p
))
1966 /* Call lra_substitute_pseudo within an insn. Try to simplify subreg
1967 of constant if SUBREG_P. This won't update the insn ptr, just the
1968 contents of the insn. */
1970 lra_substitute_pseudo_within_insn (rtx_insn
*insn
, int old_regno
,
1971 rtx new_reg
, bool subreg_p
)
1974 return lra_substitute_pseudo (&loc
, old_regno
, new_reg
, subreg_p
,
1975 DEBUG_INSN_P (insn
));
1980 /* This page contains code dealing with scratches (changing them onto
1981 pseudos and restoring them from the pseudos).
1983 We change scratches into pseudos at the beginning of LRA to
1984 simplify dealing with them (conflicts, hard register assignments).
1986 If the pseudo denoting scratch was spilled it means that we do need
1987 a hard register for it. Such pseudos are transformed back to
1988 scratches at the end of LRA. */
1990 /* Description of location of a former scratch operand. */
1993 rtx_insn
*insn
; /* Insn where the scratch was. */
1994 int nop
; /* Number of the operand which was a scratch. */
1995 int icode
; /* Original icode from which scratch was removed. */
1998 typedef struct sloc
*sloc_t
;
2000 /* Locations of the former scratches. */
2001 static vec
<sloc_t
> scratches
;
2003 /* Bitmap of scratch regnos. */
2004 static bitmap_head scratch_bitmap
;
2006 /* Bitmap of scratch operands. */
2007 static bitmap_head scratch_operand_bitmap
;
2009 /* Return true if pseudo REGNO is made of SCRATCH. */
2011 lra_former_scratch_p (int regno
)
2013 return bitmap_bit_p (&scratch_bitmap
, regno
);
2016 /* Return true if the operand NOP of INSN is a former scratch. */
2018 lra_former_scratch_operand_p (rtx_insn
*insn
, int nop
)
2020 return bitmap_bit_p (&scratch_operand_bitmap
,
2021 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
) != 0;
2024 /* Register operand NOP in INSN as a former scratch. It will be
2025 changed to scratch back, if it is necessary, at the LRA end. */
2027 lra_register_new_scratch_op (rtx_insn
*insn
, int nop
, int icode
)
2029 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
2030 rtx op
= *id
->operand_loc
[nop
];
2031 sloc_t loc
= XNEW (struct sloc
);
2032 lra_assert (REG_P (op
));
2036 scratches
.safe_push (loc
);
2037 bitmap_set_bit (&scratch_bitmap
, REGNO (op
));
2038 bitmap_set_bit (&scratch_operand_bitmap
,
2039 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
);
2040 add_reg_note (insn
, REG_UNUSED
, op
);
2043 /* Change INSN's scratches into pseudos and save their location. */
2045 remove_scratches_1 (rtx_insn
*insn
)
2048 bool insn_changed_p
;
2050 lra_insn_recog_data_t id
;
2051 struct lra_static_insn_data
*static_id
;
2053 id
= lra_get_insn_recog_data (insn
);
2054 static_id
= id
->insn_static_data
;
2055 insn_changed_p
= false;
2056 for (i
= 0; i
< static_id
->n_operands
; i
++)
2057 if (GET_CODE (*id
->operand_loc
[i
]) == SCRATCH
2058 && GET_MODE (*id
->operand_loc
[i
]) != VOIDmode
)
2060 insn_changed_p
= true;
2061 *id
->operand_loc
[i
] = reg
2062 = lra_create_new_reg (static_id
->operand
[i
].mode
,
2063 *id
->operand_loc
[i
], ALL_REGS
, NULL
);
2064 lra_register_new_scratch_op (insn
, i
, id
->icode
);
2065 if (lra_dump_file
!= NULL
)
2066 fprintf (lra_dump_file
,
2067 "Removing SCRATCH in insn #%u (nop %d)\n",
2068 INSN_UID (insn
), i
);
2071 /* Because we might use DF right after caller-saves sub-pass
2072 we need to keep DF info up to date. */
2073 df_insn_rescan (insn
);
2076 /* Change scratches into pseudos and save their location. */
2078 remove_scratches (void)
2083 scratches
.create (get_max_uid ());
2084 bitmap_initialize (&scratch_bitmap
, ®_obstack
);
2085 bitmap_initialize (&scratch_operand_bitmap
, ®_obstack
);
2086 FOR_EACH_BB_FN (bb
, cfun
)
2087 FOR_BB_INSNS (bb
, insn
)
2089 remove_scratches_1 (insn
);
2092 /* Changes pseudos created by function remove_scratches onto scratches. */
2094 restore_scratches (void)
2099 rtx_insn
*last
= NULL
;
2100 lra_insn_recog_data_t id
= NULL
;
2102 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
2104 /* Ignore already deleted insns. */
2105 if (NOTE_P (loc
->insn
)
2106 && NOTE_KIND (loc
->insn
) == NOTE_INSN_DELETED
)
2108 if (last
!= loc
->insn
)
2111 id
= lra_get_insn_recog_data (last
);
2113 if (loc
->icode
!= id
->icode
)
2115 /* The icode doesn't match, which means the insn has been modified
2116 (e.g. register elimination). The scratch cannot be restored. */
2119 if (REG_P (*id
->operand_loc
[loc
->nop
])
2120 && ((regno
= REGNO (*id
->operand_loc
[loc
->nop
]))
2121 >= FIRST_PSEUDO_REGISTER
)
2122 && lra_get_regno_hard_regno (regno
) < 0)
2124 /* It should be only case when scratch register with chosen
2125 constraint 'X' did not get memory or hard register. */
2126 lra_assert (lra_former_scratch_p (regno
));
2127 *id
->operand_loc
[loc
->nop
]
2128 = gen_rtx_SCRATCH (GET_MODE (*id
->operand_loc
[loc
->nop
]));
2129 lra_update_dup (id
, loc
->nop
);
2130 if (lra_dump_file
!= NULL
)
2131 fprintf (lra_dump_file
, "Restoring SCRATCH in insn #%u(nop %d)\n",
2132 INSN_UID (loc
->insn
), loc
->nop
);
2135 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
2137 scratches
.release ();
2138 bitmap_clear (&scratch_bitmap
);
2139 bitmap_clear (&scratch_operand_bitmap
);
2144 /* Function checks RTL for correctness. If FINAL_P is true, it is
2145 done at the end of LRA and the check is more rigorous. */
2147 check_rtl (bool final_p
)
2152 lra_assert (! final_p
|| reload_completed
);
2153 FOR_EACH_BB_FN (bb
, cfun
)
2154 FOR_BB_INSNS (bb
, insn
)
2155 if (NONDEBUG_INSN_P (insn
)
2156 && GET_CODE (PATTERN (insn
)) != USE
2157 && GET_CODE (PATTERN (insn
)) != CLOBBER
2158 && GET_CODE (PATTERN (insn
)) != ASM_INPUT
)
2162 extract_constrain_insn (insn
);
2165 /* LRA code is based on assumption that all addresses can be
2166 correctly decomposed. LRA can generate reloads for
2167 decomposable addresses. The decomposition code checks the
2168 correctness of the addresses. So we don't need to check
2169 the addresses here. Don't call insn_invalid_p here, it can
2170 change the code at this stage. */
2171 if (recog_memoized (insn
) < 0 && asm_noperands (PATTERN (insn
)) < 0)
2172 fatal_insn_not_found (insn
);
2176 /* Determine if the current function has an exception receiver block
2177 that reaches the exit block via non-exceptional edges */
2179 has_nonexceptional_receiver (void)
2183 basic_block
*tos
, *worklist
, bb
;
2185 /* If we're not optimizing, then just err on the safe side. */
2189 /* First determine which blocks can reach exit via normal paths. */
2190 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
) + 1);
2192 FOR_EACH_BB_FN (bb
, cfun
)
2193 bb
->flags
&= ~BB_REACHABLE
;
2195 /* Place the exit block on our worklist. */
2196 EXIT_BLOCK_PTR_FOR_FN (cfun
)->flags
|= BB_REACHABLE
;
2197 *tos
++ = EXIT_BLOCK_PTR_FOR_FN (cfun
);
2199 /* Iterate: find everything reachable from what we've already seen. */
2200 while (tos
!= worklist
)
2204 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2205 if (e
->flags
& EDGE_ABNORMAL
)
2212 basic_block src
= e
->src
;
2214 if (!(src
->flags
& BB_REACHABLE
))
2216 src
->flags
|= BB_REACHABLE
;
2222 /* No exceptional block reached exit unexceptionally. */
2227 /* Process recursively X of INSN and add REG_INC notes if necessary. */
2229 add_auto_inc_notes (rtx_insn
*insn
, rtx x
)
2231 enum rtx_code code
= GET_CODE (x
);
2235 if (code
== MEM
&& auto_inc_p (XEXP (x
, 0)))
2237 add_reg_note (insn
, REG_INC
, XEXP (XEXP (x
, 0), 0));
2241 /* Scan all X sub-expressions. */
2242 fmt
= GET_RTX_FORMAT (code
);
2243 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2246 add_auto_inc_notes (insn
, XEXP (x
, i
));
2247 else if (fmt
[i
] == 'E')
2248 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2249 add_auto_inc_notes (insn
, XVECEXP (x
, i
, j
));
2254 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2255 We change pseudos by hard registers without notification of DF and
2256 that can make the notes obsolete. DF-infrastructure does not deal
2257 with REG_INC notes -- so we should regenerate them here. */
2259 update_inc_notes (void)
2265 FOR_EACH_BB_FN (bb
, cfun
)
2266 FOR_BB_INSNS (bb
, insn
)
2267 if (NONDEBUG_INSN_P (insn
))
2269 pnote
= ®_NOTES (insn
);
2272 if (REG_NOTE_KIND (*pnote
) == REG_DEAD
2273 || REG_NOTE_KIND (*pnote
) == REG_UNUSED
2274 || REG_NOTE_KIND (*pnote
) == REG_INC
)
2275 *pnote
= XEXP (*pnote
, 1);
2277 pnote
= &XEXP (*pnote
, 1);
2281 add_auto_inc_notes (insn
, PATTERN (insn
));
2285 /* Set to 1 while in lra. */
2286 int lra_in_progress
;
2288 /* Start of pseudo regnos before the LRA. */
2289 int lra_new_regno_start
;
2291 /* Start of reload pseudo regnos before the new spill pass. */
2292 int lra_constraint_new_regno_start
;
2294 /* Avoid spilling pseudos with regno more than the following value if
2296 int lra_bad_spill_regno_start
;
2298 /* Inheritance pseudo regnos before the new spill pass. */
2299 bitmap_head lra_inheritance_pseudos
;
2301 /* Split regnos before the new spill pass. */
2302 bitmap_head lra_split_regs
;
2304 /* Reload pseudo regnos before the new assignment pass which still can
2305 be spilled after the assignment pass as memory is also accepted in
2306 insns for the reload pseudos. */
2307 bitmap_head lra_optional_reload_pseudos
;
2309 /* Pseudo regnos used for subreg reloads before the new assignment
2310 pass. Such pseudos still can be spilled after the assignment
2312 bitmap_head lra_subreg_reload_pseudos
;
2314 /* File used for output of LRA debug information. */
2315 FILE *lra_dump_file
;
2317 /* True if we found an asm error. */
2318 bool lra_asm_error_p
;
2320 /* True if we should try spill into registers of different classes
2321 instead of memory. */
2322 bool lra_reg_spill_p
;
2324 /* Set up value LRA_REG_SPILL_P. */
2326 setup_reg_spill_flag (void)
2330 if (targetm
.spill_class
!= NULL
)
2331 for (cl
= 0; cl
< (int) LIM_REG_CLASSES
; cl
++)
2332 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
2333 if (targetm
.spill_class ((enum reg_class
) cl
,
2334 (machine_mode
) mode
) != NO_REGS
)
2336 lra_reg_spill_p
= true;
2339 lra_reg_spill_p
= false;
2342 /* True if the current function is too big to use regular algorithms
2343 in LRA. In other words, we should use simpler and faster algorithms
2344 in LRA. It also means we should not worry about generation code
2345 for caller saves. The value is set up in IRA. */
2348 /* Major LRA entry function. F is a file should be used to dump LRA
2354 bool live_p
, inserted_p
;
2357 lra_asm_error_p
= false;
2359 timevar_push (TV_LRA
);
2361 /* Make sure that the last insn is a note. Some subsequent passes
2363 emit_note (NOTE_INSN_DELETED
);
2365 lra_no_alloc_regs
= ira_no_alloc_regs
;
2370 init_insn_recog_data ();
2372 /* Some quick check on RTL generated by previous passes. */
2376 lra_in_progress
= 1;
2378 lra_live_range_iter
= lra_coalesce_iter
= lra_constraint_iter
= 0;
2379 lra_assignment_iter
= lra_assignment_iter_after_spill
= 0;
2380 lra_inheritance_iter
= lra_undo_inheritance_iter
= 0;
2381 lra_rematerialization_iter
= 0;
2383 setup_reg_spill_flag ();
2385 /* Function remove_scratches can creates new pseudos for clobbers --
2386 so set up lra_constraint_new_regno_start before its call to
2387 permit changing reg classes for pseudos created by this
2389 lra_constraint_new_regno_start
= lra_new_regno_start
= max_reg_num ();
2390 lra_bad_spill_regno_start
= INT_MAX
;
2391 remove_scratches ();
2393 /* A function that has a non-local label that can reach the exit
2394 block via non-exceptional paths must save all call-saved
2396 if (cfun
->has_nonlocal_label
&& has_nonexceptional_receiver ())
2397 crtl
->saves_all_registers
= 1;
2399 if (crtl
->saves_all_registers
)
2400 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2401 if (!crtl
->abi
->clobbers_full_reg_p (i
)
2403 && !LOCAL_REGNO (i
))
2404 df_set_regs_ever_live (i
, true);
2406 /* We don't DF from now and avoid its using because it is to
2407 expensive when a lot of RTL changes are made. */
2408 df_set_flags (DF_NO_INSN_RESCAN
);
2409 lra_constraint_insn_stack
.create (get_max_uid ());
2410 lra_constraint_insn_stack_bitmap
= sbitmap_alloc (get_max_uid ());
2411 bitmap_clear (lra_constraint_insn_stack_bitmap
);
2412 lra_live_ranges_init ();
2413 lra_constraints_init ();
2414 lra_curr_reload_num
= 0;
2415 push_insns (get_last_insn (), NULL
);
2416 /* It is needed for the 1st coalescing. */
2417 bitmap_initialize (&lra_inheritance_pseudos
, ®_obstack
);
2418 bitmap_initialize (&lra_split_regs
, ®_obstack
);
2419 bitmap_initialize (&lra_optional_reload_pseudos
, ®_obstack
);
2420 bitmap_initialize (&lra_subreg_reload_pseudos
, ®_obstack
);
2422 if (maybe_ne (get_frame_size (), 0) && crtl
->stack_alignment_needed
)
2423 /* If we have a stack frame, we must align it now. The stack size
2424 may be a part of the offset computation for register
2426 assign_stack_local (BLKmode
, 0, crtl
->stack_alignment_needed
);
2432 bool reloads_p
= lra_constraints (lra_constraint_iter
== 0);
2433 /* Constraint transformations may result in that eliminable
2434 hard regs become uneliminable and pseudos which use them
2435 should be spilled. It is better to do it before pseudo
2438 For example, rs6000 can make
2439 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2440 to use a constant pool. */
2441 lra_eliminate (false, false);
2442 /* We should try to assign hard registers to scratches even
2443 if there were no RTL transformations in lra_constraints.
2444 Also we should check IRA assignments on the first
2445 iteration as they can be wrong because of early clobbers
2446 operands which are ignored in IRA. */
2447 if (! reloads_p
&& lra_constraint_iter
> 1)
2449 /* Stack is not empty here only when there are changes
2450 during the elimination sub-pass. */
2451 if (bitmap_empty_p (lra_constraint_insn_stack_bitmap
))
2454 /* If there are no reloads but changing due
2455 elimination, restart the constraint sub-pass
2459 /* Do inheritance only for regular algorithms. */
2463 lra_clear_live_ranges ();
2467 /* We need live ranges for lra_assign -- so build them.
2468 But don't remove dead insns or change global live
2469 info as we can undo inheritance transformations after
2470 inheritance pseudo assigning. */
2471 lra_create_live_ranges (true, false);
2473 /* If we don't spill non-reload and non-inheritance
2474 pseudos, there is no sense to run memory-memory move
2475 coalescing. If inheritance pseudos were spilled, the
2476 memory-memory moves involving them will be removed by
2477 pass undoing inheritance. */
2479 lra_assign (fails_p
);
2482 bool spill_p
= !lra_assign (fails_p
);
2484 if (lra_undo_inheritance ())
2486 if (spill_p
&& ! fails_p
)
2490 lra_create_live_ranges (true, true);
2493 if (lra_coalesce ())
2497 lra_clear_live_ranges ();
2501 /* It is a very rare case. It is the last hope to
2502 split a hard regno live range for a reload
2505 lra_clear_live_ranges ();
2507 if (! lra_split_hard_reg_for ())
2513 /* Don't clear optional reloads bitmap until all constraints are
2514 satisfied as we need to differ them from regular reloads. */
2515 bitmap_clear (&lra_optional_reload_pseudos
);
2516 bitmap_clear (&lra_subreg_reload_pseudos
);
2517 bitmap_clear (&lra_inheritance_pseudos
);
2518 bitmap_clear (&lra_split_regs
);
2521 /* We need full live info for spilling pseudos into
2522 registers instead of memory. */
2523 lra_create_live_ranges (lra_reg_spill_p
, true);
2526 /* We should check necessity for spilling here as the above live
2527 range pass can remove spilled pseudos. */
2528 if (! lra_need_for_spills_p ())
2530 /* Now we know what pseudos should be spilled. Try to
2531 rematerialize them first. */
2534 /* We need full live info -- see the comment above. */
2535 lra_create_live_ranges (lra_reg_spill_p
, true);
2537 if (! lra_need_for_spills_p ())
2539 if (lra_need_for_scratch_reg_p ())
2545 /* Assignment of stack slots changes elimination offsets for
2546 some eliminations. So update the offsets here. */
2547 lra_eliminate (false, false);
2548 lra_constraint_new_regno_start
= max_reg_num ();
2549 if (lra_bad_spill_regno_start
== INT_MAX
2550 && lra_inheritance_iter
> LRA_MAX_INHERITANCE_PASSES
2551 && lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
2552 /* After switching off inheritance and rematerialization
2553 passes, avoid spilling reload pseudos will be created to
2554 prevent LRA cycling in some complicated cases. */
2555 lra_bad_spill_regno_start
= lra_constraint_new_regno_start
;
2556 lra_assignment_iter_after_spill
= 0;
2558 restore_scratches ();
2559 lra_eliminate (true, false);
2560 lra_final_code_change ();
2561 lra_in_progress
= 0;
2563 lra_clear_live_ranges ();
2564 lra_live_ranges_finish ();
2565 lra_constraints_finish ();
2567 sbitmap_free (lra_constraint_insn_stack_bitmap
);
2568 lra_constraint_insn_stack
.release ();
2569 finish_insn_recog_data ();
2570 regstat_free_n_sets_and_refs ();
2572 reload_completed
= 1;
2573 update_inc_notes ();
2575 inserted_p
= fixup_abnormal_edges ();
2577 /* We've possibly turned single trapping insn into multiple ones. */
2578 if (cfun
->can_throw_non_call_exceptions
)
2580 auto_sbitmap
blocks (last_basic_block_for_fn (cfun
));
2581 bitmap_ones (blocks
);
2582 find_many_sub_basic_blocks (blocks
);
2586 commit_edge_insertions ();
2588 /* Replacing pseudos with their memory equivalents might have
2589 created shared rtx. Subsequent passes would get confused
2590 by this, so unshare everything here. */
2591 unshare_all_rtl_again (get_insns ());
2596 timevar_pop (TV_LRA
);
2599 /* Called once per compiler to initialize LRA data once. */
2601 lra_init_once (void)
2603 init_insn_code_data_once ();
2606 /* Called once per compiler to finish LRA data which are initialize
2609 lra_finish_once (void)
2611 finish_insn_code_data_once ();