* arm.mc (return_address_mask): Use CC_REGNUM for the condition code
[official-gcc.git] / gcc / regrename.c
blob027e2f444b7808465de9c39ce39795ca9a28244d
1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002 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 reg_class class;
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 PARAMS ((struct du_chain *, int));
82 static void scan_rtx_reg PARAMS ((rtx, rtx *, enum reg_class,
83 enum scan_actions, enum op_type, int));
84 static void scan_rtx_address PARAMS ((rtx, rtx *, enum reg_class,
85 enum scan_actions, enum machine_mode));
86 static void scan_rtx PARAMS ((rtx, rtx *, enum reg_class,
87 enum scan_actions, enum op_type, int));
88 static struct du_chain *build_def_use PARAMS ((basic_block));
89 static void dump_def_use_chain PARAMS ((struct du_chain *));
90 static void note_sets PARAMS ((rtx, rtx, void *));
91 static void clear_dead_regs PARAMS ((HARD_REG_SET *, enum machine_mode, rtx));
92 static void merge_overlapping_regs PARAMS ((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 (x, set, data)
100 rtx x;
101 rtx set ATTRIBUTE_UNUSED;
102 void *data;
104 HARD_REG_SET *pset = (HARD_REG_SET *) data;
105 unsigned int regno;
106 int nregs;
107 if (GET_CODE (x) != REG)
108 return;
109 regno = REGNO (x);
110 nregs = HARD_REGNO_NREGS (regno, GET_MODE (x));
112 /* There must not be pseudos at this point. */
113 if (regno + nregs > FIRST_PSEUDO_REGISTER)
114 abort ();
116 while (nregs-- > 0)
117 SET_HARD_REG_BIT (*pset, regno + nregs);
120 /* Clear all registers from *PSET for which a note of kind KIND can be found
121 in the list NOTES. */
123 static void
124 clear_dead_regs (pset, kind, notes)
125 HARD_REG_SET *pset;
126 enum machine_mode kind;
127 rtx notes;
129 rtx note;
130 for (note = notes; note; note = XEXP (note, 1))
131 if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0)))
133 rtx reg = XEXP (note, 0);
134 unsigned int regno = REGNO (reg);
135 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
137 /* There must not be pseudos at this point. */
138 if (regno + nregs > FIRST_PSEUDO_REGISTER)
139 abort ();
141 while (nregs-- > 0)
142 CLEAR_HARD_REG_BIT (*pset, regno + nregs);
146 /* For a def-use chain CHAIN in basic block B, find which registers overlap
147 its lifetime and set the corresponding bits in *PSET. */
149 static void
150 merge_overlapping_regs (b, pset, chain)
151 basic_block b;
152 HARD_REG_SET *pset;
153 struct du_chain *chain;
155 struct du_chain *t = chain;
156 rtx insn;
157 HARD_REG_SET live;
159 REG_SET_TO_HARD_REG_SET (live, b->global_live_at_start);
160 insn = b->head;
161 while (t)
163 /* Search forward until the next reference to the register to be
164 renamed. */
165 while (insn != t->insn)
167 if (INSN_P (insn))
169 clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn));
170 note_stores (PATTERN (insn), note_sets, (void *) &live);
171 /* Only record currently live regs if we are inside the
172 reg's live range. */
173 if (t != chain)
174 IOR_HARD_REG_SET (*pset, live);
175 clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn));
177 insn = NEXT_INSN (insn);
180 IOR_HARD_REG_SET (*pset, live);
182 /* For the last reference, also merge in all registers set in the
183 same insn.
184 @@@ We only have take earlyclobbered sets into account. */
185 if (! t->next_use)
186 note_stores (PATTERN (insn), note_sets, (void *) pset);
188 t = t->next_use;
192 /* Perform register renaming on the current function. */
194 void
195 regrename_optimize ()
197 int tick[FIRST_PSEUDO_REGISTER];
198 int this_tick = 0;
199 basic_block bb;
200 char *first_obj;
202 memset (tick, 0, sizeof tick);
204 gcc_obstack_init (&rename_obstack);
205 first_obj = (char *) obstack_alloc (&rename_obstack, 0);
207 FOR_EACH_BB (bb)
209 struct du_chain *all_chains = 0;
210 HARD_REG_SET unavailable;
211 HARD_REG_SET regs_seen;
213 CLEAR_HARD_REG_SET (unavailable);
215 if (rtl_dump_file)
216 fprintf (rtl_dump_file, "\nBasic block %d:\n", bb->index);
218 all_chains = build_def_use (bb);
220 if (rtl_dump_file)
221 dump_def_use_chain (all_chains);
223 CLEAR_HARD_REG_SET (unavailable);
224 /* Don't clobber traceback for noreturn functions. */
225 if (frame_pointer_needed)
227 int i;
229 for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;)
230 SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM + i);
232 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
233 for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;)
234 SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM + i);
235 #endif
238 CLEAR_HARD_REG_SET (regs_seen);
239 while (all_chains)
241 int new_reg, best_new_reg = -1;
242 int n_uses;
243 struct du_chain *this = all_chains;
244 struct du_chain *tmp, *last;
245 HARD_REG_SET this_unavailable;
246 int reg = REGNO (*this->loc);
247 int i;
249 all_chains = this->next_chain;
251 #if 0 /* This just disables optimization opportunities. */
252 /* Only rename once we've seen the reg more than once. */
253 if (! TEST_HARD_REG_BIT (regs_seen, reg))
255 SET_HARD_REG_BIT (regs_seen, reg);
256 continue;
258 #endif
260 if (fixed_regs[reg] || global_regs[reg]
261 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
262 || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
263 #else
264 || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
265 #endif
267 continue;
269 COPY_HARD_REG_SET (this_unavailable, unavailable);
271 /* Find last entry on chain (which has the need_caller_save bit),
272 count number of uses, and narrow the set of registers we can
273 use for renaming. */
274 n_uses = 0;
275 for (last = this; last->next_use; last = last->next_use)
277 n_uses++;
278 IOR_COMPL_HARD_REG_SET (this_unavailable,
279 reg_class_contents[last->class]);
281 if (n_uses < 1)
282 continue;
284 IOR_COMPL_HARD_REG_SET (this_unavailable,
285 reg_class_contents[last->class]);
287 if (this->need_caller_save_reg)
288 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
290 merge_overlapping_regs (bb, &this_unavailable, this);
292 /* Now potential_regs is a reasonable approximation, let's
293 have a closer look at each register still in there. */
294 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
296 int nregs = HARD_REGNO_NREGS (new_reg, GET_MODE (*this->loc));
298 for (i = nregs - 1; i >= 0; --i)
299 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
300 || fixed_regs[new_reg + i]
301 || global_regs[new_reg + i]
302 /* Can't use regs which aren't saved by the prologue. */
303 || (! regs_ever_live[new_reg + i]
304 && ! call_used_regs[new_reg + i])
305 #ifdef LEAF_REGISTERS
306 /* We can't use a non-leaf register if we're in a
307 leaf function. */
308 || (current_function_is_leaf
309 && !LEAF_REGISTERS[new_reg + i])
310 #endif
311 #ifdef HARD_REGNO_RENAME_OK
312 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
313 #endif
315 break;
316 if (i >= 0)
317 continue;
319 /* See whether it accepts all modes that occur in
320 definition and uses. */
321 for (tmp = this; tmp; tmp = tmp->next_use)
322 if (! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
323 || (tmp->need_caller_save_reg
324 && ! (HARD_REGNO_CALL_PART_CLOBBERED
325 (reg, GET_MODE (*tmp->loc)))
326 && (HARD_REGNO_CALL_PART_CLOBBERED
327 (new_reg, GET_MODE (*tmp->loc)))))
328 break;
329 if (! tmp)
331 if (best_new_reg == -1
332 || tick[best_new_reg] > tick[new_reg])
333 best_new_reg = new_reg;
337 if (rtl_dump_file)
339 fprintf (rtl_dump_file, "Register %s in insn %d",
340 reg_names[reg], INSN_UID (last->insn));
341 if (last->need_caller_save_reg)
342 fprintf (rtl_dump_file, " crosses a call");
345 if (best_new_reg == -1)
347 if (rtl_dump_file)
348 fprintf (rtl_dump_file, "; no available registers\n");
349 continue;
352 do_replace (this, best_new_reg);
353 tick[best_new_reg] = this_tick++;
355 if (rtl_dump_file)
356 fprintf (rtl_dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
359 obstack_free (&rename_obstack, first_obj);
362 obstack_free (&rename_obstack, NULL);
364 if (rtl_dump_file)
365 fputc ('\n', rtl_dump_file);
367 count_or_remove_death_notes (NULL, 1);
368 update_life_info (NULL, UPDATE_LIFE_LOCAL,
369 PROP_REG_INFO | PROP_DEATH_NOTES);
372 static void
373 do_replace (chain, reg)
374 struct du_chain *chain;
375 int reg;
377 while (chain)
379 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
380 struct reg_attrs * attr = REG_ATTRS (*chain->loc);
382 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
383 if (regno >= FIRST_PSEUDO_REGISTER)
384 ORIGINAL_REGNO (*chain->loc) = regno;
385 REG_ATTRS (*chain->loc) = attr;
386 chain = chain->next_use;
391 static struct du_chain *open_chains;
392 static struct du_chain *closed_chains;
394 static void
395 scan_rtx_reg (insn, loc, class, action, type, earlyclobber)
396 rtx insn;
397 rtx *loc;
398 enum reg_class class;
399 enum scan_actions action;
400 enum op_type type;
401 int earlyclobber;
403 struct du_chain **p;
404 rtx x = *loc;
405 enum machine_mode mode = GET_MODE (x);
406 int this_regno = REGNO (x);
407 int this_nregs = HARD_REGNO_NREGS (this_regno, mode);
409 if (action == mark_write)
411 if (type == OP_OUT)
413 struct du_chain *this = (struct du_chain *)
414 obstack_alloc (&rename_obstack, sizeof (struct du_chain));
415 this->next_use = 0;
416 this->next_chain = open_chains;
417 this->loc = loc;
418 this->insn = insn;
419 this->class = class;
420 this->need_caller_save_reg = 0;
421 this->earlyclobber = earlyclobber;
422 open_chains = this;
424 return;
427 if ((type == OP_OUT && action != terminate_write)
428 || (type != OP_OUT && action == terminate_write))
429 return;
431 for (p = &open_chains; *p;)
433 struct du_chain *this = *p;
435 /* Check if the chain has been terminated if it has then skip to
436 the next chain.
438 This can happen when we've already appended the location to
439 the chain in Step 3, but are trying to hide in-out operands
440 from terminate_write in Step 5. */
442 if (*this->loc == cc0_rtx)
443 p = &this->next_chain;
444 else
446 int regno = REGNO (*this->loc);
447 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (*this->loc));
448 int exact_match = (regno == this_regno && nregs == this_nregs);
450 if (regno + nregs <= this_regno
451 || this_regno + this_nregs <= regno)
453 p = &this->next_chain;
454 continue;
457 if (action == mark_read)
459 if (! exact_match)
460 abort ();
462 /* ??? Class NO_REGS can happen if the md file makes use of
463 EXTRA_CONSTRAINTS to match registers. Which is arguably
464 wrong, but there we are. Since we know not what this may
465 be replaced with, terminate the chain. */
466 if (class != NO_REGS)
468 this = (struct du_chain *)
469 obstack_alloc (&rename_obstack, sizeof (struct du_chain));
470 this->next_use = 0;
471 this->next_chain = (*p)->next_chain;
472 this->loc = loc;
473 this->insn = insn;
474 this->class = class;
475 this->need_caller_save_reg = 0;
476 while (*p)
477 p = &(*p)->next_use;
478 *p = this;
479 return;
483 if (action != terminate_overlapping_read || ! exact_match)
485 struct du_chain *next = this->next_chain;
487 /* Whether the terminated chain can be used for renaming
488 depends on the action and this being an exact match.
489 In either case, we remove this element from open_chains. */
491 if ((action == terminate_dead || action == terminate_write)
492 && exact_match)
494 this->next_chain = closed_chains;
495 closed_chains = this;
496 if (rtl_dump_file)
497 fprintf (rtl_dump_file,
498 "Closing chain %s at insn %d (%s)\n",
499 reg_names[REGNO (*this->loc)], INSN_UID (insn),
500 scan_actions_name[(int) action]);
502 else
504 if (rtl_dump_file)
505 fprintf (rtl_dump_file,
506 "Discarding chain %s at insn %d (%s)\n",
507 reg_names[REGNO (*this->loc)], INSN_UID (insn),
508 scan_actions_name[(int) action]);
510 *p = next;
512 else
513 p = &this->next_chain;
518 /* Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
519 BASE_REG_CLASS depending on how the register is being considered. */
521 static void
522 scan_rtx_address (insn, loc, class, action, mode)
523 rtx insn;
524 rtx *loc;
525 enum reg_class class;
526 enum scan_actions action;
527 enum machine_mode mode;
529 rtx x = *loc;
530 RTX_CODE code = GET_CODE (x);
531 const char *fmt;
532 int i, j;
534 if (action == mark_write)
535 return;
537 switch (code)
539 case PLUS:
541 rtx orig_op0 = XEXP (x, 0);
542 rtx orig_op1 = XEXP (x, 1);
543 RTX_CODE code0 = GET_CODE (orig_op0);
544 RTX_CODE code1 = GET_CODE (orig_op1);
545 rtx op0 = orig_op0;
546 rtx op1 = orig_op1;
547 rtx *locI = NULL;
548 rtx *locB = NULL;
550 if (GET_CODE (op0) == SUBREG)
552 op0 = SUBREG_REG (op0);
553 code0 = GET_CODE (op0);
556 if (GET_CODE (op1) == SUBREG)
558 op1 = SUBREG_REG (op1);
559 code1 = GET_CODE (op1);
562 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
563 || code0 == ZERO_EXTEND || code1 == MEM)
565 locI = &XEXP (x, 0);
566 locB = &XEXP (x, 1);
568 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
569 || code1 == ZERO_EXTEND || code0 == MEM)
571 locI = &XEXP (x, 1);
572 locB = &XEXP (x, 0);
574 else if (code0 == CONST_INT || code0 == CONST
575 || code0 == SYMBOL_REF || code0 == LABEL_REF)
576 locB = &XEXP (x, 1);
577 else if (code1 == CONST_INT || code1 == CONST
578 || code1 == SYMBOL_REF || code1 == LABEL_REF)
579 locB = &XEXP (x, 0);
580 else if (code0 == REG && code1 == REG)
582 int index_op;
584 if (REG_OK_FOR_INDEX_P (op0)
585 && REG_MODE_OK_FOR_BASE_P (op1, mode))
586 index_op = 0;
587 else if (REG_OK_FOR_INDEX_P (op1)
588 && REG_MODE_OK_FOR_BASE_P (op0, mode))
589 index_op = 1;
590 else if (REG_MODE_OK_FOR_BASE_P (op1, mode))
591 index_op = 0;
592 else if (REG_MODE_OK_FOR_BASE_P (op0, mode))
593 index_op = 1;
594 else if (REG_OK_FOR_INDEX_P (op1))
595 index_op = 1;
596 else
597 index_op = 0;
599 locI = &XEXP (x, index_op);
600 locB = &XEXP (x, !index_op);
602 else if (code0 == REG)
604 locI = &XEXP (x, 0);
605 locB = &XEXP (x, 1);
607 else if (code1 == REG)
609 locI = &XEXP (x, 1);
610 locB = &XEXP (x, 0);
613 if (locI)
614 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
615 if (locB)
616 scan_rtx_address (insn, locB, MODE_BASE_REG_CLASS (mode), action, mode);
617 return;
620 case POST_INC:
621 case POST_DEC:
622 case POST_MODIFY:
623 case PRE_INC:
624 case PRE_DEC:
625 case PRE_MODIFY:
626 #ifndef AUTO_INC_DEC
627 /* If the target doesn't claim to handle autoinc, this must be
628 something special, like a stack push. Kill this chain. */
629 action = terminate_all_read;
630 #endif
631 break;
633 case MEM:
634 scan_rtx_address (insn, &XEXP (x, 0),
635 MODE_BASE_REG_CLASS (GET_MODE (x)), action,
636 GET_MODE (x));
637 return;
639 case REG:
640 scan_rtx_reg (insn, loc, class, action, OP_IN, 0);
641 return;
643 default:
644 break;
647 fmt = GET_RTX_FORMAT (code);
648 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
650 if (fmt[i] == 'e')
651 scan_rtx_address (insn, &XEXP (x, i), class, action, mode);
652 else if (fmt[i] == 'E')
653 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
654 scan_rtx_address (insn, &XVECEXP (x, i, j), class, action, mode);
658 static void
659 scan_rtx (insn, loc, class, action, type, earlyclobber)
660 rtx insn;
661 rtx *loc;
662 enum reg_class class;
663 enum scan_actions action;
664 enum op_type type;
665 int earlyclobber;
667 const char *fmt;
668 rtx x = *loc;
669 enum rtx_code code = GET_CODE (x);
670 int i, j;
672 code = GET_CODE (x);
673 switch (code)
675 case CONST:
676 case CONST_INT:
677 case CONST_DOUBLE:
678 case CONST_VECTOR:
679 case SYMBOL_REF:
680 case LABEL_REF:
681 case CC0:
682 case PC:
683 return;
685 case REG:
686 scan_rtx_reg (insn, loc, class, action, type, earlyclobber);
687 return;
689 case MEM:
690 scan_rtx_address (insn, &XEXP (x, 0),
691 MODE_BASE_REG_CLASS (GET_MODE (x)), action,
692 GET_MODE (x));
693 return;
695 case SET:
696 scan_rtx (insn, &SET_SRC (x), class, action, OP_IN, 0);
697 scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 0);
698 return;
700 case STRICT_LOW_PART:
701 scan_rtx (insn, &XEXP (x, 0), class, action, OP_INOUT, earlyclobber);
702 return;
704 case ZERO_EXTRACT:
705 case SIGN_EXTRACT:
706 scan_rtx (insn, &XEXP (x, 0), class, action,
707 type == OP_IN ? OP_IN : OP_INOUT, earlyclobber);
708 scan_rtx (insn, &XEXP (x, 1), class, action, OP_IN, 0);
709 scan_rtx (insn, &XEXP (x, 2), class, action, OP_IN, 0);
710 return;
712 case POST_INC:
713 case PRE_INC:
714 case POST_DEC:
715 case PRE_DEC:
716 case POST_MODIFY:
717 case PRE_MODIFY:
718 /* Should only happen inside MEM. */
719 abort ();
721 case CLOBBER:
722 scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 1);
723 return;
725 case EXPR_LIST:
726 scan_rtx (insn, &XEXP (x, 0), class, action, type, 0);
727 if (XEXP (x, 1))
728 scan_rtx (insn, &XEXP (x, 1), class, action, type, 0);
729 return;
731 default:
732 break;
735 fmt = GET_RTX_FORMAT (code);
736 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
738 if (fmt[i] == 'e')
739 scan_rtx (insn, &XEXP (x, i), class, action, type, 0);
740 else if (fmt[i] == 'E')
741 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
742 scan_rtx (insn, &XVECEXP (x, i, j), class, action, type, 0);
746 /* Build def/use chain. */
748 static struct du_chain *
749 build_def_use (bb)
750 basic_block bb;
752 rtx insn;
754 open_chains = closed_chains = NULL;
756 for (insn = bb->head; ; insn = NEXT_INSN (insn))
758 if (INSN_P (insn))
760 int n_ops;
761 rtx note;
762 rtx old_operands[MAX_RECOG_OPERANDS];
763 rtx old_dups[MAX_DUP_OPERANDS];
764 int i, icode;
765 int alt;
766 int predicated;
768 /* Process the insn, determining its effect on the def-use
769 chains. We perform the following steps with the register
770 references in the insn:
771 (1) Any read that overlaps an open chain, but doesn't exactly
772 match, causes that chain to be closed. We can't deal
773 with overlaps yet.
774 (2) Any read outside an operand causes any chain it overlaps
775 with to be closed, since we can't replace it.
776 (3) Any read inside an operand is added if there's already
777 an open chain for it.
778 (4) For any REG_DEAD note we find, close open chains that
779 overlap it.
780 (5) For any write we find, close open chains that overlap it.
781 (6) For any write we find in an operand, make a new chain.
782 (7) For any REG_UNUSED, close any chains we just opened. */
784 icode = recog_memoized (insn);
785 extract_insn (insn);
786 if (! constrain_operands (1))
787 fatal_insn_not_found (insn);
788 preprocess_constraints ();
789 alt = which_alternative;
790 n_ops = recog_data.n_operands;
792 /* Simplify the code below by rewriting things to reflect
793 matching constraints. Also promote OP_OUT to OP_INOUT
794 in predicated instructions. */
796 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
797 for (i = 0; i < n_ops; ++i)
799 int matches = recog_op_alt[i][alt].matches;
800 if (matches >= 0)
801 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class;
802 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
803 || (predicated && recog_data.operand_type[i] == OP_OUT))
804 recog_data.operand_type[i] = OP_INOUT;
807 /* Step 1: Close chains for which we have overlapping reads. */
808 for (i = 0; i < n_ops; i++)
809 scan_rtx (insn, recog_data.operand_loc[i],
810 NO_REGS, terminate_overlapping_read,
811 recog_data.operand_type[i], 0);
813 /* Step 2: Close chains for which we have reads outside operands.
814 We do this by munging all operands into CC0, and closing
815 everything remaining. */
817 for (i = 0; i < n_ops; i++)
819 old_operands[i] = recog_data.operand[i];
820 /* Don't squash match_operator or match_parallel here, since
821 we don't know that all of the contained registers are
822 reachable by proper operands. */
823 if (recog_data.constraints[i][0] == '\0')
824 continue;
825 *recog_data.operand_loc[i] = cc0_rtx;
827 for (i = 0; i < recog_data.n_dups; i++)
829 int dup_num = recog_data.dup_num[i];
831 old_dups[i] = *recog_data.dup_loc[i];
832 *recog_data.dup_loc[i] = cc0_rtx;
834 /* For match_dup of match_operator or match_parallel, share
835 them, so that we don't miss changes in the dup. */
836 if (icode >= 0
837 && insn_data[icode].operand[dup_num].eliminable == 0)
838 old_dups[i] = recog_data.operand[dup_num];
841 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read,
842 OP_IN, 0);
844 for (i = 0; i < recog_data.n_dups; i++)
845 *recog_data.dup_loc[i] = old_dups[i];
846 for (i = 0; i < n_ops; i++)
847 *recog_data.operand_loc[i] = old_operands[i];
849 /* Step 2B: Can't rename function call argument registers. */
850 if (GET_CODE (insn) == CALL_INSN && CALL_INSN_FUNCTION_USAGE (insn))
851 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
852 NO_REGS, terminate_all_read, OP_IN, 0);
854 /* Step 2C: Can't rename asm operands that were originally
855 hard registers. */
856 if (asm_noperands (PATTERN (insn)) > 0)
857 for (i = 0; i < n_ops; i++)
859 rtx *loc = recog_data.operand_loc[i];
860 rtx op = *loc;
862 if (GET_CODE (op) == REG
863 && REGNO (op) == ORIGINAL_REGNO (op)
864 && (recog_data.operand_type[i] == OP_IN
865 || recog_data.operand_type[i] == OP_INOUT))
866 scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0);
869 /* Step 3: Append to chains for reads inside operands. */
870 for (i = 0; i < n_ops + recog_data.n_dups; i++)
872 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
873 rtx *loc = (i < n_ops
874 ? recog_data.operand_loc[opn]
875 : recog_data.dup_loc[i - n_ops]);
876 enum reg_class class = recog_op_alt[opn][alt].class;
877 enum op_type type = recog_data.operand_type[opn];
879 /* Don't scan match_operand here, since we've no reg class
880 information to pass down. Any operands that we could
881 substitute in will be represented elsewhere. */
882 if (recog_data.constraints[opn][0] == '\0')
883 continue;
885 if (recog_op_alt[opn][alt].is_address)
886 scan_rtx_address (insn, loc, class, mark_read, VOIDmode);
887 else
888 scan_rtx (insn, loc, class, mark_read, type, 0);
891 /* Step 4: Close chains for registers that die here.
892 Also record updates for REG_INC notes. */
893 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
895 if (REG_NOTE_KIND (note) == REG_DEAD)
896 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
897 OP_IN, 0);
898 else if (REG_NOTE_KIND (note) == REG_INC)
899 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
900 OP_INOUT, 0);
903 /* Step 4B: If this is a call, any chain live at this point
904 requires a caller-saved reg. */
905 if (GET_CODE (insn) == CALL_INSN)
907 struct du_chain *p;
908 for (p = open_chains; p; p = p->next_chain)
909 p->need_caller_save_reg = 1;
912 /* Step 5: Close open chains that overlap writes. Similar to
913 step 2, we hide in-out operands, since we do not want to
914 close these chains. */
916 for (i = 0; i < n_ops; i++)
918 old_operands[i] = recog_data.operand[i];
919 if (recog_data.operand_type[i] == OP_INOUT)
920 *recog_data.operand_loc[i] = cc0_rtx;
922 for (i = 0; i < recog_data.n_dups; i++)
924 int opn = recog_data.dup_num[i];
925 old_dups[i] = *recog_data.dup_loc[i];
926 if (recog_data.operand_type[opn] == OP_INOUT)
927 *recog_data.dup_loc[i] = cc0_rtx;
930 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0);
932 for (i = 0; i < recog_data.n_dups; i++)
933 *recog_data.dup_loc[i] = old_dups[i];
934 for (i = 0; i < n_ops; i++)
935 *recog_data.operand_loc[i] = old_operands[i];
937 /* Step 6: Begin new chains for writes inside operands. */
938 /* ??? Many targets have output constraints on the SET_DEST
939 of a call insn, which is stupid, since these are certainly
940 ABI defined hard registers. Don't change calls at all.
941 Similarly take special care for asm statement that originally
942 referenced hard registers. */
943 if (asm_noperands (PATTERN (insn)) > 0)
945 for (i = 0; i < n_ops; i++)
946 if (recog_data.operand_type[i] == OP_OUT)
948 rtx *loc = recog_data.operand_loc[i];
949 rtx op = *loc;
950 enum reg_class class = recog_op_alt[i][alt].class;
952 if (GET_CODE (op) == REG
953 && REGNO (op) == ORIGINAL_REGNO (op))
954 continue;
956 scan_rtx (insn, loc, class, mark_write, OP_OUT,
957 recog_op_alt[i][alt].earlyclobber);
960 else if (GET_CODE (insn) != CALL_INSN)
961 for (i = 0; i < n_ops + recog_data.n_dups; i++)
963 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
964 rtx *loc = (i < n_ops
965 ? recog_data.operand_loc[opn]
966 : recog_data.dup_loc[i - n_ops]);
967 enum reg_class class = recog_op_alt[opn][alt].class;
969 if (recog_data.operand_type[opn] == OP_OUT)
970 scan_rtx (insn, loc, class, mark_write, OP_OUT,
971 recog_op_alt[opn][alt].earlyclobber);
974 /* Step 7: Close chains for registers that were never
975 really used here. */
976 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
977 if (REG_NOTE_KIND (note) == REG_UNUSED)
978 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
979 OP_IN, 0);
981 if (insn == bb->end)
982 break;
985 /* Since we close every chain when we find a REG_DEAD note, anything that
986 is still open lives past the basic block, so it can't be renamed. */
987 return closed_chains;
990 /* Dump all def/use chains in CHAINS to RTL_DUMP_FILE. They are
991 printed in reverse order as that's how we build them. */
993 static void
994 dump_def_use_chain (chains)
995 struct du_chain *chains;
997 while (chains)
999 struct du_chain *this = chains;
1000 int r = REGNO (*this->loc);
1001 int nregs = HARD_REGNO_NREGS (r, GET_MODE (*this->loc));
1002 fprintf (rtl_dump_file, "Register %s (%d):", reg_names[r], nregs);
1003 while (this)
1005 fprintf (rtl_dump_file, " %d [%s]", INSN_UID (this->insn),
1006 reg_class_names[this->class]);
1007 this = this->next_use;
1009 fprintf (rtl_dump_file, "\n");
1010 chains = chains->next_chain;
1014 /* The following code does forward propagation of hard register copies.
1015 The object is to eliminate as many dependencies as possible, so that
1016 we have the most scheduling freedom. As a side effect, we also clean
1017 up some silly register allocation decisions made by reload. This
1018 code may be obsoleted by a new register allocator. */
1020 /* For each register, we have a list of registers that contain the same
1021 value. The OLDEST_REGNO field points to the head of the list, and
1022 the NEXT_REGNO field runs through the list. The MODE field indicates
1023 what mode the data is known to be in; this field is VOIDmode when the
1024 register is not known to contain valid data. */
1026 struct value_data_entry
1028 enum machine_mode mode;
1029 unsigned int oldest_regno;
1030 unsigned int next_regno;
1033 struct value_data
1035 struct value_data_entry e[FIRST_PSEUDO_REGISTER];
1036 unsigned int max_value_regs;
1039 static void kill_value_regno PARAMS ((unsigned, struct value_data *));
1040 static void kill_value PARAMS ((rtx, struct value_data *));
1041 static void set_value_regno PARAMS ((unsigned, enum machine_mode,
1042 struct value_data *));
1043 static void init_value_data PARAMS ((struct value_data *));
1044 static void kill_clobbered_value PARAMS ((rtx, rtx, void *));
1045 static void kill_set_value PARAMS ((rtx, rtx, void *));
1046 static int kill_autoinc_value PARAMS ((rtx *, void *));
1047 static void copy_value PARAMS ((rtx, rtx, struct value_data *));
1048 static bool mode_change_ok PARAMS ((enum machine_mode, enum machine_mode,
1049 unsigned int));
1050 static rtx maybe_mode_change PARAMS ((enum machine_mode, enum machine_mode,
1051 enum machine_mode, unsigned int,
1052 unsigned int));
1053 static rtx find_oldest_value_reg PARAMS ((enum reg_class, rtx,
1054 struct value_data *));
1055 static bool replace_oldest_value_reg PARAMS ((rtx *, enum reg_class, rtx,
1056 struct value_data *));
1057 static bool replace_oldest_value_addr PARAMS ((rtx *, enum reg_class,
1058 enum machine_mode, rtx,
1059 struct value_data *));
1060 static bool replace_oldest_value_mem PARAMS ((rtx, rtx, struct value_data *));
1061 static bool copyprop_hardreg_forward_1 PARAMS ((basic_block,
1062 struct value_data *));
1063 extern void debug_value_data PARAMS ((struct value_data *));
1064 #ifdef ENABLE_CHECKING
1065 static void validate_value_data PARAMS ((struct value_data *));
1066 #endif
1068 /* Kill register REGNO. This involves removing it from any value lists,
1069 and resetting the value mode to VOIDmode. */
1071 static void
1072 kill_value_regno (regno, vd)
1073 unsigned int regno;
1074 struct value_data *vd;
1076 unsigned int i, next;
1078 if (vd->e[regno].oldest_regno != regno)
1080 for (i = vd->e[regno].oldest_regno;
1081 vd->e[i].next_regno != regno;
1082 i = vd->e[i].next_regno)
1083 continue;
1084 vd->e[i].next_regno = vd->e[regno].next_regno;
1086 else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM)
1088 for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno)
1089 vd->e[i].oldest_regno = next;
1092 vd->e[regno].mode = VOIDmode;
1093 vd->e[regno].oldest_regno = regno;
1094 vd->e[regno].next_regno = INVALID_REGNUM;
1096 #ifdef ENABLE_CHECKING
1097 validate_value_data (vd);
1098 #endif
1101 /* Kill X. This is a convenience function for kill_value_regno
1102 so that we mind the mode the register is in. */
1104 static void
1105 kill_value (x, vd)
1106 rtx x;
1107 struct value_data *vd;
1109 /* SUBREGS are supposed to have been eliminated by now. But some
1110 ports, e.g. i386 sse, use them to smuggle vector type information
1111 through to instruction selection. Each such SUBREG should simplify,
1112 so if we get a NULL we've done something wrong elsewhere. */
1114 if (GET_CODE (x) == SUBREG)
1115 x = simplify_subreg (GET_MODE (x), SUBREG_REG (x),
1116 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
1117 if (REG_P (x))
1119 unsigned int regno = REGNO (x);
1120 unsigned int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
1121 unsigned int i, j;
1123 /* Kill the value we're told to kill. */
1124 for (i = 0; i < n; ++i)
1125 kill_value_regno (regno + i, vd);
1127 /* Kill everything that overlapped what we're told to kill. */
1128 if (regno < vd->max_value_regs)
1129 j = 0;
1130 else
1131 j = regno - vd->max_value_regs;
1132 for (; j < regno; ++j)
1134 if (vd->e[j].mode == VOIDmode)
1135 continue;
1136 n = HARD_REGNO_NREGS (j, vd->e[j].mode);
1137 if (j + n > regno)
1138 for (i = 0; i < n; ++i)
1139 kill_value_regno (j + i, vd);
1144 /* Remember that REGNO is valid in MODE. */
1146 static void
1147 set_value_regno (regno, mode, vd)
1148 unsigned int regno;
1149 enum machine_mode mode;
1150 struct value_data *vd;
1152 unsigned int nregs;
1154 vd->e[regno].mode = mode;
1156 nregs = HARD_REGNO_NREGS (regno, mode);
1157 if (nregs > vd->max_value_regs)
1158 vd->max_value_regs = nregs;
1161 /* Initialize VD such that there are no known relationships between regs. */
1163 static void
1164 init_value_data (vd)
1165 struct value_data *vd;
1167 int i;
1168 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1170 vd->e[i].mode = VOIDmode;
1171 vd->e[i].oldest_regno = i;
1172 vd->e[i].next_regno = INVALID_REGNUM;
1174 vd->max_value_regs = 0;
1177 /* Called through note_stores. If X is clobbered, kill its value. */
1179 static void
1180 kill_clobbered_value (x, set, data)
1181 rtx x;
1182 rtx set;
1183 void *data;
1185 struct value_data *vd = data;
1186 if (GET_CODE (set) == CLOBBER)
1187 kill_value (x, vd);
1190 /* Called through note_stores. If X is set, not clobbered, kill its
1191 current value and install it as the root of its own value list. */
1193 static void
1194 kill_set_value (x, set, data)
1195 rtx x;
1196 rtx set;
1197 void *data;
1199 struct value_data *vd = data;
1200 if (GET_CODE (set) != CLOBBER)
1202 kill_value (x, vd);
1203 if (REG_P (x))
1204 set_value_regno (REGNO (x), GET_MODE (x), vd);
1208 /* Called through for_each_rtx. Kill any register used as the base of an
1209 auto-increment expression, and install that register as the root of its
1210 own value list. */
1212 static int
1213 kill_autoinc_value (px, data)
1214 rtx *px;
1215 void *data;
1217 rtx x = *px;
1218 struct value_data *vd = data;
1220 if (GET_RTX_CLASS (GET_CODE (x)) == 'a')
1222 x = XEXP (x, 0);
1223 kill_value (x, vd);
1224 set_value_regno (REGNO (x), Pmode, vd);
1225 return -1;
1228 return 0;
1231 /* Assert that SRC has been copied to DEST. Adjust the data structures
1232 to reflect that SRC contains an older copy of the shared value. */
1234 static void
1235 copy_value (dest, src, vd)
1236 rtx dest;
1237 rtx src;
1238 struct value_data *vd;
1240 unsigned int dr = REGNO (dest);
1241 unsigned int sr = REGNO (src);
1242 unsigned int dn, sn;
1243 unsigned int i;
1245 /* ??? At present, it's possible to see noop sets. It'd be nice if
1246 this were cleaned up beforehand... */
1247 if (sr == dr)
1248 return;
1250 /* Do not propagate copies to the stack pointer, as that can leave
1251 memory accesses with no scheduling dependency on the stack update. */
1252 if (dr == STACK_POINTER_REGNUM)
1253 return;
1255 /* Likewise with the frame pointer, if we're using one. */
1256 if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM)
1257 return;
1259 /* If SRC and DEST overlap, don't record anything. */
1260 dn = HARD_REGNO_NREGS (dr, GET_MODE (dest));
1261 sn = HARD_REGNO_NREGS (sr, GET_MODE (dest));
1262 if ((dr > sr && dr < sr + sn)
1263 || (sr > dr && sr < dr + dn))
1264 return;
1266 /* If SRC had no assigned mode (i.e. we didn't know it was live)
1267 assign it now and assume the value came from an input argument
1268 or somesuch. */
1269 if (vd->e[sr].mode == VOIDmode)
1270 set_value_regno (sr, vd->e[dr].mode, vd);
1272 /* If we are narrowing the input to a smaller number of hard regs,
1273 and it is in big endian, we are really extracting a high part.
1274 Since we generally associate a low part of a value with the value itself,
1275 we must not do the same for the high part.
1276 Note we can still get low parts for the same mode combination through
1277 a two-step copy involving differently sized hard regs.
1278 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
1279 (set (reg:DI r0) (reg:DI fr0))
1280 (set (reg:SI fr2) (reg:SI r0))
1281 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
1282 (set (reg:SI fr2) (reg:SI fr0))
1283 loads the high part of (reg:DI fr0) into fr2.
1285 We can't properly represent the latter case in our tables, so don't
1286 record anything then. */
1287 else if (sn < (unsigned int) HARD_REGNO_NREGS (sr, vd->e[sr].mode)
1288 && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD
1289 ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
1290 return;
1292 /* If SRC had been assigned a mode narrower than the copy, we can't
1293 link DEST into the chain, because not all of the pieces of the
1294 copy came from oldest_regno. */
1295 else if (sn > (unsigned int) HARD_REGNO_NREGS (sr, vd->e[sr].mode))
1296 return;
1298 /* Link DR at the end of the value chain used by SR. */
1300 vd->e[dr].oldest_regno = vd->e[sr].oldest_regno;
1302 for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno)
1303 continue;
1304 vd->e[i].next_regno = dr;
1306 #ifdef ENABLE_CHECKING
1307 validate_value_data (vd);
1308 #endif
1311 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
1313 static bool
1314 mode_change_ok (orig_mode, new_mode, regno)
1315 enum machine_mode orig_mode, new_mode;
1316 unsigned int regno ATTRIBUTE_UNUSED;
1318 if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode))
1319 return false;
1321 #ifdef CANNOT_CHANGE_MODE_CLASS
1322 return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode);
1323 #endif
1325 return true;
1328 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
1329 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
1330 in NEW_MODE.
1331 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
1333 static rtx
1334 maybe_mode_change (orig_mode, copy_mode, new_mode, regno, copy_regno)
1335 enum machine_mode orig_mode, copy_mode, new_mode;
1336 unsigned int regno, copy_regno ATTRIBUTE_UNUSED;
1338 if (orig_mode == new_mode)
1339 return gen_rtx_raw_REG (new_mode, regno);
1340 else if (mode_change_ok (orig_mode, new_mode, regno))
1342 int copy_nregs = HARD_REGNO_NREGS (copy_regno, copy_mode);
1343 int use_nregs = HARD_REGNO_NREGS (copy_regno, new_mode);
1344 int copy_offset
1345 = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs);
1346 int offset
1347 = GET_MODE_SIZE (orig_mode) - GET_MODE_SIZE (new_mode) - copy_offset;
1348 int byteoffset = offset % UNITS_PER_WORD;
1349 int wordoffset = offset - byteoffset;
1351 offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0)
1352 + (BYTES_BIG_ENDIAN ? byteoffset : 0));
1353 return gen_rtx_raw_REG (new_mode,
1354 regno + subreg_regno_offset (regno, orig_mode,
1355 offset,
1356 new_mode));
1358 return NULL_RTX;
1361 /* Find the oldest copy of the value contained in REGNO that is in
1362 register class CLASS and has mode MODE. If found, return an rtx
1363 of that oldest register, otherwise return NULL. */
1365 static rtx
1366 find_oldest_value_reg (class, reg, vd)
1367 enum reg_class class;
1368 rtx reg;
1369 struct value_data *vd;
1371 unsigned int regno = REGNO (reg);
1372 enum machine_mode mode = GET_MODE (reg);
1373 unsigned int i;
1375 /* If we are accessing REG in some mode other that what we set it in,
1376 make sure that the replacement is valid. In particular, consider
1377 (set (reg:DI r11) (...))
1378 (set (reg:SI r9) (reg:SI r11))
1379 (set (reg:SI r10) (...))
1380 (set (...) (reg:DI r9))
1381 Replacing r9 with r11 is invalid. */
1382 if (mode != vd->e[regno].mode)
1384 if (HARD_REGNO_NREGS (regno, mode)
1385 > HARD_REGNO_NREGS (regno, vd->e[regno].mode))
1386 return NULL_RTX;
1389 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno)
1391 enum machine_mode oldmode = vd->e[i].mode;
1392 rtx new;
1394 if (TEST_HARD_REG_BIT (reg_class_contents[class], i)
1395 && (new = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i,
1396 regno)))
1398 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg);
1399 REG_ATTRS (new) = REG_ATTRS (reg);
1400 return new;
1404 return NULL_RTX;
1407 /* If possible, replace the register at *LOC with the oldest register
1408 in register class CLASS. Return true if successfully replaced. */
1410 static bool
1411 replace_oldest_value_reg (loc, class, insn, vd)
1412 rtx *loc;
1413 enum reg_class class;
1414 rtx insn;
1415 struct value_data *vd;
1417 rtx new = find_oldest_value_reg (class, *loc, vd);
1418 if (new)
1420 if (rtl_dump_file)
1421 fprintf (rtl_dump_file, "insn %u: replaced reg %u with %u\n",
1422 INSN_UID (insn), REGNO (*loc), REGNO (new));
1424 *loc = new;
1425 return true;
1427 return false;
1430 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1431 Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
1432 BASE_REG_CLASS depending on how the register is being considered. */
1434 static bool
1435 replace_oldest_value_addr (loc, class, mode, insn, vd)
1436 rtx *loc;
1437 enum reg_class class;
1438 enum machine_mode mode;
1439 rtx insn;
1440 struct value_data *vd;
1442 rtx x = *loc;
1443 RTX_CODE code = GET_CODE (x);
1444 const char *fmt;
1445 int i, j;
1446 bool changed = false;
1448 switch (code)
1450 case PLUS:
1452 rtx orig_op0 = XEXP (x, 0);
1453 rtx orig_op1 = XEXP (x, 1);
1454 RTX_CODE code0 = GET_CODE (orig_op0);
1455 RTX_CODE code1 = GET_CODE (orig_op1);
1456 rtx op0 = orig_op0;
1457 rtx op1 = orig_op1;
1458 rtx *locI = NULL;
1459 rtx *locB = NULL;
1461 if (GET_CODE (op0) == SUBREG)
1463 op0 = SUBREG_REG (op0);
1464 code0 = GET_CODE (op0);
1467 if (GET_CODE (op1) == SUBREG)
1469 op1 = SUBREG_REG (op1);
1470 code1 = GET_CODE (op1);
1473 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
1474 || code0 == ZERO_EXTEND || code1 == MEM)
1476 locI = &XEXP (x, 0);
1477 locB = &XEXP (x, 1);
1479 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
1480 || code1 == ZERO_EXTEND || code0 == MEM)
1482 locI = &XEXP (x, 1);
1483 locB = &XEXP (x, 0);
1485 else if (code0 == CONST_INT || code0 == CONST
1486 || code0 == SYMBOL_REF || code0 == LABEL_REF)
1487 locB = &XEXP (x, 1);
1488 else if (code1 == CONST_INT || code1 == CONST
1489 || code1 == SYMBOL_REF || code1 == LABEL_REF)
1490 locB = &XEXP (x, 0);
1491 else if (code0 == REG && code1 == REG)
1493 int index_op;
1495 if (REG_OK_FOR_INDEX_P (op0)
1496 && REG_MODE_OK_FOR_BASE_P (op1, mode))
1497 index_op = 0;
1498 else if (REG_OK_FOR_INDEX_P (op1)
1499 && REG_MODE_OK_FOR_BASE_P (op0, mode))
1500 index_op = 1;
1501 else if (REG_MODE_OK_FOR_BASE_P (op1, mode))
1502 index_op = 0;
1503 else if (REG_MODE_OK_FOR_BASE_P (op0, mode))
1504 index_op = 1;
1505 else if (REG_OK_FOR_INDEX_P (op1))
1506 index_op = 1;
1507 else
1508 index_op = 0;
1510 locI = &XEXP (x, index_op);
1511 locB = &XEXP (x, !index_op);
1513 else if (code0 == REG)
1515 locI = &XEXP (x, 0);
1516 locB = &XEXP (x, 1);
1518 else if (code1 == REG)
1520 locI = &XEXP (x, 1);
1521 locB = &XEXP (x, 0);
1524 if (locI)
1525 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode,
1526 insn, vd);
1527 if (locB)
1528 changed |= replace_oldest_value_addr (locB,
1529 MODE_BASE_REG_CLASS (mode),
1530 mode, insn, vd);
1531 return changed;
1534 case POST_INC:
1535 case POST_DEC:
1536 case POST_MODIFY:
1537 case PRE_INC:
1538 case PRE_DEC:
1539 case PRE_MODIFY:
1540 return false;
1542 case MEM:
1543 return replace_oldest_value_mem (x, insn, vd);
1545 case REG:
1546 return replace_oldest_value_reg (loc, class, insn, vd);
1548 default:
1549 break;
1552 fmt = GET_RTX_FORMAT (code);
1553 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1555 if (fmt[i] == 'e')
1556 changed |= replace_oldest_value_addr (&XEXP (x, i), class, mode,
1557 insn, vd);
1558 else if (fmt[i] == 'E')
1559 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1560 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), class,
1561 mode, insn, vd);
1564 return changed;
1567 /* Similar to replace_oldest_value_reg, but X contains a memory. */
1569 static bool
1570 replace_oldest_value_mem (x, insn, vd)
1571 rtx x;
1572 rtx insn;
1573 struct value_data *vd;
1575 return replace_oldest_value_addr (&XEXP (x, 0),
1576 MODE_BASE_REG_CLASS (GET_MODE (x)),
1577 GET_MODE (x), insn, vd);
1580 /* Perform the forward copy propagation on basic block BB. */
1582 static bool
1583 copyprop_hardreg_forward_1 (bb, vd)
1584 basic_block bb;
1585 struct value_data *vd;
1587 bool changed = false;
1588 rtx insn;
1590 for (insn = bb->head; ; insn = NEXT_INSN (insn))
1592 int n_ops, i, alt, predicated;
1593 bool is_asm;
1594 rtx set;
1596 if (! INSN_P (insn))
1598 if (insn == bb->end)
1599 break;
1600 else
1601 continue;
1604 set = single_set (insn);
1605 extract_insn (insn);
1606 if (! constrain_operands (1))
1607 fatal_insn_not_found (insn);
1608 preprocess_constraints ();
1609 alt = which_alternative;
1610 n_ops = recog_data.n_operands;
1611 is_asm = asm_noperands (PATTERN (insn)) >= 0;
1613 /* Simplify the code below by rewriting things to reflect
1614 matching constraints. Also promote OP_OUT to OP_INOUT
1615 in predicated instructions. */
1617 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1618 for (i = 0; i < n_ops; ++i)
1620 int matches = recog_op_alt[i][alt].matches;
1621 if (matches >= 0)
1622 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class;
1623 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
1624 || (predicated && recog_data.operand_type[i] == OP_OUT))
1625 recog_data.operand_type[i] = OP_INOUT;
1628 /* For each earlyclobber operand, zap the value data. */
1629 for (i = 0; i < n_ops; i++)
1630 if (recog_op_alt[i][alt].earlyclobber)
1631 kill_value (recog_data.operand[i], vd);
1633 /* Within asms, a clobber cannot overlap inputs or outputs.
1634 I wouldn't think this were true for regular insns, but
1635 scan_rtx treats them like that... */
1636 note_stores (PATTERN (insn), kill_clobbered_value, vd);
1638 /* Kill all auto-incremented values. */
1639 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
1640 for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd);
1642 /* Kill all early-clobbered operands. */
1643 for (i = 0; i < n_ops; i++)
1644 if (recog_op_alt[i][alt].earlyclobber)
1645 kill_value (recog_data.operand[i], vd);
1647 /* Special-case plain move instructions, since we may well
1648 be able to do the move from a different register class. */
1649 if (set && REG_P (SET_SRC (set)))
1651 rtx src = SET_SRC (set);
1652 unsigned int regno = REGNO (src);
1653 enum machine_mode mode = GET_MODE (src);
1654 unsigned int i;
1655 rtx new;
1657 /* If we are accessing SRC in some mode other that what we
1658 set it in, make sure that the replacement is valid. */
1659 if (mode != vd->e[regno].mode)
1661 if (HARD_REGNO_NREGS (regno, mode)
1662 > HARD_REGNO_NREGS (regno, vd->e[regno].mode))
1663 goto no_move_special_case;
1666 /* If the destination is also a register, try to find a source
1667 register in the same class. */
1668 if (REG_P (SET_DEST (set)))
1670 new = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd);
1671 if (new && validate_change (insn, &SET_SRC (set), new, 0))
1673 if (rtl_dump_file)
1674 fprintf (rtl_dump_file,
1675 "insn %u: replaced reg %u with %u\n",
1676 INSN_UID (insn), regno, REGNO (new));
1677 changed = true;
1678 goto did_replacement;
1682 /* Otherwise, try all valid registers and see if its valid. */
1683 for (i = vd->e[regno].oldest_regno; i != regno;
1684 i = vd->e[i].next_regno)
1686 new = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode,
1687 mode, i, regno);
1688 if (new != NULL_RTX)
1690 if (validate_change (insn, &SET_SRC (set), new, 0))
1692 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src);
1693 REG_ATTRS (new) = REG_ATTRS (src);
1694 if (rtl_dump_file)
1695 fprintf (rtl_dump_file,
1696 "insn %u: replaced reg %u with %u\n",
1697 INSN_UID (insn), regno, REGNO (new));
1698 changed = true;
1699 goto did_replacement;
1704 no_move_special_case:
1706 /* For each input operand, replace a hard register with the
1707 eldest live copy that's in an appropriate register class. */
1708 for (i = 0; i < n_ops; i++)
1710 bool replaced = false;
1712 /* Don't scan match_operand here, since we've no reg class
1713 information to pass down. Any operands that we could
1714 substitute in will be represented elsewhere. */
1715 if (recog_data.constraints[i][0] == '\0')
1716 continue;
1718 /* Don't replace in asms intentionally referencing hard regs. */
1719 if (is_asm && GET_CODE (recog_data.operand[i]) == REG
1720 && (REGNO (recog_data.operand[i])
1721 == ORIGINAL_REGNO (recog_data.operand[i])))
1722 continue;
1724 if (recog_data.operand_type[i] == OP_IN)
1726 if (recog_op_alt[i][alt].is_address)
1727 replaced
1728 = replace_oldest_value_addr (recog_data.operand_loc[i],
1729 recog_op_alt[i][alt].class,
1730 VOIDmode, insn, vd);
1731 else if (REG_P (recog_data.operand[i]))
1732 replaced
1733 = replace_oldest_value_reg (recog_data.operand_loc[i],
1734 recog_op_alt[i][alt].class,
1735 insn, vd);
1736 else if (GET_CODE (recog_data.operand[i]) == MEM)
1737 replaced = replace_oldest_value_mem (recog_data.operand[i],
1738 insn, vd);
1740 else if (GET_CODE (recog_data.operand[i]) == MEM)
1741 replaced = replace_oldest_value_mem (recog_data.operand[i],
1742 insn, vd);
1744 /* If we performed any replacement, update match_dups. */
1745 if (replaced)
1747 int j;
1748 rtx new;
1750 changed = true;
1752 new = *recog_data.operand_loc[i];
1753 recog_data.operand[i] = new;
1754 for (j = 0; j < recog_data.n_dups; j++)
1755 if (recog_data.dup_num[j] == i)
1756 *recog_data.dup_loc[j] = new;
1760 did_replacement:
1761 /* Clobber call-clobbered registers. */
1762 if (GET_CODE (insn) == CALL_INSN)
1763 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1764 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1765 kill_value_regno (i, vd);
1767 /* Notice stores. */
1768 note_stores (PATTERN (insn), kill_set_value, vd);
1770 /* Notice copies. */
1771 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
1772 copy_value (SET_DEST (set), SET_SRC (set), vd);
1774 if (insn == bb->end)
1775 break;
1778 return changed;
1781 /* Main entry point for the forward copy propagation optimization. */
1783 void
1784 copyprop_hardreg_forward ()
1786 struct value_data *all_vd;
1787 bool need_refresh;
1788 basic_block bb, bbp = 0;
1790 need_refresh = false;
1792 all_vd = xmalloc (sizeof (struct value_data) * last_basic_block);
1794 FOR_EACH_BB (bb)
1796 /* If a block has a single predecessor, that we've already
1797 processed, begin with the value data that was live at
1798 the end of the predecessor block. */
1799 /* ??? Ought to use more intelligent queueing of blocks. */
1800 if (bb->pred)
1801 for (bbp = bb; bbp && bbp != bb->pred->src; bbp = bbp->prev_bb);
1802 if (bb->pred
1803 && ! bb->pred->pred_next
1804 && ! (bb->pred->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1805 && bb->pred->src != ENTRY_BLOCK_PTR
1806 && bbp)
1807 all_vd[bb->index] = all_vd[bb->pred->src->index];
1808 else
1809 init_value_data (all_vd + bb->index);
1811 if (copyprop_hardreg_forward_1 (bb, all_vd + bb->index))
1812 need_refresh = true;
1815 if (need_refresh)
1817 if (rtl_dump_file)
1818 fputs ("\n\n", rtl_dump_file);
1820 /* ??? Irritatingly, delete_noop_moves does not take a set of blocks
1821 to scan, so we have to do a life update with no initial set of
1822 blocks Just In Case. */
1823 delete_noop_moves (get_insns ());
1824 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
1825 PROP_DEATH_NOTES
1826 | PROP_SCAN_DEAD_CODE
1827 | PROP_KILL_DEAD_CODE);
1830 free (all_vd);
1833 /* Dump the value chain data to stderr. */
1835 void
1836 debug_value_data (vd)
1837 struct value_data *vd;
1839 HARD_REG_SET set;
1840 unsigned int i, j;
1842 CLEAR_HARD_REG_SET (set);
1844 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1845 if (vd->e[i].oldest_regno == i)
1847 if (vd->e[i].mode == VOIDmode)
1849 if (vd->e[i].next_regno != INVALID_REGNUM)
1850 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n",
1851 i, vd->e[i].next_regno);
1852 continue;
1855 SET_HARD_REG_BIT (set, i);
1856 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode));
1858 for (j = vd->e[i].next_regno;
1859 j != INVALID_REGNUM;
1860 j = vd->e[j].next_regno)
1862 if (TEST_HARD_REG_BIT (set, j))
1864 fprintf (stderr, "[%u] Loop in regno chain\n", j);
1865 return;
1868 if (vd->e[j].oldest_regno != i)
1870 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n",
1871 j, vd->e[j].oldest_regno);
1872 return;
1874 SET_HARD_REG_BIT (set, j);
1875 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode));
1877 fputc ('\n', stderr);
1880 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1881 if (! TEST_HARD_REG_BIT (set, i)
1882 && (vd->e[i].mode != VOIDmode
1883 || vd->e[i].oldest_regno != i
1884 || vd->e[i].next_regno != INVALID_REGNUM))
1885 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n",
1886 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1887 vd->e[i].next_regno);
1890 #ifdef ENABLE_CHECKING
1891 static void
1892 validate_value_data (vd)
1893 struct value_data *vd;
1895 HARD_REG_SET set;
1896 unsigned int i, j;
1898 CLEAR_HARD_REG_SET (set);
1900 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1901 if (vd->e[i].oldest_regno == i)
1903 if (vd->e[i].mode == VOIDmode)
1905 if (vd->e[i].next_regno != INVALID_REGNUM)
1906 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1907 i, vd->e[i].next_regno);
1908 continue;
1911 SET_HARD_REG_BIT (set, i);
1913 for (j = vd->e[i].next_regno;
1914 j != INVALID_REGNUM;
1915 j = vd->e[j].next_regno)
1917 if (TEST_HARD_REG_BIT (set, j))
1918 internal_error ("validate_value_data: Loop in regno chain (%u)",
1920 if (vd->e[j].oldest_regno != i)
1921 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1922 j, vd->e[j].oldest_regno);
1924 SET_HARD_REG_BIT (set, j);
1928 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1929 if (! TEST_HARD_REG_BIT (set, i)
1930 && (vd->e[i].mode != VOIDmode
1931 || vd->e[i].oldest_regno != i
1932 || vd->e[i].next_regno != INVALID_REGNUM))
1933 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1934 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1935 vd->e[i].next_regno);
1937 #endif