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"
62 #include "rtl-error.h"
65 #include "insn-config.h"
81 #include "sparseset.h"
84 #include "insn-attr.h"
85 #include "insn-codes.h"
88 /* Number of candidates for rematerialization. */
89 static unsigned int cands_num
;
91 /* The following is used for representation of call_used_reg_set in
92 form array whose elements are hard register numbers with nonzero bit
93 in CALL_USED_REG_SET. */
94 static int call_used_regs_arr_len
;
95 static int call_used_regs_arr
[FIRST_PSEUDO_REGISTER
];
97 /* Bitmap used for different calculations. */
98 static bitmap_head temp_bitmap
;
100 typedef struct cand
*cand_t
;
101 typedef const struct cand
*const_cand_t
;
103 /* Insn candidates for rematerialization. The candidate insn should
104 have the following properies:
105 o no any memory (as access to memory is non-profitable)
106 o no INOUT regs (it means no non-paradoxical subreg of output reg)
107 o one output spilled pseudo (or reload pseudo of a spilled pseudo)
108 o all other pseudos are with assigned hard regs. */
111 /* Index of the candidates in all_cands. */
113 /* The candidate insn. */
115 /* Insn pseudo regno for rematerialization. */
117 /* Non-negative if a reload pseudo is in the insn instead of the
118 pseudo for rematerialization. */
120 /* Number of the operand containing the regno or its reload
123 /* Next candidate for the same regno. */
124 cand_t next_regno_cand
;
127 /* Vector containing all candidates. */
128 static vec
<cand_t
> all_cands
;
129 /* Map: insn -> candidate representing it. It is null if the insn can
130 not be used for rematerialization. */
131 static cand_t
*insn_to_cand
;
133 /* Map regno -> candidates can be used for the regno
134 rematerialization. */
135 static cand_t
*regno_cands
;
137 /* Data about basic blocks used for the rematerialization
141 /* Basic block about which the below data are. */
143 /* Registers changed in the basic block: */
144 bitmap_head changed_regs
;
145 /* Registers becoming dead in the BB. */
146 bitmap_head dead_regs
;
147 /* Cands present in the BB whose in/out regs are not changed after
148 the cands occurence and are not dead (except the reload
150 bitmap_head gen_cands
;
151 bitmap_head livein_cands
; /* cands whose inputs live at the BB start. */
152 bitmap_head pavin_cands
; /* cands partially available at BB entry. */
153 bitmap_head pavout_cands
; /* cands partially available at BB exit. */
154 bitmap_head avin_cands
; /* cands available at the entry of the BB. */
155 bitmap_head avout_cands
; /* cands available at the exit of the BB. */
158 /* Array for all BB data. Indexed by the corresponding BB index. */
159 typedef struct remat_bb_data
*remat_bb_data_t
;
161 /* Basic blocks for data flow problems -- all bocks except the special
163 static bitmap_head all_blocks
;
165 /* All basic block data are referred through the following array. */
166 static remat_bb_data_t remat_bb_data
;
168 /* Two small functions for access to the bb data. */
169 static inline remat_bb_data_t
170 get_remat_bb_data (basic_block bb
)
172 return &remat_bb_data
[(bb
)->index
];
175 static inline remat_bb_data_t
176 get_remat_bb_data_by_index (int index
)
178 return &remat_bb_data
[index
];
183 /* Recursive hash function for RTL X. */
196 val
+= (int) code
+ 4095;
198 /* Some RTL can be compared nonrecursively. */
202 return val
+ REGNO (x
);
205 return iterative_hash_object (XEXP (x
, 0), val
);
208 return iterative_hash_object (XSTR (x
, 0), val
);
220 /* Hash the elements. */
221 fmt
= GET_RTX_FORMAT (code
);
222 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
237 val
+= XVECLEN (x
, i
);
239 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
240 val
+= rtx_hash (XVECEXP (x
, i
, j
));
244 val
+= rtx_hash (XEXP (x
, i
));
249 val
+= htab_hash_string (XSTR (x
, i
));
257 /* It is believed that rtx's at this level will never
258 contain anything but integers and other rtx's, except for
259 within LABEL_REFs and SYMBOL_REFs. */
269 /* Hash table for the candidates. Different insns (e.g. structurally
270 the same insns or even insns with different unused output regs) can
271 be represented by the same candidate in the table. */
272 static htab_t cand_table
;
274 /* Hash function for candidate CAND. */
276 cand_hash (const void *cand
)
278 const_cand_t c
= (const_cand_t
) cand
;
279 lra_insn_recog_data_t id
= lra_get_insn_recog_data (c
->insn
);
280 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
281 int nops
= static_id
->n_operands
;
284 for (int i
= 0; i
< nops
; i
++)
286 hash
= iterative_hash_object (c
->regno
, hash
);
287 else if (static_id
->operand
[i
].type
== OP_IN
)
288 hash
= iterative_hash_object (*id
->operand_loc
[i
], hash
);
292 /* Equal function for candidates CAND1 and CAND2. They are equal if
293 the corresponding candidate insns have the same code, the same
294 regno for rematerialization, the same input operands. */
296 cand_eq_p (const void *cand1
, const void *cand2
)
298 const_cand_t c1
= (const_cand_t
) cand1
;
299 const_cand_t c2
= (const_cand_t
) cand2
;
300 lra_insn_recog_data_t id1
= lra_get_insn_recog_data (c1
->insn
);
301 lra_insn_recog_data_t id2
= lra_get_insn_recog_data (c2
->insn
);
302 struct lra_static_insn_data
*static_id1
= id1
->insn_static_data
;
303 int nops
= static_id1
->n_operands
;
305 if (c1
->regno
!= c2
->regno
306 || INSN_CODE (c1
->insn
) < 0
307 || INSN_CODE (c1
->insn
) != INSN_CODE (c2
->insn
))
309 gcc_assert (c1
->nop
== c2
->nop
);
310 for (int i
= 0; i
< nops
; i
++)
311 if (i
!= c1
->nop
&& static_id1
->operand
[i
].type
== OP_IN
312 && *id1
->operand_loc
[i
] != *id2
->operand_loc
[i
])
317 /* Insert candidate CAND into the table if it is not there yet.
318 Return candidate which is in the table. */
320 insert_cand (cand_t cand
)
324 entry_ptr
= htab_find_slot (cand_table
, cand
, INSERT
);
325 if (*entry_ptr
== NULL
)
326 *entry_ptr
= (void *) cand
;
327 return (cand_t
) *entry_ptr
;
330 /* Free candidate CAND memory. */
332 free_cand (void *cand
)
337 /* Initiate the candidate table. */
339 initiate_cand_table (void)
341 cand_table
= htab_create (8000, cand_hash
, cand_eq_p
,
342 (htab_del
) free_cand
);
345 /* Finish the candidate table. */
347 finish_cand_table (void)
349 htab_delete (cand_table
);
354 /* Return true if X contains memory or some UNSPEC. We can not just
355 check insn operands as memory or unspec might be not an operand
356 itself but contain an operand. Insn with memory access is not
357 profitable for rematerialization. Rematerialization of UNSPEC
358 might result in wrong code generation as the UNPEC effect is
359 unknown (e.g. generating a label). */
361 bad_for_rematerialization_p (rtx x
)
367 if (MEM_P (x
) || GET_CODE (x
) == UNSPEC
|| GET_CODE (x
) == UNSPEC_VOLATILE
)
370 fmt
= GET_RTX_FORMAT (code
);
371 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
375 if (bad_for_rematerialization_p (XEXP (x
, i
)))
378 else if (fmt
[i
] == 'E')
380 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
381 if (bad_for_rematerialization_p (XVECEXP (x
, i
, j
)))
388 /* If INSN can not be used for rematerialization, return negative
389 value. If INSN can be considered as a candidate for
390 rematerialization, return value which is the operand number of the
391 pseudo for which the insn can be used for rematerialization. Here
392 we consider the insns without any memory, spilled pseudo (except
393 for the rematerialization pseudo), or dying or unused regs. */
395 operand_to_remat (rtx_insn
*insn
)
397 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
398 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
399 struct lra_insn_reg
*reg
, *found_reg
= NULL
;
401 /* Don't rematerialize insns which can change PC. */
402 if (JUMP_P (insn
) || CALL_P (insn
))
404 /* First find a pseudo which can be rematerialized. */
405 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
406 /* True FRAME_POINTER_NEEDED might be because we can not follow
407 changing sp offsets, e.g. alloca is used. If the insn contains
408 stack pointer in such case, we can not rematerialize it as we
409 can not know sp offset at a rematerialization place. */
410 if (reg
->regno
== STACK_POINTER_REGNUM
&& frame_pointer_needed
)
412 else if (reg
->type
== OP_OUT
&& ! reg
->subreg_p
413 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
415 /* We permits only one spilled reg. */
416 if (found_reg
!= NULL
)
420 /* IRA calculates conflicts separately for subregs of two words
421 pseudo. Even if the pseudo lives, e.g. one its subreg can be
422 used lately, another subreg hard register can be already used
423 for something else. In such case, it is not safe to
424 rematerialize the insn. */
425 else if (reg
->type
== OP_IN
&& reg
->subreg_p
426 && reg
->regno
>= FIRST_PSEUDO_REGISTER
427 && (GET_MODE_SIZE (PSEUDO_REGNO_MODE (reg
->regno
))
428 == 2 * UNITS_PER_WORD
))
430 if (found_reg
== NULL
)
432 if (found_reg
->regno
< FIRST_PSEUDO_REGISTER
)
434 if (bad_for_rematerialization_p (PATTERN (insn
)))
436 /* Check the other regs are not spilled. */
437 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
438 if (found_reg
== reg
)
440 else if (reg
->type
== OP_INOUT
)
442 else if (reg
->regno
>= FIRST_PSEUDO_REGISTER
443 && reg_renumber
[reg
->regno
] < 0)
444 /* Another spilled reg. */
446 else if (reg
->type
== OP_IN
)
448 if (find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
449 /* We don't want to make live ranges longer. */
451 /* Check that there is no output reg as the input one. */
452 for (struct lra_insn_reg
*reg2
= id
->regs
;
455 if (reg2
->type
== OP_OUT
&& reg
->regno
== reg2
->regno
)
457 if (reg
->regno
< FIRST_PSEUDO_REGISTER
)
458 for (struct lra_insn_reg
*reg2
= static_id
->hard_regs
;
461 if (reg2
->type
== OP_OUT
462 && reg
->regno
<= reg2
->regno
465 + hard_regno_nregs
[reg
->regno
][reg
->biggest_mode
])))
468 /* Find the rematerialization operand. */
469 int nop
= static_id
->n_operands
;
470 for (int i
= 0; i
< nop
; i
++)
471 if (REG_P (*id
->operand_loc
[i
])
472 && (int) REGNO (*id
->operand_loc
[i
]) == found_reg
->regno
)
477 /* Create candidate for INSN with rematerialization operand NOP and
478 REGNO. Insert the candidate into the table and set up the
479 corresponding INSN_TO_CAND element. */
481 create_cand (rtx_insn
*insn
, int nop
, int regno
)
483 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
484 rtx reg
= *id
->operand_loc
[nop
];
485 gcc_assert (REG_P (reg
));
486 int op_regno
= REGNO (reg
);
487 gcc_assert (op_regno
>= FIRST_PSEUDO_REGISTER
);
488 cand_t cand
= XNEW (struct cand
);
492 cand
->reload_regno
= op_regno
== regno
? -1 : op_regno
;
493 gcc_assert (cand
->regno
>= 0);
494 cand_t cand_in_table
= insert_cand (cand
);
495 insn_to_cand
[INSN_UID (insn
)] = cand_in_table
;
496 if (cand
!= cand_in_table
)
501 cand
->index
= all_cands
.length ();
502 all_cands
.safe_push (cand
);
503 cand
->next_regno_cand
= regno_cands
[cand
->regno
];
504 regno_cands
[cand
->regno
] = cand
;
508 /* Create rematerialization candidates (inserting them into the
514 struct potential_cand
519 struct potential_cand
*regno_potential_cand
;
521 /* Create candidates. */
522 regno_potential_cand
= XCNEWVEC (struct potential_cand
, max_reg_num ());
523 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
527 int src_regno
, dst_regno
;
529 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
530 int nop
= operand_to_remat (insn
);
533 if ((set
= single_set (insn
)) != NULL
534 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
))
535 && ((src_regno
= REGNO (SET_SRC (set
)))
536 >= lra_constraint_new_regno_start
)
537 && (dst_regno
= REGNO (SET_DEST (set
))) >= FIRST_PSEUDO_REGISTER
538 && reg_renumber
[dst_regno
] < 0
539 && (insn2
= regno_potential_cand
[src_regno
].insn
) != NULL
540 && BLOCK_FOR_INSN (insn2
) == BLOCK_FOR_INSN (insn
))
541 /* It is an output reload insn after insn can be
542 rematerialized (potential candidate). */
543 create_cand (insn2
, regno_potential_cand
[src_regno
].nop
, dst_regno
);
546 gcc_assert (REG_P (*id
->operand_loc
[nop
]));
547 regno
= REGNO (*id
->operand_loc
[nop
]);
548 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
549 if (reg_renumber
[regno
] < 0)
550 create_cand (insn
, nop
, regno
);
553 regno_potential_cand
[regno
].insn
= insn
;
554 regno_potential_cand
[regno
].nop
= nop
;
559 for (struct lra_insn_reg
*reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
560 if (reg
->type
!= OP_IN
&& reg
->regno
!= regno
561 && reg
->regno
>= FIRST_PSEUDO_REGISTER
)
562 regno_potential_cand
[reg
->regno
].insn
= NULL
;
564 cands_num
= all_cands
.length ();
565 free (regno_potential_cand
);
570 /* Create and initialize BB data. */
572 create_remat_bb_data (void)
575 remat_bb_data_t bb_info
;
577 remat_bb_data
= XNEWVEC (struct remat_bb_data
,
578 last_basic_block_for_fn (cfun
));
579 FOR_ALL_BB_FN (bb
, cfun
)
581 gcc_checking_assert (bb
->index
>= 0
582 && bb
->index
< last_basic_block_for_fn (cfun
));
583 bb_info
= get_remat_bb_data (bb
);
585 bitmap_initialize (&bb_info
->changed_regs
, ®_obstack
);
586 bitmap_initialize (&bb_info
->dead_regs
, ®_obstack
);
587 bitmap_initialize (&bb_info
->gen_cands
, ®_obstack
);
588 bitmap_initialize (&bb_info
->livein_cands
, ®_obstack
);
589 bitmap_initialize (&bb_info
->pavin_cands
, ®_obstack
);
590 bitmap_initialize (&bb_info
->pavout_cands
, ®_obstack
);
591 bitmap_initialize (&bb_info
->avin_cands
, ®_obstack
);
592 bitmap_initialize (&bb_info
->avout_cands
, ®_obstack
);
596 /* Dump all candidates to DUMP_FILE. */
598 dump_cands (FILE *dump_file
)
603 fprintf (dump_file
, "\nCands:\n");
604 for (i
= 0; i
< (int) cands_num
; i
++)
607 fprintf (dump_file
, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
608 i
, cand
->nop
, cand
->regno
, cand
->reload_regno
);
609 print_inline_rtx (dump_file
, cand
->insn
, 6);
610 fprintf (dump_file
, "\n");
614 /* Dump all candidates and BB data. */
616 dump_candidates_and_remat_bb_data (void)
620 if (lra_dump_file
== NULL
)
622 dump_cands (lra_dump_file
);
623 FOR_EACH_BB_FN (bb
, cfun
)
625 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
627 fprintf (lra_dump_file
, " register live in:");
628 dump_regset (df_get_live_in (bb
), lra_dump_file
);
629 putc ('\n', lra_dump_file
);
631 fprintf (lra_dump_file
, " register live out:");
632 dump_regset (df_get_live_out (bb
), lra_dump_file
);
633 putc ('\n', lra_dump_file
);
634 /* Changed/dead regs: */
635 fprintf (lra_dump_file
, " changed regs:");
636 dump_regset (&get_remat_bb_data (bb
)->changed_regs
, lra_dump_file
);
637 putc ('\n', lra_dump_file
);
638 fprintf (lra_dump_file
, " dead regs:");
639 dump_regset (&get_remat_bb_data (bb
)->dead_regs
, lra_dump_file
);
640 putc ('\n', lra_dump_file
);
641 lra_dump_bitmap_with_title ("cands generated in BB",
642 &get_remat_bb_data (bb
)->gen_cands
, bb
->index
);
643 lra_dump_bitmap_with_title ("livein cands in BB",
644 &get_remat_bb_data (bb
)->livein_cands
, bb
->index
);
645 lra_dump_bitmap_with_title ("pavin cands in BB",
646 &get_remat_bb_data (bb
)->pavin_cands
, bb
->index
);
647 lra_dump_bitmap_with_title ("pavout cands in BB",
648 &get_remat_bb_data (bb
)->pavout_cands
, bb
->index
);
649 lra_dump_bitmap_with_title ("avin cands in BB",
650 &get_remat_bb_data (bb
)->avin_cands
, bb
->index
);
651 lra_dump_bitmap_with_title ("avout cands in BB",
652 &get_remat_bb_data (bb
)->avout_cands
, bb
->index
);
656 /* Free all BB data. */
658 finish_remat_bb_data (void)
662 FOR_EACH_BB_FN (bb
, cfun
)
664 bitmap_clear (&get_remat_bb_data (bb
)->avout_cands
);
665 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
666 bitmap_clear (&get_remat_bb_data (bb
)->pavout_cands
);
667 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
668 bitmap_clear (&get_remat_bb_data (bb
)->livein_cands
);
669 bitmap_clear (&get_remat_bb_data (bb
)->gen_cands
);
670 bitmap_clear (&get_remat_bb_data (bb
)->dead_regs
);
671 bitmap_clear (&get_remat_bb_data (bb
)->changed_regs
);
673 free (remat_bb_data
);
678 /* Update changed_regs and dead_regs of BB from INSN. */
680 set_bb_regs (basic_block bb
, rtx_insn
*insn
)
682 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
683 struct lra_insn_reg
*reg
;
685 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
686 if (reg
->type
!= OP_IN
)
687 bitmap_set_bit (&get_remat_bb_data (bb
)->changed_regs
, reg
->regno
);
690 if (find_regno_note (insn
, REG_DEAD
, (unsigned) reg
->regno
) != NULL
)
691 bitmap_set_bit (&get_remat_bb_data (bb
)->dead_regs
, reg
->regno
);
694 for (int i
= 0; i
< call_used_regs_arr_len
; i
++)
695 bitmap_set_bit (&get_remat_bb_data (bb
)->dead_regs
,
696 call_used_regs_arr
[i
]);
699 /* Calculate changed_regs and dead_regs for each BB. */
701 calculate_local_reg_remat_bb_data (void)
706 FOR_EACH_BB_FN (bb
, cfun
)
707 FOR_BB_INSNS (bb
, insn
)
709 set_bb_regs (bb
, insn
);
714 /* Return true if REGNO is an input operand of INSN. */
716 input_regno_present_p (rtx_insn
*insn
, int regno
)
718 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
719 struct lra_insn_reg
*reg
;
721 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
722 if (reg
->type
== OP_IN
&& reg
->regno
== regno
)
727 /* Return true if a call used register is an input operand of INSN. */
729 call_used_input_regno_present_p (rtx_insn
*insn
)
731 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
732 struct lra_insn_reg
*reg
;
734 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
735 if (reg
->type
== OP_IN
&& reg
->regno
<= FIRST_PSEUDO_REGISTER
736 && TEST_HARD_REG_BIT (call_used_reg_set
, reg
->regno
))
741 /* Calculate livein_cands for each BB. */
743 calculate_livein_cands (void)
747 FOR_EACH_BB_FN (bb
, cfun
)
749 bitmap livein_regs
= df_get_live_in (bb
);
750 bitmap livein_cands
= &get_remat_bb_data (bb
)->livein_cands
;
751 for (unsigned int i
= 0; i
< cands_num
; i
++)
753 cand_t cand
= all_cands
[i
];
754 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
755 struct lra_insn_reg
*reg
;
757 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
758 if (reg
->type
== OP_IN
&& ! bitmap_bit_p (livein_regs
, reg
->regno
))
761 bitmap_set_bit (livein_cands
, i
);
766 /* Calculate gen_cands for each BB. */
768 calculate_gen_cands (void)
772 bitmap_head gen_insns
;
775 bitmap_initialize (&gen_insns
, ®_obstack
);
776 FOR_EACH_BB_FN (bb
, cfun
)
778 gen_cands
= &get_remat_bb_data (bb
)->gen_cands
;
779 bitmap_clear (&gen_insns
);
780 FOR_BB_INSNS (bb
, insn
)
783 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
784 struct lra_insn_reg
*reg
;
789 int src_regno
= -1, dst_regno
= -1;
791 if ((set
= single_set (insn
)) != NULL
792 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
794 src_regno
= REGNO (SET_SRC (set
));
795 dst_regno
= REGNO (SET_DEST (set
));
798 /* Update gen_cands: */
799 bitmap_clear (&temp_bitmap
);
800 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
801 if (reg
->type
!= OP_IN
802 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
803 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
805 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
807 cand
= insn_to_cand
[INSN_UID (insn2
)];
808 gcc_assert (cand
!= NULL
);
809 /* Ignore the reload insn. */
810 if (src_regno
== cand
->reload_regno
811 && dst_regno
== cand
->regno
)
813 if (cand
->regno
== reg
->regno
814 || input_regno_present_p (insn2
, reg
->regno
))
816 bitmap_clear_bit (gen_cands
, cand
->index
);
817 bitmap_set_bit (&temp_bitmap
, uid
);
822 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
824 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
826 cand
= insn_to_cand
[INSN_UID (insn2
)];
827 gcc_assert (cand
!= NULL
);
828 if (call_used_input_regno_present_p (insn2
))
830 bitmap_clear_bit (gen_cands
, cand
->index
);
831 bitmap_set_bit (&temp_bitmap
, uid
);
834 bitmap_and_compl_into (&gen_insns
, &temp_bitmap
);
836 cand
= insn_to_cand
[INSN_UID (insn
)];
839 bitmap_set_bit (gen_cands
, cand
->index
);
840 bitmap_set_bit (&gen_insns
, INSN_UID (insn
));
844 bitmap_clear (&gen_insns
);
849 /* The common transfer function used by the DF equation solver to
850 propagate (partial) availability info BB_IN to BB_OUT through block
851 with BB_INDEX according to the following equation:
853 bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
856 cand_trans_fun (int bb_index
, bitmap bb_in
, bitmap bb_out
)
858 remat_bb_data_t bb_info
;
859 bitmap bb_livein
, bb_changed_regs
, bb_dead_regs
;
863 bb_info
= get_remat_bb_data_by_index (bb_index
);
864 bb_livein
= &bb_info
->livein_cands
;
865 bb_changed_regs
= &bb_info
->changed_regs
;
866 bb_dead_regs
= &bb_info
->dead_regs
;
867 /* Calculate killed avin cands -- cands whose regs are changed or
868 becoming dead in the BB. We calculate it here as we hope that
869 repeated calculations are compensated by smaller size of BB_IN in
870 comparison with all candidates number. */
871 bitmap_clear (&temp_bitmap
);
872 EXECUTE_IF_SET_IN_BITMAP (bb_in
, 0, cid
, bi
)
874 cand_t cand
= all_cands
[cid
];
875 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
876 struct lra_insn_reg
*reg
;
878 if (! bitmap_bit_p (bb_livein
, cid
))
880 bitmap_set_bit (&temp_bitmap
, cid
);
883 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
884 /* Ignore all outputs which are not the regno for
885 rematerialization. */
886 if (reg
->type
== OP_OUT
&& reg
->regno
!= cand
->regno
)
888 else if (bitmap_bit_p (bb_changed_regs
, reg
->regno
)
889 || bitmap_bit_p (bb_dead_regs
, reg
->regno
))
891 bitmap_set_bit (&temp_bitmap
, cid
);
894 /* Check regno for rematerialization. */
895 if (bitmap_bit_p (bb_changed_regs
, cand
->regno
)
896 || bitmap_bit_p (bb_dead_regs
, cand
->regno
))
897 bitmap_set_bit (&temp_bitmap
, cid
);
899 return bitmap_ior_and_compl (bb_out
,
900 &bb_info
->gen_cands
, bb_in
, &temp_bitmap
);
905 /* The transfer function used by the DF equation solver to propagate
906 partial candidate availability info through block with BB_INDEX
907 according to the following equation:
909 bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
912 cand_pav_trans_fun (int bb_index
)
914 remat_bb_data_t bb_info
;
916 bb_info
= get_remat_bb_data_by_index (bb_index
);
917 return cand_trans_fun (bb_index
, &bb_info
->pavin_cands
,
918 &bb_info
->pavout_cands
);
921 /* The confluence function used by the DF equation solver to set up
922 cand_pav info for a block BB without predecessor. */
924 cand_pav_con_fun_0 (basic_block bb
)
926 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
929 /* The confluence function used by the DF equation solver to propagate
930 partial candidate availability info from predecessor to successor
931 on edge E (pred->bb) according to the following equation:
933 bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
936 cand_pav_con_fun_n (edge e
)
938 basic_block pred
= e
->src
;
939 basic_block bb
= e
->dest
;
940 remat_bb_data_t bb_info
;
941 bitmap bb_pavin
, pred_pavout
;
943 bb_info
= get_remat_bb_data (bb
);
944 bb_pavin
= &bb_info
->pavin_cands
;
945 pred_pavout
= &get_remat_bb_data (pred
)->pavout_cands
;
946 return bitmap_ior_into (bb_pavin
, pred_pavout
);
951 /* The transfer function used by the DF equation solver to propagate
952 candidate availability info through block with BB_INDEX according
953 to the following equation:
955 bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
958 cand_av_trans_fun (int bb_index
)
960 remat_bb_data_t bb_info
;
962 bb_info
= get_remat_bb_data_by_index (bb_index
);
963 return cand_trans_fun (bb_index
, &bb_info
->avin_cands
,
964 &bb_info
->avout_cands
);
967 /* The confluence function used by the DF equation solver to set up
968 cand_av info for a block BB without predecessor. */
970 cand_av_con_fun_0 (basic_block bb
)
972 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
975 /* The confluence function used by the DF equation solver to propagate
976 cand_av info from predecessor to successor on edge E (pred->bb)
977 according to the following equation:
979 bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
982 cand_av_con_fun_n (edge e
)
984 basic_block pred
= e
->src
;
985 basic_block bb
= e
->dest
;
986 remat_bb_data_t bb_info
;
987 bitmap bb_avin
, pred_avout
;
989 bb_info
= get_remat_bb_data (bb
);
990 bb_avin
= &bb_info
->avin_cands
;
991 pred_avout
= &get_remat_bb_data (pred
)->avout_cands
;
992 return bitmap_and_into (bb_avin
, pred_avout
);
995 /* Calculate available candidates for each BB. */
997 calculate_global_remat_bb_data (void)
1002 (DF_FORWARD
, NULL
, cand_pav_con_fun_0
, cand_pav_con_fun_n
,
1003 cand_pav_trans_fun
, &all_blocks
,
1004 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
1005 /* Initialize avin by pavin. */
1006 FOR_EACH_BB_FN (bb
, cfun
)
1007 bitmap_copy (&get_remat_bb_data (bb
)->avin_cands
,
1008 &get_remat_bb_data (bb
)->pavin_cands
);
1010 (DF_FORWARD
, NULL
, cand_av_con_fun_0
, cand_av_con_fun_n
,
1011 cand_av_trans_fun
, &all_blocks
,
1012 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
1017 /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
1019 change_sp_offset (rtx_insn
*insns
, HOST_WIDE_INT sp_offset
)
1021 for (rtx_insn
*insn
= insns
; insn
!= NULL
; insn
= NEXT_INSN (insn
))
1022 eliminate_regs_in_insn (insn
, false, false, sp_offset
);
1025 /* Return start hard register of REG (can be a hard or a pseudo reg)
1026 or -1 (if it is a spilled pseudo). Return number of hard registers
1027 occupied by REG through parameter NREGS if the start hard reg is
1030 get_hard_regs (struct lra_insn_reg
*reg
, int &nregs
)
1032 int regno
= reg
->regno
;
1033 int hard_regno
= regno
< FIRST_PSEUDO_REGISTER
? regno
: reg_renumber
[regno
];
1035 if (hard_regno
>= 0)
1036 nregs
= hard_regno_nregs
[hard_regno
][reg
->biggest_mode
];
1040 /* Make copy of and register scratch pseudos in rematerialized insn
1043 update_scratch_ops (rtx_insn
*remat_insn
)
1045 lra_insn_recog_data_t id
= lra_get_insn_recog_data (remat_insn
);
1046 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1047 for (int i
= 0; i
< static_id
->n_operands
; i
++)
1049 rtx
*loc
= id
->operand_loc
[i
];
1052 int regno
= REGNO (*loc
);
1053 if (! lra_former_scratch_p (regno
))
1055 *loc
= lra_create_new_reg (GET_MODE (*loc
), *loc
,
1056 lra_get_allocno_class (regno
),
1057 "scratch pseudo copy");
1058 lra_register_new_scratch_op (remat_insn
, i
);
1063 /* Insert rematerialization insns using the data-flow data calculated
1070 bitmap_head avail_cands
;
1071 bool changed_p
= false;
1072 /* Living hard regs and hard registers of living pseudos. */
1073 HARD_REG_SET live_hard_regs
;
1075 bitmap_initialize (&avail_cands
, ®_obstack
);
1076 FOR_EACH_BB_FN (bb
, cfun
)
1078 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_out (bb
));
1079 bitmap_and (&avail_cands
, &get_remat_bb_data (bb
)->avin_cands
,
1080 &get_remat_bb_data (bb
)->livein_cands
);
1081 FOR_BB_INSNS (bb
, insn
)
1083 if (!NONDEBUG_INSN_P (insn
))
1086 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
1087 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1088 struct lra_insn_reg
*reg
;
1093 int src_regno
= -1, dst_regno
= -1;
1095 if ((set
= single_set (insn
)) != NULL
1096 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
1098 src_regno
= REGNO (SET_SRC (set
));
1099 dst_regno
= REGNO (SET_DEST (set
));
1103 /* Check possibility of rematerialization (hard reg or
1104 unpsilled pseudo <- spilled pseudo): */
1105 if (dst_regno
>= 0 && src_regno
>= FIRST_PSEUDO_REGISTER
1106 && reg_renumber
[src_regno
] < 0
1107 && (dst_regno
< FIRST_PSEUDO_REGISTER
1108 || reg_renumber
[dst_regno
] >= 0))
1110 for (cand
= regno_cands
[src_regno
];
1112 cand
= cand
->next_regno_cand
)
1113 if (bitmap_bit_p (&avail_cands
, cand
->index
))
1116 int i
, hard_regno
, nregs
;
1117 rtx_insn
*remat_insn
= NULL
;
1118 HOST_WIDE_INT cand_sp_offset
= 0;
1121 lra_insn_recog_data_t cand_id
1122 = lra_get_insn_recog_data (cand
->insn
);
1123 struct lra_static_insn_data
*static_cand_id
1124 = cand_id
->insn_static_data
;
1125 rtx saved_op
= *cand_id
->operand_loc
[cand
->nop
];
1127 /* Check clobbers do not kill something living. */
1128 gcc_assert (REG_P (saved_op
));
1129 int ignore_regno
= REGNO (saved_op
);
1131 for (reg
= cand_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1132 if (reg
->type
!= OP_IN
&& reg
->regno
!= ignore_regno
)
1134 hard_regno
= get_hard_regs (reg
, nregs
);
1135 gcc_assert (hard_regno
>= 0);
1136 for (i
= 0; i
< nregs
; i
++)
1137 if (TEST_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
))
1145 for (reg
= static_cand_id
->hard_regs
;
1148 if (reg
->type
!= OP_IN
1149 && TEST_HARD_REG_BIT (live_hard_regs
, reg
->regno
))
1155 *cand_id
->operand_loc
[cand
->nop
] = SET_DEST (set
);
1156 lra_update_insn_regno_info (cand
->insn
);
1157 bool ok_p
= lra_constrain_insn (cand
->insn
);
1160 rtx remat_pat
= copy_insn (PATTERN (cand
->insn
));
1163 emit_insn (remat_pat
);
1164 remat_insn
= get_insns ();
1166 if (recog_memoized (remat_insn
) < 0)
1168 cand_sp_offset
= cand_id
->sp_offset
;
1170 *cand_id
->operand_loc
[cand
->nop
] = saved_op
;
1171 lra_update_insn_regno_info (cand
->insn
);
1175 bitmap_clear (&temp_bitmap
);
1176 /* Update avail_cands (see analogous code for
1177 calculate_gen_cands). */
1178 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1179 if (reg
->type
!= OP_IN
1180 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1181 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1183 cand
= all_cands
[cid
];
1185 /* Ignore the reload insn. */
1186 if (src_regno
== cand
->reload_regno
1187 && dst_regno
== cand
->regno
)
1189 if (cand
->regno
== reg
->regno
1190 || input_regno_present_p (cand
->insn
, reg
->regno
))
1191 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1195 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1197 cand
= all_cands
[cid
];
1199 if (call_used_input_regno_present_p (cand
->insn
))
1200 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1203 bitmap_and_compl_into (&avail_cands
, &temp_bitmap
);
1204 if ((cand
= insn_to_cand
[INSN_UID (insn
)]) != NULL
)
1205 bitmap_set_bit (&avail_cands
, cand
->index
);
1207 if (remat_insn
!= NULL
)
1209 HOST_WIDE_INT sp_offset_change
= cand_sp_offset
- id
->sp_offset
;
1210 if (sp_offset_change
!= 0)
1211 change_sp_offset (remat_insn
, sp_offset_change
);
1212 update_scratch_ops (remat_insn
);
1213 lra_process_new_insns (insn
, remat_insn
, NULL
,
1214 "Inserting rematerialization insn");
1215 lra_set_insn_deleted (insn
);
1220 /* Update live hard regs: */
1221 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1222 if (reg
->type
== OP_IN
1223 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1225 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1227 for (i
= 0; i
< nregs
; i
++)
1228 CLEAR_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1230 /* Process also hard regs (e.g. CC register) which are part
1231 of insn definition. */
1232 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1233 if (reg
->type
== OP_IN
1234 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1235 CLEAR_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1236 /* Inputs have been processed, now process outputs. */
1237 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1238 if (reg
->type
!= OP_IN
1239 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1241 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1243 for (i
= 0; i
< nregs
; i
++)
1244 SET_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1246 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1247 if (reg
->type
!= OP_IN
1248 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1249 SET_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1252 bitmap_clear (&avail_cands
);
1258 /* Current number of rematerialization iteration. */
1259 int lra_rematerialization_iter
;
1261 /* Entry point of the rematerialization sub-pass. Return true if we
1262 did any rematerialization. */
1268 int max_regno
= max_reg_num ();
1270 if (! flag_lra_remat
)
1272 lra_rematerialization_iter
++;
1273 if (lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
1275 if (lra_dump_file
!= NULL
)
1276 fprintf (lra_dump_file
,
1277 "\n******** Rematerialization #%d: ********\n\n",
1278 lra_rematerialization_iter
);
1279 timevar_push (TV_LRA_REMAT
);
1280 insn_to_cand
= XCNEWVEC (cand_t
, get_max_uid ());
1281 regno_cands
= XCNEWVEC (cand_t
, max_regno
);
1282 all_cands
.create (8000);
1283 call_used_regs_arr_len
= 0;
1284 for (int i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1285 if (call_used_regs
[i
])
1286 call_used_regs_arr
[call_used_regs_arr_len
++] = i
;
1287 initiate_cand_table ();
1289 create_remat_bb_data ();
1290 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1291 calculate_local_reg_remat_bb_data ();
1292 calculate_livein_cands ();
1293 calculate_gen_cands ();
1294 bitmap_initialize (&all_blocks
, ®_obstack
);
1295 FOR_ALL_BB_FN (bb
, cfun
)
1296 bitmap_set_bit (&all_blocks
, bb
->index
);
1297 calculate_global_remat_bb_data ();
1298 dump_candidates_and_remat_bb_data ();
1299 result
= do_remat ();
1300 all_cands
.release ();
1301 bitmap_clear (&temp_bitmap
);
1302 finish_remat_bb_data ();
1303 finish_cand_table ();
1304 bitmap_clear (&all_blocks
);
1306 free (insn_to_cand
);
1307 timevar_pop (TV_LRA_REMAT
);