1 /* Compute register class preferences for pseudo-registers.
2 Copyright (C) 1987, 1988, 1991, 1992 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
21 /* This file contains two passes of the compiler: reg_scan and reg_class.
22 It also defines some tables of information about the hardware registers
23 and a function init_reg_sets to initialize the tables. */
27 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "insn-config.h"
36 #ifndef REGISTER_MOVE_COST
37 #define REGISTER_MOVE_COST(x, y) 2
40 #ifndef MEMORY_MOVE_COST
41 #define MEMORY_MOVE_COST(x) 4
44 /* Register tables used by many passes. */
46 /* Indexed by hard register number, contains 1 for registers
47 that are fixed use (stack pointer, pc, frame pointer, etc.).
48 These are the registers that cannot be used to allocate
49 a pseudo reg whose life does not cross calls. */
51 char fixed_regs[FIRST_PSEUDO_REGISTER];
53 /* Same info as a HARD_REG_SET. */
55 HARD_REG_SET fixed_reg_set;
57 /* Data for initializing the above. */
59 static char initial_fixed_regs[] = FIXED_REGISTERS;
61 /* Indexed by hard register number, contains 1 for registers
62 that are fixed use or are clobbered by function calls.
63 These are the registers that cannot be used to allocate
64 a pseudo reg whose life crosses calls. */
66 char call_used_regs[FIRST_PSEUDO_REGISTER];
68 /* Same info as a HARD_REG_SET. */
70 HARD_REG_SET call_used_reg_set;
72 /* Data for initializing the above. */
74 static char initial_call_used_regs[] = CALL_USED_REGISTERS;
76 /* Indexed by hard register number, contains 1 for registers that are
77 fixed use -- i.e. in fixed_regs -- or a function value return register
78 or STRUCT_VALUE_REGNUM or STATIC_CHAIN_REGNUM. These are the
79 registers that cannot hold quantities across calls even if we are
80 willing to save and restore them. */
82 char call_fixed_regs[FIRST_PSEUDO_REGISTER];
84 /* The same info as a HARD_REG_SET. */
86 HARD_REG_SET call_fixed_reg_set;
88 /* Number of non-fixed registers. */
92 /* Indexed by hard register number, contains 1 for registers
93 that are being used for global register decls.
94 These must be exempt from ordinary flow analysis
95 and are also considered fixed. */
97 char global_regs[FIRST_PSEUDO_REGISTER];
99 /* Table of register numbers in the order in which to try to use them. */
100 #ifdef REG_ALLOC_ORDER
101 int reg_alloc_order[FIRST_PSEUDO_REGISTER] = REG_ALLOC_ORDER;
104 /* For each reg class, a HARD_REG_SET saying which registers are in it. */
106 HARD_REG_SET reg_class_contents[] = REG_CLASS_CONTENTS;
108 /* For each reg class, number of regs it contains. */
110 int reg_class_size[N_REG_CLASSES];
112 /* For each reg class, table listing all the containing classes. */
114 enum reg_class reg_class_superclasses[N_REG_CLASSES][N_REG_CLASSES];
116 /* For each reg class, table listing all the classes contained in it. */
118 enum reg_class reg_class_subclasses[N_REG_CLASSES][N_REG_CLASSES];
120 /* For each pair of reg classes,
121 a largest reg class contained in their union. */
123 enum reg_class reg_class_subunion[N_REG_CLASSES][N_REG_CLASSES];
125 /* For each pair of reg classes,
126 the smallest reg class containing their union. */
128 enum reg_class reg_class_superunion[N_REG_CLASSES][N_REG_CLASSES];
130 /* Array containing all of the register names */
132 char *reg_names[] = REGISTER_NAMES;
134 /* Indexed by n, gives number of times (REG n) is set or clobbered.
135 This information remains valid for the rest of the compilation
136 of the current function; it is used to control register allocation.
138 This information applies to both hard registers and pseudo registers,
139 unlike much of the information above. */
143 /* Maximum cost of moving from a register in one class to a register in
144 another class. Based on REGISTER_MOVE_COST. */
146 static int move_cost[N_REG_CLASSES][N_REG_CLASSES];
148 /* Similar, but here we don't have to move if the first index is a subset
149 of the second so in that case the cost is zero. */
151 static int may_move_cost[N_REG_CLASSES][N_REG_CLASSES];
153 /* Function called only once to initialize the above data on reg usage.
154 Once this is done, various switches may override. */
161 bcopy (initial_fixed_regs, fixed_regs, sizeof fixed_regs);
162 bcopy (initial_call_used_regs, call_used_regs, sizeof call_used_regs);
163 bzero (global_regs, sizeof global_regs);
165 /* Compute number of hard regs in each class. */
167 bzero (reg_class_size, sizeof reg_class_size);
168 for (i = 0; i < N_REG_CLASSES; i++)
169 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
170 if (TEST_HARD_REG_BIT (reg_class_contents[i], j))
173 /* Initialize the table of subunions.
174 reg_class_subunion[I][J] gets the largest-numbered reg-class
175 that is contained in the union of classes I and J. */
177 for (i = 0; i < N_REG_CLASSES; i++)
179 for (j = 0; j < N_REG_CLASSES; j++)
182 register /* Declare it register if it's a scalar. */
187 COPY_HARD_REG_SET (c, reg_class_contents[i]);
188 IOR_HARD_REG_SET (c, reg_class_contents[j]);
189 for (k = 0; k < N_REG_CLASSES; k++)
191 GO_IF_HARD_REG_SUBSET (reg_class_contents[k], c,
196 /* keep the largest subclass */ /* SPEE 900308 */
197 GO_IF_HARD_REG_SUBSET (reg_class_contents[k],
198 reg_class_contents[(int) reg_class_subunion[i][j]],
200 reg_class_subunion[i][j] = (enum reg_class) k;
207 /* Initialize the table of superunions.
208 reg_class_superunion[I][J] gets the smallest-numbered reg-class
209 containing the union of classes I and J. */
211 for (i = 0; i < N_REG_CLASSES; i++)
213 for (j = 0; j < N_REG_CLASSES; j++)
216 register /* Declare it register if it's a scalar. */
221 COPY_HARD_REG_SET (c, reg_class_contents[i]);
222 IOR_HARD_REG_SET (c, reg_class_contents[j]);
223 for (k = 0; k < N_REG_CLASSES; k++)
224 GO_IF_HARD_REG_SUBSET (c, reg_class_contents[k], superclass);
227 reg_class_superunion[i][j] = (enum reg_class) k;
231 /* Initialize the tables of subclasses and superclasses of each reg class.
232 First clear the whole table, then add the elements as they are found. */
234 for (i = 0; i < N_REG_CLASSES; i++)
236 for (j = 0; j < N_REG_CLASSES; j++)
238 reg_class_superclasses[i][j] = LIM_REG_CLASSES;
239 reg_class_subclasses[i][j] = LIM_REG_CLASSES;
243 for (i = 0; i < N_REG_CLASSES; i++)
245 if (i == (int) NO_REGS)
248 for (j = i + 1; j < N_REG_CLASSES; j++)
252 GO_IF_HARD_REG_SUBSET (reg_class_contents[i], reg_class_contents[j],
256 /* Reg class I is a subclass of J.
257 Add J to the table of superclasses of I. */
258 p = ®_class_superclasses[i][0];
259 while (*p != LIM_REG_CLASSES) p++;
260 *p = (enum reg_class) j;
261 /* Add I to the table of superclasses of J. */
262 p = ®_class_subclasses[j][0];
263 while (*p != LIM_REG_CLASSES) p++;
264 *p = (enum reg_class) i;
268 /* Initialize the move cost table. Find every subset of each class
269 and take the maximum cost of moving any subset to any other. */
271 for (i = 0; i < N_REG_CLASSES; i++)
272 for (j = 0; j < N_REG_CLASSES; j++)
274 int cost = i == j ? 2 : REGISTER_MOVE_COST (i, j);
275 enum reg_class *p1, *p2;
277 for (p2 = ®_class_subclasses[j][0]; *p2 != LIM_REG_CLASSES; p2++)
279 cost = MAX (cost, REGISTER_MOVE_COST (i, *p2));
281 for (p1 = ®_class_subclasses[i][0]; *p1 != LIM_REG_CLASSES; p1++)
284 cost = MAX (cost, REGISTER_MOVE_COST (*p1, j));
286 for (p2 = ®_class_subclasses[j][0];
287 *p2 != LIM_REG_CLASSES; p2++)
289 cost = MAX (cost, REGISTER_MOVE_COST (*p1, *p2));
292 move_cost[i][j] = cost;
294 if (reg_class_subset_p (i, j))
297 may_move_cost[i][j] = cost;
301 /* After switches have been processed, which perhaps alter
302 `fixed_regs' and `call_used_regs', convert them to HARD_REG_SETs. */
309 /* This macro allows the fixed or call-used registers
310 to depend on target flags. */
312 #ifdef CONDITIONAL_REGISTER_USAGE
313 CONDITIONAL_REGISTER_USAGE;
316 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
319 if (call_used_regs[i] && ! fixed_regs[i])
320 warning ("call-clobbered register used for global register variable");
322 /* Prevent saving/restoring of this reg. */
323 call_used_regs[i] = 1;
326 /* Initialize "constant" tables. */
328 CLEAR_HARD_REG_SET (fixed_reg_set);
329 CLEAR_HARD_REG_SET (call_used_reg_set);
330 CLEAR_HARD_REG_SET (call_fixed_reg_set);
332 bcopy (fixed_regs, call_fixed_regs, sizeof call_fixed_regs);
333 #ifdef STRUCT_VALUE_REGNUM
334 call_fixed_regs[STRUCT_VALUE_REGNUM] = 1;
336 #ifdef STATIC_CHAIN_REGNUM
337 call_fixed_regs[STATIC_CHAIN_REGNUM] = 1;
340 n_non_fixed_regs = 0;
342 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
344 if (FUNCTION_VALUE_REGNO_P (i))
345 call_fixed_regs[i] = 1;
347 SET_HARD_REG_BIT (fixed_reg_set, i);
351 if (call_used_regs[i])
352 SET_HARD_REG_BIT (call_used_reg_set, i);
353 if (call_fixed_regs[i])
354 SET_HARD_REG_BIT (call_fixed_reg_set, i);
358 /* Specify the usage characteristics of the register named NAME.
359 It should be a fixed register if FIXED and a
360 call-used register if CALL_USED. */
363 fix_register (name, fixed, call_used)
365 int fixed, call_used;
369 /* Decode the name and update the primary form of
370 the register info. */
372 if ((i = decode_reg_name (name)) >= 0)
374 fixed_regs[i] = fixed;
375 call_used_regs[i] = call_used;
379 warning ("unknown register name: %s", name);
383 /* Now the data and code for the `regclass' pass, which happens
384 just before local-alloc. */
386 /* The `costs' struct records the cost of using a hard register of each class
387 and of using memory for each pseudo. We use this data to set up
388 register class preferences. */
392 int cost[N_REG_CLASSES];
396 /* Record the cost of each class for each pseudo. */
398 static struct costs *costs;
400 /* Record the same data by operand number, accumulated for each alternative
401 in an insn. The contribution to a pseudo is that of the minimum-cost
404 static struct costs op_costs[MAX_RECOG_OPERANDS];
406 /* (enum reg_class) prefclass[R] is the preferred class for pseudo number R.
407 This is available after `regclass' is run. */
409 static char *prefclass;
411 /* altclass[R] is a register class that we should use for allocating
412 pseudo number R if no register in the preferred class is available.
413 If no register in this class is available, memory is preferred.
415 It might appear to be more general to have a bitmask of classes here,
416 but since it is recommended that there be a class corresponding to the
417 union of most major pair of classes, that generality is not required.
419 This is available after `regclass' is run. */
421 static char *altclass;
423 /* Record the depth of loops that we are in. */
425 static int loop_depth;
427 /* Account for the fact that insns within a loop are executed very commonly,
428 but don't keep doing this as loops go too deep. */
430 static int loop_cost;
432 static int copy_cost ();
433 static void record_reg_classes ();
434 static void record_address_regs ();
437 /* Return the reg_class in which pseudo reg number REGNO is best allocated.
438 This function is sometimes called before the info has been computed.
439 When that happens, just return GENERAL_REGS, which is innocuous. */
442 reg_preferred_class (regno)
447 return (enum reg_class) prefclass[regno];
451 reg_alternate_class (regno)
456 return (enum reg_class) altclass[regno];
459 /* This prevents dump_flow_info from losing if called
460 before regclass is run. */
468 /* This is a pass of the compiler that scans all instructions
469 and calculates the preferred class for each pseudo-register.
470 This information can be accessed later by calling `reg_preferred_class'.
471 This pass comes just before local register allocation. */
478 #ifdef REGISTER_CONSTRAINTS
481 struct costs init_cost;
487 init_cost.mem_cost = 10000;
488 for (i = 0; i < N_REG_CLASSES; i++)
489 init_cost.cost[i] = 10000;
491 /* Normally we scan the insns once and determine the best class to use for
492 each register. However, if -fexpensive_optimizations are on, we do so
493 twice, the second time using the tentative best classes to guide the
496 for (pass = 0; pass <= flag_expensive_optimizations; pass++)
498 /* Zero out our accumulation of the cost of each class for each reg. */
500 costs = (struct costs *) alloca (nregs * sizeof (struct costs));
501 bzero (costs, nregs * sizeof (struct costs));
503 loop_depth = 0, loop_cost = 1;
505 /* Scan the instructions and record each time it would
506 save code to put a certain register in a certain class. */
508 for (insn = f; insn; insn = NEXT_INSN (insn))
510 char *constraints[MAX_RECOG_OPERANDS];
511 enum machine_mode modes[MAX_RECOG_OPERANDS];
515 /* Show that an insn inside a loop is likely to be executed three
516 times more than insns outside a loop. This is much more agressive
517 than the assumptions made elsewhere and is being tried as an
520 if (GET_CODE (insn) == NOTE
521 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
522 loop_depth++, loop_cost = 1 << (2 * MIN (loop_depth, 5));
523 else if (GET_CODE (insn) == NOTE
524 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
525 loop_depth--, loop_cost = 1 << (2 * MIN (loop_depth, 5));
527 else if ((GET_CODE (insn) == INSN
528 && GET_CODE (PATTERN (insn)) != USE
529 && GET_CODE (PATTERN (insn)) != CLOBBER
530 && GET_CODE (PATTERN (insn)) != ASM_INPUT)
531 || (GET_CODE (insn) == JUMP_INSN
532 && GET_CODE (PATTERN (insn)) != ADDR_VEC
533 && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
534 || GET_CODE (insn) == CALL_INSN)
536 if (GET_CODE (insn) == INSN
537 && (noperands = asm_noperands (PATTERN (insn))) >= 0)
539 decode_asm_operands (PATTERN (insn), recog_operand, 0,
541 nalternatives = n_occurrences (',', constraints[0]) + 1;
545 int insn_code_number = recog_memoized (insn);
548 set = single_set (insn);
551 nalternatives = insn_n_alternatives[insn_code_number];
552 noperands = insn_n_operands[insn_code_number];
554 /* If this insn loads a parameter from its stack slot, then
555 it represents a savings, rather than a cost, if the
556 parameter is stored in memory. Record this fact. */
558 if (set != 0 && GET_CODE (SET_DEST (set)) == REG
559 && GET_CODE (SET_SRC (set)) == MEM
560 && (note = find_reg_note (insn, REG_EQUIV, 0)) != 0
561 && GET_CODE (XEXP (note, 0)) == MEM)
563 costs[REGNO (SET_DEST (set))].mem_cost
564 -= (MEMORY_MOVE_COST (GET_MODE (SET_DEST (set)))
566 record_address_regs (XEXP (SET_SRC (set), 0),
567 BASE_REG_CLASS, loop_cost * 2);
571 /* Improve handling of two-address insns such as
572 (set X (ashift CONST Y)) where CONST must be made to
573 match X. Change it into two insns: (set X CONST)
574 (set X (ashift X Y)). If we left this for reloading, it
575 would probably get three insns because X and Y might go
576 in the same place. This prevents X and Y from receiving
579 We can only do this if the modes of operands 0 and 1
580 (which might not be the same) are tieable and we only need
581 do this during our first pass. */
583 if (pass == 0 && optimize
585 && insn_operand_constraint[insn_code_number][1][0] == '0'
586 && insn_operand_constraint[insn_code_number][1][1] == 0
587 && CONSTANT_P (recog_operand[1])
588 && ! rtx_equal_p (recog_operand[0], recog_operand[1])
589 && ! rtx_equal_p (recog_operand[0], recog_operand[2])
590 && GET_CODE (recog_operand[0]) == REG
591 && MODES_TIEABLE_P (GET_MODE (recog_operand[0]),
592 insn_operand_mode[insn_code_number][1]))
594 rtx previnsn = prev_real_insn (insn);
596 = gen_lowpart (insn_operand_mode[insn_code_number][1],
599 = emit_insn_before (gen_move_insn (dest,
603 /* If this insn was the start of a basic block,
604 include the new insn in that block. */
605 if (previnsn == 0 || GET_CODE (previnsn) == JUMP_INSN)
608 for (b = 0; b < n_basic_blocks; b++)
609 if (insn == basic_block_head[b])
610 basic_block_head[b] = newinsn;
613 /* This makes one more setting of new insns's dest. */
614 reg_n_sets[REGNO (recog_operand[0])]++;
616 insn = PREV_INSN (newinsn);
620 /* If this is setting a pseudo from another pseudo or the
621 sum of a pseudo and a constant integer and the other
622 pseudo is known to be a pointer, set the destination to
623 be a pointer as well.
625 Likewise if it is setting the destination from an address
626 or from a value equivalent to an address or to the sum of
627 an address and something else.
629 But don't do any of this if the pseudo corresponds to
630 a user variable since it should have already been set
631 as a pointer based on the type.
633 There is no point in doing this during our second
634 pass since not enough should have changed. */
636 if (pass == 0 && set != 0 && GET_CODE (SET_DEST (set)) == REG
637 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
638 && ! REG_USERVAR_P (SET_DEST (set))
639 && ! REGNO_POINTER_FLAG (REGNO (SET_DEST (set)))
640 && ((GET_CODE (SET_SRC (set)) == REG
641 && REGNO_POINTER_FLAG (REGNO (SET_SRC (set))))
642 || ((GET_CODE (SET_SRC (set)) == PLUS
643 || GET_CODE (SET_SRC (set)) == LO_SUM)
644 && (GET_CODE (XEXP (SET_SRC (set), 1))
646 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
647 && REGNO_POINTER_FLAG (REGNO (XEXP (SET_SRC (set), 0))))
648 || GET_CODE (SET_SRC (set)) == CONST
649 || GET_CODE (SET_SRC (set)) == SYMBOL_REF
650 || GET_CODE (SET_SRC (set)) == LABEL_REF
651 || (GET_CODE (SET_SRC (set)) == HIGH
652 && (GET_CODE (XEXP (SET_SRC (set), 0)) == CONST
653 || (GET_CODE (XEXP (SET_SRC (set), 0))
655 || (GET_CODE (XEXP (SET_SRC (set), 0))
657 || ((GET_CODE (SET_SRC (set)) == PLUS
658 || GET_CODE (SET_SRC (set)) == LO_SUM)
659 && (GET_CODE (XEXP (SET_SRC (set), 1)) == CONST
660 || (GET_CODE (XEXP (SET_SRC (set), 1))
662 || (GET_CODE (XEXP (SET_SRC (set), 1))
664 || ((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
665 && (GET_CODE (XEXP (note, 0)) == CONST
666 || GET_CODE (XEXP (note, 0)) == SYMBOL_REF
667 || GET_CODE (XEXP (note, 0)) == LABEL_REF))))
668 REGNO_POINTER_FLAG (REGNO (SET_DEST (set))) = 1;
670 for (i = 0; i < noperands; i++)
673 = insn_operand_constraint[insn_code_number][i];
674 modes[i] = insn_operand_mode[insn_code_number][i];
678 /* If we get here, we are set up to record the costs of all the
679 operands for this insn. Start by initializing the costs.
680 Then handle any address registers. Finally record the desired
681 classes for any pseudos, doing it twice if some pair of
682 operands are commutative. */
684 for (i = 0; i < noperands; i++)
686 op_costs[i] = init_cost;
688 if (GET_CODE (recog_operand[i]) == SUBREG)
689 recog_operand[i] = SUBREG_REG (recog_operand[i]);
691 if (GET_CODE (recog_operand[i]) == MEM)
692 record_address_regs (XEXP (recog_operand[i], 0),
693 BASE_REG_CLASS, loop_cost * 2);
694 else if (constraints[i][0] == 'p')
695 record_address_regs (recog_operand[i],
696 BASE_REG_CLASS, loop_cost * 2);
699 /* Check for commutative in a separate loop so everything will
700 have been initialized. Don't bother doing anything if the
701 second operand is a constant since that is the case
702 for which the constraints should have been written. */
704 for (i = 0; i < noperands; i++)
705 if (constraints[i][0] == '%'
706 && ! CONSTANT_P (recog_operand[i+1]))
708 char *xconstraints[MAX_RECOG_OPERANDS];
711 /* Handle commutative operands by swapping the constraints.
712 We assume the modes are the same. */
714 for (j = 0; j < noperands; j++)
715 xconstraints[j] = constraints[j];
717 xconstraints[i] = constraints[i+1];
718 xconstraints[i+1] = constraints[i];
719 record_reg_classes (nalternatives, noperands,
720 recog_operand, modes, xconstraints,
724 record_reg_classes (nalternatives, noperands, recog_operand,
725 modes, constraints, insn);
727 /* Now add the cost for each operand to the total costs for
730 for (i = 0; i < noperands; i++)
731 if (GET_CODE (recog_operand[i]) == REG
732 && REGNO (recog_operand[i]) >= FIRST_PSEUDO_REGISTER)
734 int regno = REGNO (recog_operand[i]);
735 struct costs *p = &costs[regno], *q = &op_costs[i];
737 p->mem_cost += q->mem_cost * loop_cost;
738 for (j = 0; j < N_REG_CLASSES; j++)
739 p->cost[j] += q->cost[j] * loop_cost;
744 /* Now for each register look at how desirable each class is
745 and find which class is preferred. Store that in
746 `prefclass[REGNO]'. Record in `altclass[REGNO]' the largest register
747 class any of whose registers is better than memory. */
751 prefclass = (char *) oballoc (nregs);
752 altclass = (char *) oballoc (nregs);
755 for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++)
757 register int best_cost = (1 << (HOST_BITS_PER_INT - 1)) - 1;
758 enum reg_class best = ALL_REGS, alt = NO_REGS;
759 /* This is an enum reg_class, but we call it an int
760 to save lots of casts. */
762 register struct costs *p = &costs[i];
764 for (class = (int) ALL_REGS - 1; class > 0; class--)
766 /* Ignore classes that are too small for this operand. */
767 if (CLASS_MAX_NREGS (class, PSEUDO_REGNO_MODE (i))
768 > reg_class_size[class])
770 else if (p->cost[class] < best_cost)
772 best_cost = p->cost[class];
773 best = (enum reg_class) class;
775 else if (p->cost[class] == best_cost)
776 best = reg_class_subunion[(int)best][class];
779 /* Record the alternate register class; i.e., a class for which
780 every register in it is better than using memory. If adding a
781 class would make a smaller class (i.e., no union of just those
782 classes exists), skip that class. The major unions of classes
783 should be provided as a register class. Don't do this if we
784 will be doing it again later. */
786 if (pass == 1 || ! flag_expensive_optimizations)
787 for (class = 0; class < N_REG_CLASSES; class++)
788 if (p->cost[class] < p->mem_cost
789 && (reg_class_size[reg_class_subunion[(int) alt][class]]
790 > reg_class_size[(int) alt]))
791 alt = reg_class_subunion[(int) alt][class];
793 /* If we don't add any classes, nothing to try. */
797 /* We cast to (int) because (char) hits bugs in some compilers. */
798 prefclass[i] = (int) best;
799 altclass[i] = (int) alt;
802 #endif /* REGISTER_CONSTRAINTS */
805 #ifdef REGISTER_CONSTRAINTS
807 /* Record the cost of using memory or registers of various classes for
808 the operands in INSN.
810 N_ALTS is the number of alternatives.
812 N_OPS is the number of operands.
814 OPS is an array of the operands.
816 MODES are the modes of the operands, in case any are VOIDmode.
818 CONSTRAINTS are the constraints to use for the operands. This array
819 is modified by this procedure.
821 This procedure works alternative by alternative. For each alternative
822 we assume that we will be able to allocate all pseudos to their ideal
823 register class and calculate the cost of using that alternative. Then
824 we compute for each operand that is a pseudo-register, the cost of
825 having the pseudo allocated to each register class and using it in that
826 alternative. To this cost is added the cost of the alternative.
828 The cost of each class for this insn is its lowest cost among all the
832 record_reg_classes (n_alts, n_ops, ops, modes, constraints, insn)
836 enum machine_mode *modes;
841 enum op_type {OP_READ, OP_WRITE, OP_READ_WRITE} op_types[MAX_RECOG_OPERANDS];
844 /* By default, each operand is an input operand. */
846 for (i = 0; i < n_ops; i++)
847 op_types[i] = OP_READ;
849 /* Process each alternative, each time minimizing an operand's cost with
850 the cost for each operand in that alternative. */
852 for (alt = 0; alt < n_alts; alt++)
854 struct costs this_op_costs[MAX_RECOG_OPERANDS];
857 enum reg_class classes[MAX_RECOG_OPERANDS];
860 for (i = 0; i < n_ops; i++)
862 char *p = constraints[i];
864 enum machine_mode mode = modes[i];
869 /* If this operand has no constraints at all, we can conclude
870 nothing about it since anything is valid. */
874 if (GET_CODE (op) == REG && REGNO (op) >= FIRST_PSEUDO_REGISTER)
875 bzero ((char *) &this_op_costs[i], sizeof this_op_costs[i]);
880 /* If this alternative is only relevant when this operand
881 matches a previous operand, we do different things depending
882 on whether this operand is a pseudo-reg or not. */
884 if (p[0] >= '0' && p[0] <= '0' + i && (p[1] == ',' || p[1] == 0))
887 classes[i] = classes[j];
889 if (GET_CODE (op) != REG || REGNO (op) < FIRST_PSEUDO_REGISTER)
891 /* If this matches the other operand, we have no added
893 if (rtx_equal_p (ops[j], op))
896 /* If we can't put the other operand into a register, this
897 alternative can't be used. */
899 else if (classes[j] == NO_REGS)
902 /* Otherwise, add to the cost of this alternative the cost
903 to copy this operand to the register used for the other
907 alt_cost += copy_cost (op, mode, classes[j], 1);
912 /* The costs of this operand are the same as that of the
913 other operand. However, if we cannot tie them, this
914 alternative needs to do a copy, which is one
917 this_op_costs[i] = this_op_costs[j];
918 if (! find_reg_note (insn, REG_DEAD, op))
925 /* Scan all the constraint letters. See if the operand matches
926 any of the constraints. Collect the valid register classes
927 and see if this operand accepts memory. */
929 classes[i] = NO_REGS;
930 while (*p && (c = *p++) != ',')
934 op_types[i] = OP_WRITE;
938 op_types[i] = OP_READ_WRITE;
942 /* Ignore the next letter for this pass. */
947 case '?': case '!': case '#':
949 case '0': case '1': case '2': case '3': case '4':
953 case 'm': case 'o': case 'V':
954 /* It doesn't seem worth distingishing between offsettable
955 and non-offsettable addresses here. */
957 if (GET_CODE (op) == MEM)
962 if (GET_CODE (op) == MEM
963 && (GET_CODE (XEXP (op, 0)) == PRE_DEC
964 || GET_CODE (XEXP (op, 0)) == POST_DEC))
969 if (GET_CODE (op) == MEM
970 && (GET_CODE (XEXP (op, 0)) == PRE_INC
971 || GET_CODE (XEXP (op, 0)) == POST_INC))
976 /* Match any floating double constant, but only if
977 we can examine the bits of it reliably. */
978 if ((HOST_FLOAT_FORMAT != TARGET_FLOAT_FORMAT
979 || HOST_BITS_PER_INT != BITS_PER_WORD)
980 && GET_MODE (op) != VOIDmode && ! flag_pretend_float)
982 if (GET_CODE (op) == CONST_DOUBLE)
987 if (GET_CODE (op) == CONST_DOUBLE)
993 if (GET_CODE (op) == CONST_DOUBLE
994 && CONST_DOUBLE_OK_FOR_LETTER_P (op, c))
999 if (GET_CODE (op) == CONST_INT
1000 || (GET_CODE (op) == CONST_DOUBLE
1001 && GET_MODE (op) == VOIDmode))
1005 #ifdef LEGITIMATE_PIC_OPERAND_P
1006 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
1013 if (GET_CODE (op) == CONST_INT
1014 || (GET_CODE (op) == CONST_DOUBLE
1015 && GET_MODE (op) == VOIDmode))
1027 if (GET_CODE (op) == CONST_INT
1028 && CONST_OK_FOR_LETTER_P (INTVAL (op), c))
1036 #ifdef EXTRA_CONSTRAINT
1042 if (EXTRA_CONSTRAINT (op, c))
1048 if (GET_CODE (op) == MEM
1050 #ifdef LEGITIMATE_PIC_OPERAND_P
1051 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
1058 = reg_class_subunion[(int) classes[i]][(int) GENERAL_REGS];
1063 = reg_class_subunion[(int) classes[i]]
1064 [(int) REG_CLASS_FROM_LETTER (c)];
1069 /* How we account for this operand now depends on whether it is a
1070 pseudo register or not. If it is, we first check if any
1071 register classes are valid. If not, we ignore this alternative,
1072 since we want to assume that all pseudos get allocated for
1073 register preferencing. If some register class is valid, compute
1074 the costs of moving the pseudo into that class. */
1076 if (GET_CODE (op) == REG && REGNO (op) >= FIRST_PSEUDO_REGISTER)
1078 if (classes[i] == NO_REGS)
1082 struct costs *pp = &this_op_costs[i];
1084 for (class = 0; class < N_REG_CLASSES; class++)
1085 pp->cost[class] = may_move_cost[class][(int) classes[i]];
1087 /* If the alternative actually allows memory, make things
1088 a bit cheaper since we won't need an extra insn to
1091 pp->mem_cost = MEMORY_MOVE_COST (mode) - allows_mem;
1093 /* If we have assigned a class to this register in our
1094 first pass, add a cost to this alternative corresponding
1095 to what we would add if this register were not in the
1096 appropriate class. */
1100 += may_move_cost[prefclass[REGNO (op)]][(int) classes[i]];
1104 /* Otherwise, if this alternative wins, either because we
1105 have already determined that or if we have a hard register of
1106 the proper class, there is no cost for this alternative. */
1109 || (GET_CODE (op) == REG
1110 && reg_fits_class_p (op, classes[i], 0, mode)))
1113 /* If registers are valid, the cost of this alternative includes
1114 copying the object to and/or from a register. */
1116 else if (classes[i] != NO_REGS)
1118 if (op_types[i] != OP_WRITE)
1119 alt_cost += copy_cost (op, mode, classes[i], 1);
1121 if (op_types[i] != OP_READ)
1122 alt_cost += copy_cost (op, mode, classes[i], 0);
1125 /* The only other way this alternative can be used is if this is a
1126 constant that could be placed into memory. */
1128 else if (CONSTANT_P (op) && allows_mem)
1129 alt_cost += MEMORY_MOVE_COST (mode);
1137 /* Finally, update the costs with the information we've calculated
1138 about this alternative. */
1140 for (i = 0; i < n_ops; i++)
1141 if (GET_CODE (ops[i]) == REG
1142 && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
1144 struct costs *pp = &op_costs[i], *qq = &this_op_costs[i];
1145 int scale = 1 + (op_types[i] == OP_READ_WRITE);
1147 pp->mem_cost = MIN (pp->mem_cost,
1148 (qq->mem_cost + alt_cost) * scale);
1150 for (class = 0; class < N_REG_CLASSES; class++)
1151 pp->cost[class] = MIN (pp->cost[class],
1152 (qq->cost[class] + alt_cost) * scale);
1157 /* Compute the cost of loading X into (if TO_P is non-zero) or from (if
1158 TO_P is zero) a register of class CLASS in mode MODE.
1160 X must not be a pseudo. */
1163 copy_cost (x, mode, class, to_p)
1165 enum machine_mode mode;
1166 enum reg_class class;
1169 enum reg_class secondary_class = NO_REGS;
1171 /* If X is a SCRATCH, there is actually nothing to move since we are
1172 assuming optimal allocation. */
1174 if (GET_CODE (x) == SCRATCH)
1177 /* Get the class we will actually use for a reload. */
1178 class = PREFERRED_RELOAD_CLASS (x, class);
1180 #ifdef HAVE_SECONDARY_RELOADS
1181 /* If we need a secondary reload (we assume here that we are using
1182 the secondary reload as an intermediate, not a scratch register), the
1183 cost is that to load the input into the intermediate register, then
1184 to copy them. We use a special value of TO_P to avoid recursion. */
1186 #ifdef SECONDARY_INPUT_RELOAD_CLASS
1188 secondary_class = SECONDARY_INPUT_RELOAD_CLASS (class, mode, x);
1191 #ifdef SECONARY_OUTPUT_RELOAD_CLASS
1193 secondary_class = SECONDARY_OUTPUT_RELOAD_CLASS (class, mode, x);
1196 if (secondary_class != NO_REGS)
1197 return (move_cost[(int) secondary_class][(int) class]
1198 + copy_cost (x, mode, secondary_class, 2));
1199 #endif /* HAVE_SECONARY_RELOADS */
1201 /* For memory, use the memory move cost, for (hard) registers, use the
1202 cost to move between the register classes, and use 2 for everything
1203 else (constants). */
1205 if (GET_CODE (x) == MEM || class == NO_REGS)
1206 return MEMORY_MOVE_COST (mode);
1208 else if (GET_CODE (x) == REG)
1209 return move_cost[(int) REGNO_REG_CLASS (REGNO (x))][(int) class];
1212 /* If this is a constant, we may eventually want to call rtx_cost here. */
1216 /* Record the pseudo registers we must reload into hard registers
1217 in a subexpression of a memory address, X.
1219 CLASS is the class that the register needs to be in and is either
1220 BASE_REG_CLASS or INDEX_REG_CLASS.
1222 SCALE is twice the amount to multiply the cost by (it is twice so we
1223 can represent half-cost adjustments). */
1226 record_address_regs (x, class, scale)
1228 enum reg_class class;
1231 register enum rtx_code code = GET_CODE (x);
1244 /* When we have an address that is a sum,
1245 we must determine whether registers are "base" or "index" regs.
1246 If there is a sum of two registers, we must choose one to be
1247 the "base". Luckily, we can use the REGNO_POINTER_FLAG
1248 to make a good choice most of the time. We only need to do this
1249 on machines that can have two registers in an address and where
1250 the base and index register classes are different.
1252 ??? This code used to set REGNO_POINTER_FLAG in some cases, but
1253 that seems bogus since it should only be set when we are sure
1254 the register is being used as a pointer. */
1257 rtx arg0 = XEXP (x, 0);
1258 rtx arg1 = XEXP (x, 1);
1259 register enum rtx_code code0 = GET_CODE (arg0);
1260 register enum rtx_code code1 = GET_CODE (arg1);
1262 /* Look inside subregs. */
1263 if (code0 == SUBREG)
1264 arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
1265 if (code1 == SUBREG)
1266 arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
1268 /* If this machine only allows one register per address, it must
1269 be in the first operand. */
1271 if (MAX_REGS_PER_ADDRESS == 1)
1272 record_address_regs (arg0, class, scale);
1274 /* If index and base registers are the same on this machine, just
1275 record registers in any non-constant operands. We assume here,
1276 as well as in the tests below, that all addresses are in
1279 else if (INDEX_REG_CLASS == BASE_REG_CLASS)
1281 record_address_regs (arg0, class, scale);
1282 if (! CONSTANT_P (arg1))
1283 record_address_regs (arg1, class, scale);
1286 /* If the second operand is a constant integer, it doesn't change
1287 what class the first operand must be. */
1289 else if (code1 == CONST_INT || code1 == CONST_DOUBLE)
1290 record_address_regs (arg0, class, scale);
1292 /* If the second operand is a symbolic constant, the first operand
1293 must be an index register. */
1295 else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF)
1296 record_address_regs (arg0, INDEX_REG_CLASS, scale);
1298 /* If this the sum of two registers where the first is known to be a
1299 pointer, it must be a base register with the second an index. */
1301 else if (code0 == REG && code1 == REG
1302 && REGNO_POINTER_FLAG (REGNO (arg0)))
1304 record_address_regs (arg0, BASE_REG_CLASS, scale);
1305 record_address_regs (arg1, INDEX_REG_CLASS, scale);
1308 /* If this is the sum of two registers and neither is known to
1309 be a pointer, count equal chances that each might be a base
1310 or index register. This case should be rare. */
1312 else if (code0 == REG && code1 == REG
1313 && ! REGNO_POINTER_FLAG (REGNO (arg0))
1314 && ! REGNO_POINTER_FLAG (REGNO (arg1)))
1316 record_address_regs (arg0, BASE_REG_CLASS, scale / 2);
1317 record_address_regs (arg0, INDEX_REG_CLASS, scale / 2);
1318 record_address_regs (arg1, BASE_REG_CLASS, scale / 2);
1319 record_address_regs (arg1, INDEX_REG_CLASS, scale / 2);
1322 /* In all other cases, the first operand is an index and the
1323 second is the base. */
1327 record_address_regs (arg0, INDEX_REG_CLASS, scale);
1328 record_address_regs (arg1, BASE_REG_CLASS, scale);
1337 /* Double the importance of a pseudo register that is incremented
1338 or decremented, since it would take two extra insns
1339 if it ends up in the wrong place. */
1341 record_address_regs (XEXP (x, 0), class, 2 * scale);
1346 register struct costs *pp = &costs[REGNO (x)];
1349 pp->mem_cost += (MEMORY_MOVE_COST (Pmode) * scale) / 2;
1351 for (i = 0; i < N_REG_CLASSES; i++)
1352 pp->cost[i] += (may_move_cost[i][(int) class] * scale) / 2;
1358 register char *fmt = GET_RTX_FORMAT (code);
1360 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1362 record_address_regs (XEXP (x, i), class, scale);
1366 #endif /* REGISTER_CONSTRAINTS */
1368 /* This is the `regscan' pass of the compiler, run just before cse
1369 and again just before loop.
1371 It finds the first and last use of each pseudo-register
1372 and records them in the vectors regno_first_uid, regno_last_uid
1373 and counts the number of sets in the vector reg_n_sets.
1375 REPEAT is nonzero the second time this is called. */
1377 /* Indexed by pseudo register number, gives uid of first insn using the reg
1378 (as of the time reg_scan is called). */
1380 int *regno_first_uid;
1382 /* Indexed by pseudo register number, gives uid of last insn using the reg
1383 (as of the time reg_scan is called). */
1385 int *regno_last_uid;
1387 /* Record the number of registers we used when we allocated the above two
1388 tables. If we are called again with more than this, we must re-allocate
1391 static int highest_regno_in_uid_map;
1393 /* Maximum number of parallel sets and clobbers in any insn in this fn.
1394 Always at least 3, since the combiner could put that many togetherm
1395 and we want this to remain correct for all the remaining passes. */
1399 void reg_scan_mark_refs ();
1402 reg_scan (f, nregs, repeat)
1409 if (!repeat || nregs > highest_regno_in_uid_map)
1411 /* Leave some spare space in case more regs are allocated. */
1412 highest_regno_in_uid_map = nregs + nregs / 20;
1414 = (int *) oballoc (highest_regno_in_uid_map * sizeof (int));
1416 = (int *) oballoc (highest_regno_in_uid_map * sizeof (int));
1418 = (short *) oballoc (highest_regno_in_uid_map * sizeof (short));
1421 bzero (regno_first_uid, highest_regno_in_uid_map * sizeof (int));
1422 bzero (regno_last_uid, highest_regno_in_uid_map * sizeof (int));
1423 bzero (reg_n_sets, highest_regno_in_uid_map * sizeof (short));
1427 for (insn = f; insn; insn = NEXT_INSN (insn))
1428 if (GET_CODE (insn) == INSN
1429 || GET_CODE (insn) == CALL_INSN
1430 || GET_CODE (insn) == JUMP_INSN)
1432 if (GET_CODE (PATTERN (insn)) == PARALLEL
1433 && XVECLEN (PATTERN (insn), 0) > max_parallel)
1434 max_parallel = XVECLEN (PATTERN (insn), 0);
1435 reg_scan_mark_refs (PATTERN (insn), INSN_UID (insn));
1440 reg_scan_mark_refs (x, uid)
1444 register enum rtx_code code = GET_CODE (x);
1462 register int regno = REGNO (x);
1464 regno_last_uid[regno] = uid;
1465 if (regno_first_uid[regno] == 0)
1466 regno_first_uid[regno] = uid;
1471 /* Count a set of the destination if it is a register. */
1472 for (dest = SET_DEST (x);
1473 GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART
1474 || GET_CODE (dest) == ZERO_EXTEND;
1475 dest = XEXP (dest, 0))
1478 if (GET_CODE (dest) == REG)
1479 reg_n_sets[REGNO (dest)]++;
1481 /* ... fall through ... */
1485 register char *fmt = GET_RTX_FORMAT (code);
1487 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1490 reg_scan_mark_refs (XEXP (x, i), uid);
1491 else if (fmt[i] == 'E' && XVEC (x, i) != 0)
1494 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1495 reg_scan_mark_refs (XVECEXP (x, i, j), uid);
1502 /* Return nonzero if C1 is a subset of C2, i.e., if every register in C1
1506 reg_class_subset_p (c1, c2)
1507 register enum reg_class c1;
1508 register enum reg_class c2;
1510 if (c1 == c2) return 1;
1515 GO_IF_HARD_REG_SUBSET (reg_class_contents[(int)c1],
1516 reg_class_contents[(int)c2],
1521 /* Return nonzero if there is a register that is in both C1 and C2. */
1524 reg_classes_intersect_p (c1, c2)
1525 register enum reg_class c1;
1526 register enum reg_class c2;
1533 if (c1 == c2) return 1;
1535 if (c1 == ALL_REGS || c2 == ALL_REGS)
1538 COPY_HARD_REG_SET (c, reg_class_contents[(int) c1]);
1539 AND_HARD_REG_SET (c, reg_class_contents[(int) c2]);
1541 GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);