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