OSDN Git Service

PR rtl-opt/17503
[pf3gnuchains/gcc-fork.git] / gcc / regclass.c
1 /* Compute register class preferences for pseudo-registers.
2    Copyright (C) 1987, 1988, 1991, 1992, 1993, 1994, 1995, 1996
3    1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
4    Free Software Foundation, Inc.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING.  If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
21 02111-1307, USA.  */
22
23
24 /* This file contains two passes of the compiler: reg_scan and reg_class.
25    It also defines some tables of information about the hardware registers
26    and a function init_reg_sets to initialize the tables.  */
27
28 #include "config.h"
29 #include "system.h"
30 #include "coretypes.h"
31 #include "tm.h"
32 #include "hard-reg-set.h"
33 #include "rtl.h"
34 #include "expr.h"
35 #include "tm_p.h"
36 #include "flags.h"
37 #include "basic-block.h"
38 #include "regs.h"
39 #include "function.h"
40 #include "insn-config.h"
41 #include "recog.h"
42 #include "reload.h"
43 #include "real.h"
44 #include "toplev.h"
45 #include "output.h"
46 #include "ggc.h"
47 #include "timevar.h"
48 #include "hashtab.h"
49
50 static void init_reg_sets_1 (void);
51 static void init_reg_autoinc (void);
52
53 /* If we have auto-increment or auto-decrement and we can have secondary
54    reloads, we are not allowed to use classes requiring secondary
55    reloads for pseudos auto-incremented since reload can't handle it.  */
56
57 #ifdef AUTO_INC_DEC
58 #if defined(SECONDARY_INPUT_RELOAD_CLASS) || defined(SECONDARY_OUTPUT_RELOAD_CLASS)
59 #define FORBIDDEN_INC_DEC_CLASSES
60 #endif
61 #endif
62 \f
63 /* Register tables used by many passes.  */
64
65 /* Indexed by hard register number, contains 1 for registers
66    that are fixed use (stack pointer, pc, frame pointer, etc.).
67    These are the registers that cannot be used to allocate
68    a pseudo reg for general use.  */
69
70 char fixed_regs[FIRST_PSEUDO_REGISTER];
71
72 /* Same info as a HARD_REG_SET.  */
73
74 HARD_REG_SET fixed_reg_set;
75
76 /* Data for initializing the above.  */
77
78 static const char initial_fixed_regs[] = FIXED_REGISTERS;
79
80 /* Indexed by hard register number, contains 1 for registers
81    that are fixed use or are clobbered by function calls.
82    These are the registers that cannot be used to allocate
83    a pseudo reg whose life crosses calls unless we are able
84    to save/restore them across the calls.  */
85
86 char call_used_regs[FIRST_PSEUDO_REGISTER];
87
88 /* Same info as a HARD_REG_SET.  */
89
90 HARD_REG_SET call_used_reg_set;
91
92 /* HARD_REG_SET of registers we want to avoid caller saving.  */
93 HARD_REG_SET losing_caller_save_reg_set;
94
95 /* Data for initializing the above.  */
96
97 static const char initial_call_used_regs[] = CALL_USED_REGISTERS;
98
99 /* This is much like call_used_regs, except it doesn't have to
100    be a superset of FIXED_REGISTERS. This vector indicates
101    what is really call clobbered, and is used when defining
102    regs_invalidated_by_call.  */
103
104 #ifdef CALL_REALLY_USED_REGISTERS
105 char call_really_used_regs[] = CALL_REALLY_USED_REGISTERS;
106 #endif
107
108 #ifdef CALL_REALLY_USED_REGISTERS
109 #define CALL_REALLY_USED_REGNO_P(X)  call_really_used_regs[X]
110 #else
111 #define CALL_REALLY_USED_REGNO_P(X)  call_used_regs[X]
112 #endif
113
114
115 /* Indexed by hard register number, contains 1 for registers that are
116    fixed use or call used registers that cannot hold quantities across
117    calls even if we are willing to save and restore them.  call fixed
118    registers are a subset of call used registers.  */
119
120 char call_fixed_regs[FIRST_PSEUDO_REGISTER];
121
122 /* The same info as a HARD_REG_SET.  */
123
124 HARD_REG_SET call_fixed_reg_set;
125
126 /* Number of non-fixed registers.  */
127
128 int n_non_fixed_regs;
129
130 /* Indexed by hard register number, contains 1 for registers
131    that are being used for global register decls.
132    These must be exempt from ordinary flow analysis
133    and are also considered fixed.  */
134
135 char global_regs[FIRST_PSEUDO_REGISTER];
136
137 /* Contains 1 for registers that are set or clobbered by calls.  */
138 /* ??? Ideally, this would be just call_used_regs plus global_regs, but
139    for someone's bright idea to have call_used_regs strictly include
140    fixed_regs.  Which leaves us guessing as to the set of fixed_regs
141    that are actually preserved.  We know for sure that those associated
142    with the local stack frame are safe, but scant others.  */
143
144 HARD_REG_SET regs_invalidated_by_call;
145
146 /* Table of register numbers in the order in which to try to use them.  */
147 #ifdef REG_ALLOC_ORDER
148 int reg_alloc_order[FIRST_PSEUDO_REGISTER] = REG_ALLOC_ORDER;
149
150 /* The inverse of reg_alloc_order.  */
151 int inv_reg_alloc_order[FIRST_PSEUDO_REGISTER];
152 #endif
153
154 /* For each reg class, a HARD_REG_SET saying which registers are in it.  */
155
156 HARD_REG_SET reg_class_contents[N_REG_CLASSES];
157
158 /* The same information, but as an array of unsigned ints.  We copy from
159    these unsigned ints to the table above.  We do this so the tm.h files
160    do not have to be aware of the wordsize for machines with <= 64 regs.
161    Note that we hard-code 32 here, not HOST_BITS_PER_INT.  */
162
163 #define N_REG_INTS  \
164   ((FIRST_PSEUDO_REGISTER + (32 - 1)) / 32)
165
166 static const unsigned int_reg_class_contents[N_REG_CLASSES][N_REG_INTS]
167   = REG_CLASS_CONTENTS;
168
169 /* For each reg class, number of regs it contains.  */
170
171 unsigned int reg_class_size[N_REG_CLASSES];
172
173 /* For each reg class, table listing all the containing classes.  */
174
175 enum reg_class reg_class_superclasses[N_REG_CLASSES][N_REG_CLASSES];
176
177 /* For each reg class, table listing all the classes contained in it.  */
178
179 enum reg_class reg_class_subclasses[N_REG_CLASSES][N_REG_CLASSES];
180
181 /* For each pair of reg classes,
182    a largest reg class contained in their union.  */
183
184 enum reg_class reg_class_subunion[N_REG_CLASSES][N_REG_CLASSES];
185
186 /* For each pair of reg classes,
187    the smallest reg class containing their union.  */
188
189 enum reg_class reg_class_superunion[N_REG_CLASSES][N_REG_CLASSES];
190
191 /* Array containing all of the register names.  */
192
193 const char * reg_names[] = REGISTER_NAMES;
194
195 /* For each hard register, the widest mode object that it can contain.
196    This will be a MODE_INT mode if the register can hold integers.  Otherwise
197    it will be a MODE_FLOAT or a MODE_CC mode, whichever is valid for the
198    register.  */
199
200 enum machine_mode reg_raw_mode[FIRST_PSEUDO_REGISTER];
201
202 /* 1 if there is a register of given mode.  */
203
204 bool have_regs_of_mode [MAX_MACHINE_MODE];
205
206 /* 1 if class does contain register of given mode.  */
207
208 static char contains_reg_of_mode [N_REG_CLASSES] [MAX_MACHINE_MODE];
209
210 /* Maximum cost of moving from a register in one class to a register in
211    another class.  Based on REGISTER_MOVE_COST.  */
212
213 static int move_cost[MAX_MACHINE_MODE][N_REG_CLASSES][N_REG_CLASSES];
214
215 /* Similar, but here we don't have to move if the first index is a subset
216    of the second so in that case the cost is zero.  */
217
218 static int may_move_in_cost[MAX_MACHINE_MODE][N_REG_CLASSES][N_REG_CLASSES];
219
220 /* Similar, but here we don't have to move if the first index is a superset
221    of the second so in that case the cost is zero.  */
222
223 static int may_move_out_cost[MAX_MACHINE_MODE][N_REG_CLASSES][N_REG_CLASSES];
224
225 #ifdef FORBIDDEN_INC_DEC_CLASSES
226
227 /* These are the classes that regs which are auto-incremented or decremented
228    cannot be put in.  */
229
230 static int forbidden_inc_dec_class[N_REG_CLASSES];
231
232 /* Indexed by n, is nonzero if (REG n) is used in an auto-inc or auto-dec
233    context.  */
234
235 static char *in_inc_dec;
236
237 #endif /* FORBIDDEN_INC_DEC_CLASSES */
238
239 /* Sample MEM values for use by memory_move_secondary_cost.  */
240
241 static GTY(()) rtx top_of_stack[MAX_MACHINE_MODE];
242
243 /* Linked list of reg_info structures allocated for reg_n_info array.
244    Grouping all of the allocated structures together in one lump
245    means only one call to bzero to clear them, rather than n smaller
246    calls.  */
247 struct reg_info_data {
248   struct reg_info_data *next;   /* next set of reg_info structures */
249   size_t min_index;             /* minimum index # */
250   size_t max_index;             /* maximum index # */
251   char used_p;                  /* nonzero if this has been used previously */
252   reg_info data[1];             /* beginning of the reg_info data */
253 };
254
255 static struct reg_info_data *reg_info_head;
256
257 /* No more global register variables may be declared; true once
258    regclass has been initialized.  */
259
260 static int no_global_reg_vars = 0;
261
262 /* Specify number of hard registers given machine mode occupy.  */
263 unsigned char hard_regno_nregs[FIRST_PSEUDO_REGISTER][MAX_MACHINE_MODE];
264
265 /* Function called only once to initialize the above data on reg usage.
266    Once this is done, various switches may override.  */
267
268 void
269 init_reg_sets (void)
270 {
271   int i, j;
272
273   /* First copy the register information from the initial int form into
274      the regsets.  */
275
276   for (i = 0; i < N_REG_CLASSES; i++)
277     {
278       CLEAR_HARD_REG_SET (reg_class_contents[i]);
279
280       /* Note that we hard-code 32 here, not HOST_BITS_PER_INT.  */
281       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
282         if (int_reg_class_contents[i][j / 32]
283             & ((unsigned) 1 << (j % 32)))
284           SET_HARD_REG_BIT (reg_class_contents[i], j);
285     }
286
287   /* Sanity check: make sure the target macros FIXED_REGISTERS and
288      CALL_USED_REGISTERS had the right number of initializers.  */
289   gcc_assert (sizeof fixed_regs == sizeof initial_fixed_regs);
290   gcc_assert (sizeof call_used_regs == sizeof initial_call_used_regs);
291
292   memcpy (fixed_regs, initial_fixed_regs, sizeof fixed_regs);
293   memcpy (call_used_regs, initial_call_used_regs, sizeof call_used_regs);
294   memset (global_regs, 0, sizeof global_regs);
295
296   /* Do any additional initialization regsets may need.  */
297   INIT_ONCE_REG_SET ();
298
299 #ifdef REG_ALLOC_ORDER
300   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
301     inv_reg_alloc_order[reg_alloc_order[i]] = i;
302 #endif
303 }
304
305 /* After switches have been processed, which perhaps alter
306    `fixed_regs' and `call_used_regs', convert them to HARD_REG_SETs.  */
307
308 static void
309 init_reg_sets_1 (void)
310 {
311   unsigned int i, j;
312   unsigned int /* enum machine_mode */ m;
313
314   /* This macro allows the fixed or call-used registers
315      and the register classes to depend on target flags.  */
316
317 #ifdef CONDITIONAL_REGISTER_USAGE
318   CONDITIONAL_REGISTER_USAGE;
319 #endif
320
321   /* Compute number of hard regs in each class.  */
322
323   memset (reg_class_size, 0, sizeof reg_class_size);
324   for (i = 0; i < N_REG_CLASSES; i++)
325     for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
326       if (TEST_HARD_REG_BIT (reg_class_contents[i], j))
327         reg_class_size[i]++;
328
329   /* Initialize the table of subunions.
330      reg_class_subunion[I][J] gets the largest-numbered reg-class
331      that is contained in the union of classes I and J.  */
332
333   for (i = 0; i < N_REG_CLASSES; i++)
334     {
335       for (j = 0; j < N_REG_CLASSES; j++)
336         {
337           HARD_REG_SET c;
338           int k;
339
340           COPY_HARD_REG_SET (c, reg_class_contents[i]);
341           IOR_HARD_REG_SET (c, reg_class_contents[j]);
342           for (k = 0; k < N_REG_CLASSES; k++)
343             {
344               GO_IF_HARD_REG_SUBSET (reg_class_contents[k], c,
345                                      subclass1);
346               continue;
347
348             subclass1:
349               /* Keep the largest subclass.  */         /* SPEE 900308 */
350               GO_IF_HARD_REG_SUBSET (reg_class_contents[k],
351                                      reg_class_contents[(int) reg_class_subunion[i][j]],
352                                      subclass2);
353               reg_class_subunion[i][j] = (enum reg_class) k;
354             subclass2:
355               ;
356             }
357         }
358     }
359
360   /* Initialize the table of superunions.
361      reg_class_superunion[I][J] gets the smallest-numbered reg-class
362      containing the union of classes I and J.  */
363
364   for (i = 0; i < N_REG_CLASSES; i++)
365     {
366       for (j = 0; j < N_REG_CLASSES; j++)
367         {
368           HARD_REG_SET c;
369           int k;
370
371           COPY_HARD_REG_SET (c, reg_class_contents[i]);
372           IOR_HARD_REG_SET (c, reg_class_contents[j]);
373           for (k = 0; k < N_REG_CLASSES; k++)
374             GO_IF_HARD_REG_SUBSET (c, reg_class_contents[k], superclass);
375
376         superclass:
377           reg_class_superunion[i][j] = (enum reg_class) k;
378         }
379     }
380
381   /* Initialize the tables of subclasses and superclasses of each reg class.
382      First clear the whole table, then add the elements as they are found.  */
383
384   for (i = 0; i < N_REG_CLASSES; i++)
385     {
386       for (j = 0; j < N_REG_CLASSES; j++)
387         {
388           reg_class_superclasses[i][j] = LIM_REG_CLASSES;
389           reg_class_subclasses[i][j] = LIM_REG_CLASSES;
390         }
391     }
392
393   for (i = 0; i < N_REG_CLASSES; i++)
394     {
395       if (i == (int) NO_REGS)
396         continue;
397
398       for (j = i + 1; j < N_REG_CLASSES; j++)
399         {
400           enum reg_class *p;
401
402           GO_IF_HARD_REG_SUBSET (reg_class_contents[i], reg_class_contents[j],
403                                  subclass);
404           continue;
405         subclass:
406           /* Reg class I is a subclass of J.
407              Add J to the table of superclasses of I.  */
408           p = &reg_class_superclasses[i][0];
409           while (*p != LIM_REG_CLASSES) p++;
410           *p = (enum reg_class) j;
411           /* Add I to the table of superclasses of J.  */
412           p = &reg_class_subclasses[j][0];
413           while (*p != LIM_REG_CLASSES) p++;
414           *p = (enum reg_class) i;
415         }
416     }
417
418   /* Initialize "constant" tables.  */
419
420   CLEAR_HARD_REG_SET (fixed_reg_set);
421   CLEAR_HARD_REG_SET (call_used_reg_set);
422   CLEAR_HARD_REG_SET (call_fixed_reg_set);
423   CLEAR_HARD_REG_SET (regs_invalidated_by_call);
424
425   memcpy (call_fixed_regs, fixed_regs, sizeof call_fixed_regs);
426
427   n_non_fixed_regs = 0;
428
429   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
430     {
431       /* call_used_regs must include fixed_regs.  */
432       gcc_assert (!fixed_regs[i] || call_used_regs[i]);
433 #ifdef CALL_REALLY_USED_REGISTERS
434       /* call_used_regs must include call_really_used_regs.  */
435       gcc_assert (!call_really_used_regs[i] || call_used_regs[i]);
436 #endif
437
438       if (fixed_regs[i])
439         SET_HARD_REG_BIT (fixed_reg_set, i);
440       else
441         n_non_fixed_regs++;
442
443       if (call_used_regs[i])
444         SET_HARD_REG_BIT (call_used_reg_set, i);
445       if (call_fixed_regs[i])
446         SET_HARD_REG_BIT (call_fixed_reg_set, i);
447       if (CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (i)))
448         SET_HARD_REG_BIT (losing_caller_save_reg_set, i);
449
450       /* There are a couple of fixed registers that we know are safe to
451          exclude from being clobbered by calls:
452
453          The frame pointer is always preserved across calls.  The arg pointer
454          is if it is fixed.  The stack pointer usually is, unless
455          RETURN_POPS_ARGS, in which case an explicit CLOBBER will be present.
456          If we are generating PIC code, the PIC offset table register is
457          preserved across calls, though the target can override that.  */
458
459       if (i == STACK_POINTER_REGNUM)
460         ;
461       else if (global_regs[i])
462         SET_HARD_REG_BIT (regs_invalidated_by_call, i);
463       else if (i == FRAME_POINTER_REGNUM)
464         ;
465 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
466       else if (i == HARD_FRAME_POINTER_REGNUM)
467         ;
468 #endif
469 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
470       else if (i == ARG_POINTER_REGNUM && fixed_regs[i])
471         ;
472 #endif
473 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
474       else if (i == (unsigned) PIC_OFFSET_TABLE_REGNUM && fixed_regs[i])
475         ;
476 #endif
477       else if (CALL_REALLY_USED_REGNO_P (i))
478         SET_HARD_REG_BIT (regs_invalidated_by_call, i);
479     }
480
481   memset (have_regs_of_mode, 0, sizeof (have_regs_of_mode));
482   memset (contains_reg_of_mode, 0, sizeof (contains_reg_of_mode));
483   for (m = 0; m < (unsigned int) MAX_MACHINE_MODE; m++)
484     for (i = 0; i < N_REG_CLASSES; i++)
485       if ((unsigned) CLASS_MAX_NREGS (i, m) <= reg_class_size[i])
486         for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
487           if (!fixed_regs [j] && TEST_HARD_REG_BIT (reg_class_contents[i], j)
488               && HARD_REGNO_MODE_OK (j, m))
489              {
490                contains_reg_of_mode [i][m] = 1;
491                have_regs_of_mode [m] = 1;
492                break;
493              }
494
495   /* Initialize the move cost table.  Find every subset of each class
496      and take the maximum cost of moving any subset to any other.  */
497
498   for (m = 0; m < (unsigned int) MAX_MACHINE_MODE; m++)
499     if (have_regs_of_mode [m])
500       {
501         for (i = 0; i < N_REG_CLASSES; i++)
502           if (contains_reg_of_mode [i][m])
503             for (j = 0; j < N_REG_CLASSES; j++)
504               {
505                 int cost;
506                 enum reg_class *p1, *p2;
507
508                 if (!contains_reg_of_mode [j][m])
509                   {
510                     move_cost[m][i][j] = 65536;
511                     may_move_in_cost[m][i][j] = 65536;
512                     may_move_out_cost[m][i][j] = 65536;
513                   }
514                 else
515                   {
516                     cost = REGISTER_MOVE_COST (m, i, j);
517
518                     for (p2 = &reg_class_subclasses[j][0];
519                          *p2 != LIM_REG_CLASSES;
520                          p2++)
521                       if (*p2 != i && contains_reg_of_mode [*p2][m])
522                         cost = MAX (cost, move_cost [m][i][*p2]);
523
524                     for (p1 = &reg_class_subclasses[i][0];
525                          *p1 != LIM_REG_CLASSES;
526                          p1++)
527                       if (*p1 != j && contains_reg_of_mode [*p1][m])
528                         cost = MAX (cost, move_cost [m][*p1][j]);
529
530                     move_cost[m][i][j] = cost;
531
532                     if (reg_class_subset_p (i, j))
533                       may_move_in_cost[m][i][j] = 0;
534                     else
535                       may_move_in_cost[m][i][j] = cost;
536
537                     if (reg_class_subset_p (j, i))
538                       may_move_out_cost[m][i][j] = 0;
539                     else
540                       may_move_out_cost[m][i][j] = cost;
541                   }
542               }
543           else
544             for (j = 0; j < N_REG_CLASSES; j++)
545               {
546                 move_cost[m][i][j] = 65536;
547                 may_move_in_cost[m][i][j] = 65536;
548                 may_move_out_cost[m][i][j] = 65536;
549               }
550       }
551 }
552
553 /* Compute the table of register modes.
554    These values are used to record death information for individual registers
555    (as opposed to a multi-register mode).  */
556
557 void
558 init_reg_modes_once (void)
559 {
560   int i, j;
561
562   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
563     for (j = 0; j < MAX_MACHINE_MODE; j++)
564       hard_regno_nregs[i][j] = HARD_REGNO_NREGS(i, (enum machine_mode)j);
565
566   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
567     {
568       reg_raw_mode[i] = choose_hard_reg_mode (i, 1, false);
569
570       /* If we couldn't find a valid mode, just use the previous mode.
571          ??? One situation in which we need to do this is on the mips where
572          HARD_REGNO_NREGS (fpreg, [SD]Fmode) returns 2.  Ideally we'd like
573          to use DF mode for the even registers and VOIDmode for the odd
574          (for the cpu models where the odd ones are inaccessible).  */
575       if (reg_raw_mode[i] == VOIDmode)
576         reg_raw_mode[i] = i == 0 ? word_mode : reg_raw_mode[i-1];
577     }
578 }
579
580 /* Finish initializing the register sets and
581    initialize the register modes.  */
582
583 void
584 init_regs (void)
585 {
586   /* This finishes what was started by init_reg_sets, but couldn't be done
587      until after register usage was specified.  */
588   init_reg_sets_1 ();
589
590   init_reg_autoinc ();
591 }
592
593 /* Initialize some fake stack-frame MEM references for use in
594    memory_move_secondary_cost.  */
595
596 void
597 init_fake_stack_mems (void)
598 {
599 #ifdef HAVE_SECONDARY_RELOADS
600   {
601     int i;
602
603     for (i = 0; i < MAX_MACHINE_MODE; i++)
604       top_of_stack[i] = gen_rtx_MEM (i, stack_pointer_rtx);
605   }
606 #endif
607 }
608
609 #ifdef HAVE_SECONDARY_RELOADS
610
611 /* Compute extra cost of moving registers to/from memory due to reloads.
612    Only needed if secondary reloads are required for memory moves.  */
613
614 int
615 memory_move_secondary_cost (enum machine_mode mode, enum reg_class class, int in)
616 {
617   enum reg_class altclass;
618   int partial_cost = 0;
619   /* We need a memory reference to feed to SECONDARY... macros.  */
620   /* mem may be unused even if the SECONDARY_ macros are defined.  */
621   rtx mem ATTRIBUTE_UNUSED = top_of_stack[(int) mode];
622
623
624   if (in)
625     {
626 #ifdef SECONDARY_INPUT_RELOAD_CLASS
627       altclass = SECONDARY_INPUT_RELOAD_CLASS (class, mode, mem);
628 #else
629       altclass = NO_REGS;
630 #endif
631     }
632   else
633     {
634 #ifdef SECONDARY_OUTPUT_RELOAD_CLASS
635       altclass = SECONDARY_OUTPUT_RELOAD_CLASS (class, mode, mem);
636 #else
637       altclass = NO_REGS;
638 #endif
639     }
640
641   if (altclass == NO_REGS)
642     return 0;
643
644   if (in)
645     partial_cost = REGISTER_MOVE_COST (mode, altclass, class);
646   else
647     partial_cost = REGISTER_MOVE_COST (mode, class, altclass);
648
649   if (class == altclass)
650     /* This isn't simply a copy-to-temporary situation.  Can't guess
651        what it is, so MEMORY_MOVE_COST really ought not to be calling
652        here in that case.
653
654        I'm tempted to put in an assert here, but returning this will
655        probably only give poor estimates, which is what we would've
656        had before this code anyways.  */
657     return partial_cost;
658
659   /* Check if the secondary reload register will also need a
660      secondary reload.  */
661   return memory_move_secondary_cost (mode, altclass, in) + partial_cost;
662 }
663 #endif
664
665 /* Return a machine mode that is legitimate for hard reg REGNO and large
666    enough to save nregs.  If we can't find one, return VOIDmode.
667    If CALL_SAVED is true, only consider modes that are call saved.  */
668
669 enum machine_mode
670 choose_hard_reg_mode (unsigned int regno ATTRIBUTE_UNUSED,
671                       unsigned int nregs, bool call_saved)
672 {
673   unsigned int /* enum machine_mode */ m;
674   enum machine_mode found_mode = VOIDmode, mode;
675
676   /* We first look for the largest integer mode that can be validly
677      held in REGNO.  If none, we look for the largest floating-point mode.
678      If we still didn't find a valid mode, try CCmode.  */
679
680   for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
681        mode != VOIDmode;
682        mode = GET_MODE_WIDER_MODE (mode))
683     if ((unsigned) hard_regno_nregs[regno][mode] == nregs
684         && HARD_REGNO_MODE_OK (regno, mode)
685         && (! call_saved || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
686       found_mode = mode;
687
688   if (found_mode != VOIDmode)
689     return found_mode;
690
691   for (mode = GET_CLASS_NARROWEST_MODE (MODE_FLOAT);
692        mode != VOIDmode;
693        mode = GET_MODE_WIDER_MODE (mode))
694     if ((unsigned) hard_regno_nregs[regno][mode] == nregs
695         && HARD_REGNO_MODE_OK (regno, mode)
696         && (! call_saved || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
697       found_mode = mode;
698
699   if (found_mode != VOIDmode)
700     return found_mode;
701
702   for (mode = GET_CLASS_NARROWEST_MODE (MODE_VECTOR_FLOAT);
703        mode != VOIDmode;
704        mode = GET_MODE_WIDER_MODE (mode))
705     if ((unsigned) hard_regno_nregs[regno][mode] == nregs
706         && HARD_REGNO_MODE_OK (regno, mode)
707         && (! call_saved || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
708       found_mode = mode;
709
710   if (found_mode != VOIDmode)
711     return found_mode;
712
713   for (mode = GET_CLASS_NARROWEST_MODE (MODE_VECTOR_INT);
714        mode != VOIDmode;
715        mode = GET_MODE_WIDER_MODE (mode))
716     if ((unsigned) hard_regno_nregs[regno][mode] == nregs
717         && HARD_REGNO_MODE_OK (regno, mode)
718         && (! call_saved || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
719       found_mode = mode;
720
721   if (found_mode != VOIDmode)
722     return found_mode;
723
724   /* Iterate over all of the CCmodes.  */
725   for (m = (unsigned int) CCmode; m < (unsigned int) NUM_MACHINE_MODES; ++m)
726     {
727       mode = (enum machine_mode) m;
728       if ((unsigned) hard_regno_nregs[regno][mode] == nregs
729           && HARD_REGNO_MODE_OK (regno, mode)
730           && (! call_saved || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
731         return mode;
732     }
733
734   /* We can't find a mode valid for this register.  */
735   return VOIDmode;
736 }
737
738 /* Specify the usage characteristics of the register named NAME.
739    It should be a fixed register if FIXED and a
740    call-used register if CALL_USED.  */
741
742 void
743 fix_register (const char *name, int fixed, int call_used)
744 {
745   int i;
746
747   /* Decode the name and update the primary form of
748      the register info.  */
749
750   if ((i = decode_reg_name (name)) >= 0)
751     {
752       if ((i == STACK_POINTER_REGNUM
753 #ifdef HARD_FRAME_POINTER_REGNUM
754            || i == HARD_FRAME_POINTER_REGNUM
755 #else
756            || i == FRAME_POINTER_REGNUM
757 #endif
758            )
759           && (fixed == 0 || call_used == 0))
760         {
761           static const char * const what_option[2][2] = {
762             { "call-saved", "call-used" },
763             { "no-such-option", "fixed" }};
764
765           error ("can't use '%s' as a %s register", name,
766                  what_option[fixed][call_used]);
767         }
768       else
769         {
770           fixed_regs[i] = fixed;
771           call_used_regs[i] = call_used;
772 #ifdef CALL_REALLY_USED_REGISTERS
773           if (fixed == 0)
774             call_really_used_regs[i] = call_used;
775 #endif
776         }
777     }
778   else
779     {
780       warning ("unknown register name: %s", name);
781     }
782 }
783
784 /* Mark register number I as global.  */
785
786 void
787 globalize_reg (int i)
788 {
789   if (fixed_regs[i] == 0 && no_global_reg_vars)
790     error ("global register variable follows a function definition");
791
792   if (global_regs[i])
793     {
794       warning ("register used for two global register variables");
795       return;
796     }
797
798   if (call_used_regs[i] && ! fixed_regs[i])
799     warning ("call-clobbered register used for global register variable");
800
801   global_regs[i] = 1;
802
803   /* If we're globalizing the frame pointer, we need to set the
804      appropriate regs_invalidated_by_call bit, even if it's already
805      set in fixed_regs.  */
806   if (i != STACK_POINTER_REGNUM)
807     SET_HARD_REG_BIT (regs_invalidated_by_call, i);
808
809   /* If already fixed, nothing else to do.  */
810   if (fixed_regs[i])
811     return;
812
813   fixed_regs[i] = call_used_regs[i] = call_fixed_regs[i] = 1;
814 #ifdef CALL_REALLY_USED_REGISTERS
815   call_really_used_regs[i] = 1;
816 #endif
817   n_non_fixed_regs--;
818
819   SET_HARD_REG_BIT (fixed_reg_set, i);
820   SET_HARD_REG_BIT (call_used_reg_set, i);
821   SET_HARD_REG_BIT (call_fixed_reg_set, i);
822 }
823 \f
824 /* Now the data and code for the `regclass' pass, which happens
825    just before local-alloc.  */
826
827 /* The `costs' struct records the cost of using a hard register of each class
828    and of using memory for each pseudo.  We use this data to set up
829    register class preferences.  */
830
831 struct costs
832 {
833   int cost[N_REG_CLASSES];
834   int mem_cost;
835 };
836
837 /* Structure used to record preferences of given pseudo.  */
838 struct reg_pref
839 {
840   /* (enum reg_class) prefclass is the preferred class.  */
841   char prefclass;
842
843   /* altclass is a register class that we should use for allocating
844      pseudo if no register in the preferred class is available.
845      If no register in this class is available, memory is preferred.
846
847      It might appear to be more general to have a bitmask of classes here,
848      but since it is recommended that there be a class corresponding to the
849      union of most major pair of classes, that generality is not required.  */
850   char altclass;
851 };
852
853 /* Record the cost of each class for each pseudo.  */
854
855 static struct costs *costs;
856
857 /* Initialized once, and used to initialize cost values for each insn.  */
858
859 static struct costs init_cost;
860
861 /* Record preferences of each pseudo.
862    This is available after `regclass' is run.  */
863
864 static struct reg_pref *reg_pref;
865
866 /* Allocated buffers for reg_pref.  */
867
868 static struct reg_pref *reg_pref_buffer;
869
870 /* Frequency of executions of current insn.  */
871
872 static int frequency;
873
874 static rtx scan_one_insn (rtx, int);
875 static void record_operand_costs (rtx, struct costs *, struct reg_pref *);
876 static void dump_regclass (FILE *);
877 static void record_reg_classes (int, int, rtx *, enum machine_mode *,
878                                 const char **, rtx, struct costs *,
879                                 struct reg_pref *);
880 static int copy_cost (rtx, enum machine_mode, enum reg_class, int);
881 static void record_address_regs (rtx, enum reg_class, int);
882 #ifdef FORBIDDEN_INC_DEC_CLASSES
883 static int auto_inc_dec_reg_p (rtx, enum machine_mode);
884 #endif
885 static void reg_scan_mark_refs (rtx, rtx, int, unsigned int);
886
887 /* Return the reg_class in which pseudo reg number REGNO is best allocated.
888    This function is sometimes called before the info has been computed.
889    When that happens, just return GENERAL_REGS, which is innocuous.  */
890
891 enum reg_class
892 reg_preferred_class (int regno)
893 {
894   if (reg_pref == 0)
895     return GENERAL_REGS;
896   return (enum reg_class) reg_pref[regno].prefclass;
897 }
898
899 enum reg_class
900 reg_alternate_class (int regno)
901 {
902   if (reg_pref == 0)
903     return ALL_REGS;
904
905   return (enum reg_class) reg_pref[regno].altclass;
906 }
907
908 /* Initialize some global data for this pass.  */
909
910 void
911 regclass_init (void)
912 {
913   int i;
914
915   init_cost.mem_cost = 10000;
916   for (i = 0; i < N_REG_CLASSES; i++)
917     init_cost.cost[i] = 10000;
918
919   /* This prevents dump_flow_info from losing if called
920      before regclass is run.  */
921   reg_pref = NULL;
922
923   /* No more global register variables may be declared.  */
924   no_global_reg_vars = 1;
925 }
926 \f
927 /* Dump register costs.  */
928 static void
929 dump_regclass (FILE *dump)
930 {
931   static const char *const reg_class_names[] = REG_CLASS_NAMES;
932   int i;
933   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
934     {
935       int /* enum reg_class */ class;
936       if (REG_N_REFS (i))
937         {
938           fprintf (dump, "  Register %i costs:", i);
939           for (class = 0; class < (int) N_REG_CLASSES; class++)
940             if (contains_reg_of_mode [(enum reg_class) class][PSEUDO_REGNO_MODE (i)]
941 #ifdef FORBIDDEN_INC_DEC_CLASSES
942                 && (!in_inc_dec[i]
943                     || !forbidden_inc_dec_class[(enum reg_class) class])
944 #endif
945 #ifdef CANNOT_CHANGE_MODE_CLASS
946                 && ! invalid_mode_change_p (i, (enum reg_class) class,
947                                             PSEUDO_REGNO_MODE (i))
948 #endif
949                 )
950             fprintf (dump, " %s:%i", reg_class_names[class],
951                      costs[i].cost[(enum reg_class) class]);
952           fprintf (dump, " MEM:%i\n", costs[i].mem_cost);
953         }
954     }
955 }
956 \f
957
958 /* Calculate the costs of insn operands.  */
959
960 static void
961 record_operand_costs (rtx insn, struct costs *op_costs,
962                       struct reg_pref *reg_pref)
963 {
964   const char *constraints[MAX_RECOG_OPERANDS];
965   enum machine_mode modes[MAX_RECOG_OPERANDS];
966   int i;
967
968   for (i = 0; i < recog_data.n_operands; i++)
969     {
970       constraints[i] = recog_data.constraints[i];
971       modes[i] = recog_data.operand_mode[i];
972     }
973
974   /* If we get here, we are set up to record the costs of all the
975      operands for this insn.  Start by initializing the costs.
976      Then handle any address registers.  Finally record the desired
977      classes for any pseudos, doing it twice if some pair of
978      operands are commutative.  */
979
980   for (i = 0; i < recog_data.n_operands; i++)
981     {
982       op_costs[i] = init_cost;
983
984       if (GET_CODE (recog_data.operand[i]) == SUBREG)
985         recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);
986
987       if (MEM_P (recog_data.operand[i]))
988         record_address_regs (XEXP (recog_data.operand[i], 0),
989                              MODE_BASE_REG_CLASS (modes[i]), frequency * 2);
990       else if (constraints[i][0] == 'p'
991                || EXTRA_ADDRESS_CONSTRAINT (constraints[i][0], constraints[i]))
992         record_address_regs (recog_data.operand[i],
993                              MODE_BASE_REG_CLASS (modes[i]), frequency * 2);
994     }
995
996   /* Check for commutative in a separate loop so everything will
997      have been initialized.  We must do this even if one operand
998      is a constant--see addsi3 in m68k.md.  */
999
1000   for (i = 0; i < (int) recog_data.n_operands - 1; i++)
1001     if (constraints[i][0] == '%')
1002       {
1003         const char *xconstraints[MAX_RECOG_OPERANDS];
1004         int j;
1005
1006         /* Handle commutative operands by swapping the constraints.
1007            We assume the modes are the same.  */
1008
1009         for (j = 0; j < recog_data.n_operands; j++)
1010           xconstraints[j] = constraints[j];
1011
1012         xconstraints[i] = constraints[i+1];
1013         xconstraints[i+1] = constraints[i];
1014         record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1015                             recog_data.operand, modes,
1016                             xconstraints, insn, op_costs, reg_pref);
1017       }
1018
1019   record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1020                       recog_data.operand, modes,
1021                       constraints, insn, op_costs, reg_pref);
1022 }
1023 \f
1024 /* Subroutine of regclass, processes one insn INSN.  Scan it and record each
1025    time it would save code to put a certain register in a certain class.
1026    PASS, when nonzero, inhibits some optimizations which need only be done
1027    once.
1028    Return the last insn processed, so that the scan can be continued from
1029    there.  */
1030
1031 static rtx
1032 scan_one_insn (rtx insn, int pass)
1033 {
1034   enum rtx_code pat_code;
1035   rtx set, note;
1036   int i, j;
1037   struct costs op_costs[MAX_RECOG_OPERANDS];
1038
1039   if (!INSN_P (insn))
1040     return insn;
1041
1042   pat_code = GET_CODE (PATTERN (insn));
1043   if (pat_code == USE
1044       || pat_code == CLOBBER
1045       || pat_code == ASM_INPUT
1046       || pat_code == ADDR_VEC
1047       || pat_code == ADDR_DIFF_VEC)
1048     return insn;
1049
1050   set = single_set (insn);
1051   extract_insn (insn);
1052
1053   /* If this insn loads a parameter from its stack slot, then
1054      it represents a savings, rather than a cost, if the
1055      parameter is stored in memory.  Record this fact.  */
1056
1057   if (set != 0 && REG_P (SET_DEST (set))
1058       && MEM_P (SET_SRC (set))
1059       && (note = find_reg_note (insn, REG_EQUIV,
1060                                 NULL_RTX)) != 0
1061       && MEM_P (XEXP (note, 0)))
1062     {
1063       costs[REGNO (SET_DEST (set))].mem_cost
1064         -= (MEMORY_MOVE_COST (GET_MODE (SET_DEST (set)),
1065                               GENERAL_REGS, 1)
1066             * frequency);
1067       record_address_regs (XEXP (SET_SRC (set), 0),
1068                            MODE_BASE_REG_CLASS (VOIDmode), frequency * 2);
1069       return insn;
1070     }
1071
1072   /* Improve handling of two-address insns such as
1073      (set X (ashift CONST Y)) where CONST must be made to
1074      match X. Change it into two insns: (set X CONST)
1075      (set X (ashift X Y)).  If we left this for reloading, it
1076      would probably get three insns because X and Y might go
1077      in the same place. This prevents X and Y from receiving
1078      the same hard reg.
1079
1080      We can only do this if the modes of operands 0 and 1
1081      (which might not be the same) are tieable and we only need
1082      do this during our first pass.  */
1083
1084   if (pass == 0 && optimize
1085       && recog_data.n_operands >= 3
1086       && recog_data.constraints[1][0] == '0'
1087       && recog_data.constraints[1][1] == 0
1088       && CONSTANT_P (recog_data.operand[1])
1089       && ! rtx_equal_p (recog_data.operand[0], recog_data.operand[1])
1090       && ! rtx_equal_p (recog_data.operand[0], recog_data.operand[2])
1091       && REG_P (recog_data.operand[0])
1092       && MODES_TIEABLE_P (GET_MODE (recog_data.operand[0]),
1093                           recog_data.operand_mode[1]))
1094     {
1095       rtx previnsn = prev_real_insn (insn);
1096       rtx dest
1097         = gen_lowpart (recog_data.operand_mode[1],
1098                        recog_data.operand[0]);
1099       rtx newinsn
1100         = emit_insn_before (gen_move_insn (dest, recog_data.operand[1]), insn);
1101
1102       /* If this insn was the start of a basic block,
1103          include the new insn in that block.
1104          We need not check for code_label here;
1105          while a basic block can start with a code_label,
1106          INSN could not be at the beginning of that block.  */
1107       if (previnsn == 0 || JUMP_P (previnsn))
1108         {
1109           basic_block b;
1110           FOR_EACH_BB (b)
1111             if (insn == BB_HEAD (b))
1112               BB_HEAD (b) = newinsn;
1113         }
1114
1115       /* This makes one more setting of new insns's dest.  */
1116       REG_N_SETS (REGNO (recog_data.operand[0]))++;
1117       REG_N_REFS (REGNO (recog_data.operand[0]))++;
1118       REG_FREQ (REGNO (recog_data.operand[0])) += frequency;
1119
1120       *recog_data.operand_loc[1] = recog_data.operand[0];
1121       REG_N_REFS (REGNO (recog_data.operand[0]))++;
1122       REG_FREQ (REGNO (recog_data.operand[0])) += frequency;
1123       for (i = recog_data.n_dups - 1; i >= 0; i--)
1124         if (recog_data.dup_num[i] == 1)
1125           {
1126             *recog_data.dup_loc[i] = recog_data.operand[0];
1127             REG_N_REFS (REGNO (recog_data.operand[0]))++;
1128             REG_FREQ (REGNO (recog_data.operand[0])) += frequency;
1129           }
1130
1131       return PREV_INSN (newinsn);
1132     }
1133
1134   record_operand_costs (insn, op_costs, reg_pref);
1135
1136   /* Now add the cost for each operand to the total costs for
1137      its register.  */
1138
1139   for (i = 0; i < recog_data.n_operands; i++)
1140     if (REG_P (recog_data.operand[i])
1141         && REGNO (recog_data.operand[i]) >= FIRST_PSEUDO_REGISTER)
1142       {
1143         int regno = REGNO (recog_data.operand[i]);
1144         struct costs *p = &costs[regno], *q = &op_costs[i];
1145
1146         p->mem_cost += q->mem_cost * frequency;
1147         for (j = 0; j < N_REG_CLASSES; j++)
1148           p->cost[j] += q->cost[j] * frequency;
1149       }
1150
1151   return insn;
1152 }
1153
1154 /* Initialize information about which register classes can be used for
1155    pseudos that are auto-incremented or auto-decremented.  */
1156
1157 static void
1158 init_reg_autoinc (void)
1159 {
1160 #ifdef FORBIDDEN_INC_DEC_CLASSES
1161   int i;
1162
1163   for (i = 0; i < N_REG_CLASSES; i++)
1164     {
1165       rtx r = gen_rtx_raw_REG (VOIDmode, 0);
1166       enum machine_mode m;
1167       int j;
1168
1169       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1170         if (TEST_HARD_REG_BIT (reg_class_contents[i], j))
1171           {
1172             REGNO (r) = j;
1173
1174             for (m = VOIDmode; (int) m < (int) MAX_MACHINE_MODE;
1175                  m = (enum machine_mode) ((int) m + 1))
1176               if (HARD_REGNO_MODE_OK (j, m))
1177                 {
1178                   PUT_MODE (r, m);
1179
1180                   /* If a register is not directly suitable for an
1181                      auto-increment or decrement addressing mode and
1182                      requires secondary reloads, disallow its class from
1183                      being used in such addresses.  */
1184
1185                   if ((0
1186 #ifdef SECONDARY_RELOAD_CLASS
1187                        || (SECONDARY_RELOAD_CLASS (MODE_BASE_REG_CLASS (VOIDmode), m, r)
1188                            != NO_REGS)
1189 #else
1190 #ifdef SECONDARY_INPUT_RELOAD_CLASS
1191                        || (SECONDARY_INPUT_RELOAD_CLASS (MODE_BASE_REG_CLASS (VOIDmode), m, r)
1192                            != NO_REGS)
1193 #endif
1194 #ifdef SECONDARY_OUTPUT_RELOAD_CLASS
1195                        || (SECONDARY_OUTPUT_RELOAD_CLASS (MODE_BASE_REG_CLASS (VOIDmode), m, r)
1196                            != NO_REGS)
1197 #endif
1198 #endif
1199                        )
1200                       && ! auto_inc_dec_reg_p (r, m))
1201                     forbidden_inc_dec_class[i] = 1;
1202                 }
1203           }
1204     }
1205 #endif /* FORBIDDEN_INC_DEC_CLASSES */
1206 }
1207
1208 /* This is a pass of the compiler that scans all instructions
1209    and calculates the preferred class for each pseudo-register.
1210    This information can be accessed later by calling `reg_preferred_class'.
1211    This pass comes just before local register allocation.  */
1212
1213 void
1214 regclass (rtx f, int nregs, FILE *dump)
1215 {
1216   rtx insn;
1217   int i;
1218   int pass;
1219
1220   init_recog ();
1221
1222   costs = xmalloc (nregs * sizeof (struct costs));
1223
1224 #ifdef FORBIDDEN_INC_DEC_CLASSES
1225
1226   in_inc_dec = xmalloc (nregs);
1227
1228 #endif /* FORBIDDEN_INC_DEC_CLASSES */
1229
1230   /* Normally we scan the insns once and determine the best class to use for
1231      each register.  However, if -fexpensive_optimizations are on, we do so
1232      twice, the second time using the tentative best classes to guide the
1233      selection.  */
1234
1235   for (pass = 0; pass <= flag_expensive_optimizations; pass++)
1236     {
1237       basic_block bb;
1238
1239       if (dump)
1240         fprintf (dump, "\n\nPass %i\n\n",pass);
1241       /* Zero out our accumulation of the cost of each class for each reg.  */
1242
1243       memset (costs, 0, nregs * sizeof (struct costs));
1244
1245 #ifdef FORBIDDEN_INC_DEC_CLASSES
1246       memset (in_inc_dec, 0, nregs);
1247 #endif
1248
1249       /* Scan the instructions and record each time it would
1250          save code to put a certain register in a certain class.  */
1251
1252       if (!optimize)
1253         {
1254           frequency = REG_FREQ_MAX;
1255           for (insn = f; insn; insn = NEXT_INSN (insn))
1256             insn = scan_one_insn (insn, pass);
1257         }
1258       else
1259         FOR_EACH_BB (bb)
1260           {
1261             /* Show that an insn inside a loop is likely to be executed three
1262                times more than insns outside a loop.  This is much more
1263                aggressive than the assumptions made elsewhere and is being
1264                tried as an experiment.  */
1265             frequency = REG_FREQ_FROM_BB (bb);
1266             for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
1267               {
1268                 insn = scan_one_insn (insn, pass);
1269                 if (insn == BB_END (bb))
1270                   break;
1271               }
1272           }
1273
1274       /* Now for each register look at how desirable each class is
1275          and find which class is preferred.  Store that in
1276          `prefclass'.  Record in `altclass' the largest register
1277          class any of whose registers is better than memory.  */
1278
1279       if (pass == 0)
1280         reg_pref = reg_pref_buffer;
1281
1282       if (dump)
1283         {
1284           dump_regclass (dump);
1285           fprintf (dump,"\n");
1286         }
1287       for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++)
1288         {
1289           int best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1290           enum reg_class best = ALL_REGS, alt = NO_REGS;
1291           /* This is an enum reg_class, but we call it an int
1292              to save lots of casts.  */
1293           int class;
1294           struct costs *p = &costs[i];
1295
1296           /* In non-optimizing compilation REG_N_REFS is not initialized
1297              yet.  */
1298           if (optimize && !REG_N_REFS (i) && !REG_N_SETS (i))
1299             continue;
1300
1301           for (class = (int) ALL_REGS - 1; class > 0; class--)
1302             {
1303               /* Ignore classes that are too small for this operand or
1304                  invalid for an operand that was auto-incremented.  */
1305               if (!contains_reg_of_mode [class][PSEUDO_REGNO_MODE (i)]
1306 #ifdef FORBIDDEN_INC_DEC_CLASSES
1307                   || (in_inc_dec[i] && forbidden_inc_dec_class[class])
1308 #endif
1309 #ifdef CANNOT_CHANGE_MODE_CLASS
1310                   || invalid_mode_change_p (i, (enum reg_class) class,
1311                                             PSEUDO_REGNO_MODE (i))
1312 #endif
1313                   )
1314                 ;
1315               else if (p->cost[class] < best_cost)
1316                 {
1317                   best_cost = p->cost[class];
1318                   best = (enum reg_class) class;
1319                 }
1320               else if (p->cost[class] == best_cost)
1321                 best = reg_class_subunion[(int) best][class];
1322             }
1323
1324           /* Record the alternate register class; i.e., a class for which
1325              every register in it is better than using memory.  If adding a
1326              class would make a smaller class (i.e., no union of just those
1327              classes exists), skip that class.  The major unions of classes
1328              should be provided as a register class.  Don't do this if we
1329              will be doing it again later.  */
1330
1331           if ((pass == 1  || dump) || ! flag_expensive_optimizations)
1332             for (class = 0; class < N_REG_CLASSES; class++)
1333               if (p->cost[class] < p->mem_cost
1334                   && (reg_class_size[(int) reg_class_subunion[(int) alt][class]]
1335                       > reg_class_size[(int) alt])
1336 #ifdef FORBIDDEN_INC_DEC_CLASSES
1337                   && ! (in_inc_dec[i] && forbidden_inc_dec_class[class])
1338 #endif
1339 #ifdef CANNOT_CHANGE_MODE_CLASS
1340                   && ! invalid_mode_change_p (i, (enum reg_class) class,
1341                                               PSEUDO_REGNO_MODE (i))
1342 #endif
1343                   )
1344                 alt = reg_class_subunion[(int) alt][class];
1345
1346           /* If we don't add any classes, nothing to try.  */
1347           if (alt == best)
1348             alt = NO_REGS;
1349
1350           if (dump
1351               && (reg_pref[i].prefclass != (int) best
1352                   || reg_pref[i].altclass != (int) alt))
1353             {
1354               static const char *const reg_class_names[] = REG_CLASS_NAMES;
1355               fprintf (dump, "  Register %i", i);
1356               if (alt == ALL_REGS || best == ALL_REGS)
1357                 fprintf (dump, " pref %s\n", reg_class_names[(int) best]);
1358               else if (alt == NO_REGS)
1359                 fprintf (dump, " pref %s or none\n", reg_class_names[(int) best]);
1360               else
1361                 fprintf (dump, " pref %s, else %s\n",
1362                          reg_class_names[(int) best],
1363                          reg_class_names[(int) alt]);
1364             }
1365
1366           /* We cast to (int) because (char) hits bugs in some compilers.  */
1367           reg_pref[i].prefclass = (int) best;
1368           reg_pref[i].altclass = (int) alt;
1369         }
1370     }
1371
1372 #ifdef FORBIDDEN_INC_DEC_CLASSES
1373   free (in_inc_dec);
1374 #endif
1375   free (costs);
1376 }
1377 \f
1378 /* Record the cost of using memory or registers of various classes for
1379    the operands in INSN.
1380
1381    N_ALTS is the number of alternatives.
1382
1383    N_OPS is the number of operands.
1384
1385    OPS is an array of the operands.
1386
1387    MODES are the modes of the operands, in case any are VOIDmode.
1388
1389    CONSTRAINTS are the constraints to use for the operands.  This array
1390    is modified by this procedure.
1391
1392    This procedure works alternative by alternative.  For each alternative
1393    we assume that we will be able to allocate all pseudos to their ideal
1394    register class and calculate the cost of using that alternative.  Then
1395    we compute for each operand that is a pseudo-register, the cost of
1396    having the pseudo allocated to each register class and using it in that
1397    alternative.  To this cost is added the cost of the alternative.
1398
1399    The cost of each class for this insn is its lowest cost among all the
1400    alternatives.  */
1401
1402 static void
1403 record_reg_classes (int n_alts, int n_ops, rtx *ops,
1404                     enum machine_mode *modes, const char **constraints,
1405                     rtx insn, struct costs *op_costs,
1406                     struct reg_pref *reg_pref)
1407 {
1408   int alt;
1409   int i, j;
1410   rtx set;
1411
1412   /* Process each alternative, each time minimizing an operand's cost with
1413      the cost for each operand in that alternative.  */
1414
1415   for (alt = 0; alt < n_alts; alt++)
1416     {
1417       struct costs this_op_costs[MAX_RECOG_OPERANDS];
1418       int alt_fail = 0;
1419       int alt_cost = 0;
1420       enum reg_class classes[MAX_RECOG_OPERANDS];
1421       int allows_mem[MAX_RECOG_OPERANDS];
1422       int class;
1423
1424       for (i = 0; i < n_ops; i++)
1425         {
1426           const char *p = constraints[i];
1427           rtx op = ops[i];
1428           enum machine_mode mode = modes[i];
1429           int allows_addr = 0;
1430           int win = 0;
1431           unsigned char c;
1432
1433           /* Initially show we know nothing about the register class.  */
1434           classes[i] = NO_REGS;
1435           allows_mem[i] = 0;
1436
1437           /* If this operand has no constraints at all, we can conclude
1438              nothing about it since anything is valid.  */
1439
1440           if (*p == 0)
1441             {
1442               if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
1443                 memset (&this_op_costs[i], 0, sizeof this_op_costs[i]);
1444
1445               continue;
1446             }
1447
1448           /* If this alternative is only relevant when this operand
1449              matches a previous operand, we do different things depending
1450              on whether this operand is a pseudo-reg or not.  We must process
1451              any modifiers for the operand before we can make this test.  */
1452
1453           while (*p == '%' || *p == '=' || *p == '+' || *p == '&')
1454             p++;
1455
1456           if (p[0] >= '0' && p[0] <= '0' + i && (p[1] == ',' || p[1] == 0))
1457             {
1458               /* Copy class and whether memory is allowed from the matching
1459                  alternative.  Then perform any needed cost computations
1460                  and/or adjustments.  */
1461               j = p[0] - '0';
1462               classes[i] = classes[j];
1463               allows_mem[i] = allows_mem[j];
1464
1465               if (!REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
1466                 {
1467                   /* If this matches the other operand, we have no added
1468                      cost and we win.  */
1469                   if (rtx_equal_p (ops[j], op))
1470                     win = 1;
1471
1472                   /* If we can put the other operand into a register, add to
1473                      the cost of this alternative the cost to copy this
1474                      operand to the register used for the other operand.  */
1475
1476                   else if (classes[j] != NO_REGS)
1477                     alt_cost += copy_cost (op, mode, classes[j], 1), win = 1;
1478                 }
1479               else if (!REG_P (ops[j])
1480                        || REGNO (ops[j]) < FIRST_PSEUDO_REGISTER)
1481                 {
1482                   /* This op is a pseudo but the one it matches is not.  */
1483
1484                   /* If we can't put the other operand into a register, this
1485                      alternative can't be used.  */
1486
1487                   if (classes[j] == NO_REGS)
1488                     alt_fail = 1;
1489
1490                   /* Otherwise, add to the cost of this alternative the cost
1491                      to copy the other operand to the register used for this
1492                      operand.  */
1493
1494                   else
1495                     alt_cost += copy_cost (ops[j], mode, classes[j], 1);
1496                 }
1497               else
1498                 {
1499                   /* The costs of this operand are not the same as the other
1500                      operand since move costs are not symmetric.  Moreover,
1501                      if we cannot tie them, this alternative needs to do a
1502                      copy, which is one instruction.  */
1503
1504                   struct costs *pp = &this_op_costs[i];
1505
1506                   for (class = 0; class < N_REG_CLASSES; class++)
1507                     pp->cost[class]
1508                       = ((recog_data.operand_type[i] != OP_OUT
1509                           ? may_move_in_cost[mode][class][(int) classes[i]]
1510                           : 0)
1511                          + (recog_data.operand_type[i] != OP_IN
1512                             ? may_move_out_cost[mode][(int) classes[i]][class]
1513                             : 0));
1514
1515                   /* If the alternative actually allows memory, make things
1516                      a bit cheaper since we won't need an extra insn to
1517                      load it.  */
1518
1519                   pp->mem_cost
1520                     = ((recog_data.operand_type[i] != OP_IN
1521                         ? MEMORY_MOVE_COST (mode, classes[i], 0)
1522                         : 0)
1523                        + (recog_data.operand_type[i] != OP_OUT
1524                           ? MEMORY_MOVE_COST (mode, classes[i], 1)
1525                           : 0) - allows_mem[i]);
1526
1527                   /* If we have assigned a class to this register in our
1528                      first pass, add a cost to this alternative corresponding
1529                      to what we would add if this register were not in the
1530                      appropriate class.  */
1531
1532                   if (reg_pref)
1533                     alt_cost
1534                       += (may_move_in_cost[mode]
1535                           [(unsigned char) reg_pref[REGNO (op)].prefclass]
1536                           [(int) classes[i]]);
1537
1538                   if (REGNO (ops[i]) != REGNO (ops[j])
1539                       && ! find_reg_note (insn, REG_DEAD, op))
1540                     alt_cost += 2;
1541
1542                   /* This is in place of ordinary cost computation
1543                      for this operand, so skip to the end of the
1544                      alternative (should be just one character).  */
1545                   while (*p && *p++ != ',')
1546                     ;
1547
1548                   constraints[i] = p;
1549                   continue;
1550                 }
1551             }
1552
1553           /* Scan all the constraint letters.  See if the operand matches
1554              any of the constraints.  Collect the valid register classes
1555              and see if this operand accepts memory.  */
1556
1557           while ((c = *p))
1558             {
1559               switch (c)
1560                 {
1561                 case ',':
1562                   break;
1563                 case '*':
1564                   /* Ignore the next letter for this pass.  */
1565                   c = *++p;
1566                   break;
1567
1568                 case '?':
1569                   alt_cost += 2;
1570                 case '!':  case '#':  case '&':
1571                 case '0':  case '1':  case '2':  case '3':  case '4':
1572                 case '5':  case '6':  case '7':  case '8':  case '9':
1573                   break;
1574
1575                 case 'p':
1576                   allows_addr = 1;
1577                   win = address_operand (op, GET_MODE (op));
1578                   /* We know this operand is an address, so we want it to be
1579                      allocated to a register that can be the base of an
1580                      address, i.e. BASE_REG_CLASS.  */
1581                   classes[i]
1582                     = reg_class_subunion[(int) classes[i]]
1583                       [(int) MODE_BASE_REG_CLASS (VOIDmode)];
1584                   break;
1585
1586                 case 'm':  case 'o':  case 'V':
1587                   /* It doesn't seem worth distinguishing between offsettable
1588                      and non-offsettable addresses here.  */
1589                   allows_mem[i] = 1;
1590                   if (MEM_P (op))
1591                     win = 1;
1592                   break;
1593
1594                 case '<':
1595                   if (MEM_P (op)
1596                       && (GET_CODE (XEXP (op, 0)) == PRE_DEC
1597                           || GET_CODE (XEXP (op, 0)) == POST_DEC))
1598                     win = 1;
1599                   break;
1600
1601                 case '>':
1602                   if (MEM_P (op)
1603                       && (GET_CODE (XEXP (op, 0)) == PRE_INC
1604                           || GET_CODE (XEXP (op, 0)) == POST_INC))
1605                     win = 1;
1606                   break;
1607
1608                 case 'E':
1609                 case 'F':
1610                   if (GET_CODE (op) == CONST_DOUBLE
1611                       || (GET_CODE (op) == CONST_VECTOR
1612                           && (GET_MODE_CLASS (GET_MODE (op))
1613                               == MODE_VECTOR_FLOAT)))
1614                     win = 1;
1615                   break;
1616
1617                 case 'G':
1618                 case 'H':
1619                   if (GET_CODE (op) == CONST_DOUBLE
1620                       && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, p))
1621                     win = 1;
1622                   break;
1623
1624                 case 's':
1625                   if (GET_CODE (op) == CONST_INT
1626                       || (GET_CODE (op) == CONST_DOUBLE
1627                           && GET_MODE (op) == VOIDmode))
1628                     break;
1629                 case 'i':
1630                   if (CONSTANT_P (op)
1631                       && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op)))
1632                     win = 1;
1633                   break;
1634
1635                 case 'n':
1636                   if (GET_CODE (op) == CONST_INT
1637                       || (GET_CODE (op) == CONST_DOUBLE
1638                           && GET_MODE (op) == VOIDmode))
1639                     win = 1;
1640                   break;
1641
1642                 case 'I':
1643                 case 'J':
1644                 case 'K':
1645                 case 'L':
1646                 case 'M':
1647                 case 'N':
1648                 case 'O':
1649                 case 'P':
1650                   if (GET_CODE (op) == CONST_INT
1651                       && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, p))
1652                     win = 1;
1653                   break;
1654
1655                 case 'X':
1656                   win = 1;
1657                   break;
1658
1659                 case 'g':
1660                   if (MEM_P (op)
1661                       || (CONSTANT_P (op)
1662                           && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))))
1663                     win = 1;
1664                   allows_mem[i] = 1;
1665                 case 'r':
1666                   classes[i]
1667                     = reg_class_subunion[(int) classes[i]][(int) GENERAL_REGS];
1668                   break;
1669
1670                 default:
1671                   if (REG_CLASS_FROM_CONSTRAINT (c, p) != NO_REGS)
1672                     classes[i]
1673                       = reg_class_subunion[(int) classes[i]]
1674                         [(int) REG_CLASS_FROM_CONSTRAINT (c, p)];
1675 #ifdef EXTRA_CONSTRAINT_STR
1676                   else if (EXTRA_CONSTRAINT_STR (op, c, p))
1677                     win = 1;
1678
1679                   if (EXTRA_MEMORY_CONSTRAINT (c, p))
1680                     {
1681                       /* Every MEM can be reloaded to fit.  */
1682                       allows_mem[i] = 1;
1683                       if (MEM_P (op))
1684                         win = 1;
1685                     }
1686                   if (EXTRA_ADDRESS_CONSTRAINT (c, p))
1687                     {
1688                       /* Every address can be reloaded to fit.  */
1689                       allows_addr = 1;
1690                       if (address_operand (op, GET_MODE (op)))
1691                         win = 1;
1692                       /* We know this operand is an address, so we want it to
1693                          be allocated to a register that can be the base of an
1694                          address, i.e. BASE_REG_CLASS.  */
1695                       classes[i]
1696                         = reg_class_subunion[(int) classes[i]]
1697                           [(int) MODE_BASE_REG_CLASS (VOIDmode)];
1698                     }
1699 #endif
1700                   break;
1701                 }
1702               p += CONSTRAINT_LEN (c, p);
1703               if (c == ',')
1704                 break;
1705             }
1706
1707           constraints[i] = p;
1708
1709           /* How we account for this operand now depends on whether it is  a
1710              pseudo register or not.  If it is, we first check if any
1711              register classes are valid.  If not, we ignore this alternative,
1712              since we want to assume that all pseudos get allocated for
1713              register preferencing.  If some register class is valid, compute
1714              the costs of moving the pseudo into that class.  */
1715
1716           if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
1717             {
1718               if (classes[i] == NO_REGS)
1719                 {
1720                   /* We must always fail if the operand is a REG, but
1721                      we did not find a suitable class.
1722
1723                      Otherwise we may perform an uninitialized read
1724                      from this_op_costs after the `continue' statement
1725                      below.  */
1726                   alt_fail = 1;
1727                 }
1728               else
1729                 {
1730                   struct costs *pp = &this_op_costs[i];
1731
1732                   for (class = 0; class < N_REG_CLASSES; class++)
1733                     pp->cost[class]
1734                       = ((recog_data.operand_type[i] != OP_OUT
1735                           ? may_move_in_cost[mode][class][(int) classes[i]]
1736                           : 0)
1737                          + (recog_data.operand_type[i] != OP_IN
1738                             ? may_move_out_cost[mode][(int) classes[i]][class]
1739                             : 0));
1740
1741                   /* If the alternative actually allows memory, make things
1742                      a bit cheaper since we won't need an extra insn to
1743                      load it.  */
1744
1745                   pp->mem_cost
1746                     = ((recog_data.operand_type[i] != OP_IN
1747                         ? MEMORY_MOVE_COST (mode, classes[i], 0)
1748                         : 0)
1749                        + (recog_data.operand_type[i] != OP_OUT
1750                           ? MEMORY_MOVE_COST (mode, classes[i], 1)
1751                           : 0) - allows_mem[i]);
1752
1753                   /* If we have assigned a class to this register in our
1754                      first pass, add a cost to this alternative corresponding
1755                      to what we would add if this register were not in the
1756                      appropriate class.  */
1757
1758                   if (reg_pref)
1759                     alt_cost
1760                       += (may_move_in_cost[mode]
1761                           [(unsigned char) reg_pref[REGNO (op)].prefclass]
1762                           [(int) classes[i]]);
1763                 }
1764             }
1765
1766           /* Otherwise, if this alternative wins, either because we
1767              have already determined that or if we have a hard register of
1768              the proper class, there is no cost for this alternative.  */
1769
1770           else if (win
1771                    || (REG_P (op)
1772                        && reg_fits_class_p (op, classes[i], 0, GET_MODE (op))))
1773             ;
1774
1775           /* If registers are valid, the cost of this alternative includes
1776              copying the object to and/or from a register.  */
1777
1778           else if (classes[i] != NO_REGS)
1779             {
1780               if (recog_data.operand_type[i] != OP_OUT)
1781                 alt_cost += copy_cost (op, mode, classes[i], 1);
1782
1783               if (recog_data.operand_type[i] != OP_IN)
1784                 alt_cost += copy_cost (op, mode, classes[i], 0);
1785             }
1786
1787           /* The only other way this alternative can be used is if this is a
1788              constant that could be placed into memory.  */
1789
1790           else if (CONSTANT_P (op) && (allows_addr || allows_mem[i]))
1791             alt_cost += MEMORY_MOVE_COST (mode, classes[i], 1);
1792           else
1793             alt_fail = 1;
1794         }
1795
1796       if (alt_fail)
1797         continue;
1798
1799       /* Finally, update the costs with the information we've calculated
1800          about this alternative.  */
1801
1802       for (i = 0; i < n_ops; i++)
1803         if (REG_P (ops[i])
1804             && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
1805           {
1806             struct costs *pp = &op_costs[i], *qq = &this_op_costs[i];
1807             int scale = 1 + (recog_data.operand_type[i] == OP_INOUT);
1808
1809             pp->mem_cost = MIN (pp->mem_cost,
1810                                 (qq->mem_cost + alt_cost) * scale);
1811
1812             for (class = 0; class < N_REG_CLASSES; class++)
1813               pp->cost[class] = MIN (pp->cost[class],
1814                                      (qq->cost[class] + alt_cost) * scale);
1815           }
1816     }
1817
1818   /* If this insn is a single set copying operand 1 to operand 0
1819      and one operand is a pseudo with the other a hard reg or a pseudo
1820      that prefers a register that is in its own register class then
1821      we may want to adjust the cost of that register class to -1.
1822
1823      Avoid the adjustment if the source does not die to avoid stressing of
1824      register allocator by preferrencing two colliding registers into single
1825      class.
1826
1827      Also avoid the adjustment if a copy between registers of the class
1828      is expensive (ten times the cost of a default copy is considered
1829      arbitrarily expensive).  This avoids losing when the preferred class
1830      is very expensive as the source of a copy instruction.  */
1831
1832   if ((set = single_set (insn)) != 0
1833       && ops[0] == SET_DEST (set) && ops[1] == SET_SRC (set)
1834       && REG_P (ops[0]) && REG_P (ops[1])
1835       && find_regno_note (insn, REG_DEAD, REGNO (ops[1])))
1836     for (i = 0; i <= 1; i++)
1837       if (REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
1838         {
1839           unsigned int regno = REGNO (ops[!i]);
1840           enum machine_mode mode = GET_MODE (ops[!i]);
1841           int class;
1842           unsigned int nr;
1843
1844           if (regno >= FIRST_PSEUDO_REGISTER && reg_pref != 0)
1845             {
1846               enum reg_class pref = reg_pref[regno].prefclass;
1847
1848               if ((reg_class_size[(unsigned char) pref]
1849                    == (unsigned) CLASS_MAX_NREGS (pref, mode))
1850                   && REGISTER_MOVE_COST (mode, pref, pref) < 10 * 2)
1851                 op_costs[i].cost[(unsigned char) pref] = -1;
1852             }
1853           else if (regno < FIRST_PSEUDO_REGISTER)
1854             for (class = 0; class < N_REG_CLASSES; class++)
1855               if (TEST_HARD_REG_BIT (reg_class_contents[class], regno)
1856                   && reg_class_size[class] == (unsigned) CLASS_MAX_NREGS (class, mode))
1857                 {
1858                   if (reg_class_size[class] == 1)
1859                     op_costs[i].cost[class] = -1;
1860                   else
1861                     {
1862                       for (nr = 0; nr < (unsigned) hard_regno_nregs[regno][mode]; nr++)
1863                         {
1864                           if (! TEST_HARD_REG_BIT (reg_class_contents[class],
1865                                                    regno + nr))
1866                             break;
1867                         }
1868
1869                       if (nr == (unsigned) hard_regno_nregs[regno][mode])
1870                         op_costs[i].cost[class] = -1;
1871                     }
1872                 }
1873         }
1874 }
1875 \f
1876 /* Compute the cost of loading X into (if TO_P is nonzero) or from (if
1877    TO_P is zero) a register of class CLASS in mode MODE.
1878
1879    X must not be a pseudo.  */
1880
1881 static int
1882 copy_cost (rtx x, enum machine_mode mode ATTRIBUTE_UNUSED,
1883            enum reg_class class, int to_p ATTRIBUTE_UNUSED)
1884 {
1885 #ifdef HAVE_SECONDARY_RELOADS
1886   enum reg_class secondary_class = NO_REGS;
1887 #endif
1888
1889   /* If X is a SCRATCH, there is actually nothing to move since we are
1890      assuming optimal allocation.  */
1891
1892   if (GET_CODE (x) == SCRATCH)
1893     return 0;
1894
1895   /* Get the class we will actually use for a reload.  */
1896   class = PREFERRED_RELOAD_CLASS (x, class);
1897
1898 #ifdef HAVE_SECONDARY_RELOADS
1899   /* If we need a secondary reload (we assume here that we are using
1900      the secondary reload as an intermediate, not a scratch register), the
1901      cost is that to load the input into the intermediate register, then
1902      to copy them.  We use a special value of TO_P to avoid recursion.  */
1903
1904 #ifdef SECONDARY_INPUT_RELOAD_CLASS
1905   if (to_p == 1)
1906     secondary_class = SECONDARY_INPUT_RELOAD_CLASS (class, mode, x);
1907 #endif
1908
1909 #ifdef SECONDARY_OUTPUT_RELOAD_CLASS
1910   if (! to_p)
1911     secondary_class = SECONDARY_OUTPUT_RELOAD_CLASS (class, mode, x);
1912 #endif
1913
1914   if (secondary_class != NO_REGS)
1915     return (move_cost[mode][(int) secondary_class][(int) class]
1916             + copy_cost (x, mode, secondary_class, 2));
1917 #endif  /* HAVE_SECONDARY_RELOADS */
1918
1919   /* For memory, use the memory move cost, for (hard) registers, use the
1920      cost to move between the register classes, and use 2 for everything
1921      else (constants).  */
1922
1923   if (MEM_P (x) || class == NO_REGS)
1924     return MEMORY_MOVE_COST (mode, class, to_p);
1925
1926   else if (REG_P (x))
1927     return move_cost[mode][(int) REGNO_REG_CLASS (REGNO (x))][(int) class];
1928
1929   else
1930     /* If this is a constant, we may eventually want to call rtx_cost here.  */
1931     return COSTS_N_INSNS (1);
1932 }
1933 \f
1934 /* Record the pseudo registers we must reload into hard registers
1935    in a subexpression of a memory address, X.
1936
1937    CLASS is the class that the register needs to be in and is either
1938    BASE_REG_CLASS or INDEX_REG_CLASS.
1939
1940    SCALE is twice the amount to multiply the cost by (it is twice so we
1941    can represent half-cost adjustments).  */
1942
1943 static void
1944 record_address_regs (rtx x, enum reg_class class, int scale)
1945 {
1946   enum rtx_code code = GET_CODE (x);
1947
1948   switch (code)
1949     {
1950     case CONST_INT:
1951     case CONST:
1952     case CC0:
1953     case PC:
1954     case SYMBOL_REF:
1955     case LABEL_REF:
1956       return;
1957
1958     case PLUS:
1959       /* When we have an address that is a sum,
1960          we must determine whether registers are "base" or "index" regs.
1961          If there is a sum of two registers, we must choose one to be
1962          the "base".  Luckily, we can use the REG_POINTER to make a good
1963          choice most of the time.  We only need to do this on machines
1964          that can have two registers in an address and where the base
1965          and index register classes are different.
1966
1967          ??? This code used to set REGNO_POINTER_FLAG in some cases, but
1968          that seems bogus since it should only be set when we are sure
1969          the register is being used as a pointer.  */
1970
1971       {
1972         rtx arg0 = XEXP (x, 0);
1973         rtx arg1 = XEXP (x, 1);
1974         enum rtx_code code0 = GET_CODE (arg0);
1975         enum rtx_code code1 = GET_CODE (arg1);
1976
1977         /* Look inside subregs.  */
1978         if (code0 == SUBREG)
1979           arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
1980         if (code1 == SUBREG)
1981           arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
1982
1983         /* If this machine only allows one register per address, it must
1984            be in the first operand.  */
1985
1986         if (MAX_REGS_PER_ADDRESS == 1)
1987           record_address_regs (arg0, class, scale);
1988
1989         /* If index and base registers are the same on this machine, just
1990            record registers in any non-constant operands.  We assume here,
1991            as well as in the tests below, that all addresses are in
1992            canonical form.  */
1993
1994         else if (INDEX_REG_CLASS == MODE_BASE_REG_CLASS (VOIDmode))
1995           {
1996             record_address_regs (arg0, class, scale);
1997             if (! CONSTANT_P (arg1))
1998               record_address_regs (arg1, class, scale);
1999           }
2000
2001         /* If the second operand is a constant integer, it doesn't change
2002            what class the first operand must be.  */
2003
2004         else if (code1 == CONST_INT || code1 == CONST_DOUBLE)
2005           record_address_regs (arg0, class, scale);
2006
2007         /* If the second operand is a symbolic constant, the first operand
2008            must be an index register.  */
2009
2010         else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF)
2011           record_address_regs (arg0, INDEX_REG_CLASS, scale);
2012
2013         /* If both operands are registers but one is already a hard register
2014            of index or base class, give the other the class that the hard
2015            register is not.  */
2016
2017 #ifdef REG_OK_FOR_BASE_P
2018         else if (code0 == REG && code1 == REG
2019                  && REGNO (arg0) < FIRST_PSEUDO_REGISTER
2020                  && (REG_OK_FOR_BASE_P (arg0) || REG_OK_FOR_INDEX_P (arg0)))
2021           record_address_regs (arg1,
2022                                REG_OK_FOR_BASE_P (arg0)
2023                                ? INDEX_REG_CLASS : MODE_BASE_REG_CLASS (VOIDmode),
2024                                scale);
2025         else if (code0 == REG && code1 == REG
2026                  && REGNO (arg1) < FIRST_PSEUDO_REGISTER
2027                  && (REG_OK_FOR_BASE_P (arg1) || REG_OK_FOR_INDEX_P (arg1)))
2028           record_address_regs (arg0,
2029                                REG_OK_FOR_BASE_P (arg1)
2030                                ? INDEX_REG_CLASS : MODE_BASE_REG_CLASS (VOIDmode),
2031                                scale);
2032 #endif
2033
2034         /* If one operand is known to be a pointer, it must be the base
2035            with the other operand the index.  Likewise if the other operand
2036            is a MULT.  */
2037
2038         else if ((code0 == REG && REG_POINTER (arg0))
2039                  || code1 == MULT)
2040           {
2041             record_address_regs (arg0, MODE_BASE_REG_CLASS (VOIDmode), scale);
2042             record_address_regs (arg1, INDEX_REG_CLASS, scale);
2043           }
2044         else if ((code1 == REG && REG_POINTER (arg1))
2045                  || code0 == MULT)
2046           {
2047             record_address_regs (arg0, INDEX_REG_CLASS, scale);
2048             record_address_regs (arg1, MODE_BASE_REG_CLASS (VOIDmode), scale);
2049           }
2050
2051         /* Otherwise, count equal chances that each might be a base
2052            or index register.  This case should be rare.  */
2053
2054         else
2055           {
2056             record_address_regs (arg0, MODE_BASE_REG_CLASS (VOIDmode),
2057                                  scale / 2);
2058             record_address_regs (arg0, INDEX_REG_CLASS, scale / 2);
2059             record_address_regs (arg1, MODE_BASE_REG_CLASS (VOIDmode),
2060                                  scale / 2);
2061             record_address_regs (arg1, INDEX_REG_CLASS, scale / 2);
2062           }
2063       }
2064       break;
2065
2066       /* Double the importance of a pseudo register that is incremented
2067          or decremented, since it would take two extra insns
2068          if it ends up in the wrong place.  */
2069     case POST_MODIFY:
2070     case PRE_MODIFY:
2071       record_address_regs (XEXP (x, 0), MODE_BASE_REG_CLASS (VOIDmode),
2072                            2 * scale);
2073       if (REG_P (XEXP (XEXP (x, 1), 1)))
2074         record_address_regs (XEXP (XEXP (x, 1), 1),
2075                              INDEX_REG_CLASS, 2 * scale);
2076       break;
2077
2078     case POST_INC:
2079     case PRE_INC:
2080     case POST_DEC:
2081     case PRE_DEC:
2082       /* Double the importance of a pseudo register that is incremented
2083          or decremented, since it would take two extra insns
2084          if it ends up in the wrong place.  If the operand is a pseudo,
2085          show it is being used in an INC_DEC context.  */
2086
2087 #ifdef FORBIDDEN_INC_DEC_CLASSES
2088       if (REG_P (XEXP (x, 0))
2089           && REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER)
2090         in_inc_dec[REGNO (XEXP (x, 0))] = 1;
2091 #endif
2092
2093       record_address_regs (XEXP (x, 0), class, 2 * scale);
2094       break;
2095
2096     case REG:
2097       {
2098         struct costs *pp = &costs[REGNO (x)];
2099         int i;
2100
2101         pp->mem_cost += (MEMORY_MOVE_COST (Pmode, class, 1) * scale) / 2;
2102
2103         for (i = 0; i < N_REG_CLASSES; i++)
2104           pp->cost[i] += (may_move_in_cost[Pmode][i][(int) class] * scale) / 2;
2105       }
2106       break;
2107
2108     default:
2109       {
2110         const char *fmt = GET_RTX_FORMAT (code);
2111         int i;
2112         for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2113           if (fmt[i] == 'e')
2114             record_address_regs (XEXP (x, i), class, scale);
2115       }
2116     }
2117 }
2118 \f
2119 #ifdef FORBIDDEN_INC_DEC_CLASSES
2120
2121 /* Return 1 if REG is valid as an auto-increment memory reference
2122    to an object of MODE.  */
2123
2124 static int
2125 auto_inc_dec_reg_p (rtx reg, enum machine_mode mode)
2126 {
2127   if (HAVE_POST_INCREMENT
2128       && memory_address_p (mode, gen_rtx_POST_INC (Pmode, reg)))
2129     return 1;
2130
2131   if (HAVE_POST_DECREMENT
2132       && memory_address_p (mode, gen_rtx_POST_DEC (Pmode, reg)))
2133     return 1;
2134
2135   if (HAVE_PRE_INCREMENT
2136       && memory_address_p (mode, gen_rtx_PRE_INC (Pmode, reg)))
2137     return 1;
2138
2139   if (HAVE_PRE_DECREMENT
2140       && memory_address_p (mode, gen_rtx_PRE_DEC (Pmode, reg)))
2141     return 1;
2142
2143   return 0;
2144 }
2145 #endif
2146 \f
2147 static short *renumber;
2148 static size_t regno_allocated;
2149 static unsigned int reg_n_max;
2150
2151 /* Allocate enough space to hold NUM_REGS registers for the tables used for
2152    reg_scan and flow_analysis that are indexed by the register number.  If
2153    NEW_P is nonzero, initialize all of the registers, otherwise only
2154    initialize the new registers allocated.  The same table is kept from
2155    function to function, only reallocating it when we need more room.  If
2156    RENUMBER_P is nonzero, allocate the reg_renumber array also.  */
2157
2158 void
2159 allocate_reg_info (size_t num_regs, int new_p, int renumber_p)
2160 {
2161   size_t size_info;
2162   size_t size_renumber;
2163   size_t min = (new_p) ? 0 : reg_n_max;
2164   struct reg_info_data *reg_data;
2165
2166   if (num_regs > regno_allocated)
2167     {
2168       size_t old_allocated = regno_allocated;
2169
2170       regno_allocated = num_regs + (num_regs / 20);     /* Add some slop space.  */
2171       size_renumber = regno_allocated * sizeof (short);
2172
2173       if (!reg_n_info)
2174         {
2175           VARRAY_REG_INIT (reg_n_info, regno_allocated, "reg_n_info");
2176           renumber = xmalloc (size_renumber);
2177           reg_pref_buffer = xmalloc (regno_allocated
2178                                      * sizeof (struct reg_pref));
2179         }
2180
2181       else
2182         {
2183           VARRAY_GROW (reg_n_info, regno_allocated);
2184
2185           if (new_p)            /* If we're zapping everything, no need to realloc.  */
2186             {
2187               free ((char *) renumber);
2188               free ((char *) reg_pref);
2189               renumber = xmalloc (size_renumber);
2190               reg_pref_buffer = xmalloc (regno_allocated
2191                                          * sizeof (struct reg_pref));
2192             }
2193
2194           else
2195             {
2196               renumber = xrealloc (renumber, size_renumber);
2197               reg_pref_buffer = xrealloc (reg_pref_buffer,
2198                                           regno_allocated
2199                                           * sizeof (struct reg_pref));
2200             }
2201         }
2202
2203       size_info = (regno_allocated - old_allocated) * sizeof (reg_info)
2204         + sizeof (struct reg_info_data) - sizeof (reg_info);
2205       reg_data = xcalloc (size_info, 1);
2206       reg_data->min_index = old_allocated;
2207       reg_data->max_index = regno_allocated - 1;
2208       reg_data->next = reg_info_head;
2209       reg_info_head = reg_data;
2210     }
2211
2212   reg_n_max = num_regs;
2213   if (min < num_regs)
2214     {
2215       /* Loop through each of the segments allocated for the actual
2216          reg_info pages, and set up the pointers, zero the pages, etc.  */
2217       for (reg_data = reg_info_head;
2218            reg_data && reg_data->max_index >= min;
2219            reg_data = reg_data->next)
2220         {
2221           size_t min_index = reg_data->min_index;
2222           size_t max_index = reg_data->max_index;
2223           size_t max = MIN (max_index, num_regs);
2224           size_t local_min = min - min_index;
2225           size_t i;
2226
2227           if (reg_data->min_index > num_regs)
2228             continue;
2229
2230           if (min < min_index)
2231             local_min = 0;
2232           if (!reg_data->used_p)        /* page just allocated with calloc */
2233             reg_data->used_p = 1;       /* no need to zero */
2234           else
2235             memset (&reg_data->data[local_min], 0,
2236                     sizeof (reg_info) * (max - min_index - local_min + 1));
2237
2238           for (i = min_index+local_min; i <= max; i++)
2239             {
2240               VARRAY_REG (reg_n_info, i) = &reg_data->data[i-min_index];
2241               REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
2242               renumber[i] = -1;
2243               reg_pref_buffer[i].prefclass = (char) NO_REGS;
2244               reg_pref_buffer[i].altclass = (char) NO_REGS;
2245             }
2246         }
2247     }
2248
2249   /* If {pref,alt}class have already been allocated, update the pointers to
2250      the newly realloced ones.  */
2251   if (reg_pref)
2252     reg_pref = reg_pref_buffer;
2253
2254   if (renumber_p)
2255     reg_renumber = renumber;
2256
2257   /* Tell the regset code about the new number of registers.  */
2258   MAX_REGNO_REG_SET (num_regs, new_p, renumber_p);
2259 }
2260
2261 /* Free up the space allocated by allocate_reg_info.  */
2262 void
2263 free_reg_info (void)
2264 {
2265   if (reg_n_info)
2266     {
2267       struct reg_info_data *reg_data;
2268       struct reg_info_data *reg_next;
2269
2270       VARRAY_FREE (reg_n_info);
2271       for (reg_data = reg_info_head; reg_data; reg_data = reg_next)
2272         {
2273           reg_next = reg_data->next;
2274           free ((char *) reg_data);
2275         }
2276
2277       free (reg_pref_buffer);
2278       reg_pref_buffer = (struct reg_pref *) 0;
2279       reg_info_head = (struct reg_info_data *) 0;
2280       renumber = (short *) 0;
2281     }
2282   regno_allocated = 0;
2283   reg_n_max = 0;
2284 }
2285 \f
2286 /* This is the `regscan' pass of the compiler, run just before cse
2287    and again just before loop.
2288
2289    It finds the first and last use of each pseudo-register
2290    and records them in the vectors regno_first_uid, regno_last_uid
2291    and counts the number of sets in the vector reg_n_sets.
2292
2293    REPEAT is nonzero the second time this is called.  */
2294
2295 /* Maximum number of parallel sets and clobbers in any insn in this fn.
2296    Always at least 3, since the combiner could put that many together
2297    and we want this to remain correct for all the remaining passes.
2298    This corresponds to the maximum number of times note_stores will call
2299    a function for any insn.  */
2300
2301 int max_parallel;
2302
2303 /* Used as a temporary to record the largest number of registers in
2304    PARALLEL in a SET_DEST.  This is added to max_parallel.  */
2305
2306 static int max_set_parallel;
2307
2308 void
2309 reg_scan (rtx f, unsigned int nregs, int repeat ATTRIBUTE_UNUSED)
2310 {
2311   rtx insn;
2312
2313   timevar_push (TV_REG_SCAN);
2314
2315   allocate_reg_info (nregs, TRUE, FALSE);
2316   max_parallel = 3;
2317   max_set_parallel = 0;
2318
2319   for (insn = f; insn; insn = NEXT_INSN (insn))
2320     if (INSN_P (insn))
2321       {
2322         rtx pat = PATTERN (insn);
2323         if (GET_CODE (pat) == PARALLEL
2324             && XVECLEN (pat, 0) > max_parallel)
2325           max_parallel = XVECLEN (pat, 0);
2326         reg_scan_mark_refs (pat, insn, 0, 0);
2327
2328         if (REG_NOTES (insn))
2329           reg_scan_mark_refs (REG_NOTES (insn), insn, 1, 0);
2330       }
2331
2332   max_parallel += max_set_parallel;
2333
2334   timevar_pop (TV_REG_SCAN);
2335 }
2336
2337 /* Update 'regscan' information by looking at the insns
2338    from FIRST to LAST.  Some new REGs have been created,
2339    and any REG with number greater than OLD_MAX_REGNO is
2340    such a REG.  We only update information for those.  */
2341
2342 void
2343 reg_scan_update (rtx first, rtx last, unsigned int old_max_regno)
2344 {
2345   rtx insn;
2346
2347   allocate_reg_info (max_reg_num (), FALSE, FALSE);
2348
2349   for (insn = first; insn != last; insn = NEXT_INSN (insn))
2350     if (INSN_P (insn))
2351       {
2352         rtx pat = PATTERN (insn);
2353         if (GET_CODE (pat) == PARALLEL
2354             && XVECLEN (pat, 0) > max_parallel)
2355           max_parallel = XVECLEN (pat, 0);
2356         reg_scan_mark_refs (pat, insn, 0, old_max_regno);
2357
2358         if (REG_NOTES (insn))
2359           reg_scan_mark_refs (REG_NOTES (insn), insn, 1, old_max_regno);
2360       }
2361 }
2362
2363 /* X is the expression to scan.  INSN is the insn it appears in.
2364    NOTE_FLAG is nonzero if X is from INSN's notes rather than its body.
2365    We should only record information for REGs with numbers
2366    greater than or equal to MIN_REGNO.  */
2367
2368 static void
2369 reg_scan_mark_refs (rtx x, rtx insn, int note_flag, unsigned int min_regno)
2370 {
2371   enum rtx_code code;
2372   rtx dest;
2373   rtx note;
2374
2375   if (!x)
2376     return;
2377   code = GET_CODE (x);
2378   switch (code)
2379     {
2380     case CONST:
2381     case CONST_INT:
2382     case CONST_DOUBLE:
2383     case CONST_VECTOR:
2384     case CC0:
2385     case PC:
2386     case SYMBOL_REF:
2387     case LABEL_REF:
2388     case ADDR_VEC:
2389     case ADDR_DIFF_VEC:
2390       return;
2391
2392     case REG:
2393       {
2394         unsigned int regno = REGNO (x);
2395
2396         if (regno >= min_regno)
2397           {
2398             REGNO_LAST_NOTE_UID (regno) = INSN_UID (insn);
2399             if (!note_flag)
2400               REGNO_LAST_UID (regno) = INSN_UID (insn);
2401             if (REGNO_FIRST_UID (regno) == 0)
2402               REGNO_FIRST_UID (regno) = INSN_UID (insn);
2403             /* If we are called by reg_scan_update() (indicated by min_regno
2404                being set), we also need to update the reference count.  */
2405             if (min_regno)
2406               REG_N_REFS (regno)++;
2407           }
2408       }
2409       break;
2410
2411     case EXPR_LIST:
2412       if (XEXP (x, 0))
2413         reg_scan_mark_refs (XEXP (x, 0), insn, note_flag, min_regno);
2414       if (XEXP (x, 1))
2415         reg_scan_mark_refs (XEXP (x, 1), insn, note_flag, min_regno);
2416       break;
2417
2418     case INSN_LIST:
2419       if (XEXP (x, 1))
2420         reg_scan_mark_refs (XEXP (x, 1), insn, note_flag, min_regno);
2421       break;
2422
2423     case CLOBBER:
2424       {
2425         rtx reg = XEXP (x, 0);
2426         if (REG_P (reg)
2427             && REGNO (reg) >= min_regno)
2428           {
2429             REG_N_SETS (REGNO (reg))++;
2430             REG_N_REFS (REGNO (reg))++;
2431           }
2432         else if (MEM_P (reg))
2433           reg_scan_mark_refs (XEXP (reg, 0), insn, note_flag, min_regno);
2434       }
2435       break;
2436
2437     case SET:
2438       /* Count a set of the destination if it is a register.  */
2439       for (dest = SET_DEST (x);
2440            GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART
2441            || GET_CODE (dest) == ZERO_EXTEND;
2442            dest = XEXP (dest, 0))
2443         ;
2444
2445       /* For a PARALLEL, record the number of things (less the usual one for a
2446          SET) that are set.  */
2447       if (GET_CODE (dest) == PARALLEL)
2448         max_set_parallel = MAX (max_set_parallel, XVECLEN (dest, 0) - 1);
2449
2450       if (REG_P (dest)
2451           && REGNO (dest) >= min_regno)
2452         {
2453           REG_N_SETS (REGNO (dest))++;
2454           REG_N_REFS (REGNO (dest))++;
2455         }
2456
2457       /* If this is setting a pseudo from another pseudo or the sum of a
2458          pseudo and a constant integer and the other pseudo is known to be
2459          a pointer, set the destination to be a pointer as well.
2460
2461          Likewise if it is setting the destination from an address or from a
2462          value equivalent to an address or to the sum of an address and
2463          something else.
2464
2465          But don't do any of this if the pseudo corresponds to a user
2466          variable since it should have already been set as a pointer based
2467          on the type.  */
2468
2469       if (REG_P (SET_DEST (x))
2470           && REGNO (SET_DEST (x)) >= FIRST_PSEUDO_REGISTER
2471           && REGNO (SET_DEST (x)) >= min_regno
2472           /* If the destination pseudo is set more than once, then other
2473              sets might not be to a pointer value (consider access to a
2474              union in two threads of control in the presence of global
2475              optimizations).  So only set REG_POINTER on the destination
2476              pseudo if this is the only set of that pseudo.  */
2477           && REG_N_SETS (REGNO (SET_DEST (x))) == 1
2478           && ! REG_USERVAR_P (SET_DEST (x))
2479           && ! REG_POINTER (SET_DEST (x))
2480           && ((REG_P (SET_SRC (x))
2481                && REG_POINTER (SET_SRC (x)))
2482               || ((GET_CODE (SET_SRC (x)) == PLUS
2483                    || GET_CODE (SET_SRC (x)) == LO_SUM)
2484                   && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
2485                   && REG_P (XEXP (SET_SRC (x), 0))
2486                   && REG_POINTER (XEXP (SET_SRC (x), 0)))
2487               || GET_CODE (SET_SRC (x)) == CONST
2488               || GET_CODE (SET_SRC (x)) == SYMBOL_REF
2489               || GET_CODE (SET_SRC (x)) == LABEL_REF
2490               || (GET_CODE (SET_SRC (x)) == HIGH
2491                   && (GET_CODE (XEXP (SET_SRC (x), 0)) == CONST
2492                       || GET_CODE (XEXP (SET_SRC (x), 0)) == SYMBOL_REF
2493                       || GET_CODE (XEXP (SET_SRC (x), 0)) == LABEL_REF))
2494               || ((GET_CODE (SET_SRC (x)) == PLUS
2495                    || GET_CODE (SET_SRC (x)) == LO_SUM)
2496                   && (GET_CODE (XEXP (SET_SRC (x), 1)) == CONST
2497                       || GET_CODE (XEXP (SET_SRC (x), 1)) == SYMBOL_REF
2498                       || GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF))
2499               || ((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
2500                   && (GET_CODE (XEXP (note, 0)) == CONST
2501                       || GET_CODE (XEXP (note, 0)) == SYMBOL_REF
2502                       || GET_CODE (XEXP (note, 0)) == LABEL_REF))))
2503         REG_POINTER (SET_DEST (x)) = 1;
2504
2505       /* If this is setting a register from a register or from a simple
2506          conversion of a register, propagate REG_EXPR.  */
2507       if (REG_P (dest))
2508         {
2509           rtx src = SET_SRC (x);
2510
2511           while (GET_CODE (src) == SIGN_EXTEND
2512                  || GET_CODE (src) == ZERO_EXTEND
2513                  || GET_CODE (src) == TRUNCATE
2514                  || (GET_CODE (src) == SUBREG && subreg_lowpart_p (src)))
2515             src = XEXP (src, 0);
2516
2517           if (!REG_ATTRS (dest) && REG_P (src))
2518             REG_ATTRS (dest) = REG_ATTRS (src);
2519           if (!REG_ATTRS (dest) && MEM_P (src))
2520             set_reg_attrs_from_mem (dest, src);
2521         }
2522
2523       /* ... fall through ...  */
2524
2525     default:
2526       {
2527         const char *fmt = GET_RTX_FORMAT (code);
2528         int i;
2529         for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2530           {
2531             if (fmt[i] == 'e')
2532               reg_scan_mark_refs (XEXP (x, i), insn, note_flag, min_regno);
2533             else if (fmt[i] == 'E' && XVEC (x, i) != 0)
2534               {
2535                 int j;
2536                 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2537                   reg_scan_mark_refs (XVECEXP (x, i, j), insn, note_flag, min_regno);
2538               }
2539           }
2540       }
2541     }
2542 }
2543 \f
2544 /* Return nonzero if C1 is a subset of C2, i.e., if every register in C1
2545    is also in C2.  */
2546
2547 int
2548 reg_class_subset_p (enum reg_class c1, enum reg_class c2)
2549 {
2550   if (c1 == c2) return 1;
2551
2552   if (c2 == ALL_REGS)
2553   win:
2554     return 1;
2555   GO_IF_HARD_REG_SUBSET (reg_class_contents[(int) c1],
2556                          reg_class_contents[(int) c2],
2557                          win);
2558   return 0;
2559 }
2560
2561 /* Return nonzero if there is a register that is in both C1 and C2.  */
2562
2563 int
2564 reg_classes_intersect_p (enum reg_class c1, enum reg_class c2)
2565 {
2566   HARD_REG_SET c;
2567
2568   if (c1 == c2) return 1;
2569
2570   if (c1 == ALL_REGS || c2 == ALL_REGS)
2571     return 1;
2572
2573   COPY_HARD_REG_SET (c, reg_class_contents[(int) c1]);
2574   AND_HARD_REG_SET (c, reg_class_contents[(int) c2]);
2575
2576   GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);
2577   return 1;
2578
2579  lose:
2580   return 0;
2581 }
2582
2583 /* Release any memory allocated by register sets.  */
2584
2585 void
2586 regset_release_memory (void)
2587 {
2588   bitmap_release_memory ();
2589 }
2590
2591 #ifdef CANNOT_CHANGE_MODE_CLASS
2592
2593 struct subregs_of_mode_node
2594 {
2595   unsigned int block;
2596   unsigned char modes[MAX_MACHINE_MODE];
2597 };
2598
2599 static htab_t subregs_of_mode;
2600
2601 static hashval_t
2602 som_hash (const void *x)
2603 {
2604   const struct subregs_of_mode_node *a = x;
2605   return a->block;
2606 }
2607
2608 static int
2609 som_eq (const void *x, const void *y)
2610 {
2611   const struct subregs_of_mode_node *a = x;
2612   const struct subregs_of_mode_node *b = y;
2613   return a->block == b->block;
2614 }
2615
2616 void
2617 init_subregs_of_mode (void)
2618 {
2619   if (subregs_of_mode)
2620     htab_empty (subregs_of_mode);
2621   else
2622     subregs_of_mode = htab_create (100, som_hash, som_eq, free);
2623 }
2624
2625 void
2626 record_subregs_of_mode (rtx subreg)
2627 {
2628   struct subregs_of_mode_node dummy, *node;
2629   enum machine_mode mode;
2630   unsigned int regno;
2631   void **slot;
2632
2633   if (!REG_P (SUBREG_REG (subreg)))
2634     return;
2635
2636   regno = REGNO (SUBREG_REG (subreg));
2637   mode = GET_MODE (subreg);
2638
2639   if (regno < FIRST_PSEUDO_REGISTER)
2640     return;
2641
2642   dummy.block = regno & -8;
2643   slot = htab_find_slot_with_hash (subregs_of_mode, &dummy,
2644                                    dummy.block, INSERT);
2645   node = *slot;
2646   if (node == NULL)
2647     {
2648       node = xcalloc (1, sizeof (*node));
2649       node->block = regno & -8;
2650       *slot = node;
2651     }
2652
2653   node->modes[mode] |= 1 << (regno & 7);
2654 }
2655
2656 /* Set bits in *USED which correspond to registers which can't change
2657    their mode from FROM to any mode in which REGNO was encountered.  */
2658
2659 void
2660 cannot_change_mode_set_regs (HARD_REG_SET *used, enum machine_mode from,
2661                              unsigned int regno)
2662 {
2663   struct subregs_of_mode_node dummy, *node;
2664   enum machine_mode to;
2665   unsigned char mask;
2666   unsigned int i;
2667
2668   dummy.block = regno & -8;
2669   node = htab_find_with_hash (subregs_of_mode, &dummy, dummy.block);
2670   if (node == NULL)
2671     return;
2672
2673   mask = 1 << (regno & 7);
2674   for (to = VOIDmode; to < NUM_MACHINE_MODES; to++)
2675     if (node->modes[to] & mask)
2676       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2677         if (!TEST_HARD_REG_BIT (*used, i)
2678             && REG_CANNOT_CHANGE_MODE_P (i, from, to))
2679           SET_HARD_REG_BIT (*used, i);
2680 }
2681
2682 /* Return 1 if REGNO has had an invalid mode change in CLASS from FROM
2683    mode.  */
2684
2685 bool
2686 invalid_mode_change_p (unsigned int regno, enum reg_class class,
2687                        enum machine_mode from)
2688 {
2689   struct subregs_of_mode_node dummy, *node;
2690   enum machine_mode to;
2691   unsigned char mask;
2692
2693   dummy.block = regno & -8;
2694   node = htab_find_with_hash (subregs_of_mode, &dummy, dummy.block);
2695   if (node == NULL)
2696     return false;
2697
2698   mask = 1 << (regno & 7);
2699   for (to = VOIDmode; to < NUM_MACHINE_MODES; to++)
2700     if (node->modes[to] & mask)
2701       if (CANNOT_CHANGE_MODE_CLASS (from, to, class))
2702         return true;
2703
2704   return false;
2705 }
2706 #endif /* CANNOT_CHANGE_MODE_CLASS */
2707
2708 #include "gt-regclass.h"