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
);
864 return bitmap_ior_and_compl (bb_out
,
865 &bb_info
->gen_cands
, bb_in
, &temp_bitmap
);
870 /* The transfer function used by the DF equation solver to propagate
871 partial candidate availability info through block with BB_INDEX
872 according to the following equation:
874 bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
877 cand_pav_trans_fun (int bb_index
)
879 remat_bb_data_t bb_info
;
881 bb_info
= get_remat_bb_data_by_index (bb_index
);
882 return cand_trans_fun (bb_index
, &bb_info
->pavin_cands
,
883 &bb_info
->pavout_cands
);
886 /* The confluence function used by the DF equation solver to set up
887 cand_pav info for a block BB without predecessor. */
889 cand_pav_con_fun_0 (basic_block bb
)
891 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
894 /* The confluence function used by the DF equation solver to propagate
895 partial candidate availability info from predecessor to successor
896 on edge E (pred->bb) according to the following equation:
898 bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
901 cand_pav_con_fun_n (edge e
)
903 basic_block pred
= e
->src
;
904 basic_block bb
= e
->dest
;
905 remat_bb_data_t bb_info
;
906 bitmap bb_pavin
, pred_pavout
;
908 bb_info
= get_remat_bb_data (bb
);
909 bb_pavin
= &bb_info
->pavin_cands
;
910 pred_pavout
= &get_remat_bb_data (pred
)->pavout_cands
;
911 return bitmap_ior_into (bb_pavin
, pred_pavout
);
916 /* The transfer function used by the DF equation solver to propagate
917 candidate availability info through block with BB_INDEX according
918 to the following equation:
920 bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
923 cand_av_trans_fun (int bb_index
)
925 remat_bb_data_t bb_info
;
927 bb_info
= get_remat_bb_data_by_index (bb_index
);
928 return cand_trans_fun (bb_index
, &bb_info
->avin_cands
,
929 &bb_info
->avout_cands
);
932 /* The confluence function used by the DF equation solver to set up
933 cand_av info for a block BB without predecessor. */
935 cand_av_con_fun_0 (basic_block bb
)
937 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
940 /* The confluence function used by the DF equation solver to propagate
941 cand_av info from predecessor to successor on edge E (pred->bb)
942 according to the following equation:
944 bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
947 cand_av_con_fun_n (edge e
)
949 basic_block pred
= e
->src
;
950 basic_block bb
= e
->dest
;
951 remat_bb_data_t bb_info
;
952 bitmap bb_avin
, pred_avout
;
954 bb_info
= get_remat_bb_data (bb
);
955 bb_avin
= &bb_info
->avin_cands
;
956 pred_avout
= &get_remat_bb_data (pred
)->avout_cands
;
957 return bitmap_and_into (bb_avin
, pred_avout
);
960 /* Calculate available candidates for each BB. */
962 calculate_global_remat_bb_data (void)
967 (DF_FORWARD
, NULL
, cand_pav_con_fun_0
, cand_pav_con_fun_n
,
968 cand_pav_trans_fun
, &all_blocks
,
969 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
970 /* Initialize avin by pavin. */
971 FOR_EACH_BB_FN (bb
, cfun
)
972 bitmap_copy (&get_remat_bb_data (bb
)->avin_cands
,
973 &get_remat_bb_data (bb
)->pavin_cands
);
975 (DF_FORWARD
, NULL
, cand_av_con_fun_0
, cand_av_con_fun_n
,
976 cand_av_trans_fun
, &all_blocks
,
977 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
982 /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
984 change_sp_offset (rtx_insn
*insns
, HOST_WIDE_INT sp_offset
)
986 for (rtx_insn
*insn
= insns
; insn
!= NULL
; insn
= NEXT_INSN (insn
))
987 eliminate_regs_in_insn (insn
, false, false, sp_offset
);
990 /* Return start hard register of REG (can be a hard or a pseudo reg)
991 or -1 (if it is a spilled pseudo). Return number of hard registers
992 occupied by REG through parameter NREGS if the start hard reg is
995 get_hard_regs (struct lra_insn_reg
*reg
, int &nregs
)
997 int regno
= reg
->regno
;
998 int hard_regno
= regno
< FIRST_PSEUDO_REGISTER
? regno
: reg_renumber
[regno
];
1000 if (hard_regno
>= 0)
1001 nregs
= hard_regno_nregs
[hard_regno
][reg
->biggest_mode
];
1005 /* Insert rematerialization insns using the data-flow data calculated
1012 bitmap_head avail_cands
;
1013 bool changed_p
= false;
1014 /* Living hard regs and hard registers of living pseudos. */
1015 HARD_REG_SET live_hard_regs
;
1017 bitmap_initialize (&avail_cands
, ®_obstack
);
1018 FOR_EACH_BB_FN (bb
, cfun
)
1020 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_out (bb
));
1021 bitmap_and (&avail_cands
, &get_remat_bb_data (bb
)->avin_cands
,
1022 &get_remat_bb_data (bb
)->livein_cands
);
1023 FOR_BB_INSNS (bb
, insn
)
1025 if (!NONDEBUG_INSN_P (insn
))
1028 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
1029 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1030 struct lra_insn_reg
*reg
;
1035 int src_regno
= -1, dst_regno
= -1;
1037 if ((set
= single_set (insn
)) != NULL
1038 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
1040 src_regno
= REGNO (SET_SRC (set
));
1041 dst_regno
= REGNO (SET_DEST (set
));
1045 /* Check possibility of rematerialization (hard reg or
1046 unpsilled pseudo <- spilled pseudo): */
1047 if (dst_regno
>= 0 && src_regno
>= FIRST_PSEUDO_REGISTER
1048 && reg_renumber
[src_regno
] < 0
1049 && (dst_regno
< FIRST_PSEUDO_REGISTER
1050 || reg_renumber
[dst_regno
] >= 0))
1052 for (cand
= regno_cands
[src_regno
];
1054 cand
= cand
->next_regno_cand
)
1055 if (bitmap_bit_p (&avail_cands
, cand
->index
))
1058 int i
, hard_regno
, nregs
;
1059 rtx_insn
*remat_insn
= NULL
;
1060 HOST_WIDE_INT cand_sp_offset
= 0;
1063 lra_insn_recog_data_t cand_id
1064 = lra_get_insn_recog_data (cand
->insn
);
1065 struct lra_static_insn_data
*static_cand_id
1066 = cand_id
->insn_static_data
;
1067 rtx saved_op
= *cand_id
->operand_loc
[cand
->nop
];
1069 /* Check clobbers do not kill something living. */
1070 gcc_assert (REG_P (saved_op
));
1071 int ignore_regno
= REGNO (saved_op
);
1073 for (reg
= cand_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1074 if (reg
->type
!= OP_IN
&& reg
->regno
!= ignore_regno
)
1076 hard_regno
= get_hard_regs (reg
, nregs
);
1077 gcc_assert (hard_regno
>= 0);
1078 for (i
= 0; i
< nregs
; i
++)
1079 if (TEST_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
))
1087 for (reg
= static_cand_id
->hard_regs
;
1090 if (reg
->type
!= OP_IN
1091 && TEST_HARD_REG_BIT (live_hard_regs
, reg
->regno
))
1097 *cand_id
->operand_loc
[cand
->nop
] = SET_DEST (set
);
1098 lra_update_insn_regno_info (cand
->insn
);
1099 bool ok_p
= lra_constrain_insn (cand
->insn
);
1102 rtx remat_pat
= copy_insn (PATTERN (cand
->insn
));
1105 emit_insn (remat_pat
);
1106 remat_insn
= get_insns ();
1108 if (recog_memoized (remat_insn
) < 0)
1110 cand_sp_offset
= cand_id
->sp_offset
;
1112 *cand_id
->operand_loc
[cand
->nop
] = saved_op
;
1113 lra_update_insn_regno_info (cand
->insn
);
1117 bitmap_clear (&temp_bitmap
);
1118 /* Update avail_cands (see analogous code for
1119 calculate_gen_cands). */
1120 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1121 if (reg
->type
!= OP_IN
1122 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1123 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1125 cand
= all_cands
[cid
];
1127 /* Ignore the reload insn. */
1128 if (src_regno
== cand
->reload_regno
1129 && dst_regno
== cand
->regno
)
1131 if (cand
->regno
== reg
->regno
1132 || input_regno_present_p (cand
->insn
, reg
->regno
))
1133 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1137 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1139 cand
= all_cands
[cid
];
1141 if (call_used_input_regno_present_p (cand
->insn
))
1142 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1145 bitmap_and_compl_into (&avail_cands
, &temp_bitmap
);
1146 if ((cand
= insn_to_cand
[INSN_UID (insn
)]) != NULL
)
1147 bitmap_set_bit (&avail_cands
, cand
->index
);
1149 if (remat_insn
!= NULL
)
1151 HOST_WIDE_INT sp_offset_change
= cand_sp_offset
- id
->sp_offset
;
1152 if (sp_offset_change
!= 0)
1153 change_sp_offset (remat_insn
, sp_offset_change
);
1154 lra_process_new_insns (insn
, remat_insn
, NULL
,
1155 "Inserting rematerialization insn");
1156 lra_set_insn_deleted (insn
);
1161 /* Update live hard regs: */
1162 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1163 if (reg
->type
== OP_IN
1164 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1166 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1168 for (i
= 0; i
< nregs
; i
++)
1169 CLEAR_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1171 else if (reg
->type
!= OP_IN
1172 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1174 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1176 for (i
= 0; i
< nregs
; i
++)
1177 SET_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1179 /* Process also hard regs (e.g. CC register) which are part
1180 of insn definition. */
1181 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1182 if (reg
->type
== OP_IN
1183 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1184 CLEAR_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1185 else if (reg
->type
!= OP_IN
1186 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1187 SET_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1190 bitmap_clear (&avail_cands
);
1196 /* Entry point of the rematerialization sub-pass. Return true if we
1197 did any rematerialization. */
1203 int max_regno
= max_reg_num ();
1205 if (! flag_lra_remat
)
1207 timevar_push (TV_LRA_REMAT
);
1208 insn_to_cand
= XCNEWVEC (cand_t
, get_max_uid ());
1209 regno_cands
= XCNEWVEC (cand_t
, max_regno
);
1210 all_cands
.create (8000);
1211 call_used_regs_arr_len
= 0;
1212 for (int i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1213 if (call_used_regs
[i
])
1214 call_used_regs_arr
[call_used_regs_arr_len
++] = i
;
1215 initiate_cand_table ();
1217 create_remat_bb_data ();
1218 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1219 calculate_local_reg_remat_bb_data ();
1220 calculate_livein_cands ();
1221 calculate_gen_cands ();
1222 bitmap_initialize (&all_blocks
, ®_obstack
);
1223 FOR_ALL_BB_FN (bb
, cfun
)
1224 bitmap_set_bit (&all_blocks
, bb
->index
);
1225 calculate_global_remat_bb_data ();
1226 dump_candidates_and_remat_bb_data ();
1227 result
= do_remat ();
1228 all_cands
.release ();
1229 bitmap_clear (&temp_bitmap
);
1230 finish_remat_bb_data ();
1231 finish_cand_table ();
1232 bitmap_clear (&all_blocks
);
1234 free (insn_to_cand
);
1235 timevar_pop (TV_LRA_REMAT
);