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 #ifdef LOAD_EXTEND_OP
1019 get_reg_use_in (rtx insn
, rtx reg
)
1023 for (use_vec
= DF_INSN_USES (insn
); *use_vec
; use_vec
++)
1025 df_ref use
= *use_vec
;
1027 if (!DF_REF_IS_ARTIFICIAL (use
)
1028 && DF_REF_TYPE (use
) == DF_REF_REG_USE
1029 && DF_REF_REG (use
) == reg
)
1036 /* If USE is a subreg, see if it can be replaced by a pseudo. */
1039 forward_propagate_subreg (df_ref use
, rtx def_insn
, rtx def_set
)
1041 rtx use_reg
= DF_REF_REG (use
);
1044 /* Only consider subregs... */
1045 enum machine_mode use_mode
= GET_MODE (use_reg
);
1046 if (GET_CODE (use_reg
) != SUBREG
1047 || !REG_P (SET_DEST (def_set
)))
1050 /* If this is a paradoxical SUBREG... */
1051 if (GET_MODE_SIZE (use_mode
)
1052 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (use_reg
))))
1054 /* If this is a paradoxical SUBREG, we have no idea what value the
1055 extra bits would have. However, if the operand is equivalent to
1056 a SUBREG whose operand is the same as our mode, and all the modes
1057 are within a word, we can just use the inner operand because
1058 these SUBREGs just say how to treat the register. */
1059 use_insn
= DF_REF_INSN (use
);
1060 src
= SET_SRC (def_set
);
1061 if (GET_CODE (src
) == SUBREG
1062 && REG_P (SUBREG_REG (src
))
1063 && GET_MODE (SUBREG_REG (src
)) == use_mode
1064 && subreg_lowpart_p (src
)
1065 && all_uses_available_at (def_insn
, use_insn
))
1066 return try_fwprop_subst (use
, DF_REF_LOC (use
), SUBREG_REG (src
),
1070 /* If this is a SUBREG of a ZERO_EXTEND or SIGN_EXTEND, and the SUBREG
1071 is the low part of the reg being extended then just use the inner
1072 operand. Don't do this if the ZERO_EXTEND or SIGN_EXTEND insn will
1073 be removed due to it matching a LOAD_EXTEND_OP load from memory. */
1074 else if (subreg_lowpart_p (use_reg
))
1076 #ifdef LOAD_EXTEND_OP
1077 df_ref prev_use
, prev_def
;
1079 use_insn
= DF_REF_INSN (use
);
1080 src
= SET_SRC (def_set
);
1081 if ((GET_CODE (src
) == ZERO_EXTEND
1082 || GET_CODE (src
) == SIGN_EXTEND
)
1083 && REG_P (XEXP (src
, 0))
1084 && GET_MODE (XEXP (src
, 0)) == use_mode
1085 #ifdef LOAD_EXTEND_OP
1086 && !(LOAD_EXTEND_OP (use_mode
) == GET_CODE (src
)
1087 && (prev_use
= get_reg_use_in (def_insn
, XEXP (src
, 0))) != NULL
1088 && (prev_def
= get_def_for_use (prev_use
)) != NULL
1089 && !DF_REF_IS_ARTIFICIAL (prev_def
)
1090 && NONJUMP_INSN_P (DF_REF_INSN (prev_def
))
1091 && GET_CODE (PATTERN (DF_REF_INSN (prev_def
))) == SET
1092 && GET_CODE (SET_SRC (PATTERN (DF_REF_INSN (prev_def
)))) == MEM
1093 && rtx_equal_p (SET_DEST (PATTERN (DF_REF_INSN (prev_def
))),
1096 && all_uses_available_at (def_insn
, use_insn
))
1097 return try_fwprop_subst (use
, DF_REF_LOC (use
), XEXP (src
, 0),
1104 /* Try to replace USE with SRC (defined in DEF_INSN) in __asm. */
1107 forward_propagate_asm (df_ref use
, rtx def_insn
, rtx def_set
, rtx reg
)
1109 rtx use_insn
= DF_REF_INSN (use
), src
, use_pat
, asm_operands
, new_rtx
, *loc
;
1113 gcc_assert ((DF_REF_FLAGS (use
) & DF_REF_IN_NOTE
) == 0);
1115 src
= SET_SRC (def_set
);
1116 use_pat
= PATTERN (use_insn
);
1118 /* In __asm don't replace if src might need more registers than
1119 reg, as that could increase register pressure on the __asm. */
1120 use_vec
= DF_INSN_USES (def_insn
);
1121 if (use_vec
[0] && use_vec
[1])
1124 speed_p
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn
));
1125 asm_operands
= NULL_RTX
;
1126 switch (GET_CODE (use_pat
))
1129 asm_operands
= use_pat
;
1132 if (MEM_P (SET_DEST (use_pat
)))
1134 loc
= &SET_DEST (use_pat
);
1135 new_rtx
= propagate_rtx (*loc
, GET_MODE (*loc
), reg
, src
, speed_p
);
1137 validate_unshare_change (use_insn
, loc
, new_rtx
, true);
1139 asm_operands
= SET_SRC (use_pat
);
1142 for (i
= 0; i
< XVECLEN (use_pat
, 0); i
++)
1143 if (GET_CODE (XVECEXP (use_pat
, 0, i
)) == SET
)
1145 if (MEM_P (SET_DEST (XVECEXP (use_pat
, 0, i
))))
1147 loc
= &SET_DEST (XVECEXP (use_pat
, 0, i
));
1148 new_rtx
= propagate_rtx (*loc
, GET_MODE (*loc
), reg
,
1151 validate_unshare_change (use_insn
, loc
, new_rtx
, true);
1153 asm_operands
= SET_SRC (XVECEXP (use_pat
, 0, i
));
1155 else if (GET_CODE (XVECEXP (use_pat
, 0, i
)) == ASM_OPERANDS
)
1156 asm_operands
= XVECEXP (use_pat
, 0, i
);
1162 gcc_assert (asm_operands
&& GET_CODE (asm_operands
) == ASM_OPERANDS
);
1163 for (i
= 0; i
< ASM_OPERANDS_INPUT_LENGTH (asm_operands
); i
++)
1165 loc
= &ASM_OPERANDS_INPUT (asm_operands
, i
);
1166 new_rtx
= propagate_rtx (*loc
, GET_MODE (*loc
), reg
, src
, speed_p
);
1168 validate_unshare_change (use_insn
, loc
, new_rtx
, true);
1171 if (num_changes_pending () == 0 || !apply_change_group ())
1178 /* Try to replace USE with SRC (defined in DEF_INSN) and simplify the
1182 forward_propagate_and_simplify (df_ref use
, rtx def_insn
, rtx def_set
)
1184 rtx use_insn
= DF_REF_INSN (use
);
1185 rtx use_set
= single_set (use_insn
);
1186 rtx src
, reg
, new_rtx
, *loc
;
1188 enum machine_mode mode
;
1191 if (INSN_CODE (use_insn
) < 0)
1192 asm_use
= asm_noperands (PATTERN (use_insn
));
1194 if (!use_set
&& asm_use
< 0)
1197 /* Do not propagate into PC, CC0, etc. */
1198 if (use_set
&& GET_MODE (SET_DEST (use_set
)) == VOIDmode
)
1201 /* If def and use are subreg, check if they match. */
1202 reg
= DF_REF_REG (use
);
1203 if (GET_CODE (reg
) == SUBREG
1204 && GET_CODE (SET_DEST (def_set
)) == SUBREG
1205 && (SUBREG_BYTE (SET_DEST (def_set
)) != SUBREG_BYTE (reg
)
1206 || GET_MODE (SET_DEST (def_set
)) != GET_MODE (reg
)))
1209 /* Check if the def had a subreg, but the use has the whole reg. */
1210 if (REG_P (reg
) && GET_CODE (SET_DEST (def_set
)) == SUBREG
)
1213 /* Check if the use has a subreg, but the def had the whole reg. Unlike the
1214 previous case, the optimization is possible and often useful indeed. */
1215 if (GET_CODE (reg
) == SUBREG
&& REG_P (SET_DEST (def_set
)))
1216 reg
= SUBREG_REG (reg
);
1218 /* Check if the substitution is valid (last, because it's the most
1219 expensive check!). */
1220 src
= SET_SRC (def_set
);
1221 if (!CONSTANT_P (src
) && !all_uses_available_at (def_insn
, use_insn
))
1224 /* Check if the def is loading something from the constant pool; in this
1225 case we would undo optimization such as compress_float_constant.
1226 Still, we can set a REG_EQUAL note. */
1227 if (MEM_P (src
) && MEM_READONLY_P (src
))
1229 rtx x
= avoid_constant_pool_reference (src
);
1230 if (x
!= src
&& use_set
)
1232 rtx note
= find_reg_note (use_insn
, REG_EQUAL
, NULL_RTX
);
1233 rtx old_rtx
= note
? XEXP (note
, 0) : SET_SRC (use_set
);
1234 rtx new_rtx
= simplify_replace_rtx (old_rtx
, src
, x
);
1235 if (old_rtx
!= new_rtx
)
1236 set_unique_reg_note (use_insn
, REG_EQUAL
, copy_rtx (new_rtx
));
1242 return forward_propagate_asm (use
, def_insn
, def_set
, reg
);
1244 /* Else try simplifying. */
1246 if (DF_REF_TYPE (use
) == DF_REF_REG_MEM_STORE
)
1248 loc
= &SET_DEST (use_set
);
1249 set_reg_equal
= false;
1253 rtx note
= find_reg_note (use_insn
, REG_EQUAL
, NULL_RTX
);
1254 if (DF_REF_FLAGS (use
) & DF_REF_IN_NOTE
)
1255 loc
= &XEXP (note
, 0);
1257 loc
= &SET_SRC (use_set
);
1259 /* Do not replace an existing REG_EQUAL note if the insn is not
1260 recognized. Either we're already replacing in the note, or
1261 we'll separately try plugging the definition in the note and
1263 set_reg_equal
= (note
== NULL_RTX
);
1266 if (GET_MODE (*loc
) == VOIDmode
)
1267 mode
= GET_MODE (SET_DEST (use_set
));
1269 mode
= GET_MODE (*loc
);
1271 new_rtx
= propagate_rtx (*loc
, mode
, reg
, src
,
1272 optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn
)));
1277 return try_fwprop_subst (use
, loc
, new_rtx
, def_insn
, set_reg_equal
);
1281 /* Given a use USE of an insn, if it has a single reaching
1282 definition, try to forward propagate it into that insn. */
1285 forward_propagate_into (df_ref use
)
1288 rtx def_insn
, def_set
, use_insn
;
1291 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
1293 if (DF_REF_IS_ARTIFICIAL (use
))
1296 /* Only consider uses that have a single definition. */
1297 def
= get_def_for_use (use
);
1300 if (DF_REF_FLAGS (def
) & DF_REF_READ_WRITE
)
1302 if (DF_REF_IS_ARTIFICIAL (def
))
1305 /* Do not propagate loop invariant definitions inside the loop. */
1306 if (DF_REF_BB (def
)->loop_father
!= DF_REF_BB (use
)->loop_father
)
1309 /* Check if the use is still present in the insn! */
1310 use_insn
= DF_REF_INSN (use
);
1311 if (DF_REF_FLAGS (use
) & DF_REF_IN_NOTE
)
1312 parent
= find_reg_note (use_insn
, REG_EQUAL
, NULL_RTX
);
1314 parent
= PATTERN (use_insn
);
1316 if (!reg_mentioned_p (DF_REF_REG (use
), parent
))
1319 def_insn
= DF_REF_INSN (def
);
1320 if (multiple_sets (def_insn
))
1322 def_set
= single_set (def_insn
);
1326 /* Only try one kind of propagation. If two are possible, we'll
1327 do it on the following iterations. */
1328 if (!forward_propagate_and_simplify (use
, def_insn
, def_set
))
1329 forward_propagate_subreg (use
, def_insn
, def_set
);
1337 calculate_dominance_info (CDI_DOMINATORS
);
1339 /* We do not always want to propagate into loops, so we have to find
1340 loops and be careful about them. But we have to call flow_loops_find
1341 before df_analyze, because flow_loops_find may introduce new jump
1342 insns (sadly) if we are not working in cfglayout mode. */
1343 loop_optimizer_init (0);
1345 build_single_def_use_links ();
1346 df_set_flags (DF_DEFER_INSN_RESCAN
);
1352 loop_optimizer_finalize ();
1354 VEC_free (df_ref
, heap
, use_def_ref
);
1355 free_dominance_info (CDI_DOMINATORS
);
1357 delete_trivially_dead_insns (get_insns (), max_reg_num ());
1361 "\nNumber of successful forward propagations: %d\n\n",
1363 df_remove_problem (df_chain
);
1368 /* Main entry point. */
1373 return optimize
> 0 && flag_forward_propagate
;
1383 /* Go through all the uses. update_df will create new ones at the
1384 end, and we'll go through them as well.
1386 Do not forward propagate addresses into loops until after unrolling.
1387 CSE did so because it was able to fix its own mess, but we are not. */
1389 for (i
= 0; i
< DF_USES_TABLE_SIZE (); i
++)
1391 df_ref use
= DF_USES_GET (i
);
1393 if (DF_REF_TYPE (use
) == DF_REF_REG_USE
1394 || DF_REF_BB (use
)->loop_father
== NULL
1395 /* The outer most loop is not really a loop. */
1396 || loop_outer (DF_REF_BB (use
)->loop_father
) == NULL
)
1397 forward_propagate_into (use
);
1404 struct rtl_opt_pass pass_rtl_fwprop
=
1408 "fwprop1", /* name */
1409 gate_fwprop
, /* gate */
1410 fwprop
, /* execute */
1413 0, /* static_pass_number */
1414 TV_FWPROP
, /* tv_id */
1415 0, /* properties_required */
1416 0, /* properties_provided */
1417 0, /* properties_destroyed */
1418 0, /* todo_flags_start */
1419 TODO_df_finish
| TODO_verify_rtl_sharing
|
1420 TODO_dump_func
/* todo_flags_finish */
1430 /* Go through all the uses. update_df will create new ones at the
1431 end, and we'll go through them as well. */
1432 for (i
= 0; i
< DF_USES_TABLE_SIZE (); i
++)
1434 df_ref use
= DF_USES_GET (i
);
1436 if (DF_REF_TYPE (use
) != DF_REF_REG_USE
1437 && DF_REF_BB (use
)->loop_father
!= NULL
1438 /* The outer most loop is not really a loop. */
1439 && loop_outer (DF_REF_BB (use
)->loop_father
) != NULL
)
1440 forward_propagate_into (use
);
1448 struct rtl_opt_pass pass_rtl_fwprop_addr
=
1452 "fwprop2", /* name */
1453 gate_fwprop
, /* gate */
1454 fwprop_addr
, /* execute */
1457 0, /* static_pass_number */
1458 TV_FWPROP
, /* tv_id */
1459 0, /* properties_required */
1460 0, /* properties_provided */
1461 0, /* properties_destroyed */
1462 0, /* todo_flags_start */
1463 TODO_df_finish
| TODO_verify_rtl_sharing
|
1464 TODO_dump_func
/* todo_flags_finish */