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"
76 #include "statistics.h"
77 #include "double-int.h"
79 #include "fixed-value.h"
93 #include "dominance.h"
95 #include "basic-block.h"
99 #include "sparseset.h"
103 /* Number of candidates for rematerialization. */
104 static unsigned int cands_num
;
106 /* The following is used for representation of call_used_reg_set in
107 form array whose elements are hard register numbers with nonzero bit
108 in CALL_USED_REG_SET. */
109 static int call_used_regs_arr_len
;
110 static int call_used_regs_arr
[FIRST_PSEUDO_REGISTER
];
112 /* Bitmap used for different calculations. */
113 static bitmap_head temp_bitmap
;
115 /* Registers accessed via subreg_p. */
116 static bitmap_head subreg_regs
;
118 typedef struct cand
*cand_t
;
119 typedef const struct cand
*const_cand_t
;
121 /* Insn candidates for rematerialization. The candidate insn should
122 have the following properies:
123 o no any memory (as access to memory is non-profitable)
124 o no INOUT regs (it means no non-paradoxical subreg of output reg)
125 o one output spilled pseudo (or reload pseudo of a spilled pseudo)
126 o all other pseudos are with assigned hard regs. */
129 /* Index of the candidates in all_cands. */
131 /* The candidate insn. */
133 /* Insn pseudo regno for rematerialization. */
135 /* Non-negative if a reload pseudo is in the insn instead of the
136 pseudo for rematerialization. */
138 /* Number of the operand containing the regno or its reload
141 /* Next candidate for the same regno. */
142 cand_t next_regno_cand
;
145 /* Vector containing all candidates. */
146 static vec
<cand_t
> all_cands
;
147 /* Map: insn -> candidate representing it. It is null if the insn can
148 not be used for rematerialization. */
149 static cand_t
*insn_to_cand
;
150 /* A secondary map, for candidates that involve two insns, where the
151 second one makes the equivalence. The candidate must not be used
152 before seeing this activation insn. */
153 static cand_t
*insn_to_cand_activation
;
155 /* Map regno -> candidates can be used for the regno
156 rematerialization. */
157 static cand_t
*regno_cands
;
159 /* Data about basic blocks used for the rematerialization
163 /* Basic block about which the below data are. */
165 /* Registers changed in the basic block: */
166 bitmap_head changed_regs
;
167 /* Registers becoming dead in the BB. */
168 bitmap_head dead_regs
;
169 /* Cands present in the BB whose in/out regs are not changed after
170 the cands occurence and are not dead (except the reload
172 bitmap_head gen_cands
;
173 bitmap_head livein_cands
; /* cands whose inputs live at the BB start. */
174 bitmap_head pavin_cands
; /* cands partially available at BB entry. */
175 bitmap_head pavout_cands
; /* cands partially available at BB exit. */
176 bitmap_head avin_cands
; /* cands available at the entry of the BB. */
177 bitmap_head avout_cands
; /* cands available at the exit of the BB. */
180 /* Array for all BB data. Indexed by the corresponding BB index. */
181 typedef struct remat_bb_data
*remat_bb_data_t
;
183 /* Basic blocks for data flow problems -- all bocks except the special
185 static bitmap_head all_blocks
;
187 /* All basic block data are referred through the following array. */
188 static remat_bb_data_t remat_bb_data
;
190 /* Two small functions for access to the bb data. */
191 static inline remat_bb_data_t
192 get_remat_bb_data (basic_block bb
)
194 return &remat_bb_data
[(bb
)->index
];
197 static inline remat_bb_data_t
198 get_remat_bb_data_by_index (int index
)
200 return &remat_bb_data
[index
];
205 /* Recursive hash function for RTL X. */
218 val
+= (int) code
+ 4095;
220 /* Some RTL can be compared nonrecursively. */
224 return val
+ REGNO (x
);
227 return iterative_hash_object (XEXP (x
, 0), val
);
230 return iterative_hash_object (XSTR (x
, 0), val
);
242 /* Hash the elements. */
243 fmt
= GET_RTX_FORMAT (code
);
244 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
259 val
+= XVECLEN (x
, i
);
261 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
262 val
+= rtx_hash (XVECEXP (x
, i
, j
));
266 val
+= rtx_hash (XEXP (x
, i
));
271 val
+= htab_hash_string (XSTR (x
, i
));
279 /* It is believed that rtx's at this level will never
280 contain anything but integers and other rtx's, except for
281 within LABEL_REFs and SYMBOL_REFs. */
291 /* Hash table for the candidates. Different insns (e.g. structurally
292 the same insns or even insns with different unused output regs) can
293 be represented by the same candidate in the table. */
294 static htab_t cand_table
;
296 /* Hash function for candidate CAND. */
298 cand_hash (const void *cand
)
300 const_cand_t c
= (const_cand_t
) cand
;
301 lra_insn_recog_data_t id
= lra_get_insn_recog_data (c
->insn
);
302 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
303 int nops
= static_id
->n_operands
;
306 for (int i
= 0; i
< nops
; i
++)
308 hash
= iterative_hash_object (c
->regno
, hash
);
309 else if (static_id
->operand
[i
].type
== OP_IN
)
310 hash
= iterative_hash_object (*id
->operand_loc
[i
], hash
);
314 /* Equal function for candidates CAND1 and CAND2. They are equal if
315 the corresponding candidate insns have the same code, the same
316 regno for rematerialization, the same input operands. */
318 cand_eq_p (const void *cand1
, const void *cand2
)
320 const_cand_t c1
= (const_cand_t
) cand1
;
321 const_cand_t c2
= (const_cand_t
) cand2
;
322 lra_insn_recog_data_t id1
= lra_get_insn_recog_data (c1
->insn
);
323 lra_insn_recog_data_t id2
= lra_get_insn_recog_data (c2
->insn
);
324 struct lra_static_insn_data
*static_id1
= id1
->insn_static_data
;
325 int nops
= static_id1
->n_operands
;
327 if (c1
->regno
!= c2
->regno
328 || INSN_CODE (c1
->insn
) < 0
329 || INSN_CODE (c1
->insn
) != INSN_CODE (c2
->insn
))
331 gcc_assert (c1
->nop
== c2
->nop
);
332 for (int i
= 0; i
< nops
; i
++)
333 if (i
!= c1
->nop
&& static_id1
->operand
[i
].type
== OP_IN
334 && *id1
->operand_loc
[i
] != *id2
->operand_loc
[i
])
339 /* Insert candidate CAND into the table if it is not there yet.
340 Return candidate which is in the table. */
342 insert_cand (cand_t cand
)
346 entry_ptr
= htab_find_slot (cand_table
, cand
, INSERT
);
347 if (*entry_ptr
== NULL
)
348 *entry_ptr
= (void *) cand
;
349 return (cand_t
) *entry_ptr
;
352 /* Free candidate CAND memory. */
354 free_cand (void *cand
)
359 /* Initiate the candidate table. */
361 initiate_cand_table (void)
363 cand_table
= htab_create (8000, cand_hash
, cand_eq_p
,
364 (htab_del
) free_cand
);
367 /* Finish the candidate table. */
369 finish_cand_table (void)
371 htab_delete (cand_table
);
376 /* Return true if X contains memory or some UNSPEC. We can not just
377 check insn operands as memory or unspec might be not an operand
378 itself but contain an operand. Insn with memory access is not
379 profitable for rematerialization. Rematerialization of UNSPEC
380 might result in wrong code generation as the UNPEC effect is
381 unknown (e.g. generating a label). */
383 bad_for_rematerialization_p (rtx x
)
389 if (MEM_P (x
) || GET_CODE (x
) == UNSPEC
|| GET_CODE (x
) == UNSPEC_VOLATILE
)
392 fmt
= GET_RTX_FORMAT (code
);
393 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
397 if (bad_for_rematerialization_p (XEXP (x
, i
)))
400 else if (fmt
[i
] == 'E')
402 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
403 if (bad_for_rematerialization_p (XVECEXP (x
, i
, j
)))
410 /* If INSN can not be used for rematerialization, return negative
411 value. If INSN can be considered as a candidate for
412 rematerialization, return value which is the operand number of the
413 pseudo for which the insn can be used for rematerialization. Here
414 we consider the insns without any memory, spilled pseudo (except
415 for the rematerialization pseudo), or dying or unused regs. */
417 operand_to_remat (rtx_insn
*insn
)
419 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
420 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
421 struct lra_insn_reg
*reg
, *found_reg
= NULL
;
423 /* Don't rematerialize insns which can change PC. */
424 if (JUMP_P (insn
) || CALL_P (insn
))
426 /* First find a pseudo which can be rematerialized. */
427 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
429 /* True FRAME_POINTER_NEEDED might be because we can not follow
430 changing sp offsets, e.g. alloca is used. If the insn contains
431 stack pointer in such case, we can not rematerialize it as we
432 can not know sp offset at a rematerialization place. */
433 if (reg
->regno
== STACK_POINTER_REGNUM
&& frame_pointer_needed
)
435 else if (reg
->type
== OP_OUT
&& ! reg
->subreg_p
436 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
438 /* We permits only one spilled reg. */
439 if (found_reg
!= NULL
)
443 /* IRA calculates conflicts separately for subregs of two words
444 pseudo. Even if the pseudo lives, e.g. one its subreg can be
445 used lately, another subreg hard register can be already used
446 for something else. In such case, it is not safe to
447 rematerialize the insn. */
448 if (reg
->regno
>= FIRST_PSEUDO_REGISTER
449 && bitmap_bit_p (&subreg_regs
, reg
->regno
))
452 if (found_reg
== NULL
)
454 if (found_reg
->regno
< FIRST_PSEUDO_REGISTER
)
456 if (bad_for_rematerialization_p (PATTERN (insn
)))
458 /* Check the other regs are not spilled. */
459 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
460 if (found_reg
== reg
)
462 else if (reg
->type
== OP_INOUT
)
464 else if (reg
->regno
>= FIRST_PSEUDO_REGISTER
465 && reg_renumber
[reg
->regno
] < 0)
466 /* Another spilled reg. */
468 else if (reg
->type
== OP_IN
)
470 if (find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
471 /* We don't want to make live ranges longer. */
473 /* Check that there is no output reg as the input one. */
474 for (struct lra_insn_reg
*reg2
= id
->regs
;
477 if (reg2
->type
== OP_OUT
&& reg
->regno
== reg2
->regno
)
479 if (reg
->regno
< FIRST_PSEUDO_REGISTER
)
480 for (struct lra_insn_reg
*reg2
= static_id
->hard_regs
;
483 if (reg2
->type
== OP_OUT
484 && reg
->regno
<= reg2
->regno
487 + hard_regno_nregs
[reg
->regno
][reg
->biggest_mode
])))
490 /* Find the rematerialization operand. */
491 int nop
= static_id
->n_operands
;
492 for (int i
= 0; i
< nop
; i
++)
493 if (REG_P (*id
->operand_loc
[i
])
494 && (int) REGNO (*id
->operand_loc
[i
]) == found_reg
->regno
)
499 /* Create candidate for INSN with rematerialization operand NOP and
500 REGNO. Insert the candidate into the table and set up the
501 corresponding INSN_TO_CAND element. */
503 create_cand (rtx_insn
*insn
, int nop
, int regno
, rtx_insn
*activation
= NULL
)
505 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
506 rtx reg
= *id
->operand_loc
[nop
];
507 gcc_assert (REG_P (reg
));
508 int op_regno
= REGNO (reg
);
509 gcc_assert (op_regno
>= FIRST_PSEUDO_REGISTER
);
510 cand_t cand
= XNEW (struct cand
);
514 cand
->reload_regno
= op_regno
== regno
? -1 : op_regno
;
515 gcc_assert (cand
->regno
>= 0);
516 cand_t cand_in_table
= insert_cand (cand
);
517 insn_to_cand
[INSN_UID (insn
)] = cand_in_table
;
518 if (cand
!= cand_in_table
)
523 cand
->index
= all_cands
.length ();
524 all_cands
.safe_push (cand
);
525 cand
->next_regno_cand
= regno_cands
[cand
->regno
];
526 regno_cands
[cand
->regno
] = cand
;
529 insn_to_cand_activation
[INSN_UID (activation
)] = cand_in_table
;
532 /* Create rematerialization candidates (inserting them into the
538 struct potential_cand
543 struct potential_cand
*regno_potential_cand
;
545 /* Create candidates. */
546 regno_potential_cand
= XCNEWVEC (struct potential_cand
, max_reg_num ());
547 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
548 if (NONDEBUG_INSN_P (insn
))
550 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
552 rtx set
= single_set (insn
);
555 /* See if this is an output reload for a previous insn. */
557 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
559 rtx dstreg
= SET_DEST (set
);
560 int src_regno
= REGNO (SET_SRC (set
));
561 int dst_regno
= REGNO (dstreg
);
562 rtx_insn
*insn2
= regno_potential_cand
[src_regno
].insn
;
565 && dst_regno
>= FIRST_PSEUDO_REGISTER
566 && reg_renumber
[dst_regno
] < 0
567 && BLOCK_FOR_INSN (insn2
) == BLOCK_FOR_INSN (insn
))
569 create_cand (insn2
, regno_potential_cand
[src_regno
].nop
,
575 nop
= operand_to_remat (insn
);
578 gcc_assert (REG_P (*id
->operand_loc
[nop
]));
579 int regno
= REGNO (*id
->operand_loc
[nop
]);
580 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
581 /* If we're setting an unrenumbered pseudo, make a candidate immediately.
582 If it's an output reload register, save it for later; the code above
583 looks for output reload insns later on. */
584 if (reg_renumber
[regno
] < 0)
585 create_cand (insn
, nop
, regno
);
586 else if (regno
>= lra_constraint_new_regno_start
)
588 regno_potential_cand
[regno
].insn
= insn
;
589 regno_potential_cand
[regno
].nop
= nop
;
595 for (struct lra_insn_reg
*reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
596 if (reg
->type
!= OP_IN
&& reg
->regno
!= keep_regno
597 && reg
->regno
>= FIRST_PSEUDO_REGISTER
)
598 regno_potential_cand
[reg
->regno
].insn
= NULL
;
600 cands_num
= all_cands
.length ();
601 free (regno_potential_cand
);
606 /* Create and initialize BB data. */
608 create_remat_bb_data (void)
611 remat_bb_data_t bb_info
;
613 remat_bb_data
= XNEWVEC (struct remat_bb_data
,
614 last_basic_block_for_fn (cfun
));
615 FOR_ALL_BB_FN (bb
, cfun
)
617 #ifdef ENABLE_CHECKING
618 if (bb
->index
< 0 || bb
->index
>= last_basic_block_for_fn (cfun
))
621 bb_info
= get_remat_bb_data (bb
);
623 bitmap_initialize (&bb_info
->changed_regs
, ®_obstack
);
624 bitmap_initialize (&bb_info
->dead_regs
, ®_obstack
);
625 bitmap_initialize (&bb_info
->gen_cands
, ®_obstack
);
626 bitmap_initialize (&bb_info
->livein_cands
, ®_obstack
);
627 bitmap_initialize (&bb_info
->pavin_cands
, ®_obstack
);
628 bitmap_initialize (&bb_info
->pavout_cands
, ®_obstack
);
629 bitmap_initialize (&bb_info
->avin_cands
, ®_obstack
);
630 bitmap_initialize (&bb_info
->avout_cands
, ®_obstack
);
634 /* Dump all candidates to DUMP_FILE. */
636 dump_cands (FILE *dump_file
)
641 fprintf (dump_file
, "\nCands:\n");
642 for (i
= 0; i
< (int) cands_num
; i
++)
645 fprintf (dump_file
, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
646 i
, cand
->nop
, cand
->regno
, cand
->reload_regno
);
647 print_inline_rtx (dump_file
, cand
->insn
, 6);
648 fprintf (dump_file
, "\n");
652 /* Dump all candidates and BB data. */
654 dump_candidates_and_remat_bb_data (void)
658 if (lra_dump_file
== NULL
)
660 dump_cands (lra_dump_file
);
661 FOR_EACH_BB_FN (bb
, cfun
)
663 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
665 fprintf (lra_dump_file
, " register live in:");
666 dump_regset (df_get_live_in (bb
), lra_dump_file
);
667 putc ('\n', lra_dump_file
);
669 fprintf (lra_dump_file
, " register live out:");
670 dump_regset (df_get_live_out (bb
), lra_dump_file
);
671 putc ('\n', lra_dump_file
);
672 /* Changed/dead regs: */
673 fprintf (lra_dump_file
, " changed regs:");
674 dump_regset (&get_remat_bb_data (bb
)->changed_regs
, lra_dump_file
);
675 putc ('\n', lra_dump_file
);
676 fprintf (lra_dump_file
, " dead regs:");
677 dump_regset (&get_remat_bb_data (bb
)->dead_regs
, lra_dump_file
);
678 putc ('\n', lra_dump_file
);
679 lra_dump_bitmap_with_title ("cands generated in BB",
680 &get_remat_bb_data (bb
)->gen_cands
, bb
->index
);
681 lra_dump_bitmap_with_title ("livein cands in BB",
682 &get_remat_bb_data (bb
)->livein_cands
, bb
->index
);
683 lra_dump_bitmap_with_title ("pavin cands in BB",
684 &get_remat_bb_data (bb
)->pavin_cands
, bb
->index
);
685 lra_dump_bitmap_with_title ("pavout cands in BB",
686 &get_remat_bb_data (bb
)->pavout_cands
, bb
->index
);
687 lra_dump_bitmap_with_title ("avin cands in BB",
688 &get_remat_bb_data (bb
)->avin_cands
, bb
->index
);
689 lra_dump_bitmap_with_title ("avout cands in BB",
690 &get_remat_bb_data (bb
)->avout_cands
, bb
->index
);
692 fprintf (lra_dump_file
, "subreg regs:");
693 dump_regset (&subreg_regs
, lra_dump_file
);
694 putc ('\n', lra_dump_file
);
697 /* Free all BB data. */
699 finish_remat_bb_data (void)
703 FOR_EACH_BB_FN (bb
, cfun
)
705 bitmap_clear (&get_remat_bb_data (bb
)->avout_cands
);
706 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
707 bitmap_clear (&get_remat_bb_data (bb
)->pavout_cands
);
708 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
709 bitmap_clear (&get_remat_bb_data (bb
)->livein_cands
);
710 bitmap_clear (&get_remat_bb_data (bb
)->gen_cands
);
711 bitmap_clear (&get_remat_bb_data (bb
)->dead_regs
);
712 bitmap_clear (&get_remat_bb_data (bb
)->changed_regs
);
714 free (remat_bb_data
);
719 /* Update changed_regs, dead_regs, subreg_regs of BB from INSN. */
721 set_bb_regs (basic_block bb
, rtx_insn
*insn
)
723 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
724 remat_bb_data_t bb_info
= get_remat_bb_data (bb
);
725 struct lra_insn_reg
*reg
;
727 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
729 unsigned regno
= reg
->regno
;
730 if (reg
->type
!= OP_IN
)
731 bitmap_set_bit (&bb_info
->changed_regs
, regno
);
732 else if (find_regno_note (insn
, REG_DEAD
, regno
) != NULL
)
733 bitmap_set_bit (&bb_info
->dead_regs
, regno
);
734 if (regno
>= FIRST_PSEUDO_REGISTER
&& reg
->subreg_p
)
735 bitmap_set_bit (&subreg_regs
, regno
);
738 for (int i
= 0; i
< call_used_regs_arr_len
; i
++)
739 bitmap_set_bit (&get_remat_bb_data (bb
)->dead_regs
,
740 call_used_regs_arr
[i
]);
743 /* Calculate changed_regs and dead_regs for each BB. */
745 calculate_local_reg_remat_bb_data (void)
750 FOR_EACH_BB_FN (bb
, cfun
)
751 FOR_BB_INSNS (bb
, insn
)
752 if (NONDEBUG_INSN_P (insn
))
753 set_bb_regs (bb
, insn
);
758 /* Return true if REGNO is an input operand of INSN. */
760 input_regno_present_p (rtx_insn
*insn
, int regno
)
763 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
764 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
765 struct lra_insn_reg
*reg
;
767 for (iter
= 0; iter
< 2; iter
++)
768 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
771 if (reg
->type
== OP_IN
&& reg
->regno
== regno
)
776 /* Return true if a call used register is an input operand of INSN. */
778 call_used_input_regno_present_p (rtx_insn
*insn
)
781 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
782 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
783 struct lra_insn_reg
*reg
;
785 for (iter
= 0; iter
< 2; iter
++)
786 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
789 if (reg
->type
== OP_IN
&& reg
->regno
<= FIRST_PSEUDO_REGISTER
790 && TEST_HARD_REG_BIT (call_used_reg_set
, reg
->regno
))
795 /* Calculate livein_cands for each BB. */
797 calculate_livein_cands (void)
801 FOR_EACH_BB_FN (bb
, cfun
)
803 bitmap livein_regs
= df_get_live_in (bb
);
804 bitmap livein_cands
= &get_remat_bb_data (bb
)->livein_cands
;
805 for (unsigned int i
= 0; i
< cands_num
; i
++)
807 cand_t cand
= all_cands
[i
];
808 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
809 struct lra_insn_reg
*reg
;
811 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
812 if (reg
->type
== OP_IN
&& ! bitmap_bit_p (livein_regs
, reg
->regno
))
815 bitmap_set_bit (livein_cands
, i
);
820 /* Calculate gen_cands for each BB. */
822 calculate_gen_cands (void)
826 bitmap_head gen_insns
;
829 bitmap_initialize (&gen_insns
, ®_obstack
);
830 FOR_EACH_BB_FN (bb
, cfun
)
832 gen_cands
= &get_remat_bb_data (bb
)->gen_cands
;
833 bitmap_clear (&gen_insns
);
834 FOR_BB_INSNS (bb
, insn
)
837 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
838 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
839 struct lra_insn_reg
*reg
;
845 int src_regno
= -1, dst_regno
= -1;
847 if ((set
= single_set (insn
)) != NULL
848 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
850 src_regno
= REGNO (SET_SRC (set
));
851 dst_regno
= REGNO (SET_DEST (set
));
854 /* Update gen_cands: */
855 bitmap_clear (&temp_bitmap
);
856 for (iter
= 0; iter
< 2; iter
++)
857 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
860 if (reg
->type
!= OP_IN
861 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
862 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
864 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
866 cand
= insn_to_cand
[INSN_UID (insn2
)];
867 gcc_assert (cand
!= NULL
);
868 /* Ignore the reload insn. */
869 if (src_regno
== cand
->reload_regno
870 && dst_regno
== cand
->regno
)
872 if (cand
->regno
== reg
->regno
873 || input_regno_present_p (insn2
, reg
->regno
))
875 bitmap_clear_bit (gen_cands
, cand
->index
);
876 bitmap_set_bit (&temp_bitmap
, uid
);
881 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
883 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
885 cand
= insn_to_cand
[INSN_UID (insn2
)];
886 gcc_assert (cand
!= NULL
);
887 if (call_used_input_regno_present_p (insn2
))
889 bitmap_clear_bit (gen_cands
, cand
->index
);
890 bitmap_set_bit (&temp_bitmap
, uid
);
893 bitmap_and_compl_into (&gen_insns
, &temp_bitmap
);
895 cand
= insn_to_cand
[INSN_UID (insn
)];
898 bitmap_set_bit (gen_cands
, cand
->index
);
899 bitmap_set_bit (&gen_insns
, INSN_UID (insn
));
903 bitmap_clear (&gen_insns
);
908 /* The common transfer function used by the DF equation solver to
909 propagate (partial) availability info BB_IN to BB_OUT through block
910 with BB_INDEX according to the following equation:
912 bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
915 cand_trans_fun (int bb_index
, bitmap bb_in
, bitmap bb_out
)
917 remat_bb_data_t bb_info
;
918 bitmap bb_livein
, bb_changed_regs
, bb_dead_regs
;
922 bb_info
= get_remat_bb_data_by_index (bb_index
);
923 bb_livein
= &bb_info
->livein_cands
;
924 bb_changed_regs
= &bb_info
->changed_regs
;
925 bb_dead_regs
= &bb_info
->dead_regs
;
926 /* Calculate killed avin cands -- cands whose regs are changed or
927 becoming dead in the BB. We calculate it here as we hope that
928 repeated calculations are compensated by smaller size of BB_IN in
929 comparison with all candidates number. */
930 bitmap_clear (&temp_bitmap
);
931 EXECUTE_IF_SET_IN_BITMAP (bb_in
, 0, cid
, bi
)
933 cand_t cand
= all_cands
[cid
];
934 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
935 struct lra_insn_reg
*reg
;
937 if (! bitmap_bit_p (bb_livein
, cid
))
939 bitmap_set_bit (&temp_bitmap
, cid
);
942 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
943 /* Ignore all outputs which are not the regno for
944 rematerialization. */
945 if (reg
->type
== OP_OUT
&& reg
->regno
!= cand
->regno
)
947 else if (bitmap_bit_p (bb_changed_regs
, reg
->regno
)
948 || bitmap_bit_p (bb_dead_regs
, reg
->regno
))
950 bitmap_set_bit (&temp_bitmap
, cid
);
953 /* Check regno for rematerialization. */
954 if (bitmap_bit_p (bb_changed_regs
, cand
->regno
)
955 || bitmap_bit_p (bb_dead_regs
, cand
->regno
))
956 bitmap_set_bit (&temp_bitmap
, cid
);
958 return bitmap_ior_and_compl (bb_out
,
959 &bb_info
->gen_cands
, bb_in
, &temp_bitmap
);
964 /* The transfer function used by the DF equation solver to propagate
965 partial candidate availability info through block with BB_INDEX
966 according to the following equation:
968 bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
971 cand_pav_trans_fun (int bb_index
)
973 remat_bb_data_t bb_info
;
975 bb_info
= get_remat_bb_data_by_index (bb_index
);
976 return cand_trans_fun (bb_index
, &bb_info
->pavin_cands
,
977 &bb_info
->pavout_cands
);
980 /* The confluence function used by the DF equation solver to set up
981 cand_pav info for a block BB without predecessor. */
983 cand_pav_con_fun_0 (basic_block bb
)
985 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
988 /* The confluence function used by the DF equation solver to propagate
989 partial candidate availability info from predecessor to successor
990 on edge E (pred->bb) according to the following equation:
992 bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
995 cand_pav_con_fun_n (edge e
)
997 basic_block pred
= e
->src
;
998 basic_block bb
= e
->dest
;
999 remat_bb_data_t bb_info
;
1000 bitmap bb_pavin
, pred_pavout
;
1002 bb_info
= get_remat_bb_data (bb
);
1003 bb_pavin
= &bb_info
->pavin_cands
;
1004 pred_pavout
= &get_remat_bb_data (pred
)->pavout_cands
;
1005 return bitmap_ior_into (bb_pavin
, pred_pavout
);
1010 /* The transfer function used by the DF equation solver to propagate
1011 candidate availability info through block with BB_INDEX according
1012 to the following equation:
1014 bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
1017 cand_av_trans_fun (int bb_index
)
1019 remat_bb_data_t bb_info
;
1021 bb_info
= get_remat_bb_data_by_index (bb_index
);
1022 return cand_trans_fun (bb_index
, &bb_info
->avin_cands
,
1023 &bb_info
->avout_cands
);
1026 /* The confluence function used by the DF equation solver to set up
1027 cand_av info for a block BB without predecessor. */
1029 cand_av_con_fun_0 (basic_block bb
)
1031 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
1034 /* The confluence function used by the DF equation solver to propagate
1035 cand_av info from predecessor to successor on edge E (pred->bb)
1036 according to the following equation:
1038 bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
1041 cand_av_con_fun_n (edge e
)
1043 basic_block pred
= e
->src
;
1044 basic_block bb
= e
->dest
;
1045 remat_bb_data_t bb_info
;
1046 bitmap bb_avin
, pred_avout
;
1048 bb_info
= get_remat_bb_data (bb
);
1049 bb_avin
= &bb_info
->avin_cands
;
1050 pred_avout
= &get_remat_bb_data (pred
)->avout_cands
;
1051 return bitmap_and_into (bb_avin
, pred_avout
);
1054 /* Calculate available candidates for each BB. */
1056 calculate_global_remat_bb_data (void)
1061 (DF_FORWARD
, NULL
, cand_pav_con_fun_0
, cand_pav_con_fun_n
,
1062 cand_pav_trans_fun
, &all_blocks
,
1063 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
1064 /* Initialize avin by pavin. */
1065 FOR_EACH_BB_FN (bb
, cfun
)
1066 bitmap_copy (&get_remat_bb_data (bb
)->avin_cands
,
1067 &get_remat_bb_data (bb
)->pavin_cands
);
1069 (DF_FORWARD
, NULL
, cand_av_con_fun_0
, cand_av_con_fun_n
,
1070 cand_av_trans_fun
, &all_blocks
,
1071 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
1076 /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
1078 change_sp_offset (rtx_insn
*insns
, HOST_WIDE_INT sp_offset
)
1080 for (rtx_insn
*insn
= insns
; insn
!= NULL
; insn
= NEXT_INSN (insn
))
1081 eliminate_regs_in_insn (insn
, false, false, sp_offset
);
1084 /* Return start hard register of REG (can be a hard or a pseudo reg)
1085 or -1 (if it is a spilled pseudo). Return number of hard registers
1086 occupied by REG through parameter NREGS if the start hard reg is
1089 get_hard_regs (struct lra_insn_reg
*reg
, int &nregs
)
1091 int regno
= reg
->regno
;
1092 int hard_regno
= regno
< FIRST_PSEUDO_REGISTER
? regno
: reg_renumber
[regno
];
1094 if (hard_regno
>= 0)
1095 nregs
= hard_regno_nregs
[hard_regno
][reg
->biggest_mode
];
1099 /* Make copy of and register scratch pseudos in rematerialized insn
1102 update_scratch_ops (rtx_insn
*remat_insn
)
1104 lra_insn_recog_data_t id
= lra_get_insn_recog_data (remat_insn
);
1105 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1106 for (int i
= 0; i
< static_id
->n_operands
; i
++)
1108 rtx
*loc
= id
->operand_loc
[i
];
1111 int regno
= REGNO (*loc
);
1112 if (! lra_former_scratch_p (regno
))
1114 *loc
= lra_create_new_reg (GET_MODE (*loc
), *loc
,
1115 lra_get_allocno_class (regno
),
1116 "scratch pseudo copy");
1117 lra_register_new_scratch_op (remat_insn
, i
);
1122 /* Insert rematerialization insns using the data-flow data calculated
1129 bitmap_head avail_cands
;
1130 bitmap_head active_cands
;
1131 bool changed_p
= false;
1132 /* Living hard regs and hard registers of living pseudos. */
1133 HARD_REG_SET live_hard_regs
;
1135 bitmap_initialize (&avail_cands
, ®_obstack
);
1136 bitmap_initialize (&active_cands
, ®_obstack
);
1137 FOR_EACH_BB_FN (bb
, cfun
)
1139 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_out (bb
));
1140 bitmap_and (&avail_cands
, &get_remat_bb_data (bb
)->avin_cands
,
1141 &get_remat_bb_data (bb
)->livein_cands
);
1142 /* Activating insns are always in the same block as their corresponding
1143 remat insn, so at the start of a block the two bitsets are equal. */
1144 bitmap_copy (&active_cands
, &avail_cands
);
1145 FOR_BB_INSNS (bb
, insn
)
1147 if (!NONDEBUG_INSN_P (insn
))
1150 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
1151 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1152 struct lra_insn_reg
*reg
;
1158 int src_regno
= -1, dst_regno
= -1;
1160 if ((set
= single_set (insn
)) != NULL
1161 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
1163 src_regno
= REGNO (SET_SRC (set
));
1164 dst_regno
= REGNO (SET_DEST (set
));
1168 /* Check possibility of rematerialization (hard reg or
1169 unpsilled pseudo <- spilled pseudo): */
1170 if (dst_regno
>= 0 && src_regno
>= FIRST_PSEUDO_REGISTER
1171 && reg_renumber
[src_regno
] < 0
1172 && (dst_regno
< FIRST_PSEUDO_REGISTER
1173 || reg_renumber
[dst_regno
] >= 0))
1175 for (cand
= regno_cands
[src_regno
];
1177 cand
= cand
->next_regno_cand
)
1178 if (bitmap_bit_p (&avail_cands
, cand
->index
)
1179 && bitmap_bit_p (&active_cands
, cand
->index
))
1182 int i
, hard_regno
, nregs
;
1183 rtx_insn
*remat_insn
= NULL
;
1184 HOST_WIDE_INT cand_sp_offset
= 0;
1187 lra_insn_recog_data_t cand_id
1188 = lra_get_insn_recog_data (cand
->insn
);
1189 struct lra_static_insn_data
*static_cand_id
1190 = cand_id
->insn_static_data
;
1191 rtx saved_op
= *cand_id
->operand_loc
[cand
->nop
];
1193 /* Check clobbers do not kill something living. */
1194 gcc_assert (REG_P (saved_op
));
1195 int ignore_regno
= REGNO (saved_op
);
1197 for (reg
= cand_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1198 if (reg
->type
!= OP_IN
&& reg
->regno
!= ignore_regno
)
1200 hard_regno
= get_hard_regs (reg
, nregs
);
1201 gcc_assert (hard_regno
>= 0);
1202 for (i
= 0; i
< nregs
; i
++)
1203 if (TEST_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
))
1211 for (reg
= static_cand_id
->hard_regs
;
1214 if (reg
->type
!= OP_IN
1215 && TEST_HARD_REG_BIT (live_hard_regs
, reg
->regno
))
1221 *cand_id
->operand_loc
[cand
->nop
] = SET_DEST (set
);
1222 lra_update_insn_regno_info (cand
->insn
);
1223 bool ok_p
= lra_constrain_insn (cand
->insn
);
1226 rtx remat_pat
= copy_insn (PATTERN (cand
->insn
));
1229 emit_insn (remat_pat
);
1230 remat_insn
= get_insns ();
1232 if (recog_memoized (remat_insn
) < 0)
1234 cand_sp_offset
= cand_id
->sp_offset
;
1236 *cand_id
->operand_loc
[cand
->nop
] = saved_op
;
1237 lra_update_insn_regno_info (cand
->insn
);
1241 bitmap_clear (&temp_bitmap
);
1242 /* Update avail_cands (see analogous code for
1243 calculate_gen_cands). */
1244 for (iter
= 0; iter
< 2; iter
++)
1245 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
1248 if (reg
->type
!= OP_IN
1249 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1250 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1252 cand
= all_cands
[cid
];
1254 /* Ignore the reload insn. */
1255 if (src_regno
== cand
->reload_regno
1256 && dst_regno
== cand
->regno
)
1258 if (cand
->regno
== reg
->regno
1259 || input_regno_present_p (cand
->insn
, reg
->regno
))
1260 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1264 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1266 cand
= all_cands
[cid
];
1268 if (call_used_input_regno_present_p (cand
->insn
))
1269 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1272 bitmap_and_compl_into (&avail_cands
, &temp_bitmap
);
1274 /* Now see whether a candidate is made active or available
1276 cand
= insn_to_cand_activation
[INSN_UID (insn
)];
1278 bitmap_set_bit (&active_cands
, cand
->index
);
1280 cand
= insn_to_cand
[INSN_UID (insn
)];
1283 bitmap_set_bit (&avail_cands
, cand
->index
);
1284 if (cand
->reload_regno
== -1)
1285 bitmap_set_bit (&active_cands
, cand
->index
);
1287 bitmap_clear_bit (&active_cands
, cand
->index
);
1290 if (remat_insn
!= NULL
)
1292 HOST_WIDE_INT sp_offset_change
= cand_sp_offset
- id
->sp_offset
;
1293 if (sp_offset_change
!= 0)
1294 change_sp_offset (remat_insn
, sp_offset_change
);
1295 update_scratch_ops (remat_insn
);
1296 lra_process_new_insns (insn
, remat_insn
, NULL
,
1297 "Inserting rematerialization insn");
1298 lra_set_insn_deleted (insn
);
1303 /* Update live hard regs: */
1304 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1305 if (reg
->type
== OP_IN
1306 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1308 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1310 for (i
= 0; i
< nregs
; i
++)
1311 CLEAR_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1313 /* Process also hard regs (e.g. CC register) which are part
1314 of insn definition. */
1315 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1316 if (reg
->type
== OP_IN
1317 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1318 CLEAR_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1319 /* Inputs have been processed, now process outputs. */
1320 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1321 if (reg
->type
!= OP_IN
1322 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1324 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1326 for (i
= 0; i
< nregs
; i
++)
1327 SET_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1329 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1330 if (reg
->type
!= OP_IN
1331 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1332 SET_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1335 bitmap_clear (&avail_cands
);
1336 bitmap_clear (&active_cands
);
1342 /* Current number of rematerialization iteration. */
1343 int lra_rematerialization_iter
;
1345 /* Entry point of the rematerialization sub-pass. Return true if we
1346 did any rematerialization. */
1352 int max_regno
= max_reg_num ();
1354 if (! flag_lra_remat
)
1356 lra_rematerialization_iter
++;
1357 if (lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
1359 if (lra_dump_file
!= NULL
)
1360 fprintf (lra_dump_file
,
1361 "\n******** Rematerialization #%d: ********\n\n",
1362 lra_rematerialization_iter
);
1363 timevar_push (TV_LRA_REMAT
);
1364 insn_to_cand
= XCNEWVEC (cand_t
, get_max_uid ());
1365 insn_to_cand_activation
= XCNEWVEC (cand_t
, get_max_uid ());
1366 regno_cands
= XCNEWVEC (cand_t
, max_regno
);
1367 all_cands
.create (8000);
1368 call_used_regs_arr_len
= 0;
1369 for (int i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1370 if (call_used_regs
[i
])
1371 call_used_regs_arr
[call_used_regs_arr_len
++] = i
;
1372 initiate_cand_table ();
1373 create_remat_bb_data ();
1374 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1375 bitmap_initialize (&subreg_regs
, ®_obstack
);
1376 calculate_local_reg_remat_bb_data ();
1378 calculate_livein_cands ();
1379 calculate_gen_cands ();
1380 bitmap_initialize (&all_blocks
, ®_obstack
);
1381 FOR_ALL_BB_FN (bb
, cfun
)
1382 bitmap_set_bit (&all_blocks
, bb
->index
);
1383 calculate_global_remat_bb_data ();
1384 dump_candidates_and_remat_bb_data ();
1385 result
= do_remat ();
1386 all_cands
.release ();
1387 bitmap_clear (&temp_bitmap
);
1388 bitmap_clear (&subreg_regs
);
1389 finish_remat_bb_data ();
1390 finish_cand_table ();
1391 bitmap_clear (&all_blocks
);
1393 free (insn_to_cand
);
1394 free (insn_to_cand_activation
);
1395 timevar_pop (TV_LRA_REMAT
);