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