1 /* Rematerialize pseudos values.
2 Copyright (C) 2014-2016 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"
61 #include "insn-config.h"
68 /* Number of candidates for rematerialization. */
69 static unsigned int cands_num
;
71 /* The following is used for representation of call_used_reg_set in
72 form array whose elements are hard register numbers with nonzero bit
73 in CALL_USED_REG_SET. */
74 static int call_used_regs_arr_len
;
75 static int call_used_regs_arr
[FIRST_PSEUDO_REGISTER
];
77 /* Bitmap used for different calculations. */
78 static bitmap_head temp_bitmap
;
80 /* Registers accessed via subreg_p. */
81 static bitmap_head subreg_regs
;
83 typedef struct cand
*cand_t
;
84 typedef const struct cand
*const_cand_t
;
86 /* Insn candidates for rematerialization. The candidate insn should
87 have the following properies:
88 o no any memory (as access to memory is non-profitable)
89 o no INOUT regs (it means no non-paradoxical subreg of output reg)
90 o one output spilled pseudo (or reload pseudo of a spilled pseudo)
91 o all other pseudos are with assigned hard regs. */
94 /* Index of the candidates in all_cands. */
96 /* The candidate insn. */
98 /* Insn pseudo regno for rematerialization. */
100 /* Non-negative if a reload pseudo is in the insn instead of the
101 pseudo for rematerialization. */
103 /* Number of the operand containing the regno or its reload
106 /* Next candidate for the same regno. */
107 cand_t next_regno_cand
;
110 /* Vector containing all candidates. */
111 static vec
<cand_t
> all_cands
;
112 /* Map: insn -> candidate representing it. It is null if the insn can
113 not be used for rematerialization. */
114 static cand_t
*insn_to_cand
;
116 /* Map regno -> candidates can be used for the regno
117 rematerialization. */
118 static cand_t
*regno_cands
;
120 /* Data about basic blocks used for the rematerialization
124 /* Basic block about which the below data are. */
126 /* Registers changed in the basic block: */
127 bitmap_head changed_regs
;
128 /* Registers becoming dead in the BB. */
129 bitmap_head dead_regs
;
130 /* Cands present in the BB whose in/out regs are not changed after
131 the cands occurence and are not dead (except the reload
133 bitmap_head gen_cands
;
134 bitmap_head livein_cands
; /* cands whose inputs live at the BB start. */
135 bitmap_head pavin_cands
; /* cands partially available at BB entry. */
136 bitmap_head pavout_cands
; /* cands partially available at BB exit. */
137 bitmap_head avin_cands
; /* cands available at the entry of the BB. */
138 bitmap_head avout_cands
; /* cands available at the exit of the BB. */
141 /* Array for all BB data. Indexed by the corresponding BB index. */
142 typedef struct remat_bb_data
*remat_bb_data_t
;
144 /* Basic blocks for data flow problems -- all bocks except the special
146 static bitmap_head all_blocks
;
148 /* All basic block data are referred through the following array. */
149 static remat_bb_data_t remat_bb_data
;
151 /* Two small functions for access to the bb data. */
152 static inline remat_bb_data_t
153 get_remat_bb_data (basic_block bb
)
155 return &remat_bb_data
[(bb
)->index
];
158 static inline remat_bb_data_t
159 get_remat_bb_data_by_index (int index
)
161 return &remat_bb_data
[index
];
166 /* Recursive hash function for RTL X. */
179 val
+= (int) code
+ 4095;
181 /* Some RTL can be compared nonrecursively. */
185 return val
+ REGNO (x
);
188 return iterative_hash_object (XEXP (x
, 0), val
);
191 return iterative_hash_object (XSTR (x
, 0), val
);
203 /* Hash the elements. */
204 fmt
= GET_RTX_FORMAT (code
);
205 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
220 val
+= XVECLEN (x
, i
);
222 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
223 val
+= rtx_hash (XVECEXP (x
, i
, j
));
227 val
+= rtx_hash (XEXP (x
, i
));
232 val
+= htab_hash_string (XSTR (x
, i
));
240 /* It is believed that rtx's at this level will never
241 contain anything but integers and other rtx's, except for
242 within LABEL_REFs and SYMBOL_REFs. */
252 /* Hash table for the candidates. Different insns (e.g. structurally
253 the same insns or even insns with different unused output regs) can
254 be represented by the same candidate in the table. */
255 static htab_t cand_table
;
257 /* Hash function for candidate CAND. */
259 cand_hash (const void *cand
)
261 const_cand_t c
= (const_cand_t
) cand
;
262 lra_insn_recog_data_t id
= lra_get_insn_recog_data (c
->insn
);
263 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
264 int nops
= static_id
->n_operands
;
267 for (int i
= 0; i
< nops
; i
++)
269 hash
= iterative_hash_object (c
->regno
, hash
);
270 else if (static_id
->operand
[i
].type
== OP_IN
)
271 hash
= iterative_hash_object (*id
->operand_loc
[i
], hash
);
275 /* Equal function for candidates CAND1 and CAND2. They are equal if
276 the corresponding candidate insns have the same code, the same
277 regno for rematerialization, the same input operands. */
279 cand_eq_p (const void *cand1
, const void *cand2
)
281 const_cand_t c1
= (const_cand_t
) cand1
;
282 const_cand_t c2
= (const_cand_t
) cand2
;
283 lra_insn_recog_data_t id1
= lra_get_insn_recog_data (c1
->insn
);
284 lra_insn_recog_data_t id2
= lra_get_insn_recog_data (c2
->insn
);
285 struct lra_static_insn_data
*static_id1
= id1
->insn_static_data
;
286 int nops
= static_id1
->n_operands
;
288 if (c1
->regno
!= c2
->regno
289 || INSN_CODE (c1
->insn
) < 0
290 || INSN_CODE (c1
->insn
) != INSN_CODE (c2
->insn
))
292 gcc_assert (c1
->nop
== c2
->nop
);
293 for (int i
= 0; i
< nops
; i
++)
294 if (i
!= c1
->nop
&& static_id1
->operand
[i
].type
== OP_IN
295 && *id1
->operand_loc
[i
] != *id2
->operand_loc
[i
])
300 /* Insert candidate CAND into the table if it is not there yet.
301 Return candidate which is in the table. */
303 insert_cand (cand_t cand
)
307 entry_ptr
= htab_find_slot (cand_table
, cand
, INSERT
);
308 if (*entry_ptr
== NULL
)
309 *entry_ptr
= (void *) cand
;
310 return (cand_t
) *entry_ptr
;
313 /* Free candidate CAND memory. */
315 free_cand (void *cand
)
320 /* Initiate the candidate table. */
322 initiate_cand_table (void)
324 cand_table
= htab_create (8000, cand_hash
, cand_eq_p
,
325 (htab_del
) free_cand
);
328 /* Finish the candidate table. */
330 finish_cand_table (void)
332 htab_delete (cand_table
);
337 /* Return true if X contains memory or some UNSPEC. We can not just
338 check insn operands as memory or unspec might be not an operand
339 itself but contain an operand. Insn with memory access is not
340 profitable for rematerialization. Rematerialization of UNSPEC
341 might result in wrong code generation as the UNPEC effect is
342 unknown (e.g. generating a label). */
344 bad_for_rematerialization_p (rtx x
)
350 if (MEM_P (x
) || GET_CODE (x
) == UNSPEC
|| GET_CODE (x
) == UNSPEC_VOLATILE
)
353 fmt
= GET_RTX_FORMAT (code
);
354 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
358 if (bad_for_rematerialization_p (XEXP (x
, i
)))
361 else if (fmt
[i
] == 'E')
363 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
364 if (bad_for_rematerialization_p (XVECEXP (x
, i
, j
)))
371 /* If INSN can not be used for rematerialization, return negative
372 value. If INSN can be considered as a candidate for
373 rematerialization, return value which is the operand number of the
374 pseudo for which the insn can be used for rematerialization. Here
375 we consider the insns without any memory, spilled pseudo (except
376 for the rematerialization pseudo), or dying or unused regs. */
378 operand_to_remat (rtx_insn
*insn
)
380 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
381 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
382 struct lra_insn_reg
*reg
, *found_reg
= NULL
;
384 /* Don't rematerialize insns which can change PC. */
385 if (JUMP_P (insn
) || CALL_P (insn
))
387 /* First find a pseudo which can be rematerialized. */
388 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
390 /* True FRAME_POINTER_NEEDED might be because we can not follow
391 changing sp offsets, e.g. alloca is used. If the insn contains
392 stack pointer in such case, we can not rematerialize it as we
393 can not know sp offset at a rematerialization place. */
394 if (reg
->regno
== STACK_POINTER_REGNUM
&& frame_pointer_needed
)
396 else if (reg
->type
== OP_OUT
&& ! reg
->subreg_p
397 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
399 /* We permits only one spilled reg. */
400 if (found_reg
!= NULL
)
404 /* IRA calculates conflicts separately for subregs of two words
405 pseudo. Even if the pseudo lives, e.g. one its subreg can be
406 used lately, another subreg hard register can be already used
407 for something else. In such case, it is not safe to
408 rematerialize the insn. */
409 if (reg
->regno
>= FIRST_PSEUDO_REGISTER
410 && bitmap_bit_p (&subreg_regs
, reg
->regno
))
413 if (found_reg
== NULL
)
415 if (found_reg
->regno
< FIRST_PSEUDO_REGISTER
)
417 if (bad_for_rematerialization_p (PATTERN (insn
)))
419 /* Check the other regs are not spilled. */
420 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
421 if (found_reg
== reg
)
423 else if (reg
->type
== OP_INOUT
)
425 else if (reg
->regno
>= FIRST_PSEUDO_REGISTER
426 && reg_renumber
[reg
->regno
] < 0)
427 /* Another spilled reg. */
429 else if (reg
->type
== OP_IN
)
431 if (find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
432 /* We don't want to make live ranges longer. */
434 /* Check that there is no output reg as the input one. */
435 for (struct lra_insn_reg
*reg2
= id
->regs
;
438 if (reg2
->type
== OP_OUT
&& reg
->regno
== reg2
->regno
)
440 if (reg
->regno
< FIRST_PSEUDO_REGISTER
)
441 for (struct lra_insn_reg
*reg2
= static_id
->hard_regs
;
444 if (reg2
->type
== OP_OUT
445 && reg
->regno
<= reg2
->regno
448 + hard_regno_nregs
[reg
->regno
][reg
->biggest_mode
])))
451 /* Find the rematerialization operand. */
452 int nop
= static_id
->n_operands
;
453 for (int i
= 0; i
< nop
; i
++)
454 if (REG_P (*id
->operand_loc
[i
])
455 && (int) REGNO (*id
->operand_loc
[i
]) == found_reg
->regno
)
460 /* Create candidate for INSN with rematerialization operand NOP and
461 REGNO. Insert the candidate into the table and set up the
462 corresponding INSN_TO_CAND element. */
464 create_cand (rtx_insn
*insn
, int nop
, int regno
)
466 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
467 rtx reg
= *id
->operand_loc
[nop
];
468 gcc_assert (REG_P (reg
));
469 int op_regno
= REGNO (reg
);
470 gcc_assert (op_regno
>= FIRST_PSEUDO_REGISTER
);
471 cand_t cand
= XNEW (struct cand
);
475 cand
->reload_regno
= op_regno
== regno
? -1 : op_regno
;
476 gcc_assert (cand
->regno
>= 0);
477 cand_t cand_in_table
= insert_cand (cand
);
478 insn_to_cand
[INSN_UID (insn
)] = cand_in_table
;
479 if (cand
!= cand_in_table
)
484 cand
->index
= all_cands
.length ();
485 all_cands
.safe_push (cand
);
486 cand
->next_regno_cand
= regno_cands
[cand
->regno
];
487 regno_cands
[cand
->regno
] = cand
;
491 /* Create rematerialization candidates (inserting them into the
497 struct potential_cand
502 struct potential_cand
*regno_potential_cand
;
504 /* Create candidates. */
505 regno_potential_cand
= XCNEWVEC (struct potential_cand
, max_reg_num ());
506 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
510 int src_regno
, dst_regno
;
512 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
513 int nop
= operand_to_remat (insn
);
516 if ((set
= single_set (insn
)) != NULL
517 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
))
518 && ((src_regno
= REGNO (SET_SRC (set
)))
519 >= lra_constraint_new_regno_start
)
520 && (dst_regno
= REGNO (SET_DEST (set
))) >= FIRST_PSEUDO_REGISTER
521 && reg_renumber
[dst_regno
] < 0
522 && (insn2
= regno_potential_cand
[src_regno
].insn
) != NULL
523 && BLOCK_FOR_INSN (insn2
) == BLOCK_FOR_INSN (insn
))
524 /* It is an output reload insn after insn can be
525 rematerialized (potential candidate). */
526 create_cand (insn2
, regno_potential_cand
[src_regno
].nop
, dst_regno
);
529 gcc_assert (REG_P (*id
->operand_loc
[nop
]));
530 regno
= REGNO (*id
->operand_loc
[nop
]);
531 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
532 if (reg_renumber
[regno
] < 0)
533 create_cand (insn
, nop
, regno
);
536 regno_potential_cand
[regno
].insn
= insn
;
537 regno_potential_cand
[regno
].nop
= nop
;
542 for (struct lra_insn_reg
*reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
543 if (reg
->type
!= OP_IN
&& reg
->regno
!= regno
544 && reg
->regno
>= FIRST_PSEUDO_REGISTER
)
545 regno_potential_cand
[reg
->regno
].insn
= NULL
;
547 cands_num
= all_cands
.length ();
548 free (regno_potential_cand
);
553 /* Create and initialize BB data. */
555 create_remat_bb_data (void)
558 remat_bb_data_t bb_info
;
560 remat_bb_data
= XNEWVEC (struct remat_bb_data
,
561 last_basic_block_for_fn (cfun
));
562 FOR_ALL_BB_FN (bb
, cfun
)
564 gcc_checking_assert (bb
->index
>= 0
565 && bb
->index
< last_basic_block_for_fn (cfun
));
566 bb_info
= get_remat_bb_data (bb
);
568 bitmap_initialize (&bb_info
->changed_regs
, ®_obstack
);
569 bitmap_initialize (&bb_info
->dead_regs
, ®_obstack
);
570 bitmap_initialize (&bb_info
->gen_cands
, ®_obstack
);
571 bitmap_initialize (&bb_info
->livein_cands
, ®_obstack
);
572 bitmap_initialize (&bb_info
->pavin_cands
, ®_obstack
);
573 bitmap_initialize (&bb_info
->pavout_cands
, ®_obstack
);
574 bitmap_initialize (&bb_info
->avin_cands
, ®_obstack
);
575 bitmap_initialize (&bb_info
->avout_cands
, ®_obstack
);
579 /* Dump all candidates to DUMP_FILE. */
581 dump_cands (FILE *dump_file
)
586 fprintf (dump_file
, "\nCands:\n");
587 for (i
= 0; i
< (int) cands_num
; i
++)
590 fprintf (dump_file
, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
591 i
, cand
->nop
, cand
->regno
, cand
->reload_regno
);
592 print_inline_rtx (dump_file
, cand
->insn
, 6);
593 fprintf (dump_file
, "\n");
597 /* Dump all candidates and BB data. */
599 dump_candidates_and_remat_bb_data (void)
603 if (lra_dump_file
== NULL
)
605 dump_cands (lra_dump_file
);
606 FOR_EACH_BB_FN (bb
, cfun
)
608 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
610 fprintf (lra_dump_file
, " register live in:");
611 dump_regset (df_get_live_in (bb
), lra_dump_file
);
612 putc ('\n', lra_dump_file
);
614 fprintf (lra_dump_file
, " register live out:");
615 dump_regset (df_get_live_out (bb
), lra_dump_file
);
616 putc ('\n', lra_dump_file
);
617 /* Changed/dead regs: */
618 fprintf (lra_dump_file
, " changed regs:");
619 dump_regset (&get_remat_bb_data (bb
)->changed_regs
, lra_dump_file
);
620 putc ('\n', lra_dump_file
);
621 fprintf (lra_dump_file
, " dead regs:");
622 dump_regset (&get_remat_bb_data (bb
)->dead_regs
, lra_dump_file
);
623 putc ('\n', lra_dump_file
);
624 lra_dump_bitmap_with_title ("cands generated in BB",
625 &get_remat_bb_data (bb
)->gen_cands
, bb
->index
);
626 lra_dump_bitmap_with_title ("livein cands in BB",
627 &get_remat_bb_data (bb
)->livein_cands
, bb
->index
);
628 lra_dump_bitmap_with_title ("pavin cands in BB",
629 &get_remat_bb_data (bb
)->pavin_cands
, bb
->index
);
630 lra_dump_bitmap_with_title ("pavout cands in BB",
631 &get_remat_bb_data (bb
)->pavout_cands
, bb
->index
);
632 lra_dump_bitmap_with_title ("avin cands in BB",
633 &get_remat_bb_data (bb
)->avin_cands
, bb
->index
);
634 lra_dump_bitmap_with_title ("avout cands in BB",
635 &get_remat_bb_data (bb
)->avout_cands
, bb
->index
);
637 fprintf (lra_dump_file
, "subreg regs:");
638 dump_regset (&subreg_regs
, lra_dump_file
);
639 putc ('\n', lra_dump_file
);
642 /* Free all BB data. */
644 finish_remat_bb_data (void)
648 FOR_EACH_BB_FN (bb
, cfun
)
650 bitmap_clear (&get_remat_bb_data (bb
)->avout_cands
);
651 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
652 bitmap_clear (&get_remat_bb_data (bb
)->pavout_cands
);
653 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
654 bitmap_clear (&get_remat_bb_data (bb
)->livein_cands
);
655 bitmap_clear (&get_remat_bb_data (bb
)->gen_cands
);
656 bitmap_clear (&get_remat_bb_data (bb
)->dead_regs
);
657 bitmap_clear (&get_remat_bb_data (bb
)->changed_regs
);
659 free (remat_bb_data
);
664 /* Update changed_regs, dead_regs, subreg_regs of BB from INSN. */
666 set_bb_regs (basic_block bb
, rtx_insn
*insn
)
668 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
669 remat_bb_data_t bb_info
= get_remat_bb_data (bb
);
670 struct lra_insn_reg
*reg
;
672 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
674 unsigned regno
= reg
->regno
;
675 if (reg
->type
!= OP_IN
)
676 bitmap_set_bit (&bb_info
->changed_regs
, regno
);
677 else if (find_regno_note (insn
, REG_DEAD
, regno
) != NULL
)
678 bitmap_set_bit (&bb_info
->dead_regs
, regno
);
679 if (regno
>= FIRST_PSEUDO_REGISTER
&& reg
->subreg_p
)
680 bitmap_set_bit (&subreg_regs
, regno
);
683 for (int i
= 0; i
< call_used_regs_arr_len
; i
++)
684 bitmap_set_bit (&get_remat_bb_data (bb
)->dead_regs
,
685 call_used_regs_arr
[i
]);
688 /* Calculate changed_regs and dead_regs for each BB. */
690 calculate_local_reg_remat_bb_data (void)
695 FOR_EACH_BB_FN (bb
, cfun
)
696 FOR_BB_INSNS (bb
, insn
)
697 if (NONDEBUG_INSN_P (insn
))
698 set_bb_regs (bb
, insn
);
703 /* Return true if REGNO is an input operand of INSN. */
705 input_regno_present_p (rtx_insn
*insn
, int regno
)
708 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
709 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
710 struct lra_insn_reg
*reg
;
712 for (iter
= 0; iter
< 2; iter
++)
713 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
716 if (reg
->type
== OP_IN
&& reg
->regno
== regno
)
721 /* Return true if a call used register is an input operand of INSN. */
723 call_used_input_regno_present_p (rtx_insn
*insn
)
726 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
727 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
728 struct lra_insn_reg
*reg
;
730 for (iter
= 0; iter
< 2; iter
++)
731 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
734 if (reg
->type
== OP_IN
&& reg
->regno
<= FIRST_PSEUDO_REGISTER
735 && TEST_HARD_REG_BIT (call_used_reg_set
, reg
->regno
))
740 /* Calculate livein_cands for each BB. */
742 calculate_livein_cands (void)
746 FOR_EACH_BB_FN (bb
, cfun
)
748 bitmap livein_regs
= df_get_live_in (bb
);
749 bitmap livein_cands
= &get_remat_bb_data (bb
)->livein_cands
;
750 for (unsigned int i
= 0; i
< cands_num
; i
++)
752 cand_t cand
= all_cands
[i
];
753 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
754 struct lra_insn_reg
*reg
;
756 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
757 if (reg
->type
== OP_IN
&& ! bitmap_bit_p (livein_regs
, reg
->regno
))
760 bitmap_set_bit (livein_cands
, i
);
765 /* Calculate gen_cands for each BB. */
767 calculate_gen_cands (void)
771 bitmap_head gen_insns
;
774 bitmap_initialize (&gen_insns
, ®_obstack
);
775 FOR_EACH_BB_FN (bb
, cfun
)
777 gen_cands
= &get_remat_bb_data (bb
)->gen_cands
;
778 bitmap_clear (&gen_insns
);
779 FOR_BB_INSNS (bb
, insn
)
782 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
783 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
784 struct lra_insn_reg
*reg
;
790 int src_regno
= -1, dst_regno
= -1;
792 if ((set
= single_set (insn
)) != NULL
793 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
795 src_regno
= REGNO (SET_SRC (set
));
796 dst_regno
= REGNO (SET_DEST (set
));
799 /* Update gen_cands: */
800 bitmap_clear (&temp_bitmap
);
801 for (iter
= 0; iter
< 2; iter
++)
802 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
805 if (reg
->type
!= OP_IN
806 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
807 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
809 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
811 cand
= insn_to_cand
[INSN_UID (insn2
)];
812 gcc_assert (cand
!= NULL
);
813 /* Ignore the reload insn. */
814 if (src_regno
== cand
->reload_regno
815 && dst_regno
== cand
->regno
)
817 if (cand
->regno
== reg
->regno
818 || input_regno_present_p (insn2
, reg
->regno
))
820 bitmap_clear_bit (gen_cands
, cand
->index
);
821 bitmap_set_bit (&temp_bitmap
, uid
);
826 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
828 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
830 cand
= insn_to_cand
[INSN_UID (insn2
)];
831 gcc_assert (cand
!= NULL
);
832 if (call_used_input_regno_present_p (insn2
))
834 bitmap_clear_bit (gen_cands
, cand
->index
);
835 bitmap_set_bit (&temp_bitmap
, uid
);
838 bitmap_and_compl_into (&gen_insns
, &temp_bitmap
);
840 cand
= insn_to_cand
[INSN_UID (insn
)];
843 bitmap_set_bit (gen_cands
, cand
->index
);
844 bitmap_set_bit (&gen_insns
, INSN_UID (insn
));
848 bitmap_clear (&gen_insns
);
853 /* The common transfer function used by the DF equation solver to
854 propagate (partial) availability info BB_IN to BB_OUT through block
855 with BB_INDEX according to the following equation:
857 bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
860 cand_trans_fun (int bb_index
, bitmap bb_in
, bitmap bb_out
)
862 remat_bb_data_t bb_info
;
863 bitmap bb_livein
, bb_changed_regs
, bb_dead_regs
;
867 bb_info
= get_remat_bb_data_by_index (bb_index
);
868 bb_livein
= &bb_info
->livein_cands
;
869 bb_changed_regs
= &bb_info
->changed_regs
;
870 bb_dead_regs
= &bb_info
->dead_regs
;
871 /* Calculate killed avin cands -- cands whose regs are changed or
872 becoming dead in the BB. We calculate it here as we hope that
873 repeated calculations are compensated by smaller size of BB_IN in
874 comparison with all candidates number. */
875 bitmap_clear (&temp_bitmap
);
876 EXECUTE_IF_SET_IN_BITMAP (bb_in
, 0, cid
, bi
)
878 cand_t cand
= all_cands
[cid
];
879 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
880 struct lra_insn_reg
*reg
;
882 if (! bitmap_bit_p (bb_livein
, cid
))
884 bitmap_set_bit (&temp_bitmap
, cid
);
887 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
888 /* Ignore all outputs which are not the regno for
889 rematerialization. */
890 if (reg
->type
== OP_OUT
&& reg
->regno
!= cand
->regno
)
892 else if (bitmap_bit_p (bb_changed_regs
, reg
->regno
)
893 || bitmap_bit_p (bb_dead_regs
, reg
->regno
))
895 bitmap_set_bit (&temp_bitmap
, cid
);
898 /* Check regno for rematerialization. */
899 if (bitmap_bit_p (bb_changed_regs
, cand
->regno
)
900 || bitmap_bit_p (bb_dead_regs
, cand
->regno
))
901 bitmap_set_bit (&temp_bitmap
, cid
);
903 return bitmap_ior_and_compl (bb_out
,
904 &bb_info
->gen_cands
, bb_in
, &temp_bitmap
);
909 /* The transfer function used by the DF equation solver to propagate
910 partial candidate availability info through block with BB_INDEX
911 according to the following equation:
913 bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
916 cand_pav_trans_fun (int bb_index
)
918 remat_bb_data_t bb_info
;
920 bb_info
= get_remat_bb_data_by_index (bb_index
);
921 return cand_trans_fun (bb_index
, &bb_info
->pavin_cands
,
922 &bb_info
->pavout_cands
);
925 /* The confluence function used by the DF equation solver to set up
926 cand_pav info for a block BB without predecessor. */
928 cand_pav_con_fun_0 (basic_block bb
)
930 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
933 /* The confluence function used by the DF equation solver to propagate
934 partial candidate availability info from predecessor to successor
935 on edge E (pred->bb) according to the following equation:
937 bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
940 cand_pav_con_fun_n (edge e
)
942 basic_block pred
= e
->src
;
943 basic_block bb
= e
->dest
;
944 remat_bb_data_t bb_info
;
945 bitmap bb_pavin
, pred_pavout
;
947 bb_info
= get_remat_bb_data (bb
);
948 bb_pavin
= &bb_info
->pavin_cands
;
949 pred_pavout
= &get_remat_bb_data (pred
)->pavout_cands
;
950 return bitmap_ior_into (bb_pavin
, pred_pavout
);
955 /* The transfer function used by the DF equation solver to propagate
956 candidate availability info through block with BB_INDEX according
957 to the following equation:
959 bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
962 cand_av_trans_fun (int bb_index
)
964 remat_bb_data_t bb_info
;
966 bb_info
= get_remat_bb_data_by_index (bb_index
);
967 return cand_trans_fun (bb_index
, &bb_info
->avin_cands
,
968 &bb_info
->avout_cands
);
971 /* The confluence function used by the DF equation solver to set up
972 cand_av info for a block BB without predecessor. */
974 cand_av_con_fun_0 (basic_block bb
)
976 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
979 /* The confluence function used by the DF equation solver to propagate
980 cand_av info from predecessor to successor on edge E (pred->bb)
981 according to the following equation:
983 bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
986 cand_av_con_fun_n (edge e
)
988 basic_block pred
= e
->src
;
989 basic_block bb
= e
->dest
;
990 remat_bb_data_t bb_info
;
991 bitmap bb_avin
, pred_avout
;
993 bb_info
= get_remat_bb_data (bb
);
994 bb_avin
= &bb_info
->avin_cands
;
995 pred_avout
= &get_remat_bb_data (pred
)->avout_cands
;
996 return bitmap_and_into (bb_avin
, pred_avout
);
999 /* Calculate available candidates for each BB. */
1001 calculate_global_remat_bb_data (void)
1006 (DF_FORWARD
, NULL
, cand_pav_con_fun_0
, cand_pav_con_fun_n
,
1007 cand_pav_trans_fun
, &all_blocks
,
1008 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
1009 /* Initialize avin by pavin. */
1010 FOR_EACH_BB_FN (bb
, cfun
)
1011 bitmap_copy (&get_remat_bb_data (bb
)->avin_cands
,
1012 &get_remat_bb_data (bb
)->pavin_cands
);
1014 (DF_FORWARD
, NULL
, cand_av_con_fun_0
, cand_av_con_fun_n
,
1015 cand_av_trans_fun
, &all_blocks
,
1016 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
1021 /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
1023 change_sp_offset (rtx_insn
*insns
, HOST_WIDE_INT sp_offset
)
1025 for (rtx_insn
*insn
= insns
; insn
!= NULL
; insn
= NEXT_INSN (insn
))
1026 eliminate_regs_in_insn (insn
, false, false, sp_offset
);
1029 /* Return start hard register of REG (can be a hard or a pseudo reg)
1030 or -1 (if it is a spilled pseudo). Return number of hard registers
1031 occupied by REG through parameter NREGS if the start hard reg is
1034 get_hard_regs (struct lra_insn_reg
*reg
, int &nregs
)
1036 int regno
= reg
->regno
;
1037 int hard_regno
= regno
< FIRST_PSEUDO_REGISTER
? regno
: reg_renumber
[regno
];
1039 if (hard_regno
>= 0)
1040 nregs
= hard_regno_nregs
[hard_regno
][reg
->biggest_mode
];
1044 /* Make copy of and register scratch pseudos in rematerialized insn
1047 update_scratch_ops (rtx_insn
*remat_insn
)
1049 lra_insn_recog_data_t id
= lra_get_insn_recog_data (remat_insn
);
1050 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1051 for (int i
= 0; i
< static_id
->n_operands
; i
++)
1053 rtx
*loc
= id
->operand_loc
[i
];
1056 int regno
= REGNO (*loc
);
1057 if (! lra_former_scratch_p (regno
))
1059 *loc
= lra_create_new_reg (GET_MODE (*loc
), *loc
,
1060 lra_get_allocno_class (regno
),
1061 "scratch pseudo copy");
1062 lra_register_new_scratch_op (remat_insn
, i
);
1067 /* Insert rematerialization insns using the data-flow data calculated
1074 bitmap_head avail_cands
;
1075 bool changed_p
= false;
1076 /* Living hard regs and hard registers of living pseudos. */
1077 HARD_REG_SET live_hard_regs
;
1079 bitmap_initialize (&avail_cands
, ®_obstack
);
1080 FOR_EACH_BB_FN (bb
, cfun
)
1082 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_out (bb
));
1083 bitmap_and (&avail_cands
, &get_remat_bb_data (bb
)->avin_cands
,
1084 &get_remat_bb_data (bb
)->livein_cands
);
1085 FOR_BB_INSNS (bb
, insn
)
1087 if (!NONDEBUG_INSN_P (insn
))
1090 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
1091 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1092 struct lra_insn_reg
*reg
;
1098 int src_regno
= -1, dst_regno
= -1;
1100 if ((set
= single_set (insn
)) != NULL
1101 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
1103 src_regno
= REGNO (SET_SRC (set
));
1104 dst_regno
= REGNO (SET_DEST (set
));
1108 /* Check possibility of rematerialization (hard reg or
1109 unpsilled pseudo <- spilled pseudo): */
1110 if (dst_regno
>= 0 && src_regno
>= FIRST_PSEUDO_REGISTER
1111 && reg_renumber
[src_regno
] < 0
1112 && (dst_regno
< FIRST_PSEUDO_REGISTER
1113 || reg_renumber
[dst_regno
] >= 0))
1115 for (cand
= regno_cands
[src_regno
];
1117 cand
= cand
->next_regno_cand
)
1118 if (bitmap_bit_p (&avail_cands
, cand
->index
))
1121 int i
, hard_regno
, nregs
;
1122 rtx_insn
*remat_insn
= NULL
;
1123 HOST_WIDE_INT cand_sp_offset
= 0;
1126 lra_insn_recog_data_t cand_id
1127 = lra_get_insn_recog_data (cand
->insn
);
1128 struct lra_static_insn_data
*static_cand_id
1129 = cand_id
->insn_static_data
;
1130 rtx saved_op
= *cand_id
->operand_loc
[cand
->nop
];
1132 /* Check clobbers do not kill something living. */
1133 gcc_assert (REG_P (saved_op
));
1134 int ignore_regno
= REGNO (saved_op
);
1136 for (reg
= cand_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1137 if (reg
->type
!= OP_IN
&& reg
->regno
!= ignore_regno
)
1139 hard_regno
= get_hard_regs (reg
, nregs
);
1140 gcc_assert (hard_regno
>= 0);
1141 for (i
= 0; i
< nregs
; i
++)
1142 if (TEST_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
))
1150 for (reg
= static_cand_id
->hard_regs
;
1153 if (reg
->type
!= OP_IN
1154 && TEST_HARD_REG_BIT (live_hard_regs
, reg
->regno
))
1160 *cand_id
->operand_loc
[cand
->nop
] = SET_DEST (set
);
1161 lra_update_insn_regno_info (cand
->insn
);
1162 bool ok_p
= lra_constrain_insn (cand
->insn
);
1165 rtx remat_pat
= copy_insn (PATTERN (cand
->insn
));
1168 emit_insn (remat_pat
);
1169 remat_insn
= get_insns ();
1171 if (recog_memoized (remat_insn
) < 0)
1173 cand_sp_offset
= cand_id
->sp_offset
;
1175 *cand_id
->operand_loc
[cand
->nop
] = saved_op
;
1176 lra_update_insn_regno_info (cand
->insn
);
1180 bitmap_clear (&temp_bitmap
);
1181 /* Update avail_cands (see analogous code for
1182 calculate_gen_cands). */
1183 for (iter
= 0; iter
< 2; iter
++)
1184 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
1187 if (reg
->type
!= OP_IN
1188 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1189 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1191 cand
= all_cands
[cid
];
1193 /* Ignore the reload insn. */
1194 if (src_regno
== cand
->reload_regno
1195 && dst_regno
== cand
->regno
)
1197 if (cand
->regno
== reg
->regno
1198 || input_regno_present_p (cand
->insn
, reg
->regno
))
1199 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1203 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1205 cand
= all_cands
[cid
];
1207 if (call_used_input_regno_present_p (cand
->insn
))
1208 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1211 bitmap_and_compl_into (&avail_cands
, &temp_bitmap
);
1212 if ((cand
= insn_to_cand
[INSN_UID (insn
)]) != NULL
)
1213 bitmap_set_bit (&avail_cands
, cand
->index
);
1215 if (remat_insn
!= NULL
)
1217 HOST_WIDE_INT sp_offset_change
= cand_sp_offset
- id
->sp_offset
;
1218 if (sp_offset_change
!= 0)
1219 change_sp_offset (remat_insn
, sp_offset_change
);
1220 update_scratch_ops (remat_insn
);
1221 lra_process_new_insns (insn
, remat_insn
, NULL
,
1222 "Inserting rematerialization insn");
1223 lra_set_insn_deleted (insn
);
1228 /* Update live hard regs: */
1229 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1230 if (reg
->type
== OP_IN
1231 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1233 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1235 for (i
= 0; i
< nregs
; i
++)
1236 CLEAR_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1238 /* Process also hard regs (e.g. CC register) which are part
1239 of insn definition. */
1240 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1241 if (reg
->type
== OP_IN
1242 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1243 CLEAR_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1244 /* Inputs have been processed, now process outputs. */
1245 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1246 if (reg
->type
!= OP_IN
1247 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1249 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1251 for (i
= 0; i
< nregs
; i
++)
1252 SET_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1254 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1255 if (reg
->type
!= OP_IN
1256 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1257 SET_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1260 bitmap_clear (&avail_cands
);
1266 /* Current number of rematerialization iteration. */
1267 int lra_rematerialization_iter
;
1269 /* Entry point of the rematerialization sub-pass. Return true if we
1270 did any rematerialization. */
1276 int max_regno
= max_reg_num ();
1278 if (! flag_lra_remat
)
1280 lra_rematerialization_iter
++;
1281 if (lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
1283 if (lra_dump_file
!= NULL
)
1284 fprintf (lra_dump_file
,
1285 "\n******** Rematerialization #%d: ********\n\n",
1286 lra_rematerialization_iter
);
1287 timevar_push (TV_LRA_REMAT
);
1288 insn_to_cand
= XCNEWVEC (cand_t
, get_max_uid ());
1289 regno_cands
= XCNEWVEC (cand_t
, max_regno
);
1290 all_cands
.create (8000);
1291 call_used_regs_arr_len
= 0;
1292 for (int i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1293 if (call_used_regs
[i
])
1294 call_used_regs_arr
[call_used_regs_arr_len
++] = i
;
1295 initiate_cand_table ();
1296 create_remat_bb_data ();
1297 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1298 bitmap_initialize (&subreg_regs
, ®_obstack
);
1299 calculate_local_reg_remat_bb_data ();
1301 calculate_livein_cands ();
1302 calculate_gen_cands ();
1303 bitmap_initialize (&all_blocks
, ®_obstack
);
1304 FOR_ALL_BB_FN (bb
, cfun
)
1305 bitmap_set_bit (&all_blocks
, bb
->index
);
1306 calculate_global_remat_bb_data ();
1307 dump_candidates_and_remat_bb_data ();
1308 result
= do_remat ();
1309 all_cands
.release ();
1310 bitmap_clear (&temp_bitmap
);
1311 bitmap_clear (&subreg_regs
);
1312 finish_remat_bb_data ();
1313 finish_cand_table ();
1314 bitmap_clear (&all_blocks
);
1316 free (insn_to_cand
);
1317 timevar_pop (TV_LRA_REMAT
);