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"
65 #include "insn-config.h"
69 #include "rtl-error.h"
80 #include "sparseset.h"
83 #include "insn-attr.h"
86 /* Number of candidates for rematerialization. */
87 static unsigned int cands_num
;
89 /* The following is used for representation of call_used_reg_set in
90 form array whose elements are hard register numbers with nonzero bit
91 in CALL_USED_REG_SET. */
92 static int call_used_regs_arr_len
;
93 static int call_used_regs_arr
[FIRST_PSEUDO_REGISTER
];
95 /* Bitmap used for different calculations. */
96 static bitmap_head temp_bitmap
;
98 typedef struct cand
*cand_t
;
99 typedef const struct cand
*const_cand_t
;
101 /* Insn candidates for rematerialization. The candidate insn should
102 have the following properies:
103 o no any memory (as access to memory is non-profitable)
104 o no INOUT regs (it means no non-paradoxical subreg of output reg)
105 o one output spilled pseudo (or reload pseudo of a spilled pseudo)
106 o all other pseudos are with assigned hard regs. */
109 /* Index of the candidates in all_cands. */
111 /* The candidate insn. */
113 /* Insn pseudo regno for rematerialization. */
115 /* Non-negative if a reload pseudo is in the insn instead of the
116 pseudo for rematerialization. */
118 /* Number of the operand containing the regno or its reload
121 /* Next candidate for the same regno. */
122 cand_t next_regno_cand
;
125 /* Vector containing all candidates. */
126 static vec
<cand_t
> all_cands
;
127 /* Map: insn -> candidate representing it. It is null if the insn can
128 not be used for rematerialization. */
129 static cand_t
*insn_to_cand
;
131 /* Map regno -> candidates can be used for the regno
132 rematerialization. */
133 static cand_t
*regno_cands
;
135 /* Data about basic blocks used for the rematerialization
139 /* Basic block about which the below data are. */
141 /* Registers changed in the basic block: */
142 bitmap_head changed_regs
;
143 /* Registers becoming dead in the BB. */
144 bitmap_head dead_regs
;
145 /* Cands present in the BB whose in/out regs are not changed after
146 the cands occurence and are not dead (except the reload
148 bitmap_head gen_cands
;
149 bitmap_head livein_cands
; /* cands whose inputs live at the BB start. */
150 bitmap_head pavin_cands
; /* cands partially available at BB entry. */
151 bitmap_head pavout_cands
; /* cands partially available at BB exit. */
152 bitmap_head avin_cands
; /* cands available at the entry of the BB. */
153 bitmap_head avout_cands
; /* cands available at the exit of the BB. */
156 /* Array for all BB data. Indexed by the corresponding BB index. */
157 typedef struct remat_bb_data
*remat_bb_data_t
;
159 /* Basic blocks for data flow problems -- all bocks except the special
161 static bitmap_head all_blocks
;
163 /* All basic block data are referred through the following array. */
164 static remat_bb_data_t remat_bb_data
;
166 /* Two small functions for access to the bb data. */
167 static inline remat_bb_data_t
168 get_remat_bb_data (basic_block bb
)
170 return &remat_bb_data
[(bb
)->index
];
173 static inline remat_bb_data_t
174 get_remat_bb_data_by_index (int index
)
176 return &remat_bb_data
[index
];
181 /* Recursive hash function for RTL X. */
194 val
+= (int) code
+ 4095;
196 /* Some RTL can be compared nonrecursively. */
200 return val
+ REGNO (x
);
203 return iterative_hash_object (XEXP (x
, 0), val
);
206 return iterative_hash_object (XSTR (x
, 0), val
);
218 /* Hash the elements. */
219 fmt
= GET_RTX_FORMAT (code
);
220 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
235 val
+= XVECLEN (x
, i
);
237 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
238 val
+= rtx_hash (XVECEXP (x
, i
, j
));
242 val
+= rtx_hash (XEXP (x
, i
));
247 val
+= htab_hash_string (XSTR (x
, i
));
255 /* It is believed that rtx's at this level will never
256 contain anything but integers and other rtx's, except for
257 within LABEL_REFs and SYMBOL_REFs. */
267 /* Hash table for the candidates. Different insns (e.g. structurally
268 the same insns or even insns with different unused output regs) can
269 be represented by the same candidate in the table. */
270 static htab_t cand_table
;
272 /* Hash function for candidate CAND. */
274 cand_hash (const void *cand
)
276 const_cand_t c
= (const_cand_t
) cand
;
277 lra_insn_recog_data_t id
= lra_get_insn_recog_data (c
->insn
);
278 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
279 int nops
= static_id
->n_operands
;
282 for (int i
= 0; i
< nops
; i
++)
284 hash
= iterative_hash_object (c
->regno
, hash
);
285 else if (static_id
->operand
[i
].type
== OP_IN
)
286 hash
= iterative_hash_object (*id
->operand_loc
[i
], hash
);
290 /* Equal function for candidates CAND1 and CAND2. They are equal if
291 the corresponding candidate insns have the same code, the same
292 regno for rematerialization, the same input operands. */
294 cand_eq_p (const void *cand1
, const void *cand2
)
296 const_cand_t c1
= (const_cand_t
) cand1
;
297 const_cand_t c2
= (const_cand_t
) cand2
;
298 lra_insn_recog_data_t id1
= lra_get_insn_recog_data (c1
->insn
);
299 lra_insn_recog_data_t id2
= lra_get_insn_recog_data (c2
->insn
);
300 struct lra_static_insn_data
*static_id1
= id1
->insn_static_data
;
301 int nops
= static_id1
->n_operands
;
303 if (c1
->regno
!= c2
->regno
304 || INSN_CODE (c1
->insn
) < 0
305 || INSN_CODE (c1
->insn
) != INSN_CODE (c2
->insn
))
307 gcc_assert (c1
->nop
== c2
->nop
);
308 for (int i
= 0; i
< nops
; i
++)
309 if (i
!= c1
->nop
&& static_id1
->operand
[i
].type
== OP_IN
310 && *id1
->operand_loc
[i
] != *id2
->operand_loc
[i
])
315 /* Insert candidate CAND into the table if it is not there yet.
316 Return candidate which is in the table. */
318 insert_cand (cand_t cand
)
322 entry_ptr
= htab_find_slot (cand_table
, cand
, INSERT
);
323 if (*entry_ptr
== NULL
)
324 *entry_ptr
= (void *) cand
;
325 return (cand_t
) *entry_ptr
;
328 /* Free candidate CAND memory. */
330 free_cand (void *cand
)
335 /* Initiate the candidate table. */
337 initiate_cand_table (void)
339 cand_table
= htab_create (8000, cand_hash
, cand_eq_p
,
340 (htab_del
) free_cand
);
343 /* Finish the candidate table. */
345 finish_cand_table (void)
347 htab_delete (cand_table
);
352 /* Return true if X contains memory or some UNSPEC. We can not just
353 check insn operands as memory or unspec might be not an operand
354 itself but contain an operand. Insn with memory access is not
355 profitable for rematerialization. Rematerialization of UNSPEC
356 might result in wrong code generation as the UNPEC effect is
357 unknown (e.g. generating a label). */
359 bad_for_rematerialization_p (rtx x
)
365 if (MEM_P (x
) || GET_CODE (x
) == UNSPEC
|| GET_CODE (x
) == UNSPEC_VOLATILE
)
368 fmt
= GET_RTX_FORMAT (code
);
369 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
373 if (bad_for_rematerialization_p (XEXP (x
, i
)))
376 else if (fmt
[i
] == 'E')
378 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
379 if (bad_for_rematerialization_p (XVECEXP (x
, i
, j
)))
386 /* If INSN can not be used for rematerialization, return negative
387 value. If INSN can be considered as a candidate for
388 rematerialization, return value which is the operand number of the
389 pseudo for which the insn can be used for rematerialization. Here
390 we consider the insns without any memory, spilled pseudo (except
391 for the rematerialization pseudo), or dying or unused regs. */
393 operand_to_remat (rtx_insn
*insn
)
395 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
396 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
397 struct lra_insn_reg
*reg
, *found_reg
= NULL
;
399 /* Don't rematerialize insns which can change PC. */
400 if (JUMP_P (insn
) || CALL_P (insn
))
402 /* First find a pseudo which can be rematerialized. */
403 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
404 /* True FRAME_POINTER_NEEDED might be because we can not follow
405 changing sp offsets, e.g. alloca is used. If the insn contains
406 stack pointer in such case, we can not rematerialize it as we
407 can not know sp offset at a rematerialization place. */
408 if (reg
->regno
== STACK_POINTER_REGNUM
&& frame_pointer_needed
)
410 else if (reg
->type
== OP_OUT
&& ! reg
->subreg_p
411 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
413 /* We permits only one spilled reg. */
414 if (found_reg
!= NULL
)
418 /* IRA calculates conflicts separately for subregs of two words
419 pseudo. Even if the pseudo lives, e.g. one its subreg can be
420 used lately, another subreg hard register can be already used
421 for something else. In such case, it is not safe to
422 rematerialize the insn. */
423 else if (reg
->type
== OP_IN
&& reg
->subreg_p
424 && reg
->regno
>= FIRST_PSEUDO_REGISTER
425 && (GET_MODE_SIZE (PSEUDO_REGNO_MODE (reg
->regno
))
426 == 2 * UNITS_PER_WORD
))
428 if (found_reg
== NULL
)
430 if (found_reg
->regno
< FIRST_PSEUDO_REGISTER
)
432 if (bad_for_rematerialization_p (PATTERN (insn
)))
434 /* Check the other regs are not spilled. */
435 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
436 if (found_reg
== reg
)
438 else if (reg
->type
== OP_INOUT
)
440 else if (reg
->regno
>= FIRST_PSEUDO_REGISTER
441 && reg_renumber
[reg
->regno
] < 0)
442 /* Another spilled reg. */
444 else if (reg
->type
== OP_IN
)
446 if (find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
447 /* We don't want to make live ranges longer. */
449 /* Check that there is no output reg as the input one. */
450 for (struct lra_insn_reg
*reg2
= id
->regs
;
453 if (reg2
->type
== OP_OUT
&& reg
->regno
== reg2
->regno
)
455 if (reg
->regno
< FIRST_PSEUDO_REGISTER
)
456 for (struct lra_insn_reg
*reg2
= static_id
->hard_regs
;
459 if (reg2
->type
== OP_OUT
460 && reg
->regno
<= reg2
->regno
463 + hard_regno_nregs
[reg
->regno
][reg
->biggest_mode
])))
466 /* Find the rematerialization operand. */
467 int nop
= static_id
->n_operands
;
468 for (int i
= 0; i
< nop
; i
++)
469 if (REG_P (*id
->operand_loc
[i
])
470 && (int) REGNO (*id
->operand_loc
[i
]) == found_reg
->regno
)
475 /* Create candidate for INSN with rematerialization operand NOP and
476 REGNO. Insert the candidate into the table and set up the
477 corresponding INSN_TO_CAND element. */
479 create_cand (rtx_insn
*insn
, int nop
, int regno
)
481 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
482 rtx reg
= *id
->operand_loc
[nop
];
483 gcc_assert (REG_P (reg
));
484 int op_regno
= REGNO (reg
);
485 gcc_assert (op_regno
>= FIRST_PSEUDO_REGISTER
);
486 cand_t cand
= XNEW (struct cand
);
490 cand
->reload_regno
= op_regno
== regno
? -1 : op_regno
;
491 gcc_assert (cand
->regno
>= 0);
492 cand_t cand_in_table
= insert_cand (cand
);
493 insn_to_cand
[INSN_UID (insn
)] = cand_in_table
;
494 if (cand
!= cand_in_table
)
499 cand
->index
= all_cands
.length ();
500 all_cands
.safe_push (cand
);
501 cand
->next_regno_cand
= regno_cands
[cand
->regno
];
502 regno_cands
[cand
->regno
] = cand
;
506 /* Create rematerialization candidates (inserting them into the
512 struct potential_cand
517 struct potential_cand
*regno_potential_cand
;
519 /* Create candidates. */
520 regno_potential_cand
= XCNEWVEC (struct potential_cand
, max_reg_num ());
521 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
525 int src_regno
, dst_regno
;
527 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
528 int nop
= operand_to_remat (insn
);
531 if ((set
= single_set (insn
)) != NULL
532 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
))
533 && ((src_regno
= REGNO (SET_SRC (set
)))
534 >= lra_constraint_new_regno_start
)
535 && (dst_regno
= REGNO (SET_DEST (set
))) >= FIRST_PSEUDO_REGISTER
536 && reg_renumber
[dst_regno
] < 0
537 && (insn2
= regno_potential_cand
[src_regno
].insn
) != NULL
538 && BLOCK_FOR_INSN (insn2
) == BLOCK_FOR_INSN (insn
))
539 /* It is an output reload insn after insn can be
540 rematerialized (potential candidate). */
541 create_cand (insn2
, regno_potential_cand
[src_regno
].nop
, dst_regno
);
544 gcc_assert (REG_P (*id
->operand_loc
[nop
]));
545 regno
= REGNO (*id
->operand_loc
[nop
]);
546 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
547 if (reg_renumber
[regno
] < 0)
548 create_cand (insn
, nop
, regno
);
551 regno_potential_cand
[regno
].insn
= insn
;
552 regno_potential_cand
[regno
].nop
= nop
;
557 for (struct lra_insn_reg
*reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
558 if (reg
->type
!= OP_IN
&& reg
->regno
!= regno
559 && reg
->regno
>= FIRST_PSEUDO_REGISTER
)
560 regno_potential_cand
[reg
->regno
].insn
= NULL
;
562 cands_num
= all_cands
.length ();
563 free (regno_potential_cand
);
568 /* Create and initialize BB data. */
570 create_remat_bb_data (void)
573 remat_bb_data_t bb_info
;
575 remat_bb_data
= XNEWVEC (struct remat_bb_data
,
576 last_basic_block_for_fn (cfun
));
577 FOR_ALL_BB_FN (bb
, cfun
)
579 gcc_checking_assert (bb
->index
>= 0
580 && bb
->index
< last_basic_block_for_fn (cfun
));
581 bb_info
= get_remat_bb_data (bb
);
583 bitmap_initialize (&bb_info
->changed_regs
, ®_obstack
);
584 bitmap_initialize (&bb_info
->dead_regs
, ®_obstack
);
585 bitmap_initialize (&bb_info
->gen_cands
, ®_obstack
);
586 bitmap_initialize (&bb_info
->livein_cands
, ®_obstack
);
587 bitmap_initialize (&bb_info
->pavin_cands
, ®_obstack
);
588 bitmap_initialize (&bb_info
->pavout_cands
, ®_obstack
);
589 bitmap_initialize (&bb_info
->avin_cands
, ®_obstack
);
590 bitmap_initialize (&bb_info
->avout_cands
, ®_obstack
);
594 /* Dump all candidates to DUMP_FILE. */
596 dump_cands (FILE *dump_file
)
601 fprintf (dump_file
, "\nCands:\n");
602 for (i
= 0; i
< (int) cands_num
; i
++)
605 fprintf (dump_file
, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
606 i
, cand
->nop
, cand
->regno
, cand
->reload_regno
);
607 print_inline_rtx (dump_file
, cand
->insn
, 6);
608 fprintf (dump_file
, "\n");
612 /* Dump all candidates and BB data. */
614 dump_candidates_and_remat_bb_data (void)
618 if (lra_dump_file
== NULL
)
620 dump_cands (lra_dump_file
);
621 FOR_EACH_BB_FN (bb
, cfun
)
623 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
625 fprintf (lra_dump_file
, " register live in:");
626 dump_regset (df_get_live_in (bb
), lra_dump_file
);
627 putc ('\n', lra_dump_file
);
629 fprintf (lra_dump_file
, " register live out:");
630 dump_regset (df_get_live_out (bb
), lra_dump_file
);
631 putc ('\n', lra_dump_file
);
632 /* Changed/dead regs: */
633 fprintf (lra_dump_file
, " changed regs:");
634 dump_regset (&get_remat_bb_data (bb
)->changed_regs
, lra_dump_file
);
635 putc ('\n', lra_dump_file
);
636 fprintf (lra_dump_file
, " dead regs:");
637 dump_regset (&get_remat_bb_data (bb
)->dead_regs
, lra_dump_file
);
638 putc ('\n', lra_dump_file
);
639 lra_dump_bitmap_with_title ("cands generated in BB",
640 &get_remat_bb_data (bb
)->gen_cands
, bb
->index
);
641 lra_dump_bitmap_with_title ("livein cands in BB",
642 &get_remat_bb_data (bb
)->livein_cands
, bb
->index
);
643 lra_dump_bitmap_with_title ("pavin cands in BB",
644 &get_remat_bb_data (bb
)->pavin_cands
, bb
->index
);
645 lra_dump_bitmap_with_title ("pavout cands in BB",
646 &get_remat_bb_data (bb
)->pavout_cands
, bb
->index
);
647 lra_dump_bitmap_with_title ("avin cands in BB",
648 &get_remat_bb_data (bb
)->avin_cands
, bb
->index
);
649 lra_dump_bitmap_with_title ("avout cands in BB",
650 &get_remat_bb_data (bb
)->avout_cands
, bb
->index
);
654 /* Free all BB data. */
656 finish_remat_bb_data (void)
660 FOR_EACH_BB_FN (bb
, cfun
)
662 bitmap_clear (&get_remat_bb_data (bb
)->avout_cands
);
663 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
664 bitmap_clear (&get_remat_bb_data (bb
)->pavout_cands
);
665 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
666 bitmap_clear (&get_remat_bb_data (bb
)->livein_cands
);
667 bitmap_clear (&get_remat_bb_data (bb
)->gen_cands
);
668 bitmap_clear (&get_remat_bb_data (bb
)->dead_regs
);
669 bitmap_clear (&get_remat_bb_data (bb
)->changed_regs
);
671 free (remat_bb_data
);
676 /* Update changed_regs and dead_regs of BB from INSN. */
678 set_bb_regs (basic_block bb
, rtx_insn
*insn
)
680 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
681 struct lra_insn_reg
*reg
;
683 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
684 if (reg
->type
!= OP_IN
)
685 bitmap_set_bit (&get_remat_bb_data (bb
)->changed_regs
, reg
->regno
);
688 if (find_regno_note (insn
, REG_DEAD
, (unsigned) reg
->regno
) != NULL
)
689 bitmap_set_bit (&get_remat_bb_data (bb
)->dead_regs
, reg
->regno
);
692 for (int i
= 0; i
< call_used_regs_arr_len
; i
++)
693 bitmap_set_bit (&get_remat_bb_data (bb
)->dead_regs
,
694 call_used_regs_arr
[i
]);
697 /* Calculate changed_regs and dead_regs for each BB. */
699 calculate_local_reg_remat_bb_data (void)
704 FOR_EACH_BB_FN (bb
, cfun
)
705 FOR_BB_INSNS (bb
, insn
)
707 set_bb_regs (bb
, insn
);
712 /* Return true if REGNO is an input operand of INSN. */
714 input_regno_present_p (rtx_insn
*insn
, int regno
)
716 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
717 struct lra_insn_reg
*reg
;
719 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
720 if (reg
->type
== OP_IN
&& reg
->regno
== regno
)
725 /* Return true if a call used register is an input operand of INSN. */
727 call_used_input_regno_present_p (rtx_insn
*insn
)
729 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
730 struct lra_insn_reg
*reg
;
732 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
733 if (reg
->type
== OP_IN
&& reg
->regno
<= FIRST_PSEUDO_REGISTER
734 && TEST_HARD_REG_BIT (call_used_reg_set
, reg
->regno
))
739 /* Calculate livein_cands for each BB. */
741 calculate_livein_cands (void)
745 FOR_EACH_BB_FN (bb
, cfun
)
747 bitmap livein_regs
= df_get_live_in (bb
);
748 bitmap livein_cands
= &get_remat_bb_data (bb
)->livein_cands
;
749 for (unsigned int i
= 0; i
< cands_num
; i
++)
751 cand_t cand
= all_cands
[i
];
752 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
753 struct lra_insn_reg
*reg
;
755 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
756 if (reg
->type
== OP_IN
&& ! bitmap_bit_p (livein_regs
, reg
->regno
))
759 bitmap_set_bit (livein_cands
, i
);
764 /* Calculate gen_cands for each BB. */
766 calculate_gen_cands (void)
770 bitmap_head gen_insns
;
773 bitmap_initialize (&gen_insns
, ®_obstack
);
774 FOR_EACH_BB_FN (bb
, cfun
)
776 gen_cands
= &get_remat_bb_data (bb
)->gen_cands
;
777 bitmap_clear (&gen_insns
);
778 FOR_BB_INSNS (bb
, insn
)
781 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
782 struct lra_insn_reg
*reg
;
787 int src_regno
= -1, dst_regno
= -1;
789 if ((set
= single_set (insn
)) != NULL
790 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
792 src_regno
= REGNO (SET_SRC (set
));
793 dst_regno
= REGNO (SET_DEST (set
));
796 /* Update gen_cands: */
797 bitmap_clear (&temp_bitmap
);
798 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
799 if (reg
->type
!= OP_IN
800 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
801 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
803 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
805 cand
= insn_to_cand
[INSN_UID (insn2
)];
806 gcc_assert (cand
!= NULL
);
807 /* Ignore the reload insn. */
808 if (src_regno
== cand
->reload_regno
809 && dst_regno
== cand
->regno
)
811 if (cand
->regno
== reg
->regno
812 || input_regno_present_p (insn2
, reg
->regno
))
814 bitmap_clear_bit (gen_cands
, cand
->index
);
815 bitmap_set_bit (&temp_bitmap
, uid
);
820 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
822 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
824 cand
= insn_to_cand
[INSN_UID (insn2
)];
825 gcc_assert (cand
!= NULL
);
826 if (call_used_input_regno_present_p (insn2
))
828 bitmap_clear_bit (gen_cands
, cand
->index
);
829 bitmap_set_bit (&temp_bitmap
, uid
);
832 bitmap_and_compl_into (&gen_insns
, &temp_bitmap
);
834 cand
= insn_to_cand
[INSN_UID (insn
)];
837 bitmap_set_bit (gen_cands
, cand
->index
);
838 bitmap_set_bit (&gen_insns
, INSN_UID (insn
));
842 bitmap_clear (&gen_insns
);
847 /* The common transfer function used by the DF equation solver to
848 propagate (partial) availability info BB_IN to BB_OUT through block
849 with BB_INDEX according to the following equation:
851 bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
854 cand_trans_fun (int bb_index
, bitmap bb_in
, bitmap bb_out
)
856 remat_bb_data_t bb_info
;
857 bitmap bb_livein
, bb_changed_regs
, bb_dead_regs
;
861 bb_info
= get_remat_bb_data_by_index (bb_index
);
862 bb_livein
= &bb_info
->livein_cands
;
863 bb_changed_regs
= &bb_info
->changed_regs
;
864 bb_dead_regs
= &bb_info
->dead_regs
;
865 /* Calculate killed avin cands -- cands whose regs are changed or
866 becoming dead in the BB. We calculate it here as we hope that
867 repeated calculations are compensated by smaller size of BB_IN in
868 comparison with all candidates number. */
869 bitmap_clear (&temp_bitmap
);
870 EXECUTE_IF_SET_IN_BITMAP (bb_in
, 0, cid
, bi
)
872 cand_t cand
= all_cands
[cid
];
873 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
874 struct lra_insn_reg
*reg
;
876 if (! bitmap_bit_p (bb_livein
, cid
))
878 bitmap_set_bit (&temp_bitmap
, cid
);
881 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
882 /* Ignore all outputs which are not the regno for
883 rematerialization. */
884 if (reg
->type
== OP_OUT
&& reg
->regno
!= cand
->regno
)
886 else if (bitmap_bit_p (bb_changed_regs
, reg
->regno
)
887 || bitmap_bit_p (bb_dead_regs
, reg
->regno
))
889 bitmap_set_bit (&temp_bitmap
, cid
);
892 /* Check regno for rematerialization. */
893 if (bitmap_bit_p (bb_changed_regs
, cand
->regno
)
894 || bitmap_bit_p (bb_dead_regs
, cand
->regno
))
895 bitmap_set_bit (&temp_bitmap
, cid
);
897 return bitmap_ior_and_compl (bb_out
,
898 &bb_info
->gen_cands
, bb_in
, &temp_bitmap
);
903 /* The transfer function used by the DF equation solver to propagate
904 partial candidate availability info through block with BB_INDEX
905 according to the following equation:
907 bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
910 cand_pav_trans_fun (int bb_index
)
912 remat_bb_data_t bb_info
;
914 bb_info
= get_remat_bb_data_by_index (bb_index
);
915 return cand_trans_fun (bb_index
, &bb_info
->pavin_cands
,
916 &bb_info
->pavout_cands
);
919 /* The confluence function used by the DF equation solver to set up
920 cand_pav info for a block BB without predecessor. */
922 cand_pav_con_fun_0 (basic_block bb
)
924 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
927 /* The confluence function used by the DF equation solver to propagate
928 partial candidate availability info from predecessor to successor
929 on edge E (pred->bb) according to the following equation:
931 bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
934 cand_pav_con_fun_n (edge e
)
936 basic_block pred
= e
->src
;
937 basic_block bb
= e
->dest
;
938 remat_bb_data_t bb_info
;
939 bitmap bb_pavin
, pred_pavout
;
941 bb_info
= get_remat_bb_data (bb
);
942 bb_pavin
= &bb_info
->pavin_cands
;
943 pred_pavout
= &get_remat_bb_data (pred
)->pavout_cands
;
944 return bitmap_ior_into (bb_pavin
, pred_pavout
);
949 /* The transfer function used by the DF equation solver to propagate
950 candidate availability info through block with BB_INDEX according
951 to the following equation:
953 bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
956 cand_av_trans_fun (int bb_index
)
958 remat_bb_data_t bb_info
;
960 bb_info
= get_remat_bb_data_by_index (bb_index
);
961 return cand_trans_fun (bb_index
, &bb_info
->avin_cands
,
962 &bb_info
->avout_cands
);
965 /* The confluence function used by the DF equation solver to set up
966 cand_av info for a block BB without predecessor. */
968 cand_av_con_fun_0 (basic_block bb
)
970 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
973 /* The confluence function used by the DF equation solver to propagate
974 cand_av info from predecessor to successor on edge E (pred->bb)
975 according to the following equation:
977 bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
980 cand_av_con_fun_n (edge e
)
982 basic_block pred
= e
->src
;
983 basic_block bb
= e
->dest
;
984 remat_bb_data_t bb_info
;
985 bitmap bb_avin
, pred_avout
;
987 bb_info
= get_remat_bb_data (bb
);
988 bb_avin
= &bb_info
->avin_cands
;
989 pred_avout
= &get_remat_bb_data (pred
)->avout_cands
;
990 return bitmap_and_into (bb_avin
, pred_avout
);
993 /* Calculate available candidates for each BB. */
995 calculate_global_remat_bb_data (void)
1000 (DF_FORWARD
, NULL
, cand_pav_con_fun_0
, cand_pav_con_fun_n
,
1001 cand_pav_trans_fun
, &all_blocks
,
1002 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
1003 /* Initialize avin by pavin. */
1004 FOR_EACH_BB_FN (bb
, cfun
)
1005 bitmap_copy (&get_remat_bb_data (bb
)->avin_cands
,
1006 &get_remat_bb_data (bb
)->pavin_cands
);
1008 (DF_FORWARD
, NULL
, cand_av_con_fun_0
, cand_av_con_fun_n
,
1009 cand_av_trans_fun
, &all_blocks
,
1010 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
1015 /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
1017 change_sp_offset (rtx_insn
*insns
, HOST_WIDE_INT sp_offset
)
1019 for (rtx_insn
*insn
= insns
; insn
!= NULL
; insn
= NEXT_INSN (insn
))
1020 eliminate_regs_in_insn (insn
, false, false, sp_offset
);
1023 /* Return start hard register of REG (can be a hard or a pseudo reg)
1024 or -1 (if it is a spilled pseudo). Return number of hard registers
1025 occupied by REG through parameter NREGS if the start hard reg is
1028 get_hard_regs (struct lra_insn_reg
*reg
, int &nregs
)
1030 int regno
= reg
->regno
;
1031 int hard_regno
= regno
< FIRST_PSEUDO_REGISTER
? regno
: reg_renumber
[regno
];
1033 if (hard_regno
>= 0)
1034 nregs
= hard_regno_nregs
[hard_regno
][reg
->biggest_mode
];
1038 /* Make copy of and register scratch pseudos in rematerialized insn
1041 update_scratch_ops (rtx_insn
*remat_insn
)
1043 lra_insn_recog_data_t id
= lra_get_insn_recog_data (remat_insn
);
1044 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1045 for (int i
= 0; i
< static_id
->n_operands
; i
++)
1047 rtx
*loc
= id
->operand_loc
[i
];
1050 int regno
= REGNO (*loc
);
1051 if (! lra_former_scratch_p (regno
))
1053 *loc
= lra_create_new_reg (GET_MODE (*loc
), *loc
,
1054 lra_get_allocno_class (regno
),
1055 "scratch pseudo copy");
1056 lra_register_new_scratch_op (remat_insn
, i
);
1061 /* Insert rematerialization insns using the data-flow data calculated
1068 bitmap_head avail_cands
;
1069 bool changed_p
= false;
1070 /* Living hard regs and hard registers of living pseudos. */
1071 HARD_REG_SET live_hard_regs
;
1073 bitmap_initialize (&avail_cands
, ®_obstack
);
1074 FOR_EACH_BB_FN (bb
, cfun
)
1076 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_out (bb
));
1077 bitmap_and (&avail_cands
, &get_remat_bb_data (bb
)->avin_cands
,
1078 &get_remat_bb_data (bb
)->livein_cands
);
1079 FOR_BB_INSNS (bb
, insn
)
1081 if (!NONDEBUG_INSN_P (insn
))
1084 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
1085 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1086 struct lra_insn_reg
*reg
;
1091 int src_regno
= -1, dst_regno
= -1;
1093 if ((set
= single_set (insn
)) != NULL
1094 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
1096 src_regno
= REGNO (SET_SRC (set
));
1097 dst_regno
= REGNO (SET_DEST (set
));
1101 /* Check possibility of rematerialization (hard reg or
1102 unpsilled pseudo <- spilled pseudo): */
1103 if (dst_regno
>= 0 && src_regno
>= FIRST_PSEUDO_REGISTER
1104 && reg_renumber
[src_regno
] < 0
1105 && (dst_regno
< FIRST_PSEUDO_REGISTER
1106 || reg_renumber
[dst_regno
] >= 0))
1108 for (cand
= regno_cands
[src_regno
];
1110 cand
= cand
->next_regno_cand
)
1111 if (bitmap_bit_p (&avail_cands
, cand
->index
))
1114 int i
, hard_regno
, nregs
;
1115 rtx_insn
*remat_insn
= NULL
;
1116 HOST_WIDE_INT cand_sp_offset
= 0;
1119 lra_insn_recog_data_t cand_id
1120 = lra_get_insn_recog_data (cand
->insn
);
1121 struct lra_static_insn_data
*static_cand_id
1122 = cand_id
->insn_static_data
;
1123 rtx saved_op
= *cand_id
->operand_loc
[cand
->nop
];
1125 /* Check clobbers do not kill something living. */
1126 gcc_assert (REG_P (saved_op
));
1127 int ignore_regno
= REGNO (saved_op
);
1129 for (reg
= cand_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1130 if (reg
->type
!= OP_IN
&& reg
->regno
!= ignore_regno
)
1132 hard_regno
= get_hard_regs (reg
, nregs
);
1133 gcc_assert (hard_regno
>= 0);
1134 for (i
= 0; i
< nregs
; i
++)
1135 if (TEST_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
))
1143 for (reg
= static_cand_id
->hard_regs
;
1146 if (reg
->type
!= OP_IN
1147 && TEST_HARD_REG_BIT (live_hard_regs
, reg
->regno
))
1153 *cand_id
->operand_loc
[cand
->nop
] = SET_DEST (set
);
1154 lra_update_insn_regno_info (cand
->insn
);
1155 bool ok_p
= lra_constrain_insn (cand
->insn
);
1158 rtx remat_pat
= copy_insn (PATTERN (cand
->insn
));
1161 emit_insn (remat_pat
);
1162 remat_insn
= get_insns ();
1164 if (recog_memoized (remat_insn
) < 0)
1166 cand_sp_offset
= cand_id
->sp_offset
;
1168 *cand_id
->operand_loc
[cand
->nop
] = saved_op
;
1169 lra_update_insn_regno_info (cand
->insn
);
1173 bitmap_clear (&temp_bitmap
);
1174 /* Update avail_cands (see analogous code for
1175 calculate_gen_cands). */
1176 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1177 if (reg
->type
!= OP_IN
1178 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1179 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1181 cand
= all_cands
[cid
];
1183 /* Ignore the reload insn. */
1184 if (src_regno
== cand
->reload_regno
1185 && dst_regno
== cand
->regno
)
1187 if (cand
->regno
== reg
->regno
1188 || input_regno_present_p (cand
->insn
, reg
->regno
))
1189 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1193 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1195 cand
= all_cands
[cid
];
1197 if (call_used_input_regno_present_p (cand
->insn
))
1198 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1201 bitmap_and_compl_into (&avail_cands
, &temp_bitmap
);
1202 if ((cand
= insn_to_cand
[INSN_UID (insn
)]) != NULL
)
1203 bitmap_set_bit (&avail_cands
, cand
->index
);
1205 if (remat_insn
!= NULL
)
1207 HOST_WIDE_INT sp_offset_change
= cand_sp_offset
- id
->sp_offset
;
1208 if (sp_offset_change
!= 0)
1209 change_sp_offset (remat_insn
, sp_offset_change
);
1210 update_scratch_ops (remat_insn
);
1211 lra_process_new_insns (insn
, remat_insn
, NULL
,
1212 "Inserting rematerialization insn");
1213 lra_set_insn_deleted (insn
);
1218 /* Update live hard regs: */
1219 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1220 if (reg
->type
== OP_IN
1221 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1223 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1225 for (i
= 0; i
< nregs
; i
++)
1226 CLEAR_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1228 /* Process also hard regs (e.g. CC register) which are part
1229 of insn definition. */
1230 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1231 if (reg
->type
== OP_IN
1232 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1233 CLEAR_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1234 /* Inputs have been processed, now process outputs. */
1235 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1236 if (reg
->type
!= OP_IN
1237 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1239 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1241 for (i
= 0; i
< nregs
; i
++)
1242 SET_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1244 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1245 if (reg
->type
!= OP_IN
1246 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1247 SET_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1250 bitmap_clear (&avail_cands
);
1256 /* Current number of rematerialization iteration. */
1257 int lra_rematerialization_iter
;
1259 /* Entry point of the rematerialization sub-pass. Return true if we
1260 did any rematerialization. */
1266 int max_regno
= max_reg_num ();
1268 if (! flag_lra_remat
)
1270 lra_rematerialization_iter
++;
1271 if (lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
1273 if (lra_dump_file
!= NULL
)
1274 fprintf (lra_dump_file
,
1275 "\n******** Rematerialization #%d: ********\n\n",
1276 lra_rematerialization_iter
);
1277 timevar_push (TV_LRA_REMAT
);
1278 insn_to_cand
= XCNEWVEC (cand_t
, get_max_uid ());
1279 regno_cands
= XCNEWVEC (cand_t
, max_regno
);
1280 all_cands
.create (8000);
1281 call_used_regs_arr_len
= 0;
1282 for (int i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1283 if (call_used_regs
[i
])
1284 call_used_regs_arr
[call_used_regs_arr_len
++] = i
;
1285 initiate_cand_table ();
1287 create_remat_bb_data ();
1288 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1289 calculate_local_reg_remat_bb_data ();
1290 calculate_livein_cands ();
1291 calculate_gen_cands ();
1292 bitmap_initialize (&all_blocks
, ®_obstack
);
1293 FOR_ALL_BB_FN (bb
, cfun
)
1294 bitmap_set_bit (&all_blocks
, bb
->index
);
1295 calculate_global_remat_bb_data ();
1296 dump_candidates_and_remat_bb_data ();
1297 result
= do_remat ();
1298 all_cands
.release ();
1299 bitmap_clear (&temp_bitmap
);
1300 finish_remat_bb_data ();
1301 finish_cand_table ();
1302 bitmap_clear (&all_blocks
);
1304 free (insn_to_cand
);
1305 timevar_pop (TV_LRA_REMAT
);