1/* Global constant/copy propagation for RTL.
2 Copyright (C) 1997-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 "rtlanal.h"
26#include "cfghooks.h"
27#include "df.h"
28#include "insn-config.h"
29#include "memmodel.h"
30#include "emit-rtl.h"
31#include "recog.h"
32#include "diagnostic-core.h"
33#include "toplev.h"
34#include "cfgrtl.h"
35#include "cfganal.h"
36#include "lcm.h"
37#include "cfgcleanup.h"
38#include "cselib.h"
39#include "intl.h"
40#include "tree-pass.h"
41#include "dbgcnt.h"
42#include "cfgloop.h"
43#include "gcse.h"
44
45
46/* An obstack for our working variables. */
47static struct obstack cprop_obstack;
48
49/* Occurrence of an expression.
50 There is one per basic block. If a pattern appears more than once the
51 last appearance is used. */
52
53struct cprop_occr
54{
55 /* Next occurrence of this expression. */
56 struct cprop_occr *next;
57 /* The insn that computes the expression. */
58 rtx_insn *insn;
59};
60
61/* Hash table entry for assignment expressions. */
62
63struct cprop_expr
64{
65 /* The expression (DEST := SRC). */
66 rtx dest;
67 rtx src;
68
69 /* Index in the available expression bitmaps. */
70 int bitmap_index;
71 /* Next entry with the same hash. */
72 struct cprop_expr *next_same_hash;
73 /* List of available occurrence in basic blocks in the function.
74 An "available occurrence" is one that is the last occurrence in the
75 basic block and whose operands are not modified by following statements
76 in the basic block [including this insn]. */
77 struct cprop_occr *avail_occr;
78};
79
80/* Hash table for copy propagation expressions.
81 Each hash table is an array of buckets.
82 ??? It is known that if it were an array of entries, structure elements
83 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
84 not clear whether in the final analysis a sufficient amount of memory would
85 be saved as the size of the available expression bitmaps would be larger
86 [one could build a mapping table without holes afterwards though].
87 Someday I'll perform the computation and figure it out. */
88
89struct hash_table_d
90{
91 /* The table itself.
92 This is an array of `set_hash_table_size' elements. */
93 struct cprop_expr **table;
94
95 /* Size of the hash table, in elements. */
96 unsigned int size;
97
98 /* Number of hash table elements. */
99 unsigned int n_elems;
100};
101
102/* Copy propagation hash table. */
103static struct hash_table_d set_hash_table;
104
105/* Array of implicit set patterns indexed by basic block index. */
106static rtx *implicit_sets;
107
108/* Array of indexes of expressions for implicit set patterns indexed by basic
109 block index. In other words, implicit_set_indexes[i] is the bitmap_index
110 of the expression whose RTX is implicit_sets[i]. */
111static int *implicit_set_indexes;
112
113/* Bitmap containing one bit for each register in the program.
114 Used when performing GCSE to track which registers have been set since
115 the start or end of the basic block while traversing that block. */
116static regset reg_set_bitmap;
117
118/* Various variables for statistics gathering. */
119
120/* Memory used in a pass.
121 This isn't intended to be absolutely precise. Its intent is only
122 to keep an eye on memory usage. */
123static int bytes_used;
124
125/* Number of local constants propagated. */
126static int local_const_prop_count;
127/* Number of local copies propagated. */
128static int local_copy_prop_count;
129/* Number of global constants propagated. */
130static int global_const_prop_count;
131/* Number of global copies propagated. */
132static int global_copy_prop_count;
133
134#define GOBNEW(T) ((T *) cprop_alloc (sizeof (T)))
135#define GOBNEWVAR(T, S) ((T *) cprop_alloc ((S)))
136
137/* Cover function to obstack_alloc. */
138
139static void *
140cprop_alloc (unsigned long size)
141{
142 bytes_used += size;
143 return obstack_alloc (&cprop_obstack, size);
144}
145
146/* Return true if register X is unchanged from INSN to the end
147 of INSN's basic block. */
148
149static bool
150reg_available_p (const_rtx x, const rtx_insn *insn ATTRIBUTE_UNUSED)
151{
152 return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
153}
154
155/* Hash a set of register REGNO.
156
157 Sets are hashed on the register that is set. This simplifies the PRE copy
158 propagation code.
159
160 ??? May need to make things more elaborate. Later, as necessary. */
161
162static unsigned int
163hash_mod (int regno, int hash_table_size)
164{
165 return (unsigned) regno % hash_table_size;
166}
167
168/* Insert assignment DEST:=SET from INSN in the hash table.
169 DEST is a register and SET is a register or a suitable constant.
170 If the assignment is already present in the table, record it as
171 the last occurrence in INSN's basic block.
172 IMPLICIT is true if it's an implicit set, false otherwise. */
173
174static void
175insert_set_in_table (rtx dest, rtx src, rtx_insn *insn,
176 struct hash_table_d *table, bool implicit)
177{
178 bool found = false;
179 unsigned int hash;
180 struct cprop_expr *cur_expr, *last_expr = NULL;
181 struct cprop_occr *cur_occr;
182
183 hash = hash_mod (REGNO (dest), hash_table_size: table->size);
184
185 for (cur_expr = table->table[hash]; cur_expr;
186 cur_expr = cur_expr->next_same_hash)
187 {
188 if (dest == cur_expr->dest
189 && src == cur_expr->src)
190 {
191 found = true;
192 break;
193 }
194 last_expr = cur_expr;
195 }
196
197 if (! found)
198 {
199 cur_expr = GOBNEW (struct cprop_expr);
200 bytes_used += sizeof (struct cprop_expr);
201 if (table->table[hash] == NULL)
202 /* This is the first pattern that hashed to this index. */
203 table->table[hash] = cur_expr;
204 else
205 /* Add EXPR to end of this hash chain. */
206 last_expr->next_same_hash = cur_expr;
207
208 /* Set the fields of the expr element.
209 We must copy X because it can be modified when copy propagation is
210 performed on its operands. */
211 cur_expr->dest = copy_rtx (dest);
212 cur_expr->src = copy_rtx (src);
213 cur_expr->bitmap_index = table->n_elems++;
214 cur_expr->next_same_hash = NULL;
215 cur_expr->avail_occr = NULL;
216 }
217
218 /* Now record the occurrence. */
219 cur_occr = cur_expr->avail_occr;
220
221 if (cur_occr
222 && BLOCK_FOR_INSN (insn: cur_occr->insn) == BLOCK_FOR_INSN (insn))
223 {
224 /* Found another instance of the expression in the same basic block.
225 Prefer this occurrence to the currently recorded one. We want
226 the last one in the block and the block is scanned from start
227 to end. */
228 cur_occr->insn = insn;
229 }
230 else
231 {
232 /* First occurrence of this expression in this basic block. */
233 cur_occr = GOBNEW (struct cprop_occr);
234 bytes_used += sizeof (struct cprop_occr);
235 cur_occr->insn = insn;
236 cur_occr->next = cur_expr->avail_occr;
237 cur_expr->avail_occr = cur_occr;
238 }
239
240 /* Record bitmap_index of the implicit set in implicit_set_indexes. */
241 if (implicit)
242 implicit_set_indexes[BLOCK_FOR_INSN (insn)->index]
243 = cur_expr->bitmap_index;
244}
245
246/* Determine whether the rtx X should be treated as a constant for CPROP.
247 Since X might be inserted more than once we have to take care that it
248 is sharable. */
249
250static bool
251cprop_constant_p (const_rtx x)
252{
253 return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x));
254}
255
256/* Determine whether the rtx X should be treated as a register that can
257 be propagated. Any pseudo-register is fine. */
258
259static bool
260cprop_reg_p (const_rtx x)
261{
262 return REG_P (x) && !HARD_REGISTER_P (x);
263}
264
265/* Scan SET present in INSN and add an entry to the hash TABLE.
266 IMPLICIT is true if it's an implicit set, false otherwise. */
267
268static void
269hash_scan_set (rtx set, rtx_insn *insn, struct hash_table_d *table,
270 bool implicit)
271{
272 rtx src = SET_SRC (set);
273 rtx dest = SET_DEST (set);
274
275 if (cprop_reg_p (x: dest)
276 && reg_available_p (x: dest, insn)
277 && can_copy_p (GET_MODE (dest)))
278 {
279 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
280
281 This allows us to do a single CPROP pass and still eliminate
282 redundant constants, addresses or other expressions that are
283 constructed with multiple instructions.
284
285 However, keep the original SRC if INSN is a simple reg-reg move. In
286 In this case, there will almost always be a REG_EQUAL note on the
287 insn that sets SRC. By recording the REG_EQUAL value here as SRC
288 for INSN, we miss copy propagation opportunities.
289
290 Note that this does not impede profitable constant propagations. We
291 "look through" reg-reg sets in lookup_set. */
292 rtx note = find_reg_equal_equiv_note (insn);
293 if (note != 0
294 && REG_NOTE_KIND (note) == REG_EQUAL
295 && !REG_P (src)
296 && cprop_constant_p (XEXP (note, 0)))
297 src = XEXP (note, 0), set = gen_rtx_SET (dest, src);
298
299 /* Record sets for constant/copy propagation. */
300 if ((cprop_reg_p (x: src)
301 && src != dest
302 && reg_available_p (x: src, insn))
303 || cprop_constant_p (x: src))
304 insert_set_in_table (dest, src, insn, table, implicit);
305 }
306}
307
308/* Process INSN and add hash table entries as appropriate. */
309
310static void
311hash_scan_insn (rtx_insn *insn, struct hash_table_d *table)
312{
313 rtx pat = PATTERN (insn);
314 int i;
315
316 /* Pick out the sets of INSN and for other forms of instructions record
317 what's been modified. */
318
319 if (GET_CODE (pat) == SET)
320 hash_scan_set (set: pat, insn, table, implicit: false);
321 else if (GET_CODE (pat) == PARALLEL)
322 for (i = 0; i < XVECLEN (pat, 0); i++)
323 {
324 rtx x = XVECEXP (pat, 0, i);
325
326 if (GET_CODE (x) == SET)
327 hash_scan_set (set: x, insn, table, implicit: false);
328 }
329}
330
331/* Dump the hash table TABLE to file FILE under the name NAME. */
332
333static void
334dump_hash_table (FILE *file, const char *name, struct hash_table_d *table)
335{
336 int i;
337 /* Flattened out table, so it's printed in proper order. */
338 struct cprop_expr **flat_table;
339 unsigned int *hash_val;
340 struct cprop_expr *expr;
341
342 flat_table = XCNEWVEC (struct cprop_expr *, table->n_elems);
343 hash_val = XNEWVEC (unsigned int, table->n_elems);
344
345 for (i = 0; i < (int) table->size; i++)
346 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
347 {
348 flat_table[expr->bitmap_index] = expr;
349 hash_val[expr->bitmap_index] = i;
350 }
351
352 fprintf (stream: file, format: "%s hash table (%d buckets, %d entries)\n",
353 name, table->size, table->n_elems);
354
355 for (i = 0; i < (int) table->n_elems; i++)
356 if (flat_table[i] != 0)
357 {
358 expr = flat_table[i];
359 fprintf (stream: file, format: "Index %d (hash value %d)\n ",
360 expr->bitmap_index, hash_val[i]);
361 print_rtl (file, expr->dest);
362 fprintf (stream: file, format: " := ");
363 print_rtl (file, expr->src);
364 fprintf (stream: file, format: "\n");
365 }
366
367 fprintf (stream: file, format: "\n");
368
369 free (ptr: flat_table);
370 free (ptr: hash_val);
371}
372
373/* Record as unavailable all registers that are DEF operands of INSN. */
374
375static void
376make_set_regs_unavailable (rtx_insn *insn)
377{
378 df_ref def;
379
380 FOR_EACH_INSN_DEF (def, insn)
381 SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (def));
382}
383
384/* Top level function to create an assignment hash table.
385
386 Assignment entries are placed in the hash table if
387 - they are of the form (set (pseudo-reg) src),
388 - src is something we want to perform const/copy propagation on,
389 - none of the operands or target are subsequently modified in the block
390
391 Currently src must be a pseudo-reg or a const_int.
392
393 TABLE is the table computed. */
394
395static void
396compute_hash_table_work (struct hash_table_d *table)
397{
398 basic_block bb;
399
400 /* Allocate vars to track sets of regs. */
401 reg_set_bitmap = ALLOC_REG_SET (NULL);
402
403 FOR_EACH_BB_FN (bb, cfun)
404 {
405 rtx_insn *insn;
406
407 /* Reset tables used to keep track of what's not yet invalid [since
408 the end of the block]. */
409 CLEAR_REG_SET (reg_set_bitmap);
410
411 /* Go over all insns from the last to the first. This is convenient
412 for tracking available registers, i.e. not set between INSN and
413 the end of the basic block BB. */
414 FOR_BB_INSNS_REVERSE (bb, insn)
415 {
416 /* Only real insns are interesting. */
417 if (!NONDEBUG_INSN_P (insn))
418 continue;
419
420 /* Record interesting sets from INSN in the hash table. */
421 hash_scan_insn (insn, table);
422
423 /* Any registers set in INSN will make SETs above it not AVAIL. */
424 make_set_regs_unavailable (insn);
425 }
426
427 /* Insert implicit sets in the hash table, pretending they appear as
428 insns at the head of the basic block. */
429 if (implicit_sets[bb->index] != NULL_RTX)
430 hash_scan_set (set: implicit_sets[bb->index], BB_HEAD (bb), table, implicit: true);
431 }
432
433 FREE_REG_SET (reg_set_bitmap);
434}
435
436/* Allocate space for the set/expr hash TABLE.
437 It is used to determine the number of buckets to use. */
438
439static void
440alloc_hash_table (struct hash_table_d *table)
441{
442 int n;
443
444 n = get_max_insn_count ();
445
446 table->size = n / 4;
447 if (table->size < 11)
448 table->size = 11;
449
450 /* Attempt to maintain efficient use of hash table.
451 Making it an odd number is simplest for now.
452 ??? Later take some measurements. */
453 table->size |= 1;
454 n = table->size * sizeof (struct cprop_expr *);
455 table->table = XNEWVAR (struct cprop_expr *, n);
456}
457
458/* Free things allocated by alloc_hash_table. */
459
460static void
461free_hash_table (struct hash_table_d *table)
462{
463 free (ptr: table->table);
464}
465
466/* Compute the hash TABLE for doing copy/const propagation or
467 expression hash table. */
468
469static void
470compute_hash_table (struct hash_table_d *table)
471{
472 /* Initialize count of number of entries in hash table. */
473 table->n_elems = 0;
474 memset (s: table->table, c: 0, n: table->size * sizeof (struct cprop_expr *));
475
476 compute_hash_table_work (table);
477}
478
479/* Expression tracking support. */
480
481/* Lookup REGNO in the set TABLE. The result is a pointer to the
482 table entry, or NULL if not found. */
483
484static struct cprop_expr *
485lookup_set (unsigned int regno, struct hash_table_d *table)
486{
487 unsigned int hash = hash_mod (regno, hash_table_size: table->size);
488 struct cprop_expr *expr;
489
490 expr = table->table[hash];
491
492 while (expr && REGNO (expr->dest) != regno)
493 expr = expr->next_same_hash;
494
495 return expr;
496}
497
498/* Return the next entry for REGNO in list EXPR. */
499
500static struct cprop_expr *
501next_set (unsigned int regno, struct cprop_expr *expr)
502{
503 do
504 expr = expr->next_same_hash;
505 while (expr && REGNO (expr->dest) != regno);
506
507 return expr;
508}
509
510/* Reset tables used to keep track of what's still available [since the
511 start of the block]. */
512
513static void
514reset_opr_set_tables (void)
515{
516 /* Maintain a bitmap of which regs have been set since beginning of
517 the block. */
518 CLEAR_REG_SET (reg_set_bitmap);
519}
520
521/* Return true if the register X has not been set yet [since the
522 start of the basic block containing INSN]. */
523
524static bool
525reg_not_set_p (const_rtx x, const rtx_insn *insn ATTRIBUTE_UNUSED)
526{
527 return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
528}
529
530/* Record things set by INSN.
531 This data is used by reg_not_set_p. */
532
533static void
534mark_oprs_set (rtx_insn *insn)
535{
536 df_ref def;
537
538 FOR_EACH_INSN_DEF (def, insn)
539 SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (def));
540}
541
542/* Compute copy/constant propagation working variables. */
543
544/* Local properties of assignments. */
545static sbitmap *cprop_avloc;
546static sbitmap *cprop_kill;
547
548/* Global properties of assignments (computed from the local properties). */
549static sbitmap *cprop_avin;
550static sbitmap *cprop_avout;
551
552/* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
553 basic blocks. N_SETS is the number of sets. */
554
555static void
556alloc_cprop_mem (int n_blocks, int n_sets)
557{
558 cprop_avloc = sbitmap_vector_alloc (n_blocks, n_sets);
559 cprop_kill = sbitmap_vector_alloc (n_blocks, n_sets);
560
561 cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
562 cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
563}
564
565/* Free vars used by copy/const propagation. */
566
567static void
568free_cprop_mem (void)
569{
570 sbitmap_vector_free (vec: cprop_avloc);
571 sbitmap_vector_free (vec: cprop_kill);
572 sbitmap_vector_free (vec: cprop_avin);
573 sbitmap_vector_free (vec: cprop_avout);
574}
575
576/* Compute the local properties of each recorded expression.
577
578 Local properties are those that are defined by the block, irrespective of
579 other blocks.
580
581 An expression is killed in a block if its operands, either DEST or SRC, are
582 modified in the block.
583
584 An expression is computed (locally available) in a block if it is computed
585 at least once and expression would contain the same value if the
586 computation was moved to the end of the block.
587
588 KILL and COMP are destination sbitmaps for recording local properties. */
589
590static void
591compute_local_properties (sbitmap *kill, sbitmap *comp,
592 struct hash_table_d *table)
593{
594 unsigned int i;
595
596 /* Initialize the bitmaps that were passed in. */
597 bitmap_vector_clear (kill, last_basic_block_for_fn (cfun));
598 bitmap_vector_clear (comp, last_basic_block_for_fn (cfun));
599
600 for (i = 0; i < table->size; i++)
601 {
602 struct cprop_expr *expr;
603
604 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
605 {
606 int indx = expr->bitmap_index;
607 df_ref def;
608 struct cprop_occr *occr;
609
610 /* For each definition of the destination pseudo-reg, the expression
611 is killed in the block where the definition is. */
612 for (def = DF_REG_DEF_CHAIN (REGNO (expr->dest));
613 def; def = DF_REF_NEXT_REG (def))
614 bitmap_set_bit (map: kill[DF_REF_BB (def)->index], bitno: indx);
615
616 /* If the source is a pseudo-reg, for each definition of the source,
617 the expression is killed in the block where the definition is. */
618 if (REG_P (expr->src))
619 for (def = DF_REG_DEF_CHAIN (REGNO (expr->src));
620 def; def = DF_REF_NEXT_REG (def))
621 bitmap_set_bit (map: kill[DF_REF_BB (def)->index], bitno: indx);
622
623 /* The occurrences recorded in avail_occr are exactly those that
624 are locally available in the block where they are. */
625 for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
626 {
627 bitmap_set_bit (map: comp[BLOCK_FOR_INSN (insn: occr->insn)->index], bitno: indx);
628 }
629 }
630 }
631}
632
633/* Hash table support. */
634
635/* Top level routine to do the dataflow analysis needed by copy/const
636 propagation. */
637
638static void
639compute_cprop_data (void)
640{
641 basic_block bb;
642
643 compute_local_properties (kill: cprop_kill, comp: cprop_avloc, table: &set_hash_table);
644 compute_available (cprop_avloc, cprop_kill, cprop_avout, cprop_avin);
645
646 /* Merge implicit sets into CPROP_AVIN. They are always available at the
647 entry of their basic block. We need to do this because 1) implicit sets
648 aren't recorded for the local pass so they cannot be propagated within
649 their basic block by this pass and 2) the global pass would otherwise
650 propagate them only in the successors of their basic block. */
651 FOR_EACH_BB_FN (bb, cfun)
652 {
653 int index = implicit_set_indexes[bb->index];
654 if (index != -1)
655 bitmap_set_bit (map: cprop_avin[bb->index], bitno: index);
656 }
657}
658
659/* Copy/constant propagation. */
660
661/* Maximum number of register uses in an insn that we handle. */
662#define MAX_USES 8
663
664/* Table of uses (registers, both hard and pseudo) found in an insn.
665 Allocated statically to avoid alloc/free complexity and overhead. */
666static rtx reg_use_table[MAX_USES];
667
668/* Index into `reg_use_table' while building it. */
669static unsigned reg_use_count;
670
671/* Set up a list of register numbers used in INSN. The found uses are stored
672 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
673 and contains the number of uses in the table upon exit.
674
675 ??? If a register appears multiple times we will record it multiple times.
676 This doesn't hurt anything but it will slow things down. */
677
678static void
679find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED)
680{
681 int i, j;
682 enum rtx_code code;
683 const char *fmt;
684 rtx x = *xptr;
685
686 /* repeat is used to turn tail-recursion into iteration since GCC
687 can't do it when there's no return value. */
688 repeat:
689 if (x == 0)
690 return;
691
692 code = GET_CODE (x);
693 if (REG_P (x))
694 {
695 if (reg_use_count == MAX_USES)
696 return;
697
698 reg_use_table[reg_use_count] = x;
699 reg_use_count++;
700 }
701
702 /* Recursively scan the operands of this expression. */
703
704 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
705 {
706 if (fmt[i] == 'e')
707 {
708 /* If we are about to do the last recursive call
709 needed at this level, change it into iteration.
710 This function is called enough to be worth it. */
711 if (i == 0)
712 {
713 x = XEXP (x, 0);
714 goto repeat;
715 }
716
717 find_used_regs (xptr: &XEXP (x, i), data);
718 }
719 else if (fmt[i] == 'E')
720 for (j = 0; j < XVECLEN (x, i); j++)
721 find_used_regs (xptr: &XVECEXP (x, i, j), data);
722 }
723}
724
725/* Try to replace all uses of FROM in INSN with TO.
726 Return true if successful. */
727
728static bool
729try_replace_reg (rtx from, rtx to, rtx_insn *insn)
730{
731 rtx note = find_reg_equal_equiv_note (insn);
732 rtx src = 0;
733 bool success = false;
734 rtx set = single_set (insn);
735
736 bool check_rtx_costs = true;
737 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
738 int old_cost = set ? set_rtx_cost (x: set, speed_p: speed) : 0;
739
740 if (!set
741 || CONSTANT_P (SET_SRC (set))
742 || (note != 0
743 && REG_NOTE_KIND (note) == REG_EQUAL
744 && (GET_CODE (XEXP (note, 0)) == CONST
745 || CONSTANT_P (XEXP (note, 0)))))
746 check_rtx_costs = false;
747
748 /* Usually we substitute easy stuff, so we won't copy everything.
749 We however need to take care to not duplicate non-trivial CONST
750 expressions. */
751 to = copy_rtx (to);
752
753 validate_replace_src_group (from, to, insn);
754
755 /* If TO is a constant, check the cost of the set after propagation
756 to the cost of the set before the propagation. If the cost is
757 higher, then do not replace FROM with TO. */
758
759 if (check_rtx_costs
760 && CONSTANT_P (to)
761 && set_rtx_cost (x: set, speed_p: speed) > old_cost)
762 {
763 cancel_changes (0);
764 return false;
765 }
766
767
768 if (num_changes_pending () && apply_change_group ())
769 success = true;
770
771 /* Try to simplify SET_SRC if we have substituted a constant. */
772 if (success && set && CONSTANT_P (to))
773 {
774 src = simplify_rtx (SET_SRC (set));
775
776 if (src)
777 validate_change (insn, &SET_SRC (set), src, 0);
778 }
779
780 /* If there is already a REG_EQUAL note, update the expression in it
781 with our replacement. */
782 if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
783 set_unique_reg_note (insn, REG_EQUAL,
784 simplify_replace_rtx (XEXP (note, 0), from, to));
785 if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
786 {
787 /* If above failed and this is a single set, try to simplify the source
788 of the set given our substitution. We could perhaps try this for
789 multiple SETs, but it probably won't buy us anything. */
790 src = simplify_replace_rtx (SET_SRC (set), from, to);
791
792 if (!rtx_equal_p (src, SET_SRC (set))
793 && validate_change (insn, &SET_SRC (set), src, 0))
794 success = true;
795
796 /* If we've failed perform the replacement, have a single SET to
797 a REG destination and don't yet have a note, add a REG_EQUAL note
798 to not lose information. */
799 if (!success && note == 0 && set != 0 && REG_P (SET_DEST (set))
800 && !contains_paradoxical_subreg_p (SET_SRC (set)))
801 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
802 }
803
804 if (set && MEM_P (SET_DEST (set)) && reg_mentioned_p (from, SET_DEST (set)))
805 {
806 /* Registers can also appear as uses in SET_DEST if it is a MEM.
807 We could perhaps try this for multiple SETs, but it probably
808 won't buy us anything. */
809 rtx dest = simplify_replace_rtx (SET_DEST (set), from, to);
810
811 if (!rtx_equal_p (dest, SET_DEST (set))
812 && validate_change (insn, &SET_DEST (set), dest, 0))
813 success = true;
814 }
815
816 /* REG_EQUAL may get simplified into register.
817 We don't allow that. Remove that note. This code ought
818 not to happen, because previous code ought to synthesize
819 reg-reg move, but be on the safe side. */
820 if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0)))
821 remove_note (insn, note);
822
823 return success;
824}
825
826/* Find a set of REGNOs that are available on entry to INSN's block. If found,
827 SET_RET[0] will be assigned a set with a register source and SET_RET[1] a
828 set with a constant source. If not found the corresponding entry is set to
829 NULL. */
830
831static void
832find_avail_set (int regno, rtx_insn *insn, struct cprop_expr *set_ret[2])
833{
834 set_ret[0] = set_ret[1] = NULL;
835
836 /* Loops are not possible here. To get a loop we would need two sets
837 available at the start of the block containing INSN. i.e. we would
838 need two sets like this available at the start of the block:
839
840 (set (reg X) (reg Y))
841 (set (reg Y) (reg X))
842
843 This cannot happen since the set of (reg Y) would have killed the
844 set of (reg X) making it unavailable at the start of this block. */
845 while (1)
846 {
847 rtx src;
848 struct cprop_expr *set = lookup_set (regno, table: &set_hash_table);
849
850 /* Find a set that is available at the start of the block
851 which contains INSN. */
852 while (set)
853 {
854 if (bitmap_bit_p (map: cprop_avin[BLOCK_FOR_INSN (insn)->index],
855 bitno: set->bitmap_index))
856 break;
857 set = next_set (regno, expr: set);
858 }
859
860 /* If no available set was found we've reached the end of the
861 (possibly empty) copy chain. */
862 if (set == 0)
863 break;
864
865 src = set->src;
866
867 /* We know the set is available.
868 Now check that SRC is locally anticipatable (i.e. none of the
869 source operands have changed since the start of the block).
870
871 If the source operand changed, we may still use it for the next
872 iteration of this loop, but we may not use it for substitutions. */
873
874 if (cprop_constant_p (x: src))
875 set_ret[1] = set;
876 else if (reg_not_set_p (x: src, insn))
877 set_ret[0] = set;
878
879 /* If the source of the set is anything except a register, then
880 we have reached the end of the copy chain. */
881 if (! REG_P (src))
882 break;
883
884 /* Follow the copy chain, i.e. start another iteration of the loop
885 and see if we have an available copy into SRC. */
886 regno = REGNO (src);
887 }
888}
889
890/* Subroutine of cprop_insn that tries to propagate constants into
891 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
892 it is the instruction that immediately precedes JUMP, and must be a
893 single SET of a register. FROM is what we will try to replace,
894 SRC is the constant we will try to substitute for it. Return true
895 if a change was made. */
896
897static bool
898cprop_jump (basic_block bb, rtx_insn *setcc, rtx_insn *jump, rtx from, rtx src)
899{
900 rtx new_rtx, set_src, note_src;
901 rtx set = pc_set (jump);
902 rtx note = find_reg_equal_equiv_note (jump);
903
904 if (note)
905 {
906 note_src = XEXP (note, 0);
907 if (GET_CODE (note_src) == EXPR_LIST)
908 note_src = NULL_RTX;
909 }
910 else note_src = NULL_RTX;
911
912 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
913 set_src = note_src ? note_src : SET_SRC (set);
914
915 /* First substitute the SETCC condition into the JUMP instruction,
916 then substitute that given values into this expanded JUMP. */
917 if (setcc != NULL_RTX
918 && !modified_between_p (from, setcc, jump)
919 && !modified_between_p (src, setcc, jump))
920 {
921 rtx setcc_src;
922 rtx setcc_set = single_set (insn: setcc);
923 rtx setcc_note = find_reg_equal_equiv_note (setcc);
924 setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST)
925 ? XEXP (setcc_note, 0) : SET_SRC (setcc_set);
926 set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set),
927 setcc_src);
928 }
929 else
930 setcc = NULL;
931
932 new_rtx = simplify_replace_rtx (set_src, from, src);
933
934 /* If no simplification can be made, then try the next register. */
935 if (rtx_equal_p (new_rtx, SET_SRC (set)))
936 return false;
937
938 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
939 if (new_rtx == pc_rtx)
940 delete_insn (jump);
941 else
942 {
943 /* Ensure the value computed inside the jump insn to be equivalent
944 to one computed by setcc. */
945 if (setcc && modified_in_p (new_rtx, setcc))
946 return false;
947 if (! validate_unshare_change (jump, &SET_SRC (set), new_rtx, 0))
948 {
949 /* When (some) constants are not valid in a comparison, and there
950 are two registers to be replaced by constants before the entire
951 comparison can be folded into a constant, we need to keep
952 intermediate information in REG_EQUAL notes. For targets with
953 separate compare insns, such notes are added by try_replace_reg.
954 When we have a combined compare-and-branch instruction, however,
955 we need to attach a note to the branch itself to make this
956 optimization work. */
957
958 if (!rtx_equal_p (new_rtx, note_src))
959 set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new_rtx));
960 return false;
961 }
962
963 /* Remove REG_EQUAL note after simplification. */
964 if (note_src)
965 remove_note (jump, note);
966 }
967
968 global_const_prop_count++;
969 if (dump_file != NULL)
970 {
971 fprintf (stream: dump_file,
972 format: "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with "
973 "constant ", REGNO (from), INSN_UID (insn: jump));
974 print_rtl (dump_file, src);
975 fprintf (stream: dump_file, format: "\n");
976 }
977 purge_dead_edges (bb);
978
979 /* If a conditional jump has been changed into unconditional jump, remove
980 the jump and make the edge fallthru - this is always called in
981 cfglayout mode. */
982 if (new_rtx != pc_rtx && simplejump_p (jump))
983 {
984 edge e;
985 edge_iterator ei;
986
987 FOR_EACH_EDGE (e, ei, bb->succs)
988 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
989 && BB_HEAD (e->dest) == JUMP_LABEL (jump))
990 {
991 e->flags |= EDGE_FALLTHRU;
992 break;
993 }
994 delete_insn (jump);
995 }
996
997 return true;
998}
999
1000/* Subroutine of cprop_insn that tries to propagate constants. FROM is what
1001 we will try to replace, SRC is the constant we will try to substitute for
1002 it and INSN is the instruction where this will be happening. */
1003
1004static bool
1005constprop_register (rtx from, rtx src, rtx_insn *insn)
1006{
1007 rtx sset;
1008 rtx_insn *next_insn;
1009
1010 /* Check for reg setting instructions followed by conditional branch
1011 instructions first. */
1012 if ((sset = single_set (insn)) != NULL
1013 && (next_insn = next_nondebug_insn (insn)) != NULL
1014 && any_condjump_p (next_insn)
1015 && onlyjump_p (next_insn))
1016 {
1017 rtx dest = SET_DEST (sset);
1018 if (REG_P (dest)
1019 && cprop_jump (bb: BLOCK_FOR_INSN (insn), setcc: insn, jump: next_insn,
1020 from, src))
1021 return true;
1022 }
1023
1024 /* Handle normal insns next. */
1025 if (NONJUMP_INSN_P (insn) && try_replace_reg (from, to: src, insn))
1026 return true;
1027
1028 /* Try to propagate a CONST_INT into a conditional jump.
1029 We're pretty specific about what we will handle in this
1030 code, we can extend this as necessary over time.
1031
1032 Right now the insn in question must look like
1033 (set (pc) (if_then_else ...)) */
1034 else if (any_condjump_p (insn) && onlyjump_p (insn))
1035 return cprop_jump (bb: BLOCK_FOR_INSN (insn), NULL, jump: insn, from, src);
1036 return false;
1037}
1038
1039/* Perform constant and copy propagation on INSN.
1040 Return true if a change was made. */
1041
1042static bool
1043cprop_insn (rtx_insn *insn)
1044{
1045 unsigned i;
1046 int changed_this_round;
1047 bool changed = false;
1048 rtx note;
1049
1050 do
1051 {
1052 changed_this_round = 0;
1053 reg_use_count = 0;
1054 note_uses (&PATTERN (insn), find_used_regs, NULL);
1055
1056 /* We may win even when propagating constants into notes. */
1057 note = find_reg_equal_equiv_note (insn);
1058 if (note)
1059 find_used_regs (xptr: &XEXP (note, 0), NULL);
1060
1061 for (i = 0; i < reg_use_count; i++)
1062 {
1063 rtx reg_used = reg_use_table[i];
1064 unsigned int regno = REGNO (reg_used);
1065 rtx src_cst = NULL, src_reg = NULL;
1066 struct cprop_expr *set[2];
1067
1068 /* If the register has already been set in this block, there's
1069 nothing we can do. */
1070 if (! reg_not_set_p (x: reg_used, insn))
1071 continue;
1072
1073 /* Find an assignment that sets reg_used and is available
1074 at the start of the block. */
1075 find_avail_set (regno, insn, set_ret: set);
1076 if (set[0])
1077 src_reg = set[0]->src;
1078 if (set[1])
1079 src_cst = set[1]->src;
1080
1081 /* Constant propagation. */
1082 if (src_cst && cprop_constant_p (x: src_cst)
1083 && constprop_register (from: reg_used, src: src_cst, insn))
1084 {
1085 changed = true;
1086 changed_this_round = 1;
1087 global_const_prop_count++;
1088 if (dump_file != NULL)
1089 {
1090 fprintf (stream: dump_file,
1091 format: "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
1092 fprintf (stream: dump_file, format: "insn %d with constant ",
1093 INSN_UID (insn));
1094 print_rtl (dump_file, src_cst);
1095 fprintf (stream: dump_file, format: "\n");
1096 }
1097 if (insn->deleted ())
1098 return true;
1099 }
1100 /* Copy propagation. */
1101 else if (src_reg && cprop_reg_p (x: src_reg)
1102 && REGNO (src_reg) != regno
1103 && try_replace_reg (from: reg_used, to: src_reg, insn))
1104 {
1105 changed = true;
1106 changed_this_round = 1;
1107 global_copy_prop_count++;
1108 if (dump_file != NULL)
1109 {
1110 fprintf (stream: dump_file,
1111 format: "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1112 regno, INSN_UID (insn));
1113 fprintf (stream: dump_file, format: " with reg %d\n", REGNO (src_reg));
1114 }
1115
1116 /* The original insn setting reg_used may or may not now be
1117 deletable. We leave the deletion to DCE. */
1118 /* FIXME: If it turns out that the insn isn't deletable,
1119 then we may have unnecessarily extended register lifetimes
1120 and made things worse. */
1121 }
1122 }
1123 }
1124 /* If try_replace_reg simplified the insn, the regs found by find_used_regs
1125 may not be valid anymore. Start over. */
1126 while (changed_this_round);
1127
1128 if (changed && DEBUG_INSN_P (insn))
1129 return false;
1130
1131 return changed;
1132}
1133
1134/* Like find_used_regs, but avoid recording uses that appear in
1135 input-output contexts such as zero_extract or pre_dec. This
1136 restricts the cases we consider to those for which local cprop
1137 can legitimately make replacements. */
1138
1139static void
1140local_cprop_find_used_regs (rtx *xptr, void *data)
1141{
1142 rtx x = *xptr;
1143
1144 if (x == 0)
1145 return;
1146
1147 switch (GET_CODE (x))
1148 {
1149 case ZERO_EXTRACT:
1150 case SIGN_EXTRACT:
1151 case STRICT_LOW_PART:
1152 return;
1153
1154 case PRE_DEC:
1155 case PRE_INC:
1156 case POST_DEC:
1157 case POST_INC:
1158 case PRE_MODIFY:
1159 case POST_MODIFY:
1160 /* Can only legitimately appear this early in the context of
1161 stack pushes for function arguments, but handle all of the
1162 codes nonetheless. */
1163 return;
1164
1165 case SUBREG:
1166 if (read_modify_subreg_p (x))
1167 return;
1168 break;
1169
1170 default:
1171 break;
1172 }
1173
1174 find_used_regs (xptr, data);
1175}
1176
1177/* Try to perform local const/copy propagation on X in INSN. */
1178
1179static bool
1180do_local_cprop (rtx x, rtx_insn *insn)
1181{
1182 rtx newreg = NULL, newcnst = NULL;
1183
1184 /* Rule out USE instructions and ASM statements as we don't want to
1185 change the hard registers mentioned. */
1186 if (REG_P (x)
1187 && (cprop_reg_p (x)
1188 || (GET_CODE (PATTERN (insn)) != USE
1189 && asm_noperands (PATTERN (insn)) < 0)))
1190 {
1191 cselib_val *val = cselib_lookup (x, GET_MODE (x), 0, VOIDmode);
1192 struct elt_loc_list *l;
1193
1194 if (!val)
1195 return false;
1196 for (l = val->locs; l; l = l->next)
1197 {
1198 rtx this_rtx = l->loc;
1199 rtx note;
1200
1201 if (cprop_constant_p (x: this_rtx))
1202 newcnst = this_rtx;
1203 if (cprop_reg_p (x: this_rtx)
1204 /* Don't copy propagate if it has attached REG_EQUIV note.
1205 At this point this only function parameters should have
1206 REG_EQUIV notes and if the argument slot is used somewhere
1207 explicitly, it means address of parameter has been taken,
1208 so we should not extend the lifetime of the pseudo. */
1209 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
1210 || ! MEM_P (XEXP (note, 0))))
1211 newreg = this_rtx;
1212 }
1213 if (newcnst && constprop_register (from: x, src: newcnst, insn))
1214 {
1215 if (dump_file != NULL)
1216 {
1217 fprintf (stream: dump_file, format: "LOCAL CONST-PROP: Replacing reg %d in ",
1218 REGNO (x));
1219 fprintf (stream: dump_file, format: "insn %d with constant ",
1220 INSN_UID (insn));
1221 print_rtl (dump_file, newcnst);
1222 fprintf (stream: dump_file, format: "\n");
1223 }
1224 local_const_prop_count++;
1225 return true;
1226 }
1227 else if (newreg && newreg != x && try_replace_reg (from: x, to: newreg, insn))
1228 {
1229 if (dump_file != NULL)
1230 {
1231 fprintf (stream: dump_file,
1232 format: "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1233 REGNO (x), INSN_UID (insn));
1234 fprintf (stream: dump_file, format: " with reg %d\n", REGNO (newreg));
1235 }
1236 local_copy_prop_count++;
1237 return true;
1238 }
1239 }
1240 return false;
1241}
1242
1243/* Do local const/copy propagation (i.e. within each basic block). */
1244
1245static bool
1246local_cprop_pass (void)
1247{
1248 basic_block bb;
1249 rtx_insn *insn;
1250 bool changed = false;
1251 unsigned i;
1252
1253 auto_vec<rtx_insn *> uncond_traps;
1254
1255 cselib_init (0);
1256 FOR_EACH_BB_FN (bb, cfun)
1257 {
1258 FOR_BB_INSNS (bb, insn)
1259 {
1260 if (INSN_P (insn))
1261 {
1262 bool was_uncond_trap
1263 = (GET_CODE (PATTERN (insn)) == TRAP_IF
1264 && XEXP (PATTERN (insn), 0) == const1_rtx);
1265 rtx note = find_reg_equal_equiv_note (insn);
1266 do
1267 {
1268 reg_use_count = 0;
1269 note_uses (&PATTERN (insn), local_cprop_find_used_regs,
1270 NULL);
1271 if (note)
1272 local_cprop_find_used_regs (xptr: &XEXP (note, 0), NULL);
1273
1274 for (i = 0; i < reg_use_count; i++)
1275 {
1276 if (do_local_cprop (x: reg_use_table[i], insn))
1277 {
1278 if (!DEBUG_INSN_P (insn))
1279 changed = true;
1280 break;
1281 }
1282 }
1283 if (!was_uncond_trap
1284 && GET_CODE (PATTERN (insn)) == TRAP_IF
1285 && XEXP (PATTERN (insn), 0) == const1_rtx)
1286 {
1287 uncond_traps.safe_push (obj: insn);
1288 break;
1289 }
1290 if (insn->deleted ())
1291 break;
1292 }
1293 while (i < reg_use_count);
1294 }
1295 cselib_process_insn (insn);
1296 }
1297
1298 /* Forget everything at the end of a basic block. */
1299 cselib_clear_table ();
1300 }
1301
1302 cselib_finish ();
1303
1304 while (!uncond_traps.is_empty ())
1305 {
1306 rtx_insn *insn = uncond_traps.pop ();
1307 basic_block to_split = BLOCK_FOR_INSN (insn);
1308 remove_edge (split_block (to_split, insn));
1309 emit_barrier_after_bb (bb: to_split);
1310 }
1311
1312 return changed;
1313}
1314
1315/* Similar to get_condition, only the resulting condition must be
1316 valid at JUMP, instead of at EARLIEST.
1317
1318 This differs from noce_get_condition in ifcvt.cc in that we prefer not to
1319 settle for the condition variable in the jump instruction being integral.
1320 We prefer to be able to record the value of a user variable, rather than
1321 the value of a temporary used in a condition. This could be solved by
1322 recording the value of *every* register scanned by canonicalize_condition,
1323 but this would require some code reorganization. */
1324
1325rtx
1326fis_get_condition (rtx_insn *jump)
1327{
1328 return get_condition (jump, NULL, false, true);
1329}
1330
1331/* Check the comparison COND to see if we can safely form an implicit
1332 set from it. */
1333
1334static bool
1335implicit_set_cond_p (const_rtx cond)
1336{
1337 machine_mode mode;
1338 rtx cst;
1339
1340 /* COND must be either an EQ or NE comparison. */
1341 if (GET_CODE (cond) != EQ && GET_CODE (cond) != NE)
1342 return false;
1343
1344 /* The first operand of COND must be a register we can propagate. */
1345 if (!cprop_reg_p (XEXP (cond, 0)))
1346 return false;
1347
1348 /* The second operand of COND must be a suitable constant. */
1349 mode = GET_MODE (XEXP (cond, 0));
1350 cst = XEXP (cond, 1);
1351
1352 /* We can't perform this optimization if either operand might be or might
1353 contain a signed zero. */
1354 if (HONOR_SIGNED_ZEROS (mode))
1355 {
1356 /* It is sufficient to check if CST is or contains a zero. We must
1357 handle float, complex, and vector. If any subpart is a zero, then
1358 the optimization can't be performed. */
1359 /* ??? The complex and vector checks are not implemented yet. We just
1360 always return false for them. */
1361 if (CONST_DOUBLE_AS_FLOAT_P (cst)
1362 && real_equal (CONST_DOUBLE_REAL_VALUE (cst), &dconst0))
1363 return false;
1364 else
1365 return false;
1366 }
1367
1368 return cprop_constant_p (x: cst);
1369}
1370
1371/* Find the implicit sets of a function. An "implicit set" is a constraint
1372 on the value of a variable, implied by a conditional jump. For example,
1373 following "if (x == 2)", the then branch may be optimized as though the
1374 conditional performed an "explicit set", in this example, "x = 2". This
1375 function records the set patterns that are implicit at the start of each
1376 basic block.
1377
1378 If an implicit set is found but the set is implicit on a critical edge,
1379 this critical edge is split.
1380
1381 Return true if the CFG was modified, false otherwise. */
1382
1383static bool
1384find_implicit_sets (void)
1385{
1386 basic_block bb, dest;
1387 rtx cond, new_rtx;
1388 unsigned int count = 0;
1389 bool edges_split = false;
1390 size_t implicit_sets_size = last_basic_block_for_fn (cfun) + 10;
1391
1392 implicit_sets = XCNEWVEC (rtx, implicit_sets_size);
1393
1394 FOR_EACH_BB_FN (bb, cfun)
1395 {
1396 /* Check for more than one successor. */
1397 if (EDGE_COUNT (bb->succs) <= 1)
1398 continue;
1399
1400 cond = fis_get_condition (BB_END (bb));
1401
1402 /* If no condition is found or if it isn't of a suitable form,
1403 ignore it. */
1404 if (! cond || ! implicit_set_cond_p (cond))
1405 continue;
1406
1407 dest = GET_CODE (cond) == EQ
1408 ? BRANCH_EDGE (bb)->dest : FALLTHRU_EDGE (bb)->dest;
1409
1410 /* If DEST doesn't go anywhere, ignore it. */
1411 if (! dest || dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1412 continue;
1413
1414 /* We have found a suitable implicit set. Try to record it now as
1415 a SET in DEST. If DEST has more than one predecessor, the edge
1416 between BB and DEST is a critical edge and we must split it,
1417 because we can only record one implicit set per DEST basic block. */
1418 if (! single_pred_p (bb: dest))
1419 {
1420 dest = split_edge (find_edge (bb, dest));
1421 edges_split = true;
1422 }
1423
1424 if (implicit_sets_size <= (size_t) dest->index)
1425 {
1426 size_t old_implicit_sets_size = implicit_sets_size;
1427 implicit_sets_size *= 2;
1428 implicit_sets = XRESIZEVEC (rtx, implicit_sets, implicit_sets_size);
1429 memset (s: implicit_sets + old_implicit_sets_size, c: 0,
1430 n: (implicit_sets_size - old_implicit_sets_size) * sizeof (rtx));
1431 }
1432
1433 new_rtx = gen_rtx_SET (XEXP (cond, 0), XEXP (cond, 1));
1434 implicit_sets[dest->index] = new_rtx;
1435 if (dump_file)
1436 {
1437 fprintf (stream: dump_file, format: "Implicit set of reg %d in ",
1438 REGNO (XEXP (cond, 0)));
1439 fprintf (stream: dump_file, format: "basic block %d\n", dest->index);
1440 }
1441 count++;
1442 }
1443
1444 if (dump_file)
1445 fprintf (stream: dump_file, format: "Found %d implicit sets\n", count);
1446
1447 /* Confess our sins. */
1448 return edges_split;
1449}
1450
1451/* Bypass conditional jumps. */
1452
1453/* The value of last_basic_block at the beginning of the jump_bypass
1454 pass. The use of redirect_edge_and_branch_force may introduce new
1455 basic blocks, but the data flow analysis is only valid for basic
1456 block indices less than bypass_last_basic_block. */
1457
1458static int bypass_last_basic_block;
1459
1460/* Find a set of REGNO to a constant that is available at the end of basic
1461 block BB. Return NULL if no such set is found. Based heavily upon
1462 find_avail_set. */
1463
1464static struct cprop_expr *
1465find_bypass_set (int regno, int bb)
1466{
1467 struct cprop_expr *result = 0;
1468
1469 for (;;)
1470 {
1471 rtx src;
1472 struct cprop_expr *set = lookup_set (regno, table: &set_hash_table);
1473
1474 while (set)
1475 {
1476 if (bitmap_bit_p (map: cprop_avout[bb], bitno: set->bitmap_index))
1477 break;
1478 set = next_set (regno, expr: set);
1479 }
1480
1481 if (set == 0)
1482 break;
1483
1484 src = set->src;
1485 if (cprop_constant_p (x: src))
1486 result = set;
1487
1488 if (! REG_P (src))
1489 break;
1490
1491 regno = REGNO (src);
1492 }
1493 return result;
1494}
1495
1496/* Subroutine of bypass_block that checks whether a pseudo is killed by
1497 any of the instructions inserted on an edge. Jump bypassing places
1498 condition code setters on CFG edges using insert_insn_on_edge. This
1499 function is required to check that our data flow analysis is still
1500 valid prior to commit_edge_insertions. */
1501
1502static bool
1503reg_killed_on_edge (const_rtx reg, const_edge e)
1504{
1505 rtx_insn *insn;
1506
1507 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
1508 if (INSN_P (insn) && reg_set_p (reg, insn))
1509 return true;
1510
1511 return false;
1512}
1513
1514/* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1515 basic block BB which has more than one predecessor. If not NULL, SETCC
1516 is the first instruction of BB, which is immediately followed by JUMP_INSN
1517 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1518 Returns true if a change was made.
1519
1520 During the jump bypassing pass, we may place copies of SETCC instructions
1521 on CFG edges. The following routine must be careful to pay attention to
1522 these inserted insns when performing its transformations. */
1523
1524static bool
1525bypass_block (basic_block bb, rtx_insn *setcc, rtx_insn *jump)
1526{
1527 rtx_insn *insn;
1528 rtx note;
1529 edge e, edest;
1530 bool change;
1531 bool may_be_loop_header = false;
1532 bool removed_p;
1533 unsigned i;
1534 edge_iterator ei;
1535
1536 insn = (setcc != NULL) ? setcc : jump;
1537
1538 /* Determine set of register uses in INSN. */
1539 reg_use_count = 0;
1540 note_uses (&PATTERN (insn), find_used_regs, NULL);
1541 note = find_reg_equal_equiv_note (insn);
1542 if (note)
1543 find_used_regs (xptr: &XEXP (note, 0), NULL);
1544
1545 if (current_loops)
1546 {
1547 /* If we are to preserve loop structure then do not bypass
1548 a loop header. This will either rotate the loop, create
1549 multiple entry loops or even irreducible regions. */
1550 if (bb == bb->loop_father->header)
1551 return 0;
1552 }
1553 else
1554 {
1555 FOR_EACH_EDGE (e, ei, bb->preds)
1556 if (e->flags & EDGE_DFS_BACK)
1557 {
1558 may_be_loop_header = true;
1559 break;
1560 }
1561 }
1562
1563 change = false;
1564 for (ei = ei_start (bb->preds); (e = ei_safe_edge (i: ei)); )
1565 {
1566 removed_p = false;
1567
1568 if (e->flags & EDGE_COMPLEX)
1569 {
1570 ei_next (i: &ei);
1571 continue;
1572 }
1573
1574 /* We can't redirect edges from new basic blocks. */
1575 if (e->src->index >= bypass_last_basic_block)
1576 {
1577 ei_next (i: &ei);
1578 continue;
1579 }
1580
1581 /* The irreducible loops created by redirecting of edges entering the
1582 loop from outside would decrease effectiveness of some of the
1583 following optimizations, so prevent this. */
1584 if (may_be_loop_header
1585 && !(e->flags & EDGE_DFS_BACK))
1586 {
1587 ei_next (i: &ei);
1588 continue;
1589 }
1590
1591 for (i = 0; i < reg_use_count; i++)
1592 {
1593 rtx reg_used = reg_use_table[i];
1594 unsigned int regno = REGNO (reg_used);
1595 basic_block dest, old_dest;
1596 struct cprop_expr *set;
1597 rtx src, new_rtx;
1598
1599 set = find_bypass_set (regno, bb: e->src->index);
1600
1601 if (! set)
1602 continue;
1603
1604 /* Check the data flow is valid after edge insertions. */
1605 if (e->insns.r && reg_killed_on_edge (reg: reg_used, e))
1606 continue;
1607
1608 src = SET_SRC (pc_set (jump));
1609
1610 if (setcc != NULL)
1611 src = simplify_replace_rtx (src,
1612 SET_DEST (PATTERN (setcc)),
1613 SET_SRC (PATTERN (setcc)));
1614
1615 new_rtx = simplify_replace_rtx (src, reg_used, set->src);
1616
1617 /* Jump bypassing may have already placed instructions on
1618 edges of the CFG. We can't bypass an outgoing edge that
1619 has instructions associated with it, as these insns won't
1620 get executed if the incoming edge is redirected. */
1621 if (new_rtx == pc_rtx)
1622 {
1623 edest = FALLTHRU_EDGE (bb);
1624 dest = edest->insns.r ? NULL : edest->dest;
1625 }
1626 else if (GET_CODE (new_rtx) == LABEL_REF)
1627 {
1628 dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0));
1629 /* Don't bypass edges containing instructions. */
1630 if (dest)
1631 {
1632 edest = find_edge (bb, dest);
1633 if (edest && edest->insns.r)
1634 dest = NULL;
1635 }
1636 }
1637 else
1638 dest = NULL;
1639
1640 /* Avoid unification of the edge with other edges from original
1641 branch. We would end up emitting the instruction on "both"
1642 edges. */
1643 if (dest && setcc && find_edge (e->src, dest))
1644 dest = NULL;
1645
1646 old_dest = e->dest;
1647 if (dest != NULL
1648 && dest != old_dest
1649 && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1650 {
1651 redirect_edge_and_branch_force (e, dest);
1652
1653 /* Copy the register setter to the redirected edge. */
1654 if (setcc)
1655 {
1656 rtx pat = PATTERN (insn: setcc);
1657 insert_insn_on_edge (copy_insn (pat), e);
1658 }
1659
1660 if (dump_file != NULL)
1661 {
1662 fprintf (stream: dump_file, format: "JUMP-BYPASS: Proved reg %d "
1663 "in jump_insn %d equals constant ",
1664 regno, INSN_UID (insn: jump));
1665 print_rtl (dump_file, set->src);
1666 fprintf (stream: dump_file, format: "\n\t when BB %d is entered from "
1667 "BB %d. Redirect edge %d->%d to %d.\n",
1668 old_dest->index, e->src->index, e->src->index,
1669 old_dest->index, dest->index);
1670 }
1671 change = true;
1672 removed_p = true;
1673 break;
1674 }
1675 }
1676 if (!removed_p)
1677 ei_next (i: &ei);
1678 }
1679 return change;
1680}
1681
1682/* Find basic blocks with more than one predecessor that only contain a
1683 single conditional jump. If the result of the comparison is known at
1684 compile-time from any incoming edge, redirect that edge to the
1685 appropriate target. Return nonzero if a change was made.
1686
1687 This function is now mis-named, because we also handle indirect jumps. */
1688
1689static bool
1690bypass_conditional_jumps (void)
1691{
1692 basic_block bb;
1693 bool changed;
1694 rtx_insn *setcc;
1695 rtx_insn *insn;
1696 rtx dest;
1697
1698 /* Note we start at block 1. */
1699 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1700 return false;
1701
1702 mark_dfs_back_edges ();
1703
1704 changed = false;
1705 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
1706 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1707 {
1708 /* Check for more than one predecessor. */
1709 if (!single_pred_p (bb))
1710 {
1711 setcc = NULL;
1712 FOR_BB_INSNS (bb, insn)
1713 if (DEBUG_INSN_P (insn))
1714 continue;
1715 else if (NONJUMP_INSN_P (insn))
1716 {
1717 if (setcc)
1718 break;
1719 if (GET_CODE (PATTERN (insn)) != SET)
1720 break;
1721
1722 dest = SET_DEST (PATTERN (insn));
1723 if (REG_P (dest))
1724 setcc = insn;
1725 else
1726 break;
1727 }
1728 else if (JUMP_P (insn))
1729 {
1730 if ((any_condjump_p (insn) || computed_jump_p (insn))
1731 && onlyjump_p (insn))
1732 if (bypass_block (bb, setcc, jump: insn))
1733 changed = true;
1734 break;
1735 }
1736 else if (INSN_P (insn))
1737 break;
1738 }
1739 }
1740
1741 /* If we bypassed any register setting insns, we inserted a
1742 copy on the redirected edge. These need to be committed. */
1743 if (changed)
1744 commit_edge_insertions ();
1745
1746 return changed;
1747}
1748
1749/* Main function for the CPROP pass. */
1750
1751static bool
1752one_cprop_pass (void)
1753{
1754 bool changed = false;
1755 int i;
1756
1757 /* Return if there's nothing to do, or it is too expensive. */
1758 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
1759 || gcse_or_cprop_is_too_expensive (_ ("const/copy propagation disabled")))
1760 return false;
1761
1762 global_const_prop_count = local_const_prop_count = 0;
1763 global_copy_prop_count = local_copy_prop_count = 0;
1764
1765 bytes_used = 0;
1766 gcc_obstack_init (&cprop_obstack);
1767
1768 /* Do a local const/copy propagation pass first. The global pass
1769 only handles global opportunities.
1770 If the local pass changes something, remove any unreachable blocks
1771 because the CPROP global dataflow analysis may get into infinite
1772 loops for CFGs with unreachable blocks.
1773
1774 FIXME: This local pass should not be necessary after CSE (but for
1775 some reason it still is). It is also (proven) not necessary
1776 to run the local pass right after FWPWOP.
1777
1778 FIXME: The global analysis would not get into infinite loops if it
1779 would use the DF solver (via df_simple_dataflow) instead of
1780 the solver implemented in this file. */
1781 if (local_cprop_pass ())
1782 changed = true;
1783
1784 if (changed)
1785 delete_unreachable_blocks ();
1786
1787 /* Determine implicit sets. This may change the CFG (split critical
1788 edges if that exposes an implicit set).
1789 Note that find_implicit_sets() does not rely on up-to-date DF caches
1790 so that we do not have to re-run df_analyze() even if local CPROP
1791 changed something.
1792 ??? This could run earlier so that any uncovered implicit sets
1793 sets could be exploited in local_cprop_pass() also. Later. */
1794 if (find_implicit_sets ())
1795 changed = true;
1796
1797 /* If local_cprop_pass() or find_implicit_sets() changed something,
1798 run df_analyze() to bring all insn caches up-to-date, and to take
1799 new basic blocks from edge splitting on the DF radar.
1800 NB: This also runs the fast DCE pass, because execute_rtl_cprop
1801 sets DF_LR_RUN_DCE. */
1802 if (changed)
1803 df_analyze ();
1804
1805 /* Initialize implicit_set_indexes array. */
1806 implicit_set_indexes = XNEWVEC (int, last_basic_block_for_fn (cfun));
1807 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
1808 implicit_set_indexes[i] = -1;
1809
1810 alloc_hash_table (table: &set_hash_table);
1811 compute_hash_table (table: &set_hash_table);
1812
1813 /* Free implicit_sets before peak usage. */
1814 free (ptr: implicit_sets);
1815 implicit_sets = NULL;
1816
1817 if (dump_file)
1818 dump_hash_table (file: dump_file, name: "SET", table: &set_hash_table);
1819 if (set_hash_table.n_elems > 0)
1820 {
1821 basic_block bb;
1822 auto_vec<rtx_insn *> uncond_traps;
1823
1824 alloc_cprop_mem (last_basic_block_for_fn (cfun),
1825 n_sets: set_hash_table.n_elems);
1826 compute_cprop_data ();
1827
1828 free (ptr: implicit_set_indexes);
1829 implicit_set_indexes = NULL;
1830
1831 /* Allocate vars to track sets of regs. */
1832 reg_set_bitmap = ALLOC_REG_SET (NULL);
1833
1834 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
1835 EXIT_BLOCK_PTR_FOR_FN (cfun),
1836 next_bb)
1837 {
1838 bool seen_uncond_trap = false;
1839 rtx_insn *insn;
1840
1841 /* Reset tables used to keep track of what's still valid [since
1842 the start of the block]. */
1843 reset_opr_set_tables ();
1844
1845 FOR_BB_INSNS (bb, insn)
1846 if (INSN_P (insn))
1847 {
1848 bool was_uncond_trap
1849 = (GET_CODE (PATTERN (insn)) == TRAP_IF
1850 && XEXP (PATTERN (insn), 0) == const1_rtx);
1851
1852 if (cprop_insn (insn))
1853 changed = true;
1854
1855 /* Keep track of everything modified by this insn. */
1856 /* ??? Need to be careful w.r.t. mods done to INSN.
1857 Don't call mark_oprs_set if we turned the
1858 insn into a NOTE, or deleted the insn. */
1859 if (! NOTE_P (insn) && ! insn->deleted ())
1860 mark_oprs_set (insn);
1861
1862 if (!was_uncond_trap
1863 && GET_CODE (PATTERN (insn)) == TRAP_IF
1864 && XEXP (PATTERN (insn), 0) == const1_rtx)
1865 {
1866 /* If we have already seen an unconditional trap
1867 earlier, the rest of the bb is going to be removed
1868 as unreachable. Just turn it into a note, so that
1869 RTL verification doesn't complain about it before
1870 it is finally removed. */
1871 if (seen_uncond_trap)
1872 set_insn_deleted (insn);
1873 else
1874 {
1875 seen_uncond_trap = true;
1876 uncond_traps.safe_push (obj: insn);
1877 }
1878 }
1879 }
1880 }
1881
1882 /* Make sure bypass_conditional_jumps will ignore not just its new
1883 basic blocks, but also the ones after unconditional traps (those are
1884 unreachable and will be eventually removed as such). */
1885 bypass_last_basic_block = last_basic_block_for_fn (cfun);
1886
1887 while (!uncond_traps.is_empty ())
1888 {
1889 rtx_insn *insn = uncond_traps.pop ();
1890 basic_block to_split = BLOCK_FOR_INSN (insn);
1891 remove_edge (split_block (to_split, insn));
1892 emit_barrier_after_bb (bb: to_split);
1893 }
1894
1895 if (bypass_conditional_jumps ())
1896 changed = true;
1897
1898 FREE_REG_SET (reg_set_bitmap);
1899 free_cprop_mem ();
1900 }
1901 else
1902 {
1903 free (ptr: implicit_set_indexes);
1904 implicit_set_indexes = NULL;
1905 }
1906
1907 free_hash_table (table: &set_hash_table);
1908 obstack_free (&cprop_obstack, NULL);
1909
1910 if (dump_file)
1911 {
1912 fprintf (stream: dump_file, format: "CPROP of %s, %d basic blocks, %d bytes needed, ",
1913 current_function_name (), n_basic_blocks_for_fn (cfun),
1914 bytes_used);
1915 fprintf (stream: dump_file, format: "%d local const props, %d local copy props, ",
1916 local_const_prop_count, local_copy_prop_count);
1917 fprintf (stream: dump_file, format: "%d global const props, %d global copy props\n\n",
1918 global_const_prop_count, global_copy_prop_count);
1919 }
1920
1921 return changed;
1922}
1923
1924/* All the passes implemented in this file. Each pass has its
1925 own gate and execute function, and at the end of the file a
1926 pass definition for passes.cc.
1927
1928 We do not construct an accurate cfg in functions which call
1929 setjmp, so none of these passes runs if the function calls
1930 setjmp.
1931 FIXME: Should just handle setjmp via REG_SETJMP notes. */
1932
1933static unsigned int
1934execute_rtl_cprop (void)
1935{
1936 int changed;
1937 delete_unreachable_blocks ();
1938 df_set_flags (DF_LR_RUN_DCE);
1939 df_analyze ();
1940 changed = one_cprop_pass ();
1941 flag_rerun_cse_after_global_opts |= changed;
1942 if (changed)
1943 cleanup_cfg (CLEANUP_CFG_CHANGED);
1944 return 0;
1945}
1946
1947namespace {
1948
1949const pass_data pass_data_rtl_cprop =
1950{
1951 .type: RTL_PASS, /* type */
1952 .name: "cprop", /* name */
1953 .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
1954 .tv_id: TV_CPROP, /* tv_id */
1955 PROP_cfglayout, /* properties_required */
1956 .properties_provided: 0, /* properties_provided */
1957 .properties_destroyed: 0, /* properties_destroyed */
1958 .todo_flags_start: 0, /* todo_flags_start */
1959 TODO_df_finish, /* todo_flags_finish */
1960};
1961
1962class pass_rtl_cprop : public rtl_opt_pass
1963{
1964public:
1965 pass_rtl_cprop (gcc::context *ctxt)
1966 : rtl_opt_pass (pass_data_rtl_cprop, ctxt)
1967 {}
1968
1969 /* opt_pass methods: */
1970 opt_pass * clone () final override { return new pass_rtl_cprop (m_ctxt); }
1971 bool gate (function *fun) final override
1972 {
1973 return optimize > 0 && flag_gcse
1974 && !fun->calls_setjmp
1975 && dbg_cnt (index: cprop);
1976 }
1977
1978 unsigned int execute (function *) final override
1979 {
1980 return execute_rtl_cprop ();
1981 }
1982
1983}; // class pass_rtl_cprop
1984
1985} // anon namespace
1986
1987rtl_opt_pass *
1988make_pass_rtl_cprop (gcc::context *ctxt)
1989{
1990 return new pass_rtl_cprop (ctxt);
1991}
1992

source code of gcc/cprop.cc