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 cprop_obstack
;
56 struct reg_use
{rtx reg_rtx
; };
58 /* Occurrence of an expression.
59 There is one per basic block. If a pattern appears more than once the
60 last appearance is used. */
64 /* Next occurrence of this expression. */
66 /* The insn that computes the expression. */
70 typedef struct occr
*occr_t
;
72 DEF_VEC_ALLOC_P (occr_t
, heap
);
74 /* Hash table entry for an assignment expressions. */
78 /* The expression (DEST := SRC). */
82 /* Index in the available expression bitmaps. */
84 /* Next entry with the same hash. */
85 struct expr
*next_same_hash
;
86 /* List of available occurrence in basic blocks in the function.
87 An "available occurrence" is one that is the last occurrence in the
88 basic block and the operands are not modified by following statements in
89 the basic block [including this insn]. */
90 struct occr
*avail_occr
;
93 /* Hash table for copy propagation expressions.
94 Each hash table is an array of buckets.
95 ??? It is known that if it were an array of entries, structure elements
96 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
97 not clear whether in the final analysis a sufficient amount of memory would
98 be saved as the size of the available expression bitmaps would be larger
99 [one could build a mapping table without holes afterwards though].
100 Someday I'll perform the computation and figure it out. */
105 This is an array of `set_hash_table_size' elements. */
108 /* Size of the hash table, in elements. */
111 /* Number of hash table elements. */
112 unsigned int n_elems
;
115 /* Copy propagation hash table. */
116 static struct hash_table_d set_hash_table
;
118 /* Array of implicit set patterns indexed by basic block index. */
119 static rtx
*implicit_sets
;
121 /* Bitmap containing one bit for each register in the program.
122 Used when performing GCSE to track which registers have been set since
123 the start or end of the basic block while traversing that block. */
124 static regset reg_set_bitmap
;
126 /* Various variables for statistics gathering. */
128 /* Memory used in a pass.
129 This isn't intended to be absolutely precise. Its intent is only
130 to keep an eye on memory usage. */
131 static int bytes_used
;
133 /* Number of local constants propagated. */
134 static int local_const_prop_count
;
135 /* Number of local copies propagated. */
136 static int local_copy_prop_count
;
137 /* Number of global constants propagated. */
138 static int global_const_prop_count
;
139 /* Number of global copies propagated. */
140 static int global_copy_prop_count
;
143 #define GOBNEW(T) ((T *) cprop_alloc (sizeof (T)))
144 #define GOBNEWVAR(T, S) ((T *) cprop_alloc ((S)))
146 /* Cover function to obstack_alloc. */
149 cprop_alloc (unsigned long size
)
152 return obstack_alloc (&cprop_obstack
, size
);
155 /* Return nonzero if register X is unchanged from INSN to the end
156 of INSN's basic block. */
159 reg_available_p (const_rtx x
, const_rtx insn ATTRIBUTE_UNUSED
)
161 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
164 /* Hash a set of register REGNO.
166 Sets are hashed on the register that is set. This simplifies the PRE copy
169 ??? May need to make things more elaborate. Later, as necessary. */
172 hash_set (int regno
, int hash_table_size
)
177 return hash
% hash_table_size
;
180 /* Insert assignment DEST:=SET from INSN in the hash table.
181 DEST is a register and SET is a register or a suitable constant.
182 If the assignment is already present in the table, record it as
183 the last occurrence in INSN's basic block. */
186 insert_set_in_table (rtx dest
, rtx src
, rtx insn
, struct hash_table_d
*table
)
190 struct expr
*cur_expr
, *last_expr
= NULL
;
191 struct occr
*cur_occr
;
193 hash
= hash_set (REGNO (dest
), table
->size
);
195 for (cur_expr
= table
->table
[hash
]; cur_expr
;
196 cur_expr
= cur_expr
->next_same_hash
)
198 if (dest
== cur_expr
->dest
199 && src
== cur_expr
->src
)
204 last_expr
= cur_expr
;
209 cur_expr
= GOBNEW (struct expr
);
210 bytes_used
+= sizeof (struct expr
);
211 if (table
->table
[hash
] == NULL
)
212 /* This is the first pattern that hashed to this index. */
213 table
->table
[hash
] = cur_expr
;
215 /* Add EXPR to end of this hash chain. */
216 last_expr
->next_same_hash
= cur_expr
;
218 /* Set the fields of the expr element.
219 We must copy X because it can be modified when copy propagation is
220 performed on its operands. */
221 cur_expr
->dest
= copy_rtx (dest
);
222 cur_expr
->src
= copy_rtx (src
);
223 cur_expr
->bitmap_index
= table
->n_elems
++;
224 cur_expr
->next_same_hash
= NULL
;
225 cur_expr
->avail_occr
= NULL
;
228 /* Now record the occurrence. */
229 cur_occr
= cur_expr
->avail_occr
;
232 && BLOCK_FOR_INSN (cur_occr
->insn
) == BLOCK_FOR_INSN (insn
))
234 /* Found another instance of the expression in the same basic block.
235 Prefer this occurrence to the currently recorded one. We want
236 the last one in the block and the block is scanned from start
238 cur_occr
->insn
= insn
;
242 /* First occurrence of this expression in this basic block. */
243 cur_occr
= GOBNEW (struct occr
);
244 bytes_used
+= sizeof (struct occr
);
245 cur_occr
->insn
= insn
;
246 cur_occr
->next
= cur_expr
->avail_occr
;
247 cur_expr
->avail_occr
= cur_occr
;
251 /* Determine whether the rtx X should be treated as a constant for CPROP.
252 Since X might be inserted more than once we have to take care that it
256 cprop_constant_p (const_rtx x
)
258 return CONSTANT_P (x
) && (GET_CODE (x
) != CONST
|| shared_const_p (x
));
261 /* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or
265 hash_scan_set (rtx pat
, rtx insn
, struct hash_table_d
*table
)
267 rtx src
= SET_SRC (pat
);
268 rtx dest
= SET_DEST (pat
);
271 && ! HARD_REGISTER_P (dest
)
272 && reg_available_p (dest
, insn
)
273 && can_copy_p (GET_MODE (dest
)))
275 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
277 This allows us to do a single CPROP pass and still eliminate
278 redundant constants, addresses or other expressions that are
279 constructed with multiple instructions.
281 However, keep the original SRC if INSN is a simple reg-reg move. In
282 In this case, there will almost always be a REG_EQUAL note on the
283 insn that sets SRC. By recording the REG_EQUAL value here as SRC
284 for INSN, we miss copy propagation opportunities.
286 Note that this does not impede profitable constant propagations. We
287 "look through" reg-reg sets in lookup_set. */
288 rtx note
= find_reg_equal_equiv_note (insn
);
290 && REG_NOTE_KIND (note
) == REG_EQUAL
292 && cprop_constant_p (XEXP (note
, 0)))
293 src
= XEXP (note
, 0), pat
= gen_rtx_SET (VOIDmode
, dest
, src
);
295 /* Record sets for constant/copy propagation. */
298 && ! HARD_REGISTER_P (src
)
299 && reg_available_p (src
, insn
))
300 || cprop_constant_p (src
))
301 insert_set_in_table (dest
, src
, insn
, table
);
305 /* Process INSN and add hash table entries as appropriate.
307 Only available expressions that set a single pseudo-reg are recorded.
309 Single sets in a PARALLEL could be handled, but it's an extra complication
310 that isn't dealt with right now. The trick is handling the CLOBBERs that
311 are also in the PARALLEL. Later.
313 If SET_P is nonzero, this is for the assignment hash table,
314 otherwise it is for the expression hash table. */
317 hash_scan_insn (rtx insn
, struct hash_table_d
*table
)
319 rtx pat
= PATTERN (insn
);
322 /* Pick out the sets of INSN and for other forms of instructions record
323 what's been modified. */
325 if (GET_CODE (pat
) == SET
)
326 hash_scan_set (pat
, insn
, table
);
327 else if (GET_CODE (pat
) == PARALLEL
)
328 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
330 rtx x
= XVECEXP (pat
, 0, i
);
332 if (GET_CODE (x
) == SET
)
333 hash_scan_set (x
, insn
, table
);
338 dump_hash_table (FILE *file
, const char *name
, struct hash_table_d
*table
)
341 /* Flattened out table, so it's printed in proper order. */
342 struct expr
**flat_table
;
343 unsigned int *hash_val
;
346 flat_table
= XCNEWVEC (struct expr
*, table
->n_elems
);
347 hash_val
= XNEWVEC (unsigned int, table
->n_elems
);
349 for (i
= 0; i
< (int) table
->size
; i
++)
350 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
352 flat_table
[expr
->bitmap_index
] = expr
;
353 hash_val
[expr
->bitmap_index
] = i
;
356 fprintf (file
, "%s hash table (%d buckets, %d entries)\n",
357 name
, table
->size
, table
->n_elems
);
359 for (i
= 0; i
< (int) table
->n_elems
; i
++)
360 if (flat_table
[i
] != 0)
362 expr
= flat_table
[i
];
363 fprintf (file
, "Index %d (hash value %d)\n ",
364 expr
->bitmap_index
, hash_val
[i
]);
365 print_rtl (file
, expr
->dest
);
366 fprintf (file
, " := ");
367 print_rtl (file
, expr
->src
);
368 fprintf (file
, "\n");
371 fprintf (file
, "\n");
377 /* Record as unavailable all registers that are DEF operands of INSN. */
379 make_set_regs_unavailable (rtx insn
)
381 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
384 for (def_rec
= DF_INSN_INFO_DEFS (insn_info
); *def_rec
; def_rec
++)
385 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (*def_rec
));
388 /* Top level function to create an assignments hash table.
390 Assignment entries are placed in the hash table if
391 - they are of the form (set (pseudo-reg) src),
392 - src is something we want to perform const/copy propagation on,
393 - none of the operands or target are subsequently modified in the block
395 Currently src must be a pseudo-reg or a const_int.
397 TABLE is the table computed. */
400 compute_hash_table_work (struct hash_table_d
*table
)
404 /* Allocate vars to track sets of regs. */
405 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
411 /* Reset tables used to keep track of what's not yet invalid [since
412 the end of the block]. */
413 CLEAR_REG_SET (reg_set_bitmap
);
415 /* Go over all insns from the last to the first. This is convenient
416 for tracking available registers, i.e. not set between INSN and
417 the end of the basic block BB. */
418 FOR_BB_INSNS_REVERSE (bb
, insn
)
420 /* Only real insns are interesting. */
421 if (!NONDEBUG_INSN_P (insn
))
424 /* Record interesting sets from INSN in the hash table. */
425 hash_scan_insn (insn
, table
);
427 /* Any registers set in INSN will make SETs above it not AVAIL. */
428 make_set_regs_unavailable (insn
);
431 /* Insert implicit sets in the hash table, pretending they appear as
432 insns at the head of the basic block. */
433 if (implicit_sets
[bb
->index
] != NULL_RTX
)
434 hash_scan_set (implicit_sets
[bb
->index
], BB_HEAD (bb
), table
);
437 FREE_REG_SET (reg_set_bitmap
);
440 /* Allocate space for the set/expr hash TABLE.
441 It is used to determine the number of buckets to use. */
444 alloc_hash_table (struct hash_table_d
*table
)
448 n
= get_max_insn_count ();
451 if (table
->size
< 11)
454 /* Attempt to maintain efficient use of hash table.
455 Making it an odd number is simplest for now.
456 ??? Later take some measurements. */
458 n
= table
->size
* sizeof (struct expr
*);
459 table
->table
= XNEWVAR (struct expr
*, n
);
462 /* Free things allocated by alloc_hash_table. */
465 free_hash_table (struct hash_table_d
*table
)
470 /* Compute the hash TABLE for doing copy/const propagation or
471 expression hash table. */
474 compute_hash_table (struct hash_table_d
*table
)
476 /* Initialize count of number of entries in hash table. */
478 memset (table
->table
, 0, table
->size
* sizeof (struct expr
*));
480 compute_hash_table_work (table
);
483 /* Expression tracking support. */
485 /* Lookup REGNO in the set TABLE. The result is a pointer to the
486 table entry, or NULL if not found. */
489 lookup_set (unsigned int regno
, struct hash_table_d
*table
)
491 unsigned int hash
= hash_set (regno
, table
->size
);
494 expr
= table
->table
[hash
];
496 while (expr
&& REGNO (expr
->dest
) != regno
)
497 expr
= expr
->next_same_hash
;
502 /* Return the next entry for REGNO in list EXPR. */
505 next_set (unsigned int regno
, struct expr
*expr
)
508 expr
= expr
->next_same_hash
;
509 while (expr
&& REGNO (expr
->dest
) != regno
);
514 /* Reset tables used to keep track of what's still available [since the
515 start of the block]. */
518 reset_opr_set_tables (void)
520 /* Maintain a bitmap of which regs have been set since beginning of
522 CLEAR_REG_SET (reg_set_bitmap
);
525 /* Return nonzero if the register X has not been set yet [since the
526 start of the basic block containing INSN]. */
529 reg_not_set_p (const_rtx x
, const_rtx insn ATTRIBUTE_UNUSED
)
531 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
534 /* Record things set by INSN.
535 This data is used by reg_not_set_p. */
538 mark_oprs_set (rtx insn
)
540 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
543 for (def_rec
= DF_INSN_INFO_DEFS (insn_info
); *def_rec
; def_rec
++)
544 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (*def_rec
));
548 /* Compute copy/constant propagation working variables. */
550 /* Local properties of assignments. */
551 static sbitmap
*cprop_pavloc
;
552 static sbitmap
*cprop_absaltered
;
554 /* Global properties of assignments (computed from the local properties). */
555 static sbitmap
*cprop_avin
;
556 static sbitmap
*cprop_avout
;
558 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
559 basic blocks. N_SETS is the number of sets. */
562 alloc_cprop_mem (int n_blocks
, int n_sets
)
564 cprop_pavloc
= sbitmap_vector_alloc (n_blocks
, n_sets
);
565 cprop_absaltered
= sbitmap_vector_alloc (n_blocks
, n_sets
);
567 cprop_avin
= sbitmap_vector_alloc (n_blocks
, n_sets
);
568 cprop_avout
= sbitmap_vector_alloc (n_blocks
, n_sets
);
571 /* Free vars used by copy/const propagation. */
574 free_cprop_mem (void)
576 sbitmap_vector_free (cprop_pavloc
);
577 sbitmap_vector_free (cprop_absaltered
);
578 sbitmap_vector_free (cprop_avin
);
579 sbitmap_vector_free (cprop_avout
);
582 /* Compute the local properties of each recorded expression.
584 Local properties are those that are defined by the block, irrespective of
587 An expression is transparent in a block if its operands are not modified
590 An expression is computed (locally available) in a block if it is computed
591 at least once and expression would contain the same value if the
592 computation was moved to the end of the block.
594 TRANSP and COMP are destination sbitmaps for recording local properties. */
597 compute_local_properties (sbitmap
*transp
, sbitmap
*comp
,
598 struct hash_table_d
*table
)
602 /* Initialize the bitmaps that were passed in. */
603 sbitmap_vector_zero (transp
, last_basic_block
);
604 sbitmap_vector_zero (comp
, last_basic_block
);
606 for (i
= 0; i
< table
->size
; i
++)
610 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
612 int indx
= expr
->bitmap_index
;
616 /* The expression is transparent in a block if it is not killed,
617 i.e. DEST and SRC are not set or clobbered in the block.
618 We start by assuming all are transparent [none are killed],
619 and then set the bits for those that are. */
620 for (def
= DF_REG_DEF_CHAIN (REGNO (expr
->dest
));
621 def
; def
= DF_REF_NEXT_REG (def
))
622 SET_BIT (transp
[DF_REF_BB (def
)->index
], indx
);
623 if (REG_P (expr
->src
))
624 for (def
= DF_REG_DEF_CHAIN (REGNO (expr
->src
));
625 def
; def
= DF_REF_NEXT_REG (def
))
626 SET_BIT (transp
[DF_REF_BB (def
)->index
], indx
);
628 /* The occurrences recorded in avail_occr are exactly those that
629 we want to set to nonzero in COMP. */
630 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
632 SET_BIT (comp
[BLOCK_FOR_INSN (occr
->insn
)->index
], indx
);
638 /* Hash table support. */
640 /* Top level routine to do the dataflow analysis needed by copy/const
644 compute_cprop_data (void)
646 compute_local_properties (cprop_absaltered
, cprop_pavloc
, &set_hash_table
);
647 compute_available (cprop_pavloc
, cprop_absaltered
,
648 cprop_avout
, cprop_avin
);
651 /* Copy/constant propagation. */
653 /* Maximum number of register uses in an insn that we handle. */
656 /* Table of uses found in an insn.
657 Allocated statically to avoid alloc/free complexity and overhead. */
658 static struct reg_use reg_use_table
[MAX_USES
];
660 /* Index into `reg_use_table' while building it. */
661 static int reg_use_count
;
663 /* Set up a list of register numbers used in INSN. The found uses are stored
664 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
665 and contains the number of uses in the table upon exit.
667 ??? If a register appears multiple times we will record it multiple times.
668 This doesn't hurt anything but it will slow things down. */
671 find_used_regs (rtx
*xptr
, void *data ATTRIBUTE_UNUSED
)
678 /* repeat is used to turn tail-recursion into iteration since GCC
679 can't do it when there's no return value. */
687 if (reg_use_count
== MAX_USES
)
690 reg_use_table
[reg_use_count
].reg_rtx
= x
;
694 /* Recursively scan the operands of this expression. */
696 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
700 /* If we are about to do the last recursive call
701 needed at this level, change it into iteration.
702 This function is called enough to be worth it. */
709 find_used_regs (&XEXP (x
, i
), data
);
711 else if (fmt
[i
] == 'E')
712 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
713 find_used_regs (&XVECEXP (x
, i
, j
), data
);
717 /* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO.
718 Returns nonzero is successful. */
721 try_replace_reg (rtx from
, rtx to
, rtx insn
)
723 rtx note
= find_reg_equal_equiv_note (insn
);
726 rtx set
= single_set (insn
);
728 /* Usually we substitute easy stuff, so we won't copy everything.
729 We however need to take care to not duplicate non-trivial CONST
733 validate_replace_src_group (from
, to
, insn
);
734 if (num_changes_pending () && apply_change_group ())
737 /* Try to simplify SET_SRC if we have substituted a constant. */
738 if (success
&& set
&& CONSTANT_P (to
))
740 src
= simplify_rtx (SET_SRC (set
));
743 validate_change (insn
, &SET_SRC (set
), src
, 0);
746 /* If there is already a REG_EQUAL note, update the expression in it
747 with our replacement. */
748 if (note
!= 0 && REG_NOTE_KIND (note
) == REG_EQUAL
)
749 set_unique_reg_note (insn
, REG_EQUAL
,
750 simplify_replace_rtx (XEXP (note
, 0), from
, to
));
751 if (!success
&& set
&& reg_mentioned_p (from
, SET_SRC (set
)))
753 /* If above failed and this is a single set, try to simplify the source of
754 the set given our substitution. We could perhaps try this for multiple
755 SETs, but it probably won't buy us anything. */
756 src
= simplify_replace_rtx (SET_SRC (set
), from
, to
);
758 if (!rtx_equal_p (src
, SET_SRC (set
))
759 && validate_change (insn
, &SET_SRC (set
), src
, 0))
762 /* If we've failed perform the replacement, have a single SET to
763 a REG destination and don't yet have a note, add a REG_EQUAL note
764 to not lose information. */
765 if (!success
&& note
== 0 && set
!= 0 && REG_P (SET_DEST (set
)))
766 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
769 /* REG_EQUAL may get simplified into register.
770 We don't allow that. Remove that note. This code ought
771 not to happen, because previous code ought to synthesize
772 reg-reg move, but be on the safe side. */
773 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
&& REG_P (XEXP (note
, 0)))
774 remove_note (insn
, note
);
779 /* Find a set of REGNOs that are available on entry to INSN's block. Returns
780 NULL no such set is found. */
783 find_avail_set (int regno
, rtx insn
)
785 /* SET1 contains the last set found that can be returned to the caller for
786 use in a substitution. */
787 struct expr
*set1
= 0;
789 /* Loops are not possible here. To get a loop we would need two sets
790 available at the start of the block containing INSN. i.e. we would
791 need two sets like this available at the start of the block:
793 (set (reg X) (reg Y))
794 (set (reg Y) (reg X))
796 This can not happen since the set of (reg Y) would have killed the
797 set of (reg X) making it unavailable at the start of this block. */
801 struct expr
*set
= lookup_set (regno
, &set_hash_table
);
803 /* Find a set that is available at the start of the block
804 which contains INSN. */
807 if (TEST_BIT (cprop_avin
[BLOCK_FOR_INSN (insn
)->index
],
810 set
= next_set (regno
, set
);
813 /* If no available set was found we've reached the end of the
814 (possibly empty) copy chain. */
820 /* We know the set is available.
821 Now check that SRC is locally anticipatable (i.e. none of the
822 source operands have changed since the start of the block).
824 If the source operand changed, we may still use it for the next
825 iteration of this loop, but we may not use it for substitutions. */
827 if (cprop_constant_p (src
) || reg_not_set_p (src
, insn
))
830 /* If the source of the set is anything except a register, then
831 we have reached the end of the copy chain. */
835 /* Follow the copy chain, i.e. start another iteration of the loop
836 and see if we have an available copy into SRC. */
840 /* SET1 holds the last set that was available and anticipatable at
845 /* Subroutine of cprop_insn that tries to propagate constants into
846 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
847 it is the instruction that immediately precedes JUMP, and must be a
848 single SET of a register. FROM is what we will try to replace,
849 SRC is the constant we will try to substitute for it. Returns nonzero
850 if a change was made. */
853 cprop_jump (basic_block bb
, rtx setcc
, rtx jump
, rtx from
, rtx src
)
855 rtx new_rtx
, set_src
, note_src
;
856 rtx set
= pc_set (jump
);
857 rtx note
= find_reg_equal_equiv_note (jump
);
861 note_src
= XEXP (note
, 0);
862 if (GET_CODE (note_src
) == EXPR_LIST
)
865 else note_src
= NULL_RTX
;
867 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
868 set_src
= note_src
? note_src
: SET_SRC (set
);
870 /* First substitute the SETCC condition into the JUMP instruction,
871 then substitute that given values into this expanded JUMP. */
872 if (setcc
!= NULL_RTX
873 && !modified_between_p (from
, setcc
, jump
)
874 && !modified_between_p (src
, setcc
, jump
))
877 rtx setcc_set
= single_set (setcc
);
878 rtx setcc_note
= find_reg_equal_equiv_note (setcc
);
879 setcc_src
= (setcc_note
&& GET_CODE (XEXP (setcc_note
, 0)) != EXPR_LIST
)
880 ? XEXP (setcc_note
, 0) : SET_SRC (setcc_set
);
881 set_src
= simplify_replace_rtx (set_src
, SET_DEST (setcc_set
),
887 new_rtx
= simplify_replace_rtx (set_src
, from
, src
);
889 /* If no simplification can be made, then try the next register. */
890 if (rtx_equal_p (new_rtx
, SET_SRC (set
)))
893 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
894 if (new_rtx
== pc_rtx
)
898 /* Ensure the value computed inside the jump insn to be equivalent
899 to one computed by setcc. */
900 if (setcc
&& modified_in_p (new_rtx
, setcc
))
902 if (! validate_unshare_change (jump
, &SET_SRC (set
), new_rtx
, 0))
904 /* When (some) constants are not valid in a comparison, and there
905 are two registers to be replaced by constants before the entire
906 comparison can be folded into a constant, we need to keep
907 intermediate information in REG_EQUAL notes. For targets with
908 separate compare insns, such notes are added by try_replace_reg.
909 When we have a combined compare-and-branch instruction, however,
910 we need to attach a note to the branch itself to make this
911 optimization work. */
913 if (!rtx_equal_p (new_rtx
, note_src
))
914 set_unique_reg_note (jump
, REG_EQUAL
, copy_rtx (new_rtx
));
918 /* Remove REG_EQUAL note after simplification. */
920 remove_note (jump
, note
);
924 /* Delete the cc0 setter. */
925 if (setcc
!= NULL
&& CC0_P (SET_DEST (single_set (setcc
))))
929 global_const_prop_count
++;
930 if (dump_file
!= NULL
)
933 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with constant ",
934 REGNO (from
), INSN_UID (jump
));
935 print_rtl (dump_file
, src
);
936 fprintf (dump_file
, "\n");
938 purge_dead_edges (bb
);
940 /* If a conditional jump has been changed into unconditional jump, remove
941 the jump and make the edge fallthru - this is always called in
943 if (new_rtx
!= pc_rtx
&& simplejump_p (jump
))
948 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
949 if (e
->dest
!= EXIT_BLOCK_PTR
950 && BB_HEAD (e
->dest
) == JUMP_LABEL (jump
))
952 e
->flags
|= EDGE_FALLTHRU
;
962 constprop_register (rtx insn
, rtx from
, rtx to
)
966 /* Check for reg or cc0 setting instructions followed by
967 conditional branch instructions first. */
968 if ((sset
= single_set (insn
)) != NULL
970 && any_condjump_p (NEXT_INSN (insn
)) && onlyjump_p (NEXT_INSN (insn
)))
972 rtx dest
= SET_DEST (sset
);
973 if ((REG_P (dest
) || CC0_P (dest
))
974 && cprop_jump (BLOCK_FOR_INSN (insn
), insn
, NEXT_INSN (insn
), from
, to
))
978 /* Handle normal insns next. */
979 if (NONJUMP_INSN_P (insn
)
980 && try_replace_reg (from
, to
, insn
))
983 /* Try to propagate a CONST_INT into a conditional jump.
984 We're pretty specific about what we will handle in this
985 code, we can extend this as necessary over time.
987 Right now the insn in question must look like
988 (set (pc) (if_then_else ...)) */
989 else if (any_condjump_p (insn
) && onlyjump_p (insn
))
990 return cprop_jump (BLOCK_FOR_INSN (insn
), NULL
, insn
, from
, to
);
994 /* Perform constant and copy propagation on INSN.
995 The result is nonzero if a change was made. */
998 cprop_insn (rtx insn
)
1000 struct reg_use
*reg_used
;
1005 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1007 /* We may win even when propagating constants into notes. */
1008 note
= find_reg_equal_equiv_note (insn
);
1010 find_used_regs (&XEXP (note
, 0), NULL
);
1012 for (reg_used
= ®_use_table
[0]; reg_use_count
> 0;
1013 reg_used
++, reg_use_count
--)
1015 unsigned int regno
= REGNO (reg_used
->reg_rtx
);
1019 /* If the register has already been set in this block, there's
1020 nothing we can do. */
1021 if (! reg_not_set_p (reg_used
->reg_rtx
, insn
))
1024 /* Find an assignment that sets reg_used and is available
1025 at the start of the block. */
1026 set
= find_avail_set (regno
, insn
);
1032 /* Constant propagation. */
1033 if (cprop_constant_p (src
))
1035 if (constprop_register (insn
, reg_used
->reg_rtx
, src
))
1038 global_const_prop_count
++;
1039 if (dump_file
!= NULL
)
1041 fprintf (dump_file
, "GLOBAL CONST-PROP: Replacing reg %d in ", regno
);
1042 fprintf (dump_file
, "insn %d with constant ", INSN_UID (insn
));
1043 print_rtl (dump_file
, src
);
1044 fprintf (dump_file
, "\n");
1046 if (INSN_DELETED_P (insn
))
1050 else if (REG_P (src
)
1051 && REGNO (src
) >= FIRST_PSEUDO_REGISTER
1052 && REGNO (src
) != regno
)
1054 if (try_replace_reg (reg_used
->reg_rtx
, src
, insn
))
1057 global_copy_prop_count
++;
1058 if (dump_file
!= NULL
)
1060 fprintf (dump_file
, "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1061 regno
, INSN_UID (insn
));
1062 fprintf (dump_file
, " with reg %d\n", REGNO (src
));
1065 /* The original insn setting reg_used may or may not now be
1066 deletable. We leave the deletion to DCE. */
1067 /* FIXME: If it turns out that the insn isn't deletable,
1068 then we may have unnecessarily extended register lifetimes
1069 and made things worse. */
1074 if (changed
&& DEBUG_INSN_P (insn
))
1080 /* Like find_used_regs, but avoid recording uses that appear in
1081 input-output contexts such as zero_extract or pre_dec. This
1082 restricts the cases we consider to those for which local cprop
1083 can legitimately make replacements. */
1086 local_cprop_find_used_regs (rtx
*xptr
, void *data
)
1093 switch (GET_CODE (x
))
1097 case STRICT_LOW_PART
:
1106 /* Can only legitimately appear this early in the context of
1107 stack pushes for function arguments, but handle all of the
1108 codes nonetheless. */
1112 /* Setting a subreg of a register larger than word_mode leaves
1113 the non-written words unchanged. */
1114 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x
))) > BITS_PER_WORD
)
1122 find_used_regs (xptr
, data
);
1125 /* Try to perform local const/copy propagation on X in INSN. */
1128 do_local_cprop (rtx x
, rtx insn
)
1130 rtx newreg
= NULL
, newcnst
= NULL
;
1132 /* Rule out USE instructions and ASM statements as we don't want to
1133 change the hard registers mentioned. */
1135 && (REGNO (x
) >= FIRST_PSEUDO_REGISTER
1136 || (GET_CODE (PATTERN (insn
)) != USE
1137 && asm_noperands (PATTERN (insn
)) < 0)))
1139 cselib_val
*val
= cselib_lookup (x
, GET_MODE (x
), 0, VOIDmode
);
1140 struct elt_loc_list
*l
;
1144 for (l
= val
->locs
; l
; l
= l
->next
)
1146 rtx this_rtx
= l
->loc
;
1149 if (cprop_constant_p (this_rtx
))
1151 if (REG_P (this_rtx
) && REGNO (this_rtx
) >= FIRST_PSEUDO_REGISTER
1152 /* Don't copy propagate if it has attached REG_EQUIV note.
1153 At this point this only function parameters should have
1154 REG_EQUIV notes and if the argument slot is used somewhere
1155 explicitly, it means address of parameter has been taken,
1156 so we should not extend the lifetime of the pseudo. */
1157 && (!(note
= find_reg_note (l
->setting_insn
, REG_EQUIV
, NULL_RTX
))
1158 || ! MEM_P (XEXP (note
, 0))))
1161 if (newcnst
&& constprop_register (insn
, x
, newcnst
))
1163 if (dump_file
!= NULL
)
1165 fprintf (dump_file
, "LOCAL CONST-PROP: Replacing reg %d in ",
1167 fprintf (dump_file
, "insn %d with constant ",
1169 print_rtl (dump_file
, newcnst
);
1170 fprintf (dump_file
, "\n");
1172 local_const_prop_count
++;
1175 else if (newreg
&& newreg
!= x
&& try_replace_reg (x
, newreg
, insn
))
1177 if (dump_file
!= NULL
)
1180 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1181 REGNO (x
), INSN_UID (insn
));
1182 fprintf (dump_file
, " with reg %d\n", REGNO (newreg
));
1184 local_copy_prop_count
++;
1191 /* Do local const/copy propagation (i.e. within each basic block). */
1194 local_cprop_pass (void)
1198 struct reg_use
*reg_used
;
1199 bool changed
= false;
1204 FOR_BB_INSNS (bb
, insn
)
1208 rtx note
= find_reg_equal_equiv_note (insn
);
1212 note_uses (&PATTERN (insn
), local_cprop_find_used_regs
,
1215 local_cprop_find_used_regs (&XEXP (note
, 0), NULL
);
1217 for (reg_used
= ®_use_table
[0]; reg_use_count
> 0;
1218 reg_used
++, reg_use_count
--)
1220 if (do_local_cprop (reg_used
->reg_rtx
, insn
))
1226 if (INSN_DELETED_P (insn
))
1229 while (reg_use_count
);
1231 cselib_process_insn (insn
);
1234 /* Forget everything at the end of a basic block. */
1235 cselib_clear_table ();
1243 /* Similar to get_condition, only the resulting condition must be
1244 valid at JUMP, instead of at EARLIEST.
1246 This differs from noce_get_condition in ifcvt.c in that we prefer not to
1247 settle for the condition variable in the jump instruction being integral.
1248 We prefer to be able to record the value of a user variable, rather than
1249 the value of a temporary used in a condition. This could be solved by
1250 recording the value of *every* register scanned by canonicalize_condition,
1251 but this would require some code reorganization. */
1254 fis_get_condition (rtx jump
)
1256 return get_condition (jump
, NULL
, false, true);
1259 /* Check the comparison COND to see if we can safely form an implicit
1263 implicit_set_cond_p (const_rtx cond
)
1265 enum machine_mode mode
;
1268 /* COND must be either an EQ or NE comparison. */
1269 if (GET_CODE (cond
) != EQ
&& GET_CODE (cond
) != NE
)
1272 /* The first operand of COND must be a pseudo-reg. */
1273 if (! REG_P (XEXP (cond
, 0))
1274 || HARD_REGISTER_P (XEXP (cond
, 0)))
1277 /* The second operand of COND must be a suitable constant. */
1278 mode
= GET_MODE (XEXP (cond
, 0));
1279 cst
= XEXP (cond
, 1);
1281 /* We can't perform this optimization if either operand might be or might
1282 contain a signed zero. */
1283 if (HONOR_SIGNED_ZEROS (mode
))
1285 /* It is sufficient to check if CST is or contains a zero. We must
1286 handle float, complex, and vector. If any subpart is a zero, then
1287 the optimization can't be performed. */
1288 /* ??? The complex and vector checks are not implemented yet. We just
1289 always return zero for them. */
1290 if (GET_CODE (cst
) == CONST_DOUBLE
)
1293 REAL_VALUE_FROM_CONST_DOUBLE (d
, cst
);
1294 if (REAL_VALUES_EQUAL (d
, dconst0
))
1301 return cprop_constant_p (cst
);
1304 /* Find the implicit sets of a function. An "implicit set" is a constraint
1305 on the value of a variable, implied by a conditional jump. For example,
1306 following "if (x == 2)", the then branch may be optimized as though the
1307 conditional performed an "explicit set", in this example, "x = 2". This
1308 function records the set patterns that are implicit at the start of each
1311 If an implicit set is found but the set is implicit on a critical edge,
1312 this critical edge is split.
1314 Return true if the CFG was modified, false otherwise. */
1317 find_implicit_sets (void)
1319 basic_block bb
, dest
;
1321 unsigned int count
= 0;
1322 bool edges_split
= false;
1323 size_t implicit_sets_size
= last_basic_block
+ 10;
1325 implicit_sets
= XCNEWVEC (rtx
, implicit_sets_size
);
1329 /* Check for more than one successor. */
1330 if (! EDGE_COUNT (bb
->succs
) > 1)
1333 cond
= fis_get_condition (BB_END (bb
));
1335 /* If no condition is found or if it isn't of a suitable form,
1337 if (! cond
|| ! implicit_set_cond_p (cond
))
1340 dest
= GET_CODE (cond
) == EQ
1341 ? BRANCH_EDGE (bb
)->dest
: FALLTHRU_EDGE (bb
)->dest
;
1343 /* If DEST doesn't go anywhere, ignore it. */
1344 if (! dest
|| dest
== EXIT_BLOCK_PTR
)
1347 /* We have found a suitable implicit set. Try to record it now as
1348 a SET in DEST. If DEST has more than one predecessor, the edge
1349 between BB and DEST is a critical edge and we must split it,
1350 because we can only record one implicit set per DEST basic block. */
1351 if (! single_pred_p (dest
))
1353 dest
= split_edge (find_edge (bb
, dest
));
1357 if (implicit_sets_size
<= (size_t) dest
->index
)
1359 size_t old_implicit_sets_size
= implicit_sets_size
;
1360 implicit_sets_size
*= 2;
1361 implicit_sets
= XRESIZEVEC (rtx
, implicit_sets
, implicit_sets_size
);
1362 memset (implicit_sets
+ old_implicit_sets_size
, 0,
1363 (implicit_sets_size
- old_implicit_sets_size
) * sizeof (rtx
));
1366 new_rtx
= gen_rtx_SET (VOIDmode
, XEXP (cond
, 0),
1368 implicit_sets
[dest
->index
] = new_rtx
;
1371 fprintf(dump_file
, "Implicit set of reg %d in ",
1372 REGNO (XEXP (cond
, 0)));
1373 fprintf(dump_file
, "basic block %d\n", dest
->index
);
1379 fprintf (dump_file
, "Found %d implicit sets\n", count
);
1381 /* Confess our sins. */
1385 /* Bypass conditional jumps. */
1387 /* The value of last_basic_block at the beginning of the jump_bypass
1388 pass. The use of redirect_edge_and_branch_force may introduce new
1389 basic blocks, but the data flow analysis is only valid for basic
1390 block indices less than bypass_last_basic_block. */
1392 static int bypass_last_basic_block
;
1394 /* Find a set of REGNO to a constant that is available at the end of basic
1395 block BB. Returns NULL if no such set is found. Based heavily upon
1398 static struct expr
*
1399 find_bypass_set (int regno
, int bb
)
1401 struct expr
*result
= 0;
1406 struct expr
*set
= lookup_set (regno
, &set_hash_table
);
1410 if (TEST_BIT (cprop_avout
[bb
], set
->bitmap_index
))
1412 set
= next_set (regno
, set
);
1419 if (cprop_constant_p (src
))
1425 regno
= REGNO (src
);
1431 /* Subroutine of bypass_block that checks whether a pseudo is killed by
1432 any of the instructions inserted on an edge. Jump bypassing places
1433 condition code setters on CFG edges using insert_insn_on_edge. This
1434 function is required to check that our data flow analysis is still
1435 valid prior to commit_edge_insertions. */
1438 reg_killed_on_edge (const_rtx reg
, const_edge e
)
1442 for (insn
= e
->insns
.r
; insn
; insn
= NEXT_INSN (insn
))
1443 if (INSN_P (insn
) && reg_set_p (reg
, insn
))
1449 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1450 basic block BB which has more than one predecessor. If not NULL, SETCC
1451 is the first instruction of BB, which is immediately followed by JUMP_INSN
1452 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1453 Returns nonzero if a change was made.
1455 During the jump bypassing pass, we may place copies of SETCC instructions
1456 on CFG edges. The following routine must be careful to pay attention to
1457 these inserted insns when performing its transformations. */
1460 bypass_block (basic_block bb
, rtx setcc
, rtx jump
)
1465 int may_be_loop_header
;
1469 insn
= (setcc
!= NULL
) ? setcc
: jump
;
1471 /* Determine set of register uses in INSN. */
1473 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1474 note
= find_reg_equal_equiv_note (insn
);
1476 find_used_regs (&XEXP (note
, 0), NULL
);
1478 may_be_loop_header
= false;
1479 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1480 if (e
->flags
& EDGE_DFS_BACK
)
1482 may_be_loop_header
= true;
1487 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
1491 if (e
->flags
& EDGE_COMPLEX
)
1497 /* We can't redirect edges from new basic blocks. */
1498 if (e
->src
->index
>= bypass_last_basic_block
)
1504 /* The irreducible loops created by redirecting of edges entering the
1505 loop from outside would decrease effectiveness of some of the following
1506 optimizations, so prevent this. */
1507 if (may_be_loop_header
1508 && !(e
->flags
& EDGE_DFS_BACK
))
1514 for (i
= 0; i
< reg_use_count
; i
++)
1516 struct reg_use
*reg_used
= ®_use_table
[i
];
1517 unsigned int regno
= REGNO (reg_used
->reg_rtx
);
1518 basic_block dest
, old_dest
;
1522 set
= find_bypass_set (regno
, e
->src
->index
);
1527 /* Check the data flow is valid after edge insertions. */
1528 if (e
->insns
.r
&& reg_killed_on_edge (reg_used
->reg_rtx
, e
))
1531 src
= SET_SRC (pc_set (jump
));
1534 src
= simplify_replace_rtx (src
,
1535 SET_DEST (PATTERN (setcc
)),
1536 SET_SRC (PATTERN (setcc
)));
1538 new_rtx
= simplify_replace_rtx (src
, reg_used
->reg_rtx
,
1541 /* Jump bypassing may have already placed instructions on
1542 edges of the CFG. We can't bypass an outgoing edge that
1543 has instructions associated with it, as these insns won't
1544 get executed if the incoming edge is redirected. */
1546 if (new_rtx
== pc_rtx
)
1548 edest
= FALLTHRU_EDGE (bb
);
1549 dest
= edest
->insns
.r
? NULL
: edest
->dest
;
1551 else if (GET_CODE (new_rtx
) == LABEL_REF
)
1553 dest
= BLOCK_FOR_INSN (XEXP (new_rtx
, 0));
1554 /* Don't bypass edges containing instructions. */
1555 edest
= find_edge (bb
, dest
);
1556 if (edest
&& edest
->insns
.r
)
1562 /* Avoid unification of the edge with other edges from original
1563 branch. We would end up emitting the instruction on "both"
1566 if (dest
&& setcc
&& !CC0_P (SET_DEST (PATTERN (setcc
)))
1567 && find_edge (e
->src
, dest
))
1573 && dest
!= EXIT_BLOCK_PTR
)
1575 redirect_edge_and_branch_force (e
, dest
);
1577 /* Copy the register setter to the redirected edge.
1578 Don't copy CC0 setters, as CC0 is dead after jump. */
1581 rtx pat
= PATTERN (setcc
);
1582 if (!CC0_P (SET_DEST (pat
)))
1583 insert_insn_on_edge (copy_insn (pat
), e
);
1586 if (dump_file
!= NULL
)
1588 fprintf (dump_file
, "JUMP-BYPASS: Proved reg %d "
1589 "in jump_insn %d equals constant ",
1590 regno
, INSN_UID (jump
));
1591 print_rtl (dump_file
, set
->src
);
1592 fprintf (dump_file
, "\nBypass edge from %d->%d to %d\n",
1593 e
->src
->index
, old_dest
->index
, dest
->index
);
1606 /* Find basic blocks with more than one predecessor that only contain a
1607 single conditional jump. If the result of the comparison is known at
1608 compile-time from any incoming edge, redirect that edge to the
1609 appropriate target. Returns nonzero if a change was made.
1611 This function is now mis-named, because we also handle indirect jumps. */
1614 bypass_conditional_jumps (void)
1622 /* Note we start at block 1. */
1623 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
1626 bypass_last_basic_block
= last_basic_block
;
1627 mark_dfs_back_edges ();
1630 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
->next_bb
,
1631 EXIT_BLOCK_PTR
, next_bb
)
1633 /* Check for more than one predecessor. */
1634 if (!single_pred_p (bb
))
1637 FOR_BB_INSNS (bb
, insn
)
1638 if (DEBUG_INSN_P (insn
))
1640 else if (NONJUMP_INSN_P (insn
))
1644 if (GET_CODE (PATTERN (insn
)) != SET
)
1647 dest
= SET_DEST (PATTERN (insn
));
1648 if (REG_P (dest
) || CC0_P (dest
))
1653 else if (JUMP_P (insn
))
1655 if ((any_condjump_p (insn
) || computed_jump_p (insn
))
1656 && onlyjump_p (insn
))
1657 changed
|= bypass_block (bb
, setcc
, insn
);
1660 else if (INSN_P (insn
))
1665 /* If we bypassed any register setting insns, we inserted a
1666 copy on the redirected edge. These need to be committed. */
1668 commit_edge_insertions ();
1673 /* Return true if the graph is too expensive to optimize. PASS is the
1674 optimization about to be performed. */
1677 is_too_expensive (const char *pass
)
1679 /* Trying to perform global optimizations on flow graphs which have
1680 a high connectivity will take a long time and is unlikely to be
1681 particularly useful.
1683 In normal circumstances a cfg should have about twice as many
1684 edges as blocks. But we do not want to punish small functions
1685 which have a couple switch statements. Rather than simply
1686 threshold the number of blocks, uses something with a more
1687 graceful degradation. */
1688 if (n_edges
> 20000 + n_basic_blocks
* 4)
1690 warning (OPT_Wdisabled_optimization
,
1691 "%s: %d basic blocks and %d edges/basic block",
1692 pass
, n_basic_blocks
, n_edges
/ n_basic_blocks
);
1697 /* If allocating memory for the cprop bitmap would take up too much
1698 storage it's better just to disable the optimization. */
1700 * SBITMAP_SET_SIZE (max_reg_num ())
1701 * sizeof (SBITMAP_ELT_TYPE
)) > MAX_GCSE_MEMORY
)
1703 warning (OPT_Wdisabled_optimization
,
1704 "%s: %d basic blocks and %d registers",
1705 pass
, n_basic_blocks
, max_reg_num ());
1714 /* Main function for the CPROP pass. */
1717 one_cprop_pass (void)
1721 /* Return if there's nothing to do, or it is too expensive. */
1722 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1
1723 || is_too_expensive (_ ("const/copy propagation disabled")))
1726 global_const_prop_count
= local_const_prop_count
= 0;
1727 global_copy_prop_count
= local_copy_prop_count
= 0;
1730 gcc_obstack_init (&cprop_obstack
);
1732 /* Do a local const/copy propagation pass first. The global pass
1733 only handles global opportunities.
1734 If the local pass changes something, remove any unreachable blocks
1735 because the CPROP global dataflow analysis may get into infinite
1736 loops for CFGs with unreachable blocks.
1738 FIXME: This local pass should not be necessary after CSE (but for
1739 some reason it still is). It is also (proven) not necessary
1740 to run the local pass right after FWPWOP.
1742 FIXME: The global analysis would not get into infinite loops if it
1743 would use the DF solver (via df_simple_dataflow) instead of
1744 the solver implemented in this file. */
1745 changed
|= local_cprop_pass ();
1747 delete_unreachable_blocks ();
1749 /* Determine implicit sets. This may change the CFG (split critical
1750 edges if that exposes an implicit set).
1751 Note that find_implicit_sets() does not rely on up-to-date DF caches
1752 so that we do not have to re-run df_analyze() even if local CPROP
1754 ??? This could run earlier so that any uncovered implicit sets
1755 sets could be exploited in local_cprop_pass() also. Later. */
1756 changed
|= find_implicit_sets ();
1758 /* If local_cprop_pass() or find_implicit_sets() changed something,
1759 run df_analyze() to bring all insn caches up-to-date, and to take
1760 new basic blocks from edge splitting on the DF radar.
1761 NB: This also runs the fast DCE pass, because execute_rtl_cprop
1762 sets DF_LR_RUN_DCE. */
1766 alloc_hash_table (&set_hash_table
);
1767 compute_hash_table (&set_hash_table
);
1769 /* Free implicit_sets before peak usage. */
1770 free (implicit_sets
);
1771 implicit_sets
= NULL
;
1774 dump_hash_table (dump_file
, "SET", &set_hash_table
);
1775 if (set_hash_table
.n_elems
> 0)
1780 alloc_cprop_mem (last_basic_block
, set_hash_table
.n_elems
);
1781 compute_cprop_data ();
1783 /* Allocate vars to track sets of regs. */
1784 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
1786 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
->next_bb
, EXIT_BLOCK_PTR
, next_bb
)
1788 /* Reset tables used to keep track of what's still valid [since
1789 the start of the block]. */
1790 reset_opr_set_tables ();
1792 FOR_BB_INSNS (bb
, insn
)
1795 changed
|= cprop_insn (insn
);
1797 /* Keep track of everything modified by this insn. */
1798 /* ??? Need to be careful w.r.t. mods done to INSN.
1799 Don't call mark_oprs_set if we turned the
1800 insn into a NOTE. */
1801 if (! NOTE_P (insn
))
1802 mark_oprs_set (insn
);
1806 changed
|= bypass_conditional_jumps ();
1808 FREE_REG_SET (reg_set_bitmap
);
1812 free_hash_table (&set_hash_table
);
1813 obstack_free (&cprop_obstack
, NULL
);
1817 fprintf (dump_file
, "CPROP of %s, %d basic blocks, %d bytes needed, ",
1818 current_function_name (), n_basic_blocks
, bytes_used
);
1819 fprintf (dump_file
, "%d local const props, %d local copy props, ",
1820 local_const_prop_count
, local_copy_prop_count
);
1821 fprintf (dump_file
, "%d global const props, %d global copy props\n\n",
1822 global_const_prop_count
, global_copy_prop_count
);
1829 /* All the passes implemented in this file. Each pass has its
1830 own gate and execute function, and at the end of the file a
1831 pass definition for passes.c.
1833 We do not construct an accurate cfg in functions which call
1834 setjmp, so none of these passes runs if the function calls
1836 FIXME: Should just handle setjmp via REG_SETJMP notes. */
1839 gate_rtl_cprop (void)
1841 return optimize
> 0 && flag_gcse
1842 && !cfun
->calls_setjmp
1847 execute_rtl_cprop (void)
1850 delete_unreachable_blocks ();
1851 df_set_flags (DF_LR_RUN_DCE
);
1853 changed
= one_cprop_pass ();
1854 flag_rerun_cse_after_global_opts
|= changed
;
1860 struct rtl_opt_pass pass_rtl_cprop
=
1865 gate_rtl_cprop
, /* gate */
1866 execute_rtl_cprop
, /* execute */
1869 0, /* static_pass_number */
1870 TV_CPROP
, /* tv_id */
1871 PROP_cfglayout
, /* properties_required */
1872 0, /* properties_provided */
1873 0, /* properties_destroyed */
1874 0, /* todo_flags_start */
1875 TODO_df_finish
| TODO_verify_rtl_sharing
|
1877 TODO_verify_flow
| TODO_ggc_collect
/* todo_flags_finish */