OSDN Git Service

* basic-block.h: Document BB_* flags.
[pf3gnuchains/gcc-fork.git] / gcc / regrename.c
1 /* Register renaming for the GNU compiler.
2    Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005
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 2, 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 COPYING.  If not, write to the Free
19    Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20    02111-1307, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "insn-config.h"
29 #include "regs.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
40 struct du_chain
41 {
42   struct du_chain *next_chain;
43   struct du_chain *next_use;
44
45   rtx insn;
46   rtx *loc;
47   ENUM_BITFIELD(reg_class) cl : 16;
48   unsigned int need_caller_save_reg:1;
49   unsigned int earlyclobber:1;
50 };
51
52 enum scan_actions
53 {
54   terminate_all_read,
55   terminate_overlapping_read,
56   terminate_write,
57   terminate_dead,
58   mark_read,
59   mark_write
60 };
61
62 static const char * const scan_actions_name[] =
63 {
64   "terminate_all_read",
65   "terminate_overlapping_read",
66   "terminate_write",
67   "terminate_dead",
68   "mark_read",
69   "mark_write"
70 };
71
72 static struct obstack rename_obstack;
73
74 static void do_replace (struct du_chain *, int);
75 static void scan_rtx_reg (rtx, rtx *, enum reg_class,
76                           enum scan_actions, enum op_type, int);
77 static void scan_rtx_address (rtx, rtx *, enum reg_class,
78                               enum scan_actions, enum machine_mode);
79 static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
80                       enum op_type, int);
81 static struct du_chain *build_def_use (basic_block);
82 static void dump_def_use_chain (struct du_chain *);
83 static void note_sets (rtx, rtx, void *);
84 static void clear_dead_regs (HARD_REG_SET *, enum machine_mode, rtx);
85 static void merge_overlapping_regs (basic_block, HARD_REG_SET *,
86                                     struct du_chain *);
87
88 /* Called through note_stores from update_life.  Find sets of registers, and
89    record them in *DATA (which is actually a HARD_REG_SET *).  */
90
91 static void
92 note_sets (rtx x, rtx set ATTRIBUTE_UNUSED, void *data)
93 {
94   HARD_REG_SET *pset = (HARD_REG_SET *) data;
95   unsigned int regno;
96   int nregs;
97   if (!REG_P (x))
98     return;
99   regno = REGNO (x);
100   nregs = hard_regno_nregs[regno][GET_MODE (x)];
101
102   /* There must not be pseudos at this point.  */
103   gcc_assert (regno + nregs <= FIRST_PSEUDO_REGISTER);
104
105   while (nregs-- > 0)
106     SET_HARD_REG_BIT (*pset, regno + nregs);
107 }
108
109 /* Clear all registers from *PSET for which a note of kind KIND can be found
110    in the list NOTES.  */
111
112 static void
113 clear_dead_regs (HARD_REG_SET *pset, enum machine_mode kind, rtx notes)
114 {
115   rtx note;
116   for (note = notes; note; note = XEXP (note, 1))
117     if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0)))
118       {
119         rtx reg = XEXP (note, 0);
120         unsigned int regno = REGNO (reg);
121         int nregs = hard_regno_nregs[regno][GET_MODE (reg)];
122
123         /* There must not be pseudos at this point.  */
124         gcc_assert (regno + nregs <= FIRST_PSEUDO_REGISTER);
125
126         while (nregs-- > 0)
127           CLEAR_HARD_REG_BIT (*pset, regno + nregs);
128       }
129 }
130
131 /* For a def-use chain CHAIN in basic block B, find which registers overlap
132    its lifetime and set the corresponding bits in *PSET.  */
133
134 static void
135 merge_overlapping_regs (basic_block b, HARD_REG_SET *pset,
136                         struct du_chain *chain)
137 {
138   struct du_chain *t = chain;
139   rtx insn;
140   HARD_REG_SET live;
141
142   REG_SET_TO_HARD_REG_SET (live, b->global_live_at_start);
143   insn = BB_HEAD (b);
144   while (t)
145     {
146       /* Search forward until the next reference to the register to be
147          renamed.  */
148       while (insn != t->insn)
149         {
150           if (INSN_P (insn))
151             {
152               clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn));
153               note_stores (PATTERN (insn), note_sets, (void *) &live);
154               /* Only record currently live regs if we are inside the
155                  reg's live range.  */
156               if (t != chain)
157                 IOR_HARD_REG_SET (*pset, live);
158               clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn));
159             }
160           insn = NEXT_INSN (insn);
161         }
162
163       IOR_HARD_REG_SET (*pset, live);
164
165       /* For the last reference, also merge in all registers set in the
166          same insn.
167          @@@ We only have take earlyclobbered sets into account.  */
168       if (! t->next_use)
169         note_stores (PATTERN (insn), note_sets, (void *) pset);
170
171       t = t->next_use;
172     }
173 }
174
175 /* Perform register renaming on the current function.  */
176
177 void
178 regrename_optimize (void)
179 {
180   int tick[FIRST_PSEUDO_REGISTER];
181   int this_tick = 0;
182   basic_block bb;
183   char *first_obj;
184
185   memset (tick, 0, sizeof tick);
186
187   gcc_obstack_init (&rename_obstack);
188   first_obj = obstack_alloc (&rename_obstack, 0);
189
190   FOR_EACH_BB (bb)
191     {
192       struct du_chain *all_chains = 0;
193       HARD_REG_SET unavailable;
194       HARD_REG_SET regs_seen;
195
196       CLEAR_HARD_REG_SET (unavailable);
197
198       if (dump_file)
199         fprintf (dump_file, "\nBasic block %d:\n", bb->index);
200
201       all_chains = build_def_use (bb);
202
203       if (dump_file)
204         dump_def_use_chain (all_chains);
205
206       CLEAR_HARD_REG_SET (unavailable);
207       /* Don't clobber traceback for noreturn functions.  */
208       if (frame_pointer_needed)
209         {
210           int i;
211
212           for (i = hard_regno_nregs[FRAME_POINTER_REGNUM][Pmode]; i--;)
213             SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM + i);
214
215 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
216           for (i = hard_regno_nregs[HARD_FRAME_POINTER_REGNUM][Pmode]; i--;)
217             SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM + i);
218 #endif
219         }
220
221       CLEAR_HARD_REG_SET (regs_seen);
222       while (all_chains)
223         {
224           int new_reg, best_new_reg;
225           int n_uses;
226           struct du_chain *this = all_chains;
227           struct du_chain *tmp, *last;
228           HARD_REG_SET this_unavailable;
229           int reg = REGNO (*this->loc);
230           int i;
231
232           all_chains = this->next_chain;
233
234           best_new_reg = reg;
235
236 #if 0 /* This just disables optimization opportunities.  */
237           /* Only rename once we've seen the reg more than once.  */
238           if (! TEST_HARD_REG_BIT (regs_seen, reg))
239             {
240               SET_HARD_REG_BIT (regs_seen, reg);
241               continue;
242             }
243 #endif
244
245           if (fixed_regs[reg] || global_regs[reg]
246 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
247               || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
248 #else
249               || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
250 #endif
251               )
252             continue;
253
254           COPY_HARD_REG_SET (this_unavailable, unavailable);
255
256           /* Find last entry on chain (which has the need_caller_save bit),
257              count number of uses, and narrow the set of registers we can
258              use for renaming.  */
259           n_uses = 0;
260           for (last = this; last->next_use; last = last->next_use)
261             {
262               n_uses++;
263               IOR_COMPL_HARD_REG_SET (this_unavailable,
264                                       reg_class_contents[last->cl]);
265             }
266           if (n_uses < 1)
267             continue;
268
269           IOR_COMPL_HARD_REG_SET (this_unavailable,
270                                   reg_class_contents[last->cl]);
271
272           if (this->need_caller_save_reg)
273             IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
274
275           merge_overlapping_regs (bb, &this_unavailable, this);
276
277           /* Now potential_regs is a reasonable approximation, let's
278              have a closer look at each register still in there.  */
279           for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
280             {
281               int nregs = hard_regno_nregs[new_reg][GET_MODE (*this->loc)];
282
283               for (i = nregs - 1; i >= 0; --i)
284                 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
285                     || fixed_regs[new_reg + i]
286                     || global_regs[new_reg + i]
287                     /* Can't use regs which aren't saved by the prologue.  */
288                     || (! regs_ever_live[new_reg + i]
289                         && ! call_used_regs[new_reg + i])
290 #ifdef LEAF_REGISTERS
291                     /* We can't use a non-leaf register if we're in a
292                        leaf function.  */
293                     || (current_function_is_leaf
294                         && !LEAF_REGISTERS[new_reg + i])
295 #endif
296 #ifdef HARD_REGNO_RENAME_OK
297                     || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
298 #endif
299                     )
300                   break;
301               if (i >= 0)
302                 continue;
303
304               /* See whether it accepts all modes that occur in
305                  definition and uses.  */
306               for (tmp = this; tmp; tmp = tmp->next_use)
307                 if (! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
308                     || (tmp->need_caller_save_reg
309                         && ! (HARD_REGNO_CALL_PART_CLOBBERED
310                               (reg, GET_MODE (*tmp->loc)))
311                         && (HARD_REGNO_CALL_PART_CLOBBERED
312                             (new_reg, GET_MODE (*tmp->loc)))))
313                   break;
314               if (! tmp)
315                 {
316                   if (tick[best_new_reg] > tick[new_reg])
317                     best_new_reg = new_reg;
318                 }
319             }
320
321           if (dump_file)
322             {
323               fprintf (dump_file, "Register %s in insn %d",
324                        reg_names[reg], INSN_UID (last->insn));
325               if (last->need_caller_save_reg)
326                 fprintf (dump_file, " crosses a call");
327             }
328
329           if (best_new_reg == reg)
330             {
331               tick[reg] = ++this_tick;
332               if (dump_file)
333                 fprintf (dump_file, "; no available better choice\n");
334               continue;
335             }
336
337           do_replace (this, best_new_reg);
338           tick[best_new_reg] = ++this_tick;
339           regs_ever_live[best_new_reg] = 1;
340
341           if (dump_file)
342             fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
343         }
344
345       obstack_free (&rename_obstack, first_obj);
346     }
347
348   obstack_free (&rename_obstack, NULL);
349
350   if (dump_file)
351     fputc ('\n', dump_file);
352
353   count_or_remove_death_notes (NULL, 1);
354   update_life_info (NULL, UPDATE_LIFE_LOCAL,
355                     PROP_DEATH_NOTES);
356 }
357
358 static void
359 do_replace (struct du_chain *chain, int reg)
360 {
361   while (chain)
362     {
363       unsigned int regno = ORIGINAL_REGNO (*chain->loc);
364       struct reg_attrs * attr = REG_ATTRS (*chain->loc);
365
366       *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
367       if (regno >= FIRST_PSEUDO_REGISTER)
368         ORIGINAL_REGNO (*chain->loc) = regno;
369       REG_ATTRS (*chain->loc) = attr;
370       chain = chain->next_use;
371     }
372 }
373
374
375 static struct du_chain *open_chains;
376 static struct du_chain *closed_chains;
377
378 static void
379 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl,
380               enum scan_actions action, enum op_type type, int earlyclobber)
381 {
382   struct du_chain **p;
383   rtx x = *loc;
384   enum machine_mode mode = GET_MODE (x);
385   int this_regno = REGNO (x);
386   int this_nregs = hard_regno_nregs[this_regno][mode];
387
388   if (action == mark_write)
389     {
390       if (type == OP_OUT)
391         {
392           struct du_chain *this
393             = obstack_alloc (&rename_obstack, sizeof (struct du_chain));
394           this->next_use = 0;
395           this->next_chain = open_chains;
396           this->loc = loc;
397           this->insn = insn;
398           this->cl = cl;
399           this->need_caller_save_reg = 0;
400           this->earlyclobber = earlyclobber;
401           open_chains = this;
402         }
403       return;
404     }
405
406   if ((type == OP_OUT && action != terminate_write)
407       || (type != OP_OUT && action == terminate_write))
408     return;
409
410   for (p = &open_chains; *p;)
411     {
412       struct du_chain *this = *p;
413
414       /* Check if the chain has been terminated if it has then skip to
415          the next chain.
416
417          This can happen when we've already appended the location to
418          the chain in Step 3, but are trying to hide in-out operands
419          from terminate_write in Step 5.  */
420
421       if (*this->loc == cc0_rtx)
422         p = &this->next_chain;
423       else
424         {
425           int regno = REGNO (*this->loc);
426           int nregs = hard_regno_nregs[regno][GET_MODE (*this->loc)];
427           int exact_match = (regno == this_regno && nregs == this_nregs);
428
429           if (regno + nregs <= this_regno
430               || this_regno + this_nregs <= regno)
431             {
432               p = &this->next_chain;
433               continue;
434             }
435
436           if (action == mark_read)
437             {
438               gcc_assert (exact_match);
439
440               /* ??? Class NO_REGS can happen if the md file makes use of
441                  EXTRA_CONSTRAINTS to match registers.  Which is arguably
442                  wrong, but there we are.  Since we know not what this may
443                  be replaced with, terminate the chain.  */
444               if (cl != NO_REGS)
445                 {
446                   this = obstack_alloc (&rename_obstack, sizeof (struct du_chain));
447                   this->next_use = 0;
448                   this->next_chain = (*p)->next_chain;
449                   this->loc = loc;
450                   this->insn = insn;
451                   this->cl = cl;
452                   this->need_caller_save_reg = 0;
453                   while (*p)
454                     p = &(*p)->next_use;
455                   *p = this;
456                   return;
457                 }
458             }
459
460           if (action != terminate_overlapping_read || ! exact_match)
461             {
462               struct du_chain *next = this->next_chain;
463
464               /* Whether the terminated chain can be used for renaming
465                  depends on the action and this being an exact match.
466                  In either case, we remove this element from open_chains.  */
467
468               if ((action == terminate_dead || action == terminate_write)
469                   && exact_match)
470                 {
471                   this->next_chain = closed_chains;
472                   closed_chains = this;
473                   if (dump_file)
474                     fprintf (dump_file,
475                              "Closing chain %s at insn %d (%s)\n",
476                              reg_names[REGNO (*this->loc)], INSN_UID (insn),
477                              scan_actions_name[(int) action]);
478                 }
479               else
480                 {
481                   if (dump_file)
482                     fprintf (dump_file,
483                              "Discarding chain %s at insn %d (%s)\n",
484                              reg_names[REGNO (*this->loc)], INSN_UID (insn),
485                              scan_actions_name[(int) action]);
486                 }
487               *p = next;
488             }
489           else
490             p = &this->next_chain;
491         }
492     }
493 }
494
495 /* Adapted from find_reloads_address_1.  CL is INDEX_REG_CLASS or
496    BASE_REG_CLASS depending on how the register is being considered.  */
497
498 static void
499 scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl,
500                   enum scan_actions action, enum machine_mode mode)
501 {
502   rtx x = *loc;
503   RTX_CODE code = GET_CODE (x);
504   const char *fmt;
505   int i, j;
506
507   if (action == mark_write)
508     return;
509
510   switch (code)
511     {
512     case PLUS:
513       {
514         rtx orig_op0 = XEXP (x, 0);
515         rtx orig_op1 = XEXP (x, 1);
516         RTX_CODE code0 = GET_CODE (orig_op0);
517         RTX_CODE code1 = GET_CODE (orig_op1);
518         rtx op0 = orig_op0;
519         rtx op1 = orig_op1;
520         rtx *locI = NULL;
521         rtx *locB = NULL;
522         rtx *locB_reg = NULL;
523
524         if (GET_CODE (op0) == SUBREG)
525           {
526             op0 = SUBREG_REG (op0);
527             code0 = GET_CODE (op0);
528           }
529
530         if (GET_CODE (op1) == SUBREG)
531           {
532             op1 = SUBREG_REG (op1);
533             code1 = GET_CODE (op1);
534           }
535
536         if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
537             || code0 == ZERO_EXTEND || code1 == MEM)
538           {
539             locI = &XEXP (x, 0);
540             locB = &XEXP (x, 1);
541           }
542         else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
543                  || code1 == ZERO_EXTEND || code0 == MEM)
544           {
545             locI = &XEXP (x, 1);
546             locB = &XEXP (x, 0);
547           }
548         else if (code0 == CONST_INT || code0 == CONST
549                  || code0 == SYMBOL_REF || code0 == LABEL_REF)
550           locB = &XEXP (x, 1);
551         else if (code1 == CONST_INT || code1 == CONST
552                  || code1 == SYMBOL_REF || code1 == LABEL_REF)
553           locB = &XEXP (x, 0);
554         else if (code0 == REG && code1 == REG)
555           {
556             int index_op;
557
558             if (REG_OK_FOR_INDEX_P (op0)
559                 && REG_MODE_OK_FOR_REG_BASE_P (op1, mode))
560               index_op = 0;
561             else if (REG_OK_FOR_INDEX_P (op1)
562                      && REG_MODE_OK_FOR_REG_BASE_P (op0, mode))
563               index_op = 1;
564             else if (REG_MODE_OK_FOR_REG_BASE_P (op1, mode))
565               index_op = 0;
566             else if (REG_MODE_OK_FOR_REG_BASE_P (op0, mode))
567               index_op = 1;
568             else if (REG_OK_FOR_INDEX_P (op1))
569               index_op = 1;
570             else
571               index_op = 0;
572
573             locI = &XEXP (x, index_op);
574             locB_reg = &XEXP (x, !index_op);
575           }
576         else if (code0 == REG)
577           {
578             locI = &XEXP (x, 0);
579             locB = &XEXP (x, 1);
580           }
581         else if (code1 == REG)
582           {
583             locI = &XEXP (x, 1);
584             locB = &XEXP (x, 0);
585           }
586
587         if (locI)
588           scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
589         if (locB)
590           scan_rtx_address (insn, locB, MODE_BASE_REG_CLASS (mode), action, mode);
591         if (locB_reg)
592           scan_rtx_address (insn, locB_reg, MODE_BASE_REG_REG_CLASS (mode),
593                             action, mode);
594         return;
595       }
596
597     case POST_INC:
598     case POST_DEC:
599     case POST_MODIFY:
600     case PRE_INC:
601     case PRE_DEC:
602     case PRE_MODIFY:
603 #ifndef AUTO_INC_DEC
604       /* If the target doesn't claim to handle autoinc, this must be
605          something special, like a stack push.  Kill this chain.  */
606       action = terminate_all_read;
607 #endif
608       break;
609
610     case MEM:
611       scan_rtx_address (insn, &XEXP (x, 0),
612                         MODE_BASE_REG_CLASS (GET_MODE (x)), action,
613                         GET_MODE (x));
614       return;
615
616     case REG:
617       scan_rtx_reg (insn, loc, cl, action, OP_IN, 0);
618       return;
619
620     default:
621       break;
622     }
623
624   fmt = GET_RTX_FORMAT (code);
625   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
626     {
627       if (fmt[i] == 'e')
628         scan_rtx_address (insn, &XEXP (x, i), cl, action, mode);
629       else if (fmt[i] == 'E')
630         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
631           scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode);
632     }
633 }
634
635 static void
636 scan_rtx (rtx insn, rtx *loc, enum reg_class cl,
637           enum scan_actions action, enum op_type type, int earlyclobber)
638 {
639   const char *fmt;
640   rtx x = *loc;
641   enum rtx_code code = GET_CODE (x);
642   int i, j;
643
644   code = GET_CODE (x);
645   switch (code)
646     {
647     case CONST:
648     case CONST_INT:
649     case CONST_DOUBLE:
650     case CONST_VECTOR:
651     case SYMBOL_REF:
652     case LABEL_REF:
653     case CC0:
654     case PC:
655       return;
656
657     case REG:
658       scan_rtx_reg (insn, loc, cl, action, type, earlyclobber);
659       return;
660
661     case MEM:
662       scan_rtx_address (insn, &XEXP (x, 0),
663                         MODE_BASE_REG_CLASS (GET_MODE (x)), action,
664                         GET_MODE (x));
665       return;
666
667     case SET:
668       scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN, 0);
669       scan_rtx (insn, &SET_DEST (x), cl, action,
670                 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0);
671       return;
672
673     case STRICT_LOW_PART:
674       scan_rtx (insn, &XEXP (x, 0), cl, action, OP_INOUT, earlyclobber);
675       return;
676
677     case ZERO_EXTRACT:
678     case SIGN_EXTRACT:
679       scan_rtx (insn, &XEXP (x, 0), cl, action,
680                 type == OP_IN ? OP_IN : OP_INOUT, earlyclobber);
681       scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN, 0);
682       scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN, 0);
683       return;
684
685     case POST_INC:
686     case PRE_INC:
687     case POST_DEC:
688     case PRE_DEC:
689     case POST_MODIFY:
690     case PRE_MODIFY:
691       /* Should only happen inside MEM.  */
692       gcc_unreachable ();
693
694     case CLOBBER:
695       scan_rtx (insn, &SET_DEST (x), cl, action,
696                 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0);
697       return;
698
699     case EXPR_LIST:
700       scan_rtx (insn, &XEXP (x, 0), cl, action, type, 0);
701       if (XEXP (x, 1))
702         scan_rtx (insn, &XEXP (x, 1), cl, action, type, 0);
703       return;
704
705     default:
706       break;
707     }
708
709   fmt = GET_RTX_FORMAT (code);
710   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
711     {
712       if (fmt[i] == 'e')
713         scan_rtx (insn, &XEXP (x, i), cl, action, type, 0);
714       else if (fmt[i] == 'E')
715         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
716           scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type, 0);
717     }
718 }
719
720 /* Build def/use chain.  */
721
722 static struct du_chain *
723 build_def_use (basic_block bb)
724 {
725   rtx insn;
726
727   open_chains = closed_chains = NULL;
728
729   for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
730     {
731       if (INSN_P (insn))
732         {
733           int n_ops;
734           rtx note;
735           rtx old_operands[MAX_RECOG_OPERANDS];
736           rtx old_dups[MAX_DUP_OPERANDS];
737           int i, icode;
738           int alt;
739           int predicated;
740
741           /* Process the insn, determining its effect on the def-use
742              chains.  We perform the following steps with the register
743              references in the insn:
744              (1) Any read that overlaps an open chain, but doesn't exactly
745                  match, causes that chain to be closed.  We can't deal
746                  with overlaps yet.
747              (2) Any read outside an operand causes any chain it overlaps
748                  with to be closed, since we can't replace it.
749              (3) Any read inside an operand is added if there's already
750                  an open chain for it.
751              (4) For any REG_DEAD note we find, close open chains that
752                  overlap it.
753              (5) For any write we find, close open chains that overlap it.
754              (6) For any write we find in an operand, make a new chain.
755              (7) For any REG_UNUSED, close any chains we just opened.  */
756
757           icode = recog_memoized (insn);
758           extract_insn (insn);
759           if (! constrain_operands (1))
760             fatal_insn_not_found (insn);
761           preprocess_constraints ();
762           alt = which_alternative;
763           n_ops = recog_data.n_operands;
764
765           /* Simplify the code below by rewriting things to reflect
766              matching constraints.  Also promote OP_OUT to OP_INOUT
767              in predicated instructions.  */
768
769           predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
770           for (i = 0; i < n_ops; ++i)
771             {
772               int matches = recog_op_alt[i][alt].matches;
773               if (matches >= 0)
774                 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
775               if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
776                   || (predicated && recog_data.operand_type[i] == OP_OUT))
777                 recog_data.operand_type[i] = OP_INOUT;
778             }
779
780           /* Step 1: Close chains for which we have overlapping reads.  */
781           for (i = 0; i < n_ops; i++)
782             scan_rtx (insn, recog_data.operand_loc[i],
783                       NO_REGS, terminate_overlapping_read,
784                       recog_data.operand_type[i], 0);
785
786           /* Step 2: Close chains for which we have reads outside operands.
787              We do this by munging all operands into CC0, and closing
788              everything remaining.  */
789
790           for (i = 0; i < n_ops; i++)
791             {
792               old_operands[i] = recog_data.operand[i];
793               /* Don't squash match_operator or match_parallel here, since
794                  we don't know that all of the contained registers are
795                  reachable by proper operands.  */
796               if (recog_data.constraints[i][0] == '\0')
797                 continue;
798               *recog_data.operand_loc[i] = cc0_rtx;
799             }
800           for (i = 0; i < recog_data.n_dups; i++)
801             {
802               int dup_num = recog_data.dup_num[i];
803
804               old_dups[i] = *recog_data.dup_loc[i];
805               *recog_data.dup_loc[i] = cc0_rtx;
806
807               /* For match_dup of match_operator or match_parallel, share
808                  them, so that we don't miss changes in the dup.  */
809               if (icode >= 0
810                   && insn_data[icode].operand[dup_num].eliminable == 0)
811                 old_dups[i] = recog_data.operand[dup_num];
812             }
813
814           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read,
815                     OP_IN, 0);
816
817           for (i = 0; i < recog_data.n_dups; i++)
818             *recog_data.dup_loc[i] = old_dups[i];
819           for (i = 0; i < n_ops; i++)
820             *recog_data.operand_loc[i] = old_operands[i];
821
822           /* Step 2B: Can't rename function call argument registers.  */
823           if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
824             scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
825                       NO_REGS, terminate_all_read, OP_IN, 0);
826
827           /* Step 2C: Can't rename asm operands that were originally
828              hard registers.  */
829           if (asm_noperands (PATTERN (insn)) > 0)
830             for (i = 0; i < n_ops; i++)
831               {
832                 rtx *loc = recog_data.operand_loc[i];
833                 rtx op = *loc;
834
835                 if (REG_P (op)
836                     && REGNO (op) == ORIGINAL_REGNO (op)
837                     && (recog_data.operand_type[i] == OP_IN
838                         || recog_data.operand_type[i] == OP_INOUT))
839                   scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0);
840               }
841
842           /* Step 3: Append to chains for reads inside operands.  */
843           for (i = 0; i < n_ops + recog_data.n_dups; i++)
844             {
845               int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
846               rtx *loc = (i < n_ops
847                           ? recog_data.operand_loc[opn]
848                           : recog_data.dup_loc[i - n_ops]);
849               enum reg_class cl = recog_op_alt[opn][alt].cl;
850               enum op_type type = recog_data.operand_type[opn];
851
852               /* Don't scan match_operand here, since we've no reg class
853                  information to pass down.  Any operands that we could
854                  substitute in will be represented elsewhere.  */
855               if (recog_data.constraints[opn][0] == '\0')
856                 continue;
857
858               if (recog_op_alt[opn][alt].is_address)
859                 scan_rtx_address (insn, loc, cl, mark_read, VOIDmode);
860               else
861                 scan_rtx (insn, loc, cl, mark_read, type, 0);
862             }
863
864           /* Step 4: Close chains for registers that die here.
865              Also record updates for REG_INC notes.  */
866           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
867             {
868               if (REG_NOTE_KIND (note) == REG_DEAD)
869                 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
870                           OP_IN, 0);
871               else if (REG_NOTE_KIND (note) == REG_INC)
872                 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
873                           OP_INOUT, 0);
874             }
875
876           /* Step 4B: If this is a call, any chain live at this point
877              requires a caller-saved reg.  */
878           if (CALL_P (insn))
879             {
880               struct du_chain *p;
881               for (p = open_chains; p; p = p->next_chain)
882                 p->need_caller_save_reg = 1;
883             }
884
885           /* Step 5: Close open chains that overlap writes.  Similar to
886              step 2, we hide in-out operands, since we do not want to
887              close these chains.  */
888
889           for (i = 0; i < n_ops; i++)
890             {
891               old_operands[i] = recog_data.operand[i];
892               if (recog_data.operand_type[i] == OP_INOUT)
893                 *recog_data.operand_loc[i] = cc0_rtx;
894             }
895           for (i = 0; i < recog_data.n_dups; i++)
896             {
897               int opn = recog_data.dup_num[i];
898               old_dups[i] = *recog_data.dup_loc[i];
899               if (recog_data.operand_type[opn] == OP_INOUT)
900                 *recog_data.dup_loc[i] = cc0_rtx;
901             }
902
903           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0);
904
905           for (i = 0; i < recog_data.n_dups; i++)
906             *recog_data.dup_loc[i] = old_dups[i];
907           for (i = 0; i < n_ops; i++)
908             *recog_data.operand_loc[i] = old_operands[i];
909
910           /* Step 6: Begin new chains for writes inside operands.  */
911           /* ??? Many targets have output constraints on the SET_DEST
912              of a call insn, which is stupid, since these are certainly
913              ABI defined hard registers.  Don't change calls at all.
914              Similarly take special care for asm statement that originally
915              referenced hard registers.  */
916           if (asm_noperands (PATTERN (insn)) > 0)
917             {
918               for (i = 0; i < n_ops; i++)
919                 if (recog_data.operand_type[i] == OP_OUT)
920                   {
921                     rtx *loc = recog_data.operand_loc[i];
922                     rtx op = *loc;
923                     enum reg_class cl = recog_op_alt[i][alt].cl;
924
925                     if (REG_P (op)
926                         && REGNO (op) == ORIGINAL_REGNO (op))
927                       continue;
928
929                     scan_rtx (insn, loc, cl, mark_write, OP_OUT,
930                               recog_op_alt[i][alt].earlyclobber);
931                   }
932             }
933           else if (!CALL_P (insn))
934             for (i = 0; i < n_ops + recog_data.n_dups; i++)
935               {
936                 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
937                 rtx *loc = (i < n_ops
938                             ? recog_data.operand_loc[opn]
939                             : recog_data.dup_loc[i - n_ops]);
940                 enum reg_class cl = recog_op_alt[opn][alt].cl;
941
942                 if (recog_data.operand_type[opn] == OP_OUT)
943                   scan_rtx (insn, loc, cl, mark_write, OP_OUT,
944                             recog_op_alt[opn][alt].earlyclobber);
945               }
946
947           /* Step 7: Close chains for registers that were never
948              really used here.  */
949           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
950             if (REG_NOTE_KIND (note) == REG_UNUSED)
951               scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
952                         OP_IN, 0);
953         }
954       if (insn == BB_END (bb))
955         break;
956     }
957
958   /* Since we close every chain when we find a REG_DEAD note, anything that
959      is still open lives past the basic block, so it can't be renamed.  */
960   return closed_chains;
961 }
962
963 /* Dump all def/use chains in CHAINS to DUMP_FILE.  They are
964    printed in reverse order as that's how we build them.  */
965
966 static void
967 dump_def_use_chain (struct du_chain *chains)
968 {
969   while (chains)
970     {
971       struct du_chain *this = chains;
972       int r = REGNO (*this->loc);
973       int nregs = hard_regno_nregs[r][GET_MODE (*this->loc)];
974       fprintf (dump_file, "Register %s (%d):", reg_names[r], nregs);
975       while (this)
976         {
977           fprintf (dump_file, " %d [%s]", INSN_UID (this->insn),
978                    reg_class_names[this->cl]);
979           this = this->next_use;
980         }
981       fprintf (dump_file, "\n");
982       chains = chains->next_chain;
983     }
984 }
985 \f
986 /* The following code does forward propagation of hard register copies.
987    The object is to eliminate as many dependencies as possible, so that
988    we have the most scheduling freedom.  As a side effect, we also clean
989    up some silly register allocation decisions made by reload.  This
990    code may be obsoleted by a new register allocator.  */
991
992 /* For each register, we have a list of registers that contain the same
993    value.  The OLDEST_REGNO field points to the head of the list, and
994    the NEXT_REGNO field runs through the list.  The MODE field indicates
995    what mode the data is known to be in; this field is VOIDmode when the
996    register is not known to contain valid data.  */
997
998 struct value_data_entry
999 {
1000   enum machine_mode mode;
1001   unsigned int oldest_regno;
1002   unsigned int next_regno;
1003 };
1004
1005 struct value_data
1006 {
1007   struct value_data_entry e[FIRST_PSEUDO_REGISTER];
1008   unsigned int max_value_regs;
1009 };
1010
1011 static void kill_value_one_regno (unsigned, struct value_data *);
1012 static void kill_value_regno (unsigned, unsigned, struct value_data *);
1013 static void kill_value (rtx, struct value_data *);
1014 static void set_value_regno (unsigned, enum machine_mode, struct value_data *);
1015 static void init_value_data (struct value_data *);
1016 static void kill_clobbered_value (rtx, rtx, void *);
1017 static void kill_set_value (rtx, rtx, void *);
1018 static int kill_autoinc_value (rtx *, void *);
1019 static void copy_value (rtx, rtx, struct value_data *);
1020 static bool mode_change_ok (enum machine_mode, enum machine_mode,
1021                             unsigned int);
1022 static rtx maybe_mode_change (enum machine_mode, enum machine_mode,
1023                               enum machine_mode, unsigned int, unsigned int);
1024 static rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *);
1025 static bool replace_oldest_value_reg (rtx *, enum reg_class, rtx,
1026                                       struct value_data *);
1027 static bool replace_oldest_value_addr (rtx *, enum reg_class,
1028                                        enum machine_mode, rtx,
1029                                        struct value_data *);
1030 static bool replace_oldest_value_mem (rtx, rtx, struct value_data *);
1031 static bool copyprop_hardreg_forward_1 (basic_block, struct value_data *);
1032 extern void debug_value_data (struct value_data *);
1033 #ifdef ENABLE_CHECKING
1034 static void validate_value_data (struct value_data *);
1035 #endif
1036
1037 /* Kill register REGNO.  This involves removing it from any value
1038    lists, and resetting the value mode to VOIDmode.  This is only a
1039    helper function; it does not handle any hard registers overlapping
1040    with REGNO.  */
1041
1042 static void
1043 kill_value_one_regno (unsigned int regno, struct value_data *vd)
1044 {
1045   unsigned int i, next;
1046
1047   if (vd->e[regno].oldest_regno != regno)
1048     {
1049       for (i = vd->e[regno].oldest_regno;
1050            vd->e[i].next_regno != regno;
1051            i = vd->e[i].next_regno)
1052         continue;
1053       vd->e[i].next_regno = vd->e[regno].next_regno;
1054     }
1055   else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM)
1056     {
1057       for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno)
1058         vd->e[i].oldest_regno = next;
1059     }
1060
1061   vd->e[regno].mode = VOIDmode;
1062   vd->e[regno].oldest_regno = regno;
1063   vd->e[regno].next_regno = INVALID_REGNUM;
1064
1065 #ifdef ENABLE_CHECKING
1066   validate_value_data (vd);
1067 #endif
1068 }
1069
1070 /* Kill the value in register REGNO for NREGS, and any other registers
1071    whose values overlap.  */
1072
1073 static void
1074 kill_value_regno (unsigned int regno, unsigned int nregs,
1075                   struct value_data *vd)
1076 {
1077   unsigned int j;
1078
1079   /* Kill the value we're told to kill.  */
1080   for (j = 0; j < nregs; ++j)
1081     kill_value_one_regno (regno + j, vd);
1082
1083   /* Kill everything that overlapped what we're told to kill.  */
1084   if (regno < vd->max_value_regs)
1085     j = 0;
1086   else
1087     j = regno - vd->max_value_regs;
1088   for (; j < regno; ++j)
1089     {
1090       unsigned int i, n;
1091       if (vd->e[j].mode == VOIDmode)
1092         continue;
1093       n = hard_regno_nregs[j][vd->e[j].mode];
1094       if (j + n > regno)
1095         for (i = 0; i < n; ++i)
1096           kill_value_one_regno (j + i, vd);
1097     }
1098 }
1099
1100 /* Kill X.  This is a convenience function wrapping kill_value_regno
1101    so that we mind the mode the register is in.  */
1102
1103 static void
1104 kill_value (rtx x, struct value_data *vd)
1105 {
1106   rtx orig_rtx = x;
1107
1108   if (GET_CODE (x) == SUBREG)
1109     {
1110       x = simplify_subreg (GET_MODE (x), SUBREG_REG (x),
1111                            GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
1112       if (x == NULL_RTX)
1113         x = SUBREG_REG (orig_rtx);
1114     }
1115   if (REG_P (x))
1116     {
1117       unsigned int regno = REGNO (x);
1118       unsigned int n = hard_regno_nregs[regno][GET_MODE (x)];
1119
1120       kill_value_regno (regno, n, vd);
1121     }
1122 }
1123
1124 /* Remember that REGNO is valid in MODE.  */
1125
1126 static void
1127 set_value_regno (unsigned int regno, enum machine_mode mode,
1128                  struct value_data *vd)
1129 {
1130   unsigned int nregs;
1131
1132   vd->e[regno].mode = mode;
1133
1134   nregs = hard_regno_nregs[regno][mode];
1135   if (nregs > vd->max_value_regs)
1136     vd->max_value_regs = nregs;
1137 }
1138
1139 /* Initialize VD such that there are no known relationships between regs.  */
1140
1141 static void
1142 init_value_data (struct value_data *vd)
1143 {
1144   int i;
1145   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1146     {
1147       vd->e[i].mode = VOIDmode;
1148       vd->e[i].oldest_regno = i;
1149       vd->e[i].next_regno = INVALID_REGNUM;
1150     }
1151   vd->max_value_regs = 0;
1152 }
1153
1154 /* Called through note_stores.  If X is clobbered, kill its value.  */
1155
1156 static void
1157 kill_clobbered_value (rtx x, rtx set, void *data)
1158 {
1159   struct value_data *vd = data;
1160   if (GET_CODE (set) == CLOBBER)
1161     kill_value (x, vd);
1162 }
1163
1164 /* Called through note_stores.  If X is set, not clobbered, kill its
1165    current value and install it as the root of its own value list.  */
1166
1167 static void
1168 kill_set_value (rtx x, rtx set, void *data)
1169 {
1170   struct value_data *vd = data;
1171   if (GET_CODE (set) != CLOBBER)
1172     {
1173       kill_value (x, vd);
1174       if (REG_P (x))
1175         set_value_regno (REGNO (x), GET_MODE (x), vd);
1176     }
1177 }
1178
1179 /* Called through for_each_rtx.  Kill any register used as the base of an
1180    auto-increment expression, and install that register as the root of its
1181    own value list.  */
1182
1183 static int
1184 kill_autoinc_value (rtx *px, void *data)
1185 {
1186   rtx x = *px;
1187   struct value_data *vd = data;
1188
1189   if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
1190     {
1191       x = XEXP (x, 0);
1192       kill_value (x, vd);
1193       set_value_regno (REGNO (x), Pmode, vd);
1194       return -1;
1195     }
1196
1197   return 0;
1198 }
1199
1200 /* Assert that SRC has been copied to DEST.  Adjust the data structures
1201    to reflect that SRC contains an older copy of the shared value.  */
1202
1203 static void
1204 copy_value (rtx dest, rtx src, struct value_data *vd)
1205 {
1206   unsigned int dr = REGNO (dest);
1207   unsigned int sr = REGNO (src);
1208   unsigned int dn, sn;
1209   unsigned int i;
1210
1211   /* ??? At present, it's possible to see noop sets.  It'd be nice if
1212      this were cleaned up beforehand...  */
1213   if (sr == dr)
1214     return;
1215
1216   /* Do not propagate copies to the stack pointer, as that can leave
1217      memory accesses with no scheduling dependency on the stack update.  */
1218   if (dr == STACK_POINTER_REGNUM)
1219     return;
1220
1221   /* Likewise with the frame pointer, if we're using one.  */
1222   if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM)
1223     return;
1224
1225   /* If SRC and DEST overlap, don't record anything.  */
1226   dn = hard_regno_nregs[dr][GET_MODE (dest)];
1227   sn = hard_regno_nregs[sr][GET_MODE (dest)];
1228   if ((dr > sr && dr < sr + sn)
1229       || (sr > dr && sr < dr + dn))
1230     return;
1231
1232   /* If SRC had no assigned mode (i.e. we didn't know it was live)
1233      assign it now and assume the value came from an input argument
1234      or somesuch.  */
1235   if (vd->e[sr].mode == VOIDmode)
1236     set_value_regno (sr, vd->e[dr].mode, vd);
1237
1238   /* If we are narrowing the input to a smaller number of hard regs,
1239      and it is in big endian, we are really extracting a high part.
1240      Since we generally associate a low part of a value with the value itself,
1241      we must not do the same for the high part.
1242      Note we can still get low parts for the same mode combination through
1243      a two-step copy involving differently sized hard regs.
1244      Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
1245      (set (reg:DI r0) (reg:DI fr0))
1246      (set (reg:SI fr2) (reg:SI r0))
1247      loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
1248      (set (reg:SI fr2) (reg:SI fr0))
1249      loads the high part of (reg:DI fr0) into fr2.
1250
1251      We can't properly represent the latter case in our tables, so don't
1252      record anything then.  */
1253   else if (sn < (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode]
1254            && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD
1255                ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
1256     return;
1257
1258   /* If SRC had been assigned a mode narrower than the copy, we can't
1259      link DEST into the chain, because not all of the pieces of the
1260      copy came from oldest_regno.  */
1261   else if (sn > (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode])
1262     return;
1263
1264   /* Link DR at the end of the value chain used by SR.  */
1265
1266   vd->e[dr].oldest_regno = vd->e[sr].oldest_regno;
1267
1268   for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno)
1269     continue;
1270   vd->e[i].next_regno = dr;
1271
1272 #ifdef ENABLE_CHECKING
1273   validate_value_data (vd);
1274 #endif
1275 }
1276
1277 /* Return true if a mode change from ORIG to NEW is allowed for REGNO.  */
1278
1279 static bool
1280 mode_change_ok (enum machine_mode orig_mode, enum machine_mode new_mode,
1281                 unsigned int regno ATTRIBUTE_UNUSED)
1282 {
1283   if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode))
1284     return false;
1285
1286 #ifdef CANNOT_CHANGE_MODE_CLASS
1287   return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode);
1288 #endif
1289
1290   return true;
1291 }
1292
1293 /* Register REGNO was originally set in ORIG_MODE.  It - or a copy of it -
1294    was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
1295    in NEW_MODE.
1296    Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX.  */
1297
1298 static rtx
1299 maybe_mode_change (enum machine_mode orig_mode, enum machine_mode copy_mode,
1300                    enum machine_mode new_mode, unsigned int regno,
1301                    unsigned int copy_regno ATTRIBUTE_UNUSED)
1302 {
1303   if (orig_mode == new_mode)
1304     return gen_rtx_raw_REG (new_mode, regno);
1305   else if (mode_change_ok (orig_mode, new_mode, regno))
1306     {
1307       int copy_nregs = hard_regno_nregs[copy_regno][copy_mode];
1308       int use_nregs = hard_regno_nregs[copy_regno][new_mode];
1309       int copy_offset
1310         = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs);
1311       int offset
1312         = GET_MODE_SIZE (orig_mode) - GET_MODE_SIZE (new_mode) - copy_offset;
1313       int byteoffset = offset % UNITS_PER_WORD;
1314       int wordoffset = offset - byteoffset;
1315
1316       offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0)
1317                 + (BYTES_BIG_ENDIAN ? byteoffset : 0));
1318       return gen_rtx_raw_REG (new_mode,
1319                               regno + subreg_regno_offset (regno, orig_mode,
1320                                                            offset,
1321                                                            new_mode));
1322     }
1323   return NULL_RTX;
1324 }
1325
1326 /* Find the oldest copy of the value contained in REGNO that is in
1327    register class CL and has mode MODE.  If found, return an rtx
1328    of that oldest register, otherwise return NULL.  */
1329
1330 static rtx
1331 find_oldest_value_reg (enum reg_class cl, rtx reg, struct value_data *vd)
1332 {
1333   unsigned int regno = REGNO (reg);
1334   enum machine_mode mode = GET_MODE (reg);
1335   unsigned int i;
1336
1337   /* If we are accessing REG in some mode other that what we set it in,
1338      make sure that the replacement is valid.  In particular, consider
1339         (set (reg:DI r11) (...))
1340         (set (reg:SI r9) (reg:SI r11))
1341         (set (reg:SI r10) (...))
1342         (set (...) (reg:DI r9))
1343      Replacing r9 with r11 is invalid.  */
1344   if (mode != vd->e[regno].mode)
1345     {
1346       if (hard_regno_nregs[regno][mode]
1347           > hard_regno_nregs[regno][vd->e[regno].mode])
1348         return NULL_RTX;
1349     }
1350
1351   for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno)
1352     {
1353       enum machine_mode oldmode = vd->e[i].mode;
1354       rtx new;
1355       unsigned int last;
1356
1357       for (last = i; last < i + hard_regno_nregs[i][mode]; last++)
1358         if (!TEST_HARD_REG_BIT (reg_class_contents[cl], last))
1359           return NULL_RTX;
1360
1361       new = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno);
1362       if (new)
1363         {
1364           ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg);
1365           REG_ATTRS (new) = REG_ATTRS (reg);
1366           return new;
1367         }
1368     }
1369
1370   return NULL_RTX;
1371 }
1372
1373 /* If possible, replace the register at *LOC with the oldest register
1374    in register class CL.  Return true if successfully replaced.  */
1375
1376 static bool
1377 replace_oldest_value_reg (rtx *loc, enum reg_class cl, rtx insn,
1378                           struct value_data *vd)
1379 {
1380   rtx new = find_oldest_value_reg (cl, *loc, vd);
1381   if (new)
1382     {
1383       if (dump_file)
1384         fprintf (dump_file, "insn %u: replaced reg %u with %u\n",
1385                  INSN_UID (insn), REGNO (*loc), REGNO (new));
1386
1387       *loc = new;
1388       return true;
1389     }
1390   return false;
1391 }
1392
1393 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1394    Adapted from find_reloads_address_1.  CL is INDEX_REG_CLASS or
1395    BASE_REG_CLASS depending on how the register is being considered.  */
1396
1397 static bool
1398 replace_oldest_value_addr (rtx *loc, enum reg_class cl,
1399                            enum machine_mode mode, rtx insn,
1400                            struct value_data *vd)
1401 {
1402   rtx x = *loc;
1403   RTX_CODE code = GET_CODE (x);
1404   const char *fmt;
1405   int i, j;
1406   bool changed = false;
1407
1408   switch (code)
1409     {
1410     case PLUS:
1411       {
1412         rtx orig_op0 = XEXP (x, 0);
1413         rtx orig_op1 = XEXP (x, 1);
1414         RTX_CODE code0 = GET_CODE (orig_op0);
1415         RTX_CODE code1 = GET_CODE (orig_op1);
1416         rtx op0 = orig_op0;
1417         rtx op1 = orig_op1;
1418         rtx *locI = NULL;
1419         rtx *locB = NULL;
1420         rtx *locB_reg = NULL;
1421
1422         if (GET_CODE (op0) == SUBREG)
1423           {
1424             op0 = SUBREG_REG (op0);
1425             code0 = GET_CODE (op0);
1426           }
1427
1428         if (GET_CODE (op1) == SUBREG)
1429           {
1430             op1 = SUBREG_REG (op1);
1431             code1 = GET_CODE (op1);
1432           }
1433
1434         if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
1435             || code0 == ZERO_EXTEND || code1 == MEM)
1436           {
1437             locI = &XEXP (x, 0);
1438             locB = &XEXP (x, 1);
1439           }
1440         else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
1441                  || code1 == ZERO_EXTEND || code0 == MEM)
1442           {
1443             locI = &XEXP (x, 1);
1444             locB = &XEXP (x, 0);
1445           }
1446         else if (code0 == CONST_INT || code0 == CONST
1447                  || code0 == SYMBOL_REF || code0 == LABEL_REF)
1448           locB = &XEXP (x, 1);
1449         else if (code1 == CONST_INT || code1 == CONST
1450                  || code1 == SYMBOL_REF || code1 == LABEL_REF)
1451           locB = &XEXP (x, 0);
1452         else if (code0 == REG && code1 == REG)
1453           {
1454             int index_op;
1455
1456             if (REG_OK_FOR_INDEX_P (op0)
1457                 && REG_MODE_OK_FOR_REG_BASE_P (op1, mode))
1458               index_op = 0;
1459             else if (REG_OK_FOR_INDEX_P (op1)
1460                      && REG_MODE_OK_FOR_REG_BASE_P (op0, mode))
1461               index_op = 1;
1462             else if (REG_MODE_OK_FOR_REG_BASE_P (op1, mode))
1463               index_op = 0;
1464             else if (REG_MODE_OK_FOR_REG_BASE_P (op0, mode))
1465               index_op = 1;
1466             else if (REG_OK_FOR_INDEX_P (op1))
1467               index_op = 1;
1468             else
1469               index_op = 0;
1470
1471             locI = &XEXP (x, index_op);
1472             locB_reg = &XEXP (x, !index_op);
1473           }
1474         else if (code0 == REG)
1475           {
1476             locI = &XEXP (x, 0);
1477             locB = &XEXP (x, 1);
1478           }
1479         else if (code1 == REG)
1480           {
1481             locI = &XEXP (x, 1);
1482             locB = &XEXP (x, 0);
1483           }
1484
1485         if (locI)
1486           changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode,
1487                                                 insn, vd);
1488         if (locB)
1489           changed |= replace_oldest_value_addr (locB,
1490                                                 MODE_BASE_REG_CLASS (mode),
1491                                                 mode, insn, vd);
1492         if (locB_reg)
1493           changed |= replace_oldest_value_addr (locB_reg,
1494                                                 MODE_BASE_REG_REG_CLASS (mode),
1495                                                 mode, insn, vd);
1496         return changed;
1497       }
1498
1499     case POST_INC:
1500     case POST_DEC:
1501     case POST_MODIFY:
1502     case PRE_INC:
1503     case PRE_DEC:
1504     case PRE_MODIFY:
1505       return false;
1506
1507     case MEM:
1508       return replace_oldest_value_mem (x, insn, vd);
1509
1510     case REG:
1511       return replace_oldest_value_reg (loc, cl, insn, vd);
1512
1513     default:
1514       break;
1515     }
1516
1517   fmt = GET_RTX_FORMAT (code);
1518   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1519     {
1520       if (fmt[i] == 'e')
1521         changed |= replace_oldest_value_addr (&XEXP (x, i), cl, mode,
1522                                               insn, vd);
1523       else if (fmt[i] == 'E')
1524         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1525           changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), cl,
1526                                                 mode, insn, vd);
1527     }
1528
1529   return changed;
1530 }
1531
1532 /* Similar to replace_oldest_value_reg, but X contains a memory.  */
1533
1534 static bool
1535 replace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd)
1536 {
1537   return replace_oldest_value_addr (&XEXP (x, 0),
1538                                     MODE_BASE_REG_CLASS (GET_MODE (x)),
1539                                     GET_MODE (x), insn, vd);
1540 }
1541
1542 /* Perform the forward copy propagation on basic block BB.  */
1543
1544 static bool
1545 copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd)
1546 {
1547   bool changed = false;
1548   rtx insn;
1549
1550   for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
1551     {
1552       int n_ops, i, alt, predicated;
1553       bool is_asm;
1554       rtx set;
1555
1556       if (! INSN_P (insn))
1557         {
1558           if (insn == BB_END (bb))
1559             break;
1560           else
1561             continue;
1562         }
1563
1564       set = single_set (insn);
1565       extract_insn (insn);
1566       if (! constrain_operands (1))
1567         fatal_insn_not_found (insn);
1568       preprocess_constraints ();
1569       alt = which_alternative;
1570       n_ops = recog_data.n_operands;
1571       is_asm = asm_noperands (PATTERN (insn)) >= 0;
1572
1573       /* Simplify the code below by rewriting things to reflect
1574          matching constraints.  Also promote OP_OUT to OP_INOUT
1575          in predicated instructions.  */
1576
1577       predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1578       for (i = 0; i < n_ops; ++i)
1579         {
1580           int matches = recog_op_alt[i][alt].matches;
1581           if (matches >= 0)
1582             recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
1583           if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
1584               || (predicated && recog_data.operand_type[i] == OP_OUT))
1585             recog_data.operand_type[i] = OP_INOUT;
1586         }
1587
1588       /* For each earlyclobber operand, zap the value data.  */
1589       for (i = 0; i < n_ops; i++)
1590         if (recog_op_alt[i][alt].earlyclobber)
1591           kill_value (recog_data.operand[i], vd);
1592
1593       /* Within asms, a clobber cannot overlap inputs or outputs.
1594          I wouldn't think this were true for regular insns, but
1595          scan_rtx treats them like that...  */
1596       note_stores (PATTERN (insn), kill_clobbered_value, vd);
1597
1598       /* Kill all auto-incremented values.  */
1599       /* ??? REG_INC is useless, since stack pushes aren't done that way.  */
1600       for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd);
1601
1602       /* Kill all early-clobbered operands.  */
1603       for (i = 0; i < n_ops; i++)
1604         if (recog_op_alt[i][alt].earlyclobber)
1605           kill_value (recog_data.operand[i], vd);
1606
1607       /* Special-case plain move instructions, since we may well
1608          be able to do the move from a different register class.  */
1609       if (set && REG_P (SET_SRC (set)))
1610         {
1611           rtx src = SET_SRC (set);
1612           unsigned int regno = REGNO (src);
1613           enum machine_mode mode = GET_MODE (src);
1614           unsigned int i;
1615           rtx new;
1616
1617           /* If we are accessing SRC in some mode other that what we
1618              set it in, make sure that the replacement is valid.  */
1619           if (mode != vd->e[regno].mode)
1620             {
1621               if (hard_regno_nregs[regno][mode]
1622                   > hard_regno_nregs[regno][vd->e[regno].mode])
1623                 goto no_move_special_case;
1624             }
1625
1626           /* If the destination is also a register, try to find a source
1627              register in the same class.  */
1628           if (REG_P (SET_DEST (set)))
1629             {
1630               new = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd);
1631               if (new && validate_change (insn, &SET_SRC (set), new, 0))
1632                 {
1633                   if (dump_file)
1634                     fprintf (dump_file,
1635                              "insn %u: replaced reg %u with %u\n",
1636                              INSN_UID (insn), regno, REGNO (new));
1637                   changed = true;
1638                   goto did_replacement;
1639                 }
1640             }
1641
1642           /* Otherwise, try all valid registers and see if its valid.  */
1643           for (i = vd->e[regno].oldest_regno; i != regno;
1644                i = vd->e[i].next_regno)
1645             {
1646               new = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode,
1647                                        mode, i, regno);
1648               if (new != NULL_RTX)
1649                 {
1650                   if (validate_change (insn, &SET_SRC (set), new, 0))
1651                     {
1652                       ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src);
1653                       REG_ATTRS (new) = REG_ATTRS (src);
1654                       if (dump_file)
1655                         fprintf (dump_file,
1656                                  "insn %u: replaced reg %u with %u\n",
1657                                  INSN_UID (insn), regno, REGNO (new));
1658                       changed = true;
1659                       goto did_replacement;
1660                     }
1661                 }
1662             }
1663         }
1664       no_move_special_case:
1665
1666       /* For each input operand, replace a hard register with the
1667          eldest live copy that's in an appropriate register class.  */
1668       for (i = 0; i < n_ops; i++)
1669         {
1670           bool replaced = false;
1671
1672           /* Don't scan match_operand here, since we've no reg class
1673              information to pass down.  Any operands that we could
1674              substitute in will be represented elsewhere.  */
1675           if (recog_data.constraints[i][0] == '\0')
1676             continue;
1677
1678           /* Don't replace in asms intentionally referencing hard regs.  */
1679           if (is_asm && REG_P (recog_data.operand[i])
1680               && (REGNO (recog_data.operand[i])
1681                   == ORIGINAL_REGNO (recog_data.operand[i])))
1682             continue;
1683
1684           if (recog_data.operand_type[i] == OP_IN)
1685             {
1686               if (recog_op_alt[i][alt].is_address)
1687                 replaced
1688                   = replace_oldest_value_addr (recog_data.operand_loc[i],
1689                                                recog_op_alt[i][alt].cl,
1690                                                VOIDmode, insn, vd);
1691               else if (REG_P (recog_data.operand[i]))
1692                 replaced
1693                   = replace_oldest_value_reg (recog_data.operand_loc[i],
1694                                               recog_op_alt[i][alt].cl,
1695                                               insn, vd);
1696               else if (MEM_P (recog_data.operand[i]))
1697                 replaced = replace_oldest_value_mem (recog_data.operand[i],
1698                                                      insn, vd);
1699             }
1700           else if (MEM_P (recog_data.operand[i]))
1701             replaced = replace_oldest_value_mem (recog_data.operand[i],
1702                                                  insn, vd);
1703
1704           /* If we performed any replacement, update match_dups.  */
1705           if (replaced)
1706             {
1707               int j;
1708               rtx new;
1709
1710               changed = true;
1711
1712               new = *recog_data.operand_loc[i];
1713               recog_data.operand[i] = new;
1714               for (j = 0; j < recog_data.n_dups; j++)
1715                 if (recog_data.dup_num[j] == i)
1716                   *recog_data.dup_loc[j] = new;
1717             }
1718         }
1719
1720     did_replacement:
1721       /* Clobber call-clobbered registers.  */
1722       if (CALL_P (insn))
1723         for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1724           if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1725             kill_value_regno (i, 1, vd);
1726
1727       /* Notice stores.  */
1728       note_stores (PATTERN (insn), kill_set_value, vd);
1729
1730       /* Notice copies.  */
1731       if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
1732         copy_value (SET_DEST (set), SET_SRC (set), vd);
1733
1734       if (insn == BB_END (bb))
1735         break;
1736     }
1737
1738   return changed;
1739 }
1740
1741 /* Main entry point for the forward copy propagation optimization.  */
1742
1743 void
1744 copyprop_hardreg_forward (void)
1745 {
1746   struct value_data *all_vd;
1747   bool need_refresh;
1748   basic_block bb;
1749   sbitmap visited;
1750
1751   need_refresh = false;
1752
1753   all_vd = xmalloc (sizeof (struct value_data) * last_basic_block);
1754
1755   visited = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
1756   sbitmap_zero (visited);
1757
1758   FOR_EACH_BB (bb)
1759     {
1760       SET_BIT (visited, bb->index - (INVALID_BLOCK + 1));
1761
1762       /* If a block has a single predecessor, that we've already
1763          processed, begin with the value data that was live at
1764          the end of the predecessor block.  */
1765       /* ??? Ought to use more intelligent queuing of blocks.  */
1766       if (EDGE_COUNT (bb->preds) == 1
1767           && TEST_BIT (visited,
1768                        EDGE_PRED (bb, 0)->src->index - (INVALID_BLOCK + 1))
1769           && ! (EDGE_PRED (bb, 0)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
1770         all_vd[bb->index] = all_vd[EDGE_PRED (bb, 0)->src->index];
1771       else
1772         init_value_data (all_vd + bb->index);
1773
1774       if (copyprop_hardreg_forward_1 (bb, all_vd + bb->index))
1775         need_refresh = true;
1776     }
1777
1778   sbitmap_free (visited);  
1779
1780   if (need_refresh)
1781     {
1782       if (dump_file)
1783         fputs ("\n\n", dump_file);
1784
1785       /* ??? Irritatingly, delete_noop_moves does not take a set of blocks
1786          to scan, so we have to do a life update with no initial set of
1787          blocks Just In Case.  */
1788       delete_noop_moves ();
1789       update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
1790                         PROP_DEATH_NOTES
1791                         | PROP_SCAN_DEAD_CODE
1792                         | PROP_KILL_DEAD_CODE);
1793     }
1794
1795   free (all_vd);
1796 }
1797
1798 /* Dump the value chain data to stderr.  */
1799
1800 void
1801 debug_value_data (struct value_data *vd)
1802 {
1803   HARD_REG_SET set;
1804   unsigned int i, j;
1805
1806   CLEAR_HARD_REG_SET (set);
1807
1808   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1809     if (vd->e[i].oldest_regno == i)
1810       {
1811         if (vd->e[i].mode == VOIDmode)
1812           {
1813             if (vd->e[i].next_regno != INVALID_REGNUM)
1814               fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n",
1815                        i, vd->e[i].next_regno);
1816             continue;
1817           }
1818
1819         SET_HARD_REG_BIT (set, i);
1820         fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode));
1821
1822         for (j = vd->e[i].next_regno;
1823              j != INVALID_REGNUM;
1824              j = vd->e[j].next_regno)
1825           {
1826             if (TEST_HARD_REG_BIT (set, j))
1827               {
1828                 fprintf (stderr, "[%u] Loop in regno chain\n", j);
1829                 return;
1830               }
1831
1832             if (vd->e[j].oldest_regno != i)
1833               {
1834                 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n",
1835                          j, vd->e[j].oldest_regno);
1836                 return;
1837               }
1838             SET_HARD_REG_BIT (set, j);
1839             fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode));
1840           }
1841         fputc ('\n', stderr);
1842       }
1843
1844   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1845     if (! TEST_HARD_REG_BIT (set, i)
1846         && (vd->e[i].mode != VOIDmode
1847             || vd->e[i].oldest_regno != i
1848             || vd->e[i].next_regno != INVALID_REGNUM))
1849       fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n",
1850                i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1851                vd->e[i].next_regno);
1852 }
1853
1854 #ifdef ENABLE_CHECKING
1855 static void
1856 validate_value_data (struct value_data *vd)
1857 {
1858   HARD_REG_SET set;
1859   unsigned int i, j;
1860
1861   CLEAR_HARD_REG_SET (set);
1862
1863   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1864     if (vd->e[i].oldest_regno == i)
1865       {
1866         if (vd->e[i].mode == VOIDmode)
1867           {
1868             if (vd->e[i].next_regno != INVALID_REGNUM)
1869               internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1870                               i, vd->e[i].next_regno);
1871             continue;
1872           }
1873
1874         SET_HARD_REG_BIT (set, i);
1875
1876         for (j = vd->e[i].next_regno;
1877              j != INVALID_REGNUM;
1878              j = vd->e[j].next_regno)
1879           {
1880             if (TEST_HARD_REG_BIT (set, j))
1881               internal_error ("validate_value_data: Loop in regno chain (%u)",
1882                               j);
1883             if (vd->e[j].oldest_regno != i)
1884               internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1885                               j, vd->e[j].oldest_regno);
1886
1887             SET_HARD_REG_BIT (set, j);
1888           }
1889       }
1890
1891   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1892     if (! TEST_HARD_REG_BIT (set, i)
1893         && (vd->e[i].mode != VOIDmode
1894             || vd->e[i].oldest_regno != i
1895             || vd->e[i].next_regno != INVALID_REGNUM))
1896       internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1897                       i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1898                       vd->e[i].next_regno);
1899 }
1900 #endif