Daily bump.
[official-gcc.git] / gcc / lra.c
blobf4d7a3c071fb0c784cd22a957817d216bf015a71
1 /* LRA (local register allocator) driver and LRA utilities.
2 Copyright (C) 2010-2015 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 /* The Local Register Allocator (LRA) is a replacement of former
23 reload pass. It is focused to simplify code solving the reload
24 pass tasks, to make the code maintenance easier, and to implement new
25 perspective optimizations.
27 The major LRA design solutions are:
28 o division small manageable, separated sub-tasks
29 o reflection of all transformations and decisions in RTL as more
30 as possible
31 o insn constraints as a primary source of the info (minimizing
32 number of target-depended macros/hooks)
34 In brief LRA works by iterative insn process with the final goal is
35 to satisfy all insn and address constraints:
36 o New reload insns (in brief reloads) and reload pseudos might be
37 generated;
38 o Some pseudos might be spilled to assign hard registers to
39 new reload pseudos;
40 o Recalculating spilled pseudo values (rematerialization);
41 o Changing spilled pseudos to stack memory or their equivalences;
42 o Allocation stack memory changes the address displacement and
43 new iteration is needed.
45 Here is block diagram of LRA passes:
47 ------------------------
48 --------------- | Undo inheritance for | ---------------
49 | Memory-memory | | spilled pseudos, | | New (and old) |
50 | move coalesce |<---| splits for pseudos got |<-- | pseudos |
51 --------------- | the same hard regs, | | assignment |
52 Start | | and optional reloads | ---------------
53 | | ------------------------ ^
54 V | ---------------- |
55 ----------- V | Update virtual | |
56 | Remove |----> ------------>| register | |
57 | scratches | ^ | displacements | |
58 ----------- | ---------------- |
59 | | |
60 | V New |
61 | ------------ pseudos -------------------
62 | |Constraints:| or insns | Inheritance/split |
63 | | RTL |--------->| transformations |
64 | | transfor- | | in EBB scope |
65 | substi- | mations | -------------------
66 | tutions ------------
67 | | No change
68 ---------------- V
69 | Spilled pseudo | -------------------
70 | to memory |<----| Rematerialization |
71 | substitution | -------------------
72 ----------------
73 | No susbtitions
75 -------------------------
76 | Hard regs substitution, |
77 | devirtalization, and |------> Finish
78 | restoring scratches got |
79 | memory |
80 -------------------------
82 To speed up the process:
83 o We process only insns affected by changes on previous
84 iterations;
85 o We don't use DFA-infrastructure because it results in much slower
86 compiler speed than a special IR described below does;
87 o We use a special insn representation for quick access to insn
88 info which is always *synchronized* with the current RTL;
89 o Insn IR is minimized by memory. It is divided on three parts:
90 o one specific for each insn in RTL (only operand locations);
91 o one common for all insns in RTL with the same insn code
92 (different operand attributes from machine descriptions);
93 o one oriented for maintenance of live info (list of pseudos).
94 o Pseudo data:
95 o all insns where the pseudo is referenced;
96 o live info (conflicting hard regs, live ranges, # of
97 references etc);
98 o data used for assigning (preferred hard regs, costs etc).
100 This file contains LRA driver, LRA utility functions and data, and
101 code for dealing with scratches. */
103 #include "config.h"
104 #include "system.h"
105 #include "coretypes.h"
106 #include "tm.h"
107 #include "hard-reg-set.h"
108 #include "rtl.h"
109 #include "tm_p.h"
110 #include "regs.h"
111 #include "insn-config.h"
112 #include "insn-codes.h"
113 #include "recog.h"
114 #include "output.h"
115 #include "addresses.h"
116 #include "flags.h"
117 #include "hashtab.h"
118 #include "hash-set.h"
119 #include "vec.h"
120 #include "machmode.h"
121 #include "input.h"
122 #include "function.h"
123 #include "symtab.h"
124 #include "wide-int.h"
125 #include "inchash.h"
126 #include "tree.h"
127 #include "optabs.h"
128 #include "statistics.h"
129 #include "double-int.h"
130 #include "real.h"
131 #include "fixed-value.h"
132 #include "alias.h"
133 #include "expmed.h"
134 #include "dojump.h"
135 #include "explow.h"
136 #include "calls.h"
137 #include "emit-rtl.h"
138 #include "varasm.h"
139 #include "stmt.h"
140 #include "expr.h"
141 #include "predict.h"
142 #include "dominance.h"
143 #include "cfg.h"
144 #include "cfgrtl.h"
145 #include "cfgbuild.h"
146 #include "basic-block.h"
147 #include "except.h"
148 #include "tree-pass.h"
149 #include "timevar.h"
150 #include "target.h"
151 #include "ira.h"
152 #include "lra-int.h"
153 #include "df.h"
155 /* Dump bitmap SET with TITLE and BB INDEX. */
156 void
157 lra_dump_bitmap_with_title (const char *title, bitmap set, int index)
159 unsigned int i;
160 int count;
161 bitmap_iterator bi;
162 static const int max_nums_on_line = 10;
164 if (bitmap_empty_p (set))
165 return;
166 fprintf (lra_dump_file, " %s %d:", title, index);
167 fprintf (lra_dump_file, "\n");
168 count = max_nums_on_line + 1;
169 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
171 if (count > max_nums_on_line)
173 fprintf (lra_dump_file, "\n ");
174 count = 0;
176 fprintf (lra_dump_file, " %4u", i);
177 count++;
179 fprintf (lra_dump_file, "\n");
182 /* Hard registers currently not available for allocation. It can
183 changed after some hard registers become not eliminable. */
184 HARD_REG_SET lra_no_alloc_regs;
186 static int get_new_reg_value (void);
187 static void expand_reg_info (void);
188 static void invalidate_insn_recog_data (int);
189 static int get_insn_freq (rtx_insn *);
190 static void invalidate_insn_data_regno_info (lra_insn_recog_data_t,
191 rtx_insn *, int);
193 /* Expand all regno related info needed for LRA. */
194 static void
195 expand_reg_data (int old)
197 resize_reg_info ();
198 expand_reg_info ();
199 ira_expand_reg_equiv ();
200 for (int i = (int) max_reg_num () - 1; i >= old; i--)
201 lra_change_class (i, ALL_REGS, " Set", true);
204 /* Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL
205 or of VOIDmode, use MD_MODE for the new reg. Initialize its
206 register class to RCLASS. Print message about assigning class
207 RCLASS containing new register name TITLE unless it is NULL. Use
208 attributes of ORIGINAL if it is a register. The created register
209 will have unique held value. */
211 lra_create_new_reg_with_unique_value (machine_mode md_mode, rtx original,
212 enum reg_class rclass, const char *title)
214 machine_mode mode;
215 rtx new_reg;
217 if (original == NULL_RTX || (mode = GET_MODE (original)) == VOIDmode)
218 mode = md_mode;
219 lra_assert (mode != VOIDmode);
220 new_reg = gen_reg_rtx (mode);
221 if (original == NULL_RTX || ! REG_P (original))
223 if (lra_dump_file != NULL)
224 fprintf (lra_dump_file, " Creating newreg=%i", REGNO (new_reg));
226 else
228 if (ORIGINAL_REGNO (original) >= FIRST_PSEUDO_REGISTER)
229 ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original);
230 REG_USERVAR_P (new_reg) = REG_USERVAR_P (original);
231 REG_POINTER (new_reg) = REG_POINTER (original);
232 REG_ATTRS (new_reg) = REG_ATTRS (original);
233 if (lra_dump_file != NULL)
234 fprintf (lra_dump_file, " Creating newreg=%i from oldreg=%i",
235 REGNO (new_reg), REGNO (original));
237 if (lra_dump_file != NULL)
239 if (title != NULL)
240 fprintf (lra_dump_file, ", assigning class %s to%s%s r%d",
241 reg_class_names[rclass], *title == '\0' ? "" : " ",
242 title, REGNO (new_reg));
243 fprintf (lra_dump_file, "\n");
245 expand_reg_data (max_reg_num ());
246 setup_reg_classes (REGNO (new_reg), rclass, NO_REGS, rclass);
247 return new_reg;
250 /* Analogous to the previous function but also inherits value of
251 ORIGINAL. */
253 lra_create_new_reg (machine_mode md_mode, rtx original,
254 enum reg_class rclass, const char *title)
256 rtx new_reg;
258 new_reg
259 = lra_create_new_reg_with_unique_value (md_mode, original, rclass, title);
260 if (original != NULL_RTX && REG_P (original))
261 lra_assign_reg_val (REGNO (original), REGNO (new_reg));
262 return new_reg;
265 /* Set up for REGNO unique hold value. */
266 void
267 lra_set_regno_unique_value (int regno)
269 lra_reg_info[regno].val = get_new_reg_value ();
272 /* Invalidate INSN related info used by LRA. The info should never be
273 used after that. */
274 void
275 lra_invalidate_insn_data (rtx_insn *insn)
277 lra_invalidate_insn_regno_info (insn);
278 invalidate_insn_recog_data (INSN_UID (insn));
281 /* Mark INSN deleted and invalidate the insn related info used by
282 LRA. */
283 void
284 lra_set_insn_deleted (rtx_insn *insn)
286 lra_invalidate_insn_data (insn);
287 SET_INSN_DELETED (insn);
290 /* Delete an unneeded INSN and any previous insns who sole purpose is
291 loading data that is dead in INSN. */
292 void
293 lra_delete_dead_insn (rtx_insn *insn)
295 rtx_insn *prev = prev_real_insn (insn);
296 rtx prev_dest;
298 /* If the previous insn sets a register that dies in our insn,
299 delete it too. */
300 if (prev && GET_CODE (PATTERN (prev)) == SET
301 && (prev_dest = SET_DEST (PATTERN (prev)), REG_P (prev_dest))
302 && reg_mentioned_p (prev_dest, PATTERN (insn))
303 && find_regno_note (insn, REG_DEAD, REGNO (prev_dest))
304 && ! side_effects_p (SET_SRC (PATTERN (prev))))
305 lra_delete_dead_insn (prev);
307 lra_set_insn_deleted (insn);
310 /* Emit insn x = y + z. Return NULL if we failed to do it.
311 Otherwise, return the insn. We don't use gen_add3_insn as it might
312 clobber CC. */
313 static rtx
314 emit_add3_insn (rtx x, rtx y, rtx z)
316 rtx_insn *last;
318 last = get_last_insn ();
320 if (have_addptr3_insn (x, y, z))
322 rtx insn = gen_addptr3_insn (x, y, z);
324 /* If the target provides an "addptr" pattern it hopefully does
325 for a reason. So falling back to the normal add would be
326 a bug. */
327 lra_assert (insn != NULL_RTX);
328 emit_insn (insn);
329 return insn;
332 rtx_insn *insn = emit_insn (gen_rtx_SET (VOIDmode, x,
333 gen_rtx_PLUS (GET_MODE (y), y, z)));
334 if (recog_memoized (insn) < 0)
336 delete_insns_since (last);
337 insn = NULL;
339 return insn;
342 /* Emit insn x = x + y. Return the insn. We use gen_add2_insn as the
343 last resort. */
344 static rtx
345 emit_add2_insn (rtx x, rtx y)
347 rtx insn;
349 insn = emit_add3_insn (x, x, y);
350 if (insn == NULL_RTX)
352 insn = gen_add2_insn (x, y);
353 if (insn != NULL_RTX)
354 emit_insn (insn);
356 return insn;
359 /* Target checks operands through operand predicates to recognize an
360 insn. We should have a special precaution to generate add insns
361 which are frequent results of elimination.
363 Emit insns for x = y + z. X can be used to store intermediate
364 values and should be not in Y and Z when we use X to store an
365 intermediate value. Y + Z should form [base] [+ index[ * scale]] [
366 + disp] where base and index are registers, disp and scale are
367 constants. Y should contain base if it is present, Z should
368 contain disp if any. index[*scale] can be part of Y or Z. */
369 void
370 lra_emit_add (rtx x, rtx y, rtx z)
372 int old;
373 rtx_insn *last;
374 rtx a1, a2, base, index, disp, scale, index_scale;
375 bool ok_p;
377 rtx add3_insn = emit_add3_insn (x, y, z);
378 old = max_reg_num ();
379 if (add3_insn != NULL)
381 else
383 disp = a2 = NULL_RTX;
384 if (GET_CODE (y) == PLUS)
386 a1 = XEXP (y, 0);
387 a2 = XEXP (y, 1);
388 disp = z;
390 else
392 a1 = y;
393 if (CONSTANT_P (z))
394 disp = z;
395 else
396 a2 = z;
398 index_scale = scale = NULL_RTX;
399 if (GET_CODE (a1) == MULT)
401 index_scale = a1;
402 index = XEXP (a1, 0);
403 scale = XEXP (a1, 1);
404 base = a2;
406 else if (a2 != NULL_RTX && GET_CODE (a2) == MULT)
408 index_scale = a2;
409 index = XEXP (a2, 0);
410 scale = XEXP (a2, 1);
411 base = a1;
413 else
415 base = a1;
416 index = a2;
418 if (! (REG_P (base) || GET_CODE (base) == SUBREG)
419 || (index != NULL_RTX
420 && ! (REG_P (index) || GET_CODE (index) == SUBREG))
421 || (disp != NULL_RTX && ! CONSTANT_P (disp))
422 || (scale != NULL_RTX && ! CONSTANT_P (scale)))
424 /* Probably we have no 3 op add. Last chance is to use 2-op
425 add insn. To succeed, don't move Z to X as an address
426 segment always comes in Y. Otherwise, we might fail when
427 adding the address segment to register. */
428 lra_assert (x != y && x != z);
429 emit_move_insn (x, y);
430 rtx insn = emit_add2_insn (x, z);
431 lra_assert (insn != NULL_RTX);
433 else
435 if (index_scale == NULL_RTX)
436 index_scale = index;
437 if (disp == NULL_RTX)
439 /* Generate x = index_scale; x = x + base. */
440 lra_assert (index_scale != NULL_RTX && base != NULL_RTX);
441 emit_move_insn (x, index_scale);
442 rtx insn = emit_add2_insn (x, base);
443 lra_assert (insn != NULL_RTX);
445 else if (scale == NULL_RTX)
447 /* Try x = base + disp. */
448 lra_assert (base != NULL_RTX);
449 last = get_last_insn ();
450 rtx_insn *move_insn =
451 emit_move_insn (x, gen_rtx_PLUS (GET_MODE (base), base, disp));
452 if (recog_memoized (move_insn) < 0)
454 delete_insns_since (last);
455 /* Generate x = disp; x = x + base. */
456 emit_move_insn (x, disp);
457 rtx add2_insn = emit_add2_insn (x, base);
458 lra_assert (add2_insn != NULL_RTX);
460 /* Generate x = x + index. */
461 if (index != NULL_RTX)
463 rtx insn = emit_add2_insn (x, index);
464 lra_assert (insn != NULL_RTX);
467 else
469 /* Try x = index_scale; x = x + disp; x = x + base. */
470 last = get_last_insn ();
471 rtx_insn *move_insn = emit_move_insn (x, index_scale);
472 ok_p = false;
473 if (recog_memoized (move_insn) >= 0)
475 rtx insn = emit_add2_insn (x, disp);
476 if (insn != NULL_RTX)
478 insn = emit_add2_insn (x, base);
479 if (insn != NULL_RTX)
480 ok_p = true;
483 if (! ok_p)
485 delete_insns_since (last);
486 /* Generate x = disp; x = x + base; x = x + index_scale. */
487 emit_move_insn (x, disp);
488 rtx insn = emit_add2_insn (x, base);
489 lra_assert (insn != NULL_RTX);
490 insn = emit_add2_insn (x, index_scale);
491 lra_assert (insn != NULL_RTX);
496 /* Functions emit_... can create pseudos -- so expand the pseudo
497 data. */
498 if (old != max_reg_num ())
499 expand_reg_data (old);
502 /* The number of emitted reload insns so far. */
503 int lra_curr_reload_num;
505 /* Emit x := y, processing special case when y = u + v or y = u + v *
506 scale + w through emit_add (Y can be an address which is base +
507 index reg * scale + displacement in general case). X may be used
508 as intermediate result therefore it should be not in Y. */
509 void
510 lra_emit_move (rtx x, rtx y)
512 int old;
514 if (GET_CODE (y) != PLUS)
516 if (rtx_equal_p (x, y))
517 return;
518 old = max_reg_num ();
519 emit_move_insn (x, y);
520 if (REG_P (x))
521 lra_reg_info[ORIGINAL_REGNO (x)].last_reload = ++lra_curr_reload_num;
522 /* Function emit_move can create pseudos -- so expand the pseudo
523 data. */
524 if (old != max_reg_num ())
525 expand_reg_data (old);
526 return;
528 lra_emit_add (x, XEXP (y, 0), XEXP (y, 1));
531 /* Update insn operands which are duplication of operands whose
532 numbers are in array of NOPS (with end marker -1). The insn is
533 represented by its LRA internal representation ID. */
534 void
535 lra_update_dups (lra_insn_recog_data_t id, signed char *nops)
537 int i, j, nop;
538 struct lra_static_insn_data *static_id = id->insn_static_data;
540 for (i = 0; i < static_id->n_dups; i++)
541 for (j = 0; (nop = nops[j]) >= 0; j++)
542 if (static_id->dup_num[i] == nop)
543 *id->dup_loc[i] = *id->operand_loc[nop];
548 /* This page contains code dealing with info about registers in the
549 insns. */
551 /* Pools for insn reg info. */
552 static alloc_pool insn_reg_pool;
554 /* Initiate pool for insn reg info. */
555 static void
556 init_insn_regs (void)
558 insn_reg_pool
559 = create_alloc_pool ("insn regs", sizeof (struct lra_insn_reg), 100);
562 /* Create LRA insn related info about a reference to REGNO in INSN with
563 TYPE (in/out/inout), biggest reference mode MODE, flag that it is
564 reference through subreg (SUBREG_P), flag that is early clobbered
565 in the insn (EARLY_CLOBBER), and reference to the next insn reg
566 info (NEXT). */
567 static struct lra_insn_reg *
568 new_insn_reg (rtx_insn *insn, int regno, enum op_type type,
569 machine_mode mode,
570 bool subreg_p, bool early_clobber, struct lra_insn_reg *next)
572 struct lra_insn_reg *ir;
574 ir = (struct lra_insn_reg *) pool_alloc (insn_reg_pool);
575 ir->type = type;
576 ir->biggest_mode = mode;
577 if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (lra_reg_info[regno].biggest_mode)
578 && NONDEBUG_INSN_P (insn))
579 lra_reg_info[regno].biggest_mode = mode;
580 ir->subreg_p = subreg_p;
581 ir->early_clobber = early_clobber;
582 ir->regno = regno;
583 ir->next = next;
584 return ir;
587 /* Free insn reg info IR. */
588 static void
589 free_insn_reg (struct lra_insn_reg *ir)
591 pool_free (insn_reg_pool, ir);
594 /* Free insn reg info list IR. */
595 static void
596 free_insn_regs (struct lra_insn_reg *ir)
598 struct lra_insn_reg *next_ir;
600 for (; ir != NULL; ir = next_ir)
602 next_ir = ir->next;
603 free_insn_reg (ir);
607 /* Finish pool for insn reg info. */
608 static void
609 finish_insn_regs (void)
611 free_alloc_pool (insn_reg_pool);
616 /* This page contains code dealing LRA insn info (or in other words
617 LRA internal insn representation). */
619 /* Map INSN_CODE -> the static insn data. This info is valid during
620 all translation unit. */
621 struct lra_static_insn_data *insn_code_data[LAST_INSN_CODE];
623 /* Debug insns are represented as a special insn with one input
624 operand which is RTL expression in var_location. */
626 /* The following data are used as static insn operand data for all
627 debug insns. If structure lra_operand_data is changed, the
628 initializer should be changed too. */
629 static struct lra_operand_data debug_operand_data =
631 NULL, /* alternative */
632 VOIDmode, /* We are not interesting in the operand mode. */
633 OP_IN,
634 0, 0, 0, 0
637 /* The following data are used as static insn data for all debug
638 insns. If structure lra_static_insn_data is changed, the
639 initializer should be changed too. */
640 static struct lra_static_insn_data debug_insn_static_data =
642 &debug_operand_data,
643 0, /* Duplication operands #. */
644 -1, /* Commutative operand #. */
645 1, /* Operands #. There is only one operand which is debug RTL
646 expression. */
647 0, /* Duplications #. */
648 0, /* Alternatives #. We are not interesting in alternatives
649 because we does not proceed debug_insns for reloads. */
650 NULL, /* Hard registers referenced in machine description. */
651 NULL /* Descriptions of operands in alternatives. */
654 /* Called once per compiler work to initialize some LRA data related
655 to insns. */
656 static void
657 init_insn_code_data_once (void)
659 memset (insn_code_data, 0, sizeof (insn_code_data));
662 /* Called once per compiler work to finalize some LRA data related to
663 insns. */
664 static void
665 finish_insn_code_data_once (void)
667 int i;
669 for (i = 0; i < LAST_INSN_CODE; i++)
671 if (insn_code_data[i] != NULL)
672 free (insn_code_data[i]);
676 /* Return static insn data, allocate and setup if necessary. Although
677 dup_num is static data (it depends only on icode), to set it up we
678 need to extract insn first. So recog_data should be valid for
679 normal insn (ICODE >= 0) before the call. */
680 static struct lra_static_insn_data *
681 get_static_insn_data (int icode, int nop, int ndup, int nalt)
683 struct lra_static_insn_data *data;
684 size_t n_bytes;
686 lra_assert (icode < LAST_INSN_CODE);
687 if (icode >= 0 && (data = insn_code_data[icode]) != NULL)
688 return data;
689 lra_assert (nop >= 0 && ndup >= 0 && nalt >= 0);
690 n_bytes = sizeof (struct lra_static_insn_data)
691 + sizeof (struct lra_operand_data) * nop
692 + sizeof (int) * ndup;
693 data = XNEWVAR (struct lra_static_insn_data, n_bytes);
694 data->operand_alternative = NULL;
695 data->n_operands = nop;
696 data->n_dups = ndup;
697 data->n_alternatives = nalt;
698 data->operand = ((struct lra_operand_data *)
699 ((char *) data + sizeof (struct lra_static_insn_data)));
700 data->dup_num = ((int *) ((char *) data->operand
701 + sizeof (struct lra_operand_data) * nop));
702 if (icode >= 0)
704 int i;
706 insn_code_data[icode] = data;
707 for (i = 0; i < nop; i++)
709 data->operand[i].constraint
710 = insn_data[icode].operand[i].constraint;
711 data->operand[i].mode = insn_data[icode].operand[i].mode;
712 data->operand[i].strict_low = insn_data[icode].operand[i].strict_low;
713 data->operand[i].is_operator
714 = insn_data[icode].operand[i].is_operator;
715 data->operand[i].type
716 = (data->operand[i].constraint[0] == '=' ? OP_OUT
717 : data->operand[i].constraint[0] == '+' ? OP_INOUT
718 : OP_IN);
719 data->operand[i].is_address = false;
721 for (i = 0; i < ndup; i++)
722 data->dup_num[i] = recog_data.dup_num[i];
724 return data;
727 /* The current length of the following array. */
728 int lra_insn_recog_data_len;
730 /* Map INSN_UID -> the insn recog data (NULL if unknown). */
731 lra_insn_recog_data_t *lra_insn_recog_data;
733 /* Initialize LRA data about insns. */
734 static void
735 init_insn_recog_data (void)
737 lra_insn_recog_data_len = 0;
738 lra_insn_recog_data = NULL;
739 init_insn_regs ();
742 /* Expand, if necessary, LRA data about insns. */
743 static void
744 check_and_expand_insn_recog_data (int index)
746 int i, old;
748 if (lra_insn_recog_data_len > index)
749 return;
750 old = lra_insn_recog_data_len;
751 lra_insn_recog_data_len = index * 3 / 2 + 1;
752 lra_insn_recog_data = XRESIZEVEC (lra_insn_recog_data_t,
753 lra_insn_recog_data,
754 lra_insn_recog_data_len);
755 for (i = old; i < lra_insn_recog_data_len; i++)
756 lra_insn_recog_data[i] = NULL;
759 /* Finish LRA DATA about insn. */
760 static void
761 free_insn_recog_data (lra_insn_recog_data_t data)
763 if (data->operand_loc != NULL)
764 free (data->operand_loc);
765 if (data->dup_loc != NULL)
766 free (data->dup_loc);
767 if (data->arg_hard_regs != NULL)
768 free (data->arg_hard_regs);
769 if (data->icode < 0 && NONDEBUG_INSN_P (data->insn))
771 if (data->insn_static_data->operand_alternative != NULL)
772 free (const_cast <operand_alternative *>
773 (data->insn_static_data->operand_alternative));
774 free_insn_regs (data->insn_static_data->hard_regs);
775 free (data->insn_static_data);
777 free_insn_regs (data->regs);
778 data->regs = NULL;
779 free (data);
782 /* Finish LRA data about all insns. */
783 static void
784 finish_insn_recog_data (void)
786 int i;
787 lra_insn_recog_data_t data;
789 for (i = 0; i < lra_insn_recog_data_len; i++)
790 if ((data = lra_insn_recog_data[i]) != NULL)
791 free_insn_recog_data (data);
792 finish_insn_regs ();
793 free (lra_insn_recog_data);
796 /* Setup info about operands in alternatives of LRA DATA of insn. */
797 static void
798 setup_operand_alternative (lra_insn_recog_data_t data,
799 const operand_alternative *op_alt)
801 int i, j, nop, nalt;
802 int icode = data->icode;
803 struct lra_static_insn_data *static_data = data->insn_static_data;
805 static_data->commutative = -1;
806 nop = static_data->n_operands;
807 nalt = static_data->n_alternatives;
808 static_data->operand_alternative = op_alt;
809 for (i = 0; i < nop; i++)
811 static_data->operand[i].early_clobber = false;
812 static_data->operand[i].is_address = false;
813 if (static_data->operand[i].constraint[0] == '%')
815 /* We currently only support one commutative pair of operands. */
816 if (static_data->commutative < 0)
817 static_data->commutative = i;
818 else
819 lra_assert (icode < 0); /* Asm */
820 /* The last operand should not be marked commutative. */
821 lra_assert (i != nop - 1);
824 for (j = 0; j < nalt; j++)
825 for (i = 0; i < nop; i++, op_alt++)
827 static_data->operand[i].early_clobber |= op_alt->earlyclobber;
828 static_data->operand[i].is_address |= op_alt->is_address;
832 /* Recursively process X and collect info about registers, which are
833 not the insn operands, in X with TYPE (in/out/inout) and flag that
834 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
835 to LIST. X is a part of insn given by DATA. Return the result
836 list. */
837 static struct lra_insn_reg *
838 collect_non_operand_hard_regs (rtx *x, lra_insn_recog_data_t data,
839 struct lra_insn_reg *list,
840 enum op_type type, bool early_clobber)
842 int i, j, regno, last;
843 bool subreg_p;
844 machine_mode mode;
845 struct lra_insn_reg *curr;
846 rtx op = *x;
847 enum rtx_code code = GET_CODE (op);
848 const char *fmt = GET_RTX_FORMAT (code);
850 for (i = 0; i < data->insn_static_data->n_operands; i++)
851 if (x == data->operand_loc[i])
852 /* It is an operand loc. Stop here. */
853 return list;
854 for (i = 0; i < data->insn_static_data->n_dups; i++)
855 if (x == data->dup_loc[i])
856 /* It is a dup loc. Stop here. */
857 return list;
858 mode = GET_MODE (op);
859 subreg_p = false;
860 if (code == SUBREG)
862 op = SUBREG_REG (op);
863 code = GET_CODE (op);
864 if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (op)))
866 mode = GET_MODE (op);
867 if (GET_MODE_SIZE (mode) > REGMODE_NATURAL_SIZE (mode))
868 subreg_p = true;
871 if (REG_P (op))
873 if ((regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER)
874 return list;
875 /* Process all regs even unallocatable ones as we need info
876 about all regs for rematerialization pass. */
877 for (last = regno + hard_regno_nregs[regno][mode];
878 regno < last;
879 regno++)
881 for (curr = list; curr != NULL; curr = curr->next)
882 if (curr->regno == regno && curr->subreg_p == subreg_p
883 && curr->biggest_mode == mode)
885 if (curr->type != type)
886 curr->type = OP_INOUT;
887 if (curr->early_clobber != early_clobber)
888 curr->early_clobber = true;
889 break;
891 if (curr == NULL)
893 /* This is a new hard regno or the info can not be
894 integrated into the found structure. */
895 #ifdef STACK_REGS
896 early_clobber
897 = (early_clobber
898 /* This clobber is to inform popping floating
899 point stack only. */
900 && ! (FIRST_STACK_REG <= regno
901 && regno <= LAST_STACK_REG));
902 #endif
903 list = new_insn_reg (data->insn, regno, type, mode, subreg_p,
904 early_clobber, list);
907 return list;
909 switch (code)
911 case SET:
912 list = collect_non_operand_hard_regs (&SET_DEST (op), data,
913 list, OP_OUT, false);
914 list = collect_non_operand_hard_regs (&SET_SRC (op), data,
915 list, OP_IN, false);
916 break;
917 case CLOBBER:
918 /* We treat clobber of non-operand hard registers as early
919 clobber (the behavior is expected from asm). */
920 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
921 list, OP_OUT, true);
922 break;
923 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
924 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
925 list, OP_INOUT, false);
926 break;
927 case PRE_MODIFY: case POST_MODIFY:
928 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
929 list, OP_INOUT, false);
930 list = collect_non_operand_hard_regs (&XEXP (op, 1), data,
931 list, OP_IN, false);
932 break;
933 default:
934 fmt = GET_RTX_FORMAT (code);
935 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
937 if (fmt[i] == 'e')
938 list = collect_non_operand_hard_regs (&XEXP (op, i), data,
939 list, OP_IN, false);
940 else if (fmt[i] == 'E')
941 for (j = XVECLEN (op, i) - 1; j >= 0; j--)
942 list = collect_non_operand_hard_regs (&XVECEXP (op, i, j), data,
943 list, OP_IN, false);
946 return list;
949 /* Set up and return info about INSN. Set up the info if it is not set up
950 yet. */
951 lra_insn_recog_data_t
952 lra_set_insn_recog_data (rtx_insn *insn)
954 lra_insn_recog_data_t data;
955 int i, n, icode;
956 rtx **locs;
957 unsigned int uid = INSN_UID (insn);
958 struct lra_static_insn_data *insn_static_data;
960 check_and_expand_insn_recog_data (uid);
961 if (DEBUG_INSN_P (insn))
962 icode = -1;
963 else
965 icode = INSN_CODE (insn);
966 if (icode < 0)
967 /* It might be a new simple insn which is not recognized yet. */
968 INSN_CODE (insn) = icode = recog_memoized (insn);
970 data = XNEW (struct lra_insn_recog_data);
971 lra_insn_recog_data[uid] = data;
972 data->insn = insn;
973 data->used_insn_alternative = -1;
974 data->icode = icode;
975 data->regs = NULL;
976 if (DEBUG_INSN_P (insn))
978 data->insn_static_data = &debug_insn_static_data;
979 data->dup_loc = NULL;
980 data->arg_hard_regs = NULL;
981 data->preferred_alternatives = ALL_ALTERNATIVES;
982 data->operand_loc = XNEWVEC (rtx *, 1);
983 data->operand_loc[0] = &INSN_VAR_LOCATION_LOC (insn);
984 return data;
986 if (icode < 0)
988 int nop, nalt;
989 machine_mode operand_mode[MAX_RECOG_OPERANDS];
990 const char *constraints[MAX_RECOG_OPERANDS];
992 nop = asm_noperands (PATTERN (insn));
993 data->operand_loc = data->dup_loc = NULL;
994 nalt = 1;
995 if (nop < 0)
997 /* It is a special insn like USE or CLOBBER. We should
998 recognize any regular insn otherwise LRA can do nothing
999 with this insn. */
1000 gcc_assert (GET_CODE (PATTERN (insn)) == USE
1001 || GET_CODE (PATTERN (insn)) == CLOBBER
1002 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
1003 data->insn_static_data = insn_static_data
1004 = get_static_insn_data (-1, 0, 0, nalt);
1006 else
1008 /* expand_asm_operands makes sure there aren't too many
1009 operands. */
1010 lra_assert (nop <= MAX_RECOG_OPERANDS);
1011 if (nop != 0)
1012 data->operand_loc = XNEWVEC (rtx *, nop);
1013 /* Now get the operand values and constraints out of the
1014 insn. */
1015 decode_asm_operands (PATTERN (insn), NULL,
1016 data->operand_loc,
1017 constraints, operand_mode, NULL);
1018 if (nop > 0)
1020 const char *p = recog_data.constraints[0];
1022 for (p = constraints[0]; *p; p++)
1023 nalt += *p == ',';
1025 data->insn_static_data = insn_static_data
1026 = get_static_insn_data (-1, nop, 0, nalt);
1027 for (i = 0; i < nop; i++)
1029 insn_static_data->operand[i].mode = operand_mode[i];
1030 insn_static_data->operand[i].constraint = constraints[i];
1031 insn_static_data->operand[i].strict_low = false;
1032 insn_static_data->operand[i].is_operator = false;
1033 insn_static_data->operand[i].is_address = false;
1036 for (i = 0; i < insn_static_data->n_operands; i++)
1037 insn_static_data->operand[i].type
1038 = (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1039 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1040 : OP_IN);
1041 data->preferred_alternatives = ALL_ALTERNATIVES;
1042 if (nop > 0)
1044 operand_alternative *op_alt = XCNEWVEC (operand_alternative,
1045 nalt * nop);
1046 preprocess_constraints (nop, nalt, constraints, op_alt);
1047 setup_operand_alternative (data, op_alt);
1050 else
1052 insn_extract (insn);
1053 data->insn_static_data = insn_static_data
1054 = get_static_insn_data (icode, insn_data[icode].n_operands,
1055 insn_data[icode].n_dups,
1056 insn_data[icode].n_alternatives);
1057 n = insn_static_data->n_operands;
1058 if (n == 0)
1059 locs = NULL;
1060 else
1062 locs = XNEWVEC (rtx *, n);
1063 memcpy (locs, recog_data.operand_loc, n * sizeof (rtx *));
1065 data->operand_loc = locs;
1066 n = insn_static_data->n_dups;
1067 if (n == 0)
1068 locs = NULL;
1069 else
1071 locs = XNEWVEC (rtx *, n);
1072 memcpy (locs, recog_data.dup_loc, n * sizeof (rtx *));
1074 data->dup_loc = locs;
1075 data->preferred_alternatives = get_preferred_alternatives (insn);
1076 const operand_alternative *op_alt = preprocess_insn_constraints (icode);
1077 if (!insn_static_data->operand_alternative)
1078 setup_operand_alternative (data, op_alt);
1079 else if (op_alt != insn_static_data->operand_alternative)
1080 insn_static_data->operand_alternative = op_alt;
1082 if (GET_CODE (PATTERN (insn)) == CLOBBER || GET_CODE (PATTERN (insn)) == USE)
1083 insn_static_data->hard_regs = NULL;
1084 else
1085 insn_static_data->hard_regs
1086 = collect_non_operand_hard_regs (&PATTERN (insn), data,
1087 NULL, OP_IN, false);
1088 data->arg_hard_regs = NULL;
1089 if (CALL_P (insn))
1091 rtx link;
1092 int n_hard_regs, regno, arg_hard_regs[FIRST_PSEUDO_REGISTER];
1094 n_hard_regs = 0;
1095 /* Finding implicit hard register usage. We believe it will be
1096 not changed whatever transformations are used. Call insns
1097 are such example. */
1098 for (link = CALL_INSN_FUNCTION_USAGE (insn);
1099 link != NULL_RTX;
1100 link = XEXP (link, 1))
1101 if (GET_CODE (XEXP (link, 0)) == USE
1102 && REG_P (XEXP (XEXP (link, 0), 0)))
1104 regno = REGNO (XEXP (XEXP (link, 0), 0));
1105 lra_assert (regno < FIRST_PSEUDO_REGISTER);
1106 /* It is an argument register. */
1107 for (i = (hard_regno_nregs
1108 [regno][GET_MODE (XEXP (XEXP (link, 0), 0))]) - 1;
1109 i >= 0;
1110 i--)
1111 arg_hard_regs[n_hard_regs++] = regno + i;
1113 if (n_hard_regs != 0)
1115 arg_hard_regs[n_hard_regs++] = -1;
1116 data->arg_hard_regs = XNEWVEC (int, n_hard_regs);
1117 memcpy (data->arg_hard_regs, arg_hard_regs,
1118 sizeof (int) * n_hard_regs);
1121 /* Some output operand can be recognized only from the context not
1122 from the constraints which are empty in this case. Call insn may
1123 contain a hard register in set destination with empty constraint
1124 and extract_insn treats them as an input. */
1125 for (i = 0; i < insn_static_data->n_operands; i++)
1127 int j;
1128 rtx pat, set;
1129 struct lra_operand_data *operand = &insn_static_data->operand[i];
1131 /* ??? Should we treat 'X' the same way. It looks to me that
1132 'X' means anything and empty constraint means we do not
1133 care. */
1134 if (operand->type != OP_IN || *operand->constraint != '\0'
1135 || operand->is_operator)
1136 continue;
1137 pat = PATTERN (insn);
1138 if (GET_CODE (pat) == SET)
1140 if (data->operand_loc[i] != &SET_DEST (pat))
1141 continue;
1143 else if (GET_CODE (pat) == PARALLEL)
1145 for (j = XVECLEN (pat, 0) - 1; j >= 0; j--)
1147 set = XVECEXP (PATTERN (insn), 0, j);
1148 if (GET_CODE (set) == SET
1149 && &SET_DEST (set) == data->operand_loc[i])
1150 break;
1152 if (j < 0)
1153 continue;
1155 else
1156 continue;
1157 operand->type = OP_OUT;
1159 return data;
1162 /* Return info about insn give by UID. The info should be already set
1163 up. */
1164 static lra_insn_recog_data_t
1165 get_insn_recog_data_by_uid (int uid)
1167 lra_insn_recog_data_t data;
1169 data = lra_insn_recog_data[uid];
1170 lra_assert (data != NULL);
1171 return data;
1174 /* Invalidate all info about insn given by its UID. */
1175 static void
1176 invalidate_insn_recog_data (int uid)
1178 lra_insn_recog_data_t data;
1180 data = lra_insn_recog_data[uid];
1181 lra_assert (data != NULL);
1182 free_insn_recog_data (data);
1183 lra_insn_recog_data[uid] = NULL;
1186 /* Update all the insn info about INSN. It is usually called when
1187 something in the insn was changed. Return the updated info. */
1188 lra_insn_recog_data_t
1189 lra_update_insn_recog_data (rtx_insn *insn)
1191 lra_insn_recog_data_t data;
1192 int n;
1193 unsigned int uid = INSN_UID (insn);
1194 struct lra_static_insn_data *insn_static_data;
1195 HOST_WIDE_INT sp_offset = 0;
1197 check_and_expand_insn_recog_data (uid);
1198 if ((data = lra_insn_recog_data[uid]) != NULL
1199 && data->icode != INSN_CODE (insn))
1201 sp_offset = data->sp_offset;
1202 invalidate_insn_data_regno_info (data, insn, get_insn_freq (insn));
1203 invalidate_insn_recog_data (uid);
1204 data = NULL;
1206 if (data == NULL)
1208 data = lra_get_insn_recog_data (insn);
1209 /* Initiate or restore SP offset. */
1210 data->sp_offset = sp_offset;
1211 return data;
1213 insn_static_data = data->insn_static_data;
1214 data->used_insn_alternative = -1;
1215 if (DEBUG_INSN_P (insn))
1216 return data;
1217 if (data->icode < 0)
1219 int nop;
1220 machine_mode operand_mode[MAX_RECOG_OPERANDS];
1221 const char *constraints[MAX_RECOG_OPERANDS];
1223 nop = asm_noperands (PATTERN (insn));
1224 if (nop >= 0)
1226 lra_assert (nop == data->insn_static_data->n_operands);
1227 /* Now get the operand values and constraints out of the
1228 insn. */
1229 decode_asm_operands (PATTERN (insn), NULL,
1230 data->operand_loc,
1231 constraints, operand_mode, NULL);
1232 #ifdef ENABLE_CHECKING
1234 int i;
1236 for (i = 0; i < nop; i++)
1237 lra_assert
1238 (insn_static_data->operand[i].mode == operand_mode[i]
1239 && insn_static_data->operand[i].constraint == constraints[i]
1240 && ! insn_static_data->operand[i].is_operator);
1242 #endif
1244 #ifdef ENABLE_CHECKING
1246 int i;
1248 for (i = 0; i < insn_static_data->n_operands; i++)
1249 lra_assert
1250 (insn_static_data->operand[i].type
1251 == (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1252 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1253 : OP_IN));
1255 #endif
1257 else
1259 insn_extract (insn);
1260 n = insn_static_data->n_operands;
1261 if (n != 0)
1262 memcpy (data->operand_loc, recog_data.operand_loc, n * sizeof (rtx *));
1263 n = insn_static_data->n_dups;
1264 if (n != 0)
1265 memcpy (data->dup_loc, recog_data.dup_loc, n * sizeof (rtx *));
1266 lra_assert (check_bool_attrs (insn));
1268 return data;
1271 /* Set up that INSN is using alternative ALT now. */
1272 void
1273 lra_set_used_insn_alternative (rtx_insn *insn, int alt)
1275 lra_insn_recog_data_t data;
1277 data = lra_get_insn_recog_data (insn);
1278 data->used_insn_alternative = alt;
1281 /* Set up that insn with UID is using alternative ALT now. The insn
1282 info should be already set up. */
1283 void
1284 lra_set_used_insn_alternative_by_uid (int uid, int alt)
1286 lra_insn_recog_data_t data;
1288 check_and_expand_insn_recog_data (uid);
1289 data = lra_insn_recog_data[uid];
1290 lra_assert (data != NULL);
1291 data->used_insn_alternative = alt;
1296 /* This page contains code dealing with common register info and
1297 pseudo copies. */
1299 /* The size of the following array. */
1300 static int reg_info_size;
1301 /* Common info about each register. */
1302 struct lra_reg *lra_reg_info;
1304 /* Last register value. */
1305 static int last_reg_value;
1307 /* Return new register value. */
1308 static int
1309 get_new_reg_value (void)
1311 return ++last_reg_value;
1314 /* Pools for copies. */
1315 static alloc_pool copy_pool;
1317 /* Vec referring to pseudo copies. */
1318 static vec<lra_copy_t> copy_vec;
1320 /* Initialize I-th element of lra_reg_info. */
1321 static inline void
1322 initialize_lra_reg_info_element (int i)
1324 bitmap_initialize (&lra_reg_info[i].insn_bitmap, &reg_obstack);
1325 #ifdef STACK_REGS
1326 lra_reg_info[i].no_stack_p = false;
1327 #endif
1328 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1329 CLEAR_HARD_REG_SET (lra_reg_info[i].actual_call_used_reg_set);
1330 lra_reg_info[i].preferred_hard_regno1 = -1;
1331 lra_reg_info[i].preferred_hard_regno2 = -1;
1332 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1333 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1334 lra_reg_info[i].biggest_mode = VOIDmode;
1335 lra_reg_info[i].live_ranges = NULL;
1336 lra_reg_info[i].nrefs = lra_reg_info[i].freq = 0;
1337 lra_reg_info[i].last_reload = 0;
1338 lra_reg_info[i].restore_regno = -1;
1339 lra_reg_info[i].val = get_new_reg_value ();
1340 lra_reg_info[i].offset = 0;
1341 lra_reg_info[i].copies = NULL;
1344 /* Initialize common reg info and copies. */
1345 static void
1346 init_reg_info (void)
1348 int i;
1350 last_reg_value = 0;
1351 reg_info_size = max_reg_num () * 3 / 2 + 1;
1352 lra_reg_info = XNEWVEC (struct lra_reg, reg_info_size);
1353 for (i = 0; i < reg_info_size; i++)
1354 initialize_lra_reg_info_element (i);
1355 copy_pool
1356 = create_alloc_pool ("lra copies", sizeof (struct lra_copy), 100);
1357 copy_vec.create (100);
1361 /* Finish common reg info and copies. */
1362 static void
1363 finish_reg_info (void)
1365 int i;
1367 for (i = 0; i < reg_info_size; i++)
1368 bitmap_clear (&lra_reg_info[i].insn_bitmap);
1369 free (lra_reg_info);
1370 reg_info_size = 0;
1371 free_alloc_pool (copy_pool);
1372 copy_vec.release ();
1375 /* Expand common reg info if it is necessary. */
1376 static void
1377 expand_reg_info (void)
1379 int i, old = reg_info_size;
1381 if (reg_info_size > max_reg_num ())
1382 return;
1383 reg_info_size = max_reg_num () * 3 / 2 + 1;
1384 lra_reg_info = XRESIZEVEC (struct lra_reg, lra_reg_info, reg_info_size);
1385 for (i = old; i < reg_info_size; i++)
1386 initialize_lra_reg_info_element (i);
1389 /* Free all copies. */
1390 void
1391 lra_free_copies (void)
1393 lra_copy_t cp;
1395 while (copy_vec.length () != 0)
1397 cp = copy_vec.pop ();
1398 lra_reg_info[cp->regno1].copies = lra_reg_info[cp->regno2].copies = NULL;
1399 pool_free (copy_pool, cp);
1403 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1404 frequency is FREQ. */
1405 void
1406 lra_create_copy (int regno1, int regno2, int freq)
1408 bool regno1_dest_p;
1409 lra_copy_t cp;
1411 lra_assert (regno1 != regno2);
1412 regno1_dest_p = true;
1413 if (regno1 > regno2)
1415 int temp = regno2;
1417 regno1_dest_p = false;
1418 regno2 = regno1;
1419 regno1 = temp;
1421 cp = (lra_copy_t) pool_alloc (copy_pool);
1422 copy_vec.safe_push (cp);
1423 cp->regno1_dest_p = regno1_dest_p;
1424 cp->freq = freq;
1425 cp->regno1 = regno1;
1426 cp->regno2 = regno2;
1427 cp->regno1_next = lra_reg_info[regno1].copies;
1428 lra_reg_info[regno1].copies = cp;
1429 cp->regno2_next = lra_reg_info[regno2].copies;
1430 lra_reg_info[regno2].copies = cp;
1431 if (lra_dump_file != NULL)
1432 fprintf (lra_dump_file, " Creating copy r%d%sr%d@%d\n",
1433 regno1, regno1_dest_p ? "<-" : "->", regno2, freq);
1436 /* Return N-th (0, 1, ...) copy. If there is no copy, return
1437 NULL. */
1438 lra_copy_t
1439 lra_get_copy (int n)
1441 if (n >= (int) copy_vec.length ())
1442 return NULL;
1443 return copy_vec[n];
1448 /* This page contains code dealing with info about registers in
1449 insns. */
1451 /* Process X of insn UID recursively and add info (operand type is
1452 given by TYPE, flag of that it is early clobber is EARLY_CLOBBER)
1453 about registers in X to the insn DATA. */
1454 static void
1455 add_regs_to_insn_regno_info (lra_insn_recog_data_t data, rtx x, int uid,
1456 enum op_type type, bool early_clobber)
1458 int i, j, regno;
1459 bool subreg_p;
1460 machine_mode mode;
1461 const char *fmt;
1462 enum rtx_code code;
1463 struct lra_insn_reg *curr;
1465 code = GET_CODE (x);
1466 mode = GET_MODE (x);
1467 subreg_p = false;
1468 if (GET_CODE (x) == SUBREG)
1470 x = SUBREG_REG (x);
1471 code = GET_CODE (x);
1472 if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (x)))
1474 mode = GET_MODE (x);
1475 if (GET_MODE_SIZE (mode) > REGMODE_NATURAL_SIZE (mode))
1476 subreg_p = true;
1479 if (REG_P (x))
1481 regno = REGNO (x);
1482 /* Process all regs even unallocatable ones as we need info about
1483 all regs for rematerialization pass. */
1484 expand_reg_info ();
1485 if (bitmap_set_bit (&lra_reg_info[regno].insn_bitmap, uid))
1487 data->regs = new_insn_reg (data->insn, regno, type, mode, subreg_p,
1488 early_clobber, data->regs);
1489 return;
1491 else
1493 for (curr = data->regs; curr != NULL; curr = curr->next)
1494 if (curr->regno == regno)
1496 if (curr->subreg_p != subreg_p || curr->biggest_mode != mode)
1497 /* The info can not be integrated into the found
1498 structure. */
1499 data->regs = new_insn_reg (data->insn, regno, type, mode,
1500 subreg_p, early_clobber,
1501 data->regs);
1502 else
1504 if (curr->type != type)
1505 curr->type = OP_INOUT;
1506 if (curr->early_clobber != early_clobber)
1507 curr->early_clobber = true;
1509 return;
1511 gcc_unreachable ();
1515 switch (code)
1517 case SET:
1518 add_regs_to_insn_regno_info (data, SET_DEST (x), uid, OP_OUT, false);
1519 add_regs_to_insn_regno_info (data, SET_SRC (x), uid, OP_IN, false);
1520 break;
1521 case CLOBBER:
1522 /* We treat clobber of non-operand hard registers as early
1523 clobber (the behavior is expected from asm). */
1524 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_OUT, true);
1525 break;
1526 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
1527 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false);
1528 break;
1529 case PRE_MODIFY: case POST_MODIFY:
1530 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false);
1531 add_regs_to_insn_regno_info (data, XEXP (x, 1), uid, OP_IN, false);
1532 break;
1533 default:
1534 if ((code != PARALLEL && code != EXPR_LIST) || type != OP_OUT)
1535 /* Some targets place small structures in registers for return
1536 values of functions, and those registers are wrapped in
1537 PARALLEL that we may see as the destination of a SET. Here
1538 is an example:
1540 (call_insn 13 12 14 2 (set (parallel:BLK [
1541 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1542 (const_int 0 [0]))
1543 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1544 (const_int 8 [0x8]))
1546 (call (mem:QI (symbol_ref:DI (... */
1547 type = OP_IN;
1548 fmt = GET_RTX_FORMAT (code);
1549 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1551 if (fmt[i] == 'e')
1552 add_regs_to_insn_regno_info (data, XEXP (x, i), uid, type, false);
1553 else if (fmt[i] == 'E')
1555 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1556 add_regs_to_insn_regno_info (data, XVECEXP (x, i, j), uid,
1557 type, false);
1563 /* Return execution frequency of INSN. */
1564 static int
1565 get_insn_freq (rtx_insn *insn)
1567 basic_block bb = BLOCK_FOR_INSN (insn);
1569 gcc_checking_assert (bb != NULL);
1570 return REG_FREQ_FROM_BB (bb);
1573 /* Invalidate all reg info of INSN with DATA and execution frequency
1574 FREQ. Update common info about the invalidated registers. */
1575 static void
1576 invalidate_insn_data_regno_info (lra_insn_recog_data_t data, rtx_insn *insn,
1577 int freq)
1579 int uid;
1580 bool debug_p;
1581 unsigned int i;
1582 struct lra_insn_reg *ir, *next_ir;
1584 uid = INSN_UID (insn);
1585 debug_p = DEBUG_INSN_P (insn);
1586 for (ir = data->regs; ir != NULL; ir = next_ir)
1588 i = ir->regno;
1589 next_ir = ir->next;
1590 free_insn_reg (ir);
1591 bitmap_clear_bit (&lra_reg_info[i].insn_bitmap, uid);
1592 if (i >= FIRST_PSEUDO_REGISTER && ! debug_p)
1594 lra_reg_info[i].nrefs--;
1595 lra_reg_info[i].freq -= freq;
1596 lra_assert (lra_reg_info[i].nrefs >= 0 && lra_reg_info[i].freq >= 0);
1599 data->regs = NULL;
1602 /* Invalidate all reg info of INSN. Update common info about the
1603 invalidated registers. */
1604 void
1605 lra_invalidate_insn_regno_info (rtx_insn *insn)
1607 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn), insn,
1608 get_insn_freq (insn));
1611 /* Update common reg info from reg info of insn given by its DATA and
1612 execution frequency FREQ. */
1613 static void
1614 setup_insn_reg_info (lra_insn_recog_data_t data, int freq)
1616 unsigned int i;
1617 struct lra_insn_reg *ir;
1619 for (ir = data->regs; ir != NULL; ir = ir->next)
1620 if ((i = ir->regno) >= FIRST_PSEUDO_REGISTER)
1622 lra_reg_info[i].nrefs++;
1623 lra_reg_info[i].freq += freq;
1627 /* Set up insn reg info of INSN. Update common reg info from reg info
1628 of INSN. */
1629 void
1630 lra_update_insn_regno_info (rtx_insn *insn)
1632 int i, uid, freq;
1633 lra_insn_recog_data_t data;
1634 struct lra_static_insn_data *static_data;
1635 enum rtx_code code;
1636 rtx link;
1638 if (! INSN_P (insn))
1639 return;
1640 data = lra_get_insn_recog_data (insn);
1641 static_data = data->insn_static_data;
1642 freq = get_insn_freq (insn);
1643 invalidate_insn_data_regno_info (data, insn, freq);
1644 uid = INSN_UID (insn);
1645 for (i = static_data->n_operands - 1; i >= 0; i--)
1646 add_regs_to_insn_regno_info (data, *data->operand_loc[i], uid,
1647 static_data->operand[i].type,
1648 static_data->operand[i].early_clobber);
1649 if ((code = GET_CODE (PATTERN (insn))) == CLOBBER || code == USE)
1650 add_regs_to_insn_regno_info (data, XEXP (PATTERN (insn), 0), uid,
1651 code == USE ? OP_IN : OP_OUT, false);
1652 if (CALL_P (insn))
1653 /* On some targets call insns can refer to pseudos in memory in
1654 CALL_INSN_FUNCTION_USAGE list. Process them in order to
1655 consider their occurrences in calls for different
1656 transformations (e.g. inheritance) with given pseudos. */
1657 for (link = CALL_INSN_FUNCTION_USAGE (insn);
1658 link != NULL_RTX;
1659 link = XEXP (link, 1))
1660 if (((code = GET_CODE (XEXP (link, 0))) == USE || code == CLOBBER)
1661 && MEM_P (XEXP (XEXP (link, 0), 0)))
1662 add_regs_to_insn_regno_info (data, XEXP (XEXP (link, 0), 0), uid,
1663 code == USE ? OP_IN : OP_OUT, false);
1664 if (NONDEBUG_INSN_P (insn))
1665 setup_insn_reg_info (data, freq);
1668 /* Return reg info of insn given by it UID. */
1669 struct lra_insn_reg *
1670 lra_get_insn_regs (int uid)
1672 lra_insn_recog_data_t data;
1674 data = get_insn_recog_data_by_uid (uid);
1675 return data->regs;
1680 /* This page contains code dealing with stack of the insns which
1681 should be processed by the next constraint pass. */
1683 /* Bitmap used to put an insn on the stack only in one exemplar. */
1684 static sbitmap lra_constraint_insn_stack_bitmap;
1686 /* The stack itself. */
1687 vec<rtx_insn *> lra_constraint_insn_stack;
1689 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1690 info for INSN, otherwise only update it if INSN is not already on the
1691 stack. */
1692 static inline void
1693 lra_push_insn_1 (rtx_insn *insn, bool always_update)
1695 unsigned int uid = INSN_UID (insn);
1696 if (always_update)
1697 lra_update_insn_regno_info (insn);
1698 if (uid >= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap))
1699 lra_constraint_insn_stack_bitmap =
1700 sbitmap_resize (lra_constraint_insn_stack_bitmap, 3 * uid / 2, 0);
1701 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap, uid))
1702 return;
1703 bitmap_set_bit (lra_constraint_insn_stack_bitmap, uid);
1704 if (! always_update)
1705 lra_update_insn_regno_info (insn);
1706 lra_constraint_insn_stack.safe_push (insn);
1709 /* Put INSN on the stack. */
1710 void
1711 lra_push_insn (rtx_insn *insn)
1713 lra_push_insn_1 (insn, false);
1716 /* Put INSN on the stack and update its reg info. */
1717 void
1718 lra_push_insn_and_update_insn_regno_info (rtx_insn *insn)
1720 lra_push_insn_1 (insn, true);
1723 /* Put insn with UID on the stack. */
1724 void
1725 lra_push_insn_by_uid (unsigned int uid)
1727 lra_push_insn (lra_insn_recog_data[uid]->insn);
1730 /* Take the last-inserted insns off the stack and return it. */
1731 rtx_insn *
1732 lra_pop_insn (void)
1734 rtx_insn *insn = lra_constraint_insn_stack.pop ();
1735 bitmap_clear_bit (lra_constraint_insn_stack_bitmap, INSN_UID (insn));
1736 return insn;
1739 /* Return the current size of the insn stack. */
1740 unsigned int
1741 lra_insn_stack_length (void)
1743 return lra_constraint_insn_stack.length ();
1746 /* Push insns FROM to TO (excluding it) going in reverse order. */
1747 static void
1748 push_insns (rtx_insn *from, rtx_insn *to)
1750 rtx_insn *insn;
1752 if (from == NULL_RTX)
1753 return;
1754 for (insn = from; insn != to; insn = PREV_INSN (insn))
1755 if (INSN_P (insn))
1756 lra_push_insn (insn);
1759 /* Set up sp offset for insn in range [FROM, LAST]. The offset is
1760 taken from the next BB insn after LAST or zero if there in such
1761 insn. */
1762 static void
1763 setup_sp_offset (rtx_insn *from, rtx_insn *last)
1765 rtx_insn *before = next_nonnote_insn_bb (last);
1766 HOST_WIDE_INT offset = (before == NULL_RTX || ! INSN_P (before)
1767 ? 0 : lra_get_insn_recog_data (before)->sp_offset);
1769 for (rtx_insn *insn = from; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
1770 lra_get_insn_recog_data (insn)->sp_offset = offset;
1773 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1774 insns onto the stack. Print about emitting the insns with
1775 TITLE. */
1776 void
1777 lra_process_new_insns (rtx_insn *insn, rtx_insn *before, rtx_insn *after,
1778 const char *title)
1780 rtx_insn *last;
1782 if (before == NULL_RTX && after == NULL_RTX)
1783 return;
1784 if (lra_dump_file != NULL)
1786 dump_insn_slim (lra_dump_file, insn);
1787 if (before != NULL_RTX)
1789 fprintf (lra_dump_file," %s before:\n", title);
1790 dump_rtl_slim (lra_dump_file, before, NULL, -1, 0);
1792 if (after != NULL_RTX)
1794 fprintf (lra_dump_file, " %s after:\n", title);
1795 dump_rtl_slim (lra_dump_file, after, NULL, -1, 0);
1797 fprintf (lra_dump_file, "\n");
1799 if (before != NULL_RTX)
1801 emit_insn_before (before, insn);
1802 push_insns (PREV_INSN (insn), PREV_INSN (before));
1803 setup_sp_offset (before, PREV_INSN (insn));
1805 if (after != NULL_RTX)
1807 for (last = after; NEXT_INSN (last) != NULL_RTX; last = NEXT_INSN (last))
1809 emit_insn_after (after, insn);
1810 push_insns (last, insn);
1811 setup_sp_offset (after, last);
1817 /* Replace all references to register OLD_REGNO in *LOC with pseudo
1818 register NEW_REG. Return true if any change was made. */
1819 bool
1820 lra_substitute_pseudo (rtx *loc, int old_regno, rtx new_reg)
1822 rtx x = *loc;
1823 bool result = false;
1824 enum rtx_code code;
1825 const char *fmt;
1826 int i, j;
1828 if (x == NULL_RTX)
1829 return false;
1831 code = GET_CODE (x);
1832 if (code == REG && (int) REGNO (x) == old_regno)
1834 machine_mode mode = GET_MODE (*loc);
1835 machine_mode inner_mode = GET_MODE (new_reg);
1837 if (mode != inner_mode
1838 && ! (CONST_INT_P (new_reg) && SCALAR_INT_MODE_P (mode)))
1840 if (GET_MODE_SIZE (mode) >= GET_MODE_SIZE (inner_mode)
1841 || ! SCALAR_INT_MODE_P (inner_mode))
1842 new_reg = gen_rtx_SUBREG (mode, new_reg, 0);
1843 else
1844 new_reg = gen_lowpart_SUBREG (mode, new_reg);
1846 *loc = new_reg;
1847 return true;
1850 /* Scan all the operand sub-expressions. */
1851 fmt = GET_RTX_FORMAT (code);
1852 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1854 if (fmt[i] == 'e')
1856 if (lra_substitute_pseudo (&XEXP (x, i), old_regno, new_reg))
1857 result = true;
1859 else if (fmt[i] == 'E')
1861 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1862 if (lra_substitute_pseudo (&XVECEXP (x, i, j), old_regno, new_reg))
1863 result = true;
1866 return result;
1869 /* Call lra_substitute_pseudo within an insn. This won't update the insn ptr,
1870 just the contents of the insn. */
1871 bool
1872 lra_substitute_pseudo_within_insn (rtx_insn *insn, int old_regno, rtx new_reg)
1874 rtx loc = insn;
1875 return lra_substitute_pseudo (&loc, old_regno, new_reg);
1880 /* This page contains code dealing with scratches (changing them onto
1881 pseudos and restoring them from the pseudos).
1883 We change scratches into pseudos at the beginning of LRA to
1884 simplify dealing with them (conflicts, hard register assignments).
1886 If the pseudo denoting scratch was spilled it means that we do need
1887 a hard register for it. Such pseudos are transformed back to
1888 scratches at the end of LRA. */
1890 /* Description of location of a former scratch operand. */
1891 struct sloc
1893 rtx_insn *insn; /* Insn where the scratch was. */
1894 int nop; /* Number of the operand which was a scratch. */
1897 typedef struct sloc *sloc_t;
1899 /* Locations of the former scratches. */
1900 static vec<sloc_t> scratches;
1902 /* Bitmap of scratch regnos. */
1903 static bitmap_head scratch_bitmap;
1905 /* Bitmap of scratch operands. */
1906 static bitmap_head scratch_operand_bitmap;
1908 /* Return true if pseudo REGNO is made of SCRATCH. */
1909 bool
1910 lra_former_scratch_p (int regno)
1912 return bitmap_bit_p (&scratch_bitmap, regno);
1915 /* Return true if the operand NOP of INSN is a former scratch. */
1916 bool
1917 lra_former_scratch_operand_p (rtx_insn *insn, int nop)
1919 return bitmap_bit_p (&scratch_operand_bitmap,
1920 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop) != 0;
1923 /* Register operand NOP in INSN as a former scratch. It will be
1924 changed to scratch back, if it is necessary, at the LRA end. */
1925 void
1926 lra_register_new_scratch_op (rtx_insn *insn, int nop)
1928 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
1929 rtx op = *id->operand_loc[nop];
1930 sloc_t loc = XNEW (struct sloc);
1931 lra_assert (REG_P (op));
1932 loc->insn = insn;
1933 loc->nop = nop;
1934 scratches.safe_push (loc);
1935 bitmap_set_bit (&scratch_bitmap, REGNO (op));
1936 bitmap_set_bit (&scratch_operand_bitmap,
1937 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop);
1938 add_reg_note (insn, REG_UNUSED, op);
1941 /* Change scratches onto pseudos and save their location. */
1942 static void
1943 remove_scratches (void)
1945 int i;
1946 bool insn_changed_p;
1947 basic_block bb;
1948 rtx_insn *insn;
1949 rtx reg;
1950 lra_insn_recog_data_t id;
1951 struct lra_static_insn_data *static_id;
1953 scratches.create (get_max_uid ());
1954 bitmap_initialize (&scratch_bitmap, &reg_obstack);
1955 bitmap_initialize (&scratch_operand_bitmap, &reg_obstack);
1956 FOR_EACH_BB_FN (bb, cfun)
1957 FOR_BB_INSNS (bb, insn)
1958 if (INSN_P (insn))
1960 id = lra_get_insn_recog_data (insn);
1961 static_id = id->insn_static_data;
1962 insn_changed_p = false;
1963 for (i = 0; i < static_id->n_operands; i++)
1964 if (GET_CODE (*id->operand_loc[i]) == SCRATCH
1965 && GET_MODE (*id->operand_loc[i]) != VOIDmode)
1967 insn_changed_p = true;
1968 *id->operand_loc[i] = reg
1969 = lra_create_new_reg (static_id->operand[i].mode,
1970 *id->operand_loc[i], ALL_REGS, NULL);
1971 lra_register_new_scratch_op (insn, i);
1972 if (lra_dump_file != NULL)
1973 fprintf (lra_dump_file,
1974 "Removing SCRATCH in insn #%u (nop %d)\n",
1975 INSN_UID (insn), i);
1977 if (insn_changed_p)
1978 /* Because we might use DF right after caller-saves sub-pass
1979 we need to keep DF info up to date. */
1980 df_insn_rescan (insn);
1984 /* Changes pseudos created by function remove_scratches onto scratches. */
1985 static void
1986 restore_scratches (void)
1988 int regno;
1989 unsigned i;
1990 sloc_t loc;
1991 rtx_insn *last = NULL;
1992 lra_insn_recog_data_t id = NULL;
1994 for (i = 0; scratches.iterate (i, &loc); i++)
1996 if (last != loc->insn)
1998 last = loc->insn;
1999 id = lra_get_insn_recog_data (last);
2001 if (REG_P (*id->operand_loc[loc->nop])
2002 && ((regno = REGNO (*id->operand_loc[loc->nop]))
2003 >= FIRST_PSEUDO_REGISTER)
2004 && lra_get_regno_hard_regno (regno) < 0)
2006 /* It should be only case when scratch register with chosen
2007 constraint 'X' did not get memory or hard register. */
2008 lra_assert (lra_former_scratch_p (regno));
2009 *id->operand_loc[loc->nop]
2010 = gen_rtx_SCRATCH (GET_MODE (*id->operand_loc[loc->nop]));
2011 lra_update_dup (id, loc->nop);
2012 if (lra_dump_file != NULL)
2013 fprintf (lra_dump_file, "Restoring SCRATCH in insn #%u(nop %d)\n",
2014 INSN_UID (loc->insn), loc->nop);
2017 for (i = 0; scratches.iterate (i, &loc); i++)
2018 free (loc);
2019 scratches.release ();
2020 bitmap_clear (&scratch_bitmap);
2021 bitmap_clear (&scratch_operand_bitmap);
2026 #ifdef ENABLE_CHECKING
2028 /* Function checks RTL for correctness. If FINAL_P is true, it is
2029 done at the end of LRA and the check is more rigorous. */
2030 static void
2031 check_rtl (bool final_p)
2033 basic_block bb;
2034 rtx_insn *insn;
2036 lra_assert (! final_p || reload_completed);
2037 FOR_EACH_BB_FN (bb, cfun)
2038 FOR_BB_INSNS (bb, insn)
2039 if (NONDEBUG_INSN_P (insn)
2040 && GET_CODE (PATTERN (insn)) != USE
2041 && GET_CODE (PATTERN (insn)) != CLOBBER
2042 && GET_CODE (PATTERN (insn)) != ASM_INPUT)
2044 if (final_p)
2046 #ifdef ENABLED_CHECKING
2047 extract_constrain_insn (insn);
2048 #endif
2049 continue;
2051 /* LRA code is based on assumption that all addresses can be
2052 correctly decomposed. LRA can generate reloads for
2053 decomposable addresses. The decomposition code checks the
2054 correctness of the addresses. So we don't need to check
2055 the addresses here. Don't call insn_invalid_p here, it can
2056 change the code at this stage. */
2057 if (recog_memoized (insn) < 0 && asm_noperands (PATTERN (insn)) < 0)
2058 fatal_insn_not_found (insn);
2061 #endif /* #ifdef ENABLE_CHECKING */
2063 /* Determine if the current function has an exception receiver block
2064 that reaches the exit block via non-exceptional edges */
2065 static bool
2066 has_nonexceptional_receiver (void)
2068 edge e;
2069 edge_iterator ei;
2070 basic_block *tos, *worklist, bb;
2072 /* If we're not optimizing, then just err on the safe side. */
2073 if (!optimize)
2074 return true;
2076 /* First determine which blocks can reach exit via normal paths. */
2077 tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1);
2079 FOR_EACH_BB_FN (bb, cfun)
2080 bb->flags &= ~BB_REACHABLE;
2082 /* Place the exit block on our worklist. */
2083 EXIT_BLOCK_PTR_FOR_FN (cfun)->flags |= BB_REACHABLE;
2084 *tos++ = EXIT_BLOCK_PTR_FOR_FN (cfun);
2086 /* Iterate: find everything reachable from what we've already seen. */
2087 while (tos != worklist)
2089 bb = *--tos;
2091 FOR_EACH_EDGE (e, ei, bb->preds)
2092 if (e->flags & EDGE_ABNORMAL)
2094 free (worklist);
2095 return true;
2097 else
2099 basic_block src = e->src;
2101 if (!(src->flags & BB_REACHABLE))
2103 src->flags |= BB_REACHABLE;
2104 *tos++ = src;
2108 free (worklist);
2109 /* No exceptional block reached exit unexceptionally. */
2110 return false;
2113 #ifdef AUTO_INC_DEC
2115 /* Process recursively X of INSN and add REG_INC notes if necessary. */
2116 static void
2117 add_auto_inc_notes (rtx_insn *insn, rtx x)
2119 enum rtx_code code = GET_CODE (x);
2120 const char *fmt;
2121 int i, j;
2123 if (code == MEM && auto_inc_p (XEXP (x, 0)))
2125 add_reg_note (insn, REG_INC, XEXP (XEXP (x, 0), 0));
2126 return;
2129 /* Scan all X sub-expressions. */
2130 fmt = GET_RTX_FORMAT (code);
2131 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2133 if (fmt[i] == 'e')
2134 add_auto_inc_notes (insn, XEXP (x, i));
2135 else if (fmt[i] == 'E')
2136 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2137 add_auto_inc_notes (insn, XVECEXP (x, i, j));
2141 #endif
2143 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2144 We change pseudos by hard registers without notification of DF and
2145 that can make the notes obsolete. DF-infrastructure does not deal
2146 with REG_INC notes -- so we should regenerate them here. */
2147 static void
2148 update_inc_notes (void)
2150 rtx *pnote;
2151 basic_block bb;
2152 rtx_insn *insn;
2154 FOR_EACH_BB_FN (bb, cfun)
2155 FOR_BB_INSNS (bb, insn)
2156 if (NONDEBUG_INSN_P (insn))
2158 pnote = &REG_NOTES (insn);
2159 while (*pnote != 0)
2161 if (REG_NOTE_KIND (*pnote) == REG_DEAD
2162 || REG_NOTE_KIND (*pnote) == REG_UNUSED
2163 || REG_NOTE_KIND (*pnote) == REG_INC)
2164 *pnote = XEXP (*pnote, 1);
2165 else
2166 pnote = &XEXP (*pnote, 1);
2168 #ifdef AUTO_INC_DEC
2169 add_auto_inc_notes (insn, PATTERN (insn));
2170 #endif
2174 /* Set to 1 while in lra. */
2175 int lra_in_progress;
2177 /* Start of pseudo regnos before the LRA. */
2178 int lra_new_regno_start;
2180 /* Start of reload pseudo regnos before the new spill pass. */
2181 int lra_constraint_new_regno_start;
2183 /* Avoid spilling pseudos with regno more than the following value if
2184 it is possible. */
2185 int lra_bad_spill_regno_start;
2187 /* Inheritance pseudo regnos before the new spill pass. */
2188 bitmap_head lra_inheritance_pseudos;
2190 /* Split regnos before the new spill pass. */
2191 bitmap_head lra_split_regs;
2193 /* Reload pseudo regnos before the new assignmnet pass which still can
2194 be spilled after the assinment pass as memory is also accepted in
2195 insns for the reload pseudos. */
2196 bitmap_head lra_optional_reload_pseudos;
2198 /* Pseudo regnos used for subreg reloads before the new assignment
2199 pass. Such pseudos still can be spilled after the assinment
2200 pass. */
2201 bitmap_head lra_subreg_reload_pseudos;
2203 /* File used for output of LRA debug information. */
2204 FILE *lra_dump_file;
2206 /* True if we should try spill into registers of different classes
2207 instead of memory. */
2208 bool lra_reg_spill_p;
2210 /* Set up value LRA_REG_SPILL_P. */
2211 static void
2212 setup_reg_spill_flag (void)
2214 int cl, mode;
2216 if (targetm.spill_class != NULL)
2217 for (cl = 0; cl < (int) LIM_REG_CLASSES; cl++)
2218 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
2219 if (targetm.spill_class ((enum reg_class) cl,
2220 (machine_mode) mode) != NO_REGS)
2222 lra_reg_spill_p = true;
2223 return;
2225 lra_reg_spill_p = false;
2228 /* True if the current function is too big to use regular algorithms
2229 in LRA. In other words, we should use simpler and faster algorithms
2230 in LRA. It also means we should not worry about generation code
2231 for caller saves. The value is set up in IRA. */
2232 bool lra_simple_p;
2234 /* Major LRA entry function. F is a file should be used to dump LRA
2235 debug info. */
2236 void
2237 lra (FILE *f)
2239 int i;
2240 bool live_p, scratch_p, inserted_p;
2242 lra_dump_file = f;
2244 timevar_push (TV_LRA);
2246 /* Make sure that the last insn is a note. Some subsequent passes
2247 need it. */
2248 emit_note (NOTE_INSN_DELETED);
2250 COPY_HARD_REG_SET (lra_no_alloc_regs, ira_no_alloc_regs);
2252 init_reg_info ();
2253 expand_reg_info ();
2255 init_insn_recog_data ();
2257 #ifdef ENABLE_CHECKING
2258 /* Some quick check on RTL generated by previous passes. */
2259 check_rtl (false);
2260 #endif
2262 lra_in_progress = 1;
2264 lra_live_range_iter = lra_coalesce_iter = lra_constraint_iter = 0;
2265 lra_assignment_iter = lra_assignment_iter_after_spill = 0;
2266 lra_inheritance_iter = lra_undo_inheritance_iter = 0;
2267 lra_rematerialization_iter = 0;
2269 setup_reg_spill_flag ();
2271 /* Function remove_scratches can creates new pseudos for clobbers --
2272 so set up lra_constraint_new_regno_start before its call to
2273 permit changing reg classes for pseudos created by this
2274 simplification. */
2275 lra_constraint_new_regno_start = lra_new_regno_start = max_reg_num ();
2276 lra_bad_spill_regno_start = INT_MAX;
2277 remove_scratches ();
2278 scratch_p = lra_constraint_new_regno_start != max_reg_num ();
2280 /* A function that has a non-local label that can reach the exit
2281 block via non-exceptional paths must save all call-saved
2282 registers. */
2283 if (cfun->has_nonlocal_label && has_nonexceptional_receiver ())
2284 crtl->saves_all_registers = 1;
2286 if (crtl->saves_all_registers)
2287 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2288 if (! call_used_regs[i] && ! fixed_regs[i] && ! LOCAL_REGNO (i))
2289 df_set_regs_ever_live (i, true);
2291 /* We don't DF from now and avoid its using because it is to
2292 expensive when a lot of RTL changes are made. */
2293 df_set_flags (DF_NO_INSN_RESCAN);
2294 lra_constraint_insn_stack.create (get_max_uid ());
2295 lra_constraint_insn_stack_bitmap = sbitmap_alloc (get_max_uid ());
2296 bitmap_clear (lra_constraint_insn_stack_bitmap);
2297 lra_live_ranges_init ();
2298 lra_constraints_init ();
2299 lra_curr_reload_num = 0;
2300 push_insns (get_last_insn (), NULL);
2301 /* It is needed for the 1st coalescing. */
2302 bitmap_initialize (&lra_inheritance_pseudos, &reg_obstack);
2303 bitmap_initialize (&lra_split_regs, &reg_obstack);
2304 bitmap_initialize (&lra_optional_reload_pseudos, &reg_obstack);
2305 bitmap_initialize (&lra_subreg_reload_pseudos, &reg_obstack);
2306 live_p = false;
2307 if (get_frame_size () != 0 && crtl->stack_alignment_needed)
2308 /* If we have a stack frame, we must align it now. The stack size
2309 may be a part of the offset computation for register
2310 elimination. */
2311 assign_stack_local (BLKmode, 0, crtl->stack_alignment_needed);
2312 lra_init_equiv ();
2313 for (;;)
2315 for (;;)
2317 /* We should try to assign hard registers to scratches even
2318 if there were no RTL transformations in
2319 lra_constraints. */
2320 if (! lra_constraints (lra_constraint_iter == 0)
2321 && (lra_constraint_iter > 1
2322 || (! scratch_p && ! caller_save_needed)))
2323 break;
2324 /* Constraint transformations may result in that eliminable
2325 hard regs become uneliminable and pseudos which use them
2326 should be spilled. It is better to do it before pseudo
2327 assignments.
2329 For example, rs6000 can make
2330 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2331 to use a constant pool. */
2332 lra_eliminate (false, false);
2333 /* Do inheritance only for regular algorithms. */
2334 if (! lra_simple_p)
2336 if (flag_ipa_ra)
2338 if (live_p)
2339 lra_clear_live_ranges ();
2340 /* As a side-effect of lra_create_live_ranges, we calculate
2341 actual_call_used_reg_set, which is needed during
2342 lra_inheritance. */
2343 lra_create_live_ranges (true, true);
2344 live_p = true;
2346 lra_inheritance ();
2348 if (live_p)
2349 lra_clear_live_ranges ();
2350 /* We need live ranges for lra_assign -- so build them. But
2351 don't remove dead insns or change global live info as we
2352 can undo inheritance transformations after inheritance
2353 pseudo assigning. */
2354 lra_create_live_ranges (true, false);
2355 live_p = true;
2356 /* If we don't spill non-reload and non-inheritance pseudos,
2357 there is no sense to run memory-memory move coalescing.
2358 If inheritance pseudos were spilled, the memory-memory
2359 moves involving them will be removed by pass undoing
2360 inheritance. */
2361 if (lra_simple_p)
2362 lra_assign ();
2363 else
2365 bool spill_p = !lra_assign ();
2367 if (lra_undo_inheritance ())
2368 live_p = false;
2369 if (spill_p)
2371 if (! live_p)
2373 lra_create_live_ranges (true, true);
2374 live_p = true;
2376 if (lra_coalesce ())
2377 live_p = false;
2379 if (! live_p)
2380 lra_clear_live_ranges ();
2383 /* Don't clear optional reloads bitmap until all constraints are
2384 satisfied as we need to differ them from regular reloads. */
2385 bitmap_clear (&lra_optional_reload_pseudos);
2386 bitmap_clear (&lra_subreg_reload_pseudos);
2387 bitmap_clear (&lra_inheritance_pseudos);
2388 bitmap_clear (&lra_split_regs);
2389 if (! live_p)
2391 /* We need full live info for spilling pseudos into
2392 registers instead of memory. */
2393 lra_create_live_ranges (lra_reg_spill_p, true);
2394 live_p = true;
2396 /* We should check necessity for spilling here as the above live
2397 range pass can remove spilled pseudos. */
2398 if (! lra_need_for_spills_p ())
2399 break;
2400 /* Now we know what pseudos should be spilled. Try to
2401 rematerialize them first. */
2402 if (lra_remat ())
2404 /* We need full live info -- see the comment above. */
2405 lra_create_live_ranges (lra_reg_spill_p, true);
2406 live_p = true;
2407 if (! lra_need_for_spills_p ())
2408 break;
2410 lra_spill ();
2411 /* Assignment of stack slots changes elimination offsets for
2412 some eliminations. So update the offsets here. */
2413 lra_eliminate (false, false);
2414 lra_constraint_new_regno_start = max_reg_num ();
2415 if (lra_bad_spill_regno_start == INT_MAX
2416 && lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES
2417 && lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
2418 /* After switching off inheritance and rematerialization
2419 passes, avoid spilling reload pseudos will be created to
2420 prevent LRA cycling in some complicated cases. */
2421 lra_bad_spill_regno_start = lra_constraint_new_regno_start;
2422 lra_assignment_iter_after_spill = 0;
2424 restore_scratches ();
2425 lra_eliminate (true, false);
2426 lra_final_code_change ();
2427 lra_in_progress = 0;
2428 if (live_p)
2429 lra_clear_live_ranges ();
2430 lra_live_ranges_finish ();
2431 lra_constraints_finish ();
2432 finish_reg_info ();
2433 sbitmap_free (lra_constraint_insn_stack_bitmap);
2434 lra_constraint_insn_stack.release ();
2435 finish_insn_recog_data ();
2436 regstat_free_n_sets_and_refs ();
2437 regstat_free_ri ();
2438 reload_completed = 1;
2439 update_inc_notes ();
2441 inserted_p = fixup_abnormal_edges ();
2443 /* We've possibly turned single trapping insn into multiple ones. */
2444 if (cfun->can_throw_non_call_exceptions)
2446 sbitmap blocks;
2447 blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
2448 bitmap_ones (blocks);
2449 find_many_sub_basic_blocks (blocks);
2450 sbitmap_free (blocks);
2453 if (inserted_p)
2454 commit_edge_insertions ();
2456 /* Replacing pseudos with their memory equivalents might have
2457 created shared rtx. Subsequent passes would get confused
2458 by this, so unshare everything here. */
2459 unshare_all_rtl_again (get_insns ());
2461 #ifdef ENABLE_CHECKING
2462 check_rtl (true);
2463 #endif
2465 timevar_pop (TV_LRA);
2468 /* Called once per compiler to initialize LRA data once. */
2469 void
2470 lra_init_once (void)
2472 init_insn_code_data_once ();
2475 /* Called once per compiler to finish LRA data which are initialize
2476 once. */
2477 void
2478 lra_finish_once (void)
2480 finish_insn_code_data_once ();