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