1 /* Global constant/copy propagation for RTL.
2 Copyright (C) 1997-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "diagnostic-core.h"
33 #include "insn-config.h"
38 #include "cfgcleanup.h"
49 #include "alloc-pool.h"
53 #include "tree-pass.h"
59 /* An obstack for our working variables. */
60 static struct obstack cprop_obstack
;
62 /* Occurrence of an expression.
63 There is one per basic block. If a pattern appears more than once the
64 last appearance is used. */
68 /* Next occurrence of this expression. */
69 struct cprop_occr
*next
;
70 /* The insn that computes the expression. */
74 typedef struct cprop_occr
*occr_t
;
76 /* Hash table entry for assignment expressions. */
80 /* The expression (DEST := SRC). */
84 /* Index in the available expression bitmaps. */
86 /* Next entry with the same hash. */
87 struct cprop_expr
*next_same_hash
;
88 /* List of available occurrence in basic blocks in the function.
89 An "available occurrence" is one that is the last occurrence in the
90 basic block and whose operands are not modified by following statements
91 in the basic block [including this insn]. */
92 struct cprop_occr
*avail_occr
;
95 /* Hash table for copy propagation expressions.
96 Each hash table is an array of buckets.
97 ??? It is known that if it were an array of entries, structure elements
98 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
99 not clear whether in the final analysis a sufficient amount of memory would
100 be saved as the size of the available expression bitmaps would be larger
101 [one could build a mapping table without holes afterwards though].
102 Someday I'll perform the computation and figure it out. */
107 This is an array of `set_hash_table_size' elements. */
108 struct cprop_expr
**table
;
110 /* Size of the hash table, in elements. */
113 /* Number of hash table elements. */
114 unsigned int n_elems
;
117 /* Copy propagation hash table. */
118 static struct hash_table_d set_hash_table
;
120 /* Array of implicit set patterns indexed by basic block index. */
121 static rtx
*implicit_sets
;
123 /* Array of indexes of expressions for implicit set patterns indexed by basic
124 block index. In other words, implicit_set_indexes[i] is the bitmap_index
125 of the expression whose RTX is implicit_sets[i]. */
126 static int *implicit_set_indexes
;
128 /* Bitmap containing one bit for each register in the program.
129 Used when performing GCSE to track which registers have been set since
130 the start or end of the basic block while traversing that block. */
131 static regset reg_set_bitmap
;
133 /* Various variables for statistics gathering. */
135 /* Memory used in a pass.
136 This isn't intended to be absolutely precise. Its intent is only
137 to keep an eye on memory usage. */
138 static int bytes_used
;
140 /* Number of local constants propagated. */
141 static int local_const_prop_count
;
142 /* Number of local copies propagated. */
143 static int local_copy_prop_count
;
144 /* Number of global constants propagated. */
145 static int global_const_prop_count
;
146 /* Number of global copies propagated. */
147 static int global_copy_prop_count
;
149 #define GOBNEW(T) ((T *) cprop_alloc (sizeof (T)))
150 #define GOBNEWVAR(T, S) ((T *) cprop_alloc ((S)))
152 /* Cover function to obstack_alloc. */
155 cprop_alloc (unsigned long size
)
158 return obstack_alloc (&cprop_obstack
, size
);
161 /* Return nonzero if register X is unchanged from INSN to the end
162 of INSN's basic block. */
165 reg_available_p (const_rtx x
, const rtx_insn
*insn ATTRIBUTE_UNUSED
)
167 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
170 /* Hash a set of register REGNO.
172 Sets are hashed on the register that is set. This simplifies the PRE copy
175 ??? May need to make things more elaborate. Later, as necessary. */
178 hash_mod (int regno
, int hash_table_size
)
180 return (unsigned) regno
% 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
*insn
,
191 struct hash_table_d
*table
, bool implicit
)
195 struct cprop_expr
*cur_expr
, *last_expr
= NULL
;
196 struct cprop_occr
*cur_occr
;
198 hash
= hash_mod (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 cprop_expr
);
215 bytes_used
+= sizeof (struct cprop_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 cprop_occr
);
249 bytes_used
+= sizeof (struct cprop_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
]
258 = cur_expr
->bitmap_index
;
261 /* Determine whether the rtx X should be treated as a constant for CPROP.
262 Since X might be inserted more than once we have to take care that it
266 cprop_constant_p (const_rtx x
)
268 return CONSTANT_P (x
) && (GET_CODE (x
) != CONST
|| shared_const_p (x
));
271 /* Determine whether the rtx X should be treated as a register that can
272 be propagated. Any pseudo-register is fine. */
275 cprop_reg_p (const_rtx x
)
277 return REG_P (x
) && !HARD_REGISTER_P (x
);
280 /* Scan SET present in INSN and add an entry to the hash TABLE.
281 IMPLICIT is true if it's an implicit set, false otherwise. */
284 hash_scan_set (rtx set
, rtx_insn
*insn
, struct hash_table_d
*table
,
287 rtx src
= SET_SRC (set
);
288 rtx dest
= SET_DEST (set
);
290 if (cprop_reg_p (dest
)
291 && reg_available_p (dest
, insn
)
292 && can_copy_p (GET_MODE (dest
)))
294 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
296 This allows us to do a single CPROP pass and still eliminate
297 redundant constants, addresses or other expressions that are
298 constructed with multiple instructions.
300 However, keep the original SRC if INSN is a simple reg-reg move. In
301 In this case, there will almost always be a REG_EQUAL note on the
302 insn that sets SRC. By recording the REG_EQUAL value here as SRC
303 for INSN, we miss copy propagation opportunities.
305 Note that this does not impede profitable constant propagations. We
306 "look through" reg-reg sets in lookup_set. */
307 rtx note
= find_reg_equal_equiv_note (insn
);
309 && REG_NOTE_KIND (note
) == REG_EQUAL
311 && cprop_constant_p (XEXP (note
, 0)))
312 src
= XEXP (note
, 0), set
= gen_rtx_SET (dest
, src
);
314 /* Record sets for constant/copy propagation. */
315 if ((cprop_reg_p (src
)
317 && reg_available_p (src
, insn
))
318 || cprop_constant_p (src
))
319 insert_set_in_table (dest
, src
, insn
, table
, implicit
);
323 /* Process INSN and add hash table entries as appropriate. */
326 hash_scan_insn (rtx_insn
*insn
, struct hash_table_d
*table
)
328 rtx pat
= PATTERN (insn
);
331 /* Pick out the sets of INSN and for other forms of instructions record
332 what's been modified. */
334 if (GET_CODE (pat
) == SET
)
335 hash_scan_set (pat
, insn
, table
, false);
336 else if (GET_CODE (pat
) == PARALLEL
)
337 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
339 rtx x
= XVECEXP (pat
, 0, i
);
341 if (GET_CODE (x
) == SET
)
342 hash_scan_set (x
, insn
, table
, false);
346 /* Dump the hash table TABLE to file FILE under the name NAME. */
349 dump_hash_table (FILE *file
, const char *name
, struct hash_table_d
*table
)
352 /* Flattened out table, so it's printed in proper order. */
353 struct cprop_expr
**flat_table
;
354 unsigned int *hash_val
;
355 struct cprop_expr
*expr
;
357 flat_table
= XCNEWVEC (struct cprop_expr
*, table
->n_elems
);
358 hash_val
= XNEWVEC (unsigned int, table
->n_elems
);
360 for (i
= 0; i
< (int) table
->size
; i
++)
361 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
363 flat_table
[expr
->bitmap_index
] = expr
;
364 hash_val
[expr
->bitmap_index
] = i
;
367 fprintf (file
, "%s hash table (%d buckets, %d entries)\n",
368 name
, table
->size
, table
->n_elems
);
370 for (i
= 0; i
< (int) table
->n_elems
; i
++)
371 if (flat_table
[i
] != 0)
373 expr
= flat_table
[i
];
374 fprintf (file
, "Index %d (hash value %d)\n ",
375 expr
->bitmap_index
, hash_val
[i
]);
376 print_rtl (file
, expr
->dest
);
377 fprintf (file
, " := ");
378 print_rtl (file
, expr
->src
);
379 fprintf (file
, "\n");
382 fprintf (file
, "\n");
388 /* Record as unavailable all registers that are DEF operands of INSN. */
391 make_set_regs_unavailable (rtx_insn
*insn
)
395 FOR_EACH_INSN_DEF (def
, insn
)
396 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (def
));
399 /* Top level function to create an assignment hash table.
401 Assignment entries are placed in the hash table if
402 - they are of the form (set (pseudo-reg) src),
403 - src is something we want to perform const/copy propagation on,
404 - none of the operands or target are subsequently modified in the block
406 Currently src must be a pseudo-reg or a const_int.
408 TABLE is the table computed. */
411 compute_hash_table_work (struct hash_table_d
*table
)
415 /* Allocate vars to track sets of regs. */
416 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
418 FOR_EACH_BB_FN (bb
, cfun
)
422 /* Reset tables used to keep track of what's not yet invalid [since
423 the end of the block]. */
424 CLEAR_REG_SET (reg_set_bitmap
);
426 /* Go over all insns from the last to the first. This is convenient
427 for tracking available registers, i.e. not set between INSN and
428 the end of the basic block BB. */
429 FOR_BB_INSNS_REVERSE (bb
, insn
)
431 /* Only real insns are interesting. */
432 if (!NONDEBUG_INSN_P (insn
))
435 /* Record interesting sets from INSN in the hash table. */
436 hash_scan_insn (insn
, table
);
438 /* Any registers set in INSN will make SETs above it not AVAIL. */
439 make_set_regs_unavailable (insn
);
442 /* Insert implicit sets in the hash table, pretending they appear as
443 insns at the head of the basic block. */
444 if (implicit_sets
[bb
->index
] != NULL_RTX
)
445 hash_scan_set (implicit_sets
[bb
->index
], BB_HEAD (bb
), table
, true);
448 FREE_REG_SET (reg_set_bitmap
);
451 /* Allocate space for the set/expr hash TABLE.
452 It is used to determine the number of buckets to use. */
455 alloc_hash_table (struct hash_table_d
*table
)
459 n
= get_max_insn_count ();
462 if (table
->size
< 11)
465 /* Attempt to maintain efficient use of hash table.
466 Making it an odd number is simplest for now.
467 ??? Later take some measurements. */
469 n
= table
->size
* sizeof (struct cprop_expr
*);
470 table
->table
= XNEWVAR (struct cprop_expr
*, n
);
473 /* Free things allocated by alloc_hash_table. */
476 free_hash_table (struct hash_table_d
*table
)
481 /* Compute the hash TABLE for doing copy/const propagation or
482 expression hash table. */
485 compute_hash_table (struct hash_table_d
*table
)
487 /* Initialize count of number of entries in hash table. */
489 memset (table
->table
, 0, table
->size
* sizeof (struct cprop_expr
*));
491 compute_hash_table_work (table
);
494 /* Expression tracking support. */
496 /* Lookup REGNO in the set TABLE. The result is a pointer to the
497 table entry, or NULL if not found. */
499 static struct cprop_expr
*
500 lookup_set (unsigned int regno
, struct hash_table_d
*table
)
502 unsigned int hash
= hash_mod (regno
, table
->size
);
503 struct cprop_expr
*expr
;
505 expr
= table
->table
[hash
];
507 while (expr
&& REGNO (expr
->dest
) != regno
)
508 expr
= expr
->next_same_hash
;
513 /* Return the next entry for REGNO in list EXPR. */
515 static struct cprop_expr
*
516 next_set (unsigned int regno
, struct cprop_expr
*expr
)
519 expr
= expr
->next_same_hash
;
520 while (expr
&& REGNO (expr
->dest
) != regno
);
525 /* Reset tables used to keep track of what's still available [since the
526 start of the block]. */
529 reset_opr_set_tables (void)
531 /* Maintain a bitmap of which regs have been set since beginning of
533 CLEAR_REG_SET (reg_set_bitmap
);
536 /* Return nonzero if the register X has not been set yet [since the
537 start of the basic block containing INSN]. */
540 reg_not_set_p (const_rtx x
, const rtx_insn
*insn ATTRIBUTE_UNUSED
)
542 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
545 /* Record things set by INSN.
546 This data is used by reg_not_set_p. */
549 mark_oprs_set (rtx_insn
*insn
)
553 FOR_EACH_INSN_DEF (def
, insn
)
554 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (def
));
557 /* Compute copy/constant propagation working variables. */
559 /* Local properties of assignments. */
560 static sbitmap
*cprop_avloc
;
561 static sbitmap
*cprop_kill
;
563 /* Global properties of assignments (computed from the local properties). */
564 static sbitmap
*cprop_avin
;
565 static sbitmap
*cprop_avout
;
567 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
568 basic blocks. N_SETS is the number of sets. */
571 alloc_cprop_mem (int n_blocks
, int n_sets
)
573 cprop_avloc
= sbitmap_vector_alloc (n_blocks
, n_sets
);
574 cprop_kill
= sbitmap_vector_alloc (n_blocks
, n_sets
);
576 cprop_avin
= sbitmap_vector_alloc (n_blocks
, n_sets
);
577 cprop_avout
= sbitmap_vector_alloc (n_blocks
, n_sets
);
580 /* Free vars used by copy/const propagation. */
583 free_cprop_mem (void)
585 sbitmap_vector_free (cprop_avloc
);
586 sbitmap_vector_free (cprop_kill
);
587 sbitmap_vector_free (cprop_avin
);
588 sbitmap_vector_free (cprop_avout
);
591 /* Compute the local properties of each recorded expression.
593 Local properties are those that are defined by the block, irrespective of
596 An expression is killed in a block if its operands, either DEST or SRC, are
597 modified in the block.
599 An expression is computed (locally available) in a block if it is computed
600 at least once and expression would contain the same value if the
601 computation was moved to the end of the block.
603 KILL and COMP are destination sbitmaps for recording local properties. */
606 compute_local_properties (sbitmap
*kill
, sbitmap
*comp
,
607 struct hash_table_d
*table
)
611 /* Initialize the bitmaps that were passed in. */
612 bitmap_vector_clear (kill
, last_basic_block_for_fn (cfun
));
613 bitmap_vector_clear (comp
, last_basic_block_for_fn (cfun
));
615 for (i
= 0; i
< table
->size
; i
++)
617 struct cprop_expr
*expr
;
619 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
621 int indx
= expr
->bitmap_index
;
623 struct cprop_occr
*occr
;
625 /* For each definition of the destination pseudo-reg, the expression
626 is killed in the block where the definition is. */
627 for (def
= DF_REG_DEF_CHAIN (REGNO (expr
->dest
));
628 def
; def
= DF_REF_NEXT_REG (def
))
629 bitmap_set_bit (kill
[DF_REF_BB (def
)->index
], indx
);
631 /* If the source is a pseudo-reg, for each definition of the source,
632 the expression is killed in the block where the definition is. */
633 if (REG_P (expr
->src
))
634 for (def
= DF_REG_DEF_CHAIN (REGNO (expr
->src
));
635 def
; def
= DF_REF_NEXT_REG (def
))
636 bitmap_set_bit (kill
[DF_REF_BB (def
)->index
], indx
);
638 /* The occurrences recorded in avail_occr are exactly those that
639 are locally available in the block where they are. */
640 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
642 bitmap_set_bit (comp
[BLOCK_FOR_INSN (occr
->insn
)->index
], indx
);
648 /* Hash table support. */
650 /* Top level routine to do the dataflow analysis needed by copy/const
654 compute_cprop_data (void)
658 compute_local_properties (cprop_kill
, cprop_avloc
, &set_hash_table
);
659 compute_available (cprop_avloc
, cprop_kill
, cprop_avout
, cprop_avin
);
661 /* Merge implicit sets into CPROP_AVIN. They are always available at the
662 entry of their basic block. We need to do this because 1) implicit sets
663 aren't recorded for the local pass so they cannot be propagated within
664 their basic block by this pass and 2) the global pass would otherwise
665 propagate them only in the successors of their basic block. */
666 FOR_EACH_BB_FN (bb
, cfun
)
668 int index
= implicit_set_indexes
[bb
->index
];
670 bitmap_set_bit (cprop_avin
[bb
->index
], index
);
674 /* Copy/constant propagation. */
676 /* Maximum number of register uses in an insn that we handle. */
679 /* Table of uses (registers, both hard and pseudo) found in an insn.
680 Allocated statically to avoid alloc/free complexity and overhead. */
681 static rtx reg_use_table
[MAX_USES
];
683 /* Index into `reg_use_table' while building it. */
684 static unsigned reg_use_count
;
686 /* Set up a list of register numbers used in INSN. The found uses are stored
687 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
688 and contains the number of uses in the table upon exit.
690 ??? If a register appears multiple times we will record it multiple times.
691 This doesn't hurt anything but it will slow things down. */
694 find_used_regs (rtx
*xptr
, void *data ATTRIBUTE_UNUSED
)
701 /* repeat is used to turn tail-recursion into iteration since GCC
702 can't do it when there's no return value. */
710 if (reg_use_count
== MAX_USES
)
713 reg_use_table
[reg_use_count
] = x
;
717 /* Recursively scan the operands of this expression. */
719 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
723 /* If we are about to do the last recursive call
724 needed at this level, change it into iteration.
725 This function is called enough to be worth it. */
732 find_used_regs (&XEXP (x
, i
), data
);
734 else if (fmt
[i
] == 'E')
735 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
736 find_used_regs (&XVECEXP (x
, i
, j
), data
);
740 /* Try to replace all uses of FROM in INSN with TO.
741 Return nonzero if successful. */
744 try_replace_reg (rtx from
, rtx to
, rtx_insn
*insn
)
746 rtx note
= find_reg_equal_equiv_note (insn
);
749 rtx set
= single_set (insn
);
751 bool check_rtx_costs
= true;
752 bool speed
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn
));
753 int old_cost
= set
? set_rtx_cost (set
, speed
) : 0;
756 && REG_NOTE_KIND (note
) == REG_EQUAL
757 && (GET_CODE (XEXP (note
, 0)) == CONST
758 || CONSTANT_P (XEXP (note
, 0))))
759 || (set
&& CONSTANT_P (SET_SRC (set
))))
760 check_rtx_costs
= false;
762 /* Usually we substitute easy stuff, so we won't copy everything.
763 We however need to take care to not duplicate non-trivial CONST
767 validate_replace_src_group (from
, to
, insn
);
769 /* If TO is a constant, check the cost of the set after propagation
770 to the cost of the set before the propagation. If the cost is
771 higher, then do not replace FROM with TO. */
775 && (set_rtx_cost (set
, speed
) > old_cost
))
782 if (num_changes_pending () && apply_change_group ())
785 /* Try to simplify SET_SRC if we have substituted a constant. */
786 if (success
&& set
&& CONSTANT_P (to
))
788 src
= simplify_rtx (SET_SRC (set
));
791 validate_change (insn
, &SET_SRC (set
), src
, 0);
794 /* If there is already a REG_EQUAL note, update the expression in it
795 with our replacement. */
796 if (note
!= 0 && REG_NOTE_KIND (note
) == REG_EQUAL
)
797 set_unique_reg_note (insn
, REG_EQUAL
,
798 simplify_replace_rtx (XEXP (note
, 0), from
, to
));
799 if (!success
&& set
&& reg_mentioned_p (from
, SET_SRC (set
)))
801 /* If above failed and this is a single set, try to simplify the source
802 of the set given our substitution. We could perhaps try this for
803 multiple SETs, but it probably won't buy us anything. */
804 src
= simplify_replace_rtx (SET_SRC (set
), from
, to
);
806 if (!rtx_equal_p (src
, SET_SRC (set
))
807 && validate_change (insn
, &SET_SRC (set
), src
, 0))
810 /* If we've failed perform the replacement, have a single SET to
811 a REG destination and don't yet have a note, add a REG_EQUAL note
812 to not lose information. */
813 if (!success
&& note
== 0 && set
!= 0 && REG_P (SET_DEST (set
)))
814 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
817 if (set
&& MEM_P (SET_DEST (set
)) && reg_mentioned_p (from
, SET_DEST (set
)))
819 /* Registers can also appear as uses in SET_DEST if it is a MEM.
820 We could perhaps try this for multiple SETs, but it probably
821 won't buy us anything. */
822 rtx dest
= simplify_replace_rtx (SET_DEST (set
), from
, to
);
824 if (!rtx_equal_p (dest
, SET_DEST (set
))
825 && validate_change (insn
, &SET_DEST (set
), dest
, 0))
829 /* REG_EQUAL may get simplified into register.
830 We don't allow that. Remove that note. This code ought
831 not to happen, because previous code ought to synthesize
832 reg-reg move, but be on the safe side. */
833 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
&& REG_P (XEXP (note
, 0)))
834 remove_note (insn
, note
);
839 /* Find a set of REGNOs that are available on entry to INSN's block. If found,
840 SET_RET[0] will be assigned a set with a register source and SET_RET[1] a
841 set with a constant source. If not found the corresponding entry is set to
845 find_avail_set (int regno
, rtx_insn
*insn
, struct cprop_expr
*set_ret
[2])
847 set_ret
[0] = set_ret
[1] = NULL
;
849 /* Loops are not possible here. To get a loop we would need two sets
850 available at the start of the block containing INSN. i.e. we would
851 need two sets like this available at the start of the block:
853 (set (reg X) (reg Y))
854 (set (reg Y) (reg X))
856 This can not happen since the set of (reg Y) would have killed the
857 set of (reg X) making it unavailable at the start of this block. */
861 struct cprop_expr
*set
= lookup_set (regno
, &set_hash_table
);
863 /* Find a set that is available at the start of the block
864 which contains INSN. */
867 if (bitmap_bit_p (cprop_avin
[BLOCK_FOR_INSN (insn
)->index
],
870 set
= next_set (regno
, set
);
873 /* If no available set was found we've reached the end of the
874 (possibly empty) copy chain. */
880 /* We know the set is available.
881 Now check that SRC is locally anticipatable (i.e. none of the
882 source operands have changed since the start of the block).
884 If the source operand changed, we may still use it for the next
885 iteration of this loop, but we may not use it for substitutions. */
887 if (cprop_constant_p (src
))
889 else if (reg_not_set_p (src
, insn
))
892 /* If the source of the set is anything except a register, then
893 we have reached the end of the copy chain. */
897 /* Follow the copy chain, i.e. start another iteration of the loop
898 and see if we have an available copy into SRC. */
903 /* Subroutine of cprop_insn that tries to propagate constants into
904 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
905 it is the instruction that immediately precedes JUMP, and must be a
906 single SET of a register. FROM is what we will try to replace,
907 SRC is the constant we will try to substitute for it. Return nonzero
908 if a change was made. */
911 cprop_jump (basic_block bb
, rtx_insn
*setcc
, rtx_insn
*jump
, rtx from
, rtx src
)
913 rtx new_rtx
, set_src
, note_src
;
914 rtx set
= pc_set (jump
);
915 rtx note
= find_reg_equal_equiv_note (jump
);
919 note_src
= XEXP (note
, 0);
920 if (GET_CODE (note_src
) == EXPR_LIST
)
923 else note_src
= NULL_RTX
;
925 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
926 set_src
= note_src
? note_src
: SET_SRC (set
);
928 /* First substitute the SETCC condition into the JUMP instruction,
929 then substitute that given values into this expanded JUMP. */
930 if (setcc
!= NULL_RTX
931 && !modified_between_p (from
, setcc
, jump
)
932 && !modified_between_p (src
, setcc
, jump
))
935 rtx setcc_set
= single_set (setcc
);
936 rtx setcc_note
= find_reg_equal_equiv_note (setcc
);
937 setcc_src
= (setcc_note
&& GET_CODE (XEXP (setcc_note
, 0)) != EXPR_LIST
)
938 ? XEXP (setcc_note
, 0) : SET_SRC (setcc_set
);
939 set_src
= simplify_replace_rtx (set_src
, SET_DEST (setcc_set
),
945 new_rtx
= simplify_replace_rtx (set_src
, from
, src
);
947 /* If no simplification can be made, then try the next register. */
948 if (rtx_equal_p (new_rtx
, SET_SRC (set
)))
951 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
952 if (new_rtx
== pc_rtx
)
956 /* Ensure the value computed inside the jump insn to be equivalent
957 to one computed by setcc. */
958 if (setcc
&& modified_in_p (new_rtx
, setcc
))
960 if (! validate_unshare_change (jump
, &SET_SRC (set
), new_rtx
, 0))
962 /* When (some) constants are not valid in a comparison, and there
963 are two registers to be replaced by constants before the entire
964 comparison can be folded into a constant, we need to keep
965 intermediate information in REG_EQUAL notes. For targets with
966 separate compare insns, such notes are added by try_replace_reg.
967 When we have a combined compare-and-branch instruction, however,
968 we need to attach a note to the branch itself to make this
969 optimization work. */
971 if (!rtx_equal_p (new_rtx
, note_src
))
972 set_unique_reg_note (jump
, REG_EQUAL
, copy_rtx (new_rtx
));
976 /* Remove REG_EQUAL note after simplification. */
978 remove_note (jump
, note
);
981 /* Delete the cc0 setter. */
982 if (HAVE_cc0
&& setcc
!= NULL
&& CC0_P (SET_DEST (single_set (setcc
))))
985 global_const_prop_count
++;
986 if (dump_file
!= NULL
)
989 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with"
990 "constant ", REGNO (from
), INSN_UID (jump
));
991 print_rtl (dump_file
, src
);
992 fprintf (dump_file
, "\n");
994 purge_dead_edges (bb
);
996 /* If a conditional jump has been changed into unconditional jump, remove
997 the jump and make the edge fallthru - this is always called in
999 if (new_rtx
!= pc_rtx
&& simplejump_p (jump
))
1004 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1005 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1006 && BB_HEAD (e
->dest
) == JUMP_LABEL (jump
))
1008 e
->flags
|= EDGE_FALLTHRU
;
1017 /* Subroutine of cprop_insn that tries to propagate constants. FROM is what
1018 we will try to replace, SRC is the constant we will try to substitute for
1019 it and INSN is the instruction where this will be happening. */
1022 constprop_register (rtx from
, rtx src
, rtx_insn
*insn
)
1026 /* Check for reg or cc0 setting instructions followed by
1027 conditional branch instructions first. */
1028 if ((sset
= single_set (insn
)) != NULL
1030 && any_condjump_p (NEXT_INSN (insn
)) && onlyjump_p (NEXT_INSN (insn
)))
1032 rtx dest
= SET_DEST (sset
);
1033 if ((REG_P (dest
) || CC0_P (dest
))
1034 && cprop_jump (BLOCK_FOR_INSN (insn
), insn
, NEXT_INSN (insn
),
1039 /* Handle normal insns next. */
1040 if (NONJUMP_INSN_P (insn
) && try_replace_reg (from
, src
, insn
))
1043 /* Try to propagate a CONST_INT into a conditional jump.
1044 We're pretty specific about what we will handle in this
1045 code, we can extend this as necessary over time.
1047 Right now the insn in question must look like
1048 (set (pc) (if_then_else ...)) */
1049 else if (any_condjump_p (insn
) && onlyjump_p (insn
))
1050 return cprop_jump (BLOCK_FOR_INSN (insn
), NULL
, insn
, from
, src
);
1054 /* Perform constant and copy propagation on INSN.
1055 Return nonzero if a change was made. */
1058 cprop_insn (rtx_insn
*insn
)
1061 int changed
= 0, changed_this_round
;
1066 changed_this_round
= 0;
1068 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1070 /* We may win even when propagating constants into notes. */
1071 note
= find_reg_equal_equiv_note (insn
);
1073 find_used_regs (&XEXP (note
, 0), NULL
);
1075 for (i
= 0; i
< reg_use_count
; i
++)
1077 rtx reg_used
= reg_use_table
[i
];
1078 unsigned int regno
= REGNO (reg_used
);
1079 rtx src_cst
= NULL
, src_reg
= NULL
;
1080 struct cprop_expr
*set
[2];
1082 /* If the register has already been set in this block, there's
1083 nothing we can do. */
1084 if (! reg_not_set_p (reg_used
, insn
))
1087 /* Find an assignment that sets reg_used and is available
1088 at the start of the block. */
1089 find_avail_set (regno
, insn
, set
);
1091 src_reg
= set
[0]->src
;
1093 src_cst
= set
[1]->src
;
1095 /* Constant propagation. */
1096 if (src_cst
&& cprop_constant_p (src_cst
)
1097 && constprop_register (reg_used
, src_cst
, insn
))
1099 changed_this_round
= changed
= 1;
1100 global_const_prop_count
++;
1101 if (dump_file
!= NULL
)
1104 "GLOBAL CONST-PROP: Replacing reg %d in ", regno
);
1105 fprintf (dump_file
, "insn %d with constant ",
1107 print_rtl (dump_file
, src_cst
);
1108 fprintf (dump_file
, "\n");
1110 if (insn
->deleted ())
1113 /* Copy propagation. */
1114 else if (src_reg
&& cprop_reg_p (src_reg
)
1115 && REGNO (src_reg
) != regno
1116 && try_replace_reg (reg_used
, src_reg
, insn
))
1118 changed_this_round
= changed
= 1;
1119 global_copy_prop_count
++;
1120 if (dump_file
!= NULL
)
1123 "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1124 regno
, INSN_UID (insn
));
1125 fprintf (dump_file
, " with reg %d\n", REGNO (src_reg
));
1128 /* The original insn setting reg_used may or may not now be
1129 deletable. We leave the deletion to DCE. */
1130 /* FIXME: If it turns out that the insn isn't deletable,
1131 then we may have unnecessarily extended register lifetimes
1132 and made things worse. */
1136 /* If try_replace_reg simplified the insn, the regs found by find_used_regs
1137 may not be valid anymore. Start over. */
1138 while (changed_this_round
);
1140 if (changed
&& DEBUG_INSN_P (insn
))
1146 /* Like find_used_regs, but avoid recording uses that appear in
1147 input-output contexts such as zero_extract or pre_dec. This
1148 restricts the cases we consider to those for which local cprop
1149 can legitimately make replacements. */
1152 local_cprop_find_used_regs (rtx
*xptr
, void *data
)
1159 switch (GET_CODE (x
))
1163 case STRICT_LOW_PART
:
1172 /* Can only legitimately appear this early in the context of
1173 stack pushes for function arguments, but handle all of the
1174 codes nonetheless. */
1178 /* Setting a subreg of a register larger than word_mode leaves
1179 the non-written words unchanged. */
1180 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x
))) > BITS_PER_WORD
)
1188 find_used_regs (xptr
, data
);
1191 /* Try to perform local const/copy propagation on X in INSN. */
1194 do_local_cprop (rtx x
, rtx_insn
*insn
)
1196 rtx newreg
= NULL
, newcnst
= NULL
;
1198 /* Rule out USE instructions and ASM statements as we don't want to
1199 change the hard registers mentioned. */
1202 || (GET_CODE (PATTERN (insn
)) != USE
1203 && asm_noperands (PATTERN (insn
)) < 0)))
1205 cselib_val
*val
= cselib_lookup (x
, GET_MODE (x
), 0, VOIDmode
);
1206 struct elt_loc_list
*l
;
1210 for (l
= val
->locs
; l
; l
= l
->next
)
1212 rtx this_rtx
= l
->loc
;
1215 if (cprop_constant_p (this_rtx
))
1217 if (cprop_reg_p (this_rtx
)
1218 /* Don't copy propagate if it has attached REG_EQUIV note.
1219 At this point this only function parameters should have
1220 REG_EQUIV notes and if the argument slot is used somewhere
1221 explicitly, it means address of parameter has been taken,
1222 so we should not extend the lifetime of the pseudo. */
1223 && (!(note
= find_reg_note (l
->setting_insn
, REG_EQUIV
, NULL_RTX
))
1224 || ! MEM_P (XEXP (note
, 0))))
1227 if (newcnst
&& constprop_register (x
, newcnst
, insn
))
1229 if (dump_file
!= NULL
)
1231 fprintf (dump_file
, "LOCAL CONST-PROP: Replacing reg %d in ",
1233 fprintf (dump_file
, "insn %d with constant ",
1235 print_rtl (dump_file
, newcnst
);
1236 fprintf (dump_file
, "\n");
1238 local_const_prop_count
++;
1241 else if (newreg
&& newreg
!= x
&& try_replace_reg (x
, newreg
, insn
))
1243 if (dump_file
!= NULL
)
1246 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1247 REGNO (x
), INSN_UID (insn
));
1248 fprintf (dump_file
, " with reg %d\n", REGNO (newreg
));
1250 local_copy_prop_count
++;
1257 /* Do local const/copy propagation (i.e. within each basic block). */
1260 local_cprop_pass (void)
1264 bool changed
= false;
1268 FOR_EACH_BB_FN (bb
, cfun
)
1270 FOR_BB_INSNS (bb
, insn
)
1274 rtx note
= find_reg_equal_equiv_note (insn
);
1278 note_uses (&PATTERN (insn
), local_cprop_find_used_regs
,
1281 local_cprop_find_used_regs (&XEXP (note
, 0), NULL
);
1283 for (i
= 0; i
< reg_use_count
; i
++)
1285 if (do_local_cprop (reg_use_table
[i
], insn
))
1287 if (!DEBUG_INSN_P (insn
))
1292 if (insn
->deleted ())
1295 while (i
< reg_use_count
);
1297 cselib_process_insn (insn
);
1300 /* Forget everything at the end of a basic block. */
1301 cselib_clear_table ();
1309 /* Similar to get_condition, only the resulting condition must be
1310 valid at JUMP, instead of at EARLIEST.
1312 This differs from noce_get_condition in ifcvt.c in that we prefer not to
1313 settle for the condition variable in the jump instruction being integral.
1314 We prefer to be able to record the value of a user variable, rather than
1315 the value of a temporary used in a condition. This could be solved by
1316 recording the value of *every* register scanned by canonicalize_condition,
1317 but this would require some code reorganization. */
1320 fis_get_condition (rtx_insn
*jump
)
1322 return get_condition (jump
, NULL
, false, true);
1325 /* Check the comparison COND to see if we can safely form an implicit
1329 implicit_set_cond_p (const_rtx cond
)
1334 /* COND must be either an EQ or NE comparison. */
1335 if (GET_CODE (cond
) != EQ
&& GET_CODE (cond
) != NE
)
1338 /* The first operand of COND must be a register we can propagate. */
1339 if (!cprop_reg_p (XEXP (cond
, 0)))
1342 /* The second operand of COND must be a suitable constant. */
1343 mode
= GET_MODE (XEXP (cond
, 0));
1344 cst
= XEXP (cond
, 1);
1346 /* We can't perform this optimization if either operand might be or might
1347 contain a signed zero. */
1348 if (HONOR_SIGNED_ZEROS (mode
))
1350 /* It is sufficient to check if CST is or contains a zero. We must
1351 handle float, complex, and vector. If any subpart is a zero, then
1352 the optimization can't be performed. */
1353 /* ??? The complex and vector checks are not implemented yet. We just
1354 always return zero for them. */
1355 if (CONST_DOUBLE_AS_FLOAT_P (cst
))
1358 REAL_VALUE_FROM_CONST_DOUBLE (d
, cst
);
1359 if (REAL_VALUES_EQUAL (d
, dconst0
))
1366 return cprop_constant_p (cst
);
1369 /* Find the implicit sets of a function. An "implicit set" is a constraint
1370 on the value of a variable, implied by a conditional jump. For example,
1371 following "if (x == 2)", the then branch may be optimized as though the
1372 conditional performed an "explicit set", in this example, "x = 2". This
1373 function records the set patterns that are implicit at the start of each
1376 If an implicit set is found but the set is implicit on a critical edge,
1377 this critical edge is split.
1379 Return true if the CFG was modified, false otherwise. */
1382 find_implicit_sets (void)
1384 basic_block bb
, dest
;
1386 unsigned int count
= 0;
1387 bool edges_split
= false;
1388 size_t implicit_sets_size
= last_basic_block_for_fn (cfun
) + 10;
1390 implicit_sets
= XCNEWVEC (rtx
, implicit_sets_size
);
1392 FOR_EACH_BB_FN (bb
, cfun
)
1394 /* Check for more than one successor. */
1395 if (EDGE_COUNT (bb
->succs
) <= 1)
1398 cond
= fis_get_condition (BB_END (bb
));
1400 /* If no condition is found or if it isn't of a suitable form,
1402 if (! cond
|| ! implicit_set_cond_p (cond
))
1405 dest
= GET_CODE (cond
) == EQ
1406 ? BRANCH_EDGE (bb
)->dest
: FALLTHRU_EDGE (bb
)->dest
;
1408 /* If DEST doesn't go anywhere, ignore it. */
1409 if (! dest
|| dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1412 /* We have found a suitable implicit set. Try to record it now as
1413 a SET in DEST. If DEST has more than one predecessor, the edge
1414 between BB and DEST is a critical edge and we must split it,
1415 because we can only record one implicit set per DEST basic block. */
1416 if (! single_pred_p (dest
))
1418 dest
= split_edge (find_edge (bb
, dest
));
1422 if (implicit_sets_size
<= (size_t) dest
->index
)
1424 size_t old_implicit_sets_size
= implicit_sets_size
;
1425 implicit_sets_size
*= 2;
1426 implicit_sets
= XRESIZEVEC (rtx
, implicit_sets
, implicit_sets_size
);
1427 memset (implicit_sets
+ old_implicit_sets_size
, 0,
1428 (implicit_sets_size
- old_implicit_sets_size
) * sizeof (rtx
));
1431 new_rtx
= gen_rtx_SET (XEXP (cond
, 0), XEXP (cond
, 1));
1432 implicit_sets
[dest
->index
] = new_rtx
;
1435 fprintf (dump_file
, "Implicit set of reg %d in ",
1436 REGNO (XEXP (cond
, 0)));
1437 fprintf (dump_file
, "basic block %d\n", dest
->index
);
1443 fprintf (dump_file
, "Found %d implicit sets\n", count
);
1445 /* Confess our sins. */
1449 /* Bypass conditional jumps. */
1451 /* The value of last_basic_block at the beginning of the jump_bypass
1452 pass. The use of redirect_edge_and_branch_force may introduce new
1453 basic blocks, but the data flow analysis is only valid for basic
1454 block indices less than bypass_last_basic_block. */
1456 static int bypass_last_basic_block
;
1458 /* Find a set of REGNO to a constant that is available at the end of basic
1459 block BB. Return NULL if no such set is found. Based heavily upon
1462 static struct cprop_expr
*
1463 find_bypass_set (int regno
, int bb
)
1465 struct cprop_expr
*result
= 0;
1470 struct cprop_expr
*set
= lookup_set (regno
, &set_hash_table
);
1474 if (bitmap_bit_p (cprop_avout
[bb
], set
->bitmap_index
))
1476 set
= next_set (regno
, set
);
1483 if (cprop_constant_p (src
))
1489 regno
= REGNO (src
);
1494 /* Subroutine of bypass_block that checks whether a pseudo is killed by
1495 any of the instructions inserted on an edge. Jump bypassing places
1496 condition code setters on CFG edges using insert_insn_on_edge. This
1497 function is required to check that our data flow analysis is still
1498 valid prior to commit_edge_insertions. */
1501 reg_killed_on_edge (const_rtx reg
, const_edge e
)
1505 for (insn
= e
->insns
.r
; insn
; insn
= NEXT_INSN (insn
))
1506 if (INSN_P (insn
) && reg_set_p (reg
, insn
))
1512 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1513 basic block BB which has more than one predecessor. If not NULL, SETCC
1514 is the first instruction of BB, which is immediately followed by JUMP_INSN
1515 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1516 Returns nonzero if a change was made.
1518 During the jump bypassing pass, we may place copies of SETCC instructions
1519 on CFG edges. The following routine must be careful to pay attention to
1520 these inserted insns when performing its transformations. */
1523 bypass_block (basic_block bb
, rtx_insn
*setcc
, rtx_insn
*jump
)
1529 int may_be_loop_header
= false;
1534 insn
= (setcc
!= NULL
) ? setcc
: jump
;
1536 /* Determine set of register uses in INSN. */
1538 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1539 note
= find_reg_equal_equiv_note (insn
);
1541 find_used_regs (&XEXP (note
, 0), NULL
);
1545 /* If we are to preserve loop structure then do not bypass
1546 a loop header. This will either rotate the loop, create
1547 multiple entry loops or even irreducible regions. */
1548 if (bb
== bb
->loop_father
->header
)
1553 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1554 if (e
->flags
& EDGE_DFS_BACK
)
1556 may_be_loop_header
= true;
1562 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
1566 if (e
->flags
& EDGE_COMPLEX
)
1572 /* We can't redirect edges from new basic blocks. */
1573 if (e
->src
->index
>= bypass_last_basic_block
)
1579 /* The irreducible loops created by redirecting of edges entering the
1580 loop from outside would decrease effectiveness of some of the
1581 following optimizations, so prevent this. */
1582 if (may_be_loop_header
1583 && !(e
->flags
& EDGE_DFS_BACK
))
1589 for (i
= 0; i
< reg_use_count
; i
++)
1591 rtx reg_used
= reg_use_table
[i
];
1592 unsigned int regno
= REGNO (reg_used
);
1593 basic_block dest
, old_dest
;
1594 struct cprop_expr
*set
;
1597 set
= find_bypass_set (regno
, e
->src
->index
);
1602 /* Check the data flow is valid after edge insertions. */
1603 if (e
->insns
.r
&& reg_killed_on_edge (reg_used
, e
))
1606 src
= SET_SRC (pc_set (jump
));
1609 src
= simplify_replace_rtx (src
,
1610 SET_DEST (PATTERN (setcc
)),
1611 SET_SRC (PATTERN (setcc
)));
1613 new_rtx
= simplify_replace_rtx (src
, reg_used
, set
->src
);
1615 /* Jump bypassing may have already placed instructions on
1616 edges of the CFG. We can't bypass an outgoing edge that
1617 has instructions associated with it, as these insns won't
1618 get executed if the incoming edge is redirected. */
1619 if (new_rtx
== pc_rtx
)
1621 edest
= FALLTHRU_EDGE (bb
);
1622 dest
= edest
->insns
.r
? NULL
: edest
->dest
;
1624 else if (GET_CODE (new_rtx
) == LABEL_REF
)
1626 dest
= BLOCK_FOR_INSN (XEXP (new_rtx
, 0));
1627 /* Don't bypass edges containing instructions. */
1628 edest
= find_edge (bb
, dest
);
1629 if (edest
&& edest
->insns
.r
)
1635 /* Avoid unification of the edge with other edges from original
1636 branch. We would end up emitting the instruction on "both"
1638 if (dest
&& setcc
&& !CC0_P (SET_DEST (PATTERN (setcc
)))
1639 && find_edge (e
->src
, dest
))
1645 && dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1647 redirect_edge_and_branch_force (e
, dest
);
1649 /* Copy the register setter to the redirected edge.
1650 Don't copy CC0 setters, as CC0 is dead after jump. */
1653 rtx pat
= PATTERN (setcc
);
1654 if (!CC0_P (SET_DEST (pat
)))
1655 insert_insn_on_edge (copy_insn (pat
), e
);
1658 if (dump_file
!= NULL
)
1660 fprintf (dump_file
, "JUMP-BYPASS: Proved reg %d "
1661 "in jump_insn %d equals constant ",
1662 regno
, INSN_UID (jump
));
1663 print_rtl (dump_file
, set
->src
);
1664 fprintf (dump_file
, "\n\t when BB %d is entered from "
1665 "BB %d. Redirect edge %d->%d to %d.\n",
1666 old_dest
->index
, e
->src
->index
, e
->src
->index
,
1667 old_dest
->index
, dest
->index
);
1680 /* Find basic blocks with more than one predecessor that only contain a
1681 single conditional jump. If the result of the comparison is known at
1682 compile-time from any incoming edge, redirect that edge to the
1683 appropriate target. Return nonzero if a change was made.
1685 This function is now mis-named, because we also handle indirect jumps. */
1688 bypass_conditional_jumps (void)
1696 /* Note we start at block 1. */
1697 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1700 bypass_last_basic_block
= last_basic_block_for_fn (cfun
);
1701 mark_dfs_back_edges ();
1704 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
->next_bb
,
1705 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1707 /* Check for more than one predecessor. */
1708 if (!single_pred_p (bb
))
1711 FOR_BB_INSNS (bb
, insn
)
1712 if (DEBUG_INSN_P (insn
))
1714 else if (NONJUMP_INSN_P (insn
))
1718 if (GET_CODE (PATTERN (insn
)) != SET
)
1721 dest
= SET_DEST (PATTERN (insn
));
1722 if (REG_P (dest
) || CC0_P (dest
))
1727 else if (JUMP_P (insn
))
1729 if ((any_condjump_p (insn
) || computed_jump_p (insn
))
1730 && onlyjump_p (insn
))
1731 changed
|= bypass_block (bb
, setcc
, insn
);
1734 else if (INSN_P (insn
))
1739 /* If we bypassed any register setting insns, we inserted a
1740 copy on the redirected edge. These need to be committed. */
1742 commit_edge_insertions ();
1747 /* Return true if the graph is too expensive to optimize. PASS is the
1748 optimization about to be performed. */
1751 is_too_expensive (const char *pass
)
1753 /* Trying to perform global optimizations on flow graphs which have
1754 a high connectivity will take a long time and is unlikely to be
1755 particularly useful.
1757 In normal circumstances a cfg should have about twice as many
1758 edges as blocks. But we do not want to punish small functions
1759 which have a couple switch statements. Rather than simply
1760 threshold the number of blocks, uses something with a more
1761 graceful degradation. */
1762 if (n_edges_for_fn (cfun
) > 20000 + n_basic_blocks_for_fn (cfun
) * 4)
1764 warning (OPT_Wdisabled_optimization
,
1765 "%s: %d basic blocks and %d edges/basic block",
1766 pass
, n_basic_blocks_for_fn (cfun
),
1767 n_edges_for_fn (cfun
) / n_basic_blocks_for_fn (cfun
));
1772 /* If allocating memory for the cprop bitmap would take up too much
1773 storage it's better just to disable the optimization. */
1774 if ((n_basic_blocks_for_fn (cfun
)
1775 * SBITMAP_SET_SIZE (max_reg_num ())
1776 * sizeof (SBITMAP_ELT_TYPE
)) > MAX_GCSE_MEMORY
)
1778 warning (OPT_Wdisabled_optimization
,
1779 "%s: %d basic blocks and %d registers",
1780 pass
, n_basic_blocks_for_fn (cfun
), max_reg_num ());
1788 /* Main function for the CPROP pass. */
1791 one_cprop_pass (void)
1796 /* Return if there's nothing to do, or it is too expensive. */
1797 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1
1798 || is_too_expensive (_ ("const/copy propagation disabled")))
1801 global_const_prop_count
= local_const_prop_count
= 0;
1802 global_copy_prop_count
= local_copy_prop_count
= 0;
1805 gcc_obstack_init (&cprop_obstack
);
1807 /* Do a local const/copy propagation pass first. The global pass
1808 only handles global opportunities.
1809 If the local pass changes something, remove any unreachable blocks
1810 because the CPROP global dataflow analysis may get into infinite
1811 loops for CFGs with unreachable blocks.
1813 FIXME: This local pass should not be necessary after CSE (but for
1814 some reason it still is). It is also (proven) not necessary
1815 to run the local pass right after FWPWOP.
1817 FIXME: The global analysis would not get into infinite loops if it
1818 would use the DF solver (via df_simple_dataflow) instead of
1819 the solver implemented in this file. */
1820 changed
|= local_cprop_pass ();
1822 delete_unreachable_blocks ();
1824 /* Determine implicit sets. This may change the CFG (split critical
1825 edges if that exposes an implicit set).
1826 Note that find_implicit_sets() does not rely on up-to-date DF caches
1827 so that we do not have to re-run df_analyze() even if local CPROP
1829 ??? This could run earlier so that any uncovered implicit sets
1830 sets could be exploited in local_cprop_pass() also. Later. */
1831 changed
|= find_implicit_sets ();
1833 /* If local_cprop_pass() or find_implicit_sets() changed something,
1834 run df_analyze() to bring all insn caches up-to-date, and to take
1835 new basic blocks from edge splitting on the DF radar.
1836 NB: This also runs the fast DCE pass, because execute_rtl_cprop
1837 sets DF_LR_RUN_DCE. */
1841 /* Initialize implicit_set_indexes array. */
1842 implicit_set_indexes
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1843 for (i
= 0; i
< last_basic_block_for_fn (cfun
); i
++)
1844 implicit_set_indexes
[i
] = -1;
1846 alloc_hash_table (&set_hash_table
);
1847 compute_hash_table (&set_hash_table
);
1849 /* Free implicit_sets before peak usage. */
1850 free (implicit_sets
);
1851 implicit_sets
= NULL
;
1854 dump_hash_table (dump_file
, "SET", &set_hash_table
);
1855 if (set_hash_table
.n_elems
> 0)
1860 alloc_cprop_mem (last_basic_block_for_fn (cfun
),
1861 set_hash_table
.n_elems
);
1862 compute_cprop_data ();
1864 free (implicit_set_indexes
);
1865 implicit_set_indexes
= NULL
;
1867 /* Allocate vars to track sets of regs. */
1868 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
1870 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
->next_bb
,
1871 EXIT_BLOCK_PTR_FOR_FN (cfun
),
1874 /* Reset tables used to keep track of what's still valid [since
1875 the start of the block]. */
1876 reset_opr_set_tables ();
1878 FOR_BB_INSNS (bb
, insn
)
1881 changed
|= cprop_insn (insn
);
1883 /* Keep track of everything modified by this insn. */
1884 /* ??? Need to be careful w.r.t. mods done to INSN.
1885 Don't call mark_oprs_set if we turned the
1886 insn into a NOTE, or deleted the insn. */
1887 if (! NOTE_P (insn
) && ! insn
->deleted ())
1888 mark_oprs_set (insn
);
1892 changed
|= bypass_conditional_jumps ();
1894 FREE_REG_SET (reg_set_bitmap
);
1899 free (implicit_set_indexes
);
1900 implicit_set_indexes
= NULL
;
1903 free_hash_table (&set_hash_table
);
1904 obstack_free (&cprop_obstack
, NULL
);
1908 fprintf (dump_file
, "CPROP of %s, %d basic blocks, %d bytes needed, ",
1909 current_function_name (), n_basic_blocks_for_fn (cfun
),
1911 fprintf (dump_file
, "%d local const props, %d local copy props, ",
1912 local_const_prop_count
, local_copy_prop_count
);
1913 fprintf (dump_file
, "%d global const props, %d global copy props\n\n",
1914 global_const_prop_count
, global_copy_prop_count
);
1920 /* All the passes implemented in this file. Each pass has its
1921 own gate and execute function, and at the end of the file a
1922 pass definition for passes.c.
1924 We do not construct an accurate cfg in functions which call
1925 setjmp, so none of these passes runs if the function calls
1927 FIXME: Should just handle setjmp via REG_SETJMP notes. */
1930 execute_rtl_cprop (void)
1933 delete_unreachable_blocks ();
1934 df_set_flags (DF_LR_RUN_DCE
);
1936 changed
= one_cprop_pass ();
1937 flag_rerun_cse_after_global_opts
|= changed
;
1939 cleanup_cfg (CLEANUP_CFG_CHANGED
);
1945 const pass_data pass_data_rtl_cprop
=
1947 RTL_PASS
, /* type */
1949 OPTGROUP_NONE
, /* optinfo_flags */
1950 TV_CPROP
, /* tv_id */
1951 PROP_cfglayout
, /* properties_required */
1952 0, /* properties_provided */
1953 0, /* properties_destroyed */
1954 0, /* todo_flags_start */
1955 TODO_df_finish
, /* todo_flags_finish */
1958 class pass_rtl_cprop
: public rtl_opt_pass
1961 pass_rtl_cprop (gcc::context
*ctxt
)
1962 : rtl_opt_pass (pass_data_rtl_cprop
, ctxt
)
1965 /* opt_pass methods: */
1966 opt_pass
* clone () { return new pass_rtl_cprop (m_ctxt
); }
1967 virtual bool gate (function
*fun
)
1969 return optimize
> 0 && flag_gcse
1970 && !fun
->calls_setjmp
1974 virtual unsigned int execute (function
*) { return execute_rtl_cprop (); }
1976 }; // class pass_rtl_cprop
1981 make_pass_rtl_cprop (gcc::context
*ctxt
)
1983 return new pass_rtl_cprop (ctxt
);