* es.po: Update.
[official-gcc.git] / gcc / fwprop.c
blob0fca0f1edbc24104c27bf20f8e641307d921f16d
1 /* RTL-based forward propagation pass for GNU compiler.
2 Copyright (C) 2005-2018 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 "backend.h"
25 #include "target.h"
26 #include "rtl.h"
27 #include "predict.h"
28 #include "df.h"
29 #include "memmodel.h"
30 #include "tm_p.h"
31 #include "insn-config.h"
32 #include "emit-rtl.h"
33 #include "recog.h"
35 #include "sparseset.h"
36 #include "cfgrtl.h"
37 #include "cfgcleanup.h"
38 #include "cfgloop.h"
39 #include "tree-pass.h"
40 #include "domwalk.h"
41 #include "rtl-iter.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.
87 Things like this:
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;
119 static vec<df_ref> use_def_ref;
120 static vec<df_ref> reg_defs;
121 static vec<df_ref> reg_defs_stack;
123 /* The maximum number of propagations that are still allowed. If we do
124 more propagations than originally we had uses, we must have ended up
125 in a propagation loop, as in PR79405. Until the algorithm fwprop
126 uses can obviously not get into such loops we need a workaround like
127 this. */
128 static int propagations_left;
130 /* The MD bitmaps are trimmed to include only live registers to cut
131 memory usage on testcases like insn-recog.c. Track live registers
132 in the basic block and do not perform forward propagation if the
133 destination is a dead pseudo occurring in a note. */
134 static bitmap local_md;
135 static bitmap local_lr;
137 /* Return the only def in USE's use-def chain, or NULL if there is
138 more than one def in the chain. */
140 static inline df_ref
141 get_def_for_use (df_ref use)
143 return use_def_ref[DF_REF_ID (use)];
147 /* Update the reg_defs vector with non-partial definitions in DEF_REC.
148 TOP_FLAG says which artificials uses should be used, when DEF_REC
149 is an artificial def vector. LOCAL_MD is modified as after a
150 df_md_simulate_* function; we do more or less the same processing
151 done there, so we do not use those functions. */
153 #define DF_MD_GEN_FLAGS \
154 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
156 static void
157 process_defs (df_ref def, int top_flag)
159 for (; def; def = DF_REF_NEXT_LOC (def))
161 df_ref curr_def = reg_defs[DF_REF_REGNO (def)];
162 unsigned int dregno;
164 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag)
165 continue;
167 dregno = DF_REF_REGNO (def);
168 if (curr_def)
169 reg_defs_stack.safe_push (curr_def);
170 else
172 /* Do not store anything if "transitioning" from NULL to NULL. But
173 otherwise, push a special entry on the stack to tell the
174 leave_block callback that the entry in reg_defs was NULL. */
175 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
177 else
178 reg_defs_stack.safe_push (def);
181 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
183 bitmap_set_bit (local_md, dregno);
184 reg_defs[dregno] = NULL;
186 else
188 bitmap_clear_bit (local_md, dregno);
189 reg_defs[dregno] = def;
195 /* Fill the use_def_ref vector with values for the uses in USE_REC,
196 taking reaching definitions info from LOCAL_MD and REG_DEFS.
197 TOP_FLAG says which artificials uses should be used, when USE_REC
198 is an artificial use vector. */
200 static void
201 process_uses (df_ref use, int top_flag)
203 for (; use; use = DF_REF_NEXT_LOC (use))
204 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag)
206 unsigned int uregno = DF_REF_REGNO (use);
207 if (reg_defs[uregno]
208 && !bitmap_bit_p (local_md, uregno)
209 && bitmap_bit_p (local_lr, uregno))
210 use_def_ref[DF_REF_ID (use)] = reg_defs[uregno];
214 class single_def_use_dom_walker : public dom_walker
216 public:
217 single_def_use_dom_walker (cdi_direction direction)
218 : dom_walker (direction) {}
219 virtual edge before_dom_children (basic_block);
220 virtual void after_dom_children (basic_block);
223 edge
224 single_def_use_dom_walker::before_dom_children (basic_block bb)
226 int bb_index = bb->index;
227 struct df_md_bb_info *md_bb_info = df_md_get_bb_info (bb_index);
228 struct df_lr_bb_info *lr_bb_info = df_lr_get_bb_info (bb_index);
229 rtx_insn *insn;
231 bitmap_copy (local_md, &md_bb_info->in);
232 bitmap_copy (local_lr, &lr_bb_info->in);
234 /* Push a marker for the leave_block callback. */
235 reg_defs_stack.safe_push (NULL);
237 process_uses (df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
238 process_defs (df_get_artificial_defs (bb_index), DF_REF_AT_TOP);
240 /* We don't call df_simulate_initialize_forwards, as it may overestimate
241 the live registers if there are unused artificial defs. We prefer
242 liveness to be underestimated. */
244 FOR_BB_INSNS (bb, insn)
245 if (INSN_P (insn))
247 unsigned int uid = INSN_UID (insn);
248 process_uses (DF_INSN_UID_USES (uid), 0);
249 process_uses (DF_INSN_UID_EQ_USES (uid), 0);
250 process_defs (DF_INSN_UID_DEFS (uid), 0);
251 df_simulate_one_insn_forwards (bb, insn, local_lr);
254 process_uses (df_get_artificial_uses (bb_index), 0);
255 process_defs (df_get_artificial_defs (bb_index), 0);
257 return NULL;
260 /* Pop the definitions created in this basic block when leaving its
261 dominated parts. */
263 void
264 single_def_use_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
266 df_ref saved_def;
267 while ((saved_def = reg_defs_stack.pop ()) != NULL)
269 unsigned int dregno = DF_REF_REGNO (saved_def);
271 /* See also process_defs. */
272 if (saved_def == reg_defs[dregno])
273 reg_defs[dregno] = NULL;
274 else
275 reg_defs[dregno] = saved_def;
280 /* Build a vector holding the reaching definitions of uses reached by a
281 single dominating definition. */
283 static void
284 build_single_def_use_links (void)
286 /* We use the multiple definitions problem to compute our restricted
287 use-def chains. */
288 df_set_flags (DF_EQ_NOTES);
289 df_md_add_problem ();
290 df_note_add_problem ();
291 df_analyze ();
292 df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
294 use_def_ref.create (DF_USES_TABLE_SIZE ());
295 use_def_ref.safe_grow_cleared (DF_USES_TABLE_SIZE ());
297 reg_defs.create (max_reg_num ());
298 reg_defs.safe_grow_cleared (max_reg_num ());
300 reg_defs_stack.create (n_basic_blocks_for_fn (cfun) * 10);
301 local_md = BITMAP_ALLOC (NULL);
302 local_lr = BITMAP_ALLOC (NULL);
304 /* Walk the dominator tree looking for single reaching definitions
305 dominating the uses. This is similar to how SSA form is built. */
306 single_def_use_dom_walker (CDI_DOMINATORS)
307 .walk (cfun->cfg->x_entry_block_ptr);
309 BITMAP_FREE (local_lr);
310 BITMAP_FREE (local_md);
311 reg_defs.release ();
312 reg_defs_stack.release ();
316 /* Do not try to replace constant addresses or addresses of local and
317 argument slots. These MEM expressions are made only once and inserted
318 in many instructions, as well as being used to control symbol table
319 output. It is not safe to clobber them.
321 There are some uncommon cases where the address is already in a register
322 for some reason, but we cannot take advantage of that because we have
323 no easy way to unshare the MEM. In addition, looking up all stack
324 addresses is costly. */
326 static bool
327 can_simplify_addr (rtx addr)
329 rtx reg;
331 if (CONSTANT_ADDRESS_P (addr))
332 return false;
334 if (GET_CODE (addr) == PLUS)
335 reg = XEXP (addr, 0);
336 else
337 reg = addr;
339 return (!REG_P (reg)
340 || (REGNO (reg) != FRAME_POINTER_REGNUM
341 && REGNO (reg) != HARD_FRAME_POINTER_REGNUM
342 && REGNO (reg) != ARG_POINTER_REGNUM));
345 /* Returns a canonical version of X for the address, from the point of view,
346 that all multiplications are represented as MULT instead of the multiply
347 by a power of 2 being represented as ASHIFT.
349 Every ASHIFT we find has been made by simplify_gen_binary and was not
350 there before, so it is not shared. So we can do this in place. */
352 static void
353 canonicalize_address (rtx x)
355 for (;;)
356 switch (GET_CODE (x))
358 case ASHIFT:
359 if (CONST_INT_P (XEXP (x, 1))
360 && INTVAL (XEXP (x, 1)) < GET_MODE_UNIT_BITSIZE (GET_MODE (x))
361 && INTVAL (XEXP (x, 1)) >= 0)
363 HOST_WIDE_INT shift = INTVAL (XEXP (x, 1));
364 PUT_CODE (x, MULT);
365 XEXP (x, 1) = gen_int_mode (HOST_WIDE_INT_1 << shift,
366 GET_MODE (x));
369 x = XEXP (x, 0);
370 break;
372 case PLUS:
373 if (GET_CODE (XEXP (x, 0)) == PLUS
374 || GET_CODE (XEXP (x, 0)) == ASHIFT
375 || GET_CODE (XEXP (x, 0)) == CONST)
376 canonicalize_address (XEXP (x, 0));
378 x = XEXP (x, 1);
379 break;
381 case CONST:
382 x = XEXP (x, 0);
383 break;
385 default:
386 return;
390 /* OLD is a memory address. Return whether it is good to use NEW instead,
391 for a memory access in the given MODE. */
393 static bool
394 should_replace_address (rtx old_rtx, rtx new_rtx, machine_mode mode,
395 addr_space_t as, bool speed)
397 int gain;
399 if (rtx_equal_p (old_rtx, new_rtx)
400 || !memory_address_addr_space_p (mode, new_rtx, as))
401 return false;
403 /* Copy propagation is always ok. */
404 if (REG_P (old_rtx) && REG_P (new_rtx))
405 return true;
407 /* Prefer the new address if it is less expensive. */
408 gain = (address_cost (old_rtx, mode, as, speed)
409 - address_cost (new_rtx, mode, as, speed));
411 /* If the addresses have equivalent cost, prefer the new address
412 if it has the highest `set_src_cost'. That has the potential of
413 eliminating the most insns without additional costs, and it
414 is the same that cse.c used to do. */
415 if (gain == 0)
416 gain = (set_src_cost (new_rtx, VOIDmode, speed)
417 - set_src_cost (old_rtx, VOIDmode, speed));
419 return (gain > 0);
423 /* Flags for the last parameter of propagate_rtx_1. */
425 enum {
426 /* If PR_CAN_APPEAR is true, propagate_rtx_1 always returns true;
427 if it is false, propagate_rtx_1 returns false if, for at least
428 one occurrence OLD, it failed to collapse the result to a constant.
429 For example, (mult:M (reg:M A) (minus:M (reg:M B) (reg:M A))) may
430 collapse to zero if replacing (reg:M B) with (reg:M A).
432 PR_CAN_APPEAR is disregarded inside MEMs: in that case,
433 propagate_rtx_1 just tries to make cheaper and valid memory
434 addresses. */
435 PR_CAN_APPEAR = 1,
437 /* If PR_HANDLE_MEM is not set, propagate_rtx_1 won't attempt any replacement
438 outside memory addresses. This is needed because propagate_rtx_1 does
439 not do any analysis on memory; thus it is very conservative and in general
440 it will fail if non-read-only MEMs are found in the source expression.
442 PR_HANDLE_MEM is set when the source of the propagation was not
443 another MEM. Then, it is safe not to treat non-read-only MEMs as
444 ``opaque'' objects. */
445 PR_HANDLE_MEM = 2,
447 /* Set when costs should be optimized for speed. */
448 PR_OPTIMIZE_FOR_SPEED = 4
452 /* Replace all occurrences of OLD in *PX with NEW and try to simplify the
453 resulting expression. Replace *PX with a new RTL expression if an
454 occurrence of OLD was found.
456 This is only a wrapper around simplify-rtx.c: do not add any pattern
457 matching code here. (The sole exception is the handling of LO_SUM, but
458 that is because there is no simplify_gen_* function for LO_SUM). */
460 static bool
461 propagate_rtx_1 (rtx *px, rtx old_rtx, rtx new_rtx, int flags)
463 rtx x = *px, tem = NULL_RTX, op0, op1, op2;
464 enum rtx_code code = GET_CODE (x);
465 machine_mode mode = GET_MODE (x);
466 machine_mode op_mode;
467 bool can_appear = (flags & PR_CAN_APPEAR) != 0;
468 bool valid_ops = true;
470 if (!(flags & PR_HANDLE_MEM) && MEM_P (x) && !MEM_READONLY_P (x))
472 /* If unsafe, change MEMs to CLOBBERs or SCRATCHes (to preserve whether
473 they have side effects or not). */
474 *px = (side_effects_p (x)
475 ? gen_rtx_CLOBBER (GET_MODE (x), const0_rtx)
476 : gen_rtx_SCRATCH (GET_MODE (x)));
477 return false;
480 /* If X is OLD_RTX, return NEW_RTX. But not if replacing only within an
481 address, and we are *not* inside one. */
482 if (x == old_rtx)
484 *px = new_rtx;
485 return can_appear;
488 /* If this is an expression, try recursive substitution. */
489 switch (GET_RTX_CLASS (code))
491 case RTX_UNARY:
492 op0 = XEXP (x, 0);
493 op_mode = GET_MODE (op0);
494 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
495 if (op0 == XEXP (x, 0))
496 return true;
497 tem = simplify_gen_unary (code, mode, op0, op_mode);
498 break;
500 case RTX_BIN_ARITH:
501 case RTX_COMM_ARITH:
502 op0 = XEXP (x, 0);
503 op1 = XEXP (x, 1);
504 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
505 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
506 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
507 return true;
508 tem = simplify_gen_binary (code, mode, op0, op1);
509 break;
511 case RTX_COMPARE:
512 case RTX_COMM_COMPARE:
513 op0 = XEXP (x, 0);
514 op1 = XEXP (x, 1);
515 op_mode = GET_MODE (op0) != VOIDmode ? GET_MODE (op0) : GET_MODE (op1);
516 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
517 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
518 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
519 return true;
520 tem = simplify_gen_relational (code, mode, op_mode, op0, op1);
521 break;
523 case RTX_TERNARY:
524 case RTX_BITFIELD_OPS:
525 op0 = XEXP (x, 0);
526 op1 = XEXP (x, 1);
527 op2 = XEXP (x, 2);
528 op_mode = GET_MODE (op0);
529 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
530 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
531 valid_ops &= propagate_rtx_1 (&op2, old_rtx, new_rtx, flags);
532 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1) && op2 == XEXP (x, 2))
533 return true;
534 if (op_mode == VOIDmode)
535 op_mode = GET_MODE (op0);
536 tem = simplify_gen_ternary (code, mode, op_mode, op0, op1, op2);
537 break;
539 case RTX_EXTRA:
540 /* The only case we try to handle is a SUBREG. */
541 if (code == SUBREG)
543 op0 = XEXP (x, 0);
544 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
545 if (op0 == XEXP (x, 0))
546 return true;
547 tem = simplify_gen_subreg (mode, op0, GET_MODE (SUBREG_REG (x)),
548 SUBREG_BYTE (x));
550 break;
552 case RTX_OBJ:
553 if (code == MEM && x != new_rtx)
555 rtx new_op0;
556 op0 = XEXP (x, 0);
558 /* There are some addresses that we cannot work on. */
559 if (!can_simplify_addr (op0))
560 return true;
562 op0 = new_op0 = targetm.delegitimize_address (op0);
563 valid_ops &= propagate_rtx_1 (&new_op0, old_rtx, new_rtx,
564 flags | PR_CAN_APPEAR);
566 /* Dismiss transformation that we do not want to carry on. */
567 if (!valid_ops
568 || new_op0 == op0
569 || !(GET_MODE (new_op0) == GET_MODE (op0)
570 || GET_MODE (new_op0) == VOIDmode))
571 return true;
573 canonicalize_address (new_op0);
575 /* Copy propagations are always ok. Otherwise check the costs. */
576 if (!(REG_P (old_rtx) && REG_P (new_rtx))
577 && !should_replace_address (op0, new_op0, GET_MODE (x),
578 MEM_ADDR_SPACE (x),
579 flags & PR_OPTIMIZE_FOR_SPEED))
580 return true;
582 tem = replace_equiv_address_nv (x, new_op0);
585 else if (code == LO_SUM)
587 op0 = XEXP (x, 0);
588 op1 = XEXP (x, 1);
590 /* The only simplification we do attempts to remove references to op0
591 or make it constant -- in both cases, op0's invalidity will not
592 make the result invalid. */
593 propagate_rtx_1 (&op0, old_rtx, new_rtx, flags | PR_CAN_APPEAR);
594 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
595 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
596 return true;
598 /* (lo_sum (high x) x) -> x */
599 if (GET_CODE (op0) == HIGH && rtx_equal_p (XEXP (op0, 0), op1))
600 tem = op1;
601 else
602 tem = gen_rtx_LO_SUM (mode, op0, op1);
604 /* OP1 is likely not a legitimate address, otherwise there would have
605 been no LO_SUM. We want it to disappear if it is invalid, return
606 false in that case. */
607 return memory_address_p (mode, tem);
610 else if (code == REG)
612 if (rtx_equal_p (x, old_rtx))
614 *px = new_rtx;
615 return can_appear;
618 break;
620 default:
621 break;
624 /* No change, no trouble. */
625 if (tem == NULL_RTX)
626 return true;
628 *px = tem;
630 /* Allow replacements that simplify operations on a vector or complex
631 value to a component. The most prominent case is
632 (subreg ([vec_]concat ...)). */
633 if (REG_P (tem) && !HARD_REGISTER_P (tem)
634 && (VECTOR_MODE_P (GET_MODE (new_rtx))
635 || COMPLEX_MODE_P (GET_MODE (new_rtx)))
636 && GET_MODE (tem) == GET_MODE_INNER (GET_MODE (new_rtx)))
637 return true;
639 /* The replacement we made so far is valid, if all of the recursive
640 replacements were valid, or we could simplify everything to
641 a constant. */
642 return valid_ops || can_appear || CONSTANT_P (tem);
646 /* Return true if X constains a non-constant mem. */
648 static bool
649 varying_mem_p (const_rtx x)
651 subrtx_iterator::array_type array;
652 FOR_EACH_SUBRTX (iter, array, x, NONCONST)
653 if (MEM_P (*iter) && !MEM_READONLY_P (*iter))
654 return true;
655 return false;
659 /* Replace all occurrences of OLD in X with NEW and try to simplify the
660 resulting expression (in mode MODE). Return a new expression if it is
661 a constant, otherwise X.
663 Simplifications where occurrences of NEW collapse to a constant are always
664 accepted. All simplifications are accepted if NEW is a pseudo too.
665 Otherwise, we accept simplifications that have a lower or equal cost. */
667 static rtx
668 propagate_rtx (rtx x, machine_mode mode, rtx old_rtx, rtx new_rtx,
669 bool speed)
671 rtx tem;
672 bool collapsed;
673 int flags;
675 if (REG_P (new_rtx) && REGNO (new_rtx) < FIRST_PSEUDO_REGISTER)
676 return NULL_RTX;
678 flags = 0;
679 if (REG_P (new_rtx)
680 || CONSTANT_P (new_rtx)
681 || (GET_CODE (new_rtx) == SUBREG
682 && REG_P (SUBREG_REG (new_rtx))
683 && !paradoxical_subreg_p (mode, GET_MODE (SUBREG_REG (new_rtx)))))
684 flags |= PR_CAN_APPEAR;
685 if (!varying_mem_p (new_rtx))
686 flags |= PR_HANDLE_MEM;
688 if (speed)
689 flags |= PR_OPTIMIZE_FOR_SPEED;
691 tem = x;
692 collapsed = propagate_rtx_1 (&tem, old_rtx, copy_rtx (new_rtx), flags);
693 if (tem == x || !collapsed)
694 return NULL_RTX;
696 /* gen_lowpart_common will not be able to process VOIDmode entities other
697 than CONST_INTs. */
698 if (GET_MODE (tem) == VOIDmode && !CONST_INT_P (tem))
699 return NULL_RTX;
701 if (GET_MODE (tem) == VOIDmode)
702 tem = rtl_hooks.gen_lowpart_no_emit (mode, tem);
703 else
704 gcc_assert (GET_MODE (tem) == mode);
706 return tem;
712 /* Return true if the register from reference REF is killed
713 between FROM to (but not including) TO. */
715 static bool
716 local_ref_killed_between_p (df_ref ref, rtx_insn *from, rtx_insn *to)
718 rtx_insn *insn;
720 for (insn = from; insn != to; insn = NEXT_INSN (insn))
722 df_ref def;
723 if (!INSN_P (insn))
724 continue;
726 FOR_EACH_INSN_DEF (def, insn)
727 if (DF_REF_REGNO (ref) == DF_REF_REGNO (def))
728 return true;
730 return false;
734 /* Check if the given DEF is available in INSN. This would require full
735 computation of available expressions; we check only restricted conditions:
736 - if DEF is the sole definition of its register, go ahead;
737 - in the same basic block, we check for no definitions killing the
738 definition of DEF_INSN;
739 - if USE's basic block has DEF's basic block as the sole predecessor,
740 we check if the definition is killed after DEF_INSN or before
741 TARGET_INSN insn, in their respective basic blocks. */
742 static bool
743 use_killed_between (df_ref use, rtx_insn *def_insn, rtx_insn *target_insn)
745 basic_block def_bb = BLOCK_FOR_INSN (def_insn);
746 basic_block target_bb = BLOCK_FOR_INSN (target_insn);
747 int regno;
748 df_ref def;
750 /* We used to have a def reaching a use that is _before_ the def,
751 with the def not dominating the use even though the use and def
752 are in the same basic block, when a register may be used
753 uninitialized in a loop. This should not happen anymore since
754 we do not use reaching definitions, but still we test for such
755 cases and assume that DEF is not available. */
756 if (def_bb == target_bb
757 ? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn)
758 : !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb))
759 return true;
761 /* Check if the reg in USE has only one definition. We already
762 know that this definition reaches use, or we wouldn't be here.
763 However, this is invalid for hard registers because if they are
764 live at the beginning of the function it does not mean that we
765 have an uninitialized access. */
766 regno = DF_REF_REGNO (use);
767 def = DF_REG_DEF_CHAIN (regno);
768 if (def
769 && DF_REF_NEXT_REG (def) == NULL
770 && regno >= FIRST_PSEUDO_REGISTER)
771 return false;
773 /* Check locally if we are in the same basic block. */
774 if (def_bb == target_bb)
775 return local_ref_killed_between_p (use, def_insn, target_insn);
777 /* Finally, if DEF_BB is the sole predecessor of TARGET_BB. */
778 if (single_pred_p (target_bb)
779 && single_pred (target_bb) == def_bb)
781 df_ref x;
783 /* See if USE is killed between DEF_INSN and the last insn in the
784 basic block containing DEF_INSN. */
785 x = df_bb_regno_last_def_find (def_bb, regno);
786 if (x && DF_INSN_LUID (DF_REF_INSN (x)) >= DF_INSN_LUID (def_insn))
787 return true;
789 /* See if USE is killed between TARGET_INSN and the first insn in the
790 basic block containing TARGET_INSN. */
791 x = df_bb_regno_first_def_find (target_bb, regno);
792 if (x && DF_INSN_LUID (DF_REF_INSN (x)) < DF_INSN_LUID (target_insn))
793 return true;
795 return false;
798 /* Otherwise assume the worst case. */
799 return true;
803 /* Check if all uses in DEF_INSN can be used in TARGET_INSN. This
804 would require full computation of available expressions;
805 we check only restricted conditions, see use_killed_between. */
806 static bool
807 all_uses_available_at (rtx_insn *def_insn, rtx_insn *target_insn)
809 df_ref use;
810 struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
811 rtx def_set = single_set (def_insn);
812 rtx_insn *next;
814 gcc_assert (def_set);
816 /* If target_insn comes right after def_insn, which is very common
817 for addresses, we can use a quicker test. Ignore debug insns
818 other than target insns for this. */
819 next = NEXT_INSN (def_insn);
820 while (next && next != target_insn && DEBUG_INSN_P (next))
821 next = NEXT_INSN (next);
822 if (next == target_insn && REG_P (SET_DEST (def_set)))
824 rtx def_reg = SET_DEST (def_set);
826 /* If the insn uses the reg that it defines, the substitution is
827 invalid. */
828 FOR_EACH_INSN_INFO_USE (use, insn_info)
829 if (rtx_equal_p (DF_REF_REG (use), def_reg))
830 return false;
831 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
832 if (rtx_equal_p (DF_REF_REG (use), def_reg))
833 return false;
835 else
837 rtx def_reg = REG_P (SET_DEST (def_set)) ? SET_DEST (def_set) : NULL_RTX;
839 /* Look at all the uses of DEF_INSN, and see if they are not
840 killed between DEF_INSN and TARGET_INSN. */
841 FOR_EACH_INSN_INFO_USE (use, insn_info)
843 if (def_reg && rtx_equal_p (DF_REF_REG (use), def_reg))
844 return false;
845 if (use_killed_between (use, def_insn, target_insn))
846 return false;
848 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
850 if (def_reg && rtx_equal_p (DF_REF_REG (use), def_reg))
851 return false;
852 if (use_killed_between (use, def_insn, target_insn))
853 return false;
857 return true;
861 static df_ref *active_defs;
862 static sparseset active_defs_check;
864 /* Fill the ACTIVE_DEFS array with the use->def link for the registers
865 mentioned in USE_REC. Register the valid entries in ACTIVE_DEFS_CHECK
866 too, for checking purposes. */
868 static void
869 register_active_defs (df_ref use)
871 for (; use; use = DF_REF_NEXT_LOC (use))
873 df_ref def = get_def_for_use (use);
874 int regno = DF_REF_REGNO (use);
876 if (flag_checking)
877 sparseset_set_bit (active_defs_check, regno);
878 active_defs[regno] = def;
883 /* Build the use->def links that we use to update the dataflow info
884 for new uses. Note that building the links is very cheap and if
885 it were done earlier, they could be used to rule out invalid
886 propagations (in addition to what is done in all_uses_available_at).
887 I'm not doing this yet, though. */
889 static void
890 update_df_init (rtx_insn *def_insn, rtx_insn *insn)
892 if (flag_checking)
893 sparseset_clear (active_defs_check);
894 register_active_defs (DF_INSN_USES (def_insn));
895 register_active_defs (DF_INSN_USES (insn));
896 register_active_defs (DF_INSN_EQ_USES (insn));
900 /* Update the USE_DEF_REF array for the given use, using the active definitions
901 in the ACTIVE_DEFS array to match pseudos to their def. */
903 static inline void
904 update_uses (df_ref use)
906 for (; use; use = DF_REF_NEXT_LOC (use))
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 if (flag_checking)
915 gcc_assert (sparseset_bit_p (active_defs_check, regno));
916 use_def_ref[DF_REF_ID (use)] = active_defs[regno];
921 /* Update the USE_DEF_REF array for the uses in INSN. Only update note
922 uses if NOTES_ONLY is true. */
924 static void
925 update_df (rtx_insn *insn, rtx note)
927 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
929 if (note)
931 df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE);
932 df_notes_rescan (insn);
934 else
936 df_uses_create (&PATTERN (insn), insn, 0);
937 df_insn_rescan (insn);
938 update_uses (DF_INSN_INFO_USES (insn_info));
941 update_uses (DF_INSN_INFO_EQ_USES (insn_info));
945 /* Try substituting NEW into LOC, which originated from forward propagation
946 of USE's value from DEF_INSN. SET_REG_EQUAL says whether we are
947 substituting the whole SET_SRC, so we can set a REG_EQUAL note if the
948 new insn is not recognized. Return whether the substitution was
949 performed. */
951 static bool
952 try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx_insn *def_insn,
953 bool set_reg_equal)
955 rtx_insn *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), GET_MODE (SET_DEST (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), GET_MODE (SET_DEST (set)), speed)
990 > old_cost))
992 if (dump_file)
993 fprintf (dump_file, "Changes to insn %d not profitable\n",
994 INSN_UID (insn));
995 ok = false;
998 else
1000 if (dump_file)
1001 fprintf (dump_file, "Changed insn %d\n", INSN_UID (insn));
1002 ok = true;
1005 if (ok)
1007 confirm_change_group ();
1008 num_changes++;
1010 else
1012 cancel_changes (0);
1014 /* Can also record a simplified value in a REG_EQUAL note,
1015 making a new one if one does not already exist. */
1016 if (set_reg_equal)
1018 /* If there are any paradoxical SUBREGs, don't add REG_EQUAL note,
1019 because the bits in there can be anything and so might not
1020 match the REG_EQUAL note content. See PR70574. */
1021 subrtx_var_iterator::array_type array;
1022 FOR_EACH_SUBRTX_VAR (iter, array, *loc, NONCONST)
1024 rtx x = *iter;
1025 if (SUBREG_P (x) && paradoxical_subreg_p (x))
1027 set_reg_equal = false;
1028 break;
1032 if (set_reg_equal)
1034 if (dump_file)
1035 fprintf (dump_file, " Setting REG_EQUAL note\n");
1037 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
1042 if ((ok || note) && !CONSTANT_P (new_rtx))
1043 update_df (insn, note);
1045 return ok;
1048 /* For the given single_set INSN, containing SRC known to be a
1049 ZERO_EXTEND or SIGN_EXTEND of a register, return true if INSN
1050 is redundant due to the register being set by a LOAD_EXTEND_OP
1051 load from memory. */
1053 static bool
1054 free_load_extend (rtx src, rtx_insn *insn)
1056 rtx reg;
1057 df_ref def, use;
1059 reg = XEXP (src, 0);
1060 if (load_extend_op (GET_MODE (reg)) != GET_CODE (src))
1061 return false;
1063 FOR_EACH_INSN_USE (use, insn)
1064 if (!DF_REF_IS_ARTIFICIAL (use)
1065 && DF_REF_TYPE (use) == DF_REF_REG_USE
1066 && DF_REF_REG (use) == reg)
1067 break;
1068 if (!use)
1069 return false;
1071 def = get_def_for_use (use);
1072 if (!def)
1073 return false;
1075 if (DF_REF_IS_ARTIFICIAL (def))
1076 return false;
1078 if (NONJUMP_INSN_P (DF_REF_INSN (def)))
1080 rtx patt = PATTERN (DF_REF_INSN (def));
1082 if (GET_CODE (patt) == SET
1083 && GET_CODE (SET_SRC (patt)) == MEM
1084 && rtx_equal_p (SET_DEST (patt), reg))
1085 return true;
1087 return false;
1090 /* If USE is a subreg, see if it can be replaced by a pseudo. */
1092 static bool
1093 forward_propagate_subreg (df_ref use, rtx_insn *def_insn, rtx def_set)
1095 rtx use_reg = DF_REF_REG (use);
1096 rtx_insn *use_insn;
1097 rtx src;
1098 scalar_int_mode int_use_mode, src_mode;
1100 /* Only consider subregs... */
1101 machine_mode use_mode = GET_MODE (use_reg);
1102 if (GET_CODE (use_reg) != SUBREG
1103 || !REG_P (SET_DEST (def_set)))
1104 return false;
1106 if (paradoxical_subreg_p (use_reg))
1108 /* If this is a paradoxical SUBREG, we have no idea what value the
1109 extra bits would have. However, if the operand is equivalent to
1110 a SUBREG whose operand is the same as our mode, and all the modes
1111 are within a word, we can just use the inner operand because
1112 these SUBREGs just say how to treat the register. */
1113 use_insn = DF_REF_INSN (use);
1114 src = SET_SRC (def_set);
1115 if (GET_CODE (src) == SUBREG
1116 && REG_P (SUBREG_REG (src))
1117 && REGNO (SUBREG_REG (src)) >= FIRST_PSEUDO_REGISTER
1118 && GET_MODE (SUBREG_REG (src)) == use_mode
1119 && subreg_lowpart_p (src)
1120 && all_uses_available_at (def_insn, use_insn))
1121 return try_fwprop_subst (use, DF_REF_LOC (use), SUBREG_REG (src),
1122 def_insn, false);
1125 /* If this is a SUBREG of a ZERO_EXTEND or SIGN_EXTEND, and the SUBREG
1126 is the low part of the reg being extended then just use the inner
1127 operand. Don't do this if the ZERO_EXTEND or SIGN_EXTEND insn will
1128 be removed due to it matching a LOAD_EXTEND_OP load from memory,
1129 or due to the operation being a no-op when applied to registers.
1130 For example, if we have:
1132 A: (set (reg:DI X) (sign_extend:DI (reg:SI Y)))
1133 B: (... (subreg:SI (reg:DI X)) ...)
1135 and mode_rep_extended says that Y is already sign-extended,
1136 the backend will typically allow A to be combined with the
1137 definition of Y or, failing that, allow A to be deleted after
1138 reload through register tying. Introducing more uses of Y
1139 prevents both optimisations. */
1140 else if (is_a <scalar_int_mode> (use_mode, &int_use_mode)
1141 && subreg_lowpart_p (use_reg))
1143 use_insn = DF_REF_INSN (use);
1144 src = SET_SRC (def_set);
1145 if ((GET_CODE (src) == ZERO_EXTEND
1146 || GET_CODE (src) == SIGN_EXTEND)
1147 && is_a <scalar_int_mode> (GET_MODE (src), &src_mode)
1148 && REG_P (XEXP (src, 0))
1149 && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER
1150 && GET_MODE (XEXP (src, 0)) == use_mode
1151 && !free_load_extend (src, def_insn)
1152 && (targetm.mode_rep_extended (int_use_mode, src_mode)
1153 != (int) GET_CODE (src))
1154 && all_uses_available_at (def_insn, use_insn))
1155 return try_fwprop_subst (use, DF_REF_LOC (use), XEXP (src, 0),
1156 def_insn, false);
1159 return false;
1162 /* Try to replace USE with SRC (defined in DEF_INSN) in __asm. */
1164 static bool
1165 forward_propagate_asm (df_ref use, rtx_insn *def_insn, rtx def_set, rtx reg)
1167 rtx_insn *use_insn = DF_REF_INSN (use);
1168 rtx src, use_pat, asm_operands, new_rtx, *loc;
1169 int speed_p, i;
1170 df_ref uses;
1172 gcc_assert ((DF_REF_FLAGS (use) & DF_REF_IN_NOTE) == 0);
1174 src = SET_SRC (def_set);
1175 use_pat = PATTERN (use_insn);
1177 /* In __asm don't replace if src might need more registers than
1178 reg, as that could increase register pressure on the __asm. */
1179 uses = DF_INSN_USES (def_insn);
1180 if (uses && DF_REF_NEXT_LOC (uses))
1181 return false;
1183 update_df_init (def_insn, use_insn);
1184 speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
1185 asm_operands = NULL_RTX;
1186 switch (GET_CODE (use_pat))
1188 case ASM_OPERANDS:
1189 asm_operands = use_pat;
1190 break;
1191 case SET:
1192 if (MEM_P (SET_DEST (use_pat)))
1194 loc = &SET_DEST (use_pat);
1195 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1196 if (new_rtx)
1197 validate_unshare_change (use_insn, loc, new_rtx, true);
1199 asm_operands = SET_SRC (use_pat);
1200 break;
1201 case PARALLEL:
1202 for (i = 0; i < XVECLEN (use_pat, 0); i++)
1203 if (GET_CODE (XVECEXP (use_pat, 0, i)) == SET)
1205 if (MEM_P (SET_DEST (XVECEXP (use_pat, 0, i))))
1207 loc = &SET_DEST (XVECEXP (use_pat, 0, i));
1208 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg,
1209 src, speed_p);
1210 if (new_rtx)
1211 validate_unshare_change (use_insn, loc, new_rtx, true);
1213 asm_operands = SET_SRC (XVECEXP (use_pat, 0, i));
1215 else if (GET_CODE (XVECEXP (use_pat, 0, i)) == ASM_OPERANDS)
1216 asm_operands = XVECEXP (use_pat, 0, i);
1217 break;
1218 default:
1219 gcc_unreachable ();
1222 gcc_assert (asm_operands && GET_CODE (asm_operands) == ASM_OPERANDS);
1223 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (asm_operands); i++)
1225 loc = &ASM_OPERANDS_INPUT (asm_operands, i);
1226 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1227 if (new_rtx)
1228 validate_unshare_change (use_insn, loc, new_rtx, true);
1231 if (num_changes_pending () == 0 || !apply_change_group ())
1232 return false;
1234 update_df (use_insn, NULL);
1235 num_changes++;
1236 return true;
1239 /* Try to replace USE with SRC (defined in DEF_INSN) and simplify the
1240 result. */
1242 static bool
1243 forward_propagate_and_simplify (df_ref use, rtx_insn *def_insn, rtx def_set)
1245 rtx_insn *use_insn = DF_REF_INSN (use);
1246 rtx use_set = single_set (use_insn);
1247 rtx src, reg, new_rtx, *loc;
1248 bool set_reg_equal;
1249 machine_mode mode;
1250 int asm_use = -1;
1252 if (INSN_CODE (use_insn) < 0)
1253 asm_use = asm_noperands (PATTERN (use_insn));
1255 if (!use_set && asm_use < 0 && !DEBUG_INSN_P (use_insn))
1256 return false;
1258 /* Do not propagate into PC, CC0, etc. */
1259 if (use_set && GET_MODE (SET_DEST (use_set)) == VOIDmode)
1260 return false;
1262 /* If def and use are subreg, check if they match. */
1263 reg = DF_REF_REG (use);
1264 if (GET_CODE (reg) == SUBREG && GET_CODE (SET_DEST (def_set)) == SUBREG)
1266 if (maybe_ne (SUBREG_BYTE (SET_DEST (def_set)), SUBREG_BYTE (reg)))
1267 return false;
1269 /* Check if the def had a subreg, but the use has the whole reg. */
1270 else if (REG_P (reg) && GET_CODE (SET_DEST (def_set)) == SUBREG)
1271 return false;
1272 /* Check if the use has a subreg, but the def had the whole reg. Unlike the
1273 previous case, the optimization is possible and often useful indeed. */
1274 else if (GET_CODE (reg) == SUBREG && REG_P (SET_DEST (def_set)))
1275 reg = SUBREG_REG (reg);
1277 /* Make sure that we can treat REG as having the same mode as the
1278 source of DEF_SET. */
1279 if (GET_MODE (SET_DEST (def_set)) != GET_MODE (reg))
1280 return false;
1282 /* Check if the substitution is valid (last, because it's the most
1283 expensive check!). */
1284 src = SET_SRC (def_set);
1285 if (!CONSTANT_P (src) && !all_uses_available_at (def_insn, use_insn))
1286 return false;
1288 /* Check if the def is loading something from the constant pool; in this
1289 case we would undo optimization such as compress_float_constant.
1290 Still, we can set a REG_EQUAL note. */
1291 if (MEM_P (src) && MEM_READONLY_P (src))
1293 rtx x = avoid_constant_pool_reference (src);
1294 if (x != src && use_set)
1296 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1297 rtx old_rtx = note ? XEXP (note, 0) : SET_SRC (use_set);
1298 rtx new_rtx = simplify_replace_rtx (old_rtx, src, x);
1299 if (old_rtx != new_rtx)
1300 set_unique_reg_note (use_insn, REG_EQUAL, copy_rtx (new_rtx));
1302 return false;
1305 if (asm_use >= 0)
1306 return forward_propagate_asm (use, def_insn, def_set, reg);
1308 /* Else try simplifying. */
1310 if (DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE)
1312 loc = &SET_DEST (use_set);
1313 set_reg_equal = false;
1315 else if (!use_set)
1317 loc = &INSN_VAR_LOCATION_LOC (use_insn);
1318 set_reg_equal = false;
1320 else
1322 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1323 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1324 loc = &XEXP (note, 0);
1325 else
1326 loc = &SET_SRC (use_set);
1328 /* Do not replace an existing REG_EQUAL note if the insn is not
1329 recognized. Either we're already replacing in the note, or we'll
1330 separately try plugging the definition in the note and simplifying.
1331 And only install a REQ_EQUAL note when the destination is a REG
1332 that isn't mentioned in USE_SET, as the note would be invalid
1333 otherwise. We also don't want to install a note if we are merely
1334 propagating a pseudo since verifying that this pseudo isn't dead
1335 is a pain; moreover such a note won't help anything.
1336 If the use is a paradoxical subreg, make sure we don't add a
1337 REG_EQUAL note for it, because it is not equivalent, it is one
1338 possible value for it, but we can't rely on it holding that value.
1339 See PR70574. */
1340 set_reg_equal = (note == NULL_RTX
1341 && REG_P (SET_DEST (use_set))
1342 && !REG_P (src)
1343 && !(GET_CODE (src) == SUBREG
1344 && REG_P (SUBREG_REG (src)))
1345 && !reg_mentioned_p (SET_DEST (use_set),
1346 SET_SRC (use_set))
1347 && !paradoxical_subreg_p (DF_REF_REG (use)));
1350 if (GET_MODE (*loc) == VOIDmode)
1351 mode = GET_MODE (SET_DEST (use_set));
1352 else
1353 mode = GET_MODE (*loc);
1355 new_rtx = propagate_rtx (*loc, mode, reg, src,
1356 optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn)));
1358 if (!new_rtx)
1359 return false;
1361 return try_fwprop_subst (use, loc, new_rtx, def_insn, set_reg_equal);
1365 /* Given a use USE of an insn, if it has a single reaching
1366 definition, try to forward propagate it into that insn.
1367 Return true if cfg cleanup will be needed. */
1369 static bool
1370 forward_propagate_into (df_ref use)
1372 df_ref def;
1373 rtx_insn *def_insn, *use_insn;
1374 rtx def_set;
1375 rtx parent;
1377 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
1378 return false;
1379 if (DF_REF_IS_ARTIFICIAL (use))
1380 return false;
1382 /* Only consider uses that have a single definition. */
1383 def = get_def_for_use (use);
1384 if (!def)
1385 return false;
1386 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
1387 return false;
1388 if (DF_REF_IS_ARTIFICIAL (def))
1389 return false;
1391 /* Do not propagate loop invariant definitions inside the loop. */
1392 if (DF_REF_BB (def)->loop_father != DF_REF_BB (use)->loop_father)
1393 return false;
1395 /* Check if the use is still present in the insn! */
1396 use_insn = DF_REF_INSN (use);
1397 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1398 parent = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1399 else
1400 parent = PATTERN (use_insn);
1402 if (!reg_mentioned_p (DF_REF_REG (use), parent))
1403 return false;
1405 def_insn = DF_REF_INSN (def);
1406 if (multiple_sets (def_insn))
1407 return false;
1408 def_set = single_set (def_insn);
1409 if (!def_set)
1410 return false;
1412 /* Only try one kind of propagation. If two are possible, we'll
1413 do it on the following iterations. */
1414 if (forward_propagate_and_simplify (use, def_insn, def_set)
1415 || forward_propagate_subreg (use, def_insn, def_set))
1417 propagations_left--;
1419 if (cfun->can_throw_non_call_exceptions
1420 && find_reg_note (use_insn, REG_EH_REGION, NULL_RTX)
1421 && purge_dead_edges (DF_REF_BB (use)))
1422 return true;
1424 return false;
1428 static void
1429 fwprop_init (void)
1431 num_changes = 0;
1432 calculate_dominance_info (CDI_DOMINATORS);
1434 /* We do not always want to propagate into loops, so we have to find
1435 loops and be careful about them. Avoid CFG modifications so that
1436 we don't have to update dominance information afterwards for
1437 build_single_def_use_links. */
1438 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
1440 build_single_def_use_links ();
1441 df_set_flags (DF_DEFER_INSN_RESCAN);
1443 active_defs = XNEWVEC (df_ref, max_reg_num ());
1444 if (flag_checking)
1445 active_defs_check = sparseset_alloc (max_reg_num ());
1447 propagations_left = DF_USES_TABLE_SIZE ();
1450 static void
1451 fwprop_done (void)
1453 loop_optimizer_finalize ();
1455 use_def_ref.release ();
1456 free (active_defs);
1457 if (flag_checking)
1458 sparseset_free (active_defs_check);
1460 free_dominance_info (CDI_DOMINATORS);
1461 cleanup_cfg (0);
1462 delete_trivially_dead_insns (get_insns (), max_reg_num ());
1464 if (dump_file)
1465 fprintf (dump_file,
1466 "\nNumber of successful forward propagations: %d\n\n",
1467 num_changes);
1471 /* Main entry point. */
1473 static bool
1474 gate_fwprop (void)
1476 return optimize > 0 && flag_forward_propagate;
1479 static unsigned int
1480 fwprop (void)
1482 unsigned i;
1484 fwprop_init ();
1486 /* Go through all the uses. df_uses_create will create new ones at the
1487 end, and we'll go through them as well.
1489 Do not forward propagate addresses into loops until after unrolling.
1490 CSE did so because it was able to fix its own mess, but we are not. */
1492 for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1494 if (!propagations_left)
1495 break;
1497 df_ref use = DF_USES_GET (i);
1498 if (use)
1499 if (DF_REF_TYPE (use) == DF_REF_REG_USE
1500 || DF_REF_BB (use)->loop_father == NULL
1501 /* The outer most loop is not really a loop. */
1502 || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
1503 forward_propagate_into (use);
1506 fwprop_done ();
1507 return 0;
1510 namespace {
1512 const pass_data pass_data_rtl_fwprop =
1514 RTL_PASS, /* type */
1515 "fwprop1", /* name */
1516 OPTGROUP_NONE, /* optinfo_flags */
1517 TV_FWPROP, /* tv_id */
1518 0, /* properties_required */
1519 0, /* properties_provided */
1520 0, /* properties_destroyed */
1521 0, /* todo_flags_start */
1522 TODO_df_finish, /* todo_flags_finish */
1525 class pass_rtl_fwprop : public rtl_opt_pass
1527 public:
1528 pass_rtl_fwprop (gcc::context *ctxt)
1529 : rtl_opt_pass (pass_data_rtl_fwprop, ctxt)
1532 /* opt_pass methods: */
1533 virtual bool gate (function *) { return gate_fwprop (); }
1534 virtual unsigned int execute (function *) { return fwprop (); }
1536 }; // class pass_rtl_fwprop
1538 } // anon namespace
1540 rtl_opt_pass *
1541 make_pass_rtl_fwprop (gcc::context *ctxt)
1543 return new pass_rtl_fwprop (ctxt);
1546 static unsigned int
1547 fwprop_addr (void)
1549 unsigned i;
1551 fwprop_init ();
1553 /* Go through all the uses. df_uses_create will create new ones at the
1554 end, and we'll go through them as well. */
1555 for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1557 if (!propagations_left)
1558 break;
1560 df_ref use = DF_USES_GET (i);
1561 if (use)
1562 if (DF_REF_TYPE (use) != DF_REF_REG_USE
1563 && DF_REF_BB (use)->loop_father != NULL
1564 /* The outer most loop is not really a loop. */
1565 && loop_outer (DF_REF_BB (use)->loop_father) != NULL)
1566 forward_propagate_into (use);
1569 fwprop_done ();
1570 return 0;
1573 namespace {
1575 const pass_data pass_data_rtl_fwprop_addr =
1577 RTL_PASS, /* type */
1578 "fwprop2", /* name */
1579 OPTGROUP_NONE, /* optinfo_flags */
1580 TV_FWPROP, /* tv_id */
1581 0, /* properties_required */
1582 0, /* properties_provided */
1583 0, /* properties_destroyed */
1584 0, /* todo_flags_start */
1585 TODO_df_finish, /* todo_flags_finish */
1588 class pass_rtl_fwprop_addr : public rtl_opt_pass
1590 public:
1591 pass_rtl_fwprop_addr (gcc::context *ctxt)
1592 : rtl_opt_pass (pass_data_rtl_fwprop_addr, ctxt)
1595 /* opt_pass methods: */
1596 virtual bool gate (function *) { return gate_fwprop (); }
1597 virtual unsigned int execute (function *) { return fwprop_addr (); }
1599 }; // class pass_rtl_fwprop_addr
1601 } // anon namespace
1603 rtl_opt_pass *
1604 make_pass_rtl_fwprop_addr (gcc::context *ctxt)
1606 return new pass_rtl_fwprop_addr (ctxt);