1 /* Early (pre-RA) rematerialization
2 Copyright (C) 2017-2019 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "tree-pass.h"
29 #include "insn-config.h"
31 /* FIXME: The next two are only needed for gen_move_insn. */
37 #include "print-rtl.h"
40 /* This pass runs before register allocation and implements an aggressive
41 form of rematerialization. It looks for pseudo registers R of mode M
44 (a) there are no call-preserved registers of mode M; and
45 (b) spilling R to the stack is expensive.
47 The assumption is that it's better to recompute R after each call instead
48 of spilling it, even if this extends the live ranges of other registers.
50 The motivating example for which these conditions hold are AArch64 SVE
51 vectors and predicates. Spilling them to the stack makes the frame
52 variable-sized, which we'd like to avoid if possible. It's also very
53 rare for SVE values to be "naturally" live across a call: usually this
54 happens as a result of CSE or other code motion.
56 The pass is split into the following phases:
61 First we go through all pseudo registers looking for any that meet
62 the conditions above. For each such register R, we go through each
63 instruction that defines R to see whether any of them are suitable
64 rematerialization candidates. If at least one is, we treat all the
65 instructions that define R as candidates, but record which ones are
66 not in fact suitable. These unsuitable candidates exist only for the
67 sake of calculating reaching definitions (see below).
69 A "candidate" is a single instruction that we want to rematerialize
70 and a "candidate register" is a register that is set by at least one
76 Next we sort the candidates based on the cfg postorder, so that if
77 candidate C1 uses candidate C2, C1 has a lower index than C2.
78 This is useful when iterating through candidate bitmaps.
80 Reaching definition calculation
81 ===============================
83 We then compute standard reaching-definition sets for each candidate.
84 Each set specifies which candidates might provide the current definition
85 of a live candidate register.
87 From here on, a candidate C is "live" at a point P if the candidate
88 register defined by C is live at P and if C's definition reaches P.
89 An instruction I "uses" a candidate C if I takes the register defined by
90 C as input and if C is one of the reaching definitions of that register.
92 Candidate validation and value numbering
93 ========================================
95 Next we simultaneously decide which candidates are valid and look
96 for candidates that are equivalent to each other, assigning numbers
97 to each unique candidate value. A candidate C is invalid if:
99 (a) C uses an invalid candidate;
101 (b) there is a cycle of candidate uses involving C; or
103 (c) C takes a candidate register R as input and the reaching
104 definitions of R do not have the same value number.
106 We assign a "representative" candidate C to each value number and from
107 here on replace references to other candidates with that value number
108 with references to C. It is then only possible to rematerialize a
109 register R at point P if (after this replacement) there is a single
110 reaching definition of R at P.
115 During this phase we go through each block and look for cases in which:
117 (a) an instruction I comes between two call instructions CI1 and CI2;
119 (b) I uses a candidate register R;
121 (c) a candidate C provides the only reaching definition of R; and
123 (d) C does not come between CI1 and I.
125 We then emit a copy of C after CI1, as well as the transitive closure
126 TC of the candidates used by C. The copies of TC might use the original
127 candidate registers or new temporary registers, depending on circumstances.
129 For example, if elsewhere we have:
135 C1: R1 <- f1 (R2, R3, ...) // uses C2 and C3
137 then for a block containing:
150 C1': R1 <- f1 (R2', R3', ...)
156 where R2' and R3' might be fresh registers. If instead we had:
160 I1: use R1 // uses C1
162 I2: use R3 // uses C3
166 we would keep the original R3:
171 C1': R1 <- f1 (R2', R3, ...)
173 I1: use R1 // uses C1
175 I2: use R3 // uses C3
179 We also record the last call in each block (if any) and compute:
182 The set of candidates that either (a) are defined outside the block
183 and are live after the last call or (b) are defined within the block
184 and reach the end of the last call. (We don't track whether the
185 latter values are live or not.)
188 The set of candidates that need to be rematerialized after the
189 last call in order to satisfy uses in the block itself.
192 The set of candidates that are live on entry to the block and are
193 used without an intervening call.
195 In addition, we compute the initial values of the sets required by
196 the global phase below.
201 We next compute a maximal solution to the following availability
205 The set of candidates that are live on entry to a block and can
206 be used at that point without rematerialization.
209 The set of candidates that are live on exit from a block and can
210 be used at that point without rematerialization.
213 The subset of available_out that is due to code in the block itself.
214 It contains candidates that are defined or used in the block and
215 not invalidated by a later call.
217 We then go through each block B and look for an appropriate place
218 to insert copies of required_in - available_in. Conceptually we
219 start by placing the copies at the head of B, but then move the
220 copy of a candidate C to predecessors if:
222 (a) that seems cheaper;
224 (b) there is more than one reaching definition of C's register at
227 (c) copying C would clobber a hard register that is live on entry to B.
229 Moving a copy of C to a predecessor block PB involves:
231 (1) adding C to PB's required_after_call, if PB contains a call; or
233 (2) adding C PB's required_in otherwise.
235 C is then available on output from each PB and on input to B.
237 Once all this is done, we emit instructions for the final required_in
238 and required_after_call sets. */
242 /* An invalid candidate index, used to indicate that there is more than
243 one reaching definition. */
244 const unsigned int MULTIPLE_CANDIDATES
= -1U;
246 /* Pass-specific information about one basic block. */
247 struct remat_block_info
{
248 /* The last call instruction in the block. */
251 /* The set of candidates that are live on entry to the block. NULL is
252 equivalent to an empty set. */
255 /* The set of candidates that are live on exit from the block. This might
256 reuse rd_in. NULL is equivalent to an empty set. */
259 /* The subset of RD_OUT that comes from local definitions. NULL is
260 equivalent to an empty set. */
263 /* The set of candidates that the block invalidates (because it defines
264 the register to something else, or because the register's value is
265 no longer important). NULL is equivalent to an empty set. */
268 /* The set of candidates that either (a) are defined outside the block
269 and are live after LAST_CALL or (b) are defined within the block
270 and reach the instruction after LAST_CALL. (We don't track whether
271 the latter values are live or not.)
273 Only used if LAST_CALL is nonnull. NULL is equivalent to an
275 bitmap rd_after_call
;
277 /* Candidates that are live and available without rematerialization
278 on entry to the block. NULL is equivalent to an empty set. */
281 /* Candidates that become available without rematerialization within the
282 block, and remain so on exit. NULL is equivalent to an empty set. */
283 bitmap available_locally
;
285 /* Candidates that are available without rematerialization on exit from
286 the block. This might reuse available_in or available_locally. */
287 bitmap available_out
;
289 /* Candidates that need to be rematerialized either at the start of the
290 block or before entering the block. */
293 /* Candidates that need to be rematerialized after LAST_CALL.
294 Only used if LAST_CALL is nonnull. */
295 bitmap required_after_call
;
297 /* The number of candidates in the block. */
298 unsigned int num_candidates
;
300 /* The earliest candidate in the block (i.e. the one with the
301 highest index). Only valid if NUM_CANDIDATES is nonzero. */
302 unsigned int first_candidate
;
304 /* The best (lowest) execution frequency for rematerializing REQUIRED_IN.
305 This is the execution frequency of the block if LOCAL_REMAT_CHEAPER_P,
306 otherwise it is the sum of the execution frequencies of whichever
307 predecessor blocks would do the rematerialization. */
310 /* True if the block ends with an abnormal call. */
311 unsigned int abnormal_call_p
: 1;
313 /* Used to record whether a graph traversal has visited this block. */
314 unsigned int visited_p
: 1;
316 /* True if we have calculated REMAT_FREQUENCY. */
317 unsigned int remat_frequency_valid_p
: 1;
319 /* True if it is cheaper to rematerialize candidates at the start of
320 the block, rather than moving them to predecessor blocks. */
321 unsigned int local_remat_cheaper_p
: 1;
324 /* Information about a group of candidates with the same value number. */
325 struct remat_equiv_class
{
326 /* The candidates that have the same value number. */
329 /* The candidate that was first added to MEMBERS. */
330 unsigned int earliest
;
332 /* The candidate that represents the others. This is always the one
333 with the highest index. */
334 unsigned int representative
;
337 /* Information about an instruction that we might want to rematerialize. */
338 struct remat_candidate
{
339 /* The pseudo register that the instruction sets. */
342 /* A temporary register used when rematerializing uses of this candidate,
343 if REGNO doesn't have the right value or isn't worth using. */
344 unsigned int copy_regno
;
346 /* True if we intend to rematerialize this instruction by emitting
347 a move of a constant into REGNO, false if we intend to emit a
348 copy of the original instruction. */
349 unsigned int constant_p
: 1;
351 /* True if we still think it's possible to rematerialize INSN. */
352 unsigned int can_copy_p
: 1;
354 /* Used to record whether a graph traversal has visited this candidate. */
355 unsigned int visited_p
: 1;
357 /* True if we have verified that it's possible to rematerialize INSN.
358 Once this is true, both it and CAN_COPY_P remain true. */
359 unsigned int validated_p
: 1;
361 /* True if we have "stabilized" INSN, i.e. ensured that all non-candidate
362 registers read by INSN will have the same value when rematerializing INSN.
363 Only ever true if CAN_COPY_P. */
364 unsigned int stabilized_p
: 1;
366 /* Hash value used for value numbering. */
369 /* The instruction that sets REGNO. */
372 /* If CONSTANT_P, the value that should be moved into REGNO when
373 rematerializing, otherwise the pattern of the instruction that
377 /* The set of candidates that INSN takes as input. NULL is equivalent
378 to the empty set. All candidates in this set have a higher index
379 than the current candidate. */
382 /* The set of hard registers that would be clobbered by rematerializing
383 the candidate, including (transitively) all those that would be
384 clobbered by rematerializing USES. */
387 /* The equivalence class to which the candidate belongs, or null if none. */
388 remat_equiv_class
*equiv_class
;
391 /* Hash functions used for value numbering. */
392 struct remat_candidate_hasher
: nofree_ptr_hash
<remat_candidate
>
394 typedef value_type compare_type
;
395 static hashval_t
hash (const remat_candidate
*);
396 static bool equal (const remat_candidate
*, const remat_candidate
*);
399 /* Main class for this pass. */
402 early_remat (function
*, sbitmap
);
408 bitmap
alloc_bitmap (void);
409 bitmap
get_bitmap (bitmap
*);
410 void init_temp_bitmap (bitmap
*);
411 void copy_temp_bitmap (bitmap
*, bitmap
*);
413 void dump_insn_id (rtx_insn
*);
414 void dump_candidate_bitmap (bitmap
);
415 void dump_all_candidates (void);
416 void dump_edge_list (basic_block
, bool);
417 void dump_block_info (basic_block
);
418 void dump_all_blocks (void);
420 bool interesting_regno_p (unsigned int);
421 remat_candidate
*add_candidate (rtx_insn
*, unsigned int, bool);
422 bool maybe_add_candidate (rtx_insn
*, unsigned int);
423 bool collect_candidates (void);
424 void init_block_info (void);
425 void sort_candidates (void);
426 void finalize_candidate_indices (void);
427 void record_equiv_candidates (unsigned int, unsigned int);
428 static bool rd_confluence_n (edge
);
429 static bool rd_transfer (int);
430 void compute_rd (void);
431 unsigned int canon_candidate (unsigned int);
432 void canon_bitmap (bitmap
*);
433 unsigned int resolve_reaching_def (bitmap
);
434 bool check_candidate_uses (unsigned int);
435 void compute_clobbers (unsigned int);
436 void assign_value_number (unsigned int);
437 void decide_candidate_validity (void);
438 bool stable_use_p (unsigned int);
439 void emit_copy_before (unsigned int, rtx
, rtx
);
440 void stabilize_pattern (unsigned int);
441 void replace_dest_with_copy (unsigned int);
442 void stabilize_candidate_uses (unsigned int, bitmap
, bitmap
, bitmap
,
444 void emit_remat_insns (bitmap
, bitmap
, bitmap
, rtx_insn
*);
445 bool set_available_out (remat_block_info
*);
446 void process_block (basic_block
);
447 void local_phase (void);
448 static bool avail_confluence_n (edge
);
449 static bool avail_transfer (int);
450 void compute_availability (void);
451 void unshare_available_sets (remat_block_info
*);
452 bool can_move_across_edge_p (edge
);
453 bool local_remat_cheaper_p (unsigned int);
454 bool need_to_move_candidate_p (unsigned int, unsigned int);
455 void compute_minimum_move_set (unsigned int, bitmap
);
456 void move_to_predecessors (unsigned int, bitmap
, bitmap
);
457 void choose_rematerialization_points (void);
458 void emit_remat_insns_for_block (basic_block
);
459 void global_phase (void);
461 /* The function that we're optimizing. */
464 /* The modes that we want to rematerialize. */
465 sbitmap m_selected_modes
;
467 /* All rematerialization candidates, identified by their index into the
469 auto_vec
<remat_candidate
> m_candidates
;
471 /* The set of candidate registers. */
472 bitmap_head m_candidate_regnos
;
474 /* Temporary sets. */
475 bitmap_head m_tmp_bitmap
;
479 /* Information about each basic block. */
480 auto_vec
<remat_block_info
> m_block_info
;
482 /* A mapping from register numbers to the set of associated candidates.
483 Only valid for registers in M_CANDIDATE_REGNOS. */
484 auto_vec
<bitmap
> m_regno_to_candidates
;
486 /* An obstack used for allocating bitmaps, so that we can free them all
488 bitmap_obstack m_obstack
;
490 /* A hash table of candidates used for value numbering. If a candidate
491 in the table is in an equivalence class, the candidate is marked as
492 the earliest member of the class. */
493 hash_table
<remat_candidate_hasher
> m_value_table
;
495 /* Used temporarily by callback functions. */
496 static early_remat
*er
;
501 early_remat
*early_remat::er
;
503 /* rtx_equal_p_cb callback that treats any two SCRATCHes as equal.
504 This allows us to compare two copies of a pattern, even though their
505 SCRATCHes are always distinct. */
508 scratch_equal (const_rtx
*x
, const_rtx
*y
, rtx
*nx
, rtx
*ny
)
510 if (GET_CODE (*x
) == SCRATCH
&& GET_CODE (*y
) == SCRATCH
)
519 /* Hash callback functions for remat_candidate. */
522 remat_candidate_hasher::hash (const remat_candidate
*cand
)
528 remat_candidate_hasher::equal (const remat_candidate
*cand1
,
529 const remat_candidate
*cand2
)
531 return (cand1
->regno
== cand2
->regno
532 && cand1
->constant_p
== cand2
->constant_p
533 && (cand1
->constant_p
534 ? rtx_equal_p (cand1
->remat_rtx
, cand2
->remat_rtx
)
535 : rtx_equal_p_cb (cand1
->remat_rtx
, cand2
->remat_rtx
,
537 && (!cand1
->uses
|| bitmap_equal_p (cand1
->uses
, cand2
->uses
)));
540 /* Return true if B is null or empty. */
545 return !b
|| bitmap_empty_p (b
);
548 /* Allocate a new bitmap. It will be automatically freed at the end of
552 early_remat::alloc_bitmap (void)
554 return bitmap_alloc (&m_obstack
);
557 /* Initialize *PTR to an empty bitmap if it is currently null. */
560 early_remat::get_bitmap (bitmap
*ptr
)
563 *ptr
= alloc_bitmap ();
567 /* *PTR is either null or empty. If it is null, initialize it to an
571 early_remat::init_temp_bitmap (bitmap
*ptr
)
574 *ptr
= alloc_bitmap ();
576 gcc_checking_assert (bitmap_empty_p (*ptr
));
579 /* Move *SRC to *DEST and leave *SRC empty. */
582 early_remat::copy_temp_bitmap (bitmap
*dest
, bitmap
*src
)
593 /* Print INSN's identifier to the dump file. */
596 early_remat::dump_insn_id (rtx_insn
*insn
)
598 fprintf (dump_file
, "%d[bb:%d]", INSN_UID (insn
),
599 BLOCK_FOR_INSN (insn
)->index
);
602 /* Print candidate set CANDIDATES to the dump file, with a leading space. */
605 early_remat::dump_candidate_bitmap (bitmap candidates
)
607 if (empty_p (candidates
))
609 fprintf (dump_file
, " none");
613 unsigned int cand_index
;
615 EXECUTE_IF_SET_IN_BITMAP (candidates
, 0, cand_index
, bi
)
616 fprintf (dump_file
, " %d", cand_index
);
619 /* Print information about all candidates to the dump file. */
622 early_remat::dump_all_candidates (void)
624 fprintf (dump_file
, "\n;; Candidates:\n;;\n");
625 fprintf (dump_file
, ";; %5s %5s %8s %s\n", "#", "reg", "mode", "insn");
626 fprintf (dump_file
, ";; %5s %5s %8s %s\n", "=", "===", "====", "====");
627 unsigned int cand_index
;
628 remat_candidate
*cand
;
629 FOR_EACH_VEC_ELT (m_candidates
, cand_index
, cand
)
631 fprintf (dump_file
, ";; %5d %5d %8s ", cand_index
, cand
->regno
,
632 GET_MODE_NAME (GET_MODE (regno_reg_rtx
[cand
->regno
])));
633 dump_insn_id (cand
->insn
);
634 if (!cand
->can_copy_p
)
635 fprintf (dump_file
, " -- can't copy");
636 fprintf (dump_file
, "\n");
639 fprintf (dump_file
, "\n;; Register-to-candidate mapping:\n;;\n");
642 EXECUTE_IF_SET_IN_BITMAP (&m_candidate_regnos
, 0, regno
, bi
)
644 fprintf (dump_file
, ";; %5d:", regno
);
645 dump_candidate_bitmap (m_regno_to_candidates
[regno
]);
646 fprintf (dump_file
, "\n");
650 /* Print the predecessors or successors of BB to the dump file, with a
651 leading space. DO_SUCC is true to print successors and false to print
655 early_remat::dump_edge_list (basic_block bb
, bool do_succ
)
659 FOR_EACH_EDGE (e
, ei
, do_succ
? bb
->succs
: bb
->preds
)
660 dump_edge_info (dump_file
, e
, TDF_NONE
, do_succ
);
663 /* Print information about basic block BB to the dump file. */
666 early_remat::dump_block_info (basic_block bb
)
668 remat_block_info
*info
= &m_block_info
[bb
->index
];
669 fprintf (dump_file
, ";;\n;; Block %d:", bb
->index
);
672 fprintf (dump_file
, "\n;;%*s:", width
, "predecessors");
673 dump_edge_list (bb
, false);
675 fprintf (dump_file
, "\n;;%*s:", width
, "successors");
676 dump_edge_list (bb
, true);
678 fprintf (dump_file
, "\n;;%*s: %d", width
, "frequency",
679 bb
->count
.to_frequency (m_fn
));
682 fprintf (dump_file
, "\n;;%*s: %d", width
, "last call",
683 INSN_UID (info
->last_call
));
685 if (!empty_p (info
->rd_in
))
687 fprintf (dump_file
, "\n;;%*s:", width
, "RD in");
688 dump_candidate_bitmap (info
->rd_in
);
690 if (!empty_p (info
->rd_kill
))
692 fprintf (dump_file
, "\n;;%*s:", width
, "RD kill");
693 dump_candidate_bitmap (info
->rd_kill
);
695 if (!empty_p (info
->rd_gen
))
697 fprintf (dump_file
, "\n;;%*s:", width
, "RD gen");
698 dump_candidate_bitmap (info
->rd_gen
);
700 if (!empty_p (info
->rd_after_call
))
702 fprintf (dump_file
, "\n;;%*s:", width
, "RD after call");
703 dump_candidate_bitmap (info
->rd_after_call
);
705 if (!empty_p (info
->rd_out
))
707 fprintf (dump_file
, "\n;;%*s:", width
, "RD out");
708 if (info
->rd_in
== info
->rd_out
)
709 fprintf (dump_file
, " RD in");
711 dump_candidate_bitmap (info
->rd_out
);
713 if (!empty_p (info
->available_in
))
715 fprintf (dump_file
, "\n;;%*s:", width
, "available in");
716 dump_candidate_bitmap (info
->available_in
);
718 if (!empty_p (info
->available_locally
))
720 fprintf (dump_file
, "\n;;%*s:", width
, "available locally");
721 dump_candidate_bitmap (info
->available_locally
);
723 if (!empty_p (info
->available_out
))
725 fprintf (dump_file
, "\n;;%*s:", width
, "available out");
726 if (info
->available_in
== info
->available_out
)
727 fprintf (dump_file
, " available in");
728 else if (info
->available_locally
== info
->available_out
)
729 fprintf (dump_file
, " available locally");
731 dump_candidate_bitmap (info
->available_out
);
733 if (!empty_p (info
->required_in
))
735 fprintf (dump_file
, "\n;;%*s:", width
, "required in");
736 dump_candidate_bitmap (info
->required_in
);
738 if (!empty_p (info
->required_after_call
))
740 fprintf (dump_file
, "\n;;%*s:", width
, "required after call");
741 dump_candidate_bitmap (info
->required_after_call
);
743 fprintf (dump_file
, "\n");
746 /* Print information about all basic blocks to the dump file. */
749 early_remat::dump_all_blocks (void)
752 FOR_EACH_BB_FN (bb
, m_fn
)
753 dump_block_info (bb
);
756 /* Return true if REGNO is worth rematerializing. */
759 early_remat::interesting_regno_p (unsigned int regno
)
761 /* Ignore unused registers. */
762 rtx reg
= regno_reg_rtx
[regno
];
763 if (!reg
|| DF_REG_DEF_COUNT (regno
) == 0)
766 /* Make sure the register has a mode that we want to rematerialize. */
767 if (!bitmap_bit_p (m_selected_modes
, GET_MODE (reg
)))
770 /* Ignore values that might sometimes be used uninitialized. We could
771 instead add dummy candidates for the entry block definition, and so
772 handle uses that are definitely not uninitialized, but the combination
773 of the two should be rare in practice. */
774 if (bitmap_bit_p (DF_LR_OUT (ENTRY_BLOCK_PTR_FOR_FN (m_fn
)), regno
))
780 /* Record the set of register REGNO in instruction INSN as a
781 rematerialization candidate. CAN_COPY_P is true unless we already
782 know that rematerialization is impossible (in which case the candidate
783 only exists for the reaching definition calculation).
785 The candidate's index is not fixed at this stage. */
788 early_remat::add_candidate (rtx_insn
*insn
, unsigned int regno
,
791 remat_candidate cand
;
792 memset (&cand
, 0, sizeof (cand
));
795 cand
.remat_rtx
= PATTERN (insn
);
796 cand
.can_copy_p
= can_copy_p
;
797 m_candidates
.safe_push (cand
);
799 bitmap_set_bit (&m_candidate_regnos
, regno
);
801 return &m_candidates
.last ();
804 /* Return true if we can rematerialize the set of register REGNO in
805 instruction INSN, and add it as a candidate if so. When returning
806 false, print the reason to the dump file. */
809 early_remat::maybe_add_candidate (rtx_insn
*insn
, unsigned int regno
)
811 #define FAILURE_FORMAT ";; Can't rematerialize set of reg %d in %d[bb:%d]: "
812 #define FAILURE_ARGS regno, INSN_UID (insn), BLOCK_FOR_INSN (insn)->index
814 /* The definition must come from an ordinary instruction. */
815 basic_block bb
= BLOCK_FOR_INSN (insn
);
816 if (!NONJUMP_INSN_P (insn
)
817 || (insn
== BB_END (bb
)
818 && has_abnormal_or_eh_outgoing_edge_p (bb
)))
821 fprintf (dump_file
, FAILURE_FORMAT
"insn alters control flow\n",
826 /* Prefer to rematerialize constants directly -- it's much easier. */
827 machine_mode mode
= GET_MODE (regno_reg_rtx
[regno
]);
828 if (rtx note
= find_reg_equal_equiv_note (insn
))
830 rtx val
= XEXP (note
, 0);
832 && targetm
.legitimate_constant_p (mode
, val
))
834 remat_candidate
*cand
= add_candidate (insn
, regno
, true);
835 cand
->constant_p
= true;
836 cand
->remat_rtx
= val
;
841 /* See whether the target has reasons to prevent a copy. */
842 if (targetm
.cannot_copy_insn_p
&& targetm
.cannot_copy_insn_p (insn
))
845 fprintf (dump_file
, FAILURE_FORMAT
"target forbids copying\n",
850 /* We can't copy trapping instructions. */
851 rtx pat
= PATTERN (insn
);
852 if (may_trap_p (pat
))
855 fprintf (dump_file
, FAILURE_FORMAT
"insn might trap\n", FAILURE_ARGS
);
859 /* We can't copy instructions that read memory, unless we know that
860 the contents never change. */
861 subrtx_iterator::array_type array
;
862 FOR_EACH_SUBRTX (iter
, array
, pat
, ALL
)
863 if (MEM_P (*iter
) && !MEM_READONLY_P (*iter
))
866 fprintf (dump_file
, FAILURE_FORMAT
"insn references non-constant"
867 " memory\n", FAILURE_ARGS
);
871 /* Check each defined register. */
873 FOR_EACH_INSN_DEF (ref
, insn
)
875 unsigned int def_regno
= DF_REF_REGNO (ref
);
876 if (def_regno
== regno
)
878 /* Make sure the definition is write-only. (Partial definitions,
879 such as setting the low part and clobbering the high part,
880 are otherwise OK.) */
881 if (DF_REF_FLAGS_IS_SET (ref
, DF_REF_READ_WRITE
))
884 fprintf (dump_file
, FAILURE_FORMAT
"destination is"
885 " read-modify-write\n", FAILURE_ARGS
);
891 /* The instruction can set additional registers, provided that
892 they're call-clobbered hard registers. This is useful for
893 instructions that alter the condition codes. */
894 if (!HARD_REGISTER_NUM_P (def_regno
))
897 fprintf (dump_file
, FAILURE_FORMAT
"insn also sets"
898 " pseudo reg %d\n", FAILURE_ARGS
, def_regno
);
901 if (global_regs
[def_regno
])
904 fprintf (dump_file
, FAILURE_FORMAT
"insn also sets"
905 " global reg %d\n", FAILURE_ARGS
, def_regno
);
908 if (!TEST_HARD_REG_BIT (regs_invalidated_by_call
, def_regno
))
911 fprintf (dump_file
, FAILURE_FORMAT
"insn also sets"
912 " call-preserved reg %d\n", FAILURE_ARGS
, def_regno
);
918 /* If the instruction uses fixed hard registers, check that those
919 registers have the same value throughout the function. If the
920 instruction uses non-fixed hard registers, check that we can
921 replace them with pseudos. */
922 FOR_EACH_INSN_USE (ref
, insn
)
924 unsigned int use_regno
= DF_REF_REGNO (ref
);
925 if (HARD_REGISTER_NUM_P (use_regno
) && fixed_regs
[use_regno
])
927 if (rtx_unstable_p (DF_REF_REAL_REG (ref
)))
930 fprintf (dump_file
, FAILURE_FORMAT
"insn uses fixed hard reg"
931 " %d\n", FAILURE_ARGS
, use_regno
);
935 else if (HARD_REGISTER_NUM_P (use_regno
))
937 /* Allocate a dummy pseudo register and temporarily install it.
938 Make the register number depend on the mode, which should
939 provide enough sharing for match_dup while also weeding
940 out cases in which operands with different modes are
942 rtx
*loc
= DF_REF_REAL_LOC (ref
);
943 unsigned int size
= RTX_CODE_SIZE (REG
);
944 rtx new_reg
= (rtx
) alloca (size
);
945 memset (new_reg
, 0, size
);
946 PUT_CODE (new_reg
, REG
);
947 set_mode_and_regno (new_reg
, GET_MODE (*loc
),
948 LAST_VIRTUAL_REGISTER
+ 1 + GET_MODE (*loc
));
949 validate_change (insn
, loc
, new_reg
, 1);
952 bool ok_p
= verify_changes (0);
957 fprintf (dump_file
, FAILURE_FORMAT
"insn does not allow hard"
958 " register inputs to be replaced\n", FAILURE_ARGS
);
963 #undef FAILURE_FORMAT
965 add_candidate (insn
, regno
, true);
969 /* Calculate the set of rematerialization candidates. Return true if
970 we find at least one. */
973 early_remat::collect_candidates (void)
975 unsigned int nregs
= DF_REG_SIZE (df
);
976 for (unsigned int regno
= FIRST_PSEUDO_REGISTER
; regno
< nregs
; ++regno
)
977 if (interesting_regno_p (regno
))
979 /* Create candidates for all suitable definitions. */
980 bitmap_clear (&m_tmp_bitmap
);
981 unsigned int bad
= 0;
983 for (df_ref ref
= DF_REG_DEF_CHAIN (regno
); ref
;
984 ref
= DF_REF_NEXT_REG (ref
))
986 rtx_insn
*insn
= DF_REF_INSN (ref
);
987 if (maybe_add_candidate (insn
, regno
))
988 bitmap_set_bit (&m_tmp_bitmap
, id
);
994 /* If we found at least one suitable definition, add dummy
995 candidates for the rest, so that we can see which definitions
997 if (!bitmap_empty_p (&m_tmp_bitmap
) && bad
)
1000 for (df_ref ref
= DF_REG_DEF_CHAIN (regno
); ref
;
1001 ref
= DF_REF_NEXT_REG (ref
))
1003 if (!bitmap_bit_p (&m_tmp_bitmap
, id
))
1004 add_candidate (DF_REF_INSN (ref
), regno
, false);
1011 return !m_candidates
.is_empty ();
1014 /* Initialize the m_block_info array. */
1017 early_remat::init_block_info (void)
1019 unsigned int n_blocks
= last_basic_block_for_fn (m_fn
);
1020 m_block_info
.safe_grow_cleared (n_blocks
);
1023 /* Maps basic block indices to their position in the post order. */
1024 static unsigned int *postorder_index
;
1026 /* Order remat_candidates X_IN and Y_IN according to the cfg postorder. */
1029 compare_candidates (const void *x_in
, const void *y_in
)
1031 const remat_candidate
*x
= (const remat_candidate
*) x_in
;
1032 const remat_candidate
*y
= (const remat_candidate
*) y_in
;
1033 basic_block x_bb
= BLOCK_FOR_INSN (x
->insn
);
1034 basic_block y_bb
= BLOCK_FOR_INSN (y
->insn
);
1036 /* Make X and Y follow block postorder. */
1037 return postorder_index
[x_bb
->index
] - postorder_index
[y_bb
->index
];
1039 /* Make X and Y follow a backward traversal of the containing block. */
1040 return DF_INSN_LUID (y
->insn
) - DF_INSN_LUID (x
->insn
);
1043 /* Sort the collected rematerialization candidates so that they follow
1047 early_remat::sort_candidates (void)
1049 /* Make sure the DF LUIDs are up-to-date for all the blocks we
1051 bitmap_clear (&m_tmp_bitmap
);
1052 unsigned int cand_index
;
1053 remat_candidate
*cand
;
1054 FOR_EACH_VEC_ELT (m_candidates
, cand_index
, cand
)
1056 basic_block bb
= BLOCK_FOR_INSN (cand
->insn
);
1057 if (bitmap_set_bit (&m_tmp_bitmap
, bb
->index
))
1058 df_recompute_luids (bb
);
1061 /* Create a mapping from block numbers to their position in the
1063 unsigned int n_blocks
= last_basic_block_for_fn (m_fn
);
1064 int *postorder
= df_get_postorder (DF_BACKWARD
);
1065 unsigned int postorder_len
= df_get_n_blocks (DF_BACKWARD
);
1066 postorder_index
= new unsigned int[n_blocks
];
1067 for (unsigned int i
= 0; i
< postorder_len
; ++i
)
1068 postorder_index
[postorder
[i
]] = i
;
1070 m_candidates
.qsort (compare_candidates
);
1072 delete postorder_index
;
1075 /* Commit to the current candidate indices and initialize cross-references. */
1078 early_remat::finalize_candidate_indices (void)
1080 /* Create a bitmap for each candidate register. */
1081 m_regno_to_candidates
.safe_grow (max_reg_num ());
1084 EXECUTE_IF_SET_IN_BITMAP (&m_candidate_regnos
, 0, regno
, bi
)
1085 m_regno_to_candidates
[regno
] = alloc_bitmap ();
1087 /* Go through each candidate and record its index. */
1088 unsigned int cand_index
;
1089 remat_candidate
*cand
;
1090 FOR_EACH_VEC_ELT (m_candidates
, cand_index
, cand
)
1092 basic_block bb
= BLOCK_FOR_INSN (cand
->insn
);
1093 remat_block_info
*info
= &m_block_info
[bb
->index
];
1094 info
->num_candidates
+= 1;
1095 info
->first_candidate
= cand_index
;
1096 bitmap_set_bit (m_regno_to_candidates
[cand
->regno
], cand_index
);
1100 /* Record that candidates CAND1_INDEX and CAND2_INDEX are equivalent.
1101 CAND1_INDEX might already have an equivalence class, but CAND2_INDEX
1105 early_remat::record_equiv_candidates (unsigned int cand1_index
,
1106 unsigned int cand2_index
)
1109 fprintf (dump_file
, ";; Candidate %d is equivalent to candidate %d\n",
1110 cand2_index
, cand1_index
);
1112 remat_candidate
*cand1
= &m_candidates
[cand1_index
];
1113 remat_candidate
*cand2
= &m_candidates
[cand2_index
];
1114 gcc_checking_assert (!cand2
->equiv_class
);
1116 remat_equiv_class
*ec
= cand1
->equiv_class
;
1119 ec
= XOBNEW (&m_obstack
.obstack
, remat_equiv_class
);
1120 ec
->members
= alloc_bitmap ();
1121 bitmap_set_bit (ec
->members
, cand1_index
);
1122 ec
->earliest
= cand1_index
;
1123 ec
->representative
= cand1_index
;
1124 cand1
->equiv_class
= ec
;
1126 cand2
->equiv_class
= ec
;
1127 bitmap_set_bit (ec
->members
, cand2_index
);
1128 if (cand2_index
> ec
->representative
)
1129 ec
->representative
= cand2_index
;
1132 /* Propagate information from the rd_out set of E->src to the rd_in set
1133 of E->dest, when computing global reaching definitions. Return true
1134 if something changed. */
1137 early_remat::rd_confluence_n (edge e
)
1139 remat_block_info
*src
= &er
->m_block_info
[e
->src
->index
];
1140 remat_block_info
*dest
= &er
->m_block_info
[e
->dest
->index
];
1142 /* available_in temporarily contains the set of candidates whose
1143 registers are live on entry. */
1144 if (empty_p (src
->rd_out
) || empty_p (dest
->available_in
))
1147 return bitmap_ior_and_into (er
->get_bitmap (&dest
->rd_in
),
1148 src
->rd_out
, dest
->available_in
);
1151 /* Propagate information from the rd_in set of block BB_INDEX to rd_out.
1152 Return true if something changed. */
1155 early_remat::rd_transfer (int bb_index
)
1157 remat_block_info
*info
= &er
->m_block_info
[bb_index
];
1159 if (empty_p (info
->rd_in
))
1162 if (empty_p (info
->rd_kill
))
1164 gcc_checking_assert (empty_p (info
->rd_gen
));
1166 info
->rd_out
= info
->rd_in
;
1168 gcc_checking_assert (info
->rd_out
== info
->rd_in
);
1169 /* Assume that we only get called if something changed. */
1173 if (empty_p (info
->rd_gen
))
1174 return bitmap_and_compl (er
->get_bitmap (&info
->rd_out
),
1175 info
->rd_in
, info
->rd_kill
);
1177 return bitmap_ior_and_compl (er
->get_bitmap (&info
->rd_out
), info
->rd_gen
,
1178 info
->rd_in
, info
->rd_kill
);
1181 /* Calculate the rd_* sets for each block. */
1184 early_remat::compute_rd (void)
1186 /* First calculate the rd_kill and rd_gen sets, using the fact
1187 that m_candidates is sorted in order of decreasing LUID. */
1188 unsigned int cand_index
;
1189 remat_candidate
*cand
;
1190 FOR_EACH_VEC_ELT_REVERSE (m_candidates
, cand_index
, cand
)
1192 rtx_insn
*insn
= cand
->insn
;
1193 basic_block bb
= BLOCK_FOR_INSN (insn
);
1194 remat_block_info
*info
= &m_block_info
[bb
->index
];
1195 bitmap kill
= m_regno_to_candidates
[cand
->regno
];
1196 bitmap_ior_into (get_bitmap (&info
->rd_kill
), kill
);
1197 if (bitmap_bit_p (DF_LR_OUT (bb
), cand
->regno
))
1199 bitmap_and_compl_into (get_bitmap (&info
->rd_gen
), kill
);
1200 bitmap_set_bit (info
->rd_gen
, cand_index
);
1204 /* Set up the initial values of the other sets. */
1206 FOR_EACH_BB_FN (bb
, m_fn
)
1208 remat_block_info
*info
= &m_block_info
[bb
->index
];
1211 EXECUTE_IF_AND_IN_BITMAP (DF_LR_IN (bb
), &m_candidate_regnos
,
1214 /* Use available_in to record the set of candidates whose
1215 registers are live on entry (i.e. a maximum bound on rd_in). */
1216 bitmap_ior_into (get_bitmap (&info
->available_in
),
1217 m_regno_to_candidates
[regno
]);
1219 /* Add registers that die in a block to the block's kill set,
1220 so that we don't needlessly propagate them through the rest
1222 if (!bitmap_bit_p (DF_LR_OUT (bb
), regno
))
1223 bitmap_ior_into (get_bitmap (&info
->rd_kill
),
1224 m_regno_to_candidates
[regno
]);
1227 /* Initialize each block's rd_out to the minimal set (the set of
1228 local definitions). */
1229 if (!empty_p (info
->rd_gen
))
1230 bitmap_copy (get_bitmap (&info
->rd_out
), info
->rd_gen
);
1233 /* Iterate until we reach a fixed point. */
1235 bitmap_clear (&m_tmp_bitmap
);
1236 bitmap_set_range (&m_tmp_bitmap
, 0, last_basic_block_for_fn (m_fn
));
1237 df_simple_dataflow (DF_FORWARD
, NULL
, NULL
, rd_confluence_n
, rd_transfer
,
1238 &m_tmp_bitmap
, df_get_postorder (DF_FORWARD
),
1239 df_get_n_blocks (DF_FORWARD
));
1242 /* Work out which definitions reach which candidates, again taking
1243 advantage of the candidate order. */
1244 bitmap_head reaching
;
1245 bitmap_initialize (&reaching
, &m_obstack
);
1246 basic_block old_bb
= NULL
;
1247 FOR_EACH_VEC_ELT_REVERSE (m_candidates
, cand_index
, cand
)
1249 bb
= BLOCK_FOR_INSN (cand
->insn
);
1252 /* Get the definitions that reach the start of the new block. */
1253 remat_block_info
*info
= &m_block_info
[bb
->index
];
1255 bitmap_copy (&reaching
, info
->rd_in
);
1257 bitmap_clear (&reaching
);
1262 /* Process the definitions of the previous instruction. */
1263 bitmap kill
= m_regno_to_candidates
[cand
[1].regno
];
1264 bitmap_and_compl_into (&reaching
, kill
);
1265 bitmap_set_bit (&reaching
, cand_index
+ 1);
1268 if (cand
->can_copy_p
&& !cand
->constant_p
)
1271 FOR_EACH_INSN_USE (ref
, cand
->insn
)
1273 unsigned int regno
= DF_REF_REGNO (ref
);
1274 if (bitmap_bit_p (&m_candidate_regnos
, regno
))
1276 bitmap defs
= m_regno_to_candidates
[regno
];
1277 bitmap_and (&m_tmp_bitmap
, defs
, &reaching
);
1278 bitmap_ior_into (get_bitmap (&cand
->uses
), &m_tmp_bitmap
);
1283 bitmap_clear (&reaching
);
1286 /* If CAND_INDEX is in an equivalence class, return the representative
1287 of the class, otherwise return CAND_INDEX. */
1290 early_remat::canon_candidate (unsigned int cand_index
)
1292 if (remat_equiv_class
*ec
= m_candidates
[cand_index
].equiv_class
)
1293 return ec
->representative
;
1297 /* Make candidate set *PTR refer to candidates using the representative
1298 of each equivalence class. */
1301 early_remat::canon_bitmap (bitmap
*ptr
)
1303 bitmap old_set
= *ptr
;
1304 if (empty_p (old_set
))
1307 bitmap new_set
= NULL
;
1308 unsigned int old_index
;
1310 EXECUTE_IF_SET_IN_BITMAP (old_set
, 0, old_index
, bi
)
1312 unsigned int new_index
= canon_candidate (old_index
);
1313 if (old_index
!= new_index
)
1317 new_set
= alloc_bitmap ();
1318 bitmap_copy (new_set
, old_set
);
1320 bitmap_clear_bit (new_set
, old_index
);
1321 bitmap_set_bit (new_set
, new_index
);
1331 /* If the candidates in REACHING all have the same value, return the
1332 earliest instance of that value (i.e. the first one to be added
1333 to m_value_table), otherwise return MULTIPLE_CANDIDATES. */
1336 early_remat::resolve_reaching_def (bitmap reaching
)
1338 unsigned int cand_index
= bitmap_first_set_bit (reaching
);
1339 if (remat_equiv_class
*ec
= m_candidates
[cand_index
].equiv_class
)
1341 if (!bitmap_intersect_compl_p (reaching
, ec
->members
))
1342 return ec
->earliest
;
1344 else if (bitmap_single_bit_set_p (reaching
))
1347 return MULTIPLE_CANDIDATES
;
1350 /* Check whether all candidate registers used by candidate CAND_INDEX have
1351 unique definitions. Return true if so, replacing the candidate's uses
1352 set with the appropriate form for value numbering. */
1355 early_remat::check_candidate_uses (unsigned int cand_index
)
1357 remat_candidate
*cand
= &m_candidates
[cand_index
];
1359 /* Process the uses for each register in turn. */
1361 bitmap_initialize (&uses
, &m_obstack
);
1362 bitmap_copy (&uses
, cand
->uses
);
1363 bitmap uses_ec
= alloc_bitmap ();
1364 while (!bitmap_empty_p (&uses
))
1366 /* Get the register for the lowest-indexed candidate remaining,
1367 and the reaching definitions of that register. */
1368 unsigned int first
= bitmap_first_set_bit (&uses
);
1369 unsigned int regno
= m_candidates
[first
].regno
;
1370 bitmap_and (&m_tmp_bitmap
, &uses
, m_regno_to_candidates
[regno
]);
1372 /* See whether all reaching definitions have the same value and if
1373 so get the index of the first candidate we saw with that value. */
1374 unsigned int def
= resolve_reaching_def (&m_tmp_bitmap
);
1375 if (def
== MULTIPLE_CANDIDATES
)
1378 fprintf (dump_file
, ";; Removing candidate %d because there is"
1379 " more than one reaching definition of reg %d\n",
1381 cand
->can_copy_p
= false;
1384 bitmap_set_bit (uses_ec
, def
);
1385 bitmap_and_compl_into (&uses
, &m_tmp_bitmap
);
1387 BITMAP_FREE (cand
->uses
);
1388 cand
->uses
= uses_ec
;
1389 return cand
->can_copy_p
;
1392 /* Calculate the set of hard registers that would be clobbered by
1393 rematerializing candidate CAND_INDEX. At this point the candidate's
1394 set of uses is final. */
1397 early_remat::compute_clobbers (unsigned int cand_index
)
1399 remat_candidate
*cand
= &m_candidates
[cand_index
];
1402 unsigned int use_index
;
1404 EXECUTE_IF_SET_IN_BITMAP (cand
->uses
, 0, use_index
, bi
)
1405 if (bitmap clobbers
= m_candidates
[use_index
].clobbers
)
1406 bitmap_ior_into (get_bitmap (&cand
->clobbers
), clobbers
);
1410 FOR_EACH_INSN_DEF (ref
, cand
->insn
)
1412 unsigned int def_regno
= DF_REF_REGNO (ref
);
1413 if (def_regno
!= cand
->regno
)
1414 bitmap_set_bit (get_bitmap (&cand
->clobbers
), def_regno
);
1418 /* Mark candidate CAND_INDEX as validated and add it to the value table. */
1421 early_remat::assign_value_number (unsigned int cand_index
)
1423 remat_candidate
*cand
= &m_candidates
[cand_index
];
1424 gcc_checking_assert (cand
->can_copy_p
&& !cand
->validated_p
);
1426 compute_clobbers (cand_index
);
1427 cand
->validated_p
= true;
1430 h
.add_int (cand
->regno
);
1431 inchash::add_rtx (cand
->remat_rtx
, h
);
1432 cand
->hash
= h
.end ();
1434 remat_candidate
**slot
1435 = m_value_table
.find_slot_with_hash (cand
, cand
->hash
, INSERT
);
1440 fprintf (dump_file
, ";; Candidate %d is not equivalent to"
1441 " others seen so far\n", cand_index
);
1444 record_equiv_candidates (*slot
- m_candidates
.address (), cand_index
);
1447 /* Make a final decision about which candidates are valid and assign
1448 value numbers to those that are. */
1451 early_remat::decide_candidate_validity (void)
1453 auto_vec
<unsigned int, 16> stack
;
1454 unsigned int cand1_index
;
1455 remat_candidate
*cand1
;
1456 FOR_EACH_VEC_ELT_REVERSE (m_candidates
, cand1_index
, cand1
)
1458 if (!cand1
->can_copy_p
|| cand1
->validated_p
)
1461 if (empty_p (cand1
->uses
))
1463 assign_value_number (cand1_index
);
1467 stack
.safe_push (cand1_index
);
1468 while (!stack
.is_empty ())
1470 unsigned int cand2_index
= stack
.last ();
1471 unsigned int watermark
= stack
.length ();
1472 remat_candidate
*cand2
= &m_candidates
[cand2_index
];
1473 if (!cand2
->can_copy_p
|| cand2
->validated_p
)
1478 cand2
->visited_p
= true;
1479 unsigned int cand3_index
;
1481 EXECUTE_IF_SET_IN_BITMAP (cand2
->uses
, 0, cand3_index
, bi
)
1483 remat_candidate
*cand3
= &m_candidates
[cand3_index
];
1484 if (!cand3
->can_copy_p
)
1487 fprintf (dump_file
, ";; Removing candidate %d because"
1488 " it uses removed candidate %d\n", cand2_index
,
1490 cand2
->can_copy_p
= false;
1493 if (!cand3
->validated_p
)
1495 if (empty_p (cand3
->uses
))
1496 assign_value_number (cand3_index
);
1497 else if (cand3
->visited_p
)
1500 fprintf (dump_file
, ";; Removing candidate %d"
1501 " because its definition is cyclic\n",
1503 cand2
->can_copy_p
= false;
1507 stack
.safe_push (cand3_index
);
1510 if (!cand2
->can_copy_p
)
1512 cand2
->visited_p
= false;
1513 stack
.truncate (watermark
- 1);
1515 else if (watermark
== stack
.length ())
1517 cand2
->visited_p
= false;
1518 if (check_candidate_uses (cand2_index
))
1519 assign_value_number (cand2_index
);
1525 /* Ensure that the candidates always use the same candidate index
1526 to refer to an equivalence class. */
1527 FOR_EACH_VEC_ELT_REVERSE (m_candidates
, cand1_index
, cand1
)
1528 if (cand1
->can_copy_p
&& !empty_p (cand1
->uses
))
1530 canon_bitmap (&cand1
->uses
);
1531 gcc_checking_assert (bitmap_first_set_bit (cand1
->uses
) > cand1_index
);
1535 /* Assuming that every path reaching a point P contains a copy of a
1536 use U of REGNO, return true if another copy of U at P would have
1537 access to the same value of REGNO. */
1540 early_remat::stable_use_p (unsigned int regno
)
1542 /* Conservatively assume not for hard registers. */
1543 if (HARD_REGISTER_NUM_P (regno
))
1546 /* See if REGNO has a single definition and is never used uninitialized.
1547 In this case the definition of REGNO dominates the common dominator
1548 of the uses U, which in turn dominates P. */
1549 if (DF_REG_DEF_COUNT (regno
) == 1
1550 && !bitmap_bit_p (DF_LR_OUT (ENTRY_BLOCK_PTR_FOR_FN (m_fn
)), regno
))
1556 /* Emit a copy from register DEST to register SRC before candidate
1557 CAND_INDEX's instruction. */
1560 early_remat::emit_copy_before (unsigned int cand_index
, rtx dest
, rtx src
)
1562 remat_candidate
*cand
= &m_candidates
[cand_index
];
1565 fprintf (dump_file
, ";; Stabilizing insn ");
1566 dump_insn_id (cand
->insn
);
1567 fprintf (dump_file
, " by copying source reg %d:%s to temporary reg %d\n",
1568 REGNO (src
), GET_MODE_NAME (GET_MODE (src
)), REGNO (dest
));
1570 emit_insn_before (gen_move_insn (dest
, src
), cand
->insn
);
1573 /* Check whether any inputs to candidate CAND_INDEX's instruction could
1574 change at rematerialization points and replace them with new pseudo
1578 early_remat::stabilize_pattern (unsigned int cand_index
)
1580 remat_candidate
*cand
= &m_candidates
[cand_index
];
1581 if (cand
->stabilized_p
)
1584 remat_equiv_class
*ec
= cand
->equiv_class
;
1585 gcc_checking_assert (!ec
|| cand_index
== ec
->representative
);
1587 /* Record the replacements we've made so far, so that we don't
1588 create two separate registers for match_dups. Lookup is O(n),
1589 but the n is very small. */
1590 typedef std::pair
<rtx
, rtx
> reg_pair
;
1591 auto_vec
<reg_pair
, 16> reg_map
;
1593 rtx_insn
*insn
= cand
->insn
;
1595 FOR_EACH_INSN_USE (ref
, insn
)
1597 unsigned int old_regno
= DF_REF_REGNO (ref
);
1598 rtx
*loc
= DF_REF_REAL_LOC (ref
);
1600 if (HARD_REGISTER_NUM_P (old_regno
) && fixed_regs
[old_regno
])
1602 /* We checked when adding the candidate that the value is stable. */
1603 gcc_checking_assert (!rtx_unstable_p (*loc
));
1607 if (bitmap_bit_p (&m_candidate_regnos
, old_regno
))
1608 /* We already know which candidate provides the definition
1609 and will handle it during copying. */
1612 if (stable_use_p (old_regno
))
1613 /* We can continue to use the existing register. */
1616 /* We need to replace the register. See whether we've already
1617 created a suitable copy. */
1619 rtx new_reg
= NULL_RTX
;
1620 machine_mode mode
= GET_MODE (old_reg
);
1623 FOR_EACH_VEC_ELT (reg_map
, pi
, p
)
1624 if (REGNO (p
->first
) == old_regno
1625 && GET_MODE (p
->first
) == mode
)
1627 new_reg
= p
->second
;
1633 /* Create a new register and initialize it just before
1635 new_reg
= gen_reg_rtx (mode
);
1636 reg_map
.safe_push (reg_pair (old_reg
, new_reg
));
1639 unsigned int member_index
;
1641 EXECUTE_IF_SET_IN_BITMAP (ec
->members
, 0, member_index
, bi
)
1642 emit_copy_before (member_index
, new_reg
, old_reg
);
1645 emit_copy_before (cand_index
, new_reg
, old_reg
);
1647 validate_change (insn
, loc
, new_reg
, true);
1649 if (num_changes_pending ())
1651 if (!apply_change_group ())
1652 /* We checked when adding the candidates that the pattern allows
1653 hard registers to be replaced. Nothing else should make the
1659 /* Copy the new pattern to other members of the equivalence
1661 unsigned int member_index
;
1663 EXECUTE_IF_SET_IN_BITMAP (ec
->members
, 0, member_index
, bi
)
1664 if (cand_index
!= member_index
)
1666 rtx_insn
*other_insn
= m_candidates
[member_index
].insn
;
1667 if (!validate_change (other_insn
, &PATTERN (other_insn
),
1668 copy_insn (PATTERN (insn
)), 0))
1669 /* If the original instruction was valid then the copy
1676 cand
->stabilized_p
= true;
1679 /* Change CAND's instruction so that it sets CAND->copy_regno instead
1683 early_remat::replace_dest_with_copy (unsigned int cand_index
)
1685 remat_candidate
*cand
= &m_candidates
[cand_index
];
1687 FOR_EACH_INSN_DEF (def
, cand
->insn
)
1688 if (DF_REF_REGNO (def
) == cand
->regno
)
1689 validate_change (cand
->insn
, DF_REF_REAL_LOC (def
),
1690 regno_reg_rtx
[cand
->copy_regno
], 1);
1693 /* Make sure that the candidates used by candidate CAND_INDEX are available.
1694 There are two ways of doing this for an input candidate I:
1696 (1) Using the existing register number and ensuring that I is available.
1698 (2) Using a new register number (recorded in copy_regno) and adding I
1699 to VIA_COPY. This guarantees that making I available does not
1700 conflict with other uses of the original register.
1702 REQUIRED is the set of candidates that are required but not available
1703 before the copy of CAND_INDEX. AVAILABLE is the set of candidates
1704 that are already available before the copy of CAND_INDEX. REACHING
1705 is the set of candidates that reach the copy of CAND_INDEX. VIA_COPY
1706 is the set of candidates that will use new register numbers recorded
1707 in copy_regno instead of the original ones. */
1710 early_remat::stabilize_candidate_uses (unsigned int cand_index
,
1711 bitmap required
, bitmap available
,
1712 bitmap reaching
, bitmap via_copy
)
1714 remat_candidate
*cand
= &m_candidates
[cand_index
];
1716 FOR_EACH_INSN_USE (use
, cand
->insn
)
1718 unsigned int regno
= DF_REF_REGNO (use
);
1719 if (!bitmap_bit_p (&m_candidate_regnos
, regno
))
1722 /* Work out which candidate provides the definition. */
1723 bitmap defs
= m_regno_to_candidates
[regno
];
1724 bitmap_and (&m_tmp_bitmap
, cand
->uses
, defs
);
1725 gcc_checking_assert (bitmap_single_bit_set_p (&m_tmp_bitmap
));
1726 unsigned int def_index
= bitmap_first_set_bit (&m_tmp_bitmap
);
1728 /* First see if DEF_INDEX is the only reaching definition of REGNO
1729 at this point too and if it is or will become available. We can
1730 continue to use REGNO if so. */
1731 bitmap_and (&m_tmp_bitmap
, reaching
, defs
);
1732 if (bitmap_single_bit_set_p (&m_tmp_bitmap
)
1733 && bitmap_first_set_bit (&m_tmp_bitmap
) == def_index
1734 && ((available
&& bitmap_bit_p (available
, def_index
))
1735 || bitmap_bit_p (required
, def_index
)))
1738 fprintf (dump_file
, ";; Keeping reg %d for use of candidate %d"
1739 " in candidate %d\n", regno
, def_index
, cand_index
);
1743 /* Otherwise fall back to using a copy. There are other cases
1744 in which we *could* continue to use REGNO, but there's not
1745 really much point. Using a separate register ought to make
1746 things easier for the register allocator. */
1747 remat_candidate
*def_cand
= &m_candidates
[def_index
];
1748 rtx
*loc
= DF_REF_REAL_LOC (use
);
1750 if (bitmap_set_bit (via_copy
, def_index
))
1752 new_reg
= gen_reg_rtx (GET_MODE (*loc
));
1753 def_cand
->copy_regno
= REGNO (new_reg
);
1755 fprintf (dump_file
, ";; Creating reg %d for use of candidate %d"
1756 " in candidate %d\n", REGNO (new_reg
), def_index
,
1760 new_reg
= regno_reg_rtx
[def_cand
->copy_regno
];
1761 validate_change (cand
->insn
, loc
, new_reg
, 1);
1765 /* Rematerialize the candidates in REQUIRED after instruction INSN,
1766 given that the candidates in AVAILABLE are already available
1767 and that REACHING is the set of candidates live after INSN.
1768 REQUIRED and AVAILABLE are disjoint on entry.
1770 Clear REQUIRED on exit. */
1773 early_remat::emit_remat_insns (bitmap required
, bitmap available
,
1774 bitmap reaching
, rtx_insn
*insn
)
1776 /* Quick exit if there's nothing to do. */
1777 if (empty_p (required
))
1780 /* Only reaching definitions should be available or required. */
1781 gcc_checking_assert (!bitmap_intersect_compl_p (required
, reaching
));
1783 gcc_checking_assert (!bitmap_intersect_compl_p (available
, reaching
));
1785 bitmap_head via_copy
;
1786 bitmap_initialize (&via_copy
, &m_obstack
);
1787 while (!bitmap_empty_p (required
) || !bitmap_empty_p (&via_copy
))
1789 /* Pick the lowest-indexed candidate left. */
1790 unsigned int required_index
= (bitmap_empty_p (required
)
1791 ? ~0U : bitmap_first_set_bit (required
));
1792 unsigned int via_copy_index
= (bitmap_empty_p (&via_copy
)
1793 ? ~0U : bitmap_first_set_bit (&via_copy
));
1794 unsigned int cand_index
= MIN (required_index
, via_copy_index
);
1795 remat_candidate
*cand
= &m_candidates
[cand_index
];
1797 bool via_copy_p
= (cand_index
== via_copy_index
);
1799 bitmap_clear_bit (&via_copy
, cand_index
);
1802 /* Remove all candidates for the same register from REQUIRED. */
1803 bitmap_and (&m_tmp_bitmap
, reaching
,
1804 m_regno_to_candidates
[cand
->regno
]);
1805 bitmap_and_compl_into (required
, &m_tmp_bitmap
);
1806 gcc_checking_assert (!bitmap_bit_p (required
, cand_index
));
1808 /* Only rematerialize if we have a single reaching definition
1810 if (!bitmap_single_bit_set_p (&m_tmp_bitmap
))
1814 fprintf (dump_file
, ";; Can't rematerialize reg %d after ",
1816 dump_insn_id (insn
);
1817 fprintf (dump_file
, ": more than one reaching definition\n");
1822 /* Skip candidates that can't be rematerialized. */
1823 if (!cand
->can_copy_p
)
1826 /* Check the function precondition. */
1827 gcc_checking_assert (!available
1828 || !bitmap_bit_p (available
, cand_index
));
1831 /* Invalid candidates should have been weeded out by now. */
1832 gcc_assert (cand
->can_copy_p
);
1835 if (cand
->constant_p
)
1837 /* Emit a simple move. */
1838 unsigned int regno
= via_copy_p
? cand
->copy_regno
: cand
->regno
;
1839 new_pattern
= gen_move_insn (regno_reg_rtx
[regno
], cand
->remat_rtx
);
1843 /* If this is the first time we've copied the instruction, make
1844 sure that any inputs will have the same value after INSN. */
1845 stabilize_pattern (cand_index
);
1847 /* Temporarily adjust the original instruction so that it has
1848 the right form for the copy. */
1850 replace_dest_with_copy (cand_index
);
1852 stabilize_candidate_uses (cand_index
, required
, available
,
1853 reaching
, &via_copy
);
1855 /* Get the new instruction pattern. */
1856 new_pattern
= copy_insn (cand
->remat_rtx
);
1858 /* Undo the temporary changes. */
1862 /* Emit the new instruction. */
1863 rtx_insn
*new_insn
= emit_insn_after (new_pattern
, insn
);
1867 fprintf (dump_file
, ";; Rematerializing candidate %d after ",
1869 dump_insn_id (insn
);
1871 fprintf (dump_file
, " with new destination reg %d",
1873 fprintf (dump_file
, ":\n\n");
1874 print_rtl_single (dump_file
, new_insn
);
1875 fprintf (dump_file
, "\n");
1880 /* Recompute INFO's available_out set, given that it's distinct from
1881 available_in and available_locally. */
1884 early_remat::set_available_out (remat_block_info
*info
)
1886 if (empty_p (info
->available_locally
))
1887 return bitmap_and_compl (get_bitmap (&info
->available_out
),
1888 info
->available_in
, info
->rd_kill
);
1890 if (empty_p (info
->rd_kill
))
1891 return bitmap_ior (get_bitmap (&info
->available_out
),
1892 info
->available_locally
, info
->available_in
);
1894 return bitmap_ior_and_compl (get_bitmap (&info
->available_out
),
1895 info
->available_locally
, info
->available_in
,
1899 /* If BB has more than one call, decide which candidates should be
1900 rematerialized after the non-final calls and emit the associated
1901 instructions. Record other information about the block in preparation
1902 for the global phase. */
1905 early_remat::process_block (basic_block bb
)
1907 remat_block_info
*info
= &m_block_info
[bb
->index
];
1908 rtx_insn
*last_call
= NULL
;
1911 /* Ensure that we always use the same candidate index to refer to an
1912 equivalence class. */
1913 if (info
->rd_out
== info
->rd_in
)
1915 canon_bitmap (&info
->rd_in
);
1916 info
->rd_out
= info
->rd_in
;
1920 canon_bitmap (&info
->rd_in
);
1921 canon_bitmap (&info
->rd_out
);
1923 canon_bitmap (&info
->rd_kill
);
1924 canon_bitmap (&info
->rd_gen
);
1926 /* The set of candidates that should be rematerialized on entry to the
1927 block or after the previous call (whichever is more recent). */
1928 init_temp_bitmap (&m_required
);
1930 /* The set of candidates that reach the current instruction (i.e. are
1931 live just before the instruction). */
1932 bitmap_head reaching
;
1933 bitmap_initialize (&reaching
, &m_obstack
);
1935 bitmap_copy (&reaching
, info
->rd_in
);
1937 /* The set of candidates that are live and available without
1938 rematerialization just before the current instruction. This only
1939 accounts for earlier candidates in the block, or those that become
1940 available by being added to M_REQUIRED. */
1941 init_temp_bitmap (&m_available
);
1943 /* Get the range of candidates in the block. */
1944 unsigned int next_candidate
= info
->first_candidate
;
1945 unsigned int num_candidates
= info
->num_candidates
;
1946 remat_candidate
*next_def
= (num_candidates
> 0
1947 ? &m_candidates
[next_candidate
]
1950 FOR_BB_INSNS (bb
, insn
)
1952 if (!NONDEBUG_INSN_P (insn
))
1955 /* First process uses, since this is a forward walk. */
1957 FOR_EACH_INSN_USE (ref
, insn
)
1959 unsigned int regno
= DF_REF_REGNO (ref
);
1960 if (bitmap_bit_p (&m_candidate_regnos
, regno
))
1962 bitmap defs
= m_regno_to_candidates
[regno
];
1963 bitmap_and (&m_tmp_bitmap
, defs
, &reaching
);
1964 gcc_checking_assert (!bitmap_empty_p (&m_tmp_bitmap
));
1965 if (!bitmap_intersect_p (defs
, m_available
))
1967 /* There has been no definition of the register since
1968 the last call or the start of the block (whichever
1969 is most recent). Mark the reaching definitions
1970 as required at that point and thus available here. */
1971 bitmap_ior_into (m_required
, &m_tmp_bitmap
);
1972 bitmap_ior_into (m_available
, &m_tmp_bitmap
);
1981 /* The first call in the block. Record which candidates are
1982 required at the start of the block. */
1983 copy_temp_bitmap (&info
->required_in
, &m_required
);
1984 init_temp_bitmap (&m_required
);
1987 /* The fully-local case: candidates that need to be
1988 rematerialized after a previous call in the block. */
1989 emit_remat_insns (m_required
, NULL
, info
->rd_after_call
,
1992 bitmap_clear (m_available
);
1993 gcc_checking_assert (empty_p (m_required
));
1996 /* Now process definitions. */
1997 if (next_def
&& insn
== next_def
->insn
)
1999 unsigned int gen
= canon_candidate (next_candidate
);
2001 /* Other candidates with the same regno are not available
2003 bitmap kill
= m_regno_to_candidates
[next_def
->regno
];
2004 bitmap_and_compl_into (m_available
, kill
);
2005 bitmap_and_compl_into (&reaching
, kill
);
2007 /* Record that this candidate is available without
2008 rematerialization. */
2009 bitmap_set_bit (m_available
, gen
);
2010 bitmap_set_bit (&reaching
, gen
);
2012 /* Find the next candidate in the block. */
2013 num_candidates
-= 1;
2014 next_candidate
-= 1;
2015 if (num_candidates
> 0)
2021 if (insn
== last_call
)
2022 bitmap_copy (get_bitmap (&info
->rd_after_call
), &reaching
);
2024 bitmap_clear (&reaching
);
2025 gcc_checking_assert (num_candidates
== 0);
2027 /* Remove values from the available set if they aren't live (and so
2028 aren't interesting to successor blocks). */
2030 bitmap_and_into (m_available
, info
->rd_out
);
2032 /* Record the accumulated information. */
2033 info
->last_call
= last_call
;
2034 info
->abnormal_call_p
= (last_call
2035 && last_call
== BB_END (bb
)
2036 && has_abnormal_or_eh_outgoing_edge_p (bb
));
2037 copy_temp_bitmap (&info
->available_locally
, &m_available
);
2039 copy_temp_bitmap (&info
->required_after_call
, &m_required
);
2041 copy_temp_bitmap (&info
->required_in
, &m_required
);
2043 /* Assume at first that all live-in values are available without
2044 rematerialization (i.e. start with the most optimistic assumption). */
2045 if (info
->available_in
)
2048 bitmap_copy (info
->available_in
, info
->rd_in
);
2050 BITMAP_FREE (info
->available_in
);
2053 if (last_call
|| empty_p (info
->available_in
))
2054 /* The values available on exit from the block are exactly those that
2055 are available locally. This set doesn't change. */
2056 info
->available_out
= info
->available_locally
;
2057 else if (empty_p (info
->available_locally
) && empty_p (info
->rd_kill
))
2058 /* The values available on exit are the same as those available on entry.
2059 Updating one updates the other. */
2060 info
->available_out
= info
->available_in
;
2062 set_available_out (info
);
2065 /* Process each block as for process_block, visiting dominators before
2066 the blocks they dominate. */
2069 early_remat::local_phase (void)
2072 fprintf (dump_file
, "\n;; Local phase:\n");
2074 int *postorder
= df_get_postorder (DF_BACKWARD
);
2075 unsigned int postorder_len
= df_get_n_blocks (DF_BACKWARD
);
2076 for (unsigned int i
= postorder_len
; i
-- > 0; )
2077 if (postorder
[i
] >= NUM_FIXED_BLOCKS
)
2078 process_block (BASIC_BLOCK_FOR_FN (m_fn
, postorder
[i
]));
2081 /* Return true if available values survive across edge E. */
2084 available_across_edge_p (edge e
)
2086 return (e
->flags
& EDGE_EH
) == 0;
2089 /* Propagate information from the available_out set of E->src to the
2090 available_in set of E->dest, when computing global availability.
2091 Return true if something changed. */
2094 early_remat::avail_confluence_n (edge e
)
2096 remat_block_info
*src
= &er
->m_block_info
[e
->src
->index
];
2097 remat_block_info
*dest
= &er
->m_block_info
[e
->dest
->index
];
2099 if (!available_across_edge_p (e
))
2102 if (empty_p (dest
->available_in
))
2105 if (!src
->available_out
)
2107 bitmap_clear (dest
->available_in
);
2111 return bitmap_and_into (dest
->available_in
, src
->available_out
);
2114 /* Propagate information from the available_in set of block BB_INDEX
2115 to available_out. Return true if something changed. */
2118 early_remat::avail_transfer (int bb_index
)
2120 remat_block_info
*info
= &er
->m_block_info
[bb_index
];
2122 if (info
->available_out
== info
->available_locally
)
2125 if (info
->available_out
== info
->available_in
)
2126 /* Assume that we are only called if the input changed. */
2129 return er
->set_available_out (info
);
2132 /* Compute global availability for the function, starting with the local
2133 information computed by local_phase. */
2136 early_remat::compute_availability (void)
2138 /* We use df_simple_dataflow instead of the lcm routines for three reasons:
2140 (1) it avoids recomputing the traversal order;
2141 (2) many of the sets are likely to be sparse, so we don't necessarily
2142 want to use sbitmaps; and
2143 (3) it means we can avoid creating an explicit kill set for the call. */
2145 bitmap_clear (&m_tmp_bitmap
);
2146 bitmap_set_range (&m_tmp_bitmap
, 0, last_basic_block_for_fn (m_fn
));
2147 df_simple_dataflow (DF_FORWARD
, NULL
, NULL
,
2148 avail_confluence_n
, avail_transfer
,
2149 &m_tmp_bitmap
, df_get_postorder (DF_FORWARD
),
2150 df_get_n_blocks (DF_FORWARD
));
2153 /* Restrict the required_in sets to values that aren't available. */
2155 FOR_EACH_BB_FN (bb
, m_fn
)
2157 remat_block_info
*info
= &m_block_info
[bb
->index
];
2158 if (info
->required_in
&& info
->available_in
)
2159 bitmap_and_compl_into (info
->required_in
, info
->available_in
);
2163 /* Make sure that INFO's available_out and available_in sets are unique. */
2166 early_remat::unshare_available_sets (remat_block_info
*info
)
2168 if (info
->available_in
&& info
->available_in
== info
->available_out
)
2170 info
->available_in
= alloc_bitmap ();
2171 bitmap_copy (info
->available_in
, info
->available_out
);
2175 /* Return true if it is possible to move rematerializations from the
2176 destination of E to the source of E. */
2179 early_remat::can_move_across_edge_p (edge e
)
2181 return (available_across_edge_p (e
)
2182 && !m_block_info
[e
->src
->index
].abnormal_call_p
);
2185 /* Return true if it is cheaper to rematerialize values at the head of
2186 block QUERY_BB_INDEX instead of rematerializing in its predecessors. */
2189 early_remat::local_remat_cheaper_p (unsigned int query_bb_index
)
2191 if (m_block_info
[query_bb_index
].remat_frequency_valid_p
)
2192 return m_block_info
[query_bb_index
].local_remat_cheaper_p
;
2194 /* Iteratively compute the cost of rematerializing values in the
2195 predecessor blocks, then compare that with the cost of
2196 rematerializing at the head of the block.
2198 A cycle indicates that there is no call on that execution path,
2199 so it isn't necessary to rematerialize on that path. */
2200 auto_vec
<basic_block
, 16> stack
;
2201 stack
.quick_push (BASIC_BLOCK_FOR_FN (m_fn
, query_bb_index
));
2202 while (!stack
.is_empty ())
2204 basic_block bb
= stack
.last ();
2205 remat_block_info
*info
= &m_block_info
[bb
->index
];
2206 if (info
->remat_frequency_valid_p
)
2212 info
->visited_p
= true;
2214 bool can_move_p
= true;
2217 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2218 if (!can_move_across_edge_p (e
))
2223 else if (m_block_info
[e
->src
->index
].last_call
)
2224 /* We'll rematerialize after the call. */
2225 frequency
+= e
->src
->count
.to_frequency (m_fn
);
2226 else if (m_block_info
[e
->src
->index
].remat_frequency_valid_p
)
2227 /* Add the cost of rematerializing at the head of E->src
2228 or in its predecessors (whichever is cheaper). */
2229 frequency
+= m_block_info
[e
->src
->index
].remat_frequency
;
2230 else if (!m_block_info
[e
->src
->index
].visited_p
)
2231 /* Queue E->src and then revisit this block again. */
2232 stack
.safe_push (e
->src
);
2234 /* Come back to this block later if we need to process some of
2235 its predecessors. */
2236 if (stack
.last () != bb
)
2239 /* If rematerializing in and before the block have equal cost, prefer
2240 rematerializing in the block. This should shorten the live range. */
2241 int bb_frequency
= bb
->count
.to_frequency (m_fn
);
2242 if (!can_move_p
|| frequency
>= bb_frequency
)
2244 info
->local_remat_cheaper_p
= true;
2245 info
->remat_frequency
= bb_frequency
;
2248 info
->remat_frequency
= frequency
;
2249 info
->remat_frequency_valid_p
= true;
2250 info
->visited_p
= false;
2254 fprintf (dump_file
, ";; Need to rematerialize at the head of"
2255 " block %d; cannot move to predecessors.\n", bb
->index
);
2258 fprintf (dump_file
, ";; Block %d has frequency %d,"
2259 " rematerializing in predecessors has frequency %d",
2260 bb
->index
, bb_frequency
, frequency
);
2261 if (info
->local_remat_cheaper_p
)
2262 fprintf (dump_file
, "; prefer to rematerialize"
2265 fprintf (dump_file
, "; prefer to rematerialize"
2266 " in predecessors\n");
2271 return m_block_info
[query_bb_index
].local_remat_cheaper_p
;
2274 /* Return true if we cannot rematerialize candidate CAND_INDEX at the head of
2278 early_remat::need_to_move_candidate_p (unsigned int bb_index
,
2279 unsigned int cand_index
)
2281 remat_block_info
*info
= &m_block_info
[bb_index
];
2282 remat_candidate
*cand
= &m_candidates
[cand_index
];
2283 basic_block bb
= BASIC_BLOCK_FOR_FN (m_fn
, bb_index
);
2285 /* If there is more than one reaching definition of REGNO,
2286 we'll need to rematerialize in predecessors instead. */
2287 bitmap_and (&m_tmp_bitmap
, info
->rd_in
, m_regno_to_candidates
[cand
->regno
]);
2288 if (!bitmap_single_bit_set_p (&m_tmp_bitmap
))
2291 fprintf (dump_file
, ";; Cannot rematerialize %d at the"
2292 " head of block %d because there is more than one"
2293 " reaching definition of reg %d\n", cand_index
,
2294 bb_index
, cand
->regno
);
2298 /* Likewise if rematerializing CAND here would clobber a live register. */
2300 && bitmap_intersect_p (cand
->clobbers
, DF_LR_IN (bb
)))
2303 fprintf (dump_file
, ";; Cannot rematerialize %d at the"
2304 " head of block %d because it would clobber live"
2305 " registers\n", cand_index
, bb_index
);
2312 /* Set REQUIRED to the minimum set of candidates that must be rematerialized
2313 in predecessors of block BB_INDEX instead of at the start of the block. */
2316 early_remat::compute_minimum_move_set (unsigned int bb_index
,
2319 remat_block_info
*info
= &m_block_info
[bb_index
];
2320 bitmap_head remaining
;
2322 bitmap_clear (required
);
2323 bitmap_initialize (&remaining
, &m_obstack
);
2324 bitmap_copy (&remaining
, info
->required_in
);
2325 while (!bitmap_empty_p (&remaining
))
2327 unsigned int cand_index
= bitmap_first_set_bit (&remaining
);
2328 remat_candidate
*cand
= &m_candidates
[cand_index
];
2329 bitmap_clear_bit (&remaining
, cand_index
);
2331 /* Leave invalid candidates where they are. */
2332 if (!cand
->can_copy_p
)
2335 /* Decide whether to move this candidate. */
2336 if (!bitmap_bit_p (required
, cand_index
))
2338 if (!need_to_move_candidate_p (bb_index
, cand_index
))
2340 bitmap_set_bit (required
, cand_index
);
2343 /* Also move values used by the candidate, so that we don't
2344 rematerialize them twice. */
2347 bitmap_ior_and_into (required
, cand
->uses
, info
->required_in
);
2348 bitmap_ior_and_into (&remaining
, cand
->uses
, info
->required_in
);
2353 /* Make the predecessors of BB_INDEX rematerialize the candidates in
2354 REQUIRED. Add any blocks whose required_in set changes to
2358 early_remat::move_to_predecessors (unsigned int bb_index
, bitmap required
,
2359 bitmap pending_blocks
)
2361 if (empty_p (required
))
2363 remat_block_info
*dest_info
= &m_block_info
[bb_index
];
2364 basic_block bb
= BASIC_BLOCK_FOR_FN (m_fn
, bb_index
);
2367 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2369 remat_block_info
*src_info
= &m_block_info
[e
->src
->index
];
2371 /* Restrict the set we add to the reaching definitions. */
2372 bitmap_and (&m_tmp_bitmap
, required
, src_info
->rd_out
);
2373 if (bitmap_empty_p (&m_tmp_bitmap
))
2376 if (!can_move_across_edge_p (e
))
2378 /* We can't move the rematerialization and we can't do it at
2379 the start of the block either. In this case we just give up
2380 and rely on spilling to make the values available across E. */
2383 fprintf (dump_file
, ";; Cannot rematerialize the following"
2384 " candidates in block %d:", e
->src
->index
);
2385 dump_candidate_bitmap (required
);
2386 fprintf (dump_file
, "\n");
2391 /* Remove candidates that are already available. */
2392 if (src_info
->available_out
)
2394 bitmap_and_compl_into (&m_tmp_bitmap
, src_info
->available_out
);
2395 if (bitmap_empty_p (&m_tmp_bitmap
))
2399 /* Add the remaining candidates to the appropriate required set. */
2402 fprintf (dump_file
, ";; Moving this set from block %d"
2403 " to block %d:", bb_index
, e
->src
->index
);
2404 dump_candidate_bitmap (&m_tmp_bitmap
);
2405 fprintf (dump_file
, "\n");
2407 /* If the source block contains a call, we want to rematerialize
2408 after the call, otherwise we want to rematerialize at the start
2410 bitmap src_required
= get_bitmap (src_info
->last_call
2411 ? &src_info
->required_after_call
2412 : &src_info
->required_in
);
2413 if (bitmap_ior_into (src_required
, &m_tmp_bitmap
))
2415 if (!src_info
->last_call
)
2416 bitmap_set_bit (pending_blocks
, e
->src
->index
);
2417 unshare_available_sets (src_info
);
2418 bitmap_ior_into (get_bitmap (&src_info
->available_out
),
2423 /* The candidates are now available on entry to the block. */
2424 bitmap_and_compl_into (dest_info
->required_in
, required
);
2425 unshare_available_sets (dest_info
);
2426 bitmap_ior_into (get_bitmap (&dest_info
->available_in
), required
);
2429 /* Go through the candidates that are currently marked as being
2430 rematerialized at the beginning of a block. Decide in each case
2431 whether that's valid and profitable; if it isn't, move the
2432 rematerialization to predecessor blocks instead. */
2435 early_remat::choose_rematerialization_points (void)
2437 bitmap_head required
;
2438 bitmap_head pending_blocks
;
2440 int *postorder
= df_get_postorder (DF_BACKWARD
);
2441 unsigned int postorder_len
= df_get_n_blocks (DF_BACKWARD
);
2442 bitmap_initialize (&required
, &m_obstack
);
2443 bitmap_initialize (&pending_blocks
, &m_obstack
);
2445 /* Process the blocks in postorder, to reduce the number of iterations
2446 of the outer loop. */
2447 for (unsigned int i
= 0; i
< postorder_len
; ++i
)
2449 unsigned int bb_index
= postorder
[i
];
2450 remat_block_info
*info
= &m_block_info
[bb_index
];
2451 bitmap_clear_bit (&pending_blocks
, bb_index
);
2453 if (empty_p (info
->required_in
))
2456 if (info
->available_in
)
2457 gcc_checking_assert (!bitmap_intersect_p (info
->required_in
,
2458 info
->available_in
));
2460 if (local_remat_cheaper_p (bb_index
))
2462 /* We'd prefer to rematerialize at the head of the block.
2463 Only move candidates if we need to. */
2464 compute_minimum_move_set (bb_index
, &required
);
2465 move_to_predecessors (bb_index
, &required
, &pending_blocks
);
2468 move_to_predecessors (bb_index
, info
->required_in
,
2471 while (!bitmap_empty_p (&pending_blocks
));
2472 bitmap_clear (&required
);
2475 /* Emit all rematerialization instructions queued for BB. */
2478 early_remat::emit_remat_insns_for_block (basic_block bb
)
2480 remat_block_info
*info
= &m_block_info
[bb
->index
];
2482 if (info
->last_call
&& !empty_p (info
->required_after_call
))
2483 emit_remat_insns (info
->required_after_call
, NULL
,
2484 info
->rd_after_call
, info
->last_call
);
2486 if (!empty_p (info
->required_in
))
2488 rtx_insn
*insn
= BB_HEAD (bb
);
2489 while (insn
!= BB_END (bb
)
2490 && !INSN_P (NEXT_INSN (insn
)))
2491 insn
= NEXT_INSN (insn
);
2492 emit_remat_insns (info
->required_in
, info
->available_in
,
2497 /* Decide which candidates in each block's REQUIRED_IN set need to be
2498 rematerialized and decide where the rematerialization instructions
2499 should go. Emit queued rematerialization instructions at the start
2500 of blocks and after the last calls in blocks. */
2503 early_remat::global_phase (void)
2505 compute_availability ();
2508 fprintf (dump_file
, "\n;; Blocks after computing global"
2509 " availability:\n");
2513 choose_rematerialization_points ();
2516 fprintf (dump_file
, "\n;; Blocks after choosing rematerialization"
2522 FOR_EACH_BB_FN (bb
, m_fn
)
2523 emit_remat_insns_for_block (bb
);
2526 /* Main function for the pass. */
2529 early_remat::run (void)
2533 if (!collect_candidates ())
2538 finalize_candidate_indices ();
2540 dump_all_candidates ();
2543 decide_candidate_validity ();
2548 early_remat::early_remat (function
*fn
, sbitmap selected_modes
)
2550 m_selected_modes (selected_modes
),
2555 bitmap_obstack_initialize (&m_obstack
);
2556 bitmap_initialize (&m_candidate_regnos
, &m_obstack
);
2557 bitmap_initialize (&m_tmp_bitmap
, &m_obstack
);
2560 early_remat::~early_remat ()
2562 bitmap_obstack_release (&m_obstack
);
2567 const pass_data pass_data_early_remat
=
2569 RTL_PASS
, /* type */
2570 "early_remat", /* name */
2571 OPTGROUP_NONE
, /* optinfo_flags */
2572 TV_EARLY_REMAT
, /* tv_id */
2573 0, /* properties_required */
2574 0, /* properties_provided */
2575 0, /* properties_destroyed */
2576 0, /* todo_flags_start */
2577 TODO_df_finish
, /* todo_flags_finish */
2580 class pass_early_remat
: public rtl_opt_pass
2583 pass_early_remat (gcc::context
*ctxt
)
2584 : rtl_opt_pass (pass_data_early_remat
, ctxt
)
2587 /* opt_pass methods: */
2588 virtual bool gate (function
*)
2590 return optimize
> 1 && NUM_POLY_INT_COEFFS
> 1;
2593 virtual unsigned int execute (function
*f
)
2595 auto_sbitmap
selected_modes (NUM_MACHINE_MODES
);
2596 bitmap_clear (selected_modes
);
2597 targetm
.select_early_remat_modes (selected_modes
);
2598 if (!bitmap_empty_p (selected_modes
))
2599 early_remat (f
, selected_modes
).run ();
2602 }; // class pass_early_remat
2607 make_pass_early_remat (gcc::context
*ctxt
)
2609 return new pass_early_remat (ctxt
);