OSDN Git Service

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