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 /* Check hard coded insn registers. */
374 for (struct lra_insn_reg
*reg
= static_id
->hard_regs
;
377 if (reg
->type
== OP_INOUT
)
379 else if (reg
->type
== OP_IN
)
381 /* Check that there is no output hard reg as the input
383 for (struct lra_insn_reg
*reg2
= static_id
->hard_regs
;
386 if (reg2
->type
== OP_OUT
&& reg
->regno
== reg2
->regno
)
389 /* Find the rematerialization operand. */
390 int nop
= static_id
->n_operands
;
391 for (int i
= 0; i
< nop
; i
++)
392 if (REG_P (*id
->operand_loc
[i
])
393 && (int) REGNO (*id
->operand_loc
[i
]) == found_reg
->regno
)
398 /* Create candidate for INSN with rematerialization operand NOP and
399 REGNO. Insert the candidate into the table and set up the
400 corresponding INSN_TO_CAND element. */
402 create_cand (rtx_insn
*insn
, int nop
, int regno
, rtx_insn
*activation
= NULL
)
404 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
405 rtx reg
= *id
->operand_loc
[nop
];
406 gcc_assert (REG_P (reg
));
407 int op_regno
= REGNO (reg
);
408 gcc_assert (op_regno
>= FIRST_PSEUDO_REGISTER
);
409 cand_t cand
= XNEW (struct cand
);
413 cand
->reload_regno
= op_regno
== regno
? -1 : op_regno
;
414 gcc_assert (cand
->regno
>= 0);
415 cand_t cand_in_table
= insert_cand (cand
);
416 insn_to_cand
[INSN_UID (insn
)] = cand_in_table
;
417 if (cand
!= cand_in_table
)
422 cand
->index
= all_cands
.length ();
423 all_cands
.safe_push (cand
);
424 cand
->next_regno_cand
= regno_cands
[cand
->regno
];
425 regno_cands
[cand
->regno
] = cand
;
428 insn_to_cand_activation
[INSN_UID (activation
)] = cand_in_table
;
431 /* Create rematerialization candidates (inserting them into the
437 struct potential_cand
442 struct potential_cand
*regno_potential_cand
;
444 /* Create candidates. */
445 regno_potential_cand
= XCNEWVEC (struct potential_cand
, max_reg_num ());
446 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
447 if (NONDEBUG_INSN_P (insn
))
449 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
451 rtx set
= single_set (insn
);
454 /* See if this is an output reload for a previous insn. */
456 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
458 rtx dstreg
= SET_DEST (set
);
459 int src_regno
= REGNO (SET_SRC (set
));
460 int dst_regno
= REGNO (dstreg
);
461 rtx_insn
*insn2
= regno_potential_cand
[src_regno
].insn
;
464 && dst_regno
>= FIRST_PSEUDO_REGISTER
465 && reg_renumber
[dst_regno
] < 0
466 && BLOCK_FOR_INSN (insn2
) == BLOCK_FOR_INSN (insn
))
468 create_cand (insn2
, regno_potential_cand
[src_regno
].nop
,
474 nop
= operand_to_remat (insn
);
477 gcc_assert (REG_P (*id
->operand_loc
[nop
]));
478 int regno
= REGNO (*id
->operand_loc
[nop
]);
479 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
480 /* If we're setting an unrenumbered pseudo, make a candidate immediately.
481 If it's an output reload register, save it for later; the code above
482 looks for output reload insns later on. */
483 if (reg_renumber
[regno
] < 0)
484 create_cand (insn
, nop
, regno
);
485 else if (regno
>= lra_constraint_new_regno_start
)
487 regno_potential_cand
[regno
].insn
= insn
;
488 regno_potential_cand
[regno
].nop
= nop
;
494 for (struct lra_insn_reg
*reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
495 if (reg
->type
!= OP_IN
&& reg
->regno
!= keep_regno
496 && reg
->regno
>= FIRST_PSEUDO_REGISTER
)
497 regno_potential_cand
[reg
->regno
].insn
= NULL
;
499 cands_num
= all_cands
.length ();
500 free (regno_potential_cand
);
505 /* Create and initialize BB data. */
507 create_remat_bb_data (void)
510 remat_bb_data_t bb_info
;
512 remat_bb_data
= XNEWVEC (struct remat_bb_data
,
513 last_basic_block_for_fn (cfun
));
514 FOR_ALL_BB_FN (bb
, cfun
)
516 gcc_checking_assert (bb
->index
>= 0
517 && bb
->index
< last_basic_block_for_fn (cfun
));
518 bb_info
= get_remat_bb_data (bb
);
520 bitmap_initialize (&bb_info
->changed_regs
, ®_obstack
);
521 bitmap_initialize (&bb_info
->dead_regs
, ®_obstack
);
522 bitmap_initialize (&bb_info
->gen_cands
, ®_obstack
);
523 bitmap_initialize (&bb_info
->livein_cands
, ®_obstack
);
524 bitmap_initialize (&bb_info
->pavin_cands
, ®_obstack
);
525 bitmap_initialize (&bb_info
->pavout_cands
, ®_obstack
);
526 bitmap_initialize (&bb_info
->avin_cands
, ®_obstack
);
527 bitmap_initialize (&bb_info
->avout_cands
, ®_obstack
);
531 /* Dump all candidates to DUMP_FILE. */
533 dump_cands (FILE *dump_file
)
538 fprintf (dump_file
, "\nCands:\n");
539 for (i
= 0; i
< (int) cands_num
; i
++)
542 fprintf (dump_file
, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
543 i
, cand
->nop
, cand
->regno
, cand
->reload_regno
);
544 print_inline_rtx (dump_file
, cand
->insn
, 6);
545 fprintf (dump_file
, "\n");
549 /* Dump all candidates and BB data. */
551 dump_candidates_and_remat_bb_data (void)
555 if (lra_dump_file
== NULL
)
557 dump_cands (lra_dump_file
);
558 FOR_EACH_BB_FN (bb
, cfun
)
560 fprintf (lra_dump_file
, "\nBB %d:\n", bb
->index
);
562 fprintf (lra_dump_file
, " register live in:");
563 dump_regset (df_get_live_in (bb
), lra_dump_file
);
564 putc ('\n', lra_dump_file
);
566 fprintf (lra_dump_file
, " register live out:");
567 dump_regset (df_get_live_out (bb
), lra_dump_file
);
568 putc ('\n', lra_dump_file
);
569 /* Changed/dead regs: */
570 fprintf (lra_dump_file
, " changed regs:");
571 dump_regset (&get_remat_bb_data (bb
)->changed_regs
, lra_dump_file
);
572 putc ('\n', lra_dump_file
);
573 fprintf (lra_dump_file
, " dead regs:");
574 dump_regset (&get_remat_bb_data (bb
)->dead_regs
, lra_dump_file
);
575 putc ('\n', lra_dump_file
);
576 lra_dump_bitmap_with_title ("cands generated in BB",
577 &get_remat_bb_data (bb
)->gen_cands
, bb
->index
);
578 lra_dump_bitmap_with_title ("livein cands in BB",
579 &get_remat_bb_data (bb
)->livein_cands
, bb
->index
);
580 lra_dump_bitmap_with_title ("pavin cands in BB",
581 &get_remat_bb_data (bb
)->pavin_cands
, bb
->index
);
582 lra_dump_bitmap_with_title ("pavout cands in BB",
583 &get_remat_bb_data (bb
)->pavout_cands
, bb
->index
);
584 lra_dump_bitmap_with_title ("avin cands in BB",
585 &get_remat_bb_data (bb
)->avin_cands
, bb
->index
);
586 lra_dump_bitmap_with_title ("avout cands in BB",
587 &get_remat_bb_data (bb
)->avout_cands
, bb
->index
);
589 fprintf (lra_dump_file
, "subreg regs:");
590 dump_regset (&subreg_regs
, lra_dump_file
);
591 putc ('\n', lra_dump_file
);
594 /* Free all BB data. */
596 finish_remat_bb_data (void)
600 FOR_EACH_BB_FN (bb
, cfun
)
602 bitmap_clear (&get_remat_bb_data (bb
)->avout_cands
);
603 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
604 bitmap_clear (&get_remat_bb_data (bb
)->pavout_cands
);
605 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
606 bitmap_clear (&get_remat_bb_data (bb
)->livein_cands
);
607 bitmap_clear (&get_remat_bb_data (bb
)->gen_cands
);
608 bitmap_clear (&get_remat_bb_data (bb
)->dead_regs
);
609 bitmap_clear (&get_remat_bb_data (bb
)->changed_regs
);
611 free (remat_bb_data
);
616 /* Update changed_regs, dead_regs, subreg_regs of BB from INSN. */
618 set_bb_regs (basic_block bb
, rtx_insn
*insn
)
620 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
621 remat_bb_data_t bb_info
= get_remat_bb_data (bb
);
622 struct lra_insn_reg
*reg
;
624 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
626 unsigned regno
= reg
->regno
;
627 if (reg
->type
!= OP_IN
)
628 bitmap_set_bit (&bb_info
->changed_regs
, regno
);
629 else if (find_regno_note (insn
, REG_DEAD
, regno
) != NULL
)
630 bitmap_set_bit (&bb_info
->dead_regs
, regno
);
631 if (regno
>= FIRST_PSEUDO_REGISTER
&& reg
->subreg_p
)
632 bitmap_set_bit (&subreg_regs
, regno
);
635 for (int i
= 0; i
< call_used_regs_arr_len
; i
++)
636 bitmap_set_bit (&get_remat_bb_data (bb
)->dead_regs
,
637 call_used_regs_arr
[i
]);
640 /* Calculate changed_regs and dead_regs for each BB. */
642 calculate_local_reg_remat_bb_data (void)
647 FOR_EACH_BB_FN (bb
, cfun
)
648 FOR_BB_INSNS (bb
, insn
)
649 if (NONDEBUG_INSN_P (insn
))
650 set_bb_regs (bb
, insn
);
655 /* Return true if REG overlaps an input operand of INSN. */
657 reg_overlap_for_remat_p (lra_insn_reg
*reg
, rtx_insn
*insn
)
660 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
661 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
662 unsigned regno
= reg
->regno
;
665 if (regno
>= FIRST_PSEUDO_REGISTER
&& reg_renumber
[regno
] >= 0)
666 regno
= reg_renumber
[regno
];
667 if (regno
>= FIRST_PSEUDO_REGISTER
)
670 nregs
= hard_regno_nregs
[regno
][reg
->biggest_mode
];
672 struct lra_insn_reg
*reg2
;
674 for (iter
= 0; iter
< 2; iter
++)
675 for (reg2
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
679 if (reg2
->type
!= OP_IN
)
681 unsigned regno2
= reg2
->regno
;
684 if (regno2
>= FIRST_PSEUDO_REGISTER
&& reg_renumber
[regno2
] >= 0)
685 regno2
= reg_renumber
[regno2
];
686 if (regno
>= FIRST_PSEUDO_REGISTER
)
689 nregs2
= hard_regno_nregs
[regno2
][reg
->biggest_mode
];
691 if ((regno2
+ nregs2
- 1 >= regno
&& regno2
< regno
+ nregs
)
692 || (regno
+ nregs
- 1 >= regno2
&& regno
< regno2
+ nregs2
))
698 /* Return true if a call used register is an input operand of INSN. */
700 call_used_input_regno_present_p (rtx_insn
*insn
)
703 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
704 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
705 struct lra_insn_reg
*reg
;
707 for (iter
= 0; iter
< 2; iter
++)
708 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
711 if (reg
->type
== OP_IN
&& reg
->regno
<= FIRST_PSEUDO_REGISTER
712 && TEST_HARD_REG_BIT (call_used_reg_set
, reg
->regno
))
717 /* Calculate livein_cands for each BB. */
719 calculate_livein_cands (void)
723 FOR_EACH_BB_FN (bb
, cfun
)
725 bitmap livein_regs
= df_get_live_in (bb
);
726 bitmap livein_cands
= &get_remat_bb_data (bb
)->livein_cands
;
727 for (unsigned int i
= 0; i
< cands_num
; i
++)
729 cand_t cand
= all_cands
[i
];
730 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
731 struct lra_insn_reg
*reg
;
733 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
734 if (reg
->type
== OP_IN
&& ! bitmap_bit_p (livein_regs
, reg
->regno
))
737 bitmap_set_bit (livein_cands
, i
);
742 /* Calculate gen_cands for each BB. */
744 calculate_gen_cands (void)
748 bitmap_head gen_insns
;
751 bitmap_initialize (&gen_insns
, ®_obstack
);
752 FOR_EACH_BB_FN (bb
, cfun
)
754 gen_cands
= &get_remat_bb_data (bb
)->gen_cands
;
755 bitmap_clear (&gen_insns
);
756 FOR_BB_INSNS (bb
, insn
)
759 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
760 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
761 struct lra_insn_reg
*reg
;
767 int src_regno
= -1, dst_regno
= -1;
769 if ((set
= single_set (insn
)) != NULL
770 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
772 src_regno
= REGNO (SET_SRC (set
));
773 dst_regno
= REGNO (SET_DEST (set
));
776 /* Update gen_cands: */
777 bitmap_clear (&temp_bitmap
);
778 for (iter
= 0; iter
< 2; iter
++)
779 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
782 if (reg
->type
!= OP_IN
783 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
784 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
786 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
788 cand
= insn_to_cand
[INSN_UID (insn2
)];
789 gcc_assert (cand
!= NULL
);
790 /* Ignore the reload insn. */
791 if (src_regno
== cand
->reload_regno
792 && dst_regno
== cand
->regno
)
794 if (cand
->regno
== reg
->regno
795 || reg_overlap_for_remat_p (reg
, insn2
))
797 bitmap_clear_bit (gen_cands
, cand
->index
);
798 bitmap_set_bit (&temp_bitmap
, uid
);
803 EXECUTE_IF_SET_IN_BITMAP (&gen_insns
, 0, uid
, bi
)
805 rtx_insn
*insn2
= lra_insn_recog_data
[uid
]->insn
;
807 cand
= insn_to_cand
[INSN_UID (insn2
)];
808 gcc_assert (cand
!= NULL
);
809 if (call_used_input_regno_present_p (insn2
))
811 bitmap_clear_bit (gen_cands
, cand
->index
);
812 bitmap_set_bit (&temp_bitmap
, uid
);
815 bitmap_and_compl_into (&gen_insns
, &temp_bitmap
);
817 cand
= insn_to_cand
[INSN_UID (insn
)];
820 bitmap_set_bit (gen_cands
, cand
->index
);
821 bitmap_set_bit (&gen_insns
, INSN_UID (insn
));
825 bitmap_clear (&gen_insns
);
830 /* The common transfer function used by the DF equation solver to
831 propagate (partial) availability info BB_IN to BB_OUT through block
832 with BB_INDEX according to the following equation:
834 bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
837 cand_trans_fun (int bb_index
, bitmap bb_in
, bitmap bb_out
)
839 remat_bb_data_t bb_info
;
840 bitmap bb_livein
, bb_changed_regs
, bb_dead_regs
;
844 bb_info
= get_remat_bb_data_by_index (bb_index
);
845 bb_livein
= &bb_info
->livein_cands
;
846 bb_changed_regs
= &bb_info
->changed_regs
;
847 bb_dead_regs
= &bb_info
->dead_regs
;
848 /* Calculate killed avin cands -- cands whose regs are changed or
849 becoming dead in the BB. We calculate it here as we hope that
850 repeated calculations are compensated by smaller size of BB_IN in
851 comparison with all candidates number. */
852 bitmap_clear (&temp_bitmap
);
853 EXECUTE_IF_SET_IN_BITMAP (bb_in
, 0, cid
, bi
)
855 cand_t cand
= all_cands
[cid
];
856 lra_insn_recog_data_t id
= lra_get_insn_recog_data (cand
->insn
);
857 struct lra_insn_reg
*reg
;
859 if (! bitmap_bit_p (bb_livein
, cid
))
861 bitmap_set_bit (&temp_bitmap
, cid
);
864 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
865 /* Ignore all outputs which are not the regno for
866 rematerialization. */
867 if (reg
->type
== OP_OUT
&& reg
->regno
!= cand
->regno
)
869 else if (bitmap_bit_p (bb_changed_regs
, reg
->regno
)
870 || bitmap_bit_p (bb_dead_regs
, reg
->regno
))
872 bitmap_set_bit (&temp_bitmap
, cid
);
875 /* Check regno for rematerialization. */
876 if (bitmap_bit_p (bb_changed_regs
, cand
->regno
)
877 || bitmap_bit_p (bb_dead_regs
, cand
->regno
))
878 bitmap_set_bit (&temp_bitmap
, cid
);
880 return bitmap_ior_and_compl (bb_out
,
881 &bb_info
->gen_cands
, bb_in
, &temp_bitmap
);
886 /* The transfer function used by the DF equation solver to propagate
887 partial candidate availability info through block with BB_INDEX
888 according to the following equation:
890 bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
893 cand_pav_trans_fun (int bb_index
)
895 remat_bb_data_t bb_info
;
897 bb_info
= get_remat_bb_data_by_index (bb_index
);
898 return cand_trans_fun (bb_index
, &bb_info
->pavin_cands
,
899 &bb_info
->pavout_cands
);
902 /* The confluence function used by the DF equation solver to set up
903 cand_pav info for a block BB without predecessor. */
905 cand_pav_con_fun_0 (basic_block bb
)
907 bitmap_clear (&get_remat_bb_data (bb
)->pavin_cands
);
910 /* The confluence function used by the DF equation solver to propagate
911 partial candidate availability info from predecessor to successor
912 on edge E (pred->bb) according to the following equation:
914 bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
917 cand_pav_con_fun_n (edge e
)
919 basic_block pred
= e
->src
;
920 basic_block bb
= e
->dest
;
921 remat_bb_data_t bb_info
;
922 bitmap bb_pavin
, pred_pavout
;
924 bb_info
= get_remat_bb_data (bb
);
925 bb_pavin
= &bb_info
->pavin_cands
;
926 pred_pavout
= &get_remat_bb_data (pred
)->pavout_cands
;
927 return bitmap_ior_into (bb_pavin
, pred_pavout
);
932 /* The transfer function used by the DF equation solver to propagate
933 candidate availability info through block with BB_INDEX according
934 to the following equation:
936 bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
939 cand_av_trans_fun (int bb_index
)
941 remat_bb_data_t bb_info
;
943 bb_info
= get_remat_bb_data_by_index (bb_index
);
944 return cand_trans_fun (bb_index
, &bb_info
->avin_cands
,
945 &bb_info
->avout_cands
);
948 /* The confluence function used by the DF equation solver to set up
949 cand_av info for a block BB without predecessor. */
951 cand_av_con_fun_0 (basic_block bb
)
953 bitmap_clear (&get_remat_bb_data (bb
)->avin_cands
);
956 /* The confluence function used by the DF equation solver to propagate
957 cand_av info from predecessor to successor on edge E (pred->bb)
958 according to the following equation:
960 bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
963 cand_av_con_fun_n (edge e
)
965 basic_block pred
= e
->src
;
966 basic_block bb
= e
->dest
;
967 remat_bb_data_t bb_info
;
968 bitmap bb_avin
, pred_avout
;
970 bb_info
= get_remat_bb_data (bb
);
971 bb_avin
= &bb_info
->avin_cands
;
972 pred_avout
= &get_remat_bb_data (pred
)->avout_cands
;
973 return bitmap_and_into (bb_avin
, pred_avout
);
976 /* Calculate available candidates for each BB. */
978 calculate_global_remat_bb_data (void)
983 (DF_FORWARD
, NULL
, cand_pav_con_fun_0
, cand_pav_con_fun_n
,
984 cand_pav_trans_fun
, &all_blocks
,
985 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
986 /* Initialize avin by pavin. */
987 FOR_EACH_BB_FN (bb
, cfun
)
988 bitmap_copy (&get_remat_bb_data (bb
)->avin_cands
,
989 &get_remat_bb_data (bb
)->pavin_cands
);
991 (DF_FORWARD
, NULL
, cand_av_con_fun_0
, cand_av_con_fun_n
,
992 cand_av_trans_fun
, &all_blocks
,
993 df_get_postorder (DF_FORWARD
), df_get_n_blocks (DF_FORWARD
));
998 /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
1000 change_sp_offset (rtx_insn
*insns
, HOST_WIDE_INT sp_offset
)
1002 for (rtx_insn
*insn
= insns
; insn
!= NULL
; insn
= NEXT_INSN (insn
))
1003 eliminate_regs_in_insn (insn
, false, false, sp_offset
);
1006 /* Return start hard register of REG (can be a hard or a pseudo reg)
1007 or -1 (if it is a spilled pseudo). Return number of hard registers
1008 occupied by REG through parameter NREGS if the start hard reg is
1011 get_hard_regs (struct lra_insn_reg
*reg
, int &nregs
)
1013 int regno
= reg
->regno
;
1014 int hard_regno
= regno
< FIRST_PSEUDO_REGISTER
? regno
: reg_renumber
[regno
];
1016 if (hard_regno
>= 0)
1017 nregs
= hard_regno_nregs
[hard_regno
][reg
->biggest_mode
];
1021 /* Make copy of and register scratch pseudos in rematerialized insn
1024 update_scratch_ops (rtx_insn
*remat_insn
)
1026 lra_insn_recog_data_t id
= lra_get_insn_recog_data (remat_insn
);
1027 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1028 for (int i
= 0; i
< static_id
->n_operands
; i
++)
1030 rtx
*loc
= id
->operand_loc
[i
];
1033 int regno
= REGNO (*loc
);
1034 if (! lra_former_scratch_p (regno
))
1036 *loc
= lra_create_new_reg (GET_MODE (*loc
), *loc
,
1037 lra_get_allocno_class (regno
),
1038 "scratch pseudo copy");
1039 lra_register_new_scratch_op (remat_insn
, i
);
1044 /* Insert rematerialization insns using the data-flow data calculated
1051 bitmap_head avail_cands
;
1052 bitmap_head active_cands
;
1053 bool changed_p
= false;
1054 /* Living hard regs and hard registers of living pseudos. */
1055 HARD_REG_SET live_hard_regs
;
1057 bitmap_initialize (&avail_cands
, ®_obstack
);
1058 bitmap_initialize (&active_cands
, ®_obstack
);
1059 FOR_EACH_BB_FN (bb
, cfun
)
1061 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_out (bb
));
1062 bitmap_and (&avail_cands
, &get_remat_bb_data (bb
)->avin_cands
,
1063 &get_remat_bb_data (bb
)->livein_cands
);
1064 /* Activating insns are always in the same block as their corresponding
1065 remat insn, so at the start of a block the two bitsets are equal. */
1066 bitmap_copy (&active_cands
, &avail_cands
);
1067 FOR_BB_INSNS (bb
, insn
)
1069 if (!NONDEBUG_INSN_P (insn
))
1072 lra_insn_recog_data_t id
= lra_get_insn_recog_data (insn
);
1073 struct lra_static_insn_data
*static_id
= id
->insn_static_data
;
1074 struct lra_insn_reg
*reg
;
1080 int src_regno
= -1, dst_regno
= -1;
1082 if ((set
= single_set (insn
)) != NULL
1083 && REG_P (SET_SRC (set
)) && REG_P (SET_DEST (set
)))
1085 src_regno
= REGNO (SET_SRC (set
));
1086 dst_regno
= REGNO (SET_DEST (set
));
1090 /* Check possibility of rematerialization (hard reg or
1091 unpsilled pseudo <- spilled pseudo): */
1092 if (dst_regno
>= 0 && src_regno
>= FIRST_PSEUDO_REGISTER
1093 && reg_renumber
[src_regno
] < 0
1094 && (dst_regno
< FIRST_PSEUDO_REGISTER
1095 || reg_renumber
[dst_regno
] >= 0))
1097 for (cand
= regno_cands
[src_regno
];
1099 cand
= cand
->next_regno_cand
)
1100 if (bitmap_bit_p (&avail_cands
, cand
->index
)
1101 && bitmap_bit_p (&active_cands
, cand
->index
))
1104 int i
, hard_regno
, nregs
;
1105 rtx_insn
*remat_insn
= NULL
;
1106 HOST_WIDE_INT cand_sp_offset
= 0;
1109 lra_insn_recog_data_t cand_id
1110 = lra_get_insn_recog_data (cand
->insn
);
1111 struct lra_static_insn_data
*static_cand_id
1112 = cand_id
->insn_static_data
;
1113 rtx saved_op
= *cand_id
->operand_loc
[cand
->nop
];
1115 /* Check clobbers do not kill something living. */
1116 gcc_assert (REG_P (saved_op
));
1117 int ignore_regno
= REGNO (saved_op
);
1119 for (reg
= cand_id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1120 if (reg
->type
!= OP_IN
&& reg
->regno
!= ignore_regno
)
1122 hard_regno
= get_hard_regs (reg
, nregs
);
1123 gcc_assert (hard_regno
>= 0);
1124 for (i
= 0; i
< nregs
; i
++)
1125 if (TEST_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
))
1133 for (reg
= static_cand_id
->hard_regs
;
1136 if (reg
->type
!= OP_IN
1137 && TEST_HARD_REG_BIT (live_hard_regs
, reg
->regno
))
1143 *cand_id
->operand_loc
[cand
->nop
] = SET_DEST (set
);
1144 lra_update_insn_regno_info (cand
->insn
);
1145 bool ok_p
= lra_constrain_insn (cand
->insn
);
1148 rtx remat_pat
= copy_insn (PATTERN (cand
->insn
));
1151 emit_insn (remat_pat
);
1152 remat_insn
= get_insns ();
1154 if (recog_memoized (remat_insn
) < 0)
1156 cand_sp_offset
= cand_id
->sp_offset
;
1158 *cand_id
->operand_loc
[cand
->nop
] = saved_op
;
1159 lra_update_insn_regno_info (cand
->insn
);
1163 bitmap_clear (&temp_bitmap
);
1164 /* Update avail_cands (see analogous code for
1165 calculate_gen_cands). */
1166 for (iter
= 0; iter
< 2; iter
++)
1167 for (reg
= (iter
== 0 ? id
->regs
: static_id
->hard_regs
);
1170 if (reg
->type
!= OP_IN
1171 || find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1172 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1174 cand
= all_cands
[cid
];
1176 /* Ignore the reload insn. */
1177 if (src_regno
== cand
->reload_regno
1178 && dst_regno
== cand
->regno
)
1180 if (cand
->regno
== reg
->regno
1181 || reg_overlap_for_remat_p (reg
, cand
->insn
))
1182 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1186 EXECUTE_IF_SET_IN_BITMAP (&avail_cands
, 0, cid
, bi
)
1188 cand
= all_cands
[cid
];
1190 if (call_used_input_regno_present_p (cand
->insn
))
1191 bitmap_set_bit (&temp_bitmap
, cand
->index
);
1194 bitmap_and_compl_into (&avail_cands
, &temp_bitmap
);
1196 /* Now see whether a candidate is made active or available
1198 cand
= insn_to_cand_activation
[INSN_UID (insn
)];
1200 bitmap_set_bit (&active_cands
, cand
->index
);
1202 cand
= insn_to_cand
[INSN_UID (insn
)];
1205 bitmap_set_bit (&avail_cands
, cand
->index
);
1206 if (cand
->reload_regno
== -1)
1207 bitmap_set_bit (&active_cands
, cand
->index
);
1209 bitmap_clear_bit (&active_cands
, cand
->index
);
1212 if (remat_insn
!= NULL
)
1214 HOST_WIDE_INT sp_offset_change
= cand_sp_offset
- id
->sp_offset
;
1215 if (sp_offset_change
!= 0)
1216 change_sp_offset (remat_insn
, sp_offset_change
);
1217 update_scratch_ops (remat_insn
);
1218 lra_process_new_insns (insn
, remat_insn
, NULL
,
1219 "Inserting rematerialization insn");
1220 lra_set_insn_deleted (insn
);
1225 /* Update live hard regs: */
1226 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1227 if (reg
->type
== OP_IN
1228 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1230 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1232 for (i
= 0; i
< nregs
; i
++)
1233 CLEAR_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1235 /* Process also hard regs (e.g. CC register) which are part
1236 of insn definition. */
1237 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1238 if (reg
->type
== OP_IN
1239 && find_regno_note (insn
, REG_DEAD
, reg
->regno
) != NULL
)
1240 CLEAR_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1241 /* Inputs have been processed, now process outputs. */
1242 for (reg
= id
->regs
; reg
!= NULL
; reg
= reg
->next
)
1243 if (reg
->type
!= OP_IN
1244 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1246 if ((hard_regno
= get_hard_regs (reg
, nregs
)) < 0)
1248 for (i
= 0; i
< nregs
; i
++)
1249 SET_HARD_REG_BIT (live_hard_regs
, hard_regno
+ i
);
1251 for (reg
= static_id
->hard_regs
; reg
!= NULL
; reg
= reg
->next
)
1252 if (reg
->type
!= OP_IN
1253 && find_regno_note (insn
, REG_UNUSED
, reg
->regno
) == NULL
)
1254 SET_HARD_REG_BIT (live_hard_regs
, reg
->regno
);
1257 bitmap_clear (&avail_cands
);
1258 bitmap_clear (&active_cands
);
1264 /* Current number of rematerialization iteration. */
1265 int lra_rematerialization_iter
;
1267 /* Entry point of the rematerialization sub-pass. Return true if we
1268 did any rematerialization. */
1274 int max_regno
= max_reg_num ();
1276 if (! flag_lra_remat
)
1278 lra_rematerialization_iter
++;
1279 if (lra_rematerialization_iter
> LRA_MAX_REMATERIALIZATION_PASSES
)
1281 if (lra_dump_file
!= NULL
)
1282 fprintf (lra_dump_file
,
1283 "\n******** Rematerialization #%d: ********\n\n",
1284 lra_rematerialization_iter
);
1285 timevar_push (TV_LRA_REMAT
);
1286 insn_to_cand
= XCNEWVEC (cand_t
, get_max_uid ());
1287 insn_to_cand_activation
= XCNEWVEC (cand_t
, get_max_uid ());
1288 regno_cands
= XCNEWVEC (cand_t
, max_regno
);
1289 all_cands
.create (8000);
1290 call_used_regs_arr_len
= 0;
1291 for (int i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1292 if (call_used_regs
[i
])
1293 call_used_regs_arr
[call_used_regs_arr_len
++] = i
;
1294 initiate_cand_table ();
1295 create_remat_bb_data ();
1296 bitmap_initialize (&temp_bitmap
, ®_obstack
);
1297 bitmap_initialize (&subreg_regs
, ®_obstack
);
1298 calculate_local_reg_remat_bb_data ();
1300 calculate_livein_cands ();
1301 calculate_gen_cands ();
1302 bitmap_initialize (&all_blocks
, ®_obstack
);
1303 FOR_ALL_BB_FN (bb
, cfun
)
1304 bitmap_set_bit (&all_blocks
, bb
->index
);
1305 calculate_global_remat_bb_data ();
1306 dump_candidates_and_remat_bb_data ();
1307 result
= do_remat ();
1308 all_cands
.release ();
1309 bitmap_clear (&temp_bitmap
);
1310 bitmap_clear (&subreg_regs
);
1311 finish_remat_bb_data ();
1312 finish_cand_table ();
1313 bitmap_clear (&all_blocks
);
1315 free (insn_to_cand
);
1316 free (insn_to_cand_activation
);
1317 timevar_pop (TV_LRA_REMAT
);