1/* LRA (local register allocator) driver and LRA utilities.
2 Copyright (C) 2010-2017 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21
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.
26
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)
33
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.
44
45 Here is block diagram of LRA passes:
46
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
74 V
75 -------------------------
76 | Hard regs substitution, |
77 | devirtalization, and |------> Finish
78 | restoring scratches got |
79 | memory |
80 -------------------------
81
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).
99
100 This file contains LRA driver, LRA utility functions and data, and
101 code for dealing with scratches. */
102
103#include "config.h"
104#include "system.h"
105#include "coretypes.h"
106#include "backend.h"
107#include "target.h"
108#include "rtl.h"
109#include "tree.h"
110#include "predict.h"
111#include "df.h"
112#include "memmodel.h"
113#include "tm_p.h"
114#include "optabs.h"
115#include "regs.h"
116#include "ira.h"
117#include "recog.h"
118#include "expr.h"
119#include "cfgrtl.h"
120#include "cfgbuild.h"
121#include "lra.h"
122#include "lra-int.h"
123#include "print-rtl.h"
124
125/* Dump bitmap SET with TITLE and BB INDEX. */
126void
127lra_dump_bitmap_with_title (const char *title, bitmap set, int index)
128{
129 unsigned int i;
130 int count;
131 bitmap_iterator bi;
132 static const int max_nums_on_line = 10;
133
134 if (bitmap_empty_p (set))
135 return;
136 fprintf (lra_dump_file, " %s %d:", title, index);
137 fprintf (lra_dump_file, "\n");
138 count = max_nums_on_line + 1;
139 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
140 {
141 if (count > max_nums_on_line)
142 {
143 fprintf (lra_dump_file, "\n ");
144 count = 0;
145 }
146 fprintf (lra_dump_file, " %4u", i);
147 count++;
148 }
149 fprintf (lra_dump_file, "\n");
150}
151
152/* Hard registers currently not available for allocation. It can
153 changed after some hard registers become not eliminable. */
154HARD_REG_SET lra_no_alloc_regs;
155
156static int get_new_reg_value (void);
157static void expand_reg_info (void);
158static void invalidate_insn_recog_data (int);
159static int get_insn_freq (rtx_insn *);
160static void invalidate_insn_data_regno_info (lra_insn_recog_data_t,
161 rtx_insn *, int);
162
163/* Expand all regno related info needed for LRA. */
164static void
165expand_reg_data (int old)
166{
167 resize_reg_info ();
168 expand_reg_info ();
169 ira_expand_reg_equiv ();
170 for (int i = (int) max_reg_num () - 1; i >= old; i--)
171 lra_change_class (i, ALL_REGS, " Set", true);
172}
173
174/* Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL
175 or of VOIDmode, use MD_MODE for the new reg. Initialize its
176 register class to RCLASS. Print message about assigning class
177 RCLASS containing new register name TITLE unless it is NULL. Use
178 attributes of ORIGINAL if it is a register. The created register
179 will have unique held value. */
180rtx
181lra_create_new_reg_with_unique_value (machine_mode md_mode, rtx original,
182 enum reg_class rclass, const char *title)
183{
184 machine_mode mode;
185 rtx new_reg;
186
187 if (original == NULL_RTX || (mode = GET_MODE (original)) == VOIDmode)
188 mode = md_mode;
189 lra_assert (mode != VOIDmode);
190 new_reg = gen_reg_rtx (mode);
191 if (original == NULL_RTX || ! REG_P (original))
192 {
193 if (lra_dump_file != NULL)
194 fprintf (lra_dump_file, " Creating newreg=%i", REGNO (new_reg));
195 }
196 else
197 {
198 if (ORIGINAL_REGNO (original) >= FIRST_PSEUDO_REGISTER)
199 ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original);
200 REG_USERVAR_P (new_reg) = REG_USERVAR_P (original);
201 REG_POINTER (new_reg) = REG_POINTER (original);
202 REG_ATTRS (new_reg) = REG_ATTRS (original);
203 if (lra_dump_file != NULL)
204 fprintf (lra_dump_file, " Creating newreg=%i from oldreg=%i",
205 REGNO (new_reg), REGNO (original));
206 }
207 if (lra_dump_file != NULL)
208 {
209 if (title != NULL)
210 fprintf (lra_dump_file, ", assigning class %s to%s%s r%d",
211 reg_class_names[rclass], *title == '\0' ? "" : " ",
212 title, REGNO (new_reg));
213 fprintf (lra_dump_file, "\n");
214 }
215 expand_reg_data (max_reg_num ());
216 setup_reg_classes (REGNO (new_reg), rclass, NO_REGS, rclass);
217 return new_reg;
218}
219
220/* Analogous to the previous function but also inherits value of
221 ORIGINAL. */
222rtx
223lra_create_new_reg (machine_mode md_mode, rtx original,
224 enum reg_class rclass, const char *title)
225{
226 rtx new_reg;
227
228 new_reg
229 = lra_create_new_reg_with_unique_value (md_mode, original, rclass, title);
230 if (original != NULL_RTX && REG_P (original))
231 lra_assign_reg_val (REGNO (original), REGNO (new_reg));
232 return new_reg;
233}
234
235/* Set up for REGNO unique hold value. */
236void
237lra_set_regno_unique_value (int regno)
238{
239 lra_reg_info[regno].val = get_new_reg_value ();
240}
241
242/* Invalidate INSN related info used by LRA. The info should never be
243 used after that. */
244void
245lra_invalidate_insn_data (rtx_insn *insn)
246{
247 lra_invalidate_insn_regno_info (insn);
248 invalidate_insn_recog_data (INSN_UID (insn));
249}
250
251/* Mark INSN deleted and invalidate the insn related info used by
252 LRA. */
253void
254lra_set_insn_deleted (rtx_insn *insn)
255{
256 lra_invalidate_insn_data (insn);
257 SET_INSN_DELETED (insn);
258}
259
260/* Delete an unneeded INSN and any previous insns who sole purpose is
261 loading data that is dead in INSN. */
262void
263lra_delete_dead_insn (rtx_insn *insn)
264{
265 rtx_insn *prev = prev_real_insn (insn);
266 rtx prev_dest;
267
268 /* If the previous insn sets a register that dies in our insn,
269 delete it too. */
270 if (prev && GET_CODE (PATTERN (prev)) == SET
271 && (prev_dest = SET_DEST (PATTERN (prev)), REG_P (prev_dest))
272 && reg_mentioned_p (prev_dest, PATTERN (insn))
273 && find_regno_note (insn, REG_DEAD, REGNO (prev_dest))
274 && ! side_effects_p (SET_SRC (PATTERN (prev))))
275 lra_delete_dead_insn (prev);
276
277 lra_set_insn_deleted (insn);
278}
279
280/* Emit insn x = y + z. Return NULL if we failed to do it.
281 Otherwise, return the insn. We don't use gen_add3_insn as it might
282 clobber CC. */
283static rtx_insn *
284emit_add3_insn (rtx x, rtx y, rtx z)
285{
286 rtx_insn *last;
287
288 last = get_last_insn ();
289
290 if (have_addptr3_insn (x, y, z))
291 {
292 rtx_insn *insn = gen_addptr3_insn (x, y, z);
293
294 /* If the target provides an "addptr" pattern it hopefully does
295 for a reason. So falling back to the normal add would be
296 a bug. */
297 lra_assert (insn != NULL_RTX);
298 emit_insn (insn);
299 return insn;
300 }
301
302 rtx_insn *insn = emit_insn (gen_rtx_SET (x, gen_rtx_PLUS (GET_MODE (y),
303 y, z)));
304 if (recog_memoized (insn) < 0)
305 {
306 delete_insns_since (last);
307 insn = NULL;
308 }
309 return insn;
310}
311
312/* Emit insn x = x + y. Return the insn. We use gen_add2_insn as the
313 last resort. */
314static rtx_insn *
315emit_add2_insn (rtx x, rtx y)
316{
317 rtx_insn *insn = emit_add3_insn (x, x, y);
318 if (insn == NULL_RTX)
319 {
320 insn = gen_add2_insn (x, y);
321 if (insn != NULL_RTX)
322 emit_insn (insn);
323 }
324 return insn;
325}
326
327/* Target checks operands through operand predicates to recognize an
328 insn. We should have a special precaution to generate add insns
329 which are frequent results of elimination.
330
331 Emit insns for x = y + z. X can be used to store intermediate
332 values and should be not in Y and Z when we use X to store an
333 intermediate value. Y + Z should form [base] [+ index[ * scale]] [
334 + disp] where base and index are registers, disp and scale are
335 constants. Y should contain base if it is present, Z should
336 contain disp if any. index[*scale] can be part of Y or Z. */
337void
338lra_emit_add (rtx x, rtx y, rtx z)
339{
340 int old;
341 rtx_insn *last;
342 rtx a1, a2, base, index, disp, scale, index_scale;
343 bool ok_p;
344
345 rtx_insn *add3_insn = emit_add3_insn (x, y, z);
346 old = max_reg_num ();
347 if (add3_insn != NULL)
348 ;
349 else
350 {
351 disp = a2 = NULL_RTX;
352 if (GET_CODE (y) == PLUS)
353 {
354 a1 = XEXP (y, 0);
355 a2 = XEXP (y, 1);
356 disp = z;
357 }
358 else
359 {
360 a1 = y;
361 if (CONSTANT_P (z))
362 disp = z;
363 else
364 a2 = z;
365 }
366 index_scale = scale = NULL_RTX;
367 if (GET_CODE (a1) == MULT)
368 {
369 index_scale = a1;
370 index = XEXP (a1, 0);
371 scale = XEXP (a1, 1);
372 base = a2;
373 }
374 else if (a2 != NULL_RTX && GET_CODE (a2) == MULT)
375 {
376 index_scale = a2;
377 index = XEXP (a2, 0);
378 scale = XEXP (a2, 1);
379 base = a1;
380 }
381 else
382 {
383 base = a1;
384 index = a2;
385 }
386 if ((base != NULL_RTX && ! (REG_P (base) || GET_CODE (base) == SUBREG))
387 || (index != NULL_RTX
388 && ! (REG_P (index) || GET_CODE (index) == SUBREG))
389 || (disp != NULL_RTX && ! CONSTANT_P (disp))
390 || (scale != NULL_RTX && ! CONSTANT_P (scale)))
391 {
392 /* Probably we have no 3 op add. Last chance is to use 2-op
393 add insn. To succeed, don't move Z to X as an address
394 segment always comes in Y. Otherwise, we might fail when
395 adding the address segment to register. */
396 lra_assert (x != y && x != z);
397 emit_move_insn (x, y);
398 rtx_insn *insn = emit_add2_insn (x, z);
399 lra_assert (insn != NULL_RTX);
400 }
401 else
402 {
403 if (index_scale == NULL_RTX)
404 index_scale = index;
405 if (disp == NULL_RTX)
406 {
407 /* Generate x = index_scale; x = x + base. */
408 lra_assert (index_scale != NULL_RTX && base != NULL_RTX);
409 emit_move_insn (x, index_scale);
410 rtx_insn *insn = emit_add2_insn (x, base);
411 lra_assert (insn != NULL_RTX);
412 }
413 else if (scale == NULL_RTX)
414 {
415 /* Try x = base + disp. */
416 lra_assert (base != NULL_RTX);
417 last = get_last_insn ();
418 rtx_insn *move_insn =
419 emit_move_insn (x, gen_rtx_PLUS (GET_MODE (base), base, disp));
420 if (recog_memoized (move_insn) < 0)
421 {
422 delete_insns_since (last);
423 /* Generate x = disp; x = x + base. */
424 emit_move_insn (x, disp);
425 rtx_insn *add2_insn = emit_add2_insn (x, base);
426 lra_assert (add2_insn != NULL_RTX);
427 }
428 /* Generate x = x + index. */
429 if (index != NULL_RTX)
430 {
431 rtx_insn *insn = emit_add2_insn (x, index);
432 lra_assert (insn != NULL_RTX);
433 }
434 }
435 else
436 {
437 /* Try x = index_scale; x = x + disp; x = x + base. */
438 last = get_last_insn ();
439 rtx_insn *move_insn = emit_move_insn (x, index_scale);
440 ok_p = false;
441 if (recog_memoized (move_insn) >= 0)
442 {
443 rtx_insn *insn = emit_add2_insn (x, disp);
444 if (insn != NULL_RTX)
445 {
446 if (base == NULL_RTX)
447 ok_p = true;
448 else
449 {
450 insn = emit_add2_insn (x, base);
451 if (insn != NULL_RTX)
452 ok_p = true;
453 }
454 }
455 }
456 if (! ok_p)
457 {
458 rtx_insn *insn;
459
460 delete_insns_since (last);
461 /* Generate x = disp; x = x + base; x = x + index_scale. */
462 emit_move_insn (x, disp);
463 if (base != NULL_RTX)
464 {
465 insn = emit_add2_insn (x, base);
466 lra_assert (insn != NULL_RTX);
467 }
468 insn = emit_add2_insn (x, index_scale);
469 lra_assert (insn != NULL_RTX);
470 }
471 }
472 }
473 }
474 /* Functions emit_... can create pseudos -- so expand the pseudo
475 data. */
476 if (old != max_reg_num ())
477 expand_reg_data (old);
478}
479
480/* The number of emitted reload insns so far. */
481int lra_curr_reload_num;
482
483/* Emit x := y, processing special case when y = u + v or y = u + v *
484 scale + w through emit_add (Y can be an address which is base +
485 index reg * scale + displacement in general case). X may be used
486 as intermediate result therefore it should be not in Y. */
487void
488lra_emit_move (rtx x, rtx y)
489{
490 int old;
491
492 if (GET_CODE (y) != PLUS)
493 {
494 if (rtx_equal_p (x, y))
495 return;
496 old = max_reg_num ();
497 emit_move_insn (x, y);
498 if (REG_P (x))
499 lra_reg_info[ORIGINAL_REGNO (x)].last_reload = ++lra_curr_reload_num;
500 /* Function emit_move can create pseudos -- so expand the pseudo
501 data. */
502 if (old != max_reg_num ())
503 expand_reg_data (old);
504 return;
505 }
506 lra_emit_add (x, XEXP (y, 0), XEXP (y, 1));
507}
508
509/* Update insn operands which are duplication of operands whose
510 numbers are in array of NOPS (with end marker -1). The insn is
511 represented by its LRA internal representation ID. */
512void
513lra_update_dups (lra_insn_recog_data_t id, signed char *nops)
514{
515 int i, j, nop;
516 struct lra_static_insn_data *static_id = id->insn_static_data;
517
518 for (i = 0; i < static_id->n_dups; i++)
519 for (j = 0; (nop = nops[j]) >= 0; j++)
520 if (static_id->dup_num[i] == nop)
521 *id->dup_loc[i] = *id->operand_loc[nop];
522}
523
524
525
526/* This page contains code dealing with info about registers in the
527 insns. */
528
529/* Pools for insn reg info. */
530object_allocator<lra_insn_reg> lra_insn_reg_pool ("insn regs");
531
532/* Create LRA insn related info about a reference to REGNO in INSN
533 with TYPE (in/out/inout), biggest reference mode MODE, flag that it
534 is reference through subreg (SUBREG_P), flag that is early
535 clobbered in the insn (EARLY_CLOBBER), and reference to the next
536 insn reg info (NEXT). If REGNO can be early clobbered,
537 alternatives in which it can be early clobbered are given by
538 EARLY_CLOBBER_ALTS. */
539static struct lra_insn_reg *
540new_insn_reg (rtx_insn *insn, int regno, enum op_type type,
541 machine_mode mode,
542 bool subreg_p, bool early_clobber,
543 alternative_mask early_clobber_alts,
544 struct lra_insn_reg *next)
545{
546 lra_insn_reg *ir = lra_insn_reg_pool.allocate ();
547 ir->type = type;
548 ir->biggest_mode = mode;
549 if (NONDEBUG_INSN_P (insn)
550 && partial_subreg_p (lra_reg_info[regno].biggest_mode, mode))
551 lra_reg_info[regno].biggest_mode = mode;
552 ir->subreg_p = subreg_p;
553 ir->early_clobber = early_clobber;
554 ir->early_clobber_alts = early_clobber_alts;
555 ir->regno = regno;
556 ir->next = next;
557 return ir;
558}
559
560/* Free insn reg info list IR. */
561static void
562free_insn_regs (struct lra_insn_reg *ir)
563{
564 struct lra_insn_reg *next_ir;
565
566 for (; ir != NULL; ir = next_ir)
567 {
568 next_ir = ir->next;
569 lra_insn_reg_pool.remove (ir);
570 }
571}
572
573/* Finish pool for insn reg info. */
574static void
575finish_insn_regs (void)
576{
577 lra_insn_reg_pool.release ();
578}
579
580
581
582/* This page contains code dealing LRA insn info (or in other words
583 LRA internal insn representation). */
584
585/* Map INSN_CODE -> the static insn data. This info is valid during
586 all translation unit. */
587struct lra_static_insn_data *insn_code_data[NUM_INSN_CODES];
588
589/* Debug insns are represented as a special insn with one input
590 operand which is RTL expression in var_location. */
591
592/* The following data are used as static insn operand data for all
593 debug insns. If structure lra_operand_data is changed, the
594 initializer should be changed too. */
595static struct lra_operand_data debug_operand_data =
596 {
597 NULL, /* alternative */
598 0, /* early_clobber_alts */
599 E_VOIDmode, /* We are not interesting in the operand mode. */
600 OP_IN,
601 0, 0, 0, 0
602 };
603
604/* The following data are used as static insn data for all debug
605 bind insns. If structure lra_static_insn_data is changed, the
606 initializer should be changed too. */
607static struct lra_static_insn_data debug_bind_static_data =
608 {
609 &debug_operand_data,
610 0, /* Duplication operands #. */
611 -1, /* Commutative operand #. */
612 1, /* Operands #. There is only one operand which is debug RTL
613 expression. */
614 0, /* Duplications #. */
615 0, /* Alternatives #. We are not interesting in alternatives
616 because we does not proceed debug_insns for reloads. */
617 NULL, /* Hard registers referenced in machine description. */
618 NULL /* Descriptions of operands in alternatives. */
619 };
620
621/* The following data are used as static insn data for all debug
622 marker insns. If structure lra_static_insn_data is changed, the
623 initializer should be changed too. */
624static struct lra_static_insn_data debug_marker_static_data =
625 {
626 &debug_operand_data,
627 0, /* Duplication operands #. */
628 -1, /* Commutative operand #. */
629 0, /* Operands #. There isn't any operand. */
630 0, /* Duplications #. */
631 0, /* Alternatives #. We are not interesting in alternatives
632 because we does not proceed debug_insns for reloads. */
633 NULL, /* Hard registers referenced in machine description. */
634 NULL /* Descriptions of operands in alternatives. */
635 };
636
637/* Called once per compiler work to initialize some LRA data related
638 to insns. */
639static void
640init_insn_code_data_once (void)
641{
642 memset (insn_code_data, 0, sizeof (insn_code_data));
643}
644
645/* Called once per compiler work to finalize some LRA data related to
646 insns. */
647static void
648finish_insn_code_data_once (void)
649{
650 for (unsigned int i = 0; i < NUM_INSN_CODES; i++)
651 {
652 if (insn_code_data[i] != NULL)
653 free (insn_code_data[i]);
654 }
655}
656
657/* Return static insn data, allocate and setup if necessary. Although
658 dup_num is static data (it depends only on icode), to set it up we
659 need to extract insn first. So recog_data should be valid for
660 normal insn (ICODE >= 0) before the call. */
661static struct lra_static_insn_data *
662get_static_insn_data (int icode, int nop, int ndup, int nalt)
663{
664 struct lra_static_insn_data *data;
665 size_t n_bytes;
666
667 lra_assert (icode < (int) NUM_INSN_CODES);
668 if (icode >= 0 && (data = insn_code_data[icode]) != NULL)
669 return data;
670 lra_assert (nop >= 0 && ndup >= 0 && nalt >= 0);
671 n_bytes = sizeof (struct lra_static_insn_data)
672 + sizeof (struct lra_operand_data) * nop
673 + sizeof (int) * ndup;
674 data = XNEWVAR (struct lra_static_insn_data, n_bytes);
675 data->operand_alternative = NULL;
676 data->n_operands = nop;
677 data->n_dups = ndup;
678 data->n_alternatives = nalt;
679 data->operand = ((struct lra_operand_data *)
680 ((char *) data + sizeof (struct lra_static_insn_data)));
681 data->dup_num = ((int *) ((char *) data->operand
682 + sizeof (struct lra_operand_data) * nop));
683 if (icode >= 0)
684 {
685 int i;
686
687 insn_code_data[icode] = data;
688 for (i = 0; i < nop; i++)
689 {
690 data->operand[i].constraint
691 = insn_data[icode].operand[i].constraint;
692 data->operand[i].mode = insn_data[icode].operand[i].mode;
693 data->operand[i].strict_low = insn_data[icode].operand[i].strict_low;
694 data->operand[i].is_operator
695 = insn_data[icode].operand[i].is_operator;
696 data->operand[i].type
697 = (data->operand[i].constraint[0] == '=' ? OP_OUT
698 : data->operand[i].constraint[0] == '+' ? OP_INOUT
699 : OP_IN);
700 data->operand[i].is_address = false;
701 }
702 for (i = 0; i < ndup; i++)
703 data->dup_num[i] = recog_data.dup_num[i];
704 }
705 return data;
706}
707
708/* The current length of the following array. */
709int lra_insn_recog_data_len;
710
711/* Map INSN_UID -> the insn recog data (NULL if unknown). */
712lra_insn_recog_data_t *lra_insn_recog_data;
713
714/* Initialize LRA data about insns. */
715static void
716init_insn_recog_data (void)
717{
718 lra_insn_recog_data_len = 0;
719 lra_insn_recog_data = NULL;
720}
721
722/* Expand, if necessary, LRA data about insns. */
723static void
724check_and_expand_insn_recog_data (int index)
725{
726 int i, old;
727
728 if (lra_insn_recog_data_len > index)
729 return;
730 old = lra_insn_recog_data_len;
731 lra_insn_recog_data_len = index * 3 / 2 + 1;
732 lra_insn_recog_data = XRESIZEVEC (lra_insn_recog_data_t,
733 lra_insn_recog_data,
734 lra_insn_recog_data_len);
735 for (i = old; i < lra_insn_recog_data_len; i++)
736 lra_insn_recog_data[i] = NULL;
737}
738
739/* Finish LRA DATA about insn. */
740static void
741free_insn_recog_data (lra_insn_recog_data_t data)
742{
743 if (data->operand_loc != NULL)
744 free (data->operand_loc);
745 if (data->dup_loc != NULL)
746 free (data->dup_loc);
747 if (data->arg_hard_regs != NULL)
748 free (data->arg_hard_regs);
749 if (data->icode < 0 && NONDEBUG_INSN_P (data->insn))
750 {
751 if (data->insn_static_data->operand_alternative != NULL)
752 free (const_cast <operand_alternative *>
753 (data->insn_static_data->operand_alternative));
754 free_insn_regs (data->insn_static_data->hard_regs);
755 free (data->insn_static_data);
756 }
757 free_insn_regs (data->regs);
758 data->regs = NULL;
759 free (data);
760}
761
762/* Pools for copies. */
763static object_allocator<lra_copy> lra_copy_pool ("lra copies");
764
765/* Finish LRA data about all insns. */
766static void
767finish_insn_recog_data (void)
768{
769 int i;
770 lra_insn_recog_data_t data;
771
772 for (i = 0; i < lra_insn_recog_data_len; i++)
773 if ((data = lra_insn_recog_data[i]) != NULL)
774 free_insn_recog_data (data);
775 finish_insn_regs ();
776 lra_copy_pool.release ();
777 lra_insn_reg_pool.release ();
778 free (lra_insn_recog_data);
779}
780
781/* Setup info about operands in alternatives of LRA DATA of insn. */
782static void
783setup_operand_alternative (lra_insn_recog_data_t data,
784 const operand_alternative *op_alt)
785{
786 int i, j, nop, nalt;
787 int icode = data->icode;
788 struct lra_static_insn_data *static_data = data->insn_static_data;
789
790 static_data->commutative = -1;
791 nop = static_data->n_operands;
792 nalt = static_data->n_alternatives;
793 static_data->operand_alternative = op_alt;
794 for (i = 0; i < nop; i++)
795 {
796 static_data->operand[i].early_clobber_alts = 0;
797 static_data->operand[i].early_clobber = false;
798 static_data->operand[i].is_address = false;
799 if (static_data->operand[i].constraint[0] == '%')
800 {
801 /* We currently only support one commutative pair of operands. */
802 if (static_data->commutative < 0)
803 static_data->commutative = i;
804 else
805 lra_assert (icode < 0); /* Asm */
806 /* The last operand should not be marked commutative. */
807 lra_assert (i != nop - 1);
808 }
809 }
810 for (j = 0; j < nalt; j++)
811 for (i = 0; i < nop; i++, op_alt++)
812 {
813 static_data->operand[i].early_clobber |= op_alt->earlyclobber;
814 if (op_alt->earlyclobber)
815 static_data->operand[i].early_clobber_alts |= (alternative_mask) 1 << j;
816 static_data->operand[i].is_address |= op_alt->is_address;
817 }
818}
819
820/* Recursively process X and collect info about registers, which are
821 not the insn operands, in X with TYPE (in/out/inout) and flag that
822 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
823 to LIST. X is a part of insn given by DATA. Return the result
824 list. */
825static struct lra_insn_reg *
826collect_non_operand_hard_regs (rtx_insn *insn, rtx *x,
827 lra_insn_recog_data_t data,
828 struct lra_insn_reg *list,
829 enum op_type type, bool early_clobber)
830{
831 int i, j, regno, last;
832 bool subreg_p;
833 machine_mode mode;
834 struct lra_insn_reg *curr;
835 rtx op = *x;
836 enum rtx_code code = GET_CODE (op);
837 const char *fmt = GET_RTX_FORMAT (code);
838
839 for (i = 0; i < data->insn_static_data->n_operands; i++)
840 if (! data->insn_static_data->operand[i].is_operator
841 && x == data->operand_loc[i])
842 /* It is an operand loc. Stop here. */
843 return list;
844 for (i = 0; i < data->insn_static_data->n_dups; i++)
845 if (x == data->dup_loc[i])
846 /* It is a dup loc. Stop here. */
847 return list;
848 mode = GET_MODE (op);
849 subreg_p = false;
850 if (code == SUBREG)
851 {
852 mode = wider_subreg_mode (op);
853 if (read_modify_subreg_p (op))
854 subreg_p = true;
855 op = SUBREG_REG (op);
856 code = GET_CODE (op);
857 }
858 if (REG_P (op))
859 {
860 if ((regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER)
861 return list;
862 /* Process all regs even unallocatable ones as we need info
863 about all regs for rematerialization pass. */
864 for (last = end_hard_regno (mode, regno); regno < last; regno++)
865 {
866 for (curr = list; curr != NULL; curr = curr->next)
867 if (curr->regno == regno && curr->subreg_p == subreg_p
868 && curr->biggest_mode == mode)
869 {
870 if (curr->type != type)
871 curr->type = OP_INOUT;
872 if (early_clobber)
873 {
874 curr->early_clobber = true;
875 curr->early_clobber_alts = ALL_ALTERNATIVES;
876 }
877 break;
878 }
879 if (curr == NULL)
880 {
881 /* This is a new hard regno or the info can not be
882 integrated into the found structure. */
883#ifdef STACK_REGS
884 early_clobber
885 = (early_clobber
886 /* This clobber is to inform popping floating
887 point stack only. */
888 && ! (FIRST_STACK_REG <= regno
889 && regno <= LAST_STACK_REG));
890#endif
891 list = new_insn_reg (data->insn, regno, type, mode, subreg_p,
892 early_clobber,
893 early_clobber ? ALL_ALTERNATIVES : 0, list);
894 }
895 }
896 return list;
897 }
898 switch (code)
899 {
900 case SET:
901 list = collect_non_operand_hard_regs (insn, &SET_DEST (op), data,
902 list, OP_OUT, false);
903 list = collect_non_operand_hard_regs (insn, &SET_SRC (op), data,
904 list, OP_IN, false);
905 break;
906 case CLOBBER:
907 /* We treat clobber of non-operand hard registers as early clobber. */
908 list = collect_non_operand_hard_regs (insn, &XEXP (op, 0), data,
909 list, OP_OUT, true);
910 break;
911 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
912 list = collect_non_operand_hard_regs (insn, &XEXP (op, 0), data,
913 list, OP_INOUT, false);
914 break;
915 case PRE_MODIFY: case POST_MODIFY:
916 list = collect_non_operand_hard_regs (insn, &XEXP (op, 0), data,
917 list, OP_INOUT, false);
918 list = collect_non_operand_hard_regs (insn, &XEXP (op, 1), data,
919 list, OP_IN, false);
920 break;
921 default:
922 fmt = GET_RTX_FORMAT (code);
923 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
924 {
925 if (fmt[i] == 'e')
926 list = collect_non_operand_hard_regs (insn, &XEXP (op, i), data,
927 list, OP_IN, false);
928 else if (fmt[i] == 'E')
929 for (j = XVECLEN (op, i) - 1; j >= 0; j--)
930 list = collect_non_operand_hard_regs (insn, &XVECEXP (op, i, j),
931 data, list, OP_IN, false);
932 }
933 }
934 return list;
935}
936
937/* Set up and return info about INSN. Set up the info if it is not set up
938 yet. */
939lra_insn_recog_data_t
940lra_set_insn_recog_data (rtx_insn *insn)
941{
942 lra_insn_recog_data_t data;
943 int i, n, icode;
944 rtx **locs;
945 unsigned int uid = INSN_UID (insn);
946 struct lra_static_insn_data *insn_static_data;
947
948 check_and_expand_insn_recog_data (uid);
949 if (DEBUG_INSN_P (insn))
950 icode = -1;
951 else
952 {
953 icode = INSN_CODE (insn);
954 if (icode < 0)
955 /* It might be a new simple insn which is not recognized yet. */
956 INSN_CODE (insn) = icode = recog_memoized (insn);
957 }
958 data = XNEW (struct lra_insn_recog_data);
959 lra_insn_recog_data[uid] = data;
960 data->insn = insn;
961 data->used_insn_alternative = -1;
962 data->icode = icode;
963 data->regs = NULL;
964 if (DEBUG_INSN_P (insn))
965 {
966 data->dup_loc = NULL;
967 data->arg_hard_regs = NULL;
968 data->preferred_alternatives = ALL_ALTERNATIVES;
969 if (DEBUG_BIND_INSN_P (insn))
970 {
971 data->insn_static_data = &debug_bind_static_data;
972 data->operand_loc = XNEWVEC (rtx *, 1);
973 data->operand_loc[0] = &INSN_VAR_LOCATION_LOC (insn);
974 }
975 else if (DEBUG_MARKER_INSN_P (insn))
976 {
977 data->insn_static_data = &debug_marker_static_data;
978 data->operand_loc = NULL;
979 }
980 return data;
981 }
982 if (icode < 0)
983 {
984 int nop, nalt;
985 machine_mode operand_mode[MAX_RECOG_OPERANDS];
986 const char *constraints[MAX_RECOG_OPERANDS];
987
988 nop = asm_noperands (PATTERN (insn));
989 data->operand_loc = data->dup_loc = NULL;
990 nalt = 1;
991 if (nop < 0)
992 {
993 /* It is a special insn like USE or CLOBBER. We should
994 recognize any regular insn otherwise LRA can do nothing
995 with this insn. */
996 gcc_assert (GET_CODE (PATTERN (insn)) == USE
997 || GET_CODE (PATTERN (insn)) == CLOBBER
998 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
999 data->insn_static_data = insn_static_data
1000 = get_static_insn_data (-1, 0, 0, nalt);
1001 }
1002 else
1003 {
1004 /* expand_asm_operands makes sure there aren't too many
1005 operands. */
1006 lra_assert (nop <= MAX_RECOG_OPERANDS);
1007 if (nop != 0)
1008 data->operand_loc = XNEWVEC (rtx *, nop);
1009 /* Now get the operand values and constraints out of the
1010 insn. */
1011 decode_asm_operands (PATTERN (insn), NULL,
1012 data->operand_loc,
1013 constraints, operand_mode, NULL);
1014 if (nop > 0)
1015 {
1016 const char *p = recog_data.constraints[0];
1017
1018 for (p = constraints[0]; *p; p++)
1019 nalt += *p == ',';
1020 }
1021 data->insn_static_data = insn_static_data
1022 = get_static_insn_data (-1, nop, 0, nalt);
1023 for (i = 0; i < nop; i++)
1024 {
1025 insn_static_data->operand[i].mode = operand_mode[i];
1026 insn_static_data->operand[i].constraint = constraints[i];
1027 insn_static_data->operand[i].strict_low = false;
1028 insn_static_data->operand[i].is_operator = false;
1029 insn_static_data->operand[i].is_address = false;
1030 }
1031 }
1032 for (i = 0; i < insn_static_data->n_operands; i++)
1033 insn_static_data->operand[i].type
1034 = (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1035 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1036 : OP_IN);
1037 data->preferred_alternatives = ALL_ALTERNATIVES;
1038 if (nop > 0)
1039 {
1040 operand_alternative *op_alt = XCNEWVEC (operand_alternative,
1041 nalt * nop);
1042 preprocess_constraints (nop, nalt, constraints, op_alt);
1043 setup_operand_alternative (data, op_alt);
1044 }
1045 }
1046 else
1047 {
1048 insn_extract (insn);
1049 data->insn_static_data = insn_static_data
1050 = get_static_insn_data (icode, insn_data[icode].n_operands,
1051 insn_data[icode].n_dups,
1052 insn_data[icode].n_alternatives);
1053 n = insn_static_data->n_operands;
1054 if (n == 0)
1055 locs = NULL;
1056 else
1057 {
1058 locs = XNEWVEC (rtx *, n);
1059 memcpy (locs, recog_data.operand_loc, n * sizeof (rtx *));
1060 }
1061 data->operand_loc = locs;
1062 n = insn_static_data->n_dups;
1063 if (n == 0)
1064 locs = NULL;
1065 else
1066 {
1067 locs = XNEWVEC (rtx *, n);
1068 memcpy (locs, recog_data.dup_loc, n * sizeof (rtx *));
1069 }
1070 data->dup_loc = locs;
1071 data->preferred_alternatives = get_preferred_alternatives (insn);
1072 const operand_alternative *op_alt = preprocess_insn_constraints (icode);
1073 if (!insn_static_data->operand_alternative)
1074 setup_operand_alternative (data, op_alt);
1075 else if (op_alt != insn_static_data->operand_alternative)
1076 insn_static_data->operand_alternative = op_alt;
1077 }
1078 if (GET_CODE (PATTERN (insn)) == CLOBBER || GET_CODE (PATTERN (insn)) == USE)
1079 insn_static_data->hard_regs = NULL;
1080 else
1081 insn_static_data->hard_regs
1082 = collect_non_operand_hard_regs (insn, &PATTERN (insn), data,
1083 NULL, OP_IN, false);
1084 data->arg_hard_regs = NULL;
1085 if (CALL_P (insn))
1086 {
1087 bool use_p;
1088 rtx link;
1089 int n_hard_regs, regno, arg_hard_regs[FIRST_PSEUDO_REGISTER];
1090
1091 n_hard_regs = 0;
1092 /* Finding implicit hard register usage. We believe it will be
1093 not changed whatever transformations are used. Call insns
1094 are such example. */
1095 for (link = CALL_INSN_FUNCTION_USAGE (insn);
1096 link != NULL_RTX;
1097 link = XEXP (link, 1))
1098 if (((use_p = GET_CODE (XEXP (link, 0)) == USE)
1099 || GET_CODE (XEXP (link, 0)) == CLOBBER)
1100 && REG_P (XEXP (XEXP (link, 0), 0)))
1101 {
1102 regno = REGNO (XEXP (XEXP (link, 0), 0));
1103 lra_assert (regno < FIRST_PSEUDO_REGISTER);
1104 /* It is an argument register. */
1105 for (i = REG_NREGS (XEXP (XEXP (link, 0), 0)) - 1; i >= 0; i--)
1106 arg_hard_regs[n_hard_regs++]
1107 = regno + i + (use_p ? 0 : FIRST_PSEUDO_REGISTER);
1108 }
1109 if (n_hard_regs != 0)
1110 {
1111 arg_hard_regs[n_hard_regs++] = -1;
1112 data->arg_hard_regs = XNEWVEC (int, n_hard_regs);
1113 memcpy (data->arg_hard_regs, arg_hard_regs,
1114 sizeof (int) * n_hard_regs);
1115 }
1116 }
1117 /* Some output operand can be recognized only from the context not
1118 from the constraints which are empty in this case. Call insn may
1119 contain a hard register in set destination with empty constraint
1120 and extract_insn treats them as an input. */
1121 for (i = 0; i < insn_static_data->n_operands; i++)
1122 {
1123 int j;
1124 rtx pat, set;
1125 struct lra_operand_data *operand = &insn_static_data->operand[i];
1126
1127 /* ??? Should we treat 'X' the same way. It looks to me that
1128 'X' means anything and empty constraint means we do not
1129 care. */
1130 if (operand->type != OP_IN || *operand->constraint != '\0'
1131 || operand->is_operator)
1132 continue;
1133 pat = PATTERN (insn);
1134 if (GET_CODE (pat) == SET)
1135 {
1136 if (data->operand_loc[i] != &SET_DEST (pat))
1137 continue;
1138 }
1139 else if (GET_CODE (pat) == PARALLEL)
1140 {
1141 for (j = XVECLEN (pat, 0) - 1; j >= 0; j--)
1142 {
1143 set = XVECEXP (PATTERN (insn), 0, j);
1144 if (GET_CODE (set) == SET
1145 && &SET_DEST (set) == data->operand_loc[i])
1146 break;
1147 }
1148 if (j < 0)
1149 continue;
1150 }
1151 else
1152 continue;
1153 operand->type = OP_OUT;
1154 }
1155 return data;
1156}
1157
1158/* Return info about insn give by UID. The info should be already set
1159 up. */
1160static lra_insn_recog_data_t
1161get_insn_recog_data_by_uid (int uid)
1162{
1163 lra_insn_recog_data_t data;
1164
1165 data = lra_insn_recog_data[uid];
1166 lra_assert (data != NULL);
1167 return data;
1168}
1169
1170/* Invalidate all info about insn given by its UID. */
1171static void
1172invalidate_insn_recog_data (int uid)
1173{
1174 lra_insn_recog_data_t data;
1175
1176 data = lra_insn_recog_data[uid];
1177 lra_assert (data != NULL);
1178 free_insn_recog_data (data);
1179 lra_insn_recog_data[uid] = NULL;
1180}
1181
1182/* Update all the insn info about INSN. It is usually called when
1183 something in the insn was changed. Return the updated info. */
1184lra_insn_recog_data_t
1185lra_update_insn_recog_data (rtx_insn *insn)
1186{
1187 lra_insn_recog_data_t data;
1188 int n;
1189 unsigned int uid = INSN_UID (insn);
1190 struct lra_static_insn_data *insn_static_data;
1191 HOST_WIDE_INT sp_offset = 0;
1192
1193 check_and_expand_insn_recog_data (uid);
1194 if ((data = lra_insn_recog_data[uid]) != NULL
1195 && data->icode != INSN_CODE (insn))
1196 {
1197 sp_offset = data->sp_offset;
1198 invalidate_insn_data_regno_info (data, insn, get_insn_freq (insn));
1199 invalidate_insn_recog_data (uid);
1200 data = NULL;
1201 }
1202 if (data == NULL)
1203 {
1204 data = lra_get_insn_recog_data (insn);
1205 /* Initiate or restore SP offset. */
1206 data->sp_offset = sp_offset;
1207 return data;
1208 }
1209 insn_static_data = data->insn_static_data;
1210 data->used_insn_alternative = -1;
1211 if (DEBUG_INSN_P (insn))
1212 return data;
1213 if (data->icode < 0)
1214 {
1215 int nop;
1216 machine_mode operand_mode[MAX_RECOG_OPERANDS];
1217 const char *constraints[MAX_RECOG_OPERANDS];
1218
1219 nop = asm_noperands (PATTERN (insn));
1220 if (nop >= 0)
1221 {
1222 lra_assert (nop == data->insn_static_data->n_operands);
1223 /* Now get the operand values and constraints out of the
1224 insn. */
1225 decode_asm_operands (PATTERN (insn), NULL,
1226 data->operand_loc,
1227 constraints, operand_mode, NULL);
1228
1229 if (flag_checking)
1230 for (int i = 0; i < nop; i++)
1231 lra_assert
1232 (insn_static_data->operand[i].mode == operand_mode[i]
1233 && insn_static_data->operand[i].constraint == constraints[i]
1234 && ! insn_static_data->operand[i].is_operator);
1235 }
1236
1237 if (flag_checking)
1238 for (int i = 0; i < insn_static_data->n_operands; i++)
1239 lra_assert
1240 (insn_static_data->operand[i].type
1241 == (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1242 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1243 : OP_IN));
1244 }
1245 else
1246 {
1247 insn_extract (insn);
1248 n = insn_static_data->n_operands;
1249 if (n != 0)
1250 memcpy (data->operand_loc, recog_data.operand_loc, n * sizeof (rtx *));
1251 n = insn_static_data->n_dups;
1252 if (n != 0)
1253 memcpy (data->dup_loc, recog_data.dup_loc, n * sizeof (rtx *));
1254 lra_assert (check_bool_attrs (insn));
1255 }
1256 return data;
1257}
1258
1259/* Set up that INSN is using alternative ALT now. */
1260void
1261lra_set_used_insn_alternative (rtx_insn *insn, int alt)
1262{
1263 lra_insn_recog_data_t data;
1264
1265 data = lra_get_insn_recog_data (insn);
1266 data->used_insn_alternative = alt;
1267}
1268
1269/* Set up that insn with UID is using alternative ALT now. The insn
1270 info should be already set up. */
1271void
1272lra_set_used_insn_alternative_by_uid (int uid, int alt)
1273{
1274 lra_insn_recog_data_t data;
1275
1276 check_and_expand_insn_recog_data (uid);
1277 data = lra_insn_recog_data[uid];
1278 lra_assert (data != NULL);
1279 data->used_insn_alternative = alt;
1280}
1281
1282
1283
1284/* This page contains code dealing with common register info and
1285 pseudo copies. */
1286
1287/* The size of the following array. */
1288static int reg_info_size;
1289/* Common info about each register. */
1290struct lra_reg *lra_reg_info;
1291
1292/* Last register value. */
1293static int last_reg_value;
1294
1295/* Return new register value. */
1296static int
1297get_new_reg_value (void)
1298{
1299 return ++last_reg_value;
1300}
1301
1302/* Vec referring to pseudo copies. */
1303static vec<lra_copy_t> copy_vec;
1304
1305/* Initialize I-th element of lra_reg_info. */
1306static inline void
1307initialize_lra_reg_info_element (int i)
1308{
1309 bitmap_initialize (&lra_reg_info[i].insn_bitmap, &reg_obstack);
1310#ifdef STACK_REGS
1311 lra_reg_info[i].no_stack_p = false;
1312#endif
1313 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1314 CLEAR_HARD_REG_SET (lra_reg_info[i].actual_call_used_reg_set);
1315 lra_reg_info[i].preferred_hard_regno1 = -1;
1316 lra_reg_info[i].preferred_hard_regno2 = -1;
1317 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1318 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1319 lra_reg_info[i].biggest_mode = VOIDmode;
1320 lra_reg_info[i].live_ranges = NULL;
1321 lra_reg_info[i].nrefs = lra_reg_info[i].freq = 0;
1322 lra_reg_info[i].last_reload = 0;
1323 lra_reg_info[i].restore_rtx = NULL_RTX;
1324 lra_reg_info[i].val = get_new_reg_value ();
1325 lra_reg_info[i].offset = 0;
1326 lra_reg_info[i].copies = NULL;
1327}
1328
1329/* Initialize common reg info and copies. */
1330static void
1331init_reg_info (void)
1332{
1333 int i;
1334
1335 last_reg_value = 0;
1336 reg_info_size = max_reg_num () * 3 / 2 + 1;
1337 lra_reg_info = XNEWVEC (struct lra_reg, reg_info_size);
1338 for (i = 0; i < reg_info_size; i++)
1339 initialize_lra_reg_info_element (i);
1340 copy_vec.truncate (0);
1341}
1342
1343
1344/* Finish common reg info and copies. */
1345static void
1346finish_reg_info (void)
1347{
1348 int i;
1349
1350 for (i = 0; i < reg_info_size; i++)
1351 bitmap_clear (&lra_reg_info[i].insn_bitmap);
1352 free (lra_reg_info);
1353 reg_info_size = 0;
1354}
1355
1356/* Expand common reg info if it is necessary. */
1357static void
1358expand_reg_info (void)
1359{
1360 int i, old = reg_info_size;
1361
1362 if (reg_info_size > max_reg_num ())
1363 return;
1364 reg_info_size = max_reg_num () * 3 / 2 + 1;
1365 lra_reg_info = XRESIZEVEC (struct lra_reg, lra_reg_info, reg_info_size);
1366 for (i = old; i < reg_info_size; i++)
1367 initialize_lra_reg_info_element (i);
1368}
1369
1370/* Free all copies. */
1371void
1372lra_free_copies (void)
1373{
1374 lra_copy_t cp;
1375
1376 while (copy_vec.length () != 0)
1377 {
1378 cp = copy_vec.pop ();
1379 lra_reg_info[cp->regno1].copies = lra_reg_info[cp->regno2].copies = NULL;
1380 lra_copy_pool.remove (cp);
1381 }
1382}
1383
1384/* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1385 frequency is FREQ. */
1386void
1387lra_create_copy (int regno1, int regno2, int freq)
1388{
1389 bool regno1_dest_p;
1390 lra_copy_t cp;
1391
1392 lra_assert (regno1 != regno2);
1393 regno1_dest_p = true;
1394 if (regno1 > regno2)
1395 {
1396 std::swap (regno1, regno2);
1397 regno1_dest_p = false;
1398 }
1399 cp = lra_copy_pool.allocate ();
1400 copy_vec.safe_push (cp);
1401 cp->regno1_dest_p = regno1_dest_p;
1402 cp->freq = freq;
1403 cp->regno1 = regno1;
1404 cp->regno2 = regno2;
1405 cp->regno1_next = lra_reg_info[regno1].copies;
1406 lra_reg_info[regno1].copies = cp;
1407 cp->regno2_next = lra_reg_info[regno2].copies;
1408 lra_reg_info[regno2].copies = cp;
1409 if (lra_dump_file != NULL)
1410 fprintf (lra_dump_file, " Creating copy r%d%sr%d@%d\n",
1411 regno1, regno1_dest_p ? "<-" : "->", regno2, freq);
1412}
1413
1414/* Return N-th (0, 1, ...) copy. If there is no copy, return
1415 NULL. */
1416lra_copy_t
1417lra_get_copy (int n)
1418{
1419 if (n >= (int) copy_vec.length ())
1420 return NULL;
1421 return copy_vec[n];
1422}
1423
1424
1425
1426/* This page contains code dealing with info about registers in
1427 insns. */
1428
1429/* Process X of INSN recursively and add info (operand type is
1430 given by TYPE, flag of that it is early clobber is EARLY_CLOBBER)
1431 about registers in X to the insn DATA. If X can be early clobbered,
1432 alternatives in which it can be early clobbered are given by
1433 EARLY_CLOBBER_ALTS. */
1434static void
1435add_regs_to_insn_regno_info (lra_insn_recog_data_t data, rtx x,
1436 rtx_insn *insn,
1437 enum op_type type, bool early_clobber,
1438 alternative_mask early_clobber_alts)
1439{
1440 int i, j, regno;
1441 bool subreg_p;
1442 machine_mode mode;
1443 const char *fmt;
1444 enum rtx_code code;
1445 struct lra_insn_reg *curr;
1446
1447 code = GET_CODE (x);
1448 mode = GET_MODE (x);
1449 subreg_p = false;
1450 if (GET_CODE (x) == SUBREG)
1451 {
1452 mode = wider_subreg_mode (x);
1453 if (read_modify_subreg_p (x))
1454 subreg_p = true;
1455 x = SUBREG_REG (x);
1456 code = GET_CODE (x);
1457 }
1458 if (REG_P (x))
1459 {
1460 regno = REGNO (x);
1461 /* Process all regs even unallocatable ones as we need info about
1462 all regs for rematerialization pass. */
1463 expand_reg_info ();
1464 if (bitmap_set_bit (&lra_reg_info[regno].insn_bitmap, INSN_UID (insn)))
1465 {
1466 data->regs = new_insn_reg (data->insn, regno, type, mode, subreg_p,
1467 early_clobber, early_clobber_alts,
1468 data->regs);
1469 return;
1470 }
1471 else
1472 {
1473 for (curr = data->regs; curr != NULL; curr = curr->next)
1474 if (curr->regno == regno)
1475 {
1476 if (curr->subreg_p != subreg_p || curr->biggest_mode != mode)
1477 /* The info can not be integrated into the found
1478 structure. */
1479 data->regs = new_insn_reg (data->insn, regno, type, mode,
1480 subreg_p, early_clobber,
1481 early_clobber_alts, data->regs);
1482 else
1483 {
1484 if (curr->type != type)
1485 curr->type = OP_INOUT;
1486 if (curr->early_clobber != early_clobber)
1487 curr->early_clobber = true;
1488 curr->early_clobber_alts |= early_clobber_alts;
1489 }
1490 return;
1491 }
1492 gcc_unreachable ();
1493 }
1494 }
1495
1496 switch (code)
1497 {
1498 case SET:
1499 add_regs_to_insn_regno_info (data, SET_DEST (x), insn, OP_OUT, false, 0);
1500 add_regs_to_insn_regno_info (data, SET_SRC (x), insn, OP_IN, false, 0);
1501 break;
1502 case CLOBBER:
1503 /* We treat clobber of non-operand hard registers as early
1504 clobber. */
1505 add_regs_to_insn_regno_info (data, XEXP (x, 0), insn, OP_OUT,
1506 true, ALL_ALTERNATIVES);
1507 break;
1508 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
1509 add_regs_to_insn_regno_info (data, XEXP (x, 0), insn, OP_INOUT, false, 0);
1510 break;
1511 case PRE_MODIFY: case POST_MODIFY:
1512 add_regs_to_insn_regno_info (data, XEXP (x, 0), insn, OP_INOUT, false, 0);
1513 add_regs_to_insn_regno_info (data, XEXP (x, 1), insn, OP_IN, false, 0);
1514 break;
1515 default:
1516 if ((code != PARALLEL && code != EXPR_LIST) || type != OP_OUT)
1517 /* Some targets place small structures in registers for return
1518 values of functions, and those registers are wrapped in
1519 PARALLEL that we may see as the destination of a SET. Here
1520 is an example:
1521
1522 (call_insn 13 12 14 2 (set (parallel:BLK [
1523 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1524 (const_int 0 [0]))
1525 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1526 (const_int 8 [0x8]))
1527 ])
1528 (call (mem:QI (symbol_ref:DI (... */
1529 type = OP_IN;
1530 fmt = GET_RTX_FORMAT (code);
1531 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1532 {
1533 if (fmt[i] == 'e')
1534 add_regs_to_insn_regno_info (data, XEXP (x, i), insn, type, false, 0);
1535 else if (fmt[i] == 'E')
1536 {
1537 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1538 add_regs_to_insn_regno_info (data, XVECEXP (x, i, j), insn,
1539 type, false, 0);
1540 }
1541 }
1542 }
1543}
1544
1545/* Return execution frequency of INSN. */
1546static int
1547get_insn_freq (rtx_insn *insn)
1548{
1549 basic_block bb = BLOCK_FOR_INSN (insn);
1550
1551 gcc_checking_assert (bb != NULL);
1552 return REG_FREQ_FROM_BB (bb);
1553}
1554
1555/* Invalidate all reg info of INSN with DATA and execution frequency
1556 FREQ. Update common info about the invalidated registers. */
1557static void
1558invalidate_insn_data_regno_info (lra_insn_recog_data_t data, rtx_insn *insn,
1559 int freq)
1560{
1561 int uid;
1562 bool debug_p;
1563 unsigned int i;
1564 struct lra_insn_reg *ir, *next_ir;
1565
1566 uid = INSN_UID (insn);
1567 debug_p = DEBUG_INSN_P (insn);
1568 for (ir = data->regs; ir != NULL; ir = next_ir)
1569 {
1570 i = ir->regno;
1571 next_ir = ir->next;
1572 lra_insn_reg_pool.remove (ir);
1573 bitmap_clear_bit (&lra_reg_info[i].insn_bitmap, uid);
1574 if (i >= FIRST_PSEUDO_REGISTER && ! debug_p)
1575 {
1576 lra_reg_info[i].nrefs--;
1577 lra_reg_info[i].freq -= freq;
1578 lra_assert (lra_reg_info[i].nrefs >= 0 && lra_reg_info[i].freq >= 0);
1579 }
1580 }
1581 data->regs = NULL;
1582}
1583
1584/* Invalidate all reg info of INSN. Update common info about the
1585 invalidated registers. */
1586void
1587lra_invalidate_insn_regno_info (rtx_insn *insn)
1588{
1589 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn), insn,
1590 get_insn_freq (insn));
1591}
1592
1593/* Update common reg info from reg info of insn given by its DATA and
1594 execution frequency FREQ. */
1595static void
1596setup_insn_reg_info (lra_insn_recog_data_t data, int freq)
1597{
1598 unsigned int i;
1599 struct lra_insn_reg *ir;
1600
1601 for (ir = data->regs; ir != NULL; ir = ir->next)
1602 if ((i = ir->regno) >= FIRST_PSEUDO_REGISTER)
1603 {
1604 lra_reg_info[i].nrefs++;
1605 lra_reg_info[i].freq += freq;
1606 }
1607}
1608
1609/* Set up insn reg info of INSN. Update common reg info from reg info
1610 of INSN. */
1611void
1612lra_update_insn_regno_info (rtx_insn *insn)
1613{
1614 int i, freq;
1615 lra_insn_recog_data_t data;
1616 struct lra_static_insn_data *static_data;
1617 enum rtx_code code;
1618 rtx link;
1619
1620 if (! INSN_P (insn))
1621 return;
1622 data = lra_get_insn_recog_data (insn);
1623 static_data = data->insn_static_data;
1624 freq = NONDEBUG_INSN_P (insn) ? get_insn_freq (insn) : 0;
1625 invalidate_insn_data_regno_info (data, insn, freq);
1626 for (i = static_data->n_operands - 1; i >= 0; i--)
1627 add_regs_to_insn_regno_info (data, *data->operand_loc[i], insn,
1628 static_data->operand[i].type,
1629 static_data->operand[i].early_clobber,
1630 static_data->operand[i].early_clobber_alts);
1631 if ((code = GET_CODE (PATTERN (insn))) == CLOBBER || code == USE)
1632 add_regs_to_insn_regno_info (data, XEXP (PATTERN (insn), 0), insn,
1633 code == USE ? OP_IN : OP_OUT, false, 0);
1634 if (CALL_P (insn))
1635 /* On some targets call insns can refer to pseudos in memory in
1636 CALL_INSN_FUNCTION_USAGE list. Process them in order to
1637 consider their occurrences in calls for different
1638 transformations (e.g. inheritance) with given pseudos. */
1639 for (link = CALL_INSN_FUNCTION_USAGE (insn);
1640 link != NULL_RTX;
1641 link = XEXP (link, 1))
1642 if (((code = GET_CODE (XEXP (link, 0))) == USE || code == CLOBBER)
1643 && MEM_P (XEXP (XEXP (link, 0), 0)))
1644 add_regs_to_insn_regno_info (data, XEXP (XEXP (link, 0), 0), insn,
1645 code == USE ? OP_IN : OP_OUT, false, 0);
1646 if (NONDEBUG_INSN_P (insn))
1647 setup_insn_reg_info (data, freq);
1648}
1649
1650/* Return reg info of insn given by it UID. */
1651struct lra_insn_reg *
1652lra_get_insn_regs (int uid)
1653{
1654 lra_insn_recog_data_t data;
1655
1656 data = get_insn_recog_data_by_uid (uid);
1657 return data->regs;
1658}
1659
1660
1661
1662/* Recursive hash function for RTL X. */
1663hashval_t
1664lra_rtx_hash (rtx x)
1665{
1666 int i, j;
1667 enum rtx_code code;
1668 const char *fmt;
1669 hashval_t val = 0;
1670
1671 if (x == 0)
1672 return val;
1673
1674 code = GET_CODE (x);
1675 val += (int) code + 4095;
1676
1677 /* Some RTL can be compared nonrecursively. */
1678 switch (code)
1679 {
1680 case REG:
1681 return val + REGNO (x);
1682
1683 case LABEL_REF:
1684 return iterative_hash_object (XEXP (x, 0), val);
1685
1686 case SYMBOL_REF:
1687 return iterative_hash_object (XSTR (x, 0), val);
1688
1689 case SCRATCH:
1690 case CONST_DOUBLE:
1691 case CONST_INT:
1692 case CONST_VECTOR:
1693 return val;
1694
1695 default:
1696 break;
1697 }
1698
1699 /* Hash the elements. */
1700 fmt = GET_RTX_FORMAT (code);
1701 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1702 {
1703 switch (fmt[i])
1704 {
1705 case 'w':
1706 val += XWINT (x, i);
1707 break;
1708
1709 case 'n':
1710 case 'i':
1711 val += XINT (x, i);
1712 break;
1713
1714 case 'V':
1715 case 'E':
1716 val += XVECLEN (x, i);
1717
1718 for (j = 0; j < XVECLEN (x, i); j++)
1719 val += lra_rtx_hash (XVECEXP (x, i, j));
1720 break;
1721
1722 case 'e':
1723 val += lra_rtx_hash (XEXP (x, i));
1724 break;
1725
1726 case 'S':
1727 case 's':
1728 val += htab_hash_string (XSTR (x, i));
1729 break;
1730
1731 case 'u':
1732 case '0':
1733 case 't':
1734 break;
1735
1736 /* It is believed that rtx's at this level will never
1737 contain anything but integers and other rtx's, except for
1738 within LABEL_REFs and SYMBOL_REFs. */
1739 default:
1740 abort ();
1741 }
1742 }
1743 return val;
1744}
1745
1746
1747
1748/* This page contains code dealing with stack of the insns which
1749 should be processed by the next constraint pass. */
1750
1751/* Bitmap used to put an insn on the stack only in one exemplar. */
1752static sbitmap lra_constraint_insn_stack_bitmap;
1753
1754/* The stack itself. */
1755vec<rtx_insn *> lra_constraint_insn_stack;
1756
1757/* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1758 info for INSN, otherwise only update it if INSN is not already on the
1759 stack. */
1760static inline void
1761lra_push_insn_1 (rtx_insn *insn, bool always_update)
1762{
1763 unsigned int uid = INSN_UID (insn);
1764 if (always_update)
1765 lra_update_insn_regno_info (insn);
1766 if (uid >= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap))
1767 lra_constraint_insn_stack_bitmap =
1768 sbitmap_resize (lra_constraint_insn_stack_bitmap, 3 * uid / 2, 0);
1769 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap, uid))
1770 return;
1771 bitmap_set_bit (lra_constraint_insn_stack_bitmap, uid);
1772 if (! always_update)
1773 lra_update_insn_regno_info (insn);
1774 lra_constraint_insn_stack.safe_push (insn);
1775}
1776
1777/* Put INSN on the stack. */
1778void
1779lra_push_insn (rtx_insn *insn)
1780{
1781 lra_push_insn_1 (insn, false);
1782}
1783
1784/* Put INSN on the stack and update its reg info. */
1785void
1786lra_push_insn_and_update_insn_regno_info (rtx_insn *insn)
1787{
1788 lra_push_insn_1 (insn, true);
1789}
1790
1791/* Put insn with UID on the stack. */
1792void
1793lra_push_insn_by_uid (unsigned int uid)
1794{
1795 lra_push_insn (lra_insn_recog_data[uid]->insn);
1796}
1797
1798/* Take the last-inserted insns off the stack and return it. */
1799rtx_insn *
1800lra_pop_insn (void)
1801{
1802 rtx_insn *insn = lra_constraint_insn_stack.pop ();
1803 bitmap_clear_bit (lra_constraint_insn_stack_bitmap, INSN_UID (insn));
1804 return insn;
1805}
1806
1807/* Return the current size of the insn stack. */
1808unsigned int
1809lra_insn_stack_length (void)
1810{
1811 return lra_constraint_insn_stack.length ();
1812}
1813
1814/* Push insns FROM to TO (excluding it) going in reverse order. */
1815static void
1816push_insns (rtx_insn *from, rtx_insn *to)
1817{
1818 rtx_insn *insn;
1819
1820 if (from == NULL_RTX)
1821 return;
1822 for (insn = from; insn != to; insn = PREV_INSN (insn))
1823 if (INSN_P (insn))
1824 lra_push_insn (insn);
1825}
1826
1827/* Set up sp offset for insn in range [FROM, LAST]. The offset is
1828 taken from the next BB insn after LAST or zero if there in such
1829 insn. */
1830static void
1831setup_sp_offset (rtx_insn *from, rtx_insn *last)
1832{
1833 rtx_insn *before = next_nonnote_nondebug_insn_bb (last);
1834 HOST_WIDE_INT offset = (before == NULL_RTX || ! INSN_P (before)
1835 ? 0 : lra_get_insn_recog_data (before)->sp_offset);
1836
1837 for (rtx_insn *insn = from; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
1838 lra_get_insn_recog_data (insn)->sp_offset = offset;
1839}
1840
1841/* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1842 insns onto the stack. Print about emitting the insns with
1843 TITLE. */
1844void
1845lra_process_new_insns (rtx_insn *insn, rtx_insn *before, rtx_insn *after,
1846 const char *title)
1847{
1848 rtx_insn *last;
1849
1850 if (before == NULL_RTX && after == NULL_RTX)
1851 return;
1852 if (lra_dump_file != NULL)
1853 {
1854 dump_insn_slim (lra_dump_file, insn);
1855 if (before != NULL_RTX)
1856 {
1857 fprintf (lra_dump_file," %s before:\n", title);
1858 dump_rtl_slim (lra_dump_file, before, NULL, -1, 0);
1859 }
1860 if (after != NULL_RTX)
1861 {
1862 fprintf (lra_dump_file, " %s after:\n", title);
1863 dump_rtl_slim (lra_dump_file, after, NULL, -1, 0);
1864 }
1865 fprintf (lra_dump_file, "\n");
1866 }
1867 if (before != NULL_RTX)
1868 {
1869 if (cfun->can_throw_non_call_exceptions)
1870 copy_reg_eh_region_note_forward (insn, before, NULL);
1871 emit_insn_before (before, insn);
1872 push_insns (PREV_INSN (insn), PREV_INSN (before));
1873 setup_sp_offset (before, PREV_INSN (insn));
1874 }
1875 if (after != NULL_RTX)
1876 {
1877 if (cfun->can_throw_non_call_exceptions)
1878 copy_reg_eh_region_note_forward (insn, after, NULL);
1879 for (last = after; NEXT_INSN (last) != NULL_RTX; last = NEXT_INSN (last))
1880 ;
1881 emit_insn_after (after, insn);
1882 push_insns (last, insn);
1883 setup_sp_offset (after, last);
1884 }
1885 if (cfun->can_throw_non_call_exceptions)
1886 {
1887 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1888 if (note && !insn_could_throw_p (insn))
1889 remove_note (insn, note);
1890 }
1891}
1892
1893
1894/* Replace all references to register OLD_REGNO in *LOC with pseudo
1895 register NEW_REG. Try to simplify subreg of constant if SUBREG_P.
1896 Return true if any change was made. */
1897bool
1898lra_substitute_pseudo (rtx *loc, int old_regno, rtx new_reg, bool subreg_p)
1899{
1900 rtx x = *loc;
1901 bool result = false;
1902 enum rtx_code code;
1903 const char *fmt;
1904 int i, j;
1905
1906 if (x == NULL_RTX)
1907 return false;
1908
1909 code = GET_CODE (x);
1910 if (code == SUBREG && subreg_p)
1911 {
1912 rtx subst, inner = SUBREG_REG (x);
1913 /* Transform subreg of constant while we still have inner mode
1914 of the subreg. The subreg internal should not be an insn
1915 operand. */
1916 if (REG_P (inner) && (int) REGNO (inner) == old_regno
1917 && CONSTANT_P (new_reg)
1918 && (subst = simplify_subreg (GET_MODE (x), new_reg, GET_MODE (inner),
1919 SUBREG_BYTE (x))) != NULL_RTX)
1920 {
1921 *loc = subst;
1922 return true;
1923 }
1924
1925 }
1926 else if (code == REG && (int) REGNO (x) == old_regno)
1927 {
1928 machine_mode mode = GET_MODE (x);
1929 machine_mode inner_mode = GET_MODE (new_reg);
1930
1931 if (mode != inner_mode
1932 && ! (CONST_INT_P (new_reg) && SCALAR_INT_MODE_P (mode)))
1933 {
1934 if (!partial_subreg_p (mode, inner_mode)
1935 || ! SCALAR_INT_MODE_P (inner_mode))
1936 new_reg = gen_rtx_SUBREG (mode, new_reg, 0);
1937 else
1938 new_reg = gen_lowpart_SUBREG (mode, new_reg);
1939 }
1940 *loc = new_reg;
1941 return true;
1942 }
1943
1944 /* Scan all the operand sub-expressions. */
1945 fmt = GET_RTX_FORMAT (code);
1946 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1947 {
1948 if (fmt[i] == 'e')
1949 {
1950 if (lra_substitute_pseudo (&XEXP (x, i), old_regno,
1951 new_reg, subreg_p))
1952 result = true;
1953 }
1954 else if (fmt[i] == 'E')
1955 {
1956 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1957 if (lra_substitute_pseudo (&XVECEXP (x, i, j), old_regno,
1958 new_reg, subreg_p))
1959 result = true;
1960 }
1961 }
1962 return result;
1963}
1964
1965/* Call lra_substitute_pseudo within an insn. Try to simplify subreg
1966 of constant if SUBREG_P. This won't update the insn ptr, just the
1967 contents of the insn. */
1968bool
1969lra_substitute_pseudo_within_insn (rtx_insn *insn, int old_regno,
1970 rtx new_reg, bool subreg_p)
1971{
1972 rtx loc = insn;
1973 return lra_substitute_pseudo (&loc, old_regno, new_reg, subreg_p);
1974}
1975
1976
1977
1978/* This page contains code dealing with scratches (changing them onto
1979 pseudos and restoring them from the pseudos).
1980
1981 We change scratches into pseudos at the beginning of LRA to
1982 simplify dealing with them (conflicts, hard register assignments).
1983
1984 If the pseudo denoting scratch was spilled it means that we do need
1985 a hard register for it. Such pseudos are transformed back to
1986 scratches at the end of LRA. */
1987
1988/* Description of location of a former scratch operand. */
1989struct sloc
1990{
1991 rtx_insn *insn; /* Insn where the scratch was. */
1992 int nop; /* Number of the operand which was a scratch. */
1993};
1994
1995typedef struct sloc *sloc_t;
1996
1997/* Locations of the former scratches. */
1998static vec<sloc_t> scratches;
1999
2000/* Bitmap of scratch regnos. */
2001static bitmap_head scratch_bitmap;
2002
2003/* Bitmap of scratch operands. */
2004static bitmap_head scratch_operand_bitmap;
2005
2006/* Return true if pseudo REGNO is made of SCRATCH. */
2007bool
2008lra_former_scratch_p (int regno)
2009{
2010 return bitmap_bit_p (&scratch_bitmap, regno);
2011}
2012
2013/* Return true if the operand NOP of INSN is a former scratch. */
2014bool
2015lra_former_scratch_operand_p (rtx_insn *insn, int nop)
2016{
2017 return bitmap_bit_p (&scratch_operand_bitmap,
2018 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop) != 0;
2019}
2020
2021/* Register operand NOP in INSN as a former scratch. It will be
2022 changed to scratch back, if it is necessary, at the LRA end. */
2023void
2024lra_register_new_scratch_op (rtx_insn *insn, int nop)
2025{
2026 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
2027 rtx op = *id->operand_loc[nop];
2028 sloc_t loc = XNEW (struct sloc);
2029 lra_assert (REG_P (op));
2030 loc->insn = insn;
2031 loc->nop = nop;
2032 scratches.safe_push (loc);
2033 bitmap_set_bit (&scratch_bitmap, REGNO (op));
2034 bitmap_set_bit (&scratch_operand_bitmap,
2035 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop);
2036 add_reg_note (insn, REG_UNUSED, op);
2037}
2038
2039/* Change scratches onto pseudos and save their location. */
2040static void
2041remove_scratches (void)
2042{
2043 int i;
2044 bool insn_changed_p;
2045 basic_block bb;
2046 rtx_insn *insn;
2047 rtx reg;
2048 lra_insn_recog_data_t id;
2049 struct lra_static_insn_data *static_id;
2050
2051 scratches.create (get_max_uid ());
2052 bitmap_initialize (&scratch_bitmap, &reg_obstack);
2053 bitmap_initialize (&scratch_operand_bitmap, &reg_obstack);
2054 FOR_EACH_BB_FN (bb, cfun)
2055 FOR_BB_INSNS (bb, insn)
2056 if (INSN_P (insn))
2057 {
2058 id = lra_get_insn_recog_data (insn);
2059 static_id = id->insn_static_data;
2060 insn_changed_p = false;
2061 for (i = 0; i < static_id->n_operands; i++)
2062 if (GET_CODE (*id->operand_loc[i]) == SCRATCH
2063 && GET_MODE (*id->operand_loc[i]) != VOIDmode)
2064 {
2065 insn_changed_p = true;
2066 *id->operand_loc[i] = reg
2067 = lra_create_new_reg (static_id->operand[i].mode,
2068 *id->operand_loc[i], ALL_REGS, NULL);
2069 lra_register_new_scratch_op (insn, i);
2070 if (lra_dump_file != NULL)
2071 fprintf (lra_dump_file,
2072 "Removing SCRATCH in insn #%u (nop %d)\n",
2073 INSN_UID (insn), i);
2074 }
2075 if (insn_changed_p)
2076 /* Because we might use DF right after caller-saves sub-pass
2077 we need to keep DF info up to date. */
2078 df_insn_rescan (insn);
2079 }
2080}
2081
2082/* Changes pseudos created by function remove_scratches onto scratches. */
2083static void
2084restore_scratches (void)
2085{
2086 int regno;
2087 unsigned i;
2088 sloc_t loc;
2089 rtx_insn *last = NULL;
2090 lra_insn_recog_data_t id = NULL;
2091
2092 for (i = 0; scratches.iterate (i, &loc); i++)
2093 {
2094 /* Ignore already deleted insns. */
2095 if (NOTE_P (loc->insn)
2096 && NOTE_KIND (loc->insn) == NOTE_INSN_DELETED)
2097 continue;
2098 if (last != loc->insn)
2099 {
2100 last = loc->insn;
2101 id = lra_get_insn_recog_data (last);
2102 }
2103 if (REG_P (*id->operand_loc[loc->nop])
2104 && ((regno = REGNO (*id->operand_loc[loc->nop]))
2105 >= FIRST_PSEUDO_REGISTER)
2106 && lra_get_regno_hard_regno (regno) < 0)
2107 {
2108 /* It should be only case when scratch register with chosen
2109 constraint 'X' did not get memory or hard register. */
2110 lra_assert (lra_former_scratch_p (regno));
2111 *id->operand_loc[loc->nop]
2112 = gen_rtx_SCRATCH (GET_MODE (*id->operand_loc[loc->nop]));
2113 lra_update_dup (id, loc->nop);
2114 if (lra_dump_file != NULL)
2115 fprintf (lra_dump_file, "Restoring SCRATCH in insn #%u(nop %d)\n",
2116 INSN_UID (loc->insn), loc->nop);
2117 }
2118 }
2119 for (i = 0; scratches.iterate (i, &loc); i++)
2120 free (loc);
2121 scratches.release ();
2122 bitmap_clear (&scratch_bitmap);
2123 bitmap_clear (&scratch_operand_bitmap);
2124}
2125
2126
2127
2128/* Function checks RTL for correctness. If FINAL_P is true, it is
2129 done at the end of LRA and the check is more rigorous. */
2130static void
2131check_rtl (bool final_p)
2132{
2133 basic_block bb;
2134 rtx_insn *insn;
2135
2136 lra_assert (! final_p || reload_completed);
2137 FOR_EACH_BB_FN (bb, cfun)
2138 FOR_BB_INSNS (bb, insn)
2139 if (NONDEBUG_INSN_P (insn)
2140 && GET_CODE (PATTERN (insn)) != USE
2141 && GET_CODE (PATTERN (insn)) != CLOBBER
2142 && GET_CODE (PATTERN (insn)) != ASM_INPUT)
2143 {
2144 if (final_p)
2145 {
2146 extract_constrain_insn (insn);
2147 continue;
2148 }
2149 /* LRA code is based on assumption that all addresses can be
2150 correctly decomposed. LRA can generate reloads for
2151 decomposable addresses. The decomposition code checks the
2152 correctness of the addresses. So we don't need to check
2153 the addresses here. Don't call insn_invalid_p here, it can
2154 change the code at this stage. */
2155 if (recog_memoized (insn) < 0 && asm_noperands (PATTERN (insn)) < 0)
2156 fatal_insn_not_found (insn);
2157 }
2158}
2159
2160/* Determine if the current function has an exception receiver block
2161 that reaches the exit block via non-exceptional edges */
2162static bool
2163has_nonexceptional_receiver (void)
2164{
2165 edge e;
2166 edge_iterator ei;
2167 basic_block *tos, *worklist, bb;
2168
2169 /* If we're not optimizing, then just err on the safe side. */
2170 if (!optimize)
2171 return true;
2172
2173 /* First determine which blocks can reach exit via normal paths. */
2174 tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1);
2175
2176 FOR_EACH_BB_FN (bb, cfun)
2177 bb->flags &= ~BB_REACHABLE;
2178
2179 /* Place the exit block on our worklist. */
2180 EXIT_BLOCK_PTR_FOR_FN (cfun)->flags |= BB_REACHABLE;
2181 *tos++ = EXIT_BLOCK_PTR_FOR_FN (cfun);
2182
2183 /* Iterate: find everything reachable from what we've already seen. */
2184 while (tos != worklist)
2185 {
2186 bb = *--tos;
2187
2188 FOR_EACH_EDGE (e, ei, bb->preds)
2189 if (e->flags & EDGE_ABNORMAL)
2190 {
2191 free (worklist);
2192 return true;
2193 }
2194 else
2195 {
2196 basic_block src = e->src;
2197
2198 if (!(src->flags & BB_REACHABLE))
2199 {
2200 src->flags |= BB_REACHABLE;
2201 *tos++ = src;
2202 }
2203 }
2204 }
2205 free (worklist);
2206 /* No exceptional block reached exit unexceptionally. */
2207 return false;
2208}
2209
2210
2211/* Process recursively X of INSN and add REG_INC notes if necessary. */
2212static void
2213add_auto_inc_notes (rtx_insn *insn, rtx x)
2214{
2215 enum rtx_code code = GET_CODE (x);
2216 const char *fmt;
2217 int i, j;
2218
2219 if (code == MEM && auto_inc_p (XEXP (x, 0)))
2220 {
2221 add_reg_note (insn, REG_INC, XEXP (XEXP (x, 0), 0));
2222 return;
2223 }
2224
2225 /* Scan all X sub-expressions. */
2226 fmt = GET_RTX_FORMAT (code);
2227 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2228 {
2229 if (fmt[i] == 'e')
2230 add_auto_inc_notes (insn, XEXP (x, i));
2231 else if (fmt[i] == 'E')
2232 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2233 add_auto_inc_notes (insn, XVECEXP (x, i, j));
2234 }
2235}
2236
2237
2238/* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2239 We change pseudos by hard registers without notification of DF and
2240 that can make the notes obsolete. DF-infrastructure does not deal
2241 with REG_INC notes -- so we should regenerate them here. */
2242static void
2243update_inc_notes (void)
2244{
2245 rtx *pnote;
2246 basic_block bb;
2247 rtx_insn *insn;
2248
2249 FOR_EACH_BB_FN (bb, cfun)
2250 FOR_BB_INSNS (bb, insn)
2251 if (NONDEBUG_INSN_P (insn))
2252 {
2253 pnote = &REG_NOTES (insn);
2254 while (*pnote != 0)
2255 {
2256 if (REG_NOTE_KIND (*pnote) == REG_DEAD
2257 || REG_NOTE_KIND (*pnote) == REG_UNUSED
2258 || REG_NOTE_KIND (*pnote) == REG_INC)
2259 *pnote = XEXP (*pnote, 1);
2260 else
2261 pnote = &XEXP (*pnote, 1);
2262 }
2263
2264 if (AUTO_INC_DEC)
2265 add_auto_inc_notes (insn, PATTERN (insn));
2266 }
2267}
2268
2269/* Set to 1 while in lra. */
2270int lra_in_progress;
2271
2272/* Start of pseudo regnos before the LRA. */
2273int lra_new_regno_start;
2274
2275/* Start of reload pseudo regnos before the new spill pass. */
2276int lra_constraint_new_regno_start;
2277
2278/* Avoid spilling pseudos with regno more than the following value if
2279 it is possible. */
2280int lra_bad_spill_regno_start;
2281
2282/* Inheritance pseudo regnos before the new spill pass. */
2283bitmap_head lra_inheritance_pseudos;
2284
2285/* Split regnos before the new spill pass. */
2286bitmap_head lra_split_regs;
2287
2288/* Reload pseudo regnos before the new assignment pass which still can
2289 be spilled after the assignment pass as memory is also accepted in
2290 insns for the reload pseudos. */
2291bitmap_head lra_optional_reload_pseudos;
2292
2293/* Pseudo regnos used for subreg reloads before the new assignment
2294 pass. Such pseudos still can be spilled after the assignment
2295 pass. */
2296bitmap_head lra_subreg_reload_pseudos;
2297
2298/* File used for output of LRA debug information. */
2299FILE *lra_dump_file;
2300
2301/* True if we should try spill into registers of different classes
2302 instead of memory. */
2303bool lra_reg_spill_p;
2304
2305/* Set up value LRA_REG_SPILL_P. */
2306static void
2307setup_reg_spill_flag (void)
2308{
2309 int cl, mode;
2310
2311 if (targetm.spill_class != NULL)
2312 for (cl = 0; cl < (int) LIM_REG_CLASSES; cl++)
2313 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
2314 if (targetm.spill_class ((enum reg_class) cl,
2315 (machine_mode) mode) != NO_REGS)
2316 {
2317 lra_reg_spill_p = true;
2318 return;
2319 }
2320 lra_reg_spill_p = false;
2321}
2322
2323/* True if the current function is too big to use regular algorithms
2324 in LRA. In other words, we should use simpler and faster algorithms
2325 in LRA. It also means we should not worry about generation code
2326 for caller saves. The value is set up in IRA. */
2327bool lra_simple_p;
2328
2329/* Major LRA entry function. F is a file should be used to dump LRA
2330 debug info. */
2331void
2332lra (FILE *f)
2333{
2334 int i;
2335 bool live_p, inserted_p;
2336
2337 lra_dump_file = f;
2338
2339 timevar_push (TV_LRA);
2340
2341 /* Make sure that the last insn is a note. Some subsequent passes
2342 need it. */
2343 emit_note (NOTE_INSN_DELETED);
2344
2345 COPY_HARD_REG_SET (lra_no_alloc_regs, ira_no_alloc_regs);
2346
2347 init_reg_info ();
2348 expand_reg_info ();
2349
2350 init_insn_recog_data ();
2351
2352 /* Some quick check on RTL generated by previous passes. */
2353 if (flag_checking)
2354 check_rtl (false);
2355
2356 lra_in_progress = 1;
2357
2358 lra_live_range_iter = lra_coalesce_iter = lra_constraint_iter = 0;
2359 lra_assignment_iter = lra_assignment_iter_after_spill = 0;
2360 lra_inheritance_iter = lra_undo_inheritance_iter = 0;
2361 lra_rematerialization_iter = 0;
2362
2363 setup_reg_spill_flag ();
2364
2365 /* Function remove_scratches can creates new pseudos for clobbers --
2366 so set up lra_constraint_new_regno_start before its call to
2367 permit changing reg classes for pseudos created by this
2368 simplification. */
2369 lra_constraint_new_regno_start = lra_new_regno_start = max_reg_num ();
2370 lra_bad_spill_regno_start = INT_MAX;
2371 remove_scratches ();
2372
2373 /* A function that has a non-local label that can reach the exit
2374 block via non-exceptional paths must save all call-saved
2375 registers. */
2376 if (cfun->has_nonlocal_label && has_nonexceptional_receiver ())
2377 crtl->saves_all_registers = 1;
2378
2379 if (crtl->saves_all_registers)
2380 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2381 if (! call_used_regs[i] && ! fixed_regs[i] && ! LOCAL_REGNO (i))
2382 df_set_regs_ever_live (i, true);
2383
2384 /* We don't DF from now and avoid its using because it is to
2385 expensive when a lot of RTL changes are made. */
2386 df_set_flags (DF_NO_INSN_RESCAN);
2387 lra_constraint_insn_stack.create (get_max_uid ());
2388 lra_constraint_insn_stack_bitmap = sbitmap_alloc (get_max_uid ());
2389 bitmap_clear (lra_constraint_insn_stack_bitmap);
2390 lra_live_ranges_init ();
2391 lra_constraints_init ();
2392 lra_curr_reload_num = 0;
2393 push_insns (get_last_insn (), NULL);
2394 /* It is needed for the 1st coalescing. */
2395 bitmap_initialize (&lra_inheritance_pseudos, &reg_obstack);
2396 bitmap_initialize (&lra_split_regs, &reg_obstack);
2397 bitmap_initialize (&lra_optional_reload_pseudos, &reg_obstack);
2398 bitmap_initialize (&lra_subreg_reload_pseudos, &reg_obstack);
2399 live_p = false;
2400 if (get_frame_size () != 0 && crtl->stack_alignment_needed)
2401 /* If we have a stack frame, we must align it now. The stack size
2402 may be a part of the offset computation for register
2403 elimination. */
2404 assign_stack_local (BLKmode, 0, crtl->stack_alignment_needed);
2405 lra_init_equiv ();
2406 for (;;)
2407 {
2408 for (;;)
2409 {
2410 bool reloads_p = lra_constraints (lra_constraint_iter == 0);
2411 /* Constraint transformations may result in that eliminable
2412 hard regs become uneliminable and pseudos which use them
2413 should be spilled. It is better to do it before pseudo
2414 assignments.
2415
2416 For example, rs6000 can make
2417 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2418 to use a constant pool. */
2419 lra_eliminate (false, false);
2420 /* We should try to assign hard registers to scratches even
2421 if there were no RTL transformations in lra_constraints.
2422 Also we should check IRA assignments on the first
2423 iteration as they can be wrong because of early clobbers
2424 operands which are ignored in IRA. */
2425 if (! reloads_p && lra_constraint_iter > 1)
2426 {
2427 /* Stack is not empty here only when there are changes
2428 during the elimination sub-pass. */
2429 if (bitmap_empty_p (lra_constraint_insn_stack_bitmap))
2430 break;
2431 else
2432 /* If there are no reloads but changing due
2433 elimination, restart the constraint sub-pass
2434 first. */
2435 continue;
2436 }
2437 /* Do inheritance only for regular algorithms. */
2438 if (! lra_simple_p)
2439 {
2440 if (flag_ipa_ra)
2441 {
2442 if (live_p)
2443 lra_clear_live_ranges ();
2444 /* As a side-effect of lra_create_live_ranges, we calculate
2445 actual_call_used_reg_set, which is needed during
2446 lra_inheritance. */
2447 lra_create_live_ranges (true, true);
2448 live_p = true;
2449 }
2450 lra_inheritance ();
2451 }
2452 if (live_p)
2453 lra_clear_live_ranges ();
2454 /* We need live ranges for lra_assign -- so build them. But
2455 don't remove dead insns or change global live info as we
2456 can undo inheritance transformations after inheritance
2457 pseudo assigning. */
2458 lra_create_live_ranges (true, false);
2459 live_p = true;
2460 /* If we don't spill non-reload and non-inheritance pseudos,
2461 there is no sense to run memory-memory move coalescing.
2462 If inheritance pseudos were spilled, the memory-memory
2463 moves involving them will be removed by pass undoing
2464 inheritance. */
2465 if (lra_simple_p)
2466 lra_assign ();
2467 else
2468 {
2469 bool spill_p = !lra_assign ();
2470
2471 if (lra_undo_inheritance ())
2472 live_p = false;
2473 if (spill_p)
2474 {
2475 if (! live_p)
2476 {
2477 lra_create_live_ranges (true, true);
2478 live_p = true;
2479 }
2480 if (lra_coalesce ())
2481 live_p = false;
2482 }
2483 if (! live_p)
2484 lra_clear_live_ranges ();
2485 }
2486 }
2487 /* Don't clear optional reloads bitmap until all constraints are
2488 satisfied as we need to differ them from regular reloads. */
2489 bitmap_clear (&lra_optional_reload_pseudos);
2490 bitmap_clear (&lra_subreg_reload_pseudos);
2491 bitmap_clear (&lra_inheritance_pseudos);
2492 bitmap_clear (&lra_split_regs);
2493 if (! live_p)
2494 {
2495 /* We need full live info for spilling pseudos into
2496 registers instead of memory. */
2497 lra_create_live_ranges (lra_reg_spill_p, true);
2498 live_p = true;
2499 }
2500 /* We should check necessity for spilling here as the above live
2501 range pass can remove spilled pseudos. */
2502 if (! lra_need_for_spills_p ())
2503 break;
2504 /* Now we know what pseudos should be spilled. Try to
2505 rematerialize them first. */
2506 if (lra_remat ())
2507 {
2508 /* We need full live info -- see the comment above. */
2509 lra_create_live_ranges (lra_reg_spill_p, true);
2510 live_p = true;
2511 if (! lra_need_for_spills_p ())
2512 break;
2513 }
2514 lra_spill ();
2515 /* Assignment of stack slots changes elimination offsets for
2516 some eliminations. So update the offsets here. */
2517 lra_eliminate (false, false);
2518 lra_constraint_new_regno_start = max_reg_num ();
2519 if (lra_bad_spill_regno_start == INT_MAX
2520 && lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES
2521 && lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
2522 /* After switching off inheritance and rematerialization
2523 passes, avoid spilling reload pseudos will be created to
2524 prevent LRA cycling in some complicated cases. */
2525 lra_bad_spill_regno_start = lra_constraint_new_regno_start;
2526 lra_assignment_iter_after_spill = 0;
2527 }
2528 restore_scratches ();
2529 lra_eliminate (true, false);
2530 lra_final_code_change ();
2531 lra_in_progress = 0;
2532 if (live_p)
2533 lra_clear_live_ranges ();
2534 lra_live_ranges_finish ();
2535 lra_constraints_finish ();
2536 finish_reg_info ();
2537 sbitmap_free (lra_constraint_insn_stack_bitmap);
2538 lra_constraint_insn_stack.release ();
2539 finish_insn_recog_data ();
2540 regstat_free_n_sets_and_refs ();
2541 regstat_free_ri ();
2542 reload_completed = 1;
2543 update_inc_notes ();
2544
2545 inserted_p = fixup_abnormal_edges ();
2546
2547 /* We've possibly turned single trapping insn into multiple ones. */
2548 if (cfun->can_throw_non_call_exceptions)
2549 {
2550 auto_sbitmap blocks (last_basic_block_for_fn (cfun));
2551 bitmap_ones (blocks);
2552 find_many_sub_basic_blocks (blocks);
2553 }
2554
2555 if (inserted_p)
2556 commit_edge_insertions ();
2557
2558 /* Replacing pseudos with their memory equivalents might have
2559 created shared rtx. Subsequent passes would get confused
2560 by this, so unshare everything here. */
2561 unshare_all_rtl_again (get_insns ());
2562
2563 if (flag_checking)
2564 check_rtl (true);
2565
2566 timevar_pop (TV_LRA);
2567}
2568
2569/* Called once per compiler to initialize LRA data once. */
2570void
2571lra_init_once (void)
2572{
2573 init_insn_code_data_once ();
2574}
2575
2576/* Called once per compiler to finish LRA data which are initialize
2577 once. */
2578void
2579lra_finish_once (void)
2580{
2581 finish_insn_code_data_once ();
2582}
2583