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 /* preferred_or_nothing[R] is nonzero if we should put pseudo number R
412 in memory if we can't get its preferred class.
413 This is available after `regclass' is run. */
415 static char *preferred_or_nothing;
417 /* Record the depth of loops that we are in, 1 for no loops. */
419 static int loop_depth;
421 void reg_class_record ();
422 void record_address_regs ();
425 /* Return the reg_class in which pseudo reg number REGNO is best allocated.
426 This function is sometimes called before the info has been computed.
427 When that happens, just return GENERAL_REGS, which is innocuous. */
430 reg_preferred_class (regno)
435 return (enum reg_class) prefclass[regno];
439 reg_alternate_class (regno)
444 return (enum reg_class) altclass[regno];
447 /* This prevents dump_flow_info from losing if called
448 before regclass is run. */
456 /* This is a pass of the compiler that scans all instructions
457 and calculates the preferred class for each pseudo-register.
458 This information can be accessed later by calling `reg_preferred_class'.
459 This pass comes just before local register allocation. */
466 #ifdef REGISTER_CONSTRAINTS
469 struct costs init_cost;
475 init_cost.mem_cost = 10000;
476 for (i = 0; i < N_REG_CLASSES; i++)
477 init_cost.cost[i] = 10000;
479 /* Normally we scan the insns once and determine the best class to use for
480 each register. However, if -fexpensive_optimizations are on, we do so
481 twice, the second time using the tentative best classes to guide the
484 for (pass = 0; pass <= flag_expensive_optimizations; pass++)
486 /* Zero out our accumulation of the cost of each class for each reg. */
488 costs = (struct costs *) alloca (nregs * sizeof (struct costs));
489 bzero (costs, nregs * sizeof (struct costs));
491 loop_depth = 0, loop_cost = 1;
493 /* Scan the instructions and record each time it would
494 save code to put a certain register in a certain class. */
496 for (insn = f; insn; insn = NEXT_INSN (insn))
498 char *constraints[MAX_RECOG_OPERANDS];
499 enum machine_mode modes[MAX_RECOG_OPERANDS];
503 /* Show that an insn inside a loop is likely to be executed three
504 times more than insns outside a loop. This is much more agressive
505 than the assumptions made elsewhere and is being tried as an
508 if (GET_CODE (insn) == NOTE
509 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
510 loop_depth++, loop_cost = 1 << (2 * MIN (loop_depth, 5));
511 else if (GET_CODE (insn) == NOTE
512 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
513 loop_depth--, loop_cost = 1 << (2 * MIN (loop_depth, 5));
515 else if ((GET_CODE (insn) == INSN
516 && GET_CODE (PATTERN (insn)) != USE
517 && GET_CODE (PATTERN (insn)) != CLOBBER
518 && GET_CODE (PATTERN (insn)) != ASM_INPUT)
519 || (GET_CODE (insn) == JUMP_INSN
520 && GET_CODE (PATTERN (insn)) != ADDR_VEC
521 && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
522 || GET_CODE (insn) == CALL_INSN)
524 if (GET_CODE (insn) == INSN
525 && (noperands = asm_noperands (PATTERN (insn))) >= 0)
527 decode_asm_operands (PATTERN (insn), recog_operand, 0,
529 nalternatives = n_occurrences (',', constraints[0]) + 1;
533 int insn_code_number = recog_memoized (insn);
536 set = single_set (insn);
539 nalternatives = insn_n_alternatives[insn_code_number];
540 noperands = insn_n_operands[insn_code_number];
542 /* If this insn loads a parameter from its stack slot, then
543 it represents a savings, rather than a cost, if the
544 parameter is stored in memory. Record this fact. */
546 if (set != 0 && GET_CODE (SET_DEST (set)) == REG
547 && GET_CODE (SET_SRC (set)) == MEM
548 && (note = find_reg_note (insn, REG_EQUIV, 0)) != 0
549 && GET_CODE (XEXP (note, 0)) == MEM)
551 costs[REGNO (SET_DEST (set))].mem_cost
552 -= (MEMORY_MOVE_COST (GET_MODE (SET_DEST (set)))
554 record_address_regs (XEXP (SET_SRC (set), 0),
555 BASE_REG_CLASS, loop_cost * 2);
559 /* Improve handling of two-address insns such as
560 (set X (ashift CONST Y)) where CONST must be made to
561 match X. Change it into two insns: (set X CONST)
562 (set X (ashift X Y)). If we left this for reloading, it
563 would probably get three insns because X and Y might go
564 in the same place. This prevents X and Y from receiving
567 We can only do this if the modes of operands 0 and 1
568 (which might not be the same) are tieable and we only need
569 do this during our first pass. */
571 if (pass == 0 && optimize
573 && insn_operand_constraint[insn_code_number][1][0] == '0'
574 && insn_operand_constraint[insn_code_number][1][1] == 0
575 && CONSTANT_P (recog_operand[1])
576 && ! rtx_equal_p (recog_operand[0], recog_operand[1])
577 && ! rtx_equal_p (recog_operand[0], recog_operand[2])
578 && GET_CODE (recog_operand[0]) == REG
579 && MODES_TIEABLE_P (GET_MODE (recog_operand[0]),
580 insn_operand_mode[insn_code_number][1]))
582 rtx previnsn = prev_real_insn (insn);
584 = gen_lowpart (insn_operand_mode[insn_code_number][1],
587 = emit_insn_before (gen_move_insn (dest,
591 /* If this insn was the start of a basic block,
592 include the new insn in that block. */
593 if (previnsn == 0 || GET_CODE (previnsn) == JUMP_INSN)
596 for (b = 0; b < n_basic_blocks; b++)
597 if (insn == basic_block_head[b])
598 basic_block_head[b] = newinsn;
601 /* This makes one more setting of new insns's dest. */
602 reg_n_sets[REGNO (recog_operand[0])]++;
604 insn = PREV_INSN (newinsn);
608 /* If this is setting a pseudo from another pseudo or the
609 sum of a pseudo and a constant integer and the other
610 pseudo is known to be a pointer, set the destination to
611 be a pointer as well.
613 Likewise if it is setting the destination from an address
614 or from a value equivalent to an address or to the sum of
615 an address and something else.
617 But don't do any of this if the pseudo corresponds to
618 a user variable since it should have already been set
619 as a pointer based on the type.
621 There is no point in doing this during our second
622 pass since not enough should have changed. */
624 if (pass == 0 && set != 0 && GET_CODE (SET_DEST (set)) == REG
625 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
626 && ! REG_USERVAR_P (SET_DEST (set))
627 && ! REGNO_POINTER_FLAG (REGNO (SET_DEST (set)))
628 && ((GET_CODE (SET_SRC (set)) == REG
629 && REGNO_POINTER_FLAG (REGNO (SET_SRC (set))))
630 || ((GET_CODE (SET_SRC (set)) == PLUS
631 || GET_CODE (SET_SRC (set)) == LO_SUM)
632 && (GET_CODE (XEXP (SET_SRC (set), 1))
634 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
635 && REGNO_POINTER_FLAG (REGNO (XEXP (SET_SRC (set), 0))))
636 || GET_CODE (SET_SRC (set)) == CONST
637 || GET_CODE (SET_SRC (set)) == SYMBOL_REF
638 || GET_CODE (SET_SRC (set)) == LABEL_REF
639 || (GET_CODE (SET_SRC (set)) == HIGH
640 && (GET_CODE (XEXP (SET_SRC (set), 0)) == CONST
641 || (GET_CODE (XEXP (SET_SRC (set), 0))
643 || (GET_CODE (XEXP (SET_SRC (set), 0))
645 || ((GET_CODE (SET_SRC (set)) == PLUS
646 || GET_CODE (SET_SRC (set)) == LO_SUM)
647 && (GET_CODE (XEXP (SET_SRC (set), 1)) == CONST
648 || (GET_CODE (XEXP (SET_SRC (set), 1))
650 || (GET_CODE (XEXP (SET_SRC (set), 1))
652 || ((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
653 && (GET_CODE (XEXP (note, 0)) == CONST
654 || GET_CODE (XEXP (note, 0)) == SYMBOL_REF
655 || GET_CODE (XEXP (note, 0)) == LABEL_REF))))
656 REGNO_POINTER_FLAG (REGNO (SET_DEST (set))) = 1;
658 for (i = 0; i < noperands; i++)
661 = insn_operand_constraint[insn_code_number][i];
662 modes[i] = insn_operand_mode[insn_code_number][i];
666 /* If we get here, we are set up to record the costs of all the
667 operands for this insn. Start by initializing the costs.
668 Then handle any address registers. Finally record the desired
669 classes for any pseudos, doing it twice if some pair of
670 operands are commutative. */
672 for (i = 0; i < noperands; i++)
674 op_costs[i] = init_cost;
676 if (GET_CODE (recog_operand[i]) == SUBREG)
677 recog_operand[i] = SUBREG_REG (recog_operand[i]);
679 if (GET_CODE (recog_operand[i]) == MEM)
680 record_address_regs (XEXP (recog_operand[i], 0),
681 BASE_REG_CLASS, loop_cost * 2);
682 else if (constraints[i][0] == 'p')
683 record_address_regs (recog_operand[i],
684 BASE_REG_CLASS, loop_cost * 2);
687 /* Check for commutative in a separate loop so everything will
688 have been initialized. Don't bother doing anything if the
689 second operand is a constant since that is the case
690 for which the constraints should have been written. */
692 for (i = 0; i < noperands; i++)
693 if (constraints[i][0] == '%'
694 && ! CONSTANT_P (recog_operand[i+1]))
696 char *xconstraints[MAX_RECOG_OPERANDS];
699 /* Handle commutative operands by swapping the constraints.
700 We assume the modes are the same. */
702 for (j = 0; j < noperands; j++)
703 xconstraints[j] = constraints[j];
705 xconstraints[i] = constraints[i+1];
706 xconstraints[i+1] = constraints[i];
707 record_reg_classes (nalternatives, noperands,
708 recog_operand, modes, xconstraints,
712 record_reg_classes (nalternatives, noperands, recog_operand,
713 modes, constraints, insn);
715 /* Now add the cost for each operand to the total costs for
718 for (i = 0; i < noperands; i++)
719 if (GET_CODE (recog_operand[i]) == REG
720 && REGNO (recog_operand[i]) >= FIRST_PSEUDO_REGISTER)
722 int regno = REGNO (recog_operand[i]);
723 struct costs *p = &costs[regno], *q = &op_costs[i];
725 p->mem_cost += q->mem_cost * loop_cost;
726 for (j = 0; j < N_REG_CLASSES; j++)
727 p->cost[j] += q->cost[j] * loop_cost;
732 /* Now for each register look at how desirable each class is
733 and find which class is preferred. Store that in
734 `prefclass[REGNO]'. Record in `altclass[REGNO]' the largest register
735 class any of whose registers is better than memory. */
739 prefclass = (char *) oballoc (nregs);
740 altclass = (char *) oballoc (nregs);
743 for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++)
745 register int best_cost = (1 << (HOST_BITS_PER_INT - 1)) - 1;
746 enum reg_class best = ALL_REGS, alt = NO_REGS;
747 /* This is an enum reg_class, but we call it an int
748 to save lots of casts. */
750 register struct costs *p = &costs[i];
752 for (class = (int) ALL_REGS - 1; class > 0; class--)
754 /* Ignore classes that are too small for this operand. */
755 if (CLASS_MAX_NREGS (class, PSEUDO_REGNO_MODE (i))
756 > reg_class_size[class])
758 else if (p->cost[class] < best_cost)
760 best_cost = p->cost[class];
761 best = (enum reg_class) class;
763 else if (p->cost[class] == best_cost)
764 best = reg_class_subunion[(int)best][class];
767 /* Record the alternate register class; i.e., a class for which
768 every register in it is better than using memory. If adding a
769 class would make a smaller class (i.e., no union of just those
770 classes exists), skip that class. The major unions of classes
771 should be provided as a register class. Don't do this if we
772 will be doing it again later. */
774 if (pass == 1 || ! flag_expensive_optimizations)
775 for (class = 0; class < N_REG_CLASSES; class++)
776 if (p->cost[class] < p->mem_cost
777 && (reg_class_size[reg_class_subunion[(int) alt][class]]
778 > reg_class_size[(int) alt]))
779 alt = reg_class_subunion[(int) alt][class];
781 /* If we don't add any classes, nothing to try. */
785 /* We cast to (int) because (char) hits bugs in some compilers. */
786 prefclass[i] = (int) best;
787 altclass[i] = (int) alt;
790 #endif /* REGISTER_CONSTRAINTS */
793 #ifdef REGISTER_CONSTRAINTS
795 /* Record the cost of using memory or registers of various classes for
796 the operands in INSN.
798 N_ALTS is the number of alternatives.
800 N_OPS is the number of operands.
802 OPS is an array of the operands.
804 MODES are the modes of the operands, in case any are VOIDmode.
806 CONSTRAINTS are the constraints to use for the operands. This array
807 is modified by this procedure.
809 This procedure works alternative by alternative. For each alternative
810 we assume that we will be able to allocate all pseudos to their ideal
811 register class and calculate the cost of using that alternative. Then
812 we compute for each operand that is a pseudo-register, the cost of
813 having the pseudo allocated to each register class and using it in that
814 alternative. To this cost is added the cost of the alternative.
816 The cost of each class for this insn is its lowest cost among all the
820 record_reg_classes (n_alts, n_ops, ops, modes, constraints, insn)
824 enum machine_mode *modes;
829 enum op_type {OP_READ, OP_WRITE, OP_READ_WRITE} op_types[MAX_RECOG_OPERANDS];
832 /* By default, each operand is an input operand. */
834 for (i = 0; i < n_ops; i++)
835 op_types[i] = OP_READ;
837 /* Process each alternative, each time minimizing an operand's cost with
838 the cost for each operand in that alternative. */
840 for (alt = 0; alt < n_alts; alt++)
842 struct costs this_op_costs[MAX_RECOG_OPERANDS];
845 enum reg_class classes[MAX_RECOG_OPERANDS];
848 for (i = 0; i < n_ops; i++)
850 char *p = constraints[i];
852 enum machine_mode mode = modes[i];
857 /* If this operand has no constraints at all, we can conclude
858 nothing about it since anything is valid. */
862 if (GET_CODE (op) == REG && REGNO (op) >= FIRST_PSEUDO_REGISTER)
863 bzero ((char *) &this_op_costs[i], sizeof this_op_costs[i]);
868 /* If this alternative is only relevant when this operand
869 matches a previous operand, we do different things depending
870 on whether this operand is a pseudo-reg or not. */
872 if (p[0] >= '0' && p[0] <= '0' + i && (p[1] == ',' || p[1] == 0))
875 classes[i] = classes[j];
877 if (GET_CODE (op) != REG || REGNO (op) < FIRST_PSEUDO_REGISTER)
879 /* If this matches the other operand, we have no added
881 if (rtx_equal_p (ops[j], op))
884 /* If we can't put the other operand into a register, this
885 alternative can't be used. */
887 else if (classes[j] == NO_REGS)
890 /* Otherwise, add to the cost of this alternative the cost
891 to copy this operand to the register used for the other
895 alt_cost += copy_cost (op, mode, classes[j], 1);
900 /* The costs of this operand are the same as that of the
901 other operand. However, if we cannot tie them, this
902 alternative needs to do a copy, which is one
905 this_op_costs[i] = this_op_costs[j];
906 if (! find_reg_note (insn, REG_DEAD, op))
913 /* Scan all the constraint letters. See if the operand matches
914 any of the constraints. Collect the valid register classes
915 and see if this operand accepts memory. */
917 classes[i] = NO_REGS;
918 while (*p && (c = *p++) != ',')
922 op_types[i] = OP_WRITE;
926 op_types[i] = OP_READ_WRITE;
930 /* Ignore the next letter for this pass. */
935 case '?': case '!': case '#':
937 case '0': case '1': case '2': case '3': case '4':
941 case 'm': case 'o': case 'V':
942 /* It doesn't seem worth distingishing between offsettable
943 and non-offsettable addresses here. */
945 if (GET_CODE (op) == MEM)
950 if (GET_CODE (op) == MEM
951 && (GET_CODE (XEXP (op, 0)) == PRE_DEC
952 || GET_CODE (XEXP (op, 0)) == POST_DEC))
957 if (GET_CODE (op) == MEM
958 && (GET_CODE (XEXP (op, 0)) == PRE_INC
959 || GET_CODE (XEXP (op, 0)) == POST_INC))
964 /* Match any floating double constant, but only if
965 we can examine the bits of it reliably. */
966 if ((HOST_FLOAT_FORMAT != TARGET_FLOAT_FORMAT
967 || HOST_BITS_PER_INT != BITS_PER_WORD)
968 && GET_MODE (op) != VOIDmode && ! flag_pretend_float)
970 if (GET_CODE (op) == CONST_DOUBLE)
975 if (GET_CODE (op) == CONST_DOUBLE)
981 if (GET_CODE (op) == CONST_DOUBLE
982 && CONST_DOUBLE_OK_FOR_LETTER_P (op, c))
987 if (GET_CODE (op) == CONST_INT
988 || (GET_CODE (op) == CONST_DOUBLE
989 && GET_MODE (op) == VOIDmode))
993 #ifdef LEGITIMATE_PIC_OPERAND_P
994 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
1001 if (GET_CODE (op) == CONST_INT
1002 || (GET_CODE (op) == CONST_DOUBLE
1003 && GET_MODE (op) == VOIDmode))
1015 if (GET_CODE (op) == CONST_INT
1016 && CONST_OK_FOR_LETTER_P (INTVAL (op), c))
1024 #ifdef EXTRA_CONSTRAINT
1030 if (EXTRA_CONSTRAINT (op, c))
1036 if (GET_CODE (op) == MEM
1038 #ifdef LEGITIMATE_PIC_OPERAND_P
1039 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
1046 = reg_class_subunion[(int) classes[i]][(int) GENERAL_REGS];
1051 = reg_class_subunion[(int) classes[i]]
1052 [(int) REG_CLASS_FROM_LETTER (c)];
1057 /* How we account for this operand now depends on whether it is a
1058 pseudo register or not. If it is, we first check if any
1059 register classes are valid. If not, we ignore this alternative,
1060 since we want to assume that all pseudos get allocated for
1061 register preferencing. If some register class is valid, compute
1062 the costs of moving the pseudo into that class. */
1064 if (GET_CODE (op) == REG && REGNO (op) >= FIRST_PSEUDO_REGISTER)
1066 if (classes[i] == NO_REGS)
1070 struct costs *pp = &this_op_costs[i];
1072 for (class = 0; class < N_REG_CLASSES; class++)
1073 pp->cost[class] = may_move_cost[class][(int) classes[i]];
1075 /* If the alternative actually allows memory, make things
1076 a bit cheaper since we won't need an extra insn to
1079 pp->mem_cost = MEMORY_MOVE_COST (mode) - allows_mem;
1081 /* If we have assigned a class to this register in our
1082 first pass, add a cost to this alternative corresponding
1083 to what we would add if this register were not in the
1084 appropriate class. */
1088 += may_move_cost[prefclass[REGNO (op)]][(int) classes[i]];
1092 /* Otherwise, if this alternative wins, either because we
1093 have already determined that or if we have a hard register of
1094 the proper class, there is no cost for this alternative. */
1097 || (GET_CODE (op) == REG
1098 && reg_fits_class_p (op, classes[i], 0, mode)))
1101 /* If registers are valid, the cost of this alternative includes
1102 copying the object to and/or from a register. */
1104 else if (classes[i] != NO_REGS)
1106 if (op_types[i] != OP_WRITE)
1107 alt_cost += copy_cost (op, mode, classes[i], 1);
1109 if (op_types[i] != OP_READ)
1110 alt_cost += copy_cost (op, mode, classes[i], 0);
1113 /* The only other way this alternative can be used is if this is a
1114 constant that could be placed into memory. */
1116 else if (CONSTANT_P (op) && allows_mem)
1117 alt_cost += MEMORY_MOVE_COST (mode);
1125 /* Finally, update the costs with the information we've calculated
1126 about this alternative. */
1128 for (i = 0; i < n_ops; i++)
1129 if (GET_CODE (ops[i]) == REG
1130 && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
1132 struct costs *pp = &op_costs[i], *qq = &this_op_costs[i];
1133 int scale = 1 + (op_types[i] == OP_READ_WRITE);
1135 pp->mem_cost = MIN (pp->mem_cost,
1136 (qq->mem_cost + alt_cost) * scale);
1138 for (class = 0; class < N_REG_CLASSES; class++)
1139 pp->cost[class] = MIN (pp->cost[class],
1140 (qq->cost[class] + alt_cost) * scale);
1145 /* Compute the cost of loading X into (if TO_P is non-zero) or from (if
1146 TO_P is zero) a register of class CLASS in mode MODE.
1148 X must not be a pseudo. */
1151 copy_cost (x, mode, class, to_p)
1153 enum machine_mode mode;
1154 enum reg_class class;
1157 enum reg_class secondary_class = NO_REGS;
1159 /* If X is a SCRATCH, there is actually nothing to move since we are
1160 assuming optimal allocation. */
1162 if (GET_CODE (x) == SCRATCH)
1165 /* Get the class we will actually use for a reload. */
1166 class = PREFERRED_RELOAD_CLASS (x, class);
1168 #ifdef HAVE_SECONDARY_RELOADS
1169 /* If we need a secondary reload (we assume here that we are using
1170 the secondary reload as an intermediate, not a scratch register), the
1171 cost is that to load the input into the intermediate register, then
1172 to copy them. We use a special value of TO_P to avoid recursion. */
1174 #ifdef SECONDARY_INPUT_RELOAD_CLASS
1176 secondary_class = SECONDARY_INPUT_RELOAD_CLASS (class, mode, x);
1179 #ifdef SECONARY_OUTPUT_RELOAD_CLASS
1181 secondary_class = SECONDARY_OUTPUT_RELOAD_CLASS (class, mode, x);
1184 if (secondary_class != NO_REGS)
1185 return (move_cost[(int) secondary_class][(int) class]
1186 + copy_cost (x, mode, secondary_class, 2));
1187 #endif /* HAVE_SECONARY_RELOADS */
1189 /* For memory, use the memory move cost, for (hard) registers, use the
1190 cost to move between the register classes, and use 2 for everything
1191 else (constants). */
1193 if (GET_CODE (x) == MEM || class == NO_REGS)
1194 return MEMORY_MOVE_COST (mode);
1196 else if (GET_CODE (x) == REG)
1197 return move_cost[(int) REGNO_REG_CLASS (REGNO (x))][(int) class];
1200 /* If this is a constant, we may eventually want to call rtx_cost here. */
1204 /* Record the pseudo registers we must reload into hard registers
1205 in a subexpression of a memory address, X.
1207 CLASS is the class that the register needs to be in and is either
1208 BASE_REG_CLASS or INDEX_REG_CLASS.
1210 SCALE is twice the amount to multiply the cost by (it is twice so we
1211 can represent half-cost adjustments). */
1214 record_address_regs (x, class, scale)
1216 enum reg_class class;
1219 register enum rtx_code code = GET_CODE (x);
1232 /* When we have an address that is a sum,
1233 we must determine whether registers are "base" or "index" regs.
1234 If there is a sum of two registers, we must choose one to be
1235 the "base". Luckily, we can use the REGNO_POINTER_FLAG
1236 to make a good choice most of the time. We only need to do this
1237 on machines that can have two registers in an address and where
1238 the base and index register classes are different.
1240 ??? This code used to set REGNO_POINTER_FLAG in some cases, but
1241 that seems bogus since it should only be set when we are sure
1242 the register is being used as a pointer. */
1245 rtx arg0 = XEXP (x, 0);
1246 rtx arg1 = XEXP (x, 1);
1247 register enum rtx_code code0 = GET_CODE (arg0);
1248 register enum rtx_code code1 = GET_CODE (arg1);
1250 /* Look inside subregs. */
1251 if (code0 == SUBREG)
1252 arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
1253 if (code1 == SUBREG)
1254 arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
1256 /* If this machine only allows one register per address, it must
1257 be in the first operand. */
1259 if (MAX_REGS_PER_ADDRESS == 1)
1260 record_address_regs (arg0, class, scale);
1262 /* If index and base registers are the same on this machine, just
1263 record registers in any non-constant operands. We assume here,
1264 as well as in the tests below, that all addresses are in
1267 else if (INDEX_REG_CLASS == BASE_REG_CLASS)
1269 record_address_regs (arg0, class, scale);
1270 if (! CONSTANT_P (arg1))
1271 record_address_regs (arg1, class, scale);
1274 /* If the second operand is a constant integer, it doesn't change
1275 what class the first operand must be. */
1277 else if (code1 == CONST_INT || code1 == CONST_DOUBLE)
1278 record_address_regs (arg0, class, scale);
1280 /* If the second operand is a symbolic constant, the first operand
1281 must be an index register. */
1283 else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF)
1284 record_address_regs (arg0, INDEX_REG_CLASS, scale);
1286 /* If this the sum of two registers where the first is known to be a
1287 pointer, it must be a base register with the second an index. */
1289 else if (code0 == REG && code1 == REG
1290 && REGNO_POINTER_FLAG (REGNO (arg0)))
1292 record_address_regs (arg0, BASE_REG_CLASS, scale);
1293 record_address_regs (arg1, INDEX_REG_CLASS, scale);
1296 /* If this is the sum of two registers and neither is known to
1297 be a pointer, count equal chances that each might be a base
1298 or index register. This case should be rare. */
1300 else if (code0 == REG && code1 == REG
1301 && ! REGNO_POINTER_FLAG (REGNO (arg0))
1302 && ! REGNO_POINTER_FLAG (REGNO (arg1)))
1304 record_address_regs (arg0, BASE_REG_CLASS, scale / 2);
1305 record_address_regs (arg0, INDEX_REG_CLASS, scale / 2);
1306 record_address_regs (arg1, BASE_REG_CLASS, scale / 2);
1307 record_address_regs (arg1, INDEX_REG_CLASS, scale / 2);
1310 /* In all other cases, the first operand is an index and the
1311 second is the base. */
1315 record_address_regs (arg0, INDEX_REG_CLASS, scale);
1316 record_address_regs (arg1, BASE_REG_CLASS, scale);
1325 /* Double the importance of a pseudo register that is incremented
1326 or decremented, since it would take two extra insns
1327 if it ends up in the wrong place. */
1329 record_address_regs (XEXP (x, 0), class, 2 * scale);
1334 register struct costs *pp = &costs[REGNO (x)];
1337 pp->mem_cost += (MEMORY_MOVE_COST (Pmode) * scale) / 2;
1339 for (i = 0; i < N_REG_CLASSES; i++)
1340 pp->cost[i] += (may_move_cost[i][(int) class] * scale) / 2;
1346 register char *fmt = GET_RTX_FORMAT (code);
1348 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1350 record_address_regs (XEXP (x, i), class, scale);
1354 #endif /* REGISTER_CONSTRAINTS */
1356 /* This is the `regscan' pass of the compiler, run just before cse
1357 and again just before loop.
1359 It finds the first and last use of each pseudo-register
1360 and records them in the vectors regno_first_uid, regno_last_uid
1361 and counts the number of sets in the vector reg_n_sets.
1363 REPEAT is nonzero the second time this is called. */
1365 /* Indexed by pseudo register number, gives uid of first insn using the reg
1366 (as of the time reg_scan is called). */
1368 int *regno_first_uid;
1370 /* Indexed by pseudo register number, gives uid of last insn using the reg
1371 (as of the time reg_scan is called). */
1373 int *regno_last_uid;
1375 /* Record the number of registers we used when we allocated the above two
1376 tables. If we are called again with more than this, we must re-allocate
1379 static int highest_regno_in_uid_map;
1381 /* Maximum number of parallel sets and clobbers in any insn in this fn.
1382 Always at least 3, since the combiner could put that many togetherm
1383 and we want this to remain correct for all the remaining passes. */
1387 void reg_scan_mark_refs ();
1390 reg_scan (f, nregs, repeat)
1397 if (!repeat || nregs > highest_regno_in_uid_map)
1399 /* Leave some spare space in case more regs are allocated. */
1400 highest_regno_in_uid_map = nregs + nregs / 20;
1402 = (int *) oballoc (highest_regno_in_uid_map * sizeof (int));
1404 = (int *) oballoc (highest_regno_in_uid_map * sizeof (int));
1406 = (short *) oballoc (highest_regno_in_uid_map * sizeof (short));
1409 bzero (regno_first_uid, highest_regno_in_uid_map * sizeof (int));
1410 bzero (regno_last_uid, highest_regno_in_uid_map * sizeof (int));
1411 bzero (reg_n_sets, highest_regno_in_uid_map * sizeof (short));
1415 for (insn = f; insn; insn = NEXT_INSN (insn))
1416 if (GET_CODE (insn) == INSN
1417 || GET_CODE (insn) == CALL_INSN
1418 || GET_CODE (insn) == JUMP_INSN)
1420 if (GET_CODE (PATTERN (insn)) == PARALLEL
1421 && XVECLEN (PATTERN (insn), 0) > max_parallel)
1422 max_parallel = XVECLEN (PATTERN (insn), 0);
1423 reg_scan_mark_refs (PATTERN (insn), INSN_UID (insn));
1428 reg_scan_mark_refs (x, uid)
1432 register enum rtx_code code = GET_CODE (x);
1450 register int regno = REGNO (x);
1452 regno_last_uid[regno] = uid;
1453 if (regno_first_uid[regno] == 0)
1454 regno_first_uid[regno] = uid;
1459 /* Count a set of the destination if it is a register. */
1460 for (dest = SET_DEST (x);
1461 GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART
1462 || GET_CODE (dest) == ZERO_EXTEND;
1463 dest = XEXP (dest, 0))
1466 if (GET_CODE (dest) == REG)
1467 reg_n_sets[REGNO (dest)]++;
1469 /* ... fall through ... */
1473 register char *fmt = GET_RTX_FORMAT (code);
1475 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1478 reg_scan_mark_refs (XEXP (x, i), uid);
1479 else if (fmt[i] == 'E' && XVEC (x, i) != 0)
1482 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1483 reg_scan_mark_refs (XVECEXP (x, i, j), uid);
1490 /* Return nonzero if C1 is a subset of C2, i.e., if every register in C1
1494 reg_class_subset_p (c1, c2)
1495 register enum reg_class c1;
1496 register enum reg_class c2;
1498 if (c1 == c2) return 1;
1503 GO_IF_HARD_REG_SUBSET (reg_class_contents[(int)c1],
1504 reg_class_contents[(int)c2],
1509 /* Return nonzero if there is a register that is in both C1 and C2. */
1512 reg_classes_intersect_p (c1, c2)
1513 register enum reg_class c1;
1514 register enum reg_class c2;
1521 if (c1 == c2) return 1;
1523 if (c1 == ALL_REGS || c2 == ALL_REGS)
1526 COPY_HARD_REG_SET (c, reg_class_contents[(int) c1]);
1527 AND_HARD_REG_SET (c, reg_class_contents[(int) c2]);
1529 GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);