1/* RTL-based forward propagation pass for GNU compiler.
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
3 Contributed by Paolo Bonzini and Steven Bosscher.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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 "backend.h"
25#include "target.h"
26#include "rtl.h"
27#include "predict.h"
28#include "df.h"
29#include "memmodel.h"
30#include "tm_p.h"
31#include "insn-config.h"
32#include "emit-rtl.h"
33#include "recog.h"
34
35#include "sparseset.h"
36#include "cfgrtl.h"
37#include "cfgcleanup.h"
38#include "cfgloop.h"
39#include "tree-pass.h"
40#include "domwalk.h"
41#include "rtl-iter.h"
42
43
44/* This pass does simple forward propagation and simplification when an
45 operand of an insn can only come from a single def. This pass uses
46 df.c, so it is global. However, we only do limited analysis of
47 available expressions.
48
49 1) The pass tries to propagate the source of the def into the use,
50 and checks if the result is independent of the substituted value.
51 For example, the high word of a (zero_extend:DI (reg:SI M)) is always
52 zero, independent of the source register.
53
54 In particular, we propagate constants into the use site. Sometimes
55 RTL expansion did not put the constant in the same insn on purpose,
56 to satisfy a predicate, and the result will fail to be recognized;
57 but this happens rarely and in this case we can still create a
58 REG_EQUAL note. For multi-word operations, this
59
60 (set (subreg:SI (reg:DI 120) 0) (const_int 0))
61 (set (subreg:SI (reg:DI 120) 4) (const_int -1))
62 (set (subreg:SI (reg:DI 122) 0)
63 (ior:SI (subreg:SI (reg:DI 119) 0) (subreg:SI (reg:DI 120) 0)))
64 (set (subreg:SI (reg:DI 122) 4)
65 (ior:SI (subreg:SI (reg:DI 119) 4) (subreg:SI (reg:DI 120) 4)))
66
67 can be simplified to the much simpler
68
69 (set (subreg:SI (reg:DI 122) 0) (subreg:SI (reg:DI 119)))
70 (set (subreg:SI (reg:DI 122) 4) (const_int -1))
71
72 This particular propagation is also effective at putting together
73 complex addressing modes. We are more aggressive inside MEMs, in
74 that all definitions are propagated if the use is in a MEM; if the
75 result is a valid memory address we check address_cost to decide
76 whether the substitution is worthwhile.
77
78 2) The pass propagates register copies. This is not as effective as
79 the copy propagation done by CSE's canon_reg, which works by walking
80 the instruction chain, it can help the other transformations.
81
82 We should consider removing this optimization, and instead reorder the
83 RTL passes, because GCSE does this transformation too. With some luck,
84 the CSE pass at the end of rest_of_handle_gcse could also go away.
85
86 3) The pass looks for paradoxical subregs that are actually unnecessary.
87 Things like this:
88
89 (set (reg:QI 120) (subreg:QI (reg:SI 118) 0))
90 (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
91 (set (reg:SI 122) (plus:SI (subreg:SI (reg:QI 120) 0)
92 (subreg:SI (reg:QI 121) 0)))
93
94 are very common on machines that can only do word-sized operations.
95 For each use of a paradoxical subreg (subreg:WIDER (reg:NARROW N) 0),
96 if it has a single def and it is (subreg:NARROW (reg:WIDE M) 0),
97 we can replace the paradoxical subreg with simply (reg:WIDE M). The
98 above will simplify this to
99
100 (set (reg:QI 120) (subreg:QI (reg:SI 118) 0))
101 (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
102 (set (reg:SI 122) (plus:SI (reg:SI 118) (reg:SI 119)))
103
104 where the first two insns are now dead.
105
106 We used to use reaching definitions to find which uses have a
107 single reaching definition (sounds obvious...), but this is too
108 complex a problem in nasty testcases like PR33928. Now we use the
109 multiple definitions problem in df-problems.c. The similarity
110 between that problem and SSA form creation is taken further, in
111 that fwprop does a dominator walk to create its chains; however,
112 instead of creating a PHI function where multiple definitions meet
113 I just punt and record only singleton use-def chains, which is
114 all that is needed by fwprop. */
115
116
117static int num_changes;
118
119static vec<df_ref> use_def_ref;
120static vec<df_ref> reg_defs;
121static vec<df_ref> reg_defs_stack;
122
123/* The maximum number of propagations that are still allowed. If we do
124 more propagations than originally we had uses, we must have ended up
125 in a propagation loop, as in PR79405. Until the algorithm fwprop
126 uses can obviously not get into such loops we need a workaround like
127 this. */
128static int propagations_left;
129
130/* The MD bitmaps are trimmed to include only live registers to cut
131 memory usage on testcases like insn-recog.c. Track live registers
132 in the basic block and do not perform forward propagation if the
133 destination is a dead pseudo occurring in a note. */
134static bitmap local_md;
135static bitmap local_lr;
136
137/* Return the only def in USE's use-def chain, or NULL if there is
138 more than one def in the chain. */
139
140static inline df_ref
141get_def_for_use (df_ref use)
142{
143 return use_def_ref[DF_REF_ID (use)];
144}
145
146
147/* Update the reg_defs vector with non-partial definitions in DEF_REC.
148 TOP_FLAG says which artificials uses should be used, when DEF_REC
149 is an artificial def vector. LOCAL_MD is modified as after a
150 df_md_simulate_* function; we do more or less the same processing
151 done there, so we do not use those functions. */
152
153#define DF_MD_GEN_FLAGS \
154 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
155
156static void
157process_defs (df_ref def, int top_flag)
158{
159 for (; def; def = DF_REF_NEXT_LOC (def))
160 {
161 df_ref curr_def = reg_defs[DF_REF_REGNO (def)];
162 unsigned int dregno;
163
164 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag)
165 continue;
166
167 dregno = DF_REF_REGNO (def);
168 if (curr_def)
169 reg_defs_stack.safe_push (curr_def);
170 else
171 {
172 /* Do not store anything if "transitioning" from NULL to NULL. But
173 otherwise, push a special entry on the stack to tell the
174 leave_block callback that the entry in reg_defs was NULL. */
175 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
176 ;
177 else
178 reg_defs_stack.safe_push (def);
179 }
180
181 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
182 {
183 bitmap_set_bit (local_md, dregno);
184 reg_defs[dregno] = NULL;
185 }
186 else
187 {
188 bitmap_clear_bit (local_md, dregno);
189 reg_defs[dregno] = def;
190 }
191 }
192}
193
194
195/* Fill the use_def_ref vector with values for the uses in USE_REC,
196 taking reaching definitions info from LOCAL_MD and REG_DEFS.
197 TOP_FLAG says which artificials uses should be used, when USE_REC
198 is an artificial use vector. */
199
200static void
201process_uses (df_ref use, int top_flag)
202{
203 for (; use; use = DF_REF_NEXT_LOC (use))
204 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag)
205 {
206 unsigned int uregno = DF_REF_REGNO (use);
207 if (reg_defs[uregno]
208 && !bitmap_bit_p (local_md, uregno)
209 && bitmap_bit_p (local_lr, uregno))
210 use_def_ref[DF_REF_ID (use)] = reg_defs[uregno];
211 }
212}
213
214class single_def_use_dom_walker : public dom_walker
215{
216public:
217 single_def_use_dom_walker (cdi_direction direction)
218 : dom_walker (direction) {}
219 virtual edge before_dom_children (basic_block);
220 virtual void after_dom_children (basic_block);
221};
222
223edge
224single_def_use_dom_walker::before_dom_children (basic_block bb)
225{
226 int bb_index = bb->index;
227 struct df_md_bb_info *md_bb_info = df_md_get_bb_info (bb_index);
228 struct df_lr_bb_info *lr_bb_info = df_lr_get_bb_info (bb_index);
229 rtx_insn *insn;
230
231 bitmap_copy (local_md, &md_bb_info->in);
232 bitmap_copy (local_lr, &lr_bb_info->in);
233
234 /* Push a marker for the leave_block callback. */
235 reg_defs_stack.safe_push (NULL);
236
237 process_uses (df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
238 process_defs (df_get_artificial_defs (bb_index), DF_REF_AT_TOP);
239
240 /* We don't call df_simulate_initialize_forwards, as it may overestimate
241 the live registers if there are unused artificial defs. We prefer
242 liveness to be underestimated. */
243
244 FOR_BB_INSNS (bb, insn)
245 if (INSN_P (insn))
246 {
247 unsigned int uid = INSN_UID (insn);
248 process_uses (DF_INSN_UID_USES (uid), 0);
249 process_uses (DF_INSN_UID_EQ_USES (uid), 0);
250 process_defs (DF_INSN_UID_DEFS (uid), 0);
251 df_simulate_one_insn_forwards (bb, insn, local_lr);
252 }
253
254 process_uses (df_get_artificial_uses (bb_index), 0);
255 process_defs (df_get_artificial_defs (bb_index), 0);
256
257 return NULL;
258}
259
260/* Pop the definitions created in this basic block when leaving its
261 dominated parts. */
262
263void
264single_def_use_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
265{
266 df_ref saved_def;
267 while ((saved_def = reg_defs_stack.pop ()) != NULL)
268 {
269 unsigned int dregno = DF_REF_REGNO (saved_def);
270
271 /* See also process_defs. */
272 if (saved_def == reg_defs[dregno])
273 reg_defs[dregno] = NULL;
274 else
275 reg_defs[dregno] = saved_def;
276 }
277}
278
279
280/* Build a vector holding the reaching definitions of uses reached by a
281 single dominating definition. */
282
283static void
284build_single_def_use_links (void)
285{
286 /* We use the multiple definitions problem to compute our restricted
287 use-def chains. */
288 df_set_flags (DF_EQ_NOTES);
289 df_md_add_problem ();
290 df_note_add_problem ();
291 df_analyze ();
292 df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
293
294 use_def_ref.create (DF_USES_TABLE_SIZE ());
295 use_def_ref.safe_grow_cleared (DF_USES_TABLE_SIZE ());
296
297 reg_defs.create (max_reg_num ());
298 reg_defs.safe_grow_cleared (max_reg_num ());
299
300 reg_defs_stack.create (n_basic_blocks_for_fn (cfun) * 10);
301 local_md = BITMAP_ALLOC (NULL);
302 local_lr = BITMAP_ALLOC (NULL);
303
304 /* Walk the dominator tree looking for single reaching definitions
305 dominating the uses. This is similar to how SSA form is built. */
306 single_def_use_dom_walker (CDI_DOMINATORS)
307 .walk (cfun->cfg->x_entry_block_ptr);
308
309 BITMAP_FREE (local_lr);
310 BITMAP_FREE (local_md);
311 reg_defs.release ();
312 reg_defs_stack.release ();
313}
314
315
316/* Do not try to replace constant addresses or addresses of local and
317 argument slots. These MEM expressions are made only once and inserted
318 in many instructions, as well as being used to control symbol table
319 output. It is not safe to clobber them.
320
321 There are some uncommon cases where the address is already in a register
322 for some reason, but we cannot take advantage of that because we have
323 no easy way to unshare the MEM. In addition, looking up all stack
324 addresses is costly. */
325
326static bool
327can_simplify_addr (rtx addr)
328{
329 rtx reg;
330
331 if (CONSTANT_ADDRESS_P (addr))
332 return false;
333
334 if (GET_CODE (addr) == PLUS)
335 reg = XEXP (addr, 0);
336 else
337 reg = addr;
338
339 return (!REG_P (reg)
340 || (REGNO (reg) != FRAME_POINTER_REGNUM
341 && REGNO (reg) != HARD_FRAME_POINTER_REGNUM
342 && REGNO (reg) != ARG_POINTER_REGNUM));
343}
344
345/* Returns a canonical version of X for the address, from the point of view,
346 that all multiplications are represented as MULT instead of the multiply
347 by a power of 2 being represented as ASHIFT.
348
349 Every ASHIFT we find has been made by simplify_gen_binary and was not
350 there before, so it is not shared. So we can do this in place. */
351
352static void
353canonicalize_address (rtx x)
354{
355 for (;;)
356 switch (GET_CODE (x))
357 {
358 case ASHIFT:
359 if (CONST_INT_P (XEXP (x, 1))
360 && INTVAL (XEXP (x, 1)) < GET_MODE_UNIT_BITSIZE (GET_MODE (x))
361 && INTVAL (XEXP (x, 1)) >= 0)
362 {
363 HOST_WIDE_INT shift = INTVAL (XEXP (x, 1));
364 PUT_CODE (x, MULT);
365 XEXP (x, 1) = gen_int_mode (HOST_WIDE_INT_1 << shift,
366 GET_MODE (x));
367 }
368
369 x = XEXP (x, 0);
370 break;
371
372 case PLUS:
373 if (GET_CODE (XEXP (x, 0)) == PLUS
374 || GET_CODE (XEXP (x, 0)) == ASHIFT
375 || GET_CODE (XEXP (x, 0)) == CONST)
376 canonicalize_address (XEXP (x, 0));
377
378 x = XEXP (x, 1);
379 break;
380
381 case CONST:
382 x = XEXP (x, 0);
383 break;
384
385 default:
386 return;
387 }
388}
389
390/* OLD is a memory address. Return whether it is good to use NEW instead,
391 for a memory access in the given MODE. */
392
393static bool
394should_replace_address (rtx old_rtx, rtx new_rtx, machine_mode mode,
395 addr_space_t as, bool speed)
396{
397 int gain;
398
399 if (rtx_equal_p (old_rtx, new_rtx)
400 || !memory_address_addr_space_p (mode, new_rtx, as))
401 return false;
402
403 /* Copy propagation is always ok. */
404 if (REG_P (old_rtx) && REG_P (new_rtx))
405 return true;
406
407 /* Prefer the new address if it is less expensive. */
408 gain = (address_cost (old_rtx, mode, as, speed)
409 - address_cost (new_rtx, mode, as, speed));
410
411 /* If the addresses have equivalent cost, prefer the new address
412 if it has the highest `set_src_cost'. That has the potential of
413 eliminating the most insns without additional costs, and it
414 is the same that cse.c used to do. */
415 if (gain == 0)
416 gain = (set_src_cost (new_rtx, VOIDmode, speed)
417 - set_src_cost (old_rtx, VOIDmode, speed));
418
419 return (gain > 0);
420}
421
422
423/* Flags for the last parameter of propagate_rtx_1. */
424
425enum {
426 /* If PR_CAN_APPEAR is true, propagate_rtx_1 always returns true;
427 if it is false, propagate_rtx_1 returns false if, for at least
428 one occurrence OLD, it failed to collapse the result to a constant.
429 For example, (mult:M (reg:M A) (minus:M (reg:M B) (reg:M A))) may
430 collapse to zero if replacing (reg:M B) with (reg:M A).
431
432 PR_CAN_APPEAR is disregarded inside MEMs: in that case,
433 propagate_rtx_1 just tries to make cheaper and valid memory
434 addresses. */
435 PR_CAN_APPEAR = 1,
436
437 /* If PR_HANDLE_MEM is not set, propagate_rtx_1 won't attempt any replacement
438 outside memory addresses. This is needed because propagate_rtx_1 does
439 not do any analysis on memory; thus it is very conservative and in general
440 it will fail if non-read-only MEMs are found in the source expression.
441
442 PR_HANDLE_MEM is set when the source of the propagation was not
443 another MEM. Then, it is safe not to treat non-read-only MEMs as
444 ``opaque'' objects. */
445 PR_HANDLE_MEM = 2,
446
447 /* Set when costs should be optimized for speed. */
448 PR_OPTIMIZE_FOR_SPEED = 4
449};
450
451
452/* Replace all occurrences of OLD in *PX with NEW and try to simplify the
453 resulting expression. Replace *PX with a new RTL expression if an
454 occurrence of OLD was found.
455
456 This is only a wrapper around simplify-rtx.c: do not add any pattern
457 matching code here. (The sole exception is the handling of LO_SUM, but
458 that is because there is no simplify_gen_* function for LO_SUM). */
459
460static bool
461propagate_rtx_1 (rtx *px, rtx old_rtx, rtx new_rtx, int flags)
462{
463 rtx x = *px, tem = NULL_RTX, op0, op1, op2;
464 enum rtx_code code = GET_CODE (x);
465 machine_mode mode = GET_MODE (x);
466 machine_mode op_mode;
467 bool can_appear = (flags & PR_CAN_APPEAR) != 0;
468 bool valid_ops = true;
469
470 if (!(flags & PR_HANDLE_MEM) && MEM_P (x) && !MEM_READONLY_P (x))
471 {
472 /* If unsafe, change MEMs to CLOBBERs or SCRATCHes (to preserve whether
473 they have side effects or not). */
474 *px = (side_effects_p (x)
475 ? gen_rtx_CLOBBER (GET_MODE (x), const0_rtx)
476 : gen_rtx_SCRATCH (GET_MODE (x)));
477 return false;
478 }
479
480 /* If X is OLD_RTX, return NEW_RTX. But not if replacing only within an
481 address, and we are *not* inside one. */
482 if (x == old_rtx)
483 {
484 *px = new_rtx;
485 return can_appear;
486 }
487
488 /* If this is an expression, try recursive substitution. */
489 switch (GET_RTX_CLASS (code))
490 {
491 case RTX_UNARY:
492 op0 = XEXP (x, 0);
493 op_mode = GET_MODE (op0);
494 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
495 if (op0 == XEXP (x, 0))
496 return true;
497 tem = simplify_gen_unary (code, mode, op0, op_mode);
498 break;
499
500 case RTX_BIN_ARITH:
501 case RTX_COMM_ARITH:
502 op0 = XEXP (x, 0);
503 op1 = XEXP (x, 1);
504 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
505 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
506 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
507 return true;
508 tem = simplify_gen_binary (code, mode, op0, op1);
509 break;
510
511 case RTX_COMPARE:
512 case RTX_COMM_COMPARE:
513 op0 = XEXP (x, 0);
514 op1 = XEXP (x, 1);
515 op_mode = GET_MODE (op0) != VOIDmode ? GET_MODE (op0) : GET_MODE (op1);
516 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
517 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
518 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
519 return true;
520 tem = simplify_gen_relational (code, mode, op_mode, op0, op1);
521 break;
522
523 case RTX_TERNARY:
524 case RTX_BITFIELD_OPS:
525 op0 = XEXP (x, 0);
526 op1 = XEXP (x, 1);
527 op2 = XEXP (x, 2);
528 op_mode = GET_MODE (op0);
529 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
530 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
531 valid_ops &= propagate_rtx_1 (&op2, old_rtx, new_rtx, flags);
532 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1) && op2 == XEXP (x, 2))
533 return true;
534 if (op_mode == VOIDmode)
535 op_mode = GET_MODE (op0);
536 tem = simplify_gen_ternary (code, mode, op_mode, op0, op1, op2);
537 break;
538
539 case RTX_EXTRA:
540 /* The only case we try to handle is a SUBREG. */
541 if (code == SUBREG)
542 {
543 op0 = XEXP (x, 0);
544 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
545 if (op0 == XEXP (x, 0))
546 return true;
547 tem = simplify_gen_subreg (mode, op0, GET_MODE (SUBREG_REG (x)),
548 SUBREG_BYTE (x));
549 }
550 break;
551
552 case RTX_OBJ:
553 if (code == MEM && x != new_rtx)
554 {
555 rtx new_op0;
556 op0 = XEXP (x, 0);
557
558 /* There are some addresses that we cannot work on. */
559 if (!can_simplify_addr (op0))
560 return true;
561
562 op0 = new_op0 = targetm.delegitimize_address (op0);
563 valid_ops &= propagate_rtx_1 (&new_op0, old_rtx, new_rtx,
564 flags | PR_CAN_APPEAR);
565
566 /* Dismiss transformation that we do not want to carry on. */
567 if (!valid_ops
568 || new_op0 == op0
569 || !(GET_MODE (new_op0) == GET_MODE (op0)
570 || GET_MODE (new_op0) == VOIDmode))
571 return true;
572
573 canonicalize_address (new_op0);
574
575 /* Copy propagations are always ok. Otherwise check the costs. */
576 if (!(REG_P (old_rtx) && REG_P (new_rtx))
577 && !should_replace_address (op0, new_op0, GET_MODE (x),
578 MEM_ADDR_SPACE (x),
579 flags & PR_OPTIMIZE_FOR_SPEED))
580 return true;
581
582 tem = replace_equiv_address_nv (x, new_op0);
583 }
584
585 else if (code == LO_SUM)
586 {
587 op0 = XEXP (x, 0);
588 op1 = XEXP (x, 1);
589
590 /* The only simplification we do attempts to remove references to op0
591 or make it constant -- in both cases, op0's invalidity will not
592 make the result invalid. */
593 propagate_rtx_1 (&op0, old_rtx, new_rtx, flags | PR_CAN_APPEAR);
594 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
595 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
596 return true;
597
598 /* (lo_sum (high x) x) -> x */
599 if (GET_CODE (op0) == HIGH && rtx_equal_p (XEXP (op0, 0), op1))
600 tem = op1;
601 else
602 tem = gen_rtx_LO_SUM (mode, op0, op1);
603
604 /* OP1 is likely not a legitimate address, otherwise there would have
605 been no LO_SUM. We want it to disappear if it is invalid, return
606 false in that case. */
607 return memory_address_p (mode, tem);
608 }
609
610 else if (code == REG)
611 {
612 if (rtx_equal_p (x, old_rtx))
613 {
614 *px = new_rtx;
615 return can_appear;
616 }
617 }
618 break;
619
620 default:
621 break;
622 }
623
624 /* No change, no trouble. */
625 if (tem == NULL_RTX)
626 return true;
627
628 *px = tem;
629
630 /* Allow replacements that simplify operations on a vector or complex
631 value to a component. The most prominent case is
632 (subreg ([vec_]concat ...)). */
633 if (REG_P (tem) && !HARD_REGISTER_P (tem)
634 && (VECTOR_MODE_P (GET_MODE (new_rtx))
635 || COMPLEX_MODE_P (GET_MODE (new_rtx)))
636 && GET_MODE (tem) == GET_MODE_INNER (GET_MODE (new_rtx)))
637 return true;
638
639 /* The replacement we made so far is valid, if all of the recursive
640 replacements were valid, or we could simplify everything to
641 a constant. */
642 return valid_ops || can_appear || CONSTANT_P (tem);
643}
644
645
646/* Return true if X constains a non-constant mem. */
647
648static bool
649varying_mem_p (const_rtx x)
650{
651 subrtx_iterator::array_type array;
652 FOR_EACH_SUBRTX (iter, array, x, NONCONST)
653 if (MEM_P (*iter) && !MEM_READONLY_P (*iter))
654 return true;
655 return false;
656}
657
658
659/* Replace all occurrences of OLD in X with NEW and try to simplify the
660 resulting expression (in mode MODE). Return a new expression if it is
661 a constant, otherwise X.
662
663 Simplifications where occurrences of NEW collapse to a constant are always
664 accepted. All simplifications are accepted if NEW is a pseudo too.
665 Otherwise, we accept simplifications that have a lower or equal cost. */
666
667static rtx
668propagate_rtx (rtx x, machine_mode mode, rtx old_rtx, rtx new_rtx,
669 bool speed)
670{
671 rtx tem;
672 bool collapsed;
673 int flags;
674
675 if (REG_P (new_rtx) && REGNO (new_rtx) < FIRST_PSEUDO_REGISTER)
676 return NULL_RTX;
677
678 flags = 0;
679 if (REG_P (new_rtx)
680 || CONSTANT_P (new_rtx)
681 || (GET_CODE (new_rtx) == SUBREG
682 && REG_P (SUBREG_REG (new_rtx))
683 && !paradoxical_subreg_p (mode, GET_MODE (SUBREG_REG (new_rtx)))))
684 flags |= PR_CAN_APPEAR;
685 if (!varying_mem_p (new_rtx))
686 flags |= PR_HANDLE_MEM;
687
688 if (speed)
689 flags |= PR_OPTIMIZE_FOR_SPEED;
690
691 tem = x;
692 collapsed = propagate_rtx_1 (&tem, old_rtx, copy_rtx (new_rtx), flags);
693 if (tem == x || !collapsed)
694 return NULL_RTX;
695
696 /* gen_lowpart_common will not be able to process VOIDmode entities other
697 than CONST_INTs. */
698 if (GET_MODE (tem) == VOIDmode && !CONST_INT_P (tem))
699 return NULL_RTX;
700
701 if (GET_MODE (tem) == VOIDmode)
702 tem = rtl_hooks.gen_lowpart_no_emit (mode, tem);
703 else
704 gcc_assert (GET_MODE (tem) == mode);
705
706 return tem;
707}
708
709
710
711
712/* Return true if the register from reference REF is killed
713 between FROM to (but not including) TO. */
714
715static bool
716local_ref_killed_between_p (df_ref ref, rtx_insn *from, rtx_insn *to)
717{
718 rtx_insn *insn;
719
720 for (insn = from; insn != to; insn = NEXT_INSN (insn))
721 {
722 df_ref def;
723 if (!INSN_P (insn))
724 continue;
725
726 FOR_EACH_INSN_DEF (def, insn)
727 if (DF_REF_REGNO (ref) == DF_REF_REGNO (def))
728 return true;
729 }
730 return false;
731}
732
733
734/* Check if the given DEF is available in INSN. This would require full
735 computation of available expressions; we check only restricted conditions:
736 - if DEF is the sole definition of its register, go ahead;
737 - in the same basic block, we check for no definitions killing the
738 definition of DEF_INSN;
739 - if USE's basic block has DEF's basic block as the sole predecessor,
740 we check if the definition is killed after DEF_INSN or before
741 TARGET_INSN insn, in their respective basic blocks. */
742static bool
743use_killed_between (df_ref use, rtx_insn *def_insn, rtx_insn *target_insn)
744{
745 basic_block def_bb = BLOCK_FOR_INSN (def_insn);
746 basic_block target_bb = BLOCK_FOR_INSN (target_insn);
747 int regno;
748 df_ref def;
749
750 /* We used to have a def reaching a use that is _before_ the def,
751 with the def not dominating the use even though the use and def
752 are in the same basic block, when a register may be used
753 uninitialized in a loop. This should not happen anymore since
754 we do not use reaching definitions, but still we test for such
755 cases and assume that DEF is not available. */
756 if (def_bb == target_bb
757 ? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn)
758 : !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb))
759 return true;
760
761 /* Check if the reg in USE has only one definition. We already
762 know that this definition reaches use, or we wouldn't be here.
763 However, this is invalid for hard registers because if they are
764 live at the beginning of the function it does not mean that we
765 have an uninitialized access. */
766 regno = DF_REF_REGNO (use);
767 def = DF_REG_DEF_CHAIN (regno);
768 if (def
769 && DF_REF_NEXT_REG (def) == NULL
770 && regno >= FIRST_PSEUDO_REGISTER)
771 return false;
772
773 /* Check locally if we are in the same basic block. */
774 if (def_bb == target_bb)
775 return local_ref_killed_between_p (use, def_insn, target_insn);
776
777 /* Finally, if DEF_BB is the sole predecessor of TARGET_BB. */
778 if (single_pred_p (target_bb)
779 && single_pred (target_bb) == def_bb)
780 {
781 df_ref x;
782
783 /* See if USE is killed between DEF_INSN and the last insn in the
784 basic block containing DEF_INSN. */
785 x = df_bb_regno_last_def_find (def_bb, regno);
786 if (x && DF_INSN_LUID (DF_REF_INSN (x)) >= DF_INSN_LUID (def_insn))
787 return true;
788
789 /* See if USE is killed between TARGET_INSN and the first insn in the
790 basic block containing TARGET_INSN. */
791 x = df_bb_regno_first_def_find (target_bb, regno);
792 if (x && DF_INSN_LUID (DF_REF_INSN (x)) < DF_INSN_LUID (target_insn))
793 return true;
794
795 return false;
796 }
797
798 /* Otherwise assume the worst case. */
799 return true;
800}
801
802
803/* Check if all uses in DEF_INSN can be used in TARGET_INSN. This
804 would require full computation of available expressions;
805 we check only restricted conditions, see use_killed_between. */
806static bool
807all_uses_available_at (rtx_insn *def_insn, rtx_insn *target_insn)
808{
809 df_ref use;
810 struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
811 rtx def_set = single_set (def_insn);
812 rtx_insn *next;
813
814 gcc_assert (def_set);
815
816 /* If target_insn comes right after def_insn, which is very common
817 for addresses, we can use a quicker test. Ignore debug insns
818 other than target insns for this. */
819 next = NEXT_INSN (def_insn);
820 while (next && next != target_insn && DEBUG_INSN_P (next))
821 next = NEXT_INSN (next);
822 if (next == target_insn && REG_P (SET_DEST (def_set)))
823 {
824 rtx def_reg = SET_DEST (def_set);
825
826 /* If the insn uses the reg that it defines, the substitution is
827 invalid. */
828 FOR_EACH_INSN_INFO_USE (use, insn_info)
829 if (rtx_equal_p (DF_REF_REG (use), def_reg))
830 return false;
831 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
832 if (rtx_equal_p (DF_REF_REG (use), def_reg))
833 return false;
834 }
835 else
836 {
837 rtx def_reg = REG_P (SET_DEST (def_set)) ? SET_DEST (def_set) : NULL_RTX;
838
839 /* Look at all the uses of DEF_INSN, and see if they are not
840 killed between DEF_INSN and TARGET_INSN. */
841 FOR_EACH_INSN_INFO_USE (use, insn_info)
842 {
843 if (def_reg && rtx_equal_p (DF_REF_REG (use), def_reg))
844 return false;
845 if (use_killed_between (use, def_insn, target_insn))
846 return false;
847 }
848 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
849 {
850 if (def_reg && rtx_equal_p (DF_REF_REG (use), def_reg))
851 return false;
852 if (use_killed_between (use, def_insn, target_insn))
853 return false;
854 }
855 }
856
857 return true;
858}
859
860
861static df_ref *active_defs;
862static sparseset active_defs_check;
863
864/* Fill the ACTIVE_DEFS array with the use->def link for the registers
865 mentioned in USE_REC. Register the valid entries in ACTIVE_DEFS_CHECK
866 too, for checking purposes. */
867
868static void
869register_active_defs (df_ref use)
870{
871 for (; use; use = DF_REF_NEXT_LOC (use))
872 {
873 df_ref def = get_def_for_use (use);
874 int regno = DF_REF_REGNO (use);
875
876 if (flag_checking)
877 sparseset_set_bit (active_defs_check, regno);
878 active_defs[regno] = def;
879 }
880}
881
882
883/* Build the use->def links that we use to update the dataflow info
884 for new uses. Note that building the links is very cheap and if
885 it were done earlier, they could be used to rule out invalid
886 propagations (in addition to what is done in all_uses_available_at).
887 I'm not doing this yet, though. */
888
889static void
890update_df_init (rtx_insn *def_insn, rtx_insn *insn)
891{
892 if (flag_checking)
893 sparseset_clear (active_defs_check);
894 register_active_defs (DF_INSN_USES (def_insn));
895 register_active_defs (DF_INSN_USES (insn));
896 register_active_defs (DF_INSN_EQ_USES (insn));
897}
898
899
900/* Update the USE_DEF_REF array for the given use, using the active definitions
901 in the ACTIVE_DEFS array to match pseudos to their def. */
902
903static inline void
904update_uses (df_ref use)
905{
906 for (; use; use = DF_REF_NEXT_LOC (use))
907 {
908 int regno = DF_REF_REGNO (use);
909
910 /* Set up the use-def chain. */
911 if (DF_REF_ID (use) >= (int) use_def_ref.length ())
912 use_def_ref.safe_grow_cleared (DF_REF_ID (use) + 1);
913
914 if (flag_checking)
915 gcc_assert (sparseset_bit_p (active_defs_check, regno));
916 use_def_ref[DF_REF_ID (use)] = active_defs[regno];
917 }
918}
919
920
921/* Update the USE_DEF_REF array for the uses in INSN. Only update note
922 uses if NOTES_ONLY is true. */
923
924static void
925update_df (rtx_insn *insn, rtx note)
926{
927 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
928
929 if (note)
930 {
931 df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE);
932 df_notes_rescan (insn);
933 }
934 else
935 {
936 df_uses_create (&PATTERN (insn), insn, 0);
937 df_insn_rescan (insn);
938 update_uses (DF_INSN_INFO_USES (insn_info));
939 }
940
941 update_uses (DF_INSN_INFO_EQ_USES (insn_info));
942}
943
944
945/* Try substituting NEW into LOC, which originated from forward propagation
946 of USE's value from DEF_INSN. SET_REG_EQUAL says whether we are
947 substituting the whole SET_SRC, so we can set a REG_EQUAL note if the
948 new insn is not recognized. Return whether the substitution was
949 performed. */
950
951static bool
952try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx_insn *def_insn,
953 bool set_reg_equal)
954{
955 rtx_insn *insn = DF_REF_INSN (use);
956 rtx set = single_set (insn);
957 rtx note = NULL_RTX;
958 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
959 int old_cost = 0;
960 bool ok;
961
962 update_df_init (def_insn, insn);
963
964 /* forward_propagate_subreg may be operating on an instruction with
965 multiple sets. If so, assume the cost of the new instruction is
966 not greater than the old one. */
967 if (set)
968 old_cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)), speed);
969 if (dump_file)
970 {
971 fprintf (dump_file, "\nIn insn %d, replacing\n ", INSN_UID (insn));
972 print_inline_rtx (dump_file, *loc, 2);
973 fprintf (dump_file, "\n with ");
974 print_inline_rtx (dump_file, new_rtx, 2);
975 fprintf (dump_file, "\n");
976 }
977
978 validate_unshare_change (insn, loc, new_rtx, true);
979 if (!verify_changes (0))
980 {
981 if (dump_file)
982 fprintf (dump_file, "Changes to insn %d not recognized\n",
983 INSN_UID (insn));
984 ok = false;
985 }
986
987 else if (DF_REF_TYPE (use) == DF_REF_REG_USE
988 && set
989 && (set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)), speed)
990 > old_cost))
991 {
992 if (dump_file)
993 fprintf (dump_file, "Changes to insn %d not profitable\n",
994 INSN_UID (insn));
995 ok = false;
996 }
997
998 else
999 {
1000 if (dump_file)
1001 fprintf (dump_file, "Changed insn %d\n", INSN_UID (insn));
1002 ok = true;
1003 }
1004
1005 if (ok)
1006 {
1007 confirm_change_group ();
1008 num_changes++;
1009 }
1010 else
1011 {
1012 cancel_changes (0);
1013
1014 /* Can also record a simplified value in a REG_EQUAL note,
1015 making a new one if one does not already exist. */
1016 if (set_reg_equal)
1017 {
1018 /* If there are any paradoxical SUBREGs, don't add REG_EQUAL note,
1019 because the bits in there can be anything and so might not
1020 match the REG_EQUAL note content. See PR70574. */
1021 subrtx_var_iterator::array_type array;
1022 FOR_EACH_SUBRTX_VAR (iter, array, *loc, NONCONST)
1023 {
1024 rtx x = *iter;
1025 if (SUBREG_P (x) && paradoxical_subreg_p (x))
1026 {
1027 set_reg_equal = false;
1028 break;
1029 }
1030 }
1031
1032 if (set_reg_equal)
1033 {
1034 if (dump_file)
1035 fprintf (dump_file, " Setting REG_EQUAL note\n");
1036
1037 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
1038 }
1039 }
1040 }
1041
1042 if ((ok || note) && !CONSTANT_P (new_rtx))
1043 update_df (insn, note);
1044
1045 return ok;
1046}
1047
1048/* For the given single_set INSN, containing SRC known to be a
1049 ZERO_EXTEND or SIGN_EXTEND of a register, return true if INSN
1050 is redundant due to the register being set by a LOAD_EXTEND_OP
1051 load from memory. */
1052
1053static bool
1054free_load_extend (rtx src, rtx_insn *insn)
1055{
1056 rtx reg;
1057 df_ref def, use;
1058
1059 reg = XEXP (src, 0);
1060 if (load_extend_op (GET_MODE (reg)) != GET_CODE (src))
1061 return false;
1062
1063 FOR_EACH_INSN_USE (use, insn)
1064 if (!DF_REF_IS_ARTIFICIAL (use)
1065 && DF_REF_TYPE (use) == DF_REF_REG_USE
1066 && DF_REF_REG (use) == reg)
1067 break;
1068 if (!use)
1069 return false;
1070
1071 def = get_def_for_use (use);
1072 if (!def)
1073 return false;
1074
1075 if (DF_REF_IS_ARTIFICIAL (def))
1076 return false;
1077
1078 if (NONJUMP_INSN_P (DF_REF_INSN (def)))
1079 {
1080 rtx patt = PATTERN (DF_REF_INSN (def));
1081
1082 if (GET_CODE (patt) == SET
1083 && GET_CODE (SET_SRC (patt)) == MEM
1084 && rtx_equal_p (SET_DEST (patt), reg))
1085 return true;
1086 }
1087 return false;
1088}
1089
1090/* If USE is a subreg, see if it can be replaced by a pseudo. */
1091
1092static bool
1093forward_propagate_subreg (df_ref use, rtx_insn *def_insn, rtx def_set)
1094{
1095 rtx use_reg = DF_REF_REG (use);
1096 rtx_insn *use_insn;
1097 rtx src;
1098 scalar_int_mode int_use_mode, src_mode;
1099
1100 /* Only consider subregs... */
1101 machine_mode use_mode = GET_MODE (use_reg);
1102 if (GET_CODE (use_reg) != SUBREG
1103 || !REG_P (SET_DEST (def_set)))
1104 return false;
1105
1106 if (paradoxical_subreg_p (use_reg))
1107 {
1108 /* If this is a paradoxical SUBREG, we have no idea what value the
1109 extra bits would have. However, if the operand is equivalent to
1110 a SUBREG whose operand is the same as our mode, and all the modes
1111 are within a word, we can just use the inner operand because
1112 these SUBREGs just say how to treat the register. */
1113 use_insn = DF_REF_INSN (use);
1114 src = SET_SRC (def_set);
1115 if (GET_CODE (src) == SUBREG
1116 && REG_P (SUBREG_REG (src))
1117 && REGNO (SUBREG_REG (src)) >= FIRST_PSEUDO_REGISTER
1118 && GET_MODE (SUBREG_REG (src)) == use_mode
1119 && subreg_lowpart_p (src)
1120 && all_uses_available_at (def_insn, use_insn))
1121 return try_fwprop_subst (use, DF_REF_LOC (use), SUBREG_REG (src),
1122 def_insn, false);
1123 }
1124
1125 /* If this is a SUBREG of a ZERO_EXTEND or SIGN_EXTEND, and the SUBREG
1126 is the low part of the reg being extended then just use the inner
1127 operand. Don't do this if the ZERO_EXTEND or SIGN_EXTEND insn will
1128 be removed due to it matching a LOAD_EXTEND_OP load from memory,
1129 or due to the operation being a no-op when applied to registers.
1130 For example, if we have:
1131
1132 A: (set (reg:DI X) (sign_extend:DI (reg:SI Y)))
1133 B: (... (subreg:SI (reg:DI X)) ...)
1134
1135 and mode_rep_extended says that Y is already sign-extended,
1136 the backend will typically allow A to be combined with the
1137 definition of Y or, failing that, allow A to be deleted after
1138 reload through register tying. Introducing more uses of Y
1139 prevents both optimisations. */
1140 else if (is_a <scalar_int_mode> (use_mode, &int_use_mode)
1141 && subreg_lowpart_p (use_reg))
1142 {
1143 use_insn = DF_REF_INSN (use);
1144 src = SET_SRC (def_set);
1145 if ((GET_CODE (src) == ZERO_EXTEND
1146 || GET_CODE (src) == SIGN_EXTEND)
1147 && is_a <scalar_int_mode> (GET_MODE (src), &src_mode)
1148 && REG_P (XEXP (src, 0))
1149 && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER
1150 && GET_MODE (XEXP (src, 0)) == use_mode
1151 && !free_load_extend (src, def_insn)
1152 && (targetm.mode_rep_extended (int_use_mode, src_mode)
1153 != (int) GET_CODE (src))
1154 && all_uses_available_at (def_insn, use_insn))
1155 return try_fwprop_subst (use, DF_REF_LOC (use), XEXP (src, 0),
1156 def_insn, false);
1157 }
1158
1159 return false;
1160}
1161
1162/* Try to replace USE with SRC (defined in DEF_INSN) in __asm. */
1163
1164static bool
1165forward_propagate_asm (df_ref use, rtx_insn *def_insn, rtx def_set, rtx reg)
1166{
1167 rtx_insn *use_insn = DF_REF_INSN (use);
1168 rtx src, use_pat, asm_operands, new_rtx, *loc;
1169 int speed_p, i;
1170 df_ref uses;
1171
1172 gcc_assert ((DF_REF_FLAGS (use) & DF_REF_IN_NOTE) == 0);
1173
1174 src = SET_SRC (def_set);
1175 use_pat = PATTERN (use_insn);
1176
1177 /* In __asm don't replace if src might need more registers than
1178 reg, as that could increase register pressure on the __asm. */
1179 uses = DF_INSN_USES (def_insn);
1180 if (uses && DF_REF_NEXT_LOC (uses))
1181 return false;
1182
1183 update_df_init (def_insn, use_insn);
1184 speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
1185 asm_operands = NULL_RTX;
1186 switch (GET_CODE (use_pat))
1187 {
1188 case ASM_OPERANDS:
1189 asm_operands = use_pat;
1190 break;
1191 case SET:
1192 if (MEM_P (SET_DEST (use_pat)))
1193 {
1194 loc = &SET_DEST (use_pat);
1195 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1196 if (new_rtx)
1197 validate_unshare_change (use_insn, loc, new_rtx, true);
1198 }
1199 asm_operands = SET_SRC (use_pat);
1200 break;
1201 case PARALLEL:
1202 for (i = 0; i < XVECLEN (use_pat, 0); i++)
1203 if (GET_CODE (XVECEXP (use_pat, 0, i)) == SET)
1204 {
1205 if (MEM_P (SET_DEST (XVECEXP (use_pat, 0, i))))
1206 {
1207 loc = &SET_DEST (XVECEXP (use_pat, 0, i));
1208 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg,
1209 src, speed_p);
1210 if (new_rtx)
1211 validate_unshare_change (use_insn, loc, new_rtx, true);
1212 }
1213 asm_operands = SET_SRC (XVECEXP (use_pat, 0, i));
1214 }
1215 else if (GET_CODE (XVECEXP (use_pat, 0, i)) == ASM_OPERANDS)
1216 asm_operands = XVECEXP (use_pat, 0, i);
1217 break;
1218 default:
1219 gcc_unreachable ();
1220 }
1221
1222 gcc_assert (asm_operands && GET_CODE (asm_operands) == ASM_OPERANDS);
1223 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (asm_operands); i++)
1224 {
1225 loc = &ASM_OPERANDS_INPUT (asm_operands, i);
1226 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
1227 if (new_rtx)
1228 validate_unshare_change (use_insn, loc, new_rtx, true);
1229 }
1230
1231 if (num_changes_pending () == 0 || !apply_change_group ())
1232 return false;
1233
1234 update_df (use_insn, NULL);
1235 num_changes++;
1236 return true;
1237}
1238
1239/* Try to replace USE with SRC (defined in DEF_INSN) and simplify the
1240 result. */
1241
1242static bool
1243forward_propagate_and_simplify (df_ref use, rtx_insn *def_insn, rtx def_set)
1244{
1245 rtx_insn *use_insn = DF_REF_INSN (use);
1246 rtx use_set = single_set (use_insn);
1247 rtx src, reg, new_rtx, *loc;
1248 bool set_reg_equal;
1249 machine_mode mode;
1250 int asm_use = -1;
1251
1252 if (INSN_CODE (use_insn) < 0)
1253 asm_use = asm_noperands (PATTERN (use_insn));
1254
1255 if (!use_set && asm_use < 0 && !DEBUG_INSN_P (use_insn))
1256 return false;
1257
1258 /* Do not propagate into PC, CC0, etc. */
1259 if (use_set && GET_MODE (SET_DEST (use_set)) == VOIDmode)
1260 return false;
1261
1262 /* If def and use are subreg, check if they match. */
1263 reg = DF_REF_REG (use);
1264 if (GET_CODE (reg) == SUBREG && GET_CODE (SET_DEST (def_set)) == SUBREG)
1265 {
1266 if (SUBREG_BYTE (SET_DEST (def_set)) != SUBREG_BYTE (reg))
1267 return false;
1268 }
1269 /* Check if the def had a subreg, but the use has the whole reg. */
1270 else if (REG_P (reg) && GET_CODE (SET_DEST (def_set)) == SUBREG)
1271 return false;
1272 /* Check if the use has a subreg, but the def had the whole reg. Unlike the
1273 previous case, the optimization is possible and often useful indeed. */
1274 else if (GET_CODE (reg) == SUBREG && REG_P (SET_DEST (def_set)))
1275 reg = SUBREG_REG (reg);
1276
1277 /* Make sure that we can treat REG as having the same mode as the
1278 source of DEF_SET. */
1279 if (GET_MODE (SET_DEST (def_set)) != GET_MODE (reg))
1280 return false;
1281
1282 /* Check if the substitution is valid (last, because it's the most
1283 expensive check!). */
1284 src = SET_SRC (def_set);
1285 if (!CONSTANT_P (src) && !all_uses_available_at (def_insn, use_insn))
1286 return false;
1287
1288 /* Check if the def is loading something from the constant pool; in this
1289 case we would undo optimization such as compress_float_constant.
1290 Still, we can set a REG_EQUAL note. */
1291 if (MEM_P (src) && MEM_READONLY_P (src))
1292 {
1293 rtx x = avoid_constant_pool_reference (src);
1294 if (x != src && use_set)
1295 {
1296 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1297 rtx old_rtx = note ? XEXP (note, 0) : SET_SRC (use_set);
1298 rtx new_rtx = simplify_replace_rtx (old_rtx, src, x);
1299 if (old_rtx != new_rtx)
1300 set_unique_reg_note (use_insn, REG_EQUAL, copy_rtx (new_rtx));
1301 }
1302 return false;
1303 }
1304
1305 if (asm_use >= 0)
1306 return forward_propagate_asm (use, def_insn, def_set, reg);
1307
1308 /* Else try simplifying. */
1309
1310 if (DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE)
1311 {
1312 loc = &SET_DEST (use_set);
1313 set_reg_equal = false;
1314 }
1315 else if (!use_set)
1316 {
1317 loc = &INSN_VAR_LOCATION_LOC (use_insn);
1318 set_reg_equal = false;
1319 }
1320 else
1321 {
1322 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1323 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1324 loc = &XEXP (note, 0);
1325 else
1326 loc = &SET_SRC (use_set);
1327
1328 /* Do not replace an existing REG_EQUAL note if the insn is not
1329 recognized. Either we're already replacing in the note, or we'll
1330 separately try plugging the definition in the note and simplifying.
1331 And only install a REQ_EQUAL note when the destination is a REG
1332 that isn't mentioned in USE_SET, as the note would be invalid
1333 otherwise. We also don't want to install a note if we are merely
1334 propagating a pseudo since verifying that this pseudo isn't dead
1335 is a pain; moreover such a note won't help anything.
1336 If the use is a paradoxical subreg, make sure we don't add a
1337 REG_EQUAL note for it, because it is not equivalent, it is one
1338 possible value for it, but we can't rely on it holding that value.
1339 See PR70574. */
1340 set_reg_equal = (note == NULL_RTX
1341 && REG_P (SET_DEST (use_set))
1342 && !REG_P (src)
1343 && !(GET_CODE (src) == SUBREG
1344 && REG_P (SUBREG_REG (src)))
1345 && !reg_mentioned_p (SET_DEST (use_set),
1346 SET_SRC (use_set))
1347 && !paradoxical_subreg_p (DF_REF_REG (use)));
1348 }
1349
1350 if (GET_MODE (*loc) == VOIDmode)
1351 mode = GET_MODE (SET_DEST (use_set));
1352 else
1353 mode = GET_MODE (*loc);
1354
1355 new_rtx = propagate_rtx (*loc, mode, reg, src,
1356 optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn)));
1357
1358 if (!new_rtx)
1359 return false;
1360
1361 return try_fwprop_subst (use, loc, new_rtx, def_insn, set_reg_equal);
1362}
1363
1364
1365/* Given a use USE of an insn, if it has a single reaching
1366 definition, try to forward propagate it into that insn.
1367 Return true if cfg cleanup will be needed. */
1368
1369static bool
1370forward_propagate_into (df_ref use)
1371{
1372 df_ref def;
1373 rtx_insn *def_insn, *use_insn;
1374 rtx def_set;
1375 rtx parent;
1376
1377 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
1378 return false;
1379 if (DF_REF_IS_ARTIFICIAL (use))
1380 return false;
1381
1382 /* Only consider uses that have a single definition. */
1383 def = get_def_for_use (use);
1384 if (!def)
1385 return false;
1386 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
1387 return false;
1388 if (DF_REF_IS_ARTIFICIAL (def))
1389 return false;
1390
1391 /* Do not propagate loop invariant definitions inside the loop. */
1392 if (DF_REF_BB (def)->loop_father != DF_REF_BB (use)->loop_father)
1393 return false;
1394
1395 /* Check if the use is still present in the insn! */
1396 use_insn = DF_REF_INSN (use);
1397 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
1398 parent = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
1399 else
1400 parent = PATTERN (use_insn);
1401
1402 if (!reg_mentioned_p (DF_REF_REG (use), parent))
1403 return false;
1404
1405 def_insn = DF_REF_INSN (def);
1406 if (multiple_sets (def_insn))
1407 return false;
1408 def_set = single_set (def_insn);
1409 if (!def_set)
1410 return false;
1411
1412 /* Only try one kind of propagation. If two are possible, we'll
1413 do it on the following iterations. */
1414 if (forward_propagate_and_simplify (use, def_insn, def_set)
1415 || forward_propagate_subreg (use, def_insn, def_set))
1416 {
1417 propagations_left--;
1418
1419 if (cfun->can_throw_non_call_exceptions
1420 && find_reg_note (use_insn, REG_EH_REGION, NULL_RTX)
1421 && purge_dead_edges (DF_REF_BB (use)))
1422 return true;
1423 }
1424 return false;
1425}
1426
1427
1428static void
1429fwprop_init (void)
1430{
1431 num_changes = 0;
1432 calculate_dominance_info (CDI_DOMINATORS);
1433
1434 /* We do not always want to propagate into loops, so we have to find
1435 loops and be careful about them. Avoid CFG modifications so that
1436 we don't have to update dominance information afterwards for
1437 build_single_def_use_links. */
1438 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
1439
1440 build_single_def_use_links ();
1441 df_set_flags (DF_DEFER_INSN_RESCAN);
1442
1443 active_defs = XNEWVEC (df_ref, max_reg_num ());
1444 if (flag_checking)
1445 active_defs_check = sparseset_alloc (max_reg_num ());
1446
1447 propagations_left = DF_USES_TABLE_SIZE ();
1448}
1449
1450static void
1451fwprop_done (void)
1452{
1453 loop_optimizer_finalize ();
1454
1455 use_def_ref.release ();
1456 free (active_defs);
1457 if (flag_checking)
1458 sparseset_free (active_defs_check);
1459
1460 free_dominance_info (CDI_DOMINATORS);
1461 cleanup_cfg (0);
1462 delete_trivially_dead_insns (get_insns (), max_reg_num ());
1463
1464 if (dump_file)
1465 fprintf (dump_file,
1466 "\nNumber of successful forward propagations: %d\n\n",
1467 num_changes);
1468}
1469
1470
1471/* Main entry point. */
1472
1473static bool
1474gate_fwprop (void)
1475{
1476 return optimize > 0 && flag_forward_propagate;
1477}
1478
1479static unsigned int
1480fwprop (void)
1481{
1482 unsigned i;
1483
1484 fwprop_init ();
1485
1486 /* Go through all the uses. df_uses_create will create new ones at the
1487 end, and we'll go through them as well.
1488
1489 Do not forward propagate addresses into loops until after unrolling.
1490 CSE did so because it was able to fix its own mess, but we are not. */
1491
1492 for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1493 {
1494 if (!propagations_left)
1495 break;
1496
1497 df_ref use = DF_USES_GET (i);
1498 if (use)
1499 if (DF_REF_TYPE (use) == DF_REF_REG_USE
1500 || DF_REF_BB (use)->loop_father == NULL
1501 /* The outer most loop is not really a loop. */
1502 || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
1503 forward_propagate_into (use);
1504 }
1505
1506 fwprop_done ();
1507 return 0;
1508}
1509
1510namespace {
1511
1512const pass_data pass_data_rtl_fwprop =
1513{
1514 RTL_PASS, /* type */
1515 "fwprop1", /* name */
1516 OPTGROUP_NONE, /* optinfo_flags */
1517 TV_FWPROP, /* tv_id */
1518 0, /* properties_required */
1519 0, /* properties_provided */
1520 0, /* properties_destroyed */
1521 0, /* todo_flags_start */
1522 TODO_df_finish, /* todo_flags_finish */
1523};
1524
1525class pass_rtl_fwprop : public rtl_opt_pass
1526{
1527public:
1528 pass_rtl_fwprop (gcc::context *ctxt)
1529 : rtl_opt_pass (pass_data_rtl_fwprop, ctxt)
1530 {}
1531
1532 /* opt_pass methods: */
1533 virtual bool gate (function *) { return gate_fwprop (); }
1534 virtual unsigned int execute (function *) { return fwprop (); }
1535
1536}; // class pass_rtl_fwprop
1537
1538} // anon namespace
1539
1540rtl_opt_pass *
1541make_pass_rtl_fwprop (gcc::context *ctxt)
1542{
1543 return new pass_rtl_fwprop (ctxt);
1544}
1545
1546static unsigned int
1547fwprop_addr (void)
1548{
1549 unsigned i;
1550
1551 fwprop_init ();
1552
1553 /* Go through all the uses. df_uses_create will create new ones at the
1554 end, and we'll go through them as well. */
1555 for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
1556 {
1557 if (!propagations_left)
1558 break;
1559
1560 df_ref use = DF_USES_GET (i);
1561 if (use)
1562 if (DF_REF_TYPE (use) != DF_REF_REG_USE
1563 && DF_REF_BB (use)->loop_father != NULL
1564 /* The outer most loop is not really a loop. */
1565 && loop_outer (DF_REF_BB (use)->loop_father) != NULL)
1566 forward_propagate_into (use);
1567 }
1568
1569 fwprop_done ();
1570 return 0;
1571}
1572
1573namespace {
1574
1575const pass_data pass_data_rtl_fwprop_addr =
1576{
1577 RTL_PASS, /* type */
1578 "fwprop2", /* name */
1579 OPTGROUP_NONE, /* optinfo_flags */
1580 TV_FWPROP, /* tv_id */
1581 0, /* properties_required */
1582 0, /* properties_provided */
1583 0, /* properties_destroyed */
1584 0, /* todo_flags_start */
1585 TODO_df_finish, /* todo_flags_finish */
1586};
1587
1588class pass_rtl_fwprop_addr : public rtl_opt_pass
1589{
1590public:
1591 pass_rtl_fwprop_addr (gcc::context *ctxt)
1592 : rtl_opt_pass (pass_data_rtl_fwprop_addr, ctxt)
1593 {}
1594
1595 /* opt_pass methods: */
1596 virtual bool gate (function *) { return gate_fwprop (); }
1597 virtual unsigned int execute (function *) { return fwprop_addr (); }
1598
1599}; // class pass_rtl_fwprop_addr
1600
1601} // anon namespace
1602
1603rtl_opt_pass *
1604make_pass_rtl_fwprop_addr (gcc::context *ctxt)
1605{
1606 return new pass_rtl_fwprop_addr (ctxt);
1607}
1608