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"
54 /* An obstack for our working variables. */
55 static struct obstack cprop_obstack
;
57 /* Occurrence of an expression.
58 There is one per basic block. If a pattern appears more than once the
59 last appearance is used. */
63 /* Next occurrence of this expression. */
65 /* The insn that computes the expression. */
69 typedef struct occr
*occr_t
;
71 DEF_VEC_ALLOC_P (occr_t
, heap
);
73 /* Hash table entry for assignment expressions. */
77 /* The expression (DEST := SRC). */
81 /* Index in the available expression bitmaps. */
83 /* Next entry with the same hash. */
84 struct expr
*next_same_hash
;
85 /* List of available occurrence in basic blocks in the function.
86 An "available occurrence" is one that is the last occurrence in the
87 basic block and whose operands are not modified by following statements
88 in the basic block [including this insn]. */
89 struct occr
*avail_occr
;
92 /* Hash table for copy propagation expressions.
93 Each hash table is an array of buckets.
94 ??? It is known that if it were an array of entries, structure elements
95 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
96 not clear whether in the final analysis a sufficient amount of memory would
97 be saved as the size of the available expression bitmaps would be larger
98 [one could build a mapping table without holes afterwards though].
99 Someday I'll perform the computation and figure it out. */
104 This is an array of `set_hash_table_size' elements. */
107 /* Size of the hash table, in elements. */
110 /* Number of hash table elements. */
111 unsigned int n_elems
;
114 /* Copy propagation hash table. */
115 static struct hash_table_d set_hash_table
;
117 /* Array of implicit set patterns indexed by basic block index. */
118 static rtx
*implicit_sets
;
120 /* Array of indexes of expressions for implicit set patterns indexed by basic
121 block index. In other words, implicit_set_indexes[i] is the bitmap_index
122 of the expression whose RTX is implicit_sets[i]. */
123 static int *implicit_set_indexes
;
125 /* Bitmap containing one bit for each register in the program.
126 Used when performing GCSE to track which registers have been set since
127 the start or end of the basic block while traversing that block. */
128 static regset reg_set_bitmap
;
130 /* Various variables for statistics gathering. */
132 /* Memory used in a pass.
133 This isn't intended to be absolutely precise. Its intent is only
134 to keep an eye on memory usage. */
135 static int bytes_used
;
137 /* Number of local constants propagated. */
138 static int local_const_prop_count
;
139 /* Number of local copies propagated. */
140 static int local_copy_prop_count
;
141 /* Number of global constants propagated. */
142 static int global_const_prop_count
;
143 /* Number of global copies propagated. */
144 static int global_copy_prop_count
;
146 #define GOBNEW(T) ((T *) cprop_alloc (sizeof (T)))
147 #define GOBNEWVAR(T, S) ((T *) cprop_alloc ((S)))
149 /* Cover function to obstack_alloc. */
152 cprop_alloc (unsigned long size
)
155 return obstack_alloc (&cprop_obstack
, size
);
158 /* Return nonzero if register X is unchanged from INSN to the end
159 of INSN's basic block. */
162 reg_available_p (const_rtx x
, const_rtx insn ATTRIBUTE_UNUSED
)
164 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
167 /* Hash a set of register REGNO.
169 Sets are hashed on the register that is set. This simplifies the PRE copy
172 ??? May need to make things more elaborate. Later, as necessary. */
175 hash_set (int regno
, int hash_table_size
)
180 return hash
% hash_table_size
;
183 /* Insert assignment DEST:=SET from INSN in the hash table.
184 DEST is a register and SET is a register or a suitable constant.
185 If the assignment is already present in the table, record it as
186 the last occurrence in INSN's basic block.
187 IMPLICIT is true if it's an implicit set, false otherwise. */
190 insert_set_in_table (rtx dest
, rtx src
, rtx insn
, struct hash_table_d
*table
,
195 struct expr
*cur_expr
, *last_expr
= NULL
;
196 struct occr
*cur_occr
;
198 hash
= hash_set (REGNO (dest
), table
->size
);
200 for (cur_expr
= table
->table
[hash
]; cur_expr
;
201 cur_expr
= cur_expr
->next_same_hash
)
203 if (dest
== cur_expr
->dest
204 && src
== cur_expr
->src
)
209 last_expr
= cur_expr
;
214 cur_expr
= GOBNEW (struct expr
);
215 bytes_used
+= sizeof (struct expr
);
216 if (table
->table
[hash
] == NULL
)
217 /* This is the first pattern that hashed to this index. */
218 table
->table
[hash
] = cur_expr
;
220 /* Add EXPR to end of this hash chain. */
221 last_expr
->next_same_hash
= cur_expr
;
223 /* Set the fields of the expr element.
224 We must copy X because it can be modified when copy propagation is
225 performed on its operands. */
226 cur_expr
->dest
= copy_rtx (dest
);
227 cur_expr
->src
= copy_rtx (src
);
228 cur_expr
->bitmap_index
= table
->n_elems
++;
229 cur_expr
->next_same_hash
= NULL
;
230 cur_expr
->avail_occr
= NULL
;
233 /* Now record the occurrence. */
234 cur_occr
= cur_expr
->avail_occr
;
237 && BLOCK_FOR_INSN (cur_occr
->insn
) == BLOCK_FOR_INSN (insn
))
239 /* Found another instance of the expression in the same basic block.
240 Prefer this occurrence to the currently recorded one. We want
241 the last one in the block and the block is scanned from start
243 cur_occr
->insn
= insn
;
247 /* First occurrence of this expression in this basic block. */
248 cur_occr
= GOBNEW (struct occr
);
249 bytes_used
+= sizeof (struct occr
);
250 cur_occr
->insn
= insn
;
251 cur_occr
->next
= cur_expr
->avail_occr
;
252 cur_expr
->avail_occr
= cur_occr
;
255 /* Record bitmap_index of the implicit set in implicit_set_indexes. */
257 implicit_set_indexes
[BLOCK_FOR_INSN(insn
)->index
] = cur_expr
->bitmap_index
;
260 /* Determine whether the rtx X should be treated as a constant for CPROP.
261 Since X might be inserted more than once we have to take care that it
265 cprop_constant_p (const_rtx x
)
267 return CONSTANT_P (x
) && (GET_CODE (x
) != CONST
|| shared_const_p (x
));
270 /* Scan SET present in INSN and add an entry to the hash TABLE.
271 IMPLICIT is true if it's an implicit set, false otherwise. */
274 hash_scan_set (rtx set
, rtx insn
, struct hash_table_d
*table
, bool implicit
)
276 rtx src
= SET_SRC (set
);
277 rtx dest
= SET_DEST (set
);
280 && ! HARD_REGISTER_P (dest
)
281 && reg_available_p (dest
, insn
)
282 && can_copy_p (GET_MODE (dest
)))
284 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
286 This allows us to do a single CPROP pass and still eliminate
287 redundant constants, addresses or other expressions that are
288 constructed with multiple instructions.
290 However, keep the original SRC if INSN is a simple reg-reg move. In
291 In this case, there will almost always be a REG_EQUAL note on the
292 insn that sets SRC. By recording the REG_EQUAL value here as SRC
293 for INSN, we miss copy propagation opportunities.
295 Note that this does not impede profitable constant propagations. We
296 "look through" reg-reg sets in lookup_set. */
297 rtx note
= find_reg_equal_equiv_note (insn
);
299 && REG_NOTE_KIND (note
) == REG_EQUAL
301 && cprop_constant_p (XEXP (note
, 0)))
302 src
= XEXP (note
, 0), set
= gen_rtx_SET (VOIDmode
, dest
, src
);
304 /* Record sets for constant/copy propagation. */
307 && ! HARD_REGISTER_P (src
)
308 && reg_available_p (src
, insn
))
309 || cprop_constant_p (src
))
310 insert_set_in_table (dest
, src
, insn
, table
, implicit
);
314 /* Process INSN and add hash table entries as appropriate. */
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
, false);
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
, false);
337 /* Dump the hash table TABLE to file FILE under the name NAME. */
340 dump_hash_table (FILE *file
, const char *name
, struct hash_table_d
*table
)
343 /* Flattened out table, so it's printed in proper order. */
344 struct expr
**flat_table
;
345 unsigned int *hash_val
;
348 flat_table
= XCNEWVEC (struct expr
*, table
->n_elems
);
349 hash_val
= XNEWVEC (unsigned int, table
->n_elems
);
351 for (i
= 0; i
< (int) table
->size
; i
++)
352 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
354 flat_table
[expr
->bitmap_index
] = expr
;
355 hash_val
[expr
->bitmap_index
] = i
;
358 fprintf (file
, "%s hash table (%d buckets, %d entries)\n",
359 name
, table
->size
, table
->n_elems
);
361 for (i
= 0; i
< (int) table
->n_elems
; i
++)
362 if (flat_table
[i
] != 0)
364 expr
= flat_table
[i
];
365 fprintf (file
, "Index %d (hash value %d)\n ",
366 expr
->bitmap_index
, hash_val
[i
]);
367 print_rtl (file
, expr
->dest
);
368 fprintf (file
, " := ");
369 print_rtl (file
, expr
->src
);
370 fprintf (file
, "\n");
373 fprintf (file
, "\n");
379 /* Record as unavailable all registers that are DEF operands of INSN. */
382 make_set_regs_unavailable (rtx insn
)
384 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
387 for (def_rec
= DF_INSN_INFO_DEFS (insn_info
); *def_rec
; def_rec
++)
388 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (*def_rec
));
391 /* Top level function to create an assignment hash table.
393 Assignment entries are placed in the hash table if
394 - they are of the form (set (pseudo-reg) src),
395 - src is something we want to perform const/copy propagation on,
396 - none of the operands or target are subsequently modified in the block
398 Currently src must be a pseudo-reg or a const_int.
400 TABLE is the table computed. */
403 compute_hash_table_work (struct hash_table_d
*table
)
407 /* Allocate vars to track sets of regs. */
408 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
414 /* Reset tables used to keep track of what's not yet invalid [since
415 the end of the block]. */
416 CLEAR_REG_SET (reg_set_bitmap
);
418 /* Go over all insns from the last to the first. This is convenient
419 for tracking available registers, i.e. not set between INSN and
420 the end of the basic block BB. */
421 FOR_BB_INSNS_REVERSE (bb
, insn
)
423 /* Only real insns are interesting. */
424 if (!NONDEBUG_INSN_P (insn
))
427 /* Record interesting sets from INSN in the hash table. */
428 hash_scan_insn (insn
, table
);
430 /* Any registers set in INSN will make SETs above it not AVAIL. */
431 make_set_regs_unavailable (insn
);
434 /* Insert implicit sets in the hash table, pretending they appear as
435 insns at the head of the basic block. */
436 if (implicit_sets
[bb
->index
] != NULL_RTX
)
437 hash_scan_set (implicit_sets
[bb
->index
], BB_HEAD (bb
), table
, true);
440 FREE_REG_SET (reg_set_bitmap
);
443 /* Allocate space for the set/expr hash TABLE.
444 It is used to determine the number of buckets to use. */
447 alloc_hash_table (struct hash_table_d
*table
)
451 n
= get_max_insn_count ();
454 if (table
->size
< 11)
457 /* Attempt to maintain efficient use of hash table.
458 Making it an odd number is simplest for now.
459 ??? Later take some measurements. */
461 n
= table
->size
* sizeof (struct expr
*);
462 table
->table
= XNEWVAR (struct expr
*, n
);
465 /* Free things allocated by alloc_hash_table. */
468 free_hash_table (struct hash_table_d
*table
)
473 /* Compute the hash TABLE for doing copy/const propagation or
474 expression hash table. */
477 compute_hash_table (struct hash_table_d
*table
)
479 /* Initialize count of number of entries in hash table. */
481 memset (table
->table
, 0, table
->size
* sizeof (struct expr
*));
483 compute_hash_table_work (table
);
486 /* Expression tracking support. */
488 /* Lookup REGNO in the set TABLE. The result is a pointer to the
489 table entry, or NULL if not found. */
492 lookup_set (unsigned int regno
, struct hash_table_d
*table
)
494 unsigned int hash
= hash_set (regno
, table
->size
);
497 expr
= table
->table
[hash
];
499 while (expr
&& REGNO (expr
->dest
) != regno
)
500 expr
= expr
->next_same_hash
;
505 /* Return the next entry for REGNO in list EXPR. */
508 next_set (unsigned int regno
, struct expr
*expr
)
511 expr
= expr
->next_same_hash
;
512 while (expr
&& REGNO (expr
->dest
) != regno
);
517 /* Reset tables used to keep track of what's still available [since the
518 start of the block]. */
521 reset_opr_set_tables (void)
523 /* Maintain a bitmap of which regs have been set since beginning of
525 CLEAR_REG_SET (reg_set_bitmap
);
528 /* Return nonzero if the register X has not been set yet [since the
529 start of the basic block containing INSN]. */
532 reg_not_set_p (const_rtx x
, const_rtx insn ATTRIBUTE_UNUSED
)
534 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
537 /* Record things set by INSN.
538 This data is used by reg_not_set_p. */
541 mark_oprs_set (rtx insn
)
543 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
546 for (def_rec
= DF_INSN_INFO_DEFS (insn_info
); *def_rec
; def_rec
++)
547 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (*def_rec
));
550 /* Compute copy/constant propagation working variables. */
552 /* Local properties of assignments. */
553 static sbitmap
*cprop_avloc
;
554 static sbitmap
*cprop_kill
;
556 /* Global properties of assignments (computed from the local properties). */
557 static sbitmap
*cprop_avin
;
558 static sbitmap
*cprop_avout
;
560 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
561 basic blocks. N_SETS is the number of sets. */
564 alloc_cprop_mem (int n_blocks
, int n_sets
)
566 cprop_avloc
= sbitmap_vector_alloc (n_blocks
, n_sets
);
567 cprop_kill
= sbitmap_vector_alloc (n_blocks
, n_sets
);
569 cprop_avin
= sbitmap_vector_alloc (n_blocks
, n_sets
);
570 cprop_avout
= sbitmap_vector_alloc (n_blocks
, n_sets
);
573 /* Free vars used by copy/const propagation. */
576 free_cprop_mem (void)
578 sbitmap_vector_free (cprop_avloc
);
579 sbitmap_vector_free (cprop_kill
);
580 sbitmap_vector_free (cprop_avin
);
581 sbitmap_vector_free (cprop_avout
);
584 /* Compute the local properties of each recorded expression.
586 Local properties are those that are defined by the block, irrespective of
589 An expression is killed in a block if its operands, either DEST or SRC, are
590 modified in the block.
592 An expression is computed (locally available) in a block if it is computed
593 at least once and expression would contain the same value if the
594 computation was moved to the end of the block.
596 KILL and COMP are destination sbitmaps for recording local properties. */
599 compute_local_properties (sbitmap
*kill
, sbitmap
*comp
,
600 struct hash_table_d
*table
)
604 /* Initialize the bitmaps that were passed in. */
605 sbitmap_vector_zero (kill
, last_basic_block
);
606 sbitmap_vector_zero (comp
, last_basic_block
);
608 for (i
= 0; i
< table
->size
; i
++)
612 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
614 int indx
= expr
->bitmap_index
;
618 /* For each definition of the destination pseudo-reg, the expression
619 is killed in the block where the definition is. */
620 for (def
= DF_REG_DEF_CHAIN (REGNO (expr
->dest
));
621 def
; def
= DF_REF_NEXT_REG (def
))
622 SET_BIT (kill
[DF_REF_BB (def
)->index
], indx
);
624 /* If the source is a pseudo-reg, for each definition of the source,
625 the expression is killed in the block where the definition is. */
626 if (REG_P (expr
->src
))
627 for (def
= DF_REG_DEF_CHAIN (REGNO (expr
->src
));
628 def
; def
= DF_REF_NEXT_REG (def
))
629 SET_BIT (kill
[DF_REF_BB (def
)->index
], indx
);
631 /* The occurrences recorded in avail_occr are exactly those that
632 are locally available in the block where they are. */
633 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
635 SET_BIT (comp
[BLOCK_FOR_INSN (occr
->insn
)->index
], indx
);
641 /* Hash table support. */
643 /* Top level routine to do the dataflow analysis needed by copy/const
647 compute_cprop_data (void)
651 compute_local_properties (cprop_kill
, cprop_avloc
, &set_hash_table
);
652 compute_available (cprop_avloc
, cprop_kill
, cprop_avout
, cprop_avin
);
654 /* Merge implicit sets into CPROP_AVIN. They are always available at the
655 entry of their basic block. We need to do this because 1) implicit sets
656 aren't recorded for the local pass so they cannot be propagated within
657 their basic block by this pass and 2) the global pass would otherwise
658 propagate them only in the successors of their basic block. */
661 int index
= implicit_set_indexes
[bb
->index
];
663 SET_BIT (cprop_avin
[bb
->index
], index
);
667 /* Copy/constant propagation. */
669 /* Maximum number of register uses in an insn that we handle. */
672 /* Table of uses (registers, both hard and pseudo) found in an insn.
673 Allocated statically to avoid alloc/free complexity and overhead. */
674 static rtx reg_use_table
[MAX_USES
];
676 /* Index into `reg_use_table' while building it. */
677 static unsigned reg_use_count
;
679 /* Set up a list of register numbers used in INSN. The found uses are stored
680 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
681 and contains the number of uses in the table upon exit.
683 ??? If a register appears multiple times we will record it multiple times.
684 This doesn't hurt anything but it will slow things down. */
687 find_used_regs (rtx
*xptr
, void *data ATTRIBUTE_UNUSED
)
694 /* repeat is used to turn tail-recursion into iteration since GCC
695 can't do it when there's no return value. */
703 if (reg_use_count
== MAX_USES
)
706 reg_use_table
[reg_use_count
] = x
;
710 /* Recursively scan the operands of this expression. */
712 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
716 /* If we are about to do the last recursive call
717 needed at this level, change it into iteration.
718 This function is called enough to be worth it. */
725 find_used_regs (&XEXP (x
, i
), data
);
727 else if (fmt
[i
] == 'E')
728 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
729 find_used_regs (&XVECEXP (x
, i
, j
), data
);
733 /* Try to replace all uses of FROM in INSN with TO.
734 Return nonzero if successful. */
737 try_replace_reg (rtx from
, rtx to
, rtx insn
)
739 rtx note
= find_reg_equal_equiv_note (insn
);
742 rtx set
= single_set (insn
);
744 /* Usually we substitute easy stuff, so we won't copy everything.
745 We however need to take care to not duplicate non-trivial CONST
749 validate_replace_src_group (from
, to
, insn
);
750 if (num_changes_pending () && apply_change_group ())
753 /* Try to simplify SET_SRC if we have substituted a constant. */
754 if (success
&& set
&& CONSTANT_P (to
))
756 src
= simplify_rtx (SET_SRC (set
));
759 validate_change (insn
, &SET_SRC (set
), src
, 0);
762 /* If there is already a REG_EQUAL note, update the expression in it
763 with our replacement. */
764 if (note
!= 0 && REG_NOTE_KIND (note
) == REG_EQUAL
)
765 set_unique_reg_note (insn
, REG_EQUAL
,
766 simplify_replace_rtx (XEXP (note
, 0), from
, to
));
767 if (!success
&& set
&& reg_mentioned_p (from
, SET_SRC (set
)))
769 /* If above failed and this is a single set, try to simplify the source
770 of the set given our substitution. We could perhaps try this for
771 multiple SETs, but it probably won't buy us anything. */
772 src
= simplify_replace_rtx (SET_SRC (set
), from
, to
);
774 if (!rtx_equal_p (src
, SET_SRC (set
))
775 && validate_change (insn
, &SET_SRC (set
), src
, 0))
778 /* If we've failed perform the replacement, have a single SET to
779 a REG destination and don't yet have a note, add a REG_EQUAL note
780 to not lose information. */
781 if (!success
&& note
== 0 && set
!= 0 && REG_P (SET_DEST (set
)))
782 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
785 if (set
&& MEM_P (SET_DEST (set
)) && reg_mentioned_p (from
, SET_DEST (set
)))
787 /* Registers can also appear as uses in SET_DEST if it is a MEM.
788 We could perhaps try this for multiple SETs, but it probably
789 won't buy us anything. */
790 rtx dest
= simplify_replace_rtx (SET_DEST (set
), from
, to
);
792 if (!rtx_equal_p (dest
, SET_DEST (set
))
793 && validate_change (insn
, &SET_DEST (set
), dest
, 0))
797 /* REG_EQUAL may get simplified into register.
798 We don't allow that. Remove that note. This code ought
799 not to happen, because previous code ought to synthesize
800 reg-reg move, but be on the safe side. */
801 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
&& REG_P (XEXP (note
, 0)))
802 remove_note (insn
, note
);
807 /* Find a set of REGNOs that are available on entry to INSN's block. Return
808 NULL no such set is found. */
811 find_avail_set (int regno
, rtx insn
)
813 /* SET1 contains the last set found that can be returned to the caller for
814 use in a substitution. */
815 struct expr
*set1
= 0;
817 /* Loops are not possible here. To get a loop we would need two sets
818 available at the start of the block containing INSN. i.e. we would
819 need two sets like this available at the start of the block:
821 (set (reg X) (reg Y))
822 (set (reg Y) (reg X))
824 This can not happen since the set of (reg Y) would have killed the
825 set of (reg X) making it unavailable at the start of this block. */
829 struct expr
*set
= lookup_set (regno
, &set_hash_table
);
831 /* Find a set that is available at the start of the block
832 which contains INSN. */
835 if (TEST_BIT (cprop_avin
[BLOCK_FOR_INSN (insn
)->index
],
838 set
= next_set (regno
, set
);
841 /* If no available set was found we've reached the end of the
842 (possibly empty) copy chain. */
848 /* We know the set is available.
849 Now check that SRC is locally anticipatable (i.e. none of the
850 source operands have changed since the start of the block).
852 If the source operand changed, we may still use it for the next
853 iteration of this loop, but we may not use it for substitutions. */
855 if (cprop_constant_p (src
) || reg_not_set_p (src
, insn
))
858 /* If the source of the set is anything except a register, then
859 we have reached the end of the copy chain. */
863 /* Follow the copy chain, i.e. start another iteration of the loop
864 and see if we have an available copy into SRC. */
868 /* SET1 holds the last set that was available and anticipatable at
873 /* Subroutine of cprop_insn that tries to propagate constants into
874 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
875 it is the instruction that immediately precedes JUMP, and must be a
876 single SET of a register. FROM is what we will try to replace,
877 SRC is the constant we will try to substitute for it. Return nonzero
878 if a change was made. */
881 cprop_jump (basic_block bb
, rtx setcc
, rtx jump
, rtx from
, rtx src
)
883 rtx new_rtx
, set_src
, note_src
;
884 rtx set
= pc_set (jump
);
885 rtx note
= find_reg_equal_equiv_note (jump
);
889 note_src
= XEXP (note
, 0);
890 if (GET_CODE (note_src
) == EXPR_LIST
)
893 else note_src
= NULL_RTX
;
895 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
896 set_src
= note_src
? note_src
: SET_SRC (set
);
898 /* First substitute the SETCC condition into the JUMP instruction,
899 then substitute that given values into this expanded JUMP. */
900 if (setcc
!= NULL_RTX
901 && !modified_between_p (from
, setcc
, jump
)
902 && !modified_between_p (src
, setcc
, jump
))
905 rtx setcc_set
= single_set (setcc
);
906 rtx setcc_note
= find_reg_equal_equiv_note (setcc
);
907 setcc_src
= (setcc_note
&& GET_CODE (XEXP (setcc_note
, 0)) != EXPR_LIST
)
908 ? XEXP (setcc_note
, 0) : SET_SRC (setcc_set
);
909 set_src
= simplify_replace_rtx (set_src
, SET_DEST (setcc_set
),
915 new_rtx
= simplify_replace_rtx (set_src
, from
, src
);
917 /* If no simplification can be made, then try the next register. */
918 if (rtx_equal_p (new_rtx
, SET_SRC (set
)))
921 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
922 if (new_rtx
== pc_rtx
)
926 /* Ensure the value computed inside the jump insn to be equivalent
927 to one computed by setcc. */
928 if (setcc
&& modified_in_p (new_rtx
, setcc
))
930 if (! validate_unshare_change (jump
, &SET_SRC (set
), new_rtx
, 0))
932 /* When (some) constants are not valid in a comparison, and there
933 are two registers to be replaced by constants before the entire
934 comparison can be folded into a constant, we need to keep
935 intermediate information in REG_EQUAL notes. For targets with
936 separate compare insns, such notes are added by try_replace_reg.
937 When we have a combined compare-and-branch instruction, however,
938 we need to attach a note to the branch itself to make this
939 optimization work. */
941 if (!rtx_equal_p (new_rtx
, note_src
))
942 set_unique_reg_note (jump
, REG_EQUAL
, copy_rtx (new_rtx
));
946 /* Remove REG_EQUAL note after simplification. */
948 remove_note (jump
, note
);
952 /* Delete the cc0 setter. */
953 if (setcc
!= NULL
&& CC0_P (SET_DEST (single_set (setcc
))))
957 global_const_prop_count
++;
958 if (dump_file
!= NULL
)
961 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with"
962 "constant ", REGNO (from
), INSN_UID (jump
));
963 print_rtl (dump_file
, src
);
964 fprintf (dump_file
, "\n");
966 purge_dead_edges (bb
);
968 /* If a conditional jump has been changed into unconditional jump, remove
969 the jump and make the edge fallthru - this is always called in
971 if (new_rtx
!= pc_rtx
&& simplejump_p (jump
))
976 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
977 if (e
->dest
!= EXIT_BLOCK_PTR
978 && BB_HEAD (e
->dest
) == JUMP_LABEL (jump
))
980 e
->flags
|= EDGE_FALLTHRU
;
989 /* Subroutine of cprop_insn that tries to propagate constants. FROM is what
990 we will try to replace, SRC is the constant we will try to substitute for
991 it and INSN is the instruction where this will be happening. */
994 constprop_register (rtx from
, rtx src
, rtx insn
)
998 /* Check for reg or cc0 setting instructions followed by
999 conditional branch instructions first. */
1000 if ((sset
= single_set (insn
)) != NULL
1002 && any_condjump_p (NEXT_INSN (insn
)) && onlyjump_p (NEXT_INSN (insn
)))
1004 rtx dest
= SET_DEST (sset
);
1005 if ((REG_P (dest
) || CC0_P (dest
))
1006 && cprop_jump (BLOCK_FOR_INSN (insn
), insn
, NEXT_INSN (insn
),
1011 /* Handle normal insns next. */
1012 if (NONJUMP_INSN_P (insn
) && try_replace_reg (from
, src
, insn
))
1015 /* Try to propagate a CONST_INT into a conditional jump.
1016 We're pretty specific about what we will handle in this
1017 code, we can extend this as necessary over time.
1019 Right now the insn in question must look like
1020 (set (pc) (if_then_else ...)) */
1021 else if (any_condjump_p (insn
) && onlyjump_p (insn
))
1022 return cprop_jump (BLOCK_FOR_INSN (insn
), NULL
, insn
, from
, src
);
1026 /* Perform constant and copy propagation on INSN.
1027 Return nonzero if a change was made. */
1030 cprop_insn (rtx insn
)
1033 int changed
= 0, changed_this_round
;
1037 changed_this_round
= 0;
1039 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1041 /* We may win even when propagating constants into notes. */
1042 note
= find_reg_equal_equiv_note (insn
);
1044 find_used_regs (&XEXP (note
, 0), NULL
);
1046 for (i
= 0; i
< reg_use_count
; i
++)
1048 rtx reg_used
= reg_use_table
[i
];
1049 unsigned int regno
= REGNO (reg_used
);
1053 /* If the register has already been set in this block, there's
1054 nothing we can do. */
1055 if (! reg_not_set_p (reg_used
, insn
))
1058 /* Find an assignment that sets reg_used and is available
1059 at the start of the block. */
1060 set
= find_avail_set (regno
, insn
);
1066 /* Constant propagation. */
1067 if (cprop_constant_p (src
))
1069 if (constprop_register (reg_used
, src
, insn
))
1071 changed_this_round
= changed
= 1;
1072 global_const_prop_count
++;
1073 if (dump_file
!= NULL
)
1076 "GLOBAL CONST-PROP: Replacing reg %d in ", regno
);
1077 fprintf (dump_file
, "insn %d with constant ",
1079 print_rtl (dump_file
, src
);
1080 fprintf (dump_file
, "\n");
1082 if (INSN_DELETED_P (insn
))
1086 else if (REG_P (src
)
1087 && REGNO (src
) >= FIRST_PSEUDO_REGISTER
1088 && REGNO (src
) != regno
)
1090 if (try_replace_reg (reg_used
, src
, insn
))
1092 changed_this_round
= changed
= 1;
1093 global_copy_prop_count
++;
1094 if (dump_file
!= NULL
)
1097 "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1098 regno
, INSN_UID (insn
));
1099 fprintf (dump_file
, " with reg %d\n", REGNO (src
));
1102 /* The original insn setting reg_used may or may not now be
1103 deletable. We leave the deletion to DCE. */
1104 /* FIXME: If it turns out that the insn isn't deletable,
1105 then we may have unnecessarily extended register lifetimes
1106 and made things worse. */
1110 /* If try_replace_reg simplified the insn, the regs found
1111 by find_used_regs may not be valid anymore. Start over. */
1112 if (changed_this_round
)
1116 if (changed
&& DEBUG_INSN_P (insn
))
1122 /* Like find_used_regs, but avoid recording uses that appear in
1123 input-output contexts such as zero_extract or pre_dec. This
1124 restricts the cases we consider to those for which local cprop
1125 can legitimately make replacements. */
1128 local_cprop_find_used_regs (rtx
*xptr
, void *data
)
1135 switch (GET_CODE (x
))
1139 case STRICT_LOW_PART
:
1148 /* Can only legitimately appear this early in the context of
1149 stack pushes for function arguments, but handle all of the
1150 codes nonetheless. */
1154 /* Setting a subreg of a register larger than word_mode leaves
1155 the non-written words unchanged. */
1156 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x
))) > BITS_PER_WORD
)
1164 find_used_regs (xptr
, data
);
1167 /* Try to perform local const/copy propagation on X in INSN. */
1170 do_local_cprop (rtx x
, rtx insn
)
1172 rtx newreg
= NULL
, newcnst
= NULL
;
1174 /* Rule out USE instructions and ASM statements as we don't want to
1175 change the hard registers mentioned. */
1177 && (REGNO (x
) >= FIRST_PSEUDO_REGISTER
1178 || (GET_CODE (PATTERN (insn
)) != USE
1179 && asm_noperands (PATTERN (insn
)) < 0)))
1181 cselib_val
*val
= cselib_lookup (x
, GET_MODE (x
), 0, VOIDmode
);
1182 struct elt_loc_list
*l
;
1186 for (l
= val
->locs
; l
; l
= l
->next
)
1188 rtx this_rtx
= l
->loc
;
1191 if (cprop_constant_p (this_rtx
))
1193 if (REG_P (this_rtx
) && REGNO (this_rtx
) >= FIRST_PSEUDO_REGISTER
1194 /* Don't copy propagate if it has attached REG_EQUIV note.
1195 At this point this only function parameters should have
1196 REG_EQUIV notes and if the argument slot is used somewhere
1197 explicitly, it means address of parameter has been taken,
1198 so we should not extend the lifetime of the pseudo. */
1199 && (!(note
= find_reg_note (l
->setting_insn
, REG_EQUIV
, NULL_RTX
))
1200 || ! MEM_P (XEXP (note
, 0))))
1203 if (newcnst
&& constprop_register (x
, newcnst
, insn
))
1205 if (dump_file
!= NULL
)
1207 fprintf (dump_file
, "LOCAL CONST-PROP: Replacing reg %d in ",
1209 fprintf (dump_file
, "insn %d with constant ",
1211 print_rtl (dump_file
, newcnst
);
1212 fprintf (dump_file
, "\n");
1214 local_const_prop_count
++;
1217 else if (newreg
&& newreg
!= x
&& try_replace_reg (x
, newreg
, insn
))
1219 if (dump_file
!= NULL
)
1222 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1223 REGNO (x
), INSN_UID (insn
));
1224 fprintf (dump_file
, " with reg %d\n", REGNO (newreg
));
1226 local_copy_prop_count
++;
1233 /* Do local const/copy propagation (i.e. within each basic block). */
1236 local_cprop_pass (void)
1240 bool changed
= false;
1246 FOR_BB_INSNS (bb
, insn
)
1250 rtx note
= find_reg_equal_equiv_note (insn
);
1254 note_uses (&PATTERN (insn
), local_cprop_find_used_regs
,
1257 local_cprop_find_used_regs (&XEXP (note
, 0), NULL
);
1259 for (i
= 0; i
< reg_use_count
; i
++)
1261 if (do_local_cprop (reg_use_table
[i
], insn
))
1263 if (!DEBUG_INSN_P (insn
))
1268 if (INSN_DELETED_P (insn
))
1271 while (i
< reg_use_count
);
1273 cselib_process_insn (insn
);
1276 /* Forget everything at the end of a basic block. */
1277 cselib_clear_table ();
1285 /* Similar to get_condition, only the resulting condition must be
1286 valid at JUMP, instead of at EARLIEST.
1288 This differs from noce_get_condition in ifcvt.c in that we prefer not to
1289 settle for the condition variable in the jump instruction being integral.
1290 We prefer to be able to record the value of a user variable, rather than
1291 the value of a temporary used in a condition. This could be solved by
1292 recording the value of *every* register scanned by canonicalize_condition,
1293 but this would require some code reorganization. */
1296 fis_get_condition (rtx jump
)
1298 return get_condition (jump
, NULL
, false, true);
1301 /* Check the comparison COND to see if we can safely form an implicit
1305 implicit_set_cond_p (const_rtx cond
)
1307 enum machine_mode mode
;
1310 /* COND must be either an EQ or NE comparison. */
1311 if (GET_CODE (cond
) != EQ
&& GET_CODE (cond
) != NE
)
1314 /* The first operand of COND must be a pseudo-reg. */
1315 if (! REG_P (XEXP (cond
, 0))
1316 || HARD_REGISTER_P (XEXP (cond
, 0)))
1319 /* The second operand of COND must be a suitable constant. */
1320 mode
= GET_MODE (XEXP (cond
, 0));
1321 cst
= XEXP (cond
, 1);
1323 /* We can't perform this optimization if either operand might be or might
1324 contain a signed zero. */
1325 if (HONOR_SIGNED_ZEROS (mode
))
1327 /* It is sufficient to check if CST is or contains a zero. We must
1328 handle float, complex, and vector. If any subpart is a zero, then
1329 the optimization can't be performed. */
1330 /* ??? The complex and vector checks are not implemented yet. We just
1331 always return zero for them. */
1332 if (GET_CODE (cst
) == CONST_DOUBLE
)
1335 REAL_VALUE_FROM_CONST_DOUBLE (d
, cst
);
1336 if (REAL_VALUES_EQUAL (d
, dconst0
))
1343 return cprop_constant_p (cst
);
1346 /* Find the implicit sets of a function. An "implicit set" is a constraint
1347 on the value of a variable, implied by a conditional jump. For example,
1348 following "if (x == 2)", the then branch may be optimized as though the
1349 conditional performed an "explicit set", in this example, "x = 2". This
1350 function records the set patterns that are implicit at the start of each
1353 If an implicit set is found but the set is implicit on a critical edge,
1354 this critical edge is split.
1356 Return true if the CFG was modified, false otherwise. */
1359 find_implicit_sets (void)
1361 basic_block bb
, dest
;
1363 unsigned int count
= 0;
1364 bool edges_split
= false;
1365 size_t implicit_sets_size
= last_basic_block
+ 10;
1367 implicit_sets
= XCNEWVEC (rtx
, implicit_sets_size
);
1371 /* Check for more than one successor. */
1372 if (EDGE_COUNT (bb
->succs
) <= 1)
1375 cond
= fis_get_condition (BB_END (bb
));
1377 /* If no condition is found or if it isn't of a suitable form,
1379 if (! cond
|| ! implicit_set_cond_p (cond
))
1382 dest
= GET_CODE (cond
) == EQ
1383 ? BRANCH_EDGE (bb
)->dest
: FALLTHRU_EDGE (bb
)->dest
;
1385 /* If DEST doesn't go anywhere, ignore it. */
1386 if (! dest
|| dest
== EXIT_BLOCK_PTR
)
1389 /* We have found a suitable implicit set. Try to record it now as
1390 a SET in DEST. If DEST has more than one predecessor, the edge
1391 between BB and DEST is a critical edge and we must split it,
1392 because we can only record one implicit set per DEST basic block. */
1393 if (! single_pred_p (dest
))
1395 dest
= split_edge (find_edge (bb
, dest
));
1399 if (implicit_sets_size
<= (size_t) dest
->index
)
1401 size_t old_implicit_sets_size
= implicit_sets_size
;
1402 implicit_sets_size
*= 2;
1403 implicit_sets
= XRESIZEVEC (rtx
, implicit_sets
, implicit_sets_size
);
1404 memset (implicit_sets
+ old_implicit_sets_size
, 0,
1405 (implicit_sets_size
- old_implicit_sets_size
) * sizeof (rtx
));
1408 new_rtx
= gen_rtx_SET (VOIDmode
, XEXP (cond
, 0),
1410 implicit_sets
[dest
->index
] = new_rtx
;
1413 fprintf(dump_file
, "Implicit set of reg %d in ",
1414 REGNO (XEXP (cond
, 0)));
1415 fprintf(dump_file
, "basic block %d\n", dest
->index
);
1421 fprintf (dump_file
, "Found %d implicit sets\n", count
);
1423 /* Confess our sins. */
1427 /* Bypass conditional jumps. */
1429 /* The value of last_basic_block at the beginning of the jump_bypass
1430 pass. The use of redirect_edge_and_branch_force may introduce new
1431 basic blocks, but the data flow analysis is only valid for basic
1432 block indices less than bypass_last_basic_block. */
1434 static int bypass_last_basic_block
;
1436 /* Find a set of REGNO to a constant that is available at the end of basic
1437 block BB. Return NULL if no such set is found. Based heavily upon
1440 static struct expr
*
1441 find_bypass_set (int regno
, int bb
)
1443 struct expr
*result
= 0;
1448 struct expr
*set
= lookup_set (regno
, &set_hash_table
);
1452 if (TEST_BIT (cprop_avout
[bb
], set
->bitmap_index
))
1454 set
= next_set (regno
, set
);
1461 if (cprop_constant_p (src
))
1467 regno
= REGNO (src
);
1472 /* Subroutine of bypass_block that checks whether a pseudo is killed by
1473 any of the instructions inserted on an edge. Jump bypassing places
1474 condition code setters on CFG edges using insert_insn_on_edge. This
1475 function is required to check that our data flow analysis is still
1476 valid prior to commit_edge_insertions. */
1479 reg_killed_on_edge (const_rtx reg
, const_edge e
)
1483 for (insn
= e
->insns
.r
; insn
; insn
= NEXT_INSN (insn
))
1484 if (INSN_P (insn
) && reg_set_p (reg
, insn
))
1490 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1491 basic block BB which has more than one predecessor. If not NULL, SETCC
1492 is the first instruction of BB, which is immediately followed by JUMP_INSN
1493 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1494 Returns nonzero if a change was made.
1496 During the jump bypassing pass, we may place copies of SETCC instructions
1497 on CFG edges. The following routine must be careful to pay attention to
1498 these inserted insns when performing its transformations. */
1501 bypass_block (basic_block bb
, rtx setcc
, rtx jump
)
1506 int may_be_loop_header
;
1511 insn
= (setcc
!= NULL
) ? setcc
: jump
;
1513 /* Determine set of register uses in INSN. */
1515 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1516 note
= find_reg_equal_equiv_note (insn
);
1518 find_used_regs (&XEXP (note
, 0), NULL
);
1520 may_be_loop_header
= false;
1521 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1522 if (e
->flags
& EDGE_DFS_BACK
)
1524 may_be_loop_header
= true;
1529 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
1533 if (e
->flags
& EDGE_COMPLEX
)
1539 /* We can't redirect edges from new basic blocks. */
1540 if (e
->src
->index
>= bypass_last_basic_block
)
1546 /* The irreducible loops created by redirecting of edges entering the
1547 loop from outside would decrease effectiveness of some of the
1548 following optimizations, so prevent this. */
1549 if (may_be_loop_header
1550 && !(e
->flags
& EDGE_DFS_BACK
))
1556 for (i
= 0; i
< reg_use_count
; i
++)
1558 rtx reg_used
= reg_use_table
[i
];
1559 unsigned int regno
= REGNO (reg_used
);
1560 basic_block dest
, old_dest
;
1564 set
= find_bypass_set (regno
, e
->src
->index
);
1569 /* Check the data flow is valid after edge insertions. */
1570 if (e
->insns
.r
&& reg_killed_on_edge (reg_used
, e
))
1573 src
= SET_SRC (pc_set (jump
));
1576 src
= simplify_replace_rtx (src
,
1577 SET_DEST (PATTERN (setcc
)),
1578 SET_SRC (PATTERN (setcc
)));
1580 new_rtx
= simplify_replace_rtx (src
, reg_used
, set
->src
);
1582 /* Jump bypassing may have already placed instructions on
1583 edges of the CFG. We can't bypass an outgoing edge that
1584 has instructions associated with it, as these insns won't
1585 get executed if the incoming edge is redirected. */
1586 if (new_rtx
== pc_rtx
)
1588 edest
= FALLTHRU_EDGE (bb
);
1589 dest
= edest
->insns
.r
? NULL
: edest
->dest
;
1591 else if (GET_CODE (new_rtx
) == LABEL_REF
)
1593 dest
= BLOCK_FOR_INSN (XEXP (new_rtx
, 0));
1594 /* Don't bypass edges containing instructions. */
1595 edest
= find_edge (bb
, dest
);
1596 if (edest
&& edest
->insns
.r
)
1602 /* Avoid unification of the edge with other edges from original
1603 branch. We would end up emitting the instruction on "both"
1605 if (dest
&& setcc
&& !CC0_P (SET_DEST (PATTERN (setcc
)))
1606 && find_edge (e
->src
, dest
))
1612 && dest
!= EXIT_BLOCK_PTR
)
1614 if (current_loops
!= NULL
1615 && e
->src
->loop_father
->latch
== e
->src
)
1617 /* ??? Now we are creating (or may create) a loop
1618 with multiple entries. Simply mark it for
1619 removal. Alternatively we could not do this
1621 e
->src
->loop_father
->header
= NULL
;
1622 e
->src
->loop_father
->latch
= NULL
;
1625 redirect_edge_and_branch_force (e
, dest
);
1627 /* Copy the register setter to the redirected edge.
1628 Don't copy CC0 setters, as CC0 is dead after jump. */
1631 rtx pat
= PATTERN (setcc
);
1632 if (!CC0_P (SET_DEST (pat
)))
1633 insert_insn_on_edge (copy_insn (pat
), e
);
1636 if (dump_file
!= NULL
)
1638 fprintf (dump_file
, "JUMP-BYPASS: Proved reg %d "
1639 "in jump_insn %d equals constant ",
1640 regno
, INSN_UID (jump
));
1641 print_rtl (dump_file
, set
->src
);
1642 fprintf (dump_file
, "\nBypass edge from %d->%d to %d\n",
1643 e
->src
->index
, old_dest
->index
, dest
->index
);
1656 /* Find basic blocks with more than one predecessor that only contain a
1657 single conditional jump. If the result of the comparison is known at
1658 compile-time from any incoming edge, redirect that edge to the
1659 appropriate target. Return nonzero if a change was made.
1661 This function is now mis-named, because we also handle indirect jumps. */
1664 bypass_conditional_jumps (void)
1672 /* Note we start at block 1. */
1673 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
1676 bypass_last_basic_block
= last_basic_block
;
1677 mark_dfs_back_edges ();
1680 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
->next_bb
,
1681 EXIT_BLOCK_PTR
, next_bb
)
1683 /* Check for more than one predecessor. */
1684 if (!single_pred_p (bb
))
1687 FOR_BB_INSNS (bb
, insn
)
1688 if (DEBUG_INSN_P (insn
))
1690 else if (NONJUMP_INSN_P (insn
))
1694 if (GET_CODE (PATTERN (insn
)) != SET
)
1697 dest
= SET_DEST (PATTERN (insn
));
1698 if (REG_P (dest
) || CC0_P (dest
))
1703 else if (JUMP_P (insn
))
1705 if ((any_condjump_p (insn
) || computed_jump_p (insn
))
1706 && onlyjump_p (insn
))
1707 changed
|= bypass_block (bb
, setcc
, insn
);
1710 else if (INSN_P (insn
))
1715 /* If we bypassed any register setting insns, we inserted a
1716 copy on the redirected edge. These need to be committed. */
1718 commit_edge_insertions ();
1723 /* Return true if the graph is too expensive to optimize. PASS is the
1724 optimization about to be performed. */
1727 is_too_expensive (const char *pass
)
1729 /* Trying to perform global optimizations on flow graphs which have
1730 a high connectivity will take a long time and is unlikely to be
1731 particularly useful.
1733 In normal circumstances a cfg should have about twice as many
1734 edges as blocks. But we do not want to punish small functions
1735 which have a couple switch statements. Rather than simply
1736 threshold the number of blocks, uses something with a more
1737 graceful degradation. */
1738 if (n_edges
> 20000 + n_basic_blocks
* 4)
1740 warning (OPT_Wdisabled_optimization
,
1741 "%s: %d basic blocks and %d edges/basic block",
1742 pass
, n_basic_blocks
, n_edges
/ n_basic_blocks
);
1747 /* If allocating memory for the cprop bitmap would take up too much
1748 storage it's better just to disable the optimization. */
1750 * SBITMAP_SET_SIZE (max_reg_num ())
1751 * sizeof (SBITMAP_ELT_TYPE
)) > MAX_GCSE_MEMORY
)
1753 warning (OPT_Wdisabled_optimization
,
1754 "%s: %d basic blocks and %d registers",
1755 pass
, n_basic_blocks
, max_reg_num ());
1763 /* Main function for the CPROP pass. */
1766 one_cprop_pass (void)
1771 /* Return if there's nothing to do, or it is too expensive. */
1772 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1
1773 || is_too_expensive (_ ("const/copy propagation disabled")))
1776 global_const_prop_count
= local_const_prop_count
= 0;
1777 global_copy_prop_count
= local_copy_prop_count
= 0;
1780 gcc_obstack_init (&cprop_obstack
);
1782 /* Do a local const/copy propagation pass first. The global pass
1783 only handles global opportunities.
1784 If the local pass changes something, remove any unreachable blocks
1785 because the CPROP global dataflow analysis may get into infinite
1786 loops for CFGs with unreachable blocks.
1788 FIXME: This local pass should not be necessary after CSE (but for
1789 some reason it still is). It is also (proven) not necessary
1790 to run the local pass right after FWPWOP.
1792 FIXME: The global analysis would not get into infinite loops if it
1793 would use the DF solver (via df_simple_dataflow) instead of
1794 the solver implemented in this file. */
1795 changed
|= local_cprop_pass ();
1797 delete_unreachable_blocks ();
1799 /* Determine implicit sets. This may change the CFG (split critical
1800 edges if that exposes an implicit set).
1801 Note that find_implicit_sets() does not rely on up-to-date DF caches
1802 so that we do not have to re-run df_analyze() even if local CPROP
1804 ??? This could run earlier so that any uncovered implicit sets
1805 sets could be exploited in local_cprop_pass() also. Later. */
1806 changed
|= find_implicit_sets ();
1808 /* If local_cprop_pass() or find_implicit_sets() changed something,
1809 run df_analyze() to bring all insn caches up-to-date, and to take
1810 new basic blocks from edge splitting on the DF radar.
1811 NB: This also runs the fast DCE pass, because execute_rtl_cprop
1812 sets DF_LR_RUN_DCE. */
1816 /* Initialize implicit_set_indexes array. */
1817 implicit_set_indexes
= XNEWVEC (int, last_basic_block
);
1818 for (i
= 0; i
< last_basic_block
; i
++)
1819 implicit_set_indexes
[i
] = -1;
1821 alloc_hash_table (&set_hash_table
);
1822 compute_hash_table (&set_hash_table
);
1824 /* Free implicit_sets before peak usage. */
1825 free (implicit_sets
);
1826 implicit_sets
= NULL
;
1829 dump_hash_table (dump_file
, "SET", &set_hash_table
);
1830 if (set_hash_table
.n_elems
> 0)
1835 alloc_cprop_mem (last_basic_block
, set_hash_table
.n_elems
);
1836 compute_cprop_data ();
1838 free (implicit_set_indexes
);
1839 implicit_set_indexes
= NULL
;
1841 /* Allocate vars to track sets of regs. */
1842 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
1844 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
->next_bb
, EXIT_BLOCK_PTR
,
1847 /* Reset tables used to keep track of what's still valid [since
1848 the start of the block]. */
1849 reset_opr_set_tables ();
1851 FOR_BB_INSNS (bb
, insn
)
1854 changed
|= cprop_insn (insn
);
1856 /* Keep track of everything modified by this insn. */
1857 /* ??? Need to be careful w.r.t. mods done to INSN.
1858 Don't call mark_oprs_set if we turned the
1859 insn into a NOTE, or deleted the insn. */
1860 if (! NOTE_P (insn
) && ! INSN_DELETED_P (insn
))
1861 mark_oprs_set (insn
);
1865 changed
|= bypass_conditional_jumps ();
1867 FREE_REG_SET (reg_set_bitmap
);
1872 free (implicit_set_indexes
);
1873 implicit_set_indexes
= NULL
;
1876 free_hash_table (&set_hash_table
);
1877 obstack_free (&cprop_obstack
, NULL
);
1881 fprintf (dump_file
, "CPROP of %s, %d basic blocks, %d bytes needed, ",
1882 current_function_name (), n_basic_blocks
, bytes_used
);
1883 fprintf (dump_file
, "%d local const props, %d local copy props, ",
1884 local_const_prop_count
, local_copy_prop_count
);
1885 fprintf (dump_file
, "%d global const props, %d global copy props\n\n",
1886 global_const_prop_count
, global_copy_prop_count
);
1892 /* All the passes implemented in this file. Each pass has its
1893 own gate and execute function, and at the end of the file a
1894 pass definition for passes.c.
1896 We do not construct an accurate cfg in functions which call
1897 setjmp, so none of these passes runs if the function calls
1899 FIXME: Should just handle setjmp via REG_SETJMP notes. */
1902 gate_rtl_cprop (void)
1904 return optimize
> 0 && flag_gcse
1905 && !cfun
->calls_setjmp
1910 execute_rtl_cprop (void)
1913 delete_unreachable_blocks ();
1914 df_set_flags (DF_LR_RUN_DCE
);
1916 changed
= one_cprop_pass ();
1917 flag_rerun_cse_after_global_opts
|= changed
;
1919 cleanup_cfg (CLEANUP_CFG_CHANGED
);
1923 struct rtl_opt_pass pass_rtl_cprop
=
1928 gate_rtl_cprop
, /* gate */
1929 execute_rtl_cprop
, /* execute */
1932 0, /* static_pass_number */
1933 TV_CPROP
, /* tv_id */
1934 PROP_cfglayout
, /* properties_required */
1935 0, /* properties_provided */
1936 0, /* properties_destroyed */
1937 0, /* todo_flags_start */
1938 TODO_df_finish
| TODO_verify_rtl_sharing
|
1939 TODO_verify_flow
| TODO_ggc_collect
/* todo_flags_finish */