1 /* Rematerialize pseudos values.
2 Copyright (C) 2014-2015 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"
82 #include "dominance.h"
84 #include "basic-block.h"
88 #include "sparseset.h"
92 /* Number of candidates for rematerialization. */
93 static unsigned int cands_num
;
95 /* The following is used for representation of call_used_reg_set in
96 form array whose elements are hard register numbers with nonzero bit
97 in CALL_USED_REG_SET. */
98 static int call_used_regs_arr_len
;
99 static int call_used_regs_arr
[FIRST_PSEUDO_REGISTER
];
101 /* Bitmap used for different calculations. */
102 static bitmap_head temp_bitmap
;
104 typedef struct cand
*cand_t
;
105 typedef const struct cand
*const_cand_t
;
107 /* Insn candidates for rematerialization. The candidate insn should
108 have the following properies:
109 o no any memory (as access to memory is non-profitable)
110 o no INOUT regs (it means no non-paradoxical subreg of output reg)
111 o one output spilled pseudo (or reload pseudo of a spilled pseudo)
112 o all other pseudos are with assigned hard regs. */
115 /* Index of the candidates in all_cands. */
117 /* The candidate insn. */
119 /* Insn pseudo regno for rematerialization. */
121 /* Non-negative if a reload pseudo is in the insn instead of the
122 pseudo for rematerialization. */
124 /* Number of the operand containing the regno or its reload
127 /* Next candidate for the same regno. */
128 cand_t next_regno_cand
;
131 /* Vector containing all candidates. */
132 static vec
<cand_t
> all_cands
;
133 /* Map: insn -> candidate representing it. It is null if the insn can
134 not be used for rematerialization. */
135 static cand_t
*insn_to_cand
;
137 /* Map regno -> candidates can be used for the regno
138 rematerialization. */
139 static cand_t
*regno_cands
;
141 /* Data about basic blocks used for the rematerialization
145 /* Basic block about which the below data are. */
147 /* Registers changed in the basic block: */
148 bitmap_head changed_regs
;
149 /* Registers becoming dead in the BB. */
150 bitmap_head dead_regs
;
151 /* Cands present in the BB whose in/out regs are not changed after
152 the cands occurence and are not dead (except the reload
154 bitmap_head gen_cands
;
155 bitmap_head livein_cands
; /* cands whose inputs live at the BB start. */
156 bitmap_head pavin_cands
; /* cands partially available at BB entry. */
157 bitmap_head pavout_cands
; /* cands partially available at BB exit. */
158 bitmap_head avin_cands
; /* cands available at the entry of the BB. */
159 bitmap_head avout_cands
; /* cands available at the exit of the BB. */
162 /* Array for all BB data. Indexed by the corresponding BB index. */
163 typedef struct remat_bb_data
*remat_bb_data_t
;
165 /* Basic blocks for data flow problems -- all bocks except the special
167 static bitmap_head all_blocks
;
169 /* All basic block data are referred through the following array. */
170 static remat_bb_data_t remat_bb_data
;
172 /* Two small functions for access to the bb data. */
173 static inline remat_bb_data_t
174 get_remat_bb_data (basic_block bb
)
176 return &remat_bb_data
[(bb
)->index
];
179 static inline remat_bb_data_t
180 get_remat_bb_data_by_index (int index
)
182 return &remat_bb_data
[index
];
187 /* Recursive hash function for RTL X. */
200 val
+= (int) code
+ 4095;
202 /* Some RTL can be compared nonrecursively. */
206 return val
+ REGNO (x
);
209 return iterative_hash_object (XEXP (x
, 0), val
);
212 return iterative_hash_object (XSTR (x
, 0), val
);
224 /* Hash the elements. */
225 fmt
= GET_RTX_FORMAT (code
);
226 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
241 val
+= XVECLEN (x
, i
);
243 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
244 val
+= rtx_hash (XVECEXP (x
, i
, j
));
248 val
+= rtx_hash (XEXP (x
, i
));
253 val
+= htab_hash_string (XSTR (x
, i
));
261 /* It is believed that rtx's at this level will never
262 contain anything but integers and other rtx's, except for
263 within LABEL_REFs and SYMBOL_REFs. */
273 /* Hash table for the candidates. Different insns (e.g. structurally
274 the same insns or even insns with different unused output regs) can
275 be represented by the same candidate in the table. */
276 static htab_t cand_table
;
278 /* Hash function for candidate CAND. */
280 cand_hash (const void *cand
)
282 const_cand_t c
= (const_cand_t
) cand
;
283 lra_insn_recog_data_t id
= lra_get_insn_recog_data (c
->insn
);
284 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
285 int nops
= static_id
->n_operands
;
288 for (int i
= 0; i
< nops
; i
++)
290 hash
= iterative_hash_object (c
->regno
, hash
);
291 else if (static_id
->operand
[i
].type
== OP_IN
)
292 hash
= iterative_hash_object (*id
->operand_loc
[i
], hash
);
296 /* Equal function for candidates CAND1 and CAND2. They are equal if
297 the corresponding candidate insns have the same code, the same
298 regno for rematerialization, the same input operands. */
300 cand_eq_p (const void *cand1
, const void *cand2
)
302 const_cand_t c1
= (const_cand_t
) cand1
;
303 const_cand_t c2
= (const_cand_t
) cand2
;
304 lra_insn_recog_data_t id1
= lra_get_insn_recog_data (c1
->insn
);
305 lra_insn_recog_data_t id2
= lra_get_insn_recog_data (c2
->insn
);
306 struct lra_static_insn_data
*static_id1
= id1
->insn_static_data
;
307 int nops
= static_id1
->n_operands
;
309 if (c1
->regno
!= c2
->regno
310 || INSN_CODE (c1
->insn
) < 0
311 || INSN_CODE (c1
->insn
) != INSN_CODE (c2
->insn
))
313 gcc_assert (c1
->nop
== c2
->nop
);
314 for (int i
= 0; i
< nops
; i
++)
315 if (i
!= c1
->nop
&& static_id1
->operand
[i
].type
== OP_IN
316 && *id1
->operand_loc
[i
] != *id2
->operand_loc
[i
])
321 /* Insert candidate CAND into the table if it is not there yet.
322 Return candidate which is in the table. */
324 insert_cand (cand_t cand
)
328 entry_ptr
= htab_find_slot (cand_table
, cand
, INSERT
);
329 if (*entry_ptr
== NULL
)
330 *entry_ptr
= (void *) cand
;
331 return (cand_t
) *entry_ptr
;
334 /* Free candidate CAND memory. */
336 free_cand (void *cand
)
341 /* Initiate the candidate table. */
343 initiate_cand_table (void)
345 cand_table
= htab_create (8000, cand_hash
, cand_eq_p
,
346 (htab_del
) free_cand
);
349 /* Finish the candidate table. */
351 finish_cand_table (void)
353 htab_delete (cand_table
);
358 /* Return true if X contains memory or some UNSPEC. We can not just
359 check insn operands as memory or unspec might be not an operand
360 itself but contain an operand. Insn with memory access is not
361 profitable for rematerialization. Rematerialization of UNSPEC
362 might result in wrong code generation as the UNPEC effect is
363 unknown (e.g. generating a label). */
365 bad_for_rematerialization_p (rtx x
)
371 if (MEM_P (x
) || GET_CODE (x
) == UNSPEC
|| GET_CODE (x
) == UNSPEC_VOLATILE
)
374 fmt
= GET_RTX_FORMAT (code
);
375 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
379 if (bad_for_rematerialization_p (XEXP (x
, i
)))
382 else if (fmt
[i
] == 'E')
384 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
385 if (bad_for_rematerialization_p (XVECEXP (x
, i
, j
)))
392 /* If INSN can not be used for rematerialization, return negative
393 value. If INSN can be considered as a candidate for
394 rematerialization, return value which is the operand number of the
395 pseudo for which the insn can be used for rematerialization. Here
396 we consider the insns without any memory, spilled pseudo (except
397 for the rematerialization pseudo), or dying or unused regs. */
399 operand_to_remat (rtx_insn
*insn
)
401 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
402 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
403 struct lra_insn_reg
*reg
, *found_reg
= NULL
;
405 /* Don't rematerialize insns which can change PC. */
406 if (JUMP_P (insn
) || CALL_P (insn
))
408 /* First find a pseudo which can be rematerialized. */
409 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
410 /* True FRAME_POINTER_NEEDED might be because we can not follow
411 changing sp offsets, e.g. alloca is used. If the insn contains
412 stack pointer in such case, we can not rematerialize it as we
413 can not know sp offset at a rematerialization place. */
414 if (reg
->regno
== STACK_POINTER_REGNUM
&& frame_pointer_needed
)
416 else if (reg
->type
== OP_OUT
&& ! reg
->subreg_p
417 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
419 /* We permits only one spilled reg. */
420 if (found_reg
!= NULL
)
424 if (found_reg
== NULL
)
426 if (found_reg
->regno
< FIRST_PSEUDO_REGISTER
)
428 if (bad_for_rematerialization_p (PATTERN (insn
)))
430 /* Check the other regs are not spilled. */
431 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
432 if (found_reg
== reg
)
434 else if (reg
->type
== OP_INOUT
)
436 else if (reg
->regno
>= FIRST_PSEUDO_REGISTER
437 && reg_renumber
[reg
->regno
] < 0)
438 /* Another spilled reg. */
440 else if (reg
->type
== OP_IN
)
442 if (find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
443 /* We don't want to make live ranges longer. */
445 /* Check that there is no output reg as the input one. */
446 for (struct lra_insn_reg
*reg2
= id
->regs
;
449 if (reg2
->type
== OP_OUT
&& reg
->regno
== reg2
->regno
)
451 if (reg
->regno
< FIRST_PSEUDO_REGISTER
)
452 for (struct lra_insn_reg
*reg2
= static_id
->hard_regs
;
455 if (reg2
->type
== OP_OUT
456 && reg
->regno
<= reg2
->regno
459 + hard_regno_nregs
[reg
->regno
][reg
->biggest_mode
])))
462 /* Find the rematerialization operand. */
463 int nop
= static_id
->n_operands
;
464 for (int i
= 0; i
< nop
; i
++)
465 if (REG_P (*id
->operand_loc
[i
])
466 && (int) REGNO (*id
->operand_loc
[i
]) == found_reg
->regno
)
471 /* Create candidate for INSN with rematerialization operand NOP and
472 REGNO. Insert the candidate into the table and set up the
473 corresponding INSN_TO_CAND element. */
475 create_cand (rtx_insn
*insn
, int nop
, int regno
)
477 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
478 rtx reg
= *id
->operand_loc
[nop
];
479 gcc_assert (REG_P (reg
));
480 int op_regno
= REGNO (reg
);
481 gcc_assert (op_regno
>= FIRST_PSEUDO_REGISTER
);
482 cand_t cand
= XNEW (struct cand
);
486 cand
->reload_regno
= op_regno
== regno
? -1 : op_regno
;
487 gcc_assert (cand
->regno
>= 0);
488 cand_t cand_in_table
= insert_cand (cand
);
489 insn_to_cand
[INSN_UID (insn
)] = cand_in_table
;
490 if (cand
!= cand_in_table
)
495 cand
->index
= all_cands
.length ();
496 all_cands
.safe_push (cand
);
497 cand
->next_regno_cand
= regno_cands
[cand
->regno
];
498 regno_cands
[cand
->regno
] = cand
;
502 /* Create rematerialization candidates (inserting them into the
508 struct potential_cand
513 struct potential_cand
*regno_potential_cand
;
515 /* Create candidates. */
516 regno_potential_cand
= XCNEWVEC (struct potential_cand
, max_reg_num ());
517 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
521 int src_regno
, dst_regno
;
523 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
524 int nop
= operand_to_remat (insn
);
527 if ((set
= single_set (insn
)) != NULL
528 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
))
529 && ((src_regno
= REGNO (SET_SRC (set
)))
530 >= lra_constraint_new_regno_start
)
531 && (dst_regno
= REGNO (SET_DEST (set
))) >= FIRST_PSEUDO_REGISTER
532 && reg_renumber
[dst_regno
] < 0
533 && (insn2
= regno_potential_cand
[src_regno
].insn
) != NULL
534 && BLOCK_FOR_INSN (insn2
) == BLOCK_FOR_INSN (insn
))
535 /* It is an output reload insn after insn can be
536 rematerialized (potential candidate). */
537 create_cand (insn2
, regno_potential_cand
[src_regno
].nop
, dst_regno
);
540 gcc_assert (REG_P (*id
->operand_loc
[nop
]));
541 regno
= REGNO (*id
->operand_loc
[nop
]);
542 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
543 if (reg_renumber
[regno
] < 0)
544 create_cand (insn
, nop
, regno
);
547 regno_potential_cand
[regno
].insn
= insn
;
548 regno_potential_cand
[regno
].nop
= nop
;
553 for (struct lra_insn_reg
*reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
554 if (reg
->type
!= OP_IN
&& reg
->regno
!= regno
555 && reg
->regno
>= FIRST_PSEUDO_REGISTER
)
556 regno_potential_cand
[reg
->regno
].insn
= NULL
;
558 cands_num
= all_cands
.length ();
559 free (regno_potential_cand
);
564 /* Create and initialize BB data. */
566 create_remat_bb_data (void)
569 remat_bb_data_t bb_info
;
571 remat_bb_data
= XNEWVEC (struct remat_bb_data
,
572 last_basic_block_for_fn (cfun
));
573 FOR_ALL_BB_FN (bb
, cfun
)
575 #ifdef ENABLE_CHECKING
576 if (bb
->index
< 0 || bb
->index
>= last_basic_block_for_fn (cfun
))
579 bb_info
= get_remat_bb_data (bb
);
581 bitmap_initialize (&bb_info
->changed_regs
, ®_obstack
);
582 bitmap_initialize (&bb_info
->dead_regs
, ®_obstack
);
583 bitmap_initialize (&bb_info
->gen_cands
, ®_obstack
);
584 bitmap_initialize (&bb_info
->livein_cands
, ®_obstack
);
585 bitmap_initialize (&bb_info
->pavin_cands
, ®_obstack
);
586 bitmap_initialize (&bb_info
->pavout_cands
, ®_obstack
);
587 bitmap_initialize (&bb_info
->avin_cands
, ®_obstack
);
588 bitmap_initialize (&bb_info
->avout_cands
, ®_obstack
);
592 /* Dump all candidates to DUMP_FILE. */
594 dump_cands (FILE *dump_file
)
599 fprintf (dump_file
, "\nCands:\n");
600 for (i
= 0; i
< (int) cands_num
; i
++)
603 fprintf (dump_file
, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
604 i
, cand
->nop
, cand
->regno
, cand
->reload_regno
);
605 print_inline_rtx (dump_file
, cand
->insn
, 6);
606 fprintf (dump_file
, "\n");
610 /* Dump all candidates and BB data. */
612 dump_candidates_and_remat_bb_data (void)
616 if (lra_dump_file
== NULL
)
618 dump_cands (lra_dump_file
);
619 FOR_EACH_BB_FN (bb
, cfun
)
621 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
623 fprintf (lra_dump_file
, " register live in:");
624 dump_regset (df_get_live_in (bb
), lra_dump_file
);
625 putc ('\n', lra_dump_file
);
627 fprintf (lra_dump_file
, " register live out:");
628 dump_regset (df_get_live_out (bb
), lra_dump_file
);
629 putc ('\n', lra_dump_file
);
630 /* Changed/dead regs: */
631 fprintf (lra_dump_file
, " changed regs:");
632 dump_regset (&get_remat_bb_data (bb
)->changed_regs
, lra_dump_file
);
633 putc ('\n', lra_dump_file
);
634 fprintf (lra_dump_file
, " dead regs:");
635 dump_regset (&get_remat_bb_data (bb
)->dead_regs
, lra_dump_file
);
636 putc ('\n', lra_dump_file
);
637 lra_dump_bitmap_with_title ("cands generated in BB",
638 &get_remat_bb_data (bb
)->gen_cands
, bb
->index
);
639 lra_dump_bitmap_with_title ("livein cands in BB",
640 &get_remat_bb_data (bb
)->livein_cands
, bb
->index
);
641 lra_dump_bitmap_with_title ("pavin cands in BB",
642 &get_remat_bb_data (bb
)->pavin_cands
, bb
->index
);
643 lra_dump_bitmap_with_title ("pavout cands in BB",
644 &get_remat_bb_data (bb
)->pavout_cands
, bb
->index
);
645 lra_dump_bitmap_with_title ("avin cands in BB",
646 &get_remat_bb_data (bb
)->avin_cands
, bb
->index
);
647 lra_dump_bitmap_with_title ("avout cands in BB",
648 &get_remat_bb_data (bb
)->avout_cands
, bb
->index
);
652 /* Free all BB data. */
654 finish_remat_bb_data (void)
658 FOR_EACH_BB_FN (bb
, cfun
)
660 bitmap_clear (&get_remat_bb_data (bb
)->avout_cands
);
661 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
662 bitmap_clear (&get_remat_bb_data (bb
)->pavout_cands
);
663 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
664 bitmap_clear (&get_remat_bb_data (bb
)->livein_cands
);
665 bitmap_clear (&get_remat_bb_data (bb
)->gen_cands
);
666 bitmap_clear (&get_remat_bb_data (bb
)->dead_regs
);
667 bitmap_clear (&get_remat_bb_data (bb
)->changed_regs
);
669 free (remat_bb_data
);
674 /* Update changed_regs and dead_regs of BB from INSN. */
676 set_bb_regs (basic_block bb
, rtx_insn
*insn
)
678 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
679 struct lra_insn_reg
*reg
;
681 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
682 if (reg
->type
!= OP_IN
)
683 bitmap_set_bit (&get_remat_bb_data (bb
)->changed_regs
, reg
->regno
);
686 if (find_regno_note (insn
, REG_DEAD
, (unsigned) reg
->regno
) != NULL
)
687 bitmap_set_bit (&get_remat_bb_data (bb
)->dead_regs
, reg
->regno
);
690 for (int i
= 0; i
< call_used_regs_arr_len
; i
++)
691 bitmap_set_bit (&get_remat_bb_data (bb
)->dead_regs
,
692 call_used_regs_arr
[i
]);
695 /* Calculate changed_regs and dead_regs for each BB. */
697 calculate_local_reg_remat_bb_data (void)
702 FOR_EACH_BB_FN (bb
, cfun
)
703 FOR_BB_INSNS (bb
, insn
)
705 set_bb_regs (bb
, insn
);
710 /* Return true if REGNO is an input operand of INSN. */
712 input_regno_present_p (rtx_insn
*insn
, int regno
)
714 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
715 struct lra_insn_reg
*reg
;
717 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
718 if (reg
->type
== OP_IN
&& reg
->regno
== regno
)
723 /* Return true if a call used register is an input operand of INSN. */
725 call_used_input_regno_present_p (rtx_insn
*insn
)
727 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
728 struct lra_insn_reg
*reg
;
730 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
731 if (reg
->type
== OP_IN
&& reg
->regno
<= FIRST_PSEUDO_REGISTER
732 && TEST_HARD_REG_BIT (call_used_reg_set
, reg
->regno
))
737 /* Calculate livein_cands for each BB. */
739 calculate_livein_cands (void)
743 FOR_EACH_BB_FN (bb
, cfun
)
745 bitmap livein_regs
= df_get_live_in (bb
);
746 bitmap livein_cands
= &get_remat_bb_data (bb
)->livein_cands
;
747 for (unsigned int i
= 0; i
< cands_num
; i
++)
749 cand_t cand
= all_cands
[i
];
750 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
751 struct lra_insn_reg
*reg
;
753 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
754 if (reg
->type
== OP_IN
&& ! bitmap_bit_p (livein_regs
, reg
->regno
))
757 bitmap_set_bit (livein_cands
, i
);
762 /* Calculate gen_cands for each BB. */
764 calculate_gen_cands (void)
768 bitmap_head gen_insns
;
771 bitmap_initialize (&gen_insns
, ®_obstack
);
772 FOR_EACH_BB_FN (bb
, cfun
)
774 gen_cands
= &get_remat_bb_data (bb
)->gen_cands
;
775 bitmap_clear (&gen_insns
);
776 FOR_BB_INSNS (bb
, insn
)
779 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
780 struct lra_insn_reg
*reg
;
785 int src_regno
= -1, dst_regno
= -1;
787 if ((set
= single_set (insn
)) != NULL
788 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
790 src_regno
= REGNO (SET_SRC (set
));
791 dst_regno
= REGNO (SET_DEST (set
));
794 /* Update gen_cands: */
795 bitmap_clear (&temp_bitmap
);
796 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
797 if (reg
->type
!= OP_IN
798 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
799 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
801 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
803 cand
= insn_to_cand
[INSN_UID (insn2
)];
804 gcc_assert (cand
!= NULL
);
805 /* Ignore the reload insn. */
806 if (src_regno
== cand
->reload_regno
807 && dst_regno
== cand
->regno
)
809 if (cand
->regno
== reg
->regno
810 || input_regno_present_p (insn2
, reg
->regno
))
812 bitmap_clear_bit (gen_cands
, cand
->index
);
813 bitmap_set_bit (&temp_bitmap
, uid
);
818 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
820 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
822 cand
= insn_to_cand
[INSN_UID (insn2
)];
823 gcc_assert (cand
!= NULL
);
824 if (call_used_input_regno_present_p (insn2
))
826 bitmap_clear_bit (gen_cands
, cand
->index
);
827 bitmap_set_bit (&temp_bitmap
, uid
);
830 bitmap_and_compl_into (&gen_insns
, &temp_bitmap
);
832 cand
= insn_to_cand
[INSN_UID (insn
)];
835 bitmap_set_bit (gen_cands
, cand
->index
);
836 bitmap_set_bit (&gen_insns
, INSN_UID (insn
));
840 bitmap_clear (&gen_insns
);
845 /* The common transfer function used by the DF equation solver to
846 propagate (partial) availability info BB_IN to BB_OUT through block
847 with BB_INDEX according to the following equation:
849 bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
852 cand_trans_fun (int bb_index
, bitmap bb_in
, bitmap bb_out
)
854 remat_bb_data_t bb_info
;
855 bitmap bb_livein
, bb_changed_regs
, bb_dead_regs
;
859 bb_info
= get_remat_bb_data_by_index (bb_index
);
860 bb_livein
= &bb_info
->livein_cands
;
861 bb_changed_regs
= &bb_info
->changed_regs
;
862 bb_dead_regs
= &bb_info
->dead_regs
;
863 /* Calculate killed avin cands -- cands whose regs are changed or
864 becoming dead in the BB. We calculate it here as we hope that
865 repeated calculations are compensated by smaller size of BB_IN in
866 comparison with all candidates number. */
867 bitmap_clear (&temp_bitmap
);
868 EXECUTE_IF_SET_IN_BITMAP (bb_in
, 0, cid
, bi
)
870 cand_t cand
= all_cands
[cid
];
871 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
872 struct lra_insn_reg
*reg
;
874 if (! bitmap_bit_p (bb_livein
, cid
))
876 bitmap_set_bit (&temp_bitmap
, cid
);
879 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
880 /* Ignore all outputs which are not the regno for
881 rematerialization. */
882 if (reg
->type
== OP_OUT
&& reg
->regno
!= cand
->regno
)
884 else if (bitmap_bit_p (bb_changed_regs
, reg
->regno
)
885 || bitmap_bit_p (bb_dead_regs
, reg
->regno
))
887 bitmap_set_bit (&temp_bitmap
, cid
);
890 /* Check regno for rematerialization. */
891 if (bitmap_bit_p (bb_changed_regs
, cand
->regno
)
892 || bitmap_bit_p (bb_dead_regs
, cand
->regno
))
893 bitmap_set_bit (&temp_bitmap
, cid
);
895 return bitmap_ior_and_compl (bb_out
,
896 &bb_info
->gen_cands
, bb_in
, &temp_bitmap
);
901 /* The transfer function used by the DF equation solver to propagate
902 partial candidate availability info through block with BB_INDEX
903 according to the following equation:
905 bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
908 cand_pav_trans_fun (int bb_index
)
910 remat_bb_data_t bb_info
;
912 bb_info
= get_remat_bb_data_by_index (bb_index
);
913 return cand_trans_fun (bb_index
, &bb_info
->pavin_cands
,
914 &bb_info
->pavout_cands
);
917 /* The confluence function used by the DF equation solver to set up
918 cand_pav info for a block BB without predecessor. */
920 cand_pav_con_fun_0 (basic_block bb
)
922 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
925 /* The confluence function used by the DF equation solver to propagate
926 partial candidate availability info from predecessor to successor
927 on edge E (pred->bb) according to the following equation:
929 bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
932 cand_pav_con_fun_n (edge e
)
934 basic_block pred
= e
->src
;
935 basic_block bb
= e
->dest
;
936 remat_bb_data_t bb_info
;
937 bitmap bb_pavin
, pred_pavout
;
939 bb_info
= get_remat_bb_data (bb
);
940 bb_pavin
= &bb_info
->pavin_cands
;
941 pred_pavout
= &get_remat_bb_data (pred
)->pavout_cands
;
942 return bitmap_ior_into (bb_pavin
, pred_pavout
);
947 /* The transfer function used by the DF equation solver to propagate
948 candidate availability info through block with BB_INDEX according
949 to the following equation:
951 bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
954 cand_av_trans_fun (int bb_index
)
956 remat_bb_data_t bb_info
;
958 bb_info
= get_remat_bb_data_by_index (bb_index
);
959 return cand_trans_fun (bb_index
, &bb_info
->avin_cands
,
960 &bb_info
->avout_cands
);
963 /* The confluence function used by the DF equation solver to set up
964 cand_av info for a block BB without predecessor. */
966 cand_av_con_fun_0 (basic_block bb
)
968 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
971 /* The confluence function used by the DF equation solver to propagate
972 cand_av info from predecessor to successor on edge E (pred->bb)
973 according to the following equation:
975 bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
978 cand_av_con_fun_n (edge e
)
980 basic_block pred
= e
->src
;
981 basic_block bb
= e
->dest
;
982 remat_bb_data_t bb_info
;
983 bitmap bb_avin
, pred_avout
;
985 bb_info
= get_remat_bb_data (bb
);
986 bb_avin
= &bb_info
->avin_cands
;
987 pred_avout
= &get_remat_bb_data (pred
)->avout_cands
;
988 return bitmap_and_into (bb_avin
, pred_avout
);
991 /* Calculate available candidates for each BB. */
993 calculate_global_remat_bb_data (void)
998 (DF_FORWARD
, NULL
, cand_pav_con_fun_0
, cand_pav_con_fun_n
,
999 cand_pav_trans_fun
, &all_blocks
,
1000 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
1001 /* Initialize avin by pavin. */
1002 FOR_EACH_BB_FN (bb
, cfun
)
1003 bitmap_copy (&get_remat_bb_data (bb
)->avin_cands
,
1004 &get_remat_bb_data (bb
)->pavin_cands
);
1006 (DF_FORWARD
, NULL
, cand_av_con_fun_0
, cand_av_con_fun_n
,
1007 cand_av_trans_fun
, &all_blocks
,
1008 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
1013 /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
1015 change_sp_offset (rtx_insn
*insns
, HOST_WIDE_INT sp_offset
)
1017 for (rtx_insn
*insn
= insns
; insn
!= NULL
; insn
= NEXT_INSN (insn
))
1018 eliminate_regs_in_insn (insn
, false, false, sp_offset
);
1021 /* Return start hard register of REG (can be a hard or a pseudo reg)
1022 or -1 (if it is a spilled pseudo). Return number of hard registers
1023 occupied by REG through parameter NREGS if the start hard reg is
1026 get_hard_regs (struct lra_insn_reg
*reg
, int &nregs
)
1028 int regno
= reg
->regno
;
1029 int hard_regno
= regno
< FIRST_PSEUDO_REGISTER
? regno
: reg_renumber
[regno
];
1031 if (hard_regno
>= 0)
1032 nregs
= hard_regno_nregs
[hard_regno
][reg
->biggest_mode
];
1036 /* Make copy of and register scratch pseudos in rematerialized insn
1039 update_scratch_ops (rtx_insn
*remat_insn
)
1041 lra_insn_recog_data_t id
= lra_get_insn_recog_data (remat_insn
);
1042 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1043 for (int i
= 0; i
< static_id
->n_operands
; i
++)
1045 rtx
*loc
= id
->operand_loc
[i
];
1048 int regno
= REGNO (*loc
);
1049 if (! lra_former_scratch_p (regno
))
1051 *loc
= lra_create_new_reg (GET_MODE (*loc
), *loc
,
1052 lra_get_allocno_class (regno
),
1053 "scratch pseudo copy");
1054 lra_register_new_scratch_op (remat_insn
, i
);
1059 /* Insert rematerialization insns using the data-flow data calculated
1066 bitmap_head avail_cands
;
1067 bool changed_p
= false;
1068 /* Living hard regs and hard registers of living pseudos. */
1069 HARD_REG_SET live_hard_regs
;
1071 bitmap_initialize (&avail_cands
, ®_obstack
);
1072 FOR_EACH_BB_FN (bb
, cfun
)
1074 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_out (bb
));
1075 bitmap_and (&avail_cands
, &get_remat_bb_data (bb
)->avin_cands
,
1076 &get_remat_bb_data (bb
)->livein_cands
);
1077 FOR_BB_INSNS (bb
, insn
)
1079 if (!NONDEBUG_INSN_P (insn
))
1082 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
1083 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1084 struct lra_insn_reg
*reg
;
1089 int src_regno
= -1, dst_regno
= -1;
1091 if ((set
= single_set (insn
)) != NULL
1092 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
1094 src_regno
= REGNO (SET_SRC (set
));
1095 dst_regno
= REGNO (SET_DEST (set
));
1099 /* Check possibility of rematerialization (hard reg or
1100 unpsilled pseudo <- spilled pseudo): */
1101 if (dst_regno
>= 0 && src_regno
>= FIRST_PSEUDO_REGISTER
1102 && reg_renumber
[src_regno
] < 0
1103 && (dst_regno
< FIRST_PSEUDO_REGISTER
1104 || reg_renumber
[dst_regno
] >= 0))
1106 for (cand
= regno_cands
[src_regno
];
1108 cand
= cand
->next_regno_cand
)
1109 if (bitmap_bit_p (&avail_cands
, cand
->index
))
1112 int i
, hard_regno
, nregs
;
1113 rtx_insn
*remat_insn
= NULL
;
1114 HOST_WIDE_INT cand_sp_offset
= 0;
1117 lra_insn_recog_data_t cand_id
1118 = lra_get_insn_recog_data (cand
->insn
);
1119 struct lra_static_insn_data
*static_cand_id
1120 = cand_id
->insn_static_data
;
1121 rtx saved_op
= *cand_id
->operand_loc
[cand
->nop
];
1123 /* Check clobbers do not kill something living. */
1124 gcc_assert (REG_P (saved_op
));
1125 int ignore_regno
= REGNO (saved_op
);
1127 for (reg
= cand_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1128 if (reg
->type
!= OP_IN
&& reg
->regno
!= ignore_regno
)
1130 hard_regno
= get_hard_regs (reg
, nregs
);
1131 gcc_assert (hard_regno
>= 0);
1132 for (i
= 0; i
< nregs
; i
++)
1133 if (TEST_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
))
1141 for (reg
= static_cand_id
->hard_regs
;
1144 if (reg
->type
!= OP_IN
1145 && TEST_HARD_REG_BIT (live_hard_regs
, reg
->regno
))
1151 *cand_id
->operand_loc
[cand
->nop
] = SET_DEST (set
);
1152 lra_update_insn_regno_info (cand
->insn
);
1153 bool ok_p
= lra_constrain_insn (cand
->insn
);
1156 rtx remat_pat
= copy_insn (PATTERN (cand
->insn
));
1159 emit_insn (remat_pat
);
1160 remat_insn
= get_insns ();
1162 if (recog_memoized (remat_insn
) < 0)
1164 cand_sp_offset
= cand_id
->sp_offset
;
1166 *cand_id
->operand_loc
[cand
->nop
] = saved_op
;
1167 lra_update_insn_regno_info (cand
->insn
);
1171 bitmap_clear (&temp_bitmap
);
1172 /* Update avail_cands (see analogous code for
1173 calculate_gen_cands). */
1174 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1175 if (reg
->type
!= OP_IN
1176 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1177 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1179 cand
= all_cands
[cid
];
1181 /* Ignore the reload insn. */
1182 if (src_regno
== cand
->reload_regno
1183 && dst_regno
== cand
->regno
)
1185 if (cand
->regno
== reg
->regno
1186 || input_regno_present_p (cand
->insn
, reg
->regno
))
1187 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1191 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1193 cand
= all_cands
[cid
];
1195 if (call_used_input_regno_present_p (cand
->insn
))
1196 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1199 bitmap_and_compl_into (&avail_cands
, &temp_bitmap
);
1200 if ((cand
= insn_to_cand
[INSN_UID (insn
)]) != NULL
)
1201 bitmap_set_bit (&avail_cands
, cand
->index
);
1203 if (remat_insn
!= NULL
)
1205 HOST_WIDE_INT sp_offset_change
= cand_sp_offset
- id
->sp_offset
;
1206 if (sp_offset_change
!= 0)
1207 change_sp_offset (remat_insn
, sp_offset_change
);
1208 update_scratch_ops (remat_insn
);
1209 lra_process_new_insns (insn
, remat_insn
, NULL
,
1210 "Inserting rematerialization insn");
1211 lra_set_insn_deleted (insn
);
1216 /* Update live hard regs: */
1217 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1218 if (reg
->type
== OP_IN
1219 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1221 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1223 for (i
= 0; i
< nregs
; i
++)
1224 CLEAR_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1226 /* Process also hard regs (e.g. CC register) which are part
1227 of insn definition. */
1228 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1229 if (reg
->type
== OP_IN
1230 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1231 CLEAR_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1232 /* Inputs have been processed, now process outputs. */
1233 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1234 if (reg
->type
!= OP_IN
1235 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1237 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1239 for (i
= 0; i
< nregs
; i
++)
1240 SET_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1242 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1243 if (reg
->type
!= OP_IN
1244 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1245 SET_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1248 bitmap_clear (&avail_cands
);
1254 /* Current number of rematerialization iteration. */
1255 int lra_rematerialization_iter
;
1257 /* Entry point of the rematerialization sub-pass. Return true if we
1258 did any rematerialization. */
1264 int max_regno
= max_reg_num ();
1266 if (! flag_lra_remat
)
1268 lra_rematerialization_iter
++;
1269 if (lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
1271 if (lra_dump_file
!= NULL
)
1272 fprintf (lra_dump_file
,
1273 "\n******** Rematerialization #%d: ********\n\n",
1274 lra_rematerialization_iter
);
1275 timevar_push (TV_LRA_REMAT
);
1276 insn_to_cand
= XCNEWVEC (cand_t
, get_max_uid ());
1277 regno_cands
= XCNEWVEC (cand_t
, max_regno
);
1278 all_cands
.create (8000);
1279 call_used_regs_arr_len
= 0;
1280 for (int i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1281 if (call_used_regs
[i
])
1282 call_used_regs_arr
[call_used_regs_arr_len
++] = i
;
1283 initiate_cand_table ();
1285 create_remat_bb_data ();
1286 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1287 calculate_local_reg_remat_bb_data ();
1288 calculate_livein_cands ();
1289 calculate_gen_cands ();
1290 bitmap_initialize (&all_blocks
, ®_obstack
);
1291 FOR_ALL_BB_FN (bb
, cfun
)
1292 bitmap_set_bit (&all_blocks
, bb
->index
);
1293 calculate_global_remat_bb_data ();
1294 dump_candidates_and_remat_bb_data ();
1295 result
= do_remat ();
1296 all_cands
.release ();
1297 bitmap_clear (&temp_bitmap
);
1298 finish_remat_bb_data ();
1299 finish_cand_table ();
1300 bitmap_clear (&all_blocks
);
1302 free (insn_to_cand
);
1303 timevar_pop (TV_LRA_REMAT
);