PR target/61794
[official-gcc.git] / gcc / lra.c
blob6442b1d751421901257a3f8fc0fac16b690e7a7b
1 /* LRA (local register allocator) driver and LRA utilities.
2 Copyright (C) 2010-2014 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 for | ---------------
48 | Memory-memory | | spilled pseudos, | | New (and old) |
49 | move coalesce |<---| splits for pseudos got |<-- | pseudos |
50 --------------- | the same hard regs, | | assignment |
51 Start | | and optional reloads | ---------------
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 (int old)
135 resize_reg_info ();
136 expand_reg_info ();
137 ira_expand_reg_equiv ();
138 for (int i = (int) max_reg_num () - 1; i >= old; i--)
139 lra_change_class (i, ALL_REGS, " Set", true);
142 /* Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL
143 or of VOIDmode, use MD_MODE for the new reg. Initialize its
144 register class to RCLASS. Print message about assigning class
145 RCLASS containing new register name TITLE unless it is NULL. Use
146 attributes of ORIGINAL if it is a register. The created register
147 will have unique held value. */
149 lra_create_new_reg_with_unique_value (enum machine_mode md_mode, rtx original,
150 enum reg_class rclass, const char *title)
152 enum machine_mode mode;
153 rtx new_reg;
155 if (original == NULL_RTX || (mode = GET_MODE (original)) == VOIDmode)
156 mode = md_mode;
157 lra_assert (mode != VOIDmode);
158 new_reg = gen_reg_rtx (mode);
159 if (original == NULL_RTX || ! REG_P (original))
161 if (lra_dump_file != NULL)
162 fprintf (lra_dump_file, " Creating newreg=%i", REGNO (new_reg));
164 else
166 if (ORIGINAL_REGNO (original) >= FIRST_PSEUDO_REGISTER)
167 ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original);
168 REG_USERVAR_P (new_reg) = REG_USERVAR_P (original);
169 REG_POINTER (new_reg) = REG_POINTER (original);
170 REG_ATTRS (new_reg) = REG_ATTRS (original);
171 if (lra_dump_file != NULL)
172 fprintf (lra_dump_file, " Creating newreg=%i from oldreg=%i",
173 REGNO (new_reg), REGNO (original));
175 if (lra_dump_file != NULL)
177 if (title != NULL)
178 fprintf (lra_dump_file, ", assigning class %s to%s%s r%d",
179 reg_class_names[rclass], *title == '\0' ? "" : " ",
180 title, REGNO (new_reg));
181 fprintf (lra_dump_file, "\n");
183 expand_reg_data (max_reg_num ());
184 setup_reg_classes (REGNO (new_reg), rclass, NO_REGS, rclass);
185 return new_reg;
188 /* Analogous to the previous function but also inherits value of
189 ORIGINAL. */
191 lra_create_new_reg (enum machine_mode md_mode, rtx original,
192 enum reg_class rclass, const char *title)
194 rtx new_reg;
196 new_reg
197 = lra_create_new_reg_with_unique_value (md_mode, original, rclass, title);
198 if (original != NULL_RTX && REG_P (original))
199 lra_assign_reg_val (REGNO (original), REGNO (new_reg));
200 return new_reg;
203 /* Set up for REGNO unique hold value. */
204 void
205 lra_set_regno_unique_value (int regno)
207 lra_reg_info[regno].val = get_new_reg_value ();
210 /* Invalidate INSN related info used by LRA. The info should never be
211 used after that. */
212 void
213 lra_invalidate_insn_data (rtx insn)
215 lra_invalidate_insn_regno_info (insn);
216 invalidate_insn_recog_data (INSN_UID (insn));
219 /* Mark INSN deleted and invalidate the insn related info used by
220 LRA. */
221 void
222 lra_set_insn_deleted (rtx insn)
224 lra_invalidate_insn_data (insn);
225 SET_INSN_DELETED (insn);
228 /* Delete an unneeded INSN and any previous insns who sole purpose is
229 loading data that is dead in INSN. */
230 void
231 lra_delete_dead_insn (rtx insn)
233 rtx prev = prev_real_insn (insn);
234 rtx prev_dest;
236 /* If the previous insn sets a register that dies in our insn,
237 delete it too. */
238 if (prev && GET_CODE (PATTERN (prev)) == SET
239 && (prev_dest = SET_DEST (PATTERN (prev)), REG_P (prev_dest))
240 && reg_mentioned_p (prev_dest, PATTERN (insn))
241 && find_regno_note (insn, REG_DEAD, REGNO (prev_dest))
242 && ! side_effects_p (SET_SRC (PATTERN (prev))))
243 lra_delete_dead_insn (prev);
245 lra_set_insn_deleted (insn);
248 /* Emit insn x = y + z. Return NULL if we failed to do it.
249 Otherwise, return the insn. We don't use gen_add3_insn as it might
250 clobber CC. */
251 static rtx
252 emit_add3_insn (rtx x, rtx y, rtx z)
254 rtx insn, last;
256 last = get_last_insn ();
258 if (have_addptr3_insn (x, y, z))
260 insn = gen_addptr3_insn (x, y, z);
262 /* If the target provides an "addptr" pattern it hopefully does
263 for a reason. So falling back to the normal add would be
264 a bug. */
265 lra_assert (insn != NULL_RTX);
266 emit_insn (insn);
267 return insn;
270 insn = emit_insn (gen_rtx_SET (VOIDmode, x,
271 gen_rtx_PLUS (GET_MODE (y), y, z)));
272 if (recog_memoized (insn) < 0)
274 delete_insns_since (last);
275 insn = NULL_RTX;
277 return insn;
280 /* Emit insn x = x + y. Return the insn. We use gen_add2_insn as the
281 last resort. */
282 static rtx
283 emit_add2_insn (rtx x, rtx y)
285 rtx insn;
287 insn = emit_add3_insn (x, x, y);
288 if (insn == NULL_RTX)
290 insn = gen_add2_insn (x, y);
291 if (insn != NULL_RTX)
292 emit_insn (insn);
294 return insn;
297 /* Target checks operands through operand predicates to recognize an
298 insn. We should have a special precaution to generate add insns
299 which are frequent results of elimination.
301 Emit insns for x = y + z. X can be used to store intermediate
302 values and should be not in Y and Z when we use X to store an
303 intermediate value. Y + Z should form [base] [+ index[ * scale]] [
304 + disp] where base and index are registers, disp and scale are
305 constants. Y should contain base if it is present, Z should
306 contain disp if any. index[*scale] can be part of Y or Z. */
307 void
308 lra_emit_add (rtx x, rtx y, rtx z)
310 int old;
311 rtx insn, last;
312 rtx a1, a2, base, index, disp, scale, index_scale;
313 bool ok_p;
315 insn = emit_add3_insn (x, y, z);
316 old = max_reg_num ();
317 if (insn != NULL_RTX)
319 else
321 disp = a2 = NULL_RTX;
322 if (GET_CODE (y) == PLUS)
324 a1 = XEXP (y, 0);
325 a2 = XEXP (y, 1);
326 disp = z;
328 else
330 a1 = y;
331 if (CONSTANT_P (z))
332 disp = z;
333 else
334 a2 = z;
336 index_scale = scale = NULL_RTX;
337 if (GET_CODE (a1) == MULT)
339 index_scale = a1;
340 index = XEXP (a1, 0);
341 scale = XEXP (a1, 1);
342 base = a2;
344 else if (a2 != NULL_RTX && GET_CODE (a2) == MULT)
346 index_scale = a2;
347 index = XEXP (a2, 0);
348 scale = XEXP (a2, 1);
349 base = a1;
351 else
353 base = a1;
354 index = a2;
356 if (! (REG_P (base) || GET_CODE (base) == SUBREG)
357 || (index != NULL_RTX
358 && ! (REG_P (index) || GET_CODE (index) == SUBREG))
359 || (disp != NULL_RTX && ! CONSTANT_P (disp))
360 || (scale != NULL_RTX && ! CONSTANT_P (scale)))
362 /* Probably we have no 3 op add. Last chance is to use 2-op
363 add insn. To succeed, don't move Z to X as an address
364 segment always comes in Y. Otherwise, we might fail when
365 adding the address segment to register. */
366 lra_assert (x != y && x != z);
367 emit_move_insn (x, y);
368 insn = emit_add2_insn (x, z);
369 lra_assert (insn != NULL_RTX);
371 else
373 if (index_scale == NULL_RTX)
374 index_scale = index;
375 if (disp == NULL_RTX)
377 /* Generate x = index_scale; x = x + base. */
378 lra_assert (index_scale != NULL_RTX && base != NULL_RTX);
379 emit_move_insn (x, index_scale);
380 insn = emit_add2_insn (x, base);
381 lra_assert (insn != NULL_RTX);
383 else if (scale == NULL_RTX)
385 /* Try x = base + disp. */
386 lra_assert (base != NULL_RTX);
387 last = get_last_insn ();
388 insn = emit_move_insn (x, gen_rtx_PLUS (GET_MODE (base),
389 base, disp));
390 if (recog_memoized (insn) < 0)
392 delete_insns_since (last);
393 /* Generate x = disp; x = x + base. */
394 emit_move_insn (x, disp);
395 insn = emit_add2_insn (x, base);
396 lra_assert (insn != NULL_RTX);
398 /* Generate x = x + index. */
399 if (index != NULL_RTX)
401 insn = emit_add2_insn (x, index);
402 lra_assert (insn != NULL_RTX);
405 else
407 /* Try x = index_scale; x = x + disp; x = x + base. */
408 last = get_last_insn ();
409 insn = emit_move_insn (x, index_scale);
410 ok_p = false;
411 if (recog_memoized (insn) >= 0)
413 insn = emit_add2_insn (x, disp);
414 if (insn != NULL_RTX)
416 insn = emit_add2_insn (x, disp);
417 if (insn != NULL_RTX)
418 ok_p = true;
421 if (! ok_p)
423 delete_insns_since (last);
424 /* Generate x = disp; x = x + base; x = x + index_scale. */
425 emit_move_insn (x, disp);
426 insn = emit_add2_insn (x, base);
427 lra_assert (insn != NULL_RTX);
428 insn = emit_add2_insn (x, index_scale);
429 lra_assert (insn != NULL_RTX);
434 /* Functions emit_... can create pseudos -- so expand the pseudo
435 data. */
436 if (old != max_reg_num ())
437 expand_reg_data (old);
440 /* The number of emitted reload insns so far. */
441 int lra_curr_reload_num;
443 /* Emit x := y, processing special case when y = u + v or y = u + v *
444 scale + w through emit_add (Y can be an address which is base +
445 index reg * scale + displacement in general case). X may be used
446 as intermediate result therefore it should be not in Y. */
447 void
448 lra_emit_move (rtx x, rtx y)
450 int old;
452 if (GET_CODE (y) != PLUS)
454 if (rtx_equal_p (x, y))
455 return;
456 old = max_reg_num ();
457 emit_move_insn (x, y);
458 if (REG_P (x))
459 lra_reg_info[ORIGINAL_REGNO (x)].last_reload = ++lra_curr_reload_num;
460 /* Function emit_move can create pseudos -- so expand the pseudo
461 data. */
462 if (old != max_reg_num ())
463 expand_reg_data (old);
464 return;
466 lra_emit_add (x, XEXP (y, 0), XEXP (y, 1));
469 /* Update insn operands which are duplication of operands whose
470 numbers are in array of NOPS (with end marker -1). The insn is
471 represented by its LRA internal representation ID. */
472 void
473 lra_update_dups (lra_insn_recog_data_t id, signed char *nops)
475 int i, j, nop;
476 struct lra_static_insn_data *static_id = id->insn_static_data;
478 for (i = 0; i < static_id->n_dups; i++)
479 for (j = 0; (nop = nops[j]) >= 0; j++)
480 if (static_id->dup_num[i] == nop)
481 *id->dup_loc[i] = *id->operand_loc[nop];
486 /* This page contains code dealing with info about registers in the
487 insns. */
489 /* Pools for insn reg info. */
490 static alloc_pool insn_reg_pool;
492 /* Initiate pool for insn reg info. */
493 static void
494 init_insn_regs (void)
496 insn_reg_pool
497 = create_alloc_pool ("insn regs", sizeof (struct lra_insn_reg), 100);
500 /* Create LRA insn related info about a reference to REGNO in INSN with
501 TYPE (in/out/inout), biggest reference mode MODE, flag that it is
502 reference through subreg (SUBREG_P), flag that is early clobbered
503 in the insn (EARLY_CLOBBER), and reference to the next insn reg
504 info (NEXT). */
505 static struct lra_insn_reg *
506 new_insn_reg (rtx insn, int regno, enum op_type type, enum machine_mode mode,
507 bool subreg_p, bool early_clobber, struct lra_insn_reg *next)
509 struct lra_insn_reg *ir;
511 ir = (struct lra_insn_reg *) pool_alloc (insn_reg_pool);
512 ir->type = type;
513 ir->biggest_mode = mode;
514 if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (lra_reg_info[regno].biggest_mode)
515 && NONDEBUG_INSN_P (insn))
516 lra_reg_info[regno].biggest_mode = mode;
517 ir->subreg_p = subreg_p;
518 ir->early_clobber = early_clobber;
519 ir->regno = regno;
520 ir->next = next;
521 return ir;
524 /* Free insn reg info IR. */
525 static void
526 free_insn_reg (struct lra_insn_reg *ir)
528 pool_free (insn_reg_pool, ir);
531 /* Free insn reg info list IR. */
532 static void
533 free_insn_regs (struct lra_insn_reg *ir)
535 struct lra_insn_reg *next_ir;
537 for (; ir != NULL; ir = next_ir)
539 next_ir = ir->next;
540 free_insn_reg (ir);
544 /* Finish pool for insn reg info. */
545 static void
546 finish_insn_regs (void)
548 free_alloc_pool (insn_reg_pool);
553 /* This page contains code dealing LRA insn info (or in other words
554 LRA internal insn representation). */
556 /* Map INSN_CODE -> the static insn data. This info is valid during
557 all translation unit. */
558 struct lra_static_insn_data *insn_code_data[LAST_INSN_CODE];
560 /* Debug insns are represented as a special insn with one input
561 operand which is RTL expression in var_location. */
563 /* The following data are used as static insn operand data for all
564 debug insns. If structure lra_operand_data is changed, the
565 initializer should be changed too. */
566 static struct lra_operand_data debug_operand_data =
568 NULL, /* alternative */
569 VOIDmode, /* We are not interesting in the operand mode. */
570 OP_IN,
571 0, 0, 0, 0
574 /* The following data are used as static insn data for all debug
575 insns. If structure lra_static_insn_data is changed, the
576 initializer should be changed too. */
577 static struct lra_static_insn_data debug_insn_static_data =
579 &debug_operand_data,
580 0, /* Duplication operands #. */
581 -1, /* Commutative operand #. */
582 1, /* Operands #. There is only one operand which is debug RTL
583 expression. */
584 0, /* Duplications #. */
585 0, /* Alternatives #. We are not interesting in alternatives
586 because we does not proceed debug_insns for reloads. */
587 NULL, /* Hard registers referenced in machine description. */
588 NULL /* Descriptions of operands in alternatives. */
591 /* Called once per compiler work to initialize some LRA data related
592 to insns. */
593 static void
594 init_insn_code_data_once (void)
596 memset (insn_code_data, 0, sizeof (insn_code_data));
599 /* Called once per compiler work to finalize some LRA data related to
600 insns. */
601 static void
602 finish_insn_code_data_once (void)
604 int i;
606 for (i = 0; i < LAST_INSN_CODE; i++)
608 if (insn_code_data[i] != NULL)
609 free (insn_code_data[i]);
613 /* Return static insn data, allocate and setup if necessary. Although
614 dup_num is static data (it depends only on icode), to set it up we
615 need to extract insn first. So recog_data should be valid for
616 normal insn (ICODE >= 0) before the call. */
617 static struct lra_static_insn_data *
618 get_static_insn_data (int icode, int nop, int ndup, int nalt)
620 struct lra_static_insn_data *data;
621 size_t n_bytes;
623 lra_assert (icode < LAST_INSN_CODE);
624 if (icode >= 0 && (data = insn_code_data[icode]) != NULL)
625 return data;
626 lra_assert (nop >= 0 && ndup >= 0 && nalt >= 0);
627 n_bytes = sizeof (struct lra_static_insn_data)
628 + sizeof (struct lra_operand_data) * nop
629 + sizeof (int) * ndup;
630 data = XNEWVAR (struct lra_static_insn_data, n_bytes);
631 data->operand_alternative = NULL;
632 data->n_operands = nop;
633 data->n_dups = ndup;
634 data->n_alternatives = nalt;
635 data->operand = ((struct lra_operand_data *)
636 ((char *) data + sizeof (struct lra_static_insn_data)));
637 data->dup_num = ((int *) ((char *) data->operand
638 + sizeof (struct lra_operand_data) * nop));
639 if (icode >= 0)
641 int i;
643 insn_code_data[icode] = data;
644 for (i = 0; i < nop; i++)
646 data->operand[i].constraint
647 = insn_data[icode].operand[i].constraint;
648 data->operand[i].mode = insn_data[icode].operand[i].mode;
649 data->operand[i].strict_low = insn_data[icode].operand[i].strict_low;
650 data->operand[i].is_operator
651 = insn_data[icode].operand[i].is_operator;
652 data->operand[i].type
653 = (data->operand[i].constraint[0] == '=' ? OP_OUT
654 : data->operand[i].constraint[0] == '+' ? OP_INOUT
655 : OP_IN);
656 data->operand[i].is_address = false;
658 for (i = 0; i < ndup; i++)
659 data->dup_num[i] = recog_data.dup_num[i];
661 return data;
664 /* The current length of the following array. */
665 int lra_insn_recog_data_len;
667 /* Map INSN_UID -> the insn recog data (NULL if unknown). */
668 lra_insn_recog_data_t *lra_insn_recog_data;
670 /* Initialize LRA data about insns. */
671 static void
672 init_insn_recog_data (void)
674 lra_insn_recog_data_len = 0;
675 lra_insn_recog_data = NULL;
676 init_insn_regs ();
679 /* Expand, if necessary, LRA data about insns. */
680 static void
681 check_and_expand_insn_recog_data (int index)
683 int i, old;
685 if (lra_insn_recog_data_len > index)
686 return;
687 old = lra_insn_recog_data_len;
688 lra_insn_recog_data_len = index * 3 / 2 + 1;
689 lra_insn_recog_data = XRESIZEVEC (lra_insn_recog_data_t,
690 lra_insn_recog_data,
691 lra_insn_recog_data_len);
692 for (i = old; i < lra_insn_recog_data_len; i++)
693 lra_insn_recog_data[i] = NULL;
696 /* Finish LRA DATA about insn. */
697 static void
698 free_insn_recog_data (lra_insn_recog_data_t data)
700 if (data->operand_loc != NULL)
701 free (data->operand_loc);
702 if (data->dup_loc != NULL)
703 free (data->dup_loc);
704 if (data->arg_hard_regs != NULL)
705 free (data->arg_hard_regs);
706 if (data->icode < 0 && NONDEBUG_INSN_P (data->insn))
708 if (data->insn_static_data->operand_alternative != NULL)
709 free (const_cast <operand_alternative *>
710 (data->insn_static_data->operand_alternative));
711 free_insn_regs (data->insn_static_data->hard_regs);
712 free (data->insn_static_data);
714 free_insn_regs (data->regs);
715 data->regs = NULL;
716 free (data);
719 /* Finish LRA data about all insns. */
720 static void
721 finish_insn_recog_data (void)
723 int i;
724 lra_insn_recog_data_t data;
726 for (i = 0; i < lra_insn_recog_data_len; i++)
727 if ((data = lra_insn_recog_data[i]) != NULL)
728 free_insn_recog_data (data);
729 finish_insn_regs ();
730 free (lra_insn_recog_data);
733 /* Setup info about operands in alternatives of LRA DATA of insn. */
734 static void
735 setup_operand_alternative (lra_insn_recog_data_t data,
736 const operand_alternative *op_alt)
738 int i, j, nop, nalt;
739 int icode = data->icode;
740 struct lra_static_insn_data *static_data = data->insn_static_data;
742 static_data->commutative = -1;
743 nop = static_data->n_operands;
744 nalt = static_data->n_alternatives;
745 static_data->operand_alternative = op_alt;
746 for (i = 0; i < nop; i++)
748 static_data->operand[i].early_clobber = false;
749 static_data->operand[i].is_address = false;
750 if (static_data->operand[i].constraint[0] == '%')
752 /* We currently only support one commutative pair of operands. */
753 if (static_data->commutative < 0)
754 static_data->commutative = i;
755 else
756 lra_assert (icode < 0); /* Asm */
757 /* The last operand should not be marked commutative. */
758 lra_assert (i != nop - 1);
761 for (j = 0; j < nalt; j++)
762 for (i = 0; i < nop; i++, op_alt++)
764 static_data->operand[i].early_clobber |= op_alt->earlyclobber;
765 static_data->operand[i].is_address |= op_alt->is_address;
769 /* Recursively process X and collect info about registers, which are
770 not the insn operands, in X with TYPE (in/out/inout) and flag that
771 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
772 to LIST. X is a part of insn given by DATA. Return the result
773 list. */
774 static struct lra_insn_reg *
775 collect_non_operand_hard_regs (rtx *x, lra_insn_recog_data_t data,
776 struct lra_insn_reg *list,
777 enum op_type type, bool early_clobber)
779 int i, j, regno, last;
780 bool subreg_p;
781 enum machine_mode mode;
782 struct lra_insn_reg *curr;
783 rtx op = *x;
784 enum rtx_code code = GET_CODE (op);
785 const char *fmt = GET_RTX_FORMAT (code);
787 for (i = 0; i < data->insn_static_data->n_operands; i++)
788 if (x == data->operand_loc[i])
789 /* It is an operand loc. Stop here. */
790 return list;
791 for (i = 0; i < data->insn_static_data->n_dups; i++)
792 if (x == data->dup_loc[i])
793 /* It is a dup loc. Stop here. */
794 return list;
795 mode = GET_MODE (op);
796 subreg_p = false;
797 if (code == SUBREG)
799 op = SUBREG_REG (op);
800 code = GET_CODE (op);
801 if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (op)))
803 mode = GET_MODE (op);
804 if (GET_MODE_SIZE (mode) > REGMODE_NATURAL_SIZE (mode))
805 subreg_p = true;
808 if (REG_P (op))
810 if ((regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER)
811 return list;
812 for (last = regno + hard_regno_nregs[regno][mode];
813 regno < last;
814 regno++)
815 if (! TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
816 || TEST_HARD_REG_BIT (eliminable_regset, regno))
818 for (curr = list; curr != NULL; curr = curr->next)
819 if (curr->regno == regno && curr->subreg_p == subreg_p
820 && curr->biggest_mode == mode)
822 if (curr->type != type)
823 curr->type = OP_INOUT;
824 if (curr->early_clobber != early_clobber)
825 curr->early_clobber = true;
826 break;
828 if (curr == NULL)
830 /* This is a new hard regno or the info can not be
831 integrated into the found structure. */
832 #ifdef STACK_REGS
833 early_clobber
834 = (early_clobber
835 /* This clobber is to inform popping floating
836 point stack only. */
837 && ! (FIRST_STACK_REG <= regno
838 && regno <= LAST_STACK_REG));
839 #endif
840 list = new_insn_reg (data->insn, regno, type, mode, subreg_p,
841 early_clobber, list);
844 return list;
846 switch (code)
848 case SET:
849 list = collect_non_operand_hard_regs (&SET_DEST (op), data,
850 list, OP_OUT, false);
851 list = collect_non_operand_hard_regs (&SET_SRC (op), data,
852 list, OP_IN, false);
853 break;
854 case CLOBBER:
855 /* We treat clobber of non-operand hard registers as early
856 clobber (the behavior is expected from asm). */
857 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
858 list, OP_OUT, true);
859 break;
860 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
861 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
862 list, OP_INOUT, false);
863 break;
864 case PRE_MODIFY: case POST_MODIFY:
865 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
866 list, OP_INOUT, false);
867 list = collect_non_operand_hard_regs (&XEXP (op, 1), data,
868 list, OP_IN, false);
869 break;
870 default:
871 fmt = GET_RTX_FORMAT (code);
872 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
874 if (fmt[i] == 'e')
875 list = collect_non_operand_hard_regs (&XEXP (op, i), data,
876 list, OP_IN, false);
877 else if (fmt[i] == 'E')
878 for (j = XVECLEN (op, i) - 1; j >= 0; j--)
879 list = collect_non_operand_hard_regs (&XVECEXP (op, i, j), data,
880 list, OP_IN, false);
883 return list;
886 /* Set up and return info about INSN. Set up the info if it is not set up
887 yet. */
888 lra_insn_recog_data_t
889 lra_set_insn_recog_data (rtx insn)
891 lra_insn_recog_data_t data;
892 int i, n, icode;
893 rtx **locs;
894 unsigned int uid = INSN_UID (insn);
895 struct lra_static_insn_data *insn_static_data;
897 check_and_expand_insn_recog_data (uid);
898 if (DEBUG_INSN_P (insn))
899 icode = -1;
900 else
902 icode = INSN_CODE (insn);
903 if (icode < 0)
904 /* It might be a new simple insn which is not recognized yet. */
905 INSN_CODE (insn) = icode = recog_memoized (insn);
907 data = XNEW (struct lra_insn_recog_data);
908 lra_insn_recog_data[uid] = data;
909 data->insn = insn;
910 data->used_insn_alternative = -1;
911 data->icode = icode;
912 data->regs = NULL;
913 if (DEBUG_INSN_P (insn))
915 data->insn_static_data = &debug_insn_static_data;
916 data->dup_loc = NULL;
917 data->arg_hard_regs = NULL;
918 data->enabled_alternatives = ALL_ALTERNATIVES;
919 data->operand_loc = XNEWVEC (rtx *, 1);
920 data->operand_loc[0] = &INSN_VAR_LOCATION_LOC (insn);
921 return data;
923 if (icode < 0)
925 int nop, nalt;
926 enum machine_mode operand_mode[MAX_RECOG_OPERANDS];
927 const char *constraints[MAX_RECOG_OPERANDS];
929 nop = asm_noperands (PATTERN (insn));
930 data->operand_loc = data->dup_loc = NULL;
931 nalt = 1;
932 if (nop < 0)
934 /* Its is a special insn like USE or CLOBBER. We should
935 recognize any regular insn otherwise LRA can do nothing
936 with this insn. */
937 gcc_assert (GET_CODE (PATTERN (insn)) == USE
938 || GET_CODE (PATTERN (insn)) == CLOBBER
939 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
940 data->insn_static_data = insn_static_data
941 = get_static_insn_data (-1, 0, 0, nalt);
943 else
945 /* expand_asm_operands makes sure there aren't too many
946 operands. */
947 lra_assert (nop <= MAX_RECOG_OPERANDS);
948 if (nop != 0)
949 data->operand_loc = XNEWVEC (rtx *, nop);
950 /* Now get the operand values and constraints out of the
951 insn. */
952 decode_asm_operands (PATTERN (insn), NULL,
953 data->operand_loc,
954 constraints, operand_mode, NULL);
955 if (nop > 0)
957 const char *p = recog_data.constraints[0];
959 for (p = constraints[0]; *p; p++)
960 nalt += *p == ',';
962 data->insn_static_data = insn_static_data
963 = get_static_insn_data (-1, nop, 0, nalt);
964 for (i = 0; i < nop; i++)
966 insn_static_data->operand[i].mode = operand_mode[i];
967 insn_static_data->operand[i].constraint = constraints[i];
968 insn_static_data->operand[i].strict_low = false;
969 insn_static_data->operand[i].is_operator = false;
970 insn_static_data->operand[i].is_address = false;
973 for (i = 0; i < insn_static_data->n_operands; i++)
974 insn_static_data->operand[i].type
975 = (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
976 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
977 : OP_IN);
978 data->enabled_alternatives = ALL_ALTERNATIVES;
979 if (nop > 0)
981 operand_alternative *op_alt = XCNEWVEC (operand_alternative,
982 nalt * nop);
983 preprocess_constraints (nop, nalt, constraints, op_alt);
984 setup_operand_alternative (data, op_alt);
987 else
989 insn_extract (insn);
990 data->insn_static_data = insn_static_data
991 = get_static_insn_data (icode, insn_data[icode].n_operands,
992 insn_data[icode].n_dups,
993 insn_data[icode].n_alternatives);
994 n = insn_static_data->n_operands;
995 if (n == 0)
996 locs = NULL;
997 else
999 locs = XNEWVEC (rtx *, n);
1000 memcpy (locs, recog_data.operand_loc, n * sizeof (rtx *));
1002 data->operand_loc = locs;
1003 n = insn_static_data->n_dups;
1004 if (n == 0)
1005 locs = NULL;
1006 else
1008 locs = XNEWVEC (rtx *, n);
1009 memcpy (locs, recog_data.dup_loc, n * sizeof (rtx *));
1011 data->dup_loc = locs;
1012 data->enabled_alternatives = get_enabled_alternatives (insn);
1013 const operand_alternative *op_alt = preprocess_insn_constraints (icode);
1014 if (!insn_static_data->operand_alternative)
1015 setup_operand_alternative (data, op_alt);
1016 else if (op_alt != insn_static_data->operand_alternative)
1017 insn_static_data->operand_alternative = op_alt;
1019 if (GET_CODE (PATTERN (insn)) == CLOBBER || GET_CODE (PATTERN (insn)) == USE)
1020 insn_static_data->hard_regs = NULL;
1021 else
1022 insn_static_data->hard_regs
1023 = collect_non_operand_hard_regs (&PATTERN (insn), data,
1024 NULL, OP_IN, false);
1025 data->arg_hard_regs = NULL;
1026 if (CALL_P (insn))
1028 rtx link;
1029 int n_hard_regs, regno, arg_hard_regs[FIRST_PSEUDO_REGISTER];
1031 n_hard_regs = 0;
1032 /* Finding implicit hard register usage. We believe it will be
1033 not changed whatever transformations are used. Call insns
1034 are such example. */
1035 for (link = CALL_INSN_FUNCTION_USAGE (insn);
1036 link != NULL_RTX;
1037 link = XEXP (link, 1))
1038 if (GET_CODE (XEXP (link, 0)) == USE
1039 && REG_P (XEXP (XEXP (link, 0), 0)))
1041 regno = REGNO (XEXP (XEXP (link, 0), 0));
1042 lra_assert (regno < FIRST_PSEUDO_REGISTER);
1043 /* It is an argument register. */
1044 for (i = (hard_regno_nregs
1045 [regno][GET_MODE (XEXP (XEXP (link, 0), 0))]) - 1;
1046 i >= 0;
1047 i--)
1048 arg_hard_regs[n_hard_regs++] = regno + i;
1050 if (n_hard_regs != 0)
1052 arg_hard_regs[n_hard_regs++] = -1;
1053 data->arg_hard_regs = XNEWVEC (int, n_hard_regs);
1054 memcpy (data->arg_hard_regs, arg_hard_regs,
1055 sizeof (int) * n_hard_regs);
1058 /* Some output operand can be recognized only from the context not
1059 from the constraints which are empty in this case. Call insn may
1060 contain a hard register in set destination with empty constraint
1061 and extract_insn treats them as an input. */
1062 for (i = 0; i < insn_static_data->n_operands; i++)
1064 int j;
1065 rtx pat, set;
1066 struct lra_operand_data *operand = &insn_static_data->operand[i];
1068 /* ??? Should we treat 'X' the same way. It looks to me that
1069 'X' means anything and empty constraint means we do not
1070 care. */
1071 if (operand->type != OP_IN || *operand->constraint != '\0'
1072 || operand->is_operator)
1073 continue;
1074 pat = PATTERN (insn);
1075 if (GET_CODE (pat) == SET)
1077 if (data->operand_loc[i] != &SET_DEST (pat))
1078 continue;
1080 else if (GET_CODE (pat) == PARALLEL)
1082 for (j = XVECLEN (pat, 0) - 1; j >= 0; j--)
1084 set = XVECEXP (PATTERN (insn), 0, j);
1085 if (GET_CODE (set) == SET
1086 && &SET_DEST (set) == data->operand_loc[i])
1087 break;
1089 if (j < 0)
1090 continue;
1092 else
1093 continue;
1094 operand->type = OP_OUT;
1096 return data;
1099 /* Return info about insn give by UID. The info should be already set
1100 up. */
1101 static lra_insn_recog_data_t
1102 get_insn_recog_data_by_uid (int uid)
1104 lra_insn_recog_data_t data;
1106 data = lra_insn_recog_data[uid];
1107 lra_assert (data != NULL);
1108 return data;
1111 /* Invalidate all info about insn given by its UID. */
1112 static void
1113 invalidate_insn_recog_data (int uid)
1115 lra_insn_recog_data_t data;
1117 data = lra_insn_recog_data[uid];
1118 lra_assert (data != NULL);
1119 free_insn_recog_data (data);
1120 lra_insn_recog_data[uid] = NULL;
1123 /* Update all the insn info about INSN. It is usually called when
1124 something in the insn was changed. Return the updated info. */
1125 lra_insn_recog_data_t
1126 lra_update_insn_recog_data (rtx insn)
1128 lra_insn_recog_data_t data;
1129 int n;
1130 unsigned int uid = INSN_UID (insn);
1131 struct lra_static_insn_data *insn_static_data;
1132 HOST_WIDE_INT sp_offset = 0;
1134 check_and_expand_insn_recog_data (uid);
1135 if ((data = lra_insn_recog_data[uid]) != NULL
1136 && data->icode != INSN_CODE (insn))
1138 sp_offset = data->sp_offset;
1139 invalidate_insn_data_regno_info (data, insn, get_insn_freq (insn));
1140 invalidate_insn_recog_data (uid);
1141 data = NULL;
1143 if (data == NULL)
1145 data = lra_get_insn_recog_data (insn);
1146 /* Initiate or restore SP offset. */
1147 data->sp_offset = sp_offset;
1148 return data;
1150 insn_static_data = data->insn_static_data;
1151 data->used_insn_alternative = -1;
1152 if (DEBUG_INSN_P (insn))
1153 return data;
1154 if (data->icode < 0)
1156 int nop;
1157 enum machine_mode operand_mode[MAX_RECOG_OPERANDS];
1158 const char *constraints[MAX_RECOG_OPERANDS];
1160 nop = asm_noperands (PATTERN (insn));
1161 if (nop >= 0)
1163 lra_assert (nop == data->insn_static_data->n_operands);
1164 /* Now get the operand values and constraints out of the
1165 insn. */
1166 decode_asm_operands (PATTERN (insn), NULL,
1167 data->operand_loc,
1168 constraints, operand_mode, NULL);
1169 #ifdef ENABLE_CHECKING
1171 int i;
1173 for (i = 0; i < nop; i++)
1174 lra_assert
1175 (insn_static_data->operand[i].mode == operand_mode[i]
1176 && insn_static_data->operand[i].constraint == constraints[i]
1177 && ! insn_static_data->operand[i].is_operator);
1179 #endif
1181 #ifdef ENABLE_CHECKING
1183 int i;
1185 for (i = 0; i < insn_static_data->n_operands; i++)
1186 lra_assert
1187 (insn_static_data->operand[i].type
1188 == (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1189 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1190 : OP_IN));
1192 #endif
1194 else
1196 insn_extract (insn);
1197 n = insn_static_data->n_operands;
1198 if (n != 0)
1199 memcpy (data->operand_loc, recog_data.operand_loc, n * sizeof (rtx *));
1200 n = insn_static_data->n_dups;
1201 if (n != 0)
1202 memcpy (data->dup_loc, recog_data.dup_loc, n * sizeof (rtx *));
1203 #if HAVE_ATTR_enabled
1204 #ifdef ENABLE_CHECKING
1206 int i;
1207 alternative_mask enabled;
1209 n = insn_static_data->n_alternatives;
1210 enabled = data->enabled_alternatives;
1211 lra_assert (n >= 0);
1212 /* Cache the insn to prevent extract_insn call from
1213 get_attr_enabled. */
1214 recog_data.insn = insn;
1215 for (i = 0; i < n; i++)
1217 which_alternative = i;
1218 lra_assert (TEST_BIT (enabled, i)
1219 == (bool) get_attr_enabled (insn));
1222 #endif
1223 #endif
1225 return data;
1228 /* Set up that INSN is using alternative ALT now. */
1229 void
1230 lra_set_used_insn_alternative (rtx insn, int alt)
1232 lra_insn_recog_data_t data;
1234 data = lra_get_insn_recog_data (insn);
1235 data->used_insn_alternative = alt;
1238 /* Set up that insn with UID is using alternative ALT now. The insn
1239 info should be already set up. */
1240 void
1241 lra_set_used_insn_alternative_by_uid (int uid, int alt)
1243 lra_insn_recog_data_t data;
1245 check_and_expand_insn_recog_data (uid);
1246 data = lra_insn_recog_data[uid];
1247 lra_assert (data != NULL);
1248 data->used_insn_alternative = alt;
1253 /* This page contains code dealing with common register info and
1254 pseudo copies. */
1256 /* The size of the following array. */
1257 static int reg_info_size;
1258 /* Common info about each register. */
1259 struct lra_reg *lra_reg_info;
1261 /* Last register value. */
1262 static int last_reg_value;
1264 /* Return new register value. */
1265 static int
1266 get_new_reg_value (void)
1268 return ++last_reg_value;
1271 /* Pools for copies. */
1272 static alloc_pool copy_pool;
1274 /* Vec referring to pseudo copies. */
1275 static vec<lra_copy_t> copy_vec;
1277 /* Initialize I-th element of lra_reg_info. */
1278 static inline void
1279 initialize_lra_reg_info_element (int i)
1281 bitmap_initialize (&lra_reg_info[i].insn_bitmap, &reg_obstack);
1282 #ifdef STACK_REGS
1283 lra_reg_info[i].no_stack_p = false;
1284 #endif
1285 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1286 CLEAR_HARD_REG_SET (lra_reg_info[i].actual_call_used_reg_set);
1287 lra_reg_info[i].preferred_hard_regno1 = -1;
1288 lra_reg_info[i].preferred_hard_regno2 = -1;
1289 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1290 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1291 lra_reg_info[i].biggest_mode = VOIDmode;
1292 lra_reg_info[i].live_ranges = NULL;
1293 lra_reg_info[i].nrefs = lra_reg_info[i].freq = 0;
1294 lra_reg_info[i].last_reload = 0;
1295 lra_reg_info[i].restore_regno = -1;
1296 lra_reg_info[i].val = get_new_reg_value ();
1297 lra_reg_info[i].offset = 0;
1298 lra_reg_info[i].copies = NULL;
1301 /* Initialize common reg info and copies. */
1302 static void
1303 init_reg_info (void)
1305 int i;
1307 last_reg_value = 0;
1308 reg_info_size = max_reg_num () * 3 / 2 + 1;
1309 lra_reg_info = XNEWVEC (struct lra_reg, reg_info_size);
1310 for (i = 0; i < reg_info_size; i++)
1311 initialize_lra_reg_info_element (i);
1312 copy_pool
1313 = create_alloc_pool ("lra copies", sizeof (struct lra_copy), 100);
1314 copy_vec.create (100);
1318 /* Finish common reg info and copies. */
1319 static void
1320 finish_reg_info (void)
1322 int i;
1324 for (i = 0; i < reg_info_size; i++)
1325 bitmap_clear (&lra_reg_info[i].insn_bitmap);
1326 free (lra_reg_info);
1327 reg_info_size = 0;
1328 free_alloc_pool (copy_pool);
1329 copy_vec.release ();
1332 /* Expand common reg info if it is necessary. */
1333 static void
1334 expand_reg_info (void)
1336 int i, old = reg_info_size;
1338 if (reg_info_size > max_reg_num ())
1339 return;
1340 reg_info_size = max_reg_num () * 3 / 2 + 1;
1341 lra_reg_info = XRESIZEVEC (struct lra_reg, lra_reg_info, reg_info_size);
1342 for (i = old; i < reg_info_size; i++)
1343 initialize_lra_reg_info_element (i);
1346 /* Free all copies. */
1347 void
1348 lra_free_copies (void)
1350 lra_copy_t cp;
1352 while (copy_vec.length () != 0)
1354 cp = copy_vec.pop ();
1355 lra_reg_info[cp->regno1].copies = lra_reg_info[cp->regno2].copies = NULL;
1356 pool_free (copy_pool, cp);
1360 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1361 frequency is FREQ. */
1362 void
1363 lra_create_copy (int regno1, int regno2, int freq)
1365 bool regno1_dest_p;
1366 lra_copy_t cp;
1368 lra_assert (regno1 != regno2);
1369 regno1_dest_p = true;
1370 if (regno1 > regno2)
1372 int temp = regno2;
1374 regno1_dest_p = false;
1375 regno2 = regno1;
1376 regno1 = temp;
1378 cp = (lra_copy_t) pool_alloc (copy_pool);
1379 copy_vec.safe_push (cp);
1380 cp->regno1_dest_p = regno1_dest_p;
1381 cp->freq = freq;
1382 cp->regno1 = regno1;
1383 cp->regno2 = regno2;
1384 cp->regno1_next = lra_reg_info[regno1].copies;
1385 lra_reg_info[regno1].copies = cp;
1386 cp->regno2_next = lra_reg_info[regno2].copies;
1387 lra_reg_info[regno2].copies = cp;
1388 if (lra_dump_file != NULL)
1389 fprintf (lra_dump_file, " Creating copy r%d%sr%d@%d\n",
1390 regno1, regno1_dest_p ? "<-" : "->", regno2, freq);
1393 /* Return N-th (0, 1, ...) copy. If there is no copy, return
1394 NULL. */
1395 lra_copy_t
1396 lra_get_copy (int n)
1398 if (n >= (int) copy_vec.length ())
1399 return NULL;
1400 return copy_vec[n];
1405 /* This page contains code dealing with info about registers in
1406 insns. */
1408 /* Process X of insn UID recursively and add info (operand type is
1409 given by TYPE, flag of that it is early clobber is EARLY_CLOBBER)
1410 about registers in X to the insn DATA. */
1411 static void
1412 add_regs_to_insn_regno_info (lra_insn_recog_data_t data, rtx x, int uid,
1413 enum op_type type, bool early_clobber)
1415 int i, j, regno;
1416 bool subreg_p;
1417 enum machine_mode mode;
1418 const char *fmt;
1419 enum rtx_code code;
1420 struct lra_insn_reg *curr;
1422 code = GET_CODE (x);
1423 mode = GET_MODE (x);
1424 subreg_p = false;
1425 if (GET_CODE (x) == SUBREG)
1427 x = SUBREG_REG (x);
1428 code = GET_CODE (x);
1429 if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (x)))
1431 mode = GET_MODE (x);
1432 if (GET_MODE_SIZE (mode) > REGMODE_NATURAL_SIZE (mode))
1433 subreg_p = true;
1436 if (REG_P (x))
1438 regno = REGNO (x);
1439 if (regno < FIRST_PSEUDO_REGISTER
1440 && TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
1441 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
1442 return;
1443 expand_reg_info ();
1444 if (bitmap_set_bit (&lra_reg_info[regno].insn_bitmap, uid))
1446 data->regs = new_insn_reg (data->insn, regno, type, mode, subreg_p,
1447 early_clobber, data->regs);
1448 return;
1450 else
1452 for (curr = data->regs; curr != NULL; curr = curr->next)
1453 if (curr->regno == regno)
1455 if (curr->subreg_p != subreg_p || curr->biggest_mode != mode)
1456 /* The info can not be integrated into the found
1457 structure. */
1458 data->regs = new_insn_reg (data->insn, regno, type, mode,
1459 subreg_p, early_clobber,
1460 data->regs);
1461 else
1463 if (curr->type != type)
1464 curr->type = OP_INOUT;
1465 if (curr->early_clobber != early_clobber)
1466 curr->early_clobber = true;
1468 return;
1470 gcc_unreachable ();
1474 switch (code)
1476 case SET:
1477 add_regs_to_insn_regno_info (data, SET_DEST (x), uid, OP_OUT, false);
1478 add_regs_to_insn_regno_info (data, SET_SRC (x), uid, OP_IN, false);
1479 break;
1480 case CLOBBER:
1481 /* We treat clobber of non-operand hard registers as early
1482 clobber (the behavior is expected from asm). */
1483 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_OUT, true);
1484 break;
1485 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
1486 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false);
1487 break;
1488 case PRE_MODIFY: case POST_MODIFY:
1489 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false);
1490 add_regs_to_insn_regno_info (data, XEXP (x, 1), uid, OP_IN, false);
1491 break;
1492 default:
1493 if ((code != PARALLEL && code != EXPR_LIST) || type != OP_OUT)
1494 /* Some targets place small structures in registers for return
1495 values of functions, and those registers are wrapped in
1496 PARALLEL that we may see as the destination of a SET. Here
1497 is an example:
1499 (call_insn 13 12 14 2 (set (parallel:BLK [
1500 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1501 (const_int 0 [0]))
1502 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1503 (const_int 8 [0x8]))
1505 (call (mem:QI (symbol_ref:DI (... */
1506 type = OP_IN;
1507 fmt = GET_RTX_FORMAT (code);
1508 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1510 if (fmt[i] == 'e')
1511 add_regs_to_insn_regno_info (data, XEXP (x, i), uid, type, false);
1512 else if (fmt[i] == 'E')
1514 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1515 add_regs_to_insn_regno_info (data, XVECEXP (x, i, j), uid,
1516 type, false);
1522 /* Return execution frequency of INSN. */
1523 static int
1524 get_insn_freq (rtx insn)
1526 basic_block bb = BLOCK_FOR_INSN (insn);
1528 gcc_checking_assert (bb != NULL);
1529 return REG_FREQ_FROM_BB (bb);
1532 /* Invalidate all reg info of INSN with DATA and execution frequency
1533 FREQ. Update common info about the invalidated registers. */
1534 static void
1535 invalidate_insn_data_regno_info (lra_insn_recog_data_t data, rtx insn,
1536 int freq)
1538 int uid;
1539 bool debug_p;
1540 unsigned int i;
1541 struct lra_insn_reg *ir, *next_ir;
1543 uid = INSN_UID (insn);
1544 debug_p = DEBUG_INSN_P (insn);
1545 for (ir = data->regs; ir != NULL; ir = next_ir)
1547 i = ir->regno;
1548 next_ir = ir->next;
1549 free_insn_reg (ir);
1550 bitmap_clear_bit (&lra_reg_info[i].insn_bitmap, uid);
1551 if (i >= FIRST_PSEUDO_REGISTER && ! debug_p)
1553 lra_reg_info[i].nrefs--;
1554 lra_reg_info[i].freq -= freq;
1555 lra_assert (lra_reg_info[i].nrefs >= 0 && lra_reg_info[i].freq >= 0);
1558 data->regs = NULL;
1561 /* Invalidate all reg info of INSN. Update common info about the
1562 invalidated registers. */
1563 void
1564 lra_invalidate_insn_regno_info (rtx insn)
1566 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn), insn,
1567 get_insn_freq (insn));
1570 /* Update common reg info from reg info of insn given by its DATA and
1571 execution frequency FREQ. */
1572 static void
1573 setup_insn_reg_info (lra_insn_recog_data_t data, int freq)
1575 unsigned int i;
1576 struct lra_insn_reg *ir;
1578 for (ir = data->regs; ir != NULL; ir = ir->next)
1579 if ((i = ir->regno) >= FIRST_PSEUDO_REGISTER)
1581 lra_reg_info[i].nrefs++;
1582 lra_reg_info[i].freq += freq;
1586 /* Set up insn reg info of INSN. Update common reg info from reg info
1587 of INSN. */
1588 void
1589 lra_update_insn_regno_info (rtx insn)
1591 int i, uid, freq;
1592 lra_insn_recog_data_t data;
1593 struct lra_static_insn_data *static_data;
1594 enum rtx_code code;
1596 if (! INSN_P (insn))
1597 return;
1598 data = lra_get_insn_recog_data (insn);
1599 static_data = data->insn_static_data;
1600 freq = get_insn_freq (insn);
1601 invalidate_insn_data_regno_info (data, insn, freq);
1602 uid = INSN_UID (insn);
1603 for (i = static_data->n_operands - 1; i >= 0; i--)
1604 add_regs_to_insn_regno_info (data, *data->operand_loc[i], uid,
1605 static_data->operand[i].type,
1606 static_data->operand[i].early_clobber);
1607 if ((code = GET_CODE (PATTERN (insn))) == CLOBBER || code == USE)
1608 add_regs_to_insn_regno_info (data, XEXP (PATTERN (insn), 0), uid,
1609 code == USE ? OP_IN : OP_OUT, false);
1610 if (NONDEBUG_INSN_P (insn))
1611 setup_insn_reg_info (data, freq);
1614 /* Return reg info of insn given by it UID. */
1615 struct lra_insn_reg *
1616 lra_get_insn_regs (int uid)
1618 lra_insn_recog_data_t data;
1620 data = get_insn_recog_data_by_uid (uid);
1621 return data->regs;
1626 /* This page contains code dealing with stack of the insns which
1627 should be processed by the next constraint pass. */
1629 /* Bitmap used to put an insn on the stack only in one exemplar. */
1630 static sbitmap lra_constraint_insn_stack_bitmap;
1632 /* The stack itself. */
1633 vec<rtx> lra_constraint_insn_stack;
1635 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1636 info for INSN, otherwise only update it if INSN is not already on the
1637 stack. */
1638 static inline void
1639 lra_push_insn_1 (rtx insn, bool always_update)
1641 unsigned int uid = INSN_UID (insn);
1642 if (always_update)
1643 lra_update_insn_regno_info (insn);
1644 if (uid >= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap))
1645 lra_constraint_insn_stack_bitmap =
1646 sbitmap_resize (lra_constraint_insn_stack_bitmap, 3 * uid / 2, 0);
1647 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap, uid))
1648 return;
1649 bitmap_set_bit (lra_constraint_insn_stack_bitmap, uid);
1650 if (! always_update)
1651 lra_update_insn_regno_info (insn);
1652 lra_constraint_insn_stack.safe_push (insn);
1655 /* Put INSN on the stack. */
1656 void
1657 lra_push_insn (rtx insn)
1659 lra_push_insn_1 (insn, false);
1662 /* Put INSN on the stack and update its reg info. */
1663 void
1664 lra_push_insn_and_update_insn_regno_info (rtx insn)
1666 lra_push_insn_1 (insn, true);
1669 /* Put insn with UID on the stack. */
1670 void
1671 lra_push_insn_by_uid (unsigned int uid)
1673 lra_push_insn (lra_insn_recog_data[uid]->insn);
1676 /* Take the last-inserted insns off the stack and return it. */
1678 lra_pop_insn (void)
1680 rtx insn = lra_constraint_insn_stack.pop ();
1681 bitmap_clear_bit (lra_constraint_insn_stack_bitmap, INSN_UID (insn));
1682 return insn;
1685 /* Return the current size of the insn stack. */
1686 unsigned int
1687 lra_insn_stack_length (void)
1689 return lra_constraint_insn_stack.length ();
1692 /* Push insns FROM to TO (excluding it) going in reverse order. */
1693 static void
1694 push_insns (rtx from, rtx to)
1696 rtx insn;
1698 if (from == NULL_RTX)
1699 return;
1700 for (insn = from; insn != to; insn = PREV_INSN (insn))
1701 if (INSN_P (insn))
1702 lra_push_insn (insn);
1705 /* Set up sp offset for insn in range [FROM, LAST]. The offset is
1706 taken from the next BB insn after LAST or zero if there in such
1707 insn. */
1708 static void
1709 setup_sp_offset (rtx from, rtx last)
1711 rtx before = next_nonnote_insn_bb (last);
1712 HOST_WIDE_INT offset = (before == NULL_RTX || ! INSN_P (before)
1713 ? 0 : lra_get_insn_recog_data (before)->sp_offset);
1715 for (rtx insn = from; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
1716 lra_get_insn_recog_data (insn)->sp_offset = offset;
1719 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1720 insns onto the stack. Print about emitting the insns with
1721 TITLE. */
1722 void
1723 lra_process_new_insns (rtx insn, rtx before, rtx after, const char *title)
1725 rtx last;
1727 if (before == NULL_RTX && after == NULL_RTX)
1728 return;
1729 if (lra_dump_file != NULL)
1731 dump_insn_slim (lra_dump_file, insn);
1732 if (before != NULL_RTX)
1734 fprintf (lra_dump_file," %s before:\n", title);
1735 dump_rtl_slim (lra_dump_file, before, NULL_RTX, -1, 0);
1737 if (after != NULL_RTX)
1739 fprintf (lra_dump_file, " %s after:\n", title);
1740 dump_rtl_slim (lra_dump_file, after, NULL_RTX, -1, 0);
1742 fprintf (lra_dump_file, "\n");
1744 if (before != NULL_RTX)
1746 emit_insn_before (before, insn);
1747 push_insns (PREV_INSN (insn), PREV_INSN (before));
1748 setup_sp_offset (before, PREV_INSN (insn));
1750 if (after != NULL_RTX)
1752 for (last = after; NEXT_INSN (last) != NULL_RTX; last = NEXT_INSN (last))
1754 emit_insn_after (after, insn);
1755 push_insns (last, insn);
1756 setup_sp_offset (after, last);
1762 /* This page contains code dealing with scratches (changing them onto
1763 pseudos and restoring them from the pseudos).
1765 We change scratches into pseudos at the beginning of LRA to
1766 simplify dealing with them (conflicts, hard register assignments).
1768 If the pseudo denoting scratch was spilled it means that we do need
1769 a hard register for it. Such pseudos are transformed back to
1770 scratches at the end of LRA. */
1772 /* Description of location of a former scratch operand. */
1773 struct sloc
1775 rtx insn; /* Insn where the scratch was. */
1776 int nop; /* Number of the operand which was a scratch. */
1779 typedef struct sloc *sloc_t;
1781 /* Locations of the former scratches. */
1782 static vec<sloc_t> scratches;
1784 /* Bitmap of scratch regnos. */
1785 static bitmap_head scratch_bitmap;
1787 /* Bitmap of scratch operands. */
1788 static bitmap_head scratch_operand_bitmap;
1790 /* Return true if pseudo REGNO is made of SCRATCH. */
1791 bool
1792 lra_former_scratch_p (int regno)
1794 return bitmap_bit_p (&scratch_bitmap, regno);
1797 /* Return true if the operand NOP of INSN is a former scratch. */
1798 bool
1799 lra_former_scratch_operand_p (rtx insn, int nop)
1801 return bitmap_bit_p (&scratch_operand_bitmap,
1802 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop) != 0;
1805 /* Change scratches onto pseudos and save their location. */
1806 static void
1807 remove_scratches (void)
1809 int i;
1810 bool insn_changed_p;
1811 basic_block bb;
1812 rtx insn, reg;
1813 sloc_t loc;
1814 lra_insn_recog_data_t id;
1815 struct lra_static_insn_data *static_id;
1817 scratches.create (get_max_uid ());
1818 bitmap_initialize (&scratch_bitmap, &reg_obstack);
1819 bitmap_initialize (&scratch_operand_bitmap, &reg_obstack);
1820 FOR_EACH_BB_FN (bb, cfun)
1821 FOR_BB_INSNS (bb, insn)
1822 if (INSN_P (insn))
1824 id = lra_get_insn_recog_data (insn);
1825 static_id = id->insn_static_data;
1826 insn_changed_p = false;
1827 for (i = 0; i < static_id->n_operands; i++)
1828 if (GET_CODE (*id->operand_loc[i]) == SCRATCH
1829 && GET_MODE (*id->operand_loc[i]) != VOIDmode)
1831 insn_changed_p = true;
1832 *id->operand_loc[i] = reg
1833 = lra_create_new_reg (static_id->operand[i].mode,
1834 *id->operand_loc[i], ALL_REGS, NULL);
1835 add_reg_note (insn, REG_UNUSED, reg);
1836 lra_update_dup (id, i);
1837 loc = XNEW (struct sloc);
1838 loc->insn = insn;
1839 loc->nop = i;
1840 scratches.safe_push (loc);
1841 bitmap_set_bit (&scratch_bitmap, REGNO (*id->operand_loc[i]));
1842 bitmap_set_bit (&scratch_operand_bitmap,
1843 INSN_UID (insn) * MAX_RECOG_OPERANDS + i);
1844 if (lra_dump_file != NULL)
1845 fprintf (lra_dump_file,
1846 "Removing SCRATCH in insn #%u (nop %d)\n",
1847 INSN_UID (insn), i);
1849 if (insn_changed_p)
1850 /* Because we might use DF right after caller-saves sub-pass
1851 we need to keep DF info up to date. */
1852 df_insn_rescan (insn);
1856 /* Changes pseudos created by function remove_scratches onto scratches. */
1857 static void
1858 restore_scratches (void)
1860 int regno;
1861 unsigned i;
1862 sloc_t loc;
1863 rtx last = NULL_RTX;
1864 lra_insn_recog_data_t id = NULL;
1866 for (i = 0; scratches.iterate (i, &loc); i++)
1868 if (last != loc->insn)
1870 last = loc->insn;
1871 id = lra_get_insn_recog_data (last);
1873 if (REG_P (*id->operand_loc[loc->nop])
1874 && ((regno = REGNO (*id->operand_loc[loc->nop]))
1875 >= FIRST_PSEUDO_REGISTER)
1876 && lra_get_regno_hard_regno (regno) < 0)
1878 /* It should be only case when scratch register with chosen
1879 constraint 'X' did not get memory or hard register. */
1880 lra_assert (lra_former_scratch_p (regno));
1881 *id->operand_loc[loc->nop]
1882 = gen_rtx_SCRATCH (GET_MODE (*id->operand_loc[loc->nop]));
1883 lra_update_dup (id, loc->nop);
1884 if (lra_dump_file != NULL)
1885 fprintf (lra_dump_file, "Restoring SCRATCH in insn #%u(nop %d)\n",
1886 INSN_UID (loc->insn), loc->nop);
1889 for (i = 0; scratches.iterate (i, &loc); i++)
1890 free (loc);
1891 scratches.release ();
1892 bitmap_clear (&scratch_bitmap);
1893 bitmap_clear (&scratch_operand_bitmap);
1898 #ifdef ENABLE_CHECKING
1900 /* Function checks RTL for correctness. If FINAL_P is true, it is
1901 done at the end of LRA and the check is more rigorous. */
1902 static void
1903 check_rtl (bool final_p)
1905 basic_block bb;
1906 rtx insn;
1908 lra_assert (! final_p || reload_completed);
1909 FOR_EACH_BB_FN (bb, cfun)
1910 FOR_BB_INSNS (bb, insn)
1911 if (NONDEBUG_INSN_P (insn)
1912 && GET_CODE (PATTERN (insn)) != USE
1913 && GET_CODE (PATTERN (insn)) != CLOBBER
1914 && GET_CODE (PATTERN (insn)) != ASM_INPUT)
1916 if (final_p)
1918 extract_insn (insn);
1919 lra_assert (constrain_operands (1));
1920 continue;
1922 /* LRA code is based on assumption that all addresses can be
1923 correctly decomposed. LRA can generate reloads for
1924 decomposable addresses. The decomposition code checks the
1925 correctness of the addresses. So we don't need to check
1926 the addresses here. Don't call insn_invalid_p here, it can
1927 change the code at this stage. */
1928 if (recog_memoized (insn) < 0 && asm_noperands (PATTERN (insn)) < 0)
1929 fatal_insn_not_found (insn);
1932 #endif /* #ifdef ENABLE_CHECKING */
1934 /* Determine if the current function has an exception receiver block
1935 that reaches the exit block via non-exceptional edges */
1936 static bool
1937 has_nonexceptional_receiver (void)
1939 edge e;
1940 edge_iterator ei;
1941 basic_block *tos, *worklist, bb;
1943 /* If we're not optimizing, then just err on the safe side. */
1944 if (!optimize)
1945 return true;
1947 /* First determine which blocks can reach exit via normal paths. */
1948 tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1);
1950 FOR_EACH_BB_FN (bb, cfun)
1951 bb->flags &= ~BB_REACHABLE;
1953 /* Place the exit block on our worklist. */
1954 EXIT_BLOCK_PTR_FOR_FN (cfun)->flags |= BB_REACHABLE;
1955 *tos++ = EXIT_BLOCK_PTR_FOR_FN (cfun);
1957 /* Iterate: find everything reachable from what we've already seen. */
1958 while (tos != worklist)
1960 bb = *--tos;
1962 FOR_EACH_EDGE (e, ei, bb->preds)
1963 if (e->flags & EDGE_ABNORMAL)
1965 free (worklist);
1966 return true;
1968 else
1970 basic_block src = e->src;
1972 if (!(src->flags & BB_REACHABLE))
1974 src->flags |= BB_REACHABLE;
1975 *tos++ = src;
1979 free (worklist);
1980 /* No exceptional block reached exit unexceptionally. */
1981 return false;
1984 #ifdef AUTO_INC_DEC
1986 /* Process recursively X of INSN and add REG_INC notes if necessary. */
1987 static void
1988 add_auto_inc_notes (rtx insn, rtx x)
1990 enum rtx_code code = GET_CODE (x);
1991 const char *fmt;
1992 int i, j;
1994 if (code == MEM && auto_inc_p (XEXP (x, 0)))
1996 add_reg_note (insn, REG_INC, XEXP (XEXP (x, 0), 0));
1997 return;
2000 /* Scan all X sub-expressions. */
2001 fmt = GET_RTX_FORMAT (code);
2002 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2004 if (fmt[i] == 'e')
2005 add_auto_inc_notes (insn, XEXP (x, i));
2006 else if (fmt[i] == 'E')
2007 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2008 add_auto_inc_notes (insn, XVECEXP (x, i, j));
2012 #endif
2014 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2015 We change pseudos by hard registers without notification of DF and
2016 that can make the notes obsolete. DF-infrastructure does not deal
2017 with REG_INC notes -- so we should regenerate them here. */
2018 static void
2019 update_inc_notes (void)
2021 rtx *pnote;
2022 basic_block bb;
2023 rtx insn;
2025 FOR_EACH_BB_FN (bb, cfun)
2026 FOR_BB_INSNS (bb, insn)
2027 if (NONDEBUG_INSN_P (insn))
2029 pnote = &REG_NOTES (insn);
2030 while (*pnote != 0)
2032 if (REG_NOTE_KIND (*pnote) == REG_DEAD
2033 || REG_NOTE_KIND (*pnote) == REG_UNUSED
2034 || REG_NOTE_KIND (*pnote) == REG_INC)
2035 *pnote = XEXP (*pnote, 1);
2036 else
2037 pnote = &XEXP (*pnote, 1);
2039 #ifdef AUTO_INC_DEC
2040 add_auto_inc_notes (insn, PATTERN (insn));
2041 #endif
2045 /* Set to 1 while in lra. */
2046 int lra_in_progress;
2048 /* Start of pseudo regnos before the LRA. */
2049 int lra_new_regno_start;
2051 /* Start of reload pseudo regnos before the new spill pass. */
2052 int lra_constraint_new_regno_start;
2054 /* Inheritance pseudo regnos before the new spill pass. */
2055 bitmap_head lra_inheritance_pseudos;
2057 /* Split regnos before the new spill pass. */
2058 bitmap_head lra_split_regs;
2060 /* Reload pseudo regnos before the new assignmnet pass which still can
2061 be spilled after the assinment pass as memory is also accepted in
2062 insns for the reload pseudos. */
2063 bitmap_head lra_optional_reload_pseudos;
2065 /* Pseudo regnos used for subreg reloads before the new assignment
2066 pass. Such pseudos still can be spilled after the assinment
2067 pass. */
2068 bitmap_head lra_subreg_reload_pseudos;
2070 /* First UID of insns generated before a new spill pass. */
2071 int lra_constraint_new_insn_uid_start;
2073 /* File used for output of LRA debug information. */
2074 FILE *lra_dump_file;
2076 /* True if we should try spill into registers of different classes
2077 instead of memory. */
2078 bool lra_reg_spill_p;
2080 /* Set up value LRA_REG_SPILL_P. */
2081 static void
2082 setup_reg_spill_flag (void)
2084 int cl, mode;
2086 if (targetm.spill_class != NULL)
2087 for (cl = 0; cl < (int) LIM_REG_CLASSES; cl++)
2088 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
2089 if (targetm.spill_class ((enum reg_class) cl,
2090 (enum machine_mode) mode) != NO_REGS)
2092 lra_reg_spill_p = true;
2093 return;
2095 lra_reg_spill_p = false;
2098 /* True if the current function is too big to use regular algorithms
2099 in LRA. In other words, we should use simpler and faster algorithms
2100 in LRA. It also means we should not worry about generation code
2101 for caller saves. The value is set up in IRA. */
2102 bool lra_simple_p;
2104 /* Major LRA entry function. F is a file should be used to dump LRA
2105 debug info. */
2106 void
2107 lra (FILE *f)
2109 int i;
2110 bool live_p, scratch_p, inserted_p;
2112 lra_dump_file = f;
2114 timevar_push (TV_LRA);
2116 /* Make sure that the last insn is a note. Some subsequent passes
2117 need it. */
2118 emit_note (NOTE_INSN_DELETED);
2120 COPY_HARD_REG_SET (lra_no_alloc_regs, ira_no_alloc_regs);
2122 init_reg_info ();
2123 expand_reg_info ();
2125 init_insn_recog_data ();
2127 #ifdef ENABLE_CHECKING
2128 /* Some quick check on RTL generated by previous passes. */
2129 check_rtl (false);
2130 #endif
2132 lra_in_progress = 1;
2134 lra_live_range_iter = lra_coalesce_iter = 0;
2135 lra_constraint_iter = lra_constraint_iter_after_spill = 0;
2136 lra_inheritance_iter = lra_undo_inheritance_iter = 0;
2138 setup_reg_spill_flag ();
2140 /* Function remove_scratches can creates new pseudos for clobbers --
2141 so set up lra_constraint_new_regno_start before its call to
2142 permit changing reg classes for pseudos created by this
2143 simplification. */
2144 lra_constraint_new_regno_start = lra_new_regno_start = max_reg_num ();
2145 remove_scratches ();
2146 scratch_p = lra_constraint_new_regno_start != max_reg_num ();
2148 /* A function that has a non-local label that can reach the exit
2149 block via non-exceptional paths must save all call-saved
2150 registers. */
2151 if (cfun->has_nonlocal_label && has_nonexceptional_receiver ())
2152 crtl->saves_all_registers = 1;
2154 if (crtl->saves_all_registers)
2155 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2156 if (! call_used_regs[i] && ! fixed_regs[i] && ! LOCAL_REGNO (i))
2157 df_set_regs_ever_live (i, true);
2159 /* We don't DF from now and avoid its using because it is to
2160 expensive when a lot of RTL changes are made. */
2161 df_set_flags (DF_NO_INSN_RESCAN);
2162 lra_constraint_insn_stack.create (get_max_uid ());
2163 lra_constraint_insn_stack_bitmap = sbitmap_alloc (get_max_uid ());
2164 bitmap_clear (lra_constraint_insn_stack_bitmap);
2165 lra_live_ranges_init ();
2166 lra_constraints_init ();
2167 lra_curr_reload_num = 0;
2168 push_insns (get_last_insn (), NULL_RTX);
2169 /* It is needed for the 1st coalescing. */
2170 lra_constraint_new_insn_uid_start = get_max_uid ();
2171 bitmap_initialize (&lra_inheritance_pseudos, &reg_obstack);
2172 bitmap_initialize (&lra_split_regs, &reg_obstack);
2173 bitmap_initialize (&lra_optional_reload_pseudos, &reg_obstack);
2174 bitmap_initialize (&lra_subreg_reload_pseudos, &reg_obstack);
2175 live_p = false;
2176 if (get_frame_size () != 0 && crtl->stack_alignment_needed)
2177 /* If we have a stack frame, we must align it now. The stack size
2178 may be a part of the offset computation for register
2179 elimination. */
2180 assign_stack_local (BLKmode, 0, crtl->stack_alignment_needed);
2181 lra_init_equiv ();
2182 for (;;)
2184 for (;;)
2186 /* We should try to assign hard registers to scratches even
2187 if there were no RTL transformations in
2188 lra_constraints. */
2189 if (! lra_constraints (lra_constraint_iter == 0)
2190 && (lra_constraint_iter > 1
2191 || (! scratch_p && ! caller_save_needed)))
2192 break;
2193 /* Constraint transformations may result in that eliminable
2194 hard regs become uneliminable and pseudos which use them
2195 should be spilled. It is better to do it before pseudo
2196 assignments.
2198 For example, rs6000 can make
2199 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2200 to use a constant pool. */
2201 lra_eliminate (false, false);
2202 /* Do inheritance only for regular algorithms. */
2203 if (! lra_simple_p)
2205 if (flag_use_caller_save)
2207 if (live_p)
2208 lra_clear_live_ranges ();
2209 /* As a side-effect of lra_create_live_ranges, we calculate
2210 actual_call_used_reg_set, which is needed during
2211 lra_inheritance. */
2212 lra_create_live_ranges (true);
2214 lra_inheritance ();
2216 if (live_p)
2217 lra_clear_live_ranges ();
2218 /* We need live ranges for lra_assign -- so build them. */
2219 lra_create_live_ranges (true);
2220 live_p = true;
2221 /* If we don't spill non-reload and non-inheritance pseudos,
2222 there is no sense to run memory-memory move coalescing.
2223 If inheritance pseudos were spilled, the memory-memory
2224 moves involving them will be removed by pass undoing
2225 inheritance. */
2226 if (lra_simple_p)
2227 lra_assign ();
2228 else
2230 bool spill_p = !lra_assign ();
2232 if (lra_undo_inheritance ())
2233 live_p = false;
2234 if (spill_p)
2236 if (! live_p)
2238 lra_create_live_ranges (true);
2239 live_p = true;
2241 if (lra_coalesce ())
2242 live_p = false;
2244 if (! live_p)
2245 lra_clear_live_ranges ();
2248 /* Don't clear optional reloads bitmap until all constraints are
2249 satisfied as we need to differ them from regular reloads. */
2250 bitmap_clear (&lra_optional_reload_pseudos);
2251 bitmap_clear (&lra_subreg_reload_pseudos);
2252 bitmap_clear (&lra_inheritance_pseudos);
2253 bitmap_clear (&lra_split_regs);
2254 if (! lra_need_for_spills_p ())
2255 break;
2256 if (! live_p)
2258 /* We need full live info for spilling pseudos into
2259 registers instead of memory. */
2260 lra_create_live_ranges (lra_reg_spill_p);
2261 live_p = true;
2263 lra_spill ();
2264 /* Assignment of stack slots changes elimination offsets for
2265 some eliminations. So update the offsets here. */
2266 lra_eliminate (false, false);
2267 lra_constraint_new_regno_start = max_reg_num ();
2268 lra_constraint_new_insn_uid_start = get_max_uid ();
2269 lra_constraint_iter_after_spill = 0;
2271 restore_scratches ();
2272 lra_eliminate (true, false);
2273 lra_final_code_change ();
2274 lra_in_progress = 0;
2275 if (live_p)
2276 lra_clear_live_ranges ();
2277 lra_live_ranges_finish ();
2278 lra_constraints_finish ();
2279 finish_reg_info ();
2280 sbitmap_free (lra_constraint_insn_stack_bitmap);
2281 lra_constraint_insn_stack.release ();
2282 finish_insn_recog_data ();
2283 regstat_free_n_sets_and_refs ();
2284 regstat_free_ri ();
2285 reload_completed = 1;
2286 update_inc_notes ();
2288 inserted_p = fixup_abnormal_edges ();
2290 /* We've possibly turned single trapping insn into multiple ones. */
2291 if (cfun->can_throw_non_call_exceptions)
2293 sbitmap blocks;
2294 blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
2295 bitmap_ones (blocks);
2296 find_many_sub_basic_blocks (blocks);
2297 sbitmap_free (blocks);
2300 if (inserted_p)
2301 commit_edge_insertions ();
2303 /* Replacing pseudos with their memory equivalents might have
2304 created shared rtx. Subsequent passes would get confused
2305 by this, so unshare everything here. */
2306 unshare_all_rtl_again (get_insns ());
2308 #ifdef ENABLE_CHECKING
2309 check_rtl (true);
2310 #endif
2312 timevar_pop (TV_LRA);
2315 /* Called once per compiler to initialize LRA data once. */
2316 void
2317 lra_init_once (void)
2319 init_insn_code_data_once ();
2322 /* Called once per compiler to finish LRA data which are initialize
2323 once. */
2324 void
2325 lra_finish_once (void)
2327 finish_insn_code_data_once ();