Branch data Line data Source code
1 : : /* Rematerialize pseudos values.
2 : : Copyright (C) 2014-2025 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)
85 : : o no INOUT regs (it means no non-paradoxical subreg of output reg)
86 : : o one output spilled pseudo (or reload pseudo of a spilled pseudo)
87 : : o all other pseudos are with assigned hard regs. */
88 : : struct cand
89 : : {
90 : : /* Index of the candidates in all_cands. */
91 : : int index;
92 : : /* Insn pseudo regno for rematerialization. */
93 : : int regno;
94 : : /* The candidate insn. */
95 : : rtx_insn *insn;
96 : : /* Non-negative if a reload pseudo is in the insn instead of the
97 : : pseudo for rematerialization. */
98 : : int reload_regno;
99 : : /* Number of the operand containing the regno or its reload
100 : : regno. */
101 : : int nop;
102 : : /* Next candidate for the same regno. */
103 : : cand_t next_regno_cand;
104 : : };
105 : :
106 : : /* Vector containing all candidates. */
107 : : static vec<cand_t> all_cands;
108 : : /* Map: insn -> candidate representing it. It is null if the insn cannot
109 : : be used for rematerialization. */
110 : : static cand_t *insn_to_cand;
111 : : /* A secondary map, for candidates that involve two insns, where the
112 : : second one makes the equivalence. The candidate must not be used
113 : : before seeing this activation insn. */
114 : : static cand_t *insn_to_cand_activation;
115 : :
116 : : /* Map regno -> candidates can be used for the regno
117 : : rematerialization. */
118 : : static cand_t *regno_cands;
119 : :
120 : : /* Data about basic blocks used for the rematerialization
121 : : sub-pass. */
122 : : class remat_bb_data
123 : : {
124 : : public:
125 : : /* Basic block about which the below data are. */
126 : : basic_block bb;
127 : : /* Registers changed in the basic block: */
128 : : bitmap_head changed_regs;
129 : : /* Registers becoming dead in the BB. */
130 : : bitmap_head dead_regs;
131 : : /* Cands present in the BB whose in/out regs are not changed after
132 : : the cands occurence and are not dead (except the reload
133 : : regno). */
134 : : bitmap_head gen_cands;
135 : : bitmap_head livein_cands; /* cands whose inputs live at the BB start. */
136 : : bitmap_head pavin_cands; /* cands partially available at BB entry. */
137 : : bitmap_head pavout_cands; /* cands partially available at BB exit. */
138 : : bitmap_head avin_cands; /* cands available at the entry of the BB. */
139 : : bitmap_head avout_cands; /* cands available at the exit of the BB. */
140 : : };
141 : :
142 : : /* Array for all BB data. Indexed by the corresponding BB index. */
143 : : typedef class remat_bb_data *remat_bb_data_t;
144 : :
145 : : /* Basic blocks for data flow problems -- all bocks except the special
146 : : ones. */
147 : : static bitmap_head all_blocks;
148 : :
149 : : /* All basic block data are referred through the following array. */
150 : : static remat_bb_data_t remat_bb_data;
151 : :
152 : : /* Two small functions for access to the bb data. */
153 : : static inline remat_bb_data_t
154 : 138145025 : get_remat_bb_data (basic_block bb)
155 : : {
156 : 138145025 : return &remat_bb_data[(bb)->index];
157 : : }
158 : :
159 : : static inline remat_bb_data_t
160 : 25557470 : get_remat_bb_data_by_index (int index)
161 : : {
162 : 25557470 : return &remat_bb_data[index];
163 : : }
164 : :
165 : :
166 : :
167 : : /* Hash table for the candidates. Different insns (e.g. structurally
168 : : the same insns or even insns with different unused output regs) can
169 : : be represented by the same candidate in the table. */
170 : : static htab_t cand_table;
171 : :
172 : : /* Hash function for candidate CAND. */
173 : : static hashval_t
174 : 312133 : cand_hash (const void *cand)
175 : : {
176 : 312133 : const_cand_t c = (const_cand_t) cand;
177 : 312133 : lra_insn_recog_data_t id = lra_get_insn_recog_data (c->insn);
178 : 312133 : struct lra_static_insn_data *static_id = id->insn_static_data;
179 : 312133 : int nops = static_id->n_operands;
180 : 312133 : hashval_t hash = 0;
181 : :
182 : 946391 : for (int i = 0; i < nops; i++)
183 : 634258 : if (i == c->nop)
184 : 312133 : hash = iterative_hash_object (c->regno, hash);
185 : 322125 : else if (static_id->operand[i].type == OP_IN)
186 : 322100 : hash = iterative_hash_object (*id->operand_loc[i], hash);
187 : 312133 : return hash;
188 : : }
189 : :
190 : : /* Equal function for candidates CAND1 and CAND2. They are equal if
191 : : the corresponding candidate insns have the same code, the same
192 : : regno for rematerialization, the same input operands. */
193 : : static int
194 : 71213 : cand_eq_p (const void *cand1, const void *cand2)
195 : : {
196 : 71213 : const_cand_t c1 = (const_cand_t) cand1;
197 : 71213 : const_cand_t c2 = (const_cand_t) cand2;
198 : 71213 : lra_insn_recog_data_t id1 = lra_get_insn_recog_data (c1->insn);
199 : 71213 : lra_insn_recog_data_t id2 = lra_get_insn_recog_data (c2->insn);
200 : 71213 : struct lra_static_insn_data *static_id1 = id1->insn_static_data;
201 : 71213 : int nops = static_id1->n_operands;
202 : :
203 : 71213 : if (c1->regno != c2->regno
204 : 70832 : || INSN_CODE (c1->insn) < 0
205 : 70832 : || INSN_CODE (c1->insn) != INSN_CODE (c2->insn))
206 : : return false;
207 : 70832 : gcc_assert (c1->nop == c2->nop);
208 : 212827 : for (int i = 0; i < nops; i++)
209 : 142009 : if (i != c1->nop && static_id1->operand[i].type == OP_IN
210 : 71177 : && *id1->operand_loc[i] != *id2->operand_loc[i])
211 : : return false;
212 : : return true;
213 : : }
214 : :
215 : : /* Insert candidate CAND into the table if it is not there yet.
216 : : Return candidate which is in the table. */
217 : : static cand_t
218 : 312133 : insert_cand (cand_t cand)
219 : : {
220 : 312133 : void **entry_ptr;
221 : :
222 : 312133 : entry_ptr = htab_find_slot (cand_table, cand, INSERT);
223 : 312133 : if (*entry_ptr == NULL)
224 : 241315 : *entry_ptr = (void *) cand;
225 : 312133 : return (cand_t) *entry_ptr;
226 : : }
227 : :
228 : : /* Free candidate CAND memory. */
229 : : static void
230 : 241315 : free_cand (void *cand)
231 : : {
232 : 241315 : free (cand);
233 : 241315 : }
234 : :
235 : : /* Initiate the candidate table. */
236 : : static void
237 : 177736 : initiate_cand_table (void)
238 : : {
239 : 177736 : cand_table = htab_create (8000, cand_hash, cand_eq_p,
240 : : (htab_del) free_cand);
241 : 177736 : }
242 : :
243 : : /* Finish the candidate table. */
244 : : static void
245 : 177736 : finish_cand_table (void)
246 : : {
247 : 0 : htab_delete (cand_table);
248 : 0 : }
249 : :
250 : :
251 : :
252 : : /* Return true if X contains memory or some UNSPEC. We cannot just
253 : : check insn operands as memory or unspec might be not an operand
254 : : itself but contain an operand. Insn with memory access is not
255 : : profitable for rematerialization. Rematerialization of UNSPEC
256 : : might result in wrong code generation as the UNPEC effect is
257 : : unknown (e.g. generating a label). */
258 : : static bool
259 : 49280798 : bad_for_rematerialization_p (rtx x)
260 : : {
261 : 49280798 : int i, j;
262 : 49280798 : const char *fmt;
263 : 49280798 : enum rtx_code code;
264 : :
265 : 49280798 : if (MEM_P (x) || GET_CODE (x) == UNSPEC || GET_CODE (x) == UNSPEC_VOLATILE)
266 : : return true;
267 : 46902642 : code = GET_CODE (x);
268 : 46902642 : fmt = GET_RTX_FORMAT (code);
269 : 105493082 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
270 : : {
271 : 61348142 : if (fmt[i] == 'e')
272 : : {
273 : 32050577 : if (bad_for_rematerialization_p (XEXP (x, i)))
274 : : return true;
275 : : }
276 : 29297565 : else if (fmt[i] == 'E')
277 : : {
278 : 5383683 : for (j = XVECLEN (x, i) - 1; j >= 0; j--)
279 : 3824437 : if (bad_for_rematerialization_p (XVECEXP (x, i, j)))
280 : : return true;
281 : : }
282 : : }
283 : : return false;
284 : : }
285 : :
286 : : /* If INSN cannot be used for rematerialization, return negative
287 : : value. If INSN can be considered as a candidate for
288 : : rematerialization, return value which is the operand number of the
289 : : pseudo for which the insn can be used for rematerialization. Here
290 : : we consider the insns without any memory, spilled pseudo (except
291 : : for the rematerialization pseudo), or dying or unused regs. */
292 : : static int
293 : 39537366 : operand_to_remat (rtx_insn *insn)
294 : : {
295 : 39537366 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
296 : 39537366 : struct lra_static_insn_data *static_id = id->insn_static_data;
297 : 39537366 : struct lra_insn_reg *reg, *found_reg = NULL;
298 : :
299 : : /* Don't rematerialize insns which can change PC. */
300 : 39537366 : if (JUMP_P (insn) || CALL_P (insn))
301 : : return -1;
302 : : /* First find a pseudo which can be rematerialized. */
303 : 72011040 : for (reg = id->regs; reg != NULL; reg = reg->next)
304 : : {
305 : : /* True FRAME_POINTER_NEEDED might be because we cannot follow
306 : : changing sp offsets, e.g. alloca is used. If the insn contains
307 : : stack pointer in such case, we cannot rematerialize it as we
308 : : cannot know sp offset at a rematerialization place. */
309 : 53150659 : if (reg->regno == STACK_POINTER_REGNUM && frame_pointer_needed)
310 : : return -1;
311 : 52488297 : else if (reg->type == OP_OUT && ! reg->subreg_p
312 : 52488297 : && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
313 : : {
314 : : /* We permits only one spilled reg. */
315 : 22214352 : if (found_reg != NULL)
316 : : return -1;
317 : : found_reg = reg;
318 : : }
319 : : /* IRA calculates conflicts separately for subregs of two words
320 : : pseudo. Even if the pseudo lives, e.g. one its subreg can be
321 : : used lately, another subreg hard register can be already used
322 : : for something else. In such case, it is not safe to
323 : : rematerialize the insn. */
324 : 52483725 : if (reg->regno >= FIRST_PSEUDO_REGISTER
325 : 52483725 : && bitmap_bit_p (&subreg_regs, reg->regno))
326 : : return -1;
327 : :
328 : : /* Don't allow hard registers to be rematerialized. */
329 : 51503752 : if (reg->regno < FIRST_PSEUDO_REGISTER)
330 : : return -1;
331 : : }
332 : 18860381 : if (found_reg == NULL)
333 : : return -1;
334 : 13405784 : if (found_reg->regno < FIRST_PSEUDO_REGISTER)
335 : : return -1;
336 : 13405784 : if (bad_for_rematerialization_p (PATTERN (insn)))
337 : : return -1;
338 : : /* Check the other regs are not spilled. */
339 : 23858712 : for (reg = id->regs; reg != NULL; reg = reg->next)
340 : 21144573 : if (found_reg == reg)
341 : 11027628 : continue;
342 : 10116945 : else if (reg->type == OP_INOUT)
343 : : return -1;
344 : 10102828 : else if (reg->regno >= FIRST_PSEUDO_REGISTER
345 : 10102828 : && reg_renumber[reg->regno] < 0)
346 : : /* Another spilled reg. */
347 : : return -1;
348 : 8588210 : else if (reg->type == OP_IN)
349 : : {
350 : 8581503 : if (find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
351 : : /* We don't want to make live ranges longer. */
352 : : return -1;
353 : : /* Check that there is no output reg as the input one. */
354 : 1798596 : for (struct lra_insn_reg *reg2 = id->regs;
355 : 5625493 : reg2 != NULL;
356 : 3826897 : reg2 = reg2->next)
357 : 3828744 : if (reg2->type == OP_OUT && reg->regno == reg2->regno)
358 : : return -1;
359 : 1796749 : if (reg->regno < FIRST_PSEUDO_REGISTER)
360 : 0 : for (struct lra_insn_reg *reg2 = static_id->hard_regs;
361 : 0 : reg2 != NULL;
362 : 0 : reg2 = reg2->next)
363 : 0 : if (reg2->type == OP_OUT
364 : 0 : && reg->regno <= reg2->regno
365 : 0 : && (reg2->regno
366 : 0 : < (int) end_hard_regno (reg->biggest_mode, reg->regno)))
367 : : return -1;
368 : : }
369 : : /* Check hard coded insn registers. */
370 : 2714139 : for (struct lra_insn_reg *reg = static_id->hard_regs;
371 : 3050383 : reg != NULL;
372 : 336244 : reg = reg->next)
373 : 336244 : if (reg->type == OP_INOUT)
374 : : return -1;
375 : 336244 : else if (reg->type == OP_IN)
376 : : {
377 : : /* Check that there is no output hard reg as the input
378 : : one. */
379 : 0 : for (struct lra_insn_reg *reg2 = static_id->hard_regs;
380 : 0 : reg2 != NULL;
381 : 0 : reg2 = reg2->next)
382 : 0 : if (reg2->type == OP_OUT && reg->regno == reg2->regno)
383 : : return -1;
384 : : }
385 : : /* Find the rematerialization operand. */
386 : 2714139 : int nop = static_id->n_operands;
387 : 2740204 : for (int i = 0; i < nop; i++)
388 : 2727013 : if (REG_P (*id->operand_loc[i])
389 : 2727013 : && (int) REGNO (*id->operand_loc[i]) == found_reg->regno)
390 : : return i;
391 : : return -1;
392 : : }
393 : :
394 : : /* Create candidate for INSN with rematerialization operand NOP and
395 : : REGNO. Insert the candidate into the table and set up the
396 : : corresponding INSN_TO_CAND element. */
397 : : static void
398 : 312133 : create_cand (rtx_insn *insn, int nop, int regno, rtx_insn *activation = NULL)
399 : : {
400 : 312133 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
401 : 312133 : rtx reg = *id->operand_loc[nop];
402 : 312133 : gcc_assert (REG_P (reg));
403 : 312133 : int op_regno = REGNO (reg);
404 : 312133 : gcc_assert (op_regno >= FIRST_PSEUDO_REGISTER);
405 : 312133 : cand_t cand = XNEW (struct cand);
406 : 312133 : cand->insn = insn;
407 : 312133 : cand->nop = nop;
408 : 312133 : cand->regno = regno;
409 : 312133 : cand->reload_regno = op_regno == regno ? -1 : op_regno;
410 : 312133 : gcc_assert (cand->regno >= 0);
411 : 312133 : cand_t cand_in_table = insert_cand (cand);
412 : 312133 : insn_to_cand[INSN_UID (insn)] = cand_in_table;
413 : 312133 : if (cand != cand_in_table)
414 : 70818 : free (cand);
415 : : else
416 : : {
417 : : /* A new cand. */
418 : 241315 : cand->index = all_cands.length ();
419 : 241315 : all_cands.safe_push (cand);
420 : 241315 : cand->next_regno_cand = regno_cands[cand->regno];
421 : 241315 : regno_cands[cand->regno] = cand;
422 : : }
423 : 312133 : if (activation)
424 : 20691 : insn_to_cand_activation[INSN_UID (activation)] = cand_in_table;
425 : 312133 : }
426 : :
427 : : /* Create rematerialization candidates (inserting them into the
428 : : table). */
429 : : static void
430 : 177736 : create_cands (void)
431 : : {
432 : 177736 : rtx_insn *insn;
433 : 177736 : struct potential_cand
434 : : {
435 : : rtx_insn *insn;
436 : : int nop;
437 : : };
438 : 177736 : struct potential_cand *regno_potential_cand;
439 : :
440 : : /* Create candidates. */
441 : 177736 : regno_potential_cand = XCNEWVEC (struct potential_cand, max_reg_num ());
442 : 85189902 : for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
443 : 85012166 : if (NONDEBUG_INSN_P (insn))
444 : : {
445 : 39558057 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
446 : 39558057 : int keep_regno = -1;
447 : 39558057 : rtx set = single_set (insn);
448 : 39558057 : int nop;
449 : :
450 : : /* See if this is an output reload for a previous insn. */
451 : 39558057 : if (set != NULL
452 : 37805304 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
453 : : {
454 : 11384061 : rtx dstreg = SET_DEST (set);
455 : 11384061 : int src_regno = REGNO (SET_SRC (set));
456 : 11384061 : int dst_regno = REGNO (dstreg);
457 : 11384061 : rtx_insn *insn2 = regno_potential_cand[src_regno].insn;
458 : :
459 : 11384061 : if (insn2 != NULL
460 : 11384061 : && dst_regno >= FIRST_PSEUDO_REGISTER
461 : 103961 : && reg_renumber[dst_regno] < 0
462 : 20800 : && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn)
463 : 11404861 : && insn2 == prev_nonnote_insn (insn))
464 : : {
465 : 20691 : create_cand (insn2, regno_potential_cand[src_regno].nop,
466 : : dst_regno, insn);
467 : 20691 : goto done;
468 : : }
469 : : }
470 : :
471 : 39537366 : nop = operand_to_remat (insn);
472 : 39537366 : if (nop >= 0)
473 : : {
474 : 2700948 : gcc_assert (REG_P (*id->operand_loc[nop]));
475 : 2700948 : int regno = REGNO (*id->operand_loc[nop]);
476 : 2700948 : gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
477 : : /* If we're setting an unrenumbered pseudo, make a candidate
478 : : immediately. If it's a potential output reload register, save
479 : : it for later; the code above looks for output reload insns later
480 : : on. */
481 : 2700948 : if (reg_renumber[regno] < 0)
482 : 291442 : create_cand (insn, nop, regno);
483 : 2409506 : else if (regno >= lra_constraint_new_regno_start)
484 : : {
485 : 862871 : regno_potential_cand[regno].insn = insn;
486 : 862871 : regno_potential_cand[regno].nop = nop;
487 : 862871 : keep_regno = regno;
488 : : }
489 : : }
490 : :
491 : 36836418 : done:
492 : 102536839 : for (struct lra_insn_reg *reg = id->regs; reg != NULL; reg = reg->next)
493 : 62978782 : if (reg->type != OP_IN && reg->regno != keep_regno
494 : 26829216 : && reg->regno >= FIRST_PSEUDO_REGISTER)
495 : 19129792 : regno_potential_cand[reg->regno].insn = NULL;
496 : : }
497 : 177736 : cands_num = all_cands.length ();
498 : 177736 : free (regno_potential_cand);
499 : 177736 : }
500 : :
501 : :
502 : :
503 : : /* Create and initialize BB data. */
504 : : static void
505 : 177736 : create_remat_bb_data (void)
506 : : {
507 : 177736 : basic_block bb;
508 : 177736 : remat_bb_data_t bb_info;
509 : :
510 : 177736 : remat_bb_data = XNEWVEC (class remat_bb_data,
511 : : last_basic_block_for_fn (cfun));
512 : 6474120 : FOR_ALL_BB_FN (bb, cfun)
513 : : {
514 : 6296384 : gcc_checking_assert (bb->index >= 0
515 : : && bb->index < last_basic_block_for_fn (cfun));
516 : 6296384 : bb_info = get_remat_bb_data (bb);
517 : 6296384 : bb_info->bb = bb;
518 : 6296384 : bitmap_initialize (&bb_info->changed_regs, ®_obstack);
519 : 6296384 : bitmap_initialize (&bb_info->dead_regs, ®_obstack);
520 : 6296384 : bitmap_initialize (&bb_info->gen_cands, ®_obstack);
521 : 6296384 : bitmap_initialize (&bb_info->livein_cands, ®_obstack);
522 : 6296384 : bitmap_initialize (&bb_info->pavin_cands, ®_obstack);
523 : 6296384 : bitmap_initialize (&bb_info->pavout_cands, ®_obstack);
524 : 6296384 : bitmap_initialize (&bb_info->avin_cands, ®_obstack);
525 : 6296384 : bitmap_initialize (&bb_info->avout_cands, ®_obstack);
526 : : }
527 : 177736 : }
528 : :
529 : : /* Dump all candidates to DUMP_FILE. */
530 : : static void
531 : 1 : dump_cands (FILE *dump_file)
532 : : {
533 : 1 : int i;
534 : 1 : cand_t cand;
535 : :
536 : 1 : fprintf (dump_file, "\nCands:\n");
537 : 2 : for (i = 0; i < (int) cands_num; i++)
538 : : {
539 : 0 : cand = all_cands[i];
540 : 0 : fprintf (dump_file, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
541 : : i, cand->nop, cand->regno, cand->reload_regno);
542 : 0 : print_inline_rtx (dump_file, cand->insn, 6);
543 : 0 : fprintf (dump_file, "\n");
544 : : }
545 : 1 : }
546 : :
547 : : /* Dump all candidates and BB data. */
548 : : static void
549 : 177736 : dump_candidates_and_remat_bb_data (void)
550 : : {
551 : 177736 : basic_block bb;
552 : :
553 : 177736 : if (lra_dump_file == NULL)
554 : : return;
555 : 1 : dump_cands (lra_dump_file);
556 : 43 : FOR_EACH_BB_FN (bb, cfun)
557 : : {
558 : 42 : fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
559 : : /* Livein */
560 : 42 : fprintf (lra_dump_file, " register live in:");
561 : 42 : dump_regset (df_get_live_in (bb), lra_dump_file);
562 : 42 : putc ('\n', lra_dump_file);
563 : : /* Liveout */
564 : 42 : fprintf (lra_dump_file, " register live out:");
565 : 42 : dump_regset (df_get_live_out (bb), lra_dump_file);
566 : 42 : putc ('\n', lra_dump_file);
567 : : /* Changed/dead regs: */
568 : 42 : fprintf (lra_dump_file, " changed regs:");
569 : 42 : dump_regset (&get_remat_bb_data (bb)->changed_regs, lra_dump_file);
570 : 42 : putc ('\n', lra_dump_file);
571 : 42 : fprintf (lra_dump_file, " dead regs:");
572 : 42 : dump_regset (&get_remat_bb_data (bb)->dead_regs, lra_dump_file);
573 : 42 : putc ('\n', lra_dump_file);
574 : 42 : lra_dump_bitmap_with_title ("cands generated in BB",
575 : 42 : &get_remat_bb_data (bb)->gen_cands, bb->index);
576 : 42 : lra_dump_bitmap_with_title ("livein cands in BB",
577 : 42 : &get_remat_bb_data (bb)->livein_cands, bb->index);
578 : 42 : lra_dump_bitmap_with_title ("pavin cands in BB",
579 : 42 : &get_remat_bb_data (bb)->pavin_cands, bb->index);
580 : 42 : lra_dump_bitmap_with_title ("pavout cands in BB",
581 : 42 : &get_remat_bb_data (bb)->pavout_cands, bb->index);
582 : 42 : lra_dump_bitmap_with_title ("avin cands in BB",
583 : 42 : &get_remat_bb_data (bb)->avin_cands, bb->index);
584 : 42 : lra_dump_bitmap_with_title ("avout cands in BB",
585 : 42 : &get_remat_bb_data (bb)->avout_cands, bb->index);
586 : : }
587 : 1 : fprintf (lra_dump_file, "subreg regs:");
588 : 1 : dump_regset (&subreg_regs, lra_dump_file);
589 : 1 : putc ('\n', lra_dump_file);
590 : : }
591 : :
592 : : /* Free all BB data. */
593 : : static void
594 : 177736 : finish_remat_bb_data (void)
595 : : {
596 : 177736 : basic_block bb;
597 : :
598 : 6118648 : FOR_EACH_BB_FN (bb, cfun)
599 : : {
600 : 5940912 : bitmap_clear (&get_remat_bb_data (bb)->avout_cands);
601 : 5940912 : bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
602 : 5940912 : bitmap_clear (&get_remat_bb_data (bb)->pavout_cands);
603 : 5940912 : bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
604 : 5940912 : bitmap_clear (&get_remat_bb_data (bb)->livein_cands);
605 : 5940912 : bitmap_clear (&get_remat_bb_data (bb)->gen_cands);
606 : 5940912 : bitmap_clear (&get_remat_bb_data (bb)->dead_regs);
607 : 5940912 : bitmap_clear (&get_remat_bb_data (bb)->changed_regs);
608 : : }
609 : 177736 : free (remat_bb_data);
610 : 177736 : }
611 : :
612 : :
613 : :
614 : : /* Update changed_regs, dead_regs, subreg_regs of BB from INSN. */
615 : : static void
616 : 39558057 : set_bb_regs (basic_block bb, rtx_insn *insn)
617 : : {
618 : 39558057 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
619 : 39558057 : remat_bb_data_t bb_info = get_remat_bb_data (bb);
620 : 39558057 : struct lra_insn_reg *reg;
621 : :
622 : 102536839 : for (reg = id->regs; reg != NULL; reg = reg->next)
623 : : {
624 : 62978782 : unsigned regno = reg->regno;
625 : 62978782 : if (reg->type != OP_IN)
626 : 27692087 : bitmap_set_bit (&bb_info->changed_regs, regno);
627 : 35286695 : else if (find_regno_note (insn, REG_DEAD, regno) != NULL)
628 : 20415503 : bitmap_set_bit (&bb_info->dead_regs, regno);
629 : 62978782 : if (regno >= FIRST_PSEUDO_REGISTER && reg->subreg_p)
630 : 552005 : bitmap_set_bit (&subreg_regs, regno);
631 : : }
632 : 39558057 : if (CALL_P (insn))
633 : : {
634 : : /* Partially-clobbered registers might still be live. */
635 : 2379116 : HARD_REG_SET clobbers = insn_callee_abi (insn).full_reg_clobbers ();
636 : 2379116 : bitmap_ior_into (&get_remat_bb_data (bb)->dead_regs,
637 : 2379116 : bitmap_view<HARD_REG_SET> (clobbers));
638 : : }
639 : 39558057 : }
640 : :
641 : : /* Calculate changed_regs and dead_regs for each BB. */
642 : : static void
643 : 177736 : calculate_local_reg_remat_bb_data (void)
644 : : {
645 : 177736 : basic_block bb;
646 : 177736 : rtx_insn *insn;
647 : :
648 : 6118648 : FOR_EACH_BB_FN (bb, cfun)
649 : 88839848 : FOR_BB_INSNS (bb, insn)
650 : 82898936 : if (NONDEBUG_INSN_P (insn))
651 : 39558057 : set_bb_regs (bb, insn);
652 : 177736 : }
653 : :
654 : :
655 : :
656 : : /* Return true if REG overlaps an input operand or non-input hard register of
657 : : INSN. Basically the function returns false if we can move rematerialization
658 : : candidate INSN through another insn with output REG or dead input REG (we
659 : : consider it to avoid extending reg live range) with possible output pseudo
660 : : renaming in INSN. */
661 : : static bool
662 : 4246422 : reg_overlap_for_remat_p (lra_insn_reg *reg, rtx_insn *insn)
663 : : {
664 : 4246422 : int iter;
665 : 4246422 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
666 : 4246422 : struct lra_static_insn_data *static_id = id->insn_static_data;
667 : 4246422 : unsigned regno = reg->regno;
668 : 4246422 : int nregs;
669 : :
670 : 4246422 : if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] >= 0)
671 : 2946881 : regno = reg_renumber[regno];
672 : 3573554 : if (regno >= FIRST_PSEUDO_REGISTER)
673 : : nregs = 1;
674 : : else
675 : 3619749 : nregs = hard_regno_nregs (regno, reg->biggest_mode);
676 : :
677 : 4246422 : struct lra_insn_reg *reg2;
678 : :
679 : 11635019 : for (iter = 0; iter < 2; iter++)
680 : 7946296 : for (reg2 = (iter == 0 ? id->regs : static_id->hard_regs);
681 : 14502758 : reg2 != NULL;
682 : 6556462 : reg2 = reg2->next)
683 : : {
684 : 7114161 : int nregs2;
685 : 7114161 : unsigned regno2 = reg2->regno;
686 : :
687 : 7114161 : if (reg2->type != OP_IN && regno2 >= FIRST_PSEUDO_REGISTER)
688 : 4246656 : continue;
689 : :
690 : 2765154 : if (regno2 >= FIRST_PSEUDO_REGISTER && reg_renumber[regno2] >= 0)
691 : 2765154 : regno2 = reg_renumber[regno2];
692 : 2765154 : if (regno2 >= FIRST_PSEUDO_REGISTER)
693 : : nregs2 = 1;
694 : : else
695 : 2867505 : nregs2 = hard_regno_nregs (regno2, reg->biggest_mode);
696 : :
697 : 2867505 : if ((regno2 + nregs2 - 1 >= regno && regno2 < regno + nregs)
698 : 2309806 : || (regno + nregs - 1 >= regno2 && regno < regno2 + nregs2))
699 : : return true;
700 : : }
701 : : return false;
702 : : }
703 : :
704 : : /* Return true if a call used register is an input operand of INSN. */
705 : : static bool
706 : 26696 : call_used_input_regno_present_p (const function_abi &abi, rtx_insn *insn)
707 : : {
708 : 26696 : int iter;
709 : 26696 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
710 : 26696 : struct lra_static_insn_data *static_id = id->insn_static_data;
711 : 26696 : struct lra_insn_reg *reg;
712 : :
713 : 80088 : for (iter = 0; iter < 2; iter++)
714 : 53392 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
715 : 104386 : reg != NULL;
716 : 50994 : reg = reg->next)
717 : 50994 : if (reg->type == OP_IN
718 : 22779 : && reg->regno < FIRST_PSEUDO_REGISTER
719 : 50994 : && abi.clobbers_reg_p (reg->biggest_mode, reg->regno))
720 : : return true;
721 : : return false;
722 : : }
723 : :
724 : : /* Calculate livein_cands for each BB. */
725 : : static void
726 : 177736 : calculate_livein_cands (void)
727 : : {
728 : 177736 : basic_block bb;
729 : :
730 : 6118648 : FOR_EACH_BB_FN (bb, cfun)
731 : : {
732 : 5940912 : bitmap livein_regs = df_get_live_in (bb);
733 : 5940912 : bitmap livein_cands = &get_remat_bb_data (bb)->livein_cands;
734 : 58417267 : for (unsigned int i = 0; i < cands_num; i++)
735 : : {
736 : 52476355 : cand_t cand = all_cands[i];
737 : 52476355 : lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
738 : 52476355 : struct lra_insn_reg *reg;
739 : :
740 : 105594634 : for (reg = id->regs; reg != NULL; reg = reg->next)
741 : 88414698 : if (reg->type == OP_IN && ! bitmap_bit_p (livein_regs, reg->regno))
742 : : break;
743 : 52476355 : if (reg == NULL)
744 : 17179936 : bitmap_set_bit (livein_cands, i);
745 : : }
746 : : }
747 : 177736 : }
748 : :
749 : : /* Calculate gen_cands for each BB. */
750 : : static void
751 : 177736 : calculate_gen_cands (void)
752 : : {
753 : 177736 : basic_block bb;
754 : 177736 : bitmap gen_cands;
755 : 177736 : rtx_insn *insn;
756 : :
757 : 6118648 : FOR_EACH_BB_FN (bb, cfun)
758 : : {
759 : 5940912 : gen_cands = &get_remat_bb_data (bb)->gen_cands;
760 : 5940912 : auto_bitmap gen_insns (®_obstack);
761 : 88839848 : FOR_BB_INSNS (bb, insn)
762 : 82898936 : if (INSN_P (insn))
763 : : {
764 : 70522159 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
765 : 70522159 : struct lra_static_insn_data *static_id = id->insn_static_data;
766 : 70522159 : struct lra_insn_reg *reg;
767 : 70522159 : unsigned int uid;
768 : 70522159 : bitmap_iterator bi;
769 : 70522159 : cand_t cand;
770 : 70522159 : rtx set;
771 : 70522159 : int iter;
772 : 70522159 : int src_regno = -1, dst_regno = -1;
773 : :
774 : 70522159 : if ((set = single_set (insn)) != NULL
775 : 70522159 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
776 : : {
777 : 11384061 : src_regno = REGNO (SET_SRC (set));
778 : 11384061 : dst_regno = REGNO (SET_DEST (set));
779 : : }
780 : :
781 : : /* Update gen_cands: */
782 : 70522159 : bitmap_clear (&temp_bitmap);
783 : 211566477 : for (iter = 0; iter < 2; iter++)
784 : 141044318 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
785 : 220728858 : reg != NULL;
786 : 79684540 : reg = reg->next)
787 : 79684540 : if (reg->type != OP_IN
788 : 79684540 : || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
789 : 59865251 : EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
790 : : {
791 : 1905548 : rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
792 : :
793 : 1905548 : cand = insn_to_cand[INSN_UID (insn2)];
794 : 1905548 : gcc_assert (cand != NULL);
795 : : /* Ignore the reload insn. */
796 : 1905548 : if (src_regno == cand->reload_regno
797 : 776288 : && dst_regno == cand->regno)
798 : 39399 : continue;
799 : 1866149 : if (cand->regno == reg->regno
800 : 1866149 : || reg_overlap_for_remat_p (reg, insn2))
801 : : {
802 : 264564 : bitmap_clear_bit (gen_cands, cand->index);
803 : 264564 : bitmap_set_bit (&temp_bitmap, uid);
804 : : }
805 : : }
806 : :
807 : 70522159 : if (CALL_P (insn))
808 : : {
809 : 2379116 : function_abi callee_abi = insn_callee_abi (insn);
810 : 2387414 : EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
811 : : {
812 : 8298 : rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
813 : :
814 : 8298 : cand = insn_to_cand[INSN_UID (insn2)];
815 : 8298 : gcc_assert (cand != NULL);
816 : 8298 : if (call_used_input_regno_present_p (callee_abi, insn2))
817 : : {
818 : 0 : bitmap_clear_bit (gen_cands, cand->index);
819 : 0 : bitmap_set_bit (&temp_bitmap, uid);
820 : : }
821 : : }
822 : : }
823 : 70522159 : bitmap_and_compl_into (gen_insns, &temp_bitmap);
824 : :
825 : 70522159 : cand = insn_to_cand[INSN_UID (insn)];
826 : 70522159 : if (cand != NULL)
827 : : {
828 : 312133 : bitmap_set_bit (gen_cands, cand->index);
829 : 312133 : bitmap_set_bit (gen_insns, INSN_UID (insn));
830 : : }
831 : : }
832 : 5940912 : }
833 : 177736 : }
834 : :
835 : :
836 : :
837 : : /* The common transfer function used by the DF equation solver to
838 : : propagate (partial) availability info BB_IN to BB_OUT through block
839 : : with BB_INDEX according to the following equation:
840 : :
841 : : bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
842 : : */
843 : : static bool
844 : 12778735 : cand_trans_fun (int bb_index, bitmap bb_in, bitmap bb_out)
845 : : {
846 : 12778735 : remat_bb_data_t bb_info;
847 : 12778735 : bitmap bb_livein, bb_changed_regs, bb_dead_regs;
848 : 12778735 : unsigned int cid;
849 : 12778735 : bitmap_iterator bi;
850 : :
851 : 12778735 : bb_info = get_remat_bb_data_by_index (bb_index);
852 : 12778735 : bb_livein = &bb_info->livein_cands;
853 : 12778735 : bb_changed_regs = &bb_info->changed_regs;
854 : 12778735 : bb_dead_regs = &bb_info->dead_regs;
855 : : /* Calculate killed avin cands -- cands whose regs are changed or
856 : : becoming dead in the BB. We calculate it here as we hope that
857 : : repeated calculations are compensated by smaller size of BB_IN in
858 : : comparison with all candidates number. */
859 : 12778735 : bitmap_clear (&temp_bitmap);
860 : 21586890 : EXECUTE_IF_SET_IN_BITMAP (bb_in, 0, cid, bi)
861 : : {
862 : 8808155 : cand_t cand = all_cands[cid];
863 : 8808155 : lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
864 : 8808155 : struct lra_insn_reg *reg;
865 : :
866 : 8808155 : if (! bitmap_bit_p (bb_livein, cid))
867 : : {
868 : 93274 : bitmap_set_bit (&temp_bitmap, cid);
869 : 93274 : continue;
870 : : }
871 : 17494853 : for (reg = id->regs; reg != NULL; reg = reg->next)
872 : : /* Ignore all outputs which are not the regno for
873 : : rematerialization. */
874 : 8983553 : if (reg->type == OP_OUT && reg->regno != cand->regno)
875 : 400654 : continue;
876 : 8582899 : else if (bitmap_bit_p (bb_changed_regs, reg->regno)
877 : 8582899 : || bitmap_bit_p (bb_dead_regs, reg->regno))
878 : : {
879 : 203581 : bitmap_set_bit (&temp_bitmap, cid);
880 : 203581 : break;
881 : : }
882 : : /* Check regno for rematerialization. */
883 : 8714881 : if (bitmap_bit_p (bb_changed_regs, cand->regno)
884 : 8714881 : || bitmap_bit_p (bb_dead_regs, cand->regno))
885 : 168865 : bitmap_set_bit (&temp_bitmap, cid);
886 : : }
887 : 12778735 : return bitmap_ior_and_compl (bb_out,
888 : 12778735 : &bb_info->gen_cands, bb_in, &temp_bitmap);
889 : : }
890 : :
891 : :
892 : :
893 : : /* The transfer function used by the DF equation solver to propagate
894 : : partial candidate availability info through block with BB_INDEX
895 : : according to the following equation:
896 : :
897 : : bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
898 : : */
899 : : static bool
900 : 6482351 : cand_pav_trans_fun (int bb_index)
901 : : {
902 : 6482351 : remat_bb_data_t bb_info;
903 : :
904 : 6482351 : bb_info = get_remat_bb_data_by_index (bb_index);
905 : 6482351 : return cand_trans_fun (bb_index, &bb_info->pavin_cands,
906 : 6482351 : &bb_info->pavout_cands);
907 : : }
908 : :
909 : : /* The confluence function used by the DF equation solver to set up
910 : : cand_pav info for a block BB without predecessor. */
911 : : static void
912 : 178978 : cand_pav_con_fun_0 (basic_block bb)
913 : : {
914 : 178978 : bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
915 : 178978 : }
916 : :
917 : : /* The confluence function used by the DF equation solver to propagate
918 : : partial candidate availability info from predecessor to successor
919 : : on edge E (pred->bb) according to the following equation:
920 : :
921 : : bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
922 : : */
923 : : static bool
924 : 9306730 : cand_pav_con_fun_n (edge e)
925 : : {
926 : 9306730 : basic_block pred = e->src;
927 : 9306730 : basic_block bb = e->dest;
928 : 9306730 : remat_bb_data_t bb_info;
929 : 9306730 : bitmap bb_pavin, pred_pavout;
930 : :
931 : 9306730 : bb_info = get_remat_bb_data (bb);
932 : 9306730 : bb_pavin = &bb_info->pavin_cands;
933 : 9306730 : pred_pavout = &get_remat_bb_data (pred)->pavout_cands;
934 : 9306730 : return bitmap_ior_into (bb_pavin, pred_pavout);
935 : : }
936 : :
937 : :
938 : :
939 : : /* The transfer function used by the DF equation solver to propagate
940 : : candidate availability info through block with BB_INDEX according
941 : : to the following equation:
942 : :
943 : : bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
944 : : */
945 : : static bool
946 : 6296384 : cand_av_trans_fun (int bb_index)
947 : : {
948 : 6296384 : remat_bb_data_t bb_info;
949 : :
950 : 6296384 : bb_info = get_remat_bb_data_by_index (bb_index);
951 : 6296384 : return cand_trans_fun (bb_index, &bb_info->avin_cands,
952 : 6296384 : &bb_info->avout_cands);
953 : : }
954 : :
955 : : /* The confluence function used by the DF equation solver to set up
956 : : cand_av info for a block BB without predecessor. */
957 : : static void
958 : 178978 : cand_av_con_fun_0 (basic_block bb)
959 : : {
960 : 178978 : bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
961 : 178978 : }
962 : :
963 : : /* The confluence function used by the DF equation solver to propagate
964 : : cand_av info from predecessor to successor on edge E (pred->bb)
965 : : according to the following equation:
966 : :
967 : : bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
968 : : */
969 : : static bool
970 : 8955502 : cand_av_con_fun_n (edge e)
971 : : {
972 : 8955502 : basic_block pred = e->src;
973 : 8955502 : basic_block bb = e->dest;
974 : 8955502 : remat_bb_data_t bb_info;
975 : 8955502 : bitmap bb_avin, pred_avout;
976 : :
977 : 8955502 : bb_info = get_remat_bb_data (bb);
978 : 8955502 : bb_avin = &bb_info->avin_cands;
979 : 8955502 : pred_avout = &get_remat_bb_data (pred)->avout_cands;
980 : 8955502 : return bitmap_and_into (bb_avin, pred_avout);
981 : : }
982 : :
983 : : /* Calculate available candidates for each BB. */
984 : : static void
985 : 177736 : calculate_global_remat_bb_data (void)
986 : : {
987 : 177736 : basic_block bb;
988 : :
989 : 177736 : df_simple_dataflow
990 : 177736 : (DF_FORWARD, NULL, cand_pav_con_fun_0, cand_pav_con_fun_n,
991 : : cand_pav_trans_fun, &all_blocks,
992 : : df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
993 : : /* Initialize avin by pavin. */
994 : 6118648 : FOR_EACH_BB_FN (bb, cfun)
995 : 5940912 : bitmap_copy (&get_remat_bb_data (bb)->avin_cands,
996 : 5940912 : &get_remat_bb_data (bb)->pavin_cands);
997 : 177736 : df_simple_dataflow
998 : 177736 : (DF_FORWARD, NULL, cand_av_con_fun_0, cand_av_con_fun_n,
999 : : cand_av_trans_fun, &all_blocks,
1000 : : df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
1001 : 177736 : }
1002 : :
1003 : :
1004 : :
1005 : : /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
1006 : : static void
1007 : 106 : change_sp_offset (rtx_insn *insns, poly_int64 sp_offset)
1008 : : {
1009 : 212 : for (rtx_insn *insn = insns; insn != NULL; insn = NEXT_INSN (insn))
1010 : 106 : eliminate_regs_in_insn (insn, false, false, sp_offset);
1011 : 106 : }
1012 : :
1013 : : /* Return start hard register of REG (can be a hard or a pseudo reg)
1014 : : or -1 (if it is a spilled pseudo). Return number of hard registers
1015 : : occupied by REG through parameter NREGS if the start hard reg is
1016 : : not negative. */
1017 : : static int
1018 : 47667976 : get_hard_regs (struct lra_insn_reg *reg, int &nregs)
1019 : : {
1020 : 47667976 : int regno = reg->regno;
1021 : 47667976 : int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
1022 : :
1023 : 47667976 : if (hard_regno >= 0)
1024 : 44820342 : nregs = hard_regno_nregs (hard_regno, reg->biggest_mode);
1025 : 47667976 : return hard_regno;
1026 : : }
1027 : :
1028 : : /* Make copy of and register scratch pseudos in rematerialized insn
1029 : : REMAT_INSN. */
1030 : : static void
1031 : 2985 : update_scratch_ops (rtx_insn *remat_insn)
1032 : : {
1033 : 2985 : lra_insn_recog_data_t id = lra_get_insn_recog_data (remat_insn);
1034 : 2985 : struct lra_static_insn_data *static_id = id->insn_static_data;
1035 : 9694 : for (int i = 0; i < static_id->n_operands; i++)
1036 : : {
1037 : 6709 : rtx *loc = id->operand_loc[i];
1038 : 6709 : if (! REG_P (*loc))
1039 : 2511 : continue;
1040 : 4198 : int regno = REGNO (*loc);
1041 : 4198 : if (! ira_former_scratch_p (regno))
1042 : 4198 : continue;
1043 : 0 : *loc = lra_create_new_reg (GET_MODE (*loc), *loc,
1044 : : lra_get_allocno_class (regno), NULL,
1045 : : "scratch pseudo copy");
1046 : 0 : ira_register_new_scratch_op (remat_insn, i, id->icode);
1047 : : }
1048 : :
1049 : 2985 : }
1050 : :
1051 : : /* Insert rematerialization insns using the data-flow data calculated
1052 : : earlier. */
1053 : : static bool
1054 : 177736 : do_remat (void)
1055 : : {
1056 : 177736 : unsigned regno;
1057 : 177736 : rtx_insn *insn;
1058 : 177736 : basic_block bb;
1059 : 177736 : bool changed_p = false;
1060 : : /* Living hard regs and hard registers of living pseudos. */
1061 : 177736 : HARD_REG_SET live_hard_regs;
1062 : 177736 : bitmap_iterator bi;
1063 : :
1064 : 177736 : auto_bitmap avail_cands (®_obstack);
1065 : 177736 : auto_bitmap active_cands (®_obstack);
1066 : 6118648 : FOR_EACH_BB_FN (bb, cfun)
1067 : : {
1068 : 5940912 : CLEAR_HARD_REG_SET (live_hard_regs);
1069 : 63362228 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), 0, regno, bi)
1070 : : {
1071 : 114842632 : int hard_regno = regno < FIRST_PSEUDO_REGISTER
1072 : 57421316 : ? regno
1073 : 48376588 : : reg_renumber[regno];
1074 : 57421316 : if (hard_regno >= 0)
1075 : 32241736 : SET_HARD_REG_BIT (live_hard_regs, hard_regno);
1076 : : }
1077 : 5940912 : bitmap_and (avail_cands, &get_remat_bb_data (bb)->avin_cands,
1078 : 5940912 : &get_remat_bb_data (bb)->livein_cands);
1079 : : /* Activating insns are always in the same block as their corresponding
1080 : : remat insn, so at the start of a block the two bitsets are equal. */
1081 : 5940912 : bitmap_copy (active_cands, avail_cands);
1082 : 88839848 : FOR_BB_INSNS (bb, insn)
1083 : : {
1084 : 82898936 : if (!NONDEBUG_INSN_P (insn))
1085 : 43343864 : continue;
1086 : :
1087 : 39558057 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
1088 : 39558057 : struct lra_static_insn_data *static_id = id->insn_static_data;
1089 : 39558057 : struct lra_insn_reg *reg;
1090 : 39558057 : cand_t cand;
1091 : 39558057 : unsigned int cid;
1092 : 39558057 : bitmap_iterator bi;
1093 : 39558057 : rtx set;
1094 : 39558057 : int iter;
1095 : 39558057 : int src_regno = -1, dst_regno = -1;
1096 : :
1097 : 39558057 : if ((set = single_set (insn)) != NULL
1098 : 39558057 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
1099 : : {
1100 : 11384061 : src_regno = REGNO (SET_SRC (set));
1101 : 11384061 : dst_regno = REGNO (SET_DEST (set));
1102 : : }
1103 : :
1104 : 39558057 : cand = NULL;
1105 : : /* Check possibility of rematerialization (hard reg or
1106 : : unpsilled pseudo <- spilled pseudo): */
1107 : 39558057 : if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER
1108 : 10033201 : && reg_renumber[src_regno] < 0
1109 : 1685802 : && (dst_regno < FIRST_PSEUDO_REGISTER
1110 : 1498340 : || reg_renumber[dst_regno] >= 0))
1111 : : {
1112 : 1685802 : for (cand = regno_cands[src_regno];
1113 : 2306626 : cand != NULL;
1114 : 620824 : cand = cand->next_regno_cand)
1115 : 624581 : if (bitmap_bit_p (avail_cands, cand->index)
1116 : 624581 : && bitmap_bit_p (active_cands, cand->index))
1117 : : break;
1118 : : }
1119 : 1685802 : int i, hard_regno, nregs;
1120 : 1685802 : int dst_hard_regno, dst_nregs;
1121 : 1685802 : rtx_insn *remat_insn = NULL;
1122 : 1685802 : poly_int64 cand_sp_offset = 0;
1123 : 1685802 : if (cand != NULL)
1124 : : {
1125 : 3757 : lra_insn_recog_data_t cand_id
1126 : 3757 : = lra_get_insn_recog_data (cand->insn);
1127 : 3757 : struct lra_static_insn_data *static_cand_id
1128 : : = cand_id->insn_static_data;
1129 : 3757 : rtx saved_op = *cand_id->operand_loc[cand->nop];
1130 : :
1131 : : /* Check clobbers do not kill something living. */
1132 : 3757 : gcc_assert (REG_P (saved_op));
1133 : 3757 : int ignore_regno = REGNO (saved_op);
1134 : :
1135 : 7514 : dst_hard_regno = dst_regno < FIRST_PSEUDO_REGISTER
1136 : 3757 : ? dst_regno : reg_renumber[dst_regno];
1137 : 3757 : gcc_assert (dst_hard_regno >= 0);
1138 : 3757 : machine_mode mode = GET_MODE (SET_DEST (set));
1139 : 3757 : dst_nregs = hard_regno_nregs (dst_hard_regno, mode);
1140 : :
1141 : 9616 : for (reg = cand_id->regs; reg != NULL; reg = reg->next)
1142 : 5861 : if (reg->type != OP_IN && reg->regno != ignore_regno)
1143 : : {
1144 : 2 : hard_regno = get_hard_regs (reg, nregs);
1145 : 2 : gcc_assert (hard_regno >= 0);
1146 : 2 : for (i = 0; i < nregs; i++)
1147 : 2 : if (TEST_HARD_REG_BIT (live_hard_regs, hard_regno + i))
1148 : : break;
1149 : 2 : if (i < nregs)
1150 : : break;
1151 : : /* Ensure the clobber also doesn't overlap dst_regno. */
1152 : 0 : if (hard_regno + nregs > dst_hard_regno
1153 : 0 : && hard_regno < dst_hard_regno + dst_nregs)
1154 : : break;
1155 : : }
1156 : :
1157 : 3757 : if (reg == NULL)
1158 : : {
1159 : 3755 : for (reg = static_cand_id->hard_regs;
1160 : 4221 : reg != NULL;
1161 : 466 : reg = reg->next)
1162 : 466 : if (reg->type != OP_IN)
1163 : : {
1164 : 466 : if (TEST_HARD_REG_BIT (live_hard_regs, reg->regno))
1165 : : break;
1166 : 466 : if (reg->regno >= dst_hard_regno
1167 : 371 : && reg->regno < dst_hard_regno + dst_nregs)
1168 : : break;
1169 : : }
1170 : : }
1171 : :
1172 : 3755 : if (reg == NULL)
1173 : : {
1174 : 3755 : *cand_id->operand_loc[cand->nop] = SET_DEST (set);
1175 : 3755 : lra_update_insn_regno_info (cand->insn);
1176 : 3755 : bool ok_p = lra_constrain_insn (cand->insn);
1177 : 3755 : if (ok_p)
1178 : : {
1179 : 2985 : rtx remat_pat = copy_insn (PATTERN (cand->insn));
1180 : :
1181 : 2985 : start_sequence ();
1182 : 2985 : emit_insn (remat_pat);
1183 : 2985 : remat_insn = get_insns ();
1184 : 2985 : end_sequence ();
1185 : 2985 : if (recog_memoized (remat_insn) < 0)
1186 : 0 : remat_insn = NULL;
1187 : 2985 : cand_sp_offset = cand_id->sp_offset;
1188 : : }
1189 : 3755 : *cand_id->operand_loc[cand->nop] = saved_op;
1190 : 3755 : lra_update_insn_regno_info (cand->insn);
1191 : : }
1192 : : }
1193 : :
1194 : 39558057 : bitmap_clear (&temp_bitmap);
1195 : : /* Update avail_cands (see analogous code for
1196 : : calculate_gen_cands). */
1197 : 158232228 : for (iter = 0; iter < 2; iter++)
1198 : 79116114 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
1199 : 152030720 : reg != NULL;
1200 : 72914606 : reg = reg->next)
1201 : 72914606 : if (reg->type != OP_IN
1202 : 72914606 : || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1203 : 60393711 : EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1204 : : {
1205 : 2434008 : cand = all_cands[cid];
1206 : :
1207 : : /* Ignore the reload insn. */
1208 : 2434008 : if (src_regno == cand->reload_regno
1209 : 1048414 : && dst_regno == cand->regno)
1210 : 39399 : continue;
1211 : 2394609 : if (cand->regno == reg->regno
1212 : 2394609 : || reg_overlap_for_remat_p (reg, cand->insn))
1213 : 307471 : bitmap_set_bit (&temp_bitmap, cand->index);
1214 : : }
1215 : :
1216 : 39558057 : if (CALL_P (insn))
1217 : : {
1218 : 2379116 : function_abi callee_abi = insn_callee_abi (insn);
1219 : 2397514 : EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1220 : : {
1221 : 18398 : cand = all_cands[cid];
1222 : :
1223 : 18398 : if (call_used_input_regno_present_p (callee_abi, cand->insn))
1224 : 0 : bitmap_set_bit (&temp_bitmap, cand->index);
1225 : : }
1226 : : }
1227 : :
1228 : 39558057 : bitmap_and_compl_into (avail_cands, &temp_bitmap);
1229 : :
1230 : : /* Now see whether a candidate is made active or available
1231 : : by this insn. */
1232 : 39558057 : cand = insn_to_cand_activation[INSN_UID (insn)];
1233 : 39558057 : if (cand)
1234 : 20691 : bitmap_set_bit (active_cands, cand->index);
1235 : :
1236 : 39558057 : cand = insn_to_cand[INSN_UID (insn)];
1237 : 39558057 : if (cand != NULL)
1238 : : {
1239 : 312133 : bitmap_set_bit (avail_cands, cand->index);
1240 : 312133 : if (cand->reload_regno == -1)
1241 : 291447 : bitmap_set_bit (active_cands, cand->index);
1242 : : else
1243 : 20686 : bitmap_clear_bit (active_cands, cand->index);
1244 : : }
1245 : :
1246 : 39558057 : if (remat_insn != NULL)
1247 : : {
1248 : 2985 : poly_int64 sp_offset_change = cand_sp_offset - id->sp_offset;
1249 : 2985 : if (maybe_ne (sp_offset_change, 0))
1250 : 106 : change_sp_offset (remat_insn, sp_offset_change);
1251 : 2985 : update_scratch_ops (remat_insn);
1252 : 2985 : lra_process_new_insns (insn, remat_insn, NULL,
1253 : : "Inserting rematerialization insn");
1254 : 2985 : lra_set_insn_deleted (insn);
1255 : 2985 : changed_p = true;
1256 : 2985 : continue;
1257 : 2985 : }
1258 : :
1259 : : /* Update live hard regs: */
1260 : 102527884 : for (reg = id->regs; reg != NULL; reg = reg->next)
1261 : 62972812 : if (reg->type == OP_IN
1262 : 62972812 : && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1263 : : {
1264 : 20413027 : if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1265 : 1213770 : continue;
1266 : 38738568 : for (i = 0; i < nregs; i++)
1267 : 19539311 : CLEAR_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1268 : : }
1269 : : /* Process also hard regs (e.g. CC register) which are part
1270 : : of insn definition. */
1271 : 49490896 : for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1272 : 9935824 : if (reg->type == OP_IN
1273 : 9935824 : && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1274 : 2685756 : CLEAR_HARD_REG_BIT (live_hard_regs, reg->regno);
1275 : : /* Inputs have been processed, now process outputs. */
1276 : 102527884 : for (reg = id->regs; reg != NULL; reg = reg->next)
1277 : 62972812 : if (reg->type != OP_IN
1278 : 62972812 : && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1279 : : {
1280 : 27254947 : if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1281 : 1633864 : continue;
1282 : 51873027 : for (i = 0; i < nregs; i++)
1283 : 26251944 : SET_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1284 : : }
1285 : 49490896 : for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1286 : 9935824 : if (reg->type != OP_IN
1287 : 9935824 : && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1288 : 2819011 : SET_HARD_REG_BIT (live_hard_regs, reg->regno);
1289 : : }
1290 : : }
1291 : 177736 : return changed_p;
1292 : 177736 : }
1293 : :
1294 : :
1295 : :
1296 : : /* Current number of rematerialization iteration. */
1297 : : int lra_rematerialization_iter;
1298 : :
1299 : : /* Entry point of the rematerialization sub-pass. Return true if we
1300 : : did any rematerialization. */
1301 : : bool
1302 : 192809 : lra_remat (void)
1303 : : {
1304 : 192809 : basic_block bb;
1305 : 192809 : bool result;
1306 : 192809 : int max_regno = max_reg_num ();
1307 : :
1308 : 192809 : if (! flag_lra_remat)
1309 : : return false;
1310 : 177736 : lra_rematerialization_iter++;
1311 : 177736 : if (lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
1312 : : return false;
1313 : 177736 : if (lra_dump_file != NULL)
1314 : 1 : fprintf (lra_dump_file,
1315 : : "\n******** Rematerialization #%d: ********\n\n",
1316 : : lra_rematerialization_iter);
1317 : 177736 : timevar_push (TV_LRA_REMAT);
1318 : 177736 : insn_to_cand = XCNEWVEC (cand_t, get_max_uid ());
1319 : 177736 : insn_to_cand_activation = XCNEWVEC (cand_t, get_max_uid ());
1320 : 177736 : regno_cands = XCNEWVEC (cand_t, max_regno);
1321 : 177736 : all_cands.create (8000);
1322 : 177736 : initiate_cand_table ();
1323 : 177736 : create_remat_bb_data ();
1324 : 177736 : bitmap_initialize (&temp_bitmap, ®_obstack);
1325 : 177736 : bitmap_initialize (&subreg_regs, ®_obstack);
1326 : 177736 : calculate_local_reg_remat_bb_data ();
1327 : 177736 : create_cands ();
1328 : 177736 : calculate_livein_cands ();
1329 : 177736 : calculate_gen_cands ();
1330 : 177736 : bitmap_initialize (&all_blocks, ®_obstack);
1331 : 6474120 : FOR_ALL_BB_FN (bb, cfun)
1332 : 6296384 : bitmap_set_bit (&all_blocks, bb->index);
1333 : 177736 : calculate_global_remat_bb_data ();
1334 : 177736 : dump_candidates_and_remat_bb_data ();
1335 : 177736 : result = do_remat ();
1336 : 177736 : if (result)
1337 : 2025 : lra_dump_insns_if_possible ("changed func after rematerialization");
1338 : 177736 : all_cands.release ();
1339 : 177736 : bitmap_clear (&temp_bitmap);
1340 : 177736 : bitmap_clear (&subreg_regs);
1341 : 177736 : finish_remat_bb_data ();
1342 : 177736 : finish_cand_table ();
1343 : 177736 : bitmap_clear (&all_blocks);
1344 : 177736 : free (regno_cands);
1345 : 177736 : free (insn_to_cand);
1346 : 177736 : free (insn_to_cand_activation);
1347 : 177736 : timevar_pop (TV_LRA_REMAT);
1348 : 177736 : return result;
1349 : : }
|
