OSDN Git Service

Daily bump.
[pf3gnuchains/gcc-fork.git] / gcc / fwprop.c
1 /* RTL-based forward propagation pass for GNU compiler.
2    Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
3    Contributed by Paolo Bonzini and Steven Bosscher.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "toplev.h"
26
27 #include "timevar.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "emit-rtl.h"
31 #include "insn-config.h"
32 #include "recog.h"
33 #include "flags.h"
34 #include "obstack.h"
35 #include "basic-block.h"
36 #include "output.h"
37 #include "df.h"
38 #include "target.h"
39 #include "cfgloop.h"
40 #include "tree-pass.h"
41
42
43 /* This pass does simple forward propagation and simplification when an
44    operand of an insn can only come from a single def.  This pass uses
45    df.c, so it is global.  However, we only do limited analysis of
46    available expressions.
47
48    1) The pass tries to propagate the source of the def into the use,
49    and checks if the result is independent of the substituted value.
50    For example, the high word of a (zero_extend:DI (reg:SI M)) is always
51    zero, independent of the source register.
52
53    In particular, we propagate constants into the use site.  Sometimes
54    RTL expansion did not put the constant in the same insn on purpose,
55    to satisfy a predicate, and the result will fail to be recognized;
56    but this happens rarely and in this case we can still create a
57    REG_EQUAL note.  For multi-word operations, this
58
59       (set (subreg:SI (reg:DI 120) 0) (const_int 0))
60       (set (subreg:SI (reg:DI 120) 4) (const_int -1))
61       (set (subreg:SI (reg:DI 122) 0)
62          (ior:SI (subreg:SI (reg:DI 119) 0) (subreg:SI (reg:DI 120) 0)))
63       (set (subreg:SI (reg:DI 122) 4)
64          (ior:SI (subreg:SI (reg:DI 119) 4) (subreg:SI (reg:DI 120) 4)))
65
66    can be simplified to the much simpler
67
68       (set (subreg:SI (reg:DI 122) 0) (subreg:SI (reg:DI 119)))
69       (set (subreg:SI (reg:DI 122) 4) (const_int -1))
70
71    This particular propagation is also effective at putting together
72    complex addressing modes.  We are more aggressive inside MEMs, in
73    that all definitions are propagated if the use is in a MEM; if the
74    result is a valid memory address we check address_cost to decide
75    whether the substitution is worthwhile.
76
77    2) The pass propagates register copies.  This is not as effective as
78    the copy propagation done by CSE's canon_reg, which works by walking
79    the instruction chain, it can help the other transformations.
80
81    We should consider removing this optimization, and instead reorder the
82    RTL passes, because GCSE does this transformation too.  With some luck,
83    the CSE pass at the end of rest_of_handle_gcse could also go away.
84
85    3) The pass looks for paradoxical subregs that are actually unnecessary.
86    Things like this:
87
88      (set (reg:QI 120) (subreg:QI (reg:SI 118) 0))
89      (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
90      (set (reg:SI 122) (plus:SI (subreg:SI (reg:QI 120) 0)
91                                 (subreg:SI (reg:QI 121) 0)))
92
93    are very common on machines that can only do word-sized operations.
94    For each use of a paradoxical subreg (subreg:WIDER (reg:NARROW N) 0),
95    if it has a single def and it is (subreg:NARROW (reg:WIDE M) 0),
96    we can replace the paradoxical subreg with simply (reg:WIDE M).  The
97    above will simplify this to
98
99      (set (reg:QI 120) (subreg:QI (reg:SI 118) 0))
100      (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
101      (set (reg:SI 122) (plus:SI (reg:SI 118) (reg:SI 119)))
102
103    where the first two insns are now dead.  */
104
105
106 static int num_changes;
107
108 \f
109 /* Do not try to replace constant addresses or addresses of local and
110    argument slots.  These MEM expressions are made only once and inserted
111    in many instructions, as well as being used to control symbol table
112    output.  It is not safe to clobber them.
113
114    There are some uncommon cases where the address is already in a register
115    for some reason, but we cannot take advantage of that because we have
116    no easy way to unshare the MEM.  In addition, looking up all stack
117    addresses is costly.  */
118
119 static bool
120 can_simplify_addr (rtx addr)
121 {
122   rtx reg;
123
124   if (CONSTANT_ADDRESS_P (addr))
125     return false;
126
127   if (GET_CODE (addr) == PLUS)
128     reg = XEXP (addr, 0);
129   else
130     reg = addr;
131
132   return (!REG_P (reg)
133           || (REGNO (reg) != FRAME_POINTER_REGNUM
134               && REGNO (reg) != HARD_FRAME_POINTER_REGNUM
135               && REGNO (reg) != ARG_POINTER_REGNUM));
136 }
137
138 /* Returns a canonical version of X for the address, from the point of view,
139    that all multiplications are represented as MULT instead of the multiply
140    by a power of 2 being represented as ASHIFT.
141
142    Every ASHIFT we find has been made by simplify_gen_binary and was not
143    there before, so it is not shared.  So we can do this in place.  */
144
145 static void
146 canonicalize_address (rtx x)
147 {
148   for (;;)
149     switch (GET_CODE (x))
150       {
151       case ASHIFT:
152         if (GET_CODE (XEXP (x, 1)) == CONST_INT
153             && INTVAL (XEXP (x, 1)) < GET_MODE_BITSIZE (GET_MODE (x))
154             && INTVAL (XEXP (x, 1)) >= 0)
155           {
156             HOST_WIDE_INT shift = INTVAL (XEXP (x, 1));
157             PUT_CODE (x, MULT);
158             XEXP (x, 1) = gen_int_mode ((HOST_WIDE_INT) 1 << shift,
159                                         GET_MODE (x));
160           }
161
162         x = XEXP (x, 0);
163         break;
164
165       case PLUS:
166         if (GET_CODE (XEXP (x, 0)) == PLUS
167             || GET_CODE (XEXP (x, 0)) == ASHIFT
168             || GET_CODE (XEXP (x, 0)) == CONST)
169           canonicalize_address (XEXP (x, 0));
170
171         x = XEXP (x, 1);
172         break;
173
174       case CONST:
175         x = XEXP (x, 0);
176         break;
177
178       default:
179         return;
180       }
181 }
182
183 /* OLD is a memory address.  Return whether it is good to use NEW instead,
184    for a memory access in the given MODE.  */
185
186 static bool
187 should_replace_address (rtx old, rtx new, enum machine_mode mode)
188 {
189   int gain;
190
191   if (rtx_equal_p (old, new) || !memory_address_p (mode, new))
192     return false;
193
194   /* Copy propagation is always ok.  */
195   if (REG_P (old) && REG_P (new))
196     return true;
197
198   /* Prefer the new address if it is less expensive.  */
199   gain = address_cost (old, mode) - address_cost (new, mode);
200
201   /* If the addresses have equivalent cost, prefer the new address
202      if it has the highest `rtx_cost'.  That has the potential of
203      eliminating the most insns without additional costs, and it
204      is the same that cse.c used to do.  */
205   if (gain == 0)
206     gain = rtx_cost (new, SET) - rtx_cost (old, SET);
207
208   return (gain > 0);
209 }
210
211
212 /* Flags for the last parameter of propagate_rtx_1.  */
213
214 enum {
215   /* If PR_CAN_APPEAR is true, propagate_rtx_1 always returns true;
216      if it is false, propagate_rtx_1 returns false if, for at least
217      one occurrence OLD, it failed to collapse the result to a constant.
218      For example, (mult:M (reg:M A) (minus:M (reg:M B) (reg:M A))) may
219      collapse to zero if replacing (reg:M B) with (reg:M A).
220
221      PR_CAN_APPEAR is disregarded inside MEMs: in that case,
222      propagate_rtx_1 just tries to make cheaper and valid memory
223      addresses.  */
224   PR_CAN_APPEAR = 1,
225
226   /* If PR_HANDLE_MEM is not set, propagate_rtx_1 won't attempt any replacement
227      outside memory addresses.  This is needed because propagate_rtx_1 does
228      not do any analysis on memory; thus it is very conservative and in general
229      it will fail if non-read-only MEMs are found in the source expression.
230
231      PR_HANDLE_MEM is set when the source of the propagation was not
232      another MEM.  Then, it is safe not to treat non-read-only MEMs as
233      ``opaque'' objects.  */
234   PR_HANDLE_MEM = 2
235 };
236
237
238 /* Replace all occurrences of OLD in *PX with NEW and try to simplify the
239    resulting expression.  Replace *PX with a new RTL expression if an
240    occurrence of OLD was found.
241
242    This is only a wrapper around simplify-rtx.c: do not add any pattern
243    matching code here.  (The sole exception is the handling of LO_SUM, but
244    that is because there is no simplify_gen_* function for LO_SUM).  */
245
246 static bool
247 propagate_rtx_1 (rtx *px, rtx old, rtx new, int flags)
248 {
249   rtx x = *px, tem = NULL_RTX, op0, op1, op2;
250   enum rtx_code code = GET_CODE (x);
251   enum machine_mode mode = GET_MODE (x);
252   enum machine_mode op_mode;
253   bool can_appear = (flags & PR_CAN_APPEAR) != 0;
254   bool valid_ops = true;
255
256   if (!(flags & PR_HANDLE_MEM) && MEM_P (x) && !MEM_READONLY_P (x))
257     {
258       /* If unsafe, change MEMs to CLOBBERs or SCRATCHes (to preserve whether
259          they have side effects or not).  */
260       *px = (side_effects_p (x)
261              ? gen_rtx_CLOBBER (GET_MODE (x), const0_rtx)
262              : gen_rtx_SCRATCH (GET_MODE (x)));
263       return false;
264     }
265
266   /* If X is OLD_RTX, return NEW_RTX.  But not if replacing only within an
267      address, and we are *not* inside one.  */
268   if (x == old)
269     {
270       *px = new;
271       return can_appear;
272     }
273
274   /* If this is an expression, try recursive substitution.  */
275   switch (GET_RTX_CLASS (code))
276     {
277     case RTX_UNARY:
278       op0 = XEXP (x, 0);
279       op_mode = GET_MODE (op0);
280       valid_ops &= propagate_rtx_1 (&op0, old, new, flags);
281       if (op0 == XEXP (x, 0))
282         return true;
283       tem = simplify_gen_unary (code, mode, op0, op_mode);
284       break;
285
286     case RTX_BIN_ARITH:
287     case RTX_COMM_ARITH:
288       op0 = XEXP (x, 0);
289       op1 = XEXP (x, 1);
290       valid_ops &= propagate_rtx_1 (&op0, old, new, flags);
291       valid_ops &= propagate_rtx_1 (&op1, old, new, flags);
292       if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
293         return true;
294       tem = simplify_gen_binary (code, mode, op0, op1);
295       break;
296
297     case RTX_COMPARE:
298     case RTX_COMM_COMPARE:
299       op0 = XEXP (x, 0);
300       op1 = XEXP (x, 1);
301       op_mode = GET_MODE (op0) != VOIDmode ? GET_MODE (op0) : GET_MODE (op1);
302       valid_ops &= propagate_rtx_1 (&op0, old, new, flags);
303       valid_ops &= propagate_rtx_1 (&op1, old, new, flags);
304       if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
305         return true;
306       tem = simplify_gen_relational (code, mode, op_mode, op0, op1);
307       break;
308
309     case RTX_TERNARY:
310     case RTX_BITFIELD_OPS:
311       op0 = XEXP (x, 0);
312       op1 = XEXP (x, 1);
313       op2 = XEXP (x, 2);
314       op_mode = GET_MODE (op0);
315       valid_ops &= propagate_rtx_1 (&op0, old, new, flags);
316       valid_ops &= propagate_rtx_1 (&op1, old, new, flags);
317       valid_ops &= propagate_rtx_1 (&op2, old, new, flags);
318       if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1) && op2 == XEXP (x, 2))
319         return true;
320       if (op_mode == VOIDmode)
321         op_mode = GET_MODE (op0);
322       tem = simplify_gen_ternary (code, mode, op_mode, op0, op1, op2);
323       break;
324
325     case RTX_EXTRA:
326       /* The only case we try to handle is a SUBREG.  */
327       if (code == SUBREG)
328         {
329           op0 = XEXP (x, 0);
330           valid_ops &= propagate_rtx_1 (&op0, old, new, flags);
331           if (op0 == XEXP (x, 0))
332             return true;
333           tem = simplify_gen_subreg (mode, op0, GET_MODE (SUBREG_REG (x)),
334                                      SUBREG_BYTE (x));
335         }
336       break;
337
338     case RTX_OBJ:
339       if (code == MEM && x != new)
340         {
341           rtx new_op0;
342           op0 = XEXP (x, 0);
343
344           /* There are some addresses that we cannot work on.  */
345           if (!can_simplify_addr (op0))
346             return true;
347
348           op0 = new_op0 = targetm.delegitimize_address (op0);
349           valid_ops &= propagate_rtx_1 (&new_op0, old, new,
350                                         flags | PR_CAN_APPEAR);
351
352           /* Dismiss transformation that we do not want to carry on.  */
353           if (!valid_ops
354               || new_op0 == op0
355               || !(GET_MODE (new_op0) == GET_MODE (op0)
356                    || GET_MODE (new_op0) == VOIDmode))
357             return true;
358
359           canonicalize_address (new_op0);
360
361           /* Copy propagations are always ok.  Otherwise check the costs.  */
362           if (!(REG_P (old) && REG_P (new))
363               && !should_replace_address (op0, new_op0, GET_MODE (x)))
364             return true;
365
366           tem = replace_equiv_address_nv (x, new_op0);
367         }
368
369       else if (code == LO_SUM)
370         {
371           op0 = XEXP (x, 0);
372           op1 = XEXP (x, 1);
373
374           /* The only simplification we do attempts to remove references to op0
375              or make it constant -- in both cases, op0's invalidity will not
376              make the result invalid.  */
377           propagate_rtx_1 (&op0, old, new, flags | PR_CAN_APPEAR);
378           valid_ops &= propagate_rtx_1 (&op1, old, new, flags);
379           if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
380             return true;
381
382           /* (lo_sum (high x) x) -> x  */
383           if (GET_CODE (op0) == HIGH && rtx_equal_p (XEXP (op0, 0), op1))
384             tem = op1;
385           else
386             tem = gen_rtx_LO_SUM (mode, op0, op1);
387
388           /* OP1 is likely not a legitimate address, otherwise there would have
389              been no LO_SUM.  We want it to disappear if it is invalid, return
390              false in that case.  */
391           return memory_address_p (mode, tem);
392         }
393
394       else if (code == REG)
395         {
396           if (rtx_equal_p (x, old))
397             {
398               *px = new;
399               return can_appear;
400             }
401         }
402       break;
403
404     default:
405       break;
406     }
407
408   /* No change, no trouble.  */
409   if (tem == NULL_RTX)
410     return true;
411
412   *px = tem;
413
414   /* The replacement we made so far is valid, if all of the recursive
415      replacements were valid, or we could simplify everything to
416      a constant.  */
417   return valid_ops || can_appear || CONSTANT_P (tem);
418 }
419
420
421 /* for_each_rtx traversal function that returns 1 if BODY points to
422    a non-constant mem.  */
423
424 static int
425 varying_mem_p (rtx *body, void *data ATTRIBUTE_UNUSED)
426 {
427   rtx x = *body;
428   return MEM_P (x) && !MEM_READONLY_P (x);
429 }
430
431
432 /* Replace all occurrences of OLD in X with NEW and try to simplify the
433    resulting expression (in mode MODE).  Return a new expression if it is
434    a constant, otherwise X.
435
436    Simplifications where occurrences of NEW collapse to a constant are always
437    accepted.  All simplifications are accepted if NEW is a pseudo too.
438    Otherwise, we accept simplifications that have a lower or equal cost.  */
439
440 static rtx
441 propagate_rtx (rtx x, enum machine_mode mode, rtx old, rtx new)
442 {
443   rtx tem;
444   bool collapsed;
445   int flags;
446
447   if (REG_P (new) && REGNO (new) < FIRST_PSEUDO_REGISTER)
448     return NULL_RTX;
449
450   flags = 0;
451   if (REG_P (new) || CONSTANT_P (new))
452     flags |= PR_CAN_APPEAR;
453   if (!for_each_rtx (&new, varying_mem_p, NULL))
454     flags |= PR_HANDLE_MEM;
455
456   tem = x;
457   collapsed = propagate_rtx_1 (&tem, old, copy_rtx (new), flags);
458   if (tem == x || !collapsed)
459     return NULL_RTX;
460
461   /* gen_lowpart_common will not be able to process VOIDmode entities other
462      than CONST_INTs.  */
463   if (GET_MODE (tem) == VOIDmode && GET_CODE (tem) != CONST_INT)
464     return NULL_RTX;
465
466   if (GET_MODE (tem) == VOIDmode)
467     tem = rtl_hooks.gen_lowpart_no_emit (mode, tem);
468   else
469     gcc_assert (GET_MODE (tem) == mode);
470
471   return tem;
472 }
473
474
475 \f
476
477 /* Return true if the register from reference REF is killed
478    between FROM to (but not including) TO.  */
479
480 static bool
481 local_ref_killed_between_p (struct df_ref * ref, rtx from, rtx to)
482 {
483   rtx insn;
484
485   for (insn = from; insn != to; insn = NEXT_INSN (insn))
486     {
487       struct df_ref **def_rec;
488       if (!INSN_P (insn))
489         continue;
490
491       for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
492         {
493           struct df_ref *def = *def_rec;
494           if (DF_REF_REGNO (ref) == DF_REF_REGNO (def))
495             return true;
496         }
497     }
498   return false;
499 }
500
501
502 /* Check if the given DEF is available in INSN.  This would require full
503    computation of available expressions; we check only restricted conditions:
504    - if DEF is the sole definition of its register, go ahead;
505    - in the same basic block, we check for no definitions killing the
506      definition of DEF_INSN;
507    - if USE's basic block has DEF's basic block as the sole predecessor,
508      we check if the definition is killed after DEF_INSN or before
509      TARGET_INSN insn, in their respective basic blocks.  */
510 static bool
511 use_killed_between (struct df_ref *use, rtx def_insn, rtx target_insn)
512 {
513   basic_block def_bb = BLOCK_FOR_INSN (def_insn);
514   basic_block target_bb = BLOCK_FOR_INSN (target_insn);
515   int regno;
516   struct df_ref * def;
517
518   /* In some obscure situations we can have a def reaching a use
519      that is _before_ the def.  In other words the def does not
520      dominate the use even though the use and def are in the same
521      basic block.  This can happen when a register may be used
522      uninitialized in a loop.  In such cases, we must assume that
523      DEF is not available.  */
524   if (def_bb == target_bb
525       ? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn)
526       : !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb))
527     return true;
528
529   /* Check if the reg in USE has only one definition.  We already
530      know that this definition reaches use, or we wouldn't be here.  */
531   regno = DF_REF_REGNO (use);
532   def = DF_REG_DEF_CHAIN (regno);
533   if (def && (def->next_reg == NULL))
534     return false;
535
536   /* Check locally if we are in the same basic block.  */
537   if (def_bb == target_bb)
538     return local_ref_killed_between_p (use, def_insn, target_insn);
539
540   /* Finally, if DEF_BB is the sole predecessor of TARGET_BB.  */
541   if (single_pred_p (target_bb)
542       && single_pred (target_bb) == def_bb)
543     {
544       struct df_ref *x;
545
546       /* See if USE is killed between DEF_INSN and the last insn in the
547          basic block containing DEF_INSN.  */
548       x = df_bb_regno_last_def_find (def_bb, regno);
549       if (x && DF_INSN_LUID (x->insn) >= DF_INSN_LUID (def_insn))
550         return true;
551
552       /* See if USE is killed between TARGET_INSN and the first insn in the
553          basic block containing TARGET_INSN.  */
554       x = df_bb_regno_first_def_find (target_bb, regno);
555       if (x && DF_INSN_LUID (x->insn) < DF_INSN_LUID (target_insn))
556         return true;
557
558       return false;
559     }
560
561   /* Otherwise assume the worst case.  */
562   return true;
563 }
564
565
566 /* Check if all uses in DEF_INSN can be used in TARGET_INSN.  This
567    would require full computation of available expressions;
568    we check only restricted conditions, see use_killed_between.  */
569 static bool
570 all_uses_available_at (rtx def_insn, rtx target_insn)
571 {
572   struct df_ref **use_rec;
573   rtx def_set = single_set (def_insn);
574
575   gcc_assert (def_set);
576
577   /* If target_insn comes right after def_insn, which is very common
578      for addresses, we can use a quicker test.  */
579   if (NEXT_INSN (def_insn) == target_insn
580       && REG_P (SET_DEST (def_set)))
581     {
582       rtx def_reg = SET_DEST (def_set);
583
584       /* If the insn uses the reg that it defines, the substitution is
585          invalid.  */
586       for (use_rec = DF_INSN_USES (def_insn); *use_rec; use_rec++)
587         {
588           struct df_ref *use = *use_rec;
589           if (rtx_equal_p (DF_REF_REG (use), def_reg))
590             return false;
591         }
592       for (use_rec = DF_INSN_EQ_USES (def_insn); *use_rec; use_rec++)
593         {
594           struct df_ref *use = *use_rec;
595           if (rtx_equal_p (use->reg, def_reg))
596             return false;
597         }
598     }
599   else
600     {
601       /* Look at all the uses of DEF_INSN, and see if they are not
602          killed between DEF_INSN and TARGET_INSN.  */
603       for (use_rec = DF_INSN_USES (def_insn); *use_rec; use_rec++)
604         {
605           struct df_ref *use = *use_rec;
606           if (use_killed_between (use, def_insn, target_insn))
607             return false;
608         }
609       for (use_rec = DF_INSN_EQ_USES (def_insn); *use_rec; use_rec++)
610         {
611           struct df_ref *use = *use_rec;
612           if (use_killed_between (use, def_insn, target_insn))
613             return false;
614         }
615     }
616
617   return true;
618 }
619
620 \f
621 struct find_occurrence_data
622 {
623   rtx find;
624   rtx *retval;
625 };
626
627 /* Callback for for_each_rtx, used in find_occurrence.
628    See if PX is the rtx we have to find.  Return 1 to stop for_each_rtx
629    if successful, or 0 to continue traversing otherwise.  */
630
631 static int
632 find_occurrence_callback (rtx *px, void *data)
633 {
634   struct find_occurrence_data *fod = (struct find_occurrence_data *) data;
635   rtx x = *px;
636   rtx find = fod->find;
637
638   if (x == find)
639     {
640       fod->retval = px;
641       return 1;
642     }
643
644   return 0;
645 }
646
647 /* Return a pointer to one of the occurrences of register FIND in *PX.  */
648
649 static rtx *
650 find_occurrence (rtx *px, rtx find)
651 {
652   struct find_occurrence_data data;
653
654   gcc_assert (REG_P (find)
655               || (GET_CODE (find) == SUBREG
656                   && REG_P (SUBREG_REG (find))));
657
658   data.find = find;
659   data.retval = NULL;
660   for_each_rtx (px, find_occurrence_callback, &data);
661   return data.retval;
662 }
663
664 \f
665 /* Inside INSN, the expression rooted at *LOC has been changed, moving some
666    uses from USE_VEC.  Find those that are present, and create new items
667    in the data flow object of the pass.  Mark any new uses as having the
668    given TYPE.  */
669 static void
670 update_df (rtx insn, rtx *loc, struct df_ref **use_rec, enum df_ref_type type,
671            int new_flags)
672 {
673   bool changed = false;
674
675   /* Add a use for the registers that were propagated.  */
676   while (*use_rec)
677     {
678       struct df_ref *use = *use_rec;
679       struct df_ref *orig_use = use, *new_use;
680       int width = -1;
681       int offset = -1;
682       enum machine_mode mode = 0;
683       rtx *new_loc = find_occurrence (loc, DF_REF_REG (orig_use));
684       use_rec++;
685
686       if (!new_loc)
687         continue;
688
689       if (DF_REF_FLAGS_IS_SET (orig_use, DF_REF_SIGN_EXTRACT | DF_REF_ZERO_EXTRACT))
690         {
691           width = DF_REF_EXTRACT_WIDTH (orig_use);
692           offset = DF_REF_EXTRACT_OFFSET (orig_use);
693           mode = DF_REF_EXTRACT_MODE (orig_use);
694         }
695
696       /* Add a new insn use.  Use the original type, because it says if the
697          use was within a MEM.  */
698       new_use = df_ref_create (DF_REF_REG (orig_use), new_loc,
699                                insn, BLOCK_FOR_INSN (insn),
700                                type, DF_REF_FLAGS (orig_use) | new_flags, 
701                                width, offset, mode);
702
703       /* Set up the use-def chain.  */
704       df_chain_copy (new_use, DF_REF_CHAIN (orig_use));
705       changed = true;
706     }
707   if (changed)
708     df_insn_rescan (insn);
709 }
710
711
712 /* Try substituting NEW into LOC, which originated from forward propagation
713    of USE's value from DEF_INSN.  SET_REG_EQUAL says whether we are
714    substituting the whole SET_SRC, so we can set a REG_EQUAL note if the
715    new insn is not recognized.  Return whether the substitution was
716    performed.  */
717
718 static bool
719 try_fwprop_subst (struct df_ref *use, rtx *loc, rtx new, rtx def_insn, bool set_reg_equal)
720 {
721   rtx insn = DF_REF_INSN (use);
722   enum df_ref_type type = DF_REF_TYPE (use);
723   int flags = DF_REF_FLAGS (use);
724   rtx set = single_set (insn);
725   int old_cost = rtx_cost (SET_SRC (set), SET);
726   bool ok;
727
728   if (dump_file)
729     {
730       fprintf (dump_file, "\nIn insn %d, replacing\n ", INSN_UID (insn));
731       print_inline_rtx (dump_file, *loc, 2);
732       fprintf (dump_file, "\n with ");
733       print_inline_rtx (dump_file, new, 2);
734       fprintf (dump_file, "\n");
735     }
736
737   validate_unshare_change (insn, loc, new, true);
738   if (!verify_changes (0))
739     {
740       if (dump_file)
741         fprintf (dump_file, "Changes to insn %d not recognized\n",
742                  INSN_UID (insn));
743       ok = false;
744     }
745
746   else if (DF_REF_TYPE (use) == DF_REF_REG_USE
747            && rtx_cost (SET_SRC (set), SET) > old_cost)
748     {
749       if (dump_file)
750         fprintf (dump_file, "Changes to insn %d not profitable\n",
751                  INSN_UID (insn));
752       ok = false;
753     }
754
755   else
756     {
757       if (dump_file)
758         fprintf (dump_file, "Changed insn %d\n", INSN_UID (insn));
759       ok = true;
760     }
761
762   if (ok)
763     {
764       confirm_change_group ();
765       num_changes++;
766
767       df_ref_remove (use);
768       if (!CONSTANT_P (new))
769         {
770           update_df (insn, loc, DF_INSN_USES (def_insn), type, flags);
771           update_df (insn, loc, DF_INSN_EQ_USES (def_insn), type, flags);
772         }
773     }
774   else
775     {
776       cancel_changes (0);
777
778       /* Can also record a simplified value in a REG_EQUAL note,
779          making a new one if one does not already exist.  */
780       if (set_reg_equal)
781         {
782           if (dump_file)
783             fprintf (dump_file, " Setting REG_EQUAL note\n");
784
785           set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new));
786
787           /* ??? Is this still necessary if we add the note through
788              set_unique_reg_note?  */
789           if (!CONSTANT_P (new))
790             {
791               update_df (insn, loc, DF_INSN_USES (def_insn),
792                          type, DF_REF_IN_NOTE);
793               update_df (insn, loc, DF_INSN_EQ_USES (def_insn),
794                          type, DF_REF_IN_NOTE);
795             }
796         }
797     }
798
799   return ok;
800 }
801
802
803 /* If USE is a paradoxical subreg, see if it can be replaced by a pseudo.  */
804
805 static bool
806 forward_propagate_subreg (struct df_ref *use, rtx def_insn, rtx def_set)
807 {
808   rtx use_reg = DF_REF_REG (use);
809   rtx use_insn, src;
810
811   /* Only consider paradoxical subregs... */
812   enum machine_mode use_mode = GET_MODE (use_reg);
813   if (GET_CODE (use_reg) != SUBREG
814       || !REG_P (SET_DEST (def_set))
815       || GET_MODE_SIZE (use_mode)
816          <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (use_reg))))
817     return false;
818
819   /* If this is a paradoxical SUBREG, we have no idea what value the
820      extra bits would have.  However, if the operand is equivalent to
821      a SUBREG whose operand is the same as our mode, and all the modes
822      are within a word, we can just use the inner operand because
823      these SUBREGs just say how to treat the register.  */
824   use_insn = DF_REF_INSN (use);
825   src = SET_SRC (def_set);
826   if (GET_CODE (src) == SUBREG
827       && REG_P (SUBREG_REG (src))
828       && GET_MODE (SUBREG_REG (src)) == use_mode
829       && subreg_lowpart_p (src)
830       && all_uses_available_at (def_insn, use_insn))
831     return try_fwprop_subst (use, DF_REF_LOC (use), SUBREG_REG (src),
832                              def_insn, false);
833   else
834     return false;
835 }
836
837 /* Try to replace USE with SRC (defined in DEF_INSN) and simplify the
838    result.  */
839
840 static bool
841 forward_propagate_and_simplify (struct df_ref *use, rtx def_insn, rtx def_set)
842 {
843   rtx use_insn = DF_REF_INSN (use);
844   rtx use_set = single_set (use_insn);
845   rtx src, reg, new, *loc;
846   bool set_reg_equal;
847   enum machine_mode mode;
848
849   if (!use_set)
850     return false;
851
852   /* Do not propagate into PC, CC0, etc.  */
853   if (GET_MODE (SET_DEST (use_set)) == VOIDmode)
854     return false;
855
856   /* If def and use are subreg, check if they match.  */
857   reg = DF_REF_REG (use);
858   if (GET_CODE (reg) == SUBREG
859       && GET_CODE (SET_DEST (def_set)) == SUBREG
860       && (SUBREG_BYTE (SET_DEST (def_set)) != SUBREG_BYTE (reg)
861           || GET_MODE (SET_DEST (def_set)) != GET_MODE (reg)))
862     return false;
863
864   /* Check if the def had a subreg, but the use has the whole reg.  */
865   if (REG_P (reg) && GET_CODE (SET_DEST (def_set)) == SUBREG)
866     return false;
867
868   /* Check if the use has a subreg, but the def had the whole reg.  Unlike the
869      previous case, the optimization is possible and often useful indeed.  */
870   if (GET_CODE (reg) == SUBREG && REG_P (SET_DEST (def_set)))
871     reg = SUBREG_REG (reg);
872
873   /* Check if the substitution is valid (last, because it's the most
874      expensive check!).  */
875   src = SET_SRC (def_set);
876   if (!CONSTANT_P (src) && !all_uses_available_at (def_insn, use_insn))
877     return false;
878
879   /* Check if the def is loading something from the constant pool; in this
880      case we would undo optimization such as compress_float_constant.
881      Still, we can set a REG_EQUAL note.  */
882   if (MEM_P (src) && MEM_READONLY_P (src))
883     {
884       rtx x = avoid_constant_pool_reference (src);
885       if (x != src)
886         {
887           rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
888           rtx old = note ? XEXP (note, 0) : SET_SRC (use_set);
889           rtx new = simplify_replace_rtx (old, src, x);
890           if (old != new)
891             set_unique_reg_note (use_insn, REG_EQUAL, copy_rtx (new));
892         }
893       return false;
894     }
895
896   /* Else try simplifying.  */
897
898   if (DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE)
899     {
900       loc = &SET_DEST (use_set);
901       set_reg_equal = false;
902     }
903   else
904     {
905       rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
906       if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
907         loc = &XEXP (note, 0);
908       else
909         loc = &SET_SRC (use_set);
910
911       /* Do not replace an existing REG_EQUAL note if the insn is not
912          recognized.  Either we're already replacing in the note, or
913          we'll separately try plugging the definition in the note and
914          simplifying.  */
915       set_reg_equal = (note == NULL_RTX);
916     }
917
918   if (GET_MODE (*loc) == VOIDmode)
919     mode = GET_MODE (SET_DEST (use_set));
920   else
921     mode = GET_MODE (*loc);
922
923   new = propagate_rtx (*loc, mode, reg, src);
924
925   if (!new)
926     return false;
927
928   return try_fwprop_subst (use, loc, new, def_insn, set_reg_equal);
929 }
930
931
932 /* Given a use USE of an insn, if it has a single reaching
933    definition, try to forward propagate it into that insn.  */
934
935 static void
936 forward_propagate_into (struct df_ref *use)
937 {
938   struct df_link *defs;
939   struct df_ref *def;
940   rtx def_insn, def_set, use_insn;
941   rtx parent;
942
943   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
944     return;
945   if (DF_REF_IS_ARTIFICIAL (use))
946     return;
947
948   /* Only consider uses that have a single definition.  */
949   defs = DF_REF_CHAIN (use);
950   if (!defs || defs->next)
951     return;
952
953   def = defs->ref;
954   if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
955     return;
956   if (DF_REF_IS_ARTIFICIAL (def))
957     return;
958
959   /* Do not propagate loop invariant definitions inside the loop.  */
960   if (DF_REF_BB (def)->loop_father != DF_REF_BB (use)->loop_father)
961     return;
962
963   /* Check if the use is still present in the insn!  */
964   use_insn = DF_REF_INSN (use);
965   if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
966     parent = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
967   else
968     parent = PATTERN (use_insn);
969
970   if (!reg_mentioned_p (DF_REF_REG (use), parent))
971     return;
972
973   def_insn = DF_REF_INSN (def);
974   if (multiple_sets (def_insn))
975     return;
976   def_set = single_set (def_insn);
977   if (!def_set)
978     return;
979
980   /* Only try one kind of propagation.  If two are possible, we'll
981      do it on the following iterations.  */
982   if (!forward_propagate_and_simplify (use, def_insn, def_set))
983     forward_propagate_subreg (use, def_insn, def_set);
984 }
985
986 \f
987 static void
988 fwprop_init (void)
989 {
990   num_changes = 0;
991   calculate_dominance_info (CDI_DOMINATORS);
992
993   /* We do not always want to propagate into loops, so we have to find
994      loops and be careful about them.  But we have to call flow_loops_find
995      before df_analyze, because flow_loops_find may introduce new jump
996      insns (sadly) if we are not working in cfglayout mode.  */
997   loop_optimizer_init (0);
998
999   /* Now set up the dataflow problem (we only want use-def chains) and
1000      put the dataflow solver to work.  */
1001   df_set_flags (DF_EQ_NOTES);
1002   df_chain_add_problem (DF_UD_CHAIN);
1003   df_analyze ();
1004   df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
1005   df_set_flags (DF_DEFER_INSN_RESCAN);
1006 }
1007
1008 static void
1009 fwprop_done (void)
1010 {
1011   loop_optimizer_finalize ();
1012
1013   free_dominance_info (CDI_DOMINATORS);
1014   cleanup_cfg (0);
1015   delete_trivially_dead_insns (get_insns (), max_reg_num ());
1016
1017   if (dump_file)
1018     fprintf (dump_file,
1019              "\nNumber of successful forward propagations: %d\n\n",
1020              num_changes);
1021 }
1022
1023
1024
1025 /* Main entry point.  */
1026
1027 static bool
1028 gate_fwprop (void)
1029 {
1030   return optimize > 0 && flag_forward_propagate;
1031 }
1032
1033 static unsigned int
1034 fwprop (void)
1035 {
1036   unsigned i;
1037
1038   fwprop_init ();
1039
1040   /* Go through all the uses.  update_df will create new ones at the
1041      end, and we'll go through them as well.
1042
1043      Do not forward propagate addresses into loops until after unrolling.
1044      CSE did so because it was able to fix its own mess, but we are not.  */
1045
1046   for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1047     {
1048       struct df_ref *use = DF_USES_GET (i);
1049       if (use)
1050         if (DF_REF_TYPE (use) == DF_REF_REG_USE
1051             || DF_REF_BB (use)->loop_father == NULL)
1052           forward_propagate_into (use);
1053     }
1054
1055   fwprop_done ();
1056   return 0;
1057 }
1058
1059 struct rtl_opt_pass pass_rtl_fwprop =
1060 {
1061  {
1062   RTL_PASS,
1063   "fwprop1",                            /* name */
1064   gate_fwprop,                          /* gate */
1065   fwprop,                               /* execute */
1066   NULL,                                 /* sub */
1067   NULL,                                 /* next */
1068   0,                                    /* static_pass_number */
1069   TV_FWPROP,                            /* tv_id */
1070   0,                                    /* properties_required */
1071   0,                                    /* properties_provided */
1072   0,                                    /* properties_destroyed */
1073   0,                                    /* todo_flags_start */
1074   TODO_df_finish | TODO_verify_rtl_sharing |
1075   TODO_dump_func                        /* todo_flags_finish */
1076  }
1077 };
1078
1079 static unsigned int
1080 fwprop_addr (void)
1081 {
1082   unsigned i;
1083   fwprop_init ();
1084
1085   /* Go through all the uses.  update_df will create new ones at the
1086      end, and we'll go through them as well.  */
1087   df_set_flags (DF_DEFER_INSN_RESCAN);
1088
1089   for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1090     {
1091       struct df_ref *use = DF_USES_GET (i);
1092       if (use)
1093         if (DF_REF_TYPE (use) != DF_REF_REG_USE
1094             && DF_REF_BB (use)->loop_father != NULL)
1095           forward_propagate_into (use);
1096     }
1097
1098   fwprop_done ();
1099
1100   return 0;
1101 }
1102
1103 struct rtl_opt_pass pass_rtl_fwprop_addr =
1104 {
1105  {
1106   RTL_PASS,
1107   "fwprop2",                            /* name */
1108   gate_fwprop,                          /* gate */
1109   fwprop_addr,                          /* execute */
1110   NULL,                                 /* sub */
1111   NULL,                                 /* next */
1112   0,                                    /* static_pass_number */
1113   TV_FWPROP,                            /* tv_id */
1114   0,                                    /* properties_required */
1115   0,                                    /* properties_provided */
1116   0,                                    /* properties_destroyed */
1117   0,                                    /* todo_flags_start */
1118   TODO_df_finish | TODO_verify_rtl_sharing |
1119   TODO_dump_func                        /* todo_flags_finish */
1120  }
1121 };