1/* Early (pre-RA) rematerialization
2 Copyright (C) 2017-2023 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "backend.h"
24#include "rtl.h"
25#include "df.h"
26#include "tree-pass.h"
27#include "memmodel.h"
28#include "emit-rtl.h"
29#include "insn-config.h"
30#include "recog.h"
31/* FIXME: The next two are only needed for gen_move_insn. */
32#include "tree.h"
33#include "expr.h"
34#include "target.h"
35#include "inchash.h"
36#include "rtlhash.h"
37#include "print-rtl.h"
38#include "rtl-iter.h"
39#include "regs.h"
40#include "function-abi.h"
41
42/* This pass runs before register allocation and implements an aggressive
43 form of rematerialization. It looks for pseudo registers R of mode M
44 for which:
45
46 (a) there are no call-preserved registers of mode M; and
47 (b) spilling R to the stack is expensive.
48
49 The assumption is that it's better to recompute R after each call instead
50 of spilling it, even if this extends the live ranges of other registers.
51
52 The motivating example for which these conditions hold are AArch64 SVE
53 vectors and predicates. Spilling them to the stack makes the frame
54 variable-sized, which we'd like to avoid if possible. It's also very
55 rare for SVE values to be "naturally" live across a call: usually this
56 happens as a result of CSE or other code motion.
57
58 The pass is split into the following phases:
59
60 Collection phase
61 ================
62
63 First we go through all pseudo registers looking for any that meet
64 the conditions above. For each such register R, we go through each
65 instruction that defines R to see whether any of them are suitable
66 rematerialization candidates. If at least one is, we treat all the
67 instructions that define R as candidates, but record which ones are
68 not in fact suitable. These unsuitable candidates exist only for the
69 sake of calculating reaching definitions (see below).
70
71 A "candidate" is a single instruction that we want to rematerialize
72 and a "candidate register" is a register that is set by at least one
73 candidate.
74
75 Candidate sorting
76 =================
77
78 Next we sort the candidates based on the cfg postorder, so that if
79 candidate C1 uses candidate C2, C1 has a lower index than C2.
80 This is useful when iterating through candidate bitmaps.
81
82 Reaching definition calculation
83 ===============================
84
85 We then compute standard reaching-definition sets for each candidate.
86 Each set specifies which candidates might provide the current definition
87 of a live candidate register.
88
89 From here on, a candidate C is "live" at a point P if the candidate
90 register defined by C is live at P and if C's definition reaches P.
91 An instruction I "uses" a candidate C if I takes the register defined by
92 C as input and if C is one of the reaching definitions of that register.
93
94 Candidate validation and value numbering
95 ========================================
96
97 Next we simultaneously decide which candidates are valid and look
98 for candidates that are equivalent to each other, assigning numbers
99 to each unique candidate value. A candidate C is invalid if:
100
101 (a) C uses an invalid candidate;
102
103 (b) there is a cycle of candidate uses involving C; or
104
105 (c) C takes a candidate register R as input and the reaching
106 definitions of R do not have the same value number.
107
108 We assign a "representative" candidate C to each value number and from
109 here on replace references to other candidates with that value number
110 with references to C. It is then only possible to rematerialize a
111 register R at point P if (after this replacement) there is a single
112 reaching definition of R at P.
113
114 Local phase
115 ===========
116
117 During this phase we go through each block and look for cases in which:
118
119 (a) an instruction I comes between two call instructions CI1 and CI2;
120
121 (b) I uses a candidate register R;
122
123 (c) a candidate C provides the only reaching definition of R; and
124
125 (d) C does not come between CI1 and I.
126
127 We then emit a copy of C after CI1, as well as the transitive closure
128 TC of the candidates used by C. The copies of TC might use the original
129 candidate registers or new temporary registers, depending on circumstances.
130
131 For example, if elsewhere we have:
132
133 C3: R3 <- f3 (...)
134 ...
135 C2: R2 <- f2 (...)
136 ...
137 C1: R1 <- f1 (R2, R3, ...) // uses C2 and C3
138
139 then for a block containing:
140
141 CI1: call
142 ...
143 I: use R1 // uses C1
144 ...
145 CI2: call
146
147 we would emit:
148
149 CI1: call
150 C3': R3' <- f3 (...)
151 C2': R2' <- f2 (...)
152 C1': R1 <- f1 (R2', R3', ...)
153 ...
154 I: use R1
155 ...
156 CI2: call
157
158 where R2' and R3' might be fresh registers. If instead we had:
159
160 CI1: call
161 ...
162 I1: use R1 // uses C1
163 ...
164 I2: use R3 // uses C3
165 ...
166 CI2: call
167
168 we would keep the original R3:
169
170 CI1: call
171 C3': R3 <- f3 (...)
172 C2': R2' <- f2 (...)
173 C1': R1 <- f1 (R2', R3, ...)
174 ...
175 I1: use R1 // uses C1
176 ...
177 I2: use R3 // uses C3
178 ...
179 CI2: call
180
181 We also record the last call in each block (if any) and compute:
182
183 rd_after_call:
184 The set of candidates that either (a) are defined outside the block
185 and are live after the last call or (b) are defined within the block
186 and reach the end of the last call. (We don't track whether the
187 latter values are live or not.)
188
189 required_after_call:
190 The set of candidates that need to be rematerialized after the
191 last call in order to satisfy uses in the block itself.
192
193 required_in:
194 The set of candidates that are live on entry to the block and are
195 used without an intervening call.
196
197 In addition, we compute the initial values of the sets required by
198 the global phase below.
199
200 Global phase
201 ============
202
203 We next compute a maximal solution to the following availability
204 problem:
205
206 available_in:
207 The set of candidates that are live on entry to a block and can
208 be used at that point without rematerialization.
209
210 available_out:
211 The set of candidates that are live on exit from a block and can
212 be used at that point without rematerialization.
213
214 available_locally:
215 The subset of available_out that is due to code in the block itself.
216 It contains candidates that are defined or used in the block and
217 not invalidated by a later call.
218
219 We then go through each block B and look for an appropriate place
220 to insert copies of required_in - available_in. Conceptually we
221 start by placing the copies at the head of B, but then move the
222 copy of a candidate C to predecessors if:
223
224 (a) that seems cheaper;
225
226 (b) there is more than one reaching definition of C's register at
227 the head of B; or
228
229 (c) copying C would clobber a hard register that is live on entry to B.
230
231 Moving a copy of C to a predecessor block PB involves:
232
233 (1) adding C to PB's required_after_call, if PB contains a call; or
234
235 (2) adding C PB's required_in otherwise.
236
237 C is then available on output from each PB and on input to B.
238
239 Once all this is done, we emit instructions for the final required_in
240 and required_after_call sets. */
241
242namespace {
243
244/* An invalid candidate index, used to indicate that there is more than
245 one reaching definition. */
246const unsigned int MULTIPLE_CANDIDATES = -1U;
247
248/* Pass-specific information about one basic block. */
249struct remat_block_info {
250 /* The last call instruction in the block. */
251 rtx_insn *last_call;
252
253 /* The set of candidates that are live on entry to the block. NULL is
254 equivalent to an empty set. */
255 bitmap rd_in;
256
257 /* The set of candidates that are live on exit from the block. This might
258 reuse rd_in. NULL is equivalent to an empty set. */
259 bitmap rd_out;
260
261 /* The subset of RD_OUT that comes from local definitions. NULL is
262 equivalent to an empty set. */
263 bitmap rd_gen;
264
265 /* The set of candidates that the block invalidates (because it defines
266 the register to something else, or because the register's value is
267 no longer important). NULL is equivalent to an empty set. */
268 bitmap rd_kill;
269
270 /* The set of candidates that either (a) are defined outside the block
271 and are live after LAST_CALL or (b) are defined within the block
272 and reach the instruction after LAST_CALL. (We don't track whether
273 the latter values are live or not.)
274
275 Only used if LAST_CALL is nonnull. NULL is equivalent to an
276 empty set. */
277 bitmap rd_after_call;
278
279 /* Candidates that are live and available without rematerialization
280 on entry to the block. NULL is equivalent to an empty set. */
281 bitmap available_in;
282
283 /* Candidates that become available without rematerialization within the
284 block, and remain so on exit. NULL is equivalent to an empty set. */
285 bitmap available_locally;
286
287 /* Candidates that are available without rematerialization on exit from
288 the block. This might reuse available_in or available_locally. */
289 bitmap available_out;
290
291 /* Candidates that need to be rematerialized either at the start of the
292 block or before entering the block. */
293 bitmap required_in;
294
295 /* Candidates that need to be rematerialized after LAST_CALL.
296 Only used if LAST_CALL is nonnull. */
297 bitmap required_after_call;
298
299 /* The number of candidates in the block. */
300 unsigned int num_candidates;
301
302 /* The earliest candidate in the block (i.e. the one with the
303 highest index). Only valid if NUM_CANDIDATES is nonzero. */
304 unsigned int first_candidate;
305
306 /* The best (lowest) execution frequency for rematerializing REQUIRED_IN.
307 This is the execution frequency of the block if LOCAL_REMAT_CHEAPER_P,
308 otherwise it is the sum of the execution frequencies of whichever
309 predecessor blocks would do the rematerialization. */
310 int remat_frequency;
311
312 /* True if the block ends with an abnormal call. */
313 unsigned int abnormal_call_p : 1;
314
315 /* Used to record whether a graph traversal has visited this block. */
316 unsigned int visited_p : 1;
317
318 /* True if we have calculated REMAT_FREQUENCY. */
319 unsigned int remat_frequency_valid_p : 1;
320
321 /* True if it is cheaper to rematerialize candidates at the start of
322 the block, rather than moving them to predecessor blocks. */
323 unsigned int local_remat_cheaper_p : 1;
324};
325
326/* Information about a group of candidates with the same value number. */
327struct remat_equiv_class {
328 /* The candidates that have the same value number. */
329 bitmap members;
330
331 /* The candidate that was first added to MEMBERS. */
332 unsigned int earliest;
333
334 /* The candidate that represents the others. This is always the one
335 with the highest index. */
336 unsigned int representative;
337};
338
339/* Information about an instruction that we might want to rematerialize. */
340struct remat_candidate {
341 /* The pseudo register that the instruction sets. */
342 unsigned int regno;
343
344 /* A temporary register used when rematerializing uses of this candidate,
345 if REGNO doesn't have the right value or isn't worth using. */
346 unsigned int copy_regno;
347
348 /* True if we intend to rematerialize this instruction by emitting
349 a move of a constant into REGNO, false if we intend to emit a
350 copy of the original instruction. */
351 unsigned int constant_p : 1;
352
353 /* True if we still think it's possible to rematerialize INSN. */
354 unsigned int can_copy_p : 1;
355
356 /* Used to record whether a graph traversal has visited this candidate. */
357 unsigned int visited_p : 1;
358
359 /* True if we have verified that it's possible to rematerialize INSN.
360 Once this is true, both it and CAN_COPY_P remain true. */
361 unsigned int validated_p : 1;
362
363 /* True if we have "stabilized" INSN, i.e. ensured that all non-candidate
364 registers read by INSN will have the same value when rematerializing INSN.
365 Only ever true if CAN_COPY_P. */
366 unsigned int stabilized_p : 1;
367
368 /* Hash value used for value numbering. */
369 hashval_t hash;
370
371 /* The instruction that sets REGNO. */
372 rtx_insn *insn;
373
374 /* If CONSTANT_P, the value that should be moved into REGNO when
375 rematerializing, otherwise the pattern of the instruction that
376 should be used. */
377 rtx remat_rtx;
378
379 /* The set of candidates that INSN takes as input. NULL is equivalent
380 to the empty set. All candidates in this set have a higher index
381 than the current candidate. */
382 bitmap uses;
383
384 /* The set of hard registers that would be clobbered by rematerializing
385 the candidate, including (transitively) all those that would be
386 clobbered by rematerializing USES. */
387 bitmap clobbers;
388
389 /* The equivalence class to which the candidate belongs, or null if none. */
390 remat_equiv_class *equiv_class;
391};
392
393/* Hash functions used for value numbering. */
394struct remat_candidate_hasher : nofree_ptr_hash <remat_candidate>
395{
396 typedef value_type compare_type;
397 static hashval_t hash (const remat_candidate *);
398 static bool equal (const remat_candidate *, const remat_candidate *);
399};
400
401/* Main class for this pass. */
402class early_remat {
403public:
404 early_remat (function *, sbitmap);
405 ~early_remat ();
406
407 void run (void);
408
409private:
410 bitmap alloc_bitmap (void);
411 bitmap get_bitmap (bitmap *);
412 void init_temp_bitmap (bitmap *);
413 void copy_temp_bitmap (bitmap *, bitmap *);
414
415 void dump_insn_id (rtx_insn *);
416 void dump_candidate_bitmap (bitmap);
417 void dump_all_candidates (void);
418 void dump_edge_list (basic_block, bool);
419 void dump_block_info (basic_block);
420 void dump_all_blocks (void);
421
422 bool interesting_regno_p (unsigned int);
423 remat_candidate *add_candidate (rtx_insn *, unsigned int, bool);
424 bool maybe_add_candidate (rtx_insn *, unsigned int);
425 bool collect_candidates (void);
426 void init_block_info (void);
427 void sort_candidates (void);
428 void finalize_candidate_indices (void);
429 void record_equiv_candidates (unsigned int, unsigned int);
430 static bool rd_confluence_n (edge);
431 static bool rd_transfer (int);
432 void compute_rd (void);
433 unsigned int canon_candidate (unsigned int);
434 void canon_bitmap (bitmap *);
435 unsigned int resolve_reaching_def (bitmap);
436 bool check_candidate_uses (unsigned int);
437 void compute_clobbers (unsigned int);
438 void assign_value_number (unsigned int);
439 void decide_candidate_validity (void);
440 void restrict_remat_for_unavail_regs (bitmap, const_bitmap);
441 void restrict_remat_for_call (bitmap, rtx_insn *);
442 bool stable_use_p (unsigned int);
443 void emit_copy_before (unsigned int, rtx, rtx);
444 void stabilize_pattern (unsigned int);
445 void replace_dest_with_copy (unsigned int);
446 void stabilize_candidate_uses (unsigned int, bitmap, bitmap, bitmap,
447 bitmap);
448 void emit_remat_insns (bitmap, bitmap, bitmap, rtx_insn *);
449 bool set_available_out (remat_block_info *);
450 void process_block (basic_block);
451 void local_phase (void);
452 static bool avail_confluence_n (edge);
453 static bool avail_transfer (int);
454 void compute_availability (void);
455 void unshare_available_sets (remat_block_info *);
456 bool can_move_across_edge_p (edge);
457 bool local_remat_cheaper_p (unsigned int);
458 bool need_to_move_candidate_p (unsigned int, unsigned int);
459 void compute_minimum_move_set (unsigned int, bitmap);
460 void move_to_predecessors (unsigned int, bitmap, bitmap);
461 void choose_rematerialization_points (void);
462 void emit_remat_insns_for_block (basic_block);
463 void global_phase (void);
464
465 /* The function that we're optimizing. */
466 function *m_fn;
467
468 /* The modes that we want to rematerialize. */
469 sbitmap m_selected_modes;
470
471 /* All rematerialization candidates, identified by their index into the
472 vector. */
473 auto_vec<remat_candidate> m_candidates;
474
475 /* The set of candidate registers. */
476 bitmap_head m_candidate_regnos;
477
478 /* Temporary sets. */
479 bitmap_head m_tmp_bitmap;
480 bitmap m_available;
481 bitmap m_required;
482
483 /* Information about each basic block. */
484 auto_vec<remat_block_info> m_block_info;
485
486 /* A mapping from register numbers to the set of associated candidates.
487 Only valid for registers in M_CANDIDATE_REGNOS. */
488 auto_vec<bitmap> m_regno_to_candidates;
489
490 /* An obstack used for allocating bitmaps, so that we can free them all
491 in one go. */
492 bitmap_obstack m_obstack;
493
494 /* A hash table of candidates used for value numbering. If a candidate
495 in the table is in an equivalence class, the candidate is marked as
496 the earliest member of the class. */
497 hash_table<remat_candidate_hasher> m_value_table;
498
499 /* Used temporarily by callback functions. */
500 static early_remat *er;
501};
502
503}
504
505early_remat *early_remat::er;
506
507/* rtx_equal_p callback that treats any two SCRATCHes as equal.
508 This allows us to compare two copies of a pattern, even though their
509 SCRATCHes are always distinct. */
510
511static bool
512scratch_equal (const_rtx *x, const_rtx *y, rtx *nx, rtx *ny)
513{
514 if (GET_CODE (*x) == SCRATCH && GET_CODE (*y) == SCRATCH)
515 {
516 *nx = const0_rtx;
517 *ny = const0_rtx;
518 return true;
519 }
520 return false;
521}
522
523/* Hash callback functions for remat_candidate. */
524
525hashval_t
526remat_candidate_hasher::hash (const remat_candidate *cand)
527{
528 return cand->hash;
529}
530
531bool
532remat_candidate_hasher::equal (const remat_candidate *cand1,
533 const remat_candidate *cand2)
534{
535 return (cand1->regno == cand2->regno
536 && cand1->constant_p == cand2->constant_p
537 && rtx_equal_p (cand1->remat_rtx, cand2->remat_rtx,
538 cand1->constant_p ? NULL : scratch_equal)
539 && (!cand1->uses || bitmap_equal_p (cand1->uses, cand2->uses)));
540}
541
542/* Return true if B is null or empty. */
543
544inline bool
545empty_p (bitmap b)
546{
547 return !b || bitmap_empty_p (map: b);
548}
549
550/* Allocate a new bitmap. It will be automatically freed at the end of
551 the pass. */
552
553inline bitmap
554early_remat::alloc_bitmap (void)
555{
556 return bitmap_alloc (obstack: &m_obstack);
557}
558
559/* Initialize *PTR to an empty bitmap if it is currently null. */
560
561inline bitmap
562early_remat::get_bitmap (bitmap *ptr)
563{
564 if (!*ptr)
565 *ptr = alloc_bitmap ();
566 return *ptr;
567}
568
569/* *PTR is either null or empty. If it is null, initialize it to an
570 empty bitmap. */
571
572inline void
573early_remat::init_temp_bitmap (bitmap *ptr)
574{
575 if (!*ptr)
576 *ptr = alloc_bitmap ();
577 else
578 gcc_checking_assert (bitmap_empty_p (*ptr));
579}
580
581/* Move *SRC to *DEST and leave *SRC empty. */
582
583inline void
584early_remat::copy_temp_bitmap (bitmap *dest, bitmap *src)
585{
586 if (!empty_p (b: *src))
587 {
588 *dest = *src;
589 *src = NULL;
590 }
591 else
592 *dest = NULL;
593}
594
595/* Print INSN's identifier to the dump file. */
596
597void
598early_remat::dump_insn_id (rtx_insn *insn)
599{
600 fprintf (stream: dump_file, format: "%d[bb:%d]", INSN_UID (insn),
601 BLOCK_FOR_INSN (insn)->index);
602}
603
604/* Print candidate set CANDIDATES to the dump file, with a leading space. */
605
606void
607early_remat::dump_candidate_bitmap (bitmap candidates)
608{
609 if (empty_p (b: candidates))
610 {
611 fprintf (stream: dump_file, format: " none");
612 return;
613 }
614
615 unsigned int cand_index;
616 bitmap_iterator bi;
617 EXECUTE_IF_SET_IN_BITMAP (candidates, 0, cand_index, bi)
618 fprintf (stream: dump_file, format: " %d", cand_index);
619}
620
621/* Print information about all candidates to the dump file. */
622
623void
624early_remat::dump_all_candidates (void)
625{
626 fprintf (stream: dump_file, format: "\n;; Candidates:\n;;\n");
627 fprintf (stream: dump_file, format: ";; %5s %5s %8s %s\n", "#", "reg", "mode", "insn");
628 fprintf (stream: dump_file, format: ";; %5s %5s %8s %s\n", "=", "===", "====", "====");
629 unsigned int cand_index;
630 remat_candidate *cand;
631 FOR_EACH_VEC_ELT (m_candidates, cand_index, cand)
632 {
633 fprintf (stream: dump_file, format: ";; %5d %5d %8s ", cand_index, cand->regno,
634 GET_MODE_NAME (GET_MODE (regno_reg_rtx[cand->regno])));
635 dump_insn_id (insn: cand->insn);
636 if (!cand->can_copy_p)
637 fprintf (stream: dump_file, format: " -- can't copy");
638 fprintf (stream: dump_file, format: "\n");
639 }
640
641 fprintf (stream: dump_file, format: "\n;; Register-to-candidate mapping:\n;;\n");
642 unsigned int regno;
643 bitmap_iterator bi;
644 EXECUTE_IF_SET_IN_BITMAP (&m_candidate_regnos, 0, regno, bi)
645 {
646 fprintf (stream: dump_file, format: ";; %5d:", regno);
647 dump_candidate_bitmap (candidates: m_regno_to_candidates[regno]);
648 fprintf (stream: dump_file, format: "\n");
649 }
650}
651
652/* Print the predecessors or successors of BB to the dump file, with a
653 leading space. DO_SUCC is true to print successors and false to print
654 predecessors. */
655
656void
657early_remat::dump_edge_list (basic_block bb, bool do_succ)
658{
659 edge e;
660 edge_iterator ei;
661 FOR_EACH_EDGE (e, ei, do_succ ? bb->succs : bb->preds)
662 dump_edge_info (dump_file, e, TDF_NONE, do_succ);
663}
664
665/* Print information about basic block BB to the dump file. */
666
667void
668early_remat::dump_block_info (basic_block bb)
669{
670 remat_block_info *info = &m_block_info[bb->index];
671 fprintf (stream: dump_file, format: ";;\n;; Block %d:", bb->index);
672 int width = 25;
673
674 fprintf (stream: dump_file, format: "\n;;%*s:", width, "predecessors");
675 dump_edge_list (bb, do_succ: false);
676
677 fprintf (stream: dump_file, format: "\n;;%*s:", width, "successors");
678 dump_edge_list (bb, do_succ: true);
679
680 fprintf (stream: dump_file, format: "\n;;%*s: %d", width, "frequency",
681 bb->count.to_frequency (fun: m_fn));
682
683 if (info->last_call)
684 fprintf (stream: dump_file, format: "\n;;%*s: %d", width, "last call",
685 INSN_UID (insn: info->last_call));
686
687 if (!empty_p (b: info->rd_in))
688 {
689 fprintf (stream: dump_file, format: "\n;;%*s:", width, "RD in");
690 dump_candidate_bitmap (candidates: info->rd_in);
691 }
692 if (!empty_p (b: info->rd_kill))
693 {
694 fprintf (stream: dump_file, format: "\n;;%*s:", width, "RD kill");
695 dump_candidate_bitmap (candidates: info->rd_kill);
696 }
697 if (!empty_p (b: info->rd_gen))
698 {
699 fprintf (stream: dump_file, format: "\n;;%*s:", width, "RD gen");
700 dump_candidate_bitmap (candidates: info->rd_gen);
701 }
702 if (!empty_p (b: info->rd_after_call))
703 {
704 fprintf (stream: dump_file, format: "\n;;%*s:", width, "RD after call");
705 dump_candidate_bitmap (candidates: info->rd_after_call);
706 }
707 if (!empty_p (b: info->rd_out))
708 {
709 fprintf (stream: dump_file, format: "\n;;%*s:", width, "RD out");
710 if (info->rd_in == info->rd_out)
711 fprintf (stream: dump_file, format: " RD in");
712 else
713 dump_candidate_bitmap (candidates: info->rd_out);
714 }
715 if (!empty_p (b: info->available_in))
716 {
717 fprintf (stream: dump_file, format: "\n;;%*s:", width, "available in");
718 dump_candidate_bitmap (candidates: info->available_in);
719 }
720 if (!empty_p (b: info->available_locally))
721 {
722 fprintf (stream: dump_file, format: "\n;;%*s:", width, "available locally");
723 dump_candidate_bitmap (candidates: info->available_locally);
724 }
725 if (!empty_p (b: info->available_out))
726 {
727 fprintf (stream: dump_file, format: "\n;;%*s:", width, "available out");
728 if (info->available_in == info->available_out)
729 fprintf (stream: dump_file, format: " available in");
730 else if (info->available_locally == info->available_out)
731 fprintf (stream: dump_file, format: " available locally");
732 else
733 dump_candidate_bitmap (candidates: info->available_out);
734 }
735 if (!empty_p (b: info->required_in))
736 {
737 fprintf (stream: dump_file, format: "\n;;%*s:", width, "required in");
738 dump_candidate_bitmap (candidates: info->required_in);
739 }
740 if (!empty_p (b: info->required_after_call))
741 {
742 fprintf (stream: dump_file, format: "\n;;%*s:", width, "required after call");
743 dump_candidate_bitmap (candidates: info->required_after_call);
744 }
745 fprintf (stream: dump_file, format: "\n");
746}
747
748/* Print information about all basic blocks to the dump file. */
749
750void
751early_remat::dump_all_blocks (void)
752{
753 basic_block bb;
754 FOR_EACH_BB_FN (bb, m_fn)
755 dump_block_info (bb);
756}
757
758/* Return true if REGNO is worth rematerializing. */
759
760bool
761early_remat::interesting_regno_p (unsigned int regno)
762{
763 /* Ignore unused registers. */
764 rtx reg = regno_reg_rtx[regno];
765 if (!reg || DF_REG_DEF_COUNT (regno) == 0)
766 return false;
767
768 /* Make sure the register has a mode that we want to rematerialize. */
769 if (!bitmap_bit_p (map: m_selected_modes, GET_MODE (reg)))
770 return false;
771
772 /* Ignore values that might sometimes be used uninitialized. We could
773 instead add dummy candidates for the entry block definition, and so
774 handle uses that are definitely not uninitialized, but the combination
775 of the two should be rare in practice. */
776 if (bitmap_bit_p (DF_LR_OUT (ENTRY_BLOCK_PTR_FOR_FN (m_fn)), regno))
777 return false;
778
779 return true;
780}
781
782/* Record the set of register REGNO in instruction INSN as a
783 rematerialization candidate. CAN_COPY_P is true unless we already
784 know that rematerialization is impossible (in which case the candidate
785 only exists for the reaching definition calculation).
786
787 The candidate's index is not fixed at this stage. */
788
789remat_candidate *
790early_remat::add_candidate (rtx_insn *insn, unsigned int regno,
791 bool can_copy_p)
792{
793 remat_candidate cand;
794 memset (s: &cand, c: 0, n: sizeof (cand));
795 cand.regno = regno;
796 cand.insn = insn;
797 cand.remat_rtx = PATTERN (insn);
798 cand.can_copy_p = can_copy_p;
799 m_candidates.safe_push (obj: cand);
800
801 bitmap_set_bit (&m_candidate_regnos, regno);
802
803 return &m_candidates.last ();
804}
805
806/* Return true if we can rematerialize the set of register REGNO in
807 instruction INSN, and add it as a candidate if so. When returning
808 false, print the reason to the dump file. */
809
810bool
811early_remat::maybe_add_candidate (rtx_insn *insn, unsigned int regno)
812{
813#define FAILURE_FORMAT ";; Can't rematerialize set of reg %d in %d[bb:%d]: "
814#define FAILURE_ARGS regno, INSN_UID (insn), BLOCK_FOR_INSN (insn)->index
815
816 /* The definition must come from an ordinary instruction. */
817 basic_block bb = BLOCK_FOR_INSN (insn);
818 if (!NONJUMP_INSN_P (insn)
819 || (insn == BB_END (bb)
820 && has_abnormal_or_eh_outgoing_edge_p (bb)))
821 {
822 if (dump_file)
823 fprintf (stream: dump_file, FAILURE_FORMAT "insn alters control flow\n",
824 FAILURE_ARGS);
825 return false;
826 }
827
828 /* Prefer to rematerialize constants directly -- it's much easier. */
829 machine_mode mode = GET_MODE (regno_reg_rtx[regno]);
830 if (rtx note = find_reg_equal_equiv_note (insn))
831 {
832 rtx val = XEXP (note, 0);
833 if (CONSTANT_P (val)
834 && targetm.legitimate_constant_p (mode, val))
835 {
836 remat_candidate *cand = add_candidate (insn, regno, can_copy_p: true);
837 cand->constant_p = true;
838 cand->remat_rtx = val;
839 return true;
840 }
841 }
842
843 /* See whether the target has reasons to prevent a copy. */
844 if (targetm.cannot_copy_insn_p && targetm.cannot_copy_insn_p (insn))
845 {
846 if (dump_file)
847 fprintf (stream: dump_file, FAILURE_FORMAT "target forbids copying\n",
848 FAILURE_ARGS);
849 return false;
850 }
851
852 /* We can't copy trapping instructions. */
853 rtx pat = PATTERN (insn);
854 if (may_trap_p (pat))
855 {
856 if (dump_file)
857 fprintf (stream: dump_file, FAILURE_FORMAT "insn might trap\n", FAILURE_ARGS);
858 return false;
859 }
860
861 /* We can't copy instructions that read memory, unless we know that
862 the contents never change. */
863 subrtx_iterator::array_type array;
864 FOR_EACH_SUBRTX (iter, array, pat, ALL)
865 if (MEM_P (*iter) && !MEM_READONLY_P (*iter))
866 {
867 if (dump_file)
868 fprintf (stream: dump_file, FAILURE_FORMAT "insn references non-constant"
869 " memory\n", FAILURE_ARGS);
870 return false;
871 }
872
873 /* Check each defined register. */
874 df_ref ref;
875 FOR_EACH_INSN_DEF (ref, insn)
876 {
877 unsigned int def_regno = DF_REF_REGNO (ref);
878 if (def_regno == regno)
879 {
880 /* Make sure the definition is write-only. (Partial definitions,
881 such as setting the low part and clobbering the high part,
882 are otherwise OK.) */
883 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_READ_WRITE))
884 {
885 if (dump_file)
886 fprintf (stream: dump_file, FAILURE_FORMAT "destination is"
887 " read-modify-write\n", FAILURE_ARGS);
888 return false;
889 }
890 }
891 else
892 {
893 /* The instruction can set additional registers, provided that
894 they're hard registers. This is useful for instructions
895 that alter the condition codes. */
896 if (!HARD_REGISTER_NUM_P (def_regno))
897 {
898 if (dump_file)
899 fprintf (stream: dump_file, FAILURE_FORMAT "insn also sets"
900 " pseudo reg %d\n", FAILURE_ARGS, def_regno);
901 return false;
902 }
903 }
904 }
905
906 /* If the instruction uses fixed hard registers, check that those
907 registers have the same value throughout the function. If the
908 instruction uses non-fixed hard registers, check that we can
909 replace them with pseudos. */
910 FOR_EACH_INSN_USE (ref, insn)
911 {
912 unsigned int use_regno = DF_REF_REGNO (ref);
913 if (HARD_REGISTER_NUM_P (use_regno) && fixed_regs[use_regno])
914 {
915 if (rtx_unstable_p (DF_REF_REAL_REG (ref)))
916 {
917 if (dump_file)
918 fprintf (stream: dump_file, FAILURE_FORMAT "insn uses fixed hard reg"
919 " %d\n", FAILURE_ARGS, use_regno);
920 return false;
921 }
922 }
923 else if (HARD_REGISTER_NUM_P (use_regno))
924 {
925 /* Allocate a dummy pseudo register and temporarily install it.
926 Make the register number depend on the mode, which should
927 provide enough sharing for match_dup while also weeding
928 out cases in which operands with different modes are
929 explicitly tied. */
930 rtx *loc = DF_REF_REAL_LOC (ref);
931 unsigned int size = RTX_CODE_SIZE (REG);
932 rtx new_reg = (rtx) alloca (size);
933 memset (s: new_reg, c: 0, n: size);
934 PUT_CODE (new_reg, REG);
935 set_mode_and_regno (new_reg, GET_MODE (*loc),
936 LAST_VIRTUAL_REGISTER + 1 + GET_MODE (*loc));
937 validate_change (insn, loc, new_reg, 1);
938 }
939 }
940 bool ok_p = verify_changes (0);
941 cancel_changes (0);
942 if (!ok_p)
943 {
944 if (dump_file)
945 fprintf (stream: dump_file, FAILURE_FORMAT "insn does not allow hard"
946 " register inputs to be replaced\n", FAILURE_ARGS);
947 return false;
948 }
949
950#undef FAILURE_ARGS
951#undef FAILURE_FORMAT
952
953 add_candidate (insn, regno, can_copy_p: true);
954 return true;
955}
956
957/* Calculate the set of rematerialization candidates. Return true if
958 we find at least one. */
959
960bool
961early_remat::collect_candidates (void)
962{
963 unsigned int nregs = DF_REG_SIZE (df);
964 for (unsigned int regno = FIRST_PSEUDO_REGISTER; regno < nregs; ++regno)
965 if (interesting_regno_p (regno))
966 {
967 /* Create candidates for all suitable definitions. */
968 bitmap_clear (&m_tmp_bitmap);
969 unsigned int bad = 0;
970 unsigned int id = 0;
971 for (df_ref ref = DF_REG_DEF_CHAIN (regno); ref;
972 ref = DF_REF_NEXT_REG (ref))
973 {
974 rtx_insn *insn = DF_REF_INSN (ref);
975 if (maybe_add_candidate (insn, regno))
976 bitmap_set_bit (&m_tmp_bitmap, id);
977 else
978 bad += 1;
979 id += 1;
980 }
981
982 /* If we found at least one suitable definition, add dummy
983 candidates for the rest, so that we can see which definitions
984 are live where. */
985 if (!bitmap_empty_p (map: &m_tmp_bitmap) && bad)
986 {
987 id = 0;
988 for (df_ref ref = DF_REG_DEF_CHAIN (regno); ref;
989 ref = DF_REF_NEXT_REG (ref))
990 {
991 if (!bitmap_bit_p (&m_tmp_bitmap, id))
992 add_candidate (DF_REF_INSN (ref), regno, can_copy_p: false);
993 id += 1;
994 }
995 }
996 }
997
998
999 return !m_candidates.is_empty ();
1000}
1001
1002/* Initialize the m_block_info array. */
1003
1004void
1005early_remat::init_block_info (void)
1006{
1007 unsigned int n_blocks = last_basic_block_for_fn (m_fn);
1008 m_block_info.safe_grow_cleared (len: n_blocks, exact: true);
1009}
1010
1011/* Maps basic block indices to their position in the forward RPO. */
1012static unsigned int *rpo_index;
1013
1014/* Order remat_candidates X_IN and Y_IN according to the cfg postorder. */
1015
1016static int
1017compare_candidates (const void *x_in, const void *y_in)
1018{
1019 const remat_candidate *x = (const remat_candidate *) x_in;
1020 const remat_candidate *y = (const remat_candidate *) y_in;
1021 basic_block x_bb = BLOCK_FOR_INSN (insn: x->insn);
1022 basic_block y_bb = BLOCK_FOR_INSN (insn: y->insn);
1023 if (x_bb != y_bb)
1024 /* Make X and Y follow block postorder. */
1025 return rpo_index[y_bb->index] - rpo_index[x_bb->index];
1026
1027 /* Make X and Y follow a backward traversal of the containing block. */
1028 return DF_INSN_LUID (y->insn) - DF_INSN_LUID (x->insn);
1029}
1030
1031/* Sort the collected rematerialization candidates so that they follow
1032 cfg postorder. */
1033
1034void
1035early_remat::sort_candidates (void)
1036{
1037 /* Make sure the DF LUIDs are up-to-date for all the blocks we
1038 care about. */
1039 bitmap_clear (&m_tmp_bitmap);
1040 unsigned int cand_index;
1041 remat_candidate *cand;
1042 FOR_EACH_VEC_ELT (m_candidates, cand_index, cand)
1043 {
1044 basic_block bb = BLOCK_FOR_INSN (insn: cand->insn);
1045 if (bitmap_set_bit (&m_tmp_bitmap, bb->index))
1046 df_recompute_luids (bb);
1047 }
1048
1049 /* Create a mapping from block numbers to their position in the
1050 postorder. */
1051 unsigned int n_blocks = last_basic_block_for_fn (m_fn);
1052 int *rpo = df_get_postorder (DF_FORWARD);
1053 unsigned int rpo_len = df_get_n_blocks (DF_FORWARD);
1054 rpo_index = new unsigned int[n_blocks];
1055 for (unsigned int i = 0; i < rpo_len; ++i)
1056 rpo_index[rpo[i]] = i;
1057
1058 m_candidates.qsort (compare_candidates);
1059
1060 delete[] rpo_index;
1061}
1062
1063/* Commit to the current candidate indices and initialize cross-references. */
1064
1065void
1066early_remat::finalize_candidate_indices (void)
1067{
1068 /* Create a bitmap for each candidate register. */
1069 m_regno_to_candidates.safe_grow (len: max_reg_num (), exact: true);
1070 unsigned int regno;
1071 bitmap_iterator bi;
1072 EXECUTE_IF_SET_IN_BITMAP (&m_candidate_regnos, 0, regno, bi)
1073 m_regno_to_candidates[regno] = alloc_bitmap ();
1074
1075 /* Go through each candidate and record its index. */
1076 unsigned int cand_index;
1077 remat_candidate *cand;
1078 FOR_EACH_VEC_ELT (m_candidates, cand_index, cand)
1079 {
1080 basic_block bb = BLOCK_FOR_INSN (insn: cand->insn);
1081 remat_block_info *info = &m_block_info[bb->index];
1082 info->num_candidates += 1;
1083 info->first_candidate = cand_index;
1084 bitmap_set_bit (m_regno_to_candidates[cand->regno], cand_index);
1085 }
1086}
1087
1088/* Record that candidates CAND1_INDEX and CAND2_INDEX are equivalent.
1089 CAND1_INDEX might already have an equivalence class, but CAND2_INDEX
1090 doesn't. */
1091
1092void
1093early_remat::record_equiv_candidates (unsigned int cand1_index,
1094 unsigned int cand2_index)
1095{
1096 if (dump_file)
1097 fprintf (stream: dump_file, format: ";; Candidate %d is equivalent to candidate %d\n",
1098 cand2_index, cand1_index);
1099
1100 remat_candidate *cand1 = &m_candidates[cand1_index];
1101 remat_candidate *cand2 = &m_candidates[cand2_index];
1102 gcc_checking_assert (!cand2->equiv_class);
1103
1104 remat_equiv_class *ec = cand1->equiv_class;
1105 if (!ec)
1106 {
1107 ec = XOBNEW (&m_obstack.obstack, remat_equiv_class);
1108 ec->members = alloc_bitmap ();
1109 bitmap_set_bit (ec->members, cand1_index);
1110 ec->earliest = cand1_index;
1111 ec->representative = cand1_index;
1112 cand1->equiv_class = ec;
1113 }
1114 cand2->equiv_class = ec;
1115 bitmap_set_bit (ec->members, cand2_index);
1116 if (cand2_index > ec->representative)
1117 ec->representative = cand2_index;
1118}
1119
1120/* Propagate information from the rd_out set of E->src to the rd_in set
1121 of E->dest, when computing global reaching definitions. Return true
1122 if something changed. */
1123
1124bool
1125early_remat::rd_confluence_n (edge e)
1126{
1127 remat_block_info *src = &er->m_block_info[e->src->index];
1128 remat_block_info *dest = &er->m_block_info[e->dest->index];
1129
1130 /* available_in temporarily contains the set of candidates whose
1131 registers are live on entry. */
1132 if (empty_p (b: src->rd_out) || empty_p (b: dest->available_in))
1133 return false;
1134
1135 return bitmap_ior_and_into (DST: er->get_bitmap (ptr: &dest->rd_in),
1136 B: src->rd_out, C: dest->available_in);
1137}
1138
1139/* Propagate information from the rd_in set of block BB_INDEX to rd_out.
1140 Return true if something changed. */
1141
1142bool
1143early_remat::rd_transfer (int bb_index)
1144{
1145 remat_block_info *info = &er->m_block_info[bb_index];
1146
1147 if (empty_p (b: info->rd_in))
1148 return false;
1149
1150 if (empty_p (b: info->rd_kill))
1151 {
1152 gcc_checking_assert (empty_p (info->rd_gen));
1153 if (!info->rd_out)
1154 info->rd_out = info->rd_in;
1155 else
1156 gcc_checking_assert (info->rd_out == info->rd_in);
1157 /* Assume that we only get called if something changed. */
1158 return true;
1159 }
1160
1161 if (empty_p (b: info->rd_gen))
1162 return bitmap_and_compl (er->get_bitmap (ptr: &info->rd_out),
1163 info->rd_in, info->rd_kill);
1164
1165 return bitmap_ior_and_compl (DST: er->get_bitmap (ptr: &info->rd_out), A: info->rd_gen,
1166 B: info->rd_in, C: info->rd_kill);
1167}
1168
1169/* Calculate the rd_* sets for each block. */
1170
1171void
1172early_remat::compute_rd (void)
1173{
1174 /* First calculate the rd_kill and rd_gen sets, using the fact
1175 that m_candidates is sorted in order of decreasing LUID. */
1176 unsigned int cand_index;
1177 remat_candidate *cand;
1178 FOR_EACH_VEC_ELT_REVERSE (m_candidates, cand_index, cand)
1179 {
1180 rtx_insn *insn = cand->insn;
1181 basic_block bb = BLOCK_FOR_INSN (insn);
1182 remat_block_info *info = &m_block_info[bb->index];
1183 bitmap kill = m_regno_to_candidates[cand->regno];
1184 bitmap_ior_into (get_bitmap (ptr: &info->rd_kill), kill);
1185 if (bitmap_bit_p (DF_LR_OUT (bb), cand->regno))
1186 {
1187 bitmap_and_compl_into (get_bitmap (ptr: &info->rd_gen), kill);
1188 bitmap_set_bit (info->rd_gen, cand_index);
1189 }
1190 }
1191
1192 /* Set up the initial values of the other sets. */
1193 basic_block bb;
1194 FOR_EACH_BB_FN (bb, m_fn)
1195 {
1196 remat_block_info *info = &m_block_info[bb->index];
1197 unsigned int regno;
1198 bitmap_iterator bi;
1199 EXECUTE_IF_AND_IN_BITMAP (DF_LR_IN (bb), &m_candidate_regnos,
1200 0, regno, bi)
1201 {
1202 /* Use available_in to record the set of candidates whose
1203 registers are live on entry (i.e. a maximum bound on rd_in). */
1204 bitmap_ior_into (get_bitmap (ptr: &info->available_in),
1205 m_regno_to_candidates[regno]);
1206
1207 /* Add registers that die in a block to the block's kill set,
1208 so that we don't needlessly propagate them through the rest
1209 of the function. */
1210 if (!bitmap_bit_p (DF_LR_OUT (bb), regno))
1211 bitmap_ior_into (get_bitmap (ptr: &info->rd_kill),
1212 m_regno_to_candidates[regno]);
1213 }
1214
1215 /* Initialize each block's rd_out to the minimal set (the set of
1216 local definitions). */
1217 if (!empty_p (b: info->rd_gen))
1218 bitmap_copy (get_bitmap (ptr: &info->rd_out), info->rd_gen);
1219 }
1220
1221 /* Iterate until we reach a fixed point. */
1222 er = this;
1223 bitmap_clear (&m_tmp_bitmap);
1224 bitmap_set_range (&m_tmp_bitmap, 0, last_basic_block_for_fn (m_fn));
1225 df_simple_dataflow (DF_FORWARD, NULL, NULL, rd_confluence_n, rd_transfer,
1226 &m_tmp_bitmap, df_get_postorder (DF_FORWARD),
1227 df_get_n_blocks (DF_FORWARD));
1228 er = 0;
1229
1230 /* Work out which definitions reach which candidates, again taking
1231 advantage of the candidate order. */
1232 bitmap_head reaching;
1233 bitmap_initialize (head: &reaching, obstack: &m_obstack);
1234 basic_block old_bb = NULL;
1235 FOR_EACH_VEC_ELT_REVERSE (m_candidates, cand_index, cand)
1236 {
1237 bb = BLOCK_FOR_INSN (insn: cand->insn);
1238 if (bb != old_bb)
1239 {
1240 /* Get the definitions that reach the start of the new block. */
1241 remat_block_info *info = &m_block_info[bb->index];
1242 if (info->rd_in)
1243 bitmap_copy (&reaching, info->rd_in);
1244 else
1245 bitmap_clear (&reaching);
1246 old_bb = bb;
1247 }
1248 else
1249 {
1250 /* Process the definitions of the previous instruction. */
1251 bitmap kill = m_regno_to_candidates[cand[1].regno];
1252 bitmap_and_compl_into (&reaching, kill);
1253 bitmap_set_bit (&reaching, cand_index + 1);
1254 }
1255
1256 if (cand->can_copy_p && !cand->constant_p)
1257 {
1258 df_ref ref;
1259 FOR_EACH_INSN_USE (ref, cand->insn)
1260 {
1261 unsigned int regno = DF_REF_REGNO (ref);
1262 if (bitmap_bit_p (&m_candidate_regnos, regno))
1263 {
1264 bitmap defs = m_regno_to_candidates[regno];
1265 bitmap_and (&m_tmp_bitmap, defs, &reaching);
1266 bitmap_ior_into (get_bitmap (ptr: &cand->uses), &m_tmp_bitmap);
1267 }
1268 }
1269 }
1270 }
1271 bitmap_clear (&reaching);
1272}
1273
1274/* If CAND_INDEX is in an equivalence class, return the representative
1275 of the class, otherwise return CAND_INDEX. */
1276
1277inline unsigned int
1278early_remat::canon_candidate (unsigned int cand_index)
1279{
1280 if (remat_equiv_class *ec = m_candidates[cand_index].equiv_class)
1281 return ec->representative;
1282 return cand_index;
1283}
1284
1285/* Make candidate set *PTR refer to candidates using the representative
1286 of each equivalence class. */
1287
1288void
1289early_remat::canon_bitmap (bitmap *ptr)
1290{
1291 bitmap old_set = *ptr;
1292 if (empty_p (b: old_set))
1293 return;
1294
1295 bitmap new_set = NULL;
1296 unsigned int old_index;
1297 bitmap_iterator bi;
1298 EXECUTE_IF_SET_IN_BITMAP (old_set, 0, old_index, bi)
1299 {
1300 unsigned int new_index = canon_candidate (cand_index: old_index);
1301 if (old_index != new_index)
1302 {
1303 if (!new_set)
1304 {
1305 new_set = alloc_bitmap ();
1306 bitmap_copy (new_set, old_set);
1307 }
1308 bitmap_clear_bit (new_set, old_index);
1309 bitmap_set_bit (new_set, new_index);
1310 }
1311 }
1312 if (new_set)
1313 {
1314 BITMAP_FREE (*ptr);
1315 *ptr = new_set;
1316 }
1317}
1318
1319/* If the candidates in REACHING all have the same value, return the
1320 earliest instance of that value (i.e. the first one to be added
1321 to m_value_table), otherwise return MULTIPLE_CANDIDATES. */
1322
1323unsigned int
1324early_remat::resolve_reaching_def (bitmap reaching)
1325{
1326 unsigned int cand_index = bitmap_first_set_bit (reaching);
1327 if (remat_equiv_class *ec = m_candidates[cand_index].equiv_class)
1328 {
1329 if (!bitmap_intersect_compl_p (reaching, ec->members))
1330 return ec->earliest;
1331 }
1332 else if (bitmap_single_bit_set_p (reaching))
1333 return cand_index;
1334
1335 return MULTIPLE_CANDIDATES;
1336}
1337
1338/* Check whether all candidate registers used by candidate CAND_INDEX have
1339 unique definitions. Return true if so, replacing the candidate's uses
1340 set with the appropriate form for value numbering. */
1341
1342bool
1343early_remat::check_candidate_uses (unsigned int cand_index)
1344{
1345 remat_candidate *cand = &m_candidates[cand_index];
1346
1347 /* Process the uses for each register in turn. */
1348 bitmap_head uses;
1349 bitmap_initialize (head: &uses, obstack: &m_obstack);
1350 bitmap_copy (&uses, cand->uses);
1351 bitmap uses_ec = alloc_bitmap ();
1352 while (!bitmap_empty_p (map: &uses))
1353 {
1354 /* Get the register for the lowest-indexed candidate remaining,
1355 and the reaching definitions of that register. */
1356 unsigned int first = bitmap_first_set_bit (&uses);
1357 unsigned int regno = m_candidates[first].regno;
1358 bitmap_and (&m_tmp_bitmap, &uses, m_regno_to_candidates[regno]);
1359
1360 /* See whether all reaching definitions have the same value and if
1361 so get the index of the first candidate we saw with that value. */
1362 unsigned int def = resolve_reaching_def (reaching: &m_tmp_bitmap);
1363 if (def == MULTIPLE_CANDIDATES)
1364 {
1365 if (dump_file)
1366 fprintf (stream: dump_file, format: ";; Removing candidate %d because there is"
1367 " more than one reaching definition of reg %d\n",
1368 cand_index, regno);
1369 cand->can_copy_p = false;
1370 break;
1371 }
1372 bitmap_set_bit (uses_ec, def);
1373 bitmap_and_compl_into (&uses, &m_tmp_bitmap);
1374 }
1375 BITMAP_FREE (cand->uses);
1376 cand->uses = uses_ec;
1377 return cand->can_copy_p;
1378}
1379
1380/* Calculate the set of hard registers that would be clobbered by
1381 rematerializing candidate CAND_INDEX. At this point the candidate's
1382 set of uses is final. */
1383
1384void
1385early_remat::compute_clobbers (unsigned int cand_index)
1386{
1387 remat_candidate *cand = &m_candidates[cand_index];
1388 if (cand->uses)
1389 {
1390 unsigned int use_index;
1391 bitmap_iterator bi;
1392 EXECUTE_IF_SET_IN_BITMAP (cand->uses, 0, use_index, bi)
1393 if (bitmap clobbers = m_candidates[use_index].clobbers)
1394 bitmap_ior_into (get_bitmap (ptr: &cand->clobbers), clobbers);
1395 }
1396
1397 df_ref ref;
1398 FOR_EACH_INSN_DEF (ref, cand->insn)
1399 {
1400 unsigned int def_regno = DF_REF_REGNO (ref);
1401 if (def_regno != cand->regno)
1402 bitmap_set_bit (get_bitmap (ptr: &cand->clobbers), def_regno);
1403 }
1404}
1405
1406/* Mark candidate CAND_INDEX as validated and add it to the value table. */
1407
1408void
1409early_remat::assign_value_number (unsigned int cand_index)
1410{
1411 remat_candidate *cand = &m_candidates[cand_index];
1412 gcc_checking_assert (cand->can_copy_p && !cand->validated_p);
1413
1414 compute_clobbers (cand_index);
1415 cand->validated_p = true;
1416
1417 inchash::hash h;
1418 h.add_int (v: cand->regno);
1419 inchash::add_rtx (cand->remat_rtx, h);
1420 cand->hash = h.end ();
1421
1422 remat_candidate **slot
1423 = m_value_table.find_slot_with_hash (comparable: cand, hash: cand->hash, insert: INSERT);
1424 if (!*slot)
1425 {
1426 *slot = cand;
1427 if (dump_file)
1428 fprintf (stream: dump_file, format: ";; Candidate %d is not equivalent to"
1429 " others seen so far\n", cand_index);
1430 }
1431 else
1432 record_equiv_candidates (cand1_index: *slot - m_candidates.address (), cand2_index: cand_index);
1433}
1434
1435/* Make a final decision about which candidates are valid and assign
1436 value numbers to those that are. */
1437
1438void
1439early_remat::decide_candidate_validity (void)
1440{
1441 auto_vec<unsigned int, 16> stack;
1442 unsigned int cand1_index;
1443 remat_candidate *cand1;
1444 FOR_EACH_VEC_ELT_REVERSE (m_candidates, cand1_index, cand1)
1445 {
1446 if (!cand1->can_copy_p || cand1->validated_p)
1447 continue;
1448
1449 if (empty_p (b: cand1->uses))
1450 {
1451 assign_value_number (cand_index: cand1_index);
1452 continue;
1453 }
1454
1455 stack.safe_push (obj: cand1_index);
1456 while (!stack.is_empty ())
1457 {
1458 unsigned int cand2_index = stack.last ();
1459 unsigned int watermark = stack.length ();
1460 remat_candidate *cand2 = &m_candidates[cand2_index];
1461 if (!cand2->can_copy_p || cand2->validated_p)
1462 {
1463 stack.pop ();
1464 continue;
1465 }
1466 cand2->visited_p = true;
1467 unsigned int cand3_index;
1468 bitmap_iterator bi;
1469 EXECUTE_IF_SET_IN_BITMAP (cand2->uses, 0, cand3_index, bi)
1470 {
1471 remat_candidate *cand3 = &m_candidates[cand3_index];
1472 if (!cand3->can_copy_p)
1473 {
1474 if (dump_file)
1475 fprintf (stream: dump_file, format: ";; Removing candidate %d because"
1476 " it uses removed candidate %d\n", cand2_index,
1477 cand3_index);
1478 cand2->can_copy_p = false;
1479 break;
1480 }
1481 if (!cand3->validated_p)
1482 {
1483 if (empty_p (b: cand3->uses))
1484 assign_value_number (cand_index: cand3_index);
1485 else if (cand3->visited_p)
1486 {
1487 if (dump_file)
1488 fprintf (stream: dump_file, format: ";; Removing candidate %d"
1489 " because its definition is cyclic\n",
1490 cand2_index);
1491 cand2->can_copy_p = false;
1492 break;
1493 }
1494 else
1495 stack.safe_push (obj: cand3_index);
1496 }
1497 }
1498 if (!cand2->can_copy_p)
1499 {
1500 cand2->visited_p = false;
1501 stack.truncate (size: watermark - 1);
1502 }
1503 else if (watermark == stack.length ())
1504 {
1505 cand2->visited_p = false;
1506 if (check_candidate_uses (cand_index: cand2_index))
1507 assign_value_number (cand_index: cand2_index);
1508 stack.pop ();
1509 }
1510 }
1511 }
1512
1513 /* Ensure that the candidates always use the same candidate index
1514 to refer to an equivalence class. */
1515 FOR_EACH_VEC_ELT_REVERSE (m_candidates, cand1_index, cand1)
1516 if (cand1->can_copy_p && !empty_p (b: cand1->uses))
1517 {
1518 canon_bitmap (ptr: &cand1->uses);
1519 gcc_checking_assert (bitmap_first_set_bit (cand1->uses) > cand1_index);
1520 }
1521}
1522
1523/* Remove any candidates in CANDIDATES that would clobber a register in
1524 UNAVAIL_REGS. */
1525
1526void
1527early_remat::restrict_remat_for_unavail_regs (bitmap candidates,
1528 const_bitmap unavail_regs)
1529{
1530 bitmap_clear (&m_tmp_bitmap);
1531 unsigned int cand_index;
1532 bitmap_iterator bi;
1533 EXECUTE_IF_SET_IN_BITMAP (candidates, 0, cand_index, bi)
1534 {
1535 remat_candidate *cand = &m_candidates[cand_index];
1536 if (cand->clobbers
1537 && bitmap_intersect_p (cand->clobbers, unavail_regs))
1538 bitmap_set_bit (&m_tmp_bitmap, cand_index);
1539 }
1540 bitmap_and_compl_into (candidates, &m_tmp_bitmap);
1541}
1542
1543/* Remove any candidates in CANDIDATES that would clobber a register
1544 that is potentially live across CALL. */
1545
1546void
1547early_remat::restrict_remat_for_call (bitmap candidates, rtx_insn *call)
1548{
1549 /* We don't know whether partially-clobbered registers are live
1550 across the call or not, so assume that they are. */
1551 bitmap_view<HARD_REG_SET> call_preserved_regs
1552 (~insn_callee_abi (call).full_reg_clobbers ());
1553 restrict_remat_for_unavail_regs (candidates, unavail_regs: call_preserved_regs);
1554}
1555
1556/* Assuming that every path reaching a point P contains a copy of a
1557 use U of REGNO, return true if another copy of U at P would have
1558 access to the same value of REGNO. */
1559
1560bool
1561early_remat::stable_use_p (unsigned int regno)
1562{
1563 /* Conservatively assume not for hard registers. */
1564 if (HARD_REGISTER_NUM_P (regno))
1565 return false;
1566
1567 /* See if REGNO has a single definition and is never used uninitialized.
1568 In this case the definition of REGNO dominates the common dominator
1569 of the uses U, which in turn dominates P. */
1570 if (DF_REG_DEF_COUNT (regno) == 1
1571 && !bitmap_bit_p (DF_LR_OUT (ENTRY_BLOCK_PTR_FOR_FN (m_fn)), regno))
1572 return true;
1573
1574 return false;
1575}
1576
1577/* Emit a copy from register DEST to register SRC before candidate
1578 CAND_INDEX's instruction. */
1579
1580void
1581early_remat::emit_copy_before (unsigned int cand_index, rtx dest, rtx src)
1582{
1583 remat_candidate *cand = &m_candidates[cand_index];
1584 if (dump_file)
1585 {
1586 fprintf (stream: dump_file, format: ";; Stabilizing insn ");
1587 dump_insn_id (insn: cand->insn);
1588 fprintf (stream: dump_file, format: " by copying source reg %d:%s to temporary reg %d\n",
1589 REGNO (src), GET_MODE_NAME (GET_MODE (src)), REGNO (dest));
1590 }
1591 emit_insn_before (gen_move_insn (dest, src), cand->insn);
1592}
1593
1594/* Check whether any inputs to candidate CAND_INDEX's instruction could
1595 change at rematerialization points and replace them with new pseudo
1596 registers if so. */
1597
1598void
1599early_remat::stabilize_pattern (unsigned int cand_index)
1600{
1601 remat_candidate *cand = &m_candidates[cand_index];
1602 if (cand->stabilized_p)
1603 return;
1604
1605 remat_equiv_class *ec = cand->equiv_class;
1606 gcc_checking_assert (!ec || cand_index == ec->representative);
1607
1608 /* Record the replacements we've made so far, so that we don't
1609 create two separate registers for match_dups. Lookup is O(n),
1610 but the n is very small. */
1611 typedef std::pair<rtx, rtx> reg_pair;
1612 auto_vec<reg_pair, 16> reg_map;
1613
1614 rtx_insn *insn = cand->insn;
1615 df_ref ref;
1616 FOR_EACH_INSN_USE (ref, insn)
1617 {
1618 unsigned int old_regno = DF_REF_REGNO (ref);
1619 rtx *loc = DF_REF_REAL_LOC (ref);
1620
1621 if (HARD_REGISTER_NUM_P (old_regno) && fixed_regs[old_regno])
1622 {
1623 /* We checked when adding the candidate that the value is stable. */
1624 gcc_checking_assert (!rtx_unstable_p (*loc));
1625 continue;
1626 }
1627
1628 if (bitmap_bit_p (&m_candidate_regnos, old_regno))
1629 /* We already know which candidate provides the definition
1630 and will handle it during copying. */
1631 continue;
1632
1633 if (stable_use_p (regno: old_regno))
1634 /* We can continue to use the existing register. */
1635 continue;
1636
1637 /* We need to replace the register. See whether we've already
1638 created a suitable copy. */
1639 rtx old_reg = *loc;
1640 rtx new_reg = NULL_RTX;
1641 machine_mode mode = GET_MODE (old_reg);
1642 reg_pair *p;
1643 unsigned int pi;
1644 FOR_EACH_VEC_ELT (reg_map, pi, p)
1645 if (REGNO (p->first) == old_regno
1646 && GET_MODE (p->first) == mode)
1647 {
1648 new_reg = p->second;
1649 break;
1650 }
1651
1652 if (!new_reg)
1653 {
1654 /* Create a new register and initialize it just before
1655 the instruction. */
1656 new_reg = gen_reg_rtx (mode);
1657 reg_map.safe_push (obj: reg_pair (old_reg, new_reg));
1658 if (ec)
1659 {
1660 unsigned int member_index;
1661 bitmap_iterator bi;
1662 EXECUTE_IF_SET_IN_BITMAP (ec->members, 0, member_index, bi)
1663 emit_copy_before (cand_index: member_index, dest: new_reg, src: old_reg);
1664 }
1665 else
1666 emit_copy_before (cand_index, dest: new_reg, src: old_reg);
1667 }
1668 validate_change (insn, loc, new_reg, true);
1669 }
1670 if (num_changes_pending ())
1671 {
1672 if (!apply_change_group ())
1673 /* We checked when adding the candidates that the pattern allows
1674 hard registers to be replaced. Nothing else should make the
1675 changes invalid. */
1676 gcc_unreachable ();
1677
1678 if (ec)
1679 {
1680 /* Copy the new pattern to other members of the equivalence
1681 class. */
1682 unsigned int member_index;
1683 bitmap_iterator bi;
1684 EXECUTE_IF_SET_IN_BITMAP (ec->members, 0, member_index, bi)
1685 if (cand_index != member_index)
1686 {
1687 rtx_insn *other_insn = m_candidates[member_index].insn;
1688 if (!validate_change (other_insn, &PATTERN (insn: other_insn),
1689 copy_insn (PATTERN (insn)), 0))
1690 /* If the original instruction was valid then the copy
1691 should be too. */
1692 gcc_unreachable ();
1693 }
1694 }
1695 }
1696
1697 cand->stabilized_p = true;
1698}
1699
1700/* Change CAND's instruction so that it sets CAND->copy_regno instead
1701 of CAND->regno. */
1702
1703void
1704early_remat::replace_dest_with_copy (unsigned int cand_index)
1705{
1706 remat_candidate *cand = &m_candidates[cand_index];
1707 df_ref def;
1708 FOR_EACH_INSN_DEF (def, cand->insn)
1709 if (DF_REF_REGNO (def) == cand->regno)
1710 validate_change (cand->insn, DF_REF_REAL_LOC (def),
1711 regno_reg_rtx[cand->copy_regno], 1);
1712}
1713
1714/* Make sure that the candidates used by candidate CAND_INDEX are available.
1715 There are two ways of doing this for an input candidate I:
1716
1717 (1) Using the existing register number and ensuring that I is available.
1718
1719 (2) Using a new register number (recorded in copy_regno) and adding I
1720 to VIA_COPY. This guarantees that making I available does not
1721 conflict with other uses of the original register.
1722
1723 REQUIRED is the set of candidates that are required but not available
1724 before the copy of CAND_INDEX. AVAILABLE is the set of candidates
1725 that are already available before the copy of CAND_INDEX. REACHING
1726 is the set of candidates that reach the copy of CAND_INDEX. VIA_COPY
1727 is the set of candidates that will use new register numbers recorded
1728 in copy_regno instead of the original ones. */
1729
1730void
1731early_remat::stabilize_candidate_uses (unsigned int cand_index,
1732 bitmap required, bitmap available,
1733 bitmap reaching, bitmap via_copy)
1734{
1735 remat_candidate *cand = &m_candidates[cand_index];
1736 df_ref use;
1737 FOR_EACH_INSN_USE (use, cand->insn)
1738 {
1739 unsigned int regno = DF_REF_REGNO (use);
1740 if (!bitmap_bit_p (&m_candidate_regnos, regno))
1741 continue;
1742
1743 /* Work out which candidate provides the definition. */
1744 bitmap defs = m_regno_to_candidates[regno];
1745 bitmap_and (&m_tmp_bitmap, cand->uses, defs);
1746 gcc_checking_assert (bitmap_single_bit_set_p (&m_tmp_bitmap));
1747 unsigned int def_index = bitmap_first_set_bit (&m_tmp_bitmap);
1748
1749 /* First see if DEF_INDEX is the only reaching definition of REGNO
1750 at this point too and if it is or will become available. We can
1751 continue to use REGNO if so. */
1752 bitmap_and (&m_tmp_bitmap, reaching, defs);
1753 if (bitmap_single_bit_set_p (&m_tmp_bitmap)
1754 && bitmap_first_set_bit (&m_tmp_bitmap) == def_index
1755 && ((available && bitmap_bit_p (available, def_index))
1756 || bitmap_bit_p (required, def_index)))
1757 {
1758 if (dump_file)
1759 fprintf (stream: dump_file, format: ";; Keeping reg %d for use of candidate %d"
1760 " in candidate %d\n", regno, def_index, cand_index);
1761 continue;
1762 }
1763
1764 /* Otherwise fall back to using a copy. There are other cases
1765 in which we *could* continue to use REGNO, but there's not
1766 really much point. Using a separate register ought to make
1767 things easier for the register allocator. */
1768 remat_candidate *def_cand = &m_candidates[def_index];
1769 rtx *loc = DF_REF_REAL_LOC (use);
1770 rtx new_reg;
1771 if (bitmap_set_bit (via_copy, def_index))
1772 {
1773 new_reg = gen_reg_rtx (GET_MODE (*loc));
1774 def_cand->copy_regno = REGNO (new_reg);
1775 if (dump_file)
1776 fprintf (stream: dump_file, format: ";; Creating reg %d for use of candidate %d"
1777 " in candidate %d\n", REGNO (new_reg), def_index,
1778 cand_index);
1779 }
1780 else
1781 new_reg = regno_reg_rtx[def_cand->copy_regno];
1782 validate_change (cand->insn, loc, new_reg, 1);
1783 }
1784}
1785
1786/* Rematerialize the candidates in REQUIRED after instruction INSN,
1787 given that the candidates in AVAILABLE are already available
1788 and that REACHING is the set of candidates live after INSN.
1789 REQUIRED and AVAILABLE are disjoint on entry.
1790
1791 Clear REQUIRED on exit. */
1792
1793void
1794early_remat::emit_remat_insns (bitmap required, bitmap available,
1795 bitmap reaching, rtx_insn *insn)
1796{
1797 /* Quick exit if there's nothing to do. */
1798 if (empty_p (b: required))
1799 return;
1800
1801 /* Only reaching definitions should be available or required. */
1802 gcc_checking_assert (!bitmap_intersect_compl_p (required, reaching));
1803 if (available)
1804 gcc_checking_assert (!bitmap_intersect_compl_p (available, reaching));
1805
1806 bitmap_head via_copy;
1807 bitmap_initialize (head: &via_copy, obstack: &m_obstack);
1808 while (!bitmap_empty_p (map: required) || !bitmap_empty_p (map: &via_copy))
1809 {
1810 /* Pick the lowest-indexed candidate left. */
1811 unsigned int required_index = (bitmap_empty_p (map: required)
1812 ? ~0U : bitmap_first_set_bit (required));
1813 unsigned int via_copy_index = (bitmap_empty_p (map: &via_copy)
1814 ? ~0U : bitmap_first_set_bit (&via_copy));
1815 unsigned int cand_index = MIN (required_index, via_copy_index);
1816 remat_candidate *cand = &m_candidates[cand_index];
1817
1818 bool via_copy_p = (cand_index == via_copy_index);
1819 if (via_copy_p)
1820 bitmap_clear_bit (&via_copy, cand_index);
1821 else
1822 {
1823 /* Remove all candidates for the same register from REQUIRED. */
1824 bitmap_and (&m_tmp_bitmap, reaching,
1825 m_regno_to_candidates[cand->regno]);
1826 bitmap_and_compl_into (required, &m_tmp_bitmap);
1827 gcc_checking_assert (!bitmap_bit_p (required, cand_index));
1828
1829 /* Only rematerialize if we have a single reaching definition
1830 of the register. */
1831 if (!bitmap_single_bit_set_p (&m_tmp_bitmap))
1832 {
1833 if (dump_file)
1834 {
1835 fprintf (stream: dump_file, format: ";; Can't rematerialize reg %d after ",
1836 cand->regno);
1837 dump_insn_id (insn);
1838 fprintf (stream: dump_file, format: ": more than one reaching definition\n");
1839 }
1840 continue;
1841 }
1842
1843 /* Skip candidates that can't be rematerialized. */
1844 if (!cand->can_copy_p)
1845 continue;
1846
1847 /* Check the function precondition. */
1848 gcc_checking_assert (!available
1849 || !bitmap_bit_p (available, cand_index));
1850 }
1851
1852 /* Invalid candidates should have been weeded out by now. */
1853 gcc_assert (cand->can_copy_p);
1854
1855 rtx new_pattern;
1856 if (cand->constant_p)
1857 {
1858 /* Emit a simple move. */
1859 unsigned int regno = via_copy_p ? cand->copy_regno : cand->regno;
1860 new_pattern = gen_move_insn (regno_reg_rtx[regno], cand->remat_rtx);
1861 }
1862 else
1863 {
1864 /* If this is the first time we've copied the instruction, make
1865 sure that any inputs will have the same value after INSN. */
1866 stabilize_pattern (cand_index);
1867
1868 /* Temporarily adjust the original instruction so that it has
1869 the right form for the copy. */
1870 if (via_copy_p)
1871 replace_dest_with_copy (cand_index);
1872 if (cand->uses)
1873 stabilize_candidate_uses (cand_index, required, available,
1874 reaching, via_copy: &via_copy);
1875
1876 /* Get the new instruction pattern. */
1877 new_pattern = copy_insn (cand->remat_rtx);
1878
1879 /* Undo the temporary changes. */
1880 cancel_changes (0);
1881 }
1882
1883 /* Emit the new instruction. */
1884 rtx_insn *new_insn = emit_insn_after (new_pattern, insn);
1885
1886 if (dump_file)
1887 {
1888 fprintf (stream: dump_file, format: ";; Rematerializing candidate %d after ",
1889 cand_index);
1890 dump_insn_id (insn);
1891 if (via_copy_p)
1892 fprintf (stream: dump_file, format: " with new destination reg %d",
1893 cand->copy_regno);
1894 fprintf (stream: dump_file, format: ":\n\n");
1895 print_rtl_single (dump_file, new_insn);
1896 fprintf (stream: dump_file, format: "\n");
1897 }
1898 }
1899}
1900
1901/* Recompute INFO's available_out set, given that it's distinct from
1902 available_in and available_locally. */
1903
1904bool
1905early_remat::set_available_out (remat_block_info *info)
1906{
1907 if (empty_p (b: info->available_locally))
1908 return bitmap_and_compl (get_bitmap (ptr: &info->available_out),
1909 info->available_in, info->rd_kill);
1910
1911 if (empty_p (b: info->rd_kill))
1912 return bitmap_ior (get_bitmap (ptr: &info->available_out),
1913 info->available_locally, info->available_in);
1914
1915 return bitmap_ior_and_compl (DST: get_bitmap (ptr: &info->available_out),
1916 A: info->available_locally, B: info->available_in,
1917 C: info->rd_kill);
1918}
1919
1920/* If BB has more than one call, decide which candidates should be
1921 rematerialized after the non-final calls and emit the associated
1922 instructions. Record other information about the block in preparation
1923 for the global phase. */
1924
1925void
1926early_remat::process_block (basic_block bb)
1927{
1928 remat_block_info *info = &m_block_info[bb->index];
1929 rtx_insn *last_call = NULL;
1930 rtx_insn *insn;
1931
1932 /* Ensure that we always use the same candidate index to refer to an
1933 equivalence class. */
1934 if (info->rd_out == info->rd_in)
1935 {
1936 canon_bitmap (ptr: &info->rd_in);
1937 info->rd_out = info->rd_in;
1938 }
1939 else
1940 {
1941 canon_bitmap (ptr: &info->rd_in);
1942 canon_bitmap (ptr: &info->rd_out);
1943 }
1944 canon_bitmap (ptr: &info->rd_kill);
1945 canon_bitmap (ptr: &info->rd_gen);
1946
1947 /* The set of candidates that should be rematerialized on entry to the
1948 block or after the previous call (whichever is more recent). */
1949 init_temp_bitmap (ptr: &m_required);
1950
1951 /* The set of candidates that reach the current instruction (i.e. are
1952 live just before the instruction). */
1953 bitmap_head reaching;
1954 bitmap_initialize (head: &reaching, obstack: &m_obstack);
1955 if (info->rd_in)
1956 bitmap_copy (&reaching, info->rd_in);
1957
1958 /* The set of candidates that are live and available without
1959 rematerialization just before the current instruction. This only
1960 accounts for earlier candidates in the block, or those that become
1961 available by being added to M_REQUIRED. */
1962 init_temp_bitmap (ptr: &m_available);
1963
1964 /* Get the range of candidates in the block. */
1965 unsigned int next_candidate = info->first_candidate;
1966 unsigned int num_candidates = info->num_candidates;
1967 remat_candidate *next_def = (num_candidates > 0
1968 ? &m_candidates[next_candidate]
1969 : NULL);
1970
1971 FOR_BB_INSNS (bb, insn)
1972 {
1973 if (!NONDEBUG_INSN_P (insn))
1974 continue;
1975
1976 /* First process uses, since this is a forward walk. */
1977 df_ref ref;
1978 FOR_EACH_INSN_USE (ref, insn)
1979 {
1980 unsigned int regno = DF_REF_REGNO (ref);
1981 if (bitmap_bit_p (&m_candidate_regnos, regno))
1982 {
1983 bitmap defs = m_regno_to_candidates[regno];
1984 bitmap_and (&m_tmp_bitmap, defs, &reaching);
1985 gcc_checking_assert (!bitmap_empty_p (&m_tmp_bitmap));
1986 if (!bitmap_intersect_p (defs, m_available))
1987 {
1988 /* There has been no definition of the register since
1989 the last call or the start of the block (whichever
1990 is most recent). Mark the reaching definitions
1991 as required at that point and thus available here. */
1992 bitmap_ior_into (m_required, &m_tmp_bitmap);
1993 bitmap_ior_into (m_available, &m_tmp_bitmap);
1994 }
1995 }
1996 }
1997
1998 if (CALL_P (insn))
1999 {
2000 if (!last_call)
2001 {
2002 /* The first call in the block. Record which candidates are
2003 required at the start of the block. */
2004 copy_temp_bitmap (dest: &info->required_in, src: &m_required);
2005 init_temp_bitmap (ptr: &m_required);
2006 }
2007 else
2008 {
2009 /* The fully-local case: candidates that need to be
2010 rematerialized after a previous call in the block. */
2011 restrict_remat_for_call (candidates: m_required, call: last_call);
2012 emit_remat_insns (required: m_required, NULL, reaching: info->rd_after_call,
2013 insn: last_call);
2014 }
2015 last_call = insn;
2016 bitmap_clear (m_available);
2017 gcc_checking_assert (empty_p (m_required));
2018 }
2019
2020 /* Now process definitions. */
2021 while (next_def && insn == next_def->insn)
2022 {
2023 unsigned int gen = canon_candidate (cand_index: next_candidate);
2024
2025 /* Other candidates with the same regno are not available
2026 any more. */
2027 bitmap kill = m_regno_to_candidates[next_def->regno];
2028 bitmap_and_compl_into (m_available, kill);
2029 bitmap_and_compl_into (&reaching, kill);
2030
2031 /* Record that this candidate is available without
2032 rematerialization. */
2033 bitmap_set_bit (m_available, gen);
2034 bitmap_set_bit (&reaching, gen);
2035
2036 /* Find the next candidate in the block. */
2037 num_candidates -= 1;
2038 next_candidate -= 1;
2039 if (num_candidates > 0)
2040 next_def -= 1;
2041 else
2042 next_def = NULL;
2043 }
2044
2045 if (insn == last_call)
2046 bitmap_copy (get_bitmap (ptr: &info->rd_after_call), &reaching);
2047 }
2048 bitmap_clear (&reaching);
2049 gcc_checking_assert (num_candidates == 0);
2050
2051 /* Remove values from the available set if they aren't live (and so
2052 aren't interesting to successor blocks). */
2053 if (info->rd_out)
2054 bitmap_and_into (m_available, info->rd_out);
2055
2056 /* Record the accumulated information. */
2057 info->last_call = last_call;
2058 info->abnormal_call_p = (last_call
2059 && last_call == BB_END (bb)
2060 && has_abnormal_or_eh_outgoing_edge_p (bb));
2061 copy_temp_bitmap (dest: &info->available_locally, src: &m_available);
2062 if (last_call)
2063 copy_temp_bitmap (dest: &info->required_after_call, src: &m_required);
2064 else
2065 copy_temp_bitmap (dest: &info->required_in, src: &m_required);
2066
2067 /* Assume at first that all live-in values are available without
2068 rematerialization (i.e. start with the most optimistic assumption). */
2069 if (info->available_in)
2070 {
2071 if (info->rd_in)
2072 bitmap_copy (info->available_in, info->rd_in);
2073 else
2074 BITMAP_FREE (info->available_in);
2075 }
2076
2077 if (last_call || empty_p (b: info->available_in))
2078 /* The values available on exit from the block are exactly those that
2079 are available locally. This set doesn't change. */
2080 info->available_out = info->available_locally;
2081 else if (empty_p (b: info->available_locally) && empty_p (b: info->rd_kill))
2082 /* The values available on exit are the same as those available on entry.
2083 Updating one updates the other. */
2084 info->available_out = info->available_in;
2085 else
2086 set_available_out (info);
2087}
2088
2089/* Process each block as for process_block, visiting dominators before
2090 the blocks they dominate. */
2091
2092void
2093early_remat::local_phase (void)
2094{
2095 if (dump_file)
2096 fprintf (stream: dump_file, format: "\n;; Local phase:\n");
2097
2098 int *rpo = df_get_postorder (DF_FORWARD);
2099 unsigned int rpo_len = df_get_n_blocks (DF_FORWARD);
2100 for (unsigned int i = 0; i < rpo_len; ++i)
2101 if (rpo[i] >= NUM_FIXED_BLOCKS)
2102 process_block (BASIC_BLOCK_FOR_FN (m_fn, rpo[i]));
2103}
2104
2105/* Return true if available values survive across edge E. */
2106
2107static inline bool
2108available_across_edge_p (edge e)
2109{
2110 return (e->flags & EDGE_EH) == 0;
2111}
2112
2113/* Propagate information from the available_out set of E->src to the
2114 available_in set of E->dest, when computing global availability.
2115 Return true if something changed. */
2116
2117bool
2118early_remat::avail_confluence_n (edge e)
2119{
2120 remat_block_info *src = &er->m_block_info[e->src->index];
2121 remat_block_info *dest = &er->m_block_info[e->dest->index];
2122
2123 if (!available_across_edge_p (e))
2124 return false;
2125
2126 if (empty_p (b: dest->available_in))
2127 return false;
2128
2129 if (!src->available_out)
2130 {
2131 bitmap_clear (dest->available_in);
2132 return true;
2133 }
2134
2135 return bitmap_and_into (dest->available_in, src->available_out);
2136}
2137
2138/* Propagate information from the available_in set of block BB_INDEX
2139 to available_out. Return true if something changed. */
2140
2141bool
2142early_remat::avail_transfer (int bb_index)
2143{
2144 remat_block_info *info = &er->m_block_info[bb_index];
2145
2146 if (info->available_out == info->available_locally)
2147 return false;
2148
2149 if (info->available_out == info->available_in)
2150 /* Assume that we are only called if the input changed. */
2151 return true;
2152
2153 return er->set_available_out (info);
2154}
2155
2156/* Compute global availability for the function, starting with the local
2157 information computed by local_phase. */
2158
2159void
2160early_remat::compute_availability (void)
2161{
2162 /* We use df_simple_dataflow instead of the lcm routines for three reasons:
2163
2164 (1) it avoids recomputing the traversal order;
2165 (2) many of the sets are likely to be sparse, so we don't necessarily
2166 want to use sbitmaps; and
2167 (3) it means we can avoid creating an explicit kill set for the call. */
2168 er = this;
2169 bitmap_clear (&m_tmp_bitmap);
2170 bitmap_set_range (&m_tmp_bitmap, 0, last_basic_block_for_fn (m_fn));
2171 df_simple_dataflow (DF_FORWARD, NULL, NULL,
2172 avail_confluence_n, avail_transfer,
2173 &m_tmp_bitmap, df_get_postorder (DF_FORWARD),
2174 df_get_n_blocks (DF_FORWARD));
2175 er = 0;
2176
2177 /* Restrict the required_in sets to values that aren't available. */
2178 basic_block bb;
2179 FOR_EACH_BB_FN (bb, m_fn)
2180 {
2181 remat_block_info *info = &m_block_info[bb->index];
2182 if (info->required_in && info->available_in)
2183 bitmap_and_compl_into (info->required_in, info->available_in);
2184 }
2185}
2186
2187/* Make sure that INFO's available_out and available_in sets are unique. */
2188
2189inline void
2190early_remat::unshare_available_sets (remat_block_info *info)
2191{
2192 if (info->available_in && info->available_in == info->available_out)
2193 {
2194 info->available_in = alloc_bitmap ();
2195 bitmap_copy (info->available_in, info->available_out);
2196 }
2197}
2198
2199/* Return true if it is possible to move rematerializations from the
2200 destination of E to the source of E. */
2201
2202inline bool
2203early_remat::can_move_across_edge_p (edge e)
2204{
2205 return (available_across_edge_p (e)
2206 && !m_block_info[e->src->index].abnormal_call_p);
2207}
2208
2209/* Return true if it is cheaper to rematerialize values at the head of
2210 block QUERY_BB_INDEX instead of rematerializing in its predecessors. */
2211
2212bool
2213early_remat::local_remat_cheaper_p (unsigned int query_bb_index)
2214{
2215 if (m_block_info[query_bb_index].remat_frequency_valid_p)
2216 return m_block_info[query_bb_index].local_remat_cheaper_p;
2217
2218 /* Iteratively compute the cost of rematerializing values in the
2219 predecessor blocks, then compare that with the cost of
2220 rematerializing at the head of the block.
2221
2222 A cycle indicates that there is no call on that execution path,
2223 so it isn't necessary to rematerialize on that path. */
2224 auto_vec<basic_block, 16> stack;
2225 stack.quick_push (BASIC_BLOCK_FOR_FN (m_fn, query_bb_index));
2226 while (!stack.is_empty ())
2227 {
2228 basic_block bb = stack.last ();
2229 remat_block_info *info = &m_block_info[bb->index];
2230 if (info->remat_frequency_valid_p)
2231 {
2232 stack.pop ();
2233 continue;
2234 }
2235
2236 info->visited_p = true;
2237 int frequency = 0;
2238 bool can_move_p = true;
2239 edge e;
2240 edge_iterator ei;
2241 FOR_EACH_EDGE (e, ei, bb->preds)
2242 if (!can_move_across_edge_p (e))
2243 {
2244 can_move_p = false;
2245 break;
2246 }
2247 else if (m_block_info[e->src->index].last_call)
2248 /* We'll rematerialize after the call. */
2249 frequency += e->src->count.to_frequency (fun: m_fn);
2250 else if (m_block_info[e->src->index].remat_frequency_valid_p)
2251 /* Add the cost of rematerializing at the head of E->src
2252 or in its predecessors (whichever is cheaper). */
2253 frequency += m_block_info[e->src->index].remat_frequency;
2254 else if (!m_block_info[e->src->index].visited_p)
2255 /* Queue E->src and then revisit this block again. */
2256 stack.safe_push (obj: e->src);
2257
2258 /* Come back to this block later if we need to process some of
2259 its predecessors. */
2260 if (stack.last () != bb)
2261 continue;
2262
2263 /* If rematerializing in and before the block have equal cost, prefer
2264 rematerializing in the block. This should shorten the live range. */
2265 int bb_frequency = bb->count.to_frequency (fun: m_fn);
2266 if (!can_move_p || frequency >= bb_frequency)
2267 {
2268 info->local_remat_cheaper_p = true;
2269 info->remat_frequency = bb_frequency;
2270 }
2271 else
2272 info->remat_frequency = frequency;
2273 info->remat_frequency_valid_p = true;
2274 info->visited_p = false;
2275 if (dump_file)
2276 {
2277 if (!can_move_p)
2278 fprintf (stream: dump_file, format: ";; Need to rematerialize at the head of"
2279 " block %d; cannot move to predecessors.\n", bb->index);
2280 else
2281 {
2282 fprintf (stream: dump_file, format: ";; Block %d has frequency %d,"
2283 " rematerializing in predecessors has frequency %d",
2284 bb->index, bb_frequency, frequency);
2285 if (info->local_remat_cheaper_p)
2286 fprintf (stream: dump_file, format: "; prefer to rematerialize"
2287 " in the block\n");
2288 else
2289 fprintf (stream: dump_file, format: "; prefer to rematerialize"
2290 " in predecessors\n");
2291 }
2292 }
2293 stack.pop ();
2294 }
2295 return m_block_info[query_bb_index].local_remat_cheaper_p;
2296}
2297
2298/* Return true if we cannot rematerialize candidate CAND_INDEX at the head of
2299 block BB_INDEX. */
2300
2301bool
2302early_remat::need_to_move_candidate_p (unsigned int bb_index,
2303 unsigned int cand_index)
2304{
2305 remat_block_info *info = &m_block_info[bb_index];
2306 remat_candidate *cand = &m_candidates[cand_index];
2307 basic_block bb = BASIC_BLOCK_FOR_FN (m_fn, bb_index);
2308
2309 /* If there is more than one reaching definition of REGNO,
2310 we'll need to rematerialize in predecessors instead. */
2311 bitmap_and (&m_tmp_bitmap, info->rd_in, m_regno_to_candidates[cand->regno]);
2312 if (!bitmap_single_bit_set_p (&m_tmp_bitmap))
2313 {
2314 if (dump_file)
2315 fprintf (stream: dump_file, format: ";; Cannot rematerialize %d at the"
2316 " head of block %d because there is more than one"
2317 " reaching definition of reg %d\n", cand_index,
2318 bb_index, cand->regno);
2319 return true;
2320 }
2321
2322 /* Likewise if rematerializing CAND here would clobber a live register. */
2323 if (cand->clobbers
2324 && bitmap_intersect_p (cand->clobbers, DF_LR_IN (bb)))
2325 {
2326 if (dump_file)
2327 fprintf (stream: dump_file, format: ";; Cannot rematerialize %d at the"
2328 " head of block %d because it would clobber live"
2329 " registers\n", cand_index, bb_index);
2330 return true;
2331 }
2332
2333 return false;
2334}
2335
2336/* Set REQUIRED to the minimum set of candidates that must be rematerialized
2337 in predecessors of block BB_INDEX instead of at the start of the block. */
2338
2339void
2340early_remat::compute_minimum_move_set (unsigned int bb_index,
2341 bitmap required)
2342{
2343 remat_block_info *info = &m_block_info[bb_index];
2344 bitmap_head remaining;
2345
2346 bitmap_clear (required);
2347 bitmap_initialize (head: &remaining, obstack: &m_obstack);
2348 bitmap_copy (&remaining, info->required_in);
2349 while (!bitmap_empty_p (map: &remaining))
2350 {
2351 unsigned int cand_index = bitmap_first_set_bit (&remaining);
2352 remat_candidate *cand = &m_candidates[cand_index];
2353 bitmap_clear_bit (&remaining, cand_index);
2354
2355 /* Leave invalid candidates where they are. */
2356 if (!cand->can_copy_p)
2357 continue;
2358
2359 /* Decide whether to move this candidate. */
2360 if (!bitmap_bit_p (required, cand_index))
2361 {
2362 if (!need_to_move_candidate_p (bb_index, cand_index))
2363 continue;
2364 bitmap_set_bit (required, cand_index);
2365 }
2366
2367 /* Also move values used by the candidate, so that we don't
2368 rematerialize them twice. */
2369 if (cand->uses)
2370 {
2371 bitmap_ior_and_into (DST: required, B: cand->uses, C: info->required_in);
2372 bitmap_ior_and_into (DST: &remaining, B: cand->uses, C: info->required_in);
2373 }
2374 }
2375}
2376
2377/* Make the predecessors of BB_INDEX rematerialize the candidates in
2378 REQUIRED. Add any blocks whose required_in set changes to
2379 PENDING_BLOCKS. */
2380
2381void
2382early_remat::move_to_predecessors (unsigned int bb_index, bitmap required,
2383 bitmap pending_blocks)
2384{
2385 if (empty_p (b: required))
2386 return;
2387 remat_block_info *dest_info = &m_block_info[bb_index];
2388 basic_block bb = BASIC_BLOCK_FOR_FN (m_fn, bb_index);
2389 edge e;
2390 edge_iterator ei;
2391 FOR_EACH_EDGE (e, ei, bb->preds)
2392 {
2393 remat_block_info *src_info = &m_block_info[e->src->index];
2394
2395 /* Restrict the set we add to the reaching definitions. */
2396 bitmap_and (&m_tmp_bitmap, required, src_info->rd_out);
2397 if (bitmap_empty_p (map: &m_tmp_bitmap))
2398 continue;
2399
2400 if (!can_move_across_edge_p (e))
2401 {
2402 /* We can't move the rematerialization and we can't do it at
2403 the start of the block either. In this case we just give up
2404 and rely on spilling to make the values available across E. */
2405 if (dump_file)
2406 {
2407 fprintf (stream: dump_file, format: ";; Cannot rematerialize the following"
2408 " candidates in block %d:", e->src->index);
2409 dump_candidate_bitmap (candidates: required);
2410 fprintf (stream: dump_file, format: "\n");
2411 }
2412 continue;
2413 }
2414
2415 /* Remove candidates that are already available. */
2416 if (src_info->available_out)
2417 {
2418 bitmap_and_compl_into (&m_tmp_bitmap, src_info->available_out);
2419 if (bitmap_empty_p (map: &m_tmp_bitmap))
2420 continue;
2421 }
2422
2423 /* Add the remaining candidates to the appropriate required set. */
2424 if (dump_file)
2425 {
2426 fprintf (stream: dump_file, format: ";; Moving this set from block %d"
2427 " to block %d:", bb_index, e->src->index);
2428 dump_candidate_bitmap (candidates: &m_tmp_bitmap);
2429 fprintf (stream: dump_file, format: "\n");
2430 }
2431 /* If the source block contains a call, we want to rematerialize
2432 after the call, otherwise we want to rematerialize at the start
2433 of the block. */
2434 bitmap src_required = get_bitmap (ptr: src_info->last_call
2435 ? &src_info->required_after_call
2436 : &src_info->required_in);
2437 if (bitmap_ior_into (src_required, &m_tmp_bitmap))
2438 {
2439 if (!src_info->last_call)
2440 bitmap_set_bit (pending_blocks, e->src->index);
2441 unshare_available_sets (info: src_info);
2442 bitmap_ior_into (get_bitmap (ptr: &src_info->available_out),
2443 &m_tmp_bitmap);
2444 }
2445 }
2446
2447 /* The candidates are now available on entry to the block. */
2448 bitmap_and_compl_into (dest_info->required_in, required);
2449 unshare_available_sets (info: dest_info);
2450 bitmap_ior_into (get_bitmap (ptr: &dest_info->available_in), required);
2451}
2452
2453/* Go through the candidates that are currently marked as being
2454 rematerialized at the beginning of a block. Decide in each case
2455 whether that's valid and profitable; if it isn't, move the
2456 rematerialization to predecessor blocks instead. */
2457
2458void
2459early_remat::choose_rematerialization_points (void)
2460{
2461 bitmap_head required;
2462 bitmap_head pending_blocks;
2463
2464 int *postorder = df_get_postorder (DF_BACKWARD);
2465 unsigned int postorder_len = df_get_n_blocks (DF_BACKWARD);
2466 bitmap_initialize (head: &required, obstack: &m_obstack);
2467 bitmap_initialize (head: &pending_blocks, obstack: &m_obstack);
2468 do
2469 /* Process the blocks in postorder, to reduce the number of iterations
2470 of the outer loop. */
2471 for (unsigned int i = 0; i < postorder_len; ++i)
2472 {
2473 unsigned int bb_index = postorder[i];
2474 remat_block_info *info = &m_block_info[bb_index];
2475 bitmap_clear_bit (&pending_blocks, bb_index);
2476
2477 if (empty_p (b: info->required_in))
2478 continue;
2479
2480 if (info->available_in)
2481 gcc_checking_assert (!bitmap_intersect_p (info->required_in,
2482 info->available_in));
2483
2484 if (local_remat_cheaper_p (query_bb_index: bb_index))
2485 {
2486 /* We'd prefer to rematerialize at the head of the block.
2487 Only move candidates if we need to. */
2488 compute_minimum_move_set (bb_index, required: &required);
2489 move_to_predecessors (bb_index, required: &required, pending_blocks: &pending_blocks);
2490 }
2491 else
2492 move_to_predecessors (bb_index, required: info->required_in,
2493 pending_blocks: &pending_blocks);
2494 }
2495 while (!bitmap_empty_p (map: &pending_blocks));
2496 bitmap_clear (&required);
2497}
2498
2499/* Emit all rematerialization instructions queued for BB. */
2500
2501void
2502early_remat::emit_remat_insns_for_block (basic_block bb)
2503{
2504 remat_block_info *info = &m_block_info[bb->index];
2505
2506 if (info->last_call && !empty_p (b: info->required_after_call))
2507 {
2508 restrict_remat_for_call (candidates: info->required_after_call, call: info->last_call);
2509 emit_remat_insns (required: info->required_after_call, NULL,
2510 reaching: info->rd_after_call, insn: info->last_call);
2511 }
2512
2513 if (!empty_p (b: info->required_in))
2514 {
2515 rtx_insn *insn = BB_HEAD (bb);
2516 while (insn != BB_END (bb)
2517 && !INSN_P (NEXT_INSN (insn)))
2518 insn = NEXT_INSN (insn);
2519 restrict_remat_for_unavail_regs (candidates: info->required_in, DF_LR_IN (bb));
2520 emit_remat_insns (required: info->required_in, available: info->available_in,
2521 reaching: info->rd_in, insn);
2522 }
2523}
2524
2525/* Decide which candidates in each block's REQUIRED_IN set need to be
2526 rematerialized and decide where the rematerialization instructions
2527 should go. Emit queued rematerialization instructions at the start
2528 of blocks and after the last calls in blocks. */
2529
2530void
2531early_remat::global_phase (void)
2532{
2533 compute_availability ();
2534 if (dump_file)
2535 {
2536 fprintf (stream: dump_file, format: "\n;; Blocks after computing global"
2537 " availability:\n");
2538 dump_all_blocks ();
2539 }
2540
2541 choose_rematerialization_points ();
2542 if (dump_file)
2543 {
2544 fprintf (stream: dump_file, format: "\n;; Blocks after choosing rematerialization"
2545 " points:\n");
2546 dump_all_blocks ();
2547 }
2548
2549 basic_block bb;
2550 FOR_EACH_BB_FN (bb, m_fn)
2551 emit_remat_insns_for_block (bb);
2552}
2553
2554/* Main function for the pass. */
2555
2556void
2557early_remat::run (void)
2558{
2559 df_analyze ();
2560
2561 if (!collect_candidates ())
2562 return;
2563
2564 init_block_info ();
2565 sort_candidates ();
2566 finalize_candidate_indices ();
2567 if (dump_file)
2568 dump_all_candidates ();
2569
2570 compute_rd ();
2571 decide_candidate_validity ();
2572 local_phase ();
2573 global_phase ();
2574}
2575
2576early_remat::early_remat (function *fn, sbitmap selected_modes)
2577 : m_fn (fn),
2578 m_selected_modes (selected_modes),
2579 m_available (0),
2580 m_required (0),
2581 m_value_table (63)
2582{
2583 bitmap_obstack_initialize (&m_obstack);
2584 bitmap_initialize (head: &m_candidate_regnos, obstack: &m_obstack);
2585 bitmap_initialize (head: &m_tmp_bitmap, obstack: &m_obstack);
2586}
2587
2588early_remat::~early_remat ()
2589{
2590 bitmap_obstack_release (&m_obstack);
2591}
2592
2593namespace {
2594
2595const pass_data pass_data_early_remat =
2596{
2597 .type: RTL_PASS, /* type */
2598 .name: "early_remat", /* name */
2599 .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
2600 .tv_id: TV_EARLY_REMAT, /* tv_id */
2601 .properties_required: 0, /* properties_required */
2602 .properties_provided: 0, /* properties_provided */
2603 .properties_destroyed: 0, /* properties_destroyed */
2604 .todo_flags_start: 0, /* todo_flags_start */
2605 TODO_df_finish, /* todo_flags_finish */
2606};
2607
2608class pass_early_remat : public rtl_opt_pass
2609{
2610public:
2611 pass_early_remat (gcc::context *ctxt)
2612 : rtl_opt_pass (pass_data_early_remat, ctxt)
2613 {}
2614
2615 /* opt_pass methods: */
2616 bool gate (function *) final override
2617 {
2618 return optimize > 1 && NUM_POLY_INT_COEFFS > 1;
2619 }
2620
2621 unsigned int execute (function *f) final override
2622 {
2623 auto_sbitmap selected_modes (NUM_MACHINE_MODES);
2624 bitmap_clear (selected_modes);
2625 targetm.select_early_remat_modes (selected_modes);
2626 if (!bitmap_empty_p (selected_modes))
2627 early_remat (f, selected_modes).run ();
2628 return 0;
2629 }
2630}; // class pass_early_remat
2631
2632} // anon namespace
2633
2634rtl_opt_pass *
2635make_pass_early_remat (gcc::context *ctxt)
2636{
2637 return new pass_early_remat (ctxt);
2638}
2639

source code of gcc/early-remat.cc