1 /* Global constant/copy propagation for RTL.
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
3 2006, 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
25 #include "diagnostic-core.h"
32 #include "hard-reg-set.h"
34 #include "insn-config.h"
36 #include "basic-block.h"
46 #include "tree-pass.h"
53 /* An obstack for our working variables. */
54 static struct obstack gcse_obstack;
56 struct reg_use {rtx reg_rtx; };
58 /* Hash table of expressions. */
62 /* The expression (SET_SRC for expressions, PATTERN for assignments). */
64 /* Index in the available expression bitmaps. */
66 /* Next entry with the same hash. */
67 struct expr *next_same_hash;
68 /* List of available occurrence in basic blocks in the function.
69 An "available occurrence" is one that is the last occurrence in the
70 basic block and the operands are not modified by following statements in
71 the basic block [including this insn]. */
72 struct occr *avail_occr;
75 /* Occurrence of an expression.
76 There is one per basic block. If a pattern appears more than once the
77 last appearance is used. */
81 /* Next occurrence of this expression. */
83 /* The insn that computes the expression. */
87 typedef struct occr *occr_t;
89 DEF_VEC_ALLOC_P (occr_t, heap);
91 /* Expression and copy propagation hash tables.
92 Each hash table is an array of buckets.
93 ??? It is known that if it were an array of entries, structure elements
94 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
95 not clear whether in the final analysis a sufficient amount of memory would
96 be saved as the size of the available expression bitmaps would be larger
97 [one could build a mapping table without holes afterwards though].
98 Someday I'll perform the computation and figure it out. */
103 This is an array of `set_hash_table_size' elements. */
106 /* Size of the hash table, in elements. */
109 /* Number of hash table elements. */
110 unsigned int n_elems;
113 /* Copy propagation hash table. */
114 static struct hash_table_d set_hash_table;
116 /* Array of implicit set patterns indexed by basic block index. */
117 static rtx *implicit_sets;
119 /* Bitmap containing one bit for each register in the program.
120 Used when performing GCSE to track which registers have been set since
121 the start of the basic block. */
122 static regset reg_set_bitmap;
124 /* Various variables for statistics gathering. */
126 /* Memory used in a pass.
127 This isn't intended to be absolutely precise. Its intent is only
128 to keep an eye on memory usage. */
129 static int bytes_used;
131 /* Number of local constants propagated. */
132 static int local_const_prop_count;
133 /* Number of local copies propagated. */
134 static int local_copy_prop_count;
135 /* Number of global constants propagated. */
136 static int global_const_prop_count;
137 /* Number of global copies propagated. */
138 static int global_copy_prop_count;
141 #define GNEW(T) ((T *) gmalloc (sizeof (T)))
143 #define GNEWVEC(T, N) ((T *) gmalloc (sizeof (T) * (N)))
145 #define GNEWVAR(T, S) ((T *) gmalloc ((S)))
147 #define GOBNEW(T) ((T *) gcse_alloc (sizeof (T)))
148 #define GOBNEWVAR(T, S) ((T *) gcse_alloc ((S)))
150 /* Cover function to xmalloc to record bytes allocated. */
153 gmalloc (size_t size)
156 return xmalloc (size);
159 /* Cover function to obstack_alloc. */
162 gcse_alloc (unsigned long size)
165 return obstack_alloc (&gcse_obstack, size);
168 /* Allocate memory for the reg/memory set tracking tables.
169 This is called at the start of each pass. */
172 alloc_gcse_mem (void)
174 /* Allocate vars to track sets of regs. */
175 reg_set_bitmap = ALLOC_REG_SET (NULL);
178 /* Free memory allocated by alloc_gcse_mem. */
183 FREE_REG_SET (reg_set_bitmap);
186 struct reg_avail_info
192 static struct reg_avail_info *reg_avail_info;
193 static basic_block current_bb;
195 /* Return nonzero if the operands of expression X are unchanged from
196 INSN to the end of INSN's basic block. */
199 oprs_available_p (const_rtx x, const_rtx insn)
213 struct reg_avail_info *info = ®_avail_info[REGNO (x)];
215 if (info->last_bb != current_bb)
217 return info->last_set < DF_INSN_LUID (insn);
245 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
249 if (! oprs_available_p (XEXP (x, i), insn))
252 else if (fmt[i] == 'E')
253 for (j = 0; j < XVECLEN (x, i); j++)
254 if (! oprs_available_p (XVECEXP (x, i, j), insn))
261 /* Hash a set of register REGNO.
263 Sets are hashed on the register that is set. This simplifies the PRE copy
266 ??? May need to make things more elaborate. Later, as necessary. */
269 hash_set (int regno, int hash_table_size)
274 return hash % hash_table_size;
277 /* Return nonzero if exp1 is equivalent to exp2. */
280 expr_equiv_p (const_rtx x, const_rtx y)
282 return exp_equiv_p (x, y, 0, true);
285 /* Insert pattern X in INSN in the hash table.
286 X is a SET of a reg to either another reg or a constant.
287 If it is already present, record it as the last occurrence in INSN's
291 insert_set_in_table (rtx x, rtx insn, struct hash_table_d *table)
295 struct expr *cur_expr, *last_expr = NULL;
296 struct occr *cur_occr;
298 gcc_assert (GET_CODE (x) == SET && REG_P (SET_DEST (x)));
300 hash = hash_set (REGNO (SET_DEST (x)), table->size);
302 cur_expr = table->table[hash];
305 while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
307 /* If the expression isn't found, save a pointer to the end of
309 last_expr = cur_expr;
310 cur_expr = cur_expr->next_same_hash;
315 cur_expr = GOBNEW (struct expr);
316 bytes_used += sizeof (struct expr);
317 if (table->table[hash] == NULL)
318 /* This is the first pattern that hashed to this index. */
319 table->table[hash] = cur_expr;
321 /* Add EXPR to end of this hash chain. */
322 last_expr->next_same_hash = cur_expr;
324 /* Set the fields of the expr element.
325 We must copy X because it can be modified when copy propagation is
326 performed on its operands. */
327 cur_expr->expr = copy_rtx (x);
328 cur_expr->bitmap_index = table->n_elems++;
329 cur_expr->next_same_hash = NULL;
330 cur_expr->avail_occr = NULL;
333 /* Now record the occurrence. */
334 cur_occr = cur_expr->avail_occr;
337 && BLOCK_FOR_INSN (cur_occr->insn) == BLOCK_FOR_INSN (insn))
339 /* Found another instance of the expression in the same basic block.
340 Prefer this occurrence to the currently recorded one. We want
341 the last one in the block and the block is scanned from start
343 cur_occr->insn = insn;
347 /* First occurrence of this expression in this basic block. */
348 cur_occr = GOBNEW (struct occr);
349 bytes_used += sizeof (struct occr);
350 cur_occr->insn = insn;
351 cur_occr->next = cur_expr->avail_occr;
352 cur_expr->avail_occr = cur_occr;
356 /* Determine whether the rtx X should be treated as a constant for
357 the purposes of GCSE's constant propagation. */
360 gcse_constant_p (const_rtx x)
362 /* Consider a COMPARE of two integers constant. */
363 if (GET_CODE (x) == COMPARE
364 && CONST_INT_P (XEXP (x, 0))
365 && CONST_INT_P (XEXP (x, 1)))
368 /* Consider a COMPARE of the same registers is a constant
369 if they are not floating point registers. */
370 if (GET_CODE(x) == COMPARE
371 && REG_P (XEXP (x, 0)) && REG_P (XEXP (x, 1))
372 && REGNO (XEXP (x, 0)) == REGNO (XEXP (x, 1))
373 && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 0)))
374 && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 1))))
377 /* Since X might be inserted more than once we have to take care that it
379 return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x));
382 /* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or
386 hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table)
388 rtx src = SET_SRC (pat);
389 rtx dest = SET_DEST (pat);
394 unsigned int regno = REGNO (dest);
397 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
399 This allows us to do a single GCSE pass and still eliminate
400 redundant constants, addresses or other expressions that are
401 constructed with multiple instructions.
403 However, keep the original SRC if INSN is a simple reg-reg move. In
404 In this case, there will almost always be a REG_EQUAL note on the
405 insn that sets SRC. By recording the REG_EQUAL value here as SRC
406 for INSN, we miss copy propagation opportunities and we perform the
407 same PRE GCSE operation repeatedly on the same REG_EQUAL value if we
408 do more than one PRE GCSE pass.
410 Note that this does not impede profitable constant propagations. We
411 "look through" reg-reg sets in lookup_avail_set. */
412 note = find_reg_equal_equiv_note (insn);
414 && REG_NOTE_KIND (note) == REG_EQUAL
416 && gcse_constant_p (XEXP (note, 0)))
417 src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest, src);
419 /* Record sets for constant/copy propagation. */
420 if (regno >= FIRST_PSEUDO_REGISTER
422 && REGNO (src) >= FIRST_PSEUDO_REGISTER
423 && can_copy_p (GET_MODE (dest))
424 && REGNO (src) != regno)
425 || gcse_constant_p (src))
426 /* A copy is not available if its src or dest is subsequently
427 modified. Here we want to search from INSN+1 on, but
428 oprs_available_p searches from INSN on. */
429 && (insn == BB_END (BLOCK_FOR_INSN (insn))
430 || (tmp = next_nonnote_nondebug_insn (insn)) == NULL_RTX
431 || BLOCK_FOR_INSN (tmp) != BLOCK_FOR_INSN (insn)
432 || oprs_available_p (pat, tmp)))
433 insert_set_in_table (pat, insn, table);
437 /* Process INSN and add hash table entries as appropriate.
439 Only available expressions that set a single pseudo-reg are recorded.
441 Single sets in a PARALLEL could be handled, but it's an extra complication
442 that isn't dealt with right now. The trick is handling the CLOBBERs that
443 are also in the PARALLEL. Later.
445 If SET_P is nonzero, this is for the assignment hash table,
446 otherwise it is for the expression hash table. */
449 hash_scan_insn (rtx insn, struct hash_table_d *table)
451 rtx pat = PATTERN (insn);
454 /* Pick out the sets of INSN and for other forms of instructions record
455 what's been modified. */
457 if (GET_CODE (pat) == SET)
458 hash_scan_set (pat, insn, table);
459 else if (GET_CODE (pat) == PARALLEL)
460 for (i = 0; i < XVECLEN (pat, 0); i++)
462 rtx x = XVECEXP (pat, 0, i);
464 if (GET_CODE (x) == SET)
465 hash_scan_set (x, insn, table);
470 dump_hash_table (FILE *file, const char *name, struct hash_table_d *table)
473 /* Flattened out table, so it's printed in proper order. */
474 struct expr **flat_table;
475 unsigned int *hash_val;
478 flat_table = XCNEWVEC (struct expr *, table->n_elems);
479 hash_val = XNEWVEC (unsigned int, table->n_elems);
481 for (i = 0; i < (int) table->size; i++)
482 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
484 flat_table[expr->bitmap_index] = expr;
485 hash_val[expr->bitmap_index] = i;
488 fprintf (file, "%s hash table (%d buckets, %d entries)\n",
489 name, table->size, table->n_elems);
491 for (i = 0; i < (int) table->n_elems; i++)
492 if (flat_table[i] != 0)
494 expr = flat_table[i];
495 fprintf (file, "Index %d (hash value %d)\n ",
496 expr->bitmap_index, hash_val[i]);
497 print_rtl (file, expr->expr);
498 fprintf (file, "\n");
501 fprintf (file, "\n");
507 /* Record register first/last/block set information for REGNO in INSN.
509 last_set records the last place in the block where the register
510 is set and is used to compute "availability".
512 last_bb records the block for which last_set is valid, as a quick
513 test to invalidate it. */
516 record_last_reg_set_info (rtx insn, int regno)
518 struct reg_avail_info *info = ®_avail_info[regno];
519 int luid = DF_INSN_LUID (insn);
521 info->last_set = luid;
522 if (info->last_bb != current_bb)
523 info->last_bb = current_bb;
526 /* Called from compute_hash_table via note_stores to handle one
527 SET or CLOBBER in an insn. DATA is really the instruction in which
528 the SET is taking place. */
531 record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data)
533 rtx last_set_insn = (rtx) data;
535 if (GET_CODE (dest) == SUBREG)
536 dest = SUBREG_REG (dest);
539 record_last_reg_set_info (last_set_insn, REGNO (dest));
542 /* Top level function to create an assignments hash table.
544 Assignment entries are placed in the hash table if
545 - they are of the form (set (pseudo-reg) src),
546 - src is something we want to perform const/copy propagation on,
547 - none of the operands or target are subsequently modified in the block
549 Currently src must be a pseudo-reg or a const_int.
551 TABLE is the table computed. */
554 compute_hash_table_work (struct hash_table_d *table)
558 /* Some working arrays used to track first and last set in each block. */
559 reg_avail_info = GNEWVEC (struct reg_avail_info, max_reg_num ());
561 for (i = 0; i < max_reg_num (); ++i)
562 reg_avail_info[i].last_bb = NULL;
564 FOR_EACH_BB (current_bb)
569 /* First pass over the instructions records information used to
570 determine when registers and memory are first and last set. */
571 FOR_BB_INSNS (current_bb, insn)
573 if (!NONDEBUG_INSN_P (insn))
578 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
579 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
580 record_last_reg_set_info (insn, regno);
583 note_stores (PATTERN (insn), record_last_set_info, insn);
586 /* Insert implicit sets in the hash table. */
587 if (implicit_sets[current_bb->index] != NULL_RTX)
588 hash_scan_set (implicit_sets[current_bb->index],
589 BB_HEAD (current_bb), table);
591 /* The next pass builds the hash table. */
592 FOR_BB_INSNS (current_bb, insn)
593 if (NONDEBUG_INSN_P (insn))
594 hash_scan_insn (insn, table);
597 free (reg_avail_info);
598 reg_avail_info = NULL;
601 /* Allocate space for the set/expr hash TABLE.
602 It is used to determine the number of buckets to use. */
605 alloc_hash_table (struct hash_table_d *table)
609 n = get_max_insn_count ();
612 if (table->size < 11)
615 /* Attempt to maintain efficient use of hash table.
616 Making it an odd number is simplest for now.
617 ??? Later take some measurements. */
619 n = table->size * sizeof (struct expr *);
620 table->table = GNEWVAR (struct expr *, n);
623 /* Free things allocated by alloc_hash_table. */
626 free_hash_table (struct hash_table_d *table)
631 /* Compute the hash TABLE for doing copy/const propagation or
632 expression hash table. */
635 compute_hash_table (struct hash_table_d *table)
637 /* Initialize count of number of entries in hash table. */
639 memset (table->table, 0, table->size * sizeof (struct expr *));
641 compute_hash_table_work (table);
644 /* Expression tracking support. */
646 /* Lookup REGNO in the set TABLE. The result is a pointer to the
647 table entry, or NULL if not found. */
650 lookup_set (unsigned int regno, struct hash_table_d *table)
652 unsigned int hash = hash_set (regno, table->size);
655 expr = table->table[hash];
657 while (expr && REGNO (SET_DEST (expr->expr)) != regno)
658 expr = expr->next_same_hash;
663 /* Return the next entry for REGNO in list EXPR. */
666 next_set (unsigned int regno, struct expr *expr)
669 expr = expr->next_same_hash;
670 while (expr && REGNO (SET_DEST (expr->expr)) != regno);
675 /* Reset tables used to keep track of what's still available [since the
676 start of the block]. */
679 reset_opr_set_tables (void)
681 /* Maintain a bitmap of which regs have been set since beginning of
683 CLEAR_REG_SET (reg_set_bitmap);
686 /* Return nonzero if the operands of X are not set before INSN in
687 INSN's basic block. */
690 oprs_not_set_p (const_rtx x, const_rtx insn)
716 return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
722 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
726 /* If we are about to do the last recursive call
727 needed at this level, change it into iteration.
728 This function is called enough to be worth it. */
730 return oprs_not_set_p (XEXP (x, i), insn);
732 if (! oprs_not_set_p (XEXP (x, i), insn))
735 else if (fmt[i] == 'E')
736 for (j = 0; j < XVECLEN (x, i); j++)
737 if (! oprs_not_set_p (XVECEXP (x, i, j), insn))
744 /* Mark things set by a SET. */
747 mark_set (rtx pat, rtx insn ATTRIBUTE_UNUSED)
749 rtx dest = SET_DEST (pat);
751 while (GET_CODE (dest) == SUBREG
752 || GET_CODE (dest) == ZERO_EXTRACT
753 || GET_CODE (dest) == STRICT_LOW_PART)
754 dest = XEXP (dest, 0);
757 SET_REGNO_REG_SET (reg_set_bitmap, REGNO (dest));
760 /* Record things set by a CLOBBER. */
763 mark_clobber (rtx pat, rtx insn ATTRIBUTE_UNUSED)
765 rtx clob = XEXP (pat, 0);
767 while (GET_CODE (clob) == SUBREG || GET_CODE (clob) == STRICT_LOW_PART)
768 clob = XEXP (clob, 0);
771 SET_REGNO_REG_SET (reg_set_bitmap, REGNO (clob));
774 /* Record things set by INSN.
775 This data is used by oprs_not_set_p. */
778 mark_oprs_set (rtx insn)
780 rtx pat = PATTERN (insn);
783 if (GET_CODE (pat) == SET)
784 mark_set (pat, insn);
785 else if (GET_CODE (pat) == PARALLEL)
786 for (i = 0; i < XVECLEN (pat, 0); i++)
788 rtx x = XVECEXP (pat, 0, i);
790 if (GET_CODE (x) == SET)
792 else if (GET_CODE (x) == CLOBBER)
793 mark_clobber (x, insn);
796 else if (GET_CODE (pat) == CLOBBER)
797 mark_clobber (pat, insn);
801 /* Compute copy/constant propagation working variables. */
803 /* Local properties of assignments. */
804 static sbitmap *cprop_pavloc;
805 static sbitmap *cprop_absaltered;
807 /* Global properties of assignments (computed from the local properties). */
808 static sbitmap *cprop_avin;
809 static sbitmap *cprop_avout;
811 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
812 basic blocks. N_SETS is the number of sets. */
815 alloc_cprop_mem (int n_blocks, int n_sets)
817 cprop_pavloc = sbitmap_vector_alloc (n_blocks, n_sets);
818 cprop_absaltered = sbitmap_vector_alloc (n_blocks, n_sets);
820 cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
821 cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
824 /* Free vars used by copy/const propagation. */
827 free_cprop_mem (void)
829 sbitmap_vector_free (cprop_pavloc);
830 sbitmap_vector_free (cprop_absaltered);
831 sbitmap_vector_free (cprop_avin);
832 sbitmap_vector_free (cprop_avout);
835 /* For each block, compute whether X is transparent. X is either an
836 expression or an assignment [though we don't care which, for this context
837 an assignment is treated as an expression]. For each block where an
838 element of X is modified, set the INDX bit in BMAP. */
841 compute_transp (const_rtx x, int indx, sbitmap *bmap)
847 /* repeat is used to turn tail-recursion into iteration since GCC
848 can't do it when there's no return value. */
860 for (def = DF_REG_DEF_CHAIN (REGNO (x));
862 def = DF_REF_NEXT_REG (def))
863 SET_BIT (bmap[DF_REF_BB (def)->index], indx);
884 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
888 /* If we are about to do the last recursive call
889 needed at this level, change it into iteration.
890 This function is called enough to be worth it. */
897 compute_transp (XEXP (x, i), indx, bmap);
899 else if (fmt[i] == 'E')
900 for (j = 0; j < XVECLEN (x, i); j++)
901 compute_transp (XVECEXP (x, i, j), indx, bmap);
905 /* Compute the local properties of each recorded expression.
907 Local properties are those that are defined by the block, irrespective of
910 An expression is transparent in a block if its operands are not modified
913 An expression is computed (locally available) in a block if it is computed
914 at least once and expression would contain the same value if the
915 computation was moved to the end of the block.
917 TRANSP and COMP are destination sbitmaps for recording local properties.
918 If NULL, then it is not necessary to compute or record that particular
921 TRANSP is computed as ~TRANSP, since this is really cprop's ABSALTERED. */
924 compute_local_properties (sbitmap *transp, sbitmap *comp,
925 struct hash_table_d *table)
929 /* Initialize any bitmaps that were passed in. */
932 sbitmap_vector_zero (transp, last_basic_block);
936 sbitmap_vector_zero (comp, last_basic_block);
938 for (i = 0; i < table->size; i++)
942 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
944 int indx = expr->bitmap_index;
947 /* The expression is transparent in this block if it is not killed.
948 We start by assuming all are transparent [none are killed], and
949 then reset the bits for those that are. */
951 compute_transp (expr->expr, indx, transp);
953 /* The occurrences recorded in avail_occr are exactly those that
954 we want to set to nonzero in COMP. */
956 for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
958 SET_BIT (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
964 /* Hash table support. */
966 /* Top level routine to do the dataflow analysis needed by copy/const
970 compute_cprop_data (void)
972 compute_local_properties (cprop_absaltered, cprop_pavloc, &set_hash_table);
973 compute_available (cprop_pavloc, cprop_absaltered,
974 cprop_avout, cprop_avin);
977 /* Copy/constant propagation. */
979 /* Maximum number of register uses in an insn that we handle. */
982 /* Table of uses found in an insn.
983 Allocated statically to avoid alloc/free complexity and overhead. */
984 static struct reg_use reg_use_table[MAX_USES];
986 /* Index into `reg_use_table' while building it. */
987 static int reg_use_count;
989 /* Set up a list of register numbers used in INSN. The found uses are stored
990 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
991 and contains the number of uses in the table upon exit.
993 ??? If a register appears multiple times we will record it multiple times.
994 This doesn't hurt anything but it will slow things down. */
997 find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED)
1004 /* repeat is used to turn tail-recursion into iteration since GCC
1005 can't do it when there's no return value. */
1010 code = GET_CODE (x);
1013 if (reg_use_count == MAX_USES)
1016 reg_use_table[reg_use_count].reg_rtx = x;
1020 /* Recursively scan the operands of this expression. */
1022 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
1026 /* If we are about to do the last recursive call
1027 needed at this level, change it into iteration.
1028 This function is called enough to be worth it. */
1035 find_used_regs (&XEXP (x, i), data);
1037 else if (fmt[i] == 'E')
1038 for (j = 0; j < XVECLEN (x, i); j++)
1039 find_used_regs (&XVECEXP (x, i, j), data);
1043 /* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO.
1044 Returns nonzero is successful. */
1047 try_replace_reg (rtx from, rtx to, rtx insn)
1049 rtx note = find_reg_equal_equiv_note (insn);
1052 rtx set = single_set (insn);
1054 /* Usually we substitute easy stuff, so we won't copy everything.
1055 We however need to take care to not duplicate non-trivial CONST
1059 validate_replace_src_group (from, to, insn);
1060 if (num_changes_pending () && apply_change_group ())
1063 /* Try to simplify SET_SRC if we have substituted a constant. */
1064 if (success && set && CONSTANT_P (to))
1066 src = simplify_rtx (SET_SRC (set));
1069 validate_change (insn, &SET_SRC (set), src, 0);
1072 /* If there is already a REG_EQUAL note, update the expression in it
1073 with our replacement. */
1074 if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
1075 set_unique_reg_note (insn, REG_EQUAL,
1076 simplify_replace_rtx (XEXP (note, 0), from, to));
1077 if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
1079 /* If above failed and this is a single set, try to simplify the source of
1080 the set given our substitution. We could perhaps try this for multiple
1081 SETs, but it probably won't buy us anything. */
1082 src = simplify_replace_rtx (SET_SRC (set), from, to);
1084 if (!rtx_equal_p (src, SET_SRC (set))
1085 && validate_change (insn, &SET_SRC (set), src, 0))
1088 /* If we've failed perform the replacement, have a single SET to
1089 a REG destination and don't yet have a note, add a REG_EQUAL note
1090 to not lose information. */
1091 if (!success && note == 0 && set != 0 && REG_P (SET_DEST (set)))
1092 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
1095 /* REG_EQUAL may get simplified into register.
1096 We don't allow that. Remove that note. This code ought
1097 not to happen, because previous code ought to synthesize
1098 reg-reg move, but be on the safe side. */
1099 if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0)))
1100 remove_note (insn, note);
1105 /* Find a set of REGNOs that are available on entry to INSN's block. Returns
1106 NULL no such set is found. */
1108 static struct expr *
1109 find_avail_set (int regno, rtx insn)
1111 /* SET1 contains the last set found that can be returned to the caller for
1112 use in a substitution. */
1113 struct expr *set1 = 0;
1115 /* Loops are not possible here. To get a loop we would need two sets
1116 available at the start of the block containing INSN. i.e. we would
1117 need two sets like this available at the start of the block:
1119 (set (reg X) (reg Y))
1120 (set (reg Y) (reg X))
1122 This can not happen since the set of (reg Y) would have killed the
1123 set of (reg X) making it unavailable at the start of this block. */
1127 struct expr *set = lookup_set (regno, &set_hash_table);
1129 /* Find a set that is available at the start of the block
1130 which contains INSN. */
1133 if (TEST_BIT (cprop_avin[BLOCK_FOR_INSN (insn)->index],
1136 set = next_set (regno, set);
1139 /* If no available set was found we've reached the end of the
1140 (possibly empty) copy chain. */
1144 gcc_assert (GET_CODE (set->expr) == SET);
1146 src = SET_SRC (set->expr);
1148 /* We know the set is available.
1149 Now check that SRC is locally anticipatable (i.e. none of the
1150 source operands have changed since the start of the block).
1152 If the source operand changed, we may still use it for the next
1153 iteration of this loop, but we may not use it for substitutions. */
1155 if (gcse_constant_p (src) || oprs_not_set_p (src, insn))
1158 /* If the source of the set is anything except a register, then
1159 we have reached the end of the copy chain. */
1163 /* Follow the copy chain, i.e. start another iteration of the loop
1164 and see if we have an available copy into SRC. */
1165 regno = REGNO (src);
1168 /* SET1 holds the last set that was available and anticipatable at
1173 /* Subroutine of cprop_insn that tries to propagate constants into
1174 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
1175 it is the instruction that immediately precedes JUMP, and must be a
1176 single SET of a register. FROM is what we will try to replace,
1177 SRC is the constant we will try to substitute for it. Returns nonzero
1178 if a change was made. */
1181 cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src)
1183 rtx new_rtx, set_src, note_src;
1184 rtx set = pc_set (jump);
1185 rtx note = find_reg_equal_equiv_note (jump);
1189 note_src = XEXP (note, 0);
1190 if (GET_CODE (note_src) == EXPR_LIST)
1191 note_src = NULL_RTX;
1193 else note_src = NULL_RTX;
1195 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
1196 set_src = note_src ? note_src : SET_SRC (set);
1198 /* First substitute the SETCC condition into the JUMP instruction,
1199 then substitute that given values into this expanded JUMP. */
1200 if (setcc != NULL_RTX
1201 && !modified_between_p (from, setcc, jump)
1202 && !modified_between_p (src, setcc, jump))
1205 rtx setcc_set = single_set (setcc);
1206 rtx setcc_note = find_reg_equal_equiv_note (setcc);
1207 setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST)
1208 ? XEXP (setcc_note, 0) : SET_SRC (setcc_set);
1209 set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set),
1215 new_rtx = simplify_replace_rtx (set_src, from, src);
1217 /* If no simplification can be made, then try the next register. */
1218 if (rtx_equal_p (new_rtx, SET_SRC (set)))
1221 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
1222 if (new_rtx == pc_rtx)
1226 /* Ensure the value computed inside the jump insn to be equivalent
1227 to one computed by setcc. */
1228 if (setcc && modified_in_p (new_rtx, setcc))
1230 if (! validate_unshare_change (jump, &SET_SRC (set), new_rtx, 0))
1232 /* When (some) constants are not valid in a comparison, and there
1233 are two registers to be replaced by constants before the entire
1234 comparison can be folded into a constant, we need to keep
1235 intermediate information in REG_EQUAL notes. For targets with
1236 separate compare insns, such notes are added by try_replace_reg.
1237 When we have a combined compare-and-branch instruction, however,
1238 we need to attach a note to the branch itself to make this
1239 optimization work. */
1241 if (!rtx_equal_p (new_rtx, note_src))
1242 set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new_rtx));
1246 /* Remove REG_EQUAL note after simplification. */
1248 remove_note (jump, note);
1252 /* Delete the cc0 setter. */
1253 if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
1254 delete_insn (setcc);
1257 global_const_prop_count++;
1258 if (dump_file != NULL)
1261 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with constant ",
1262 REGNO (from), INSN_UID (jump));
1263 print_rtl (dump_file, src);
1264 fprintf (dump_file, "\n");
1266 purge_dead_edges (bb);
1268 /* If a conditional jump has been changed into unconditional jump, remove
1269 the jump and make the edge fallthru - this is always called in
1271 if (new_rtx != pc_rtx && simplejump_p (jump))
1276 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ei_next (&ei))
1277 if (e->dest != EXIT_BLOCK_PTR
1278 && BB_HEAD (e->dest) == JUMP_LABEL (jump))
1280 e->flags |= EDGE_FALLTHRU;
1290 constprop_register (rtx insn, rtx from, rtx to)
1294 /* Check for reg or cc0 setting instructions followed by
1295 conditional branch instructions first. */
1296 if ((sset = single_set (insn)) != NULL
1298 && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
1300 rtx dest = SET_DEST (sset);
1301 if ((REG_P (dest) || CC0_P (dest))
1302 && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to))
1306 /* Handle normal insns next. */
1307 if (NONJUMP_INSN_P (insn)
1308 && try_replace_reg (from, to, insn))
1311 /* Try to propagate a CONST_INT into a conditional jump.
1312 We're pretty specific about what we will handle in this
1313 code, we can extend this as necessary over time.
1315 Right now the insn in question must look like
1316 (set (pc) (if_then_else ...)) */
1317 else if (any_condjump_p (insn) && onlyjump_p (insn))
1318 return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
1322 /* Perform constant and copy propagation on INSN.
1323 The result is nonzero if a change was made. */
1326 cprop_insn (rtx insn)
1328 struct reg_use *reg_used;
1336 note_uses (&PATTERN (insn), find_used_regs, NULL);
1338 note = find_reg_equal_equiv_note (insn);
1340 /* We may win even when propagating constants into notes. */
1342 find_used_regs (&XEXP (note, 0), NULL);
1344 for (reg_used = ®_use_table[0]; reg_use_count > 0;
1345 reg_used++, reg_use_count--)
1347 unsigned int regno = REGNO (reg_used->reg_rtx);
1351 /* If the register has already been set in this block, there's
1352 nothing we can do. */
1353 if (! oprs_not_set_p (reg_used->reg_rtx, insn))
1356 /* Find an assignment that sets reg_used and is available
1357 at the start of the block. */
1358 set = find_avail_set (regno, insn);
1363 /* ??? We might be able to handle PARALLELs. Later. */
1364 gcc_assert (GET_CODE (pat) == SET);
1366 src = SET_SRC (pat);
1368 /* Constant propagation. */
1369 if (gcse_constant_p (src))
1371 if (constprop_register (insn, reg_used->reg_rtx, src))
1374 global_const_prop_count++;
1375 if (dump_file != NULL)
1377 fprintf (dump_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
1378 fprintf (dump_file, "insn %d with constant ", INSN_UID (insn));
1379 print_rtl (dump_file, src);
1380 fprintf (dump_file, "\n");
1382 if (INSN_DELETED_P (insn))
1386 else if (REG_P (src)
1387 && REGNO (src) >= FIRST_PSEUDO_REGISTER
1388 && REGNO (src) != regno)
1390 if (try_replace_reg (reg_used->reg_rtx, src, insn))
1393 global_copy_prop_count++;
1394 if (dump_file != NULL)
1396 fprintf (dump_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1397 regno, INSN_UID (insn));
1398 fprintf (dump_file, " with reg %d\n", REGNO (src));
1401 /* The original insn setting reg_used may or may not now be
1402 deletable. We leave the deletion to flow. */
1403 /* FIXME: If it turns out that the insn isn't deletable,
1404 then we may have unnecessarily extended register lifetimes
1405 and made things worse. */
1410 if (changed && DEBUG_INSN_P (insn))
1416 /* Like find_used_regs, but avoid recording uses that appear in
1417 input-output contexts such as zero_extract or pre_dec. This
1418 restricts the cases we consider to those for which local cprop
1419 can legitimately make replacements. */
1422 local_cprop_find_used_regs (rtx *xptr, void *data)
1429 switch (GET_CODE (x))
1433 case STRICT_LOW_PART:
1442 /* Can only legitimately appear this early in the context of
1443 stack pushes for function arguments, but handle all of the
1444 codes nonetheless. */
1448 /* Setting a subreg of a register larger than word_mode leaves
1449 the non-written words unchanged. */
1450 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) > BITS_PER_WORD)
1458 find_used_regs (xptr, data);
1461 /* Try to perform local const/copy propagation on X in INSN. */
1464 do_local_cprop (rtx x, rtx insn)
1466 rtx newreg = NULL, newcnst = NULL;
1468 /* Rule out USE instructions and ASM statements as we don't want to
1469 change the hard registers mentioned. */
1471 && (REGNO (x) >= FIRST_PSEUDO_REGISTER
1472 || (GET_CODE (PATTERN (insn)) != USE
1473 && asm_noperands (PATTERN (insn)) < 0)))
1475 cselib_val *val = cselib_lookup (x, GET_MODE (x), 0, VOIDmode);
1476 struct elt_loc_list *l;
1480 for (l = val->locs; l; l = l->next)
1482 rtx this_rtx = l->loc;
1485 if (gcse_constant_p (this_rtx))
1487 if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
1488 /* Don't copy propagate if it has attached REG_EQUIV note.
1489 At this point this only function parameters should have
1490 REG_EQUIV notes and if the argument slot is used somewhere
1491 explicitly, it means address of parameter has been taken,
1492 so we should not extend the lifetime of the pseudo. */
1493 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
1494 || ! MEM_P (XEXP (note, 0))))
1497 if (newcnst && constprop_register (insn, x, newcnst))
1499 if (dump_file != NULL)
1501 fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ",
1503 fprintf (dump_file, "insn %d with constant ",
1505 print_rtl (dump_file, newcnst);
1506 fprintf (dump_file, "\n");
1508 local_const_prop_count++;
1511 else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
1513 if (dump_file != NULL)
1516 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1517 REGNO (x), INSN_UID (insn));
1518 fprintf (dump_file, " with reg %d\n", REGNO (newreg));
1520 local_copy_prop_count++;
1527 /* Do local const/copy propagation (i.e. within each basic block). */
1530 local_cprop_pass (void)
1534 struct reg_use *reg_used;
1535 bool changed = false;
1540 FOR_BB_INSNS (bb, insn)
1544 rtx note = find_reg_equal_equiv_note (insn);
1548 note_uses (&PATTERN (insn), local_cprop_find_used_regs,
1551 local_cprop_find_used_regs (&XEXP (note, 0), NULL);
1553 for (reg_used = ®_use_table[0]; reg_use_count > 0;
1554 reg_used++, reg_use_count--)
1556 if (do_local_cprop (reg_used->reg_rtx, insn))
1562 if (INSN_DELETED_P (insn))
1565 while (reg_use_count);
1567 cselib_process_insn (insn);
1570 /* Forget everything at the end of a basic block. */
1571 cselib_clear_table ();
1579 /* Similar to get_condition, only the resulting condition must be
1580 valid at JUMP, instead of at EARLIEST.
1582 This differs from noce_get_condition in ifcvt.c in that we prefer not to
1583 settle for the condition variable in the jump instruction being integral.
1584 We prefer to be able to record the value of a user variable, rather than
1585 the value of a temporary used in a condition. This could be solved by
1586 recording the value of *every* register scanned by canonicalize_condition,
1587 but this would require some code reorganization. */
1590 fis_get_condition (rtx jump)
1592 return get_condition (jump, NULL, false, true);
1595 /* Check the comparison COND to see if we can safely form an implicit set from
1596 it. COND is either an EQ or NE comparison. */
1599 implicit_set_cond_p (const_rtx cond)
1601 const enum machine_mode mode = GET_MODE (XEXP (cond, 0));
1602 const_rtx cst = XEXP (cond, 1);
1604 /* We can't perform this optimization if either operand might be or might
1605 contain a signed zero. */
1606 if (HONOR_SIGNED_ZEROS (mode))
1608 /* It is sufficient to check if CST is or contains a zero. We must
1609 handle float, complex, and vector. If any subpart is a zero, then
1610 the optimization can't be performed. */
1611 /* ??? The complex and vector checks are not implemented yet. We just
1612 always return zero for them. */
1613 if (GET_CODE (cst) == CONST_DOUBLE)
1616 REAL_VALUE_FROM_CONST_DOUBLE (d, cst);
1617 if (REAL_VALUES_EQUAL (d, dconst0))
1624 return gcse_constant_p (cst);
1627 /* Find the implicit sets of a function. An "implicit set" is a constraint
1628 on the value of a variable, implied by a conditional jump. For example,
1629 following "if (x == 2)", the then branch may be optimized as though the
1630 conditional performed an "explicit set", in this example, "x = 2". This
1631 function records the set patterns that are implicit at the start of each
1634 FIXME: This would be more effective if critical edges are pre-split. As
1635 it is now, we can't record implicit sets for blocks that have
1636 critical successor edges. This results in missed optimizations
1637 and in more (unnecessary) work in cfgcleanup.c:thread_jump(). */
1640 find_implicit_sets (void)
1642 basic_block bb, dest;
1648 /* Check for more than one successor. */
1649 if (EDGE_COUNT (bb->succs) > 1)
1651 cond = fis_get_condition (BB_END (bb));
1654 && (GET_CODE (cond) == EQ || GET_CODE (cond) == NE)
1655 && REG_P (XEXP (cond, 0))
1656 && REGNO (XEXP (cond, 0)) >= FIRST_PSEUDO_REGISTER
1657 && implicit_set_cond_p (cond))
1659 dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest
1660 : FALLTHRU_EDGE (bb)->dest;
1663 /* Record nothing for a critical edge. */
1664 && single_pred_p (dest)
1665 && dest != EXIT_BLOCK_PTR)
1667 new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
1669 implicit_sets[dest->index] = new_rtx;
1672 fprintf(dump_file, "Implicit set of reg %d in ",
1673 REGNO (XEXP (cond, 0)));
1674 fprintf(dump_file, "basic block %d\n", dest->index);
1682 fprintf (dump_file, "Found %d implicit sets\n", count);
1685 /* Bypass conditional jumps. */
1687 /* The value of last_basic_block at the beginning of the jump_bypass
1688 pass. The use of redirect_edge_and_branch_force may introduce new
1689 basic blocks, but the data flow analysis is only valid for basic
1690 block indices less than bypass_last_basic_block. */
1692 static int bypass_last_basic_block;
1694 /* Find a set of REGNO to a constant that is available at the end of basic
1695 block BB. Returns NULL if no such set is found. Based heavily upon
1698 static struct expr *
1699 find_bypass_set (int regno, int bb)
1701 struct expr *result = 0;
1706 struct expr *set = lookup_set (regno, &set_hash_table);
1710 if (TEST_BIT (cprop_avout[bb], set->bitmap_index))
1712 set = next_set (regno, set);
1718 gcc_assert (GET_CODE (set->expr) == SET);
1720 src = SET_SRC (set->expr);
1721 if (gcse_constant_p (src))
1727 regno = REGNO (src);
1733 /* Subroutine of bypass_block that checks whether a pseudo is killed by
1734 any of the instructions inserted on an edge. Jump bypassing places
1735 condition code setters on CFG edges using insert_insn_on_edge. This
1736 function is required to check that our data flow analysis is still
1737 valid prior to commit_edge_insertions. */
1740 reg_killed_on_edge (const_rtx reg, const_edge e)
1744 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
1745 if (INSN_P (insn) && reg_set_p (reg, insn))
1751 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1752 basic block BB which has more than one predecessor. If not NULL, SETCC
1753 is the first instruction of BB, which is immediately followed by JUMP_INSN
1754 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1755 Returns nonzero if a change was made.
1757 During the jump bypassing pass, we may place copies of SETCC instructions
1758 on CFG edges. The following routine must be careful to pay attention to
1759 these inserted insns when performing its transformations. */
1762 bypass_block (basic_block bb, rtx setcc, rtx jump)
1767 int may_be_loop_header;
1771 insn = (setcc != NULL) ? setcc : jump;
1773 /* Determine set of register uses in INSN. */
1775 note_uses (&PATTERN (insn), find_used_regs, NULL);
1776 note = find_reg_equal_equiv_note (insn);
1778 find_used_regs (&XEXP (note, 0), NULL);
1780 may_be_loop_header = false;
1781 FOR_EACH_EDGE (e, ei, bb->preds)
1782 if (e->flags & EDGE_DFS_BACK)
1784 may_be_loop_header = true;
1789 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
1793 if (e->flags & EDGE_COMPLEX)
1799 /* We can't redirect edges from new basic blocks. */
1800 if (e->src->index >= bypass_last_basic_block)
1806 /* The irreducible loops created by redirecting of edges entering the
1807 loop from outside would decrease effectiveness of some of the following
1808 optimizations, so prevent this. */
1809 if (may_be_loop_header
1810 && !(e->flags & EDGE_DFS_BACK))
1816 for (i = 0; i < reg_use_count; i++)
1818 struct reg_use *reg_used = ®_use_table[i];
1819 unsigned int regno = REGNO (reg_used->reg_rtx);
1820 basic_block dest, old_dest;
1824 set = find_bypass_set (regno, e->src->index);
1829 /* Check the data flow is valid after edge insertions. */
1830 if (e->insns.r && reg_killed_on_edge (reg_used->reg_rtx, e))
1833 src = SET_SRC (pc_set (jump));
1836 src = simplify_replace_rtx (src,
1837 SET_DEST (PATTERN (setcc)),
1838 SET_SRC (PATTERN (setcc)));
1840 new_rtx = simplify_replace_rtx (src, reg_used->reg_rtx,
1841 SET_SRC (set->expr));
1843 /* Jump bypassing may have already placed instructions on
1844 edges of the CFG. We can't bypass an outgoing edge that
1845 has instructions associated with it, as these insns won't
1846 get executed if the incoming edge is redirected. */
1848 if (new_rtx == pc_rtx)
1850 edest = FALLTHRU_EDGE (bb);
1851 dest = edest->insns.r ? NULL : edest->dest;
1853 else if (GET_CODE (new_rtx) == LABEL_REF)
1855 dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0));
1856 /* Don't bypass edges containing instructions. */
1857 edest = find_edge (bb, dest);
1858 if (edest && edest->insns.r)
1864 /* Avoid unification of the edge with other edges from original
1865 branch. We would end up emitting the instruction on "both"
1868 if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))
1869 && find_edge (e->src, dest))
1875 && dest != EXIT_BLOCK_PTR)
1877 redirect_edge_and_branch_force (e, dest);
1879 /* Copy the register setter to the redirected edge.
1880 Don't copy CC0 setters, as CC0 is dead after jump. */
1883 rtx pat = PATTERN (setcc);
1884 if (!CC0_P (SET_DEST (pat)))
1885 insert_insn_on_edge (copy_insn (pat), e);
1888 if (dump_file != NULL)
1890 fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
1891 "in jump_insn %d equals constant ",
1892 regno, INSN_UID (jump));
1893 print_rtl (dump_file, SET_SRC (set->expr));
1894 fprintf (dump_file, "\nBypass edge from %d->%d to %d\n",
1895 e->src->index, old_dest->index, dest->index);
1908 /* Find basic blocks with more than one predecessor that only contain a
1909 single conditional jump. If the result of the comparison is known at
1910 compile-time from any incoming edge, redirect that edge to the
1911 appropriate target. Returns nonzero if a change was made.
1913 This function is now mis-named, because we also handle indirect jumps. */
1916 bypass_conditional_jumps (void)
1924 /* Note we start at block 1. */
1925 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
1928 bypass_last_basic_block = last_basic_block;
1929 mark_dfs_back_edges ();
1932 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb,
1933 EXIT_BLOCK_PTR, next_bb)
1935 /* Check for more than one predecessor. */
1936 if (!single_pred_p (bb))
1939 FOR_BB_INSNS (bb, insn)
1940 if (DEBUG_INSN_P (insn))
1942 else if (NONJUMP_INSN_P (insn))
1946 if (GET_CODE (PATTERN (insn)) != SET)
1949 dest = SET_DEST (PATTERN (insn));
1950 if (REG_P (dest) || CC0_P (dest))
1955 else if (JUMP_P (insn))
1957 if ((any_condjump_p (insn) || computed_jump_p (insn))
1958 && onlyjump_p (insn))
1959 changed |= bypass_block (bb, setcc, insn);
1962 else if (INSN_P (insn))
1967 /* If we bypassed any register setting insns, we inserted a
1968 copy on the redirected edge. These need to be committed. */
1970 commit_edge_insertions ();
1975 /* Return true if the graph is too expensive to optimize. PASS is the
1976 optimization about to be performed. */
1979 is_too_expensive (const char *pass)
1981 /* Trying to perform global optimizations on flow graphs which have
1982 a high connectivity will take a long time and is unlikely to be
1983 particularly useful.
1985 In normal circumstances a cfg should have about twice as many
1986 edges as blocks. But we do not want to punish small functions
1987 which have a couple switch statements. Rather than simply
1988 threshold the number of blocks, uses something with a more
1989 graceful degradation. */
1990 if (n_edges > 20000 + n_basic_blocks * 4)
1992 warning (OPT_Wdisabled_optimization,
1993 "%s: %d basic blocks and %d edges/basic block",
1994 pass, n_basic_blocks, n_edges / n_basic_blocks);
1999 /* If allocating memory for the cprop bitmap would take up too much
2000 storage it's better just to disable the optimization. */
2002 * SBITMAP_SET_SIZE (max_reg_num ())
2003 * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
2005 warning (OPT_Wdisabled_optimization,
2006 "%s: %d basic blocks and %d registers",
2007 pass, n_basic_blocks, max_reg_num ());
2016 /* Main function for the CPROP pass. */
2019 one_cprop_pass (void)
2023 /* Return if there's nothing to do, or it is too expensive. */
2024 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
2025 || is_too_expensive (_ ("const/copy propagation disabled")))
2028 global_const_prop_count = local_const_prop_count = 0;
2029 global_copy_prop_count = local_copy_prop_count = 0;
2032 gcc_obstack_init (&gcse_obstack);
2035 /* Do a local const/copy propagation pass first. The global pass
2036 only handles global opportunities.
2037 If the local pass changes something, remove any unreachable blocks
2038 because the CPROP global dataflow analysis may get into infinite
2039 loops for CFGs with unreachable blocks.
2041 FIXME: This local pass should not be necessary after CSE (but for
2042 some reason it still is). It is also (proven) not necessary
2043 to run the local pass right after FWPWOP.
2045 FIXME: The global analysis would not get into infinite loops if it
2046 would use the DF solver (via df_simple_dataflow) instead of
2047 the solver implemented in this file. */
2048 if (local_cprop_pass ())
2050 delete_unreachable_blocks ();
2054 /* Determine implicit sets. */
2055 implicit_sets = XCNEWVEC (rtx, last_basic_block);
2056 find_implicit_sets ();
2058 alloc_hash_table (&set_hash_table);
2059 compute_hash_table (&set_hash_table);
2061 /* Free implicit_sets before peak usage. */
2062 free (implicit_sets);
2063 implicit_sets = NULL;
2066 dump_hash_table (dump_file, "SET", &set_hash_table);
2067 if (set_hash_table.n_elems > 0)
2072 alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
2073 compute_cprop_data ();
2075 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
2077 /* Reset tables used to keep track of what's still valid [since
2078 the start of the block]. */
2079 reset_opr_set_tables ();
2081 FOR_BB_INSNS (bb, insn)
2084 changed |= cprop_insn (insn);
2086 /* Keep track of everything modified by this insn. */
2087 /* ??? Need to be careful w.r.t. mods done to INSN.
2088 Don't call mark_oprs_set if we turned the
2089 insn into a NOTE. */
2090 if (! NOTE_P (insn))
2091 mark_oprs_set (insn);
2095 changed |= bypass_conditional_jumps ();
2099 free_hash_table (&set_hash_table);
2101 obstack_free (&gcse_obstack, NULL);
2105 fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
2106 current_function_name (), n_basic_blocks, bytes_used);
2107 fprintf (dump_file, "%d local const props, %d local copy props, ",
2108 local_const_prop_count, local_copy_prop_count);
2109 fprintf (dump_file, "%d global const props, %d global copy props\n\n",
2110 global_const_prop_count, global_copy_prop_count);
2117 /* All the passes implemented in this file. Each pass has its
2118 own gate and execute function, and at the end of the file a
2119 pass definition for passes.c.
2121 We do not construct an accurate cfg in functions which call
2122 setjmp, so none of these passes runs if the function calls
2124 FIXME: Should just handle setjmp via REG_SETJMP notes. */
2127 gate_rtl_cprop (void)
2129 return optimize > 0 && flag_gcse
2130 && !cfun->calls_setjmp
2135 execute_rtl_cprop (void)
2138 delete_unreachable_blocks ();
2139 df_set_flags (DF_LR_RUN_DCE);
2141 changed = one_cprop_pass ();
2142 flag_rerun_cse_after_global_opts |= changed;
2148 struct rtl_opt_pass pass_rtl_cprop =
2153 gate_rtl_cprop, /* gate */
2154 execute_rtl_cprop, /* execute */
2157 0, /* static_pass_number */
2158 TV_CPROP, /* tv_id */
2159 PROP_cfglayout, /* properties_required */
2160 0, /* properties_provided */
2161 0, /* properties_destroyed */
2162 0, /* todo_flags_start */
2163 TODO_df_finish | TODO_verify_rtl_sharing |
2165 TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */