Daily bump.
[official-gcc.git] / gcc / cprop.c
blobc3acb05c171df2b5931a413aed5f6b872a58397c
1 /* Global constant/copy propagation for RTL.
2 Copyright (C) 1997-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "diagnostic-core.h"
25 #include "toplev.h"
27 #include "rtl.h"
28 #include "tree.h"
29 #include "tm_p.h"
30 #include "regs.h"
31 #include "hard-reg-set.h"
32 #include "flags.h"
33 #include "insn-config.h"
34 #include "recog.h"
35 #include "basic-block.h"
36 #include "function.h"
37 #include "expr.h"
38 #include "except.h"
39 #include "params.h"
40 #include "cselib.h"
41 #include "intl.h"
42 #include "obstack.h"
43 #include "tree-pass.h"
44 #include "hashtab.h"
45 #include "df.h"
46 #include "dbgcnt.h"
47 #include "target.h"
48 #include "cfgloop.h"
51 /* An obstack for our working variables. */
52 static struct obstack cprop_obstack;
54 /* Occurrence of an expression.
55 There is one per basic block. If a pattern appears more than once the
56 last appearance is used. */
58 struct occr
60 /* Next occurrence of this expression. */
61 struct occr *next;
62 /* The insn that computes the expression. */
63 rtx insn;
66 typedef struct occr *occr_t;
68 /* Hash table entry for assignment expressions. */
70 struct expr
72 /* The expression (DEST := SRC). */
73 rtx dest;
74 rtx src;
76 /* Index in the available expression bitmaps. */
77 int bitmap_index;
78 /* Next entry with the same hash. */
79 struct expr *next_same_hash;
80 /* List of available occurrence in basic blocks in the function.
81 An "available occurrence" is one that is the last occurrence in the
82 basic block and whose operands are not modified by following statements
83 in the basic block [including this insn]. */
84 struct occr *avail_occr;
87 /* Hash table for copy propagation expressions.
88 Each hash table is an array of buckets.
89 ??? It is known that if it were an array of entries, structure elements
90 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
91 not clear whether in the final analysis a sufficient amount of memory would
92 be saved as the size of the available expression bitmaps would be larger
93 [one could build a mapping table without holes afterwards though].
94 Someday I'll perform the computation and figure it out. */
96 struct hash_table_d
98 /* The table itself.
99 This is an array of `set_hash_table_size' elements. */
100 struct expr **table;
102 /* Size of the hash table, in elements. */
103 unsigned int size;
105 /* Number of hash table elements. */
106 unsigned int n_elems;
109 /* Copy propagation hash table. */
110 static struct hash_table_d set_hash_table;
112 /* Array of implicit set patterns indexed by basic block index. */
113 static rtx *implicit_sets;
115 /* Array of indexes of expressions for implicit set patterns indexed by basic
116 block index. In other words, implicit_set_indexes[i] is the bitmap_index
117 of the expression whose RTX is implicit_sets[i]. */
118 static int *implicit_set_indexes;
120 /* Bitmap containing one bit for each register in the program.
121 Used when performing GCSE to track which registers have been set since
122 the start or end of the basic block while traversing that block. */
123 static regset reg_set_bitmap;
125 /* Various variables for statistics gathering. */
127 /* Memory used in a pass.
128 This isn't intended to be absolutely precise. Its intent is only
129 to keep an eye on memory usage. */
130 static int bytes_used;
132 /* Number of local constants propagated. */
133 static int local_const_prop_count;
134 /* Number of local copies propagated. */
135 static int local_copy_prop_count;
136 /* Number of global constants propagated. */
137 static int global_const_prop_count;
138 /* Number of global copies propagated. */
139 static int global_copy_prop_count;
141 #define GOBNEW(T) ((T *) cprop_alloc (sizeof (T)))
142 #define GOBNEWVAR(T, S) ((T *) cprop_alloc ((S)))
144 /* Cover function to obstack_alloc. */
146 static void *
147 cprop_alloc (unsigned long size)
149 bytes_used += size;
150 return obstack_alloc (&cprop_obstack, size);
153 /* Return nonzero if register X is unchanged from INSN to the end
154 of INSN's basic block. */
156 static int
157 reg_available_p (const_rtx x, const_rtx insn ATTRIBUTE_UNUSED)
159 return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
162 /* Hash a set of register REGNO.
164 Sets are hashed on the register that is set. This simplifies the PRE copy
165 propagation code.
167 ??? May need to make things more elaborate. Later, as necessary. */
169 static unsigned int
170 hash_set (int regno, int hash_table_size)
172 return (unsigned) regno % hash_table_size;
175 /* Insert assignment DEST:=SET from INSN in the hash table.
176 DEST is a register and SET is a register or a suitable constant.
177 If the assignment is already present in the table, record it as
178 the last occurrence in INSN's basic block.
179 IMPLICIT is true if it's an implicit set, false otherwise. */
181 static void
182 insert_set_in_table (rtx dest, rtx src, rtx insn, struct hash_table_d *table,
183 bool implicit)
185 bool found = false;
186 unsigned int hash;
187 struct expr *cur_expr, *last_expr = NULL;
188 struct occr *cur_occr;
190 hash = hash_set (REGNO (dest), table->size);
192 for (cur_expr = table->table[hash]; cur_expr;
193 cur_expr = cur_expr->next_same_hash)
195 if (dest == cur_expr->dest
196 && src == cur_expr->src)
198 found = true;
199 break;
201 last_expr = cur_expr;
204 if (! found)
206 cur_expr = GOBNEW (struct expr);
207 bytes_used += sizeof (struct expr);
208 if (table->table[hash] == NULL)
209 /* This is the first pattern that hashed to this index. */
210 table->table[hash] = cur_expr;
211 else
212 /* Add EXPR to end of this hash chain. */
213 last_expr->next_same_hash = cur_expr;
215 /* Set the fields of the expr element.
216 We must copy X because it can be modified when copy propagation is
217 performed on its operands. */
218 cur_expr->dest = copy_rtx (dest);
219 cur_expr->src = copy_rtx (src);
220 cur_expr->bitmap_index = table->n_elems++;
221 cur_expr->next_same_hash = NULL;
222 cur_expr->avail_occr = NULL;
225 /* Now record the occurrence. */
226 cur_occr = cur_expr->avail_occr;
228 if (cur_occr
229 && BLOCK_FOR_INSN (cur_occr->insn) == BLOCK_FOR_INSN (insn))
231 /* Found another instance of the expression in the same basic block.
232 Prefer this occurrence to the currently recorded one. We want
233 the last one in the block and the block is scanned from start
234 to end. */
235 cur_occr->insn = insn;
237 else
239 /* First occurrence of this expression in this basic block. */
240 cur_occr = GOBNEW (struct occr);
241 bytes_used += sizeof (struct occr);
242 cur_occr->insn = insn;
243 cur_occr->next = cur_expr->avail_occr;
244 cur_expr->avail_occr = cur_occr;
247 /* Record bitmap_index of the implicit set in implicit_set_indexes. */
248 if (implicit)
249 implicit_set_indexes[BLOCK_FOR_INSN (insn)->index]
250 = cur_expr->bitmap_index;
253 /* Determine whether the rtx X should be treated as a constant for CPROP.
254 Since X might be inserted more than once we have to take care that it
255 is sharable. */
257 static bool
258 cprop_constant_p (const_rtx x)
260 return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x));
263 /* Scan SET present in INSN and add an entry to the hash TABLE.
264 IMPLICIT is true if it's an implicit set, false otherwise. */
266 static void
267 hash_scan_set (rtx set, rtx insn, struct hash_table_d *table, bool implicit)
269 rtx src = SET_SRC (set);
270 rtx dest = SET_DEST (set);
272 if (REG_P (dest)
273 && ! HARD_REGISTER_P (dest)
274 && reg_available_p (dest, insn)
275 && can_copy_p (GET_MODE (dest)))
277 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
279 This allows us to do a single CPROP pass and still eliminate
280 redundant constants, addresses or other expressions that are
281 constructed with multiple instructions.
283 However, keep the original SRC if INSN is a simple reg-reg move. In
284 In this case, there will almost always be a REG_EQUAL note on the
285 insn that sets SRC. By recording the REG_EQUAL value here as SRC
286 for INSN, we miss copy propagation opportunities.
288 Note that this does not impede profitable constant propagations. We
289 "look through" reg-reg sets in lookup_set. */
290 rtx note = find_reg_equal_equiv_note (insn);
291 if (note != 0
292 && REG_NOTE_KIND (note) == REG_EQUAL
293 && !REG_P (src)
294 && cprop_constant_p (XEXP (note, 0)))
295 src = XEXP (note, 0), set = gen_rtx_SET (VOIDmode, dest, src);
297 /* Record sets for constant/copy propagation. */
298 if ((REG_P (src)
299 && src != dest
300 && ! HARD_REGISTER_P (src)
301 && reg_available_p (src, insn))
302 || cprop_constant_p (src))
303 insert_set_in_table (dest, src, insn, table, implicit);
307 /* Process INSN and add hash table entries as appropriate. */
309 static void
310 hash_scan_insn (rtx insn, struct hash_table_d *table)
312 rtx pat = PATTERN (insn);
313 int i;
315 /* Pick out the sets of INSN and for other forms of instructions record
316 what's been modified. */
318 if (GET_CODE (pat) == SET)
319 hash_scan_set (pat, insn, table, false);
320 else if (GET_CODE (pat) == PARALLEL)
321 for (i = 0; i < XVECLEN (pat, 0); i++)
323 rtx x = XVECEXP (pat, 0, i);
325 if (GET_CODE (x) == SET)
326 hash_scan_set (x, insn, table, false);
330 /* Dump the hash table TABLE to file FILE under the name NAME. */
332 static void
333 dump_hash_table (FILE *file, const char *name, struct hash_table_d *table)
335 int i;
336 /* Flattened out table, so it's printed in proper order. */
337 struct expr **flat_table;
338 unsigned int *hash_val;
339 struct expr *expr;
341 flat_table = XCNEWVEC (struct expr *, table->n_elems);
342 hash_val = XNEWVEC (unsigned int, table->n_elems);
344 for (i = 0; i < (int) table->size; i++)
345 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
347 flat_table[expr->bitmap_index] = expr;
348 hash_val[expr->bitmap_index] = i;
351 fprintf (file, "%s hash table (%d buckets, %d entries)\n",
352 name, table->size, table->n_elems);
354 for (i = 0; i < (int) table->n_elems; i++)
355 if (flat_table[i] != 0)
357 expr = flat_table[i];
358 fprintf (file, "Index %d (hash value %d)\n ",
359 expr->bitmap_index, hash_val[i]);
360 print_rtl (file, expr->dest);
361 fprintf (file, " := ");
362 print_rtl (file, expr->src);
363 fprintf (file, "\n");
366 fprintf (file, "\n");
368 free (flat_table);
369 free (hash_val);
372 /* Record as unavailable all registers that are DEF operands of INSN. */
374 static void
375 make_set_regs_unavailable (rtx insn)
377 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
378 df_ref *def_rec;
380 for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++)
381 SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (*def_rec));
384 /* Top level function to create an assignment hash table.
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
391 Currently src must be a pseudo-reg or a const_int.
393 TABLE is the table computed. */
395 static void
396 compute_hash_table_work (struct hash_table_d *table)
398 basic_block bb;
400 /* Allocate vars to track sets of regs. */
401 reg_set_bitmap = ALLOC_REG_SET (NULL);
403 FOR_EACH_BB_FN (bb, cfun)
405 rtx insn;
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);
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)
416 /* Only real insns are interesting. */
417 if (!NONDEBUG_INSN_P (insn))
418 continue;
420 /* Record interesting sets from INSN in the hash table. */
421 hash_scan_insn (insn, table);
423 /* Any registers set in INSN will make SETs above it not AVAIL. */
424 make_set_regs_unavailable (insn);
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);
433 FREE_REG_SET (reg_set_bitmap);
436 /* Allocate space for the set/expr hash TABLE.
437 It is used to determine the number of buckets to use. */
439 static void
440 alloc_hash_table (struct hash_table_d *table)
442 int n;
444 n = get_max_insn_count ();
446 table->size = n / 4;
447 if (table->size < 11)
448 table->size = 11;
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 expr *);
455 table->table = XNEWVAR (struct expr *, n);
458 /* Free things allocated by alloc_hash_table. */
460 static void
461 free_hash_table (struct hash_table_d *table)
463 free (table->table);
466 /* Compute the hash TABLE for doing copy/const propagation or
467 expression hash table. */
469 static void
470 compute_hash_table (struct hash_table_d *table)
472 /* Initialize count of number of entries in hash table. */
473 table->n_elems = 0;
474 memset (table->table, 0, table->size * sizeof (struct expr *));
476 compute_hash_table_work (table);
479 /* Expression tracking support. */
481 /* Lookup REGNO in the set TABLE. The result is a pointer to the
482 table entry, or NULL if not found. */
484 static struct expr *
485 lookup_set (unsigned int regno, struct hash_table_d *table)
487 unsigned int hash = hash_set (regno, table->size);
488 struct expr *expr;
490 expr = table->table[hash];
492 while (expr && REGNO (expr->dest) != regno)
493 expr = expr->next_same_hash;
495 return expr;
498 /* Return the next entry for REGNO in list EXPR. */
500 static struct expr *
501 next_set (unsigned int regno, struct expr *expr)
504 expr = expr->next_same_hash;
505 while (expr && REGNO (expr->dest) != regno);
507 return expr;
510 /* Reset tables used to keep track of what's still available [since the
511 start of the block]. */
513 static void
514 reset_opr_set_tables (void)
516 /* Maintain a bitmap of which regs have been set since beginning of
517 the block. */
518 CLEAR_REG_SET (reg_set_bitmap);
521 /* Return nonzero if the register X has not been set yet [since the
522 start of the basic block containing INSN]. */
524 static int
525 reg_not_set_p (const_rtx x, const_rtx insn ATTRIBUTE_UNUSED)
527 return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
530 /* Record things set by INSN.
531 This data is used by reg_not_set_p. */
533 static void
534 mark_oprs_set (rtx insn)
536 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
537 df_ref *def_rec;
539 for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++)
540 SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (*def_rec));
543 /* Compute copy/constant propagation working variables. */
545 /* Local properties of assignments. */
546 static sbitmap *cprop_avloc;
547 static sbitmap *cprop_kill;
549 /* Global properties of assignments (computed from the local properties). */
550 static sbitmap *cprop_avin;
551 static sbitmap *cprop_avout;
553 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
554 basic blocks. N_SETS is the number of sets. */
556 static void
557 alloc_cprop_mem (int n_blocks, int n_sets)
559 cprop_avloc = sbitmap_vector_alloc (n_blocks, n_sets);
560 cprop_kill = sbitmap_vector_alloc (n_blocks, n_sets);
562 cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
563 cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
566 /* Free vars used by copy/const propagation. */
568 static void
569 free_cprop_mem (void)
571 sbitmap_vector_free (cprop_avloc);
572 sbitmap_vector_free (cprop_kill);
573 sbitmap_vector_free (cprop_avin);
574 sbitmap_vector_free (cprop_avout);
577 /* Compute the local properties of each recorded expression.
579 Local properties are those that are defined by the block, irrespective of
580 other blocks.
582 An expression is killed in a block if its operands, either DEST or SRC, are
583 modified in the block.
585 An expression is computed (locally available) in a block if it is computed
586 at least once and expression would contain the same value if the
587 computation was moved to the end of the block.
589 KILL and COMP are destination sbitmaps for recording local properties. */
591 static void
592 compute_local_properties (sbitmap *kill, sbitmap *comp,
593 struct hash_table_d *table)
595 unsigned int i;
597 /* Initialize the bitmaps that were passed in. */
598 bitmap_vector_clear (kill, last_basic_block_for_fn (cfun));
599 bitmap_vector_clear (comp, last_basic_block_for_fn (cfun));
601 for (i = 0; i < table->size; i++)
603 struct expr *expr;
605 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
607 int indx = expr->bitmap_index;
608 df_ref def;
609 struct occr *occr;
611 /* For each definition of the destination pseudo-reg, the expression
612 is killed in the block where the definition is. */
613 for (def = DF_REG_DEF_CHAIN (REGNO (expr->dest));
614 def; def = DF_REF_NEXT_REG (def))
615 bitmap_set_bit (kill[DF_REF_BB (def)->index], indx);
617 /* If the source is a pseudo-reg, for each definition of the source,
618 the expression is killed in the block where the definition is. */
619 if (REG_P (expr->src))
620 for (def = DF_REG_DEF_CHAIN (REGNO (expr->src));
621 def; def = DF_REF_NEXT_REG (def))
622 bitmap_set_bit (kill[DF_REF_BB (def)->index], indx);
624 /* The occurrences recorded in avail_occr are exactly those that
625 are locally available in the block where they are. */
626 for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
628 bitmap_set_bit (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
634 /* Hash table support. */
636 /* Top level routine to do the dataflow analysis needed by copy/const
637 propagation. */
639 static void
640 compute_cprop_data (void)
642 basic_block bb;
644 compute_local_properties (cprop_kill, cprop_avloc, &set_hash_table);
645 compute_available (cprop_avloc, cprop_kill, cprop_avout, cprop_avin);
647 /* Merge implicit sets into CPROP_AVIN. They are always available at the
648 entry of their basic block. We need to do this because 1) implicit sets
649 aren't recorded for the local pass so they cannot be propagated within
650 their basic block by this pass and 2) the global pass would otherwise
651 propagate them only in the successors of their basic block. */
652 FOR_EACH_BB_FN (bb, cfun)
654 int index = implicit_set_indexes[bb->index];
655 if (index != -1)
656 bitmap_set_bit (cprop_avin[bb->index], index);
660 /* Copy/constant propagation. */
662 /* Maximum number of register uses in an insn that we handle. */
663 #define MAX_USES 8
665 /* Table of uses (registers, both hard and pseudo) found in an insn.
666 Allocated statically to avoid alloc/free complexity and overhead. */
667 static rtx reg_use_table[MAX_USES];
669 /* Index into `reg_use_table' while building it. */
670 static unsigned reg_use_count;
672 /* Set up a list of register numbers used in INSN. The found uses are stored
673 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
674 and contains the number of uses in the table upon exit.
676 ??? If a register appears multiple times we will record it multiple times.
677 This doesn't hurt anything but it will slow things down. */
679 static void
680 find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED)
682 int i, j;
683 enum rtx_code code;
684 const char *fmt;
685 rtx x = *xptr;
687 /* repeat is used to turn tail-recursion into iteration since GCC
688 can't do it when there's no return value. */
689 repeat:
690 if (x == 0)
691 return;
693 code = GET_CODE (x);
694 if (REG_P (x))
696 if (reg_use_count == MAX_USES)
697 return;
699 reg_use_table[reg_use_count] = x;
700 reg_use_count++;
703 /* Recursively scan the operands of this expression. */
705 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
707 if (fmt[i] == 'e')
709 /* If we are about to do the last recursive call
710 needed at this level, change it into iteration.
711 This function is called enough to be worth it. */
712 if (i == 0)
714 x = XEXP (x, 0);
715 goto repeat;
718 find_used_regs (&XEXP (x, i), data);
720 else if (fmt[i] == 'E')
721 for (j = 0; j < XVECLEN (x, i); j++)
722 find_used_regs (&XVECEXP (x, i, j), data);
726 /* Try to replace all uses of FROM in INSN with TO.
727 Return nonzero if successful. */
729 static int
730 try_replace_reg (rtx from, rtx to, rtx insn)
732 rtx note = find_reg_equal_equiv_note (insn);
733 rtx src = 0;
734 int success = 0;
735 rtx set = single_set (insn);
737 /* Usually we substitute easy stuff, so we won't copy everything.
738 We however need to take care to not duplicate non-trivial CONST
739 expressions. */
740 to = copy_rtx (to);
742 validate_replace_src_group (from, to, insn);
743 if (num_changes_pending () && apply_change_group ())
744 success = 1;
746 /* Try to simplify SET_SRC if we have substituted a constant. */
747 if (success && set && CONSTANT_P (to))
749 src = simplify_rtx (SET_SRC (set));
751 if (src)
752 validate_change (insn, &SET_SRC (set), src, 0);
755 /* If there is already a REG_EQUAL note, update the expression in it
756 with our replacement. */
757 if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
758 set_unique_reg_note (insn, REG_EQUAL,
759 simplify_replace_rtx (XEXP (note, 0), from, to));
760 if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
762 /* If above failed and this is a single set, try to simplify the source
763 of the set given our substitution. We could perhaps try this for
764 multiple SETs, but it probably won't buy us anything. */
765 src = simplify_replace_rtx (SET_SRC (set), from, to);
767 if (!rtx_equal_p (src, SET_SRC (set))
768 && validate_change (insn, &SET_SRC (set), src, 0))
769 success = 1;
771 /* If we've failed perform the replacement, have a single SET to
772 a REG destination and don't yet have a note, add a REG_EQUAL note
773 to not lose information. */
774 if (!success && note == 0 && set != 0 && REG_P (SET_DEST (set)))
775 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
778 if (set && MEM_P (SET_DEST (set)) && reg_mentioned_p (from, SET_DEST (set)))
780 /* Registers can also appear as uses in SET_DEST if it is a MEM.
781 We could perhaps try this for multiple SETs, but it probably
782 won't buy us anything. */
783 rtx dest = simplify_replace_rtx (SET_DEST (set), from, to);
785 if (!rtx_equal_p (dest, SET_DEST (set))
786 && validate_change (insn, &SET_DEST (set), dest, 0))
787 success = 1;
790 /* REG_EQUAL may get simplified into register.
791 We don't allow that. Remove that note. This code ought
792 not to happen, because previous code ought to synthesize
793 reg-reg move, but be on the safe side. */
794 if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0)))
795 remove_note (insn, note);
797 return success;
800 /* Find a set of REGNOs that are available on entry to INSN's block. Return
801 NULL no such set is found. */
803 static struct expr *
804 find_avail_set (int regno, rtx insn)
806 /* SET1 contains the last set found that can be returned to the caller for
807 use in a substitution. */
808 struct expr *set1 = 0;
810 /* Loops are not possible here. To get a loop we would need two sets
811 available at the start of the block containing INSN. i.e. we would
812 need two sets like this available at the start of the block:
814 (set (reg X) (reg Y))
815 (set (reg Y) (reg X))
817 This can not happen since the set of (reg Y) would have killed the
818 set of (reg X) making it unavailable at the start of this block. */
819 while (1)
821 rtx src;
822 struct expr *set = lookup_set (regno, &set_hash_table);
824 /* Find a set that is available at the start of the block
825 which contains INSN. */
826 while (set)
828 if (bitmap_bit_p (cprop_avin[BLOCK_FOR_INSN (insn)->index],
829 set->bitmap_index))
830 break;
831 set = next_set (regno, set);
834 /* If no available set was found we've reached the end of the
835 (possibly empty) copy chain. */
836 if (set == 0)
837 break;
839 src = set->src;
841 /* We know the set is available.
842 Now check that SRC is locally anticipatable (i.e. none of the
843 source operands have changed since the start of the block).
845 If the source operand changed, we may still use it for the next
846 iteration of this loop, but we may not use it for substitutions. */
848 if (cprop_constant_p (src) || reg_not_set_p (src, insn))
849 set1 = set;
851 /* If the source of the set is anything except a register, then
852 we have reached the end of the copy chain. */
853 if (! REG_P (src))
854 break;
856 /* Follow the copy chain, i.e. start another iteration of the loop
857 and see if we have an available copy into SRC. */
858 regno = REGNO (src);
861 /* SET1 holds the last set that was available and anticipatable at
862 INSN. */
863 return set1;
866 /* Subroutine of cprop_insn that tries to propagate constants into
867 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
868 it is the instruction that immediately precedes JUMP, and must be a
869 single SET of a register. FROM is what we will try to replace,
870 SRC is the constant we will try to substitute for it. Return nonzero
871 if a change was made. */
873 static int
874 cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src)
876 rtx new_rtx, set_src, note_src;
877 rtx set = pc_set (jump);
878 rtx note = find_reg_equal_equiv_note (jump);
880 if (note)
882 note_src = XEXP (note, 0);
883 if (GET_CODE (note_src) == EXPR_LIST)
884 note_src = NULL_RTX;
886 else note_src = NULL_RTX;
888 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
889 set_src = note_src ? note_src : SET_SRC (set);
891 /* First substitute the SETCC condition into the JUMP instruction,
892 then substitute that given values into this expanded JUMP. */
893 if (setcc != NULL_RTX
894 && !modified_between_p (from, setcc, jump)
895 && !modified_between_p (src, setcc, jump))
897 rtx setcc_src;
898 rtx setcc_set = single_set (setcc);
899 rtx setcc_note = find_reg_equal_equiv_note (setcc);
900 setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST)
901 ? XEXP (setcc_note, 0) : SET_SRC (setcc_set);
902 set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set),
903 setcc_src);
905 else
906 setcc = NULL_RTX;
908 new_rtx = simplify_replace_rtx (set_src, from, src);
910 /* If no simplification can be made, then try the next register. */
911 if (rtx_equal_p (new_rtx, SET_SRC (set)))
912 return 0;
914 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
915 if (new_rtx == pc_rtx)
916 delete_insn (jump);
917 else
919 /* Ensure the value computed inside the jump insn to be equivalent
920 to one computed by setcc. */
921 if (setcc && modified_in_p (new_rtx, setcc))
922 return 0;
923 if (! validate_unshare_change (jump, &SET_SRC (set), new_rtx, 0))
925 /* When (some) constants are not valid in a comparison, and there
926 are two registers to be replaced by constants before the entire
927 comparison can be folded into a constant, we need to keep
928 intermediate information in REG_EQUAL notes. For targets with
929 separate compare insns, such notes are added by try_replace_reg.
930 When we have a combined compare-and-branch instruction, however,
931 we need to attach a note to the branch itself to make this
932 optimization work. */
934 if (!rtx_equal_p (new_rtx, note_src))
935 set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new_rtx));
936 return 0;
939 /* Remove REG_EQUAL note after simplification. */
940 if (note_src)
941 remove_note (jump, note);
944 #ifdef HAVE_cc0
945 /* Delete the cc0 setter. */
946 if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
947 delete_insn (setcc);
948 #endif
950 global_const_prop_count++;
951 if (dump_file != NULL)
953 fprintf (dump_file,
954 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with"
955 "constant ", REGNO (from), INSN_UID (jump));
956 print_rtl (dump_file, src);
957 fprintf (dump_file, "\n");
959 purge_dead_edges (bb);
961 /* If a conditional jump has been changed into unconditional jump, remove
962 the jump and make the edge fallthru - this is always called in
963 cfglayout mode. */
964 if (new_rtx != pc_rtx && simplejump_p (jump))
966 edge e;
967 edge_iterator ei;
969 FOR_EACH_EDGE (e, ei, bb->succs)
970 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
971 && BB_HEAD (e->dest) == JUMP_LABEL (jump))
973 e->flags |= EDGE_FALLTHRU;
974 break;
976 delete_insn (jump);
979 return 1;
982 /* Subroutine of cprop_insn that tries to propagate constants. FROM is what
983 we will try to replace, SRC is the constant we will try to substitute for
984 it and INSN is the instruction where this will be happening. */
986 static int
987 constprop_register (rtx from, rtx src, rtx insn)
989 rtx sset;
991 /* Check for reg or cc0 setting instructions followed by
992 conditional branch instructions first. */
993 if ((sset = single_set (insn)) != NULL
994 && NEXT_INSN (insn)
995 && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
997 rtx dest = SET_DEST (sset);
998 if ((REG_P (dest) || CC0_P (dest))
999 && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn),
1000 from, src))
1001 return 1;
1004 /* Handle normal insns next. */
1005 if (NONJUMP_INSN_P (insn) && try_replace_reg (from, src, insn))
1006 return 1;
1008 /* Try to propagate a CONST_INT into a conditional jump.
1009 We're pretty specific about what we will handle in this
1010 code, we can extend this as necessary over time.
1012 Right now the insn in question must look like
1013 (set (pc) (if_then_else ...)) */
1014 else if (any_condjump_p (insn) && onlyjump_p (insn))
1015 return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, src);
1016 return 0;
1019 /* Perform constant and copy propagation on INSN.
1020 Return nonzero if a change was made. */
1022 static int
1023 cprop_insn (rtx insn)
1025 unsigned i;
1026 int changed = 0, changed_this_round;
1027 rtx note;
1029 retry:
1030 changed_this_round = 0;
1031 reg_use_count = 0;
1032 note_uses (&PATTERN (insn), find_used_regs, NULL);
1034 /* We may win even when propagating constants into notes. */
1035 note = find_reg_equal_equiv_note (insn);
1036 if (note)
1037 find_used_regs (&XEXP (note, 0), NULL);
1039 for (i = 0; i < reg_use_count; i++)
1041 rtx reg_used = reg_use_table[i];
1042 unsigned int regno = REGNO (reg_used);
1043 rtx src;
1044 struct expr *set;
1046 /* If the register has already been set in this block, there's
1047 nothing we can do. */
1048 if (! reg_not_set_p (reg_used, insn))
1049 continue;
1051 /* Find an assignment that sets reg_used and is available
1052 at the start of the block. */
1053 set = find_avail_set (regno, insn);
1054 if (! set)
1055 continue;
1057 src = set->src;
1059 /* Constant propagation. */
1060 if (cprop_constant_p (src))
1062 if (constprop_register (reg_used, src, insn))
1064 changed_this_round = changed = 1;
1065 global_const_prop_count++;
1066 if (dump_file != NULL)
1068 fprintf (dump_file,
1069 "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
1070 fprintf (dump_file, "insn %d with constant ",
1071 INSN_UID (insn));
1072 print_rtl (dump_file, src);
1073 fprintf (dump_file, "\n");
1075 if (INSN_DELETED_P (insn))
1076 return 1;
1079 else if (REG_P (src)
1080 && REGNO (src) >= FIRST_PSEUDO_REGISTER
1081 && REGNO (src) != regno)
1083 if (try_replace_reg (reg_used, src, insn))
1085 changed_this_round = changed = 1;
1086 global_copy_prop_count++;
1087 if (dump_file != NULL)
1089 fprintf (dump_file,
1090 "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1091 regno, INSN_UID (insn));
1092 fprintf (dump_file, " with reg %d\n", REGNO (src));
1095 /* The original insn setting reg_used may or may not now be
1096 deletable. We leave the deletion to DCE. */
1097 /* FIXME: If it turns out that the insn isn't deletable,
1098 then we may have unnecessarily extended register lifetimes
1099 and made things worse. */
1103 /* If try_replace_reg simplified the insn, the regs found
1104 by find_used_regs may not be valid anymore. Start over. */
1105 if (changed_this_round)
1106 goto retry;
1109 if (changed && DEBUG_INSN_P (insn))
1110 return 0;
1112 return changed;
1115 /* Like find_used_regs, but avoid recording uses that appear in
1116 input-output contexts such as zero_extract or pre_dec. This
1117 restricts the cases we consider to those for which local cprop
1118 can legitimately make replacements. */
1120 static void
1121 local_cprop_find_used_regs (rtx *xptr, void *data)
1123 rtx x = *xptr;
1125 if (x == 0)
1126 return;
1128 switch (GET_CODE (x))
1130 case ZERO_EXTRACT:
1131 case SIGN_EXTRACT:
1132 case STRICT_LOW_PART:
1133 return;
1135 case PRE_DEC:
1136 case PRE_INC:
1137 case POST_DEC:
1138 case POST_INC:
1139 case PRE_MODIFY:
1140 case POST_MODIFY:
1141 /* Can only legitimately appear this early in the context of
1142 stack pushes for function arguments, but handle all of the
1143 codes nonetheless. */
1144 return;
1146 case SUBREG:
1147 /* Setting a subreg of a register larger than word_mode leaves
1148 the non-written words unchanged. */
1149 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) > BITS_PER_WORD)
1150 return;
1151 break;
1153 default:
1154 break;
1157 find_used_regs (xptr, data);
1160 /* Try to perform local const/copy propagation on X in INSN. */
1162 static bool
1163 do_local_cprop (rtx x, rtx insn)
1165 rtx newreg = NULL, newcnst = NULL;
1167 /* Rule out USE instructions and ASM statements as we don't want to
1168 change the hard registers mentioned. */
1169 if (REG_P (x)
1170 && (REGNO (x) >= FIRST_PSEUDO_REGISTER
1171 || (GET_CODE (PATTERN (insn)) != USE
1172 && asm_noperands (PATTERN (insn)) < 0)))
1174 cselib_val *val = cselib_lookup (x, GET_MODE (x), 0, VOIDmode);
1175 struct elt_loc_list *l;
1177 if (!val)
1178 return false;
1179 for (l = val->locs; l; l = l->next)
1181 rtx this_rtx = l->loc;
1182 rtx note;
1184 if (cprop_constant_p (this_rtx))
1185 newcnst = this_rtx;
1186 if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
1187 /* Don't copy propagate if it has attached REG_EQUIV note.
1188 At this point this only function parameters should have
1189 REG_EQUIV notes and if the argument slot is used somewhere
1190 explicitly, it means address of parameter has been taken,
1191 so we should not extend the lifetime of the pseudo. */
1192 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
1193 || ! MEM_P (XEXP (note, 0))))
1194 newreg = this_rtx;
1196 if (newcnst && constprop_register (x, newcnst, insn))
1198 if (dump_file != NULL)
1200 fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ",
1201 REGNO (x));
1202 fprintf (dump_file, "insn %d with constant ",
1203 INSN_UID (insn));
1204 print_rtl (dump_file, newcnst);
1205 fprintf (dump_file, "\n");
1207 local_const_prop_count++;
1208 return true;
1210 else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
1212 if (dump_file != NULL)
1214 fprintf (dump_file,
1215 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1216 REGNO (x), INSN_UID (insn));
1217 fprintf (dump_file, " with reg %d\n", REGNO (newreg));
1219 local_copy_prop_count++;
1220 return true;
1223 return false;
1226 /* Do local const/copy propagation (i.e. within each basic block). */
1228 static int
1229 local_cprop_pass (void)
1231 basic_block bb;
1232 rtx insn;
1233 bool changed = false;
1234 unsigned i;
1236 cselib_init (0);
1237 FOR_EACH_BB_FN (bb, cfun)
1239 FOR_BB_INSNS (bb, insn)
1241 if (INSN_P (insn))
1243 rtx note = find_reg_equal_equiv_note (insn);
1246 reg_use_count = 0;
1247 note_uses (&PATTERN (insn), local_cprop_find_used_regs,
1248 NULL);
1249 if (note)
1250 local_cprop_find_used_regs (&XEXP (note, 0), NULL);
1252 for (i = 0; i < reg_use_count; i++)
1254 if (do_local_cprop (reg_use_table[i], insn))
1256 if (!DEBUG_INSN_P (insn))
1257 changed = true;
1258 break;
1261 if (INSN_DELETED_P (insn))
1262 break;
1264 while (i < reg_use_count);
1266 cselib_process_insn (insn);
1269 /* Forget everything at the end of a basic block. */
1270 cselib_clear_table ();
1273 cselib_finish ();
1275 return changed;
1278 /* Similar to get_condition, only the resulting condition must be
1279 valid at JUMP, instead of at EARLIEST.
1281 This differs from noce_get_condition in ifcvt.c in that we prefer not to
1282 settle for the condition variable in the jump instruction being integral.
1283 We prefer to be able to record the value of a user variable, rather than
1284 the value of a temporary used in a condition. This could be solved by
1285 recording the value of *every* register scanned by canonicalize_condition,
1286 but this would require some code reorganization. */
1289 fis_get_condition (rtx jump)
1291 return get_condition (jump, NULL, false, true);
1294 /* Check the comparison COND to see if we can safely form an implicit
1295 set from it. */
1297 static bool
1298 implicit_set_cond_p (const_rtx cond)
1300 enum machine_mode mode;
1301 rtx cst;
1303 /* COND must be either an EQ or NE comparison. */
1304 if (GET_CODE (cond) != EQ && GET_CODE (cond) != NE)
1305 return false;
1307 /* The first operand of COND must be a pseudo-reg. */
1308 if (! REG_P (XEXP (cond, 0))
1309 || HARD_REGISTER_P (XEXP (cond, 0)))
1310 return false;
1312 /* The second operand of COND must be a suitable constant. */
1313 mode = GET_MODE (XEXP (cond, 0));
1314 cst = XEXP (cond, 1);
1316 /* We can't perform this optimization if either operand might be or might
1317 contain a signed zero. */
1318 if (HONOR_SIGNED_ZEROS (mode))
1320 /* It is sufficient to check if CST is or contains a zero. We must
1321 handle float, complex, and vector. If any subpart is a zero, then
1322 the optimization can't be performed. */
1323 /* ??? The complex and vector checks are not implemented yet. We just
1324 always return zero for them. */
1325 if (CONST_DOUBLE_AS_FLOAT_P (cst))
1327 REAL_VALUE_TYPE d;
1328 REAL_VALUE_FROM_CONST_DOUBLE (d, cst);
1329 if (REAL_VALUES_EQUAL (d, dconst0))
1330 return 0;
1332 else
1333 return 0;
1336 return cprop_constant_p (cst);
1339 /* Find the implicit sets of a function. An "implicit set" is a constraint
1340 on the value of a variable, implied by a conditional jump. For example,
1341 following "if (x == 2)", the then branch may be optimized as though the
1342 conditional performed an "explicit set", in this example, "x = 2". This
1343 function records the set patterns that are implicit at the start of each
1344 basic block.
1346 If an implicit set is found but the set is implicit on a critical edge,
1347 this critical edge is split.
1349 Return true if the CFG was modified, false otherwise. */
1351 static bool
1352 find_implicit_sets (void)
1354 basic_block bb, dest;
1355 rtx cond, new_rtx;
1356 unsigned int count = 0;
1357 bool edges_split = false;
1358 size_t implicit_sets_size = last_basic_block_for_fn (cfun) + 10;
1360 implicit_sets = XCNEWVEC (rtx, implicit_sets_size);
1362 FOR_EACH_BB_FN (bb, cfun)
1364 /* Check for more than one successor. */
1365 if (EDGE_COUNT (bb->succs) <= 1)
1366 continue;
1368 cond = fis_get_condition (BB_END (bb));
1370 /* If no condition is found or if it isn't of a suitable form,
1371 ignore it. */
1372 if (! cond || ! implicit_set_cond_p (cond))
1373 continue;
1375 dest = GET_CODE (cond) == EQ
1376 ? BRANCH_EDGE (bb)->dest : FALLTHRU_EDGE (bb)->dest;
1378 /* If DEST doesn't go anywhere, ignore it. */
1379 if (! dest || dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1380 continue;
1382 /* We have found a suitable implicit set. Try to record it now as
1383 a SET in DEST. If DEST has more than one predecessor, the edge
1384 between BB and DEST is a critical edge and we must split it,
1385 because we can only record one implicit set per DEST basic block. */
1386 if (! single_pred_p (dest))
1388 dest = split_edge (find_edge (bb, dest));
1389 edges_split = true;
1392 if (implicit_sets_size <= (size_t) dest->index)
1394 size_t old_implicit_sets_size = implicit_sets_size;
1395 implicit_sets_size *= 2;
1396 implicit_sets = XRESIZEVEC (rtx, implicit_sets, implicit_sets_size);
1397 memset (implicit_sets + old_implicit_sets_size, 0,
1398 (implicit_sets_size - old_implicit_sets_size) * sizeof (rtx));
1401 new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
1402 XEXP (cond, 1));
1403 implicit_sets[dest->index] = new_rtx;
1404 if (dump_file)
1406 fprintf (dump_file, "Implicit set of reg %d in ",
1407 REGNO (XEXP (cond, 0)));
1408 fprintf (dump_file, "basic block %d\n", dest->index);
1410 count++;
1413 if (dump_file)
1414 fprintf (dump_file, "Found %d implicit sets\n", count);
1416 /* Confess our sins. */
1417 return edges_split;
1420 /* Bypass conditional jumps. */
1422 /* The value of last_basic_block at the beginning of the jump_bypass
1423 pass. The use of redirect_edge_and_branch_force may introduce new
1424 basic blocks, but the data flow analysis is only valid for basic
1425 block indices less than bypass_last_basic_block. */
1427 static int bypass_last_basic_block;
1429 /* Find a set of REGNO to a constant that is available at the end of basic
1430 block BB. Return NULL if no such set is found. Based heavily upon
1431 find_avail_set. */
1433 static struct expr *
1434 find_bypass_set (int regno, int bb)
1436 struct expr *result = 0;
1438 for (;;)
1440 rtx src;
1441 struct expr *set = lookup_set (regno, &set_hash_table);
1443 while (set)
1445 if (bitmap_bit_p (cprop_avout[bb], set->bitmap_index))
1446 break;
1447 set = next_set (regno, set);
1450 if (set == 0)
1451 break;
1453 src = set->src;
1454 if (cprop_constant_p (src))
1455 result = set;
1457 if (! REG_P (src))
1458 break;
1460 regno = REGNO (src);
1462 return result;
1465 /* Subroutine of bypass_block that checks whether a pseudo is killed by
1466 any of the instructions inserted on an edge. Jump bypassing places
1467 condition code setters on CFG edges using insert_insn_on_edge. This
1468 function is required to check that our data flow analysis is still
1469 valid prior to commit_edge_insertions. */
1471 static bool
1472 reg_killed_on_edge (const_rtx reg, const_edge e)
1474 rtx insn;
1476 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
1477 if (INSN_P (insn) && reg_set_p (reg, insn))
1478 return true;
1480 return false;
1483 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1484 basic block BB which has more than one predecessor. If not NULL, SETCC
1485 is the first instruction of BB, which is immediately followed by JUMP_INSN
1486 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1487 Returns nonzero if a change was made.
1489 During the jump bypassing pass, we may place copies of SETCC instructions
1490 on CFG edges. The following routine must be careful to pay attention to
1491 these inserted insns when performing its transformations. */
1493 static int
1494 bypass_block (basic_block bb, rtx setcc, rtx jump)
1496 rtx insn, note;
1497 edge e, edest;
1498 int change;
1499 int may_be_loop_header = false;
1500 unsigned removed_p;
1501 unsigned i;
1502 edge_iterator ei;
1504 insn = (setcc != NULL) ? setcc : jump;
1506 /* Determine set of register uses in INSN. */
1507 reg_use_count = 0;
1508 note_uses (&PATTERN (insn), find_used_regs, NULL);
1509 note = find_reg_equal_equiv_note (insn);
1510 if (note)
1511 find_used_regs (&XEXP (note, 0), NULL);
1513 if (current_loops)
1515 /* If we are to preserve loop structure then do not bypass
1516 a loop header. This will either rotate the loop, create
1517 multiple entry loops or even irreducible regions. */
1518 if (bb == bb->loop_father->header)
1519 return 0;
1521 else
1523 FOR_EACH_EDGE (e, ei, bb->preds)
1524 if (e->flags & EDGE_DFS_BACK)
1526 may_be_loop_header = true;
1527 break;
1531 change = 0;
1532 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
1534 removed_p = 0;
1536 if (e->flags & EDGE_COMPLEX)
1538 ei_next (&ei);
1539 continue;
1542 /* We can't redirect edges from new basic blocks. */
1543 if (e->src->index >= bypass_last_basic_block)
1545 ei_next (&ei);
1546 continue;
1549 /* The irreducible loops created by redirecting of edges entering the
1550 loop from outside would decrease effectiveness of some of the
1551 following optimizations, so prevent this. */
1552 if (may_be_loop_header
1553 && !(e->flags & EDGE_DFS_BACK))
1555 ei_next (&ei);
1556 continue;
1559 for (i = 0; i < reg_use_count; i++)
1561 rtx reg_used = reg_use_table[i];
1562 unsigned int regno = REGNO (reg_used);
1563 basic_block dest, old_dest;
1564 struct expr *set;
1565 rtx src, new_rtx;
1567 set = find_bypass_set (regno, e->src->index);
1569 if (! set)
1570 continue;
1572 /* Check the data flow is valid after edge insertions. */
1573 if (e->insns.r && reg_killed_on_edge (reg_used, e))
1574 continue;
1576 src = SET_SRC (pc_set (jump));
1578 if (setcc != NULL)
1579 src = simplify_replace_rtx (src,
1580 SET_DEST (PATTERN (setcc)),
1581 SET_SRC (PATTERN (setcc)));
1583 new_rtx = simplify_replace_rtx (src, reg_used, set->src);
1585 /* Jump bypassing may have already placed instructions on
1586 edges of the CFG. We can't bypass an outgoing edge that
1587 has instructions associated with it, as these insns won't
1588 get executed if the incoming edge is redirected. */
1589 if (new_rtx == pc_rtx)
1591 edest = FALLTHRU_EDGE (bb);
1592 dest = edest->insns.r ? NULL : edest->dest;
1594 else if (GET_CODE (new_rtx) == LABEL_REF)
1596 dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0));
1597 /* Don't bypass edges containing instructions. */
1598 edest = find_edge (bb, dest);
1599 if (edest && edest->insns.r)
1600 dest = NULL;
1602 else
1603 dest = NULL;
1605 /* Avoid unification of the edge with other edges from original
1606 branch. We would end up emitting the instruction on "both"
1607 edges. */
1608 if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))
1609 && find_edge (e->src, dest))
1610 dest = NULL;
1612 old_dest = e->dest;
1613 if (dest != NULL
1614 && dest != old_dest
1615 && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1617 redirect_edge_and_branch_force (e, dest);
1619 /* Copy the register setter to the redirected edge.
1620 Don't copy CC0 setters, as CC0 is dead after jump. */
1621 if (setcc)
1623 rtx pat = PATTERN (setcc);
1624 if (!CC0_P (SET_DEST (pat)))
1625 insert_insn_on_edge (copy_insn (pat), e);
1628 if (dump_file != NULL)
1630 fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
1631 "in jump_insn %d equals constant ",
1632 regno, INSN_UID (jump));
1633 print_rtl (dump_file, set->src);
1634 fprintf (dump_file, "\n\t when BB %d is entered from "
1635 "BB %d. Redirect edge %d->%d to %d.\n",
1636 old_dest->index, e->src->index, e->src->index,
1637 old_dest->index, dest->index);
1639 change = 1;
1640 removed_p = 1;
1641 break;
1644 if (!removed_p)
1645 ei_next (&ei);
1647 return change;
1650 /* Find basic blocks with more than one predecessor that only contain a
1651 single conditional jump. If the result of the comparison is known at
1652 compile-time from any incoming edge, redirect that edge to the
1653 appropriate target. Return nonzero if a change was made.
1655 This function is now mis-named, because we also handle indirect jumps. */
1657 static int
1658 bypass_conditional_jumps (void)
1660 basic_block bb;
1661 int changed;
1662 rtx setcc;
1663 rtx insn;
1664 rtx dest;
1666 /* Note we start at block 1. */
1667 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1668 return 0;
1670 bypass_last_basic_block = last_basic_block_for_fn (cfun);
1671 mark_dfs_back_edges ();
1673 changed = 0;
1674 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
1675 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1677 /* Check for more than one predecessor. */
1678 if (!single_pred_p (bb))
1680 setcc = NULL_RTX;
1681 FOR_BB_INSNS (bb, insn)
1682 if (DEBUG_INSN_P (insn))
1683 continue;
1684 else if (NONJUMP_INSN_P (insn))
1686 if (setcc)
1687 break;
1688 if (GET_CODE (PATTERN (insn)) != SET)
1689 break;
1691 dest = SET_DEST (PATTERN (insn));
1692 if (REG_P (dest) || CC0_P (dest))
1693 setcc = insn;
1694 else
1695 break;
1697 else if (JUMP_P (insn))
1699 if ((any_condjump_p (insn) || computed_jump_p (insn))
1700 && onlyjump_p (insn))
1701 changed |= bypass_block (bb, setcc, insn);
1702 break;
1704 else if (INSN_P (insn))
1705 break;
1709 /* If we bypassed any register setting insns, we inserted a
1710 copy on the redirected edge. These need to be committed. */
1711 if (changed)
1712 commit_edge_insertions ();
1714 return changed;
1717 /* Return true if the graph is too expensive to optimize. PASS is the
1718 optimization about to be performed. */
1720 static bool
1721 is_too_expensive (const char *pass)
1723 /* Trying to perform global optimizations on flow graphs which have
1724 a high connectivity will take a long time and is unlikely to be
1725 particularly useful.
1727 In normal circumstances a cfg should have about twice as many
1728 edges as blocks. But we do not want to punish small functions
1729 which have a couple switch statements. Rather than simply
1730 threshold the number of blocks, uses something with a more
1731 graceful degradation. */
1732 if (n_edges_for_fn (cfun) > 20000 + n_basic_blocks_for_fn (cfun) * 4)
1734 warning (OPT_Wdisabled_optimization,
1735 "%s: %d basic blocks and %d edges/basic block",
1736 pass, n_basic_blocks_for_fn (cfun),
1737 n_edges_for_fn (cfun) / n_basic_blocks_for_fn (cfun));
1739 return true;
1742 /* If allocating memory for the cprop bitmap would take up too much
1743 storage it's better just to disable the optimization. */
1744 if ((n_basic_blocks_for_fn (cfun)
1745 * SBITMAP_SET_SIZE (max_reg_num ())
1746 * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
1748 warning (OPT_Wdisabled_optimization,
1749 "%s: %d basic blocks and %d registers",
1750 pass, n_basic_blocks_for_fn (cfun), max_reg_num ());
1752 return true;
1755 return false;
1758 /* Main function for the CPROP pass. */
1760 static int
1761 one_cprop_pass (void)
1763 int i;
1764 int changed = 0;
1766 /* Return if there's nothing to do, or it is too expensive. */
1767 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
1768 || is_too_expensive (_ ("const/copy propagation disabled")))
1769 return 0;
1771 global_const_prop_count = local_const_prop_count = 0;
1772 global_copy_prop_count = local_copy_prop_count = 0;
1774 bytes_used = 0;
1775 gcc_obstack_init (&cprop_obstack);
1777 /* Do a local const/copy propagation pass first. The global pass
1778 only handles global opportunities.
1779 If the local pass changes something, remove any unreachable blocks
1780 because the CPROP global dataflow analysis may get into infinite
1781 loops for CFGs with unreachable blocks.
1783 FIXME: This local pass should not be necessary after CSE (but for
1784 some reason it still is). It is also (proven) not necessary
1785 to run the local pass right after FWPWOP.
1787 FIXME: The global analysis would not get into infinite loops if it
1788 would use the DF solver (via df_simple_dataflow) instead of
1789 the solver implemented in this file. */
1790 changed |= local_cprop_pass ();
1791 if (changed)
1792 delete_unreachable_blocks ();
1794 /* Determine implicit sets. This may change the CFG (split critical
1795 edges if that exposes an implicit set).
1796 Note that find_implicit_sets() does not rely on up-to-date DF caches
1797 so that we do not have to re-run df_analyze() even if local CPROP
1798 changed something.
1799 ??? This could run earlier so that any uncovered implicit sets
1800 sets could be exploited in local_cprop_pass() also. Later. */
1801 changed |= find_implicit_sets ();
1803 /* If local_cprop_pass() or find_implicit_sets() changed something,
1804 run df_analyze() to bring all insn caches up-to-date, and to take
1805 new basic blocks from edge splitting on the DF radar.
1806 NB: This also runs the fast DCE pass, because execute_rtl_cprop
1807 sets DF_LR_RUN_DCE. */
1808 if (changed)
1809 df_analyze ();
1811 /* Initialize implicit_set_indexes array. */
1812 implicit_set_indexes = XNEWVEC (int, last_basic_block_for_fn (cfun));
1813 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
1814 implicit_set_indexes[i] = -1;
1816 alloc_hash_table (&set_hash_table);
1817 compute_hash_table (&set_hash_table);
1819 /* Free implicit_sets before peak usage. */
1820 free (implicit_sets);
1821 implicit_sets = NULL;
1823 if (dump_file)
1824 dump_hash_table (dump_file, "SET", &set_hash_table);
1825 if (set_hash_table.n_elems > 0)
1827 basic_block bb;
1828 rtx insn;
1830 alloc_cprop_mem (last_basic_block_for_fn (cfun),
1831 set_hash_table.n_elems);
1832 compute_cprop_data ();
1834 free (implicit_set_indexes);
1835 implicit_set_indexes = NULL;
1837 /* Allocate vars to track sets of regs. */
1838 reg_set_bitmap = ALLOC_REG_SET (NULL);
1840 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
1841 EXIT_BLOCK_PTR_FOR_FN (cfun),
1842 next_bb)
1844 /* Reset tables used to keep track of what's still valid [since
1845 the start of the block]. */
1846 reset_opr_set_tables ();
1848 FOR_BB_INSNS (bb, insn)
1849 if (INSN_P (insn))
1851 changed |= cprop_insn (insn);
1853 /* Keep track of everything modified by this insn. */
1854 /* ??? Need to be careful w.r.t. mods done to INSN.
1855 Don't call mark_oprs_set if we turned the
1856 insn into a NOTE, or deleted the insn. */
1857 if (! NOTE_P (insn) && ! INSN_DELETED_P (insn))
1858 mark_oprs_set (insn);
1862 changed |= bypass_conditional_jumps ();
1864 FREE_REG_SET (reg_set_bitmap);
1865 free_cprop_mem ();
1867 else
1869 free (implicit_set_indexes);
1870 implicit_set_indexes = NULL;
1873 free_hash_table (&set_hash_table);
1874 obstack_free (&cprop_obstack, NULL);
1876 if (dump_file)
1878 fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
1879 current_function_name (), n_basic_blocks_for_fn (cfun),
1880 bytes_used);
1881 fprintf (dump_file, "%d local const props, %d local copy props, ",
1882 local_const_prop_count, local_copy_prop_count);
1883 fprintf (dump_file, "%d global const props, %d global copy props\n\n",
1884 global_const_prop_count, global_copy_prop_count);
1887 return changed;
1890 /* All the passes implemented in this file. Each pass has its
1891 own gate and execute function, and at the end of the file a
1892 pass definition for passes.c.
1894 We do not construct an accurate cfg in functions which call
1895 setjmp, so none of these passes runs if the function calls
1896 setjmp.
1897 FIXME: Should just handle setjmp via REG_SETJMP notes. */
1899 static bool
1900 gate_rtl_cprop (void)
1902 return optimize > 0 && flag_gcse
1903 && !cfun->calls_setjmp
1904 && dbg_cnt (cprop);
1907 static unsigned int
1908 execute_rtl_cprop (void)
1910 int changed;
1911 delete_unreachable_blocks ();
1912 df_set_flags (DF_LR_RUN_DCE);
1913 df_analyze ();
1914 changed = one_cprop_pass ();
1915 flag_rerun_cse_after_global_opts |= changed;
1916 if (changed)
1917 cleanup_cfg (CLEANUP_CFG_CHANGED);
1918 return 0;
1921 namespace {
1923 const pass_data pass_data_rtl_cprop =
1925 RTL_PASS, /* type */
1926 "cprop", /* name */
1927 OPTGROUP_NONE, /* optinfo_flags */
1928 true, /* has_gate */
1929 true, /* has_execute */
1930 TV_CPROP, /* tv_id */
1931 PROP_cfglayout, /* properties_required */
1932 0, /* properties_provided */
1933 0, /* properties_destroyed */
1934 0, /* todo_flags_start */
1935 ( TODO_df_finish | TODO_verify_rtl_sharing
1936 | TODO_verify_flow ), /* todo_flags_finish */
1939 class pass_rtl_cprop : public rtl_opt_pass
1941 public:
1942 pass_rtl_cprop (gcc::context *ctxt)
1943 : rtl_opt_pass (pass_data_rtl_cprop, ctxt)
1946 /* opt_pass methods: */
1947 opt_pass * clone () { return new pass_rtl_cprop (m_ctxt); }
1948 bool gate () { return gate_rtl_cprop (); }
1949 unsigned int execute () { return execute_rtl_cprop (); }
1951 }; // class pass_rtl_cprop
1953 } // anon namespace
1955 rtl_opt_pass *
1956 make_pass_rtl_cprop (gcc::context *ctxt)
1958 return new pass_rtl_cprop (ctxt);