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