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"
24 #include "diagnostic-core.h"
33 #include "hard-reg-set.h"
35 #include "insn-config.h"
39 #include "dominance.h"
44 #include "cfgcleanup.h"
45 #include "basic-block.h"
56 #include "alloc-pool.h"
60 #include "tree-pass.h"
67 /* An obstack for our working variables. */
68 static struct obstack cprop_obstack
;
70 /* Occurrence of an expression.
71 There is one per basic block. If a pattern appears more than once the
72 last appearance is used. */
76 /* Next occurrence of this expression. */
77 struct cprop_occr
*next
;
78 /* The insn that computes the expression. */
82 typedef struct cprop_occr
*occr_t
;
84 /* Hash table entry for assignment expressions. */
88 /* The expression (DEST := SRC). */
92 /* Index in the available expression bitmaps. */
94 /* Next entry with the same hash. */
95 struct cprop_expr
*next_same_hash
;
96 /* List of available occurrence in basic blocks in the function.
97 An "available occurrence" is one that is the last occurrence in the
98 basic block and whose operands are not modified by following statements
99 in the basic block [including this insn]. */
100 struct cprop_occr
*avail_occr
;
103 /* Hash table for copy propagation expressions.
104 Each hash table is an array of buckets.
105 ??? It is known that if it were an array of entries, structure elements
106 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
107 not clear whether in the final analysis a sufficient amount of memory would
108 be saved as the size of the available expression bitmaps would be larger
109 [one could build a mapping table without holes afterwards though].
110 Someday I'll perform the computation and figure it out. */
115 This is an array of `set_hash_table_size' elements. */
116 struct cprop_expr
**table
;
118 /* Size of the hash table, in elements. */
121 /* Number of hash table elements. */
122 unsigned int n_elems
;
125 /* Copy propagation hash table. */
126 static struct hash_table_d set_hash_table
;
128 /* Array of implicit set patterns indexed by basic block index. */
129 static rtx
*implicit_sets
;
131 /* Array of indexes of expressions for implicit set patterns indexed by basic
132 block index. In other words, implicit_set_indexes[i] is the bitmap_index
133 of the expression whose RTX is implicit_sets[i]. */
134 static int *implicit_set_indexes
;
136 /* Bitmap containing one bit for each register in the program.
137 Used when performing GCSE to track which registers have been set since
138 the start or end of the basic block while traversing that block. */
139 static regset reg_set_bitmap
;
141 /* Various variables for statistics gathering. */
143 /* Memory used in a pass.
144 This isn't intended to be absolutely precise. Its intent is only
145 to keep an eye on memory usage. */
146 static int bytes_used
;
148 /* Number of local constants propagated. */
149 static int local_const_prop_count
;
150 /* Number of local copies propagated. */
151 static int local_copy_prop_count
;
152 /* Number of global constants propagated. */
153 static int global_const_prop_count
;
154 /* Number of global copies propagated. */
155 static int global_copy_prop_count
;
157 #define GOBNEW(T) ((T *) cprop_alloc (sizeof (T)))
158 #define GOBNEWVAR(T, S) ((T *) cprop_alloc ((S)))
160 /* Cover function to obstack_alloc. */
163 cprop_alloc (unsigned long size
)
166 return obstack_alloc (&cprop_obstack
, size
);
169 /* Return nonzero if register X is unchanged from INSN to the end
170 of INSN's basic block. */
173 reg_available_p (const_rtx x
, const rtx_insn
*insn ATTRIBUTE_UNUSED
)
175 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
178 /* Hash a set of register REGNO.
180 Sets are hashed on the register that is set. This simplifies the PRE copy
183 ??? May need to make things more elaborate. Later, as necessary. */
186 hash_mod (int regno
, int hash_table_size
)
188 return (unsigned) regno
% hash_table_size
;
191 /* Insert assignment DEST:=SET from INSN in the hash table.
192 DEST is a register and SET is a register or a suitable constant.
193 If the assignment is already present in the table, record it as
194 the last occurrence in INSN's basic block.
195 IMPLICIT is true if it's an implicit set, false otherwise. */
198 insert_set_in_table (rtx dest
, rtx src
, rtx_insn
*insn
,
199 struct hash_table_d
*table
, bool implicit
)
203 struct cprop_expr
*cur_expr
, *last_expr
= NULL
;
204 struct cprop_occr
*cur_occr
;
206 hash
= hash_mod (REGNO (dest
), table
->size
);
208 for (cur_expr
= table
->table
[hash
]; cur_expr
;
209 cur_expr
= cur_expr
->next_same_hash
)
211 if (dest
== cur_expr
->dest
212 && src
== cur_expr
->src
)
217 last_expr
= cur_expr
;
222 cur_expr
= GOBNEW (struct cprop_expr
);
223 bytes_used
+= sizeof (struct cprop_expr
);
224 if (table
->table
[hash
] == NULL
)
225 /* This is the first pattern that hashed to this index. */
226 table
->table
[hash
] = cur_expr
;
228 /* Add EXPR to end of this hash chain. */
229 last_expr
->next_same_hash
= cur_expr
;
231 /* Set the fields of the expr element.
232 We must copy X because it can be modified when copy propagation is
233 performed on its operands. */
234 cur_expr
->dest
= copy_rtx (dest
);
235 cur_expr
->src
= copy_rtx (src
);
236 cur_expr
->bitmap_index
= table
->n_elems
++;
237 cur_expr
->next_same_hash
= NULL
;
238 cur_expr
->avail_occr
= NULL
;
241 /* Now record the occurrence. */
242 cur_occr
= cur_expr
->avail_occr
;
245 && BLOCK_FOR_INSN (cur_occr
->insn
) == BLOCK_FOR_INSN (insn
))
247 /* Found another instance of the expression in the same basic block.
248 Prefer this occurrence to the currently recorded one. We want
249 the last one in the block and the block is scanned from start
251 cur_occr
->insn
= insn
;
255 /* First occurrence of this expression in this basic block. */
256 cur_occr
= GOBNEW (struct cprop_occr
);
257 bytes_used
+= sizeof (struct cprop_occr
);
258 cur_occr
->insn
= insn
;
259 cur_occr
->next
= cur_expr
->avail_occr
;
260 cur_expr
->avail_occr
= cur_occr
;
263 /* Record bitmap_index of the implicit set in implicit_set_indexes. */
265 implicit_set_indexes
[BLOCK_FOR_INSN (insn
)->index
]
266 = cur_expr
->bitmap_index
;
269 /* Determine whether the rtx X should be treated as a constant for CPROP.
270 Since X might be inserted more than once we have to take care that it
274 cprop_constant_p (const_rtx x
)
276 return CONSTANT_P (x
) && (GET_CODE (x
) != CONST
|| shared_const_p (x
));
279 /* Determine whether the rtx X should be treated as a register that can
280 be propagated. Any pseudo-register is fine. */
283 cprop_reg_p (const_rtx x
)
285 return REG_P (x
) && !HARD_REGISTER_P (x
);
288 /* Scan SET present in INSN and add an entry to the hash TABLE.
289 IMPLICIT is true if it's an implicit set, false otherwise. */
292 hash_scan_set (rtx set
, rtx_insn
*insn
, struct hash_table_d
*table
,
295 rtx src
= SET_SRC (set
);
296 rtx dest
= SET_DEST (set
);
298 if (cprop_reg_p (dest
)
299 && reg_available_p (dest
, insn
)
300 && can_copy_p (GET_MODE (dest
)))
302 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
304 This allows us to do a single CPROP pass and still eliminate
305 redundant constants, addresses or other expressions that are
306 constructed with multiple instructions.
308 However, keep the original SRC if INSN is a simple reg-reg move. In
309 In this case, there will almost always be a REG_EQUAL note on the
310 insn that sets SRC. By recording the REG_EQUAL value here as SRC
311 for INSN, we miss copy propagation opportunities.
313 Note that this does not impede profitable constant propagations. We
314 "look through" reg-reg sets in lookup_set. */
315 rtx note
= find_reg_equal_equiv_note (insn
);
317 && REG_NOTE_KIND (note
) == REG_EQUAL
319 && cprop_constant_p (XEXP (note
, 0)))
320 src
= XEXP (note
, 0), set
= gen_rtx_SET (dest
, src
);
322 /* Record sets for constant/copy propagation. */
323 if ((cprop_reg_p (src
)
325 && reg_available_p (src
, insn
))
326 || cprop_constant_p (src
))
327 insert_set_in_table (dest
, src
, insn
, table
, implicit
);
331 /* Process INSN and add hash table entries as appropriate. */
334 hash_scan_insn (rtx_insn
*insn
, struct hash_table_d
*table
)
336 rtx pat
= PATTERN (insn
);
339 /* Pick out the sets of INSN and for other forms of instructions record
340 what's been modified. */
342 if (GET_CODE (pat
) == SET
)
343 hash_scan_set (pat
, insn
, table
, false);
344 else if (GET_CODE (pat
) == PARALLEL
)
345 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
347 rtx x
= XVECEXP (pat
, 0, i
);
349 if (GET_CODE (x
) == SET
)
350 hash_scan_set (x
, insn
, table
, false);
354 /* Dump the hash table TABLE to file FILE under the name NAME. */
357 dump_hash_table (FILE *file
, const char *name
, struct hash_table_d
*table
)
360 /* Flattened out table, so it's printed in proper order. */
361 struct cprop_expr
**flat_table
;
362 unsigned int *hash_val
;
363 struct cprop_expr
*expr
;
365 flat_table
= XCNEWVEC (struct cprop_expr
*, table
->n_elems
);
366 hash_val
= XNEWVEC (unsigned int, table
->n_elems
);
368 for (i
= 0; i
< (int) table
->size
; i
++)
369 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
371 flat_table
[expr
->bitmap_index
] = expr
;
372 hash_val
[expr
->bitmap_index
] = i
;
375 fprintf (file
, "%s hash table (%d buckets, %d entries)\n",
376 name
, table
->size
, table
->n_elems
);
378 for (i
= 0; i
< (int) table
->n_elems
; i
++)
379 if (flat_table
[i
] != 0)
381 expr
= flat_table
[i
];
382 fprintf (file
, "Index %d (hash value %d)\n ",
383 expr
->bitmap_index
, hash_val
[i
]);
384 print_rtl (file
, expr
->dest
);
385 fprintf (file
, " := ");
386 print_rtl (file
, expr
->src
);
387 fprintf (file
, "\n");
390 fprintf (file
, "\n");
396 /* Record as unavailable all registers that are DEF operands of INSN. */
399 make_set_regs_unavailable (rtx_insn
*insn
)
403 FOR_EACH_INSN_DEF (def
, insn
)
404 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (def
));
407 /* Top level function to create an assignment hash table.
409 Assignment entries are placed in the hash table if
410 - they are of the form (set (pseudo-reg) src),
411 - src is something we want to perform const/copy propagation on,
412 - none of the operands or target are subsequently modified in the block
414 Currently src must be a pseudo-reg or a const_int.
416 TABLE is the table computed. */
419 compute_hash_table_work (struct hash_table_d
*table
)
423 /* Allocate vars to track sets of regs. */
424 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
426 FOR_EACH_BB_FN (bb
, cfun
)
430 /* Reset tables used to keep track of what's not yet invalid [since
431 the end of the block]. */
432 CLEAR_REG_SET (reg_set_bitmap
);
434 /* Go over all insns from the last to the first. This is convenient
435 for tracking available registers, i.e. not set between INSN and
436 the end of the basic block BB. */
437 FOR_BB_INSNS_REVERSE (bb
, insn
)
439 /* Only real insns are interesting. */
440 if (!NONDEBUG_INSN_P (insn
))
443 /* Record interesting sets from INSN in the hash table. */
444 hash_scan_insn (insn
, table
);
446 /* Any registers set in INSN will make SETs above it not AVAIL. */
447 make_set_regs_unavailable (insn
);
450 /* Insert implicit sets in the hash table, pretending they appear as
451 insns at the head of the basic block. */
452 if (implicit_sets
[bb
->index
] != NULL_RTX
)
453 hash_scan_set (implicit_sets
[bb
->index
], BB_HEAD (bb
), table
, true);
456 FREE_REG_SET (reg_set_bitmap
);
459 /* Allocate space for the set/expr hash TABLE.
460 It is used to determine the number of buckets to use. */
463 alloc_hash_table (struct hash_table_d
*table
)
467 n
= get_max_insn_count ();
470 if (table
->size
< 11)
473 /* Attempt to maintain efficient use of hash table.
474 Making it an odd number is simplest for now.
475 ??? Later take some measurements. */
477 n
= table
->size
* sizeof (struct cprop_expr
*);
478 table
->table
= XNEWVAR (struct cprop_expr
*, n
);
481 /* Free things allocated by alloc_hash_table. */
484 free_hash_table (struct hash_table_d
*table
)
489 /* Compute the hash TABLE for doing copy/const propagation or
490 expression hash table. */
493 compute_hash_table (struct hash_table_d
*table
)
495 /* Initialize count of number of entries in hash table. */
497 memset (table
->table
, 0, table
->size
* sizeof (struct cprop_expr
*));
499 compute_hash_table_work (table
);
502 /* Expression tracking support. */
504 /* Lookup REGNO in the set TABLE. The result is a pointer to the
505 table entry, or NULL if not found. */
507 static struct cprop_expr
*
508 lookup_set (unsigned int regno
, struct hash_table_d
*table
)
510 unsigned int hash
= hash_mod (regno
, table
->size
);
511 struct cprop_expr
*expr
;
513 expr
= table
->table
[hash
];
515 while (expr
&& REGNO (expr
->dest
) != regno
)
516 expr
= expr
->next_same_hash
;
521 /* Return the next entry for REGNO in list EXPR. */
523 static struct cprop_expr
*
524 next_set (unsigned int regno
, struct cprop_expr
*expr
)
527 expr
= expr
->next_same_hash
;
528 while (expr
&& REGNO (expr
->dest
) != regno
);
533 /* Reset tables used to keep track of what's still available [since the
534 start of the block]. */
537 reset_opr_set_tables (void)
539 /* Maintain a bitmap of which regs have been set since beginning of
541 CLEAR_REG_SET (reg_set_bitmap
);
544 /* Return nonzero if the register X has not been set yet [since the
545 start of the basic block containing INSN]. */
548 reg_not_set_p (const_rtx x
, const rtx_insn
*insn ATTRIBUTE_UNUSED
)
550 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
553 /* Record things set by INSN.
554 This data is used by reg_not_set_p. */
557 mark_oprs_set (rtx_insn
*insn
)
561 FOR_EACH_INSN_DEF (def
, insn
)
562 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (def
));
565 /* Compute copy/constant propagation working variables. */
567 /* Local properties of assignments. */
568 static sbitmap
*cprop_avloc
;
569 static sbitmap
*cprop_kill
;
571 /* Global properties of assignments (computed from the local properties). */
572 static sbitmap
*cprop_avin
;
573 static sbitmap
*cprop_avout
;
575 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
576 basic blocks. N_SETS is the number of sets. */
579 alloc_cprop_mem (int n_blocks
, int n_sets
)
581 cprop_avloc
= sbitmap_vector_alloc (n_blocks
, n_sets
);
582 cprop_kill
= sbitmap_vector_alloc (n_blocks
, n_sets
);
584 cprop_avin
= sbitmap_vector_alloc (n_blocks
, n_sets
);
585 cprop_avout
= sbitmap_vector_alloc (n_blocks
, n_sets
);
588 /* Free vars used by copy/const propagation. */
591 free_cprop_mem (void)
593 sbitmap_vector_free (cprop_avloc
);
594 sbitmap_vector_free (cprop_kill
);
595 sbitmap_vector_free (cprop_avin
);
596 sbitmap_vector_free (cprop_avout
);
599 /* Compute the local properties of each recorded expression.
601 Local properties are those that are defined by the block, irrespective of
604 An expression is killed in a block if its operands, either DEST or SRC, are
605 modified in the block.
607 An expression is computed (locally available) in a block if it is computed
608 at least once and expression would contain the same value if the
609 computation was moved to the end of the block.
611 KILL and COMP are destination sbitmaps for recording local properties. */
614 compute_local_properties (sbitmap
*kill
, sbitmap
*comp
,
615 struct hash_table_d
*table
)
619 /* Initialize the bitmaps that were passed in. */
620 bitmap_vector_clear (kill
, last_basic_block_for_fn (cfun
));
621 bitmap_vector_clear (comp
, last_basic_block_for_fn (cfun
));
623 for (i
= 0; i
< table
->size
; i
++)
625 struct cprop_expr
*expr
;
627 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
629 int indx
= expr
->bitmap_index
;
631 struct cprop_occr
*occr
;
633 /* For each definition of the destination pseudo-reg, the expression
634 is killed in the block where the definition is. */
635 for (def
= DF_REG_DEF_CHAIN (REGNO (expr
->dest
));
636 def
; def
= DF_REF_NEXT_REG (def
))
637 bitmap_set_bit (kill
[DF_REF_BB (def
)->index
], indx
);
639 /* If the source is a pseudo-reg, for each definition of the source,
640 the expression is killed in the block where the definition is. */
641 if (REG_P (expr
->src
))
642 for (def
= DF_REG_DEF_CHAIN (REGNO (expr
->src
));
643 def
; def
= DF_REF_NEXT_REG (def
))
644 bitmap_set_bit (kill
[DF_REF_BB (def
)->index
], indx
);
646 /* The occurrences recorded in avail_occr are exactly those that
647 are locally available in the block where they are. */
648 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
650 bitmap_set_bit (comp
[BLOCK_FOR_INSN (occr
->insn
)->index
], indx
);
656 /* Hash table support. */
658 /* Top level routine to do the dataflow analysis needed by copy/const
662 compute_cprop_data (void)
666 compute_local_properties (cprop_kill
, cprop_avloc
, &set_hash_table
);
667 compute_available (cprop_avloc
, cprop_kill
, cprop_avout
, cprop_avin
);
669 /* Merge implicit sets into CPROP_AVIN. They are always available at the
670 entry of their basic block. We need to do this because 1) implicit sets
671 aren't recorded for the local pass so they cannot be propagated within
672 their basic block by this pass and 2) the global pass would otherwise
673 propagate them only in the successors of their basic block. */
674 FOR_EACH_BB_FN (bb
, cfun
)
676 int index
= implicit_set_indexes
[bb
->index
];
678 bitmap_set_bit (cprop_avin
[bb
->index
], index
);
682 /* Copy/constant propagation. */
684 /* Maximum number of register uses in an insn that we handle. */
687 /* Table of uses (registers, both hard and pseudo) found in an insn.
688 Allocated statically to avoid alloc/free complexity and overhead. */
689 static rtx reg_use_table
[MAX_USES
];
691 /* Index into `reg_use_table' while building it. */
692 static unsigned reg_use_count
;
694 /* Set up a list of register numbers used in INSN. The found uses are stored
695 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
696 and contains the number of uses in the table upon exit.
698 ??? If a register appears multiple times we will record it multiple times.
699 This doesn't hurt anything but it will slow things down. */
702 find_used_regs (rtx
*xptr
, void *data ATTRIBUTE_UNUSED
)
709 /* repeat is used to turn tail-recursion into iteration since GCC
710 can't do it when there's no return value. */
718 if (reg_use_count
== MAX_USES
)
721 reg_use_table
[reg_use_count
] = x
;
725 /* Recursively scan the operands of this expression. */
727 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
731 /* If we are about to do the last recursive call
732 needed at this level, change it into iteration.
733 This function is called enough to be worth it. */
740 find_used_regs (&XEXP (x
, i
), data
);
742 else if (fmt
[i
] == 'E')
743 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
744 find_used_regs (&XVECEXP (x
, i
, j
), data
);
748 /* Try to replace all uses of FROM in INSN with TO.
749 Return nonzero if successful. */
752 try_replace_reg (rtx from
, rtx to
, rtx_insn
*insn
)
754 rtx note
= find_reg_equal_equiv_note (insn
);
757 rtx set
= single_set (insn
);
759 bool check_rtx_costs
= true;
760 bool speed
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn
));
761 int old_cost
= set
? set_rtx_cost (set
, speed
) : 0;
764 && REG_NOTE_KIND (note
) == REG_EQUAL
765 && (GET_CODE (XEXP (note
, 0)) == CONST
766 || CONSTANT_P (XEXP (note
, 0))))
767 || (set
&& CONSTANT_P (SET_SRC (set
))))
768 check_rtx_costs
= false;
770 /* Usually we substitute easy stuff, so we won't copy everything.
771 We however need to take care to not duplicate non-trivial CONST
775 validate_replace_src_group (from
, to
, insn
);
777 /* If TO is a constant, check the cost of the set after propagation
778 to the cost of the set before the propagation. If the cost is
779 higher, then do not replace FROM with TO. */
783 && (set_rtx_cost (set
, speed
) > old_cost
))
790 if (num_changes_pending () && apply_change_group ())
793 /* Try to simplify SET_SRC if we have substituted a constant. */
794 if (success
&& set
&& CONSTANT_P (to
))
796 src
= simplify_rtx (SET_SRC (set
));
799 validate_change (insn
, &SET_SRC (set
), src
, 0);
802 /* If there is already a REG_EQUAL note, update the expression in it
803 with our replacement. */
804 if (note
!= 0 && REG_NOTE_KIND (note
) == REG_EQUAL
)
805 set_unique_reg_note (insn
, REG_EQUAL
,
806 simplify_replace_rtx (XEXP (note
, 0), from
, to
));
807 if (!success
&& set
&& reg_mentioned_p (from
, SET_SRC (set
)))
809 /* If above failed and this is a single set, try to simplify the source
810 of the set given our substitution. We could perhaps try this for
811 multiple SETs, but it probably won't buy us anything. */
812 src
= simplify_replace_rtx (SET_SRC (set
), from
, to
);
814 if (!rtx_equal_p (src
, SET_SRC (set
))
815 && validate_change (insn
, &SET_SRC (set
), src
, 0))
818 /* If we've failed perform the replacement, have a single SET to
819 a REG destination and don't yet have a note, add a REG_EQUAL note
820 to not lose information. */
821 if (!success
&& note
== 0 && set
!= 0 && REG_P (SET_DEST (set
)))
822 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
825 if (set
&& MEM_P (SET_DEST (set
)) && reg_mentioned_p (from
, SET_DEST (set
)))
827 /* Registers can also appear as uses in SET_DEST if it is a MEM.
828 We could perhaps try this for multiple SETs, but it probably
829 won't buy us anything. */
830 rtx dest
= simplify_replace_rtx (SET_DEST (set
), from
, to
);
832 if (!rtx_equal_p (dest
, SET_DEST (set
))
833 && validate_change (insn
, &SET_DEST (set
), dest
, 0))
837 /* REG_EQUAL may get simplified into register.
838 We don't allow that. Remove that note. This code ought
839 not to happen, because previous code ought to synthesize
840 reg-reg move, but be on the safe side. */
841 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
&& REG_P (XEXP (note
, 0)))
842 remove_note (insn
, note
);
847 /* Find a set of REGNOs that are available on entry to INSN's block. If found,
848 SET_RET[0] will be assigned a set with a register source and SET_RET[1] a
849 set with a constant source. If not found the corresponding entry is set to
853 find_avail_set (int regno
, rtx_insn
*insn
, struct cprop_expr
*set_ret
[2])
855 set_ret
[0] = set_ret
[1] = NULL
;
857 /* Loops are not possible here. To get a loop we would need two sets
858 available at the start of the block containing INSN. i.e. we would
859 need two sets like this available at the start of the block:
861 (set (reg X) (reg Y))
862 (set (reg Y) (reg X))
864 This can not happen since the set of (reg Y) would have killed the
865 set of (reg X) making it unavailable at the start of this block. */
869 struct cprop_expr
*set
= lookup_set (regno
, &set_hash_table
);
871 /* Find a set that is available at the start of the block
872 which contains INSN. */
875 if (bitmap_bit_p (cprop_avin
[BLOCK_FOR_INSN (insn
)->index
],
878 set
= next_set (regno
, set
);
881 /* If no available set was found we've reached the end of the
882 (possibly empty) copy chain. */
888 /* We know the set is available.
889 Now check that SRC is locally anticipatable (i.e. none of the
890 source operands have changed since the start of the block).
892 If the source operand changed, we may still use it for the next
893 iteration of this loop, but we may not use it for substitutions. */
895 if (cprop_constant_p (src
))
897 else if (reg_not_set_p (src
, insn
))
900 /* If the source of the set is anything except a register, then
901 we have reached the end of the copy chain. */
905 /* Follow the copy chain, i.e. start another iteration of the loop
906 and see if we have an available copy into SRC. */
911 /* Subroutine of cprop_insn that tries to propagate constants into
912 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
913 it is the instruction that immediately precedes JUMP, and must be a
914 single SET of a register. FROM is what we will try to replace,
915 SRC is the constant we will try to substitute for it. Return nonzero
916 if a change was made. */
919 cprop_jump (basic_block bb
, rtx_insn
*setcc
, rtx_insn
*jump
, rtx from
, rtx src
)
921 rtx new_rtx
, set_src
, note_src
;
922 rtx set
= pc_set (jump
);
923 rtx note
= find_reg_equal_equiv_note (jump
);
927 note_src
= XEXP (note
, 0);
928 if (GET_CODE (note_src
) == EXPR_LIST
)
931 else note_src
= NULL_RTX
;
933 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
934 set_src
= note_src
? note_src
: SET_SRC (set
);
936 /* First substitute the SETCC condition into the JUMP instruction,
937 then substitute that given values into this expanded JUMP. */
938 if (setcc
!= NULL_RTX
939 && !modified_between_p (from
, setcc
, jump
)
940 && !modified_between_p (src
, setcc
, jump
))
943 rtx setcc_set
= single_set (setcc
);
944 rtx setcc_note
= find_reg_equal_equiv_note (setcc
);
945 setcc_src
= (setcc_note
&& GET_CODE (XEXP (setcc_note
, 0)) != EXPR_LIST
)
946 ? XEXP (setcc_note
, 0) : SET_SRC (setcc_set
);
947 set_src
= simplify_replace_rtx (set_src
, SET_DEST (setcc_set
),
953 new_rtx
= simplify_replace_rtx (set_src
, from
, src
);
955 /* If no simplification can be made, then try the next register. */
956 if (rtx_equal_p (new_rtx
, SET_SRC (set
)))
959 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
960 if (new_rtx
== pc_rtx
)
964 /* Ensure the value computed inside the jump insn to be equivalent
965 to one computed by setcc. */
966 if (setcc
&& modified_in_p (new_rtx
, setcc
))
968 if (! validate_unshare_change (jump
, &SET_SRC (set
), new_rtx
, 0))
970 /* When (some) constants are not valid in a comparison, and there
971 are two registers to be replaced by constants before the entire
972 comparison can be folded into a constant, we need to keep
973 intermediate information in REG_EQUAL notes. For targets with
974 separate compare insns, such notes are added by try_replace_reg.
975 When we have a combined compare-and-branch instruction, however,
976 we need to attach a note to the branch itself to make this
977 optimization work. */
979 if (!rtx_equal_p (new_rtx
, note_src
))
980 set_unique_reg_note (jump
, REG_EQUAL
, copy_rtx (new_rtx
));
984 /* Remove REG_EQUAL note after simplification. */
986 remove_note (jump
, note
);
989 /* Delete the cc0 setter. */
990 if (HAVE_cc0
&& setcc
!= NULL
&& CC0_P (SET_DEST (single_set (setcc
))))
993 global_const_prop_count
++;
994 if (dump_file
!= NULL
)
997 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with"
998 "constant ", REGNO (from
), INSN_UID (jump
));
999 print_rtl (dump_file
, src
);
1000 fprintf (dump_file
, "\n");
1002 purge_dead_edges (bb
);
1004 /* If a conditional jump has been changed into unconditional jump, remove
1005 the jump and make the edge fallthru - this is always called in
1007 if (new_rtx
!= pc_rtx
&& simplejump_p (jump
))
1012 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1013 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1014 && BB_HEAD (e
->dest
) == JUMP_LABEL (jump
))
1016 e
->flags
|= EDGE_FALLTHRU
;
1025 /* Subroutine of cprop_insn that tries to propagate constants. FROM is what
1026 we will try to replace, SRC is the constant we will try to substitute for
1027 it and INSN is the instruction where this will be happening. */
1030 constprop_register (rtx from
, rtx src
, rtx_insn
*insn
)
1034 /* Check for reg or cc0 setting instructions followed by
1035 conditional branch instructions first. */
1036 if ((sset
= single_set (insn
)) != NULL
1038 && any_condjump_p (NEXT_INSN (insn
)) && onlyjump_p (NEXT_INSN (insn
)))
1040 rtx dest
= SET_DEST (sset
);
1041 if ((REG_P (dest
) || CC0_P (dest
))
1042 && cprop_jump (BLOCK_FOR_INSN (insn
), insn
, NEXT_INSN (insn
),
1047 /* Handle normal insns next. */
1048 if (NONJUMP_INSN_P (insn
) && try_replace_reg (from
, src
, insn
))
1051 /* Try to propagate a CONST_INT into a conditional jump.
1052 We're pretty specific about what we will handle in this
1053 code, we can extend this as necessary over time.
1055 Right now the insn in question must look like
1056 (set (pc) (if_then_else ...)) */
1057 else if (any_condjump_p (insn
) && onlyjump_p (insn
))
1058 return cprop_jump (BLOCK_FOR_INSN (insn
), NULL
, insn
, from
, src
);
1062 /* Perform constant and copy propagation on INSN.
1063 Return nonzero if a change was made. */
1066 cprop_insn (rtx_insn
*insn
)
1069 int changed
= 0, changed_this_round
;
1074 changed_this_round
= 0;
1076 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1078 /* We may win even when propagating constants into notes. */
1079 note
= find_reg_equal_equiv_note (insn
);
1081 find_used_regs (&XEXP (note
, 0), NULL
);
1083 for (i
= 0; i
< reg_use_count
; i
++)
1085 rtx reg_used
= reg_use_table
[i
];
1086 unsigned int regno
= REGNO (reg_used
);
1087 rtx src_cst
= NULL
, src_reg
= NULL
;
1088 struct cprop_expr
*set
[2];
1090 /* If the register has already been set in this block, there's
1091 nothing we can do. */
1092 if (! reg_not_set_p (reg_used
, insn
))
1095 /* Find an assignment that sets reg_used and is available
1096 at the start of the block. */
1097 find_avail_set (regno
, insn
, set
);
1099 src_reg
= set
[0]->src
;
1101 src_cst
= set
[1]->src
;
1103 /* Constant propagation. */
1104 if (src_cst
&& cprop_constant_p (src_cst
)
1105 && constprop_register (reg_used
, src_cst
, insn
))
1107 changed_this_round
= changed
= 1;
1108 global_const_prop_count
++;
1109 if (dump_file
!= NULL
)
1112 "GLOBAL CONST-PROP: Replacing reg %d in ", regno
);
1113 fprintf (dump_file
, "insn %d with constant ",
1115 print_rtl (dump_file
, src_cst
);
1116 fprintf (dump_file
, "\n");
1118 if (insn
->deleted ())
1121 /* Copy propagation. */
1122 else if (src_reg
&& cprop_reg_p (src_reg
)
1123 && REGNO (src_reg
) != regno
1124 && try_replace_reg (reg_used
, src_reg
, insn
))
1126 changed_this_round
= changed
= 1;
1127 global_copy_prop_count
++;
1128 if (dump_file
!= NULL
)
1131 "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1132 regno
, INSN_UID (insn
));
1133 fprintf (dump_file
, " with reg %d\n", REGNO (src_reg
));
1136 /* The original insn setting reg_used may or may not now be
1137 deletable. We leave the deletion to DCE. */
1138 /* FIXME: If it turns out that the insn isn't deletable,
1139 then we may have unnecessarily extended register lifetimes
1140 and made things worse. */
1144 /* If try_replace_reg simplified the insn, the regs found by find_used_regs
1145 may not be valid anymore. Start over. */
1146 while (changed_this_round
);
1148 if (changed
&& DEBUG_INSN_P (insn
))
1154 /* Like find_used_regs, but avoid recording uses that appear in
1155 input-output contexts such as zero_extract or pre_dec. This
1156 restricts the cases we consider to those for which local cprop
1157 can legitimately make replacements. */
1160 local_cprop_find_used_regs (rtx
*xptr
, void *data
)
1167 switch (GET_CODE (x
))
1171 case STRICT_LOW_PART
:
1180 /* Can only legitimately appear this early in the context of
1181 stack pushes for function arguments, but handle all of the
1182 codes nonetheless. */
1186 /* Setting a subreg of a register larger than word_mode leaves
1187 the non-written words unchanged. */
1188 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x
))) > BITS_PER_WORD
)
1196 find_used_regs (xptr
, data
);
1199 /* Try to perform local const/copy propagation on X in INSN. */
1202 do_local_cprop (rtx x
, rtx_insn
*insn
)
1204 rtx newreg
= NULL
, newcnst
= NULL
;
1206 /* Rule out USE instructions and ASM statements as we don't want to
1207 change the hard registers mentioned. */
1210 || (GET_CODE (PATTERN (insn
)) != USE
1211 && asm_noperands (PATTERN (insn
)) < 0)))
1213 cselib_val
*val
= cselib_lookup (x
, GET_MODE (x
), 0, VOIDmode
);
1214 struct elt_loc_list
*l
;
1218 for (l
= val
->locs
; l
; l
= l
->next
)
1220 rtx this_rtx
= l
->loc
;
1223 if (cprop_constant_p (this_rtx
))
1225 if (cprop_reg_p (this_rtx
)
1226 /* Don't copy propagate if it has attached REG_EQUIV note.
1227 At this point this only function parameters should have
1228 REG_EQUIV notes and if the argument slot is used somewhere
1229 explicitly, it means address of parameter has been taken,
1230 so we should not extend the lifetime of the pseudo. */
1231 && (!(note
= find_reg_note (l
->setting_insn
, REG_EQUIV
, NULL_RTX
))
1232 || ! MEM_P (XEXP (note
, 0))))
1235 if (newcnst
&& constprop_register (x
, newcnst
, insn
))
1237 if (dump_file
!= NULL
)
1239 fprintf (dump_file
, "LOCAL CONST-PROP: Replacing reg %d in ",
1241 fprintf (dump_file
, "insn %d with constant ",
1243 print_rtl (dump_file
, newcnst
);
1244 fprintf (dump_file
, "\n");
1246 local_const_prop_count
++;
1249 else if (newreg
&& newreg
!= x
&& try_replace_reg (x
, newreg
, insn
))
1251 if (dump_file
!= NULL
)
1254 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1255 REGNO (x
), INSN_UID (insn
));
1256 fprintf (dump_file
, " with reg %d\n", REGNO (newreg
));
1258 local_copy_prop_count
++;
1265 /* Do local const/copy propagation (i.e. within each basic block). */
1268 local_cprop_pass (void)
1272 bool changed
= false;
1276 FOR_EACH_BB_FN (bb
, cfun
)
1278 FOR_BB_INSNS (bb
, insn
)
1282 rtx note
= find_reg_equal_equiv_note (insn
);
1286 note_uses (&PATTERN (insn
), local_cprop_find_used_regs
,
1289 local_cprop_find_used_regs (&XEXP (note
, 0), NULL
);
1291 for (i
= 0; i
< reg_use_count
; i
++)
1293 if (do_local_cprop (reg_use_table
[i
], insn
))
1295 if (!DEBUG_INSN_P (insn
))
1300 if (insn
->deleted ())
1303 while (i
< reg_use_count
);
1305 cselib_process_insn (insn
);
1308 /* Forget everything at the end of a basic block. */
1309 cselib_clear_table ();
1317 /* Similar to get_condition, only the resulting condition must be
1318 valid at JUMP, instead of at EARLIEST.
1320 This differs from noce_get_condition in ifcvt.c in that we prefer not to
1321 settle for the condition variable in the jump instruction being integral.
1322 We prefer to be able to record the value of a user variable, rather than
1323 the value of a temporary used in a condition. This could be solved by
1324 recording the value of *every* register scanned by canonicalize_condition,
1325 but this would require some code reorganization. */
1328 fis_get_condition (rtx_insn
*jump
)
1330 return get_condition (jump
, NULL
, false, true);
1333 /* Check the comparison COND to see if we can safely form an implicit
1337 implicit_set_cond_p (const_rtx cond
)
1342 /* COND must be either an EQ or NE comparison. */
1343 if (GET_CODE (cond
) != EQ
&& GET_CODE (cond
) != NE
)
1346 /* The first operand of COND must be a register we can propagate. */
1347 if (!cprop_reg_p (XEXP (cond
, 0)))
1350 /* The second operand of COND must be a suitable constant. */
1351 mode
= GET_MODE (XEXP (cond
, 0));
1352 cst
= XEXP (cond
, 1);
1354 /* We can't perform this optimization if either operand might be or might
1355 contain a signed zero. */
1356 if (HONOR_SIGNED_ZEROS (mode
))
1358 /* It is sufficient to check if CST is or contains a zero. We must
1359 handle float, complex, and vector. If any subpart is a zero, then
1360 the optimization can't be performed. */
1361 /* ??? The complex and vector checks are not implemented yet. We just
1362 always return zero for them. */
1363 if (CONST_DOUBLE_AS_FLOAT_P (cst
))
1366 REAL_VALUE_FROM_CONST_DOUBLE (d
, cst
);
1367 if (REAL_VALUES_EQUAL (d
, dconst0
))
1374 return cprop_constant_p (cst
);
1377 /* Find the implicit sets of a function. An "implicit set" is a constraint
1378 on the value of a variable, implied by a conditional jump. For example,
1379 following "if (x == 2)", the then branch may be optimized as though the
1380 conditional performed an "explicit set", in this example, "x = 2". This
1381 function records the set patterns that are implicit at the start of each
1384 If an implicit set is found but the set is implicit on a critical edge,
1385 this critical edge is split.
1387 Return true if the CFG was modified, false otherwise. */
1390 find_implicit_sets (void)
1392 basic_block bb
, dest
;
1394 unsigned int count
= 0;
1395 bool edges_split
= false;
1396 size_t implicit_sets_size
= last_basic_block_for_fn (cfun
) + 10;
1398 implicit_sets
= XCNEWVEC (rtx
, implicit_sets_size
);
1400 FOR_EACH_BB_FN (bb
, cfun
)
1402 /* Check for more than one successor. */
1403 if (EDGE_COUNT (bb
->succs
) <= 1)
1406 cond
= fis_get_condition (BB_END (bb
));
1408 /* If no condition is found or if it isn't of a suitable form,
1410 if (! cond
|| ! implicit_set_cond_p (cond
))
1413 dest
= GET_CODE (cond
) == EQ
1414 ? BRANCH_EDGE (bb
)->dest
: FALLTHRU_EDGE (bb
)->dest
;
1416 /* If DEST doesn't go anywhere, ignore it. */
1417 if (! dest
|| dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1420 /* We have found a suitable implicit set. Try to record it now as
1421 a SET in DEST. If DEST has more than one predecessor, the edge
1422 between BB and DEST is a critical edge and we must split it,
1423 because we can only record one implicit set per DEST basic block. */
1424 if (! single_pred_p (dest
))
1426 dest
= split_edge (find_edge (bb
, dest
));
1430 if (implicit_sets_size
<= (size_t) dest
->index
)
1432 size_t old_implicit_sets_size
= implicit_sets_size
;
1433 implicit_sets_size
*= 2;
1434 implicit_sets
= XRESIZEVEC (rtx
, implicit_sets
, implicit_sets_size
);
1435 memset (implicit_sets
+ old_implicit_sets_size
, 0,
1436 (implicit_sets_size
- old_implicit_sets_size
) * sizeof (rtx
));
1439 new_rtx
= gen_rtx_SET (XEXP (cond
, 0), XEXP (cond
, 1));
1440 implicit_sets
[dest
->index
] = new_rtx
;
1443 fprintf (dump_file
, "Implicit set of reg %d in ",
1444 REGNO (XEXP (cond
, 0)));
1445 fprintf (dump_file
, "basic block %d\n", dest
->index
);
1451 fprintf (dump_file
, "Found %d implicit sets\n", count
);
1453 /* Confess our sins. */
1457 /* Bypass conditional jumps. */
1459 /* The value of last_basic_block at the beginning of the jump_bypass
1460 pass. The use of redirect_edge_and_branch_force may introduce new
1461 basic blocks, but the data flow analysis is only valid for basic
1462 block indices less than bypass_last_basic_block. */
1464 static int bypass_last_basic_block
;
1466 /* Find a set of REGNO to a constant that is available at the end of basic
1467 block BB. Return NULL if no such set is found. Based heavily upon
1470 static struct cprop_expr
*
1471 find_bypass_set (int regno
, int bb
)
1473 struct cprop_expr
*result
= 0;
1478 struct cprop_expr
*set
= lookup_set (regno
, &set_hash_table
);
1482 if (bitmap_bit_p (cprop_avout
[bb
], set
->bitmap_index
))
1484 set
= next_set (regno
, set
);
1491 if (cprop_constant_p (src
))
1497 regno
= REGNO (src
);
1502 /* Subroutine of bypass_block that checks whether a pseudo is killed by
1503 any of the instructions inserted on an edge. Jump bypassing places
1504 condition code setters on CFG edges using insert_insn_on_edge. This
1505 function is required to check that our data flow analysis is still
1506 valid prior to commit_edge_insertions. */
1509 reg_killed_on_edge (const_rtx reg
, const_edge e
)
1513 for (insn
= e
->insns
.r
; insn
; insn
= NEXT_INSN (insn
))
1514 if (INSN_P (insn
) && reg_set_p (reg
, insn
))
1520 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1521 basic block BB which has more than one predecessor. If not NULL, SETCC
1522 is the first instruction of BB, which is immediately followed by JUMP_INSN
1523 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1524 Returns nonzero if a change was made.
1526 During the jump bypassing pass, we may place copies of SETCC instructions
1527 on CFG edges. The following routine must be careful to pay attention to
1528 these inserted insns when performing its transformations. */
1531 bypass_block (basic_block bb
, rtx_insn
*setcc
, rtx_insn
*jump
)
1537 int may_be_loop_header
= false;
1542 insn
= (setcc
!= NULL
) ? setcc
: jump
;
1544 /* Determine set of register uses in INSN. */
1546 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1547 note
= find_reg_equal_equiv_note (insn
);
1549 find_used_regs (&XEXP (note
, 0), NULL
);
1553 /* If we are to preserve loop structure then do not bypass
1554 a loop header. This will either rotate the loop, create
1555 multiple entry loops or even irreducible regions. */
1556 if (bb
== bb
->loop_father
->header
)
1561 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1562 if (e
->flags
& EDGE_DFS_BACK
)
1564 may_be_loop_header
= true;
1570 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
1574 if (e
->flags
& EDGE_COMPLEX
)
1580 /* We can't redirect edges from new basic blocks. */
1581 if (e
->src
->index
>= bypass_last_basic_block
)
1587 /* The irreducible loops created by redirecting of edges entering the
1588 loop from outside would decrease effectiveness of some of the
1589 following optimizations, so prevent this. */
1590 if (may_be_loop_header
1591 && !(e
->flags
& EDGE_DFS_BACK
))
1597 for (i
= 0; i
< reg_use_count
; i
++)
1599 rtx reg_used
= reg_use_table
[i
];
1600 unsigned int regno
= REGNO (reg_used
);
1601 basic_block dest
, old_dest
;
1602 struct cprop_expr
*set
;
1605 set
= find_bypass_set (regno
, e
->src
->index
);
1610 /* Check the data flow is valid after edge insertions. */
1611 if (e
->insns
.r
&& reg_killed_on_edge (reg_used
, e
))
1614 src
= SET_SRC (pc_set (jump
));
1617 src
= simplify_replace_rtx (src
,
1618 SET_DEST (PATTERN (setcc
)),
1619 SET_SRC (PATTERN (setcc
)));
1621 new_rtx
= simplify_replace_rtx (src
, reg_used
, set
->src
);
1623 /* Jump bypassing may have already placed instructions on
1624 edges of the CFG. We can't bypass an outgoing edge that
1625 has instructions associated with it, as these insns won't
1626 get executed if the incoming edge is redirected. */
1627 if (new_rtx
== pc_rtx
)
1629 edest
= FALLTHRU_EDGE (bb
);
1630 dest
= edest
->insns
.r
? NULL
: edest
->dest
;
1632 else if (GET_CODE (new_rtx
) == LABEL_REF
)
1634 dest
= BLOCK_FOR_INSN (XEXP (new_rtx
, 0));
1635 /* Don't bypass edges containing instructions. */
1636 edest
= find_edge (bb
, dest
);
1637 if (edest
&& edest
->insns
.r
)
1643 /* Avoid unification of the edge with other edges from original
1644 branch. We would end up emitting the instruction on "both"
1646 if (dest
&& setcc
&& !CC0_P (SET_DEST (PATTERN (setcc
)))
1647 && find_edge (e
->src
, dest
))
1653 && dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1655 redirect_edge_and_branch_force (e
, dest
);
1657 /* Copy the register setter to the redirected edge.
1658 Don't copy CC0 setters, as CC0 is dead after jump. */
1661 rtx pat
= PATTERN (setcc
);
1662 if (!CC0_P (SET_DEST (pat
)))
1663 insert_insn_on_edge (copy_insn (pat
), e
);
1666 if (dump_file
!= NULL
)
1668 fprintf (dump_file
, "JUMP-BYPASS: Proved reg %d "
1669 "in jump_insn %d equals constant ",
1670 regno
, INSN_UID (jump
));
1671 print_rtl (dump_file
, set
->src
);
1672 fprintf (dump_file
, "\n\t when BB %d is entered from "
1673 "BB %d. Redirect edge %d->%d to %d.\n",
1674 old_dest
->index
, e
->src
->index
, e
->src
->index
,
1675 old_dest
->index
, dest
->index
);
1688 /* Find basic blocks with more than one predecessor that only contain a
1689 single conditional jump. If the result of the comparison is known at
1690 compile-time from any incoming edge, redirect that edge to the
1691 appropriate target. Return nonzero if a change was made.
1693 This function is now mis-named, because we also handle indirect jumps. */
1696 bypass_conditional_jumps (void)
1704 /* Note we start at block 1. */
1705 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1708 bypass_last_basic_block
= last_basic_block_for_fn (cfun
);
1709 mark_dfs_back_edges ();
1712 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
->next_bb
,
1713 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1715 /* Check for more than one predecessor. */
1716 if (!single_pred_p (bb
))
1719 FOR_BB_INSNS (bb
, insn
)
1720 if (DEBUG_INSN_P (insn
))
1722 else if (NONJUMP_INSN_P (insn
))
1726 if (GET_CODE (PATTERN (insn
)) != SET
)
1729 dest
= SET_DEST (PATTERN (insn
));
1730 if (REG_P (dest
) || CC0_P (dest
))
1735 else if (JUMP_P (insn
))
1737 if ((any_condjump_p (insn
) || computed_jump_p (insn
))
1738 && onlyjump_p (insn
))
1739 changed
|= bypass_block (bb
, setcc
, insn
);
1742 else if (INSN_P (insn
))
1747 /* If we bypassed any register setting insns, we inserted a
1748 copy on the redirected edge. These need to be committed. */
1750 commit_edge_insertions ();
1755 /* Return true if the graph is too expensive to optimize. PASS is the
1756 optimization about to be performed. */
1759 is_too_expensive (const char *pass
)
1761 /* Trying to perform global optimizations on flow graphs which have
1762 a high connectivity will take a long time and is unlikely to be
1763 particularly useful.
1765 In normal circumstances a cfg should have about twice as many
1766 edges as blocks. But we do not want to punish small functions
1767 which have a couple switch statements. Rather than simply
1768 threshold the number of blocks, uses something with a more
1769 graceful degradation. */
1770 if (n_edges_for_fn (cfun
) > 20000 + n_basic_blocks_for_fn (cfun
) * 4)
1772 warning (OPT_Wdisabled_optimization
,
1773 "%s: %d basic blocks and %d edges/basic block",
1774 pass
, n_basic_blocks_for_fn (cfun
),
1775 n_edges_for_fn (cfun
) / n_basic_blocks_for_fn (cfun
));
1780 /* If allocating memory for the cprop bitmap would take up too much
1781 storage it's better just to disable the optimization. */
1782 if ((n_basic_blocks_for_fn (cfun
)
1783 * SBITMAP_SET_SIZE (max_reg_num ())
1784 * sizeof (SBITMAP_ELT_TYPE
)) > MAX_GCSE_MEMORY
)
1786 warning (OPT_Wdisabled_optimization
,
1787 "%s: %d basic blocks and %d registers",
1788 pass
, n_basic_blocks_for_fn (cfun
), max_reg_num ());
1796 /* Main function for the CPROP pass. */
1799 one_cprop_pass (void)
1804 /* Return if there's nothing to do, or it is too expensive. */
1805 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1
1806 || is_too_expensive (_ ("const/copy propagation disabled")))
1809 global_const_prop_count
= local_const_prop_count
= 0;
1810 global_copy_prop_count
= local_copy_prop_count
= 0;
1813 gcc_obstack_init (&cprop_obstack
);
1815 /* Do a local const/copy propagation pass first. The global pass
1816 only handles global opportunities.
1817 If the local pass changes something, remove any unreachable blocks
1818 because the CPROP global dataflow analysis may get into infinite
1819 loops for CFGs with unreachable blocks.
1821 FIXME: This local pass should not be necessary after CSE (but for
1822 some reason it still is). It is also (proven) not necessary
1823 to run the local pass right after FWPWOP.
1825 FIXME: The global analysis would not get into infinite loops if it
1826 would use the DF solver (via df_simple_dataflow) instead of
1827 the solver implemented in this file. */
1828 changed
|= local_cprop_pass ();
1830 delete_unreachable_blocks ();
1832 /* Determine implicit sets. This may change the CFG (split critical
1833 edges if that exposes an implicit set).
1834 Note that find_implicit_sets() does not rely on up-to-date DF caches
1835 so that we do not have to re-run df_analyze() even if local CPROP
1837 ??? This could run earlier so that any uncovered implicit sets
1838 sets could be exploited in local_cprop_pass() also. Later. */
1839 changed
|= find_implicit_sets ();
1841 /* If local_cprop_pass() or find_implicit_sets() changed something,
1842 run df_analyze() to bring all insn caches up-to-date, and to take
1843 new basic blocks from edge splitting on the DF radar.
1844 NB: This also runs the fast DCE pass, because execute_rtl_cprop
1845 sets DF_LR_RUN_DCE. */
1849 /* Initialize implicit_set_indexes array. */
1850 implicit_set_indexes
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1851 for (i
= 0; i
< last_basic_block_for_fn (cfun
); i
++)
1852 implicit_set_indexes
[i
] = -1;
1854 alloc_hash_table (&set_hash_table
);
1855 compute_hash_table (&set_hash_table
);
1857 /* Free implicit_sets before peak usage. */
1858 free (implicit_sets
);
1859 implicit_sets
= NULL
;
1862 dump_hash_table (dump_file
, "SET", &set_hash_table
);
1863 if (set_hash_table
.n_elems
> 0)
1868 alloc_cprop_mem (last_basic_block_for_fn (cfun
),
1869 set_hash_table
.n_elems
);
1870 compute_cprop_data ();
1872 free (implicit_set_indexes
);
1873 implicit_set_indexes
= NULL
;
1875 /* Allocate vars to track sets of regs. */
1876 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
1878 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
->next_bb
,
1879 EXIT_BLOCK_PTR_FOR_FN (cfun
),
1882 /* Reset tables used to keep track of what's still valid [since
1883 the start of the block]. */
1884 reset_opr_set_tables ();
1886 FOR_BB_INSNS (bb
, insn
)
1889 changed
|= cprop_insn (insn
);
1891 /* Keep track of everything modified by this insn. */
1892 /* ??? Need to be careful w.r.t. mods done to INSN.
1893 Don't call mark_oprs_set if we turned the
1894 insn into a NOTE, or deleted the insn. */
1895 if (! NOTE_P (insn
) && ! insn
->deleted ())
1896 mark_oprs_set (insn
);
1900 changed
|= bypass_conditional_jumps ();
1902 FREE_REG_SET (reg_set_bitmap
);
1907 free (implicit_set_indexes
);
1908 implicit_set_indexes
= NULL
;
1911 free_hash_table (&set_hash_table
);
1912 obstack_free (&cprop_obstack
, NULL
);
1916 fprintf (dump_file
, "CPROP of %s, %d basic blocks, %d bytes needed, ",
1917 current_function_name (), n_basic_blocks_for_fn (cfun
),
1919 fprintf (dump_file
, "%d local const props, %d local copy props, ",
1920 local_const_prop_count
, local_copy_prop_count
);
1921 fprintf (dump_file
, "%d global const props, %d global copy props\n\n",
1922 global_const_prop_count
, global_copy_prop_count
);
1928 /* All the passes implemented in this file. Each pass has its
1929 own gate and execute function, and at the end of the file a
1930 pass definition for passes.c.
1932 We do not construct an accurate cfg in functions which call
1933 setjmp, so none of these passes runs if the function calls
1935 FIXME: Should just handle setjmp via REG_SETJMP notes. */
1938 execute_rtl_cprop (void)
1941 delete_unreachable_blocks ();
1942 df_set_flags (DF_LR_RUN_DCE
);
1944 changed
= one_cprop_pass ();
1945 flag_rerun_cse_after_global_opts
|= changed
;
1947 cleanup_cfg (CLEANUP_CFG_CHANGED
);
1953 const pass_data pass_data_rtl_cprop
=
1955 RTL_PASS
, /* type */
1957 OPTGROUP_NONE
, /* optinfo_flags */
1958 TV_CPROP
, /* tv_id */
1959 PROP_cfglayout
, /* properties_required */
1960 0, /* properties_provided */
1961 0, /* properties_destroyed */
1962 0, /* todo_flags_start */
1963 TODO_df_finish
, /* todo_flags_finish */
1966 class pass_rtl_cprop
: public rtl_opt_pass
1969 pass_rtl_cprop (gcc::context
*ctxt
)
1970 : rtl_opt_pass (pass_data_rtl_cprop
, ctxt
)
1973 /* opt_pass methods: */
1974 opt_pass
* clone () { return new pass_rtl_cprop (m_ctxt
); }
1975 virtual bool gate (function
*fun
)
1977 return optimize
> 0 && flag_gcse
1978 && !fun
->calls_setjmp
1982 virtual unsigned int execute (function
*) { return execute_rtl_cprop (); }
1984 }; // class pass_rtl_cprop
1989 make_pass_rtl_cprop (gcc::context
*ctxt
)
1991 return new pass_rtl_cprop (ctxt
);