OSDN Git Service

835a7218b364514768990e93b6b0922f76dc20ee
[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 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
392       CLEAR_HARD_REG_SET (equiv_regs[i]);
393
394       /* cselib blows up on CODE_LABELs.  Trying to fix that doesn't seem
395          right, so avoid the problem here.  Likewise if we have a constant
396          and the insn pattern doesn't tell us the mode we need.  */
397       if (GET_CODE (recog_data.operand[i]) == CODE_LABEL
398           || (CONSTANT_P (recog_data.operand[i])
399               && recog_data.operand_mode[i] == VOIDmode))
400         continue;
401
402       v = cselib_lookup (recog_data.operand[i], recog_data.operand_mode[i], 0);
403       if (! v)
404         continue;
405
406       for (l = v->locs; l; l = l->next)
407         if (GET_CODE (l->loc) == REG)
408           SET_HARD_REG_BIT (equiv_regs[i], REGNO (l->loc));
409     }
410
411   for (i = 0; i < recog_data.n_operands; i++)
412     {
413       enum machine_mode mode;
414       int regno;
415       const char *p;
416
417       op_alt_regno[i] = alloca (recog_data.n_alternatives * sizeof (int));
418       for (j = 0; j < recog_data.n_alternatives; j++)
419         op_alt_regno[i][j] = -1;
420
421       p = constraints[i] = recog_data.constraints[i];
422       mode = recog_data.operand_mode[i];
423
424       /* Add the reject values for each alternative given by the constraints
425          for this operand.  */
426       j = 0;
427       while (*p != '\0')
428         {
429           char c = *p++;
430           if (c == ',')
431             j++;
432           else if (c == '?')
433             alternative_reject[j] += 3;
434           else if (c == '!')
435             alternative_reject[j] += 300;
436         }
437
438       /* We won't change operands which are already registers.  We
439          also don't want to modify output operands.  */
440       regno = true_regnum (recog_data.operand[i]);
441       if (regno >= 0
442           || constraints[i][0] == '='
443           || constraints[i][0] == '+')
444         continue;
445
446       for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
447         {
448           int class = (int) NO_REGS;
449
450           if (! TEST_HARD_REG_BIT (equiv_regs[i], regno))
451             continue;
452
453           REGNO (testreg) = regno;
454           PUT_MODE (testreg, mode);
455
456           /* We found a register equal to this operand.  Now look for all
457              alternatives that can accept this register and have not been
458              assigned a register they can use yet.  */
459           j = 0;
460           p = constraints[i];
461           for (;;)
462             {
463               char c = *p;
464
465               switch (c)
466                 {
467                 case '=':  case '+':  case '?':
468                 case '#':  case '&':  case '!':
469                 case '*':  case '%':
470                 case '0':  case '1':  case '2':  case '3':  case '4':
471                 case '5':  case '6':  case '7':  case '8':  case '9':
472                 case 'm':  case '<':  case '>':  case 'V':  case 'o':
473                 case 'E':  case 'F':  case 'G':  case 'H':
474                 case 's':  case 'i':  case 'n':
475                 case 'I':  case 'J':  case 'K':  case 'L':
476                 case 'M':  case 'N':  case 'O':  case 'P':
477                 case 'p': case 'X':
478                   /* These don't say anything we care about.  */
479                   break;
480
481                 case 'g': case 'r':
482                   class = reg_class_subunion[(int) class][(int) GENERAL_REGS];
483                   break;
484
485                 default:
486                   class
487                     = (reg_class_subunion
488                        [(int) class]
489                        [(int) REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p)]);
490                   break;
491
492                 case ',': case '\0':
493                   /* See if REGNO fits this alternative, and set it up as the
494                      replacement register if we don't have one for this
495                      alternative yet and the operand being replaced is not
496                      a cheap CONST_INT.  */
497                   if (op_alt_regno[i][j] == -1
498                       && reg_fits_class_p (testreg, class, 0, mode)
499                       && (GET_CODE (recog_data.operand[i]) != CONST_INT
500                           || (rtx_cost (recog_data.operand[i], SET)
501                               > rtx_cost (testreg, SET))))
502                     {
503                       alternative_nregs[j]++;
504                       op_alt_regno[i][j] = regno;
505                     }
506                   j++;
507                   break;
508                 }
509               p += CONSTRAINT_LEN (c, p);
510
511               if (c == '\0')
512                 break;
513             }
514         }
515     }
516
517   /* Record all alternatives which are better or equal to the currently
518      matching one in the alternative_order array.  */
519   for (i = j = 0; i < recog_data.n_alternatives; i++)
520     if (alternative_reject[i] <= alternative_reject[which_alternative])
521       alternative_order[j++] = i;
522   recog_data.n_alternatives = j;
523
524   /* Sort it.  Given a small number of alternatives, a dumb algorithm
525      won't hurt too much.  */
526   for (i = 0; i < recog_data.n_alternatives - 1; i++)
527     {
528       int best = i;
529       int best_reject = alternative_reject[alternative_order[i]];
530       int best_nregs = alternative_nregs[alternative_order[i]];
531       int tmp;
532
533       for (j = i + 1; j < recog_data.n_alternatives; j++)
534         {
535           int this_reject = alternative_reject[alternative_order[j]];
536           int this_nregs = alternative_nregs[alternative_order[j]];
537
538           if (this_reject < best_reject
539               || (this_reject == best_reject && this_nregs < best_nregs))
540             {
541               best = j;
542               best_reject = this_reject;
543               best_nregs = this_nregs;
544             }
545         }
546
547       tmp = alternative_order[best];
548       alternative_order[best] = alternative_order[i];
549       alternative_order[i] = tmp;
550     }
551
552   /* Substitute the operands as determined by op_alt_regno for the best
553      alternative.  */
554   j = alternative_order[0];
555
556   for (i = 0; i < recog_data.n_operands; i++)
557     {
558       enum machine_mode mode = recog_data.operand_mode[i];
559       if (op_alt_regno[i][j] == -1)
560         continue;
561
562       validate_change (insn, recog_data.operand_loc[i],
563                        gen_rtx_REG (mode, op_alt_regno[i][j]), 1);
564     }
565
566   for (i = recog_data.n_dups - 1; i >= 0; i--)
567     {
568       int op = recog_data.dup_num[i];
569       enum machine_mode mode = recog_data.operand_mode[op];
570
571       if (op_alt_regno[op][j] == -1)
572         continue;
573
574       validate_change (insn, recog_data.dup_loc[i],
575                        gen_rtx_REG (mode, op_alt_regno[op][j]), 1);
576     }
577
578   return apply_change_group ();
579 }
580 \f
581 /* If reload couldn't use reg+reg+offset addressing, try to use reg+reg
582    addressing now.
583    This code might also be useful when reload gave up on reg+reg addressing
584    because of clashes between the return register and INDEX_REG_CLASS.  */
585
586 /* The maximum number of uses of a register we can keep track of to
587    replace them with reg+reg addressing.  */
588 #define RELOAD_COMBINE_MAX_USES 6
589
590 /* INSN is the insn where a register has ben used, and USEP points to the
591    location of the register within the rtl.  */
592 struct reg_use { rtx insn, *usep; };
593
594 /* If the register is used in some unknown fashion, USE_INDEX is negative.
595    If it is dead, USE_INDEX is RELOAD_COMBINE_MAX_USES, and STORE_RUID
596    indicates where it becomes live again.
597    Otherwise, USE_INDEX is the index of the last encountered use of the
598    register (which is first among these we have seen since we scan backwards),
599    OFFSET contains the constant offset that is added to the register in
600    all encountered uses, and USE_RUID indicates the first encountered, i.e.
601    last, of these uses.
602    STORE_RUID is always meaningful if we only want to use a value in a
603    register in a different place: it denotes the next insn in the insn
604    stream (i.e. the last encountered) that sets or clobbers the register.  */
605 static struct
606   {
607     struct reg_use reg_use[RELOAD_COMBINE_MAX_USES];
608     int use_index;
609     rtx offset;
610     int store_ruid;
611     int use_ruid;
612   } reg_state[FIRST_PSEUDO_REGISTER];
613
614 /* Reverse linear uid.  This is increased in reload_combine while scanning
615    the instructions from last to first.  It is used to set last_label_ruid
616    and the store_ruid / use_ruid fields in reg_state.  */
617 static int reload_combine_ruid;
618
619 #define LABEL_LIVE(LABEL) \
620   (label_live[CODE_LABEL_NUMBER (LABEL) - min_labelno])
621
622 static void
623 reload_combine (void)
624 {
625   rtx insn, set;
626   int first_index_reg = -1;
627   int last_index_reg = 0;
628   int i;
629   basic_block bb;
630   unsigned int r;
631   int last_label_ruid;
632   int min_labelno, n_labels;
633   HARD_REG_SET ever_live_at_start, *label_live;
634
635   /* If reg+reg can be used in offsetable memory addresses, the main chunk of
636      reload has already used it where appropriate, so there is no use in
637      trying to generate it now.  */
638   if (double_reg_address_ok && INDEX_REG_CLASS != NO_REGS)
639     return;
640
641   /* To avoid wasting too much time later searching for an index register,
642      determine the minimum and maximum index register numbers.  */
643   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
644     if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], r))
645       {
646         if (first_index_reg == -1)
647           first_index_reg = r;
648
649         last_index_reg = r;
650       }
651
652   /* If no index register is available, we can quit now.  */
653   if (first_index_reg == -1)
654     return;
655
656   /* Set up LABEL_LIVE and EVER_LIVE_AT_START.  The register lifetime
657      information is a bit fuzzy immediately after reload, but it's
658      still good enough to determine which registers are live at a jump
659      destination.  */
660   min_labelno = get_first_label_num ();
661   n_labels = max_label_num () - min_labelno;
662   label_live = xmalloc (n_labels * sizeof (HARD_REG_SET));
663   CLEAR_HARD_REG_SET (ever_live_at_start);
664
665   FOR_EACH_BB_REVERSE (bb)
666     {
667       insn = BB_HEAD (bb);
668       if (GET_CODE (insn) == CODE_LABEL)
669         {
670           HARD_REG_SET live;
671
672           REG_SET_TO_HARD_REG_SET (live,
673                                    bb->global_live_at_start);
674           compute_use_by_pseudos (&live,
675                                   bb->global_live_at_start);
676           COPY_HARD_REG_SET (LABEL_LIVE (insn), live);
677           IOR_HARD_REG_SET (ever_live_at_start, live);
678         }
679     }
680
681   /* Initialize last_label_ruid, reload_combine_ruid and reg_state.  */
682   last_label_ruid = reload_combine_ruid = 0;
683   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
684     {
685       reg_state[r].store_ruid = reload_combine_ruid;
686       if (fixed_regs[r])
687         reg_state[r].use_index = -1;
688       else
689         reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
690     }
691
692   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
693     {
694       rtx note;
695
696       /* We cannot do our optimization across labels.  Invalidating all the use
697          information we have would be costly, so we just note where the label
698          is and then later disable any optimization that would cross it.  */
699       if (GET_CODE (insn) == CODE_LABEL)
700         last_label_ruid = reload_combine_ruid;
701       else if (GET_CODE (insn) == BARRIER)
702         for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
703           if (! fixed_regs[r])
704               reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
705
706       if (! INSN_P (insn))
707         continue;
708
709       reload_combine_ruid++;
710
711       /* Look for (set (REGX) (CONST_INT))
712          (set (REGX) (PLUS (REGX) (REGY)))
713          ...
714          ... (MEM (REGX)) ...
715          and convert it to
716          (set (REGZ) (CONST_INT))
717          ...
718          ... (MEM (PLUS (REGZ) (REGY)))... .
719
720          First, check that we have (set (REGX) (PLUS (REGX) (REGY)))
721          and that we know all uses of REGX before it dies.  
722          Also, explicitly check that REGX != REGY; our life information
723          does not yet show whether REGY changes in this insn.  */
724       set = single_set (insn);
725       if (set != NULL_RTX
726           && GET_CODE (SET_DEST (set)) == REG
727           && (HARD_REGNO_NREGS (REGNO (SET_DEST (set)),
728                                 GET_MODE (SET_DEST (set)))
729               == 1)
730           && GET_CODE (SET_SRC (set)) == PLUS
731           && GET_CODE (XEXP (SET_SRC (set), 1)) == REG
732           && rtx_equal_p (XEXP (SET_SRC (set), 0), SET_DEST (set))
733           && !rtx_equal_p (XEXP (SET_SRC (set), 1), SET_DEST (set))
734           && last_label_ruid < reg_state[REGNO (SET_DEST (set))].use_ruid)
735         {
736           rtx reg = SET_DEST (set);
737           rtx plus = SET_SRC (set);
738           rtx base = XEXP (plus, 1);
739           rtx prev = prev_nonnote_insn (insn);
740           rtx prev_set = prev ? single_set (prev) : NULL_RTX;
741           unsigned int regno = REGNO (reg);
742           rtx const_reg = NULL_RTX;
743           rtx reg_sum = NULL_RTX;
744
745           /* Now, we need an index register.
746              We'll set index_reg to this index register, const_reg to the
747              register that is to be loaded with the constant
748              (denoted as REGZ in the substitution illustration above),
749              and reg_sum to the register-register that we want to use to
750              substitute uses of REG (typically in MEMs) with.
751              First check REG and BASE for being index registers;
752              we can use them even if they are not dead.  */
753           if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS], regno)
754               || TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS],
755                                     REGNO (base)))
756             {
757               const_reg = reg;
758               reg_sum = plus;
759             }
760           else
761             {
762               /* Otherwise, look for a free index register.  Since we have
763                  checked above that neither REG nor BASE are index registers,
764                  if we find anything at all, it will be different from these
765                  two registers.  */
766               for (i = first_index_reg; i <= last_index_reg; i++)
767                 {
768                   if (TEST_HARD_REG_BIT (reg_class_contents[INDEX_REG_CLASS],
769                                          i)
770                       && reg_state[i].use_index == RELOAD_COMBINE_MAX_USES
771                       && reg_state[i].store_ruid <= reg_state[regno].use_ruid
772                       && HARD_REGNO_NREGS (i, GET_MODE (reg)) == 1)
773                     {
774                       rtx index_reg = gen_rtx_REG (GET_MODE (reg), i);
775
776                       const_reg = index_reg;
777                       reg_sum = gen_rtx_PLUS (GET_MODE (reg), index_reg, base);
778                       break;
779                     }
780                 }
781             }
782
783           /* Check that PREV_SET is indeed (set (REGX) (CONST_INT)) and that
784              (REGY), i.e. BASE, is not clobbered before the last use we'll
785              create.  */
786           if (prev_set != 0
787               && GET_CODE (SET_SRC (prev_set)) == CONST_INT
788               && rtx_equal_p (SET_DEST (prev_set), reg)
789               && reg_state[regno].use_index >= 0
790               && (reg_state[REGNO (base)].store_ruid
791                   <= reg_state[regno].use_ruid)
792               && reg_sum != 0)
793             {
794               int i;
795
796               /* Change destination register and, if necessary, the
797                  constant value in PREV, the constant loading instruction.  */
798               validate_change (prev, &SET_DEST (prev_set), const_reg, 1);
799               if (reg_state[regno].offset != const0_rtx)
800                 validate_change (prev,
801                                  &SET_SRC (prev_set),
802                                  GEN_INT (INTVAL (SET_SRC (prev_set))
803                                           + INTVAL (reg_state[regno].offset)),
804                                  1);
805
806               /* Now for every use of REG that we have recorded, replace REG
807                  with REG_SUM.  */
808               for (i = reg_state[regno].use_index;
809                    i < RELOAD_COMBINE_MAX_USES; i++)
810                 validate_change (reg_state[regno].reg_use[i].insn,
811                                  reg_state[regno].reg_use[i].usep,
812                                  /* Each change must have its own
813                                     replacement.  */
814                                  copy_rtx (reg_sum), 1);
815
816               if (apply_change_group ())
817                 {
818                   rtx *np;
819
820                   /* Delete the reg-reg addition.  */
821                   delete_insn (insn);
822
823                   if (reg_state[regno].offset != const0_rtx)
824                     /* Previous REG_EQUIV / REG_EQUAL notes for PREV
825                        are now invalid.  */
826                     for (np = &REG_NOTES (prev); *np;)
827                       {
828                         if (REG_NOTE_KIND (*np) == REG_EQUAL
829                             || REG_NOTE_KIND (*np) == REG_EQUIV)
830                           *np = XEXP (*np, 1);
831                         else
832                           np = &XEXP (*np, 1);
833                       }
834
835                   reg_state[regno].use_index = RELOAD_COMBINE_MAX_USES;
836                   reg_state[REGNO (const_reg)].store_ruid
837                     = reload_combine_ruid;
838                   continue;
839                 }
840             }
841         }
842
843       note_stores (PATTERN (insn), reload_combine_note_store, NULL);
844
845       if (GET_CODE (insn) == CALL_INSN)
846         {
847           rtx link;
848
849           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
850             if (call_used_regs[r])
851               {
852                 reg_state[r].use_index = RELOAD_COMBINE_MAX_USES;
853                 reg_state[r].store_ruid = reload_combine_ruid;
854               }
855
856           for (link = CALL_INSN_FUNCTION_USAGE (insn); link;
857                link = XEXP (link, 1))
858             {
859               rtx usage_rtx = XEXP (XEXP (link, 0), 0);
860               if (GET_CODE (usage_rtx) == REG)
861                 {
862                   unsigned int i;
863                   unsigned int start_reg = REGNO (usage_rtx);
864                   unsigned int num_regs =
865                         HARD_REGNO_NREGS (start_reg, GET_MODE (usage_rtx));
866                   unsigned int end_reg  = start_reg + num_regs - 1;
867                   for (i = start_reg; i <= end_reg; i++)
868                     if (GET_CODE (XEXP (link, 0)) == CLOBBER)
869                       {
870                         reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
871                         reg_state[i].store_ruid = reload_combine_ruid;
872                       }
873                     else
874                       reg_state[i].use_index = -1;
875                  }
876              }
877
878         }
879       else if (GET_CODE (insn) == JUMP_INSN
880                && GET_CODE (PATTERN (insn)) != RETURN)
881         {
882           /* Non-spill registers might be used at the call destination in
883              some unknown fashion, so we have to mark the unknown use.  */
884           HARD_REG_SET *live;
885
886           if ((condjump_p (insn) || condjump_in_parallel_p (insn))
887               && JUMP_LABEL (insn))
888             live = &LABEL_LIVE (JUMP_LABEL (insn));
889           else
890             live = &ever_live_at_start;
891
892           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; --i)
893             if (TEST_HARD_REG_BIT (*live, i))
894               reg_state[i].use_index = -1;
895         }
896
897       reload_combine_note_use (&PATTERN (insn), insn);
898       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
899         {
900           if (REG_NOTE_KIND (note) == REG_INC
901               && GET_CODE (XEXP (note, 0)) == REG)
902             {
903               int regno = REGNO (XEXP (note, 0));
904
905               reg_state[regno].store_ruid = reload_combine_ruid;
906               reg_state[regno].use_index = -1;
907             }
908         }
909     }
910
911   free (label_live);
912 }
913
914 /* Check if DST is a register or a subreg of a register; if it is,
915    update reg_state[regno].store_ruid and reg_state[regno].use_index
916    accordingly.  Called via note_stores from reload_combine.  */
917
918 static void
919 reload_combine_note_store (rtx dst, rtx set, void *data ATTRIBUTE_UNUSED)
920 {
921   int regno = 0;
922   int i;
923   enum machine_mode mode = GET_MODE (dst);
924
925   if (GET_CODE (dst) == SUBREG)
926     {
927       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
928                                    GET_MODE (SUBREG_REG (dst)),
929                                    SUBREG_BYTE (dst),
930                                    GET_MODE (dst));
931       dst = SUBREG_REG (dst);
932     }
933   if (GET_CODE (dst) != REG)
934     return;
935   regno += REGNO (dst);
936
937   /* note_stores might have stripped a STRICT_LOW_PART, so we have to be
938      careful with registers / register parts that are not full words.
939
940      Similarly for ZERO_EXTRACT and SIGN_EXTRACT.  */
941   if (GET_CODE (set) != SET
942       || GET_CODE (SET_DEST (set)) == ZERO_EXTRACT
943       || GET_CODE (SET_DEST (set)) == SIGN_EXTRACT
944       || GET_CODE (SET_DEST (set)) == STRICT_LOW_PART)
945     {
946       for (i = HARD_REGNO_NREGS (regno, mode) - 1 + regno; i >= regno; i--)
947         {
948           reg_state[i].use_index = -1;
949           reg_state[i].store_ruid = reload_combine_ruid;
950         }
951     }
952   else
953     {
954       for (i = HARD_REGNO_NREGS (regno, mode) - 1 + regno; i >= regno; i--)
955         {
956           reg_state[i].store_ruid = reload_combine_ruid;
957           reg_state[i].use_index = RELOAD_COMBINE_MAX_USES;
958         }
959     }
960 }
961
962 /* XP points to a piece of rtl that has to be checked for any uses of
963    registers.
964    *XP is the pattern of INSN, or a part of it.
965    Called from reload_combine, and recursively by itself.  */
966 static void
967 reload_combine_note_use (rtx *xp, rtx insn)
968 {
969   rtx x = *xp;
970   enum rtx_code code = x->code;
971   const char *fmt;
972   int i, j;
973   rtx offset = const0_rtx; /* For the REG case below.  */
974
975   switch (code)
976     {
977     case SET:
978       if (GET_CODE (SET_DEST (x)) == REG)
979         {
980           reload_combine_note_use (&SET_SRC (x), insn);
981           return;
982         }
983       break;
984
985     case USE:
986       /* If this is the USE of a return value, we can't change it.  */
987       if (GET_CODE (XEXP (x, 0)) == REG && REG_FUNCTION_VALUE_P (XEXP (x, 0)))
988         {
989         /* Mark the return register as used in an unknown fashion.  */
990           rtx reg = XEXP (x, 0);
991           int regno = REGNO (reg);
992           int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
993
994           while (--nregs >= 0)
995             reg_state[regno + nregs].use_index = -1;
996           return;
997         }
998       break;
999
1000     case CLOBBER:
1001       if (GET_CODE (SET_DEST (x)) == REG)
1002         {
1003           /* No spurious CLOBBERs of pseudo registers may remain.  */
1004           if (REGNO (SET_DEST (x)) >= FIRST_PSEUDO_REGISTER)
1005             abort ();
1006           return;
1007         }
1008       break;
1009
1010     case PLUS:
1011       /* We are interested in (plus (reg) (const_int)) .  */
1012       if (GET_CODE (XEXP (x, 0)) != REG
1013           || GET_CODE (XEXP (x, 1)) != CONST_INT)
1014         break;
1015       offset = XEXP (x, 1);
1016       x = XEXP (x, 0);
1017       /* Fall through.  */
1018     case REG:
1019       {
1020         int regno = REGNO (x);
1021         int use_index;
1022         int nregs;
1023
1024         /* No spurious USEs of pseudo registers may remain.  */
1025         if (regno >= FIRST_PSEUDO_REGISTER)
1026           abort ();
1027
1028         nregs = HARD_REGNO_NREGS (regno, GET_MODE (x));
1029
1030         /* We can't substitute into multi-hard-reg uses.  */
1031         if (nregs > 1)
1032           {
1033             while (--nregs >= 0)
1034               reg_state[regno + nregs].use_index = -1;
1035             return;
1036           }
1037
1038         /* If this register is already used in some unknown fashion, we
1039            can't do anything.
1040            If we decrement the index from zero to -1, we can't store more
1041            uses, so this register becomes used in an unknown fashion.  */
1042         use_index = --reg_state[regno].use_index;
1043         if (use_index < 0)
1044           return;
1045
1046         if (use_index != RELOAD_COMBINE_MAX_USES - 1)
1047           {
1048             /* We have found another use for a register that is already
1049                used later.  Check if the offsets match; if not, mark the
1050                register as used in an unknown fashion.  */
1051             if (! rtx_equal_p (offset, reg_state[regno].offset))
1052               {
1053                 reg_state[regno].use_index = -1;
1054                 return;
1055               }
1056           }
1057         else
1058           {
1059             /* This is the first use of this register we have seen since we
1060                marked it as dead.  */
1061             reg_state[regno].offset = offset;
1062             reg_state[regno].use_ruid = reload_combine_ruid;
1063           }
1064         reg_state[regno].reg_use[use_index].insn = insn;
1065         reg_state[regno].reg_use[use_index].usep = xp;
1066         return;
1067       }
1068
1069     default:
1070       break;
1071     }
1072
1073   /* Recursively process the components of X.  */
1074   fmt = GET_RTX_FORMAT (code);
1075   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1076     {
1077       if (fmt[i] == 'e')
1078         reload_combine_note_use (&XEXP (x, i), insn);
1079       else if (fmt[i] == 'E')
1080         {
1081           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1082             reload_combine_note_use (&XVECEXP (x, i, j), insn);
1083         }
1084     }
1085 }
1086 \f
1087 /* See if we can reduce the cost of a constant by replacing a move
1088    with an add.  We track situations in which a register is set to a
1089    constant or to a register plus a constant.  */
1090 /* We cannot do our optimization across labels.  Invalidating all the
1091    information about register contents we have would be costly, so we
1092    use move2add_last_label_luid to note where the label is and then
1093    later disable any optimization that would cross it.
1094    reg_offset[n] / reg_base_reg[n] / reg_mode[n] are only valid if
1095    reg_set_luid[n] is greater than move2add_last_label_luid.  */
1096 static int reg_set_luid[FIRST_PSEUDO_REGISTER];
1097
1098 /* If reg_base_reg[n] is negative, register n has been set to
1099    reg_offset[n] in mode reg_mode[n] .
1100    If reg_base_reg[n] is non-negative, register n has been set to the
1101    sum of reg_offset[n] and the value of register reg_base_reg[n]
1102    before reg_set_luid[n], calculated in mode reg_mode[n] .  */
1103 static HOST_WIDE_INT reg_offset[FIRST_PSEUDO_REGISTER];
1104 static int reg_base_reg[FIRST_PSEUDO_REGISTER];
1105 static enum machine_mode reg_mode[FIRST_PSEUDO_REGISTER];
1106
1107 /* move2add_luid is linearly increased while scanning the instructions
1108    from first to last.  It is used to set reg_set_luid in
1109    reload_cse_move2add and move2add_note_store.  */
1110 static int move2add_luid;
1111
1112 /* move2add_last_label_luid is set whenever a label is found.  Labels
1113    invalidate all previously collected reg_offset data.  */
1114 static int move2add_last_label_luid;
1115
1116 /* ??? We don't know how zero / sign extension is handled, hence we
1117    can't go from a narrower to a wider mode.  */
1118 #define MODES_OK_FOR_MOVE2ADD(OUTMODE, INMODE) \
1119   (GET_MODE_SIZE (OUTMODE) == GET_MODE_SIZE (INMODE) \
1120    || (GET_MODE_SIZE (OUTMODE) <= GET_MODE_SIZE (INMODE) \
1121        && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (OUTMODE), \
1122                                  GET_MODE_BITSIZE (INMODE))))
1123
1124 static void
1125 reload_cse_move2add (rtx first)
1126 {
1127   int i;
1128   rtx insn;
1129
1130   for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1131     reg_set_luid[i] = 0;
1132
1133   move2add_last_label_luid = 0;
1134   move2add_luid = 2;
1135   for (insn = first; insn; insn = NEXT_INSN (insn), move2add_luid++)
1136     {
1137       rtx pat, note;
1138
1139       if (GET_CODE (insn) == CODE_LABEL)
1140         {
1141           move2add_last_label_luid = move2add_luid;
1142           /* We're going to increment move2add_luid twice after a
1143              label, so that we can use move2add_last_label_luid + 1 as
1144              the luid for constants.  */
1145           move2add_luid++;
1146           continue;
1147         }
1148       if (! INSN_P (insn))
1149         continue;
1150       pat = PATTERN (insn);
1151       /* For simplicity, we only perform this optimization on
1152          straightforward SETs.  */
1153       if (GET_CODE (pat) == SET
1154           && GET_CODE (SET_DEST (pat)) == REG)
1155         {
1156           rtx reg = SET_DEST (pat);
1157           int regno = REGNO (reg);
1158           rtx src = SET_SRC (pat);
1159
1160           /* Check if we have valid information on the contents of this
1161              register in the mode of REG.  */
1162           if (reg_set_luid[regno] > move2add_last_label_luid
1163               && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg), reg_mode[regno]))
1164             {
1165               /* Try to transform (set (REGX) (CONST_INT A))
1166                                   ...
1167                                   (set (REGX) (CONST_INT B))
1168                  to
1169                                   (set (REGX) (CONST_INT A))
1170                                   ...
1171                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))
1172                  or
1173                                   (set (REGX) (CONST_INT A))
1174                                   ...
1175                                   (set (STRICT_LOW_PART (REGX)) (CONST_INT B))
1176               */
1177
1178               if (GET_CODE (src) == CONST_INT && reg_base_reg[regno] < 0)
1179                 {
1180                   rtx new_src =
1181                     GEN_INT (trunc_int_for_mode (INTVAL (src)
1182                                                  - reg_offset[regno],
1183                                                  GET_MODE (reg)));
1184                   /* (set (reg) (plus (reg) (const_int 0))) is not canonical;
1185                      use (set (reg) (reg)) instead.
1186                      We don't delete this insn, nor do we convert it into a
1187                      note, to avoid losing register notes or the return
1188                      value flag.  jump2 already knows how to get rid of
1189                      no-op moves.  */
1190                   if (new_src == const0_rtx)
1191                     {
1192                       /* If the constants are different, this is a
1193                          truncation, that, if turned into (set (reg)
1194                          (reg)), would be discarded.  Maybe we should
1195                          try a truncMN pattern?  */
1196                       if (INTVAL (src) == reg_offset [regno])
1197                         validate_change (insn, &SET_SRC (pat), reg, 0);
1198                     }
1199                   else if (rtx_cost (new_src, PLUS) < rtx_cost (src, SET)
1200                            && have_add2_insn (reg, new_src))
1201                     {
1202                       rtx newpat = gen_rtx_SET (VOIDmode,
1203                                                 reg,
1204                                                 gen_rtx_PLUS (GET_MODE (reg),
1205                                                               reg,
1206                                                               new_src));
1207                       validate_change (insn, &PATTERN (insn), newpat, 0);
1208                     }
1209                   else
1210                     {
1211                       enum machine_mode narrow_mode;
1212                       for (narrow_mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
1213                            narrow_mode != GET_MODE (reg);
1214                            narrow_mode = GET_MODE_WIDER_MODE (narrow_mode))
1215                         {
1216                           if (have_insn_for (STRICT_LOW_PART, narrow_mode)
1217                               && ((reg_offset[regno]
1218                                    & ~GET_MODE_MASK (narrow_mode))
1219                                   == (INTVAL (src)
1220                                       & ~GET_MODE_MASK (narrow_mode))))
1221                             {
1222                               rtx narrow_reg = gen_rtx_REG (narrow_mode,
1223                                                             REGNO (reg));
1224                               rtx narrow_src =
1225                                 GEN_INT (trunc_int_for_mode (INTVAL (src),
1226                                                              narrow_mode));
1227                               rtx new_set =
1228                                 gen_rtx_SET (VOIDmode,
1229                                              gen_rtx_STRICT_LOW_PART (VOIDmode,
1230                                                                       narrow_reg),
1231                                              narrow_src);
1232                               if (validate_change (insn, &PATTERN (insn),
1233                                                    new_set, 0))
1234                                 break;
1235                             }
1236                         }
1237                     }
1238                   reg_set_luid[regno] = move2add_luid;
1239                   reg_mode[regno] = GET_MODE (reg);
1240                   reg_offset[regno] = INTVAL (src);
1241                   continue;
1242                 }
1243
1244               /* Try to transform (set (REGX) (REGY))
1245                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1246                                   ...
1247                                   (set (REGX) (REGY))
1248                                   (set (REGX) (PLUS (REGX) (CONST_INT B)))
1249                  to
1250                                   (set (REGX) (REGY))
1251                                   (set (REGX) (PLUS (REGX) (CONST_INT A)))
1252                                   ...
1253                                   (set (REGX) (plus (REGX) (CONST_INT B-A)))  */
1254               else if (GET_CODE (src) == REG
1255                        && reg_set_luid[regno] == reg_set_luid[REGNO (src)]
1256                        && reg_base_reg[regno] == reg_base_reg[REGNO (src)]
1257                        && MODES_OK_FOR_MOVE2ADD (GET_MODE (reg),
1258                                                  reg_mode[REGNO (src)]))
1259                 {
1260                   rtx next = next_nonnote_insn (insn);
1261                   rtx set = NULL_RTX;
1262                   if (next)
1263                     set = single_set (next);
1264                   if (set
1265                       && SET_DEST (set) == reg
1266                       && GET_CODE (SET_SRC (set)) == PLUS
1267                       && XEXP (SET_SRC (set), 0) == reg
1268                       && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1269                     {
1270                       rtx src3 = XEXP (SET_SRC (set), 1);
1271                       HOST_WIDE_INT added_offset = INTVAL (src3);
1272                       HOST_WIDE_INT base_offset = reg_offset[REGNO (src)];
1273                       HOST_WIDE_INT regno_offset = reg_offset[regno];
1274                       rtx new_src =
1275                         GEN_INT (trunc_int_for_mode (added_offset
1276                                                      + base_offset
1277                                                      - regno_offset,
1278                                                      GET_MODE (reg)));
1279                       int success = 0;
1280
1281                       if (new_src == const0_rtx)
1282                         /* See above why we create (set (reg) (reg)) here.  */
1283                         success
1284                           = validate_change (next, &SET_SRC (set), reg, 0);
1285                       else if ((rtx_cost (new_src, PLUS)
1286                                 < COSTS_N_INSNS (1) + rtx_cost (src3, SET))
1287                                && have_add2_insn (reg, new_src))
1288                         {
1289                           rtx newpat = gen_rtx_SET (VOIDmode,
1290                                                     reg,
1291                                                     gen_rtx_PLUS (GET_MODE (reg),
1292                                                                   reg,
1293                                                                   new_src));
1294                           success
1295                             = validate_change (next, &PATTERN (next),
1296                                                newpat, 0);
1297                         }
1298                       if (success)
1299                         delete_insn (insn);
1300                       insn = next;
1301                       reg_mode[regno] = GET_MODE (reg);
1302                       reg_offset[regno] =
1303                         trunc_int_for_mode (added_offset + base_offset,
1304                                             GET_MODE (reg));
1305                       continue;
1306                     }
1307                 }
1308             }
1309         }
1310
1311       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1312         {
1313           if (REG_NOTE_KIND (note) == REG_INC
1314               && GET_CODE (XEXP (note, 0)) == REG)
1315             {
1316               /* Reset the information about this register.  */
1317               int regno = REGNO (XEXP (note, 0));
1318               if (regno < FIRST_PSEUDO_REGISTER)
1319                 reg_set_luid[regno] = 0;
1320             }
1321         }
1322       note_stores (PATTERN (insn), move2add_note_store, NULL);
1323
1324       /* If INSN is a conditional branch, we try to extract an
1325          implicit set out of it.  */
1326       if (any_condjump_p (insn) && onlyjump_p (insn))
1327         {
1328           rtx cnd = fis_get_condition (insn);
1329
1330           if (cnd != NULL_RTX
1331               && GET_CODE (cnd) == NE
1332               && GET_CODE (XEXP (cnd, 0)) == REG
1333               /* The following two checks, which are also in
1334                  move2add_note_store, are intended to reduce the
1335                  number of calls to gen_rtx_SET to avoid memory
1336                  allocation if possible.  */
1337               && SCALAR_INT_MODE_P (GET_MODE (XEXP (cnd, 0)))
1338               && HARD_REGNO_NREGS (REGNO (XEXP (cnd, 0)), GET_MODE (XEXP (cnd, 0))) == 1
1339               && GET_CODE (XEXP (cnd, 1)) == CONST_INT)
1340             {
1341               rtx implicit_set =
1342                 gen_rtx_SET (VOIDmode, XEXP (cnd, 0), XEXP (cnd, 1));
1343               move2add_note_store (SET_DEST (implicit_set), implicit_set, 0);
1344             }
1345         }
1346
1347       /* If this is a CALL_INSN, all call used registers are stored with
1348          unknown values.  */
1349       if (GET_CODE (insn) == CALL_INSN)
1350         {
1351           for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1352             {
1353               if (call_used_regs[i])
1354                 /* Reset the information about this register.  */
1355                 reg_set_luid[i] = 0;
1356             }
1357         }
1358     }
1359 }
1360
1361 /* SET is a SET or CLOBBER that sets DST.
1362    Update reg_set_luid, reg_offset and reg_base_reg accordingly.
1363    Called from reload_cse_move2add via note_stores.  */
1364
1365 static void
1366 move2add_note_store (rtx dst, rtx set, void *data ATTRIBUTE_UNUSED)
1367 {
1368   unsigned int regno = 0;
1369   unsigned int i;
1370   enum machine_mode mode = GET_MODE (dst);
1371
1372   if (GET_CODE (dst) == SUBREG)
1373     {
1374       regno = subreg_regno_offset (REGNO (SUBREG_REG (dst)),
1375                                    GET_MODE (SUBREG_REG (dst)),
1376                                    SUBREG_BYTE (dst),
1377                                    GET_MODE (dst));
1378       dst = SUBREG_REG (dst);
1379     }
1380
1381   /* Some targets do argument pushes without adding REG_INC notes.  */
1382
1383   if (GET_CODE (dst) == MEM)
1384     {
1385       dst = XEXP (dst, 0);
1386       if (GET_CODE (dst) == PRE_INC || GET_CODE (dst) == POST_INC
1387           || GET_CODE (dst) == PRE_DEC || GET_CODE (dst) == POST_DEC)
1388         reg_set_luid[REGNO (XEXP (dst, 0))] = 0;
1389       return;
1390     }
1391   if (GET_CODE (dst) != REG)
1392     return;
1393
1394   regno += REGNO (dst);
1395
1396   if (SCALAR_INT_MODE_P (mode)
1397       && HARD_REGNO_NREGS (regno, mode) == 1 && GET_CODE (set) == SET
1398       && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
1399       && GET_CODE (SET_DEST (set)) != SIGN_EXTRACT
1400       && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
1401     {
1402       rtx src = SET_SRC (set);
1403       rtx base_reg;
1404       HOST_WIDE_INT offset;
1405       int base_regno;
1406       /* This may be different from mode, if SET_DEST (set) is a
1407          SUBREG.  */
1408       enum machine_mode dst_mode = GET_MODE (dst);
1409
1410       switch (GET_CODE (src))
1411         {
1412         case PLUS:
1413           if (GET_CODE (XEXP (src, 0)) == REG)
1414             {
1415               base_reg = XEXP (src, 0);
1416
1417               if (GET_CODE (XEXP (src, 1)) == CONST_INT)
1418                 offset = INTVAL (XEXP (src, 1));
1419               else if (GET_CODE (XEXP (src, 1)) == REG
1420                        && (reg_set_luid[REGNO (XEXP (src, 1))]
1421                            > move2add_last_label_luid)
1422                        && (MODES_OK_FOR_MOVE2ADD
1423                            (dst_mode, reg_mode[REGNO (XEXP (src, 1))])))
1424                 {
1425                   if (reg_base_reg[REGNO (XEXP (src, 1))] < 0)
1426                     offset = reg_offset[REGNO (XEXP (src, 1))];
1427                   /* Maybe the first register is known to be a
1428                      constant.  */
1429                   else if (reg_set_luid[REGNO (base_reg)]
1430                            > move2add_last_label_luid
1431                            && (MODES_OK_FOR_MOVE2ADD
1432                                (dst_mode, reg_mode[REGNO (XEXP (src, 1))]))
1433                            && reg_base_reg[REGNO (base_reg)] < 0)
1434                     {
1435                       offset = reg_offset[REGNO (base_reg)];
1436                       base_reg = XEXP (src, 1);
1437                     }
1438                   else
1439                     goto invalidate;
1440                 }
1441               else
1442                 goto invalidate;
1443
1444               break;
1445             }
1446
1447           goto invalidate;
1448
1449         case REG:
1450           base_reg = src;
1451           offset = 0;
1452           break;
1453
1454         case CONST_INT:
1455           /* Start tracking the register as a constant.  */
1456           reg_base_reg[regno] = -1;
1457           reg_offset[regno] = INTVAL (SET_SRC (set));
1458           /* We assign the same luid to all registers set to constants.  */
1459           reg_set_luid[regno] = move2add_last_label_luid + 1;
1460           reg_mode[regno] = mode;
1461           return;
1462
1463         default:
1464         invalidate:
1465           /* Invalidate the contents of the register.  */
1466           reg_set_luid[regno] = 0;
1467           return;
1468         }
1469
1470       base_regno = REGNO (base_reg);
1471       /* If information about the base register is not valid, set it
1472          up as a new base register, pretending its value is known
1473          starting from the current insn.  */
1474       if (reg_set_luid[base_regno] <= move2add_last_label_luid)
1475         {
1476           reg_base_reg[base_regno] = base_regno;
1477           reg_offset[base_regno] = 0;
1478           reg_set_luid[base_regno] = move2add_luid;
1479           reg_mode[base_regno] = mode;
1480         }
1481       else if (! MODES_OK_FOR_MOVE2ADD (dst_mode,
1482                                         reg_mode[base_regno]))
1483         goto invalidate;
1484
1485       reg_mode[regno] = mode;
1486
1487       /* Copy base information from our base register.  */
1488       reg_set_luid[regno] = reg_set_luid[base_regno];
1489       reg_base_reg[regno] = reg_base_reg[base_regno];
1490
1491       /* Compute the sum of the offsets or constants.  */
1492       reg_offset[regno] = trunc_int_for_mode (offset
1493                                               + reg_offset[base_regno],
1494                                               dst_mode);
1495     }
1496   else
1497     {
1498       unsigned int endregno = regno + HARD_REGNO_NREGS (regno, mode);
1499
1500       for (i = regno; i < endregno; i++)
1501         /* Reset the information about this register.  */
1502         reg_set_luid[i] = 0;
1503     }
1504 }