1 /* Rematerialize pseudos values.
2 Copyright (C) 2014-2021 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
get_remat_bb_data(basic_block bb)154 get_remat_bb_data (basic_block bb)
155 {
156 return &remat_bb_data[(bb)->index];
157 }
158
159 static inline remat_bb_data_t
get_remat_bb_data_by_index(int index)160 get_remat_bb_data_by_index (int index)
161 {
162 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
cand_hash(const void * cand)174 cand_hash (const void *cand)
175 {
176 const_cand_t c = (const_cand_t) cand;
177 lra_insn_recog_data_t id = lra_get_insn_recog_data (c->insn);
178 struct lra_static_insn_data *static_id = id->insn_static_data;
179 int nops = static_id->n_operands;
180 hashval_t hash = 0;
181
182 for (int i = 0; i < nops; i++)
183 if (i == c->nop)
184 hash = iterative_hash_object (c->regno, hash);
185 else if (static_id->operand[i].type == OP_IN)
186 hash = iterative_hash_object (*id->operand_loc[i], hash);
187 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
cand_eq_p(const void * cand1,const void * cand2)194 cand_eq_p (const void *cand1, const void *cand2)
195 {
196 const_cand_t c1 = (const_cand_t) cand1;
197 const_cand_t c2 = (const_cand_t) cand2;
198 lra_insn_recog_data_t id1 = lra_get_insn_recog_data (c1->insn);
199 lra_insn_recog_data_t id2 = lra_get_insn_recog_data (c2->insn);
200 struct lra_static_insn_data *static_id1 = id1->insn_static_data;
201 int nops = static_id1->n_operands;
202
203 if (c1->regno != c2->regno
204 || INSN_CODE (c1->insn) < 0
205 || INSN_CODE (c1->insn) != INSN_CODE (c2->insn))
206 return false;
207 gcc_assert (c1->nop == c2->nop);
208 for (int i = 0; i < nops; i++)
209 if (i != c1->nop && static_id1->operand[i].type == OP_IN
210 && *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
insert_cand(cand_t cand)218 insert_cand (cand_t cand)
219 {
220 void **entry_ptr;
221
222 entry_ptr = htab_find_slot (cand_table, cand, INSERT);
223 if (*entry_ptr == NULL)
224 *entry_ptr = (void *) cand;
225 return (cand_t) *entry_ptr;
226 }
227
228 /* Free candidate CAND memory. */
229 static void
free_cand(void * cand)230 free_cand (void *cand)
231 {
232 free (cand);
233 }
234
235 /* Initiate the candidate table. */
236 static void
initiate_cand_table(void)237 initiate_cand_table (void)
238 {
239 cand_table = htab_create (8000, cand_hash, cand_eq_p,
240 (htab_del) free_cand);
241 }
242
243 /* Finish the candidate table. */
244 static void
finish_cand_table(void)245 finish_cand_table (void)
246 {
247 htab_delete (cand_table);
248 }
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
bad_for_rematerialization_p(rtx x)259 bad_for_rematerialization_p (rtx x)
260 {
261 int i, j;
262 const char *fmt;
263 enum rtx_code code;
264
265 if (MEM_P (x) || GET_CODE (x) == UNSPEC || GET_CODE (x) == UNSPEC_VOLATILE)
266 return true;
267 code = GET_CODE (x);
268 fmt = GET_RTX_FORMAT (code);
269 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
270 {
271 if (fmt[i] == 'e')
272 {
273 if (bad_for_rematerialization_p (XEXP (x, i)))
274 return true;
275 }
276 else if (fmt[i] == 'E')
277 {
278 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
279 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
operand_to_remat(rtx_insn * insn)293 operand_to_remat (rtx_insn *insn)
294 {
295 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
296 struct lra_static_insn_data *static_id = id->insn_static_data;
297 struct lra_insn_reg *reg, *found_reg = NULL;
298
299 /* Don't rematerialize insns which can change PC. */
300 if (JUMP_P (insn) || CALL_P (insn))
301 return -1;
302 /* First find a pseudo which can be rematerialized. */
303 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 if (reg->regno == STACK_POINTER_REGNUM && frame_pointer_needed)
310 return -1;
311 else if (reg->type == OP_OUT && ! reg->subreg_p
312 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
313 {
314 /* We permits only one spilled reg. */
315 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 if (reg->regno >= FIRST_PSEUDO_REGISTER
325 && bitmap_bit_p (&subreg_regs, reg->regno))
326 return -1;
327
328 /* Don't allow hard registers to be rematerialized. */
329 if (reg->regno < FIRST_PSEUDO_REGISTER)
330 return -1;
331 }
332 if (found_reg == NULL)
333 return -1;
334 if (found_reg->regno < FIRST_PSEUDO_REGISTER)
335 return -1;
336 if (bad_for_rematerialization_p (PATTERN (insn)))
337 return -1;
338 /* Check the other regs are not spilled. */
339 for (reg = id->regs; reg != NULL; reg = reg->next)
340 if (found_reg == reg)
341 continue;
342 else if (reg->type == OP_INOUT)
343 return -1;
344 else if (reg->regno >= FIRST_PSEUDO_REGISTER
345 && reg_renumber[reg->regno] < 0)
346 /* Another spilled reg. */
347 return -1;
348 else if (reg->type == OP_IN)
349 {
350 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 for (struct lra_insn_reg *reg2 = id->regs;
355 reg2 != NULL;
356 reg2 = reg2->next)
357 if (reg2->type == OP_OUT && reg->regno == reg2->regno)
358 return -1;
359 if (reg->regno < FIRST_PSEUDO_REGISTER)
360 for (struct lra_insn_reg *reg2 = static_id->hard_regs;
361 reg2 != NULL;
362 reg2 = reg2->next)
363 if (reg2->type == OP_OUT
364 && reg->regno <= reg2->regno
365 && (reg2->regno
366 < (int) end_hard_regno (reg->biggest_mode, reg->regno)))
367 return -1;
368 }
369 /* Check hard coded insn registers. */
370 for (struct lra_insn_reg *reg = static_id->hard_regs;
371 reg != NULL;
372 reg = reg->next)
373 if (reg->type == OP_INOUT)
374 return -1;
375 else if (reg->type == OP_IN)
376 {
377 /* Check that there is no output hard reg as the input
378 one. */
379 for (struct lra_insn_reg *reg2 = static_id->hard_regs;
380 reg2 != NULL;
381 reg2 = reg2->next)
382 if (reg2->type == OP_OUT && reg->regno == reg2->regno)
383 return -1;
384 }
385 /* Find the rematerialization operand. */
386 int nop = static_id->n_operands;
387 for (int i = 0; i < nop; i++)
388 if (REG_P (*id->operand_loc[i])
389 && (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 create_cand (rtx_insn *insn, int nop, int regno, rtx_insn *activation = NULL)
399 {
400 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
401 rtx reg = *id->operand_loc[nop];
402 gcc_assert (REG_P (reg));
403 int op_regno = REGNO (reg);
404 gcc_assert (op_regno >= FIRST_PSEUDO_REGISTER);
405 cand_t cand = XNEW (struct cand);
406 cand->insn = insn;
407 cand->nop = nop;
408 cand->regno = regno;
409 cand->reload_regno = op_regno == regno ? -1 : op_regno;
410 gcc_assert (cand->regno >= 0);
411 cand_t cand_in_table = insert_cand (cand);
412 insn_to_cand[INSN_UID (insn)] = cand_in_table;
413 if (cand != cand_in_table)
414 free (cand);
415 else
416 {
417 /* A new cand. */
418 cand->index = all_cands.length ();
419 all_cands.safe_push (cand);
420 cand->next_regno_cand = regno_cands[cand->regno];
421 regno_cands[cand->regno] = cand;
422 }
423 if (activation)
424 insn_to_cand_activation[INSN_UID (activation)] = cand_in_table;
425 }
426
427 /* Create rematerialization candidates (inserting them into the
428 table). */
429 static void
create_cands(void)430 create_cands (void)
431 {
432 rtx_insn *insn;
433 struct potential_cand
434 {
435 rtx_insn *insn;
436 int nop;
437 };
438 struct potential_cand *regno_potential_cand;
439
440 /* Create candidates. */
441 regno_potential_cand = XCNEWVEC (struct potential_cand, max_reg_num ());
442 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
443 if (NONDEBUG_INSN_P (insn))
444 {
445 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
446 int keep_regno = -1;
447 rtx set = single_set (insn);
448 int nop;
449
450 /* See if this is an output reload for a previous insn. */
451 if (set != NULL
452 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
453 {
454 rtx dstreg = SET_DEST (set);
455 int src_regno = REGNO (SET_SRC (set));
456 int dst_regno = REGNO (dstreg);
457 rtx_insn *insn2 = regno_potential_cand[src_regno].insn;
458
459 if (insn2 != NULL
460 && dst_regno >= FIRST_PSEUDO_REGISTER
461 && reg_renumber[dst_regno] < 0
462 && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn))
463 {
464 create_cand (insn2, regno_potential_cand[src_regno].nop,
465 dst_regno, insn);
466 goto done;
467 }
468 }
469
470 nop = operand_to_remat (insn);
471 if (nop >= 0)
472 {
473 gcc_assert (REG_P (*id->operand_loc[nop]));
474 int regno = REGNO (*id->operand_loc[nop]);
475 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 if (reg_renumber[regno] < 0)
480 create_cand (insn, nop, regno);
481 else if (regno >= lra_constraint_new_regno_start)
482 {
483 regno_potential_cand[regno].insn = insn;
484 regno_potential_cand[regno].nop = nop;
485 keep_regno = regno;
486 }
487 }
488
489 done:
490 for (struct lra_insn_reg *reg = id->regs; reg != NULL; reg = reg->next)
491 if (reg->type != OP_IN && reg->regno != keep_regno
492 && reg->regno >= FIRST_PSEUDO_REGISTER)
493 regno_potential_cand[reg->regno].insn = NULL;
494 }
495 cands_num = all_cands.length ();
496 free (regno_potential_cand);
497 }
498
499
500
501 /* Create and initialize BB data. */
502 static void
create_remat_bb_data(void)503 create_remat_bb_data (void)
504 {
505 basic_block bb;
506 remat_bb_data_t bb_info;
507
508 remat_bb_data = XNEWVEC (class remat_bb_data,
509 last_basic_block_for_fn (cfun));
510 FOR_ALL_BB_FN (bb, cfun)
511 {
512 gcc_checking_assert (bb->index >= 0
513 && bb->index < last_basic_block_for_fn (cfun));
514 bb_info = get_remat_bb_data (bb);
515 bb_info->bb = bb;
516 bitmap_initialize (&bb_info->changed_regs, ®_obstack);
517 bitmap_initialize (&bb_info->dead_regs, ®_obstack);
518 bitmap_initialize (&bb_info->gen_cands, ®_obstack);
519 bitmap_initialize (&bb_info->livein_cands, ®_obstack);
520 bitmap_initialize (&bb_info->pavin_cands, ®_obstack);
521 bitmap_initialize (&bb_info->pavout_cands, ®_obstack);
522 bitmap_initialize (&bb_info->avin_cands, ®_obstack);
523 bitmap_initialize (&bb_info->avout_cands, ®_obstack);
524 }
525 }
526
527 /* Dump all candidates to DUMP_FILE. */
528 static void
dump_cands(FILE * dump_file)529 dump_cands (FILE *dump_file)
530 {
531 int i;
532 cand_t cand;
533
534 fprintf (dump_file, "\nCands:\n");
535 for (i = 0; i < (int) cands_num; i++)
536 {
537 cand = all_cands[i];
538 fprintf (dump_file, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
539 i, cand->nop, cand->regno, cand->reload_regno);
540 print_inline_rtx (dump_file, cand->insn, 6);
541 fprintf (dump_file, "\n");
542 }
543 }
544
545 /* Dump all candidates and BB data. */
546 static void
dump_candidates_and_remat_bb_data(void)547 dump_candidates_and_remat_bb_data (void)
548 {
549 basic_block bb;
550
551 if (lra_dump_file == NULL)
552 return;
553 dump_cands (lra_dump_file);
554 FOR_EACH_BB_FN (bb, cfun)
555 {
556 fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
557 /* Livein */
558 fprintf (lra_dump_file, " register live in:");
559 dump_regset (df_get_live_in (bb), lra_dump_file);
560 putc ('\n', lra_dump_file);
561 /* Liveout */
562 fprintf (lra_dump_file, " register live out:");
563 dump_regset (df_get_live_out (bb), lra_dump_file);
564 putc ('\n', lra_dump_file);
565 /* Changed/dead regs: */
566 fprintf (lra_dump_file, " changed regs:");
567 dump_regset (&get_remat_bb_data (bb)->changed_regs, lra_dump_file);
568 putc ('\n', lra_dump_file);
569 fprintf (lra_dump_file, " dead regs:");
570 dump_regset (&get_remat_bb_data (bb)->dead_regs, lra_dump_file);
571 putc ('\n', lra_dump_file);
572 lra_dump_bitmap_with_title ("cands generated in BB",
573 &get_remat_bb_data (bb)->gen_cands, bb->index);
574 lra_dump_bitmap_with_title ("livein cands in BB",
575 &get_remat_bb_data (bb)->livein_cands, bb->index);
576 lra_dump_bitmap_with_title ("pavin cands in BB",
577 &get_remat_bb_data (bb)->pavin_cands, bb->index);
578 lra_dump_bitmap_with_title ("pavout cands in BB",
579 &get_remat_bb_data (bb)->pavout_cands, bb->index);
580 lra_dump_bitmap_with_title ("avin cands in BB",
581 &get_remat_bb_data (bb)->avin_cands, bb->index);
582 lra_dump_bitmap_with_title ("avout cands in BB",
583 &get_remat_bb_data (bb)->avout_cands, bb->index);
584 }
585 fprintf (lra_dump_file, "subreg regs:");
586 dump_regset (&subreg_regs, lra_dump_file);
587 putc ('\n', lra_dump_file);
588 }
589
590 /* Free all BB data. */
591 static void
finish_remat_bb_data(void)592 finish_remat_bb_data (void)
593 {
594 basic_block bb;
595
596 FOR_EACH_BB_FN (bb, cfun)
597 {
598 bitmap_clear (&get_remat_bb_data (bb)->avout_cands);
599 bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
600 bitmap_clear (&get_remat_bb_data (bb)->pavout_cands);
601 bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
602 bitmap_clear (&get_remat_bb_data (bb)->livein_cands);
603 bitmap_clear (&get_remat_bb_data (bb)->gen_cands);
604 bitmap_clear (&get_remat_bb_data (bb)->dead_regs);
605 bitmap_clear (&get_remat_bb_data (bb)->changed_regs);
606 }
607 free (remat_bb_data);
608 }
609
610
611
612 /* Update changed_regs, dead_regs, subreg_regs of BB from INSN. */
613 static void
set_bb_regs(basic_block bb,rtx_insn * insn)614 set_bb_regs (basic_block bb, rtx_insn *insn)
615 {
616 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
617 remat_bb_data_t bb_info = get_remat_bb_data (bb);
618 struct lra_insn_reg *reg;
619
620 for (reg = id->regs; reg != NULL; reg = reg->next)
621 {
622 unsigned regno = reg->regno;
623 if (reg->type != OP_IN)
624 bitmap_set_bit (&bb_info->changed_regs, regno);
625 else if (find_regno_note (insn, REG_DEAD, regno) != NULL)
626 bitmap_set_bit (&bb_info->dead_regs, regno);
627 if (regno >= FIRST_PSEUDO_REGISTER && reg->subreg_p)
628 bitmap_set_bit (&subreg_regs, regno);
629 }
630 if (CALL_P (insn))
631 {
632 /* Partially-clobbered registers might still be live. */
633 HARD_REG_SET clobbers = insn_callee_abi (insn).full_reg_clobbers ();
634 bitmap_ior_into (&get_remat_bb_data (bb)->dead_regs,
635 bitmap_view<HARD_REG_SET> (clobbers));
636 }
637 }
638
639 /* Calculate changed_regs and dead_regs for each BB. */
640 static void
calculate_local_reg_remat_bb_data(void)641 calculate_local_reg_remat_bb_data (void)
642 {
643 basic_block bb;
644 rtx_insn *insn;
645
646 FOR_EACH_BB_FN (bb, cfun)
647 FOR_BB_INSNS (bb, insn)
648 if (NONDEBUG_INSN_P (insn))
649 set_bb_regs (bb, insn);
650 }
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
reg_overlap_for_remat_p(lra_insn_reg * reg,rtx_insn * insn)660 reg_overlap_for_remat_p (lra_insn_reg *reg, rtx_insn *insn)
661 {
662 int iter;
663 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
664 struct lra_static_insn_data *static_id = id->insn_static_data;
665 unsigned regno = reg->regno;
666 int nregs;
667
668 if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] >= 0)
669 regno = reg_renumber[regno];
670 if (regno >= FIRST_PSEUDO_REGISTER)
671 nregs = 1;
672 else
673 nregs = hard_regno_nregs (regno, reg->biggest_mode);
674
675 struct lra_insn_reg *reg2;
676
677 for (iter = 0; iter < 2; iter++)
678 for (reg2 = (iter == 0 ? id->regs : static_id->hard_regs);
679 reg2 != NULL;
680 reg2 = reg2->next)
681 {
682 int nregs2;
683 unsigned regno2 = reg2->regno;
684
685 if (reg2->type != OP_IN && regno2 >= FIRST_PSEUDO_REGISTER)
686 continue;
687
688 if (regno2 >= FIRST_PSEUDO_REGISTER && reg_renumber[regno2] >= 0)
689 regno2 = reg_renumber[regno2];
690 if (regno2 >= FIRST_PSEUDO_REGISTER)
691 nregs2 = 1;
692 else
693 nregs2 = hard_regno_nregs (regno2, reg->biggest_mode);
694
695 if ((regno2 + nregs2 - 1 >= regno && regno2 < regno + nregs)
696 || (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
call_used_input_regno_present_p(const function_abi & abi,rtx_insn * insn)704 call_used_input_regno_present_p (const function_abi &abi, rtx_insn *insn)
705 {
706 int iter;
707 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
708 struct lra_static_insn_data *static_id = id->insn_static_data;
709 struct lra_insn_reg *reg;
710
711 for (iter = 0; iter < 2; iter++)
712 for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
713 reg != NULL;
714 reg = reg->next)
715 if (reg->type == OP_IN
716 && reg->regno < FIRST_PSEUDO_REGISTER
717 && 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
calculate_livein_cands(void)724 calculate_livein_cands (void)
725 {
726 basic_block bb;
727
728 FOR_EACH_BB_FN (bb, cfun)
729 {
730 bitmap livein_regs = df_get_live_in (bb);
731 bitmap livein_cands = &get_remat_bb_data (bb)->livein_cands;
732 for (unsigned int i = 0; i < cands_num; i++)
733 {
734 cand_t cand = all_cands[i];
735 lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
736 struct lra_insn_reg *reg;
737
738 for (reg = id->regs; reg != NULL; reg = reg->next)
739 if (reg->type == OP_IN && ! bitmap_bit_p (livein_regs, reg->regno))
740 break;
741 if (reg == NULL)
742 bitmap_set_bit (livein_cands, i);
743 }
744 }
745 }
746
747 /* Calculate gen_cands for each BB. */
748 static void
calculate_gen_cands(void)749 calculate_gen_cands (void)
750 {
751 basic_block bb;
752 bitmap gen_cands;
753 rtx_insn *insn;
754
755 FOR_EACH_BB_FN (bb, cfun)
756 {
757 gen_cands = &get_remat_bb_data (bb)->gen_cands;
758 auto_bitmap gen_insns (®_obstack);
759 FOR_BB_INSNS (bb, insn)
760 if (INSN_P (insn))
761 {
762 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
763 struct lra_static_insn_data *static_id = id->insn_static_data;
764 struct lra_insn_reg *reg;
765 unsigned int uid;
766 bitmap_iterator bi;
767 cand_t cand;
768 rtx set;
769 int iter;
770 int src_regno = -1, dst_regno = -1;
771
772 if ((set = single_set (insn)) != NULL
773 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
774 {
775 src_regno = REGNO (SET_SRC (set));
776 dst_regno = REGNO (SET_DEST (set));
777 }
778
779 /* Update gen_cands: */
780 bitmap_clear (&temp_bitmap);
781 for (iter = 0; iter < 2; iter++)
782 for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
783 reg != NULL;
784 reg = reg->next)
785 if (reg->type != OP_IN
786 || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
787 EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
788 {
789 rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
790
791 cand = insn_to_cand[INSN_UID (insn2)];
792 gcc_assert (cand != NULL);
793 /* Ignore the reload insn. */
794 if (src_regno == cand->reload_regno
795 && dst_regno == cand->regno)
796 continue;
797 if (cand->regno == reg->regno
798 || reg_overlap_for_remat_p (reg, insn2))
799 {
800 bitmap_clear_bit (gen_cands, cand->index);
801 bitmap_set_bit (&temp_bitmap, uid);
802 }
803 }
804
805 if (CALL_P (insn))
806 {
807 function_abi callee_abi = insn_callee_abi (insn);
808 EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
809 {
810 rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
811
812 cand = insn_to_cand[INSN_UID (insn2)];
813 gcc_assert (cand != NULL);
814 if (call_used_input_regno_present_p (callee_abi, insn2))
815 {
816 bitmap_clear_bit (gen_cands, cand->index);
817 bitmap_set_bit (&temp_bitmap, uid);
818 }
819 }
820 }
821 bitmap_and_compl_into (gen_insns, &temp_bitmap);
822
823 cand = insn_to_cand[INSN_UID (insn)];
824 if (cand != NULL)
825 {
826 bitmap_set_bit (gen_cands, cand->index);
827 bitmap_set_bit (gen_insns, INSN_UID (insn));
828 }
829 }
830 }
831 }
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
cand_trans_fun(int bb_index,bitmap bb_in,bitmap bb_out)842 cand_trans_fun (int bb_index, bitmap bb_in, bitmap bb_out)
843 {
844 remat_bb_data_t bb_info;
845 bitmap bb_livein, bb_changed_regs, bb_dead_regs;
846 unsigned int cid;
847 bitmap_iterator bi;
848
849 bb_info = get_remat_bb_data_by_index (bb_index);
850 bb_livein = &bb_info->livein_cands;
851 bb_changed_regs = &bb_info->changed_regs;
852 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 bitmap_clear (&temp_bitmap);
858 EXECUTE_IF_SET_IN_BITMAP (bb_in, 0, cid, bi)
859 {
860 cand_t cand = all_cands[cid];
861 lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
862 struct lra_insn_reg *reg;
863
864 if (! bitmap_bit_p (bb_livein, cid))
865 {
866 bitmap_set_bit (&temp_bitmap, cid);
867 continue;
868 }
869 for (reg = id->regs; reg != NULL; reg = reg->next)
870 /* Ignore all outputs which are not the regno for
871 rematerialization. */
872 if (reg->type == OP_OUT && reg->regno != cand->regno)
873 continue;
874 else if (bitmap_bit_p (bb_changed_regs, reg->regno)
875 || bitmap_bit_p (bb_dead_regs, reg->regno))
876 {
877 bitmap_set_bit (&temp_bitmap, cid);
878 break;
879 }
880 /* Check regno for rematerialization. */
881 if (bitmap_bit_p (bb_changed_regs, cand->regno)
882 || bitmap_bit_p (bb_dead_regs, cand->regno))
883 bitmap_set_bit (&temp_bitmap, cid);
884 }
885 return bitmap_ior_and_compl (bb_out,
886 &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
cand_pav_trans_fun(int bb_index)898 cand_pav_trans_fun (int bb_index)
899 {
900 remat_bb_data_t bb_info;
901
902 bb_info = get_remat_bb_data_by_index (bb_index);
903 return cand_trans_fun (bb_index, &bb_info->pavin_cands,
904 &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
cand_pav_con_fun_0(basic_block bb)910 cand_pav_con_fun_0 (basic_block bb)
911 {
912 bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
913 }
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
cand_pav_con_fun_n(edge e)922 cand_pav_con_fun_n (edge e)
923 {
924 basic_block pred = e->src;
925 basic_block bb = e->dest;
926 remat_bb_data_t bb_info;
927 bitmap bb_pavin, pred_pavout;
928
929 bb_info = get_remat_bb_data (bb);
930 bb_pavin = &bb_info->pavin_cands;
931 pred_pavout = &get_remat_bb_data (pred)->pavout_cands;
932 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
cand_av_trans_fun(int bb_index)944 cand_av_trans_fun (int bb_index)
945 {
946 remat_bb_data_t bb_info;
947
948 bb_info = get_remat_bb_data_by_index (bb_index);
949 return cand_trans_fun (bb_index, &bb_info->avin_cands,
950 &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
cand_av_con_fun_0(basic_block bb)956 cand_av_con_fun_0 (basic_block bb)
957 {
958 bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
959 }
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
cand_av_con_fun_n(edge e)968 cand_av_con_fun_n (edge e)
969 {
970 basic_block pred = e->src;
971 basic_block bb = e->dest;
972 remat_bb_data_t bb_info;
973 bitmap bb_avin, pred_avout;
974
975 bb_info = get_remat_bb_data (bb);
976 bb_avin = &bb_info->avin_cands;
977 pred_avout = &get_remat_bb_data (pred)->avout_cands;
978 return bitmap_and_into (bb_avin, pred_avout);
979 }
980
981 /* Calculate available candidates for each BB. */
982 static void
calculate_global_remat_bb_data(void)983 calculate_global_remat_bb_data (void)
984 {
985 basic_block bb;
986
987 df_simple_dataflow
988 (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 FOR_EACH_BB_FN (bb, cfun)
993 bitmap_copy (&get_remat_bb_data (bb)->avin_cands,
994 &get_remat_bb_data (bb)->pavin_cands);
995 df_simple_dataflow
996 (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 }
1000
1001
1002
1003 /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
1004 static void
change_sp_offset(rtx_insn * insns,poly_int64 sp_offset)1005 change_sp_offset (rtx_insn *insns, poly_int64 sp_offset)
1006 {
1007 for (rtx_insn *insn = insns; insn != NULL; insn = NEXT_INSN (insn))
1008 eliminate_regs_in_insn (insn, false, false, sp_offset);
1009 }
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
get_hard_regs(struct lra_insn_reg * reg,int & nregs)1016 get_hard_regs (struct lra_insn_reg *reg, int &nregs)
1017 {
1018 int regno = reg->regno;
1019 int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
1020
1021 if (hard_regno >= 0)
1022 nregs = hard_regno_nregs (hard_regno, reg->biggest_mode);
1023 return hard_regno;
1024 }
1025
1026 /* Make copy of and register scratch pseudos in rematerialized insn
1027 REMAT_INSN. */
1028 static void
update_scratch_ops(rtx_insn * remat_insn)1029 update_scratch_ops (rtx_insn *remat_insn)
1030 {
1031 lra_insn_recog_data_t id = lra_get_insn_recog_data (remat_insn);
1032 struct lra_static_insn_data *static_id = id->insn_static_data;
1033 for (int i = 0; i < static_id->n_operands; i++)
1034 {
1035 rtx *loc = id->operand_loc[i];
1036 if (! REG_P (*loc))
1037 continue;
1038 int regno = REGNO (*loc);
1039 if (! ira_former_scratch_p (regno))
1040 continue;
1041 *loc = lra_create_new_reg (GET_MODE (*loc), *loc,
1042 lra_get_allocno_class (regno),
1043 "scratch pseudo copy");
1044 ira_register_new_scratch_op (remat_insn, i, id->icode);
1045 }
1046
1047 }
1048
1049 /* Insert rematerialization insns using the data-flow data calculated
1050 earlier. */
1051 static bool
do_remat(void)1052 do_remat (void)
1053 {
1054 unsigned regno;
1055 rtx_insn *insn;
1056 basic_block bb;
1057 bool changed_p = false;
1058 /* Living hard regs and hard registers of living pseudos. */
1059 HARD_REG_SET live_hard_regs;
1060 bitmap_iterator bi;
1061
1062 auto_bitmap avail_cands (®_obstack);
1063 auto_bitmap active_cands (®_obstack);
1064 FOR_EACH_BB_FN (bb, cfun)
1065 {
1066 CLEAR_HARD_REG_SET (live_hard_regs);
1067 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), 0, regno, bi)
1068 {
1069 int hard_regno = regno < FIRST_PSEUDO_REGISTER
1070 ? regno
1071 : reg_renumber[regno];
1072 if (hard_regno >= 0)
1073 SET_HARD_REG_BIT (live_hard_regs, hard_regno);
1074 }
1075 bitmap_and (avail_cands, &get_remat_bb_data (bb)->avin_cands,
1076 &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 bitmap_copy (active_cands, avail_cands);
1080 FOR_BB_INSNS (bb, insn)
1081 {
1082 if (!NONDEBUG_INSN_P (insn))
1083 continue;
1084
1085 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
1086 struct lra_static_insn_data *static_id = id->insn_static_data;
1087 struct lra_insn_reg *reg;
1088 cand_t cand;
1089 unsigned int cid;
1090 bitmap_iterator bi;
1091 rtx set;
1092 int iter;
1093 int src_regno = -1, dst_regno = -1;
1094
1095 if ((set = single_set (insn)) != NULL
1096 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
1097 {
1098 src_regno = REGNO (SET_SRC (set));
1099 dst_regno = REGNO (SET_DEST (set));
1100 }
1101
1102 cand = NULL;
1103 /* Check possibility of rematerialization (hard reg or
1104 unpsilled pseudo <- spilled pseudo): */
1105 if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER
1106 && reg_renumber[src_regno] < 0
1107 && (dst_regno < FIRST_PSEUDO_REGISTER
1108 || reg_renumber[dst_regno] >= 0))
1109 {
1110 for (cand = regno_cands[src_regno];
1111 cand != NULL;
1112 cand = cand->next_regno_cand)
1113 if (bitmap_bit_p (avail_cands, cand->index)
1114 && bitmap_bit_p (active_cands, cand->index))
1115 break;
1116 }
1117 int i, hard_regno, nregs;
1118 int dst_hard_regno, dst_nregs;
1119 rtx_insn *remat_insn = NULL;
1120 poly_int64 cand_sp_offset = 0;
1121 if (cand != NULL)
1122 {
1123 lra_insn_recog_data_t cand_id
1124 = lra_get_insn_recog_data (cand->insn);
1125 struct lra_static_insn_data *static_cand_id
1126 = cand_id->insn_static_data;
1127 rtx saved_op = *cand_id->operand_loc[cand->nop];
1128
1129 /* Check clobbers do not kill something living. */
1130 gcc_assert (REG_P (saved_op));
1131 int ignore_regno = REGNO (saved_op);
1132
1133 dst_hard_regno = dst_regno < FIRST_PSEUDO_REGISTER
1134 ? dst_regno : reg_renumber[dst_regno];
1135 gcc_assert (dst_hard_regno >= 0);
1136 machine_mode mode = GET_MODE (SET_DEST (set));
1137 dst_nregs = hard_regno_nregs (dst_hard_regno, mode);
1138
1139 for (reg = cand_id->regs; reg != NULL; reg = reg->next)
1140 if (reg->type != OP_IN && reg->regno != ignore_regno)
1141 {
1142 hard_regno = get_hard_regs (reg, nregs);
1143 gcc_assert (hard_regno >= 0);
1144 for (i = 0; i < nregs; i++)
1145 if (TEST_HARD_REG_BIT (live_hard_regs, hard_regno + i))
1146 break;
1147 if (i < nregs)
1148 break;
1149 /* Ensure the clobber also doesn't overlap dst_regno. */
1150 if (hard_regno + nregs > dst_hard_regno
1151 && hard_regno < dst_hard_regno + dst_nregs)
1152 break;
1153 }
1154
1155 if (reg == NULL)
1156 {
1157 for (reg = static_cand_id->hard_regs;
1158 reg != NULL;
1159 reg = reg->next)
1160 if (reg->type != OP_IN)
1161 {
1162 if (TEST_HARD_REG_BIT (live_hard_regs, reg->regno))
1163 break;
1164 if (reg->regno >= dst_hard_regno
1165 && reg->regno < dst_hard_regno + dst_nregs)
1166 break;
1167 }
1168 }
1169
1170 if (reg == NULL)
1171 {
1172 *cand_id->operand_loc[cand->nop] = SET_DEST (set);
1173 lra_update_insn_regno_info (cand->insn);
1174 bool ok_p = lra_constrain_insn (cand->insn);
1175 if (ok_p)
1176 {
1177 rtx remat_pat = copy_insn (PATTERN (cand->insn));
1178
1179 start_sequence ();
1180 emit_insn (remat_pat);
1181 remat_insn = get_insns ();
1182 end_sequence ();
1183 if (recog_memoized (remat_insn) < 0)
1184 remat_insn = NULL;
1185 cand_sp_offset = cand_id->sp_offset;
1186 }
1187 *cand_id->operand_loc[cand->nop] = saved_op;
1188 lra_update_insn_regno_info (cand->insn);
1189 }
1190 }
1191
1192 bitmap_clear (&temp_bitmap);
1193 /* Update avail_cands (see analogous code for
1194 calculate_gen_cands). */
1195 for (iter = 0; iter < 2; iter++)
1196 for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
1197 reg != NULL;
1198 reg = reg->next)
1199 if (reg->type != OP_IN
1200 || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1201 EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1202 {
1203 cand = all_cands[cid];
1204
1205 /* Ignore the reload insn. */
1206 if (src_regno == cand->reload_regno
1207 && dst_regno == cand->regno)
1208 continue;
1209 if (cand->regno == reg->regno
1210 || reg_overlap_for_remat_p (reg, cand->insn))
1211 bitmap_set_bit (&temp_bitmap, cand->index);
1212 }
1213
1214 if (CALL_P (insn))
1215 {
1216 function_abi callee_abi = insn_callee_abi (insn);
1217 EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1218 {
1219 cand = all_cands[cid];
1220
1221 if (call_used_input_regno_present_p (callee_abi, cand->insn))
1222 bitmap_set_bit (&temp_bitmap, cand->index);
1223 }
1224 }
1225
1226 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 cand = insn_to_cand_activation[INSN_UID (insn)];
1231 if (cand)
1232 bitmap_set_bit (active_cands, cand->index);
1233
1234 cand = insn_to_cand[INSN_UID (insn)];
1235 if (cand != NULL)
1236 {
1237 bitmap_set_bit (avail_cands, cand->index);
1238 if (cand->reload_regno == -1)
1239 bitmap_set_bit (active_cands, cand->index);
1240 else
1241 bitmap_clear_bit (active_cands, cand->index);
1242 }
1243
1244 if (remat_insn != NULL)
1245 {
1246 poly_int64 sp_offset_change = cand_sp_offset - id->sp_offset;
1247 if (maybe_ne (sp_offset_change, 0))
1248 change_sp_offset (remat_insn, sp_offset_change);
1249 update_scratch_ops (remat_insn);
1250 lra_process_new_insns (insn, remat_insn, NULL,
1251 "Inserting rematerialization insn");
1252 lra_set_insn_deleted (insn);
1253 changed_p = true;
1254 continue;
1255 }
1256
1257 /* Update live hard regs: */
1258 for (reg = id->regs; reg != NULL; reg = reg->next)
1259 if (reg->type == OP_IN
1260 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1261 {
1262 if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1263 continue;
1264 for (i = 0; i < nregs; i++)
1265 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 for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1270 if (reg->type == OP_IN
1271 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1272 CLEAR_HARD_REG_BIT (live_hard_regs, reg->regno);
1273 /* Inputs have been processed, now process outputs. */
1274 for (reg = id->regs; reg != NULL; reg = reg->next)
1275 if (reg->type != OP_IN
1276 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1277 {
1278 if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1279 continue;
1280 for (i = 0; i < nregs; i++)
1281 SET_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1282 }
1283 for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1284 if (reg->type != OP_IN
1285 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1286 SET_HARD_REG_BIT (live_hard_regs, reg->regno);
1287 }
1288 }
1289 return changed_p;
1290 }
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
lra_remat(void)1300 lra_remat (void)
1301 {
1302 basic_block bb;
1303 bool result;
1304 int max_regno = max_reg_num ();
1305
1306 if (! flag_lra_remat)
1307 return false;
1308 lra_rematerialization_iter++;
1309 if (lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
1310 return false;
1311 if (lra_dump_file != NULL)
1312 fprintf (lra_dump_file,
1313 "\n******** Rematerialization #%d: ********\n\n",
1314 lra_rematerialization_iter);
1315 timevar_push (TV_LRA_REMAT);
1316 insn_to_cand = XCNEWVEC (cand_t, get_max_uid ());
1317 insn_to_cand_activation = XCNEWVEC (cand_t, get_max_uid ());
1318 regno_cands = XCNEWVEC (cand_t, max_regno);
1319 all_cands.create (8000);
1320 initiate_cand_table ();
1321 create_remat_bb_data ();
1322 bitmap_initialize (&temp_bitmap, ®_obstack);
1323 bitmap_initialize (&subreg_regs, ®_obstack);
1324 calculate_local_reg_remat_bb_data ();
1325 create_cands ();
1326 calculate_livein_cands ();
1327 calculate_gen_cands ();
1328 bitmap_initialize (&all_blocks, ®_obstack);
1329 FOR_ALL_BB_FN (bb, cfun)
1330 bitmap_set_bit (&all_blocks, bb->index);
1331 calculate_global_remat_bb_data ();
1332 dump_candidates_and_remat_bb_data ();
1333 result = do_remat ();
1334 all_cands.release ();
1335 bitmap_clear (&temp_bitmap);
1336 bitmap_clear (&subreg_regs);
1337 finish_remat_bb_data ();
1338 finish_cand_table ();
1339 bitmap_clear (&all_blocks);
1340 free (regno_cands);
1341 free (insn_to_cand);
1342 free (insn_to_cand_activation);
1343 timevar_pop (TV_LRA_REMAT);
1344 return result;
1345 }
1346