1 /* Rematerialize pseudos values.
2 Copyright (C) 2014 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
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
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
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/>. */
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.
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.
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
38 The rematerialization sub-pass could be improved further in the
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
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
57 #include "coretypes.h"
59 #include "hard-reg-set.h"
61 #include "rtl-error.h"
64 #include "insn-config.h"
76 #include "dominance.h"
78 #include "basic-block.h"
82 #include "sparseset.h"
87 /* Number of candidates for rematerialization. */
88 static unsigned int cands_num
;
90 /* The following is used for representation of call_used_reg_set in
91 form array whose elements are hard register numbers with nonzero bit
92 in CALL_USED_REG_SET. */
93 static int call_used_regs_arr_len
;
94 static int call_used_regs_arr
[FIRST_PSEUDO_REGISTER
];
96 /* Bitmap used for different calculations. */
97 static bitmap_head temp_bitmap
;
99 typedef struct cand
*cand_t
;
100 typedef const struct cand
*const_cand_t
;
102 /* Insn candidates for rematerialization. The candidate insn should
103 have the following properies:
104 o no any memory (as access to memory is non-profitable)
105 o no INOUT regs (it means no non-paradoxical subreg of output reg)
106 o one output spilled pseudo (or reload pseudo of a spilled pseudo)
107 o all other pseudos are with assigned hard regs. */
110 /* Index of the candidates in all_cands. */
112 /* The candidate insn. */
114 /* Insn pseudo regno for rematerialization. */
116 /* Non-negative if a reload pseudo is in the insn instead of the
117 pseudo for rematerialization. */
119 /* Number of the operand containing the regno or its reload
122 /* Next candidate for the same regno. */
123 cand_t next_regno_cand
;
126 /* Vector containing all candidates. */
127 static vec
<cand_t
> all_cands
;
128 /* Map: insn -> candidate representing it. It is null if the insn can
129 not be used for rematerialization. */
130 static cand_t
*insn_to_cand
;
132 /* Map regno -> candidates can be used for the regno
133 rematerialization. */
134 static cand_t
*regno_cands
;
136 /* Data about basic blocks used for the rematerialization
140 /* Basic block about which the below data are. */
142 /* Registers changed in the basic block: */
143 bitmap_head changed_regs
;
144 /* Registers becoming dead in the BB. */
145 bitmap_head dead_regs
;
146 /* Cands present in the BB whose in/out regs are not changed after
147 the cands occurence and are not dead (except the reload
149 bitmap_head gen_cands
;
150 bitmap_head livein_cands
; /* cands whose inputs live at the BB start. */
151 bitmap_head pavin_cands
; /* cands partially available at BB entry. */
152 bitmap_head pavout_cands
; /* cands partially available at BB exit. */
153 bitmap_head avin_cands
; /* cands available at the entry of the BB. */
154 bitmap_head avout_cands
; /* cands available at the exit of the BB. */
157 /* Array for all BB data. Indexed by the corresponding BB index. */
158 typedef struct remat_bb_data
*remat_bb_data_t
;
160 /* Basic blocks for data flow problems -- all bocks except the special
162 static bitmap_head all_blocks
;
164 /* All basic block data are referred through the following array. */
165 static remat_bb_data_t remat_bb_data
;
167 /* Two small functions for access to the bb data. */
168 static inline remat_bb_data_t
169 get_remat_bb_data (basic_block bb
)
171 return &remat_bb_data
[(bb
)->index
];
174 static inline remat_bb_data_t
175 get_remat_bb_data_by_index (int index
)
177 return &remat_bb_data
[index
];
182 /* Recursive hash function for RTL X. */
195 val
+= (int) code
+ 4095;
197 /* Some RTL can be compared nonrecursively. */
201 return val
+ REGNO (x
);
204 return iterative_hash_object (XEXP (x
, 0), val
);
207 return iterative_hash_object (XSTR (x
, 0), val
);
219 /* Hash the elements. */
220 fmt
= GET_RTX_FORMAT (code
);
221 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
236 val
+= XVECLEN (x
, i
);
238 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
239 val
+= rtx_hash (XVECEXP (x
, i
, j
));
243 val
+= rtx_hash (XEXP (x
, i
));
248 val
+= htab_hash_string (XSTR (x
, i
));
256 /* It is believed that rtx's at this level will never
257 contain anything but integers and other rtx's, except for
258 within LABEL_REFs and SYMBOL_REFs. */
268 /* Hash table for the candidates. Different insns (e.g. structurally
269 the same insns or even insns with different unused output regs) can
270 be represented by the same candidate in the table. */
271 static htab_t cand_table
;
273 /* Hash function for candidate CAND. */
275 cand_hash (const void *cand
)
277 const_cand_t c
= (const_cand_t
) cand
;
278 lra_insn_recog_data_t id
= lra_get_insn_recog_data (c
->insn
);
279 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
280 int nops
= static_id
->n_operands
;
283 for (int i
= 0; i
< nops
; i
++)
285 hash
= iterative_hash_object (c
->regno
, hash
);
286 else if (static_id
->operand
[i
].type
== OP_IN
)
287 hash
= iterative_hash_object (*id
->operand_loc
[i
], hash
);
291 /* Equal function for candidates CAND1 and CAND2. They are equal if
292 the corresponding candidate insns have the same code, the same
293 regno for rematerialization, the same input operands. */
295 cand_eq_p (const void *cand1
, const void *cand2
)
297 const_cand_t c1
= (const_cand_t
) cand1
;
298 const_cand_t c2
= (const_cand_t
) cand2
;
299 lra_insn_recog_data_t id1
= lra_get_insn_recog_data (c1
->insn
);
300 lra_insn_recog_data_t id2
= lra_get_insn_recog_data (c2
->insn
);
301 struct lra_static_insn_data
*static_id1
= id1
->insn_static_data
;
302 int nops
= static_id1
->n_operands
;
304 if (c1
->regno
!= c2
->regno
305 || INSN_CODE (c1
->insn
) < 0
306 || INSN_CODE (c1
->insn
) != INSN_CODE (c2
->insn
))
308 gcc_assert (c1
->nop
== c2
->nop
);
309 for (int i
= 0; i
< nops
; i
++)
310 if (i
!= c1
->nop
&& static_id1
->operand
[i
].type
== OP_IN
311 && *id1
->operand_loc
[i
] != *id2
->operand_loc
[i
])
316 /* Insert candidate CAND into the table if it is not there yet.
317 Return candidate which is in the table. */
319 insert_cand (cand_t cand
)
323 entry_ptr
= htab_find_slot (cand_table
, cand
, INSERT
);
324 if (*entry_ptr
== NULL
)
325 *entry_ptr
= (void *) cand
;
326 return (cand_t
) *entry_ptr
;
329 /* Free candidate CAND memory. */
331 free_cand (void *cand
)
336 /* Initiate the candidate table. */
338 initiate_cand_table (void)
340 cand_table
= htab_create (8000, cand_hash
, cand_eq_p
,
341 (htab_del
) free_cand
);
344 /* Finish the candidate table. */
346 finish_cand_table (void)
348 htab_delete (cand_table
);
353 /* Return true if X contains memory or UNSPEC. We can not just check
354 insn operands as memory or unspec might be not an operand itself
355 but contain an operand. Insn with memory access is not profitable
356 for rematerialization. Rematerialization of UNSPEC might result in
357 wrong code generation as the UNPEC effect is unknown
358 (e.g. generating a label). */
360 bad_for_rematerialization_p (rtx x
)
366 if (MEM_P (x
) || GET_CODE (x
) == UNSPEC
)
369 fmt
= GET_RTX_FORMAT (code
);
370 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
374 if (bad_for_rematerialization_p (XEXP (x
, i
)))
377 else if (fmt
[i
] == 'E')
379 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
380 if (bad_for_rematerialization_p (XVECEXP (x
, i
, j
)))
387 /* If INSN can not be used for rematerialization, return negative
388 value. If INSN can be considered as a candidate for
389 rematerialization, return value which is the operand number of the
390 pseudo for which the insn can be used for rematerialization. Here
391 we consider the insns without any memory, spilled pseudo (except
392 for the rematerialization pseudo), or dying or unused regs. */
394 operand_to_remat (rtx_insn
*insn
)
396 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
397 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
398 struct lra_insn_reg
*reg
, *found_reg
= NULL
;
400 /* First find a pseudo which can be rematerialized. */
401 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
402 if (reg
->type
== OP_OUT
&& ! reg
->subreg_p
403 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
405 /* We permits only one spilled reg. */
406 if (found_reg
!= NULL
)
410 if (found_reg
== NULL
)
412 if (found_reg
->regno
< FIRST_PSEUDO_REGISTER
)
414 if (bad_for_rematerialization_p (PATTERN (insn
)))
416 /* Check the other regs are not spilled. */
417 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
418 if (found_reg
== reg
)
420 else if (reg
->type
== OP_INOUT
)
422 else if (reg
->regno
>= FIRST_PSEUDO_REGISTER
423 && reg_renumber
[reg
->regno
] < 0)
424 /* Another spilled reg. */
426 else if (reg
->type
== OP_IN
)
428 if (find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
429 /* We don't want to make live ranges longer. */
431 /* Check that there is no output reg as the input one. */
432 for (struct lra_insn_reg
*reg2
= id
->regs
;
435 if (reg2
->type
== OP_OUT
&& reg
->regno
== reg2
->regno
)
438 /* Find the rematerialization operand. */
439 int nop
= static_id
->n_operands
;
440 for (int i
= 0; i
< nop
; i
++)
441 if (REG_P (*id
->operand_loc
[i
])
442 && (int) REGNO (*id
->operand_loc
[i
]) == found_reg
->regno
)
447 /* Create candidate for INSN with rematerialization operand NOP and
448 REGNO. Insert the candidate into the table and set up the
449 corresponding INSN_TO_CAND element. */
451 create_cand (rtx_insn
*insn
, int nop
, int regno
)
453 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
454 rtx reg
= *id
->operand_loc
[nop
];
455 gcc_assert (REG_P (reg
));
456 int op_regno
= REGNO (reg
);
457 gcc_assert (op_regno
>= FIRST_PSEUDO_REGISTER
);
458 cand_t cand
= XNEW (struct cand
);
462 cand
->reload_regno
= op_regno
== regno
? -1 : op_regno
;
463 gcc_assert (cand
->regno
>= 0);
464 cand_t cand_in_table
= insert_cand (cand
);
465 insn_to_cand
[INSN_UID (insn
)] = cand_in_table
;
466 if (cand
!= cand_in_table
)
471 cand
->index
= all_cands
.length ();
472 all_cands
.safe_push (cand
);
473 cand
->next_regno_cand
= regno_cands
[cand
->regno
];
474 regno_cands
[cand
->regno
] = cand
;
478 /* Create rematerialization candidates (inserting them into the
484 struct potential_cand
489 struct potential_cand
*regno_potential_cand
;
491 /* Create candidates. */
492 regno_potential_cand
= XCNEWVEC (struct potential_cand
, max_reg_num ());
493 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
497 int src_regno
, dst_regno
;
499 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
500 int nop
= operand_to_remat (insn
);
503 if ((set
= single_set (insn
)) != NULL
504 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
))
505 && (src_regno
= REGNO (SET_SRC (set
))) >= FIRST_PSEUDO_REGISTER
506 && (dst_regno
= REGNO (SET_DEST (set
))) >= FIRST_PSEUDO_REGISTER
507 && reg_renumber
[dst_regno
] < 0
508 && (insn2
= regno_potential_cand
[src_regno
].insn
) != NULL
509 && BLOCK_FOR_INSN (insn2
) == BLOCK_FOR_INSN (insn
))
510 create_cand (insn2
, regno_potential_cand
[src_regno
].nop
, dst_regno
);
513 gcc_assert (REG_P (*id
->operand_loc
[nop
]));
514 regno
= REGNO (*id
->operand_loc
[nop
]);
515 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
516 if (reg_renumber
[regno
] < 0)
517 create_cand (insn
, nop
, regno
);
520 regno_potential_cand
[regno
].insn
= insn
;
521 regno_potential_cand
[regno
].nop
= nop
;
526 for (struct lra_insn_reg
*reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
527 if (reg
->type
!= OP_IN
&& reg
->regno
!= regno
528 && reg
->regno
>= FIRST_PSEUDO_REGISTER
)
529 regno_potential_cand
[reg
->regno
].insn
= NULL
;
531 cands_num
= all_cands
.length ();
532 free (regno_potential_cand
);
537 /* Create and initialize BB data. */
539 create_remat_bb_data (void)
542 remat_bb_data_t bb_info
;
544 remat_bb_data
= XNEWVEC (struct remat_bb_data
,
545 last_basic_block_for_fn (cfun
));
546 FOR_ALL_BB_FN (bb
, cfun
)
548 #ifdef ENABLE_CHECKING
549 if (bb
->index
< 0 || bb
->index
>= last_basic_block_for_fn (cfun
))
552 bb_info
= get_remat_bb_data (bb
);
554 bitmap_initialize (&bb_info
->changed_regs
, ®_obstack
);
555 bitmap_initialize (&bb_info
->dead_regs
, ®_obstack
);
556 bitmap_initialize (&bb_info
->gen_cands
, ®_obstack
);
557 bitmap_initialize (&bb_info
->livein_cands
, ®_obstack
);
558 bitmap_initialize (&bb_info
->pavin_cands
, ®_obstack
);
559 bitmap_initialize (&bb_info
->pavout_cands
, ®_obstack
);
560 bitmap_initialize (&bb_info
->avin_cands
, ®_obstack
);
561 bitmap_initialize (&bb_info
->avout_cands
, ®_obstack
);
565 /* Dump all candidates to DUMP_FILE. */
567 dump_cands (FILE *dump_file
)
572 fprintf (dump_file
, "\nCands:\n");
573 for (i
= 0; i
< (int) cands_num
; i
++)
576 fprintf (dump_file
, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
577 i
, cand
->nop
, cand
->regno
, cand
->reload_regno
);
578 print_inline_rtx (dump_file
, cand
->insn
, 6);
579 fprintf (dump_file
, "\n");
583 /* Dump all candidates and BB data. */
585 dump_candidates_and_remat_bb_data (void)
589 if (lra_dump_file
== NULL
)
591 dump_cands (lra_dump_file
);
592 FOR_EACH_BB_FN (bb
, cfun
)
594 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
596 fprintf (lra_dump_file
, " register live in:");
597 dump_regset (df_get_live_in (bb
), lra_dump_file
);
598 putc ('\n', lra_dump_file
);
600 fprintf (lra_dump_file
, " register live out:");
601 dump_regset (df_get_live_out (bb
), lra_dump_file
);
602 putc ('\n', lra_dump_file
);
603 /* Changed/dead regs: */
604 fprintf (lra_dump_file
, " changed regs:");
605 dump_regset (&get_remat_bb_data (bb
)->changed_regs
, lra_dump_file
);
606 putc ('\n', lra_dump_file
);
607 fprintf (lra_dump_file
, " dead regs:");
608 dump_regset (&get_remat_bb_data (bb
)->dead_regs
, lra_dump_file
);
609 putc ('\n', lra_dump_file
);
610 lra_dump_bitmap_with_title ("cands generated in BB",
611 &get_remat_bb_data (bb
)->gen_cands
, bb
->index
);
612 lra_dump_bitmap_with_title ("livein cands in BB",
613 &get_remat_bb_data (bb
)->livein_cands
, bb
->index
);
614 lra_dump_bitmap_with_title ("pavin cands in BB",
615 &get_remat_bb_data (bb
)->pavin_cands
, bb
->index
);
616 lra_dump_bitmap_with_title ("pavout cands in BB",
617 &get_remat_bb_data (bb
)->pavout_cands
, bb
->index
);
618 lra_dump_bitmap_with_title ("avin cands in BB",
619 &get_remat_bb_data (bb
)->avin_cands
, bb
->index
);
620 lra_dump_bitmap_with_title ("avout cands in BB",
621 &get_remat_bb_data (bb
)->avout_cands
, bb
->index
);
625 /* Free all BB data. */
627 finish_remat_bb_data (void)
631 FOR_EACH_BB_FN (bb
, cfun
)
633 bitmap_clear (&get_remat_bb_data (bb
)->avout_cands
);
634 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
635 bitmap_clear (&get_remat_bb_data (bb
)->pavout_cands
);
636 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
637 bitmap_clear (&get_remat_bb_data (bb
)->livein_cands
);
638 bitmap_clear (&get_remat_bb_data (bb
)->gen_cands
);
639 bitmap_clear (&get_remat_bb_data (bb
)->dead_regs
);
640 bitmap_clear (&get_remat_bb_data (bb
)->changed_regs
);
642 free (remat_bb_data
);
647 /* Update changed_regs and dead_regs of BB from INSN. */
649 set_bb_regs (basic_block bb
, rtx_insn
*insn
)
651 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
652 struct lra_insn_reg
*reg
;
654 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
655 if (reg
->type
!= OP_IN
)
656 bitmap_set_bit (&get_remat_bb_data (bb
)->changed_regs
, reg
->regno
);
659 if (find_regno_note (insn
, REG_DEAD
, (unsigned) reg
->regno
) != NULL
)
660 bitmap_set_bit (&get_remat_bb_data (bb
)->dead_regs
, reg
->regno
);
663 for (int i
= 0; i
< call_used_regs_arr_len
; i
++)
664 bitmap_set_bit (&get_remat_bb_data (bb
)->dead_regs
,
665 call_used_regs_arr
[i
]);
668 /* Calculate changed_regs and dead_regs for each BB. */
670 calculate_local_reg_remat_bb_data (void)
675 FOR_EACH_BB_FN (bb
, cfun
)
676 FOR_BB_INSNS (bb
, insn
)
678 set_bb_regs (bb
, insn
);
683 /* Return true if REGNO is an input operand of INSN. */
685 input_regno_present_p (rtx_insn
*insn
, int regno
)
687 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
688 struct lra_insn_reg
*reg
;
690 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
691 if (reg
->type
== OP_IN
&& reg
->regno
== regno
)
696 /* Return true if a call used register is an input operand of INSN. */
698 call_used_input_regno_present_p (rtx_insn
*insn
)
700 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
701 struct lra_insn_reg
*reg
;
703 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
704 if (reg
->type
== OP_IN
&& reg
->regno
<= FIRST_PSEUDO_REGISTER
705 && TEST_HARD_REG_BIT (call_used_reg_set
, reg
->regno
))
710 /* Calculate livein_cands for each BB. */
712 calculate_livein_cands (void)
716 FOR_EACH_BB_FN (bb
, cfun
)
718 bitmap livein_regs
= df_get_live_in (bb
);
719 bitmap livein_cands
= &get_remat_bb_data (bb
)->livein_cands
;
720 for (unsigned int i
= 0; i
< cands_num
; i
++)
722 cand_t cand
= all_cands
[i
];
723 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
724 struct lra_insn_reg
*reg
;
726 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
727 if (reg
->type
== OP_IN
&& ! bitmap_bit_p (livein_regs
, reg
->regno
))
730 bitmap_set_bit (livein_cands
, i
);
735 /* Calculate gen_cands for each BB. */
737 calculate_gen_cands (void)
741 bitmap_head gen_insns
;
744 bitmap_initialize (&gen_insns
, ®_obstack
);
745 FOR_EACH_BB_FN (bb
, cfun
)
747 gen_cands
= &get_remat_bb_data (bb
)->gen_cands
;
748 bitmap_clear (&gen_insns
);
749 FOR_BB_INSNS (bb
, insn
)
752 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
753 struct lra_insn_reg
*reg
;
758 int src_regno
= -1, dst_regno
= -1;
760 if ((set
= single_set (insn
)) != NULL
761 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
763 src_regno
= REGNO (SET_SRC (set
));
764 dst_regno
= REGNO (SET_DEST (set
));
767 /* Update gen_cands: */
768 bitmap_clear (&temp_bitmap
);
769 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
770 if (reg
->type
!= OP_IN
771 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
772 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
774 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
776 cand
= insn_to_cand
[INSN_UID (insn2
)];
777 gcc_assert (cand
!= NULL
);
778 /* Ignore the reload insn. */
779 if (src_regno
== cand
->reload_regno
780 && dst_regno
== cand
->regno
)
782 if (cand
->regno
== reg
->regno
783 || input_regno_present_p (insn2
, reg
->regno
))
785 bitmap_clear_bit (gen_cands
, cand
->index
);
786 bitmap_set_bit (&temp_bitmap
, uid
);
791 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
793 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
795 cand
= insn_to_cand
[INSN_UID (insn2
)];
796 gcc_assert (cand
!= NULL
);
797 if (call_used_input_regno_present_p (insn2
))
799 bitmap_clear_bit (gen_cands
, cand
->index
);
800 bitmap_set_bit (&temp_bitmap
, uid
);
803 bitmap_and_compl_into (&gen_insns
, &temp_bitmap
);
805 cand
= insn_to_cand
[INSN_UID (insn
)];
808 bitmap_set_bit (gen_cands
, cand
->index
);
809 bitmap_set_bit (&gen_insns
, INSN_UID (insn
));
813 bitmap_clear (&gen_insns
);
818 /* The common transfer function used by the DF equation solver to
819 propagate (partial) availability info BB_IN to BB_OUT through block
820 with BB_INDEX according to the following equation:
822 bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
825 cand_trans_fun (int bb_index
, bitmap bb_in
, bitmap bb_out
)
827 remat_bb_data_t bb_info
;
828 bitmap bb_livein
, bb_changed_regs
, bb_dead_regs
;
832 bb_info
= get_remat_bb_data_by_index (bb_index
);
833 bb_livein
= &bb_info
->livein_cands
;
834 bb_changed_regs
= &bb_info
->changed_regs
;
835 bb_dead_regs
= &bb_info
->dead_regs
;
836 /* Calculate killed avin cands -- cands whose regs are changed or
837 becoming dead in the BB. We calculate it here as we hope that
838 repeated calculations are compensated by smaller size of BB_IN in
839 comparison with all candidates number. */
840 bitmap_clear (&temp_bitmap
);
841 EXECUTE_IF_SET_IN_BITMAP (bb_in
, 0, cid
, bi
)
843 cand_t cand
= all_cands
[cid
];
844 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
845 struct lra_insn_reg
*reg
;
847 if (! bitmap_bit_p (bb_livein
, cid
))
849 bitmap_set_bit (&temp_bitmap
, cid
);
852 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
853 /* Ignore all outputs which are not the regno for
854 rematerialization. */
855 if (reg
->type
== OP_OUT
&& reg
->regno
!= cand
->regno
)
857 else if (bitmap_bit_p (bb_changed_regs
, reg
->regno
)
858 || bitmap_bit_p (bb_dead_regs
, reg
->regno
))
860 bitmap_set_bit (&temp_bitmap
, cid
);
863 /* Check regno for rematerialization. */
864 if (bitmap_bit_p (bb_changed_regs
, cand
->regno
)
865 || bitmap_bit_p (bb_dead_regs
, cand
->regno
))
866 bitmap_set_bit (&temp_bitmap
, cid
);
868 return bitmap_ior_and_compl (bb_out
,
869 &bb_info
->gen_cands
, bb_in
, &temp_bitmap
);
874 /* The transfer function used by the DF equation solver to propagate
875 partial candidate availability info through block with BB_INDEX
876 according to the following equation:
878 bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
881 cand_pav_trans_fun (int bb_index
)
883 remat_bb_data_t bb_info
;
885 bb_info
= get_remat_bb_data_by_index (bb_index
);
886 return cand_trans_fun (bb_index
, &bb_info
->pavin_cands
,
887 &bb_info
->pavout_cands
);
890 /* The confluence function used by the DF equation solver to set up
891 cand_pav info for a block BB without predecessor. */
893 cand_pav_con_fun_0 (basic_block bb
)
895 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
898 /* The confluence function used by the DF equation solver to propagate
899 partial candidate availability info from predecessor to successor
900 on edge E (pred->bb) according to the following equation:
902 bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
905 cand_pav_con_fun_n (edge e
)
907 basic_block pred
= e
->src
;
908 basic_block bb
= e
->dest
;
909 remat_bb_data_t bb_info
;
910 bitmap bb_pavin
, pred_pavout
;
912 bb_info
= get_remat_bb_data (bb
);
913 bb_pavin
= &bb_info
->pavin_cands
;
914 pred_pavout
= &get_remat_bb_data (pred
)->pavout_cands
;
915 return bitmap_ior_into (bb_pavin
, pred_pavout
);
920 /* The transfer function used by the DF equation solver to propagate
921 candidate availability info through block with BB_INDEX according
922 to the following equation:
924 bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
927 cand_av_trans_fun (int bb_index
)
929 remat_bb_data_t bb_info
;
931 bb_info
= get_remat_bb_data_by_index (bb_index
);
932 return cand_trans_fun (bb_index
, &bb_info
->avin_cands
,
933 &bb_info
->avout_cands
);
936 /* The confluence function used by the DF equation solver to set up
937 cand_av info for a block BB without predecessor. */
939 cand_av_con_fun_0 (basic_block bb
)
941 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
944 /* The confluence function used by the DF equation solver to propagate
945 cand_av info from predecessor to successor on edge E (pred->bb)
946 according to the following equation:
948 bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
951 cand_av_con_fun_n (edge e
)
953 basic_block pred
= e
->src
;
954 basic_block bb
= e
->dest
;
955 remat_bb_data_t bb_info
;
956 bitmap bb_avin
, pred_avout
;
958 bb_info
= get_remat_bb_data (bb
);
959 bb_avin
= &bb_info
->avin_cands
;
960 pred_avout
= &get_remat_bb_data (pred
)->avout_cands
;
961 return bitmap_and_into (bb_avin
, pred_avout
);
964 /* Calculate available candidates for each BB. */
966 calculate_global_remat_bb_data (void)
971 (DF_FORWARD
, NULL
, cand_pav_con_fun_0
, cand_pav_con_fun_n
,
972 cand_pav_trans_fun
, &all_blocks
,
973 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
974 /* Initialize avin by pavin. */
975 FOR_EACH_BB_FN (bb
, cfun
)
976 bitmap_copy (&get_remat_bb_data (bb
)->avin_cands
,
977 &get_remat_bb_data (bb
)->pavin_cands
);
979 (DF_FORWARD
, NULL
, cand_av_con_fun_0
, cand_av_con_fun_n
,
980 cand_av_trans_fun
, &all_blocks
,
981 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
986 /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
988 change_sp_offset (rtx_insn
*insns
, HOST_WIDE_INT sp_offset
)
990 for (rtx_insn
*insn
= insns
; insn
!= NULL
; insn
= NEXT_INSN (insn
))
991 eliminate_regs_in_insn (insn
, false, false, sp_offset
);
994 /* Return start hard register of REG (can be a hard or a pseudo reg)
995 or -1 (if it is a spilled pseudo). Return number of hard registers
996 occupied by REG through parameter NREGS if the start hard reg is
999 get_hard_regs (struct lra_insn_reg
*reg
, int &nregs
)
1001 int regno
= reg
->regno
;
1002 int hard_regno
= regno
< FIRST_PSEUDO_REGISTER
? regno
: reg_renumber
[regno
];
1004 if (hard_regno
>= 0)
1005 nregs
= hard_regno_nregs
[hard_regno
][reg
->biggest_mode
];
1009 /* Insert rematerialization insns using the data-flow data calculated
1016 bitmap_head avail_cands
;
1017 bool changed_p
= false;
1018 /* Living hard regs and hard registers of living pseudos. */
1019 HARD_REG_SET live_hard_regs
;
1021 bitmap_initialize (&avail_cands
, ®_obstack
);
1022 FOR_EACH_BB_FN (bb
, cfun
)
1024 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_out (bb
));
1025 bitmap_and (&avail_cands
, &get_remat_bb_data (bb
)->avin_cands
,
1026 &get_remat_bb_data (bb
)->livein_cands
);
1027 FOR_BB_INSNS (bb
, insn
)
1029 if (!NONDEBUG_INSN_P (insn
))
1032 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
1033 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1034 struct lra_insn_reg
*reg
;
1039 int src_regno
= -1, dst_regno
= -1;
1041 if ((set
= single_set (insn
)) != NULL
1042 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
1044 src_regno
= REGNO (SET_SRC (set
));
1045 dst_regno
= REGNO (SET_DEST (set
));
1049 /* Check possibility of rematerialization (hard reg or
1050 unpsilled pseudo <- spilled pseudo): */
1051 if (dst_regno
>= 0 && src_regno
>= FIRST_PSEUDO_REGISTER
1052 && reg_renumber
[src_regno
] < 0
1053 && (dst_regno
< FIRST_PSEUDO_REGISTER
1054 || reg_renumber
[dst_regno
] >= 0))
1056 for (cand
= regno_cands
[src_regno
];
1058 cand
= cand
->next_regno_cand
)
1059 if (bitmap_bit_p (&avail_cands
, cand
->index
))
1062 int i
, hard_regno
, nregs
;
1063 rtx_insn
*remat_insn
= NULL
;
1064 HOST_WIDE_INT cand_sp_offset
= 0;
1067 lra_insn_recog_data_t cand_id
1068 = lra_get_insn_recog_data (cand
->insn
);
1069 struct lra_static_insn_data
*static_cand_id
1070 = cand_id
->insn_static_data
;
1071 rtx saved_op
= *cand_id
->operand_loc
[cand
->nop
];
1073 /* Check clobbers do not kill something living. */
1074 gcc_assert (REG_P (saved_op
));
1075 int ignore_regno
= REGNO (saved_op
);
1077 for (reg
= cand_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1078 if (reg
->type
!= OP_IN
&& reg
->regno
!= ignore_regno
)
1080 hard_regno
= get_hard_regs (reg
, nregs
);
1081 gcc_assert (hard_regno
>= 0);
1082 for (i
= 0; i
< nregs
; i
++)
1083 if (TEST_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
))
1091 for (reg
= static_cand_id
->hard_regs
;
1094 if (reg
->type
!= OP_IN
1095 && TEST_HARD_REG_BIT (live_hard_regs
, reg
->regno
))
1101 *cand_id
->operand_loc
[cand
->nop
] = SET_DEST (set
);
1102 lra_update_insn_regno_info (cand
->insn
);
1103 bool ok_p
= lra_constrain_insn (cand
->insn
);
1106 rtx remat_pat
= copy_insn (PATTERN (cand
->insn
));
1109 emit_insn (remat_pat
);
1110 remat_insn
= get_insns ();
1112 if (recog_memoized (remat_insn
) < 0)
1114 cand_sp_offset
= cand_id
->sp_offset
;
1116 *cand_id
->operand_loc
[cand
->nop
] = saved_op
;
1117 lra_update_insn_regno_info (cand
->insn
);
1121 bitmap_clear (&temp_bitmap
);
1122 /* Update avail_cands (see analogous code for
1123 calculate_gen_cands). */
1124 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1125 if (reg
->type
!= OP_IN
1126 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1127 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1129 cand
= all_cands
[cid
];
1131 /* Ignore the reload insn. */
1132 if (src_regno
== cand
->reload_regno
1133 && dst_regno
== cand
->regno
)
1135 if (cand
->regno
== reg
->regno
1136 || input_regno_present_p (cand
->insn
, reg
->regno
))
1137 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1141 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1143 cand
= all_cands
[cid
];
1145 if (call_used_input_regno_present_p (cand
->insn
))
1146 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1149 bitmap_and_compl_into (&avail_cands
, &temp_bitmap
);
1150 if ((cand
= insn_to_cand
[INSN_UID (insn
)]) != NULL
)
1151 bitmap_set_bit (&avail_cands
, cand
->index
);
1153 if (remat_insn
!= NULL
)
1155 HOST_WIDE_INT sp_offset_change
= cand_sp_offset
- id
->sp_offset
;
1156 if (sp_offset_change
!= 0)
1157 change_sp_offset (remat_insn
, sp_offset_change
);
1158 lra_process_new_insns (insn
, remat_insn
, NULL
,
1159 "Inserting rematerialization insn");
1160 lra_set_insn_deleted (insn
);
1165 /* Update live hard regs: */
1166 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1167 if (reg
->type
== OP_IN
1168 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1170 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1172 for (i
= 0; i
< nregs
; i
++)
1173 CLEAR_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1175 else if (reg
->type
!= OP_IN
1176 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1178 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1180 for (i
= 0; i
< nregs
; i
++)
1181 SET_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1183 /* Process also hard regs (e.g. CC register) which are part
1184 of insn definition. */
1185 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1186 if (reg
->type
== OP_IN
1187 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1188 CLEAR_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1189 else if (reg
->type
!= OP_IN
1190 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1191 SET_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1194 bitmap_clear (&avail_cands
);
1200 /* Entry point of the rematerialization sub-pass. Return true if we
1201 did any rematerialization. */
1207 int max_regno
= max_reg_num ();
1209 if (! flag_lra_remat
)
1211 timevar_push (TV_LRA_REMAT
);
1212 insn_to_cand
= XCNEWVEC (cand_t
, get_max_uid ());
1213 regno_cands
= XCNEWVEC (cand_t
, max_regno
);
1214 all_cands
.create (8000);
1215 call_used_regs_arr_len
= 0;
1216 for (int i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1217 if (call_used_regs
[i
])
1218 call_used_regs_arr
[call_used_regs_arr_len
++] = i
;
1219 initiate_cand_table ();
1221 create_remat_bb_data ();
1222 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1223 calculate_local_reg_remat_bb_data ();
1224 calculate_livein_cands ();
1225 calculate_gen_cands ();
1226 bitmap_initialize (&all_blocks
, ®_obstack
);
1227 FOR_ALL_BB_FN (bb
, cfun
)
1228 bitmap_set_bit (&all_blocks
, bb
->index
);
1229 calculate_global_remat_bb_data ();
1230 dump_candidates_and_remat_bb_data ();
1231 result
= do_remat ();
1232 all_cands
.release ();
1233 bitmap_clear (&temp_bitmap
);
1234 finish_remat_bb_data ();
1235 finish_cand_table ();
1236 bitmap_clear (&all_blocks
);
1238 free (insn_to_cand
);
1239 timevar_pop (TV_LRA_REMAT
);