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"
28 #include "diagnostic-core.h"
34 #include "insn-config.h"
39 #include "cfgcleanup.h"
50 #include "alloc-pool.h"
54 #include "tree-pass.h"
60 /* An obstack for our working variables. */
61 static struct obstack cprop_obstack
;
63 /* Occurrence of an expression.
64 There is one per basic block. If a pattern appears more than once the
65 last appearance is used. */
69 /* Next occurrence of this expression. */
70 struct cprop_occr
*next
;
71 /* The insn that computes the expression. */
75 typedef struct cprop_occr
*occr_t
;
77 /* Hash table entry for assignment expressions. */
81 /* The expression (DEST := SRC). */
85 /* Index in the available expression bitmaps. */
87 /* Next entry with the same hash. */
88 struct cprop_expr
*next_same_hash
;
89 /* List of available occurrence in basic blocks in the function.
90 An "available occurrence" is one that is the last occurrence in the
91 basic block and whose operands are not modified by following statements
92 in the basic block [including this insn]. */
93 struct cprop_occr
*avail_occr
;
96 /* Hash table for copy propagation expressions.
97 Each hash table is an array of buckets.
98 ??? It is known that if it were an array of entries, structure elements
99 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
100 not clear whether in the final analysis a sufficient amount of memory would
101 be saved as the size of the available expression bitmaps would be larger
102 [one could build a mapping table without holes afterwards though].
103 Someday I'll perform the computation and figure it out. */
108 This is an array of `set_hash_table_size' elements. */
109 struct cprop_expr
**table
;
111 /* Size of the hash table, in elements. */
114 /* Number of hash table elements. */
115 unsigned int n_elems
;
118 /* Copy propagation hash table. */
119 static struct hash_table_d set_hash_table
;
121 /* Array of implicit set patterns indexed by basic block index. */
122 static rtx
*implicit_sets
;
124 /* Array of indexes of expressions for implicit set patterns indexed by basic
125 block index. In other words, implicit_set_indexes[i] is the bitmap_index
126 of the expression whose RTX is implicit_sets[i]. */
127 static int *implicit_set_indexes
;
129 /* Bitmap containing one bit for each register in the program.
130 Used when performing GCSE to track which registers have been set since
131 the start or end of the basic block while traversing that block. */
132 static regset reg_set_bitmap
;
134 /* Various variables for statistics gathering. */
136 /* Memory used in a pass.
137 This isn't intended to be absolutely precise. Its intent is only
138 to keep an eye on memory usage. */
139 static int bytes_used
;
141 /* Number of local constants propagated. */
142 static int local_const_prop_count
;
143 /* Number of local copies propagated. */
144 static int local_copy_prop_count
;
145 /* Number of global constants propagated. */
146 static int global_const_prop_count
;
147 /* Number of global copies propagated. */
148 static int global_copy_prop_count
;
150 #define GOBNEW(T) ((T *) cprop_alloc (sizeof (T)))
151 #define GOBNEWVAR(T, S) ((T *) cprop_alloc ((S)))
153 /* Cover function to obstack_alloc. */
156 cprop_alloc (unsigned long size
)
159 return obstack_alloc (&cprop_obstack
, size
);
162 /* Return nonzero if register X is unchanged from INSN to the end
163 of INSN's basic block. */
166 reg_available_p (const_rtx x
, const rtx_insn
*insn ATTRIBUTE_UNUSED
)
168 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
171 /* Hash a set of register REGNO.
173 Sets are hashed on the register that is set. This simplifies the PRE copy
176 ??? May need to make things more elaborate. Later, as necessary. */
179 hash_mod (int regno
, int hash_table_size
)
181 return (unsigned) regno
% hash_table_size
;
184 /* Insert assignment DEST:=SET from INSN in the hash table.
185 DEST is a register and SET is a register or a suitable constant.
186 If the assignment is already present in the table, record it as
187 the last occurrence in INSN's basic block.
188 IMPLICIT is true if it's an implicit set, false otherwise. */
191 insert_set_in_table (rtx dest
, rtx src
, rtx_insn
*insn
,
192 struct hash_table_d
*table
, bool implicit
)
196 struct cprop_expr
*cur_expr
, *last_expr
= NULL
;
197 struct cprop_occr
*cur_occr
;
199 hash
= hash_mod (REGNO (dest
), table
->size
);
201 for (cur_expr
= table
->table
[hash
]; cur_expr
;
202 cur_expr
= cur_expr
->next_same_hash
)
204 if (dest
== cur_expr
->dest
205 && src
== cur_expr
->src
)
210 last_expr
= cur_expr
;
215 cur_expr
= GOBNEW (struct cprop_expr
);
216 bytes_used
+= sizeof (struct cprop_expr
);
217 if (table
->table
[hash
] == NULL
)
218 /* This is the first pattern that hashed to this index. */
219 table
->table
[hash
] = cur_expr
;
221 /* Add EXPR to end of this hash chain. */
222 last_expr
->next_same_hash
= cur_expr
;
224 /* Set the fields of the expr element.
225 We must copy X because it can be modified when copy propagation is
226 performed on its operands. */
227 cur_expr
->dest
= copy_rtx (dest
);
228 cur_expr
->src
= copy_rtx (src
);
229 cur_expr
->bitmap_index
= table
->n_elems
++;
230 cur_expr
->next_same_hash
= NULL
;
231 cur_expr
->avail_occr
= NULL
;
234 /* Now record the occurrence. */
235 cur_occr
= cur_expr
->avail_occr
;
238 && BLOCK_FOR_INSN (cur_occr
->insn
) == BLOCK_FOR_INSN (insn
))
240 /* Found another instance of the expression in the same basic block.
241 Prefer this occurrence to the currently recorded one. We want
242 the last one in the block and the block is scanned from start
244 cur_occr
->insn
= insn
;
248 /* First occurrence of this expression in this basic block. */
249 cur_occr
= GOBNEW (struct cprop_occr
);
250 bytes_used
+= sizeof (struct cprop_occr
);
251 cur_occr
->insn
= insn
;
252 cur_occr
->next
= cur_expr
->avail_occr
;
253 cur_expr
->avail_occr
= cur_occr
;
256 /* Record bitmap_index of the implicit set in implicit_set_indexes. */
258 implicit_set_indexes
[BLOCK_FOR_INSN (insn
)->index
]
259 = cur_expr
->bitmap_index
;
262 /* Determine whether the rtx X should be treated as a constant for CPROP.
263 Since X might be inserted more than once we have to take care that it
267 cprop_constant_p (const_rtx x
)
269 return CONSTANT_P (x
) && (GET_CODE (x
) != CONST
|| shared_const_p (x
));
272 /* Determine whether the rtx X should be treated as a register that can
273 be propagated. Any pseudo-register is fine. */
276 cprop_reg_p (const_rtx x
)
278 return REG_P (x
) && !HARD_REGISTER_P (x
);
281 /* Scan SET present in INSN and add an entry to the hash TABLE.
282 IMPLICIT is true if it's an implicit set, false otherwise. */
285 hash_scan_set (rtx set
, rtx_insn
*insn
, struct hash_table_d
*table
,
288 rtx src
= SET_SRC (set
);
289 rtx dest
= SET_DEST (set
);
291 if (cprop_reg_p (dest
)
292 && reg_available_p (dest
, insn
)
293 && can_copy_p (GET_MODE (dest
)))
295 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
297 This allows us to do a single CPROP pass and still eliminate
298 redundant constants, addresses or other expressions that are
299 constructed with multiple instructions.
301 However, keep the original SRC if INSN is a simple reg-reg move. In
302 In this case, there will almost always be a REG_EQUAL note on the
303 insn that sets SRC. By recording the REG_EQUAL value here as SRC
304 for INSN, we miss copy propagation opportunities.
306 Note that this does not impede profitable constant propagations. We
307 "look through" reg-reg sets in lookup_set. */
308 rtx note
= find_reg_equal_equiv_note (insn
);
310 && REG_NOTE_KIND (note
) == REG_EQUAL
312 && cprop_constant_p (XEXP (note
, 0)))
313 src
= XEXP (note
, 0), set
= gen_rtx_SET (dest
, src
);
315 /* Record sets for constant/copy propagation. */
316 if ((cprop_reg_p (src
)
318 && reg_available_p (src
, insn
))
319 || cprop_constant_p (src
))
320 insert_set_in_table (dest
, src
, insn
, table
, implicit
);
324 /* Process INSN and add hash table entries as appropriate. */
327 hash_scan_insn (rtx_insn
*insn
, struct hash_table_d
*table
)
329 rtx pat
= PATTERN (insn
);
332 /* Pick out the sets of INSN and for other forms of instructions record
333 what's been modified. */
335 if (GET_CODE (pat
) == SET
)
336 hash_scan_set (pat
, insn
, table
, false);
337 else if (GET_CODE (pat
) == PARALLEL
)
338 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
340 rtx x
= XVECEXP (pat
, 0, i
);
342 if (GET_CODE (x
) == SET
)
343 hash_scan_set (x
, insn
, table
, false);
347 /* Dump the hash table TABLE to file FILE under the name NAME. */
350 dump_hash_table (FILE *file
, const char *name
, struct hash_table_d
*table
)
353 /* Flattened out table, so it's printed in proper order. */
354 struct cprop_expr
**flat_table
;
355 unsigned int *hash_val
;
356 struct cprop_expr
*expr
;
358 flat_table
= XCNEWVEC (struct cprop_expr
*, table
->n_elems
);
359 hash_val
= XNEWVEC (unsigned int, table
->n_elems
);
361 for (i
= 0; i
< (int) table
->size
; i
++)
362 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
364 flat_table
[expr
->bitmap_index
] = expr
;
365 hash_val
[expr
->bitmap_index
] = i
;
368 fprintf (file
, "%s hash table (%d buckets, %d entries)\n",
369 name
, table
->size
, table
->n_elems
);
371 for (i
= 0; i
< (int) table
->n_elems
; i
++)
372 if (flat_table
[i
] != 0)
374 expr
= flat_table
[i
];
375 fprintf (file
, "Index %d (hash value %d)\n ",
376 expr
->bitmap_index
, hash_val
[i
]);
377 print_rtl (file
, expr
->dest
);
378 fprintf (file
, " := ");
379 print_rtl (file
, expr
->src
);
380 fprintf (file
, "\n");
383 fprintf (file
, "\n");
389 /* Record as unavailable all registers that are DEF operands of INSN. */
392 make_set_regs_unavailable (rtx_insn
*insn
)
396 FOR_EACH_INSN_DEF (def
, insn
)
397 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (def
));
400 /* Top level function to create an assignment hash table.
402 Assignment entries are placed in the hash table if
403 - they are of the form (set (pseudo-reg) src),
404 - src is something we want to perform const/copy propagation on,
405 - none of the operands or target are subsequently modified in the block
407 Currently src must be a pseudo-reg or a const_int.
409 TABLE is the table computed. */
412 compute_hash_table_work (struct hash_table_d
*table
)
416 /* Allocate vars to track sets of regs. */
417 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
419 FOR_EACH_BB_FN (bb
, cfun
)
423 /* Reset tables used to keep track of what's not yet invalid [since
424 the end of the block]. */
425 CLEAR_REG_SET (reg_set_bitmap
);
427 /* Go over all insns from the last to the first. This is convenient
428 for tracking available registers, i.e. not set between INSN and
429 the end of the basic block BB. */
430 FOR_BB_INSNS_REVERSE (bb
, insn
)
432 /* Only real insns are interesting. */
433 if (!NONDEBUG_INSN_P (insn
))
436 /* Record interesting sets from INSN in the hash table. */
437 hash_scan_insn (insn
, table
);
439 /* Any registers set in INSN will make SETs above it not AVAIL. */
440 make_set_regs_unavailable (insn
);
443 /* Insert implicit sets in the hash table, pretending they appear as
444 insns at the head of the basic block. */
445 if (implicit_sets
[bb
->index
] != NULL_RTX
)
446 hash_scan_set (implicit_sets
[bb
->index
], BB_HEAD (bb
), table
, true);
449 FREE_REG_SET (reg_set_bitmap
);
452 /* Allocate space for the set/expr hash TABLE.
453 It is used to determine the number of buckets to use. */
456 alloc_hash_table (struct hash_table_d
*table
)
460 n
= get_max_insn_count ();
463 if (table
->size
< 11)
466 /* Attempt to maintain efficient use of hash table.
467 Making it an odd number is simplest for now.
468 ??? Later take some measurements. */
470 n
= table
->size
* sizeof (struct cprop_expr
*);
471 table
->table
= XNEWVAR (struct cprop_expr
*, n
);
474 /* Free things allocated by alloc_hash_table. */
477 free_hash_table (struct hash_table_d
*table
)
482 /* Compute the hash TABLE for doing copy/const propagation or
483 expression hash table. */
486 compute_hash_table (struct hash_table_d
*table
)
488 /* Initialize count of number of entries in hash table. */
490 memset (table
->table
, 0, table
->size
* sizeof (struct cprop_expr
*));
492 compute_hash_table_work (table
);
495 /* Expression tracking support. */
497 /* Lookup REGNO in the set TABLE. The result is a pointer to the
498 table entry, or NULL if not found. */
500 static struct cprop_expr
*
501 lookup_set (unsigned int regno
, struct hash_table_d
*table
)
503 unsigned int hash
= hash_mod (regno
, table
->size
);
504 struct cprop_expr
*expr
;
506 expr
= table
->table
[hash
];
508 while (expr
&& REGNO (expr
->dest
) != regno
)
509 expr
= expr
->next_same_hash
;
514 /* Return the next entry for REGNO in list EXPR. */
516 static struct cprop_expr
*
517 next_set (unsigned int regno
, struct cprop_expr
*expr
)
520 expr
= expr
->next_same_hash
;
521 while (expr
&& REGNO (expr
->dest
) != regno
);
526 /* Reset tables used to keep track of what's still available [since the
527 start of the block]. */
530 reset_opr_set_tables (void)
532 /* Maintain a bitmap of which regs have been set since beginning of
534 CLEAR_REG_SET (reg_set_bitmap
);
537 /* Return nonzero if the register X has not been set yet [since the
538 start of the basic block containing INSN]. */
541 reg_not_set_p (const_rtx x
, const rtx_insn
*insn ATTRIBUTE_UNUSED
)
543 return ! REGNO_REG_SET_P (reg_set_bitmap
, REGNO (x
));
546 /* Record things set by INSN.
547 This data is used by reg_not_set_p. */
550 mark_oprs_set (rtx_insn
*insn
)
554 FOR_EACH_INSN_DEF (def
, insn
)
555 SET_REGNO_REG_SET (reg_set_bitmap
, DF_REF_REGNO (def
));
558 /* Compute copy/constant propagation working variables. */
560 /* Local properties of assignments. */
561 static sbitmap
*cprop_avloc
;
562 static sbitmap
*cprop_kill
;
564 /* Global properties of assignments (computed from the local properties). */
565 static sbitmap
*cprop_avin
;
566 static sbitmap
*cprop_avout
;
568 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
569 basic blocks. N_SETS is the number of sets. */
572 alloc_cprop_mem (int n_blocks
, int n_sets
)
574 cprop_avloc
= sbitmap_vector_alloc (n_blocks
, n_sets
);
575 cprop_kill
= sbitmap_vector_alloc (n_blocks
, n_sets
);
577 cprop_avin
= sbitmap_vector_alloc (n_blocks
, n_sets
);
578 cprop_avout
= sbitmap_vector_alloc (n_blocks
, n_sets
);
581 /* Free vars used by copy/const propagation. */
584 free_cprop_mem (void)
586 sbitmap_vector_free (cprop_avloc
);
587 sbitmap_vector_free (cprop_kill
);
588 sbitmap_vector_free (cprop_avin
);
589 sbitmap_vector_free (cprop_avout
);
592 /* Compute the local properties of each recorded expression.
594 Local properties are those that are defined by the block, irrespective of
597 An expression is killed in a block if its operands, either DEST or SRC, are
598 modified in the block.
600 An expression is computed (locally available) in a block if it is computed
601 at least once and expression would contain the same value if the
602 computation was moved to the end of the block.
604 KILL and COMP are destination sbitmaps for recording local properties. */
607 compute_local_properties (sbitmap
*kill
, sbitmap
*comp
,
608 struct hash_table_d
*table
)
612 /* Initialize the bitmaps that were passed in. */
613 bitmap_vector_clear (kill
, last_basic_block_for_fn (cfun
));
614 bitmap_vector_clear (comp
, last_basic_block_for_fn (cfun
));
616 for (i
= 0; i
< table
->size
; i
++)
618 struct cprop_expr
*expr
;
620 for (expr
= table
->table
[i
]; expr
!= NULL
; expr
= expr
->next_same_hash
)
622 int indx
= expr
->bitmap_index
;
624 struct cprop_occr
*occr
;
626 /* For each definition of the destination pseudo-reg, the expression
627 is killed in the block where the definition is. */
628 for (def
= DF_REG_DEF_CHAIN (REGNO (expr
->dest
));
629 def
; def
= DF_REF_NEXT_REG (def
))
630 bitmap_set_bit (kill
[DF_REF_BB (def
)->index
], indx
);
632 /* If the source is a pseudo-reg, for each definition of the source,
633 the expression is killed in the block where the definition is. */
634 if (REG_P (expr
->src
))
635 for (def
= DF_REG_DEF_CHAIN (REGNO (expr
->src
));
636 def
; def
= DF_REF_NEXT_REG (def
))
637 bitmap_set_bit (kill
[DF_REF_BB (def
)->index
], indx
);
639 /* The occurrences recorded in avail_occr are exactly those that
640 are locally available in the block where they are. */
641 for (occr
= expr
->avail_occr
; occr
!= NULL
; occr
= occr
->next
)
643 bitmap_set_bit (comp
[BLOCK_FOR_INSN (occr
->insn
)->index
], indx
);
649 /* Hash table support. */
651 /* Top level routine to do the dataflow analysis needed by copy/const
655 compute_cprop_data (void)
659 compute_local_properties (cprop_kill
, cprop_avloc
, &set_hash_table
);
660 compute_available (cprop_avloc
, cprop_kill
, cprop_avout
, cprop_avin
);
662 /* Merge implicit sets into CPROP_AVIN. They are always available at the
663 entry of their basic block. We need to do this because 1) implicit sets
664 aren't recorded for the local pass so they cannot be propagated within
665 their basic block by this pass and 2) the global pass would otherwise
666 propagate them only in the successors of their basic block. */
667 FOR_EACH_BB_FN (bb
, cfun
)
669 int index
= implicit_set_indexes
[bb
->index
];
671 bitmap_set_bit (cprop_avin
[bb
->index
], index
);
675 /* Copy/constant propagation. */
677 /* Maximum number of register uses in an insn that we handle. */
680 /* Table of uses (registers, both hard and pseudo) found in an insn.
681 Allocated statically to avoid alloc/free complexity and overhead. */
682 static rtx reg_use_table
[MAX_USES
];
684 /* Index into `reg_use_table' while building it. */
685 static unsigned reg_use_count
;
687 /* Set up a list of register numbers used in INSN. The found uses are stored
688 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
689 and contains the number of uses in the table upon exit.
691 ??? If a register appears multiple times we will record it multiple times.
692 This doesn't hurt anything but it will slow things down. */
695 find_used_regs (rtx
*xptr
, void *data ATTRIBUTE_UNUSED
)
702 /* repeat is used to turn tail-recursion into iteration since GCC
703 can't do it when there's no return value. */
711 if (reg_use_count
== MAX_USES
)
714 reg_use_table
[reg_use_count
] = x
;
718 /* Recursively scan the operands of this expression. */
720 for (i
= GET_RTX_LENGTH (code
) - 1, fmt
= GET_RTX_FORMAT (code
); i
>= 0; i
--)
724 /* If we are about to do the last recursive call
725 needed at this level, change it into iteration.
726 This function is called enough to be worth it. */
733 find_used_regs (&XEXP (x
, i
), data
);
735 else if (fmt
[i
] == 'E')
736 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
737 find_used_regs (&XVECEXP (x
, i
, j
), data
);
741 /* Try to replace all uses of FROM in INSN with TO.
742 Return nonzero if successful. */
745 try_replace_reg (rtx from
, rtx to
, rtx_insn
*insn
)
747 rtx note
= find_reg_equal_equiv_note (insn
);
750 rtx set
= single_set (insn
);
752 bool check_rtx_costs
= true;
753 bool speed
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn
));
754 int old_cost
= set
? set_rtx_cost (set
, speed
) : 0;
757 || CONSTANT_P (SET_SRC (set
))
759 && REG_NOTE_KIND (note
) == REG_EQUAL
760 && (GET_CODE (XEXP (note
, 0)) == CONST
761 || CONSTANT_P (XEXP (note
, 0)))))
762 check_rtx_costs
= false;
764 /* Usually we substitute easy stuff, so we won't copy everything.
765 We however need to take care to not duplicate non-trivial CONST
769 validate_replace_src_group (from
, to
, insn
);
771 /* If TO is a constant, check the cost of the set after propagation
772 to the cost of the set before the propagation. If the cost is
773 higher, then do not replace FROM with TO. */
777 && set_rtx_cost (set
, speed
) > old_cost
)
784 if (num_changes_pending () && apply_change_group ())
787 /* Try to simplify SET_SRC if we have substituted a constant. */
788 if (success
&& set
&& CONSTANT_P (to
))
790 src
= simplify_rtx (SET_SRC (set
));
793 validate_change (insn
, &SET_SRC (set
), src
, 0);
796 /* If there is already a REG_EQUAL note, update the expression in it
797 with our replacement. */
798 if (note
!= 0 && REG_NOTE_KIND (note
) == REG_EQUAL
)
799 set_unique_reg_note (insn
, REG_EQUAL
,
800 simplify_replace_rtx (XEXP (note
, 0), from
, to
));
801 if (!success
&& set
&& reg_mentioned_p (from
, SET_SRC (set
)))
803 /* If above failed and this is a single set, try to simplify the source
804 of the set given our substitution. We could perhaps try this for
805 multiple SETs, but it probably won't buy us anything. */
806 src
= simplify_replace_rtx (SET_SRC (set
), from
, to
);
808 if (!rtx_equal_p (src
, SET_SRC (set
))
809 && validate_change (insn
, &SET_SRC (set
), src
, 0))
812 /* If we've failed perform the replacement, have a single SET to
813 a REG destination and don't yet have a note, add a REG_EQUAL note
814 to not lose information. */
815 if (!success
&& note
== 0 && set
!= 0 && REG_P (SET_DEST (set
)))
816 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
819 if (set
&& MEM_P (SET_DEST (set
)) && reg_mentioned_p (from
, SET_DEST (set
)))
821 /* Registers can also appear as uses in SET_DEST if it is a MEM.
822 We could perhaps try this for multiple SETs, but it probably
823 won't buy us anything. */
824 rtx dest
= simplify_replace_rtx (SET_DEST (set
), from
, to
);
826 if (!rtx_equal_p (dest
, SET_DEST (set
))
827 && validate_change (insn
, &SET_DEST (set
), dest
, 0))
831 /* REG_EQUAL may get simplified into register.
832 We don't allow that. Remove that note. This code ought
833 not to happen, because previous code ought to synthesize
834 reg-reg move, but be on the safe side. */
835 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
&& REG_P (XEXP (note
, 0)))
836 remove_note (insn
, note
);
841 /* Find a set of REGNOs that are available on entry to INSN's block. If found,
842 SET_RET[0] will be assigned a set with a register source and SET_RET[1] a
843 set with a constant source. If not found the corresponding entry is set to
847 find_avail_set (int regno
, rtx_insn
*insn
, struct cprop_expr
*set_ret
[2])
849 set_ret
[0] = set_ret
[1] = NULL
;
851 /* Loops are not possible here. To get a loop we would need two sets
852 available at the start of the block containing INSN. i.e. we would
853 need two sets like this available at the start of the block:
855 (set (reg X) (reg Y))
856 (set (reg Y) (reg X))
858 This can not happen since the set of (reg Y) would have killed the
859 set of (reg X) making it unavailable at the start of this block. */
863 struct cprop_expr
*set
= lookup_set (regno
, &set_hash_table
);
865 /* Find a set that is available at the start of the block
866 which contains INSN. */
869 if (bitmap_bit_p (cprop_avin
[BLOCK_FOR_INSN (insn
)->index
],
872 set
= next_set (regno
, set
);
875 /* If no available set was found we've reached the end of the
876 (possibly empty) copy chain. */
882 /* We know the set is available.
883 Now check that SRC is locally anticipatable (i.e. none of the
884 source operands have changed since the start of the block).
886 If the source operand changed, we may still use it for the next
887 iteration of this loop, but we may not use it for substitutions. */
889 if (cprop_constant_p (src
))
891 else if (reg_not_set_p (src
, insn
))
894 /* If the source of the set is anything except a register, then
895 we have reached the end of the copy chain. */
899 /* Follow the copy chain, i.e. start another iteration of the loop
900 and see if we have an available copy into SRC. */
905 /* Subroutine of cprop_insn that tries to propagate constants into
906 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
907 it is the instruction that immediately precedes JUMP, and must be a
908 single SET of a register. FROM is what we will try to replace,
909 SRC is the constant we will try to substitute for it. Return nonzero
910 if a change was made. */
913 cprop_jump (basic_block bb
, rtx_insn
*setcc
, rtx_insn
*jump
, rtx from
, rtx src
)
915 rtx new_rtx
, set_src
, note_src
;
916 rtx set
= pc_set (jump
);
917 rtx note
= find_reg_equal_equiv_note (jump
);
921 note_src
= XEXP (note
, 0);
922 if (GET_CODE (note_src
) == EXPR_LIST
)
925 else note_src
= NULL_RTX
;
927 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
928 set_src
= note_src
? note_src
: SET_SRC (set
);
930 /* First substitute the SETCC condition into the JUMP instruction,
931 then substitute that given values into this expanded JUMP. */
932 if (setcc
!= NULL_RTX
933 && !modified_between_p (from
, setcc
, jump
)
934 && !modified_between_p (src
, setcc
, jump
))
937 rtx setcc_set
= single_set (setcc
);
938 rtx setcc_note
= find_reg_equal_equiv_note (setcc
);
939 setcc_src
= (setcc_note
&& GET_CODE (XEXP (setcc_note
, 0)) != EXPR_LIST
)
940 ? XEXP (setcc_note
, 0) : SET_SRC (setcc_set
);
941 set_src
= simplify_replace_rtx (set_src
, SET_DEST (setcc_set
),
947 new_rtx
= simplify_replace_rtx (set_src
, from
, src
);
949 /* If no simplification can be made, then try the next register. */
950 if (rtx_equal_p (new_rtx
, SET_SRC (set
)))
953 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
954 if (new_rtx
== pc_rtx
)
958 /* Ensure the value computed inside the jump insn to be equivalent
959 to one computed by setcc. */
960 if (setcc
&& modified_in_p (new_rtx
, setcc
))
962 if (! validate_unshare_change (jump
, &SET_SRC (set
), new_rtx
, 0))
964 /* When (some) constants are not valid in a comparison, and there
965 are two registers to be replaced by constants before the entire
966 comparison can be folded into a constant, we need to keep
967 intermediate information in REG_EQUAL notes. For targets with
968 separate compare insns, such notes are added by try_replace_reg.
969 When we have a combined compare-and-branch instruction, however,
970 we need to attach a note to the branch itself to make this
971 optimization work. */
973 if (!rtx_equal_p (new_rtx
, note_src
))
974 set_unique_reg_note (jump
, REG_EQUAL
, copy_rtx (new_rtx
));
978 /* Remove REG_EQUAL note after simplification. */
980 remove_note (jump
, note
);
983 /* Delete the cc0 setter. */
984 if (HAVE_cc0
&& setcc
!= NULL
&& CC0_P (SET_DEST (single_set (setcc
))))
987 global_const_prop_count
++;
988 if (dump_file
!= NULL
)
991 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with"
992 "constant ", REGNO (from
), INSN_UID (jump
));
993 print_rtl (dump_file
, src
);
994 fprintf (dump_file
, "\n");
996 purge_dead_edges (bb
);
998 /* If a conditional jump has been changed into unconditional jump, remove
999 the jump and make the edge fallthru - this is always called in
1001 if (new_rtx
!= pc_rtx
&& simplejump_p (jump
))
1006 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1007 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1008 && BB_HEAD (e
->dest
) == JUMP_LABEL (jump
))
1010 e
->flags
|= EDGE_FALLTHRU
;
1019 /* Subroutine of cprop_insn that tries to propagate constants. FROM is what
1020 we will try to replace, SRC is the constant we will try to substitute for
1021 it and INSN is the instruction where this will be happening. */
1024 constprop_register (rtx from
, rtx src
, rtx_insn
*insn
)
1028 /* Check for reg or cc0 setting instructions followed by
1029 conditional branch instructions first. */
1030 if ((sset
= single_set (insn
)) != NULL
1032 && any_condjump_p (NEXT_INSN (insn
)) && onlyjump_p (NEXT_INSN (insn
)))
1034 rtx dest
= SET_DEST (sset
);
1035 if ((REG_P (dest
) || CC0_P (dest
))
1036 && cprop_jump (BLOCK_FOR_INSN (insn
), insn
, NEXT_INSN (insn
),
1041 /* Handle normal insns next. */
1042 if (NONJUMP_INSN_P (insn
) && try_replace_reg (from
, src
, insn
))
1045 /* Try to propagate a CONST_INT into a conditional jump.
1046 We're pretty specific about what we will handle in this
1047 code, we can extend this as necessary over time.
1049 Right now the insn in question must look like
1050 (set (pc) (if_then_else ...)) */
1051 else if (any_condjump_p (insn
) && onlyjump_p (insn
))
1052 return cprop_jump (BLOCK_FOR_INSN (insn
), NULL
, insn
, from
, src
);
1056 /* Perform constant and copy propagation on INSN.
1057 Return nonzero if a change was made. */
1060 cprop_insn (rtx_insn
*insn
)
1063 int changed
= 0, changed_this_round
;
1068 changed_this_round
= 0;
1070 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1072 /* We may win even when propagating constants into notes. */
1073 note
= find_reg_equal_equiv_note (insn
);
1075 find_used_regs (&XEXP (note
, 0), NULL
);
1077 for (i
= 0; i
< reg_use_count
; i
++)
1079 rtx reg_used
= reg_use_table
[i
];
1080 unsigned int regno
= REGNO (reg_used
);
1081 rtx src_cst
= NULL
, src_reg
= NULL
;
1082 struct cprop_expr
*set
[2];
1084 /* If the register has already been set in this block, there's
1085 nothing we can do. */
1086 if (! reg_not_set_p (reg_used
, insn
))
1089 /* Find an assignment that sets reg_used and is available
1090 at the start of the block. */
1091 find_avail_set (regno
, insn
, set
);
1093 src_reg
= set
[0]->src
;
1095 src_cst
= set
[1]->src
;
1097 /* Constant propagation. */
1098 if (src_cst
&& cprop_constant_p (src_cst
)
1099 && constprop_register (reg_used
, src_cst
, insn
))
1101 changed_this_round
= changed
= 1;
1102 global_const_prop_count
++;
1103 if (dump_file
!= NULL
)
1106 "GLOBAL CONST-PROP: Replacing reg %d in ", regno
);
1107 fprintf (dump_file
, "insn %d with constant ",
1109 print_rtl (dump_file
, src_cst
);
1110 fprintf (dump_file
, "\n");
1112 if (insn
->deleted ())
1115 /* Copy propagation. */
1116 else if (src_reg
&& cprop_reg_p (src_reg
)
1117 && REGNO (src_reg
) != regno
1118 && try_replace_reg (reg_used
, src_reg
, insn
))
1120 changed_this_round
= changed
= 1;
1121 global_copy_prop_count
++;
1122 if (dump_file
!= NULL
)
1125 "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1126 regno
, INSN_UID (insn
));
1127 fprintf (dump_file
, " with reg %d\n", REGNO (src_reg
));
1130 /* The original insn setting reg_used may or may not now be
1131 deletable. We leave the deletion to DCE. */
1132 /* FIXME: If it turns out that the insn isn't deletable,
1133 then we may have unnecessarily extended register lifetimes
1134 and made things worse. */
1138 /* If try_replace_reg simplified the insn, the regs found by find_used_regs
1139 may not be valid anymore. Start over. */
1140 while (changed_this_round
);
1142 if (changed
&& DEBUG_INSN_P (insn
))
1148 /* Like find_used_regs, but avoid recording uses that appear in
1149 input-output contexts such as zero_extract or pre_dec. This
1150 restricts the cases we consider to those for which local cprop
1151 can legitimately make replacements. */
1154 local_cprop_find_used_regs (rtx
*xptr
, void *data
)
1161 switch (GET_CODE (x
))
1165 case STRICT_LOW_PART
:
1174 /* Can only legitimately appear this early in the context of
1175 stack pushes for function arguments, but handle all of the
1176 codes nonetheless. */
1180 /* Setting a subreg of a register larger than word_mode leaves
1181 the non-written words unchanged. */
1182 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x
))) > BITS_PER_WORD
)
1190 find_used_regs (xptr
, data
);
1193 /* Try to perform local const/copy propagation on X in INSN. */
1196 do_local_cprop (rtx x
, rtx_insn
*insn
)
1198 rtx newreg
= NULL
, newcnst
= NULL
;
1200 /* Rule out USE instructions and ASM statements as we don't want to
1201 change the hard registers mentioned. */
1204 || (GET_CODE (PATTERN (insn
)) != USE
1205 && asm_noperands (PATTERN (insn
)) < 0)))
1207 cselib_val
*val
= cselib_lookup (x
, GET_MODE (x
), 0, VOIDmode
);
1208 struct elt_loc_list
*l
;
1212 for (l
= val
->locs
; l
; l
= l
->next
)
1214 rtx this_rtx
= l
->loc
;
1217 if (cprop_constant_p (this_rtx
))
1219 if (cprop_reg_p (this_rtx
)
1220 /* Don't copy propagate if it has attached REG_EQUIV note.
1221 At this point this only function parameters should have
1222 REG_EQUIV notes and if the argument slot is used somewhere
1223 explicitly, it means address of parameter has been taken,
1224 so we should not extend the lifetime of the pseudo. */
1225 && (!(note
= find_reg_note (l
->setting_insn
, REG_EQUIV
, NULL_RTX
))
1226 || ! MEM_P (XEXP (note
, 0))))
1229 if (newcnst
&& constprop_register (x
, newcnst
, insn
))
1231 if (dump_file
!= NULL
)
1233 fprintf (dump_file
, "LOCAL CONST-PROP: Replacing reg %d in ",
1235 fprintf (dump_file
, "insn %d with constant ",
1237 print_rtl (dump_file
, newcnst
);
1238 fprintf (dump_file
, "\n");
1240 local_const_prop_count
++;
1243 else if (newreg
&& newreg
!= x
&& try_replace_reg (x
, newreg
, insn
))
1245 if (dump_file
!= NULL
)
1248 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1249 REGNO (x
), INSN_UID (insn
));
1250 fprintf (dump_file
, " with reg %d\n", REGNO (newreg
));
1252 local_copy_prop_count
++;
1259 /* Do local const/copy propagation (i.e. within each basic block). */
1262 local_cprop_pass (void)
1266 bool changed
= false;
1270 FOR_EACH_BB_FN (bb
, cfun
)
1272 FOR_BB_INSNS (bb
, insn
)
1276 rtx note
= find_reg_equal_equiv_note (insn
);
1280 note_uses (&PATTERN (insn
), local_cprop_find_used_regs
,
1283 local_cprop_find_used_regs (&XEXP (note
, 0), NULL
);
1285 for (i
= 0; i
< reg_use_count
; i
++)
1287 if (do_local_cprop (reg_use_table
[i
], insn
))
1289 if (!DEBUG_INSN_P (insn
))
1294 if (insn
->deleted ())
1297 while (i
< reg_use_count
);
1299 cselib_process_insn (insn
);
1302 /* Forget everything at the end of a basic block. */
1303 cselib_clear_table ();
1311 /* Similar to get_condition, only the resulting condition must be
1312 valid at JUMP, instead of at EARLIEST.
1314 This differs from noce_get_condition in ifcvt.c in that we prefer not to
1315 settle for the condition variable in the jump instruction being integral.
1316 We prefer to be able to record the value of a user variable, rather than
1317 the value of a temporary used in a condition. This could be solved by
1318 recording the value of *every* register scanned by canonicalize_condition,
1319 but this would require some code reorganization. */
1322 fis_get_condition (rtx_insn
*jump
)
1324 return get_condition (jump
, NULL
, false, true);
1327 /* Check the comparison COND to see if we can safely form an implicit
1331 implicit_set_cond_p (const_rtx cond
)
1336 /* COND must be either an EQ or NE comparison. */
1337 if (GET_CODE (cond
) != EQ
&& GET_CODE (cond
) != NE
)
1340 /* The first operand of COND must be a register we can propagate. */
1341 if (!cprop_reg_p (XEXP (cond
, 0)))
1344 /* The second operand of COND must be a suitable constant. */
1345 mode
= GET_MODE (XEXP (cond
, 0));
1346 cst
= XEXP (cond
, 1);
1348 /* We can't perform this optimization if either operand might be or might
1349 contain a signed zero. */
1350 if (HONOR_SIGNED_ZEROS (mode
))
1352 /* It is sufficient to check if CST is or contains a zero. We must
1353 handle float, complex, and vector. If any subpart is a zero, then
1354 the optimization can't be performed. */
1355 /* ??? The complex and vector checks are not implemented yet. We just
1356 always return zero for them. */
1357 if (CONST_DOUBLE_AS_FLOAT_P (cst
))
1360 REAL_VALUE_FROM_CONST_DOUBLE (d
, cst
);
1361 if (REAL_VALUES_EQUAL (d
, dconst0
))
1368 return cprop_constant_p (cst
);
1371 /* Find the implicit sets of a function. An "implicit set" is a constraint
1372 on the value of a variable, implied by a conditional jump. For example,
1373 following "if (x == 2)", the then branch may be optimized as though the
1374 conditional performed an "explicit set", in this example, "x = 2". This
1375 function records the set patterns that are implicit at the start of each
1378 If an implicit set is found but the set is implicit on a critical edge,
1379 this critical edge is split.
1381 Return true if the CFG was modified, false otherwise. */
1384 find_implicit_sets (void)
1386 basic_block bb
, dest
;
1388 unsigned int count
= 0;
1389 bool edges_split
= false;
1390 size_t implicit_sets_size
= last_basic_block_for_fn (cfun
) + 10;
1392 implicit_sets
= XCNEWVEC (rtx
, implicit_sets_size
);
1394 FOR_EACH_BB_FN (bb
, cfun
)
1396 /* Check for more than one successor. */
1397 if (EDGE_COUNT (bb
->succs
) <= 1)
1400 cond
= fis_get_condition (BB_END (bb
));
1402 /* If no condition is found or if it isn't of a suitable form,
1404 if (! cond
|| ! implicit_set_cond_p (cond
))
1407 dest
= GET_CODE (cond
) == EQ
1408 ? BRANCH_EDGE (bb
)->dest
: FALLTHRU_EDGE (bb
)->dest
;
1410 /* If DEST doesn't go anywhere, ignore it. */
1411 if (! dest
|| dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1414 /* We have found a suitable implicit set. Try to record it now as
1415 a SET in DEST. If DEST has more than one predecessor, the edge
1416 between BB and DEST is a critical edge and we must split it,
1417 because we can only record one implicit set per DEST basic block. */
1418 if (! single_pred_p (dest
))
1420 dest
= split_edge (find_edge (bb
, dest
));
1424 if (implicit_sets_size
<= (size_t) dest
->index
)
1426 size_t old_implicit_sets_size
= implicit_sets_size
;
1427 implicit_sets_size
*= 2;
1428 implicit_sets
= XRESIZEVEC (rtx
, implicit_sets
, implicit_sets_size
);
1429 memset (implicit_sets
+ old_implicit_sets_size
, 0,
1430 (implicit_sets_size
- old_implicit_sets_size
) * sizeof (rtx
));
1433 new_rtx
= gen_rtx_SET (XEXP (cond
, 0), XEXP (cond
, 1));
1434 implicit_sets
[dest
->index
] = new_rtx
;
1437 fprintf (dump_file
, "Implicit set of reg %d in ",
1438 REGNO (XEXP (cond
, 0)));
1439 fprintf (dump_file
, "basic block %d\n", dest
->index
);
1445 fprintf (dump_file
, "Found %d implicit sets\n", count
);
1447 /* Confess our sins. */
1451 /* Bypass conditional jumps. */
1453 /* The value of last_basic_block at the beginning of the jump_bypass
1454 pass. The use of redirect_edge_and_branch_force may introduce new
1455 basic blocks, but the data flow analysis is only valid for basic
1456 block indices less than bypass_last_basic_block. */
1458 static int bypass_last_basic_block
;
1460 /* Find a set of REGNO to a constant that is available at the end of basic
1461 block BB. Return NULL if no such set is found. Based heavily upon
1464 static struct cprop_expr
*
1465 find_bypass_set (int regno
, int bb
)
1467 struct cprop_expr
*result
= 0;
1472 struct cprop_expr
*set
= lookup_set (regno
, &set_hash_table
);
1476 if (bitmap_bit_p (cprop_avout
[bb
], set
->bitmap_index
))
1478 set
= next_set (regno
, set
);
1485 if (cprop_constant_p (src
))
1491 regno
= REGNO (src
);
1496 /* Subroutine of bypass_block that checks whether a pseudo is killed by
1497 any of the instructions inserted on an edge. Jump bypassing places
1498 condition code setters on CFG edges using insert_insn_on_edge. This
1499 function is required to check that our data flow analysis is still
1500 valid prior to commit_edge_insertions. */
1503 reg_killed_on_edge (const_rtx reg
, const_edge e
)
1507 for (insn
= e
->insns
.r
; insn
; insn
= NEXT_INSN (insn
))
1508 if (INSN_P (insn
) && reg_set_p (reg
, insn
))
1514 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1515 basic block BB which has more than one predecessor. If not NULL, SETCC
1516 is the first instruction of BB, which is immediately followed by JUMP_INSN
1517 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1518 Returns nonzero if a change was made.
1520 During the jump bypassing pass, we may place copies of SETCC instructions
1521 on CFG edges. The following routine must be careful to pay attention to
1522 these inserted insns when performing its transformations. */
1525 bypass_block (basic_block bb
, rtx_insn
*setcc
, rtx_insn
*jump
)
1531 int may_be_loop_header
= false;
1536 insn
= (setcc
!= NULL
) ? setcc
: jump
;
1538 /* Determine set of register uses in INSN. */
1540 note_uses (&PATTERN (insn
), find_used_regs
, NULL
);
1541 note
= find_reg_equal_equiv_note (insn
);
1543 find_used_regs (&XEXP (note
, 0), NULL
);
1547 /* If we are to preserve loop structure then do not bypass
1548 a loop header. This will either rotate the loop, create
1549 multiple entry loops or even irreducible regions. */
1550 if (bb
== bb
->loop_father
->header
)
1555 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1556 if (e
->flags
& EDGE_DFS_BACK
)
1558 may_be_loop_header
= true;
1564 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
1568 if (e
->flags
& EDGE_COMPLEX
)
1574 /* We can't redirect edges from new basic blocks. */
1575 if (e
->src
->index
>= bypass_last_basic_block
)
1581 /* The irreducible loops created by redirecting of edges entering the
1582 loop from outside would decrease effectiveness of some of the
1583 following optimizations, so prevent this. */
1584 if (may_be_loop_header
1585 && !(e
->flags
& EDGE_DFS_BACK
))
1591 for (i
= 0; i
< reg_use_count
; i
++)
1593 rtx reg_used
= reg_use_table
[i
];
1594 unsigned int regno
= REGNO (reg_used
);
1595 basic_block dest
, old_dest
;
1596 struct cprop_expr
*set
;
1599 set
= find_bypass_set (regno
, e
->src
->index
);
1604 /* Check the data flow is valid after edge insertions. */
1605 if (e
->insns
.r
&& reg_killed_on_edge (reg_used
, e
))
1608 src
= SET_SRC (pc_set (jump
));
1611 src
= simplify_replace_rtx (src
,
1612 SET_DEST (PATTERN (setcc
)),
1613 SET_SRC (PATTERN (setcc
)));
1615 new_rtx
= simplify_replace_rtx (src
, reg_used
, set
->src
);
1617 /* Jump bypassing may have already placed instructions on
1618 edges of the CFG. We can't bypass an outgoing edge that
1619 has instructions associated with it, as these insns won't
1620 get executed if the incoming edge is redirected. */
1621 if (new_rtx
== pc_rtx
)
1623 edest
= FALLTHRU_EDGE (bb
);
1624 dest
= edest
->insns
.r
? NULL
: edest
->dest
;
1626 else if (GET_CODE (new_rtx
) == LABEL_REF
)
1628 dest
= BLOCK_FOR_INSN (XEXP (new_rtx
, 0));
1629 /* Don't bypass edges containing instructions. */
1630 edest
= find_edge (bb
, dest
);
1631 if (edest
&& edest
->insns
.r
)
1637 /* Avoid unification of the edge with other edges from original
1638 branch. We would end up emitting the instruction on "both"
1640 if (dest
&& setcc
&& !CC0_P (SET_DEST (PATTERN (setcc
)))
1641 && find_edge (e
->src
, dest
))
1647 && dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1649 redirect_edge_and_branch_force (e
, dest
);
1651 /* Copy the register setter to the redirected edge.
1652 Don't copy CC0 setters, as CC0 is dead after jump. */
1655 rtx pat
= PATTERN (setcc
);
1656 if (!CC0_P (SET_DEST (pat
)))
1657 insert_insn_on_edge (copy_insn (pat
), e
);
1660 if (dump_file
!= NULL
)
1662 fprintf (dump_file
, "JUMP-BYPASS: Proved reg %d "
1663 "in jump_insn %d equals constant ",
1664 regno
, INSN_UID (jump
));
1665 print_rtl (dump_file
, set
->src
);
1666 fprintf (dump_file
, "\n\t when BB %d is entered from "
1667 "BB %d. Redirect edge %d->%d to %d.\n",
1668 old_dest
->index
, e
->src
->index
, e
->src
->index
,
1669 old_dest
->index
, dest
->index
);
1682 /* Find basic blocks with more than one predecessor that only contain a
1683 single conditional jump. If the result of the comparison is known at
1684 compile-time from any incoming edge, redirect that edge to the
1685 appropriate target. Return nonzero if a change was made.
1687 This function is now mis-named, because we also handle indirect jumps. */
1690 bypass_conditional_jumps (void)
1698 /* Note we start at block 1. */
1699 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1702 bypass_last_basic_block
= last_basic_block_for_fn (cfun
);
1703 mark_dfs_back_edges ();
1706 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
->next_bb
,
1707 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1709 /* Check for more than one predecessor. */
1710 if (!single_pred_p (bb
))
1713 FOR_BB_INSNS (bb
, insn
)
1714 if (DEBUG_INSN_P (insn
))
1716 else if (NONJUMP_INSN_P (insn
))
1720 if (GET_CODE (PATTERN (insn
)) != SET
)
1723 dest
= SET_DEST (PATTERN (insn
));
1724 if (REG_P (dest
) || CC0_P (dest
))
1729 else if (JUMP_P (insn
))
1731 if ((any_condjump_p (insn
) || computed_jump_p (insn
))
1732 && onlyjump_p (insn
))
1733 changed
|= bypass_block (bb
, setcc
, insn
);
1736 else if (INSN_P (insn
))
1741 /* If we bypassed any register setting insns, we inserted a
1742 copy on the redirected edge. These need to be committed. */
1744 commit_edge_insertions ();
1749 /* Return true if the graph is too expensive to optimize. PASS is the
1750 optimization about to be performed. */
1753 is_too_expensive (const char *pass
)
1755 /* Trying to perform global optimizations on flow graphs which have
1756 a high connectivity will take a long time and is unlikely to be
1757 particularly useful.
1759 In normal circumstances a cfg should have about twice as many
1760 edges as blocks. But we do not want to punish small functions
1761 which have a couple switch statements. Rather than simply
1762 threshold the number of blocks, uses something with a more
1763 graceful degradation. */
1764 if (n_edges_for_fn (cfun
) > 20000 + n_basic_blocks_for_fn (cfun
) * 4)
1766 warning (OPT_Wdisabled_optimization
,
1767 "%s: %d basic blocks and %d edges/basic block",
1768 pass
, n_basic_blocks_for_fn (cfun
),
1769 n_edges_for_fn (cfun
) / n_basic_blocks_for_fn (cfun
));
1774 /* If allocating memory for the cprop bitmap would take up too much
1775 storage it's better just to disable the optimization. */
1776 if ((n_basic_blocks_for_fn (cfun
)
1777 * SBITMAP_SET_SIZE (max_reg_num ())
1778 * sizeof (SBITMAP_ELT_TYPE
)) > MAX_GCSE_MEMORY
)
1780 warning (OPT_Wdisabled_optimization
,
1781 "%s: %d basic blocks and %d registers",
1782 pass
, n_basic_blocks_for_fn (cfun
), max_reg_num ());
1790 /* Main function for the CPROP pass. */
1793 one_cprop_pass (void)
1798 /* Return if there's nothing to do, or it is too expensive. */
1799 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1
1800 || is_too_expensive (_ ("const/copy propagation disabled")))
1803 global_const_prop_count
= local_const_prop_count
= 0;
1804 global_copy_prop_count
= local_copy_prop_count
= 0;
1807 gcc_obstack_init (&cprop_obstack
);
1809 /* Do a local const/copy propagation pass first. The global pass
1810 only handles global opportunities.
1811 If the local pass changes something, remove any unreachable blocks
1812 because the CPROP global dataflow analysis may get into infinite
1813 loops for CFGs with unreachable blocks.
1815 FIXME: This local pass should not be necessary after CSE (but for
1816 some reason it still is). It is also (proven) not necessary
1817 to run the local pass right after FWPWOP.
1819 FIXME: The global analysis would not get into infinite loops if it
1820 would use the DF solver (via df_simple_dataflow) instead of
1821 the solver implemented in this file. */
1822 changed
|= local_cprop_pass ();
1824 delete_unreachable_blocks ();
1826 /* Determine implicit sets. This may change the CFG (split critical
1827 edges if that exposes an implicit set).
1828 Note that find_implicit_sets() does not rely on up-to-date DF caches
1829 so that we do not have to re-run df_analyze() even if local CPROP
1831 ??? This could run earlier so that any uncovered implicit sets
1832 sets could be exploited in local_cprop_pass() also. Later. */
1833 changed
|= find_implicit_sets ();
1835 /* If local_cprop_pass() or find_implicit_sets() changed something,
1836 run df_analyze() to bring all insn caches up-to-date, and to take
1837 new basic blocks from edge splitting on the DF radar.
1838 NB: This also runs the fast DCE pass, because execute_rtl_cprop
1839 sets DF_LR_RUN_DCE. */
1843 /* Initialize implicit_set_indexes array. */
1844 implicit_set_indexes
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1845 for (i
= 0; i
< last_basic_block_for_fn (cfun
); i
++)
1846 implicit_set_indexes
[i
] = -1;
1848 alloc_hash_table (&set_hash_table
);
1849 compute_hash_table (&set_hash_table
);
1851 /* Free implicit_sets before peak usage. */
1852 free (implicit_sets
);
1853 implicit_sets
= NULL
;
1856 dump_hash_table (dump_file
, "SET", &set_hash_table
);
1857 if (set_hash_table
.n_elems
> 0)
1862 alloc_cprop_mem (last_basic_block_for_fn (cfun
),
1863 set_hash_table
.n_elems
);
1864 compute_cprop_data ();
1866 free (implicit_set_indexes
);
1867 implicit_set_indexes
= NULL
;
1869 /* Allocate vars to track sets of regs. */
1870 reg_set_bitmap
= ALLOC_REG_SET (NULL
);
1872 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
->next_bb
,
1873 EXIT_BLOCK_PTR_FOR_FN (cfun
),
1876 /* Reset tables used to keep track of what's still valid [since
1877 the start of the block]. */
1878 reset_opr_set_tables ();
1880 FOR_BB_INSNS (bb
, insn
)
1883 changed
|= cprop_insn (insn
);
1885 /* Keep track of everything modified by this insn. */
1886 /* ??? Need to be careful w.r.t. mods done to INSN.
1887 Don't call mark_oprs_set if we turned the
1888 insn into a NOTE, or deleted the insn. */
1889 if (! NOTE_P (insn
) && ! insn
->deleted ())
1890 mark_oprs_set (insn
);
1894 changed
|= bypass_conditional_jumps ();
1896 FREE_REG_SET (reg_set_bitmap
);
1901 free (implicit_set_indexes
);
1902 implicit_set_indexes
= NULL
;
1905 free_hash_table (&set_hash_table
);
1906 obstack_free (&cprop_obstack
, NULL
);
1910 fprintf (dump_file
, "CPROP of %s, %d basic blocks, %d bytes needed, ",
1911 current_function_name (), n_basic_blocks_for_fn (cfun
),
1913 fprintf (dump_file
, "%d local const props, %d local copy props, ",
1914 local_const_prop_count
, local_copy_prop_count
);
1915 fprintf (dump_file
, "%d global const props, %d global copy props\n\n",
1916 global_const_prop_count
, global_copy_prop_count
);
1922 /* All the passes implemented in this file. Each pass has its
1923 own gate and execute function, and at the end of the file a
1924 pass definition for passes.c.
1926 We do not construct an accurate cfg in functions which call
1927 setjmp, so none of these passes runs if the function calls
1929 FIXME: Should just handle setjmp via REG_SETJMP notes. */
1932 execute_rtl_cprop (void)
1935 delete_unreachable_blocks ();
1936 df_set_flags (DF_LR_RUN_DCE
);
1938 changed
= one_cprop_pass ();
1939 flag_rerun_cse_after_global_opts
|= changed
;
1941 cleanup_cfg (CLEANUP_CFG_CHANGED
);
1947 const pass_data pass_data_rtl_cprop
=
1949 RTL_PASS
, /* type */
1951 OPTGROUP_NONE
, /* optinfo_flags */
1952 TV_CPROP
, /* tv_id */
1953 PROP_cfglayout
, /* properties_required */
1954 0, /* properties_provided */
1955 0, /* properties_destroyed */
1956 0, /* todo_flags_start */
1957 TODO_df_finish
, /* todo_flags_finish */
1960 class pass_rtl_cprop
: public rtl_opt_pass
1963 pass_rtl_cprop (gcc::context
*ctxt
)
1964 : rtl_opt_pass (pass_data_rtl_cprop
, ctxt
)
1967 /* opt_pass methods: */
1968 opt_pass
* clone () { return new pass_rtl_cprop (m_ctxt
); }
1969 virtual bool gate (function
*fun
)
1971 return optimize
> 0 && flag_gcse
1972 && !fun
->calls_setjmp
1976 virtual unsigned int execute (function
*) { return execute_rtl_cprop (); }
1978 }; // class pass_rtl_cprop
1983 make_pass_rtl_cprop (gcc::context
*ctxt
)
1985 return new pass_rtl_cprop (ctxt
);