Daily bump.
[official-gcc.git] / gcc / regcprop.c
blob367d85a7e242e9765767dcdd29080bd1fde3eb84
1 /* Copy propagation on hard registers for the GNU compiler.
2 Copyright (C) 2000-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "rtl.h"
25 #include "df.h"
26 #include "memmodel.h"
27 #include "tm_p.h"
28 #include "insn-config.h"
29 #include "regs.h"
30 #include "emit-rtl.h"
31 #include "recog.h"
32 #include "diagnostic-core.h"
33 #include "addresses.h"
34 #include "tree-pass.h"
35 #include "rtl-iter.h"
36 #include "cfgrtl.h"
38 /* The following code does forward propagation of hard register copies.
39 The object is to eliminate as many dependencies as possible, so that
40 we have the most scheduling freedom. As a side effect, we also clean
41 up some silly register allocation decisions made by reload. This
42 code may be obsoleted by a new register allocator. */
44 /* DEBUG_INSNs aren't changed right away, as doing so might extend the
45 lifetime of a register and get the DEBUG_INSN subsequently reset.
46 So they are queued instead, and updated only when the register is
47 used in some subsequent real insn before it is set. */
48 struct queued_debug_insn_change
50 struct queued_debug_insn_change *next;
51 rtx_insn *insn;
52 rtx *loc;
53 rtx new_rtx;
56 /* For each register, we have a list of registers that contain the same
57 value. The OLDEST_REGNO field points to the head of the list, and
58 the NEXT_REGNO field runs through the list. The MODE field indicates
59 what mode the data is known to be in; this field is VOIDmode when the
60 register is not known to contain valid data. */
62 struct value_data_entry
64 machine_mode mode;
65 unsigned int oldest_regno;
66 unsigned int next_regno;
67 struct queued_debug_insn_change *debug_insn_changes;
70 struct value_data
72 struct value_data_entry e[FIRST_PSEUDO_REGISTER];
73 unsigned int max_value_regs;
74 unsigned int n_debug_insn_changes;
77 static object_allocator<queued_debug_insn_change> queued_debug_insn_change_pool
78 ("debug insn changes pool");
80 static bool skip_debug_insn_p;
82 static void kill_value_one_regno (unsigned, struct value_data *);
83 static void kill_value_regno (unsigned, unsigned, struct value_data *);
84 static void kill_value (const_rtx, struct value_data *);
85 static void set_value_regno (unsigned, machine_mode, struct value_data *);
86 static void init_value_data (struct value_data *);
87 static void kill_clobbered_value (rtx, const_rtx, void *);
88 static void kill_set_value (rtx, const_rtx, void *);
89 static void copy_value (rtx, rtx, struct value_data *);
90 static bool mode_change_ok (machine_mode, machine_mode,
91 unsigned int);
92 static rtx maybe_mode_change (machine_mode, machine_mode,
93 machine_mode, unsigned int, unsigned int);
94 static rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *);
95 static bool replace_oldest_value_reg (rtx *, enum reg_class, rtx_insn *,
96 struct value_data *);
97 static bool replace_oldest_value_addr (rtx *, enum reg_class,
98 machine_mode, addr_space_t,
99 rtx_insn *, struct value_data *);
100 static bool replace_oldest_value_mem (rtx, rtx_insn *, struct value_data *);
101 static bool copyprop_hardreg_forward_1 (basic_block, struct value_data *);
102 extern void debug_value_data (struct value_data *);
103 static void validate_value_data (struct value_data *);
105 /* Free all queued updates for DEBUG_INSNs that change some reg to
106 register REGNO. */
108 static void
109 free_debug_insn_changes (struct value_data *vd, unsigned int regno)
111 struct queued_debug_insn_change *cur, *next;
112 for (cur = vd->e[regno].debug_insn_changes; cur; cur = next)
114 next = cur->next;
115 --vd->n_debug_insn_changes;
116 queued_debug_insn_change_pool.remove (cur);
118 vd->e[regno].debug_insn_changes = NULL;
121 /* Kill register REGNO. This involves removing it from any value
122 lists, and resetting the value mode to VOIDmode. This is only a
123 helper function; it does not handle any hard registers overlapping
124 with REGNO. */
126 static void
127 kill_value_one_regno (unsigned int regno, struct value_data *vd)
129 unsigned int i, next;
131 if (vd->e[regno].oldest_regno != regno)
133 for (i = vd->e[regno].oldest_regno;
134 vd->e[i].next_regno != regno;
135 i = vd->e[i].next_regno)
136 continue;
137 vd->e[i].next_regno = vd->e[regno].next_regno;
139 else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM)
141 for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno)
142 vd->e[i].oldest_regno = next;
145 vd->e[regno].mode = VOIDmode;
146 vd->e[regno].oldest_regno = regno;
147 vd->e[regno].next_regno = INVALID_REGNUM;
148 if (vd->e[regno].debug_insn_changes)
149 free_debug_insn_changes (vd, regno);
151 if (flag_checking)
152 validate_value_data (vd);
155 /* Kill the value in register REGNO for NREGS, and any other registers
156 whose values overlap. */
158 static void
159 kill_value_regno (unsigned int regno, unsigned int nregs,
160 struct value_data *vd)
162 unsigned int j;
164 /* Kill the value we're told to kill. */
165 for (j = 0; j < nregs; ++j)
166 kill_value_one_regno (regno + j, vd);
168 /* Kill everything that overlapped what we're told to kill. */
169 if (regno < vd->max_value_regs)
170 j = 0;
171 else
172 j = regno - vd->max_value_regs;
173 for (; j < regno; ++j)
175 unsigned int i, n;
176 if (vd->e[j].mode == VOIDmode)
177 continue;
178 n = hard_regno_nregs[j][vd->e[j].mode];
179 if (j + n > regno)
180 for (i = 0; i < n; ++i)
181 kill_value_one_regno (j + i, vd);
185 /* Kill X. This is a convenience function wrapping kill_value_regno
186 so that we mind the mode the register is in. */
188 static void
189 kill_value (const_rtx x, struct value_data *vd)
191 if (GET_CODE (x) == SUBREG)
193 rtx tmp = simplify_subreg (GET_MODE (x), SUBREG_REG (x),
194 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
195 x = tmp ? tmp : SUBREG_REG (x);
197 if (REG_P (x))
198 kill_value_regno (REGNO (x), REG_NREGS (x), vd);
201 /* Remember that REGNO is valid in MODE. */
203 static void
204 set_value_regno (unsigned int regno, machine_mode mode,
205 struct value_data *vd)
207 unsigned int nregs;
209 vd->e[regno].mode = mode;
211 nregs = hard_regno_nregs[regno][mode];
212 if (nregs > vd->max_value_regs)
213 vd->max_value_regs = nregs;
216 /* Initialize VD such that there are no known relationships between regs. */
218 static void
219 init_value_data (struct value_data *vd)
221 int i;
222 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
224 vd->e[i].mode = VOIDmode;
225 vd->e[i].oldest_regno = i;
226 vd->e[i].next_regno = INVALID_REGNUM;
227 vd->e[i].debug_insn_changes = NULL;
229 vd->max_value_regs = 0;
230 vd->n_debug_insn_changes = 0;
233 /* Called through note_stores. If X is clobbered, kill its value. */
235 static void
236 kill_clobbered_value (rtx x, const_rtx set, void *data)
238 struct value_data *const vd = (struct value_data *) data;
239 if (GET_CODE (set) == CLOBBER)
240 kill_value (x, vd);
243 /* A structure passed as data to kill_set_value through note_stores. */
244 struct kill_set_value_data
246 struct value_data *vd;
247 rtx ignore_set_reg;
250 /* Called through note_stores. If X is set, not clobbered, kill its
251 current value and install it as the root of its own value list. */
253 static void
254 kill_set_value (rtx x, const_rtx set, void *data)
256 struct kill_set_value_data *ksvd = (struct kill_set_value_data *) data;
257 if (rtx_equal_p (x, ksvd->ignore_set_reg))
258 return;
259 if (GET_CODE (set) != CLOBBER)
261 kill_value (x, ksvd->vd);
262 if (REG_P (x))
263 set_value_regno (REGNO (x), GET_MODE (x), ksvd->vd);
267 /* Kill any register used in X as the base of an auto-increment expression,
268 and install that register as the root of its own value list. */
270 static void
271 kill_autoinc_value (rtx_insn *insn, struct value_data *vd)
273 subrtx_iterator::array_type array;
274 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
276 const_rtx x = *iter;
277 if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
279 x = XEXP (x, 0);
280 kill_value (x, vd);
281 set_value_regno (REGNO (x), GET_MODE (x), vd);
282 iter.skip_subrtxes ();
287 /* Assert that SRC has been copied to DEST. Adjust the data structures
288 to reflect that SRC contains an older copy of the shared value. */
290 static void
291 copy_value (rtx dest, rtx src, struct value_data *vd)
293 unsigned int dr = REGNO (dest);
294 unsigned int sr = REGNO (src);
295 unsigned int dn, sn;
296 unsigned int i;
298 /* ??? At present, it's possible to see noop sets. It'd be nice if
299 this were cleaned up beforehand... */
300 if (sr == dr)
301 return;
303 /* Do not propagate copies to the stack pointer, as that can leave
304 memory accesses with no scheduling dependency on the stack update. */
305 if (dr == STACK_POINTER_REGNUM)
306 return;
308 /* Likewise with the frame pointer, if we're using one. */
309 if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM)
310 return;
312 /* Do not propagate copies to fixed or global registers, patterns
313 can be relying to see particular fixed register or users can
314 expect the chosen global register in asm. */
315 if (fixed_regs[dr] || global_regs[dr])
316 return;
318 /* If SRC and DEST overlap, don't record anything. */
319 dn = REG_NREGS (dest);
320 sn = REG_NREGS (src);
321 if ((dr > sr && dr < sr + sn)
322 || (sr > dr && sr < dr + dn))
323 return;
325 /* If SRC had no assigned mode (i.e. we didn't know it was live)
326 assign it now and assume the value came from an input argument
327 or somesuch. */
328 if (vd->e[sr].mode == VOIDmode)
329 set_value_regno (sr, vd->e[dr].mode, vd);
331 /* If we are narrowing the input to a smaller number of hard regs,
332 and it is in big endian, we are really extracting a high part.
333 Since we generally associate a low part of a value with the value itself,
334 we must not do the same for the high part.
335 Note we can still get low parts for the same mode combination through
336 a two-step copy involving differently sized hard regs.
337 Assume hard regs fr* are 32 bits each, while r* are 64 bits each:
338 (set (reg:DI r0) (reg:DI fr0))
339 (set (reg:SI fr2) (reg:SI r0))
340 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
341 (set (reg:SI fr2) (reg:SI fr0))
342 loads the high part of (reg:DI fr0) into fr2.
344 We can't properly represent the latter case in our tables, so don't
345 record anything then. */
346 else if (sn < (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode]
347 && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD
348 ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
349 return;
351 /* If SRC had been assigned a mode narrower than the copy, we can't
352 link DEST into the chain, because not all of the pieces of the
353 copy came from oldest_regno. */
354 else if (sn > (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode])
355 return;
357 /* Link DR at the end of the value chain used by SR. */
359 vd->e[dr].oldest_regno = vd->e[sr].oldest_regno;
361 for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno)
362 continue;
363 vd->e[i].next_regno = dr;
365 if (flag_checking)
366 validate_value_data (vd);
369 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
371 static bool
372 mode_change_ok (machine_mode orig_mode, machine_mode new_mode,
373 unsigned int regno ATTRIBUTE_UNUSED)
375 if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode))
376 return false;
378 #ifdef CANNOT_CHANGE_MODE_CLASS
379 return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode);
380 #endif
382 return true;
385 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
386 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
387 in NEW_MODE.
388 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
390 static rtx
391 maybe_mode_change (machine_mode orig_mode, machine_mode copy_mode,
392 machine_mode new_mode, unsigned int regno,
393 unsigned int copy_regno ATTRIBUTE_UNUSED)
395 if (GET_MODE_SIZE (copy_mode) < GET_MODE_SIZE (orig_mode)
396 && GET_MODE_SIZE (copy_mode) < GET_MODE_SIZE (new_mode))
397 return NULL_RTX;
399 /* Avoid creating multiple copies of the stack pointer. Some ports
400 assume there is one and only one stack pointer.
402 It's unclear if we need to do the same for other special registers. */
403 if (regno == STACK_POINTER_REGNUM)
404 return NULL_RTX;
406 if (orig_mode == new_mode)
407 return gen_raw_REG (new_mode, regno);
408 else if (mode_change_ok (orig_mode, new_mode, regno))
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;
419 offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0)
420 + (BYTES_BIG_ENDIAN ? byteoffset : 0));
421 regno += subreg_regno_offset (regno, orig_mode, offset, new_mode);
422 if (HARD_REGNO_MODE_OK (regno, new_mode))
423 return gen_raw_REG (new_mode, regno);
425 return NULL_RTX;
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. */
432 static rtx
433 find_oldest_value_reg (enum reg_class cl, rtx reg, struct value_data *vd)
435 unsigned int regno = REGNO (reg);
436 machine_mode mode = GET_MODE (reg);
437 unsigned int i;
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)
448 if (hard_regno_nregs[regno][mode]
449 > hard_regno_nregs[regno][vd->e[regno].mode])
450 return NULL_RTX;
453 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno)
455 machine_mode oldmode = vd->e[i].mode;
456 rtx new_rtx;
458 if (!in_hard_reg_set_p (reg_class_contents[cl], mode, i))
459 continue;
461 new_rtx = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno);
462 if (new_rtx)
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;
471 return NULL_RTX;
474 /* If possible, replace the register at *LOC with the oldest register
475 in register class CL. Return true if successfully replaced. */
477 static bool
478 replace_oldest_value_reg (rtx *loc, enum reg_class cl, rtx_insn *insn,
479 struct value_data *vd)
481 rtx new_rtx = find_oldest_value_reg (cl, *loc, vd);
482 if (new_rtx && (!DEBUG_INSN_P (insn) || !skip_debug_insn_p))
484 if (DEBUG_INSN_P (insn))
486 struct queued_debug_insn_change *change;
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));
492 change = queued_debug_insn_change_pool.allocate ();
493 change->next = vd->e[REGNO (new_rtx)].debug_insn_changes;
494 change->insn = insn;
495 change->loc = loc;
496 change->new_rtx = new_rtx;
497 vd->e[REGNO (new_rtx)].debug_insn_changes = change;
498 ++vd->n_debug_insn_changes;
499 return true;
501 if (dump_file)
502 fprintf (dump_file, "insn %u: replaced reg %u with %u\n",
503 INSN_UID (insn), REGNO (*loc), REGNO (new_rtx));
505 validate_change (insn, loc, new_rtx, 1);
506 return true;
508 return false;
511 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
512 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
513 BASE_REG_CLASS depending on how the register is being considered. */
515 static bool
516 replace_oldest_value_addr (rtx *loc, enum reg_class cl,
517 machine_mode mode, addr_space_t as,
518 rtx_insn *insn, struct value_data *vd)
520 rtx x = *loc;
521 RTX_CODE code = GET_CODE (x);
522 const char *fmt;
523 int i, j;
524 bool changed = false;
526 switch (code)
528 case PLUS:
529 if (DEBUG_INSN_P (insn))
530 break;
533 rtx orig_op0 = XEXP (x, 0);
534 rtx orig_op1 = XEXP (x, 1);
535 RTX_CODE code0 = GET_CODE (orig_op0);
536 RTX_CODE code1 = GET_CODE (orig_op1);
537 rtx op0 = orig_op0;
538 rtx op1 = orig_op1;
539 rtx *locI = NULL;
540 rtx *locB = NULL;
541 enum rtx_code index_code = SCRATCH;
543 if (GET_CODE (op0) == SUBREG)
545 op0 = SUBREG_REG (op0);
546 code0 = GET_CODE (op0);
549 if (GET_CODE (op1) == SUBREG)
551 op1 = SUBREG_REG (op1);
552 code1 = GET_CODE (op1);
555 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
556 || code0 == ZERO_EXTEND || code1 == MEM)
558 locI = &XEXP (x, 0);
559 locB = &XEXP (x, 1);
560 index_code = GET_CODE (*locI);
562 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
563 || code1 == ZERO_EXTEND || code0 == MEM)
565 locI = &XEXP (x, 1);
566 locB = &XEXP (x, 0);
567 index_code = GET_CODE (*locI);
569 else if (code0 == CONST_INT || code0 == CONST
570 || code0 == SYMBOL_REF || code0 == LABEL_REF)
572 locB = &XEXP (x, 1);
573 index_code = GET_CODE (XEXP (x, 0));
575 else if (code1 == CONST_INT || code1 == CONST
576 || code1 == SYMBOL_REF || code1 == LABEL_REF)
578 locB = &XEXP (x, 0);
579 index_code = GET_CODE (XEXP (x, 1));
581 else if (code0 == REG && code1 == REG)
583 int index_op;
584 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
586 if (REGNO_OK_FOR_INDEX_P (regno1)
587 && regno_ok_for_base_p (regno0, mode, as, PLUS, REG))
588 index_op = 1;
589 else if (REGNO_OK_FOR_INDEX_P (regno0)
590 && regno_ok_for_base_p (regno1, mode, as, PLUS, REG))
591 index_op = 0;
592 else if (regno_ok_for_base_p (regno0, mode, as, PLUS, REG)
593 || REGNO_OK_FOR_INDEX_P (regno1))
594 index_op = 1;
595 else if (regno_ok_for_base_p (regno1, mode, as, PLUS, REG))
596 index_op = 0;
597 else
598 index_op = 1;
600 locI = &XEXP (x, index_op);
601 locB = &XEXP (x, !index_op);
602 index_code = GET_CODE (*locI);
604 else if (code0 == REG)
606 locI = &XEXP (x, 0);
607 locB = &XEXP (x, 1);
608 index_code = GET_CODE (*locI);
610 else if (code1 == REG)
612 locI = &XEXP (x, 1);
613 locB = &XEXP (x, 0);
614 index_code = GET_CODE (*locI);
617 if (locI)
618 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS,
619 mode, as, insn, vd);
620 if (locB)
621 changed |= replace_oldest_value_addr (locB,
622 base_reg_class (mode, as, PLUS,
623 index_code),
624 mode, as, insn, vd);
625 return changed;
628 case POST_INC:
629 case POST_DEC:
630 case POST_MODIFY:
631 case PRE_INC:
632 case PRE_DEC:
633 case PRE_MODIFY:
634 return false;
636 case MEM:
637 return replace_oldest_value_mem (x, insn, vd);
639 case REG:
640 return replace_oldest_value_reg (loc, cl, insn, vd);
642 default:
643 break;
646 fmt = GET_RTX_FORMAT (code);
647 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
649 if (fmt[i] == 'e')
650 changed |= replace_oldest_value_addr (&XEXP (x, i), cl, mode, as,
651 insn, vd);
652 else if (fmt[i] == 'E')
653 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
654 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), cl,
655 mode, as, insn, vd);
658 return changed;
661 /* Similar to replace_oldest_value_reg, but X contains a memory. */
663 static bool
664 replace_oldest_value_mem (rtx x, rtx_insn *insn, struct value_data *vd)
666 enum reg_class cl;
668 if (DEBUG_INSN_P (insn))
669 cl = ALL_REGS;
670 else
671 cl = base_reg_class (GET_MODE (x), MEM_ADDR_SPACE (x), MEM, SCRATCH);
673 return replace_oldest_value_addr (&XEXP (x, 0), cl,
674 GET_MODE (x), MEM_ADDR_SPACE (x),
675 insn, vd);
678 /* Apply all queued updates for DEBUG_INSNs that change some reg to
679 register REGNO. */
681 static void
682 apply_debug_insn_changes (struct value_data *vd, unsigned int regno)
684 struct queued_debug_insn_change *change;
685 rtx_insn *last_insn = vd->e[regno].debug_insn_changes->insn;
687 for (change = vd->e[regno].debug_insn_changes;
688 change;
689 change = change->next)
691 if (last_insn != change->insn)
693 apply_change_group ();
694 last_insn = change->insn;
696 validate_change (change->insn, change->loc, change->new_rtx, 1);
698 apply_change_group ();
701 /* Called via note_uses, for all used registers in a real insn
702 apply DEBUG_INSN changes that change registers to the used
703 registers. */
705 static void
706 cprop_find_used_regs (rtx *loc, void *data)
708 struct value_data *const vd = (struct value_data *) data;
709 subrtx_iterator::array_type array;
710 FOR_EACH_SUBRTX (iter, array, *loc, NONCONST)
712 const_rtx x = *iter;
713 if (REG_P (x))
715 unsigned int regno = REGNO (x);
716 if (vd->e[regno].debug_insn_changes)
718 apply_debug_insn_changes (vd, regno);
719 free_debug_insn_changes (vd, regno);
725 /* Apply clobbers of INSN in PATTERN and C_I_F_U to value_data VD. */
727 static void
728 kill_clobbered_values (rtx_insn *insn, struct value_data *vd)
730 note_stores (PATTERN (insn), kill_clobbered_value, vd);
732 if (CALL_P (insn))
734 rtx exp;
736 for (exp = CALL_INSN_FUNCTION_USAGE (insn); exp; exp = XEXP (exp, 1))
738 rtx x = XEXP (exp, 0);
739 if (GET_CODE (x) == CLOBBER)
740 kill_value (SET_DEST (x), vd);
745 /* Perform the forward copy propagation on basic block BB. */
747 static bool
748 copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd)
750 bool anything_changed = false;
751 rtx_insn *insn, *next;
753 for (insn = BB_HEAD (bb); ; insn = next)
755 int n_ops, i, predicated;
756 bool is_asm, any_replacements;
757 rtx set;
758 rtx link;
759 bool replaced[MAX_RECOG_OPERANDS];
760 bool changed = false;
761 struct kill_set_value_data ksvd;
763 next = NEXT_INSN (insn);
764 if (!NONDEBUG_INSN_P (insn))
766 if (DEBUG_INSN_P (insn))
768 rtx loc = INSN_VAR_LOCATION_LOC (insn);
769 if (!VAR_LOC_UNKNOWN_P (loc))
770 replace_oldest_value_addr (&INSN_VAR_LOCATION_LOC (insn),
771 ALL_REGS, GET_MODE (loc),
772 ADDR_SPACE_GENERIC, insn, vd);
775 if (insn == BB_END (bb))
776 break;
777 else
778 continue;
781 set = single_set (insn);
783 /* Detect noop sets and remove them before processing side effects. */
784 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
786 unsigned int regno = REGNO (SET_SRC (set));
787 rtx r1 = find_oldest_value_reg (REGNO_REG_CLASS (regno),
788 SET_DEST (set), vd);
789 rtx r2 = find_oldest_value_reg (REGNO_REG_CLASS (regno),
790 SET_SRC (set), vd);
791 if (rtx_equal_p (r1 ? r1 : SET_DEST (set), r2 ? r2 : SET_SRC (set)))
793 bool last = insn == BB_END (bb);
794 delete_insn (insn);
795 if (last)
796 break;
797 continue;
801 extract_constrain_insn (insn);
802 preprocess_constraints (insn);
803 const operand_alternative *op_alt = which_op_alt ();
804 n_ops = recog_data.n_operands;
805 is_asm = asm_noperands (PATTERN (insn)) >= 0;
807 /* Simplify the code below by promoting OP_OUT to OP_INOUT
808 in predicated instructions. */
810 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
811 for (i = 0; i < n_ops; ++i)
813 int matches = op_alt[i].matches;
814 if (matches >= 0 || op_alt[i].matched >= 0
815 || (predicated && recog_data.operand_type[i] == OP_OUT))
816 recog_data.operand_type[i] = OP_INOUT;
819 /* Apply changes to earlier DEBUG_INSNs if possible. */
820 if (vd->n_debug_insn_changes)
821 note_uses (&PATTERN (insn), cprop_find_used_regs, vd);
823 /* For each earlyclobber operand, zap the value data. */
824 for (i = 0; i < n_ops; i++)
825 if (op_alt[i].earlyclobber)
826 kill_value (recog_data.operand[i], vd);
828 /* Within asms, a clobber cannot overlap inputs or outputs.
829 I wouldn't think this were true for regular insns, but
830 scan_rtx treats them like that... */
831 kill_clobbered_values (insn, vd);
833 /* Kill all auto-incremented values. */
834 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
835 kill_autoinc_value (insn, vd);
837 /* Kill all early-clobbered operands. */
838 for (i = 0; i < n_ops; i++)
839 if (op_alt[i].earlyclobber)
840 kill_value (recog_data.operand[i], vd);
842 /* If we have dead sets in the insn, then we need to note these as we
843 would clobbers. */
844 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
846 if (REG_NOTE_KIND (link) == REG_UNUSED)
848 kill_value (XEXP (link, 0), vd);
849 /* Furthermore, if the insn looked like a single-set,
850 but the dead store kills the source value of that
851 set, then we can no-longer use the plain move
852 special case below. */
853 if (set
854 && reg_overlap_mentioned_p (XEXP (link, 0), SET_SRC (set)))
855 set = NULL;
859 /* Special-case plain move instructions, since we may well
860 be able to do the move from a different register class. */
861 if (set && REG_P (SET_SRC (set)))
863 rtx src = SET_SRC (set);
864 unsigned int regno = REGNO (src);
865 machine_mode mode = GET_MODE (src);
866 unsigned int i;
867 rtx new_rtx;
869 /* If we are accessing SRC in some mode other that what we
870 set it in, make sure that the replacement is valid. */
871 if (mode != vd->e[regno].mode)
873 if (hard_regno_nregs[regno][mode]
874 > hard_regno_nregs[regno][vd->e[regno].mode])
875 goto no_move_special_case;
877 /* And likewise, if we are narrowing on big endian the transformation
878 is also invalid. */
879 if (hard_regno_nregs[regno][mode]
880 < hard_regno_nregs[regno][vd->e[regno].mode]
881 && (GET_MODE_SIZE (vd->e[regno].mode) > UNITS_PER_WORD
882 ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
883 goto no_move_special_case;
886 /* If the destination is also a register, try to find a source
887 register in the same class. */
888 if (REG_P (SET_DEST (set)))
890 new_rtx = find_oldest_value_reg (REGNO_REG_CLASS (regno),
891 src, vd);
893 if (new_rtx && validate_change (insn, &SET_SRC (set), new_rtx, 0))
895 if (dump_file)
896 fprintf (dump_file,
897 "insn %u: replaced reg %u with %u\n",
898 INSN_UID (insn), regno, REGNO (new_rtx));
899 changed = true;
900 goto did_replacement;
902 /* We need to re-extract as validate_change clobbers
903 recog_data. */
904 extract_constrain_insn (insn);
905 preprocess_constraints (insn);
908 /* Otherwise, try all valid registers and see if its valid. */
909 for (i = vd->e[regno].oldest_regno; i != regno;
910 i = vd->e[i].next_regno)
912 new_rtx = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode,
913 mode, i, regno);
914 if (new_rtx != NULL_RTX)
916 if (validate_change (insn, &SET_SRC (set), new_rtx, 0))
918 ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (src);
919 REG_ATTRS (new_rtx) = REG_ATTRS (src);
920 REG_POINTER (new_rtx) = REG_POINTER (src);
921 if (dump_file)
922 fprintf (dump_file,
923 "insn %u: replaced reg %u with %u\n",
924 INSN_UID (insn), regno, REGNO (new_rtx));
925 changed = true;
926 goto did_replacement;
928 /* We need to re-extract as validate_change clobbers
929 recog_data. */
930 extract_constrain_insn (insn);
931 preprocess_constraints (insn);
935 no_move_special_case:
937 any_replacements = false;
939 /* For each input operand, replace a hard register with the
940 eldest live copy that's in an appropriate register class. */
941 for (i = 0; i < n_ops; i++)
943 replaced[i] = false;
945 /* Don't scan match_operand here, since we've no reg class
946 information to pass down. Any operands that we could
947 substitute in will be represented elsewhere. */
948 if (recog_data.constraints[i][0] == '\0')
949 continue;
951 /* Don't replace in asms intentionally referencing hard regs. */
952 if (is_asm && REG_P (recog_data.operand[i])
953 && (REGNO (recog_data.operand[i])
954 == ORIGINAL_REGNO (recog_data.operand[i])))
955 continue;
957 if (recog_data.operand_type[i] == OP_IN)
959 if (op_alt[i].is_address)
960 replaced[i]
961 = replace_oldest_value_addr (recog_data.operand_loc[i],
962 alternative_class (op_alt, i),
963 VOIDmode, ADDR_SPACE_GENERIC,
964 insn, vd);
965 else if (REG_P (recog_data.operand[i]))
966 replaced[i]
967 = replace_oldest_value_reg (recog_data.operand_loc[i],
968 alternative_class (op_alt, i),
969 insn, vd);
970 else if (MEM_P (recog_data.operand[i]))
971 replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
972 insn, vd);
974 else if (MEM_P (recog_data.operand[i]))
975 replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
976 insn, vd);
978 /* If we performed any replacement, update match_dups. */
979 if (replaced[i])
981 int j;
982 rtx new_rtx;
984 new_rtx = *recog_data.operand_loc[i];
985 recog_data.operand[i] = new_rtx;
986 for (j = 0; j < recog_data.n_dups; j++)
987 if (recog_data.dup_num[j] == i)
988 validate_unshare_change (insn, recog_data.dup_loc[j], new_rtx, 1);
990 any_replacements = true;
994 if (any_replacements)
996 if (! apply_change_group ())
998 for (i = 0; i < n_ops; i++)
999 if (replaced[i])
1001 rtx old = *recog_data.operand_loc[i];
1002 recog_data.operand[i] = old;
1005 if (dump_file)
1006 fprintf (dump_file,
1007 "insn %u: reg replacements not verified\n",
1008 INSN_UID (insn));
1010 else
1011 changed = true;
1014 did_replacement:
1015 if (changed)
1017 anything_changed = true;
1019 /* If something changed, perhaps further changes to earlier
1020 DEBUG_INSNs can be applied. */
1021 if (vd->n_debug_insn_changes)
1022 note_uses (&PATTERN (insn), cprop_find_used_regs, vd);
1025 ksvd.vd = vd;
1026 ksvd.ignore_set_reg = NULL_RTX;
1028 /* Clobber call-clobbered registers. */
1029 if (CALL_P (insn))
1031 unsigned int set_regno = INVALID_REGNUM;
1032 unsigned int set_nregs = 0;
1033 unsigned int regno;
1034 rtx exp;
1035 HARD_REG_SET regs_invalidated_by_this_call;
1037 for (exp = CALL_INSN_FUNCTION_USAGE (insn); exp; exp = XEXP (exp, 1))
1039 rtx x = XEXP (exp, 0);
1040 if (GET_CODE (x) == SET)
1042 rtx dest = SET_DEST (x);
1043 kill_value (dest, vd);
1044 set_value_regno (REGNO (dest), GET_MODE (dest), vd);
1045 copy_value (dest, SET_SRC (x), vd);
1046 ksvd.ignore_set_reg = dest;
1047 set_regno = REGNO (dest);
1048 set_nregs = REG_NREGS (dest);
1049 break;
1053 get_call_reg_set_usage (insn,
1054 &regs_invalidated_by_this_call,
1055 regs_invalidated_by_call);
1056 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1057 if ((TEST_HARD_REG_BIT (regs_invalidated_by_this_call, regno)
1058 || HARD_REGNO_CALL_PART_CLOBBERED (regno, vd->e[regno].mode))
1059 && (regno < set_regno || regno >= set_regno + set_nregs))
1060 kill_value_regno (regno, 1, vd);
1062 /* If SET was seen in CALL_INSN_FUNCTION_USAGE, and SET_SRC
1063 of the SET isn't in regs_invalidated_by_call hard reg set,
1064 but instead among CLOBBERs on the CALL_INSN, we could wrongly
1065 assume the value in it is still live. */
1066 if (ksvd.ignore_set_reg)
1067 kill_clobbered_values (insn, vd);
1070 bool copy_p = (set
1071 && REG_P (SET_DEST (set))
1072 && REG_P (SET_SRC (set)));
1073 bool noop_p = (copy_p
1074 && rtx_equal_p (SET_DEST (set), SET_SRC (set)));
1076 /* If a noop move is using narrower mode than we have recorded,
1077 we need to either remove the noop move, or kill_set_value. */
1078 if (noop_p
1079 && (GET_MODE_BITSIZE (GET_MODE (SET_DEST (set)))
1080 < GET_MODE_BITSIZE (vd->e[REGNO (SET_DEST (set))].mode)))
1082 if (noop_move_p (insn))
1084 bool last = insn == BB_END (bb);
1085 delete_insn (insn);
1086 if (last)
1087 break;
1089 else
1090 noop_p = false;
1093 if (!noop_p)
1095 /* Notice stores. */
1096 note_stores (PATTERN (insn), kill_set_value, &ksvd);
1098 /* Notice copies. */
1099 if (copy_p)
1100 copy_value (SET_DEST (set), SET_SRC (set), vd);
1103 if (insn == BB_END (bb))
1104 break;
1107 return anything_changed;
1110 /* Dump the value chain data to stderr. */
1112 DEBUG_FUNCTION void
1113 debug_value_data (struct value_data *vd)
1115 HARD_REG_SET set;
1116 unsigned int i, j;
1118 CLEAR_HARD_REG_SET (set);
1120 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1121 if (vd->e[i].oldest_regno == i)
1123 if (vd->e[i].mode == VOIDmode)
1125 if (vd->e[i].next_regno != INVALID_REGNUM)
1126 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n",
1127 i, vd->e[i].next_regno);
1128 continue;
1131 SET_HARD_REG_BIT (set, i);
1132 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode));
1134 for (j = vd->e[i].next_regno;
1135 j != INVALID_REGNUM;
1136 j = vd->e[j].next_regno)
1138 if (TEST_HARD_REG_BIT (set, j))
1140 fprintf (stderr, "[%u] Loop in regno chain\n", j);
1141 return;
1144 if (vd->e[j].oldest_regno != i)
1146 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n",
1147 j, vd->e[j].oldest_regno);
1148 return;
1150 SET_HARD_REG_BIT (set, j);
1151 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode));
1153 fputc ('\n', stderr);
1156 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1157 if (! TEST_HARD_REG_BIT (set, i)
1158 && (vd->e[i].mode != VOIDmode
1159 || vd->e[i].oldest_regno != i
1160 || vd->e[i].next_regno != INVALID_REGNUM))
1161 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n",
1162 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1163 vd->e[i].next_regno);
1166 /* Do copyprop_hardreg_forward_1 for a single basic block BB.
1167 DEBUG_INSN is skipped since we do not want to involve DF related
1168 staff as how it is handled in function pass_cprop_hardreg::execute.
1170 NOTE: Currently it is only used for shrink-wrap. Maybe extend it
1171 to handle DEBUG_INSN for other uses. */
1173 void
1174 copyprop_hardreg_forward_bb_without_debug_insn (basic_block bb)
1176 struct value_data *vd;
1177 vd = XNEWVEC (struct value_data, 1);
1178 init_value_data (vd);
1180 skip_debug_insn_p = true;
1181 copyprop_hardreg_forward_1 (bb, vd);
1182 free (vd);
1183 skip_debug_insn_p = false;
1186 static void
1187 validate_value_data (struct value_data *vd)
1189 HARD_REG_SET set;
1190 unsigned int i, j;
1192 CLEAR_HARD_REG_SET (set);
1194 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1195 if (vd->e[i].oldest_regno == i)
1197 if (vd->e[i].mode == VOIDmode)
1199 if (vd->e[i].next_regno != INVALID_REGNUM)
1200 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1201 i, vd->e[i].next_regno);
1202 continue;
1205 SET_HARD_REG_BIT (set, i);
1207 for (j = vd->e[i].next_regno;
1208 j != INVALID_REGNUM;
1209 j = vd->e[j].next_regno)
1211 if (TEST_HARD_REG_BIT (set, j))
1212 internal_error ("validate_value_data: Loop in regno chain (%u)",
1214 if (vd->e[j].oldest_regno != i)
1215 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1216 j, vd->e[j].oldest_regno);
1218 SET_HARD_REG_BIT (set, j);
1222 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1223 if (! TEST_HARD_REG_BIT (set, i)
1224 && (vd->e[i].mode != VOIDmode
1225 || vd->e[i].oldest_regno != i
1226 || vd->e[i].next_regno != INVALID_REGNUM))
1227 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1228 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1229 vd->e[i].next_regno);
1233 namespace {
1235 const pass_data pass_data_cprop_hardreg =
1237 RTL_PASS, /* type */
1238 "cprop_hardreg", /* name */
1239 OPTGROUP_NONE, /* optinfo_flags */
1240 TV_CPROP_REGISTERS, /* tv_id */
1241 0, /* properties_required */
1242 0, /* properties_provided */
1243 0, /* properties_destroyed */
1244 0, /* todo_flags_start */
1245 TODO_df_finish, /* todo_flags_finish */
1248 class pass_cprop_hardreg : public rtl_opt_pass
1250 public:
1251 pass_cprop_hardreg (gcc::context *ctxt)
1252 : rtl_opt_pass (pass_data_cprop_hardreg, ctxt)
1255 /* opt_pass methods: */
1256 virtual bool gate (function *)
1258 return (optimize > 0 && (flag_cprop_registers));
1261 virtual unsigned int execute (function *);
1263 }; // class pass_cprop_hardreg
1265 unsigned int
1266 pass_cprop_hardreg::execute (function *fun)
1268 struct value_data *all_vd;
1269 basic_block bb;
1270 bool analyze_called = false;
1272 all_vd = XNEWVEC (struct value_data, last_basic_block_for_fn (fun));
1274 auto_sbitmap visited (last_basic_block_for_fn (fun));
1275 bitmap_clear (visited);
1277 FOR_EACH_BB_FN (bb, fun)
1279 bitmap_set_bit (visited, bb->index);
1281 /* If a block has a single predecessor, that we've already
1282 processed, begin with the value data that was live at
1283 the end of the predecessor block. */
1284 /* ??? Ought to use more intelligent queuing of blocks. */
1285 if (single_pred_p (bb)
1286 && bitmap_bit_p (visited, single_pred (bb)->index)
1287 && ! (single_pred_edge (bb)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
1289 all_vd[bb->index] = all_vd[single_pred (bb)->index];
1290 if (all_vd[bb->index].n_debug_insn_changes)
1292 unsigned int regno;
1294 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1296 if (all_vd[bb->index].e[regno].debug_insn_changes)
1298 all_vd[bb->index].e[regno].debug_insn_changes = NULL;
1299 if (--all_vd[bb->index].n_debug_insn_changes == 0)
1300 break;
1305 else
1306 init_value_data (all_vd + bb->index);
1308 copyprop_hardreg_forward_1 (bb, all_vd + bb->index);
1311 if (MAY_HAVE_DEBUG_INSNS)
1313 FOR_EACH_BB_FN (bb, fun)
1314 if (bitmap_bit_p (visited, bb->index)
1315 && all_vd[bb->index].n_debug_insn_changes)
1317 unsigned int regno;
1318 bitmap live;
1320 if (!analyze_called)
1322 df_analyze ();
1323 analyze_called = true;
1325 live = df_get_live_out (bb);
1326 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1327 if (all_vd[bb->index].e[regno].debug_insn_changes)
1329 if (REGNO_REG_SET_P (live, regno))
1330 apply_debug_insn_changes (all_vd + bb->index, regno);
1331 if (all_vd[bb->index].n_debug_insn_changes == 0)
1332 break;
1336 queued_debug_insn_change_pool.release ();
1339 free (all_vd);
1340 return 0;
1343 } // anon namespace
1345 rtl_opt_pass *
1346 make_pass_cprop_hardreg (gcc::context *ctxt)
1348 return new pass_cprop_hardreg (ctxt);