Daily bump.
[official-gcc.git] / gcc / fwprop.c
blob17cc62aa2e4e2cfcfd1dc0135ef20722301b12dd
1 /* RTL-based forward propagation pass for GNU compiler.
2 Copyright (C) 2005-2013 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
10 version.
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
15 for more details.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "diagnostic-core.h"
27 #include "sparseset.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "insn-config.h"
31 #include "recog.h"
32 #include "flags.h"
33 #include "obstack.h"
34 #include "basic-block.h"
35 #include "df.h"
36 #include "target.h"
37 #include "cfgloop.h"
38 #include "tree-pass.h"
39 #include "domwalk.h"
40 #include "emit-rtl.h"
43 /* This pass does simple forward propagation and simplification when an
44 operand of an insn can only come from a single def. This pass uses
45 df.c, so it is global. However, we only do limited analysis of
46 available expressions.
48 1) The pass tries to propagate the source of the def into the use,
49 and checks if the result is independent of the substituted value.
50 For example, the high word of a (zero_extend:DI (reg:SI M)) is always
51 zero, independent of the source register.
53 In particular, we propagate constants into the use site. Sometimes
54 RTL expansion did not put the constant in the same insn on purpose,
55 to satisfy a predicate, and the result will fail to be recognized;
56 but this happens rarely and in this case we can still create a
57 REG_EQUAL note. For multi-word operations, this
59 (set (subreg:SI (reg:DI 120) 0) (const_int 0))
60 (set (subreg:SI (reg:DI 120) 4) (const_int -1))
61 (set (subreg:SI (reg:DI 122) 0)
62 (ior:SI (subreg:SI (reg:DI 119) 0) (subreg:SI (reg:DI 120) 0)))
63 (set (subreg:SI (reg:DI 122) 4)
64 (ior:SI (subreg:SI (reg:DI 119) 4) (subreg:SI (reg:DI 120) 4)))
66 can be simplified to the much simpler
68 (set (subreg:SI (reg:DI 122) 0) (subreg:SI (reg:DI 119)))
69 (set (subreg:SI (reg:DI 122) 4) (const_int -1))
71 This particular propagation is also effective at putting together
72 complex addressing modes. We are more aggressive inside MEMs, in
73 that all definitions are propagated if the use is in a MEM; if the
74 result is a valid memory address we check address_cost to decide
75 whether the substitution is worthwhile.
77 2) The pass propagates register copies. This is not as effective as
78 the copy propagation done by CSE's canon_reg, which works by walking
79 the instruction chain, it can help the other transformations.
81 We should consider removing this optimization, and instead reorder the
82 RTL passes, because GCSE does this transformation too. With some luck,
83 the CSE pass at the end of rest_of_handle_gcse could also go away.
85 3) The pass looks for paradoxical subregs that are actually unnecessary.
86 Things like this:
88 (set (reg:QI 120) (subreg:QI (reg:SI 118) 0))
89 (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
90 (set (reg:SI 122) (plus:SI (subreg:SI (reg:QI 120) 0)
91 (subreg:SI (reg:QI 121) 0)))
93 are very common on machines that can only do word-sized operations.
94 For each use of a paradoxical subreg (subreg:WIDER (reg:NARROW N) 0),
95 if it has a single def and it is (subreg:NARROW (reg:WIDE M) 0),
96 we can replace the paradoxical subreg with simply (reg:WIDE M). The
97 above will simplify this to
99 (set (reg:QI 120) (subreg:QI (reg:SI 118) 0))
100 (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
101 (set (reg:SI 122) (plus:SI (reg:SI 118) (reg:SI 119)))
103 where the first two insns are now dead.
105 We used to use reaching definitions to find which uses have a
106 single reaching definition (sounds obvious...), but this is too
107 complex a problem in nasty testcases like PR33928. Now we use the
108 multiple definitions problem in df-problems.c. The similarity
109 between that problem and SSA form creation is taken further, in
110 that fwprop does a dominator walk to create its chains; however,
111 instead of creating a PHI function where multiple definitions meet
112 I just punt and record only singleton use-def chains, which is
113 all that is needed by fwprop. */
116 static int num_changes;
118 static vec<df_ref> use_def_ref;
119 static vec<df_ref> reg_defs;
120 static vec<df_ref> reg_defs_stack;
122 /* The MD bitmaps are trimmed to include only live registers to cut
123 memory usage on testcases like insn-recog.c. Track live registers
124 in the basic block and do not perform forward propagation if the
125 destination is a dead pseudo occurring in a note. */
126 static bitmap local_md;
127 static bitmap local_lr;
129 /* Return the only def in USE's use-def chain, or NULL if there is
130 more than one def in the chain. */
132 static inline df_ref
133 get_def_for_use (df_ref use)
135 return use_def_ref[DF_REF_ID (use)];
139 /* Update the reg_defs vector with non-partial definitions in DEF_REC.
140 TOP_FLAG says which artificials uses should be used, when DEF_REC
141 is an artificial def vector. LOCAL_MD is modified as after a
142 df_md_simulate_* function; we do more or less the same processing
143 done there, so we do not use those functions. */
145 #define DF_MD_GEN_FLAGS \
146 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
148 static void
149 process_defs (df_ref *def_rec, int top_flag)
151 df_ref def;
152 while ((def = *def_rec++) != NULL)
154 df_ref curr_def = reg_defs[DF_REF_REGNO (def)];
155 unsigned int dregno;
157 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag)
158 continue;
160 dregno = DF_REF_REGNO (def);
161 if (curr_def)
162 reg_defs_stack.safe_push (curr_def);
163 else
165 /* Do not store anything if "transitioning" from NULL to NULL. But
166 otherwise, push a special entry on the stack to tell the
167 leave_block callback that the entry in reg_defs was NULL. */
168 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
170 else
171 reg_defs_stack.safe_push (def);
174 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
176 bitmap_set_bit (local_md, dregno);
177 reg_defs[dregno] = NULL;
179 else
181 bitmap_clear_bit (local_md, dregno);
182 reg_defs[dregno] = def;
188 /* Fill the use_def_ref vector with values for the uses in USE_REC,
189 taking reaching definitions info from LOCAL_MD and REG_DEFS.
190 TOP_FLAG says which artificials uses should be used, when USE_REC
191 is an artificial use vector. */
193 static void
194 process_uses (df_ref *use_rec, int top_flag)
196 df_ref use;
197 while ((use = *use_rec++) != NULL)
198 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag)
200 unsigned int uregno = DF_REF_REGNO (use);
201 if (reg_defs[uregno]
202 && !bitmap_bit_p (local_md, uregno)
203 && bitmap_bit_p (local_lr, uregno))
204 use_def_ref[DF_REF_ID (use)] = reg_defs[uregno];
209 static void
210 single_def_use_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
211 basic_block bb)
213 int bb_index = bb->index;
214 struct df_md_bb_info *md_bb_info = df_md_get_bb_info (bb_index);
215 struct df_lr_bb_info *lr_bb_info = df_lr_get_bb_info (bb_index);
216 rtx insn;
218 bitmap_copy (local_md, &md_bb_info->in);
219 bitmap_copy (local_lr, &lr_bb_info->in);
221 /* Push a marker for the leave_block callback. */
222 reg_defs_stack.safe_push (NULL);
224 process_uses (df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
225 process_defs (df_get_artificial_defs (bb_index), DF_REF_AT_TOP);
227 /* We don't call df_simulate_initialize_forwards, as it may overestimate
228 the live registers if there are unused artificial defs. We prefer
229 liveness to be underestimated. */
231 FOR_BB_INSNS (bb, insn)
232 if (INSN_P (insn))
234 unsigned int uid = INSN_UID (insn);
235 process_uses (DF_INSN_UID_USES (uid), 0);
236 process_uses (DF_INSN_UID_EQ_USES (uid), 0);
237 process_defs (DF_INSN_UID_DEFS (uid), 0);
238 df_simulate_one_insn_forwards (bb, insn, local_lr);
241 process_uses (df_get_artificial_uses (bb_index), 0);
242 process_defs (df_get_artificial_defs (bb_index), 0);
245 /* Pop the definitions created in this basic block when leaving its
246 dominated parts. */
248 static void
249 single_def_use_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
250 basic_block bb ATTRIBUTE_UNUSED)
252 df_ref saved_def;
253 while ((saved_def = reg_defs_stack.pop ()) != NULL)
255 unsigned int dregno = DF_REF_REGNO (saved_def);
257 /* See also process_defs. */
258 if (saved_def == reg_defs[dregno])
259 reg_defs[dregno] = NULL;
260 else
261 reg_defs[dregno] = saved_def;
266 /* Build a vector holding the reaching definitions of uses reached by a
267 single dominating definition. */
269 static void
270 build_single_def_use_links (void)
272 struct dom_walk_data walk_data;
274 /* We use the multiple definitions problem to compute our restricted
275 use-def chains. */
276 df_set_flags (DF_EQ_NOTES);
277 df_md_add_problem ();
278 df_note_add_problem ();
279 df_analyze ();
280 df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
282 use_def_ref.create (DF_USES_TABLE_SIZE ());
283 use_def_ref.safe_grow_cleared (DF_USES_TABLE_SIZE ());
285 reg_defs.create (max_reg_num ());
286 reg_defs.safe_grow_cleared (max_reg_num ());
288 reg_defs_stack.create (n_basic_blocks * 10);
289 local_md = BITMAP_ALLOC (NULL);
290 local_lr = BITMAP_ALLOC (NULL);
292 /* Walk the dominator tree looking for single reaching definitions
293 dominating the uses. This is similar to how SSA form is built. */
294 walk_data.dom_direction = CDI_DOMINATORS;
295 walk_data.initialize_block_local_data = NULL;
296 walk_data.before_dom_children = single_def_use_enter_block;
297 walk_data.after_dom_children = single_def_use_leave_block;
299 init_walk_dominator_tree (&walk_data);
300 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
301 fini_walk_dominator_tree (&walk_data);
303 BITMAP_FREE (local_lr);
304 BITMAP_FREE (local_md);
305 reg_defs.release ();
306 reg_defs_stack.release ();
310 /* Do not try to replace constant addresses or addresses of local and
311 argument slots. These MEM expressions are made only once and inserted
312 in many instructions, as well as being used to control symbol table
313 output. It is not safe to clobber them.
315 There are some uncommon cases where the address is already in a register
316 for some reason, but we cannot take advantage of that because we have
317 no easy way to unshare the MEM. In addition, looking up all stack
318 addresses is costly. */
320 static bool
321 can_simplify_addr (rtx addr)
323 rtx reg;
325 if (CONSTANT_ADDRESS_P (addr))
326 return false;
328 if (GET_CODE (addr) == PLUS)
329 reg = XEXP (addr, 0);
330 else
331 reg = addr;
333 return (!REG_P (reg)
334 || (REGNO (reg) != FRAME_POINTER_REGNUM
335 && REGNO (reg) != HARD_FRAME_POINTER_REGNUM
336 && REGNO (reg) != ARG_POINTER_REGNUM));
339 /* Returns a canonical version of X for the address, from the point of view,
340 that all multiplications are represented as MULT instead of the multiply
341 by a power of 2 being represented as ASHIFT.
343 Every ASHIFT we find has been made by simplify_gen_binary and was not
344 there before, so it is not shared. So we can do this in place. */
346 static void
347 canonicalize_address (rtx x)
349 for (;;)
350 switch (GET_CODE (x))
352 case ASHIFT:
353 if (CONST_INT_P (XEXP (x, 1))
354 && INTVAL (XEXP (x, 1)) < GET_MODE_BITSIZE (GET_MODE (x))
355 && INTVAL (XEXP (x, 1)) >= 0)
357 HOST_WIDE_INT shift = INTVAL (XEXP (x, 1));
358 PUT_CODE (x, MULT);
359 XEXP (x, 1) = gen_int_mode ((HOST_WIDE_INT) 1 << shift,
360 GET_MODE (x));
363 x = XEXP (x, 0);
364 break;
366 case PLUS:
367 if (GET_CODE (XEXP (x, 0)) == PLUS
368 || GET_CODE (XEXP (x, 0)) == ASHIFT
369 || GET_CODE (XEXP (x, 0)) == CONST)
370 canonicalize_address (XEXP (x, 0));
372 x = XEXP (x, 1);
373 break;
375 case CONST:
376 x = XEXP (x, 0);
377 break;
379 default:
380 return;
384 /* OLD is a memory address. Return whether it is good to use NEW instead,
385 for a memory access in the given MODE. */
387 static bool
388 should_replace_address (rtx old_rtx, rtx new_rtx, enum machine_mode mode,
389 addr_space_t as, bool speed)
391 int gain;
393 if (rtx_equal_p (old_rtx, new_rtx)
394 || !memory_address_addr_space_p (mode, new_rtx, as))
395 return false;
397 /* Copy propagation is always ok. */
398 if (REG_P (old_rtx) && REG_P (new_rtx))
399 return true;
401 /* Prefer the new address if it is less expensive. */
402 gain = (address_cost (old_rtx, mode, as, speed)
403 - address_cost (new_rtx, mode, as, speed));
405 /* If the addresses have equivalent cost, prefer the new address
406 if it has the highest `set_src_cost'. That has the potential of
407 eliminating the most insns without additional costs, and it
408 is the same that cse.c used to do. */
409 if (gain == 0)
410 gain = set_src_cost (new_rtx, speed) - set_src_cost (old_rtx, speed);
412 return (gain > 0);
416 /* Flags for the last parameter of propagate_rtx_1. */
418 enum {
419 /* If PR_CAN_APPEAR is true, propagate_rtx_1 always returns true;
420 if it is false, propagate_rtx_1 returns false if, for at least
421 one occurrence OLD, it failed to collapse the result to a constant.
422 For example, (mult:M (reg:M A) (minus:M (reg:M B) (reg:M A))) may
423 collapse to zero if replacing (reg:M B) with (reg:M A).
425 PR_CAN_APPEAR is disregarded inside MEMs: in that case,
426 propagate_rtx_1 just tries to make cheaper and valid memory
427 addresses. */
428 PR_CAN_APPEAR = 1,
430 /* If PR_HANDLE_MEM is not set, propagate_rtx_1 won't attempt any replacement
431 outside memory addresses. This is needed because propagate_rtx_1 does
432 not do any analysis on memory; thus it is very conservative and in general
433 it will fail if non-read-only MEMs are found in the source expression.
435 PR_HANDLE_MEM is set when the source of the propagation was not
436 another MEM. Then, it is safe not to treat non-read-only MEMs as
437 ``opaque'' objects. */
438 PR_HANDLE_MEM = 2,
440 /* Set when costs should be optimized for speed. */
441 PR_OPTIMIZE_FOR_SPEED = 4
445 /* Replace all occurrences of OLD in *PX with NEW and try to simplify the
446 resulting expression. Replace *PX with a new RTL expression if an
447 occurrence of OLD was found.
449 This is only a wrapper around simplify-rtx.c: do not add any pattern
450 matching code here. (The sole exception is the handling of LO_SUM, but
451 that is because there is no simplify_gen_* function for LO_SUM). */
453 static bool
454 propagate_rtx_1 (rtx *px, rtx old_rtx, rtx new_rtx, int flags)
456 rtx x = *px, tem = NULL_RTX, op0, op1, op2;
457 enum rtx_code code = GET_CODE (x);
458 enum machine_mode mode = GET_MODE (x);
459 enum machine_mode op_mode;
460 bool can_appear = (flags & PR_CAN_APPEAR) != 0;
461 bool valid_ops = true;
463 if (!(flags & PR_HANDLE_MEM) && MEM_P (x) && !MEM_READONLY_P (x))
465 /* If unsafe, change MEMs to CLOBBERs or SCRATCHes (to preserve whether
466 they have side effects or not). */
467 *px = (side_effects_p (x)
468 ? gen_rtx_CLOBBER (GET_MODE (x), const0_rtx)
469 : gen_rtx_SCRATCH (GET_MODE (x)));
470 return false;
473 /* If X is OLD_RTX, return NEW_RTX. But not if replacing only within an
474 address, and we are *not* inside one. */
475 if (x == old_rtx)
477 *px = new_rtx;
478 return can_appear;
481 /* If this is an expression, try recursive substitution. */
482 switch (GET_RTX_CLASS (code))
484 case RTX_UNARY:
485 op0 = XEXP (x, 0);
486 op_mode = GET_MODE (op0);
487 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
488 if (op0 == XEXP (x, 0))
489 return true;
490 tem = simplify_gen_unary (code, mode, op0, op_mode);
491 break;
493 case RTX_BIN_ARITH:
494 case RTX_COMM_ARITH:
495 op0 = XEXP (x, 0);
496 op1 = XEXP (x, 1);
497 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
498 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
499 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
500 return true;
501 tem = simplify_gen_binary (code, mode, op0, op1);
502 break;
504 case RTX_COMPARE:
505 case RTX_COMM_COMPARE:
506 op0 = XEXP (x, 0);
507 op1 = XEXP (x, 1);
508 op_mode = GET_MODE (op0) != VOIDmode ? GET_MODE (op0) : GET_MODE (op1);
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 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
512 return true;
513 tem = simplify_gen_relational (code, mode, op_mode, op0, op1);
514 break;
516 case RTX_TERNARY:
517 case RTX_BITFIELD_OPS:
518 op0 = XEXP (x, 0);
519 op1 = XEXP (x, 1);
520 op2 = XEXP (x, 2);
521 op_mode = GET_MODE (op0);
522 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
523 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
524 valid_ops &= propagate_rtx_1 (&op2, old_rtx, new_rtx, flags);
525 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1) && op2 == XEXP (x, 2))
526 return true;
527 if (op_mode == VOIDmode)
528 op_mode = GET_MODE (op0);
529 tem = simplify_gen_ternary (code, mode, op_mode, op0, op1, op2);
530 break;
532 case RTX_EXTRA:
533 /* The only case we try to handle is a SUBREG. */
534 if (code == SUBREG)
536 op0 = XEXP (x, 0);
537 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
538 if (op0 == XEXP (x, 0))
539 return true;
540 tem = simplify_gen_subreg (mode, op0, GET_MODE (SUBREG_REG (x)),
541 SUBREG_BYTE (x));
543 break;
545 case RTX_OBJ:
546 if (code == MEM && x != new_rtx)
548 rtx new_op0;
549 op0 = XEXP (x, 0);
551 /* There are some addresses that we cannot work on. */
552 if (!can_simplify_addr (op0))
553 return true;
555 op0 = new_op0 = targetm.delegitimize_address (op0);
556 valid_ops &= propagate_rtx_1 (&new_op0, old_rtx, new_rtx,
557 flags | PR_CAN_APPEAR);
559 /* Dismiss transformation that we do not want to carry on. */
560 if (!valid_ops
561 || new_op0 == op0
562 || !(GET_MODE (new_op0) == GET_MODE (op0)
563 || GET_MODE (new_op0) == VOIDmode))
564 return true;
566 canonicalize_address (new_op0);
568 /* Copy propagations are always ok. Otherwise check the costs. */
569 if (!(REG_P (old_rtx) && REG_P (new_rtx))
570 && !should_replace_address (op0, new_op0, GET_MODE (x),
571 MEM_ADDR_SPACE (x),
572 flags & PR_OPTIMIZE_FOR_SPEED))
573 return true;
575 tem = replace_equiv_address_nv (x, new_op0);
578 else if (code == LO_SUM)
580 op0 = XEXP (x, 0);
581 op1 = XEXP (x, 1);
583 /* The only simplification we do attempts to remove references to op0
584 or make it constant -- in both cases, op0's invalidity will not
585 make the result invalid. */
586 propagate_rtx_1 (&op0, old_rtx, new_rtx, flags | PR_CAN_APPEAR);
587 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
588 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
589 return true;
591 /* (lo_sum (high x) x) -> x */
592 if (GET_CODE (op0) == HIGH && rtx_equal_p (XEXP (op0, 0), op1))
593 tem = op1;
594 else
595 tem = gen_rtx_LO_SUM (mode, op0, op1);
597 /* OP1 is likely not a legitimate address, otherwise there would have
598 been no LO_SUM. We want it to disappear if it is invalid, return
599 false in that case. */
600 return memory_address_p (mode, tem);
603 else if (code == REG)
605 if (rtx_equal_p (x, old_rtx))
607 *px = new_rtx;
608 return can_appear;
611 break;
613 default:
614 break;
617 /* No change, no trouble. */
618 if (tem == NULL_RTX)
619 return true;
621 *px = tem;
623 /* The replacement we made so far is valid, if all of the recursive
624 replacements were valid, or we could simplify everything to
625 a constant. */
626 return valid_ops || can_appear || CONSTANT_P (tem);
630 /* for_each_rtx traversal function that returns 1 if BODY points to
631 a non-constant mem. */
633 static int
634 varying_mem_p (rtx *body, void *data ATTRIBUTE_UNUSED)
636 rtx x = *body;
637 return MEM_P (x) && !MEM_READONLY_P (x);
641 /* Replace all occurrences of OLD in X with NEW and try to simplify the
642 resulting expression (in mode MODE). Return a new expression if it is
643 a constant, otherwise X.
645 Simplifications where occurrences of NEW collapse to a constant are always
646 accepted. All simplifications are accepted if NEW is a pseudo too.
647 Otherwise, we accept simplifications that have a lower or equal cost. */
649 static rtx
650 propagate_rtx (rtx x, enum machine_mode mode, rtx old_rtx, rtx new_rtx,
651 bool speed)
653 rtx tem;
654 bool collapsed;
655 int flags;
657 if (REG_P (new_rtx) && REGNO (new_rtx) < FIRST_PSEUDO_REGISTER)
658 return NULL_RTX;
660 flags = 0;
661 if (REG_P (new_rtx)
662 || CONSTANT_P (new_rtx)
663 || (GET_CODE (new_rtx) == SUBREG
664 && REG_P (SUBREG_REG (new_rtx))
665 && (GET_MODE_SIZE (mode)
666 <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (new_rtx))))))
667 flags |= PR_CAN_APPEAR;
668 if (!for_each_rtx (&new_rtx, varying_mem_p, NULL))
669 flags |= PR_HANDLE_MEM;
671 if (speed)
672 flags |= PR_OPTIMIZE_FOR_SPEED;
674 tem = x;
675 collapsed = propagate_rtx_1 (&tem, old_rtx, copy_rtx (new_rtx), flags);
676 if (tem == x || !collapsed)
677 return NULL_RTX;
679 /* gen_lowpart_common will not be able to process VOIDmode entities other
680 than CONST_INTs. */
681 if (GET_MODE (tem) == VOIDmode && !CONST_INT_P (tem))
682 return NULL_RTX;
684 if (GET_MODE (tem) == VOIDmode)
685 tem = rtl_hooks.gen_lowpart_no_emit (mode, tem);
686 else
687 gcc_assert (GET_MODE (tem) == mode);
689 return tem;
695 /* Return true if the register from reference REF is killed
696 between FROM to (but not including) TO. */
698 static bool
699 local_ref_killed_between_p (df_ref ref, rtx from, rtx to)
701 rtx insn;
703 for (insn = from; insn != to; insn = NEXT_INSN (insn))
705 df_ref *def_rec;
706 if (!INSN_P (insn))
707 continue;
709 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
711 df_ref def = *def_rec;
712 if (DF_REF_REGNO (ref) == DF_REF_REGNO (def))
713 return true;
716 return false;
720 /* Check if the given DEF is available in INSN. This would require full
721 computation of available expressions; we check only restricted conditions:
722 - if DEF is the sole definition of its register, go ahead;
723 - in the same basic block, we check for no definitions killing the
724 definition of DEF_INSN;
725 - if USE's basic block has DEF's basic block as the sole predecessor,
726 we check if the definition is killed after DEF_INSN or before
727 TARGET_INSN insn, in their respective basic blocks. */
728 static bool
729 use_killed_between (df_ref use, rtx def_insn, rtx target_insn)
731 basic_block def_bb = BLOCK_FOR_INSN (def_insn);
732 basic_block target_bb = BLOCK_FOR_INSN (target_insn);
733 int regno;
734 df_ref def;
736 /* We used to have a def reaching a use that is _before_ the def,
737 with the def not dominating the use even though the use and def
738 are in the same basic block, when a register may be used
739 uninitialized in a loop. This should not happen anymore since
740 we do not use reaching definitions, but still we test for such
741 cases and assume that DEF is not available. */
742 if (def_bb == target_bb
743 ? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn)
744 : !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb))
745 return true;
747 /* Check if the reg in USE has only one definition. We already
748 know that this definition reaches use, or we wouldn't be here.
749 However, this is invalid for hard registers because if they are
750 live at the beginning of the function it does not mean that we
751 have an uninitialized access. */
752 regno = DF_REF_REGNO (use);
753 def = DF_REG_DEF_CHAIN (regno);
754 if (def
755 && DF_REF_NEXT_REG (def) == NULL
756 && regno >= FIRST_PSEUDO_REGISTER)
757 return false;
759 /* Check locally if we are in the same basic block. */
760 if (def_bb == target_bb)
761 return local_ref_killed_between_p (use, def_insn, target_insn);
763 /* Finally, if DEF_BB is the sole predecessor of TARGET_BB. */
764 if (single_pred_p (target_bb)
765 && single_pred (target_bb) == def_bb)
767 df_ref x;
769 /* See if USE is killed between DEF_INSN and the last insn in the
770 basic block containing DEF_INSN. */
771 x = df_bb_regno_last_def_find (def_bb, regno);
772 if (x && DF_INSN_LUID (DF_REF_INSN (x)) >= DF_INSN_LUID (def_insn))
773 return true;
775 /* See if USE is killed between TARGET_INSN and the first insn in the
776 basic block containing TARGET_INSN. */
777 x = df_bb_regno_first_def_find (target_bb, regno);
778 if (x && DF_INSN_LUID (DF_REF_INSN (x)) < DF_INSN_LUID (target_insn))
779 return true;
781 return false;
784 /* Otherwise assume the worst case. */
785 return true;
789 /* Check if all uses in DEF_INSN can be used in TARGET_INSN. This
790 would require full computation of available expressions;
791 we check only restricted conditions, see use_killed_between. */
792 static bool
793 all_uses_available_at (rtx def_insn, rtx target_insn)
795 df_ref *use_rec;
796 struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
797 rtx def_set = single_set (def_insn);
798 rtx next;
800 gcc_assert (def_set);
802 /* If target_insn comes right after def_insn, which is very common
803 for addresses, we can use a quicker test. Ignore debug insns
804 other than target insns for this. */
805 next = NEXT_INSN (def_insn);
806 while (next && next != target_insn && DEBUG_INSN_P (next))
807 next = NEXT_INSN (next);
808 if (next == target_insn && REG_P (SET_DEST (def_set)))
810 rtx def_reg = SET_DEST (def_set);
812 /* If the insn uses the reg that it defines, the substitution is
813 invalid. */
814 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
816 df_ref use = *use_rec;
817 if (rtx_equal_p (DF_REF_REG (use), def_reg))
818 return false;
820 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
822 df_ref use = *use_rec;
823 if (rtx_equal_p (DF_REF_REG (use), def_reg))
824 return false;
827 else
829 rtx def_reg = REG_P (SET_DEST (def_set)) ? SET_DEST (def_set) : NULL_RTX;
831 /* Look at all the uses of DEF_INSN, and see if they are not
832 killed between DEF_INSN and TARGET_INSN. */
833 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
835 df_ref use = *use_rec;
836 if (def_reg && rtx_equal_p (DF_REF_REG (use), def_reg))
837 return false;
838 if (use_killed_between (use, def_insn, target_insn))
839 return false;
841 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
843 df_ref use = *use_rec;
844 if (def_reg && rtx_equal_p (DF_REF_REG (use), def_reg))
845 return false;
846 if (use_killed_between (use, def_insn, target_insn))
847 return false;
851 return true;
855 static df_ref *active_defs;
856 #ifdef ENABLE_CHECKING
857 static sparseset active_defs_check;
858 #endif
860 /* Fill the ACTIVE_DEFS array with the use->def link for the registers
861 mentioned in USE_REC. Register the valid entries in ACTIVE_DEFS_CHECK
862 too, for checking purposes. */
864 static void
865 register_active_defs (df_ref *use_rec)
867 while (*use_rec)
869 df_ref use = *use_rec++;
870 df_ref def = get_def_for_use (use);
871 int regno = DF_REF_REGNO (use);
873 #ifdef ENABLE_CHECKING
874 sparseset_set_bit (active_defs_check, regno);
875 #endif
876 active_defs[regno] = def;
881 /* Build the use->def links that we use to update the dataflow info
882 for new uses. Note that building the links is very cheap and if
883 it were done earlier, they could be used to rule out invalid
884 propagations (in addition to what is done in all_uses_available_at).
885 I'm not doing this yet, though. */
887 static void
888 update_df_init (rtx def_insn, rtx insn)
890 #ifdef ENABLE_CHECKING
891 sparseset_clear (active_defs_check);
892 #endif
893 register_active_defs (DF_INSN_USES (def_insn));
894 register_active_defs (DF_INSN_USES (insn));
895 register_active_defs (DF_INSN_EQ_USES (insn));
899 /* Update the USE_DEF_REF array for the given use, using the active definitions
900 in the ACTIVE_DEFS array to match pseudos to their def. */
902 static inline void
903 update_uses (df_ref *use_rec)
905 while (*use_rec)
907 df_ref use = *use_rec++;
908 int regno = DF_REF_REGNO (use);
910 /* Set up the use-def chain. */
911 if (DF_REF_ID (use) >= (int) use_def_ref.length ())
912 use_def_ref.safe_grow_cleared (DF_REF_ID (use) + 1);
914 #ifdef ENABLE_CHECKING
915 gcc_assert (sparseset_bit_p (active_defs_check, regno));
916 #endif
917 use_def_ref[DF_REF_ID (use)] = active_defs[regno];
922 /* Update the USE_DEF_REF array for the uses in INSN. Only update note
923 uses if NOTES_ONLY is true. */
925 static void
926 update_df (rtx insn, rtx note)
928 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
930 if (note)
932 df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE);
933 df_notes_rescan (insn);
935 else
937 df_uses_create (&PATTERN (insn), insn, 0);
938 df_insn_rescan (insn);
939 update_uses (DF_INSN_INFO_USES (insn_info));
942 update_uses (DF_INSN_INFO_EQ_USES (insn_info));
946 /* Try substituting NEW into LOC, which originated from forward propagation
947 of USE's value from DEF_INSN. SET_REG_EQUAL says whether we are
948 substituting the whole SET_SRC, so we can set a REG_EQUAL note if the
949 new insn is not recognized. Return whether the substitution was
950 performed. */
952 static bool
953 try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx def_insn, bool set_reg_equal)
955 rtx insn = DF_REF_INSN (use);
956 rtx set = single_set (insn);
957 rtx note = NULL_RTX;
958 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
959 int old_cost = 0;
960 bool ok;
962 update_df_init (def_insn, insn);
964 /* forward_propagate_subreg may be operating on an instruction with
965 multiple sets. If so, assume the cost of the new instruction is
966 not greater than the old one. */
967 if (set)
968 old_cost = set_src_cost (SET_SRC (set), speed);
969 if (dump_file)
971 fprintf (dump_file, "\nIn insn %d, replacing\n ", INSN_UID (insn));
972 print_inline_rtx (dump_file, *loc, 2);
973 fprintf (dump_file, "\n with ");
974 print_inline_rtx (dump_file, new_rtx, 2);
975 fprintf (dump_file, "\n");
978 validate_unshare_change (insn, loc, new_rtx, true);
979 if (!verify_changes (0))
981 if (dump_file)
982 fprintf (dump_file, "Changes to insn %d not recognized\n",
983 INSN_UID (insn));
984 ok = false;
987 else if (DF_REF_TYPE (use) == DF_REF_REG_USE
988 && set
989 && set_src_cost (SET_SRC (set), speed) > old_cost)
991 if (dump_file)
992 fprintf (dump_file, "Changes to insn %d not profitable\n",
993 INSN_UID (insn));
994 ok = false;
997 else
999 if (dump_file)
1000 fprintf (dump_file, "Changed insn %d\n", INSN_UID (insn));
1001 ok = true;
1004 if (ok)
1006 confirm_change_group ();
1007 num_changes++;
1009 else
1011 cancel_changes (0);
1013 /* Can also record a simplified value in a REG_EQUAL note,
1014 making a new one if one does not already exist. */
1015 if (set_reg_equal)
1017 if (dump_file)
1018 fprintf (dump_file, " Setting REG_EQUAL note\n");
1020 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
1024 if ((ok || note) && !CONSTANT_P (new_rtx))
1025 update_df (insn, note);
1027 return ok;
1030 /* For the given single_set INSN, containing SRC known to be a
1031 ZERO_EXTEND or SIGN_EXTEND of a register, return true if INSN
1032 is redundant due to the register being set by a LOAD_EXTEND_OP
1033 load from memory. */
1035 static bool
1036 free_load_extend (rtx src, rtx insn)
1038 rtx reg;
1039 df_ref *use_vec;
1040 df_ref use = 0, def;
1042 reg = XEXP (src, 0);
1043 #ifdef LOAD_EXTEND_OP
1044 if (LOAD_EXTEND_OP (GET_MODE (reg)) != GET_CODE (src))
1045 #endif
1046 return false;
1048 for (use_vec = DF_INSN_USES (insn); *use_vec; use_vec++)
1050 use = *use_vec;
1052 if (!DF_REF_IS_ARTIFICIAL (use)
1053 && DF_REF_TYPE (use) == DF_REF_REG_USE
1054 && DF_REF_REG (use) == reg)
1055 break;
1057 if (!use)
1058 return false;
1060 def = get_def_for_use (use);
1061 if (!def)
1062 return false;
1064 if (DF_REF_IS_ARTIFICIAL (def))
1065 return false;
1067 if (NONJUMP_INSN_P (DF_REF_INSN (def)))
1069 rtx patt = PATTERN (DF_REF_INSN (def));
1071 if (GET_CODE (patt) == SET
1072 && GET_CODE (SET_SRC (patt)) == MEM
1073 && rtx_equal_p (SET_DEST (patt), reg))
1074 return true;
1076 return false;
1079 /* If USE is a subreg, see if it can be replaced by a pseudo. */
1081 static bool
1082 forward_propagate_subreg (df_ref use, rtx def_insn, rtx def_set)
1084 rtx use_reg = DF_REF_REG (use);
1085 rtx use_insn, src;
1087 /* Only consider subregs... */
1088 enum machine_mode use_mode = GET_MODE (use_reg);
1089 if (GET_CODE (use_reg) != SUBREG
1090 || !REG_P (SET_DEST (def_set)))
1091 return false;
1093 /* If this is a paradoxical SUBREG... */
1094 if (GET_MODE_SIZE (use_mode)
1095 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (use_reg))))
1097 /* If this is a paradoxical SUBREG, we have no idea what value the
1098 extra bits would have. However, if the operand is equivalent to
1099 a SUBREG whose operand is the same as our mode, and all the modes
1100 are within a word, we can just use the inner operand because
1101 these SUBREGs just say how to treat the register. */
1102 use_insn = DF_REF_INSN (use);
1103 src = SET_SRC (def_set);
1104 if (GET_CODE (src) == SUBREG
1105 && REG_P (SUBREG_REG (src))
1106 && REGNO (SUBREG_REG (src)) >= FIRST_PSEUDO_REGISTER
1107 && GET_MODE (SUBREG_REG (src)) == use_mode
1108 && subreg_lowpart_p (src)
1109 && all_uses_available_at (def_insn, use_insn))
1110 return try_fwprop_subst (use, DF_REF_LOC (use), SUBREG_REG (src),
1111 def_insn, false);
1114 /* If this is a SUBREG of a ZERO_EXTEND or SIGN_EXTEND, and the SUBREG
1115 is the low part of the reg being extended then just use the inner
1116 operand. Don't do this if the ZERO_EXTEND or SIGN_EXTEND insn will
1117 be removed due to it matching a LOAD_EXTEND_OP load from memory,
1118 or due to the operation being a no-op when applied to registers.
1119 For example, if we have:
1121 A: (set (reg:DI X) (sign_extend:DI (reg:SI Y)))
1122 B: (... (subreg:SI (reg:DI X)) ...)
1124 and mode_rep_extended says that Y is already sign-extended,
1125 the backend will typically allow A to be combined with the
1126 definition of Y or, failing that, allow A to be deleted after
1127 reload through register tying. Introducing more uses of Y
1128 prevents both optimisations. */
1129 else if (subreg_lowpart_p (use_reg))
1131 use_insn = DF_REF_INSN (use);
1132 src = SET_SRC (def_set);
1133 if ((GET_CODE (src) == ZERO_EXTEND
1134 || GET_CODE (src) == SIGN_EXTEND)
1135 && REG_P (XEXP (src, 0))
1136 && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER
1137 && GET_MODE (XEXP (src, 0)) == use_mode
1138 && !free_load_extend (src, def_insn)
1139 && (targetm.mode_rep_extended (use_mode, GET_MODE (src))
1140 != (int) GET_CODE (src))
1141 && all_uses_available_at (def_insn, use_insn))
1142 return try_fwprop_subst (use, DF_REF_LOC (use), XEXP (src, 0),
1143 def_insn, false);
1146 return false;
1149 /* Try to replace USE with SRC (defined in DEF_INSN) in __asm. */
1151 static bool
1152 forward_propagate_asm (df_ref use, rtx def_insn, rtx def_set, rtx reg)
1154 rtx use_insn = DF_REF_INSN (use), src, use_pat, asm_operands, new_rtx, *loc;
1155 int speed_p, i;
1156 df_ref *use_vec;
1158 gcc_assert ((DF_REF_FLAGS (use) & DF_REF_IN_NOTE) == 0);
1160 src = SET_SRC (def_set);
1161 use_pat = PATTERN (use_insn);
1163 /* In __asm don't replace if src might need more registers than
1164 reg, as that could increase register pressure on the __asm. */
1165 use_vec = DF_INSN_USES (def_insn);
1166 if (use_vec[0] && use_vec[1])
1167 return false;
1169 update_df_init (def_insn, use_insn);
1170 speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
1171 asm_operands = NULL_RTX;
1172 switch (GET_CODE (use_pat))
1174 case ASM_OPERANDS:
1175 asm_operands = use_pat;
1176 break;
1177 case SET:
1178 if (MEM_P (SET_DEST (use_pat)))
1180 loc = &SET_DEST (use_pat);
1181 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1182 if (new_rtx)
1183 validate_unshare_change (use_insn, loc, new_rtx, true);
1185 asm_operands = SET_SRC (use_pat);
1186 break;
1187 case PARALLEL:
1188 for (i = 0; i < XVECLEN (use_pat, 0); i++)
1189 if (GET_CODE (XVECEXP (use_pat, 0, i)) == SET)
1191 if (MEM_P (SET_DEST (XVECEXP (use_pat, 0, i))))
1193 loc = &SET_DEST (XVECEXP (use_pat, 0, i));
1194 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg,
1195 src, speed_p);
1196 if (new_rtx)
1197 validate_unshare_change (use_insn, loc, new_rtx, true);
1199 asm_operands = SET_SRC (XVECEXP (use_pat, 0, i));
1201 else if (GET_CODE (XVECEXP (use_pat, 0, i)) == ASM_OPERANDS)
1202 asm_operands = XVECEXP (use_pat, 0, i);
1203 break;
1204 default:
1205 gcc_unreachable ();
1208 gcc_assert (asm_operands && GET_CODE (asm_operands) == ASM_OPERANDS);
1209 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (asm_operands); i++)
1211 loc = &ASM_OPERANDS_INPUT (asm_operands, i);
1212 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1213 if (new_rtx)
1214 validate_unshare_change (use_insn, loc, new_rtx, true);
1217 if (num_changes_pending () == 0 || !apply_change_group ())
1218 return false;
1220 update_df (use_insn, NULL);
1221 num_changes++;
1222 return true;
1225 /* Try to replace USE with SRC (defined in DEF_INSN) and simplify the
1226 result. */
1228 static bool
1229 forward_propagate_and_simplify (df_ref use, rtx def_insn, rtx def_set)
1231 rtx use_insn = DF_REF_INSN (use);
1232 rtx use_set = single_set (use_insn);
1233 rtx src, reg, new_rtx, *loc;
1234 bool set_reg_equal;
1235 enum machine_mode mode;
1236 int asm_use = -1;
1238 if (INSN_CODE (use_insn) < 0)
1239 asm_use = asm_noperands (PATTERN (use_insn));
1241 if (!use_set && asm_use < 0 && !DEBUG_INSN_P (use_insn))
1242 return false;
1244 /* Do not propagate into PC, CC0, etc. */
1245 if (use_set && GET_MODE (SET_DEST (use_set)) == VOIDmode)
1246 return false;
1248 /* If def and use are subreg, check if they match. */
1249 reg = DF_REF_REG (use);
1250 if (GET_CODE (reg) == SUBREG && GET_CODE (SET_DEST (def_set)) == SUBREG)
1252 if (SUBREG_BYTE (SET_DEST (def_set)) != SUBREG_BYTE (reg))
1253 return false;
1255 /* Check if the def had a subreg, but the use has the whole reg. */
1256 else if (REG_P (reg) && GET_CODE (SET_DEST (def_set)) == SUBREG)
1257 return false;
1258 /* Check if the use has a subreg, but the def had the whole reg. Unlike the
1259 previous case, the optimization is possible and often useful indeed. */
1260 else if (GET_CODE (reg) == SUBREG && REG_P (SET_DEST (def_set)))
1261 reg = SUBREG_REG (reg);
1263 /* Make sure that we can treat REG as having the same mode as the
1264 source of DEF_SET. */
1265 if (GET_MODE (SET_DEST (def_set)) != GET_MODE (reg))
1266 return false;
1268 /* Check if the substitution is valid (last, because it's the most
1269 expensive check!). */
1270 src = SET_SRC (def_set);
1271 if (!CONSTANT_P (src) && !all_uses_available_at (def_insn, use_insn))
1272 return false;
1274 /* Check if the def is loading something from the constant pool; in this
1275 case we would undo optimization such as compress_float_constant.
1276 Still, we can set a REG_EQUAL note. */
1277 if (MEM_P (src) && MEM_READONLY_P (src))
1279 rtx x = avoid_constant_pool_reference (src);
1280 if (x != src && use_set)
1282 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1283 rtx old_rtx = note ? XEXP (note, 0) : SET_SRC (use_set);
1284 rtx new_rtx = simplify_replace_rtx (old_rtx, src, x);
1285 if (old_rtx != new_rtx)
1286 set_unique_reg_note (use_insn, REG_EQUAL, copy_rtx (new_rtx));
1288 return false;
1291 if (asm_use >= 0)
1292 return forward_propagate_asm (use, def_insn, def_set, reg);
1294 /* Else try simplifying. */
1296 if (DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE)
1298 loc = &SET_DEST (use_set);
1299 set_reg_equal = false;
1301 else if (!use_set)
1303 loc = &INSN_VAR_LOCATION_LOC (use_insn);
1304 set_reg_equal = false;
1306 else
1308 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1309 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1310 loc = &XEXP (note, 0);
1311 else
1312 loc = &SET_SRC (use_set);
1314 /* Do not replace an existing REG_EQUAL note if the insn is not
1315 recognized. Either we're already replacing in the note, or we'll
1316 separately try plugging the definition in the note and simplifying.
1317 And only install a REQ_EQUAL note when the destination is a REG
1318 that isn't mentioned in USE_SET, as the note would be invalid
1319 otherwise. We also don't want to install a note if we are merely
1320 propagating a pseudo since verifying that this pseudo isn't dead
1321 is a pain; moreover such a note won't help anything. */
1322 set_reg_equal = (note == NULL_RTX
1323 && REG_P (SET_DEST (use_set))
1324 && !REG_P (src)
1325 && !(GET_CODE (src) == SUBREG
1326 && REG_P (SUBREG_REG (src)))
1327 && !reg_mentioned_p (SET_DEST (use_set),
1328 SET_SRC (use_set)));
1331 if (GET_MODE (*loc) == VOIDmode)
1332 mode = GET_MODE (SET_DEST (use_set));
1333 else
1334 mode = GET_MODE (*loc);
1336 new_rtx = propagate_rtx (*loc, mode, reg, src,
1337 optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn)));
1339 if (!new_rtx)
1340 return false;
1342 return try_fwprop_subst (use, loc, new_rtx, def_insn, set_reg_equal);
1346 /* Given a use USE of an insn, if it has a single reaching
1347 definition, try to forward propagate it into that insn.
1348 Return true if cfg cleanup will be needed. */
1350 static bool
1351 forward_propagate_into (df_ref use)
1353 df_ref def;
1354 rtx def_insn, def_set, use_insn;
1355 rtx parent;
1357 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
1358 return false;
1359 if (DF_REF_IS_ARTIFICIAL (use))
1360 return false;
1362 /* Only consider uses that have a single definition. */
1363 def = get_def_for_use (use);
1364 if (!def)
1365 return false;
1366 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
1367 return false;
1368 if (DF_REF_IS_ARTIFICIAL (def))
1369 return false;
1371 /* Do not propagate loop invariant definitions inside the loop. */
1372 if (DF_REF_BB (def)->loop_father != DF_REF_BB (use)->loop_father)
1373 return false;
1375 /* Check if the use is still present in the insn! */
1376 use_insn = DF_REF_INSN (use);
1377 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1378 parent = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1379 else
1380 parent = PATTERN (use_insn);
1382 if (!reg_mentioned_p (DF_REF_REG (use), parent))
1383 return false;
1385 def_insn = DF_REF_INSN (def);
1386 if (multiple_sets (def_insn))
1387 return false;
1388 def_set = single_set (def_insn);
1389 if (!def_set)
1390 return false;
1392 /* Only try one kind of propagation. If two are possible, we'll
1393 do it on the following iterations. */
1394 if (forward_propagate_and_simplify (use, def_insn, def_set)
1395 || forward_propagate_subreg (use, def_insn, def_set))
1397 if (cfun->can_throw_non_call_exceptions
1398 && find_reg_note (use_insn, REG_EH_REGION, NULL_RTX)
1399 && purge_dead_edges (DF_REF_BB (use)))
1400 return true;
1402 return false;
1406 static void
1407 fwprop_init (void)
1409 num_changes = 0;
1410 calculate_dominance_info (CDI_DOMINATORS);
1412 /* We do not always want to propagate into loops, so we have to find
1413 loops and be careful about them. Avoid CFG modifications so that
1414 we don't have to update dominance information afterwards for
1415 build_single_def_use_links. */
1416 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
1418 build_single_def_use_links ();
1419 df_set_flags (DF_DEFER_INSN_RESCAN);
1421 active_defs = XNEWVEC (df_ref, max_reg_num ());
1422 #ifdef ENABLE_CHECKING
1423 active_defs_check = sparseset_alloc (max_reg_num ());
1424 #endif
1427 static void
1428 fwprop_done (void)
1430 loop_optimizer_finalize ();
1432 use_def_ref.release ();
1433 free (active_defs);
1434 #ifdef ENABLE_CHECKING
1435 sparseset_free (active_defs_check);
1436 #endif
1438 free_dominance_info (CDI_DOMINATORS);
1439 cleanup_cfg (0);
1440 delete_trivially_dead_insns (get_insns (), max_reg_num ());
1442 if (dump_file)
1443 fprintf (dump_file,
1444 "\nNumber of successful forward propagations: %d\n\n",
1445 num_changes);
1449 /* Main entry point. */
1451 static bool
1452 gate_fwprop (void)
1454 return optimize > 0 && flag_forward_propagate;
1457 static unsigned int
1458 fwprop (void)
1460 unsigned i;
1461 bool need_cleanup = false;
1463 fwprop_init ();
1465 /* Go through all the uses. df_uses_create will create new ones at the
1466 end, and we'll go through them as well.
1468 Do not forward propagate addresses into loops until after unrolling.
1469 CSE did so because it was able to fix its own mess, but we are not. */
1471 for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1473 df_ref use = DF_USES_GET (i);
1474 if (use)
1475 if (DF_REF_TYPE (use) == DF_REF_REG_USE
1476 || DF_REF_BB (use)->loop_father == NULL
1477 /* The outer most loop is not really a loop. */
1478 || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
1479 need_cleanup |= forward_propagate_into (use);
1482 fwprop_done ();
1483 if (need_cleanup)
1484 cleanup_cfg (0);
1485 return 0;
1488 struct rtl_opt_pass pass_rtl_fwprop =
1491 RTL_PASS,
1492 "fwprop1", /* name */
1493 OPTGROUP_NONE, /* optinfo_flags */
1494 gate_fwprop, /* gate */
1495 fwprop, /* execute */
1496 NULL, /* sub */
1497 NULL, /* next */
1498 0, /* static_pass_number */
1499 TV_FWPROP, /* tv_id */
1500 0, /* properties_required */
1501 0, /* properties_provided */
1502 0, /* properties_destroyed */
1503 0, /* todo_flags_start */
1504 TODO_df_finish
1505 | TODO_verify_flow
1506 | TODO_verify_rtl_sharing /* todo_flags_finish */
1510 static unsigned int
1511 fwprop_addr (void)
1513 unsigned i;
1514 bool need_cleanup = false;
1516 fwprop_init ();
1518 /* Go through all the uses. df_uses_create will create new ones at the
1519 end, and we'll go through them as well. */
1520 for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1522 df_ref use = DF_USES_GET (i);
1523 if (use)
1524 if (DF_REF_TYPE (use) != DF_REF_REG_USE
1525 && DF_REF_BB (use)->loop_father != NULL
1526 /* The outer most loop is not really a loop. */
1527 && loop_outer (DF_REF_BB (use)->loop_father) != NULL)
1528 need_cleanup |= forward_propagate_into (use);
1531 fwprop_done ();
1533 if (need_cleanup)
1534 cleanup_cfg (0);
1535 return 0;
1538 struct rtl_opt_pass pass_rtl_fwprop_addr =
1541 RTL_PASS,
1542 "fwprop2", /* name */
1543 OPTGROUP_NONE, /* optinfo_flags */
1544 gate_fwprop, /* gate */
1545 fwprop_addr, /* execute */
1546 NULL, /* sub */
1547 NULL, /* next */
1548 0, /* static_pass_number */
1549 TV_FWPROP, /* tv_id */
1550 0, /* properties_required */
1551 0, /* properties_provided */
1552 0, /* properties_destroyed */
1553 0, /* todo_flags_start */
1554 TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */