1 /* Compute register class preferences for pseudo-registers.
2 Copyright (C) 1987, 1988, 1991, 1992, 1993, 1994, 1995, 1996
3 1997, 1998, 1999, 2000 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
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. */
31 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "insn-config.h"
44 #ifndef REGISTER_MOVE_COST
45 #define REGISTER_MOVE_COST(x, y) 2
48 static void init_reg_sets_1 PARAMS ((void));
49 static void init_reg_modes PARAMS ((void));
51 /* If we have auto-increment or auto-decrement and we can have secondary
52 reloads, we are not allowed to use classes requiring secondary
53 reloads for pseudos auto-incremented since reload can't handle it. */
56 #if defined(SECONDARY_INPUT_RELOAD_CLASS) || defined(SECONDARY_OUTPUT_RELOAD_CLASS)
57 #define FORBIDDEN_INC_DEC_CLASSES
61 /* Register tables used by many passes. */
63 /* Indexed by hard register number, contains 1 for registers
64 that are fixed use (stack pointer, pc, frame pointer, etc.).
65 These are the registers that cannot be used to allocate
66 a pseudo reg for general use. */
68 char fixed_regs[FIRST_PSEUDO_REGISTER];
70 /* Same info as a HARD_REG_SET. */
72 HARD_REG_SET fixed_reg_set;
74 /* Data for initializing the above. */
76 static char initial_fixed_regs[] = FIXED_REGISTERS;
78 /* Indexed by hard register number, contains 1 for registers
79 that are fixed use or are clobbered by function calls.
80 These are the registers that cannot be used to allocate
81 a pseudo reg whose life crosses calls unless we are able
82 to save/restore them across the calls. */
84 char call_used_regs[FIRST_PSEUDO_REGISTER];
86 /* Same info as a HARD_REG_SET. */
88 HARD_REG_SET call_used_reg_set;
90 /* HARD_REG_SET of registers we want to avoid caller saving. */
91 HARD_REG_SET losing_caller_save_reg_set;
93 /* Data for initializing the above. */
95 static char initial_call_used_regs[] = CALL_USED_REGISTERS;
97 /* Indexed by hard register number, contains 1 for registers that are
98 fixed use or call used registers that cannot hold quantities across
99 calls even if we are willing to save and restore them. call fixed
100 registers are a subset of call used registers. */
102 char call_fixed_regs[FIRST_PSEUDO_REGISTER];
104 /* The same info as a HARD_REG_SET. */
106 HARD_REG_SET call_fixed_reg_set;
108 /* Number of non-fixed registers. */
110 int n_non_fixed_regs;
112 /* Indexed by hard register number, contains 1 for registers
113 that are being used for global register decls.
114 These must be exempt from ordinary flow analysis
115 and are also considered fixed. */
117 char global_regs[FIRST_PSEUDO_REGISTER];
119 /* Table of register numbers in the order in which to try to use them. */
120 #ifdef REG_ALLOC_ORDER
121 int reg_alloc_order[FIRST_PSEUDO_REGISTER] = REG_ALLOC_ORDER;
123 /* The inverse of reg_alloc_order. */
124 int inv_reg_alloc_order[FIRST_PSEUDO_REGISTER];
127 /* For each reg class, a HARD_REG_SET saying which registers are in it. */
129 HARD_REG_SET reg_class_contents[N_REG_CLASSES];
131 /* The same information, but as an array of unsigned ints. We copy from
132 these unsigned ints to the table above. We do this so the tm.h files
133 do not have to be aware of the wordsize for machines with <= 64 regs. */
136 ((FIRST_PSEUDO_REGISTER + (HOST_BITS_PER_INT - 1)) / HOST_BITS_PER_INT)
138 static unsigned int_reg_class_contents[N_REG_CLASSES][N_REG_INTS]
139 = REG_CLASS_CONTENTS;
141 /* For each reg class, number of regs it contains. */
143 unsigned int reg_class_size[N_REG_CLASSES];
145 /* For each reg class, table listing all the containing classes. */
147 enum reg_class reg_class_superclasses[N_REG_CLASSES][N_REG_CLASSES];
149 /* For each reg class, table listing all the classes contained in it. */
151 enum reg_class reg_class_subclasses[N_REG_CLASSES][N_REG_CLASSES];
153 /* For each pair of reg classes,
154 a largest reg class contained in their union. */
156 enum reg_class reg_class_subunion[N_REG_CLASSES][N_REG_CLASSES];
158 /* For each pair of reg classes,
159 the smallest reg class containing their union. */
161 enum reg_class reg_class_superunion[N_REG_CLASSES][N_REG_CLASSES];
163 /* Array containing all of the register names. Unless
164 DEBUG_REGISTER_NAMES is defined, use the copy in print-rtl.c. */
166 #ifdef DEBUG_REGISTER_NAMES
167 const char * const reg_names[] = REGISTER_NAMES;
170 /* For each hard register, the widest mode object that it can contain.
171 This will be a MODE_INT mode if the register can hold integers. Otherwise
172 it will be a MODE_FLOAT or a MODE_CC mode, whichever is valid for the
175 enum machine_mode reg_raw_mode[FIRST_PSEUDO_REGISTER];
177 /* Maximum cost of moving from a register in one class to a register in
178 another class. Based on REGISTER_MOVE_COST. */
180 static int move_cost[N_REG_CLASSES][N_REG_CLASSES];
182 /* Similar, but here we don't have to move if the first index is a subset
183 of the second so in that case the cost is zero. */
185 static int may_move_in_cost[N_REG_CLASSES][N_REG_CLASSES];
187 /* Similar, but here we don't have to move if the first index is a superset
188 of the second so in that case the cost is zero. */
190 static int may_move_out_cost[N_REG_CLASSES][N_REG_CLASSES];
192 #ifdef FORBIDDEN_INC_DEC_CLASSES
194 /* These are the classes that regs which are auto-incremented or decremented
197 static int forbidden_inc_dec_class[N_REG_CLASSES];
199 /* Indexed by n, is non-zero if (REG n) is used in an auto-inc or auto-dec
202 static char *in_inc_dec;
204 #endif /* FORBIDDEN_INC_DEC_CLASSES */
206 #ifdef HAVE_SECONDARY_RELOADS
208 /* Sample MEM values for use by memory_move_secondary_cost. */
210 static rtx top_of_stack[MAX_MACHINE_MODE];
212 #endif /* HAVE_SECONDARY_RELOADS */
214 /* Linked list of reg_info structures allocated for reg_n_info array.
215 Grouping all of the allocated structures together in one lump
216 means only one call to bzero to clear them, rather than n smaller
218 struct reg_info_data {
219 struct reg_info_data *next; /* next set of reg_info structures */
220 size_t min_index; /* minimum index # */
221 size_t max_index; /* maximum index # */
222 char used_p; /* non-zero if this has been used previously */
223 reg_info data[1]; /* beginning of the reg_info data */
226 static struct reg_info_data *reg_info_head;
228 /* No more global register variables may be declared; true once
229 regclass has been initialized. */
231 static int no_global_reg_vars = 0;
234 /* Function called only once to initialize the above data on reg usage.
235 Once this is done, various switches may override. */
242 /* First copy the register information from the initial int form into
245 for (i = 0; i < N_REG_CLASSES; i++)
247 CLEAR_HARD_REG_SET (reg_class_contents[i]);
249 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
250 if (int_reg_class_contents[i][j / HOST_BITS_PER_INT]
251 & ((unsigned) 1 << (j % HOST_BITS_PER_INT)))
252 SET_HARD_REG_BIT (reg_class_contents[i], j);
255 bcopy (initial_fixed_regs, fixed_regs, sizeof fixed_regs);
256 bcopy (initial_call_used_regs, call_used_regs, sizeof call_used_regs);
257 bzero (global_regs, sizeof global_regs);
259 /* Do any additional initialization regsets may need */
260 INIT_ONCE_REG_SET ();
262 #ifdef REG_ALLOC_ORDER
263 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
264 inv_reg_alloc_order[reg_alloc_order[i]] = i;
268 /* After switches have been processed, which perhaps alter
269 `fixed_regs' and `call_used_regs', convert them to HARD_REG_SETs. */
274 register unsigned int i, j;
276 /* This macro allows the fixed or call-used registers
277 and the register classes to depend on target flags. */
279 #ifdef CONDITIONAL_REGISTER_USAGE
280 CONDITIONAL_REGISTER_USAGE;
283 /* Compute number of hard regs in each class. */
285 bzero ((char *) reg_class_size, sizeof reg_class_size);
286 for (i = 0; i < N_REG_CLASSES; i++)
287 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
288 if (TEST_HARD_REG_BIT (reg_class_contents[i], j))
291 /* Initialize the table of subunions.
292 reg_class_subunion[I][J] gets the largest-numbered reg-class
293 that is contained in the union of classes I and J. */
295 for (i = 0; i < N_REG_CLASSES; i++)
297 for (j = 0; j < N_REG_CLASSES; j++)
300 register /* Declare it register if it's a scalar. */
305 COPY_HARD_REG_SET (c, reg_class_contents[i]);
306 IOR_HARD_REG_SET (c, reg_class_contents[j]);
307 for (k = 0; k < N_REG_CLASSES; k++)
309 GO_IF_HARD_REG_SUBSET (reg_class_contents[k], c,
314 /* keep the largest subclass */ /* SPEE 900308 */
315 GO_IF_HARD_REG_SUBSET (reg_class_contents[k],
316 reg_class_contents[(int) reg_class_subunion[i][j]],
318 reg_class_subunion[i][j] = (enum reg_class) k;
325 /* Initialize the table of superunions.
326 reg_class_superunion[I][J] gets the smallest-numbered reg-class
327 containing the union of classes I and J. */
329 for (i = 0; i < N_REG_CLASSES; i++)
331 for (j = 0; j < N_REG_CLASSES; j++)
334 register /* Declare it register if it's a scalar. */
339 COPY_HARD_REG_SET (c, reg_class_contents[i]);
340 IOR_HARD_REG_SET (c, reg_class_contents[j]);
341 for (k = 0; k < N_REG_CLASSES; k++)
342 GO_IF_HARD_REG_SUBSET (c, reg_class_contents[k], superclass);
345 reg_class_superunion[i][j] = (enum reg_class) k;
349 /* Initialize the tables of subclasses and superclasses of each reg class.
350 First clear the whole table, then add the elements as they are found. */
352 for (i = 0; i < N_REG_CLASSES; i++)
354 for (j = 0; j < N_REG_CLASSES; j++)
356 reg_class_superclasses[i][j] = LIM_REG_CLASSES;
357 reg_class_subclasses[i][j] = LIM_REG_CLASSES;
361 for (i = 0; i < N_REG_CLASSES; i++)
363 if (i == (int) NO_REGS)
366 for (j = i + 1; j < N_REG_CLASSES; j++)
370 GO_IF_HARD_REG_SUBSET (reg_class_contents[i], reg_class_contents[j],
374 /* Reg class I is a subclass of J.
375 Add J to the table of superclasses of I. */
376 p = ®_class_superclasses[i][0];
377 while (*p != LIM_REG_CLASSES) p++;
378 *p = (enum reg_class) j;
379 /* Add I to the table of superclasses of J. */
380 p = ®_class_subclasses[j][0];
381 while (*p != LIM_REG_CLASSES) p++;
382 *p = (enum reg_class) i;
386 /* Initialize "constant" tables. */
388 CLEAR_HARD_REG_SET (fixed_reg_set);
389 CLEAR_HARD_REG_SET (call_used_reg_set);
390 CLEAR_HARD_REG_SET (call_fixed_reg_set);
392 bcopy (fixed_regs, call_fixed_regs, sizeof call_fixed_regs);
394 n_non_fixed_regs = 0;
396 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
399 SET_HARD_REG_BIT (fixed_reg_set, i);
403 if (call_used_regs[i])
404 SET_HARD_REG_BIT (call_used_reg_set, i);
405 if (call_fixed_regs[i])
406 SET_HARD_REG_BIT (call_fixed_reg_set, i);
407 if (CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (i)))
408 SET_HARD_REG_BIT (losing_caller_save_reg_set, i);
411 /* Initialize the move cost table. Find every subset of each class
412 and take the maximum cost of moving any subset to any other. */
414 for (i = 0; i < N_REG_CLASSES; i++)
415 for (j = 0; j < N_REG_CLASSES; j++)
417 int cost = i == j ? 2 : REGISTER_MOVE_COST (i, j);
418 enum reg_class *p1, *p2;
420 for (p2 = ®_class_subclasses[j][0]; *p2 != LIM_REG_CLASSES; p2++)
422 cost = MAX (cost, REGISTER_MOVE_COST (i, *p2));
424 for (p1 = ®_class_subclasses[i][0]; *p1 != LIM_REG_CLASSES; p1++)
427 cost = MAX (cost, REGISTER_MOVE_COST (*p1, j));
429 for (p2 = ®_class_subclasses[j][0];
430 *p2 != LIM_REG_CLASSES; p2++)
432 cost = MAX (cost, REGISTER_MOVE_COST (*p1, *p2));
435 move_cost[i][j] = cost;
437 if (reg_class_subset_p (i, j))
438 may_move_in_cost[i][j] = 0;
440 may_move_in_cost[i][j] = cost;
442 if (reg_class_subset_p (j, i))
443 may_move_out_cost[i][j] = 0;
445 may_move_out_cost[i][j] = cost;
449 /* Compute the table of register modes.
450 These values are used to record death information for individual registers
451 (as opposed to a multi-register mode). */
458 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
460 reg_raw_mode[i] = choose_hard_reg_mode (i, 1);
462 /* If we couldn't find a valid mode, just use the previous mode.
463 ??? One situation in which we need to do this is on the mips where
464 HARD_REGNO_NREGS (fpreg, [SD]Fmode) returns 2. Ideally we'd like
465 to use DF mode for the even registers and VOIDmode for the odd
466 (for the cpu models where the odd ones are inaccessible). */
467 if (reg_raw_mode[i] == VOIDmode)
468 reg_raw_mode[i] = i == 0 ? word_mode : reg_raw_mode[i-1];
472 /* Finish initializing the register sets and
473 initialize the register modes. */
478 /* This finishes what was started by init_reg_sets, but couldn't be done
479 until after register usage was specified. */
484 #ifdef HAVE_SECONDARY_RELOADS
486 /* Make some fake stack-frame MEM references for use in
487 memory_move_secondary_cost. */
489 for (i = 0; i < MAX_MACHINE_MODE; i++)
490 top_of_stack[i] = gen_rtx_MEM (i, stack_pointer_rtx);
491 ggc_add_rtx_root (top_of_stack, MAX_MACHINE_MODE);
496 #ifdef HAVE_SECONDARY_RELOADS
498 /* Compute extra cost of moving registers to/from memory due to reloads.
499 Only needed if secondary reloads are required for memory moves. */
502 memory_move_secondary_cost (mode, class, in)
503 enum machine_mode mode;
504 enum reg_class class;
507 enum reg_class altclass;
508 int partial_cost = 0;
509 /* We need a memory reference to feed to SECONDARY... macros. */
510 /* mem may be unused even if the SECONDARY_ macros are defined. */
511 rtx mem ATTRIBUTE_UNUSED = top_of_stack[(int) mode];
516 #ifdef SECONDARY_INPUT_RELOAD_CLASS
517 altclass = SECONDARY_INPUT_RELOAD_CLASS (class, mode, mem);
524 #ifdef SECONDARY_OUTPUT_RELOAD_CLASS
525 altclass = SECONDARY_OUTPUT_RELOAD_CLASS (class, mode, mem);
531 if (altclass == NO_REGS)
535 partial_cost = REGISTER_MOVE_COST (altclass, class);
537 partial_cost = REGISTER_MOVE_COST (class, altclass);
539 if (class == altclass)
540 /* This isn't simply a copy-to-temporary situation. Can't guess
541 what it is, so MEMORY_MOVE_COST really ought not to be calling
544 I'm tempted to put in an abort here, but returning this will
545 probably only give poor estimates, which is what we would've
546 had before this code anyways. */
549 /* Check if the secondary reload register will also need a
551 return memory_move_secondary_cost (mode, altclass, in) + partial_cost;
555 /* Return a machine mode that is legitimate for hard reg REGNO and large
556 enough to save nregs. If we can't find one, return VOIDmode. */
559 choose_hard_reg_mode (regno, nregs)
560 unsigned int regno ATTRIBUTE_UNUSED;
563 enum machine_mode found_mode = VOIDmode, mode;
565 /* We first look for the largest integer mode that can be validly
566 held in REGNO. If none, we look for the largest floating-point mode.
567 If we still didn't find a valid mode, try CCmode. */
569 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
571 mode = GET_MODE_WIDER_MODE (mode))
572 if (HARD_REGNO_NREGS (regno, mode) == nregs
573 && HARD_REGNO_MODE_OK (regno, mode))
576 if (found_mode != VOIDmode)
579 for (mode = GET_CLASS_NARROWEST_MODE (MODE_FLOAT);
581 mode = GET_MODE_WIDER_MODE (mode))
582 if (HARD_REGNO_NREGS (regno, mode) == nregs
583 && HARD_REGNO_MODE_OK (regno, mode))
586 if (found_mode != VOIDmode)
589 if (HARD_REGNO_NREGS (regno, CCmode) == nregs
590 && HARD_REGNO_MODE_OK (regno, CCmode))
593 /* We can't find a mode valid for this register. */
597 /* Specify the usage characteristics of the register named NAME.
598 It should be a fixed register if FIXED and a
599 call-used register if CALL_USED. */
602 fix_register (name, fixed, call_used)
604 int fixed, call_used;
608 /* Decode the name and update the primary form of
609 the register info. */
611 if ((i = decode_reg_name (name)) >= 0)
613 if ((i == STACK_POINTER_REGNUM
614 #ifdef HARD_FRAME_POINTER_REGNUM
615 || i == HARD_FRAME_POINTER_REGNUM
617 || i == FRAME_POINTER_REGNUM
620 && (fixed == 0 || call_used == 0))
622 static const char * const what_option[2][2] = {
623 { "call-saved", "call-used" },
624 { "no-such-option", "fixed" }};
626 error ("can't use '%s' as a %s register", name,
627 what_option[fixed][call_used]);
631 fixed_regs[i] = fixed;
632 call_used_regs[i] = call_used;
637 warning ("unknown register name: %s", name);
641 /* Mark register number I as global. */
647 if (fixed_regs[i] == 0 && no_global_reg_vars)
648 error ("global register variable follows a function definition");
652 warning ("register used for two global register variables");
656 if (call_used_regs[i] && ! fixed_regs[i])
657 warning ("call-clobbered register used for global register variable");
661 /* If already fixed, nothing else to do. */
665 fixed_regs[i] = call_used_regs[i] = call_fixed_regs[i] = 1;
668 SET_HARD_REG_BIT (fixed_reg_set, i);
669 SET_HARD_REG_BIT (call_used_reg_set, i);
670 SET_HARD_REG_BIT (call_fixed_reg_set, i);
673 /* Now the data and code for the `regclass' pass, which happens
674 just before local-alloc. */
676 /* The `costs' struct records the cost of using a hard register of each class
677 and of using memory for each pseudo. We use this data to set up
678 register class preferences. */
682 int cost[N_REG_CLASSES];
686 /* Structure used to record preferrences of given pseudo. */
689 /* (enum reg_class) prefclass is the preferred class. */
692 /* altclass is a register class that we should use for allocating
693 pseudo if no register in the preferred class is available.
694 If no register in this class is available, memory is preferred.
696 It might appear to be more general to have a bitmask of classes here,
697 but since it is recommended that there be a class corresponding to the
698 union of most major pair of classes, that generality is not required. */
702 /* Record the cost of each class for each pseudo. */
704 static struct costs *costs;
706 /* Initialized once, and used to initialize cost values for each insn. */
708 static struct costs init_cost;
710 /* Record preferrences of each pseudo.
711 This is available after `regclass' is run. */
713 static struct reg_pref *reg_pref;
715 /* Allocated buffers for reg_pref. */
717 static struct reg_pref *reg_pref_buffer;
719 /* Account for the fact that insns within a loop are executed very commonly,
720 but don't keep doing this as loops go too deep. */
722 static int loop_cost;
724 static rtx scan_one_insn PARAMS ((rtx, int));
725 static void record_operand_costs PARAMS ((rtx, struct costs *, struct reg_pref *));
726 static void dump_regclass PARAMS ((FILE *));
727 static void record_reg_classes PARAMS ((int, int, rtx *, enum machine_mode *,
728 char *, const char **, rtx,
729 struct costs *, struct reg_pref *));
730 static int copy_cost PARAMS ((rtx, enum machine_mode,
731 enum reg_class, int));
732 static void record_address_regs PARAMS ((rtx, enum reg_class, int));
733 #ifdef FORBIDDEN_INC_DEC_CLASSES
734 static int auto_inc_dec_reg_p PARAMS ((rtx, enum machine_mode));
736 static void reg_scan_mark_refs PARAMS ((rtx, rtx, int, unsigned int));
738 /* Return the reg_class in which pseudo reg number REGNO is best allocated.
739 This function is sometimes called before the info has been computed.
740 When that happens, just return GENERAL_REGS, which is innocuous. */
743 reg_preferred_class (regno)
748 return (enum reg_class) reg_pref[regno].prefclass;
752 reg_alternate_class (regno)
758 return (enum reg_class) reg_pref[regno].altclass;
761 /* Initialize some global data for this pass. */
768 init_cost.mem_cost = 10000;
769 for (i = 0; i < N_REG_CLASSES; i++)
770 init_cost.cost[i] = 10000;
772 /* This prevents dump_flow_info from losing if called
773 before regclass is run. */
776 /* No more global register variables may be declared. */
777 no_global_reg_vars = 1;
780 /* Dump register costs. */
785 static const char *const reg_class_names[] = REG_CLASS_NAMES;
787 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
789 enum reg_class class;
792 fprintf (dump, " Register %i costs:", i);
793 for (class = 0; class < N_REG_CLASSES; class++)
794 fprintf (dump, " %s:%i", reg_class_names[(int) class],
795 costs[i].cost[class]);
796 fprintf (dump, " MEM:%i\n", costs[i].mem_cost);
802 /* Calculate the costs of insn operands. */
805 record_operand_costs (insn, op_costs, reg_pref)
807 struct costs *op_costs;
808 struct reg_pref *reg_pref;
810 const char *constraints[MAX_RECOG_OPERANDS];
811 enum machine_mode modes[MAX_RECOG_OPERANDS];
812 char subreg_changes_size[MAX_RECOG_OPERANDS];
815 for (i = 0; i < recog_data.n_operands; i++)
817 constraints[i] = recog_data.constraints[i];
818 modes[i] = recog_data.operand_mode[i];
820 memset (subreg_changes_size, 0, sizeof (subreg_changes_size));
822 /* If we get here, we are set up to record the costs of all the
823 operands for this insn. Start by initializing the costs.
824 Then handle any address registers. Finally record the desired
825 classes for any pseudos, doing it twice if some pair of
826 operands are commutative. */
828 for (i = 0; i < recog_data.n_operands; i++)
830 op_costs[i] = init_cost;
832 if (GET_CODE (recog_data.operand[i]) == SUBREG)
834 rtx inner = SUBREG_REG (recog_data.operand[i]);
835 if (GET_MODE_SIZE (modes[i]) != GET_MODE_SIZE (GET_MODE (inner)))
836 subreg_changes_size[i] = 1;
837 recog_data.operand[i] = inner;
840 if (GET_CODE (recog_data.operand[i]) == MEM)
841 record_address_regs (XEXP (recog_data.operand[i], 0),
842 BASE_REG_CLASS, loop_cost * 2);
843 else if (constraints[i][0] == 'p')
844 record_address_regs (recog_data.operand[i],
845 BASE_REG_CLASS, loop_cost * 2);
848 /* Check for commutative in a separate loop so everything will
849 have been initialized. We must do this even if one operand
850 is a constant--see addsi3 in m68k.md. */
852 for (i = 0; i < (int) recog_data.n_operands - 1; i++)
853 if (constraints[i][0] == '%')
855 const char *xconstraints[MAX_RECOG_OPERANDS];
858 /* Handle commutative operands by swapping the constraints.
859 We assume the modes are the same. */
861 for (j = 0; j < recog_data.n_operands; j++)
862 xconstraints[j] = constraints[j];
864 xconstraints[i] = constraints[i+1];
865 xconstraints[i+1] = constraints[i];
866 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
867 recog_data.operand, modes, subreg_changes_size,
868 xconstraints, insn, op_costs, reg_pref);
871 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
872 recog_data.operand, modes, subreg_changes_size,
873 constraints, insn, op_costs, reg_pref);
876 /* Subroutine of regclass, processes one insn INSN. Scan it and record each
877 time it would save code to put a certain register in a certain class.
878 PASS, when nonzero, inhibits some optimizations which need only be done
880 Return the last insn processed, so that the scan can be continued from
884 scan_one_insn (insn, pass)
888 enum rtx_code code = GET_CODE (insn);
889 enum rtx_code pat_code;
892 struct costs op_costs[MAX_RECOG_OPERANDS];
894 if (GET_RTX_CLASS (code) != 'i')
897 pat_code = GET_CODE (PATTERN (insn));
899 || pat_code == CLOBBER
900 || pat_code == ASM_INPUT
901 || pat_code == ADDR_VEC
902 || pat_code == ADDR_DIFF_VEC)
905 set = single_set (insn);
908 /* If this insn loads a parameter from its stack slot, then
909 it represents a savings, rather than a cost, if the
910 parameter is stored in memory. Record this fact. */
912 if (set != 0 && GET_CODE (SET_DEST (set)) == REG
913 && GET_CODE (SET_SRC (set)) == MEM
914 && (note = find_reg_note (insn, REG_EQUIV,
916 && GET_CODE (XEXP (note, 0)) == MEM)
918 costs[REGNO (SET_DEST (set))].mem_cost
919 -= (MEMORY_MOVE_COST (GET_MODE (SET_DEST (set)),
922 record_address_regs (XEXP (SET_SRC (set), 0),
923 BASE_REG_CLASS, loop_cost * 2);
927 /* Improve handling of two-address insns such as
928 (set X (ashift CONST Y)) where CONST must be made to
929 match X. Change it into two insns: (set X CONST)
930 (set X (ashift X Y)). If we left this for reloading, it
931 would probably get three insns because X and Y might go
932 in the same place. This prevents X and Y from receiving
935 We can only do this if the modes of operands 0 and 1
936 (which might not be the same) are tieable and we only need
937 do this during our first pass. */
939 if (pass == 0 && optimize
940 && recog_data.n_operands >= 3
941 && recog_data.constraints[1][0] == '0'
942 && recog_data.constraints[1][1] == 0
943 && CONSTANT_P (recog_data.operand[1])
944 && ! rtx_equal_p (recog_data.operand[0], recog_data.operand[1])
945 && ! rtx_equal_p (recog_data.operand[0], recog_data.operand[2])
946 && GET_CODE (recog_data.operand[0]) == REG
947 && MODES_TIEABLE_P (GET_MODE (recog_data.operand[0]),
948 recog_data.operand_mode[1]))
950 rtx previnsn = prev_real_insn (insn);
952 = gen_lowpart (recog_data.operand_mode[1],
953 recog_data.operand[0]);
955 = emit_insn_before (gen_move_insn (dest, recog_data.operand[1]), insn);
957 /* If this insn was the start of a basic block,
958 include the new insn in that block.
959 We need not check for code_label here;
960 while a basic block can start with a code_label,
961 INSN could not be at the beginning of that block. */
962 if (previnsn == 0 || GET_CODE (previnsn) == JUMP_INSN)
965 for (b = 0; b < n_basic_blocks; b++)
966 if (insn == BLOCK_HEAD (b))
967 BLOCK_HEAD (b) = newinsn;
970 /* This makes one more setting of new insns's dest. */
971 REG_N_SETS (REGNO (recog_data.operand[0]))++;
973 *recog_data.operand_loc[1] = recog_data.operand[0];
974 for (i = recog_data.n_dups - 1; i >= 0; i--)
975 if (recog_data.dup_num[i] == 1)
976 *recog_data.dup_loc[i] = recog_data.operand[0];
978 return PREV_INSN (newinsn);
981 record_operand_costs (insn, op_costs, reg_pref);
983 /* Now add the cost for each operand to the total costs for
986 for (i = 0; i < recog_data.n_operands; i++)
987 if (GET_CODE (recog_data.operand[i]) == REG
988 && REGNO (recog_data.operand[i]) >= FIRST_PSEUDO_REGISTER)
990 int regno = REGNO (recog_data.operand[i]);
991 struct costs *p = &costs[regno], *q = &op_costs[i];
993 p->mem_cost += q->mem_cost * loop_cost;
994 for (j = 0; j < N_REG_CLASSES; j++)
995 p->cost[j] += q->cost[j] * loop_cost;
1001 /* This is a pass of the compiler that scans all instructions
1002 and calculates the preferred class for each pseudo-register.
1003 This information can be accessed later by calling `reg_preferred_class'.
1004 This pass comes just before local register allocation. */
1007 regclass (f, nregs, dump)
1018 costs = (struct costs *) xmalloc (nregs * sizeof (struct costs));
1020 #ifdef FORBIDDEN_INC_DEC_CLASSES
1022 in_inc_dec = (char *) xmalloc (nregs);
1024 /* Initialize information about which register classes can be used for
1025 pseudos that are auto-incremented or auto-decremented. It would
1026 seem better to put this in init_reg_sets, but we need to be able
1027 to allocate rtx, which we can't do that early. */
1029 for (i = 0; i < N_REG_CLASSES; i++)
1031 rtx r = gen_rtx_REG (VOIDmode, 0);
1032 enum machine_mode m;
1035 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1036 if (TEST_HARD_REG_BIT (reg_class_contents[i], j))
1040 for (m = VOIDmode; (int) m < (int) MAX_MACHINE_MODE;
1041 m = (enum machine_mode) ((int) m + 1))
1042 if (HARD_REGNO_MODE_OK (j, m))
1046 /* If a register is not directly suitable for an
1047 auto-increment or decrement addressing mode and
1048 requires secondary reloads, disallow its class from
1049 being used in such addresses. */
1052 #ifdef SECONDARY_RELOAD_CLASS
1053 || (SECONDARY_RELOAD_CLASS (BASE_REG_CLASS, m, r)
1056 #ifdef SECONDARY_INPUT_RELOAD_CLASS
1057 || (SECONDARY_INPUT_RELOAD_CLASS (BASE_REG_CLASS, m, r)
1060 #ifdef SECONDARY_OUTPUT_RELOAD_CLASS
1061 || (SECONDARY_OUTPUT_RELOAD_CLASS (BASE_REG_CLASS, m, r)
1066 && ! auto_inc_dec_reg_p (r, m))
1067 forbidden_inc_dec_class[i] = 1;
1071 #endif /* FORBIDDEN_INC_DEC_CLASSES */
1073 /* Normally we scan the insns once and determine the best class to use for
1074 each register. However, if -fexpensive_optimizations are on, we do so
1075 twice, the second time using the tentative best classes to guide the
1078 for (pass = 0; pass <= flag_expensive_optimizations; pass++)
1083 fprintf (dump, "\n\nPass %i\n\n",pass);
1084 /* Zero out our accumulation of the cost of each class for each reg. */
1086 bzero ((char *) costs, nregs * sizeof (struct costs));
1088 #ifdef FORBIDDEN_INC_DEC_CLASSES
1089 bzero (in_inc_dec, nregs);
1092 /* Scan the instructions and record each time it would
1093 save code to put a certain register in a certain class. */
1098 for (insn = f; insn; insn = NEXT_INSN (insn))
1099 insn = scan_one_insn (insn, pass);
1102 for (index = 0; index < n_basic_blocks; index++)
1104 basic_block bb = BASIC_BLOCK (index);
1106 /* Show that an insn inside a loop is likely to be executed three
1107 times more than insns outside a loop. This is much more
1108 aggressive than the assumptions made elsewhere and is being
1109 tried as an experiment. */
1113 loop_cost = 1 << (2 * MIN (bb->loop_depth, 5));
1114 for (insn = bb->head; ; insn = NEXT_INSN (insn))
1116 insn = scan_one_insn (insn, pass);
1117 if (insn == bb->end)
1122 /* Now for each register look at how desirable each class is
1123 and find which class is preferred. Store that in
1124 `prefclass'. Record in `altclass' the largest register
1125 class any of whose registers is better than memory. */
1128 reg_pref = reg_pref_buffer;
1132 dump_regclass (dump);
1133 fprintf (dump,"\n");
1135 for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++)
1137 register int best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1138 enum reg_class best = ALL_REGS, alt = NO_REGS;
1139 /* This is an enum reg_class, but we call it an int
1140 to save lots of casts. */
1142 register struct costs *p = &costs[i];
1144 /* In non-optimizing compilation REG_N_REFS is not initialized
1146 if (optimize && !REG_N_REFS (i))
1149 for (class = (int) ALL_REGS - 1; class > 0; class--)
1151 /* Ignore classes that are too small for this operand or
1152 invalid for a operand that was auto-incremented. */
1153 if (CLASS_MAX_NREGS (class, PSEUDO_REGNO_MODE (i))
1154 > reg_class_size[class]
1155 #ifdef FORBIDDEN_INC_DEC_CLASSES
1156 || (in_inc_dec[i] && forbidden_inc_dec_class[class])
1160 else if (p->cost[class] < best_cost)
1162 best_cost = p->cost[class];
1163 best = (enum reg_class) class;
1165 else if (p->cost[class] == best_cost)
1166 best = reg_class_subunion[(int)best][class];
1169 /* Record the alternate register class; i.e., a class for which
1170 every register in it is better than using memory. If adding a
1171 class would make a smaller class (i.e., no union of just those
1172 classes exists), skip that class. The major unions of classes
1173 should be provided as a register class. Don't do this if we
1174 will be doing it again later. */
1176 if ((pass == 1 || dump) || ! flag_expensive_optimizations)
1177 for (class = 0; class < N_REG_CLASSES; class++)
1178 if (p->cost[class] < p->mem_cost
1179 && (reg_class_size[(int) reg_class_subunion[(int) alt][class]]
1180 > reg_class_size[(int) alt])
1181 #ifdef FORBIDDEN_INC_DEC_CLASSES
1182 && ! (in_inc_dec[i] && forbidden_inc_dec_class[class])
1185 alt = reg_class_subunion[(int) alt][class];
1187 /* If we don't add any classes, nothing to try. */
1192 && (reg_pref[i].prefclass != (int) best
1193 || reg_pref[i].altclass != (int) alt))
1195 static const char *const reg_class_names[] = REG_CLASS_NAMES;
1196 fprintf (dump, " Register %i", i);
1197 if (alt == ALL_REGS || best == ALL_REGS)
1198 fprintf (dump, " pref %s\n", reg_class_names[(int) best]);
1199 else if (alt == NO_REGS)
1200 fprintf (dump, " pref %s or none\n", reg_class_names[(int) best]);
1202 fprintf (dump, " pref %s, else %s\n",
1203 reg_class_names[(int) best],
1204 reg_class_names[(int) alt]);
1207 /* We cast to (int) because (char) hits bugs in some compilers. */
1208 reg_pref[i].prefclass = (int) best;
1209 reg_pref[i].altclass = (int) alt;
1213 #ifdef FORBIDDEN_INC_DEC_CLASSES
1219 /* Record the cost of using memory or registers of various classes for
1220 the operands in INSN.
1222 N_ALTS is the number of alternatives.
1224 N_OPS is the number of operands.
1226 OPS is an array of the operands.
1228 MODES are the modes of the operands, in case any are VOIDmode.
1230 CONSTRAINTS are the constraints to use for the operands. This array
1231 is modified by this procedure.
1233 This procedure works alternative by alternative. For each alternative
1234 we assume that we will be able to allocate all pseudos to their ideal
1235 register class and calculate the cost of using that alternative. Then
1236 we compute for each operand that is a pseudo-register, the cost of
1237 having the pseudo allocated to each register class and using it in that
1238 alternative. To this cost is added the cost of the alternative.
1240 The cost of each class for this insn is its lowest cost among all the
1244 record_reg_classes (n_alts, n_ops, ops, modes, subreg_changes_size,
1245 constraints, insn, op_costs, reg_pref)
1249 enum machine_mode *modes;
1250 char *subreg_changes_size ATTRIBUTE_UNUSED;
1251 const char **constraints;
1253 struct costs *op_costs;
1254 struct reg_pref *reg_pref;
1260 /* Process each alternative, each time minimizing an operand's cost with
1261 the cost for each operand in that alternative. */
1263 for (alt = 0; alt < n_alts; alt++)
1265 struct costs this_op_costs[MAX_RECOG_OPERANDS];
1268 enum reg_class classes[MAX_RECOG_OPERANDS];
1269 int allows_mem[MAX_RECOG_OPERANDS];
1272 for (i = 0; i < n_ops; i++)
1274 const char *p = constraints[i];
1276 enum machine_mode mode = modes[i];
1277 int allows_addr = 0;
1281 /* Initially show we know nothing about the register class. */
1282 classes[i] = NO_REGS;
1285 /* If this operand has no constraints at all, we can conclude
1286 nothing about it since anything is valid. */
1290 if (GET_CODE (op) == REG && REGNO (op) >= FIRST_PSEUDO_REGISTER)
1291 bzero ((char *) &this_op_costs[i], sizeof this_op_costs[i]);
1296 /* If this alternative is only relevant when this operand
1297 matches a previous operand, we do different things depending
1298 on whether this operand is a pseudo-reg or not. We must process
1299 any modifiers for the operand before we can make this test. */
1301 while (*p == '%' || *p == '=' || *p == '+' || *p == '&')
1304 if (p[0] >= '0' && p[0] <= '0' + i && (p[1] == ',' || p[1] == 0))
1306 /* Copy class and whether memory is allowed from the matching
1307 alternative. Then perform any needed cost computations
1308 and/or adjustments. */
1310 classes[i] = classes[j];
1311 allows_mem[i] = allows_mem[j];
1313 if (GET_CODE (op) != REG || REGNO (op) < FIRST_PSEUDO_REGISTER)
1315 /* If this matches the other operand, we have no added
1317 if (rtx_equal_p (ops[j], op))
1320 /* If we can put the other operand into a register, add to
1321 the cost of this alternative the cost to copy this
1322 operand to the register used for the other operand. */
1324 else if (classes[j] != NO_REGS)
1325 alt_cost += copy_cost (op, mode, classes[j], 1), win = 1;
1327 else if (GET_CODE (ops[j]) != REG
1328 || REGNO (ops[j]) < FIRST_PSEUDO_REGISTER)
1330 /* This op is a pseudo but the one it matches is not. */
1332 /* If we can't put the other operand into a register, this
1333 alternative can't be used. */
1335 if (classes[j] == NO_REGS)
1338 /* Otherwise, add to the cost of this alternative the cost
1339 to copy the other operand to the register used for this
1343 alt_cost += copy_cost (ops[j], mode, classes[j], 1);
1347 /* The costs of this operand are not the same as the other
1348 operand since move costs are not symmetric. Moreover,
1349 if we cannot tie them, this alternative needs to do a
1350 copy, which is one instruction. */
1352 struct costs *pp = &this_op_costs[i];
1354 for (class = 0; class < N_REG_CLASSES; class++)
1356 = ((recog_data.operand_type[i] != OP_OUT
1357 ? may_move_in_cost[class][(int) classes[i]]
1359 + (recog_data.operand_type[i] != OP_IN
1360 ? may_move_out_cost[(int) classes[i]][class]
1363 /* If the alternative actually allows memory, make things
1364 a bit cheaper since we won't need an extra insn to
1368 = ((recog_data.operand_type[i] != OP_IN
1369 ? MEMORY_MOVE_COST (mode, classes[i], 0)
1371 + (recog_data.operand_type[i] != OP_OUT
1372 ? MEMORY_MOVE_COST (mode, classes[i], 1)
1373 : 0) - allows_mem[i]);
1375 /* If we have assigned a class to this register in our
1376 first pass, add a cost to this alternative corresponding
1377 to what we would add if this register were not in the
1378 appropriate class. */
1382 += (may_move_in_cost[(unsigned char) reg_pref[REGNO (op)].prefclass]
1383 [(int) classes[i]]);
1385 if (REGNO (ops[i]) != REGNO (ops[j])
1386 && ! find_reg_note (insn, REG_DEAD, op))
1389 /* This is in place of ordinary cost computation
1390 for this operand, so skip to the end of the
1391 alternative (should be just one character). */
1392 while (*p && *p++ != ',')
1400 /* Scan all the constraint letters. See if the operand matches
1401 any of the constraints. Collect the valid register classes
1402 and see if this operand accepts memory. */
1404 while (*p && (c = *p++) != ',')
1408 /* Ignore the next letter for this pass. */
1414 case '!': case '#': case '&':
1415 case '0': case '1': case '2': case '3': case '4':
1416 case '5': case '6': case '7': case '8': case '9':
1421 win = address_operand (op, GET_MODE (op));
1422 /* We know this operand is an address, so we want it to be
1423 allocated to a register that can be the base of an
1424 address, ie BASE_REG_CLASS. */
1426 = reg_class_subunion[(int) classes[i]]
1427 [(int) BASE_REG_CLASS];
1430 case 'm': case 'o': case 'V':
1431 /* It doesn't seem worth distinguishing between offsettable
1432 and non-offsettable addresses here. */
1434 if (GET_CODE (op) == MEM)
1439 if (GET_CODE (op) == MEM
1440 && (GET_CODE (XEXP (op, 0)) == PRE_DEC
1441 || GET_CODE (XEXP (op, 0)) == POST_DEC))
1446 if (GET_CODE (op) == MEM
1447 && (GET_CODE (XEXP (op, 0)) == PRE_INC
1448 || GET_CODE (XEXP (op, 0)) == POST_INC))
1453 #ifndef REAL_ARITHMETIC
1454 /* Match any floating double constant, but only if
1455 we can examine the bits of it reliably. */
1456 if ((HOST_FLOAT_FORMAT != TARGET_FLOAT_FORMAT
1457 || HOST_BITS_PER_WIDE_INT != BITS_PER_WORD)
1458 && GET_MODE (op) != VOIDmode && ! flag_pretend_float)
1461 if (GET_CODE (op) == CONST_DOUBLE)
1466 if (GET_CODE (op) == CONST_DOUBLE)
1472 if (GET_CODE (op) == CONST_DOUBLE
1473 && CONST_DOUBLE_OK_FOR_LETTER_P (op, c))
1478 if (GET_CODE (op) == CONST_INT
1479 || (GET_CODE (op) == CONST_DOUBLE
1480 && GET_MODE (op) == VOIDmode))
1484 #ifdef LEGITIMATE_PIC_OPERAND_P
1485 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
1492 if (GET_CODE (op) == CONST_INT
1493 || (GET_CODE (op) == CONST_DOUBLE
1494 && GET_MODE (op) == VOIDmode))
1506 if (GET_CODE (op) == CONST_INT
1507 && CONST_OK_FOR_LETTER_P (INTVAL (op), c))
1515 #ifdef EXTRA_CONSTRAINT
1521 if (EXTRA_CONSTRAINT (op, c))
1527 if (GET_CODE (op) == MEM
1529 #ifdef LEGITIMATE_PIC_OPERAND_P
1530 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
1537 = reg_class_subunion[(int) classes[i]][(int) GENERAL_REGS];
1542 = reg_class_subunion[(int) classes[i]]
1543 [(int) REG_CLASS_FROM_LETTER (c)];
1548 #ifdef CLASS_CANNOT_CHANGE_SIZE
1549 /* If we noted a subreg earlier, and the selected class is a
1550 subclass of CLASS_CANNOT_CHANGE_SIZE, zap it. */
1551 if (subreg_changes_size[i]
1552 && (reg_class_subunion[(int) CLASS_CANNOT_CHANGE_SIZE]
1554 == CLASS_CANNOT_CHANGE_SIZE))
1555 classes[i] = NO_REGS;
1558 /* How we account for this operand now depends on whether it is a
1559 pseudo register or not. If it is, we first check if any
1560 register classes are valid. If not, we ignore this alternative,
1561 since we want to assume that all pseudos get allocated for
1562 register preferencing. If some register class is valid, compute
1563 the costs of moving the pseudo into that class. */
1565 if (GET_CODE (op) == REG && REGNO (op) >= FIRST_PSEUDO_REGISTER)
1567 if (classes[i] == NO_REGS)
1569 /* We must always fail if the operand is a REG, but
1570 we did not find a suitable class.
1572 Otherwise we may perform an uninitialized read
1573 from this_op_costs after the `continue' statement
1579 struct costs *pp = &this_op_costs[i];
1581 for (class = 0; class < N_REG_CLASSES; class++)
1583 = ((recog_data.operand_type[i] != OP_OUT
1584 ? may_move_in_cost[class][(int) classes[i]]
1586 + (recog_data.operand_type[i] != OP_IN
1587 ? may_move_out_cost[(int) classes[i]][class]
1590 /* If the alternative actually allows memory, make things
1591 a bit cheaper since we won't need an extra insn to
1595 = ((recog_data.operand_type[i] != OP_IN
1596 ? MEMORY_MOVE_COST (mode, classes[i], 0)
1598 + (recog_data.operand_type[i] != OP_OUT
1599 ? MEMORY_MOVE_COST (mode, classes[i], 1)
1600 : 0) - allows_mem[i]);
1602 /* If we have assigned a class to this register in our
1603 first pass, add a cost to this alternative corresponding
1604 to what we would add if this register were not in the
1605 appropriate class. */
1609 += (may_move_in_cost[(unsigned char) reg_pref[REGNO (op)].prefclass]
1610 [(int) classes[i]]);
1614 /* Otherwise, if this alternative wins, either because we
1615 have already determined that or if we have a hard register of
1616 the proper class, there is no cost for this alternative. */
1619 || (GET_CODE (op) == REG
1620 && reg_fits_class_p (op, classes[i], 0, GET_MODE (op))))
1623 /* If registers are valid, the cost of this alternative includes
1624 copying the object to and/or from a register. */
1626 else if (classes[i] != NO_REGS)
1628 if (recog_data.operand_type[i] != OP_OUT)
1629 alt_cost += copy_cost (op, mode, classes[i], 1);
1631 if (recog_data.operand_type[i] != OP_IN)
1632 alt_cost += copy_cost (op, mode, classes[i], 0);
1635 /* The only other way this alternative can be used is if this is a
1636 constant that could be placed into memory. */
1638 else if (CONSTANT_P (op) && (allows_addr || allows_mem[i]))
1639 alt_cost += MEMORY_MOVE_COST (mode, classes[i], 1);
1647 /* Finally, update the costs with the information we've calculated
1648 about this alternative. */
1650 for (i = 0; i < n_ops; i++)
1651 if (GET_CODE (ops[i]) == REG
1652 && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
1654 struct costs *pp = &op_costs[i], *qq = &this_op_costs[i];
1655 int scale = 1 + (recog_data.operand_type[i] == OP_INOUT);
1657 pp->mem_cost = MIN (pp->mem_cost,
1658 (qq->mem_cost + alt_cost) * scale);
1660 for (class = 0; class < N_REG_CLASSES; class++)
1661 pp->cost[class] = MIN (pp->cost[class],
1662 (qq->cost[class] + alt_cost) * scale);
1666 /* If this insn is a single set copying operand 1 to operand 0
1667 and one operand is a pseudo with the other a hard reg or a pseudo
1668 that prefers a register that is in its own register class then
1669 we may want to adjust the cost of that register class to -1.
1671 Avoid the adjustment if the source does not die to avoid stressing of
1672 register allocator by preferrencing two coliding registers into single
1675 Also avoid the adjustment if a copy between registers of the class
1676 is expensive (ten times the cost of a default copy is considered
1677 arbitrarily expensive). This avoids losing when the preferred class
1678 is very expensive as the source of a copy instruction. */
1680 if ((set = single_set (insn)) != 0
1681 && ops[0] == SET_DEST (set) && ops[1] == SET_SRC (set)
1682 && GET_CODE (ops[0]) == REG && GET_CODE (ops[1]) == REG
1683 && find_regno_note (insn, REG_DEAD, REGNO (ops[1])))
1684 for (i = 0; i <= 1; i++)
1685 if (REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
1687 unsigned int regno = REGNO (ops[!i]);
1688 enum machine_mode mode = GET_MODE (ops[!i]);
1692 if (regno >= FIRST_PSEUDO_REGISTER && reg_pref != 0)
1694 enum reg_class pref = reg_pref[regno].prefclass;
1696 if ((reg_class_size[(unsigned char) pref]
1697 == CLASS_MAX_NREGS (pref, mode))
1698 && REGISTER_MOVE_COST (pref, pref) < 10 * 2)
1699 op_costs[i].cost[(unsigned char) pref] = -1;
1701 else if (regno < FIRST_PSEUDO_REGISTER)
1702 for (class = 0; class < N_REG_CLASSES; class++)
1703 if (TEST_HARD_REG_BIT (reg_class_contents[class], regno)
1704 && reg_class_size[class] == CLASS_MAX_NREGS (class, mode))
1706 if (reg_class_size[class] == 1)
1707 op_costs[i].cost[class] = -1;
1710 for (nr = 0; nr < HARD_REGNO_NREGS (regno, mode); nr++)
1712 if (! TEST_HARD_REG_BIT (reg_class_contents[class],
1717 if (nr == HARD_REGNO_NREGS (regno,mode))
1718 op_costs[i].cost[class] = -1;
1724 /* Compute the cost of loading X into (if TO_P is non-zero) or from (if
1725 TO_P is zero) a register of class CLASS in mode MODE.
1727 X must not be a pseudo. */
1730 copy_cost (x, mode, class, to_p)
1732 enum machine_mode mode ATTRIBUTE_UNUSED;
1733 enum reg_class class;
1734 int to_p ATTRIBUTE_UNUSED;
1736 #ifdef HAVE_SECONDARY_RELOADS
1737 enum reg_class secondary_class = NO_REGS;
1740 /* If X is a SCRATCH, there is actually nothing to move since we are
1741 assuming optimal allocation. */
1743 if (GET_CODE (x) == SCRATCH)
1746 /* Get the class we will actually use for a reload. */
1747 class = PREFERRED_RELOAD_CLASS (x, class);
1749 #ifdef HAVE_SECONDARY_RELOADS
1750 /* If we need a secondary reload (we assume here that we are using
1751 the secondary reload as an intermediate, not a scratch register), the
1752 cost is that to load the input into the intermediate register, then
1753 to copy them. We use a special value of TO_P to avoid recursion. */
1755 #ifdef SECONDARY_INPUT_RELOAD_CLASS
1757 secondary_class = SECONDARY_INPUT_RELOAD_CLASS (class, mode, x);
1760 #ifdef SECONDARY_OUTPUT_RELOAD_CLASS
1762 secondary_class = SECONDARY_OUTPUT_RELOAD_CLASS (class, mode, x);
1765 if (secondary_class != NO_REGS)
1766 return (move_cost[(int) secondary_class][(int) class]
1767 + copy_cost (x, mode, secondary_class, 2));
1768 #endif /* HAVE_SECONDARY_RELOADS */
1770 /* For memory, use the memory move cost, for (hard) registers, use the
1771 cost to move between the register classes, and use 2 for everything
1772 else (constants). */
1774 if (GET_CODE (x) == MEM || class == NO_REGS)
1775 return MEMORY_MOVE_COST (mode, class, to_p);
1777 else if (GET_CODE (x) == REG)
1778 return move_cost[(int) REGNO_REG_CLASS (REGNO (x))][(int) class];
1781 /* If this is a constant, we may eventually want to call rtx_cost here. */
1785 /* Record the pseudo registers we must reload into hard registers
1786 in a subexpression of a memory address, X.
1788 CLASS is the class that the register needs to be in and is either
1789 BASE_REG_CLASS or INDEX_REG_CLASS.
1791 SCALE is twice the amount to multiply the cost by (it is twice so we
1792 can represent half-cost adjustments). */
1795 record_address_regs (x, class, scale)
1797 enum reg_class class;
1800 register enum rtx_code code = GET_CODE (x);
1813 /* When we have an address that is a sum,
1814 we must determine whether registers are "base" or "index" regs.
1815 If there is a sum of two registers, we must choose one to be
1816 the "base". Luckily, we can use the REGNO_POINTER_FLAG
1817 to make a good choice most of the time. We only need to do this
1818 on machines that can have two registers in an address and where
1819 the base and index register classes are different.
1821 ??? This code used to set REGNO_POINTER_FLAG in some cases, but
1822 that seems bogus since it should only be set when we are sure
1823 the register is being used as a pointer. */
1826 rtx arg0 = XEXP (x, 0);
1827 rtx arg1 = XEXP (x, 1);
1828 register enum rtx_code code0 = GET_CODE (arg0);
1829 register enum rtx_code code1 = GET_CODE (arg1);
1831 /* Look inside subregs. */
1832 if (code0 == SUBREG)
1833 arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
1834 if (code1 == SUBREG)
1835 arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
1837 /* If this machine only allows one register per address, it must
1838 be in the first operand. */
1840 if (MAX_REGS_PER_ADDRESS == 1)
1841 record_address_regs (arg0, class, scale);
1843 /* If index and base registers are the same on this machine, just
1844 record registers in any non-constant operands. We assume here,
1845 as well as in the tests below, that all addresses are in
1848 else if (INDEX_REG_CLASS == BASE_REG_CLASS)
1850 record_address_regs (arg0, class, scale);
1851 if (! CONSTANT_P (arg1))
1852 record_address_regs (arg1, class, scale);
1855 /* If the second operand is a constant integer, it doesn't change
1856 what class the first operand must be. */
1858 else if (code1 == CONST_INT || code1 == CONST_DOUBLE)
1859 record_address_regs (arg0, class, scale);
1861 /* If the second operand is a symbolic constant, the first operand
1862 must be an index register. */
1864 else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF)
1865 record_address_regs (arg0, INDEX_REG_CLASS, scale);
1867 /* If both operands are registers but one is already a hard register
1868 of index or base class, give the other the class that the hard
1871 #ifdef REG_OK_FOR_BASE_P
1872 else if (code0 == REG && code1 == REG
1873 && REGNO (arg0) < FIRST_PSEUDO_REGISTER
1874 && (REG_OK_FOR_BASE_P (arg0) || REG_OK_FOR_INDEX_P (arg0)))
1875 record_address_regs (arg1,
1876 REG_OK_FOR_BASE_P (arg0)
1877 ? INDEX_REG_CLASS : BASE_REG_CLASS,
1879 else if (code0 == REG && code1 == REG
1880 && REGNO (arg1) < FIRST_PSEUDO_REGISTER
1881 && (REG_OK_FOR_BASE_P (arg1) || REG_OK_FOR_INDEX_P (arg1)))
1882 record_address_regs (arg0,
1883 REG_OK_FOR_BASE_P (arg1)
1884 ? INDEX_REG_CLASS : BASE_REG_CLASS,
1888 /* If one operand is known to be a pointer, it must be the base
1889 with the other operand the index. Likewise if the other operand
1892 else if ((code0 == REG && REGNO_POINTER_FLAG (REGNO (arg0)))
1895 record_address_regs (arg0, BASE_REG_CLASS, scale);
1896 record_address_regs (arg1, INDEX_REG_CLASS, scale);
1898 else if ((code1 == REG && REGNO_POINTER_FLAG (REGNO (arg1)))
1901 record_address_regs (arg0, INDEX_REG_CLASS, scale);
1902 record_address_regs (arg1, BASE_REG_CLASS, scale);
1905 /* Otherwise, count equal chances that each might be a base
1906 or index register. This case should be rare. */
1910 record_address_regs (arg0, BASE_REG_CLASS, scale / 2);
1911 record_address_regs (arg0, INDEX_REG_CLASS, scale / 2);
1912 record_address_regs (arg1, BASE_REG_CLASS, scale / 2);
1913 record_address_regs (arg1, INDEX_REG_CLASS, scale / 2);
1922 /* Double the importance of a pseudo register that is incremented
1923 or decremented, since it would take two extra insns
1924 if it ends up in the wrong place. If the operand is a pseudo,
1925 show it is being used in an INC_DEC context. */
1927 #ifdef FORBIDDEN_INC_DEC_CLASSES
1928 if (GET_CODE (XEXP (x, 0)) == REG
1929 && REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER)
1930 in_inc_dec[REGNO (XEXP (x, 0))] = 1;
1933 record_address_regs (XEXP (x, 0), class, 2 * scale);
1938 register struct costs *pp = &costs[REGNO (x)];
1941 pp->mem_cost += (MEMORY_MOVE_COST (Pmode, class, 1) * scale) / 2;
1943 for (i = 0; i < N_REG_CLASSES; i++)
1944 pp->cost[i] += (may_move_in_cost[i][(int) class] * scale) / 2;
1950 register const char *fmt = GET_RTX_FORMAT (code);
1952 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1954 record_address_regs (XEXP (x, i), class, scale);
1959 #ifdef FORBIDDEN_INC_DEC_CLASSES
1961 /* Return 1 if REG is valid as an auto-increment memory reference
1962 to an object of MODE. */
1965 auto_inc_dec_reg_p (reg, mode)
1967 enum machine_mode mode;
1969 if (HAVE_POST_INCREMENT
1970 && memory_address_p (mode, gen_rtx_POST_INC (Pmode, reg)))
1973 if (HAVE_POST_DECREMENT
1974 && memory_address_p (mode, gen_rtx_POST_DEC (Pmode, reg)))
1977 if (HAVE_PRE_INCREMENT
1978 && memory_address_p (mode, gen_rtx_PRE_INC (Pmode, reg)))
1981 if (HAVE_PRE_DECREMENT
1982 && memory_address_p (mode, gen_rtx_PRE_DEC (Pmode, reg)))
1989 static short *renumber;
1990 static size_t regno_allocated;
1991 static unsigned int reg_n_max;
1993 /* Allocate enough space to hold NUM_REGS registers for the tables used for
1994 reg_scan and flow_analysis that are indexed by the register number. If
1995 NEW_P is non zero, initialize all of the registers, otherwise only
1996 initialize the new registers allocated. The same table is kept from
1997 function to function, only reallocating it when we need more room. If
1998 RENUMBER_P is non zero, allocate the reg_renumber array also. */
2001 allocate_reg_info (num_regs, new_p, renumber_p)
2007 size_t size_renumber;
2008 size_t min = (new_p) ? 0 : reg_n_max;
2009 struct reg_info_data *reg_data;
2011 if (num_regs > regno_allocated)
2013 size_t old_allocated = regno_allocated;
2015 regno_allocated = num_regs + (num_regs / 20); /* add some slop space */
2016 size_renumber = regno_allocated * sizeof (short);
2020 VARRAY_REG_INIT (reg_n_info, regno_allocated, "reg_n_info");
2021 renumber = (short *) xmalloc (size_renumber);
2022 reg_pref_buffer = (struct reg_pref *) xmalloc (regno_allocated
2023 * sizeof (struct reg_pref));
2028 VARRAY_GROW (reg_n_info, regno_allocated);
2030 if (new_p) /* if we're zapping everything, no need to realloc */
2032 free ((char *)renumber);
2033 free ((char *)reg_pref);
2034 renumber = (short *) xmalloc (size_renumber);
2035 reg_pref_buffer = (struct reg_pref *) xmalloc (regno_allocated
2036 * sizeof (struct reg_pref));
2041 renumber = (short *) xrealloc ((char *)renumber, size_renumber);
2042 reg_pref_buffer = (struct reg_pref *) xrealloc ((char *)reg_pref_buffer,
2044 * sizeof (struct reg_pref));
2048 size_info = (regno_allocated - old_allocated) * sizeof (reg_info)
2049 + sizeof (struct reg_info_data) - sizeof (reg_info);
2050 reg_data = (struct reg_info_data *) xcalloc (size_info, 1);
2051 reg_data->min_index = old_allocated;
2052 reg_data->max_index = regno_allocated - 1;
2053 reg_data->next = reg_info_head;
2054 reg_info_head = reg_data;
2057 reg_n_max = num_regs;
2060 /* Loop through each of the segments allocated for the actual
2061 reg_info pages, and set up the pointers, zero the pages, etc. */
2062 for (reg_data = reg_info_head;
2063 reg_data && reg_data->max_index >= min;
2064 reg_data = reg_data->next)
2066 size_t min_index = reg_data->min_index;
2067 size_t max_index = reg_data->max_index;
2068 size_t max = MIN (max_index, num_regs);
2069 size_t local_min = min - min_index;
2072 if (reg_data->min_index > num_regs)
2075 if (min < min_index)
2077 if (!reg_data->used_p) /* page just allocated with calloc */
2078 reg_data->used_p = 1; /* no need to zero */
2080 bzero ((char *) ®_data->data[local_min],
2081 sizeof (reg_info) * (max - min_index - local_min + 1));
2083 for (i = min_index+local_min; i <= max; i++)
2085 VARRAY_REG (reg_n_info, i) = ®_data->data[i-min_index];
2086 REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
2088 reg_pref_buffer[i].prefclass = (char) NO_REGS;
2089 reg_pref_buffer[i].altclass = (char) NO_REGS;
2094 /* If {pref,alt}class have already been allocated, update the pointers to
2095 the newly realloced ones. */
2097 reg_pref = reg_pref_buffer;
2100 reg_renumber = renumber;
2102 /* Tell the regset code about the new number of registers */
2103 MAX_REGNO_REG_SET (num_regs, new_p, renumber_p);
2106 /* Free up the space allocated by allocate_reg_info. */
2112 struct reg_info_data *reg_data;
2113 struct reg_info_data *reg_next;
2115 VARRAY_FREE (reg_n_info);
2116 for (reg_data = reg_info_head; reg_data; reg_data = reg_next)
2118 reg_next = reg_data->next;
2119 free ((char *)reg_data);
2122 free (reg_pref_buffer);
2123 reg_pref_buffer = (struct reg_pref *)0;
2124 reg_info_head = (struct reg_info_data *)0;
2125 renumber = (short *)0;
2127 regno_allocated = 0;
2131 /* This is the `regscan' pass of the compiler, run just before cse
2132 and again just before loop.
2134 It finds the first and last use of each pseudo-register
2135 and records them in the vectors regno_first_uid, regno_last_uid
2136 and counts the number of sets in the vector reg_n_sets.
2138 REPEAT is nonzero the second time this is called. */
2140 /* Maximum number of parallel sets and clobbers in any insn in this fn.
2141 Always at least 3, since the combiner could put that many together
2142 and we want this to remain correct for all the remaining passes. */
2147 reg_scan (f, nregs, repeat)
2150 int repeat ATTRIBUTE_UNUSED;
2154 allocate_reg_info (nregs, TRUE, FALSE);
2157 for (insn = f; insn; insn = NEXT_INSN (insn))
2158 if (GET_CODE (insn) == INSN
2159 || GET_CODE (insn) == CALL_INSN
2160 || GET_CODE (insn) == JUMP_INSN)
2162 if (GET_CODE (PATTERN (insn)) == PARALLEL
2163 && XVECLEN (PATTERN (insn), 0) > max_parallel)
2164 max_parallel = XVECLEN (PATTERN (insn), 0);
2165 reg_scan_mark_refs (PATTERN (insn), insn, 0, 0);
2167 if (REG_NOTES (insn))
2168 reg_scan_mark_refs (REG_NOTES (insn), insn, 1, 0);
2172 /* Update 'regscan' information by looking at the insns
2173 from FIRST to LAST. Some new REGs have been created,
2174 and any REG with number greater than OLD_MAX_REGNO is
2175 such a REG. We only update information for those. */
2178 reg_scan_update (first, last, old_max_regno)
2181 unsigned int old_max_regno;
2185 allocate_reg_info (max_reg_num (), FALSE, FALSE);
2187 for (insn = first; insn != last; insn = NEXT_INSN (insn))
2188 if (GET_CODE (insn) == INSN
2189 || GET_CODE (insn) == CALL_INSN
2190 || GET_CODE (insn) == JUMP_INSN)
2192 if (GET_CODE (PATTERN (insn)) == PARALLEL
2193 && XVECLEN (PATTERN (insn), 0) > max_parallel)
2194 max_parallel = XVECLEN (PATTERN (insn), 0);
2195 reg_scan_mark_refs (PATTERN (insn), insn, 0, old_max_regno);
2197 if (REG_NOTES (insn))
2198 reg_scan_mark_refs (REG_NOTES (insn), insn, 1, old_max_regno);
2202 /* X is the expression to scan. INSN is the insn it appears in.
2203 NOTE_FLAG is nonzero if X is from INSN's notes rather than its body.
2204 We should only record information for REGs with numbers
2205 greater than or equal to MIN_REGNO. */
2208 reg_scan_mark_refs (x, insn, note_flag, min_regno)
2212 unsigned int min_regno;
2214 register enum rtx_code code;
2218 code = GET_CODE (x);
2234 unsigned int regno = REGNO (x);
2236 if (regno >= min_regno)
2238 REGNO_LAST_NOTE_UID (regno) = INSN_UID (insn);
2240 REGNO_LAST_UID (regno) = INSN_UID (insn);
2241 if (REGNO_FIRST_UID (regno) == 0)
2242 REGNO_FIRST_UID (regno) = INSN_UID (insn);
2249 reg_scan_mark_refs (XEXP (x, 0), insn, note_flag, min_regno);
2251 reg_scan_mark_refs (XEXP (x, 1), insn, note_flag, min_regno);
2256 reg_scan_mark_refs (XEXP (x, 1), insn, note_flag, min_regno);
2260 /* Count a set of the destination if it is a register. */
2261 for (dest = SET_DEST (x);
2262 GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART
2263 || GET_CODE (dest) == ZERO_EXTEND;
2264 dest = XEXP (dest, 0))
2267 if (GET_CODE (dest) == REG
2268 && REGNO (dest) >= min_regno)
2269 REG_N_SETS (REGNO (dest))++;
2271 /* If this is setting a pseudo from another pseudo or the sum of a
2272 pseudo and a constant integer and the other pseudo is known to be
2273 a pointer, set the destination to be a pointer as well.
2275 Likewise if it is setting the destination from an address or from a
2276 value equivalent to an address or to the sum of an address and
2279 But don't do any of this if the pseudo corresponds to a user
2280 variable since it should have already been set as a pointer based
2283 if (GET_CODE (SET_DEST (x)) == REG
2284 && REGNO (SET_DEST (x)) >= FIRST_PSEUDO_REGISTER
2285 && REGNO (SET_DEST (x)) >= min_regno
2286 /* If the destination pseudo is set more than once, then other
2287 sets might not be to a pointer value (consider access to a
2288 union in two threads of control in the presense of global
2289 optimizations). So only set REGNO_POINTER_FLAG on the destination
2290 pseudo if this is the only set of that pseudo. */
2291 && REG_N_SETS (REGNO (SET_DEST (x))) == 1
2292 && ! REG_USERVAR_P (SET_DEST (x))
2293 && ! REGNO_POINTER_FLAG (REGNO (SET_DEST (x)))
2294 && ((GET_CODE (SET_SRC (x)) == REG
2295 && REGNO_POINTER_FLAG (REGNO (SET_SRC (x))))
2296 || ((GET_CODE (SET_SRC (x)) == PLUS
2297 || GET_CODE (SET_SRC (x)) == LO_SUM)
2298 && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
2299 && GET_CODE (XEXP (SET_SRC (x), 0)) == REG
2300 && REGNO_POINTER_FLAG (REGNO (XEXP (SET_SRC (x), 0))))
2301 || GET_CODE (SET_SRC (x)) == CONST
2302 || GET_CODE (SET_SRC (x)) == SYMBOL_REF
2303 || GET_CODE (SET_SRC (x)) == LABEL_REF
2304 || (GET_CODE (SET_SRC (x)) == HIGH
2305 && (GET_CODE (XEXP (SET_SRC (x), 0)) == CONST
2306 || GET_CODE (XEXP (SET_SRC (x), 0)) == SYMBOL_REF
2307 || GET_CODE (XEXP (SET_SRC (x), 0)) == LABEL_REF))
2308 || ((GET_CODE (SET_SRC (x)) == PLUS
2309 || GET_CODE (SET_SRC (x)) == LO_SUM)
2310 && (GET_CODE (XEXP (SET_SRC (x), 1)) == CONST
2311 || GET_CODE (XEXP (SET_SRC (x), 1)) == SYMBOL_REF
2312 || GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF))
2313 || ((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
2314 && (GET_CODE (XEXP (note, 0)) == CONST
2315 || GET_CODE (XEXP (note, 0)) == SYMBOL_REF
2316 || GET_CODE (XEXP (note, 0)) == LABEL_REF))))
2317 REGNO_POINTER_FLAG (REGNO (SET_DEST (x))) = 1;
2319 /* ... fall through ... */
2323 register const char *fmt = GET_RTX_FORMAT (code);
2325 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2328 reg_scan_mark_refs (XEXP (x, i), insn, note_flag, min_regno);
2329 else if (fmt[i] == 'E' && XVEC (x, i) != 0)
2332 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2333 reg_scan_mark_refs (XVECEXP (x, i, j), insn, note_flag, min_regno);
2340 /* Return nonzero if C1 is a subset of C2, i.e., if every register in C1
2344 reg_class_subset_p (c1, c2)
2345 register enum reg_class c1;
2346 register enum reg_class c2;
2348 if (c1 == c2) return 1;
2353 GO_IF_HARD_REG_SUBSET (reg_class_contents[(int)c1],
2354 reg_class_contents[(int)c2],
2359 /* Return nonzero if there is a register that is in both C1 and C2. */
2362 reg_classes_intersect_p (c1, c2)
2363 register enum reg_class c1;
2364 register enum reg_class c2;
2371 if (c1 == c2) return 1;
2373 if (c1 == ALL_REGS || c2 == ALL_REGS)
2376 COPY_HARD_REG_SET (c, reg_class_contents[(int) c1]);
2377 AND_HARD_REG_SET (c, reg_class_contents[(int) c2]);
2379 GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);
2386 /* Release any memory allocated by register sets. */
2389 regset_release_memory ()
2391 bitmap_release_memory ();