1	/* Perform simple optimizations to clean up the result of reload.
2	Copyright (C) 1987-2023 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 under
7	the terms of the GNU General Public License as published by the Free
8	Software Foundation; either version 3, or (at your option) any later
9	version.
10
11	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12	WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14	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 "target.h"
25	#include "rtl.h"
26	#include "tree.h"
27	#include "predict.h"
28	#include "df.h"
29	#include "memmodel.h"
30	#include "tm_p.h"
31	#include "optabs.h"
32	#include "regs.h"
33	#include "emit-rtl.h"
34	#include "recog.h"
35
36	#include "cfgrtl.h"
37	#include "cfgbuild.h"
38	#include "cfgcleanup.h"
39	#include "reload.h"
40	#include "cselib.h"
41	#include "tree-pass.h"
42	#include "dbgcnt.h"
43	#include "function-abi.h"
44	#include "rtl-iter.h"
45
46	static bool reload_cse_simplify (rtx_insn *, rtx);
47	static void reload_cse_regs_1 (void);
48	static int reload_cse_simplify_set (rtx, rtx_insn *);
49	static int reload_cse_simplify_operands (rtx_insn *, rtx);
50
51	static void reload_combine (void);
52	static void reload_combine_note_use (rtx *, rtx_insn *, int, rtx);
53	static void reload_combine_note_store (rtx, const_rtx, void *);
54
55	static bool reload_cse_move2add (rtx_insn *);
56	static void move2add_note_store (rtx, const_rtx, void *);
57
58	/* Call cse / combine like post-reload optimization phases.
59	FIRST is the first instruction. */
60
61	static void
62	reload_cse_regs (rtx_insn *first ATTRIBUTE_UNUSED)
63	{
64	bool moves_converted;
65	reload_cse_regs_1 ();
66	reload_combine ();
67	moves_converted = reload_cse_move2add (first);
68	if (flag_expensive_optimizations)
69	{
70	if (moves_converted)
71	reload_combine ();
72	reload_cse_regs_1 ();
73	}
74	}
75
76	/* Try to simplify INSN. Return true if the CFG may have changed. */
77	static bool
78	reload_cse_simplify (rtx_insn *insn, rtx testreg)
79	{
80	rtx body = PATTERN (insn);
81	basic_block insn_bb = BLOCK_FOR_INSN (insn);
82	unsigned insn_bb_succs = EDGE_COUNT (insn_bb->succs);
83
84	/* If NO_FUNCTION_CSE has been set by the target, then we should not try
85	to cse function calls. */
86	if (NO_FUNCTION_CSE && CALL_P (insn))
87	return false;
88
89	/* Remember if this insn has been sp += const_int. */
90	rtx sp_set = set_for_reg_notes (insn);
91	rtx sp_addend = NULL_RTX;
92	if (sp_set
93	&& SET_DEST (sp_set) == stack_pointer_rtx
94	&& GET_CODE (SET_SRC (sp_set)) == PLUS
95	&& XEXP (SET_SRC (sp_set), 0) == stack_pointer_rtx
96	&& CONST_INT_P (XEXP (SET_SRC (sp_set), 1)))
97	sp_addend = XEXP (SET_SRC (sp_set), 1);
98
99	if (GET_CODE (body) == SET)
100	{
101	int count = 0;
102
103	/* Simplify even if we may think it is a no-op.
104	We may think a memory load of a value smaller than WORD_SIZE
105	is redundant because we haven't taken into account possible
106	implicit extension. reload_cse_simplify_set() will bring
107	this out, so it's safer to simplify before we delete. */
108	count += reload_cse_simplify_set (body, insn);
109
110	if (!count && cselib_redundant_set_p (body))
111	{
112	if (check_for_inc_dec (insn))
113	delete_insn_and_edges (insn);
114	/* We're done with this insn. */
115	goto done;
116	}
117
118	if (count > 0)
119	apply_change_group ();
120	else
121	reload_cse_simplify_operands (insn, testreg);
122	}
123	else if (GET_CODE (body) == PARALLEL)
124	{
125	int i;
126	int count = 0;
127	rtx value = NULL_RTX;
128
129	/* Registers mentioned in the clobber list for an asm cannot be reused
130	within the body of the asm. Invalidate those registers now so that
131	we don't try to substitute values for them. */
132	if (asm_noperands (body) >= 0)
133	{
134	for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
135	{
136	rtx part = XVECEXP (body, 0, i);
137	if (GET_CODE (part) == CLOBBER && REG_P (XEXP (part, 0)))
138	cselib_invalidate_rtx (XEXP (part, 0));
139	}
140	}
141
142	/* If every action in a PARALLEL is a noop, we can delete
143	the entire PARALLEL. */
144	for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
145	{
146	rtx part = XVECEXP (body, 0, i);
147	if (GET_CODE (part) == SET)
148	{
149	if (! cselib_redundant_set_p (part))
150	break;
151	if (REG_P (SET_DEST (part))
152	&& REG_FUNCTION_VALUE_P (SET_DEST (part)))
153	{
154	if (value)
155	break;
156	value = SET_DEST (part);
157	}
158	}
159	else if (GET_CODE (part) != CLOBBER && GET_CODE (part) != USE)
160	break;
161	}
162
163	if (i < 0)
164	{
165	if (check_for_inc_dec (insn))
166	delete_insn_and_edges (insn);
167	/* We're done with this insn. */
168	goto done;
169	}
170
171	/* It's not a no-op, but we can try to simplify it. */
172	for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
173	if (GET_CODE (XVECEXP (body, 0, i)) == SET)
174	count += reload_cse_simplify_set (XVECEXP (body, 0, i), insn);
175
176	if (count > 0)
177	apply_change_group ();
178	else
179	reload_cse_simplify_operands (insn, testreg);
180	}
181
182	/* If sp += const_int insn is changed into sp = reg;, add REG_EQUAL
183	note so that the stack_adjustments pass can undo it if beneficial. */
184	if (sp_addend
185	&& SET_DEST (sp_set) == stack_pointer_rtx
186	&& REG_P (SET_SRC (sp_set)))
187	set_dst_reg_note (insn, REG_EQUAL,
188	gen_rtx_PLUS (Pmode, stack_pointer_rtx,
189	sp_addend), stack_pointer_rtx);
190
191	done:
192	return (EDGE_COUNT (insn_bb->succs) != insn_bb_succs);
193	}
194
195	/* Do a very simple CSE pass over the hard registers.
196
197	This function detects no-op moves where we happened to assign two
198	different pseudo-registers to the same hard register, and then
199	copied one to the other. Reload will generate a useless
200	instruction copying a register to itself.
201
202	This function also detects cases where we load a value from memory
203	into two different registers, and (if memory is more expensive than
204	registers) changes it to simply copy the first register into the
205	second register.
206
207	Another optimization is performed that scans the operands of each
208	instruction to see whether the value is already available in a
209	hard register. It then replaces the operand with the hard register
210	if possible, much like an optional reload would. */
211
212	static void
213	reload_cse_regs_1 (void)
214	{
215	bool cfg_changed = false;
216	basic_block bb;
217	rtx_insn *insn;
218	rtx testreg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
219
220	cselib_init (CSELIB_RECORD_MEMORY);
221	init_alias_analysis ();
222
223	FOR_EACH_BB_FN (bb, cfun)
224	FOR_BB_INSNS (bb, insn)
225	{
226	if (INSN_P (insn))
227	cfg_changed |= reload_cse_simplify (insn, testreg);
228
229	cselib_process_insn (insn);
230	}
231
232	/* Clean up. */
233	end_alias_analysis ();
234	cselib_finish ();
235	if (cfg_changed)
236	cleanup_cfg (0);
237	}
238
239	/* Try to simplify a single SET instruction. SET is the set pattern.
240	INSN is the instruction it came from.
241	This function only handles one case: if we set a register to a value
242	which is not a register, we try to find that value in some other register
243	and change the set into a register copy. */
244
245	static int
246	reload_cse_simplify_set (rtx set, rtx_insn *insn)
247	{
248	int did_change = 0;
249	int dreg;
250	rtx src;
251	reg_class_t dclass;
252	int old_cost;
253	cselib_val *val;
254	struct elt_loc_list *l;
255	enum rtx_code extend_op = UNKNOWN;
256	bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
257
258	dreg = true_regnum (SET_DEST (set));
259	if (dreg < 0)
260	return 0;
261
262	src = SET_SRC (set);
263	if (side_effects_p (src) || true_regnum (src) >= 0)
264	return 0;
265
266	dclass = REGNO_REG_CLASS (dreg);
267
268	/* When replacing a memory with a register, we need to honor assumptions
269	that combine made wrt the contents of sign bits. We'll do this by
270	generating an extend instruction instead of a reg->reg copy. Thus
271	the destination must be a register that we can widen. */
272	if (MEM_P (src)
273	&& (extend_op = load_extend_op (GET_MODE (src))) != UNKNOWN
274	&& !REG_P (SET_DEST (set)))
275	return 0;
276
277	val = cselib_lookup (src, GET_MODE (SET_DEST (set)), 0, VOIDmode);
278	if (! val)
279	return 0;
280
281	/* If memory loads are cheaper than register copies, don't change them. */
282	if (MEM_P (src))
283	old_cost = memory_move_cost (GET_MODE (src), dclass, true);
284	else if (REG_P (src))
285	old_cost = register_move_cost (GET_MODE (src),
286	REGNO_REG_CLASS (REGNO (src)), dclass);
287	else
288	old_cost = set_src_cost (x: src, GET_MODE (SET_DEST (set)), speed_p: speed);
289
290	for (l = val->locs; l; l = l->next)
291	{
292	rtx this_rtx = l->loc;
293	int this_cost;
294
295	if (CONSTANT_P (this_rtx) && ! references_value_p (this_rtx, 0))
296	{
297	if (extend_op != UNKNOWN)
298	{
299	wide_int result;
300
301	if (!CONST_SCALAR_INT_P (this_rtx))
302	continue;
303
304	switch (extend_op)
305	{
306	case ZERO_EXTEND:
307	result = wide_int::from (x: rtx_mode_t (this_rtx,
308	GET_MODE (src)),
309	BITS_PER_WORD, sgn: UNSIGNED);
310	break;
311	case SIGN_EXTEND:
312	result = wide_int::from (x: rtx_mode_t (this_rtx,
313	GET_MODE (src)),
314	BITS_PER_WORD, sgn: SIGNED);
315	break;
316	default:
317	gcc_unreachable ();
318	}
319	this_rtx = immed_wide_int_const (result, word_mode);
320	}
321
322	this_cost = set_src_cost (x: this_rtx, GET_MODE (SET_DEST (set)), speed_p: speed);
323	}
324	else if (REG_P (this_rtx))
325	{
326	if (extend_op != UNKNOWN)
327	{
328	this_rtx = gen_rtx_fmt_e (extend_op, word_mode, this_rtx);
329	this_cost = set_src_cost (x: this_rtx, mode: word_mode, speed_p: speed);
330	}
331	else
332	this_cost = register_move_cost (GET_MODE (this_rtx),
333	REGNO_REG_CLASS (REGNO (this_rtx)),
334	dclass);
335	}
336	else
337	continue;
338
339	/* If equal costs, prefer registers over anything else. That
340	tends to lead to smaller instructions on some machines. */
341	if (this_cost < old_cost
342	|| (this_cost == old_cost
343	&& REG_P (this_rtx)
344	&& !REG_P (SET_SRC (set))))
345	{
346	if (extend_op != UNKNOWN
347	&& REG_CAN_CHANGE_MODE_P (REGNO (SET_DEST (set)),
348	GET_MODE (SET_DEST (set)), word_mode))
349	{
350	rtx wide_dest = gen_rtx_REG (word_mode, REGNO (SET_DEST (set)));
351	ORIGINAL_REGNO (wide_dest) = ORIGINAL_REGNO (SET_DEST (set));
352	validate_change (insn, &SET_DEST (set), wide_dest, 1);
353	}
354
355	validate_unshare_change (insn, &SET_SRC (set), this_rtx, 1);
356	old_cost = this_cost, did_change = 1;
357	}
358	}
359
360	return did_change;
361	}
362
363	/* Try to replace operands in INSN with equivalent values that are already
364	in registers. This can be viewed as optional reloading.
365
366	For each non-register operand in the insn, see if any hard regs are
367	known to be equivalent to that operand. Record the alternatives which
368	can accept these hard registers. Among all alternatives, select the
369	ones which are better or equal to the one currently matching, where
370	"better" is in terms of '?' and '!' constraints. Among the remaining
371	alternatives, select the one which replaces most operands with
372	hard registers. */
373
374	static int
375	reload_cse_simplify_operands (rtx_insn *insn, rtx testreg)
376	{
377	int i, j;
378
379	/* For each operand, all registers that are equivalent to it. */
380	HARD_REG_SET equiv_regs[MAX_RECOG_OPERANDS];
381
382	const char *constraints[MAX_RECOG_OPERANDS];
383
384	/* Vector recording how bad an alternative is. */
385	int *alternative_reject;
386	/* Vector recording how many registers can be introduced by choosing
387	this alternative. */
388	int *alternative_nregs;
389	/* Array of vectors recording, for each operand and each alternative,
390	which hard register to substitute, or -1 if the operand should be
391	left as it is. */
392	int *op_alt_regno[MAX_RECOG_OPERANDS];
393	/* Array of alternatives, sorted in order of decreasing desirability. */
394	int *alternative_order;
395
396	extract_constrain_insn (insn);
397
398	if (recog_data.n_alternatives == 0 || recog_data.n_operands == 0)
399	return 0;
400
401	alternative_reject = XALLOCAVEC (int, recog_data.n_alternatives);
402	alternative_nregs = XALLOCAVEC (int, recog_data.n_alternatives);
403	alternative_order = XALLOCAVEC (int, recog_data.n_alternatives);
404	memset (s: alternative_reject, c: 0, n: recog_data.n_alternatives * sizeof (int));
405	memset (s: alternative_nregs, c: 0, n: recog_data.n_alternatives * sizeof (int));
406
407	/* For each operand, find out which regs are equivalent. */
408	for (i = 0; i < recog_data.n_operands; i++)
409	{
410	cselib_val *v;
411	struct elt_loc_list *l;
412	rtx op;
413
414	CLEAR_HARD_REG_SET (set&: equiv_regs[i]);
415
416	/* cselib blows up on CODE_LABELs. Trying to fix that doesn't seem
417	right, so avoid the problem here. Similarly NOTE_INSN_DELETED_LABEL.
418	Likewise if we have a constant and the insn pattern doesn't tell us
419	the mode we need. */
420	if (LABEL_P (recog_data.operand[i])
421	|| (NOTE_P (recog_data.operand[i])
422	&& NOTE_KIND (recog_data.operand[i]) == NOTE_INSN_DELETED_LABEL)
423	|| (CONSTANT_P (recog_data.operand[i])
424	&& recog_data.operand_mode[i] == VOIDmode))
425	continue;
426
427	op = recog_data.operand[i];
428	if (MEM_P (op) && load_extend_op (GET_MODE (op)) != UNKNOWN)
429	{
430	rtx set = single_set (insn);
431
432	/* We might have multiple sets, some of which do implicit
433	extension. Punt on this for now. */
434	if (! set)
435	continue;
436	/* If the destination is also a MEM or a STRICT_LOW_PART, no
437	extension applies.
438	Also, if there is an explicit extension, we don't have to
439	worry about an implicit one. */
440	else if (MEM_P (SET_DEST (set))
441	|| GET_CODE (SET_DEST (set)) == STRICT_LOW_PART
442	|| GET_CODE (SET_SRC (set)) == ZERO_EXTEND
443	|| GET_CODE (SET_SRC (set)) == SIGN_EXTEND)
444	; /* Continue ordinary processing. */
445	/* If the register cannot change mode to word_mode, it follows that
446	it cannot have been used in word_mode. */
447	else if (REG_P (SET_DEST (set))
448	&& !REG_CAN_CHANGE_MODE_P (REGNO (SET_DEST (set)),
449	GET_MODE (SET_DEST (set)),
450	word_mode))
451	; /* Continue ordinary processing. */
452	/* If this is a straight load, make the extension explicit. */
453	else if (REG_P (SET_DEST (set))
454	&& recog_data.n_operands == 2
455	&& SET_SRC (set) == op
456	&& SET_DEST (set) == recog_data.operand[1-i])
457	{
458	validate_change (insn, recog_data.operand_loc[i],
459	gen_rtx_fmt_e (load_extend_op (GET_MODE (op)),
460	word_mode, op),
461	1);
462	validate_change (insn, recog_data.operand_loc[1-i],
463	gen_rtx_REG (word_mode, REGNO (SET_DEST (set))),
464	1);
465	if (! apply_change_group ())
466	return 0;
467	return reload_cse_simplify_operands (insn, testreg);
468	}
469	else
470	/* ??? There might be arithmetic operations with memory that are
471	safe to optimize, but is it worth the trouble? */
472	continue;
473	}
474
475	if (side_effects_p (op))
476	continue;
477	v = cselib_lookup (op, recog_data.operand_mode[i], 0, VOIDmode);
478	if (! v)
479	continue;
480
481	for (l = v->locs; l; l = l->next)
482	if (REG_P (l->loc))
483	SET_HARD_REG_BIT (set&: equiv_regs[i], REGNO (l->loc));
484	}
485
486	alternative_mask preferred = get_preferred_alternatives (insn);
487	for (i = 0; i < recog_data.n_operands; i++)
488	{
489	machine_mode mode;
490	int regno;
491	const char *p;
492
493	op_alt_regno[i] = XALLOCAVEC (int, recog_data.n_alternatives);
494	for (j = 0; j < recog_data.n_alternatives; j++)
495	op_alt_regno[i][j] = -1;
496
497	p = constraints[i] = recog_data.constraints[i];
498	mode = recog_data.operand_mode[i];
499
500	/* Add the reject values for each alternative given by the constraints
501	for this operand. */
502	j = 0;
503	while (*p != '\0')
504	{
505	char c = *p++;
506	if (c == ',')
507	j++;
508	else if (c == '?')
509	alternative_reject[j] += 3;
510	else if (c == '!')
511	alternative_reject[j] += 300;
512	}
513
514	/* We won't change operands which are already registers. We
515	also don't want to modify output operands. */
516	regno = true_regnum (recog_data.operand[i]);
517	if (regno >= 0
518	|| constraints[i][0] == '='
519	|| constraints[i][0] == '+')
520	continue;
521
522	for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
523	{
524	enum reg_class rclass = NO_REGS;
525
526	if (! TEST_HARD_REG_BIT (set: equiv_regs[i], bit: regno))
527	continue;
528
529	set_mode_and_regno (testreg, mode, regno);
530
531	/* We found a register equal to this operand. Now look for all
532	alternatives that can accept this register and have not been
533	assigned a register they can use yet. */
534	j = 0;
535	p = constraints[i];
536	for (;;)
537	{
538	char c = *p;
539
540	switch (c)
541	{
542	case 'g':
543	rclass = reg_class_subunion[rclass][GENERAL_REGS];
544	break;
545
546	default:
547	rclass
548	= (reg_class_subunion
549	[rclass]
550	[reg_class_for_constraint (c: lookup_constraint (p))]);
551	break;
552
553	case ',': case '\0':
554	/* See if REGNO fits this alternative, and set it up as the
555	replacement register if we don't have one for this
556	alternative yet and the operand being replaced is not
557	a cheap CONST_INT. */
558	if (op_alt_regno[i][j] == -1
559	&& TEST_BIT (preferred, j)
560	&& reg_fits_class_p (testreg, rclass, 0, mode)
561	&& (!CONST_INT_P (recog_data.operand[i])
562	|| (set_src_cost (x: recog_data.operand[i], mode,
563	speed_p: optimize_bb_for_speed_p
564	(BLOCK_FOR_INSN (insn)))
565	> set_src_cost (x: testreg, mode,
566	speed_p: optimize_bb_for_speed_p
567	(BLOCK_FOR_INSN (insn))))))
568	{
569	alternative_nregs[j]++;
570	op_alt_regno[i][j] = regno;
571	}
572	j++;
573	rclass = NO_REGS;
574	break;
575	}
576	p += CONSTRAINT_LEN (c, p);
577
578	if (c == '\0')
579	break;
580	}
581	}
582	}
583
584	/* The loop below sets alternative_order[0] but -Wmaybe-uninitialized
585	can't know that. Clear it here to avoid the warning. */
586	alternative_order[0] = 0;
587	gcc_assert (!recog_data.n_alternatives
588	|| (which_alternative >= 0
589	&& which_alternative < recog_data.n_alternatives));
590
591	/* Record all alternatives which are better or equal to the currently
592	matching one in the alternative_order array. */
593	for (i = j = 0; i < recog_data.n_alternatives; i++)
594	if (alternative_reject[i] <= alternative_reject[which_alternative])
595	alternative_order[j++] = i;
596	recog_data.n_alternatives = j;
597
598	/* Sort it. Given a small number of alternatives, a dumb algorithm
599	won't hurt too much. */
600	for (i = 0; i < recog_data.n_alternatives - 1; i++)
601	{
602	int best = i;
603	int best_reject = alternative_reject[alternative_order[i]];
604	int best_nregs = alternative_nregs[alternative_order[i]];
605
606	for (j = i + 1; j < recog_data.n_alternatives; j++)
607	{
608	int this_reject = alternative_reject[alternative_order[j]];
609	int this_nregs = alternative_nregs[alternative_order[j]];
610
611	if (this_reject < best_reject
612	|| (this_reject == best_reject && this_nregs > best_nregs))
613	{
614	best = j;
615	best_reject = this_reject;
616	best_nregs = this_nregs;
617	}
618	}
619
620	std::swap (a&: alternative_order[best], b&: alternative_order[i]);
621	}
622
623	/* Substitute the operands as determined by op_alt_regno for the best
624	alternative. */
625	j = alternative_order[0];
626
627	for (i = 0; i < recog_data.n_operands; i++)
628	{
629	machine_mode mode = recog_data.operand_mode[i];
630	if (op_alt_regno[i][j] == -1)
631	continue;
632
633	validate_change (insn, recog_data.operand_loc[i],
634	gen_rtx_REG (mode, op_alt_regno[i][j]), 1);
635	}
636
637	for (i = recog_data.n_dups - 1; i >= 0; i--)
638	{
639	int op = recog_data.dup_num[i];
640	machine_mode mode = recog_data.operand_mode[op];
641
642	if (op_alt_regno[op][j] == -1)
643	continue;
644
645	validate_change (insn, recog_data.dup_loc[i],
646	gen_rtx_REG (mode, op_alt_regno[op][j]), 1);
647	}
648
649	return apply_change_group ();
650	}
651
652	/* If reload couldn't use reg+reg+offset addressing, try to use reg+reg
653	addressing now.
654	This code might also be useful when reload gave up on reg+reg addressing
655	because of clashes between the return register and INDEX_REG_CLASS. */
656
657	/* The maximum number of uses of a register we can keep track of to
658	replace them with reg+reg addressing. */
659	#define RELOAD_COMBINE_MAX_USES 16
660
661	/* Describes a recorded use of a register. */
662	struct reg_use
663	{
664	/* The insn where a register has been used. */
665	rtx_insn *insn;
666	/* Points to the memory reference enclosing the use, if any, NULL_RTX
667	otherwise. */
668	rtx containing_mem;
669	/* Location of the register within INSN. */
670	rtx *usep;
671	/* The reverse uid of the insn. */
672	int ruid;
673	};
674
675	/* If the register is used in some unknown fashion, USE_INDEX is negative.
676	If it is dead, USE_INDEX is RELOAD_COMBINE_MAX_USES, and STORE_RUID
677	indicates where it is first set or clobbered.
678	Otherwise, USE_INDEX is the index of the last encountered use of the
679	register (which is first among these we have seen since we scan backwards).
680	USE_RUID indicates the first encountered, i.e. last, of these uses.
681	If ALL_OFFSETS_MATCH is true, all encountered uses were inside a PLUS
682	with a constant offset; OFFSET contains this constant in that case.
683	STORE_RUID is always meaningful if we only want to use a value in a
684	register in a different place: it denotes the next insn in the insn
685	stream (i.e. the last encountered) that sets or clobbers the register.
686	REAL_STORE_RUID is similar, but clobbers are ignored when updating it.
687	EXPR is the expression used when storing the register. */
688	static struct
689	{
690	struct reg_use reg_use[RELOAD_COMBINE_MAX_USES];
691	rtx offset;
692	int use_index;
693	int store_ruid;
694	int real_store_ruid;
695	int use_ruid;
696	bool all_offsets_match;
697	rtx expr;
698	} reg_state[FIRST_PSEUDO_REGISTER];
699
700	/* Reverse linear uid. This is increased in reload_combine while scanning
701	the instructions from last to first. It is used to set last_label_ruid
702	and the store_ruid / use_ruid fields in reg_state. */
703	static int reload_combine_ruid;
704
705	/* The RUID of the last label we encountered in reload_combine. */
706	static int last_label_ruid;
707
708	/* The RUID of the last jump we encountered in reload_combine. */
709	static int last_jump_ruid;
710
711	/* The register numbers of the first and last index register. A value of
712	-1 in LAST_INDEX_REG indicates that we've previously computed these
713	values and found no suitable index registers. */
714	static int first_index_reg = -1;
715	static int last_index_reg;
716
717	#define LABEL_LIVE(LABEL) \
718	(label_live[CODE_LABEL_NUMBER (LABEL) - min_labelno])
719
720	/* Subroutine of reload_combine_split_ruids, called to fix up a single
721	ruid pointed to by *PRUID if it is higher than SPLIT_RUID. */
722
723	static inline void
724	reload_combine_split_one_ruid (int *pruid, int split_ruid)
725	{
726	if (*pruid > split_ruid)
727	(*pruid)++;
728	}
729
730	/* Called when we insert a new insn in a position we've already passed in
731	the scan. Examine all our state, increasing all ruids that are higher
732	than SPLIT_RUID by one in order to make room for a new insn. */
733
734	static void
735	reload_combine_split_ruids (int split_ruid)
736	{
737	unsigned i;
738
739	reload_combine_split_one_ruid (pruid: &reload_combine_ruid, split_ruid);
740	reload_combine_split_one_ruid (pruid: &last_label_ruid, split_ruid);
741	reload_combine_split_one_ruid (pruid: &last_jump_ruid, split_ruid);
742
743	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
744	{
745	int j, idx = reg_state[i].use_index;
746	reload_combine_split_one_ruid (pruid: &reg_state[i].use_ruid, split_ruid);
747	reload_combine_split_one_ruid (pruid: &reg_state[i].store_ruid, split_ruid);
748	reload_combine_split_one_ruid (pruid: &reg_state[i].real_store_ruid,
749	split_ruid);
750	if (idx < 0)
751	continue;
752	for (j = idx; j < RELOAD_COMBINE_MAX_USES; j++)
753	{
754	reload_combine_split_one_ruid (pruid: &reg_state[i].reg_use[j].ruid,
755	split_ruid);
756	}
757	}
758	}
759
760	/* Called when we are about to rescan a previously encountered insn with
761	reload_combine_note_use after modifying some part of it. This clears all
762	information about uses in that particular insn. */
763
764	static void
765	reload_combine_purge_insn_uses (rtx_insn *insn)
766	{
767	unsigned i;
768
769	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
770	{
771	int j, k, idx = reg_state[i].use_index;
772	if (idx < 0)
773	continue;
774	j = k = RELOAD_COMBINE_MAX_USES;
775	while (j-- > idx)
776	{
777	if (reg_state[i].reg_use[j].insn != insn)
778	{
779	k--;
780	if (k != j)
781	reg_state[i].reg_use[k] = reg_state[i].reg_use[j];
782	}
783	}
784	reg_state[i].use_index = k;
785	}
786	}
787
788	/* Called when we need to forget about all uses of REGNO after an insn
789	which is identified by RUID. */
790
791	static void
792	reload_combine_purge_reg_uses_after_ruid (unsigned regno, int ruid)
793	{
794	int j, k, idx = reg_state[regno].use_index;
795	if (idx < 0)
796	return;
797	j = k = RELOAD_COMBINE_MAX_USES;
798	while (j-- > idx)
799	{
800	if (reg_state[regno].reg_use[j].ruid >= ruid)
801	{
802	k--;
803	if (k != j)
804	reg_state[regno].reg_use[k] = reg_state[regno].reg_use[j];
805	}
806	}
807	reg_state[regno].use_index = k;
808	}
809
810	/* Find the use of REGNO with the ruid that is highest among those
811	lower than RUID_LIMIT, and return it if it is the only use of this
812	reg in the insn. Return NULL otherwise. */
813
814	static struct reg_use *
815	reload_combine_closest_single_use (unsigned regno, int ruid_limit)
816	{
817	int i, best_ruid = 0;
818	int use_idx = reg_state[regno].use_index;
819	struct reg_use *retval;
820
821	if (use_idx < 0)
822	return NULL;
823	retval = NULL;
824	for (i = use_idx; i < RELOAD_COMBINE_MAX_USES; i++)
825	{
826	struct reg_use *use = reg_state[regno].reg_use + i;
827	int this_ruid = use->ruid;
828	if (this_ruid >= ruid_limit)
829	continue;
830	if (this_ruid > best_ruid)
831	{
832	best_ruid = this_ruid;
833	retval = use;
834	}
835	else if (this_ruid == best_ruid)
836	retval = NULL;
837	}
838	if (last_label_ruid >= best_ruid)
839	return NULL;
840	return retval;
841	}
842
843	/* After we've moved an add insn, fix up any debug insns that occur
844	between the old location of the add and the new location. REG is
845	the destination register of the add insn; REPLACEMENT is the
846	SET_SRC of the add. FROM and TO specify the range in which we
847	should make this change on debug insns. */
848
849	static void
850	fixup_debug_insns (rtx reg, rtx replacement, rtx_insn *from, rtx_insn *to)
851	{
852	rtx_insn *insn;
853	for (insn = from; insn != to; insn = NEXT_INSN (insn))
854	{
855	rtx t;
856
857	if (!DEBUG_BIND_INSN_P (insn))
858	continue;
859
860	t = INSN_VAR_LOCATION_LOC (insn);
861	t = simplify_replace_rtx (t, reg, replacement);
862	validate_change (insn, &INSN_VAR_LOCATION_LOC (insn), t, 0);
863	}
864	}
865
866	/* Subroutine of reload_combine_recognize_const_pattern. Try to replace REG
867	with SRC in the insn described by USE, taking costs into account. Return
868	true if we made the replacement. */
869
870	static bool
871	try_replace_in_use (struct reg_use *use, rtx reg, rtx src)
872	{
873	rtx_insn *use_insn = use->insn;
874	rtx mem = use->containing_mem;
875	bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn: use_insn));
876
877	if (mem != NULL_RTX)
878	{
879	addr_space_t as = MEM_ADDR_SPACE (mem);
880	rtx oldaddr = XEXP (mem, 0);
881	rtx newaddr = NULL_RTX;
882	int old_cost = address_cost (oldaddr, GET_MODE (mem), as, speed);
883	int new_cost;
884
885	newaddr = simplify_replace_rtx (oldaddr, reg, src);
886	if (memory_address_addr_space_p (GET_MODE (mem), newaddr, as))
887	{
888	XEXP (mem, 0) = newaddr;
889	new_cost = address_cost (newaddr, GET_MODE (mem), as, speed);
890	XEXP (mem, 0) = oldaddr;
891	if (new_cost <= old_cost
892	&& validate_change (use_insn,
893	&XEXP (mem, 0), newaddr, 0))
894	return true;
895	}
896	}
897	else
898	{
899	rtx new_set = single_set (insn: use_insn);
900	if (new_set
901	&& REG_P (SET_DEST (new_set))
902	&& GET_CODE (SET_SRC (new_set)) == PLUS
903	&& REG_P (XEXP (SET_SRC (new_set), 0))
904	&& CONSTANT_P (XEXP (SET_SRC (new_set), 1)))
905	{
906	rtx new_src;
907	machine_mode mode = GET_MODE (SET_DEST (new_set));
908	int old_cost = set_src_cost (SET_SRC (new_set), mode, speed_p: speed);
909
910	gcc_assert (rtx_equal_p (XEXP (SET_SRC (new_set), 0), reg));
911	new_src = simplify_replace_rtx (SET_SRC (new_set), reg, src);
912
913	if (set_src_cost (x: new_src, mode, speed_p: speed) <= old_cost
914	&& validate_change (use_insn, &SET_SRC (new_set),
915	new_src, 0))
916	return true;
917	}
918	}
919	return false;
920	}
921
922	/* Called by reload_combine when scanning INSN. This function tries to detect
923	patterns where a constant is added to a register, and the result is used
924	in an address.
925	Return true if no further processing is needed on INSN; false if it wasn't
926	recognized and should be handled normally. */
927
928	static bool
929	reload_combine_recognize_const_pattern (rtx_insn *insn)
930	{
931	int from_ruid = reload_combine_ruid;
932	rtx set, pat, reg, src, addreg;
933	unsigned int regno;
934	struct reg_use *use;
935	bool must_move_add;
936	rtx_insn *add_moved_after_insn = NULL;
937	int add_moved_after_ruid = 0;
938	int clobbered_regno = -1;
939
940	set = single_set (insn);
941	if (set == NULL_RTX)
942	return false;
943
944	reg = SET_DEST (set);
945	src = SET_SRC (set);
946	if (!REG_P (reg)
947	|| REG_NREGS (reg) != 1
948	|| GET_MODE (reg) != Pmode
949	|| reg == stack_pointer_rtx)
950	return false;
951
952	regno = REGNO (reg);
953
954	/* We look for a REG1 = REG2 + CONSTANT insn, followed by either
955	uses of REG1 inside an address, or inside another add insn. If
956	possible and profitable, merge the addition into subsequent
957	uses. */
958	if (GET_CODE (src) != PLUS
959	|| !REG_P (XEXP (src, 0))
960	|| !CONSTANT_P (XEXP (src, 1)))
961	return false;
962
963	addreg = XEXP (src, 0);
964	must_move_add = rtx_equal_p (reg, addreg);
965
966	pat = PATTERN (insn);
967	if (must_move_add && set != pat)
968	{
969	/* We have to be careful when moving the add; apart from the
970	single_set there may also be clobbers. Recognize one special
971	case, that of one clobber alongside the set (likely a clobber
972	of the CC register). */
973	gcc_assert (GET_CODE (PATTERN (insn)) == PARALLEL);
974	if (XVECLEN (pat, 0) != 2 || XVECEXP (pat, 0, 0) != set
975	|| GET_CODE (XVECEXP (pat, 0, 1)) != CLOBBER
976	|| !REG_P (XEXP (XVECEXP (pat, 0, 1), 0)))
977	return false;
978	clobbered_regno = REGNO (XEXP (XVECEXP (pat, 0, 1), 0));
979	}
980
981	do
982	{
983	use = reload_combine_closest_single_use (regno, ruid_limit: from_ruid);
984
985	if (use)
986	/* Start the search for the next use from here. */
987	from_ruid = use->ruid;
988
989	if (use && GET_MODE (*use->usep) == Pmode)
990	{
991	bool delete_add = false;
992	rtx_insn *use_insn = use->insn;
993	int use_ruid = use->ruid;
994
995	/* Avoid moving the add insn past a jump. */
996	if (must_move_add && use_ruid <= last_jump_ruid)
997	break;
998
999	/* If the add clobbers another hard reg in parallel, don't move
1000	it past a real set of this hard reg. */
1001	if (must_move_add && clobbered_regno >= 0
1002	&& reg_state[clobbered_regno].real_store_ruid >= use_ruid)
1003	break;
1004
1005	gcc_assert (reg_state[regno].store_ruid <= use_ruid);
1006	/* Avoid moving a use of ADDREG past a point where it is stored. */
1007	if (reg_state[REGNO (addreg)].store_ruid > use_ruid)
1008	break;
1009
1010	/* We also must not move the addition past an insn that sets
1011	the same register, unless we can combine two add insns. */
1012	if (must_move_add && reg_state[regno].store_ruid == use_ruid)
1013	{
1014	if (use->containing_mem == NULL_RTX)
1015	delete_add = true;
1016	else
1017	break;
1018	}
1019
1020	if (try_replace_in_use (use, reg, src))
1021	{
1022	reload_combine_purge_insn_uses (insn: use_insn);
1023	reload_combine_note_use (&PATTERN (insn: use_insn), use_insn,
1024	use_ruid, NULL_RTX);
1025
1026	if (delete_add)
1027	{
1028	fixup_debug_insns (reg, replacement: src, from: insn, to: use_insn);
1029	delete_insn (insn);
1030	return true;
1031	}
1032	if (must_move_add)
1033	{
1034	add_moved_after_insn = use_insn;
1035	add_moved_after_ruid = use_ruid;
1036	}
1037	continue;
1038	}
1039	}
1040	/* If we get here, we couldn't handle this use. */
1041	if (must_move_add)
1042	break;
1043	}
1044	while (use);
1045
1046	if (!must_move_add || add_moved_after_insn == NULL_RTX)
1047	/* Process the add normally. */
1048	return false;
1049
1050	fixup_debug_insns (reg, replacement: src, from: insn, to: add_moved_after_insn);
1051
1052	reorder_insns (insn, insn, add_moved_after_insn);
1053	reload_combine_purge_reg_uses_after_ruid (regno, ruid: add_moved_after_ruid);
1054	reload_combine_split_ruids (split_ruid: add_moved_after_ruid - 1);
1055	reload_combine_note_use (&PATTERN (insn), insn,
1056	add_moved_after_ruid, NULL_RTX);
1057	reg_state[regno].store_ruid = add_moved_after_ruid;
1058
1059	return true;
1060	}
1061
1062	/* Called by reload_combine when scanning INSN. Try to detect a pattern we
1063	can handle and improve. Return true if no further processing is needed on
1064	INSN; false if it wasn't recognized and should be handled normally. */
1065
1066	static bool
1067	reload_combine_recognize_pattern (rtx_insn *insn)
1068	{
1069	rtx set, reg, src;
1070
1071	set = single_set (insn);
1072	if (set == NULL_RTX)
1073	return false;
1074
1075	reg = SET_DEST (set);
1076	src = SET_SRC (set);
1077	if (!REG_P (reg) || REG_NREGS (reg) != 1)
1078	return false;
1079
1080	unsigned int regno = REGNO (reg);
1081	machine_mode mode = GET_MODE (reg);
1082
1083	if (reg_state[regno].use_index < 0
1084	|| reg_state[regno].use_index >= RELOAD_COMBINE_MAX_USES)
1085	return false;
1086
1087	for (int i = reg_state[regno].use_index;
1088	i < RELOAD_COMBINE_MAX_USES; i++)
1089	{
1090	struct reg_use *use = reg_state[regno].reg_use + i;
1091	if (GET_MODE (*use->usep) != mode)
1092	return false;
1093	/* Don't try to adjust (use (REGX)). */
1094	if (GET_CODE (PATTERN (use->insn)) == USE
1095	&& &XEXP (PATTERN (use->insn), 0) == use->usep)
1096	return false;
1097	}
1098
1099	/* Look for (set (REGX) (CONST_INT))
1100	(set (REGX) (PLUS (REGX) (REGY)))
1101	...
1102	... (MEM (REGX)) ...
1103	and convert it to
1104	(set (REGZ) (CONST_INT))
1105	...
1106	... (MEM (PLUS (REGZ) (REGY)))... .
1107
1108	First, check that we have (set (REGX) (PLUS (REGX) (REGY)))
1109	and that we know all uses of REGX before it dies.
1110	Also, explicitly check that REGX != REGY; our life information
1111	does not yet show whether REGY changes in this insn. */
1112
1113	if (GET_CODE (src) == PLUS
1114	&& reg_state[regno].all_offsets_match
1115	&& last_index_reg != -1
1116	&& REG_P (XEXP (src, 1))
1117	&& rtx_equal_p (XEXP (src, 0), reg)
1118	&& !rtx_equal_p (XEXP (src, 1), reg)
1119	&& last_label_ruid < reg_state[regno].use_ruid)
1120	{
1121	rtx base = XEXP (src, 1);
1122	rtx_insn *prev = prev_nonnote_nondebug_insn (insn);
1123	rtx prev_set = prev ? single_set (insn: prev) : NULL_RTX;
1124	rtx index_reg = NULL_RTX;
1125	rtx reg_sum = NULL_RTX;
1126	int i;
1127
1128	/* Now we need to set INDEX_REG to an index register (denoted as
1129	REGZ in the illustration above) and REG_SUM to the expression
1130	register+register that we want to use to substitute uses of REG
1131	(typically in MEMs) with. First check REG and BASE for being
1132	index registers; we can use them even if they are not dead. */
1133	if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], bit: regno)
1134	|| TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS],
1135	REGNO (base)))
1136	{
1137	index_reg = reg;
1138	reg_sum = src;
1139	}
1140	else
1141	{
1142	/* Otherwise, look for a free index register. Since we have
1143	checked above that neither REG nor BASE are index registers,
1144	if we find anything at all, it will be different from these
1145	two registers. */
1146	for (i = first_index_reg; i <= last_index_reg; i++)
1147	{
1148	if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], bit: i)
1149	&& reg_state[i].use_index == RELOAD_COMBINE_MAX_USES
1150	&& reg_state[i].store_ruid <= reg_state[regno].use_ruid
1151	&& (crtl->abi->clobbers_full_reg_p (regno: i)
1152	|| df_regs_ever_live_p (i))
1153	&& (!frame_pointer_needed || i != HARD_FRAME_POINTER_REGNUM)
1154	&& !fixed_regs[i] && !global_regs[i]
1155	&& hard_regno_nregs (regno: i, GET_MODE (reg)) == 1
1156	&& targetm.hard_regno_scratch_ok (i))
1157	{
1158	index_reg = gen_rtx_REG (GET_MODE (reg), i);
1159	reg_sum = gen_rtx_PLUS (GET_MODE (reg), index_reg, base);
1160	break;
1161	}
1162	}
1163	}
1164
1165	/* Check that PREV_SET is indeed (set (REGX) (CONST_INT)) and that
1166	(REGY), i.e. BASE, is not clobbered before the last use we'll
1167	create. */
1168	if (reg_sum
1169	&& prev_set
1170	&& CONST_INT_P (SET_SRC (prev_set))
1171	&& rtx_equal_p (SET_DEST (prev_set), reg)
1172	&& (reg_state[REGNO (base)].store_ruid
1173	<= reg_state[regno].use_ruid))
1174	{
1175	/* Change destination register and, if necessary, the constant
1176	value in PREV, the constant loading instruction. */
1177	validate_change (prev, &SET_DEST (prev_set), index_reg, 1);
1178	if (reg_state[regno].offset != const0_rtx)
1179	{
1180	HOST_WIDE_INT c
1181	= trunc_int_for_mode (UINTVAL (SET_SRC (prev_set))
1182	+ UINTVAL (reg_state[regno].offset),
1183	GET_MODE (index_reg));
1184	validate_change (prev, &SET_SRC (prev_set), GEN_INT (c), 1);
1185	}
1186
1187	/* Now for every use of REG that we have recorded, replace REG
1188	with REG_SUM. */
1189	for (i = reg_state[regno].use_index;
1190	i < RELOAD_COMBINE_MAX_USES; i++)
1191	validate_unshare_change (reg_state[regno].reg_use[i].insn,
1192	reg_state[regno].reg_use[i].usep,
1193	/* Each change must have its own
1194	replacement. */
1195	reg_sum, 1);
1196
1197	if (apply_change_group ())
1198	{
1199	struct reg_use *lowest_ruid = NULL;
1200
1201	/* For every new use of REG_SUM, we have to record the use
1202	of BASE therein, i.e. operand 1. */
1203	for (i = reg_state[regno].use_index;
1204	i < RELOAD_COMBINE_MAX_USES; i++)
1205	{
1206	struct reg_use *use = reg_state[regno].reg_use + i;
1207	reload_combine_note_use (&XEXP (*use->usep, 1), use->insn,
1208	use->ruid, use->containing_mem);
1209	if (lowest_ruid == NULL || use->ruid < lowest_ruid->ruid)
1210	lowest_ruid = use;
1211	}
1212
1213	fixup_debug_insns (reg, replacement: reg_sum, from: insn, to: lowest_ruid->insn);
1214
1215	/* Delete the reg-reg addition. */
1216	delete_insn (insn);
1217
1218	if (reg_state[regno].offset != const0_rtx)
1219	/* Previous REG_EQUIV / REG_EQUAL notes for PREV
1220	are now invalid. */
1221	remove_reg_equal_equiv_notes (prev);
1222
1223	reg_state[regno].use_index = RELOAD_COMBINE_MAX_USES;
1224	return true;
1225	}
1226	}
1227	}
1228	return false;
1229	}
1230
1231	static void
1232	reload_combine (void)
1233	{
1234	rtx_insn *insn, *prev;
1235	basic_block bb;
1236	unsigned int r;
1237	int min_labelno, n_labels;
1238	HARD_REG_SET ever_live_at_start, *label_live;
1239
1240	/* To avoid wasting too much time later searching for an index register,
1241	determine the minimum and maximum index register numbers. */
1242	if (INDEX_REG_CLASS == NO_REGS)
1243	last_index_reg = -1;
1244	else if (first_index_reg == -1 && last_index_reg == 0)
1245	{
1246	for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1247	if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], bit: r))
1248	{
1249	if (first_index_reg == -1)
1250	first_index_reg = r;
1251
1252	last_index_reg = r;
1253	}
1254
1255	/* If no index register is available, we can quit now. Set LAST_INDEX_REG
1256	to -1 so we'll know to quit early the next time we get here. */
1257	if (first_index_reg == -1)
1258	{
1259	last_index_reg = -1;
1260	return;
1261	}
1262	}
1263
1264	/* Set up LABEL_LIVE and EVER_LIVE_AT_START. The register lifetime
1265	information is a bit fuzzy immediately after reload, but it's
1266	still good enough to determine which registers are live at a jump
1267	destination. */
1268	min_labelno = get_first_label_num ();
1269	n_labels = max_label_num () - min_labelno;
1270	label_live = XNEWVEC (HARD_REG_SET, n_labels);
1271	CLEAR_HARD_REG_SET (set&: ever_live_at_start);
1272
1273	FOR_EACH_BB_REVERSE_FN (bb, cfun)
1274	{
1275	insn = BB_HEAD (bb);
1276	if (LABEL_P (insn))
1277	{
1278	HARD_REG_SET live;
1279	bitmap live_in = df_get_live_in (bb);
1280
1281	REG_SET_TO_HARD_REG_SET (live, live_in);
1282	compute_use_by_pseudos (&live, live_in);
1283	LABEL_LIVE (insn) = live;
1284	ever_live_at_start |= live;
1285	}
1286	}
1287
1288	/* Initialize last_label_ruid, reload_combine_ruid and reg_state. */
1289	last_label_ruid = last_jump_ruid = reload_combine_ruid = 0;
1290	for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1291	{
1292	reg_state[r].store_ruid = 0;
1293	reg_state[r].real_store_ruid = 0;
1294	if (fixed_regs[r])
1295	reg_state[r].use_index = -1;
1296	else
1297	reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
1298	}
1299
1300	for (insn = get_last_insn (); insn; insn = prev)
1301	{
1302	bool control_flow_insn;
1303	rtx note;
1304
1305	prev = PREV_INSN (insn);
1306
1307	/* We cannot do our optimization across labels. Invalidating all the use
1308	information we have would be costly, so we just note where the label
1309	is and then later disable any optimization that would cross it. */
1310	if (LABEL_P (insn))
1311	last_label_ruid = reload_combine_ruid;
1312	else if (BARRIER_P (insn))
1313	{
1314	/* Crossing a barrier resets all the use information. */
1315	for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1316	if (! fixed_regs[r])
1317	reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
1318	}
1319	else if (INSN_P (insn) && volatile_insn_p (PATTERN (insn)))
1320	/* Optimizations across insns being marked as volatile must be
1321	prevented. All the usage information is invalidated
1322	here. */
1323	for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1324	if (! fixed_regs[r]
1325	&& reg_state[r].use_index != RELOAD_COMBINE_MAX_USES)
1326	reg_state[r].use_index = -1;
1327
1328	if (! NONDEBUG_INSN_P (insn))
1329	continue;
1330
1331	reload_combine_ruid++;
1332
1333	control_flow_insn = control_flow_insn_p (insn);
1334	if (control_flow_insn)
1335	last_jump_ruid = reload_combine_ruid;
1336
1337	if (reload_combine_recognize_const_pattern (insn)
1338	|| reload_combine_recognize_pattern (insn))
1339	continue;
1340
1341	note_stores (insn, reload_combine_note_store, NULL);
1342
1343	if (CALL_P (insn))
1344	{
1345	rtx link;
1346	HARD_REG_SET used_regs = insn_callee_abi (insn).full_reg_clobbers ();
1347
1348	for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1349	if (TEST_HARD_REG_BIT (set: used_regs, bit: r))
1350	{
1351	reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
1352	reg_state[r].store_ruid = reload_combine_ruid;
1353	}
1354
1355	for (link = CALL_INSN_FUNCTION_USAGE (insn); link;
1356	link = XEXP (link, 1))
1357	{
1358	rtx setuse = XEXP (link, 0);
1359	rtx usage_rtx = XEXP (setuse, 0);
1360
1361	if (GET_CODE (setuse) == USE && REG_P (usage_rtx))
1362	{
1363	unsigned int end_regno = END_REGNO (x: usage_rtx);
1364	for (unsigned int i = REGNO (usage_rtx); i < end_regno; ++i)
1365	reg_state[i].use_index = -1;
1366	}
1367	}
1368	}
1369
1370	if (control_flow_insn && !ANY_RETURN_P (PATTERN (insn)))
1371	{
1372	/* Non-spill registers might be used at the call destination in
1373	some unknown fashion, so we have to mark the unknown use. */
1374	HARD_REG_SET *live;
1375
1376	if ((condjump_p (insn) || condjump_in_parallel_p (insn))
1377	&& JUMP_LABEL (insn))
1378	{
1379	if (ANY_RETURN_P (JUMP_LABEL (insn)))
1380	live = NULL;
1381	else
1382	live = &LABEL_LIVE (JUMP_LABEL (insn));
1383	}
1384	else
1385	live = &ever_live_at_start;
1386
1387	if (live)
1388	for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1389	if (TEST_HARD_REG_BIT (set: *live, bit: r))
1390	reg_state[r].use_index = -1;
1391	}
1392
1393	reload_combine_note_use (&PATTERN (insn), insn, reload_combine_ruid,
1394	NULL_RTX);
1395
1396	for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1397	{
1398	if (REG_NOTE_KIND (note) == REG_INC && REG_P (XEXP (note, 0)))
1399	{
1400	int regno = REGNO (XEXP (note, 0));
1401	reg_state[regno].store_ruid = reload_combine_ruid;
1402	reg_state[regno].real_store_ruid = reload_combine_ruid;
1403	reg_state[regno].use_index = -1;
1404	}
1405	}
1406	}
1407
1408	free (ptr: label_live);
1409	}
1410
1411	/* Check if DST is a register or a subreg of a register; if it is,
1412	update store_ruid, real_store_ruid and use_index in the reg_state
1413	structure accordingly. Called via note_stores from reload_combine. */
1414
1415	static void
1416	reload_combine_note_store (rtx dst, const_rtx set, void *data ATTRIBUTE_UNUSED)
1417	{
1418	int regno = 0;
1419	int i;
1420	machine_mode mode = GET_MODE (dst);
1421
1422	if (GET_CODE (dst) == SUBREG)
1423	{
1424	regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
1425	GET_MODE (SUBREG_REG (dst)),
1426	SUBREG_BYTE (dst),
1427	GET_MODE (dst));
1428	dst = SUBREG_REG (dst);
1429	}
1430
1431	/* Some targets do argument pushes without adding REG_INC notes. */
1432
1433	if (MEM_P (dst))
1434	{
1435	dst = XEXP (dst, 0);
1436	if (GET_CODE (dst) == PRE_INC || GET_CODE (dst) == POST_INC
1437	|| GET_CODE (dst) == PRE_DEC || GET_CODE (dst) == POST_DEC
1438	|| GET_CODE (dst) == PRE_MODIFY || GET_CODE (dst) == POST_MODIFY)
1439	{
1440	unsigned int end_regno = END_REGNO (XEXP (dst, 0));
1441	for (unsigned int i = REGNO (XEXP (dst, 0)); i < end_regno; ++i)
1442	{
1443	/* We could probably do better, but for now mark the register
1444	as used in an unknown fashion and set/clobbered at this
1445	insn. */
1446	reg_state[i].use_index = -1;
1447	reg_state[i].store_ruid = reload_combine_ruid;
1448	reg_state[i].real_store_ruid = reload_combine_ruid;
1449	}
1450	}
1451	else
1452	return;
1453	}
1454
1455	if (!REG_P (dst))
1456	return;
1457	regno += REGNO (dst);
1458
1459	/* note_stores might have stripped a STRICT_LOW_PART, so we have to be
1460	careful with registers / register parts that are not full words.
1461	Similarly for ZERO_EXTRACT. */
1462	if (GET_CODE (SET_DEST (set)) == ZERO_EXTRACT
1463	|| GET_CODE (SET_DEST (set)) == STRICT_LOW_PART)
1464	{
1465	for (i = end_hard_regno (mode, regno) - 1; i >= regno; i--)
1466	{
1467	reg_state[i].use_index = -1;
1468	reg_state[i].store_ruid = reload_combine_ruid;
1469	reg_state[i].real_store_ruid = reload_combine_ruid;
1470	}
1471	}
1472	else
1473	{
1474	for (i = end_hard_regno (mode, regno) - 1; i >= regno; i--)
1475	{
1476	reg_state[i].store_ruid = reload_combine_ruid;
1477	if (GET_CODE (set) == SET)
1478	reg_state[i].real_store_ruid = reload_combine_ruid;
1479	reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
1480	}
1481	}
1482	}
1483
1484	/* XP points to a piece of rtl that has to be checked for any uses of
1485	registers.
1486	*XP is the pattern of INSN, or a part of it.
1487	Called from reload_combine, and recursively by itself. */
1488	static void
1489	reload_combine_note_use (rtx *xp, rtx_insn *insn, int ruid, rtx containing_mem)
1490	{
1491	rtx x = *xp;
1492	enum rtx_code code = x->code;
1493	const char *fmt;
1494	int i, j;
1495	rtx offset = const0_rtx; /* For the REG case below. */
1496
1497	switch (code)
1498	{
1499	case SET:
1500	if (REG_P (SET_DEST (x)))
1501	{
1502	reload_combine_note_use (xp: &SET_SRC (x), insn, ruid, NULL_RTX);
1503	return;
1504	}
1505	break;
1506
1507	case USE:
1508	/* If this is the USE of a return value, we can't change it. */
1509	if (REG_P (XEXP (x, 0)) && REG_FUNCTION_VALUE_P (XEXP (x, 0)))
1510	{
1511	/* Mark the return register as used in an unknown fashion. */
1512	rtx reg = XEXP (x, 0);
1513	unsigned int end_regno = END_REGNO (x: reg);
1514	for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
1515	reg_state[regno].use_index = -1;
1516	return;
1517	}
1518	break;
1519
1520	case CLOBBER:
1521	if (REG_P (SET_DEST (x)))
1522	{
1523	/* No spurious CLOBBERs of pseudo registers may remain. */
1524	gcc_assert (REGNO (SET_DEST (x)) < FIRST_PSEUDO_REGISTER);
1525	return;
1526	}
1527	break;
1528
1529	case PLUS:
1530	/* We are interested in (plus (reg) (const_int)) . */
1531	if (!REG_P (XEXP (x, 0))
1532	|| !CONST_INT_P (XEXP (x, 1)))
1533	break;
1534	offset = XEXP (x, 1);
1535	x = XEXP (x, 0);
1536	/* Fall through. */
1537	case REG:
1538	{
1539	int regno = REGNO (x);
1540	int use_index;
1541	int nregs;
1542
1543	/* No spurious USEs of pseudo registers may remain. */
1544	gcc_assert (regno < FIRST_PSEUDO_REGISTER);
1545
1546	nregs = REG_NREGS (x);
1547
1548	/* We can't substitute into multi-hard-reg uses. */
1549	if (nregs > 1)
1550	{
1551	while (--nregs >= 0)
1552	reg_state[regno + nregs].use_index = -1;
1553	return;
1554	}
1555
1556	/* We may be called to update uses in previously seen insns.
1557	Don't add uses beyond the last store we saw. */
1558	if (ruid < reg_state[regno].store_ruid)
1559	return;
1560
1561	/* If this register is already used in some unknown fashion, we
1562	can't do anything.
1563	If we decrement the index from zero to -1, we can't store more
1564	uses, so this register becomes used in an unknown fashion. */
1565	use_index = --reg_state[regno].use_index;
1566	if (use_index < 0)
1567	return;
1568
1569	if (use_index == RELOAD_COMBINE_MAX_USES - 1)
1570	{
1571	/* This is the first use of this register we have seen since we
1572	marked it as dead. */
1573	reg_state[regno].offset = offset;
1574	reg_state[regno].all_offsets_match = true;
1575	reg_state[regno].use_ruid = ruid;
1576	}
1577	else
1578	{
1579	if (reg_state[regno].use_ruid > ruid)
1580	reg_state[regno].use_ruid = ruid;
1581
1582	if (! rtx_equal_p (offset, reg_state[regno].offset))
1583	reg_state[regno].all_offsets_match = false;
1584	}
1585
1586	reg_state[regno].reg_use[use_index].insn = insn;
1587	reg_state[regno].reg_use[use_index].ruid = ruid;
1588	reg_state[regno].reg_use[use_index].containing_mem = containing_mem;
1589	reg_state[regno].reg_use[use_index].usep = xp;
1590	return;
1591	}
1592
1593	case MEM:
1594	containing_mem = x;
1595	break;
1596
1597	default:
1598	break;
1599	}
1600
1601	/* Recursively process the components of X. */
1602	fmt = GET_RTX_FORMAT (code);
1603	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1604	{
1605	if (fmt[i] == 'e')
1606	reload_combine_note_use (xp: &XEXP (x, i), insn, ruid, containing_mem);
1607	else if (fmt[i] == 'E')
1608	{
1609	for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1610	reload_combine_note_use (xp: &XVECEXP (x, i, j), insn, ruid,
1611	containing_mem);
1612	}
1613	}
1614	}
1615
1616	/* See if we can reduce the cost of a constant by replacing a move
1617	with an add. We track situations in which a register is set to a
1618	constant or to a register plus a constant. */
1619	/* We cannot do our optimization across labels. Invalidating all the
1620	information about register contents we have would be costly, so we
1621	use move2add_last_label_luid to note where the label is and then
1622	later disable any optimization that would cross it.
1623	reg_offset[n] / reg_base_reg[n] / reg_symbol_ref[n] / reg_mode[n]
1624	are only valid if reg_set_luid[n] is greater than
1625	move2add_last_label_luid.
1626	For a set that established a new (potential) base register with
1627	non-constant value, we use move2add_luid from the place where the
1628	setting insn is encountered; registers based off that base then
1629	get the same reg_set_luid. Constants all get
1630	move2add_last_label_luid + 1 as their reg_set_luid. */
1631	static int reg_set_luid[FIRST_PSEUDO_REGISTER];
1632
1633	/* If reg_base_reg[n] is negative, register n has been set to
1634	reg_offset[n] or reg_symbol_ref[n] + reg_offset[n] in mode reg_mode[n].
1635	If reg_base_reg[n] is non-negative, register n has been set to the
1636	sum of reg_offset[n] and the value of register reg_base_reg[n]
1637	before reg_set_luid[n], calculated in mode reg_mode[n] .
1638	For multi-hard-register registers, all but the first one are
1639	recorded as BLKmode in reg_mode. Setting reg_mode to VOIDmode
1640	marks it as invalid. */
1641	static HOST_WIDE_INT reg_offset[FIRST_PSEUDO_REGISTER];
1642	static int reg_base_reg[FIRST_PSEUDO_REGISTER];
1643	static rtx reg_symbol_ref[FIRST_PSEUDO_REGISTER];
1644	static machine_mode reg_mode[FIRST_PSEUDO_REGISTER];
1645
1646	/* move2add_luid is linearly increased while scanning the instructions
1647	from first to last. It is used to set reg_set_luid in
1648	reload_cse_move2add and move2add_note_store. */
1649	static int move2add_luid;
1650
1651	/* move2add_last_label_luid is set whenever a label is found. Labels
1652	invalidate all previously collected reg_offset data. */
1653	static int move2add_last_label_luid;
1654
1655	/* ??? We don't know how zero / sign extension is handled, hence we
1656	can't go from a narrower to a wider mode. */
1657	#define MODES_OK_FOR_MOVE2ADD(OUTMODE, INMODE) \
1658	(GET_MODE_SIZE (OUTMODE) == GET_MODE_SIZE (INMODE) \
1659	|| (GET_MODE_SIZE (OUTMODE) <= GET_MODE_SIZE (INMODE) \
1660	&& TRULY_NOOP_TRUNCATION_MODES_P (OUTMODE, INMODE)))
1661
1662	/* Record that REG is being set to a value with the mode of REG. */
1663
1664	static void
1665	move2add_record_mode (rtx reg)
1666	{
1667	int regno, nregs;
1668	machine_mode mode = GET_MODE (reg);
1669
1670	if (GET_CODE (reg) == SUBREG)
1671	{
1672	regno = subreg_regno (reg);
1673	nregs = subreg_nregs (reg);
1674	}
1675	else if (REG_P (reg))
1676	{
1677	regno = REGNO (reg);
1678	nregs = REG_NREGS (reg);
1679	}
1680	else
1681	gcc_unreachable ();
1682	for (int i = nregs - 1; i > 0; i--)
1683	reg_mode[regno + i] = BLKmode;
1684	reg_mode[regno] = mode;
1685	}
1686
1687	/* Record that REG is being set to the sum of SYM and OFF. */
1688
1689	static void
1690	move2add_record_sym_value (rtx reg, rtx sym, rtx off)
1691	{
1692	int regno = REGNO (reg);
1693
1694	move2add_record_mode (reg);
1695	reg_set_luid[regno] = move2add_luid;
1696	reg_base_reg[regno] = -1;
1697	reg_symbol_ref[regno] = sym;
1698	reg_offset[regno] = INTVAL (off);
1699	}
1700
1701	/* Check if REGNO contains a valid value in MODE. */
1702
1703	static bool
1704	move2add_valid_value_p (int regno, scalar_int_mode mode)
1705	{
1706	if (reg_set_luid[regno] <= move2add_last_label_luid)
1707	return false;
1708
1709	if (mode != reg_mode[regno])
1710	{
1711	scalar_int_mode old_mode;
1712	if (!is_a <scalar_int_mode> (m: reg_mode[regno], result: &old_mode)
1713	|| !MODES_OK_FOR_MOVE2ADD (mode, old_mode)
1714	|| !REG_CAN_CHANGE_MODE_P (regno, old_mode, mode))
1715	return false;
1716	/* The value loaded into regno in reg_mode[regno] is also valid in
1717	mode after truncation only if (REG:mode regno) is the lowpart of
1718	(REG:reg_mode[regno] regno). Now, for big endian, the starting
1719	regno of the lowpart might be different. */
1720	poly_int64 s_off = subreg_lowpart_offset (outermode: mode, innermode: old_mode);
1721	s_off = subreg_regno_offset (regno, old_mode, s_off, mode);
1722	if (maybe_ne (a: s_off, b: 0))
1723	/* We could in principle adjust regno, check reg_mode[regno] to be
1724	BLKmode, and return s_off to the caller (vs. -1 for failure),
1725	but we currently have no callers that could make use of this
1726	information. */
1727	return false;
1728	}
1729
1730	for (int i = end_hard_regno (mode, regno) - 1; i > regno; i--)
1731	if (reg_mode[i] != BLKmode)
1732	return false;
1733	return true;
1734	}
1735
1736	/* This function is called with INSN that sets REG (of mode MODE)
1737	to (SYM + OFF), while REG is known to already have value (SYM + offset).
1738	This function tries to change INSN into an add instruction
1739	(set (REG) (plus (REG) (OFF - offset))) using the known value.
1740	It also updates the information about REG's known value.
1741	Return true if we made a change. */
1742
1743	static bool
1744	move2add_use_add2_insn (scalar_int_mode mode, rtx reg, rtx sym, rtx off,
1745	rtx_insn *insn)
1746	{
1747	rtx set = single_set (insn);
1748	rtx src = SET_SRC (set);
1749	int regno = REGNO (reg);
1750	rtx new_src = gen_int_mode (UINTVAL (off) - reg_offset[regno], mode);
1751	bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
1752	bool changed = false;
1753
1754	/* (set (reg) (plus (reg) (const_int 0))) is not canonical;
1755	use (set (reg) (reg)) instead.
1756	We don't delete this insn, nor do we convert it into a
1757	note, to avoid losing register notes or the return
1758	value flag. jump2 already knows how to get rid of
1759	no-op moves. */
1760	if (new_src == const0_rtx)
1761	{
1762	/* If the constants are different, this is a
1763	truncation, that, if turned into (set (reg)
1764	(reg)), would be discarded. Maybe we should
1765	try a truncMN pattern? */
1766	if (INTVAL (off) == reg_offset [regno])
1767	changed = validate_change (insn, &SET_SRC (set), reg, 0);
1768	}
1769	else
1770	{
1771	struct full_rtx_costs oldcst, newcst;
1772	rtx tem = gen_rtx_PLUS (mode, reg, new_src);
1773
1774	get_full_set_rtx_cost (x: set, c: &oldcst);
1775	SET_SRC (set) = tem;
1776	get_full_set_rtx_cost (x: set, c: &newcst);
1777	SET_SRC (set) = src;
1778
1779	if (costs_lt_p (a: &newcst, b: &oldcst, speed)
1780	&& have_add2_insn (reg, new_src))
1781	changed = validate_change (insn, &SET_SRC (set), tem, 0);
1782	else if (sym == NULL_RTX && mode != BImode)
1783	{
1784	scalar_int_mode narrow_mode;
1785	FOR_EACH_MODE_UNTIL (narrow_mode, mode)
1786	{
1787	if (have_insn_for (STRICT_LOW_PART, narrow_mode)
1788	&& ((reg_offset[regno] & ~GET_MODE_MASK (narrow_mode))
1789	== (INTVAL (off) & ~GET_MODE_MASK (narrow_mode))))
1790	{
1791	rtx narrow_reg = gen_lowpart_common (narrow_mode, reg);
1792	rtx narrow_src = gen_int_mode (INTVAL (off),
1793	narrow_mode);
1794	rtx new_set
1795	= gen_rtx_SET (gen_rtx_STRICT_LOW_PART (VOIDmode,
1796	narrow_reg),
1797	narrow_src);
1798	get_full_set_rtx_cost (x: new_set, c: &newcst);
1799
1800	/* We perform this replacement only if NEXT is either a
1801	naked SET, or else its single_set is the first element
1802	in a PARALLEL. */
1803	rtx *setloc = GET_CODE (PATTERN (insn)) == PARALLEL
1804	? &XVECEXP (PATTERN (insn), 0, 0) : &PATTERN (insn);
1805	if (*setloc == set && costs_lt_p (a: &newcst, b: &oldcst, speed))
1806	{
1807	changed = validate_change (insn, setloc, new_set, 0);
1808	if (changed)
1809	break;
1810	}
1811	}
1812	}
1813	}
1814	}
1815	move2add_record_sym_value (reg, sym, off);
1816	return changed;
1817	}
1818
1819
1820	/* This function is called with INSN that sets REG (of mode MODE) to
1821	(SYM + OFF), but REG doesn't have known value (SYM + offset). This
1822	function tries to find another register which is known to already have
1823	value (SYM + offset) and change INSN into an add instruction
1824	(set (REG) (plus (the found register) (OFF - offset))) if such
1825	a register is found. It also updates the information about
1826	REG's known value.
1827	Return true iff we made a change. */
1828
1829	static bool
1830	move2add_use_add3_insn (scalar_int_mode mode, rtx reg, rtx sym, rtx off,
1831	rtx_insn *insn)
1832	{
1833	rtx set = single_set (insn);
1834	rtx src = SET_SRC (set);
1835	int regno = REGNO (reg);
1836	int min_regno = 0;
1837	bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
1838	int i;
1839	bool changed = false;
1840	struct full_rtx_costs oldcst, newcst, mincst;
1841	rtx plus_expr;
1842
1843	init_costs_to_max (c: &mincst);
1844	get_full_set_rtx_cost (x: set, c: &oldcst);
1845
1846	plus_expr = gen_rtx_PLUS (GET_MODE (reg), reg, const0_rtx);
1847	SET_SRC (set) = plus_expr;
1848
1849	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1850	if (move2add_valid_value_p (regno: i, mode)
1851	&& reg_base_reg[i] < 0
1852	&& reg_symbol_ref[i] != NULL_RTX
1853	&& rtx_equal_p (sym, reg_symbol_ref[i]))
1854	{
1855	rtx new_src = gen_int_mode (UINTVAL (off) - reg_offset[i],
1856	GET_MODE (reg));
1857	/* (set (reg) (plus (reg) (const_int 0))) is not canonical;
1858	use (set (reg) (reg)) instead.
1859	We don't delete this insn, nor do we convert it into a
1860	note, to avoid losing register notes or the return
1861	value flag. jump2 already knows how to get rid of
1862	no-op moves. */
1863	if (new_src == const0_rtx)
1864	{
1865	init_costs_to_zero (c: &mincst);
1866	min_regno = i;
1867	break;
1868	}
1869	else
1870	{
1871	XEXP (plus_expr, 1) = new_src;
1872	get_full_set_rtx_cost (x: set, c: &newcst);
1873
1874	if (costs_lt_p (a: &newcst, b: &mincst, speed))
1875	{
1876	mincst = newcst;
1877	min_regno = i;
1878	}
1879	}
1880	}
1881	SET_SRC (set) = src;
1882
1883	if (costs_lt_p (a: &mincst, b: &oldcst, speed))
1884	{
1885	rtx tem;
1886
1887	tem = gen_rtx_REG (GET_MODE (reg), min_regno);
1888	if (i != min_regno)
1889	{
1890	rtx new_src = gen_int_mode (UINTVAL (off) - reg_offset[min_regno],
1891	GET_MODE (reg));
1892	tem = gen_rtx_PLUS (GET_MODE (reg), tem, new_src);
1893	}
1894	if (validate_change (insn, &SET_SRC (set), tem, 0))
1895	changed = true;
1896	}
1897	reg_set_luid[regno] = move2add_luid;
1898	move2add_record_sym_value (reg, sym, off);
1899	return changed;
1900	}
1901
1902	/* Perform any invalidations necessary for INSN. */
1903
1904	static void
1905	reload_cse_move2add_invalidate (rtx_insn *insn)
1906	{
1907	for (rtx note = REG_NOTES (insn); note; note = XEXP (note, 1))
1908	{
1909	if (REG_NOTE_KIND (note) == REG_INC
1910	&& REG_P (XEXP (note, 0)))
1911	{
1912	/* Reset the information about this register. */
1913	int regno = REGNO (XEXP (note, 0));
1914	if (regno < FIRST_PSEUDO_REGISTER)
1915	{
1916	move2add_record_mode (XEXP (note, 0));
1917	reg_mode[regno] = VOIDmode;
1918	}
1919	}
1920	}
1921
1922	/* There are no REG_INC notes for SP autoinc. */
1923	subrtx_var_iterator::array_type array;
1924	FOR_EACH_SUBRTX_VAR (iter, array, PATTERN (insn), NONCONST)
1925	{
1926	rtx mem = *iter;
1927	if (mem
1928	&& MEM_P (mem)
1929	&& GET_RTX_CLASS (GET_CODE (XEXP (mem, 0))) == RTX_AUTOINC)
1930	{
1931	if (XEXP (XEXP (mem, 0), 0) == stack_pointer_rtx)
1932	reg_mode[STACK_POINTER_REGNUM] = VOIDmode;
1933	}
1934	}
1935
1936	note_stores (insn, move2add_note_store, insn);
1937
1938	/* If INSN is a conditional branch, we try to extract an
1939	implicit set out of it. */
1940	if (any_condjump_p (insn))
1941	{
1942	rtx cnd = fis_get_condition (insn);
1943
1944	if (cnd != NULL_RTX
1945	&& GET_CODE (cnd) == NE
1946	&& REG_P (XEXP (cnd, 0))
1947	&& !reg_set_p (XEXP (cnd, 0), insn)
1948	/* The following two checks, which are also in
1949	move2add_note_store, are intended to reduce the
1950	number of calls to gen_rtx_SET to avoid memory
1951	allocation if possible. */
1952	&& SCALAR_INT_MODE_P (GET_MODE (XEXP (cnd, 0)))
1953	&& REG_NREGS (XEXP (cnd, 0)) == 1
1954	&& CONST_INT_P (XEXP (cnd, 1)))
1955	{
1956	rtx implicit_set = gen_rtx_SET (XEXP (cnd, 0), XEXP (cnd, 1));
1957	move2add_note_store (SET_DEST (implicit_set), implicit_set, insn);
1958	}
1959	}
1960
1961	/* If this is a CALL_INSN, all call used registers are stored with
1962	unknown values. */
1963	if (CALL_P (insn))
1964	{
1965	function_abi callee_abi = insn_callee_abi (insn);
1966	for (int i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1967	if (reg_mode[i] != VOIDmode
1968	&& reg_mode[i] != BLKmode
1969	&& callee_abi.clobbers_reg_p (mode: reg_mode[i], regno: i))
1970	/* Reset the information about this register. */
1971	reg_mode[i] = VOIDmode;
1972	}
1973	}
1974
1975	/* Convert move insns with constant inputs to additions if they are cheaper.
1976	Return true if any changes were made. */
1977	static bool
1978	reload_cse_move2add (rtx_insn *first)
1979	{
1980	int i;
1981	rtx_insn *insn;
1982	bool changed = false;
1983
1984	for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1985	{
1986	reg_set_luid[i] = 0;
1987	reg_offset[i] = 0;
1988	reg_base_reg[i] = 0;
1989	reg_symbol_ref[i] = NULL_RTX;
1990	reg_mode[i] = VOIDmode;
1991	}
1992
1993	move2add_last_label_luid = 0;
1994	move2add_luid = 2;
1995	for (insn = first; insn; insn = NEXT_INSN (insn), move2add_luid++)
1996	{
1997	rtx set;
1998
1999	if (LABEL_P (insn))
2000	{
2001	move2add_last_label_luid = move2add_luid;
2002	/* We're going to increment move2add_luid twice after a
2003	label, so that we can use move2add_last_label_luid + 1 as
2004	the luid for constants. */
2005	move2add_luid++;
2006	continue;
2007	}
2008	if (! INSN_P (insn))
2009	continue;
2010	set = single_set (insn);
2011	/* For simplicity, we only perform this optimization on
2012	single-sets. */
2013	scalar_int_mode mode;
2014	if (set
2015	&& REG_P (SET_DEST (set))
2016	&& is_a <scalar_int_mode> (GET_MODE (SET_DEST (set)), result: &mode))
2017	{
2018	rtx reg = SET_DEST (set);
2019	int regno = REGNO (reg);
2020	rtx src = SET_SRC (set);
2021
2022	/* Check if we have valid information on the contents of this
2023	register in the mode of REG. */
2024	if (move2add_valid_value_p (regno, mode)
2025	&& dbg_cnt (index: cse2_move2add))
2026	{
2027	/* Try to transform (set (REGX) (CONST_INT A))
2028	...
2029	(set (REGX) (CONST_INT B))
2030	to
2031	(set (REGX) (CONST_INT A))
2032	...
2033	(set (REGX) (plus (REGX) (CONST_INT B-A)))
2034	or
2035	(set (REGX) (CONST_INT A))
2036	...
2037	(set (STRICT_LOW_PART (REGX)) (CONST_INT B))
2038	*/
2039
2040	if (CONST_INT_P (src)
2041	&& reg_base_reg[regno] < 0
2042	&& reg_symbol_ref[regno] == NULL_RTX)
2043	{
2044	changed |= move2add_use_add2_insn (mode, reg, NULL_RTX,
2045	off: src, insn);
2046	continue;
2047	}
2048
2049	/* Try to transform (set (REGX) (REGY))
2050	(set (REGX) (PLUS (REGX) (CONST_INT A)))
2051	...
2052	(set (REGX) (REGY))
2053	(set (REGX) (PLUS (REGX) (CONST_INT B)))
2054	to
2055	(set (REGX) (REGY))
2056	(set (REGX) (PLUS (REGX) (CONST_INT A)))
2057	...
2058	(set (REGX) (plus (REGX) (CONST_INT B-A))) */
2059	else if (REG_P (src)
2060	&& reg_set_luid[regno] == reg_set_luid[REGNO (src)]
2061	&& reg_base_reg[regno] == reg_base_reg[REGNO (src)]
2062	&& move2add_valid_value_p (REGNO (src), mode))
2063	{
2064	rtx_insn *next = next_nonnote_nondebug_insn (insn);
2065	rtx set = NULL_RTX;
2066	if (next)
2067	set = single_set (insn: next);
2068	if (set
2069	&& SET_DEST (set) == reg
2070	&& GET_CODE (SET_SRC (set)) == PLUS
2071	&& XEXP (SET_SRC (set), 0) == reg
2072	&& CONST_INT_P (XEXP (SET_SRC (set), 1)))
2073	{
2074	rtx src3 = XEXP (SET_SRC (set), 1);
2075	unsigned HOST_WIDE_INT added_offset = UINTVAL (src3);
2076	HOST_WIDE_INT base_offset = reg_offset[REGNO (src)];
2077	HOST_WIDE_INT regno_offset = reg_offset[regno];
2078	rtx new_src =
2079	gen_int_mode (added_offset
2080	+ base_offset
2081	- regno_offset,
2082	mode);
2083	bool success = false;
2084	bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
2085
2086	if (new_src == const0_rtx)
2087	/* See above why we create (set (reg) (reg)) here. */
2088	success
2089	= validate_change (next, &SET_SRC (set), reg, 0);
2090	else
2091	{
2092	rtx old_src = SET_SRC (set);
2093	struct full_rtx_costs oldcst, newcst;
2094	rtx tem = gen_rtx_PLUS (mode, reg, new_src);
2095
2096	get_full_set_rtx_cost (x: set, c: &oldcst);
2097	SET_SRC (set) = tem;
2098	get_full_set_src_cost (x: tem, mode, c: &newcst);
2099	SET_SRC (set) = old_src;
2100	costs_add_n_insns (c: &oldcst, n: 1);
2101
2102	rtx *setloc = GET_CODE (PATTERN (next)) == PARALLEL
2103	? &XVECEXP (PATTERN (next), 0, 0) : &PATTERN (insn: next);
2104	if (*setloc == set
2105	&& costs_lt_p (a: &newcst, b: &oldcst, speed)
2106	&& have_add2_insn (reg, new_src))
2107	{
2108	rtx newpat = gen_rtx_SET (reg, tem);
2109	success
2110	= validate_change (next, setloc, newpat, 0);
2111	}
2112	}
2113	if (success)
2114	delete_insn (insn);
2115	changed |= success;
2116	insn = next;
2117	/* Make sure to perform any invalidations related to
2118	NEXT/INSN since we're going to bypass the normal
2119	flow with the continue below.
2120
2121	Do this before recording the new mode/offset. */
2122	reload_cse_move2add_invalidate (insn);
2123	move2add_record_mode (reg);
2124	reg_offset[regno]
2125	= trunc_int_for_mode (added_offset + base_offset,
2126	mode);
2127	continue;
2128	}
2129	}
2130	}
2131
2132	/* Try to transform
2133	(set (REGX) (CONST (PLUS (SYMBOL_REF) (CONST_INT A))))
2134	...
2135	(set (REGY) (CONST (PLUS (SYMBOL_REF) (CONST_INT B))))
2136	to
2137	(set (REGX) (CONST (PLUS (SYMBOL_REF) (CONST_INT A))))
2138	...
2139	(set (REGY) (CONST (PLUS (REGX) (CONST_INT B-A)))) */
2140	if ((GET_CODE (src) == SYMBOL_REF
2141	|| (GET_CODE (src) == CONST
2142	&& GET_CODE (XEXP (src, 0)) == PLUS
2143	&& GET_CODE (XEXP (XEXP (src, 0), 0)) == SYMBOL_REF
2144	&& CONST_INT_P (XEXP (XEXP (src, 0), 1))))
2145	&& dbg_cnt (index: cse2_move2add))
2146	{
2147	rtx sym, off;
2148
2149	if (GET_CODE (src) == SYMBOL_REF)
2150	{
2151	sym = src;
2152	off = const0_rtx;
2153	}
2154	else
2155	{
2156	sym = XEXP (XEXP (src, 0), 0);
2157	off = XEXP (XEXP (src, 0), 1);
2158	}
2159
2160	/* If the reg already contains the value which is sum of
2161	sym and some constant value, we can use an add2 insn. */
2162	if (move2add_valid_value_p (regno, mode)
2163	&& reg_base_reg[regno] < 0
2164	&& reg_symbol_ref[regno] != NULL_RTX
2165	&& rtx_equal_p (sym, reg_symbol_ref[regno]))
2166	changed |= move2add_use_add2_insn (mode, reg, sym, off, insn);
2167
2168	/* Otherwise, we have to find a register whose value is sum
2169	of sym and some constant value. */
2170	else
2171	changed |= move2add_use_add3_insn (mode, reg, sym, off, insn);
2172
2173	continue;
2174	}
2175	}
2176	reload_cse_move2add_invalidate (insn);
2177	}
2178	return changed;
2179	}
2180
2181	/* SET is a SET or CLOBBER that sets DST. DATA is the insn which
2182	contains SET.
2183	Update reg_set_luid, reg_offset and reg_base_reg accordingly.
2184	Called from reload_cse_move2add via note_stores. */
2185
2186	static void
2187	move2add_note_store (rtx dst, const_rtx set, void *data)
2188	{
2189	rtx_insn *insn = (rtx_insn *) data;
2190	unsigned int regno = 0;
2191	scalar_int_mode mode;
2192
2193	if (GET_CODE (dst) == SUBREG)
2194	regno = subreg_regno (dst);
2195	else if (REG_P (dst))
2196	regno = REGNO (dst);
2197	else
2198	return;
2199
2200	if (!is_a <scalar_int_mode> (GET_MODE (dst), result: &mode))
2201	goto invalidate;
2202
2203	if (GET_CODE (set) == SET)
2204	{
2205	rtx note, sym = NULL_RTX;
2206	rtx off;
2207
2208	note = find_reg_equal_equiv_note (insn);
2209	if (note && GET_CODE (XEXP (note, 0)) == SYMBOL_REF)
2210	{
2211	sym = XEXP (note, 0);
2212	off = const0_rtx;
2213	}
2214	else if (note && GET_CODE (XEXP (note, 0)) == CONST
2215	&& GET_CODE (XEXP (XEXP (note, 0), 0)) == PLUS
2216	&& GET_CODE (XEXP (XEXP (XEXP (note, 0), 0), 0)) == SYMBOL_REF
2217	&& CONST_INT_P (XEXP (XEXP (XEXP (note, 0), 0), 1)))
2218	{
2219	sym = XEXP (XEXP (XEXP (note, 0), 0), 0);
2220	off = XEXP (XEXP (XEXP (note, 0), 0), 1);
2221	}
2222
2223	if (sym != NULL_RTX)
2224	{
2225	move2add_record_sym_value (reg: dst, sym, off);
2226	return;
2227	}
2228	}
2229
2230	if (GET_CODE (set) == SET
2231	&& GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
2232	&& GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
2233	{
2234	rtx src = SET_SRC (set);
2235	rtx base_reg;
2236	unsigned HOST_WIDE_INT offset;
2237	int base_regno;
2238
2239	switch (GET_CODE (src))
2240	{
2241	case PLUS:
2242	if (REG_P (XEXP (src, 0)))
2243	{
2244	base_reg = XEXP (src, 0);
2245
2246	if (CONST_INT_P (XEXP (src, 1)))
2247	offset = UINTVAL (XEXP (src, 1));
2248	else if (REG_P (XEXP (src, 1))
2249	&& move2add_valid_value_p (REGNO (XEXP (src, 1)), mode))
2250	{
2251	if (reg_base_reg[REGNO (XEXP (src, 1))] < 0
2252	&& reg_symbol_ref[REGNO (XEXP (src, 1))] == NULL_RTX)
2253	offset = reg_offset[REGNO (XEXP (src, 1))];
2254	/* Maybe the first register is known to be a
2255	constant. */
2256	else if (move2add_valid_value_p (REGNO (base_reg), mode)
2257	&& reg_base_reg[REGNO (base_reg)] < 0
2258	&& reg_symbol_ref[REGNO (base_reg)] == NULL_RTX)
2259	{
2260	offset = reg_offset[REGNO (base_reg)];
2261	base_reg = XEXP (src, 1);
2262	}
2263	else
2264	goto invalidate;
2265	}
2266	else
2267	goto invalidate;
2268
2269	break;
2270	}
2271
2272	goto invalidate;
2273
2274	case REG:
2275	base_reg = src;
2276	offset = 0;
2277	break;
2278
2279	case CONST_INT:
2280	/* Start tracking the register as a constant. */
2281	reg_base_reg[regno] = -1;
2282	reg_symbol_ref[regno] = NULL_RTX;
2283	reg_offset[regno] = INTVAL (SET_SRC (set));
2284	/* We assign the same luid to all registers set to constants. */
2285	reg_set_luid[regno] = move2add_last_label_luid + 1;
2286	move2add_record_mode (reg: dst);
2287	return;
2288
2289	default:
2290	goto invalidate;
2291	}
2292
2293	base_regno = REGNO (base_reg);
2294	/* If information about the base register is not valid, set it
2295	up as a new base register, pretending its value is known
2296	starting from the current insn. */
2297	if (!move2add_valid_value_p (regno: base_regno, mode))
2298	{
2299	reg_base_reg[base_regno] = base_regno;
2300	reg_symbol_ref[base_regno] = NULL_RTX;
2301	reg_offset[base_regno] = 0;
2302	reg_set_luid[base_regno] = move2add_luid;
2303	gcc_assert (GET_MODE (base_reg) == mode);
2304	move2add_record_mode (reg: base_reg);
2305	}
2306
2307	/* Copy base information from our base register. */
2308	reg_set_luid[regno] = reg_set_luid[base_regno];
2309	reg_base_reg[regno] = reg_base_reg[base_regno];
2310	reg_symbol_ref[regno] = reg_symbol_ref[base_regno];
2311
2312	/* Compute the sum of the offsets or constants. */
2313	reg_offset[regno]
2314	= trunc_int_for_mode (offset + reg_offset[base_regno], mode);
2315
2316	move2add_record_mode (reg: dst);
2317	}
2318	else
2319	{
2320	invalidate:
2321	/* Invalidate the contents of the register. */
2322	move2add_record_mode (reg: dst);
2323	reg_mode[regno] = VOIDmode;
2324	}
2325	}
2326
2327	namespace {
2328
2329	const pass_data pass_data_postreload_cse =
2330	{
2331	.type: RTL_PASS, /* type */
2332	.name: "postreload", /* name */
2333	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
2334	.tv_id: TV_RELOAD_CSE_REGS, /* tv_id */
2335	.properties_required: 0, /* properties_required */
2336	.properties_provided: 0, /* properties_provided */
2337	.properties_destroyed: 0, /* properties_destroyed */
2338	.todo_flags_start: 0, /* todo_flags_start */
2339	TODO_df_finish, /* todo_flags_finish */
2340	};
2341
2342	class pass_postreload_cse : public rtl_opt_pass
2343	{
2344	public:
2345	pass_postreload_cse (gcc::context *ctxt)
2346	: rtl_opt_pass (pass_data_postreload_cse, ctxt)
2347	{}
2348
2349	/* opt_pass methods: */
2350	bool gate (function *) final override
2351	{
2352	return (optimize > 0 && reload_completed);
2353	}
2354
2355	unsigned int execute (function *) final override;
2356
2357	}; // class pass_postreload_cse
2358
2359	unsigned int
2360	pass_postreload_cse::execute (function *fun)
2361	{
2362	if (!dbg_cnt (index: postreload_cse))
2363	return 0;
2364
2365	/* Do a very simple CSE pass over just the hard registers. */
2366	reload_cse_regs (first: get_insns ());
2367	/* Reload_cse_regs can eliminate potentially-trapping MEMs.
2368	Remove any EH edges associated with them. */
2369	if (fun->can_throw_non_call_exceptions
2370	&& purge_all_dead_edges ())
2371	cleanup_cfg (0);
2372
2373	return 0;
2374	}
2375
2376	} // anon namespace
2377
2378	rtl_opt_pass *
2379	make_pass_postreload_cse (gcc::context *ctxt)
2380	{
2381	return new pass_postreload_cse (ctxt);
2382	}
2383