Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / fwprop.c
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.
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 "diagnostic-core.h"
26
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"
54
55
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.
60
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.
65
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
71
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)))
78
79    can be simplified to the much simpler
80
81       (set (subreg:SI (reg:DI 122) 0) (subreg:SI (reg:DI 119)))
82       (set (subreg:SI (reg:DI 122) 4) (const_int -1))
83
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.
89
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.
93
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.
97
98    3) The pass looks for paradoxical subregs that are actually unnecessary.
99    Things like this:
100
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)))
105
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
111
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)))
115
116    where the first two insns are now dead.
117
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.  */
127
128
129 static int num_changes;
130
131 static vec<df_ref> use_def_ref;
132 static vec<df_ref> reg_defs;
133 static vec<df_ref> reg_defs_stack;
134
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;
141
142 /* Return the only def in USE's use-def chain, or NULL if there is
143    more than one def in the chain.  */
144
145 static inline df_ref
146 get_def_for_use (df_ref use)
147 {
148   return use_def_ref[DF_REF_ID (use)];
149 }
150
151
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.  */
157
158 #define DF_MD_GEN_FLAGS \
159         (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
160
161 static void
162 process_defs (df_ref def, int top_flag)
163 {
164   for (; def; def = DF_REF_NEXT_LOC (def))
165     {
166       df_ref curr_def = reg_defs[DF_REF_REGNO (def)];
167       unsigned int dregno;
168
169       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag)
170         continue;
171
172       dregno = DF_REF_REGNO (def);
173       if (curr_def)
174         reg_defs_stack.safe_push (curr_def);
175       else
176         {
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)
181             ;
182           else
183             reg_defs_stack.safe_push (def);
184         }
185
186       if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
187         {
188           bitmap_set_bit (local_md, dregno);
189           reg_defs[dregno] = NULL;
190         }
191       else
192         {
193           bitmap_clear_bit (local_md, dregno);
194           reg_defs[dregno] = def;
195         }
196     }
197 }
198
199
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.  */
204
205 static void
206 process_uses (df_ref use, int top_flag)
207 {
208   for (; use; use = DF_REF_NEXT_LOC (use))
209     if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag)
210       {
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];
216       }
217 }
218
219 class single_def_use_dom_walker : public dom_walker
220 {
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);
226 };
227
228 void
229 single_def_use_dom_walker::before_dom_children (basic_block bb)
230 {
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;
235
236   bitmap_copy (local_md, &md_bb_info->in);
237   bitmap_copy (local_lr, &lr_bb_info->in);
238
239   /* Push a marker for the leave_block callback.  */
240   reg_defs_stack.safe_push (NULL);
241
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);
244
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.  */
248
249   FOR_BB_INSNS (bb, insn)
250     if (INSN_P (insn))
251       {
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);
257       }
258
259   process_uses (df_get_artificial_uses (bb_index), 0);
260   process_defs (df_get_artificial_defs (bb_index), 0);
261 }
262
263 /* Pop the definitions created in this basic block when leaving its
264    dominated parts.  */
265
266 void
267 single_def_use_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
268 {
269   df_ref saved_def;
270   while ((saved_def = reg_defs_stack.pop ()) != NULL)
271     {
272       unsigned int dregno = DF_REF_REGNO (saved_def);
273
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;
279     }
280 }
281
282
283 /* Build a vector holding the reaching definitions of uses reached by a
284    single dominating definition.  */
285
286 static void
287 build_single_def_use_links (void)
288 {
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);
296
297   use_def_ref.create (DF_USES_TABLE_SIZE ());
298   use_def_ref.safe_grow_cleared (DF_USES_TABLE_SIZE ());
299
300   reg_defs.create (max_reg_num ());
301   reg_defs.safe_grow_cleared (max_reg_num ());
302
303   reg_defs_stack.create (n_basic_blocks_for_fn (cfun) * 10);
304   local_md = BITMAP_ALLOC (NULL);
305   local_lr = BITMAP_ALLOC (NULL);
306
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);
311
312   BITMAP_FREE (local_lr);
313   BITMAP_FREE (local_md);
314   reg_defs.release ();
315   reg_defs_stack.release ();
316 }
317
318 \f
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.
323
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.  */
328
329 static bool
330 can_simplify_addr (rtx addr)
331 {
332   rtx reg;
333
334   if (CONSTANT_ADDRESS_P (addr))
335     return false;
336
337   if (GET_CODE (addr) == PLUS)
338     reg = XEXP (addr, 0);
339   else
340     reg = addr;
341
342   return (!REG_P (reg)
343           || (REGNO (reg) != FRAME_POINTER_REGNUM
344               && REGNO (reg) != HARD_FRAME_POINTER_REGNUM
345               && REGNO (reg) != ARG_POINTER_REGNUM));
346 }
347
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.
351
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.  */
354
355 static void
356 canonicalize_address (rtx x)
357 {
358   for (;;)
359     switch (GET_CODE (x))
360       {
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)
365           {
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));
370           }
371
372         x = XEXP (x, 0);
373         break;
374
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));
380
381         x = XEXP (x, 1);
382         break;
383
384       case CONST:
385         x = XEXP (x, 0);
386         break;
387
388       default:
389         return;
390       }
391 }
392
393 /* OLD is a memory address.  Return whether it is good to use NEW instead,
394    for a memory access in the given MODE.  */
395
396 static bool
397 should_replace_address (rtx old_rtx, rtx new_rtx, machine_mode mode,
398                         addr_space_t as, bool speed)
399 {
400   int gain;
401
402   if (rtx_equal_p (old_rtx, new_rtx)
403       || !memory_address_addr_space_p (mode, new_rtx, as))
404     return false;
405
406   /* Copy propagation is always ok.  */
407   if (REG_P (old_rtx) && REG_P (new_rtx))
408     return true;
409
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));
413
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);
420
421   return (gain > 0);
422 }
423
424
425 /* Flags for the last parameter of propagate_rtx_1.  */
426
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).
433
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,
438
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.
443
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,
448
449   /* Set when costs should be optimized for speed.  */
450   PR_OPTIMIZE_FOR_SPEED = 4
451 };
452
453
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.
457
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).  */
461
462 static bool
463 propagate_rtx_1 (rtx *px, rtx old_rtx, rtx new_rtx, int flags)
464 {
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;
471
472   if (!(flags & PR_HANDLE_MEM) && MEM_P (x) && !MEM_READONLY_P (x))
473     {
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;
480     }
481
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)
485     {
486       *px = new_rtx;
487       return can_appear;
488     }
489
490   /* If this is an expression, try recursive substitution.  */
491   switch (GET_RTX_CLASS (code))
492     {
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;
501
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;
512
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;
524
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;
540
541     case RTX_EXTRA:
542       /* The only case we try to handle is a SUBREG.  */
543       if (code == SUBREG)
544         {
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));
551         }
552       break;
553
554     case RTX_OBJ:
555       if (code == MEM && x != new_rtx)
556         {
557           rtx new_op0;
558           op0 = XEXP (x, 0);
559
560           /* There are some addresses that we cannot work on.  */
561           if (!can_simplify_addr (op0))
562             return true;
563
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);
567
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;
574
575           canonicalize_address (new_op0);
576
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;
583
584           tem = replace_equiv_address_nv (x, new_op0);
585         }
586
587       else if (code == LO_SUM)
588         {
589           op0 = XEXP (x, 0);
590           op1 = XEXP (x, 1);
591
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;
599
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);
605
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);
610         }
611
612       else if (code == REG)
613         {
614           if (rtx_equal_p (x, old_rtx))
615             {
616               *px = new_rtx;
617               return can_appear;
618             }
619         }
620       break;
621
622     default:
623       break;
624     }
625
626   /* No change, no trouble.  */
627   if (tem == NULL_RTX)
628     return true;
629
630   *px = tem;
631
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);
636 }
637
638
639 /* Return true if X constains a non-constant mem.  */
640
641 static bool
642 varying_mem_p (const_rtx x)
643 {
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;
649 }
650
651
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.
655
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.  */
659
660 static rtx
661 propagate_rtx (rtx x, machine_mode mode, rtx old_rtx, rtx new_rtx,
662                bool speed)
663 {
664   rtx tem;
665   bool collapsed;
666   int flags;
667
668   if (REG_P (new_rtx) && REGNO (new_rtx) < FIRST_PSEUDO_REGISTER)
669     return NULL_RTX;
670
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;
681
682   if (speed)
683     flags |= PR_OPTIMIZE_FOR_SPEED;
684
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;
689
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;
694
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);
699
700   return tem;
701 }
702
703
704 \f
705
706 /* Return true if the register from reference REF is killed
707    between FROM to (but not including) TO.  */
708
709 static bool
710 local_ref_killed_between_p (df_ref ref, rtx_insn *from, rtx_insn *to)
711 {
712   rtx_insn *insn;
713
714   for (insn = from; insn != to; insn = NEXT_INSN (insn))
715     {
716       df_ref def;
717       if (!INSN_P (insn))
718         continue;
719
720       FOR_EACH_INSN_DEF (def, insn)
721         if (DF_REF_REGNO (ref) == DF_REF_REGNO (def))
722           return true;
723     }
724   return false;
725 }
726
727
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)
738 {
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;
743
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;
754
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;
766
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);
770
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)
774     {
775       df_ref x;
776
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;
782
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;
788
789       return false;
790     }
791
792   /* Otherwise assume the worst case.  */
793   return true;
794 }
795
796
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)
802 {
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;
807
808   gcc_assert (def_set);
809
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)))
817     {
818       rtx def_reg = SET_DEST (def_set);
819
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;
828     }
829   else
830     {
831       rtx def_reg = REG_P (SET_DEST (def_set)) ? SET_DEST (def_set) : NULL_RTX;
832
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)
836         {
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;
841         }
842       FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
843         {
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;
848         }
849     }
850
851   return true;
852 }
853
854 \f
855 static df_ref *active_defs;
856 #ifdef ENABLE_CHECKING
857 static sparseset active_defs_check;
858 #endif
859
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.  */
863
864 static void
865 register_active_defs (df_ref use)
866 {
867   for (; use; use = DF_REF_NEXT_LOC (use))
868     {
869       df_ref def = get_def_for_use (use);
870       int regno = DF_REF_REGNO (use);
871
872 #ifdef ENABLE_CHECKING
873       sparseset_set_bit (active_defs_check, regno);
874 #endif
875       active_defs[regno] = def;
876     }
877 }
878
879
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.  */
885
886 static void
887 update_df_init (rtx_insn *def_insn, rtx_insn *insn)
888 {
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));
895 }
896
897
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. */
900
901 static inline void
902 update_uses (df_ref use)
903 {
904   for (; use; use = DF_REF_NEXT_LOC (use))
905     {
906       int regno = DF_REF_REGNO (use);
907
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);
911
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];
916     }
917 }
918
919
920 /* Update the USE_DEF_REF array for the uses in INSN.  Only update note
921    uses if NOTES_ONLY is true.  */
922
923 static void
924 update_df (rtx_insn *insn, rtx note)
925 {
926   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
927
928   if (note)
929     {
930       df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE);
931       df_notes_rescan (insn);
932     }
933   else
934     {
935       df_uses_create (&PATTERN (insn), insn, 0);
936       df_insn_rescan (insn);
937       update_uses (DF_INSN_INFO_USES (insn_info));
938     }
939
940   update_uses (DF_INSN_INFO_EQ_USES (insn_info));
941 }
942
943
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.  */
949
950 static bool
951 try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx_insn *def_insn,
952                   bool set_reg_equal)
953 {
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;
960
961   update_df_init (def_insn, insn);
962
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)
969     {
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");
975     }
976
977   validate_unshare_change (insn, loc, new_rtx, true);
978   if (!verify_changes (0))
979     {
980       if (dump_file)
981         fprintf (dump_file, "Changes to insn %d not recognized\n",
982                  INSN_UID (insn));
983       ok = false;
984     }
985
986   else if (DF_REF_TYPE (use) == DF_REF_REG_USE
987            && set
988            && set_src_cost (SET_SRC (set), speed) > old_cost)
989     {
990       if (dump_file)
991         fprintf (dump_file, "Changes to insn %d not profitable\n",
992                  INSN_UID (insn));
993       ok = false;
994     }
995
996   else
997     {
998       if (dump_file)
999         fprintf (dump_file, "Changed insn %d\n", INSN_UID (insn));
1000       ok = true;
1001     }
1002
1003   if (ok)
1004     {
1005       confirm_change_group ();
1006       num_changes++;
1007     }
1008   else
1009     {
1010       cancel_changes (0);
1011
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)
1015         {
1016           if (dump_file)
1017             fprintf (dump_file, " Setting REG_EQUAL note\n");
1018
1019           note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
1020         }
1021     }
1022
1023   if ((ok || note) && !CONSTANT_P (new_rtx))
1024     update_df (insn, note);
1025
1026   return ok;
1027 }
1028
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.  */
1033
1034 static bool
1035 free_load_extend (rtx src, rtx_insn *insn)
1036 {
1037   rtx reg;
1038   df_ref def, use;
1039
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;
1045
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;
1053
1054   def = get_def_for_use (use);
1055   if (!def)
1056     return false;
1057
1058   if (DF_REF_IS_ARTIFICIAL (def))
1059     return false;
1060
1061   if (NONJUMP_INSN_P (DF_REF_INSN (def)))
1062     {
1063       rtx patt = PATTERN (DF_REF_INSN (def));
1064
1065       if (GET_CODE (patt) == SET
1066           && GET_CODE (SET_SRC (patt)) == MEM
1067           && rtx_equal_p (SET_DEST (patt), reg))
1068         return true;
1069     }
1070   return false;
1071 }
1072
1073 /* If USE is a subreg, see if it can be replaced by a pseudo.  */
1074
1075 static bool
1076 forward_propagate_subreg (df_ref use, rtx_insn *def_insn, rtx def_set)
1077 {
1078   rtx use_reg = DF_REF_REG (use);
1079   rtx_insn *use_insn;
1080   rtx src;
1081
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;
1087
1088   /* If this is a paradoxical SUBREG...  */
1089   if (GET_MODE_SIZE (use_mode)
1090       > GET_MODE_SIZE (GET_MODE (SUBREG_REG (use_reg))))
1091     {
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);
1107     }
1108
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:
1115
1116          A: (set (reg:DI X) (sign_extend:DI (reg:SI Y)))
1117          B: (... (subreg:SI (reg:DI X)) ...)
1118
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))
1125     {
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);
1139     }
1140
1141   return false;
1142 }
1143
1144 /* Try to replace USE with SRC (defined in DEF_INSN) in __asm.  */
1145
1146 static bool
1147 forward_propagate_asm (df_ref use, rtx_insn *def_insn, rtx def_set, rtx reg)
1148 {
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;
1153
1154   gcc_assert ((DF_REF_FLAGS (use) & DF_REF_IN_NOTE) == 0);
1155
1156   src = SET_SRC (def_set);
1157   use_pat = PATTERN (use_insn);
1158
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;
1164
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))
1169     {
1170     case ASM_OPERANDS:
1171       asm_operands = use_pat;
1172       break;
1173     case SET:
1174       if (MEM_P (SET_DEST (use_pat)))
1175         {
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);
1180         }
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)
1186           {
1187             if (MEM_P (SET_DEST (XVECEXP (use_pat, 0, i))))
1188               {
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);
1194               }
1195             asm_operands = SET_SRC (XVECEXP (use_pat, 0, i));
1196           }
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 ();
1202     }
1203
1204   gcc_assert (asm_operands && GET_CODE (asm_operands) == ASM_OPERANDS);
1205   for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (asm_operands); i++)
1206     {
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);
1211     }
1212
1213   if (num_changes_pending () == 0 || !apply_change_group ())
1214     return false;
1215
1216   update_df (use_insn, NULL);
1217   num_changes++;
1218   return true;
1219 }
1220
1221 /* Try to replace USE with SRC (defined in DEF_INSN) and simplify the
1222    result.  */
1223
1224 static bool
1225 forward_propagate_and_simplify (df_ref use, rtx_insn *def_insn, rtx def_set)
1226 {
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;
1233
1234   if (INSN_CODE (use_insn) < 0)
1235     asm_use = asm_noperands (PATTERN (use_insn));
1236
1237   if (!use_set && asm_use < 0 && !DEBUG_INSN_P (use_insn))
1238     return false;
1239
1240   /* Do not propagate into PC, CC0, etc.  */
1241   if (use_set && GET_MODE (SET_DEST (use_set)) == VOIDmode)
1242     return false;
1243
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)
1247     {
1248       if (SUBREG_BYTE (SET_DEST (def_set)) != SUBREG_BYTE (reg))
1249         return false;
1250     }
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);
1258
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;
1263
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;
1269
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))
1274     {
1275       rtx x = avoid_constant_pool_reference (src);
1276       if (x != src && use_set)
1277         {
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));
1283         }
1284       return false;
1285     }
1286
1287   if (asm_use >= 0)
1288     return forward_propagate_asm (use, def_insn, def_set, reg);
1289
1290   /* Else try simplifying.  */
1291
1292   if (DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE)
1293     {
1294       loc = &SET_DEST (use_set);
1295       set_reg_equal = false;
1296     }
1297   else if (!use_set)
1298     {
1299       loc = &INSN_VAR_LOCATION_LOC (use_insn);
1300       set_reg_equal = false;
1301     }
1302   else
1303     {
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);
1309
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)));
1325     }
1326
1327   if (GET_MODE (*loc) == VOIDmode)
1328     mode = GET_MODE (SET_DEST (use_set));
1329   else
1330     mode = GET_MODE (*loc);
1331
1332   new_rtx = propagate_rtx (*loc, mode, reg, src,
1333                            optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn)));
1334
1335   if (!new_rtx)
1336     return false;
1337
1338   return try_fwprop_subst (use, loc, new_rtx, def_insn, set_reg_equal);
1339 }
1340
1341
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.  */
1345
1346 static bool
1347 forward_propagate_into (df_ref use)
1348 {
1349   df_ref def;
1350   rtx_insn *def_insn, *use_insn;
1351   rtx def_set;
1352   rtx parent;
1353
1354   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
1355     return false;
1356   if (DF_REF_IS_ARTIFICIAL (use))
1357     return false;
1358
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;
1367
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;
1371
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);
1378
1379   if (!reg_mentioned_p (DF_REF_REG (use), parent))
1380     return false;
1381
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;
1388
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))
1393     {
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;
1398     }
1399   return false;
1400 }
1401
1402 \f
1403 static void
1404 fwprop_init (void)
1405 {
1406   num_changes = 0;
1407   calculate_dominance_info (CDI_DOMINATORS);
1408
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);
1414
1415   build_single_def_use_links ();
1416   df_set_flags (DF_DEFER_INSN_RESCAN);
1417
1418   active_defs = XNEWVEC (df_ref, max_reg_num ());
1419 #ifdef ENABLE_CHECKING
1420   active_defs_check = sparseset_alloc (max_reg_num ());
1421 #endif
1422 }
1423
1424 static void
1425 fwprop_done (void)
1426 {
1427   loop_optimizer_finalize ();
1428
1429   use_def_ref.release ();
1430   free (active_defs);
1431 #ifdef ENABLE_CHECKING
1432   sparseset_free (active_defs_check);
1433 #endif
1434
1435   free_dominance_info (CDI_DOMINATORS);
1436   cleanup_cfg (0);
1437   delete_trivially_dead_insns (get_insns (), max_reg_num ());
1438
1439   if (dump_file)
1440     fprintf (dump_file,
1441              "\nNumber of successful forward propagations: %d\n\n",
1442              num_changes);
1443 }
1444
1445
1446 /* Main entry point.  */
1447
1448 static bool
1449 gate_fwprop (void)
1450 {
1451   return optimize > 0 && flag_forward_propagate;
1452 }
1453
1454 static unsigned int
1455 fwprop (void)
1456 {
1457   unsigned i;
1458   bool need_cleanup = false;
1459
1460   fwprop_init ();
1461
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.
1464
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.  */
1467
1468   for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1469     {
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);
1477     }
1478
1479   fwprop_done ();
1480   if (need_cleanup)
1481     cleanup_cfg (0);
1482   return 0;
1483 }
1484
1485 namespace {
1486
1487 const pass_data pass_data_rtl_fwprop =
1488 {
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 */
1498 };
1499
1500 class pass_rtl_fwprop : public rtl_opt_pass
1501 {
1502 public:
1503   pass_rtl_fwprop (gcc::context *ctxt)
1504     : rtl_opt_pass (pass_data_rtl_fwprop, ctxt)
1505   {}
1506
1507   /* opt_pass methods: */
1508   virtual bool gate (function *) { return gate_fwprop (); }
1509   virtual unsigned int execute (function *) { return fwprop (); }
1510
1511 }; // class pass_rtl_fwprop
1512
1513 } // anon namespace
1514
1515 rtl_opt_pass *
1516 make_pass_rtl_fwprop (gcc::context *ctxt)
1517 {
1518   return new pass_rtl_fwprop (ctxt);
1519 }
1520
1521 static unsigned int
1522 fwprop_addr (void)
1523 {
1524   unsigned i;
1525   bool need_cleanup = false;
1526
1527   fwprop_init ();
1528
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++)
1532     {
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);
1540     }
1541
1542   fwprop_done ();
1543
1544   if (need_cleanup)
1545     cleanup_cfg (0);
1546   return 0;
1547 }
1548
1549 namespace {
1550
1551 const pass_data pass_data_rtl_fwprop_addr =
1552 {
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 */
1562 };
1563
1564 class pass_rtl_fwprop_addr : public rtl_opt_pass
1565 {
1566 public:
1567   pass_rtl_fwprop_addr (gcc::context *ctxt)
1568     : rtl_opt_pass (pass_data_rtl_fwprop_addr, ctxt)
1569   {}
1570
1571   /* opt_pass methods: */
1572   virtual bool gate (function *) { return gate_fwprop (); }
1573   virtual unsigned int execute (function *) { return fwprop_addr (); }
1574
1575 }; // class pass_rtl_fwprop_addr
1576
1577 } // anon namespace
1578
1579 rtl_opt_pass *
1580 make_pass_rtl_fwprop_addr (gcc::context *ctxt)
1581 {
1582   return new pass_rtl_fwprop_addr (ctxt);
1583 }