]> 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
* config/spu/spu.md ("vec_permv16qi"): Reduce selector modulo 32
[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));
3a45e441 421 regno += subreg_regno_offset (regno, orig_mode, offset, new_mode);
422 if (HARD_REGNO_MODE_OK (regno, new_mode))
423 return gen_rtx_raw_REG (new_mode, regno);
2d4749b6 424 }
425 return NULL_RTX;
426}
427
428/* Find the oldest copy of the value contained in REGNO that is in
429 register class CL and has mode MODE. If found, return an rtx
430 of that oldest register, otherwise return NULL. */
431
432static rtx
433find_oldest_value_reg (enum reg_class cl, rtx reg, struct value_data *vd)
434{
435 unsigned int regno = REGNO (reg);
436 enum machine_mode mode = GET_MODE (reg);
437 unsigned int i;
438
439 /* If we are accessing REG in some mode other that what we set it in,
440 make sure that the replacement is valid. In particular, consider
441 (set (reg:DI r11) (...))
442 (set (reg:SI r9) (reg:SI r11))
443 (set (reg:SI r10) (...))
444 (set (...) (reg:DI r9))
445 Replacing r9 with r11 is invalid. */
446 if (mode != vd->e[regno].mode)
447 {
448 if (hard_regno_nregs[regno][mode]
449 > hard_regno_nregs[regno][vd->e[regno].mode])
450 return NULL_RTX;
451 }
452
453 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno)
454 {
455 enum machine_mode oldmode = vd->e[i].mode;
456 rtx new_rtx;
457
458 if (!in_hard_reg_set_p (reg_class_contents[cl], mode, i))
75219367 459 continue;
2d4749b6 460
461 new_rtx = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno);
462 if (new_rtx)
463 {
464 ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (reg);
465 REG_ATTRS (new_rtx) = REG_ATTRS (reg);
466 REG_POINTER (new_rtx) = REG_POINTER (reg);
467 return new_rtx;
468 }
469 }
470
471 return NULL_RTX;
472}
473
474/* If possible, replace the register at *LOC with the oldest register
475 in register class CL. Return true if successfully replaced. */
476
477static bool
478replace_oldest_value_reg (rtx *loc, enum reg_class cl, rtx insn,
479 struct value_data *vd)
480{
481 rtx new_rtx = find_oldest_value_reg (cl, *loc, vd);
482 if (new_rtx)
483 {
2058ec71 484 if (DEBUG_INSN_P (insn))
485 {
486 struct queued_debug_insn_change *change;
487
488 if (dump_file)
489 fprintf (dump_file, "debug_insn %u: queued replacing reg %u with %u\n",
490 INSN_UID (insn), REGNO (*loc), REGNO (new_rtx));
491
492 change = (struct queued_debug_insn_change *)
493 pool_alloc (debug_insn_changes_pool);
494 change->next = vd->e[REGNO (new_rtx)].debug_insn_changes;
495 change->insn = insn;
496 change->loc = loc;
497 change->new_rtx = new_rtx;
498 vd->e[REGNO (new_rtx)].debug_insn_changes = change;
499 ++vd->n_debug_insn_changes;
500 return true;
501 }
2d4749b6 502 if (dump_file)
503 fprintf (dump_file, "insn %u: replaced reg %u with %u\n",
504 INSN_UID (insn), REGNO (*loc), REGNO (new_rtx));
505
506 validate_change (insn, loc, new_rtx, 1);
507 return true;
508 }
509 return false;
510}
511
512/* Similar to replace_oldest_value_reg, but *LOC contains an address.
513 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
514 BASE_REG_CLASS depending on how the register is being considered. */
515
516static bool
517replace_oldest_value_addr (rtx *loc, enum reg_class cl,
518 enum machine_mode mode, rtx insn,
519 struct value_data *vd)
520{
521 rtx x = *loc;
522 RTX_CODE code = GET_CODE (x);
523 const char *fmt;
524 int i, j;
525 bool changed = false;
526
527 switch (code)
528 {
529 case PLUS:
9845d120 530 if (DEBUG_INSN_P (insn))
531 break;
532
2d4749b6 533 {
534 rtx orig_op0 = XEXP (x, 0);
535 rtx orig_op1 = XEXP (x, 1);
536 RTX_CODE code0 = GET_CODE (orig_op0);
537 RTX_CODE code1 = GET_CODE (orig_op1);
538 rtx op0 = orig_op0;
539 rtx op1 = orig_op1;
540 rtx *locI = NULL;
541 rtx *locB = NULL;
542 enum rtx_code index_code = SCRATCH;
543
544 if (GET_CODE (op0) == SUBREG)
545 {
546 op0 = SUBREG_REG (op0);
547 code0 = GET_CODE (op0);
548 }
549
550 if (GET_CODE (op1) == SUBREG)
551 {
552 op1 = SUBREG_REG (op1);
553 code1 = GET_CODE (op1);
554 }
555
556 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
557 || code0 == ZERO_EXTEND || code1 == MEM)
558 {
559 locI = &XEXP (x, 0);
560 locB = &XEXP (x, 1);
561 index_code = GET_CODE (*locI);
562 }
563 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
564 || code1 == ZERO_EXTEND || code0 == MEM)
565 {
566 locI = &XEXP (x, 1);
567 locB = &XEXP (x, 0);
568 index_code = GET_CODE (*locI);
569 }
570 else if (code0 == CONST_INT || code0 == CONST
571 || code0 == SYMBOL_REF || code0 == LABEL_REF)
572 {
573 locB = &XEXP (x, 1);
574 index_code = GET_CODE (XEXP (x, 0));
575 }
576 else if (code1 == CONST_INT || code1 == CONST
577 || code1 == SYMBOL_REF || code1 == LABEL_REF)
578 {
579 locB = &XEXP (x, 0);
580 index_code = GET_CODE (XEXP (x, 1));
581 }
582 else if (code0 == REG && code1 == REG)
583 {
584 int index_op;
585 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
586
587 if (REGNO_OK_FOR_INDEX_P (regno1)
588 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
589 index_op = 1;
590 else if (REGNO_OK_FOR_INDEX_P (regno0)
591 && regno_ok_for_base_p (regno1, mode, PLUS, REG))
592 index_op = 0;
593 else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
594 || REGNO_OK_FOR_INDEX_P (regno1))
595 index_op = 1;
596 else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
597 index_op = 0;
598 else
599 index_op = 1;
600
601 locI = &XEXP (x, index_op);
602 locB = &XEXP (x, !index_op);
603 index_code = GET_CODE (*locI);
604 }
605 else if (code0 == REG)
606 {
607 locI = &XEXP (x, 0);
608 locB = &XEXP (x, 1);
609 index_code = GET_CODE (*locI);
610 }
611 else if (code1 == REG)
612 {
613 locI = &XEXP (x, 1);
614 locB = &XEXP (x, 0);
615 index_code = GET_CODE (*locI);
616 }
617
618 if (locI)
619 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode,
620 insn, vd);
621 if (locB)
622 changed |= replace_oldest_value_addr (locB,
623 base_reg_class (mode, PLUS,
624 index_code),
625 mode, insn, vd);
626 return changed;
627 }
628
629 case POST_INC:
630 case POST_DEC:
631 case POST_MODIFY:
632 case PRE_INC:
633 case PRE_DEC:
634 case PRE_MODIFY:
635 return false;
636
637 case MEM:
638 return replace_oldest_value_mem (x, insn, vd);
639
640 case REG:
641 return replace_oldest_value_reg (loc, cl, insn, vd);
642
643 default:
644 break;
645 }
646
647 fmt = GET_RTX_FORMAT (code);
648 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
649 {
650 if (fmt[i] == 'e')
651 changed |= replace_oldest_value_addr (&XEXP (x, i), cl, mode,
652 insn, vd);
653 else if (fmt[i] == 'E')
654 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
655 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), cl,
656 mode, insn, vd);
657 }
658
659 return changed;
660}
661
662/* Similar to replace_oldest_value_reg, but X contains a memory. */
663
664static bool
665replace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd)
666{
9845d120 667 enum reg_class cl;
668
669 if (DEBUG_INSN_P (insn))
670 cl = ALL_REGS;
671 else
672 cl = base_reg_class (GET_MODE (x), MEM, SCRATCH);
673
674 return replace_oldest_value_addr (&XEXP (x, 0), cl,
2d4749b6 675 GET_MODE (x), insn, vd);
676}
677
2058ec71 678/* Apply all queued updates for DEBUG_INSNs that change some reg to
679 register REGNO. */
680
681static void
682apply_debug_insn_changes (struct value_data *vd, unsigned int regno)
683{
684 struct queued_debug_insn_change *change;
685 rtx last_insn = vd->e[regno].debug_insn_changes->insn;
686
687 for (change = vd->e[regno].debug_insn_changes;
688 change;
689 change = change->next)
690 {
691 if (last_insn != change->insn)
692 {
693 apply_change_group ();
694 last_insn = change->insn;
695 }
696 validate_change (change->insn, change->loc, change->new_rtx, 1);
697 }
698 apply_change_group ();
699}
700
701/* Called via for_each_rtx, for all used registers in a real
702 insn apply DEBUG_INSN changes that change registers to the
703 used register. */
704
705static int
706cprop_find_used_regs_1 (rtx *loc, void *data)
707{
708 if (REG_P (*loc))
709 {
710 struct value_data *vd = (struct value_data *) data;
711 if (vd->e[REGNO (*loc)].debug_insn_changes)
712 {
713 apply_debug_insn_changes (vd, REGNO (*loc));
714 free_debug_insn_changes (vd, REGNO (*loc));
715 }
716 }
717 return 0;
718}
719
720/* Called via note_uses, for all used registers in a real insn
721 apply DEBUG_INSN changes that change registers to the used
722 registers. */
723
724static void
725cprop_find_used_regs (rtx *loc, void *vd)
726{
727 for_each_rtx (loc, cprop_find_used_regs_1, vd);
728}
729
2d4749b6 730/* Perform the forward copy propagation on basic block BB. */
731
732static bool
733copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd)
734{
9845d120 735 bool anything_changed = false;
2d4749b6 736 rtx insn;
737
738 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
739 {
740 int n_ops, i, alt, predicated;
741 bool is_asm, any_replacements;
742 rtx set;
743 bool replaced[MAX_RECOG_OPERANDS];
9845d120 744 bool changed = false;
2d4749b6 745
9845d120 746 if (!NONDEBUG_INSN_P (insn))
2d4749b6 747 {
9845d120 748 if (DEBUG_INSN_P (insn))
749 {
750 rtx loc = INSN_VAR_LOCATION_LOC (insn);
2058ec71 751 if (!VAR_LOC_UNKNOWN_P (loc))
752 replace_oldest_value_addr (&INSN_VAR_LOCATION_LOC (insn),
753 ALL_REGS, GET_MODE (loc),
754 insn, vd);
9845d120 755 }
756
2d4749b6 757 if (insn == BB_END (bb))
758 break;
759 else
760 continue;
761 }
762
763 set = single_set (insn);
764 extract_insn (insn);
765 if (! constrain_operands (1))
766 fatal_insn_not_found (insn);
767 preprocess_constraints ();
768 alt = which_alternative;
769 n_ops = recog_data.n_operands;
770 is_asm = asm_noperands (PATTERN (insn)) >= 0;
771
772 /* Simplify the code below by rewriting things to reflect
773 matching constraints. Also promote OP_OUT to OP_INOUT
774 in predicated instructions. */
775
776 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
777 for (i = 0; i < n_ops; ++i)
778 {
779 int matches = recog_op_alt[i][alt].matches;
780 if (matches >= 0)
781 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
782 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
783 || (predicated && recog_data.operand_type[i] == OP_OUT))
784 recog_data.operand_type[i] = OP_INOUT;
785 }
786
2058ec71 787 /* Apply changes to earlier DEBUG_INSNs if possible. */
788 if (vd->n_debug_insn_changes)
789 note_uses (&PATTERN (insn), cprop_find_used_regs, vd);
790
2d4749b6 791 /* For each earlyclobber operand, zap the value data. */
792 for (i = 0; i < n_ops; i++)
793 if (recog_op_alt[i][alt].earlyclobber)
794 kill_value (recog_data.operand[i], vd);
795
796 /* Within asms, a clobber cannot overlap inputs or outputs.
797 I wouldn't think this were true for regular insns, but
798 scan_rtx treats them like that... */
799 note_stores (PATTERN (insn), kill_clobbered_value, vd);
800
801 /* Kill all auto-incremented values. */
802 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
803 for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd);
804
805 /* Kill all early-clobbered operands. */
806 for (i = 0; i < n_ops; i++)
807 if (recog_op_alt[i][alt].earlyclobber)
808 kill_value (recog_data.operand[i], vd);
809
810 /* Special-case plain move instructions, since we may well
811 be able to do the move from a different register class. */
812 if (set && REG_P (SET_SRC (set)))
813 {
814 rtx src = SET_SRC (set);
815 unsigned int regno = REGNO (src);
816 enum machine_mode mode = GET_MODE (src);
817 unsigned int i;
818 rtx new_rtx;
819
820 /* If we are accessing SRC in some mode other that what we
821 set it in, make sure that the replacement is valid. */
822 if (mode != vd->e[regno].mode)
823 {
824 if (hard_regno_nregs[regno][mode]
825 > hard_regno_nregs[regno][vd->e[regno].mode])
826 goto no_move_special_case;
827 }
828
829 /* If the destination is also a register, try to find a source
830 register in the same class. */
831 if (REG_P (SET_DEST (set)))
832 {
833 new_rtx = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd);
834 if (new_rtx && validate_change (insn, &SET_SRC (set), new_rtx, 0))
835 {
836 if (dump_file)
837 fprintf (dump_file,
838 "insn %u: replaced reg %u with %u\n",
839 INSN_UID (insn), regno, REGNO (new_rtx));
840 changed = true;
841 goto did_replacement;
842 }
843 }
844
845 /* Otherwise, try all valid registers and see if its valid. */
846 for (i = vd->e[regno].oldest_regno; i != regno;
847 i = vd->e[i].next_regno)
848 {
849 new_rtx = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode,
850 mode, i, regno);
851 if (new_rtx != NULL_RTX)
852 {
853 if (validate_change (insn, &SET_SRC (set), new_rtx, 0))
854 {
855 ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (src);
856 REG_ATTRS (new_rtx) = REG_ATTRS (src);
857 REG_POINTER (new_rtx) = REG_POINTER (src);
858 if (dump_file)
859 fprintf (dump_file,
860 "insn %u: replaced reg %u with %u\n",
861 INSN_UID (insn), regno, REGNO (new_rtx));
862 changed = true;
863 goto did_replacement;
864 }
865 }
866 }
867 }
868 no_move_special_case:
869
870 any_replacements = false;
871
872 /* For each input operand, replace a hard register with the
873 eldest live copy that's in an appropriate register class. */
874 for (i = 0; i < n_ops; i++)
875 {
876 replaced[i] = false;
877
878 /* Don't scan match_operand here, since we've no reg class
879 information to pass down. Any operands that we could
880 substitute in will be represented elsewhere. */
881 if (recog_data.constraints[i][0] == '\0')
882 continue;
883
884 /* Don't replace in asms intentionally referencing hard regs. */
885 if (is_asm && REG_P (recog_data.operand[i])
886 && (REGNO (recog_data.operand[i])
887 == ORIGINAL_REGNO (recog_data.operand[i])))
888 continue;
889
890 if (recog_data.operand_type[i] == OP_IN)
891 {
892 if (recog_op_alt[i][alt].is_address)
893 replaced[i]
894 = replace_oldest_value_addr (recog_data.operand_loc[i],
895 recog_op_alt[i][alt].cl,
896 VOIDmode, insn, vd);
897 else if (REG_P (recog_data.operand[i]))
898 replaced[i]
899 = replace_oldest_value_reg (recog_data.operand_loc[i],
900 recog_op_alt[i][alt].cl,
901 insn, vd);
902 else if (MEM_P (recog_data.operand[i]))
903 replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
904 insn, vd);
905 }
906 else if (MEM_P (recog_data.operand[i]))
907 replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
908 insn, vd);
909
910 /* If we performed any replacement, update match_dups. */
911 if (replaced[i])
912 {
913 int j;
914 rtx new_rtx;
915
916 new_rtx = *recog_data.operand_loc[i];
917 recog_data.operand[i] = new_rtx;
918 for (j = 0; j < recog_data.n_dups; j++)
919 if (recog_data.dup_num[j] == i)
920 validate_unshare_change (insn, recog_data.dup_loc[j], new_rtx, 1);
921
922 any_replacements = true;
923 }
924 }
925
926 if (any_replacements)
927 {
928 if (! apply_change_group ())
929 {
930 for (i = 0; i < n_ops; i++)
931 if (replaced[i])
932 {
933 rtx old = *recog_data.operand_loc[i];
934 recog_data.operand[i] = old;
935 }
936
937 if (dump_file)
938 fprintf (dump_file,
939 "insn %u: reg replacements not verified\n",
940 INSN_UID (insn));
941 }
942 else
943 changed = true;
944 }
945
946 did_replacement:
9845d120 947 if (changed)
c7458ee3 948 {
949 anything_changed = true;
950
951 /* If something changed, perhaps further changes to earlier
952 DEBUG_INSNs can be applied. */
953 if (vd->n_debug_insn_changes)
954 note_uses (&PATTERN (insn), cprop_find_used_regs, vd);
955 }
9845d120 956
2d4749b6 957 /* Clobber call-clobbered registers. */
958 if (CALL_P (insn))
959 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
960 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
961 kill_value_regno (i, 1, vd);
962
963 /* Notice stores. */
964 note_stores (PATTERN (insn), kill_set_value, vd);
965
966 /* Notice copies. */
967 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
968 copy_value (SET_DEST (set), SET_SRC (set), vd);
969
970 if (insn == BB_END (bb))
971 break;
972 }
973
9845d120 974 return anything_changed;
2d4749b6 975}
976
977/* Main entry point for the forward copy propagation optimization. */
978
979static unsigned int
980copyprop_hardreg_forward (void)
981{
982 struct value_data *all_vd;
983 basic_block bb;
984 sbitmap visited;
2058ec71 985 bool analyze_called = false;
2d4749b6 986
987 all_vd = XNEWVEC (struct value_data, last_basic_block);
988
989 visited = sbitmap_alloc (last_basic_block);
990 sbitmap_zero (visited);
991
6d31b223 992 if (MAY_HAVE_DEBUG_INSNS)
2058ec71 993 debug_insn_changes_pool
994 = create_alloc_pool ("debug insn changes pool",
995 sizeof (struct queued_debug_insn_change), 256);
996
2d4749b6 997 FOR_EACH_BB (bb)
998 {
999 SET_BIT (visited, bb->index);
1000
1001 /* If a block has a single predecessor, that we've already
1002 processed, begin with the value data that was live at
1003 the end of the predecessor block. */
1004 /* ??? Ought to use more intelligent queuing of blocks. */
48e1416a 1005 if (single_pred_p (bb)
2d4749b6 1006 && TEST_BIT (visited, single_pred (bb)->index)
1007 && ! (single_pred_edge (bb)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
2058ec71 1008 {
1009 all_vd[bb->index] = all_vd[single_pred (bb)->index];
1010 if (all_vd[bb->index].n_debug_insn_changes)
1011 {
1012 unsigned int regno;
1013
1014 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1015 {
1016 if (all_vd[bb->index].e[regno].debug_insn_changes)
1017 {
1018 all_vd[bb->index].e[regno].debug_insn_changes = NULL;
1019 if (--all_vd[bb->index].n_debug_insn_changes == 0)
1020 break;
1021 }
1022 }
1023 }
1024 }
2d4749b6 1025 else
1026 init_value_data (all_vd + bb->index);
1027
1028 copyprop_hardreg_forward_1 (bb, all_vd + bb->index);
1029 }
1030
6d31b223 1031 if (MAY_HAVE_DEBUG_INSNS)
2058ec71 1032 {
1033 FOR_EACH_BB (bb)
1034 if (TEST_BIT (visited, bb->index)
1035 && all_vd[bb->index].n_debug_insn_changes)
1036 {
1037 unsigned int regno;
1038 bitmap live;
1039
1040 if (!analyze_called)
1041 {
1042 df_analyze ();
1043 analyze_called = true;
1044 }
1045 live = df_get_live_out (bb);
1046 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1047 if (all_vd[bb->index].e[regno].debug_insn_changes)
1048 {
1049 if (REGNO_REG_SET_P (live, regno))
1050 apply_debug_insn_changes (all_vd + bb->index, regno);
1051 if (all_vd[bb->index].n_debug_insn_changes == 0)
1052 break;
1053 }
1054 }
1055
1056 free_alloc_pool (debug_insn_changes_pool);
1057 }
1058
48e1416a 1059 sbitmap_free (visited);
2d4749b6 1060 free (all_vd);
1061 return 0;
1062}
1063
1064/* Dump the value chain data to stderr. */
1065
4b987fac 1066DEBUG_FUNCTION void
2d4749b6 1067debug_value_data (struct value_data *vd)
1068{
1069 HARD_REG_SET set;
1070 unsigned int i, j;
1071
1072 CLEAR_HARD_REG_SET (set);
1073
1074 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1075 if (vd->e[i].oldest_regno == i)
1076 {
1077 if (vd->e[i].mode == VOIDmode)
1078 {
1079 if (vd->e[i].next_regno != INVALID_REGNUM)
1080 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n",
1081 i, vd->e[i].next_regno);
1082 continue;
1083 }
1084
1085 SET_HARD_REG_BIT (set, i);
1086 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode));
1087
1088 for (j = vd->e[i].next_regno;
1089 j != INVALID_REGNUM;
1090 j = vd->e[j].next_regno)
1091 {
1092 if (TEST_HARD_REG_BIT (set, j))
1093 {
1094 fprintf (stderr, "[%u] Loop in regno chain\n", j);
1095 return;
1096 }
1097
1098 if (vd->e[j].oldest_regno != i)
1099 {
1100 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n",
1101 j, vd->e[j].oldest_regno);
1102 return;
1103 }
1104 SET_HARD_REG_BIT (set, j);
1105 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode));
1106 }
1107 fputc ('\n', stderr);
1108 }
1109
1110 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1111 if (! TEST_HARD_REG_BIT (set, i)
1112 && (vd->e[i].mode != VOIDmode
1113 || vd->e[i].oldest_regno != i
1114 || vd->e[i].next_regno != INVALID_REGNUM))
1115 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n",
1116 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1117 vd->e[i].next_regno);
1118}
1119
1120#ifdef ENABLE_CHECKING
1121static void
1122validate_value_data (struct value_data *vd)
1123{
1124 HARD_REG_SET set;
1125 unsigned int i, j;
1126
1127 CLEAR_HARD_REG_SET (set);
1128
1129 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1130 if (vd->e[i].oldest_regno == i)
1131 {
1132 if (vd->e[i].mode == VOIDmode)
1133 {
1134 if (vd->e[i].next_regno != INVALID_REGNUM)
1135 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1136 i, vd->e[i].next_regno);
1137 continue;
1138 }
1139
1140 SET_HARD_REG_BIT (set, i);
1141
1142 for (j = vd->e[i].next_regno;
1143 j != INVALID_REGNUM;
1144 j = vd->e[j].next_regno)
1145 {
1146 if (TEST_HARD_REG_BIT (set, j))
1147 internal_error ("validate_value_data: Loop in regno chain (%u)",
1148 j);
1149 if (vd->e[j].oldest_regno != i)
1150 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1151 j, vd->e[j].oldest_regno);
1152
1153 SET_HARD_REG_BIT (set, j);
1154 }
1155 }
1156
1157 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1158 if (! TEST_HARD_REG_BIT (set, i)
1159 && (vd->e[i].mode != VOIDmode
1160 || vd->e[i].oldest_regno != i
1161 || vd->e[i].next_regno != INVALID_REGNUM))
1162 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1163 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1164 vd->e[i].next_regno);
1165}
1166#endif
1167\f
1168static bool
1169gate_handle_cprop (void)
1170{
1171 return (optimize > 0 && (flag_cprop_registers));
1172}
1173
1174
1175struct rtl_opt_pass pass_cprop_hardreg =
1176{
1177 {
1178 RTL_PASS,
1179 "cprop_hardreg", /* name */
1180 gate_handle_cprop, /* gate */
1181 copyprop_hardreg_forward, /* execute */
1182 NULL, /* sub */
1183 NULL, /* next */
1184 0, /* static_pass_number */
1185 TV_CPROP_REGISTERS, /* tv_id */
1186 0, /* properties_required */
1187 0, /* properties_provided */
1188 0, /* properties_destroyed */
1189 0, /* todo_flags_start */
771e2890 1190 TODO_df_finish
2058ec71 1191 | TODO_verify_rtl_sharing /* todo_flags_finish */
2d4749b6 1192 }
1193};
Mirror of https://gcc.gnu.org/git/gcc.git