PR c++/3478
[official-gcc.git] / gcc / regrename.c
blob56f6a8842b62ddda8fe9729bb8bd3715a357e73b
1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, USA. */
21 #define REG_OK_STRICT
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "insn-config.h"
30 #include "regs.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
33 #include "reload.h"
34 #include "output.h"
35 #include "function.h"
36 #include "recog.h"
37 #include "flags.h"
38 #include "toplev.h"
39 #include "obstack.h"
41 #ifndef REG_MODE_OK_FOR_BASE_P
42 #define REG_MODE_OK_FOR_BASE_P(REGNO, MODE) REG_OK_FOR_BASE_P (REGNO)
43 #endif
45 static const char *const reg_class_names[] = REG_CLASS_NAMES;
47 struct du_chain
49 struct du_chain *next_chain;
50 struct du_chain *next_use;
52 rtx insn;
53 rtx *loc;
54 ENUM_BITFIELD(reg_class) class : 16;
55 unsigned int need_caller_save_reg:1;
56 unsigned int earlyclobber:1;
59 enum scan_actions
61 terminate_all_read,
62 terminate_overlapping_read,
63 terminate_write,
64 terminate_dead,
65 mark_read,
66 mark_write
69 static const char * const scan_actions_name[] =
71 "terminate_all_read",
72 "terminate_overlapping_read",
73 "terminate_write",
74 "terminate_dead",
75 "mark_read",
76 "mark_write"
79 static struct obstack rename_obstack;
81 static void do_replace (struct du_chain *, int);
82 static void scan_rtx_reg (rtx, rtx *, enum reg_class,
83 enum scan_actions, enum op_type, int);
84 static void scan_rtx_address (rtx, rtx *, enum reg_class,
85 enum scan_actions, enum machine_mode);
86 static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
87 enum op_type, int);
88 static struct du_chain *build_def_use (basic_block);
89 static void dump_def_use_chain (struct du_chain *);
90 static void note_sets (rtx, rtx, void *);
91 static void clear_dead_regs (HARD_REG_SET *, enum machine_mode, rtx);
92 static void merge_overlapping_regs (basic_block, HARD_REG_SET *,
93 struct du_chain *);
95 /* Called through note_stores from update_life. Find sets of registers, and
96 record them in *DATA (which is actually a HARD_REG_SET *). */
98 static void
99 note_sets (rtx x, rtx set ATTRIBUTE_UNUSED, void *data)
101 HARD_REG_SET *pset = (HARD_REG_SET *) data;
102 unsigned int regno;
103 int nregs;
104 if (GET_CODE (x) != REG)
105 return;
106 regno = REGNO (x);
107 nregs = HARD_REGNO_NREGS (regno, GET_MODE (x));
109 /* There must not be pseudos at this point. */
110 if (regno + nregs > FIRST_PSEUDO_REGISTER)
111 abort ();
113 while (nregs-- > 0)
114 SET_HARD_REG_BIT (*pset, regno + nregs);
117 /* Clear all registers from *PSET for which a note of kind KIND can be found
118 in the list NOTES. */
120 static void
121 clear_dead_regs (HARD_REG_SET *pset, enum machine_mode kind, rtx notes)
123 rtx note;
124 for (note = notes; note; note = XEXP (note, 1))
125 if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0)))
127 rtx reg = XEXP (note, 0);
128 unsigned int regno = REGNO (reg);
129 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
131 /* There must not be pseudos at this point. */
132 if (regno + nregs > FIRST_PSEUDO_REGISTER)
133 abort ();
135 while (nregs-- > 0)
136 CLEAR_HARD_REG_BIT (*pset, regno + nregs);
140 /* For a def-use chain CHAIN in basic block B, find which registers overlap
141 its lifetime and set the corresponding bits in *PSET. */
143 static void
144 merge_overlapping_regs (basic_block b, HARD_REG_SET *pset,
145 struct du_chain *chain)
147 struct du_chain *t = chain;
148 rtx insn;
149 HARD_REG_SET live;
151 REG_SET_TO_HARD_REG_SET (live, b->global_live_at_start);
152 insn = BB_HEAD (b);
153 while (t)
155 /* Search forward until the next reference to the register to be
156 renamed. */
157 while (insn != t->insn)
159 if (INSN_P (insn))
161 clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn));
162 note_stores (PATTERN (insn), note_sets, (void *) &live);
163 /* Only record currently live regs if we are inside the
164 reg's live range. */
165 if (t != chain)
166 IOR_HARD_REG_SET (*pset, live);
167 clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn));
169 insn = NEXT_INSN (insn);
172 IOR_HARD_REG_SET (*pset, live);
174 /* For the last reference, also merge in all registers set in the
175 same insn.
176 @@@ We only have take earlyclobbered sets into account. */
177 if (! t->next_use)
178 note_stores (PATTERN (insn), note_sets, (void *) pset);
180 t = t->next_use;
184 /* Perform register renaming on the current function. */
186 void
187 regrename_optimize (void)
189 int tick[FIRST_PSEUDO_REGISTER];
190 int this_tick = 0;
191 basic_block bb;
192 char *first_obj;
194 memset (tick, 0, sizeof tick);
196 gcc_obstack_init (&rename_obstack);
197 first_obj = obstack_alloc (&rename_obstack, 0);
199 FOR_EACH_BB (bb)
201 struct du_chain *all_chains = 0;
202 HARD_REG_SET unavailable;
203 HARD_REG_SET regs_seen;
205 CLEAR_HARD_REG_SET (unavailable);
207 if (rtl_dump_file)
208 fprintf (rtl_dump_file, "\nBasic block %d:\n", bb->index);
210 all_chains = build_def_use (bb);
212 if (rtl_dump_file)
213 dump_def_use_chain (all_chains);
215 CLEAR_HARD_REG_SET (unavailable);
216 /* Don't clobber traceback for noreturn functions. */
217 if (frame_pointer_needed)
219 int i;
221 for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;)
222 SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM + i);
224 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
225 for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;)
226 SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM + i);
227 #endif
230 CLEAR_HARD_REG_SET (regs_seen);
231 while (all_chains)
233 int new_reg, best_new_reg;
234 int n_uses;
235 struct du_chain *this = all_chains;
236 struct du_chain *tmp, *last;
237 HARD_REG_SET this_unavailable;
238 int reg = REGNO (*this->loc);
239 int i;
241 all_chains = this->next_chain;
243 best_new_reg = reg;
245 #if 0 /* This just disables optimization opportunities. */
246 /* Only rename once we've seen the reg more than once. */
247 if (! TEST_HARD_REG_BIT (regs_seen, reg))
249 SET_HARD_REG_BIT (regs_seen, reg);
250 continue;
252 #endif
254 if (fixed_regs[reg] || global_regs[reg]
255 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
256 || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
257 #else
258 || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
259 #endif
261 continue;
263 COPY_HARD_REG_SET (this_unavailable, unavailable);
265 /* Find last entry on chain (which has the need_caller_save bit),
266 count number of uses, and narrow the set of registers we can
267 use for renaming. */
268 n_uses = 0;
269 for (last = this; last->next_use; last = last->next_use)
271 n_uses++;
272 IOR_COMPL_HARD_REG_SET (this_unavailable,
273 reg_class_contents[last->class]);
275 if (n_uses < 1)
276 continue;
278 IOR_COMPL_HARD_REG_SET (this_unavailable,
279 reg_class_contents[last->class]);
281 if (this->need_caller_save_reg)
282 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
284 merge_overlapping_regs (bb, &this_unavailable, this);
286 /* Now potential_regs is a reasonable approximation, let's
287 have a closer look at each register still in there. */
288 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
290 int nregs = HARD_REGNO_NREGS (new_reg, GET_MODE (*this->loc));
292 for (i = nregs - 1; i >= 0; --i)
293 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
294 || fixed_regs[new_reg + i]
295 || global_regs[new_reg + i]
296 /* Can't use regs which aren't saved by the prologue. */
297 || (! regs_ever_live[new_reg + i]
298 && ! call_used_regs[new_reg + i])
299 #ifdef LEAF_REGISTERS
300 /* We can't use a non-leaf register if we're in a
301 leaf function. */
302 || (current_function_is_leaf
303 && !LEAF_REGISTERS[new_reg + i])
304 #endif
305 #ifdef HARD_REGNO_RENAME_OK
306 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
307 #endif
309 break;
310 if (i >= 0)
311 continue;
313 /* See whether it accepts all modes that occur in
314 definition and uses. */
315 for (tmp = this; tmp; tmp = tmp->next_use)
316 if (! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
317 || (tmp->need_caller_save_reg
318 && ! (HARD_REGNO_CALL_PART_CLOBBERED
319 (reg, GET_MODE (*tmp->loc)))
320 && (HARD_REGNO_CALL_PART_CLOBBERED
321 (new_reg, GET_MODE (*tmp->loc)))))
322 break;
323 if (! tmp)
325 if (tick[best_new_reg] > tick[new_reg])
326 best_new_reg = new_reg;
330 if (rtl_dump_file)
332 fprintf (rtl_dump_file, "Register %s in insn %d",
333 reg_names[reg], INSN_UID (last->insn));
334 if (last->need_caller_save_reg)
335 fprintf (rtl_dump_file, " crosses a call");
338 if (best_new_reg == reg)
340 tick[reg] = ++this_tick;
341 if (rtl_dump_file)
342 fprintf (rtl_dump_file, "; no available better choice\n");
343 continue;
346 do_replace (this, best_new_reg);
347 tick[best_new_reg] = ++this_tick;
349 if (rtl_dump_file)
350 fprintf (rtl_dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
353 obstack_free (&rename_obstack, first_obj);
356 obstack_free (&rename_obstack, NULL);
358 if (rtl_dump_file)
359 fputc ('\n', rtl_dump_file);
361 count_or_remove_death_notes (NULL, 1);
362 update_life_info (NULL, UPDATE_LIFE_LOCAL,
363 PROP_REG_INFO | PROP_DEATH_NOTES);
366 static void
367 do_replace (struct du_chain *chain, int reg)
369 while (chain)
371 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
372 struct reg_attrs * attr = REG_ATTRS (*chain->loc);
374 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
375 if (regno >= FIRST_PSEUDO_REGISTER)
376 ORIGINAL_REGNO (*chain->loc) = regno;
377 REG_ATTRS (*chain->loc) = attr;
378 chain = chain->next_use;
383 static struct du_chain *open_chains;
384 static struct du_chain *closed_chains;
386 static void
387 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class class,
388 enum scan_actions action, enum op_type type, int earlyclobber)
390 struct du_chain **p;
391 rtx x = *loc;
392 enum machine_mode mode = GET_MODE (x);
393 int this_regno = REGNO (x);
394 int this_nregs = HARD_REGNO_NREGS (this_regno, mode);
396 if (action == mark_write)
398 if (type == OP_OUT)
400 struct du_chain *this
401 = obstack_alloc (&rename_obstack, sizeof (struct du_chain));
402 this->next_use = 0;
403 this->next_chain = open_chains;
404 this->loc = loc;
405 this->insn = insn;
406 this->class = class;
407 this->need_caller_save_reg = 0;
408 this->earlyclobber = earlyclobber;
409 open_chains = this;
411 return;
414 if ((type == OP_OUT && action != terminate_write)
415 || (type != OP_OUT && action == terminate_write))
416 return;
418 for (p = &open_chains; *p;)
420 struct du_chain *this = *p;
422 /* Check if the chain has been terminated if it has then skip to
423 the next chain.
425 This can happen when we've already appended the location to
426 the chain in Step 3, but are trying to hide in-out operands
427 from terminate_write in Step 5. */
429 if (*this->loc == cc0_rtx)
430 p = &this->next_chain;
431 else
433 int regno = REGNO (*this->loc);
434 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (*this->loc));
435 int exact_match = (regno == this_regno && nregs == this_nregs);
437 if (regno + nregs <= this_regno
438 || this_regno + this_nregs <= regno)
440 p = &this->next_chain;
441 continue;
444 if (action == mark_read)
446 if (! exact_match)
447 abort ();
449 /* ??? Class NO_REGS can happen if the md file makes use of
450 EXTRA_CONSTRAINTS to match registers. Which is arguably
451 wrong, but there we are. Since we know not what this may
452 be replaced with, terminate the chain. */
453 if (class != NO_REGS)
455 this = obstack_alloc (&rename_obstack, sizeof (struct du_chain));
456 this->next_use = 0;
457 this->next_chain = (*p)->next_chain;
458 this->loc = loc;
459 this->insn = insn;
460 this->class = class;
461 this->need_caller_save_reg = 0;
462 while (*p)
463 p = &(*p)->next_use;
464 *p = this;
465 return;
469 if (action != terminate_overlapping_read || ! exact_match)
471 struct du_chain *next = this->next_chain;
473 /* Whether the terminated chain can be used for renaming
474 depends on the action and this being an exact match.
475 In either case, we remove this element from open_chains. */
477 if ((action == terminate_dead || action == terminate_write)
478 && exact_match)
480 this->next_chain = closed_chains;
481 closed_chains = this;
482 if (rtl_dump_file)
483 fprintf (rtl_dump_file,
484 "Closing chain %s at insn %d (%s)\n",
485 reg_names[REGNO (*this->loc)], INSN_UID (insn),
486 scan_actions_name[(int) action]);
488 else
490 if (rtl_dump_file)
491 fprintf (rtl_dump_file,
492 "Discarding chain %s at insn %d (%s)\n",
493 reg_names[REGNO (*this->loc)], INSN_UID (insn),
494 scan_actions_name[(int) action]);
496 *p = next;
498 else
499 p = &this->next_chain;
504 /* Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
505 BASE_REG_CLASS depending on how the register is being considered. */
507 static void
508 scan_rtx_address (rtx insn, rtx *loc, enum reg_class class,
509 enum scan_actions action, enum machine_mode mode)
511 rtx x = *loc;
512 RTX_CODE code = GET_CODE (x);
513 const char *fmt;
514 int i, j;
516 if (action == mark_write)
517 return;
519 switch (code)
521 case PLUS:
523 rtx orig_op0 = XEXP (x, 0);
524 rtx orig_op1 = XEXP (x, 1);
525 RTX_CODE code0 = GET_CODE (orig_op0);
526 RTX_CODE code1 = GET_CODE (orig_op1);
527 rtx op0 = orig_op0;
528 rtx op1 = orig_op1;
529 rtx *locI = NULL;
530 rtx *locB = NULL;
532 if (GET_CODE (op0) == SUBREG)
534 op0 = SUBREG_REG (op0);
535 code0 = GET_CODE (op0);
538 if (GET_CODE (op1) == SUBREG)
540 op1 = SUBREG_REG (op1);
541 code1 = GET_CODE (op1);
544 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
545 || code0 == ZERO_EXTEND || code1 == MEM)
547 locI = &XEXP (x, 0);
548 locB = &XEXP (x, 1);
550 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
551 || code1 == ZERO_EXTEND || code0 == MEM)
553 locI = &XEXP (x, 1);
554 locB = &XEXP (x, 0);
556 else if (code0 == CONST_INT || code0 == CONST
557 || code0 == SYMBOL_REF || code0 == LABEL_REF)
558 locB = &XEXP (x, 1);
559 else if (code1 == CONST_INT || code1 == CONST
560 || code1 == SYMBOL_REF || code1 == LABEL_REF)
561 locB = &XEXP (x, 0);
562 else if (code0 == REG && code1 == REG)
564 int index_op;
566 if (REG_OK_FOR_INDEX_P (op0)
567 && REG_MODE_OK_FOR_BASE_P (op1, mode))
568 index_op = 0;
569 else if (REG_OK_FOR_INDEX_P (op1)
570 && REG_MODE_OK_FOR_BASE_P (op0, mode))
571 index_op = 1;
572 else if (REG_MODE_OK_FOR_BASE_P (op1, mode))
573 index_op = 0;
574 else if (REG_MODE_OK_FOR_BASE_P (op0, mode))
575 index_op = 1;
576 else if (REG_OK_FOR_INDEX_P (op1))
577 index_op = 1;
578 else
579 index_op = 0;
581 locI = &XEXP (x, index_op);
582 locB = &XEXP (x, !index_op);
584 else if (code0 == REG)
586 locI = &XEXP (x, 0);
587 locB = &XEXP (x, 1);
589 else if (code1 == REG)
591 locI = &XEXP (x, 1);
592 locB = &XEXP (x, 0);
595 if (locI)
596 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
597 if (locB)
598 scan_rtx_address (insn, locB, MODE_BASE_REG_CLASS (mode), action, mode);
599 return;
602 case POST_INC:
603 case POST_DEC:
604 case POST_MODIFY:
605 case PRE_INC:
606 case PRE_DEC:
607 case PRE_MODIFY:
608 #ifndef AUTO_INC_DEC
609 /* If the target doesn't claim to handle autoinc, this must be
610 something special, like a stack push. Kill this chain. */
611 action = terminate_all_read;
612 #endif
613 break;
615 case MEM:
616 scan_rtx_address (insn, &XEXP (x, 0),
617 MODE_BASE_REG_CLASS (GET_MODE (x)), action,
618 GET_MODE (x));
619 return;
621 case REG:
622 scan_rtx_reg (insn, loc, class, action, OP_IN, 0);
623 return;
625 default:
626 break;
629 fmt = GET_RTX_FORMAT (code);
630 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
632 if (fmt[i] == 'e')
633 scan_rtx_address (insn, &XEXP (x, i), class, action, mode);
634 else if (fmt[i] == 'E')
635 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
636 scan_rtx_address (insn, &XVECEXP (x, i, j), class, action, mode);
640 static void
641 scan_rtx (rtx insn, rtx *loc, enum reg_class class,
642 enum scan_actions action, enum op_type type, int earlyclobber)
644 const char *fmt;
645 rtx x = *loc;
646 enum rtx_code code = GET_CODE (x);
647 int i, j;
649 code = GET_CODE (x);
650 switch (code)
652 case CONST:
653 case CONST_INT:
654 case CONST_DOUBLE:
655 case CONST_VECTOR:
656 case SYMBOL_REF:
657 case LABEL_REF:
658 case CC0:
659 case PC:
660 return;
662 case REG:
663 scan_rtx_reg (insn, loc, class, action, type, earlyclobber);
664 return;
666 case MEM:
667 scan_rtx_address (insn, &XEXP (x, 0),
668 MODE_BASE_REG_CLASS (GET_MODE (x)), action,
669 GET_MODE (x));
670 return;
672 case SET:
673 scan_rtx (insn, &SET_SRC (x), class, action, OP_IN, 0);
674 scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 0);
675 return;
677 case STRICT_LOW_PART:
678 scan_rtx (insn, &XEXP (x, 0), class, action, OP_INOUT, earlyclobber);
679 return;
681 case ZERO_EXTRACT:
682 case SIGN_EXTRACT:
683 scan_rtx (insn, &XEXP (x, 0), class, action,
684 type == OP_IN ? OP_IN : OP_INOUT, earlyclobber);
685 scan_rtx (insn, &XEXP (x, 1), class, action, OP_IN, 0);
686 scan_rtx (insn, &XEXP (x, 2), class, action, OP_IN, 0);
687 return;
689 case POST_INC:
690 case PRE_INC:
691 case POST_DEC:
692 case PRE_DEC:
693 case POST_MODIFY:
694 case PRE_MODIFY:
695 /* Should only happen inside MEM. */
696 abort ();
698 case CLOBBER:
699 scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 1);
700 return;
702 case EXPR_LIST:
703 scan_rtx (insn, &XEXP (x, 0), class, action, type, 0);
704 if (XEXP (x, 1))
705 scan_rtx (insn, &XEXP (x, 1), class, action, type, 0);
706 return;
708 default:
709 break;
712 fmt = GET_RTX_FORMAT (code);
713 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
715 if (fmt[i] == 'e')
716 scan_rtx (insn, &XEXP (x, i), class, action, type, 0);
717 else if (fmt[i] == 'E')
718 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
719 scan_rtx (insn, &XVECEXP (x, i, j), class, action, type, 0);
723 /* Build def/use chain. */
725 static struct du_chain *
726 build_def_use (basic_block bb)
728 rtx insn;
730 open_chains = closed_chains = NULL;
732 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
734 if (INSN_P (insn))
736 int n_ops;
737 rtx note;
738 rtx old_operands[MAX_RECOG_OPERANDS];
739 rtx old_dups[MAX_DUP_OPERANDS];
740 int i, icode;
741 int alt;
742 int predicated;
744 /* Process the insn, determining its effect on the def-use
745 chains. We perform the following steps with the register
746 references in the insn:
747 (1) Any read that overlaps an open chain, but doesn't exactly
748 match, causes that chain to be closed. We can't deal
749 with overlaps yet.
750 (2) Any read outside an operand causes any chain it overlaps
751 with to be closed, since we can't replace it.
752 (3) Any read inside an operand is added if there's already
753 an open chain for it.
754 (4) For any REG_DEAD note we find, close open chains that
755 overlap it.
756 (5) For any write we find, close open chains that overlap it.
757 (6) For any write we find in an operand, make a new chain.
758 (7) For any REG_UNUSED, close any chains we just opened. */
760 icode = recog_memoized (insn);
761 extract_insn (insn);
762 if (! constrain_operands (1))
763 fatal_insn_not_found (insn);
764 preprocess_constraints ();
765 alt = which_alternative;
766 n_ops = recog_data.n_operands;
768 /* Simplify the code below by rewriting things to reflect
769 matching constraints. Also promote OP_OUT to OP_INOUT
770 in predicated instructions. */
772 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
773 for (i = 0; i < n_ops; ++i)
775 int matches = recog_op_alt[i][alt].matches;
776 if (matches >= 0)
777 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class;
778 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
779 || (predicated && recog_data.operand_type[i] == OP_OUT))
780 recog_data.operand_type[i] = OP_INOUT;
783 /* Step 1: Close chains for which we have overlapping reads. */
784 for (i = 0; i < n_ops; i++)
785 scan_rtx (insn, recog_data.operand_loc[i],
786 NO_REGS, terminate_overlapping_read,
787 recog_data.operand_type[i], 0);
789 /* Step 2: Close chains for which we have reads outside operands.
790 We do this by munging all operands into CC0, and closing
791 everything remaining. */
793 for (i = 0; i < n_ops; i++)
795 old_operands[i] = recog_data.operand[i];
796 /* Don't squash match_operator or match_parallel here, since
797 we don't know that all of the contained registers are
798 reachable by proper operands. */
799 if (recog_data.constraints[i][0] == '\0')
800 continue;
801 *recog_data.operand_loc[i] = cc0_rtx;
803 for (i = 0; i < recog_data.n_dups; i++)
805 int dup_num = recog_data.dup_num[i];
807 old_dups[i] = *recog_data.dup_loc[i];
808 *recog_data.dup_loc[i] = cc0_rtx;
810 /* For match_dup of match_operator or match_parallel, share
811 them, so that we don't miss changes in the dup. */
812 if (icode >= 0
813 && insn_data[icode].operand[dup_num].eliminable == 0)
814 old_dups[i] = recog_data.operand[dup_num];
817 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read,
818 OP_IN, 0);
820 for (i = 0; i < recog_data.n_dups; i++)
821 *recog_data.dup_loc[i] = old_dups[i];
822 for (i = 0; i < n_ops; i++)
823 *recog_data.operand_loc[i] = old_operands[i];
825 /* Step 2B: Can't rename function call argument registers. */
826 if (GET_CODE (insn) == CALL_INSN && CALL_INSN_FUNCTION_USAGE (insn))
827 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
828 NO_REGS, terminate_all_read, OP_IN, 0);
830 /* Step 2C: Can't rename asm operands that were originally
831 hard registers. */
832 if (asm_noperands (PATTERN (insn)) > 0)
833 for (i = 0; i < n_ops; i++)
835 rtx *loc = recog_data.operand_loc[i];
836 rtx op = *loc;
838 if (GET_CODE (op) == REG
839 && REGNO (op) == ORIGINAL_REGNO (op)
840 && (recog_data.operand_type[i] == OP_IN
841 || recog_data.operand_type[i] == OP_INOUT))
842 scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0);
845 /* Step 3: Append to chains for reads inside operands. */
846 for (i = 0; i < n_ops + recog_data.n_dups; i++)
848 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
849 rtx *loc = (i < n_ops
850 ? recog_data.operand_loc[opn]
851 : recog_data.dup_loc[i - n_ops]);
852 enum reg_class class = recog_op_alt[opn][alt].class;
853 enum op_type type = recog_data.operand_type[opn];
855 /* Don't scan match_operand here, since we've no reg class
856 information to pass down. Any operands that we could
857 substitute in will be represented elsewhere. */
858 if (recog_data.constraints[opn][0] == '\0')
859 continue;
861 if (recog_op_alt[opn][alt].is_address)
862 scan_rtx_address (insn, loc, class, mark_read, VOIDmode);
863 else
864 scan_rtx (insn, loc, class, mark_read, type, 0);
867 /* Step 4: Close chains for registers that die here.
868 Also record updates for REG_INC notes. */
869 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
871 if (REG_NOTE_KIND (note) == REG_DEAD)
872 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
873 OP_IN, 0);
874 else if (REG_NOTE_KIND (note) == REG_INC)
875 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
876 OP_INOUT, 0);
879 /* Step 4B: If this is a call, any chain live at this point
880 requires a caller-saved reg. */
881 if (GET_CODE (insn) == CALL_INSN)
883 struct du_chain *p;
884 for (p = open_chains; p; p = p->next_chain)
885 p->need_caller_save_reg = 1;
888 /* Step 5: Close open chains that overlap writes. Similar to
889 step 2, we hide in-out operands, since we do not want to
890 close these chains. */
892 for (i = 0; i < n_ops; i++)
894 old_operands[i] = recog_data.operand[i];
895 if (recog_data.operand_type[i] == OP_INOUT)
896 *recog_data.operand_loc[i] = cc0_rtx;
898 for (i = 0; i < recog_data.n_dups; i++)
900 int opn = recog_data.dup_num[i];
901 old_dups[i] = *recog_data.dup_loc[i];
902 if (recog_data.operand_type[opn] == OP_INOUT)
903 *recog_data.dup_loc[i] = cc0_rtx;
906 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0);
908 for (i = 0; i < recog_data.n_dups; i++)
909 *recog_data.dup_loc[i] = old_dups[i];
910 for (i = 0; i < n_ops; i++)
911 *recog_data.operand_loc[i] = old_operands[i];
913 /* Step 6: Begin new chains for writes inside operands. */
914 /* ??? Many targets have output constraints on the SET_DEST
915 of a call insn, which is stupid, since these are certainly
916 ABI defined hard registers. Don't change calls at all.
917 Similarly take special care for asm statement that originally
918 referenced hard registers. */
919 if (asm_noperands (PATTERN (insn)) > 0)
921 for (i = 0; i < n_ops; i++)
922 if (recog_data.operand_type[i] == OP_OUT)
924 rtx *loc = recog_data.operand_loc[i];
925 rtx op = *loc;
926 enum reg_class class = recog_op_alt[i][alt].class;
928 if (GET_CODE (op) == REG
929 && REGNO (op) == ORIGINAL_REGNO (op))
930 continue;
932 scan_rtx (insn, loc, class, mark_write, OP_OUT,
933 recog_op_alt[i][alt].earlyclobber);
936 else if (GET_CODE (insn) != CALL_INSN)
937 for (i = 0; i < n_ops + recog_data.n_dups; i++)
939 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
940 rtx *loc = (i < n_ops
941 ? recog_data.operand_loc[opn]
942 : recog_data.dup_loc[i - n_ops]);
943 enum reg_class class = recog_op_alt[opn][alt].class;
945 if (recog_data.operand_type[opn] == OP_OUT)
946 scan_rtx (insn, loc, class, mark_write, OP_OUT,
947 recog_op_alt[opn][alt].earlyclobber);
950 /* Step 7: Close chains for registers that were never
951 really used here. */
952 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
953 if (REG_NOTE_KIND (note) == REG_UNUSED)
954 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
955 OP_IN, 0);
957 if (insn == BB_END (bb))
958 break;
961 /* Since we close every chain when we find a REG_DEAD note, anything that
962 is still open lives past the basic block, so it can't be renamed. */
963 return closed_chains;
966 /* Dump all def/use chains in CHAINS to RTL_DUMP_FILE. They are
967 printed in reverse order as that's how we build them. */
969 static void
970 dump_def_use_chain (struct du_chain *chains)
972 while (chains)
974 struct du_chain *this = chains;
975 int r = REGNO (*this->loc);
976 int nregs = HARD_REGNO_NREGS (r, GET_MODE (*this->loc));
977 fprintf (rtl_dump_file, "Register %s (%d):", reg_names[r], nregs);
978 while (this)
980 fprintf (rtl_dump_file, " %d [%s]", INSN_UID (this->insn),
981 reg_class_names[this->class]);
982 this = this->next_use;
984 fprintf (rtl_dump_file, "\n");
985 chains = chains->next_chain;
989 /* The following code does forward propagation of hard register copies.
990 The object is to eliminate as many dependencies as possible, so that
991 we have the most scheduling freedom. As a side effect, we also clean
992 up some silly register allocation decisions made by reload. This
993 code may be obsoleted by a new register allocator. */
995 /* For each register, we have a list of registers that contain the same
996 value. The OLDEST_REGNO field points to the head of the list, and
997 the NEXT_REGNO field runs through the list. The MODE field indicates
998 what mode the data is known to be in; this field is VOIDmode when the
999 register is not known to contain valid data. */
1001 struct value_data_entry
1003 enum machine_mode mode;
1004 unsigned int oldest_regno;
1005 unsigned int next_regno;
1008 struct value_data
1010 struct value_data_entry e[FIRST_PSEUDO_REGISTER];
1011 unsigned int max_value_regs;
1014 static void kill_value_regno (unsigned, struct value_data *);
1015 static void kill_value (rtx, struct value_data *);
1016 static void set_value_regno (unsigned, enum machine_mode, struct value_data *);
1017 static void init_value_data (struct value_data *);
1018 static void kill_clobbered_value (rtx, rtx, void *);
1019 static void kill_set_value (rtx, rtx, void *);
1020 static int kill_autoinc_value (rtx *, void *);
1021 static void copy_value (rtx, rtx, struct value_data *);
1022 static bool mode_change_ok (enum machine_mode, enum machine_mode,
1023 unsigned int);
1024 static rtx maybe_mode_change (enum machine_mode, enum machine_mode,
1025 enum machine_mode, unsigned int, unsigned int);
1026 static rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *);
1027 static bool replace_oldest_value_reg (rtx *, enum reg_class, rtx,
1028 struct value_data *);
1029 static bool replace_oldest_value_addr (rtx *, enum reg_class,
1030 enum machine_mode, rtx,
1031 struct value_data *);
1032 static bool replace_oldest_value_mem (rtx, rtx, struct value_data *);
1033 static bool copyprop_hardreg_forward_1 (basic_block, struct value_data *);
1034 extern void debug_value_data (struct value_data *);
1035 #ifdef ENABLE_CHECKING
1036 static void validate_value_data (struct value_data *);
1037 #endif
1039 /* Kill register REGNO. This involves removing it from any value lists,
1040 and resetting the value mode to VOIDmode. */
1042 static void
1043 kill_value_regno (unsigned int regno, struct value_data *vd)
1045 unsigned int i, next;
1047 if (vd->e[regno].oldest_regno != regno)
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;
1055 else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM)
1057 for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno)
1058 vd->e[i].oldest_regno = next;
1061 vd->e[regno].mode = VOIDmode;
1062 vd->e[regno].oldest_regno = regno;
1063 vd->e[regno].next_regno = INVALID_REGNUM;
1065 #ifdef ENABLE_CHECKING
1066 validate_value_data (vd);
1067 #endif
1070 /* Kill X. This is a convenience function for kill_value_regno
1071 so that we mind the mode the register is in. */
1073 static void
1074 kill_value (rtx x, struct value_data *vd)
1076 /* SUBREGS are supposed to have been eliminated by now. But some
1077 ports, e.g. i386 sse, use them to smuggle vector type information
1078 through to instruction selection. Each such SUBREG should simplify,
1079 so if we get a NULL we've done something wrong elsewhere. */
1081 if (GET_CODE (x) == SUBREG)
1082 x = simplify_subreg (GET_MODE (x), SUBREG_REG (x),
1083 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
1084 if (REG_P (x))
1086 unsigned int regno = REGNO (x);
1087 unsigned int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
1088 unsigned int i, j;
1090 /* Kill the value we're told to kill. */
1091 for (i = 0; i < n; ++i)
1092 kill_value_regno (regno + i, vd);
1094 /* Kill everything that overlapped what we're told to kill. */
1095 if (regno < vd->max_value_regs)
1096 j = 0;
1097 else
1098 j = regno - vd->max_value_regs;
1099 for (; j < regno; ++j)
1101 if (vd->e[j].mode == VOIDmode)
1102 continue;
1103 n = HARD_REGNO_NREGS (j, vd->e[j].mode);
1104 if (j + n > regno)
1105 for (i = 0; i < n; ++i)
1106 kill_value_regno (j + i, vd);
1111 /* Remember that REGNO is valid in MODE. */
1113 static void
1114 set_value_regno (unsigned int regno, enum machine_mode mode,
1115 struct value_data *vd)
1117 unsigned int nregs;
1119 vd->e[regno].mode = mode;
1121 nregs = HARD_REGNO_NREGS (regno, mode);
1122 if (nregs > vd->max_value_regs)
1123 vd->max_value_regs = nregs;
1126 /* Initialize VD such that there are no known relationships between regs. */
1128 static void
1129 init_value_data (struct value_data *vd)
1131 int i;
1132 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1134 vd->e[i].mode = VOIDmode;
1135 vd->e[i].oldest_regno = i;
1136 vd->e[i].next_regno = INVALID_REGNUM;
1138 vd->max_value_regs = 0;
1141 /* Called through note_stores. If X is clobbered, kill its value. */
1143 static void
1144 kill_clobbered_value (rtx x, rtx set, void *data)
1146 struct value_data *vd = data;
1147 if (GET_CODE (set) == CLOBBER)
1148 kill_value (x, vd);
1151 /* Called through note_stores. If X is set, not clobbered, kill its
1152 current value and install it as the root of its own value list. */
1154 static void
1155 kill_set_value (rtx x, rtx set, void *data)
1157 struct value_data *vd = data;
1158 if (GET_CODE (set) != CLOBBER)
1160 kill_value (x, vd);
1161 if (REG_P (x))
1162 set_value_regno (REGNO (x), GET_MODE (x), vd);
1166 /* Called through for_each_rtx. Kill any register used as the base of an
1167 auto-increment expression, and install that register as the root of its
1168 own value list. */
1170 static int
1171 kill_autoinc_value (rtx *px, void *data)
1173 rtx x = *px;
1174 struct value_data *vd = data;
1176 if (GET_RTX_CLASS (GET_CODE (x)) == 'a')
1178 x = XEXP (x, 0);
1179 kill_value (x, vd);
1180 set_value_regno (REGNO (x), Pmode, vd);
1181 return -1;
1184 return 0;
1187 /* Assert that SRC has been copied to DEST. Adjust the data structures
1188 to reflect that SRC contains an older copy of the shared value. */
1190 static void
1191 copy_value (rtx dest, rtx src, struct value_data *vd)
1193 unsigned int dr = REGNO (dest);
1194 unsigned int sr = REGNO (src);
1195 unsigned int dn, sn;
1196 unsigned int i;
1198 /* ??? At present, it's possible to see noop sets. It'd be nice if
1199 this were cleaned up beforehand... */
1200 if (sr == dr)
1201 return;
1203 /* Do not propagate copies to the stack pointer, as that can leave
1204 memory accesses with no scheduling dependency on the stack update. */
1205 if (dr == STACK_POINTER_REGNUM)
1206 return;
1208 /* Likewise with the frame pointer, if we're using one. */
1209 if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM)
1210 return;
1212 /* If SRC and DEST overlap, don't record anything. */
1213 dn = HARD_REGNO_NREGS (dr, GET_MODE (dest));
1214 sn = HARD_REGNO_NREGS (sr, GET_MODE (dest));
1215 if ((dr > sr && dr < sr + sn)
1216 || (sr > dr && sr < dr + dn))
1217 return;
1219 /* If SRC had no assigned mode (i.e. we didn't know it was live)
1220 assign it now and assume the value came from an input argument
1221 or somesuch. */
1222 if (vd->e[sr].mode == VOIDmode)
1223 set_value_regno (sr, vd->e[dr].mode, vd);
1225 /* If we are narrowing the input to a smaller number of hard regs,
1226 and it is in big endian, we are really extracting a high part.
1227 Since we generally associate a low part of a value with the value itself,
1228 we must not do the same for the high part.
1229 Note we can still get low parts for the same mode combination through
1230 a two-step copy involving differently sized hard regs.
1231 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
1232 (set (reg:DI r0) (reg:DI fr0))
1233 (set (reg:SI fr2) (reg:SI r0))
1234 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
1235 (set (reg:SI fr2) (reg:SI fr0))
1236 loads the high part of (reg:DI fr0) into fr2.
1238 We can't properly represent the latter case in our tables, so don't
1239 record anything then. */
1240 else if (sn < (unsigned int) HARD_REGNO_NREGS (sr, vd->e[sr].mode)
1241 && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD
1242 ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
1243 return;
1245 /* If SRC had been assigned a mode narrower than the copy, we can't
1246 link DEST into the chain, because not all of the pieces of the
1247 copy came from oldest_regno. */
1248 else if (sn > (unsigned int) HARD_REGNO_NREGS (sr, vd->e[sr].mode))
1249 return;
1251 /* Link DR at the end of the value chain used by SR. */
1253 vd->e[dr].oldest_regno = vd->e[sr].oldest_regno;
1255 for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno)
1256 continue;
1257 vd->e[i].next_regno = dr;
1259 #ifdef ENABLE_CHECKING
1260 validate_value_data (vd);
1261 #endif
1264 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
1266 static bool
1267 mode_change_ok (enum machine_mode orig_mode, enum machine_mode new_mode,
1268 unsigned int regno ATTRIBUTE_UNUSED)
1270 if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode))
1271 return false;
1273 #ifdef CANNOT_CHANGE_MODE_CLASS
1274 return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode);
1275 #endif
1277 return true;
1280 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
1281 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
1282 in NEW_MODE.
1283 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
1285 static rtx
1286 maybe_mode_change (enum machine_mode orig_mode, enum machine_mode copy_mode,
1287 enum machine_mode new_mode, unsigned int regno,
1288 unsigned int copy_regno ATTRIBUTE_UNUSED)
1290 if (orig_mode == new_mode)
1291 return gen_rtx_raw_REG (new_mode, regno);
1292 else if (mode_change_ok (orig_mode, new_mode, regno))
1294 int copy_nregs = HARD_REGNO_NREGS (copy_regno, copy_mode);
1295 int use_nregs = HARD_REGNO_NREGS (copy_regno, new_mode);
1296 int copy_offset
1297 = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs);
1298 int offset
1299 = GET_MODE_SIZE (orig_mode) - GET_MODE_SIZE (new_mode) - copy_offset;
1300 int byteoffset = offset % UNITS_PER_WORD;
1301 int wordoffset = offset - byteoffset;
1303 offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0)
1304 + (BYTES_BIG_ENDIAN ? byteoffset : 0));
1305 return gen_rtx_raw_REG (new_mode,
1306 regno + subreg_regno_offset (regno, orig_mode,
1307 offset,
1308 new_mode));
1310 return NULL_RTX;
1313 /* Find the oldest copy of the value contained in REGNO that is in
1314 register class CLASS and has mode MODE. If found, return an rtx
1315 of that oldest register, otherwise return NULL. */
1317 static rtx
1318 find_oldest_value_reg (enum reg_class class, rtx reg, struct value_data *vd)
1320 unsigned int regno = REGNO (reg);
1321 enum machine_mode mode = GET_MODE (reg);
1322 unsigned int i;
1324 /* If we are accessing REG in some mode other that what we set it in,
1325 make sure that the replacement is valid. In particular, consider
1326 (set (reg:DI r11) (...))
1327 (set (reg:SI r9) (reg:SI r11))
1328 (set (reg:SI r10) (...))
1329 (set (...) (reg:DI r9))
1330 Replacing r9 with r11 is invalid. */
1331 if (mode != vd->e[regno].mode)
1333 if (HARD_REGNO_NREGS (regno, mode)
1334 > HARD_REGNO_NREGS (regno, vd->e[regno].mode))
1335 return NULL_RTX;
1338 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno)
1340 enum machine_mode oldmode = vd->e[i].mode;
1341 rtx new;
1343 if (TEST_HARD_REG_BIT (reg_class_contents[class], i)
1344 && (new = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i,
1345 regno)))
1347 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg);
1348 REG_ATTRS (new) = REG_ATTRS (reg);
1349 return new;
1353 return NULL_RTX;
1356 /* If possible, replace the register at *LOC with the oldest register
1357 in register class CLASS. Return true if successfully replaced. */
1359 static bool
1360 replace_oldest_value_reg (rtx *loc, enum reg_class class, rtx insn,
1361 struct value_data *vd)
1363 rtx new = find_oldest_value_reg (class, *loc, vd);
1364 if (new)
1366 if (rtl_dump_file)
1367 fprintf (rtl_dump_file, "insn %u: replaced reg %u with %u\n",
1368 INSN_UID (insn), REGNO (*loc), REGNO (new));
1370 *loc = new;
1371 return true;
1373 return false;
1376 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1377 Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
1378 BASE_REG_CLASS depending on how the register is being considered. */
1380 static bool
1381 replace_oldest_value_addr (rtx *loc, enum reg_class class,
1382 enum machine_mode mode, rtx insn,
1383 struct value_data *vd)
1385 rtx x = *loc;
1386 RTX_CODE code = GET_CODE (x);
1387 const char *fmt;
1388 int i, j;
1389 bool changed = false;
1391 switch (code)
1393 case PLUS:
1395 rtx orig_op0 = XEXP (x, 0);
1396 rtx orig_op1 = XEXP (x, 1);
1397 RTX_CODE code0 = GET_CODE (orig_op0);
1398 RTX_CODE code1 = GET_CODE (orig_op1);
1399 rtx op0 = orig_op0;
1400 rtx op1 = orig_op1;
1401 rtx *locI = NULL;
1402 rtx *locB = NULL;
1404 if (GET_CODE (op0) == SUBREG)
1406 op0 = SUBREG_REG (op0);
1407 code0 = GET_CODE (op0);
1410 if (GET_CODE (op1) == SUBREG)
1412 op1 = SUBREG_REG (op1);
1413 code1 = GET_CODE (op1);
1416 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
1417 || code0 == ZERO_EXTEND || code1 == MEM)
1419 locI = &XEXP (x, 0);
1420 locB = &XEXP (x, 1);
1422 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
1423 || code1 == ZERO_EXTEND || code0 == MEM)
1425 locI = &XEXP (x, 1);
1426 locB = &XEXP (x, 0);
1428 else if (code0 == CONST_INT || code0 == CONST
1429 || code0 == SYMBOL_REF || code0 == LABEL_REF)
1430 locB = &XEXP (x, 1);
1431 else if (code1 == CONST_INT || code1 == CONST
1432 || code1 == SYMBOL_REF || code1 == LABEL_REF)
1433 locB = &XEXP (x, 0);
1434 else if (code0 == REG && code1 == REG)
1436 int index_op;
1438 if (REG_OK_FOR_INDEX_P (op0)
1439 && REG_MODE_OK_FOR_BASE_P (op1, mode))
1440 index_op = 0;
1441 else if (REG_OK_FOR_INDEX_P (op1)
1442 && REG_MODE_OK_FOR_BASE_P (op0, mode))
1443 index_op = 1;
1444 else if (REG_MODE_OK_FOR_BASE_P (op1, mode))
1445 index_op = 0;
1446 else if (REG_MODE_OK_FOR_BASE_P (op0, mode))
1447 index_op = 1;
1448 else if (REG_OK_FOR_INDEX_P (op1))
1449 index_op = 1;
1450 else
1451 index_op = 0;
1453 locI = &XEXP (x, index_op);
1454 locB = &XEXP (x, !index_op);
1456 else if (code0 == REG)
1458 locI = &XEXP (x, 0);
1459 locB = &XEXP (x, 1);
1461 else if (code1 == REG)
1463 locI = &XEXP (x, 1);
1464 locB = &XEXP (x, 0);
1467 if (locI)
1468 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode,
1469 insn, vd);
1470 if (locB)
1471 changed |= replace_oldest_value_addr (locB,
1472 MODE_BASE_REG_CLASS (mode),
1473 mode, insn, vd);
1474 return changed;
1477 case POST_INC:
1478 case POST_DEC:
1479 case POST_MODIFY:
1480 case PRE_INC:
1481 case PRE_DEC:
1482 case PRE_MODIFY:
1483 return false;
1485 case MEM:
1486 return replace_oldest_value_mem (x, insn, vd);
1488 case REG:
1489 return replace_oldest_value_reg (loc, class, insn, vd);
1491 default:
1492 break;
1495 fmt = GET_RTX_FORMAT (code);
1496 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1498 if (fmt[i] == 'e')
1499 changed |= replace_oldest_value_addr (&XEXP (x, i), class, mode,
1500 insn, vd);
1501 else if (fmt[i] == 'E')
1502 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1503 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), class,
1504 mode, insn, vd);
1507 return changed;
1510 /* Similar to replace_oldest_value_reg, but X contains a memory. */
1512 static bool
1513 replace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd)
1515 return replace_oldest_value_addr (&XEXP (x, 0),
1516 MODE_BASE_REG_CLASS (GET_MODE (x)),
1517 GET_MODE (x), insn, vd);
1520 /* Perform the forward copy propagation on basic block BB. */
1522 static bool
1523 copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd)
1525 bool changed = false;
1526 rtx insn;
1528 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
1530 int n_ops, i, alt, predicated;
1531 bool is_asm;
1532 rtx set;
1534 if (! INSN_P (insn))
1536 if (insn == BB_END (bb))
1537 break;
1538 else
1539 continue;
1542 set = single_set (insn);
1543 extract_insn (insn);
1544 if (! constrain_operands (1))
1545 fatal_insn_not_found (insn);
1546 preprocess_constraints ();
1547 alt = which_alternative;
1548 n_ops = recog_data.n_operands;
1549 is_asm = asm_noperands (PATTERN (insn)) >= 0;
1551 /* Simplify the code below by rewriting things to reflect
1552 matching constraints. Also promote OP_OUT to OP_INOUT
1553 in predicated instructions. */
1555 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1556 for (i = 0; i < n_ops; ++i)
1558 int matches = recog_op_alt[i][alt].matches;
1559 if (matches >= 0)
1560 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class;
1561 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
1562 || (predicated && recog_data.operand_type[i] == OP_OUT))
1563 recog_data.operand_type[i] = OP_INOUT;
1566 /* For each earlyclobber operand, zap the value data. */
1567 for (i = 0; i < n_ops; i++)
1568 if (recog_op_alt[i][alt].earlyclobber)
1569 kill_value (recog_data.operand[i], vd);
1571 /* Within asms, a clobber cannot overlap inputs or outputs.
1572 I wouldn't think this were true for regular insns, but
1573 scan_rtx treats them like that... */
1574 note_stores (PATTERN (insn), kill_clobbered_value, vd);
1576 /* Kill all auto-incremented values. */
1577 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
1578 for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd);
1580 /* Kill all early-clobbered operands. */
1581 for (i = 0; i < n_ops; i++)
1582 if (recog_op_alt[i][alt].earlyclobber)
1583 kill_value (recog_data.operand[i], vd);
1585 /* Special-case plain move instructions, since we may well
1586 be able to do the move from a different register class. */
1587 if (set && REG_P (SET_SRC (set)))
1589 rtx src = SET_SRC (set);
1590 unsigned int regno = REGNO (src);
1591 enum machine_mode mode = GET_MODE (src);
1592 unsigned int i;
1593 rtx new;
1595 /* If we are accessing SRC in some mode other that what we
1596 set it in, make sure that the replacement is valid. */
1597 if (mode != vd->e[regno].mode)
1599 if (HARD_REGNO_NREGS (regno, mode)
1600 > HARD_REGNO_NREGS (regno, vd->e[regno].mode))
1601 goto no_move_special_case;
1604 /* If the destination is also a register, try to find a source
1605 register in the same class. */
1606 if (REG_P (SET_DEST (set)))
1608 new = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd);
1609 if (new && validate_change (insn, &SET_SRC (set), new, 0))
1611 if (rtl_dump_file)
1612 fprintf (rtl_dump_file,
1613 "insn %u: replaced reg %u with %u\n",
1614 INSN_UID (insn), regno, REGNO (new));
1615 changed = true;
1616 goto did_replacement;
1620 /* Otherwise, try all valid registers and see if its valid. */
1621 for (i = vd->e[regno].oldest_regno; i != regno;
1622 i = vd->e[i].next_regno)
1624 new = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode,
1625 mode, i, regno);
1626 if (new != NULL_RTX)
1628 if (validate_change (insn, &SET_SRC (set), new, 0))
1630 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src);
1631 REG_ATTRS (new) = REG_ATTRS (src);
1632 if (rtl_dump_file)
1633 fprintf (rtl_dump_file,
1634 "insn %u: replaced reg %u with %u\n",
1635 INSN_UID (insn), regno, REGNO (new));
1636 changed = true;
1637 goto did_replacement;
1642 no_move_special_case:
1644 /* For each input operand, replace a hard register with the
1645 eldest live copy that's in an appropriate register class. */
1646 for (i = 0; i < n_ops; i++)
1648 bool replaced = false;
1650 /* Don't scan match_operand here, since we've no reg class
1651 information to pass down. Any operands that we could
1652 substitute in will be represented elsewhere. */
1653 if (recog_data.constraints[i][0] == '\0')
1654 continue;
1656 /* Don't replace in asms intentionally referencing hard regs. */
1657 if (is_asm && GET_CODE (recog_data.operand[i]) == REG
1658 && (REGNO (recog_data.operand[i])
1659 == ORIGINAL_REGNO (recog_data.operand[i])))
1660 continue;
1662 if (recog_data.operand_type[i] == OP_IN)
1664 if (recog_op_alt[i][alt].is_address)
1665 replaced
1666 = replace_oldest_value_addr (recog_data.operand_loc[i],
1667 recog_op_alt[i][alt].class,
1668 VOIDmode, insn, vd);
1669 else if (REG_P (recog_data.operand[i]))
1670 replaced
1671 = replace_oldest_value_reg (recog_data.operand_loc[i],
1672 recog_op_alt[i][alt].class,
1673 insn, vd);
1674 else if (GET_CODE (recog_data.operand[i]) == MEM)
1675 replaced = replace_oldest_value_mem (recog_data.operand[i],
1676 insn, vd);
1678 else if (GET_CODE (recog_data.operand[i]) == MEM)
1679 replaced = replace_oldest_value_mem (recog_data.operand[i],
1680 insn, vd);
1682 /* If we performed any replacement, update match_dups. */
1683 if (replaced)
1685 int j;
1686 rtx new;
1688 changed = true;
1690 new = *recog_data.operand_loc[i];
1691 recog_data.operand[i] = new;
1692 for (j = 0; j < recog_data.n_dups; j++)
1693 if (recog_data.dup_num[j] == i)
1694 *recog_data.dup_loc[j] = new;
1698 did_replacement:
1699 /* Clobber call-clobbered registers. */
1700 if (GET_CODE (insn) == CALL_INSN)
1701 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1702 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1703 kill_value_regno (i, vd);
1705 /* Notice stores. */
1706 note_stores (PATTERN (insn), kill_set_value, vd);
1708 /* Notice copies. */
1709 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
1710 copy_value (SET_DEST (set), SET_SRC (set), vd);
1712 if (insn == BB_END (bb))
1713 break;
1716 return changed;
1719 /* Main entry point for the forward copy propagation optimization. */
1721 void
1722 copyprop_hardreg_forward (void)
1724 struct value_data *all_vd;
1725 bool need_refresh;
1726 basic_block bb, bbp = 0;
1728 need_refresh = false;
1730 all_vd = xmalloc (sizeof (struct value_data) * last_basic_block);
1732 FOR_EACH_BB (bb)
1734 /* If a block has a single predecessor, that we've already
1735 processed, begin with the value data that was live at
1736 the end of the predecessor block. */
1737 /* ??? Ought to use more intelligent queuing of blocks. */
1738 if (bb->pred)
1739 for (bbp = bb; bbp && bbp != bb->pred->src; bbp = bbp->prev_bb);
1740 if (bb->pred
1741 && ! bb->pred->pred_next
1742 && ! (bb->pred->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1743 && bb->pred->src != ENTRY_BLOCK_PTR
1744 && bbp)
1745 all_vd[bb->index] = all_vd[bb->pred->src->index];
1746 else
1747 init_value_data (all_vd + bb->index);
1749 if (copyprop_hardreg_forward_1 (bb, all_vd + bb->index))
1750 need_refresh = true;
1753 if (need_refresh)
1755 if (rtl_dump_file)
1756 fputs ("\n\n", rtl_dump_file);
1758 /* ??? Irritatingly, delete_noop_moves does not take a set of blocks
1759 to scan, so we have to do a life update with no initial set of
1760 blocks Just In Case. */
1761 delete_noop_moves (get_insns ());
1762 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
1763 PROP_DEATH_NOTES
1764 | PROP_SCAN_DEAD_CODE
1765 | PROP_KILL_DEAD_CODE);
1768 free (all_vd);
1771 /* Dump the value chain data to stderr. */
1773 void
1774 debug_value_data (struct value_data *vd)
1776 HARD_REG_SET set;
1777 unsigned int i, j;
1779 CLEAR_HARD_REG_SET (set);
1781 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1782 if (vd->e[i].oldest_regno == i)
1784 if (vd->e[i].mode == VOIDmode)
1786 if (vd->e[i].next_regno != INVALID_REGNUM)
1787 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n",
1788 i, vd->e[i].next_regno);
1789 continue;
1792 SET_HARD_REG_BIT (set, i);
1793 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode));
1795 for (j = vd->e[i].next_regno;
1796 j != INVALID_REGNUM;
1797 j = vd->e[j].next_regno)
1799 if (TEST_HARD_REG_BIT (set, j))
1801 fprintf (stderr, "[%u] Loop in regno chain\n", j);
1802 return;
1805 if (vd->e[j].oldest_regno != i)
1807 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n",
1808 j, vd->e[j].oldest_regno);
1809 return;
1811 SET_HARD_REG_BIT (set, j);
1812 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode));
1814 fputc ('\n', stderr);
1817 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1818 if (! TEST_HARD_REG_BIT (set, i)
1819 && (vd->e[i].mode != VOIDmode
1820 || vd->e[i].oldest_regno != i
1821 || vd->e[i].next_regno != INVALID_REGNUM))
1822 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n",
1823 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1824 vd->e[i].next_regno);
1827 #ifdef ENABLE_CHECKING
1828 static void
1829 validate_value_data (struct value_data *vd)
1831 HARD_REG_SET set;
1832 unsigned int i, j;
1834 CLEAR_HARD_REG_SET (set);
1836 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1837 if (vd->e[i].oldest_regno == i)
1839 if (vd->e[i].mode == VOIDmode)
1841 if (vd->e[i].next_regno != INVALID_REGNUM)
1842 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1843 i, vd->e[i].next_regno);
1844 continue;
1847 SET_HARD_REG_BIT (set, i);
1849 for (j = vd->e[i].next_regno;
1850 j != INVALID_REGNUM;
1851 j = vd->e[j].next_regno)
1853 if (TEST_HARD_REG_BIT (set, j))
1854 internal_error ("validate_value_data: Loop in regno chain (%u)",
1856 if (vd->e[j].oldest_regno != i)
1857 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1858 j, vd->e[j].oldest_regno);
1860 SET_HARD_REG_BIT (set, j);
1864 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1865 if (! TEST_HARD_REG_BIT (set, i)
1866 && (vd->e[i].mode != VOIDmode
1867 || vd->e[i].oldest_regno != i
1868 || vd->e[i].next_regno != INVALID_REGNUM))
1869 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1870 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1871 vd->e[i].next_regno);
1873 #endif