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
;
115 /* A secondary map, for candidates that involve two insns, where the
116 second one makes the equivalence. The candidate must not be used
117 before seeing this activation insn. */
118 static cand_t
*insn_to_cand_activation
;
120 /* Map regno -> candidates can be used for the regno
121 rematerialization. */
122 static cand_t
*regno_cands
;
124 /* Data about basic blocks used for the rematerialization
128 /* Basic block about which the below data are. */
130 /* Registers changed in the basic block: */
131 bitmap_head changed_regs
;
132 /* Registers becoming dead in the BB. */
133 bitmap_head dead_regs
;
134 /* Cands present in the BB whose in/out regs are not changed after
135 the cands occurence and are not dead (except the reload
137 bitmap_head gen_cands
;
138 bitmap_head livein_cands
; /* cands whose inputs live at the BB start. */
139 bitmap_head pavin_cands
; /* cands partially available at BB entry. */
140 bitmap_head pavout_cands
; /* cands partially available at BB exit. */
141 bitmap_head avin_cands
; /* cands available at the entry of the BB. */
142 bitmap_head avout_cands
; /* cands available at the exit of the BB. */
145 /* Array for all BB data. Indexed by the corresponding BB index. */
146 typedef struct remat_bb_data
*remat_bb_data_t
;
148 /* Basic blocks for data flow problems -- all bocks except the special
150 static bitmap_head all_blocks
;
152 /* All basic block data are referred through the following array. */
153 static remat_bb_data_t remat_bb_data
;
155 /* Two small functions for access to the bb data. */
156 static inline remat_bb_data_t
157 get_remat_bb_data (basic_block bb
)
159 return &remat_bb_data
[(bb
)->index
];
162 static inline remat_bb_data_t
163 get_remat_bb_data_by_index (int index
)
165 return &remat_bb_data
[index
];
170 /* Hash table for the candidates. Different insns (e.g. structurally
171 the same insns or even insns with different unused output regs) can
172 be represented by the same candidate in the table. */
173 static htab_t cand_table
;
175 /* Hash function for candidate CAND. */
177 cand_hash (const void *cand
)
179 const_cand_t c
= (const_cand_t
) cand
;
180 lra_insn_recog_data_t id
= lra_get_insn_recog_data (c
->insn
);
181 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
182 int nops
= static_id
->n_operands
;
185 for (int i
= 0; i
< nops
; i
++)
187 hash
= iterative_hash_object (c
->regno
, hash
);
188 else if (static_id
->operand
[i
].type
== OP_IN
)
189 hash
= iterative_hash_object (*id
->operand_loc
[i
], hash
);
193 /* Equal function for candidates CAND1 and CAND2. They are equal if
194 the corresponding candidate insns have the same code, the same
195 regno for rematerialization, the same input operands. */
197 cand_eq_p (const void *cand1
, const void *cand2
)
199 const_cand_t c1
= (const_cand_t
) cand1
;
200 const_cand_t c2
= (const_cand_t
) cand2
;
201 lra_insn_recog_data_t id1
= lra_get_insn_recog_data (c1
->insn
);
202 lra_insn_recog_data_t id2
= lra_get_insn_recog_data (c2
->insn
);
203 struct lra_static_insn_data
*static_id1
= id1
->insn_static_data
;
204 int nops
= static_id1
->n_operands
;
206 if (c1
->regno
!= c2
->regno
207 || INSN_CODE (c1
->insn
) < 0
208 || INSN_CODE (c1
->insn
) != INSN_CODE (c2
->insn
))
210 gcc_assert (c1
->nop
== c2
->nop
);
211 for (int i
= 0; i
< nops
; i
++)
212 if (i
!= c1
->nop
&& static_id1
->operand
[i
].type
== OP_IN
213 && *id1
->operand_loc
[i
] != *id2
->operand_loc
[i
])
218 /* Insert candidate CAND into the table if it is not there yet.
219 Return candidate which is in the table. */
221 insert_cand (cand_t cand
)
225 entry_ptr
= htab_find_slot (cand_table
, cand
, INSERT
);
226 if (*entry_ptr
== NULL
)
227 *entry_ptr
= (void *) cand
;
228 return (cand_t
) *entry_ptr
;
231 /* Free candidate CAND memory. */
233 free_cand (void *cand
)
238 /* Initiate the candidate table. */
240 initiate_cand_table (void)
242 cand_table
= htab_create (8000, cand_hash
, cand_eq_p
,
243 (htab_del
) free_cand
);
246 /* Finish the candidate table. */
248 finish_cand_table (void)
250 htab_delete (cand_table
);
255 /* Return true if X contains memory or some UNSPEC. We can not just
256 check insn operands as memory or unspec might be not an operand
257 itself but contain an operand. Insn with memory access is not
258 profitable for rematerialization. Rematerialization of UNSPEC
259 might result in wrong code generation as the UNPEC effect is
260 unknown (e.g. generating a label). */
262 bad_for_rematerialization_p (rtx x
)
268 if (MEM_P (x
) || GET_CODE (x
) == UNSPEC
|| GET_CODE (x
) == UNSPEC_VOLATILE
)
271 fmt
= GET_RTX_FORMAT (code
);
272 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
276 if (bad_for_rematerialization_p (XEXP (x
, i
)))
279 else if (fmt
[i
] == 'E')
281 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
282 if (bad_for_rematerialization_p (XVECEXP (x
, i
, j
)))
289 /* If INSN can not be used for rematerialization, return negative
290 value. If INSN can be considered as a candidate for
291 rematerialization, return value which is the operand number of the
292 pseudo for which the insn can be used for rematerialization. Here
293 we consider the insns without any memory, spilled pseudo (except
294 for the rematerialization pseudo), or dying or unused regs. */
296 operand_to_remat (rtx_insn
*insn
)
298 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
299 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
300 struct lra_insn_reg
*reg
, *found_reg
= NULL
;
302 /* Don't rematerialize insns which can change PC. */
303 if (JUMP_P (insn
) || CALL_P (insn
))
305 /* First find a pseudo which can be rematerialized. */
306 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
308 /* True FRAME_POINTER_NEEDED might be because we can not follow
309 changing sp offsets, e.g. alloca is used. If the insn contains
310 stack pointer in such case, we can not rematerialize it as we
311 can not know sp offset at a rematerialization place. */
312 if (reg
->regno
== STACK_POINTER_REGNUM
&& frame_pointer_needed
)
314 else if (reg
->type
== OP_OUT
&& ! reg
->subreg_p
315 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
317 /* We permits only one spilled reg. */
318 if (found_reg
!= NULL
)
322 /* IRA calculates conflicts separately for subregs of two words
323 pseudo. Even if the pseudo lives, e.g. one its subreg can be
324 used lately, another subreg hard register can be already used
325 for something else. In such case, it is not safe to
326 rematerialize the insn. */
327 if (reg
->regno
>= FIRST_PSEUDO_REGISTER
328 && bitmap_bit_p (&subreg_regs
, reg
->regno
))
331 /* Don't allow hard registers to be rematerialized. */
332 if (reg
->regno
< FIRST_PSEUDO_REGISTER
)
335 if (found_reg
== NULL
)
337 if (found_reg
->regno
< FIRST_PSEUDO_REGISTER
)
339 if (bad_for_rematerialization_p (PATTERN (insn
)))
341 /* Check the other regs are not spilled. */
342 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
343 if (found_reg
== reg
)
345 else if (reg
->type
== OP_INOUT
)
347 else if (reg
->regno
>= FIRST_PSEUDO_REGISTER
348 && reg_renumber
[reg
->regno
] < 0)
349 /* Another spilled reg. */
351 else if (reg
->type
== OP_IN
)
353 if (find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
354 /* We don't want to make live ranges longer. */
356 /* Check that there is no output reg as the input one. */
357 for (struct lra_insn_reg
*reg2
= id
->regs
;
360 if (reg2
->type
== OP_OUT
&& reg
->regno
== reg2
->regno
)
362 if (reg
->regno
< FIRST_PSEUDO_REGISTER
)
363 for (struct lra_insn_reg
*reg2
= static_id
->hard_regs
;
366 if (reg2
->type
== OP_OUT
367 && reg
->regno
<= reg2
->regno
370 + hard_regno_nregs
[reg
->regno
][reg
->biggest_mode
])))
373 /* Find the rematerialization operand. */
374 int nop
= static_id
->n_operands
;
375 for (int i
= 0; i
< nop
; i
++)
376 if (REG_P (*id
->operand_loc
[i
])
377 && (int) REGNO (*id
->operand_loc
[i
]) == found_reg
->regno
)
382 /* Create candidate for INSN with rematerialization operand NOP and
383 REGNO. Insert the candidate into the table and set up the
384 corresponding INSN_TO_CAND element. */
386 create_cand (rtx_insn
*insn
, int nop
, int regno
, rtx_insn
*activation
= NULL
)
388 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
389 rtx reg
= *id
->operand_loc
[nop
];
390 gcc_assert (REG_P (reg
));
391 int op_regno
= REGNO (reg
);
392 gcc_assert (op_regno
>= FIRST_PSEUDO_REGISTER
);
393 cand_t cand
= XNEW (struct cand
);
397 cand
->reload_regno
= op_regno
== regno
? -1 : op_regno
;
398 gcc_assert (cand
->regno
>= 0);
399 cand_t cand_in_table
= insert_cand (cand
);
400 insn_to_cand
[INSN_UID (insn
)] = cand_in_table
;
401 if (cand
!= cand_in_table
)
406 cand
->index
= all_cands
.length ();
407 all_cands
.safe_push (cand
);
408 cand
->next_regno_cand
= regno_cands
[cand
->regno
];
409 regno_cands
[cand
->regno
] = cand
;
412 insn_to_cand_activation
[INSN_UID (activation
)] = cand_in_table
;
415 /* Create rematerialization candidates (inserting them into the
421 struct potential_cand
426 struct potential_cand
*regno_potential_cand
;
428 /* Create candidates. */
429 regno_potential_cand
= XCNEWVEC (struct potential_cand
, max_reg_num ());
430 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
431 if (NONDEBUG_INSN_P (insn
))
433 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
435 rtx set
= single_set (insn
);
438 /* See if this is an output reload for a previous insn. */
440 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
442 rtx dstreg
= SET_DEST (set
);
443 int src_regno
= REGNO (SET_SRC (set
));
444 int dst_regno
= REGNO (dstreg
);
445 rtx_insn
*insn2
= regno_potential_cand
[src_regno
].insn
;
448 && dst_regno
>= FIRST_PSEUDO_REGISTER
449 && reg_renumber
[dst_regno
] < 0
450 && BLOCK_FOR_INSN (insn2
) == BLOCK_FOR_INSN (insn
))
452 create_cand (insn2
, regno_potential_cand
[src_regno
].nop
,
458 nop
= operand_to_remat (insn
);
461 gcc_assert (REG_P (*id
->operand_loc
[nop
]));
462 int regno
= REGNO (*id
->operand_loc
[nop
]);
463 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
464 /* If we're setting an unrenumbered pseudo, make a candidate immediately.
465 If it's an output reload register, save it for later; the code above
466 looks for output reload insns later on. */
467 if (reg_renumber
[regno
] < 0)
468 create_cand (insn
, nop
, regno
);
469 else if (regno
>= lra_constraint_new_regno_start
)
471 regno_potential_cand
[regno
].insn
= insn
;
472 regno_potential_cand
[regno
].nop
= nop
;
478 for (struct lra_insn_reg
*reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
479 if (reg
->type
!= OP_IN
&& reg
->regno
!= keep_regno
480 && reg
->regno
>= FIRST_PSEUDO_REGISTER
)
481 regno_potential_cand
[reg
->regno
].insn
= NULL
;
483 cands_num
= all_cands
.length ();
484 free (regno_potential_cand
);
489 /* Create and initialize BB data. */
491 create_remat_bb_data (void)
494 remat_bb_data_t bb_info
;
496 remat_bb_data
= XNEWVEC (struct remat_bb_data
,
497 last_basic_block_for_fn (cfun
));
498 FOR_ALL_BB_FN (bb
, cfun
)
500 gcc_checking_assert (bb
->index
>= 0
501 && bb
->index
< last_basic_block_for_fn (cfun
));
502 bb_info
= get_remat_bb_data (bb
);
504 bitmap_initialize (&bb_info
->changed_regs
, ®_obstack
);
505 bitmap_initialize (&bb_info
->dead_regs
, ®_obstack
);
506 bitmap_initialize (&bb_info
->gen_cands
, ®_obstack
);
507 bitmap_initialize (&bb_info
->livein_cands
, ®_obstack
);
508 bitmap_initialize (&bb_info
->pavin_cands
, ®_obstack
);
509 bitmap_initialize (&bb_info
->pavout_cands
, ®_obstack
);
510 bitmap_initialize (&bb_info
->avin_cands
, ®_obstack
);
511 bitmap_initialize (&bb_info
->avout_cands
, ®_obstack
);
515 /* Dump all candidates to DUMP_FILE. */
517 dump_cands (FILE *dump_file
)
522 fprintf (dump_file
, "\nCands:\n");
523 for (i
= 0; i
< (int) cands_num
; i
++)
526 fprintf (dump_file
, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
527 i
, cand
->nop
, cand
->regno
, cand
->reload_regno
);
528 print_inline_rtx (dump_file
, cand
->insn
, 6);
529 fprintf (dump_file
, "\n");
533 /* Dump all candidates and BB data. */
535 dump_candidates_and_remat_bb_data (void)
539 if (lra_dump_file
== NULL
)
541 dump_cands (lra_dump_file
);
542 FOR_EACH_BB_FN (bb
, cfun
)
544 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
546 fprintf (lra_dump_file
, " register live in:");
547 dump_regset (df_get_live_in (bb
), lra_dump_file
);
548 putc ('\n', lra_dump_file
);
550 fprintf (lra_dump_file
, " register live out:");
551 dump_regset (df_get_live_out (bb
), lra_dump_file
);
552 putc ('\n', lra_dump_file
);
553 /* Changed/dead regs: */
554 fprintf (lra_dump_file
, " changed regs:");
555 dump_regset (&get_remat_bb_data (bb
)->changed_regs
, lra_dump_file
);
556 putc ('\n', lra_dump_file
);
557 fprintf (lra_dump_file
, " dead regs:");
558 dump_regset (&get_remat_bb_data (bb
)->dead_regs
, lra_dump_file
);
559 putc ('\n', lra_dump_file
);
560 lra_dump_bitmap_with_title ("cands generated in BB",
561 &get_remat_bb_data (bb
)->gen_cands
, bb
->index
);
562 lra_dump_bitmap_with_title ("livein cands in BB",
563 &get_remat_bb_data (bb
)->livein_cands
, bb
->index
);
564 lra_dump_bitmap_with_title ("pavin cands in BB",
565 &get_remat_bb_data (bb
)->pavin_cands
, bb
->index
);
566 lra_dump_bitmap_with_title ("pavout cands in BB",
567 &get_remat_bb_data (bb
)->pavout_cands
, bb
->index
);
568 lra_dump_bitmap_with_title ("avin cands in BB",
569 &get_remat_bb_data (bb
)->avin_cands
, bb
->index
);
570 lra_dump_bitmap_with_title ("avout cands in BB",
571 &get_remat_bb_data (bb
)->avout_cands
, bb
->index
);
573 fprintf (lra_dump_file
, "subreg regs:");
574 dump_regset (&subreg_regs
, lra_dump_file
);
575 putc ('\n', lra_dump_file
);
578 /* Free all BB data. */
580 finish_remat_bb_data (void)
584 FOR_EACH_BB_FN (bb
, cfun
)
586 bitmap_clear (&get_remat_bb_data (bb
)->avout_cands
);
587 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
588 bitmap_clear (&get_remat_bb_data (bb
)->pavout_cands
);
589 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
590 bitmap_clear (&get_remat_bb_data (bb
)->livein_cands
);
591 bitmap_clear (&get_remat_bb_data (bb
)->gen_cands
);
592 bitmap_clear (&get_remat_bb_data (bb
)->dead_regs
);
593 bitmap_clear (&get_remat_bb_data (bb
)->changed_regs
);
595 free (remat_bb_data
);
600 /* Update changed_regs, dead_regs, subreg_regs of BB from INSN. */
602 set_bb_regs (basic_block bb
, rtx_insn
*insn
)
604 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
605 remat_bb_data_t bb_info
= get_remat_bb_data (bb
);
606 struct lra_insn_reg
*reg
;
608 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
610 unsigned regno
= reg
->regno
;
611 if (reg
->type
!= OP_IN
)
612 bitmap_set_bit (&bb_info
->changed_regs
, regno
);
613 else if (find_regno_note (insn
, REG_DEAD
, regno
) != NULL
)
614 bitmap_set_bit (&bb_info
->dead_regs
, regno
);
615 if (regno
>= FIRST_PSEUDO_REGISTER
&& reg
->subreg_p
)
616 bitmap_set_bit (&subreg_regs
, regno
);
619 for (int i
= 0; i
< call_used_regs_arr_len
; i
++)
620 bitmap_set_bit (&get_remat_bb_data (bb
)->dead_regs
,
621 call_used_regs_arr
[i
]);
624 /* Calculate changed_regs and dead_regs for each BB. */
626 calculate_local_reg_remat_bb_data (void)
631 FOR_EACH_BB_FN (bb
, cfun
)
632 FOR_BB_INSNS (bb
, insn
)
633 if (NONDEBUG_INSN_P (insn
))
634 set_bb_regs (bb
, insn
);
639 /* Return true if REG overlaps an input operand of INSN. */
641 reg_overlap_for_remat_p (lra_insn_reg
*reg
, rtx_insn
*insn
)
644 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
645 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
646 unsigned regno
= reg
->regno
;
649 if (regno
>= FIRST_PSEUDO_REGISTER
&& reg_renumber
[regno
] >= 0)
650 regno
= reg_renumber
[regno
];
651 if (regno
>= FIRST_PSEUDO_REGISTER
)
654 nregs
= hard_regno_nregs
[regno
][reg
->biggest_mode
];
656 struct lra_insn_reg
*reg2
;
658 for (iter
= 0; iter
< 2; iter
++)
659 for (reg2
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
663 if (reg2
->type
!= OP_IN
)
665 unsigned regno2
= reg2
->regno
;
668 if (regno2
>= FIRST_PSEUDO_REGISTER
&& reg_renumber
[regno2
] >= 0)
669 regno2
= reg_renumber
[regno2
];
670 if (regno
>= FIRST_PSEUDO_REGISTER
)
673 nregs2
= hard_regno_nregs
[regno2
][reg
->biggest_mode
];
675 if ((regno2
+ nregs2
- 1 >= regno
&& regno2
< regno
+ nregs
)
676 || (regno
+ nregs
- 1 >= regno2
&& regno
< regno2
+ nregs2
))
682 /* Return true if a call used register is an input operand of INSN. */
684 call_used_input_regno_present_p (rtx_insn
*insn
)
687 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
688 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
689 struct lra_insn_reg
*reg
;
691 for (iter
= 0; iter
< 2; iter
++)
692 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
695 if (reg
->type
== OP_IN
&& reg
->regno
<= FIRST_PSEUDO_REGISTER
696 && TEST_HARD_REG_BIT (call_used_reg_set
, reg
->regno
))
701 /* Calculate livein_cands for each BB. */
703 calculate_livein_cands (void)
707 FOR_EACH_BB_FN (bb
, cfun
)
709 bitmap livein_regs
= df_get_live_in (bb
);
710 bitmap livein_cands
= &get_remat_bb_data (bb
)->livein_cands
;
711 for (unsigned int i
= 0; i
< cands_num
; i
++)
713 cand_t cand
= all_cands
[i
];
714 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
715 struct lra_insn_reg
*reg
;
717 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
718 if (reg
->type
== OP_IN
&& ! bitmap_bit_p (livein_regs
, reg
->regno
))
721 bitmap_set_bit (livein_cands
, i
);
726 /* Calculate gen_cands for each BB. */
728 calculate_gen_cands (void)
732 bitmap_head gen_insns
;
735 bitmap_initialize (&gen_insns
, ®_obstack
);
736 FOR_EACH_BB_FN (bb
, cfun
)
738 gen_cands
= &get_remat_bb_data (bb
)->gen_cands
;
739 bitmap_clear (&gen_insns
);
740 FOR_BB_INSNS (bb
, insn
)
743 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
744 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
745 struct lra_insn_reg
*reg
;
751 int src_regno
= -1, dst_regno
= -1;
753 if ((set
= single_set (insn
)) != NULL
754 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
756 src_regno
= REGNO (SET_SRC (set
));
757 dst_regno
= REGNO (SET_DEST (set
));
760 /* Update gen_cands: */
761 bitmap_clear (&temp_bitmap
);
762 for (iter
= 0; iter
< 2; iter
++)
763 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
766 if (reg
->type
!= OP_IN
767 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
768 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
770 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
772 cand
= insn_to_cand
[INSN_UID (insn2
)];
773 gcc_assert (cand
!= NULL
);
774 /* Ignore the reload insn. */
775 if (src_regno
== cand
->reload_regno
776 && dst_regno
== cand
->regno
)
778 if (cand
->regno
== reg
->regno
779 || reg_overlap_for_remat_p (reg
, insn2
))
781 bitmap_clear_bit (gen_cands
, cand
->index
);
782 bitmap_set_bit (&temp_bitmap
, uid
);
787 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
789 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
791 cand
= insn_to_cand
[INSN_UID (insn2
)];
792 gcc_assert (cand
!= NULL
);
793 if (call_used_input_regno_present_p (insn2
))
795 bitmap_clear_bit (gen_cands
, cand
->index
);
796 bitmap_set_bit (&temp_bitmap
, uid
);
799 bitmap_and_compl_into (&gen_insns
, &temp_bitmap
);
801 cand
= insn_to_cand
[INSN_UID (insn
)];
804 bitmap_set_bit (gen_cands
, cand
->index
);
805 bitmap_set_bit (&gen_insns
, INSN_UID (insn
));
809 bitmap_clear (&gen_insns
);
814 /* The common transfer function used by the DF equation solver to
815 propagate (partial) availability info BB_IN to BB_OUT through block
816 with BB_INDEX according to the following equation:
818 bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
821 cand_trans_fun (int bb_index
, bitmap bb_in
, bitmap bb_out
)
823 remat_bb_data_t bb_info
;
824 bitmap bb_livein
, bb_changed_regs
, bb_dead_regs
;
828 bb_info
= get_remat_bb_data_by_index (bb_index
);
829 bb_livein
= &bb_info
->livein_cands
;
830 bb_changed_regs
= &bb_info
->changed_regs
;
831 bb_dead_regs
= &bb_info
->dead_regs
;
832 /* Calculate killed avin cands -- cands whose regs are changed or
833 becoming dead in the BB. We calculate it here as we hope that
834 repeated calculations are compensated by smaller size of BB_IN in
835 comparison with all candidates number. */
836 bitmap_clear (&temp_bitmap
);
837 EXECUTE_IF_SET_IN_BITMAP (bb_in
, 0, cid
, bi
)
839 cand_t cand
= all_cands
[cid
];
840 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
841 struct lra_insn_reg
*reg
;
843 if (! bitmap_bit_p (bb_livein
, cid
))
845 bitmap_set_bit (&temp_bitmap
, cid
);
848 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
849 /* Ignore all outputs which are not the regno for
850 rematerialization. */
851 if (reg
->type
== OP_OUT
&& reg
->regno
!= cand
->regno
)
853 else if (bitmap_bit_p (bb_changed_regs
, reg
->regno
)
854 || bitmap_bit_p (bb_dead_regs
, reg
->regno
))
856 bitmap_set_bit (&temp_bitmap
, cid
);
859 /* Check regno for rematerialization. */
860 if (bitmap_bit_p (bb_changed_regs
, cand
->regno
)
861 || bitmap_bit_p (bb_dead_regs
, cand
->regno
))
862 bitmap_set_bit (&temp_bitmap
, cid
);
864 return bitmap_ior_and_compl (bb_out
,
865 &bb_info
->gen_cands
, bb_in
, &temp_bitmap
);
870 /* The transfer function used by the DF equation solver to propagate
871 partial candidate availability info through block with BB_INDEX
872 according to the following equation:
874 bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
877 cand_pav_trans_fun (int bb_index
)
879 remat_bb_data_t bb_info
;
881 bb_info
= get_remat_bb_data_by_index (bb_index
);
882 return cand_trans_fun (bb_index
, &bb_info
->pavin_cands
,
883 &bb_info
->pavout_cands
);
886 /* The confluence function used by the DF equation solver to set up
887 cand_pav info for a block BB without predecessor. */
889 cand_pav_con_fun_0 (basic_block bb
)
891 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
894 /* The confluence function used by the DF equation solver to propagate
895 partial candidate availability info from predecessor to successor
896 on edge E (pred->bb) according to the following equation:
898 bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
901 cand_pav_con_fun_n (edge e
)
903 basic_block pred
= e
->src
;
904 basic_block bb
= e
->dest
;
905 remat_bb_data_t bb_info
;
906 bitmap bb_pavin
, pred_pavout
;
908 bb_info
= get_remat_bb_data (bb
);
909 bb_pavin
= &bb_info
->pavin_cands
;
910 pred_pavout
= &get_remat_bb_data (pred
)->pavout_cands
;
911 return bitmap_ior_into (bb_pavin
, pred_pavout
);
916 /* The transfer function used by the DF equation solver to propagate
917 candidate availability info through block with BB_INDEX according
918 to the following equation:
920 bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
923 cand_av_trans_fun (int bb_index
)
925 remat_bb_data_t bb_info
;
927 bb_info
= get_remat_bb_data_by_index (bb_index
);
928 return cand_trans_fun (bb_index
, &bb_info
->avin_cands
,
929 &bb_info
->avout_cands
);
932 /* The confluence function used by the DF equation solver to set up
933 cand_av info for a block BB without predecessor. */
935 cand_av_con_fun_0 (basic_block bb
)
937 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
940 /* The confluence function used by the DF equation solver to propagate
941 cand_av info from predecessor to successor on edge E (pred->bb)
942 according to the following equation:
944 bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
947 cand_av_con_fun_n (edge e
)
949 basic_block pred
= e
->src
;
950 basic_block bb
= e
->dest
;
951 remat_bb_data_t bb_info
;
952 bitmap bb_avin
, pred_avout
;
954 bb_info
= get_remat_bb_data (bb
);
955 bb_avin
= &bb_info
->avin_cands
;
956 pred_avout
= &get_remat_bb_data (pred
)->avout_cands
;
957 return bitmap_and_into (bb_avin
, pred_avout
);
960 /* Calculate available candidates for each BB. */
962 calculate_global_remat_bb_data (void)
967 (DF_FORWARD
, NULL
, cand_pav_con_fun_0
, cand_pav_con_fun_n
,
968 cand_pav_trans_fun
, &all_blocks
,
969 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
970 /* Initialize avin by pavin. */
971 FOR_EACH_BB_FN (bb
, cfun
)
972 bitmap_copy (&get_remat_bb_data (bb
)->avin_cands
,
973 &get_remat_bb_data (bb
)->pavin_cands
);
975 (DF_FORWARD
, NULL
, cand_av_con_fun_0
, cand_av_con_fun_n
,
976 cand_av_trans_fun
, &all_blocks
,
977 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
982 /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
984 change_sp_offset (rtx_insn
*insns
, HOST_WIDE_INT sp_offset
)
986 for (rtx_insn
*insn
= insns
; insn
!= NULL
; insn
= NEXT_INSN (insn
))
987 eliminate_regs_in_insn (insn
, false, false, sp_offset
);
990 /* Return start hard register of REG (can be a hard or a pseudo reg)
991 or -1 (if it is a spilled pseudo). Return number of hard registers
992 occupied by REG through parameter NREGS if the start hard reg is
995 get_hard_regs (struct lra_insn_reg
*reg
, int &nregs
)
997 int regno
= reg
->regno
;
998 int hard_regno
= regno
< FIRST_PSEUDO_REGISTER
? regno
: reg_renumber
[regno
];
1000 if (hard_regno
>= 0)
1001 nregs
= hard_regno_nregs
[hard_regno
][reg
->biggest_mode
];
1005 /* Make copy of and register scratch pseudos in rematerialized insn
1008 update_scratch_ops (rtx_insn
*remat_insn
)
1010 lra_insn_recog_data_t id
= lra_get_insn_recog_data (remat_insn
);
1011 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1012 for (int i
= 0; i
< static_id
->n_operands
; i
++)
1014 rtx
*loc
= id
->operand_loc
[i
];
1017 int regno
= REGNO (*loc
);
1018 if (! lra_former_scratch_p (regno
))
1020 *loc
= lra_create_new_reg (GET_MODE (*loc
), *loc
,
1021 lra_get_allocno_class (regno
),
1022 "scratch pseudo copy");
1023 lra_register_new_scratch_op (remat_insn
, i
);
1028 /* Insert rematerialization insns using the data-flow data calculated
1035 bitmap_head avail_cands
;
1036 bitmap_head active_cands
;
1037 bool changed_p
= false;
1038 /* Living hard regs and hard registers of living pseudos. */
1039 HARD_REG_SET live_hard_regs
;
1041 bitmap_initialize (&avail_cands
, ®_obstack
);
1042 bitmap_initialize (&active_cands
, ®_obstack
);
1043 FOR_EACH_BB_FN (bb
, cfun
)
1045 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_out (bb
));
1046 bitmap_and (&avail_cands
, &get_remat_bb_data (bb
)->avin_cands
,
1047 &get_remat_bb_data (bb
)->livein_cands
);
1048 /* Activating insns are always in the same block as their corresponding
1049 remat insn, so at the start of a block the two bitsets are equal. */
1050 bitmap_copy (&active_cands
, &avail_cands
);
1051 FOR_BB_INSNS (bb
, insn
)
1053 if (!NONDEBUG_INSN_P (insn
))
1056 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
1057 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1058 struct lra_insn_reg
*reg
;
1064 int src_regno
= -1, dst_regno
= -1;
1066 if ((set
= single_set (insn
)) != NULL
1067 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
1069 src_regno
= REGNO (SET_SRC (set
));
1070 dst_regno
= REGNO (SET_DEST (set
));
1074 /* Check possibility of rematerialization (hard reg or
1075 unpsilled pseudo <- spilled pseudo): */
1076 if (dst_regno
>= 0 && src_regno
>= FIRST_PSEUDO_REGISTER
1077 && reg_renumber
[src_regno
] < 0
1078 && (dst_regno
< FIRST_PSEUDO_REGISTER
1079 || reg_renumber
[dst_regno
] >= 0))
1081 for (cand
= regno_cands
[src_regno
];
1083 cand
= cand
->next_regno_cand
)
1084 if (bitmap_bit_p (&avail_cands
, cand
->index
)
1085 && bitmap_bit_p (&active_cands
, cand
->index
))
1088 int i
, hard_regno
, nregs
;
1089 rtx_insn
*remat_insn
= NULL
;
1090 HOST_WIDE_INT cand_sp_offset
= 0;
1093 lra_insn_recog_data_t cand_id
1094 = lra_get_insn_recog_data (cand
->insn
);
1095 struct lra_static_insn_data
*static_cand_id
1096 = cand_id
->insn_static_data
;
1097 rtx saved_op
= *cand_id
->operand_loc
[cand
->nop
];
1099 /* Check clobbers do not kill something living. */
1100 gcc_assert (REG_P (saved_op
));
1101 int ignore_regno
= REGNO (saved_op
);
1103 for (reg
= cand_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1104 if (reg
->type
!= OP_IN
&& reg
->regno
!= ignore_regno
)
1106 hard_regno
= get_hard_regs (reg
, nregs
);
1107 gcc_assert (hard_regno
>= 0);
1108 for (i
= 0; i
< nregs
; i
++)
1109 if (TEST_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
))
1117 for (reg
= static_cand_id
->hard_regs
;
1120 if (reg
->type
!= OP_IN
1121 && TEST_HARD_REG_BIT (live_hard_regs
, reg
->regno
))
1127 *cand_id
->operand_loc
[cand
->nop
] = SET_DEST (set
);
1128 lra_update_insn_regno_info (cand
->insn
);
1129 bool ok_p
= lra_constrain_insn (cand
->insn
);
1132 rtx remat_pat
= copy_insn (PATTERN (cand
->insn
));
1135 emit_insn (remat_pat
);
1136 remat_insn
= get_insns ();
1138 if (recog_memoized (remat_insn
) < 0)
1140 cand_sp_offset
= cand_id
->sp_offset
;
1142 *cand_id
->operand_loc
[cand
->nop
] = saved_op
;
1143 lra_update_insn_regno_info (cand
->insn
);
1147 bitmap_clear (&temp_bitmap
);
1148 /* Update avail_cands (see analogous code for
1149 calculate_gen_cands). */
1150 for (iter
= 0; iter
< 2; iter
++)
1151 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
1154 if (reg
->type
!= OP_IN
1155 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1156 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1158 cand
= all_cands
[cid
];
1160 /* Ignore the reload insn. */
1161 if (src_regno
== cand
->reload_regno
1162 && dst_regno
== cand
->regno
)
1164 if (cand
->regno
== reg
->regno
1165 || reg_overlap_for_remat_p (reg
, cand
->insn
))
1166 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1170 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1172 cand
= all_cands
[cid
];
1174 if (call_used_input_regno_present_p (cand
->insn
))
1175 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1178 bitmap_and_compl_into (&avail_cands
, &temp_bitmap
);
1180 /* Now see whether a candidate is made active or available
1182 cand
= insn_to_cand_activation
[INSN_UID (insn
)];
1184 bitmap_set_bit (&active_cands
, cand
->index
);
1186 cand
= insn_to_cand
[INSN_UID (insn
)];
1189 bitmap_set_bit (&avail_cands
, cand
->index
);
1190 if (cand
->reload_regno
== -1)
1191 bitmap_set_bit (&active_cands
, cand
->index
);
1193 bitmap_clear_bit (&active_cands
, cand
->index
);
1196 if (remat_insn
!= NULL
)
1198 HOST_WIDE_INT sp_offset_change
= cand_sp_offset
- id
->sp_offset
;
1199 if (sp_offset_change
!= 0)
1200 change_sp_offset (remat_insn
, sp_offset_change
);
1201 update_scratch_ops (remat_insn
);
1202 lra_process_new_insns (insn
, remat_insn
, NULL
,
1203 "Inserting rematerialization insn");
1204 lra_set_insn_deleted (insn
);
1209 /* Update live hard regs: */
1210 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1211 if (reg
->type
== OP_IN
1212 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1214 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1216 for (i
= 0; i
< nregs
; i
++)
1217 CLEAR_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1219 /* Process also hard regs (e.g. CC register) which are part
1220 of insn definition. */
1221 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1222 if (reg
->type
== OP_IN
1223 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1224 CLEAR_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1225 /* Inputs have been processed, now process outputs. */
1226 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1227 if (reg
->type
!= OP_IN
1228 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1230 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1232 for (i
= 0; i
< nregs
; i
++)
1233 SET_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1235 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1236 if (reg
->type
!= OP_IN
1237 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1238 SET_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1241 bitmap_clear (&avail_cands
);
1242 bitmap_clear (&active_cands
);
1248 /* Current number of rematerialization iteration. */
1249 int lra_rematerialization_iter
;
1251 /* Entry point of the rematerialization sub-pass. Return true if we
1252 did any rematerialization. */
1258 int max_regno
= max_reg_num ();
1260 if (! flag_lra_remat
)
1262 lra_rematerialization_iter
++;
1263 if (lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
1265 if (lra_dump_file
!= NULL
)
1266 fprintf (lra_dump_file
,
1267 "\n******** Rematerialization #%d: ********\n\n",
1268 lra_rematerialization_iter
);
1269 timevar_push (TV_LRA_REMAT
);
1270 insn_to_cand
= XCNEWVEC (cand_t
, get_max_uid ());
1271 insn_to_cand_activation
= XCNEWVEC (cand_t
, get_max_uid ());
1272 regno_cands
= XCNEWVEC (cand_t
, max_regno
);
1273 all_cands
.create (8000);
1274 call_used_regs_arr_len
= 0;
1275 for (int i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1276 if (call_used_regs
[i
])
1277 call_used_regs_arr
[call_used_regs_arr_len
++] = i
;
1278 initiate_cand_table ();
1279 create_remat_bb_data ();
1280 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1281 bitmap_initialize (&subreg_regs
, ®_obstack
);
1282 calculate_local_reg_remat_bb_data ();
1284 calculate_livein_cands ();
1285 calculate_gen_cands ();
1286 bitmap_initialize (&all_blocks
, ®_obstack
);
1287 FOR_ALL_BB_FN (bb
, cfun
)
1288 bitmap_set_bit (&all_blocks
, bb
->index
);
1289 calculate_global_remat_bb_data ();
1290 dump_candidates_and_remat_bb_data ();
1291 result
= do_remat ();
1292 all_cands
.release ();
1293 bitmap_clear (&temp_bitmap
);
1294 bitmap_clear (&subreg_regs
);
1295 finish_remat_bb_data ();
1296 finish_cand_table ();
1297 bitmap_clear (&all_blocks
);
1299 free (insn_to_cand
);
1300 free (insn_to_cand_activation
);
1301 timevar_pop (TV_LRA_REMAT
);