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;
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[(int) rclass]
941 == ira_reg_class_max_nregs [(int) rclass][(int) 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)])
1372 fprintf (f, " %s:%d", reg_class_names[rclass],
1373 COSTS (costs, i)->cost[k]);
1374 if (flag_ira_region == IRA_REGION_ALL
1375 || flag_ira_region == IRA_REGION_MIXED)
1376 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->cost[k]);
1379 fprintf (f, " MEM:%i", COSTS (costs, i)->mem_cost);
1380 if (flag_ira_region == IRA_REGION_ALL
1381 || flag_ira_region == IRA_REGION_MIXED)
1382 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->mem_cost);
1387 /* Print pseudo costs to file F. */
1389 print_pseudo_costs (FILE *f)
1393 cost_classes_t cost_classes_ptr;
1394 enum reg_class *cost_classes;
1396 ira_assert (! allocno_p);
1398 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1400 if (REG_N_REFS (regno) <= 0)
1402 cost_classes_ptr = regno_cost_classes[regno];
1403 cost_classes = cost_classes_ptr->classes;
1404 fprintf (f, " r%d costs:", regno);
1405 for (k = 0; k < cost_classes_ptr->num; k++)
1407 rclass = cost_classes[k];
1408 if (contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (regno)])
1409 fprintf (f, " %s:%d", reg_class_names[rclass],
1410 COSTS (costs, regno)->cost[k]);
1412 fprintf (f, " MEM:%i\n", COSTS (costs, regno)->mem_cost);
1416 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1419 process_bb_for_costs (basic_block bb)
1423 frequency = REG_FREQ_FROM_BB (bb);
1426 FOR_BB_INSNS (bb, insn)
1427 insn = scan_one_insn (insn);
1430 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1433 process_bb_node_for_costs (ira_loop_tree_node_t loop_tree_node)
1437 bb = loop_tree_node->bb;
1439 process_bb_for_costs (bb);
1442 /* Find costs of register classes and memory for allocnos or pseudos
1443 and their best costs. Set up preferred, alternative and allocno
1444 classes for pseudos. */
1446 find_costs_and_classes (FILE *dump_file)
1448 int i, k, start, max_cost_classes_num;
1451 enum reg_class *regno_best_class;
1455 = (enum reg_class *) ira_allocate (max_reg_num ()
1456 * sizeof (enum reg_class));
1457 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1458 regno_best_class[i] = NO_REGS;
1459 if (!resize_reg_info () && allocno_p
1460 && pseudo_classes_defined_p && flag_expensive_optimizations)
1463 ira_allocno_iterator ai;
1466 max_cost_classes_num = 1;
1467 FOR_EACH_ALLOCNO (a, ai)
1469 pref[ALLOCNO_NUM (a)] = reg_preferred_class (ALLOCNO_REGNO (a));
1470 setup_regno_cost_classes_by_aclass
1471 (ALLOCNO_REGNO (a), pref[ALLOCNO_NUM (a)]);
1472 max_cost_classes_num
1473 = MAX (max_cost_classes_num,
1474 regno_cost_classes[ALLOCNO_REGNO (a)]->num);
1481 max_cost_classes_num = ira_important_classes_num;
1482 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1483 if (regno_reg_rtx[i] != NULL_RTX)
1484 setup_regno_cost_classes_by_mode (i, PSEUDO_REGNO_MODE (i));
1486 setup_regno_cost_classes_by_aclass (i, ALL_REGS);
1490 /* Clear the flag for the next compiled function. */
1491 pseudo_classes_defined_p = false;
1492 /* Normally we scan the insns once and determine the best class to
1493 use for each allocno. However, if -fexpensive-optimizations are
1494 on, we do so twice, the second time using the tentative best
1495 classes to guide the selection. */
1496 for (pass = start; pass <= flag_expensive_optimizations; pass++)
1498 if ((!allocno_p || internal_flag_ira_verbose > 0) && dump_file)
1500 "\nPass %i for finding pseudo/allocno costs\n\n", pass);
1504 max_cost_classes_num = 1;
1505 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1507 setup_regno_cost_classes_by_aclass (i, regno_best_class[i]);
1508 max_cost_classes_num
1509 = MAX (max_cost_classes_num, regno_cost_classes[i]->num);
1514 = sizeof (struct costs) + sizeof (int) * (max_cost_classes_num - 1);
1515 /* Zero out our accumulation of the cost of each class for each
1517 memset (costs, 0, cost_elements_num * struct_costs_size);
1521 /* Scan the instructions and record each time it would save code
1522 to put a certain allocno in a certain class. */
1523 ira_traverse_loop_tree (true, ira_loop_tree_root,
1524 process_bb_node_for_costs, NULL);
1526 memcpy (total_allocno_costs, costs,
1527 max_struct_costs_size * ira_allocnos_num);
1534 process_bb_for_costs (bb);
1540 /* Now for each allocno look at how desirable each class is and
1541 find which class is preferred. */
1542 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1544 ira_allocno_t a, parent_a;
1545 int rclass, a_num, parent_a_num, add_cost;
1546 ira_loop_tree_node_t parent;
1547 int best_cost, allocno_cost;
1548 enum reg_class best, alt_class;
1549 cost_classes_t cost_classes_ptr = regno_cost_classes[i];
1550 enum reg_class *cost_classes = cost_classes_ptr->classes;
1551 int *i_costs = temp_costs->cost;
1553 int equiv_savings = regno_equiv_gains[i];
1557 if (regno_reg_rtx[i] == NULL_RTX)
1559 memcpy (temp_costs, COSTS (costs, i), struct_costs_size);
1560 i_mem_cost = temp_costs->mem_cost;
1564 if (ira_regno_allocno_map[i] == NULL)
1566 memset (temp_costs, 0, struct_costs_size);
1568 /* Find cost of all allocnos with the same regno. */
1569 for (a = ira_regno_allocno_map[i];
1571 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1573 int *a_costs, *p_costs;
1575 a_num = ALLOCNO_NUM (a);
1576 if ((flag_ira_region == IRA_REGION_ALL
1577 || flag_ira_region == IRA_REGION_MIXED)
1578 && (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1579 && (parent_a = parent->regno_allocno_map[i]) != NULL
1580 /* There are no caps yet. */
1581 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE
1582 (a)->border_allocnos,
1585 /* Propagate costs to upper levels in the region
1587 parent_a_num = ALLOCNO_NUM (parent_a);
1588 a_costs = COSTS (total_allocno_costs, a_num)->cost;
1589 p_costs = COSTS (total_allocno_costs, parent_a_num)->cost;
1590 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1592 add_cost = a_costs[k];
1593 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1594 p_costs[k] = INT_MAX;
1596 p_costs[k] += add_cost;
1598 add_cost = COSTS (total_allocno_costs, a_num)->mem_cost;
1600 && (INT_MAX - add_cost
1601 < COSTS (total_allocno_costs,
1602 parent_a_num)->mem_cost))
1603 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1606 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1610 a_costs = COSTS (costs, a_num)->cost;
1611 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1613 add_cost = a_costs[k];
1614 if (add_cost > 0 && INT_MAX - add_cost < i_costs[k])
1615 i_costs[k] = INT_MAX;
1617 i_costs[k] += add_cost;
1619 add_cost = COSTS (costs, a_num)->mem_cost;
1620 if (add_cost > 0 && INT_MAX - add_cost < i_mem_cost)
1621 i_mem_cost = INT_MAX;
1623 i_mem_cost += add_cost;
1626 if (equiv_savings < 0)
1627 i_mem_cost = -equiv_savings;
1628 else if (equiv_savings > 0)
1631 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1632 i_costs[k] += equiv_savings;
1635 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1637 alt_class = NO_REGS;
1638 /* Find best common class for all allocnos with the same
1640 for (k = 0; k < cost_classes_ptr->num; k++)
1642 rclass = cost_classes[k];
1643 /* Ignore classes that are too small or invalid for this
1645 if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)])
1647 if (i_costs[k] < best_cost)
1649 best_cost = i_costs[k];
1650 best = (enum reg_class) rclass;
1652 else if (i_costs[k] == best_cost)
1653 best = ira_reg_class_subunion[best][rclass];
1654 if (pass == flag_expensive_optimizations
1655 && i_costs[k] < i_mem_cost
1656 && (reg_class_size[reg_class_subunion[alt_class][rclass]]
1657 > reg_class_size[alt_class]))
1658 alt_class = reg_class_subunion[alt_class][rclass];
1660 alt_class = ira_allocno_class_translate[alt_class];
1661 if (best_cost > i_mem_cost)
1662 regno_aclass[i] = NO_REGS;
1665 /* Make the common class the biggest class of best and
1668 = ira_reg_class_superunion[best][alt_class];
1669 ira_assert (regno_aclass[i] != NO_REGS
1670 && ira_reg_allocno_class_p[regno_aclass[i]]);
1672 if (pass == flag_expensive_optimizations)
1674 if (best_cost > i_mem_cost)
1675 best = alt_class = NO_REGS;
1676 else if (best == alt_class)
1677 alt_class = NO_REGS;
1678 setup_reg_classes (i, best, alt_class, regno_aclass[i]);
1679 if ((!allocno_p || internal_flag_ira_verbose > 2)
1680 && dump_file != NULL)
1682 " r%d: preferred %s, alternative %s, allocno %s\n",
1683 i, reg_class_names[best], reg_class_names[alt_class],
1684 reg_class_names[regno_aclass[i]]);
1686 regno_best_class[i] = best;
1689 pref[i] = best_cost > i_mem_cost ? NO_REGS : best;
1692 for (a = ira_regno_allocno_map[i];
1694 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1696 a_num = ALLOCNO_NUM (a);
1697 if (regno_aclass[i] == NO_REGS)
1701 int *total_a_costs = COSTS (total_allocno_costs, a_num)->cost;
1702 int *a_costs = COSTS (costs, a_num)->cost;
1704 /* Finding best class which is subset of the common
1706 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1707 allocno_cost = best_cost;
1709 for (k = 0; k < cost_classes_ptr->num; k++)
1711 rclass = cost_classes[k];
1712 if (! ira_class_subset_p[rclass][regno_aclass[i]])
1714 /* Ignore classes that are too small or invalid
1715 for this operand. */
1716 if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)])
1718 else if (total_a_costs[k] < best_cost)
1720 best_cost = total_a_costs[k];
1721 allocno_cost = a_costs[k];
1722 best = (enum reg_class) rclass;
1724 else if (total_a_costs[k] == best_cost)
1726 best = ira_reg_class_subunion[best][rclass];
1727 allocno_cost = MAX (allocno_cost, a_costs[k]);
1730 ALLOCNO_CLASS_COST (a) = allocno_cost;
1732 if (internal_flag_ira_verbose > 2 && dump_file != NULL
1733 && (pass == 0 || pref[a_num] != best))
1735 fprintf (dump_file, " a%d (r%d,", a_num, i);
1736 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1737 fprintf (dump_file, "b%d", bb->index);
1739 fprintf (dump_file, "l%d",
1740 ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
1741 fprintf (dump_file, ") best %s, allocno %s\n",
1742 reg_class_names[best],
1743 reg_class_names[regno_aclass[i]]);
1749 if (internal_flag_ira_verbose > 4 && dump_file)
1752 print_allocno_costs (dump_file);
1754 print_pseudo_costs (dump_file);
1755 fprintf (dump_file,"\n");
1758 ira_free (regno_best_class);
1763 /* Process moves involving hard regs to modify allocno hard register
1764 costs. We can do this only after determining allocno class. If a
1765 hard register forms a register class, than moves with the hard
1766 register are already taken into account in class costs for the
1769 process_bb_node_for_hard_reg_moves (ira_loop_tree_node_t loop_tree_node)
1771 int i, freq, cost, src_regno, dst_regno, hard_regno;
1774 enum reg_class rclass, hard_reg_class;
1775 enum machine_mode mode;
1777 rtx insn, set, src, dst;
1779 bb = loop_tree_node->bb;
1782 freq = REG_FREQ_FROM_BB (bb);
1785 FOR_BB_INSNS (bb, insn)
1787 if (!NONDEBUG_INSN_P (insn))
1789 set = single_set (insn);
1790 if (set == NULL_RTX)
1792 dst = SET_DEST (set);
1793 src = SET_SRC (set);
1794 if (! REG_P (dst) || ! REG_P (src))
1796 dst_regno = REGNO (dst);
1797 src_regno = REGNO (src);
1798 if (dst_regno >= FIRST_PSEUDO_REGISTER
1799 && src_regno < FIRST_PSEUDO_REGISTER)
1801 hard_regno = src_regno;
1803 a = ira_curr_regno_allocno_map[dst_regno];
1805 else if (src_regno >= FIRST_PSEUDO_REGISTER
1806 && dst_regno < FIRST_PSEUDO_REGISTER)
1808 hard_regno = dst_regno;
1810 a = ira_curr_regno_allocno_map[src_regno];
1814 rclass = ALLOCNO_CLASS (a);
1815 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass], hard_regno))
1817 i = ira_class_hard_reg_index[rclass][hard_regno];
1820 mode = ALLOCNO_MODE (a);
1821 hard_reg_class = REGNO_REG_CLASS (hard_regno);
1822 ira_init_register_move_cost_if_necessary (mode);
1824 = (to_p ? ira_register_move_cost[mode][hard_reg_class][rclass]
1825 : ira_register_move_cost[mode][rclass][hard_reg_class]) * freq;
1826 ira_allocate_and_set_costs (&ALLOCNO_HARD_REG_COSTS (a), rclass,
1827 ALLOCNO_CLASS_COST (a));
1828 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
1830 ALLOCNO_HARD_REG_COSTS (a)[i] -= cost;
1831 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[i] -= cost;
1832 ALLOCNO_CLASS_COST (a) = MIN (ALLOCNO_CLASS_COST (a),
1833 ALLOCNO_HARD_REG_COSTS (a)[i]);
1837 /* After we find hard register and memory costs for allocnos, define
1838 its class and modify hard register cost because insns moving
1839 allocno to/from hard registers. */
1841 setup_allocno_class_and_costs (void)
1843 int i, j, n, regno, hard_regno, num;
1845 enum reg_class aclass, rclass;
1847 ira_allocno_iterator ai;
1848 cost_classes_t cost_classes_ptr;
1850 ira_assert (allocno_p);
1851 FOR_EACH_ALLOCNO (a, ai)
1853 i = ALLOCNO_NUM (a);
1854 regno = ALLOCNO_REGNO (a);
1855 aclass = regno_aclass[regno];
1856 cost_classes_ptr = regno_cost_classes[regno];
1857 ira_assert (pref[i] == NO_REGS || aclass != NO_REGS);
1858 ALLOCNO_MEMORY_COST (a) = COSTS (costs, i)->mem_cost;
1859 ira_set_allocno_class (a, aclass);
1860 if (aclass == NO_REGS)
1862 if (optimize && ALLOCNO_CLASS (a) != pref[i])
1864 n = ira_class_hard_regs_num[aclass];
1865 ALLOCNO_HARD_REG_COSTS (a)
1866 = reg_costs = ira_allocate_cost_vector (aclass);
1867 for (j = n - 1; j >= 0; j--)
1869 hard_regno = ira_class_hard_regs[aclass][j];
1870 if (TEST_HARD_REG_BIT (reg_class_contents[pref[i]], hard_regno))
1871 reg_costs[j] = ALLOCNO_CLASS_COST (a);
1874 rclass = REGNO_REG_CLASS (hard_regno);
1875 num = cost_classes_ptr->index[rclass];
1878 num = cost_classes_ptr->hard_regno_index[hard_regno];
1879 ira_assert (num >= 0);
1881 reg_costs[j] = COSTS (costs, i)->cost[num];
1887 ira_traverse_loop_tree (true, ira_loop_tree_root,
1888 process_bb_node_for_hard_reg_moves, NULL);
1893 /* Function called once during compiler work. */
1895 ira_init_costs_once (void)
1900 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
1903 this_op_costs[i] = NULL;
1908 /* Free allocated temporary cost vectors. */
1910 free_ira_costs (void)
1916 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
1919 free (this_op_costs[i]);
1920 op_costs[i] = this_op_costs[i] = NULL;
1926 /* This is called each time register related information is
1929 ira_init_costs (void)
1934 max_struct_costs_size
1935 = sizeof (struct costs) + sizeof (int) * (ira_important_classes_num - 1);
1936 /* Don't use ira_allocate because vectors live through several IRA
1938 init_cost = (struct costs *) xmalloc (max_struct_costs_size);
1939 init_cost->mem_cost = 1000000;
1940 for (i = 0; i < ira_important_classes_num; i++)
1941 init_cost->cost[i] = 1000000;
1942 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
1944 op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
1945 this_op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
1947 temp_costs = (struct costs *) xmalloc (max_struct_costs_size);
1950 /* Function called once at the end of compiler work. */
1952 ira_finish_costs_once (void)
1959 /* Common initialization function for ira_costs and
1960 ira_set_pseudo_classes. */
1964 init_subregs_of_mode ();
1965 costs = (struct costs *) ira_allocate (max_struct_costs_size
1966 * cost_elements_num);
1967 pref_buffer = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
1968 * cost_elements_num);
1969 regno_aclass = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
1971 regno_equiv_gains = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1972 memset (regno_equiv_gains, 0, sizeof (int) * max_reg_num ());
1975 /* Common finalization function for ira_costs and
1976 ira_set_pseudo_classes. */
1980 finish_subregs_of_mode ();
1981 ira_free (regno_equiv_gains);
1982 ira_free (regno_aclass);
1983 ira_free (pref_buffer);
1987 /* Entry function which defines register class, memory and hard
1988 register costs for each allocno. */
1993 cost_elements_num = ira_allocnos_num;
1995 total_allocno_costs = (struct costs *) ira_allocate (max_struct_costs_size
1996 * ira_allocnos_num);
1997 initiate_regno_cost_classes ();
1998 calculate_elim_costs_all_insns ();
1999 find_costs_and_classes (ira_dump_file);
2000 setup_allocno_class_and_costs ();
2001 finish_regno_cost_classes ();
2003 ira_free (total_allocno_costs);
2006 /* Entry function which defines classes for pseudos. */
2008 ira_set_pseudo_classes (FILE *dump_file)
2011 internal_flag_ira_verbose = flag_ira_verbose;
2012 cost_elements_num = max_reg_num ();
2014 initiate_regno_cost_classes ();
2015 find_costs_and_classes (dump_file);
2016 finish_regno_cost_classes ();
2017 pseudo_classes_defined_p = true;
2023 /* Change hard register costs for allocnos which lives through
2024 function calls. This is called only when we found all intersected
2025 calls during building allocno live ranges. */
2027 ira_tune_allocno_costs (void)
2030 int cost, min_cost, *reg_costs;
2031 enum reg_class aclass, rclass;
2032 enum machine_mode mode;
2034 ira_allocno_iterator ai;
2035 ira_allocno_object_iterator oi;
2039 FOR_EACH_ALLOCNO (a, ai)
2041 aclass = ALLOCNO_CLASS (a);
2042 if (aclass == NO_REGS)
2044 mode = ALLOCNO_MODE (a);
2045 n = ira_class_hard_regs_num[aclass];
2047 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2049 ira_allocate_and_set_costs
2050 (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2051 ALLOCNO_CLASS_COST (a));
2052 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2053 for (j = n - 1; j >= 0; j--)
2055 regno = ira_class_hard_regs[aclass][j];
2057 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2059 if (! ira_hard_reg_not_in_set_p (regno, mode,
2060 OBJECT_CONFLICT_HARD_REGS
2069 rclass = REGNO_REG_CLASS (regno);
2071 if (! ira_hard_reg_not_in_set_p (regno, mode, call_used_reg_set)
2072 || HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
2073 cost += (ALLOCNO_CALL_FREQ (a)
2074 * (ira_memory_move_cost[mode][rclass][0]
2075 + ira_memory_move_cost[mode][rclass][1]));
2076 #ifdef IRA_HARD_REGNO_ADD_COST_MULTIPLIER
2077 cost += ((ira_memory_move_cost[mode][rclass][0]
2078 + ira_memory_move_cost[mode][rclass][1])
2080 * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno) / 2);
2082 if (INT_MAX - cost < reg_costs[j])
2083 reg_costs[j] = INT_MAX;
2085 reg_costs[j] += cost;
2086 if (min_cost > reg_costs[j])
2087 min_cost = reg_costs[j];
2090 if (min_cost != INT_MAX)
2091 ALLOCNO_CLASS_COST (a) = min_cost;
2093 /* Some targets allow pseudos to be allocated to unaligned sequences
2094 of hard registers. However, selecting an unaligned sequence can
2095 unnecessarily restrict later allocations. So increase the cost of
2096 unaligned hard regs to encourage the use of aligned hard regs. */
2098 const int nregs = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2102 ira_allocate_and_set_costs
2103 (&ALLOCNO_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a));
2104 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2105 for (j = n - 1; j >= 0; j--)
2107 regno = ira_non_ordered_class_hard_regs[aclass][j];
2108 if ((regno % nregs) != 0)
2110 int index = ira_class_hard_reg_index[aclass][regno];
2111 ira_assert (index != -1);
2112 reg_costs[index] += ALLOCNO_FREQ (a);
2120 /* Add COST to the estimated gain for eliminating REGNO with its
2121 equivalence. If COST is zero, record that no such elimination is
2125 ira_adjust_equiv_reg_cost (unsigned regno, int cost)
2128 regno_equiv_gains[regno] = 0;
2130 regno_equiv_gains[regno] += cost;