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 or end of the basic block while traversing that 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 /* Return nonzero if register X is unchanged from INSN to the end
187 of INSN's basic block. */
190 reg_available_p (const_rtx x
, const_rtx insn ATTRIBUTE_UNUSED
)
192 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
195 /* Hash a set of register REGNO.
197 Sets are hashed on the register that is set. This simplifies the PRE copy
200 ??? May need to make things more elaborate. Later, as necessary. */
203 hash_set (int regno
, int hash_table_size
)
208 return hash
% hash_table_size
;
211 /* Return nonzero if exp1 is equivalent to exp2. */
214 expr_equiv_p (const_rtx x
, const_rtx y
)
216 return exp_equiv_p (x
, y
, 0, true);
219 /* Insert pattern X in INSN in the hash table.
220 X is a SET of a reg to either another reg or a constant.
221 If it is already present, record it as the last occurrence in INSN's
225 insert_set_in_table (rtx x
, rtx insn
, struct hash_table_d
*table
)
229 struct expr
*cur_expr
, *last_expr
= NULL
;
230 struct occr
*cur_occr
;
232 gcc_assert (GET_CODE (x
) == SET
&& REG_P (SET_DEST (x
)));
234 hash
= hash_set (REGNO (SET_DEST (x
)), table
->size
);
236 cur_expr
= table
->table
[hash
];
239 while (cur_expr
&& 0 == (found
= expr_equiv_p (cur_expr
->expr
, x
)))
241 /* If the expression isn't found, save a pointer to the end of
243 last_expr
= cur_expr
;
244 cur_expr
= cur_expr
->next_same_hash
;
249 cur_expr
= GOBNEW (struct expr
);
250 bytes_used
+= sizeof (struct expr
);
251 if (table
->table
[hash
] == NULL
)
252 /* This is the first pattern that hashed to this index. */
253 table
->table
[hash
] = cur_expr
;
255 /* Add EXPR to end of this hash chain. */
256 last_expr
->next_same_hash
= cur_expr
;
258 /* Set the fields of the expr element.
259 We must copy X because it can be modified when copy propagation is
260 performed on its operands. */
261 cur_expr
->expr
= copy_rtx (x
);
262 cur_expr
->bitmap_index
= table
->n_elems
++;
263 cur_expr
->next_same_hash
= NULL
;
264 cur_expr
->avail_occr
= NULL
;
267 /* Now record the occurrence. */
268 cur_occr
= cur_expr
->avail_occr
;
271 && BLOCK_FOR_INSN (cur_occr
->insn
) == BLOCK_FOR_INSN (insn
))
273 /* Found another instance of the expression in the same basic block.
274 Prefer this occurrence to the currently recorded one. We want
275 the last one in the block and the block is scanned from start
277 cur_occr
->insn
= insn
;
281 /* First occurrence of this expression in this basic block. */
282 cur_occr
= GOBNEW (struct occr
);
283 bytes_used
+= sizeof (struct occr
);
284 cur_occr
->insn
= insn
;
285 cur_occr
->next
= cur_expr
->avail_occr
;
286 cur_expr
->avail_occr
= cur_occr
;
290 /* Determine whether the rtx X should be treated as a constant for CPROP.
291 Since X might be inserted more than once we have to take care that it
295 gcse_constant_p (const_rtx x
)
297 return CONSTANT_P (x
) && (GET_CODE (x
) != CONST
|| shared_const_p (x
));
300 /* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or
304 hash_scan_set (rtx pat
, rtx insn
, struct hash_table_d
*table
)
306 rtx src
= SET_SRC (pat
);
307 rtx dest
= SET_DEST (pat
);
310 && ! HARD_REGISTER_P (dest
)
311 && reg_available_p (dest
, insn
)
312 && can_copy_p (GET_MODE (dest
)))
314 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
316 This allows us to do a single CPROP pass and still eliminate
317 redundant constants, addresses or other expressions that are
318 constructed with multiple instructions.
320 However, keep the original SRC if INSN is a simple reg-reg move. In
321 In this case, there will almost always be a REG_EQUAL note on the
322 insn that sets SRC. By recording the REG_EQUAL value here as SRC
323 for INSN, we miss copy propagation opportunities.
325 Note that this does not impede profitable constant propagations. We
326 "look through" reg-reg sets in lookup_avail_set. */
327 rtx note
= find_reg_equal_equiv_note (insn
);
329 && REG_NOTE_KIND (note
) == REG_EQUAL
331 && gcse_constant_p (XEXP (note
, 0)))
332 src
= XEXP (note
, 0), pat
= gen_rtx_SET (VOIDmode
, dest
, src
);
334 /* Record sets for constant/copy propagation. */
337 && ! HARD_REGISTER_P (src
)
338 && reg_available_p (src
, insn
))
339 || gcse_constant_p (src
))
340 insert_set_in_table (pat
, insn
, table
);
344 /* Process INSN and add hash table entries as appropriate.
346 Only available expressions that set a single pseudo-reg are recorded.
348 Single sets in a PARALLEL could be handled, but it's an extra complication
349 that isn't dealt with right now. The trick is handling the CLOBBERs that
350 are also in the PARALLEL. Later.
352 If SET_P is nonzero, this is for the assignment hash table,
353 otherwise it is for the expression hash table. */
356 hash_scan_insn (rtx insn
, struct hash_table_d
*table
)
358 rtx pat
= PATTERN (insn
);
361 /* Pick out the sets of INSN and for other forms of instructions record
362 what's been modified. */
364 if (GET_CODE (pat
) == SET
)
365 hash_scan_set (pat
, insn
, table
);
366 else if (GET_CODE (pat
) == PARALLEL
)
367 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
369 rtx x
= XVECEXP (pat
, 0, i
);
371 if (GET_CODE (x
) == SET
)
372 hash_scan_set (x
, insn
, table
);
377 dump_hash_table (FILE *file
, const char *name
, struct hash_table_d
*table
)
380 /* Flattened out table, so it's printed in proper order. */
381 struct expr
**flat_table
;
382 unsigned int *hash_val
;
385 flat_table
= XCNEWVEC (struct expr
*, table
->n_elems
);
386 hash_val
= XNEWVEC (unsigned int, table
->n_elems
);
388 for (i
= 0; i
< (int) table
->size
; i
++)
389 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
391 flat_table
[expr
->bitmap_index
] = expr
;
392 hash_val
[expr
->bitmap_index
] = i
;
395 fprintf (file
, "%s hash table (%d buckets, %d entries)\n",
396 name
, table
->size
, table
->n_elems
);
398 for (i
= 0; i
< (int) table
->n_elems
; i
++)
399 if (flat_table
[i
] != 0)
401 expr
= flat_table
[i
];
402 fprintf (file
, "Index %d (hash value %d)\n ",
403 expr
->bitmap_index
, hash_val
[i
]);
404 print_rtl (file
, expr
->expr
);
405 fprintf (file
, "\n");
408 fprintf (file
, "\n");
414 /* Record as unavailable all registers that are DEF operands of INSN. */
416 make_set_regs_unavailable (rtx insn
)
418 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
421 for (def_rec
= DF_INSN_INFO_DEFS (insn_info
); *def_rec
; def_rec
++)
422 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (*def_rec
));
425 /* Top level function to create an assignments hash table.
427 Assignment entries are placed in the hash table if
428 - they are of the form (set (pseudo-reg) src),
429 - src is something we want to perform const/copy propagation on,
430 - none of the operands or target are subsequently modified in the block
432 Currently src must be a pseudo-reg or a const_int.
434 TABLE is the table computed. */
437 compute_hash_table_work (struct hash_table_d
*table
)
445 /* Reset tables used to keep track of what's not yet invalid [since
446 the end of the block]. */
447 CLEAR_REG_SET (reg_set_bitmap
);
449 /* Go over all insns from the last to the first. This is convenient
450 for tracking available registers, i.e. not set between INSN and
451 the end of the basic block BB. */
452 FOR_BB_INSNS_REVERSE (bb
, insn
)
454 /* Only real insns are interesting. */
455 if (!NONDEBUG_INSN_P (insn
))
458 /* Record interesting sets from INSN in the hash table. */
459 hash_scan_insn (insn
, table
);
461 /* Any registers set in INSN will make SETs above it not AVAIL. */
462 make_set_regs_unavailable (insn
);
465 /* Insert implicit sets in the hash table, pretending they appear as
466 insns at the head of the basic block. */
467 if (implicit_sets
[bb
->index
] != NULL_RTX
)
468 hash_scan_set (implicit_sets
[bb
->index
], BB_HEAD (bb
), table
);
472 /* Allocate space for the set/expr hash TABLE.
473 It is used to determine the number of buckets to use. */
476 alloc_hash_table (struct hash_table_d
*table
)
480 n
= get_max_insn_count ();
483 if (table
->size
< 11)
486 /* Attempt to maintain efficient use of hash table.
487 Making it an odd number is simplest for now.
488 ??? Later take some measurements. */
490 n
= table
->size
* sizeof (struct expr
*);
491 table
->table
= GNEWVAR (struct expr
*, n
);
494 /* Free things allocated by alloc_hash_table. */
497 free_hash_table (struct hash_table_d
*table
)
502 /* Compute the hash TABLE for doing copy/const propagation or
503 expression hash table. */
506 compute_hash_table (struct hash_table_d
*table
)
508 /* Initialize count of number of entries in hash table. */
510 memset (table
->table
, 0, table
->size
* sizeof (struct expr
*));
512 compute_hash_table_work (table
);
515 /* Expression tracking support. */
517 /* Lookup REGNO in the set TABLE. The result is a pointer to the
518 table entry, or NULL if not found. */
521 lookup_set (unsigned int regno
, struct hash_table_d
*table
)
523 unsigned int hash
= hash_set (regno
, table
->size
);
526 expr
= table
->table
[hash
];
528 while (expr
&& REGNO (SET_DEST (expr
->expr
)) != regno
)
529 expr
= expr
->next_same_hash
;
534 /* Return the next entry for REGNO in list EXPR. */
537 next_set (unsigned int regno
, struct expr
*expr
)
540 expr
= expr
->next_same_hash
;
541 while (expr
&& REGNO (SET_DEST (expr
->expr
)) != regno
);
546 /* Reset tables used to keep track of what's still available [since the
547 start of the block]. */
550 reset_opr_set_tables (void)
552 /* Maintain a bitmap of which regs have been set since beginning of
554 CLEAR_REG_SET (reg_set_bitmap
);
557 /* Return nonzero if the operands of X are not set before INSN in
558 INSN's basic block. */
561 oprs_not_set_p (const_rtx x
, const_rtx insn
)
587 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
593 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
597 /* If we are about to do the last recursive call
598 needed at this level, change it into iteration.
599 This function is called enough to be worth it. */
601 return oprs_not_set_p (XEXP (x
, i
), insn
);
603 if (! oprs_not_set_p (XEXP (x
, i
), insn
))
606 else if (fmt
[i
] == 'E')
607 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
608 if (! oprs_not_set_p (XVECEXP (x
, i
, j
), insn
))
615 /* Mark things set by a SET. */
618 mark_set (rtx pat
, rtx insn ATTRIBUTE_UNUSED
)
620 rtx dest
= SET_DEST (pat
);
622 while (GET_CODE (dest
) == SUBREG
623 || GET_CODE (dest
) == ZERO_EXTRACT
624 || GET_CODE (dest
) == STRICT_LOW_PART
)
625 dest
= XEXP (dest
, 0);
628 SET_REGNO_REG_SET (reg_set_bitmap
, REGNO (dest
));
631 /* Record things set by a CLOBBER. */
634 mark_clobber (rtx pat
, rtx insn ATTRIBUTE_UNUSED
)
636 rtx clob
= XEXP (pat
, 0);
638 while (GET_CODE (clob
) == SUBREG
|| GET_CODE (clob
) == STRICT_LOW_PART
)
639 clob
= XEXP (clob
, 0);
642 SET_REGNO_REG_SET (reg_set_bitmap
, REGNO (clob
));
645 /* Record things set by INSN.
646 This data is used by oprs_not_set_p. */
649 mark_oprs_set (rtx insn
)
651 rtx pat
= PATTERN (insn
);
654 if (GET_CODE (pat
) == SET
)
655 mark_set (pat
, insn
);
656 else if (GET_CODE (pat
) == PARALLEL
)
657 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
659 rtx x
= XVECEXP (pat
, 0, i
);
661 if (GET_CODE (x
) == SET
)
663 else if (GET_CODE (x
) == CLOBBER
)
664 mark_clobber (x
, insn
);
667 else if (GET_CODE (pat
) == CLOBBER
)
668 mark_clobber (pat
, insn
);
672 /* Compute copy/constant propagation working variables. */
674 /* Local properties of assignments. */
675 static sbitmap
*cprop_pavloc
;
676 static sbitmap
*cprop_absaltered
;
678 /* Global properties of assignments (computed from the local properties). */
679 static sbitmap
*cprop_avin
;
680 static sbitmap
*cprop_avout
;
682 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
683 basic blocks. N_SETS is the number of sets. */
686 alloc_cprop_mem (int n_blocks
, int n_sets
)
688 cprop_pavloc
= sbitmap_vector_alloc (n_blocks
, n_sets
);
689 cprop_absaltered
= sbitmap_vector_alloc (n_blocks
, n_sets
);
691 cprop_avin
= sbitmap_vector_alloc (n_blocks
, n_sets
);
692 cprop_avout
= sbitmap_vector_alloc (n_blocks
, n_sets
);
695 /* Free vars used by copy/const propagation. */
698 free_cprop_mem (void)
700 sbitmap_vector_free (cprop_pavloc
);
701 sbitmap_vector_free (cprop_absaltered
);
702 sbitmap_vector_free (cprop_avin
);
703 sbitmap_vector_free (cprop_avout
);
706 /* For each block, compute whether X is transparent. X is either an
707 expression or an assignment [though we don't care which, for this context
708 an assignment is treated as an expression]. For each block where an
709 element of X is modified, set the INDX bit in BMAP. */
712 compute_transp (const_rtx x
, int indx
, sbitmap
*bmap
)
718 /* repeat is used to turn tail-recursion into iteration since GCC
719 can't do it when there's no return value. */
731 for (def
= DF_REG_DEF_CHAIN (REGNO (x
));
733 def
= DF_REF_NEXT_REG (def
))
734 SET_BIT (bmap
[DF_REF_BB (def
)->index
], indx
);
755 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
759 /* If we are about to do the last recursive call
760 needed at this level, change it into iteration.
761 This function is called enough to be worth it. */
768 compute_transp (XEXP (x
, i
), indx
, bmap
);
770 else if (fmt
[i
] == 'E')
771 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
772 compute_transp (XVECEXP (x
, i
, j
), indx
, bmap
);
776 /* Compute the local properties of each recorded expression.
778 Local properties are those that are defined by the block, irrespective of
781 An expression is transparent in a block if its operands are not modified
784 An expression is computed (locally available) in a block if it is computed
785 at least once and expression would contain the same value if the
786 computation was moved to the end of the block.
788 TRANSP and COMP are destination sbitmaps for recording local properties.
789 If NULL, then it is not necessary to compute or record that particular
792 TRANSP is computed as ~TRANSP, since this is really cprop's ABSALTERED. */
795 compute_local_properties (sbitmap
*transp
, sbitmap
*comp
,
796 struct hash_table_d
*table
)
800 /* Initialize any bitmaps that were passed in. */
803 sbitmap_vector_zero (transp
, last_basic_block
);
807 sbitmap_vector_zero (comp
, last_basic_block
);
809 for (i
= 0; i
< table
->size
; i
++)
813 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
815 int indx
= expr
->bitmap_index
;
818 /* The expression is transparent in this block if it is not killed.
819 We start by assuming all are transparent [none are killed], and
820 then reset the bits for those that are. */
822 compute_transp (expr
->expr
, indx
, transp
);
824 /* The occurrences recorded in avail_occr are exactly those that
825 we want to set to nonzero in COMP. */
827 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
829 SET_BIT (comp
[BLOCK_FOR_INSN (occr
->insn
)->index
], indx
);
835 /* Hash table support. */
837 /* Top level routine to do the dataflow analysis needed by copy/const
841 compute_cprop_data (void)
843 compute_local_properties (cprop_absaltered
, cprop_pavloc
, &set_hash_table
);
844 compute_available (cprop_pavloc
, cprop_absaltered
,
845 cprop_avout
, cprop_avin
);
848 /* Copy/constant propagation. */
850 /* Maximum number of register uses in an insn that we handle. */
853 /* Table of uses found in an insn.
854 Allocated statically to avoid alloc/free complexity and overhead. */
855 static struct reg_use reg_use_table
[MAX_USES
];
857 /* Index into `reg_use_table' while building it. */
858 static int reg_use_count
;
860 /* Set up a list of register numbers used in INSN. The found uses are stored
861 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
862 and contains the number of uses in the table upon exit.
864 ??? If a register appears multiple times we will record it multiple times.
865 This doesn't hurt anything but it will slow things down. */
868 find_used_regs (rtx
*xptr
, void *data ATTRIBUTE_UNUSED
)
875 /* repeat is used to turn tail-recursion into iteration since GCC
876 can't do it when there's no return value. */
884 if (reg_use_count
== MAX_USES
)
887 reg_use_table
[reg_use_count
].reg_rtx
= x
;
891 /* Recursively scan the operands of this expression. */
893 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
897 /* If we are about to do the last recursive call
898 needed at this level, change it into iteration.
899 This function is called enough to be worth it. */
906 find_used_regs (&XEXP (x
, i
), data
);
908 else if (fmt
[i
] == 'E')
909 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
910 find_used_regs (&XVECEXP (x
, i
, j
), data
);
914 /* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO.
915 Returns nonzero is successful. */
918 try_replace_reg (rtx from
, rtx to
, rtx insn
)
920 rtx note
= find_reg_equal_equiv_note (insn
);
923 rtx set
= single_set (insn
);
925 /* Usually we substitute easy stuff, so we won't copy everything.
926 We however need to take care to not duplicate non-trivial CONST
930 validate_replace_src_group (from
, to
, insn
);
931 if (num_changes_pending () && apply_change_group ())
934 /* Try to simplify SET_SRC if we have substituted a constant. */
935 if (success
&& set
&& CONSTANT_P (to
))
937 src
= simplify_rtx (SET_SRC (set
));
940 validate_change (insn
, &SET_SRC (set
), src
, 0);
943 /* If there is already a REG_EQUAL note, update the expression in it
944 with our replacement. */
945 if (note
!= 0 && REG_NOTE_KIND (note
) == REG_EQUAL
)
946 set_unique_reg_note (insn
, REG_EQUAL
,
947 simplify_replace_rtx (XEXP (note
, 0), from
, to
));
948 if (!success
&& set
&& reg_mentioned_p (from
, SET_SRC (set
)))
950 /* If above failed and this is a single set, try to simplify the source of
951 the set given our substitution. We could perhaps try this for multiple
952 SETs, but it probably won't buy us anything. */
953 src
= simplify_replace_rtx (SET_SRC (set
), from
, to
);
955 if (!rtx_equal_p (src
, SET_SRC (set
))
956 && validate_change (insn
, &SET_SRC (set
), src
, 0))
959 /* If we've failed perform the replacement, have a single SET to
960 a REG destination and don't yet have a note, add a REG_EQUAL note
961 to not lose information. */
962 if (!success
&& note
== 0 && set
!= 0 && REG_P (SET_DEST (set
)))
963 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
966 /* REG_EQUAL may get simplified into register.
967 We don't allow that. Remove that note. This code ought
968 not to happen, because previous code ought to synthesize
969 reg-reg move, but be on the safe side. */
970 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
&& REG_P (XEXP (note
, 0)))
971 remove_note (insn
, note
);
976 /* Find a set of REGNOs that are available on entry to INSN's block. Returns
977 NULL no such set is found. */
980 find_avail_set (int regno
, rtx insn
)
982 /* SET1 contains the last set found that can be returned to the caller for
983 use in a substitution. */
984 struct expr
*set1
= 0;
986 /* Loops are not possible here. To get a loop we would need two sets
987 available at the start of the block containing INSN. i.e. we would
988 need two sets like this available at the start of the block:
990 (set (reg X) (reg Y))
991 (set (reg Y) (reg X))
993 This can not happen since the set of (reg Y) would have killed the
994 set of (reg X) making it unavailable at the start of this block. */
998 struct expr
*set
= lookup_set (regno
, &set_hash_table
);
1000 /* Find a set that is available at the start of the block
1001 which contains INSN. */
1004 if (TEST_BIT (cprop_avin
[BLOCK_FOR_INSN (insn
)->index
],
1007 set
= next_set (regno
, set
);
1010 /* If no available set was found we've reached the end of the
1011 (possibly empty) copy chain. */
1015 gcc_assert (GET_CODE (set
->expr
) == SET
);
1017 src
= SET_SRC (set
->expr
);
1019 /* We know the set is available.
1020 Now check that SRC is locally anticipatable (i.e. none of the
1021 source operands have changed since the start of the block).
1023 If the source operand changed, we may still use it for the next
1024 iteration of this loop, but we may not use it for substitutions. */
1026 if (gcse_constant_p (src
) || oprs_not_set_p (src
, insn
))
1029 /* If the source of the set is anything except a register, then
1030 we have reached the end of the copy chain. */
1034 /* Follow the copy chain, i.e. start another iteration of the loop
1035 and see if we have an available copy into SRC. */
1036 regno
= REGNO (src
);
1039 /* SET1 holds the last set that was available and anticipatable at
1044 /* Subroutine of cprop_insn that tries to propagate constants into
1045 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
1046 it is the instruction that immediately precedes JUMP, and must be a
1047 single SET of a register. FROM is what we will try to replace,
1048 SRC is the constant we will try to substitute for it. Returns nonzero
1049 if a change was made. */
1052 cprop_jump (basic_block bb
, rtx setcc
, rtx jump
, rtx from
, rtx src
)
1054 rtx new_rtx
, set_src
, note_src
;
1055 rtx set
= pc_set (jump
);
1056 rtx note
= find_reg_equal_equiv_note (jump
);
1060 note_src
= XEXP (note
, 0);
1061 if (GET_CODE (note_src
) == EXPR_LIST
)
1062 note_src
= NULL_RTX
;
1064 else note_src
= NULL_RTX
;
1066 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
1067 set_src
= note_src
? note_src
: SET_SRC (set
);
1069 /* First substitute the SETCC condition into the JUMP instruction,
1070 then substitute that given values into this expanded JUMP. */
1071 if (setcc
!= NULL_RTX
1072 && !modified_between_p (from
, setcc
, jump
)
1073 && !modified_between_p (src
, setcc
, jump
))
1076 rtx setcc_set
= single_set (setcc
);
1077 rtx setcc_note
= find_reg_equal_equiv_note (setcc
);
1078 setcc_src
= (setcc_note
&& GET_CODE (XEXP (setcc_note
, 0)) != EXPR_LIST
)
1079 ? XEXP (setcc_note
, 0) : SET_SRC (setcc_set
);
1080 set_src
= simplify_replace_rtx (set_src
, SET_DEST (setcc_set
),
1086 new_rtx
= simplify_replace_rtx (set_src
, from
, src
);
1088 /* If no simplification can be made, then try the next register. */
1089 if (rtx_equal_p (new_rtx
, SET_SRC (set
)))
1092 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
1093 if (new_rtx
== pc_rtx
)
1097 /* Ensure the value computed inside the jump insn to be equivalent
1098 to one computed by setcc. */
1099 if (setcc
&& modified_in_p (new_rtx
, setcc
))
1101 if (! validate_unshare_change (jump
, &SET_SRC (set
), new_rtx
, 0))
1103 /* When (some) constants are not valid in a comparison, and there
1104 are two registers to be replaced by constants before the entire
1105 comparison can be folded into a constant, we need to keep
1106 intermediate information in REG_EQUAL notes. For targets with
1107 separate compare insns, such notes are added by try_replace_reg.
1108 When we have a combined compare-and-branch instruction, however,
1109 we need to attach a note to the branch itself to make this
1110 optimization work. */
1112 if (!rtx_equal_p (new_rtx
, note_src
))
1113 set_unique_reg_note (jump
, REG_EQUAL
, copy_rtx (new_rtx
));
1117 /* Remove REG_EQUAL note after simplification. */
1119 remove_note (jump
, note
);
1123 /* Delete the cc0 setter. */
1124 if (setcc
!= NULL
&& CC0_P (SET_DEST (single_set (setcc
))))
1125 delete_insn (setcc
);
1128 global_const_prop_count
++;
1129 if (dump_file
!= NULL
)
1132 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with constant ",
1133 REGNO (from
), INSN_UID (jump
));
1134 print_rtl (dump_file
, src
);
1135 fprintf (dump_file
, "\n");
1137 purge_dead_edges (bb
);
1139 /* If a conditional jump has been changed into unconditional jump, remove
1140 the jump and make the edge fallthru - this is always called in
1142 if (new_rtx
!= pc_rtx
&& simplejump_p (jump
))
1147 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); ei_next (&ei
))
1148 if (e
->dest
!= EXIT_BLOCK_PTR
1149 && BB_HEAD (e
->dest
) == JUMP_LABEL (jump
))
1151 e
->flags
|= EDGE_FALLTHRU
;
1161 constprop_register (rtx insn
, rtx from
, rtx to
)
1165 /* Check for reg or cc0 setting instructions followed by
1166 conditional branch instructions first. */
1167 if ((sset
= single_set (insn
)) != NULL
1169 && any_condjump_p (NEXT_INSN (insn
)) && onlyjump_p (NEXT_INSN (insn
)))
1171 rtx dest
= SET_DEST (sset
);
1172 if ((REG_P (dest
) || CC0_P (dest
))
1173 && cprop_jump (BLOCK_FOR_INSN (insn
), insn
, NEXT_INSN (insn
), from
, to
))
1177 /* Handle normal insns next. */
1178 if (NONJUMP_INSN_P (insn
)
1179 && try_replace_reg (from
, to
, insn
))
1182 /* Try to propagate a CONST_INT into a conditional jump.
1183 We're pretty specific about what we will handle in this
1184 code, we can extend this as necessary over time.
1186 Right now the insn in question must look like
1187 (set (pc) (if_then_else ...)) */
1188 else if (any_condjump_p (insn
) && onlyjump_p (insn
))
1189 return cprop_jump (BLOCK_FOR_INSN (insn
), NULL
, insn
, from
, to
);
1193 /* Perform constant and copy propagation on INSN.
1194 The result is nonzero if a change was made. */
1197 cprop_insn (rtx insn
)
1199 struct reg_use
*reg_used
;
1207 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1209 note
= find_reg_equal_equiv_note (insn
);
1211 /* We may win even when propagating constants into notes. */
1213 find_used_regs (&XEXP (note
, 0), NULL
);
1215 for (reg_used
= ®_use_table
[0]; reg_use_count
> 0;
1216 reg_used
++, reg_use_count
--)
1218 unsigned int regno
= REGNO (reg_used
->reg_rtx
);
1222 /* If the register has already been set in this block, there's
1223 nothing we can do. */
1224 if (! oprs_not_set_p (reg_used
->reg_rtx
, insn
))
1227 /* Find an assignment that sets reg_used and is available
1228 at the start of the block. */
1229 set
= find_avail_set (regno
, insn
);
1234 /* ??? We might be able to handle PARALLELs. Later. */
1235 gcc_assert (GET_CODE (pat
) == SET
);
1237 src
= SET_SRC (pat
);
1239 /* Constant propagation. */
1240 if (gcse_constant_p (src
))
1242 if (constprop_register (insn
, reg_used
->reg_rtx
, src
))
1245 global_const_prop_count
++;
1246 if (dump_file
!= NULL
)
1248 fprintf (dump_file
, "GLOBAL CONST-PROP: Replacing reg %d in ", regno
);
1249 fprintf (dump_file
, "insn %d with constant ", INSN_UID (insn
));
1250 print_rtl (dump_file
, src
);
1251 fprintf (dump_file
, "\n");
1253 if (INSN_DELETED_P (insn
))
1257 else if (REG_P (src
)
1258 && REGNO (src
) >= FIRST_PSEUDO_REGISTER
1259 && REGNO (src
) != regno
)
1261 if (try_replace_reg (reg_used
->reg_rtx
, src
, insn
))
1264 global_copy_prop_count
++;
1265 if (dump_file
!= NULL
)
1267 fprintf (dump_file
, "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1268 regno
, INSN_UID (insn
));
1269 fprintf (dump_file
, " with reg %d\n", REGNO (src
));
1272 /* The original insn setting reg_used may or may not now be
1273 deletable. We leave the deletion to flow. */
1274 /* FIXME: If it turns out that the insn isn't deletable,
1275 then we may have unnecessarily extended register lifetimes
1276 and made things worse. */
1281 if (changed
&& DEBUG_INSN_P (insn
))
1287 /* Like find_used_regs, but avoid recording uses that appear in
1288 input-output contexts such as zero_extract or pre_dec. This
1289 restricts the cases we consider to those for which local cprop
1290 can legitimately make replacements. */
1293 local_cprop_find_used_regs (rtx
*xptr
, void *data
)
1300 switch (GET_CODE (x
))
1304 case STRICT_LOW_PART
:
1313 /* Can only legitimately appear this early in the context of
1314 stack pushes for function arguments, but handle all of the
1315 codes nonetheless. */
1319 /* Setting a subreg of a register larger than word_mode leaves
1320 the non-written words unchanged. */
1321 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x
))) > BITS_PER_WORD
)
1329 find_used_regs (xptr
, data
);
1332 /* Try to perform local const/copy propagation on X in INSN. */
1335 do_local_cprop (rtx x
, rtx insn
)
1337 rtx newreg
= NULL
, newcnst
= NULL
;
1339 /* Rule out USE instructions and ASM statements as we don't want to
1340 change the hard registers mentioned. */
1342 && (REGNO (x
) >= FIRST_PSEUDO_REGISTER
1343 || (GET_CODE (PATTERN (insn
)) != USE
1344 && asm_noperands (PATTERN (insn
)) < 0)))
1346 cselib_val
*val
= cselib_lookup (x
, GET_MODE (x
), 0, VOIDmode
);
1347 struct elt_loc_list
*l
;
1351 for (l
= val
->locs
; l
; l
= l
->next
)
1353 rtx this_rtx
= l
->loc
;
1356 if (gcse_constant_p (this_rtx
))
1358 if (REG_P (this_rtx
) && REGNO (this_rtx
) >= FIRST_PSEUDO_REGISTER
1359 /* Don't copy propagate if it has attached REG_EQUIV note.
1360 At this point this only function parameters should have
1361 REG_EQUIV notes and if the argument slot is used somewhere
1362 explicitly, it means address of parameter has been taken,
1363 so we should not extend the lifetime of the pseudo. */
1364 && (!(note
= find_reg_note (l
->setting_insn
, REG_EQUIV
, NULL_RTX
))
1365 || ! MEM_P (XEXP (note
, 0))))
1368 if (newcnst
&& constprop_register (insn
, x
, newcnst
))
1370 if (dump_file
!= NULL
)
1372 fprintf (dump_file
, "LOCAL CONST-PROP: Replacing reg %d in ",
1374 fprintf (dump_file
, "insn %d with constant ",
1376 print_rtl (dump_file
, newcnst
);
1377 fprintf (dump_file
, "\n");
1379 local_const_prop_count
++;
1382 else if (newreg
&& newreg
!= x
&& try_replace_reg (x
, newreg
, insn
))
1384 if (dump_file
!= NULL
)
1387 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1388 REGNO (x
), INSN_UID (insn
));
1389 fprintf (dump_file
, " with reg %d\n", REGNO (newreg
));
1391 local_copy_prop_count
++;
1398 /* Do local const/copy propagation (i.e. within each basic block). */
1401 local_cprop_pass (void)
1405 struct reg_use
*reg_used
;
1406 bool changed
= false;
1411 FOR_BB_INSNS (bb
, insn
)
1415 rtx note
= find_reg_equal_equiv_note (insn
);
1419 note_uses (&PATTERN (insn
), local_cprop_find_used_regs
,
1422 local_cprop_find_used_regs (&XEXP (note
, 0), NULL
);
1424 for (reg_used
= ®_use_table
[0]; reg_use_count
> 0;
1425 reg_used
++, reg_use_count
--)
1427 if (do_local_cprop (reg_used
->reg_rtx
, insn
))
1433 if (INSN_DELETED_P (insn
))
1436 while (reg_use_count
);
1438 cselib_process_insn (insn
);
1441 /* Forget everything at the end of a basic block. */
1442 cselib_clear_table ();
1450 /* Similar to get_condition, only the resulting condition must be
1451 valid at JUMP, instead of at EARLIEST.
1453 This differs from noce_get_condition in ifcvt.c in that we prefer not to
1454 settle for the condition variable in the jump instruction being integral.
1455 We prefer to be able to record the value of a user variable, rather than
1456 the value of a temporary used in a condition. This could be solved by
1457 recording the value of *every* register scanned by canonicalize_condition,
1458 but this would require some code reorganization. */
1461 fis_get_condition (rtx jump
)
1463 return get_condition (jump
, NULL
, false, true);
1466 /* Check the comparison COND to see if we can safely form an implicit set from
1467 it. COND is either an EQ or NE comparison. */
1470 implicit_set_cond_p (const_rtx cond
)
1472 const enum machine_mode mode
= GET_MODE (XEXP (cond
, 0));
1473 const_rtx cst
= XEXP (cond
, 1);
1475 /* We can't perform this optimization if either operand might be or might
1476 contain a signed zero. */
1477 if (HONOR_SIGNED_ZEROS (mode
))
1479 /* It is sufficient to check if CST is or contains a zero. We must
1480 handle float, complex, and vector. If any subpart is a zero, then
1481 the optimization can't be performed. */
1482 /* ??? The complex and vector checks are not implemented yet. We just
1483 always return zero for them. */
1484 if (GET_CODE (cst
) == CONST_DOUBLE
)
1487 REAL_VALUE_FROM_CONST_DOUBLE (d
, cst
);
1488 if (REAL_VALUES_EQUAL (d
, dconst0
))
1495 return gcse_constant_p (cst
);
1498 /* Find the implicit sets of a function. An "implicit set" is a constraint
1499 on the value of a variable, implied by a conditional jump. For example,
1500 following "if (x == 2)", the then branch may be optimized as though the
1501 conditional performed an "explicit set", in this example, "x = 2". This
1502 function records the set patterns that are implicit at the start of each
1505 FIXME: This would be more effective if critical edges are pre-split. As
1506 it is now, we can't record implicit sets for blocks that have
1507 critical successor edges. This results in missed optimizations
1508 and in more (unnecessary) work in cfgcleanup.c:thread_jump(). */
1511 find_implicit_sets (void)
1513 basic_block bb
, dest
;
1519 /* Check for more than one successor. */
1520 if (EDGE_COUNT (bb
->succs
) > 1)
1522 cond
= fis_get_condition (BB_END (bb
));
1525 && (GET_CODE (cond
) == EQ
|| GET_CODE (cond
) == NE
)
1526 && REG_P (XEXP (cond
, 0))
1527 && REGNO (XEXP (cond
, 0)) >= FIRST_PSEUDO_REGISTER
1528 && implicit_set_cond_p (cond
))
1530 dest
= GET_CODE (cond
) == EQ
? BRANCH_EDGE (bb
)->dest
1531 : FALLTHRU_EDGE (bb
)->dest
;
1534 /* Record nothing for a critical edge. */
1535 && single_pred_p (dest
)
1536 && dest
!= EXIT_BLOCK_PTR
)
1538 new_rtx
= gen_rtx_SET (VOIDmode
, XEXP (cond
, 0),
1540 implicit_sets
[dest
->index
] = new_rtx
;
1543 fprintf(dump_file
, "Implicit set of reg %d in ",
1544 REGNO (XEXP (cond
, 0)));
1545 fprintf(dump_file
, "basic block %d\n", dest
->index
);
1553 fprintf (dump_file
, "Found %d implicit sets\n", count
);
1556 /* Bypass conditional jumps. */
1558 /* The value of last_basic_block at the beginning of the jump_bypass
1559 pass. The use of redirect_edge_and_branch_force may introduce new
1560 basic blocks, but the data flow analysis is only valid for basic
1561 block indices less than bypass_last_basic_block. */
1563 static int bypass_last_basic_block
;
1565 /* Find a set of REGNO to a constant that is available at the end of basic
1566 block BB. Returns NULL if no such set is found. Based heavily upon
1569 static struct expr
*
1570 find_bypass_set (int regno
, int bb
)
1572 struct expr
*result
= 0;
1577 struct expr
*set
= lookup_set (regno
, &set_hash_table
);
1581 if (TEST_BIT (cprop_avout
[bb
], set
->bitmap_index
))
1583 set
= next_set (regno
, set
);
1589 gcc_assert (GET_CODE (set
->expr
) == SET
);
1591 src
= SET_SRC (set
->expr
);
1592 if (gcse_constant_p (src
))
1598 regno
= REGNO (src
);
1604 /* Subroutine of bypass_block that checks whether a pseudo is killed by
1605 any of the instructions inserted on an edge. Jump bypassing places
1606 condition code setters on CFG edges using insert_insn_on_edge. This
1607 function is required to check that our data flow analysis is still
1608 valid prior to commit_edge_insertions. */
1611 reg_killed_on_edge (const_rtx reg
, const_edge e
)
1615 for (insn
= e
->insns
.r
; insn
; insn
= NEXT_INSN (insn
))
1616 if (INSN_P (insn
) && reg_set_p (reg
, insn
))
1622 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1623 basic block BB which has more than one predecessor. If not NULL, SETCC
1624 is the first instruction of BB, which is immediately followed by JUMP_INSN
1625 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1626 Returns nonzero if a change was made.
1628 During the jump bypassing pass, we may place copies of SETCC instructions
1629 on CFG edges. The following routine must be careful to pay attention to
1630 these inserted insns when performing its transformations. */
1633 bypass_block (basic_block bb
, rtx setcc
, rtx jump
)
1638 int may_be_loop_header
;
1642 insn
= (setcc
!= NULL
) ? setcc
: jump
;
1644 /* Determine set of register uses in INSN. */
1646 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1647 note
= find_reg_equal_equiv_note (insn
);
1649 find_used_regs (&XEXP (note
, 0), NULL
);
1651 may_be_loop_header
= false;
1652 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1653 if (e
->flags
& EDGE_DFS_BACK
)
1655 may_be_loop_header
= true;
1660 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
1664 if (e
->flags
& EDGE_COMPLEX
)
1670 /* We can't redirect edges from new basic blocks. */
1671 if (e
->src
->index
>= bypass_last_basic_block
)
1677 /* The irreducible loops created by redirecting of edges entering the
1678 loop from outside would decrease effectiveness of some of the following
1679 optimizations, so prevent this. */
1680 if (may_be_loop_header
1681 && !(e
->flags
& EDGE_DFS_BACK
))
1687 for (i
= 0; i
< reg_use_count
; i
++)
1689 struct reg_use
*reg_used
= ®_use_table
[i
];
1690 unsigned int regno
= REGNO (reg_used
->reg_rtx
);
1691 basic_block dest
, old_dest
;
1695 set
= find_bypass_set (regno
, e
->src
->index
);
1700 /* Check the data flow is valid after edge insertions. */
1701 if (e
->insns
.r
&& reg_killed_on_edge (reg_used
->reg_rtx
, e
))
1704 src
= SET_SRC (pc_set (jump
));
1707 src
= simplify_replace_rtx (src
,
1708 SET_DEST (PATTERN (setcc
)),
1709 SET_SRC (PATTERN (setcc
)));
1711 new_rtx
= simplify_replace_rtx (src
, reg_used
->reg_rtx
,
1712 SET_SRC (set
->expr
));
1714 /* Jump bypassing may have already placed instructions on
1715 edges of the CFG. We can't bypass an outgoing edge that
1716 has instructions associated with it, as these insns won't
1717 get executed if the incoming edge is redirected. */
1719 if (new_rtx
== pc_rtx
)
1721 edest
= FALLTHRU_EDGE (bb
);
1722 dest
= edest
->insns
.r
? NULL
: edest
->dest
;
1724 else if (GET_CODE (new_rtx
) == LABEL_REF
)
1726 dest
= BLOCK_FOR_INSN (XEXP (new_rtx
, 0));
1727 /* Don't bypass edges containing instructions. */
1728 edest
= find_edge (bb
, dest
);
1729 if (edest
&& edest
->insns
.r
)
1735 /* Avoid unification of the edge with other edges from original
1736 branch. We would end up emitting the instruction on "both"
1739 if (dest
&& setcc
&& !CC0_P (SET_DEST (PATTERN (setcc
)))
1740 && find_edge (e
->src
, dest
))
1746 && dest
!= EXIT_BLOCK_PTR
)
1748 redirect_edge_and_branch_force (e
, dest
);
1750 /* Copy the register setter to the redirected edge.
1751 Don't copy CC0 setters, as CC0 is dead after jump. */
1754 rtx pat
= PATTERN (setcc
);
1755 if (!CC0_P (SET_DEST (pat
)))
1756 insert_insn_on_edge (copy_insn (pat
), e
);
1759 if (dump_file
!= NULL
)
1761 fprintf (dump_file
, "JUMP-BYPASS: Proved reg %d "
1762 "in jump_insn %d equals constant ",
1763 regno
, INSN_UID (jump
));
1764 print_rtl (dump_file
, SET_SRC (set
->expr
));
1765 fprintf (dump_file
, "\nBypass edge from %d->%d to %d\n",
1766 e
->src
->index
, old_dest
->index
, dest
->index
);
1779 /* Find basic blocks with more than one predecessor that only contain a
1780 single conditional jump. If the result of the comparison is known at
1781 compile-time from any incoming edge, redirect that edge to the
1782 appropriate target. Returns nonzero if a change was made.
1784 This function is now mis-named, because we also handle indirect jumps. */
1787 bypass_conditional_jumps (void)
1795 /* Note we start at block 1. */
1796 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
1799 bypass_last_basic_block
= last_basic_block
;
1800 mark_dfs_back_edges ();
1803 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
->next_bb
,
1804 EXIT_BLOCK_PTR
, next_bb
)
1806 /* Check for more than one predecessor. */
1807 if (!single_pred_p (bb
))
1810 FOR_BB_INSNS (bb
, insn
)
1811 if (DEBUG_INSN_P (insn
))
1813 else if (NONJUMP_INSN_P (insn
))
1817 if (GET_CODE (PATTERN (insn
)) != SET
)
1820 dest
= SET_DEST (PATTERN (insn
));
1821 if (REG_P (dest
) || CC0_P (dest
))
1826 else if (JUMP_P (insn
))
1828 if ((any_condjump_p (insn
) || computed_jump_p (insn
))
1829 && onlyjump_p (insn
))
1830 changed
|= bypass_block (bb
, setcc
, insn
);
1833 else if (INSN_P (insn
))
1838 /* If we bypassed any register setting insns, we inserted a
1839 copy on the redirected edge. These need to be committed. */
1841 commit_edge_insertions ();
1846 /* Return true if the graph is too expensive to optimize. PASS is the
1847 optimization about to be performed. */
1850 is_too_expensive (const char *pass
)
1852 /* Trying to perform global optimizations on flow graphs which have
1853 a high connectivity will take a long time and is unlikely to be
1854 particularly useful.
1856 In normal circumstances a cfg should have about twice as many
1857 edges as blocks. But we do not want to punish small functions
1858 which have a couple switch statements. Rather than simply
1859 threshold the number of blocks, uses something with a more
1860 graceful degradation. */
1861 if (n_edges
> 20000 + n_basic_blocks
* 4)
1863 warning (OPT_Wdisabled_optimization
,
1864 "%s: %d basic blocks and %d edges/basic block",
1865 pass
, n_basic_blocks
, n_edges
/ n_basic_blocks
);
1870 /* If allocating memory for the cprop bitmap would take up too much
1871 storage it's better just to disable the optimization. */
1873 * SBITMAP_SET_SIZE (max_reg_num ())
1874 * sizeof (SBITMAP_ELT_TYPE
)) > MAX_GCSE_MEMORY
)
1876 warning (OPT_Wdisabled_optimization
,
1877 "%s: %d basic blocks and %d registers",
1878 pass
, n_basic_blocks
, max_reg_num ());
1887 /* Main function for the CPROP pass. */
1890 one_cprop_pass (void)
1894 /* Return if there's nothing to do, or it is too expensive. */
1895 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1
1896 || is_too_expensive (_ ("const/copy propagation disabled")))
1899 global_const_prop_count
= local_const_prop_count
= 0;
1900 global_copy_prop_count
= local_copy_prop_count
= 0;
1903 gcc_obstack_init (&gcse_obstack
);
1906 /* Do a local const/copy propagation pass first. The global pass
1907 only handles global opportunities.
1908 If the local pass changes something, remove any unreachable blocks
1909 because the CPROP global dataflow analysis may get into infinite
1910 loops for CFGs with unreachable blocks.
1912 FIXME: This local pass should not be necessary after CSE (but for
1913 some reason it still is). It is also (proven) not necessary
1914 to run the local pass right after FWPWOP.
1916 FIXME: The global analysis would not get into infinite loops if it
1917 would use the DF solver (via df_simple_dataflow) instead of
1918 the solver implemented in this file. */
1919 if (local_cprop_pass ())
1921 delete_unreachable_blocks ();
1925 /* Determine implicit sets. */
1926 implicit_sets
= XCNEWVEC (rtx
, last_basic_block
);
1927 find_implicit_sets ();
1929 alloc_hash_table (&set_hash_table
);
1930 compute_hash_table (&set_hash_table
);
1932 /* Free implicit_sets before peak usage. */
1933 free (implicit_sets
);
1934 implicit_sets
= NULL
;
1937 dump_hash_table (dump_file
, "SET", &set_hash_table
);
1938 if (set_hash_table
.n_elems
> 0)
1943 alloc_cprop_mem (last_basic_block
, set_hash_table
.n_elems
);
1944 compute_cprop_data ();
1946 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
->next_bb
, EXIT_BLOCK_PTR
, next_bb
)
1948 /* Reset tables used to keep track of what's still valid [since
1949 the start of the block]. */
1950 reset_opr_set_tables ();
1952 FOR_BB_INSNS (bb
, insn
)
1955 changed
|= cprop_insn (insn
);
1957 /* Keep track of everything modified by this insn. */
1958 /* ??? Need to be careful w.r.t. mods done to INSN.
1959 Don't call mark_oprs_set if we turned the
1960 insn into a NOTE. */
1961 if (! NOTE_P (insn
))
1962 mark_oprs_set (insn
);
1966 changed
|= bypass_conditional_jumps ();
1970 free_hash_table (&set_hash_table
);
1972 obstack_free (&gcse_obstack
, NULL
);
1976 fprintf (dump_file
, "CPROP of %s, %d basic blocks, %d bytes needed, ",
1977 current_function_name (), n_basic_blocks
, bytes_used
);
1978 fprintf (dump_file
, "%d local const props, %d local copy props, ",
1979 local_const_prop_count
, local_copy_prop_count
);
1980 fprintf (dump_file
, "%d global const props, %d global copy props\n\n",
1981 global_const_prop_count
, global_copy_prop_count
);
1988 /* All the passes implemented in this file. Each pass has its
1989 own gate and execute function, and at the end of the file a
1990 pass definition for passes.c.
1992 We do not construct an accurate cfg in functions which call
1993 setjmp, so none of these passes runs if the function calls
1995 FIXME: Should just handle setjmp via REG_SETJMP notes. */
1998 gate_rtl_cprop (void)
2000 return optimize
> 0 && flag_gcse
2001 && !cfun
->calls_setjmp
2006 execute_rtl_cprop (void)
2009 delete_unreachable_blocks ();
2010 df_set_flags (DF_LR_RUN_DCE
);
2012 changed
= one_cprop_pass ();
2013 flag_rerun_cse_after_global_opts
|= changed
;
2019 struct rtl_opt_pass pass_rtl_cprop
=
2024 gate_rtl_cprop
, /* gate */
2025 execute_rtl_cprop
, /* execute */
2028 0, /* static_pass_number */
2029 TV_CPROP
, /* tv_id */
2030 PROP_cfglayout
, /* properties_required */
2031 0, /* properties_provided */
2032 0, /* properties_destroyed */
2033 0, /* todo_flags_start */
2034 TODO_df_finish
| TODO_verify_rtl_sharing
|
2036 TODO_verify_flow
| TODO_ggc_collect
/* todo_flags_finish */