1 /* RTL-based forward propagation pass for GNU compiler.
2 Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
3 Contributed by Paolo Bonzini and Steven Bosscher.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
31 #include "insn-config.h"
35 #include "basic-block.h"
40 #include "tree-pass.h"
44 /* This pass does simple forward propagation and simplification when an
45 operand of an insn can only come from a single def. This pass uses
46 df.c, so it is global. However, we only do limited analysis of
47 available expressions.
49 1) The pass tries to propagate the source of the def into the use,
50 and checks if the result is independent of the substituted value.
51 For example, the high word of a (zero_extend:DI (reg:SI M)) is always
52 zero, independent of the source register.
54 In particular, we propagate constants into the use site. Sometimes
55 RTL expansion did not put the constant in the same insn on purpose,
56 to satisfy a predicate, and the result will fail to be recognized;
57 but this happens rarely and in this case we can still create a
58 REG_EQUAL note. For multi-word operations, this
60 (set (subreg:SI (reg:DI 120) 0) (const_int 0))
61 (set (subreg:SI (reg:DI 120) 4) (const_int -1))
62 (set (subreg:SI (reg:DI 122) 0)
63 (ior:SI (subreg:SI (reg:DI 119) 0) (subreg:SI (reg:DI 120) 0)))
64 (set (subreg:SI (reg:DI 122) 4)
65 (ior:SI (subreg:SI (reg:DI 119) 4) (subreg:SI (reg:DI 120) 4)))
67 can be simplified to the much simpler
69 (set (subreg:SI (reg:DI 122) 0) (subreg:SI (reg:DI 119)))
70 (set (subreg:SI (reg:DI 122) 4) (const_int -1))
72 This particular propagation is also effective at putting together
73 complex addressing modes. We are more aggressive inside MEMs, in
74 that all definitions are propagated if the use is in a MEM; if the
75 result is a valid memory address we check address_cost to decide
76 whether the substitution is worthwhile.
78 2) The pass propagates register copies. This is not as effective as
79 the copy propagation done by CSE's canon_reg, which works by walking
80 the instruction chain, it can help the other transformations.
82 We should consider removing this optimization, and instead reorder the
83 RTL passes, because GCSE does this transformation too. With some luck,
84 the CSE pass at the end of rest_of_handle_gcse could also go away.
86 3) The pass looks for paradoxical subregs that are actually unnecessary.
89 (set (reg:QI 120) (subreg:QI (reg:SI 118) 0))
90 (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
91 (set (reg:SI 122) (plus:SI (subreg:SI (reg:QI 120) 0)
92 (subreg:SI (reg:QI 121) 0)))
94 are very common on machines that can only do word-sized operations.
95 For each use of a paradoxical subreg (subreg:WIDER (reg:NARROW N) 0),
96 if it has a single def and it is (subreg:NARROW (reg:WIDE M) 0),
97 we can replace the paradoxical subreg with simply (reg:WIDE M). The
98 above will simplify this to
100 (set (reg:QI 120) (subreg:QI (reg:SI 118) 0))
101 (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
102 (set (reg:SI 122) (plus:SI (reg:SI 118) (reg:SI 119)))
104 where the first two insns are now dead.
106 We used to use reaching definitions to find which uses have a
107 single reaching definition (sounds obvious...), but this is too
108 complex a problem in nasty testcases like PR33928. Now we use the
109 multiple definitions problem in df-problems.c. The similarity
110 between that problem and SSA form creation is taken further, in
111 that fwprop does a dominator walk to create its chains; however,
112 instead of creating a PHI function where multiple definitions meet
113 I just punt and record only singleton use-def chains, which is
114 all that is needed by fwprop. */
117 static int num_changes;
120 DEF_VEC_ALLOC_P(df_ref,heap);
121 static VEC(df_ref,heap) *use_def_ref;
122 static VEC(df_ref,heap) *reg_defs;
123 static VEC(df_ref,heap) *reg_defs_stack;
125 /* The MD bitmaps are trimmed to include only live registers to cut
126 memory usage on testcases like insn-recog.c. Track live registers
127 in the basic block and do not perform forward propagation if the
128 destination is a dead pseudo occurring in a note. */
129 static bitmap local_md;
130 static bitmap local_lr;
132 /* Return the only def in USE's use-def chain, or NULL if there is
133 more than one def in the chain. */
136 get_def_for_use (df_ref use)
138 return VEC_index (df_ref, use_def_ref, DF_REF_ID (use));
142 /* Update the reg_defs vector with non-partial definitions in DEF_REC.
143 TOP_FLAG says which artificials uses should be used, when DEF_REC
144 is an artificial def vector. LOCAL_MD is modified as after a
145 df_md_simulate_* function; we do more or less the same processing
146 done there, so we do not use those functions. */
148 #define DF_MD_GEN_FLAGS \
149 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
152 process_defs (df_ref *def_rec, int top_flag)
155 while ((def = *def_rec++) != NULL)
157 df_ref curr_def = VEC_index (df_ref, reg_defs, DF_REF_REGNO (def));
160 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag)
163 dregno = DF_REF_REGNO (def);
165 VEC_safe_push (df_ref, heap, reg_defs_stack, curr_def);
168 /* Do not store anything if "transitioning" from NULL to NULL. But
169 otherwise, push a special entry on the stack to tell the
170 leave_block callback that the entry in reg_defs was NULL. */
171 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
174 VEC_safe_push (df_ref, heap, reg_defs_stack, def);
177 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
179 bitmap_set_bit (local_md, dregno);
180 VEC_replace (df_ref, reg_defs, dregno, NULL);
184 bitmap_clear_bit (local_md, dregno);
185 VEC_replace (df_ref, reg_defs, dregno, def);
191 /* Fill the use_def_ref vector with values for the uses in USE_REC,
192 taking reaching definitions info from LOCAL_MD and REG_DEFS.
193 TOP_FLAG says which artificials uses should be used, when USE_REC
194 is an artificial use vector. */
197 process_uses (df_ref *use_rec, int top_flag)
200 while ((use = *use_rec++) != NULL)
201 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag)
203 unsigned int uregno = DF_REF_REGNO (use);
204 if (VEC_index (df_ref, reg_defs, uregno)
205 && !bitmap_bit_p (local_md, uregno)
206 && bitmap_bit_p (local_lr, uregno))
207 VEC_replace (df_ref, use_def_ref, DF_REF_ID (use),
208 VEC_index (df_ref, reg_defs, uregno));
214 single_def_use_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
217 int bb_index = bb->index;
218 struct df_md_bb_info *md_bb_info = df_md_get_bb_info (bb_index);
219 struct df_lr_bb_info *lr_bb_info = df_lr_get_bb_info (bb_index);
222 bitmap_copy (local_md, md_bb_info->in);
223 bitmap_copy (local_lr, lr_bb_info->in);
225 /* Push a marker for the leave_block callback. */
226 VEC_safe_push (df_ref, heap, reg_defs_stack, NULL);
228 process_uses (df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
229 process_defs (df_get_artificial_defs (bb_index), DF_REF_AT_TOP);
230 df_simulate_initialize_forwards (bb, local_lr);
232 FOR_BB_INSNS (bb, insn)
235 unsigned int uid = INSN_UID (insn);
236 process_uses (DF_INSN_UID_USES (uid), 0);
237 process_uses (DF_INSN_UID_EQ_USES (uid), 0);
238 process_defs (DF_INSN_UID_DEFS (uid), 0);
239 df_simulate_one_insn_forwards (bb, insn, local_lr);
242 process_uses (df_get_artificial_uses (bb_index), 0);
243 process_defs (df_get_artificial_defs (bb_index), 0);
246 /* Pop the definitions created in this basic block when leaving its
250 single_def_use_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
251 basic_block bb ATTRIBUTE_UNUSED)
254 while ((saved_def = VEC_pop (df_ref, reg_defs_stack)) != NULL)
256 unsigned int dregno = DF_REF_REGNO (saved_def);
258 /* See also process_defs. */
259 if (saved_def == VEC_index (df_ref, reg_defs, dregno))
260 VEC_replace (df_ref, reg_defs, dregno, NULL);
262 VEC_replace (df_ref, reg_defs, dregno, saved_def);
267 /* Build a vector holding the reaching definitions of uses reached by a
268 single dominating definition. */
271 build_single_def_use_links (void)
273 struct dom_walk_data walk_data;
275 /* We use the multiple definitions problem to compute our restricted
277 df_set_flags (DF_EQ_NOTES);
278 df_md_add_problem ();
279 df_note_add_problem ();
281 df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
283 use_def_ref = VEC_alloc (df_ref, heap, DF_USES_TABLE_SIZE ());
284 VEC_safe_grow_cleared (df_ref, heap, use_def_ref, DF_USES_TABLE_SIZE ());
286 reg_defs = VEC_alloc (df_ref, heap, max_reg_num ());
287 VEC_safe_grow_cleared (df_ref, heap, reg_defs, max_reg_num ());
289 reg_defs_stack = VEC_alloc (df_ref, heap, n_basic_blocks * 10);
290 local_md = BITMAP_ALLOC (NULL);
291 local_lr = BITMAP_ALLOC (NULL);
293 /* Walk the dominator tree looking for single reaching definitions
294 dominating the uses. This is similar to how SSA form is built. */
295 walk_data.dom_direction = CDI_DOMINATORS;
296 walk_data.initialize_block_local_data = NULL;
297 walk_data.before_dom_children = single_def_use_enter_block;
298 walk_data.after_dom_children = single_def_use_leave_block;
300 init_walk_dominator_tree (&walk_data);
301 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
302 fini_walk_dominator_tree (&walk_data);
304 BITMAP_FREE (local_lr);
305 BITMAP_FREE (local_md);
306 VEC_free (df_ref, heap, reg_defs);
307 VEC_free (df_ref, heap, reg_defs_stack);
311 /* Do not try to replace constant addresses or addresses of local and
312 argument slots. These MEM expressions are made only once and inserted
313 in many instructions, as well as being used to control symbol table
314 output. It is not safe to clobber them.
316 There are some uncommon cases where the address is already in a register
317 for some reason, but we cannot take advantage of that because we have
318 no easy way to unshare the MEM. In addition, looking up all stack
319 addresses is costly. */
322 can_simplify_addr (rtx addr)
326 if (CONSTANT_ADDRESS_P (addr))
329 if (GET_CODE (addr) == PLUS)
330 reg = XEXP (addr, 0);
335 || (REGNO (reg) != FRAME_POINTER_REGNUM
336 && REGNO (reg) != HARD_FRAME_POINTER_REGNUM
337 && REGNO (reg) != ARG_POINTER_REGNUM));
340 /* Returns a canonical version of X for the address, from the point of view,
341 that all multiplications are represented as MULT instead of the multiply
342 by a power of 2 being represented as ASHIFT.
344 Every ASHIFT we find has been made by simplify_gen_binary and was not
345 there before, so it is not shared. So we can do this in place. */
348 canonicalize_address (rtx x)
351 switch (GET_CODE (x))
354 if (CONST_INT_P (XEXP (x, 1))
355 && INTVAL (XEXP (x, 1)) < GET_MODE_BITSIZE (GET_MODE (x))
356 && INTVAL (XEXP (x, 1)) >= 0)
358 HOST_WIDE_INT shift = INTVAL (XEXP (x, 1));
360 XEXP (x, 1) = gen_int_mode ((HOST_WIDE_INT) 1 << shift,
368 if (GET_CODE (XEXP (x, 0)) == PLUS
369 || GET_CODE (XEXP (x, 0)) == ASHIFT
370 || GET_CODE (XEXP (x, 0)) == CONST)
371 canonicalize_address (XEXP (x, 0));
385 /* OLD is a memory address. Return whether it is good to use NEW instead,
386 for a memory access in the given MODE. */
389 should_replace_address (rtx old_rtx, rtx new_rtx, enum machine_mode mode,
390 addr_space_t as, bool speed)
394 if (rtx_equal_p (old_rtx, new_rtx)
395 || !memory_address_addr_space_p (mode, new_rtx, as))
398 /* Copy propagation is always ok. */
399 if (REG_P (old_rtx) && REG_P (new_rtx))
402 /* Prefer the new address if it is less expensive. */
403 gain = (address_cost (old_rtx, mode, as, speed)
404 - address_cost (new_rtx, mode, as, speed));
406 /* If the addresses have equivalent cost, prefer the new address
407 if it has the highest `rtx_cost'. That has the potential of
408 eliminating the most insns without additional costs, and it
409 is the same that cse.c used to do. */
411 gain = rtx_cost (new_rtx, SET, speed) - rtx_cost (old_rtx, SET, speed);
417 /* Flags for the last parameter of propagate_rtx_1. */
420 /* If PR_CAN_APPEAR is true, propagate_rtx_1 always returns true;
421 if it is false, propagate_rtx_1 returns false if, for at least
422 one occurrence OLD, it failed to collapse the result to a constant.
423 For example, (mult:M (reg:M A) (minus:M (reg:M B) (reg:M A))) may
424 collapse to zero if replacing (reg:M B) with (reg:M A).
426 PR_CAN_APPEAR is disregarded inside MEMs: in that case,
427 propagate_rtx_1 just tries to make cheaper and valid memory
431 /* If PR_HANDLE_MEM is not set, propagate_rtx_1 won't attempt any replacement
432 outside memory addresses. This is needed because propagate_rtx_1 does
433 not do any analysis on memory; thus it is very conservative and in general
434 it will fail if non-read-only MEMs are found in the source expression.
436 PR_HANDLE_MEM is set when the source of the propagation was not
437 another MEM. Then, it is safe not to treat non-read-only MEMs as
438 ``opaque'' objects. */
441 /* Set when costs should be optimized for speed. */
442 PR_OPTIMIZE_FOR_SPEED = 4
446 /* Replace all occurrences of OLD in *PX with NEW and try to simplify the
447 resulting expression. Replace *PX with a new RTL expression if an
448 occurrence of OLD was found.
450 This is only a wrapper around simplify-rtx.c: do not add any pattern
451 matching code here. (The sole exception is the handling of LO_SUM, but
452 that is because there is no simplify_gen_* function for LO_SUM). */
455 propagate_rtx_1 (rtx *px, rtx old_rtx, rtx new_rtx, int flags)
457 rtx x = *px, tem = NULL_RTX, op0, op1, op2;
458 enum rtx_code code = GET_CODE (x);
459 enum machine_mode mode = GET_MODE (x);
460 enum machine_mode op_mode;
461 bool can_appear = (flags & PR_CAN_APPEAR) != 0;
462 bool valid_ops = true;
464 if (!(flags & PR_HANDLE_MEM) && MEM_P (x) && !MEM_READONLY_P (x))
466 /* If unsafe, change MEMs to CLOBBERs or SCRATCHes (to preserve whether
467 they have side effects or not). */
468 *px = (side_effects_p (x)
469 ? gen_rtx_CLOBBER (GET_MODE (x), const0_rtx)
470 : gen_rtx_SCRATCH (GET_MODE (x)));
474 /* If X is OLD_RTX, return NEW_RTX. But not if replacing only within an
475 address, and we are *not* inside one. */
482 /* If this is an expression, try recursive substitution. */
483 switch (GET_RTX_CLASS (code))
487 op_mode = GET_MODE (op0);
488 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
489 if (op0 == XEXP (x, 0))
491 tem = simplify_gen_unary (code, mode, op0, op_mode);
498 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
499 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
500 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
502 tem = simplify_gen_binary (code, mode, op0, op1);
506 case RTX_COMM_COMPARE:
509 op_mode = GET_MODE (op0) != VOIDmode ? GET_MODE (op0) : GET_MODE (op1);
510 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
511 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
512 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
514 tem = simplify_gen_relational (code, mode, op_mode, op0, op1);
518 case RTX_BITFIELD_OPS:
522 op_mode = GET_MODE (op0);
523 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
524 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
525 valid_ops &= propagate_rtx_1 (&op2, old_rtx, new_rtx, flags);
526 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1) && op2 == XEXP (x, 2))
528 if (op_mode == VOIDmode)
529 op_mode = GET_MODE (op0);
530 tem = simplify_gen_ternary (code, mode, op_mode, op0, op1, op2);
534 /* The only case we try to handle is a SUBREG. */
538 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
539 if (op0 == XEXP (x, 0))
541 tem = simplify_gen_subreg (mode, op0, GET_MODE (SUBREG_REG (x)),
547 if (code == MEM && x != new_rtx)
552 /* There are some addresses that we cannot work on. */
553 if (!can_simplify_addr (op0))
556 op0 = new_op0 = targetm.delegitimize_address (op0);
557 valid_ops &= propagate_rtx_1 (&new_op0, old_rtx, new_rtx,
558 flags | PR_CAN_APPEAR);
560 /* Dismiss transformation that we do not want to carry on. */
563 || !(GET_MODE (new_op0) == GET_MODE (op0)
564 || GET_MODE (new_op0) == VOIDmode))
567 canonicalize_address (new_op0);
569 /* Copy propagations are always ok. Otherwise check the costs. */
570 if (!(REG_P (old_rtx) && REG_P (new_rtx))
571 && !should_replace_address (op0, new_op0, GET_MODE (x),
573 flags & PR_OPTIMIZE_FOR_SPEED))
576 tem = replace_equiv_address_nv (x, new_op0);
579 else if (code == LO_SUM)
584 /* The only simplification we do attempts to remove references to op0
585 or make it constant -- in both cases, op0's invalidity will not
586 make the result invalid. */
587 propagate_rtx_1 (&op0, old_rtx, new_rtx, flags | PR_CAN_APPEAR);
588 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
589 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
592 /* (lo_sum (high x) x) -> x */
593 if (GET_CODE (op0) == HIGH && rtx_equal_p (XEXP (op0, 0), op1))
596 tem = gen_rtx_LO_SUM (mode, op0, op1);
598 /* OP1 is likely not a legitimate address, otherwise there would have
599 been no LO_SUM. We want it to disappear if it is invalid, return
600 false in that case. */
601 return memory_address_p (mode, tem);
604 else if (code == REG)
606 if (rtx_equal_p (x, old_rtx))
618 /* No change, no trouble. */
624 /* The replacement we made so far is valid, if all of the recursive
625 replacements were valid, or we could simplify everything to
627 return valid_ops || can_appear || CONSTANT_P (tem);
631 /* for_each_rtx traversal function that returns 1 if BODY points to
632 a non-constant mem. */
635 varying_mem_p (rtx *body, void *data ATTRIBUTE_UNUSED)
638 return MEM_P (x) && !MEM_READONLY_P (x);
642 /* Replace all occurrences of OLD in X with NEW and try to simplify the
643 resulting expression (in mode MODE). Return a new expression if it is
644 a constant, otherwise X.
646 Simplifications where occurrences of NEW collapse to a constant are always
647 accepted. All simplifications are accepted if NEW is a pseudo too.
648 Otherwise, we accept simplifications that have a lower or equal cost. */
651 propagate_rtx (rtx x, enum machine_mode mode, rtx old_rtx, rtx new_rtx,
658 if (REG_P (new_rtx) && REGNO (new_rtx) < FIRST_PSEUDO_REGISTER)
662 if (REG_P (new_rtx) || CONSTANT_P (new_rtx))
663 flags |= PR_CAN_APPEAR;
664 if (!for_each_rtx (&new_rtx, varying_mem_p, NULL))
665 flags |= PR_HANDLE_MEM;
668 flags |= PR_OPTIMIZE_FOR_SPEED;
671 collapsed = propagate_rtx_1 (&tem, old_rtx, copy_rtx (new_rtx), flags);
672 if (tem == x || !collapsed)
675 /* gen_lowpart_common will not be able to process VOIDmode entities other
677 if (GET_MODE (tem) == VOIDmode && !CONST_INT_P (tem))
680 if (GET_MODE (tem) == VOIDmode)
681 tem = rtl_hooks.gen_lowpart_no_emit (mode, tem);
683 gcc_assert (GET_MODE (tem) == mode);
691 /* Return true if the register from reference REF is killed
692 between FROM to (but not including) TO. */
695 local_ref_killed_between_p (df_ref ref, rtx from, rtx to)
699 for (insn = from; insn != to; insn = NEXT_INSN (insn))
705 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
707 df_ref def = *def_rec;
708 if (DF_REF_REGNO (ref) == DF_REF_REGNO (def))
716 /* Check if the given DEF is available in INSN. This would require full
717 computation of available expressions; we check only restricted conditions:
718 - if DEF is the sole definition of its register, go ahead;
719 - in the same basic block, we check for no definitions killing the
720 definition of DEF_INSN;
721 - if USE's basic block has DEF's basic block as the sole predecessor,
722 we check if the definition is killed after DEF_INSN or before
723 TARGET_INSN insn, in their respective basic blocks. */
725 use_killed_between (df_ref use, rtx def_insn, rtx target_insn)
727 basic_block def_bb = BLOCK_FOR_INSN (def_insn);
728 basic_block target_bb = BLOCK_FOR_INSN (target_insn);
732 /* We used to have a def reaching a use that is _before_ the def,
733 with the def not dominating the use even though the use and def
734 are in the same basic block, when a register may be used
735 uninitialized in a loop. This should not happen anymore since
736 we do not use reaching definitions, but still we test for such
737 cases and assume that DEF is not available. */
738 if (def_bb == target_bb
739 ? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn)
740 : !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb))
743 /* Check if the reg in USE has only one definition. We already
744 know that this definition reaches use, or we wouldn't be here.
745 However, this is invalid for hard registers because if they are
746 live at the beginning of the function it does not mean that we
747 have an uninitialized access. */
748 regno = DF_REF_REGNO (use);
749 def = DF_REG_DEF_CHAIN (regno);
751 && DF_REF_NEXT_REG (def) == NULL
752 && regno >= FIRST_PSEUDO_REGISTER)
755 /* Check locally if we are in the same basic block. */
756 if (def_bb == target_bb)
757 return local_ref_killed_between_p (use, def_insn, target_insn);
759 /* Finally, if DEF_BB is the sole predecessor of TARGET_BB. */
760 if (single_pred_p (target_bb)
761 && single_pred (target_bb) == def_bb)
765 /* See if USE is killed between DEF_INSN and the last insn in the
766 basic block containing DEF_INSN. */
767 x = df_bb_regno_last_def_find (def_bb, regno);
768 if (x && DF_INSN_LUID (DF_REF_INSN (x)) >= DF_INSN_LUID (def_insn))
771 /* See if USE is killed between TARGET_INSN and the first insn in the
772 basic block containing TARGET_INSN. */
773 x = df_bb_regno_first_def_find (target_bb, regno);
774 if (x && DF_INSN_LUID (DF_REF_INSN (x)) < DF_INSN_LUID (target_insn))
780 /* Otherwise assume the worst case. */
785 /* Check if all uses in DEF_INSN can be used in TARGET_INSN. This
786 would require full computation of available expressions;
787 we check only restricted conditions, see use_killed_between. */
789 all_uses_available_at (rtx def_insn, rtx target_insn)
792 struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
793 rtx def_set = single_set (def_insn);
795 gcc_assert (def_set);
797 /* If target_insn comes right after def_insn, which is very common
798 for addresses, we can use a quicker test. */
799 if (NEXT_INSN (def_insn) == target_insn
800 && REG_P (SET_DEST (def_set)))
802 rtx def_reg = SET_DEST (def_set);
804 /* If the insn uses the reg that it defines, the substitution is
806 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
808 df_ref use = *use_rec;
809 if (rtx_equal_p (DF_REF_REG (use), def_reg))
812 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
814 df_ref use = *use_rec;
815 if (rtx_equal_p (DF_REF_REG (use), def_reg))
821 /* Look at all the uses of DEF_INSN, and see if they are not
822 killed between DEF_INSN and TARGET_INSN. */
823 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
825 df_ref use = *use_rec;
826 if (use_killed_between (use, def_insn, target_insn))
829 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
831 df_ref use = *use_rec;
832 if (use_killed_between (use, def_insn, target_insn))
841 struct find_occurrence_data
847 /* Callback for for_each_rtx, used in find_occurrence.
848 See if PX is the rtx we have to find. Return 1 to stop for_each_rtx
849 if successful, or 0 to continue traversing otherwise. */
852 find_occurrence_callback (rtx *px, void *data)
854 struct find_occurrence_data *fod = (struct find_occurrence_data *) data;
856 rtx find = fod->find;
867 /* Return a pointer to one of the occurrences of register FIND in *PX. */
870 find_occurrence (rtx *px, rtx find)
872 struct find_occurrence_data data;
874 gcc_assert (REG_P (find)
875 || (GET_CODE (find) == SUBREG
876 && REG_P (SUBREG_REG (find))));
880 for_each_rtx (px, find_occurrence_callback, &data);
885 /* Inside INSN, the expression rooted at *LOC has been changed, moving some
886 uses from USE_VEC. Find those that are present, and create new items
887 in the data flow object of the pass. Mark any new uses as having the
890 update_df (rtx insn, rtx *loc, df_ref *use_rec, enum df_ref_type type,
893 bool changed = false;
895 /* Add a use for the registers that were propagated. */
898 df_ref use = *use_rec;
899 df_ref orig_use = use, new_use;
902 enum machine_mode mode = VOIDmode;
903 rtx *new_loc = find_occurrence (loc, DF_REF_REG (orig_use));
909 if (DF_REF_FLAGS_IS_SET (orig_use, DF_REF_SIGN_EXTRACT | DF_REF_ZERO_EXTRACT))
911 width = DF_REF_EXTRACT_WIDTH (orig_use);
912 offset = DF_REF_EXTRACT_OFFSET (orig_use);
913 mode = DF_REF_EXTRACT_MODE (orig_use);
916 /* Add a new insn use. Use the original type, because it says if the
917 use was within a MEM. */
918 new_use = df_ref_create (DF_REF_REG (orig_use), new_loc,
919 insn, BLOCK_FOR_INSN (insn),
920 type, DF_REF_FLAGS (orig_use) | new_flags,
921 width, offset, mode);
923 /* Set up the use-def chain. */
924 gcc_assert (DF_REF_ID (new_use) == (int) VEC_length (df_ref, use_def_ref));
925 VEC_safe_push (df_ref, heap, use_def_ref, get_def_for_use (orig_use));
929 df_insn_rescan (insn);
933 /* Try substituting NEW into LOC, which originated from forward propagation
934 of USE's value from DEF_INSN. SET_REG_EQUAL says whether we are
935 substituting the whole SET_SRC, so we can set a REG_EQUAL note if the
936 new insn is not recognized. Return whether the substitution was
940 try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx def_insn, bool set_reg_equal)
942 rtx insn = DF_REF_INSN (use);
943 enum df_ref_type type = DF_REF_TYPE (use);
944 int flags = DF_REF_FLAGS (use);
945 rtx set = single_set (insn);
946 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
950 /* forward_propagate_subreg may be operating on an instruction with
951 multiple sets. If so, assume the cost of the new instruction is
952 not greater than the old one. */
954 old_cost = rtx_cost (SET_SRC (set), SET, speed);
957 fprintf (dump_file, "\nIn insn %d, replacing\n ", INSN_UID (insn));
958 print_inline_rtx (dump_file, *loc, 2);
959 fprintf (dump_file, "\n with ");
960 print_inline_rtx (dump_file, new_rtx, 2);
961 fprintf (dump_file, "\n");
964 validate_unshare_change (insn, loc, new_rtx, true);
965 if (!verify_changes (0))
968 fprintf (dump_file, "Changes to insn %d not recognized\n",
973 else if (DF_REF_TYPE (use) == DF_REF_REG_USE
975 && rtx_cost (SET_SRC (set), SET, speed) > old_cost)
978 fprintf (dump_file, "Changes to insn %d not profitable\n",
986 fprintf (dump_file, "Changed insn %d\n", INSN_UID (insn));
992 confirm_change_group ();
996 if (!CONSTANT_P (new_rtx))
998 struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
999 update_df (insn, loc, DF_INSN_INFO_USES (insn_info), type, flags);
1000 update_df (insn, loc, DF_INSN_INFO_EQ_USES (insn_info), type, flags);
1007 /* Can also record a simplified value in a REG_EQUAL note,
1008 making a new one if one does not already exist. */
1012 fprintf (dump_file, " Setting REG_EQUAL note\n");
1014 set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
1016 /* ??? Is this still necessary if we add the note through
1017 set_unique_reg_note? */
1018 if (!CONSTANT_P (new_rtx))
1020 struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
1021 update_df (insn, loc, DF_INSN_INFO_USES (insn_info),
1022 type, DF_REF_IN_NOTE);
1023 update_df (insn, loc, DF_INSN_INFO_EQ_USES (insn_info),
1024 type, DF_REF_IN_NOTE);
1032 /* For the given single_set INSN, containing SRC known to be a
1033 ZERO_EXTEND or SIGN_EXTEND of a register, return true if INSN
1034 is redundant due to the register being set by a LOAD_EXTEND_OP
1035 load from memory. */
1038 free_load_extend (rtx src, rtx insn)
1042 df_ref use = 0, def;
1044 reg = XEXP (src, 0);
1045 #ifdef LOAD_EXTEND_OP
1046 if (LOAD_EXTEND_OP (GET_MODE (reg)) != GET_CODE (src))
1050 for (use_vec = DF_INSN_USES (insn); *use_vec; use_vec++)
1054 if (!DF_REF_IS_ARTIFICIAL (use)
1055 && DF_REF_TYPE (use) == DF_REF_REG_USE
1056 && DF_REF_REG (use) == reg)
1062 def = get_def_for_use (use);
1066 if (DF_REF_IS_ARTIFICIAL (def))
1069 if (NONJUMP_INSN_P (DF_REF_INSN (def)))
1071 rtx patt = PATTERN (DF_REF_INSN (def));
1073 if (GET_CODE (patt) == SET
1074 && GET_CODE (SET_SRC (patt)) == MEM
1075 && rtx_equal_p (SET_DEST (patt), reg))
1081 /* If USE is a subreg, see if it can be replaced by a pseudo. */
1084 forward_propagate_subreg (df_ref use, rtx def_insn, rtx def_set)
1086 rtx use_reg = DF_REF_REG (use);
1089 /* Only consider subregs... */
1090 enum machine_mode use_mode = GET_MODE (use_reg);
1091 if (GET_CODE (use_reg) != SUBREG
1092 || !REG_P (SET_DEST (def_set)))
1095 /* If this is a paradoxical SUBREG... */
1096 if (GET_MODE_SIZE (use_mode)
1097 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (use_reg))))
1099 /* If this is a paradoxical SUBREG, we have no idea what value the
1100 extra bits would have. However, if the operand is equivalent to
1101 a SUBREG whose operand is the same as our mode, and all the modes
1102 are within a word, we can just use the inner operand because
1103 these SUBREGs just say how to treat the register. */
1104 use_insn = DF_REF_INSN (use);
1105 src = SET_SRC (def_set);
1106 if (GET_CODE (src) == SUBREG
1107 && REG_P (SUBREG_REG (src))
1108 && GET_MODE (SUBREG_REG (src)) == use_mode
1109 && subreg_lowpart_p (src)
1110 && all_uses_available_at (def_insn, use_insn))
1111 return try_fwprop_subst (use, DF_REF_LOC (use), SUBREG_REG (src),
1115 /* If this is a SUBREG of a ZERO_EXTEND or SIGN_EXTEND, and the SUBREG
1116 is the low part of the reg being extended then just use the inner
1117 operand. Don't do this if the ZERO_EXTEND or SIGN_EXTEND insn will
1118 be removed due to it matching a LOAD_EXTEND_OP load from memory. */
1119 else if (subreg_lowpart_p (use_reg))
1121 use_insn = DF_REF_INSN (use);
1122 src = SET_SRC (def_set);
1123 if ((GET_CODE (src) == ZERO_EXTEND
1124 || GET_CODE (src) == SIGN_EXTEND)
1125 && REG_P (XEXP (src, 0))
1126 && GET_MODE (XEXP (src, 0)) == use_mode
1127 && !free_load_extend (src, def_insn)
1128 && all_uses_available_at (def_insn, use_insn))
1129 return try_fwprop_subst (use, DF_REF_LOC (use), XEXP (src, 0),
1136 /* Try to replace USE with SRC (defined in DEF_INSN) in __asm. */
1139 forward_propagate_asm (df_ref use, rtx def_insn, rtx def_set, rtx reg)
1141 rtx use_insn = DF_REF_INSN (use), src, use_pat, asm_operands, new_rtx, *loc;
1145 gcc_assert ((DF_REF_FLAGS (use) & DF_REF_IN_NOTE) == 0);
1147 src = SET_SRC (def_set);
1148 use_pat = PATTERN (use_insn);
1150 /* In __asm don't replace if src might need more registers than
1151 reg, as that could increase register pressure on the __asm. */
1152 use_vec = DF_INSN_USES (def_insn);
1153 if (use_vec[0] && use_vec[1])
1156 speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
1157 asm_operands = NULL_RTX;
1158 switch (GET_CODE (use_pat))
1161 asm_operands = use_pat;
1164 if (MEM_P (SET_DEST (use_pat)))
1166 loc = &SET_DEST (use_pat);
1167 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1169 validate_unshare_change (use_insn, loc, new_rtx, true);
1171 asm_operands = SET_SRC (use_pat);
1174 for (i = 0; i < XVECLEN (use_pat, 0); i++)
1175 if (GET_CODE (XVECEXP (use_pat, 0, i)) == SET)
1177 if (MEM_P (SET_DEST (XVECEXP (use_pat, 0, i))))
1179 loc = &SET_DEST (XVECEXP (use_pat, 0, i));
1180 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg,
1183 validate_unshare_change (use_insn, loc, new_rtx, true);
1185 asm_operands = SET_SRC (XVECEXP (use_pat, 0, i));
1187 else if (GET_CODE (XVECEXP (use_pat, 0, i)) == ASM_OPERANDS)
1188 asm_operands = XVECEXP (use_pat, 0, i);
1194 gcc_assert (asm_operands && GET_CODE (asm_operands) == ASM_OPERANDS);
1195 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (asm_operands); i++)
1197 loc = &ASM_OPERANDS_INPUT (asm_operands, i);
1198 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1200 validate_unshare_change (use_insn, loc, new_rtx, true);
1203 if (num_changes_pending () == 0 || !apply_change_group ())
1210 /* Try to replace USE with SRC (defined in DEF_INSN) and simplify the
1214 forward_propagate_and_simplify (df_ref use, rtx def_insn, rtx def_set)
1216 rtx use_insn = DF_REF_INSN (use);
1217 rtx use_set = single_set (use_insn);
1218 rtx src, reg, new_rtx, *loc;
1220 enum machine_mode mode;
1223 if (INSN_CODE (use_insn) < 0)
1224 asm_use = asm_noperands (PATTERN (use_insn));
1226 if (!use_set && asm_use < 0 && !DEBUG_INSN_P (use_insn))
1229 /* Do not propagate into PC, CC0, etc. */
1230 if (use_set && GET_MODE (SET_DEST (use_set)) == VOIDmode)
1233 /* If def and use are subreg, check if they match. */
1234 reg = DF_REF_REG (use);
1235 if (GET_CODE (reg) == SUBREG
1236 && GET_CODE (SET_DEST (def_set)) == SUBREG
1237 && (SUBREG_BYTE (SET_DEST (def_set)) != SUBREG_BYTE (reg)
1238 || GET_MODE (SET_DEST (def_set)) != GET_MODE (reg)))
1241 /* Check if the def had a subreg, but the use has the whole reg. */
1242 if (REG_P (reg) && GET_CODE (SET_DEST (def_set)) == SUBREG)
1245 /* Check if the use has a subreg, but the def had the whole reg. Unlike the
1246 previous case, the optimization is possible and often useful indeed. */
1247 if (GET_CODE (reg) == SUBREG && REG_P (SET_DEST (def_set)))
1248 reg = SUBREG_REG (reg);
1250 /* Check if the substitution is valid (last, because it's the most
1251 expensive check!). */
1252 src = SET_SRC (def_set);
1253 if (!CONSTANT_P (src) && !all_uses_available_at (def_insn, use_insn))
1256 /* Check if the def is loading something from the constant pool; in this
1257 case we would undo optimization such as compress_float_constant.
1258 Still, we can set a REG_EQUAL note. */
1259 if (MEM_P (src) && MEM_READONLY_P (src))
1261 rtx x = avoid_constant_pool_reference (src);
1262 if (x != src && use_set)
1264 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1265 rtx old_rtx = note ? XEXP (note, 0) : SET_SRC (use_set);
1266 rtx new_rtx = simplify_replace_rtx (old_rtx, src, x);
1267 if (old_rtx != new_rtx)
1268 set_unique_reg_note (use_insn, REG_EQUAL, copy_rtx (new_rtx));
1274 return forward_propagate_asm (use, def_insn, def_set, reg);
1276 /* Else try simplifying. */
1278 if (DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE)
1280 loc = &SET_DEST (use_set);
1281 set_reg_equal = false;
1285 loc = &INSN_VAR_LOCATION_LOC (use_insn);
1286 set_reg_equal = false;
1290 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1291 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1292 loc = &XEXP (note, 0);
1294 loc = &SET_SRC (use_set);
1296 /* Do not replace an existing REG_EQUAL note if the insn is not
1297 recognized. Either we're already replacing in the note, or
1298 we'll separately try plugging the definition in the note and
1300 set_reg_equal = (note == NULL_RTX);
1303 if (GET_MODE (*loc) == VOIDmode)
1304 mode = GET_MODE (SET_DEST (use_set));
1306 mode = GET_MODE (*loc);
1308 new_rtx = propagate_rtx (*loc, mode, reg, src,
1309 optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn)));
1314 return try_fwprop_subst (use, loc, new_rtx, def_insn, set_reg_equal);
1318 /* Given a use USE of an insn, if it has a single reaching
1319 definition, try to forward propagate it into that insn. */
1322 forward_propagate_into (df_ref use)
1325 rtx def_insn, def_set, use_insn;
1328 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
1330 if (DF_REF_IS_ARTIFICIAL (use))
1333 /* Only consider uses that have a single definition. */
1334 def = get_def_for_use (use);
1337 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
1339 if (DF_REF_IS_ARTIFICIAL (def))
1342 /* Do not propagate loop invariant definitions inside the loop. */
1343 if (DF_REF_BB (def)->loop_father != DF_REF_BB (use)->loop_father)
1346 /* Check if the use is still present in the insn! */
1347 use_insn = DF_REF_INSN (use);
1348 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1349 parent = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1351 parent = PATTERN (use_insn);
1353 if (!reg_mentioned_p (DF_REF_REG (use), parent))
1356 def_insn = DF_REF_INSN (def);
1357 if (multiple_sets (def_insn))
1359 def_set = single_set (def_insn);
1363 /* Only try one kind of propagation. If two are possible, we'll
1364 do it on the following iterations. */
1365 if (!forward_propagate_and_simplify (use, def_insn, def_set))
1366 forward_propagate_subreg (use, def_insn, def_set);
1374 calculate_dominance_info (CDI_DOMINATORS);
1376 /* We do not always want to propagate into loops, so we have to find
1377 loops and be careful about them. But we have to call flow_loops_find
1378 before df_analyze, because flow_loops_find may introduce new jump
1379 insns (sadly) if we are not working in cfglayout mode. */
1380 loop_optimizer_init (0);
1382 build_single_def_use_links ();
1383 df_set_flags (DF_DEFER_INSN_RESCAN);
1389 loop_optimizer_finalize ();
1391 VEC_free (df_ref, heap, use_def_ref);
1392 free_dominance_info (CDI_DOMINATORS);
1394 delete_trivially_dead_insns (get_insns (), max_reg_num ());
1398 "\nNumber of successful forward propagations: %d\n\n",
1403 /* Main entry point. */
1408 return optimize > 0 && flag_forward_propagate;
1418 /* Go through all the uses. update_df will create new ones at the
1419 end, and we'll go through them as well.
1421 Do not forward propagate addresses into loops until after unrolling.
1422 CSE did so because it was able to fix its own mess, but we are not. */
1424 for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1426 df_ref use = DF_USES_GET (i);
1428 if (DF_REF_TYPE (use) == DF_REF_REG_USE
1429 || DF_REF_BB (use)->loop_father == NULL
1430 /* The outer most loop is not really a loop. */
1431 || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
1432 forward_propagate_into (use);
1439 struct rtl_opt_pass pass_rtl_fwprop =
1443 "fwprop1", /* name */
1444 gate_fwprop, /* gate */
1445 fwprop, /* execute */
1448 0, /* static_pass_number */
1449 TV_FWPROP, /* tv_id */
1450 0, /* properties_required */
1451 0, /* properties_provided */
1452 0, /* properties_destroyed */
1453 0, /* todo_flags_start */
1454 TODO_df_finish | TODO_verify_rtl_sharing |
1455 TODO_dump_func /* todo_flags_finish */
1465 /* Go through all the uses. update_df will create new ones at the
1466 end, and we'll go through them as well. */
1467 for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1469 df_ref use = DF_USES_GET (i);
1471 if (DF_REF_TYPE (use) != DF_REF_REG_USE
1472 && DF_REF_BB (use)->loop_father != NULL
1473 /* The outer most loop is not really a loop. */
1474 && loop_outer (DF_REF_BB (use)->loop_father) != NULL)
1475 forward_propagate_into (use);
1483 struct rtl_opt_pass pass_rtl_fwprop_addr =
1487 "fwprop2", /* name */
1488 gate_fwprop, /* gate */
1489 fwprop_addr, /* execute */
1492 0, /* static_pass_number */
1493 TV_FWPROP, /* tv_id */
1494 0, /* properties_required */
1495 0, /* properties_provided */
1496 0, /* properties_destroyed */
1497 0, /* todo_flags_start */
1498 TODO_df_finish | TODO_verify_rtl_sharing |
1499 TODO_dump_func /* todo_flags_finish */