Daily bump.
[official-gcc.git] / gcc / lra.c
blob1230b25e7e12e6dcc41ac51a96e9d1522ec6d1f5
1 /* LRA (local register allocator) driver and LRA utilities.
2 Copyright (C) 2010-2017 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
10 version.
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
15 for more details.
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
30 as possible
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
37 generated;
38 o Some pseudos might be spilled to assign hard registers to
39 new reload pseudos;
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 ----------- | ---------------- |
59 | | |
60 | V New |
61 | ------------ pseudos -------------------
62 | |Constraints:| or insns | Inheritance/split |
63 | | RTL |--------->| transformations |
64 | | transfor- | | in EBB scope |
65 | substi- | mations | -------------------
66 | tutions ------------
67 | | No change
68 ---------------- V
69 | Spilled pseudo | -------------------
70 | to memory |<----| Rematerialization |
71 | substitution | -------------------
72 ----------------
73 | No susbtitions
75 -------------------------
76 | Hard regs substitution, |
77 | devirtalization, and |------> Finish
78 | restoring scratches got |
79 | memory |
80 -------------------------
82 To speed up the process:
83 o We process only insns affected by changes on previous
84 iterations;
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).
94 o Pseudo data:
95 o all insns where the pseudo is referenced;
96 o live info (conflicting hard regs, live ranges, # of
97 references etc);
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. */
103 #include "config.h"
104 #include "system.h"
105 #include "coretypes.h"
106 #include "backend.h"
107 #include "target.h"
108 #include "rtl.h"
109 #include "tree.h"
110 #include "predict.h"
111 #include "df.h"
112 #include "memmodel.h"
113 #include "tm_p.h"
114 #include "optabs.h"
115 #include "regs.h"
116 #include "ira.h"
117 #include "recog.h"
118 #include "expr.h"
119 #include "cfgrtl.h"
120 #include "cfgbuild.h"
121 #include "lra.h"
122 #include "lra-int.h"
123 #include "print-rtl.h"
125 /* Dump bitmap SET with TITLE and BB INDEX. */
126 void
127 lra_dump_bitmap_with_title (const char *title, bitmap set, int index)
129 unsigned int i;
130 int count;
131 bitmap_iterator bi;
132 static const int max_nums_on_line = 10;
134 if (bitmap_empty_p (set))
135 return;
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 ");
144 count = 0;
146 fprintf (lra_dump_file, " %4u", i);
147 count++;
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,
161 rtx_insn *, int);
163 /* Expand all regno related info needed for LRA. */
164 static void
165 expand_reg_data (int old)
167 resize_reg_info ();
168 expand_reg_info ();
169 ira_expand_reg_equiv ();
170 for (int i = (int) max_reg_num () - 1; i >= old; i--)
171 lra_change_class (i, ALL_REGS, " Set", true);
174 /* Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL
175 or of VOIDmode, use MD_MODE for the new reg. Initialize its
176 register class to RCLASS. Print message about assigning class
177 RCLASS containing new register name TITLE unless it is NULL. Use
178 attributes of ORIGINAL if it is a register. The created register
179 will have unique held value. */
181 lra_create_new_reg_with_unique_value (machine_mode md_mode, rtx original,
182 enum reg_class rclass, const char *title)
184 machine_mode mode;
185 rtx new_reg;
187 if (original == NULL_RTX || (mode = GET_MODE (original)) == VOIDmode)
188 mode = md_mode;
189 lra_assert (mode != VOIDmode);
190 new_reg = gen_reg_rtx (mode);
191 if (original == NULL_RTX || ! REG_P (original))
193 if (lra_dump_file != NULL)
194 fprintf (lra_dump_file, " Creating newreg=%i", REGNO (new_reg));
196 else
198 if (ORIGINAL_REGNO (original) >= FIRST_PSEUDO_REGISTER)
199 ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original);
200 REG_USERVAR_P (new_reg) = REG_USERVAR_P (original);
201 REG_POINTER (new_reg) = REG_POINTER (original);
202 REG_ATTRS (new_reg) = REG_ATTRS (original);
203 if (lra_dump_file != NULL)
204 fprintf (lra_dump_file, " Creating newreg=%i from oldreg=%i",
205 REGNO (new_reg), REGNO (original));
207 if (lra_dump_file != NULL)
209 if (title != NULL)
210 fprintf (lra_dump_file, ", assigning class %s to%s%s r%d",
211 reg_class_names[rclass], *title == '\0' ? "" : " ",
212 title, REGNO (new_reg));
213 fprintf (lra_dump_file, "\n");
215 expand_reg_data (max_reg_num ());
216 setup_reg_classes (REGNO (new_reg), rclass, NO_REGS, rclass);
217 return new_reg;
220 /* Analogous to the previous function but also inherits value of
221 ORIGINAL. */
223 lra_create_new_reg (machine_mode md_mode, rtx original,
224 enum reg_class rclass, const char *title)
226 rtx new_reg;
228 new_reg
229 = lra_create_new_reg_with_unique_value (md_mode, original, rclass, title);
230 if (original != NULL_RTX && REG_P (original))
231 lra_assign_reg_val (REGNO (original), REGNO (new_reg));
232 return new_reg;
235 /* Set up for REGNO unique hold value. */
236 void
237 lra_set_regno_unique_value (int regno)
239 lra_reg_info[regno].val = get_new_reg_value ();
242 /* Invalidate INSN related info used by LRA. The info should never be
243 used after that. */
244 void
245 lra_invalidate_insn_data (rtx_insn *insn)
247 lra_invalidate_insn_regno_info (insn);
248 invalidate_insn_recog_data (INSN_UID (insn));
251 /* Mark INSN deleted and invalidate the insn related info used by
252 LRA. */
253 void
254 lra_set_insn_deleted (rtx_insn *insn)
256 lra_invalidate_insn_data (insn);
257 SET_INSN_DELETED (insn);
260 /* Delete an unneeded INSN and any previous insns who sole purpose is
261 loading data that is dead in INSN. */
262 void
263 lra_delete_dead_insn (rtx_insn *insn)
265 rtx_insn *prev = prev_real_insn (insn);
266 rtx prev_dest;
268 /* If the previous insn sets a register that dies in our insn,
269 delete it too. */
270 if (prev && GET_CODE (PATTERN (prev)) == SET
271 && (prev_dest = SET_DEST (PATTERN (prev)), REG_P (prev_dest))
272 && reg_mentioned_p (prev_dest, PATTERN (insn))
273 && find_regno_note (insn, REG_DEAD, REGNO (prev_dest))
274 && ! side_effects_p (SET_SRC (PATTERN (prev))))
275 lra_delete_dead_insn (prev);
277 lra_set_insn_deleted (insn);
280 /* Emit insn x = y + z. Return NULL if we failed to do it.
281 Otherwise, return the insn. We don't use gen_add3_insn as it might
282 clobber CC. */
283 static rtx_insn *
284 emit_add3_insn (rtx x, rtx y, rtx z)
286 rtx_insn *last;
288 last = get_last_insn ();
290 if (have_addptr3_insn (x, y, z))
292 rtx_insn *insn = gen_addptr3_insn (x, y, z);
294 /* If the target provides an "addptr" pattern it hopefully does
295 for a reason. So falling back to the normal add would be
296 a bug. */
297 lra_assert (insn != NULL_RTX);
298 emit_insn (insn);
299 return insn;
302 rtx_insn *insn = emit_insn (gen_rtx_SET (x, gen_rtx_PLUS (GET_MODE (y),
303 y, z)));
304 if (recog_memoized (insn) < 0)
306 delete_insns_since (last);
307 insn = NULL;
309 return insn;
312 /* Emit insn x = x + y. Return the insn. We use gen_add2_insn as the
313 last resort. */
314 static rtx_insn *
315 emit_add2_insn (rtx x, rtx y)
317 rtx_insn *insn = emit_add3_insn (x, x, y);
318 if (insn == NULL_RTX)
320 insn = gen_add2_insn (x, y);
321 if (insn != NULL_RTX)
322 emit_insn (insn);
324 return insn;
327 /* Target checks operands through operand predicates to recognize an
328 insn. We should have a special precaution to generate add insns
329 which are frequent results of elimination.
331 Emit insns for x = y + z. X can be used to store intermediate
332 values and should be not in Y and Z when we use X to store an
333 intermediate value. Y + Z should form [base] [+ index[ * scale]] [
334 + disp] where base and index are registers, disp and scale are
335 constants. Y should contain base if it is present, Z should
336 contain disp if any. index[*scale] can be part of Y or Z. */
337 void
338 lra_emit_add (rtx x, rtx y, rtx z)
340 int old;
341 rtx_insn *last;
342 rtx a1, a2, base, index, disp, scale, index_scale;
343 bool ok_p;
345 rtx_insn *add3_insn = emit_add3_insn (x, y, z);
346 old = max_reg_num ();
347 if (add3_insn != NULL)
349 else
351 disp = a2 = NULL_RTX;
352 if (GET_CODE (y) == PLUS)
354 a1 = XEXP (y, 0);
355 a2 = XEXP (y, 1);
356 disp = z;
358 else
360 a1 = y;
361 if (CONSTANT_P (z))
362 disp = z;
363 else
364 a2 = z;
366 index_scale = scale = NULL_RTX;
367 if (GET_CODE (a1) == MULT)
369 index_scale = a1;
370 index = XEXP (a1, 0);
371 scale = XEXP (a1, 1);
372 base = a2;
374 else if (a2 != NULL_RTX && GET_CODE (a2) == MULT)
376 index_scale = a2;
377 index = XEXP (a2, 0);
378 scale = XEXP (a2, 1);
379 base = a1;
381 else
383 base = a1;
384 index = a2;
386 if ((base != NULL_RTX && ! (REG_P (base) || GET_CODE (base) == SUBREG))
387 || (index != NULL_RTX
388 && ! (REG_P (index) || GET_CODE (index) == SUBREG))
389 || (disp != NULL_RTX && ! CONSTANT_P (disp))
390 || (scale != NULL_RTX && ! CONSTANT_P (scale)))
392 /* Probably we have no 3 op add. Last chance is to use 2-op
393 add insn. To succeed, don't move Z to X as an address
394 segment always comes in Y. Otherwise, we might fail when
395 adding the address segment to register. */
396 lra_assert (x != y && x != z);
397 emit_move_insn (x, y);
398 rtx_insn *insn = emit_add2_insn (x, z);
399 lra_assert (insn != NULL_RTX);
401 else
403 if (index_scale == NULL_RTX)
404 index_scale = index;
405 if (disp == NULL_RTX)
407 /* Generate x = index_scale; x = x + base. */
408 lra_assert (index_scale != NULL_RTX && base != NULL_RTX);
409 emit_move_insn (x, index_scale);
410 rtx_insn *insn = emit_add2_insn (x, base);
411 lra_assert (insn != NULL_RTX);
413 else if (scale == NULL_RTX)
415 /* Try x = base + disp. */
416 lra_assert (base != NULL_RTX);
417 last = get_last_insn ();
418 rtx_insn *move_insn =
419 emit_move_insn (x, gen_rtx_PLUS (GET_MODE (base), base, disp));
420 if (recog_memoized (move_insn) < 0)
422 delete_insns_since (last);
423 /* Generate x = disp; x = x + base. */
424 emit_move_insn (x, disp);
425 rtx_insn *add2_insn = emit_add2_insn (x, base);
426 lra_assert (add2_insn != NULL_RTX);
428 /* Generate x = x + index. */
429 if (index != NULL_RTX)
431 rtx_insn *insn = emit_add2_insn (x, index);
432 lra_assert (insn != NULL_RTX);
435 else
437 /* Try x = index_scale; x = x + disp; x = x + base. */
438 last = get_last_insn ();
439 rtx_insn *move_insn = emit_move_insn (x, index_scale);
440 ok_p = false;
441 if (recog_memoized (move_insn) >= 0)
443 rtx_insn *insn = emit_add2_insn (x, disp);
444 if (insn != NULL_RTX)
446 if (base == NULL_RTX)
447 ok_p = true;
448 else
450 insn = emit_add2_insn (x, base);
451 if (insn != NULL_RTX)
452 ok_p = true;
456 if (! ok_p)
458 rtx_insn *insn;
460 delete_insns_since (last);
461 /* Generate x = disp; x = x + base; x = x + index_scale. */
462 emit_move_insn (x, disp);
463 if (base != NULL_RTX)
465 insn = emit_add2_insn (x, base);
466 lra_assert (insn != NULL_RTX);
468 insn = emit_add2_insn (x, index_scale);
469 lra_assert (insn != NULL_RTX);
474 /* Functions emit_... can create pseudos -- so expand the pseudo
475 data. */
476 if (old != max_reg_num ())
477 expand_reg_data (old);
480 /* The number of emitted reload insns so far. */
481 int lra_curr_reload_num;
483 /* Emit x := y, processing special case when y = u + v or y = u + v *
484 scale + w through emit_add (Y can be an address which is base +
485 index reg * scale + displacement in general case). X may be used
486 as intermediate result therefore it should be not in Y. */
487 void
488 lra_emit_move (rtx x, rtx y)
490 int old;
492 if (GET_CODE (y) != PLUS)
494 if (rtx_equal_p (x, y))
495 return;
496 old = max_reg_num ();
497 emit_move_insn (x, y);
498 if (REG_P (x))
499 lra_reg_info[ORIGINAL_REGNO (x)].last_reload = ++lra_curr_reload_num;
500 /* Function emit_move can create pseudos -- so expand the pseudo
501 data. */
502 if (old != max_reg_num ())
503 expand_reg_data (old);
504 return;
506 lra_emit_add (x, XEXP (y, 0), XEXP (y, 1));
509 /* Update insn operands which are duplication of operands whose
510 numbers are in array of NOPS (with end marker -1). The insn is
511 represented by its LRA internal representation ID. */
512 void
513 lra_update_dups (lra_insn_recog_data_t id, signed char *nops)
515 int i, j, nop;
516 struct lra_static_insn_data *static_id = id->insn_static_data;
518 for (i = 0; i < static_id->n_dups; i++)
519 for (j = 0; (nop = nops[j]) >= 0; j++)
520 if (static_id->dup_num[i] == nop)
521 *id->dup_loc[i] = *id->operand_loc[nop];
526 /* This page contains code dealing with info about registers in the
527 insns. */
529 /* Pools for insn reg info. */
530 object_allocator<lra_insn_reg> lra_insn_reg_pool ("insn regs");
532 /* Create LRA insn related info about a reference to REGNO in INSN
533 with TYPE (in/out/inout), biggest reference mode MODE, flag that it
534 is reference through subreg (SUBREG_P), flag that is early
535 clobbered in the insn (EARLY_CLOBBER), and reference to the next
536 insn reg info (NEXT). If REGNO can be early clobbered,
537 alternatives in which it can be early clobbered are given by
538 EARLY_CLOBBER_ALTS. */
539 static struct lra_insn_reg *
540 new_insn_reg (rtx_insn *insn, int regno, enum op_type type,
541 machine_mode mode,
542 bool subreg_p, bool early_clobber,
543 alternative_mask early_clobber_alts,
544 struct lra_insn_reg *next)
546 lra_insn_reg *ir = lra_insn_reg_pool.allocate ();
547 ir->type = type;
548 ir->biggest_mode = mode;
549 if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (lra_reg_info[regno].biggest_mode)
550 && NONDEBUG_INSN_P (insn))
551 lra_reg_info[regno].biggest_mode = mode;
552 ir->subreg_p = subreg_p;
553 ir->early_clobber = early_clobber;
554 ir->early_clobber_alts = early_clobber_alts;
555 ir->regno = regno;
556 ir->next = next;
557 return ir;
560 /* Free insn reg info list IR. */
561 static void
562 free_insn_regs (struct lra_insn_reg *ir)
564 struct lra_insn_reg *next_ir;
566 for (; ir != NULL; ir = next_ir)
568 next_ir = ir->next;
569 lra_insn_reg_pool.remove (ir);
573 /* Finish pool for insn reg info. */
574 static void
575 finish_insn_regs (void)
577 lra_insn_reg_pool.release ();
582 /* This page contains code dealing LRA insn info (or in other words
583 LRA internal insn representation). */
585 /* Map INSN_CODE -> the static insn data. This info is valid during
586 all translation unit. */
587 struct lra_static_insn_data *insn_code_data[NUM_INSN_CODES];
589 /* Debug insns are represented as a special insn with one input
590 operand which is RTL expression in var_location. */
592 /* The following data are used as static insn operand data for all
593 debug insns. If structure lra_operand_data is changed, the
594 initializer should be changed too. */
595 static struct lra_operand_data debug_operand_data =
597 NULL, /* alternative */
598 0, /* early_clobber_alts */
599 VOIDmode, /* We are not interesting in the operand mode. */
600 OP_IN,
601 0, 0, 0, 0
604 /* The following data are used as static insn data for all debug
605 insns. If structure lra_static_insn_data is changed, the
606 initializer should be changed too. */
607 static struct lra_static_insn_data debug_insn_static_data =
609 &debug_operand_data,
610 0, /* Duplication operands #. */
611 -1, /* Commutative operand #. */
612 1, /* Operands #. There is only one operand which is debug RTL
613 expression. */
614 0, /* Duplications #. */
615 0, /* Alternatives #. We are not interesting in alternatives
616 because we does not proceed debug_insns for reloads. */
617 NULL, /* Hard registers referenced in machine description. */
618 NULL /* Descriptions of operands in alternatives. */
621 /* Called once per compiler work to initialize some LRA data related
622 to insns. */
623 static void
624 init_insn_code_data_once (void)
626 memset (insn_code_data, 0, sizeof (insn_code_data));
629 /* Called once per compiler work to finalize some LRA data related to
630 insns. */
631 static void
632 finish_insn_code_data_once (void)
634 for (unsigned int i = 0; i < NUM_INSN_CODES; i++)
636 if (insn_code_data[i] != NULL)
637 free (insn_code_data[i]);
641 /* Return static insn data, allocate and setup if necessary. Although
642 dup_num is static data (it depends only on icode), to set it up we
643 need to extract insn first. So recog_data should be valid for
644 normal insn (ICODE >= 0) before the call. */
645 static struct lra_static_insn_data *
646 get_static_insn_data (int icode, int nop, int ndup, int nalt)
648 struct lra_static_insn_data *data;
649 size_t n_bytes;
651 lra_assert (icode < (int) NUM_INSN_CODES);
652 if (icode >= 0 && (data = insn_code_data[icode]) != NULL)
653 return data;
654 lra_assert (nop >= 0 && ndup >= 0 && nalt >= 0);
655 n_bytes = sizeof (struct lra_static_insn_data)
656 + sizeof (struct lra_operand_data) * nop
657 + sizeof (int) * ndup;
658 data = XNEWVAR (struct lra_static_insn_data, n_bytes);
659 data->operand_alternative = NULL;
660 data->n_operands = nop;
661 data->n_dups = ndup;
662 data->n_alternatives = nalt;
663 data->operand = ((struct lra_operand_data *)
664 ((char *) data + sizeof (struct lra_static_insn_data)));
665 data->dup_num = ((int *) ((char *) data->operand
666 + sizeof (struct lra_operand_data) * nop));
667 if (icode >= 0)
669 int i;
671 insn_code_data[icode] = data;
672 for (i = 0; i < nop; i++)
674 data->operand[i].constraint
675 = insn_data[icode].operand[i].constraint;
676 data->operand[i].mode = insn_data[icode].operand[i].mode;
677 data->operand[i].strict_low = insn_data[icode].operand[i].strict_low;
678 data->operand[i].is_operator
679 = insn_data[icode].operand[i].is_operator;
680 data->operand[i].type
681 = (data->operand[i].constraint[0] == '=' ? OP_OUT
682 : data->operand[i].constraint[0] == '+' ? OP_INOUT
683 : OP_IN);
684 data->operand[i].is_address = false;
686 for (i = 0; i < ndup; i++)
687 data->dup_num[i] = recog_data.dup_num[i];
689 return data;
692 /* The current length of the following array. */
693 int lra_insn_recog_data_len;
695 /* Map INSN_UID -> the insn recog data (NULL if unknown). */
696 lra_insn_recog_data_t *lra_insn_recog_data;
698 /* Initialize LRA data about insns. */
699 static void
700 init_insn_recog_data (void)
702 lra_insn_recog_data_len = 0;
703 lra_insn_recog_data = NULL;
706 /* Expand, if necessary, LRA data about insns. */
707 static void
708 check_and_expand_insn_recog_data (int index)
710 int i, old;
712 if (lra_insn_recog_data_len > index)
713 return;
714 old = lra_insn_recog_data_len;
715 lra_insn_recog_data_len = index * 3 / 2 + 1;
716 lra_insn_recog_data = XRESIZEVEC (lra_insn_recog_data_t,
717 lra_insn_recog_data,
718 lra_insn_recog_data_len);
719 for (i = old; i < lra_insn_recog_data_len; i++)
720 lra_insn_recog_data[i] = NULL;
723 /* Finish LRA DATA about insn. */
724 static void
725 free_insn_recog_data (lra_insn_recog_data_t data)
727 if (data->operand_loc != NULL)
728 free (data->operand_loc);
729 if (data->dup_loc != NULL)
730 free (data->dup_loc);
731 if (data->arg_hard_regs != NULL)
732 free (data->arg_hard_regs);
733 if (data->icode < 0 && NONDEBUG_INSN_P (data->insn))
735 if (data->insn_static_data->operand_alternative != NULL)
736 free (const_cast <operand_alternative *>
737 (data->insn_static_data->operand_alternative));
738 free_insn_regs (data->insn_static_data->hard_regs);
739 free (data->insn_static_data);
741 free_insn_regs (data->regs);
742 data->regs = NULL;
743 free (data);
746 /* Pools for copies. */
747 static object_allocator<lra_copy> lra_copy_pool ("lra copies");
749 /* Finish LRA data about all insns. */
750 static void
751 finish_insn_recog_data (void)
753 int i;
754 lra_insn_recog_data_t data;
756 for (i = 0; i < lra_insn_recog_data_len; i++)
757 if ((data = lra_insn_recog_data[i]) != NULL)
758 free_insn_recog_data (data);
759 finish_insn_regs ();
760 lra_copy_pool.release ();
761 lra_insn_reg_pool.release ();
762 free (lra_insn_recog_data);
765 /* Setup info about operands in alternatives of LRA DATA of insn. */
766 static void
767 setup_operand_alternative (lra_insn_recog_data_t data,
768 const operand_alternative *op_alt)
770 int i, j, nop, nalt;
771 int icode = data->icode;
772 struct lra_static_insn_data *static_data = data->insn_static_data;
774 static_data->commutative = -1;
775 nop = static_data->n_operands;
776 nalt = static_data->n_alternatives;
777 static_data->operand_alternative = op_alt;
778 for (i = 0; i < nop; i++)
780 static_data->operand[i].early_clobber_alts = 0;
781 static_data->operand[i].early_clobber = false;
782 static_data->operand[i].is_address = false;
783 if (static_data->operand[i].constraint[0] == '%')
785 /* We currently only support one commutative pair of operands. */
786 if (static_data->commutative < 0)
787 static_data->commutative = i;
788 else
789 lra_assert (icode < 0); /* Asm */
790 /* The last operand should not be marked commutative. */
791 lra_assert (i != nop - 1);
794 for (j = 0; j < nalt; j++)
795 for (i = 0; i < nop; i++, op_alt++)
797 static_data->operand[i].early_clobber |= op_alt->earlyclobber;
798 if (op_alt->earlyclobber)
799 static_data->operand[i].early_clobber_alts |= (alternative_mask) 1 << j;
800 static_data->operand[i].is_address |= op_alt->is_address;
804 /* Recursively process X and collect info about registers, which are
805 not the insn operands, in X with TYPE (in/out/inout) and flag that
806 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
807 to LIST. X is a part of insn given by DATA. Return the result
808 list. */
809 static struct lra_insn_reg *
810 collect_non_operand_hard_regs (rtx *x, lra_insn_recog_data_t data,
811 struct lra_insn_reg *list,
812 enum op_type type, bool early_clobber)
814 int i, j, regno, last;
815 bool subreg_p;
816 machine_mode mode;
817 struct lra_insn_reg *curr;
818 rtx op = *x;
819 enum rtx_code code = GET_CODE (op);
820 const char *fmt = GET_RTX_FORMAT (code);
822 for (i = 0; i < data->insn_static_data->n_operands; i++)
823 if (x == data->operand_loc[i])
824 /* It is an operand loc. Stop here. */
825 return list;
826 for (i = 0; i < data->insn_static_data->n_dups; i++)
827 if (x == data->dup_loc[i])
828 /* It is a dup loc. Stop here. */
829 return list;
830 mode = GET_MODE (op);
831 subreg_p = false;
832 if (code == SUBREG)
834 op = SUBREG_REG (op);
835 code = GET_CODE (op);
836 if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (op)))
838 mode = GET_MODE (op);
839 if (GET_MODE_SIZE (mode) > REGMODE_NATURAL_SIZE (mode))
840 subreg_p = true;
843 if (REG_P (op))
845 if ((regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER)
846 return list;
847 /* Process all regs even unallocatable ones as we need info
848 about all regs for rematerialization pass. */
849 for (last = regno + hard_regno_nregs[regno][mode];
850 regno < last;
851 regno++)
853 for (curr = list; curr != NULL; curr = curr->next)
854 if (curr->regno == regno && curr->subreg_p == subreg_p
855 && curr->biggest_mode == mode)
857 if (curr->type != type)
858 curr->type = OP_INOUT;
859 if (early_clobber)
861 curr->early_clobber = true;
862 curr->early_clobber_alts = ALL_ALTERNATIVES;
864 break;
866 if (curr == NULL)
868 /* This is a new hard regno or the info can not be
869 integrated into the found structure. */
870 #ifdef STACK_REGS
871 early_clobber
872 = (early_clobber
873 /* This clobber is to inform popping floating
874 point stack only. */
875 && ! (FIRST_STACK_REG <= regno
876 && regno <= LAST_STACK_REG));
877 #endif
878 list = new_insn_reg (data->insn, regno, type, mode, subreg_p,
879 early_clobber,
880 early_clobber ? ALL_ALTERNATIVES : 0, list);
883 return list;
885 switch (code)
887 case SET:
888 list = collect_non_operand_hard_regs (&SET_DEST (op), data,
889 list, OP_OUT, false);
890 list = collect_non_operand_hard_regs (&SET_SRC (op), data,
891 list, OP_IN, false);
892 break;
893 case CLOBBER:
894 /* We treat clobber of non-operand hard registers as early
895 clobber (the behavior is expected from asm). */
896 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
897 list, OP_OUT, true);
898 break;
899 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
900 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
901 list, OP_INOUT, false);
902 break;
903 case PRE_MODIFY: case POST_MODIFY:
904 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
905 list, OP_INOUT, false);
906 list = collect_non_operand_hard_regs (&XEXP (op, 1), data,
907 list, OP_IN, false);
908 break;
909 default:
910 fmt = GET_RTX_FORMAT (code);
911 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
913 if (fmt[i] == 'e')
914 list = collect_non_operand_hard_regs (&XEXP (op, i), data,
915 list, OP_IN, false);
916 else if (fmt[i] == 'E')
917 for (j = XVECLEN (op, i) - 1; j >= 0; j--)
918 list = collect_non_operand_hard_regs (&XVECEXP (op, i, j), data,
919 list, OP_IN, false);
922 return list;
925 /* Set up and return info about INSN. Set up the info if it is not set up
926 yet. */
927 lra_insn_recog_data_t
928 lra_set_insn_recog_data (rtx_insn *insn)
930 lra_insn_recog_data_t data;
931 int i, n, icode;
932 rtx **locs;
933 unsigned int uid = INSN_UID (insn);
934 struct lra_static_insn_data *insn_static_data;
936 check_and_expand_insn_recog_data (uid);
937 if (DEBUG_INSN_P (insn))
938 icode = -1;
939 else
941 icode = INSN_CODE (insn);
942 if (icode < 0)
943 /* It might be a new simple insn which is not recognized yet. */
944 INSN_CODE (insn) = icode = recog_memoized (insn);
946 data = XNEW (struct lra_insn_recog_data);
947 lra_insn_recog_data[uid] = data;
948 data->insn = insn;
949 data->used_insn_alternative = -1;
950 data->icode = icode;
951 data->regs = NULL;
952 if (DEBUG_INSN_P (insn))
954 data->insn_static_data = &debug_insn_static_data;
955 data->dup_loc = NULL;
956 data->arg_hard_regs = NULL;
957 data->preferred_alternatives = ALL_ALTERNATIVES;
958 data->operand_loc = XNEWVEC (rtx *, 1);
959 data->operand_loc[0] = &INSN_VAR_LOCATION_LOC (insn);
960 return data;
962 if (icode < 0)
964 int nop, nalt;
965 machine_mode operand_mode[MAX_RECOG_OPERANDS];
966 const char *constraints[MAX_RECOG_OPERANDS];
968 nop = asm_noperands (PATTERN (insn));
969 data->operand_loc = data->dup_loc = NULL;
970 nalt = 1;
971 if (nop < 0)
973 /* It is a special insn like USE or CLOBBER. We should
974 recognize any regular insn otherwise LRA can do nothing
975 with this insn. */
976 gcc_assert (GET_CODE (PATTERN (insn)) == USE
977 || GET_CODE (PATTERN (insn)) == CLOBBER
978 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
979 data->insn_static_data = insn_static_data
980 = get_static_insn_data (-1, 0, 0, nalt);
982 else
984 /* expand_asm_operands makes sure there aren't too many
985 operands. */
986 lra_assert (nop <= MAX_RECOG_OPERANDS);
987 if (nop != 0)
988 data->operand_loc = XNEWVEC (rtx *, nop);
989 /* Now get the operand values and constraints out of the
990 insn. */
991 decode_asm_operands (PATTERN (insn), NULL,
992 data->operand_loc,
993 constraints, operand_mode, NULL);
994 if (nop > 0)
996 const char *p = recog_data.constraints[0];
998 for (p = constraints[0]; *p; p++)
999 nalt += *p == ',';
1001 data->insn_static_data = insn_static_data
1002 = get_static_insn_data (-1, nop, 0, nalt);
1003 for (i = 0; i < nop; i++)
1005 insn_static_data->operand[i].mode = operand_mode[i];
1006 insn_static_data->operand[i].constraint = constraints[i];
1007 insn_static_data->operand[i].strict_low = false;
1008 insn_static_data->operand[i].is_operator = false;
1009 insn_static_data->operand[i].is_address = false;
1012 for (i = 0; i < insn_static_data->n_operands; i++)
1013 insn_static_data->operand[i].type
1014 = (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1015 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1016 : OP_IN);
1017 data->preferred_alternatives = ALL_ALTERNATIVES;
1018 if (nop > 0)
1020 operand_alternative *op_alt = XCNEWVEC (operand_alternative,
1021 nalt * nop);
1022 preprocess_constraints (nop, nalt, constraints, op_alt);
1023 setup_operand_alternative (data, op_alt);
1026 else
1028 insn_extract (insn);
1029 data->insn_static_data = insn_static_data
1030 = get_static_insn_data (icode, insn_data[icode].n_operands,
1031 insn_data[icode].n_dups,
1032 insn_data[icode].n_alternatives);
1033 n = insn_static_data->n_operands;
1034 if (n == 0)
1035 locs = NULL;
1036 else
1038 locs = XNEWVEC (rtx *, n);
1039 memcpy (locs, recog_data.operand_loc, n * sizeof (rtx *));
1041 data->operand_loc = locs;
1042 n = insn_static_data->n_dups;
1043 if (n == 0)
1044 locs = NULL;
1045 else
1047 locs = XNEWVEC (rtx *, n);
1048 memcpy (locs, recog_data.dup_loc, n * sizeof (rtx *));
1050 data->dup_loc = locs;
1051 data->preferred_alternatives = get_preferred_alternatives (insn);
1052 const operand_alternative *op_alt = preprocess_insn_constraints (icode);
1053 if (!insn_static_data->operand_alternative)
1054 setup_operand_alternative (data, op_alt);
1055 else if (op_alt != insn_static_data->operand_alternative)
1056 insn_static_data->operand_alternative = op_alt;
1058 if (GET_CODE (PATTERN (insn)) == CLOBBER || GET_CODE (PATTERN (insn)) == USE)
1059 insn_static_data->hard_regs = NULL;
1060 else
1061 insn_static_data->hard_regs
1062 = collect_non_operand_hard_regs (&PATTERN (insn), data,
1063 NULL, OP_IN, false);
1064 data->arg_hard_regs = NULL;
1065 if (CALL_P (insn))
1067 bool use_p;
1068 rtx link;
1069 int n_hard_regs, regno, arg_hard_regs[FIRST_PSEUDO_REGISTER];
1071 n_hard_regs = 0;
1072 /* Finding implicit hard register usage. We believe it will be
1073 not changed whatever transformations are used. Call insns
1074 are such example. */
1075 for (link = CALL_INSN_FUNCTION_USAGE (insn);
1076 link != NULL_RTX;
1077 link = XEXP (link, 1))
1078 if (((use_p = GET_CODE (XEXP (link, 0)) == USE)
1079 || GET_CODE (XEXP (link, 0)) == CLOBBER)
1080 && REG_P (XEXP (XEXP (link, 0), 0)))
1082 regno = REGNO (XEXP (XEXP (link, 0), 0));
1083 lra_assert (regno < FIRST_PSEUDO_REGISTER);
1084 /* It is an argument register. */
1085 for (i = REG_NREGS (XEXP (XEXP (link, 0), 0)) - 1; i >= 0; i--)
1086 arg_hard_regs[n_hard_regs++]
1087 = regno + i + (use_p ? 0 : FIRST_PSEUDO_REGISTER);
1089 if (n_hard_regs != 0)
1091 arg_hard_regs[n_hard_regs++] = -1;
1092 data->arg_hard_regs = XNEWVEC (int, n_hard_regs);
1093 memcpy (data->arg_hard_regs, arg_hard_regs,
1094 sizeof (int) * n_hard_regs);
1097 /* Some output operand can be recognized only from the context not
1098 from the constraints which are empty in this case. Call insn may
1099 contain a hard register in set destination with empty constraint
1100 and extract_insn treats them as an input. */
1101 for (i = 0; i < insn_static_data->n_operands; i++)
1103 int j;
1104 rtx pat, set;
1105 struct lra_operand_data *operand = &insn_static_data->operand[i];
1107 /* ??? Should we treat 'X' the same way. It looks to me that
1108 'X' means anything and empty constraint means we do not
1109 care. */
1110 if (operand->type != OP_IN || *operand->constraint != '\0'
1111 || operand->is_operator)
1112 continue;
1113 pat = PATTERN (insn);
1114 if (GET_CODE (pat) == SET)
1116 if (data->operand_loc[i] != &SET_DEST (pat))
1117 continue;
1119 else if (GET_CODE (pat) == PARALLEL)
1121 for (j = XVECLEN (pat, 0) - 1; j >= 0; j--)
1123 set = XVECEXP (PATTERN (insn), 0, j);
1124 if (GET_CODE (set) == SET
1125 && &SET_DEST (set) == data->operand_loc[i])
1126 break;
1128 if (j < 0)
1129 continue;
1131 else
1132 continue;
1133 operand->type = OP_OUT;
1135 return data;
1138 /* Return info about insn give by UID. The info should be already set
1139 up. */
1140 static lra_insn_recog_data_t
1141 get_insn_recog_data_by_uid (int uid)
1143 lra_insn_recog_data_t data;
1145 data = lra_insn_recog_data[uid];
1146 lra_assert (data != NULL);
1147 return data;
1150 /* Invalidate all info about insn given by its UID. */
1151 static void
1152 invalidate_insn_recog_data (int uid)
1154 lra_insn_recog_data_t data;
1156 data = lra_insn_recog_data[uid];
1157 lra_assert (data != NULL);
1158 free_insn_recog_data (data);
1159 lra_insn_recog_data[uid] = NULL;
1162 /* Update all the insn info about INSN. It is usually called when
1163 something in the insn was changed. Return the updated info. */
1164 lra_insn_recog_data_t
1165 lra_update_insn_recog_data (rtx_insn *insn)
1167 lra_insn_recog_data_t data;
1168 int n;
1169 unsigned int uid = INSN_UID (insn);
1170 struct lra_static_insn_data *insn_static_data;
1171 HOST_WIDE_INT sp_offset = 0;
1173 check_and_expand_insn_recog_data (uid);
1174 if ((data = lra_insn_recog_data[uid]) != NULL
1175 && data->icode != INSN_CODE (insn))
1177 sp_offset = data->sp_offset;
1178 invalidate_insn_data_regno_info (data, insn, get_insn_freq (insn));
1179 invalidate_insn_recog_data (uid);
1180 data = NULL;
1182 if (data == NULL)
1184 data = lra_get_insn_recog_data (insn);
1185 /* Initiate or restore SP offset. */
1186 data->sp_offset = sp_offset;
1187 return data;
1189 insn_static_data = data->insn_static_data;
1190 data->used_insn_alternative = -1;
1191 if (DEBUG_INSN_P (insn))
1192 return data;
1193 if (data->icode < 0)
1195 int nop;
1196 machine_mode operand_mode[MAX_RECOG_OPERANDS];
1197 const char *constraints[MAX_RECOG_OPERANDS];
1199 nop = asm_noperands (PATTERN (insn));
1200 if (nop >= 0)
1202 lra_assert (nop == data->insn_static_data->n_operands);
1203 /* Now get the operand values and constraints out of the
1204 insn. */
1205 decode_asm_operands (PATTERN (insn), NULL,
1206 data->operand_loc,
1207 constraints, operand_mode, NULL);
1209 if (flag_checking)
1210 for (int i = 0; i < nop; i++)
1211 lra_assert
1212 (insn_static_data->operand[i].mode == operand_mode[i]
1213 && insn_static_data->operand[i].constraint == constraints[i]
1214 && ! insn_static_data->operand[i].is_operator);
1217 if (flag_checking)
1218 for (int i = 0; i < insn_static_data->n_operands; i++)
1219 lra_assert
1220 (insn_static_data->operand[i].type
1221 == (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1222 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1223 : OP_IN));
1225 else
1227 insn_extract (insn);
1228 n = insn_static_data->n_operands;
1229 if (n != 0)
1230 memcpy (data->operand_loc, recog_data.operand_loc, n * sizeof (rtx *));
1231 n = insn_static_data->n_dups;
1232 if (n != 0)
1233 memcpy (data->dup_loc, recog_data.dup_loc, n * sizeof (rtx *));
1234 lra_assert (check_bool_attrs (insn));
1236 return data;
1239 /* Set up that INSN is using alternative ALT now. */
1240 void
1241 lra_set_used_insn_alternative (rtx_insn *insn, int alt)
1243 lra_insn_recog_data_t data;
1245 data = lra_get_insn_recog_data (insn);
1246 data->used_insn_alternative = alt;
1249 /* Set up that insn with UID is using alternative ALT now. The insn
1250 info should be already set up. */
1251 void
1252 lra_set_used_insn_alternative_by_uid (int uid, int alt)
1254 lra_insn_recog_data_t data;
1256 check_and_expand_insn_recog_data (uid);
1257 data = lra_insn_recog_data[uid];
1258 lra_assert (data != NULL);
1259 data->used_insn_alternative = alt;
1264 /* This page contains code dealing with common register info and
1265 pseudo copies. */
1267 /* The size of the following array. */
1268 static int reg_info_size;
1269 /* Common info about each register. */
1270 struct lra_reg *lra_reg_info;
1272 /* Last register value. */
1273 static int last_reg_value;
1275 /* Return new register value. */
1276 static int
1277 get_new_reg_value (void)
1279 return ++last_reg_value;
1282 /* Vec referring to pseudo copies. */
1283 static vec<lra_copy_t> copy_vec;
1285 /* Initialize I-th element of lra_reg_info. */
1286 static inline void
1287 initialize_lra_reg_info_element (int i)
1289 bitmap_initialize (&lra_reg_info[i].insn_bitmap, &reg_obstack);
1290 #ifdef STACK_REGS
1291 lra_reg_info[i].no_stack_p = false;
1292 #endif
1293 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1294 CLEAR_HARD_REG_SET (lra_reg_info[i].actual_call_used_reg_set);
1295 lra_reg_info[i].preferred_hard_regno1 = -1;
1296 lra_reg_info[i].preferred_hard_regno2 = -1;
1297 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1298 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1299 lra_reg_info[i].biggest_mode = VOIDmode;
1300 lra_reg_info[i].live_ranges = NULL;
1301 lra_reg_info[i].nrefs = lra_reg_info[i].freq = 0;
1302 lra_reg_info[i].last_reload = 0;
1303 lra_reg_info[i].restore_rtx = NULL_RTX;
1304 lra_reg_info[i].val = get_new_reg_value ();
1305 lra_reg_info[i].offset = 0;
1306 lra_reg_info[i].copies = NULL;
1309 /* Initialize common reg info and copies. */
1310 static void
1311 init_reg_info (void)
1313 int i;
1315 last_reg_value = 0;
1316 reg_info_size = max_reg_num () * 3 / 2 + 1;
1317 lra_reg_info = XNEWVEC (struct lra_reg, reg_info_size);
1318 for (i = 0; i < reg_info_size; i++)
1319 initialize_lra_reg_info_element (i);
1320 copy_vec.truncate (0);
1324 /* Finish common reg info and copies. */
1325 static void
1326 finish_reg_info (void)
1328 int i;
1330 for (i = 0; i < reg_info_size; i++)
1331 bitmap_clear (&lra_reg_info[i].insn_bitmap);
1332 free (lra_reg_info);
1333 reg_info_size = 0;
1336 /* Expand common reg info if it is necessary. */
1337 static void
1338 expand_reg_info (void)
1340 int i, old = reg_info_size;
1342 if (reg_info_size > max_reg_num ())
1343 return;
1344 reg_info_size = max_reg_num () * 3 / 2 + 1;
1345 lra_reg_info = XRESIZEVEC (struct lra_reg, lra_reg_info, reg_info_size);
1346 for (i = old; i < reg_info_size; i++)
1347 initialize_lra_reg_info_element (i);
1350 /* Free all copies. */
1351 void
1352 lra_free_copies (void)
1354 lra_copy_t cp;
1356 while (copy_vec.length () != 0)
1358 cp = copy_vec.pop ();
1359 lra_reg_info[cp->regno1].copies = lra_reg_info[cp->regno2].copies = NULL;
1360 lra_copy_pool.remove (cp);
1364 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1365 frequency is FREQ. */
1366 void
1367 lra_create_copy (int regno1, int regno2, int freq)
1369 bool regno1_dest_p;
1370 lra_copy_t cp;
1372 lra_assert (regno1 != regno2);
1373 regno1_dest_p = true;
1374 if (regno1 > regno2)
1376 std::swap (regno1, regno2);
1377 regno1_dest_p = false;
1379 cp = lra_copy_pool.allocate ();
1380 copy_vec.safe_push (cp);
1381 cp->regno1_dest_p = regno1_dest_p;
1382 cp->freq = freq;
1383 cp->regno1 = regno1;
1384 cp->regno2 = regno2;
1385 cp->regno1_next = lra_reg_info[regno1].copies;
1386 lra_reg_info[regno1].copies = cp;
1387 cp->regno2_next = lra_reg_info[regno2].copies;
1388 lra_reg_info[regno2].copies = cp;
1389 if (lra_dump_file != NULL)
1390 fprintf (lra_dump_file, " Creating copy r%d%sr%d@%d\n",
1391 regno1, regno1_dest_p ? "<-" : "->", regno2, freq);
1394 /* Return N-th (0, 1, ...) copy. If there is no copy, return
1395 NULL. */
1396 lra_copy_t
1397 lra_get_copy (int n)
1399 if (n >= (int) copy_vec.length ())
1400 return NULL;
1401 return copy_vec[n];
1406 /* This page contains code dealing with info about registers in
1407 insns. */
1409 /* Process X of insn UID recursively and add info (operand type is
1410 given by TYPE, flag of that it is early clobber is EARLY_CLOBBER)
1411 about registers in X to the insn DATA. If X can be early clobbered,
1412 alternatives in which it can be early clobbered are given by
1413 EARLY_CLOBBER_ALTS. */
1414 static void
1415 add_regs_to_insn_regno_info (lra_insn_recog_data_t data, rtx x, int uid,
1416 enum op_type type, bool early_clobber,
1417 alternative_mask early_clobber_alts)
1419 int i, j, regno;
1420 bool subreg_p;
1421 machine_mode mode;
1422 const char *fmt;
1423 enum rtx_code code;
1424 struct lra_insn_reg *curr;
1426 code = GET_CODE (x);
1427 mode = GET_MODE (x);
1428 subreg_p = false;
1429 if (GET_CODE (x) == SUBREG)
1431 x = SUBREG_REG (x);
1432 code = GET_CODE (x);
1433 if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (x)))
1435 mode = GET_MODE (x);
1436 if (GET_MODE_SIZE (mode) > REGMODE_NATURAL_SIZE (mode))
1437 subreg_p = true;
1440 if (REG_P (x))
1442 regno = REGNO (x);
1443 /* Process all regs even unallocatable ones as we need info about
1444 all regs for rematerialization pass. */
1445 expand_reg_info ();
1446 if (bitmap_set_bit (&lra_reg_info[regno].insn_bitmap, uid))
1448 data->regs = new_insn_reg (data->insn, regno, type, mode, subreg_p,
1449 early_clobber, early_clobber_alts,
1450 data->regs);
1451 return;
1453 else
1455 for (curr = data->regs; curr != NULL; curr = curr->next)
1456 if (curr->regno == regno)
1458 if (curr->subreg_p != subreg_p || curr->biggest_mode != mode)
1459 /* The info can not be integrated into the found
1460 structure. */
1461 data->regs = new_insn_reg (data->insn, regno, type, mode,
1462 subreg_p, early_clobber,
1463 early_clobber_alts, data->regs);
1464 else
1466 if (curr->type != type)
1467 curr->type = OP_INOUT;
1468 if (curr->early_clobber != early_clobber)
1469 curr->early_clobber = true;
1470 curr->early_clobber_alts |= early_clobber_alts;
1472 return;
1474 gcc_unreachable ();
1478 switch (code)
1480 case SET:
1481 add_regs_to_insn_regno_info (data, SET_DEST (x), uid, OP_OUT, false, 0);
1482 add_regs_to_insn_regno_info (data, SET_SRC (x), uid, OP_IN, false, 0);
1483 break;
1484 case CLOBBER:
1485 /* We treat clobber of non-operand hard registers as early
1486 clobber (the behavior is expected from asm). */
1487 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_OUT, true, ALL_ALTERNATIVES);
1488 break;
1489 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
1490 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false, 0);
1491 break;
1492 case PRE_MODIFY: case POST_MODIFY:
1493 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false, 0);
1494 add_regs_to_insn_regno_info (data, XEXP (x, 1), uid, OP_IN, false, 0);
1495 break;
1496 default:
1497 if ((code != PARALLEL && code != EXPR_LIST) || type != OP_OUT)
1498 /* Some targets place small structures in registers for return
1499 values of functions, and those registers are wrapped in
1500 PARALLEL that we may see as the destination of a SET. Here
1501 is an example:
1503 (call_insn 13 12 14 2 (set (parallel:BLK [
1504 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1505 (const_int 0 [0]))
1506 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1507 (const_int 8 [0x8]))
1509 (call (mem:QI (symbol_ref:DI (... */
1510 type = OP_IN;
1511 fmt = GET_RTX_FORMAT (code);
1512 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1514 if (fmt[i] == 'e')
1515 add_regs_to_insn_regno_info (data, XEXP (x, i), uid, type, false, 0);
1516 else if (fmt[i] == 'E')
1518 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1519 add_regs_to_insn_regno_info (data, XVECEXP (x, i, j), uid,
1520 type, false, 0);
1526 /* Return execution frequency of INSN. */
1527 static int
1528 get_insn_freq (rtx_insn *insn)
1530 basic_block bb = BLOCK_FOR_INSN (insn);
1532 gcc_checking_assert (bb != NULL);
1533 return REG_FREQ_FROM_BB (bb);
1536 /* Invalidate all reg info of INSN with DATA and execution frequency
1537 FREQ. Update common info about the invalidated registers. */
1538 static void
1539 invalidate_insn_data_regno_info (lra_insn_recog_data_t data, rtx_insn *insn,
1540 int freq)
1542 int uid;
1543 bool debug_p;
1544 unsigned int i;
1545 struct lra_insn_reg *ir, *next_ir;
1547 uid = INSN_UID (insn);
1548 debug_p = DEBUG_INSN_P (insn);
1549 for (ir = data->regs; ir != NULL; ir = next_ir)
1551 i = ir->regno;
1552 next_ir = ir->next;
1553 lra_insn_reg_pool.remove (ir);
1554 bitmap_clear_bit (&lra_reg_info[i].insn_bitmap, uid);
1555 if (i >= FIRST_PSEUDO_REGISTER && ! debug_p)
1557 lra_reg_info[i].nrefs--;
1558 lra_reg_info[i].freq -= freq;
1559 lra_assert (lra_reg_info[i].nrefs >= 0 && lra_reg_info[i].freq >= 0);
1562 data->regs = NULL;
1565 /* Invalidate all reg info of INSN. Update common info about the
1566 invalidated registers. */
1567 void
1568 lra_invalidate_insn_regno_info (rtx_insn *insn)
1570 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn), insn,
1571 get_insn_freq (insn));
1574 /* Update common reg info from reg info of insn given by its DATA and
1575 execution frequency FREQ. */
1576 static void
1577 setup_insn_reg_info (lra_insn_recog_data_t data, int freq)
1579 unsigned int i;
1580 struct lra_insn_reg *ir;
1582 for (ir = data->regs; ir != NULL; ir = ir->next)
1583 if ((i = ir->regno) >= FIRST_PSEUDO_REGISTER)
1585 lra_reg_info[i].nrefs++;
1586 lra_reg_info[i].freq += freq;
1590 /* Set up insn reg info of INSN. Update common reg info from reg info
1591 of INSN. */
1592 void
1593 lra_update_insn_regno_info (rtx_insn *insn)
1595 int i, uid, freq;
1596 lra_insn_recog_data_t data;
1597 struct lra_static_insn_data *static_data;
1598 enum rtx_code code;
1599 rtx link;
1601 if (! INSN_P (insn))
1602 return;
1603 data = lra_get_insn_recog_data (insn);
1604 static_data = data->insn_static_data;
1605 freq = get_insn_freq (insn);
1606 invalidate_insn_data_regno_info (data, insn, freq);
1607 uid = INSN_UID (insn);
1608 for (i = static_data->n_operands - 1; i >= 0; i--)
1609 add_regs_to_insn_regno_info (data, *data->operand_loc[i], uid,
1610 static_data->operand[i].type,
1611 static_data->operand[i].early_clobber,
1612 static_data->operand[i].early_clobber_alts);
1613 if ((code = GET_CODE (PATTERN (insn))) == CLOBBER || code == USE)
1614 add_regs_to_insn_regno_info (data, XEXP (PATTERN (insn), 0), uid,
1615 code == USE ? OP_IN : OP_OUT, false, 0);
1616 if (CALL_P (insn))
1617 /* On some targets call insns can refer to pseudos in memory in
1618 CALL_INSN_FUNCTION_USAGE list. Process them in order to
1619 consider their occurrences in calls for different
1620 transformations (e.g. inheritance) with given pseudos. */
1621 for (link = CALL_INSN_FUNCTION_USAGE (insn);
1622 link != NULL_RTX;
1623 link = XEXP (link, 1))
1624 if (((code = GET_CODE (XEXP (link, 0))) == USE || code == CLOBBER)
1625 && MEM_P (XEXP (XEXP (link, 0), 0)))
1626 add_regs_to_insn_regno_info (data, XEXP (XEXP (link, 0), 0), uid,
1627 code == USE ? OP_IN : OP_OUT, false, 0);
1628 if (NONDEBUG_INSN_P (insn))
1629 setup_insn_reg_info (data, freq);
1632 /* Return reg info of insn given by it UID. */
1633 struct lra_insn_reg *
1634 lra_get_insn_regs (int uid)
1636 lra_insn_recog_data_t data;
1638 data = get_insn_recog_data_by_uid (uid);
1639 return data->regs;
1644 /* Recursive hash function for RTL X. */
1645 hashval_t
1646 lra_rtx_hash (rtx x)
1648 int i, j;
1649 enum rtx_code code;
1650 const char *fmt;
1651 hashval_t val = 0;
1653 if (x == 0)
1654 return val;
1656 code = GET_CODE (x);
1657 val += (int) code + 4095;
1659 /* Some RTL can be compared nonrecursively. */
1660 switch (code)
1662 case REG:
1663 return val + REGNO (x);
1665 case LABEL_REF:
1666 return iterative_hash_object (XEXP (x, 0), val);
1668 case SYMBOL_REF:
1669 return iterative_hash_object (XSTR (x, 0), val);
1671 case SCRATCH:
1672 case CONST_DOUBLE:
1673 case CONST_INT:
1674 case CONST_VECTOR:
1675 return val;
1677 default:
1678 break;
1681 /* Hash the elements. */
1682 fmt = GET_RTX_FORMAT (code);
1683 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1685 switch (fmt[i])
1687 case 'w':
1688 val += XWINT (x, i);
1689 break;
1691 case 'n':
1692 case 'i':
1693 val += XINT (x, i);
1694 break;
1696 case 'V':
1697 case 'E':
1698 val += XVECLEN (x, i);
1700 for (j = 0; j < XVECLEN (x, i); j++)
1701 val += lra_rtx_hash (XVECEXP (x, i, j));
1702 break;
1704 case 'e':
1705 val += lra_rtx_hash (XEXP (x, i));
1706 break;
1708 case 'S':
1709 case 's':
1710 val += htab_hash_string (XSTR (x, i));
1711 break;
1713 case 'u':
1714 case '0':
1715 case 't':
1716 break;
1718 /* It is believed that rtx's at this level will never
1719 contain anything but integers and other rtx's, except for
1720 within LABEL_REFs and SYMBOL_REFs. */
1721 default:
1722 abort ();
1725 return val;
1730 /* This page contains code dealing with stack of the insns which
1731 should be processed by the next constraint pass. */
1733 /* Bitmap used to put an insn on the stack only in one exemplar. */
1734 static sbitmap lra_constraint_insn_stack_bitmap;
1736 /* The stack itself. */
1737 vec<rtx_insn *> lra_constraint_insn_stack;
1739 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1740 info for INSN, otherwise only update it if INSN is not already on the
1741 stack. */
1742 static inline void
1743 lra_push_insn_1 (rtx_insn *insn, bool always_update)
1745 unsigned int uid = INSN_UID (insn);
1746 if (always_update)
1747 lra_update_insn_regno_info (insn);
1748 if (uid >= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap))
1749 lra_constraint_insn_stack_bitmap =
1750 sbitmap_resize (lra_constraint_insn_stack_bitmap, 3 * uid / 2, 0);
1751 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap, uid))
1752 return;
1753 bitmap_set_bit (lra_constraint_insn_stack_bitmap, uid);
1754 if (! always_update)
1755 lra_update_insn_regno_info (insn);
1756 lra_constraint_insn_stack.safe_push (insn);
1759 /* Put INSN on the stack. */
1760 void
1761 lra_push_insn (rtx_insn *insn)
1763 lra_push_insn_1 (insn, false);
1766 /* Put INSN on the stack and update its reg info. */
1767 void
1768 lra_push_insn_and_update_insn_regno_info (rtx_insn *insn)
1770 lra_push_insn_1 (insn, true);
1773 /* Put insn with UID on the stack. */
1774 void
1775 lra_push_insn_by_uid (unsigned int uid)
1777 lra_push_insn (lra_insn_recog_data[uid]->insn);
1780 /* Take the last-inserted insns off the stack and return it. */
1781 rtx_insn *
1782 lra_pop_insn (void)
1784 rtx_insn *insn = lra_constraint_insn_stack.pop ();
1785 bitmap_clear_bit (lra_constraint_insn_stack_bitmap, INSN_UID (insn));
1786 return insn;
1789 /* Return the current size of the insn stack. */
1790 unsigned int
1791 lra_insn_stack_length (void)
1793 return lra_constraint_insn_stack.length ();
1796 /* Push insns FROM to TO (excluding it) going in reverse order. */
1797 static void
1798 push_insns (rtx_insn *from, rtx_insn *to)
1800 rtx_insn *insn;
1802 if (from == NULL_RTX)
1803 return;
1804 for (insn = from; insn != to; insn = PREV_INSN (insn))
1805 if (INSN_P (insn))
1806 lra_push_insn (insn);
1809 /* Set up sp offset for insn in range [FROM, LAST]. The offset is
1810 taken from the next BB insn after LAST or zero if there in such
1811 insn. */
1812 static void
1813 setup_sp_offset (rtx_insn *from, rtx_insn *last)
1815 rtx_insn *before = next_nonnote_insn_bb (last);
1816 HOST_WIDE_INT offset = (before == NULL_RTX || ! INSN_P (before)
1817 ? 0 : lra_get_insn_recog_data (before)->sp_offset);
1819 for (rtx_insn *insn = from; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
1820 lra_get_insn_recog_data (insn)->sp_offset = offset;
1823 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1824 insns onto the stack. Print about emitting the insns with
1825 TITLE. */
1826 void
1827 lra_process_new_insns (rtx_insn *insn, rtx_insn *before, rtx_insn *after,
1828 const char *title)
1830 rtx_insn *last;
1832 if (before == NULL_RTX && after == NULL_RTX)
1833 return;
1834 if (lra_dump_file != NULL)
1836 dump_insn_slim (lra_dump_file, insn);
1837 if (before != NULL_RTX)
1839 fprintf (lra_dump_file," %s before:\n", title);
1840 dump_rtl_slim (lra_dump_file, before, NULL, -1, 0);
1842 if (after != NULL_RTX)
1844 fprintf (lra_dump_file, " %s after:\n", title);
1845 dump_rtl_slim (lra_dump_file, after, NULL, -1, 0);
1847 fprintf (lra_dump_file, "\n");
1849 if (before != NULL_RTX)
1851 if (cfun->can_throw_non_call_exceptions)
1852 copy_reg_eh_region_note_forward (insn, before, NULL);
1853 emit_insn_before (before, insn);
1854 push_insns (PREV_INSN (insn), PREV_INSN (before));
1855 setup_sp_offset (before, PREV_INSN (insn));
1857 if (after != NULL_RTX)
1859 if (cfun->can_throw_non_call_exceptions)
1860 copy_reg_eh_region_note_forward (insn, after, NULL);
1861 for (last = after; NEXT_INSN (last) != NULL_RTX; last = NEXT_INSN (last))
1863 emit_insn_after (after, insn);
1864 push_insns (last, insn);
1865 setup_sp_offset (after, last);
1867 if (cfun->can_throw_non_call_exceptions)
1869 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1870 if (note && !insn_could_throw_p (insn))
1871 remove_note (insn, note);
1876 /* Replace all references to register OLD_REGNO in *LOC with pseudo
1877 register NEW_REG. Try to simplify subreg of constant if SUBREG_P.
1878 Return true if any change was made. */
1879 bool
1880 lra_substitute_pseudo (rtx *loc, int old_regno, rtx new_reg, bool subreg_p)
1882 rtx x = *loc;
1883 bool result = false;
1884 enum rtx_code code;
1885 const char *fmt;
1886 int i, j;
1888 if (x == NULL_RTX)
1889 return false;
1891 code = GET_CODE (x);
1892 if (code == SUBREG && subreg_p)
1894 rtx subst, inner = SUBREG_REG (x);
1895 /* Transform subreg of constant while we still have inner mode
1896 of the subreg. The subreg internal should not be an insn
1897 operand. */
1898 if (REG_P (inner) && (int) REGNO (inner) == old_regno
1899 && CONSTANT_P (new_reg)
1900 && (subst = simplify_subreg (GET_MODE (x), new_reg, GET_MODE (inner),
1901 SUBREG_BYTE (x))) != NULL_RTX)
1903 *loc = subst;
1904 return true;
1908 else if (code == REG && (int) REGNO (x) == old_regno)
1910 machine_mode mode = GET_MODE (x);
1911 machine_mode inner_mode = GET_MODE (new_reg);
1913 if (mode != inner_mode
1914 && ! (CONST_INT_P (new_reg) && SCALAR_INT_MODE_P (mode)))
1916 if (GET_MODE_SIZE (mode) >= GET_MODE_SIZE (inner_mode)
1917 || ! SCALAR_INT_MODE_P (inner_mode))
1918 new_reg = gen_rtx_SUBREG (mode, new_reg, 0);
1919 else
1920 new_reg = gen_lowpart_SUBREG (mode, new_reg);
1922 *loc = new_reg;
1923 return true;
1926 /* Scan all the operand sub-expressions. */
1927 fmt = GET_RTX_FORMAT (code);
1928 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1930 if (fmt[i] == 'e')
1932 if (lra_substitute_pseudo (&XEXP (x, i), old_regno,
1933 new_reg, subreg_p))
1934 result = true;
1936 else if (fmt[i] == 'E')
1938 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1939 if (lra_substitute_pseudo (&XVECEXP (x, i, j), old_regno,
1940 new_reg, subreg_p))
1941 result = true;
1944 return result;
1947 /* Call lra_substitute_pseudo within an insn. Try to simplify subreg
1948 of constant if SUBREG_P. This won't update the insn ptr, just the
1949 contents of the insn. */
1950 bool
1951 lra_substitute_pseudo_within_insn (rtx_insn *insn, int old_regno,
1952 rtx new_reg, bool subreg_p)
1954 rtx loc = insn;
1955 return lra_substitute_pseudo (&loc, old_regno, new_reg, subreg_p);
1960 /* This page contains code dealing with scratches (changing them onto
1961 pseudos and restoring them from the pseudos).
1963 We change scratches into pseudos at the beginning of LRA to
1964 simplify dealing with them (conflicts, hard register assignments).
1966 If the pseudo denoting scratch was spilled it means that we do need
1967 a hard register for it. Such pseudos are transformed back to
1968 scratches at the end of LRA. */
1970 /* Description of location of a former scratch operand. */
1971 struct sloc
1973 rtx_insn *insn; /* Insn where the scratch was. */
1974 int nop; /* Number of the operand which was a scratch. */
1977 typedef struct sloc *sloc_t;
1979 /* Locations of the former scratches. */
1980 static vec<sloc_t> scratches;
1982 /* Bitmap of scratch regnos. */
1983 static bitmap_head scratch_bitmap;
1985 /* Bitmap of scratch operands. */
1986 static bitmap_head scratch_operand_bitmap;
1988 /* Return true if pseudo REGNO is made of SCRATCH. */
1989 bool
1990 lra_former_scratch_p (int regno)
1992 return bitmap_bit_p (&scratch_bitmap, regno);
1995 /* Return true if the operand NOP of INSN is a former scratch. */
1996 bool
1997 lra_former_scratch_operand_p (rtx_insn *insn, int nop)
1999 return bitmap_bit_p (&scratch_operand_bitmap,
2000 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop) != 0;
2003 /* Register operand NOP in INSN as a former scratch. It will be
2004 changed to scratch back, if it is necessary, at the LRA end. */
2005 void
2006 lra_register_new_scratch_op (rtx_insn *insn, int nop)
2008 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
2009 rtx op = *id->operand_loc[nop];
2010 sloc_t loc = XNEW (struct sloc);
2011 lra_assert (REG_P (op));
2012 loc->insn = insn;
2013 loc->nop = nop;
2014 scratches.safe_push (loc);
2015 bitmap_set_bit (&scratch_bitmap, REGNO (op));
2016 bitmap_set_bit (&scratch_operand_bitmap,
2017 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop);
2018 add_reg_note (insn, REG_UNUSED, op);
2021 /* Change scratches onto pseudos and save their location. */
2022 static void
2023 remove_scratches (void)
2025 int i;
2026 bool insn_changed_p;
2027 basic_block bb;
2028 rtx_insn *insn;
2029 rtx reg;
2030 lra_insn_recog_data_t id;
2031 struct lra_static_insn_data *static_id;
2033 scratches.create (get_max_uid ());
2034 bitmap_initialize (&scratch_bitmap, &reg_obstack);
2035 bitmap_initialize (&scratch_operand_bitmap, &reg_obstack);
2036 FOR_EACH_BB_FN (bb, cfun)
2037 FOR_BB_INSNS (bb, insn)
2038 if (INSN_P (insn))
2040 id = lra_get_insn_recog_data (insn);
2041 static_id = id->insn_static_data;
2042 insn_changed_p = false;
2043 for (i = 0; i < static_id->n_operands; i++)
2044 if (GET_CODE (*id->operand_loc[i]) == SCRATCH
2045 && GET_MODE (*id->operand_loc[i]) != VOIDmode)
2047 insn_changed_p = true;
2048 *id->operand_loc[i] = reg
2049 = lra_create_new_reg (static_id->operand[i].mode,
2050 *id->operand_loc[i], ALL_REGS, NULL);
2051 lra_register_new_scratch_op (insn, i);
2052 if (lra_dump_file != NULL)
2053 fprintf (lra_dump_file,
2054 "Removing SCRATCH in insn #%u (nop %d)\n",
2055 INSN_UID (insn), i);
2057 if (insn_changed_p)
2058 /* Because we might use DF right after caller-saves sub-pass
2059 we need to keep DF info up to date. */
2060 df_insn_rescan (insn);
2064 /* Changes pseudos created by function remove_scratches onto scratches. */
2065 static void
2066 restore_scratches (void)
2068 int regno;
2069 unsigned i;
2070 sloc_t loc;
2071 rtx_insn *last = NULL;
2072 lra_insn_recog_data_t id = NULL;
2074 for (i = 0; scratches.iterate (i, &loc); i++)
2076 /* Ignore already deleted insns. */
2077 if (NOTE_P (loc->insn)
2078 && NOTE_KIND (loc->insn) == NOTE_INSN_DELETED)
2079 continue;
2080 if (last != loc->insn)
2082 last = loc->insn;
2083 id = lra_get_insn_recog_data (last);
2085 if (REG_P (*id->operand_loc[loc->nop])
2086 && ((regno = REGNO (*id->operand_loc[loc->nop]))
2087 >= FIRST_PSEUDO_REGISTER)
2088 && lra_get_regno_hard_regno (regno) < 0)
2090 /* It should be only case when scratch register with chosen
2091 constraint 'X' did not get memory or hard register. */
2092 lra_assert (lra_former_scratch_p (regno));
2093 *id->operand_loc[loc->nop]
2094 = gen_rtx_SCRATCH (GET_MODE (*id->operand_loc[loc->nop]));
2095 lra_update_dup (id, loc->nop);
2096 if (lra_dump_file != NULL)
2097 fprintf (lra_dump_file, "Restoring SCRATCH in insn #%u(nop %d)\n",
2098 INSN_UID (loc->insn), loc->nop);
2101 for (i = 0; scratches.iterate (i, &loc); i++)
2102 free (loc);
2103 scratches.release ();
2104 bitmap_clear (&scratch_bitmap);
2105 bitmap_clear (&scratch_operand_bitmap);
2110 /* Function checks RTL for correctness. If FINAL_P is true, it is
2111 done at the end of LRA and the check is more rigorous. */
2112 static void
2113 check_rtl (bool final_p)
2115 basic_block bb;
2116 rtx_insn *insn;
2118 lra_assert (! final_p || reload_completed);
2119 FOR_EACH_BB_FN (bb, cfun)
2120 FOR_BB_INSNS (bb, insn)
2121 if (NONDEBUG_INSN_P (insn)
2122 && GET_CODE (PATTERN (insn)) != USE
2123 && GET_CODE (PATTERN (insn)) != CLOBBER
2124 && GET_CODE (PATTERN (insn)) != ASM_INPUT)
2126 if (final_p)
2128 extract_constrain_insn (insn);
2129 continue;
2131 /* LRA code is based on assumption that all addresses can be
2132 correctly decomposed. LRA can generate reloads for
2133 decomposable addresses. The decomposition code checks the
2134 correctness of the addresses. So we don't need to check
2135 the addresses here. Don't call insn_invalid_p here, it can
2136 change the code at this stage. */
2137 if (recog_memoized (insn) < 0 && asm_noperands (PATTERN (insn)) < 0)
2138 fatal_insn_not_found (insn);
2142 /* Determine if the current function has an exception receiver block
2143 that reaches the exit block via non-exceptional edges */
2144 static bool
2145 has_nonexceptional_receiver (void)
2147 edge e;
2148 edge_iterator ei;
2149 basic_block *tos, *worklist, bb;
2151 /* If we're not optimizing, then just err on the safe side. */
2152 if (!optimize)
2153 return true;
2155 /* First determine which blocks can reach exit via normal paths. */
2156 tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1);
2158 FOR_EACH_BB_FN (bb, cfun)
2159 bb->flags &= ~BB_REACHABLE;
2161 /* Place the exit block on our worklist. */
2162 EXIT_BLOCK_PTR_FOR_FN (cfun)->flags |= BB_REACHABLE;
2163 *tos++ = EXIT_BLOCK_PTR_FOR_FN (cfun);
2165 /* Iterate: find everything reachable from what we've already seen. */
2166 while (tos != worklist)
2168 bb = *--tos;
2170 FOR_EACH_EDGE (e, ei, bb->preds)
2171 if (e->flags & EDGE_ABNORMAL)
2173 free (worklist);
2174 return true;
2176 else
2178 basic_block src = e->src;
2180 if (!(src->flags & BB_REACHABLE))
2182 src->flags |= BB_REACHABLE;
2183 *tos++ = src;
2187 free (worklist);
2188 /* No exceptional block reached exit unexceptionally. */
2189 return false;
2193 /* Process recursively X of INSN and add REG_INC notes if necessary. */
2194 static void
2195 add_auto_inc_notes (rtx_insn *insn, rtx x)
2197 enum rtx_code code = GET_CODE (x);
2198 const char *fmt;
2199 int i, j;
2201 if (code == MEM && auto_inc_p (XEXP (x, 0)))
2203 add_reg_note (insn, REG_INC, XEXP (XEXP (x, 0), 0));
2204 return;
2207 /* Scan all X sub-expressions. */
2208 fmt = GET_RTX_FORMAT (code);
2209 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2211 if (fmt[i] == 'e')
2212 add_auto_inc_notes (insn, XEXP (x, i));
2213 else if (fmt[i] == 'E')
2214 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2215 add_auto_inc_notes (insn, XVECEXP (x, i, j));
2220 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2221 We change pseudos by hard registers without notification of DF and
2222 that can make the notes obsolete. DF-infrastructure does not deal
2223 with REG_INC notes -- so we should regenerate them here. */
2224 static void
2225 update_inc_notes (void)
2227 rtx *pnote;
2228 basic_block bb;
2229 rtx_insn *insn;
2231 FOR_EACH_BB_FN (bb, cfun)
2232 FOR_BB_INSNS (bb, insn)
2233 if (NONDEBUG_INSN_P (insn))
2235 pnote = &REG_NOTES (insn);
2236 while (*pnote != 0)
2238 if (REG_NOTE_KIND (*pnote) == REG_DEAD
2239 || REG_NOTE_KIND (*pnote) == REG_UNUSED
2240 || REG_NOTE_KIND (*pnote) == REG_INC)
2241 *pnote = XEXP (*pnote, 1);
2242 else
2243 pnote = &XEXP (*pnote, 1);
2246 if (AUTO_INC_DEC)
2247 add_auto_inc_notes (insn, PATTERN (insn));
2251 /* Set to 1 while in lra. */
2252 int lra_in_progress;
2254 /* Start of pseudo regnos before the LRA. */
2255 int lra_new_regno_start;
2257 /* Start of reload pseudo regnos before the new spill pass. */
2258 int lra_constraint_new_regno_start;
2260 /* Avoid spilling pseudos with regno more than the following value if
2261 it is possible. */
2262 int lra_bad_spill_regno_start;
2264 /* Inheritance pseudo regnos before the new spill pass. */
2265 bitmap_head lra_inheritance_pseudos;
2267 /* Split regnos before the new spill pass. */
2268 bitmap_head lra_split_regs;
2270 /* Reload pseudo regnos before the new assignment pass which still can
2271 be spilled after the assignment pass as memory is also accepted in
2272 insns for the reload pseudos. */
2273 bitmap_head lra_optional_reload_pseudos;
2275 /* Pseudo regnos used for subreg reloads before the new assignment
2276 pass. Such pseudos still can be spilled after the assignment
2277 pass. */
2278 bitmap_head lra_subreg_reload_pseudos;
2280 /* File used for output of LRA debug information. */
2281 FILE *lra_dump_file;
2283 /* True if we should try spill into registers of different classes
2284 instead of memory. */
2285 bool lra_reg_spill_p;
2287 /* Set up value LRA_REG_SPILL_P. */
2288 static void
2289 setup_reg_spill_flag (void)
2291 int cl, mode;
2293 if (targetm.spill_class != NULL)
2294 for (cl = 0; cl < (int) LIM_REG_CLASSES; cl++)
2295 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
2296 if (targetm.spill_class ((enum reg_class) cl,
2297 (machine_mode) mode) != NO_REGS)
2299 lra_reg_spill_p = true;
2300 return;
2302 lra_reg_spill_p = false;
2305 /* True if the current function is too big to use regular algorithms
2306 in LRA. In other words, we should use simpler and faster algorithms
2307 in LRA. It also means we should not worry about generation code
2308 for caller saves. The value is set up in IRA. */
2309 bool lra_simple_p;
2311 /* Major LRA entry function. F is a file should be used to dump LRA
2312 debug info. */
2313 void
2314 lra (FILE *f)
2316 int i;
2317 bool live_p, inserted_p;
2319 lra_dump_file = f;
2321 timevar_push (TV_LRA);
2323 /* Make sure that the last insn is a note. Some subsequent passes
2324 need it. */
2325 emit_note (NOTE_INSN_DELETED);
2327 COPY_HARD_REG_SET (lra_no_alloc_regs, ira_no_alloc_regs);
2329 init_reg_info ();
2330 expand_reg_info ();
2332 init_insn_recog_data ();
2334 /* Some quick check on RTL generated by previous passes. */
2335 if (flag_checking)
2336 check_rtl (false);
2338 lra_in_progress = 1;
2340 lra_live_range_iter = lra_coalesce_iter = lra_constraint_iter = 0;
2341 lra_assignment_iter = lra_assignment_iter_after_spill = 0;
2342 lra_inheritance_iter = lra_undo_inheritance_iter = 0;
2343 lra_rematerialization_iter = 0;
2345 setup_reg_spill_flag ();
2347 /* Function remove_scratches can creates new pseudos for clobbers --
2348 so set up lra_constraint_new_regno_start before its call to
2349 permit changing reg classes for pseudos created by this
2350 simplification. */
2351 lra_constraint_new_regno_start = lra_new_regno_start = max_reg_num ();
2352 lra_bad_spill_regno_start = INT_MAX;
2353 remove_scratches ();
2355 /* A function that has a non-local label that can reach the exit
2356 block via non-exceptional paths must save all call-saved
2357 registers. */
2358 if (cfun->has_nonlocal_label && has_nonexceptional_receiver ())
2359 crtl->saves_all_registers = 1;
2361 if (crtl->saves_all_registers)
2362 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2363 if (! call_used_regs[i] && ! fixed_regs[i] && ! LOCAL_REGNO (i))
2364 df_set_regs_ever_live (i, true);
2366 /* We don't DF from now and avoid its using because it is to
2367 expensive when a lot of RTL changes are made. */
2368 df_set_flags (DF_NO_INSN_RESCAN);
2369 lra_constraint_insn_stack.create (get_max_uid ());
2370 lra_constraint_insn_stack_bitmap = sbitmap_alloc (get_max_uid ());
2371 bitmap_clear (lra_constraint_insn_stack_bitmap);
2372 lra_live_ranges_init ();
2373 lra_constraints_init ();
2374 lra_curr_reload_num = 0;
2375 push_insns (get_last_insn (), NULL);
2376 /* It is needed for the 1st coalescing. */
2377 bitmap_initialize (&lra_inheritance_pseudos, &reg_obstack);
2378 bitmap_initialize (&lra_split_regs, &reg_obstack);
2379 bitmap_initialize (&lra_optional_reload_pseudos, &reg_obstack);
2380 bitmap_initialize (&lra_subreg_reload_pseudos, &reg_obstack);
2381 live_p = false;
2382 if (get_frame_size () != 0 && crtl->stack_alignment_needed)
2383 /* If we have a stack frame, we must align it now. The stack size
2384 may be a part of the offset computation for register
2385 elimination. */
2386 assign_stack_local (BLKmode, 0, crtl->stack_alignment_needed);
2387 lra_init_equiv ();
2388 for (;;)
2390 for (;;)
2392 bool reloads_p = lra_constraints (lra_constraint_iter == 0);
2393 /* Constraint transformations may result in that eliminable
2394 hard regs become uneliminable and pseudos which use them
2395 should be spilled. It is better to do it before pseudo
2396 assignments.
2398 For example, rs6000 can make
2399 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2400 to use a constant pool. */
2401 lra_eliminate (false, false);
2402 /* We should try to assign hard registers to scratches even
2403 if there were no RTL transformations in lra_constraints.
2404 Also we should check IRA assignments on the first
2405 iteration as they can be wrong because of early clobbers
2406 operands which are ignored in IRA. */
2407 if (! reloads_p && lra_constraint_iter > 1)
2409 /* Stack is not empty here only when there are changes
2410 during the elimination sub-pass. */
2411 if (bitmap_empty_p (lra_constraint_insn_stack_bitmap))
2412 break;
2413 else
2414 /* If there are no reloads but changing due
2415 elimination, restart the constraint sub-pass
2416 first. */
2417 continue;
2419 /* Do inheritance only for regular algorithms. */
2420 if (! lra_simple_p)
2422 if (flag_ipa_ra)
2424 if (live_p)
2425 lra_clear_live_ranges ();
2426 /* As a side-effect of lra_create_live_ranges, we calculate
2427 actual_call_used_reg_set, which is needed during
2428 lra_inheritance. */
2429 lra_create_live_ranges (true, true);
2430 live_p = true;
2432 lra_inheritance ();
2434 if (live_p)
2435 lra_clear_live_ranges ();
2436 /* We need live ranges for lra_assign -- so build them. But
2437 don't remove dead insns or change global live info as we
2438 can undo inheritance transformations after inheritance
2439 pseudo assigning. */
2440 lra_create_live_ranges (true, false);
2441 live_p = true;
2442 /* If we don't spill non-reload and non-inheritance pseudos,
2443 there is no sense to run memory-memory move coalescing.
2444 If inheritance pseudos were spilled, the memory-memory
2445 moves involving them will be removed by pass undoing
2446 inheritance. */
2447 if (lra_simple_p)
2448 lra_assign ();
2449 else
2451 bool spill_p = !lra_assign ();
2453 if (lra_undo_inheritance ())
2454 live_p = false;
2455 if (spill_p)
2457 if (! live_p)
2459 lra_create_live_ranges (true, true);
2460 live_p = true;
2462 if (lra_coalesce ())
2463 live_p = false;
2465 if (! live_p)
2466 lra_clear_live_ranges ();
2469 /* Don't clear optional reloads bitmap until all constraints are
2470 satisfied as we need to differ them from regular reloads. */
2471 bitmap_clear (&lra_optional_reload_pseudos);
2472 bitmap_clear (&lra_subreg_reload_pseudos);
2473 bitmap_clear (&lra_inheritance_pseudos);
2474 bitmap_clear (&lra_split_regs);
2475 if (! live_p)
2477 /* We need full live info for spilling pseudos into
2478 registers instead of memory. */
2479 lra_create_live_ranges (lra_reg_spill_p, true);
2480 live_p = true;
2482 /* We should check necessity for spilling here as the above live
2483 range pass can remove spilled pseudos. */
2484 if (! lra_need_for_spills_p ())
2485 break;
2486 /* Now we know what pseudos should be spilled. Try to
2487 rematerialize them first. */
2488 if (lra_remat ())
2490 /* We need full live info -- see the comment above. */
2491 lra_create_live_ranges (lra_reg_spill_p, true);
2492 live_p = true;
2493 if (! lra_need_for_spills_p ())
2494 break;
2496 lra_spill ();
2497 /* Assignment of stack slots changes elimination offsets for
2498 some eliminations. So update the offsets here. */
2499 lra_eliminate (false, false);
2500 lra_constraint_new_regno_start = max_reg_num ();
2501 if (lra_bad_spill_regno_start == INT_MAX
2502 && lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES
2503 && lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
2504 /* After switching off inheritance and rematerialization
2505 passes, avoid spilling reload pseudos will be created to
2506 prevent LRA cycling in some complicated cases. */
2507 lra_bad_spill_regno_start = lra_constraint_new_regno_start;
2508 lra_assignment_iter_after_spill = 0;
2510 restore_scratches ();
2511 lra_eliminate (true, false);
2512 lra_final_code_change ();
2513 lra_in_progress = 0;
2514 if (live_p)
2515 lra_clear_live_ranges ();
2516 lra_live_ranges_finish ();
2517 lra_constraints_finish ();
2518 finish_reg_info ();
2519 sbitmap_free (lra_constraint_insn_stack_bitmap);
2520 lra_constraint_insn_stack.release ();
2521 finish_insn_recog_data ();
2522 regstat_free_n_sets_and_refs ();
2523 regstat_free_ri ();
2524 reload_completed = 1;
2525 update_inc_notes ();
2527 inserted_p = fixup_abnormal_edges ();
2529 /* We've possibly turned single trapping insn into multiple ones. */
2530 if (cfun->can_throw_non_call_exceptions)
2532 auto_sbitmap blocks (last_basic_block_for_fn (cfun));
2533 bitmap_ones (blocks);
2534 find_many_sub_basic_blocks (blocks);
2537 if (inserted_p)
2538 commit_edge_insertions ();
2540 /* Replacing pseudos with their memory equivalents might have
2541 created shared rtx. Subsequent passes would get confused
2542 by this, so unshare everything here. */
2543 unshare_all_rtl_again (get_insns ());
2545 if (flag_checking)
2546 check_rtl (true);
2548 timevar_pop (TV_LRA);
2551 /* Called once per compiler to initialize LRA data once. */
2552 void
2553 lra_init_once (void)
2555 init_insn_code_data_once ();
2558 /* Called once per compiler to finish LRA data which are initialize
2559 once. */
2560 void
2561 lra_finish_once (void)
2563 finish_insn_code_data_once ();