1/* Copy propagation on hard registers for the GNU compiler.
2 Copyright (C) 2000-2017 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>. */
19
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"
37#include "target.h"
38
39/* The following code does forward propagation of hard register copies.
40 The object is to eliminate as many dependencies as possible, so that
41 we have the most scheduling freedom. As a side effect, we also clean
42 up some silly register allocation decisions made by reload. This
43 code may be obsoleted by a new register allocator. */
44
45/* DEBUG_INSNs aren't changed right away, as doing so might extend the
46 lifetime of a register and get the DEBUG_INSN subsequently reset.
47 So they are queued instead, and updated only when the register is
48 used in some subsequent real insn before it is set. */
49struct queued_debug_insn_change
50{
51 struct queued_debug_insn_change *next;
52 rtx_insn *insn;
53 rtx *loc;
54 rtx new_rtx;
55};
56
57/* For each register, we have a list of registers that contain the same
58 value. The OLDEST_REGNO field points to the head of the list, and
59 the NEXT_REGNO field runs through the list. The MODE field indicates
60 what mode the data is known to be in; this field is VOIDmode when the
61 register is not known to contain valid data. */
62
63struct value_data_entry
64{
65 machine_mode mode;
66 unsigned int oldest_regno;
67 unsigned int next_regno;
68 struct queued_debug_insn_change *debug_insn_changes;
69};
70
71struct value_data
72{
73 struct value_data_entry e[FIRST_PSEUDO_REGISTER];
74 unsigned int max_value_regs;
75 unsigned int n_debug_insn_changes;
76};
77
78static object_allocator<queued_debug_insn_change> queued_debug_insn_change_pool
79 ("debug insn changes pool");
80
81static bool skip_debug_insn_p;
82
83static void kill_value_one_regno (unsigned, struct value_data *);
84static void kill_value_regno (unsigned, unsigned, struct value_data *);
85static void kill_value (const_rtx, struct value_data *);
86static void set_value_regno (unsigned, machine_mode, struct value_data *);
87static void init_value_data (struct value_data *);
88static void kill_clobbered_value (rtx, const_rtx, void *);
89static void kill_set_value (rtx, const_rtx, void *);
90static void copy_value (rtx, rtx, struct value_data *);
91static bool mode_change_ok (machine_mode, machine_mode,
92 unsigned int);
93static rtx maybe_mode_change (machine_mode, machine_mode,
94 machine_mode, unsigned int, unsigned int);
95static rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *);
96static bool replace_oldest_value_reg (rtx *, enum reg_class, rtx_insn *,
97 struct value_data *);
98static bool replace_oldest_value_addr (rtx *, enum reg_class,
99 machine_mode, addr_space_t,
100 rtx_insn *, struct value_data *);
101static bool replace_oldest_value_mem (rtx, rtx_insn *, struct value_data *);
102static bool copyprop_hardreg_forward_1 (basic_block, struct value_data *);
103extern void debug_value_data (struct value_data *);
104static void validate_value_data (struct value_data *);
105
106/* Free all queued updates for DEBUG_INSNs that change some reg to
107 register REGNO. */
108
109static void
110free_debug_insn_changes (struct value_data *vd, unsigned int regno)
111{
112 struct queued_debug_insn_change *cur, *next;
113 for (cur = vd->e[regno].debug_insn_changes; cur; cur = next)
114 {
115 next = cur->next;
116 --vd->n_debug_insn_changes;
117 queued_debug_insn_change_pool.remove (cur);
118 }
119 vd->e[regno].debug_insn_changes = NULL;
120}
121
122/* Kill register REGNO. This involves removing it from any value
123 lists, and resetting the value mode to VOIDmode. This is only a
124 helper function; it does not handle any hard registers overlapping
125 with REGNO. */
126
127static void
128kill_value_one_regno (unsigned int regno, struct value_data *vd)
129{
130 unsigned int i, next;
131
132 if (vd->e[regno].oldest_regno != regno)
133 {
134 for (i = vd->e[regno].oldest_regno;
135 vd->e[i].next_regno != regno;
136 i = vd->e[i].next_regno)
137 continue;
138 vd->e[i].next_regno = vd->e[regno].next_regno;
139 }
140 else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM)
141 {
142 for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno)
143 vd->e[i].oldest_regno = next;
144 }
145
146 vd->e[regno].mode = VOIDmode;
147 vd->e[regno].oldest_regno = regno;
148 vd->e[regno].next_regno = INVALID_REGNUM;
149 if (vd->e[regno].debug_insn_changes)
150 free_debug_insn_changes (vd, regno);
151
152 if (flag_checking)
153 validate_value_data (vd);
154}
155
156/* Kill the value in register REGNO for NREGS, and any other registers
157 whose values overlap. */
158
159static void
160kill_value_regno (unsigned int regno, unsigned int nregs,
161 struct value_data *vd)
162{
163 unsigned int j;
164
165 /* Kill the value we're told to kill. */
166 for (j = 0; j < nregs; ++j)
167 kill_value_one_regno (regno + j, vd);
168
169 /* Kill everything that overlapped what we're told to kill. */
170 if (regno < vd->max_value_regs)
171 j = 0;
172 else
173 j = regno - vd->max_value_regs;
174 for (; j < regno; ++j)
175 {
176 unsigned int i, n;
177 if (vd->e[j].mode == VOIDmode)
178 continue;
179 n = hard_regno_nregs (j, vd->e[j].mode);
180 if (j + n > regno)
181 for (i = 0; i < n; ++i)
182 kill_value_one_regno (j + i, vd);
183 }
184}
185
186/* Kill X. This is a convenience function wrapping kill_value_regno
187 so that we mind the mode the register is in. */
188
189static void
190kill_value (const_rtx x, struct value_data *vd)
191{
192 if (GET_CODE (x) == SUBREG)
193 {
194 rtx tmp = simplify_subreg (GET_MODE (x), SUBREG_REG (x),
195 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
196 x = tmp ? tmp : SUBREG_REG (x);
197 }
198 if (REG_P (x))
199 kill_value_regno (REGNO (x), REG_NREGS (x), vd);
200}
201
202/* Remember that REGNO is valid in MODE. */
203
204static void
205set_value_regno (unsigned int regno, machine_mode mode,
206 struct value_data *vd)
207{
208 unsigned int nregs;
209
210 vd->e[regno].mode = mode;
211
212 nregs = hard_regno_nregs (regno, mode);
213 if (nregs > vd->max_value_regs)
214 vd->max_value_regs = nregs;
215}
216
217/* Initialize VD such that there are no known relationships between regs. */
218
219static void
220init_value_data (struct value_data *vd)
221{
222 int i;
223 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
224 {
225 vd->e[i].mode = VOIDmode;
226 vd->e[i].oldest_regno = i;
227 vd->e[i].next_regno = INVALID_REGNUM;
228 vd->e[i].debug_insn_changes = NULL;
229 }
230 vd->max_value_regs = 0;
231 vd->n_debug_insn_changes = 0;
232}
233
234/* Called through note_stores. If X is clobbered, kill its value. */
235
236static void
237kill_clobbered_value (rtx x, const_rtx set, void *data)
238{
239 struct value_data *const vd = (struct value_data *) data;
240 if (GET_CODE (set) == CLOBBER)
241 kill_value (x, vd);
242}
243
244/* A structure passed as data to kill_set_value through note_stores. */
245struct kill_set_value_data
246{
247 struct value_data *vd;
248 rtx ignore_set_reg;
249};
250
251/* Called through note_stores. If X is set, not clobbered, kill its
252 current value and install it as the root of its own value list. */
253
254static void
255kill_set_value (rtx x, const_rtx set, void *data)
256{
257 struct kill_set_value_data *ksvd = (struct kill_set_value_data *) data;
258 if (rtx_equal_p (x, ksvd->ignore_set_reg))
259 return;
260 if (GET_CODE (set) != CLOBBER)
261 {
262 kill_value (x, ksvd->vd);
263 if (REG_P (x))
264 set_value_regno (REGNO (x), GET_MODE (x), ksvd->vd);
265 }
266}
267
268/* Kill any register used in X as the base of an auto-increment expression,
269 and install that register as the root of its own value list. */
270
271static void
272kill_autoinc_value (rtx_insn *insn, struct value_data *vd)
273{
274 subrtx_iterator::array_type array;
275 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
276 {
277 const_rtx x = *iter;
278 if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
279 {
280 x = XEXP (x, 0);
281 kill_value (x, vd);
282 set_value_regno (REGNO (x), GET_MODE (x), vd);
283 iter.skip_subrtxes ();
284 }
285 }
286}
287
288/* Assert that SRC has been copied to DEST. Adjust the data structures
289 to reflect that SRC contains an older copy of the shared value. */
290
291static void
292copy_value (rtx dest, rtx src, struct value_data *vd)
293{
294 unsigned int dr = REGNO (dest);
295 unsigned int sr = REGNO (src);
296 unsigned int dn, sn;
297 unsigned int i;
298
299 /* ??? At present, it's possible to see noop sets. It'd be nice if
300 this were cleaned up beforehand... */
301 if (sr == dr)
302 return;
303
304 /* Do not propagate copies to the stack pointer, as that can leave
305 memory accesses with no scheduling dependency on the stack update. */
306 if (dr == STACK_POINTER_REGNUM)
307 return;
308
309 /* Likewise with the frame pointer, if we're using one. */
310 if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM)
311 return;
312
313 /* Do not propagate copies to fixed or global registers, patterns
314 can be relying to see particular fixed register or users can
315 expect the chosen global register in asm. */
316 if (fixed_regs[dr] || global_regs[dr])
317 return;
318
319 /* If SRC and DEST overlap, don't record anything. */
320 dn = REG_NREGS (dest);
321 sn = REG_NREGS (src);
322 if ((dr > sr && dr < sr + sn)
323 || (sr > dr && sr < dr + dn))
324 return;
325
326 /* If SRC had no assigned mode (i.e. we didn't know it was live)
327 assign it now and assume the value came from an input argument
328 or somesuch. */
329 if (vd->e[sr].mode == VOIDmode)
330 set_value_regno (sr, vd->e[dr].mode, vd);
331
332 /* If we are narrowing the input to a smaller number of hard regs,
333 and it is in big endian, we are really extracting a high part.
334 Since we generally associate a low part of a value with the value itself,
335 we must not do the same for the high part.
336 Note we can still get low parts for the same mode combination through
337 a two-step copy involving differently sized hard regs.
338 Assume hard regs fr* are 32 bits each, while r* are 64 bits each:
339 (set (reg:DI r0) (reg:DI fr0))
340 (set (reg:SI fr2) (reg:SI r0))
341 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
342 (set (reg:SI fr2) (reg:SI fr0))
343 loads the high part of (reg:DI fr0) into fr2.
344
345 We can't properly represent the latter case in our tables, so don't
346 record anything then. */
347 else if (sn < hard_regno_nregs (sr, vd->e[sr].mode)
348 && subreg_lowpart_offset (GET_MODE (dest), vd->e[sr].mode) != 0)
349 return;
350
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 > hard_regno_nregs (sr, vd->e[sr].mode))
355 return;
356
357 /* Link DR at the end of the value chain used by SR. */
358
359 vd->e[dr].oldest_regno = vd->e[sr].oldest_regno;
360
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;
364
365 if (flag_checking)
366 validate_value_data (vd);
367}
368
369/* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
370
371static bool
372mode_change_ok (machine_mode orig_mode, machine_mode new_mode,
373 unsigned int regno ATTRIBUTE_UNUSED)
374{
375 if (partial_subreg_p (orig_mode, new_mode))
376 return false;
377
378 return REG_CAN_CHANGE_MODE_P (regno, orig_mode, new_mode);
379}
380
381/* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
382 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
383 in NEW_MODE.
384 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
385
386static rtx
387maybe_mode_change (machine_mode orig_mode, machine_mode copy_mode,
388 machine_mode new_mode, unsigned int regno,
389 unsigned int copy_regno ATTRIBUTE_UNUSED)
390{
391 if (partial_subreg_p (copy_mode, orig_mode)
392 && partial_subreg_p (copy_mode, new_mode))
393 return NULL_RTX;
394
395 /* Avoid creating multiple copies of the stack pointer. Some ports
396 assume there is one and only one stack pointer.
397
398 It's unclear if we need to do the same for other special registers. */
399 if (regno == STACK_POINTER_REGNUM)
400 return NULL_RTX;
401
402 if (orig_mode == new_mode)
403 return gen_raw_REG (new_mode, regno);
404 else if (mode_change_ok (orig_mode, new_mode, regno))
405 {
406 int copy_nregs = hard_regno_nregs (copy_regno, copy_mode);
407 int use_nregs = hard_regno_nregs (copy_regno, new_mode);
408 int copy_offset
409 = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs);
410 unsigned int offset
411 = subreg_size_lowpart_offset (GET_MODE_SIZE (new_mode) + copy_offset,
412 GET_MODE_SIZE (orig_mode));
413 regno += subreg_regno_offset (regno, orig_mode, offset, new_mode);
414 if (targetm.hard_regno_mode_ok (regno, new_mode))
415 return gen_raw_REG (new_mode, regno);
416 }
417 return NULL_RTX;
418}
419
420/* Find the oldest copy of the value contained in REGNO that is in
421 register class CL and has mode MODE. If found, return an rtx
422 of that oldest register, otherwise return NULL. */
423
424static rtx
425find_oldest_value_reg (enum reg_class cl, rtx reg, struct value_data *vd)
426{
427 unsigned int regno = REGNO (reg);
428 machine_mode mode = GET_MODE (reg);
429 unsigned int i;
430
431 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
432
433 /* If we are accessing REG in some mode other that what we set it in,
434 make sure that the replacement is valid. In particular, consider
435 (set (reg:DI r11) (...))
436 (set (reg:SI r9) (reg:SI r11))
437 (set (reg:SI r10) (...))
438 (set (...) (reg:DI r9))
439 Replacing r9 with r11 is invalid. */
440 if (mode != vd->e[regno].mode
441 && REG_NREGS (reg) > hard_regno_nregs (regno, vd->e[regno].mode))
442 return NULL_RTX;
443
444 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno)
445 {
446 machine_mode oldmode = vd->e[i].mode;
447 rtx new_rtx;
448
449 if (!in_hard_reg_set_p (reg_class_contents[cl], mode, i))
450 continue;
451
452 new_rtx = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno);
453 if (new_rtx)
454 {
455 ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (reg);
456 REG_ATTRS (new_rtx) = REG_ATTRS (reg);
457 REG_POINTER (new_rtx) = REG_POINTER (reg);
458 return new_rtx;
459 }
460 }
461
462 return NULL_RTX;
463}
464
465/* If possible, replace the register at *LOC with the oldest register
466 in register class CL. Return true if successfully replaced. */
467
468static bool
469replace_oldest_value_reg (rtx *loc, enum reg_class cl, rtx_insn *insn,
470 struct value_data *vd)
471{
472 rtx new_rtx = find_oldest_value_reg (cl, *loc, vd);
473 if (new_rtx && (!DEBUG_INSN_P (insn) || !skip_debug_insn_p))
474 {
475 if (DEBUG_INSN_P (insn))
476 {
477 struct queued_debug_insn_change *change;
478
479 if (dump_file)
480 fprintf (dump_file, "debug_insn %u: queued replacing reg %u with %u\n",
481 INSN_UID (insn), REGNO (*loc), REGNO (new_rtx));
482
483 change = queued_debug_insn_change_pool.allocate ();
484 change->next = vd->e[REGNO (new_rtx)].debug_insn_changes;
485 change->insn = insn;
486 change->loc = loc;
487 change->new_rtx = new_rtx;
488 vd->e[REGNO (new_rtx)].debug_insn_changes = change;
489 ++vd->n_debug_insn_changes;
490 return true;
491 }
492 if (dump_file)
493 fprintf (dump_file, "insn %u: replaced reg %u with %u\n",
494 INSN_UID (insn), REGNO (*loc), REGNO (new_rtx));
495
496 validate_change (insn, loc, new_rtx, 1);
497 return true;
498 }
499 return false;
500}
501
502/* Similar to replace_oldest_value_reg, but *LOC contains an address.
503 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
504 BASE_REG_CLASS depending on how the register is being considered. */
505
506static bool
507replace_oldest_value_addr (rtx *loc, enum reg_class cl,
508 machine_mode mode, addr_space_t as,
509 rtx_insn *insn, struct value_data *vd)
510{
511 rtx x = *loc;
512 RTX_CODE code = GET_CODE (x);
513 const char *fmt;
514 int i, j;
515 bool changed = false;
516
517 switch (code)
518 {
519 case PLUS:
520 if (DEBUG_INSN_P (insn))
521 break;
522
523 {
524 rtx orig_op0 = XEXP (x, 0);
525 rtx orig_op1 = XEXP (x, 1);
526 RTX_CODE code0 = GET_CODE (orig_op0);
527 RTX_CODE code1 = GET_CODE (orig_op1);
528 rtx op0 = orig_op0;
529 rtx op1 = orig_op1;
530 rtx *locI = NULL;
531 rtx *locB = NULL;
532 enum rtx_code index_code = SCRATCH;
533
534 if (GET_CODE (op0) == SUBREG)
535 {
536 op0 = SUBREG_REG (op0);
537 code0 = GET_CODE (op0);
538 }
539
540 if (GET_CODE (op1) == SUBREG)
541 {
542 op1 = SUBREG_REG (op1);
543 code1 = GET_CODE (op1);
544 }
545
546 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
547 || code0 == ZERO_EXTEND || code1 == MEM)
548 {
549 locI = &XEXP (x, 0);
550 locB = &XEXP (x, 1);
551 index_code = GET_CODE (*locI);
552 }
553 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
554 || code1 == ZERO_EXTEND || code0 == MEM)
555 {
556 locI = &XEXP (x, 1);
557 locB = &XEXP (x, 0);
558 index_code = GET_CODE (*locI);
559 }
560 else if (code0 == CONST_INT || code0 == CONST
561 || code0 == SYMBOL_REF || code0 == LABEL_REF)
562 {
563 locB = &XEXP (x, 1);
564 index_code = GET_CODE (XEXP (x, 0));
565 }
566 else if (code1 == CONST_INT || code1 == CONST
567 || code1 == SYMBOL_REF || code1 == LABEL_REF)
568 {
569 locB = &XEXP (x, 0);
570 index_code = GET_CODE (XEXP (x, 1));
571 }
572 else if (code0 == REG && code1 == REG)
573 {
574 int index_op;
575 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
576
577 if (REGNO_OK_FOR_INDEX_P (regno1)
578 && regno_ok_for_base_p (regno0, mode, as, PLUS, REG))
579 index_op = 1;
580 else if (REGNO_OK_FOR_INDEX_P (regno0)
581 && regno_ok_for_base_p (regno1, mode, as, PLUS, REG))
582 index_op = 0;
583 else if (regno_ok_for_base_p (regno0, mode, as, PLUS, REG)
584 || REGNO_OK_FOR_INDEX_P (regno1))
585 index_op = 1;
586 else if (regno_ok_for_base_p (regno1, mode, as, PLUS, REG))
587 index_op = 0;
588 else
589 index_op = 1;
590
591 locI = &XEXP (x, index_op);
592 locB = &XEXP (x, !index_op);
593 index_code = GET_CODE (*locI);
594 }
595 else if (code0 == REG)
596 {
597 locI = &XEXP (x, 0);
598 locB = &XEXP (x, 1);
599 index_code = GET_CODE (*locI);
600 }
601 else if (code1 == REG)
602 {
603 locI = &XEXP (x, 1);
604 locB = &XEXP (x, 0);
605 index_code = GET_CODE (*locI);
606 }
607
608 if (locI)
609 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS,
610 mode, as, insn, vd);
611 if (locB)
612 changed |= replace_oldest_value_addr (locB,
613 base_reg_class (mode, as, PLUS,
614 index_code),
615 mode, as, insn, vd);
616 return changed;
617 }
618
619 case POST_INC:
620 case POST_DEC:
621 case POST_MODIFY:
622 case PRE_INC:
623 case PRE_DEC:
624 case PRE_MODIFY:
625 return false;
626
627 case MEM:
628 return replace_oldest_value_mem (x, insn, vd);
629
630 case REG:
631 return replace_oldest_value_reg (loc, cl, insn, vd);
632
633 default:
634 break;
635 }
636
637 fmt = GET_RTX_FORMAT (code);
638 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
639 {
640 if (fmt[i] == 'e')
641 changed |= replace_oldest_value_addr (&XEXP (x, i), cl, mode, as,
642 insn, vd);
643 else if (fmt[i] == 'E')
644 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
645 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), cl,
646 mode, as, insn, vd);
647 }
648
649 return changed;
650}
651
652/* Similar to replace_oldest_value_reg, but X contains a memory. */
653
654static bool
655replace_oldest_value_mem (rtx x, rtx_insn *insn, struct value_data *vd)
656{
657 enum reg_class cl;
658
659 if (DEBUG_INSN_P (insn))
660 cl = ALL_REGS;
661 else
662 cl = base_reg_class (GET_MODE (x), MEM_ADDR_SPACE (x), MEM, SCRATCH);
663
664 return replace_oldest_value_addr (&XEXP (x, 0), cl,
665 GET_MODE (x), MEM_ADDR_SPACE (x),
666 insn, vd);
667}
668
669/* Apply all queued updates for DEBUG_INSNs that change some reg to
670 register REGNO. */
671
672static void
673apply_debug_insn_changes (struct value_data *vd, unsigned int regno)
674{
675 struct queued_debug_insn_change *change;
676 rtx_insn *last_insn = vd->e[regno].debug_insn_changes->insn;
677
678 for (change = vd->e[regno].debug_insn_changes;
679 change;
680 change = change->next)
681 {
682 if (last_insn != change->insn)
683 {
684 apply_change_group ();
685 last_insn = change->insn;
686 }
687 validate_change (change->insn, change->loc, change->new_rtx, 1);
688 }
689 apply_change_group ();
690}
691
692/* Called via note_uses, for all used registers in a real insn
693 apply DEBUG_INSN changes that change registers to the used
694 registers. */
695
696static void
697cprop_find_used_regs (rtx *loc, void *data)
698{
699 struct value_data *const vd = (struct value_data *) data;
700 subrtx_iterator::array_type array;
701 FOR_EACH_SUBRTX (iter, array, *loc, NONCONST)
702 {
703 const_rtx x = *iter;
704 if (REG_P (x))
705 {
706 unsigned int regno = REGNO (x);
707 if (vd->e[regno].debug_insn_changes)
708 {
709 apply_debug_insn_changes (vd, regno);
710 free_debug_insn_changes (vd, regno);
711 }
712 }
713 }
714}
715
716/* Apply clobbers of INSN in PATTERN and C_I_F_U to value_data VD. */
717
718static void
719kill_clobbered_values (rtx_insn *insn, struct value_data *vd)
720{
721 note_stores (PATTERN (insn), kill_clobbered_value, vd);
722
723 if (CALL_P (insn))
724 {
725 rtx exp;
726
727 for (exp = CALL_INSN_FUNCTION_USAGE (insn); exp; exp = XEXP (exp, 1))
728 {
729 rtx x = XEXP (exp, 0);
730 if (GET_CODE (x) == CLOBBER)
731 kill_value (SET_DEST (x), vd);
732 }
733 }
734}
735
736/* Perform the forward copy propagation on basic block BB. */
737
738static bool
739copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd)
740{
741 bool anything_changed = false;
742 rtx_insn *insn, *next;
743
744 for (insn = BB_HEAD (bb); ; insn = next)
745 {
746 int n_ops, i, predicated;
747 bool is_asm, any_replacements;
748 rtx set;
749 rtx link;
750 bool replaced[MAX_RECOG_OPERANDS];
751 bool changed = false;
752 struct kill_set_value_data ksvd;
753
754 next = NEXT_INSN (insn);
755 if (!NONDEBUG_INSN_P (insn))
756 {
757 if (DEBUG_BIND_INSN_P (insn))
758 {
759 rtx loc = INSN_VAR_LOCATION_LOC (insn);
760 if (!VAR_LOC_UNKNOWN_P (loc))
761 replace_oldest_value_addr (&INSN_VAR_LOCATION_LOC (insn),
762 ALL_REGS, GET_MODE (loc),
763 ADDR_SPACE_GENERIC, insn, vd);
764 }
765
766 if (insn == BB_END (bb))
767 break;
768 else
769 continue;
770 }
771
772 set = single_set (insn);
773
774 /* Detect noop sets and remove them before processing side effects. */
775 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
776 {
777 unsigned int regno = REGNO (SET_SRC (set));
778 rtx r1 = find_oldest_value_reg (REGNO_REG_CLASS (regno),
779 SET_DEST (set), vd);
780 rtx r2 = find_oldest_value_reg (REGNO_REG_CLASS (regno),
781 SET_SRC (set), vd);
782 if (rtx_equal_p (r1 ? r1 : SET_DEST (set), r2 ? r2 : SET_SRC (set)))
783 {
784 bool last = insn == BB_END (bb);
785 delete_insn (insn);
786 if (last)
787 break;
788 continue;
789 }
790 }
791
792 extract_constrain_insn (insn);
793 preprocess_constraints (insn);
794 const operand_alternative *op_alt = which_op_alt ();
795 n_ops = recog_data.n_operands;
796 is_asm = asm_noperands (PATTERN (insn)) >= 0;
797
798 /* Simplify the code below by promoting OP_OUT to OP_INOUT
799 in predicated instructions. */
800
801 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
802 for (i = 0; i < n_ops; ++i)
803 {
804 int matches = op_alt[i].matches;
805 if (matches >= 0 || op_alt[i].matched >= 0
806 || (predicated && recog_data.operand_type[i] == OP_OUT))
807 recog_data.operand_type[i] = OP_INOUT;
808 }
809
810 /* Apply changes to earlier DEBUG_INSNs if possible. */
811 if (vd->n_debug_insn_changes)
812 note_uses (&PATTERN (insn), cprop_find_used_regs, vd);
813
814 /* For each earlyclobber operand, zap the value data. */
815 for (i = 0; i < n_ops; i++)
816 if (op_alt[i].earlyclobber)
817 kill_value (recog_data.operand[i], vd);
818
819 /* Within asms, a clobber cannot overlap inputs or outputs.
820 I wouldn't think this were true for regular insns, but
821 scan_rtx treats them like that... */
822 kill_clobbered_values (insn, vd);
823
824 /* Kill all auto-incremented values. */
825 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
826 kill_autoinc_value (insn, vd);
827
828 /* Kill all early-clobbered operands. */
829 for (i = 0; i < n_ops; i++)
830 if (op_alt[i].earlyclobber)
831 kill_value (recog_data.operand[i], vd);
832
833 /* If we have dead sets in the insn, then we need to note these as we
834 would clobbers. */
835 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
836 {
837 if (REG_NOTE_KIND (link) == REG_UNUSED)
838 {
839 kill_value (XEXP (link, 0), vd);
840 /* Furthermore, if the insn looked like a single-set,
841 but the dead store kills the source value of that
842 set, then we can no-longer use the plain move
843 special case below. */
844 if (set
845 && reg_overlap_mentioned_p (XEXP (link, 0), SET_SRC (set)))
846 set = NULL;
847 }
848 }
849
850 /* Special-case plain move instructions, since we may well
851 be able to do the move from a different register class. */
852 if (set && REG_P (SET_SRC (set)))
853 {
854 rtx src = SET_SRC (set);
855 unsigned int regno = REGNO (src);
856 machine_mode mode = GET_MODE (src);
857 unsigned int i;
858 rtx new_rtx;
859
860 /* If we are accessing SRC in some mode other that what we
861 set it in, make sure that the replacement is valid. */
862 if (mode != vd->e[regno].mode)
863 {
864 if (REG_NREGS (src)
865 > hard_regno_nregs (regno, vd->e[regno].mode))
866 goto no_move_special_case;
867
868 /* And likewise, if we are narrowing on big endian the transformation
869 is also invalid. */
870 if (REG_NREGS (src) < hard_regno_nregs (regno, vd->e[regno].mode)
871 && subreg_lowpart_offset (mode, vd->e[regno].mode) != 0)
872 goto no_move_special_case;
873 }
874
875 /* If the destination is also a register, try to find a source
876 register in the same class. */
877 if (REG_P (SET_DEST (set)))
878 {
879 new_rtx = find_oldest_value_reg (REGNO_REG_CLASS (regno),
880 src, vd);
881
882 if (new_rtx && validate_change (insn, &SET_SRC (set), new_rtx, 0))
883 {
884 if (dump_file)
885 fprintf (dump_file,
886 "insn %u: replaced reg %u with %u\n",
887 INSN_UID (insn), regno, REGNO (new_rtx));
888 changed = true;
889 goto did_replacement;
890 }
891 /* We need to re-extract as validate_change clobbers
892 recog_data. */
893 extract_constrain_insn (insn);
894 preprocess_constraints (insn);
895 }
896
897 /* Otherwise, try all valid registers and see if its valid. */
898 for (i = vd->e[regno].oldest_regno; i != regno;
899 i = vd->e[i].next_regno)
900 {
901 new_rtx = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode,
902 mode, i, regno);
903 if (new_rtx != NULL_RTX)
904 {
905 if (validate_change (insn, &SET_SRC (set), new_rtx, 0))
906 {
907 ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (src);
908 REG_ATTRS (new_rtx) = REG_ATTRS (src);
909 REG_POINTER (new_rtx) = REG_POINTER (src);
910 if (dump_file)
911 fprintf (dump_file,
912 "insn %u: replaced reg %u with %u\n",
913 INSN_UID (insn), regno, REGNO (new_rtx));
914 changed = true;
915 goto did_replacement;
916 }
917 /* We need to re-extract as validate_change clobbers
918 recog_data. */
919 extract_constrain_insn (insn);
920 preprocess_constraints (insn);
921 }
922 }
923 }
924 no_move_special_case:
925
926 any_replacements = false;
927
928 /* For each input operand, replace a hard register with the
929 eldest live copy that's in an appropriate register class. */
930 for (i = 0; i < n_ops; i++)
931 {
932 replaced[i] = false;
933
934 /* Don't scan match_operand here, since we've no reg class
935 information to pass down. Any operands that we could
936 substitute in will be represented elsewhere. */
937 if (recog_data.constraints[i][0] == '\0')
938 continue;
939
940 /* Don't replace in asms intentionally referencing hard regs. */
941 if (is_asm && REG_P (recog_data.operand[i])
942 && (REGNO (recog_data.operand[i])
943 == ORIGINAL_REGNO (recog_data.operand[i])))
944 continue;
945
946 if (recog_data.operand_type[i] == OP_IN)
947 {
948 if (op_alt[i].is_address)
949 replaced[i]
950 = replace_oldest_value_addr (recog_data.operand_loc[i],
951 alternative_class (op_alt, i),
952 VOIDmode, ADDR_SPACE_GENERIC,
953 insn, vd);
954 else if (REG_P (recog_data.operand[i]))
955 replaced[i]
956 = replace_oldest_value_reg (recog_data.operand_loc[i],
957 alternative_class (op_alt, i),
958 insn, vd);
959 else if (MEM_P (recog_data.operand[i]))
960 replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
961 insn, vd);
962 }
963 else if (MEM_P (recog_data.operand[i]))
964 replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
965 insn, vd);
966
967 /* If we performed any replacement, update match_dups. */
968 if (replaced[i])
969 {
970 int j;
971 rtx new_rtx;
972
973 new_rtx = *recog_data.operand_loc[i];
974 recog_data.operand[i] = new_rtx;
975 for (j = 0; j < recog_data.n_dups; j++)
976 if (recog_data.dup_num[j] == i)
977 validate_unshare_change (insn, recog_data.dup_loc[j], new_rtx, 1);
978
979 any_replacements = true;
980 }
981 }
982
983 if (any_replacements)
984 {
985 if (! apply_change_group ())
986 {
987 for (i = 0; i < n_ops; i++)
988 if (replaced[i])
989 {
990 rtx old = *recog_data.operand_loc[i];
991 recog_data.operand[i] = old;
992 }
993
994 if (dump_file)
995 fprintf (dump_file,
996 "insn %u: reg replacements not verified\n",
997 INSN_UID (insn));
998 }
999 else
1000 changed = true;
1001 }
1002
1003 did_replacement:
1004 if (changed)
1005 {
1006 anything_changed = true;
1007
1008 /* If something changed, perhaps further changes to earlier
1009 DEBUG_INSNs can be applied. */
1010 if (vd->n_debug_insn_changes)
1011 note_uses (&PATTERN (insn), cprop_find_used_regs, vd);
1012 }
1013
1014 ksvd.vd = vd;
1015 ksvd.ignore_set_reg = NULL_RTX;
1016
1017 /* Clobber call-clobbered registers. */
1018 if (CALL_P (insn))
1019 {
1020 unsigned int set_regno = INVALID_REGNUM;
1021 unsigned int set_nregs = 0;
1022 unsigned int regno;
1023 rtx exp;
1024 HARD_REG_SET regs_invalidated_by_this_call;
1025
1026 for (exp = CALL_INSN_FUNCTION_USAGE (insn); exp; exp = XEXP (exp, 1))
1027 {
1028 rtx x = XEXP (exp, 0);
1029 if (GET_CODE (x) == SET)
1030 {
1031 rtx dest = SET_DEST (x);
1032 kill_value (dest, vd);
1033 set_value_regno (REGNO (dest), GET_MODE (dest), vd);
1034 copy_value (dest, SET_SRC (x), vd);
1035 ksvd.ignore_set_reg = dest;
1036 set_regno = REGNO (dest);
1037 set_nregs = REG_NREGS (dest);
1038 break;
1039 }
1040 }
1041
1042 get_call_reg_set_usage (insn,
1043 &regs_invalidated_by_this_call,
1044 regs_invalidated_by_call);
1045 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1046 if ((TEST_HARD_REG_BIT (regs_invalidated_by_this_call, regno)
1047 || (targetm.hard_regno_call_part_clobbered
1048 (regno, vd->e[regno].mode)))
1049 && (regno < set_regno || regno >= set_regno + set_nregs))
1050 kill_value_regno (regno, 1, vd);
1051
1052 /* If SET was seen in CALL_INSN_FUNCTION_USAGE, and SET_SRC
1053 of the SET isn't in regs_invalidated_by_call hard reg set,
1054 but instead among CLOBBERs on the CALL_INSN, we could wrongly
1055 assume the value in it is still live. */
1056 if (ksvd.ignore_set_reg)
1057 kill_clobbered_values (insn, vd);
1058 }
1059
1060 bool copy_p = (set
1061 && REG_P (SET_DEST (set))
1062 && REG_P (SET_SRC (set)));
1063 bool noop_p = (copy_p
1064 && rtx_equal_p (SET_DEST (set), SET_SRC (set)));
1065
1066 /* If a noop move is using narrower mode than we have recorded,
1067 we need to either remove the noop move, or kill_set_value. */
1068 if (noop_p
1069 && partial_subreg_p (GET_MODE (SET_DEST (set)),
1070 vd->e[REGNO (SET_DEST (set))].mode))
1071 {
1072 if (noop_move_p (insn))
1073 {
1074 bool last = insn == BB_END (bb);
1075 delete_insn (insn);
1076 if (last)
1077 break;
1078 }
1079 else
1080 noop_p = false;
1081 }
1082
1083 if (!noop_p)
1084 {
1085 /* Notice stores. */
1086 note_stores (PATTERN (insn), kill_set_value, &ksvd);
1087
1088 /* Notice copies. */
1089 if (copy_p)
1090 copy_value (SET_DEST (set), SET_SRC (set), vd);
1091 }
1092
1093 if (insn == BB_END (bb))
1094 break;
1095 }
1096
1097 return anything_changed;
1098}
1099
1100/* Dump the value chain data to stderr. */
1101
1102DEBUG_FUNCTION void
1103debug_value_data (struct value_data *vd)
1104{
1105 HARD_REG_SET set;
1106 unsigned int i, j;
1107
1108 CLEAR_HARD_REG_SET (set);
1109
1110 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1111 if (vd->e[i].oldest_regno == i)
1112 {
1113 if (vd->e[i].mode == VOIDmode)
1114 {
1115 if (vd->e[i].next_regno != INVALID_REGNUM)
1116 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n",
1117 i, vd->e[i].next_regno);
1118 continue;
1119 }
1120
1121 SET_HARD_REG_BIT (set, i);
1122 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode));
1123
1124 for (j = vd->e[i].next_regno;
1125 j != INVALID_REGNUM;
1126 j = vd->e[j].next_regno)
1127 {
1128 if (TEST_HARD_REG_BIT (set, j))
1129 {
1130 fprintf (stderr, "[%u] Loop in regno chain\n", j);
1131 return;
1132 }
1133
1134 if (vd->e[j].oldest_regno != i)
1135 {
1136 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n",
1137 j, vd->e[j].oldest_regno);
1138 return;
1139 }
1140 SET_HARD_REG_BIT (set, j);
1141 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode));
1142 }
1143 fputc ('\n', stderr);
1144 }
1145
1146 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1147 if (! TEST_HARD_REG_BIT (set, i)
1148 && (vd->e[i].mode != VOIDmode
1149 || vd->e[i].oldest_regno != i
1150 || vd->e[i].next_regno != INVALID_REGNUM))
1151 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n",
1152 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1153 vd->e[i].next_regno);
1154}
1155
1156/* Do copyprop_hardreg_forward_1 for a single basic block BB.
1157 DEBUG_INSN is skipped since we do not want to involve DF related
1158 staff as how it is handled in function pass_cprop_hardreg::execute.
1159
1160 NOTE: Currently it is only used for shrink-wrap. Maybe extend it
1161 to handle DEBUG_INSN for other uses. */
1162
1163void
1164copyprop_hardreg_forward_bb_without_debug_insn (basic_block bb)
1165{
1166 struct value_data *vd;
1167 vd = XNEWVEC (struct value_data, 1);
1168 init_value_data (vd);
1169
1170 skip_debug_insn_p = true;
1171 copyprop_hardreg_forward_1 (bb, vd);
1172 free (vd);
1173 skip_debug_insn_p = false;
1174}
1175
1176static void
1177validate_value_data (struct value_data *vd)
1178{
1179 HARD_REG_SET set;
1180 unsigned int i, j;
1181
1182 CLEAR_HARD_REG_SET (set);
1183
1184 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1185 if (vd->e[i].oldest_regno == i)
1186 {
1187 if (vd->e[i].mode == VOIDmode)
1188 {
1189 if (vd->e[i].next_regno != INVALID_REGNUM)
1190 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1191 i, vd->e[i].next_regno);
1192 continue;
1193 }
1194
1195 SET_HARD_REG_BIT (set, i);
1196
1197 for (j = vd->e[i].next_regno;
1198 j != INVALID_REGNUM;
1199 j = vd->e[j].next_regno)
1200 {
1201 if (TEST_HARD_REG_BIT (set, j))
1202 internal_error ("validate_value_data: Loop in regno chain (%u)",
1203 j);
1204 if (vd->e[j].oldest_regno != i)
1205 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1206 j, vd->e[j].oldest_regno);
1207
1208 SET_HARD_REG_BIT (set, j);
1209 }
1210 }
1211
1212 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1213 if (! TEST_HARD_REG_BIT (set, i)
1214 && (vd->e[i].mode != VOIDmode
1215 || vd->e[i].oldest_regno != i
1216 || vd->e[i].next_regno != INVALID_REGNUM))
1217 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1218 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1219 vd->e[i].next_regno);
1220}
1221
1222
1223namespace {
1224
1225const pass_data pass_data_cprop_hardreg =
1226{
1227 RTL_PASS, /* type */
1228 "cprop_hardreg", /* name */
1229 OPTGROUP_NONE, /* optinfo_flags */
1230 TV_CPROP_REGISTERS, /* tv_id */
1231 0, /* properties_required */
1232 0, /* properties_provided */
1233 0, /* properties_destroyed */
1234 0, /* todo_flags_start */
1235 TODO_df_finish, /* todo_flags_finish */
1236};
1237
1238class pass_cprop_hardreg : public rtl_opt_pass
1239{
1240public:
1241 pass_cprop_hardreg (gcc::context *ctxt)
1242 : rtl_opt_pass (pass_data_cprop_hardreg, ctxt)
1243 {}
1244
1245 /* opt_pass methods: */
1246 virtual bool gate (function *)
1247 {
1248 return (optimize > 0 && (flag_cprop_registers));
1249 }
1250
1251 virtual unsigned int execute (function *);
1252
1253}; // class pass_cprop_hardreg
1254
1255unsigned int
1256pass_cprop_hardreg::execute (function *fun)
1257{
1258 struct value_data *all_vd;
1259 basic_block bb;
1260 bool analyze_called = false;
1261
1262 all_vd = XNEWVEC (struct value_data, last_basic_block_for_fn (fun));
1263
1264 auto_sbitmap visited (last_basic_block_for_fn (fun));
1265 bitmap_clear (visited);
1266
1267 FOR_EACH_BB_FN (bb, fun)
1268 {
1269 bitmap_set_bit (visited, bb->index);
1270
1271 /* If a block has a single predecessor, that we've already
1272 processed, begin with the value data that was live at
1273 the end of the predecessor block. */
1274 /* ??? Ought to use more intelligent queuing of blocks. */
1275 if (single_pred_p (bb)
1276 && bitmap_bit_p (visited, single_pred (bb)->index)
1277 && ! (single_pred_edge (bb)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
1278 {
1279 all_vd[bb->index] = all_vd[single_pred (bb)->index];
1280 if (all_vd[bb->index].n_debug_insn_changes)
1281 {
1282 unsigned int regno;
1283
1284 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1285 {
1286 if (all_vd[bb->index].e[regno].debug_insn_changes)
1287 {
1288 all_vd[bb->index].e[regno].debug_insn_changes = NULL;
1289 if (--all_vd[bb->index].n_debug_insn_changes == 0)
1290 break;
1291 }
1292 }
1293 }
1294 }
1295 else
1296 init_value_data (all_vd + bb->index);
1297
1298 copyprop_hardreg_forward_1 (bb, all_vd + bb->index);
1299 }
1300
1301 if (MAY_HAVE_DEBUG_BIND_INSNS)
1302 {
1303 FOR_EACH_BB_FN (bb, fun)
1304 if (bitmap_bit_p (visited, bb->index)
1305 && all_vd[bb->index].n_debug_insn_changes)
1306 {
1307 unsigned int regno;
1308 bitmap live;
1309
1310 if (!analyze_called)
1311 {
1312 df_analyze ();
1313 analyze_called = true;
1314 }
1315 live = df_get_live_out (bb);
1316 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1317 if (all_vd[bb->index].e[regno].debug_insn_changes)
1318 {
1319 if (REGNO_REG_SET_P (live, regno))
1320 apply_debug_insn_changes (all_vd + bb->index, regno);
1321 if (all_vd[bb->index].n_debug_insn_changes == 0)
1322 break;
1323 }
1324 }
1325
1326 queued_debug_insn_change_pool.release ();
1327 }
1328
1329 free (all_vd);
1330 return 0;
1331}
1332
1333} // anon namespace
1334
1335rtl_opt_pass *
1336make_pass_cprop_hardreg (gcc::context *ctxt)
1337{
1338 return new pass_cprop_hardreg (ctxt);
1339}
1340