2015-05-22 Robert Dewar <dewar@adacore.com>
[official-gcc.git] / gcc / fwprop.c
blobfc64ec95e6bc7a5b4e4da4b0005b3f5c80a1b405
1 /* RTL-based forward propagation pass for GNU compiler.
2 Copyright (C) 2005-2015 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 "predict.h"
35 #include "vec.h"
36 #include "hashtab.h"
37 #include "hash-set.h"
38 #include "machmode.h"
39 #include "hard-reg-set.h"
40 #include "input.h"
41 #include "function.h"
42 #include "dominance.h"
43 #include "cfg.h"
44 #include "cfgrtl.h"
45 #include "cfgcleanup.h"
46 #include "basic-block.h"
47 #include "df.h"
48 #include "target.h"
49 #include "cfgloop.h"
50 #include "tree-pass.h"
51 #include "domwalk.h"
52 #include "emit-rtl.h"
53 #include "rtl-iter.h"
56 /* This pass does simple forward propagation and simplification when an
57 operand of an insn can only come from a single def. This pass uses
58 df.c, so it is global. However, we only do limited analysis of
59 available expressions.
61 1) The pass tries to propagate the source of the def into the use,
62 and checks if the result is independent of the substituted value.
63 For example, the high word of a (zero_extend:DI (reg:SI M)) is always
64 zero, independent of the source register.
66 In particular, we propagate constants into the use site. Sometimes
67 RTL expansion did not put the constant in the same insn on purpose,
68 to satisfy a predicate, and the result will fail to be recognized;
69 but this happens rarely and in this case we can still create a
70 REG_EQUAL note. For multi-word operations, this
72 (set (subreg:SI (reg:DI 120) 0) (const_int 0))
73 (set (subreg:SI (reg:DI 120) 4) (const_int -1))
74 (set (subreg:SI (reg:DI 122) 0)
75 (ior:SI (subreg:SI (reg:DI 119) 0) (subreg:SI (reg:DI 120) 0)))
76 (set (subreg:SI (reg:DI 122) 4)
77 (ior:SI (subreg:SI (reg:DI 119) 4) (subreg:SI (reg:DI 120) 4)))
79 can be simplified to the much simpler
81 (set (subreg:SI (reg:DI 122) 0) (subreg:SI (reg:DI 119)))
82 (set (subreg:SI (reg:DI 122) 4) (const_int -1))
84 This particular propagation is also effective at putting together
85 complex addressing modes. We are more aggressive inside MEMs, in
86 that all definitions are propagated if the use is in a MEM; if the
87 result is a valid memory address we check address_cost to decide
88 whether the substitution is worthwhile.
90 2) The pass propagates register copies. This is not as effective as
91 the copy propagation done by CSE's canon_reg, which works by walking
92 the instruction chain, it can help the other transformations.
94 We should consider removing this optimization, and instead reorder the
95 RTL passes, because GCSE does this transformation too. With some luck,
96 the CSE pass at the end of rest_of_handle_gcse could also go away.
98 3) The pass looks for paradoxical subregs that are actually unnecessary.
99 Things like this:
101 (set (reg:QI 120) (subreg:QI (reg:SI 118) 0))
102 (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
103 (set (reg:SI 122) (plus:SI (subreg:SI (reg:QI 120) 0)
104 (subreg:SI (reg:QI 121) 0)))
106 are very common on machines that can only do word-sized operations.
107 For each use of a paradoxical subreg (subreg:WIDER (reg:NARROW N) 0),
108 if it has a single def and it is (subreg:NARROW (reg:WIDE M) 0),
109 we can replace the paradoxical subreg with simply (reg:WIDE M). The
110 above will simplify this to
112 (set (reg:QI 120) (subreg:QI (reg:SI 118) 0))
113 (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
114 (set (reg:SI 122) (plus:SI (reg:SI 118) (reg:SI 119)))
116 where the first two insns are now dead.
118 We used to use reaching definitions to find which uses have a
119 single reaching definition (sounds obvious...), but this is too
120 complex a problem in nasty testcases like PR33928. Now we use the
121 multiple definitions problem in df-problems.c. The similarity
122 between that problem and SSA form creation is taken further, in
123 that fwprop does a dominator walk to create its chains; however,
124 instead of creating a PHI function where multiple definitions meet
125 I just punt and record only singleton use-def chains, which is
126 all that is needed by fwprop. */
129 static int num_changes;
131 static vec<df_ref> use_def_ref;
132 static vec<df_ref> reg_defs;
133 static vec<df_ref> reg_defs_stack;
135 /* The MD bitmaps are trimmed to include only live registers to cut
136 memory usage on testcases like insn-recog.c. Track live registers
137 in the basic block and do not perform forward propagation if the
138 destination is a dead pseudo occurring in a note. */
139 static bitmap local_md;
140 static bitmap local_lr;
142 /* Return the only def in USE's use-def chain, or NULL if there is
143 more than one def in the chain. */
145 static inline df_ref
146 get_def_for_use (df_ref use)
148 return use_def_ref[DF_REF_ID (use)];
152 /* Update the reg_defs vector with non-partial definitions in DEF_REC.
153 TOP_FLAG says which artificials uses should be used, when DEF_REC
154 is an artificial def vector. LOCAL_MD is modified as after a
155 df_md_simulate_* function; we do more or less the same processing
156 done there, so we do not use those functions. */
158 #define DF_MD_GEN_FLAGS \
159 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
161 static void
162 process_defs (df_ref def, int top_flag)
164 for (; def; def = DF_REF_NEXT_LOC (def))
166 df_ref curr_def = reg_defs[DF_REF_REGNO (def)];
167 unsigned int dregno;
169 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag)
170 continue;
172 dregno = DF_REF_REGNO (def);
173 if (curr_def)
174 reg_defs_stack.safe_push (curr_def);
175 else
177 /* Do not store anything if "transitioning" from NULL to NULL. But
178 otherwise, push a special entry on the stack to tell the
179 leave_block callback that the entry in reg_defs was NULL. */
180 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
182 else
183 reg_defs_stack.safe_push (def);
186 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
188 bitmap_set_bit (local_md, dregno);
189 reg_defs[dregno] = NULL;
191 else
193 bitmap_clear_bit (local_md, dregno);
194 reg_defs[dregno] = def;
200 /* Fill the use_def_ref vector with values for the uses in USE_REC,
201 taking reaching definitions info from LOCAL_MD and REG_DEFS.
202 TOP_FLAG says which artificials uses should be used, when USE_REC
203 is an artificial use vector. */
205 static void
206 process_uses (df_ref use, int top_flag)
208 for (; use; use = DF_REF_NEXT_LOC (use))
209 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag)
211 unsigned int uregno = DF_REF_REGNO (use);
212 if (reg_defs[uregno]
213 && !bitmap_bit_p (local_md, uregno)
214 && bitmap_bit_p (local_lr, uregno))
215 use_def_ref[DF_REF_ID (use)] = reg_defs[uregno];
219 class single_def_use_dom_walker : public dom_walker
221 public:
222 single_def_use_dom_walker (cdi_direction direction)
223 : dom_walker (direction) {}
224 virtual void before_dom_children (basic_block);
225 virtual void after_dom_children (basic_block);
228 void
229 single_def_use_dom_walker::before_dom_children (basic_block bb)
231 int bb_index = bb->index;
232 struct df_md_bb_info *md_bb_info = df_md_get_bb_info (bb_index);
233 struct df_lr_bb_info *lr_bb_info = df_lr_get_bb_info (bb_index);
234 rtx_insn *insn;
236 bitmap_copy (local_md, &md_bb_info->in);
237 bitmap_copy (local_lr, &lr_bb_info->in);
239 /* Push a marker for the leave_block callback. */
240 reg_defs_stack.safe_push (NULL);
242 process_uses (df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
243 process_defs (df_get_artificial_defs (bb_index), DF_REF_AT_TOP);
245 /* We don't call df_simulate_initialize_forwards, as it may overestimate
246 the live registers if there are unused artificial defs. We prefer
247 liveness to be underestimated. */
249 FOR_BB_INSNS (bb, insn)
250 if (INSN_P (insn))
252 unsigned int uid = INSN_UID (insn);
253 process_uses (DF_INSN_UID_USES (uid), 0);
254 process_uses (DF_INSN_UID_EQ_USES (uid), 0);
255 process_defs (DF_INSN_UID_DEFS (uid), 0);
256 df_simulate_one_insn_forwards (bb, insn, local_lr);
259 process_uses (df_get_artificial_uses (bb_index), 0);
260 process_defs (df_get_artificial_defs (bb_index), 0);
263 /* Pop the definitions created in this basic block when leaving its
264 dominated parts. */
266 void
267 single_def_use_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
269 df_ref saved_def;
270 while ((saved_def = reg_defs_stack.pop ()) != NULL)
272 unsigned int dregno = DF_REF_REGNO (saved_def);
274 /* See also process_defs. */
275 if (saved_def == reg_defs[dregno])
276 reg_defs[dregno] = NULL;
277 else
278 reg_defs[dregno] = saved_def;
283 /* Build a vector holding the reaching definitions of uses reached by a
284 single dominating definition. */
286 static void
287 build_single_def_use_links (void)
289 /* We use the multiple definitions problem to compute our restricted
290 use-def chains. */
291 df_set_flags (DF_EQ_NOTES);
292 df_md_add_problem ();
293 df_note_add_problem ();
294 df_analyze ();
295 df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
297 use_def_ref.create (DF_USES_TABLE_SIZE ());
298 use_def_ref.safe_grow_cleared (DF_USES_TABLE_SIZE ());
300 reg_defs.create (max_reg_num ());
301 reg_defs.safe_grow_cleared (max_reg_num ());
303 reg_defs_stack.create (n_basic_blocks_for_fn (cfun) * 10);
304 local_md = BITMAP_ALLOC (NULL);
305 local_lr = BITMAP_ALLOC (NULL);
307 /* Walk the dominator tree looking for single reaching definitions
308 dominating the uses. This is similar to how SSA form is built. */
309 single_def_use_dom_walker (CDI_DOMINATORS)
310 .walk (cfun->cfg->x_entry_block_ptr);
312 BITMAP_FREE (local_lr);
313 BITMAP_FREE (local_md);
314 reg_defs.release ();
315 reg_defs_stack.release ();
319 /* Do not try to replace constant addresses or addresses of local and
320 argument slots. These MEM expressions are made only once and inserted
321 in many instructions, as well as being used to control symbol table
322 output. It is not safe to clobber them.
324 There are some uncommon cases where the address is already in a register
325 for some reason, but we cannot take advantage of that because we have
326 no easy way to unshare the MEM. In addition, looking up all stack
327 addresses is costly. */
329 static bool
330 can_simplify_addr (rtx addr)
332 rtx reg;
334 if (CONSTANT_ADDRESS_P (addr))
335 return false;
337 if (GET_CODE (addr) == PLUS)
338 reg = XEXP (addr, 0);
339 else
340 reg = addr;
342 return (!REG_P (reg)
343 || (REGNO (reg) != FRAME_POINTER_REGNUM
344 && REGNO (reg) != HARD_FRAME_POINTER_REGNUM
345 && REGNO (reg) != ARG_POINTER_REGNUM));
348 /* Returns a canonical version of X for the address, from the point of view,
349 that all multiplications are represented as MULT instead of the multiply
350 by a power of 2 being represented as ASHIFT.
352 Every ASHIFT we find has been made by simplify_gen_binary and was not
353 there before, so it is not shared. So we can do this in place. */
355 static void
356 canonicalize_address (rtx x)
358 for (;;)
359 switch (GET_CODE (x))
361 case ASHIFT:
362 if (CONST_INT_P (XEXP (x, 1))
363 && INTVAL (XEXP (x, 1)) < GET_MODE_BITSIZE (GET_MODE (x))
364 && INTVAL (XEXP (x, 1)) >= 0)
366 HOST_WIDE_INT shift = INTVAL (XEXP (x, 1));
367 PUT_CODE (x, MULT);
368 XEXP (x, 1) = gen_int_mode ((HOST_WIDE_INT) 1 << shift,
369 GET_MODE (x));
372 x = XEXP (x, 0);
373 break;
375 case PLUS:
376 if (GET_CODE (XEXP (x, 0)) == PLUS
377 || GET_CODE (XEXP (x, 0)) == ASHIFT
378 || GET_CODE (XEXP (x, 0)) == CONST)
379 canonicalize_address (XEXP (x, 0));
381 x = XEXP (x, 1);
382 break;
384 case CONST:
385 x = XEXP (x, 0);
386 break;
388 default:
389 return;
393 /* OLD is a memory address. Return whether it is good to use NEW instead,
394 for a memory access in the given MODE. */
396 static bool
397 should_replace_address (rtx old_rtx, rtx new_rtx, machine_mode mode,
398 addr_space_t as, bool speed)
400 int gain;
402 if (rtx_equal_p (old_rtx, new_rtx)
403 || !memory_address_addr_space_p (mode, new_rtx, as))
404 return false;
406 /* Copy propagation is always ok. */
407 if (REG_P (old_rtx) && REG_P (new_rtx))
408 return true;
410 /* Prefer the new address if it is less expensive. */
411 gain = (address_cost (old_rtx, mode, as, speed)
412 - address_cost (new_rtx, mode, as, speed));
414 /* If the addresses have equivalent cost, prefer the new address
415 if it has the highest `set_src_cost'. That has the potential of
416 eliminating the most insns without additional costs, and it
417 is the same that cse.c used to do. */
418 if (gain == 0)
419 gain = set_src_cost (new_rtx, speed) - set_src_cost (old_rtx, speed);
421 return (gain > 0);
425 /* Flags for the last parameter of propagate_rtx_1. */
427 enum {
428 /* If PR_CAN_APPEAR is true, propagate_rtx_1 always returns true;
429 if it is false, propagate_rtx_1 returns false if, for at least
430 one occurrence OLD, it failed to collapse the result to a constant.
431 For example, (mult:M (reg:M A) (minus:M (reg:M B) (reg:M A))) may
432 collapse to zero if replacing (reg:M B) with (reg:M A).
434 PR_CAN_APPEAR is disregarded inside MEMs: in that case,
435 propagate_rtx_1 just tries to make cheaper and valid memory
436 addresses. */
437 PR_CAN_APPEAR = 1,
439 /* If PR_HANDLE_MEM is not set, propagate_rtx_1 won't attempt any replacement
440 outside memory addresses. This is needed because propagate_rtx_1 does
441 not do any analysis on memory; thus it is very conservative and in general
442 it will fail if non-read-only MEMs are found in the source expression.
444 PR_HANDLE_MEM is set when the source of the propagation was not
445 another MEM. Then, it is safe not to treat non-read-only MEMs as
446 ``opaque'' objects. */
447 PR_HANDLE_MEM = 2,
449 /* Set when costs should be optimized for speed. */
450 PR_OPTIMIZE_FOR_SPEED = 4
454 /* Replace all occurrences of OLD in *PX with NEW and try to simplify the
455 resulting expression. Replace *PX with a new RTL expression if an
456 occurrence of OLD was found.
458 This is only a wrapper around simplify-rtx.c: do not add any pattern
459 matching code here. (The sole exception is the handling of LO_SUM, but
460 that is because there is no simplify_gen_* function for LO_SUM). */
462 static bool
463 propagate_rtx_1 (rtx *px, rtx old_rtx, rtx new_rtx, int flags)
465 rtx x = *px, tem = NULL_RTX, op0, op1, op2;
466 enum rtx_code code = GET_CODE (x);
467 machine_mode mode = GET_MODE (x);
468 machine_mode op_mode;
469 bool can_appear = (flags & PR_CAN_APPEAR) != 0;
470 bool valid_ops = true;
472 if (!(flags & PR_HANDLE_MEM) && MEM_P (x) && !MEM_READONLY_P (x))
474 /* If unsafe, change MEMs to CLOBBERs or SCRATCHes (to preserve whether
475 they have side effects or not). */
476 *px = (side_effects_p (x)
477 ? gen_rtx_CLOBBER (GET_MODE (x), const0_rtx)
478 : gen_rtx_SCRATCH (GET_MODE (x)));
479 return false;
482 /* If X is OLD_RTX, return NEW_RTX. But not if replacing only within an
483 address, and we are *not* inside one. */
484 if (x == old_rtx)
486 *px = new_rtx;
487 return can_appear;
490 /* If this is an expression, try recursive substitution. */
491 switch (GET_RTX_CLASS (code))
493 case RTX_UNARY:
494 op0 = XEXP (x, 0);
495 op_mode = GET_MODE (op0);
496 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
497 if (op0 == XEXP (x, 0))
498 return true;
499 tem = simplify_gen_unary (code, mode, op0, op_mode);
500 break;
502 case RTX_BIN_ARITH:
503 case RTX_COMM_ARITH:
504 op0 = XEXP (x, 0);
505 op1 = XEXP (x, 1);
506 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
507 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
508 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
509 return true;
510 tem = simplify_gen_binary (code, mode, op0, op1);
511 break;
513 case RTX_COMPARE:
514 case RTX_COMM_COMPARE:
515 op0 = XEXP (x, 0);
516 op1 = XEXP (x, 1);
517 op_mode = GET_MODE (op0) != VOIDmode ? GET_MODE (op0) : GET_MODE (op1);
518 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
519 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
520 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
521 return true;
522 tem = simplify_gen_relational (code, mode, op_mode, op0, op1);
523 break;
525 case RTX_TERNARY:
526 case RTX_BITFIELD_OPS:
527 op0 = XEXP (x, 0);
528 op1 = XEXP (x, 1);
529 op2 = XEXP (x, 2);
530 op_mode = GET_MODE (op0);
531 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
532 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
533 valid_ops &= propagate_rtx_1 (&op2, old_rtx, new_rtx, flags);
534 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1) && op2 == XEXP (x, 2))
535 return true;
536 if (op_mode == VOIDmode)
537 op_mode = GET_MODE (op0);
538 tem = simplify_gen_ternary (code, mode, op_mode, op0, op1, op2);
539 break;
541 case RTX_EXTRA:
542 /* The only case we try to handle is a SUBREG. */
543 if (code == SUBREG)
545 op0 = XEXP (x, 0);
546 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
547 if (op0 == XEXP (x, 0))
548 return true;
549 tem = simplify_gen_subreg (mode, op0, GET_MODE (SUBREG_REG (x)),
550 SUBREG_BYTE (x));
552 break;
554 case RTX_OBJ:
555 if (code == MEM && x != new_rtx)
557 rtx new_op0;
558 op0 = XEXP (x, 0);
560 /* There are some addresses that we cannot work on. */
561 if (!can_simplify_addr (op0))
562 return true;
564 op0 = new_op0 = targetm.delegitimize_address (op0);
565 valid_ops &= propagate_rtx_1 (&new_op0, old_rtx, new_rtx,
566 flags | PR_CAN_APPEAR);
568 /* Dismiss transformation that we do not want to carry on. */
569 if (!valid_ops
570 || new_op0 == op0
571 || !(GET_MODE (new_op0) == GET_MODE (op0)
572 || GET_MODE (new_op0) == VOIDmode))
573 return true;
575 canonicalize_address (new_op0);
577 /* Copy propagations are always ok. Otherwise check the costs. */
578 if (!(REG_P (old_rtx) && REG_P (new_rtx))
579 && !should_replace_address (op0, new_op0, GET_MODE (x),
580 MEM_ADDR_SPACE (x),
581 flags & PR_OPTIMIZE_FOR_SPEED))
582 return true;
584 tem = replace_equiv_address_nv (x, new_op0);
587 else if (code == LO_SUM)
589 op0 = XEXP (x, 0);
590 op1 = XEXP (x, 1);
592 /* The only simplification we do attempts to remove references to op0
593 or make it constant -- in both cases, op0's invalidity will not
594 make the result invalid. */
595 propagate_rtx_1 (&op0, old_rtx, new_rtx, flags | PR_CAN_APPEAR);
596 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
597 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
598 return true;
600 /* (lo_sum (high x) x) -> x */
601 if (GET_CODE (op0) == HIGH && rtx_equal_p (XEXP (op0, 0), op1))
602 tem = op1;
603 else
604 tem = gen_rtx_LO_SUM (mode, op0, op1);
606 /* OP1 is likely not a legitimate address, otherwise there would have
607 been no LO_SUM. We want it to disappear if it is invalid, return
608 false in that case. */
609 return memory_address_p (mode, tem);
612 else if (code == REG)
614 if (rtx_equal_p (x, old_rtx))
616 *px = new_rtx;
617 return can_appear;
620 break;
622 default:
623 break;
626 /* No change, no trouble. */
627 if (tem == NULL_RTX)
628 return true;
630 *px = tem;
632 /* The replacement we made so far is valid, if all of the recursive
633 replacements were valid, or we could simplify everything to
634 a constant. */
635 return valid_ops || can_appear || CONSTANT_P (tem);
639 /* Return true if X constains a non-constant mem. */
641 static bool
642 varying_mem_p (const_rtx x)
644 subrtx_iterator::array_type array;
645 FOR_EACH_SUBRTX (iter, array, x, NONCONST)
646 if (MEM_P (*iter) && !MEM_READONLY_P (*iter))
647 return true;
648 return false;
652 /* Replace all occurrences of OLD in X with NEW and try to simplify the
653 resulting expression (in mode MODE). Return a new expression if it is
654 a constant, otherwise X.
656 Simplifications where occurrences of NEW collapse to a constant are always
657 accepted. All simplifications are accepted if NEW is a pseudo too.
658 Otherwise, we accept simplifications that have a lower or equal cost. */
660 static rtx
661 propagate_rtx (rtx x, machine_mode mode, rtx old_rtx, rtx new_rtx,
662 bool speed)
664 rtx tem;
665 bool collapsed;
666 int flags;
668 if (REG_P (new_rtx) && REGNO (new_rtx) < FIRST_PSEUDO_REGISTER)
669 return NULL_RTX;
671 flags = 0;
672 if (REG_P (new_rtx)
673 || CONSTANT_P (new_rtx)
674 || (GET_CODE (new_rtx) == SUBREG
675 && REG_P (SUBREG_REG (new_rtx))
676 && (GET_MODE_SIZE (mode)
677 <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (new_rtx))))))
678 flags |= PR_CAN_APPEAR;
679 if (!varying_mem_p (new_rtx))
680 flags |= PR_HANDLE_MEM;
682 if (speed)
683 flags |= PR_OPTIMIZE_FOR_SPEED;
685 tem = x;
686 collapsed = propagate_rtx_1 (&tem, old_rtx, copy_rtx (new_rtx), flags);
687 if (tem == x || !collapsed)
688 return NULL_RTX;
690 /* gen_lowpart_common will not be able to process VOIDmode entities other
691 than CONST_INTs. */
692 if (GET_MODE (tem) == VOIDmode && !CONST_INT_P (tem))
693 return NULL_RTX;
695 if (GET_MODE (tem) == VOIDmode)
696 tem = rtl_hooks.gen_lowpart_no_emit (mode, tem);
697 else
698 gcc_assert (GET_MODE (tem) == mode);
700 return tem;
706 /* Return true if the register from reference REF is killed
707 between FROM to (but not including) TO. */
709 static bool
710 local_ref_killed_between_p (df_ref ref, rtx_insn *from, rtx_insn *to)
712 rtx_insn *insn;
714 for (insn = from; insn != to; insn = NEXT_INSN (insn))
716 df_ref def;
717 if (!INSN_P (insn))
718 continue;
720 FOR_EACH_INSN_DEF (def, insn)
721 if (DF_REF_REGNO (ref) == DF_REF_REGNO (def))
722 return true;
724 return false;
728 /* Check if the given DEF is available in INSN. This would require full
729 computation of available expressions; we check only restricted conditions:
730 - if DEF is the sole definition of its register, go ahead;
731 - in the same basic block, we check for no definitions killing the
732 definition of DEF_INSN;
733 - if USE's basic block has DEF's basic block as the sole predecessor,
734 we check if the definition is killed after DEF_INSN or before
735 TARGET_INSN insn, in their respective basic blocks. */
736 static bool
737 use_killed_between (df_ref use, rtx_insn *def_insn, rtx_insn *target_insn)
739 basic_block def_bb = BLOCK_FOR_INSN (def_insn);
740 basic_block target_bb = BLOCK_FOR_INSN (target_insn);
741 int regno;
742 df_ref def;
744 /* We used to have a def reaching a use that is _before_ the def,
745 with the def not dominating the use even though the use and def
746 are in the same basic block, when a register may be used
747 uninitialized in a loop. This should not happen anymore since
748 we do not use reaching definitions, but still we test for such
749 cases and assume that DEF is not available. */
750 if (def_bb == target_bb
751 ? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn)
752 : !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb))
753 return true;
755 /* Check if the reg in USE has only one definition. We already
756 know that this definition reaches use, or we wouldn't be here.
757 However, this is invalid for hard registers because if they are
758 live at the beginning of the function it does not mean that we
759 have an uninitialized access. */
760 regno = DF_REF_REGNO (use);
761 def = DF_REG_DEF_CHAIN (regno);
762 if (def
763 && DF_REF_NEXT_REG (def) == NULL
764 && regno >= FIRST_PSEUDO_REGISTER)
765 return false;
767 /* Check locally if we are in the same basic block. */
768 if (def_bb == target_bb)
769 return local_ref_killed_between_p (use, def_insn, target_insn);
771 /* Finally, if DEF_BB is the sole predecessor of TARGET_BB. */
772 if (single_pred_p (target_bb)
773 && single_pred (target_bb) == def_bb)
775 df_ref x;
777 /* See if USE is killed between DEF_INSN and the last insn in the
778 basic block containing DEF_INSN. */
779 x = df_bb_regno_last_def_find (def_bb, regno);
780 if (x && DF_INSN_LUID (DF_REF_INSN (x)) >= DF_INSN_LUID (def_insn))
781 return true;
783 /* See if USE is killed between TARGET_INSN and the first insn in the
784 basic block containing TARGET_INSN. */
785 x = df_bb_regno_first_def_find (target_bb, regno);
786 if (x && DF_INSN_LUID (DF_REF_INSN (x)) < DF_INSN_LUID (target_insn))
787 return true;
789 return false;
792 /* Otherwise assume the worst case. */
793 return true;
797 /* Check if all uses in DEF_INSN can be used in TARGET_INSN. This
798 would require full computation of available expressions;
799 we check only restricted conditions, see use_killed_between. */
800 static bool
801 all_uses_available_at (rtx_insn *def_insn, rtx_insn *target_insn)
803 df_ref use;
804 struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
805 rtx def_set = single_set (def_insn);
806 rtx_insn *next;
808 gcc_assert (def_set);
810 /* If target_insn comes right after def_insn, which is very common
811 for addresses, we can use a quicker test. Ignore debug insns
812 other than target insns for this. */
813 next = NEXT_INSN (def_insn);
814 while (next && next != target_insn && DEBUG_INSN_P (next))
815 next = NEXT_INSN (next);
816 if (next == target_insn && REG_P (SET_DEST (def_set)))
818 rtx def_reg = SET_DEST (def_set);
820 /* If the insn uses the reg that it defines, the substitution is
821 invalid. */
822 FOR_EACH_INSN_INFO_USE (use, insn_info)
823 if (rtx_equal_p (DF_REF_REG (use), def_reg))
824 return false;
825 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
826 if (rtx_equal_p (DF_REF_REG (use), def_reg))
827 return false;
829 else
831 rtx def_reg = REG_P (SET_DEST (def_set)) ? SET_DEST (def_set) : NULL_RTX;
833 /* Look at all the uses of DEF_INSN, and see if they are not
834 killed between DEF_INSN and TARGET_INSN. */
835 FOR_EACH_INSN_INFO_USE (use, insn_info)
837 if (def_reg && rtx_equal_p (DF_REF_REG (use), def_reg))
838 return false;
839 if (use_killed_between (use, def_insn, target_insn))
840 return false;
842 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
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)
867 for (; use; use = DF_REF_NEXT_LOC (use))
869 df_ref def = get_def_for_use (use);
870 int regno = DF_REF_REGNO (use);
872 #ifdef ENABLE_CHECKING
873 sparseset_set_bit (active_defs_check, regno);
874 #endif
875 active_defs[regno] = def;
880 /* Build the use->def links that we use to update the dataflow info
881 for new uses. Note that building the links is very cheap and if
882 it were done earlier, they could be used to rule out invalid
883 propagations (in addition to what is done in all_uses_available_at).
884 I'm not doing this yet, though. */
886 static void
887 update_df_init (rtx_insn *def_insn, rtx_insn *insn)
889 #ifdef ENABLE_CHECKING
890 sparseset_clear (active_defs_check);
891 #endif
892 register_active_defs (DF_INSN_USES (def_insn));
893 register_active_defs (DF_INSN_USES (insn));
894 register_active_defs (DF_INSN_EQ_USES (insn));
898 /* Update the USE_DEF_REF array for the given use, using the active definitions
899 in the ACTIVE_DEFS array to match pseudos to their def. */
901 static inline void
902 update_uses (df_ref use)
904 for (; use; use = DF_REF_NEXT_LOC (use))
906 int regno = DF_REF_REGNO (use);
908 /* Set up the use-def chain. */
909 if (DF_REF_ID (use) >= (int) use_def_ref.length ())
910 use_def_ref.safe_grow_cleared (DF_REF_ID (use) + 1);
912 #ifdef ENABLE_CHECKING
913 gcc_assert (sparseset_bit_p (active_defs_check, regno));
914 #endif
915 use_def_ref[DF_REF_ID (use)] = active_defs[regno];
920 /* Update the USE_DEF_REF array for the uses in INSN. Only update note
921 uses if NOTES_ONLY is true. */
923 static void
924 update_df (rtx_insn *insn, rtx note)
926 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
928 if (note)
930 df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE);
931 df_notes_rescan (insn);
933 else
935 df_uses_create (&PATTERN (insn), insn, 0);
936 df_insn_rescan (insn);
937 update_uses (DF_INSN_INFO_USES (insn_info));
940 update_uses (DF_INSN_INFO_EQ_USES (insn_info));
944 /* Try substituting NEW into LOC, which originated from forward propagation
945 of USE's value from DEF_INSN. SET_REG_EQUAL says whether we are
946 substituting the whole SET_SRC, so we can set a REG_EQUAL note if the
947 new insn is not recognized. Return whether the substitution was
948 performed. */
950 static bool
951 try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx_insn *def_insn,
952 bool set_reg_equal)
954 rtx_insn *insn = DF_REF_INSN (use);
955 rtx set = single_set (insn);
956 rtx note = NULL_RTX;
957 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
958 int old_cost = 0;
959 bool ok;
961 update_df_init (def_insn, insn);
963 /* forward_propagate_subreg may be operating on an instruction with
964 multiple sets. If so, assume the cost of the new instruction is
965 not greater than the old one. */
966 if (set)
967 old_cost = set_src_cost (SET_SRC (set), speed);
968 if (dump_file)
970 fprintf (dump_file, "\nIn insn %d, replacing\n ", INSN_UID (insn));
971 print_inline_rtx (dump_file, *loc, 2);
972 fprintf (dump_file, "\n with ");
973 print_inline_rtx (dump_file, new_rtx, 2);
974 fprintf (dump_file, "\n");
977 validate_unshare_change (insn, loc, new_rtx, true);
978 if (!verify_changes (0))
980 if (dump_file)
981 fprintf (dump_file, "Changes to insn %d not recognized\n",
982 INSN_UID (insn));
983 ok = false;
986 else if (DF_REF_TYPE (use) == DF_REF_REG_USE
987 && set
988 && set_src_cost (SET_SRC (set), speed) > old_cost)
990 if (dump_file)
991 fprintf (dump_file, "Changes to insn %d not profitable\n",
992 INSN_UID (insn));
993 ok = false;
996 else
998 if (dump_file)
999 fprintf (dump_file, "Changed insn %d\n", INSN_UID (insn));
1000 ok = true;
1003 if (ok)
1005 confirm_change_group ();
1006 num_changes++;
1008 else
1010 cancel_changes (0);
1012 /* Can also record a simplified value in a REG_EQUAL note,
1013 making a new one if one does not already exist. */
1014 if (set_reg_equal)
1016 if (dump_file)
1017 fprintf (dump_file, " Setting REG_EQUAL note\n");
1019 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
1023 if ((ok || note) && !CONSTANT_P (new_rtx))
1024 update_df (insn, note);
1026 return ok;
1029 /* For the given single_set INSN, containing SRC known to be a
1030 ZERO_EXTEND or SIGN_EXTEND of a register, return true if INSN
1031 is redundant due to the register being set by a LOAD_EXTEND_OP
1032 load from memory. */
1034 static bool
1035 free_load_extend (rtx src, rtx_insn *insn)
1037 rtx reg;
1038 df_ref def, use;
1040 reg = XEXP (src, 0);
1041 #ifdef LOAD_EXTEND_OP
1042 if (LOAD_EXTEND_OP (GET_MODE (reg)) != GET_CODE (src))
1043 #endif
1044 return false;
1046 FOR_EACH_INSN_USE (use, insn)
1047 if (!DF_REF_IS_ARTIFICIAL (use)
1048 && DF_REF_TYPE (use) == DF_REF_REG_USE
1049 && DF_REF_REG (use) == reg)
1050 break;
1051 if (!use)
1052 return false;
1054 def = get_def_for_use (use);
1055 if (!def)
1056 return false;
1058 if (DF_REF_IS_ARTIFICIAL (def))
1059 return false;
1061 if (NONJUMP_INSN_P (DF_REF_INSN (def)))
1063 rtx patt = PATTERN (DF_REF_INSN (def));
1065 if (GET_CODE (patt) == SET
1066 && GET_CODE (SET_SRC (patt)) == MEM
1067 && rtx_equal_p (SET_DEST (patt), reg))
1068 return true;
1070 return false;
1073 /* If USE is a subreg, see if it can be replaced by a pseudo. */
1075 static bool
1076 forward_propagate_subreg (df_ref use, rtx_insn *def_insn, rtx def_set)
1078 rtx use_reg = DF_REF_REG (use);
1079 rtx_insn *use_insn;
1080 rtx src;
1082 /* Only consider subregs... */
1083 machine_mode use_mode = GET_MODE (use_reg);
1084 if (GET_CODE (use_reg) != SUBREG
1085 || !REG_P (SET_DEST (def_set)))
1086 return false;
1088 /* If this is a paradoxical SUBREG... */
1089 if (GET_MODE_SIZE (use_mode)
1090 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (use_reg))))
1092 /* If this is a paradoxical SUBREG, we have no idea what value the
1093 extra bits would have. However, if the operand is equivalent to
1094 a SUBREG whose operand is the same as our mode, and all the modes
1095 are within a word, we can just use the inner operand because
1096 these SUBREGs just say how to treat the register. */
1097 use_insn = DF_REF_INSN (use);
1098 src = SET_SRC (def_set);
1099 if (GET_CODE (src) == SUBREG
1100 && REG_P (SUBREG_REG (src))
1101 && REGNO (SUBREG_REG (src)) >= FIRST_PSEUDO_REGISTER
1102 && GET_MODE (SUBREG_REG (src)) == use_mode
1103 && subreg_lowpart_p (src)
1104 && all_uses_available_at (def_insn, use_insn))
1105 return try_fwprop_subst (use, DF_REF_LOC (use), SUBREG_REG (src),
1106 def_insn, false);
1109 /* If this is a SUBREG of a ZERO_EXTEND or SIGN_EXTEND, and the SUBREG
1110 is the low part of the reg being extended then just use the inner
1111 operand. Don't do this if the ZERO_EXTEND or SIGN_EXTEND insn will
1112 be removed due to it matching a LOAD_EXTEND_OP load from memory,
1113 or due to the operation being a no-op when applied to registers.
1114 For example, if we have:
1116 A: (set (reg:DI X) (sign_extend:DI (reg:SI Y)))
1117 B: (... (subreg:SI (reg:DI X)) ...)
1119 and mode_rep_extended says that Y is already sign-extended,
1120 the backend will typically allow A to be combined with the
1121 definition of Y or, failing that, allow A to be deleted after
1122 reload through register tying. Introducing more uses of Y
1123 prevents both optimisations. */
1124 else if (subreg_lowpart_p (use_reg))
1126 use_insn = DF_REF_INSN (use);
1127 src = SET_SRC (def_set);
1128 if ((GET_CODE (src) == ZERO_EXTEND
1129 || GET_CODE (src) == SIGN_EXTEND)
1130 && REG_P (XEXP (src, 0))
1131 && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER
1132 && GET_MODE (XEXP (src, 0)) == use_mode
1133 && !free_load_extend (src, def_insn)
1134 && (targetm.mode_rep_extended (use_mode, GET_MODE (src))
1135 != (int) GET_CODE (src))
1136 && all_uses_available_at (def_insn, use_insn))
1137 return try_fwprop_subst (use, DF_REF_LOC (use), XEXP (src, 0),
1138 def_insn, false);
1141 return false;
1144 /* Try to replace USE with SRC (defined in DEF_INSN) in __asm. */
1146 static bool
1147 forward_propagate_asm (df_ref use, rtx_insn *def_insn, rtx def_set, rtx reg)
1149 rtx_insn *use_insn = DF_REF_INSN (use);
1150 rtx src, use_pat, asm_operands, new_rtx, *loc;
1151 int speed_p, i;
1152 df_ref uses;
1154 gcc_assert ((DF_REF_FLAGS (use) & DF_REF_IN_NOTE) == 0);
1156 src = SET_SRC (def_set);
1157 use_pat = PATTERN (use_insn);
1159 /* In __asm don't replace if src might need more registers than
1160 reg, as that could increase register pressure on the __asm. */
1161 uses = DF_INSN_USES (def_insn);
1162 if (uses && DF_REF_NEXT_LOC (uses))
1163 return false;
1165 update_df_init (def_insn, use_insn);
1166 speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
1167 asm_operands = NULL_RTX;
1168 switch (GET_CODE (use_pat))
1170 case ASM_OPERANDS:
1171 asm_operands = use_pat;
1172 break;
1173 case SET:
1174 if (MEM_P (SET_DEST (use_pat)))
1176 loc = &SET_DEST (use_pat);
1177 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1178 if (new_rtx)
1179 validate_unshare_change (use_insn, loc, new_rtx, true);
1181 asm_operands = SET_SRC (use_pat);
1182 break;
1183 case PARALLEL:
1184 for (i = 0; i < XVECLEN (use_pat, 0); i++)
1185 if (GET_CODE (XVECEXP (use_pat, 0, i)) == SET)
1187 if (MEM_P (SET_DEST (XVECEXP (use_pat, 0, i))))
1189 loc = &SET_DEST (XVECEXP (use_pat, 0, i));
1190 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg,
1191 src, speed_p);
1192 if (new_rtx)
1193 validate_unshare_change (use_insn, loc, new_rtx, true);
1195 asm_operands = SET_SRC (XVECEXP (use_pat, 0, i));
1197 else if (GET_CODE (XVECEXP (use_pat, 0, i)) == ASM_OPERANDS)
1198 asm_operands = XVECEXP (use_pat, 0, i);
1199 break;
1200 default:
1201 gcc_unreachable ();
1204 gcc_assert (asm_operands && GET_CODE (asm_operands) == ASM_OPERANDS);
1205 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (asm_operands); i++)
1207 loc = &ASM_OPERANDS_INPUT (asm_operands, i);
1208 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1209 if (new_rtx)
1210 validate_unshare_change (use_insn, loc, new_rtx, true);
1213 if (num_changes_pending () == 0 || !apply_change_group ())
1214 return false;
1216 update_df (use_insn, NULL);
1217 num_changes++;
1218 return true;
1221 /* Try to replace USE with SRC (defined in DEF_INSN) and simplify the
1222 result. */
1224 static bool
1225 forward_propagate_and_simplify (df_ref use, rtx_insn *def_insn, rtx def_set)
1227 rtx_insn *use_insn = DF_REF_INSN (use);
1228 rtx use_set = single_set (use_insn);
1229 rtx src, reg, new_rtx, *loc;
1230 bool set_reg_equal;
1231 machine_mode mode;
1232 int asm_use = -1;
1234 if (INSN_CODE (use_insn) < 0)
1235 asm_use = asm_noperands (PATTERN (use_insn));
1237 if (!use_set && asm_use < 0 && !DEBUG_INSN_P (use_insn))
1238 return false;
1240 /* Do not propagate into PC, CC0, etc. */
1241 if (use_set && GET_MODE (SET_DEST (use_set)) == VOIDmode)
1242 return false;
1244 /* If def and use are subreg, check if they match. */
1245 reg = DF_REF_REG (use);
1246 if (GET_CODE (reg) == SUBREG && GET_CODE (SET_DEST (def_set)) == SUBREG)
1248 if (SUBREG_BYTE (SET_DEST (def_set)) != SUBREG_BYTE (reg))
1249 return false;
1251 /* Check if the def had a subreg, but the use has the whole reg. */
1252 else if (REG_P (reg) && GET_CODE (SET_DEST (def_set)) == SUBREG)
1253 return false;
1254 /* Check if the use has a subreg, but the def had the whole reg. Unlike the
1255 previous case, the optimization is possible and often useful indeed. */
1256 else if (GET_CODE (reg) == SUBREG && REG_P (SET_DEST (def_set)))
1257 reg = SUBREG_REG (reg);
1259 /* Make sure that we can treat REG as having the same mode as the
1260 source of DEF_SET. */
1261 if (GET_MODE (SET_DEST (def_set)) != GET_MODE (reg))
1262 return false;
1264 /* Check if the substitution is valid (last, because it's the most
1265 expensive check!). */
1266 src = SET_SRC (def_set);
1267 if (!CONSTANT_P (src) && !all_uses_available_at (def_insn, use_insn))
1268 return false;
1270 /* Check if the def is loading something from the constant pool; in this
1271 case we would undo optimization such as compress_float_constant.
1272 Still, we can set a REG_EQUAL note. */
1273 if (MEM_P (src) && MEM_READONLY_P (src))
1275 rtx x = avoid_constant_pool_reference (src);
1276 if (x != src && use_set)
1278 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1279 rtx old_rtx = note ? XEXP (note, 0) : SET_SRC (use_set);
1280 rtx new_rtx = simplify_replace_rtx (old_rtx, src, x);
1281 if (old_rtx != new_rtx)
1282 set_unique_reg_note (use_insn, REG_EQUAL, copy_rtx (new_rtx));
1284 return false;
1287 if (asm_use >= 0)
1288 return forward_propagate_asm (use, def_insn, def_set, reg);
1290 /* Else try simplifying. */
1292 if (DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE)
1294 loc = &SET_DEST (use_set);
1295 set_reg_equal = false;
1297 else if (!use_set)
1299 loc = &INSN_VAR_LOCATION_LOC (use_insn);
1300 set_reg_equal = false;
1302 else
1304 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1305 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1306 loc = &XEXP (note, 0);
1307 else
1308 loc = &SET_SRC (use_set);
1310 /* Do not replace an existing REG_EQUAL note if the insn is not
1311 recognized. Either we're already replacing in the note, or we'll
1312 separately try plugging the definition in the note and simplifying.
1313 And only install a REQ_EQUAL note when the destination is a REG
1314 that isn't mentioned in USE_SET, as the note would be invalid
1315 otherwise. We also don't want to install a note if we are merely
1316 propagating a pseudo since verifying that this pseudo isn't dead
1317 is a pain; moreover such a note won't help anything. */
1318 set_reg_equal = (note == NULL_RTX
1319 && REG_P (SET_DEST (use_set))
1320 && !REG_P (src)
1321 && !(GET_CODE (src) == SUBREG
1322 && REG_P (SUBREG_REG (src)))
1323 && !reg_mentioned_p (SET_DEST (use_set),
1324 SET_SRC (use_set)));
1327 if (GET_MODE (*loc) == VOIDmode)
1328 mode = GET_MODE (SET_DEST (use_set));
1329 else
1330 mode = GET_MODE (*loc);
1332 new_rtx = propagate_rtx (*loc, mode, reg, src,
1333 optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn)));
1335 if (!new_rtx)
1336 return false;
1338 return try_fwprop_subst (use, loc, new_rtx, def_insn, set_reg_equal);
1342 /* Given a use USE of an insn, if it has a single reaching
1343 definition, try to forward propagate it into that insn.
1344 Return true if cfg cleanup will be needed. */
1346 static bool
1347 forward_propagate_into (df_ref use)
1349 df_ref def;
1350 rtx_insn *def_insn, *use_insn;
1351 rtx def_set;
1352 rtx parent;
1354 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
1355 return false;
1356 if (DF_REF_IS_ARTIFICIAL (use))
1357 return false;
1359 /* Only consider uses that have a single definition. */
1360 def = get_def_for_use (use);
1361 if (!def)
1362 return false;
1363 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
1364 return false;
1365 if (DF_REF_IS_ARTIFICIAL (def))
1366 return false;
1368 /* Do not propagate loop invariant definitions inside the loop. */
1369 if (DF_REF_BB (def)->loop_father != DF_REF_BB (use)->loop_father)
1370 return false;
1372 /* Check if the use is still present in the insn! */
1373 use_insn = DF_REF_INSN (use);
1374 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1375 parent = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1376 else
1377 parent = PATTERN (use_insn);
1379 if (!reg_mentioned_p (DF_REF_REG (use), parent))
1380 return false;
1382 def_insn = DF_REF_INSN (def);
1383 if (multiple_sets (def_insn))
1384 return false;
1385 def_set = single_set (def_insn);
1386 if (!def_set)
1387 return false;
1389 /* Only try one kind of propagation. If two are possible, we'll
1390 do it on the following iterations. */
1391 if (forward_propagate_and_simplify (use, def_insn, def_set)
1392 || forward_propagate_subreg (use, def_insn, def_set))
1394 if (cfun->can_throw_non_call_exceptions
1395 && find_reg_note (use_insn, REG_EH_REGION, NULL_RTX)
1396 && purge_dead_edges (DF_REF_BB (use)))
1397 return true;
1399 return false;
1403 static void
1404 fwprop_init (void)
1406 num_changes = 0;
1407 calculate_dominance_info (CDI_DOMINATORS);
1409 /* We do not always want to propagate into loops, so we have to find
1410 loops and be careful about them. Avoid CFG modifications so that
1411 we don't have to update dominance information afterwards for
1412 build_single_def_use_links. */
1413 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
1415 build_single_def_use_links ();
1416 df_set_flags (DF_DEFER_INSN_RESCAN);
1418 active_defs = XNEWVEC (df_ref, max_reg_num ());
1419 #ifdef ENABLE_CHECKING
1420 active_defs_check = sparseset_alloc (max_reg_num ());
1421 #endif
1424 static void
1425 fwprop_done (void)
1427 loop_optimizer_finalize ();
1429 use_def_ref.release ();
1430 free (active_defs);
1431 #ifdef ENABLE_CHECKING
1432 sparseset_free (active_defs_check);
1433 #endif
1435 free_dominance_info (CDI_DOMINATORS);
1436 cleanup_cfg (0);
1437 delete_trivially_dead_insns (get_insns (), max_reg_num ());
1439 if (dump_file)
1440 fprintf (dump_file,
1441 "\nNumber of successful forward propagations: %d\n\n",
1442 num_changes);
1446 /* Main entry point. */
1448 static bool
1449 gate_fwprop (void)
1451 return optimize > 0 && flag_forward_propagate;
1454 static unsigned int
1455 fwprop (void)
1457 unsigned i;
1458 bool need_cleanup = false;
1460 fwprop_init ();
1462 /* Go through all the uses. df_uses_create will create new ones at the
1463 end, and we'll go through them as well.
1465 Do not forward propagate addresses into loops until after unrolling.
1466 CSE did so because it was able to fix its own mess, but we are not. */
1468 for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1470 df_ref use = DF_USES_GET (i);
1471 if (use)
1472 if (DF_REF_TYPE (use) == DF_REF_REG_USE
1473 || DF_REF_BB (use)->loop_father == NULL
1474 /* The outer most loop is not really a loop. */
1475 || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
1476 need_cleanup |= forward_propagate_into (use);
1479 fwprop_done ();
1480 if (need_cleanup)
1481 cleanup_cfg (0);
1482 return 0;
1485 namespace {
1487 const pass_data pass_data_rtl_fwprop =
1489 RTL_PASS, /* type */
1490 "fwprop1", /* name */
1491 OPTGROUP_NONE, /* optinfo_flags */
1492 TV_FWPROP, /* tv_id */
1493 0, /* properties_required */
1494 0, /* properties_provided */
1495 0, /* properties_destroyed */
1496 0, /* todo_flags_start */
1497 TODO_df_finish, /* todo_flags_finish */
1500 class pass_rtl_fwprop : public rtl_opt_pass
1502 public:
1503 pass_rtl_fwprop (gcc::context *ctxt)
1504 : rtl_opt_pass (pass_data_rtl_fwprop, ctxt)
1507 /* opt_pass methods: */
1508 virtual bool gate (function *) { return gate_fwprop (); }
1509 virtual unsigned int execute (function *) { return fwprop (); }
1511 }; // class pass_rtl_fwprop
1513 } // anon namespace
1515 rtl_opt_pass *
1516 make_pass_rtl_fwprop (gcc::context *ctxt)
1518 return new pass_rtl_fwprop (ctxt);
1521 static unsigned int
1522 fwprop_addr (void)
1524 unsigned i;
1525 bool need_cleanup = false;
1527 fwprop_init ();
1529 /* Go through all the uses. df_uses_create will create new ones at the
1530 end, and we'll go through them as well. */
1531 for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1533 df_ref use = DF_USES_GET (i);
1534 if (use)
1535 if (DF_REF_TYPE (use) != DF_REF_REG_USE
1536 && DF_REF_BB (use)->loop_father != NULL
1537 /* The outer most loop is not really a loop. */
1538 && loop_outer (DF_REF_BB (use)->loop_father) != NULL)
1539 need_cleanup |= forward_propagate_into (use);
1542 fwprop_done ();
1544 if (need_cleanup)
1545 cleanup_cfg (0);
1546 return 0;
1549 namespace {
1551 const pass_data pass_data_rtl_fwprop_addr =
1553 RTL_PASS, /* type */
1554 "fwprop2", /* name */
1555 OPTGROUP_NONE, /* optinfo_flags */
1556 TV_FWPROP, /* tv_id */
1557 0, /* properties_required */
1558 0, /* properties_provided */
1559 0, /* properties_destroyed */
1560 0, /* todo_flags_start */
1561 TODO_df_finish, /* todo_flags_finish */
1564 class pass_rtl_fwprop_addr : public rtl_opt_pass
1566 public:
1567 pass_rtl_fwprop_addr (gcc::context *ctxt)
1568 : rtl_opt_pass (pass_data_rtl_fwprop_addr, ctxt)
1571 /* opt_pass methods: */
1572 virtual bool gate (function *) { return gate_fwprop (); }
1573 virtual unsigned int execute (function *) { return fwprop_addr (); }
1575 }; // class pass_rtl_fwprop_addr
1577 } // anon namespace
1579 rtl_opt_pass *
1580 make_pass_rtl_fwprop_addr (gcc::context *ctxt)
1582 return new pass_rtl_fwprop_addr (ctxt);