Branch data 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 : 150925268 : get_remat_bb_data (basic_block bb)
157 : : {
158 : 150925268 : return &remat_bb_data[(bb)->index];
159 : : }
160 : :
161 : : static inline remat_bb_data_t
162 : 27993422 : get_remat_bb_data_by_index (int index)
163 : : {
164 : 27993422 : 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 : 325138 : cand_hash (const void *cand)
177 : : {
178 : 325138 : const_cand_t c = (const_cand_t) cand;
179 : 325138 : lra_insn_recog_data_t id = lra_get_insn_recog_data (c->insn);
180 : 325138 : struct lra_static_insn_data *static_id = id->insn_static_data;
181 : 325138 : int nops = static_id->n_operands;
182 : 325138 : hashval_t hash = 0;
183 : :
184 : 986606 : for (int i = 0; i < nops; i++)
185 : 661468 : if (i == c->nop)
186 : 325138 : hash = iterative_hash_object (c->regno, hash);
187 : 336330 : else if (static_id->operand[i].type == OP_IN)
188 : 336330 : hash = iterative_hash_object (*id->operand_loc[i], hash);
189 : 325138 : 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 : 70994 : cand_eq_p (const void *cand1, const void *cand2)
197 : : {
198 : 70994 : const_cand_t c1 = (const_cand_t) cand1;
199 : 70994 : const_cand_t c2 = (const_cand_t) cand2;
200 : 70994 : lra_insn_recog_data_t id1 = lra_get_insn_recog_data (c1->insn);
201 : 70994 : lra_insn_recog_data_t id2 = lra_get_insn_recog_data (c2->insn);
202 : 70994 : struct lra_static_insn_data *static_id1 = id1->insn_static_data;
203 : 70994 : int nops = static_id1->n_operands;
204 : :
205 : 70994 : if (c1->regno != c2->regno
206 : 70619 : || INSN_CODE (c1->insn) < 0
207 : 70619 : || INSN_CODE (c1->insn) != INSN_CODE (c2->insn))
208 : : return false;
209 : 70618 : gcc_assert (c1->nop == c2->nop);
210 : 212124 : for (int i = 0; i < nops; i++)
211 : 141524 : if (i != c1->nop && static_id1->operand[i].type == OP_IN
212 : 70906 : && *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 : 325138 : insert_cand (cand_t cand)
221 : : {
222 : 325138 : void **entry_ptr;
223 : :
224 : 325138 : entry_ptr = htab_find_slot (cand_table, cand, INSERT);
225 : 325138 : if (*entry_ptr == NULL)
226 : 254538 : *entry_ptr = (void *) cand;
227 : 325138 : return (cand_t) *entry_ptr;
228 : : }
229 : :
230 : : /* Free candidate CAND memory. */
231 : : static void
232 : 254538 : free_cand (void *cand)
233 : : {
234 : 254538 : free (cand);
235 : 254538 : }
236 : :
237 : : /* Initiate the candidate table. */
238 : : static void
239 : 184574 : initiate_cand_table (void)
240 : : {
241 : 184574 : cand_table = htab_create (8000, cand_hash, cand_eq_p,
242 : : (htab_del) free_cand);
243 : 184574 : }
244 : :
245 : : /* Finish the candidate table. */
246 : : static void
247 : 184574 : 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 : 53614268 : bad_for_rematerialization_p (rtx x)
262 : : {
263 : 53614268 : int i, j;
264 : 53614268 : const char *fmt;
265 : 53614268 : enum rtx_code code;
266 : :
267 : 53614268 : 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 : 50860525 : code = GET_CODE (x);
274 : 50860525 : fmt = GET_RTX_FORMAT (code);
275 : 114032404 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
276 : : {
277 : 66363841 : if (fmt[i] == 'e')
278 : : {
279 : 34702747 : if (bad_for_rematerialization_p (XEXP (x, i)))
280 : : return true;
281 : : }
282 : 31661094 : else if (fmt[i] == 'E')
283 : : {
284 : 5938741 : for (j = XVECLEN (x, i) - 1; j >= 0; j--)
285 : 4256692 : 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 : 42708929 : operand_to_remat (rtx_insn *insn)
300 : : {
301 : 42708929 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
302 : 42708929 : struct lra_static_insn_data *static_id = id->insn_static_data;
303 : 42708929 : struct lra_insn_reg *reg, *found_reg = NULL;
304 : :
305 : : /* Don't rematerialize insns which can change PC. */
306 : 42708929 : if (JUMP_P (insn) || CALL_P (insn))
307 : : return -1;
308 : : /* First find a pseudo which can be rematerialized. */
309 : 78346691 : 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 : 57611989 : if (reg->regno == STACK_POINTER_REGNUM && frame_pointer_needed)
316 : : return -1;
317 : 56893692 : else if (reg->type == OP_OUT)
318 : : {
319 : : /* We permits only one spilled reg. */
320 : 24228207 : 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 : 56876140 : if (reg->regno >= FIRST_PSEUDO_REGISTER
330 : 56876140 : && bitmap_bit_p (&subreg_regs, reg->regno))
331 : : return -1;
332 : :
333 : : /* Don't allow hard registers to be rematerialized. */
334 : 55912616 : if (reg->regno < FIRST_PSEUDO_REGISTER)
335 : : return -1;
336 : : }
337 : 20734702 : if (found_reg == NULL)
338 : : return -1;
339 : 14654829 : if (found_reg->regno < FIRST_PSEUDO_REGISTER)
340 : : return -1;
341 : 14654829 : if (bad_for_rematerialization_p (PATTERN (insn)))
342 : : return -1;
343 : : /* Check the other regs are not spilled. */
344 : 25778630 : for (reg = id->regs; reg != NULL; reg = reg->next)
345 : 22829952 : if (found_reg == reg)
346 : 11900300 : continue;
347 : 10929652 : else if (reg->type == OP_INOUT)
348 : : return -1;
349 : 10925373 : else if (reg->regno >= FIRST_PSEUDO_REGISTER
350 : 10925373 : && reg_renumber[reg->regno] < 0)
351 : : /* Another spilled reg. */
352 : : return -1;
353 : 9251250 : else if (reg->type == OP_IN)
354 : : {
355 : 9251250 : 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 : 1979115 : for (struct lra_insn_reg *reg2 = id->regs;
360 : 6188829 : reg2 != NULL;
361 : 4209714 : reg2 = reg2->next)
362 : 4211585 : if (reg2->type == OP_OUT && reg->regno == reg2->regno)
363 : : return -1;
364 : 1977244 : 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 : 2948678 : for (struct lra_insn_reg *reg = static_id->hard_regs;
376 : 3331231 : reg != NULL;
377 : 382553 : reg = reg->next)
378 : 382553 : if (reg->type == OP_INOUT)
379 : : return -1;
380 : 382553 : 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 : 2948678 : int nop = static_id->n_operands;
392 : 2974879 : for (int i = 0; i < nop; i++)
393 : 2951451 : if (REG_P (*id->operand_loc[i])
394 : 2951451 : && (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 : 325138 : create_cand (rtx_insn *insn, int nop, int regno, rtx_insn *activation = NULL)
404 : : {
405 : 325138 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
406 : 325138 : rtx reg = *id->operand_loc[nop];
407 : 325138 : gcc_assert (REG_P (reg));
408 : 325138 : int op_regno = REGNO (reg);
409 : 325138 : gcc_assert (op_regno >= FIRST_PSEUDO_REGISTER);
410 : 325138 : cand_t cand = XNEW (struct cand);
411 : 325138 : cand->insn = insn;
412 : 325138 : cand->nop = nop;
413 : 325138 : cand->regno = regno;
414 : 325138 : cand->reload_regno = op_regno == regno ? -1 : op_regno;
415 : 325138 : gcc_assert (cand->regno >= 0);
416 : 325138 : cand_t cand_in_table = insert_cand (cand);
417 : 325138 : insn_to_cand[INSN_UID (insn)] = cand_in_table;
418 : 325138 : if (cand != cand_in_table)
419 : 70600 : free (cand);
420 : : else
421 : : {
422 : : /* A new cand. */
423 : 254538 : cand->index = all_cands.length ();
424 : 254538 : all_cands.safe_push (cand);
425 : 254538 : cand->next_regno_cand = regno_cands[cand->regno];
426 : 254538 : regno_cands[cand->regno] = cand;
427 : : }
428 : 325138 : if (activation)
429 : 23987 : insn_to_cand_activation[INSN_UID (activation)] = cand_in_table;
430 : 325138 : }
431 : :
432 : : /* Create rematerialization candidates (inserting them into the
433 : : table). */
434 : : static void
435 : 184574 : create_cands (void)
436 : : {
437 : 184574 : rtx_insn *insn;
438 : 184574 : struct potential_cand
439 : : {
440 : : rtx_insn *insn;
441 : : int nop;
442 : : };
443 : 184574 : struct potential_cand *regno_potential_cand;
444 : :
445 : : /* Create candidates. */
446 : 184574 : regno_potential_cand = XCNEWVEC (struct potential_cand, max_reg_num ());
447 : 96078138 : for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
448 : 95893564 : if (NONDEBUG_INSN_P (insn))
449 : : {
450 : 42732916 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
451 : 42732916 : int keep_regno = -1;
452 : 42732916 : rtx set = single_set (insn);
453 : 42732916 : int nop;
454 : :
455 : : /* See if this is an output reload for a previous insn. */
456 : 42732916 : if (set != NULL
457 : 40899693 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
458 : : {
459 : 12268517 : rtx dstreg = SET_DEST (set);
460 : 12268517 : int src_regno = REGNO (SET_SRC (set));
461 : 12268517 : int dst_regno = REGNO (dstreg);
462 : 12268517 : rtx_insn *insn2 = regno_potential_cand[src_regno].insn;
463 : :
464 : 12268517 : if (insn2 != NULL
465 : 12268517 : && dst_regno >= FIRST_PSEUDO_REGISTER
466 : 87799 : && reg_renumber[dst_regno] < 0
467 : 24138 : && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn)
468 : 12292655 : && insn2 == prev_nonnote_nondebug_insn (insn))
469 : : {
470 : 23987 : create_cand (insn2, regno_potential_cand[src_regno].nop,
471 : : dst_regno, insn);
472 : 23987 : goto done;
473 : : }
474 : : }
475 : :
476 : 42708929 : nop = operand_to_remat (insn);
477 : 42708929 : if (nop >= 0)
478 : : {
479 : 2925250 : gcc_assert (REG_P (*id->operand_loc[nop]));
480 : 2925250 : int regno = REGNO (*id->operand_loc[nop]);
481 : 2925250 : 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 : 2925250 : if (reg_renumber[regno] < 0)
487 : 301151 : create_cand (insn, nop, regno);
488 : 2624099 : else if (regno >= lra_constraint_new_regno_start)
489 : : {
490 : 888679 : regno_potential_cand[regno].insn = insn;
491 : 888679 : regno_potential_cand[regno].nop = nop;
492 : 888679 : keep_regno = regno;
493 : : }
494 : : }
495 : :
496 : 39783679 : done:
497 : 111615957 : for (struct lra_insn_reg *reg = id->regs; reg != NULL; reg = reg->next)
498 : 68883041 : if (reg->type != OP_IN && reg->regno != keep_regno
499 : 28620389 : && reg->regno >= FIRST_PSEUDO_REGISTER)
500 : 20520131 : regno_potential_cand[reg->regno].insn = NULL;
501 : : }
502 : 184574 : cands_num = all_cands.length ();
503 : 184574 : free (regno_potential_cand);
504 : 184574 : }
505 : :
506 : :
507 : :
508 : : /* Create and initialize BB data. */
509 : : static void
510 : 184574 : create_remat_bb_data (void)
511 : : {
512 : 184574 : basic_block bb;
513 : 184574 : remat_bb_data_t bb_info;
514 : :
515 : 184574 : remat_bb_data = XNEWVEC (class remat_bb_data,
516 : : last_basic_block_for_fn (cfun));
517 : 7078640 : FOR_ALL_BB_FN (bb, cfun)
518 : : {
519 : 6894066 : gcc_checking_assert (bb->index >= 0
520 : : && bb->index < last_basic_block_for_fn (cfun));
521 : 6894066 : bb_info = get_remat_bb_data (bb);
522 : 6894066 : bb_info->bb = bb;
523 : 6894066 : bitmap_initialize (&bb_info->changed_regs, ®_obstack);
524 : 6894066 : bitmap_initialize (&bb_info->dead_regs, ®_obstack);
525 : 6894066 : bitmap_initialize (&bb_info->gen_cands, ®_obstack);
526 : 6894066 : bitmap_initialize (&bb_info->livein_cands, ®_obstack);
527 : 6894066 : bitmap_initialize (&bb_info->pavin_cands, ®_obstack);
528 : 6894066 : bitmap_initialize (&bb_info->pavout_cands, ®_obstack);
529 : 6894066 : bitmap_initialize (&bb_info->avin_cands, ®_obstack);
530 : 6894066 : bitmap_initialize (&bb_info->avout_cands, ®_obstack);
531 : : }
532 : 184574 : }
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 : 184574 : dump_candidates_and_remat_bb_data (void)
555 : : {
556 : 184574 : basic_block bb;
557 : :
558 : 184574 : 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 : 184574 : finish_remat_bb_data (void)
600 : : {
601 : 184574 : basic_block bb;
602 : :
603 : 6709492 : FOR_EACH_BB_FN (bb, cfun)
604 : : {
605 : 6524918 : bitmap_clear (&get_remat_bb_data (bb)->avout_cands);
606 : 6524918 : bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
607 : 6524918 : bitmap_clear (&get_remat_bb_data (bb)->pavout_cands);
608 : 6524918 : bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
609 : 6524918 : bitmap_clear (&get_remat_bb_data (bb)->livein_cands);
610 : 6524918 : bitmap_clear (&get_remat_bb_data (bb)->gen_cands);
611 : 6524918 : bitmap_clear (&get_remat_bb_data (bb)->dead_regs);
612 : 6524918 : bitmap_clear (&get_remat_bb_data (bb)->changed_regs);
613 : : }
614 : 184574 : free (remat_bb_data);
615 : 184574 : }
616 : :
617 : :
618 : :
619 : : /* Update changed_regs, dead_regs, subreg_regs of BB from INSN. */
620 : : static void
621 : 42732916 : set_bb_regs (basic_block bb, rtx_insn *insn)
622 : : {
623 : 42732916 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
624 : 42732916 : remat_bb_data_t bb_info = get_remat_bb_data (bb);
625 : 42732916 : struct lra_insn_reg *reg;
626 : :
627 : 111615957 : for (reg = id->regs; reg != NULL; reg = reg->next)
628 : : {
629 : 68883041 : unsigned regno = reg->regno;
630 : 68883041 : if (reg->type != OP_IN)
631 : 29509068 : bitmap_set_bit (&bb_info->changed_regs, regno);
632 : 39373973 : else if (find_regno_note (insn, REG_DEAD, regno) != NULL)
633 : 22134422 : bitmap_set_bit (&bb_info->dead_regs, regno);
634 : 68883041 : if (regno >= FIRST_PSEUDO_REGISTER && reg->subreg_p)
635 : 536896 : bitmap_set_bit (&subreg_regs, regno);
636 : : }
637 : 42732916 : if (CALL_P (insn))
638 : : {
639 : : /* Partially-clobbered registers might still be live. */
640 : 2528306 : HARD_REG_SET clobbers = insn_callee_abi (insn).full_reg_clobbers ();
641 : 2528306 : bitmap_ior_into (&get_remat_bb_data (bb)->dead_regs,
642 : 2528306 : bitmap_view<HARD_REG_SET> (clobbers));
643 : : }
644 : 42732916 : }
645 : :
646 : : /* Calculate changed_regs and dead_regs for each BB. */
647 : : static void
648 : 184574 : calculate_local_reg_remat_bb_data (void)
649 : : {
650 : 184574 : basic_block bb;
651 : 184574 : rtx_insn *insn;
652 : :
653 : 6709492 : FOR_EACH_BB_FN (bb, cfun)
654 : 100158316 : FOR_BB_INSNS (bb, insn)
655 : 93633398 : if (NONDEBUG_INSN_P (insn))
656 : 42732916 : set_bb_regs (bb, insn);
657 : 184574 : }
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 : 4452856 : reg_overlap_for_remat_p (lra_insn_reg *reg, rtx_insn *insn)
668 : : {
669 : 4452856 : int iter;
670 : 4452856 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
671 : 4452856 : struct lra_static_insn_data *static_id = id->insn_static_data;
672 : 4452856 : unsigned regno = reg->regno;
673 : 4452856 : int nregs;
674 : :
675 : 4452856 : if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] >= 0)
676 : 3119751 : regno = reg_renumber[regno];
677 : 3748558 : if (regno >= FIRST_PSEUDO_REGISTER)
678 : : nregs = 1;
679 : : else
680 : 3824049 : nregs = hard_regno_nregs (regno, reg->biggest_mode);
681 : :
682 : 4452856 : struct lra_insn_reg *reg2;
683 : :
684 : 12209506 : for (iter = 0; iter < 2; iter++)
685 : 8337275 : for (reg2 = (iter == 0 ? id->regs : static_id->hard_regs);
686 : 15272993 : reg2 != NULL;
687 : 6935718 : reg2 = reg2->next)
688 : : {
689 : 7516343 : int nregs2;
690 : 7516343 : unsigned regno2 = reg2->regno;
691 : :
692 : 7516343 : if (reg2->type != OP_IN && regno2 >= FIRST_PSEUDO_REGISTER)
693 : 4452856 : continue;
694 : :
695 : 2981217 : if (regno2 >= FIRST_PSEUDO_REGISTER && reg_renumber[regno2] >= 0)
696 : 2981217 : regno2 = reg_renumber[regno2];
697 : 2981217 : if (regno2 >= FIRST_PSEUDO_REGISTER)
698 : : nregs2 = 1;
699 : : else
700 : 3063487 : nregs2 = hard_regno_nregs (regno2, reg->biggest_mode);
701 : :
702 : 3063487 : if ((regno2 + nregs2 - 1 >= regno && regno2 < regno + nregs)
703 : 2482862 : || (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 : 29092 : call_used_input_regno_present_p (const function_abi &abi, rtx_insn *insn)
712 : : {
713 : 29092 : int iter;
714 : 29092 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
715 : 29092 : struct lra_static_insn_data *static_id = id->insn_static_data;
716 : 29092 : struct lra_insn_reg *reg;
717 : :
718 : 87276 : for (iter = 0; iter < 2; iter++)
719 : 58184 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
720 : 113188 : reg != NULL;
721 : 55004 : reg = reg->next)
722 : 55004 : if (reg->type == OP_IN
723 : 24326 : && reg->regno < FIRST_PSEUDO_REGISTER
724 : 55004 : && 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 : 184574 : calculate_livein_cands (void)
732 : : {
733 : 184574 : basic_block bb;
734 : :
735 : 6709492 : FOR_EACH_BB_FN (bb, cfun)
736 : : {
737 : 6524918 : bitmap livein_regs = df_get_live_in (bb);
738 : 6524918 : bitmap livein_cands = &get_remat_bb_data (bb)->livein_cands;
739 : 60596977 : for (unsigned int i = 0; i < cands_num; i++)
740 : : {
741 : 54072059 : cand_t cand = all_cands[i];
742 : 54072059 : lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
743 : 54072059 : struct lra_insn_reg *reg;
744 : :
745 : 108967631 : for (reg = id->regs; reg != NULL; reg = reg->next)
746 : 91116435 : if (reg->type == OP_IN && ! bitmap_bit_p (livein_regs, reg->regno))
747 : : break;
748 : 54072059 : if (reg == NULL)
749 : 17851196 : bitmap_set_bit (livein_cands, i);
750 : : }
751 : : }
752 : 184574 : }
753 : :
754 : : /* Calculate gen_cands for each BB. */
755 : : static void
756 : 184574 : calculate_gen_cands (void)
757 : : {
758 : 184574 : basic_block bb;
759 : 184574 : bitmap gen_cands;
760 : 184574 : rtx_insn *insn;
761 : :
762 : 6709492 : FOR_EACH_BB_FN (bb, cfun)
763 : : {
764 : 6524918 : gen_cands = &get_remat_bb_data (bb)->gen_cands;
765 : 6524918 : auto_bitmap gen_insns (®_obstack);
766 : 100158316 : FOR_BB_INSNS (bb, insn)
767 : 93633398 : if (INSN_P (insn))
768 : : {
769 : 80152014 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
770 : 80152014 : struct lra_static_insn_data *static_id = id->insn_static_data;
771 : 80152014 : struct lra_insn_reg *reg;
772 : 80152014 : unsigned int uid;
773 : 80152014 : bitmap_iterator bi;
774 : 80152014 : cand_t cand;
775 : 80152014 : rtx set;
776 : 80152014 : int iter;
777 : 80152014 : int src_regno = -1, dst_regno = -1;
778 : :
779 : 80152014 : if ((set = single_set (insn)) != NULL
780 : 80152014 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
781 : : {
782 : 12268517 : src_regno = REGNO (SET_SRC (set));
783 : 12268517 : dst_regno = REGNO (SET_DEST (set));
784 : : }
785 : :
786 : : /* Update gen_cands: */
787 : 80152014 : bitmap_clear (&temp_bitmap);
788 : 240456042 : for (iter = 0; iter < 2; iter++)
789 : 160304028 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
790 : 248140188 : reg != NULL;
791 : 87836160 : reg = reg->next)
792 : 87836160 : if (reg->type != OP_IN
793 : 87836160 : || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
794 : 64362694 : EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
795 : : {
796 : 1996745 : rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
797 : :
798 : 1996745 : cand = insn_to_cand[INSN_UID (insn2)];
799 : 1996745 : gcc_assert (cand != NULL);
800 : : /* Ignore the reload insn. */
801 : 1996745 : if (src_regno == cand->reload_regno
802 : 821334 : && dst_regno == cand->regno)
803 : 45383 : continue;
804 : 1951362 : if (cand->regno == reg->regno
805 : 1951362 : || reg_overlap_for_remat_p (reg, insn2))
806 : : {
807 : 274108 : bitmap_clear_bit (gen_cands, cand->index);
808 : 274108 : bitmap_set_bit (&temp_bitmap, uid);
809 : : }
810 : : }
811 : :
812 : 80152014 : if (CALL_P (insn))
813 : : {
814 : 2528306 : function_abi callee_abi = insn_callee_abi (insn);
815 : 2537514 : EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
816 : : {
817 : 9208 : rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
818 : :
819 : 9208 : cand = insn_to_cand[INSN_UID (insn2)];
820 : 9208 : gcc_assert (cand != NULL);
821 : 9208 : 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 : 80152014 : bitmap_and_compl_into (gen_insns, &temp_bitmap);
829 : :
830 : 80152014 : cand = insn_to_cand[INSN_UID (insn)];
831 : 80152014 : if (cand != NULL)
832 : : {
833 : 325138 : bitmap_set_bit (gen_cands, cand->index);
834 : 325138 : bitmap_set_bit (gen_insns, INSN_UID (insn));
835 : : }
836 : : }
837 : 6524918 : }
838 : 184574 : }
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 : 13996711 : cand_trans_fun (int bb_index, bitmap bb_in, bitmap bb_out)
850 : : {
851 : 13996711 : remat_bb_data_t bb_info;
852 : 13996711 : bitmap bb_livein, bb_changed_regs, bb_dead_regs;
853 : 13996711 : unsigned int cid;
854 : 13996711 : bitmap_iterator bi;
855 : :
856 : 13996711 : bb_info = get_remat_bb_data_by_index (bb_index);
857 : 13996711 : bb_livein = &bb_info->livein_cands;
858 : 13996711 : bb_changed_regs = &bb_info->changed_regs;
859 : 13996711 : 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 : 13996711 : bitmap_clear (&temp_bitmap);
865 : 22694230 : EXECUTE_IF_SET_IN_BITMAP (bb_in, 0, cid, bi)
866 : : {
867 : 8697519 : cand_t cand = all_cands[cid];
868 : 8697519 : lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
869 : 8697519 : struct lra_insn_reg *reg;
870 : :
871 : 8697519 : if (! bitmap_bit_p (bb_livein, cid))
872 : : {
873 : 100740 : bitmap_set_bit (&temp_bitmap, cid);
874 : 100740 : continue;
875 : : }
876 : 17298409 : for (reg = id->regs; reg != NULL; reg = reg->next)
877 : : /* Ignore all outputs which are not the regno for
878 : : rematerialization. */
879 : 8909625 : if (reg->type == OP_OUT && reg->regno != cand->regno)
880 : 530302 : continue;
881 : 8379323 : else if (bitmap_bit_p (bb_changed_regs, reg->regno)
882 : 8379323 : || bitmap_bit_p (bb_dead_regs, reg->regno))
883 : : {
884 : 207995 : bitmap_set_bit (&temp_bitmap, cid);
885 : 207995 : break;
886 : : }
887 : : /* Check regno for rematerialization. */
888 : 8596779 : if (bitmap_bit_p (bb_changed_regs, cand->regno)
889 : 8596779 : || bitmap_bit_p (bb_dead_regs, cand->regno))
890 : 166666 : bitmap_set_bit (&temp_bitmap, cid);
891 : : }
892 : 13996711 : return bitmap_ior_and_compl (bb_out,
893 : 13996711 : &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 : 7102645 : cand_pav_trans_fun (int bb_index)
906 : : {
907 : 7102645 : remat_bb_data_t bb_info;
908 : :
909 : 7102645 : bb_info = get_remat_bb_data_by_index (bb_index);
910 : 7102645 : return cand_trans_fun (bb_index, &bb_info->pavin_cands,
911 : 7102645 : &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 : 185790 : cand_pav_con_fun_0 (basic_block bb)
918 : : {
919 : 185790 : bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
920 : 185790 : }
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 : 10245280 : cand_pav_con_fun_n (edge e)
930 : : {
931 : 10245280 : basic_block pred = e->src;
932 : 10245280 : basic_block bb = e->dest;
933 : 10245280 : remat_bb_data_t bb_info;
934 : 10245280 : bitmap bb_pavin, pred_pavout;
935 : :
936 : 10245280 : bb_info = get_remat_bb_data (bb);
937 : 10245280 : bb_pavin = &bb_info->pavin_cands;
938 : 10245280 : pred_pavout = &get_remat_bb_data (pred)->pavout_cands;
939 : 10245280 : 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 : 6894066 : cand_av_trans_fun (int bb_index)
952 : : {
953 : 6894066 : remat_bb_data_t bb_info;
954 : :
955 : 6894066 : bb_info = get_remat_bb_data_by_index (bb_index);
956 : 6894066 : return cand_trans_fun (bb_index, &bb_info->avin_cands,
957 : 6894066 : &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 : 185790 : cand_av_con_fun_0 (basic_block bb)
964 : : {
965 : 185790 : bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
966 : 185790 : }
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 : 9853768 : cand_av_con_fun_n (edge e)
976 : : {
977 : 9853768 : basic_block pred = e->src;
978 : 9853768 : basic_block bb = e->dest;
979 : 9853768 : remat_bb_data_t bb_info;
980 : 9853768 : bitmap bb_avin, pred_avout;
981 : :
982 : 9853768 : bb_info = get_remat_bb_data (bb);
983 : 9853768 : bb_avin = &bb_info->avin_cands;
984 : 9853768 : pred_avout = &get_remat_bb_data (pred)->avout_cands;
985 : 9853768 : return bitmap_and_into (bb_avin, pred_avout);
986 : : }
987 : :
988 : : /* Calculate available candidates for each BB. */
989 : : static void
990 : 184574 : calculate_global_remat_bb_data (void)
991 : : {
992 : 184574 : basic_block bb;
993 : :
994 : 184574 : df_simple_dataflow
995 : 184574 : (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 : 6709492 : FOR_EACH_BB_FN (bb, cfun)
1000 : 6524918 : bitmap_copy (&get_remat_bb_data (bb)->avin_cands,
1001 : 6524918 : &get_remat_bb_data (bb)->pavin_cands);
1002 : 184574 : df_simple_dataflow
1003 : 184574 : (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 : 184574 : }
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 : 51195631 : get_hard_regs (struct lra_insn_reg *reg, int &nregs)
1024 : : {
1025 : 51195631 : int regno = reg->regno;
1026 : 51195631 : int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
1027 : :
1028 : 51195631 : if (hard_regno >= 0)
1029 : 48093968 : nregs = hard_regno_nregs (hard_regno, reg->biggest_mode);
1030 : 51195631 : return hard_regno;
1031 : : }
1032 : :
1033 : : /* Make copy of and register scratch pseudos in rematerialized insn
1034 : : REMAT_INSN. */
1035 : : static void
1036 : 2617 : update_scratch_ops (rtx_insn *remat_insn)
1037 : : {
1038 : 2617 : lra_insn_recog_data_t id = lra_get_insn_recog_data (remat_insn);
1039 : 2617 : struct lra_static_insn_data *static_id = id->insn_static_data;
1040 : 8518 : for (int i = 0; i < static_id->n_operands; i++)
1041 : : {
1042 : 5901 : rtx *loc = id->operand_loc[i];
1043 : 5901 : if (! REG_P (*loc))
1044 : 2188 : continue;
1045 : 3713 : int regno = REGNO (*loc);
1046 : 3713 : if (! ira_former_scratch_p (regno))
1047 : 3713 : 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 : 2617 : }
1055 : :
1056 : : /* Insert rematerialization insns using the data-flow data calculated
1057 : : earlier. */
1058 : : static bool
1059 : 184574 : do_remat (void)
1060 : : {
1061 : 184574 : unsigned regno;
1062 : 184574 : rtx_insn *insn;
1063 : 184574 : basic_block bb;
1064 : 184574 : bool changed_p = false;
1065 : : /* Living hard regs and hard registers of living pseudos. */
1066 : 184574 : HARD_REG_SET live_hard_regs;
1067 : 184574 : bitmap_iterator bi;
1068 : :
1069 : 184574 : auto_bitmap avail_cands (®_obstack);
1070 : 184574 : auto_bitmap active_cands (®_obstack);
1071 : 6709492 : FOR_EACH_BB_FN (bb, cfun)
1072 : : {
1073 : 6524918 : CLEAR_HARD_REG_SET (live_hard_regs);
1074 : 68031382 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), 0, regno, bi)
1075 : : {
1076 : 8595643 : int hard_regno = regno < FIRST_PSEUDO_REGISTER
1077 : 61506464 : ? regno
1078 : 52910821 : : reg_renumber[regno];
1079 : 61506464 : if (hard_regno >= 0)
1080 : 35087163 : SET_HARD_REG_BIT (live_hard_regs, hard_regno);
1081 : : }
1082 : 6524918 : bitmap_and (avail_cands, &get_remat_bb_data (bb)->avin_cands,
1083 : 6524918 : &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 : 6524918 : bitmap_copy (active_cands, avail_cands);
1087 : 100158316 : FOR_BB_INSNS (bb, insn)
1088 : : {
1089 : 93633398 : if (!NONDEBUG_INSN_P (insn))
1090 : 50903099 : continue;
1091 : :
1092 : 42732916 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
1093 : 42732916 : struct lra_static_insn_data *static_id = id->insn_static_data;
1094 : 42732916 : struct lra_insn_reg *reg;
1095 : 42732916 : cand_t cand;
1096 : 42732916 : unsigned int cid;
1097 : 42732916 : bitmap_iterator bi;
1098 : 42732916 : rtx set;
1099 : 42732916 : int iter;
1100 : 42732916 : int src_regno = -1, dst_regno = -1;
1101 : :
1102 : 42732916 : if ((set = single_set (insn)) != NULL
1103 : 42732916 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
1104 : : {
1105 : 12268517 : src_regno = REGNO (SET_SRC (set));
1106 : 12268517 : dst_regno = REGNO (SET_DEST (set));
1107 : : }
1108 : :
1109 : 42732916 : cand = NULL;
1110 : : /* Check possibility of rematerialization (hard reg or
1111 : : unpsilled pseudo <- spilled pseudo): */
1112 : 42732916 : if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER
1113 : 10829455 : && reg_renumber[src_regno] < 0
1114 : 1817767 : && (dst_regno < FIRST_PSEUDO_REGISTER
1115 : 1656533 : || reg_renumber[dst_regno] >= 0))
1116 : : {
1117 : 1817761 : for (cand = regno_cands[src_regno];
1118 : 2423041 : cand != NULL;
1119 : 605280 : cand = cand->next_regno_cand)
1120 : 608654 : if (bitmap_bit_p (avail_cands, cand->index)
1121 : 608654 : && bitmap_bit_p (active_cands, cand->index))
1122 : : break;
1123 : : }
1124 : 1817761 : int i, hard_regno, nregs;
1125 : 1817761 : int dst_hard_regno, dst_nregs;
1126 : 1817761 : rtx_insn *remat_insn = NULL;
1127 : 1817761 : poly_int64 cand_sp_offset = 0;
1128 : 1817761 : if (cand != NULL)
1129 : : {
1130 : 3374 : lra_insn_recog_data_t cand_id
1131 : 3374 : = lra_get_insn_recog_data (cand->insn);
1132 : 3374 : struct lra_static_insn_data *static_cand_id
1133 : : = cand_id->insn_static_data;
1134 : 3374 : rtx saved_op = *cand_id->operand_loc[cand->nop];
1135 : :
1136 : : /* Check clobbers do not kill something living. */
1137 : 3374 : gcc_assert (REG_P (saved_op));
1138 : 3374 : int ignore_regno = REGNO (saved_op);
1139 : :
1140 : 6493 : dst_hard_regno = dst_regno < FIRST_PSEUDO_REGISTER
1141 : 3374 : ? dst_regno : reg_renumber[dst_regno];
1142 : 3374 : gcc_assert (dst_hard_regno >= 0);
1143 : 3374 : machine_mode mode = GET_MODE (SET_DEST (set));
1144 : 3374 : dst_nregs = hard_regno_nregs (dst_hard_regno, mode);
1145 : :
1146 : 8874 : for (reg = cand_id->regs; reg != NULL; reg = reg->next)
1147 : 5500 : 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 : 3374 : if (reg == NULL)
1163 : : {
1164 : 3374 : for (reg = static_cand_id->hard_regs;
1165 : 3766 : 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 : 372 : && reg->regno < dst_hard_regno + dst_nregs)
1173 : : break;
1174 : : }
1175 : : }
1176 : :
1177 : 3374 : if (reg == NULL)
1178 : : {
1179 : 3374 : *cand_id->operand_loc[cand->nop] = SET_DEST (set);
1180 : 3374 : lra_update_insn_regno_info (cand->insn);
1181 : 3374 : bool ok_p = lra_constrain_insn (cand->insn);
1182 : 3374 : if (ok_p)
1183 : : {
1184 : 2617 : rtx remat_pat = copy_insn (PATTERN (cand->insn));
1185 : :
1186 : 2617 : start_sequence ();
1187 : 2617 : emit_insn (remat_pat);
1188 : 2617 : remat_insn = end_sequence ();
1189 : 2617 : if (recog_memoized (remat_insn) < 0)
1190 : 0 : remat_insn = NULL;
1191 : 2617 : cand_sp_offset = cand_id->sp_offset;
1192 : : }
1193 : 3374 : *cand_id->operand_loc[cand->nop] = saved_op;
1194 : 3374 : lra_update_insn_regno_info (cand->insn);
1195 : : }
1196 : : }
1197 : :
1198 : 42732916 : bitmap_clear (&temp_bitmap);
1199 : : /* Update avail_cands (see analogous code for
1200 : : calculate_gen_cands). */
1201 : 170931664 : for (iter = 0; iter < 2; iter++)
1202 : 85465832 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
1203 : 165170859 : reg != NULL;
1204 : 79705027 : reg = reg->next)
1205 : 79705027 : if (reg->type != OP_IN
1206 : 79705027 : || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1207 : 64926767 : EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1208 : : {
1209 : 2560818 : cand = all_cands[cid];
1210 : :
1211 : : /* Ignore the reload insn. */
1212 : 2560818 : if (src_regno == cand->reload_regno
1213 : 1112991 : && dst_regno == cand->regno)
1214 : 45383 : continue;
1215 : 2515435 : if (cand->regno == reg->regno
1216 : 2515435 : || reg_overlap_for_remat_p (reg, cand->insn))
1217 : 320458 : bitmap_set_bit (&temp_bitmap, cand->index);
1218 : : }
1219 : :
1220 : 42732916 : if (CALL_P (insn))
1221 : : {
1222 : 2528306 : function_abi callee_abi = insn_callee_abi (insn);
1223 : 2548190 : EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1224 : : {
1225 : 19884 : cand = all_cands[cid];
1226 : :
1227 : 19884 : if (call_used_input_regno_present_p (callee_abi, cand->insn))
1228 : 0 : bitmap_set_bit (&temp_bitmap, cand->index);
1229 : : }
1230 : : }
1231 : :
1232 : 42732916 : 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 : 42732916 : cand = insn_to_cand_activation[INSN_UID (insn)];
1237 : 42732916 : if (cand)
1238 : 23987 : bitmap_set_bit (active_cands, cand->index);
1239 : :
1240 : 42732916 : cand = insn_to_cand[INSN_UID (insn)];
1241 : 42732916 : if (cand != NULL)
1242 : : {
1243 : 325138 : bitmap_set_bit (avail_cands, cand->index);
1244 : 325138 : if (cand->reload_regno == -1)
1245 : 301163 : bitmap_set_bit (active_cands, cand->index);
1246 : : else
1247 : 23975 : bitmap_clear_bit (active_cands, cand->index);
1248 : : }
1249 : :
1250 : 42732916 : if (remat_insn != NULL)
1251 : : {
1252 : 2617 : poly_int64 sp_offset_change = cand_sp_offset - id->sp_offset;
1253 : 2617 : if (maybe_ne (sp_offset_change, 0))
1254 : 74 : change_sp_offset (remat_insn, sp_offset_change);
1255 : 2617 : update_scratch_ops (remat_insn);
1256 : 2617 : lra_process_new_insns (insn, remat_insn, NULL,
1257 : : "Inserting rematerialization insn");
1258 : 2617 : lra_set_insn_deleted (insn);
1259 : 2617 : changed_p = true;
1260 : 2617 : continue;
1261 : 2617 : }
1262 : :
1263 : : /* Update live hard regs: */
1264 : 111608106 : for (reg = id->regs; reg != NULL; reg = reg->next)
1265 : 68877807 : if (reg->type == OP_IN
1266 : 68877807 : && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1267 : : {
1268 : 22132292 : if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1269 : 1342685 : continue;
1270 : 41926575 : for (i = 0; i < nregs; i++)
1271 : 21136968 : 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 : 53552285 : for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1276 : 10821986 : if (reg->type == OP_IN
1277 : 10821986 : && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1278 : 3024328 : CLEAR_HARD_REG_BIT (live_hard_regs, reg->regno);
1279 : : /* Inputs have been processed, now process outputs. */
1280 : 111608106 : for (reg = id->regs; reg != NULL; reg = reg->next)
1281 : 68877807 : if (reg->type != OP_IN
1282 : 68877807 : && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1283 : : {
1284 : 29063339 : if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1285 : 1758978 : continue;
1286 : 55237102 : for (i = 0; i < nregs; i++)
1287 : 27932741 : SET_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1288 : : }
1289 : 53552285 : for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1290 : 10821986 : if (reg->type != OP_IN
1291 : 10821986 : && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1292 : 3158835 : SET_HARD_REG_BIT (live_hard_regs, reg->regno);
1293 : : }
1294 : : }
1295 : 184574 : return changed_p;
1296 : 184574 : }
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 : 199067 : lra_remat (void)
1307 : : {
1308 : 199067 : basic_block bb;
1309 : 199067 : bool result;
1310 : 199067 : int max_regno = max_reg_num ();
1311 : :
1312 : 199067 : if (! flag_lra_remat)
1313 : : return false;
1314 : 184661 : lra_rematerialization_iter++;
1315 : 184661 : if (lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
1316 : : return false;
1317 : 184574 : if (lra_dump_file != NULL)
1318 : 1 : fprintf (lra_dump_file,
1319 : : "\n******** Rematerialization #%d: ********\n\n",
1320 : : lra_rematerialization_iter);
1321 : 184574 : timevar_push (TV_LRA_REMAT);
1322 : 184574 : insn_to_cand = XCNEWVEC (cand_t, get_max_uid ());
1323 : 184574 : insn_to_cand_activation = XCNEWVEC (cand_t, get_max_uid ());
1324 : 184574 : regno_cands = XCNEWVEC (cand_t, max_regno);
1325 : 184574 : all_cands.create (8000);
1326 : 184574 : initiate_cand_table ();
1327 : 184574 : create_remat_bb_data ();
1328 : 184574 : bitmap_initialize (&temp_bitmap, ®_obstack);
1329 : 184574 : bitmap_initialize (&subreg_regs, ®_obstack);
1330 : 184574 : calculate_local_reg_remat_bb_data ();
1331 : 184574 : create_cands ();
1332 : 184574 : calculate_livein_cands ();
1333 : 184574 : calculate_gen_cands ();
1334 : 184574 : bitmap_initialize (&all_blocks, ®_obstack);
1335 : 7078640 : FOR_ALL_BB_FN (bb, cfun)
1336 : 6894066 : bitmap_set_bit (&all_blocks, bb->index);
1337 : 184574 : calculate_global_remat_bb_data ();
1338 : 184574 : dump_candidates_and_remat_bb_data ();
1339 : 184574 : result = do_remat ();
1340 : 184574 : if (result)
1341 : 1836 : lra_dump_insns_if_possible ("changed func after rematerialization");
1342 : 184574 : all_cands.release ();
1343 : 184574 : bitmap_clear (&temp_bitmap);
1344 : 184574 : bitmap_clear (&subreg_regs);
1345 : 184574 : finish_remat_bb_data ();
1346 : 184574 : finish_cand_table ();
1347 : 184574 : bitmap_clear (&all_blocks);
1348 : 184574 : free (regno_cands);
1349 : 184574 : free (insn_to_cand);
1350 : 184574 : free (insn_to_cand_activation);
1351 : 184574 : timevar_pop (TV_LRA_REMAT);
1352 : 184574 : return result;
1353 : : }
|
