OSDN Git Service

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