OSDN Git Service

fcdaaf79e81d5a7317c6be3624c5f423191cd019
[pf3gnuchains/gcc-fork.git] / gcc / regrename.c
1 /* Register renaming 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 struct du_chain
44 {
45   struct du_chain *next_chain;
46   struct du_chain *next_use;
47
48   rtx insn;
49   rtx *loc;
50   ENUM_BITFIELD(reg_class) cl : 16;
51   unsigned int need_caller_save_reg:1;
52   unsigned int earlyclobber:1;
53 };
54
55 enum scan_actions
56 {
57   terminate_all_read,
58   terminate_overlapping_read,
59   terminate_write,
60   terminate_dead,
61   mark_read,
62   mark_write,
63   /* mark_access is for marking the destination regs in
64      REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
65      note is updated properly.  */
66   mark_access
67 };
68
69 static const char * const scan_actions_name[] =
70 {
71   "terminate_all_read",
72   "terminate_overlapping_read",
73   "terminate_write",
74   "terminate_dead",
75   "mark_read",
76   "mark_write",
77   "mark_access"
78 };
79
80 static struct obstack rename_obstack;
81
82 static void do_replace (struct du_chain *, int);
83 static void scan_rtx_reg (rtx, rtx *, enum reg_class,
84                           enum scan_actions, enum op_type, int);
85 static void scan_rtx_address (rtx, rtx *, enum reg_class,
86                               enum scan_actions, enum machine_mode);
87 static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
88                       enum op_type, int);
89 static struct du_chain *build_def_use (basic_block);
90 static void dump_def_use_chain (struct du_chain *);
91 static void note_sets (rtx, const_rtx, void *);
92 static void clear_dead_regs (HARD_REG_SET *, enum reg_note, rtx);
93 static void merge_overlapping_regs (basic_block, HARD_REG_SET *,
94                                     struct du_chain *);
95
96 /* Called through note_stores.  Find sets of registers, and
97    record them in *DATA (which is actually a HARD_REG_SET *).  */
98
99 static void
100 note_sets (rtx x, const_rtx set ATTRIBUTE_UNUSED, void *data)
101 {
102   HARD_REG_SET *pset = (HARD_REG_SET *) data;
103
104   if (GET_CODE (x) == SUBREG)
105     x = SUBREG_REG (x);
106   if (!REG_P (x))
107     return;
108   /* There must not be pseudos at this point.  */
109   gcc_assert (HARD_REGISTER_P (x));
110   add_to_hard_reg_set (pset, GET_MODE (x), REGNO (x));
111 }
112
113 /* Clear all registers from *PSET for which a note of kind KIND can be found
114    in the list NOTES.  */
115
116 static void
117 clear_dead_regs (HARD_REG_SET *pset, enum reg_note kind, rtx notes)
118 {
119   rtx note;
120   for (note = notes; note; note = XEXP (note, 1))
121     if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0)))
122       {
123         rtx reg = XEXP (note, 0);
124         /* There must not be pseudos at this point.  */
125         gcc_assert (HARD_REGISTER_P (reg));
126         remove_from_hard_reg_set (pset, GET_MODE (reg), REGNO (reg));
127       }
128 }
129
130 /* For a def-use chain CHAIN in basic block B, find which registers overlap
131    its lifetime and set the corresponding bits in *PSET.  */
132
133 static void
134 merge_overlapping_regs (basic_block b, HARD_REG_SET *pset,
135                         struct du_chain *chain)
136 {
137   struct du_chain *t = chain;
138   rtx insn;
139   HARD_REG_SET live;
140   df_ref *def_rec;
141
142   REG_SET_TO_HARD_REG_SET (live, df_get_live_in (b));
143   for (def_rec = df_get_artificial_defs (b->index); *def_rec; def_rec++)
144     {
145       df_ref def = *def_rec;
146       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
147         SET_HARD_REG_BIT (live, DF_REF_REGNO (def));
148     }
149   insn = BB_HEAD (b);
150   while (t)
151     {
152       /* Search forward until the next reference to the register to be
153          renamed.  */
154       while (insn != t->insn)
155         {
156           if (INSN_P (insn))
157             {
158               clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn));
159               note_stores (PATTERN (insn), note_sets, (void *) &live);
160               /* Only record currently live regs if we are inside the
161                  reg's live range.  */
162               if (t != chain)
163                 IOR_HARD_REG_SET (*pset, live);
164               clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn));
165             }
166           insn = NEXT_INSN (insn);
167         }
168
169       IOR_HARD_REG_SET (*pset, live);
170
171       /* For the last reference, also merge in all registers set in the
172          same insn.
173          @@@ We only have take earlyclobbered sets into account.  */
174       if (! t->next_use)
175         note_stores (PATTERN (insn), note_sets, (void *) pset);
176
177       t = t->next_use;
178     }
179 }
180
181 /* Perform register renaming on the current function.  */
182
183 static unsigned int
184 regrename_optimize (void)
185 {
186   int tick[FIRST_PSEUDO_REGISTER];
187   int this_tick = 0;
188   basic_block bb;
189   char *first_obj;
190
191   df_set_flags (DF_LR_RUN_DCE);
192   df_note_add_problem ();
193   df_analyze ();
194   df_set_flags (DF_DEFER_INSN_RESCAN);
195
196   memset (tick, 0, sizeof tick);
197
198   gcc_obstack_init (&rename_obstack);
199   first_obj = XOBNEWVAR (&rename_obstack, char, 0);
200
201   FOR_EACH_BB (bb)
202     {
203       struct du_chain *all_chains = 0;
204       HARD_REG_SET unavailable;
205       HARD_REG_SET regs_seen;
206
207       CLEAR_HARD_REG_SET (unavailable);
208
209       if (dump_file)
210         fprintf (dump_file, "\nBasic block %d:\n", bb->index);
211
212       all_chains = build_def_use (bb);
213
214       if (dump_file)
215         dump_def_use_chain (all_chains);
216
217       CLEAR_HARD_REG_SET (unavailable);
218       /* Don't clobber traceback for noreturn functions.  */
219       if (frame_pointer_needed)
220         {
221           add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
222 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
223           add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
224 #endif
225         }
226
227       CLEAR_HARD_REG_SET (regs_seen);
228       while (all_chains)
229         {
230           int new_reg, best_new_reg;
231           int n_uses;
232           struct du_chain *this_du = all_chains;
233           struct du_chain *tmp, *last;
234           HARD_REG_SET this_unavailable;
235           int reg = REGNO (*this_du->loc);
236           int i;
237
238           all_chains = this_du->next_chain;
239
240           best_new_reg = reg;
241
242 #if 0 /* This just disables optimization opportunities.  */
243           /* Only rename once we've seen the reg more than once.  */
244           if (! TEST_HARD_REG_BIT (regs_seen, reg))
245             {
246               SET_HARD_REG_BIT (regs_seen, reg);
247               continue;
248             }
249 #endif
250
251           if (fixed_regs[reg] || global_regs[reg]
252 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
253               || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
254 #else
255               || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
256 #endif
257               )
258             continue;
259
260           COPY_HARD_REG_SET (this_unavailable, unavailable);
261
262           /* Find last entry on chain (which has the need_caller_save bit),
263              count number of uses, and narrow the set of registers we can
264              use for renaming.  */
265           n_uses = 0;
266           for (last = this_du; last->next_use; last = last->next_use)
267             {
268               n_uses++;
269               IOR_COMPL_HARD_REG_SET (this_unavailable,
270                                       reg_class_contents[last->cl]);
271             }
272           if (n_uses < 1)
273             continue;
274
275           IOR_COMPL_HARD_REG_SET (this_unavailable,
276                                   reg_class_contents[last->cl]);
277
278           if (this_du->need_caller_save_reg)
279             IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
280
281           merge_overlapping_regs (bb, &this_unavailable, this_du);
282
283           /* Now potential_regs is a reasonable approximation, let's
284              have a closer look at each register still in there.  */
285           for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
286             {
287               int nregs = hard_regno_nregs[new_reg][GET_MODE (*this_du->loc)];
288
289               for (i = nregs - 1; i >= 0; --i)
290                 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
291                     || fixed_regs[new_reg + i]
292                     || global_regs[new_reg + i]
293                     /* Can't use regs which aren't saved by the prologue.  */
294                     || (! df_regs_ever_live_p (new_reg + i)
295                         && ! call_used_regs[new_reg + i])
296 #ifdef LEAF_REGISTERS
297                     /* We can't use a non-leaf register if we're in a
298                        leaf function.  */
299                     || (current_function_is_leaf
300                         && !LEAF_REGISTERS[new_reg + i])
301 #endif
302 #ifdef HARD_REGNO_RENAME_OK
303                     || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
304 #endif
305                     )
306                   break;
307               if (i >= 0)
308                 continue;
309
310               /* See whether it accepts all modes that occur in
311                  definition and uses.  */
312               for (tmp = this_du; tmp; tmp = tmp->next_use)
313                 if (! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
314                     || (tmp->need_caller_save_reg
315                         && ! (HARD_REGNO_CALL_PART_CLOBBERED
316                               (reg, GET_MODE (*tmp->loc)))
317                         && (HARD_REGNO_CALL_PART_CLOBBERED
318                             (new_reg, GET_MODE (*tmp->loc)))))
319                   break;
320               if (! tmp)
321                 {
322                   if (tick[best_new_reg] > tick[new_reg])
323                     best_new_reg = new_reg;
324                 }
325             }
326
327           if (dump_file)
328             {
329               fprintf (dump_file, "Register %s in insn %d",
330                        reg_names[reg], INSN_UID (last->insn));
331               if (last->need_caller_save_reg)
332                 fprintf (dump_file, " crosses a call");
333             }
334
335           if (best_new_reg == reg)
336             {
337               tick[reg] = ++this_tick;
338               if (dump_file)
339                 fprintf (dump_file, "; no available better choice\n");
340               continue;
341             }
342
343           if (dump_file)
344             fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
345
346           do_replace (this_du, best_new_reg);
347           tick[best_new_reg] = ++this_tick;
348           df_set_regs_ever_live (best_new_reg, true);
349         }
350
351       obstack_free (&rename_obstack, first_obj);
352     }
353
354   obstack_free (&rename_obstack, NULL);
355
356   if (dump_file)
357     fputc ('\n', dump_file);
358
359   return 0;
360 }
361
362 static void
363 do_replace (struct du_chain *chain, int reg)
364 {
365   while (chain)
366     {
367       unsigned int regno = ORIGINAL_REGNO (*chain->loc);
368       struct reg_attrs * attr = REG_ATTRS (*chain->loc);
369       int reg_ptr = REG_POINTER (*chain->loc);
370
371       *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
372       if (regno >= FIRST_PSEUDO_REGISTER)
373         ORIGINAL_REGNO (*chain->loc) = regno;
374       REG_ATTRS (*chain->loc) = attr;
375       REG_POINTER (*chain->loc) = reg_ptr;
376       df_insn_rescan (chain->insn);
377       chain = chain->next_use;
378     }
379 }
380
381
382 static struct du_chain *open_chains;
383 static struct du_chain *closed_chains;
384
385 static void
386 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl,
387               enum scan_actions action, enum op_type type, int earlyclobber)
388 {
389   struct du_chain **p;
390   rtx x = *loc;
391   enum machine_mode mode = GET_MODE (x);
392   int this_regno = REGNO (x);
393   int this_nregs = hard_regno_nregs[this_regno][mode];
394
395   if (action == mark_write)
396     {
397       if (type == OP_OUT)
398         {
399           struct du_chain *this_du = XOBNEW (&rename_obstack, struct du_chain);
400           this_du->next_use = 0;
401           this_du->next_chain = open_chains;
402           this_du->loc = loc;
403           this_du->insn = insn;
404           this_du->cl = cl;
405           this_du->need_caller_save_reg = 0;
406           this_du->earlyclobber = earlyclobber;
407           open_chains = this_du;
408         }
409       return;
410     }
411
412   if ((type == OP_OUT) != (action == terminate_write || action == mark_access))
413     return;
414
415   for (p = &open_chains; *p;)
416     {
417       struct du_chain *this_du = *p;
418
419       /* Check if the chain has been terminated if it has then skip to
420          the next chain.
421
422          This can happen when we've already appended the location to
423          the chain in Step 3, but are trying to hide in-out operands
424          from terminate_write in Step 5.  */
425
426       if (*this_du->loc == cc0_rtx)
427         p = &this_du->next_chain;
428       else
429         {
430           int regno = REGNO (*this_du->loc);
431           int nregs = hard_regno_nregs[regno][GET_MODE (*this_du->loc)];
432           int exact_match = (regno == this_regno && nregs == this_nregs);
433
434           if (regno + nregs <= this_regno
435               || this_regno + this_nregs <= regno)
436             {
437               p = &this_du->next_chain;
438               continue;
439             }
440
441           if (action == mark_read || action == mark_access)
442             {
443               gcc_assert (exact_match);
444
445               /* ??? Class NO_REGS can happen if the md file makes use of
446                  EXTRA_CONSTRAINTS to match registers.  Which is arguably
447                  wrong, but there we are.  Since we know not what this may
448                  be replaced with, terminate the chain.  */
449               if (cl != NO_REGS)
450                 {
451                   this_du = XOBNEW (&rename_obstack, struct du_chain);
452                   this_du->next_use = 0;
453                   this_du->next_chain = (*p)->next_chain;
454                   this_du->loc = loc;
455                   this_du->insn = insn;
456                   this_du->cl = cl;
457                   this_du->need_caller_save_reg = 0;
458                   while (*p)
459                     p = &(*p)->next_use;
460                   *p = this_du;
461                   return;
462                 }
463             }
464
465           if (action != terminate_overlapping_read || ! exact_match)
466             {
467               struct du_chain *next = this_du->next_chain;
468
469               /* Whether the terminated chain can be used for renaming
470                  depends on the action and this being an exact match.
471                  In either case, we remove this element from open_chains.  */
472
473               if ((action == terminate_dead || action == terminate_write)
474                   && exact_match)
475                 {
476                   this_du->next_chain = closed_chains;
477                   closed_chains = this_du;
478                   if (dump_file)
479                     fprintf (dump_file,
480                              "Closing chain %s at insn %d (%s)\n",
481                              reg_names[REGNO (*this_du->loc)], INSN_UID (insn),
482                              scan_actions_name[(int) action]);
483                 }
484               else
485                 {
486                   if (dump_file)
487                     fprintf (dump_file,
488                              "Discarding chain %s at insn %d (%s)\n",
489                              reg_names[REGNO (*this_du->loc)], INSN_UID (insn),
490                              scan_actions_name[(int) action]);
491                 }
492               *p = next;
493             }
494           else
495             p = &this_du->next_chain;
496         }
497     }
498 }
499
500 /* Adapted from find_reloads_address_1.  CL is INDEX_REG_CLASS or
501    BASE_REG_CLASS depending on how the register is being considered.  */
502
503 static void
504 scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl,
505                   enum scan_actions action, enum machine_mode mode)
506 {
507   rtx x = *loc;
508   RTX_CODE code = GET_CODE (x);
509   const char *fmt;
510   int i, j;
511
512   if (action == mark_write || action == mark_access)
513     return;
514
515   switch (code)
516     {
517     case PLUS:
518       {
519         rtx orig_op0 = XEXP (x, 0);
520         rtx orig_op1 = XEXP (x, 1);
521         RTX_CODE code0 = GET_CODE (orig_op0);
522         RTX_CODE code1 = GET_CODE (orig_op1);
523         rtx op0 = orig_op0;
524         rtx op1 = orig_op1;
525         rtx *locI = NULL;
526         rtx *locB = NULL;
527         enum rtx_code index_code = SCRATCH;
528
529         if (GET_CODE (op0) == SUBREG)
530           {
531             op0 = SUBREG_REG (op0);
532             code0 = GET_CODE (op0);
533           }
534
535         if (GET_CODE (op1) == SUBREG)
536           {
537             op1 = SUBREG_REG (op1);
538             code1 = GET_CODE (op1);
539           }
540
541         if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
542             || code0 == ZERO_EXTEND || code1 == MEM)
543           {
544             locI = &XEXP (x, 0);
545             locB = &XEXP (x, 1);
546             index_code = GET_CODE (*locI);
547           }
548         else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
549                  || code1 == ZERO_EXTEND || code0 == MEM)
550           {
551             locI = &XEXP (x, 1);
552             locB = &XEXP (x, 0);
553             index_code = GET_CODE (*locI);
554           }
555         else if (code0 == CONST_INT || code0 == CONST
556                  || code0 == SYMBOL_REF || code0 == LABEL_REF)
557           {
558             locB = &XEXP (x, 1);
559             index_code = GET_CODE (XEXP (x, 0));
560           }
561         else if (code1 == CONST_INT || code1 == CONST
562                  || code1 == SYMBOL_REF || code1 == LABEL_REF)
563           {
564             locB = &XEXP (x, 0);
565             index_code = GET_CODE (XEXP (x, 1));
566           }
567         else if (code0 == REG && code1 == REG)
568           {
569             int index_op;
570             unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
571
572             if (REGNO_OK_FOR_INDEX_P (regno1)
573                 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
574               index_op = 1;
575             else if (REGNO_OK_FOR_INDEX_P (regno0)
576                      && regno_ok_for_base_p (regno1, mode, PLUS, REG))
577               index_op = 0;
578             else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
579                      || REGNO_OK_FOR_INDEX_P (regno1))
580               index_op = 1;
581             else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
582               index_op = 0;
583             else
584               index_op = 1;
585
586             locI = &XEXP (x, index_op);
587             locB = &XEXP (x, !index_op);
588             index_code = GET_CODE (*locI);
589           }
590         else if (code0 == REG)
591           {
592             locI = &XEXP (x, 0);
593             locB = &XEXP (x, 1);
594             index_code = GET_CODE (*locI);
595           }
596         else if (code1 == REG)
597           {
598             locI = &XEXP (x, 1);
599             locB = &XEXP (x, 0);
600             index_code = GET_CODE (*locI);
601           }
602
603         if (locI)
604           scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
605         if (locB)
606           scan_rtx_address (insn, locB, base_reg_class (mode, PLUS, index_code),
607                             action, mode);
608
609         return;
610       }
611
612     case POST_INC:
613     case POST_DEC:
614     case POST_MODIFY:
615     case PRE_INC:
616     case PRE_DEC:
617     case PRE_MODIFY:
618 #ifndef AUTO_INC_DEC
619       /* If the target doesn't claim to handle autoinc, this must be
620          something special, like a stack push.  Kill this chain.  */
621       action = terminate_all_read;
622 #endif
623       break;
624
625     case MEM:
626       scan_rtx_address (insn, &XEXP (x, 0),
627                         base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
628                         GET_MODE (x));
629       return;
630
631     case REG:
632       scan_rtx_reg (insn, loc, cl, action, OP_IN, 0);
633       return;
634
635     default:
636       break;
637     }
638
639   fmt = GET_RTX_FORMAT (code);
640   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
641     {
642       if (fmt[i] == 'e')
643         scan_rtx_address (insn, &XEXP (x, i), cl, action, mode);
644       else if (fmt[i] == 'E')
645         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
646           scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode);
647     }
648 }
649
650 static void
651 scan_rtx (rtx insn, rtx *loc, enum reg_class cl,
652           enum scan_actions action, enum op_type type, int earlyclobber)
653 {
654   const char *fmt;
655   rtx x = *loc;
656   enum rtx_code code = GET_CODE (x);
657   int i, j;
658
659   code = GET_CODE (x);
660   switch (code)
661     {
662     case CONST:
663     case CONST_INT:
664     case CONST_DOUBLE:
665     case CONST_FIXED:
666     case CONST_VECTOR:
667     case SYMBOL_REF:
668     case LABEL_REF:
669     case CC0:
670     case PC:
671       return;
672
673     case REG:
674       scan_rtx_reg (insn, loc, cl, action, type, earlyclobber);
675       return;
676
677     case MEM:
678       scan_rtx_address (insn, &XEXP (x, 0),
679                         base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
680                         GET_MODE (x));
681       return;
682
683     case SET:
684       scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN, 0);
685       scan_rtx (insn, &SET_DEST (x), cl, action,
686                 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0);
687       return;
688
689     case STRICT_LOW_PART:
690       scan_rtx (insn, &XEXP (x, 0), cl, action, OP_INOUT, earlyclobber);
691       return;
692
693     case ZERO_EXTRACT:
694     case SIGN_EXTRACT:
695       scan_rtx (insn, &XEXP (x, 0), cl, action,
696                 type == OP_IN ? OP_IN : OP_INOUT, earlyclobber);
697       scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN, 0);
698       scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN, 0);
699       return;
700
701     case POST_INC:
702     case PRE_INC:
703     case POST_DEC:
704     case PRE_DEC:
705     case POST_MODIFY:
706     case PRE_MODIFY:
707       /* Should only happen inside MEM.  */
708       gcc_unreachable ();
709
710     case CLOBBER:
711       scan_rtx (insn, &SET_DEST (x), cl, action,
712                 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0);
713       return;
714
715     case EXPR_LIST:
716       scan_rtx (insn, &XEXP (x, 0), cl, action, type, 0);
717       if (XEXP (x, 1))
718         scan_rtx (insn, &XEXP (x, 1), cl, action, type, 0);
719       return;
720
721     default:
722       break;
723     }
724
725   fmt = GET_RTX_FORMAT (code);
726   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
727     {
728       if (fmt[i] == 'e')
729         scan_rtx (insn, &XEXP (x, i), cl, action, type, 0);
730       else if (fmt[i] == 'E')
731         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
732           scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type, 0);
733     }
734 }
735
736 /* Build def/use chain.  */
737
738 static struct du_chain *
739 build_def_use (basic_block bb)
740 {
741   rtx insn;
742
743   open_chains = closed_chains = NULL;
744
745   for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
746     {
747       if (INSN_P (insn))
748         {
749           int n_ops;
750           rtx note;
751           rtx old_operands[MAX_RECOG_OPERANDS];
752           rtx old_dups[MAX_DUP_OPERANDS];
753           int i, icode;
754           int alt;
755           int predicated;
756
757           /* Process the insn, determining its effect on the def-use
758              chains.  We perform the following steps with the register
759              references in the insn:
760              (1) Any read that overlaps an open chain, but doesn't exactly
761                  match, causes that chain to be closed.  We can't deal
762                  with overlaps yet.
763              (2) Any read outside an operand causes any chain it overlaps
764                  with to be closed, since we can't replace it.
765              (3) Any read inside an operand is added if there's already
766                  an open chain for it.
767              (4) For any REG_DEAD note we find, close open chains that
768                  overlap it.
769              (5) For any write we find, close open chains that overlap it.
770              (6) For any write we find in an operand, make a new chain.
771              (7) For any REG_UNUSED, close any chains we just opened.  */
772
773           icode = recog_memoized (insn);
774           extract_insn (insn);
775           if (! constrain_operands (1))
776             fatal_insn_not_found (insn);
777           preprocess_constraints ();
778           alt = which_alternative;
779           n_ops = recog_data.n_operands;
780
781           /* Simplify the code below by rewriting things to reflect
782              matching constraints.  Also promote OP_OUT to OP_INOUT
783              in predicated instructions.  */
784
785           predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
786           for (i = 0; i < n_ops; ++i)
787             {
788               int matches = recog_op_alt[i][alt].matches;
789               if (matches >= 0)
790                 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
791               if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
792                   || (predicated && recog_data.operand_type[i] == OP_OUT))
793                 recog_data.operand_type[i] = OP_INOUT;
794             }
795
796           /* Step 1: Close chains for which we have overlapping reads.  */
797           for (i = 0; i < n_ops; i++)
798             scan_rtx (insn, recog_data.operand_loc[i],
799                       NO_REGS, terminate_overlapping_read,
800                       recog_data.operand_type[i], 0);
801
802           /* Step 2: Close chains for which we have reads outside operands.
803              We do this by munging all operands into CC0, and closing
804              everything remaining.  */
805
806           for (i = 0; i < n_ops; i++)
807             {
808               old_operands[i] = recog_data.operand[i];
809               /* Don't squash match_operator or match_parallel here, since
810                  we don't know that all of the contained registers are
811                  reachable by proper operands.  */
812               if (recog_data.constraints[i][0] == '\0')
813                 continue;
814               *recog_data.operand_loc[i] = cc0_rtx;
815             }
816           for (i = 0; i < recog_data.n_dups; i++)
817             {
818               old_dups[i] = *recog_data.dup_loc[i];
819               *recog_data.dup_loc[i] = cc0_rtx;
820             }
821
822           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read,
823                     OP_IN, 0);
824
825           for (i = 0; i < recog_data.n_dups; i++)
826             *recog_data.dup_loc[i] = old_dups[i];
827           for (i = 0; i < n_ops; i++)
828             *recog_data.operand_loc[i] = old_operands[i];
829           if (recog_data.n_dups)
830             df_insn_rescan (insn);
831
832           /* Step 2B: Can't rename function call argument registers.  */
833           if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
834             scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
835                       NO_REGS, terminate_all_read, OP_IN, 0);
836
837           /* Step 2C: Can't rename asm operands that were originally
838              hard registers.  */
839           if (asm_noperands (PATTERN (insn)) > 0)
840             for (i = 0; i < n_ops; i++)
841               {
842                 rtx *loc = recog_data.operand_loc[i];
843                 rtx op = *loc;
844
845                 if (REG_P (op)
846                     && REGNO (op) == ORIGINAL_REGNO (op)
847                     && (recog_data.operand_type[i] == OP_IN
848                         || recog_data.operand_type[i] == OP_INOUT))
849                   scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0);
850               }
851
852           /* Step 3: Append to chains for reads inside operands.  */
853           for (i = 0; i < n_ops + recog_data.n_dups; i++)
854             {
855               int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
856               rtx *loc = (i < n_ops
857                           ? recog_data.operand_loc[opn]
858                           : recog_data.dup_loc[i - n_ops]);
859               enum reg_class cl = recog_op_alt[opn][alt].cl;
860               enum op_type type = recog_data.operand_type[opn];
861
862               /* Don't scan match_operand here, since we've no reg class
863                  information to pass down.  Any operands that we could
864                  substitute in will be represented elsewhere.  */
865               if (recog_data.constraints[opn][0] == '\0')
866                 continue;
867
868               if (recog_op_alt[opn][alt].is_address)
869                 scan_rtx_address (insn, loc, cl, mark_read, VOIDmode);
870               else
871                 scan_rtx (insn, loc, cl, mark_read, type, 0);
872             }
873
874           /* Step 3B: Record updates for regs in REG_INC notes, and
875              source regs in REG_FRAME_RELATED_EXPR notes.  */
876           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
877             if (REG_NOTE_KIND (note) == REG_INC
878                 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
879               scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
880                         OP_INOUT, 0);
881
882           /* Step 4: Close chains for registers that die here.  */
883           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
884             if (REG_NOTE_KIND (note) == REG_DEAD)
885               scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
886                         OP_IN, 0);
887
888           /* Step 4B: If this is a call, any chain live at this point
889              requires a caller-saved reg.  */
890           if (CALL_P (insn))
891             {
892               struct du_chain *p;
893               for (p = open_chains; p; p = p->next_chain)
894                 p->need_caller_save_reg = 1;
895             }
896
897           /* Step 5: Close open chains that overlap writes.  Similar to
898              step 2, we hide in-out operands, since we do not want to
899              close these chains.  */
900
901           for (i = 0; i < n_ops; i++)
902             {
903               old_operands[i] = recog_data.operand[i];
904               if (recog_data.operand_type[i] == OP_INOUT)
905                 *recog_data.operand_loc[i] = cc0_rtx;
906             }
907           for (i = 0; i < recog_data.n_dups; i++)
908             {
909               int opn = recog_data.dup_num[i];
910               old_dups[i] = *recog_data.dup_loc[i];
911               if (recog_data.operand_type[opn] == OP_INOUT)
912                 *recog_data.dup_loc[i] = cc0_rtx;
913             }
914
915           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0);
916
917           for (i = 0; i < recog_data.n_dups; i++)
918             *recog_data.dup_loc[i] = old_dups[i];
919           for (i = 0; i < n_ops; i++)
920             *recog_data.operand_loc[i] = old_operands[i];
921
922           /* Step 6: Begin new chains for writes inside operands.  */
923           /* ??? Many targets have output constraints on the SET_DEST
924              of a call insn, which is stupid, since these are certainly
925              ABI defined hard registers.  Don't change calls at all.
926              Similarly take special care for asm statement that originally
927              referenced hard registers.  */
928           if (asm_noperands (PATTERN (insn)) > 0)
929             {
930               for (i = 0; i < n_ops; i++)
931                 if (recog_data.operand_type[i] == OP_OUT)
932                   {
933                     rtx *loc = recog_data.operand_loc[i];
934                     rtx op = *loc;
935                     enum reg_class cl = recog_op_alt[i][alt].cl;
936
937                     if (REG_P (op)
938                         && REGNO (op) == ORIGINAL_REGNO (op))
939                       continue;
940
941                     scan_rtx (insn, loc, cl, mark_write, OP_OUT,
942                               recog_op_alt[i][alt].earlyclobber);
943                   }
944             }
945           else if (!CALL_P (insn))
946             for (i = 0; i < n_ops + recog_data.n_dups; i++)
947               {
948                 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
949                 rtx *loc = (i < n_ops
950                             ? recog_data.operand_loc[opn]
951                             : recog_data.dup_loc[i - n_ops]);
952                 enum reg_class cl = recog_op_alt[opn][alt].cl;
953
954                 if (recog_data.operand_type[opn] == OP_OUT)
955                   scan_rtx (insn, loc, cl, mark_write, OP_OUT,
956                             recog_op_alt[opn][alt].earlyclobber);
957               }
958
959           /* Step 6B: Record destination regs in REG_FRAME_RELATED_EXPR
960              notes for update.  */
961           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
962             if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
963               scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
964                         OP_INOUT, 0);
965
966           /* Step 7: Close chains for registers that were never
967              really used here.  */
968           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
969             if (REG_NOTE_KIND (note) == REG_UNUSED)
970               scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
971                         OP_IN, 0);
972         }
973       if (insn == BB_END (bb))
974         break;
975     }
976
977   /* Since we close every chain when we find a REG_DEAD note, anything that
978      is still open lives past the basic block, so it can't be renamed.  */
979   return closed_chains;
980 }
981
982 /* Dump all def/use chains in CHAINS to DUMP_FILE.  They are
983    printed in reverse order as that's how we build them.  */
984
985 static void
986 dump_def_use_chain (struct du_chain *chains)
987 {
988   while (chains)
989     {
990       struct du_chain *this_du = chains;
991       int r = REGNO (*this_du->loc);
992       int nregs = hard_regno_nregs[r][GET_MODE (*this_du->loc)];
993       fprintf (dump_file, "Register %s (%d):", reg_names[r], nregs);
994       while (this_du)
995         {
996           fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
997                    reg_class_names[this_du->cl]);
998           this_du = this_du->next_use;
999         }
1000       fprintf (dump_file, "\n");
1001       chains = chains->next_chain;
1002     }
1003 }
1004
1005 \f
1006 static bool
1007 gate_handle_regrename (void)
1008 {
1009   return (optimize > 0 && (flag_rename_registers));
1010 }
1011
1012 struct rtl_opt_pass pass_regrename =
1013 {
1014  {
1015   RTL_PASS,
1016   "rnreg",                              /* name */
1017   gate_handle_regrename,                /* gate */
1018   regrename_optimize,                   /* execute */
1019   NULL,                                 /* sub */
1020   NULL,                                 /* next */
1021   0,                                    /* static_pass_number */
1022   TV_RENAME_REGISTERS,                  /* tv_id */
1023   0,                                    /* properties_required */
1024   0,                                    /* properties_provided */
1025   0,                                    /* properties_destroyed */
1026   0,                                    /* todo_flags_start */
1027   TODO_df_finish | TODO_verify_rtl_sharing |
1028   TODO_dump_func                        /* todo_flags_finish */
1029  }
1030 };
1031