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 VEC(df_ref,heap) *use_def_ref;
122 VEC(df_ref,heap) *reg_defs;
123 VEC(df_ref,heap) *reg_defs_stack;
126 /* Return the only def in USE's use-def chain, or NULL if there is
127 more than one def in the chain. */
130 get_def_for_use (df_ref use)
132 return VEC_index (df_ref, use_def_ref, DF_REF_ID (use));
136 /* Update the reg_defs vector with non-partial definitions in DEF_REC.
137 TOP_FLAG says which artificials uses should be used, when DEF_REC
138 is an artificial def vector. LOCAL_MD is modified as after a
139 df_md_simulate_* function; we do more or less the same processing
140 done there, so we do not use those functions. */
142 #define DF_MD_GEN_FLAGS \
143 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
146 process_defs (bitmap local_md, df_ref *def_rec, int top_flag)
149 while ((def = *def_rec++) != NULL)
151 df_ref curr_def = VEC_index (df_ref, reg_defs, DF_REF_REGNO (def));
154 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag)
157 dregno = DF_REF_REGNO (def);
159 VEC_safe_push (df_ref, heap, reg_defs_stack, curr_def);
162 /* Do not store anything if "transitioning" from NULL to NULL. But
163 otherwise, push a special entry on the stack to tell the
164 leave_block callback that the entry in reg_defs was NULL. */
165 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
168 VEC_safe_push (df_ref, heap, reg_defs_stack, def);
171 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
173 bitmap_set_bit (local_md, dregno);
174 VEC_replace (df_ref, reg_defs, dregno, NULL);
178 bitmap_clear_bit (local_md, dregno);
179 VEC_replace (df_ref, reg_defs, dregno, def);
185 /* Fill the use_def_ref vector with values for the uses in USE_REC,
186 taking reaching definitions info from LOCAL_MD and REG_DEFS.
187 TOP_FLAG says which artificials uses should be used, when USE_REC
188 is an artificial use vector. */
191 process_uses (bitmap local_md, df_ref *use_rec, int top_flag)
194 while ((use = *use_rec++) != NULL)
195 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag)
197 unsigned int uregno = DF_REF_REGNO (use);
198 if (VEC_index (df_ref, reg_defs, uregno)
199 && !bitmap_bit_p (local_md, uregno))
200 VEC_replace (df_ref, use_def_ref, DF_REF_ID (use),
201 VEC_index (df_ref, reg_defs, uregno));
207 single_def_use_enter_block (struct dom_walk_data *walk_data, basic_block bb)
209 bitmap local_md = (bitmap) walk_data->global_data;
210 int bb_index = bb->index;
211 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
214 bitmap_copy (local_md, bb_info->in);
216 /* Push a marker for the leave_block callback. */
217 VEC_safe_push (df_ref, heap, reg_defs_stack, NULL);
219 process_uses (local_md, df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
220 process_defs (local_md, df_get_artificial_defs (bb_index), DF_REF_AT_TOP);
222 FOR_BB_INSNS (bb, insn)
225 unsigned int uid = INSN_UID (insn);
226 process_uses (local_md, DF_INSN_UID_USES (uid), 0);
227 process_uses (local_md, DF_INSN_UID_EQ_USES (uid), 0);
228 process_defs (local_md, DF_INSN_UID_DEFS (uid), 0);
231 process_uses (local_md, df_get_artificial_uses (bb_index), 0);
232 process_defs (local_md, df_get_artificial_defs (bb_index), 0);
235 /* Pop the definitions created in this basic block when leaving its
239 single_def_use_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
240 basic_block bb ATTRIBUTE_UNUSED)
243 while ((saved_def = VEC_pop (df_ref, reg_defs_stack)) != NULL)
245 unsigned int dregno = DF_REF_REGNO (saved_def);
247 /* See also process_defs. */
248 if (saved_def == VEC_index (df_ref, reg_defs, dregno))
249 VEC_replace (df_ref, reg_defs, dregno, NULL);
251 VEC_replace (df_ref, reg_defs, dregno, saved_def);
256 /* Build a vector holding the reaching definitions of uses reached by a
257 single dominating definition. */
260 build_single_def_use_links (void)
262 struct dom_walk_data walk_data;
265 /* We use the multiple definitions problem to compute our restricted
267 df_set_flags (DF_EQ_NOTES);
268 df_md_add_problem ();
270 df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
272 use_def_ref = VEC_alloc (df_ref, heap, DF_USES_TABLE_SIZE ());
273 VEC_safe_grow_cleared (df_ref, heap, use_def_ref, DF_USES_TABLE_SIZE ());
275 reg_defs = VEC_alloc (df_ref, heap, max_reg_num ());
276 VEC_safe_grow_cleared (df_ref, heap, reg_defs, max_reg_num ());
278 reg_defs_stack = VEC_alloc (df_ref, heap, n_basic_blocks * 10);
279 local_md = BITMAP_ALLOC (NULL);
281 /* Walk the dominator tree looking for single reaching definitions
282 dominating the uses. This is similar to how SSA form is built. */
283 walk_data.dom_direction = CDI_DOMINATORS;
284 walk_data.initialize_block_local_data = NULL;
285 walk_data.before_dom_children = single_def_use_enter_block;
286 walk_data.after_dom_children = single_def_use_leave_block;
287 walk_data.global_data = local_md;
289 init_walk_dominator_tree (&walk_data);
290 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
291 fini_walk_dominator_tree (&walk_data);
293 BITMAP_FREE (local_md);
294 VEC_free (df_ref, heap, reg_defs);
295 VEC_free (df_ref, heap, reg_defs_stack);
299 /* Do not try to replace constant addresses or addresses of local and
300 argument slots. These MEM expressions are made only once and inserted
301 in many instructions, as well as being used to control symbol table
302 output. It is not safe to clobber them.
304 There are some uncommon cases where the address is already in a register
305 for some reason, but we cannot take advantage of that because we have
306 no easy way to unshare the MEM. In addition, looking up all stack
307 addresses is costly. */
310 can_simplify_addr (rtx addr)
314 if (CONSTANT_ADDRESS_P (addr))
317 if (GET_CODE (addr) == PLUS)
318 reg = XEXP (addr, 0);
323 || (REGNO (reg) != FRAME_POINTER_REGNUM
324 && REGNO (reg) != HARD_FRAME_POINTER_REGNUM
325 && REGNO (reg) != ARG_POINTER_REGNUM));
328 /* Returns a canonical version of X for the address, from the point of view,
329 that all multiplications are represented as MULT instead of the multiply
330 by a power of 2 being represented as ASHIFT.
332 Every ASHIFT we find has been made by simplify_gen_binary and was not
333 there before, so it is not shared. So we can do this in place. */
336 canonicalize_address (rtx x)
339 switch (GET_CODE (x))
342 if (CONST_INT_P (XEXP (x, 1))
343 && INTVAL (XEXP (x, 1)) < GET_MODE_BITSIZE (GET_MODE (x))
344 && INTVAL (XEXP (x, 1)) >= 0)
346 HOST_WIDE_INT shift = INTVAL (XEXP (x, 1));
348 XEXP (x, 1) = gen_int_mode ((HOST_WIDE_INT) 1 << shift,
356 if (GET_CODE (XEXP (x, 0)) == PLUS
357 || GET_CODE (XEXP (x, 0)) == ASHIFT
358 || GET_CODE (XEXP (x, 0)) == CONST)
359 canonicalize_address (XEXP (x, 0));
373 /* OLD is a memory address. Return whether it is good to use NEW instead,
374 for a memory access in the given MODE. */
377 should_replace_address (rtx old_rtx, rtx new_rtx, enum machine_mode mode,
382 if (rtx_equal_p (old_rtx, new_rtx) || !memory_address_p (mode, new_rtx))
385 /* Copy propagation is always ok. */
386 if (REG_P (old_rtx) && REG_P (new_rtx))
389 /* Prefer the new address if it is less expensive. */
390 gain = address_cost (old_rtx, mode, speed) - address_cost (new_rtx, mode, speed);
392 /* If the addresses have equivalent cost, prefer the new address
393 if it has the highest `rtx_cost'. That has the potential of
394 eliminating the most insns without additional costs, and it
395 is the same that cse.c used to do. */
397 gain = rtx_cost (new_rtx, SET, speed) - rtx_cost (old_rtx, SET, speed);
403 /* Flags for the last parameter of propagate_rtx_1. */
406 /* If PR_CAN_APPEAR is true, propagate_rtx_1 always returns true;
407 if it is false, propagate_rtx_1 returns false if, for at least
408 one occurrence OLD, it failed to collapse the result to a constant.
409 For example, (mult:M (reg:M A) (minus:M (reg:M B) (reg:M A))) may
410 collapse to zero if replacing (reg:M B) with (reg:M A).
412 PR_CAN_APPEAR is disregarded inside MEMs: in that case,
413 propagate_rtx_1 just tries to make cheaper and valid memory
417 /* If PR_HANDLE_MEM is not set, propagate_rtx_1 won't attempt any replacement
418 outside memory addresses. This is needed because propagate_rtx_1 does
419 not do any analysis on memory; thus it is very conservative and in general
420 it will fail if non-read-only MEMs are found in the source expression.
422 PR_HANDLE_MEM is set when the source of the propagation was not
423 another MEM. Then, it is safe not to treat non-read-only MEMs as
424 ``opaque'' objects. */
427 /* Set when costs should be optimized for speed. */
428 PR_OPTIMIZE_FOR_SPEED = 4
432 /* Replace all occurrences of OLD in *PX with NEW and try to simplify the
433 resulting expression. Replace *PX with a new RTL expression if an
434 occurrence of OLD was found.
436 This is only a wrapper around simplify-rtx.c: do not add any pattern
437 matching code here. (The sole exception is the handling of LO_SUM, but
438 that is because there is no simplify_gen_* function for LO_SUM). */
441 propagate_rtx_1 (rtx *px, rtx old_rtx, rtx new_rtx, int flags)
443 rtx x = *px, tem = NULL_RTX, op0, op1, op2;
444 enum rtx_code code = GET_CODE (x);
445 enum machine_mode mode = GET_MODE (x);
446 enum machine_mode op_mode;
447 bool can_appear = (flags & PR_CAN_APPEAR) != 0;
448 bool valid_ops = true;
450 if (!(flags & PR_HANDLE_MEM) && MEM_P (x) && !MEM_READONLY_P (x))
452 /* If unsafe, change MEMs to CLOBBERs or SCRATCHes (to preserve whether
453 they have side effects or not). */
454 *px = (side_effects_p (x)
455 ? gen_rtx_CLOBBER (GET_MODE (x), const0_rtx)
456 : gen_rtx_SCRATCH (GET_MODE (x)));
460 /* If X is OLD_RTX, return NEW_RTX. But not if replacing only within an
461 address, and we are *not* inside one. */
468 /* If this is an expression, try recursive substitution. */
469 switch (GET_RTX_CLASS (code))
473 op_mode = GET_MODE (op0);
474 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
475 if (op0 == XEXP (x, 0))
477 tem = simplify_gen_unary (code, mode, op0, op_mode);
484 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
485 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
486 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
488 tem = simplify_gen_binary (code, mode, op0, op1);
492 case RTX_COMM_COMPARE:
495 op_mode = GET_MODE (op0) != VOIDmode ? GET_MODE (op0) : GET_MODE (op1);
496 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
497 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
498 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
500 tem = simplify_gen_relational (code, mode, op_mode, op0, op1);
504 case RTX_BITFIELD_OPS:
508 op_mode = GET_MODE (op0);
509 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
510 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
511 valid_ops &= propagate_rtx_1 (&op2, old_rtx, new_rtx, flags);
512 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1) && op2 == XEXP (x, 2))
514 if (op_mode == VOIDmode)
515 op_mode = GET_MODE (op0);
516 tem = simplify_gen_ternary (code, mode, op_mode, op0, op1, op2);
520 /* The only case we try to handle is a SUBREG. */
524 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
525 if (op0 == XEXP (x, 0))
527 tem = simplify_gen_subreg (mode, op0, GET_MODE (SUBREG_REG (x)),
533 if (code == MEM && x != new_rtx)
538 /* There are some addresses that we cannot work on. */
539 if (!can_simplify_addr (op0))
542 op0 = new_op0 = targetm.delegitimize_address (op0);
543 valid_ops &= propagate_rtx_1 (&new_op0, old_rtx, new_rtx,
544 flags | PR_CAN_APPEAR);
546 /* Dismiss transformation that we do not want to carry on. */
549 || !(GET_MODE (new_op0) == GET_MODE (op0)
550 || GET_MODE (new_op0) == VOIDmode))
553 canonicalize_address (new_op0);
555 /* Copy propagations are always ok. Otherwise check the costs. */
556 if (!(REG_P (old_rtx) && REG_P (new_rtx))
557 && !should_replace_address (op0, new_op0, GET_MODE (x),
558 flags & PR_OPTIMIZE_FOR_SPEED))
561 tem = replace_equiv_address_nv (x, new_op0);
564 else if (code == LO_SUM)
569 /* The only simplification we do attempts to remove references to op0
570 or make it constant -- in both cases, op0's invalidity will not
571 make the result invalid. */
572 propagate_rtx_1 (&op0, old_rtx, new_rtx, flags | PR_CAN_APPEAR);
573 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
574 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
577 /* (lo_sum (high x) x) -> x */
578 if (GET_CODE (op0) == HIGH && rtx_equal_p (XEXP (op0, 0), op1))
581 tem = gen_rtx_LO_SUM (mode, op0, op1);
583 /* OP1 is likely not a legitimate address, otherwise there would have
584 been no LO_SUM. We want it to disappear if it is invalid, return
585 false in that case. */
586 return memory_address_p (mode, tem);
589 else if (code == REG)
591 if (rtx_equal_p (x, old_rtx))
603 /* No change, no trouble. */
609 /* The replacement we made so far is valid, if all of the recursive
610 replacements were valid, or we could simplify everything to
612 return valid_ops || can_appear || CONSTANT_P (tem);
616 /* for_each_rtx traversal function that returns 1 if BODY points to
617 a non-constant mem. */
620 varying_mem_p (rtx *body, void *data ATTRIBUTE_UNUSED)
623 return MEM_P (x) && !MEM_READONLY_P (x);
627 /* Replace all occurrences of OLD in X with NEW and try to simplify the
628 resulting expression (in mode MODE). Return a new expression if it is
629 a constant, otherwise X.
631 Simplifications where occurrences of NEW collapse to a constant are always
632 accepted. All simplifications are accepted if NEW is a pseudo too.
633 Otherwise, we accept simplifications that have a lower or equal cost. */
636 propagate_rtx (rtx x, enum machine_mode mode, rtx old_rtx, rtx new_rtx,
643 if (REG_P (new_rtx) && REGNO (new_rtx) < FIRST_PSEUDO_REGISTER)
647 if (REG_P (new_rtx) || CONSTANT_P (new_rtx))
648 flags |= PR_CAN_APPEAR;
649 if (!for_each_rtx (&new_rtx, varying_mem_p, NULL))
650 flags |= PR_HANDLE_MEM;
653 flags |= PR_OPTIMIZE_FOR_SPEED;
656 collapsed = propagate_rtx_1 (&tem, old_rtx, copy_rtx (new_rtx), flags);
657 if (tem == x || !collapsed)
660 /* gen_lowpart_common will not be able to process VOIDmode entities other
662 if (GET_MODE (tem) == VOIDmode && !CONST_INT_P (tem))
665 if (GET_MODE (tem) == VOIDmode)
666 tem = rtl_hooks.gen_lowpart_no_emit (mode, tem);
668 gcc_assert (GET_MODE (tem) == mode);
676 /* Return true if the register from reference REF is killed
677 between FROM to (but not including) TO. */
680 local_ref_killed_between_p (df_ref ref, rtx from, rtx to)
684 for (insn = from; insn != to; insn = NEXT_INSN (insn))
690 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
692 df_ref def = *def_rec;
693 if (DF_REF_REGNO (ref) == DF_REF_REGNO (def))
701 /* Check if the given DEF is available in INSN. This would require full
702 computation of available expressions; we check only restricted conditions:
703 - if DEF is the sole definition of its register, go ahead;
704 - in the same basic block, we check for no definitions killing the
705 definition of DEF_INSN;
706 - if USE's basic block has DEF's basic block as the sole predecessor,
707 we check if the definition is killed after DEF_INSN or before
708 TARGET_INSN insn, in their respective basic blocks. */
710 use_killed_between (df_ref use, rtx def_insn, rtx target_insn)
712 basic_block def_bb = BLOCK_FOR_INSN (def_insn);
713 basic_block target_bb = BLOCK_FOR_INSN (target_insn);
717 /* We used to have a def reaching a use that is _before_ the def,
718 with the def not dominating the use even though the use and def
719 are in the same basic block, when a register may be used
720 uninitialized in a loop. This should not happen anymore since
721 we do not use reaching definitions, but still we test for such
722 cases and assume that DEF is not available. */
723 if (def_bb == target_bb
724 ? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn)
725 : !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb))
728 /* Check if the reg in USE has only one definition. We already
729 know that this definition reaches use, or we wouldn't be here.
730 However, this is invalid for hard registers because if they are
731 live at the beginning of the function it does not mean that we
732 have an uninitialized access. */
733 regno = DF_REF_REGNO (use);
734 def = DF_REG_DEF_CHAIN (regno);
736 && DF_REF_NEXT_REG (def) == NULL
737 && regno >= FIRST_PSEUDO_REGISTER)
740 /* Check locally if we are in the same basic block. */
741 if (def_bb == target_bb)
742 return local_ref_killed_between_p (use, def_insn, target_insn);
744 /* Finally, if DEF_BB is the sole predecessor of TARGET_BB. */
745 if (single_pred_p (target_bb)
746 && single_pred (target_bb) == def_bb)
750 /* See if USE is killed between DEF_INSN and the last insn in the
751 basic block containing DEF_INSN. */
752 x = df_bb_regno_last_def_find (def_bb, regno);
753 if (x && DF_INSN_LUID (DF_REF_INSN (x)) >= DF_INSN_LUID (def_insn))
756 /* See if USE is killed between TARGET_INSN and the first insn in the
757 basic block containing TARGET_INSN. */
758 x = df_bb_regno_first_def_find (target_bb, regno);
759 if (x && DF_INSN_LUID (DF_REF_INSN (x)) < DF_INSN_LUID (target_insn))
765 /* Otherwise assume the worst case. */
770 /* Check if all uses in DEF_INSN can be used in TARGET_INSN. This
771 would require full computation of available expressions;
772 we check only restricted conditions, see use_killed_between. */
774 all_uses_available_at (rtx def_insn, rtx target_insn)
777 struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
778 rtx def_set = single_set (def_insn);
780 gcc_assert (def_set);
782 /* If target_insn comes right after def_insn, which is very common
783 for addresses, we can use a quicker test. */
784 if (NEXT_INSN (def_insn) == target_insn
785 && REG_P (SET_DEST (def_set)))
787 rtx def_reg = SET_DEST (def_set);
789 /* If the insn uses the reg that it defines, the substitution is
791 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
793 df_ref use = *use_rec;
794 if (rtx_equal_p (DF_REF_REG (use), def_reg))
797 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
799 df_ref use = *use_rec;
800 if (rtx_equal_p (DF_REF_REG (use), def_reg))
806 /* Look at all the uses of DEF_INSN, and see if they are not
807 killed between DEF_INSN and TARGET_INSN. */
808 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
810 df_ref use = *use_rec;
811 if (use_killed_between (use, def_insn, target_insn))
814 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
816 df_ref use = *use_rec;
817 if (use_killed_between (use, def_insn, target_insn))
826 struct find_occurrence_data
832 /* Callback for for_each_rtx, used in find_occurrence.
833 See if PX is the rtx we have to find. Return 1 to stop for_each_rtx
834 if successful, or 0 to continue traversing otherwise. */
837 find_occurrence_callback (rtx *px, void *data)
839 struct find_occurrence_data *fod = (struct find_occurrence_data *) data;
841 rtx find = fod->find;
852 /* Return a pointer to one of the occurrences of register FIND in *PX. */
855 find_occurrence (rtx *px, rtx find)
857 struct find_occurrence_data data;
859 gcc_assert (REG_P (find)
860 || (GET_CODE (find) == SUBREG
861 && REG_P (SUBREG_REG (find))));
865 for_each_rtx (px, find_occurrence_callback, &data);
870 /* Inside INSN, the expression rooted at *LOC has been changed, moving some
871 uses from USE_VEC. Find those that are present, and create new items
872 in the data flow object of the pass. Mark any new uses as having the
875 update_df (rtx insn, rtx *loc, df_ref *use_rec, enum df_ref_type type,
878 bool changed = false;
880 /* Add a use for the registers that were propagated. */
883 df_ref use = *use_rec;
884 df_ref orig_use = use, new_use;
887 enum machine_mode mode = VOIDmode;
888 rtx *new_loc = find_occurrence (loc, DF_REF_REG (orig_use));
894 if (DF_REF_FLAGS_IS_SET (orig_use, DF_REF_SIGN_EXTRACT | DF_REF_ZERO_EXTRACT))
896 width = DF_REF_EXTRACT_WIDTH (orig_use);
897 offset = DF_REF_EXTRACT_OFFSET (orig_use);
898 mode = DF_REF_EXTRACT_MODE (orig_use);
901 /* Add a new insn use. Use the original type, because it says if the
902 use was within a MEM. */
903 new_use = df_ref_create (DF_REF_REG (orig_use), new_loc,
904 insn, BLOCK_FOR_INSN (insn),
905 type, DF_REF_FLAGS (orig_use) | new_flags,
906 width, offset, mode);
908 /* Set up the use-def chain. */
909 gcc_assert (DF_REF_ID (new_use) == (int) VEC_length (df_ref, use_def_ref));
910 VEC_safe_push (df_ref, heap, use_def_ref, get_def_for_use (orig_use));
914 df_insn_rescan (insn);
918 /* Try substituting NEW into LOC, which originated from forward propagation
919 of USE's value from DEF_INSN. SET_REG_EQUAL says whether we are
920 substituting the whole SET_SRC, so we can set a REG_EQUAL note if the
921 new insn is not recognized. Return whether the substitution was
925 try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx def_insn, bool set_reg_equal)
927 rtx insn = DF_REF_INSN (use);
928 enum df_ref_type type = DF_REF_TYPE (use);
929 int flags = DF_REF_FLAGS (use);
930 rtx set = single_set (insn);
931 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
935 /* forward_propagate_subreg may be operating on an instruction with
936 multiple sets. If so, assume the cost of the new instruction is
937 not greater than the old one. */
939 old_cost = rtx_cost (SET_SRC (set), SET, speed);
942 fprintf (dump_file, "\nIn insn %d, replacing\n ", INSN_UID (insn));
943 print_inline_rtx (dump_file, *loc, 2);
944 fprintf (dump_file, "\n with ");
945 print_inline_rtx (dump_file, new_rtx, 2);
946 fprintf (dump_file, "\n");
949 validate_unshare_change (insn, loc, new_rtx, true);
950 if (!verify_changes (0))
953 fprintf (dump_file, "Changes to insn %d not recognized\n",
958 else if (DF_REF_TYPE (use) == DF_REF_REG_USE
960 && rtx_cost (SET_SRC (set), SET, speed) > old_cost)
963 fprintf (dump_file, "Changes to insn %d not profitable\n",
971 fprintf (dump_file, "Changed insn %d\n", INSN_UID (insn));
977 confirm_change_group ();
981 if (!CONSTANT_P (new_rtx))
983 struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
984 update_df (insn, loc, DF_INSN_INFO_USES (insn_info), type, flags);
985 update_df (insn, loc, DF_INSN_INFO_EQ_USES (insn_info), type, flags);
992 /* Can also record a simplified value in a REG_EQUAL note,
993 making a new one if one does not already exist. */
997 fprintf (dump_file, " Setting REG_EQUAL note\n");
999 set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
1001 /* ??? Is this still necessary if we add the note through
1002 set_unique_reg_note? */
1003 if (!CONSTANT_P (new_rtx))
1005 struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
1006 update_df (insn, loc, DF_INSN_INFO_USES (insn_info),
1007 type, DF_REF_IN_NOTE);
1008 update_df (insn, loc, DF_INSN_INFO_EQ_USES (insn_info),
1009 type, DF_REF_IN_NOTE);
1017 /* For the given single_set INSN, containing SRC known to be a
1018 ZERO_EXTEND or SIGN_EXTEND of a register, return true if INSN
1019 is redundant due to the register being set by a LOAD_EXTEND_OP
1020 load from memory. */
1023 free_load_extend (rtx src, rtx insn)
1029 reg = XEXP (src, 0);
1030 #ifdef LOAD_EXTEND_OP
1031 if (LOAD_EXTEND_OP (GET_MODE (reg)) != GET_CODE (src))
1035 for (use_vec = DF_INSN_USES (insn); *use_vec; use_vec++)
1039 if (!DF_REF_IS_ARTIFICIAL (use)
1040 && DF_REF_TYPE (use) == DF_REF_REG_USE
1041 && DF_REF_REG (use) == reg)
1047 def = get_def_for_use (use);
1051 if (DF_REF_IS_ARTIFICIAL (def))
1054 if (NONJUMP_INSN_P (DF_REF_INSN (def)))
1056 rtx patt = PATTERN (DF_REF_INSN (def));
1058 if (GET_CODE (patt) == SET
1059 && GET_CODE (SET_SRC (patt)) == MEM
1060 && rtx_equal_p (SET_DEST (patt), reg))
1066 /* If USE is a subreg, see if it can be replaced by a pseudo. */
1069 forward_propagate_subreg (df_ref use, rtx def_insn, rtx def_set)
1071 rtx use_reg = DF_REF_REG (use);
1074 /* Only consider subregs... */
1075 enum machine_mode use_mode = GET_MODE (use_reg);
1076 if (GET_CODE (use_reg) != SUBREG
1077 || !REG_P (SET_DEST (def_set)))
1080 /* If this is a paradoxical SUBREG... */
1081 if (GET_MODE_SIZE (use_mode)
1082 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (use_reg))))
1084 /* If this is a paradoxical SUBREG, we have no idea what value the
1085 extra bits would have. However, if the operand is equivalent to
1086 a SUBREG whose operand is the same as our mode, and all the modes
1087 are within a word, we can just use the inner operand because
1088 these SUBREGs just say how to treat the register. */
1089 use_insn = DF_REF_INSN (use);
1090 src = SET_SRC (def_set);
1091 if (GET_CODE (src) == SUBREG
1092 && REG_P (SUBREG_REG (src))
1093 && GET_MODE (SUBREG_REG (src)) == use_mode
1094 && subreg_lowpart_p (src)
1095 && all_uses_available_at (def_insn, use_insn))
1096 return try_fwprop_subst (use, DF_REF_LOC (use), SUBREG_REG (src),
1100 /* If this is a SUBREG of a ZERO_EXTEND or SIGN_EXTEND, and the SUBREG
1101 is the low part of the reg being extended then just use the inner
1102 operand. Don't do this if the ZERO_EXTEND or SIGN_EXTEND insn will
1103 be removed due to it matching a LOAD_EXTEND_OP load from memory. */
1104 else if (subreg_lowpart_p (use_reg))
1106 use_insn = DF_REF_INSN (use);
1107 src = SET_SRC (def_set);
1108 if ((GET_CODE (src) == ZERO_EXTEND
1109 || GET_CODE (src) == SIGN_EXTEND)
1110 && REG_P (XEXP (src, 0))
1111 && GET_MODE (XEXP (src, 0)) == use_mode
1112 && !free_load_extend (src, def_insn)
1113 && all_uses_available_at (def_insn, use_insn))
1114 return try_fwprop_subst (use, DF_REF_LOC (use), XEXP (src, 0),
1121 /* Try to replace USE with SRC (defined in DEF_INSN) in __asm. */
1124 forward_propagate_asm (df_ref use, rtx def_insn, rtx def_set, rtx reg)
1126 rtx use_insn = DF_REF_INSN (use), src, use_pat, asm_operands, new_rtx, *loc;
1130 gcc_assert ((DF_REF_FLAGS (use) & DF_REF_IN_NOTE) == 0);
1132 src = SET_SRC (def_set);
1133 use_pat = PATTERN (use_insn);
1135 /* In __asm don't replace if src might need more registers than
1136 reg, as that could increase register pressure on the __asm. */
1137 use_vec = DF_INSN_USES (def_insn);
1138 if (use_vec[0] && use_vec[1])
1141 speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
1142 asm_operands = NULL_RTX;
1143 switch (GET_CODE (use_pat))
1146 asm_operands = use_pat;
1149 if (MEM_P (SET_DEST (use_pat)))
1151 loc = &SET_DEST (use_pat);
1152 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1154 validate_unshare_change (use_insn, loc, new_rtx, true);
1156 asm_operands = SET_SRC (use_pat);
1159 for (i = 0; i < XVECLEN (use_pat, 0); i++)
1160 if (GET_CODE (XVECEXP (use_pat, 0, i)) == SET)
1162 if (MEM_P (SET_DEST (XVECEXP (use_pat, 0, i))))
1164 loc = &SET_DEST (XVECEXP (use_pat, 0, i));
1165 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg,
1168 validate_unshare_change (use_insn, loc, new_rtx, true);
1170 asm_operands = SET_SRC (XVECEXP (use_pat, 0, i));
1172 else if (GET_CODE (XVECEXP (use_pat, 0, i)) == ASM_OPERANDS)
1173 asm_operands = XVECEXP (use_pat, 0, i);
1179 gcc_assert (asm_operands && GET_CODE (asm_operands) == ASM_OPERANDS);
1180 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (asm_operands); i++)
1182 loc = &ASM_OPERANDS_INPUT (asm_operands, i);
1183 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1185 validate_unshare_change (use_insn, loc, new_rtx, true);
1188 if (num_changes_pending () == 0 || !apply_change_group ())
1195 /* Try to replace USE with SRC (defined in DEF_INSN) and simplify the
1199 forward_propagate_and_simplify (df_ref use, rtx def_insn, rtx def_set)
1201 rtx use_insn = DF_REF_INSN (use);
1202 rtx use_set = single_set (use_insn);
1203 rtx src, reg, new_rtx, *loc;
1205 enum machine_mode mode;
1208 if (INSN_CODE (use_insn) < 0)
1209 asm_use = asm_noperands (PATTERN (use_insn));
1211 if (!use_set && asm_use < 0 && !DEBUG_INSN_P (use_insn))
1214 /* Do not propagate into PC, CC0, etc. */
1215 if (use_set && GET_MODE (SET_DEST (use_set)) == VOIDmode)
1218 /* If def and use are subreg, check if they match. */
1219 reg = DF_REF_REG (use);
1220 if (GET_CODE (reg) == SUBREG
1221 && GET_CODE (SET_DEST (def_set)) == SUBREG
1222 && (SUBREG_BYTE (SET_DEST (def_set)) != SUBREG_BYTE (reg)
1223 || GET_MODE (SET_DEST (def_set)) != GET_MODE (reg)))
1226 /* Check if the def had a subreg, but the use has the whole reg. */
1227 if (REG_P (reg) && GET_CODE (SET_DEST (def_set)) == SUBREG)
1230 /* Check if the use has a subreg, but the def had the whole reg. Unlike the
1231 previous case, the optimization is possible and often useful indeed. */
1232 if (GET_CODE (reg) == SUBREG && REG_P (SET_DEST (def_set)))
1233 reg = SUBREG_REG (reg);
1235 /* Check if the substitution is valid (last, because it's the most
1236 expensive check!). */
1237 src = SET_SRC (def_set);
1238 if (!CONSTANT_P (src) && !all_uses_available_at (def_insn, use_insn))
1241 /* Check if the def is loading something from the constant pool; in this
1242 case we would undo optimization such as compress_float_constant.
1243 Still, we can set a REG_EQUAL note. */
1244 if (MEM_P (src) && MEM_READONLY_P (src))
1246 rtx x = avoid_constant_pool_reference (src);
1247 if (x != src && use_set)
1249 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1250 rtx old_rtx = note ? XEXP (note, 0) : SET_SRC (use_set);
1251 rtx new_rtx = simplify_replace_rtx (old_rtx, src, x);
1252 if (old_rtx != new_rtx)
1253 set_unique_reg_note (use_insn, REG_EQUAL, copy_rtx (new_rtx));
1259 return forward_propagate_asm (use, def_insn, def_set, reg);
1261 /* Else try simplifying. */
1263 if (DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE)
1265 loc = &SET_DEST (use_set);
1266 set_reg_equal = false;
1270 loc = &INSN_VAR_LOCATION_LOC (use_insn);
1271 set_reg_equal = false;
1275 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1276 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1277 loc = &XEXP (note, 0);
1279 loc = &SET_SRC (use_set);
1281 /* Do not replace an existing REG_EQUAL note if the insn is not
1282 recognized. Either we're already replacing in the note, or
1283 we'll separately try plugging the definition in the note and
1285 set_reg_equal = (note == NULL_RTX);
1288 if (GET_MODE (*loc) == VOIDmode)
1289 mode = GET_MODE (SET_DEST (use_set));
1291 mode = GET_MODE (*loc);
1293 new_rtx = propagate_rtx (*loc, mode, reg, src,
1294 optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn)));
1299 return try_fwprop_subst (use, loc, new_rtx, def_insn, set_reg_equal);
1303 /* Given a use USE of an insn, if it has a single reaching
1304 definition, try to forward propagate it into that insn. */
1307 forward_propagate_into (df_ref use)
1310 rtx def_insn, def_set, use_insn;
1313 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
1315 if (DF_REF_IS_ARTIFICIAL (use))
1318 /* Only consider uses that have a single definition. */
1319 def = get_def_for_use (use);
1322 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
1324 if (DF_REF_IS_ARTIFICIAL (def))
1327 /* Do not propagate loop invariant definitions inside the loop. */
1328 if (DF_REF_BB (def)->loop_father != DF_REF_BB (use)->loop_father)
1331 /* Check if the use is still present in the insn! */
1332 use_insn = DF_REF_INSN (use);
1333 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1334 parent = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1336 parent = PATTERN (use_insn);
1338 if (!reg_mentioned_p (DF_REF_REG (use), parent))
1341 def_insn = DF_REF_INSN (def);
1342 if (multiple_sets (def_insn))
1344 def_set = single_set (def_insn);
1348 /* Only try one kind of propagation. If two are possible, we'll
1349 do it on the following iterations. */
1350 if (!forward_propagate_and_simplify (use, def_insn, def_set))
1351 forward_propagate_subreg (use, def_insn, def_set);
1359 calculate_dominance_info (CDI_DOMINATORS);
1361 /* We do not always want to propagate into loops, so we have to find
1362 loops and be careful about them. But we have to call flow_loops_find
1363 before df_analyze, because flow_loops_find may introduce new jump
1364 insns (sadly) if we are not working in cfglayout mode. */
1365 loop_optimizer_init (0);
1367 build_single_def_use_links ();
1368 df_set_flags (DF_DEFER_INSN_RESCAN);
1374 loop_optimizer_finalize ();
1376 VEC_free (df_ref, heap, use_def_ref);
1377 free_dominance_info (CDI_DOMINATORS);
1379 delete_trivially_dead_insns (get_insns (), max_reg_num ());
1383 "\nNumber of successful forward propagations: %d\n\n",
1385 df_remove_problem (df_chain);
1390 /* Main entry point. */
1395 return optimize > 0 && flag_forward_propagate;
1405 /* Go through all the uses. update_df will create new ones at the
1406 end, and we'll go through them as well.
1408 Do not forward propagate addresses into loops until after unrolling.
1409 CSE did so because it was able to fix its own mess, but we are not. */
1411 for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1413 df_ref use = DF_USES_GET (i);
1415 if (DF_REF_TYPE (use) == DF_REF_REG_USE
1416 || DF_REF_BB (use)->loop_father == NULL
1417 /* The outer most loop is not really a loop. */
1418 || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
1419 forward_propagate_into (use);
1426 struct rtl_opt_pass pass_rtl_fwprop =
1430 "fwprop1", /* name */
1431 gate_fwprop, /* gate */
1432 fwprop, /* execute */
1435 0, /* static_pass_number */
1436 TV_FWPROP, /* tv_id */
1437 0, /* properties_required */
1438 0, /* properties_provided */
1439 0, /* properties_destroyed */
1440 0, /* todo_flags_start */
1441 TODO_df_finish | TODO_verify_rtl_sharing |
1442 TODO_dump_func /* todo_flags_finish */
1452 /* Go through all the uses. update_df will create new ones at the
1453 end, and we'll go through them as well. */
1454 for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1456 df_ref use = DF_USES_GET (i);
1458 if (DF_REF_TYPE (use) != DF_REF_REG_USE
1459 && DF_REF_BB (use)->loop_father != NULL
1460 /* The outer most loop is not really a loop. */
1461 && loop_outer (DF_REF_BB (use)->loop_father) != NULL)
1462 forward_propagate_into (use);
1470 struct rtl_opt_pass pass_rtl_fwprop_addr =
1474 "fwprop2", /* name */
1475 gate_fwprop, /* gate */
1476 fwprop_addr, /* execute */
1479 0, /* static_pass_number */
1480 TV_FWPROP, /* tv_id */
1481 0, /* properties_required */
1482 0, /* properties_provided */
1483 0, /* properties_destroyed */
1484 0, /* todo_flags_start */
1485 TODO_df_finish | TODO_verify_rtl_sharing |
1486 TODO_dump_func /* todo_flags_finish */