Branch data Line data Source code
1 : : /* Rematerialize pseudos values.
2 : : Copyright (C) 2014-2024 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 : 118105803 : get_remat_bb_data (basic_block bb)
155 : : {
156 : 118105803 : return &remat_bb_data[(bb)->index];
157 : : }
158 : :
159 : : static inline remat_bb_data_t
160 : 21522080 : get_remat_bb_data_by_index (int index)
161 : : {
162 : 21522080 : 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 : 299620 : cand_hash (const void *cand)
175 : : {
176 : 299620 : const_cand_t c = (const_cand_t) cand;
177 : 299620 : lra_insn_recog_data_t id = lra_get_insn_recog_data (c->insn);
178 : 299620 : struct lra_static_insn_data *static_id = id->insn_static_data;
179 : 299620 : int nops = static_id->n_operands;
180 : 299620 : hashval_t hash = 0;
181 : :
182 : 908805 : for (int i = 0; i < nops; i++)
183 : 609185 : if (i == c->nop)
184 : 299620 : hash = iterative_hash_object (c->regno, hash);
185 : 309565 : else if (static_id->operand[i].type == OP_IN)
186 : 309536 : hash = iterative_hash_object (*id->operand_loc[i], hash);
187 : 299620 : 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 : 70404 : cand_eq_p (const void *cand1, const void *cand2)
195 : : {
196 : 70404 : const_cand_t c1 = (const_cand_t) cand1;
197 : 70404 : const_cand_t c2 = (const_cand_t) cand2;
198 : 70404 : lra_insn_recog_data_t id1 = lra_get_insn_recog_data (c1->insn);
199 : 70404 : lra_insn_recog_data_t id2 = lra_get_insn_recog_data (c2->insn);
200 : 70404 : struct lra_static_insn_data *static_id1 = id1->insn_static_data;
201 : 70404 : int nops = static_id1->n_operands;
202 : :
203 : 70404 : if (c1->regno != c2->regno
204 : 69929 : || INSN_CODE (c1->insn) < 0
205 : 69929 : || INSN_CODE (c1->insn) != INSN_CODE (c2->insn))
206 : : return false;
207 : 69928 : gcc_assert (c1->nop == c2->nop);
208 : 210057 : for (int i = 0; i < nops; i++)
209 : 140137 : if (i != c1->nop && static_id1->operand[i].type == OP_IN
210 : 70209 : && *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 : 299620 : insert_cand (cand_t cand)
219 : : {
220 : 299620 : void **entry_ptr;
221 : :
222 : 299620 : entry_ptr = htab_find_slot (cand_table, cand, INSERT);
223 : 299620 : if (*entry_ptr == NULL)
224 : 229700 : *entry_ptr = (void *) cand;
225 : 299620 : return (cand_t) *entry_ptr;
226 : : }
227 : :
228 : : /* Free candidate CAND memory. */
229 : : static void
230 : 229700 : free_cand (void *cand)
231 : : {
232 : 229700 : free (cand);
233 : 229700 : }
234 : :
235 : : /* Initiate the candidate table. */
236 : : static void
237 : 129485 : initiate_cand_table (void)
238 : : {
239 : 129485 : cand_table = htab_create (8000, cand_hash, cand_eq_p,
240 : : (htab_del) free_cand);
241 : 129485 : }
242 : :
243 : : /* Finish the candidate table. */
244 : : static void
245 : 129485 : 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 : 44202110 : bad_for_rematerialization_p (rtx x)
260 : : {
261 : 44202110 : int i, j;
262 : 44202110 : const char *fmt;
263 : 44202110 : enum rtx_code code;
264 : :
265 : 44202110 : if (MEM_P (x) || GET_CODE (x) == UNSPEC || GET_CODE (x) == UNSPEC_VOLATILE)
266 : : return true;
267 : 42123049 : code = GET_CODE (x);
268 : 42123049 : fmt = GET_RTX_FORMAT (code);
269 : 94891226 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
270 : : {
271 : 55190102 : if (fmt[i] == 'e')
272 : : {
273 : 28809974 : if (bad_for_rematerialization_p (XEXP (x, i)))
274 : : return true;
275 : : }
276 : 26380128 : else if (fmt[i] == 'E')
277 : : {
278 : 4662450 : for (j = XVECLEN (x, i) - 1; j >= 0; j--)
279 : 3301463 : 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 : 34739904 : operand_to_remat (rtx_insn *insn)
294 : : {
295 : 34739904 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
296 : 34739904 : struct lra_static_insn_data *static_id = id->insn_static_data;
297 : 34739904 : struct lra_insn_reg *reg, *found_reg = NULL;
298 : :
299 : : /* Don't rematerialize insns which can change PC. */
300 : 34739904 : if (JUMP_P (insn) || CALL_P (insn))
301 : : return -1;
302 : : /* First find a pseudo which can be rematerialized. */
303 : 63779145 : 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 : 47093195 : if (reg->regno == STACK_POINTER_REGNUM && frame_pointer_needed)
310 : : return -1;
311 : 46422341 : else if (reg->type == OP_OUT && ! reg->subreg_p
312 : 46422341 : && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
313 : : {
314 : : /* We permits only one spilled reg. */
315 : 19586771 : 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 : 46418460 : if (reg->regno >= FIRST_PSEUDO_REGISTER
325 : 46418460 : && bitmap_bit_p (&subreg_regs, reg->regno))
326 : : return -1;
327 : :
328 : : /* Don't allow hard registers to be rematerialized. */
329 : 45483976 : if (reg->regno < FIRST_PSEUDO_REGISTER)
330 : : return -1;
331 : : }
332 : 16685950 : if (found_reg == NULL)
333 : : return -1;
334 : 12090673 : if (found_reg->regno < FIRST_PSEUDO_REGISTER)
335 : : return -1;
336 : 12090673 : if (bad_for_rematerialization_p (PATTERN (insn)))
337 : : return -1;
338 : : /* Check the other regs are not spilled. */
339 : 21564730 : for (reg = id->regs; reg != NULL; reg = reg->next)
340 : 19234699 : if (found_reg == reg)
341 : 10011612 : continue;
342 : 9223087 : else if (reg->type == OP_INOUT)
343 : : return -1;
344 : 9210983 : else if (reg->regno >= FIRST_PSEUDO_REGISTER
345 : 9210983 : && reg_renumber[reg->regno] < 0)
346 : : /* Another spilled reg. */
347 : : return -1;
348 : 7961291 : else if (reg->type == OP_IN)
349 : : {
350 : 7955423 : 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 : 1537543 : for (struct lra_insn_reg *reg2 = id->regs;
355 : 4803121 : reg2 != NULL;
356 : 3265578 : reg2 = reg2->next)
357 : 3267483 : if (reg2->type == OP_OUT && reg->regno == reg2->regno)
358 : : return -1;
359 : 1535638 : 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 : 2330031 : for (struct lra_insn_reg *reg = static_id->hard_regs;
371 : 2628003 : reg != NULL;
372 : 297972 : reg = reg->next)
373 : 297972 : if (reg->type == OP_INOUT)
374 : : return -1;
375 : 297972 : 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 : 2330031 : int nop = static_id->n_operands;
387 : 2351208 : for (int i = 0; i < nop; i++)
388 : 2340565 : if (REG_P (*id->operand_loc[i])
389 : 2340565 : && (int) REGNO (*id->operand_loc[i]) == found_reg->regno)
390 : 2319388 : 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 : 299620 : create_cand (rtx_insn *insn, int nop, int regno, rtx_insn *activation = NULL)
399 : : {
400 : 299620 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
401 : 299620 : rtx reg = *id->operand_loc[nop];
402 : 299620 : gcc_assert (REG_P (reg));
403 : 299620 : int op_regno = REGNO (reg);
404 : 299620 : gcc_assert (op_regno >= FIRST_PSEUDO_REGISTER);
405 : 299620 : cand_t cand = XNEW (struct cand);
406 : 299620 : cand->insn = insn;
407 : 299620 : cand->nop = nop;
408 : 299620 : cand->regno = regno;
409 : 299620 : cand->reload_regno = op_regno == regno ? -1 : op_regno;
410 : 299620 : gcc_assert (cand->regno >= 0);
411 : 299620 : cand_t cand_in_table = insert_cand (cand);
412 : 299620 : insn_to_cand[INSN_UID (insn)] = cand_in_table;
413 : 299620 : if (cand != cand_in_table)
414 : 69920 : free (cand);
415 : : else
416 : : {
417 : : /* A new cand. */
418 : 229700 : cand->index = all_cands.length ();
419 : 229700 : all_cands.safe_push (cand);
420 : 229700 : cand->next_regno_cand = regno_cands[cand->regno];
421 : 229700 : regno_cands[cand->regno] = cand;
422 : : }
423 : 299620 : if (activation)
424 : 20975 : insn_to_cand_activation[INSN_UID (activation)] = cand_in_table;
425 : 299620 : }
426 : :
427 : : /* Create rematerialization candidates (inserting them into the
428 : : table). */
429 : : static void
430 : 129485 : create_cands (void)
431 : : {
432 : 129485 : rtx_insn *insn;
433 : 129485 : struct potential_cand
434 : : {
435 : : rtx_insn *insn;
436 : : int nop;
437 : : };
438 : 129485 : struct potential_cand *regno_potential_cand;
439 : :
440 : : /* Create candidates. */
441 : 129485 : regno_potential_cand = XCNEWVEC (struct potential_cand, max_reg_num ());
442 : 71249196 : for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
443 : 71119711 : if (NONDEBUG_INSN_P (insn))
444 : : {
445 : 34760879 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
446 : 34760879 : int keep_regno = -1;
447 : 34760879 : rtx set = single_set (insn);
448 : 34760879 : int nop;
449 : :
450 : : /* See if this is an output reload for a previous insn. */
451 : 34760879 : if (set != NULL
452 : 33232143 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
453 : : {
454 : 10194080 : rtx dstreg = SET_DEST (set);
455 : 10194080 : int src_regno = REGNO (SET_SRC (set));
456 : 10194080 : int dst_regno = REGNO (dstreg);
457 : 10194080 : rtx_insn *insn2 = regno_potential_cand[src_regno].insn;
458 : :
459 : 10194080 : if (insn2 != NULL
460 : 10194080 : && dst_regno >= FIRST_PSEUDO_REGISTER
461 : 80776 : && reg_renumber[dst_regno] < 0
462 : 10215056 : && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn))
463 : : {
464 : 20975 : create_cand (insn2, regno_potential_cand[src_regno].nop,
465 : : dst_regno, insn);
466 : 20975 : goto done;
467 : : }
468 : : }
469 : :
470 : 34739904 : nop = operand_to_remat (insn);
471 : 34739904 : if (nop >= 0)
472 : : {
473 : 2319388 : gcc_assert (REG_P (*id->operand_loc[nop]));
474 : 2319388 : int regno = REGNO (*id->operand_loc[nop]);
475 : 2319388 : gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
476 : : /* If we're setting an unrenumbered pseudo, make a candidate immediately.
477 : : If it's an output reload register, save it for later; the code above
478 : : looks for output reload insns later on. */
479 : 2319388 : if (reg_renumber[regno] < 0)
480 : 278645 : create_cand (insn, nop, regno);
481 : 2040743 : else if (regno >= lra_constraint_new_regno_start)
482 : : {
483 : 734753 : regno_potential_cand[regno].insn = insn;
484 : 734753 : regno_potential_cand[regno].nop = nop;
485 : 734753 : keep_regno = regno;
486 : : }
487 : : }
488 : :
489 : 32420516 : done:
490 : 90480535 : for (struct lra_insn_reg *reg = id->regs; reg != NULL; reg = reg->next)
491 : 55719656 : if (reg->type != OP_IN && reg->regno != keep_regno
492 : 23835779 : && reg->regno >= FIRST_PSEUDO_REGISTER)
493 : 17053323 : regno_potential_cand[reg->regno].insn = NULL;
494 : : }
495 : 129485 : cands_num = all_cands.length ();
496 : 129485 : free (regno_potential_cand);
497 : 129485 : }
498 : :
499 : :
500 : :
501 : : /* Create and initialize BB data. */
502 : : static void
503 : 129485 : create_remat_bb_data (void)
504 : : {
505 : 129485 : basic_block bb;
506 : 129485 : remat_bb_data_t bb_info;
507 : :
508 : 129485 : remat_bb_data = XNEWVEC (class remat_bb_data,
509 : : last_basic_block_for_fn (cfun));
510 : 5407432 : FOR_ALL_BB_FN (bb, cfun)
511 : : {
512 : 5277947 : gcc_checking_assert (bb->index >= 0
513 : : && bb->index < last_basic_block_for_fn (cfun));
514 : 5277947 : bb_info = get_remat_bb_data (bb);
515 : 5277947 : bb_info->bb = bb;
516 : 5277947 : bitmap_initialize (&bb_info->changed_regs, ®_obstack);
517 : 5277947 : bitmap_initialize (&bb_info->dead_regs, ®_obstack);
518 : 5277947 : bitmap_initialize (&bb_info->gen_cands, ®_obstack);
519 : 5277947 : bitmap_initialize (&bb_info->livein_cands, ®_obstack);
520 : 5277947 : bitmap_initialize (&bb_info->pavin_cands, ®_obstack);
521 : 5277947 : bitmap_initialize (&bb_info->pavout_cands, ®_obstack);
522 : 5277947 : bitmap_initialize (&bb_info->avin_cands, ®_obstack);
523 : 5277947 : bitmap_initialize (&bb_info->avout_cands, ®_obstack);
524 : : }
525 : 129485 : }
526 : :
527 : : /* Dump all candidates to DUMP_FILE. */
528 : : static void
529 : 1 : dump_cands (FILE *dump_file)
530 : : {
531 : 1 : int i;
532 : 1 : cand_t cand;
533 : :
534 : 1 : fprintf (dump_file, "\nCands:\n");
535 : 2 : for (i = 0; i < (int) cands_num; i++)
536 : : {
537 : 0 : cand = all_cands[i];
538 : 0 : fprintf (dump_file, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
539 : : i, cand->nop, cand->regno, cand->reload_regno);
540 : 0 : print_inline_rtx (dump_file, cand->insn, 6);
541 : 0 : fprintf (dump_file, "\n");
542 : : }
543 : 1 : }
544 : :
545 : : /* Dump all candidates and BB data. */
546 : : static void
547 : 129485 : dump_candidates_and_remat_bb_data (void)
548 : : {
549 : 129485 : basic_block bb;
550 : :
551 : 129485 : if (lra_dump_file == NULL)
552 : : return;
553 : 1 : dump_cands (lra_dump_file);
554 : 43 : FOR_EACH_BB_FN (bb, cfun)
555 : : {
556 : 42 : fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
557 : : /* Livein */
558 : 42 : fprintf (lra_dump_file, " register live in:");
559 : 42 : dump_regset (df_get_live_in (bb), lra_dump_file);
560 : 42 : putc ('\n', lra_dump_file);
561 : : /* Liveout */
562 : 42 : fprintf (lra_dump_file, " register live out:");
563 : 42 : dump_regset (df_get_live_out (bb), lra_dump_file);
564 : 42 : putc ('\n', lra_dump_file);
565 : : /* Changed/dead regs: */
566 : 42 : fprintf (lra_dump_file, " changed regs:");
567 : 42 : dump_regset (&get_remat_bb_data (bb)->changed_regs, lra_dump_file);
568 : 42 : putc ('\n', lra_dump_file);
569 : 42 : fprintf (lra_dump_file, " dead regs:");
570 : 42 : dump_regset (&get_remat_bb_data (bb)->dead_regs, lra_dump_file);
571 : 42 : putc ('\n', lra_dump_file);
572 : 42 : lra_dump_bitmap_with_title ("cands generated in BB",
573 : 42 : &get_remat_bb_data (bb)->gen_cands, bb->index);
574 : 42 : lra_dump_bitmap_with_title ("livein cands in BB",
575 : 42 : &get_remat_bb_data (bb)->livein_cands, bb->index);
576 : 42 : lra_dump_bitmap_with_title ("pavin cands in BB",
577 : 42 : &get_remat_bb_data (bb)->pavin_cands, bb->index);
578 : 42 : lra_dump_bitmap_with_title ("pavout cands in BB",
579 : 42 : &get_remat_bb_data (bb)->pavout_cands, bb->index);
580 : 42 : lra_dump_bitmap_with_title ("avin cands in BB",
581 : 42 : &get_remat_bb_data (bb)->avin_cands, bb->index);
582 : 42 : lra_dump_bitmap_with_title ("avout cands in BB",
583 : 42 : &get_remat_bb_data (bb)->avout_cands, bb->index);
584 : : }
585 : 1 : fprintf (lra_dump_file, "subreg regs:");
586 : 1 : dump_regset (&subreg_regs, lra_dump_file);
587 : 1 : putc ('\n', lra_dump_file);
588 : : }
589 : :
590 : : /* Free all BB data. */
591 : : static void
592 : 129485 : finish_remat_bb_data (void)
593 : : {
594 : 129485 : basic_block bb;
595 : :
596 : 5148462 : FOR_EACH_BB_FN (bb, cfun)
597 : : {
598 : 5018977 : bitmap_clear (&get_remat_bb_data (bb)->avout_cands);
599 : 5018977 : bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
600 : 5018977 : bitmap_clear (&get_remat_bb_data (bb)->pavout_cands);
601 : 5018977 : bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
602 : 5018977 : bitmap_clear (&get_remat_bb_data (bb)->livein_cands);
603 : 5018977 : bitmap_clear (&get_remat_bb_data (bb)->gen_cands);
604 : 5018977 : bitmap_clear (&get_remat_bb_data (bb)->dead_regs);
605 : 5018977 : bitmap_clear (&get_remat_bb_data (bb)->changed_regs);
606 : : }
607 : 129485 : free (remat_bb_data);
608 : 129485 : }
609 : :
610 : :
611 : :
612 : : /* Update changed_regs, dead_regs, subreg_regs of BB from INSN. */
613 : : static void
614 : 34760879 : set_bb_regs (basic_block bb, rtx_insn *insn)
615 : : {
616 : 34760879 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
617 : 34760879 : remat_bb_data_t bb_info = get_remat_bb_data (bb);
618 : 34760879 : struct lra_insn_reg *reg;
619 : :
620 : 90480535 : for (reg = id->regs; reg != NULL; reg = reg->next)
621 : : {
622 : 55719656 : unsigned regno = reg->regno;
623 : 55719656 : if (reg->type != OP_IN)
624 : 24570532 : bitmap_set_bit (&bb_info->changed_regs, regno);
625 : 31149124 : else if (find_regno_note (insn, REG_DEAD, regno) != NULL)
626 : 17986623 : bitmap_set_bit (&bb_info->dead_regs, regno);
627 : 55719656 : if (regno >= FIRST_PSEUDO_REGISTER && reg->subreg_p)
628 : 527363 : bitmap_set_bit (&subreg_regs, regno);
629 : : }
630 : 34760879 : if (CALL_P (insn))
631 : : {
632 : : /* Partially-clobbered registers might still be live. */
633 : 2048354 : HARD_REG_SET clobbers = insn_callee_abi (insn).full_reg_clobbers ();
634 : 2048354 : bitmap_ior_into (&get_remat_bb_data (bb)->dead_regs,
635 : 2048354 : bitmap_view<HARD_REG_SET> (clobbers));
636 : : }
637 : 34760879 : }
638 : :
639 : : /* Calculate changed_regs and dead_regs for each BB. */
640 : : static void
641 : 129485 : calculate_local_reg_remat_bb_data (void)
642 : : {
643 : 129485 : basic_block bb;
644 : 129485 : rtx_insn *insn;
645 : :
646 : 5148462 : FOR_EACH_BB_FN (bb, cfun)
647 : 74409769 : FOR_BB_INSNS (bb, insn)
648 : 69390792 : if (NONDEBUG_INSN_P (insn))
649 : 34760879 : set_bb_regs (bb, insn);
650 : 129485 : }
651 : :
652 : :
653 : :
654 : : /* Return true if REG overlaps an input operand or non-input hard register of
655 : : INSN. Basically the function returns false if we can move rematerialization
656 : : candidate INSN through another insn with output REG or dead input REG (we
657 : : consider it to avoid extending reg live range) with possible output pseudo
658 : : renaming in INSN. */
659 : : static bool
660 : 4337037 : reg_overlap_for_remat_p (lra_insn_reg *reg, rtx_insn *insn)
661 : : {
662 : 4337037 : int iter;
663 : 4337037 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
664 : 4337037 : struct lra_static_insn_data *static_id = id->insn_static_data;
665 : 4337037 : unsigned regno = reg->regno;
666 : 4337037 : int nregs;
667 : :
668 : 4337037 : if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] >= 0)
669 : 2989595 : regno = reg_renumber[regno];
670 : 3649995 : if (regno >= FIRST_PSEUDO_REGISTER)
671 : : nregs = 1;
672 : : else
673 : 3676637 : nregs = hard_regno_nregs (regno, reg->biggest_mode);
674 : :
675 : 4337037 : struct lra_insn_reg *reg2;
676 : :
677 : 11996909 : for (iter = 0; iter < 2; iter++)
678 : 8173508 : for (reg2 = (iter == 0 ? id->regs : static_id->hard_regs);
679 : 14885321 : reg2 != NULL;
680 : 6711813 : reg2 = reg2->next)
681 : : {
682 : 7225449 : int nregs2;
683 : 7225449 : unsigned regno2 = reg2->regno;
684 : :
685 : 7225449 : if (reg2->type != OP_IN && regno2 >= FIRST_PSEUDO_REGISTER)
686 : 4337339 : continue;
687 : :
688 : 2802414 : if (regno2 >= FIRST_PSEUDO_REGISTER && reg_renumber[regno2] >= 0)
689 : 2802414 : regno2 = reg_renumber[regno2];
690 : 2802414 : if (regno2 >= FIRST_PSEUDO_REGISTER)
691 : : nregs2 = 1;
692 : : else
693 : 2888110 : nregs2 = hard_regno_nregs (regno2, reg->biggest_mode);
694 : :
695 : 2888110 : if ((regno2 + nregs2 - 1 >= regno && regno2 < regno + nregs)
696 : 2374474 : || (regno + nregs - 1 >= regno2 && regno < regno2 + nregs2))
697 : : return true;
698 : : }
699 : : return false;
700 : : }
701 : :
702 : : /* Return true if a call used register is an input operand of INSN. */
703 : : static bool
704 : 26703 : call_used_input_regno_present_p (const function_abi &abi, rtx_insn *insn)
705 : : {
706 : 26703 : int iter;
707 : 26703 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
708 : 26703 : struct lra_static_insn_data *static_id = id->insn_static_data;
709 : 26703 : struct lra_insn_reg *reg;
710 : :
711 : 80109 : for (iter = 0; iter < 2; iter++)
712 : 53406 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
713 : 104207 : reg != NULL;
714 : 50801 : reg = reg->next)
715 : 50801 : if (reg->type == OP_IN
716 : 23095 : && reg->regno < FIRST_PSEUDO_REGISTER
717 : 50801 : && abi.clobbers_reg_p (reg->biggest_mode, reg->regno))
718 : : return true;
719 : : return false;
720 : : }
721 : :
722 : : /* Calculate livein_cands for each BB. */
723 : : static void
724 : 129485 : calculate_livein_cands (void)
725 : : {
726 : 129485 : basic_block bb;
727 : :
728 : 5148462 : FOR_EACH_BB_FN (bb, cfun)
729 : : {
730 : 5018977 : bitmap livein_regs = df_get_live_in (bb);
731 : 5018977 : bitmap livein_cands = &get_remat_bb_data (bb)->livein_cands;
732 : 55414905 : for (unsigned int i = 0; i < cands_num; i++)
733 : : {
734 : 50395928 : cand_t cand = all_cands[i];
735 : 50395928 : lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
736 : 50395928 : struct lra_insn_reg *reg;
737 : :
738 : 101380570 : for (reg = id->regs; reg != NULL; reg = reg->next)
739 : 84632599 : if (reg->type == OP_IN && ! bitmap_bit_p (livein_regs, reg->regno))
740 : : break;
741 : 50395928 : if (reg == NULL)
742 : 16747971 : bitmap_set_bit (livein_cands, i);
743 : : }
744 : : }
745 : 129485 : }
746 : :
747 : : /* Calculate gen_cands for each BB. */
748 : : static void
749 : 129485 : calculate_gen_cands (void)
750 : : {
751 : 129485 : basic_block bb;
752 : 129485 : bitmap gen_cands;
753 : 129485 : rtx_insn *insn;
754 : :
755 : 5148462 : FOR_EACH_BB_FN (bb, cfun)
756 : : {
757 : 5018977 : gen_cands = &get_remat_bb_data (bb)->gen_cands;
758 : 5018977 : auto_bitmap gen_insns (®_obstack);
759 : 74409769 : FOR_BB_INSNS (bb, insn)
760 : 69390792 : if (INSN_P (insn))
761 : : {
762 : 58847674 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
763 : 58847674 : struct lra_static_insn_data *static_id = id->insn_static_data;
764 : 58847674 : struct lra_insn_reg *reg;
765 : 58847674 : unsigned int uid;
766 : 58847674 : bitmap_iterator bi;
767 : 58847674 : cand_t cand;
768 : 58847674 : rtx set;
769 : 58847674 : int iter;
770 : 58847674 : int src_regno = -1, dst_regno = -1;
771 : :
772 : 58847674 : if ((set = single_set (insn)) != NULL
773 : 58847674 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
774 : : {
775 : 10194080 : src_regno = REGNO (SET_SRC (set));
776 : 10194080 : dst_regno = REGNO (SET_DEST (set));
777 : : }
778 : :
779 : : /* Update gen_cands: */
780 : 58847674 : bitmap_clear (&temp_bitmap);
781 : 176543022 : for (iter = 0; iter < 2; iter++)
782 : 117695348 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
783 : 187498941 : reg != NULL;
784 : 69803593 : reg = reg->next)
785 : 69803593 : if (reg->type != OP_IN
786 : 69803593 : || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
787 : 53022451 : EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
788 : : {
789 : 1924471 : rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
790 : :
791 : 1924471 : cand = insn_to_cand[INSN_UID (insn2)];
792 : 1924471 : gcc_assert (cand != NULL);
793 : : /* Ignore the reload insn. */
794 : 1924471 : if (src_regno == cand->reload_regno
795 : 795006 : && dst_regno == cand->regno)
796 : 39366 : continue;
797 : 1885105 : if (cand->regno == reg->regno
798 : 1885105 : || reg_overlap_for_remat_p (reg, insn2))
799 : : {
800 : 242985 : bitmap_clear_bit (gen_cands, cand->index);
801 : 242985 : bitmap_set_bit (&temp_bitmap, uid);
802 : : }
803 : : }
804 : :
805 : 58847674 : if (CALL_P (insn))
806 : : {
807 : 2048354 : function_abi callee_abi = insn_callee_abi (insn);
808 : 2056365 : EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
809 : : {
810 : 8011 : rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
811 : :
812 : 8011 : cand = insn_to_cand[INSN_UID (insn2)];
813 : 8011 : gcc_assert (cand != NULL);
814 : 8011 : if (call_used_input_regno_present_p (callee_abi, insn2))
815 : : {
816 : 0 : bitmap_clear_bit (gen_cands, cand->index);
817 : 0 : bitmap_set_bit (&temp_bitmap, uid);
818 : : }
819 : : }
820 : : }
821 : 58847674 : bitmap_and_compl_into (gen_insns, &temp_bitmap);
822 : :
823 : 58847674 : cand = insn_to_cand[INSN_UID (insn)];
824 : 58847674 : if (cand != NULL)
825 : : {
826 : 299620 : bitmap_set_bit (gen_cands, cand->index);
827 : 299620 : bitmap_set_bit (gen_insns, INSN_UID (insn));
828 : : }
829 : : }
830 : 5018977 : }
831 : 129485 : }
832 : :
833 : :
834 : :
835 : : /* The common transfer function used by the DF equation solver to
836 : : propagate (partial) availability info BB_IN to BB_OUT through block
837 : : with BB_INDEX according to the following equation:
838 : :
839 : : bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
840 : : */
841 : : static bool
842 : 10761040 : cand_trans_fun (int bb_index, bitmap bb_in, bitmap bb_out)
843 : : {
844 : 10761040 : remat_bb_data_t bb_info;
845 : 10761040 : bitmap bb_livein, bb_changed_regs, bb_dead_regs;
846 : 10761040 : unsigned int cid;
847 : 10761040 : bitmap_iterator bi;
848 : :
849 : 10761040 : bb_info = get_remat_bb_data_by_index (bb_index);
850 : 10761040 : bb_livein = &bb_info->livein_cands;
851 : 10761040 : bb_changed_regs = &bb_info->changed_regs;
852 : 10761040 : bb_dead_regs = &bb_info->dead_regs;
853 : : /* Calculate killed avin cands -- cands whose regs are changed or
854 : : becoming dead in the BB. We calculate it here as we hope that
855 : : repeated calculations are compensated by smaller size of BB_IN in
856 : : comparison with all candidates number. */
857 : 10761040 : bitmap_clear (&temp_bitmap);
858 : 19783854 : EXECUTE_IF_SET_IN_BITMAP (bb_in, 0, cid, bi)
859 : : {
860 : 9022814 : cand_t cand = all_cands[cid];
861 : 9022814 : lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
862 : 9022814 : struct lra_insn_reg *reg;
863 : :
864 : 9022814 : if (! bitmap_bit_p (bb_livein, cid))
865 : : {
866 : 93554 : bitmap_set_bit (&temp_bitmap, cid);
867 : 93554 : continue;
868 : : }
869 : 17900030 : for (reg = id->regs; reg != NULL; reg = reg->next)
870 : : /* Ignore all outputs which are not the regno for
871 : : rematerialization. */
872 : 9182934 : if (reg->type == OP_OUT && reg->regno != cand->regno)
873 : 359772 : continue;
874 : 8823162 : else if (bitmap_bit_p (bb_changed_regs, reg->regno)
875 : 8823162 : || bitmap_bit_p (bb_dead_regs, reg->regno))
876 : : {
877 : 212164 : bitmap_set_bit (&temp_bitmap, cid);
878 : 212164 : break;
879 : : }
880 : : /* Check regno for rematerialization. */
881 : 8929260 : if (bitmap_bit_p (bb_changed_regs, cand->regno)
882 : 8929260 : || bitmap_bit_p (bb_dead_regs, cand->regno))
883 : 177798 : bitmap_set_bit (&temp_bitmap, cid);
884 : : }
885 : 10761040 : return bitmap_ior_and_compl (bb_out,
886 : 10761040 : &bb_info->gen_cands, bb_in, &temp_bitmap);
887 : : }
888 : :
889 : :
890 : :
891 : : /* The transfer function used by the DF equation solver to propagate
892 : : partial candidate availability info through block with BB_INDEX
893 : : according to the following equation:
894 : :
895 : : bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
896 : : */
897 : : static bool
898 : 5483093 : cand_pav_trans_fun (int bb_index)
899 : : {
900 : 5483093 : remat_bb_data_t bb_info;
901 : :
902 : 5483093 : bb_info = get_remat_bb_data_by_index (bb_index);
903 : 5483093 : return cand_trans_fun (bb_index, &bb_info->pavin_cands,
904 : 5483093 : &bb_info->pavout_cands);
905 : : }
906 : :
907 : : /* The confluence function used by the DF equation solver to set up
908 : : cand_pav info for a block BB without predecessor. */
909 : : static void
910 : 130764 : cand_pav_con_fun_0 (basic_block bb)
911 : : {
912 : 130764 : bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
913 : 130764 : }
914 : :
915 : : /* The confluence function used by the DF equation solver to propagate
916 : : partial candidate availability info from predecessor to successor
917 : : on edge E (pred->bb) according to the following equation:
918 : :
919 : : bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
920 : : */
921 : : static bool
922 : 7951817 : cand_pav_con_fun_n (edge e)
923 : : {
924 : 7951817 : basic_block pred = e->src;
925 : 7951817 : basic_block bb = e->dest;
926 : 7951817 : remat_bb_data_t bb_info;
927 : 7951817 : bitmap bb_pavin, pred_pavout;
928 : :
929 : 7951817 : bb_info = get_remat_bb_data (bb);
930 : 7951817 : bb_pavin = &bb_info->pavin_cands;
931 : 7951817 : pred_pavout = &get_remat_bb_data (pred)->pavout_cands;
932 : 7951817 : return bitmap_ior_into (bb_pavin, pred_pavout);
933 : : }
934 : :
935 : :
936 : :
937 : : /* The transfer function used by the DF equation solver to propagate
938 : : candidate availability info through block with BB_INDEX according
939 : : to the following equation:
940 : :
941 : : bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
942 : : */
943 : : static bool
944 : 5277947 : cand_av_trans_fun (int bb_index)
945 : : {
946 : 5277947 : remat_bb_data_t bb_info;
947 : :
948 : 5277947 : bb_info = get_remat_bb_data_by_index (bb_index);
949 : 5277947 : return cand_trans_fun (bb_index, &bb_info->avin_cands,
950 : 5277947 : &bb_info->avout_cands);
951 : : }
952 : :
953 : : /* The confluence function used by the DF equation solver to set up
954 : : cand_av info for a block BB without predecessor. */
955 : : static void
956 : 130764 : cand_av_con_fun_0 (basic_block bb)
957 : : {
958 : 130764 : bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
959 : 130764 : }
960 : :
961 : : /* The confluence function used by the DF equation solver to propagate
962 : : cand_av info from predecessor to successor on edge E (pred->bb)
963 : : according to the following equation:
964 : :
965 : : bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
966 : : */
967 : : static bool
968 : 7577218 : cand_av_con_fun_n (edge e)
969 : : {
970 : 7577218 : basic_block pred = e->src;
971 : 7577218 : basic_block bb = e->dest;
972 : 7577218 : remat_bb_data_t bb_info;
973 : 7577218 : bitmap bb_avin, pred_avout;
974 : :
975 : 7577218 : bb_info = get_remat_bb_data (bb);
976 : 7577218 : bb_avin = &bb_info->avin_cands;
977 : 7577218 : pred_avout = &get_remat_bb_data (pred)->avout_cands;
978 : 7577218 : return bitmap_and_into (bb_avin, pred_avout);
979 : : }
980 : :
981 : : /* Calculate available candidates for each BB. */
982 : : static void
983 : 129485 : calculate_global_remat_bb_data (void)
984 : : {
985 : 129485 : basic_block bb;
986 : :
987 : 129485 : df_simple_dataflow
988 : 129485 : (DF_FORWARD, NULL, cand_pav_con_fun_0, cand_pav_con_fun_n,
989 : : cand_pav_trans_fun, &all_blocks,
990 : : df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
991 : : /* Initialize avin by pavin. */
992 : 5148462 : FOR_EACH_BB_FN (bb, cfun)
993 : 5018977 : bitmap_copy (&get_remat_bb_data (bb)->avin_cands,
994 : 5018977 : &get_remat_bb_data (bb)->pavin_cands);
995 : 129485 : df_simple_dataflow
996 : 129485 : (DF_FORWARD, NULL, cand_av_con_fun_0, cand_av_con_fun_n,
997 : : cand_av_trans_fun, &all_blocks,
998 : : df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
999 : 129485 : }
1000 : :
1001 : :
1002 : :
1003 : : /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
1004 : : static void
1005 : 63 : change_sp_offset (rtx_insn *insns, poly_int64 sp_offset)
1006 : : {
1007 : 126 : for (rtx_insn *insn = insns; insn != NULL; insn = NEXT_INSN (insn))
1008 : 63 : eliminate_regs_in_insn (insn, false, false, sp_offset);
1009 : 63 : }
1010 : :
1011 : : /* Return start hard register of REG (can be a hard or a pseudo reg)
1012 : : or -1 (if it is a spilled pseudo). Return number of hard registers
1013 : : occupied by REG through parameter NREGS if the start hard reg is
1014 : : not negative. */
1015 : : static int
1016 : 42163548 : get_hard_regs (struct lra_insn_reg *reg, int &nregs)
1017 : : {
1018 : 42163548 : int regno = reg->regno;
1019 : 42163548 : int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
1020 : :
1021 : 42163548 : if (hard_regno >= 0)
1022 : 39807107 : nregs = hard_regno_nregs (hard_regno, reg->biggest_mode);
1023 : 42163548 : return hard_regno;
1024 : : }
1025 : :
1026 : : /* Make copy of and register scratch pseudos in rematerialized insn
1027 : : REMAT_INSN. */
1028 : : static void
1029 : 1975 : update_scratch_ops (rtx_insn *remat_insn)
1030 : : {
1031 : 1975 : lra_insn_recog_data_t id = lra_get_insn_recog_data (remat_insn);
1032 : 1975 : struct lra_static_insn_data *static_id = id->insn_static_data;
1033 : 6225 : for (int i = 0; i < static_id->n_operands; i++)
1034 : : {
1035 : 4250 : rtx *loc = id->operand_loc[i];
1036 : 4250 : if (! REG_P (*loc))
1037 : 1644 : continue;
1038 : 2606 : int regno = REGNO (*loc);
1039 : 2606 : if (! ira_former_scratch_p (regno))
1040 : 2606 : continue;
1041 : 0 : *loc = lra_create_new_reg (GET_MODE (*loc), *loc,
1042 : : lra_get_allocno_class (regno), NULL,
1043 : : "scratch pseudo copy");
1044 : 0 : ira_register_new_scratch_op (remat_insn, i, id->icode);
1045 : : }
1046 : :
1047 : 1975 : }
1048 : :
1049 : : /* Insert rematerialization insns using the data-flow data calculated
1050 : : earlier. */
1051 : : static bool
1052 : 129485 : do_remat (void)
1053 : : {
1054 : 129485 : unsigned regno;
1055 : 129485 : rtx_insn *insn;
1056 : 129485 : basic_block bb;
1057 : 129485 : bool changed_p = false;
1058 : : /* Living hard regs and hard registers of living pseudos. */
1059 : 129485 : HARD_REG_SET live_hard_regs;
1060 : 129485 : bitmap_iterator bi;
1061 : :
1062 : 129485 : auto_bitmap avail_cands (®_obstack);
1063 : 129485 : auto_bitmap active_cands (®_obstack);
1064 : 5148462 : FOR_EACH_BB_FN (bb, cfun)
1065 : : {
1066 : 5018977 : CLEAR_HARD_REG_SET (live_hard_regs);
1067 : 57937578 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), 0, regno, bi)
1068 : : {
1069 : 105837202 : int hard_regno = regno < FIRST_PSEUDO_REGISTER
1070 : 52918601 : ? regno
1071 : 45570943 : : reg_renumber[regno];
1072 : 52918601 : if (hard_regno >= 0)
1073 : 27730824 : SET_HARD_REG_BIT (live_hard_regs, hard_regno);
1074 : : }
1075 : 5018977 : bitmap_and (avail_cands, &get_remat_bb_data (bb)->avin_cands,
1076 : 5018977 : &get_remat_bb_data (bb)->livein_cands);
1077 : : /* Activating insns are always in the same block as their corresponding
1078 : : remat insn, so at the start of a block the two bitsets are equal. */
1079 : 5018977 : bitmap_copy (active_cands, avail_cands);
1080 : 74409769 : FOR_BB_INSNS (bb, insn)
1081 : : {
1082 : 69390792 : if (!NONDEBUG_INSN_P (insn))
1083 : 34631888 : continue;
1084 : :
1085 : 34760879 : lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
1086 : 34760879 : struct lra_static_insn_data *static_id = id->insn_static_data;
1087 : 34760879 : struct lra_insn_reg *reg;
1088 : 34760879 : cand_t cand;
1089 : 34760879 : unsigned int cid;
1090 : 34760879 : bitmap_iterator bi;
1091 : 34760879 : rtx set;
1092 : 34760879 : int iter;
1093 : 34760879 : int src_regno = -1, dst_regno = -1;
1094 : :
1095 : 34760879 : if ((set = single_set (insn)) != NULL
1096 : 34760879 : && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
1097 : : {
1098 : 10194080 : src_regno = REGNO (SET_SRC (set));
1099 : 10194080 : dst_regno = REGNO (SET_DEST (set));
1100 : : }
1101 : :
1102 : 34760879 : cand = NULL;
1103 : : /* Check possibility of rematerialization (hard reg or
1104 : : unpsilled pseudo <- spilled pseudo): */
1105 : 34760879 : if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER
1106 : 9102237 : && reg_renumber[src_regno] < 0
1107 : 1418418 : && (dst_regno < FIRST_PSEUDO_REGISTER
1108 : 1230243 : || reg_renumber[dst_regno] >= 0))
1109 : : {
1110 : 1418418 : for (cand = regno_cands[src_regno];
1111 : 2001203 : cand != NULL;
1112 : 582785 : cand = cand->next_regno_cand)
1113 : 585201 : if (bitmap_bit_p (avail_cands, cand->index)
1114 : 585201 : && bitmap_bit_p (active_cands, cand->index))
1115 : : break;
1116 : : }
1117 : 1418418 : int i, hard_regno, nregs;
1118 : 1418418 : int dst_hard_regno, dst_nregs;
1119 : 1418418 : rtx_insn *remat_insn = NULL;
1120 : 1418418 : poly_int64 cand_sp_offset = 0;
1121 : 1418418 : if (cand != NULL)
1122 : : {
1123 : 2416 : lra_insn_recog_data_t cand_id
1124 : 2416 : = lra_get_insn_recog_data (cand->insn);
1125 : 2416 : struct lra_static_insn_data *static_cand_id
1126 : : = cand_id->insn_static_data;
1127 : 2416 : rtx saved_op = *cand_id->operand_loc[cand->nop];
1128 : :
1129 : : /* Check clobbers do not kill something living. */
1130 : 2416 : gcc_assert (REG_P (saved_op));
1131 : 2416 : int ignore_regno = REGNO (saved_op);
1132 : :
1133 : 4832 : dst_hard_regno = dst_regno < FIRST_PSEUDO_REGISTER
1134 : 2416 : ? dst_regno : reg_renumber[dst_regno];
1135 : 2416 : gcc_assert (dst_hard_regno >= 0);
1136 : 2416 : machine_mode mode = GET_MODE (SET_DEST (set));
1137 : 2416 : dst_nregs = hard_regno_nregs (dst_hard_regno, mode);
1138 : :
1139 : 6019 : for (reg = cand_id->regs; reg != NULL; reg = reg->next)
1140 : 3606 : if (reg->type != OP_IN && reg->regno != ignore_regno)
1141 : : {
1142 : 3 : hard_regno = get_hard_regs (reg, nregs);
1143 : 3 : gcc_assert (hard_regno >= 0);
1144 : 6 : for (i = 0; i < nregs; i++)
1145 : 3 : if (TEST_HARD_REG_BIT (live_hard_regs, hard_regno + i))
1146 : : break;
1147 : 3 : if (i < nregs)
1148 : : break;
1149 : : /* Ensure the clobber also doesn't overlap dst_regno. */
1150 : 3 : if (hard_regno + nregs > dst_hard_regno
1151 : 3 : && hard_regno < dst_hard_regno + dst_nregs)
1152 : : break;
1153 : : }
1154 : :
1155 : 2416 : if (reg == NULL)
1156 : : {
1157 : 2413 : for (reg = static_cand_id->hard_regs;
1158 : 2613 : reg != NULL;
1159 : 200 : reg = reg->next)
1160 : 200 : if (reg->type != OP_IN)
1161 : : {
1162 : 200 : if (TEST_HARD_REG_BIT (live_hard_regs, reg->regno))
1163 : : break;
1164 : 200 : if (reg->regno >= dst_hard_regno
1165 : 191 : && reg->regno < dst_hard_regno + dst_nregs)
1166 : : break;
1167 : : }
1168 : : }
1169 : :
1170 : 2413 : if (reg == NULL)
1171 : : {
1172 : 2413 : *cand_id->operand_loc[cand->nop] = SET_DEST (set);
1173 : 2413 : lra_update_insn_regno_info (cand->insn);
1174 : 2413 : bool ok_p = lra_constrain_insn (cand->insn);
1175 : 2413 : if (ok_p)
1176 : : {
1177 : 2008 : rtx remat_pat = copy_insn (PATTERN (cand->insn));
1178 : :
1179 : 2008 : start_sequence ();
1180 : 2008 : emit_insn (remat_pat);
1181 : 2008 : remat_insn = get_insns ();
1182 : 2008 : end_sequence ();
1183 : 2008 : if (recog_memoized (remat_insn) < 0)
1184 : 33 : remat_insn = NULL;
1185 : 2008 : cand_sp_offset = cand_id->sp_offset;
1186 : : }
1187 : 2413 : *cand_id->operand_loc[cand->nop] = saved_op;
1188 : 2413 : lra_update_insn_regno_info (cand->insn);
1189 : : }
1190 : : }
1191 : :
1192 : 34760879 : bitmap_clear (&temp_bitmap);
1193 : : /* Update avail_cands (see analogous code for
1194 : : calculate_gen_cands). */
1195 : 139043516 : for (iter = 0; iter < 2; iter++)
1196 : 69521758 : for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
1197 : 133855994 : reg != NULL;
1198 : 64334236 : reg = reg->next)
1199 : 64334236 : if (reg->type != OP_IN
1200 : 64334236 : || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1201 : 53602638 : EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1202 : : {
1203 : 2504658 : cand = all_cands[cid];
1204 : :
1205 : : /* Ignore the reload insn. */
1206 : 2504658 : if (src_regno == cand->reload_regno
1207 : 1105594 : && dst_regno == cand->regno)
1208 : 39366 : continue;
1209 : 2465292 : if (cand->regno == reg->regno
1210 : 2465292 : || reg_overlap_for_remat_p (reg, cand->insn))
1211 : 284011 : bitmap_set_bit (&temp_bitmap, cand->index);
1212 : : }
1213 : :
1214 : 34760879 : if (CALL_P (insn))
1215 : : {
1216 : 2048354 : function_abi callee_abi = insn_callee_abi (insn);
1217 : 2067046 : EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1218 : : {
1219 : 18692 : cand = all_cands[cid];
1220 : :
1221 : 18692 : if (call_used_input_regno_present_p (callee_abi, cand->insn))
1222 : 0 : bitmap_set_bit (&temp_bitmap, cand->index);
1223 : : }
1224 : : }
1225 : :
1226 : 34760879 : bitmap_and_compl_into (avail_cands, &temp_bitmap);
1227 : :
1228 : : /* Now see whether a candidate is made active or available
1229 : : by this insn. */
1230 : 34760879 : cand = insn_to_cand_activation[INSN_UID (insn)];
1231 : 34760879 : if (cand)
1232 : 20975 : bitmap_set_bit (active_cands, cand->index);
1233 : :
1234 : 34760879 : cand = insn_to_cand[INSN_UID (insn)];
1235 : 34760879 : if (cand != NULL)
1236 : : {
1237 : 299620 : bitmap_set_bit (avail_cands, cand->index);
1238 : 299620 : if (cand->reload_regno == -1)
1239 : 278658 : bitmap_set_bit (active_cands, cand->index);
1240 : : else
1241 : 20962 : bitmap_clear_bit (active_cands, cand->index);
1242 : : }
1243 : :
1244 : 34760879 : if (remat_insn != NULL)
1245 : : {
1246 : 1975 : poly_int64 sp_offset_change = cand_sp_offset - id->sp_offset;
1247 : 1975 : if (maybe_ne (sp_offset_change, 0))
1248 : 63 : change_sp_offset (remat_insn, sp_offset_change);
1249 : 1975 : update_scratch_ops (remat_insn);
1250 : 1975 : lra_process_new_insns (insn, remat_insn, NULL,
1251 : : "Inserting rematerialization insn");
1252 : 1975 : lra_set_insn_deleted (insn);
1253 : 1975 : changed_p = true;
1254 : 1975 : continue;
1255 : 1975 : }
1256 : :
1257 : : /* Update live hard regs: */
1258 : 90474610 : for (reg = id->regs; reg != NULL; reg = reg->next)
1259 : 55715706 : if (reg->type == OP_IN
1260 : 55715706 : && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1261 : : {
1262 : 17985040 : if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1263 : 971981 : continue;
1264 : 34342075 : for (i = 0; i < nregs; i++)
1265 : 17329016 : CLEAR_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1266 : : }
1267 : : /* Process also hard regs (e.g. CC register) which are part
1268 : : of insn definition. */
1269 : 43373484 : for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1270 : 8614580 : if (reg->type == OP_IN
1271 : 8614580 : && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1272 : 2248085 : CLEAR_HARD_REG_BIT (live_hard_regs, reg->regno);
1273 : : /* Inputs have been processed, now process outputs. */
1274 : 90474610 : for (reg = id->regs; reg != NULL; reg = reg->next)
1275 : 55715706 : if (reg->type != OP_IN
1276 : 55715706 : && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1277 : : {
1278 : 24178505 : if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1279 : 1384460 : continue;
1280 : 46145582 : for (i = 0; i < nregs; i++)
1281 : 23351537 : SET_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1282 : : }
1283 : 43373484 : for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1284 : 8614580 : if (reg->type != OP_IN
1285 : 8614580 : && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1286 : 2376040 : SET_HARD_REG_BIT (live_hard_regs, reg->regno);
1287 : : }
1288 : : }
1289 : 129485 : return changed_p;
1290 : 129485 : }
1291 : :
1292 : :
1293 : :
1294 : : /* Current number of rematerialization iteration. */
1295 : : int lra_rematerialization_iter;
1296 : :
1297 : : /* Entry point of the rematerialization sub-pass. Return true if we
1298 : : did any rematerialization. */
1299 : : bool
1300 : 143206 : lra_remat (void)
1301 : : {
1302 : 143206 : basic_block bb;
1303 : 143206 : bool result;
1304 : 143206 : int max_regno = max_reg_num ();
1305 : :
1306 : 143206 : if (! flag_lra_remat)
1307 : : return false;
1308 : 129485 : lra_rematerialization_iter++;
1309 : 129485 : if (lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
1310 : : return false;
1311 : 129485 : if (lra_dump_file != NULL)
1312 : 1 : fprintf (lra_dump_file,
1313 : : "\n******** Rematerialization #%d: ********\n\n",
1314 : : lra_rematerialization_iter);
1315 : 129485 : timevar_push (TV_LRA_REMAT);
1316 : 129485 : insn_to_cand = XCNEWVEC (cand_t, get_max_uid ());
1317 : 129485 : insn_to_cand_activation = XCNEWVEC (cand_t, get_max_uid ());
1318 : 129485 : regno_cands = XCNEWVEC (cand_t, max_regno);
1319 : 129485 : all_cands.create (8000);
1320 : 129485 : initiate_cand_table ();
1321 : 129485 : create_remat_bb_data ();
1322 : 129485 : bitmap_initialize (&temp_bitmap, ®_obstack);
1323 : 129485 : bitmap_initialize (&subreg_regs, ®_obstack);
1324 : 129485 : calculate_local_reg_remat_bb_data ();
1325 : 129485 : create_cands ();
1326 : 129485 : calculate_livein_cands ();
1327 : 129485 : calculate_gen_cands ();
1328 : 129485 : bitmap_initialize (&all_blocks, ®_obstack);
1329 : 5407432 : FOR_ALL_BB_FN (bb, cfun)
1330 : 5277947 : bitmap_set_bit (&all_blocks, bb->index);
1331 : 129485 : calculate_global_remat_bb_data ();
1332 : 129485 : dump_candidates_and_remat_bb_data ();
1333 : 129485 : result = do_remat ();
1334 : 129485 : if (result)
1335 : 1297 : lra_dump_insns_if_possible ("changed func after rematerialization");
1336 : 129485 : all_cands.release ();
1337 : 129485 : bitmap_clear (&temp_bitmap);
1338 : 129485 : bitmap_clear (&subreg_regs);
1339 : 129485 : finish_remat_bb_data ();
1340 : 129485 : finish_cand_table ();
1341 : 129485 : bitmap_clear (&all_blocks);
1342 : 129485 : free (regno_cands);
1343 : 129485 : free (insn_to_cand);
1344 : 129485 : free (insn_to_cand_activation);
1345 : 129485 : timevar_pop (TV_LRA_REMAT);
1346 : 129485 : return result;
1347 : : }
|
