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