OSDN Git Service

d1e58ab944d4ef823ef105847e42d7c119e67976
[pf3gnuchains/gcc-fork.git] / gcc / postreload.c
1 /* Perform simple optimizations to clean up the result of reload.
2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26
27 #include "machmode.h"
28 #include "hard-reg-set.h"
29 #include "rtl.h"
30 #include "tm_p.h"
31 #include "obstack.h"
32 #include "insn-config.h"
33 #include "flags.h"
34 #include "function.h"
35 #include "expr.h"
36 #include "optabs.h"
37 #include "regs.h"
38 #include "basic-block.h"
39 #include "reload.h"
40 #include "recog.h"
41 #include "output.h"
42 #include "cselib.h"
43 #include "real.h"
44 #include "toplev.h"
45 #include "except.h"
46 #include "tree.h"
47 #include "timevar.h"
48 #include "tree-pass.h"
49
50 static int reload_cse_noop_set_p (rtx);
51 static void reload_cse_simplify (rtx, rtx);
52 static void reload_cse_regs_1 (rtx);
53 static int reload_cse_simplify_set (rtx, rtx);
54 static int reload_cse_simplify_operands (rtx, rtx);
55
56 static void reload_combine (void);
57 static void reload_combine_note_use (rtx *, rtx);
58 static void reload_combine_note_store (rtx, rtx, void *);
59
60 static void reload_cse_move2add (rtx);
61 static void move2add_note_store (rtx, rtx, void *);
62
63 /* Call cse / combine like post-reload optimization phases.
64    FIRST is the first instruction.  */
65 void
66 reload_cse_regs (rtx first ATTRIBUTE_UNUSED)
67 {
68   reload_cse_regs_1 (first);
69   reload_combine ();
70   reload_cse_move2add (first);
71   if (flag_expensive_optimizations)
72     reload_cse_regs_1 (first);
73 }
74
75 /* See whether a single set SET is a noop.  */
76 static int
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.  */
86 static void
87 reload_cse_simplify (rtx insn, rtx testreg)
88 {
89   rtx body = PATTERN (insn);
90
91   if (GET_CODE (body) == SET)
92     {
93       int count = 0;
94
95       /* Simplify even if we may think it is a no-op.
96          We may think a memory load of a value smaller than WORD_SIZE
97          is redundant because we haven't taken into account possible
98          implicit extension.  reload_cse_simplify_set() will bring
99          this out, so it's safer to simplify before we delete.  */
100       count += reload_cse_simplify_set (body, insn);
101
102       if (!count && reload_cse_noop_set_p (body))
103         {
104           rtx value = SET_DEST (body);
105           if (REG_P (value)
106               && ! REG_FUNCTION_VALUE_P (value))
107             value = 0;
108           delete_insn_and_edges (insn);
109           return;
110         }
111
112       if (count > 0)
113         apply_change_group ();
114       else
115         reload_cse_simplify_operands (insn, testreg);
116     }
117   else if (GET_CODE (body) == PARALLEL)
118     {
119       int i;
120       int count = 0;
121       rtx value = NULL_RTX;
122
123       /* Registers mentioned in the clobber list for an asm cannot be reused
124          within the body of the asm.  Invalidate those registers now so that
125          we don't try to substitute values for them.  */
126       if (asm_noperands (body) >= 0)
127         {
128           for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
129             {
130               rtx part = XVECEXP (body, 0, i);
131               if (GET_CODE (part) == CLOBBER && REG_P (XEXP (part, 0)))
132                 cselib_invalidate_rtx (XEXP (part, 0));
133             }
134         }
135
136       /* If every action in a PARALLEL is a noop, we can delete
137          the entire PARALLEL.  */
138       for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
139         {
140           rtx part = XVECEXP (body, 0, i);
141           if (GET_CODE (part) == SET)
142             {
143               if (! reload_cse_noop_set_p (part))
144                 break;
145               if (REG_P (SET_DEST (part))
146                   && REG_FUNCTION_VALUE_P (SET_DEST (part)))
147                 {
148                   if (value)
149                     break;
150                   value = SET_DEST (part);
151                 }
152             }
153           else if (GET_CODE (part) != CLOBBER)
154             break;
155         }
156
157       if (i < 0)
158         {
159           delete_insn_and_edges (insn);
160           /* We're done with this insn.  */
161           return;
162         }
163
164       /* It's not a no-op, but we can try to simplify it.  */
165       for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
166         if (GET_CODE (XVECEXP (body, 0, i)) == SET)
167           count += reload_cse_simplify_set (XVECEXP (body, 0, i), insn);
168
169       if (count > 0)
170         apply_change_group ();
171       else
172         reload_cse_simplify_operands (insn, testreg);
173     }
174 }
175
176 /* Do a very simple CSE pass over the hard registers.
177
178    This function detects no-op moves where we happened to assign two
179    different pseudo-registers to the same hard register, and then
180    copied one to the other.  Reload will generate a useless
181    instruction copying a register to itself.
182
183    This function also detects cases where we load a value from memory
184    into two different registers, and (if memory is more expensive than
185    registers) changes it to simply copy the first register into the
186    second register.
187
188    Another optimization is performed that scans the operands of each
189    instruction to see whether the value is already available in a
190    hard register.  It then replaces the operand with the hard register
191    if possible, much like an optional reload would.  */
192
193 static void
194 reload_cse_regs_1 (rtx first)
195 {
196   rtx insn;
197   rtx testreg = gen_rtx_REG (VOIDmode, -1);
198
199   cselib_init (true);
200   init_alias_analysis ();
201
202   for (insn = first; insn; insn = NEXT_INSN (insn))
203     {
204       if (INSN_P (insn))
205         reload_cse_simplify (insn, testreg);
206
207       cselib_process_insn (insn);
208     }
209
210   /* Clean up.  */
211   end_alias_analysis ();
212   cselib_finish ();
213 }
214
215 /* Try to simplify a single SET instruction.  SET is the set pattern.
216    INSN is the instruction it came from.
217    This function only handles one case: if we set a register to a value
218    which is not a register, we try to find that value in some other register
219    and change the set into a register copy.  */
220
221 static int
222 reload_cse_simplify_set (rtx set, rtx insn)
223 {
224   int did_change = 0;
225   int dreg;
226   rtx src;
227   enum reg_class dclass;
228   int old_cost;
229   cselib_val *val;
230   struct elt_loc_list *l;
231 #ifdef LOAD_EXTEND_OP
232   enum rtx_code extend_op = UNKNOWN;
233 #endif
234
235   dreg = true_regnum (SET_DEST (set));
236   if (dreg < 0)
237     return 0;
238
239   src = SET_SRC (set);
240   if (side_effects_p (src) || true_regnum (src) >= 0)
241     return 0;
242
243   dclass = REGNO_REG_CLASS (dreg);
244
245 #ifdef LOAD_EXTEND_OP
246   /* When replacing a memory with a register, we need to honor assumptions
247      that combine made wrt the contents of sign bits.  We'll do this by
248      generating an extend instruction instead of a reg->reg copy.  Thus
249      the destination must be a register that we can widen.  */
250   if (MEM_P (src)
251       && GET_MODE_BITSIZE (GET_MODE (src)) < BITS_PER_WORD
252       && (extend_op = LOAD_EXTEND_OP (GET_MODE (src))) != UNKNOWN
253       && !REG_P (SET_DEST (set)))
254     return 0;
255 #endif
256
257   val = cselib_lookup (src, GET_MODE (SET_DEST (set)), 0);
258   if (! val)
259     return 0;
260
261   /* If memory loads are cheaper than register copies, don't change them.  */
262   if (MEM_P (src))
263     old_cost = MEMORY_MOVE_COST (GET_MODE (src), dclass, 1);
264   else if (REG_P (src))
265     old_cost = REGISTER_MOVE_COST (GET_MODE (src),
266                                    REGNO_REG_CLASS (REGNO (src)), dclass);
267   else
268     old_cost = rtx_cost (src, SET);
269
270   for (l = val->locs; l; l = l->next)
271     {
272       rtx this_rtx = l->loc;
273       int this_cost;
274
275       if (CONSTANT_P (this_rtx) && ! references_value_p (this_rtx, 0))
276         {
277 #ifdef LOAD_EXTEND_OP
278           if (extend_op != UNKNOWN)
279             {
280               HOST_WIDE_INT this_val;
281
282               /* ??? I'm lazy and don't wish to handle CONST_DOUBLE.  Other
283                  constants, such as SYMBOL_REF, cannot be extended.  */
284               if (GET_CODE (this_rtx) != CONST_INT)
285                 continue;
286
287               this_val = INTVAL (this_rtx);
288               switch (extend_op)
289                 {
290                 case ZERO_EXTEND:
291                   this_val &= GET_MODE_MASK (GET_MODE (src));
292                   break;
293                 case SIGN_EXTEND:
294                   /* ??? In theory we're already extended.  */
295                   if (this_val == trunc_int_for_mode (this_val, GET_MODE (src)))
296                     break;
297                 default:
298                   gcc_unreachable ();
299                 }
300               this_rtx = GEN_INT (this_val);
301             }
302 #endif
303           this_cost = rtx_cost (this_rtx, SET);
304         }
305       else if (REG_P (this_rtx))
306         {
307 #ifdef LOAD_EXTEND_OP
308           if (extend_op != UNKNOWN)
309             {
310               this_rtx = gen_rtx_fmt_e (extend_op, word_mode, this_rtx);
311               this_cost = rtx_cost (this_rtx, SET);
312             }
313           else
314 #endif
315             this_cost = REGISTER_MOVE_COST (GET_MODE (this_rtx),
316                                             REGNO_REG_CLASS (REGNO (this_rtx)),
317                                             dclass);
318         }
319       else
320         continue;
321
322       /* If equal costs, prefer registers over anything else.  That
323          tends to lead to smaller instructions on some machines.  */
324       if (this_cost < old_cost
325           || (this_cost == old_cost
326               && REG_P (this_rtx)
327               && !REG_P (SET_SRC (set))))
328         {
329 #ifdef LOAD_EXTEND_OP
330           if (GET_MODE_BITSIZE (GET_MODE (SET_DEST (set))) < BITS_PER_WORD
331               && extend_op != UNKNOWN
332 #ifdef CANNOT_CHANGE_MODE_CLASS
333               && !CANNOT_CHANGE_MODE_CLASS (GET_MODE (SET_DEST (set)),
334                                             word_mode,
335                                             REGNO_REG_CLASS (REGNO (SET_DEST (set))))
336 #endif
337               )
338             {
339               rtx wide_dest = gen_rtx_REG (word_mode, REGNO (SET_DEST (set)));
340               ORIGINAL_REGNO (wide_dest) = ORIGINAL_REGNO (SET_DEST (set));
341               validate_change (insn, &SET_DEST (set), wide_dest, 1);
342             }
343 #endif
344
345           validate_change (insn, &SET_SRC (set), copy_rtx (this_rtx), 1);
346           old_cost = this_cost, did_change = 1;
347         }
348     }
349
350   return did_change;
351 }
352
353 /* Try to replace operands in INSN with equivalent values that are already
354    in registers.  This can be viewed as optional reloading.
355
356    For each non-register operand in the insn, see if any hard regs are
357    known to be equivalent to that operand.  Record the alternatives which
358    can accept these hard registers.  Among all alternatives, select the
359    ones which are better or equal to the one currently matching, where
360    "better" is in terms of '?' and '!' constraints.  Among the remaining
361    alternatives, select the one which replaces most operands with
362    hard registers.  */
363
364 static int
365 reload_cse_simplify_operands (rtx insn, rtx testreg)
366 {
367   int i, j;
368
369   /* For each operand, all registers that are equivalent to it.  */
370   HARD_REG_SET equiv_regs[MAX_RECOG_OPERANDS];
371
372   const char *constraints[MAX_RECOG_OPERANDS];
373
374   /* Vector recording how bad an alternative is.  */
375   int *alternative_reject;
376   /* Vector recording how many registers can be introduced by choosing
377      this alternative.  */
378   int *alternative_nregs;
379   /* Array of vectors recording, for each operand and each alternative,
380      which hard register to substitute, or -1 if the operand should be
381      left as it is.  */
382   int *op_alt_regno[MAX_RECOG_OPERANDS];
383   /* Array of alternatives, sorted in order of decreasing desirability.  */
384   int *alternative_order;
385
386   extract_insn (insn);
387
388   if (recog_data.n_alternatives == 0 || recog_data.n_operands == 0)
389     return 0;
390
391   /* Figure out which alternative currently matches.  */
392   if (! constrain_operands (1))
393     fatal_insn_not_found (insn);
394
395   alternative_reject = alloca (recog_data.n_alternatives * sizeof (int));
396   alternative_nregs = alloca (recog_data.n_alternatives * sizeof (int));
397   alternative_order = alloca (recog_data.n_alternatives * sizeof (int));
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       enum machine_mode mode;
408
409       CLEAR_HARD_REG_SET (equiv_regs[i]);
410
411       /* cselib blows up on CODE_LABELs.  Trying to fix that doesn't seem
412          right, so avoid the problem here.  Likewise if we have a constant
413          and the insn pattern doesn't tell us the mode we need.  */
414       if (LABEL_P (recog_data.operand[i])
415           || (CONSTANT_P (recog_data.operand[i])
416               && recog_data.operand_mode[i] == VOIDmode))
417         continue;
418
419       op = recog_data.operand[i];
420       mode = GET_MODE (op);
421 #ifdef LOAD_EXTEND_OP
422       if (MEM_P (op)
423           && GET_MODE_BITSIZE (mode) < BITS_PER_WORD
424           && LOAD_EXTEND_OP (mode) != UNKNOWN)
425         {
426           rtx set = single_set (insn);
427
428           /* We might have multiple sets, some of which do implicit
429              extension.  Punt on this for now.  */
430           if (! set)
431             continue;
432           /* If the destination is also a MEM or a STRICT_LOW_PART, no
433              extension applies.
434              Also, if there is an explicit extension, we don't have to
435              worry about an implicit one.  */
436           else if (MEM_P (SET_DEST (set))
437                    || GET_CODE (SET_DEST (set)) == STRICT_LOW_PART
438                    || GET_CODE (SET_SRC (set)) == ZERO_EXTEND
439                    || GET_CODE (SET_SRC (set)) == SIGN_EXTEND)
440             ; /* Continue ordinary processing.  */
441 #ifdef CANNOT_CHANGE_MODE_CLASS
442           /* If the register cannot change mode to word_mode, it follows that
443              it cannot have been used in word_mode.  */
444           else if (REG_P (SET_DEST (set))
445                    && CANNOT_CHANGE_MODE_CLASS (GET_MODE (SET_DEST (set)),
446                                                 word_mode,
447                                                 REGNO_REG_CLASS (REGNO (SET_DEST (set)))))
448             ; /* Continue ordinary processing.  */
449 #endif
450           /* If this is a straight load, make the extension explicit.  */
451           else if (REG_P (SET_DEST (set))
452                    && recog_data.n_operands == 2
453                    && SET_SRC (set) == op
454                    && SET_DEST (set) == recog_data.operand[1-i])
455             {
456               validate_change (insn, recog_data.operand_loc[i],
457                                gen_rtx_fmt_e (LOAD_EXTEND_OP (mode),
458                                               word_mode, op),
459                                1);
460               validate_change (insn, recog_data.operand_loc[1-i],
461                                gen_rtx_REG (word_mode, REGNO (SET_DEST (set))),
462                                1);
463               if (! apply_change_group ())
464                 return 0;
465               return reload_cse_simplify_operands (insn, testreg);
466             }
467           else
468             /* ??? There might be arithmetic operations with memory that are
469                safe to optimize, but is it worth the trouble?  */
470             continue;
471         }
472 #endif /* LOAD_EXTEND_OP */
473       v = cselib_lookup (op, recog_data.operand_mode[i], 0);
474       if (! v)
475         continue;
476
477       for (l = v->locs; l; l = l->next)
478         if (REG_P (l->loc))
479           SET_HARD_REG_BIT (equiv_regs[i], REGNO (l->loc));
480     }
481
482   for (i = 0; i < recog_data.n_operands; i++)
483     {
484       enum machine_mode mode;
485       int regno;
486       const char *p;
487
488       op_alt_regno[i] = alloca (recog_data.n_alternatives * sizeof (int));
489       for (j = 0; j < recog_data.n_alternatives; j++)
490         op_alt_regno[i][j] = -1;
491
492       p = constraints[i] = recog_data.constraints[i];
493       mode = recog_data.operand_mode[i];
494
495       /* Add the reject values for each alternative given by the constraints
496          for this operand.  */
497       j = 0;
498       while (*p != '\0')
499         {
500           char c = *p++;
501           if (c == ',')
502             j++;
503           else if (c == '?')
504             alternative_reject[j] += 3;
505           else if (c == '!')
506             alternative_reject[j] += 300;
507         }
508
509       /* We won't change operands which are already registers.  We
510          also don't want to modify output operands.  */
511       regno = true_regnum (recog_data.operand[i]);
512       if (regno >= 0
513           || constraints[i][0] == '='
514           || constraints[i][0] == '+')
515         continue;
516
517       for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
518         {
519           int class = (int) NO_REGS;
520
521           if (! TEST_HARD_REG_BIT (equiv_regs[i], regno))
522             continue;
523
524           REGNO (testreg) = regno;
525           PUT_MODE (testreg, mode);
526
527           /* We found a register equal to this operand.  Now look for all
528              alternatives that can accept this register and have not been
529              assigned a register they can use yet.  */
530           j = 0;
531           p = constraints[i];
532           for (;;)
533             {
534               char c = *p;
535
536               switch (c)
537                 {
538                 case '=':  case '+':  case '?':
539                 case '#':  case '&':  case '!':
540                 case '*':  case '%':
541                 case '0':  case '1':  case '2':  case '3':  case '4':
542                 case '5':  case '6':  case '7':  case '8':  case '9':
543                 case 'm':  case '<':  case '>':  case 'V':  case 'o':
544                 case 'E':  case 'F':  case 'G':  case 'H':
545                 case 's':  case 'i':  case 'n':
546                 case 'I':  case 'J':  case 'K':  case 'L':
547                 case 'M':  case 'N':  case 'O':  case 'P':
548                 case 'p': case 'X':
549                   /* These don't say anything we care about.  */
550                   break;
551
552                 case 'g': case 'r':
553                   class = reg_class_subunion[(int) class][(int) GENERAL_REGS];
554                   break;
555
556                 default:
557                   class
558                     = (reg_class_subunion
559                        [(int) class]
560                        [(int) REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p)]);
561                   break;
562
563                 case ',': case '\0':
564                   /* See if REGNO fits this alternative, and set it up as the
565                      replacement register if we don't have one for this
566                      alternative yet and the operand being replaced is not
567                      a cheap CONST_INT.  */
568                   if (op_alt_regno[i][j] == -1
569                       && reg_fits_class_p (testreg, class, 0, mode)
570                       && (GET_CODE (recog_data.operand[i]) != CONST_INT
571                           || (rtx_cost (recog_data.operand[i], SET)
572                               > rtx_cost (testreg, SET))))
573                     {
574                       alternative_nregs[j]++;
575                       op_alt_regno[i][j] = regno;
576                     }
577                   j++;
578                   class = (int) NO_REGS;
579                   break;
580                 }
581               p += CONSTRAINT_LEN (c, p);
582
583               if (c == '\0')
584                 break;
585             }
586         }
587     }
588
589   /* Record all alternatives which are better or equal to the currently
590      matching one in the alternative_order array.  */
591   for (i = j = 0; i < recog_data.n_alternatives; i++)
592     if (alternative_reject[i] <= alternative_reject[which_alternative])
593       alternative_order[j++] = i;
594   recog_data.n_alternatives = j;
595
596   /* Sort it.  Given a small number of alternatives, a dumb algorithm
597      won't hurt too much.  */
598   for (i = 0; i < recog_data.n_alternatives - 1; i++)
599     {
600       int best = i;
601       int best_reject = alternative_reject[alternative_order[i]];
602       int best_nregs = alternative_nregs[alternative_order[i]];
603       int tmp;
604
605       for (j = i + 1; j < recog_data.n_alternatives; j++)
606         {
607           int this_reject = alternative_reject[alternative_order[j]];
608           int this_nregs = alternative_nregs[alternative_order[j]];
609
610           if (this_reject < best_reject
611               || (this_reject == best_reject && this_nregs > best_nregs))
612             {
613               best = j;
614               best_reject = this_reject;
615               best_nregs = this_nregs;
616             }
617         }
618
619       tmp = alternative_order[best];
620       alternative_order[best] = alternative_order[i];
621       alternative_order[i] = tmp;
622     }
623
624   /* Substitute the operands as determined by op_alt_regno for the best
625      alternative.  */
626   j = alternative_order[0];
627
628   for (i = 0; i < recog_data.n_operands; i++)
629     {
630       enum machine_mode mode = recog_data.operand_mode[i];
631       if (op_alt_regno[i][j] == -1)
632         continue;
633
634       validate_change (insn, recog_data.operand_loc[i],
635                        gen_rtx_REG (mode, op_alt_regno[i][j]), 1);
636     }
637
638   for (i = recog_data.n_dups - 1; i >= 0; i--)
639     {
640       int op = recog_data.dup_num[i];
641       enum machine_mode mode = recog_data.operand_mode[op];
642
643       if (op_alt_regno[op][j] == -1)
644         continue;
645
646       validate_change (insn, recog_data.dup_loc[i],
647                        gen_rtx_REG (mode, op_alt_regno[op][j]), 1);
648     }
649
650   return apply_change_group ();
651 }
652 \f
653 /* If reload couldn't use reg+reg+offset addressing, try to use reg+reg
654    addressing now.
655    This code might also be useful when reload gave up on reg+reg addressing
656    because of clashes between the return register and INDEX_REG_CLASS.  */
657
658 /* The maximum number of uses of a register we can keep track of to
659    replace them with reg+reg addressing.  */
660 #define RELOAD_COMBINE_MAX_USES 6
661
662 /* INSN is the insn where a register has ben used, and USEP points to the
663    location of the register within the rtl.  */
664 struct reg_use { rtx insn, *usep; };
665
666 /* If the register is used in some unknown fashion, USE_INDEX is negative.
667    If it is dead, USE_INDEX is RELOAD_COMBINE_MAX_USES, and STORE_RUID
668    indicates where it becomes live again.
669    Otherwise, USE_INDEX is the index of the last encountered use of the
670    register (which is first among these we have seen since we scan backwards),
671    OFFSET contains the constant offset that is added to the register in
672    all encountered uses, and USE_RUID indicates the first encountered, i.e.
673    last, of these uses.
674    STORE_RUID is always meaningful if we only want to use a value in a
675    register in a different place: it denotes the next insn in the insn
676    stream (i.e. the last encountered) that sets or clobbers the register.  */
677 static struct
678   {
679     struct reg_use reg_use[RELOAD_COMBINE_MAX_USES];
680     int use_index;
681     rtx offset;
682     int store_ruid;
683     int use_ruid;
684   } reg_state[FIRST_PSEUDO_REGISTER];
685
686 /* Reverse linear uid.  This is increased in reload_combine while scanning
687    the instructions from last to first.  It is used to set last_label_ruid
688    and the store_ruid / use_ruid fields in reg_state.  */
689 static int reload_combine_ruid;
690
691 #define LABEL_LIVE(LABEL) \
692   (label_live[CODE_LABEL_NUMBER (LABEL) - min_labelno])
693
694 static void
695 reload_combine (void)
696 {
697   rtx insn, set;
698   int first_index_reg = -1;
699   int last_index_reg = 0;
700   int i;
701   basic_block bb;
702   unsigned int r;
703   int last_label_ruid;
704   int min_labelno, n_labels;
705   HARD_REG_SET ever_live_at_start, *label_live;
706
707   /* If reg+reg can be used in offsetable memory addresses, the main chunk of
708      reload has already used it where appropriate, so there is no use in
709      trying to generate it now.  */
710   if (double_reg_address_ok && INDEX_REG_CLASS != NO_REGS)
711     return;
712
713   /* To avoid wasting too much time later searching for an index register,
714      determine the minimum and maximum index register numbers.  */
715   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
716     if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], r))
717       {
718         if (first_index_reg == -1)
719           first_index_reg = r;
720
721         last_index_reg = r;
722       }
723
724   /* If no index register is available, we can quit now.  */
725   if (first_index_reg == -1)
726     return;
727
728   /* Set up LABEL_LIVE and EVER_LIVE_AT_START.  The register lifetime
729      information is a bit fuzzy immediately after reload, but it's
730      still good enough to determine which registers are live at a jump
731      destination.  */
732   min_labelno = get_first_label_num ();
733   n_labels = max_label_num () - min_labelno;
734   label_live = XNEWVEC (HARD_REG_SET, n_labels);
735   CLEAR_HARD_REG_SET (ever_live_at_start);
736
737   FOR_EACH_BB_REVERSE (bb)
738     {
739       insn = BB_HEAD (bb);
740       if (LABEL_P (insn))
741         {
742           HARD_REG_SET live;
743
744           REG_SET_TO_HARD_REG_SET (live,
745                                    bb->il.rtl->global_live_at_start);
746           compute_use_by_pseudos (&live,
747                                   bb->il.rtl->global_live_at_start);
748           COPY_HARD_REG_SET (LABEL_LIVE (insn), live);
749           IOR_HARD_REG_SET (ever_live_at_start, live);
750         }
751     }
752
753   /* Initialize last_label_ruid, reload_combine_ruid and reg_state.  */
754   last_label_ruid = reload_combine_ruid = 0;
755   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
756     {
757       reg_state[r].store_ruid = reload_combine_ruid;
758       if (fixed_regs[r])
759         reg_state[r].use_index = -1;
760       else
761         reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
762     }
763
764   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
765     {
766       rtx note;
767
768       /* We cannot do our optimization across labels.  Invalidating all the use
769          information we have would be costly, so we just note where the label
770          is and then later disable any optimization that would cross it.  */
771       if (LABEL_P (insn))
772         last_label_ruid = reload_combine_ruid;
773       else if (BARRIER_P (insn))
774         for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
775           if (! fixed_regs[r])
776               reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
777
778       if (! INSN_P (insn))
779         continue;
780
781       reload_combine_ruid++;
782
783       /* Look for (set (REGX) (CONST_INT))
784          (set (REGX) (PLUS (REGX) (REGY)))
785          ...
786          ... (MEM (REGX)) ...
787          and convert it to
788          (set (REGZ) (CONST_INT))
789          ...
790          ... (MEM (PLUS (REGZ) (REGY)))... .
791
792          First, check that we have (set (REGX) (PLUS (REGX) (REGY)))
793          and that we know all uses of REGX before it dies.  
794          Also, explicitly check that REGX != REGY; our life information
795          does not yet show whether REGY changes in this insn.  */
796       set = single_set (insn);
797       if (set != NULL_RTX
798           && REG_P (SET_DEST (set))
799           && (hard_regno_nregs[REGNO (SET_DEST (set))]
800                               [GET_MODE (SET_DEST (set))]
801               == 1)
802           && GET_CODE (SET_SRC (set)) == PLUS
803           && REG_P (XEXP (SET_SRC (set), 1))
804           && rtx_equal_p (XEXP (SET_SRC (set), 0), SET_DEST (set))
805           && !rtx_equal_p (XEXP (SET_SRC (set), 1), SET_DEST (set))
806           && last_label_ruid < reg_state[REGNO (SET_DEST (set))].use_ruid)
807         {
808           rtx reg = SET_DEST (set);
809           rtx plus = SET_SRC (set);
810           rtx base = XEXP (plus, 1);
811           rtx prev = prev_nonnote_insn (insn);
812           rtx prev_set = prev ? single_set (prev) : NULL_RTX;
813           unsigned int regno = REGNO (reg);
814           rtx const_reg = NULL_RTX;
815           rtx reg_sum = NULL_RTX;
816
817           /* Now, we need an index register.
818              We'll set index_reg to this index register, const_reg to the
819              register that is to be loaded with the constant
820              (denoted as REGZ in the substitution illustration above),
821              and reg_sum to the register-register that we want to use to
822              substitute uses of REG (typically in MEMs) with.
823              First check REG and BASE for being index registers;
824              we can use them even if they are not dead.  */
825           if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], regno)
826               || TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS],
827                                     REGNO (base)))
828             {
829               const_reg = reg;
830               reg_sum = plus;
831             }
832           else
833             {
834               /* Otherwise, look for a free index register.  Since we have
835                  checked above that neither REG nor BASE are index registers,
836                  if we find anything at all, it will be different from these
837                  two registers.  */
838               for (i = first_index_reg; i <= last_index_reg; i++)
839                 {
840                   if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS],
841                                          i)
842                       && reg_state[i].use_index == RELOAD_COMBINE_MAX_USES
843                       && reg_state[i].store_ruid <= reg_state[regno].use_ruid
844                       && hard_regno_nregs[i][GET_MODE (reg)] == 1)
845                     {
846                       rtx index_reg = gen_rtx_REG (GET_MODE (reg), i);
847
848                       const_reg = index_reg;
849                       reg_sum = gen_rtx_PLUS (GET_MODE (reg), index_reg, base);
850                       break;
851                     }
852                 }
853             }
854
855           /* Check that PREV_SET is indeed (set (REGX) (CONST_INT)) and that
856              (REGY), i.e. BASE, is not clobbered before the last use we'll
857              create.  */
858           if (prev_set != 0
859               && GET_CODE (SET_SRC (prev_set)) == CONST_INT
860               && rtx_equal_p (SET_DEST (prev_set), reg)
861               && reg_state[regno].use_index >= 0
862               && (reg_state[REGNO (base)].store_ruid
863                   <= reg_state[regno].use_ruid)
864               && reg_sum != 0)
865             {
866               int i;
867
868               /* Change destination register and, if necessary, the
869                  constant value in PREV, the constant loading instruction.  */
870               validate_change (prev, &SET_DEST (prev_set), const_reg, 1);
871               if (reg_state[regno].offset != const0_rtx)
872                 validate_change (prev,
873                                  &SET_SRC (prev_set),
874                                  GEN_INT (INTVAL (SET_SRC (prev_set))
875                                           + INTVAL (reg_state[regno].offset)),
876                                  1);
877
878               /* Now for every use of REG that we have recorded, replace REG
879                  with REG_SUM.  */
880               for (i = reg_state[regno].use_index;
881                    i < RELOAD_COMBINE_MAX_USES; i++)
882                 validate_change (reg_state[regno].reg_use[i].insn,
883                                  reg_state[regno].reg_use[i].usep,
884                                  /* Each change must have its own
885                                     replacement.  */
886                                  copy_rtx (reg_sum), 1);
887
888               if (apply_change_group ())
889                 {
890                   rtx *np;
891
892                   /* Delete the reg-reg addition.  */
893                   delete_insn (insn);
894
895                   if (reg_state[regno].offset != const0_rtx)
896                     /* Previous REG_EQUIV / REG_EQUAL notes for PREV
897                        are now invalid.  */
898                     for (np = &REG_NOTES (prev); *np;)
899                       {
900                         if (REG_NOTE_KIND (*np) == REG_EQUAL
901                             || REG_NOTE_KIND (*np) == REG_EQUIV)
902                           *np = XEXP (*np, 1);
903                         else
904                           np = &XEXP (*np, 1);
905                       }
906
907                   reg_state[regno].use_index = RELOAD_COMBINE_MAX_USES;
908                   reg_state[REGNO (const_reg)].store_ruid
909                     = reload_combine_ruid;
910                   continue;
911                 }
912             }
913         }
914
915       note_stores (PATTERN (insn), reload_combine_note_store, NULL);
916
917       if (CALL_P (insn))
918         {
919           rtx link;
920
921           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
922             if (call_used_regs[r])
923               {
924                 reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
925                 reg_state[r].store_ruid = reload_combine_ruid;
926               }
927
928           for (link = CALL_INSN_FUNCTION_USAGE (insn); link;
929                link = XEXP (link, 1))
930             {
931               rtx usage_rtx = XEXP (XEXP (link, 0), 0);
932               if (REG_P (usage_rtx))
933                 {
934                   unsigned int i;
935                   unsigned int start_reg = REGNO (usage_rtx);
936                   unsigned int num_regs =
937                         hard_regno_nregs[start_reg][GET_MODE (usage_rtx)];
938                   unsigned int end_reg  = start_reg + num_regs - 1;
939                   for (i = start_reg; i <= end_reg; i++)
940                     if (GET_CODE (XEXP (link, 0)) == CLOBBER)
941                       {
942                         reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
943                         reg_state[i].store_ruid = reload_combine_ruid;
944                       }
945                     else
946                       reg_state[i].use_index = -1;
947                  }
948              }
949
950         }
951       else if (JUMP_P (insn)
952                && GET_CODE (PATTERN (insn)) != RETURN)
953         {
954           /* Non-spill registers might be used at the call destination in
955              some unknown fashion, so we have to mark the unknown use.  */
956           HARD_REG_SET *live;
957
958           if ((condjump_p (insn) || condjump_in_parallel_p (insn))
959               && JUMP_LABEL (insn))
960             live = &LABEL_LIVE (JUMP_LABEL (insn));
961           else
962             live = &ever_live_at_start;
963
964           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; --i)
965             if (TEST_HARD_REG_BIT (*live, i))
966               reg_state[i].use_index = -1;
967         }
968
969       reload_combine_note_use (&PATTERN (insn), insn);
970       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
971         {
972           if (REG_NOTE_KIND (note) == REG_INC
973               && REG_P (XEXP (note, 0)))
974             {
975               int regno = REGNO (XEXP (note, 0));
976
977               reg_state[regno].store_ruid = reload_combine_ruid;
978               reg_state[regno].use_index = -1;
979             }
980         }
981     }
982
983   free (label_live);
984 }
985
986 /* Check if DST is a register or a subreg of a register; if it is,
987    update reg_state[regno].store_ruid and reg_state[regno].use_index
988    accordingly.  Called via note_stores from reload_combine.  */
989
990 static void
991 reload_combine_note_store (rtx dst, rtx set, void *data ATTRIBUTE_UNUSED)
992 {
993   int regno = 0;
994   int i;
995   enum machine_mode mode = GET_MODE (dst);
996
997   if (GET_CODE (dst) == SUBREG)
998     {
999       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
1000                                    GET_MODE (SUBREG_REG (dst)),
1001                                    SUBREG_BYTE (dst),
1002                                    GET_MODE (dst));
1003       dst = SUBREG_REG (dst);
1004     }
1005   if (!REG_P (dst))
1006     return;
1007   regno += REGNO (dst);
1008
1009   /* note_stores might have stripped a STRICT_LOW_PART, so we have to be
1010      careful with registers / register parts that are not full words.
1011      Similarly for ZERO_EXTRACT.  */
1012   if (GET_CODE (set) != SET
1013       || GET_CODE (SET_DEST (set)) == ZERO_EXTRACT
1014       || GET_CODE (SET_DEST (set)) == STRICT_LOW_PART)
1015     {
1016       for (i = hard_regno_nregs[regno][mode] - 1 + regno; i >= regno; i--)
1017         {
1018           reg_state[i].use_index = -1;
1019           reg_state[i].store_ruid = reload_combine_ruid;
1020         }
1021     }
1022   else
1023     {
1024       for (i = hard_regno_nregs[regno][mode] - 1 + regno; i >= regno; i--)
1025         {
1026           reg_state[i].store_ruid = reload_combine_ruid;
1027           reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
1028         }
1029     }
1030 }
1031
1032 /* XP points to a piece of rtl that has to be checked for any uses of
1033    registers.
1034    *XP is the pattern of INSN, or a part of it.
1035    Called from reload_combine, and recursively by itself.  */
1036 static void
1037 reload_combine_note_use (rtx *xp, rtx insn)
1038 {
1039   rtx x = *xp;
1040   enum rtx_code code = x->code;
1041   const char *fmt;
1042   int i, j;
1043   rtx offset = const0_rtx; /* For the REG case below.  */
1044
1045   switch (code)
1046     {
1047     case SET:
1048       if (REG_P (SET_DEST (x)))
1049         {
1050           reload_combine_note_use (&SET_SRC (x), insn);
1051           return;
1052         }
1053       break;
1054
1055     case USE:
1056       /* If this is the USE of a return value, we can't change it.  */
1057       if (REG_P (XEXP (x, 0)) && REG_FUNCTION_VALUE_P (XEXP (x, 0)))
1058         {
1059         /* Mark the return register as used in an unknown fashion.  */
1060           rtx reg = XEXP (x, 0);
1061           int regno = REGNO (reg);
1062           int nregs = hard_regno_nregs[regno][GET_MODE (reg)];
1063
1064           while (--nregs >= 0)
1065             reg_state[regno + nregs].use_index = -1;
1066           return;
1067         }
1068       break;
1069
1070     case CLOBBER:
1071       if (REG_P (SET_DEST (x)))
1072         {
1073           /* No spurious CLOBBERs of pseudo registers may remain.  */
1074           gcc_assert (REGNO (SET_DEST (x)) < FIRST_PSEUDO_REGISTER);
1075           return;
1076         }
1077       break;
1078
1079     case PLUS:
1080       /* We are interested in (plus (reg) (const_int)) .  */
1081       if (!REG_P (XEXP (x, 0))
1082           || GET_CODE (XEXP (x, 1)) != CONST_INT)
1083         break;
1084       offset = XEXP (x, 1);
1085       x = XEXP (x, 0);
1086       /* Fall through.  */
1087     case REG:
1088       {
1089         int regno = REGNO (x);
1090         int use_index;
1091         int nregs;
1092
1093         /* No spurious USEs of pseudo registers may remain.  */
1094         gcc_assert (regno < FIRST_PSEUDO_REGISTER);
1095
1096         nregs = hard_regno_nregs[regno][GET_MODE (x)];
1097
1098         /* We can't substitute into multi-hard-reg uses.  */
1099         if (nregs > 1)
1100           {
1101             while (--nregs >= 0)
1102               reg_state[regno + nregs].use_index = -1;
1103             return;
1104           }
1105
1106         /* If this register is already used in some unknown fashion, we
1107            can't do anything.
1108            If we decrement the index from zero to -1, we can't store more
1109            uses, so this register becomes used in an unknown fashion.  */
1110         use_index = --reg_state[regno].use_index;
1111         if (use_index < 0)
1112           return;
1113
1114         if (use_index != RELOAD_COMBINE_MAX_USES - 1)
1115           {
1116             /* We have found another use for a register that is already
1117                used later.  Check if the offsets match; if not, mark the
1118                register as used in an unknown fashion.  */
1119             if (! rtx_equal_p (offset, reg_state[regno].offset))
1120               {
1121                 reg_state[regno].use_index = -1;
1122                 return;
1123               }
1124           }
1125         else
1126           {
1127             /* This is the first use of this register we have seen since we
1128                marked it as dead.  */
1129             reg_state[regno].offset = offset;
1130             reg_state[regno].use_ruid = reload_combine_ruid;
1131           }
1132         reg_state[regno].reg_use[use_index].insn = insn;
1133         reg_state[regno].reg_use[use_index].usep = xp;
1134         return;
1135       }
1136
1137     default:
1138       break;
1139     }
1140
1141   /* Recursively process the components of X.  */
1142   fmt = GET_RTX_FORMAT (code);
1143   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1144     {
1145       if (fmt[i] == 'e')
1146         reload_combine_note_use (&XEXP (x, i), insn);
1147       else if (fmt[i] == 'E')
1148         {
1149           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1150             reload_combine_note_use (&XVECEXP (x, i, j), insn);
1151         }
1152     }
1153 }
1154 \f
1155 /* See if we can reduce the cost of a constant by replacing a move
1156    with an add.  We track situations in which a register is set to a
1157    constant or to a register plus a constant.  */
1158 /* We cannot do our optimization across labels.  Invalidating all the
1159    information about register contents we have would be costly, so we
1160    use move2add_last_label_luid to note where the label is and then
1161    later disable any optimization that would cross it.
1162    reg_offset[n] / reg_base_reg[n] / reg_mode[n] are only valid if
1163    reg_set_luid[n] is greater than move2add_last_label_luid.  */
1164 static int reg_set_luid[FIRST_PSEUDO_REGISTER];
1165
1166 /* If reg_base_reg[n] is negative, register n has been set to
1167    reg_offset[n] in mode reg_mode[n] .
1168    If reg_base_reg[n] is non-negative, register n has been set to the
1169    sum of reg_offset[n] and the value of register reg_base_reg[n]
1170    before reg_set_luid[n], calculated in mode reg_mode[n] .  */
1171 static HOST_WIDE_INT reg_offset[FIRST_PSEUDO_REGISTER];
1172 static int reg_base_reg[FIRST_PSEUDO_REGISTER];
1173 static enum machine_mode reg_mode[FIRST_PSEUDO_REGISTER];
1174
1175 /* move2add_luid is linearly increased while scanning the instructions
1176    from first to last.  It is used to set reg_set_luid in
1177    reload_cse_move2add and move2add_note_store.  */
1178 static int move2add_luid;
1179
1180 /* move2add_last_label_luid is set whenever a label is found.  Labels
1181    invalidate all previously collected reg_offset data.  */
1182 static int move2add_last_label_luid;
1183
1184 /* ??? We don't know how zero / sign extension is handled, hence we
1185    can't go from a narrower to a wider mode.  */
1186 #define MODES_OK_FOR_MOVE2ADD(OUTMODE, INMODE) \
1187   (GET_MODE_SIZE (OUTMODE) == GET_MODE_SIZE (INMODE) \
1188    || (GET_MODE_SIZE (OUTMODE) <= GET_MODE_SIZE (INMODE) \
1189        && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (OUTMODE), \
1190                                  GET_MODE_BITSIZE (INMODE))))
1191
1192 static void
1193 reload_cse_move2add (rtx first)
1194 {
1195   int i;
1196   rtx insn;
1197
1198   for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1199     reg_set_luid[i] = 0;
1200
1201   move2add_last_label_luid = 0;
1202   move2add_luid = 2;
1203   for (insn = first; insn; insn = NEXT_INSN (insn), move2add_luid++)
1204     {
1205       rtx pat, note;
1206
1207       if (LABEL_P (insn))
1208         {
1209           move2add_last_label_luid = move2add_luid;
1210           /* We're going to increment move2add_luid twice after a
1211              label, so that we can use move2add_last_label_luid + 1 as
1212              the luid for constants.  */
1213           move2add_luid++;
1214           continue;
1215         }
1216       if (! INSN_P (insn))
1217         continue;
1218       pat = PATTERN (insn);
1219       /* For simplicity, we only perform this optimization on
1220          straightforward SETs.  */
1221       if (GET_CODE (pat) == SET
1222           && REG_P (SET_DEST (pat)))
1223         {
1224           rtx reg = SET_DEST (pat);
1225           int regno = REGNO (reg);
1226           rtx src = SET_SRC (pat);
1227
1228           /* Check if we have valid information on the contents of this
1229              register in the mode of REG.  */
1230           if (reg_set_luid[regno] > move2add_last_label_luid
1231               && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg), reg_mode[regno]))
1232             {
1233               /* Try to transform (set (REGX) (CONST_INT A))
1234                                   ...
1235                                   (set (REGX) (CONST_INT B))
1236                  to
1237                                   (set (REGX) (CONST_INT A))
1238                                   ...
1239                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))
1240                  or
1241                                   (set (REGX) (CONST_INT A))
1242                                   ...
1243                                   (set (STRICT_LOW_PART (REGX)) (CONST_INT B))
1244               */
1245
1246               if (GET_CODE (src) == CONST_INT && reg_base_reg[regno] < 0)
1247                 {
1248                   rtx new_src = gen_int_mode (INTVAL (src) - reg_offset[regno],
1249                                               GET_MODE (reg));
1250                   /* (set (reg) (plus (reg) (const_int 0))) is not canonical;
1251                      use (set (reg) (reg)) instead.
1252                      We don't delete this insn, nor do we convert it into a
1253                      note, to avoid losing register notes or the return
1254                      value flag.  jump2 already knows how to get rid of
1255                      no-op moves.  */
1256                   if (new_src == const0_rtx)
1257                     {
1258                       /* If the constants are different, this is a
1259                          truncation, that, if turned into (set (reg)
1260                          (reg)), would be discarded.  Maybe we should
1261                          try a truncMN pattern?  */
1262                       if (INTVAL (src) == reg_offset [regno])
1263                         validate_change (insn, &SET_SRC (pat), reg, 0);
1264                     }
1265                   else if (rtx_cost (new_src, PLUS) < rtx_cost (src, SET)
1266                            && have_add2_insn (reg, new_src))
1267                     {
1268                       rtx tem = gen_rtx_PLUS (GET_MODE (reg), reg, new_src);
1269                       validate_change (insn, &SET_SRC (pat), tem, 0);
1270                     }
1271                   else if (GET_MODE (reg) != BImode)
1272                     {
1273                       enum machine_mode narrow_mode;
1274                       for (narrow_mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
1275                            narrow_mode != VOIDmode
1276                            && narrow_mode != GET_MODE (reg);
1277                            narrow_mode = GET_MODE_WIDER_MODE (narrow_mode))
1278                         {
1279                           if (have_insn_for (STRICT_LOW_PART, narrow_mode)
1280                               && ((reg_offset[regno]
1281                                    & ~GET_MODE_MASK (narrow_mode))
1282                                   == (INTVAL (src)
1283                                       & ~GET_MODE_MASK (narrow_mode))))
1284                             {
1285                               rtx narrow_reg = gen_rtx_REG (narrow_mode,
1286                                                             REGNO (reg));
1287                               rtx narrow_src = gen_int_mode (INTVAL (src),
1288                                                              narrow_mode);
1289                               rtx new_set =
1290                                 gen_rtx_SET (VOIDmode,
1291                                              gen_rtx_STRICT_LOW_PART (VOIDmode,
1292                                                                       narrow_reg),
1293                                              narrow_src);
1294                               if (validate_change (insn, &PATTERN (insn),
1295                                                    new_set, 0))
1296                                 break;
1297                             }
1298                         }
1299                     }
1300                   reg_set_luid[regno] = move2add_luid;
1301                   reg_mode[regno] = GET_MODE (reg);
1302                   reg_offset[regno] = INTVAL (src);
1303                   continue;
1304                 }
1305
1306               /* Try to transform (set (REGX) (REGY))
1307                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1308                                   ...
1309                                   (set (REGX) (REGY))
1310                                   (set (REGX) (PLUS (REGX) (CONST_INT B)))
1311                  to
1312                                   (set (REGX) (REGY))
1313                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1314                                   ...
1315                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))  */
1316               else if (REG_P (src)
1317                        && reg_set_luid[regno] == reg_set_luid[REGNO (src)]
1318                        && reg_base_reg[regno] == reg_base_reg[REGNO (src)]
1319                        && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg),
1320                                                  reg_mode[REGNO (src)]))
1321                 {
1322                   rtx next = next_nonnote_insn (insn);
1323                   rtx set = NULL_RTX;
1324                   if (next)
1325                     set = single_set (next);
1326                   if (set
1327                       && SET_DEST (set) == reg
1328                       && GET_CODE (SET_SRC (set)) == PLUS
1329                       && XEXP (SET_SRC (set), 0) == reg
1330                       && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1331                     {
1332                       rtx src3 = XEXP (SET_SRC (set), 1);
1333                       HOST_WIDE_INT added_offset = INTVAL (src3);
1334                       HOST_WIDE_INT base_offset = reg_offset[REGNO (src)];
1335                       HOST_WIDE_INT regno_offset = reg_offset[regno];
1336                       rtx new_src =
1337                         gen_int_mode (added_offset
1338                                       + base_offset
1339                                       - regno_offset,
1340                                       GET_MODE (reg));
1341                       int success = 0;
1342
1343                       if (new_src == const0_rtx)
1344                         /* See above why we create (set (reg) (reg)) here.  */
1345                         success
1346                           = validate_change (next, &SET_SRC (set), reg, 0);
1347                       else if ((rtx_cost (new_src, PLUS)
1348                                 < COSTS_N_INSNS (1) + rtx_cost (src3, SET))
1349                                && have_add2_insn (reg, new_src))
1350                         {
1351                           rtx newpat = gen_rtx_SET (VOIDmode,
1352                                                     reg,
1353                                                     gen_rtx_PLUS (GET_MODE (reg),
1354                                                                   reg,
1355                                                                   new_src));
1356                           success
1357                             = validate_change (next, &PATTERN (next),
1358                                                newpat, 0);
1359                         }
1360                       if (success)
1361                         delete_insn (insn);
1362                       insn = next;
1363                       reg_mode[regno] = GET_MODE (reg);
1364                       reg_offset[regno] =
1365                         trunc_int_for_mode (added_offset + base_offset,
1366                                             GET_MODE (reg));
1367                       continue;
1368                     }
1369                 }
1370             }
1371         }
1372
1373       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1374         {
1375           if (REG_NOTE_KIND (note) == REG_INC
1376               && REG_P (XEXP (note, 0)))
1377             {
1378               /* Reset the information about this register.  */
1379               int regno = REGNO (XEXP (note, 0));
1380               if (regno < FIRST_PSEUDO_REGISTER)
1381                 reg_set_luid[regno] = 0;
1382             }
1383         }
1384       note_stores (PATTERN (insn), move2add_note_store, NULL);
1385
1386       /* If INSN is a conditional branch, we try to extract an
1387          implicit set out of it.  */
1388       if (any_condjump_p (insn))
1389         {
1390           rtx cnd = fis_get_condition (insn);
1391
1392           if (cnd != NULL_RTX
1393               && GET_CODE (cnd) == NE
1394               && REG_P (XEXP (cnd, 0))
1395               && !reg_set_p (XEXP (cnd, 0), insn)
1396               /* The following two checks, which are also in
1397                  move2add_note_store, are intended to reduce the
1398                  number of calls to gen_rtx_SET to avoid memory
1399                  allocation if possible.  */
1400               && SCALAR_INT_MODE_P (GET_MODE (XEXP (cnd, 0)))
1401               && hard_regno_nregs[REGNO (XEXP (cnd, 0))][GET_MODE (XEXP (cnd, 0))] == 1
1402               && GET_CODE (XEXP (cnd, 1)) == CONST_INT)
1403             {
1404               rtx implicit_set =
1405                 gen_rtx_SET (VOIDmode, XEXP (cnd, 0), XEXP (cnd, 1));
1406               move2add_note_store (SET_DEST (implicit_set), implicit_set, 0);
1407             }
1408         }
1409
1410       /* If this is a CALL_INSN, all call used registers are stored with
1411          unknown values.  */
1412       if (CALL_P (insn))
1413         {
1414           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1415             {
1416               if (call_used_regs[i])
1417                 /* Reset the information about this register.  */
1418                 reg_set_luid[i] = 0;
1419             }
1420         }
1421     }
1422 }
1423
1424 /* SET is a SET or CLOBBER that sets DST.
1425    Update reg_set_luid, reg_offset and reg_base_reg accordingly.
1426    Called from reload_cse_move2add via note_stores.  */
1427
1428 static void
1429 move2add_note_store (rtx dst, rtx set, void *data ATTRIBUTE_UNUSED)
1430 {
1431   unsigned int regno = 0;
1432   unsigned int nregs = 0;
1433   unsigned int i;
1434   enum machine_mode mode = GET_MODE (dst);
1435
1436   if (GET_CODE (dst) == SUBREG)
1437     {
1438       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
1439                                    GET_MODE (SUBREG_REG (dst)),
1440                                    SUBREG_BYTE (dst),
1441                                    GET_MODE (dst));
1442       nregs = subreg_nregs (dst);
1443       dst = SUBREG_REG (dst);
1444     }
1445
1446   /* Some targets do argument pushes without adding REG_INC notes.  */
1447
1448   if (MEM_P (dst))
1449     {
1450       dst = XEXP (dst, 0);
1451       if (GET_CODE (dst) == PRE_INC || GET_CODE (dst) == POST_INC
1452           || GET_CODE (dst) == PRE_DEC || GET_CODE (dst) == POST_DEC)
1453         reg_set_luid[REGNO (XEXP (dst, 0))] = 0;
1454       return;
1455     }
1456   if (!REG_P (dst))
1457     return;
1458
1459   regno += REGNO (dst);
1460   if (!nregs)
1461     nregs = hard_regno_nregs[regno][mode];
1462
1463   if (SCALAR_INT_MODE_P (GET_MODE (dst))
1464       && nregs == 1 && GET_CODE (set) == SET
1465       && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
1466       && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
1467     {
1468       rtx src = SET_SRC (set);
1469       rtx base_reg;
1470       HOST_WIDE_INT offset;
1471       int base_regno;
1472       /* This may be different from mode, if SET_DEST (set) is a
1473          SUBREG.  */
1474       enum machine_mode dst_mode = GET_MODE (dst);
1475
1476       switch (GET_CODE (src))
1477         {
1478         case PLUS:
1479           if (REG_P (XEXP (src, 0)))
1480             {
1481               base_reg = XEXP (src, 0);
1482
1483               if (GET_CODE (XEXP (src, 1)) == CONST_INT)
1484                 offset = INTVAL (XEXP (src, 1));
1485               else if (REG_P (XEXP (src, 1))
1486                        && (reg_set_luid[REGNO (XEXP (src, 1))]
1487                            > move2add_last_label_luid)
1488                        && (MODES_OK_FOR_MOVE2ADD
1489                            (dst_mode, reg_mode[REGNO (XEXP (src, 1))])))
1490                 {
1491                   if (reg_base_reg[REGNO (XEXP (src, 1))] < 0)
1492                     offset = reg_offset[REGNO (XEXP (src, 1))];
1493                   /* Maybe the first register is known to be a
1494                      constant.  */
1495                   else if (reg_set_luid[REGNO (base_reg)]
1496                            > move2add_last_label_luid
1497                            && (MODES_OK_FOR_MOVE2ADD
1498                                (dst_mode, reg_mode[REGNO (XEXP (src, 1))]))
1499                            && reg_base_reg[REGNO (base_reg)] < 0)
1500                     {
1501                       offset = reg_offset[REGNO (base_reg)];
1502                       base_reg = XEXP (src, 1);
1503                     }
1504                   else
1505                     goto invalidate;
1506                 }
1507               else
1508                 goto invalidate;
1509
1510               break;
1511             }
1512
1513           goto invalidate;
1514
1515         case REG:
1516           base_reg = src;
1517           offset = 0;
1518           break;
1519
1520         case CONST_INT:
1521           /* Start tracking the register as a constant.  */
1522           reg_base_reg[regno] = -1;
1523           reg_offset[regno] = INTVAL (SET_SRC (set));
1524           /* We assign the same luid to all registers set to constants.  */
1525           reg_set_luid[regno] = move2add_last_label_luid + 1;
1526           reg_mode[regno] = mode;
1527           return;
1528
1529         default:
1530         invalidate:
1531           /* Invalidate the contents of the register.  */
1532           reg_set_luid[regno] = 0;
1533           return;
1534         }
1535
1536       base_regno = REGNO (base_reg);
1537       /* If information about the base register is not valid, set it
1538          up as a new base register, pretending its value is known
1539          starting from the current insn.  */
1540       if (reg_set_luid[base_regno] <= move2add_last_label_luid)
1541         {
1542           reg_base_reg[base_regno] = base_regno;
1543           reg_offset[base_regno] = 0;
1544           reg_set_luid[base_regno] = move2add_luid;
1545           reg_mode[base_regno] = mode;
1546         }
1547       else if (! MODES_OK_FOR_MOVE2ADD (dst_mode,
1548                                         reg_mode[base_regno]))
1549         goto invalidate;
1550
1551       reg_mode[regno] = mode;
1552
1553       /* Copy base information from our base register.  */
1554       reg_set_luid[regno] = reg_set_luid[base_regno];
1555       reg_base_reg[regno] = reg_base_reg[base_regno];
1556
1557       /* Compute the sum of the offsets or constants.  */
1558       reg_offset[regno] = trunc_int_for_mode (offset
1559                                               + reg_offset[base_regno],
1560                                               dst_mode);
1561     }
1562   else
1563     {
1564       unsigned int endregno = regno + nregs;
1565
1566       for (i = regno; i < endregno; i++)
1567         /* Reset the information about this register.  */
1568         reg_set_luid[i] = 0;
1569     }
1570 }
1571 \f
1572 static bool
1573 gate_handle_postreload (void)
1574 {
1575   return (optimize > 0);
1576 }
1577
1578
1579 static unsigned int
1580 rest_of_handle_postreload (void)
1581 {
1582   /* Do a very simple CSE pass over just the hard registers.  */
1583   reload_cse_regs (get_insns ());
1584   /* reload_cse_regs can eliminate potentially-trapping MEMs.
1585      Remove any EH edges associated with them.  */
1586   if (flag_non_call_exceptions)
1587     purge_all_dead_edges ();
1588   return 0;
1589 }
1590
1591 struct tree_opt_pass pass_postreload_cse =
1592 {
1593   "postreload",                         /* name */
1594   gate_handle_postreload,               /* gate */
1595   rest_of_handle_postreload,            /* execute */
1596   NULL,                                 /* sub */
1597   NULL,                                 /* next */
1598   0,                                    /* static_pass_number */
1599   TV_RELOAD_CSE_REGS,                   /* tv_id */
1600   0,                                    /* properties_required */
1601   0,                                    /* properties_provided */
1602   0,                                    /* properties_destroyed */
1603   0,                                    /* todo_flags_start */
1604   TODO_dump_func,                       /* todo_flags_finish */
1605   'o'                                   /* letter */
1606 };
1607