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