OSDN Git Service

2009-05-07 Paolo Bonzini <bonzini@gnu.org>
[pf3gnuchains/gcc-fork.git] / gcc / regcprop.c
1 /* Copy propagation on hard registers for the GNU compiler.
2    Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
3    Free Software Foundation, Inc.
4
5    This file is part of GCC.
6
7    GCC is free software; you can redistribute it and/or modify it
8    under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 3, or (at your option)
10    any later version.
11
12    GCC is distributed in the hope that it will be useful, but WITHOUT
13    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
15    License 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 "rtl.h"
26 #include "tm_p.h"
27 #include "insn-config.h"
28 #include "regs.h"
29 #include "addresses.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
32 #include "reload.h"
33 #include "output.h"
34 #include "function.h"
35 #include "recog.h"
36 #include "flags.h"
37 #include "toplev.h"
38 #include "obstack.h"
39 #include "timevar.h"
40 #include "tree-pass.h"
41 #include "df.h"
42
43 /* The following code does forward propagation of hard register copies.
44    The object is to eliminate as many dependencies as possible, so that
45    we have the most scheduling freedom.  As a side effect, we also clean
46    up some silly register allocation decisions made by reload.  This
47    code may be obsoleted by a new register allocator.  */
48
49 /* For each register, we have a list of registers that contain the same
50    value.  The OLDEST_REGNO field points to the head of the list, and
51    the NEXT_REGNO field runs through the list.  The MODE field indicates
52    what mode the data is known to be in; this field is VOIDmode when the
53    register is not known to contain valid data.  */
54
55 struct value_data_entry
56 {
57   enum machine_mode mode;
58   unsigned int oldest_regno;
59   unsigned int next_regno;
60 };
61
62 struct value_data
63 {
64   struct value_data_entry e[FIRST_PSEUDO_REGISTER];
65   unsigned int max_value_regs;
66 };
67
68 static void kill_value_one_regno (unsigned, struct value_data *);
69 static void kill_value_regno (unsigned, unsigned, struct value_data *);
70 static void kill_value (rtx, struct value_data *);
71 static void set_value_regno (unsigned, enum machine_mode, struct value_data *);
72 static void init_value_data (struct value_data *);
73 static void kill_clobbered_value (rtx, const_rtx, void *);
74 static void kill_set_value (rtx, const_rtx, void *);
75 static int kill_autoinc_value (rtx *, void *);
76 static void copy_value (rtx, rtx, struct value_data *);
77 static bool mode_change_ok (enum machine_mode, enum machine_mode,
78                             unsigned int);
79 static rtx maybe_mode_change (enum machine_mode, enum machine_mode,
80                               enum machine_mode, unsigned int, unsigned int);
81 static rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *);
82 static bool replace_oldest_value_reg (rtx *, enum reg_class, rtx,
83                                       struct value_data *);
84 static bool replace_oldest_value_addr (rtx *, enum reg_class,
85                                        enum machine_mode, rtx,
86                                        struct value_data *);
87 static bool replace_oldest_value_mem (rtx, rtx, struct value_data *);
88 static bool copyprop_hardreg_forward_1 (basic_block, struct value_data *);
89 extern void debug_value_data (struct value_data *);
90 #ifdef ENABLE_CHECKING
91 static void validate_value_data (struct value_data *);
92 #endif
93
94 /* Kill register REGNO.  This involves removing it from any value
95    lists, and resetting the value mode to VOIDmode.  This is only a
96    helper function; it does not handle any hard registers overlapping
97    with REGNO.  */
98
99 static void
100 kill_value_one_regno (unsigned int regno, struct value_data *vd)
101 {
102   unsigned int i, next;
103
104   if (vd->e[regno].oldest_regno != regno)
105     {
106       for (i = vd->e[regno].oldest_regno;
107            vd->e[i].next_regno != regno;
108            i = vd->e[i].next_regno)
109         continue;
110       vd->e[i].next_regno = vd->e[regno].next_regno;
111     }
112   else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM)
113     {
114       for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno)
115         vd->e[i].oldest_regno = next;
116     }
117
118   vd->e[regno].mode = VOIDmode;
119   vd->e[regno].oldest_regno = regno;
120   vd->e[regno].next_regno = INVALID_REGNUM;
121
122 #ifdef ENABLE_CHECKING
123   validate_value_data (vd);
124 #endif
125 }
126
127 /* Kill the value in register REGNO for NREGS, and any other registers
128    whose values overlap.  */
129
130 static void
131 kill_value_regno (unsigned int regno, unsigned int nregs,
132                   struct value_data *vd)
133 {
134   unsigned int j;
135
136   /* Kill the value we're told to kill.  */
137   for (j = 0; j < nregs; ++j)
138     kill_value_one_regno (regno + j, vd);
139
140   /* Kill everything that overlapped what we're told to kill.  */
141   if (regno < vd->max_value_regs)
142     j = 0;
143   else
144     j = regno - vd->max_value_regs;
145   for (; j < regno; ++j)
146     {
147       unsigned int i, n;
148       if (vd->e[j].mode == VOIDmode)
149         continue;
150       n = hard_regno_nregs[j][vd->e[j].mode];
151       if (j + n > regno)
152         for (i = 0; i < n; ++i)
153           kill_value_one_regno (j + i, vd);
154     }
155 }
156
157 /* Kill X.  This is a convenience function wrapping kill_value_regno
158    so that we mind the mode the register is in.  */
159
160 static void
161 kill_value (rtx x, struct value_data *vd)
162 {
163   rtx orig_rtx = x;
164
165   if (GET_CODE (x) == SUBREG)
166     {
167       x = simplify_subreg (GET_MODE (x), SUBREG_REG (x),
168                            GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
169       if (x == NULL_RTX)
170         x = SUBREG_REG (orig_rtx);
171     }
172   if (REG_P (x))
173     {
174       unsigned int regno = REGNO (x);
175       unsigned int n = hard_regno_nregs[regno][GET_MODE (x)];
176
177       kill_value_regno (regno, n, vd);
178     }
179 }
180
181 /* Remember that REGNO is valid in MODE.  */
182
183 static void
184 set_value_regno (unsigned int regno, enum machine_mode mode,
185                  struct value_data *vd)
186 {
187   unsigned int nregs;
188
189   vd->e[regno].mode = mode;
190
191   nregs = hard_regno_nregs[regno][mode];
192   if (nregs > vd->max_value_regs)
193     vd->max_value_regs = nregs;
194 }
195
196 /* Initialize VD such that there are no known relationships between regs.  */
197
198 static void
199 init_value_data (struct value_data *vd)
200 {
201   int i;
202   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
203     {
204       vd->e[i].mode = VOIDmode;
205       vd->e[i].oldest_regno = i;
206       vd->e[i].next_regno = INVALID_REGNUM;
207     }
208   vd->max_value_regs = 0;
209 }
210
211 /* Called through note_stores.  If X is clobbered, kill its value.  */
212
213 static void
214 kill_clobbered_value (rtx x, const_rtx set, void *data)
215 {
216   struct value_data *const vd = (struct value_data *) data;
217   if (GET_CODE (set) == CLOBBER)
218     kill_value (x, vd);
219 }
220
221 /* Called through note_stores.  If X is set, not clobbered, kill its
222    current value and install it as the root of its own value list.  */
223
224 static void
225 kill_set_value (rtx x, const_rtx set, void *data)
226 {
227   struct value_data *const vd = (struct value_data *) data;
228   if (GET_CODE (set) != CLOBBER)
229     {
230       kill_value (x, vd);
231       if (REG_P (x))
232         set_value_regno (REGNO (x), GET_MODE (x), vd);
233     }
234 }
235
236 /* Called through for_each_rtx.  Kill any register used as the base of an
237    auto-increment expression, and install that register as the root of its
238    own value list.  */
239
240 static int
241 kill_autoinc_value (rtx *px, void *data)
242 {
243   rtx x = *px;
244   struct value_data *const vd = (struct value_data *) data;
245
246   if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
247     {
248       x = XEXP (x, 0);
249       kill_value (x, vd);
250       set_value_regno (REGNO (x), Pmode, vd);
251       return -1;
252     }
253
254   return 0;
255 }
256
257 /* Assert that SRC has been copied to DEST.  Adjust the data structures
258    to reflect that SRC contains an older copy of the shared value.  */
259
260 static void
261 copy_value (rtx dest, rtx src, struct value_data *vd)
262 {
263   unsigned int dr = REGNO (dest);
264   unsigned int sr = REGNO (src);
265   unsigned int dn, sn;
266   unsigned int i;
267
268   /* ??? At present, it's possible to see noop sets.  It'd be nice if
269      this were cleaned up beforehand...  */
270   if (sr == dr)
271     return;
272
273   /* Do not propagate copies to the stack pointer, as that can leave
274      memory accesses with no scheduling dependency on the stack update.  */
275   if (dr == STACK_POINTER_REGNUM)
276     return;
277
278   /* Likewise with the frame pointer, if we're using one.  */
279   if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM)
280     return;
281
282   /* Do not propagate copies to fixed or global registers, patterns
283      can be relying to see particular fixed register or users can
284      expect the chosen global register in asm.  */
285   if (fixed_regs[dr] || global_regs[dr])
286     return;
287
288   /* If SRC and DEST overlap, don't record anything.  */
289   dn = hard_regno_nregs[dr][GET_MODE (dest)];
290   sn = hard_regno_nregs[sr][GET_MODE (dest)];
291   if ((dr > sr && dr < sr + sn)
292       || (sr > dr && sr < dr + dn))
293     return;
294
295   /* If SRC had no assigned mode (i.e. we didn't know it was live)
296      assign it now and assume the value came from an input argument
297      or somesuch.  */
298   if (vd->e[sr].mode == VOIDmode)
299     set_value_regno (sr, vd->e[dr].mode, vd);
300
301   /* If we are narrowing the input to a smaller number of hard regs,
302      and it is in big endian, we are really extracting a high part.
303      Since we generally associate a low part of a value with the value itself,
304      we must not do the same for the high part.
305      Note we can still get low parts for the same mode combination through
306      a two-step copy involving differently sized hard regs.
307      Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
308      (set (reg:DI r0) (reg:DI fr0))
309      (set (reg:SI fr2) (reg:SI r0))
310      loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
311      (set (reg:SI fr2) (reg:SI fr0))
312      loads the high part of (reg:DI fr0) into fr2.
313
314      We can't properly represent the latter case in our tables, so don't
315      record anything then.  */
316   else if (sn < (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode]
317            && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD
318                ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
319     return;
320
321   /* If SRC had been assigned a mode narrower than the copy, we can't
322      link DEST into the chain, because not all of the pieces of the
323      copy came from oldest_regno.  */
324   else if (sn > (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode])
325     return;
326
327   /* Link DR at the end of the value chain used by SR.  */
328
329   vd->e[dr].oldest_regno = vd->e[sr].oldest_regno;
330
331   for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno)
332     continue;
333   vd->e[i].next_regno = dr;
334
335 #ifdef ENABLE_CHECKING
336   validate_value_data (vd);
337 #endif
338 }
339
340 /* Return true if a mode change from ORIG to NEW is allowed for REGNO.  */
341
342 static bool
343 mode_change_ok (enum machine_mode orig_mode, enum machine_mode new_mode,
344                 unsigned int regno ATTRIBUTE_UNUSED)
345 {
346   if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode))
347     return false;
348
349 #ifdef CANNOT_CHANGE_MODE_CLASS
350   return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode);
351 #endif
352
353   return true;
354 }
355
356 /* Register REGNO was originally set in ORIG_MODE.  It - or a copy of it -
357    was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
358    in NEW_MODE.
359    Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX.  */
360
361 static rtx
362 maybe_mode_change (enum machine_mode orig_mode, enum machine_mode copy_mode,
363                    enum machine_mode new_mode, unsigned int regno,
364                    unsigned int copy_regno ATTRIBUTE_UNUSED)
365 {
366   if (GET_MODE_SIZE (copy_mode) < GET_MODE_SIZE (orig_mode)
367       && GET_MODE_SIZE (copy_mode) < GET_MODE_SIZE (new_mode))
368     return NULL_RTX;
369
370   if (orig_mode == new_mode)
371     return gen_rtx_raw_REG (new_mode, regno);
372   else if (mode_change_ok (orig_mode, new_mode, regno))
373     {
374       int copy_nregs = hard_regno_nregs[copy_regno][copy_mode];
375       int use_nregs = hard_regno_nregs[copy_regno][new_mode];
376       int copy_offset
377         = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs);
378       int offset
379         = GET_MODE_SIZE (orig_mode) - GET_MODE_SIZE (new_mode) - copy_offset;
380       int byteoffset = offset % UNITS_PER_WORD;
381       int wordoffset = offset - byteoffset;
382
383       offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0)
384                 + (BYTES_BIG_ENDIAN ? byteoffset : 0));
385       return gen_rtx_raw_REG (new_mode,
386                               regno + subreg_regno_offset (regno, orig_mode,
387                                                            offset,
388                                                            new_mode));
389     }
390   return NULL_RTX;
391 }
392
393 /* Find the oldest copy of the value contained in REGNO that is in
394    register class CL and has mode MODE.  If found, return an rtx
395    of that oldest register, otherwise return NULL.  */
396
397 static rtx
398 find_oldest_value_reg (enum reg_class cl, rtx reg, struct value_data *vd)
399 {
400   unsigned int regno = REGNO (reg);
401   enum machine_mode mode = GET_MODE (reg);
402   unsigned int i;
403
404   /* If we are accessing REG in some mode other that what we set it in,
405      make sure that the replacement is valid.  In particular, consider
406         (set (reg:DI r11) (...))
407         (set (reg:SI r9) (reg:SI r11))
408         (set (reg:SI r10) (...))
409         (set (...) (reg:DI r9))
410      Replacing r9 with r11 is invalid.  */
411   if (mode != vd->e[regno].mode)
412     {
413       if (hard_regno_nregs[regno][mode]
414           > hard_regno_nregs[regno][vd->e[regno].mode])
415         return NULL_RTX;
416     }
417
418   for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno)
419     {
420       enum machine_mode oldmode = vd->e[i].mode;
421       rtx new_rtx;
422
423       if (!in_hard_reg_set_p (reg_class_contents[cl], mode, i))
424         return NULL_RTX;
425
426       new_rtx = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno);
427       if (new_rtx)
428         {
429           ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (reg);
430           REG_ATTRS (new_rtx) = REG_ATTRS (reg);
431           REG_POINTER (new_rtx) = REG_POINTER (reg);
432           return new_rtx;
433         }
434     }
435
436   return NULL_RTX;
437 }
438
439 /* If possible, replace the register at *LOC with the oldest register
440    in register class CL.  Return true if successfully replaced.  */
441
442 static bool
443 replace_oldest_value_reg (rtx *loc, enum reg_class cl, rtx insn,
444                           struct value_data *vd)
445 {
446   rtx new_rtx = find_oldest_value_reg (cl, *loc, vd);
447   if (new_rtx)
448     {
449       if (dump_file)
450         fprintf (dump_file, "insn %u: replaced reg %u with %u\n",
451                  INSN_UID (insn), REGNO (*loc), REGNO (new_rtx));
452
453       validate_change (insn, loc, new_rtx, 1);
454       return true;
455     }
456   return false;
457 }
458
459 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
460    Adapted from find_reloads_address_1.  CL is INDEX_REG_CLASS or
461    BASE_REG_CLASS depending on how the register is being considered.  */
462
463 static bool
464 replace_oldest_value_addr (rtx *loc, enum reg_class cl,
465                            enum machine_mode mode, rtx insn,
466                            struct value_data *vd)
467 {
468   rtx x = *loc;
469   RTX_CODE code = GET_CODE (x);
470   const char *fmt;
471   int i, j;
472   bool changed = false;
473
474   switch (code)
475     {
476     case PLUS:
477       {
478         rtx orig_op0 = XEXP (x, 0);
479         rtx orig_op1 = XEXP (x, 1);
480         RTX_CODE code0 = GET_CODE (orig_op0);
481         RTX_CODE code1 = GET_CODE (orig_op1);
482         rtx op0 = orig_op0;
483         rtx op1 = orig_op1;
484         rtx *locI = NULL;
485         rtx *locB = NULL;
486         enum rtx_code index_code = SCRATCH;
487
488         if (GET_CODE (op0) == SUBREG)
489           {
490             op0 = SUBREG_REG (op0);
491             code0 = GET_CODE (op0);
492           }
493
494         if (GET_CODE (op1) == SUBREG)
495           {
496             op1 = SUBREG_REG (op1);
497             code1 = GET_CODE (op1);
498           }
499
500         if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
501             || code0 == ZERO_EXTEND || code1 == MEM)
502           {
503             locI = &XEXP (x, 0);
504             locB = &XEXP (x, 1);
505             index_code = GET_CODE (*locI);
506           }
507         else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
508                  || code1 == ZERO_EXTEND || code0 == MEM)
509           {
510             locI = &XEXP (x, 1);
511             locB = &XEXP (x, 0);
512             index_code = GET_CODE (*locI);
513           }
514         else if (code0 == CONST_INT || code0 == CONST
515                  || code0 == SYMBOL_REF || code0 == LABEL_REF)
516           {
517             locB = &XEXP (x, 1);
518             index_code = GET_CODE (XEXP (x, 0));
519           }
520         else if (code1 == CONST_INT || code1 == CONST
521                  || code1 == SYMBOL_REF || code1 == LABEL_REF)
522           {
523             locB = &XEXP (x, 0);
524             index_code = GET_CODE (XEXP (x, 1));
525           }
526         else if (code0 == REG && code1 == REG)
527           {
528             int index_op;
529             unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
530
531             if (REGNO_OK_FOR_INDEX_P (regno1)
532                 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
533               index_op = 1;
534             else if (REGNO_OK_FOR_INDEX_P (regno0)
535                      && regno_ok_for_base_p (regno1, mode, PLUS, REG))
536               index_op = 0;
537             else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
538                      || REGNO_OK_FOR_INDEX_P (regno1))
539               index_op = 1;
540             else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
541               index_op = 0;
542             else
543               index_op = 1;
544
545             locI = &XEXP (x, index_op);
546             locB = &XEXP (x, !index_op);
547             index_code = GET_CODE (*locI);
548           }
549         else if (code0 == REG)
550           {
551             locI = &XEXP (x, 0);
552             locB = &XEXP (x, 1);
553             index_code = GET_CODE (*locI);
554           }
555         else if (code1 == REG)
556           {
557             locI = &XEXP (x, 1);
558             locB = &XEXP (x, 0);
559             index_code = GET_CODE (*locI);
560           }
561
562         if (locI)
563           changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode,
564                                                 insn, vd);
565         if (locB)
566           changed |= replace_oldest_value_addr (locB,
567                                                 base_reg_class (mode, PLUS,
568                                                                 index_code),
569                                                 mode, insn, vd);
570         return changed;
571       }
572
573     case POST_INC:
574     case POST_DEC:
575     case POST_MODIFY:
576     case PRE_INC:
577     case PRE_DEC:
578     case PRE_MODIFY:
579       return false;
580
581     case MEM:
582       return replace_oldest_value_mem (x, insn, vd);
583
584     case REG:
585       return replace_oldest_value_reg (loc, cl, insn, vd);
586
587     default:
588       break;
589     }
590
591   fmt = GET_RTX_FORMAT (code);
592   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
593     {
594       if (fmt[i] == 'e')
595         changed |= replace_oldest_value_addr (&XEXP (x, i), cl, mode,
596                                               insn, vd);
597       else if (fmt[i] == 'E')
598         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
599           changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), cl,
600                                                 mode, insn, vd);
601     }
602
603   return changed;
604 }
605
606 /* Similar to replace_oldest_value_reg, but X contains a memory.  */
607
608 static bool
609 replace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd)
610 {
611   return replace_oldest_value_addr (&XEXP (x, 0),
612                                     base_reg_class (GET_MODE (x), MEM,
613                                                     SCRATCH),
614                                     GET_MODE (x), insn, vd);
615 }
616
617 /* Perform the forward copy propagation on basic block BB.  */
618
619 static bool
620 copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd)
621 {
622   bool changed = false;
623   rtx insn;
624
625   for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
626     {
627       int n_ops, i, alt, predicated;
628       bool is_asm, any_replacements;
629       rtx set;
630       bool replaced[MAX_RECOG_OPERANDS];
631
632       if (! INSN_P (insn))
633         {
634           if (insn == BB_END (bb))
635             break;
636           else
637             continue;
638         }
639
640       set = single_set (insn);
641       extract_insn (insn);
642       if (! constrain_operands (1))
643         fatal_insn_not_found (insn);
644       preprocess_constraints ();
645       alt = which_alternative;
646       n_ops = recog_data.n_operands;
647       is_asm = asm_noperands (PATTERN (insn)) >= 0;
648
649       /* Simplify the code below by rewriting things to reflect
650          matching constraints.  Also promote OP_OUT to OP_INOUT
651          in predicated instructions.  */
652
653       predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
654       for (i = 0; i < n_ops; ++i)
655         {
656           int matches = recog_op_alt[i][alt].matches;
657           if (matches >= 0)
658             recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
659           if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
660               || (predicated && recog_data.operand_type[i] == OP_OUT))
661             recog_data.operand_type[i] = OP_INOUT;
662         }
663
664       /* For each earlyclobber operand, zap the value data.  */
665       for (i = 0; i < n_ops; i++)
666         if (recog_op_alt[i][alt].earlyclobber)
667           kill_value (recog_data.operand[i], vd);
668
669       /* Within asms, a clobber cannot overlap inputs or outputs.
670          I wouldn't think this were true for regular insns, but
671          scan_rtx treats them like that...  */
672       note_stores (PATTERN (insn), kill_clobbered_value, vd);
673
674       /* Kill all auto-incremented values.  */
675       /* ??? REG_INC is useless, since stack pushes aren't done that way.  */
676       for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd);
677
678       /* Kill all early-clobbered operands.  */
679       for (i = 0; i < n_ops; i++)
680         if (recog_op_alt[i][alt].earlyclobber)
681           kill_value (recog_data.operand[i], vd);
682
683       /* Special-case plain move instructions, since we may well
684          be able to do the move from a different register class.  */
685       if (set && REG_P (SET_SRC (set)))
686         {
687           rtx src = SET_SRC (set);
688           unsigned int regno = REGNO (src);
689           enum machine_mode mode = GET_MODE (src);
690           unsigned int i;
691           rtx new_rtx;
692
693           /* If we are accessing SRC in some mode other that what we
694              set it in, make sure that the replacement is valid.  */
695           if (mode != vd->e[regno].mode)
696             {
697               if (hard_regno_nregs[regno][mode]
698                   > hard_regno_nregs[regno][vd->e[regno].mode])
699                 goto no_move_special_case;
700             }
701
702           /* If the destination is also a register, try to find a source
703              register in the same class.  */
704           if (REG_P (SET_DEST (set)))
705             {
706               new_rtx = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd);
707               if (new_rtx && validate_change (insn, &SET_SRC (set), new_rtx, 0))
708                 {
709                   if (dump_file)
710                     fprintf (dump_file,
711                              "insn %u: replaced reg %u with %u\n",
712                              INSN_UID (insn), regno, REGNO (new_rtx));
713                   changed = true;
714                   goto did_replacement;
715                 }
716             }
717
718           /* Otherwise, try all valid registers and see if its valid.  */
719           for (i = vd->e[regno].oldest_regno; i != regno;
720                i = vd->e[i].next_regno)
721             {
722               new_rtx = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode,
723                                        mode, i, regno);
724               if (new_rtx != NULL_RTX)
725                 {
726                   if (validate_change (insn, &SET_SRC (set), new_rtx, 0))
727                     {
728                       ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (src);
729                       REG_ATTRS (new_rtx) = REG_ATTRS (src);
730                       REG_POINTER (new_rtx) = REG_POINTER (src);
731                       if (dump_file)
732                         fprintf (dump_file,
733                                  "insn %u: replaced reg %u with %u\n",
734                                  INSN_UID (insn), regno, REGNO (new_rtx));
735                       changed = true;
736                       goto did_replacement;
737                     }
738                 }
739             }
740         }
741       no_move_special_case:
742
743       any_replacements = false;
744
745       /* For each input operand, replace a hard register with the
746          eldest live copy that's in an appropriate register class.  */
747       for (i = 0; i < n_ops; i++)
748         {
749           replaced[i] = false;
750
751           /* Don't scan match_operand here, since we've no reg class
752              information to pass down.  Any operands that we could
753              substitute in will be represented elsewhere.  */
754           if (recog_data.constraints[i][0] == '\0')
755             continue;
756
757           /* Don't replace in asms intentionally referencing hard regs.  */
758           if (is_asm && REG_P (recog_data.operand[i])
759               && (REGNO (recog_data.operand[i])
760                   == ORIGINAL_REGNO (recog_data.operand[i])))
761             continue;
762
763           if (recog_data.operand_type[i] == OP_IN)
764             {
765               if (recog_op_alt[i][alt].is_address)
766                 replaced[i]
767                   = replace_oldest_value_addr (recog_data.operand_loc[i],
768                                                recog_op_alt[i][alt].cl,
769                                                VOIDmode, insn, vd);
770               else if (REG_P (recog_data.operand[i]))
771                 replaced[i]
772                   = replace_oldest_value_reg (recog_data.operand_loc[i],
773                                               recog_op_alt[i][alt].cl,
774                                               insn, vd);
775               else if (MEM_P (recog_data.operand[i]))
776                 replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
777                                                         insn, vd);
778             }
779           else if (MEM_P (recog_data.operand[i]))
780             replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
781                                                     insn, vd);
782
783           /* If we performed any replacement, update match_dups.  */
784           if (replaced[i])
785             {
786               int j;
787               rtx new_rtx;
788
789               new_rtx = *recog_data.operand_loc[i];
790               recog_data.operand[i] = new_rtx;
791               for (j = 0; j < recog_data.n_dups; j++)
792                 if (recog_data.dup_num[j] == i)
793                   validate_unshare_change (insn, recog_data.dup_loc[j], new_rtx, 1);
794
795               any_replacements = true;
796             }
797         }
798
799       if (any_replacements)
800         {
801           if (! apply_change_group ())
802             {
803               for (i = 0; i < n_ops; i++)
804                 if (replaced[i])
805                   {
806                     rtx old = *recog_data.operand_loc[i];
807                     recog_data.operand[i] = old;
808                   }
809
810               if (dump_file)
811                 fprintf (dump_file,
812                          "insn %u: reg replacements not verified\n",
813                          INSN_UID (insn));
814             }
815           else
816             changed = true;
817         }
818
819     did_replacement:
820       /* Clobber call-clobbered registers.  */
821       if (CALL_P (insn))
822         for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
823           if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
824             kill_value_regno (i, 1, vd);
825
826       /* Notice stores.  */
827       note_stores (PATTERN (insn), kill_set_value, vd);
828
829       /* Notice copies.  */
830       if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
831         copy_value (SET_DEST (set), SET_SRC (set), vd);
832
833       if (insn == BB_END (bb))
834         break;
835     }
836
837   return changed;
838 }
839
840 /* Main entry point for the forward copy propagation optimization.  */
841
842 static unsigned int
843 copyprop_hardreg_forward (void)
844 {
845   struct value_data *all_vd;
846   basic_block bb;
847   sbitmap visited;
848
849   all_vd = XNEWVEC (struct value_data, last_basic_block);
850
851   visited = sbitmap_alloc (last_basic_block);
852   sbitmap_zero (visited);
853
854   FOR_EACH_BB (bb)
855     {
856       SET_BIT (visited, bb->index);
857
858       /* If a block has a single predecessor, that we've already
859          processed, begin with the value data that was live at
860          the end of the predecessor block.  */
861       /* ??? Ought to use more intelligent queuing of blocks.  */
862       if (single_pred_p (bb) 
863           && TEST_BIT (visited, single_pred (bb)->index)
864           && ! (single_pred_edge (bb)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
865         all_vd[bb->index] = all_vd[single_pred (bb)->index];
866       else
867         init_value_data (all_vd + bb->index);
868
869       copyprop_hardreg_forward_1 (bb, all_vd + bb->index);
870     }
871
872   sbitmap_free (visited);  
873   free (all_vd);
874   return 0;
875 }
876
877 /* Dump the value chain data to stderr.  */
878
879 void
880 debug_value_data (struct value_data *vd)
881 {
882   HARD_REG_SET set;
883   unsigned int i, j;
884
885   CLEAR_HARD_REG_SET (set);
886
887   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
888     if (vd->e[i].oldest_regno == i)
889       {
890         if (vd->e[i].mode == VOIDmode)
891           {
892             if (vd->e[i].next_regno != INVALID_REGNUM)
893               fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n",
894                        i, vd->e[i].next_regno);
895             continue;
896           }
897
898         SET_HARD_REG_BIT (set, i);
899         fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode));
900
901         for (j = vd->e[i].next_regno;
902              j != INVALID_REGNUM;
903              j = vd->e[j].next_regno)
904           {
905             if (TEST_HARD_REG_BIT (set, j))
906               {
907                 fprintf (stderr, "[%u] Loop in regno chain\n", j);
908                 return;
909               }
910
911             if (vd->e[j].oldest_regno != i)
912               {
913                 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n",
914                          j, vd->e[j].oldest_regno);
915                 return;
916               }
917             SET_HARD_REG_BIT (set, j);
918             fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode));
919           }
920         fputc ('\n', stderr);
921       }
922
923   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
924     if (! TEST_HARD_REG_BIT (set, i)
925         && (vd->e[i].mode != VOIDmode
926             || vd->e[i].oldest_regno != i
927             || vd->e[i].next_regno != INVALID_REGNUM))
928       fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n",
929                i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
930                vd->e[i].next_regno);
931 }
932
933 #ifdef ENABLE_CHECKING
934 static void
935 validate_value_data (struct value_data *vd)
936 {
937   HARD_REG_SET set;
938   unsigned int i, j;
939
940   CLEAR_HARD_REG_SET (set);
941
942   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
943     if (vd->e[i].oldest_regno == i)
944       {
945         if (vd->e[i].mode == VOIDmode)
946           {
947             if (vd->e[i].next_regno != INVALID_REGNUM)
948               internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
949                               i, vd->e[i].next_regno);
950             continue;
951           }
952
953         SET_HARD_REG_BIT (set, i);
954
955         for (j = vd->e[i].next_regno;
956              j != INVALID_REGNUM;
957              j = vd->e[j].next_regno)
958           {
959             if (TEST_HARD_REG_BIT (set, j))
960               internal_error ("validate_value_data: Loop in regno chain (%u)",
961                               j);
962             if (vd->e[j].oldest_regno != i)
963               internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
964                               j, vd->e[j].oldest_regno);
965
966             SET_HARD_REG_BIT (set, j);
967           }
968       }
969
970   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
971     if (! TEST_HARD_REG_BIT (set, i)
972         && (vd->e[i].mode != VOIDmode
973             || vd->e[i].oldest_regno != i
974             || vd->e[i].next_regno != INVALID_REGNUM))
975       internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
976                       i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
977                       vd->e[i].next_regno);
978 }
979 #endif
980 \f
981 static bool
982 gate_handle_cprop (void)
983 {
984   return (optimize > 0 && (flag_cprop_registers));
985 }
986
987
988 struct rtl_opt_pass pass_cprop_hardreg =
989 {
990  {
991   RTL_PASS,
992   "cprop_hardreg",                      /* name */
993   gate_handle_cprop,                    /* gate */
994   copyprop_hardreg_forward,             /* execute */
995   NULL,                                 /* sub */
996   NULL,                                 /* next */
997   0,                                    /* static_pass_number */
998   TV_CPROP_REGISTERS,                   /* tv_id */
999   0,                                    /* properties_required */
1000   0,                                    /* properties_provided */
1001   0,                                    /* properties_destroyed */
1002   0,                                    /* todo_flags_start */
1003   TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
1004  }
1005 };