1 /* IRA hard register and memory cost calculation for allocnos or pseudos.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
26 #include "hard-reg-set.h"
31 #include "basic-block.h"
33 #include "addresses.h"
34 #include "insn-config.h"
37 #include "diagnostic-core.h"
42 /* The flags is set up every time when we calculate pseudo register
43 classes through function ira_set_pseudo_classes. */
44 static bool pseudo_classes_defined_p = false;
46 /* TRUE if we work with allocnos. Otherwise we work with pseudos. */
47 static bool allocno_p;
49 /* Number of elements in array `costs'. */
50 static int cost_elements_num;
52 /* The `costs' struct records the cost of using hard registers of each
53 class considered for the calculation and of using memory for each
58 /* Costs for register classes start here. We process only some
63 #define max_struct_costs_size \
64 (this_target_ira_int->x_max_struct_costs_size)
66 (this_target_ira_int->x_init_cost)
68 (this_target_ira_int->x_temp_costs)
70 (this_target_ira_int->x_op_costs)
71 #define this_op_costs \
72 (this_target_ira_int->x_this_op_costs)
74 /* Costs of each class for each allocno or pseudo. */
75 static struct costs *costs;
77 /* Accumulated costs of each class for each allocno. */
78 static struct costs *total_allocno_costs;
80 /* It is the current size of struct costs. */
81 static int struct_costs_size;
83 /* Return pointer to structure containing costs of allocno or pseudo
84 with given NUM in array ARR. */
85 #define COSTS(arr, num) \
86 ((struct costs *) ((char *) (arr) + (num) * struct_costs_size))
88 /* Return index in COSTS when processing reg with REGNO. */
89 #define COST_INDEX(regno) (allocno_p \
90 ? ALLOCNO_NUM (ira_curr_regno_allocno_map[regno]) \
93 /* Record register class preferences of each allocno or pseudo. Null
94 value means no preferences. It happens on the 1st iteration of the
96 static enum reg_class *pref;
98 /* Allocated buffers for pref. */
99 static enum reg_class *pref_buffer;
101 /* Record allocno class of each allocno with the same regno. */
102 static enum reg_class *regno_aclass;
104 /* Record cost gains for not allocating a register with an invariant
106 static int *regno_equiv_gains;
108 /* Execution frequency of the current insn. */
109 static int frequency;
113 /* Info about reg classes whose costs are calculated for a pseudo. */
116 /* Number of the cost classes in the subsequent array. */
118 /* Container of the cost classes. */
119 enum reg_class classes[N_REG_CLASSES];
120 /* Map reg class -> index of the reg class in the previous array.
121 -1 if it is not a cost classe. */
122 int index[N_REG_CLASSES];
123 /* Map hard regno index of first class in array CLASSES containing
124 the hard regno, -1 otherwise. */
125 int hard_regno_index[FIRST_PSEUDO_REGISTER];
128 /* Types of pointers to the structure above. */
129 typedef struct cost_classes *cost_classes_t;
130 typedef const struct cost_classes *const_cost_classes_t;
132 /* Info about cost classes for each pseudo. */
133 static cost_classes_t *regno_cost_classes;
135 /* Returns hash value for cost classes info V. */
137 cost_classes_hash (const void *v)
139 const_cost_classes_t hv = (const_cost_classes_t) v;
141 return iterative_hash (&hv->classes, sizeof (enum reg_class) * hv->num, 0);
144 /* Compares cost classes info V1 and V2. */
146 cost_classes_eq (const void *v1, const void *v2)
148 const_cost_classes_t hv1 = (const_cost_classes_t) v1;
149 const_cost_classes_t hv2 = (const_cost_classes_t) v2;
151 return hv1->num == hv2->num && memcmp (hv1->classes, hv2->classes,
152 sizeof (enum reg_class) * hv1->num);
155 /* Delete cost classes info V from the hash table. */
157 cost_classes_del (void *v)
162 /* Hash table of unique cost classes. */
163 static htab_t cost_classes_htab;
165 /* Map allocno class -> cost classes for pseudo of given allocno
167 static cost_classes_t cost_classes_aclass_cache[N_REG_CLASSES];
169 /* Map mode -> cost classes for pseudo of give mode. */
170 static cost_classes_t cost_classes_mode_cache[MAX_MACHINE_MODE];
172 /* Initialize info about the cost classes for each pseudo. */
174 initiate_regno_cost_classes (void)
176 int size = sizeof (cost_classes_t) * max_reg_num ();
178 regno_cost_classes = (cost_classes_t *) ira_allocate (size);
179 memset (regno_cost_classes, 0, size);
180 memset (cost_classes_aclass_cache, 0,
181 sizeof (cost_classes_t) * N_REG_CLASSES);
182 memset (cost_classes_mode_cache, 0,
183 sizeof (cost_classes_t) * MAX_MACHINE_MODE);
185 = htab_create (200, cost_classes_hash, cost_classes_eq, cost_classes_del);
188 /* Create new cost classes from cost classes FROM and set up members
189 index and hard_regno_index. Return the new classes. The function
190 implements some common code of two functions
191 setup_regno_cost_classes_by_aclass and
192 setup_regno_cost_classes_by_mode. */
193 static cost_classes_t
194 setup_cost_classes (cost_classes_t from)
196 cost_classes_t classes_ptr;
198 int i, j, hard_regno;
200 classes_ptr = (cost_classes_t) ira_allocate (sizeof (struct cost_classes));
201 classes_ptr->num = from->num;
202 for (i = 0; i < N_REG_CLASSES; i++)
203 classes_ptr->index[i] = -1;
204 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
205 classes_ptr->hard_regno_index[i] = -1;
206 for (i = 0; i < from->num; i++)
208 cl = classes_ptr->classes[i] = from->classes[i];
209 classes_ptr->index[cl] = i;
210 for (j = ira_class_hard_regs_num[cl] - 1; j >= 0; j--)
212 hard_regno = ira_class_hard_regs[cl][j];
213 if (classes_ptr->hard_regno_index[hard_regno] < 0)
214 classes_ptr->hard_regno_index[hard_regno] = i;
220 /* Setup cost classes for pseudo REGNO whose allocno class is ACLASS.
221 This function is used when we know an initial approximation of
222 allocno class of the pseudo already, e.g. on the second iteration
223 of class cost calculation or after class cost calculation in
224 register-pressure sensitive insn scheduling or register-pressure
225 sensitive loop-invariant motion. */
227 setup_regno_cost_classes_by_aclass (int regno, enum reg_class aclass)
229 static struct cost_classes classes;
230 cost_classes_t classes_ptr;
234 HARD_REG_SET temp, temp2;
236 if ((classes_ptr = cost_classes_aclass_cache[aclass]) == NULL)
238 COPY_HARD_REG_SET (temp, reg_class_contents[aclass]);
239 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
241 for (i = 0; i < ira_important_classes_num; i++)
243 cl = ira_important_classes[i];
244 COPY_HARD_REG_SET (temp2, reg_class_contents[cl]);
245 AND_COMPL_HARD_REG_SET (temp2, ira_no_alloc_regs);
246 if (! ira_reg_pressure_class_p[cl]
247 && hard_reg_set_subset_p (temp2, temp) && cl != aclass)
249 classes.classes[classes.num++] = cl;
251 slot = htab_find_slot (cost_classes_htab, &classes, INSERT);
254 classes_ptr = setup_cost_classes (&classes);
257 classes_ptr = cost_classes_aclass_cache[aclass] = (cost_classes_t) *slot;
259 regno_cost_classes[regno] = classes_ptr;
262 /* Setup cost classes for pseudo REGNO with MODE. Usage of MODE can
263 decrease number of cost classes for the pseudo, if hard registers
264 of some important classes can not hold a value of MODE. So the
265 pseudo can not get hard register of some important classes and cost
266 calculation for such important classes is only waisting CPU
269 setup_regno_cost_classes_by_mode (int regno, enum machine_mode mode)
271 static struct cost_classes classes;
272 cost_classes_t classes_ptr;
278 if ((classes_ptr = cost_classes_mode_cache[mode]) == NULL)
281 for (i = 0; i < ira_important_classes_num; i++)
283 cl = ira_important_classes[i];
284 COPY_HARD_REG_SET (temp, ira_prohibited_class_mode_regs[cl][mode]);
285 IOR_HARD_REG_SET (temp, ira_no_alloc_regs);
286 if (hard_reg_set_subset_p (reg_class_contents[cl], temp))
288 classes.classes[classes.num++] = cl;
290 slot = htab_find_slot (cost_classes_htab, &classes, INSERT);
293 classes_ptr = setup_cost_classes (&classes);
297 classes_ptr = (cost_classes_t) *slot;
298 cost_classes_mode_cache[mode] = (cost_classes_t) *slot;
300 regno_cost_classes[regno] = classes_ptr;
303 /* Finilize info about the cost classes for each pseudo. */
305 finish_regno_cost_classes (void)
307 ira_free (regno_cost_classes);
308 htab_delete (cost_classes_htab);
313 /* Compute the cost of loading X into (if TO_P is TRUE) or from (if
314 TO_P is FALSE) a register of class RCLASS in mode MODE. X must not
315 be a pseudo register. */
317 copy_cost (rtx x, enum machine_mode mode, reg_class_t rclass, bool to_p,
318 secondary_reload_info *prev_sri)
320 secondary_reload_info sri;
321 reg_class_t secondary_class = NO_REGS;
323 /* If X is a SCRATCH, there is actually nothing to move since we are
324 assuming optimal allocation. */
325 if (GET_CODE (x) == SCRATCH)
328 /* Get the class we will actually use for a reload. */
329 rclass = targetm.preferred_reload_class (x, rclass);
331 /* If we need a secondary reload for an intermediate, the cost is
332 that to load the input into the intermediate register, then to
334 sri.prev_sri = prev_sri;
336 secondary_class = targetm.secondary_reload (to_p, x, rclass, mode, &sri);
338 if (secondary_class != NO_REGS)
340 if (!move_cost[mode])
341 init_move_cost (mode);
342 return (move_cost[mode][(int) secondary_class][(int) rclass]
344 + copy_cost (x, mode, secondary_class, to_p, &sri));
347 /* For memory, use the memory move cost, for (hard) registers, use
348 the cost to move between the register classes, and use 2 for
349 everything else (constants). */
350 if (MEM_P (x) || rclass == NO_REGS)
351 return sri.extra_cost
352 + ira_memory_move_cost[mode][(int) rclass][to_p != 0];
355 if (!move_cost[mode])
356 init_move_cost (mode);
357 return (sri.extra_cost
358 + move_cost[mode][REGNO_REG_CLASS (REGNO (x))][(int) rclass]);
361 /* If this is a constant, we may eventually want to call rtx_cost
363 return sri.extra_cost + COSTS_N_INSNS (1);
368 /* Record the cost of using memory or hard registers of various
369 classes for the operands in INSN.
371 N_ALTS is the number of alternatives.
372 N_OPS is the number of operands.
373 OPS is an array of the operands.
374 MODES are the modes of the operands, in case any are VOIDmode.
375 CONSTRAINTS are the constraints to use for the operands. This array
376 is modified by this procedure.
378 This procedure works alternative by alternative. For each
379 alternative we assume that we will be able to allocate all allocnos
380 to their ideal register class and calculate the cost of using that
381 alternative. Then we compute, for each operand that is a
382 pseudo-register, the cost of having the allocno allocated to each
383 register class and using it in that alternative. To this cost is
384 added the cost of the alternative.
386 The cost of each class for this insn is its lowest cost among all
389 record_reg_classes (int n_alts, int n_ops, rtx *ops,
390 enum machine_mode *modes, const char **constraints,
391 rtx insn, enum reg_class *pref)
396 int insn_allows_mem[MAX_RECOG_OPERANDS];
398 for (i = 0; i < n_ops; i++)
399 insn_allows_mem[i] = 0;
401 /* Process each alternative, each time minimizing an operand's cost
402 with the cost for each operand in that alternative. */
403 for (alt = 0; alt < n_alts; alt++)
405 enum reg_class classes[MAX_RECOG_OPERANDS];
406 int allows_mem[MAX_RECOG_OPERANDS];
407 enum reg_class rclass;
409 int alt_cost = 0, op_cost_add;
411 if (!recog_data.alternative_enabled_p[alt])
413 for (i = 0; i < recog_data.n_operands; i++)
414 constraints[i] = skip_alternative (constraints[i]);
419 for (i = 0; i < n_ops; i++)
422 const char *p = constraints[i];
424 enum machine_mode mode = modes[i];
428 /* Initially show we know nothing about the register class. */
429 classes[i] = NO_REGS;
432 /* If this operand has no constraints at all, we can
433 conclude nothing about it since anything is valid. */
436 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
437 memset (this_op_costs[i], 0, struct_costs_size);
441 /* If this alternative is only relevant when this operand
442 matches a previous operand, we do different things
443 depending on whether this operand is a allocno-reg or not.
444 We must process any modifiers for the operand before we
445 can make this test. */
446 while (*p == '%' || *p == '=' || *p == '+' || *p == '&')
449 if (p[0] >= '0' && p[0] <= '0' + i && (p[1] == ',' || p[1] == 0))
451 /* Copy class and whether memory is allowed from the
452 matching alternative. Then perform any needed cost
453 computations and/or adjustments. */
455 classes[i] = classes[j];
456 allows_mem[i] = allows_mem[j];
458 insn_allows_mem[i] = 1;
460 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
462 /* If this matches the other operand, we have no
463 added cost and we win. */
464 if (rtx_equal_p (ops[j], op))
466 /* If we can put the other operand into a register,
467 add to the cost of this alternative the cost to
468 copy this operand to the register used for the
470 else if (classes[j] != NO_REGS)
472 alt_cost += copy_cost (op, mode, classes[j], 1, NULL);
476 else if (! REG_P (ops[j])
477 || REGNO (ops[j]) < FIRST_PSEUDO_REGISTER)
479 /* This op is an allocno but the one it matches is
482 /* If we can't put the other operand into a
483 register, this alternative can't be used. */
485 if (classes[j] == NO_REGS)
487 /* Otherwise, add to the cost of this alternative
488 the cost to copy the other operand to the hard
489 register used for this operand. */
491 alt_cost += copy_cost (ops[j], mode, classes[j], 1, NULL);
495 /* The costs of this operand are not the same as the
496 other operand since move costs are not symmetric.
497 Moreover, if we cannot tie them, this alternative
498 needs to do a copy, which is one insn. */
499 struct costs *pp = this_op_costs[i];
500 int *pp_costs = pp->cost;
501 cost_classes_t cost_classes_ptr
502 = regno_cost_classes[REGNO (op)];
503 enum reg_class *cost_classes = cost_classes_ptr->classes;
504 bool in_p = recog_data.operand_type[i] != OP_OUT;
505 bool out_p = recog_data.operand_type[i] != OP_IN;
506 enum reg_class op_class = classes[i];
507 move_table *move_in_cost, *move_out_cost;
509 ira_init_register_move_cost_if_necessary (mode);
513 move_out_cost = ira_may_move_out_cost[mode];
514 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
516 rclass = cost_classes[k];
518 = move_out_cost[op_class][rclass] * frequency;
524 move_in_cost = ira_may_move_in_cost[mode];
525 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
527 rclass = cost_classes[k];
529 = move_in_cost[rclass][op_class] * frequency;
534 move_in_cost = ira_may_move_in_cost[mode];
535 move_out_cost = ira_may_move_out_cost[mode];
536 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
538 rclass = cost_classes[k];
539 pp_costs[k] = ((move_in_cost[rclass][op_class]
540 + move_out_cost[op_class][rclass])
545 /* If the alternative actually allows memory, make
546 things a bit cheaper since we won't need an extra
549 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
550 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
551 - allows_mem[i]) * frequency;
553 /* If we have assigned a class to this allocno in
554 our first pass, add a cost to this alternative
555 corresponding to what we would add if this
556 allocno were not in the appropriate class. */
559 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
561 if (pref_class == NO_REGS)
564 ? ira_memory_move_cost[mode][op_class][0] : 0)
566 ? ira_memory_move_cost[mode][op_class][1]
568 else if (ira_reg_class_intersect
569 [pref_class][op_class] == NO_REGS)
571 += ira_register_move_cost[mode][pref_class][op_class];
573 if (REGNO (ops[i]) != REGNO (ops[j])
574 && ! find_reg_note (insn, REG_DEAD, op))
577 /* This is in place of ordinary cost computation for
578 this operand, so skip to the end of the
579 alternative (should be just one character). */
580 while (*p && *p++ != ',')
588 /* Scan all the constraint letters. See if the operand
589 matches any of the constraints. Collect the valid
590 register classes and see if this operand accepts
599 /* Ignore the next letter for this pass. */
605 case '!': case '#': case '&':
606 case '0': case '1': case '2': case '3': case '4':
607 case '5': case '6': case '7': case '8': case '9':
612 win = address_operand (op, GET_MODE (op));
613 /* We know this operand is an address, so we want it
614 to be allocated to a register that can be the
615 base of an address, i.e. BASE_REG_CLASS. */
617 = ira_reg_class_subunion[classes[i]]
618 [base_reg_class (VOIDmode, ADDRESS, SCRATCH)];
621 case 'm': case 'o': case 'V':
622 /* It doesn't seem worth distinguishing between
623 offsettable and non-offsettable addresses
625 insn_allows_mem[i] = allows_mem[i] = 1;
632 && (GET_CODE (XEXP (op, 0)) == PRE_DEC
633 || GET_CODE (XEXP (op, 0)) == POST_DEC))
639 && (GET_CODE (XEXP (op, 0)) == PRE_INC
640 || GET_CODE (XEXP (op, 0)) == POST_INC))
646 if (GET_CODE (op) == CONST_DOUBLE
647 || (GET_CODE (op) == CONST_VECTOR
648 && (GET_MODE_CLASS (GET_MODE (op))
649 == MODE_VECTOR_FLOAT)))
655 if (GET_CODE (op) == CONST_DOUBLE
656 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, p))
662 || (GET_CODE (op) == CONST_DOUBLE
663 && GET_MODE (op) == VOIDmode))
668 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op)))
674 || (GET_CODE (op) == CONST_DOUBLE
675 && GET_MODE (op) == VOIDmode))
688 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, p))
699 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))))
701 insn_allows_mem[i] = allows_mem[i] = 1;
703 classes[i] = ira_reg_class_subunion[classes[i]][GENERAL_REGS];
707 if (REG_CLASS_FROM_CONSTRAINT (c, p) != NO_REGS)
708 classes[i] = ira_reg_class_subunion[classes[i]]
709 [REG_CLASS_FROM_CONSTRAINT (c, p)];
710 #ifdef EXTRA_CONSTRAINT_STR
711 else if (EXTRA_CONSTRAINT_STR (op, c, p))
714 if (EXTRA_MEMORY_CONSTRAINT (c, p))
716 /* Every MEM can be reloaded to fit. */
717 insn_allows_mem[i] = allows_mem[i] = 1;
721 if (EXTRA_ADDRESS_CONSTRAINT (c, p))
723 /* Every address can be reloaded to fit. */
725 if (address_operand (op, GET_MODE (op)))
727 /* We know this operand is an address, so we
728 want it to be allocated to a hard register
729 that can be the base of an address,
730 i.e. BASE_REG_CLASS. */
732 = ira_reg_class_subunion[classes[i]]
733 [base_reg_class (VOIDmode, ADDRESS, SCRATCH)];
738 p += CONSTRAINT_LEN (c, p);
745 /* How we account for this operand now depends on whether it
746 is a pseudo register or not. If it is, we first check if
747 any register classes are valid. If not, we ignore this
748 alternative, since we want to assume that all allocnos get
749 allocated for register preferencing. If some register
750 class is valid, compute the costs of moving the allocno
752 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
754 if (classes[i] == NO_REGS)
756 /* We must always fail if the operand is a REG, but
757 we did not find a suitable class.
759 Otherwise we may perform an uninitialized read
760 from this_op_costs after the `continue' statement
766 unsigned int regno = REGNO (op);
767 struct costs *pp = this_op_costs[i];
768 int *pp_costs = pp->cost;
769 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
770 enum reg_class *cost_classes = cost_classes_ptr->classes;
771 bool in_p = recog_data.operand_type[i] != OP_OUT;
772 bool out_p = recog_data.operand_type[i] != OP_IN;
773 enum reg_class op_class = classes[i];
774 move_table *move_in_cost, *move_out_cost;
776 ira_init_register_move_cost_if_necessary (mode);
780 move_out_cost = ira_may_move_out_cost[mode];
781 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
783 rclass = cost_classes[k];
785 = move_out_cost[op_class][rclass] * frequency;
791 move_in_cost = ira_may_move_in_cost[mode];
792 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
794 rclass = cost_classes[k];
796 = move_in_cost[rclass][op_class] * frequency;
801 move_in_cost = ira_may_move_in_cost[mode];
802 move_out_cost = ira_may_move_out_cost[mode];
803 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
805 rclass = cost_classes[k];
806 pp_costs[k] = ((move_in_cost[rclass][op_class]
807 + move_out_cost[op_class][rclass])
812 /* If the alternative actually allows memory, make
813 things a bit cheaper since we won't need an extra
816 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
817 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
818 - allows_mem[i]) * frequency;
819 /* If we have assigned a class to this allocno in
820 our first pass, add a cost to this alternative
821 corresponding to what we would add if this
822 allocno were not in the appropriate class. */
825 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
827 if (pref_class == NO_REGS)
830 ? ira_memory_move_cost[mode][op_class][0] : 0)
832 ? ira_memory_move_cost[mode][op_class][1]
834 else if (ira_reg_class_intersect[pref_class][op_class]
836 alt_cost += ira_register_move_cost[mode][pref_class][op_class];
841 /* Otherwise, if this alternative wins, either because we
842 have already determined that or if we have a hard
843 register of the proper class, there is no cost for this
845 else if (win || (REG_P (op)
846 && reg_fits_class_p (op, classes[i],
850 /* If registers are valid, the cost of this alternative
851 includes copying the object to and/or from a
853 else if (classes[i] != NO_REGS)
855 if (recog_data.operand_type[i] != OP_OUT)
856 alt_cost += copy_cost (op, mode, classes[i], 1, NULL);
858 if (recog_data.operand_type[i] != OP_IN)
859 alt_cost += copy_cost (op, mode, classes[i], 0, NULL);
861 /* The only other way this alternative can be used is if
862 this is a constant that could be placed into memory. */
863 else if (CONSTANT_P (op) && (allows_addr || allows_mem[i]))
864 alt_cost += ira_memory_move_cost[mode][classes[i]][1];
872 op_cost_add = alt_cost * frequency;
873 /* Finally, update the costs with the information we've
874 calculated about this alternative. */
875 for (i = 0; i < n_ops; i++)
876 if (REG_P (ops[i]) && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
878 struct costs *pp = op_costs[i], *qq = this_op_costs[i];
879 int *pp_costs = pp->cost, *qq_costs = qq->cost;
880 int scale = 1 + (recog_data.operand_type[i] == OP_INOUT);
881 cost_classes_t cost_classes_ptr
882 = regno_cost_classes[REGNO (ops[i])];
884 pp->mem_cost = MIN (pp->mem_cost,
885 (qq->mem_cost + op_cost_add) * scale);
887 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
889 = MIN (pp_costs[k], (qq_costs[k] + op_cost_add) * scale);
894 for (i = 0; i < n_ops; i++)
899 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
901 a = ira_curr_regno_allocno_map [REGNO (op)];
902 if (! ALLOCNO_BAD_SPILL_P (a) && insn_allows_mem[i] == 0)
903 ALLOCNO_BAD_SPILL_P (a) = true;
906 /* If this insn is a single set copying operand 1 to operand 0 and
907 one operand is an allocno with the other a hard reg or an allocno
908 that prefers a hard register that is in its own register class
909 then we may want to adjust the cost of that register class to -1.
911 Avoid the adjustment if the source does not die to avoid
912 stressing of register allocator by preferrencing two colliding
913 registers into single class.
915 Also avoid the adjustment if a copy between hard registers of the
916 class is expensive (ten times the cost of a default copy is
917 considered arbitrarily expensive). This avoids losing when the
918 preferred class is very expensive as the source of a copy
920 if ((set = single_set (insn)) != 0
921 && ops[0] == SET_DEST (set) && ops[1] == SET_SRC (set)
922 && REG_P (ops[0]) && REG_P (ops[1])
923 && find_regno_note (insn, REG_DEAD, REGNO (ops[1])))
924 for (i = 0; i <= 1; i++)
925 if (REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER
926 && REGNO (ops[!i]) < FIRST_PSEUDO_REGISTER)
928 unsigned int regno = REGNO (ops[i]);
929 unsigned int other_regno = REGNO (ops[!i]);
930 enum machine_mode mode = GET_MODE (ops[!i]);
931 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
932 enum reg_class *cost_classes = cost_classes_ptr->classes;
933 enum reg_class rclass;
936 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
938 rclass = cost_classes[k];
939 if (TEST_HARD_REG_BIT (reg_class_contents[rclass], other_regno)
940 && (reg_class_size[rclass]
941 == (unsigned) CLASS_MAX_NREGS (rclass, mode)))
943 if (reg_class_size[rclass] == 1)
944 op_costs[i]->cost[k] = -frequency;
948 nr < hard_regno_nregs[other_regno][mode];
950 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass],
954 if (nr == hard_regno_nregs[other_regno][mode])
955 op_costs[i]->cost[k] = -frequency;
964 /* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudo registers. */
966 ok_for_index_p_nonstrict (rtx reg)
968 unsigned regno = REGNO (reg);
970 return regno >= FIRST_PSEUDO_REGISTER || REGNO_OK_FOR_INDEX_P (regno);
973 /* A version of regno_ok_for_base_p for use here, when all
974 pseudo-registers should count as OK. Arguments as for
975 regno_ok_for_base_p. */
977 ok_for_base_p_nonstrict (rtx reg, enum machine_mode mode,
978 enum rtx_code outer_code, enum rtx_code index_code)
980 unsigned regno = REGNO (reg);
982 if (regno >= FIRST_PSEUDO_REGISTER)
984 return ok_for_base_p_1 (regno, mode, outer_code, index_code);
987 /* Record the pseudo registers we must reload into hard registers in a
988 subexpression of a memory address, X.
990 If CONTEXT is 0, we are looking at the base part of an address,
991 otherwise we are looking at the index part.
993 MODE is the mode of the memory reference; OUTER_CODE and INDEX_CODE
994 give the context that the rtx appears in. These three arguments
995 are passed down to base_reg_class.
997 SCALE is twice the amount to multiply the cost by (it is twice so
998 we can represent half-cost adjustments). */
1000 record_address_regs (enum machine_mode mode, rtx x, int context,
1001 enum rtx_code outer_code, enum rtx_code index_code,
1004 enum rtx_code code = GET_CODE (x);
1005 enum reg_class rclass;
1008 rclass = INDEX_REG_CLASS;
1010 rclass = base_reg_class (mode, outer_code, index_code);
1023 /* When we have an address that is a sum, we must determine
1024 whether registers are "base" or "index" regs. If there is a
1025 sum of two registers, we must choose one to be the "base".
1026 Luckily, we can use the REG_POINTER to make a good choice
1027 most of the time. We only need to do this on machines that
1028 can have two registers in an address and where the base and
1029 index register classes are different.
1031 ??? This code used to set REGNO_POINTER_FLAG in some cases,
1032 but that seems bogus since it should only be set when we are
1033 sure the register is being used as a pointer. */
1035 rtx arg0 = XEXP (x, 0);
1036 rtx arg1 = XEXP (x, 1);
1037 enum rtx_code code0 = GET_CODE (arg0);
1038 enum rtx_code code1 = GET_CODE (arg1);
1040 /* Look inside subregs. */
1041 if (code0 == SUBREG)
1042 arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
1043 if (code1 == SUBREG)
1044 arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
1046 /* If this machine only allows one register per address, it
1047 must be in the first operand. */
1048 if (MAX_REGS_PER_ADDRESS == 1)
1049 record_address_regs (mode, arg0, 0, PLUS, code1, scale);
1051 /* If index and base registers are the same on this machine,
1052 just record registers in any non-constant operands. We
1053 assume here, as well as in the tests below, that all
1054 addresses are in canonical form. */
1055 else if (INDEX_REG_CLASS == base_reg_class (VOIDmode, PLUS, SCRATCH))
1057 record_address_regs (mode, arg0, context, PLUS, code1, scale);
1058 if (! CONSTANT_P (arg1))
1059 record_address_regs (mode, arg1, context, PLUS, code0, scale);
1062 /* If the second operand is a constant integer, it doesn't
1063 change what class the first operand must be. */
1064 else if (code1 == CONST_INT || code1 == CONST_DOUBLE)
1065 record_address_regs (mode, arg0, context, PLUS, code1, scale);
1066 /* If the second operand is a symbolic constant, the first
1067 operand must be an index register. */
1068 else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF)
1069 record_address_regs (mode, arg0, 1, PLUS, code1, scale);
1070 /* If both operands are registers but one is already a hard
1071 register of index or reg-base class, give the other the
1072 class that the hard register is not. */
1073 else if (code0 == REG && code1 == REG
1074 && REGNO (arg0) < FIRST_PSEUDO_REGISTER
1075 && (ok_for_base_p_nonstrict (arg0, mode, PLUS, REG)
1076 || ok_for_index_p_nonstrict (arg0)))
1077 record_address_regs (mode, arg1,
1078 ok_for_base_p_nonstrict (arg0, mode, PLUS, REG)
1081 else if (code0 == REG && code1 == REG
1082 && REGNO (arg1) < FIRST_PSEUDO_REGISTER
1083 && (ok_for_base_p_nonstrict (arg1, mode, PLUS, REG)
1084 || ok_for_index_p_nonstrict (arg1)))
1085 record_address_regs (mode, arg0,
1086 ok_for_base_p_nonstrict (arg1, mode, PLUS, REG)
1089 /* If one operand is known to be a pointer, it must be the
1090 base with the other operand the index. Likewise if the
1091 other operand is a MULT. */
1092 else if ((code0 == REG && REG_POINTER (arg0)) || code1 == MULT)
1094 record_address_regs (mode, arg0, 0, PLUS, code1, scale);
1095 record_address_regs (mode, arg1, 1, PLUS, code0, scale);
1097 else if ((code1 == REG && REG_POINTER (arg1)) || code0 == MULT)
1099 record_address_regs (mode, arg0, 1, PLUS, code1, scale);
1100 record_address_regs (mode, arg1, 0, PLUS, code0, scale);
1102 /* Otherwise, count equal chances that each might be a base or
1103 index register. This case should be rare. */
1106 record_address_regs (mode, arg0, 0, PLUS, code1, scale / 2);
1107 record_address_regs (mode, arg0, 1, PLUS, code1, scale / 2);
1108 record_address_regs (mode, arg1, 0, PLUS, code0, scale / 2);
1109 record_address_regs (mode, arg1, 1, PLUS, code0, scale / 2);
1114 /* Double the importance of an allocno that is incremented or
1115 decremented, since it would take two extra insns if it ends
1116 up in the wrong place. */
1119 record_address_regs (mode, XEXP (x, 0), 0, code,
1120 GET_CODE (XEXP (XEXP (x, 1), 1)), 2 * scale);
1121 if (REG_P (XEXP (XEXP (x, 1), 1)))
1122 record_address_regs (mode, XEXP (XEXP (x, 1), 1), 1, code, REG,
1130 /* Double the importance of an allocno that is incremented or
1131 decremented, since it would take two extra insns if it ends
1132 up in the wrong place. */
1133 record_address_regs (mode, XEXP (x, 0), 0, code, SCRATCH, 2 * scale);
1141 int k, regno, add_cost;
1142 cost_classes_t cost_classes_ptr;
1143 enum reg_class *cost_classes;
1144 move_table *move_in_cost;
1146 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
1151 ALLOCNO_BAD_SPILL_P (ira_curr_regno_allocno_map[regno]) = true;
1152 pp = COSTS (costs, COST_INDEX (regno));
1153 add_cost = (ira_memory_move_cost[Pmode][rclass][1] * scale) / 2;
1154 if (INT_MAX - add_cost < pp->mem_cost)
1155 pp->mem_cost = INT_MAX;
1157 pp->mem_cost += add_cost;
1158 cost_classes_ptr = regno_cost_classes[regno];
1159 cost_classes = cost_classes_ptr->classes;
1160 pp_costs = pp->cost;
1161 ira_init_register_move_cost_if_necessary (Pmode);
1162 move_in_cost = ira_may_move_in_cost[Pmode];
1163 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1165 i = cost_classes[k];
1166 add_cost = (move_in_cost[i][rclass] * scale) / 2;
1167 if (INT_MAX - add_cost < pp_costs[k])
1168 pp_costs[k] = INT_MAX;
1170 pp_costs[k] += add_cost;
1177 const char *fmt = GET_RTX_FORMAT (code);
1179 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1181 record_address_regs (mode, XEXP (x, i), context, code, SCRATCH,
1189 /* Calculate the costs of insn operands. */
1191 record_operand_costs (rtx insn, enum reg_class *pref)
1193 const char *constraints[MAX_RECOG_OPERANDS];
1194 enum machine_mode modes[MAX_RECOG_OPERANDS];
1197 for (i = 0; i < recog_data.n_operands; i++)
1199 constraints[i] = recog_data.constraints[i];
1200 modes[i] = recog_data.operand_mode[i];
1203 /* If we get here, we are set up to record the costs of all the
1204 operands for this insn. Start by initializing the costs. Then
1205 handle any address registers. Finally record the desired classes
1206 for any allocnos, doing it twice if some pair of operands are
1208 for (i = 0; i < recog_data.n_operands; i++)
1210 memcpy (op_costs[i], init_cost, struct_costs_size);
1212 if (GET_CODE (recog_data.operand[i]) == SUBREG)
1213 recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);
1215 if (MEM_P (recog_data.operand[i]))
1216 record_address_regs (GET_MODE (recog_data.operand[i]),
1217 XEXP (recog_data.operand[i], 0),
1218 0, MEM, SCRATCH, frequency * 2);
1219 else if (constraints[i][0] == 'p'
1220 || EXTRA_ADDRESS_CONSTRAINT (constraints[i][0],
1222 record_address_regs (VOIDmode, recog_data.operand[i], 0, ADDRESS,
1223 SCRATCH, frequency * 2);
1226 /* Check for commutative in a separate loop so everything will have
1227 been initialized. We must do this even if one operand is a
1228 constant--see addsi3 in m68k.md. */
1229 for (i = 0; i < (int) recog_data.n_operands - 1; i++)
1230 if (constraints[i][0] == '%')
1232 const char *xconstraints[MAX_RECOG_OPERANDS];
1235 /* Handle commutative operands by swapping the constraints.
1236 We assume the modes are the same. */
1237 for (j = 0; j < recog_data.n_operands; j++)
1238 xconstraints[j] = constraints[j];
1240 xconstraints[i] = constraints[i+1];
1241 xconstraints[i+1] = constraints[i];
1242 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1243 recog_data.operand, modes,
1244 xconstraints, insn, pref);
1246 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1247 recog_data.operand, modes,
1248 constraints, insn, pref);
1253 /* Process one insn INSN. Scan it and record each time it would save
1254 code to put a certain allocnos in a certain class. Return the last
1255 insn processed, so that the scan can be continued from there. */
1257 scan_one_insn (rtx insn)
1259 enum rtx_code pat_code;
1264 if (!NONDEBUG_INSN_P (insn))
1267 pat_code = GET_CODE (PATTERN (insn));
1268 if (pat_code == USE || pat_code == CLOBBER || pat_code == ASM_INPUT
1269 || pat_code == ADDR_VEC || pat_code == ADDR_DIFF_VEC)
1272 counted_mem = false;
1273 set = single_set (insn);
1274 extract_insn (insn);
1276 /* If this insn loads a parameter from its stack slot, then it
1277 represents a savings, rather than a cost, if the parameter is
1278 stored in memory. Record this fact.
1280 Similarly if we're loading other constants from memory (constant
1281 pool, TOC references, small data areas, etc) and this is the only
1282 assignment to the destination pseudo. */
1283 if (set != 0 && REG_P (SET_DEST (set)) && MEM_P (SET_SRC (set))
1284 && (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL_RTX
1285 && ((MEM_P (XEXP (note, 0)))
1286 || (CONSTANT_P (XEXP (note, 0))
1287 && targetm.legitimate_constant_p (GET_MODE (SET_DEST (set)),
1289 && REG_N_SETS (REGNO (SET_DEST (set))) == 1)))
1291 enum reg_class cl = GENERAL_REGS;
1292 rtx reg = SET_DEST (set);
1293 int num = COST_INDEX (REGNO (reg));
1295 COSTS (costs, num)->mem_cost
1296 -= ira_memory_move_cost[GET_MODE (reg)][cl][1] * frequency;
1297 record_address_regs (GET_MODE (SET_SRC (set)), XEXP (SET_SRC (set), 0),
1298 0, MEM, SCRATCH, frequency * 2);
1302 record_operand_costs (insn, pref);
1304 /* Now add the cost for each operand to the total costs for its
1306 for (i = 0; i < recog_data.n_operands; i++)
1307 if (REG_P (recog_data.operand[i])
1308 && REGNO (recog_data.operand[i]) >= FIRST_PSEUDO_REGISTER)
1310 int regno = REGNO (recog_data.operand[i]);
1311 struct costs *p = COSTS (costs, COST_INDEX (regno));
1312 struct costs *q = op_costs[i];
1313 int *p_costs = p->cost, *q_costs = q->cost;
1314 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1317 /* If the already accounted for the memory "cost" above, don't
1321 add_cost = q->mem_cost;
1322 if (add_cost > 0 && INT_MAX - add_cost < p->mem_cost)
1323 p->mem_cost = INT_MAX;
1325 p->mem_cost += add_cost;
1327 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1329 add_cost = q_costs[k];
1330 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1331 p_costs[k] = INT_MAX;
1333 p_costs[k] += add_cost;
1342 /* Print allocnos costs to file F. */
1344 print_allocno_costs (FILE *f)
1348 ira_allocno_iterator ai;
1350 ira_assert (allocno_p);
1352 FOR_EACH_ALLOCNO (a, ai)
1356 int regno = ALLOCNO_REGNO (a);
1357 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1358 enum reg_class *cost_classes = cost_classes_ptr->classes;
1360 i = ALLOCNO_NUM (a);
1361 fprintf (f, " a%d(r%d,", i, regno);
1362 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1363 fprintf (f, "b%d", bb->index);
1365 fprintf (f, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
1366 fprintf (f, ") costs:");
1367 for (k = 0; k < cost_classes_ptr->num; k++)
1369 rclass = cost_classes[k];
1370 if (contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (regno)]
1371 #ifdef CANNOT_CHANGE_MODE_CLASS
1372 && ! invalid_mode_change_p (regno, (enum reg_class) rclass)
1376 fprintf (f, " %s:%d", reg_class_names[rclass],
1377 COSTS (costs, i)->cost[k]);
1378 if (flag_ira_region == IRA_REGION_ALL
1379 || flag_ira_region == IRA_REGION_MIXED)
1380 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->cost[k]);
1383 fprintf (f, " MEM:%i", COSTS (costs, i)->mem_cost);
1384 if (flag_ira_region == IRA_REGION_ALL
1385 || flag_ira_region == IRA_REGION_MIXED)
1386 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->mem_cost);
1391 /* Print pseudo costs to file F. */
1393 print_pseudo_costs (FILE *f)
1397 cost_classes_t cost_classes_ptr;
1398 enum reg_class *cost_classes;
1400 ira_assert (! allocno_p);
1402 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1404 if (REG_N_REFS (regno) <= 0)
1406 cost_classes_ptr = regno_cost_classes[regno];
1407 cost_classes = cost_classes_ptr->classes;
1408 fprintf (f, " r%d costs:", regno);
1409 for (k = 0; k < cost_classes_ptr->num; k++)
1411 rclass = cost_classes[k];
1412 if (contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (regno)]
1413 #ifdef CANNOT_CHANGE_MODE_CLASS
1414 && ! invalid_mode_change_p (regno, (enum reg_class) rclass)
1417 fprintf (f, " %s:%d", reg_class_names[rclass],
1418 COSTS (costs, regno)->cost[k]);
1420 fprintf (f, " MEM:%i\n", COSTS (costs, regno)->mem_cost);
1424 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1427 process_bb_for_costs (basic_block bb)
1431 frequency = REG_FREQ_FROM_BB (bb);
1434 FOR_BB_INSNS (bb, insn)
1435 insn = scan_one_insn (insn);
1438 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1441 process_bb_node_for_costs (ira_loop_tree_node_t loop_tree_node)
1445 bb = loop_tree_node->bb;
1447 process_bb_for_costs (bb);
1450 /* Find costs of register classes and memory for allocnos or pseudos
1451 and their best costs. Set up preferred, alternative and allocno
1452 classes for pseudos. */
1454 find_costs_and_classes (FILE *dump_file)
1456 int i, k, start, max_cost_classes_num;
1459 enum reg_class *regno_best_class;
1463 = (enum reg_class *) ira_allocate (max_reg_num ()
1464 * sizeof (enum reg_class));
1465 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1466 regno_best_class[i] = NO_REGS;
1467 if (!resize_reg_info () && allocno_p
1468 && pseudo_classes_defined_p && flag_expensive_optimizations)
1471 ira_allocno_iterator ai;
1474 max_cost_classes_num = 1;
1475 FOR_EACH_ALLOCNO (a, ai)
1477 pref[ALLOCNO_NUM (a)] = reg_preferred_class (ALLOCNO_REGNO (a));
1478 setup_regno_cost_classes_by_aclass
1479 (ALLOCNO_REGNO (a), pref[ALLOCNO_NUM (a)]);
1480 max_cost_classes_num
1481 = MAX (max_cost_classes_num,
1482 regno_cost_classes[ALLOCNO_REGNO (a)]->num);
1489 max_cost_classes_num = ira_important_classes_num;
1490 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1491 if (regno_reg_rtx[i] != NULL_RTX)
1492 setup_regno_cost_classes_by_mode (i, PSEUDO_REGNO_MODE (i));
1494 setup_regno_cost_classes_by_aclass (i, ALL_REGS);
1498 /* Clear the flag for the next compiled function. */
1499 pseudo_classes_defined_p = false;
1500 /* Normally we scan the insns once and determine the best class to
1501 use for each allocno. However, if -fexpensive-optimizations are
1502 on, we do so twice, the second time using the tentative best
1503 classes to guide the selection. */
1504 for (pass = start; pass <= flag_expensive_optimizations; pass++)
1506 if ((!allocno_p || internal_flag_ira_verbose > 0) && dump_file)
1508 "\nPass %i for finding pseudo/allocno costs\n\n", pass);
1512 max_cost_classes_num = 1;
1513 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1515 setup_regno_cost_classes_by_aclass (i, regno_best_class[i]);
1516 max_cost_classes_num
1517 = MAX (max_cost_classes_num, regno_cost_classes[i]->num);
1522 = sizeof (struct costs) + sizeof (int) * (max_cost_classes_num - 1);
1523 /* Zero out our accumulation of the cost of each class for each
1525 memset (costs, 0, cost_elements_num * struct_costs_size);
1529 /* Scan the instructions and record each time it would save code
1530 to put a certain allocno in a certain class. */
1531 ira_traverse_loop_tree (true, ira_loop_tree_root,
1532 process_bb_node_for_costs, NULL);
1534 memcpy (total_allocno_costs, costs,
1535 max_struct_costs_size * ira_allocnos_num);
1542 process_bb_for_costs (bb);
1548 /* Now for each allocno look at how desirable each class is and
1549 find which class is preferred. */
1550 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1552 ira_allocno_t a, parent_a;
1553 int rclass, a_num, parent_a_num, add_cost;
1554 ira_loop_tree_node_t parent;
1555 int best_cost, allocno_cost;
1556 enum reg_class best, alt_class;
1557 cost_classes_t cost_classes_ptr = regno_cost_classes[i];
1558 enum reg_class *cost_classes = cost_classes_ptr->classes;
1559 int *i_costs = temp_costs->cost;
1561 int equiv_savings = regno_equiv_gains[i];
1565 if (regno_reg_rtx[i] == NULL_RTX)
1567 memcpy (temp_costs, COSTS (costs, i), struct_costs_size);
1568 i_mem_cost = temp_costs->mem_cost;
1572 if (ira_regno_allocno_map[i] == NULL)
1574 memset (temp_costs, 0, struct_costs_size);
1576 /* Find cost of all allocnos with the same regno. */
1577 for (a = ira_regno_allocno_map[i];
1579 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1581 int *a_costs, *p_costs;
1583 a_num = ALLOCNO_NUM (a);
1584 if ((flag_ira_region == IRA_REGION_ALL
1585 || flag_ira_region == IRA_REGION_MIXED)
1586 && (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1587 && (parent_a = parent->regno_allocno_map[i]) != NULL
1588 /* There are no caps yet. */
1589 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE
1590 (a)->border_allocnos,
1593 /* Propagate costs to upper levels in the region
1595 parent_a_num = ALLOCNO_NUM (parent_a);
1596 a_costs = COSTS (total_allocno_costs, a_num)->cost;
1597 p_costs = COSTS (total_allocno_costs, parent_a_num)->cost;
1598 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1600 add_cost = a_costs[k];
1601 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1602 p_costs[k] = INT_MAX;
1604 p_costs[k] += add_cost;
1606 add_cost = COSTS (total_allocno_costs, a_num)->mem_cost;
1608 && (INT_MAX - add_cost
1609 < COSTS (total_allocno_costs,
1610 parent_a_num)->mem_cost))
1611 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1614 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1618 a_costs = COSTS (costs, a_num)->cost;
1619 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1621 add_cost = a_costs[k];
1622 if (add_cost > 0 && INT_MAX - add_cost < i_costs[k])
1623 i_costs[k] = INT_MAX;
1625 i_costs[k] += add_cost;
1627 add_cost = COSTS (costs, a_num)->mem_cost;
1628 if (add_cost > 0 && INT_MAX - add_cost < i_mem_cost)
1629 i_mem_cost = INT_MAX;
1631 i_mem_cost += add_cost;
1634 if (equiv_savings < 0)
1635 i_mem_cost = -equiv_savings;
1636 else if (equiv_savings > 0)
1639 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1640 i_costs[k] += equiv_savings;
1643 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1645 alt_class = NO_REGS;
1646 /* Find best common class for all allocnos with the same
1648 for (k = 0; k < cost_classes_ptr->num; k++)
1650 rclass = cost_classes[k];
1651 /* Ignore classes that are too small or invalid for this
1653 if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)]
1654 #ifdef CANNOT_CHANGE_MODE_CLASS
1655 || invalid_mode_change_p (i, (enum reg_class) rclass)
1659 if (i_costs[k] < best_cost)
1661 best_cost = i_costs[k];
1662 best = (enum reg_class) rclass;
1664 else if (i_costs[k] == best_cost)
1665 best = ira_reg_class_subunion[best][rclass];
1666 if (pass == flag_expensive_optimizations
1667 && i_costs[k] < i_mem_cost
1668 && (reg_class_size[reg_class_subunion[alt_class][rclass]]
1669 > reg_class_size[alt_class]))
1670 alt_class = reg_class_subunion[alt_class][rclass];
1672 alt_class = ira_allocno_class_translate[alt_class];
1673 if (best_cost > i_mem_cost)
1674 regno_aclass[i] = NO_REGS;
1677 /* Make the common class the biggest class of best and
1680 = ira_reg_class_superunion[best][alt_class];
1681 ira_assert (regno_aclass[i] != NO_REGS
1682 && ira_reg_allocno_class_p[regno_aclass[i]]);
1684 if (pass == flag_expensive_optimizations)
1686 if (best_cost > i_mem_cost)
1687 best = alt_class = NO_REGS;
1688 else if (best == alt_class)
1689 alt_class = NO_REGS;
1690 setup_reg_classes (i, best, alt_class, regno_aclass[i]);
1691 if ((!allocno_p || internal_flag_ira_verbose > 2)
1692 && dump_file != NULL)
1694 " r%d: preferred %s, alternative %s, allocno %s\n",
1695 i, reg_class_names[best], reg_class_names[alt_class],
1696 reg_class_names[regno_aclass[i]]);
1698 regno_best_class[i] = best;
1701 pref[i] = best_cost > i_mem_cost ? NO_REGS : best;
1704 for (a = ira_regno_allocno_map[i];
1706 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1708 a_num = ALLOCNO_NUM (a);
1709 if (regno_aclass[i] == NO_REGS)
1713 int *total_a_costs = COSTS (total_allocno_costs, a_num)->cost;
1714 int *a_costs = COSTS (costs, a_num)->cost;
1716 /* Finding best class which is subset of the common
1718 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1719 allocno_cost = best_cost;
1721 for (k = 0; k < cost_classes_ptr->num; k++)
1723 rclass = cost_classes[k];
1724 if (! ira_class_subset_p[rclass][regno_aclass[i]])
1726 /* Ignore classes that are too small or invalid
1727 for this operand. */
1728 if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)]
1729 #ifdef CANNOT_CHANGE_MODE_CLASS
1730 || invalid_mode_change_p (i, (enum reg_class) rclass)
1734 else if (total_a_costs[k] < best_cost)
1736 best_cost = total_a_costs[k];
1737 allocno_cost = a_costs[k];
1738 best = (enum reg_class) rclass;
1740 else if (total_a_costs[k] == best_cost)
1742 best = ira_reg_class_subunion[best][rclass];
1743 allocno_cost = MAX (allocno_cost, a_costs[k]);
1746 ALLOCNO_CLASS_COST (a) = allocno_cost;
1748 if (internal_flag_ira_verbose > 2 && dump_file != NULL
1749 && (pass == 0 || pref[a_num] != best))
1751 fprintf (dump_file, " a%d (r%d,", a_num, i);
1752 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1753 fprintf (dump_file, "b%d", bb->index);
1755 fprintf (dump_file, "l%d",
1756 ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
1757 fprintf (dump_file, ") best %s, allocno %s\n",
1758 reg_class_names[best],
1759 reg_class_names[regno_aclass[i]]);
1765 if (internal_flag_ira_verbose > 4 && dump_file)
1768 print_allocno_costs (dump_file);
1770 print_pseudo_costs (dump_file);
1771 fprintf (dump_file,"\n");
1774 ira_free (regno_best_class);
1779 /* Process moves involving hard regs to modify allocno hard register
1780 costs. We can do this only after determining allocno class. If a
1781 hard register forms a register class, than moves with the hard
1782 register are already taken into account in class costs for the
1785 process_bb_node_for_hard_reg_moves (ira_loop_tree_node_t loop_tree_node)
1787 int i, freq, cost, src_regno, dst_regno, hard_regno;
1790 enum reg_class rclass, hard_reg_class;
1791 enum machine_mode mode;
1793 rtx insn, set, src, dst;
1795 bb = loop_tree_node->bb;
1798 freq = REG_FREQ_FROM_BB (bb);
1801 FOR_BB_INSNS (bb, insn)
1803 if (!NONDEBUG_INSN_P (insn))
1805 set = single_set (insn);
1806 if (set == NULL_RTX)
1808 dst = SET_DEST (set);
1809 src = SET_SRC (set);
1810 if (! REG_P (dst) || ! REG_P (src))
1812 dst_regno = REGNO (dst);
1813 src_regno = REGNO (src);
1814 if (dst_regno >= FIRST_PSEUDO_REGISTER
1815 && src_regno < FIRST_PSEUDO_REGISTER)
1817 hard_regno = src_regno;
1819 a = ira_curr_regno_allocno_map[dst_regno];
1821 else if (src_regno >= FIRST_PSEUDO_REGISTER
1822 && dst_regno < FIRST_PSEUDO_REGISTER)
1824 hard_regno = dst_regno;
1826 a = ira_curr_regno_allocno_map[src_regno];
1830 rclass = ALLOCNO_CLASS (a);
1831 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass], hard_regno))
1833 i = ira_class_hard_reg_index[rclass][hard_regno];
1836 mode = ALLOCNO_MODE (a);
1837 hard_reg_class = REGNO_REG_CLASS (hard_regno);
1838 ira_init_register_move_cost_if_necessary (mode);
1840 = (to_p ? ira_register_move_cost[mode][hard_reg_class][rclass]
1841 : ira_register_move_cost[mode][rclass][hard_reg_class]) * freq;
1842 ira_allocate_and_set_costs (&ALLOCNO_HARD_REG_COSTS (a), rclass,
1843 ALLOCNO_CLASS_COST (a));
1844 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
1846 ALLOCNO_HARD_REG_COSTS (a)[i] -= cost;
1847 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[i] -= cost;
1848 ALLOCNO_CLASS_COST (a) = MIN (ALLOCNO_CLASS_COST (a),
1849 ALLOCNO_HARD_REG_COSTS (a)[i]);
1853 /* After we find hard register and memory costs for allocnos, define
1854 its class and modify hard register cost because insns moving
1855 allocno to/from hard registers. */
1857 setup_allocno_class_and_costs (void)
1859 int i, j, n, regno, hard_regno, num;
1861 enum reg_class aclass, rclass;
1863 ira_allocno_iterator ai;
1864 cost_classes_t cost_classes_ptr;
1866 ira_assert (allocno_p);
1867 FOR_EACH_ALLOCNO (a, ai)
1869 i = ALLOCNO_NUM (a);
1870 regno = ALLOCNO_REGNO (a);
1871 aclass = regno_aclass[regno];
1872 cost_classes_ptr = regno_cost_classes[regno];
1873 ira_assert (pref[i] == NO_REGS || aclass != NO_REGS);
1874 ALLOCNO_MEMORY_COST (a) = COSTS (costs, i)->mem_cost;
1875 ira_set_allocno_class (a, aclass);
1876 if (aclass == NO_REGS)
1878 if (optimize && ALLOCNO_CLASS (a) != pref[i])
1880 n = ira_class_hard_regs_num[aclass];
1881 ALLOCNO_HARD_REG_COSTS (a)
1882 = reg_costs = ira_allocate_cost_vector (aclass);
1883 for (j = n - 1; j >= 0; j--)
1885 hard_regno = ira_class_hard_regs[aclass][j];
1886 if (TEST_HARD_REG_BIT (reg_class_contents[pref[i]], hard_regno))
1887 reg_costs[j] = ALLOCNO_CLASS_COST (a);
1890 rclass = REGNO_REG_CLASS (hard_regno);
1891 num = cost_classes_ptr->index[rclass];
1894 num = cost_classes_ptr->hard_regno_index[hard_regno];
1895 ira_assert (num >= 0);
1897 reg_costs[j] = COSTS (costs, i)->cost[num];
1903 ira_traverse_loop_tree (true, ira_loop_tree_root,
1904 process_bb_node_for_hard_reg_moves, NULL);
1909 /* Function called once during compiler work. */
1911 ira_init_costs_once (void)
1916 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
1919 this_op_costs[i] = NULL;
1924 /* Free allocated temporary cost vectors. */
1926 free_ira_costs (void)
1932 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
1935 free (this_op_costs[i]);
1936 op_costs[i] = this_op_costs[i] = NULL;
1942 /* This is called each time register related information is
1945 ira_init_costs (void)
1950 max_struct_costs_size
1951 = sizeof (struct costs) + sizeof (int) * (ira_important_classes_num - 1);
1952 /* Don't use ira_allocate because vectors live through several IRA
1954 init_cost = (struct costs *) xmalloc (max_struct_costs_size);
1955 init_cost->mem_cost = 1000000;
1956 for (i = 0; i < ira_important_classes_num; i++)
1957 init_cost->cost[i] = 1000000;
1958 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
1960 op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
1961 this_op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
1963 temp_costs = (struct costs *) xmalloc (max_struct_costs_size);
1966 /* Function called once at the end of compiler work. */
1968 ira_finish_costs_once (void)
1975 /* Common initialization function for ira_costs and
1976 ira_set_pseudo_classes. */
1980 init_subregs_of_mode ();
1981 costs = (struct costs *) ira_allocate (max_struct_costs_size
1982 * cost_elements_num);
1983 pref_buffer = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
1984 * cost_elements_num);
1985 regno_aclass = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
1987 regno_equiv_gains = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1988 memset (regno_equiv_gains, 0, sizeof (int) * max_reg_num ());
1991 /* Common finalization function for ira_costs and
1992 ira_set_pseudo_classes. */
1996 finish_subregs_of_mode ();
1997 ira_free (regno_equiv_gains);
1998 ira_free (regno_aclass);
1999 ira_free (pref_buffer);
2003 /* Entry function which defines register class, memory and hard
2004 register costs for each allocno. */
2009 cost_elements_num = ira_allocnos_num;
2011 total_allocno_costs = (struct costs *) ira_allocate (max_struct_costs_size
2012 * ira_allocnos_num);
2013 initiate_regno_cost_classes ();
2014 calculate_elim_costs_all_insns ();
2015 find_costs_and_classes (ira_dump_file);
2016 setup_allocno_class_and_costs ();
2017 finish_regno_cost_classes ();
2019 ira_free (total_allocno_costs);
2022 /* Entry function which defines classes for pseudos. */
2024 ira_set_pseudo_classes (FILE *dump_file)
2027 internal_flag_ira_verbose = flag_ira_verbose;
2028 cost_elements_num = max_reg_num ();
2030 initiate_regno_cost_classes ();
2031 find_costs_and_classes (dump_file);
2032 finish_regno_cost_classes ();
2033 pseudo_classes_defined_p = true;
2039 /* Change hard register costs for allocnos which lives through
2040 function calls. This is called only when we found all intersected
2041 calls during building allocno live ranges. */
2043 ira_tune_allocno_costs (void)
2046 int cost, min_cost, *reg_costs;
2047 enum reg_class aclass, rclass;
2048 enum machine_mode mode;
2050 ira_allocno_iterator ai;
2051 ira_allocno_object_iterator oi;
2055 FOR_EACH_ALLOCNO (a, ai)
2057 aclass = ALLOCNO_CLASS (a);
2058 if (aclass == NO_REGS)
2060 mode = ALLOCNO_MODE (a);
2061 n = ira_class_hard_regs_num[aclass];
2063 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2065 ira_allocate_and_set_costs
2066 (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2067 ALLOCNO_CLASS_COST (a));
2068 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2069 for (j = n - 1; j >= 0; j--)
2071 regno = ira_class_hard_regs[aclass][j];
2073 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2075 if (! ira_hard_reg_not_in_set_p (regno, mode,
2076 OBJECT_CONFLICT_HARD_REGS
2085 rclass = REGNO_REG_CLASS (regno);
2087 if (! ira_hard_reg_not_in_set_p (regno, mode, call_used_reg_set)
2088 || HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
2089 cost += (ALLOCNO_CALL_FREQ (a)
2090 * (ira_memory_move_cost[mode][rclass][0]
2091 + ira_memory_move_cost[mode][rclass][1]));
2092 #ifdef IRA_HARD_REGNO_ADD_COST_MULTIPLIER
2093 cost += ((ira_memory_move_cost[mode][rclass][0]
2094 + ira_memory_move_cost[mode][rclass][1])
2096 * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno) / 2);
2098 if (INT_MAX - cost < reg_costs[j])
2099 reg_costs[j] = INT_MAX;
2101 reg_costs[j] += cost;
2102 if (min_cost > reg_costs[j])
2103 min_cost = reg_costs[j];
2106 if (min_cost != INT_MAX)
2107 ALLOCNO_CLASS_COST (a) = min_cost;
2109 /* Some targets allow pseudos to be allocated to unaligned sequences
2110 of hard registers. However, selecting an unaligned sequence can
2111 unnecessarily restrict later allocations. So increase the cost of
2112 unaligned hard regs to encourage the use of aligned hard regs. */
2114 const int nregs = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2118 ira_allocate_and_set_costs
2119 (&ALLOCNO_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a));
2120 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2121 for (j = n - 1; j >= 0; j--)
2123 regno = ira_non_ordered_class_hard_regs[aclass][j];
2124 if ((regno % nregs) != 0)
2126 int index = ira_class_hard_reg_index[aclass][regno];
2127 ira_assert (index != -1);
2128 reg_costs[index] += ALLOCNO_FREQ (a);
2136 /* Add COST to the estimated gain for eliminating REGNO with its
2137 equivalence. If COST is zero, record that no such elimination is
2141 ira_adjust_equiv_reg_cost (unsigned regno, int cost)
2144 regno_equiv_gains[regno] = 0;
2146 regno_equiv_gains[regno] += cost;