Line data Source code
1 : /* Rematerialize pseudos values.
2 : Copyright (C) 2014-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 : /* This code objective is to rematerialize spilled pseudo values. To
22 : do this we calculate available insn candidates. The candidate is
23 : available at some point if there is dominated set of insns with the
24 : same pattern, the insn inputs are not dying or modified on any path
25 : from the set, the outputs are not modified.
26 :
27 : The insns containing memory or spilled pseudos (except for the
28 : rematerialized pseudo) are not considered as such insns are not
29 : profitable in comparison with regular loads of spilled pseudo
30 : values. That simplifies the implementation as we don't need to
31 : deal with memory aliasing.
32 :
33 : To speed up available candidate calculation, we calculate partially
34 : available candidates first and use them for initialization of the
35 : availability. That is because (partial) availability sets are
36 : sparse.
37 :
38 : The rematerialization sub-pass could be improved further in the
39 : following ways:
40 :
41 : o We could make longer live ranges of inputs in the
42 : rematerialization candidates if their hard registers are not used
43 : for other purposes. This could be complicated if we need to
44 : update BB live info information as LRA does not use
45 : DF-infrastructure for compile-time reasons. This problem could
46 : be overcome if constrain making live ranges longer only in BB/EBB
47 : scope.
48 : o We could use cost-based decision to choose rematerialization insn
49 : (currently all insns without memory is can be used).
50 : o We could use other free hard regs for unused output pseudos in
51 : rematerialization candidates although such cases probably will
52 : be very rare. */
53 :
54 :
55 : #include "config.h"
56 : #include "system.h"
57 : #include "coretypes.h"
58 : #include "backend.h"
59 : #include "rtl.h"
60 : #include "df.h"
61 : #include "insn-config.h"
62 : #include "regs.h"
63 : #include "memmodel.h"
64 : #include "ira.h"
65 : #include "recog.h"
66 : #include "lra.h"
67 : #include "lra-int.h"
68 : #include "function-abi.h"
69 :
70 : /* Number of candidates for rematerialization. */
71 : static unsigned int cands_num;
72 :
73 : /* Bitmap used for different calculations. */
74 : static bitmap_head temp_bitmap;
75 :
76 : /* Registers accessed via subreg_p. */
77 : static bitmap_head subreg_regs;
78 :
79 : typedef struct cand *cand_t;
80 : typedef const struct cand *const_cand_t;
81 :
82 : /* Insn candidates for rematerialization. The candidate insn should
83 : have the following properies:
84 : o no any memory (as access to memory is non-profitable) or
85 : div/mod operations (as they are usually more expensive than loads)
86 : o no INOUT regs (it means no non-paradoxical subreg of output reg)
87 : o no multiple output pseudos
88 : o one output spilled pseudo (or reload pseudo of a spilled pseudo)
89 : o all other pseudos are with assigned hard regs. */
90 : struct cand
91 : {
92 : /* Index of the candidates in all_cands. */
93 : int index;
94 : /* Insn pseudo regno for rematerialization. */
95 : int regno;
96 : /* The candidate insn. */
97 : rtx_insn *insn;
98 : /* Non-negative if a reload pseudo is in the insn instead of the
99 : pseudo for rematerialization. */
100 : int reload_regno;
101 : /* Number of the operand containing the regno or its reload
102 : regno. */
103 : int nop;
104 : /* Next candidate for the same regno. */
105 : cand_t next_regno_cand;
106 : };
107 :
108 : /* Vector containing all candidates. */
109 : static vec<cand_t> all_cands;
110 : /* Map: insn -> candidate representing it. It is null if the insn cannot
111 : be used for rematerialization. */
112 : static cand_t *insn_to_cand;
113 : /* A secondary map, for candidates that involve two insns, where the
114 : second one makes the equivalence. The candidate must not be used
115 : before seeing this activation insn. */
116 : static cand_t *insn_to_cand_activation;
117 :
118 : /* Map regno -> candidates can be used for the regno
119 : rematerialization. */
120 : static cand_t *regno_cands;
121 :
122 : /* Data about basic blocks used for the rematerialization
123 : sub-pass. */
124 : class remat_bb_data
125 : {
126 : public:
127 : /* Basic block about which the below data are. */
128 : basic_block bb;
129 : /* Registers changed in the basic block: */
130 : bitmap_head changed_regs;
131 : /* Registers becoming dead in the BB. */
132 : bitmap_head dead_regs;
133 : /* Cands present in the BB whose in/out regs are not changed after
134 : the cands occurence and are not dead (except the reload
135 : regno). */
136 : bitmap_head gen_cands;
137 : bitmap_head livein_cands; /* cands whose inputs live at the BB start. */
138 : bitmap_head pavin_cands; /* cands partially available at BB entry. */
139 : bitmap_head pavout_cands; /* cands partially available at BB exit. */
140 : bitmap_head avin_cands; /* cands available at the entry of the BB. */
141 : bitmap_head avout_cands; /* cands available at the exit of the BB. */
142 : };
143 :
144 : /* Array for all BB data. Indexed by the corresponding BB index. */
145 : typedef class remat_bb_data *remat_bb_data_t;
146 :
147 : /* Basic blocks for data flow problems -- all bocks except the special
148 : ones. */
149 : static bitmap_head all_blocks;
150 :
151 : /* All basic block data are referred through the following array. */
152 : static remat_bb_data_t remat_bb_data;
153 :
154 : /* Two small functions for access to the bb data. */
155 : static inline remat_bb_data_t
156 148151639 : get_remat_bb_data (basic_block bb)
157 : {
158 148151639 : return &remat_bb_data[(bb)->index];
159 : }
160 :
161 : static inline remat_bb_data_t
162 27453372 : get_remat_bb_data_by_index (int index)
163 : {
164 27453372 : return &remat_bb_data[index];
165 : }
166 :
167 :
168 :
169 : /* Hash table for the candidates. Different insns (e.g. structurally
170 : the same insns or even insns with different unused output regs) can
171 : be represented by the same candidate in the table. */
172 : static htab_t cand_table;
173 :
174 : /* Hash function for candidate CAND. */
175 : static hashval_t
176 310434 : cand_hash (const void *cand)
177 : {
178 310434 : const_cand_t c = (const_cand_t) cand;
179 310434 : lra_insn_recog_data_t id = lra_get_insn_recog_data (c->insn);
180 310434 : struct lra_static_insn_data *static_id = id->insn_static_data;
181 310434 : int nops = static_id->n_operands;
182 310434 : hashval_t hash = 0;
183 :
184 942241 : for (int i = 0; i < nops; i++)
185 631807 : if (i == c->nop)
186 310434 : hash = iterative_hash_object (c->regno, hash);
187 321373 : else if (static_id->operand[i].type == OP_IN)
188 321373 : hash = iterative_hash_object (*id->operand_loc[i], hash);
189 310434 : return hash;
190 : }
191 :
192 : /* Equal function for candidates CAND1 and CAND2. They are equal if
193 : the corresponding candidate insns have the same code, the same
194 : regno for rematerialization, the same input operands. */
195 : static int
196 56566 : cand_eq_p (const void *cand1, const void *cand2)
197 : {
198 56566 : const_cand_t c1 = (const_cand_t) cand1;
199 56566 : const_cand_t c2 = (const_cand_t) cand2;
200 56566 : lra_insn_recog_data_t id1 = lra_get_insn_recog_data (c1->insn);
201 56566 : lra_insn_recog_data_t id2 = lra_get_insn_recog_data (c2->insn);
202 56566 : struct lra_static_insn_data *static_id1 = id1->insn_static_data;
203 56566 : int nops = static_id1->n_operands;
204 :
205 56566 : if (c1->regno != c2->regno
206 56184 : || INSN_CODE (c1->insn) < 0
207 56184 : || INSN_CODE (c1->insn) != INSN_CODE (c2->insn))
208 : return false;
209 56181 : gcc_assert (c1->nop == c2->nop);
210 168813 : for (int i = 0; i < nops; i++)
211 112640 : if (i != c1->nop && static_id1->operand[i].type == OP_IN
212 56459 : && *id1->operand_loc[i] != *id2->operand_loc[i])
213 : return false;
214 : return true;
215 : }
216 :
217 : /* Insert candidate CAND into the table if it is not there yet.
218 : Return candidate which is in the table. */
219 : static cand_t
220 310434 : insert_cand (cand_t cand)
221 : {
222 310434 : void **entry_ptr;
223 :
224 310434 : entry_ptr = htab_find_slot (cand_table, cand, INSERT);
225 310434 : if (*entry_ptr == NULL)
226 254261 : *entry_ptr = (void *) cand;
227 310434 : return (cand_t) *entry_ptr;
228 : }
229 :
230 : /* Free candidate CAND memory. */
231 : static void
232 254261 : free_cand (void *cand)
233 : {
234 254261 : free (cand);
235 254261 : }
236 :
237 : /* Initiate the candidate table. */
238 : static void
239 182566 : initiate_cand_table (void)
240 : {
241 182566 : cand_table = htab_create (8000, cand_hash, cand_eq_p,
242 : (htab_del) free_cand);
243 182566 : }
244 :
245 : /* Finish the candidate table. */
246 : static void
247 182566 : finish_cand_table (void)
248 : {
249 0 : htab_delete (cand_table);
250 0 : }
251 :
252 :
253 :
254 : /* Return true if X contains memory, some UNSPEC, or expensive operations. We
255 : cannot just check insn operands as memory or unspec might be not an operand
256 : itself but contain an operand. Insns with memory access or expensive ones
257 : are not profitable for rematerialization. Rematerialization of UNSPEC might
258 : result in wrong code generation as the UNPEC effect is unknown
259 : (e.g. generating a label). */
260 : static bool
261 52406617 : bad_for_rematerialization_p (rtx x)
262 : {
263 52406617 : int i, j;
264 52406617 : const char *fmt;
265 52406617 : enum rtx_code code;
266 :
267 52406617 : if (MEM_P (x) || GET_CODE (x) == UNSPEC || GET_CODE (x) == UNSPEC_VOLATILE
268 : /* Usually the following operations are expensive and does not worth to
269 : rematerialize: */
270 : || GET_CODE(x) == DIV || GET_CODE(x) == UDIV
271 : || GET_CODE(x) == MOD || GET_CODE(x) == UMOD)
272 : return true;
273 49700151 : code = GET_CODE (x);
274 49700151 : fmt = GET_RTX_FORMAT (code);
275 111443128 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
276 : {
277 64885118 : if (fmt[i] == 'e')
278 : {
279 33931714 : if (bad_for_rematerialization_p (XEXP (x, i)))
280 : return true;
281 : }
282 30953404 : else if (fmt[i] == 'E')
283 : {
284 5760820 : for (j = XVECLEN (x, i) - 1; j >= 0; j--)
285 4136063 : if (bad_for_rematerialization_p (XVECEXP (x, i, j)))
286 : return true;
287 : }
288 : }
289 : return false;
290 : }
291 :
292 : /* If INSN cannot be used for rematerialization, return negative
293 : value. If INSN can be considered as a candidate for
294 : rematerialization, return value which is the operand number of the
295 : pseudo for which the insn can be used for rematerialization. Here
296 : we consider the insns without any memory, spilled pseudo (except
297 : for the rematerialization pseudo), or dying or unused regs. */
298 : static int
299 42072667 : operand_to_remat (rtx_insn *insn)
300 : {
301 42072667 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
302 42072667 : struct lra_static_insn_data *static_id = id->insn_static_data;
303 42072667 : struct lra_insn_reg *reg, *found_reg = NULL;
304 :
305 : /* Don't rematerialize insns which can change PC. */
306 42072667 : if (JUMP_P (insn) || CALL_P (insn))
307 : return -1;
308 : /* First find a pseudo which can be rematerialized. */
309 77073437 : for (reg = id->regs; reg != NULL; reg = reg->next)
310 : {
311 : /* True FRAME_POINTER_NEEDED might be because we cannot follow
312 : changing sp offsets, e.g. alloca is used. If the insn contains
313 : stack pointer in such case, we cannot rematerialize it as we
314 : cannot know sp offset at a rematerialization place. */
315 56714158 : if (reg->regno == STACK_POINTER_REGNUM && frame_pointer_needed)
316 : return -1;
317 55992579 : else if (reg->type == OP_OUT)
318 : {
319 : /* We permits only one spilled reg. */
320 23779549 : if (found_reg != NULL)
321 : return -1;
322 : found_reg = reg;
323 : }
324 : /* IRA calculates conflicts separately for subregs of two words
325 : pseudo. Even if the pseudo lives, e.g. one its subreg can be
326 : used lately, another subreg hard register can be already used
327 : for something else. In such case, it is not safe to
328 : rematerialize the insn. */
329 55975027 : if (reg->regno >= FIRST_PSEUDO_REGISTER
330 55975027 : && bitmap_bit_p (&subreg_regs, reg->regno))
331 : return -1;
332 :
333 : /* Don't allow hard registers to be rematerialized. */
334 55028862 : if (reg->regno < FIRST_PSEUDO_REGISTER)
335 : return -1;
336 : }
337 20359279 : if (found_reg == NULL)
338 : return -1;
339 14338840 : if (found_reg->regno < FIRST_PSEUDO_REGISTER)
340 : return -1;
341 14338840 : if (bad_for_rematerialization_p (PATTERN (insn)))
342 : return -1;
343 : /* Check the other regs are not spilled. */
344 25207002 : for (reg = id->regs; reg != NULL; reg = reg->next)
345 22339383 : if (found_reg == reg)
346 11631636 : continue;
347 10707747 : else if (reg->type == OP_INOUT)
348 : return -1;
349 10703911 : else if (reg->regno >= FIRST_PSEUDO_REGISTER
350 10703911 : && reg_renumber[reg->regno] < 0)
351 : /* Another spilled reg. */
352 : return -1;
353 9047969 : else if (reg->type == OP_IN)
354 : {
355 9047969 : if (find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
356 : /* We don't want to make live ranges longer. */
357 : return -1;
358 : /* Check that there is no output reg as the input one. */
359 1944895 : for (struct lra_insn_reg *reg2 = id->regs;
360 6080934 : reg2 != NULL;
361 4136039 : reg2 = reg2->next)
362 4137942 : if (reg2->type == OP_OUT && reg->regno == reg2->regno)
363 : return -1;
364 1942992 : if (reg->regno < FIRST_PSEUDO_REGISTER)
365 0 : for (struct lra_insn_reg *reg2 = static_id->hard_regs;
366 0 : reg2 != NULL;
367 0 : reg2 = reg2->next)
368 0 : if (reg2->type == OP_OUT
369 0 : && reg->regno <= reg2->regno
370 0 : && (reg2->regno
371 0 : < (int) end_hard_regno (reg->biggest_mode, reg->regno)))
372 : return -1;
373 : }
374 : /* Check hard coded insn registers. */
375 2867619 : for (struct lra_insn_reg *reg = static_id->hard_regs;
376 3234307 : reg != NULL;
377 366688 : reg = reg->next)
378 366688 : if (reg->type == OP_INOUT)
379 : return -1;
380 366688 : else if (reg->type == OP_IN)
381 : {
382 : /* Check that there is no output hard reg as the input
383 : one. */
384 0 : for (struct lra_insn_reg *reg2 = static_id->hard_regs;
385 0 : reg2 != NULL;
386 0 : reg2 = reg2->next)
387 0 : if (reg2->type == OP_OUT && reg->regno == reg2->regno)
388 : return -1;
389 : }
390 : /* Find the rematerialization operand. */
391 2867619 : int nop = static_id->n_operands;
392 2924853 : for (int i = 0; i < nop; i++)
393 2885311 : if (REG_P (*id->operand_loc[i])
394 2885311 : && (int) REGNO (*id->operand_loc[i]) == found_reg->regno)
395 : return i;
396 : return -1;
397 : }
398 :
399 : /* Create candidate for INSN with rematerialization operand NOP and
400 : REGNO. Insert the candidate into the table and set up the
401 : corresponding INSN_TO_CAND element. */
402 : static void
403 310434 : create_cand (rtx_insn *insn, int nop, int regno, rtx_insn *activation = NULL)
404 : {
405 310434 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
406 310434 : rtx reg = *id->operand_loc[nop];
407 310434 : gcc_assert (REG_P (reg));
408 310434 : int op_regno = REGNO (reg);
409 310434 : gcc_assert (op_regno >= FIRST_PSEUDO_REGISTER);
410 310434 : cand_t cand = XNEW (struct cand);
411 310434 : cand->insn = insn;
412 310434 : cand->nop = nop;
413 310434 : cand->regno = regno;
414 310434 : cand->reload_regno = op_regno == regno ? -1 : op_regno;
415 310434 : gcc_assert (cand->regno >= 0);
416 310434 : cand_t cand_in_table = insert_cand (cand);
417 310434 : insn_to_cand[INSN_UID (insn)] = cand_in_table;
418 310434 : if (cand != cand_in_table)
419 56173 : free (cand);
420 : else
421 : {
422 : /* A new cand. */
423 254261 : cand->index = all_cands.length ();
424 254261 : all_cands.safe_push (cand);
425 254261 : cand->next_regno_cand = regno_cands[cand->regno];
426 254261 : regno_cands[cand->regno] = cand;
427 : }
428 310434 : if (activation)
429 25457 : insn_to_cand_activation[INSN_UID (activation)] = cand_in_table;
430 310434 : }
431 :
432 : /* Create rematerialization candidates (inserting them into the
433 : table). */
434 : static void
435 182566 : create_cands (void)
436 : {
437 182566 : rtx_insn *insn;
438 182566 : struct potential_cand
439 : {
440 : rtx_insn *insn;
441 : int nop;
442 : };
443 182566 : struct potential_cand *regno_potential_cand;
444 :
445 : /* Create candidates. */
446 182566 : regno_potential_cand = XCNEWVEC (struct potential_cand, max_reg_num ());
447 94467827 : for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
448 94285261 : if (NONDEBUG_INSN_P (insn))
449 : {
450 42098124 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
451 42098124 : int keep_regno = -1;
452 42098124 : rtx set = single_set (insn);
453 42098124 : int nop;
454 :
455 : /* See if this is an output reload for a previous insn. */
456 42098124 : if (set != NULL
457 40281010 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
458 : {
459 12018868 : rtx dstreg = SET_DEST (set);
460 12018868 : int src_regno = REGNO (SET_SRC (set));
461 12018868 : int dst_regno = REGNO (dstreg);
462 12018868 : rtx_insn *insn2 = regno_potential_cand[src_regno].insn;
463 :
464 12018868 : if (insn2 != NULL
465 12018868 : && dst_regno >= FIRST_PSEUDO_REGISTER
466 89054 : && reg_renumber[dst_regno] < 0
467 25589 : && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn)
468 12044457 : && insn2 == prev_nonnote_nondebug_insn (insn))
469 : {
470 25457 : create_cand (insn2, regno_potential_cand[src_regno].nop,
471 : dst_regno, insn);
472 25457 : goto done;
473 : }
474 : }
475 :
476 42072667 : nop = operand_to_remat (insn);
477 42072667 : if (nop >= 0)
478 : {
479 2828077 : gcc_assert (REG_P (*id->operand_loc[nop]));
480 2828077 : int regno = REGNO (*id->operand_loc[nop]);
481 2828077 : gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
482 : /* If we're setting an unrenumbered pseudo, make a candidate
483 : immediately. If it's a potential output reload register, save
484 : it for later; the code above looks for output reload insns later
485 : on. */
486 2828077 : if (reg_renumber[regno] < 0)
487 284977 : create_cand (insn, nop, regno);
488 2543100 : else if (regno >= lra_constraint_new_regno_start)
489 : {
490 885111 : regno_potential_cand[regno].insn = insn;
491 885111 : regno_potential_cand[regno].nop = nop;
492 885111 : keep_regno = regno;
493 : }
494 : }
495 :
496 39244590 : done:
497 109933205 : for (struct lra_insn_reg *reg = id->regs; reg != NULL; reg = reg->next)
498 67835081 : if (reg->type != OP_IN && reg->regno != keep_regno
499 28173869 : && reg->regno >= FIRST_PSEUDO_REGISTER)
500 20129043 : regno_potential_cand[reg->regno].insn = NULL;
501 : }
502 182566 : cands_num = all_cands.length ();
503 182566 : free (regno_potential_cand);
504 182566 : }
505 :
506 :
507 :
508 : /* Create and initialize BB data. */
509 : static void
510 182566 : create_remat_bb_data (void)
511 : {
512 182566 : basic_block bb;
513 182566 : remat_bb_data_t bb_info;
514 :
515 182566 : remat_bb_data = XNEWVEC (class remat_bb_data,
516 : last_basic_block_for_fn (cfun));
517 6941183 : FOR_ALL_BB_FN (bb, cfun)
518 : {
519 6758617 : gcc_checking_assert (bb->index >= 0
520 : && bb->index < last_basic_block_for_fn (cfun));
521 6758617 : bb_info = get_remat_bb_data (bb);
522 6758617 : bb_info->bb = bb;
523 6758617 : bitmap_initialize (&bb_info->changed_regs, ®_obstack);
524 6758617 : bitmap_initialize (&bb_info->dead_regs, ®_obstack);
525 6758617 : bitmap_initialize (&bb_info->gen_cands, ®_obstack);
526 6758617 : bitmap_initialize (&bb_info->livein_cands, ®_obstack);
527 6758617 : bitmap_initialize (&bb_info->pavin_cands, ®_obstack);
528 6758617 : bitmap_initialize (&bb_info->pavout_cands, ®_obstack);
529 6758617 : bitmap_initialize (&bb_info->avin_cands, ®_obstack);
530 6758617 : bitmap_initialize (&bb_info->avout_cands, ®_obstack);
531 : }
532 182566 : }
533 :
534 : /* Dump all candidates to DUMP_FILE. */
535 : static void
536 1 : dump_cands (FILE *dump_file)
537 : {
538 1 : int i;
539 1 : cand_t cand;
540 :
541 1 : fprintf (dump_file, "\nCands:\n");
542 2 : for (i = 0; i < (int) cands_num; i++)
543 : {
544 0 : cand = all_cands[i];
545 0 : fprintf (dump_file, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
546 : i, cand->nop, cand->regno, cand->reload_regno);
547 0 : print_inline_rtx (dump_file, cand->insn, 6);
548 0 : fprintf (dump_file, "\n");
549 : }
550 1 : }
551 :
552 : /* Dump all candidates and BB data. */
553 : static void
554 182566 : dump_candidates_and_remat_bb_data (void)
555 : {
556 182566 : basic_block bb;
557 :
558 182566 : if (lra_dump_file == NULL)
559 : return;
560 1 : dump_cands (lra_dump_file);
561 43 : FOR_EACH_BB_FN (bb, cfun)
562 : {
563 42 : fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
564 : /* Livein */
565 42 : fprintf (lra_dump_file, " register live in:");
566 42 : dump_regset (df_get_live_in (bb), lra_dump_file);
567 42 : putc ('\n', lra_dump_file);
568 : /* Liveout */
569 42 : fprintf (lra_dump_file, " register live out:");
570 42 : dump_regset (df_get_live_out (bb), lra_dump_file);
571 42 : putc ('\n', lra_dump_file);
572 : /* Changed/dead regs: */
573 42 : fprintf (lra_dump_file, " changed regs:");
574 42 : dump_regset (&get_remat_bb_data (bb)->changed_regs, lra_dump_file);
575 42 : putc ('\n', lra_dump_file);
576 42 : fprintf (lra_dump_file, " dead regs:");
577 42 : dump_regset (&get_remat_bb_data (bb)->dead_regs, lra_dump_file);
578 42 : putc ('\n', lra_dump_file);
579 42 : lra_dump_bitmap_with_title ("cands generated in BB",
580 42 : &get_remat_bb_data (bb)->gen_cands, bb->index);
581 42 : lra_dump_bitmap_with_title ("livein cands in BB",
582 42 : &get_remat_bb_data (bb)->livein_cands, bb->index);
583 42 : lra_dump_bitmap_with_title ("pavin cands in BB",
584 42 : &get_remat_bb_data (bb)->pavin_cands, bb->index);
585 42 : lra_dump_bitmap_with_title ("pavout cands in BB",
586 42 : &get_remat_bb_data (bb)->pavout_cands, bb->index);
587 42 : lra_dump_bitmap_with_title ("avin cands in BB",
588 42 : &get_remat_bb_data (bb)->avin_cands, bb->index);
589 42 : lra_dump_bitmap_with_title ("avout cands in BB",
590 42 : &get_remat_bb_data (bb)->avout_cands, bb->index);
591 : }
592 1 : fprintf (lra_dump_file, "subreg regs:");
593 1 : dump_regset (&subreg_regs, lra_dump_file);
594 1 : putc ('\n', lra_dump_file);
595 : }
596 :
597 : /* Free all BB data. */
598 : static void
599 182566 : finish_remat_bb_data (void)
600 : {
601 182566 : basic_block bb;
602 :
603 6576051 : FOR_EACH_BB_FN (bb, cfun)
604 : {
605 6393485 : bitmap_clear (&get_remat_bb_data (bb)->avout_cands);
606 6393485 : bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
607 6393485 : bitmap_clear (&get_remat_bb_data (bb)->pavout_cands);
608 6393485 : bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
609 6393485 : bitmap_clear (&get_remat_bb_data (bb)->livein_cands);
610 6393485 : bitmap_clear (&get_remat_bb_data (bb)->gen_cands);
611 6393485 : bitmap_clear (&get_remat_bb_data (bb)->dead_regs);
612 6393485 : bitmap_clear (&get_remat_bb_data (bb)->changed_regs);
613 : }
614 182566 : free (remat_bb_data);
615 182566 : }
616 :
617 :
618 :
619 : /* Update changed_regs, dead_regs, subreg_regs of BB from INSN. */
620 : static void
621 42098124 : set_bb_regs (basic_block bb, rtx_insn *insn)
622 : {
623 42098124 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
624 42098124 : remat_bb_data_t bb_info = get_remat_bb_data (bb);
625 42098124 : struct lra_insn_reg *reg;
626 :
627 109933205 : for (reg = id->regs; reg != NULL; reg = reg->next)
628 : {
629 67835081 : unsigned regno = reg->regno;
630 67835081 : if (reg->type != OP_IN)
631 29058980 : bitmap_set_bit (&bb_info->changed_regs, regno);
632 38776101 : else if (find_regno_note (insn, REG_DEAD, regno) != NULL)
633 21734505 : bitmap_set_bit (&bb_info->dead_regs, regno);
634 67835081 : if (regno >= FIRST_PSEUDO_REGISTER && reg->subreg_p)
635 527913 : bitmap_set_bit (&subreg_regs, regno);
636 : }
637 42098124 : if (CALL_P (insn))
638 : {
639 : /* Partially-clobbered registers might still be live. */
640 2507368 : HARD_REG_SET clobbers = insn_callee_abi (insn).full_reg_clobbers ();
641 2507368 : bitmap_ior_into (&get_remat_bb_data (bb)->dead_regs,
642 2507368 : bitmap_view<HARD_REG_SET> (clobbers));
643 : }
644 42098124 : }
645 :
646 : /* Calculate changed_regs and dead_regs for each BB. */
647 : static void
648 182566 : calculate_local_reg_remat_bb_data (void)
649 : {
650 182566 : basic_block bb;
651 182566 : rtx_insn *insn;
652 :
653 6576051 : FOR_EACH_BB_FN (bb, cfun)
654 98475357 : FOR_BB_INSNS (bb, insn)
655 92081872 : if (NONDEBUG_INSN_P (insn))
656 42098124 : set_bb_regs (bb, insn);
657 182566 : }
658 :
659 :
660 :
661 : /* Return true if REG overlaps an input operand or non-input hard register of
662 : INSN. Basically the function returns false if we can move rematerialization
663 : candidate INSN through another insn with output REG or dead input REG (we
664 : consider it to avoid extending reg live range) with possible output pseudo
665 : renaming in INSN. */
666 : static bool
667 4361480 : reg_overlap_for_remat_p (lra_insn_reg *reg, rtx_insn *insn)
668 : {
669 4361480 : int iter;
670 4361480 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
671 4361480 : struct lra_static_insn_data *static_id = id->insn_static_data;
672 4361480 : unsigned regno = reg->regno;
673 4361480 : int nregs;
674 :
675 4361480 : if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] >= 0)
676 3058914 : regno = reg_renumber[regno];
677 3655524 : if (regno >= FIRST_PSEUDO_REGISTER)
678 : nregs = 1;
679 : else
680 3764870 : nregs = hard_regno_nregs (regno, reg->biggest_mode);
681 :
682 4361480 : struct lra_insn_reg *reg2;
683 :
684 11931524 : for (iter = 0; iter < 2; iter++)
685 8152407 : for (reg2 = (iter == 0 ? id->regs : static_id->hard_regs);
686 15014911 : reg2 != NULL;
687 6862504 : reg2 = reg2->next)
688 : {
689 7444867 : int nregs2;
690 7444867 : unsigned regno2 = reg2->regno;
691 :
692 7444867 : if (reg2->type != OP_IN && regno2 >= FIRST_PSEUDO_REGISTER)
693 4361480 : continue;
694 :
695 3003222 : if (regno2 >= FIRST_PSEUDO_REGISTER && reg_renumber[regno2] >= 0)
696 3003222 : regno2 = reg_renumber[regno2];
697 3003222 : if (regno2 >= FIRST_PSEUDO_REGISTER)
698 : nregs2 = 1;
699 : else
700 3083387 : nregs2 = hard_regno_nregs (regno2, reg2->biggest_mode);
701 :
702 3083387 : if ((regno2 + nregs2 - 1 >= regno && regno2 < regno + nregs)
703 2501024 : || (regno + nregs - 1 >= regno2 && regno < regno2 + nregs2))
704 : return true;
705 : }
706 : return false;
707 : }
708 :
709 : /* Return true if a call used register is an input operand of INSN. */
710 : static bool
711 28910 : call_used_input_regno_present_p (const function_abi &abi, rtx_insn *insn)
712 : {
713 28910 : int iter;
714 28910 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
715 28910 : struct lra_static_insn_data *static_id = id->insn_static_data;
716 28910 : struct lra_insn_reg *reg;
717 :
718 86730 : for (iter = 0; iter < 2; iter++)
719 57820 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
720 112829 : reg != NULL;
721 55009 : reg = reg->next)
722 55009 : if (reg->type == OP_IN
723 24495 : && reg->regno < FIRST_PSEUDO_REGISTER
724 55009 : && abi.clobbers_reg_p (reg->biggest_mode, reg->regno))
725 : return true;
726 : return false;
727 : }
728 :
729 : /* Calculate livein_cands for each BB. */
730 : static void
731 182566 : calculate_livein_cands (void)
732 : {
733 182566 : basic_block bb;
734 :
735 6576051 : FOR_EACH_BB_FN (bb, cfun)
736 : {
737 6393485 : bitmap livein_regs = df_get_live_in (bb);
738 6393485 : bitmap livein_cands = &get_remat_bb_data (bb)->livein_cands;
739 61001025 : for (unsigned int i = 0; i < cands_num; i++)
740 : {
741 54607540 : cand_t cand = all_cands[i];
742 54607540 : lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
743 54607540 : struct lra_insn_reg *reg;
744 :
745 110285226 : for (reg = id->regs; reg != NULL; reg = reg->next)
746 92774210 : if (reg->type == OP_IN && ! bitmap_bit_p (livein_regs, reg->regno))
747 : break;
748 54607540 : if (reg == NULL)
749 17511016 : bitmap_set_bit (livein_cands, i);
750 : }
751 : }
752 182566 : }
753 :
754 : /* Calculate gen_cands for each BB. */
755 : static void
756 182566 : calculate_gen_cands (void)
757 : {
758 182566 : basic_block bb;
759 182566 : bitmap gen_cands;
760 182566 : rtx_insn *insn;
761 :
762 6576051 : FOR_EACH_BB_FN (bb, cfun)
763 : {
764 6393485 : gen_cands = &get_remat_bb_data (bb)->gen_cands;
765 6393485 : auto_bitmap gen_insns (®_obstack);
766 98475357 : FOR_BB_INSNS (bb, insn)
767 92081872 : if (INSN_P (insn))
768 : {
769 78848427 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
770 78848427 : struct lra_static_insn_data *static_id = id->insn_static_data;
771 78848427 : struct lra_insn_reg *reg;
772 78848427 : unsigned int uid;
773 78848427 : bitmap_iterator bi;
774 78848427 : cand_t cand;
775 78848427 : rtx set;
776 78848427 : int iter;
777 78848427 : int src_regno = -1, dst_regno = -1;
778 :
779 78848427 : if ((set = single_set (insn)) != NULL
780 78848427 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
781 : {
782 12018868 : src_regno = REGNO (SET_SRC (set));
783 12018868 : dst_regno = REGNO (SET_DEST (set));
784 : }
785 :
786 : /* Update gen_cands: */
787 78848427 : bitmap_clear (&temp_bitmap);
788 236545281 : for (iter = 0; iter < 2; iter++)
789 157696854 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
790 244151839 : reg != NULL;
791 86454985 : reg = reg->next)
792 86454985 : if (reg->type != OP_IN
793 86454985 : || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
794 63289203 : EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
795 : {
796 1954014 : rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
797 :
798 1954014 : cand = insn_to_cand[INSN_UID (insn2)];
799 1954014 : gcc_assert (cand != NULL);
800 : /* Ignore the reload insn. */
801 1954014 : if (src_regno == cand->reload_regno
802 799050 : && dst_regno == cand->regno)
803 48212 : continue;
804 1905802 : if (cand->regno == reg->regno
805 1905802 : || reg_overlap_for_remat_p (reg, insn2))
806 : {
807 275347 : bitmap_clear_bit (gen_cands, cand->index);
808 275347 : bitmap_set_bit (&temp_bitmap, uid);
809 : }
810 : }
811 :
812 78848427 : if (CALL_P (insn))
813 : {
814 2507368 : function_abi callee_abi = insn_callee_abi (insn);
815 2516330 : EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
816 : {
817 8962 : rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
818 :
819 8962 : cand = insn_to_cand[INSN_UID (insn2)];
820 8962 : gcc_assert (cand != NULL);
821 8962 : if (call_used_input_regno_present_p (callee_abi, insn2))
822 : {
823 0 : bitmap_clear_bit (gen_cands, cand->index);
824 0 : bitmap_set_bit (&temp_bitmap, uid);
825 : }
826 : }
827 : }
828 78848427 : bitmap_and_compl_into (gen_insns, &temp_bitmap);
829 :
830 78848427 : cand = insn_to_cand[INSN_UID (insn)];
831 78848427 : if (cand != NULL)
832 : {
833 310434 : bitmap_set_bit (gen_cands, cand->index);
834 310434 : bitmap_set_bit (gen_insns, INSN_UID (insn));
835 : }
836 : }
837 6393485 : }
838 182566 : }
839 :
840 :
841 :
842 : /* The common transfer function used by the DF equation solver to
843 : propagate (partial) availability info BB_IN to BB_OUT through block
844 : with BB_INDEX according to the following equation:
845 :
846 : bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
847 : */
848 : static bool
849 13726686 : cand_trans_fun (int bb_index, bitmap bb_in, bitmap bb_out)
850 : {
851 13726686 : remat_bb_data_t bb_info;
852 13726686 : bitmap bb_livein, bb_changed_regs, bb_dead_regs;
853 13726686 : unsigned int cid;
854 13726686 : bitmap_iterator bi;
855 :
856 13726686 : bb_info = get_remat_bb_data_by_index (bb_index);
857 13726686 : bb_livein = &bb_info->livein_cands;
858 13726686 : bb_changed_regs = &bb_info->changed_regs;
859 13726686 : bb_dead_regs = &bb_info->dead_regs;
860 : /* Calculate killed avin cands -- cands whose regs are changed or
861 : becoming dead in the BB. We calculate it here as we hope that
862 : repeated calculations are compensated by smaller size of BB_IN in
863 : comparison with all candidates number. */
864 13726686 : bitmap_clear (&temp_bitmap);
865 21989453 : EXECUTE_IF_SET_IN_BITMAP (bb_in, 0, cid, bi)
866 : {
867 8262767 : cand_t cand = all_cands[cid];
868 8262767 : lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
869 8262767 : struct lra_insn_reg *reg;
870 :
871 8262767 : if (! bitmap_bit_p (bb_livein, cid))
872 : {
873 96095 : bitmap_set_bit (&temp_bitmap, cid);
874 96095 : continue;
875 : }
876 16483396 : for (reg = id->regs; reg != NULL; reg = reg->next)
877 : /* Ignore all outputs which are not the regno for
878 : rematerialization. */
879 8519610 : if (reg->type == OP_OUT && reg->regno != cand->regno)
880 517501 : continue;
881 8002109 : else if (bitmap_bit_p (bb_changed_regs, reg->regno)
882 8002109 : || bitmap_bit_p (bb_dead_regs, reg->regno))
883 : {
884 202886 : bitmap_set_bit (&temp_bitmap, cid);
885 202886 : break;
886 : }
887 : /* Check regno for rematerialization. */
888 8166672 : if (bitmap_bit_p (bb_changed_regs, cand->regno)
889 8166672 : || bitmap_bit_p (bb_dead_regs, cand->regno))
890 162453 : bitmap_set_bit (&temp_bitmap, cid);
891 : }
892 13726686 : return bitmap_ior_and_compl (bb_out,
893 13726686 : &bb_info->gen_cands, bb_in, &temp_bitmap);
894 : }
895 :
896 :
897 :
898 : /* The transfer function used by the DF equation solver to propagate
899 : partial candidate availability info through block with BB_INDEX
900 : according to the following equation:
901 :
902 : bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
903 : */
904 : static bool
905 6968069 : cand_pav_trans_fun (int bb_index)
906 : {
907 6968069 : remat_bb_data_t bb_info;
908 :
909 6968069 : bb_info = get_remat_bb_data_by_index (bb_index);
910 6968069 : return cand_trans_fun (bb_index, &bb_info->pavin_cands,
911 6968069 : &bb_info->pavout_cands);
912 : }
913 :
914 : /* The confluence function used by the DF equation solver to set up
915 : cand_pav info for a block BB without predecessor. */
916 : static void
917 183793 : cand_pav_con_fun_0 (basic_block bb)
918 : {
919 183793 : bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
920 183793 : }
921 :
922 : /* The confluence function used by the DF equation solver to propagate
923 : partial candidate availability info from predecessor to successor
924 : on edge E (pred->bb) according to the following equation:
925 :
926 : bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
927 : */
928 : static bool
929 10045245 : cand_pav_con_fun_n (edge e)
930 : {
931 10045245 : basic_block pred = e->src;
932 10045245 : basic_block bb = e->dest;
933 10045245 : remat_bb_data_t bb_info;
934 10045245 : bitmap bb_pavin, pred_pavout;
935 :
936 10045245 : bb_info = get_remat_bb_data (bb);
937 10045245 : bb_pavin = &bb_info->pavin_cands;
938 10045245 : pred_pavout = &get_remat_bb_data (pred)->pavout_cands;
939 10045245 : return bitmap_ior_into (bb_pavin, pred_pavout);
940 : }
941 :
942 :
943 :
944 : /* The transfer function used by the DF equation solver to propagate
945 : candidate availability info through block with BB_INDEX according
946 : to the following equation:
947 :
948 : bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
949 : */
950 : static bool
951 6758617 : cand_av_trans_fun (int bb_index)
952 : {
953 6758617 : remat_bb_data_t bb_info;
954 :
955 6758617 : bb_info = get_remat_bb_data_by_index (bb_index);
956 6758617 : return cand_trans_fun (bb_index, &bb_info->avin_cands,
957 6758617 : &bb_info->avout_cands);
958 : }
959 :
960 : /* The confluence function used by the DF equation solver to set up
961 : cand_av info for a block BB without predecessor. */
962 : static void
963 183793 : cand_av_con_fun_0 (basic_block bb)
964 : {
965 183793 : bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
966 183793 : }
967 :
968 : /* The confluence function used by the DF equation solver to propagate
969 : cand_av info from predecessor to successor on edge E (pred->bb)
970 : according to the following equation:
971 :
972 : bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
973 : */
974 : static bool
975 9652543 : cand_av_con_fun_n (edge e)
976 : {
977 9652543 : basic_block pred = e->src;
978 9652543 : basic_block bb = e->dest;
979 9652543 : remat_bb_data_t bb_info;
980 9652543 : bitmap bb_avin, pred_avout;
981 :
982 9652543 : bb_info = get_remat_bb_data (bb);
983 9652543 : bb_avin = &bb_info->avin_cands;
984 9652543 : pred_avout = &get_remat_bb_data (pred)->avout_cands;
985 9652543 : return bitmap_and_into (bb_avin, pred_avout);
986 : }
987 :
988 : /* Calculate available candidates for each BB. */
989 : static void
990 182566 : calculate_global_remat_bb_data (void)
991 : {
992 182566 : basic_block bb;
993 :
994 182566 : df_simple_dataflow
995 182566 : (DF_FORWARD, NULL, cand_pav_con_fun_0, cand_pav_con_fun_n,
996 : cand_pav_trans_fun, &all_blocks,
997 : df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
998 : /* Initialize avin by pavin. */
999 6576051 : FOR_EACH_BB_FN (bb, cfun)
1000 6393485 : bitmap_copy (&get_remat_bb_data (bb)->avin_cands,
1001 6393485 : &get_remat_bb_data (bb)->pavin_cands);
1002 182566 : df_simple_dataflow
1003 182566 : (DF_FORWARD, NULL, cand_av_con_fun_0, cand_av_con_fun_n,
1004 : cand_av_trans_fun, &all_blocks,
1005 : df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
1006 182566 : }
1007 :
1008 :
1009 :
1010 : /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
1011 : static void
1012 109 : change_sp_offset (rtx_insn *insns, poly_int64 sp_offset)
1013 : {
1014 218 : for (rtx_insn *insn = insns; insn != NULL; insn = NEXT_INSN (insn))
1015 109 : eliminate_regs_in_insn (insn, false, false, sp_offset);
1016 109 : }
1017 :
1018 : /* Return start hard register of REG (can be a hard or a pseudo reg)
1019 : or -1 (if it is a spilled pseudo). Return number of hard registers
1020 : occupied by REG through parameter NREGS if the start hard reg is
1021 : not negative. */
1022 : static int
1023 50341858 : get_hard_regs (struct lra_insn_reg *reg, int &nregs)
1024 : {
1025 50341858 : int regno = reg->regno;
1026 50341858 : int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
1027 :
1028 50341858 : if (hard_regno >= 0)
1029 47297324 : nregs = hard_regno_nregs (hard_regno, reg->biggest_mode);
1030 50341858 : return hard_regno;
1031 : }
1032 :
1033 : /* Make copy of and register scratch pseudos in rematerialized insn
1034 : REMAT_INSN. */
1035 : static void
1036 2944 : update_scratch_ops (rtx_insn *remat_insn)
1037 : {
1038 2944 : lra_insn_recog_data_t id = lra_get_insn_recog_data (remat_insn);
1039 2944 : struct lra_static_insn_data *static_id = id->insn_static_data;
1040 9530 : for (int i = 0; i < static_id->n_operands; i++)
1041 : {
1042 6586 : rtx *loc = id->operand_loc[i];
1043 6586 : if (! REG_P (*loc))
1044 2551 : continue;
1045 4035 : int regno = REGNO (*loc);
1046 4035 : if (! ira_former_scratch_p (regno))
1047 4035 : continue;
1048 0 : *loc = lra_create_new_reg (GET_MODE (*loc), *loc,
1049 : lra_get_allocno_class (regno), NULL,
1050 : "scratch pseudo copy");
1051 0 : ira_register_new_scratch_op (remat_insn, i, id->icode);
1052 : }
1053 :
1054 2944 : }
1055 :
1056 : /* Insert rematerialization insns using the data-flow data calculated
1057 : earlier. */
1058 : static bool
1059 182566 : do_remat (void)
1060 : {
1061 182566 : unsigned regno;
1062 182566 : rtx_insn *insn;
1063 182566 : basic_block bb;
1064 182566 : bool changed_p = false;
1065 : /* Living hard regs and hard registers of living pseudos. */
1066 182566 : HARD_REG_SET live_hard_regs;
1067 182566 : bitmap_iterator bi;
1068 :
1069 182566 : auto_bitmap avail_cands (®_obstack);
1070 182566 : auto_bitmap active_cands (®_obstack);
1071 6576051 : FOR_EACH_BB_FN (bb, cfun)
1072 : {
1073 6393485 : CLEAR_HARD_REG_SET (live_hard_regs);
1074 67011611 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), 0, regno, bi)
1075 : {
1076 60618126 : int nregs = 1;
1077 60618126 : int hard_regno = regno;
1078 60618126 : if (regno >= FIRST_PSEUDO_REGISTER)
1079 : {
1080 52263188 : hard_regno = reg_renumber[regno];
1081 52263188 : if (hard_regno < 0)
1082 26316611 : continue;
1083 25946577 : nregs = hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno));
1084 : }
1085 68826030 : for (int i = 0; i < nregs; i++)
1086 34524515 : SET_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1087 : }
1088 6393485 : bitmap_and (avail_cands, &get_remat_bb_data (bb)->avin_cands,
1089 6393485 : &get_remat_bb_data (bb)->livein_cands);
1090 : /* Activating insns are always in the same block as their corresponding
1091 : remat insn, so at the start of a block the two bitsets are equal. */
1092 6393485 : bitmap_copy (active_cands, avail_cands);
1093 98475357 : FOR_BB_INSNS (bb, insn)
1094 : {
1095 92081872 : if (!NONDEBUG_INSN_P (insn))
1096 49986692 : continue;
1097 :
1098 42098124 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
1099 42098124 : struct lra_static_insn_data *static_id = id->insn_static_data;
1100 42098124 : struct lra_insn_reg *reg;
1101 42098124 : cand_t cand;
1102 42098124 : unsigned int cid;
1103 42098124 : bitmap_iterator bi;
1104 42098124 : rtx set;
1105 42098124 : int iter;
1106 42098124 : int src_regno = -1, dst_regno = -1;
1107 :
1108 42098124 : if ((set = single_set (insn)) != NULL
1109 42098124 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
1110 : {
1111 12018868 : src_regno = REGNO (SET_SRC (set));
1112 12018868 : dst_regno = REGNO (SET_DEST (set));
1113 : }
1114 :
1115 42098124 : cand = NULL;
1116 : /* Check possibility of rematerialization (hard reg or
1117 : unpsilled pseudo <- spilled pseudo): */
1118 42098124 : if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER
1119 10603673 : && reg_renumber[src_regno] < 0
1120 1795810 : && (dst_regno < FIRST_PSEUDO_REGISTER
1121 1637899 : || reg_renumber[dst_regno] >= 0))
1122 : {
1123 1795810 : for (cand = regno_cands[src_regno];
1124 2400745 : cand != NULL;
1125 604935 : cand = cand->next_regno_cand)
1126 608665 : if (bitmap_bit_p (avail_cands, cand->index)
1127 608665 : && bitmap_bit_p (active_cands, cand->index))
1128 : break;
1129 : }
1130 1795810 : int i, hard_regno, nregs;
1131 1795810 : int dst_hard_regno, dst_nregs;
1132 1795810 : rtx_insn *remat_insn = NULL;
1133 1795810 : poly_int64 cand_sp_offset = 0;
1134 1795810 : if (cand != NULL)
1135 : {
1136 3730 : lra_insn_recog_data_t cand_id
1137 3730 : = lra_get_insn_recog_data (cand->insn);
1138 3730 : struct lra_static_insn_data *static_cand_id
1139 : = cand_id->insn_static_data;
1140 3730 : rtx saved_op = *cand_id->operand_loc[cand->nop];
1141 :
1142 : /* Check clobbers do not kill something living. */
1143 3730 : gcc_assert (REG_P (saved_op));
1144 3730 : int ignore_regno = REGNO (saved_op);
1145 :
1146 7163 : dst_hard_regno = dst_regno < FIRST_PSEUDO_REGISTER
1147 3730 : ? dst_regno : reg_renumber[dst_regno];
1148 3730 : gcc_assert (dst_hard_regno >= 0);
1149 3730 : machine_mode mode = GET_MODE (SET_DEST (set));
1150 3730 : dst_nregs = hard_regno_nregs (dst_hard_regno, mode);
1151 :
1152 9652 : for (reg = cand_id->regs; reg != NULL; reg = reg->next)
1153 5922 : if (reg->type != OP_IN && reg->regno != ignore_regno)
1154 : {
1155 0 : hard_regno = get_hard_regs (reg, nregs);
1156 0 : gcc_assert (hard_regno >= 0);
1157 0 : for (i = 0; i < nregs; i++)
1158 0 : if (TEST_HARD_REG_BIT (live_hard_regs, hard_regno + i))
1159 : break;
1160 0 : if (i < nregs)
1161 : break;
1162 : /* Ensure the clobber also doesn't overlap dst_regno. */
1163 0 : if (hard_regno + nregs > dst_hard_regno
1164 0 : && hard_regno < dst_hard_regno + dst_nregs)
1165 : break;
1166 : }
1167 :
1168 3730 : if (reg == NULL)
1169 : {
1170 3730 : for (reg = static_cand_id->hard_regs;
1171 4125 : reg != NULL;
1172 395 : reg = reg->next)
1173 395 : if (reg->type != OP_IN)
1174 : {
1175 395 : if (TEST_HARD_REG_BIT (live_hard_regs, reg->regno))
1176 : break;
1177 395 : if (reg->regno >= dst_hard_regno
1178 372 : && reg->regno < dst_hard_regno + dst_nregs)
1179 : break;
1180 : }
1181 : }
1182 :
1183 3730 : if (reg == NULL)
1184 : {
1185 3730 : *cand_id->operand_loc[cand->nop] = SET_DEST (set);
1186 3730 : lra_update_insn_regno_info (cand->insn);
1187 3730 : bool ok_p = lra_constrain_insn (cand->insn);
1188 3730 : if (ok_p)
1189 : {
1190 2944 : rtx remat_pat = copy_insn (PATTERN (cand->insn));
1191 :
1192 2944 : start_sequence ();
1193 2944 : emit_insn (remat_pat);
1194 2944 : remat_insn = end_sequence ();
1195 2944 : if (recog_memoized (remat_insn) < 0)
1196 0 : remat_insn = NULL;
1197 2944 : cand_sp_offset = cand_id->sp_offset;
1198 : }
1199 3730 : *cand_id->operand_loc[cand->nop] = saved_op;
1200 3730 : lra_update_insn_regno_info (cand->insn);
1201 : }
1202 : }
1203 :
1204 42098124 : bitmap_clear (&temp_bitmap);
1205 : /* Update avail_cands (see analogous code for
1206 : calculate_gen_cands). */
1207 168392496 : for (iter = 0; iter < 2; iter++)
1208 84196248 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
1209 162669674 : reg != NULL;
1210 78473426 : reg = reg->next)
1211 78473426 : if (reg->type != OP_IN
1212 78473426 : || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1213 63853434 : EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1214 : {
1215 2518245 : cand = all_cands[cid];
1216 :
1217 : /* Ignore the reload insn. */
1218 2518245 : if (src_regno == cand->reload_regno
1219 1091393 : && dst_regno == cand->regno)
1220 48212 : continue;
1221 2470033 : if (cand->regno == reg->regno
1222 2470033 : || reg_overlap_for_remat_p (reg, cand->insn))
1223 321371 : bitmap_set_bit (&temp_bitmap, cand->index);
1224 : }
1225 :
1226 42098124 : if (CALL_P (insn))
1227 : {
1228 2507368 : function_abi callee_abi = insn_callee_abi (insn);
1229 2527316 : EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1230 : {
1231 19948 : cand = all_cands[cid];
1232 :
1233 19948 : if (call_used_input_regno_present_p (callee_abi, cand->insn))
1234 0 : bitmap_set_bit (&temp_bitmap, cand->index);
1235 : }
1236 : }
1237 :
1238 42098124 : bitmap_and_compl_into (avail_cands, &temp_bitmap);
1239 :
1240 : /* Now see whether a candidate is made active or available
1241 : by this insn. */
1242 42098124 : cand = insn_to_cand_activation[INSN_UID (insn)];
1243 42098124 : if (cand)
1244 25457 : bitmap_set_bit (active_cands, cand->index);
1245 :
1246 42098124 : cand = insn_to_cand[INSN_UID (insn)];
1247 42098124 : if (cand != NULL)
1248 : {
1249 310434 : bitmap_set_bit (avail_cands, cand->index);
1250 310434 : if (cand->reload_regno == -1)
1251 284982 : bitmap_set_bit (active_cands, cand->index);
1252 : else
1253 25452 : bitmap_clear_bit (active_cands, cand->index);
1254 : }
1255 :
1256 42098124 : if (remat_insn != NULL)
1257 : {
1258 2944 : poly_int64 sp_offset_change = cand_sp_offset - id->sp_offset;
1259 2944 : if (maybe_ne (sp_offset_change, 0))
1260 109 : change_sp_offset (remat_insn, sp_offset_change);
1261 2944 : update_scratch_ops (remat_insn);
1262 2944 : lra_process_new_insns (insn, remat_insn, NULL,
1263 : "Inserting rematerialization insn");
1264 2944 : lra_set_insn_deleted (insn);
1265 2944 : changed_p = true;
1266 2944 : continue;
1267 2944 : }
1268 :
1269 : /* Update live hard regs: */
1270 109924373 : for (reg = id->regs; reg != NULL; reg = reg->next)
1271 67829193 : if (reg->type == OP_IN
1272 67829193 : && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1273 : {
1274 21732066 : if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1275 1316918 : continue;
1276 41171142 : for (i = 0; i < nregs; i++)
1277 20755994 : CLEAR_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1278 : }
1279 : /* Process also hard regs (e.g. CC register) which are part
1280 : of insn definition. */
1281 52733525 : for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1282 10638345 : if (reg->type == OP_IN
1283 10638345 : && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1284 2969141 : CLEAR_HARD_REG_BIT (live_hard_regs, reg->regno);
1285 : /* Inputs have been processed, now process outputs. */
1286 109924373 : for (reg = id->regs; reg != NULL; reg = reg->next)
1287 67829193 : if (reg->type != OP_IN
1288 67829193 : && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1289 : {
1290 28609792 : if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1291 1727616 : continue;
1292 54383472 : for (i = 0; i < nregs; i++)
1293 27501296 : SET_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1294 : }
1295 52733525 : for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1296 10638345 : if (reg->type != OP_IN
1297 10638345 : && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1298 3102492 : SET_HARD_REG_BIT (live_hard_regs, reg->regno);
1299 : }
1300 : }
1301 182566 : return changed_p;
1302 182566 : }
1303 :
1304 :
1305 :
1306 : /* Current number of rematerialization iteration. */
1307 : int lra_rematerialization_iter;
1308 :
1309 : /* Entry point of the rematerialization sub-pass. Return true if we
1310 : did any rematerialization. */
1311 : bool
1312 196911 : lra_remat (void)
1313 : {
1314 196911 : basic_block bb;
1315 196911 : bool result;
1316 196911 : int max_regno = max_reg_num ();
1317 :
1318 196911 : if (! flag_lra_remat)
1319 : return false;
1320 182653 : lra_rematerialization_iter++;
1321 182653 : if (lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
1322 : return false;
1323 182566 : if (lra_dump_file != NULL)
1324 1 : fprintf (lra_dump_file,
1325 : "\n******** Rematerialization #%d: ********\n\n",
1326 : lra_rematerialization_iter);
1327 182566 : timevar_push (TV_LRA_REMAT);
1328 182566 : insn_to_cand = XCNEWVEC (cand_t, get_max_uid ());
1329 182566 : insn_to_cand_activation = XCNEWVEC (cand_t, get_max_uid ());
1330 182566 : regno_cands = XCNEWVEC (cand_t, max_regno);
1331 182566 : all_cands.create (8000);
1332 182566 : initiate_cand_table ();
1333 182566 : create_remat_bb_data ();
1334 182566 : bitmap_initialize (&temp_bitmap, ®_obstack);
1335 182566 : bitmap_initialize (&subreg_regs, ®_obstack);
1336 182566 : calculate_local_reg_remat_bb_data ();
1337 182566 : create_cands ();
1338 182566 : calculate_livein_cands ();
1339 182566 : calculate_gen_cands ();
1340 182566 : bitmap_initialize (&all_blocks, ®_obstack);
1341 6941183 : FOR_ALL_BB_FN (bb, cfun)
1342 6758617 : bitmap_set_bit (&all_blocks, bb->index);
1343 182566 : calculate_global_remat_bb_data ();
1344 182566 : dump_candidates_and_remat_bb_data ();
1345 182566 : result = do_remat ();
1346 182566 : if (result)
1347 1931 : lra_dump_insns_if_possible ("changed func after rematerialization");
1348 182566 : all_cands.release ();
1349 182566 : bitmap_clear (&temp_bitmap);
1350 182566 : bitmap_clear (&subreg_regs);
1351 182566 : finish_remat_bb_data ();
1352 182566 : finish_cand_table ();
1353 182566 : bitmap_clear (&all_blocks);
1354 182566 : free (regno_cands);
1355 182566 : free (insn_to_cand);
1356 182566 : free (insn_to_cand_activation);
1357 182566 : timevar_pop (TV_LRA_REMAT);
1358 182566 : return result;
1359 : }
|
