1 /* LRA (local register allocator) driver and LRA utilities.
2 Copyright (C) 2010-2020 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
)
657 free (insn_code_data
[i
]);
658 insn_code_data
[i
] = NULL
;
663 /* Return static insn data, allocate and setup if necessary. Although
664 dup_num is static data (it depends only on icode), to set it up we
665 need to extract insn first. So recog_data should be valid for
666 normal insn (ICODE >= 0) before the call. */
667 static struct lra_static_insn_data
*
668 get_static_insn_data (int icode
, int nop
, int ndup
, int nalt
)
670 struct lra_static_insn_data
*data
;
673 lra_assert (icode
< (int) NUM_INSN_CODES
);
674 if (icode
>= 0 && (data
= insn_code_data
[icode
]) != NULL
)
676 lra_assert (nop
>= 0 && ndup
>= 0 && nalt
>= 0);
677 n_bytes
= sizeof (struct lra_static_insn_data
)
678 + sizeof (struct lra_operand_data
) * nop
679 + sizeof (int) * ndup
;
680 data
= XNEWVAR (struct lra_static_insn_data
, n_bytes
);
681 data
->operand_alternative
= NULL
;
682 data
->n_operands
= nop
;
684 data
->n_alternatives
= nalt
;
685 data
->operand
= ((struct lra_operand_data
*)
686 ((char *) data
+ sizeof (struct lra_static_insn_data
)));
687 data
->dup_num
= ((int *) ((char *) data
->operand
688 + sizeof (struct lra_operand_data
) * nop
));
693 insn_code_data
[icode
] = data
;
694 for (i
= 0; i
< nop
; i
++)
696 data
->operand
[i
].constraint
697 = insn_data
[icode
].operand
[i
].constraint
;
698 data
->operand
[i
].mode
= insn_data
[icode
].operand
[i
].mode
;
699 data
->operand
[i
].strict_low
= insn_data
[icode
].operand
[i
].strict_low
;
700 data
->operand
[i
].is_operator
701 = insn_data
[icode
].operand
[i
].is_operator
;
702 data
->operand
[i
].type
703 = (data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
704 : data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
706 data
->operand
[i
].is_address
= false;
708 for (i
= 0; i
< ndup
; i
++)
709 data
->dup_num
[i
] = recog_data
.dup_num
[i
];
714 /* The current length of the following array. */
715 int lra_insn_recog_data_len
;
717 /* Map INSN_UID -> the insn recog data (NULL if unknown). */
718 lra_insn_recog_data_t
*lra_insn_recog_data
;
720 /* Alloc pool we allocate entries for lra_insn_recog_data from. */
721 static object_allocator
<class lra_insn_recog_data
>
722 lra_insn_recog_data_pool ("insn recog data pool");
724 /* Initialize LRA data about insns. */
726 init_insn_recog_data (void)
728 lra_insn_recog_data_len
= 0;
729 lra_insn_recog_data
= NULL
;
732 /* Expand, if necessary, LRA data about insns. */
734 check_and_expand_insn_recog_data (int index
)
738 if (lra_insn_recog_data_len
> index
)
740 old
= lra_insn_recog_data_len
;
741 lra_insn_recog_data_len
= index
* 3 / 2 + 1;
742 lra_insn_recog_data
= XRESIZEVEC (lra_insn_recog_data_t
,
744 lra_insn_recog_data_len
);
745 for (i
= old
; i
< lra_insn_recog_data_len
; i
++)
746 lra_insn_recog_data
[i
] = NULL
;
749 /* Finish LRA DATA about insn. */
751 free_insn_recog_data (lra_insn_recog_data_t data
)
753 if (data
->operand_loc
!= NULL
)
754 free (data
->operand_loc
);
755 if (data
->dup_loc
!= NULL
)
756 free (data
->dup_loc
);
757 if (data
->arg_hard_regs
!= NULL
)
758 free (data
->arg_hard_regs
);
759 if (data
->icode
< 0 && NONDEBUG_INSN_P (data
->insn
))
761 if (data
->insn_static_data
->operand_alternative
!= NULL
)
762 free (const_cast <operand_alternative
*>
763 (data
->insn_static_data
->operand_alternative
));
764 free_insn_regs (data
->insn_static_data
->hard_regs
);
765 free (data
->insn_static_data
);
767 free_insn_regs (data
->regs
);
769 lra_insn_recog_data_pool
.remove (data
);
772 /* Pools for copies. */
773 static object_allocator
<lra_copy
> lra_copy_pool ("lra copies");
775 /* Finish LRA data about all insns. */
777 finish_insn_recog_data (void)
780 lra_insn_recog_data_t data
;
782 for (i
= 0; i
< lra_insn_recog_data_len
; i
++)
783 if ((data
= lra_insn_recog_data
[i
]) != NULL
)
784 free_insn_recog_data (data
);
786 lra_copy_pool
.release ();
787 lra_insn_reg_pool
.release ();
788 lra_insn_recog_data_pool
.release ();
789 free (lra_insn_recog_data
);
792 /* Setup info about operands in alternatives of LRA DATA of insn. */
794 setup_operand_alternative (lra_insn_recog_data_t data
,
795 const operand_alternative
*op_alt
)
798 int icode
= data
->icode
;
799 struct lra_static_insn_data
*static_data
= data
->insn_static_data
;
801 static_data
->commutative
= -1;
802 nop
= static_data
->n_operands
;
803 nalt
= static_data
->n_alternatives
;
804 static_data
->operand_alternative
= op_alt
;
805 for (i
= 0; i
< nop
; i
++)
807 static_data
->operand
[i
].early_clobber_alts
= 0;
808 static_data
->operand
[i
].is_address
= false;
809 if (static_data
->operand
[i
].constraint
[0] == '%')
811 /* We currently only support one commutative pair of operands. */
812 if (static_data
->commutative
< 0)
813 static_data
->commutative
= i
;
815 lra_assert (icode
< 0); /* Asm */
816 /* The last operand should not be marked commutative. */
817 lra_assert (i
!= nop
- 1);
820 for (j
= 0; j
< nalt
; j
++)
821 for (i
= 0; i
< nop
; i
++, op_alt
++)
823 if (op_alt
->earlyclobber
)
824 static_data
->operand
[i
].early_clobber_alts
|= (alternative_mask
) 1 << j
;
825 static_data
->operand
[i
].is_address
|= op_alt
->is_address
;
829 /* Recursively process X and collect info about registers, which are
830 not the insn operands, in X with TYPE (in/out/inout) and flag that
831 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
832 to LIST. X is a part of insn given by DATA. Return the result
834 static struct lra_insn_reg
*
835 collect_non_operand_hard_regs (rtx_insn
*insn
, rtx
*x
,
836 lra_insn_recog_data_t data
,
837 struct lra_insn_reg
*list
,
838 enum op_type type
, bool early_clobber
)
840 int i
, j
, regno
, last
;
843 struct lra_insn_reg
*curr
;
845 enum rtx_code code
= GET_CODE (op
);
846 const char *fmt
= GET_RTX_FORMAT (code
);
848 for (i
= 0; i
< data
->insn_static_data
->n_operands
; i
++)
849 if (! data
->insn_static_data
->operand
[i
].is_operator
850 && x
== data
->operand_loc
[i
])
851 /* It is an operand loc. Stop here. */
853 for (i
= 0; i
< data
->insn_static_data
->n_dups
; i
++)
854 if (x
== data
->dup_loc
[i
])
855 /* It is a dup loc. Stop here. */
857 mode
= GET_MODE (op
);
861 mode
= wider_subreg_mode (op
);
862 if (read_modify_subreg_p (op
))
864 op
= SUBREG_REG (op
);
865 code
= GET_CODE (op
);
869 if ((regno
= REGNO (op
)) >= FIRST_PSEUDO_REGISTER
)
871 /* Process all regs even unallocatable ones as we need info
872 about all regs for rematerialization pass. */
873 for (last
= end_hard_regno (mode
, regno
); regno
< last
; regno
++)
875 for (curr
= list
; curr
!= NULL
; curr
= curr
->next
)
876 if (curr
->regno
== regno
&& curr
->subreg_p
== subreg_p
877 && curr
->biggest_mode
== mode
)
879 if (curr
->type
!= type
)
880 curr
->type
= OP_INOUT
;
882 curr
->early_clobber_alts
= ALL_ALTERNATIVES
;
887 /* This is a new hard regno or the info cannot be
888 integrated into the found structure. */
892 /* This clobber is to inform popping floating
894 && ! (FIRST_STACK_REG
<= regno
895 && regno
<= LAST_STACK_REG
));
897 list
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
898 early_clobber
? ALL_ALTERNATIVES
: 0, list
);
906 list
= collect_non_operand_hard_regs (insn
, &SET_DEST (op
), data
,
907 list
, OP_OUT
, false);
908 list
= collect_non_operand_hard_regs (insn
, &SET_SRC (op
), data
,
912 /* We treat clobber of non-operand hard registers as early clobber. */
913 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
916 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
917 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
918 list
, OP_INOUT
, false);
920 case PRE_MODIFY
: case POST_MODIFY
:
921 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
922 list
, OP_INOUT
, false);
923 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 1), data
,
927 fmt
= GET_RTX_FORMAT (code
);
928 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
931 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, i
), data
,
933 else if (fmt
[i
] == 'E')
934 for (j
= XVECLEN (op
, i
) - 1; j
>= 0; j
--)
935 list
= collect_non_operand_hard_regs (insn
, &XVECEXP (op
, i
, j
),
936 data
, list
, OP_IN
, false);
942 /* Set up and return info about INSN. Set up the info if it is not set up
944 lra_insn_recog_data_t
945 lra_set_insn_recog_data (rtx_insn
*insn
)
947 lra_insn_recog_data_t data
;
950 unsigned int uid
= INSN_UID (insn
);
951 struct lra_static_insn_data
*insn_static_data
;
953 check_and_expand_insn_recog_data (uid
);
954 if (DEBUG_INSN_P (insn
))
958 icode
= INSN_CODE (insn
);
960 /* It might be a new simple insn which is not recognized yet. */
961 INSN_CODE (insn
) = icode
= recog_memoized (insn
);
963 data
= lra_insn_recog_data_pool
.allocate ();
964 lra_insn_recog_data
[uid
] = data
;
966 data
->used_insn_alternative
= LRA_UNKNOWN_ALT
;
969 if (DEBUG_INSN_P (insn
))
971 data
->dup_loc
= NULL
;
972 data
->arg_hard_regs
= NULL
;
973 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
974 if (DEBUG_BIND_INSN_P (insn
))
976 data
->insn_static_data
= &debug_bind_static_data
;
977 data
->operand_loc
= XNEWVEC (rtx
*, 1);
978 data
->operand_loc
[0] = &INSN_VAR_LOCATION_LOC (insn
);
980 else if (DEBUG_MARKER_INSN_P (insn
))
982 data
->insn_static_data
= &debug_marker_static_data
;
983 data
->operand_loc
= NULL
;
990 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
991 const char *constraints
[MAX_RECOG_OPERANDS
];
993 nop
= asm_noperands (PATTERN (insn
));
994 data
->operand_loc
= data
->dup_loc
= NULL
;
998 /* It is a special insn like USE or CLOBBER. We should
999 recognize any regular insn otherwise LRA can do nothing
1001 gcc_assert (GET_CODE (PATTERN (insn
)) == USE
1002 || GET_CODE (PATTERN (insn
)) == CLOBBER
1003 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
1004 data
->insn_static_data
= insn_static_data
1005 = get_static_insn_data (-1, 0, 0, nalt
);
1009 /* expand_asm_operands makes sure there aren't too many
1011 lra_assert (nop
<= MAX_RECOG_OPERANDS
);
1013 data
->operand_loc
= XNEWVEC (rtx
*, nop
);
1014 /* Now get the operand values and constraints out of the
1016 decode_asm_operands (PATTERN (insn
), NULL
,
1018 constraints
, operand_mode
, NULL
);
1020 for (const char *p
=constraints
[0]; *p
; p
++)
1022 data
->insn_static_data
= insn_static_data
1023 = get_static_insn_data (-1, nop
, 0, nalt
);
1024 for (i
= 0; i
< nop
; i
++)
1026 insn_static_data
->operand
[i
].mode
= operand_mode
[i
];
1027 insn_static_data
->operand
[i
].constraint
= constraints
[i
];
1028 insn_static_data
->operand
[i
].strict_low
= false;
1029 insn_static_data
->operand
[i
].is_operator
= false;
1030 insn_static_data
->operand
[i
].is_address
= false;
1033 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1034 insn_static_data
->operand
[i
].type
1035 = (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1036 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1038 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
1041 operand_alternative
*op_alt
= XCNEWVEC (operand_alternative
,
1043 preprocess_constraints (nop
, nalt
, constraints
, op_alt
,
1045 setup_operand_alternative (data
, op_alt
);
1050 insn_extract (insn
);
1051 data
->insn_static_data
= insn_static_data
1052 = get_static_insn_data (icode
, insn_data
[icode
].n_operands
,
1053 insn_data
[icode
].n_dups
,
1054 insn_data
[icode
].n_alternatives
);
1055 n
= insn_static_data
->n_operands
;
1060 locs
= XNEWVEC (rtx
*, n
);
1061 memcpy (locs
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1063 data
->operand_loc
= locs
;
1064 n
= insn_static_data
->n_dups
;
1069 locs
= XNEWVEC (rtx
*, n
);
1070 memcpy (locs
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1072 data
->dup_loc
= locs
;
1073 data
->preferred_alternatives
= get_preferred_alternatives (insn
);
1074 const operand_alternative
*op_alt
= preprocess_insn_constraints (icode
);
1075 if (!insn_static_data
->operand_alternative
)
1076 setup_operand_alternative (data
, op_alt
);
1077 else if (op_alt
!= insn_static_data
->operand_alternative
)
1078 insn_static_data
->operand_alternative
= op_alt
;
1080 if (GET_CODE (PATTERN (insn
)) == CLOBBER
|| GET_CODE (PATTERN (insn
)) == USE
)
1081 insn_static_data
->hard_regs
= NULL
;
1083 insn_static_data
->hard_regs
1084 = collect_non_operand_hard_regs (insn
, &PATTERN (insn
), data
,
1085 NULL
, OP_IN
, false);
1086 data
->arg_hard_regs
= NULL
;
1091 int n_hard_regs
, regno
, arg_hard_regs
[FIRST_PSEUDO_REGISTER
];
1094 /* Finding implicit hard register usage. We believe it will be
1095 not changed whatever transformations are used. Call insns
1096 are such example. */
1097 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1099 link
= XEXP (link
, 1))
1100 if (((use_p
= GET_CODE (XEXP (link
, 0)) == USE
)
1101 || GET_CODE (XEXP (link
, 0)) == CLOBBER
)
1102 && REG_P (XEXP (XEXP (link
, 0), 0)))
1104 regno
= REGNO (XEXP (XEXP (link
, 0), 0));
1105 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
1106 /* It is an argument register. */
1107 for (i
= REG_NREGS (XEXP (XEXP (link
, 0), 0)) - 1; i
>= 0; i
--)
1108 arg_hard_regs
[n_hard_regs
++]
1109 = regno
+ i
+ (use_p
? 0 : FIRST_PSEUDO_REGISTER
);
1112 if (n_hard_regs
!= 0)
1114 arg_hard_regs
[n_hard_regs
++] = -1;
1115 data
->arg_hard_regs
= XNEWVEC (int, n_hard_regs
);
1116 memcpy (data
->arg_hard_regs
, arg_hard_regs
,
1117 sizeof (int) * n_hard_regs
);
1120 /* Some output operand can be recognized only from the context not
1121 from the constraints which are empty in this case. Call insn may
1122 contain a hard register in set destination with empty constraint
1123 and extract_insn treats them as an input. */
1124 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1128 struct lra_operand_data
*operand
= &insn_static_data
->operand
[i
];
1130 /* ??? Should we treat 'X' the same way. It looks to me that
1131 'X' means anything and empty constraint means we do not
1133 if (operand
->type
!= OP_IN
|| *operand
->constraint
!= '\0'
1134 || operand
->is_operator
)
1136 pat
= PATTERN (insn
);
1137 if (GET_CODE (pat
) == SET
)
1139 if (data
->operand_loc
[i
] != &SET_DEST (pat
))
1142 else if (GET_CODE (pat
) == PARALLEL
)
1144 for (j
= XVECLEN (pat
, 0) - 1; j
>= 0; j
--)
1146 set
= XVECEXP (PATTERN (insn
), 0, j
);
1147 if (GET_CODE (set
) == SET
1148 && &SET_DEST (set
) == data
->operand_loc
[i
])
1156 operand
->type
= OP_OUT
;
1161 /* Return info about insn give by UID. The info should be already set
1163 static lra_insn_recog_data_t
1164 get_insn_recog_data_by_uid (int uid
)
1166 lra_insn_recog_data_t data
;
1168 data
= lra_insn_recog_data
[uid
];
1169 lra_assert (data
!= NULL
);
1173 /* Invalidate all info about insn given by its UID. */
1175 invalidate_insn_recog_data (int uid
)
1177 lra_insn_recog_data_t data
;
1179 data
= lra_insn_recog_data
[uid
];
1180 lra_assert (data
!= NULL
);
1181 free_insn_recog_data (data
);
1182 lra_insn_recog_data
[uid
] = NULL
;
1185 /* Update all the insn info about INSN. It is usually called when
1186 something in the insn was changed. Return the updated info. */
1187 lra_insn_recog_data_t
1188 lra_update_insn_recog_data (rtx_insn
*insn
)
1190 lra_insn_recog_data_t data
;
1192 unsigned int uid
= INSN_UID (insn
);
1193 struct lra_static_insn_data
*insn_static_data
;
1194 poly_int64 sp_offset
= 0;
1196 check_and_expand_insn_recog_data (uid
);
1197 if ((data
= lra_insn_recog_data
[uid
]) != NULL
1198 && data
->icode
!= INSN_CODE (insn
))
1200 sp_offset
= data
->sp_offset
;
1201 invalidate_insn_data_regno_info (data
, insn
, get_insn_freq (insn
));
1202 invalidate_insn_recog_data (uid
);
1207 data
= lra_get_insn_recog_data (insn
);
1208 /* Initiate or restore SP offset. */
1209 data
->sp_offset
= sp_offset
;
1212 insn_static_data
= data
->insn_static_data
;
1213 data
->used_insn_alternative
= LRA_UNKNOWN_ALT
;
1214 if (DEBUG_INSN_P (insn
))
1216 if (data
->icode
< 0)
1219 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
1220 const char *constraints
[MAX_RECOG_OPERANDS
];
1222 nop
= asm_noperands (PATTERN (insn
));
1225 lra_assert (nop
== data
->insn_static_data
->n_operands
);
1226 /* Now get the operand values and constraints out of the
1228 decode_asm_operands (PATTERN (insn
), NULL
,
1230 constraints
, operand_mode
, NULL
);
1233 for (int i
= 0; i
< nop
; i
++)
1235 (insn_static_data
->operand
[i
].mode
== operand_mode
[i
]
1236 && insn_static_data
->operand
[i
].constraint
== constraints
[i
]
1237 && ! insn_static_data
->operand
[i
].is_operator
);
1241 for (int i
= 0; i
< insn_static_data
->n_operands
; i
++)
1243 (insn_static_data
->operand
[i
].type
1244 == (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1245 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1250 insn_extract (insn
);
1251 n
= insn_static_data
->n_operands
;
1253 memcpy (data
->operand_loc
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1254 n
= insn_static_data
->n_dups
;
1256 memcpy (data
->dup_loc
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1257 lra_assert (check_bool_attrs (insn
));
1262 /* Set up that INSN is using alternative ALT now. */
1264 lra_set_used_insn_alternative (rtx_insn
*insn
, int alt
)
1266 lra_insn_recog_data_t data
;
1268 data
= lra_get_insn_recog_data (insn
);
1269 data
->used_insn_alternative
= alt
;
1272 /* Set up that insn with UID is using alternative ALT now. The insn
1273 info should be already set up. */
1275 lra_set_used_insn_alternative_by_uid (int uid
, int alt
)
1277 lra_insn_recog_data_t data
;
1279 check_and_expand_insn_recog_data (uid
);
1280 data
= lra_insn_recog_data
[uid
];
1281 lra_assert (data
!= NULL
);
1282 data
->used_insn_alternative
= alt
;
1287 /* This page contains code dealing with common register info and
1290 /* The size of the following array. */
1291 static int reg_info_size
;
1292 /* Common info about each register. */
1293 class lra_reg
*lra_reg_info
;
1295 HARD_REG_SET hard_regs_spilled_into
;
1297 /* Last register value. */
1298 static int last_reg_value
;
1300 /* Return new register value. */
1302 get_new_reg_value (void)
1304 return ++last_reg_value
;
1307 /* Vec referring to pseudo copies. */
1308 static vec
<lra_copy_t
> copy_vec
;
1310 /* Initialize I-th element of lra_reg_info. */
1312 initialize_lra_reg_info_element (int i
)
1314 bitmap_initialize (&lra_reg_info
[i
].insn_bitmap
, ®_obstack
);
1316 lra_reg_info
[i
].no_stack_p
= false;
1318 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
1319 lra_reg_info
[i
].preferred_hard_regno1
= -1;
1320 lra_reg_info
[i
].preferred_hard_regno2
= -1;
1321 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
1322 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
1323 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
1324 lra_reg_info
[i
].live_ranges
= NULL
;
1325 lra_reg_info
[i
].nrefs
= lra_reg_info
[i
].freq
= 0;
1326 lra_reg_info
[i
].last_reload
= 0;
1327 lra_reg_info
[i
].restore_rtx
= NULL_RTX
;
1328 lra_reg_info
[i
].val
= get_new_reg_value ();
1329 lra_reg_info
[i
].offset
= 0;
1330 lra_reg_info
[i
].copies
= NULL
;
1333 /* Initialize common reg info and copies. */
1335 init_reg_info (void)
1340 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1341 lra_reg_info
= XNEWVEC (class lra_reg
, reg_info_size
);
1342 for (i
= 0; i
< reg_info_size
; i
++)
1343 initialize_lra_reg_info_element (i
);
1344 copy_vec
.truncate (0);
1345 CLEAR_HARD_REG_SET (hard_regs_spilled_into
);
1349 /* Finish common reg info and copies. */
1351 finish_reg_info (void)
1355 for (i
= 0; i
< reg_info_size
; i
++)
1356 bitmap_clear (&lra_reg_info
[i
].insn_bitmap
);
1357 free (lra_reg_info
);
1361 /* Expand common reg info if it is necessary. */
1363 expand_reg_info (void)
1365 int i
, old
= reg_info_size
;
1367 if (reg_info_size
> max_reg_num ())
1369 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1370 lra_reg_info
= XRESIZEVEC (class lra_reg
, lra_reg_info
, reg_info_size
);
1371 for (i
= old
; i
< reg_info_size
; i
++)
1372 initialize_lra_reg_info_element (i
);
1375 /* Free all copies. */
1377 lra_free_copies (void)
1381 while (copy_vec
.length () != 0)
1383 cp
= copy_vec
.pop ();
1384 lra_reg_info
[cp
->regno1
].copies
= lra_reg_info
[cp
->regno2
].copies
= NULL
;
1385 lra_copy_pool
.remove (cp
);
1389 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1390 frequency is FREQ. */
1392 lra_create_copy (int regno1
, int regno2
, int freq
)
1397 lra_assert (regno1
!= regno2
);
1398 regno1_dest_p
= true;
1399 if (regno1
> regno2
)
1401 std::swap (regno1
, regno2
);
1402 regno1_dest_p
= false;
1404 cp
= lra_copy_pool
.allocate ();
1405 copy_vec
.safe_push (cp
);
1406 cp
->regno1_dest_p
= regno1_dest_p
;
1408 cp
->regno1
= regno1
;
1409 cp
->regno2
= regno2
;
1410 cp
->regno1_next
= lra_reg_info
[regno1
].copies
;
1411 lra_reg_info
[regno1
].copies
= cp
;
1412 cp
->regno2_next
= lra_reg_info
[regno2
].copies
;
1413 lra_reg_info
[regno2
].copies
= cp
;
1414 if (lra_dump_file
!= NULL
)
1415 fprintf (lra_dump_file
, " Creating copy r%d%sr%d@%d\n",
1416 regno1
, regno1_dest_p
? "<-" : "->", regno2
, freq
);
1419 /* Return N-th (0, 1, ...) copy. If there is no copy, return
1422 lra_get_copy (int n
)
1424 if (n
>= (int) copy_vec
.length ())
1431 /* This page contains code dealing with info about registers in
1434 /* Process X of INSN recursively and add info (operand type is given
1435 by TYPE) about registers in X to the insn DATA. If X can be early
1436 clobbered, alternatives in which it can be early clobbered are given
1437 by EARLY_CLOBBER_ALTS. */
1439 add_regs_to_insn_regno_info (lra_insn_recog_data_t data
, rtx x
,
1440 rtx_insn
*insn
, enum op_type type
,
1441 alternative_mask early_clobber_alts
)
1448 struct lra_insn_reg
*curr
;
1450 code
= GET_CODE (x
);
1451 mode
= GET_MODE (x
);
1453 if (GET_CODE (x
) == SUBREG
)
1455 mode
= wider_subreg_mode (x
);
1456 if (read_modify_subreg_p (x
))
1459 code
= GET_CODE (x
);
1464 /* Process all regs even unallocatable ones as we need info about
1465 all regs for rematerialization pass. */
1467 if (bitmap_set_bit (&lra_reg_info
[regno
].insn_bitmap
, INSN_UID (insn
)))
1469 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
1470 early_clobber_alts
, data
->regs
);
1475 for (curr
= data
->regs
; curr
!= NULL
; curr
= curr
->next
)
1476 if (curr
->regno
== regno
)
1478 if (curr
->subreg_p
!= subreg_p
|| curr
->biggest_mode
!= mode
)
1479 /* The info cannot be integrated into the found
1481 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
,
1482 subreg_p
, early_clobber_alts
,
1486 if (curr
->type
!= type
)
1487 curr
->type
= OP_INOUT
;
1488 curr
->early_clobber_alts
|= early_clobber_alts
;
1499 add_regs_to_insn_regno_info (data
, SET_DEST (x
), insn
, OP_OUT
, 0);
1500 add_regs_to_insn_regno_info (data
, SET_SRC (x
), insn
, OP_IN
, 0);
1503 /* We treat clobber of non-operand hard registers as early
1505 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), insn
, OP_OUT
,
1508 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
1509 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), insn
, OP_INOUT
, 0);
1511 case PRE_MODIFY
: case POST_MODIFY
:
1512 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), insn
, OP_INOUT
, 0);
1513 add_regs_to_insn_regno_info (data
, XEXP (x
, 1), insn
, OP_IN
, 0);
1516 if ((code
!= PARALLEL
&& code
!= EXPR_LIST
) || type
!= OP_OUT
)
1517 /* Some targets place small structures in registers for return
1518 values of functions, and those registers are wrapped in
1519 PARALLEL that we may see as the destination of a SET. Here
1522 (call_insn 13 12 14 2 (set (parallel:BLK [
1523 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1525 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1526 (const_int 8 [0x8]))
1528 (call (mem:QI (symbol_ref:DI (... */
1530 fmt
= GET_RTX_FORMAT (code
);
1531 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1534 add_regs_to_insn_regno_info (data
, XEXP (x
, i
), insn
, type
, 0);
1535 else if (fmt
[i
] == 'E')
1537 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1538 add_regs_to_insn_regno_info (data
, XVECEXP (x
, i
, j
), insn
,
1545 /* Return execution frequency of INSN. */
1547 get_insn_freq (rtx_insn
*insn
)
1549 basic_block bb
= BLOCK_FOR_INSN (insn
);
1551 gcc_checking_assert (bb
!= NULL
);
1552 return REG_FREQ_FROM_BB (bb
);
1555 /* Invalidate all reg info of INSN with DATA and execution frequency
1556 FREQ. Update common info about the invalidated registers. */
1558 invalidate_insn_data_regno_info (lra_insn_recog_data_t data
, rtx_insn
*insn
,
1564 struct lra_insn_reg
*ir
, *next_ir
;
1566 uid
= INSN_UID (insn
);
1567 debug_p
= DEBUG_INSN_P (insn
);
1568 for (ir
= data
->regs
; ir
!= NULL
; ir
= next_ir
)
1572 lra_insn_reg_pool
.remove (ir
);
1573 bitmap_clear_bit (&lra_reg_info
[i
].insn_bitmap
, uid
);
1574 if (i
>= FIRST_PSEUDO_REGISTER
&& ! debug_p
)
1576 lra_reg_info
[i
].nrefs
--;
1577 lra_reg_info
[i
].freq
-= freq
;
1578 lra_assert (lra_reg_info
[i
].nrefs
>= 0 && lra_reg_info
[i
].freq
>= 0);
1584 /* Invalidate all reg info of INSN. Update common info about the
1585 invalidated registers. */
1587 lra_invalidate_insn_regno_info (rtx_insn
*insn
)
1589 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn
), insn
,
1590 get_insn_freq (insn
));
1593 /* Update common reg info from reg info of insn given by its DATA and
1594 execution frequency FREQ. */
1596 setup_insn_reg_info (lra_insn_recog_data_t data
, int freq
)
1599 struct lra_insn_reg
*ir
;
1601 for (ir
= data
->regs
; ir
!= NULL
; ir
= ir
->next
)
1602 if ((i
= ir
->regno
) >= FIRST_PSEUDO_REGISTER
)
1604 lra_reg_info
[i
].nrefs
++;
1605 lra_reg_info
[i
].freq
+= freq
;
1609 /* Set up insn reg info of INSN. Update common reg info from reg info
1612 lra_update_insn_regno_info (rtx_insn
*insn
)
1615 lra_insn_recog_data_t data
;
1616 struct lra_static_insn_data
*static_data
;
1620 if (! INSN_P (insn
))
1622 data
= lra_get_insn_recog_data (insn
);
1623 static_data
= data
->insn_static_data
;
1624 freq
= NONDEBUG_INSN_P (insn
) ? get_insn_freq (insn
) : 0;
1625 invalidate_insn_data_regno_info (data
, insn
, freq
);
1626 for (i
= static_data
->n_operands
- 1; i
>= 0; i
--)
1627 add_regs_to_insn_regno_info (data
, *data
->operand_loc
[i
], insn
,
1628 static_data
->operand
[i
].type
,
1629 static_data
->operand
[i
].early_clobber_alts
);
1630 if ((code
= GET_CODE (PATTERN (insn
))) == CLOBBER
|| code
== USE
)
1631 add_regs_to_insn_regno_info (data
, XEXP (PATTERN (insn
), 0), insn
,
1632 code
== USE
? OP_IN
: OP_OUT
, 0);
1634 /* On some targets call insns can refer to pseudos in memory in
1635 CALL_INSN_FUNCTION_USAGE list. Process them in order to
1636 consider their occurrences in calls for different
1637 transformations (e.g. inheritance) with given pseudos. */
1638 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1640 link
= XEXP (link
, 1))
1642 code
= GET_CODE (XEXP (link
, 0));
1643 if ((code
== USE
|| code
== CLOBBER
)
1644 && MEM_P (XEXP (XEXP (link
, 0), 0)))
1645 add_regs_to_insn_regno_info (data
, XEXP (XEXP (link
, 0), 0), insn
,
1646 code
== USE
? OP_IN
: OP_OUT
, 0);
1648 if (NONDEBUG_INSN_P (insn
))
1649 setup_insn_reg_info (data
, freq
);
1652 /* Return reg info of insn given by it UID. */
1653 struct lra_insn_reg
*
1654 lra_get_insn_regs (int uid
)
1656 lra_insn_recog_data_t data
;
1658 data
= get_insn_recog_data_by_uid (uid
);
1664 /* Recursive hash function for RTL X. */
1666 lra_rtx_hash (rtx x
)
1676 code
= GET_CODE (x
);
1677 val
+= (int) code
+ 4095;
1679 /* Some RTL can be compared nonrecursively. */
1683 return val
+ REGNO (x
);
1686 return iterative_hash_object (XEXP (x
, 0), val
);
1689 return iterative_hash_object (XSTR (x
, 0), val
);
1697 return val
+ UINTVAL (x
);
1703 /* Hash the elements. */
1704 fmt
= GET_RTX_FORMAT (code
);
1705 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1710 val
+= XWINT (x
, i
);
1720 val
+= XVECLEN (x
, i
);
1722 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1723 val
+= lra_rtx_hash (XVECEXP (x
, i
, j
));
1727 val
+= lra_rtx_hash (XEXP (x
, i
));
1732 val
+= htab_hash_string (XSTR (x
, i
));
1740 /* It is believed that rtx's at this level will never
1741 contain anything but integers and other rtx's, except for
1742 within LABEL_REFs and SYMBOL_REFs. */
1752 /* This page contains code dealing with stack of the insns which
1753 should be processed by the next constraint pass. */
1755 /* Bitmap used to put an insn on the stack only in one exemplar. */
1756 static sbitmap lra_constraint_insn_stack_bitmap
;
1758 /* The stack itself. */
1759 vec
<rtx_insn
*> lra_constraint_insn_stack
;
1761 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1762 info for INSN, otherwise only update it if INSN is not already on the
1765 lra_push_insn_1 (rtx_insn
*insn
, bool always_update
)
1767 unsigned int uid
= INSN_UID (insn
);
1769 lra_update_insn_regno_info (insn
);
1770 if (uid
>= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap
))
1771 lra_constraint_insn_stack_bitmap
=
1772 sbitmap_resize (lra_constraint_insn_stack_bitmap
, 3 * uid
/ 2, 0);
1773 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap
, uid
))
1775 bitmap_set_bit (lra_constraint_insn_stack_bitmap
, uid
);
1776 if (! always_update
)
1777 lra_update_insn_regno_info (insn
);
1778 lra_constraint_insn_stack
.safe_push (insn
);
1781 /* Put INSN on the stack. */
1783 lra_push_insn (rtx_insn
*insn
)
1785 lra_push_insn_1 (insn
, false);
1788 /* Put INSN on the stack and update its reg info. */
1790 lra_push_insn_and_update_insn_regno_info (rtx_insn
*insn
)
1792 lra_push_insn_1 (insn
, true);
1795 /* Put insn with UID on the stack. */
1797 lra_push_insn_by_uid (unsigned int uid
)
1799 lra_push_insn (lra_insn_recog_data
[uid
]->insn
);
1802 /* Take the last-inserted insns off the stack and return it. */
1806 rtx_insn
*insn
= lra_constraint_insn_stack
.pop ();
1807 bitmap_clear_bit (lra_constraint_insn_stack_bitmap
, INSN_UID (insn
));
1811 /* Return the current size of the insn stack. */
1813 lra_insn_stack_length (void)
1815 return lra_constraint_insn_stack
.length ();
1818 /* Push insns FROM to TO (excluding it) going in reverse order. */
1820 push_insns (rtx_insn
*from
, rtx_insn
*to
)
1824 if (from
== NULL_RTX
)
1826 for (insn
= from
; insn
!= to
; insn
= PREV_INSN (insn
))
1828 lra_push_insn (insn
);
1831 /* Set up sp offset for insn in range [FROM, LAST]. The offset is
1832 taken from the next BB insn after LAST or zero if there in such
1835 setup_sp_offset (rtx_insn
*from
, rtx_insn
*last
)
1837 rtx_insn
*before
= next_nonnote_nondebug_insn_bb (last
);
1838 poly_int64 offset
= (before
== NULL_RTX
|| ! INSN_P (before
)
1839 ? 0 : lra_get_insn_recog_data (before
)->sp_offset
);
1841 for (rtx_insn
*insn
= from
; insn
!= NEXT_INSN (last
); insn
= NEXT_INSN (insn
))
1842 lra_get_insn_recog_data (insn
)->sp_offset
= offset
;
1845 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1846 insns onto the stack. Print about emitting the insns with
1849 lra_process_new_insns (rtx_insn
*insn
, rtx_insn
*before
, rtx_insn
*after
,
1854 if (before
== NULL_RTX
&& after
== NULL_RTX
)
1856 if (lra_dump_file
!= NULL
)
1858 dump_insn_slim (lra_dump_file
, insn
);
1859 if (before
!= NULL_RTX
)
1861 fprintf (lra_dump_file
," %s before:\n", title
);
1862 dump_rtl_slim (lra_dump_file
, before
, NULL
, -1, 0);
1864 if (after
!= NULL_RTX
)
1866 fprintf (lra_dump_file
, " %s after:\n", title
);
1867 dump_rtl_slim (lra_dump_file
, after
, NULL
, -1, 0);
1869 fprintf (lra_dump_file
, "\n");
1871 if (before
!= NULL_RTX
)
1873 if (cfun
->can_throw_non_call_exceptions
)
1874 copy_reg_eh_region_note_forward (insn
, before
, NULL
);
1875 emit_insn_before (before
, insn
);
1876 push_insns (PREV_INSN (insn
), PREV_INSN (before
));
1877 setup_sp_offset (before
, PREV_INSN (insn
));
1879 if (after
!= NULL_RTX
)
1881 if (cfun
->can_throw_non_call_exceptions
)
1882 copy_reg_eh_region_note_forward (insn
, after
, NULL
);
1883 for (last
= after
; NEXT_INSN (last
) != NULL_RTX
; last
= NEXT_INSN (last
))
1885 emit_insn_after (after
, insn
);
1886 push_insns (last
, insn
);
1887 setup_sp_offset (after
, last
);
1889 if (cfun
->can_throw_non_call_exceptions
)
1891 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
1892 if (note
&& !insn_could_throw_p (insn
))
1893 remove_note (insn
, note
);
1898 /* Replace all references to register OLD_REGNO in *LOC with pseudo
1899 register NEW_REG. Try to simplify subreg of constant if SUBREG_P.
1900 DEBUG_P is if LOC is within a DEBUG_INSN. Return true if any
1903 lra_substitute_pseudo (rtx
*loc
, int old_regno
, rtx new_reg
, bool subreg_p
,
1907 bool result
= false;
1915 code
= GET_CODE (x
);
1916 if (code
== SUBREG
&& subreg_p
)
1918 rtx subst
, inner
= SUBREG_REG (x
);
1919 /* Transform subreg of constant while we still have inner mode
1920 of the subreg. The subreg internal should not be an insn
1922 if (REG_P (inner
) && (int) REGNO (inner
) == old_regno
1923 && CONSTANT_P (new_reg
)
1924 && (subst
= simplify_subreg (GET_MODE (x
), new_reg
, GET_MODE (inner
),
1925 SUBREG_BYTE (x
))) != NULL_RTX
)
1932 else if (code
== REG
&& (int) REGNO (x
) == old_regno
)
1934 machine_mode mode
= GET_MODE (x
);
1935 machine_mode inner_mode
= GET_MODE (new_reg
);
1937 if (mode
!= inner_mode
1938 && ! (CONST_SCALAR_INT_P (new_reg
) && SCALAR_INT_MODE_P (mode
)))
1940 poly_uint64 offset
= 0;
1941 if (partial_subreg_p (mode
, inner_mode
)
1942 && SCALAR_INT_MODE_P (inner_mode
))
1943 offset
= subreg_lowpart_offset (mode
, inner_mode
);
1945 new_reg
= gen_rtx_raw_SUBREG (mode
, new_reg
, offset
);
1947 new_reg
= gen_rtx_SUBREG (mode
, new_reg
, offset
);
1953 /* Scan all the operand sub-expressions. */
1954 fmt
= GET_RTX_FORMAT (code
);
1955 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1959 if (lra_substitute_pseudo (&XEXP (x
, i
), old_regno
,
1960 new_reg
, subreg_p
, debug_p
))
1963 else if (fmt
[i
] == 'E')
1965 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1966 if (lra_substitute_pseudo (&XVECEXP (x
, i
, j
), old_regno
,
1967 new_reg
, subreg_p
, debug_p
))
1974 /* Call lra_substitute_pseudo within an insn. Try to simplify subreg
1975 of constant if SUBREG_P. This won't update the insn ptr, just the
1976 contents of the insn. */
1978 lra_substitute_pseudo_within_insn (rtx_insn
*insn
, int old_regno
,
1979 rtx new_reg
, bool subreg_p
)
1982 return lra_substitute_pseudo (&loc
, old_regno
, new_reg
, subreg_p
,
1983 DEBUG_INSN_P (insn
));
1988 /* This page contains code dealing with scratches (changing them onto
1989 pseudos and restoring them from the pseudos).
1991 We change scratches into pseudos at the beginning of LRA to
1992 simplify dealing with them (conflicts, hard register assignments).
1994 If the pseudo denoting scratch was spilled it means that we do need
1995 a hard register for it. Such pseudos are transformed back to
1996 scratches at the end of LRA. */
1998 /* Description of location of a former scratch operand. */
2001 rtx_insn
*insn
; /* Insn where the scratch was. */
2002 int nop
; /* Number of the operand which was a scratch. */
2003 int icode
; /* Original icode from which scratch was removed. */
2006 typedef struct sloc
*sloc_t
;
2008 /* Locations of the former scratches. */
2009 static vec
<sloc_t
> scratches
;
2011 /* Bitmap of scratch regnos. */
2012 static bitmap_head scratch_bitmap
;
2014 /* Bitmap of scratch operands. */
2015 static bitmap_head scratch_operand_bitmap
;
2017 /* Return true if pseudo REGNO is made of SCRATCH. */
2019 lra_former_scratch_p (int regno
)
2021 return bitmap_bit_p (&scratch_bitmap
, regno
);
2024 /* Return true if the operand NOP of INSN is a former scratch. */
2026 lra_former_scratch_operand_p (rtx_insn
*insn
, int nop
)
2028 return bitmap_bit_p (&scratch_operand_bitmap
,
2029 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
) != 0;
2032 /* Register operand NOP in INSN as a former scratch. It will be
2033 changed to scratch back, if it is necessary, at the LRA end. */
2035 lra_register_new_scratch_op (rtx_insn
*insn
, int nop
, int icode
)
2037 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
2038 rtx op
= *id
->operand_loc
[nop
];
2039 sloc_t loc
= XNEW (struct sloc
);
2040 lra_assert (REG_P (op
));
2044 scratches
.safe_push (loc
);
2045 bitmap_set_bit (&scratch_bitmap
, REGNO (op
));
2046 bitmap_set_bit (&scratch_operand_bitmap
,
2047 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
);
2048 add_reg_note (insn
, REG_UNUSED
, op
);
2051 /* Change INSN's scratches into pseudos and save their location. */
2053 remove_scratches_1 (rtx_insn
*insn
)
2056 bool insn_changed_p
;
2058 lra_insn_recog_data_t id
;
2059 struct lra_static_insn_data
*static_id
;
2061 id
= lra_get_insn_recog_data (insn
);
2062 static_id
= id
->insn_static_data
;
2063 insn_changed_p
= false;
2064 for (i
= 0; i
< static_id
->n_operands
; i
++)
2065 if (GET_CODE (*id
->operand_loc
[i
]) == SCRATCH
2066 && GET_MODE (*id
->operand_loc
[i
]) != VOIDmode
)
2068 insn_changed_p
= true;
2069 *id
->operand_loc
[i
] = reg
2070 = lra_create_new_reg (static_id
->operand
[i
].mode
,
2071 *id
->operand_loc
[i
], ALL_REGS
, NULL
);
2072 lra_register_new_scratch_op (insn
, i
, id
->icode
);
2073 if (lra_dump_file
!= NULL
)
2074 fprintf (lra_dump_file
,
2075 "Removing SCRATCH in insn #%u (nop %d)\n",
2076 INSN_UID (insn
), i
);
2079 /* Because we might use DF right after caller-saves sub-pass
2080 we need to keep DF info up to date. */
2081 df_insn_rescan (insn
);
2084 /* Change scratches into pseudos and save their location. */
2086 remove_scratches (void)
2091 scratches
.create (get_max_uid ());
2092 bitmap_initialize (&scratch_bitmap
, ®_obstack
);
2093 bitmap_initialize (&scratch_operand_bitmap
, ®_obstack
);
2094 FOR_EACH_BB_FN (bb
, cfun
)
2095 FOR_BB_INSNS (bb
, insn
)
2097 remove_scratches_1 (insn
);
2100 /* Changes pseudos created by function remove_scratches onto scratches. */
2102 restore_scratches (void)
2107 rtx_insn
*last
= NULL
;
2108 lra_insn_recog_data_t id
= NULL
;
2110 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
2112 /* Ignore already deleted insns. */
2113 if (NOTE_P (loc
->insn
)
2114 && NOTE_KIND (loc
->insn
) == NOTE_INSN_DELETED
)
2116 if (last
!= loc
->insn
)
2119 id
= lra_get_insn_recog_data (last
);
2121 if (loc
->icode
!= id
->icode
)
2123 /* The icode doesn't match, which means the insn has been modified
2124 (e.g. register elimination). The scratch cannot be restored. */
2127 if (REG_P (*id
->operand_loc
[loc
->nop
])
2128 && ((regno
= REGNO (*id
->operand_loc
[loc
->nop
]))
2129 >= FIRST_PSEUDO_REGISTER
)
2130 && lra_get_regno_hard_regno (regno
) < 0)
2132 /* It should be only case when scratch register with chosen
2133 constraint 'X' did not get memory or hard register. */
2134 lra_assert (lra_former_scratch_p (regno
));
2135 *id
->operand_loc
[loc
->nop
]
2136 = gen_rtx_SCRATCH (GET_MODE (*id
->operand_loc
[loc
->nop
]));
2137 lra_update_dup (id
, loc
->nop
);
2138 if (lra_dump_file
!= NULL
)
2139 fprintf (lra_dump_file
, "Restoring SCRATCH in insn #%u(nop %d)\n",
2140 INSN_UID (loc
->insn
), loc
->nop
);
2143 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
2145 scratches
.release ();
2146 bitmap_clear (&scratch_bitmap
);
2147 bitmap_clear (&scratch_operand_bitmap
);
2152 /* Function checks RTL for correctness. If FINAL_P is true, it is
2153 done at the end of LRA and the check is more rigorous. */
2155 check_rtl (bool final_p
)
2160 lra_assert (! final_p
|| reload_completed
);
2161 FOR_EACH_BB_FN (bb
, cfun
)
2162 FOR_BB_INSNS (bb
, insn
)
2163 if (NONDEBUG_INSN_P (insn
)
2164 && GET_CODE (PATTERN (insn
)) != USE
2165 && GET_CODE (PATTERN (insn
)) != CLOBBER
2166 && GET_CODE (PATTERN (insn
)) != ASM_INPUT
)
2170 extract_constrain_insn (insn
);
2173 /* LRA code is based on assumption that all addresses can be
2174 correctly decomposed. LRA can generate reloads for
2175 decomposable addresses. The decomposition code checks the
2176 correctness of the addresses. So we don't need to check
2177 the addresses here. Don't call insn_invalid_p here, it can
2178 change the code at this stage. */
2179 if (recog_memoized (insn
) < 0 && asm_noperands (PATTERN (insn
)) < 0)
2180 fatal_insn_not_found (insn
);
2184 /* Determine if the current function has an exception receiver block
2185 that reaches the exit block via non-exceptional edges */
2187 has_nonexceptional_receiver (void)
2191 basic_block
*tos
, *worklist
, bb
;
2193 /* If we're not optimizing, then just err on the safe side. */
2197 /* First determine which blocks can reach exit via normal paths. */
2198 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
) + 1);
2200 FOR_EACH_BB_FN (bb
, cfun
)
2201 bb
->flags
&= ~BB_REACHABLE
;
2203 /* Place the exit block on our worklist. */
2204 EXIT_BLOCK_PTR_FOR_FN (cfun
)->flags
|= BB_REACHABLE
;
2205 *tos
++ = EXIT_BLOCK_PTR_FOR_FN (cfun
);
2207 /* Iterate: find everything reachable from what we've already seen. */
2208 while (tos
!= worklist
)
2212 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2213 if (e
->flags
& EDGE_ABNORMAL
)
2220 basic_block src
= e
->src
;
2222 if (!(src
->flags
& BB_REACHABLE
))
2224 src
->flags
|= BB_REACHABLE
;
2230 /* No exceptional block reached exit unexceptionally. */
2235 /* Process recursively X of INSN and add REG_INC notes if necessary. */
2237 add_auto_inc_notes (rtx_insn
*insn
, rtx x
)
2239 enum rtx_code code
= GET_CODE (x
);
2243 if (code
== MEM
&& auto_inc_p (XEXP (x
, 0)))
2245 add_reg_note (insn
, REG_INC
, XEXP (XEXP (x
, 0), 0));
2249 /* Scan all X sub-expressions. */
2250 fmt
= GET_RTX_FORMAT (code
);
2251 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2254 add_auto_inc_notes (insn
, XEXP (x
, i
));
2255 else if (fmt
[i
] == 'E')
2256 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2257 add_auto_inc_notes (insn
, XVECEXP (x
, i
, j
));
2262 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2263 We change pseudos by hard registers without notification of DF and
2264 that can make the notes obsolete. DF-infrastructure does not deal
2265 with REG_INC notes -- so we should regenerate them here. */
2267 update_inc_notes (void)
2273 FOR_EACH_BB_FN (bb
, cfun
)
2274 FOR_BB_INSNS (bb
, insn
)
2275 if (NONDEBUG_INSN_P (insn
))
2277 pnote
= ®_NOTES (insn
);
2280 if (REG_NOTE_KIND (*pnote
) == REG_DEAD
2281 || REG_NOTE_KIND (*pnote
) == REG_UNUSED
2282 || REG_NOTE_KIND (*pnote
) == REG_INC
)
2283 *pnote
= XEXP (*pnote
, 1);
2285 pnote
= &XEXP (*pnote
, 1);
2289 add_auto_inc_notes (insn
, PATTERN (insn
));
2293 /* Set to 1 while in lra. */
2294 int lra_in_progress
;
2296 /* Start of pseudo regnos before the LRA. */
2297 int lra_new_regno_start
;
2299 /* Start of reload pseudo regnos before the new spill pass. */
2300 int lra_constraint_new_regno_start
;
2302 /* Avoid spilling pseudos with regno more than the following value if
2304 int lra_bad_spill_regno_start
;
2306 /* Inheritance pseudo regnos before the new spill pass. */
2307 bitmap_head lra_inheritance_pseudos
;
2309 /* Split regnos before the new spill pass. */
2310 bitmap_head lra_split_regs
;
2312 /* Reload pseudo regnos before the new assignment pass which still can
2313 be spilled after the assignment pass as memory is also accepted in
2314 insns for the reload pseudos. */
2315 bitmap_head lra_optional_reload_pseudos
;
2317 /* Pseudo regnos used for subreg reloads before the new assignment
2318 pass. Such pseudos still can be spilled after the assignment
2320 bitmap_head lra_subreg_reload_pseudos
;
2322 /* File used for output of LRA debug information. */
2323 FILE *lra_dump_file
;
2325 /* True if we found an asm error. */
2326 bool lra_asm_error_p
;
2328 /* True if we should try spill into registers of different classes
2329 instead of memory. */
2330 bool lra_reg_spill_p
;
2332 /* Set up value LRA_REG_SPILL_P. */
2334 setup_reg_spill_flag (void)
2338 if (targetm
.spill_class
!= NULL
)
2339 for (cl
= 0; cl
< (int) LIM_REG_CLASSES
; cl
++)
2340 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
2341 if (targetm
.spill_class ((enum reg_class
) cl
,
2342 (machine_mode
) mode
) != NO_REGS
)
2344 lra_reg_spill_p
= true;
2347 lra_reg_spill_p
= false;
2350 /* True if the current function is too big to use regular algorithms
2351 in LRA. In other words, we should use simpler and faster algorithms
2352 in LRA. It also means we should not worry about generation code
2353 for caller saves. The value is set up in IRA. */
2356 /* Major LRA entry function. F is a file should be used to dump LRA
2362 bool live_p
, inserted_p
;
2365 lra_asm_error_p
= false;
2367 timevar_push (TV_LRA
);
2369 /* Make sure that the last insn is a note. Some subsequent passes
2371 emit_note (NOTE_INSN_DELETED
);
2373 lra_no_alloc_regs
= ira_no_alloc_regs
;
2378 init_insn_recog_data ();
2380 /* Some quick check on RTL generated by previous passes. */
2384 lra_in_progress
= 1;
2386 lra_live_range_iter
= lra_coalesce_iter
= lra_constraint_iter
= 0;
2387 lra_assignment_iter
= lra_assignment_iter_after_spill
= 0;
2388 lra_inheritance_iter
= lra_undo_inheritance_iter
= 0;
2389 lra_rematerialization_iter
= 0;
2391 setup_reg_spill_flag ();
2393 /* Function remove_scratches can creates new pseudos for clobbers --
2394 so set up lra_constraint_new_regno_start before its call to
2395 permit changing reg classes for pseudos created by this
2397 lra_constraint_new_regno_start
= lra_new_regno_start
= max_reg_num ();
2398 lra_bad_spill_regno_start
= INT_MAX
;
2399 remove_scratches ();
2401 /* A function that has a non-local label that can reach the exit
2402 block via non-exceptional paths must save all call-saved
2404 if (cfun
->has_nonlocal_label
&& has_nonexceptional_receiver ())
2405 crtl
->saves_all_registers
= 1;
2407 if (crtl
->saves_all_registers
)
2408 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2409 if (!crtl
->abi
->clobbers_full_reg_p (i
)
2411 && !LOCAL_REGNO (i
))
2412 df_set_regs_ever_live (i
, true);
2414 /* We don't DF from now and avoid its using because it is to
2415 expensive when a lot of RTL changes are made. */
2416 df_set_flags (DF_NO_INSN_RESCAN
);
2417 lra_constraint_insn_stack
.create (get_max_uid ());
2418 lra_constraint_insn_stack_bitmap
= sbitmap_alloc (get_max_uid ());
2419 bitmap_clear (lra_constraint_insn_stack_bitmap
);
2420 lra_live_ranges_init ();
2421 lra_constraints_init ();
2422 lra_curr_reload_num
= 0;
2423 push_insns (get_last_insn (), NULL
);
2424 /* It is needed for the 1st coalescing. */
2425 bitmap_initialize (&lra_inheritance_pseudos
, ®_obstack
);
2426 bitmap_initialize (&lra_split_regs
, ®_obstack
);
2427 bitmap_initialize (&lra_optional_reload_pseudos
, ®_obstack
);
2428 bitmap_initialize (&lra_subreg_reload_pseudos
, ®_obstack
);
2430 if (maybe_ne (get_frame_size (), 0) && crtl
->stack_alignment_needed
)
2431 /* If we have a stack frame, we must align it now. The stack size
2432 may be a part of the offset computation for register
2434 assign_stack_local (BLKmode
, 0, crtl
->stack_alignment_needed
);
2440 bool reloads_p
= lra_constraints (lra_constraint_iter
== 0);
2441 /* Constraint transformations may result in that eliminable
2442 hard regs become uneliminable and pseudos which use them
2443 should be spilled. It is better to do it before pseudo
2446 For example, rs6000 can make
2447 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2448 to use a constant pool. */
2449 lra_eliminate (false, false);
2450 /* We should try to assign hard registers to scratches even
2451 if there were no RTL transformations in lra_constraints.
2452 Also we should check IRA assignments on the first
2453 iteration as they can be wrong because of early clobbers
2454 operands which are ignored in IRA. */
2455 if (! reloads_p
&& lra_constraint_iter
> 1)
2457 /* Stack is not empty here only when there are changes
2458 during the elimination sub-pass. */
2459 if (bitmap_empty_p (lra_constraint_insn_stack_bitmap
))
2462 /* If there are no reloads but changing due
2463 elimination, restart the constraint sub-pass
2467 /* Do inheritance only for regular algorithms. */
2471 lra_clear_live_ranges ();
2475 /* We need live ranges for lra_assign -- so build them.
2476 But don't remove dead insns or change global live
2477 info as we can undo inheritance transformations after
2478 inheritance pseudo assigning. */
2479 lra_create_live_ranges (true, !lra_simple_p
);
2481 /* If we don't spill non-reload and non-inheritance
2482 pseudos, there is no sense to run memory-memory move
2483 coalescing. If inheritance pseudos were spilled, the
2484 memory-memory moves involving them will be removed by
2485 pass undoing inheritance. */
2487 lra_assign (fails_p
);
2490 bool spill_p
= !lra_assign (fails_p
);
2492 if (lra_undo_inheritance ())
2494 if (spill_p
&& ! fails_p
)
2498 lra_create_live_ranges (true, true);
2501 if (lra_coalesce ())
2505 lra_clear_live_ranges ();
2509 /* It is a very rare case. It is the last hope to
2510 split a hard regno live range for a reload
2513 lra_clear_live_ranges ();
2515 if (! lra_split_hard_reg_for ())
2521 /* We need the correct reg notes for work of constraint sub-pass. */
2522 lra_create_live_ranges (true, true);
2526 /* Don't clear optional reloads bitmap until all constraints are
2527 satisfied as we need to differ them from regular reloads. */
2528 bitmap_clear (&lra_optional_reload_pseudos
);
2529 bitmap_clear (&lra_subreg_reload_pseudos
);
2530 bitmap_clear (&lra_inheritance_pseudos
);
2531 bitmap_clear (&lra_split_regs
);
2534 /* We need full live info for spilling pseudos into
2535 registers instead of memory. */
2536 lra_create_live_ranges (lra_reg_spill_p
, true);
2539 /* We should check necessity for spilling here as the above live
2540 range pass can remove spilled pseudos. */
2541 if (! lra_need_for_spills_p ())
2543 /* Now we know what pseudos should be spilled. Try to
2544 rematerialize them first. */
2547 /* We need full live info -- see the comment above. */
2548 lra_create_live_ranges (lra_reg_spill_p
, true);
2550 if (! lra_need_for_spills_p ())
2552 if (lra_need_for_scratch_reg_p ())
2558 /* Assignment of stack slots changes elimination offsets for
2559 some eliminations. So update the offsets here. */
2560 lra_eliminate (false, false);
2561 lra_constraint_new_regno_start
= max_reg_num ();
2562 if (lra_bad_spill_regno_start
== INT_MAX
2563 && lra_inheritance_iter
> LRA_MAX_INHERITANCE_PASSES
2564 && lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
2565 /* After switching off inheritance and rematerialization
2566 passes, avoid spilling reload pseudos will be created to
2567 prevent LRA cycling in some complicated cases. */
2568 lra_bad_spill_regno_start
= lra_constraint_new_regno_start
;
2569 lra_assignment_iter_after_spill
= 0;
2571 restore_scratches ();
2572 lra_eliminate (true, false);
2573 lra_final_code_change ();
2574 lra_in_progress
= 0;
2576 lra_clear_live_ranges ();
2577 lra_live_ranges_finish ();
2578 lra_constraints_finish ();
2580 sbitmap_free (lra_constraint_insn_stack_bitmap
);
2581 lra_constraint_insn_stack
.release ();
2582 finish_insn_recog_data ();
2583 regstat_free_n_sets_and_refs ();
2585 reload_completed
= 1;
2586 update_inc_notes ();
2588 inserted_p
= fixup_abnormal_edges ();
2590 /* We've possibly turned single trapping insn into multiple ones. */
2591 if (cfun
->can_throw_non_call_exceptions
)
2593 auto_sbitmap
blocks (last_basic_block_for_fn (cfun
));
2594 bitmap_ones (blocks
);
2595 find_many_sub_basic_blocks (blocks
);
2599 commit_edge_insertions ();
2601 /* Replacing pseudos with their memory equivalents might have
2602 created shared rtx. Subsequent passes would get confused
2603 by this, so unshare everything here. */
2604 unshare_all_rtl_again (get_insns ());
2609 timevar_pop (TV_LRA
);
2612 /* Called once per compiler to initialize LRA data once. */
2614 lra_init_once (void)
2616 init_insn_code_data_once ();
2619 /* Called once per compiler to finish LRA data which are initialize
2622 lra_finish_once (void)
2624 finish_insn_code_data_once ();