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