1 /* Compute cover class of the pseudos and their hard register costs.
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
26 #include "hard-reg-set.h"
31 #include "basic-block.h"
33 #include "addresses.h"
34 #include "insn-config.h"
41 /* The file contains code is analogous to one in regclass but the code
42 works on the pseudo basis. */
46 static void record_reg_classes (int, int, rtx
*, enum machine_mode
*,
47 const char **, rtx
, struct costs
*,
49 static inline int ok_for_index_p_nonstrict (rtx
);
50 static inline int ok_for_base_p_nonstrict (rtx
, enum machine_mode
,
51 enum rtx_code
, enum rtx_code
);
52 static void record_address_regs (enum machine_mode
, rtx x
, int,
53 enum rtx_code
, enum rtx_code
, int scale
);
54 static void record_operand_costs (rtx
, struct costs
*, enum reg_class
*);
55 static rtx
scan_one_insn (rtx
);
56 static void print_costs (FILE *);
57 static void process_bb_node_for_costs (struct ira_loop_tree_node
*);
58 static void find_pseudo_class_costs (void);
59 static void process_bb_node_for_hard_reg_moves (struct ira_loop_tree_node
*);
60 static void setup_pseudo_cover_class_and_costs (void);
62 #ifdef FORBIDDEN_INC_DEC_CLASSES
63 /* Indexed by n, is nonzero if (REG n) is used in an auto-inc or
65 static char *in_inc_dec
;
68 /* The `costs' struct records the cost of using a hard register of
69 each class and of using memory for each pseudo. We use this data
70 to set up register and costs. */
73 int cost
[N_REG_CLASSES
];
77 /* Record the cost of each class for each pseudo. */
78 static struct costs
*costs
;
80 /* Initialized once, and used to initialize cost values for each
82 static struct costs init_cost
;
84 /* Record register class preferences of each pseudo. */
85 static enum reg_class
*reg_pref
;
87 /* Allocated buffers for reg_pref. */
88 static enum reg_class
*reg_pref_buffer
;
90 /* Frequency of executions of the current insn. */
93 /* Map regno->pseudo for the current loop. */
94 static pseudo_t
*curr_regno_pseudo_map
;
96 /* Compute the cost of loading X into (if TO_P is nonzero) or from (if
97 TO_P is zero) a register of class CLASS in mode MODE. X must not
98 be a pseudo register. */
100 copy_cost (rtx x
, enum machine_mode mode
, enum reg_class
class, int to_p
,
101 secondary_reload_info
*prev_sri
)
103 secondary_reload_info sri
;
104 enum reg_class secondary_class
= NO_REGS
;
106 /* If X is a SCRATCH, there is actually nothing to move since we are
107 assuming optimal allocation. */
108 if (GET_CODE (x
) == SCRATCH
)
111 /* Get the class we will actually use for a reload. */
112 class = PREFERRED_RELOAD_CLASS (x
, class);
114 /* If we need a secondary reload for an intermediate, the cost is
115 that to load the input into the intermediate register, then to
117 sri
.prev_sri
= prev_sri
;
119 secondary_class
= targetm
.secondary_reload (to_p
, x
, class, mode
, &sri
);
121 if (secondary_class
!= NO_REGS
)
122 return (move_cost
[mode
] [secondary_class
] [class]
124 + copy_cost (x
, mode
, secondary_class
, to_p
, &sri
));
126 /* For memory, use the memory move cost, for (hard) registers, use
127 the cost to move between the register classes, and use 2 for
128 everything else (constants). */
129 if (MEM_P (x
) || class == NO_REGS
)
130 return sri
.extra_cost
+ memory_move_cost
[mode
] [class] [to_p
!= 0];
134 + move_cost
[mode
] [REGNO_REG_CLASS (REGNO (x
))] [class]);
136 /* If this is a constant, we may eventually want to call rtx_cost
138 return sri
.extra_cost
+ COSTS_N_INSNS (1);
143 /* Record the cost of using memory or registers of various classes for
144 the operands in INSN.
146 N_ALTS is the number of alternatives.
147 N_OPS is the number of operands.
148 OPS is an array of the operands.
149 MODES are the modes of the operands, in case any are VOIDmode.
150 CONSTRAINTS are the constraints to use for the operands. This array
151 is modified by this procedure.
153 This procedure works alternative by alternative. For each
154 alternative we assume that we will be able to allocate all pseudos
155 to their ideal register class and calculate the cost of using that
156 alternative. Then we compute for each operand that is a
157 pseudo-register, the cost of having the pseudo allocated to each
158 register class and using it in that alternative. To this cost is
159 added the cost of the alternative.
161 The cost of each class for this insn is its lowest cost among all
164 record_reg_classes (int n_alts
, int n_ops
, rtx
*ops
,
165 enum machine_mode
*modes
, const char **constraints
,
166 rtx insn
, struct costs
*op_costs
,
167 enum reg_class
*reg_pref
)
173 /* Process each alternative, each time minimizing an operand's cost
174 with the cost for each operand in that alternative. */
175 for (alt
= 0; alt
< n_alts
; alt
++)
177 struct costs this_op_costs
[MAX_RECOG_OPERANDS
];
178 enum reg_class classes
[MAX_RECOG_OPERANDS
];
179 int allows_mem
[MAX_RECOG_OPERANDS
];
184 for (i
= 0; i
< n_ops
; i
++)
187 const char *p
= constraints
[i
];
189 enum machine_mode mode
= modes
[i
];
193 /* Initially show we know nothing about the register class. */
194 classes
[i
] = NO_REGS
;
197 /* If this operand has no constraints at all, we can
198 conclude nothing about it since anything is valid. */
201 if (REG_P (op
) && REGNO (op
) >= FIRST_PSEUDO_REGISTER
)
202 memset (&this_op_costs
[i
], 0, sizeof this_op_costs
[i
]);
206 /* If this alternative is only relevant when this operand
207 matches a previous operand, we do different things
208 depending on whether this operand is a pseudo-reg or not.
209 We must process any modifiers for the operand before we
210 can make this test. */
211 while (*p
== '%' || *p
== '=' || *p
== '+' || *p
== '&')
214 if (p
[0] >= '0' && p
[0] <= '0' + i
&& (p
[1] == ',' || p
[1] == 0))
216 /* Copy class and whether memory is allowed from the
217 matching alternative. Then perform any needed cost
218 computations and/or adjustments. */
220 classes
[i
] = classes
[j
];
221 allows_mem
[i
] = allows_mem
[j
];
223 if (! REG_P (op
) || REGNO (op
) < FIRST_PSEUDO_REGISTER
)
225 /* If this matches the other operand, we have no
226 added cost and we win. */
227 if (rtx_equal_p (ops
[j
], op
))
229 /* If we can put the other operand into a register,
230 add to the cost of this alternative the cost to
231 copy this operand to the register used for the
233 else if (classes
[j
] != NO_REGS
)
235 alt_cost
+= copy_cost (op
, mode
, classes
[j
], 1, NULL
);
239 else if (! REG_P (ops
[j
])
240 || REGNO (ops
[j
]) < FIRST_PSEUDO_REGISTER
)
242 /* This op is a pseudo but the one it matches is
245 /* If we can't put the other operand into a
246 register, this alternative can't be used. */
248 if (classes
[j
] == NO_REGS
)
250 /* Otherwise, add to the cost of this alternative
251 the cost to copy the other operand to the
252 register used for this operand. */
255 += copy_cost (ops
[j
], mode
, classes
[j
], 1, NULL
);
259 /* The costs of this operand are not the same as the
260 other operand since move costs are not symmetric.
261 Moreover, if we cannot tie them, this alternative
262 needs to do a copy, which is one instruction. */
263 struct costs
*pp
= &this_op_costs
[i
];
265 for (class = 0; class < N_REG_CLASSES
; class++)
267 = ((recog_data
.operand_type
[i
] != OP_OUT
268 ? may_move_in_cost
[mode
] [class] [classes
[i
]]
270 + (recog_data
.operand_type
[i
] != OP_IN
271 ? may_move_out_cost
[mode
] [classes
[i
]] [class]
274 /* If the alternative actually allows memory, make
275 things a bit cheaper since we won't need an extra
278 = ((recog_data
.operand_type
[i
] != OP_IN
279 ? memory_move_cost
[mode
] [classes
[i
]] [0]
281 + (recog_data
.operand_type
[i
] != OP_OUT
282 ? memory_move_cost
[mode
] [classes
[i
]] [1]
283 : 0) - allows_mem
[i
]);
285 /* If we have assigned a class to this pseudo in our
286 first pass, add a cost to this alternative
287 corresponding to what we would add if this pseudo
288 were not in the appropriate class. We could use
289 cover class here but it is less accurate
293 += (may_move_in_cost
[mode
]
294 [reg_pref
[PSEUDO_NUM
295 (curr_regno_pseudo_map
[REGNO (op
)])]]
297 if (REGNO (ops
[i
]) != REGNO (ops
[j
])
298 && ! find_reg_note (insn
, REG_DEAD
, op
))
301 /* This is in place of ordinary cost computation for
302 this operand, so skip to the end of the
303 alternative (should be just one character). */
304 while (*p
&& *p
++ != ',')
312 /* Scan all the constraint letters. See if the operand
313 matches any of the constraints. Collect the valid
314 register classes and see if this operand accepts
323 /* Ignore the next letter for this pass. */
329 case '!': case '#': case '&':
330 case '0': case '1': case '2': case '3': case '4':
331 case '5': case '6': case '7': case '8': case '9':
336 win
= address_operand (op
, GET_MODE (op
));
337 /* We know this operand is an address, so we want it
338 to be allocated to a register that can be the
339 base of an address, i.e. BASE_REG_CLASS. */
341 = reg_class_subunion
[classes
[i
]]
342 [base_reg_class (VOIDmode
, ADDRESS
, SCRATCH
)];
345 case 'm': case 'o': case 'V':
346 /* It doesn't seem worth distinguishing between
347 offsettable and non-offsettable addresses
356 && (GET_CODE (XEXP (op
, 0)) == PRE_DEC
357 || GET_CODE (XEXP (op
, 0)) == POST_DEC
))
363 && (GET_CODE (XEXP (op
, 0)) == PRE_INC
364 || GET_CODE (XEXP (op
, 0)) == POST_INC
))
370 if (GET_CODE (op
) == CONST_DOUBLE
371 || (GET_CODE (op
) == CONST_VECTOR
372 && (GET_MODE_CLASS (GET_MODE (op
))
373 == MODE_VECTOR_FLOAT
)))
379 if (GET_CODE (op
) == CONST_DOUBLE
380 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op
, c
, p
))
385 if (GET_CODE (op
) == CONST_INT
386 || (GET_CODE (op
) == CONST_DOUBLE
387 && GET_MODE (op
) == VOIDmode
))
392 && (! flag_pic
|| LEGITIMATE_PIC_OPERAND_P (op
)))
397 if (GET_CODE (op
) == CONST_INT
398 || (GET_CODE (op
) == CONST_DOUBLE
399 && GET_MODE (op
) == VOIDmode
))
411 if (GET_CODE (op
) == CONST_INT
412 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op
), c
, p
))
423 && (! flag_pic
|| LEGITIMATE_PIC_OPERAND_P (op
))))
428 = reg_class_subunion
[classes
[i
]] [GENERAL_REGS
];
432 if (REG_CLASS_FROM_CONSTRAINT (c
, p
) != NO_REGS
)
434 = reg_class_subunion
[classes
[i
]]
435 [REG_CLASS_FROM_CONSTRAINT (c
, p
)];
436 #ifdef EXTRA_CONSTRAINT_STR
437 else if (EXTRA_CONSTRAINT_STR (op
, c
, p
))
440 if (EXTRA_MEMORY_CONSTRAINT (c
, p
))
442 /* Every MEM can be reloaded to fit. */
447 if (EXTRA_ADDRESS_CONSTRAINT (c
, p
))
449 /* Every address can be reloaded to fit. */
451 if (address_operand (op
, GET_MODE (op
)))
453 /* We know this operand is an address, so we
454 want it to be allocated to a register that
455 can be the base of an address,
456 i.e. BASE_REG_CLASS. */
458 = reg_class_subunion
[classes
[i
]]
459 [base_reg_class (VOIDmode
, ADDRESS
, SCRATCH
)];
464 p
+= CONSTRAINT_LEN (c
, p
);
471 /* How we account for this operand now depends on whether it
472 is a pseudo register or not. If it is, we first check if
473 any register classes are valid. If not, we ignore this
474 alternative, since we want to assume that all pseudos get
475 allocated for register preferencing. If some register
476 class is valid, compute the costs of moving the pseudo
478 if (REG_P (op
) && REGNO (op
) >= FIRST_PSEUDO_REGISTER
)
480 if (classes
[i
] == NO_REGS
)
482 /* We must always fail if the operand is a REG, but
483 we did not find a suitable class.
485 Otherwise we may perform an uninitialized read
486 from this_op_costs after the `continue' statement
492 struct costs
*pp
= &this_op_costs
[i
];
494 for (class = 0; class < N_REG_CLASSES
; class++)
496 = ((recog_data
.operand_type
[i
] != OP_OUT
497 ? may_move_in_cost
[mode
] [class] [classes
[i
]]
499 + (recog_data
.operand_type
[i
] != OP_IN
500 ? may_move_out_cost
[mode
] [classes
[i
]] [class]
503 /* If the alternative actually allows memory, make
504 things a bit cheaper since we won't need an extra
507 = ((recog_data
.operand_type
[i
] != OP_IN
508 ? memory_move_cost
[mode
] [classes
[i
]] [0]
510 + (recog_data
.operand_type
[i
] != OP_OUT
511 ? memory_move_cost
[mode
] [classes
[i
]] [1]
512 : 0) - allows_mem
[i
]);
514 /* If we have assigned a class to this pseudo in our
515 first pass, add a cost to this alternative
516 corresponding to what we would add if this pseudo
517 were not in the appropriate class. We could use
518 cover class here but it is less accurate
522 += (may_move_in_cost
[mode
]
523 [reg_pref
[PSEUDO_NUM
524 (curr_regno_pseudo_map
[REGNO (op
)])]]
529 /* Otherwise, if this alternative wins, either because we
530 have already determined that or if we have a hard
531 register of the proper class, there is no cost for this
533 else if (win
|| (REG_P (op
)
534 && reg_fits_class_p (op
, classes
[i
],
538 /* If registers are valid, the cost of this alternative
539 includes copying the object to and/or from a
541 else if (classes
[i
] != NO_REGS
)
543 if (recog_data
.operand_type
[i
] != OP_OUT
)
544 alt_cost
+= copy_cost (op
, mode
, classes
[i
], 1, NULL
);
546 if (recog_data
.operand_type
[i
] != OP_IN
)
547 alt_cost
+= copy_cost (op
, mode
, classes
[i
], 0, NULL
);
549 /* The only other way this alternative can be used is if
550 this is a constant that could be placed into memory. */
551 else if (CONSTANT_P (op
) && (allows_addr
|| allows_mem
[i
]))
552 alt_cost
+= memory_move_cost
[mode
] [classes
[i
]] [1];
560 /* Finally, update the costs with the information we've
561 calculated about this alternative. */
562 for (i
= 0; i
< n_ops
; i
++)
564 && REGNO (ops
[i
]) >= FIRST_PSEUDO_REGISTER
)
566 struct costs
*pp
= &op_costs
[i
], *qq
= &this_op_costs
[i
];
567 int scale
= 1 + (recog_data
.operand_type
[i
] == OP_INOUT
);
569 pp
->mem_cost
= MIN (pp
->mem_cost
,
570 (qq
->mem_cost
+ alt_cost
) * scale
);
572 for (class = 0; class < N_REG_CLASSES
; class++)
573 pp
->cost
[class] = MIN (pp
->cost
[class],
574 (qq
->cost
[class] + alt_cost
) * scale
);
578 /* If this insn is a single set copying operand 1 to operand 0 and
579 one operand is a pseudo with the other a hard reg or a pseudo
580 that prefers a register that is in its own register class then we
581 may want to adjust the cost of that register class to -1.
583 Avoid the adjustment if the source does not die to avoid
584 stressing of register allocator by preferrencing two colliding
585 registers into single class.
587 Also avoid the adjustment if a copy between registers of the
588 class is expensive (ten times the cost of a default copy is
589 considered arbitrarily expensive). This avoids losing when the
590 preferred class is very expensive as the source of a copy
592 if ((set
= single_set (insn
)) != 0
593 && ops
[0] == SET_DEST (set
) && ops
[1] == SET_SRC (set
)
594 && REG_P (ops
[0]) && REG_P (ops
[1])
595 && find_regno_note (insn
, REG_DEAD
, REGNO (ops
[1])))
596 for (i
= 0; i
<= 1; i
++)
597 if (REGNO (ops
[i
]) >= FIRST_PSEUDO_REGISTER
)
599 unsigned int regno
= REGNO (ops
[!i
]);
600 enum machine_mode mode
= GET_MODE (ops
[!i
]);
604 if (regno
>= FIRST_PSEUDO_REGISTER
&& reg_pref
!= 0)
608 /* We could use cover class here but it is less accurate
610 pref
= reg_pref
[PSEUDO_NUM (curr_regno_pseudo_map
[regno
])];
612 if ((reg_class_size
[pref
]
613 == (unsigned) CLASS_MAX_NREGS (pref
, mode
))
614 && register_move_cost
[mode
] [pref
] [pref
] < 10 * 2)
615 op_costs
[i
].cost
[pref
] = -1;
617 else if (regno
< FIRST_PSEUDO_REGISTER
)
618 for (class = 0; class < N_REG_CLASSES
; class++)
619 if (TEST_HARD_REG_BIT (reg_class_contents
[class], regno
)
620 && (reg_class_size
[class]
621 == (unsigned) CLASS_MAX_NREGS (class, mode
)))
623 if (reg_class_size
[class] == 1)
624 op_costs
[i
].cost
[class] = -1;
628 nr
< (unsigned) hard_regno_nregs
[regno
] [mode
];
630 if (! TEST_HARD_REG_BIT (reg_class_contents
[class],
634 if (nr
== (unsigned) hard_regno_nregs
[regno
] [mode
])
635 op_costs
[i
].cost
[class] = -1;
643 /* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudo registers. */
645 ok_for_index_p_nonstrict (rtx reg
)
647 unsigned regno
= REGNO (reg
);
649 return regno
>= FIRST_PSEUDO_REGISTER
|| REGNO_OK_FOR_INDEX_P (regno
);
652 /* A version of regno_ok_for_base_p for use during regclass, when all
653 pseudos should count as OK. Arguments as for
654 regno_ok_for_base_p. */
656 ok_for_base_p_nonstrict (rtx reg
, enum machine_mode mode
,
657 enum rtx_code outer_code
, enum rtx_code index_code
)
659 unsigned regno
= REGNO (reg
);
661 if (regno
>= FIRST_PSEUDO_REGISTER
)
663 return ok_for_base_p_1 (regno
, mode
, outer_code
, index_code
);
666 /* Record the pseudo registers we must reload into hard registers in a
667 subexpression of a memory address, X.
669 If CONTEXT is 0, we are looking at the base part of an address,
670 otherwise we are looking at the index part.
672 MODE is the mode of the memory reference; OUTER_CODE and INDEX_CODE
673 give the context that the rtx appears in. These three arguments
674 are passed down to base_reg_class.
676 SCALE is twice the amount to multiply the cost by (it is twice so
677 we can represent half-cost adjustments). */
679 record_address_regs (enum machine_mode mode
, rtx x
, int context
,
680 enum rtx_code outer_code
, enum rtx_code index_code
,
683 enum rtx_code code
= GET_CODE (x
);
684 enum reg_class
class;
687 class = INDEX_REG_CLASS
;
689 class = base_reg_class (mode
, outer_code
, index_code
);
702 /* When we have an address that is a sum, we must determine
703 whether registers are "base" or "index" regs. If there is a
704 sum of two registers, we must choose one to be the "base".
705 Luckily, we can use the REG_POINTER to make a good choice
706 most of the time. We only need to do this on machines that
707 can have two registers in an address and where the base and
708 index register classes are different.
710 ??? This code used to set REGNO_POINTER_FLAG in some cases,
711 but that seems bogus since it should only be set when we are
712 sure the register is being used as a pointer. */
714 rtx arg0
= XEXP (x
, 0);
715 rtx arg1
= XEXP (x
, 1);
716 enum rtx_code code0
= GET_CODE (arg0
);
717 enum rtx_code code1
= GET_CODE (arg1
);
719 /* Look inside subregs. */
721 arg0
= SUBREG_REG (arg0
), code0
= GET_CODE (arg0
);
723 arg1
= SUBREG_REG (arg1
), code1
= GET_CODE (arg1
);
725 /* If this machine only allows one register per address, it
726 must be in the first operand. */
727 if (MAX_REGS_PER_ADDRESS
== 1)
728 record_address_regs (mode
, arg0
, 0, PLUS
, code1
, scale
);
730 /* If index and base registers are the same on this machine,
731 just record registers in any non-constant operands. We
732 assume here, as well as in the tests below, that all
733 addresses are in canonical form. */
734 else if (INDEX_REG_CLASS
== base_reg_class (VOIDmode
, PLUS
, SCRATCH
))
736 record_address_regs (mode
, arg0
, context
, PLUS
, code1
, scale
);
737 if (! CONSTANT_P (arg1
))
738 record_address_regs (mode
, arg1
, context
, PLUS
, code0
, scale
);
741 /* If the second operand is a constant integer, it doesn't
742 change what class the first operand must be. */
743 else if (code1
== CONST_INT
|| code1
== CONST_DOUBLE
)
744 record_address_regs (mode
, arg0
, context
, PLUS
, code1
, scale
);
745 /* If the second operand is a symbolic constant, the first
746 operand must be an index register. */
747 else if (code1
== SYMBOL_REF
|| code1
== CONST
|| code1
== LABEL_REF
)
748 record_address_regs (mode
, arg0
, 1, PLUS
, code1
, scale
);
749 /* If both operands are registers but one is already a hard
750 register of index or reg-base class, give the other the
751 class that the hard register is not. */
752 else if (code0
== REG
&& code1
== REG
753 && REGNO (arg0
) < FIRST_PSEUDO_REGISTER
754 && (ok_for_base_p_nonstrict (arg0
, mode
, PLUS
, REG
)
755 || ok_for_index_p_nonstrict (arg0
)))
756 record_address_regs (mode
, arg1
,
757 ok_for_base_p_nonstrict (arg0
, mode
, PLUS
, REG
)
760 else if (code0
== REG
&& code1
== REG
761 && REGNO (arg1
) < FIRST_PSEUDO_REGISTER
762 && (ok_for_base_p_nonstrict (arg1
, mode
, PLUS
, REG
)
763 || ok_for_index_p_nonstrict (arg1
)))
764 record_address_regs (mode
, arg0
,
765 ok_for_base_p_nonstrict (arg1
, mode
, PLUS
, REG
)
768 /* If one operand is known to be a pointer, it must be the
769 base with the other operand the index. Likewise if the
770 other operand is a MULT. */
771 else if ((code0
== REG
&& REG_POINTER (arg0
)) || code1
== MULT
)
773 record_address_regs (mode
, arg0
, 0, PLUS
, code1
, scale
);
774 record_address_regs (mode
, arg1
, 1, PLUS
, code0
, scale
);
776 else if ((code1
== REG
&& REG_POINTER (arg1
)) || code0
== MULT
)
778 record_address_regs (mode
, arg0
, 1, PLUS
, code1
, scale
);
779 record_address_regs (mode
, arg1
, 0, PLUS
, code0
, scale
);
781 /* Otherwise, count equal chances that each might be a base or
782 index register. This case should be rare. */
785 record_address_regs (mode
, arg0
, 0, PLUS
, code1
, scale
/ 2);
786 record_address_regs (mode
, arg0
, 1, PLUS
, code1
, scale
/ 2);
787 record_address_regs (mode
, arg1
, 0, PLUS
, code0
, scale
/ 2);
788 record_address_regs (mode
, arg1
, 1, PLUS
, code0
, scale
/ 2);
793 /* Double the importance of a pseudo that is incremented or
794 decremented, since it would take two extra insns if it ends
795 up in the wrong place. */
798 record_address_regs (mode
, XEXP (x
, 0), 0, code
,
799 GET_CODE (XEXP (XEXP (x
, 1), 1)), 2 * scale
);
800 if (REG_P (XEXP (XEXP (x
, 1), 1)))
801 record_address_regs (mode
, XEXP (XEXP (x
, 1), 1), 1, code
, REG
,
809 /* Double the importance of a pseudo that is incremented or
810 decremented, since it would take two extra insns if it ends
811 up in the wrong place. If the operand is a pseudo-register,
812 show it is being used in an INC_DEC context. */
813 #ifdef FORBIDDEN_INC_DEC_CLASSES
814 if (REG_P (XEXP (x
, 0))
815 && REGNO (XEXP (x
, 0)) >= FIRST_PSEUDO_REGISTER
)
816 in_inc_dec
[PSEUDO_NUM (curr_regno_pseudo_map
[REGNO (XEXP (x
, 0))])]
819 record_address_regs (mode
, XEXP (x
, 0), 0, code
, SCRATCH
, 2 * scale
);
827 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
)
830 pp
= &costs
[PSEUDO_NUM (curr_regno_pseudo_map
[REGNO (x
)])];
831 pp
->mem_cost
+= (memory_move_cost
[Pmode
] [class] [1] * scale
) / 2;
832 for (i
= 0; i
< N_REG_CLASSES
; i
++)
833 pp
->cost
[i
] += (may_move_in_cost
[Pmode
] [i
] [class] * scale
) / 2;
839 const char *fmt
= GET_RTX_FORMAT (code
);
841 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
843 record_address_regs (mode
, XEXP (x
, i
), context
, code
, SCRATCH
,
851 /* Calculate the costs of insn operands. */
853 record_operand_costs (rtx insn
, struct costs
*op_costs
,
854 enum reg_class
*reg_pref
)
856 const char *constraints
[MAX_RECOG_OPERANDS
];
857 enum machine_mode modes
[MAX_RECOG_OPERANDS
];
860 for (i
= 0; i
< recog_data
.n_operands
; i
++)
862 constraints
[i
] = recog_data
.constraints
[i
];
863 modes
[i
] = recog_data
.operand_mode
[i
];
866 /* If we get here, we are set up to record the costs of all the
867 operands for this insn. Start by initializing the costs. Then
868 handle any address registers. Finally record the desired classes
869 for any pseudos, doing it twice if some pair of operands are
871 for (i
= 0; i
< recog_data
.n_operands
; i
++)
873 op_costs
[i
] = init_cost
;
875 if (GET_CODE (recog_data
.operand
[i
]) == SUBREG
)
876 recog_data
.operand
[i
] = SUBREG_REG (recog_data
.operand
[i
]);
878 if (MEM_P (recog_data
.operand
[i
]))
879 record_address_regs (GET_MODE (recog_data
.operand
[i
]),
880 XEXP (recog_data
.operand
[i
], 0),
881 0, MEM
, SCRATCH
, frequency
* 2);
882 else if (constraints
[i
] [0] == 'p'
883 || EXTRA_ADDRESS_CONSTRAINT (constraints
[i
] [0],
885 record_address_regs (VOIDmode
, recog_data
.operand
[i
], 0, ADDRESS
,
886 SCRATCH
, frequency
* 2);
889 /* Check for commutative in a separate loop so everything will have
890 been initialized. We must do this even if one operand is a
891 constant--see addsi3 in m68k.md. */
892 for (i
= 0; i
< (int) recog_data
.n_operands
- 1; i
++)
893 if (constraints
[i
] [0] == '%')
895 const char *xconstraints
[MAX_RECOG_OPERANDS
];
898 /* Handle commutative operands by swapping the constraints.
899 We assume the modes are the same. */
900 for (j
= 0; j
< recog_data
.n_operands
; j
++)
901 xconstraints
[j
] = constraints
[j
];
903 xconstraints
[i
] = constraints
[i
+1];
904 xconstraints
[i
+1] = constraints
[i
];
905 record_reg_classes (recog_data
.n_alternatives
, recog_data
.n_operands
,
906 recog_data
.operand
, modes
,
907 xconstraints
, insn
, op_costs
, reg_pref
);
909 record_reg_classes (recog_data
.n_alternatives
, recog_data
.n_operands
,
910 recog_data
.operand
, modes
,
911 constraints
, insn
, op_costs
, reg_pref
);
916 /* Process one insn INSN. Scan it and record each time it would save
917 code to put a certain pseudos in a certain class. Return the last
918 insn processed, so that the scan can be continued from there. */
920 scan_one_insn (rtx insn
)
922 enum rtx_code pat_code
;
925 struct costs op_costs
[MAX_RECOG_OPERANDS
];
930 pat_code
= GET_CODE (PATTERN (insn
));
931 if (pat_code
== USE
|| pat_code
== CLOBBER
|| pat_code
== ASM_INPUT
932 || pat_code
== ADDR_VEC
|| pat_code
== ADDR_DIFF_VEC
)
935 set
= single_set (insn
);
938 /* If this insn loads a parameter from its stack slot, then it
939 represents a savings, rather than a cost, if the parameter is
940 stored in memory. Record this fact. */
941 if (set
!= 0 && REG_P (SET_DEST (set
)) && MEM_P (SET_SRC (set
))
942 && (note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) != NULL_RTX
943 && MEM_P (XEXP (note
, 0)))
945 costs
[PSEUDO_NUM (curr_regno_pseudo_map
946 [REGNO (SET_DEST (set
))])].mem_cost
947 -= (memory_move_cost
[GET_MODE (SET_DEST (set
))] [GENERAL_REGS
] [1]
949 record_address_regs (GET_MODE (SET_SRC (set
)), XEXP (SET_SRC (set
), 0),
950 0, MEM
, SCRATCH
, frequency
* 2);
954 record_operand_costs (insn
, op_costs
, reg_pref
);
956 /* Now add the cost for each operand to the total costs for its
958 for (i
= 0; i
< recog_data
.n_operands
; i
++)
959 if (REG_P (recog_data
.operand
[i
])
960 && REGNO (recog_data
.operand
[i
]) >= FIRST_PSEUDO_REGISTER
)
962 int regno
= REGNO (recog_data
.operand
[i
]);
963 struct costs
*p
= &costs
[PSEUDO_NUM (curr_regno_pseudo_map
[regno
])];
964 struct costs
*q
= &op_costs
[i
];
966 p
->mem_cost
+= q
->mem_cost
* frequency
;
967 for (j
= 0; j
< N_REG_CLASSES
; j
++)
968 p
->cost
[j
] += q
->cost
[j
] * frequency
;
976 /* Dump pseudos costs. */
978 print_costs (FILE *f
)
983 for (i
= 0; i
< pseudos_num
; i
++)
987 pseudo_t p
= pseudos
[i
];
988 int regno
= PSEUDO_REGNO (p
);
990 fprintf (f
, " p%d(r%d,", i
, regno
);
991 if ((bb
= PSEUDO_LOOP_TREE_NODE (p
)->bb
) != NULL
)
992 fprintf (f
, "b%d", bb
->index
);
994 fprintf (f
, "l%d", PSEUDO_LOOP_TREE_NODE (p
)->loop
->num
);
995 fprintf (f
, ") costs:");
996 for (class = 0; class < (int) N_REG_CLASSES
; class++)
997 if (contains_reg_of_mode
[class] [PSEUDO_REGNO_MODE (regno
)]
998 #ifdef FORBIDDEN_INC_DEC_CLASSES
999 && (! in_inc_dec
[i
] || ! forbidden_inc_dec_class
[class])
1001 #ifdef CANNOT_CHANGE_MODE_CLASS
1002 && ! invalid_mode_change_p (i
, (enum reg_class
) class,
1003 PSEUDO_REGNO_MODE (regno
))
1006 fprintf (f
, " %s:%d", reg_class_names
[class],
1007 costs
[i
].cost
[class]);
1008 fprintf (f
, " MEM:%i\n", costs
[i
].mem_cost
);
1012 /* The function traverses basic blocks represented by LOOP_TREE_NODE
1013 to find the costs of the pseudos. */
1015 process_bb_node_for_costs (struct ira_loop_tree_node
*loop_tree_node
)
1020 bb
= loop_tree_node
->bb
;
1023 frequency
= REG_FREQ_FROM_BB (bb
);
1026 curr_regno_pseudo_map
= ira_curr_loop_tree_node
->regno_pseudo_map
;
1027 FOR_BB_INSNS (bb
, insn
)
1028 insn
= scan_one_insn (insn
);
1031 /* Entry function to find costs of each class cost for pesudos and
1032 their best classes. */
1034 find_pseudo_class_costs (void)
1041 #ifdef FORBIDDEN_INC_DEC_CLASSES
1042 in_inc_dec
= ira_allocate (sizeof (char) * pseudos_num
);
1043 #endif /* FORBIDDEN_INC_DEC_CLASSES */
1046 /* Normally we scan the insns once and determine the best class to
1047 use for each pseudo. However, if -fexpensive_optimizations are
1048 on, we do so twice, the second time using the tentative best
1049 classes to guide the selection. */
1050 for (pass
= 0; pass
<= flag_expensive_optimizations
; pass
++)
1053 fprintf (ira_dump_file
, "\nPass %i\n\n",pass
);
1054 /* Zero out our accumulation of the cost of each class for each
1056 memset (costs
, 0, pseudos_num
* sizeof (struct costs
));
1057 #ifdef FORBIDDEN_INC_DEC_CLASSES
1058 memset (in_inc_dec
, 0, pseudos_num
* sizeof (char));
1061 /* Scan the instructions and record each time it would save code
1062 to put a certain pseudo in a certain class. */
1063 traverse_loop_tree (ira_loop_tree_root
, process_bb_node_for_costs
, NULL
);
1065 /* Now for each pseudo look at how desirable each class is and
1066 find which class is preferred. Store that in `prefclass'.
1067 Record in `altclass' the largest register class any of whose
1068 registers is better than memory. */
1070 reg_pref
= reg_pref_buffer
;
1072 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
1074 pseudo_t p
, father_p
;
1075 int class, p_num
, father_p_num
;
1076 struct ira_loop_tree_node
*father
;
1077 int best_cost
= (1 << (HOST_BITS_PER_INT
- 2)) - 1;
1078 enum reg_class best
= ALL_REGS
;
1079 #ifdef FORBIDDEN_INC_DEC_CLASSES
1080 int inc_dec_p
= FALSE
;
1082 struct costs reg_costs
;
1084 if (regno_pseudo_map
[i
] == NULL
)
1086 memset (®_costs
, 0, sizeof (struct costs
));
1087 for (p
= regno_pseudo_map
[i
];
1089 p
= PSEUDO_NEXT_REGNO_PSEUDO (p
))
1091 p_num
= PSEUDO_NUM (p
);
1092 if (bitmap_bit_p (PSEUDO_LOOP_TREE_NODE (p
)->mentioned_pseudos
,
1095 if (flag_ira_algorithm
== IRA_ALGORITHM_REGIONAL
1096 && (father
= PSEUDO_LOOP_TREE_NODE (p
)->father
) != NULL
1097 && (father_p
= father
->regno_pseudo_map
[i
]) != NULL
)
1099 father_p_num
= PSEUDO_NUM (father_p
);
1100 for (class = (int) ALL_REGS
- 1; class > 0; class--)
1101 costs
[father_p_num
].cost
[class]
1102 += costs
[p_num
].cost
[class];
1103 costs
[father_p_num
].mem_cost
+= costs
[p_num
].mem_cost
;
1105 for (class = (int) ALL_REGS
- 1; class > 0; class--)
1106 reg_costs
.cost
[class] += costs
[p_num
].cost
[class];
1107 reg_costs
.mem_cost
+= costs
[p_num
].mem_cost
;
1108 #ifdef FORBIDDEN_INC_DEC_CLASSES
1109 if (in_inc_dec
[p_num
])
1114 for (class = (int) ALL_REGS
- 1; class > 0; class--)
1116 /* Ignore classes that are too small for this operand or
1117 invalid for an operand that was auto-incremented. */
1118 if (! contains_reg_of_mode
[class] [PSEUDO_REGNO_MODE (i
)]
1119 #ifdef FORBIDDEN_INC_DEC_CLASSES
1120 || (inc_dec_p
&& forbidden_inc_dec_class
[class])
1122 #ifdef CANNOT_CHANGE_MODE_CLASS
1123 || invalid_mode_change_p (i
, (enum reg_class
) class,
1124 PSEUDO_REGNO_MODE (i
))
1128 else if (reg_costs
.cost
[class] < best_cost
)
1130 best_cost
= reg_costs
.cost
[class];
1131 best
= (enum reg_class
) class;
1133 else if (reg_costs
.cost
[class] == best_cost
)
1134 best
= reg_class_subunion
[best
] [class];
1136 for (p
= regno_pseudo_map
[i
];
1138 p
= PSEUDO_NEXT_REGNO_PSEUDO (p
))
1140 p_num
= PSEUDO_NUM (p
);
1141 if (! bitmap_bit_p (PSEUDO_LOOP_TREE_NODE (p
)->mentioned_pseudos
,
1143 memset (&costs
[p_num
], 0, sizeof (struct costs
));
1144 if (ira_dump_file
&& (pass
== 0 || reg_pref
[p_num
] != best
))
1146 fprintf (ira_dump_file
, " p%d (r%d,", p_num
, i
);
1147 if ((bb
= PSEUDO_LOOP_TREE_NODE (p
)->bb
) != NULL
)
1148 fprintf (ira_dump_file
, "b%d", bb
->index
);
1150 fprintf (ira_dump_file
, "l%d",
1151 PSEUDO_LOOP_TREE_NODE (p
)->loop
->num
);
1152 fprintf (ira_dump_file
, ") best %s, cover %s\n",
1153 reg_class_names
[best
],
1154 reg_class_names
[class_translate
[best
]]);
1156 reg_pref
[p_num
] = best
;
1162 print_costs (ira_dump_file
);
1163 fprintf (ira_dump_file
,"\n");
1167 #ifdef FORBIDDEN_INC_DEC_CLASSES
1168 ira_free (in_inc_dec
);
1174 /* Process moves involving hard regs to modify pseudo hard register
1175 costs. We can do this only after determining pseudo cover class.
1176 If a hard register forms a register class, than moves with the hard
1177 register are already taken into account slightly in class costs for
1180 process_bb_node_for_hard_reg_moves (struct ira_loop_tree_node
*loop_tree_node
)
1182 int i
, freq
, cost
, src_regno
, dst_regno
, hard_regno
, to_p
;
1184 enum reg_class
class, hard_reg_class
;
1185 enum machine_mode mode
;
1187 rtx insn
, set
, src
, dst
;
1189 bb
= loop_tree_node
->bb
;
1192 freq
= REG_FREQ_FROM_BB (bb
);
1195 curr_regno_pseudo_map
= ira_curr_loop_tree_node
->regno_pseudo_map
;
1196 FOR_BB_INSNS (bb
, insn
)
1198 if (! INSN_P (insn
))
1200 set
= single_set (insn
);
1201 if (set
== NULL_RTX
)
1203 dst
= SET_DEST (set
);
1204 src
= SET_SRC (set
);
1205 if (! REG_P (dst
) || ! REG_P (src
))
1207 dst_regno
= REGNO (dst
);
1208 src_regno
= REGNO (src
);
1209 if (dst_regno
>= FIRST_PSEUDO_REGISTER
1210 && src_regno
< FIRST_PSEUDO_REGISTER
)
1212 hard_regno
= src_regno
;
1214 p
= curr_regno_pseudo_map
[dst_regno
];
1216 else if (src_regno
>= FIRST_PSEUDO_REGISTER
1217 && dst_regno
< FIRST_PSEUDO_REGISTER
)
1219 hard_regno
= dst_regno
;
1221 p
= curr_regno_pseudo_map
[src_regno
];
1225 class = PSEUDO_COVER_CLASS (p
);
1226 if (! TEST_HARD_REG_BIT (reg_class_contents
[class], hard_regno
))
1228 i
= class_hard_reg_index
[class] [hard_regno
];
1231 mode
= PSEUDO_MODE (p
);
1232 hard_reg_class
= REGNO_REG_CLASS (hard_regno
);
1233 cost
= (to_p
? register_move_cost
[mode
] [hard_reg_class
] [class]
1234 : register_move_cost
[mode
] [class] [hard_reg_class
]) * freq
;
1235 PSEUDO_HARD_REG_COSTS (p
) [i
] -= cost
;
1236 PSEUDO_CONFLICT_HARD_REG_COSTS (p
) [i
] -= cost
;
1237 PSEUDO_COVER_CLASS_COST (p
) = MIN (PSEUDO_COVER_CLASS_COST (p
),
1238 PSEUDO_HARD_REG_COSTS (p
) [i
]);
1239 if (flag_ira_algorithm
== IRA_ALGORITHM_REGIONAL
)
1241 struct ira_loop_tree_node
*father
;
1242 int regno
= PSEUDO_REGNO (p
);
1246 if ((father
= PSEUDO_LOOP_TREE_NODE (p
)->father
) == NULL
)
1248 if ((p
= father
->regno_pseudo_map
[regno
]) == NULL
)
1250 PSEUDO_HARD_REG_COSTS (p
) [i
] -= cost
;
1251 PSEUDO_CONFLICT_HARD_REG_COSTS (p
) [i
] -= cost
;
1252 PSEUDO_COVER_CLASS_COST (p
)
1253 = MIN (PSEUDO_COVER_CLASS_COST (p
),
1254 PSEUDO_HARD_REG_COSTS (p
) [i
]);
1260 /* After we find hard register and memory costs for pseudos, define
1261 its cover class and modify hard register cost because insns moving
1262 pseudo to/from hard registers. */
1264 setup_pseudo_cover_class_and_costs (void)
1266 int i
, j
, n
, regno
, cost
, *reg_costs
, *reg_conflict_costs
;
1267 enum reg_class cover_class
, class;
1268 enum machine_mode mode
;
1271 for (i
= 0; i
< pseudos_num
; i
++)
1274 mode
= PSEUDO_MODE (p
);
1275 cover_class
= class_translate
[reg_pref
[i
]];
1276 ira_assert (reg_pref
[i
] == NO_REGS
|| cover_class
!= NO_REGS
);
1277 PSEUDO_ORIGINAL_MEMORY_COST (p
)
1278 = PSEUDO_MEMORY_COST (p
) = costs
[i
].mem_cost
;
1281 if (costs
[i
].mem_cost
< costs
[i
].cost
[cover_class
])
1282 cover_class
= NO_REGS
;
1284 PSEUDO_COVER_CLASS (p
) = cover_class
;
1285 if (cover_class
== NO_REGS
)
1287 PSEUDO_AVAILABLE_REGS_NUM (p
) = available_class_regs
[cover_class
];
1288 PSEUDO_COVER_CLASS_COST (p
) = costs
[i
].cost
[reg_pref
[i
]];
1289 n
= class_hard_regs_num
[cover_class
];
1290 PSEUDO_HARD_REG_COSTS (p
) = reg_costs
= ira_allocate (n
* sizeof (int));
1291 PSEUDO_CONFLICT_HARD_REG_COSTS (p
)
1292 = reg_conflict_costs
= ira_allocate (n
* sizeof (int));
1293 PSEUDO_CURR_HARD_REG_COSTS (p
) = ira_allocate (n
* sizeof (int));
1294 PSEUDO_CURR_CONFLICT_HARD_REG_COSTS (p
)
1295 = ira_allocate (n
* sizeof (int));
1296 memset (reg_conflict_costs
, 0, n
* sizeof (int));
1297 for (j
= n
- 1; j
>= 0; j
--)
1299 regno
= class_hard_regs
[cover_class
] [j
];
1300 class = REGNO_REG_CLASS (regno
);
1301 /* ??? what is cost AREG when DImode. Should be ok. */
1302 cost
= costs
[i
].cost
[class];
1303 reg_costs
[j
] = cost
;
1306 traverse_loop_tree (ira_loop_tree_root
,
1307 process_bb_node_for_hard_reg_moves
, NULL
);
1312 /* Function called once during compiler work. It sets up init_cost
1313 whose values don't depend on the compiled function. */
1315 init_ira_costs_once (void)
1319 init_cost
.mem_cost
= 10000;
1320 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1321 init_cost
.cost
[i
] = 10000;
1326 /* Entry function which defines cover class, memory and hard register
1327 costs for each pseudo. */
1331 costs
= ira_allocate (sizeof (struct costs
) * pseudos_num
);
1332 reg_pref_buffer
= ira_allocate (sizeof (enum reg_class
) * pseudos_num
);
1333 find_pseudo_class_costs ();
1334 setup_pseudo_cover_class_and_costs ();
1335 ira_free (reg_pref_buffer
);
1341 /* This function changes hard register costs for pseudos which lives
1342 trough function calls. The function is called only when we found
1343 all intersected calls during building pseudo conflicts. */
1345 tune_pseudo_costs_and_cover_classes (void)
1347 int i
, j
, k
, n
, regno
, cost
, min_cost
, *reg_costs
, freq
;
1348 enum reg_class cover_class
, class;
1349 enum machine_mode mode
;
1351 rtx call
, *pseudo_calls
;
1352 HARD_REG_SET clobbered_regs
;
1354 for (i
= 0; i
< pseudos_num
; i
++)
1357 cover_class
= PSEUDO_COVER_CLASS (p
);
1358 if (cover_class
== NO_REGS
)
1360 mode
= PSEUDO_MODE (p
);
1361 n
= class_hard_regs_num
[cover_class
];
1362 reg_costs
= PSEUDO_HARD_REG_COSTS (p
);
1364 if (PSEUDO_CALLS_CROSSED_NUM (p
) != 0)
1365 for (j
= n
- 1; j
>= 0; j
--)
1367 regno
= class_hard_regs
[cover_class
] [j
];
1368 class = REGNO_REG_CLASS (regno
);
1372 /* ??? If only part is call clobbered. */
1373 if (! hard_reg_not_in_set_p (regno
, mode
, call_used_reg_set
))
1374 cost
+= (PSEUDO_CALL_FREQ (p
)
1375 * (memory_move_cost
[mode
] [class] [0]
1376 + memory_move_cost
[mode
] [class] [1]));
1380 pseudo_calls
= PSEUDO_CALLS_CROSSED (p
);
1381 ira_assert (pseudo_calls
!= NULL
);
1382 for (k
= PSEUDO_CALLS_CROSSED_NUM (p
) - 1; k
>= 0; k
--)
1384 call
= pseudo_calls
[k
];
1385 freq
= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (call
));
1388 get_call_invalidated_used_regs (call
, &clobbered_regs
,
1390 /* ??? If only part is call clobbered. */
1391 if (! hard_reg_not_in_set_p (regno
, mode
, clobbered_regs
))
1392 cost
+= freq
* (memory_move_cost
[mode
] [class] [0]
1393 + memory_move_cost
[mode
] [class] [1]);
1396 #ifdef IRA_HARD_REGNO_ADD_COST_MULTIPLIER
1397 cost
+= ((memory_move_cost
[mode
] [class] [0]
1398 + memory_move_cost
[mode
] [class] [1]) * PSEUDO_FREQ (p
)
1399 * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno
) / 2);
1401 reg_costs
[j
] += cost
;
1402 if (min_cost
> reg_costs
[j
])
1403 min_cost
= reg_costs
[j
];
1405 if (min_cost
== INT_MAX
)
1407 PSEUDO_COVER_CLASS_COST (p
) = min_cost
;