Daily bump.
[official-gcc.git] / gcc / regmove.c
blob1ce8a7ed285e10c09faa01262115cd595d2f9b5a
1 /* Move registers around to reduce number of move instructions needed.
2 Copyright (C) 1987-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
21 /* This module makes some simple RTL code transformations which
22 improve the subsequent register allocation. */
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "tm.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "insn-config.h"
31 #include "recog.h"
32 #include "target.h"
33 #include "regs.h"
34 #include "hard-reg-set.h"
35 #include "flags.h"
36 #include "function.h"
37 #include "expr.h"
38 #include "basic-block.h"
39 #include "except.h"
40 #include "diagnostic-core.h"
41 #include "reload.h"
42 #include "tree-pass.h"
43 #include "df.h"
44 #include "ira.h"
46 static int optimize_reg_copy_1 (rtx, rtx, rtx);
47 static void optimize_reg_copy_2 (rtx, rtx, rtx);
48 static void optimize_reg_copy_3 (rtx, rtx, rtx);
49 static void copy_src_to_dest (rtx, rtx, rtx);
51 enum match_use
53 READ,
54 WRITE,
55 READWRITE
58 struct match {
59 int with[MAX_RECOG_OPERANDS];
60 enum match_use use[MAX_RECOG_OPERANDS];
61 int commutative[MAX_RECOG_OPERANDS];
62 int early_clobber[MAX_RECOG_OPERANDS];
65 static int find_matches (rtx, struct match *);
66 static int fixup_match_2 (rtx, rtx, rtx, rtx);
68 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
69 causing too much register allocation problems. */
70 static int
71 regclass_compatible_p (reg_class_t class0, reg_class_t class1)
73 return (class0 == class1
74 || (reg_class_subset_p (class0, class1)
75 && ! targetm.class_likely_spilled_p (class0))
76 || (reg_class_subset_p (class1, class0)
77 && ! targetm.class_likely_spilled_p (class1)));
81 #ifdef AUTO_INC_DEC
83 /* Find the place in the rtx X where REG is used as a memory address.
84 Return the MEM rtx that so uses it.
85 If PLUSCONST is nonzero, search instead for a memory address equivalent to
86 (plus REG (const_int PLUSCONST)).
88 If such an address does not appear, return 0.
89 If REG appears more than once, or is used other than in such an address,
90 return (rtx) 1. */
92 static rtx
93 find_use_as_address (rtx x, rtx reg, HOST_WIDE_INT plusconst)
95 enum rtx_code code = GET_CODE (x);
96 const char * const fmt = GET_RTX_FORMAT (code);
97 int i;
98 rtx value = 0;
99 rtx tem;
101 if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
102 return x;
104 if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
105 && XEXP (XEXP (x, 0), 0) == reg
106 && CONST_INT_P (XEXP (XEXP (x, 0), 1))
107 && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
108 return x;
110 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
112 /* If REG occurs inside a MEM used in a bit-field reference,
113 that is unacceptable. */
114 if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
115 return (rtx) (size_t) 1;
118 if (x == reg)
119 return (rtx) (size_t) 1;
121 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
123 if (fmt[i] == 'e')
125 tem = find_use_as_address (XEXP (x, i), reg, plusconst);
126 if (value == 0)
127 value = tem;
128 else if (tem != 0)
129 return (rtx) (size_t) 1;
131 else if (fmt[i] == 'E')
133 int j;
134 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
136 tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
137 if (value == 0)
138 value = tem;
139 else if (tem != 0)
140 return (rtx) (size_t) 1;
145 return value;
149 /* INC_INSN is an instruction that adds INCREMENT to REG.
150 Try to fold INC_INSN as a post/pre in/decrement into INSN.
151 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
152 Return nonzero for success. */
153 static int
154 try_auto_increment (rtx insn, rtx inc_insn, rtx inc_insn_set, rtx reg,
155 HOST_WIDE_INT increment, int pre)
157 enum rtx_code inc_code;
159 rtx pset = single_set (insn);
160 if (pset)
162 /* Can't use the size of SET_SRC, we might have something like
163 (sign_extend:SI (mem:QI ... */
164 rtx use = find_use_as_address (pset, reg, 0);
165 if (use != 0 && use != (rtx) (size_t) 1)
167 int size = GET_MODE_SIZE (GET_MODE (use));
168 if (0
169 || (HAVE_POST_INCREMENT
170 && pre == 0 && (inc_code = POST_INC, increment == size))
171 || (HAVE_PRE_INCREMENT
172 && pre == 1 && (inc_code = PRE_INC, increment == size))
173 || (HAVE_POST_DECREMENT
174 && pre == 0 && (inc_code = POST_DEC, increment == -size))
175 || (HAVE_PRE_DECREMENT
176 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
179 if (inc_insn_set)
180 validate_change
181 (inc_insn,
182 &SET_SRC (inc_insn_set),
183 XEXP (SET_SRC (inc_insn_set), 0), 1);
184 validate_change (insn, &XEXP (use, 0),
185 gen_rtx_fmt_e (inc_code,
186 GET_MODE (XEXP (use, 0)), reg),
188 if (apply_change_group ())
190 /* If there is a REG_DEAD note on this insn, we must
191 change this not to REG_UNUSED meaning that the register
192 is set, but the value is dead. Failure to do so will
193 result in sched1 dying -- when it recomputes lifetime
194 information, the number of REG_DEAD notes will have
195 changed. */
196 rtx note = find_reg_note (insn, REG_DEAD, reg);
197 if (note)
198 PUT_REG_NOTE_KIND (note, REG_UNUSED);
200 add_reg_note (insn, REG_INC, reg);
202 if (! inc_insn_set)
203 delete_insn (inc_insn);
204 return 1;
209 return 0;
211 #endif
214 static int *regno_src_regno;
216 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
217 in INSN.
219 Search forward to see if SRC dies before either it or DEST is modified,
220 but don't scan past the end of a basic block. If so, we can replace SRC
221 with DEST and let SRC die in INSN.
223 This will reduce the number of registers live in that range and may enable
224 DEST to be tied to SRC, thus often saving one register in addition to a
225 register-register copy. */
227 static int
228 optimize_reg_copy_1 (rtx insn, rtx dest, rtx src)
230 rtx p, q;
231 rtx note;
232 rtx dest_death = 0;
233 int sregno = REGNO (src);
234 int dregno = REGNO (dest);
235 basic_block bb = BLOCK_FOR_INSN (insn);
237 /* We don't want to mess with hard regs if register classes are small. */
238 if (sregno == dregno
239 || (targetm.small_register_classes_for_mode_p (GET_MODE (src))
240 && (sregno < FIRST_PSEUDO_REGISTER
241 || dregno < FIRST_PSEUDO_REGISTER))
242 /* We don't see all updates to SP if they are in an auto-inc memory
243 reference, so we must disallow this optimization on them. */
244 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
245 return 0;
247 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
249 if (! INSN_P (p))
250 continue;
251 if (BLOCK_FOR_INSN (p) != bb)
252 break;
254 if (reg_set_p (src, p) || reg_set_p (dest, p)
255 /* If SRC is an asm-declared register, it must not be replaced
256 in any asm. Unfortunately, the REG_EXPR tree for the asm
257 variable may be absent in the SRC rtx, so we can't check the
258 actual register declaration easily (the asm operand will have
259 it, though). To avoid complicating the test for a rare case,
260 we just don't perform register replacement for a hard reg
261 mentioned in an asm. */
262 || (sregno < FIRST_PSEUDO_REGISTER
263 && asm_noperands (PATTERN (p)) >= 0
264 && reg_overlap_mentioned_p (src, PATTERN (p)))
265 /* Don't change hard registers used by a call. */
266 || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
267 && find_reg_fusage (p, USE, src))
268 /* Don't change a USE of a register. */
269 || (GET_CODE (PATTERN (p)) == USE
270 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
271 break;
273 /* See if all of SRC dies in P. This test is slightly more
274 conservative than it needs to be. */
275 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
276 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
278 int failed = 0;
279 int d_length = 0;
280 int s_length = 0;
281 int d_n_calls = 0;
282 int s_n_calls = 0;
283 int s_freq_calls = 0;
284 int d_freq_calls = 0;
286 /* We can do the optimization. Scan forward from INSN again,
287 replacing regs as we go. Set FAILED if a replacement can't
288 be done. In that case, we can't move the death note for SRC.
289 This should be rare. */
291 /* Set to stop at next insn. */
292 for (q = next_real_insn (insn);
293 q != next_real_insn (p);
294 q = next_real_insn (q))
296 if (reg_overlap_mentioned_p (src, PATTERN (q)))
298 /* If SRC is a hard register, we might miss some
299 overlapping registers with validate_replace_rtx,
300 so we would have to undo it. We can't if DEST is
301 present in the insn, so fail in that combination
302 of cases. */
303 if (sregno < FIRST_PSEUDO_REGISTER
304 && reg_mentioned_p (dest, PATTERN (q)))
305 failed = 1;
307 /* Attempt to replace all uses. */
308 else if (!validate_replace_rtx (src, dest, q))
309 failed = 1;
311 /* If this succeeded, but some part of the register
312 is still present, undo the replacement. */
313 else if (sregno < FIRST_PSEUDO_REGISTER
314 && reg_overlap_mentioned_p (src, PATTERN (q)))
316 validate_replace_rtx (dest, src, q);
317 failed = 1;
321 /* For SREGNO, count the total number of insns scanned.
322 For DREGNO, count the total number of insns scanned after
323 passing the death note for DREGNO. */
324 if (!DEBUG_INSN_P (p))
326 s_length++;
327 if (dest_death)
328 d_length++;
331 /* If the insn in which SRC dies is a CALL_INSN, don't count it
332 as a call that has been crossed. Otherwise, count it. */
333 if (q != p && CALL_P (q))
335 /* Similarly, total calls for SREGNO, total calls beyond
336 the death note for DREGNO. */
337 s_n_calls++;
338 s_freq_calls += REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q));
339 if (dest_death)
341 d_n_calls++;
342 d_freq_calls += REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q));
346 /* If DEST dies here, remove the death note and save it for
347 later. Make sure ALL of DEST dies here; again, this is
348 overly conservative. */
349 if (dest_death == 0
350 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
352 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
353 failed = 1, dest_death = 0;
354 else
355 remove_note (q, dest_death);
359 if (! failed)
361 /* These counters need to be updated if and only if we are
362 going to move the REG_DEAD note. */
363 if (sregno >= FIRST_PSEUDO_REGISTER)
365 if (REG_LIVE_LENGTH (sregno) >= 0)
367 REG_LIVE_LENGTH (sregno) -= s_length;
368 /* REG_LIVE_LENGTH is only an approximation after
369 combine if sched is not run, so make sure that we
370 still have a reasonable value. */
371 if (REG_LIVE_LENGTH (sregno) < 2)
372 REG_LIVE_LENGTH (sregno) = 2;
375 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
376 REG_FREQ_CALLS_CROSSED (sregno) -= s_freq_calls;
379 /* Move death note of SRC from P to INSN. */
380 remove_note (p, note);
381 XEXP (note, 1) = REG_NOTES (insn);
382 REG_NOTES (insn) = note;
385 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
386 if (! dest_death
387 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
389 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
390 remove_note (insn, dest_death);
393 /* Put death note of DEST on P if we saw it die. */
394 if (dest_death)
396 XEXP (dest_death, 1) = REG_NOTES (p);
397 REG_NOTES (p) = dest_death;
399 if (dregno >= FIRST_PSEUDO_REGISTER)
401 /* If and only if we are moving the death note for DREGNO,
402 then we need to update its counters. */
403 if (REG_LIVE_LENGTH (dregno) >= 0)
404 REG_LIVE_LENGTH (dregno) += d_length;
405 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
406 REG_FREQ_CALLS_CROSSED (dregno) += d_freq_calls;
410 return ! failed;
413 /* If SRC is a hard register which is set or killed in some other
414 way, we can't do this optimization. */
415 else if (sregno < FIRST_PSEUDO_REGISTER
416 && dead_or_set_p (p, src))
417 break;
419 return 0;
422 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
423 a sequence of insns that modify DEST followed by an insn that sets
424 SRC to DEST in which DEST dies, with no prior modification of DEST.
425 (There is no need to check if the insns in between actually modify
426 DEST. We should not have cases where DEST is not modified, but
427 the optimization is safe if no such modification is detected.)
428 In that case, we can replace all uses of DEST, starting with INSN and
429 ending with the set of SRC to DEST, with SRC. We do not do this
430 optimization if a CALL_INSN is crossed unless SRC already crosses a
431 call or if DEST dies before the copy back to SRC.
433 It is assumed that DEST and SRC are pseudos; it is too complicated to do
434 this for hard registers since the substitutions we may make might fail. */
436 static void
437 optimize_reg_copy_2 (rtx insn, rtx dest, rtx src)
439 rtx p, q;
440 rtx set;
441 int sregno = REGNO (src);
442 int dregno = REGNO (dest);
443 basic_block bb = BLOCK_FOR_INSN (insn);
445 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
447 if (! INSN_P (p))
448 continue;
449 if (BLOCK_FOR_INSN (p) != bb)
450 break;
452 set = single_set (p);
453 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
454 && find_reg_note (p, REG_DEAD, dest))
456 /* We can do the optimization. Scan forward from INSN again,
457 replacing regs as we go. */
459 /* Set to stop at next insn. */
460 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
461 if (INSN_P (q))
463 if (reg_mentioned_p (dest, PATTERN (q)))
465 rtx note;
467 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
468 note = FIND_REG_INC_NOTE (q, dest);
469 if (note)
471 remove_note (q, note);
472 add_reg_note (q, REG_INC, src);
474 df_insn_rescan (q);
477 if (CALL_P (q))
479 int freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q));
480 REG_N_CALLS_CROSSED (dregno)--;
481 REG_N_CALLS_CROSSED (sregno)++;
482 REG_FREQ_CALLS_CROSSED (dregno) -= freq;
483 REG_FREQ_CALLS_CROSSED (sregno) += freq;
487 remove_note (p, find_reg_note (p, REG_DEAD, dest));
488 REG_N_DEATHS (dregno)--;
489 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
490 REG_N_DEATHS (sregno)--;
491 return;
494 if (reg_set_p (src, p)
495 || find_reg_note (p, REG_DEAD, dest)
496 || (CALL_P (p) && REG_N_CALLS_CROSSED (sregno) == 0))
497 break;
501 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
502 Look if SRC dies there, and if it is only set once, by loading
503 it from memory. If so, try to incorporate the zero/sign extension
504 into the memory read, change SRC to the mode of DEST, and alter
505 the remaining accesses to use the appropriate SUBREG. This allows
506 SRC and DEST to be tied later. */
507 static void
508 optimize_reg_copy_3 (rtx insn, rtx dest, rtx src)
510 rtx src_reg = XEXP (src, 0);
511 int src_no = REGNO (src_reg);
512 int dst_no = REGNO (dest);
513 rtx p, set, set_insn;
514 enum machine_mode old_mode;
515 basic_block bb = BLOCK_FOR_INSN (insn);
517 if (src_no < FIRST_PSEUDO_REGISTER
518 || dst_no < FIRST_PSEUDO_REGISTER
519 || ! find_reg_note (insn, REG_DEAD, src_reg)
520 || REG_N_DEATHS (src_no) != 1
521 || REG_N_SETS (src_no) != 1)
522 return;
524 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
525 if (INSN_P (p) && BLOCK_FOR_INSN (p) != bb)
526 break;
528 if (! p || BLOCK_FOR_INSN (p) != bb)
529 return;
531 if (! (set = single_set (p))
532 || !MEM_P (SET_SRC (set))
533 /* If there's a REG_EQUIV note, this must be an insn that loads an
534 argument. Prefer keeping the note over doing this optimization. */
535 || find_reg_note (p, REG_EQUIV, NULL_RTX)
536 || SET_DEST (set) != src_reg)
537 return;
539 /* Be conservative: although this optimization is also valid for
540 volatile memory references, that could cause trouble in later passes. */
541 if (MEM_VOLATILE_P (SET_SRC (set)))
542 return;
544 /* Do not use a SUBREG to truncate from one mode to another if truncation
545 is not a nop. */
546 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
547 && !TRULY_NOOP_TRUNCATION_MODES_P (GET_MODE (src), GET_MODE (src_reg)))
548 return;
550 set_insn = p;
551 old_mode = GET_MODE (src_reg);
552 PUT_MODE (src_reg, GET_MODE (src));
553 XEXP (src, 0) = SET_SRC (set);
555 /* Include this change in the group so that it's easily undone if
556 one of the changes in the group is invalid. */
557 validate_change (p, &SET_SRC (set), src, 1);
559 /* Now walk forward making additional replacements. We want to be able
560 to undo all the changes if a later substitution fails. */
561 while (p = NEXT_INSN (p), p != insn)
563 if (! INSN_P (p))
564 continue;
566 /* Make a tentative change. */
567 validate_replace_rtx_group (src_reg,
568 gen_lowpart_SUBREG (old_mode, src_reg),
572 validate_replace_rtx_group (src, src_reg, insn);
574 /* Now see if all the changes are valid. */
575 if (! apply_change_group ())
577 /* One or more changes were no good. Back out everything. */
578 PUT_MODE (src_reg, old_mode);
579 XEXP (src, 0) = src_reg;
581 else
583 rtx note = find_reg_note (set_insn, REG_EQUAL, NULL_RTX);
584 if (note)
586 if (rtx_equal_p (XEXP (note, 0), XEXP (src, 0)))
588 XEXP (note, 0)
589 = gen_rtx_fmt_e (GET_CODE (src), GET_MODE (src),
590 XEXP (note, 0));
591 df_notes_rescan (set_insn);
593 else
594 remove_note (set_insn, note);
600 /* If we were not able to update the users of src to use dest directly, try
601 instead moving the value to dest directly before the operation. */
603 static void
604 copy_src_to_dest (rtx insn, rtx src, rtx dest)
606 rtx seq;
607 rtx link;
608 rtx next;
609 rtx set;
610 rtx move_insn;
611 rtx *p_insn_notes;
612 rtx *p_move_notes;
613 int src_regno;
614 int dest_regno;
616 /* A REG_LIVE_LENGTH of -1 indicates the register must not go into
617 a hard register, e.g. because it crosses as setjmp. See the
618 comment in regstat.c:regstat_bb_compute_ri. Don't try to apply
619 any transformations to such regs. */
621 if (REG_P (src)
622 && REG_LIVE_LENGTH (REGNO (src)) > 0
623 && REG_P (dest)
624 && REG_LIVE_LENGTH (REGNO (dest)) > 0
625 && (set = single_set (insn)) != NULL_RTX
626 && !reg_mentioned_p (dest, SET_SRC (set))
627 && GET_MODE (src) == GET_MODE (dest))
629 int old_num_regs = reg_rtx_no;
631 /* Generate the src->dest move. */
632 start_sequence ();
633 emit_move_insn (dest, src);
634 seq = get_insns ();
635 end_sequence ();
636 /* If this sequence uses new registers, we may not use it. */
637 if (old_num_regs != reg_rtx_no
638 || ! validate_replace_rtx (src, dest, insn))
640 /* We have to restore reg_rtx_no to its old value, lest
641 recompute_reg_usage will try to compute the usage of the
642 new regs, yet reg_n_info is not valid for them. */
643 reg_rtx_no = old_num_regs;
644 return;
646 emit_insn_before (seq, insn);
647 move_insn = PREV_INSN (insn);
648 p_move_notes = &REG_NOTES (move_insn);
649 p_insn_notes = &REG_NOTES (insn);
651 /* Move any notes mentioning src to the move instruction. */
652 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
654 next = XEXP (link, 1);
655 if (XEXP (link, 0) == src)
657 *p_move_notes = link;
658 p_move_notes = &XEXP (link, 1);
660 else
662 *p_insn_notes = link;
663 p_insn_notes = &XEXP (link, 1);
667 *p_move_notes = NULL_RTX;
668 *p_insn_notes = NULL_RTX;
670 /* Update the various register tables. */
671 dest_regno = REGNO (dest);
672 INC_REG_N_SETS (dest_regno, 1);
673 REG_LIVE_LENGTH (dest_regno)++;
674 src_regno = REGNO (src);
675 if (! find_reg_note (move_insn, REG_DEAD, src))
676 REG_LIVE_LENGTH (src_regno)++;
680 /* reg_set_in_bb[REGNO] points to basic block iff the register is set
681 only once in the given block and has REG_EQUAL note. */
683 static basic_block *reg_set_in_bb;
685 /* Size of reg_set_in_bb array. */
686 static unsigned int max_reg_computed;
689 /* Return whether REG is set in only one location, and is set to a
690 constant, but is set in a different basic block from INSN (an
691 instructions which uses REG). In this case REG is equivalent to a
692 constant, and we don't want to break that equivalence, because that
693 may increase register pressure and make reload harder. If REG is
694 set in the same basic block as INSN, we don't worry about it,
695 because we'll probably need a register anyhow (??? but what if REG
696 is used in a different basic block as well as this one?). */
698 static bool
699 reg_is_remote_constant_p (rtx reg, rtx insn)
701 basic_block bb;
702 rtx p;
703 int max;
705 if (!reg_set_in_bb)
707 max_reg_computed = max = max_reg_num ();
708 reg_set_in_bb = XCNEWVEC (basic_block, max);
710 FOR_EACH_BB (bb)
711 FOR_BB_INSNS (bb, p)
713 rtx s;
715 if (!INSN_P (p))
716 continue;
717 s = single_set (p);
718 /* This is the instruction which sets REG. If there is a
719 REG_EQUAL note, then REG is equivalent to a constant. */
720 if (s != 0
721 && REG_P (SET_DEST (s))
722 && REG_N_SETS (REGNO (SET_DEST (s))) == 1
723 && find_reg_note (p, REG_EQUAL, NULL_RTX))
724 reg_set_in_bb[REGNO (SET_DEST (s))] = bb;
728 gcc_assert (REGNO (reg) < max_reg_computed);
729 if (reg_set_in_bb[REGNO (reg)] == NULL)
730 return false;
731 return (reg_set_in_bb[REGNO (reg)] != BLOCK_FOR_INSN (insn));
734 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
735 another add immediate instruction with the same source and dest registers,
736 and if we find one, we change INSN to an increment, and return 1. If
737 no changes are made, we return 0.
739 This changes
740 (set (reg100) (plus reg1 offset1))
742 (set (reg100) (plus reg1 offset2))
744 (set (reg100) (plus reg1 offset1))
746 (set (reg100) (plus reg100 offset2-offset1)) */
748 /* ??? What does this comment mean? */
749 /* cse disrupts preincrement / postdecrement sequences when it finds a
750 hard register as ultimate source, like the frame pointer. */
752 static int
753 fixup_match_2 (rtx insn, rtx dst, rtx src, rtx offset)
755 rtx p, dst_death = 0;
756 int length, num_calls = 0, freq_calls = 0;
757 basic_block bb = BLOCK_FOR_INSN (insn);
759 /* If SRC dies in INSN, we'd have to move the death note. This is
760 considered to be very unlikely, so we just skip the optimization
761 in this case. */
762 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
763 return 0;
765 /* Scan backward to find the first instruction that sets DST. */
767 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
769 rtx pset;
771 if (! INSN_P (p))
772 continue;
773 if (BLOCK_FOR_INSN (p) != bb)
774 break;
776 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
777 dst_death = p;
778 if (! dst_death && !DEBUG_INSN_P (p))
779 length++;
781 pset = single_set (p);
782 if (pset && SET_DEST (pset) == dst
783 && GET_CODE (SET_SRC (pset)) == PLUS
784 && XEXP (SET_SRC (pset), 0) == src
785 && CONST_INT_P (XEXP (SET_SRC (pset), 1)))
787 HOST_WIDE_INT newconst
788 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
789 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
791 if (add && validate_change (insn, &PATTERN (insn), add, 0))
793 /* Remove the death note for DST from DST_DEATH. */
794 if (dst_death)
796 remove_death (REGNO (dst), dst_death);
797 REG_LIVE_LENGTH (REGNO (dst)) += length;
798 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
799 REG_FREQ_CALLS_CROSSED (REGNO (dst)) += freq_calls;
802 if (dump_file)
803 fprintf (dump_file,
804 "Fixed operand of insn %d.\n",
805 INSN_UID (insn));
807 #ifdef AUTO_INC_DEC
808 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
810 if (! INSN_P (p))
811 continue;
812 if (BLOCK_FOR_INSN (p) != bb)
813 break;
814 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
816 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
817 return 1;
818 break;
821 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
823 if (! INSN_P (p))
824 continue;
825 if (BLOCK_FOR_INSN (p) != bb)
826 break;
827 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
829 try_auto_increment (p, insn, 0, dst, newconst, 1);
830 break;
833 #endif
834 return 1;
838 if (reg_set_p (dst, PATTERN (p)))
839 break;
841 /* If we have passed a call instruction, and the
842 pseudo-reg SRC is not already live across a call,
843 then don't perform the optimization. */
844 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
845 hard regs are clobbered. Thus, we only use it for src for
846 non-call insns. */
847 if (CALL_P (p))
849 if (! dst_death)
851 num_calls++;
852 freq_calls += REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p));
855 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
856 break;
858 if ((HARD_REGISTER_P (dst) && call_used_regs [REGNO (dst)])
859 || find_reg_fusage (p, CLOBBER, dst))
860 break;
862 else if (reg_set_p (src, PATTERN (p)))
863 break;
866 return 0;
869 /* A forward pass. Replace output operands with input operands. */
871 static void
872 regmove_forward_pass (void)
874 basic_block bb;
875 rtx insn;
877 if (! flag_expensive_optimizations)
878 return;
880 if (dump_file)
881 fprintf (dump_file, "Starting forward pass...\n");
883 FOR_EACH_BB (bb)
885 FOR_BB_INSNS (bb, insn)
887 rtx set = single_set (insn);
888 if (! set)
889 continue;
891 if ((GET_CODE (SET_SRC (set)) == SIGN_EXTEND
892 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
893 && REG_P (XEXP (SET_SRC (set), 0))
894 && REG_P (SET_DEST (set)))
895 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
897 if (REG_P (SET_SRC (set))
898 && REG_P (SET_DEST (set)))
900 /* If this is a register-register copy where SRC is not dead,
901 see if we can optimize it. If this optimization succeeds,
902 it will become a copy where SRC is dead. */
903 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
904 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
905 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
907 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
908 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
909 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
910 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
911 && SET_SRC (set) != SET_DEST (set))
913 int srcregno = REGNO (SET_SRC (set));
914 if (regno_src_regno[srcregno] >= 0)
915 srcregno = regno_src_regno[srcregno];
916 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
924 /* A backward pass. Replace input operands with output operands. */
926 static void
927 regmove_backward_pass (void)
929 basic_block bb;
930 rtx insn, prev;
932 if (dump_file)
933 fprintf (dump_file, "Starting backward pass...\n");
935 FOR_EACH_BB_REVERSE (bb)
937 /* ??? Use the safe iterator because fixup_match_2 can remove
938 insns via try_auto_increment. */
939 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)
941 struct match match;
942 rtx copy_src, copy_dst;
943 int op_no, match_no;
944 int success = 0;
946 if (! INSN_P (insn))
947 continue;
949 if (! find_matches (insn, &match))
950 continue;
952 /* Now scan through the operands looking for a destination operand
953 which is supposed to match a source operand.
954 Then scan backward for an instruction which sets the source
955 operand. If safe, then replace the source operand with the
956 dest operand in both instructions. */
958 copy_src = NULL_RTX;
959 copy_dst = NULL_RTX;
960 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
962 rtx set, p, src, dst;
963 rtx src_note, dst_note;
964 int num_calls = 0, freq_calls = 0;
965 enum reg_class src_class, dst_class;
966 int length;
968 match_no = match.with[op_no];
970 /* Nothing to do if the two operands aren't supposed to match. */
971 if (match_no < 0)
972 continue;
974 dst = recog_data.operand[match_no];
975 src = recog_data.operand[op_no];
977 if (!REG_P (src))
978 continue;
980 if (!REG_P (dst)
981 || REGNO (dst) < FIRST_PSEUDO_REGISTER
982 || REG_LIVE_LENGTH (REGNO (dst)) < 0
983 || GET_MODE (src) != GET_MODE (dst))
984 continue;
986 /* If the operands already match, then there is nothing to do. */
987 if (operands_match_p (src, dst))
988 continue;
990 if (match.commutative[op_no] >= 0)
992 rtx comm = recog_data.operand[match.commutative[op_no]];
993 if (operands_match_p (comm, dst))
994 continue;
997 set = single_set (insn);
998 if (! set)
999 continue;
1001 /* Note that single_set ignores parts of a parallel set for
1002 which one of the destinations is REG_UNUSED. We can't
1003 handle that here, since we can wind up rewriting things
1004 such that a single register is set twice within a single
1005 parallel. */
1006 if (reg_set_p (src, insn))
1007 continue;
1009 /* match_no/dst must be a write-only operand, and
1010 operand_operand/src must be a read-only operand. */
1011 if (match.use[op_no] != READ
1012 || match.use[match_no] != WRITE)
1013 continue;
1015 if (match.early_clobber[match_no]
1016 && count_occurrences (PATTERN (insn), src, 0) > 1)
1017 continue;
1019 /* Make sure match_no is the destination. */
1020 if (recog_data.operand[match_no] != SET_DEST (set))
1021 continue;
1023 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1025 if (GET_CODE (SET_SRC (set)) == PLUS
1026 && CONST_INT_P (XEXP (SET_SRC (set), 1))
1027 && XEXP (SET_SRC (set), 0) == src
1028 && fixup_match_2 (insn, dst, src,
1029 XEXP (SET_SRC (set), 1)))
1030 break;
1031 continue;
1033 src_class = reg_preferred_class (REGNO (src));
1034 dst_class = reg_preferred_class (REGNO (dst));
1036 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1038 /* We used to force the copy here like in other cases, but
1039 it produces worse code, as it eliminates no copy
1040 instructions and the copy emitted will be produced by
1041 reload anyway. On patterns with multiple alternatives,
1042 there may be better solution available.
1044 In particular this change produced slower code for numeric
1045 i387 programs. */
1047 continue;
1050 if (! regclass_compatible_p (src_class, dst_class))
1052 if (!copy_src)
1054 copy_src = src;
1055 copy_dst = dst;
1057 continue;
1060 /* Can not modify an earlier insn to set dst if this insn
1061 uses an old value in the source. */
1062 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1064 if (!copy_src)
1066 copy_src = src;
1067 copy_dst = dst;
1069 continue;
1072 /* If src is set once in a different basic block,
1073 and is set equal to a constant, then do not use
1074 it for this optimization, as this would make it
1075 no longer equivalent to a constant. */
1077 if (reg_is_remote_constant_p (src, insn))
1079 if (!copy_src)
1081 copy_src = src;
1082 copy_dst = dst;
1084 continue;
1088 if (dump_file)
1089 fprintf (dump_file,
1090 "Could fix operand %d of insn %d matching operand %d.\n",
1091 op_no, INSN_UID (insn), match_no);
1093 /* Scan backward to find the first instruction that uses
1094 the input operand. If the operand is set here, then
1095 replace it in both instructions with match_no. */
1097 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1099 rtx pset;
1101 if (! INSN_P (p))
1102 continue;
1103 if (BLOCK_FOR_INSN (p) != bb)
1104 break;
1106 if (!DEBUG_INSN_P (p))
1107 length++;
1109 /* ??? See if all of SRC is set in P. This test is much
1110 more conservative than it needs to be. */
1111 pset = single_set (p);
1112 if (pset && SET_DEST (pset) == src)
1114 /* We use validate_replace_rtx, in case there
1115 are multiple identical source operands. All
1116 of them have to be changed at the same time:
1117 when validate_replace_rtx() calls
1118 apply_change_group(). */
1119 validate_change (p, &SET_DEST (pset), dst, 1);
1120 if (validate_replace_rtx (src, dst, insn))
1121 success = 1;
1122 break;
1125 /* We can't make this change if DST is mentioned at
1126 all in P, since we are going to change its value.
1127 We can't make this change if SRC is read or
1128 partially written in P, since we are going to
1129 eliminate SRC. However, if it's a debug insn, we
1130 can't refrain from making the change, for this
1131 would cause codegen differences, so instead we
1132 invalidate debug expressions that reference DST,
1133 and adjust references to SRC in them so that they
1134 become references to DST. */
1135 if (reg_mentioned_p (dst, PATTERN (p)))
1137 if (DEBUG_INSN_P (p))
1138 validate_change (p, &INSN_VAR_LOCATION_LOC (p),
1139 gen_rtx_UNKNOWN_VAR_LOC (), 1);
1140 else
1141 break;
1143 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1145 if (DEBUG_INSN_P (p))
1146 validate_replace_rtx_group (src, dst, p);
1147 else
1148 break;
1151 /* If we have passed a call instruction, and the
1152 pseudo-reg DST is not already live across a call,
1153 then don't perform the optimization. */
1154 if (CALL_P (p))
1156 num_calls++;
1157 freq_calls += REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p));
1159 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1160 break;
1164 if (success)
1166 int dstno, srcno;
1168 /* Remove the death note for SRC from INSN. */
1169 remove_note (insn, src_note);
1170 /* Move the death note for SRC to P if it is used
1171 there. */
1172 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1174 XEXP (src_note, 1) = REG_NOTES (p);
1175 REG_NOTES (p) = src_note;
1177 /* If there is a REG_DEAD note for DST on P, then remove
1178 it, because DST is now set there. */
1179 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1180 remove_note (p, dst_note);
1182 dstno = REGNO (dst);
1183 srcno = REGNO (src);
1185 INC_REG_N_SETS (dstno, 1);
1186 INC_REG_N_SETS (srcno, -1);
1188 REG_N_CALLS_CROSSED (dstno) += num_calls;
1189 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1190 REG_FREQ_CALLS_CROSSED (dstno) += freq_calls;
1191 REG_FREQ_CALLS_CROSSED (srcno) -= freq_calls;
1193 REG_LIVE_LENGTH (dstno) += length;
1194 if (REG_LIVE_LENGTH (srcno) >= 0)
1196 REG_LIVE_LENGTH (srcno) -= length;
1197 /* REG_LIVE_LENGTH is only an approximation after
1198 combine if sched is not run, so make sure that we
1199 still have a reasonable value. */
1200 if (REG_LIVE_LENGTH (srcno) < 2)
1201 REG_LIVE_LENGTH (srcno) = 2;
1204 if (dump_file)
1205 fprintf (dump_file,
1206 "Fixed operand %d of insn %d matching operand %d.\n",
1207 op_no, INSN_UID (insn), match_no);
1209 break;
1211 else if (num_changes_pending () > 0)
1212 cancel_changes (0);
1215 /* If we weren't able to replace any of the alternatives, try an
1216 alternative approach of copying the source to the destination. */
1217 if (!success && copy_src != NULL_RTX)
1218 copy_src_to_dest (insn, copy_src, copy_dst);
1223 /* Main entry for the register move optimization. */
1225 static unsigned int
1226 regmove_optimize (void)
1228 int i;
1229 int nregs = max_reg_num ();
1231 df_note_add_problem ();
1232 df_analyze ();
1234 regstat_init_n_sets_and_refs ();
1235 regstat_compute_ri ();
1237 if (flag_ira_loop_pressure)
1238 ira_set_pseudo_classes (true, dump_file);
1240 regno_src_regno = XNEWVEC (int, nregs);
1241 for (i = nregs; --i >= 0; )
1242 regno_src_regno[i] = -1;
1244 /* A forward pass. Replace output operands with input operands. */
1245 regmove_forward_pass ();
1247 /* A backward pass. Replace input operands with output operands. */
1248 regmove_backward_pass ();
1250 /* Clean up. */
1251 free (regno_src_regno);
1252 if (reg_set_in_bb)
1254 free (reg_set_in_bb);
1255 reg_set_in_bb = NULL;
1257 regstat_free_n_sets_and_refs ();
1258 regstat_free_ri ();
1259 if (flag_ira_loop_pressure)
1260 free_reg_info ();
1261 return 0;
1264 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1265 Returns 0 if INSN can't be recognized, or if the alternative can't be
1266 determined.
1268 Initialize the info in MATCHP based on the constraints. */
1270 static int
1271 find_matches (rtx insn, struct match *matchp)
1273 int likely_spilled[MAX_RECOG_OPERANDS];
1274 int op_no;
1275 int any_matches = 0;
1277 extract_insn (insn);
1278 if (! constrain_operands (0))
1279 return 0;
1281 /* Must initialize this before main loop, because the code for
1282 the commutative case may set matches for operands other than
1283 the current one. */
1284 for (op_no = recog_data.n_operands; --op_no >= 0; )
1285 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1287 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1289 const char *p;
1290 char c;
1291 int i = 0;
1293 p = recog_data.constraints[op_no];
1295 likely_spilled[op_no] = 0;
1296 matchp->use[op_no] = READ;
1297 matchp->early_clobber[op_no] = 0;
1298 if (*p == '=')
1299 matchp->use[op_no] = WRITE;
1300 else if (*p == '+')
1301 matchp->use[op_no] = READWRITE;
1303 for (;*p && i < which_alternative; p++)
1304 if (*p == ',')
1305 i++;
1307 while ((c = *p) != '\0' && c != ',')
1309 switch (c)
1311 case '=':
1312 break;
1313 case '+':
1314 break;
1315 case '&':
1316 matchp->early_clobber[op_no] = 1;
1317 break;
1318 case '%':
1319 matchp->commutative[op_no] = op_no + 1;
1320 matchp->commutative[op_no + 1] = op_no;
1321 break;
1323 case '0': case '1': case '2': case '3': case '4':
1324 case '5': case '6': case '7': case '8': case '9':
1326 char *end;
1327 unsigned long match_ul = strtoul (p, &end, 10);
1328 int match = match_ul;
1330 p = end;
1332 if (match < op_no && likely_spilled[match])
1333 continue;
1334 matchp->with[op_no] = match;
1335 any_matches = 1;
1336 if (matchp->commutative[op_no] >= 0)
1337 matchp->with[matchp->commutative[op_no]] = match;
1339 continue;
1341 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1342 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1343 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1344 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1345 if (targetm.class_likely_spilled_p (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p)))
1346 likely_spilled[op_no] = 1;
1347 break;
1349 p += CONSTRAINT_LEN (c, p);
1352 return any_matches;
1357 static bool
1358 gate_handle_regmove (void)
1360 return (optimize > 0 && flag_regmove);
1364 struct rtl_opt_pass pass_regmove =
1367 RTL_PASS,
1368 "regmove", /* name */
1369 OPTGROUP_NONE, /* optinfo_flags */
1370 gate_handle_regmove, /* gate */
1371 regmove_optimize, /* execute */
1372 NULL, /* sub */
1373 NULL, /* next */
1374 0, /* static_pass_number */
1375 TV_REGMOVE, /* tv_id */
1376 0, /* properties_required */
1377 0, /* properties_provided */
1378 0, /* properties_destroyed */
1379 0, /* todo_flags_start */
1380 TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */