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"
31 #include "insn-config.h"
35 #include "diagnostic-core.h"
42 #include "cfgcleanup.h"
53 #include "tree-pass.h"
58 /* An obstack for our working variables. */
59 static struct obstack cprop_obstack
;
61 /* Occurrence of an expression.
62 There is one per basic block. If a pattern appears more than once the
63 last appearance is used. */
67 /* Next occurrence of this expression. */
68 struct cprop_occr
*next
;
69 /* The insn that computes the expression. */
73 /* Hash table entry for assignment expressions. */
77 /* The expression (DEST := SRC). */
81 /* Index in the available expression bitmaps. */
83 /* Next entry with the same hash. */
84 struct cprop_expr
*next_same_hash
;
85 /* List of available occurrence in basic blocks in the function.
86 An "available occurrence" is one that is the last occurrence in the
87 basic block and whose operands are not modified by following statements
88 in the basic block [including this insn]. */
89 struct cprop_occr
*avail_occr
;
92 /* Hash table for copy propagation expressions.
93 Each hash table is an array of buckets.
94 ??? It is known that if it were an array of entries, structure elements
95 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
96 not clear whether in the final analysis a sufficient amount of memory would
97 be saved as the size of the available expression bitmaps would be larger
98 [one could build a mapping table without holes afterwards though].
99 Someday I'll perform the computation and figure it out. */
104 This is an array of `set_hash_table_size' elements. */
105 struct cprop_expr
**table
;
107 /* Size of the hash table, in elements. */
110 /* Number of hash table elements. */
111 unsigned int n_elems
;
114 /* Copy propagation hash table. */
115 static struct hash_table_d set_hash_table
;
117 /* Array of implicit set patterns indexed by basic block index. */
118 static rtx
*implicit_sets
;
120 /* Array of indexes of expressions for implicit set patterns indexed by basic
121 block index. In other words, implicit_set_indexes[i] is the bitmap_index
122 of the expression whose RTX is implicit_sets[i]. */
123 static int *implicit_set_indexes
;
125 /* Bitmap containing one bit for each register in the program.
126 Used when performing GCSE to track which registers have been set since
127 the start or end of the basic block while traversing that block. */
128 static regset reg_set_bitmap
;
130 /* Various variables for statistics gathering. */
132 /* Memory used in a pass.
133 This isn't intended to be absolutely precise. Its intent is only
134 to keep an eye on memory usage. */
135 static int bytes_used
;
137 /* Number of local constants propagated. */
138 static int local_const_prop_count
;
139 /* Number of local copies propagated. */
140 static int local_copy_prop_count
;
141 /* Number of global constants propagated. */
142 static int global_const_prop_count
;
143 /* Number of global copies propagated. */
144 static int global_copy_prop_count
;
146 #define GOBNEW(T) ((T *) cprop_alloc (sizeof (T)))
147 #define GOBNEWVAR(T, S) ((T *) cprop_alloc ((S)))
149 /* Cover function to obstack_alloc. */
152 cprop_alloc (unsigned long size
)
155 return obstack_alloc (&cprop_obstack
, size
);
158 /* Return nonzero if register X is unchanged from INSN to the end
159 of INSN's basic block. */
162 reg_available_p (const_rtx x
, const rtx_insn
*insn ATTRIBUTE_UNUSED
)
164 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
167 /* Hash a set of register REGNO.
169 Sets are hashed on the register that is set. This simplifies the PRE copy
172 ??? May need to make things more elaborate. Later, as necessary. */
175 hash_mod (int regno
, int hash_table_size
)
177 return (unsigned) regno
% hash_table_size
;
180 /* Insert assignment DEST:=SET from INSN in the hash table.
181 DEST is a register and SET is a register or a suitable constant.
182 If the assignment is already present in the table, record it as
183 the last occurrence in INSN's basic block.
184 IMPLICIT is true if it's an implicit set, false otherwise. */
187 insert_set_in_table (rtx dest
, rtx src
, rtx_insn
*insn
,
188 struct hash_table_d
*table
, bool implicit
)
192 struct cprop_expr
*cur_expr
, *last_expr
= NULL
;
193 struct cprop_occr
*cur_occr
;
195 hash
= hash_mod (REGNO (dest
), table
->size
);
197 for (cur_expr
= table
->table
[hash
]; cur_expr
;
198 cur_expr
= cur_expr
->next_same_hash
)
200 if (dest
== cur_expr
->dest
201 && src
== cur_expr
->src
)
206 last_expr
= cur_expr
;
211 cur_expr
= GOBNEW (struct cprop_expr
);
212 bytes_used
+= sizeof (struct cprop_expr
);
213 if (table
->table
[hash
] == NULL
)
214 /* This is the first pattern that hashed to this index. */
215 table
->table
[hash
] = cur_expr
;
217 /* Add EXPR to end of this hash chain. */
218 last_expr
->next_same_hash
= cur_expr
;
220 /* Set the fields of the expr element.
221 We must copy X because it can be modified when copy propagation is
222 performed on its operands. */
223 cur_expr
->dest
= copy_rtx (dest
);
224 cur_expr
->src
= copy_rtx (src
);
225 cur_expr
->bitmap_index
= table
->n_elems
++;
226 cur_expr
->next_same_hash
= NULL
;
227 cur_expr
->avail_occr
= NULL
;
230 /* Now record the occurrence. */
231 cur_occr
= cur_expr
->avail_occr
;
234 && BLOCK_FOR_INSN (cur_occr
->insn
) == BLOCK_FOR_INSN (insn
))
236 /* Found another instance of the expression in the same basic block.
237 Prefer this occurrence to the currently recorded one. We want
238 the last one in the block and the block is scanned from start
240 cur_occr
->insn
= insn
;
244 /* First occurrence of this expression in this basic block. */
245 cur_occr
= GOBNEW (struct cprop_occr
);
246 bytes_used
+= sizeof (struct cprop_occr
);
247 cur_occr
->insn
= insn
;
248 cur_occr
->next
= cur_expr
->avail_occr
;
249 cur_expr
->avail_occr
= cur_occr
;
252 /* Record bitmap_index of the implicit set in implicit_set_indexes. */
254 implicit_set_indexes
[BLOCK_FOR_INSN (insn
)->index
]
255 = cur_expr
->bitmap_index
;
258 /* Determine whether the rtx X should be treated as a constant for CPROP.
259 Since X might be inserted more than once we have to take care that it
263 cprop_constant_p (const_rtx x
)
265 return CONSTANT_P (x
) && (GET_CODE (x
) != CONST
|| shared_const_p (x
));
268 /* Determine whether the rtx X should be treated as a register that can
269 be propagated. Any pseudo-register is fine. */
272 cprop_reg_p (const_rtx x
)
274 return REG_P (x
) && !HARD_REGISTER_P (x
);
277 /* Scan SET present in INSN and add an entry to the hash TABLE.
278 IMPLICIT is true if it's an implicit set, false otherwise. */
281 hash_scan_set (rtx set
, rtx_insn
*insn
, struct hash_table_d
*table
,
284 rtx src
= SET_SRC (set
);
285 rtx dest
= SET_DEST (set
);
287 if (cprop_reg_p (dest
)
288 && reg_available_p (dest
, insn
)
289 && can_copy_p (GET_MODE (dest
)))
291 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
293 This allows us to do a single CPROP pass and still eliminate
294 redundant constants, addresses or other expressions that are
295 constructed with multiple instructions.
297 However, keep the original SRC if INSN is a simple reg-reg move. In
298 In this case, there will almost always be a REG_EQUAL note on the
299 insn that sets SRC. By recording the REG_EQUAL value here as SRC
300 for INSN, we miss copy propagation opportunities.
302 Note that this does not impede profitable constant propagations. We
303 "look through" reg-reg sets in lookup_set. */
304 rtx note
= find_reg_equal_equiv_note (insn
);
306 && REG_NOTE_KIND (note
) == REG_EQUAL
308 && cprop_constant_p (XEXP (note
, 0)))
309 src
= XEXP (note
, 0), set
= gen_rtx_SET (dest
, src
);
311 /* Record sets for constant/copy propagation. */
312 if ((cprop_reg_p (src
)
314 && reg_available_p (src
, insn
))
315 || cprop_constant_p (src
))
316 insert_set_in_table (dest
, src
, insn
, table
, implicit
);
320 /* Process INSN and add hash table entries as appropriate. */
323 hash_scan_insn (rtx_insn
*insn
, struct hash_table_d
*table
)
325 rtx pat
= PATTERN (insn
);
328 /* Pick out the sets of INSN and for other forms of instructions record
329 what's been modified. */
331 if (GET_CODE (pat
) == SET
)
332 hash_scan_set (pat
, insn
, table
, false);
333 else if (GET_CODE (pat
) == PARALLEL
)
334 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
336 rtx x
= XVECEXP (pat
, 0, i
);
338 if (GET_CODE (x
) == SET
)
339 hash_scan_set (x
, insn
, table
, false);
343 /* Dump the hash table TABLE to file FILE under the name NAME. */
346 dump_hash_table (FILE *file
, const char *name
, struct hash_table_d
*table
)
349 /* Flattened out table, so it's printed in proper order. */
350 struct cprop_expr
**flat_table
;
351 unsigned int *hash_val
;
352 struct cprop_expr
*expr
;
354 flat_table
= XCNEWVEC (struct cprop_expr
*, table
->n_elems
);
355 hash_val
= XNEWVEC (unsigned int, table
->n_elems
);
357 for (i
= 0; i
< (int) table
->size
; i
++)
358 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
360 flat_table
[expr
->bitmap_index
] = expr
;
361 hash_val
[expr
->bitmap_index
] = i
;
364 fprintf (file
, "%s hash table (%d buckets, %d entries)\n",
365 name
, table
->size
, table
->n_elems
);
367 for (i
= 0; i
< (int) table
->n_elems
; i
++)
368 if (flat_table
[i
] != 0)
370 expr
= flat_table
[i
];
371 fprintf (file
, "Index %d (hash value %d)\n ",
372 expr
->bitmap_index
, hash_val
[i
]);
373 print_rtl (file
, expr
->dest
);
374 fprintf (file
, " := ");
375 print_rtl (file
, expr
->src
);
376 fprintf (file
, "\n");
379 fprintf (file
, "\n");
385 /* Record as unavailable all registers that are DEF operands of INSN. */
388 make_set_regs_unavailable (rtx_insn
*insn
)
392 FOR_EACH_INSN_DEF (def
, insn
)
393 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (def
));
396 /* Top level function to create an assignment hash table.
398 Assignment entries are placed in the hash table if
399 - they are of the form (set (pseudo-reg) src),
400 - src is something we want to perform const/copy propagation on,
401 - none of the operands or target are subsequently modified in the block
403 Currently src must be a pseudo-reg or a const_int.
405 TABLE is the table computed. */
408 compute_hash_table_work (struct hash_table_d
*table
)
412 /* Allocate vars to track sets of regs. */
413 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
415 FOR_EACH_BB_FN (bb
, cfun
)
419 /* Reset tables used to keep track of what's not yet invalid [since
420 the end of the block]. */
421 CLEAR_REG_SET (reg_set_bitmap
);
423 /* Go over all insns from the last to the first. This is convenient
424 for tracking available registers, i.e. not set between INSN and
425 the end of the basic block BB. */
426 FOR_BB_INSNS_REVERSE (bb
, insn
)
428 /* Only real insns are interesting. */
429 if (!NONDEBUG_INSN_P (insn
))
432 /* Record interesting sets from INSN in the hash table. */
433 hash_scan_insn (insn
, table
);
435 /* Any registers set in INSN will make SETs above it not AVAIL. */
436 make_set_regs_unavailable (insn
);
439 /* Insert implicit sets in the hash table, pretending they appear as
440 insns at the head of the basic block. */
441 if (implicit_sets
[bb
->index
] != NULL_RTX
)
442 hash_scan_set (implicit_sets
[bb
->index
], BB_HEAD (bb
), table
, true);
445 FREE_REG_SET (reg_set_bitmap
);
448 /* Allocate space for the set/expr hash TABLE.
449 It is used to determine the number of buckets to use. */
452 alloc_hash_table (struct hash_table_d
*table
)
456 n
= get_max_insn_count ();
459 if (table
->size
< 11)
462 /* Attempt to maintain efficient use of hash table.
463 Making it an odd number is simplest for now.
464 ??? Later take some measurements. */
466 n
= table
->size
* sizeof (struct cprop_expr
*);
467 table
->table
= XNEWVAR (struct cprop_expr
*, n
);
470 /* Free things allocated by alloc_hash_table. */
473 free_hash_table (struct hash_table_d
*table
)
478 /* Compute the hash TABLE for doing copy/const propagation or
479 expression hash table. */
482 compute_hash_table (struct hash_table_d
*table
)
484 /* Initialize count of number of entries in hash table. */
486 memset (table
->table
, 0, table
->size
* sizeof (struct cprop_expr
*));
488 compute_hash_table_work (table
);
491 /* Expression tracking support. */
493 /* Lookup REGNO in the set TABLE. The result is a pointer to the
494 table entry, or NULL if not found. */
496 static struct cprop_expr
*
497 lookup_set (unsigned int regno
, struct hash_table_d
*table
)
499 unsigned int hash
= hash_mod (regno
, table
->size
);
500 struct cprop_expr
*expr
;
502 expr
= table
->table
[hash
];
504 while (expr
&& REGNO (expr
->dest
) != regno
)
505 expr
= expr
->next_same_hash
;
510 /* Return the next entry for REGNO in list EXPR. */
512 static struct cprop_expr
*
513 next_set (unsigned int regno
, struct cprop_expr
*expr
)
516 expr
= expr
->next_same_hash
;
517 while (expr
&& REGNO (expr
->dest
) != regno
);
522 /* Reset tables used to keep track of what's still available [since the
523 start of the block]. */
526 reset_opr_set_tables (void)
528 /* Maintain a bitmap of which regs have been set since beginning of
530 CLEAR_REG_SET (reg_set_bitmap
);
533 /* Return nonzero if the register X has not been set yet [since the
534 start of the basic block containing INSN]. */
537 reg_not_set_p (const_rtx x
, const rtx_insn
*insn ATTRIBUTE_UNUSED
)
539 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
542 /* Record things set by INSN.
543 This data is used by reg_not_set_p. */
546 mark_oprs_set (rtx_insn
*insn
)
550 FOR_EACH_INSN_DEF (def
, insn
)
551 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (def
));
554 /* Compute copy/constant propagation working variables. */
556 /* Local properties of assignments. */
557 static sbitmap
*cprop_avloc
;
558 static sbitmap
*cprop_kill
;
560 /* Global properties of assignments (computed from the local properties). */
561 static sbitmap
*cprop_avin
;
562 static sbitmap
*cprop_avout
;
564 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
565 basic blocks. N_SETS is the number of sets. */
568 alloc_cprop_mem (int n_blocks
, int n_sets
)
570 cprop_avloc
= sbitmap_vector_alloc (n_blocks
, n_sets
);
571 cprop_kill
= sbitmap_vector_alloc (n_blocks
, n_sets
);
573 cprop_avin
= sbitmap_vector_alloc (n_blocks
, n_sets
);
574 cprop_avout
= sbitmap_vector_alloc (n_blocks
, n_sets
);
577 /* Free vars used by copy/const propagation. */
580 free_cprop_mem (void)
582 sbitmap_vector_free (cprop_avloc
);
583 sbitmap_vector_free (cprop_kill
);
584 sbitmap_vector_free (cprop_avin
);
585 sbitmap_vector_free (cprop_avout
);
588 /* Compute the local properties of each recorded expression.
590 Local properties are those that are defined by the block, irrespective of
593 An expression is killed in a block if its operands, either DEST or SRC, are
594 modified in the block.
596 An expression is computed (locally available) in a block if it is computed
597 at least once and expression would contain the same value if the
598 computation was moved to the end of the block.
600 KILL and COMP are destination sbitmaps for recording local properties. */
603 compute_local_properties (sbitmap
*kill
, sbitmap
*comp
,
604 struct hash_table_d
*table
)
608 /* Initialize the bitmaps that were passed in. */
609 bitmap_vector_clear (kill
, last_basic_block_for_fn (cfun
));
610 bitmap_vector_clear (comp
, last_basic_block_for_fn (cfun
));
612 for (i
= 0; i
< table
->size
; i
++)
614 struct cprop_expr
*expr
;
616 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
618 int indx
= expr
->bitmap_index
;
620 struct cprop_occr
*occr
;
622 /* For each definition of the destination pseudo-reg, the expression
623 is killed in the block where the definition is. */
624 for (def
= DF_REG_DEF_CHAIN (REGNO (expr
->dest
));
625 def
; def
= DF_REF_NEXT_REG (def
))
626 bitmap_set_bit (kill
[DF_REF_BB (def
)->index
], indx
);
628 /* If the source is a pseudo-reg, for each definition of the source,
629 the expression is killed in the block where the definition is. */
630 if (REG_P (expr
->src
))
631 for (def
= DF_REG_DEF_CHAIN (REGNO (expr
->src
));
632 def
; def
= DF_REF_NEXT_REG (def
))
633 bitmap_set_bit (kill
[DF_REF_BB (def
)->index
], indx
);
635 /* The occurrences recorded in avail_occr are exactly those that
636 are locally available in the block where they are. */
637 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
639 bitmap_set_bit (comp
[BLOCK_FOR_INSN (occr
->insn
)->index
], indx
);
645 /* Hash table support. */
647 /* Top level routine to do the dataflow analysis needed by copy/const
651 compute_cprop_data (void)
655 compute_local_properties (cprop_kill
, cprop_avloc
, &set_hash_table
);
656 compute_available (cprop_avloc
, cprop_kill
, cprop_avout
, cprop_avin
);
658 /* Merge implicit sets into CPROP_AVIN. They are always available at the
659 entry of their basic block. We need to do this because 1) implicit sets
660 aren't recorded for the local pass so they cannot be propagated within
661 their basic block by this pass and 2) the global pass would otherwise
662 propagate them only in the successors of their basic block. */
663 FOR_EACH_BB_FN (bb
, cfun
)
665 int index
= implicit_set_indexes
[bb
->index
];
667 bitmap_set_bit (cprop_avin
[bb
->index
], index
);
671 /* Copy/constant propagation. */
673 /* Maximum number of register uses in an insn that we handle. */
676 /* Table of uses (registers, both hard and pseudo) found in an insn.
677 Allocated statically to avoid alloc/free complexity and overhead. */
678 static rtx reg_use_table
[MAX_USES
];
680 /* Index into `reg_use_table' while building it. */
681 static unsigned reg_use_count
;
683 /* Set up a list of register numbers used in INSN. The found uses are stored
684 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
685 and contains the number of uses in the table upon exit.
687 ??? If a register appears multiple times we will record it multiple times.
688 This doesn't hurt anything but it will slow things down. */
691 find_used_regs (rtx
*xptr
, void *data ATTRIBUTE_UNUSED
)
698 /* repeat is used to turn tail-recursion into iteration since GCC
699 can't do it when there's no return value. */
707 if (reg_use_count
== MAX_USES
)
710 reg_use_table
[reg_use_count
] = x
;
714 /* Recursively scan the operands of this expression. */
716 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
720 /* If we are about to do the last recursive call
721 needed at this level, change it into iteration.
722 This function is called enough to be worth it. */
729 find_used_regs (&XEXP (x
, i
), data
);
731 else if (fmt
[i
] == 'E')
732 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
733 find_used_regs (&XVECEXP (x
, i
, j
), data
);
737 /* Try to replace all uses of FROM in INSN with TO.
738 Return nonzero if successful. */
741 try_replace_reg (rtx from
, rtx to
, rtx_insn
*insn
)
743 rtx note
= find_reg_equal_equiv_note (insn
);
746 rtx set
= single_set (insn
);
748 bool check_rtx_costs
= true;
749 bool speed
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn
));
750 int old_cost
= set
? set_rtx_cost (set
, speed
) : 0;
753 || CONSTANT_P (SET_SRC (set
))
755 && REG_NOTE_KIND (note
) == REG_EQUAL
756 && (GET_CODE (XEXP (note
, 0)) == CONST
757 || CONSTANT_P (XEXP (note
, 0)))))
758 check_rtx_costs
= false;
760 /* Usually we substitute easy stuff, so we won't copy everything.
761 We however need to take care to not duplicate non-trivial CONST
765 validate_replace_src_group (from
, to
, insn
);
767 /* If TO is a constant, check the cost of the set after propagation
768 to the cost of the set before the propagation. If the cost is
769 higher, then do not replace FROM with TO. */
773 && set_rtx_cost (set
, speed
) > old_cost
)
780 if (num_changes_pending () && apply_change_group ())
783 /* Try to simplify SET_SRC if we have substituted a constant. */
784 if (success
&& set
&& CONSTANT_P (to
))
786 src
= simplify_rtx (SET_SRC (set
));
789 validate_change (insn
, &SET_SRC (set
), src
, 0);
792 /* If there is already a REG_EQUAL note, update the expression in it
793 with our replacement. */
794 if (note
!= 0 && REG_NOTE_KIND (note
) == REG_EQUAL
)
795 set_unique_reg_note (insn
, REG_EQUAL
,
796 simplify_replace_rtx (XEXP (note
, 0), from
, to
));
797 if (!success
&& set
&& reg_mentioned_p (from
, SET_SRC (set
)))
799 /* If above failed and this is a single set, try to simplify the source
800 of the set given our substitution. We could perhaps try this for
801 multiple SETs, but it probably won't buy us anything. */
802 src
= simplify_replace_rtx (SET_SRC (set
), from
, to
);
804 if (!rtx_equal_p (src
, SET_SRC (set
))
805 && validate_change (insn
, &SET_SRC (set
), src
, 0))
808 /* If we've failed perform the replacement, have a single SET to
809 a REG destination and don't yet have a note, add a REG_EQUAL note
810 to not lose information. */
811 if (!success
&& note
== 0 && set
!= 0 && REG_P (SET_DEST (set
)))
812 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
815 if (set
&& MEM_P (SET_DEST (set
)) && reg_mentioned_p (from
, SET_DEST (set
)))
817 /* Registers can also appear as uses in SET_DEST if it is a MEM.
818 We could perhaps try this for multiple SETs, but it probably
819 won't buy us anything. */
820 rtx dest
= simplify_replace_rtx (SET_DEST (set
), from
, to
);
822 if (!rtx_equal_p (dest
, SET_DEST (set
))
823 && validate_change (insn
, &SET_DEST (set
), dest
, 0))
827 /* REG_EQUAL may get simplified into register.
828 We don't allow that. Remove that note. This code ought
829 not to happen, because previous code ought to synthesize
830 reg-reg move, but be on the safe side. */
831 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
&& REG_P (XEXP (note
, 0)))
832 remove_note (insn
, note
);
837 /* Find a set of REGNOs that are available on entry to INSN's block. If found,
838 SET_RET[0] will be assigned a set with a register source and SET_RET[1] a
839 set with a constant source. If not found the corresponding entry is set to
843 find_avail_set (int regno
, rtx_insn
*insn
, struct cprop_expr
*set_ret
[2])
845 set_ret
[0] = set_ret
[1] = NULL
;
847 /* Loops are not possible here. To get a loop we would need two sets
848 available at the start of the block containing INSN. i.e. we would
849 need two sets like this available at the start of the block:
851 (set (reg X) (reg Y))
852 (set (reg Y) (reg X))
854 This can not happen since the set of (reg Y) would have killed the
855 set of (reg X) making it unavailable at the start of this block. */
859 struct cprop_expr
*set
= lookup_set (regno
, &set_hash_table
);
861 /* Find a set that is available at the start of the block
862 which contains INSN. */
865 if (bitmap_bit_p (cprop_avin
[BLOCK_FOR_INSN (insn
)->index
],
868 set
= next_set (regno
, set
);
871 /* If no available set was found we've reached the end of the
872 (possibly empty) copy chain. */
878 /* We know the set is available.
879 Now check that SRC is locally anticipatable (i.e. none of the
880 source operands have changed since the start of the block).
882 If the source operand changed, we may still use it for the next
883 iteration of this loop, but we may not use it for substitutions. */
885 if (cprop_constant_p (src
))
887 else if (reg_not_set_p (src
, insn
))
890 /* If the source of the set is anything except a register, then
891 we have reached the end of the copy chain. */
895 /* Follow the copy chain, i.e. start another iteration of the loop
896 and see if we have an available copy into SRC. */
901 /* Subroutine of cprop_insn that tries to propagate constants into
902 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
903 it is the instruction that immediately precedes JUMP, and must be a
904 single SET of a register. FROM is what we will try to replace,
905 SRC is the constant we will try to substitute for it. Return nonzero
906 if a change was made. */
909 cprop_jump (basic_block bb
, rtx_insn
*setcc
, rtx_insn
*jump
, rtx from
, rtx src
)
911 rtx new_rtx
, set_src
, note_src
;
912 rtx set
= pc_set (jump
);
913 rtx note
= find_reg_equal_equiv_note (jump
);
917 note_src
= XEXP (note
, 0);
918 if (GET_CODE (note_src
) == EXPR_LIST
)
921 else note_src
= NULL_RTX
;
923 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
924 set_src
= note_src
? note_src
: SET_SRC (set
);
926 /* First substitute the SETCC condition into the JUMP instruction,
927 then substitute that given values into this expanded JUMP. */
928 if (setcc
!= NULL_RTX
929 && !modified_between_p (from
, setcc
, jump
)
930 && !modified_between_p (src
, setcc
, jump
))
933 rtx setcc_set
= single_set (setcc
);
934 rtx setcc_note
= find_reg_equal_equiv_note (setcc
);
935 setcc_src
= (setcc_note
&& GET_CODE (XEXP (setcc_note
, 0)) != EXPR_LIST
)
936 ? XEXP (setcc_note
, 0) : SET_SRC (setcc_set
);
937 set_src
= simplify_replace_rtx (set_src
, SET_DEST (setcc_set
),
943 new_rtx
= simplify_replace_rtx (set_src
, from
, src
);
945 /* If no simplification can be made, then try the next register. */
946 if (rtx_equal_p (new_rtx
, SET_SRC (set
)))
949 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
950 if (new_rtx
== pc_rtx
)
954 /* Ensure the value computed inside the jump insn to be equivalent
955 to one computed by setcc. */
956 if (setcc
&& modified_in_p (new_rtx
, setcc
))
958 if (! validate_unshare_change (jump
, &SET_SRC (set
), new_rtx
, 0))
960 /* When (some) constants are not valid in a comparison, and there
961 are two registers to be replaced by constants before the entire
962 comparison can be folded into a constant, we need to keep
963 intermediate information in REG_EQUAL notes. For targets with
964 separate compare insns, such notes are added by try_replace_reg.
965 When we have a combined compare-and-branch instruction, however,
966 we need to attach a note to the branch itself to make this
967 optimization work. */
969 if (!rtx_equal_p (new_rtx
, note_src
))
970 set_unique_reg_note (jump
, REG_EQUAL
, copy_rtx (new_rtx
));
974 /* Remove REG_EQUAL note after simplification. */
976 remove_note (jump
, note
);
979 /* Delete the cc0 setter. */
980 if (HAVE_cc0
&& setcc
!= NULL
&& CC0_P (SET_DEST (single_set (setcc
))))
983 global_const_prop_count
++;
984 if (dump_file
!= NULL
)
987 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with"
988 "constant ", REGNO (from
), INSN_UID (jump
));
989 print_rtl (dump_file
, src
);
990 fprintf (dump_file
, "\n");
992 purge_dead_edges (bb
);
994 /* If a conditional jump has been changed into unconditional jump, remove
995 the jump and make the edge fallthru - this is always called in
997 if (new_rtx
!= pc_rtx
&& simplejump_p (jump
))
1002 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1003 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1004 && BB_HEAD (e
->dest
) == JUMP_LABEL (jump
))
1006 e
->flags
|= EDGE_FALLTHRU
;
1015 /* Subroutine of cprop_insn that tries to propagate constants. FROM is what
1016 we will try to replace, SRC is the constant we will try to substitute for
1017 it and INSN is the instruction where this will be happening. */
1020 constprop_register (rtx from
, rtx src
, rtx_insn
*insn
)
1024 /* Check for reg or cc0 setting instructions followed by
1025 conditional branch instructions first. */
1026 if ((sset
= single_set (insn
)) != NULL
1028 && any_condjump_p (NEXT_INSN (insn
)) && onlyjump_p (NEXT_INSN (insn
)))
1030 rtx dest
= SET_DEST (sset
);
1031 if ((REG_P (dest
) || CC0_P (dest
))
1032 && cprop_jump (BLOCK_FOR_INSN (insn
), insn
, NEXT_INSN (insn
),
1037 /* Handle normal insns next. */
1038 if (NONJUMP_INSN_P (insn
) && try_replace_reg (from
, src
, insn
))
1041 /* Try to propagate a CONST_INT into a conditional jump.
1042 We're pretty specific about what we will handle in this
1043 code, we can extend this as necessary over time.
1045 Right now the insn in question must look like
1046 (set (pc) (if_then_else ...)) */
1047 else if (any_condjump_p (insn
) && onlyjump_p (insn
))
1048 return cprop_jump (BLOCK_FOR_INSN (insn
), NULL
, insn
, from
, src
);
1052 /* Perform constant and copy propagation on INSN.
1053 Return nonzero if a change was made. */
1056 cprop_insn (rtx_insn
*insn
)
1059 int changed
= 0, changed_this_round
;
1064 changed_this_round
= 0;
1066 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1068 /* We may win even when propagating constants into notes. */
1069 note
= find_reg_equal_equiv_note (insn
);
1071 find_used_regs (&XEXP (note
, 0), NULL
);
1073 for (i
= 0; i
< reg_use_count
; i
++)
1075 rtx reg_used
= reg_use_table
[i
];
1076 unsigned int regno
= REGNO (reg_used
);
1077 rtx src_cst
= NULL
, src_reg
= NULL
;
1078 struct cprop_expr
*set
[2];
1080 /* If the register has already been set in this block, there's
1081 nothing we can do. */
1082 if (! reg_not_set_p (reg_used
, insn
))
1085 /* Find an assignment that sets reg_used and is available
1086 at the start of the block. */
1087 find_avail_set (regno
, insn
, set
);
1089 src_reg
= set
[0]->src
;
1091 src_cst
= set
[1]->src
;
1093 /* Constant propagation. */
1094 if (src_cst
&& cprop_constant_p (src_cst
)
1095 && constprop_register (reg_used
, src_cst
, insn
))
1097 changed_this_round
= changed
= 1;
1098 global_const_prop_count
++;
1099 if (dump_file
!= NULL
)
1102 "GLOBAL CONST-PROP: Replacing reg %d in ", regno
);
1103 fprintf (dump_file
, "insn %d with constant ",
1105 print_rtl (dump_file
, src_cst
);
1106 fprintf (dump_file
, "\n");
1108 if (insn
->deleted ())
1111 /* Copy propagation. */
1112 else if (src_reg
&& cprop_reg_p (src_reg
)
1113 && REGNO (src_reg
) != regno
1114 && try_replace_reg (reg_used
, src_reg
, insn
))
1116 changed_this_round
= changed
= 1;
1117 global_copy_prop_count
++;
1118 if (dump_file
!= NULL
)
1121 "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1122 regno
, INSN_UID (insn
));
1123 fprintf (dump_file
, " with reg %d\n", REGNO (src_reg
));
1126 /* The original insn setting reg_used may or may not now be
1127 deletable. We leave the deletion to DCE. */
1128 /* FIXME: If it turns out that the insn isn't deletable,
1129 then we may have unnecessarily extended register lifetimes
1130 and made things worse. */
1134 /* If try_replace_reg simplified the insn, the regs found by find_used_regs
1135 may not be valid anymore. Start over. */
1136 while (changed_this_round
);
1138 if (changed
&& DEBUG_INSN_P (insn
))
1144 /* Like find_used_regs, but avoid recording uses that appear in
1145 input-output contexts such as zero_extract or pre_dec. This
1146 restricts the cases we consider to those for which local cprop
1147 can legitimately make replacements. */
1150 local_cprop_find_used_regs (rtx
*xptr
, void *data
)
1157 switch (GET_CODE (x
))
1161 case STRICT_LOW_PART
:
1170 /* Can only legitimately appear this early in the context of
1171 stack pushes for function arguments, but handle all of the
1172 codes nonetheless. */
1176 /* Setting a subreg of a register larger than word_mode leaves
1177 the non-written words unchanged. */
1178 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x
))) > BITS_PER_WORD
)
1186 find_used_regs (xptr
, data
);
1189 /* Try to perform local const/copy propagation on X in INSN. */
1192 do_local_cprop (rtx x
, rtx_insn
*insn
)
1194 rtx newreg
= NULL
, newcnst
= NULL
;
1196 /* Rule out USE instructions and ASM statements as we don't want to
1197 change the hard registers mentioned. */
1200 || (GET_CODE (PATTERN (insn
)) != USE
1201 && asm_noperands (PATTERN (insn
)) < 0)))
1203 cselib_val
*val
= cselib_lookup (x
, GET_MODE (x
), 0, VOIDmode
);
1204 struct elt_loc_list
*l
;
1208 for (l
= val
->locs
; l
; l
= l
->next
)
1210 rtx this_rtx
= l
->loc
;
1213 if (cprop_constant_p (this_rtx
))
1215 if (cprop_reg_p (this_rtx
)
1216 /* Don't copy propagate if it has attached REG_EQUIV note.
1217 At this point this only function parameters should have
1218 REG_EQUIV notes and if the argument slot is used somewhere
1219 explicitly, it means address of parameter has been taken,
1220 so we should not extend the lifetime of the pseudo. */
1221 && (!(note
= find_reg_note (l
->setting_insn
, REG_EQUIV
, NULL_RTX
))
1222 || ! MEM_P (XEXP (note
, 0))))
1225 if (newcnst
&& constprop_register (x
, newcnst
, insn
))
1227 if (dump_file
!= NULL
)
1229 fprintf (dump_file
, "LOCAL CONST-PROP: Replacing reg %d in ",
1231 fprintf (dump_file
, "insn %d with constant ",
1233 print_rtl (dump_file
, newcnst
);
1234 fprintf (dump_file
, "\n");
1236 local_const_prop_count
++;
1239 else if (newreg
&& newreg
!= x
&& try_replace_reg (x
, newreg
, insn
))
1241 if (dump_file
!= NULL
)
1244 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1245 REGNO (x
), INSN_UID (insn
));
1246 fprintf (dump_file
, " with reg %d\n", REGNO (newreg
));
1248 local_copy_prop_count
++;
1255 /* Do local const/copy propagation (i.e. within each basic block). */
1258 local_cprop_pass (void)
1262 bool changed
= false;
1266 FOR_EACH_BB_FN (bb
, cfun
)
1268 FOR_BB_INSNS (bb
, insn
)
1272 rtx note
= find_reg_equal_equiv_note (insn
);
1276 note_uses (&PATTERN (insn
), local_cprop_find_used_regs
,
1279 local_cprop_find_used_regs (&XEXP (note
, 0), NULL
);
1281 for (i
= 0; i
< reg_use_count
; i
++)
1283 if (do_local_cprop (reg_use_table
[i
], insn
))
1285 if (!DEBUG_INSN_P (insn
))
1290 if (insn
->deleted ())
1293 while (i
< reg_use_count
);
1295 cselib_process_insn (insn
);
1298 /* Forget everything at the end of a basic block. */
1299 cselib_clear_table ();
1307 /* Similar to get_condition, only the resulting condition must be
1308 valid at JUMP, instead of at EARLIEST.
1310 This differs from noce_get_condition in ifcvt.c in that we prefer not to
1311 settle for the condition variable in the jump instruction being integral.
1312 We prefer to be able to record the value of a user variable, rather than
1313 the value of a temporary used in a condition. This could be solved by
1314 recording the value of *every* register scanned by canonicalize_condition,
1315 but this would require some code reorganization. */
1318 fis_get_condition (rtx_insn
*jump
)
1320 return get_condition (jump
, NULL
, false, true);
1323 /* Check the comparison COND to see if we can safely form an implicit
1327 implicit_set_cond_p (const_rtx cond
)
1332 /* COND must be either an EQ or NE comparison. */
1333 if (GET_CODE (cond
) != EQ
&& GET_CODE (cond
) != NE
)
1336 /* The first operand of COND must be a register we can propagate. */
1337 if (!cprop_reg_p (XEXP (cond
, 0)))
1340 /* The second operand of COND must be a suitable constant. */
1341 mode
= GET_MODE (XEXP (cond
, 0));
1342 cst
= XEXP (cond
, 1);
1344 /* We can't perform this optimization if either operand might be or might
1345 contain a signed zero. */
1346 if (HONOR_SIGNED_ZEROS (mode
))
1348 /* It is sufficient to check if CST is or contains a zero. We must
1349 handle float, complex, and vector. If any subpart is a zero, then
1350 the optimization can't be performed. */
1351 /* ??? The complex and vector checks are not implemented yet. We just
1352 always return zero for them. */
1353 if (CONST_DOUBLE_AS_FLOAT_P (cst
)
1354 && real_equal (CONST_DOUBLE_REAL_VALUE (cst
), &dconst0
))
1360 return cprop_constant_p (cst
);
1363 /* Find the implicit sets of a function. An "implicit set" is a constraint
1364 on the value of a variable, implied by a conditional jump. For example,
1365 following "if (x == 2)", the then branch may be optimized as though the
1366 conditional performed an "explicit set", in this example, "x = 2". This
1367 function records the set patterns that are implicit at the start of each
1370 If an implicit set is found but the set is implicit on a critical edge,
1371 this critical edge is split.
1373 Return true if the CFG was modified, false otherwise. */
1376 find_implicit_sets (void)
1378 basic_block bb
, dest
;
1380 unsigned int count
= 0;
1381 bool edges_split
= false;
1382 size_t implicit_sets_size
= last_basic_block_for_fn (cfun
) + 10;
1384 implicit_sets
= XCNEWVEC (rtx
, implicit_sets_size
);
1386 FOR_EACH_BB_FN (bb
, cfun
)
1388 /* Check for more than one successor. */
1389 if (EDGE_COUNT (bb
->succs
) <= 1)
1392 cond
= fis_get_condition (BB_END (bb
));
1394 /* If no condition is found or if it isn't of a suitable form,
1396 if (! cond
|| ! implicit_set_cond_p (cond
))
1399 dest
= GET_CODE (cond
) == EQ
1400 ? BRANCH_EDGE (bb
)->dest
: FALLTHRU_EDGE (bb
)->dest
;
1402 /* If DEST doesn't go anywhere, ignore it. */
1403 if (! dest
|| dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1406 /* We have found a suitable implicit set. Try to record it now as
1407 a SET in DEST. If DEST has more than one predecessor, the edge
1408 between BB and DEST is a critical edge and we must split it,
1409 because we can only record one implicit set per DEST basic block. */
1410 if (! single_pred_p (dest
))
1412 dest
= split_edge (find_edge (bb
, dest
));
1416 if (implicit_sets_size
<= (size_t) dest
->index
)
1418 size_t old_implicit_sets_size
= implicit_sets_size
;
1419 implicit_sets_size
*= 2;
1420 implicit_sets
= XRESIZEVEC (rtx
, implicit_sets
, implicit_sets_size
);
1421 memset (implicit_sets
+ old_implicit_sets_size
, 0,
1422 (implicit_sets_size
- old_implicit_sets_size
) * sizeof (rtx
));
1425 new_rtx
= gen_rtx_SET (XEXP (cond
, 0), XEXP (cond
, 1));
1426 implicit_sets
[dest
->index
] = new_rtx
;
1429 fprintf (dump_file
, "Implicit set of reg %d in ",
1430 REGNO (XEXP (cond
, 0)));
1431 fprintf (dump_file
, "basic block %d\n", dest
->index
);
1437 fprintf (dump_file
, "Found %d implicit sets\n", count
);
1439 /* Confess our sins. */
1443 /* Bypass conditional jumps. */
1445 /* The value of last_basic_block at the beginning of the jump_bypass
1446 pass. The use of redirect_edge_and_branch_force may introduce new
1447 basic blocks, but the data flow analysis is only valid for basic
1448 block indices less than bypass_last_basic_block. */
1450 static int bypass_last_basic_block
;
1452 /* Find a set of REGNO to a constant that is available at the end of basic
1453 block BB. Return NULL if no such set is found. Based heavily upon
1456 static struct cprop_expr
*
1457 find_bypass_set (int regno
, int bb
)
1459 struct cprop_expr
*result
= 0;
1464 struct cprop_expr
*set
= lookup_set (regno
, &set_hash_table
);
1468 if (bitmap_bit_p (cprop_avout
[bb
], set
->bitmap_index
))
1470 set
= next_set (regno
, set
);
1477 if (cprop_constant_p (src
))
1483 regno
= REGNO (src
);
1488 /* Subroutine of bypass_block that checks whether a pseudo is killed by
1489 any of the instructions inserted on an edge. Jump bypassing places
1490 condition code setters on CFG edges using insert_insn_on_edge. This
1491 function is required to check that our data flow analysis is still
1492 valid prior to commit_edge_insertions. */
1495 reg_killed_on_edge (const_rtx reg
, const_edge e
)
1499 for (insn
= e
->insns
.r
; insn
; insn
= NEXT_INSN (insn
))
1500 if (INSN_P (insn
) && reg_set_p (reg
, insn
))
1506 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1507 basic block BB which has more than one predecessor. If not NULL, SETCC
1508 is the first instruction of BB, which is immediately followed by JUMP_INSN
1509 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1510 Returns nonzero if a change was made.
1512 During the jump bypassing pass, we may place copies of SETCC instructions
1513 on CFG edges. The following routine must be careful to pay attention to
1514 these inserted insns when performing its transformations. */
1517 bypass_block (basic_block bb
, rtx_insn
*setcc
, rtx_insn
*jump
)
1523 int may_be_loop_header
= false;
1528 insn
= (setcc
!= NULL
) ? setcc
: jump
;
1530 /* Determine set of register uses in INSN. */
1532 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1533 note
= find_reg_equal_equiv_note (insn
);
1535 find_used_regs (&XEXP (note
, 0), NULL
);
1539 /* If we are to preserve loop structure then do not bypass
1540 a loop header. This will either rotate the loop, create
1541 multiple entry loops or even irreducible regions. */
1542 if (bb
== bb
->loop_father
->header
)
1547 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1548 if (e
->flags
& EDGE_DFS_BACK
)
1550 may_be_loop_header
= true;
1556 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
1560 if (e
->flags
& EDGE_COMPLEX
)
1566 /* We can't redirect edges from new basic blocks. */
1567 if (e
->src
->index
>= bypass_last_basic_block
)
1573 /* The irreducible loops created by redirecting of edges entering the
1574 loop from outside would decrease effectiveness of some of the
1575 following optimizations, so prevent this. */
1576 if (may_be_loop_header
1577 && !(e
->flags
& EDGE_DFS_BACK
))
1583 for (i
= 0; i
< reg_use_count
; i
++)
1585 rtx reg_used
= reg_use_table
[i
];
1586 unsigned int regno
= REGNO (reg_used
);
1587 basic_block dest
, old_dest
;
1588 struct cprop_expr
*set
;
1591 set
= find_bypass_set (regno
, e
->src
->index
);
1596 /* Check the data flow is valid after edge insertions. */
1597 if (e
->insns
.r
&& reg_killed_on_edge (reg_used
, e
))
1600 src
= SET_SRC (pc_set (jump
));
1603 src
= simplify_replace_rtx (src
,
1604 SET_DEST (PATTERN (setcc
)),
1605 SET_SRC (PATTERN (setcc
)));
1607 new_rtx
= simplify_replace_rtx (src
, reg_used
, set
->src
);
1609 /* Jump bypassing may have already placed instructions on
1610 edges of the CFG. We can't bypass an outgoing edge that
1611 has instructions associated with it, as these insns won't
1612 get executed if the incoming edge is redirected. */
1613 if (new_rtx
== pc_rtx
)
1615 edest
= FALLTHRU_EDGE (bb
);
1616 dest
= edest
->insns
.r
? NULL
: edest
->dest
;
1618 else if (GET_CODE (new_rtx
) == LABEL_REF
)
1620 dest
= BLOCK_FOR_INSN (XEXP (new_rtx
, 0));
1621 /* Don't bypass edges containing instructions. */
1622 edest
= find_edge (bb
, dest
);
1623 if (edest
&& edest
->insns
.r
)
1629 /* Avoid unification of the edge with other edges from original
1630 branch. We would end up emitting the instruction on "both"
1632 if (dest
&& setcc
&& !CC0_P (SET_DEST (PATTERN (setcc
)))
1633 && find_edge (e
->src
, dest
))
1639 && dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1641 redirect_edge_and_branch_force (e
, dest
);
1643 /* Copy the register setter to the redirected edge.
1644 Don't copy CC0 setters, as CC0 is dead after jump. */
1647 rtx pat
= PATTERN (setcc
);
1648 if (!CC0_P (SET_DEST (pat
)))
1649 insert_insn_on_edge (copy_insn (pat
), e
);
1652 if (dump_file
!= NULL
)
1654 fprintf (dump_file
, "JUMP-BYPASS: Proved reg %d "
1655 "in jump_insn %d equals constant ",
1656 regno
, INSN_UID (jump
));
1657 print_rtl (dump_file
, set
->src
);
1658 fprintf (dump_file
, "\n\t when BB %d is entered from "
1659 "BB %d. Redirect edge %d->%d to %d.\n",
1660 old_dest
->index
, e
->src
->index
, e
->src
->index
,
1661 old_dest
->index
, dest
->index
);
1674 /* Find basic blocks with more than one predecessor that only contain a
1675 single conditional jump. If the result of the comparison is known at
1676 compile-time from any incoming edge, redirect that edge to the
1677 appropriate target. Return nonzero if a change was made.
1679 This function is now mis-named, because we also handle indirect jumps. */
1682 bypass_conditional_jumps (void)
1690 /* Note we start at block 1. */
1691 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1694 bypass_last_basic_block
= last_basic_block_for_fn (cfun
);
1695 mark_dfs_back_edges ();
1698 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
->next_bb
,
1699 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1701 /* Check for more than one predecessor. */
1702 if (!single_pred_p (bb
))
1705 FOR_BB_INSNS (bb
, insn
)
1706 if (DEBUG_INSN_P (insn
))
1708 else if (NONJUMP_INSN_P (insn
))
1712 if (GET_CODE (PATTERN (insn
)) != SET
)
1715 dest
= SET_DEST (PATTERN (insn
));
1716 if (REG_P (dest
) || CC0_P (dest
))
1721 else if (JUMP_P (insn
))
1723 if ((any_condjump_p (insn
) || computed_jump_p (insn
))
1724 && onlyjump_p (insn
))
1725 changed
|= bypass_block (bb
, setcc
, insn
);
1728 else if (INSN_P (insn
))
1733 /* If we bypassed any register setting insns, we inserted a
1734 copy on the redirected edge. These need to be committed. */
1736 commit_edge_insertions ();
1741 /* Return true if the graph is too expensive to optimize. PASS is the
1742 optimization about to be performed. */
1745 is_too_expensive (const char *pass
)
1747 /* Trying to perform global optimizations on flow graphs which have
1748 a high connectivity will take a long time and is unlikely to be
1749 particularly useful.
1751 In normal circumstances a cfg should have about twice as many
1752 edges as blocks. But we do not want to punish small functions
1753 which have a couple switch statements. Rather than simply
1754 threshold the number of blocks, uses something with a more
1755 graceful degradation. */
1756 if (n_edges_for_fn (cfun
) > 20000 + n_basic_blocks_for_fn (cfun
) * 4)
1758 warning (OPT_Wdisabled_optimization
,
1759 "%s: %d basic blocks and %d edges/basic block",
1760 pass
, n_basic_blocks_for_fn (cfun
),
1761 n_edges_for_fn (cfun
) / n_basic_blocks_for_fn (cfun
));
1766 /* If allocating memory for the cprop bitmap would take up too much
1767 storage it's better just to disable the optimization. */
1768 if ((n_basic_blocks_for_fn (cfun
)
1769 * SBITMAP_SET_SIZE (max_reg_num ())
1770 * sizeof (SBITMAP_ELT_TYPE
)) > MAX_GCSE_MEMORY
)
1772 warning (OPT_Wdisabled_optimization
,
1773 "%s: %d basic blocks and %d registers",
1774 pass
, n_basic_blocks_for_fn (cfun
), max_reg_num ());
1782 /* Main function for the CPROP pass. */
1785 one_cprop_pass (void)
1790 /* Return if there's nothing to do, or it is too expensive. */
1791 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1
1792 || is_too_expensive (_ ("const/copy propagation disabled")))
1795 global_const_prop_count
= local_const_prop_count
= 0;
1796 global_copy_prop_count
= local_copy_prop_count
= 0;
1799 gcc_obstack_init (&cprop_obstack
);
1801 /* Do a local const/copy propagation pass first. The global pass
1802 only handles global opportunities.
1803 If the local pass changes something, remove any unreachable blocks
1804 because the CPROP global dataflow analysis may get into infinite
1805 loops for CFGs with unreachable blocks.
1807 FIXME: This local pass should not be necessary after CSE (but for
1808 some reason it still is). It is also (proven) not necessary
1809 to run the local pass right after FWPWOP.
1811 FIXME: The global analysis would not get into infinite loops if it
1812 would use the DF solver (via df_simple_dataflow) instead of
1813 the solver implemented in this file. */
1814 changed
|= local_cprop_pass ();
1816 delete_unreachable_blocks ();
1818 /* Determine implicit sets. This may change the CFG (split critical
1819 edges if that exposes an implicit set).
1820 Note that find_implicit_sets() does not rely on up-to-date DF caches
1821 so that we do not have to re-run df_analyze() even if local CPROP
1823 ??? This could run earlier so that any uncovered implicit sets
1824 sets could be exploited in local_cprop_pass() also. Later. */
1825 changed
|= find_implicit_sets ();
1827 /* If local_cprop_pass() or find_implicit_sets() changed something,
1828 run df_analyze() to bring all insn caches up-to-date, and to take
1829 new basic blocks from edge splitting on the DF radar.
1830 NB: This also runs the fast DCE pass, because execute_rtl_cprop
1831 sets DF_LR_RUN_DCE. */
1835 /* Initialize implicit_set_indexes array. */
1836 implicit_set_indexes
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1837 for (i
= 0; i
< last_basic_block_for_fn (cfun
); i
++)
1838 implicit_set_indexes
[i
] = -1;
1840 alloc_hash_table (&set_hash_table
);
1841 compute_hash_table (&set_hash_table
);
1843 /* Free implicit_sets before peak usage. */
1844 free (implicit_sets
);
1845 implicit_sets
= NULL
;
1848 dump_hash_table (dump_file
, "SET", &set_hash_table
);
1849 if (set_hash_table
.n_elems
> 0)
1854 alloc_cprop_mem (last_basic_block_for_fn (cfun
),
1855 set_hash_table
.n_elems
);
1856 compute_cprop_data ();
1858 free (implicit_set_indexes
);
1859 implicit_set_indexes
= NULL
;
1861 /* Allocate vars to track sets of regs. */
1862 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
1864 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
->next_bb
,
1865 EXIT_BLOCK_PTR_FOR_FN (cfun
),
1868 /* Reset tables used to keep track of what's still valid [since
1869 the start of the block]. */
1870 reset_opr_set_tables ();
1872 FOR_BB_INSNS (bb
, insn
)
1875 changed
|= cprop_insn (insn
);
1877 /* Keep track of everything modified by this insn. */
1878 /* ??? Need to be careful w.r.t. mods done to INSN.
1879 Don't call mark_oprs_set if we turned the
1880 insn into a NOTE, or deleted the insn. */
1881 if (! NOTE_P (insn
) && ! insn
->deleted ())
1882 mark_oprs_set (insn
);
1886 changed
|= bypass_conditional_jumps ();
1888 FREE_REG_SET (reg_set_bitmap
);
1893 free (implicit_set_indexes
);
1894 implicit_set_indexes
= NULL
;
1897 free_hash_table (&set_hash_table
);
1898 obstack_free (&cprop_obstack
, NULL
);
1902 fprintf (dump_file
, "CPROP of %s, %d basic blocks, %d bytes needed, ",
1903 current_function_name (), n_basic_blocks_for_fn (cfun
),
1905 fprintf (dump_file
, "%d local const props, %d local copy props, ",
1906 local_const_prop_count
, local_copy_prop_count
);
1907 fprintf (dump_file
, "%d global const props, %d global copy props\n\n",
1908 global_const_prop_count
, global_copy_prop_count
);
1914 /* All the passes implemented in this file. Each pass has its
1915 own gate and execute function, and at the end of the file a
1916 pass definition for passes.c.
1918 We do not construct an accurate cfg in functions which call
1919 setjmp, so none of these passes runs if the function calls
1921 FIXME: Should just handle setjmp via REG_SETJMP notes. */
1924 execute_rtl_cprop (void)
1927 delete_unreachable_blocks ();
1928 df_set_flags (DF_LR_RUN_DCE
);
1930 changed
= one_cprop_pass ();
1931 flag_rerun_cse_after_global_opts
|= changed
;
1933 cleanup_cfg (CLEANUP_CFG_CHANGED
);
1939 const pass_data pass_data_rtl_cprop
=
1941 RTL_PASS
, /* type */
1943 OPTGROUP_NONE
, /* optinfo_flags */
1944 TV_CPROP
, /* tv_id */
1945 PROP_cfglayout
, /* properties_required */
1946 0, /* properties_provided */
1947 0, /* properties_destroyed */
1948 0, /* todo_flags_start */
1949 TODO_df_finish
, /* todo_flags_finish */
1952 class pass_rtl_cprop
: public rtl_opt_pass
1955 pass_rtl_cprop (gcc::context
*ctxt
)
1956 : rtl_opt_pass (pass_data_rtl_cprop
, ctxt
)
1959 /* opt_pass methods: */
1960 opt_pass
* clone () { return new pass_rtl_cprop (m_ctxt
); }
1961 virtual bool gate (function
*fun
)
1963 return optimize
> 0 && flag_gcse
1964 && !fun
->calls_setjmp
1968 virtual unsigned int execute (function
*) { return execute_rtl_cprop (); }
1970 }; // class pass_rtl_cprop
1975 make_pass_rtl_cprop (gcc::context
*ctxt
)
1977 return new pass_rtl_cprop (ctxt
);