]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/regcprop.c
projects / thirdparty / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
2010-12-17 Nicola Pero <nicola.pero@meta-innovation.com>
[thirdparty/gcc.git] / gcc / regcprop.c
CommitLineData
2d4749b6 1/* Copy propagation on hard registers for the GNU compiler.
02bbc669 2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
3 2010 Free Software Foundation, Inc.
2d4749b6 4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "tm.h"
25#include "rtl.h"
26#include "tm_p.h"
27#include "insn-config.h"
28#include "regs.h"
29#include "addresses.h"
30#include "hard-reg-set.h"
31#include "basic-block.h"
32#include "reload.h"
33#include "output.h"
34#include "function.h"
35#include "recog.h"
36#include "flags.h"
0b205f4c 37#include "diagnostic-core.h"
2d4749b6 38#include "obstack.h"
39#include "timevar.h"
40#include "tree-pass.h"
41#include "df.h"
42
43/* The following code does forward propagation of hard register copies.
44 The object is to eliminate as many dependencies as possible, so that
45 we have the most scheduling freedom. As a side effect, we also clean
46 up some silly register allocation decisions made by reload. This
47 code may be obsoleted by a new register allocator. */
48
2058ec71 49/* DEBUG_INSNs aren't changed right away, as doing so might extend the
50 lifetime of a register and get the DEBUG_INSN subsequently reset.
51 So they are queued instead, and updated only when the register is
52 used in some subsequent real insn before it is set. */
53struct queued_debug_insn_change
54{
55 struct queued_debug_insn_change *next;
56 rtx insn;
57 rtx *loc;
58 rtx new_rtx;
59};
60
2d4749b6 61/* For each register, we have a list of registers that contain the same
62 value. The OLDEST_REGNO field points to the head of the list, and
63 the NEXT_REGNO field runs through the list. The MODE field indicates
64 what mode the data is known to be in; this field is VOIDmode when the
65 register is not known to contain valid data. */
66
67struct value_data_entry
68{
69 enum machine_mode mode;
70 unsigned int oldest_regno;
71 unsigned int next_regno;
2058ec71 72 struct queued_debug_insn_change *debug_insn_changes;
2d4749b6 73};
74
75struct value_data
76{
77 struct value_data_entry e[FIRST_PSEUDO_REGISTER];
78 unsigned int max_value_regs;
2058ec71 79 unsigned int n_debug_insn_changes;
2d4749b6 80};
81
2058ec71 82static alloc_pool debug_insn_changes_pool;
83
2d4749b6 84static void kill_value_one_regno (unsigned, struct value_data *);
85static void kill_value_regno (unsigned, unsigned, struct value_data *);
86static void kill_value (rtx, struct value_data *);
87static void set_value_regno (unsigned, enum machine_mode, struct value_data *);
88static void init_value_data (struct value_data *);
89static void kill_clobbered_value (rtx, const_rtx, void *);
90static void kill_set_value (rtx, const_rtx, void *);
91static int kill_autoinc_value (rtx *, void *);
92static void copy_value (rtx, rtx, struct value_data *);
93static bool mode_change_ok (enum machine_mode, enum machine_mode,
94 unsigned int);
95static rtx maybe_mode_change (enum machine_mode, enum machine_mode,
96 enum machine_mode, unsigned int, unsigned int);
97static rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *);
98static bool replace_oldest_value_reg (rtx *, enum reg_class, rtx,
99 struct value_data *);
100static bool replace_oldest_value_addr (rtx *, enum reg_class,
101 enum machine_mode, rtx,
102 struct value_data *);
103static bool replace_oldest_value_mem (rtx, rtx, struct value_data *);
104static bool copyprop_hardreg_forward_1 (basic_block, struct value_data *);
105extern void debug_value_data (struct value_data *);
106#ifdef ENABLE_CHECKING
107static void validate_value_data (struct value_data *);
108#endif
109
2058ec71 110/* Free all queued updates for DEBUG_INSNs that change some reg to
111 register REGNO. */
112
113static void
114free_debug_insn_changes (struct value_data *vd, unsigned int regno)
115{
116 struct queued_debug_insn_change *cur, *next;
117 for (cur = vd->e[regno].debug_insn_changes; cur; cur = next)
118 {
119 next = cur->next;
120 --vd->n_debug_insn_changes;
121 pool_free (debug_insn_changes_pool, cur);
122 }
123 vd->e[regno].debug_insn_changes = NULL;
124}
125
2d4749b6 126/* Kill register REGNO. This involves removing it from any value
127 lists, and resetting the value mode to VOIDmode. This is only a
128 helper function; it does not handle any hard registers overlapping
129 with REGNO. */
130
131static void
132kill_value_one_regno (unsigned int regno, struct value_data *vd)
133{
134 unsigned int i, next;
135
136 if (vd->e[regno].oldest_regno != regno)
137 {
138 for (i = vd->e[regno].oldest_regno;
139 vd->e[i].next_regno != regno;
140 i = vd->e[i].next_regno)
141 continue;
142 vd->e[i].next_regno = vd->e[regno].next_regno;
143 }
144 else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM)
145 {
146 for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno)
147 vd->e[i].oldest_regno = next;
148 }
149
150 vd->e[regno].mode = VOIDmode;
151 vd->e[regno].oldest_regno = regno;
152 vd->e[regno].next_regno = INVALID_REGNUM;
2058ec71 153 if (vd->e[regno].debug_insn_changes)
154 free_debug_insn_changes (vd, regno);
2d4749b6 155
156#ifdef ENABLE_CHECKING
157 validate_value_data (vd);
158#endif
159}
160
161/* Kill the value in register REGNO for NREGS, and any other registers
162 whose values overlap. */
163
164static void
165kill_value_regno (unsigned int regno, unsigned int nregs,
166 struct value_data *vd)
167{
168 unsigned int j;
169
170 /* Kill the value we're told to kill. */
171 for (j = 0; j < nregs; ++j)
172 kill_value_one_regno (regno + j, vd);
173
174 /* Kill everything that overlapped what we're told to kill. */
175 if (regno < vd->max_value_regs)
176 j = 0;
177 else
178 j = regno - vd->max_value_regs;
179 for (; j < regno; ++j)
180 {
181 unsigned int i, n;
182 if (vd->e[j].mode == VOIDmode)
183 continue;
184 n = hard_regno_nregs[j][vd->e[j].mode];
185 if (j + n > regno)
186 for (i = 0; i < n; ++i)
187 kill_value_one_regno (j + i, vd);
188 }
189}
190
191/* Kill X. This is a convenience function wrapping kill_value_regno
192 so that we mind the mode the register is in. */
193
194static void
195kill_value (rtx x, struct value_data *vd)
196{
197 rtx orig_rtx = x;
198
199 if (GET_CODE (x) == SUBREG)
200 {
201 x = simplify_subreg (GET_MODE (x), SUBREG_REG (x),
202 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
203 if (x == NULL_RTX)
204 x = SUBREG_REG (orig_rtx);
205 }
206 if (REG_P (x))
207 {
208 unsigned int regno = REGNO (x);
209 unsigned int n = hard_regno_nregs[regno][GET_MODE (x)];
210
211 kill_value_regno (regno, n, vd);
212 }
213}
214
215/* Remember that REGNO is valid in MODE. */
216
217static void
218set_value_regno (unsigned int regno, enum machine_mode mode,
219 struct value_data *vd)
220{
221 unsigned int nregs;
222
223 vd->e[regno].mode = mode;
224
225 nregs = hard_regno_nregs[regno][mode];
226 if (nregs > vd->max_value_regs)
227 vd->max_value_regs = nregs;
228}
229
230/* Initialize VD such that there are no known relationships between regs. */
231
232static void
233init_value_data (struct value_data *vd)
234{
235 int i;
236 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
237 {
238 vd->e[i].mode = VOIDmode;
239 vd->e[i].oldest_regno = i;
240 vd->e[i].next_regno = INVALID_REGNUM;
2058ec71 241 vd->e[i].debug_insn_changes = NULL;
2d4749b6 242 }
243 vd->max_value_regs = 0;
2058ec71 244 vd->n_debug_insn_changes = 0;
2d4749b6 245}
246
247/* Called through note_stores. If X is clobbered, kill its value. */
248
249static void
250kill_clobbered_value (rtx x, const_rtx set, void *data)
251{
252 struct value_data *const vd = (struct value_data *) data;
253 if (GET_CODE (set) == CLOBBER)
254 kill_value (x, vd);
255}
256
257/* Called through note_stores. If X is set, not clobbered, kill its
258 current value and install it as the root of its own value list. */
259
260static void
261kill_set_value (rtx x, const_rtx set, void *data)
262{
263 struct value_data *const vd = (struct value_data *) data;
264 if (GET_CODE (set) != CLOBBER)
265 {
266 kill_value (x, vd);
267 if (REG_P (x))
268 set_value_regno (REGNO (x), GET_MODE (x), vd);
269 }
270}
271
272/* Called through for_each_rtx. Kill any register used as the base of an
273 auto-increment expression, and install that register as the root of its
274 own value list. */
275
276static int
277kill_autoinc_value (rtx *px, void *data)
278{
279 rtx x = *px;
280 struct value_data *const vd = (struct value_data *) data;
281
282 if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
283 {
284 x = XEXP (x, 0);
285 kill_value (x, vd);
98155838 286 set_value_regno (REGNO (x), GET_MODE (x), vd);
2d4749b6 287 return -1;
288 }
289
290 return 0;
291}
292
293/* Assert that SRC has been copied to DEST. Adjust the data structures
294 to reflect that SRC contains an older copy of the shared value. */
295
296static void
297copy_value (rtx dest, rtx src, struct value_data *vd)
298{
299 unsigned int dr = REGNO (dest);
300 unsigned int sr = REGNO (src);
301 unsigned int dn, sn;
302 unsigned int i;
303
304 /* ??? At present, it's possible to see noop sets. It'd be nice if
305 this were cleaned up beforehand... */
306 if (sr == dr)
307 return;
308
309 /* Do not propagate copies to the stack pointer, as that can leave
310 memory accesses with no scheduling dependency on the stack update. */
311 if (dr == STACK_POINTER_REGNUM)
312 return;
313
314 /* Likewise with the frame pointer, if we're using one. */
315 if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM)
316 return;
317
318 /* Do not propagate copies to fixed or global registers, patterns
319 can be relying to see particular fixed register or users can
320 expect the chosen global register in asm. */
321 if (fixed_regs[dr] || global_regs[dr])
322 return;
323
324 /* If SRC and DEST overlap, don't record anything. */
325 dn = hard_regno_nregs[dr][GET_MODE (dest)];
326 sn = hard_regno_nregs[sr][GET_MODE (dest)];
327 if ((dr > sr && dr < sr + sn)
328 || (sr > dr && sr < dr + dn))
329 return;
330
331 /* If SRC had no assigned mode (i.e. we didn't know it was live)
332 assign it now and assume the value came from an input argument
333 or somesuch. */
334 if (vd->e[sr].mode == VOIDmode)
335 set_value_regno (sr, vd->e[dr].mode, vd);
336
337 /* If we are narrowing the input to a smaller number of hard regs,
338 and it is in big endian, we are really extracting a high part.
339 Since we generally associate a low part of a value with the value itself,
340 we must not do the same for the high part.
341 Note we can still get low parts for the same mode combination through
342 a two-step copy involving differently sized hard regs.
343 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
344 (set (reg:DI r0) (reg:DI fr0))
345 (set (reg:SI fr2) (reg:SI r0))
346 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
347 (set (reg:SI fr2) (reg:SI fr0))
348 loads the high part of (reg:DI fr0) into fr2.
349
350 We can't properly represent the latter case in our tables, so don't
351 record anything then. */
352 else if (sn < (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode]
353 && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD
354 ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
355 return;
356
357 /* If SRC had been assigned a mode narrower than the copy, we can't
358 link DEST into the chain, because not all of the pieces of the
359 copy came from oldest_regno. */
360 else if (sn > (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode])
361 return;
362
363 /* Link DR at the end of the value chain used by SR. */
364
365 vd->e[dr].oldest_regno = vd->e[sr].oldest_regno;
366
367 for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno)
368 continue;
369 vd->e[i].next_regno = dr;
370
371#ifdef ENABLE_CHECKING
372 validate_value_data (vd);
373#endif
374}
375
376/* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
377
378static bool
379mode_change_ok (enum machine_mode orig_mode, enum machine_mode new_mode,
380 unsigned int regno ATTRIBUTE_UNUSED)
381{
382 if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode))
383 return false;
384
385#ifdef CANNOT_CHANGE_MODE_CLASS
386 return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode);
387#endif
388
389 return true;
390}
391
392/* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
393 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
394 in NEW_MODE.
395 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
396
397static rtx
398maybe_mode_change (enum machine_mode orig_mode, enum machine_mode copy_mode,
399 enum machine_mode new_mode, unsigned int regno,
400 unsigned int copy_regno ATTRIBUTE_UNUSED)
401{
402 if (GET_MODE_SIZE (copy_mode) < GET_MODE_SIZE (orig_mode)
403 && GET_MODE_SIZE (copy_mode) < GET_MODE_SIZE (new_mode))
404 return NULL_RTX;
405
406 if (orig_mode == new_mode)
407 return gen_rtx_raw_REG (new_mode, regno);
408 else if (mode_change_ok (orig_mode, new_mode, regno))
409 {
410 int copy_nregs = hard_regno_nregs[copy_regno][copy_mode];
411 int use_nregs = hard_regno_nregs[copy_regno][new_mode];
412 int copy_offset
413 = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs);
414 int offset
415 = GET_MODE_SIZE (orig_mode) - GET_MODE_SIZE (new_mode) - copy_offset;
416 int byteoffset = offset % UNITS_PER_WORD;
417 int wordoffset = offset - byteoffset;
418
419 offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0)
420 + (BYTES_BIG_ENDIAN ? byteoffset : 0));
421 return gen_rtx_raw_REG (new_mode,
422 regno + subreg_regno_offset (regno, orig_mode,
423 offset,
424 new_mode));
425 }
426 return NULL_RTX;
427}
428
429/* Find the oldest copy of the value contained in REGNO that is in
430 register class CL and has mode MODE. If found, return an rtx
431 of that oldest register, otherwise return NULL. */
432
433static rtx
434find_oldest_value_reg (enum reg_class cl, rtx reg, struct value_data *vd)
435{
436 unsigned int regno = REGNO (reg);
437 enum machine_mode mode = GET_MODE (reg);
438 unsigned int i;
439
440 /* If we are accessing REG in some mode other that what we set it in,
441 make sure that the replacement is valid. In particular, consider
442 (set (reg:DI r11) (...))
443 (set (reg:SI r9) (reg:SI r11))
444 (set (reg:SI r10) (...))
445 (set (...) (reg:DI r9))
446 Replacing r9 with r11 is invalid. */
447 if (mode != vd->e[regno].mode)
448 {
449 if (hard_regno_nregs[regno][mode]
450 > hard_regno_nregs[regno][vd->e[regno].mode])
451 return NULL_RTX;
452 }
453
454 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno)
455 {
456 enum machine_mode oldmode = vd->e[i].mode;
457 rtx new_rtx;
458
459 if (!in_hard_reg_set_p (reg_class_contents[cl], mode, i))
460 return NULL_RTX;
461
462 new_rtx = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno);
463 if (new_rtx)
464 {
465 ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (reg);
466 REG_ATTRS (new_rtx) = REG_ATTRS (reg);
467 REG_POINTER (new_rtx) = REG_POINTER (reg);
468 return new_rtx;
469 }
470 }
471
472 return NULL_RTX;
473}
474
475/* If possible, replace the register at *LOC with the oldest register
476 in register class CL. Return true if successfully replaced. */
477
478static bool
479replace_oldest_value_reg (rtx *loc, enum reg_class cl, rtx insn,
480 struct value_data *vd)
481{
482 rtx new_rtx = find_oldest_value_reg (cl, *loc, vd);
483 if (new_rtx)
484 {
2058ec71 485 if (DEBUG_INSN_P (insn))
486 {
487 struct queued_debug_insn_change *change;
488
489 if (dump_file)
490 fprintf (dump_file, "debug_insn %u: queued replacing reg %u with %u\n",
491 INSN_UID (insn), REGNO (*loc), REGNO (new_rtx));
492
493 change = (struct queued_debug_insn_change *)
494 pool_alloc (debug_insn_changes_pool);
495 change->next = vd->e[REGNO (new_rtx)].debug_insn_changes;
496 change->insn = insn;
497 change->loc = loc;
498 change->new_rtx = new_rtx;
499 vd->e[REGNO (new_rtx)].debug_insn_changes = change;
500 ++vd->n_debug_insn_changes;
501 return true;
502 }
2d4749b6 503 if (dump_file)
504 fprintf (dump_file, "insn %u: replaced reg %u with %u\n",
505 INSN_UID (insn), REGNO (*loc), REGNO (new_rtx));
506
507 validate_change (insn, loc, new_rtx, 1);
508 return true;
509 }
510 return false;
511}
512
513/* Similar to replace_oldest_value_reg, but *LOC contains an address.
514 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
515 BASE_REG_CLASS depending on how the register is being considered. */
516
517static bool
518replace_oldest_value_addr (rtx *loc, enum reg_class cl,
519 enum machine_mode mode, rtx insn,
520 struct value_data *vd)
521{
522 rtx x = *loc;
523 RTX_CODE code = GET_CODE (x);
524 const char *fmt;
525 int i, j;
526 bool changed = false;
527
528 switch (code)
529 {
530 case PLUS:
9845d120 531 if (DEBUG_INSN_P (insn))
532 break;
533
2d4749b6 534 {
535 rtx orig_op0 = XEXP (x, 0);
536 rtx orig_op1 = XEXP (x, 1);
537 RTX_CODE code0 = GET_CODE (orig_op0);
538 RTX_CODE code1 = GET_CODE (orig_op1);
539 rtx op0 = orig_op0;
540 rtx op1 = orig_op1;
541 rtx *locI = NULL;
542 rtx *locB = NULL;
543 enum rtx_code index_code = SCRATCH;
544
545 if (GET_CODE (op0) == SUBREG)
546 {
547 op0 = SUBREG_REG (op0);
548 code0 = GET_CODE (op0);
549 }
550
551 if (GET_CODE (op1) == SUBREG)
552 {
553 op1 = SUBREG_REG (op1);
554 code1 = GET_CODE (op1);
555 }
556
557 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
558 || code0 == ZERO_EXTEND || code1 == MEM)
559 {
560 locI = &XEXP (x, 0);
561 locB = &XEXP (x, 1);
562 index_code = GET_CODE (*locI);
563 }
564 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
565 || code1 == ZERO_EXTEND || code0 == MEM)
566 {
567 locI = &XEXP (x, 1);
568 locB = &XEXP (x, 0);
569 index_code = GET_CODE (*locI);
570 }
571 else if (code0 == CONST_INT || code0 == CONST
572 || code0 == SYMBOL_REF || code0 == LABEL_REF)
573 {
574 locB = &XEXP (x, 1);
575 index_code = GET_CODE (XEXP (x, 0));
576 }
577 else if (code1 == CONST_INT || code1 == CONST
578 || code1 == SYMBOL_REF || code1 == LABEL_REF)
579 {
580 locB = &XEXP (x, 0);
581 index_code = GET_CODE (XEXP (x, 1));
582 }
583 else if (code0 == REG && code1 == REG)
584 {
585 int index_op;
586 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
587
588 if (REGNO_OK_FOR_INDEX_P (regno1)
589 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
590 index_op = 1;
591 else if (REGNO_OK_FOR_INDEX_P (regno0)
592 && regno_ok_for_base_p (regno1, mode, PLUS, REG))
593 index_op = 0;
594 else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
595 || REGNO_OK_FOR_INDEX_P (regno1))
596 index_op = 1;
597 else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
598 index_op = 0;
599 else
600 index_op = 1;
601
602 locI = &XEXP (x, index_op);
603 locB = &XEXP (x, !index_op);
604 index_code = GET_CODE (*locI);
605 }
606 else if (code0 == REG)
607 {
608 locI = &XEXP (x, 0);
609 locB = &XEXP (x, 1);
610 index_code = GET_CODE (*locI);
611 }
612 else if (code1 == REG)
613 {
614 locI = &XEXP (x, 1);
615 locB = &XEXP (x, 0);
616 index_code = GET_CODE (*locI);
617 }
618
619 if (locI)
620 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode,
621 insn, vd);
622 if (locB)
623 changed |= replace_oldest_value_addr (locB,
624 base_reg_class (mode, PLUS,
625 index_code),
626 mode, insn, vd);
627 return changed;
628 }
629
630 case POST_INC:
631 case POST_DEC:
632 case POST_MODIFY:
633 case PRE_INC:
634 case PRE_DEC:
635 case PRE_MODIFY:
636 return false;
637
638 case MEM:
639 return replace_oldest_value_mem (x, insn, vd);
640
641 case REG:
642 return replace_oldest_value_reg (loc, cl, insn, vd);
643
644 default:
645 break;
646 }
647
648 fmt = GET_RTX_FORMAT (code);
649 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
650 {
651 if (fmt[i] == 'e')
652 changed |= replace_oldest_value_addr (&XEXP (x, i), cl, mode,
653 insn, vd);
654 else if (fmt[i] == 'E')
655 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
656 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), cl,
657 mode, insn, vd);
658 }
659
660 return changed;
661}
662
663/* Similar to replace_oldest_value_reg, but X contains a memory. */
664
665static bool
666replace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd)
667{
9845d120 668 enum reg_class cl;
669
670 if (DEBUG_INSN_P (insn))
671 cl = ALL_REGS;
672 else
673 cl = base_reg_class (GET_MODE (x), MEM, SCRATCH);
674
675 return replace_oldest_value_addr (&XEXP (x, 0), cl,
2d4749b6 676 GET_MODE (x), insn, vd);
677}
678
2058ec71 679/* Apply all queued updates for DEBUG_INSNs that change some reg to
680 register REGNO. */
681
682static void
683apply_debug_insn_changes (struct value_data *vd, unsigned int regno)
684{
685 struct queued_debug_insn_change *change;
686 rtx last_insn = vd->e[regno].debug_insn_changes->insn;
687
688 for (change = vd->e[regno].debug_insn_changes;
689 change;
690 change = change->next)
691 {
692 if (last_insn != change->insn)
693 {
694 apply_change_group ();
695 last_insn = change->insn;
696 }
697 validate_change (change->insn, change->loc, change->new_rtx, 1);
698 }
699 apply_change_group ();
700}
701
702/* Called via for_each_rtx, for all used registers in a real
703 insn apply DEBUG_INSN changes that change registers to the
704 used register. */
705
706static int
707cprop_find_used_regs_1 (rtx *loc, void *data)
708{
709 if (REG_P (*loc))
710 {
711 struct value_data *vd = (struct value_data *) data;
712 if (vd->e[REGNO (*loc)].debug_insn_changes)
713 {
714 apply_debug_insn_changes (vd, REGNO (*loc));
715 free_debug_insn_changes (vd, REGNO (*loc));
716 }
717 }
718 return 0;
719}
720
721/* Called via note_uses, for all used registers in a real insn
722 apply DEBUG_INSN changes that change registers to the used
723 registers. */
724
725static void
726cprop_find_used_regs (rtx *loc, void *vd)
727{
728 for_each_rtx (loc, cprop_find_used_regs_1, vd);
729}
730
2d4749b6 731/* Perform the forward copy propagation on basic block BB. */
732
733static bool
734copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd)
735{
9845d120 736 bool anything_changed = false;
2d4749b6 737 rtx insn;
738
739 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
740 {
741 int n_ops, i, alt, predicated;
742 bool is_asm, any_replacements;
743 rtx set;
744 bool replaced[MAX_RECOG_OPERANDS];
9845d120 745 bool changed = false;
2d4749b6 746
9845d120 747 if (!NONDEBUG_INSN_P (insn))
2d4749b6 748 {
9845d120 749 if (DEBUG_INSN_P (insn))
750 {
751 rtx loc = INSN_VAR_LOCATION_LOC (insn);
2058ec71 752 if (!VAR_LOC_UNKNOWN_P (loc))
753 replace_oldest_value_addr (&INSN_VAR_LOCATION_LOC (insn),
754 ALL_REGS, GET_MODE (loc),
755 insn, vd);
9845d120 756 }
757
2d4749b6 758 if (insn == BB_END (bb))
759 break;
760 else
761 continue;
762 }
763
764 set = single_set (insn);
765 extract_insn (insn);
766 if (! constrain_operands (1))
767 fatal_insn_not_found (insn);
768 preprocess_constraints ();
769 alt = which_alternative;
770 n_ops = recog_data.n_operands;
771 is_asm = asm_noperands (PATTERN (insn)) >= 0;
772
773 /* Simplify the code below by rewriting things to reflect
774 matching constraints. Also promote OP_OUT to OP_INOUT
775 in predicated instructions. */
776
777 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
778 for (i = 0; i < n_ops; ++i)
779 {
780 int matches = recog_op_alt[i][alt].matches;
781 if (matches >= 0)
782 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
783 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
784 || (predicated && recog_data.operand_type[i] == OP_OUT))
785 recog_data.operand_type[i] = OP_INOUT;
786 }
787
2058ec71 788 /* Apply changes to earlier DEBUG_INSNs if possible. */
789 if (vd->n_debug_insn_changes)
790 note_uses (&PATTERN (insn), cprop_find_used_regs, vd);
791
2d4749b6 792 /* For each earlyclobber operand, zap the value data. */
793 for (i = 0; i < n_ops; i++)
794 if (recog_op_alt[i][alt].earlyclobber)
795 kill_value (recog_data.operand[i], vd);
796
797 /* Within asms, a clobber cannot overlap inputs or outputs.
798 I wouldn't think this were true for regular insns, but
799 scan_rtx treats them like that... */
800 note_stores (PATTERN (insn), kill_clobbered_value, vd);
801
802 /* Kill all auto-incremented values. */
803 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
804 for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd);
805
806 /* Kill all early-clobbered operands. */
807 for (i = 0; i < n_ops; i++)
808 if (recog_op_alt[i][alt].earlyclobber)
809 kill_value (recog_data.operand[i], vd);
810
811 /* Special-case plain move instructions, since we may well
812 be able to do the move from a different register class. */
813 if (set && REG_P (SET_SRC (set)))
814 {
815 rtx src = SET_SRC (set);
816 unsigned int regno = REGNO (src);
817 enum machine_mode mode = GET_MODE (src);
818 unsigned int i;
819 rtx new_rtx;
820
821 /* If we are accessing SRC in some mode other that what we
822 set it in, make sure that the replacement is valid. */
823 if (mode != vd->e[regno].mode)
824 {
825 if (hard_regno_nregs[regno][mode]
826 > hard_regno_nregs[regno][vd->e[regno].mode])
827 goto no_move_special_case;
828 }
829
830 /* If the destination is also a register, try to find a source
831 register in the same class. */
832 if (REG_P (SET_DEST (set)))
833 {
834 new_rtx = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd);
835 if (new_rtx && validate_change (insn, &SET_SRC (set), new_rtx, 0))
836 {
837 if (dump_file)
838 fprintf (dump_file,
839 "insn %u: replaced reg %u with %u\n",
840 INSN_UID (insn), regno, REGNO (new_rtx));
841 changed = true;
842 goto did_replacement;
843 }
844 }
845
846 /* Otherwise, try all valid registers and see if its valid. */
847 for (i = vd->e[regno].oldest_regno; i != regno;
848 i = vd->e[i].next_regno)
849 {
850 new_rtx = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode,
851 mode, i, regno);
852 if (new_rtx != NULL_RTX)
853 {
854 if (validate_change (insn, &SET_SRC (set), new_rtx, 0))
855 {
856 ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (src);
857 REG_ATTRS (new_rtx) = REG_ATTRS (src);
858 REG_POINTER (new_rtx) = REG_POINTER (src);
859 if (dump_file)
860 fprintf (dump_file,
861 "insn %u: replaced reg %u with %u\n",
862 INSN_UID (insn), regno, REGNO (new_rtx));
863 changed = true;
864 goto did_replacement;
865 }
866 }
867 }
868 }
869 no_move_special_case:
870
871 any_replacements = false;
872
873 /* For each input operand, replace a hard register with the
874 eldest live copy that's in an appropriate register class. */
875 for (i = 0; i < n_ops; i++)
876 {
877 replaced[i] = false;
878
879 /* Don't scan match_operand here, since we've no reg class
880 information to pass down. Any operands that we could
881 substitute in will be represented elsewhere. */
882 if (recog_data.constraints[i][0] == '\0')
883 continue;
884
885 /* Don't replace in asms intentionally referencing hard regs. */
886 if (is_asm && REG_P (recog_data.operand[i])
887 && (REGNO (recog_data.operand[i])
888 == ORIGINAL_REGNO (recog_data.operand[i])))
889 continue;
890
891 if (recog_data.operand_type[i] == OP_IN)
892 {
893 if (recog_op_alt[i][alt].is_address)
894 replaced[i]
895 = replace_oldest_value_addr (recog_data.operand_loc[i],
896 recog_op_alt[i][alt].cl,
897 VOIDmode, insn, vd);
898 else if (REG_P (recog_data.operand[i]))
899 replaced[i]
900 = replace_oldest_value_reg (recog_data.operand_loc[i],
901 recog_op_alt[i][alt].cl,
902 insn, vd);
903 else if (MEM_P (recog_data.operand[i]))
904 replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
905 insn, vd);
906 }
907 else if (MEM_P (recog_data.operand[i]))
908 replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
909 insn, vd);
910
911 /* If we performed any replacement, update match_dups. */
912 if (replaced[i])
913 {
914 int j;
915 rtx new_rtx;
916
917 new_rtx = *recog_data.operand_loc[i];
918 recog_data.operand[i] = new_rtx;
919 for (j = 0; j < recog_data.n_dups; j++)
920 if (recog_data.dup_num[j] == i)
921 validate_unshare_change (insn, recog_data.dup_loc[j], new_rtx, 1);
922
923 any_replacements = true;
924 }
925 }
926
927 if (any_replacements)
928 {
929 if (! apply_change_group ())
930 {
931 for (i = 0; i < n_ops; i++)
932 if (replaced[i])
933 {
934 rtx old = *recog_data.operand_loc[i];
935 recog_data.operand[i] = old;
936 }
937
938 if (dump_file)
939 fprintf (dump_file,
940 "insn %u: reg replacements not verified\n",
941 INSN_UID (insn));
942 }
943 else
944 changed = true;
945 }
946
947 did_replacement:
9845d120 948 if (changed)
c7458ee3 949 {
950 anything_changed = true;
951
952 /* If something changed, perhaps further changes to earlier
953 DEBUG_INSNs can be applied. */
954 if (vd->n_debug_insn_changes)
955 note_uses (&PATTERN (insn), cprop_find_used_regs, vd);
956 }
9845d120 957
2d4749b6 958 /* Clobber call-clobbered registers. */
959 if (CALL_P (insn))
960 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
961 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
962 kill_value_regno (i, 1, vd);
963
964 /* Notice stores. */
965 note_stores (PATTERN (insn), kill_set_value, vd);
966
967 /* Notice copies. */
968 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
969 copy_value (SET_DEST (set), SET_SRC (set), vd);
970
971 if (insn == BB_END (bb))
972 break;
973 }
974
9845d120 975 return anything_changed;
2d4749b6 976}
977
978/* Main entry point for the forward copy propagation optimization. */
979
980static unsigned int
981copyprop_hardreg_forward (void)
982{
983 struct value_data *all_vd;
984 basic_block bb;
985 sbitmap visited;
2058ec71 986 bool analyze_called = false;
2d4749b6 987
988 all_vd = XNEWVEC (struct value_data, last_basic_block);
989
990 visited = sbitmap_alloc (last_basic_block);
991 sbitmap_zero (visited);
992
2058ec71 993 if (MAY_HAVE_DEBUG_STMTS)
994 debug_insn_changes_pool
995 = create_alloc_pool ("debug insn changes pool",
996 sizeof (struct queued_debug_insn_change), 256);
997
2d4749b6 998 FOR_EACH_BB (bb)
999 {
1000 SET_BIT (visited, bb->index);
1001
1002 /* If a block has a single predecessor, that we've already
1003 processed, begin with the value data that was live at
1004 the end of the predecessor block. */
1005 /* ??? Ought to use more intelligent queuing of blocks. */
48e1416a 1006 if (single_pred_p (bb)
2d4749b6 1007 && TEST_BIT (visited, single_pred (bb)->index)
1008 && ! (single_pred_edge (bb)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
2058ec71 1009 {
1010 all_vd[bb->index] = all_vd[single_pred (bb)->index];
1011 if (all_vd[bb->index].n_debug_insn_changes)
1012 {
1013 unsigned int regno;
1014
1015 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1016 {
1017 if (all_vd[bb->index].e[regno].debug_insn_changes)
1018 {
1019 all_vd[bb->index].e[regno].debug_insn_changes = NULL;
1020 if (--all_vd[bb->index].n_debug_insn_changes == 0)
1021 break;
1022 }
1023 }
1024 }
1025 }
2d4749b6 1026 else
1027 init_value_data (all_vd + bb->index);
1028
1029 copyprop_hardreg_forward_1 (bb, all_vd + bb->index);
1030 }
1031
2058ec71 1032 if (MAY_HAVE_DEBUG_STMTS)
1033 {
1034 FOR_EACH_BB (bb)
1035 if (TEST_BIT (visited, bb->index)
1036 && all_vd[bb->index].n_debug_insn_changes)
1037 {
1038 unsigned int regno;
1039 bitmap live;
1040
1041 if (!analyze_called)
1042 {
1043 df_analyze ();
1044 analyze_called = true;
1045 }
1046 live = df_get_live_out (bb);
1047 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1048 if (all_vd[bb->index].e[regno].debug_insn_changes)
1049 {
1050 if (REGNO_REG_SET_P (live, regno))
1051 apply_debug_insn_changes (all_vd + bb->index, regno);
1052 if (all_vd[bb->index].n_debug_insn_changes == 0)
1053 break;
1054 }
1055 }
1056
1057 free_alloc_pool (debug_insn_changes_pool);
1058 }
1059
48e1416a 1060 sbitmap_free (visited);
2d4749b6 1061 free (all_vd);
1062 return 0;
1063}
1064
1065/* Dump the value chain data to stderr. */
1066
4b987fac 1067DEBUG_FUNCTION void
2d4749b6 1068debug_value_data (struct value_data *vd)
1069{
1070 HARD_REG_SET set;
1071 unsigned int i, j;
1072
1073 CLEAR_HARD_REG_SET (set);
1074
1075 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1076 if (vd->e[i].oldest_regno == i)
1077 {
1078 if (vd->e[i].mode == VOIDmode)
1079 {
1080 if (vd->e[i].next_regno != INVALID_REGNUM)
1081 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n",
1082 i, vd->e[i].next_regno);
1083 continue;
1084 }
1085
1086 SET_HARD_REG_BIT (set, i);
1087 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode));
1088
1089 for (j = vd->e[i].next_regno;
1090 j != INVALID_REGNUM;
1091 j = vd->e[j].next_regno)
1092 {
1093 if (TEST_HARD_REG_BIT (set, j))
1094 {
1095 fprintf (stderr, "[%u] Loop in regno chain\n", j);
1096 return;
1097 }
1098
1099 if (vd->e[j].oldest_regno != i)
1100 {
1101 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n",
1102 j, vd->e[j].oldest_regno);
1103 return;
1104 }
1105 SET_HARD_REG_BIT (set, j);
1106 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode));
1107 }
1108 fputc ('\n', stderr);
1109 }
1110
1111 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1112 if (! TEST_HARD_REG_BIT (set, i)
1113 && (vd->e[i].mode != VOIDmode
1114 || vd->e[i].oldest_regno != i
1115 || vd->e[i].next_regno != INVALID_REGNUM))
1116 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n",
1117 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1118 vd->e[i].next_regno);
1119}
1120
1121#ifdef ENABLE_CHECKING
1122static void
1123validate_value_data (struct value_data *vd)
1124{
1125 HARD_REG_SET set;
1126 unsigned int i, j;
1127
1128 CLEAR_HARD_REG_SET (set);
1129
1130 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1131 if (vd->e[i].oldest_regno == i)
1132 {
1133 if (vd->e[i].mode == VOIDmode)
1134 {
1135 if (vd->e[i].next_regno != INVALID_REGNUM)
1136 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1137 i, vd->e[i].next_regno);
1138 continue;
1139 }
1140
1141 SET_HARD_REG_BIT (set, i);
1142
1143 for (j = vd->e[i].next_regno;
1144 j != INVALID_REGNUM;
1145 j = vd->e[j].next_regno)
1146 {
1147 if (TEST_HARD_REG_BIT (set, j))
1148 internal_error ("validate_value_data: Loop in regno chain (%u)",
1149 j);
1150 if (vd->e[j].oldest_regno != i)
1151 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1152 j, vd->e[j].oldest_regno);
1153
1154 SET_HARD_REG_BIT (set, j);
1155 }
1156 }
1157
1158 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1159 if (! TEST_HARD_REG_BIT (set, i)
1160 && (vd->e[i].mode != VOIDmode
1161 || vd->e[i].oldest_regno != i
1162 || vd->e[i].next_regno != INVALID_REGNUM))
1163 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1164 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1165 vd->e[i].next_regno);
1166}
1167#endif
1168\f
1169static bool
1170gate_handle_cprop (void)
1171{
1172 return (optimize > 0 && (flag_cprop_registers));
1173}
1174
1175
1176struct rtl_opt_pass pass_cprop_hardreg =
1177{
1178 {
1179 RTL_PASS,
1180 "cprop_hardreg", /* name */
1181 gate_handle_cprop, /* gate */
1182 copyprop_hardreg_forward, /* execute */
1183 NULL, /* sub */
1184 NULL, /* next */
1185 0, /* static_pass_number */
1186 TV_CPROP_REGISTERS, /* tv_id */
1187 0, /* properties_required */
1188 0, /* properties_provided */
1189 0, /* properties_destroyed */
1190 0, /* todo_flags_start */
2058ec71 1191 TODO_dump_func | TODO_df_finish
1192 | TODO_verify_rtl_sharing /* todo_flags_finish */
2d4749b6 1193 }
1194};
Mirror of https://gcc.gnu.org/git/gcc.git