Mercurial > hg > CbC > CbC_gcc

comparison gcc/regmove.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* Move registers around to reduce number of move instructions needed.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
3 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 Free Software Foundation, Inc.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22
23 /* This module makes some simple RTL code transformations which
24 improve the subsequent register allocation. */
25
26 #include "config.h"
27 #include "system.h"
28 #include "coretypes.h"
29 #include "tm.h"
30 #include "rtl.h" /* stdio.h must precede rtl.h for FFS. */
31 #include "tm_p.h"
32 #include "insn-config.h"
33 #include "recog.h"
34 #include "output.h"
35 #include "regs.h"
36 #include "hard-reg-set.h"
37 #include "flags.h"
38 #include "function.h"
39 #include "expr.h"
40 #include "basic-block.h"
41 #include "except.h"
42 #include "toplev.h"
43 #include "reload.h"
44 #include "timevar.h"
45 #include "tree-pass.h"
46 #include "df.h"
47
48 static int perhaps_ends_bb_p (rtx);
49 static int optimize_reg_copy_1 (rtx, rtx, rtx);
50 static void optimize_reg_copy_2 (rtx, rtx, rtx);
51 static void optimize_reg_copy_3 (rtx, rtx, rtx);
52 static void copy_src_to_dest (rtx, rtx, rtx);
53
54 struct match {
55 int with[MAX_RECOG_OPERANDS];
56 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
57 int commutative[MAX_RECOG_OPERANDS];
58 int early_clobber[MAX_RECOG_OPERANDS];
59 };
60
61 static int find_matches (rtx, struct match *);
62 static int regclass_compatible_p (int, int);
63 static int fixup_match_2 (rtx, rtx, rtx, rtx);
64
65 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
66 causing too much register allocation problems. */
67 static int
68 regclass_compatible_p (int class0, int class1)
69 {
70 return (class0 == class1
71 || (reg_class_subset_p (class0, class1)
72 && ! CLASS_LIKELY_SPILLED_P (class0))
73 || (reg_class_subset_p (class1, class0)
74 && ! CLASS_LIKELY_SPILLED_P (class1)));
75 }
76
77
78 #ifdef AUTO_INC_DEC
79
80 /* Find the place in the rtx X where REG is used as a memory address.
81 Return the MEM rtx that so uses it.
82 If PLUSCONST is nonzero, search instead for a memory address equivalent to
83 (plus REG (const_int PLUSCONST)).
84
85 If such an address does not appear, return 0.
86 If REG appears more than once, or is used other than in such an address,
87 return (rtx) 1. */
88
89 static rtx
90 find_use_as_address (rtx x, rtx reg, HOST_WIDE_INT plusconst)
91 {
92 enum rtx_code code = GET_CODE (x);
93 const char * const fmt = GET_RTX_FORMAT (code);
94 int i;
95 rtx value = 0;
96 rtx tem;
97
98 if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
99 return x;
100
101 if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
102 && XEXP (XEXP (x, 0), 0) == reg
103 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
104 && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
105 return x;
106
107 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
108 {
109 /* If REG occurs inside a MEM used in a bit-field reference,
110 that is unacceptable. */
111 if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
112 return (rtx) (size_t) 1;
113 }
114
115 if (x == reg)
116 return (rtx) (size_t) 1;
117
118 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
119 {
120 if (fmt[i] == 'e')
121 {
122 tem = find_use_as_address (XEXP (x, i), reg, plusconst);
123 if (value == 0)
124 value = tem;
125 else if (tem != 0)
126 return (rtx) (size_t) 1;
127 }
128 else if (fmt[i] == 'E')
129 {
130 int j;
131 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
132 {
133 tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
134 if (value == 0)
135 value = tem;
136 else if (tem != 0)
137 return (rtx) (size_t) 1;
138 }
139 }
140 }
141
142 return value;
143 }
144
145
146 /* INC_INSN is an instruction that adds INCREMENT to REG.
147 Try to fold INC_INSN as a post/pre in/decrement into INSN.
148 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
149 Return nonzero for success. */
150 static int
151 try_auto_increment (rtx insn, rtx inc_insn, rtx inc_insn_set, rtx reg,
152 HOST_WIDE_INT increment, int pre)
153 {
154 enum rtx_code inc_code;
155
156 rtx pset = single_set (insn);
157 if (pset)
158 {
159 /* Can't use the size of SET_SRC, we might have something like
160 (sign_extend:SI (mem:QI ... */
161 rtx use = find_use_as_address (pset, reg, 0);
162 if (use != 0 && use != (rtx) (size_t) 1)
163 {
164 int size = GET_MODE_SIZE (GET_MODE (use));
165 if (0
166 || (HAVE_POST_INCREMENT
167 && pre == 0 && (inc_code = POST_INC, increment == size))
168 || (HAVE_PRE_INCREMENT
169 && pre == 1 && (inc_code = PRE_INC, increment == size))
170 || (HAVE_POST_DECREMENT
171 && pre == 0 && (inc_code = POST_DEC, increment == -size))
172 || (HAVE_PRE_DECREMENT
173 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
174 )
175 {
176 if (inc_insn_set)
177 validate_change
178 (inc_insn,
179 &SET_SRC (inc_insn_set),
180 XEXP (SET_SRC (inc_insn_set), 0), 1);
181 validate_change (insn, &XEXP (use, 0),
182 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
183 if (apply_change_group ())
184 {
185 /* If there is a REG_DEAD note on this insn, we must
186 change this not to REG_UNUSED meaning that the register
187 is set, but the value is dead. Failure to do so will
188 result in sched1 dying -- when it recomputes lifetime
189 information, the number of REG_DEAD notes will have
190 changed. */
191 rtx note = find_reg_note (insn, REG_DEAD, reg);
192 if (note)
193 PUT_MODE (note, REG_UNUSED);
194
195 add_reg_note (insn, REG_INC, reg);
196
197 if (! inc_insn_set)
198 delete_insn (inc_insn);
199 return 1;
200 }
201 }
202 }
203 }
204 return 0;
205 }
206 #endif
207
208
209 static int *regno_src_regno;
210
211
212 /* Return 1 if INSN might end a basic block. */
213
214 static int perhaps_ends_bb_p (rtx insn)
215 {
216 switch (GET_CODE (insn))
217 {
218 case CODE_LABEL:
219 case JUMP_INSN:
220 /* These always end a basic block. */
221 return 1;
222
223 case CALL_INSN:
224 /* A CALL_INSN might be the last insn of a basic block, if it is inside
225 an EH region or if there are nonlocal gotos. Note that this test is
226 very conservative. */
227 if (nonlocal_goto_handler_labels)
228 return 1;
229 /* Fall through. */
230 default:
231 return can_throw_internal (insn);
232 }
233 }
234
235 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
236 in INSN.
237
238 Search forward to see if SRC dies before either it or DEST is modified,
239 but don't scan past the end of a basic block. If so, we can replace SRC
240 with DEST and let SRC die in INSN.
241
242 This will reduce the number of registers live in that range and may enable
243 DEST to be tied to SRC, thus often saving one register in addition to a
244 register-register copy. */
245
246 static int
247 optimize_reg_copy_1 (rtx insn, rtx dest, rtx src)
248 {
249 rtx p, q;
250 rtx note;
251 rtx dest_death = 0;
252 int sregno = REGNO (src);
253 int dregno = REGNO (dest);
254
255 /* We don't want to mess with hard regs if register classes are small. */
256 if (sregno == dregno
257 || (SMALL_REGISTER_CLASSES
258 && (sregno < FIRST_PSEUDO_REGISTER
259 || dregno < FIRST_PSEUDO_REGISTER))
260 /* We don't see all updates to SP if they are in an auto-inc memory
261 reference, so we must disallow this optimization on them. */
262 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
263 return 0;
264
265 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
266 {
267 /* ??? We can't scan past the end of a basic block without updating
268 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
269 if (perhaps_ends_bb_p (p))
270 break;
271 else if (! INSN_P (p))
272 continue;
273
274 if (reg_set_p (src, p) || reg_set_p (dest, p)
275 /* If SRC is an asm-declared register, it must not be replaced
276 in any asm. Unfortunately, the REG_EXPR tree for the asm
277 variable may be absent in the SRC rtx, so we can't check the
278 actual register declaration easily (the asm operand will have
279 it, though). To avoid complicating the test for a rare case,
280 we just don't perform register replacement for a hard reg
281 mentioned in an asm. */
282 || (sregno < FIRST_PSEUDO_REGISTER
283 && asm_noperands (PATTERN (p)) >= 0
284 && reg_overlap_mentioned_p (src, PATTERN (p)))
285 /* Don't change hard registers used by a call. */
286 || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
287 && find_reg_fusage (p, USE, src))
288 /* Don't change a USE of a register. */
289 || (GET_CODE (PATTERN (p)) == USE
290 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
291 break;
292
293 /* See if all of SRC dies in P. This test is slightly more
294 conservative than it needs to be. */
295 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
296 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
297 {
298 int failed = 0;
299 int d_length = 0;
300 int s_length = 0;
301 int d_n_calls = 0;
302 int s_n_calls = 0;
303 int s_freq_calls = 0;
304 int d_freq_calls = 0;
305
306 /* We can do the optimization. Scan forward from INSN again,
307 replacing regs as we go. Set FAILED if a replacement can't
308 be done. In that case, we can't move the death note for SRC.
309 This should be rare. */
310
311 /* Set to stop at next insn. */
312 for (q = next_real_insn (insn);
313 q != next_real_insn (p);
314 q = next_real_insn (q))
315 {
316 if (reg_overlap_mentioned_p (src, PATTERN (q)))
317 {
318 /* If SRC is a hard register, we might miss some
319 overlapping registers with validate_replace_rtx,
320 so we would have to undo it. We can't if DEST is
321 present in the insn, so fail in that combination
322 of cases. */
323 if (sregno < FIRST_PSEUDO_REGISTER
324 && reg_mentioned_p (dest, PATTERN (q)))
325 failed = 1;
326
327 /* Attempt to replace all uses. */
328 else if (!validate_replace_rtx (src, dest, q))
329 failed = 1;
330
331 /* If this succeeded, but some part of the register
332 is still present, undo the replacement. */
333 else if (sregno < FIRST_PSEUDO_REGISTER
334 && reg_overlap_mentioned_p (src, PATTERN (q)))
335 {
336 validate_replace_rtx (dest, src, q);
337 failed = 1;
338 }
339 }
340
341 /* For SREGNO, count the total number of insns scanned.
342 For DREGNO, count the total number of insns scanned after
343 passing the death note for DREGNO. */
344 s_length++;
345 if (dest_death)
346 d_length++;
347
348 /* If the insn in which SRC dies is a CALL_INSN, don't count it
349 as a call that has been crossed. Otherwise, count it. */
350 if (q != p && CALL_P (q))
351 {
352 /* Similarly, total calls for SREGNO, total calls beyond
353 the death note for DREGNO. */
354 s_n_calls++;
355 s_freq_calls += REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q));
356 if (dest_death)
357 {
358 d_n_calls++;
359 d_freq_calls += REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q));
360 }
361 }
362
363 /* If DEST dies here, remove the death note and save it for
364 later. Make sure ALL of DEST dies here; again, this is
365 overly conservative. */
366 if (dest_death == 0
367 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
368 {
369 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
370 failed = 1, dest_death = 0;
371 else
372 remove_note (q, dest_death);
373 }
374 }
375
376 if (! failed)
377 {
378 /* These counters need to be updated if and only if we are
379 going to move the REG_DEAD note. */
380 if (sregno >= FIRST_PSEUDO_REGISTER)
381 {
382 if (REG_LIVE_LENGTH (sregno) >= 0)
383 {
384 REG_LIVE_LENGTH (sregno) -= s_length;
385 /* REG_LIVE_LENGTH is only an approximation after
386 combine if sched is not run, so make sure that we
387 still have a reasonable value. */
388 if (REG_LIVE_LENGTH (sregno) < 2)
389 REG_LIVE_LENGTH (sregno) = 2;
390 }
391
392 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
393 REG_FREQ_CALLS_CROSSED (sregno) -= s_freq_calls;
394 }
395
396 /* Move death note of SRC from P to INSN. */
397 remove_note (p, note);
398 XEXP (note, 1) = REG_NOTES (insn);
399 REG_NOTES (insn) = note;
400 }
401
402 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
403 if (! dest_death
404 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
405 {
406 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
407 remove_note (insn, dest_death);
408 }
409
410 /* Put death note of DEST on P if we saw it die. */
411 if (dest_death)
412 {
413 XEXP (dest_death, 1) = REG_NOTES (p);
414 REG_NOTES (p) = dest_death;
415
416 if (dregno >= FIRST_PSEUDO_REGISTER)
417 {
418 /* If and only if we are moving the death note for DREGNO,
419 then we need to update its counters. */
420 if (REG_LIVE_LENGTH (dregno) >= 0)
421 REG_LIVE_LENGTH (dregno) += d_length;
422 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
423 REG_FREQ_CALLS_CROSSED (dregno) += d_freq_calls;
424 }
425 }
426
427 return ! failed;
428 }
429
430 /* If SRC is a hard register which is set or killed in some other
431 way, we can't do this optimization. */
432 else if (sregno < FIRST_PSEUDO_REGISTER
433 && dead_or_set_p (p, src))
434 break;
435 }
436 return 0;
437 }
438
439 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
440 a sequence of insns that modify DEST followed by an insn that sets
441 SRC to DEST in which DEST dies, with no prior modification of DEST.
442 (There is no need to check if the insns in between actually modify
443 DEST. We should not have cases where DEST is not modified, but
444 the optimization is safe if no such modification is detected.)
445 In that case, we can replace all uses of DEST, starting with INSN and
446 ending with the set of SRC to DEST, with SRC. We do not do this
447 optimization if a CALL_INSN is crossed unless SRC already crosses a
448 call or if DEST dies before the copy back to SRC.
449
450 It is assumed that DEST and SRC are pseudos; it is too complicated to do
451 this for hard registers since the substitutions we may make might fail. */
452
453 static void
454 optimize_reg_copy_2 (rtx insn, rtx dest, rtx src)
455 {
456 rtx p, q;
457 rtx set;
458 int sregno = REGNO (src);
459 int dregno = REGNO (dest);
460
461 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
462 {
463 /* ??? We can't scan past the end of a basic block without updating
464 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
465 if (perhaps_ends_bb_p (p))
466 break;
467 else if (! INSN_P (p))
468 continue;
469
470 set = single_set (p);
471 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
472 && find_reg_note (p, REG_DEAD, dest))
473 {
474 /* We can do the optimization. Scan forward from INSN again,
475 replacing regs as we go. */
476
477 /* Set to stop at next insn. */
478 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
479 if (INSN_P (q))
480 {
481 if (reg_mentioned_p (dest, PATTERN (q)))
482 {
483 rtx note;
484
485 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
486 note = FIND_REG_INC_NOTE (q, dest);
487 if (note)
488 {
489 remove_note (q, note);
490 add_reg_note (q, REG_INC, src);
491 }
492 df_insn_rescan (q);
493 }
494
495 if (CALL_P (q))
496 {
497 int freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q));
498 REG_N_CALLS_CROSSED (dregno)--;
499 REG_N_CALLS_CROSSED (sregno)++;
500 REG_FREQ_CALLS_CROSSED (dregno) -= freq;
501 REG_FREQ_CALLS_CROSSED (sregno) += freq;
502 }
503 }
504
505 remove_note (p, find_reg_note (p, REG_DEAD, dest));
506 REG_N_DEATHS (dregno)--;
507 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
508 REG_N_DEATHS (sregno)--;
509 return;
510 }
511
512 if (reg_set_p (src, p)
513 || find_reg_note (p, REG_DEAD, dest)
514 || (CALL_P (p) && REG_N_CALLS_CROSSED (sregno) == 0))
515 break;
516 }
517 }
518
519 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
520 Look if SRC dies there, and if it is only set once, by loading
521 it from memory. If so, try to incorporate the zero/sign extension
522 into the memory read, change SRC to the mode of DEST, and alter
523 the remaining accesses to use the appropriate SUBREG. This allows
524 SRC and DEST to be tied later. */
525 static void
526 optimize_reg_copy_3 (rtx insn, rtx dest, rtx src)
527 {
528 rtx src_reg = XEXP (src, 0);
529 int src_no = REGNO (src_reg);
530 int dst_no = REGNO (dest);
531 rtx p, set;
532 enum machine_mode old_mode;
533
534 if (src_no < FIRST_PSEUDO_REGISTER
535 || dst_no < FIRST_PSEUDO_REGISTER
536 || ! find_reg_note (insn, REG_DEAD, src_reg)
537 || REG_N_DEATHS (src_no) != 1
538 || REG_N_SETS (src_no) != 1)
539 return;
540 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
541 /* ??? We can't scan past the end of a basic block without updating
542 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
543 if (perhaps_ends_bb_p (p))
544 break;
545
546 if (! p)
547 return;
548
549 if (! (set = single_set (p))
550 || !MEM_P (SET_SRC (set))
551 /* If there's a REG_EQUIV note, this must be an insn that loads an
552 argument. Prefer keeping the note over doing this optimization. */
553 || find_reg_note (p, REG_EQUIV, NULL_RTX)
554 || SET_DEST (set) != src_reg)
555 return;
556
557 /* Be conservative: although this optimization is also valid for
558 volatile memory references, that could cause trouble in later passes. */
559 if (MEM_VOLATILE_P (SET_SRC (set)))
560 return;
561
562 /* Do not use a SUBREG to truncate from one mode to another if truncation
563 is not a nop. */
564 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
565 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
566 GET_MODE_BITSIZE (GET_MODE (src_reg))))
567 return;
568
569 old_mode = GET_MODE (src_reg);
570 PUT_MODE (src_reg, GET_MODE (src));
571 XEXP (src, 0) = SET_SRC (set);
572
573 /* Include this change in the group so that it's easily undone if
574 one of the changes in the group is invalid. */
575 validate_change (p, &SET_SRC (set), src, 1);
576
577 /* Now walk forward making additional replacements. We want to be able
578 to undo all the changes if a later substitution fails. */
579 while (p = NEXT_INSN (p), p != insn)
580 {
581 if (! INSN_P (p))
582 continue;
583
584 /* Make a tentative change. */
585 validate_replace_rtx_group (src_reg,
586 gen_lowpart_SUBREG (old_mode, src_reg),
587 p);
588 }
589
590 validate_replace_rtx_group (src, src_reg, insn);
591
592 /* Now see if all the changes are valid. */
593 if (! apply_change_group ())
594 {
595 /* One or more changes were no good. Back out everything. */
596 PUT_MODE (src_reg, old_mode);
597 XEXP (src, 0) = src_reg;
598 }
599 else
600 {
601 rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
602 if (note)
603 remove_note (p, note);
604 }
605 }
606
607
608 /* If we were not able to update the users of src to use dest directly, try
609 instead moving the value to dest directly before the operation. */
610
611 static void
612 copy_src_to_dest (rtx insn, rtx src, rtx dest)
613 {
614 rtx seq;
615 rtx link;
616 rtx next;
617 rtx set;
618 rtx move_insn;
619 rtx *p_insn_notes;
620 rtx *p_move_notes;
621 int src_regno;
622 int dest_regno;
623 int insn_uid;
624 int move_uid;
625
626 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
627 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
628 parameter when there is no frame pointer that is not allocated a register.
629 For now, we just reject them, rather than incrementing the live length. */
630
631 if (REG_P (src)
632 && REG_LIVE_LENGTH (REGNO (src)) > 0
633 && REG_P (dest)
634 && REG_LIVE_LENGTH (REGNO (dest)) > 0
635 && (set = single_set (insn)) != NULL_RTX
636 && !reg_mentioned_p (dest, SET_SRC (set))
637 && GET_MODE (src) == GET_MODE (dest))
638 {
639 int old_num_regs = reg_rtx_no;
640
641 /* Generate the src->dest move. */
642 start_sequence ();
643 emit_move_insn (dest, src);
644 seq = get_insns ();
645 end_sequence ();
646 /* If this sequence uses new registers, we may not use it. */
647 if (old_num_regs != reg_rtx_no
648 || ! validate_replace_rtx (src, dest, insn))
649 {
650 /* We have to restore reg_rtx_no to its old value, lest
651 recompute_reg_usage will try to compute the usage of the
652 new regs, yet reg_n_info is not valid for them. */
653 reg_rtx_no = old_num_regs;
654 return;
655 }
656 emit_insn_before (seq, insn);
657 move_insn = PREV_INSN (insn);
658 p_move_notes = &REG_NOTES (move_insn);
659 p_insn_notes = &REG_NOTES (insn);
660
661 /* Move any notes mentioning src to the move instruction. */
662 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
663 {
664 next = XEXP (link, 1);
665 if (XEXP (link, 0) == src)
666 {
667 *p_move_notes = link;
668 p_move_notes = &XEXP (link, 1);
669 }
670 else
671 {
672 *p_insn_notes = link;
673 p_insn_notes = &XEXP (link, 1);
674 }
675 }
676
677 *p_move_notes = NULL_RTX;
678 *p_insn_notes = NULL_RTX;
679
680 insn_uid = INSN_UID (insn);
681 move_uid = INSN_UID (move_insn);
682
683 /* Update the various register tables. */
684 dest_regno = REGNO (dest);
685 INC_REG_N_SETS (dest_regno, 1);
686 REG_LIVE_LENGTH (dest_regno)++;
687 src_regno = REGNO (src);
688 if (! find_reg_note (move_insn, REG_DEAD, src))
689 REG_LIVE_LENGTH (src_regno)++;
690 }
691 }
692
693 /* reg_set_in_bb[REGNO] points to basic block iff the register is set
694 only once in the given block and has REG_EQUAL note. */
695
696 static basic_block *reg_set_in_bb;
697
698 /* Size of reg_set_in_bb array. */
699 static unsigned int max_reg_computed;
700
701
702 /* Return whether REG is set in only one location, and is set to a
703 constant, but is set in a different basic block from INSN (an
704 instructions which uses REG). In this case REG is equivalent to a
705 constant, and we don't want to break that equivalence, because that
706 may increase register pressure and make reload harder. If REG is
707 set in the same basic block as INSN, we don't worry about it,
708 because we'll probably need a register anyhow (??? but what if REG
709 is used in a different basic block as well as this one?). */
710
711 static bool
712 reg_is_remote_constant_p (rtx reg, rtx insn)
713 {
714 basic_block bb;
715 rtx p;
716 int max;
717
718 if (!reg_set_in_bb)
719 {
720 max_reg_computed = max = max_reg_num ();
721 reg_set_in_bb = XCNEWVEC (basic_block, max);
722
723 FOR_EACH_BB (bb)
724 FOR_BB_INSNS (bb, p)
725 {
726 rtx s;
727
728 if (!INSN_P (p))
729 continue;
730 s = single_set (p);
731 /* This is the instruction which sets REG. If there is a
732 REG_EQUAL note, then REG is equivalent to a constant. */
733 if (s != 0
734 && REG_P (SET_DEST (s))
735 && REG_N_SETS (REGNO (SET_DEST (s))) == 1
736 && find_reg_note (p, REG_EQUAL, NULL_RTX))
737 reg_set_in_bb[REGNO (SET_DEST (s))] = bb;
738 }
739 }
740
741 gcc_assert (REGNO (reg) < max_reg_computed);
742 if (reg_set_in_bb[REGNO (reg)] == NULL)
743 return false;
744 return (reg_set_in_bb[REGNO (reg)] != BLOCK_FOR_INSN (insn));
745 }
746
747 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
748 another add immediate instruction with the same source and dest registers,
749 and if we find one, we change INSN to an increment, and return 1. If
750 no changes are made, we return 0.
751
752 This changes
753 (set (reg100) (plus reg1 offset1))
754 ...
755 (set (reg100) (plus reg1 offset2))
756 to
757 (set (reg100) (plus reg1 offset1))
758 ...
759 (set (reg100) (plus reg100 offset2-offset1)) */
760
761 /* ??? What does this comment mean? */
762 /* cse disrupts preincrement / postdecrement sequences when it finds a
763 hard register as ultimate source, like the frame pointer. */
764
765 static int
766 fixup_match_2 (rtx insn, rtx dst, rtx src, rtx offset)
767 {
768 rtx p, dst_death = 0;
769 int length, num_calls = 0, freq_calls = 0;
770
771 /* If SRC dies in INSN, we'd have to move the death note. This is
772 considered to be very unlikely, so we just skip the optimization
773 in this case. */
774 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
775 return 0;
776
777 /* Scan backward to find the first instruction that sets DST. */
778
779 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
780 {
781 rtx pset;
782
783 /* ??? We can't scan past the end of a basic block without updating
784 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
785 if (perhaps_ends_bb_p (p))
786 break;
787 else if (! INSN_P (p))
788 continue;
789
790 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
791 dst_death = p;
792 if (! dst_death)
793 length++;
794
795 pset = single_set (p);
796 if (pset && SET_DEST (pset) == dst
797 && GET_CODE (SET_SRC (pset)) == PLUS
798 && XEXP (SET_SRC (pset), 0) == src
799 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
800 {
801 HOST_WIDE_INT newconst
802 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
803 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
804
805 if (add && validate_change (insn, &PATTERN (insn), add, 0))
806 {
807 /* Remove the death note for DST from DST_DEATH. */
808 if (dst_death)
809 {
810 remove_death (REGNO (dst), dst_death);
811 REG_LIVE_LENGTH (REGNO (dst)) += length;
812 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
813 REG_FREQ_CALLS_CROSSED (REGNO (dst)) += freq_calls;
814 }
815
816 if (dump_file)
817 fprintf (dump_file,
818 "Fixed operand of insn %d.\n",
819 INSN_UID (insn));
820
821 #ifdef AUTO_INC_DEC
822 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
823 {
824 if (LABEL_P (p)
825 || JUMP_P (p))
826 break;
827 if (! INSN_P (p))
828 continue;
829 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
830 {
831 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
832 return 1;
833 break;
834 }
835 }
836 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
837 {
838 if (LABEL_P (p)
839 || JUMP_P (p))
840 break;
841 if (! INSN_P (p))
842 continue;
843 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
844 {
845 try_auto_increment (p, insn, 0, dst, newconst, 1);
846 break;
847 }
848 }
849 #endif
850 return 1;
851 }
852 }
853
854 if (reg_set_p (dst, PATTERN (p)))
855 break;
856
857 /* If we have passed a call instruction, and the
858 pseudo-reg SRC is not already live across a call,
859 then don't perform the optimization. */
860 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
861 hard regs are clobbered. Thus, we only use it for src for
862 non-call insns. */
863 if (CALL_P (p))
864 {
865 if (! dst_death)
866 {
867 num_calls++;
868 freq_calls += REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p));
869 }
870
871 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
872 break;
873
874 if (call_used_regs [REGNO (dst)]
875 || find_reg_fusage (p, CLOBBER, dst))
876 break;
877 }
878 else if (reg_set_p (src, PATTERN (p)))
879 break;
880 }
881
882 return 0;
883 }
884
885 /* Main entry for the register move optimization. */
886
887 static unsigned int
888 regmove_optimize (void)
889 {
890 rtx insn;
891 struct match match;
892 int i;
893 rtx copy_src, copy_dst;
894 int nregs = max_reg_num ();
895
896 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
897 confused by non-call exceptions ending blocks. */
898 if (flag_non_call_exceptions)
899 return 0;
900
901 df_note_add_problem ();
902 df_analyze ();
903
904 regstat_init_n_sets_and_refs ();
905 regstat_compute_ri ();
906
907 regno_src_regno = XNEWVEC (int, nregs);
908 for (i = nregs; --i >= 0; )
909 regno_src_regno[i] = -1;
910
911 /* A forward pass. Replace output operands with input operands. */
912
913 if (flag_expensive_optimizations)
914 {
915 if (dump_file)
916 fprintf (dump_file, "Starting forward pass...\n");
917
918 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
919 {
920 rtx set = single_set (insn);
921 if (! set)
922 continue;
923
924 if ((GET_CODE (SET_SRC (set)) == SIGN_EXTEND
925 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
926 && REG_P (XEXP (SET_SRC (set), 0))
927 && REG_P (SET_DEST (set)))
928 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
929
930 if (REG_P (SET_SRC (set))
931 && REG_P (SET_DEST (set)))
932 {
933 /* If this is a register-register copy where SRC is not dead,
934 see if we can optimize it. If this optimization succeeds,
935 it will become a copy where SRC is dead. */
936 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
937 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
938 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
939 {
940 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
941 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
942 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
943 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
944 && SET_SRC (set) != SET_DEST (set))
945 {
946 int srcregno = REGNO (SET_SRC (set));
947 if (regno_src_regno[srcregno] >= 0)
948 srcregno = regno_src_regno[srcregno];
949 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
950 }
951 }
952 }
953 }
954 }
955
956 /* A backward pass. Replace input operands with output operands. */
957
958 if (dump_file)
959 fprintf (dump_file, "Starting backward pass...\n");
960
961 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
962 {
963 if (INSN_P (insn))
964 {
965 int op_no, match_no;
966 int success = 0;
967
968 if (! find_matches (insn, &match))
969 continue;
970
971 /* Now scan through the operands looking for a destination operand
972 which is supposed to match a source operand.
973 Then scan backward for an instruction which sets the source
974 operand. If safe, then replace the source operand with the
975 dest operand in both instructions. */
976
977 copy_src = NULL_RTX;
978 copy_dst = NULL_RTX;
979 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
980 {
981 rtx set, p, src, dst;
982 rtx src_note, dst_note;
983 int num_calls = 0, freq_calls = 0;
984 enum reg_class src_class, dst_class;
985 int length;
986
987 match_no = match.with[op_no];
988
989 /* Nothing to do if the two operands aren't supposed to match. */
990 if (match_no < 0)
991 continue;
992
993 dst = recog_data.operand[match_no];
994 src = recog_data.operand[op_no];
995
996 if (!REG_P (src))
997 continue;
998
999 if (!REG_P (dst)
1000 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1001 || REG_LIVE_LENGTH (REGNO (dst)) < 0
1002 || GET_MODE (src) != GET_MODE (dst))
1003 continue;
1004
1005 /* If the operands already match, then there is nothing to do. */
1006 if (operands_match_p (src, dst))
1007 continue;
1008
1009 if (match.commutative[op_no] >= 0)
1010 {
1011 rtx comm = recog_data.operand[match.commutative[op_no]];
1012 if (operands_match_p (comm, dst))
1013 continue;
1014 }
1015
1016 set = single_set (insn);
1017 if (! set)
1018 continue;
1019
1020 /* Note that single_set ignores parts of a parallel set for
1021 which one of the destinations is REG_UNUSED. We can't
1022 handle that here, since we can wind up rewriting things
1023 such that a single register is set twice within a single
1024 parallel. */
1025 if (reg_set_p (src, insn))
1026 continue;
1027
1028 /* match_no/dst must be a write-only operand, and
1029 operand_operand/src must be a read-only operand. */
1030 if (match.use[op_no] != READ
1031 || match.use[match_no] != WRITE)
1032 continue;
1033
1034 if (match.early_clobber[match_no]
1035 && count_occurrences (PATTERN (insn), src, 0) > 1)
1036 continue;
1037
1038 /* Make sure match_no is the destination. */
1039 if (recog_data.operand[match_no] != SET_DEST (set))
1040 continue;
1041
1042 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1043 {
1044 if (GET_CODE (SET_SRC (set)) == PLUS
1045 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1046 && XEXP (SET_SRC (set), 0) == src
1047 && fixup_match_2 (insn, dst, src,
1048 XEXP (SET_SRC (set), 1)))
1049 break;
1050 continue;
1051 }
1052 src_class = reg_preferred_class (REGNO (src));
1053 dst_class = reg_preferred_class (REGNO (dst));
1054
1055 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1056 {
1057 /* We used to force the copy here like in other cases, but
1058 it produces worse code, as it eliminates no copy
1059 instructions and the copy emitted will be produced by
1060 reload anyway. On patterns with multiple alternatives,
1061 there may be better solution available.
1062
1063 In particular this change produced slower code for numeric
1064 i387 programs. */
1065
1066 continue;
1067 }
1068
1069 if (! regclass_compatible_p (src_class, dst_class))
1070 {
1071 if (!copy_src)
1072 {
1073 copy_src = src;
1074 copy_dst = dst;
1075 }
1076 continue;
1077 }
1078
1079 /* Can not modify an earlier insn to set dst if this insn
1080 uses an old value in the source. */
1081 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1082 {
1083 if (!copy_src)
1084 {
1085 copy_src = src;
1086 copy_dst = dst;
1087 }
1088 continue;
1089 }
1090
1091 /* If src is set once in a different basic block,
1092 and is set equal to a constant, then do not use
1093 it for this optimization, as this would make it
1094 no longer equivalent to a constant. */
1095
1096 if (reg_is_remote_constant_p (src, insn))
1097 {
1098 if (!copy_src)
1099 {
1100 copy_src = src;
1101 copy_dst = dst;
1102 }
1103 continue;
1104 }
1105
1106
1107 if (dump_file)
1108 fprintf (dump_file,
1109 "Could fix operand %d of insn %d matching operand %d.\n",
1110 op_no, INSN_UID (insn), match_no);
1111
1112 /* Scan backward to find the first instruction that uses
1113 the input operand. If the operand is set here, then
1114 replace it in both instructions with match_no. */
1115
1116 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1117 {
1118 rtx pset;
1119
1120 /* ??? We can't scan past the end of a basic block without
1121 updating the register lifetime info
1122 (REG_DEAD/basic_block_live_at_start). */
1123 if (perhaps_ends_bb_p (p))
1124 break;
1125 else if (! INSN_P (p))
1126 continue;
1127
1128 length++;
1129
1130 /* ??? See if all of SRC is set in P. This test is much
1131 more conservative than it needs to be. */
1132 pset = single_set (p);
1133 if (pset && SET_DEST (pset) == src)
1134 {
1135 /* We use validate_replace_rtx, in case there
1136 are multiple identical source operands. All of
1137 them have to be changed at the same time. */
1138 if (validate_replace_rtx (src, dst, insn))
1139 {
1140 if (validate_change (p, &SET_DEST (pset),
1141 dst, 0))
1142 success = 1;
1143 else
1144 {
1145 /* Change all source operands back.
1146 This modifies the dst as a side-effect. */
1147 validate_replace_rtx (dst, src, insn);
1148 /* Now make sure the dst is right. */
1149 validate_change (insn,
1150 recog_data.operand_loc[match_no],
1151 dst, 0);
1152 }
1153 }
1154 break;
1155 }
1156
1157 /* We can't make this change if SRC is read or
1158 partially written in P, since we are going to
1159 eliminate SRC. We can't make this change
1160 if DST is mentioned at all in P,
1161 since we are going to change its value. */
1162 if (reg_overlap_mentioned_p (src, PATTERN (p))
1163 || reg_mentioned_p (dst, PATTERN (p)))
1164 break;
1165
1166 /* If we have passed a call instruction, and the
1167 pseudo-reg DST is not already live across a call,
1168 then don't perform the optimization. */
1169 if (CALL_P (p))
1170 {
1171 num_calls++;
1172 freq_calls += REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p));
1173
1174 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1175 break;
1176 }
1177 }
1178
1179 if (success)
1180 {
1181 int dstno, srcno;
1182
1183 /* Remove the death note for SRC from INSN. */
1184 remove_note (insn, src_note);
1185 /* Move the death note for SRC to P if it is used
1186 there. */
1187 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1188 {
1189 XEXP (src_note, 1) = REG_NOTES (p);
1190 REG_NOTES (p) = src_note;
1191 }
1192 /* If there is a REG_DEAD note for DST on P, then remove
1193 it, because DST is now set there. */
1194 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1195 remove_note (p, dst_note);
1196
1197 dstno = REGNO (dst);
1198 srcno = REGNO (src);
1199
1200 INC_REG_N_SETS (dstno, 1);
1201 INC_REG_N_SETS (srcno, -1);
1202
1203 REG_N_CALLS_CROSSED (dstno) += num_calls;
1204 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1205 REG_FREQ_CALLS_CROSSED (dstno) += freq_calls;
1206 REG_FREQ_CALLS_CROSSED (srcno) -= freq_calls;
1207
1208 REG_LIVE_LENGTH (dstno) += length;
1209 if (REG_LIVE_LENGTH (srcno) >= 0)
1210 {
1211 REG_LIVE_LENGTH (srcno) -= length;
1212 /* REG_LIVE_LENGTH is only an approximation after
1213 combine if sched is not run, so make sure that we
1214 still have a reasonable value. */
1215 if (REG_LIVE_LENGTH (srcno) < 2)
1216 REG_LIVE_LENGTH (srcno) = 2;
1217 }
1218
1219 if (dump_file)
1220 fprintf (dump_file,
1221 "Fixed operand %d of insn %d matching operand %d.\n",
1222 op_no, INSN_UID (insn), match_no);
1223
1224 break;
1225 }
1226 }
1227
1228 /* If we weren't able to replace any of the alternatives, try an
1229 alternative approach of copying the source to the destination. */
1230 if (!success && copy_src != NULL_RTX)
1231 copy_src_to_dest (insn, copy_src, copy_dst);
1232 }
1233 }
1234
1235 /* Clean up. */
1236 free (regno_src_regno);
1237 if (reg_set_in_bb)
1238 {
1239 free (reg_set_in_bb);
1240 reg_set_in_bb = NULL;
1241 }
1242 regstat_free_n_sets_and_refs ();
1243 regstat_free_ri ();
1244 return 0;
1245 }
1246
1247 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1248 Returns 0 if INSN can't be recognized, or if the alternative can't be
1249 determined.
1250
1251 Initialize the info in MATCHP based on the constraints. */
1252
1253 static int
1254 find_matches (rtx insn, struct match *matchp)
1255 {
1256 int likely_spilled[MAX_RECOG_OPERANDS];
1257 int op_no;
1258 int any_matches = 0;
1259
1260 extract_insn (insn);
1261 if (! constrain_operands (0))
1262 return 0;
1263
1264 /* Must initialize this before main loop, because the code for
1265 the commutative case may set matches for operands other than
1266 the current one. */
1267 for (op_no = recog_data.n_operands; --op_no >= 0; )
1268 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1269
1270 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1271 {
1272 const char *p;
1273 char c;
1274 int i = 0;
1275
1276 p = recog_data.constraints[op_no];
1277
1278 likely_spilled[op_no] = 0;
1279 matchp->use[op_no] = READ;
1280 matchp->early_clobber[op_no] = 0;
1281 if (*p == '=')
1282 matchp->use[op_no] = WRITE;
1283 else if (*p == '+')
1284 matchp->use[op_no] = READWRITE;
1285
1286 for (;*p && i < which_alternative; p++)
1287 if (*p == ',')
1288 i++;
1289
1290 while ((c = *p) != '\0' && c != ',')
1291 {
1292 switch (c)
1293 {
1294 case '=':
1295 break;
1296 case '+':
1297 break;
1298 case '&':
1299 matchp->early_clobber[op_no] = 1;
1300 break;
1301 case '%':
1302 matchp->commutative[op_no] = op_no + 1;
1303 matchp->commutative[op_no + 1] = op_no;
1304 break;
1305
1306 case '0': case '1': case '2': case '3': case '4':
1307 case '5': case '6': case '7': case '8': case '9':
1308 {
1309 char *end;
1310 unsigned long match_ul = strtoul (p, &end, 10);
1311 int match = match_ul;
1312
1313 p = end;
1314
1315 if (match < op_no && likely_spilled[match])
1316 continue;
1317 matchp->with[op_no] = match;
1318 any_matches = 1;
1319 if (matchp->commutative[op_no] >= 0)
1320 matchp->with[matchp->commutative[op_no]] = match;
1321 }
1322 continue;
1323
1324 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1325 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1326 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1327 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1328 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p) ))
1329 likely_spilled[op_no] = 1;
1330 break;
1331 }
1332 p += CONSTRAINT_LEN (c, p);
1333 }
1334 }
1335 return any_matches;
1336 }
1337
1338
1339
1340 static bool
1341 gate_handle_regmove (void)
1342 {
1343 return (optimize > 0 && flag_regmove);
1344 }
1345
1346
1347 struct rtl_opt_pass pass_regmove =
1348 {
1349 {
1350 RTL_PASS,
1351 "regmove", /* name */
1352 gate_handle_regmove, /* gate */
1353 regmove_optimize, /* execute */
1354 NULL, /* sub */
1355 NULL, /* next */
1356 0, /* static_pass_number */
1357 TV_REGMOVE, /* tv_id */
1358 0, /* properties_required */
1359 0, /* properties_provided */
1360 0, /* properties_destroyed */
1361 0, /* todo_flags_start */
1362 TODO_df_finish | TODO_verify_rtl_sharing |
1363 TODO_dump_func |
1364 TODO_ggc_collect /* todo_flags_finish */
1365 }
1366 };
1367