1 /* Rematerialize pseudos values.
2 Copyright (C) 2014-2020 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 of INSN. */
655 static bool
reg_overlap_for_remat_p(lra_insn_reg * reg,rtx_insn * insn)656 reg_overlap_for_remat_p (lra_insn_reg *reg, rtx_insn *insn)
657 {
658 int iter;
659 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
660 struct lra_static_insn_data *static_id = id->insn_static_data;
661 unsigned regno = reg->regno;
662 int nregs;
663
664 if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] >= 0)
665 regno = reg_renumber[regno];
666 if (regno >= FIRST_PSEUDO_REGISTER)
667 nregs = 1;
668 else
669 nregs = hard_regno_nregs (regno, reg->biggest_mode);
670
671 struct lra_insn_reg *reg2;
672
673 for (iter = 0; iter < 2; iter++)
674 for (reg2 = (iter == 0 ? id->regs : static_id->hard_regs);
675 reg2 != NULL;
676 reg2 = reg2->next)
677 {
678 if (reg2->type != OP_IN)
679 continue;
680 unsigned regno2 = reg2->regno;
681 int nregs2;
682
683 if (regno2 >= FIRST_PSEUDO_REGISTER && reg_renumber[regno2] >= 0)
684 regno2 = reg_renumber[regno2];
685 if (regno2 >= FIRST_PSEUDO_REGISTER)
686 nregs2 = 1;
687 else
688 nregs2 = hard_regno_nregs (regno2, reg->biggest_mode);
689
690 if ((regno2 + nregs2 - 1 >= regno && regno2 < regno + nregs)
691 || (regno + nregs - 1 >= regno2 && regno < regno2 + nregs2))
692 return true;
693 }
694 return false;
695 }
696
697 /* Return true if a call used register is an input operand of INSN. */
698 static bool
call_used_input_regno_present_p(const function_abi & abi,rtx_insn * insn)699 call_used_input_regno_present_p (const function_abi &abi, rtx_insn *insn)
700 {
701 int iter;
702 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
703 struct lra_static_insn_data *static_id = id->insn_static_data;
704 struct lra_insn_reg *reg;
705
706 for (iter = 0; iter < 2; iter++)
707 for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
708 reg != NULL;
709 reg = reg->next)
710 if (reg->type == OP_IN
711 && reg->regno < FIRST_PSEUDO_REGISTER
712 && abi.clobbers_reg_p (reg->biggest_mode, reg->regno))
713 return true;
714 return false;
715 }
716
717 /* Calculate livein_cands for each BB. */
718 static void
calculate_livein_cands(void)719 calculate_livein_cands (void)
720 {
721 basic_block bb;
722
723 FOR_EACH_BB_FN (bb, cfun)
724 {
725 bitmap livein_regs = df_get_live_in (bb);
726 bitmap livein_cands = &get_remat_bb_data (bb)->livein_cands;
727 for (unsigned int i = 0; i < cands_num; i++)
728 {
729 cand_t cand = all_cands[i];
730 lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
731 struct lra_insn_reg *reg;
732
733 for (reg = id->regs; reg != NULL; reg = reg->next)
734 if (reg->type == OP_IN && ! bitmap_bit_p (livein_regs, reg->regno))
735 break;
736 if (reg == NULL)
737 bitmap_set_bit (livein_cands, i);
738 }
739 }
740 }
741
742 /* Calculate gen_cands for each BB. */
743 static void
calculate_gen_cands(void)744 calculate_gen_cands (void)
745 {
746 basic_block bb;
747 bitmap gen_cands;
748 rtx_insn *insn;
749
750 FOR_EACH_BB_FN (bb, cfun)
751 {
752 gen_cands = &get_remat_bb_data (bb)->gen_cands;
753 auto_bitmap gen_insns (®_obstack);
754 FOR_BB_INSNS (bb, insn)
755 if (INSN_P (insn))
756 {
757 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
758 struct lra_static_insn_data *static_id = id->insn_static_data;
759 struct lra_insn_reg *reg;
760 unsigned int uid;
761 bitmap_iterator bi;
762 cand_t cand;
763 rtx set;
764 int iter;
765 int src_regno = -1, dst_regno = -1;
766
767 if ((set = single_set (insn)) != NULL
768 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
769 {
770 src_regno = REGNO (SET_SRC (set));
771 dst_regno = REGNO (SET_DEST (set));
772 }
773
774 /* Update gen_cands: */
775 bitmap_clear (&temp_bitmap);
776 for (iter = 0; iter < 2; iter++)
777 for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
778 reg != NULL;
779 reg = reg->next)
780 if (reg->type != OP_IN
781 || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
782 EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
783 {
784 rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
785
786 cand = insn_to_cand[INSN_UID (insn2)];
787 gcc_assert (cand != NULL);
788 /* Ignore the reload insn. */
789 if (src_regno == cand->reload_regno
790 && dst_regno == cand->regno)
791 continue;
792 if (cand->regno == reg->regno
793 || reg_overlap_for_remat_p (reg, insn2))
794 {
795 bitmap_clear_bit (gen_cands, cand->index);
796 bitmap_set_bit (&temp_bitmap, uid);
797 }
798 }
799
800 if (CALL_P (insn))
801 {
802 function_abi callee_abi = insn_callee_abi (insn);
803 EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
804 {
805 rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
806
807 cand = insn_to_cand[INSN_UID (insn2)];
808 gcc_assert (cand != NULL);
809 if (call_used_input_regno_present_p (callee_abi, insn2))
810 {
811 bitmap_clear_bit (gen_cands, cand->index);
812 bitmap_set_bit (&temp_bitmap, uid);
813 }
814 }
815 }
816 bitmap_and_compl_into (gen_insns, &temp_bitmap);
817
818 cand = insn_to_cand[INSN_UID (insn)];
819 if (cand != NULL)
820 {
821 bitmap_set_bit (gen_cands, cand->index);
822 bitmap_set_bit (gen_insns, INSN_UID (insn));
823 }
824 }
825 }
826 }
827
828
829
830 /* The common transfer function used by the DF equation solver to
831 propagate (partial) availability info BB_IN to BB_OUT through block
832 with BB_INDEX according to the following equation:
833
834 bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
835 */
836 static bool
cand_trans_fun(int bb_index,bitmap bb_in,bitmap bb_out)837 cand_trans_fun (int bb_index, bitmap bb_in, bitmap bb_out)
838 {
839 remat_bb_data_t bb_info;
840 bitmap bb_livein, bb_changed_regs, bb_dead_regs;
841 unsigned int cid;
842 bitmap_iterator bi;
843
844 bb_info = get_remat_bb_data_by_index (bb_index);
845 bb_livein = &bb_info->livein_cands;
846 bb_changed_regs = &bb_info->changed_regs;
847 bb_dead_regs = &bb_info->dead_regs;
848 /* Calculate killed avin cands -- cands whose regs are changed or
849 becoming dead in the BB. We calculate it here as we hope that
850 repeated calculations are compensated by smaller size of BB_IN in
851 comparison with all candidates number. */
852 bitmap_clear (&temp_bitmap);
853 EXECUTE_IF_SET_IN_BITMAP (bb_in, 0, cid, bi)
854 {
855 cand_t cand = all_cands[cid];
856 lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
857 struct lra_insn_reg *reg;
858
859 if (! bitmap_bit_p (bb_livein, cid))
860 {
861 bitmap_set_bit (&temp_bitmap, cid);
862 continue;
863 }
864 for (reg = id->regs; reg != NULL; reg = reg->next)
865 /* Ignore all outputs which are not the regno for
866 rematerialization. */
867 if (reg->type == OP_OUT && reg->regno != cand->regno)
868 continue;
869 else if (bitmap_bit_p (bb_changed_regs, reg->regno)
870 || bitmap_bit_p (bb_dead_regs, reg->regno))
871 {
872 bitmap_set_bit (&temp_bitmap, cid);
873 break;
874 }
875 /* Check regno for rematerialization. */
876 if (bitmap_bit_p (bb_changed_regs, cand->regno)
877 || bitmap_bit_p (bb_dead_regs, cand->regno))
878 bitmap_set_bit (&temp_bitmap, cid);
879 }
880 return bitmap_ior_and_compl (bb_out,
881 &bb_info->gen_cands, bb_in, &temp_bitmap);
882 }
883
884
885
886 /* The transfer function used by the DF equation solver to propagate
887 partial candidate availability info through block with BB_INDEX
888 according to the following equation:
889
890 bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
891 */
892 static bool
cand_pav_trans_fun(int bb_index)893 cand_pav_trans_fun (int bb_index)
894 {
895 remat_bb_data_t bb_info;
896
897 bb_info = get_remat_bb_data_by_index (bb_index);
898 return cand_trans_fun (bb_index, &bb_info->pavin_cands,
899 &bb_info->pavout_cands);
900 }
901
902 /* The confluence function used by the DF equation solver to set up
903 cand_pav info for a block BB without predecessor. */
904 static void
cand_pav_con_fun_0(basic_block bb)905 cand_pav_con_fun_0 (basic_block bb)
906 {
907 bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
908 }
909
910 /* The confluence function used by the DF equation solver to propagate
911 partial candidate availability info from predecessor to successor
912 on edge E (pred->bb) according to the following equation:
913
914 bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
915 */
916 static bool
cand_pav_con_fun_n(edge e)917 cand_pav_con_fun_n (edge e)
918 {
919 basic_block pred = e->src;
920 basic_block bb = e->dest;
921 remat_bb_data_t bb_info;
922 bitmap bb_pavin, pred_pavout;
923
924 bb_info = get_remat_bb_data (bb);
925 bb_pavin = &bb_info->pavin_cands;
926 pred_pavout = &get_remat_bb_data (pred)->pavout_cands;
927 return bitmap_ior_into (bb_pavin, pred_pavout);
928 }
929
930
931
932 /* The transfer function used by the DF equation solver to propagate
933 candidate availability info through block with BB_INDEX according
934 to the following equation:
935
936 bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
937 */
938 static bool
cand_av_trans_fun(int bb_index)939 cand_av_trans_fun (int bb_index)
940 {
941 remat_bb_data_t bb_info;
942
943 bb_info = get_remat_bb_data_by_index (bb_index);
944 return cand_trans_fun (bb_index, &bb_info->avin_cands,
945 &bb_info->avout_cands);
946 }
947
948 /* The confluence function used by the DF equation solver to set up
949 cand_av info for a block BB without predecessor. */
950 static void
cand_av_con_fun_0(basic_block bb)951 cand_av_con_fun_0 (basic_block bb)
952 {
953 bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
954 }
955
956 /* The confluence function used by the DF equation solver to propagate
957 cand_av info from predecessor to successor on edge E (pred->bb)
958 according to the following equation:
959
960 bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
961 */
962 static bool
cand_av_con_fun_n(edge e)963 cand_av_con_fun_n (edge e)
964 {
965 basic_block pred = e->src;
966 basic_block bb = e->dest;
967 remat_bb_data_t bb_info;
968 bitmap bb_avin, pred_avout;
969
970 bb_info = get_remat_bb_data (bb);
971 bb_avin = &bb_info->avin_cands;
972 pred_avout = &get_remat_bb_data (pred)->avout_cands;
973 return bitmap_and_into (bb_avin, pred_avout);
974 }
975
976 /* Calculate available candidates for each BB. */
977 static void
calculate_global_remat_bb_data(void)978 calculate_global_remat_bb_data (void)
979 {
980 basic_block bb;
981
982 df_simple_dataflow
983 (DF_FORWARD, NULL, cand_pav_con_fun_0, cand_pav_con_fun_n,
984 cand_pav_trans_fun, &all_blocks,
985 df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
986 /* Initialize avin by pavin. */
987 FOR_EACH_BB_FN (bb, cfun)
988 bitmap_copy (&get_remat_bb_data (bb)->avin_cands,
989 &get_remat_bb_data (bb)->pavin_cands);
990 df_simple_dataflow
991 (DF_FORWARD, NULL, cand_av_con_fun_0, cand_av_con_fun_n,
992 cand_av_trans_fun, &all_blocks,
993 df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
994 }
995
996
997
998 /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
999 static void
change_sp_offset(rtx_insn * insns,poly_int64 sp_offset)1000 change_sp_offset (rtx_insn *insns, poly_int64 sp_offset)
1001 {
1002 for (rtx_insn *insn = insns; insn != NULL; insn = NEXT_INSN (insn))
1003 eliminate_regs_in_insn (insn, false, false, sp_offset);
1004 }
1005
1006 /* Return start hard register of REG (can be a hard or a pseudo reg)
1007 or -1 (if it is a spilled pseudo). Return number of hard registers
1008 occupied by REG through parameter NREGS if the start hard reg is
1009 not negative. */
1010 static int
get_hard_regs(struct lra_insn_reg * reg,int & nregs)1011 get_hard_regs (struct lra_insn_reg *reg, int &nregs)
1012 {
1013 int regno = reg->regno;
1014 int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
1015
1016 if (hard_regno >= 0)
1017 nregs = hard_regno_nregs (hard_regno, reg->biggest_mode);
1018 return hard_regno;
1019 }
1020
1021 /* Make copy of and register scratch pseudos in rematerialized insn
1022 REMAT_INSN. */
1023 static void
update_scratch_ops(rtx_insn * remat_insn)1024 update_scratch_ops (rtx_insn *remat_insn)
1025 {
1026 lra_insn_recog_data_t id = lra_get_insn_recog_data (remat_insn);
1027 struct lra_static_insn_data *static_id = id->insn_static_data;
1028 for (int i = 0; i < static_id->n_operands; i++)
1029 {
1030 rtx *loc = id->operand_loc[i];
1031 if (! REG_P (*loc))
1032 continue;
1033 int regno = REGNO (*loc);
1034 if (! lra_former_scratch_p (regno))
1035 continue;
1036 *loc = lra_create_new_reg (GET_MODE (*loc), *loc,
1037 lra_get_allocno_class (regno),
1038 "scratch pseudo copy");
1039 lra_register_new_scratch_op (remat_insn, i, id->icode);
1040 }
1041
1042 }
1043
1044 /* Insert rematerialization insns using the data-flow data calculated
1045 earlier. */
1046 static bool
do_remat(void)1047 do_remat (void)
1048 {
1049 unsigned regno;
1050 rtx_insn *insn;
1051 basic_block bb;
1052 bool changed_p = false;
1053 /* Living hard regs and hard registers of living pseudos. */
1054 HARD_REG_SET live_hard_regs;
1055 bitmap_iterator bi;
1056
1057 auto_bitmap avail_cands (®_obstack);
1058 auto_bitmap active_cands (®_obstack);
1059 FOR_EACH_BB_FN (bb, cfun)
1060 {
1061 CLEAR_HARD_REG_SET (live_hard_regs);
1062 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), 0, regno, bi)
1063 {
1064 int hard_regno = regno < FIRST_PSEUDO_REGISTER
1065 ? regno
1066 : reg_renumber[regno];
1067 if (hard_regno >= 0)
1068 SET_HARD_REG_BIT (live_hard_regs, hard_regno);
1069 }
1070 bitmap_and (avail_cands, &get_remat_bb_data (bb)->avin_cands,
1071 &get_remat_bb_data (bb)->livein_cands);
1072 /* Activating insns are always in the same block as their corresponding
1073 remat insn, so at the start of a block the two bitsets are equal. */
1074 bitmap_copy (active_cands, avail_cands);
1075 FOR_BB_INSNS (bb, insn)
1076 {
1077 if (!NONDEBUG_INSN_P (insn))
1078 continue;
1079
1080 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
1081 struct lra_static_insn_data *static_id = id->insn_static_data;
1082 struct lra_insn_reg *reg;
1083 cand_t cand;
1084 unsigned int cid;
1085 bitmap_iterator bi;
1086 rtx set;
1087 int iter;
1088 int src_regno = -1, dst_regno = -1;
1089
1090 if ((set = single_set (insn)) != NULL
1091 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
1092 {
1093 src_regno = REGNO (SET_SRC (set));
1094 dst_regno = REGNO (SET_DEST (set));
1095 }
1096
1097 cand = NULL;
1098 /* Check possibility of rematerialization (hard reg or
1099 unpsilled pseudo <- spilled pseudo): */
1100 if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER
1101 && reg_renumber[src_regno] < 0
1102 && (dst_regno < FIRST_PSEUDO_REGISTER
1103 || reg_renumber[dst_regno] >= 0))
1104 {
1105 for (cand = regno_cands[src_regno];
1106 cand != NULL;
1107 cand = cand->next_regno_cand)
1108 if (bitmap_bit_p (avail_cands, cand->index)
1109 && bitmap_bit_p (active_cands, cand->index))
1110 break;
1111 }
1112 int i, hard_regno, nregs;
1113 int dst_hard_regno, dst_nregs;
1114 rtx_insn *remat_insn = NULL;
1115 poly_int64 cand_sp_offset = 0;
1116 if (cand != NULL)
1117 {
1118 lra_insn_recog_data_t cand_id
1119 = lra_get_insn_recog_data (cand->insn);
1120 struct lra_static_insn_data *static_cand_id
1121 = cand_id->insn_static_data;
1122 rtx saved_op = *cand_id->operand_loc[cand->nop];
1123
1124 /* Check clobbers do not kill something living. */
1125 gcc_assert (REG_P (saved_op));
1126 int ignore_regno = REGNO (saved_op);
1127
1128 dst_hard_regno = dst_regno < FIRST_PSEUDO_REGISTER
1129 ? dst_regno : reg_renumber[dst_regno];
1130 gcc_assert (dst_hard_regno >= 0);
1131 machine_mode mode = GET_MODE (SET_DEST (set));
1132 dst_nregs = hard_regno_nregs (dst_hard_regno, mode);
1133
1134 for (reg = cand_id->regs; reg != NULL; reg = reg->next)
1135 if (reg->type != OP_IN && reg->regno != ignore_regno)
1136 {
1137 hard_regno = get_hard_regs (reg, nregs);
1138 gcc_assert (hard_regno >= 0);
1139 for (i = 0; i < nregs; i++)
1140 if (TEST_HARD_REG_BIT (live_hard_regs, hard_regno + i))
1141 break;
1142 if (i < nregs)
1143 break;
1144 /* Ensure the clobber also doesn't overlap dst_regno. */
1145 if (hard_regno + nregs > dst_hard_regno
1146 && hard_regno < dst_hard_regno + dst_nregs)
1147 break;
1148 }
1149
1150 if (reg == NULL)
1151 {
1152 for (reg = static_cand_id->hard_regs;
1153 reg != NULL;
1154 reg = reg->next)
1155 if (reg->type != OP_IN)
1156 {
1157 if (TEST_HARD_REG_BIT (live_hard_regs, reg->regno))
1158 break;
1159 if (reg->regno >= dst_hard_regno
1160 && reg->regno < dst_hard_regno + dst_nregs)
1161 break;
1162 }
1163 }
1164
1165 if (reg == NULL)
1166 {
1167 *cand_id->operand_loc[cand->nop] = SET_DEST (set);
1168 lra_update_insn_regno_info (cand->insn);
1169 bool ok_p = lra_constrain_insn (cand->insn);
1170 if (ok_p)
1171 {
1172 rtx remat_pat = copy_insn (PATTERN (cand->insn));
1173
1174 start_sequence ();
1175 emit_insn (remat_pat);
1176 remat_insn = get_insns ();
1177 end_sequence ();
1178 if (recog_memoized (remat_insn) < 0)
1179 remat_insn = NULL;
1180 cand_sp_offset = cand_id->sp_offset;
1181 }
1182 *cand_id->operand_loc[cand->nop] = saved_op;
1183 lra_update_insn_regno_info (cand->insn);
1184 }
1185 }
1186
1187 bitmap_clear (&temp_bitmap);
1188 /* Update avail_cands (see analogous code for
1189 calculate_gen_cands). */
1190 for (iter = 0; iter < 2; iter++)
1191 for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
1192 reg != NULL;
1193 reg = reg->next)
1194 if (reg->type != OP_IN
1195 || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1196 EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1197 {
1198 cand = all_cands[cid];
1199
1200 /* Ignore the reload insn. */
1201 if (src_regno == cand->reload_regno
1202 && dst_regno == cand->regno)
1203 continue;
1204 if (cand->regno == reg->regno
1205 || reg_overlap_for_remat_p (reg, cand->insn))
1206 bitmap_set_bit (&temp_bitmap, cand->index);
1207 }
1208
1209 if (CALL_P (insn))
1210 {
1211 function_abi callee_abi = insn_callee_abi (insn);
1212 EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
1213 {
1214 cand = all_cands[cid];
1215
1216 if (call_used_input_regno_present_p (callee_abi, cand->insn))
1217 bitmap_set_bit (&temp_bitmap, cand->index);
1218 }
1219 }
1220
1221 bitmap_and_compl_into (avail_cands, &temp_bitmap);
1222
1223 /* Now see whether a candidate is made active or available
1224 by this insn. */
1225 cand = insn_to_cand_activation[INSN_UID (insn)];
1226 if (cand)
1227 bitmap_set_bit (active_cands, cand->index);
1228
1229 cand = insn_to_cand[INSN_UID (insn)];
1230 if (cand != NULL)
1231 {
1232 bitmap_set_bit (avail_cands, cand->index);
1233 if (cand->reload_regno == -1)
1234 bitmap_set_bit (active_cands, cand->index);
1235 else
1236 bitmap_clear_bit (active_cands, cand->index);
1237 }
1238
1239 if (remat_insn != NULL)
1240 {
1241 poly_int64 sp_offset_change = cand_sp_offset - id->sp_offset;
1242 if (maybe_ne (sp_offset_change, 0))
1243 change_sp_offset (remat_insn, sp_offset_change);
1244 update_scratch_ops (remat_insn);
1245 lra_process_new_insns (insn, remat_insn, NULL,
1246 "Inserting rematerialization insn");
1247 lra_set_insn_deleted (insn);
1248 changed_p = true;
1249 continue;
1250 }
1251
1252 /* Update live hard regs: */
1253 for (reg = id->regs; reg != NULL; reg = reg->next)
1254 if (reg->type == OP_IN
1255 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1256 {
1257 if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1258 continue;
1259 for (i = 0; i < nregs; i++)
1260 CLEAR_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1261 }
1262 /* Process also hard regs (e.g. CC register) which are part
1263 of insn definition. */
1264 for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1265 if (reg->type == OP_IN
1266 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1267 CLEAR_HARD_REG_BIT (live_hard_regs, reg->regno);
1268 /* Inputs have been processed, now process outputs. */
1269 for (reg = id->regs; reg != NULL; reg = reg->next)
1270 if (reg->type != OP_IN
1271 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1272 {
1273 if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1274 continue;
1275 for (i = 0; i < nregs; i++)
1276 SET_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1277 }
1278 for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1279 if (reg->type != OP_IN
1280 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1281 SET_HARD_REG_BIT (live_hard_regs, reg->regno);
1282 }
1283 }
1284 return changed_p;
1285 }
1286
1287
1288
1289 /* Current number of rematerialization iteration. */
1290 int lra_rematerialization_iter;
1291
1292 /* Entry point of the rematerialization sub-pass. Return true if we
1293 did any rematerialization. */
1294 bool
lra_remat(void)1295 lra_remat (void)
1296 {
1297 basic_block bb;
1298 bool result;
1299 int max_regno = max_reg_num ();
1300
1301 if (! flag_lra_remat)
1302 return false;
1303 lra_rematerialization_iter++;
1304 if (lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
1305 return false;
1306 if (lra_dump_file != NULL)
1307 fprintf (lra_dump_file,
1308 "\n******** Rematerialization #%d: ********\n\n",
1309 lra_rematerialization_iter);
1310 timevar_push (TV_LRA_REMAT);
1311 insn_to_cand = XCNEWVEC (cand_t, get_max_uid ());
1312 insn_to_cand_activation = XCNEWVEC (cand_t, get_max_uid ());
1313 regno_cands = XCNEWVEC (cand_t, max_regno);
1314 all_cands.create (8000);
1315 initiate_cand_table ();
1316 create_remat_bb_data ();
1317 bitmap_initialize (&temp_bitmap, ®_obstack);
1318 bitmap_initialize (&subreg_regs, ®_obstack);
1319 calculate_local_reg_remat_bb_data ();
1320 create_cands ();
1321 calculate_livein_cands ();
1322 calculate_gen_cands ();
1323 bitmap_initialize (&all_blocks, ®_obstack);
1324 FOR_ALL_BB_FN (bb, cfun)
1325 bitmap_set_bit (&all_blocks, bb->index);
1326 calculate_global_remat_bb_data ();
1327 dump_candidates_and_remat_bb_data ();
1328 result = do_remat ();
1329 all_cands.release ();
1330 bitmap_clear (&temp_bitmap);
1331 bitmap_clear (&subreg_regs);
1332 finish_remat_bb_data ();
1333 finish_cand_table ();
1334 bitmap_clear (&all_blocks);
1335 free (regno_cands);
1336 free (insn_to_cand);
1337 free (insn_to_cand_activation);
1338 timevar_pop (TV_LRA_REMAT);
1339 return result;
1340 }
1341