1/* Global constant/copy propagation for RTL.
2 Copyright (C) 1997-2017 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 "cfghooks.h"
26#include "df.h"
27#include "insn-config.h"
28#include "memmodel.h"
29#include "emit-rtl.h"
30#include "recog.h"
31#include "diagnostic-core.h"
32#include "toplev.h"
33#include "cfgrtl.h"
34#include "cfganal.h"
35#include "lcm.h"
36#include "cfgcleanup.h"
37#include "params.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 nonzero if register X is unchanged from INSN to the end
147 of INSN's basic block. */
148
149static int
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), 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 (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 (dest)
276 && reg_available_p (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 (src)
301 && src != dest
302 && reg_available_p (src, insn))
303 || cprop_constant_p (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 (pat, insn, table, 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 (x, insn, table, 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 (file, "%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 (file, "Index %d (hash value %d)\n ",
360 expr->bitmap_index, hash_val[i]);
361 print_rtl (file, expr->dest);
362 fprintf (file, " := ");
363 print_rtl (file, expr->src);
364 fprintf (file, "\n");
365 }
366
367 fprintf (file, "\n");
368
369 free (flat_table);
370 free (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 (implicit_sets[bb->index], BB_HEAD (bb), table, 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 (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 (table->table, 0, 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, 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 nonzero if the register X has not been set yet [since the
522 start of the basic block containing INSN]. */
523
524static int
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 (cprop_avloc);
571 sbitmap_vector_free (cprop_kill);
572 sbitmap_vector_free (cprop_avin);
573 sbitmap_vector_free (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 (kill[DF_REF_BB (def)->index], 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 (kill[DF_REF_BB (def)->index], 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 (comp[BLOCK_FOR_INSN (occr->insn)->index], 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 (cprop_kill, cprop_avloc, &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 (cprop_avin[bb->index], 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 (&XEXP (x, i), data);
718 }
719 else if (fmt[i] == 'E')
720 for (j = 0; j < XVECLEN (x, i); j++)
721 find_used_regs (&XVECEXP (x, i, j), data);
722 }
723}
724
725/* Try to replace all uses of FROM in INSN with TO.
726 Return nonzero if successful. */
727
728static int
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 int success = 0;
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 (set, 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 (set, speed) > old_cost)
762 {
763 cancel_changes (0);
764 return false;
765 }
766
767
768 if (num_changes_pending () && apply_change_group ())
769 success = 1;
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 = 1;
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 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
801 }
802
803 if (set && MEM_P (SET_DEST (set)) && reg_mentioned_p (from, SET_DEST (set)))
804 {
805 /* Registers can also appear as uses in SET_DEST if it is a MEM.
806 We could perhaps try this for multiple SETs, but it probably
807 won't buy us anything. */
808 rtx dest = simplify_replace_rtx (SET_DEST (set), from, to);
809
810 if (!rtx_equal_p (dest, SET_DEST (set))
811 && validate_change (insn, &SET_DEST (set), dest, 0))
812 success = 1;
813 }
814
815 /* REG_EQUAL may get simplified into register.
816 We don't allow that. Remove that note. This code ought
817 not to happen, because previous code ought to synthesize
818 reg-reg move, but be on the safe side. */
819 if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0)))
820 remove_note (insn, note);
821
822 return success;
823}
824
825/* Find a set of REGNOs that are available on entry to INSN's block. If found,
826 SET_RET[0] will be assigned a set with a register source and SET_RET[1] a
827 set with a constant source. If not found the corresponding entry is set to
828 NULL. */
829
830static void
831find_avail_set (int regno, rtx_insn *insn, struct cprop_expr *set_ret[2])
832{
833 set_ret[0] = set_ret[1] = NULL;
834
835 /* Loops are not possible here. To get a loop we would need two sets
836 available at the start of the block containing INSN. i.e. we would
837 need two sets like this available at the start of the block:
838
839 (set (reg X) (reg Y))
840 (set (reg Y) (reg X))
841
842 This can not happen since the set of (reg Y) would have killed the
843 set of (reg X) making it unavailable at the start of this block. */
844 while (1)
845 {
846 rtx src;
847 struct cprop_expr *set = lookup_set (regno, &set_hash_table);
848
849 /* Find a set that is available at the start of the block
850 which contains INSN. */
851 while (set)
852 {
853 if (bitmap_bit_p (cprop_avin[BLOCK_FOR_INSN (insn)->index],
854 set->bitmap_index))
855 break;
856 set = next_set (regno, set);
857 }
858
859 /* If no available set was found we've reached the end of the
860 (possibly empty) copy chain. */
861 if (set == 0)
862 break;
863
864 src = set->src;
865
866 /* We know the set is available.
867 Now check that SRC is locally anticipatable (i.e. none of the
868 source operands have changed since the start of the block).
869
870 If the source operand changed, we may still use it for the next
871 iteration of this loop, but we may not use it for substitutions. */
872
873 if (cprop_constant_p (src))
874 set_ret[1] = set;
875 else if (reg_not_set_p (src, insn))
876 set_ret[0] = set;
877
878 /* If the source of the set is anything except a register, then
879 we have reached the end of the copy chain. */
880 if (! REG_P (src))
881 break;
882
883 /* Follow the copy chain, i.e. start another iteration of the loop
884 and see if we have an available copy into SRC. */
885 regno = REGNO (src);
886 }
887}
888
889/* Subroutine of cprop_insn that tries to propagate constants into
890 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
891 it is the instruction that immediately precedes JUMP, and must be a
892 single SET of a register. FROM is what we will try to replace,
893 SRC is the constant we will try to substitute for it. Return nonzero
894 if a change was made. */
895
896static int
897cprop_jump (basic_block bb, rtx_insn *setcc, rtx_insn *jump, rtx from, rtx src)
898{
899 rtx new_rtx, set_src, note_src;
900 rtx set = pc_set (jump);
901 rtx note = find_reg_equal_equiv_note (jump);
902
903 if (note)
904 {
905 note_src = XEXP (note, 0);
906 if (GET_CODE (note_src) == EXPR_LIST)
907 note_src = NULL_RTX;
908 }
909 else note_src = NULL_RTX;
910
911 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
912 set_src = note_src ? note_src : SET_SRC (set);
913
914 /* First substitute the SETCC condition into the JUMP instruction,
915 then substitute that given values into this expanded JUMP. */
916 if (setcc != NULL_RTX
917 && !modified_between_p (from, setcc, jump)
918 && !modified_between_p (src, setcc, jump))
919 {
920 rtx setcc_src;
921 rtx setcc_set = single_set (setcc);
922 rtx setcc_note = find_reg_equal_equiv_note (setcc);
923 setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST)
924 ? XEXP (setcc_note, 0) : SET_SRC (setcc_set);
925 set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set),
926 setcc_src);
927 }
928 else
929 setcc = NULL;
930
931 new_rtx = simplify_replace_rtx (set_src, from, src);
932
933 /* If no simplification can be made, then try the next register. */
934 if (rtx_equal_p (new_rtx, SET_SRC (set)))
935 return 0;
936
937 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
938 if (new_rtx == pc_rtx)
939 delete_insn (jump);
940 else
941 {
942 /* Ensure the value computed inside the jump insn to be equivalent
943 to one computed by setcc. */
944 if (setcc && modified_in_p (new_rtx, setcc))
945 return 0;
946 if (! validate_unshare_change (jump, &SET_SRC (set), new_rtx, 0))
947 {
948 /* When (some) constants are not valid in a comparison, and there
949 are two registers to be replaced by constants before the entire
950 comparison can be folded into a constant, we need to keep
951 intermediate information in REG_EQUAL notes. For targets with
952 separate compare insns, such notes are added by try_replace_reg.
953 When we have a combined compare-and-branch instruction, however,
954 we need to attach a note to the branch itself to make this
955 optimization work. */
956
957 if (!rtx_equal_p (new_rtx, note_src))
958 set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new_rtx));
959 return 0;
960 }
961
962 /* Remove REG_EQUAL note after simplification. */
963 if (note_src)
964 remove_note (jump, note);
965 }
966
967 /* Delete the cc0 setter. */
968 if (HAVE_cc0 && setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
969 delete_insn (setcc);
970
971 global_const_prop_count++;
972 if (dump_file != NULL)
973 {
974 fprintf (dump_file,
975 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with "
976 "constant ", REGNO (from), INSN_UID (jump));
977 print_rtl (dump_file, src);
978 fprintf (dump_file, "\n");
979 }
980 purge_dead_edges (bb);
981
982 /* If a conditional jump has been changed into unconditional jump, remove
983 the jump and make the edge fallthru - this is always called in
984 cfglayout mode. */
985 if (new_rtx != pc_rtx && simplejump_p (jump))
986 {
987 edge e;
988 edge_iterator ei;
989
990 FOR_EACH_EDGE (e, ei, bb->succs)
991 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
992 && BB_HEAD (e->dest) == JUMP_LABEL (jump))
993 {
994 e->flags |= EDGE_FALLTHRU;
995 break;
996 }
997 delete_insn (jump);
998 }
999
1000 return 1;
1001}
1002
1003/* Subroutine of cprop_insn that tries to propagate constants. FROM is what
1004 we will try to replace, SRC is the constant we will try to substitute for
1005 it and INSN is the instruction where this will be happening. */
1006
1007static int
1008constprop_register (rtx from, rtx src, rtx_insn *insn)
1009{
1010 rtx sset;
1011
1012 /* Check for reg or cc0 setting instructions followed by
1013 conditional branch instructions first. */
1014 if ((sset = single_set (insn)) != NULL
1015 && NEXT_INSN (insn)
1016 && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
1017 {
1018 rtx dest = SET_DEST (sset);
1019 if ((REG_P (dest) || CC0_P (dest))
1020 && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn),
1021 from, src))
1022 return 1;
1023 }
1024
1025 /* Handle normal insns next. */
1026 if (NONJUMP_INSN_P (insn) && try_replace_reg (from, src, insn))
1027 return 1;
1028
1029 /* Try to propagate a CONST_INT into a conditional jump.
1030 We're pretty specific about what we will handle in this
1031 code, we can extend this as necessary over time.
1032
1033 Right now the insn in question must look like
1034 (set (pc) (if_then_else ...)) */
1035 else if (any_condjump_p (insn) && onlyjump_p (insn))
1036 return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, src);
1037 return 0;
1038}
1039
1040/* Perform constant and copy propagation on INSN.
1041 Return nonzero if a change was made. */
1042
1043static int
1044cprop_insn (rtx_insn *insn)
1045{
1046 unsigned i;
1047 int changed = 0, changed_this_round;
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 (&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 (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);
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 (src_cst)
1083 && constprop_register (reg_used, src_cst, insn))
1084 {
1085 changed_this_round = changed = 1;
1086 global_const_prop_count++;
1087 if (dump_file != NULL)
1088 {
1089 fprintf (dump_file,
1090 "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
1091 fprintf (dump_file, "insn %d with constant ",
1092 INSN_UID (insn));
1093 print_rtl (dump_file, src_cst);
1094 fprintf (dump_file, "\n");
1095 }
1096 if (insn->deleted ())
1097 return 1;
1098 }
1099 /* Copy propagation. */
1100 else if (src_reg && cprop_reg_p (src_reg)
1101 && REGNO (src_reg) != regno
1102 && try_replace_reg (reg_used, src_reg, insn))
1103 {
1104 changed_this_round = changed = 1;
1105 global_copy_prop_count++;
1106 if (dump_file != NULL)
1107 {
1108 fprintf (dump_file,
1109 "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1110 regno, INSN_UID (insn));
1111 fprintf (dump_file, " with reg %d\n", REGNO (src_reg));
1112 }
1113
1114 /* The original insn setting reg_used may or may not now be
1115 deletable. We leave the deletion to DCE. */
1116 /* FIXME: If it turns out that the insn isn't deletable,
1117 then we may have unnecessarily extended register lifetimes
1118 and made things worse. */
1119 }
1120 }
1121 }
1122 /* If try_replace_reg simplified the insn, the regs found by find_used_regs
1123 may not be valid anymore. Start over. */
1124 while (changed_this_round);
1125
1126 if (changed && DEBUG_INSN_P (insn))
1127 return 0;
1128
1129 return changed;
1130}
1131
1132/* Like find_used_regs, but avoid recording uses that appear in
1133 input-output contexts such as zero_extract or pre_dec. This
1134 restricts the cases we consider to those for which local cprop
1135 can legitimately make replacements. */
1136
1137static void
1138local_cprop_find_used_regs (rtx *xptr, void *data)
1139{
1140 rtx x = *xptr;
1141
1142 if (x == 0)
1143 return;
1144
1145 switch (GET_CODE (x))
1146 {
1147 case ZERO_EXTRACT:
1148 case SIGN_EXTRACT:
1149 case STRICT_LOW_PART:
1150 return;
1151
1152 case PRE_DEC:
1153 case PRE_INC:
1154 case POST_DEC:
1155 case POST_INC:
1156 case PRE_MODIFY:
1157 case POST_MODIFY:
1158 /* Can only legitimately appear this early in the context of
1159 stack pushes for function arguments, but handle all of the
1160 codes nonetheless. */
1161 return;
1162
1163 case SUBREG:
1164 if (read_modify_subreg_p (x))
1165 return;
1166 break;
1167
1168 default:
1169 break;
1170 }
1171
1172 find_used_regs (xptr, data);
1173}
1174
1175/* Try to perform local const/copy propagation on X in INSN. */
1176
1177static bool
1178do_local_cprop (rtx x, rtx_insn *insn)
1179{
1180 rtx newreg = NULL, newcnst = NULL;
1181
1182 /* Rule out USE instructions and ASM statements as we don't want to
1183 change the hard registers mentioned. */
1184 if (REG_P (x)
1185 && (cprop_reg_p (x)
1186 || (GET_CODE (PATTERN (insn)) != USE
1187 && asm_noperands (PATTERN (insn)) < 0)))
1188 {
1189 cselib_val *val = cselib_lookup (x, GET_MODE (x), 0, VOIDmode);
1190 struct elt_loc_list *l;
1191
1192 if (!val)
1193 return false;
1194 for (l = val->locs; l; l = l->next)
1195 {
1196 rtx this_rtx = l->loc;
1197 rtx note;
1198
1199 if (cprop_constant_p (this_rtx))
1200 newcnst = this_rtx;
1201 if (cprop_reg_p (this_rtx)
1202 /* Don't copy propagate if it has attached REG_EQUIV note.
1203 At this point this only function parameters should have
1204 REG_EQUIV notes and if the argument slot is used somewhere
1205 explicitly, it means address of parameter has been taken,
1206 so we should not extend the lifetime of the pseudo. */
1207 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
1208 || ! MEM_P (XEXP (note, 0))))
1209 newreg = this_rtx;
1210 }
1211 if (newcnst && constprop_register (x, newcnst, insn))
1212 {
1213 if (dump_file != NULL)
1214 {
1215 fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ",
1216 REGNO (x));
1217 fprintf (dump_file, "insn %d with constant ",
1218 INSN_UID (insn));
1219 print_rtl (dump_file, newcnst);
1220 fprintf (dump_file, "\n");
1221 }
1222 local_const_prop_count++;
1223 return true;
1224 }
1225 else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
1226 {
1227 if (dump_file != NULL)
1228 {
1229 fprintf (dump_file,
1230 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1231 REGNO (x), INSN_UID (insn));
1232 fprintf (dump_file, " with reg %d\n", REGNO (newreg));
1233 }
1234 local_copy_prop_count++;
1235 return true;
1236 }
1237 }
1238 return false;
1239}
1240
1241/* Do local const/copy propagation (i.e. within each basic block). */
1242
1243static int
1244local_cprop_pass (void)
1245{
1246 basic_block bb;
1247 rtx_insn *insn;
1248 bool changed = false;
1249 unsigned i;
1250
1251 auto_vec<rtx_insn *> uncond_traps;
1252
1253 cselib_init (0);
1254 FOR_EACH_BB_FN (bb, cfun)
1255 {
1256 FOR_BB_INSNS (bb, insn)
1257 {
1258 if (INSN_P (insn))
1259 {
1260 bool was_uncond_trap
1261 = (GET_CODE (PATTERN (insn)) == TRAP_IF
1262 && XEXP (PATTERN (insn), 0) == const1_rtx);
1263 rtx note = find_reg_equal_equiv_note (insn);
1264 do
1265 {
1266 reg_use_count = 0;
1267 note_uses (&PATTERN (insn), local_cprop_find_used_regs,
1268 NULL);
1269 if (note)
1270 local_cprop_find_used_regs (&XEXP (note, 0), NULL);
1271
1272 for (i = 0; i < reg_use_count; i++)
1273 {
1274 if (do_local_cprop (reg_use_table[i], insn))
1275 {
1276 if (!DEBUG_INSN_P (insn))
1277 changed = true;
1278 break;
1279 }
1280 }
1281 if (!was_uncond_trap
1282 && GET_CODE (PATTERN (insn)) == TRAP_IF
1283 && XEXP (PATTERN (insn), 0) == const1_rtx)
1284 {
1285 uncond_traps.safe_push (insn);
1286 break;
1287 }
1288 if (insn->deleted ())
1289 break;
1290 }
1291 while (i < reg_use_count);
1292 }
1293 cselib_process_insn (insn);
1294 }
1295
1296 /* Forget everything at the end of a basic block. */
1297 cselib_clear_table ();
1298 }
1299
1300 cselib_finish ();
1301
1302 while (!uncond_traps.is_empty ())
1303 {
1304 rtx_insn *insn = uncond_traps.pop ();
1305 basic_block to_split = BLOCK_FOR_INSN (insn);
1306 remove_edge (split_block (to_split, insn));
1307 emit_barrier_after_bb (to_split);
1308 }
1309
1310 return changed;
1311}
1312
1313/* Similar to get_condition, only the resulting condition must be
1314 valid at JUMP, instead of at EARLIEST.
1315
1316 This differs from noce_get_condition in ifcvt.c in that we prefer not to
1317 settle for the condition variable in the jump instruction being integral.
1318 We prefer to be able to record the value of a user variable, rather than
1319 the value of a temporary used in a condition. This could be solved by
1320 recording the value of *every* register scanned by canonicalize_condition,
1321 but this would require some code reorganization. */
1322
1323rtx
1324fis_get_condition (rtx_insn *jump)
1325{
1326 return get_condition (jump, NULL, false, true);
1327}
1328
1329/* Check the comparison COND to see if we can safely form an implicit
1330 set from it. */
1331
1332static bool
1333implicit_set_cond_p (const_rtx cond)
1334{
1335 machine_mode mode;
1336 rtx cst;
1337
1338 /* COND must be either an EQ or NE comparison. */
1339 if (GET_CODE (cond) != EQ && GET_CODE (cond) != NE)
1340 return false;
1341
1342 /* The first operand of COND must be a register we can propagate. */
1343 if (!cprop_reg_p (XEXP (cond, 0)))
1344 return false;
1345
1346 /* The second operand of COND must be a suitable constant. */
1347 mode = GET_MODE (XEXP (cond, 0));
1348 cst = XEXP (cond, 1);
1349
1350 /* We can't perform this optimization if either operand might be or might
1351 contain a signed zero. */
1352 if (HONOR_SIGNED_ZEROS (mode))
1353 {
1354 /* It is sufficient to check if CST is or contains a zero. We must
1355 handle float, complex, and vector. If any subpart is a zero, then
1356 the optimization can't be performed. */
1357 /* ??? The complex and vector checks are not implemented yet. We just
1358 always return zero for them. */
1359 if (CONST_DOUBLE_AS_FLOAT_P (cst)
1360 && real_equal (CONST_DOUBLE_REAL_VALUE (cst), &dconst0))
1361 return 0;
1362 else
1363 return 0;
1364 }
1365
1366 return cprop_constant_p (cst);
1367}
1368
1369/* Find the implicit sets of a function. An "implicit set" is a constraint
1370 on the value of a variable, implied by a conditional jump. For example,
1371 following "if (x == 2)", the then branch may be optimized as though the
1372 conditional performed an "explicit set", in this example, "x = 2". This
1373 function records the set patterns that are implicit at the start of each
1374 basic block.
1375
1376 If an implicit set is found but the set is implicit on a critical edge,
1377 this critical edge is split.
1378
1379 Return true if the CFG was modified, false otherwise. */
1380
1381static bool
1382find_implicit_sets (void)
1383{
1384 basic_block bb, dest;
1385 rtx cond, new_rtx;
1386 unsigned int count = 0;
1387 bool edges_split = false;
1388 size_t implicit_sets_size = last_basic_block_for_fn (cfun) + 10;
1389
1390 implicit_sets = XCNEWVEC (rtx, implicit_sets_size);
1391
1392 FOR_EACH_BB_FN (bb, cfun)
1393 {
1394 /* Check for more than one successor. */
1395 if (EDGE_COUNT (bb->succs) <= 1)
1396 continue;
1397
1398 cond = fis_get_condition (BB_END (bb));
1399
1400 /* If no condition is found or if it isn't of a suitable form,
1401 ignore it. */
1402 if (! cond || ! implicit_set_cond_p (cond))
1403 continue;
1404
1405 dest = GET_CODE (cond) == EQ
1406 ? BRANCH_EDGE (bb)->dest : FALLTHRU_EDGE (bb)->dest;
1407
1408 /* If DEST doesn't go anywhere, ignore it. */
1409 if (! dest || dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1410 continue;
1411
1412 /* We have found a suitable implicit set. Try to record it now as
1413 a SET in DEST. If DEST has more than one predecessor, the edge
1414 between BB and DEST is a critical edge and we must split it,
1415 because we can only record one implicit set per DEST basic block. */
1416 if (! single_pred_p (dest))
1417 {
1418 dest = split_edge (find_edge (bb, dest));
1419 edges_split = true;
1420 }
1421
1422 if (implicit_sets_size <= (size_t) dest->index)
1423 {
1424 size_t old_implicit_sets_size = implicit_sets_size;
1425 implicit_sets_size *= 2;
1426 implicit_sets = XRESIZEVEC (rtx, implicit_sets, implicit_sets_size);
1427 memset (implicit_sets + old_implicit_sets_size, 0,
1428 (implicit_sets_size - old_implicit_sets_size) * sizeof (rtx));
1429 }
1430
1431 new_rtx = gen_rtx_SET (XEXP (cond, 0), XEXP (cond, 1));
1432 implicit_sets[dest->index] = new_rtx;
1433 if (dump_file)
1434 {
1435 fprintf (dump_file, "Implicit set of reg %d in ",
1436 REGNO (XEXP (cond, 0)));
1437 fprintf (dump_file, "basic block %d\n", dest->index);
1438 }
1439 count++;
1440 }
1441
1442 if (dump_file)
1443 fprintf (dump_file, "Found %d implicit sets\n", count);
1444
1445 /* Confess our sins. */
1446 return edges_split;
1447}
1448
1449/* Bypass conditional jumps. */
1450
1451/* The value of last_basic_block at the beginning of the jump_bypass
1452 pass. The use of redirect_edge_and_branch_force may introduce new
1453 basic blocks, but the data flow analysis is only valid for basic
1454 block indices less than bypass_last_basic_block. */
1455
1456static int bypass_last_basic_block;
1457
1458/* Find a set of REGNO to a constant that is available at the end of basic
1459 block BB. Return NULL if no such set is found. Based heavily upon
1460 find_avail_set. */
1461
1462static struct cprop_expr *
1463find_bypass_set (int regno, int bb)
1464{
1465 struct cprop_expr *result = 0;
1466
1467 for (;;)
1468 {
1469 rtx src;
1470 struct cprop_expr *set = lookup_set (regno, &set_hash_table);
1471
1472 while (set)
1473 {
1474 if (bitmap_bit_p (cprop_avout[bb], set->bitmap_index))
1475 break;
1476 set = next_set (regno, set);
1477 }
1478
1479 if (set == 0)
1480 break;
1481
1482 src = set->src;
1483 if (cprop_constant_p (src))
1484 result = set;
1485
1486 if (! REG_P (src))
1487 break;
1488
1489 regno = REGNO (src);
1490 }
1491 return result;
1492}
1493
1494/* Subroutine of bypass_block that checks whether a pseudo is killed by
1495 any of the instructions inserted on an edge. Jump bypassing places
1496 condition code setters on CFG edges using insert_insn_on_edge. This
1497 function is required to check that our data flow analysis is still
1498 valid prior to commit_edge_insertions. */
1499
1500static bool
1501reg_killed_on_edge (const_rtx reg, const_edge e)
1502{
1503 rtx_insn *insn;
1504
1505 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
1506 if (INSN_P (insn) && reg_set_p (reg, insn))
1507 return true;
1508
1509 return false;
1510}
1511
1512/* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1513 basic block BB which has more than one predecessor. If not NULL, SETCC
1514 is the first instruction of BB, which is immediately followed by JUMP_INSN
1515 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1516 Returns nonzero if a change was made.
1517
1518 During the jump bypassing pass, we may place copies of SETCC instructions
1519 on CFG edges. The following routine must be careful to pay attention to
1520 these inserted insns when performing its transformations. */
1521
1522static int
1523bypass_block (basic_block bb, rtx_insn *setcc, rtx_insn *jump)
1524{
1525 rtx_insn *insn;
1526 rtx note;
1527 edge e, edest;
1528 int change;
1529 int may_be_loop_header = false;
1530 unsigned removed_p;
1531 unsigned i;
1532 edge_iterator ei;
1533
1534 insn = (setcc != NULL) ? setcc : jump;
1535
1536 /* Determine set of register uses in INSN. */
1537 reg_use_count = 0;
1538 note_uses (&PATTERN (insn), find_used_regs, NULL);
1539 note = find_reg_equal_equiv_note (insn);
1540 if (note)
1541 find_used_regs (&XEXP (note, 0), NULL);
1542
1543 if (current_loops)
1544 {
1545 /* If we are to preserve loop structure then do not bypass
1546 a loop header. This will either rotate the loop, create
1547 multiple entry loops or even irreducible regions. */
1548 if (bb == bb->loop_father->header)
1549 return 0;
1550 }
1551 else
1552 {
1553 FOR_EACH_EDGE (e, ei, bb->preds)
1554 if (e->flags & EDGE_DFS_BACK)
1555 {
1556 may_be_loop_header = true;
1557 break;
1558 }
1559 }
1560
1561 change = 0;
1562 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
1563 {
1564 removed_p = 0;
1565
1566 if (e->flags & EDGE_COMPLEX)
1567 {
1568 ei_next (&ei);
1569 continue;
1570 }
1571
1572 /* We can't redirect edges from new basic blocks. */
1573 if (e->src->index >= bypass_last_basic_block)
1574 {
1575 ei_next (&ei);
1576 continue;
1577 }
1578
1579 /* The irreducible loops created by redirecting of edges entering the
1580 loop from outside would decrease effectiveness of some of the
1581 following optimizations, so prevent this. */
1582 if (may_be_loop_header
1583 && !(e->flags & EDGE_DFS_BACK))
1584 {
1585 ei_next (&ei);
1586 continue;
1587 }
1588
1589 for (i = 0; i < reg_use_count; i++)
1590 {
1591 rtx reg_used = reg_use_table[i];
1592 unsigned int regno = REGNO (reg_used);
1593 basic_block dest, old_dest;
1594 struct cprop_expr *set;
1595 rtx src, new_rtx;
1596
1597 set = find_bypass_set (regno, e->src->index);
1598
1599 if (! set)
1600 continue;
1601
1602 /* Check the data flow is valid after edge insertions. */
1603 if (e->insns.r && reg_killed_on_edge (reg_used, e))
1604 continue;
1605
1606 src = SET_SRC (pc_set (jump));
1607
1608 if (setcc != NULL)
1609 src = simplify_replace_rtx (src,
1610 SET_DEST (PATTERN (setcc)),
1611 SET_SRC (PATTERN (setcc)));
1612
1613 new_rtx = simplify_replace_rtx (src, reg_used, set->src);
1614
1615 /* Jump bypassing may have already placed instructions on
1616 edges of the CFG. We can't bypass an outgoing edge that
1617 has instructions associated with it, as these insns won't
1618 get executed if the incoming edge is redirected. */
1619 if (new_rtx == pc_rtx)
1620 {
1621 edest = FALLTHRU_EDGE (bb);
1622 dest = edest->insns.r ? NULL : edest->dest;
1623 }
1624 else if (GET_CODE (new_rtx) == LABEL_REF)
1625 {
1626 dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0));
1627 /* Don't bypass edges containing instructions. */
1628 edest = find_edge (bb, dest);
1629 if (edest && edest->insns.r)
1630 dest = NULL;
1631 }
1632 else
1633 dest = NULL;
1634
1635 /* Avoid unification of the edge with other edges from original
1636 branch. We would end up emitting the instruction on "both"
1637 edges. */
1638 if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))
1639 && find_edge (e->src, dest))
1640 dest = NULL;
1641
1642 old_dest = e->dest;
1643 if (dest != NULL
1644 && dest != old_dest
1645 && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1646 {
1647 redirect_edge_and_branch_force (e, dest);
1648
1649 /* Copy the register setter to the redirected edge.
1650 Don't copy CC0 setters, as CC0 is dead after jump. */
1651 if (setcc)
1652 {
1653 rtx pat = PATTERN (setcc);
1654 if (!CC0_P (SET_DEST (pat)))
1655 insert_insn_on_edge (copy_insn (pat), e);
1656 }
1657
1658 if (dump_file != NULL)
1659 {
1660 fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
1661 "in jump_insn %d equals constant ",
1662 regno, INSN_UID (jump));
1663 print_rtl (dump_file, set->src);
1664 fprintf (dump_file, "\n\t when BB %d is entered from "
1665 "BB %d. Redirect edge %d->%d to %d.\n",
1666 old_dest->index, e->src->index, e->src->index,
1667 old_dest->index, dest->index);
1668 }
1669 change = 1;
1670 removed_p = 1;
1671 break;
1672 }
1673 }
1674 if (!removed_p)
1675 ei_next (&ei);
1676 }
1677 return change;
1678}
1679
1680/* Find basic blocks with more than one predecessor that only contain a
1681 single conditional jump. If the result of the comparison is known at
1682 compile-time from any incoming edge, redirect that edge to the
1683 appropriate target. Return nonzero if a change was made.
1684
1685 This function is now mis-named, because we also handle indirect jumps. */
1686
1687static int
1688bypass_conditional_jumps (void)
1689{
1690 basic_block bb;
1691 int changed;
1692 rtx_insn *setcc;
1693 rtx_insn *insn;
1694 rtx dest;
1695
1696 /* Note we start at block 1. */
1697 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1698 return 0;
1699
1700 mark_dfs_back_edges ();
1701
1702 changed = 0;
1703 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
1704 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1705 {
1706 /* Check for more than one predecessor. */
1707 if (!single_pred_p (bb))
1708 {
1709 setcc = NULL;
1710 FOR_BB_INSNS (bb, insn)
1711 if (DEBUG_INSN_P (insn))
1712 continue;
1713 else if (NONJUMP_INSN_P (insn))
1714 {
1715 if (setcc)
1716 break;
1717 if (GET_CODE (PATTERN (insn)) != SET)
1718 break;
1719
1720 dest = SET_DEST (PATTERN (insn));
1721 if (REG_P (dest) || CC0_P (dest))
1722 setcc = insn;
1723 else
1724 break;
1725 }
1726 else if (JUMP_P (insn))
1727 {
1728 if ((any_condjump_p (insn) || computed_jump_p (insn))
1729 && onlyjump_p (insn))
1730 changed |= bypass_block (bb, setcc, insn);
1731 break;
1732 }
1733 else if (INSN_P (insn))
1734 break;
1735 }
1736 }
1737
1738 /* If we bypassed any register setting insns, we inserted a
1739 copy on the redirected edge. These need to be committed. */
1740 if (changed)
1741 commit_edge_insertions ();
1742
1743 return changed;
1744}
1745
1746/* Main function for the CPROP pass. */
1747
1748static int
1749one_cprop_pass (void)
1750{
1751 int i;
1752 int changed = 0;
1753
1754 /* Return if there's nothing to do, or it is too expensive. */
1755 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
1756 || gcse_or_cprop_is_too_expensive (_ ("const/copy propagation disabled")))
1757 return 0;
1758
1759 global_const_prop_count = local_const_prop_count = 0;
1760 global_copy_prop_count = local_copy_prop_count = 0;
1761
1762 bytes_used = 0;
1763 gcc_obstack_init (&cprop_obstack);
1764
1765 /* Do a local const/copy propagation pass first. The global pass
1766 only handles global opportunities.
1767 If the local pass changes something, remove any unreachable blocks
1768 because the CPROP global dataflow analysis may get into infinite
1769 loops for CFGs with unreachable blocks.
1770
1771 FIXME: This local pass should not be necessary after CSE (but for
1772 some reason it still is). It is also (proven) not necessary
1773 to run the local pass right after FWPWOP.
1774
1775 FIXME: The global analysis would not get into infinite loops if it
1776 would use the DF solver (via df_simple_dataflow) instead of
1777 the solver implemented in this file. */
1778 changed |= local_cprop_pass ();
1779 if (changed)
1780 delete_unreachable_blocks ();
1781
1782 /* Determine implicit sets. This may change the CFG (split critical
1783 edges if that exposes an implicit set).
1784 Note that find_implicit_sets() does not rely on up-to-date DF caches
1785 so that we do not have to re-run df_analyze() even if local CPROP
1786 changed something.
1787 ??? This could run earlier so that any uncovered implicit sets
1788 sets could be exploited in local_cprop_pass() also. Later. */
1789 changed |= find_implicit_sets ();
1790
1791 /* If local_cprop_pass() or find_implicit_sets() changed something,
1792 run df_analyze() to bring all insn caches up-to-date, and to take
1793 new basic blocks from edge splitting on the DF radar.
1794 NB: This also runs the fast DCE pass, because execute_rtl_cprop
1795 sets DF_LR_RUN_DCE. */
1796 if (changed)
1797 df_analyze ();
1798
1799 /* Initialize implicit_set_indexes array. */
1800 implicit_set_indexes = XNEWVEC (int, last_basic_block_for_fn (cfun));
1801 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
1802 implicit_set_indexes[i] = -1;
1803
1804 alloc_hash_table (&set_hash_table);
1805 compute_hash_table (&set_hash_table);
1806
1807 /* Free implicit_sets before peak usage. */
1808 free (implicit_sets);
1809 implicit_sets = NULL;
1810
1811 if (dump_file)
1812 dump_hash_table (dump_file, "SET", &set_hash_table);
1813 if (set_hash_table.n_elems > 0)
1814 {
1815 basic_block bb;
1816 auto_vec<rtx_insn *> uncond_traps;
1817
1818 alloc_cprop_mem (last_basic_block_for_fn (cfun),
1819 set_hash_table.n_elems);
1820 compute_cprop_data ();
1821
1822 free (implicit_set_indexes);
1823 implicit_set_indexes = NULL;
1824
1825 /* Allocate vars to track sets of regs. */
1826 reg_set_bitmap = ALLOC_REG_SET (NULL);
1827
1828 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
1829 EXIT_BLOCK_PTR_FOR_FN (cfun),
1830 next_bb)
1831 {
1832 bool seen_uncond_trap = false;
1833 rtx_insn *insn;
1834
1835 /* Reset tables used to keep track of what's still valid [since
1836 the start of the block]. */
1837 reset_opr_set_tables ();
1838
1839 FOR_BB_INSNS (bb, insn)
1840 if (INSN_P (insn))
1841 {
1842 bool was_uncond_trap
1843 = (GET_CODE (PATTERN (insn)) == TRAP_IF
1844 && XEXP (PATTERN (insn), 0) == const1_rtx);
1845
1846 changed |= cprop_insn (insn);
1847
1848 /* Keep track of everything modified by this insn. */
1849 /* ??? Need to be careful w.r.t. mods done to INSN.
1850 Don't call mark_oprs_set if we turned the
1851 insn into a NOTE, or deleted the insn. */
1852 if (! NOTE_P (insn) && ! insn->deleted ())
1853 mark_oprs_set (insn);
1854
1855 if (!was_uncond_trap
1856 && GET_CODE (PATTERN (insn)) == TRAP_IF
1857 && XEXP (PATTERN (insn), 0) == const1_rtx)
1858 {
1859 /* If we have already seen an unconditional trap
1860 earlier, the rest of the bb is going to be removed
1861 as unreachable. Just turn it into a note, so that
1862 RTL verification doesn't complain about it before
1863 it is finally removed. */
1864 if (seen_uncond_trap)
1865 set_insn_deleted (insn);
1866 else
1867 {
1868 seen_uncond_trap = true;
1869 uncond_traps.safe_push (insn);
1870 }
1871 }
1872 }
1873 }
1874
1875 /* Make sure bypass_conditional_jumps will ignore not just its new
1876 basic blocks, but also the ones after unconditional traps (those are
1877 unreachable and will be eventually removed as such). */
1878 bypass_last_basic_block = last_basic_block_for_fn (cfun);
1879
1880 while (!uncond_traps.is_empty ())
1881 {
1882 rtx_insn *insn = uncond_traps.pop ();
1883 basic_block to_split = BLOCK_FOR_INSN (insn);
1884 remove_edge (split_block (to_split, insn));
1885 emit_barrier_after_bb (to_split);
1886 }
1887
1888 changed |= bypass_conditional_jumps ();
1889
1890 FREE_REG_SET (reg_set_bitmap);
1891 free_cprop_mem ();
1892 }
1893 else
1894 {
1895 free (implicit_set_indexes);
1896 implicit_set_indexes = NULL;
1897 }
1898
1899 free_hash_table (&set_hash_table);
1900 obstack_free (&cprop_obstack, NULL);
1901
1902 if (dump_file)
1903 {
1904 fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
1905 current_function_name (), n_basic_blocks_for_fn (cfun),
1906 bytes_used);
1907 fprintf (dump_file, "%d local const props, %d local copy props, ",
1908 local_const_prop_count, local_copy_prop_count);
1909 fprintf (dump_file, "%d global const props, %d global copy props\n\n",
1910 global_const_prop_count, global_copy_prop_count);
1911 }
1912
1913 return changed;
1914}
1915
1916/* All the passes implemented in this file. Each pass has its
1917 own gate and execute function, and at the end of the file a
1918 pass definition for passes.c.
1919
1920 We do not construct an accurate cfg in functions which call
1921 setjmp, so none of these passes runs if the function calls
1922 setjmp.
1923 FIXME: Should just handle setjmp via REG_SETJMP notes. */
1924
1925static unsigned int
1926execute_rtl_cprop (void)
1927{
1928 int changed;
1929 delete_unreachable_blocks ();
1930 df_set_flags (DF_LR_RUN_DCE);
1931 df_analyze ();
1932 changed = one_cprop_pass ();
1933 flag_rerun_cse_after_global_opts |= changed;
1934 if (changed)
1935 cleanup_cfg (CLEANUP_CFG_CHANGED);
1936 return 0;
1937}
1938
1939namespace {
1940
1941const pass_data pass_data_rtl_cprop =
1942{
1943 RTL_PASS, /* type */
1944 "cprop", /* name */
1945 OPTGROUP_NONE, /* optinfo_flags */
1946 TV_CPROP, /* tv_id */
1947 PROP_cfglayout, /* properties_required */
1948 0, /* properties_provided */
1949 0, /* properties_destroyed */
1950 0, /* todo_flags_start */
1951 TODO_df_finish, /* todo_flags_finish */
1952};
1953
1954class pass_rtl_cprop : public rtl_opt_pass
1955{
1956public:
1957 pass_rtl_cprop (gcc::context *ctxt)
1958 : rtl_opt_pass (pass_data_rtl_cprop, ctxt)
1959 {}
1960
1961 /* opt_pass methods: */
1962 opt_pass * clone () { return new pass_rtl_cprop (m_ctxt); }
1963 virtual bool gate (function *fun)
1964 {
1965 return optimize > 0 && flag_gcse
1966 && !fun->calls_setjmp
1967 && dbg_cnt (cprop);
1968 }
1969
1970 virtual unsigned int execute (function *) { return execute_rtl_cprop (); }
1971
1972}; // class pass_rtl_cprop
1973
1974} // anon namespace
1975
1976rtl_opt_pass *
1977make_pass_rtl_cprop (gcc::context *ctxt)
1978{
1979 return new pass_rtl_cprop (ctxt);
1980}
1981