1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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. */
20
21 #define REG_OK_STRICT
22
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"
40
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
44
45 static const char *const reg_class_names[] = REG_CLASS_NAMES;
46
47 struct du_chain
48 {
49 struct du_chain *next_chain;
50 struct du_chain *next_use;
51
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;
57 };
58
59 enum scan_actions
60 {
61 terminate_all_read,
62 terminate_overlapping_read,
63 terminate_write,
64 terminate_dead,
65 mark_read,
66 mark_write
67 };
68
69 static const char * const scan_actions_name[] =
70 {
71 "terminate_all_read",
72 "terminate_overlapping_read",
73 "terminate_write",
74 "terminate_dead",
75 "mark_read",
76 "mark_write"
77 };
78
79 static struct obstack rename_obstack;
80
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 *);
94
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 *). */
97
98 static void
note_sets(rtx x,rtx set ATTRIBUTE_UNUSED,void * data)99 note_sets (rtx x, rtx set ATTRIBUTE_UNUSED, void *data)
100 {
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));
108
109 /* There must not be pseudos at this point. */
110 if (regno + nregs > FIRST_PSEUDO_REGISTER)
111 abort ();
112
113 while (nregs-- > 0)
114 SET_HARD_REG_BIT (*pset, regno + nregs);
115 }
116
117 /* Clear all registers from *PSET for which a note of kind KIND can be found
118 in the list NOTES. */
119
120 static void
clear_dead_regs(HARD_REG_SET * pset,enum machine_mode kind,rtx notes)121 clear_dead_regs (HARD_REG_SET *pset, enum machine_mode kind, rtx notes)
122 {
123 rtx note;
124 for (note = notes; note; note = XEXP (note, 1))
125 if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0)))
126 {
127 rtx reg = XEXP (note, 0);
128 unsigned int regno = REGNO (reg);
129 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
130
131 /* There must not be pseudos at this point. */
132 if (regno + nregs > FIRST_PSEUDO_REGISTER)
133 abort ();
134
135 while (nregs-- > 0)
136 CLEAR_HARD_REG_BIT (*pset, regno + nregs);
137 }
138 }
139
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. */
142
143 static void
merge_overlapping_regs(basic_block b,HARD_REG_SET * pset,struct du_chain * chain)144 merge_overlapping_regs (basic_block b, HARD_REG_SET *pset,
145 struct du_chain *chain)
146 {
147 struct du_chain *t = chain;
148 rtx insn;
149 HARD_REG_SET live;
150
151 REG_SET_TO_HARD_REG_SET (live, b->global_live_at_start);
152 insn = BB_HEAD (b);
153 while (t)
154 {
155 /* Search forward until the next reference to the register to be
156 renamed. */
157 while (insn != t->insn)
158 {
159 if (INSN_P (insn))
160 {
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));
168 }
169 insn = NEXT_INSN (insn);
170 }
171
172 IOR_HARD_REG_SET (*pset, live);
173
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);
179
180 t = t->next_use;
181 }
182 }
183
184 /* Perform register renaming on the current function. */
185
186 void
regrename_optimize(void)187 regrename_optimize (void)
188 {
189 int tick[FIRST_PSEUDO_REGISTER];
190 int this_tick = 0;
191 basic_block bb;
192 char *first_obj;
193
194 memset (tick, 0, sizeof tick);
195
196 gcc_obstack_init (&rename_obstack);
197 first_obj = obstack_alloc (&rename_obstack, 0);
198
199 FOR_EACH_BB (bb)
200 {
201 struct du_chain *all_chains = 0;
202 HARD_REG_SET unavailable;
203 HARD_REG_SET regs_seen;
204
205 CLEAR_HARD_REG_SET (unavailable);
206
207 if (rtl_dump_file)
208 fprintf (rtl_dump_file, "\nBasic block %d:\n", bb->index);
209
210 all_chains = build_def_use (bb);
211
212 if (rtl_dump_file)
213 dump_def_use_chain (all_chains);
214
215 CLEAR_HARD_REG_SET (unavailable);
216 /* Don't clobber traceback for noreturn functions. */
217 if (frame_pointer_needed)
218 {
219 int i;
220
221 for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;)
222 SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM + i);
223
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
228 }
229
230 CLEAR_HARD_REG_SET (regs_seen);
231 while (all_chains)
232 {
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;
240
241 all_chains = this->next_chain;
242
243 best_new_reg = reg;
244
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))
248 {
249 SET_HARD_REG_BIT (regs_seen, reg);
250 continue;
251 }
252 #endif
253
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
260 )
261 continue;
262
263 COPY_HARD_REG_SET (this_unavailable, unavailable);
264
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)
270 {
271 n_uses++;
272 IOR_COMPL_HARD_REG_SET (this_unavailable,
273 reg_class_contents[last->class]);
274 }
275 if (n_uses < 1)
276 continue;
277
278 IOR_COMPL_HARD_REG_SET (this_unavailable,
279 reg_class_contents[last->class]);
280
281 if (this->need_caller_save_reg)
282 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
283
284 merge_overlapping_regs (bb, &this_unavailable, this);
285
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++)
289 {
290 int nregs = HARD_REGNO_NREGS (new_reg, GET_MODE (*this->loc));
291
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
308 )
309 break;
310 if (i >= 0)
311 continue;
312
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)
324 {
325 if (tick[best_new_reg] > tick[new_reg])
326 best_new_reg = new_reg;
327 }
328 }
329
330 if (rtl_dump_file)
331 {
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");
336 }
337
338 if (best_new_reg == reg)
339 {
340 tick[reg] = ++this_tick;
341 if (rtl_dump_file)
342 fprintf (rtl_dump_file, "; no available better choice\n");
343 continue;
344 }
345
346 do_replace (this, best_new_reg);
347 tick[best_new_reg] = ++this_tick;
348
349 if (rtl_dump_file)
350 fprintf (rtl_dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
351 }
352
353 obstack_free (&rename_obstack, first_obj);
354 }
355
356 obstack_free (&rename_obstack, NULL);
357
358 if (rtl_dump_file)
359 fputc ('\n', rtl_dump_file);
360
361 count_or_remove_death_notes (NULL, 1);
362 update_life_info (NULL, UPDATE_LIFE_LOCAL,
363 PROP_REG_INFO | PROP_DEATH_NOTES);
364 }
365
366 static void
do_replace(struct du_chain * chain,int reg)367 do_replace (struct du_chain *chain, int reg)
368 {
369 while (chain)
370 {
371 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
372 struct reg_attrs * attr = REG_ATTRS (*chain->loc);
373
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;
379 }
380 }
381
382
383 static struct du_chain *open_chains;
384 static struct du_chain *closed_chains;
385
386 static void
scan_rtx_reg(rtx insn,rtx * loc,enum reg_class class,enum scan_actions action,enum op_type type,int earlyclobber)387 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class class,
388 enum scan_actions action, enum op_type type, int earlyclobber)
389 {
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);
395
396 if (action == mark_write)
397 {
398 if (type == OP_OUT)
399 {
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;
410 }
411 return;
412 }
413
414 if ((type == OP_OUT && action != terminate_write)
415 || (type != OP_OUT && action == terminate_write))
416 return;
417
418 for (p = &open_chains; *p;)
419 {
420 struct du_chain *this = *p;
421
422 /* Check if the chain has been terminated if it has then skip to
423 the next chain.
424
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. */
428
429 if (*this->loc == cc0_rtx)
430 p = &this->next_chain;
431 else
432 {
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);
436
437 if (regno + nregs <= this_regno
438 || this_regno + this_nregs <= regno)
439 {
440 p = &this->next_chain;
441 continue;
442 }
443
444 if (action == mark_read)
445 {
446 if (! exact_match)
447 abort ();
448
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)
454 {
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;
466 }
467 }
468
469 if (action != terminate_overlapping_read || ! exact_match)
470 {
471 struct du_chain *next = this->next_chain;
472
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. */
476
477 if ((action == terminate_dead || action == terminate_write)
478 && exact_match)
479 {
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]);
487 }
488 else
489 {
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]);
495 }
496 *p = next;
497 }
498 else
499 p = &this->next_chain;
500 }
501 }
502 }
503
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. */
506
507 static void
scan_rtx_address(rtx insn,rtx * loc,enum reg_class class,enum scan_actions action,enum machine_mode mode)508 scan_rtx_address (rtx insn, rtx *loc, enum reg_class class,
509 enum scan_actions action, enum machine_mode mode)
510 {
511 rtx x = *loc;
512 RTX_CODE code = GET_CODE (x);
513 const char *fmt;
514 int i, j;
515
516 if (action == mark_write)
517 return;
518
519 switch (code)
520 {
521 case PLUS:
522 {
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;
531
532 if (GET_CODE (op0) == SUBREG)
533 {
534 op0 = SUBREG_REG (op0);
535 code0 = GET_CODE (op0);
536 }
537
538 if (GET_CODE (op1) == SUBREG)
539 {
540 op1 = SUBREG_REG (op1);
541 code1 = GET_CODE (op1);
542 }
543
544 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
545 || code0 == ZERO_EXTEND || code1 == MEM)
546 {
547 locI = &XEXP (x, 0);
548 locB = &XEXP (x, 1);
549 }
550 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
551 || code1 == ZERO_EXTEND || code0 == MEM)
552 {
553 locI = &XEXP (x, 1);
554 locB = &XEXP (x, 0);
555 }
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)
563 {
564 int index_op;
565
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;
580
581 locI = &XEXP (x, index_op);
582 locB = &XEXP (x, !index_op);
583 }
584 else if (code0 == REG)
585 {
586 locI = &XEXP (x, 0);
587 locB = &XEXP (x, 1);
588 }
589 else if (code1 == REG)
590 {
591 locI = &XEXP (x, 1);
592 locB = &XEXP (x, 0);
593 }
594
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;
600 }
601
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;
614
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;
620
621 case REG:
622 scan_rtx_reg (insn, loc, class, action, OP_IN, 0);
623 return;
624
625 default:
626 break;
627 }
628
629 fmt = GET_RTX_FORMAT (code);
630 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
631 {
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);
637 }
638 }
639
640 static void
scan_rtx(rtx insn,rtx * loc,enum reg_class class,enum scan_actions action,enum op_type type,int earlyclobber)641 scan_rtx (rtx insn, rtx *loc, enum reg_class class,
642 enum scan_actions action, enum op_type type, int earlyclobber)
643 {
644 const char *fmt;
645 rtx x = *loc;
646 enum rtx_code code = GET_CODE (x);
647 int i, j;
648
649 code = GET_CODE (x);
650 switch (code)
651 {
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;
661
662 case REG:
663 scan_rtx_reg (insn, loc, class, action, type, earlyclobber);
664 return;
665
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;
671
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;
676
677 case STRICT_LOW_PART:
678 scan_rtx (insn, &XEXP (x, 0), class, action, OP_INOUT, earlyclobber);
679 return;
680
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;
688
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 ();
697
698 case CLOBBER:
699 scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 1);
700 return;
701
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;
707
708 default:
709 break;
710 }
711
712 fmt = GET_RTX_FORMAT (code);
713 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
714 {
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);
720 }
721 }
722
723 /* Build def/use chain. */
724
725 static struct du_chain *
build_def_use(basic_block bb)726 build_def_use (basic_block bb)
727 {
728 rtx insn;
729
730 open_chains = closed_chains = NULL;
731
732 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
733 {
734 if (INSN_P (insn))
735 {
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;
743
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. */
759
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;
767
768 /* Simplify the code below by rewriting things to reflect
769 matching constraints. Also promote OP_OUT to OP_INOUT
770 in predicated instructions. */
771
772 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
773 for (i = 0; i < n_ops; ++i)
774 {
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;
781 }
782
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);
788
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. */
792
793 for (i = 0; i < n_ops; i++)
794 {
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;
802 }
803 for (i = 0; i < recog_data.n_dups; i++)
804 {
805 int dup_num = recog_data.dup_num[i];
806
807 old_dups[i] = *recog_data.dup_loc[i];
808 *recog_data.dup_loc[i] = cc0_rtx;
809
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];
815 }
816
817 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read,
818 OP_IN, 0);
819
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];
824
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);
829
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++)
834 {
835 rtx *loc = recog_data.operand_loc[i];
836 rtx op = *loc;
837
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);
843 }
844
845 /* Step 3: Append to chains for reads inside operands. */
846 for (i = 0; i < n_ops + recog_data.n_dups; i++)
847 {
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];
854
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;
860
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);
865 }
866
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))
870 {
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);
877 }
878
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)
882 {
883 struct du_chain *p;
884 for (p = open_chains; p; p = p->next_chain)
885 p->need_caller_save_reg = 1;
886 }
887
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. */
891
892 for (i = 0; i < n_ops; i++)
893 {
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;
897 }
898 for (i = 0; i < recog_data.n_dups; i++)
899 {
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;
904 }
905
906 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0);
907
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];
912
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)
920 {
921 for (i = 0; i < n_ops; i++)
922 if (recog_data.operand_type[i] == OP_OUT)
923 {
924 rtx *loc = recog_data.operand_loc[i];
925 rtx op = *loc;
926 enum reg_class class = recog_op_alt[i][alt].class;
927
928 if (GET_CODE (op) == REG
929 && REGNO (op) == ORIGINAL_REGNO (op))
930 continue;
931
932 scan_rtx (insn, loc, class, mark_write, OP_OUT,
933 recog_op_alt[i][alt].earlyclobber);
934 }
935 }
936 else if (GET_CODE (insn) != CALL_INSN)
937 for (i = 0; i < n_ops + recog_data.n_dups; i++)
938 {
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;
944
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);
948 }
949
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);
956 }
957 if (insn == BB_END (bb))
958 break;
959 }
960
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;
964 }
965
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. */
968
969 static void
dump_def_use_chain(struct du_chain * chains)970 dump_def_use_chain (struct du_chain *chains)
971 {
972 while (chains)
973 {
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)
979 {
980 fprintf (rtl_dump_file, " %d [%s]", INSN_UID (this->insn),
981 reg_class_names[this->class]);
982 this = this->next_use;
983 }
984 fprintf (rtl_dump_file, "\n");
985 chains = chains->next_chain;
986 }
987 }
988
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. */
994
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. */
1000
1001 struct value_data_entry
1002 {
1003 enum machine_mode mode;
1004 unsigned int oldest_regno;
1005 unsigned int next_regno;
1006 };
1007
1008 struct value_data
1009 {
1010 struct value_data_entry e[FIRST_PSEUDO_REGISTER];
1011 unsigned int max_value_regs;
1012 };
1013
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
1038
1039 /* Kill register REGNO. This involves removing it from any value lists,
1040 and resetting the value mode to VOIDmode. */
1041
1042 static void
kill_value_regno(unsigned int regno,struct value_data * vd)1043 kill_value_regno (unsigned int regno, struct value_data *vd)
1044 {
1045 unsigned int i, next;
1046
1047 if (vd->e[regno].oldest_regno != regno)
1048 {
1049 for (i = vd->e[regno].oldest_regno;
1050 vd->e[i].next_regno != regno;
1051 i = vd->e[i].next_regno)
1052 continue;
1053 vd->e[i].next_regno = vd->e[regno].next_regno;
1054 }
1055 else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM)
1056 {
1057 for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno)
1058 vd->e[i].oldest_regno = next;
1059 }
1060
1061 vd->e[regno].mode = VOIDmode;
1062 vd->e[regno].oldest_regno = regno;
1063 vd->e[regno].next_regno = INVALID_REGNUM;
1064
1065 #ifdef ENABLE_CHECKING
1066 validate_value_data (vd);
1067 #endif
1068 }
1069
1070 /* Kill X. This is a convenience function for kill_value_regno
1071 so that we mind the mode the register is in. */
1072
1073 static void
kill_value(rtx x,struct value_data * vd)1074 kill_value (rtx x, struct value_data *vd)
1075 {
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. */
1080
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))
1085 {
1086 unsigned int regno = REGNO (x);
1087 unsigned int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
1088 unsigned int i, j;
1089
1090 /* Kill the value we're told to kill. */
1091 for (i = 0; i < n; ++i)
1092 kill_value_regno (regno + i, vd);
1093
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)
1100 {
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);
1107 }
1108 }
1109 }
1110
1111 /* Remember that REGNO is valid in MODE. */
1112
1113 static void
set_value_regno(unsigned int regno,enum machine_mode mode,struct value_data * vd)1114 set_value_regno (unsigned int regno, enum machine_mode mode,
1115 struct value_data *vd)
1116 {
1117 unsigned int nregs;
1118
1119 vd->e[regno].mode = mode;
1120
1121 nregs = HARD_REGNO_NREGS (regno, mode);
1122 if (nregs > vd->max_value_regs)
1123 vd->max_value_regs = nregs;
1124 }
1125
1126 /* Initialize VD such that there are no known relationships between regs. */
1127
1128 static void
init_value_data(struct value_data * vd)1129 init_value_data (struct value_data *vd)
1130 {
1131 int i;
1132 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1133 {
1134 vd->e[i].mode = VOIDmode;
1135 vd->e[i].oldest_regno = i;
1136 vd->e[i].next_regno = INVALID_REGNUM;
1137 }
1138 vd->max_value_regs = 0;
1139 }
1140
1141 /* Called through note_stores. If X is clobbered, kill its value. */
1142
1143 static void
kill_clobbered_value(rtx x,rtx set,void * data)1144 kill_clobbered_value (rtx x, rtx set, void *data)
1145 {
1146 struct value_data *vd = data;
1147 if (GET_CODE (set) == CLOBBER)
1148 kill_value (x, vd);
1149 }
1150
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. */
1153
1154 static void
kill_set_value(rtx x,rtx set,void * data)1155 kill_set_value (rtx x, rtx set, void *data)
1156 {
1157 struct value_data *vd = data;
1158 if (GET_CODE (set) != CLOBBER)
1159 {
1160 kill_value (x, vd);
1161 if (REG_P (x))
1162 set_value_regno (REGNO (x), GET_MODE (x), vd);
1163 }
1164 }
1165
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. */
1169
1170 static int
kill_autoinc_value(rtx * px,void * data)1171 kill_autoinc_value (rtx *px, void *data)
1172 {
1173 rtx x = *px;
1174 struct value_data *vd = data;
1175
1176 if (GET_RTX_CLASS (GET_CODE (x)) == 'a')
1177 {
1178 x = XEXP (x, 0);
1179 kill_value (x, vd);
1180 set_value_regno (REGNO (x), Pmode, vd);
1181 return -1;
1182 }
1183
1184 return 0;
1185 }
1186
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. */
1189
1190 static void
copy_value(rtx dest,rtx src,struct value_data * vd)1191 copy_value (rtx dest, rtx src, struct value_data *vd)
1192 {
1193 unsigned int dr = REGNO (dest);
1194 unsigned int sr = REGNO (src);
1195 unsigned int dn, sn;
1196 unsigned int i;
1197
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;
1202
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;
1207
1208 /* Likewise with the frame pointer, if we're using one. */
1209 if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM)
1210 return;
1211
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;
1218
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);
1224
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.
1237
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;
1244
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;
1250
1251 /* Link DR at the end of the value chain used by SR. */
1252
1253 vd->e[dr].oldest_regno = vd->e[sr].oldest_regno;
1254
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;
1258
1259 #ifdef ENABLE_CHECKING
1260 validate_value_data (vd);
1261 #endif
1262 }
1263
1264 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
1265
1266 static bool
mode_change_ok(enum machine_mode orig_mode,enum machine_mode new_mode,unsigned int regno ATTRIBUTE_UNUSED)1267 mode_change_ok (enum machine_mode orig_mode, enum machine_mode new_mode,
1268 unsigned int regno ATTRIBUTE_UNUSED)
1269 {
1270 if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode))
1271 return false;
1272
1273 #ifdef CANNOT_CHANGE_MODE_CLASS
1274 return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode);
1275 #endif
1276
1277 return true;
1278 }
1279
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. */
1284
1285 static rtx
maybe_mode_change(enum machine_mode orig_mode,enum machine_mode copy_mode,enum machine_mode new_mode,unsigned int regno,unsigned int copy_regno ATTRIBUTE_UNUSED)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)
1289 {
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))
1293 {
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;
1302
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));
1309 }
1310 return NULL_RTX;
1311 }
1312
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. */
1316
1317 static rtx
find_oldest_value_reg(enum reg_class class,rtx reg,struct value_data * vd)1318 find_oldest_value_reg (enum reg_class class, rtx reg, struct value_data *vd)
1319 {
1320 unsigned int regno = REGNO (reg);
1321 enum machine_mode mode = GET_MODE (reg);
1322 unsigned int i;
1323
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)
1332 {
1333 if (HARD_REGNO_NREGS (regno, mode)
1334 > HARD_REGNO_NREGS (regno, vd->e[regno].mode))
1335 return NULL_RTX;
1336 }
1337
1338 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno)
1339 {
1340 enum machine_mode oldmode = vd->e[i].mode;
1341 rtx new;
1342 unsigned int last;
1343
1344 for (last = i; last < i + HARD_REGNO_NREGS (i, mode); last++)
1345 if (!TEST_HARD_REG_BIT (reg_class_contents[class], last))
1346 return NULL_RTX;
1347
1348 new = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno);
1349 if (new)
1350 {
1351 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg);
1352 REG_ATTRS (new) = REG_ATTRS (reg);
1353 return new;
1354 }
1355 }
1356
1357 return NULL_RTX;
1358 }
1359
1360 /* If possible, replace the register at *LOC with the oldest register
1361 in register class CLASS. Return true if successfully replaced. */
1362
1363 static bool
replace_oldest_value_reg(rtx * loc,enum reg_class class,rtx insn,struct value_data * vd)1364 replace_oldest_value_reg (rtx *loc, enum reg_class class, rtx insn,
1365 struct value_data *vd)
1366 {
1367 rtx new = find_oldest_value_reg (class, *loc, vd);
1368 if (new)
1369 {
1370 if (rtl_dump_file)
1371 fprintf (rtl_dump_file, "insn %u: replaced reg %u with %u\n",
1372 INSN_UID (insn), REGNO (*loc), REGNO (new));
1373
1374 *loc = new;
1375 return true;
1376 }
1377 return false;
1378 }
1379
1380 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1381 Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
1382 BASE_REG_CLASS depending on how the register is being considered. */
1383
1384 static bool
replace_oldest_value_addr(rtx * loc,enum reg_class class,enum machine_mode mode,rtx insn,struct value_data * vd)1385 replace_oldest_value_addr (rtx *loc, enum reg_class class,
1386 enum machine_mode mode, rtx insn,
1387 struct value_data *vd)
1388 {
1389 rtx x = *loc;
1390 RTX_CODE code = GET_CODE (x);
1391 const char *fmt;
1392 int i, j;
1393 bool changed = false;
1394
1395 switch (code)
1396 {
1397 case PLUS:
1398 {
1399 rtx orig_op0 = XEXP (x, 0);
1400 rtx orig_op1 = XEXP (x, 1);
1401 RTX_CODE code0 = GET_CODE (orig_op0);
1402 RTX_CODE code1 = GET_CODE (orig_op1);
1403 rtx op0 = orig_op0;
1404 rtx op1 = orig_op1;
1405 rtx *locI = NULL;
1406 rtx *locB = NULL;
1407
1408 if (GET_CODE (op0) == SUBREG)
1409 {
1410 op0 = SUBREG_REG (op0);
1411 code0 = GET_CODE (op0);
1412 }
1413
1414 if (GET_CODE (op1) == SUBREG)
1415 {
1416 op1 = SUBREG_REG (op1);
1417 code1 = GET_CODE (op1);
1418 }
1419
1420 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
1421 || code0 == ZERO_EXTEND || code1 == MEM)
1422 {
1423 locI = &XEXP (x, 0);
1424 locB = &XEXP (x, 1);
1425 }
1426 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
1427 || code1 == ZERO_EXTEND || code0 == MEM)
1428 {
1429 locI = &XEXP (x, 1);
1430 locB = &XEXP (x, 0);
1431 }
1432 else if (code0 == CONST_INT || code0 == CONST
1433 || code0 == SYMBOL_REF || code0 == LABEL_REF)
1434 locB = &XEXP (x, 1);
1435 else if (code1 == CONST_INT || code1 == CONST
1436 || code1 == SYMBOL_REF || code1 == LABEL_REF)
1437 locB = &XEXP (x, 0);
1438 else if (code0 == REG && code1 == REG)
1439 {
1440 int index_op;
1441
1442 if (REG_OK_FOR_INDEX_P (op0)
1443 && REG_MODE_OK_FOR_BASE_P (op1, mode))
1444 index_op = 0;
1445 else if (REG_OK_FOR_INDEX_P (op1)
1446 && REG_MODE_OK_FOR_BASE_P (op0, mode))
1447 index_op = 1;
1448 else if (REG_MODE_OK_FOR_BASE_P (op1, mode))
1449 index_op = 0;
1450 else if (REG_MODE_OK_FOR_BASE_P (op0, mode))
1451 index_op = 1;
1452 else if (REG_OK_FOR_INDEX_P (op1))
1453 index_op = 1;
1454 else
1455 index_op = 0;
1456
1457 locI = &XEXP (x, index_op);
1458 locB = &XEXP (x, !index_op);
1459 }
1460 else if (code0 == REG)
1461 {
1462 locI = &XEXP (x, 0);
1463 locB = &XEXP (x, 1);
1464 }
1465 else if (code1 == REG)
1466 {
1467 locI = &XEXP (x, 1);
1468 locB = &XEXP (x, 0);
1469 }
1470
1471 if (locI)
1472 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode,
1473 insn, vd);
1474 if (locB)
1475 changed |= replace_oldest_value_addr (locB,
1476 MODE_BASE_REG_CLASS (mode),
1477 mode, insn, vd);
1478 return changed;
1479 }
1480
1481 case POST_INC:
1482 case POST_DEC:
1483 case POST_MODIFY:
1484 case PRE_INC:
1485 case PRE_DEC:
1486 case PRE_MODIFY:
1487 return false;
1488
1489 case MEM:
1490 return replace_oldest_value_mem (x, insn, vd);
1491
1492 case REG:
1493 return replace_oldest_value_reg (loc, class, insn, vd);
1494
1495 default:
1496 break;
1497 }
1498
1499 fmt = GET_RTX_FORMAT (code);
1500 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1501 {
1502 if (fmt[i] == 'e')
1503 changed |= replace_oldest_value_addr (&XEXP (x, i), class, mode,
1504 insn, vd);
1505 else if (fmt[i] == 'E')
1506 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1507 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), class,
1508 mode, insn, vd);
1509 }
1510
1511 return changed;
1512 }
1513
1514 /* Similar to replace_oldest_value_reg, but X contains a memory. */
1515
1516 static bool
replace_oldest_value_mem(rtx x,rtx insn,struct value_data * vd)1517 replace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd)
1518 {
1519 return replace_oldest_value_addr (&XEXP (x, 0),
1520 MODE_BASE_REG_CLASS (GET_MODE (x)),
1521 GET_MODE (x), insn, vd);
1522 }
1523
1524 /* Perform the forward copy propagation on basic block BB. */
1525
1526 static bool
copyprop_hardreg_forward_1(basic_block bb,struct value_data * vd)1527 copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd)
1528 {
1529 bool changed = false;
1530 rtx insn;
1531
1532 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
1533 {
1534 int n_ops, i, alt, predicated;
1535 bool is_asm;
1536 rtx set;
1537
1538 if (! INSN_P (insn))
1539 {
1540 if (insn == BB_END (bb))
1541 break;
1542 else
1543 continue;
1544 }
1545
1546 set = single_set (insn);
1547 extract_insn (insn);
1548 if (! constrain_operands (1))
1549 fatal_insn_not_found (insn);
1550 preprocess_constraints ();
1551 alt = which_alternative;
1552 n_ops = recog_data.n_operands;
1553 is_asm = asm_noperands (PATTERN (insn)) >= 0;
1554
1555 /* Simplify the code below by rewriting things to reflect
1556 matching constraints. Also promote OP_OUT to OP_INOUT
1557 in predicated instructions. */
1558
1559 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1560 for (i = 0; i < n_ops; ++i)
1561 {
1562 int matches = recog_op_alt[i][alt].matches;
1563 if (matches >= 0)
1564 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class;
1565 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
1566 || (predicated && recog_data.operand_type[i] == OP_OUT))
1567 recog_data.operand_type[i] = OP_INOUT;
1568 }
1569
1570 /* For each earlyclobber operand, zap the value data. */
1571 for (i = 0; i < n_ops; i++)
1572 if (recog_op_alt[i][alt].earlyclobber)
1573 kill_value (recog_data.operand[i], vd);
1574
1575 /* Within asms, a clobber cannot overlap inputs or outputs.
1576 I wouldn't think this were true for regular insns, but
1577 scan_rtx treats them like that... */
1578 note_stores (PATTERN (insn), kill_clobbered_value, vd);
1579
1580 /* Kill all auto-incremented values. */
1581 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
1582 for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd);
1583
1584 /* Kill all early-clobbered operands. */
1585 for (i = 0; i < n_ops; i++)
1586 if (recog_op_alt[i][alt].earlyclobber)
1587 kill_value (recog_data.operand[i], vd);
1588
1589 /* Special-case plain move instructions, since we may well
1590 be able to do the move from a different register class. */
1591 if (set && REG_P (SET_SRC (set)))
1592 {
1593 rtx src = SET_SRC (set);
1594 unsigned int regno = REGNO (src);
1595 enum machine_mode mode = GET_MODE (src);
1596 unsigned int i;
1597 rtx new;
1598
1599 /* If we are accessing SRC in some mode other that what we
1600 set it in, make sure that the replacement is valid. */
1601 if (mode != vd->e[regno].mode)
1602 {
1603 if (HARD_REGNO_NREGS (regno, mode)
1604 > HARD_REGNO_NREGS (regno, vd->e[regno].mode))
1605 goto no_move_special_case;
1606 }
1607
1608 /* If the destination is also a register, try to find a source
1609 register in the same class. */
1610 if (REG_P (SET_DEST (set)))
1611 {
1612 new = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd);
1613 if (new && validate_change (insn, &SET_SRC (set), new, 0))
1614 {
1615 if (rtl_dump_file)
1616 fprintf (rtl_dump_file,
1617 "insn %u: replaced reg %u with %u\n",
1618 INSN_UID (insn), regno, REGNO (new));
1619 changed = true;
1620 goto did_replacement;
1621 }
1622 }
1623
1624 /* Otherwise, try all valid registers and see if its valid. */
1625 for (i = vd->e[regno].oldest_regno; i != regno;
1626 i = vd->e[i].next_regno)
1627 {
1628 new = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode,
1629 mode, i, regno);
1630 if (new != NULL_RTX)
1631 {
1632 if (validate_change (insn, &SET_SRC (set), new, 0))
1633 {
1634 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src);
1635 REG_ATTRS (new) = REG_ATTRS (src);
1636 if (rtl_dump_file)
1637 fprintf (rtl_dump_file,
1638 "insn %u: replaced reg %u with %u\n",
1639 INSN_UID (insn), regno, REGNO (new));
1640 changed = true;
1641 goto did_replacement;
1642 }
1643 }
1644 }
1645 }
1646 no_move_special_case:
1647
1648 /* For each input operand, replace a hard register with the
1649 eldest live copy that's in an appropriate register class. */
1650 for (i = 0; i < n_ops; i++)
1651 {
1652 bool replaced = false;
1653
1654 /* Don't scan match_operand here, since we've no reg class
1655 information to pass down. Any operands that we could
1656 substitute in will be represented elsewhere. */
1657 if (recog_data.constraints[i][0] == '\0')
1658 continue;
1659
1660 /* Don't replace in asms intentionally referencing hard regs. */
1661 if (is_asm && GET_CODE (recog_data.operand[i]) == REG
1662 && (REGNO (recog_data.operand[i])
1663 == ORIGINAL_REGNO (recog_data.operand[i])))
1664 continue;
1665
1666 if (recog_data.operand_type[i] == OP_IN)
1667 {
1668 if (recog_op_alt[i][alt].is_address)
1669 replaced
1670 = replace_oldest_value_addr (recog_data.operand_loc[i],
1671 recog_op_alt[i][alt].class,
1672 VOIDmode, insn, vd);
1673 else if (REG_P (recog_data.operand[i]))
1674 replaced
1675 = replace_oldest_value_reg (recog_data.operand_loc[i],
1676 recog_op_alt[i][alt].class,
1677 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);
1681 }
1682 else if (GET_CODE (recog_data.operand[i]) == MEM)
1683 replaced = replace_oldest_value_mem (recog_data.operand[i],
1684 insn, vd);
1685
1686 /* If we performed any replacement, update match_dups. */
1687 if (replaced)
1688 {
1689 int j;
1690 rtx new;
1691
1692 changed = true;
1693
1694 new = *recog_data.operand_loc[i];
1695 recog_data.operand[i] = new;
1696 for (j = 0; j < recog_data.n_dups; j++)
1697 if (recog_data.dup_num[j] == i)
1698 *recog_data.dup_loc[j] = new;
1699 }
1700 }
1701
1702 did_replacement:
1703 /* Clobber call-clobbered registers. */
1704 if (GET_CODE (insn) == CALL_INSN)
1705 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1706 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1707 kill_value_regno (i, vd);
1708
1709 /* Notice stores. */
1710 note_stores (PATTERN (insn), kill_set_value, vd);
1711
1712 /* Notice copies. */
1713 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
1714 copy_value (SET_DEST (set), SET_SRC (set), vd);
1715
1716 if (insn == BB_END (bb))
1717 break;
1718 }
1719
1720 return changed;
1721 }
1722
1723 /* Main entry point for the forward copy propagation optimization. */
1724
1725 void
copyprop_hardreg_forward(void)1726 copyprop_hardreg_forward (void)
1727 {
1728 struct value_data *all_vd;
1729 bool need_refresh;
1730 basic_block bb, bbp = 0;
1731
1732 need_refresh = false;
1733
1734 all_vd = xmalloc (sizeof (struct value_data) * last_basic_block);
1735
1736 FOR_EACH_BB (bb)
1737 {
1738 /* If a block has a single predecessor, that we've already
1739 processed, begin with the value data that was live at
1740 the end of the predecessor block. */
1741 /* ??? Ought to use more intelligent queuing of blocks. */
1742 if (bb->pred)
1743 for (bbp = bb; bbp && bbp != bb->pred->src; bbp = bbp->prev_bb);
1744 if (bb->pred
1745 && ! bb->pred->pred_next
1746 && ! (bb->pred->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1747 && bb->pred->src != ENTRY_BLOCK_PTR
1748 && bbp)
1749 all_vd[bb->index] = all_vd[bb->pred->src->index];
1750 else
1751 init_value_data (all_vd + bb->index);
1752
1753 if (copyprop_hardreg_forward_1 (bb, all_vd + bb->index))
1754 need_refresh = true;
1755 }
1756
1757 if (need_refresh)
1758 {
1759 if (rtl_dump_file)
1760 fputs ("\n\n", rtl_dump_file);
1761
1762 /* ??? Irritatingly, delete_noop_moves does not take a set of blocks
1763 to scan, so we have to do a life update with no initial set of
1764 blocks Just In Case. */
1765 delete_noop_moves (get_insns ());
1766 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
1767 PROP_DEATH_NOTES
1768 | PROP_SCAN_DEAD_CODE
1769 | PROP_KILL_DEAD_CODE);
1770 }
1771
1772 free (all_vd);
1773 }
1774
1775 /* Dump the value chain data to stderr. */
1776
1777 void
debug_value_data(struct value_data * vd)1778 debug_value_data (struct value_data *vd)
1779 {
1780 HARD_REG_SET set;
1781 unsigned int i, j;
1782
1783 CLEAR_HARD_REG_SET (set);
1784
1785 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1786 if (vd->e[i].oldest_regno == i)
1787 {
1788 if (vd->e[i].mode == VOIDmode)
1789 {
1790 if (vd->e[i].next_regno != INVALID_REGNUM)
1791 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n",
1792 i, vd->e[i].next_regno);
1793 continue;
1794 }
1795
1796 SET_HARD_REG_BIT (set, i);
1797 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode));
1798
1799 for (j = vd->e[i].next_regno;
1800 j != INVALID_REGNUM;
1801 j = vd->e[j].next_regno)
1802 {
1803 if (TEST_HARD_REG_BIT (set, j))
1804 {
1805 fprintf (stderr, "[%u] Loop in regno chain\n", j);
1806 return;
1807 }
1808
1809 if (vd->e[j].oldest_regno != i)
1810 {
1811 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n",
1812 j, vd->e[j].oldest_regno);
1813 return;
1814 }
1815 SET_HARD_REG_BIT (set, j);
1816 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode));
1817 }
1818 fputc ('\n', stderr);
1819 }
1820
1821 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1822 if (! TEST_HARD_REG_BIT (set, i)
1823 && (vd->e[i].mode != VOIDmode
1824 || vd->e[i].oldest_regno != i
1825 || vd->e[i].next_regno != INVALID_REGNUM))
1826 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n",
1827 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1828 vd->e[i].next_regno);
1829 }
1830
1831 #ifdef ENABLE_CHECKING
1832 static void
validate_value_data(struct value_data * vd)1833 validate_value_data (struct value_data *vd)
1834 {
1835 HARD_REG_SET set;
1836 unsigned int i, j;
1837
1838 CLEAR_HARD_REG_SET (set);
1839
1840 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1841 if (vd->e[i].oldest_regno == i)
1842 {
1843 if (vd->e[i].mode == VOIDmode)
1844 {
1845 if (vd->e[i].next_regno != INVALID_REGNUM)
1846 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1847 i, vd->e[i].next_regno);
1848 continue;
1849 }
1850
1851 SET_HARD_REG_BIT (set, i);
1852
1853 for (j = vd->e[i].next_regno;
1854 j != INVALID_REGNUM;
1855 j = vd->e[j].next_regno)
1856 {
1857 if (TEST_HARD_REG_BIT (set, j))
1858 internal_error ("validate_value_data: Loop in regno chain (%u)",
1859 j);
1860 if (vd->e[j].oldest_regno != i)
1861 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1862 j, vd->e[j].oldest_regno);
1863
1864 SET_HARD_REG_BIT (set, j);
1865 }
1866 }
1867
1868 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1869 if (! TEST_HARD_REG_BIT (set, i)
1870 && (vd->e[i].mode != VOIDmode
1871 || vd->e[i].oldest_regno != i
1872 || vd->e[i].next_regno != INVALID_REGNUM))
1873 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1874 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1875 vd->e[i].next_regno);
1876 }
1877 #endif
1878