comparison gcc/lra.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents
children 84e7813d76e9
comparison
equal deleted inserted replaced
15:561a7518be6b 16:04ced10e8804
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
5 This file is part of GCC.
6
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.
11
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.
16
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/>. */
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. */
126 void
127 lra_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. */
154 HARD_REG_SET lra_no_alloc_regs;
155
156 static int get_new_reg_value (void);
157 static void expand_reg_info (void);
158 static void invalidate_insn_recog_data (int);
159 static int get_insn_freq (rtx_insn *);
160 static void invalidate_insn_data_regno_info (lra_insn_recog_data_t,
161 rtx_insn *, int);
162
163 /* Expand all regno related info needed for LRA. */
164 static void
165 expand_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. */
180 rtx
181 lra_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. */
222 rtx
223 lra_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. */
236 void
237 lra_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. */
244 void
245 lra_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. */
253 void
254 lra_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. */
262 void
263 lra_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. */
283 static rtx_insn *
284 emit_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. */
314 static rtx_insn *
315 emit_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. */
337 void
338 lra_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. */
481 int 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. */
487 void
488 lra_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. */
512 void
513 lra_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. */
530 object_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. */
539 static struct lra_insn_reg *
540 new_insn_reg (rtx_insn *insn, int regno, enum op_type type,
541 machine_mode mode,
542 bool subreg_p, bool early_clobber,
543 alternative_mask early_clobber_alts,
544 struct lra_insn_reg *next)
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. */
561 static void
562 free_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. */
574 static void
575 finish_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. */
587 struct 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. */
595 static 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 insns. If structure lra_static_insn_data is changed, the
606 initializer should be changed too. */
607 static struct lra_static_insn_data debug_insn_static_data =
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 /* Called once per compiler work to initialize some LRA data related
622 to insns. */
623 static void
624 init_insn_code_data_once (void)
625 {
626 memset (insn_code_data, 0, sizeof (insn_code_data));
627 }
628
629 /* Called once per compiler work to finalize some LRA data related to
630 insns. */
631 static void
632 finish_insn_code_data_once (void)
633 {
634 for (unsigned int i = 0; i < NUM_INSN_CODES; i++)
635 {
636 if (insn_code_data[i] != NULL)
637 free (insn_code_data[i]);
638 }
639 }
640
641 /* Return static insn data, allocate and setup if necessary. Although
642 dup_num is static data (it depends only on icode), to set it up we
643 need to extract insn first. So recog_data should be valid for
644 normal insn (ICODE >= 0) before the call. */
645 static struct lra_static_insn_data *
646 get_static_insn_data (int icode, int nop, int ndup, int nalt)
647 {
648 struct lra_static_insn_data *data;
649 size_t n_bytes;
650
651 lra_assert (icode < (int) NUM_INSN_CODES);
652 if (icode >= 0 && (data = insn_code_data[icode]) != NULL)
653 return data;
654 lra_assert (nop >= 0 && ndup >= 0 && nalt >= 0);
655 n_bytes = sizeof (struct lra_static_insn_data)
656 + sizeof (struct lra_operand_data) * nop
657 + sizeof (int) * ndup;
658 data = XNEWVAR (struct lra_static_insn_data, n_bytes);
659 data->operand_alternative = NULL;
660 data->n_operands = nop;
661 data->n_dups = ndup;
662 data->n_alternatives = nalt;
663 data->operand = ((struct lra_operand_data *)
664 ((char *) data + sizeof (struct lra_static_insn_data)));
665 data->dup_num = ((int *) ((char *) data->operand
666 + sizeof (struct lra_operand_data) * nop));
667 if (icode >= 0)
668 {
669 int i;
670
671 insn_code_data[icode] = data;
672 for (i = 0; i < nop; i++)
673 {
674 data->operand[i].constraint
675 = insn_data[icode].operand[i].constraint;
676 data->operand[i].mode = insn_data[icode].operand[i].mode;
677 data->operand[i].strict_low = insn_data[icode].operand[i].strict_low;
678 data->operand[i].is_operator
679 = insn_data[icode].operand[i].is_operator;
680 data->operand[i].type
681 = (data->operand[i].constraint[0] == '=' ? OP_OUT
682 : data->operand[i].constraint[0] == '+' ? OP_INOUT
683 : OP_IN);
684 data->operand[i].is_address = false;
685 }
686 for (i = 0; i < ndup; i++)
687 data->dup_num[i] = recog_data.dup_num[i];
688 }
689 return data;
690 }
691
692 /* The current length of the following array. */
693 int lra_insn_recog_data_len;
694
695 /* Map INSN_UID -> the insn recog data (NULL if unknown). */
696 lra_insn_recog_data_t *lra_insn_recog_data;
697
698 /* Initialize LRA data about insns. */
699 static void
700 init_insn_recog_data (void)
701 {
702 lra_insn_recog_data_len = 0;
703 lra_insn_recog_data = NULL;
704 }
705
706 /* Expand, if necessary, LRA data about insns. */
707 static void
708 check_and_expand_insn_recog_data (int index)
709 {
710 int i, old;
711
712 if (lra_insn_recog_data_len > index)
713 return;
714 old = lra_insn_recog_data_len;
715 lra_insn_recog_data_len = index * 3 / 2 + 1;
716 lra_insn_recog_data = XRESIZEVEC (lra_insn_recog_data_t,
717 lra_insn_recog_data,
718 lra_insn_recog_data_len);
719 for (i = old; i < lra_insn_recog_data_len; i++)
720 lra_insn_recog_data[i] = NULL;
721 }
722
723 /* Finish LRA DATA about insn. */
724 static void
725 free_insn_recog_data (lra_insn_recog_data_t data)
726 {
727 if (data->operand_loc != NULL)
728 free (data->operand_loc);
729 if (data->dup_loc != NULL)
730 free (data->dup_loc);
731 if (data->arg_hard_regs != NULL)
732 free (data->arg_hard_regs);
733 if (data->icode < 0 && NONDEBUG_INSN_P (data->insn))
734 {
735 if (data->insn_static_data->operand_alternative != NULL)
736 free (const_cast <operand_alternative *>
737 (data->insn_static_data->operand_alternative));
738 free_insn_regs (data->insn_static_data->hard_regs);
739 free (data->insn_static_data);
740 }
741 free_insn_regs (data->regs);
742 data->regs = NULL;
743 free (data);
744 }
745
746 /* Pools for copies. */
747 static object_allocator<lra_copy> lra_copy_pool ("lra copies");
748
749 /* Finish LRA data about all insns. */
750 static void
751 finish_insn_recog_data (void)
752 {
753 int i;
754 lra_insn_recog_data_t data;
755
756 for (i = 0; i < lra_insn_recog_data_len; i++)
757 if ((data = lra_insn_recog_data[i]) != NULL)
758 free_insn_recog_data (data);
759 finish_insn_regs ();
760 lra_copy_pool.release ();
761 lra_insn_reg_pool.release ();
762 free (lra_insn_recog_data);
763 }
764
765 /* Setup info about operands in alternatives of LRA DATA of insn. */
766 static void
767 setup_operand_alternative (lra_insn_recog_data_t data,
768 const operand_alternative *op_alt)
769 {
770 int i, j, nop, nalt;
771 int icode = data->icode;
772 struct lra_static_insn_data *static_data = data->insn_static_data;
773
774 static_data->commutative = -1;
775 nop = static_data->n_operands;
776 nalt = static_data->n_alternatives;
777 static_data->operand_alternative = op_alt;
778 for (i = 0; i < nop; i++)
779 {
780 static_data->operand[i].early_clobber_alts = 0;
781 static_data->operand[i].early_clobber = false;
782 static_data->operand[i].is_address = false;
783 if (static_data->operand[i].constraint[0] == '%')
784 {
785 /* We currently only support one commutative pair of operands. */
786 if (static_data->commutative < 0)
787 static_data->commutative = i;
788 else
789 lra_assert (icode < 0); /* Asm */
790 /* The last operand should not be marked commutative. */
791 lra_assert (i != nop - 1);
792 }
793 }
794 for (j = 0; j < nalt; j++)
795 for (i = 0; i < nop; i++, op_alt++)
796 {
797 static_data->operand[i].early_clobber |= op_alt->earlyclobber;
798 if (op_alt->earlyclobber)
799 static_data->operand[i].early_clobber_alts |= (alternative_mask) 1 << j;
800 static_data->operand[i].is_address |= op_alt->is_address;
801 }
802 }
803
804 /* Recursively process X and collect info about registers, which are
805 not the insn operands, in X with TYPE (in/out/inout) and flag that
806 it is early clobbered in the insn (EARLY_CLOBBER) and add the info
807 to LIST. X is a part of insn given by DATA. Return the result
808 list. */
809 static struct lra_insn_reg *
810 collect_non_operand_hard_regs (rtx *x, lra_insn_recog_data_t data,
811 struct lra_insn_reg *list,
812 enum op_type type, bool early_clobber)
813 {
814 int i, j, regno, last;
815 bool subreg_p;
816 machine_mode mode;
817 struct lra_insn_reg *curr;
818 rtx op = *x;
819 enum rtx_code code = GET_CODE (op);
820 const char *fmt = GET_RTX_FORMAT (code);
821
822 for (i = 0; i < data->insn_static_data->n_operands; i++)
823 if (! data->insn_static_data->operand[i].is_operator
824 && x == data->operand_loc[i])
825 /* It is an operand loc. Stop here. */
826 return list;
827 for (i = 0; i < data->insn_static_data->n_dups; i++)
828 if (x == data->dup_loc[i])
829 /* It is a dup loc. Stop here. */
830 return list;
831 mode = GET_MODE (op);
832 subreg_p = false;
833 if (code == SUBREG)
834 {
835 mode = wider_subreg_mode (op);
836 if (read_modify_subreg_p (op))
837 subreg_p = true;
838 op = SUBREG_REG (op);
839 code = GET_CODE (op);
840 }
841 if (REG_P (op))
842 {
843 if ((regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER)
844 return list;
845 /* Process all regs even unallocatable ones as we need info
846 about all regs for rematerialization pass. */
847 for (last = end_hard_regno (mode, regno); regno < last; regno++)
848 {
849 for (curr = list; curr != NULL; curr = curr->next)
850 if (curr->regno == regno && curr->subreg_p == subreg_p
851 && curr->biggest_mode == mode)
852 {
853 if (curr->type != type)
854 curr->type = OP_INOUT;
855 if (early_clobber)
856 {
857 curr->early_clobber = true;
858 curr->early_clobber_alts = ALL_ALTERNATIVES;
859 }
860 break;
861 }
862 if (curr == NULL)
863 {
864 /* This is a new hard regno or the info can not be
865 integrated into the found structure. */
866 #ifdef STACK_REGS
867 early_clobber
868 = (early_clobber
869 /* This clobber is to inform popping floating
870 point stack only. */
871 && ! (FIRST_STACK_REG <= regno
872 && regno <= LAST_STACK_REG));
873 #endif
874 list = new_insn_reg (data->insn, regno, type, mode, subreg_p,
875 early_clobber,
876 early_clobber ? ALL_ALTERNATIVES : 0, list);
877 }
878 }
879 return list;
880 }
881 switch (code)
882 {
883 case SET:
884 list = collect_non_operand_hard_regs (&SET_DEST (op), data,
885 list, OP_OUT, false);
886 list = collect_non_operand_hard_regs (&SET_SRC (op), data,
887 list, OP_IN, false);
888 break;
889 case CLOBBER:
890 /* We treat clobber of non-operand hard registers as early
891 clobber (the behavior is expected from asm). */
892 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
893 list, OP_OUT, true);
894 break;
895 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
896 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
897 list, OP_INOUT, false);
898 break;
899 case PRE_MODIFY: case POST_MODIFY:
900 list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
901 list, OP_INOUT, false);
902 list = collect_non_operand_hard_regs (&XEXP (op, 1), data,
903 list, OP_IN, false);
904 break;
905 default:
906 fmt = GET_RTX_FORMAT (code);
907 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
908 {
909 if (fmt[i] == 'e')
910 list = collect_non_operand_hard_regs (&XEXP (op, i), data,
911 list, OP_IN, false);
912 else if (fmt[i] == 'E')
913 for (j = XVECLEN (op, i) - 1; j >= 0; j--)
914 list = collect_non_operand_hard_regs (&XVECEXP (op, i, j), data,
915 list, OP_IN, false);
916 }
917 }
918 return list;
919 }
920
921 /* Set up and return info about INSN. Set up the info if it is not set up
922 yet. */
923 lra_insn_recog_data_t
924 lra_set_insn_recog_data (rtx_insn *insn)
925 {
926 lra_insn_recog_data_t data;
927 int i, n, icode;
928 rtx **locs;
929 unsigned int uid = INSN_UID (insn);
930 struct lra_static_insn_data *insn_static_data;
931
932 check_and_expand_insn_recog_data (uid);
933 if (DEBUG_INSN_P (insn))
934 icode = -1;
935 else
936 {
937 icode = INSN_CODE (insn);
938 if (icode < 0)
939 /* It might be a new simple insn which is not recognized yet. */
940 INSN_CODE (insn) = icode = recog_memoized (insn);
941 }
942 data = XNEW (struct lra_insn_recog_data);
943 lra_insn_recog_data[uid] = data;
944 data->insn = insn;
945 data->used_insn_alternative = -1;
946 data->icode = icode;
947 data->regs = NULL;
948 if (DEBUG_INSN_P (insn))
949 {
950 data->insn_static_data = &debug_insn_static_data;
951 data->dup_loc = NULL;
952 data->arg_hard_regs = NULL;
953 data->preferred_alternatives = ALL_ALTERNATIVES;
954 data->operand_loc = XNEWVEC (rtx *, 1);
955 data->operand_loc[0] = &INSN_VAR_LOCATION_LOC (insn);
956 return data;
957 }
958 if (icode < 0)
959 {
960 int nop, nalt;
961 machine_mode operand_mode[MAX_RECOG_OPERANDS];
962 const char *constraints[MAX_RECOG_OPERANDS];
963
964 nop = asm_noperands (PATTERN (insn));
965 data->operand_loc = data->dup_loc = NULL;
966 nalt = 1;
967 if (nop < 0)
968 {
969 /* It is a special insn like USE or CLOBBER. We should
970 recognize any regular insn otherwise LRA can do nothing
971 with this insn. */
972 gcc_assert (GET_CODE (PATTERN (insn)) == USE
973 || GET_CODE (PATTERN (insn)) == CLOBBER
974 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
975 data->insn_static_data = insn_static_data
976 = get_static_insn_data (-1, 0, 0, nalt);
977 }
978 else
979 {
980 /* expand_asm_operands makes sure there aren't too many
981 operands. */
982 lra_assert (nop <= MAX_RECOG_OPERANDS);
983 if (nop != 0)
984 data->operand_loc = XNEWVEC (rtx *, nop);
985 /* Now get the operand values and constraints out of the
986 insn. */
987 decode_asm_operands (PATTERN (insn), NULL,
988 data->operand_loc,
989 constraints, operand_mode, NULL);
990 if (nop > 0)
991 {
992 const char *p = recog_data.constraints[0];
993
994 for (p = constraints[0]; *p; p++)
995 nalt += *p == ',';
996 }
997 data->insn_static_data = insn_static_data
998 = get_static_insn_data (-1, nop, 0, nalt);
999 for (i = 0; i < nop; i++)
1000 {
1001 insn_static_data->operand[i].mode = operand_mode[i];
1002 insn_static_data->operand[i].constraint = constraints[i];
1003 insn_static_data->operand[i].strict_low = false;
1004 insn_static_data->operand[i].is_operator = false;
1005 insn_static_data->operand[i].is_address = false;
1006 }
1007 }
1008 for (i = 0; i < insn_static_data->n_operands; i++)
1009 insn_static_data->operand[i].type
1010 = (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1011 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1012 : OP_IN);
1013 data->preferred_alternatives = ALL_ALTERNATIVES;
1014 if (nop > 0)
1015 {
1016 operand_alternative *op_alt = XCNEWVEC (operand_alternative,
1017 nalt * nop);
1018 preprocess_constraints (nop, nalt, constraints, op_alt);
1019 setup_operand_alternative (data, op_alt);
1020 }
1021 }
1022 else
1023 {
1024 insn_extract (insn);
1025 data->insn_static_data = insn_static_data
1026 = get_static_insn_data (icode, insn_data[icode].n_operands,
1027 insn_data[icode].n_dups,
1028 insn_data[icode].n_alternatives);
1029 n = insn_static_data->n_operands;
1030 if (n == 0)
1031 locs = NULL;
1032 else
1033 {
1034 locs = XNEWVEC (rtx *, n);
1035 memcpy (locs, recog_data.operand_loc, n * sizeof (rtx *));
1036 }
1037 data->operand_loc = locs;
1038 n = insn_static_data->n_dups;
1039 if (n == 0)
1040 locs = NULL;
1041 else
1042 {
1043 locs = XNEWVEC (rtx *, n);
1044 memcpy (locs, recog_data.dup_loc, n * sizeof (rtx *));
1045 }
1046 data->dup_loc = locs;
1047 data->preferred_alternatives = get_preferred_alternatives (insn);
1048 const operand_alternative *op_alt = preprocess_insn_constraints (icode);
1049 if (!insn_static_data->operand_alternative)
1050 setup_operand_alternative (data, op_alt);
1051 else if (op_alt != insn_static_data->operand_alternative)
1052 insn_static_data->operand_alternative = op_alt;
1053 }
1054 if (GET_CODE (PATTERN (insn)) == CLOBBER || GET_CODE (PATTERN (insn)) == USE)
1055 insn_static_data->hard_regs = NULL;
1056 else
1057 insn_static_data->hard_regs
1058 = collect_non_operand_hard_regs (&PATTERN (insn), data,
1059 NULL, OP_IN, false);
1060 data->arg_hard_regs = NULL;
1061 if (CALL_P (insn))
1062 {
1063 bool use_p;
1064 rtx link;
1065 int n_hard_regs, regno, arg_hard_regs[FIRST_PSEUDO_REGISTER];
1066
1067 n_hard_regs = 0;
1068 /* Finding implicit hard register usage. We believe it will be
1069 not changed whatever transformations are used. Call insns
1070 are such example. */
1071 for (link = CALL_INSN_FUNCTION_USAGE (insn);
1072 link != NULL_RTX;
1073 link = XEXP (link, 1))
1074 if (((use_p = GET_CODE (XEXP (link, 0)) == USE)
1075 || GET_CODE (XEXP (link, 0)) == CLOBBER)
1076 && REG_P (XEXP (XEXP (link, 0), 0)))
1077 {
1078 regno = REGNO (XEXP (XEXP (link, 0), 0));
1079 lra_assert (regno < FIRST_PSEUDO_REGISTER);
1080 /* It is an argument register. */
1081 for (i = REG_NREGS (XEXP (XEXP (link, 0), 0)) - 1; i >= 0; i--)
1082 arg_hard_regs[n_hard_regs++]
1083 = regno + i + (use_p ? 0 : FIRST_PSEUDO_REGISTER);
1084 }
1085 if (n_hard_regs != 0)
1086 {
1087 arg_hard_regs[n_hard_regs++] = -1;
1088 data->arg_hard_regs = XNEWVEC (int, n_hard_regs);
1089 memcpy (data->arg_hard_regs, arg_hard_regs,
1090 sizeof (int) * n_hard_regs);
1091 }
1092 }
1093 /* Some output operand can be recognized only from the context not
1094 from the constraints which are empty in this case. Call insn may
1095 contain a hard register in set destination with empty constraint
1096 and extract_insn treats them as an input. */
1097 for (i = 0; i < insn_static_data->n_operands; i++)
1098 {
1099 int j;
1100 rtx pat, set;
1101 struct lra_operand_data *operand = &insn_static_data->operand[i];
1102
1103 /* ??? Should we treat 'X' the same way. It looks to me that
1104 'X' means anything and empty constraint means we do not
1105 care. */
1106 if (operand->type != OP_IN || *operand->constraint != '\0'
1107 || operand->is_operator)
1108 continue;
1109 pat = PATTERN (insn);
1110 if (GET_CODE (pat) == SET)
1111 {
1112 if (data->operand_loc[i] != &SET_DEST (pat))
1113 continue;
1114 }
1115 else if (GET_CODE (pat) == PARALLEL)
1116 {
1117 for (j = XVECLEN (pat, 0) - 1; j >= 0; j--)
1118 {
1119 set = XVECEXP (PATTERN (insn), 0, j);
1120 if (GET_CODE (set) == SET
1121 && &SET_DEST (set) == data->operand_loc[i])
1122 break;
1123 }
1124 if (j < 0)
1125 continue;
1126 }
1127 else
1128 continue;
1129 operand->type = OP_OUT;
1130 }
1131 return data;
1132 }
1133
1134 /* Return info about insn give by UID. The info should be already set
1135 up. */
1136 static lra_insn_recog_data_t
1137 get_insn_recog_data_by_uid (int uid)
1138 {
1139 lra_insn_recog_data_t data;
1140
1141 data = lra_insn_recog_data[uid];
1142 lra_assert (data != NULL);
1143 return data;
1144 }
1145
1146 /* Invalidate all info about insn given by its UID. */
1147 static void
1148 invalidate_insn_recog_data (int uid)
1149 {
1150 lra_insn_recog_data_t data;
1151
1152 data = lra_insn_recog_data[uid];
1153 lra_assert (data != NULL);
1154 free_insn_recog_data (data);
1155 lra_insn_recog_data[uid] = NULL;
1156 }
1157
1158 /* Update all the insn info about INSN. It is usually called when
1159 something in the insn was changed. Return the updated info. */
1160 lra_insn_recog_data_t
1161 lra_update_insn_recog_data (rtx_insn *insn)
1162 {
1163 lra_insn_recog_data_t data;
1164 int n;
1165 unsigned int uid = INSN_UID (insn);
1166 struct lra_static_insn_data *insn_static_data;
1167 HOST_WIDE_INT sp_offset = 0;
1168
1169 check_and_expand_insn_recog_data (uid);
1170 if ((data = lra_insn_recog_data[uid]) != NULL
1171 && data->icode != INSN_CODE (insn))
1172 {
1173 sp_offset = data->sp_offset;
1174 invalidate_insn_data_regno_info (data, insn, get_insn_freq (insn));
1175 invalidate_insn_recog_data (uid);
1176 data = NULL;
1177 }
1178 if (data == NULL)
1179 {
1180 data = lra_get_insn_recog_data (insn);
1181 /* Initiate or restore SP offset. */
1182 data->sp_offset = sp_offset;
1183 return data;
1184 }
1185 insn_static_data = data->insn_static_data;
1186 data->used_insn_alternative = -1;
1187 if (DEBUG_INSN_P (insn))
1188 return data;
1189 if (data->icode < 0)
1190 {
1191 int nop;
1192 machine_mode operand_mode[MAX_RECOG_OPERANDS];
1193 const char *constraints[MAX_RECOG_OPERANDS];
1194
1195 nop = asm_noperands (PATTERN (insn));
1196 if (nop >= 0)
1197 {
1198 lra_assert (nop == data->insn_static_data->n_operands);
1199 /* Now get the operand values and constraints out of the
1200 insn. */
1201 decode_asm_operands (PATTERN (insn), NULL,
1202 data->operand_loc,
1203 constraints, operand_mode, NULL);
1204
1205 if (flag_checking)
1206 for (int i = 0; i < nop; i++)
1207 lra_assert
1208 (insn_static_data->operand[i].mode == operand_mode[i]
1209 && insn_static_data->operand[i].constraint == constraints[i]
1210 && ! insn_static_data->operand[i].is_operator);
1211 }
1212
1213 if (flag_checking)
1214 for (int i = 0; i < insn_static_data->n_operands; i++)
1215 lra_assert
1216 (insn_static_data->operand[i].type
1217 == (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1218 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1219 : OP_IN));
1220 }
1221 else
1222 {
1223 insn_extract (insn);
1224 n = insn_static_data->n_operands;
1225 if (n != 0)
1226 memcpy (data->operand_loc, recog_data.operand_loc, n * sizeof (rtx *));
1227 n = insn_static_data->n_dups;
1228 if (n != 0)
1229 memcpy (data->dup_loc, recog_data.dup_loc, n * sizeof (rtx *));
1230 lra_assert (check_bool_attrs (insn));
1231 }
1232 return data;
1233 }
1234
1235 /* Set up that INSN is using alternative ALT now. */
1236 void
1237 lra_set_used_insn_alternative (rtx_insn *insn, int alt)
1238 {
1239 lra_insn_recog_data_t data;
1240
1241 data = lra_get_insn_recog_data (insn);
1242 data->used_insn_alternative = alt;
1243 }
1244
1245 /* Set up that insn with UID is using alternative ALT now. The insn
1246 info should be already set up. */
1247 void
1248 lra_set_used_insn_alternative_by_uid (int uid, int alt)
1249 {
1250 lra_insn_recog_data_t data;
1251
1252 check_and_expand_insn_recog_data (uid);
1253 data = lra_insn_recog_data[uid];
1254 lra_assert (data != NULL);
1255 data->used_insn_alternative = alt;
1256 }
1257
1258
1259
1260 /* This page contains code dealing with common register info and
1261 pseudo copies. */
1262
1263 /* The size of the following array. */
1264 static int reg_info_size;
1265 /* Common info about each register. */
1266 struct lra_reg *lra_reg_info;
1267
1268 /* Last register value. */
1269 static int last_reg_value;
1270
1271 /* Return new register value. */
1272 static int
1273 get_new_reg_value (void)
1274 {
1275 return ++last_reg_value;
1276 }
1277
1278 /* Vec referring to pseudo copies. */
1279 static vec<lra_copy_t> copy_vec;
1280
1281 /* Initialize I-th element of lra_reg_info. */
1282 static inline void
1283 initialize_lra_reg_info_element (int i)
1284 {
1285 bitmap_initialize (&lra_reg_info[i].insn_bitmap, &reg_obstack);
1286 #ifdef STACK_REGS
1287 lra_reg_info[i].no_stack_p = false;
1288 #endif
1289 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1290 CLEAR_HARD_REG_SET (lra_reg_info[i].actual_call_used_reg_set);
1291 lra_reg_info[i].preferred_hard_regno1 = -1;
1292 lra_reg_info[i].preferred_hard_regno2 = -1;
1293 lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1294 lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1295 lra_reg_info[i].biggest_mode = VOIDmode;
1296 lra_reg_info[i].live_ranges = NULL;
1297 lra_reg_info[i].nrefs = lra_reg_info[i].freq = 0;
1298 lra_reg_info[i].last_reload = 0;
1299 lra_reg_info[i].restore_rtx = NULL_RTX;
1300 lra_reg_info[i].val = get_new_reg_value ();
1301 lra_reg_info[i].offset = 0;
1302 lra_reg_info[i].copies = NULL;
1303 }
1304
1305 /* Initialize common reg info and copies. */
1306 static void
1307 init_reg_info (void)
1308 {
1309 int i;
1310
1311 last_reg_value = 0;
1312 reg_info_size = max_reg_num () * 3 / 2 + 1;
1313 lra_reg_info = XNEWVEC (struct lra_reg, reg_info_size);
1314 for (i = 0; i < reg_info_size; i++)
1315 initialize_lra_reg_info_element (i);
1316 copy_vec.truncate (0);
1317 }
1318
1319
1320 /* Finish common reg info and copies. */
1321 static void
1322 finish_reg_info (void)
1323 {
1324 int i;
1325
1326 for (i = 0; i < reg_info_size; i++)
1327 bitmap_clear (&lra_reg_info[i].insn_bitmap);
1328 free (lra_reg_info);
1329 reg_info_size = 0;
1330 }
1331
1332 /* Expand common reg info if it is necessary. */
1333 static void
1334 expand_reg_info (void)
1335 {
1336 int i, old = reg_info_size;
1337
1338 if (reg_info_size > max_reg_num ())
1339 return;
1340 reg_info_size = max_reg_num () * 3 / 2 + 1;
1341 lra_reg_info = XRESIZEVEC (struct lra_reg, lra_reg_info, reg_info_size);
1342 for (i = old; i < reg_info_size; i++)
1343 initialize_lra_reg_info_element (i);
1344 }
1345
1346 /* Free all copies. */
1347 void
1348 lra_free_copies (void)
1349 {
1350 lra_copy_t cp;
1351
1352 while (copy_vec.length () != 0)
1353 {
1354 cp = copy_vec.pop ();
1355 lra_reg_info[cp->regno1].copies = lra_reg_info[cp->regno2].copies = NULL;
1356 lra_copy_pool.remove (cp);
1357 }
1358 }
1359
1360 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution
1361 frequency is FREQ. */
1362 void
1363 lra_create_copy (int regno1, int regno2, int freq)
1364 {
1365 bool regno1_dest_p;
1366 lra_copy_t cp;
1367
1368 lra_assert (regno1 != regno2);
1369 regno1_dest_p = true;
1370 if (regno1 > regno2)
1371 {
1372 std::swap (regno1, regno2);
1373 regno1_dest_p = false;
1374 }
1375 cp = lra_copy_pool.allocate ();
1376 copy_vec.safe_push (cp);
1377 cp->regno1_dest_p = regno1_dest_p;
1378 cp->freq = freq;
1379 cp->regno1 = regno1;
1380 cp->regno2 = regno2;
1381 cp->regno1_next = lra_reg_info[regno1].copies;
1382 lra_reg_info[regno1].copies = cp;
1383 cp->regno2_next = lra_reg_info[regno2].copies;
1384 lra_reg_info[regno2].copies = cp;
1385 if (lra_dump_file != NULL)
1386 fprintf (lra_dump_file, " Creating copy r%d%sr%d@%d\n",
1387 regno1, regno1_dest_p ? "<-" : "->", regno2, freq);
1388 }
1389
1390 /* Return N-th (0, 1, ...) copy. If there is no copy, return
1391 NULL. */
1392 lra_copy_t
1393 lra_get_copy (int n)
1394 {
1395 if (n >= (int) copy_vec.length ())
1396 return NULL;
1397 return copy_vec[n];
1398 }
1399
1400
1401
1402 /* This page contains code dealing with info about registers in
1403 insns. */
1404
1405 /* Process X of insn UID recursively and add info (operand type is
1406 given by TYPE, flag of that it is early clobber is EARLY_CLOBBER)
1407 about registers in X to the insn DATA. If X can be early clobbered,
1408 alternatives in which it can be early clobbered are given by
1409 EARLY_CLOBBER_ALTS. */
1410 static void
1411 add_regs_to_insn_regno_info (lra_insn_recog_data_t data, rtx x, int uid,
1412 enum op_type type, bool early_clobber,
1413 alternative_mask early_clobber_alts)
1414 {
1415 int i, j, regno;
1416 bool subreg_p;
1417 machine_mode mode;
1418 const char *fmt;
1419 enum rtx_code code;
1420 struct lra_insn_reg *curr;
1421
1422 code = GET_CODE (x);
1423 mode = GET_MODE (x);
1424 subreg_p = false;
1425 if (GET_CODE (x) == SUBREG)
1426 {
1427 mode = wider_subreg_mode (x);
1428 if (read_modify_subreg_p (x))
1429 subreg_p = true;
1430 x = SUBREG_REG (x);
1431 code = GET_CODE (x);
1432 }
1433 if (REG_P (x))
1434 {
1435 regno = REGNO (x);
1436 /* Process all regs even unallocatable ones as we need info about
1437 all regs for rematerialization pass. */
1438 expand_reg_info ();
1439 if (bitmap_set_bit (&lra_reg_info[regno].insn_bitmap, uid))
1440 {
1441 data->regs = new_insn_reg (data->insn, regno, type, mode, subreg_p,
1442 early_clobber, early_clobber_alts,
1443 data->regs);
1444 return;
1445 }
1446 else
1447 {
1448 for (curr = data->regs; curr != NULL; curr = curr->next)
1449 if (curr->regno == regno)
1450 {
1451 if (curr->subreg_p != subreg_p || curr->biggest_mode != mode)
1452 /* The info can not be integrated into the found
1453 structure. */
1454 data->regs = new_insn_reg (data->insn, regno, type, mode,
1455 subreg_p, early_clobber,
1456 early_clobber_alts, data->regs);
1457 else
1458 {
1459 if (curr->type != type)
1460 curr->type = OP_INOUT;
1461 if (curr->early_clobber != early_clobber)
1462 curr->early_clobber = true;
1463 curr->early_clobber_alts |= early_clobber_alts;
1464 }
1465 return;
1466 }
1467 gcc_unreachable ();
1468 }
1469 }
1470
1471 switch (code)
1472 {
1473 case SET:
1474 add_regs_to_insn_regno_info (data, SET_DEST (x), uid, OP_OUT, false, 0);
1475 add_regs_to_insn_regno_info (data, SET_SRC (x), uid, OP_IN, false, 0);
1476 break;
1477 case CLOBBER:
1478 /* We treat clobber of non-operand hard registers as early
1479 clobber (the behavior is expected from asm). */
1480 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_OUT, true, ALL_ALTERNATIVES);
1481 break;
1482 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
1483 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false, 0);
1484 break;
1485 case PRE_MODIFY: case POST_MODIFY:
1486 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false, 0);
1487 add_regs_to_insn_regno_info (data, XEXP (x, 1), uid, OP_IN, false, 0);
1488 break;
1489 default:
1490 if ((code != PARALLEL && code != EXPR_LIST) || type != OP_OUT)
1491 /* Some targets place small structures in registers for return
1492 values of functions, and those registers are wrapped in
1493 PARALLEL that we may see as the destination of a SET. Here
1494 is an example:
1495
1496 (call_insn 13 12 14 2 (set (parallel:BLK [
1497 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1498 (const_int 0 [0]))
1499 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1500 (const_int 8 [0x8]))
1501 ])
1502 (call (mem:QI (symbol_ref:DI (... */
1503 type = OP_IN;
1504 fmt = GET_RTX_FORMAT (code);
1505 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1506 {
1507 if (fmt[i] == 'e')
1508 add_regs_to_insn_regno_info (data, XEXP (x, i), uid, type, false, 0);
1509 else if (fmt[i] == 'E')
1510 {
1511 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1512 add_regs_to_insn_regno_info (data, XVECEXP (x, i, j), uid,
1513 type, false, 0);
1514 }
1515 }
1516 }
1517 }
1518
1519 /* Return execution frequency of INSN. */
1520 static int
1521 get_insn_freq (rtx_insn *insn)
1522 {
1523 basic_block bb = BLOCK_FOR_INSN (insn);
1524
1525 gcc_checking_assert (bb != NULL);
1526 return REG_FREQ_FROM_BB (bb);
1527 }
1528
1529 /* Invalidate all reg info of INSN with DATA and execution frequency
1530 FREQ. Update common info about the invalidated registers. */
1531 static void
1532 invalidate_insn_data_regno_info (lra_insn_recog_data_t data, rtx_insn *insn,
1533 int freq)
1534 {
1535 int uid;
1536 bool debug_p;
1537 unsigned int i;
1538 struct lra_insn_reg *ir, *next_ir;
1539
1540 uid = INSN_UID (insn);
1541 debug_p = DEBUG_INSN_P (insn);
1542 for (ir = data->regs; ir != NULL; ir = next_ir)
1543 {
1544 i = ir->regno;
1545 next_ir = ir->next;
1546 lra_insn_reg_pool.remove (ir);
1547 bitmap_clear_bit (&lra_reg_info[i].insn_bitmap, uid);
1548 if (i >= FIRST_PSEUDO_REGISTER && ! debug_p)
1549 {
1550 lra_reg_info[i].nrefs--;
1551 lra_reg_info[i].freq -= freq;
1552 lra_assert (lra_reg_info[i].nrefs >= 0 && lra_reg_info[i].freq >= 0);
1553 }
1554 }
1555 data->regs = NULL;
1556 }
1557
1558 /* Invalidate all reg info of INSN. Update common info about the
1559 invalidated registers. */
1560 void
1561 lra_invalidate_insn_regno_info (rtx_insn *insn)
1562 {
1563 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn), insn,
1564 get_insn_freq (insn));
1565 }
1566
1567 /* Update common reg info from reg info of insn given by its DATA and
1568 execution frequency FREQ. */
1569 static void
1570 setup_insn_reg_info (lra_insn_recog_data_t data, int freq)
1571 {
1572 unsigned int i;
1573 struct lra_insn_reg *ir;
1574
1575 for (ir = data->regs; ir != NULL; ir = ir->next)
1576 if ((i = ir->regno) >= FIRST_PSEUDO_REGISTER)
1577 {
1578 lra_reg_info[i].nrefs++;
1579 lra_reg_info[i].freq += freq;
1580 }
1581 }
1582
1583 /* Set up insn reg info of INSN. Update common reg info from reg info
1584 of INSN. */
1585 void
1586 lra_update_insn_regno_info (rtx_insn *insn)
1587 {
1588 int i, uid, freq;
1589 lra_insn_recog_data_t data;
1590 struct lra_static_insn_data *static_data;
1591 enum rtx_code code;
1592 rtx link;
1593
1594 if (! INSN_P (insn))
1595 return;
1596 data = lra_get_insn_recog_data (insn);
1597 static_data = data->insn_static_data;
1598 freq = get_insn_freq (insn);
1599 invalidate_insn_data_regno_info (data, insn, freq);
1600 uid = INSN_UID (insn);
1601 for (i = static_data->n_operands - 1; i >= 0; i--)
1602 add_regs_to_insn_regno_info (data, *data->operand_loc[i], uid,
1603 static_data->operand[i].type,
1604 static_data->operand[i].early_clobber,
1605 static_data->operand[i].early_clobber_alts);
1606 if ((code = GET_CODE (PATTERN (insn))) == CLOBBER || code == USE)
1607 add_regs_to_insn_regno_info (data, XEXP (PATTERN (insn), 0), uid,
1608 code == USE ? OP_IN : OP_OUT, false, 0);
1609 if (CALL_P (insn))
1610 /* On some targets call insns can refer to pseudos in memory in
1611 CALL_INSN_FUNCTION_USAGE list. Process them in order to
1612 consider their occurrences in calls for different
1613 transformations (e.g. inheritance) with given pseudos. */
1614 for (link = CALL_INSN_FUNCTION_USAGE (insn);
1615 link != NULL_RTX;
1616 link = XEXP (link, 1))
1617 if (((code = GET_CODE (XEXP (link, 0))) == USE || code == CLOBBER)
1618 && MEM_P (XEXP (XEXP (link, 0), 0)))
1619 add_regs_to_insn_regno_info (data, XEXP (XEXP (link, 0), 0), uid,
1620 code == USE ? OP_IN : OP_OUT, false, 0);
1621 if (NONDEBUG_INSN_P (insn))
1622 setup_insn_reg_info (data, freq);
1623 }
1624
1625 /* Return reg info of insn given by it UID. */
1626 struct lra_insn_reg *
1627 lra_get_insn_regs (int uid)
1628 {
1629 lra_insn_recog_data_t data;
1630
1631 data = get_insn_recog_data_by_uid (uid);
1632 return data->regs;
1633 }
1634
1635
1636
1637 /* Recursive hash function for RTL X. */
1638 hashval_t
1639 lra_rtx_hash (rtx x)
1640 {
1641 int i, j;
1642 enum rtx_code code;
1643 const char *fmt;
1644 hashval_t val = 0;
1645
1646 if (x == 0)
1647 return val;
1648
1649 code = GET_CODE (x);
1650 val += (int) code + 4095;
1651
1652 /* Some RTL can be compared nonrecursively. */
1653 switch (code)
1654 {
1655 case REG:
1656 return val + REGNO (x);
1657
1658 case LABEL_REF:
1659 return iterative_hash_object (XEXP (x, 0), val);
1660
1661 case SYMBOL_REF:
1662 return iterative_hash_object (XSTR (x, 0), val);
1663
1664 case SCRATCH:
1665 case CONST_DOUBLE:
1666 case CONST_INT:
1667 case CONST_VECTOR:
1668 return val;
1669
1670 default:
1671 break;
1672 }
1673
1674 /* Hash the elements. */
1675 fmt = GET_RTX_FORMAT (code);
1676 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1677 {
1678 switch (fmt[i])
1679 {
1680 case 'w':
1681 val += XWINT (x, i);
1682 break;
1683
1684 case 'n':
1685 case 'i':
1686 val += XINT (x, i);
1687 break;
1688
1689 case 'V':
1690 case 'E':
1691 val += XVECLEN (x, i);
1692
1693 for (j = 0; j < XVECLEN (x, i); j++)
1694 val += lra_rtx_hash (XVECEXP (x, i, j));
1695 break;
1696
1697 case 'e':
1698 val += lra_rtx_hash (XEXP (x, i));
1699 break;
1700
1701 case 'S':
1702 case 's':
1703 val += htab_hash_string (XSTR (x, i));
1704 break;
1705
1706 case 'u':
1707 case '0':
1708 case 't':
1709 break;
1710
1711 /* It is believed that rtx's at this level will never
1712 contain anything but integers and other rtx's, except for
1713 within LABEL_REFs and SYMBOL_REFs. */
1714 default:
1715 abort ();
1716 }
1717 }
1718 return val;
1719 }
1720
1721
1722
1723 /* This page contains code dealing with stack of the insns which
1724 should be processed by the next constraint pass. */
1725
1726 /* Bitmap used to put an insn on the stack only in one exemplar. */
1727 static sbitmap lra_constraint_insn_stack_bitmap;
1728
1729 /* The stack itself. */
1730 vec<rtx_insn *> lra_constraint_insn_stack;
1731
1732 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg
1733 info for INSN, otherwise only update it if INSN is not already on the
1734 stack. */
1735 static inline void
1736 lra_push_insn_1 (rtx_insn *insn, bool always_update)
1737 {
1738 unsigned int uid = INSN_UID (insn);
1739 if (always_update)
1740 lra_update_insn_regno_info (insn);
1741 if (uid >= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap))
1742 lra_constraint_insn_stack_bitmap =
1743 sbitmap_resize (lra_constraint_insn_stack_bitmap, 3 * uid / 2, 0);
1744 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap, uid))
1745 return;
1746 bitmap_set_bit (lra_constraint_insn_stack_bitmap, uid);
1747 if (! always_update)
1748 lra_update_insn_regno_info (insn);
1749 lra_constraint_insn_stack.safe_push (insn);
1750 }
1751
1752 /* Put INSN on the stack. */
1753 void
1754 lra_push_insn (rtx_insn *insn)
1755 {
1756 lra_push_insn_1 (insn, false);
1757 }
1758
1759 /* Put INSN on the stack and update its reg info. */
1760 void
1761 lra_push_insn_and_update_insn_regno_info (rtx_insn *insn)
1762 {
1763 lra_push_insn_1 (insn, true);
1764 }
1765
1766 /* Put insn with UID on the stack. */
1767 void
1768 lra_push_insn_by_uid (unsigned int uid)
1769 {
1770 lra_push_insn (lra_insn_recog_data[uid]->insn);
1771 }
1772
1773 /* Take the last-inserted insns off the stack and return it. */
1774 rtx_insn *
1775 lra_pop_insn (void)
1776 {
1777 rtx_insn *insn = lra_constraint_insn_stack.pop ();
1778 bitmap_clear_bit (lra_constraint_insn_stack_bitmap, INSN_UID (insn));
1779 return insn;
1780 }
1781
1782 /* Return the current size of the insn stack. */
1783 unsigned int
1784 lra_insn_stack_length (void)
1785 {
1786 return lra_constraint_insn_stack.length ();
1787 }
1788
1789 /* Push insns FROM to TO (excluding it) going in reverse order. */
1790 static void
1791 push_insns (rtx_insn *from, rtx_insn *to)
1792 {
1793 rtx_insn *insn;
1794
1795 if (from == NULL_RTX)
1796 return;
1797 for (insn = from; insn != to; insn = PREV_INSN (insn))
1798 if (INSN_P (insn))
1799 lra_push_insn (insn);
1800 }
1801
1802 /* Set up sp offset for insn in range [FROM, LAST]. The offset is
1803 taken from the next BB insn after LAST or zero if there in such
1804 insn. */
1805 static void
1806 setup_sp_offset (rtx_insn *from, rtx_insn *last)
1807 {
1808 rtx_insn *before = next_nonnote_insn_bb (last);
1809 HOST_WIDE_INT offset = (before == NULL_RTX || ! INSN_P (before)
1810 ? 0 : lra_get_insn_recog_data (before)->sp_offset);
1811
1812 for (rtx_insn *insn = from; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
1813 lra_get_insn_recog_data (insn)->sp_offset = offset;
1814 }
1815
1816 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the
1817 insns onto the stack. Print about emitting the insns with
1818 TITLE. */
1819 void
1820 lra_process_new_insns (rtx_insn *insn, rtx_insn *before, rtx_insn *after,
1821 const char *title)
1822 {
1823 rtx_insn *last;
1824
1825 if (before == NULL_RTX && after == NULL_RTX)
1826 return;
1827 if (lra_dump_file != NULL)
1828 {
1829 dump_insn_slim (lra_dump_file, insn);
1830 if (before != NULL_RTX)
1831 {
1832 fprintf (lra_dump_file," %s before:\n", title);
1833 dump_rtl_slim (lra_dump_file, before, NULL, -1, 0);
1834 }
1835 if (after != NULL_RTX)
1836 {
1837 fprintf (lra_dump_file, " %s after:\n", title);
1838 dump_rtl_slim (lra_dump_file, after, NULL, -1, 0);
1839 }
1840 fprintf (lra_dump_file, "\n");
1841 }
1842 if (before != NULL_RTX)
1843 {
1844 if (cfun->can_throw_non_call_exceptions)
1845 copy_reg_eh_region_note_forward (insn, before, NULL);
1846 emit_insn_before (before, insn);
1847 push_insns (PREV_INSN (insn), PREV_INSN (before));
1848 setup_sp_offset (before, PREV_INSN (insn));
1849 }
1850 if (after != NULL_RTX)
1851 {
1852 if (cfun->can_throw_non_call_exceptions)
1853 copy_reg_eh_region_note_forward (insn, after, NULL);
1854 for (last = after; NEXT_INSN (last) != NULL_RTX; last = NEXT_INSN (last))
1855 ;
1856 emit_insn_after (after, insn);
1857 push_insns (last, insn);
1858 setup_sp_offset (after, last);
1859 }
1860 if (cfun->can_throw_non_call_exceptions)
1861 {
1862 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1863 if (note && !insn_could_throw_p (insn))
1864 remove_note (insn, note);
1865 }
1866 }
1867
1868
1869 /* Replace all references to register OLD_REGNO in *LOC with pseudo
1870 register NEW_REG. Try to simplify subreg of constant if SUBREG_P.
1871 Return true if any change was made. */
1872 bool
1873 lra_substitute_pseudo (rtx *loc, int old_regno, rtx new_reg, bool subreg_p)
1874 {
1875 rtx x = *loc;
1876 bool result = false;
1877 enum rtx_code code;
1878 const char *fmt;
1879 int i, j;
1880
1881 if (x == NULL_RTX)
1882 return false;
1883
1884 code = GET_CODE (x);
1885 if (code == SUBREG && subreg_p)
1886 {
1887 rtx subst, inner = SUBREG_REG (x);
1888 /* Transform subreg of constant while we still have inner mode
1889 of the subreg. The subreg internal should not be an insn
1890 operand. */
1891 if (REG_P (inner) && (int) REGNO (inner) == old_regno
1892 && CONSTANT_P (new_reg)
1893 && (subst = simplify_subreg (GET_MODE (x), new_reg, GET_MODE (inner),
1894 SUBREG_BYTE (x))) != NULL_RTX)
1895 {
1896 *loc = subst;
1897 return true;
1898 }
1899
1900 }
1901 else if (code == REG && (int) REGNO (x) == old_regno)
1902 {
1903 machine_mode mode = GET_MODE (x);
1904 machine_mode inner_mode = GET_MODE (new_reg);
1905
1906 if (mode != inner_mode
1907 && ! (CONST_INT_P (new_reg) && SCALAR_INT_MODE_P (mode)))
1908 {
1909 if (!partial_subreg_p (mode, inner_mode)
1910 || ! SCALAR_INT_MODE_P (inner_mode))
1911 new_reg = gen_rtx_SUBREG (mode, new_reg, 0);
1912 else
1913 new_reg = gen_lowpart_SUBREG (mode, new_reg);
1914 }
1915 *loc = new_reg;
1916 return true;
1917 }
1918
1919 /* Scan all the operand sub-expressions. */
1920 fmt = GET_RTX_FORMAT (code);
1921 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1922 {
1923 if (fmt[i] == 'e')
1924 {
1925 if (lra_substitute_pseudo (&XEXP (x, i), old_regno,
1926 new_reg, subreg_p))
1927 result = true;
1928 }
1929 else if (fmt[i] == 'E')
1930 {
1931 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1932 if (lra_substitute_pseudo (&XVECEXP (x, i, j), old_regno,
1933 new_reg, subreg_p))
1934 result = true;
1935 }
1936 }
1937 return result;
1938 }
1939
1940 /* Call lra_substitute_pseudo within an insn. Try to simplify subreg
1941 of constant if SUBREG_P. This won't update the insn ptr, just the
1942 contents of the insn. */
1943 bool
1944 lra_substitute_pseudo_within_insn (rtx_insn *insn, int old_regno,
1945 rtx new_reg, bool subreg_p)
1946 {
1947 rtx loc = insn;
1948 return lra_substitute_pseudo (&loc, old_regno, new_reg, subreg_p);
1949 }
1950
1951
1952
1953 /* This page contains code dealing with scratches (changing them onto
1954 pseudos and restoring them from the pseudos).
1955
1956 We change scratches into pseudos at the beginning of LRA to
1957 simplify dealing with them (conflicts, hard register assignments).
1958
1959 If the pseudo denoting scratch was spilled it means that we do need
1960 a hard register for it. Such pseudos are transformed back to
1961 scratches at the end of LRA. */
1962
1963 /* Description of location of a former scratch operand. */
1964 struct sloc
1965 {
1966 rtx_insn *insn; /* Insn where the scratch was. */
1967 int nop; /* Number of the operand which was a scratch. */
1968 };
1969
1970 typedef struct sloc *sloc_t;
1971
1972 /* Locations of the former scratches. */
1973 static vec<sloc_t> scratches;
1974
1975 /* Bitmap of scratch regnos. */
1976 static bitmap_head scratch_bitmap;
1977
1978 /* Bitmap of scratch operands. */
1979 static bitmap_head scratch_operand_bitmap;
1980
1981 /* Return true if pseudo REGNO is made of SCRATCH. */
1982 bool
1983 lra_former_scratch_p (int regno)
1984 {
1985 return bitmap_bit_p (&scratch_bitmap, regno);
1986 }
1987
1988 /* Return true if the operand NOP of INSN is a former scratch. */
1989 bool
1990 lra_former_scratch_operand_p (rtx_insn *insn, int nop)
1991 {
1992 return bitmap_bit_p (&scratch_operand_bitmap,
1993 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop) != 0;
1994 }
1995
1996 /* Register operand NOP in INSN as a former scratch. It will be
1997 changed to scratch back, if it is necessary, at the LRA end. */
1998 void
1999 lra_register_new_scratch_op (rtx_insn *insn, int nop)
2000 {
2001 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
2002 rtx op = *id->operand_loc[nop];
2003 sloc_t loc = XNEW (struct sloc);
2004 lra_assert (REG_P (op));
2005 loc->insn = insn;
2006 loc->nop = nop;
2007 scratches.safe_push (loc);
2008 bitmap_set_bit (&scratch_bitmap, REGNO (op));
2009 bitmap_set_bit (&scratch_operand_bitmap,
2010 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop);
2011 add_reg_note (insn, REG_UNUSED, op);
2012 }
2013
2014 /* Change scratches onto pseudos and save their location. */
2015 static void
2016 remove_scratches (void)
2017 {
2018 int i;
2019 bool insn_changed_p;
2020 basic_block bb;
2021 rtx_insn *insn;
2022 rtx reg;
2023 lra_insn_recog_data_t id;
2024 struct lra_static_insn_data *static_id;
2025
2026 scratches.create (get_max_uid ());
2027 bitmap_initialize (&scratch_bitmap, &reg_obstack);
2028 bitmap_initialize (&scratch_operand_bitmap, &reg_obstack);
2029 FOR_EACH_BB_FN (bb, cfun)
2030 FOR_BB_INSNS (bb, insn)
2031 if (INSN_P (insn))
2032 {
2033 id = lra_get_insn_recog_data (insn);
2034 static_id = id->insn_static_data;
2035 insn_changed_p = false;
2036 for (i = 0; i < static_id->n_operands; i++)
2037 if (GET_CODE (*id->operand_loc[i]) == SCRATCH
2038 && GET_MODE (*id->operand_loc[i]) != VOIDmode)
2039 {
2040 insn_changed_p = true;
2041 *id->operand_loc[i] = reg
2042 = lra_create_new_reg (static_id->operand[i].mode,
2043 *id->operand_loc[i], ALL_REGS, NULL);
2044 lra_register_new_scratch_op (insn, i);
2045 if (lra_dump_file != NULL)
2046 fprintf (lra_dump_file,
2047 "Removing SCRATCH in insn #%u (nop %d)\n",
2048 INSN_UID (insn), i);
2049 }
2050 if (insn_changed_p)
2051 /* Because we might use DF right after caller-saves sub-pass
2052 we need to keep DF info up to date. */
2053 df_insn_rescan (insn);
2054 }
2055 }
2056
2057 /* Changes pseudos created by function remove_scratches onto scratches. */
2058 static void
2059 restore_scratches (void)
2060 {
2061 int regno;
2062 unsigned i;
2063 sloc_t loc;
2064 rtx_insn *last = NULL;
2065 lra_insn_recog_data_t id = NULL;
2066
2067 for (i = 0; scratches.iterate (i, &loc); i++)
2068 {
2069 /* Ignore already deleted insns. */
2070 if (NOTE_P (loc->insn)
2071 && NOTE_KIND (loc->insn) == NOTE_INSN_DELETED)
2072 continue;
2073 if (last != loc->insn)
2074 {
2075 last = loc->insn;
2076 id = lra_get_insn_recog_data (last);
2077 }
2078 if (REG_P (*id->operand_loc[loc->nop])
2079 && ((regno = REGNO (*id->operand_loc[loc->nop]))
2080 >= FIRST_PSEUDO_REGISTER)
2081 && lra_get_regno_hard_regno (regno) < 0)
2082 {
2083 /* It should be only case when scratch register with chosen
2084 constraint 'X' did not get memory or hard register. */
2085 lra_assert (lra_former_scratch_p (regno));
2086 *id->operand_loc[loc->nop]
2087 = gen_rtx_SCRATCH (GET_MODE (*id->operand_loc[loc->nop]));
2088 lra_update_dup (id, loc->nop);
2089 if (lra_dump_file != NULL)
2090 fprintf (lra_dump_file, "Restoring SCRATCH in insn #%u(nop %d)\n",
2091 INSN_UID (loc->insn), loc->nop);
2092 }
2093 }
2094 for (i = 0; scratches.iterate (i, &loc); i++)
2095 free (loc);
2096 scratches.release ();
2097 bitmap_clear (&scratch_bitmap);
2098 bitmap_clear (&scratch_operand_bitmap);
2099 }
2100
2101
2102
2103 /* Function checks RTL for correctness. If FINAL_P is true, it is
2104 done at the end of LRA and the check is more rigorous. */
2105 static void
2106 check_rtl (bool final_p)
2107 {
2108 basic_block bb;
2109 rtx_insn *insn;
2110
2111 lra_assert (! final_p || reload_completed);
2112 FOR_EACH_BB_FN (bb, cfun)
2113 FOR_BB_INSNS (bb, insn)
2114 if (NONDEBUG_INSN_P (insn)
2115 && GET_CODE (PATTERN (insn)) != USE
2116 && GET_CODE (PATTERN (insn)) != CLOBBER
2117 && GET_CODE (PATTERN (insn)) != ASM_INPUT)
2118 {
2119 if (final_p)
2120 {
2121 extract_constrain_insn (insn);
2122 continue;
2123 }
2124 /* LRA code is based on assumption that all addresses can be
2125 correctly decomposed. LRA can generate reloads for
2126 decomposable addresses. The decomposition code checks the
2127 correctness of the addresses. So we don't need to check
2128 the addresses here. Don't call insn_invalid_p here, it can
2129 change the code at this stage. */
2130 if (recog_memoized (insn) < 0 && asm_noperands (PATTERN (insn)) < 0)
2131 fatal_insn_not_found (insn);
2132 }
2133 }
2134
2135 /* Determine if the current function has an exception receiver block
2136 that reaches the exit block via non-exceptional edges */
2137 static bool
2138 has_nonexceptional_receiver (void)
2139 {
2140 edge e;
2141 edge_iterator ei;
2142 basic_block *tos, *worklist, bb;
2143
2144 /* If we're not optimizing, then just err on the safe side. */
2145 if (!optimize)
2146 return true;
2147
2148 /* First determine which blocks can reach exit via normal paths. */
2149 tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1);
2150
2151 FOR_EACH_BB_FN (bb, cfun)
2152 bb->flags &= ~BB_REACHABLE;
2153
2154 /* Place the exit block on our worklist. */
2155 EXIT_BLOCK_PTR_FOR_FN (cfun)->flags |= BB_REACHABLE;
2156 *tos++ = EXIT_BLOCK_PTR_FOR_FN (cfun);
2157
2158 /* Iterate: find everything reachable from what we've already seen. */
2159 while (tos != worklist)
2160 {
2161 bb = *--tos;
2162
2163 FOR_EACH_EDGE (e, ei, bb->preds)
2164 if (e->flags & EDGE_ABNORMAL)
2165 {
2166 free (worklist);
2167 return true;
2168 }
2169 else
2170 {
2171 basic_block src = e->src;
2172
2173 if (!(src->flags & BB_REACHABLE))
2174 {
2175 src->flags |= BB_REACHABLE;
2176 *tos++ = src;
2177 }
2178 }
2179 }
2180 free (worklist);
2181 /* No exceptional block reached exit unexceptionally. */
2182 return false;
2183 }
2184
2185
2186 /* Process recursively X of INSN and add REG_INC notes if necessary. */
2187 static void
2188 add_auto_inc_notes (rtx_insn *insn, rtx x)
2189 {
2190 enum rtx_code code = GET_CODE (x);
2191 const char *fmt;
2192 int i, j;
2193
2194 if (code == MEM && auto_inc_p (XEXP (x, 0)))
2195 {
2196 add_reg_note (insn, REG_INC, XEXP (XEXP (x, 0), 0));
2197 return;
2198 }
2199
2200 /* Scan all X sub-expressions. */
2201 fmt = GET_RTX_FORMAT (code);
2202 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2203 {
2204 if (fmt[i] == 'e')
2205 add_auto_inc_notes (insn, XEXP (x, i));
2206 else if (fmt[i] == 'E')
2207 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2208 add_auto_inc_notes (insn, XVECEXP (x, i, j));
2209 }
2210 }
2211
2212
2213 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2214 We change pseudos by hard registers without notification of DF and
2215 that can make the notes obsolete. DF-infrastructure does not deal
2216 with REG_INC notes -- so we should regenerate them here. */
2217 static void
2218 update_inc_notes (void)
2219 {
2220 rtx *pnote;
2221 basic_block bb;
2222 rtx_insn *insn;
2223
2224 FOR_EACH_BB_FN (bb, cfun)
2225 FOR_BB_INSNS (bb, insn)
2226 if (NONDEBUG_INSN_P (insn))
2227 {
2228 pnote = &REG_NOTES (insn);
2229 while (*pnote != 0)
2230 {
2231 if (REG_NOTE_KIND (*pnote) == REG_DEAD
2232 || REG_NOTE_KIND (*pnote) == REG_UNUSED
2233 || REG_NOTE_KIND (*pnote) == REG_INC)
2234 *pnote = XEXP (*pnote, 1);
2235 else
2236 pnote = &XEXP (*pnote, 1);
2237 }
2238
2239 if (AUTO_INC_DEC)
2240 add_auto_inc_notes (insn, PATTERN (insn));
2241 }
2242 }
2243
2244 /* Set to 1 while in lra. */
2245 int lra_in_progress;
2246
2247 /* Start of pseudo regnos before the LRA. */
2248 int lra_new_regno_start;
2249
2250 /* Start of reload pseudo regnos before the new spill pass. */
2251 int lra_constraint_new_regno_start;
2252
2253 /* Avoid spilling pseudos with regno more than the following value if
2254 it is possible. */
2255 int lra_bad_spill_regno_start;
2256
2257 /* Inheritance pseudo regnos before the new spill pass. */
2258 bitmap_head lra_inheritance_pseudos;
2259
2260 /* Split regnos before the new spill pass. */
2261 bitmap_head lra_split_regs;
2262
2263 /* Reload pseudo regnos before the new assignment pass which still can
2264 be spilled after the assignment pass as memory is also accepted in
2265 insns for the reload pseudos. */
2266 bitmap_head lra_optional_reload_pseudos;
2267
2268 /* Pseudo regnos used for subreg reloads before the new assignment
2269 pass. Such pseudos still can be spilled after the assignment
2270 pass. */
2271 bitmap_head lra_subreg_reload_pseudos;
2272
2273 /* File used for output of LRA debug information. */
2274 FILE *lra_dump_file;
2275
2276 /* True if we should try spill into registers of different classes
2277 instead of memory. */
2278 bool lra_reg_spill_p;
2279
2280 /* Set up value LRA_REG_SPILL_P. */
2281 static void
2282 setup_reg_spill_flag (void)
2283 {
2284 int cl, mode;
2285
2286 if (targetm.spill_class != NULL)
2287 for (cl = 0; cl < (int) LIM_REG_CLASSES; cl++)
2288 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
2289 if (targetm.spill_class ((enum reg_class) cl,
2290 (machine_mode) mode) != NO_REGS)
2291 {
2292 lra_reg_spill_p = true;
2293 return;
2294 }
2295 lra_reg_spill_p = false;
2296 }
2297
2298 /* True if the current function is too big to use regular algorithms
2299 in LRA. In other words, we should use simpler and faster algorithms
2300 in LRA. It also means we should not worry about generation code
2301 for caller saves. The value is set up in IRA. */
2302 bool lra_simple_p;
2303
2304 /* Major LRA entry function. F is a file should be used to dump LRA
2305 debug info. */
2306 void
2307 lra (FILE *f)
2308 {
2309 int i;
2310 bool live_p, inserted_p;
2311
2312 lra_dump_file = f;
2313
2314 timevar_push (TV_LRA);
2315
2316 /* Make sure that the last insn is a note. Some subsequent passes
2317 need it. */
2318 emit_note (NOTE_INSN_DELETED);
2319
2320 COPY_HARD_REG_SET (lra_no_alloc_regs, ira_no_alloc_regs);
2321
2322 init_reg_info ();
2323 expand_reg_info ();
2324
2325 init_insn_recog_data ();
2326
2327 /* Some quick check on RTL generated by previous passes. */
2328 if (flag_checking)
2329 check_rtl (false);
2330
2331 lra_in_progress = 1;
2332
2333 lra_live_range_iter = lra_coalesce_iter = lra_constraint_iter = 0;
2334 lra_assignment_iter = lra_assignment_iter_after_spill = 0;
2335 lra_inheritance_iter = lra_undo_inheritance_iter = 0;
2336 lra_rematerialization_iter = 0;
2337
2338 setup_reg_spill_flag ();
2339
2340 /* Function remove_scratches can creates new pseudos for clobbers --
2341 so set up lra_constraint_new_regno_start before its call to
2342 permit changing reg classes for pseudos created by this
2343 simplification. */
2344 lra_constraint_new_regno_start = lra_new_regno_start = max_reg_num ();
2345 lra_bad_spill_regno_start = INT_MAX;
2346 remove_scratches ();
2347
2348 /* A function that has a non-local label that can reach the exit
2349 block via non-exceptional paths must save all call-saved
2350 registers. */
2351 if (cfun->has_nonlocal_label && has_nonexceptional_receiver ())
2352 crtl->saves_all_registers = 1;
2353
2354 if (crtl->saves_all_registers)
2355 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2356 if (! call_used_regs[i] && ! fixed_regs[i] && ! LOCAL_REGNO (i))
2357 df_set_regs_ever_live (i, true);
2358
2359 /* We don't DF from now and avoid its using because it is to
2360 expensive when a lot of RTL changes are made. */
2361 df_set_flags (DF_NO_INSN_RESCAN);
2362 lra_constraint_insn_stack.create (get_max_uid ());
2363 lra_constraint_insn_stack_bitmap = sbitmap_alloc (get_max_uid ());
2364 bitmap_clear (lra_constraint_insn_stack_bitmap);
2365 lra_live_ranges_init ();
2366 lra_constraints_init ();
2367 lra_curr_reload_num = 0;
2368 push_insns (get_last_insn (), NULL);
2369 /* It is needed for the 1st coalescing. */
2370 bitmap_initialize (&lra_inheritance_pseudos, &reg_obstack);
2371 bitmap_initialize (&lra_split_regs, &reg_obstack);
2372 bitmap_initialize (&lra_optional_reload_pseudos, &reg_obstack);
2373 bitmap_initialize (&lra_subreg_reload_pseudos, &reg_obstack);
2374 live_p = false;
2375 if (get_frame_size () != 0 && crtl->stack_alignment_needed)
2376 /* If we have a stack frame, we must align it now. The stack size
2377 may be a part of the offset computation for register
2378 elimination. */
2379 assign_stack_local (BLKmode, 0, crtl->stack_alignment_needed);
2380 lra_init_equiv ();
2381 for (;;)
2382 {
2383 for (;;)
2384 {
2385 bool reloads_p = lra_constraints (lra_constraint_iter == 0);
2386 /* Constraint transformations may result in that eliminable
2387 hard regs become uneliminable and pseudos which use them
2388 should be spilled. It is better to do it before pseudo
2389 assignments.
2390
2391 For example, rs6000 can make
2392 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2393 to use a constant pool. */
2394 lra_eliminate (false, false);
2395 /* We should try to assign hard registers to scratches even
2396 if there were no RTL transformations in lra_constraints.
2397 Also we should check IRA assignments on the first
2398 iteration as they can be wrong because of early clobbers
2399 operands which are ignored in IRA. */
2400 if (! reloads_p && lra_constraint_iter > 1)
2401 {
2402 /* Stack is not empty here only when there are changes
2403 during the elimination sub-pass. */
2404 if (bitmap_empty_p (lra_constraint_insn_stack_bitmap))
2405 break;
2406 else
2407 /* If there are no reloads but changing due
2408 elimination, restart the constraint sub-pass
2409 first. */
2410 continue;
2411 }
2412 /* Do inheritance only for regular algorithms. */
2413 if (! lra_simple_p)
2414 {
2415 if (flag_ipa_ra)
2416 {
2417 if (live_p)
2418 lra_clear_live_ranges ();
2419 /* As a side-effect of lra_create_live_ranges, we calculate
2420 actual_call_used_reg_set, which is needed during
2421 lra_inheritance. */
2422 lra_create_live_ranges (true, true);
2423 live_p = true;
2424 }
2425 lra_inheritance ();
2426 }
2427 if (live_p)
2428 lra_clear_live_ranges ();
2429 /* We need live ranges for lra_assign -- so build them. But
2430 don't remove dead insns or change global live info as we
2431 can undo inheritance transformations after inheritance
2432 pseudo assigning. */
2433 lra_create_live_ranges (true, false);
2434 live_p = true;
2435 /* If we don't spill non-reload and non-inheritance pseudos,
2436 there is no sense to run memory-memory move coalescing.
2437 If inheritance pseudos were spilled, the memory-memory
2438 moves involving them will be removed by pass undoing
2439 inheritance. */
2440 if (lra_simple_p)
2441 lra_assign ();
2442 else
2443 {
2444 bool spill_p = !lra_assign ();
2445
2446 if (lra_undo_inheritance ())
2447 live_p = false;
2448 if (spill_p)
2449 {
2450 if (! live_p)
2451 {
2452 lra_create_live_ranges (true, true);
2453 live_p = true;
2454 }
2455 if (lra_coalesce ())
2456 live_p = false;
2457 }
2458 if (! live_p)
2459 lra_clear_live_ranges ();
2460 }
2461 }
2462 /* Don't clear optional reloads bitmap until all constraints are
2463 satisfied as we need to differ them from regular reloads. */
2464 bitmap_clear (&lra_optional_reload_pseudos);
2465 bitmap_clear (&lra_subreg_reload_pseudos);
2466 bitmap_clear (&lra_inheritance_pseudos);
2467 bitmap_clear (&lra_split_regs);
2468 if (! live_p)
2469 {
2470 /* We need full live info for spilling pseudos into
2471 registers instead of memory. */
2472 lra_create_live_ranges (lra_reg_spill_p, true);
2473 live_p = true;
2474 }
2475 /* We should check necessity for spilling here as the above live
2476 range pass can remove spilled pseudos. */
2477 if (! lra_need_for_spills_p ())
2478 break;
2479 /* Now we know what pseudos should be spilled. Try to
2480 rematerialize them first. */
2481 if (lra_remat ())
2482 {
2483 /* We need full live info -- see the comment above. */
2484 lra_create_live_ranges (lra_reg_spill_p, true);
2485 live_p = true;
2486 if (! lra_need_for_spills_p ())
2487 break;
2488 }
2489 lra_spill ();
2490 /* Assignment of stack slots changes elimination offsets for
2491 some eliminations. So update the offsets here. */
2492 lra_eliminate (false, false);
2493 lra_constraint_new_regno_start = max_reg_num ();
2494 if (lra_bad_spill_regno_start == INT_MAX
2495 && lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES
2496 && lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
2497 /* After switching off inheritance and rematerialization
2498 passes, avoid spilling reload pseudos will be created to
2499 prevent LRA cycling in some complicated cases. */
2500 lra_bad_spill_regno_start = lra_constraint_new_regno_start;
2501 lra_assignment_iter_after_spill = 0;
2502 }
2503 restore_scratches ();
2504 lra_eliminate (true, false);
2505 lra_final_code_change ();
2506 lra_in_progress = 0;
2507 if (live_p)
2508 lra_clear_live_ranges ();
2509 lra_live_ranges_finish ();
2510 lra_constraints_finish ();
2511 finish_reg_info ();
2512 sbitmap_free (lra_constraint_insn_stack_bitmap);
2513 lra_constraint_insn_stack.release ();
2514 finish_insn_recog_data ();
2515 regstat_free_n_sets_and_refs ();
2516 regstat_free_ri ();
2517 reload_completed = 1;
2518 update_inc_notes ();
2519
2520 inserted_p = fixup_abnormal_edges ();
2521
2522 /* We've possibly turned single trapping insn into multiple ones. */
2523 if (cfun->can_throw_non_call_exceptions)
2524 {
2525 auto_sbitmap blocks (last_basic_block_for_fn (cfun));
2526 bitmap_ones (blocks);
2527 find_many_sub_basic_blocks (blocks);
2528 }
2529
2530 if (inserted_p)
2531 commit_edge_insertions ();
2532
2533 /* Replacing pseudos with their memory equivalents might have
2534 created shared rtx. Subsequent passes would get confused
2535 by this, so unshare everything here. */
2536 unshare_all_rtl_again (get_insns ());
2537
2538 if (flag_checking)
2539 check_rtl (true);
2540
2541 timevar_pop (TV_LRA);
2542 }
2543
2544 /* Called once per compiler to initialize LRA data once. */
2545 void
2546 lra_init_once (void)
2547 {
2548 init_insn_code_data_once ();
2549 }
2550
2551 /* Called once per compiler to finish LRA data which are initialize
2552 once. */
2553 void
2554 lra_finish_once (void)
2555 {
2556 finish_insn_code_data_once ();
2557 }