1 /* LRA (local register allocator) driver and LRA utilities.
2 Copyright (C) 2010-2019 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 /* The Local Register Allocator (LRA) is a replacement of former
23 reload pass. It is focused to simplify code solving the reload
24 pass tasks, to make the code maintenance easier, and to implement new
25 perspective optimizations.
27 The major LRA design solutions are:
28 o division small manageable, separated sub-tasks
29 o reflection of all transformations and decisions in RTL as more
31 o insn constraints as a primary source of the info (minimizing
32 number of target-depended macros/hooks)
34 In brief LRA works by iterative insn process with the final goal is
35 to satisfy all insn and address constraints:
36 o New reload insns (in brief reloads) and reload pseudos might be
38 o Some pseudos might be spilled to assign hard registers to
40 o Recalculating spilled pseudo values (rematerialization);
41 o Changing spilled pseudos to stack memory or their equivalences;
42 o Allocation stack memory changes the address displacement and
43 new iteration is needed.
45 Here is block diagram of LRA passes:
47 ------------------------
48 --------------- | Undo inheritance for | ---------------
49 | Memory-memory | | spilled pseudos, | | New (and old) |
50 | move coalesce |<---| splits for pseudos got |<-- | pseudos |
51 --------------- | the same hard regs, | | assignment |
52 Start | | and optional reloads | ---------------
53 | | ------------------------ ^
54 V | ---------------- |
55 ----------- V | Update virtual | |
56 | Remove |----> ------------>| register | |
57 | scratches | ^ | displacements | |
58 ----------- | ---------------- |
61 | ------------ pseudos -------------------
62 | |Constraints:| or insns | Inheritance/split |
63 | | RTL |--------->| transformations |
64 | | transfor- | | in EBB scope |
65 | substi- | mations | -------------------
66 | tutions ------------
69 | Spilled pseudo | -------------------
70 | to memory |<----| Rematerialization |
71 | substitution | -------------------
75 -------------------------
76 | Hard regs substitution, |
77 | devirtalization, and |------> Finish
78 | restoring scratches got |
80 -------------------------
82 To speed up the process:
83 o We process only insns affected by changes on previous
85 o We don't use DFA-infrastructure because it results in much slower
86 compiler speed than a special IR described below does;
87 o We use a special insn representation for quick access to insn
88 info which is always *synchronized* with the current RTL;
89 o Insn IR is minimized by memory. It is divided on three parts:
90 o one specific for each insn in RTL (only operand locations);
91 o one common for all insns in RTL with the same insn code
92 (different operand attributes from machine descriptions);
93 o one oriented for maintenance of live info (list of pseudos).
95 o all insns where the pseudo is referenced;
96 o live info (conflicting hard regs, live ranges, # of
98 o data used for assigning (preferred hard regs, costs etc).
100 This file contains LRA driver, LRA utility functions and data, and
101 code for dealing with scratches. */
105 #include "coretypes.h"
112 #include "memmodel.h"
120 #include "cfgbuild.h"
123 #include "print-rtl.h"
125 /* Dump bitmap SET with TITLE and BB INDEX. */
127 lra_dump_bitmap_with_title (const char *title
, bitmap set
, int index
)
132 static const int max_nums_on_line
= 10;
134 if (bitmap_empty_p (set
))
136 fprintf (lra_dump_file
, " %s %d:", title
, index
);
137 fprintf (lra_dump_file
, "\n");
138 count
= max_nums_on_line
+ 1;
139 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
141 if (count
> max_nums_on_line
)
143 fprintf (lra_dump_file
, "\n ");
146 fprintf (lra_dump_file
, " %4u", i
);
149 fprintf (lra_dump_file
, "\n");
152 /* Hard registers currently not available for allocation. It can
153 changed after some hard registers become not eliminable. */
154 HARD_REG_SET lra_no_alloc_regs
;
156 static int get_new_reg_value (void);
157 static void expand_reg_info (void);
158 static void invalidate_insn_recog_data (int);
159 static int get_insn_freq (rtx_insn
*);
160 static void invalidate_insn_data_regno_info (lra_insn_recog_data_t
,
162 static void remove_scratches_1 (rtx_insn
*);
164 /* Expand all regno related info needed for LRA. */
166 expand_reg_data (int old
)
170 ira_expand_reg_equiv ();
171 for (int i
= (int) max_reg_num () - 1; i
>= old
; i
--)
172 lra_change_class (i
, ALL_REGS
, " Set", true);
175 /* Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL
176 or of VOIDmode, use MD_MODE for the new reg. Initialize its
177 register class to RCLASS. Print message about assigning class
178 RCLASS containing new register name TITLE unless it is NULL. Use
179 attributes of ORIGINAL if it is a register. The created register
180 will have unique held value. */
182 lra_create_new_reg_with_unique_value (machine_mode md_mode
, rtx original
,
183 enum reg_class rclass
, const char *title
)
188 if (original
== NULL_RTX
|| (mode
= GET_MODE (original
)) == VOIDmode
)
190 lra_assert (mode
!= VOIDmode
);
191 new_reg
= gen_reg_rtx (mode
);
192 if (original
== NULL_RTX
|| ! REG_P (original
))
194 if (lra_dump_file
!= NULL
)
195 fprintf (lra_dump_file
, " Creating newreg=%i", REGNO (new_reg
));
199 if (ORIGINAL_REGNO (original
) >= FIRST_PSEUDO_REGISTER
)
200 ORIGINAL_REGNO (new_reg
) = ORIGINAL_REGNO (original
);
201 REG_USERVAR_P (new_reg
) = REG_USERVAR_P (original
);
202 REG_POINTER (new_reg
) = REG_POINTER (original
);
203 REG_ATTRS (new_reg
) = REG_ATTRS (original
);
204 if (lra_dump_file
!= NULL
)
205 fprintf (lra_dump_file
, " Creating newreg=%i from oldreg=%i",
206 REGNO (new_reg
), REGNO (original
));
208 if (lra_dump_file
!= NULL
)
211 fprintf (lra_dump_file
, ", assigning class %s to%s%s r%d",
212 reg_class_names
[rclass
], *title
== '\0' ? "" : " ",
213 title
, REGNO (new_reg
));
214 fprintf (lra_dump_file
, "\n");
216 expand_reg_data (max_reg_num ());
217 setup_reg_classes (REGNO (new_reg
), rclass
, NO_REGS
, rclass
);
221 /* Analogous to the previous function but also inherits value of
224 lra_create_new_reg (machine_mode md_mode
, rtx original
,
225 enum reg_class rclass
, const char *title
)
230 = lra_create_new_reg_with_unique_value (md_mode
, original
, rclass
, title
);
231 if (original
!= NULL_RTX
&& REG_P (original
))
232 lra_assign_reg_val (REGNO (original
), REGNO (new_reg
));
236 /* Set up for REGNO unique hold value. */
238 lra_set_regno_unique_value (int regno
)
240 lra_reg_info
[regno
].val
= get_new_reg_value ();
243 /* Invalidate INSN related info used by LRA. The info should never be
246 lra_invalidate_insn_data (rtx_insn
*insn
)
248 lra_invalidate_insn_regno_info (insn
);
249 invalidate_insn_recog_data (INSN_UID (insn
));
252 /* Mark INSN deleted and invalidate the insn related info used by
255 lra_set_insn_deleted (rtx_insn
*insn
)
257 lra_invalidate_insn_data (insn
);
258 SET_INSN_DELETED (insn
);
261 /* Delete an unneeded INSN and any previous insns who sole purpose is
262 loading data that is dead in INSN. */
264 lra_delete_dead_insn (rtx_insn
*insn
)
266 rtx_insn
*prev
= prev_real_insn (insn
);
269 /* If the previous insn sets a register that dies in our insn,
271 if (prev
&& GET_CODE (PATTERN (prev
)) == SET
272 && (prev_dest
= SET_DEST (PATTERN (prev
)), REG_P (prev_dest
))
273 && reg_mentioned_p (prev_dest
, PATTERN (insn
))
274 && find_regno_note (insn
, REG_DEAD
, REGNO (prev_dest
))
275 && ! side_effects_p (SET_SRC (PATTERN (prev
))))
276 lra_delete_dead_insn (prev
);
278 lra_set_insn_deleted (insn
);
281 /* Emit insn x = y + z. Return NULL if we failed to do it.
282 Otherwise, return the insn. We don't use gen_add3_insn as it might
285 emit_add3_insn (rtx x
, rtx y
, rtx z
)
289 last
= get_last_insn ();
291 if (have_addptr3_insn (x
, y
, z
))
293 rtx_insn
*insn
= gen_addptr3_insn (x
, y
, z
);
295 /* If the target provides an "addptr" pattern it hopefully does
296 for a reason. So falling back to the normal add would be
298 lra_assert (insn
!= NULL_RTX
);
303 rtx_insn
*insn
= emit_insn (gen_rtx_SET (x
, gen_rtx_PLUS (GET_MODE (y
),
305 if (recog_memoized (insn
) < 0)
307 delete_insns_since (last
);
313 /* Emit insn x = x + y. Return the insn. We use gen_add2_insn as the
316 emit_add2_insn (rtx x
, rtx y
)
318 rtx_insn
*insn
= emit_add3_insn (x
, x
, y
);
319 if (insn
== NULL_RTX
)
321 insn
= gen_add2_insn (x
, y
);
322 if (insn
!= NULL_RTX
)
328 /* Target checks operands through operand predicates to recognize an
329 insn. We should have a special precaution to generate add insns
330 which are frequent results of elimination.
332 Emit insns for x = y + z. X can be used to store intermediate
333 values and should be not in Y and Z when we use X to store an
334 intermediate value. Y + Z should form [base] [+ index[ * scale]] [
335 + disp] where base and index are registers, disp and scale are
336 constants. Y should contain base if it is present, Z should
337 contain disp if any. index[*scale] can be part of Y or Z. */
339 lra_emit_add (rtx x
, rtx y
, rtx z
)
343 rtx a1
, a2
, base
, index
, disp
, scale
, index_scale
;
346 rtx_insn
*add3_insn
= emit_add3_insn (x
, y
, z
);
347 old
= max_reg_num ();
348 if (add3_insn
!= NULL
)
352 disp
= a2
= NULL_RTX
;
353 if (GET_CODE (y
) == PLUS
)
367 index_scale
= scale
= NULL_RTX
;
368 if (GET_CODE (a1
) == MULT
)
371 index
= XEXP (a1
, 0);
372 scale
= XEXP (a1
, 1);
375 else if (a2
!= NULL_RTX
&& GET_CODE (a2
) == MULT
)
378 index
= XEXP (a2
, 0);
379 scale
= XEXP (a2
, 1);
387 if ((base
!= NULL_RTX
&& ! (REG_P (base
) || GET_CODE (base
) == SUBREG
))
388 || (index
!= NULL_RTX
389 && ! (REG_P (index
) || GET_CODE (index
) == SUBREG
))
390 || (disp
!= NULL_RTX
&& ! CONSTANT_P (disp
))
391 || (scale
!= NULL_RTX
&& ! CONSTANT_P (scale
)))
393 /* Probably we have no 3 op add. Last chance is to use 2-op
394 add insn. To succeed, don't move Z to X as an address
395 segment always comes in Y. Otherwise, we might fail when
396 adding the address segment to register. */
397 lra_assert (x
!= y
&& x
!= z
);
398 emit_move_insn (x
, y
);
399 rtx_insn
*insn
= emit_add2_insn (x
, z
);
400 lra_assert (insn
!= NULL_RTX
);
404 if (index_scale
== NULL_RTX
)
406 if (disp
== NULL_RTX
)
408 /* Generate x = index_scale; x = x + base. */
409 lra_assert (index_scale
!= NULL_RTX
&& base
!= NULL_RTX
);
410 emit_move_insn (x
, index_scale
);
411 rtx_insn
*insn
= emit_add2_insn (x
, base
);
412 lra_assert (insn
!= NULL_RTX
);
414 else if (scale
== NULL_RTX
)
416 /* Try x = base + disp. */
417 lra_assert (base
!= NULL_RTX
);
418 last
= get_last_insn ();
419 rtx_insn
*move_insn
=
420 emit_move_insn (x
, gen_rtx_PLUS (GET_MODE (base
), base
, disp
));
421 if (recog_memoized (move_insn
) < 0)
423 delete_insns_since (last
);
424 /* Generate x = disp; x = x + base. */
425 emit_move_insn (x
, disp
);
426 rtx_insn
*add2_insn
= emit_add2_insn (x
, base
);
427 lra_assert (add2_insn
!= NULL_RTX
);
429 /* Generate x = x + index. */
430 if (index
!= NULL_RTX
)
432 rtx_insn
*insn
= emit_add2_insn (x
, index
);
433 lra_assert (insn
!= NULL_RTX
);
438 /* Try x = index_scale; x = x + disp; x = x + base. */
439 last
= get_last_insn ();
440 rtx_insn
*move_insn
= emit_move_insn (x
, index_scale
);
442 if (recog_memoized (move_insn
) >= 0)
444 rtx_insn
*insn
= emit_add2_insn (x
, disp
);
445 if (insn
!= NULL_RTX
)
447 if (base
== NULL_RTX
)
451 insn
= emit_add2_insn (x
, base
);
452 if (insn
!= NULL_RTX
)
461 delete_insns_since (last
);
462 /* Generate x = disp; x = x + base; x = x + index_scale. */
463 emit_move_insn (x
, disp
);
464 if (base
!= NULL_RTX
)
466 insn
= emit_add2_insn (x
, base
);
467 lra_assert (insn
!= NULL_RTX
);
469 insn
= emit_add2_insn (x
, index_scale
);
470 lra_assert (insn
!= NULL_RTX
);
475 /* Functions emit_... can create pseudos -- so expand the pseudo
477 if (old
!= max_reg_num ())
478 expand_reg_data (old
);
481 /* The number of emitted reload insns so far. */
482 int lra_curr_reload_num
;
484 /* Emit x := y, processing special case when y = u + v or y = u + v *
485 scale + w through emit_add (Y can be an address which is base +
486 index reg * scale + displacement in general case). X may be used
487 as intermediate result therefore it should be not in Y. */
489 lra_emit_move (rtx x
, rtx y
)
493 if (GET_CODE (y
) != PLUS
)
495 if (rtx_equal_p (x
, y
))
497 old
= max_reg_num ();
498 rtx_insn
*insn
= emit_move_insn (x
, y
);
499 /* The move pattern may require scratch registers, so convert them
500 into real registers now. */
501 if (insn
!= NULL_RTX
)
502 remove_scratches_1 (insn
);
504 lra_reg_info
[ORIGINAL_REGNO (x
)].last_reload
= ++lra_curr_reload_num
;
505 /* Function emit_move can create pseudos -- so expand the pseudo
507 if (old
!= max_reg_num ())
508 expand_reg_data (old
);
511 lra_emit_add (x
, XEXP (y
, 0), XEXP (y
, 1));
514 /* Update insn operands which are duplication of operands whose
515 numbers are in array of NOPS (with end marker -1). The insn is
516 represented by its LRA internal representation ID. */
518 lra_update_dups (lra_insn_recog_data_t id
, signed char *nops
)
521 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
523 for (i
= 0; i
< static_id
->n_dups
; i
++)
524 for (j
= 0; (nop
= nops
[j
]) >= 0; j
++)
525 if (static_id
->dup_num
[i
] == nop
)
526 *id
->dup_loc
[i
] = *id
->operand_loc
[nop
];
531 /* This page contains code dealing with info about registers in the
534 /* Pools for insn reg info. */
535 object_allocator
<lra_insn_reg
> lra_insn_reg_pool ("insn regs");
537 /* Create LRA insn related info about a reference to REGNO in INSN
538 with TYPE (in/out/inout), biggest reference mode MODE, flag that it
539 is reference through subreg (SUBREG_P), flag that is early
540 clobbered in the insn (EARLY_CLOBBER), 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. CLOBBER_HIGH marks if reference is a clobber
545 static struct lra_insn_reg
*
546 new_insn_reg (rtx_insn
*insn
, int regno
, enum op_type type
,
548 bool subreg_p
, bool early_clobber
,
549 alternative_mask early_clobber_alts
,
550 struct lra_insn_reg
*next
, bool clobber_high
)
552 lra_insn_reg
*ir
= lra_insn_reg_pool
.allocate ();
554 ir
->biggest_mode
= mode
;
555 if (NONDEBUG_INSN_P (insn
)
556 && partial_subreg_p (lra_reg_info
[regno
].biggest_mode
, mode
))
557 lra_reg_info
[regno
].biggest_mode
= mode
;
558 ir
->subreg_p
= subreg_p
;
559 ir
->early_clobber
= early_clobber
;
560 ir
->early_clobber_alts
= early_clobber_alts
;
561 ir
->clobber_high
= clobber_high
;
567 /* Free insn reg info list IR. */
569 free_insn_regs (struct lra_insn_reg
*ir
)
571 struct lra_insn_reg
*next_ir
;
573 for (; ir
!= NULL
; ir
= next_ir
)
576 lra_insn_reg_pool
.remove (ir
);
580 /* Finish pool for insn reg info. */
582 finish_insn_regs (void)
584 lra_insn_reg_pool
.release ();
589 /* This page contains code dealing LRA insn info (or in other words
590 LRA internal insn representation). */
592 /* Map INSN_CODE -> the static insn data. This info is valid during
593 all translation unit. */
594 struct lra_static_insn_data
*insn_code_data
[NUM_INSN_CODES
];
596 /* Debug insns are represented as a special insn with one input
597 operand which is RTL expression in var_location. */
599 /* The following data are used as static insn operand data for all
600 debug insns. If structure lra_operand_data is changed, the
601 initializer should be changed too. */
602 static struct lra_operand_data debug_operand_data
=
604 NULL
, /* alternative */
605 0, /* early_clobber_alts */
606 E_VOIDmode
, /* We are not interesting in the operand mode. */
611 /* The following data are used as static insn data for all debug
612 bind insns. If structure lra_static_insn_data is changed, the
613 initializer should be changed too. */
614 static struct lra_static_insn_data debug_bind_static_data
=
617 0, /* Duplication operands #. */
618 -1, /* Commutative operand #. */
619 1, /* Operands #. There is only one operand which is debug RTL
621 0, /* Duplications #. */
622 0, /* Alternatives #. We are not interesting in alternatives
623 because we does not proceed debug_insns for reloads. */
624 NULL
, /* Hard registers referenced in machine description. */
625 NULL
/* Descriptions of operands in alternatives. */
628 /* The following data are used as static insn data for all debug
629 marker insns. If structure lra_static_insn_data is changed, the
630 initializer should be changed too. */
631 static struct lra_static_insn_data debug_marker_static_data
=
634 0, /* Duplication operands #. */
635 -1, /* Commutative operand #. */
636 0, /* Operands #. There isn't any operand. */
637 0, /* Duplications #. */
638 0, /* Alternatives #. We are not interesting in alternatives
639 because we does not proceed debug_insns for reloads. */
640 NULL
, /* Hard registers referenced in machine description. */
641 NULL
/* Descriptions of operands in alternatives. */
644 /* Called once per compiler work to initialize some LRA data related
647 init_insn_code_data_once (void)
649 memset (insn_code_data
, 0, sizeof (insn_code_data
));
652 /* Called once per compiler work to finalize some LRA data related to
655 finish_insn_code_data_once (void)
657 for (unsigned int i
= 0; i
< NUM_INSN_CODES
; i
++)
659 if (insn_code_data
[i
] != NULL
)
660 free (insn_code_data
[i
]);
664 /* Return static insn data, allocate and setup if necessary. Although
665 dup_num is static data (it depends only on icode), to set it up we
666 need to extract insn first. So recog_data should be valid for
667 normal insn (ICODE >= 0) before the call. */
668 static struct lra_static_insn_data
*
669 get_static_insn_data (int icode
, int nop
, int ndup
, int nalt
)
671 struct lra_static_insn_data
*data
;
674 lra_assert (icode
< (int) NUM_INSN_CODES
);
675 if (icode
>= 0 && (data
= insn_code_data
[icode
]) != NULL
)
677 lra_assert (nop
>= 0 && ndup
>= 0 && nalt
>= 0);
678 n_bytes
= sizeof (struct lra_static_insn_data
)
679 + sizeof (struct lra_operand_data
) * nop
680 + sizeof (int) * ndup
;
681 data
= XNEWVAR (struct lra_static_insn_data
, n_bytes
);
682 data
->operand_alternative
= NULL
;
683 data
->n_operands
= nop
;
685 data
->n_alternatives
= nalt
;
686 data
->operand
= ((struct lra_operand_data
*)
687 ((char *) data
+ sizeof (struct lra_static_insn_data
)));
688 data
->dup_num
= ((int *) ((char *) data
->operand
689 + sizeof (struct lra_operand_data
) * nop
));
694 insn_code_data
[icode
] = data
;
695 for (i
= 0; i
< nop
; i
++)
697 data
->operand
[i
].constraint
698 = insn_data
[icode
].operand
[i
].constraint
;
699 data
->operand
[i
].mode
= insn_data
[icode
].operand
[i
].mode
;
700 data
->operand
[i
].strict_low
= insn_data
[icode
].operand
[i
].strict_low
;
701 data
->operand
[i
].is_operator
702 = insn_data
[icode
].operand
[i
].is_operator
;
703 data
->operand
[i
].type
704 = (data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
705 : data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
707 data
->operand
[i
].is_address
= false;
709 for (i
= 0; i
< ndup
; i
++)
710 data
->dup_num
[i
] = recog_data
.dup_num
[i
];
715 /* The current length of the following array. */
716 int lra_insn_recog_data_len
;
718 /* Map INSN_UID -> the insn recog data (NULL if unknown). */
719 lra_insn_recog_data_t
*lra_insn_recog_data
;
721 /* Initialize LRA data about insns. */
723 init_insn_recog_data (void)
725 lra_insn_recog_data_len
= 0;
726 lra_insn_recog_data
= NULL
;
729 /* Expand, if necessary, LRA data about insns. */
731 check_and_expand_insn_recog_data (int index
)
735 if (lra_insn_recog_data_len
> index
)
737 old
= lra_insn_recog_data_len
;
738 lra_insn_recog_data_len
= index
* 3 / 2 + 1;
739 lra_insn_recog_data
= XRESIZEVEC (lra_insn_recog_data_t
,
741 lra_insn_recog_data_len
);
742 for (i
= old
; i
< lra_insn_recog_data_len
; i
++)
743 lra_insn_recog_data
[i
] = NULL
;
746 /* Finish LRA DATA about insn. */
748 free_insn_recog_data (lra_insn_recog_data_t data
)
750 if (data
->operand_loc
!= NULL
)
751 free (data
->operand_loc
);
752 if (data
->dup_loc
!= NULL
)
753 free (data
->dup_loc
);
754 if (data
->arg_hard_regs
!= NULL
)
755 free (data
->arg_hard_regs
);
756 if (data
->icode
< 0 && NONDEBUG_INSN_P (data
->insn
))
758 if (data
->insn_static_data
->operand_alternative
!= NULL
)
759 free (const_cast <operand_alternative
*>
760 (data
->insn_static_data
->operand_alternative
));
761 free_insn_regs (data
->insn_static_data
->hard_regs
);
762 free (data
->insn_static_data
);
764 free_insn_regs (data
->regs
);
769 /* Pools for copies. */
770 static object_allocator
<lra_copy
> lra_copy_pool ("lra copies");
772 /* Finish LRA data about all insns. */
774 finish_insn_recog_data (void)
777 lra_insn_recog_data_t data
;
779 for (i
= 0; i
< lra_insn_recog_data_len
; i
++)
780 if ((data
= lra_insn_recog_data
[i
]) != NULL
)
781 free_insn_recog_data (data
);
783 lra_copy_pool
.release ();
784 lra_insn_reg_pool
.release ();
785 free (lra_insn_recog_data
);
788 /* Setup info about operands in alternatives of LRA DATA of insn. */
790 setup_operand_alternative (lra_insn_recog_data_t data
,
791 const operand_alternative
*op_alt
)
794 int icode
= data
->icode
;
795 struct lra_static_insn_data
*static_data
= data
->insn_static_data
;
797 static_data
->commutative
= -1;
798 nop
= static_data
->n_operands
;
799 nalt
= static_data
->n_alternatives
;
800 static_data
->operand_alternative
= op_alt
;
801 for (i
= 0; i
< nop
; i
++)
803 static_data
->operand
[i
].early_clobber_alts
= 0;
804 static_data
->operand
[i
].early_clobber
= false;
805 static_data
->operand
[i
].is_address
= false;
806 if (static_data
->operand
[i
].constraint
[0] == '%')
808 /* We currently only support one commutative pair of operands. */
809 if (static_data
->commutative
< 0)
810 static_data
->commutative
= i
;
812 lra_assert (icode
< 0); /* Asm */
813 /* The last operand should not be marked commutative. */
814 lra_assert (i
!= nop
- 1);
817 for (j
= 0; j
< nalt
; j
++)
818 for (i
= 0; i
< nop
; i
++, op_alt
++)
820 static_data
->operand
[i
].early_clobber
|= op_alt
->earlyclobber
;
821 if (op_alt
->earlyclobber
)
822 static_data
->operand
[i
].early_clobber_alts
|= (alternative_mask
) 1 << j
;
823 static_data
->operand
[i
].is_address
|= op_alt
->is_address
;
827 /* Recursively process X and collect info about registers, which are
828 not the insn operands, in X with TYPE (in/out/inout) and flag that
829 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
830 to LIST. X is a part of insn given by DATA. Return the result
831 list. CLOBBER_HIGH marks if X is a clobber high. */
832 static struct lra_insn_reg
*
833 collect_non_operand_hard_regs (rtx_insn
*insn
, rtx
*x
,
834 lra_insn_recog_data_t data
,
835 struct lra_insn_reg
*list
,
836 enum op_type type
, bool early_clobber
,
839 int i
, j
, regno
, last
;
842 struct lra_insn_reg
*curr
;
844 enum rtx_code code
= GET_CODE (op
);
845 const char *fmt
= GET_RTX_FORMAT (code
);
847 for (i
= 0; i
< data
->insn_static_data
->n_operands
; i
++)
848 if (! data
->insn_static_data
->operand
[i
].is_operator
849 && x
== data
->operand_loc
[i
])
850 /* It is an operand loc. Stop here. */
852 for (i
= 0; i
< data
->insn_static_data
->n_dups
; i
++)
853 if (x
== data
->dup_loc
[i
])
854 /* It is a dup loc. Stop here. */
856 mode
= GET_MODE (op
);
860 mode
= wider_subreg_mode (op
);
861 if (read_modify_subreg_p (op
))
863 op
= SUBREG_REG (op
);
864 code
= GET_CODE (op
);
868 if ((regno
= REGNO (op
)) >= FIRST_PSEUDO_REGISTER
)
870 /* Process all regs even unallocatable ones as we need info
871 about all regs for rematerialization pass. */
872 for (last
= end_hard_regno (mode
, regno
); regno
< last
; regno
++)
874 for (curr
= list
; curr
!= NULL
; curr
= curr
->next
)
875 if (curr
->regno
== regno
&& curr
->subreg_p
== subreg_p
876 && curr
->biggest_mode
== mode
)
878 if (curr
->type
!= type
)
879 curr
->type
= OP_INOUT
;
882 curr
->early_clobber
= true;
883 curr
->early_clobber_alts
= ALL_ALTERNATIVES
;
889 /* This is a new hard regno or the info cannot be
890 integrated into the found structure. */
894 /* This clobber is to inform popping floating
896 && ! (FIRST_STACK_REG
<= regno
897 && regno
<= LAST_STACK_REG
));
899 list
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
901 early_clobber
? ALL_ALTERNATIVES
: 0, list
,
910 list
= collect_non_operand_hard_regs (insn
, &SET_DEST (op
), data
,
911 list
, OP_OUT
, false, false);
912 list
= collect_non_operand_hard_regs (insn
, &SET_SRC (op
), data
,
913 list
, OP_IN
, false, false);
916 /* We treat clobber of non-operand hard registers as early clobber. */
917 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
918 list
, OP_OUT
, true, false);
921 /* Clobber high should always span exactly one register. */
922 gcc_assert (REG_NREGS (XEXP (op
, 0)) == 1);
923 /* We treat clobber of non-operand hard registers as early clobber. */
924 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
925 list
, OP_OUT
, true, true);
927 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
928 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
929 list
, OP_INOUT
, false, false);
931 case PRE_MODIFY
: case POST_MODIFY
:
932 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 0), data
,
933 list
, OP_INOUT
, false, false);
934 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, 1), data
,
935 list
, OP_IN
, false, false);
938 fmt
= GET_RTX_FORMAT (code
);
939 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
942 list
= collect_non_operand_hard_regs (insn
, &XEXP (op
, i
), data
,
943 list
, OP_IN
, false, false);
944 else if (fmt
[i
] == 'E')
945 for (j
= XVECLEN (op
, i
) - 1; j
>= 0; j
--)
946 list
= collect_non_operand_hard_regs (insn
, &XVECEXP (op
, i
, j
),
947 data
, list
, OP_IN
, false,
954 /* Set up and return info about INSN. Set up the info if it is not set up
956 lra_insn_recog_data_t
957 lra_set_insn_recog_data (rtx_insn
*insn
)
959 lra_insn_recog_data_t data
;
962 unsigned int uid
= INSN_UID (insn
);
963 struct lra_static_insn_data
*insn_static_data
;
965 check_and_expand_insn_recog_data (uid
);
966 if (DEBUG_INSN_P (insn
))
970 icode
= INSN_CODE (insn
);
972 /* It might be a new simple insn which is not recognized yet. */
973 INSN_CODE (insn
) = icode
= recog_memoized (insn
);
975 data
= XNEW (struct lra_insn_recog_data
);
976 lra_insn_recog_data
[uid
] = data
;
978 data
->used_insn_alternative
= LRA_UNKNOWN_ALT
;
981 if (DEBUG_INSN_P (insn
))
983 data
->dup_loc
= NULL
;
984 data
->arg_hard_regs
= NULL
;
985 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
986 if (DEBUG_BIND_INSN_P (insn
))
988 data
->insn_static_data
= &debug_bind_static_data
;
989 data
->operand_loc
= XNEWVEC (rtx
*, 1);
990 data
->operand_loc
[0] = &INSN_VAR_LOCATION_LOC (insn
);
992 else if (DEBUG_MARKER_INSN_P (insn
))
994 data
->insn_static_data
= &debug_marker_static_data
;
995 data
->operand_loc
= NULL
;
1002 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
1003 const char *constraints
[MAX_RECOG_OPERANDS
];
1005 nop
= asm_noperands (PATTERN (insn
));
1006 data
->operand_loc
= data
->dup_loc
= NULL
;
1010 /* It is a special insn like USE or CLOBBER. We should
1011 recognize any regular insn otherwise LRA can do nothing
1013 gcc_assert (GET_CODE (PATTERN (insn
)) == USE
1014 || GET_CODE (PATTERN (insn
)) == CLOBBER
1015 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
1016 data
->insn_static_data
= insn_static_data
1017 = get_static_insn_data (-1, 0, 0, nalt
);
1021 /* expand_asm_operands makes sure there aren't too many
1023 lra_assert (nop
<= MAX_RECOG_OPERANDS
);
1025 data
->operand_loc
= XNEWVEC (rtx
*, nop
);
1026 /* Now get the operand values and constraints out of the
1028 decode_asm_operands (PATTERN (insn
), NULL
,
1030 constraints
, operand_mode
, NULL
);
1033 const char *p
= recog_data
.constraints
[0];
1035 for (p
= constraints
[0]; *p
; p
++)
1038 data
->insn_static_data
= insn_static_data
1039 = get_static_insn_data (-1, nop
, 0, nalt
);
1040 for (i
= 0; i
< nop
; i
++)
1042 insn_static_data
->operand
[i
].mode
= operand_mode
[i
];
1043 insn_static_data
->operand
[i
].constraint
= constraints
[i
];
1044 insn_static_data
->operand
[i
].strict_low
= false;
1045 insn_static_data
->operand
[i
].is_operator
= false;
1046 insn_static_data
->operand
[i
].is_address
= false;
1049 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1050 insn_static_data
->operand
[i
].type
1051 = (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1052 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1054 data
->preferred_alternatives
= ALL_ALTERNATIVES
;
1057 operand_alternative
*op_alt
= XCNEWVEC (operand_alternative
,
1059 preprocess_constraints (nop
, nalt
, constraints
, op_alt
,
1061 setup_operand_alternative (data
, op_alt
);
1066 insn_extract (insn
);
1067 data
->insn_static_data
= insn_static_data
1068 = get_static_insn_data (icode
, insn_data
[icode
].n_operands
,
1069 insn_data
[icode
].n_dups
,
1070 insn_data
[icode
].n_alternatives
);
1071 n
= insn_static_data
->n_operands
;
1076 locs
= XNEWVEC (rtx
*, n
);
1077 memcpy (locs
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1079 data
->operand_loc
= locs
;
1080 n
= insn_static_data
->n_dups
;
1085 locs
= XNEWVEC (rtx
*, n
);
1086 memcpy (locs
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1088 data
->dup_loc
= locs
;
1089 data
->preferred_alternatives
= get_preferred_alternatives (insn
);
1090 const operand_alternative
*op_alt
= preprocess_insn_constraints (icode
);
1091 if (!insn_static_data
->operand_alternative
)
1092 setup_operand_alternative (data
, op_alt
);
1093 else if (op_alt
!= insn_static_data
->operand_alternative
)
1094 insn_static_data
->operand_alternative
= op_alt
;
1096 if (GET_CODE (PATTERN (insn
)) == CLOBBER
|| GET_CODE (PATTERN (insn
)) == USE
)
1097 insn_static_data
->hard_regs
= NULL
;
1099 insn_static_data
->hard_regs
1100 = collect_non_operand_hard_regs (insn
, &PATTERN (insn
), data
,
1101 NULL
, OP_IN
, false, false);
1102 data
->arg_hard_regs
= NULL
;
1107 int n_hard_regs
, regno
, arg_hard_regs
[FIRST_PSEUDO_REGISTER
];
1110 /* Finding implicit hard register usage. We believe it will be
1111 not changed whatever transformations are used. Call insns
1112 are such example. */
1113 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1115 link
= XEXP (link
, 1))
1116 if (((use_p
= GET_CODE (XEXP (link
, 0)) == USE
)
1117 || GET_CODE (XEXP (link
, 0)) == CLOBBER
)
1118 && REG_P (XEXP (XEXP (link
, 0), 0)))
1120 regno
= REGNO (XEXP (XEXP (link
, 0), 0));
1121 lra_assert (regno
< FIRST_PSEUDO_REGISTER
);
1122 /* It is an argument register. */
1123 for (i
= REG_NREGS (XEXP (XEXP (link
, 0), 0)) - 1; i
>= 0; i
--)
1124 arg_hard_regs
[n_hard_regs
++]
1125 = regno
+ i
+ (use_p
? 0 : FIRST_PSEUDO_REGISTER
);
1127 else if (GET_CODE (XEXP (link
, 0)) == CLOBBER_HIGH
)
1128 /* We could support CLOBBER_HIGH and treat it in the same way as
1129 HARD_REGNO_CALL_PART_CLOBBERED, but no port needs that yet. */
1132 if (n_hard_regs
!= 0)
1134 arg_hard_regs
[n_hard_regs
++] = -1;
1135 data
->arg_hard_regs
= XNEWVEC (int, n_hard_regs
);
1136 memcpy (data
->arg_hard_regs
, arg_hard_regs
,
1137 sizeof (int) * n_hard_regs
);
1140 /* Some output operand can be recognized only from the context not
1141 from the constraints which are empty in this case. Call insn may
1142 contain a hard register in set destination with empty constraint
1143 and extract_insn treats them as an input. */
1144 for (i
= 0; i
< insn_static_data
->n_operands
; i
++)
1148 struct lra_operand_data
*operand
= &insn_static_data
->operand
[i
];
1150 /* ??? Should we treat 'X' the same way. It looks to me that
1151 'X' means anything and empty constraint means we do not
1153 if (operand
->type
!= OP_IN
|| *operand
->constraint
!= '\0'
1154 || operand
->is_operator
)
1156 pat
= PATTERN (insn
);
1157 if (GET_CODE (pat
) == SET
)
1159 if (data
->operand_loc
[i
] != &SET_DEST (pat
))
1162 else if (GET_CODE (pat
) == PARALLEL
)
1164 for (j
= XVECLEN (pat
, 0) - 1; j
>= 0; j
--)
1166 set
= XVECEXP (PATTERN (insn
), 0, j
);
1167 if (GET_CODE (set
) == SET
1168 && &SET_DEST (set
) == data
->operand_loc
[i
])
1176 operand
->type
= OP_OUT
;
1181 /* Return info about insn give by UID. The info should be already set
1183 static lra_insn_recog_data_t
1184 get_insn_recog_data_by_uid (int uid
)
1186 lra_insn_recog_data_t data
;
1188 data
= lra_insn_recog_data
[uid
];
1189 lra_assert (data
!= NULL
);
1193 /* Invalidate all info about insn given by its UID. */
1195 invalidate_insn_recog_data (int uid
)
1197 lra_insn_recog_data_t data
;
1199 data
= lra_insn_recog_data
[uid
];
1200 lra_assert (data
!= NULL
);
1201 free_insn_recog_data (data
);
1202 lra_insn_recog_data
[uid
] = NULL
;
1205 /* Update all the insn info about INSN. It is usually called when
1206 something in the insn was changed. Return the updated info. */
1207 lra_insn_recog_data_t
1208 lra_update_insn_recog_data (rtx_insn
*insn
)
1210 lra_insn_recog_data_t data
;
1212 unsigned int uid
= INSN_UID (insn
);
1213 struct lra_static_insn_data
*insn_static_data
;
1214 poly_int64 sp_offset
= 0;
1216 check_and_expand_insn_recog_data (uid
);
1217 if ((data
= lra_insn_recog_data
[uid
]) != NULL
1218 && data
->icode
!= INSN_CODE (insn
))
1220 sp_offset
= data
->sp_offset
;
1221 invalidate_insn_data_regno_info (data
, insn
, get_insn_freq (insn
));
1222 invalidate_insn_recog_data (uid
);
1227 data
= lra_get_insn_recog_data (insn
);
1228 /* Initiate or restore SP offset. */
1229 data
->sp_offset
= sp_offset
;
1232 insn_static_data
= data
->insn_static_data
;
1233 data
->used_insn_alternative
= LRA_UNKNOWN_ALT
;
1234 if (DEBUG_INSN_P (insn
))
1236 if (data
->icode
< 0)
1239 machine_mode operand_mode
[MAX_RECOG_OPERANDS
];
1240 const char *constraints
[MAX_RECOG_OPERANDS
];
1242 nop
= asm_noperands (PATTERN (insn
));
1245 lra_assert (nop
== data
->insn_static_data
->n_operands
);
1246 /* Now get the operand values and constraints out of the
1248 decode_asm_operands (PATTERN (insn
), NULL
,
1250 constraints
, operand_mode
, NULL
);
1253 for (int i
= 0; i
< nop
; i
++)
1255 (insn_static_data
->operand
[i
].mode
== operand_mode
[i
]
1256 && insn_static_data
->operand
[i
].constraint
== constraints
[i
]
1257 && ! insn_static_data
->operand
[i
].is_operator
);
1261 for (int i
= 0; i
< insn_static_data
->n_operands
; i
++)
1263 (insn_static_data
->operand
[i
].type
1264 == (insn_static_data
->operand
[i
].constraint
[0] == '=' ? OP_OUT
1265 : insn_static_data
->operand
[i
].constraint
[0] == '+' ? OP_INOUT
1270 insn_extract (insn
);
1271 n
= insn_static_data
->n_operands
;
1273 memcpy (data
->operand_loc
, recog_data
.operand_loc
, n
* sizeof (rtx
*));
1274 n
= insn_static_data
->n_dups
;
1276 memcpy (data
->dup_loc
, recog_data
.dup_loc
, n
* sizeof (rtx
*));
1277 lra_assert (check_bool_attrs (insn
));
1282 /* Set up that INSN is using alternative ALT now. */
1284 lra_set_used_insn_alternative (rtx_insn
*insn
, int alt
)
1286 lra_insn_recog_data_t data
;
1288 data
= lra_get_insn_recog_data (insn
);
1289 data
->used_insn_alternative
= alt
;
1292 /* Set up that insn with UID is using alternative ALT now. The insn
1293 info should be already set up. */
1295 lra_set_used_insn_alternative_by_uid (int uid
, int alt
)
1297 lra_insn_recog_data_t data
;
1299 check_and_expand_insn_recog_data (uid
);
1300 data
= lra_insn_recog_data
[uid
];
1301 lra_assert (data
!= NULL
);
1302 data
->used_insn_alternative
= alt
;
1307 /* This page contains code dealing with common register info and
1310 /* The size of the following array. */
1311 static int reg_info_size
;
1312 /* Common info about each register. */
1313 struct lra_reg
*lra_reg_info
;
1315 HARD_REG_SET hard_regs_spilled_into
;
1317 /* Last register value. */
1318 static int last_reg_value
;
1320 /* Return new register value. */
1322 get_new_reg_value (void)
1324 return ++last_reg_value
;
1327 /* Vec referring to pseudo copies. */
1328 static vec
<lra_copy_t
> copy_vec
;
1330 /* Initialize I-th element of lra_reg_info. */
1332 initialize_lra_reg_info_element (int i
)
1334 bitmap_initialize (&lra_reg_info
[i
].insn_bitmap
, ®_obstack
);
1336 lra_reg_info
[i
].no_stack_p
= false;
1338 CLEAR_HARD_REG_SET (lra_reg_info
[i
].conflict_hard_regs
);
1339 CLEAR_HARD_REG_SET (lra_reg_info
[i
].actual_call_used_reg_set
);
1340 lra_reg_info
[i
].preferred_hard_regno1
= -1;
1341 lra_reg_info
[i
].preferred_hard_regno2
= -1;
1342 lra_reg_info
[i
].preferred_hard_regno_profit1
= 0;
1343 lra_reg_info
[i
].preferred_hard_regno_profit2
= 0;
1344 lra_reg_info
[i
].biggest_mode
= VOIDmode
;
1345 lra_reg_info
[i
].live_ranges
= NULL
;
1346 lra_reg_info
[i
].nrefs
= lra_reg_info
[i
].freq
= 0;
1347 lra_reg_info
[i
].last_reload
= 0;
1348 lra_reg_info
[i
].restore_rtx
= NULL_RTX
;
1349 lra_reg_info
[i
].val
= get_new_reg_value ();
1350 lra_reg_info
[i
].offset
= 0;
1351 lra_reg_info
[i
].copies
= NULL
;
1352 lra_reg_info
[i
].call_insn
= NULL
;
1355 /* Initialize common reg info and copies. */
1357 init_reg_info (void)
1362 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1363 lra_reg_info
= XNEWVEC (struct lra_reg
, reg_info_size
);
1364 for (i
= 0; i
< reg_info_size
; i
++)
1365 initialize_lra_reg_info_element (i
);
1366 copy_vec
.truncate (0);
1367 CLEAR_HARD_REG_SET (hard_regs_spilled_into
);
1371 /* Finish common reg info and copies. */
1373 finish_reg_info (void)
1377 for (i
= 0; i
< reg_info_size
; i
++)
1378 bitmap_clear (&lra_reg_info
[i
].insn_bitmap
);
1379 free (lra_reg_info
);
1383 /* Expand common reg info if it is necessary. */
1385 expand_reg_info (void)
1387 int i
, old
= reg_info_size
;
1389 if (reg_info_size
> max_reg_num ())
1391 reg_info_size
= max_reg_num () * 3 / 2 + 1;
1392 lra_reg_info
= XRESIZEVEC (struct lra_reg
, lra_reg_info
, reg_info_size
);
1393 for (i
= old
; i
< reg_info_size
; i
++)
1394 initialize_lra_reg_info_element (i
);
1397 /* Free all copies. */
1399 lra_free_copies (void)
1403 while (copy_vec
.length () != 0)
1405 cp
= copy_vec
.pop ();
1406 lra_reg_info
[cp
->regno1
].copies
= lra_reg_info
[cp
->regno2
].copies
= NULL
;
1407 lra_copy_pool
.remove (cp
);
1411 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1412 frequency is FREQ. */
1414 lra_create_copy (int regno1
, int regno2
, int freq
)
1419 lra_assert (regno1
!= regno2
);
1420 regno1_dest_p
= true;
1421 if (regno1
> regno2
)
1423 std::swap (regno1
, regno2
);
1424 regno1_dest_p
= false;
1426 cp
= lra_copy_pool
.allocate ();
1427 copy_vec
.safe_push (cp
);
1428 cp
->regno1_dest_p
= regno1_dest_p
;
1430 cp
->regno1
= regno1
;
1431 cp
->regno2
= regno2
;
1432 cp
->regno1_next
= lra_reg_info
[regno1
].copies
;
1433 lra_reg_info
[regno1
].copies
= cp
;
1434 cp
->regno2_next
= lra_reg_info
[regno2
].copies
;
1435 lra_reg_info
[regno2
].copies
= cp
;
1436 if (lra_dump_file
!= NULL
)
1437 fprintf (lra_dump_file
, " Creating copy r%d%sr%d@%d\n",
1438 regno1
, regno1_dest_p
? "<-" : "->", regno2
, freq
);
1441 /* Return N-th (0, 1, ...) copy. If there is no copy, return
1444 lra_get_copy (int n
)
1446 if (n
>= (int) copy_vec
.length ())
1453 /* This page contains code dealing with info about registers in
1456 /* Process X of INSN recursively and add info (operand type is
1457 given by TYPE, flag of that it is early clobber is EARLY_CLOBBER)
1458 about registers in X to the insn DATA. If X can be early clobbered,
1459 alternatives in which it can be early clobbered are given by
1460 EARLY_CLOBBER_ALTS. */
1462 add_regs_to_insn_regno_info (lra_insn_recog_data_t data
, rtx x
,
1464 enum op_type type
, bool early_clobber
,
1465 alternative_mask early_clobber_alts
)
1472 struct lra_insn_reg
*curr
;
1474 code
= GET_CODE (x
);
1475 mode
= GET_MODE (x
);
1477 if (GET_CODE (x
) == SUBREG
)
1479 mode
= wider_subreg_mode (x
);
1480 if (read_modify_subreg_p (x
))
1483 code
= GET_CODE (x
);
1488 /* Process all regs even unallocatable ones as we need info about
1489 all regs for rematerialization pass. */
1491 if (bitmap_set_bit (&lra_reg_info
[regno
].insn_bitmap
, INSN_UID (insn
)))
1493 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
, subreg_p
,
1494 early_clobber
, early_clobber_alts
,
1500 for (curr
= data
->regs
; curr
!= NULL
; curr
= curr
->next
)
1501 if (curr
->regno
== regno
)
1503 if (curr
->subreg_p
!= subreg_p
|| curr
->biggest_mode
!= mode
)
1504 /* The info cannot be integrated into the found
1506 data
->regs
= new_insn_reg (data
->insn
, regno
, type
, mode
,
1507 subreg_p
, early_clobber
,
1508 early_clobber_alts
, data
->regs
,
1512 if (curr
->type
!= type
)
1513 curr
->type
= OP_INOUT
;
1514 if (curr
->early_clobber
!= early_clobber
)
1515 curr
->early_clobber
= true;
1516 curr
->early_clobber_alts
|= early_clobber_alts
;
1527 add_regs_to_insn_regno_info (data
, SET_DEST (x
), insn
, OP_OUT
, false, 0);
1528 add_regs_to_insn_regno_info (data
, SET_SRC (x
), insn
, OP_IN
, false, 0);
1531 /* We treat clobber of non-operand hard registers as early
1533 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), insn
, OP_OUT
,
1534 true, ALL_ALTERNATIVES
);
1538 case PRE_INC
: case PRE_DEC
: case POST_INC
: case POST_DEC
:
1539 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), insn
, OP_INOUT
, false, 0);
1541 case PRE_MODIFY
: case POST_MODIFY
:
1542 add_regs_to_insn_regno_info (data
, XEXP (x
, 0), insn
, OP_INOUT
, false, 0);
1543 add_regs_to_insn_regno_info (data
, XEXP (x
, 1), insn
, OP_IN
, false, 0);
1546 if ((code
!= PARALLEL
&& code
!= EXPR_LIST
) || type
!= OP_OUT
)
1547 /* Some targets place small structures in registers for return
1548 values of functions, and those registers are wrapped in
1549 PARALLEL that we may see as the destination of a SET. Here
1552 (call_insn 13 12 14 2 (set (parallel:BLK [
1553 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1555 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1556 (const_int 8 [0x8]))
1558 (call (mem:QI (symbol_ref:DI (... */
1560 fmt
= GET_RTX_FORMAT (code
);
1561 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1564 add_regs_to_insn_regno_info (data
, XEXP (x
, i
), insn
, type
, false, 0);
1565 else if (fmt
[i
] == 'E')
1567 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1568 add_regs_to_insn_regno_info (data
, XVECEXP (x
, i
, j
), insn
,
1575 /* Return execution frequency of INSN. */
1577 get_insn_freq (rtx_insn
*insn
)
1579 basic_block bb
= BLOCK_FOR_INSN (insn
);
1581 gcc_checking_assert (bb
!= NULL
);
1582 return REG_FREQ_FROM_BB (bb
);
1585 /* Invalidate all reg info of INSN with DATA and execution frequency
1586 FREQ. Update common info about the invalidated registers. */
1588 invalidate_insn_data_regno_info (lra_insn_recog_data_t data
, rtx_insn
*insn
,
1594 struct lra_insn_reg
*ir
, *next_ir
;
1596 uid
= INSN_UID (insn
);
1597 debug_p
= DEBUG_INSN_P (insn
);
1598 for (ir
= data
->regs
; ir
!= NULL
; ir
= next_ir
)
1602 lra_insn_reg_pool
.remove (ir
);
1603 bitmap_clear_bit (&lra_reg_info
[i
].insn_bitmap
, uid
);
1604 if (i
>= FIRST_PSEUDO_REGISTER
&& ! debug_p
)
1606 lra_reg_info
[i
].nrefs
--;
1607 lra_reg_info
[i
].freq
-= freq
;
1608 lra_assert (lra_reg_info
[i
].nrefs
>= 0 && lra_reg_info
[i
].freq
>= 0);
1614 /* Invalidate all reg info of INSN. Update common info about the
1615 invalidated registers. */
1617 lra_invalidate_insn_regno_info (rtx_insn
*insn
)
1619 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn
), insn
,
1620 get_insn_freq (insn
));
1623 /* Update common reg info from reg info of insn given by its DATA and
1624 execution frequency FREQ. */
1626 setup_insn_reg_info (lra_insn_recog_data_t data
, int freq
)
1629 struct lra_insn_reg
*ir
;
1631 for (ir
= data
->regs
; ir
!= NULL
; ir
= ir
->next
)
1632 if ((i
= ir
->regno
) >= FIRST_PSEUDO_REGISTER
)
1634 lra_reg_info
[i
].nrefs
++;
1635 lra_reg_info
[i
].freq
+= freq
;
1639 /* Set up insn reg info of INSN. Update common reg info from reg info
1642 lra_update_insn_regno_info (rtx_insn
*insn
)
1645 lra_insn_recog_data_t data
;
1646 struct lra_static_insn_data
*static_data
;
1650 if (! INSN_P (insn
))
1652 data
= lra_get_insn_recog_data (insn
);
1653 static_data
= data
->insn_static_data
;
1654 freq
= NONDEBUG_INSN_P (insn
) ? get_insn_freq (insn
) : 0;
1655 invalidate_insn_data_regno_info (data
, insn
, freq
);
1656 for (i
= static_data
->n_operands
- 1; i
>= 0; i
--)
1657 add_regs_to_insn_regno_info (data
, *data
->operand_loc
[i
], insn
,
1658 static_data
->operand
[i
].type
,
1659 static_data
->operand
[i
].early_clobber
,
1660 static_data
->operand
[i
].early_clobber_alts
);
1661 if ((code
= GET_CODE (PATTERN (insn
))) == CLOBBER
|| code
== USE
)
1662 add_regs_to_insn_regno_info (data
, XEXP (PATTERN (insn
), 0), insn
,
1663 code
== USE
? OP_IN
: OP_OUT
, false, 0);
1665 /* On some targets call insns can refer to pseudos in memory in
1666 CALL_INSN_FUNCTION_USAGE list. Process them in order to
1667 consider their occurrences in calls for different
1668 transformations (e.g. inheritance) with given pseudos. */
1669 for (link
= CALL_INSN_FUNCTION_USAGE (insn
);
1671 link
= XEXP (link
, 1))
1673 code
= GET_CODE (XEXP (link
, 0));
1674 /* We could support CLOBBER_HIGH and treat it in the same way as
1675 HARD_REGNO_CALL_PART_CLOBBERED, but no port needs that yet. */
1676 gcc_assert (code
!= CLOBBER_HIGH
);
1677 if ((code
== USE
|| code
== CLOBBER
)
1678 && MEM_P (XEXP (XEXP (link
, 0), 0)))
1679 add_regs_to_insn_regno_info (data
, XEXP (XEXP (link
, 0), 0), insn
,
1680 code
== USE
? OP_IN
: OP_OUT
, false, 0);
1682 if (NONDEBUG_INSN_P (insn
))
1683 setup_insn_reg_info (data
, freq
);
1686 /* Return reg info of insn given by it UID. */
1687 struct lra_insn_reg
*
1688 lra_get_insn_regs (int uid
)
1690 lra_insn_recog_data_t data
;
1692 data
= get_insn_recog_data_by_uid (uid
);
1698 /* Recursive hash function for RTL X. */
1700 lra_rtx_hash (rtx x
)
1710 code
= GET_CODE (x
);
1711 val
+= (int) code
+ 4095;
1713 /* Some RTL can be compared nonrecursively. */
1717 return val
+ REGNO (x
);
1720 return iterative_hash_object (XEXP (x
, 0), val
);
1723 return iterative_hash_object (XSTR (x
, 0), val
);
1731 return val
+ UINTVAL (x
);
1737 /* Hash the elements. */
1738 fmt
= GET_RTX_FORMAT (code
);
1739 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1744 val
+= XWINT (x
, i
);
1754 val
+= XVECLEN (x
, i
);
1756 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1757 val
+= lra_rtx_hash (XVECEXP (x
, i
, j
));
1761 val
+= lra_rtx_hash (XEXP (x
, i
));
1766 val
+= htab_hash_string (XSTR (x
, i
));
1774 /* It is believed that rtx's at this level will never
1775 contain anything but integers and other rtx's, except for
1776 within LABEL_REFs and SYMBOL_REFs. */
1786 /* This page contains code dealing with stack of the insns which
1787 should be processed by the next constraint pass. */
1789 /* Bitmap used to put an insn on the stack only in one exemplar. */
1790 static sbitmap lra_constraint_insn_stack_bitmap
;
1792 /* The stack itself. */
1793 vec
<rtx_insn
*> lra_constraint_insn_stack
;
1795 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1796 info for INSN, otherwise only update it if INSN is not already on the
1799 lra_push_insn_1 (rtx_insn
*insn
, bool always_update
)
1801 unsigned int uid
= INSN_UID (insn
);
1803 lra_update_insn_regno_info (insn
);
1804 if (uid
>= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap
))
1805 lra_constraint_insn_stack_bitmap
=
1806 sbitmap_resize (lra_constraint_insn_stack_bitmap
, 3 * uid
/ 2, 0);
1807 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap
, uid
))
1809 bitmap_set_bit (lra_constraint_insn_stack_bitmap
, uid
);
1810 if (! always_update
)
1811 lra_update_insn_regno_info (insn
);
1812 lra_constraint_insn_stack
.safe_push (insn
);
1815 /* Put INSN on the stack. */
1817 lra_push_insn (rtx_insn
*insn
)
1819 lra_push_insn_1 (insn
, false);
1822 /* Put INSN on the stack and update its reg info. */
1824 lra_push_insn_and_update_insn_regno_info (rtx_insn
*insn
)
1826 lra_push_insn_1 (insn
, true);
1829 /* Put insn with UID on the stack. */
1831 lra_push_insn_by_uid (unsigned int uid
)
1833 lra_push_insn (lra_insn_recog_data
[uid
]->insn
);
1836 /* Take the last-inserted insns off the stack and return it. */
1840 rtx_insn
*insn
= lra_constraint_insn_stack
.pop ();
1841 bitmap_clear_bit (lra_constraint_insn_stack_bitmap
, INSN_UID (insn
));
1845 /* Return the current size of the insn stack. */
1847 lra_insn_stack_length (void)
1849 return lra_constraint_insn_stack
.length ();
1852 /* Push insns FROM to TO (excluding it) going in reverse order. */
1854 push_insns (rtx_insn
*from
, rtx_insn
*to
)
1858 if (from
== NULL_RTX
)
1860 for (insn
= from
; insn
!= to
; insn
= PREV_INSN (insn
))
1862 lra_push_insn (insn
);
1865 /* Set up sp offset for insn in range [FROM, LAST]. The offset is
1866 taken from the next BB insn after LAST or zero if there in such
1869 setup_sp_offset (rtx_insn
*from
, rtx_insn
*last
)
1871 rtx_insn
*before
= next_nonnote_nondebug_insn_bb (last
);
1872 poly_int64 offset
= (before
== NULL_RTX
|| ! INSN_P (before
)
1873 ? 0 : lra_get_insn_recog_data (before
)->sp_offset
);
1875 for (rtx_insn
*insn
= from
; insn
!= NEXT_INSN (last
); insn
= NEXT_INSN (insn
))
1876 lra_get_insn_recog_data (insn
)->sp_offset
= offset
;
1879 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1880 insns onto the stack. Print about emitting the insns with
1883 lra_process_new_insns (rtx_insn
*insn
, rtx_insn
*before
, rtx_insn
*after
,
1888 if (before
== NULL_RTX
&& after
== NULL_RTX
)
1890 if (lra_dump_file
!= NULL
)
1892 dump_insn_slim (lra_dump_file
, insn
);
1893 if (before
!= NULL_RTX
)
1895 fprintf (lra_dump_file
," %s before:\n", title
);
1896 dump_rtl_slim (lra_dump_file
, before
, NULL
, -1, 0);
1898 if (after
!= NULL_RTX
)
1900 fprintf (lra_dump_file
, " %s after:\n", title
);
1901 dump_rtl_slim (lra_dump_file
, after
, NULL
, -1, 0);
1903 fprintf (lra_dump_file
, "\n");
1905 if (before
!= NULL_RTX
)
1907 if (cfun
->can_throw_non_call_exceptions
)
1908 copy_reg_eh_region_note_forward (insn
, before
, NULL
);
1909 emit_insn_before (before
, insn
);
1910 push_insns (PREV_INSN (insn
), PREV_INSN (before
));
1911 setup_sp_offset (before
, PREV_INSN (insn
));
1913 if (after
!= NULL_RTX
)
1915 if (cfun
->can_throw_non_call_exceptions
)
1916 copy_reg_eh_region_note_forward (insn
, after
, NULL
);
1917 for (last
= after
; NEXT_INSN (last
) != NULL_RTX
; last
= NEXT_INSN (last
))
1919 emit_insn_after (after
, insn
);
1920 push_insns (last
, insn
);
1921 setup_sp_offset (after
, last
);
1923 if (cfun
->can_throw_non_call_exceptions
)
1925 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
1926 if (note
&& !insn_could_throw_p (insn
))
1927 remove_note (insn
, note
);
1932 /* Replace all references to register OLD_REGNO in *LOC with pseudo
1933 register NEW_REG. Try to simplify subreg of constant if SUBREG_P.
1934 DEBUG_P is if LOC is within a DEBUG_INSN. Return true if any
1937 lra_substitute_pseudo (rtx
*loc
, int old_regno
, rtx new_reg
, bool subreg_p
,
1941 bool result
= false;
1949 code
= GET_CODE (x
);
1950 if (code
== SUBREG
&& subreg_p
)
1952 rtx subst
, inner
= SUBREG_REG (x
);
1953 /* Transform subreg of constant while we still have inner mode
1954 of the subreg. The subreg internal should not be an insn
1956 if (REG_P (inner
) && (int) REGNO (inner
) == old_regno
1957 && CONSTANT_P (new_reg
)
1958 && (subst
= simplify_subreg (GET_MODE (x
), new_reg
, GET_MODE (inner
),
1959 SUBREG_BYTE (x
))) != NULL_RTX
)
1966 else if (code
== REG
&& (int) REGNO (x
) == old_regno
)
1968 machine_mode mode
= GET_MODE (x
);
1969 machine_mode inner_mode
= GET_MODE (new_reg
);
1971 if (mode
!= inner_mode
1972 && ! (CONST_SCALAR_INT_P (new_reg
) && SCALAR_INT_MODE_P (mode
)))
1974 poly_uint64 offset
= 0;
1975 if (partial_subreg_p (mode
, inner_mode
)
1976 && SCALAR_INT_MODE_P (inner_mode
))
1977 offset
= subreg_lowpart_offset (mode
, inner_mode
);
1979 new_reg
= gen_rtx_raw_SUBREG (mode
, new_reg
, offset
);
1981 new_reg
= gen_rtx_SUBREG (mode
, new_reg
, offset
);
1987 /* Scan all the operand sub-expressions. */
1988 fmt
= GET_RTX_FORMAT (code
);
1989 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1993 if (lra_substitute_pseudo (&XEXP (x
, i
), old_regno
,
1994 new_reg
, subreg_p
, debug_p
))
1997 else if (fmt
[i
] == 'E')
1999 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2000 if (lra_substitute_pseudo (&XVECEXP (x
, i
, j
), old_regno
,
2001 new_reg
, subreg_p
, debug_p
))
2008 /* Call lra_substitute_pseudo within an insn. Try to simplify subreg
2009 of constant if SUBREG_P. This won't update the insn ptr, just the
2010 contents of the insn. */
2012 lra_substitute_pseudo_within_insn (rtx_insn
*insn
, int old_regno
,
2013 rtx new_reg
, bool subreg_p
)
2016 return lra_substitute_pseudo (&loc
, old_regno
, new_reg
, subreg_p
,
2017 DEBUG_INSN_P (insn
));
2022 /* This page contains code dealing with scratches (changing them onto
2023 pseudos and restoring them from the pseudos).
2025 We change scratches into pseudos at the beginning of LRA to
2026 simplify dealing with them (conflicts, hard register assignments).
2028 If the pseudo denoting scratch was spilled it means that we do need
2029 a hard register for it. Such pseudos are transformed back to
2030 scratches at the end of LRA. */
2032 /* Description of location of a former scratch operand. */
2035 rtx_insn
*insn
; /* Insn where the scratch was. */
2036 int nop
; /* Number of the operand which was a scratch. */
2037 int icode
; /* Original icode from which scratch was removed. */
2040 typedef struct sloc
*sloc_t
;
2042 /* Locations of the former scratches. */
2043 static vec
<sloc_t
> scratches
;
2045 /* Bitmap of scratch regnos. */
2046 static bitmap_head scratch_bitmap
;
2048 /* Bitmap of scratch operands. */
2049 static bitmap_head scratch_operand_bitmap
;
2051 /* Return true if pseudo REGNO is made of SCRATCH. */
2053 lra_former_scratch_p (int regno
)
2055 return bitmap_bit_p (&scratch_bitmap
, regno
);
2058 /* Return true if the operand NOP of INSN is a former scratch. */
2060 lra_former_scratch_operand_p (rtx_insn
*insn
, int nop
)
2062 return bitmap_bit_p (&scratch_operand_bitmap
,
2063 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
) != 0;
2066 /* Register operand NOP in INSN as a former scratch. It will be
2067 changed to scratch back, if it is necessary, at the LRA end. */
2069 lra_register_new_scratch_op (rtx_insn
*insn
, int nop
, int icode
)
2071 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
2072 rtx op
= *id
->operand_loc
[nop
];
2073 sloc_t loc
= XNEW (struct sloc
);
2074 lra_assert (REG_P (op
));
2078 scratches
.safe_push (loc
);
2079 bitmap_set_bit (&scratch_bitmap
, REGNO (op
));
2080 bitmap_set_bit (&scratch_operand_bitmap
,
2081 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
);
2082 add_reg_note (insn
, REG_UNUSED
, op
);
2085 /* Change INSN's scratches into pseudos and save their location. */
2087 remove_scratches_1 (rtx_insn
*insn
)
2090 bool insn_changed_p
;
2092 lra_insn_recog_data_t id
;
2093 struct lra_static_insn_data
*static_id
;
2095 id
= lra_get_insn_recog_data (insn
);
2096 static_id
= id
->insn_static_data
;
2097 insn_changed_p
= false;
2098 for (i
= 0; i
< static_id
->n_operands
; i
++)
2099 if (GET_CODE (*id
->operand_loc
[i
]) == SCRATCH
2100 && GET_MODE (*id
->operand_loc
[i
]) != VOIDmode
)
2102 insn_changed_p
= true;
2103 *id
->operand_loc
[i
] = reg
2104 = lra_create_new_reg (static_id
->operand
[i
].mode
,
2105 *id
->operand_loc
[i
], ALL_REGS
, NULL
);
2106 lra_register_new_scratch_op (insn
, i
, id
->icode
);
2107 if (lra_dump_file
!= NULL
)
2108 fprintf (lra_dump_file
,
2109 "Removing SCRATCH in insn #%u (nop %d)\n",
2110 INSN_UID (insn
), i
);
2113 /* Because we might use DF right after caller-saves sub-pass
2114 we need to keep DF info up to date. */
2115 df_insn_rescan (insn
);
2118 /* Change scratches into pseudos and save their location. */
2120 remove_scratches (void)
2125 scratches
.create (get_max_uid ());
2126 bitmap_initialize (&scratch_bitmap
, ®_obstack
);
2127 bitmap_initialize (&scratch_operand_bitmap
, ®_obstack
);
2128 FOR_EACH_BB_FN (bb
, cfun
)
2129 FOR_BB_INSNS (bb
, insn
)
2131 remove_scratches_1 (insn
);
2134 /* Changes pseudos created by function remove_scratches onto scratches. */
2136 restore_scratches (void)
2141 rtx_insn
*last
= NULL
;
2142 lra_insn_recog_data_t id
= NULL
;
2144 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
2146 /* Ignore already deleted insns. */
2147 if (NOTE_P (loc
->insn
)
2148 && NOTE_KIND (loc
->insn
) == NOTE_INSN_DELETED
)
2150 if (last
!= loc
->insn
)
2153 id
= lra_get_insn_recog_data (last
);
2155 if (loc
->icode
!= id
->icode
)
2157 /* The icode doesn't match, which means the insn has been modified
2158 (e.g. register elimination). The scratch cannot be restored. */
2161 if (REG_P (*id
->operand_loc
[loc
->nop
])
2162 && ((regno
= REGNO (*id
->operand_loc
[loc
->nop
]))
2163 >= FIRST_PSEUDO_REGISTER
)
2164 && lra_get_regno_hard_regno (regno
) < 0)
2166 /* It should be only case when scratch register with chosen
2167 constraint 'X' did not get memory or hard register. */
2168 lra_assert (lra_former_scratch_p (regno
));
2169 *id
->operand_loc
[loc
->nop
]
2170 = gen_rtx_SCRATCH (GET_MODE (*id
->operand_loc
[loc
->nop
]));
2171 lra_update_dup (id
, loc
->nop
);
2172 if (lra_dump_file
!= NULL
)
2173 fprintf (lra_dump_file
, "Restoring SCRATCH in insn #%u(nop %d)\n",
2174 INSN_UID (loc
->insn
), loc
->nop
);
2177 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
2179 scratches
.release ();
2180 bitmap_clear (&scratch_bitmap
);
2181 bitmap_clear (&scratch_operand_bitmap
);
2186 /* Function checks RTL for correctness. If FINAL_P is true, it is
2187 done at the end of LRA and the check is more rigorous. */
2189 check_rtl (bool final_p
)
2194 lra_assert (! final_p
|| reload_completed
);
2195 FOR_EACH_BB_FN (bb
, cfun
)
2196 FOR_BB_INSNS (bb
, insn
)
2197 if (NONDEBUG_INSN_P (insn
)
2198 && GET_CODE (PATTERN (insn
)) != USE
2199 && GET_CODE (PATTERN (insn
)) != CLOBBER
2200 && GET_CODE (PATTERN (insn
)) != ASM_INPUT
)
2204 extract_constrain_insn (insn
);
2207 /* LRA code is based on assumption that all addresses can be
2208 correctly decomposed. LRA can generate reloads for
2209 decomposable addresses. The decomposition code checks the
2210 correctness of the addresses. So we don't need to check
2211 the addresses here. Don't call insn_invalid_p here, it can
2212 change the code at this stage. */
2213 if (recog_memoized (insn
) < 0 && asm_noperands (PATTERN (insn
)) < 0)
2214 fatal_insn_not_found (insn
);
2218 /* Determine if the current function has an exception receiver block
2219 that reaches the exit block via non-exceptional edges */
2221 has_nonexceptional_receiver (void)
2225 basic_block
*tos
, *worklist
, bb
;
2227 /* If we're not optimizing, then just err on the safe side. */
2231 /* First determine which blocks can reach exit via normal paths. */
2232 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
) + 1);
2234 FOR_EACH_BB_FN (bb
, cfun
)
2235 bb
->flags
&= ~BB_REACHABLE
;
2237 /* Place the exit block on our worklist. */
2238 EXIT_BLOCK_PTR_FOR_FN (cfun
)->flags
|= BB_REACHABLE
;
2239 *tos
++ = EXIT_BLOCK_PTR_FOR_FN (cfun
);
2241 /* Iterate: find everything reachable from what we've already seen. */
2242 while (tos
!= worklist
)
2246 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2247 if (e
->flags
& EDGE_ABNORMAL
)
2254 basic_block src
= e
->src
;
2256 if (!(src
->flags
& BB_REACHABLE
))
2258 src
->flags
|= BB_REACHABLE
;
2264 /* No exceptional block reached exit unexceptionally. */
2269 /* Process recursively X of INSN and add REG_INC notes if necessary. */
2271 add_auto_inc_notes (rtx_insn
*insn
, rtx x
)
2273 enum rtx_code code
= GET_CODE (x
);
2277 if (code
== MEM
&& auto_inc_p (XEXP (x
, 0)))
2279 add_reg_note (insn
, REG_INC
, XEXP (XEXP (x
, 0), 0));
2283 /* Scan all X sub-expressions. */
2284 fmt
= GET_RTX_FORMAT (code
);
2285 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2288 add_auto_inc_notes (insn
, XEXP (x
, i
));
2289 else if (fmt
[i
] == 'E')
2290 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2291 add_auto_inc_notes (insn
, XVECEXP (x
, i
, j
));
2296 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2297 We change pseudos by hard registers without notification of DF and
2298 that can make the notes obsolete. DF-infrastructure does not deal
2299 with REG_INC notes -- so we should regenerate them here. */
2301 update_inc_notes (void)
2307 FOR_EACH_BB_FN (bb
, cfun
)
2308 FOR_BB_INSNS (bb
, insn
)
2309 if (NONDEBUG_INSN_P (insn
))
2311 pnote
= ®_NOTES (insn
);
2314 if (REG_NOTE_KIND (*pnote
) == REG_DEAD
2315 || REG_NOTE_KIND (*pnote
) == REG_UNUSED
2316 || REG_NOTE_KIND (*pnote
) == REG_INC
)
2317 *pnote
= XEXP (*pnote
, 1);
2319 pnote
= &XEXP (*pnote
, 1);
2323 add_auto_inc_notes (insn
, PATTERN (insn
));
2327 /* Set to 1 while in lra. */
2328 int lra_in_progress
;
2330 /* Start of pseudo regnos before the LRA. */
2331 int lra_new_regno_start
;
2333 /* Start of reload pseudo regnos before the new spill pass. */
2334 int lra_constraint_new_regno_start
;
2336 /* Avoid spilling pseudos with regno more than the following value if
2338 int lra_bad_spill_regno_start
;
2340 /* Inheritance pseudo regnos before the new spill pass. */
2341 bitmap_head lra_inheritance_pseudos
;
2343 /* Split regnos before the new spill pass. */
2344 bitmap_head lra_split_regs
;
2346 /* Reload pseudo regnos before the new assignment pass which still can
2347 be spilled after the assignment pass as memory is also accepted in
2348 insns for the reload pseudos. */
2349 bitmap_head lra_optional_reload_pseudos
;
2351 /* Pseudo regnos used for subreg reloads before the new assignment
2352 pass. Such pseudos still can be spilled after the assignment
2354 bitmap_head lra_subreg_reload_pseudos
;
2356 /* File used for output of LRA debug information. */
2357 FILE *lra_dump_file
;
2359 /* True if we found an asm error. */
2360 bool lra_asm_error_p
;
2362 /* True if we should try spill into registers of different classes
2363 instead of memory. */
2364 bool lra_reg_spill_p
;
2366 /* Set up value LRA_REG_SPILL_P. */
2368 setup_reg_spill_flag (void)
2372 if (targetm
.spill_class
!= NULL
)
2373 for (cl
= 0; cl
< (int) LIM_REG_CLASSES
; cl
++)
2374 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
2375 if (targetm
.spill_class ((enum reg_class
) cl
,
2376 (machine_mode
) mode
) != NO_REGS
)
2378 lra_reg_spill_p
= true;
2381 lra_reg_spill_p
= false;
2384 /* True if the current function is too big to use regular algorithms
2385 in LRA. In other words, we should use simpler and faster algorithms
2386 in LRA. It also means we should not worry about generation code
2387 for caller saves. The value is set up in IRA. */
2390 /* Major LRA entry function. F is a file should be used to dump LRA
2396 bool live_p
, inserted_p
;
2399 lra_asm_error_p
= false;
2401 timevar_push (TV_LRA
);
2403 /* Make sure that the last insn is a note. Some subsequent passes
2405 emit_note (NOTE_INSN_DELETED
);
2407 COPY_HARD_REG_SET (lra_no_alloc_regs
, ira_no_alloc_regs
);
2412 init_insn_recog_data ();
2414 /* Some quick check on RTL generated by previous passes. */
2418 lra_in_progress
= 1;
2420 lra_live_range_iter
= lra_coalesce_iter
= lra_constraint_iter
= 0;
2421 lra_assignment_iter
= lra_assignment_iter_after_spill
= 0;
2422 lra_inheritance_iter
= lra_undo_inheritance_iter
= 0;
2423 lra_rematerialization_iter
= 0;
2425 setup_reg_spill_flag ();
2427 /* Function remove_scratches can creates new pseudos for clobbers --
2428 so set up lra_constraint_new_regno_start before its call to
2429 permit changing reg classes for pseudos created by this
2431 lra_constraint_new_regno_start
= lra_new_regno_start
= max_reg_num ();
2432 lra_bad_spill_regno_start
= INT_MAX
;
2433 remove_scratches ();
2435 /* A function that has a non-local label that can reach the exit
2436 block via non-exceptional paths must save all call-saved
2438 if (cfun
->has_nonlocal_label
&& has_nonexceptional_receiver ())
2439 crtl
->saves_all_registers
= 1;
2441 if (crtl
->saves_all_registers
)
2442 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2443 if (! call_used_regs
[i
] && ! fixed_regs
[i
] && ! LOCAL_REGNO (i
))
2444 df_set_regs_ever_live (i
, true);
2446 /* We don't DF from now and avoid its using because it is to
2447 expensive when a lot of RTL changes are made. */
2448 df_set_flags (DF_NO_INSN_RESCAN
);
2449 lra_constraint_insn_stack
.create (get_max_uid ());
2450 lra_constraint_insn_stack_bitmap
= sbitmap_alloc (get_max_uid ());
2451 bitmap_clear (lra_constraint_insn_stack_bitmap
);
2452 lra_live_ranges_init ();
2453 lra_constraints_init ();
2454 lra_curr_reload_num
= 0;
2455 push_insns (get_last_insn (), NULL
);
2456 /* It is needed for the 1st coalescing. */
2457 bitmap_initialize (&lra_inheritance_pseudos
, ®_obstack
);
2458 bitmap_initialize (&lra_split_regs
, ®_obstack
);
2459 bitmap_initialize (&lra_optional_reload_pseudos
, ®_obstack
);
2460 bitmap_initialize (&lra_subreg_reload_pseudos
, ®_obstack
);
2462 if (maybe_ne (get_frame_size (), 0) && crtl
->stack_alignment_needed
)
2463 /* If we have a stack frame, we must align it now. The stack size
2464 may be a part of the offset computation for register
2466 assign_stack_local (BLKmode
, 0, crtl
->stack_alignment_needed
);
2472 bool reloads_p
= lra_constraints (lra_constraint_iter
== 0);
2473 /* Constraint transformations may result in that eliminable
2474 hard regs become uneliminable and pseudos which use them
2475 should be spilled. It is better to do it before pseudo
2478 For example, rs6000 can make
2479 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2480 to use a constant pool. */
2481 lra_eliminate (false, false);
2482 /* We should try to assign hard registers to scratches even
2483 if there were no RTL transformations in lra_constraints.
2484 Also we should check IRA assignments on the first
2485 iteration as they can be wrong because of early clobbers
2486 operands which are ignored in IRA. */
2487 if (! reloads_p
&& lra_constraint_iter
> 1)
2489 /* Stack is not empty here only when there are changes
2490 during the elimination sub-pass. */
2491 if (bitmap_empty_p (lra_constraint_insn_stack_bitmap
))
2494 /* If there are no reloads but changing due
2495 elimination, restart the constraint sub-pass
2499 /* Do inheritance only for regular algorithms. */
2505 lra_clear_live_ranges ();
2506 /* As a side-effect of lra_create_live_ranges, we calculate
2507 actual_call_used_reg_set, which is needed during
2509 lra_create_live_ranges (true, true);
2515 lra_clear_live_ranges ();
2519 /* We need live ranges for lra_assign -- so build them.
2520 But don't remove dead insns or change global live
2521 info as we can undo inheritance transformations after
2522 inheritance pseudo assigning. */
2523 lra_create_live_ranges (true, false);
2525 /* If we don't spill non-reload and non-inheritance
2526 pseudos, there is no sense to run memory-memory move
2527 coalescing. If inheritance pseudos were spilled, the
2528 memory-memory moves involving them will be removed by
2529 pass undoing inheritance. */
2531 lra_assign (fails_p
);
2534 bool spill_p
= !lra_assign (fails_p
);
2536 if (lra_undo_inheritance ())
2538 if (spill_p
&& ! fails_p
)
2542 lra_create_live_ranges (true, true);
2545 if (lra_coalesce ())
2549 lra_clear_live_ranges ();
2553 /* It is a very rare case. It is the last hope to
2554 split a hard regno live range for a reload
2557 lra_clear_live_ranges ();
2559 if (! lra_split_hard_reg_for ())
2565 /* Don't clear optional reloads bitmap until all constraints are
2566 satisfied as we need to differ them from regular reloads. */
2567 bitmap_clear (&lra_optional_reload_pseudos
);
2568 bitmap_clear (&lra_subreg_reload_pseudos
);
2569 bitmap_clear (&lra_inheritance_pseudos
);
2570 bitmap_clear (&lra_split_regs
);
2573 /* We need full live info for spilling pseudos into
2574 registers instead of memory. */
2575 lra_create_live_ranges (lra_reg_spill_p
, true);
2578 /* We should check necessity for spilling here as the above live
2579 range pass can remove spilled pseudos. */
2580 if (! lra_need_for_spills_p ())
2582 /* Now we know what pseudos should be spilled. Try to
2583 rematerialize them first. */
2586 /* We need full live info -- see the comment above. */
2587 lra_create_live_ranges (lra_reg_spill_p
, true);
2589 if (! lra_need_for_spills_p ())
2593 /* Assignment of stack slots changes elimination offsets for
2594 some eliminations. So update the offsets here. */
2595 lra_eliminate (false, false);
2596 lra_constraint_new_regno_start
= max_reg_num ();
2597 if (lra_bad_spill_regno_start
== INT_MAX
2598 && lra_inheritance_iter
> LRA_MAX_INHERITANCE_PASSES
2599 && lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
2600 /* After switching off inheritance and rematerialization
2601 passes, avoid spilling reload pseudos will be created to
2602 prevent LRA cycling in some complicated cases. */
2603 lra_bad_spill_regno_start
= lra_constraint_new_regno_start
;
2604 lra_assignment_iter_after_spill
= 0;
2606 restore_scratches ();
2607 lra_eliminate (true, false);
2608 lra_final_code_change ();
2609 lra_in_progress
= 0;
2611 lra_clear_live_ranges ();
2612 lra_live_ranges_finish ();
2613 lra_constraints_finish ();
2615 sbitmap_free (lra_constraint_insn_stack_bitmap
);
2616 lra_constraint_insn_stack
.release ();
2617 finish_insn_recog_data ();
2618 regstat_free_n_sets_and_refs ();
2620 reload_completed
= 1;
2621 update_inc_notes ();
2623 inserted_p
= fixup_abnormal_edges ();
2625 /* We've possibly turned single trapping insn into multiple ones. */
2626 if (cfun
->can_throw_non_call_exceptions
)
2628 auto_sbitmap
blocks (last_basic_block_for_fn (cfun
));
2629 bitmap_ones (blocks
);
2630 find_many_sub_basic_blocks (blocks
);
2634 commit_edge_insertions ();
2636 /* Replacing pseudos with their memory equivalents might have
2637 created shared rtx. Subsequent passes would get confused
2638 by this, so unshare everything here. */
2639 unshare_all_rtl_again (get_insns ());
2644 timevar_pop (TV_LRA
);
2647 /* Called once per compiler to initialize LRA data once. */
2649 lra_init_once (void)
2651 init_insn_code_data_once ();
2654 /* Called once per compiler to finish LRA data which are initialize
2657 lra_finish_once (void)
2659 finish_insn_code_data_once ();