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 150022535 : get_remat_bb_data (basic_block bb)
157 : {
158 150022535 : return &remat_bb_data[(bb)->index];
159 : }
160 :
161 : static inline remat_bb_data_t
162 27812510 : get_remat_bb_data_by_index (int index)
163 : {
164 27812510 : 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 323109 : cand_hash (const void *cand)
177 : {
178 323109 : const_cand_t c = (const_cand_t) cand;
179 323109 : lra_insn_recog_data_t id = lra_get_insn_recog_data (c->insn);
180 323109 : struct lra_static_insn_data *static_id = id->insn_static_data;
181 323109 : int nops = static_id->n_operands;
182 323109 : hashval_t hash = 0;
183 :
184 980495 : for (int i = 0; i < nops; i++)
185 657386 : if (i == c->nop)
186 323109 : hash = iterative_hash_object (c->regno, hash);
187 334277 : else if (static_id->operand[i].type == OP_IN)
188 334277 : hash = iterative_hash_object (*id->operand_loc[i], hash);
189 323109 : 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 69934 : cand_eq_p (const void *cand1, const void *cand2)
197 : {
198 69934 : const_cand_t c1 = (const_cand_t) cand1;
199 69934 : const_cand_t c2 = (const_cand_t) cand2;
200 69934 : lra_insn_recog_data_t id1 = lra_get_insn_recog_data (c1->insn);
201 69934 : lra_insn_recog_data_t id2 = lra_get_insn_recog_data (c2->insn);
202 69934 : struct lra_static_insn_data *static_id1 = id1->insn_static_data;
203 69934 : int nops = static_id1->n_operands;
204 :
205 69934 : if (c1->regno != c2->regno
206 69508 : || INSN_CODE (c1->insn) < 0
207 69508 : || INSN_CODE (c1->insn) != INSN_CODE (c2->insn))
208 : return false;
209 69506 : gcc_assert (c1->nop == c2->nop);
210 208796 : for (int i = 0; i < nops; i++)
211 139296 : if (i != c1->nop && static_id1->operand[i].type == OP_IN
212 69790 : && *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 323109 : insert_cand (cand_t cand)
221 : {
222 323109 : void **entry_ptr;
223 :
224 323109 : entry_ptr = htab_find_slot (cand_table, cand, INSERT);
225 323109 : if (*entry_ptr == NULL)
226 253609 : *entry_ptr = (void *) cand;
227 323109 : return (cand_t) *entry_ptr;
228 : }
229 :
230 : /* Free candidate CAND memory. */
231 : static void
232 253609 : free_cand (void *cand)
233 : {
234 253609 : free (cand);
235 253609 : }
236 :
237 : /* Initiate the candidate table. */
238 : static void
239 184086 : initiate_cand_table (void)
240 : {
241 184086 : cand_table = htab_create (8000, cand_hash, cand_eq_p,
242 : (htab_del) free_cand);
243 184086 : }
244 :
245 : /* Finish the candidate table. */
246 : static void
247 184086 : 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 53438086 : bad_for_rematerialization_p (rtx x)
262 : {
263 53438086 : int i, j;
264 53438086 : const char *fmt;
265 53438086 : enum rtx_code code;
266 :
267 53438086 : 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 50693957 : code = GET_CODE (x);
274 50693957 : fmt = GET_RTX_FORMAT (code);
275 113650617 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
276 : {
277 66143046 : if (fmt[i] == 'e')
278 : {
279 34582062 : if (bad_for_rematerialization_p (XEXP (x, i)))
280 : return true;
281 : }
282 31560984 : else if (fmt[i] == 'E')
283 : {
284 5927000 : for (j = XVECLEN (x, i) - 1; j >= 0; j--)
285 4253552 : 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 42544251 : operand_to_remat (rtx_insn *insn)
300 : {
301 42544251 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
302 42544251 : struct lra_static_insn_data *static_id = id->insn_static_data;
303 42544251 : struct lra_insn_reg *reg, *found_reg = NULL;
304 :
305 : /* Don't rematerialize insns which can change PC. */
306 42544251 : if (JUMP_P (insn) || CALL_P (insn))
307 : return -1;
308 : /* First find a pseudo which can be rematerialized. */
309 78072727 : 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 57404548 : if (reg->regno == STACK_POINTER_REGNUM && frame_pointer_needed)
316 : return -1;
317 56685886 : else if (reg->type == OP_OUT)
318 : {
319 : /* We permits only one spilled reg. */
320 24126753 : 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 56668237 : if (reg->regno >= FIRST_PSEUDO_REGISTER
330 56668237 : && bitmap_bit_p (&subreg_regs, reg->regno))
331 : return -1;
332 :
333 : /* Don't allow hard registers to be rematerialized. */
334 55704684 : if (reg->regno < FIRST_PSEUDO_REGISTER)
335 : return -1;
336 : }
337 20668179 : if (found_reg == NULL)
338 : return -1;
339 14602472 : if (found_reg->regno < FIRST_PSEUDO_REGISTER)
340 : return -1;
341 14602472 : if (bad_for_rematerialization_p (PATTERN (insn)))
342 : return -1;
343 : /* Check the other regs are not spilled. */
344 25688764 : for (reg = id->regs; reg != NULL; reg = reg->next)
345 22746783 : if (found_reg == reg)
346 11857557 : continue;
347 10889226 : else if (reg->type == OP_INOUT)
348 : return -1;
349 10884928 : else if (reg->regno >= FIRST_PSEUDO_REGISTER
350 10884928 : && reg_renumber[reg->regno] < 0)
351 : /* Another spilled reg. */
352 : return -1;
353 9217710 : else if (reg->type == OP_IN)
354 : {
355 9217710 : 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 1974735 : for (struct lra_insn_reg *reg2 = id->regs;
360 6176157 : reg2 != NULL;
361 4201422 : reg2 = reg2->next)
362 4203293 : if (reg2->type == OP_OUT && reg->regno == reg2->regno)
363 : return -1;
364 1972864 : 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 2941981 : for (struct lra_insn_reg *reg = static_id->hard_regs;
376 3323023 : reg != NULL;
377 381042 : reg = reg->next)
378 381042 : if (reg->type == OP_INOUT)
379 : return -1;
380 381042 : 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 2941981 : int nop = static_id->n_operands;
392 2968250 : for (int i = 0; i < nop; i++)
393 2944740 : if (REG_P (*id->operand_loc[i])
394 2944740 : && (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 323109 : create_cand (rtx_insn *insn, int nop, int regno, rtx_insn *activation = NULL)
404 : {
405 323109 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
406 323109 : rtx reg = *id->operand_loc[nop];
407 323109 : gcc_assert (REG_P (reg));
408 323109 : int op_regno = REGNO (reg);
409 323109 : gcc_assert (op_regno >= FIRST_PSEUDO_REGISTER);
410 323109 : cand_t cand = XNEW (struct cand);
411 323109 : cand->insn = insn;
412 323109 : cand->nop = nop;
413 323109 : cand->regno = regno;
414 323109 : cand->reload_regno = op_regno == regno ? -1 : op_regno;
415 323109 : gcc_assert (cand->regno >= 0);
416 323109 : cand_t cand_in_table = insert_cand (cand);
417 323109 : insn_to_cand[INSN_UID (insn)] = cand_in_table;
418 323109 : if (cand != cand_in_table)
419 69500 : free (cand);
420 : else
421 : {
422 : /* A new cand. */
423 253609 : cand->index = all_cands.length ();
424 253609 : all_cands.safe_push (cand);
425 253609 : cand->next_regno_cand = regno_cands[cand->regno];
426 253609 : regno_cands[cand->regno] = cand;
427 : }
428 323109 : if (activation)
429 23945 : insn_to_cand_activation[INSN_UID (activation)] = cand_in_table;
430 323109 : }
431 :
432 : /* Create rematerialization candidates (inserting them into the
433 : table). */
434 : static void
435 184086 : create_cands (void)
436 : {
437 184086 : rtx_insn *insn;
438 184086 : struct potential_cand
439 : {
440 : rtx_insn *insn;
441 : int nop;
442 : };
443 184086 : struct potential_cand *regno_potential_cand;
444 :
445 : /* Create candidates. */
446 184086 : regno_potential_cand = XCNEWVEC (struct potential_cand, max_reg_num ());
447 95580904 : for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
448 95396818 : if (NONDEBUG_INSN_P (insn))
449 : {
450 42568196 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
451 42568196 : int keep_regno = -1;
452 42568196 : rtx set = single_set (insn);
453 42568196 : int nop;
454 :
455 : /* See if this is an output reload for a previous insn. */
456 42568196 : if (set != NULL
457 40748051 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
458 : {
459 12199898 : rtx dstreg = SET_DEST (set);
460 12199898 : int src_regno = REGNO (SET_SRC (set));
461 12199898 : int dst_regno = REGNO (dstreg);
462 12199898 : rtx_insn *insn2 = regno_potential_cand[src_regno].insn;
463 :
464 12199898 : if (insn2 != NULL
465 12199898 : && dst_regno >= FIRST_PSEUDO_REGISTER
466 88511 : && reg_renumber[dst_regno] < 0
467 24096 : && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn)
468 12223994 : && insn2 == prev_nonnote_nondebug_insn (insn))
469 : {
470 23945 : create_cand (insn2, regno_potential_cand[src_regno].nop,
471 : dst_regno, insn);
472 23945 : goto done;
473 : }
474 : }
475 :
476 42544251 : nop = operand_to_remat (insn);
477 42544251 : if (nop >= 0)
478 : {
479 2918471 : gcc_assert (REG_P (*id->operand_loc[nop]));
480 2918471 : int regno = REGNO (*id->operand_loc[nop]);
481 2918471 : 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 2918471 : if (reg_renumber[regno] < 0)
487 299164 : create_cand (insn, nop, regno);
488 2619307 : else if (regno >= lra_constraint_new_regno_start)
489 : {
490 887509 : regno_potential_cand[regno].insn = insn;
491 887509 : regno_potential_cand[regno].nop = nop;
492 887509 : keep_regno = regno;
493 : }
494 : }
495 :
496 39625780 : done:
497 111195844 : for (struct lra_insn_reg *reg = id->regs; reg != NULL; reg = reg->next)
498 68627648 : if (reg->type != OP_IN && reg->regno != keep_regno
499 28523918 : && reg->regno >= FIRST_PSEUDO_REGISTER)
500 20448100 : regno_potential_cand[reg->regno].insn = NULL;
501 : }
502 184086 : cands_num = all_cands.length ();
503 184086 : free (regno_potential_cand);
504 184086 : }
505 :
506 :
507 :
508 : /* Create and initialize BB data. */
509 : static void
510 184086 : create_remat_bb_data (void)
511 : {
512 184086 : basic_block bb;
513 184086 : remat_bb_data_t bb_info;
514 :
515 184086 : remat_bb_data = XNEWVEC (class remat_bb_data,
516 : last_basic_block_for_fn (cfun));
517 7031324 : FOR_ALL_BB_FN (bb, cfun)
518 : {
519 6847238 : gcc_checking_assert (bb->index >= 0
520 : && bb->index < last_basic_block_for_fn (cfun));
521 6847238 : bb_info = get_remat_bb_data (bb);
522 6847238 : bb_info->bb = bb;
523 6847238 : bitmap_initialize (&bb_info->changed_regs, ®_obstack);
524 6847238 : bitmap_initialize (&bb_info->dead_regs, ®_obstack);
525 6847238 : bitmap_initialize (&bb_info->gen_cands, ®_obstack);
526 6847238 : bitmap_initialize (&bb_info->livein_cands, ®_obstack);
527 6847238 : bitmap_initialize (&bb_info->pavin_cands, ®_obstack);
528 6847238 : bitmap_initialize (&bb_info->pavout_cands, ®_obstack);
529 6847238 : bitmap_initialize (&bb_info->avin_cands, ®_obstack);
530 6847238 : bitmap_initialize (&bb_info->avout_cands, ®_obstack);
531 : }
532 184086 : }
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 184086 : dump_candidates_and_remat_bb_data (void)
555 : {
556 184086 : basic_block bb;
557 :
558 184086 : 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 184086 : finish_remat_bb_data (void)
600 : {
601 184086 : basic_block bb;
602 :
603 6663152 : FOR_EACH_BB_FN (bb, cfun)
604 : {
605 6479066 : bitmap_clear (&get_remat_bb_data (bb)->avout_cands);
606 6479066 : bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
607 6479066 : bitmap_clear (&get_remat_bb_data (bb)->pavout_cands);
608 6479066 : bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
609 6479066 : bitmap_clear (&get_remat_bb_data (bb)->livein_cands);
610 6479066 : bitmap_clear (&get_remat_bb_data (bb)->gen_cands);
611 6479066 : bitmap_clear (&get_remat_bb_data (bb)->dead_regs);
612 6479066 : bitmap_clear (&get_remat_bb_data (bb)->changed_regs);
613 : }
614 184086 : free (remat_bb_data);
615 184086 : }
616 :
617 :
618 :
619 : /* Update changed_regs, dead_regs, subreg_regs of BB from INSN. */
620 : static void
621 42568196 : set_bb_regs (basic_block bb, rtx_insn *insn)
622 : {
623 42568196 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
624 42568196 : remat_bb_data_t bb_info = get_remat_bb_data (bb);
625 42568196 : struct lra_insn_reg *reg;
626 :
627 111195844 : for (reg = id->regs; reg != NULL; reg = reg->next)
628 : {
629 68627648 : unsigned regno = reg->regno;
630 68627648 : if (reg->type != OP_IN)
631 29411427 : bitmap_set_bit (&bb_info->changed_regs, regno);
632 39216221 : else if (find_regno_note (insn, REG_DEAD, regno) != NULL)
633 22043271 : bitmap_set_bit (&bb_info->dead_regs, regno);
634 68627648 : if (regno >= FIRST_PSEUDO_REGISTER && reg->subreg_p)
635 536926 : bitmap_set_bit (&subreg_regs, regno);
636 : }
637 42568196 : if (CALL_P (insn))
638 : {
639 : /* Partially-clobbered registers might still be live. */
640 2512395 : HARD_REG_SET clobbers = insn_callee_abi (insn).full_reg_clobbers ();
641 2512395 : bitmap_ior_into (&get_remat_bb_data (bb)->dead_regs,
642 2512395 : bitmap_view<HARD_REG_SET> (clobbers));
643 : }
644 42568196 : }
645 :
646 : /* Calculate changed_regs and dead_regs for each BB. */
647 : static void
648 184086 : calculate_local_reg_remat_bb_data (void)
649 : {
650 184086 : basic_block bb;
651 184086 : rtx_insn *insn;
652 :
653 6663152 : FOR_EACH_BB_FN (bb, cfun)
654 99633419 : FOR_BB_INSNS (bb, insn)
655 93154353 : if (NONDEBUG_INSN_P (insn))
656 42568196 : set_bb_regs (bb, insn);
657 184086 : }
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 4428014 : reg_overlap_for_remat_p (lra_insn_reg *reg, rtx_insn *insn)
668 : {
669 4428014 : int iter;
670 4428014 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
671 4428014 : struct lra_static_insn_data *static_id = id->insn_static_data;
672 4428014 : unsigned regno = reg->regno;
673 4428014 : int nregs;
674 :
675 4428014 : if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] >= 0)
676 3109121 : regno = reg_renumber[regno];
677 3726118 : if (regno >= FIRST_PSEUDO_REGISTER)
678 : nregs = 1;
679 : else
680 3811017 : nregs = hard_regno_nregs (regno, reg->biggest_mode);
681 :
682 4428014 : struct lra_insn_reg *reg2;
683 :
684 12135426 : for (iter = 0; iter < 2; iter++)
685 8287749 : for (reg2 = (iter == 0 ? id->regs : static_id->hard_regs);
686 15188477 : reg2 != NULL;
687 6900728 : reg2 = reg2->next)
688 : {
689 7481065 : int nregs2;
690 7481065 : unsigned regno2 = reg2->regno;
691 :
692 7481065 : if (reg2->type != OP_IN && regno2 >= FIRST_PSEUDO_REGISTER)
693 4428014 : continue;
694 :
695 2971171 : if (regno2 >= FIRST_PSEUDO_REGISTER && reg_renumber[regno2] >= 0)
696 2971171 : regno2 = reg_renumber[regno2];
697 2971171 : if (regno2 >= FIRST_PSEUDO_REGISTER)
698 : nregs2 = 1;
699 : else
700 3053051 : nregs2 = hard_regno_nregs (regno2, reg->biggest_mode);
701 :
702 3053051 : if ((regno2 + nregs2 - 1 >= regno && regno2 < regno + nregs)
703 2472714 : || (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 28572 : call_used_input_regno_present_p (const function_abi &abi, rtx_insn *insn)
712 : {
713 28572 : int iter;
714 28572 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
715 28572 : struct lra_static_insn_data *static_id = id->insn_static_data;
716 28572 : struct lra_insn_reg *reg;
717 :
718 85716 : for (iter = 0; iter < 2; iter++)
719 57144 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
720 111116 : reg != NULL;
721 53972 : reg = reg->next)
722 53972 : if (reg->type == OP_IN
723 23818 : && reg->regno < FIRST_PSEUDO_REGISTER
724 53972 : && 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 184086 : calculate_livein_cands (void)
732 : {
733 184086 : basic_block bb;
734 :
735 6663152 : FOR_EACH_BB_FN (bb, cfun)
736 : {
737 6479066 : bitmap livein_regs = df_get_live_in (bb);
738 6479066 : bitmap livein_cands = &get_remat_bb_data (bb)->livein_cands;
739 60135835 : for (unsigned int i = 0; i < cands_num; i++)
740 : {
741 53656769 : cand_t cand = all_cands[i];
742 53656769 : lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
743 53656769 : struct lra_insn_reg *reg;
744 :
745 108142627 : for (reg = id->regs; reg != NULL; reg = reg->next)
746 90608466 : if (reg->type == OP_IN && ! bitmap_bit_p (livein_regs, reg->regno))
747 : break;
748 53656769 : if (reg == NULL)
749 17534161 : bitmap_set_bit (livein_cands, i);
750 : }
751 : }
752 184086 : }
753 :
754 : /* Calculate gen_cands for each BB. */
755 : static void
756 184086 : calculate_gen_cands (void)
757 : {
758 184086 : basic_block bb;
759 184086 : bitmap gen_cands;
760 184086 : rtx_insn *insn;
761 :
762 6663152 : FOR_EACH_BB_FN (bb, cfun)
763 : {
764 6479066 : gen_cands = &get_remat_bb_data (bb)->gen_cands;
765 6479066 : auto_bitmap gen_insns (®_obstack);
766 99633419 : FOR_BB_INSNS (bb, insn)
767 93154353 : if (INSN_P (insn))
768 : {
769 79758604 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
770 79758604 : struct lra_static_insn_data *static_id = id->insn_static_data;
771 79758604 : struct lra_insn_reg *reg;
772 79758604 : unsigned int uid;
773 79758604 : bitmap_iterator bi;
774 79758604 : cand_t cand;
775 79758604 : rtx set;
776 79758604 : int iter;
777 79758604 : int src_regno = -1, dst_regno = -1;
778 :
779 79758604 : if ((set = single_set (insn)) != NULL
780 79758604 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
781 : {
782 12199898 : src_regno = REGNO (SET_SRC (set));
783 12199898 : dst_regno = REGNO (SET_DEST (set));
784 : }
785 :
786 : /* Update gen_cands: */
787 79758604 : bitmap_clear (&temp_bitmap);
788 239275812 : for (iter = 0; iter < 2; iter++)
789 159517208 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
790 247035100 : reg != NULL;
791 87517892 : reg = reg->next)
792 87517892 : if (reg->type != OP_IN
793 87517892 : || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
794 64133600 : EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
795 : {
796 1984348 : rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
797 :
798 1984348 : cand = insn_to_cand[INSN_UID (insn2)];
799 1984348 : gcc_assert (cand != NULL);
800 : /* Ignore the reload insn. */
801 1984348 : if (src_regno == cand->reload_regno
802 812687 : && dst_regno == cand->regno)
803 45309 : continue;
804 1939039 : if (cand->regno == reg->regno
805 1939039 : || reg_overlap_for_remat_p (reg, insn2))
806 : {
807 274175 : bitmap_clear_bit (gen_cands, cand->index);
808 274175 : bitmap_set_bit (&temp_bitmap, uid);
809 : }
810 : }
811 :
812 79758604 : if (CALL_P (insn))
813 : {
814 2512395 : function_abi callee_abi = insn_callee_abi (insn);
815 2521281 : EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
816 : {
817 8886 : rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
818 :
819 8886 : cand = insn_to_cand[INSN_UID (insn2)];
820 8886 : gcc_assert (cand != NULL);
821 8886 : 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 79758604 : bitmap_and_compl_into (gen_insns, &temp_bitmap);
829 :
830 79758604 : cand = insn_to_cand[INSN_UID (insn)];
831 79758604 : if (cand != NULL)
832 : {
833 323109 : bitmap_set_bit (gen_cands, cand->index);
834 323109 : bitmap_set_bit (gen_insns, INSN_UID (insn));
835 : }
836 : }
837 6479066 : }
838 184086 : }
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 13906255 : cand_trans_fun (int bb_index, bitmap bb_in, bitmap bb_out)
850 : {
851 13906255 : remat_bb_data_t bb_info;
852 13906255 : bitmap bb_livein, bb_changed_regs, bb_dead_regs;
853 13906255 : unsigned int cid;
854 13906255 : bitmap_iterator bi;
855 :
856 13906255 : bb_info = get_remat_bb_data_by_index (bb_index);
857 13906255 : bb_livein = &bb_info->livein_cands;
858 13906255 : bb_changed_regs = &bb_info->changed_regs;
859 13906255 : 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 13906255 : bitmap_clear (&temp_bitmap);
865 22353506 : EXECUTE_IF_SET_IN_BITMAP (bb_in, 0, cid, bi)
866 : {
867 8447251 : cand_t cand = all_cands[cid];
868 8447251 : lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
869 8447251 : struct lra_insn_reg *reg;
870 :
871 8447251 : if (! bitmap_bit_p (bb_livein, cid))
872 : {
873 100673 : bitmap_set_bit (&temp_bitmap, cid);
874 100673 : continue;
875 : }
876 16801530 : for (reg = id->regs; reg != NULL; reg = reg->next)
877 : /* Ignore all outputs which are not the regno for
878 : rematerialization. */
879 8662723 : if (reg->type == OP_OUT && reg->regno != cand->regno)
880 534069 : continue;
881 8128654 : else if (bitmap_bit_p (bb_changed_regs, reg->regno)
882 8128654 : || bitmap_bit_p (bb_dead_regs, reg->regno))
883 : {
884 207771 : bitmap_set_bit (&temp_bitmap, cid);
885 207771 : break;
886 : }
887 : /* Check regno for rematerialization. */
888 8346578 : if (bitmap_bit_p (bb_changed_regs, cand->regno)
889 8346578 : || bitmap_bit_p (bb_dead_regs, cand->regno))
890 166820 : bitmap_set_bit (&temp_bitmap, cid);
891 : }
892 13906255 : return bitmap_ior_and_compl (bb_out,
893 13906255 : &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 7059017 : cand_pav_trans_fun (int bb_index)
906 : {
907 7059017 : remat_bb_data_t bb_info;
908 :
909 7059017 : bb_info = get_remat_bb_data_by_index (bb_index);
910 7059017 : return cand_trans_fun (bb_index, &bb_info->pavin_cands,
911 7059017 : &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 185306 : cand_pav_con_fun_0 (basic_block bb)
918 : {
919 185306 : bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
920 185306 : }
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 10185389 : cand_pav_con_fun_n (edge e)
930 : {
931 10185389 : basic_block pred = e->src;
932 10185389 : basic_block bb = e->dest;
933 10185389 : remat_bb_data_t bb_info;
934 10185389 : bitmap bb_pavin, pred_pavout;
935 :
936 10185389 : bb_info = get_remat_bb_data (bb);
937 10185389 : bb_pavin = &bb_info->pavin_cands;
938 10185389 : pred_pavout = &get_remat_bb_data (pred)->pavout_cands;
939 10185389 : 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 6847238 : cand_av_trans_fun (int bb_index)
952 : {
953 6847238 : remat_bb_data_t bb_info;
954 :
955 6847238 : bb_info = get_remat_bb_data_by_index (bb_index);
956 6847238 : return cand_trans_fun (bb_index, &bb_info->avin_cands,
957 6847238 : &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 185306 : cand_av_con_fun_0 (basic_block bb)
964 : {
965 185306 : bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
966 185306 : }
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 9789577 : cand_av_con_fun_n (edge e)
976 : {
977 9789577 : basic_block pred = e->src;
978 9789577 : basic_block bb = e->dest;
979 9789577 : remat_bb_data_t bb_info;
980 9789577 : bitmap bb_avin, pred_avout;
981 :
982 9789577 : bb_info = get_remat_bb_data (bb);
983 9789577 : bb_avin = &bb_info->avin_cands;
984 9789577 : pred_avout = &get_remat_bb_data (pred)->avout_cands;
985 9789577 : return bitmap_and_into (bb_avin, pred_avout);
986 : }
987 :
988 : /* Calculate available candidates for each BB. */
989 : static void
990 184086 : calculate_global_remat_bb_data (void)
991 : {
992 184086 : basic_block bb;
993 :
994 184086 : df_simple_dataflow
995 184086 : (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 6663152 : FOR_EACH_BB_FN (bb, cfun)
1000 6479066 : bitmap_copy (&get_remat_bb_data (bb)->avin_cands,
1001 6479066 : &get_remat_bb_data (bb)->pavin_cands);
1002 184086 : df_simple_dataflow
1003 184086 : (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 184086 : }
1007 :
1008 :
1009 :
1010 : /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
1011 : static void
1012 74 : change_sp_offset (rtx_insn *insns, poly_int64 sp_offset)
1013 : {
1014 148 : for (rtx_insn *insn = insns; insn != NULL; insn = NEXT_INSN (insn))
1015 74 : eliminate_regs_in_insn (insn, false, false, sp_offset);
1016 74 : }
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 51007049 : get_hard_regs (struct lra_insn_reg *reg, int &nregs)
1024 : {
1025 51007049 : int regno = reg->regno;
1026 51007049 : int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
1027 :
1028 51007049 : if (hard_regno >= 0)
1029 47919515 : nregs = hard_regno_nregs (hard_regno, reg->biggest_mode);
1030 51007049 : return hard_regno;
1031 : }
1032 :
1033 : /* Make copy of and register scratch pseudos in rematerialized insn
1034 : REMAT_INSN. */
1035 : static void
1036 2605 : update_scratch_ops (rtx_insn *remat_insn)
1037 : {
1038 2605 : lra_insn_recog_data_t id = lra_get_insn_recog_data (remat_insn);
1039 2605 : struct lra_static_insn_data *static_id = id->insn_static_data;
1040 8482 : for (int i = 0; i < static_id->n_operands; i++)
1041 : {
1042 5877 : rtx *loc = id->operand_loc[i];
1043 5877 : if (! REG_P (*loc))
1044 2180 : continue;
1045 3697 : int regno = REGNO (*loc);
1046 3697 : if (! ira_former_scratch_p (regno))
1047 3697 : 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 2605 : }
1055 :
1056 : /* Insert rematerialization insns using the data-flow data calculated
1057 : earlier. */
1058 : static bool
1059 184086 : do_remat (void)
1060 : {
1061 184086 : unsigned regno;
1062 184086 : rtx_insn *insn;
1063 184086 : basic_block bb;
1064 184086 : bool changed_p = false;
1065 : /* Living hard regs and hard registers of living pseudos. */
1066 184086 : HARD_REG_SET live_hard_regs;
1067 184086 : bitmap_iterator bi;
1068 :
1069 184086 : auto_bitmap avail_cands (®_obstack);
1070 184086 : auto_bitmap active_cands (®_obstack);
1071 6663152 : FOR_EACH_BB_FN (bb, cfun)
1072 : {
1073 6479066 : CLEAR_HARD_REG_SET (live_hard_regs);
1074 67588446 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), 0, regno, bi)
1075 : {
1076 8628515 : int hard_regno = regno < FIRST_PSEUDO_REGISTER
1077 61109380 : ? regno
1078 52480865 : : reg_renumber[regno];
1079 61109380 : if (hard_regno >= 0)
1080 34925947 : SET_HARD_REG_BIT (live_hard_regs, hard_regno);
1081 : }
1082 6479066 : bitmap_and (avail_cands, &get_remat_bb_data (bb)->avin_cands,
1083 6479066 : &get_remat_bb_data (bb)->livein_cands);
1084 : /* Activating insns are always in the same block as their corresponding
1085 : remat insn, so at the start of a block the two bitsets are equal. */
1086 6479066 : bitmap_copy (active_cands, avail_cands);
1087 99633419 : FOR_BB_INSNS (bb, insn)
1088 : {
1089 93154353 : if (!NONDEBUG_INSN_P (insn))
1090 50588762 : continue;
1091 :
1092 42568196 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
1093 42568196 : struct lra_static_insn_data *static_id = id->insn_static_data;
1094 42568196 : struct lra_insn_reg *reg;
1095 42568196 : cand_t cand;
1096 42568196 : unsigned int cid;
1097 42568196 : bitmap_iterator bi;
1098 42568196 : rtx set;
1099 42568196 : int iter;
1100 42568196 : int src_regno = -1, dst_regno = -1;
1101 :
1102 42568196 : if ((set = single_set (insn)) != NULL
1103 42568196 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
1104 : {
1105 12199898 : src_regno = REGNO (SET_SRC (set));
1106 12199898 : dst_regno = REGNO (SET_DEST (set));
1107 : }
1108 :
1109 42568196 : cand = NULL;
1110 : /* Check possibility of rematerialization (hard reg or
1111 : unpsilled pseudo <- spilled pseudo): */
1112 42568196 : if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER
1113 10772715 : && reg_renumber[src_regno] < 0
1114 1810947 : && (dst_regno < FIRST_PSEUDO_REGISTER
1115 1649837 : || reg_renumber[dst_regno] >= 0))
1116 : {
1117 1810941 : for (cand = regno_cands[src_regno];
1118 2412106 : cand != NULL;
1119 601165 : cand = cand->next_regno_cand)
1120 604525 : if (bitmap_bit_p (avail_cands, cand->index)
1121 604525 : && bitmap_bit_p (active_cands, cand->index))
1122 : break;
1123 : }
1124 1810941 : int i, hard_regno, nregs;
1125 1810941 : int dst_hard_regno, dst_nregs;
1126 1810941 : rtx_insn *remat_insn = NULL;
1127 1810941 : poly_int64 cand_sp_offset = 0;
1128 1810941 : if (cand != NULL)
1129 : {
1130 3360 : lra_insn_recog_data_t cand_id
1131 3360 : = lra_get_insn_recog_data (cand->insn);
1132 3360 : struct lra_static_insn_data *static_cand_id
1133 : = cand_id->insn_static_data;
1134 3360 : rtx saved_op = *cand_id->operand_loc[cand->nop];
1135 :
1136 : /* Check clobbers do not kill something living. */
1137 3360 : gcc_assert (REG_P (saved_op));
1138 3360 : int ignore_regno = REGNO (saved_op);
1139 :
1140 6465 : dst_hard_regno = dst_regno < FIRST_PSEUDO_REGISTER
1141 3360 : ? dst_regno : reg_renumber[dst_regno];
1142 3360 : gcc_assert (dst_hard_regno >= 0);
1143 3360 : machine_mode mode = GET_MODE (SET_DEST (set));
1144 3360 : dst_nregs = hard_regno_nregs (dst_hard_regno, mode);
1145 :
1146 8840 : for (reg = cand_id->regs; reg != NULL; reg = reg->next)
1147 5480 : if (reg->type != OP_IN && reg->regno != ignore_regno)
1148 : {
1149 0 : hard_regno = get_hard_regs (reg, nregs);
1150 0 : gcc_assert (hard_regno >= 0);
1151 0 : for (i = 0; i < nregs; i++)
1152 0 : if (TEST_HARD_REG_BIT (live_hard_regs, hard_regno + i))
1153 : break;
1154 0 : if (i < nregs)
1155 : break;
1156 : /* Ensure the clobber also doesn't overlap dst_regno. */
1157 0 : if (hard_regno + nregs > dst_hard_regno
1158 0 : && hard_regno < dst_hard_regno + dst_nregs)
1159 : break;
1160 : }
1161 :
1162 3360 : if (reg == NULL)
1163 : {
1164 3360 : for (reg = static_cand_id->hard_regs;
1165 3752 : reg != NULL;
1166 392 : reg = reg->next)
1167 392 : if (reg->type != OP_IN)
1168 : {
1169 392 : if (TEST_HARD_REG_BIT (live_hard_regs, reg->regno))
1170 : break;
1171 392 : if (reg->regno >= dst_hard_regno
1172 371 : && reg->regno < dst_hard_regno + dst_nregs)
1173 : break;
1174 : }
1175 : }
1176 :
1177 3360 : if (reg == NULL)
1178 : {
1179 3360 : *cand_id->operand_loc[cand->nop] = SET_DEST (set);
1180 3360 : lra_update_insn_regno_info (cand->insn);
1181 3360 : bool ok_p = lra_constrain_insn (cand->insn);
1182 3360 : if (ok_p)
1183 : {
1184 2605 : rtx remat_pat = copy_insn (PATTERN (cand->insn));
1185 :
1186 2605 : start_sequence ();
1187 2605 : emit_insn (remat_pat);
1188 2605 : remat_insn = end_sequence ();
1189 2605 : if (recog_memoized (remat_insn) < 0)
1190 0 : remat_insn = NULL;
1191 2605 : cand_sp_offset = cand_id->sp_offset;
1192 : }
1193 3360 : *cand_id->operand_loc[cand->nop] = saved_op;
1194 3360 : lra_update_insn_regno_info (cand->insn);
1195 : }
1196 : }
1197 :
1198 42568196 : bitmap_clear (&temp_bitmap);
1199 : /* Update avail_cands (see analogous code for
1200 : calculate_gen_cands). */
1201 170272784 : for (iter = 0; iter < 2; iter++)
1202 85136392 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
1203 164558348 : reg != NULL;
1204 79421956 : reg = reg->next)
1205 79421956 : if (reg->type != OP_IN
1206 79421956 : || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1207 64697510 : EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1208 : {
1209 2548258 : cand = all_cands[cid];
1210 :
1211 : /* Ignore the reload insn. */
1212 2548258 : if (src_regno == cand->reload_regno
1213 1106098 : && dst_regno == cand->regno)
1214 45309 : continue;
1215 2502949 : if (cand->regno == reg->regno
1216 2502949 : || reg_overlap_for_remat_p (reg, cand->insn))
1217 320136 : bitmap_set_bit (&temp_bitmap, cand->index);
1218 : }
1219 :
1220 42568196 : if (CALL_P (insn))
1221 : {
1222 2512395 : function_abi callee_abi = insn_callee_abi (insn);
1223 2532081 : EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1224 : {
1225 19686 : cand = all_cands[cid];
1226 :
1227 19686 : if (call_used_input_regno_present_p (callee_abi, cand->insn))
1228 0 : bitmap_set_bit (&temp_bitmap, cand->index);
1229 : }
1230 : }
1231 :
1232 42568196 : bitmap_and_compl_into (avail_cands, &temp_bitmap);
1233 :
1234 : /* Now see whether a candidate is made active or available
1235 : by this insn. */
1236 42568196 : cand = insn_to_cand_activation[INSN_UID (insn)];
1237 42568196 : if (cand)
1238 23945 : bitmap_set_bit (active_cands, cand->index);
1239 :
1240 42568196 : cand = insn_to_cand[INSN_UID (insn)];
1241 42568196 : if (cand != NULL)
1242 : {
1243 323109 : bitmap_set_bit (avail_cands, cand->index);
1244 323109 : if (cand->reload_regno == -1)
1245 299175 : bitmap_set_bit (active_cands, cand->index);
1246 : else
1247 23934 : bitmap_clear_bit (active_cands, cand->index);
1248 : }
1249 :
1250 42568196 : if (remat_insn != NULL)
1251 : {
1252 2605 : poly_int64 sp_offset_change = cand_sp_offset - id->sp_offset;
1253 2605 : if (maybe_ne (sp_offset_change, 0))
1254 74 : change_sp_offset (remat_insn, sp_offset_change);
1255 2605 : update_scratch_ops (remat_insn);
1256 2605 : lra_process_new_insns (insn, remat_insn, NULL,
1257 : "Inserting rematerialization insn");
1258 2605 : lra_set_insn_deleted (insn);
1259 2605 : changed_p = true;
1260 2605 : continue;
1261 2605 : }
1262 :
1263 : /* Update live hard regs: */
1264 111188029 : for (reg = id->regs; reg != NULL; reg = reg->next)
1265 68622438 : if (reg->type == OP_IN
1266 68622438 : && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1267 : {
1268 22041135 : if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1269 1336258 : continue;
1270 41757327 : for (i = 0; i < nregs; i++)
1271 21052450 : CLEAR_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1272 : }
1273 : /* Process also hard regs (e.g. CC register) which are part
1274 : of insn definition. */
1275 53359899 : for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1276 10794308 : if (reg->type == OP_IN
1277 10794308 : && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1278 3010213 : CLEAR_HARD_REG_BIT (live_hard_regs, reg->regno);
1279 : /* Inputs have been processed, now process outputs. */
1280 111188029 : for (reg = id->regs; reg != NULL; reg = reg->next)
1281 68622438 : if (reg->type != OP_IN
1282 68622438 : && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1283 : {
1284 28965914 : if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1285 1751276 : continue;
1286 55057823 : for (i = 0; i < nregs; i++)
1287 27843185 : SET_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1288 : }
1289 53359899 : for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1290 10794308 : if (reg->type != OP_IN
1291 10794308 : && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1292 3145121 : SET_HARD_REG_BIT (live_hard_regs, reg->regno);
1293 : }
1294 : }
1295 184086 : return changed_p;
1296 184086 : }
1297 :
1298 :
1299 :
1300 : /* Current number of rematerialization iteration. */
1301 : int lra_rematerialization_iter;
1302 :
1303 : /* Entry point of the rematerialization sub-pass. Return true if we
1304 : did any rematerialization. */
1305 : bool
1306 198257 : lra_remat (void)
1307 : {
1308 198257 : basic_block bb;
1309 198257 : bool result;
1310 198257 : int max_regno = max_reg_num ();
1311 :
1312 198257 : if (! flag_lra_remat)
1313 : return false;
1314 184173 : lra_rematerialization_iter++;
1315 184173 : if (lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
1316 : return false;
1317 184086 : if (lra_dump_file != NULL)
1318 1 : fprintf (lra_dump_file,
1319 : "\n******** Rematerialization #%d: ********\n\n",
1320 : lra_rematerialization_iter);
1321 184086 : timevar_push (TV_LRA_REMAT);
1322 184086 : insn_to_cand = XCNEWVEC (cand_t, get_max_uid ());
1323 184086 : insn_to_cand_activation = XCNEWVEC (cand_t, get_max_uid ());
1324 184086 : regno_cands = XCNEWVEC (cand_t, max_regno);
1325 184086 : all_cands.create (8000);
1326 184086 : initiate_cand_table ();
1327 184086 : create_remat_bb_data ();
1328 184086 : bitmap_initialize (&temp_bitmap, ®_obstack);
1329 184086 : bitmap_initialize (&subreg_regs, ®_obstack);
1330 184086 : calculate_local_reg_remat_bb_data ();
1331 184086 : create_cands ();
1332 184086 : calculate_livein_cands ();
1333 184086 : calculate_gen_cands ();
1334 184086 : bitmap_initialize (&all_blocks, ®_obstack);
1335 7031324 : FOR_ALL_BB_FN (bb, cfun)
1336 6847238 : bitmap_set_bit (&all_blocks, bb->index);
1337 184086 : calculate_global_remat_bb_data ();
1338 184086 : dump_candidates_and_remat_bb_data ();
1339 184086 : result = do_remat ();
1340 184086 : if (result)
1341 1839 : lra_dump_insns_if_possible ("changed func after rematerialization");
1342 184086 : all_cands.release ();
1343 184086 : bitmap_clear (&temp_bitmap);
1344 184086 : bitmap_clear (&subreg_regs);
1345 184086 : finish_remat_bb_data ();
1346 184086 : finish_cand_table ();
1347 184086 : bitmap_clear (&all_blocks);
1348 184086 : free (regno_cands);
1349 184086 : free (insn_to_cand);
1350 184086 : free (insn_to_cand_activation);
1351 184086 : timevar_pop (TV_LRA_REMAT);
1352 184086 : return result;
1353 : }
|
