2013-05-03 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / lra.c
blob7c6bff15b8b3eb1c94d41ab5965b331639806ba5
1 /* LRA (local register allocator) driver and LRA utilities.
2 Copyright (C) 2010-2013 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 Changing spilled pseudos to stack memory or their equivalences;
41 o Allocation stack memory changes the address displacement and
42 new iteration is needed.
44 Here is block diagram of LRA passes:
46 ---------------------
47 --------------- | Undo inheritance | ---------------
48 | Memory-memory | | for spilled pseudos)| | New (and old) |
49 | move coalesce |<---| and splits (for |<-- | pseudos |
50 --------------- | pseudos got the | | assignment |
51 Start | | same hard regs) | ---------------
52 | | --------------------- ^
53 V | ---------------- |
54 ----------- V | Update virtual | |
55 | Remove |----> ------------>| register | |
56 | scratches | ^ | displacements | |
57 ----------- | ---------------- |
58 | | |
59 | V New |
60 ---------------- No ------------ pseudos -------------------
61 | Spilled pseudo | change |Constraints:| or insns | Inheritance/split |
62 | to memory |<-------| RTL |--------->| transformations |
63 | substitution | | transfor- | | in EBB scope |
64 ---------------- | mations | -------------------
65 | ------------
67 -------------------------
68 | Hard regs substitution, |
69 | devirtalization, and |------> Finish
70 | restoring scratches got |
71 | memory |
72 -------------------------
74 To speed up the process:
75 o We process only insns affected by changes on previous
76 iterations;
77 o We don't use DFA-infrastructure because it results in much slower
78 compiler speed than a special IR described below does;
79 o We use a special insn representation for quick access to insn
80 info which is always *synchronized* with the current RTL;
81 o Insn IR is minimized by memory. It is divided on three parts:
82 o one specific for each insn in RTL (only operand locations);
83 o one common for all insns in RTL with the same insn code
84 (different operand attributes from machine descriptions);
85 o one oriented for maintenance of live info (list of pseudos).
86 o Pseudo data:
87 o all insns where the pseudo is referenced;
88 o live info (conflicting hard regs, live ranges, # of
89 references etc);
90 o data used for assigning (preferred hard regs, costs etc).
92 This file contains LRA driver, LRA utility functions and data, and
93 code for dealing with scratches. */
95 #include "config.h"
96 #include "system.h"
97 #include "coretypes.h"
98 #include "tm.h"
99 #include "hard-reg-set.h"
100 #include "rtl.h"
101 #include "tm_p.h"
102 #include "regs.h"
103 #include "insn-config.h"
104 #include "insn-codes.h"
105 #include "recog.h"
106 #include "output.h"
107 #include "addresses.h"
108 #include "flags.h"
109 #include "function.h"
110 #include "expr.h"
111 #include "basic-block.h"
112 #include "except.h"
113 #include "tree-pass.h"
114 #include "timevar.h"
115 #include "target.h"
116 #include "vec.h"
117 #include "ira.h"
118 #include "lra-int.h"
119 #include "df.h"
121 /* Hard registers currently not available for allocation. It can
122 changed after some hard registers become not eliminable. */
123 HARD_REG_SET lra_no_alloc_regs;
125 static int get_new_reg_value (void);
126 static void expand_reg_info (void);
127 static void invalidate_insn_recog_data (int);
128 static int get_insn_freq (rtx);
129 static void invalidate_insn_data_regno_info (lra_insn_recog_data_t, rtx, int);
131 /* Expand all regno related info needed for LRA. */
132 static void
133 expand_reg_data (void)
135 resize_reg_info ();
136 expand_reg_info ();
137 ira_expand_reg_equiv ();
140 /* Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL
141 or of VOIDmode, use MD_MODE for the new reg. Initialize its
142 register class to RCLASS. Print message about assigning class
143 RCLASS containing new register name TITLE unless it is NULL. Use
144 attributes of ORIGINAL if it is a register. The created register
145 will have unique held value. */
147 lra_create_new_reg_with_unique_value (enum machine_mode md_mode, rtx original,
148 enum reg_class rclass, const char *title)
150 enum machine_mode mode;
151 rtx new_reg;
153 if (original == NULL_RTX || (mode = GET_MODE (original)) == VOIDmode)
154 mode = md_mode;
155 lra_assert (mode != VOIDmode);
156 new_reg = gen_reg_rtx (mode);
157 if (original == NULL_RTX || ! REG_P (original))
159 if (lra_dump_file != NULL)
160 fprintf (lra_dump_file, " Creating newreg=%i", REGNO (new_reg));
162 else
164 if (ORIGINAL_REGNO (original) >= FIRST_PSEUDO_REGISTER)
165 ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original);
166 REG_USERVAR_P (new_reg) = REG_USERVAR_P (original);
167 REG_POINTER (new_reg) = REG_POINTER (original);
168 REG_ATTRS (new_reg) = REG_ATTRS (original);
169 if (lra_dump_file != NULL)
170 fprintf (lra_dump_file, " Creating newreg=%i from oldreg=%i",
171 REGNO (new_reg), REGNO (original));
173 if (lra_dump_file != NULL)
175 if (title != NULL)
176 fprintf (lra_dump_file, ", assigning class %s to%s%s r%d",
177 reg_class_names[rclass], *title == '\0' ? "" : " ",
178 title, REGNO (new_reg));
179 fprintf (lra_dump_file, "\n");
181 expand_reg_data ();
182 setup_reg_classes (REGNO (new_reg), rclass, NO_REGS, rclass);
183 return new_reg;
186 /* Analogous to the previous function but also inherits value of
187 ORIGINAL. */
189 lra_create_new_reg (enum machine_mode md_mode, rtx original,
190 enum reg_class rclass, const char *title)
192 rtx new_reg;
194 new_reg
195 = lra_create_new_reg_with_unique_value (md_mode, original, rclass, title);
196 if (original != NULL_RTX && REG_P (original))
197 lra_assign_reg_val (REGNO (original), REGNO (new_reg));
198 return new_reg;
201 /* Set up for REGNO unique hold value. */
202 void
203 lra_set_regno_unique_value (int regno)
205 lra_reg_info[regno].val = get_new_reg_value ();
208 /* Invalidate INSN related info used by LRA. */
209 void
210 lra_invalidate_insn_data (rtx insn)
212 lra_invalidate_insn_regno_info (insn);
213 invalidate_insn_recog_data (INSN_UID (insn));
216 /* Mark INSN deleted and invalidate the insn related info used by
217 LRA. */
218 void
219 lra_set_insn_deleted (rtx insn)
221 lra_invalidate_insn_data (insn);
222 SET_INSN_DELETED (insn);
225 /* Delete an unneeded INSN and any previous insns who sole purpose is
226 loading data that is dead in INSN. */
227 void
228 lra_delete_dead_insn (rtx insn)
230 rtx prev = prev_real_insn (insn);
231 rtx prev_dest;
233 /* If the previous insn sets a register that dies in our insn,
234 delete it too. */
235 if (prev && GET_CODE (PATTERN (prev)) == SET
236 && (prev_dest = SET_DEST (PATTERN (prev)), REG_P (prev_dest))
237 && reg_mentioned_p (prev_dest, PATTERN (insn))
238 && find_regno_note (insn, REG_DEAD, REGNO (prev_dest))
239 && ! side_effects_p (SET_SRC (PATTERN (prev))))
240 lra_delete_dead_insn (prev);
242 lra_set_insn_deleted (insn);
245 /* Target checks operands through operand predicates to recognize an
246 insn. We should have a special precaution to generate add insns
247 which are frequent results of elimination.
249 Emit insns for x = y + z. X can be used to store intermediate
250 values and should be not in Y and Z when we use X to store an
251 intermediate value. Y + Z should form [base] [+ index[ * scale]] [
252 + disp] where base and index are registers, disp and scale are
253 constants. Y should contain base if it is present, Z should
254 contain disp if any. index[*scale] can be part of Y or Z. */
255 void
256 lra_emit_add (rtx x, rtx y, rtx z)
258 int old;
259 rtx insn, last;
260 rtx a1, a2, base, index, disp, scale, index_scale;
261 bool ok_p;
263 insn = gen_add3_insn (x, y, z);
264 old = max_reg_num ();
265 if (insn != NULL_RTX)
266 emit_insn (insn);
267 else
269 disp = a2 = NULL_RTX;
270 if (GET_CODE (y) == PLUS)
272 a1 = XEXP (y, 0);
273 a2 = XEXP (y, 1);
274 disp = z;
276 else
278 a1 = y;
279 if (CONSTANT_P (z))
280 disp = z;
281 else
282 a2 = z;
284 index_scale = scale = NULL_RTX;
285 if (GET_CODE (a1) == MULT)
287 index_scale = a1;
288 index = XEXP (a1, 0);
289 scale = XEXP (a1, 1);
290 base = a2;
292 else if (a2 != NULL_RTX && GET_CODE (a2) == MULT)
294 index_scale = a2;
295 index = XEXP (a2, 0);
296 scale = XEXP (a2, 1);
297 base = a1;
299 else
301 base = a1;
302 index = a2;
304 if (! REG_P (base)
305 || (index != NULL_RTX && ! REG_P (index))
306 || (disp != NULL_RTX && ! CONSTANT_P (disp))
307 || (scale != NULL_RTX && ! CONSTANT_P (scale)))
309 /* Its is not an address generation. Probably we have no 3 op
310 add. Last chance is to use 2-op add insn. */
311 lra_assert (x != y && x != z);
312 emit_move_insn (x, z);
313 insn = gen_add2_insn (x, y);
314 emit_insn (insn);
316 else
318 if (index_scale == NULL_RTX)
319 index_scale = index;
320 if (disp == NULL_RTX)
322 /* Generate x = index_scale; x = x + base. */
323 lra_assert (index_scale != NULL_RTX && base != NULL_RTX);
324 emit_move_insn (x, index_scale);
325 insn = gen_add2_insn (x, base);
326 emit_insn (insn);
328 else if (scale == NULL_RTX)
330 /* Try x = base + disp. */
331 lra_assert (base != NULL_RTX);
332 last = get_last_insn ();
333 insn = emit_move_insn (x, gen_rtx_PLUS (GET_MODE (base),
334 base, disp));
335 if (recog_memoized (insn) < 0)
337 delete_insns_since (last);
338 /* Generate x = disp; x = x + base. */
339 emit_move_insn (x, disp);
340 insn = gen_add2_insn (x, base);
341 emit_insn (insn);
343 /* Generate x = x + index. */
344 if (index != NULL_RTX)
346 insn = gen_add2_insn (x, index);
347 emit_insn (insn);
350 else
352 /* Try x = index_scale; x = x + disp; x = x + base. */
353 last = get_last_insn ();
354 insn = emit_move_insn (x, index_scale);
355 ok_p = false;
356 if (recog_memoized (insn) >= 0)
358 insn = gen_add2_insn (x, disp);
359 if (insn != NULL_RTX)
361 emit_insn (insn);
362 insn = gen_add2_insn (x, disp);
363 if (insn != NULL_RTX)
365 emit_insn (insn);
366 ok_p = true;
370 if (! ok_p)
372 delete_insns_since (last);
373 /* Generate x = disp; x = x + base; x = x + index_scale. */
374 emit_move_insn (x, disp);
375 insn = gen_add2_insn (x, base);
376 emit_insn (insn);
377 insn = gen_add2_insn (x, index_scale);
378 emit_insn (insn);
383 /* Functions emit_... can create pseudos -- so expand the pseudo
384 data. */
385 if (old != max_reg_num ())
386 expand_reg_data ();
389 /* The number of emitted reload insns so far. */
390 int lra_curr_reload_num;
392 /* Emit x := y, processing special case when y = u + v or y = u + v *
393 scale + w through emit_add (Y can be an address which is base +
394 index reg * scale + displacement in general case). X may be used
395 as intermediate result therefore it should be not in Y. */
396 void
397 lra_emit_move (rtx x, rtx y)
399 int old;
401 if (GET_CODE (y) != PLUS)
403 if (rtx_equal_p (x, y))
404 return;
405 old = max_reg_num ();
406 emit_move_insn (x, y);
407 if (REG_P (x))
408 lra_reg_info[ORIGINAL_REGNO (x)].last_reload = ++lra_curr_reload_num;
409 /* Function emit_move can create pseudos -- so expand the pseudo
410 data. */
411 if (old != max_reg_num ())
412 expand_reg_data ();
413 return;
415 lra_emit_add (x, XEXP (y, 0), XEXP (y, 1));
418 /* Update insn operands which are duplication of operands whose
419 numbers are in array of NOPS (with end marker -1). The insn is
420 represented by its LRA internal representation ID. */
421 void
422 lra_update_dups (lra_insn_recog_data_t id, signed char *nops)
424 int i, j, nop;
425 struct lra_static_insn_data *static_id = id->insn_static_data;
427 for (i = 0; i < static_id->n_dups; i++)
428 for (j = 0; (nop = nops[j]) >= 0; j++)
429 if (static_id->dup_num[i] == nop)
430 *id->dup_loc[i] = *id->operand_loc[nop];
435 /* This page contains code dealing with info about registers in the
436 insns. */
438 /* Pools for insn reg info. */
439 static alloc_pool insn_reg_pool;
441 /* Initiate pool for insn reg info. */
442 static void
443 init_insn_regs (void)
445 insn_reg_pool
446 = create_alloc_pool ("insn regs", sizeof (struct lra_insn_reg), 100);
449 /* Create LRA insn related info about referenced REGNO with TYPE
450 (in/out/inout), biggest reference mode MODE, flag that it is
451 reference through subreg (SUBREG_P), flag that is early clobbered
452 in the insn (EARLY_CLOBBER), and reference to the next insn reg
453 info (NEXT). */
454 static struct lra_insn_reg *
455 new_insn_reg (int regno, enum op_type type, enum machine_mode mode,
456 bool subreg_p, bool early_clobber, struct lra_insn_reg *next)
458 struct lra_insn_reg *ir;
460 ir = (struct lra_insn_reg *) pool_alloc (insn_reg_pool);
461 ir->type = type;
462 ir->biggest_mode = mode;
463 if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (lra_reg_info[regno].biggest_mode))
464 lra_reg_info[regno].biggest_mode = mode;
465 ir->subreg_p = subreg_p;
466 ir->early_clobber = early_clobber;
467 ir->regno = regno;
468 ir->next = next;
469 return ir;
472 /* Free insn reg info IR. */
473 static void
474 free_insn_reg (struct lra_insn_reg *ir)
476 pool_free (insn_reg_pool, ir);
479 /* Free insn reg info list IR. */
480 static void
481 free_insn_regs (struct lra_insn_reg *ir)
483 struct lra_insn_reg *next_ir;
485 for (; ir != NULL; ir = next_ir)
487 next_ir = ir->next;
488 free_insn_reg (ir);
492 /* Finish pool for insn reg info. */
493 static void
494 finish_insn_regs (void)
496 free_alloc_pool (insn_reg_pool);
501 /* This page contains code dealing LRA insn info (or in other words
502 LRA internal insn representation). */
504 struct target_lra_int default_target_lra_int;
505 #if SWITCHABLE_TARGET
506 struct target_lra_int *this_target_lra_int = &default_target_lra_int;
507 #endif
509 /* Map INSN_CODE -> the static insn data. This info is valid during
510 all translation unit. */
511 struct lra_static_insn_data *insn_code_data[LAST_INSN_CODE];
513 /* Debug insns are represented as a special insn with one input
514 operand which is RTL expression in var_location. */
516 /* The following data are used as static insn operand data for all
517 debug insns. If structure lra_operand_data is changed, the
518 initializer should be changed too. */
519 static struct lra_operand_data debug_operand_data =
521 NULL, /* alternative */
522 VOIDmode, /* We are not interesting in the operand mode. */
523 OP_IN,
524 0, 0, 0, 0
527 /* The following data are used as static insn data for all debug
528 insns. If structure lra_static_insn_data is changed, the
529 initializer should be changed too. */
530 static struct lra_static_insn_data debug_insn_static_data =
532 &debug_operand_data,
533 0, /* Duplication operands #. */
534 -1, /* Commutative operand #. */
535 1, /* Operands #. There is only one operand which is debug RTL
536 expression. */
537 0, /* Duplications #. */
538 0, /* Alternatives #. We are not interesting in alternatives
539 because we does not proceed debug_insns for reloads. */
540 NULL, /* Hard registers referenced in machine description. */
541 NULL /* Descriptions of operands in alternatives. */
544 /* Called once per compiler work to initialize some LRA data related
545 to insns. */
546 static void
547 init_insn_code_data_once (void)
549 memset (insn_code_data, 0, sizeof (insn_code_data));
550 memset (op_alt_data, 0, sizeof (op_alt_data));
553 /* Called once per compiler work to finalize some LRA data related to
554 insns. */
555 static void
556 finish_insn_code_data_once (void)
558 int i;
560 for (i = 0; i < LAST_INSN_CODE; i++)
562 if (insn_code_data[i] != NULL)
563 free (insn_code_data[i]);
564 if (op_alt_data[i] != NULL)
565 free (op_alt_data[i]);
569 /* Initialize LRA info about operands in insn alternatives. */
570 static void
571 init_op_alt_data (void)
573 int i;
575 for (i = 0; i < LAST_INSN_CODE; i++)
576 if (op_alt_data[i] != NULL)
578 free (op_alt_data[i]);
579 op_alt_data[i] = NULL;
583 /* Return static insn data, allocate and setup if necessary. Although
584 dup_num is static data (it depends only on icode), to set it up we
585 need to extract insn first. So recog_data should be valid for
586 normal insn (ICODE >= 0) before the call. */
587 static struct lra_static_insn_data *
588 get_static_insn_data (int icode, int nop, int ndup, int nalt)
590 struct lra_static_insn_data *data;
591 size_t n_bytes;
593 lra_assert (icode < LAST_INSN_CODE);
594 if (icode >= 0 && (data = insn_code_data[icode]) != NULL)
595 return data;
596 lra_assert (nop >= 0 && ndup >= 0 && nalt >= 0);
597 n_bytes = sizeof (struct lra_static_insn_data)
598 + sizeof (struct lra_operand_data) * nop
599 + sizeof (int) * ndup;
600 data = XNEWVAR (struct lra_static_insn_data, n_bytes);
601 data->n_operands = nop;
602 data->n_dups = ndup;
603 data->n_alternatives = nalt;
604 data->operand = ((struct lra_operand_data *)
605 ((char *) data + sizeof (struct lra_static_insn_data)));
606 data->dup_num = ((int *) ((char *) data->operand
607 + sizeof (struct lra_operand_data) * nop));
608 if (icode >= 0)
610 int i;
612 insn_code_data[icode] = data;
613 for (i = 0; i < nop; i++)
615 data->operand[i].constraint
616 = insn_data[icode].operand[i].constraint;
617 data->operand[i].mode = insn_data[icode].operand[i].mode;
618 data->operand[i].strict_low = insn_data[icode].operand[i].strict_low;
619 data->operand[i].is_operator
620 = insn_data[icode].operand[i].is_operator;
621 data->operand[i].type
622 = (data->operand[i].constraint[0] == '=' ? OP_OUT
623 : data->operand[i].constraint[0] == '+' ? OP_INOUT
624 : OP_IN);
625 data->operand[i].is_address = false;
627 for (i = 0; i < ndup; i++)
628 data->dup_num[i] = recog_data.dup_num[i];
630 return data;
633 /* The current length of the following array. */
634 int lra_insn_recog_data_len;
636 /* Map INSN_UID -> the insn recog data (NULL if unknown). */
637 lra_insn_recog_data_t *lra_insn_recog_data;
639 /* Initialize LRA data about insns. */
640 static void
641 init_insn_recog_data (void)
643 lra_insn_recog_data_len = 0;
644 lra_insn_recog_data = NULL;
645 init_insn_regs ();
648 /* Expand, if necessary, LRA data about insns. */
649 static void
650 check_and_expand_insn_recog_data (int index)
652 int i, old;
654 if (lra_insn_recog_data_len > index)
655 return;
656 old = lra_insn_recog_data_len;
657 lra_insn_recog_data_len = index * 3 / 2 + 1;
658 lra_insn_recog_data = XRESIZEVEC (lra_insn_recog_data_t,
659 lra_insn_recog_data,
660 lra_insn_recog_data_len);
661 for (i = old; i < lra_insn_recog_data_len; i++)
662 lra_insn_recog_data[i] = NULL;
665 /* Finish LRA DATA about insn. */
666 static void
667 free_insn_recog_data (lra_insn_recog_data_t data)
669 if (data->operand_loc != NULL)
670 free (data->operand_loc);
671 if (data->dup_loc != NULL)
672 free (data->dup_loc);
673 if (data->arg_hard_regs != NULL)
674 free (data->arg_hard_regs);
675 if (HAVE_ATTR_enabled && data->alternative_enabled_p != NULL)
676 free (data->alternative_enabled_p);
677 if (data->icode < 0 && NONDEBUG_INSN_P (data->insn))
679 if (data->insn_static_data->operand_alternative != NULL)
680 free (data->insn_static_data->operand_alternative);
681 free_insn_regs (data->insn_static_data->hard_regs);
682 free (data->insn_static_data);
684 free_insn_regs (data->regs);
685 data->regs = NULL;
686 free (data);
689 /* Finish LRA data about all insns. */
690 static void
691 finish_insn_recog_data (void)
693 int i;
694 lra_insn_recog_data_t data;
696 for (i = 0; i < lra_insn_recog_data_len; i++)
697 if ((data = lra_insn_recog_data[i]) != NULL)
698 free_insn_recog_data (data);
699 finish_insn_regs ();
700 free (lra_insn_recog_data);
703 /* Setup info about operands in alternatives of LRA DATA of insn. */
704 static void
705 setup_operand_alternative (lra_insn_recog_data_t data)
707 int i, nop, nalt;
708 int icode = data->icode;
709 struct lra_static_insn_data *static_data = data->insn_static_data;
711 if (icode >= 0
712 && (static_data->operand_alternative = op_alt_data[icode]) != NULL)
713 return;
714 static_data->commutative = -1;
715 nop = static_data->n_operands;
716 if (nop == 0)
718 static_data->operand_alternative = NULL;
719 return;
721 nalt = static_data->n_alternatives;
722 static_data->operand_alternative = XNEWVEC (struct operand_alternative,
723 nalt * nop);
724 memset (static_data->operand_alternative, 0,
725 nalt * nop * sizeof (struct operand_alternative));
726 if (icode >= 0)
727 op_alt_data[icode] = static_data->operand_alternative;
728 for (i = 0; i < nop; i++)
730 int j;
731 struct operand_alternative *op_alt_start, *op_alt;
732 const char *p = static_data->operand[i].constraint;
734 static_data->operand[i].early_clobber = 0;
735 op_alt_start = &static_data->operand_alternative[i];
737 for (j = 0; j < nalt; j++)
739 op_alt = op_alt_start + j * nop;
740 op_alt->cl = NO_REGS;
741 op_alt->constraint = p;
742 op_alt->matches = -1;
743 op_alt->matched = -1;
745 if (*p == '\0' || *p == ',')
747 op_alt->anything_ok = 1;
748 continue;
751 for (;;)
753 char c = *p;
754 if (c == '#')
756 c = *++p;
757 while (c != ',' && c != '\0');
758 if (c == ',' || c == '\0')
760 p++;
761 break;
764 switch (c)
766 case '=': case '+': case '*':
767 case 'E': case 'F': case 'G': case 'H':
768 case 's': case 'i': case 'n':
769 case 'I': case 'J': case 'K': case 'L':
770 case 'M': case 'N': case 'O': case 'P':
771 /* These don't say anything we care about. */
772 break;
774 case '%':
775 /* We currently only support one commutative pair of
776 operands. */
777 if (static_data->commutative < 0)
778 static_data->commutative = i;
779 else
780 lra_assert (data->icode < 0); /* Asm */
782 /* The last operand should not be marked
783 commutative. */
784 lra_assert (i != nop - 1);
785 break;
787 case '?':
788 op_alt->reject += LRA_LOSER_COST_FACTOR;
789 break;
790 case '!':
791 op_alt->reject += LRA_MAX_REJECT;
792 break;
793 case '&':
794 op_alt->earlyclobber = 1;
795 static_data->operand[i].early_clobber = 1;
796 break;
798 case '0': case '1': case '2': case '3': case '4':
799 case '5': case '6': case '7': case '8': case '9':
801 char *end;
802 op_alt->matches = strtoul (p, &end, 10);
803 static_data->operand_alternative
804 [j * nop + op_alt->matches].matched = i;
805 p = end;
807 continue;
809 case TARGET_MEM_CONSTRAINT:
810 op_alt->memory_ok = 1;
811 break;
812 case '<':
813 op_alt->decmem_ok = 1;
814 break;
815 case '>':
816 op_alt->incmem_ok = 1;
817 break;
818 case 'V':
819 op_alt->nonoffmem_ok = 1;
820 break;
821 case 'o':
822 op_alt->offmem_ok = 1;
823 break;
824 case 'X':
825 op_alt->anything_ok = 1;
826 break;
828 case 'p':
829 static_data->operand[i].is_address = true;
830 op_alt->is_address = 1;
831 op_alt->cl = (reg_class_subunion[(int) op_alt->cl]
832 [(int) base_reg_class (VOIDmode,
833 ADDR_SPACE_GENERIC,
834 ADDRESS, SCRATCH)]);
835 break;
837 case 'g':
838 case 'r':
839 op_alt->cl =
840 reg_class_subunion[(int) op_alt->cl][(int) GENERAL_REGS];
841 break;
843 default:
844 if (EXTRA_MEMORY_CONSTRAINT (c, p))
846 op_alt->memory_ok = 1;
847 break;
849 if (EXTRA_ADDRESS_CONSTRAINT (c, p))
851 static_data->operand[i].is_address = true;
852 op_alt->is_address = 1;
853 op_alt->cl
854 = (reg_class_subunion
855 [(int) op_alt->cl]
856 [(int) base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
857 ADDRESS, SCRATCH)]);
858 break;
861 op_alt->cl
862 = (reg_class_subunion
863 [(int) op_alt->cl]
864 [(int)
865 REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p)]);
866 break;
868 p += CONSTRAINT_LEN (c, p);
874 /* Recursively process X and collect info about registers, which are
875 not the insn operands, in X with TYPE (in/out/inout) and flag that
876 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
877 to LIST. X is a part of insn given by DATA. Return the result
878 list. */
879 static struct lra_insn_reg *
880 collect_non_operand_hard_regs (rtx *x, lra_insn_recog_data_t data,
881 struct lra_insn_reg *list,
882 enum op_type type, bool early_clobber)
884 int i, j, regno, last;
885 bool subreg_p;
886 enum machine_mode mode;
887 struct lra_insn_reg *curr;
888 rtx op = *x;
889 enum rtx_code code = GET_CODE (op);
890 const char *fmt = GET_RTX_FORMAT (code);
892 for (i = 0; i < data->insn_static_data->n_operands; i++)
893 if (x == data->operand_loc[i])
894 /* It is an operand loc. Stop here. */
895 return list;
896 for (i = 0; i < data->insn_static_data->n_dups; i++)
897 if (x == data->dup_loc[i])
898 /* It is a dup loc. Stop here. */
899 return list;
900 mode = GET_MODE (op);
901 subreg_p = false;
902 if (code == SUBREG)
904 op = SUBREG_REG (op);
905 code = GET_CODE (op);
906 if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (op)))
908 mode = GET_MODE (op);
909 if (GET_MODE_SIZE (mode) > REGMODE_NATURAL_SIZE (mode))
910 subreg_p = true;
913 if (REG_P (op))
915 if ((regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER)
916 return list;
917 for (last = regno + hard_regno_nregs[regno][mode];
918 regno < last;
919 regno++)
920 if (! TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
921 || TEST_HARD_REG_BIT (eliminable_regset, regno))
923 for (curr = list; curr != NULL; curr = curr->next)
924 if (curr->regno == regno && curr->subreg_p == subreg_p
925 && curr->biggest_mode == mode)
927 if (curr->type != type)
928 curr->type = OP_INOUT;
929 if (curr->early_clobber != early_clobber)
930 curr->early_clobber = true;
931 break;
933 if (curr == NULL)
935 /* This is a new hard regno or the info can not be
936 integrated into the found structure. */
937 #ifdef STACK_REGS
938 early_clobber
939 = (early_clobber
940 /* This clobber is to inform popping floating
941 point stack only. */
942 && ! (FIRST_STACK_REG <= regno
943 && regno <= LAST_STACK_REG));
944 #endif
945 list = new_insn_reg (regno, type, mode, subreg_p,
946 early_clobber, list);
949 return list;
951 switch (code)
953 case SET:
954 list = collect_non_operand_hard_regs (&SET_DEST (op), data,
955 list, OP_OUT, false);
956 list = collect_non_operand_hard_regs (&SET_SRC (op), data,
957 list, OP_IN, false);
958 break;
959 case CLOBBER:
960 /* We treat clobber of non-operand hard registers as early
961 clobber (the behavior is expected from asm). */
962 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
963 list, OP_OUT, true);
964 break;
965 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
966 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
967 list, OP_INOUT, false);
968 break;
969 case PRE_MODIFY: case POST_MODIFY:
970 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
971 list, OP_INOUT, false);
972 list = collect_non_operand_hard_regs (&XEXP (op, 1), data,
973 list, OP_IN, false);
974 break;
975 default:
976 fmt = GET_RTX_FORMAT (code);
977 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
979 if (fmt[i] == 'e')
980 list = collect_non_operand_hard_regs (&XEXP (op, i), data,
981 list, OP_IN, false);
982 else if (fmt[i] == 'E')
983 for (j = XVECLEN (op, i) - 1; j >= 0; j--)
984 list = collect_non_operand_hard_regs (&XVECEXP (op, i, j), data,
985 list, OP_IN, false);
988 return list;
991 /* Set up and return info about INSN. Set up the info if it is not set up
992 yet. */
993 lra_insn_recog_data_t
994 lra_set_insn_recog_data (rtx insn)
996 lra_insn_recog_data_t data;
997 int i, n, icode;
998 rtx **locs;
999 unsigned int uid = INSN_UID (insn);
1000 struct lra_static_insn_data *insn_static_data;
1002 check_and_expand_insn_recog_data (uid);
1003 if (DEBUG_INSN_P (insn))
1004 icode = -1;
1005 else
1007 icode = INSN_CODE (insn);
1008 if (icode < 0)
1009 /* It might be a new simple insn which is not recognized yet. */
1010 INSN_CODE (insn) = icode = recog_memoized (insn);
1012 data = XNEW (struct lra_insn_recog_data);
1013 lra_insn_recog_data[uid] = data;
1014 data->insn = insn;
1015 data->used_insn_alternative = -1;
1016 data->icode = icode;
1017 data->regs = NULL;
1018 if (DEBUG_INSN_P (insn))
1020 data->insn_static_data = &debug_insn_static_data;
1021 data->dup_loc = NULL;
1022 data->arg_hard_regs = NULL;
1023 data->alternative_enabled_p = NULL;
1024 data->operand_loc = XNEWVEC (rtx *, 1);
1025 data->operand_loc[0] = &INSN_VAR_LOCATION_LOC (insn);
1026 return data;
1028 if (icode < 0)
1030 int nop;
1031 enum machine_mode operand_mode[MAX_RECOG_OPERANDS];
1032 const char *constraints[MAX_RECOG_OPERANDS];
1034 nop = asm_noperands (PATTERN (insn));
1035 data->operand_loc = data->dup_loc = NULL;
1036 if (nop < 0)
1037 /* Its is a special insn like USE or CLOBBER. */
1038 data->insn_static_data = insn_static_data
1039 = get_static_insn_data (-1, 0, 0, 1);
1040 else
1042 /* expand_asm_operands makes sure there aren't too many
1043 operands. */
1044 lra_assert (nop <= MAX_RECOG_OPERANDS);
1045 if (nop != 0)
1046 data->operand_loc = XNEWVEC (rtx *, nop);
1047 /* Now get the operand values and constraints out of the
1048 insn. */
1049 decode_asm_operands (PATTERN (insn), NULL,
1050 data->operand_loc,
1051 constraints, operand_mode, NULL);
1052 n = 1;
1053 if (nop > 0)
1055 const char *p = recog_data.constraints[0];
1057 for (p = constraints[0]; *p; p++)
1058 n += *p == ',';
1060 data->insn_static_data = insn_static_data
1061 = get_static_insn_data (-1, nop, 0, n);
1062 for (i = 0; i < nop; i++)
1064 insn_static_data->operand[i].mode = operand_mode[i];
1065 insn_static_data->operand[i].constraint = constraints[i];
1066 insn_static_data->operand[i].strict_low = false;
1067 insn_static_data->operand[i].is_operator = false;
1068 insn_static_data->operand[i].is_address = false;
1071 for (i = 0; i < insn_static_data->n_operands; i++)
1072 insn_static_data->operand[i].type
1073 = (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1074 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1075 : OP_IN);
1076 data->alternative_enabled_p = NULL;
1078 else
1080 insn_extract (insn);
1081 data->insn_static_data = insn_static_data
1082 = get_static_insn_data (icode, insn_data[icode].n_operands,
1083 insn_data[icode].n_dups,
1084 insn_data[icode].n_alternatives);
1085 n = insn_static_data->n_operands;
1086 if (n == 0)
1087 locs = NULL;
1088 else
1090 locs = XNEWVEC (rtx *, n);
1091 memcpy (locs, recog_data.operand_loc, n * sizeof (rtx *));
1093 data->operand_loc = locs;
1094 n = insn_static_data->n_dups;
1095 if (n == 0)
1096 locs = NULL;
1097 else
1099 locs = XNEWVEC (rtx *, n);
1100 memcpy (locs, recog_data.dup_loc, n * sizeof (rtx *));
1102 data->dup_loc = locs;
1103 if (HAVE_ATTR_enabled)
1105 bool *bp;
1107 n = insn_static_data->n_alternatives;
1108 lra_assert (n >= 0);
1109 data->alternative_enabled_p = bp = XNEWVEC (bool, n);
1110 /* Cache the insn because we don't want to call extract_insn
1111 from get_attr_enabled as extract_insn modifies
1112 which_alternative. The attribute enabled should not depend
1113 on insn operands, operand modes, operand types, and operand
1114 constraints. It should depend on the architecture. If it
1115 is not true, we should rewrite this file code to use
1116 extract_insn instead of less expensive insn_extract. */
1117 recog_data.insn = insn;
1118 for (i = 0; i < n; i++)
1120 which_alternative = i;
1121 bp[i] = get_attr_enabled (insn);
1125 if (GET_CODE (PATTERN (insn)) == CLOBBER || GET_CODE (PATTERN (insn)) == USE)
1126 insn_static_data->hard_regs = NULL;
1127 else
1128 insn_static_data->hard_regs
1129 = collect_non_operand_hard_regs (&PATTERN (insn), data,
1130 NULL, OP_IN, false);
1131 setup_operand_alternative (data);
1132 data->arg_hard_regs = NULL;
1133 if (CALL_P (insn))
1135 rtx link;
1136 int n_hard_regs, regno, arg_hard_regs[FIRST_PSEUDO_REGISTER];
1138 n_hard_regs = 0;
1139 /* Finding implicit hard register usage. We believe it will be
1140 not changed whatever transformations are used. Call insns
1141 are such example. */
1142 for (link = CALL_INSN_FUNCTION_USAGE (insn);
1143 link != NULL_RTX;
1144 link = XEXP (link, 1))
1145 if (GET_CODE (XEXP (link, 0)) == USE
1146 && REG_P (XEXP (XEXP (link, 0), 0)))
1148 regno = REGNO (XEXP (XEXP (link, 0), 0));
1149 lra_assert (regno < FIRST_PSEUDO_REGISTER);
1150 /* It is an argument register. */
1151 for (i = (hard_regno_nregs
1152 [regno][GET_MODE (XEXP (XEXP (link, 0), 0))]) - 1;
1153 i >= 0;
1154 i--)
1155 arg_hard_regs[n_hard_regs++] = regno + i;
1157 if (n_hard_regs != 0)
1159 arg_hard_regs[n_hard_regs++] = -1;
1160 data->arg_hard_regs = XNEWVEC (int, n_hard_regs);
1161 memcpy (data->arg_hard_regs, arg_hard_regs,
1162 sizeof (int) * n_hard_regs);
1165 /* Some output operand can be recognized only from the context not
1166 from the constraints which are empty in this case. Call insn may
1167 contain a hard register in set destination with empty constraint
1168 and extract_insn treats them as an input. */
1169 for (i = 0; i < insn_static_data->n_operands; i++)
1171 int j;
1172 rtx pat, set;
1173 struct lra_operand_data *operand = &insn_static_data->operand[i];
1175 /* ??? Should we treat 'X' the same way. It looks to me that
1176 'X' means anything and empty constraint means we do not
1177 care. */
1178 if (operand->type != OP_IN || *operand->constraint != '\0'
1179 || operand->is_operator)
1180 continue;
1181 pat = PATTERN (insn);
1182 if (GET_CODE (pat) == SET)
1184 if (data->operand_loc[i] != &SET_DEST (pat))
1185 continue;
1187 else if (GET_CODE (pat) == PARALLEL)
1189 for (j = XVECLEN (pat, 0) - 1; j >= 0; j--)
1191 set = XVECEXP (PATTERN (insn), 0, j);
1192 if (GET_CODE (set) == SET
1193 && &SET_DEST (set) == data->operand_loc[i])
1194 break;
1196 if (j < 0)
1197 continue;
1199 else
1200 continue;
1201 operand->type = OP_OUT;
1203 return data;
1206 /* Return info about insn give by UID. The info should be already set
1207 up. */
1208 static lra_insn_recog_data_t
1209 get_insn_recog_data_by_uid (int uid)
1211 lra_insn_recog_data_t data;
1213 data = lra_insn_recog_data[uid];
1214 lra_assert (data != NULL);
1215 return data;
1218 /* Invalidate all info about insn given by its UID. */
1219 static void
1220 invalidate_insn_recog_data (int uid)
1222 lra_insn_recog_data_t data;
1224 data = lra_insn_recog_data[uid];
1225 lra_assert (data != NULL);
1226 free_insn_recog_data (data);
1227 lra_insn_recog_data[uid] = NULL;
1230 /* Update all the insn info about INSN. It is usually called when
1231 something in the insn was changed. Return the updated info. */
1232 lra_insn_recog_data_t
1233 lra_update_insn_recog_data (rtx insn)
1235 lra_insn_recog_data_t data;
1236 int n;
1237 unsigned int uid = INSN_UID (insn);
1238 struct lra_static_insn_data *insn_static_data;
1240 check_and_expand_insn_recog_data (uid);
1241 if ((data = lra_insn_recog_data[uid]) != NULL
1242 && data->icode != INSN_CODE (insn))
1244 invalidate_insn_data_regno_info (data, insn, get_insn_freq (insn));
1245 invalidate_insn_recog_data (uid);
1246 data = NULL;
1248 if (data == NULL)
1249 return lra_get_insn_recog_data (insn);
1250 insn_static_data = data->insn_static_data;
1251 data->used_insn_alternative = -1;
1252 if (DEBUG_INSN_P (insn))
1253 return data;
1254 if (data->icode < 0)
1256 int nop;
1257 enum machine_mode operand_mode[MAX_RECOG_OPERANDS];
1258 const char *constraints[MAX_RECOG_OPERANDS];
1260 nop = asm_noperands (PATTERN (insn));
1261 if (nop >= 0)
1263 lra_assert (nop == data->insn_static_data->n_operands);
1264 /* Now get the operand values and constraints out of the
1265 insn. */
1266 decode_asm_operands (PATTERN (insn), NULL,
1267 data->operand_loc,
1268 constraints, operand_mode, NULL);
1269 #ifdef ENABLE_CHECKING
1271 int i;
1273 for (i = 0; i < nop; i++)
1274 lra_assert
1275 (insn_static_data->operand[i].mode == operand_mode[i]
1276 && insn_static_data->operand[i].constraint == constraints[i]
1277 && ! insn_static_data->operand[i].is_operator);
1279 #endif
1281 #ifdef ENABLE_CHECKING
1283 int i;
1285 for (i = 0; i < insn_static_data->n_operands; i++)
1286 lra_assert
1287 (insn_static_data->operand[i].type
1288 == (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1289 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1290 : OP_IN));
1292 #endif
1294 else
1296 insn_extract (insn);
1297 n = insn_static_data->n_operands;
1298 if (n != 0)
1299 memcpy (data->operand_loc, recog_data.operand_loc, n * sizeof (rtx *));
1300 n = insn_static_data->n_dups;
1301 if (n != 0)
1302 memcpy (data->dup_loc, recog_data.dup_loc, n * sizeof (rtx *));
1303 #if HAVE_ATTR_enabled
1304 #ifdef ENABLE_CHECKING
1306 int i;
1307 bool *bp;
1309 n = insn_static_data->n_alternatives;
1310 bp = data->alternative_enabled_p;
1311 lra_assert (n >= 0 && bp != NULL);
1312 /* Cache the insn to prevent extract_insn call from
1313 get_attr_enabled. */
1314 recog_data.insn = insn;
1315 for (i = 0; i < n; i++)
1317 which_alternative = i;
1318 lra_assert (bp[i] == get_attr_enabled (insn));
1321 #endif
1322 #endif
1324 return data;
1327 /* Set up that INSN is using alternative ALT now. */
1328 void
1329 lra_set_used_insn_alternative (rtx insn, int alt)
1331 lra_insn_recog_data_t data;
1333 data = lra_get_insn_recog_data (insn);
1334 data->used_insn_alternative = alt;
1337 /* Set up that insn with UID is using alternative ALT now. The insn
1338 info should be already set up. */
1339 void
1340 lra_set_used_insn_alternative_by_uid (int uid, int alt)
1342 lra_insn_recog_data_t data;
1344 check_and_expand_insn_recog_data (uid);
1345 data = lra_insn_recog_data[uid];
1346 lra_assert (data != NULL);
1347 data->used_insn_alternative = alt;
1352 /* This page contains code dealing with common register info and
1353 pseudo copies. */
1355 /* The size of the following array. */
1356 static int reg_info_size;
1357 /* Common info about each register. */
1358 struct lra_reg *lra_reg_info;
1360 /* Last register value. */
1361 static int last_reg_value;
1363 /* Return new register value. */
1364 static int
1365 get_new_reg_value (void)
1367 return ++last_reg_value;
1370 /* Pools for copies. */
1371 static alloc_pool copy_pool;
1373 /* Vec referring to pseudo copies. */
1374 static vec<lra_copy_t> copy_vec;
1376 /* Initialize I-th element of lra_reg_info. */
1377 static inline void
1378 initialize_lra_reg_info_element (int i)
1380 bitmap_initialize (&lra_reg_info[i].insn_bitmap, &reg_obstack);
1381 #ifdef STACK_REGS
1382 lra_reg_info[i].no_stack_p = false;
1383 #endif
1384 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1385 lra_reg_info[i].preferred_hard_regno1 = -1;
1386 lra_reg_info[i].preferred_hard_regno2 = -1;
1387 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1388 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1389 lra_reg_info[i].biggest_mode = VOIDmode;
1390 lra_reg_info[i].live_ranges = NULL;
1391 lra_reg_info[i].nrefs = lra_reg_info[i].freq = 0;
1392 lra_reg_info[i].last_reload = 0;
1393 lra_reg_info[i].restore_regno = -1;
1394 lra_reg_info[i].val = get_new_reg_value ();
1395 lra_reg_info[i].offset = 0;
1396 lra_reg_info[i].copies = NULL;
1399 /* Initialize common reg info and copies. */
1400 static void
1401 init_reg_info (void)
1403 int i;
1405 last_reg_value = 0;
1406 reg_info_size = max_reg_num () * 3 / 2 + 1;
1407 lra_reg_info = XNEWVEC (struct lra_reg, reg_info_size);
1408 for (i = 0; i < reg_info_size; i++)
1409 initialize_lra_reg_info_element (i);
1410 copy_pool
1411 = create_alloc_pool ("lra copies", sizeof (struct lra_copy), 100);
1412 copy_vec.create (100);
1416 /* Finish common reg info and copies. */
1417 static void
1418 finish_reg_info (void)
1420 int i;
1422 for (i = 0; i < reg_info_size; i++)
1423 bitmap_clear (&lra_reg_info[i].insn_bitmap);
1424 free (lra_reg_info);
1425 reg_info_size = 0;
1426 free_alloc_pool (copy_pool);
1427 copy_vec.release ();
1430 /* Expand common reg info if it is necessary. */
1431 static void
1432 expand_reg_info (void)
1434 int i, old = reg_info_size;
1436 if (reg_info_size > max_reg_num ())
1437 return;
1438 reg_info_size = max_reg_num () * 3 / 2 + 1;
1439 lra_reg_info = XRESIZEVEC (struct lra_reg, lra_reg_info, reg_info_size);
1440 for (i = old; i < reg_info_size; i++)
1441 initialize_lra_reg_info_element (i);
1444 /* Free all copies. */
1445 void
1446 lra_free_copies (void)
1448 lra_copy_t cp;
1450 while (copy_vec.length () != 0)
1452 cp = copy_vec.pop ();
1453 lra_reg_info[cp->regno1].copies = lra_reg_info[cp->regno2].copies = NULL;
1454 pool_free (copy_pool, cp);
1458 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1459 frequency is FREQ. */
1460 void
1461 lra_create_copy (int regno1, int regno2, int freq)
1463 bool regno1_dest_p;
1464 lra_copy_t cp;
1466 lra_assert (regno1 != regno2);
1467 regno1_dest_p = true;
1468 if (regno1 > regno2)
1470 int temp = regno2;
1472 regno1_dest_p = false;
1473 regno2 = regno1;
1474 regno1 = temp;
1476 cp = (lra_copy_t) pool_alloc (copy_pool);
1477 copy_vec.safe_push (cp);
1478 cp->regno1_dest_p = regno1_dest_p;
1479 cp->freq = freq;
1480 cp->regno1 = regno1;
1481 cp->regno2 = regno2;
1482 cp->regno1_next = lra_reg_info[regno1].copies;
1483 lra_reg_info[regno1].copies = cp;
1484 cp->regno2_next = lra_reg_info[regno2].copies;
1485 lra_reg_info[regno2].copies = cp;
1486 if (lra_dump_file != NULL)
1487 fprintf (lra_dump_file, " Creating copy r%d%sr%d@%d\n",
1488 regno1, regno1_dest_p ? "<-" : "->", regno2, freq);
1491 /* Return N-th (0, 1, ...) copy. If there is no copy, return
1492 NULL. */
1493 lra_copy_t
1494 lra_get_copy (int n)
1496 if (n >= (int) copy_vec.length ())
1497 return NULL;
1498 return copy_vec[n];
1503 /* This page contains code dealing with info about registers in
1504 insns. */
1506 /* Process X of insn UID recursively and add info (operand type is
1507 given by TYPE, flag of that it is early clobber is EARLY_CLOBBER)
1508 about registers in X to the insn DATA. */
1509 static void
1510 add_regs_to_insn_regno_info (lra_insn_recog_data_t data, rtx x, int uid,
1511 enum op_type type, bool early_clobber)
1513 int i, j, regno;
1514 bool subreg_p;
1515 enum machine_mode mode;
1516 const char *fmt;
1517 enum rtx_code code;
1518 struct lra_insn_reg *curr;
1520 code = GET_CODE (x);
1521 mode = GET_MODE (x);
1522 subreg_p = false;
1523 if (GET_CODE (x) == SUBREG)
1525 x = SUBREG_REG (x);
1526 code = GET_CODE (x);
1527 if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (x)))
1529 mode = GET_MODE (x);
1530 if (GET_MODE_SIZE (mode) > REGMODE_NATURAL_SIZE (mode))
1531 subreg_p = true;
1534 if (REG_P (x))
1536 regno = REGNO (x);
1537 if (regno < FIRST_PSEUDO_REGISTER
1538 && TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
1539 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
1540 return;
1541 expand_reg_info ();
1542 if (bitmap_set_bit (&lra_reg_info[regno].insn_bitmap, uid))
1544 data->regs = new_insn_reg (regno, type, mode, subreg_p,
1545 early_clobber, data->regs);
1546 return;
1548 else
1550 for (curr = data->regs; curr != NULL; curr = curr->next)
1551 if (curr->regno == regno)
1553 if (curr->subreg_p != subreg_p || curr->biggest_mode != mode)
1554 /* The info can not be integrated into the found
1555 structure. */
1556 data->regs = new_insn_reg (regno, type, mode, subreg_p,
1557 early_clobber, data->regs);
1558 else
1560 if (curr->type != type)
1561 curr->type = OP_INOUT;
1562 if (curr->early_clobber != early_clobber)
1563 curr->early_clobber = true;
1565 return;
1567 gcc_unreachable ();
1571 switch (code)
1573 case SET:
1574 add_regs_to_insn_regno_info (data, SET_DEST (x), uid, OP_OUT, false);
1575 add_regs_to_insn_regno_info (data, SET_SRC (x), uid, OP_IN, false);
1576 break;
1577 case CLOBBER:
1578 /* We treat clobber of non-operand hard registers as early
1579 clobber (the behavior is expected from asm). */
1580 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_OUT, true);
1581 break;
1582 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
1583 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false);
1584 break;
1585 case PRE_MODIFY: case POST_MODIFY:
1586 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false);
1587 add_regs_to_insn_regno_info (data, XEXP (x, 1), uid, OP_IN, false);
1588 break;
1589 default:
1590 if ((code != PARALLEL && code != EXPR_LIST) || type != OP_OUT)
1591 /* Some targets place small structures in registers for return
1592 values of functions, and those registers are wrapped in
1593 PARALLEL that we may see as the destination of a SET. Here
1594 is an example:
1596 (call_insn 13 12 14 2 (set (parallel:BLK [
1597 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1598 (const_int 0 [0]))
1599 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1600 (const_int 8 [0x8]))
1602 (call (mem:QI (symbol_ref:DI (... */
1603 type = OP_IN;
1604 fmt = GET_RTX_FORMAT (code);
1605 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1607 if (fmt[i] == 'e')
1608 add_regs_to_insn_regno_info (data, XEXP (x, i), uid, type, false);
1609 else if (fmt[i] == 'E')
1611 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1612 add_regs_to_insn_regno_info (data, XVECEXP (x, i, j), uid,
1613 type, false);
1619 /* Return execution frequency of INSN. */
1620 static int
1621 get_insn_freq (rtx insn)
1623 basic_block bb = BLOCK_FOR_INSN (insn);
1625 gcc_checking_assert (bb != NULL);
1626 return REG_FREQ_FROM_BB (bb);
1629 /* Invalidate all reg info of INSN with DATA and execution frequency
1630 FREQ. Update common info about the invalidated registers. */
1631 static void
1632 invalidate_insn_data_regno_info (lra_insn_recog_data_t data, rtx insn,
1633 int freq)
1635 int uid;
1636 bool debug_p;
1637 unsigned int i;
1638 struct lra_insn_reg *ir, *next_ir;
1640 uid = INSN_UID (insn);
1641 debug_p = DEBUG_INSN_P (insn);
1642 for (ir = data->regs; ir != NULL; ir = next_ir)
1644 i = ir->regno;
1645 next_ir = ir->next;
1646 free_insn_reg (ir);
1647 bitmap_clear_bit (&lra_reg_info[i].insn_bitmap, uid);
1648 if (i >= FIRST_PSEUDO_REGISTER && ! debug_p)
1650 lra_reg_info[i].nrefs--;
1651 lra_reg_info[i].freq -= freq;
1652 lra_assert (lra_reg_info[i].nrefs >= 0 && lra_reg_info[i].freq >= 0);
1655 data->regs = NULL;
1658 /* Invalidate all reg info of INSN. Update common info about the
1659 invalidated registers. */
1660 void
1661 lra_invalidate_insn_regno_info (rtx insn)
1663 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn), insn,
1664 get_insn_freq (insn));
1667 /* Update common reg info from reg info of insn given by its DATA and
1668 execution frequency FREQ. */
1669 static void
1670 setup_insn_reg_info (lra_insn_recog_data_t data, int freq)
1672 unsigned int i;
1673 struct lra_insn_reg *ir;
1675 for (ir = data->regs; ir != NULL; ir = ir->next)
1676 if ((i = ir->regno) >= FIRST_PSEUDO_REGISTER)
1678 lra_reg_info[i].nrefs++;
1679 lra_reg_info[i].freq += freq;
1683 /* Set up insn reg info of INSN. Update common reg info from reg info
1684 of INSN. */
1685 void
1686 lra_update_insn_regno_info (rtx insn)
1688 int i, uid, freq;
1689 lra_insn_recog_data_t data;
1690 struct lra_static_insn_data *static_data;
1691 enum rtx_code code;
1693 if (! INSN_P (insn))
1694 return;
1695 data = lra_get_insn_recog_data (insn);
1696 static_data = data->insn_static_data;
1697 freq = get_insn_freq (insn);
1698 invalidate_insn_data_regno_info (data, insn, freq);
1699 uid = INSN_UID (insn);
1700 for (i = static_data->n_operands - 1; i >= 0; i--)
1701 add_regs_to_insn_regno_info (data, *data->operand_loc[i], uid,
1702 static_data->operand[i].type,
1703 static_data->operand[i].early_clobber);
1704 if ((code = GET_CODE (PATTERN (insn))) == CLOBBER || code == USE)
1705 add_regs_to_insn_regno_info (data, XEXP (PATTERN (insn), 0), uid,
1706 code == USE ? OP_IN : OP_OUT, false);
1707 if (NONDEBUG_INSN_P (insn))
1708 setup_insn_reg_info (data, freq);
1711 /* Return reg info of insn given by it UID. */
1712 struct lra_insn_reg *
1713 lra_get_insn_regs (int uid)
1715 lra_insn_recog_data_t data;
1717 data = get_insn_recog_data_by_uid (uid);
1718 return data->regs;
1723 /* This page contains code dealing with stack of the insns which
1724 should be processed by the next constraint pass. */
1726 /* Bitmap used to put an insn on the stack only in one exemplar. */
1727 static sbitmap lra_constraint_insn_stack_bitmap;
1729 /* The stack itself. */
1730 vec<rtx> lra_constraint_insn_stack;
1732 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1733 info for INSN, otherwise only update it if INSN is not already on the
1734 stack. */
1735 static inline void
1736 lra_push_insn_1 (rtx insn, bool always_update)
1738 unsigned int uid = INSN_UID (insn);
1739 if (always_update)
1740 lra_update_insn_regno_info (insn);
1741 if (uid >= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap))
1742 lra_constraint_insn_stack_bitmap =
1743 sbitmap_resize (lra_constraint_insn_stack_bitmap, 3 * uid / 2, 0);
1744 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap, uid))
1745 return;
1746 bitmap_set_bit (lra_constraint_insn_stack_bitmap, uid);
1747 if (! always_update)
1748 lra_update_insn_regno_info (insn);
1749 lra_constraint_insn_stack.safe_push (insn);
1752 /* Put INSN on the stack. */
1753 void
1754 lra_push_insn (rtx insn)
1756 lra_push_insn_1 (insn, false);
1759 /* Put INSN on the stack and update its reg info. */
1760 void
1761 lra_push_insn_and_update_insn_regno_info (rtx insn)
1763 lra_push_insn_1 (insn, true);
1766 /* Put insn with UID on the stack. */
1767 void
1768 lra_push_insn_by_uid (unsigned int uid)
1770 lra_push_insn (lra_insn_recog_data[uid]->insn);
1773 /* Take the last-inserted insns off the stack and return it. */
1775 lra_pop_insn (void)
1777 rtx insn = lra_constraint_insn_stack.pop ();
1778 bitmap_clear_bit (lra_constraint_insn_stack_bitmap, INSN_UID (insn));
1779 return insn;
1782 /* Return the current size of the insn stack. */
1783 unsigned int
1784 lra_insn_stack_length (void)
1786 return lra_constraint_insn_stack.length ();
1789 /* Push insns FROM to TO (excluding it) going in reverse order. */
1790 static void
1791 push_insns (rtx from, rtx to)
1793 rtx insn;
1795 if (from == NULL_RTX)
1796 return;
1797 for (insn = from; insn != to; insn = PREV_INSN (insn))
1798 if (INSN_P (insn))
1799 lra_push_insn (insn);
1802 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1803 insns onto the stack. Print about emitting the insns with
1804 TITLE. */
1805 void
1806 lra_process_new_insns (rtx insn, rtx before, rtx after, const char *title)
1808 rtx last;
1810 if (lra_dump_file != NULL && (before != NULL_RTX || after != NULL_RTX))
1812 dump_insn_slim (lra_dump_file, insn);
1813 if (before != NULL_RTX)
1815 fprintf (lra_dump_file," %s before:\n", title);
1816 dump_rtl_slim (lra_dump_file, before, NULL_RTX, -1, 0);
1818 if (after != NULL_RTX)
1820 fprintf (lra_dump_file, " %s after:\n", title);
1821 dump_rtl_slim (lra_dump_file, after, NULL_RTX, -1, 0);
1823 fprintf (lra_dump_file, "\n");
1825 if (before != NULL_RTX)
1827 emit_insn_before (before, insn);
1828 push_insns (PREV_INSN (insn), PREV_INSN (before));
1830 if (after != NULL_RTX)
1832 for (last = after; NEXT_INSN (last) != NULL_RTX; last = NEXT_INSN (last))
1834 emit_insn_after (after, insn);
1835 push_insns (last, insn);
1841 /* This page contains code dealing with scratches (changing them onto
1842 pseudos and restoring them from the pseudos).
1844 We change scratches into pseudos at the beginning of LRA to
1845 simplify dealing with them (conflicts, hard register assignments).
1847 If the pseudo denoting scratch was spilled it means that we do need
1848 a hard register for it. Such pseudos are transformed back to
1849 scratches at the end of LRA. */
1851 /* Description of location of a former scratch operand. */
1852 struct sloc
1854 rtx insn; /* Insn where the scratch was. */
1855 int nop; /* Number of the operand which was a scratch. */
1858 typedef struct sloc *sloc_t;
1860 /* Locations of the former scratches. */
1861 static vec<sloc_t> scratches;
1863 /* Bitmap of scratch regnos. */
1864 static bitmap_head scratch_bitmap;
1866 /* Bitmap of scratch operands. */
1867 static bitmap_head scratch_operand_bitmap;
1869 /* Return true if pseudo REGNO is made of SCRATCH. */
1870 bool
1871 lra_former_scratch_p (int regno)
1873 return bitmap_bit_p (&scratch_bitmap, regno);
1876 /* Return true if the operand NOP of INSN is a former scratch. */
1877 bool
1878 lra_former_scratch_operand_p (rtx insn, int nop)
1880 return bitmap_bit_p (&scratch_operand_bitmap,
1881 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop) != 0;
1884 /* Change scratches onto pseudos and save their location. */
1885 static void
1886 remove_scratches (void)
1888 int i;
1889 bool insn_changed_p;
1890 basic_block bb;
1891 rtx insn, reg;
1892 sloc_t loc;
1893 lra_insn_recog_data_t id;
1894 struct lra_static_insn_data *static_id;
1896 scratches.create (get_max_uid ());
1897 bitmap_initialize (&scratch_bitmap, &reg_obstack);
1898 bitmap_initialize (&scratch_operand_bitmap, &reg_obstack);
1899 FOR_EACH_BB (bb)
1900 FOR_BB_INSNS (bb, insn)
1901 if (INSN_P (insn))
1903 id = lra_get_insn_recog_data (insn);
1904 static_id = id->insn_static_data;
1905 insn_changed_p = false;
1906 for (i = 0; i < static_id->n_operands; i++)
1907 if (GET_CODE (*id->operand_loc[i]) == SCRATCH
1908 && GET_MODE (*id->operand_loc[i]) != VOIDmode)
1910 insn_changed_p = true;
1911 *id->operand_loc[i] = reg
1912 = lra_create_new_reg (static_id->operand[i].mode,
1913 *id->operand_loc[i], ALL_REGS, NULL);
1914 add_reg_note (insn, REG_UNUSED, reg);
1915 lra_update_dup (id, i);
1916 loc = XNEW (struct sloc);
1917 loc->insn = insn;
1918 loc->nop = i;
1919 scratches.safe_push (loc);
1920 bitmap_set_bit (&scratch_bitmap, REGNO (*id->operand_loc[i]));
1921 bitmap_set_bit (&scratch_operand_bitmap,
1922 INSN_UID (insn) * MAX_RECOG_OPERANDS + i);
1923 if (lra_dump_file != NULL)
1924 fprintf (lra_dump_file,
1925 "Removing SCRATCH in insn #%u (nop %d)\n",
1926 INSN_UID (insn), i);
1928 if (insn_changed_p)
1929 /* Because we might use DF right after caller-saves sub-pass
1930 we need to keep DF info up to date. */
1931 df_insn_rescan (insn);
1935 /* Changes pseudos created by function remove_scratches onto scratches. */
1936 static void
1937 restore_scratches (void)
1939 int regno;
1940 unsigned i;
1941 sloc_t loc;
1942 rtx last = NULL_RTX;
1943 lra_insn_recog_data_t id = NULL;
1945 for (i = 0; scratches.iterate (i, &loc); i++)
1947 if (last != loc->insn)
1949 last = loc->insn;
1950 id = lra_get_insn_recog_data (last);
1952 if (REG_P (*id->operand_loc[loc->nop])
1953 && ((regno = REGNO (*id->operand_loc[loc->nop]))
1954 >= FIRST_PSEUDO_REGISTER)
1955 && lra_get_regno_hard_regno (regno) < 0)
1957 /* It should be only case when scratch register with chosen
1958 constraint 'X' did not get memory or hard register. */
1959 lra_assert (lra_former_scratch_p (regno));
1960 *id->operand_loc[loc->nop]
1961 = gen_rtx_SCRATCH (GET_MODE (*id->operand_loc[loc->nop]));
1962 lra_update_dup (id, loc->nop);
1963 if (lra_dump_file != NULL)
1964 fprintf (lra_dump_file, "Restoring SCRATCH in insn #%u(nop %d)\n",
1965 INSN_UID (loc->insn), loc->nop);
1968 for (i = 0; scratches.iterate (i, &loc); i++)
1969 free (loc);
1970 scratches.release ();
1971 bitmap_clear (&scratch_bitmap);
1972 bitmap_clear (&scratch_operand_bitmap);
1977 #ifdef ENABLE_CHECKING
1979 /* Function checks RTL for correctness. If FINAL_P is true, it is
1980 done at the end of LRA and the check is more rigorous. */
1981 static void
1982 check_rtl (bool final_p)
1984 int i;
1985 basic_block bb;
1986 rtx insn;
1987 lra_insn_recog_data_t id;
1989 lra_assert (! final_p || reload_completed);
1990 FOR_EACH_BB (bb)
1991 FOR_BB_INSNS (bb, insn)
1992 if (NONDEBUG_INSN_P (insn)
1993 && GET_CODE (PATTERN (insn)) != USE
1994 && GET_CODE (PATTERN (insn)) != CLOBBER
1995 && GET_CODE (PATTERN (insn)) != ASM_INPUT)
1997 if (final_p)
1999 extract_insn (insn);
2000 lra_assert (constrain_operands (1));
2001 continue;
2003 if (insn_invalid_p (insn, false))
2004 fatal_insn_not_found (insn);
2005 if (asm_noperands (PATTERN (insn)) >= 0)
2006 continue;
2007 id = lra_get_insn_recog_data (insn);
2008 /* The code is based on assumption that all addresses in
2009 regular instruction are legitimate before LRA. The code in
2010 lra-constraints.c is based on assumption that there is no
2011 subreg of memory as an insn operand. */
2012 for (i = 0; i < id->insn_static_data->n_operands; i++)
2014 rtx op = *id->operand_loc[i];
2016 if (MEM_P (op)
2017 && (GET_MODE (op) != BLKmode
2018 || GET_CODE (XEXP (op, 0)) != SCRATCH)
2019 && ! memory_address_p (GET_MODE (op), XEXP (op, 0))
2020 /* Some ports don't recognize the following addresses
2021 as legitimate. Although they are legitimate if
2022 they satisfies the constraints and will be checked
2023 by insn constraints which we ignore here. */
2024 && GET_CODE (XEXP (op, 0)) != UNSPEC
2025 && GET_RTX_CLASS (GET_CODE (XEXP (op, 0))) != RTX_AUTOINC)
2026 fatal_insn_not_found (insn);
2030 #endif /* #ifdef ENABLE_CHECKING */
2032 /* Determine if the current function has an exception receiver block
2033 that reaches the exit block via non-exceptional edges */
2034 static bool
2035 has_nonexceptional_receiver (void)
2037 edge e;
2038 edge_iterator ei;
2039 basic_block *tos, *worklist, bb;
2041 /* If we're not optimizing, then just err on the safe side. */
2042 if (!optimize)
2043 return true;
2045 /* First determine which blocks can reach exit via normal paths. */
2046 tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1);
2048 FOR_EACH_BB (bb)
2049 bb->flags &= ~BB_REACHABLE;
2051 /* Place the exit block on our worklist. */
2052 EXIT_BLOCK_PTR->flags |= BB_REACHABLE;
2053 *tos++ = EXIT_BLOCK_PTR;
2055 /* Iterate: find everything reachable from what we've already seen. */
2056 while (tos != worklist)
2058 bb = *--tos;
2060 FOR_EACH_EDGE (e, ei, bb->preds)
2061 if (e->flags & EDGE_ABNORMAL)
2063 free (worklist);
2064 return true;
2066 else
2068 basic_block src = e->src;
2070 if (!(src->flags & BB_REACHABLE))
2072 src->flags |= BB_REACHABLE;
2073 *tos++ = src;
2077 free (worklist);
2078 /* No exceptional block reached exit unexceptionally. */
2079 return false;
2082 #ifdef AUTO_INC_DEC
2084 /* Process recursively X of INSN and add REG_INC notes if necessary. */
2085 static void
2086 add_auto_inc_notes (rtx insn, rtx x)
2088 enum rtx_code code = GET_CODE (x);
2089 const char *fmt;
2090 int i, j;
2092 if (code == MEM && auto_inc_p (XEXP (x, 0)))
2094 add_reg_note (insn, REG_INC, XEXP (XEXP (x, 0), 0));
2095 return;
2098 /* Scan all X sub-expressions. */
2099 fmt = GET_RTX_FORMAT (code);
2100 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2102 if (fmt[i] == 'e')
2103 add_auto_inc_notes (insn, XEXP (x, i));
2104 else if (fmt[i] == 'E')
2105 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2106 add_auto_inc_notes (insn, XVECEXP (x, i, j));
2110 #endif
2112 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2113 We change pseudos by hard registers without notification of DF and
2114 that can make the notes obsolete. DF-infrastructure does not deal
2115 with REG_INC notes -- so we should regenerate them here. */
2116 static void
2117 update_inc_notes (void)
2119 rtx *pnote;
2120 basic_block bb;
2121 rtx insn;
2123 FOR_EACH_BB (bb)
2124 FOR_BB_INSNS (bb, insn)
2125 if (NONDEBUG_INSN_P (insn))
2127 pnote = &REG_NOTES (insn);
2128 while (*pnote != 0)
2130 if (REG_NOTE_KIND (*pnote) == REG_INC)
2131 *pnote = XEXP (*pnote, 1);
2132 else
2133 pnote = &XEXP (*pnote, 1);
2135 #ifdef AUTO_INC_DEC
2136 add_auto_inc_notes (insn, PATTERN (insn));
2137 #endif
2141 /* Set to 1 while in lra. */
2142 int lra_in_progress;
2144 /* Start of pseudo regnos before the LRA. */
2145 int lra_new_regno_start;
2147 /* Start of reload pseudo regnos before the new spill pass. */
2148 int lra_constraint_new_regno_start;
2150 /* Inheritance pseudo regnos before the new spill pass. */
2151 bitmap_head lra_inheritance_pseudos;
2153 /* Split regnos before the new spill pass. */
2154 bitmap_head lra_split_regs;
2156 /* Reload pseudo regnos before the new assign pass which still can be
2157 spilled after the assinment pass. */
2158 bitmap_head lra_optional_reload_pseudos;
2160 /* First UID of insns generated before a new spill pass. */
2161 int lra_constraint_new_insn_uid_start;
2163 /* File used for output of LRA debug information. */
2164 FILE *lra_dump_file;
2166 /* True if we should try spill into registers of different classes
2167 instead of memory. */
2168 bool lra_reg_spill_p;
2170 /* Set up value LRA_REG_SPILL_P. */
2171 static void
2172 setup_reg_spill_flag (void)
2174 int cl, mode;
2176 if (targetm.spill_class != NULL)
2177 for (cl = 0; cl < (int) LIM_REG_CLASSES; cl++)
2178 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
2179 if (targetm.spill_class ((enum reg_class) cl,
2180 (enum machine_mode) mode) != NO_REGS)
2182 lra_reg_spill_p = true;
2183 return;
2185 lra_reg_spill_p = false;
2188 /* True if the current function is too big to use regular algorithms
2189 in LRA. In other words, we should use simpler and faster algorithms
2190 in LRA. It also means we should not worry about generation code
2191 for caller saves. The value is set up in IRA. */
2192 bool lra_simple_p;
2194 /* Major LRA entry function. F is a file should be used to dump LRA
2195 debug info. */
2196 void
2197 lra (FILE *f)
2199 int i;
2200 bool live_p, scratch_p, inserted_p;
2202 lra_dump_file = f;
2204 timevar_push (TV_LRA);
2206 /* Make sure that the last insn is a note. Some subsequent passes
2207 need it. */
2208 emit_note (NOTE_INSN_DELETED);
2210 COPY_HARD_REG_SET (lra_no_alloc_regs, ira_no_alloc_regs);
2212 init_reg_info ();
2213 expand_reg_info ();
2215 init_insn_recog_data ();
2217 #ifdef ENABLE_CHECKING
2218 check_rtl (false);
2219 #endif
2221 lra_live_range_iter = lra_coalesce_iter = 0;
2222 lra_constraint_iter = lra_constraint_iter_after_spill = 0;
2223 lra_inheritance_iter = lra_undo_inheritance_iter = 0;
2225 setup_reg_spill_flag ();
2227 /* We can not set up reload_in_progress because it prevents new
2228 pseudo creation. */
2229 lra_in_progress = 1;
2231 /* Function remove_scratches can creates new pseudos for clobbers --
2232 so set up lra_constraint_new_regno_start before its call to
2233 permit changing reg classes for pseudos created by this
2234 simplification. */
2235 lra_constraint_new_regno_start = lra_new_regno_start = max_reg_num ();
2236 remove_scratches ();
2237 scratch_p = lra_constraint_new_regno_start != max_reg_num ();
2239 /* A function that has a non-local label that can reach the exit
2240 block via non-exceptional paths must save all call-saved
2241 registers. */
2242 if (cfun->has_nonlocal_label && has_nonexceptional_receiver ())
2243 crtl->saves_all_registers = 1;
2245 if (crtl->saves_all_registers)
2246 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2247 if (! call_used_regs[i] && ! fixed_regs[i] && ! LOCAL_REGNO (i))
2248 df_set_regs_ever_live (i, true);
2250 /* We don't DF from now and avoid its using because it is to
2251 expensive when a lot of RTL changes are made. */
2252 df_set_flags (DF_NO_INSN_RESCAN);
2253 lra_constraint_insn_stack.create (get_max_uid ());
2254 lra_constraint_insn_stack_bitmap = sbitmap_alloc (get_max_uid ());
2255 bitmap_clear (lra_constraint_insn_stack_bitmap);
2256 lra_live_ranges_init ();
2257 lra_constraints_init ();
2258 lra_curr_reload_num = 0;
2259 push_insns (get_last_insn (), NULL_RTX);
2260 /* It is needed for the 1st coalescing. */
2261 lra_constraint_new_insn_uid_start = get_max_uid ();
2262 bitmap_initialize (&lra_inheritance_pseudos, &reg_obstack);
2263 bitmap_initialize (&lra_split_regs, &reg_obstack);
2264 bitmap_initialize (&lra_optional_reload_pseudos, &reg_obstack);
2265 live_p = false;
2266 if (get_frame_size () != 0 && crtl->stack_alignment_needed)
2267 /* If we have a stack frame, we must align it now. The stack size
2268 may be a part of the offset computation for register
2269 elimination. */
2270 assign_stack_local (BLKmode, 0, crtl->stack_alignment_needed);
2271 for (;;)
2273 for (;;)
2275 /* We should try to assign hard registers to scratches even
2276 if there were no RTL transformations in
2277 lra_constraints. */
2278 if (! lra_constraints (lra_constraint_iter == 0)
2279 && (lra_constraint_iter > 1
2280 || (! scratch_p && ! caller_save_needed)))
2281 break;
2282 /* Constraint transformations may result in that eliminable
2283 hard regs become uneliminable and pseudos which use them
2284 should be spilled. It is better to do it before pseudo
2285 assignments.
2287 For example, rs6000 can make
2288 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2289 to use a constant pool. */
2290 lra_eliminate (false);
2291 /* Do inheritance only for regular algorithms. */
2292 if (! lra_simple_p)
2293 lra_inheritance ();
2294 if (live_p)
2295 lra_clear_live_ranges ();
2296 /* We need live ranges for lra_assign -- so build them. */
2297 lra_create_live_ranges (true);
2298 live_p = true;
2299 /* If we don't spill non-reload and non-inheritance pseudos,
2300 there is no sense to run memory-memory move coalescing.
2301 If inheritance pseudos were spilled, the memory-memory
2302 moves involving them will be removed by pass undoing
2303 inheritance. */
2304 if (lra_simple_p)
2305 lra_assign ();
2306 else
2308 bool spill_p = !lra_assign ();
2310 if (lra_undo_inheritance ())
2311 live_p = false;
2312 if (spill_p)
2314 if (! live_p)
2316 lra_create_live_ranges (true);
2317 live_p = true;
2319 if (lra_coalesce ())
2320 live_p = false;
2322 if (! live_p)
2323 lra_clear_live_ranges ();
2326 bitmap_clear (&lra_optional_reload_pseudos);
2327 bitmap_clear (&lra_inheritance_pseudos);
2328 bitmap_clear (&lra_split_regs);
2329 if (! lra_need_for_spills_p ())
2330 break;
2331 if (! live_p)
2333 /* We need full live info for spilling pseudos into
2334 registers instead of memory. */
2335 lra_create_live_ranges (lra_reg_spill_p);
2336 live_p = true;
2338 lra_spill ();
2339 /* Assignment of stack slots changes elimination offsets for
2340 some eliminations. So update the offsets here. */
2341 lra_eliminate (false);
2342 lra_constraint_new_regno_start = max_reg_num ();
2343 lra_constraint_new_insn_uid_start = get_max_uid ();
2344 lra_constraint_iter_after_spill = 0;
2346 restore_scratches ();
2347 lra_eliminate (true);
2348 lra_final_code_change ();
2349 lra_in_progress = 0;
2350 if (live_p)
2351 lra_clear_live_ranges ();
2352 lra_live_ranges_finish ();
2353 lra_constraints_finish ();
2354 finish_reg_info ();
2355 sbitmap_free (lra_constraint_insn_stack_bitmap);
2356 lra_constraint_insn_stack.release ();
2357 finish_insn_recog_data ();
2358 regstat_free_n_sets_and_refs ();
2359 regstat_free_ri ();
2360 reload_completed = 1;
2361 update_inc_notes ();
2363 inserted_p = fixup_abnormal_edges ();
2365 /* We've possibly turned single trapping insn into multiple ones. */
2366 if (cfun->can_throw_non_call_exceptions)
2368 sbitmap blocks;
2369 blocks = sbitmap_alloc (last_basic_block);
2370 bitmap_ones (blocks);
2371 find_many_sub_basic_blocks (blocks);
2372 sbitmap_free (blocks);
2375 if (inserted_p)
2376 commit_edge_insertions ();
2378 /* Replacing pseudos with their memory equivalents might have
2379 created shared rtx. Subsequent passes would get confused
2380 by this, so unshare everything here. */
2381 unshare_all_rtl_again (get_insns ());
2383 #ifdef ENABLE_CHECKING
2384 check_rtl (true);
2385 #endif
2387 timevar_pop (TV_LRA);
2390 /* Called once per compiler to initialize LRA data once. */
2391 void
2392 lra_init_once (void)
2394 init_insn_code_data_once ();
2397 /* Initialize LRA whenever register-related information is changed. */
2398 void
2399 lra_init (void)
2401 init_op_alt_data ();
2404 /* Called once per compiler to finish LRA data which are initialize
2405 once. */
2406 void
2407 lra_finish_once (void)
2409 finish_insn_code_data_once ();