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