OSDN Git Service

PR target/41081
[pf3gnuchains/gcc-fork.git] / gcc / fwprop.c
1 /* RTL-based forward propagation pass for GNU compiler.
2    Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
3    Contributed by Paolo Bonzini and Steven Bosscher.
4
5 This file is part of GCC.
6
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.
11
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.
16
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/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "toplev.h"
26
27 #include "timevar.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "emit-rtl.h"
31 #include "insn-config.h"
32 #include "recog.h"
33 #include "flags.h"
34 #include "obstack.h"
35 #include "basic-block.h"
36 #include "output.h"
37 #include "df.h"
38 #include "target.h"
39 #include "cfgloop.h"
40 #include "tree-pass.h"
41 #include "domwalk.h"
42
43
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.
48
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.
53
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
59
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)))
66
67    can be simplified to the much simpler
68
69       (set (subreg:SI (reg:DI 122) 0) (subreg:SI (reg:DI 119)))
70       (set (subreg:SI (reg:DI 122) 4) (const_int -1))
71
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.
77
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.
81
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.
85
86    3) The pass looks for paradoxical subregs that are actually unnecessary.
87    Things like this:
88
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)))
93
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
99
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)))
103
104    where the first two insns are now dead.
105
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.  */
115
116
117 static int num_changes;
118
119 DEF_VEC_P(df_ref);
120 DEF_VEC_ALLOC_P(df_ref,heap);
121 VEC(df_ref,heap) *use_def_ref;
122 VEC(df_ref,heap) *reg_defs;
123 VEC(df_ref,heap) *reg_defs_stack;
124
125
126 /* Return the only def in USE's use-def chain, or NULL if there is
127    more than one def in the chain.  */
128
129 static inline df_ref
130 get_def_for_use (df_ref use)
131 {
132   return VEC_index (df_ref, use_def_ref, DF_REF_ID (use));
133 }
134
135
136 /* Update the reg_defs vector with non-partial definitions in DEF_REC.
137    TOP_FLAG says which artificials uses should be used, when DEF_REC
138    is an artificial def vector.  LOCAL_MD is modified as after a
139    df_md_simulate_* function; we do more or less the same processing
140    done there, so we do not use those functions.  */
141
142 #define DF_MD_GEN_FLAGS \
143         (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
144
145 static void
146 process_defs (bitmap local_md, df_ref *def_rec, int top_flag)
147 {
148   df_ref def;
149   while ((def = *def_rec++) != NULL)
150     {
151       df_ref curr_def = VEC_index (df_ref, reg_defs, DF_REF_REGNO (def));
152       unsigned int dregno;
153
154       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag)
155         continue;
156
157       dregno = DF_REF_REGNO (def);
158       if (curr_def)
159         VEC_safe_push (df_ref, heap, reg_defs_stack, curr_def);
160       else
161         {
162           /* Do not store anything if "transitioning" from NULL to NULL.  But
163              otherwise, push a special entry on the stack to tell the
164              leave_block callback that the entry in reg_defs was NULL.  */
165           if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
166             ;
167           else
168             VEC_safe_push (df_ref, heap, reg_defs_stack, def);
169         }
170
171       if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
172         {
173           bitmap_set_bit (local_md, dregno);
174           VEC_replace (df_ref, reg_defs, dregno, NULL);
175         }
176       else
177         {
178           bitmap_clear_bit (local_md, dregno);
179           VEC_replace (df_ref, reg_defs, dregno, def);
180         }
181     }
182 }
183
184
185 /* Fill the use_def_ref vector with values for the uses in USE_REC,
186    taking reaching definitions info from LOCAL_MD and REG_DEFS.
187    TOP_FLAG says which artificials uses should be used, when USE_REC
188    is an artificial use vector.  */
189
190 static void
191 process_uses (bitmap local_md, df_ref *use_rec, int top_flag)
192 {
193   df_ref use;
194   while ((use = *use_rec++) != NULL)
195     if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag)
196       {
197         unsigned int uregno = DF_REF_REGNO (use);
198         if (VEC_index (df_ref, reg_defs, uregno)
199             && !bitmap_bit_p (local_md, uregno))
200           VEC_replace (df_ref, use_def_ref, DF_REF_ID (use),
201                        VEC_index (df_ref, reg_defs, uregno));
202       }
203 }
204
205
206 static void
207 single_def_use_enter_block (struct dom_walk_data *walk_data, basic_block bb)
208 {
209   bitmap local_md = (bitmap) walk_data->global_data;
210   int bb_index = bb->index;
211   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
212   rtx insn;
213
214   bitmap_copy (local_md, bb_info->in);
215
216   /* Push a marker for the leave_block callback.  */
217   VEC_safe_push (df_ref, heap, reg_defs_stack, NULL);
218
219   process_uses (local_md, df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
220   process_defs (local_md, df_get_artificial_defs (bb_index), DF_REF_AT_TOP);
221
222   FOR_BB_INSNS (bb, insn)
223     if (INSN_P (insn))
224       {
225         unsigned int uid = INSN_UID (insn);
226         process_uses (local_md, DF_INSN_UID_USES (uid), 0);
227         process_uses (local_md, DF_INSN_UID_EQ_USES (uid), 0);
228         process_defs (local_md, DF_INSN_UID_DEFS (uid), 0);
229       }
230
231   process_uses (local_md, df_get_artificial_uses (bb_index), 0);
232   process_defs (local_md, df_get_artificial_defs (bb_index), 0);
233 }
234
235 /* Pop the definitions created in this basic block when leaving its
236    dominated parts.  */
237
238 static void
239 single_def_use_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
240                             basic_block bb ATTRIBUTE_UNUSED)
241 {
242   df_ref saved_def;
243   while ((saved_def = VEC_pop (df_ref, reg_defs_stack)) != NULL)
244     {
245       unsigned int dregno = DF_REF_REGNO (saved_def);
246
247       /* See also process_defs.  */
248       if (saved_def == VEC_index (df_ref, reg_defs, dregno))
249         VEC_replace (df_ref, reg_defs, dregno, NULL);
250       else
251         VEC_replace (df_ref, reg_defs, dregno, saved_def);
252     }
253 }
254
255
256 /* Build a vector holding the reaching definitions of uses reached by a
257    single dominating definition.  */
258
259 static void
260 build_single_def_use_links (void)
261 {
262   struct dom_walk_data walk_data;
263   bitmap local_md;
264
265   /* We use the multiple definitions problem to compute our restricted
266      use-def chains.  */
267   df_set_flags (DF_EQ_NOTES);
268   df_md_add_problem ();
269   df_analyze ();
270   df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
271
272   use_def_ref = VEC_alloc (df_ref, heap, DF_USES_TABLE_SIZE ());
273   VEC_safe_grow_cleared (df_ref, heap, use_def_ref, DF_USES_TABLE_SIZE ());
274
275   reg_defs = VEC_alloc (df_ref, heap, max_reg_num ());
276   VEC_safe_grow_cleared (df_ref, heap, reg_defs, max_reg_num ());
277
278   reg_defs_stack = VEC_alloc (df_ref, heap, n_basic_blocks * 10);
279   local_md = BITMAP_ALLOC (NULL);
280
281   /* Walk the dominator tree looking for single reaching definitions
282      dominating the uses.  This is similar to how SSA form is built.  */
283   walk_data.dom_direction = CDI_DOMINATORS;
284   walk_data.initialize_block_local_data = NULL;
285   walk_data.before_dom_children = single_def_use_enter_block;
286   walk_data.after_dom_children = single_def_use_leave_block;
287   walk_data.global_data = local_md;
288
289   init_walk_dominator_tree (&walk_data);
290   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
291   fini_walk_dominator_tree (&walk_data);
292
293   BITMAP_FREE (local_md);
294   VEC_free (df_ref, heap, reg_defs);
295   VEC_free (df_ref, heap, reg_defs_stack);
296 }
297
298 \f
299 /* Do not try to replace constant addresses or addresses of local and
300    argument slots.  These MEM expressions are made only once and inserted
301    in many instructions, as well as being used to control symbol table
302    output.  It is not safe to clobber them.
303
304    There are some uncommon cases where the address is already in a register
305    for some reason, but we cannot take advantage of that because we have
306    no easy way to unshare the MEM.  In addition, looking up all stack
307    addresses is costly.  */
308
309 static bool
310 can_simplify_addr (rtx addr)
311 {
312   rtx reg;
313
314   if (CONSTANT_ADDRESS_P (addr))
315     return false;
316
317   if (GET_CODE (addr) == PLUS)
318     reg = XEXP (addr, 0);
319   else
320     reg = addr;
321
322   return (!REG_P (reg)
323           || (REGNO (reg) != FRAME_POINTER_REGNUM
324               && REGNO (reg) != HARD_FRAME_POINTER_REGNUM
325               && REGNO (reg) != ARG_POINTER_REGNUM));
326 }
327
328 /* Returns a canonical version of X for the address, from the point of view,
329    that all multiplications are represented as MULT instead of the multiply
330    by a power of 2 being represented as ASHIFT.
331
332    Every ASHIFT we find has been made by simplify_gen_binary and was not
333    there before, so it is not shared.  So we can do this in place.  */
334
335 static void
336 canonicalize_address (rtx x)
337 {
338   for (;;)
339     switch (GET_CODE (x))
340       {
341       case ASHIFT:
342         if (CONST_INT_P (XEXP (x, 1))
343             && INTVAL (XEXP (x, 1)) < GET_MODE_BITSIZE (GET_MODE (x))
344             && INTVAL (XEXP (x, 1)) >= 0)
345           {
346             HOST_WIDE_INT shift = INTVAL (XEXP (x, 1));
347             PUT_CODE (x, MULT);
348             XEXP (x, 1) = gen_int_mode ((HOST_WIDE_INT) 1 << shift,
349                                         GET_MODE (x));
350           }
351
352         x = XEXP (x, 0);
353         break;
354
355       case PLUS:
356         if (GET_CODE (XEXP (x, 0)) == PLUS
357             || GET_CODE (XEXP (x, 0)) == ASHIFT
358             || GET_CODE (XEXP (x, 0)) == CONST)
359           canonicalize_address (XEXP (x, 0));
360
361         x = XEXP (x, 1);
362         break;
363
364       case CONST:
365         x = XEXP (x, 0);
366         break;
367
368       default:
369         return;
370       }
371 }
372
373 /* OLD is a memory address.  Return whether it is good to use NEW instead,
374    for a memory access in the given MODE.  */
375
376 static bool
377 should_replace_address (rtx old_rtx, rtx new_rtx, enum machine_mode mode,
378                         bool speed)
379 {
380   int gain;
381
382   if (rtx_equal_p (old_rtx, new_rtx) || !memory_address_p (mode, new_rtx))
383     return false;
384
385   /* Copy propagation is always ok.  */
386   if (REG_P (old_rtx) && REG_P (new_rtx))
387     return true;
388
389   /* Prefer the new address if it is less expensive.  */
390   gain = address_cost (old_rtx, mode, speed) - address_cost (new_rtx, mode, speed);
391
392   /* If the addresses have equivalent cost, prefer the new address
393      if it has the highest `rtx_cost'.  That has the potential of
394      eliminating the most insns without additional costs, and it
395      is the same that cse.c used to do.  */
396   if (gain == 0)
397     gain = rtx_cost (new_rtx, SET, speed) - rtx_cost (old_rtx, SET, speed);
398
399   return (gain > 0);
400 }
401
402
403 /* Flags for the last parameter of propagate_rtx_1.  */
404
405 enum {
406   /* If PR_CAN_APPEAR is true, propagate_rtx_1 always returns true;
407      if it is false, propagate_rtx_1 returns false if, for at least
408      one occurrence OLD, it failed to collapse the result to a constant.
409      For example, (mult:M (reg:M A) (minus:M (reg:M B) (reg:M A))) may
410      collapse to zero if replacing (reg:M B) with (reg:M A).
411
412      PR_CAN_APPEAR is disregarded inside MEMs: in that case,
413      propagate_rtx_1 just tries to make cheaper and valid memory
414      addresses.  */
415   PR_CAN_APPEAR = 1,
416
417   /* If PR_HANDLE_MEM is not set, propagate_rtx_1 won't attempt any replacement
418      outside memory addresses.  This is needed because propagate_rtx_1 does
419      not do any analysis on memory; thus it is very conservative and in general
420      it will fail if non-read-only MEMs are found in the source expression.
421
422      PR_HANDLE_MEM is set when the source of the propagation was not
423      another MEM.  Then, it is safe not to treat non-read-only MEMs as
424      ``opaque'' objects.  */
425   PR_HANDLE_MEM = 2,
426
427   /* Set when costs should be optimized for speed.  */
428   PR_OPTIMIZE_FOR_SPEED = 4
429 };
430
431
432 /* Replace all occurrences of OLD in *PX with NEW and try to simplify the
433    resulting expression.  Replace *PX with a new RTL expression if an
434    occurrence of OLD was found.
435
436    This is only a wrapper around simplify-rtx.c: do not add any pattern
437    matching code here.  (The sole exception is the handling of LO_SUM, but
438    that is because there is no simplify_gen_* function for LO_SUM).  */
439
440 static bool
441 propagate_rtx_1 (rtx *px, rtx old_rtx, rtx new_rtx, int flags)
442 {
443   rtx x = *px, tem = NULL_RTX, op0, op1, op2;
444   enum rtx_code code = GET_CODE (x);
445   enum machine_mode mode = GET_MODE (x);
446   enum machine_mode op_mode;
447   bool can_appear = (flags & PR_CAN_APPEAR) != 0;
448   bool valid_ops = true;
449
450   if (!(flags & PR_HANDLE_MEM) && MEM_P (x) && !MEM_READONLY_P (x))
451     {
452       /* If unsafe, change MEMs to CLOBBERs or SCRATCHes (to preserve whether
453          they have side effects or not).  */
454       *px = (side_effects_p (x)
455              ? gen_rtx_CLOBBER (GET_MODE (x), const0_rtx)
456              : gen_rtx_SCRATCH (GET_MODE (x)));
457       return false;
458     }
459
460   /* If X is OLD_RTX, return NEW_RTX.  But not if replacing only within an
461      address, and we are *not* inside one.  */
462   if (x == old_rtx)
463     {
464       *px = new_rtx;
465       return can_appear;
466     }
467
468   /* If this is an expression, try recursive substitution.  */
469   switch (GET_RTX_CLASS (code))
470     {
471     case RTX_UNARY:
472       op0 = XEXP (x, 0);
473       op_mode = GET_MODE (op0);
474       valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
475       if (op0 == XEXP (x, 0))
476         return true;
477       tem = simplify_gen_unary (code, mode, op0, op_mode);
478       break;
479
480     case RTX_BIN_ARITH:
481     case RTX_COMM_ARITH:
482       op0 = XEXP (x, 0);
483       op1 = XEXP (x, 1);
484       valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
485       valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
486       if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
487         return true;
488       tem = simplify_gen_binary (code, mode, op0, op1);
489       break;
490
491     case RTX_COMPARE:
492     case RTX_COMM_COMPARE:
493       op0 = XEXP (x, 0);
494       op1 = XEXP (x, 1);
495       op_mode = GET_MODE (op0) != VOIDmode ? GET_MODE (op0) : GET_MODE (op1);
496       valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
497       valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
498       if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
499         return true;
500       tem = simplify_gen_relational (code, mode, op_mode, op0, op1);
501       break;
502
503     case RTX_TERNARY:
504     case RTX_BITFIELD_OPS:
505       op0 = XEXP (x, 0);
506       op1 = XEXP (x, 1);
507       op2 = XEXP (x, 2);
508       op_mode = GET_MODE (op0);
509       valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
510       valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
511       valid_ops &= propagate_rtx_1 (&op2, old_rtx, new_rtx, flags);
512       if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1) && op2 == XEXP (x, 2))
513         return true;
514       if (op_mode == VOIDmode)
515         op_mode = GET_MODE (op0);
516       tem = simplify_gen_ternary (code, mode, op_mode, op0, op1, op2);
517       break;
518
519     case RTX_EXTRA:
520       /* The only case we try to handle is a SUBREG.  */
521       if (code == SUBREG)
522         {
523           op0 = XEXP (x, 0);
524           valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
525           if (op0 == XEXP (x, 0))
526             return true;
527           tem = simplify_gen_subreg (mode, op0, GET_MODE (SUBREG_REG (x)),
528                                      SUBREG_BYTE (x));
529         }
530       break;
531
532     case RTX_OBJ:
533       if (code == MEM && x != new_rtx)
534         {
535           rtx new_op0;
536           op0 = XEXP (x, 0);
537
538           /* There are some addresses that we cannot work on.  */
539           if (!can_simplify_addr (op0))
540             return true;
541
542           op0 = new_op0 = targetm.delegitimize_address (op0);
543           valid_ops &= propagate_rtx_1 (&new_op0, old_rtx, new_rtx,
544                                         flags | PR_CAN_APPEAR);
545
546           /* Dismiss transformation that we do not want to carry on.  */
547           if (!valid_ops
548               || new_op0 == op0
549               || !(GET_MODE (new_op0) == GET_MODE (op0)
550                    || GET_MODE (new_op0) == VOIDmode))
551             return true;
552
553           canonicalize_address (new_op0);
554
555           /* Copy propagations are always ok.  Otherwise check the costs.  */
556           if (!(REG_P (old_rtx) && REG_P (new_rtx))
557               && !should_replace_address (op0, new_op0, GET_MODE (x),
558                                           flags & PR_OPTIMIZE_FOR_SPEED))
559             return true;
560
561           tem = replace_equiv_address_nv (x, new_op0);
562         }
563
564       else if (code == LO_SUM)
565         {
566           op0 = XEXP (x, 0);
567           op1 = XEXP (x, 1);
568
569           /* The only simplification we do attempts to remove references to op0
570              or make it constant -- in both cases, op0's invalidity will not
571              make the result invalid.  */
572           propagate_rtx_1 (&op0, old_rtx, new_rtx, flags | PR_CAN_APPEAR);
573           valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
574           if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
575             return true;
576
577           /* (lo_sum (high x) x) -> x  */
578           if (GET_CODE (op0) == HIGH && rtx_equal_p (XEXP (op0, 0), op1))
579             tem = op1;
580           else
581             tem = gen_rtx_LO_SUM (mode, op0, op1);
582
583           /* OP1 is likely not a legitimate address, otherwise there would have
584              been no LO_SUM.  We want it to disappear if it is invalid, return
585              false in that case.  */
586           return memory_address_p (mode, tem);
587         }
588
589       else if (code == REG)
590         {
591           if (rtx_equal_p (x, old_rtx))
592             {
593               *px = new_rtx;
594               return can_appear;
595             }
596         }
597       break;
598
599     default:
600       break;
601     }
602
603   /* No change, no trouble.  */
604   if (tem == NULL_RTX)
605     return true;
606
607   *px = tem;
608
609   /* The replacement we made so far is valid, if all of the recursive
610      replacements were valid, or we could simplify everything to
611      a constant.  */
612   return valid_ops || can_appear || CONSTANT_P (tem);
613 }
614
615
616 /* for_each_rtx traversal function that returns 1 if BODY points to
617    a non-constant mem.  */
618
619 static int
620 varying_mem_p (rtx *body, void *data ATTRIBUTE_UNUSED)
621 {
622   rtx x = *body;
623   return MEM_P (x) && !MEM_READONLY_P (x);
624 }
625
626
627 /* Replace all occurrences of OLD in X with NEW and try to simplify the
628    resulting expression (in mode MODE).  Return a new expression if it is
629    a constant, otherwise X.
630
631    Simplifications where occurrences of NEW collapse to a constant are always
632    accepted.  All simplifications are accepted if NEW is a pseudo too.
633    Otherwise, we accept simplifications that have a lower or equal cost.  */
634
635 static rtx
636 propagate_rtx (rtx x, enum machine_mode mode, rtx old_rtx, rtx new_rtx,
637                bool speed)
638 {
639   rtx tem;
640   bool collapsed;
641   int flags;
642
643   if (REG_P (new_rtx) && REGNO (new_rtx) < FIRST_PSEUDO_REGISTER)
644     return NULL_RTX;
645
646   flags = 0;
647   if (REG_P (new_rtx) || CONSTANT_P (new_rtx))
648     flags |= PR_CAN_APPEAR;
649   if (!for_each_rtx (&new_rtx, varying_mem_p, NULL))
650     flags |= PR_HANDLE_MEM;
651
652   if (speed)
653     flags |= PR_OPTIMIZE_FOR_SPEED;
654
655   tem = x;
656   collapsed = propagate_rtx_1 (&tem, old_rtx, copy_rtx (new_rtx), flags);
657   if (tem == x || !collapsed)
658     return NULL_RTX;
659
660   /* gen_lowpart_common will not be able to process VOIDmode entities other
661      than CONST_INTs.  */
662   if (GET_MODE (tem) == VOIDmode && !CONST_INT_P (tem))
663     return NULL_RTX;
664
665   if (GET_MODE (tem) == VOIDmode)
666     tem = rtl_hooks.gen_lowpart_no_emit (mode, tem);
667   else
668     gcc_assert (GET_MODE (tem) == mode);
669
670   return tem;
671 }
672
673
674 \f
675
676 /* Return true if the register from reference REF is killed
677    between FROM to (but not including) TO.  */
678
679 static bool
680 local_ref_killed_between_p (df_ref ref, rtx from, rtx to)
681 {
682   rtx insn;
683
684   for (insn = from; insn != to; insn = NEXT_INSN (insn))
685     {
686       df_ref *def_rec;
687       if (!INSN_P (insn))
688         continue;
689
690       for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
691         {
692           df_ref def = *def_rec;
693           if (DF_REF_REGNO (ref) == DF_REF_REGNO (def))
694             return true;
695         }
696     }
697   return false;
698 }
699
700
701 /* Check if the given DEF is available in INSN.  This would require full
702    computation of available expressions; we check only restricted conditions:
703    - if DEF is the sole definition of its register, go ahead;
704    - in the same basic block, we check for no definitions killing the
705      definition of DEF_INSN;
706    - if USE's basic block has DEF's basic block as the sole predecessor,
707      we check if the definition is killed after DEF_INSN or before
708      TARGET_INSN insn, in their respective basic blocks.  */
709 static bool
710 use_killed_between (df_ref use, rtx def_insn, rtx target_insn)
711 {
712   basic_block def_bb = BLOCK_FOR_INSN (def_insn);
713   basic_block target_bb = BLOCK_FOR_INSN (target_insn);
714   int regno;
715   df_ref def;
716
717   /* We used to have a def reaching a use that is _before_ the def,
718      with the def not dominating the use even though the use and def
719      are in the same basic block, when a register may be used
720      uninitialized in a loop.  This should not happen anymore since
721      we do not use reaching definitions, but still we test for such
722      cases and assume that DEF is not available.  */
723   if (def_bb == target_bb
724       ? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn)
725       : !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb))
726     return true;
727
728   /* Check if the reg in USE has only one definition.  We already
729      know that this definition reaches use, or we wouldn't be here.
730      However, this is invalid for hard registers because if they are
731      live at the beginning of the function it does not mean that we
732      have an uninitialized access.  */
733   regno = DF_REF_REGNO (use);
734   def = DF_REG_DEF_CHAIN (regno);
735   if (def
736       && DF_REF_NEXT_REG (def) == NULL
737       && regno >= FIRST_PSEUDO_REGISTER)
738     return false;
739
740   /* Check locally if we are in the same basic block.  */
741   if (def_bb == target_bb)
742     return local_ref_killed_between_p (use, def_insn, target_insn);
743
744   /* Finally, if DEF_BB is the sole predecessor of TARGET_BB.  */
745   if (single_pred_p (target_bb)
746       && single_pred (target_bb) == def_bb)
747     {
748       df_ref x;
749
750       /* See if USE is killed between DEF_INSN and the last insn in the
751          basic block containing DEF_INSN.  */
752       x = df_bb_regno_last_def_find (def_bb, regno);
753       if (x && DF_INSN_LUID (DF_REF_INSN (x)) >= DF_INSN_LUID (def_insn))
754         return true;
755
756       /* See if USE is killed between TARGET_INSN and the first insn in the
757          basic block containing TARGET_INSN.  */
758       x = df_bb_regno_first_def_find (target_bb, regno);
759       if (x && DF_INSN_LUID (DF_REF_INSN (x)) < DF_INSN_LUID (target_insn))
760         return true;
761
762       return false;
763     }
764
765   /* Otherwise assume the worst case.  */
766   return true;
767 }
768
769
770 /* Check if all uses in DEF_INSN can be used in TARGET_INSN.  This
771    would require full computation of available expressions;
772    we check only restricted conditions, see use_killed_between.  */
773 static bool
774 all_uses_available_at (rtx def_insn, rtx target_insn)
775 {
776   df_ref *use_rec;
777   struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
778   rtx def_set = single_set (def_insn);
779
780   gcc_assert (def_set);
781
782   /* If target_insn comes right after def_insn, which is very common
783      for addresses, we can use a quicker test.  */
784   if (NEXT_INSN (def_insn) == target_insn
785       && REG_P (SET_DEST (def_set)))
786     {
787       rtx def_reg = SET_DEST (def_set);
788
789       /* If the insn uses the reg that it defines, the substitution is
790          invalid.  */
791       for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
792         {
793           df_ref use = *use_rec;
794           if (rtx_equal_p (DF_REF_REG (use), def_reg))
795             return false;
796         }
797       for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
798         {
799           df_ref use = *use_rec;
800           if (rtx_equal_p (DF_REF_REG (use), def_reg))
801             return false;
802         }
803     }
804   else
805     {
806       /* Look at all the uses of DEF_INSN, and see if they are not
807          killed between DEF_INSN and TARGET_INSN.  */
808       for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
809         {
810           df_ref use = *use_rec;
811           if (use_killed_between (use, def_insn, target_insn))
812             return false;
813         }
814       for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
815         {
816           df_ref use = *use_rec;
817           if (use_killed_between (use, def_insn, target_insn))
818             return false;
819         }
820     }
821
822   return true;
823 }
824
825 \f
826 struct find_occurrence_data
827 {
828   rtx find;
829   rtx *retval;
830 };
831
832 /* Callback for for_each_rtx, used in find_occurrence.
833    See if PX is the rtx we have to find.  Return 1 to stop for_each_rtx
834    if successful, or 0 to continue traversing otherwise.  */
835
836 static int
837 find_occurrence_callback (rtx *px, void *data)
838 {
839   struct find_occurrence_data *fod = (struct find_occurrence_data *) data;
840   rtx x = *px;
841   rtx find = fod->find;
842
843   if (x == find)
844     {
845       fod->retval = px;
846       return 1;
847     }
848
849   return 0;
850 }
851
852 /* Return a pointer to one of the occurrences of register FIND in *PX.  */
853
854 static rtx *
855 find_occurrence (rtx *px, rtx find)
856 {
857   struct find_occurrence_data data;
858
859   gcc_assert (REG_P (find)
860               || (GET_CODE (find) == SUBREG
861                   && REG_P (SUBREG_REG (find))));
862
863   data.find = find;
864   data.retval = NULL;
865   for_each_rtx (px, find_occurrence_callback, &data);
866   return data.retval;
867 }
868
869 \f
870 /* Inside INSN, the expression rooted at *LOC has been changed, moving some
871    uses from USE_VEC.  Find those that are present, and create new items
872    in the data flow object of the pass.  Mark any new uses as having the
873    given TYPE.  */
874 static void
875 update_df (rtx insn, rtx *loc, df_ref *use_rec, enum df_ref_type type,
876            int new_flags)
877 {
878   bool changed = false;
879
880   /* Add a use for the registers that were propagated.  */
881   while (*use_rec)
882     {
883       df_ref use = *use_rec;
884       df_ref orig_use = use, new_use;
885       int width = -1;
886       int offset = -1;
887       enum machine_mode mode = VOIDmode;
888       rtx *new_loc = find_occurrence (loc, DF_REF_REG (orig_use));
889       use_rec++;
890
891       if (!new_loc)
892         continue;
893
894       if (DF_REF_FLAGS_IS_SET (orig_use, DF_REF_SIGN_EXTRACT | DF_REF_ZERO_EXTRACT))
895         {
896           width = DF_REF_EXTRACT_WIDTH (orig_use);
897           offset = DF_REF_EXTRACT_OFFSET (orig_use);
898           mode = DF_REF_EXTRACT_MODE (orig_use);
899         }
900
901       /* Add a new insn use.  Use the original type, because it says if the
902          use was within a MEM.  */
903       new_use = df_ref_create (DF_REF_REG (orig_use), new_loc,
904                                insn, BLOCK_FOR_INSN (insn),
905                                type, DF_REF_FLAGS (orig_use) | new_flags, 
906                                width, offset, mode);
907
908       /* Set up the use-def chain.  */
909       gcc_assert (DF_REF_ID (new_use) == (int) VEC_length (df_ref, use_def_ref));
910       VEC_safe_push (df_ref, heap, use_def_ref, get_def_for_use (orig_use));
911       changed = true;
912     }
913   if (changed)
914     df_insn_rescan (insn);
915 }
916
917
918 /* Try substituting NEW into LOC, which originated from forward propagation
919    of USE's value from DEF_INSN.  SET_REG_EQUAL says whether we are
920    substituting the whole SET_SRC, so we can set a REG_EQUAL note if the
921    new insn is not recognized.  Return whether the substitution was
922    performed.  */
923
924 static bool
925 try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx def_insn, bool set_reg_equal)
926 {
927   rtx insn = DF_REF_INSN (use);
928   enum df_ref_type type = DF_REF_TYPE (use);
929   int flags = DF_REF_FLAGS (use);
930   rtx set = single_set (insn);
931   bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
932   int old_cost = 0;
933   bool ok;
934
935   /* forward_propagate_subreg may be operating on an instruction with
936      multiple sets.  If so, assume the cost of the new instruction is
937      not greater than the old one.  */
938   if (set)
939     old_cost = rtx_cost (SET_SRC (set), SET, speed);
940   if (dump_file)
941     {
942       fprintf (dump_file, "\nIn insn %d, replacing\n ", INSN_UID (insn));
943       print_inline_rtx (dump_file, *loc, 2);
944       fprintf (dump_file, "\n with ");
945       print_inline_rtx (dump_file, new_rtx, 2);
946       fprintf (dump_file, "\n");
947     }
948
949   validate_unshare_change (insn, loc, new_rtx, true);
950   if (!verify_changes (0))
951     {
952       if (dump_file)
953         fprintf (dump_file, "Changes to insn %d not recognized\n",
954                  INSN_UID (insn));
955       ok = false;
956     }
957
958   else if (DF_REF_TYPE (use) == DF_REF_REG_USE
959            && set
960            && rtx_cost (SET_SRC (set), SET, speed) > old_cost)
961     {
962       if (dump_file)
963         fprintf (dump_file, "Changes to insn %d not profitable\n",
964                  INSN_UID (insn));
965       ok = false;
966     }
967
968   else
969     {
970       if (dump_file)
971         fprintf (dump_file, "Changed insn %d\n", INSN_UID (insn));
972       ok = true;
973     }
974
975   if (ok)
976     {
977       confirm_change_group ();
978       num_changes++;
979
980       df_ref_remove (use);
981       if (!CONSTANT_P (new_rtx))
982         {
983           struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
984           update_df (insn, loc, DF_INSN_INFO_USES (insn_info), type, flags);
985           update_df (insn, loc, DF_INSN_INFO_EQ_USES (insn_info), type, flags);
986         }
987     }
988   else
989     {
990       cancel_changes (0);
991
992       /* Can also record a simplified value in a REG_EQUAL note,
993          making a new one if one does not already exist.  */
994       if (set_reg_equal)
995         {
996           if (dump_file)
997             fprintf (dump_file, " Setting REG_EQUAL note\n");
998
999           set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
1000
1001           /* ??? Is this still necessary if we add the note through
1002              set_unique_reg_note?  */
1003           if (!CONSTANT_P (new_rtx))
1004             {
1005               struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
1006               update_df (insn, loc, DF_INSN_INFO_USES (insn_info),
1007                          type, DF_REF_IN_NOTE);
1008               update_df (insn, loc, DF_INSN_INFO_EQ_USES (insn_info),
1009                          type, DF_REF_IN_NOTE);
1010             }
1011         }
1012     }
1013
1014   return ok;
1015 }
1016
1017 #ifdef LOAD_EXTEND_OP
1018 static df_ref
1019 get_reg_use_in (rtx insn, rtx reg)
1020 {
1021   df_ref *use_vec;
1022
1023   for (use_vec = DF_INSN_USES (insn); *use_vec; use_vec++)
1024     {
1025       df_ref use = *use_vec;
1026
1027       if (!DF_REF_IS_ARTIFICIAL (use)
1028           && DF_REF_TYPE (use) == DF_REF_REG_USE
1029           && DF_REF_REG (use) == reg)
1030         return use;
1031     }
1032   return NULL;
1033 }
1034 #endif
1035
1036 /* If USE is a subreg, see if it can be replaced by a pseudo.  */
1037
1038 static bool
1039 forward_propagate_subreg (df_ref use, rtx def_insn, rtx def_set)
1040 {
1041   rtx use_reg = DF_REF_REG (use);
1042   rtx use_insn, src;
1043
1044   /* Only consider subregs... */
1045   enum machine_mode use_mode = GET_MODE (use_reg);
1046   if (GET_CODE (use_reg) != SUBREG
1047       || !REG_P (SET_DEST (def_set)))
1048     return false;
1049
1050   /* If this is a paradoxical SUBREG...  */
1051   if (GET_MODE_SIZE (use_mode)
1052       > GET_MODE_SIZE (GET_MODE (SUBREG_REG (use_reg))))
1053     {
1054       /* If this is a paradoxical SUBREG, we have no idea what value the
1055          extra bits would have.  However, if the operand is equivalent to
1056          a SUBREG whose operand is the same as our mode, and all the modes
1057          are within a word, we can just use the inner operand because
1058          these SUBREGs just say how to treat the register.  */
1059       use_insn = DF_REF_INSN (use);
1060       src = SET_SRC (def_set);
1061       if (GET_CODE (src) == SUBREG
1062           && REG_P (SUBREG_REG (src))
1063           && GET_MODE (SUBREG_REG (src)) == use_mode
1064           && subreg_lowpart_p (src)
1065           && all_uses_available_at (def_insn, use_insn))
1066         return try_fwprop_subst (use, DF_REF_LOC (use), SUBREG_REG (src),
1067                                  def_insn, false);
1068     }
1069
1070   /* If this is a SUBREG of a ZERO_EXTEND or SIGN_EXTEND, and the SUBREG
1071      is the low part of the reg being extended then just use the inner
1072      operand.  Don't do this if the ZERO_EXTEND or SIGN_EXTEND insn will
1073      be removed due to it matching a LOAD_EXTEND_OP load from memory.  */
1074   else if (subreg_lowpart_p (use_reg))
1075     {
1076 #ifdef LOAD_EXTEND_OP
1077       df_ref prev_use, prev_def;
1078 #endif
1079       use_insn = DF_REF_INSN (use);
1080       src = SET_SRC (def_set);
1081       if ((GET_CODE (src) == ZERO_EXTEND
1082            || GET_CODE (src) == SIGN_EXTEND)
1083           && REG_P (XEXP (src, 0))
1084           && GET_MODE (XEXP (src, 0)) == use_mode
1085 #ifdef LOAD_EXTEND_OP
1086           && !(LOAD_EXTEND_OP (use_mode) == GET_CODE (src)
1087                && (prev_use = get_reg_use_in (def_insn, XEXP (src, 0))) != NULL
1088                && (prev_def = get_def_for_use (prev_use)) != NULL
1089                && !DF_REF_IS_ARTIFICIAL (prev_def)
1090                && NONJUMP_INSN_P (DF_REF_INSN (prev_def))
1091                && GET_CODE (PATTERN (DF_REF_INSN (prev_def))) == SET
1092                && GET_CODE (SET_SRC (PATTERN (DF_REF_INSN (prev_def)))) == MEM
1093                && rtx_equal_p (SET_DEST (PATTERN (DF_REF_INSN (prev_def))),
1094                                XEXP (src, 0)))
1095 #endif
1096           && all_uses_available_at (def_insn, use_insn))
1097         return try_fwprop_subst (use, DF_REF_LOC (use), XEXP (src, 0),
1098                                  def_insn, false);
1099     }
1100
1101   return false;
1102 }
1103
1104 /* Try to replace USE with SRC (defined in DEF_INSN) in __asm.  */
1105
1106 static bool
1107 forward_propagate_asm (df_ref use, rtx def_insn, rtx def_set, rtx reg)
1108 {
1109   rtx use_insn = DF_REF_INSN (use), src, use_pat, asm_operands, new_rtx, *loc;
1110   int speed_p, i;
1111   df_ref *use_vec;
1112
1113   gcc_assert ((DF_REF_FLAGS (use) & DF_REF_IN_NOTE) == 0);
1114
1115   src = SET_SRC (def_set);
1116   use_pat = PATTERN (use_insn);
1117
1118   /* In __asm don't replace if src might need more registers than
1119      reg, as that could increase register pressure on the __asm.  */
1120   use_vec = DF_INSN_USES (def_insn);
1121   if (use_vec[0] && use_vec[1])
1122     return false;
1123
1124   speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
1125   asm_operands = NULL_RTX;
1126   switch (GET_CODE (use_pat))
1127     {
1128     case ASM_OPERANDS:
1129       asm_operands = use_pat;
1130       break;
1131     case SET:
1132       if (MEM_P (SET_DEST (use_pat)))
1133         {
1134           loc = &SET_DEST (use_pat);
1135           new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1136           if (new_rtx)
1137             validate_unshare_change (use_insn, loc, new_rtx, true);
1138         }
1139       asm_operands = SET_SRC (use_pat);
1140       break;
1141     case PARALLEL:
1142       for (i = 0; i < XVECLEN (use_pat, 0); i++)
1143         if (GET_CODE (XVECEXP (use_pat, 0, i)) == SET)
1144           {
1145             if (MEM_P (SET_DEST (XVECEXP (use_pat, 0, i))))
1146               {
1147                 loc = &SET_DEST (XVECEXP (use_pat, 0, i));
1148                 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg,
1149                                          src, speed_p);
1150                 if (new_rtx)
1151                   validate_unshare_change (use_insn, loc, new_rtx, true);
1152               }
1153             asm_operands = SET_SRC (XVECEXP (use_pat, 0, i));
1154           }
1155         else if (GET_CODE (XVECEXP (use_pat, 0, i)) == ASM_OPERANDS)
1156           asm_operands = XVECEXP (use_pat, 0, i);
1157       break;
1158     default:
1159       gcc_unreachable ();
1160     }
1161
1162   gcc_assert (asm_operands && GET_CODE (asm_operands) == ASM_OPERANDS);
1163   for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (asm_operands); i++)
1164     {
1165       loc = &ASM_OPERANDS_INPUT (asm_operands, i);
1166       new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1167       if (new_rtx)
1168         validate_unshare_change (use_insn, loc, new_rtx, true);
1169     }
1170
1171   if (num_changes_pending () == 0 || !apply_change_group ())
1172     return false;
1173
1174   num_changes++;
1175   return true;
1176 }
1177
1178 /* Try to replace USE with SRC (defined in DEF_INSN) and simplify the
1179    result.  */
1180
1181 static bool
1182 forward_propagate_and_simplify (df_ref use, rtx def_insn, rtx def_set)
1183 {
1184   rtx use_insn = DF_REF_INSN (use);
1185   rtx use_set = single_set (use_insn);
1186   rtx src, reg, new_rtx, *loc;
1187   bool set_reg_equal;
1188   enum machine_mode mode;
1189   int asm_use = -1;
1190
1191   if (INSN_CODE (use_insn) < 0)
1192     asm_use = asm_noperands (PATTERN (use_insn));
1193
1194   if (!use_set && asm_use < 0)
1195     return false;
1196
1197   /* Do not propagate into PC, CC0, etc.  */
1198   if (use_set && GET_MODE (SET_DEST (use_set)) == VOIDmode)
1199     return false;
1200
1201   /* If def and use are subreg, check if they match.  */
1202   reg = DF_REF_REG (use);
1203   if (GET_CODE (reg) == SUBREG
1204       && GET_CODE (SET_DEST (def_set)) == SUBREG
1205       && (SUBREG_BYTE (SET_DEST (def_set)) != SUBREG_BYTE (reg)
1206           || GET_MODE (SET_DEST (def_set)) != GET_MODE (reg)))
1207     return false;
1208
1209   /* Check if the def had a subreg, but the use has the whole reg.  */
1210   if (REG_P (reg) && GET_CODE (SET_DEST (def_set)) == SUBREG)
1211     return false;
1212
1213   /* Check if the use has a subreg, but the def had the whole reg.  Unlike the
1214      previous case, the optimization is possible and often useful indeed.  */
1215   if (GET_CODE (reg) == SUBREG && REG_P (SET_DEST (def_set)))
1216     reg = SUBREG_REG (reg);
1217
1218   /* Check if the substitution is valid (last, because it's the most
1219      expensive check!).  */
1220   src = SET_SRC (def_set);
1221   if (!CONSTANT_P (src) && !all_uses_available_at (def_insn, use_insn))
1222     return false;
1223
1224   /* Check if the def is loading something from the constant pool; in this
1225      case we would undo optimization such as compress_float_constant.
1226      Still, we can set a REG_EQUAL note.  */
1227   if (MEM_P (src) && MEM_READONLY_P (src))
1228     {
1229       rtx x = avoid_constant_pool_reference (src);
1230       if (x != src && use_set)
1231         {
1232           rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1233           rtx old_rtx = note ? XEXP (note, 0) : SET_SRC (use_set);
1234           rtx new_rtx = simplify_replace_rtx (old_rtx, src, x);
1235           if (old_rtx != new_rtx)
1236             set_unique_reg_note (use_insn, REG_EQUAL, copy_rtx (new_rtx));
1237         }
1238       return false;
1239     }
1240
1241   if (asm_use >= 0)
1242     return forward_propagate_asm (use, def_insn, def_set, reg);
1243
1244   /* Else try simplifying.  */
1245
1246   if (DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE)
1247     {
1248       loc = &SET_DEST (use_set);
1249       set_reg_equal = false;
1250     }
1251   else
1252     {
1253       rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1254       if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1255         loc = &XEXP (note, 0);
1256       else
1257         loc = &SET_SRC (use_set);
1258
1259       /* Do not replace an existing REG_EQUAL note if the insn is not
1260          recognized.  Either we're already replacing in the note, or
1261          we'll separately try plugging the definition in the note and
1262          simplifying.  */
1263       set_reg_equal = (note == NULL_RTX);
1264     }
1265
1266   if (GET_MODE (*loc) == VOIDmode)
1267     mode = GET_MODE (SET_DEST (use_set));
1268   else
1269     mode = GET_MODE (*loc);
1270
1271   new_rtx = propagate_rtx (*loc, mode, reg, src,
1272                            optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn)));
1273
1274   if (!new_rtx)
1275     return false;
1276
1277   return try_fwprop_subst (use, loc, new_rtx, def_insn, set_reg_equal);
1278 }
1279
1280
1281 /* Given a use USE of an insn, if it has a single reaching
1282    definition, try to forward propagate it into that insn.  */
1283
1284 static void
1285 forward_propagate_into (df_ref use)
1286 {
1287   df_ref def;
1288   rtx def_insn, def_set, use_insn;
1289   rtx parent;
1290
1291   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
1292     return;
1293   if (DF_REF_IS_ARTIFICIAL (use))
1294     return;
1295
1296   /* Only consider uses that have a single definition.  */
1297   def = get_def_for_use (use);
1298   if (!def)
1299     return;
1300   if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
1301     return;
1302   if (DF_REF_IS_ARTIFICIAL (def))
1303     return;
1304
1305   /* Do not propagate loop invariant definitions inside the loop.  */
1306   if (DF_REF_BB (def)->loop_father != DF_REF_BB (use)->loop_father)
1307     return;
1308
1309   /* Check if the use is still present in the insn!  */
1310   use_insn = DF_REF_INSN (use);
1311   if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1312     parent = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1313   else
1314     parent = PATTERN (use_insn);
1315
1316   if (!reg_mentioned_p (DF_REF_REG (use), parent))
1317     return;
1318
1319   def_insn = DF_REF_INSN (def);
1320   if (multiple_sets (def_insn))
1321     return;
1322   def_set = single_set (def_insn);
1323   if (!def_set)
1324     return;
1325
1326   /* Only try one kind of propagation.  If two are possible, we'll
1327      do it on the following iterations.  */
1328   if (!forward_propagate_and_simplify (use, def_insn, def_set))
1329     forward_propagate_subreg (use, def_insn, def_set);
1330 }
1331
1332 \f
1333 static void
1334 fwprop_init (void)
1335 {
1336   num_changes = 0;
1337   calculate_dominance_info (CDI_DOMINATORS);
1338
1339   /* We do not always want to propagate into loops, so we have to find
1340      loops and be careful about them.  But we have to call flow_loops_find
1341      before df_analyze, because flow_loops_find may introduce new jump
1342      insns (sadly) if we are not working in cfglayout mode.  */
1343   loop_optimizer_init (0);
1344
1345   build_single_def_use_links ();
1346   df_set_flags (DF_DEFER_INSN_RESCAN);
1347 }
1348
1349 static void
1350 fwprop_done (void)
1351 {
1352   loop_optimizer_finalize ();
1353
1354   VEC_free (df_ref, heap, use_def_ref);
1355   free_dominance_info (CDI_DOMINATORS);
1356   cleanup_cfg (0);
1357   delete_trivially_dead_insns (get_insns (), max_reg_num ());
1358
1359   if (dump_file)
1360     fprintf (dump_file,
1361              "\nNumber of successful forward propagations: %d\n\n",
1362              num_changes);
1363   df_remove_problem (df_chain);
1364 }
1365
1366
1367
1368 /* Main entry point.  */
1369
1370 static bool
1371 gate_fwprop (void)
1372 {
1373   return optimize > 0 && flag_forward_propagate;
1374 }
1375
1376 static unsigned int
1377 fwprop (void)
1378 {
1379   unsigned i;
1380
1381   fwprop_init ();
1382
1383   /* Go through all the uses.  update_df will create new ones at the
1384      end, and we'll go through them as well.
1385
1386      Do not forward propagate addresses into loops until after unrolling.
1387      CSE did so because it was able to fix its own mess, but we are not.  */
1388
1389   for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1390     {
1391       df_ref use = DF_USES_GET (i);
1392       if (use)
1393         if (DF_REF_TYPE (use) == DF_REF_REG_USE
1394             || DF_REF_BB (use)->loop_father == NULL
1395             /* The outer most loop is not really a loop.  */
1396             || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
1397           forward_propagate_into (use);
1398     }
1399
1400   fwprop_done ();
1401   return 0;
1402 }
1403
1404 struct rtl_opt_pass pass_rtl_fwprop =
1405 {
1406  {
1407   RTL_PASS,
1408   "fwprop1",                            /* name */
1409   gate_fwprop,                          /* gate */
1410   fwprop,                               /* execute */
1411   NULL,                                 /* sub */
1412   NULL,                                 /* next */
1413   0,                                    /* static_pass_number */
1414   TV_FWPROP,                            /* tv_id */
1415   0,                                    /* properties_required */
1416   0,                                    /* properties_provided */
1417   0,                                    /* properties_destroyed */
1418   0,                                    /* todo_flags_start */
1419   TODO_df_finish | TODO_verify_rtl_sharing |
1420   TODO_dump_func                        /* todo_flags_finish */
1421  }
1422 };
1423
1424 static unsigned int
1425 fwprop_addr (void)
1426 {
1427   unsigned i;
1428   fwprop_init ();
1429
1430   /* Go through all the uses.  update_df will create new ones at the
1431      end, and we'll go through them as well.  */
1432   for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1433     {
1434       df_ref use = DF_USES_GET (i);
1435       if (use)
1436         if (DF_REF_TYPE (use) != DF_REF_REG_USE
1437             && DF_REF_BB (use)->loop_father != NULL
1438             /* The outer most loop is not really a loop.  */
1439             && loop_outer (DF_REF_BB (use)->loop_father) != NULL)
1440           forward_propagate_into (use);
1441     }
1442
1443   fwprop_done ();
1444
1445   return 0;
1446 }
1447
1448 struct rtl_opt_pass pass_rtl_fwprop_addr =
1449 {
1450  {
1451   RTL_PASS,
1452   "fwprop2",                            /* name */
1453   gate_fwprop,                          /* gate */
1454   fwprop_addr,                          /* execute */
1455   NULL,                                 /* sub */
1456   NULL,                                 /* next */
1457   0,                                    /* static_pass_number */
1458   TV_FWPROP,                            /* tv_id */
1459   0,                                    /* properties_required */
1460   0,                                    /* properties_provided */
1461   0,                                    /* properties_destroyed */
1462   0,                                    /* todo_flags_start */
1463   TODO_df_finish | TODO_verify_rtl_sharing |
1464   TODO_dump_func                        /* todo_flags_finish */
1465  }
1466 };