1 /* IRA hard register and memory cost calculation for allocnos or pseudos.
2 Copyright (C) 2006-2014 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
25 #include "hash-table.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 class. */
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 /* Helper for cost_classes hashing. */
137 struct cost_classes_hasher
139 typedef cost_classes value_type;
140 typedef cost_classes compare_type;
141 static inline hashval_t hash (const value_type *);
142 static inline bool equal (const value_type *, const compare_type *);
143 static inline void remove (value_type *);
146 /* Returns hash value for cost classes info HV. */
148 cost_classes_hasher::hash (const value_type *hv)
150 return iterative_hash (&hv->classes, sizeof (enum reg_class) * hv->num, 0);
153 /* Compares cost classes info HV1 and HV2. */
155 cost_classes_hasher::equal (const value_type *hv1, const compare_type *hv2)
157 return (hv1->num == hv2->num
158 && memcmp (hv1->classes, hv2->classes,
159 sizeof (enum reg_class) * hv1->num) == 0);
162 /* Delete cost classes info V from the hash table. */
164 cost_classes_hasher::remove (value_type *v)
169 /* Hash table of unique cost classes. */
170 static hash_table<cost_classes_hasher> *cost_classes_htab;
172 /* Map allocno class -> cost classes for pseudo of given allocno
174 static cost_classes_t cost_classes_aclass_cache[N_REG_CLASSES];
176 /* Map mode -> cost classes for pseudo of give mode. */
177 static cost_classes_t cost_classes_mode_cache[MAX_MACHINE_MODE];
179 /* Initialize info about the cost classes for each pseudo. */
181 initiate_regno_cost_classes (void)
183 int size = sizeof (cost_classes_t) * max_reg_num ();
185 regno_cost_classes = (cost_classes_t *) ira_allocate (size);
186 memset (regno_cost_classes, 0, size);
187 memset (cost_classes_aclass_cache, 0,
188 sizeof (cost_classes_t) * N_REG_CLASSES);
189 memset (cost_classes_mode_cache, 0,
190 sizeof (cost_classes_t) * MAX_MACHINE_MODE);
191 cost_classes_htab = new hash_table<cost_classes_hasher> (200);
194 /* Create new cost classes from cost classes FROM and set up members
195 index and hard_regno_index. Return the new classes. The function
196 implements some common code of two functions
197 setup_regno_cost_classes_by_aclass and
198 setup_regno_cost_classes_by_mode. */
199 static cost_classes_t
200 setup_cost_classes (cost_classes_t from)
202 cost_classes_t classes_ptr;
204 int i, j, hard_regno;
206 classes_ptr = (cost_classes_t) ira_allocate (sizeof (struct cost_classes));
207 classes_ptr->num = from->num;
208 for (i = 0; i < N_REG_CLASSES; i++)
209 classes_ptr->index[i] = -1;
210 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
211 classes_ptr->hard_regno_index[i] = -1;
212 for (i = 0; i < from->num; i++)
214 cl = classes_ptr->classes[i] = from->classes[i];
215 classes_ptr->index[cl] = i;
216 for (j = ira_class_hard_regs_num[cl] - 1; j >= 0; j--)
218 hard_regno = ira_class_hard_regs[cl][j];
219 if (classes_ptr->hard_regno_index[hard_regno] < 0)
220 classes_ptr->hard_regno_index[hard_regno] = i;
226 /* Setup cost classes for pseudo REGNO whose allocno class is ACLASS.
227 This function is used when we know an initial approximation of
228 allocno class of the pseudo already, e.g. on the second iteration
229 of class cost calculation or after class cost calculation in
230 register-pressure sensitive insn scheduling or register-pressure
231 sensitive loop-invariant motion. */
233 setup_regno_cost_classes_by_aclass (int regno, enum reg_class aclass)
235 static struct cost_classes classes;
236 cost_classes_t classes_ptr;
240 HARD_REG_SET temp, temp2;
243 if ((classes_ptr = cost_classes_aclass_cache[aclass]) == NULL)
245 COPY_HARD_REG_SET (temp, reg_class_contents[aclass]);
246 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
247 /* We exclude classes from consideration which are subsets of
248 ACLASS only if ACLASS is an uniform class. */
249 exclude_p = ira_uniform_class_p[aclass];
251 for (i = 0; i < ira_important_classes_num; i++)
253 cl = ira_important_classes[i];
256 /* Exclude non-uniform classes which are subsets of
258 COPY_HARD_REG_SET (temp2, reg_class_contents[cl]);
259 AND_COMPL_HARD_REG_SET (temp2, ira_no_alloc_regs);
260 if (hard_reg_set_subset_p (temp2, temp) && cl != aclass)
263 classes.classes[classes.num++] = cl;
265 slot = cost_classes_htab->find_slot (&classes, INSERT);
268 classes_ptr = setup_cost_classes (&classes);
271 classes_ptr = cost_classes_aclass_cache[aclass] = (cost_classes_t) *slot;
273 regno_cost_classes[regno] = classes_ptr;
276 /* Setup cost classes for pseudo REGNO with MODE. Usage of MODE can
277 decrease number of cost classes for the pseudo, if hard registers
278 of some important classes can not hold a value of MODE. So the
279 pseudo can not get hard register of some important classes and cost
280 calculation for such important classes is only wasting CPU
283 setup_regno_cost_classes_by_mode (int regno, enum machine_mode mode)
285 static struct cost_classes classes;
286 cost_classes_t classes_ptr;
292 if ((classes_ptr = cost_classes_mode_cache[mode]) == NULL)
295 for (i = 0; i < ira_important_classes_num; i++)
297 cl = ira_important_classes[i];
298 COPY_HARD_REG_SET (temp, ira_prohibited_class_mode_regs[cl][mode]);
299 IOR_HARD_REG_SET (temp, ira_no_alloc_regs);
300 if (hard_reg_set_subset_p (reg_class_contents[cl], temp))
302 classes.classes[classes.num++] = cl;
304 slot = cost_classes_htab->find_slot (&classes, INSERT);
307 classes_ptr = setup_cost_classes (&classes);
311 classes_ptr = (cost_classes_t) *slot;
312 cost_classes_mode_cache[mode] = (cost_classes_t) *slot;
314 regno_cost_classes[regno] = classes_ptr;
317 /* Finalize info about the cost classes for each pseudo. */
319 finish_regno_cost_classes (void)
321 ira_free (regno_cost_classes);
322 delete cost_classes_htab;
323 cost_classes_htab = NULL;
328 /* Compute the cost of loading X into (if TO_P is TRUE) or from (if
329 TO_P is FALSE) a register of class RCLASS in mode MODE. X must not
330 be a pseudo register. */
332 copy_cost (rtx x, enum machine_mode mode, reg_class_t rclass, bool to_p,
333 secondary_reload_info *prev_sri)
335 secondary_reload_info sri;
336 reg_class_t secondary_class = NO_REGS;
338 /* If X is a SCRATCH, there is actually nothing to move since we are
339 assuming optimal allocation. */
340 if (GET_CODE (x) == SCRATCH)
343 /* Get the class we will actually use for a reload. */
344 rclass = targetm.preferred_reload_class (x, rclass);
346 /* If we need a secondary reload for an intermediate, the cost is
347 that to load the input into the intermediate register, then to
349 sri.prev_sri = prev_sri;
351 secondary_class = targetm.secondary_reload (to_p, x, rclass, mode, &sri);
353 if (secondary_class != NO_REGS)
355 ira_init_register_move_cost_if_necessary (mode);
356 return (ira_register_move_cost[mode][(int) secondary_class][(int) rclass]
358 + copy_cost (x, mode, secondary_class, to_p, &sri));
361 /* For memory, use the memory move cost, for (hard) registers, use
362 the cost to move between the register classes, and use 2 for
363 everything else (constants). */
364 if (MEM_P (x) || rclass == NO_REGS)
365 return sri.extra_cost
366 + ira_memory_move_cost[mode][(int) rclass][to_p != 0];
369 reg_class_t x_class = REGNO_REG_CLASS (REGNO (x));
371 ira_init_register_move_cost_if_necessary (mode);
372 return (sri.extra_cost
373 + ira_register_move_cost[mode][(int) x_class][(int) rclass]);
376 /* If this is a constant, we may eventually want to call rtx_cost
378 return sri.extra_cost + COSTS_N_INSNS (1);
383 /* Record the cost of using memory or hard registers of various
384 classes for the operands in INSN.
386 N_ALTS is the number of alternatives.
387 N_OPS is the number of operands.
388 OPS is an array of the operands.
389 MODES are the modes of the operands, in case any are VOIDmode.
390 CONSTRAINTS are the constraints to use for the operands. This array
391 is modified by this procedure.
393 This procedure works alternative by alternative. For each
394 alternative we assume that we will be able to allocate all allocnos
395 to their ideal register class and calculate the cost of using that
396 alternative. Then we compute, for each operand that is a
397 pseudo-register, the cost of having the allocno allocated to each
398 register class and using it in that alternative. To this cost is
399 added the cost of the alternative.
401 The cost of each class for this insn is its lowest cost among all
404 record_reg_classes (int n_alts, int n_ops, rtx *ops,
405 enum machine_mode *modes, const char **constraints,
406 rtx_insn *insn, enum reg_class *pref)
410 int insn_allows_mem[MAX_RECOG_OPERANDS];
411 move_table *move_in_cost, *move_out_cost;
412 short (*mem_cost)[2];
414 for (i = 0; i < n_ops; i++)
415 insn_allows_mem[i] = 0;
417 /* Process each alternative, each time minimizing an operand's cost
418 with the cost for each operand in that alternative. */
419 alternative_mask preferred = get_preferred_alternatives (insn);
420 for (alt = 0; alt < n_alts; alt++)
422 enum reg_class classes[MAX_RECOG_OPERANDS];
423 int allows_mem[MAX_RECOG_OPERANDS];
424 enum reg_class rclass;
426 int alt_cost = 0, op_cost_add;
428 if (!TEST_BIT (preferred, alt))
430 for (i = 0; i < recog_data.n_operands; i++)
431 constraints[i] = skip_alternative (constraints[i]);
436 for (i = 0; i < n_ops; i++)
439 const char *p = constraints[i];
441 enum machine_mode mode = modes[i];
445 /* Initially show we know nothing about the register class. */
446 classes[i] = NO_REGS;
449 /* If this operand has no constraints at all, we can
450 conclude nothing about it since anything is valid. */
453 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
454 memset (this_op_costs[i], 0, struct_costs_size);
458 /* If this alternative is only relevant when this operand
459 matches a previous operand, we do different things
460 depending on whether this operand is a allocno-reg or not.
461 We must process any modifiers for the operand before we
462 can make this test. */
463 while (*p == '%' || *p == '=' || *p == '+' || *p == '&')
466 if (p[0] >= '0' && p[0] <= '0' + i && (p[1] == ',' || p[1] == 0))
468 /* Copy class and whether memory is allowed from the
469 matching alternative. Then perform any needed cost
470 computations and/or adjustments. */
472 classes[i] = classes[j];
473 allows_mem[i] = allows_mem[j];
475 insn_allows_mem[i] = 1;
477 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
479 /* If this matches the other operand, we have no
480 added cost and we win. */
481 if (rtx_equal_p (ops[j], op))
483 /* If we can put the other operand into a register,
484 add to the cost of this alternative the cost to
485 copy this operand to the register used for the
487 else if (classes[j] != NO_REGS)
489 alt_cost += copy_cost (op, mode, classes[j], 1, NULL);
493 else if (! REG_P (ops[j])
494 || REGNO (ops[j]) < FIRST_PSEUDO_REGISTER)
496 /* This op is an allocno but the one it matches is
499 /* If we can't put the other operand into a
500 register, this alternative can't be used. */
502 if (classes[j] == NO_REGS)
504 /* Otherwise, add to the cost of this alternative
505 the cost to copy the other operand to the hard
506 register used for this operand. */
508 alt_cost += copy_cost (ops[j], mode, classes[j], 1, NULL);
512 /* The costs of this operand are not the same as the
513 other operand since move costs are not symmetric.
514 Moreover, if we cannot tie them, this alternative
515 needs to do a copy, which is one insn. */
516 struct costs *pp = this_op_costs[i];
517 int *pp_costs = pp->cost;
518 cost_classes_t cost_classes_ptr
519 = regno_cost_classes[REGNO (op)];
520 enum reg_class *cost_classes = cost_classes_ptr->classes;
521 bool in_p = recog_data.operand_type[i] != OP_OUT;
522 bool out_p = recog_data.operand_type[i] != OP_IN;
523 enum reg_class op_class = classes[i];
525 ira_init_register_move_cost_if_necessary (mode);
529 if (op_class == NO_REGS)
531 mem_cost = ira_memory_move_cost[mode];
532 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
534 rclass = cost_classes[k];
535 pp_costs[k] = mem_cost[rclass][0] * frequency;
540 move_out_cost = ira_may_move_out_cost[mode];
541 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
543 rclass = cost_classes[k];
545 = move_out_cost[op_class][rclass] * frequency;
552 if (op_class == NO_REGS)
554 mem_cost = ira_memory_move_cost[mode];
555 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
557 rclass = cost_classes[k];
558 pp_costs[k] = mem_cost[rclass][1] * frequency;
563 move_in_cost = ira_may_move_in_cost[mode];
564 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
566 rclass = cost_classes[k];
568 = move_in_cost[rclass][op_class] * frequency;
574 if (op_class == NO_REGS)
576 mem_cost = ira_memory_move_cost[mode];
577 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
579 rclass = cost_classes[k];
580 pp_costs[k] = ((mem_cost[rclass][0]
581 + mem_cost[rclass][1])
587 move_in_cost = ira_may_move_in_cost[mode];
588 move_out_cost = ira_may_move_out_cost[mode];
589 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
591 rclass = cost_classes[k];
592 pp_costs[k] = ((move_in_cost[rclass][op_class]
593 + move_out_cost[op_class][rclass])
599 /* If the alternative actually allows memory, make
600 things a bit cheaper since we won't need an extra
603 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
604 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
605 - allows_mem[i]) * frequency;
607 /* If we have assigned a class to this allocno in
608 our first pass, add a cost to this alternative
609 corresponding to what we would add if this
610 allocno were not in the appropriate class. */
613 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
615 if (pref_class == NO_REGS)
618 ? ira_memory_move_cost[mode][op_class][0] : 0)
620 ? ira_memory_move_cost[mode][op_class][1]
622 else if (ira_reg_class_intersect
623 [pref_class][op_class] == NO_REGS)
625 += ira_register_move_cost[mode][pref_class][op_class];
627 if (REGNO (ops[i]) != REGNO (ops[j])
628 && ! find_reg_note (insn, REG_DEAD, op))
631 /* This is in place of ordinary cost computation for
632 this operand, so skip to the end of the
633 alternative (should be just one character). */
634 while (*p && *p++ != ',')
642 /* Scan all the constraint letters. See if the operand
643 matches any of the constraints. Collect the valid
644 register classes and see if this operand accepts
651 /* Ignore the next letter for this pass. */
662 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))))
664 insn_allows_mem[i] = allows_mem[i] = 1;
665 classes[i] = ira_reg_class_subunion[classes[i]][GENERAL_REGS];
669 enum constraint_num cn = lookup_constraint (p);
671 switch (get_constraint_type (cn))
674 cl = reg_class_for_constraint (cn);
676 classes[i] = ira_reg_class_subunion[classes[i]][cl];
681 && insn_const_int_ok_for_constraint (INTVAL (op), cn))
686 /* Every MEM can be reloaded to fit. */
687 insn_allows_mem[i] = allows_mem[i] = 1;
693 /* Every address can be reloaded to fit. */
695 if (address_operand (op, GET_MODE (op))
696 || constraint_satisfied_p (op, cn))
698 /* We know this operand is an address, so we
699 want it to be allocated to a hard register
700 that can be the base of an address,
701 i.e. BASE_REG_CLASS. */
703 = ira_reg_class_subunion[classes[i]]
704 [base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
709 if (constraint_satisfied_p (op, cn))
715 p += CONSTRAINT_LEN (c, p);
722 /* How we account for this operand now depends on whether it
723 is a pseudo register or not. If it is, we first check if
724 any register classes are valid. If not, we ignore this
725 alternative, since we want to assume that all allocnos get
726 allocated for register preferencing. If some register
727 class is valid, compute the costs of moving the allocno
729 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
731 if (classes[i] == NO_REGS && ! allows_mem[i])
733 /* We must always fail if the operand is a REG, but
734 we did not find a suitable class and memory is
737 Otherwise we may perform an uninitialized read
738 from this_op_costs after the `continue' statement
744 unsigned int regno = REGNO (op);
745 struct costs *pp = this_op_costs[i];
746 int *pp_costs = pp->cost;
747 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
748 enum reg_class *cost_classes = cost_classes_ptr->classes;
749 bool in_p = recog_data.operand_type[i] != OP_OUT;
750 bool out_p = recog_data.operand_type[i] != OP_IN;
751 enum reg_class op_class = classes[i];
753 ira_init_register_move_cost_if_necessary (mode);
757 if (op_class == NO_REGS)
759 mem_cost = ira_memory_move_cost[mode];
760 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
762 rclass = cost_classes[k];
763 pp_costs[k] = mem_cost[rclass][0] * frequency;
768 move_out_cost = ira_may_move_out_cost[mode];
769 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
771 rclass = cost_classes[k];
773 = move_out_cost[op_class][rclass] * frequency;
780 if (op_class == NO_REGS)
782 mem_cost = ira_memory_move_cost[mode];
783 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
785 rclass = cost_classes[k];
786 pp_costs[k] = mem_cost[rclass][1] * 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;
802 if (op_class == NO_REGS)
804 mem_cost = ira_memory_move_cost[mode];
805 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
807 rclass = cost_classes[k];
808 pp_costs[k] = ((mem_cost[rclass][0]
809 + mem_cost[rclass][1])
815 move_in_cost = ira_may_move_in_cost[mode];
816 move_out_cost = ira_may_move_out_cost[mode];
817 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
819 rclass = cost_classes[k];
820 pp_costs[k] = ((move_in_cost[rclass][op_class]
821 + move_out_cost[op_class][rclass])
827 if (op_class == NO_REGS)
828 /* Although we don't need insn to reload from
829 memory, still accessing memory is usually more
830 expensive than a register. */
831 pp->mem_cost = frequency;
833 /* If the alternative actually allows memory, make
834 things a bit cheaper since we won't need an
835 extra insn to load it. */
837 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
838 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
839 - allows_mem[i]) * frequency;
840 /* If we have assigned a class to this allocno in
841 our first pass, add a cost to this alternative
842 corresponding to what we would add if this
843 allocno were not in the appropriate class. */
846 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
848 if (pref_class == NO_REGS)
850 if (op_class != NO_REGS)
853 ? ira_memory_move_cost[mode][op_class][0]
856 ? ira_memory_move_cost[mode][op_class][1]
859 else if (op_class == NO_REGS)
862 ? ira_memory_move_cost[mode][pref_class][1]
865 ? ira_memory_move_cost[mode][pref_class][0]
867 else if (ira_reg_class_intersect[pref_class][op_class]
869 alt_cost += (ira_register_move_cost
870 [mode][pref_class][op_class]);
875 /* Otherwise, if this alternative wins, either because we
876 have already determined that or if we have a hard
877 register of the proper class, there is no cost for this
879 else if (win || (REG_P (op)
880 && reg_fits_class_p (op, classes[i],
884 /* If registers are valid, the cost of this alternative
885 includes copying the object to and/or from a
887 else if (classes[i] != NO_REGS)
889 if (recog_data.operand_type[i] != OP_OUT)
890 alt_cost += copy_cost (op, mode, classes[i], 1, NULL);
892 if (recog_data.operand_type[i] != OP_IN)
893 alt_cost += copy_cost (op, mode, classes[i], 0, NULL);
895 /* The only other way this alternative can be used is if
896 this is a constant that could be placed into memory. */
897 else if (CONSTANT_P (op) && (allows_addr || allows_mem[i]))
898 alt_cost += ira_memory_move_cost[mode][classes[i]][1];
906 op_cost_add = alt_cost * frequency;
907 /* Finally, update the costs with the information we've
908 calculated about this alternative. */
909 for (i = 0; i < n_ops; i++)
910 if (REG_P (ops[i]) && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
912 struct costs *pp = op_costs[i], *qq = this_op_costs[i];
913 int *pp_costs = pp->cost, *qq_costs = qq->cost;
914 int scale = 1 + (recog_data.operand_type[i] == OP_INOUT);
915 cost_classes_t cost_classes_ptr
916 = regno_cost_classes[REGNO (ops[i])];
918 pp->mem_cost = MIN (pp->mem_cost,
919 (qq->mem_cost + op_cost_add) * scale);
921 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
923 = MIN (pp_costs[k], (qq_costs[k] + op_cost_add) * scale);
928 for (i = 0; i < n_ops; i++)
933 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
935 a = ira_curr_regno_allocno_map [REGNO (op)];
936 if (! ALLOCNO_BAD_SPILL_P (a) && insn_allows_mem[i] == 0)
937 ALLOCNO_BAD_SPILL_P (a) = true;
944 /* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudo registers. */
946 ok_for_index_p_nonstrict (rtx reg)
948 unsigned regno = REGNO (reg);
950 return regno >= FIRST_PSEUDO_REGISTER || REGNO_OK_FOR_INDEX_P (regno);
953 /* A version of regno_ok_for_base_p for use here, when all
954 pseudo-registers should count as OK. Arguments as for
955 regno_ok_for_base_p. */
957 ok_for_base_p_nonstrict (rtx reg, enum machine_mode mode, addr_space_t as,
958 enum rtx_code outer_code, enum rtx_code index_code)
960 unsigned regno = REGNO (reg);
962 if (regno >= FIRST_PSEUDO_REGISTER)
964 return ok_for_base_p_1 (regno, mode, as, outer_code, index_code);
967 /* Record the pseudo registers we must reload into hard registers in a
968 subexpression of a memory address, X.
970 If CONTEXT is 0, we are looking at the base part of an address,
971 otherwise we are looking at the index part.
973 MODE and AS are the mode and address space of the memory reference;
974 OUTER_CODE and INDEX_CODE give the context that the rtx appears in.
975 These four arguments are passed down to base_reg_class.
977 SCALE is twice the amount to multiply the cost by (it is twice so
978 we can represent half-cost adjustments). */
980 record_address_regs (enum machine_mode mode, addr_space_t as, rtx x,
981 int context, enum rtx_code outer_code,
982 enum rtx_code index_code, int scale)
984 enum rtx_code code = GET_CODE (x);
985 enum reg_class rclass;
988 rclass = INDEX_REG_CLASS;
990 rclass = base_reg_class (mode, as, outer_code, index_code);
1003 /* When we have an address that is a sum, we must determine
1004 whether registers are "base" or "index" regs. If there is a
1005 sum of two registers, we must choose one to be the "base".
1006 Luckily, we can use the REG_POINTER to make a good choice
1007 most of the time. We only need to do this on machines that
1008 can have two registers in an address and where the base and
1009 index register classes are different.
1011 ??? This code used to set REGNO_POINTER_FLAG in some cases,
1012 but that seems bogus since it should only be set when we are
1013 sure the register is being used as a pointer. */
1015 rtx arg0 = XEXP (x, 0);
1016 rtx arg1 = XEXP (x, 1);
1017 enum rtx_code code0 = GET_CODE (arg0);
1018 enum rtx_code code1 = GET_CODE (arg1);
1020 /* Look inside subregs. */
1021 if (code0 == SUBREG)
1022 arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
1023 if (code1 == SUBREG)
1024 arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
1026 /* If this machine only allows one register per address, it
1027 must be in the first operand. */
1028 if (MAX_REGS_PER_ADDRESS == 1)
1029 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale);
1031 /* If index and base registers are the same on this machine,
1032 just record registers in any non-constant operands. We
1033 assume here, as well as in the tests below, that all
1034 addresses are in canonical form. */
1035 else if (INDEX_REG_CLASS
1036 == base_reg_class (VOIDmode, as, PLUS, SCRATCH))
1038 record_address_regs (mode, as, arg0, context, PLUS, code1, scale);
1039 if (! CONSTANT_P (arg1))
1040 record_address_regs (mode, as, arg1, context, PLUS, code0, scale);
1043 /* If the second operand is a constant integer, it doesn't
1044 change what class the first operand must be. */
1045 else if (CONST_SCALAR_INT_P (arg1))
1046 record_address_regs (mode, as, arg0, context, PLUS, code1, scale);
1047 /* If the second operand is a symbolic constant, the first
1048 operand must be an index register. */
1049 else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF)
1050 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale);
1051 /* If both operands are registers but one is already a hard
1052 register of index or reg-base class, give the other the
1053 class that the hard register is not. */
1054 else if (code0 == REG && code1 == REG
1055 && REGNO (arg0) < FIRST_PSEUDO_REGISTER
1056 && (ok_for_base_p_nonstrict (arg0, mode, as, PLUS, REG)
1057 || ok_for_index_p_nonstrict (arg0)))
1058 record_address_regs (mode, as, arg1,
1059 ok_for_base_p_nonstrict (arg0, mode, as,
1062 else if (code0 == REG && code1 == REG
1063 && REGNO (arg1) < FIRST_PSEUDO_REGISTER
1064 && (ok_for_base_p_nonstrict (arg1, mode, as, PLUS, REG)
1065 || ok_for_index_p_nonstrict (arg1)))
1066 record_address_regs (mode, as, arg0,
1067 ok_for_base_p_nonstrict (arg1, mode, as,
1070 /* If one operand is known to be a pointer, it must be the
1071 base with the other operand the index. Likewise if the
1072 other operand is a MULT. */
1073 else if ((code0 == REG && REG_POINTER (arg0)) || code1 == MULT)
1075 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale);
1076 record_address_regs (mode, as, arg1, 1, PLUS, code0, scale);
1078 else if ((code1 == REG && REG_POINTER (arg1)) || code0 == MULT)
1080 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale);
1081 record_address_regs (mode, as, arg1, 0, PLUS, code0, scale);
1083 /* Otherwise, count equal chances that each might be a base or
1084 index register. This case should be rare. */
1087 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale / 2);
1088 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale / 2);
1089 record_address_regs (mode, as, arg1, 0, PLUS, code0, scale / 2);
1090 record_address_regs (mode, as, arg1, 1, PLUS, code0, scale / 2);
1095 /* Double the importance of an allocno that is incremented or
1096 decremented, since it would take two extra insns if it ends
1097 up in the wrong place. */
1100 record_address_regs (mode, as, XEXP (x, 0), 0, code,
1101 GET_CODE (XEXP (XEXP (x, 1), 1)), 2 * scale);
1102 if (REG_P (XEXP (XEXP (x, 1), 1)))
1103 record_address_regs (mode, as, XEXP (XEXP (x, 1), 1), 1, code, REG,
1111 /* Double the importance of an allocno that is incremented or
1112 decremented, since it would take two extra insns if it ends
1113 up in the wrong place. */
1114 record_address_regs (mode, as, XEXP (x, 0), 0, code, SCRATCH, 2 * scale);
1122 int k, regno, add_cost;
1123 cost_classes_t cost_classes_ptr;
1124 enum reg_class *cost_classes;
1125 move_table *move_in_cost;
1127 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
1132 ALLOCNO_BAD_SPILL_P (ira_curr_regno_allocno_map[regno]) = true;
1133 pp = COSTS (costs, COST_INDEX (regno));
1134 add_cost = (ira_memory_move_cost[Pmode][rclass][1] * scale) / 2;
1135 if (INT_MAX - add_cost < pp->mem_cost)
1136 pp->mem_cost = INT_MAX;
1138 pp->mem_cost += add_cost;
1139 cost_classes_ptr = regno_cost_classes[regno];
1140 cost_classes = cost_classes_ptr->classes;
1141 pp_costs = pp->cost;
1142 ira_init_register_move_cost_if_necessary (Pmode);
1143 move_in_cost = ira_may_move_in_cost[Pmode];
1144 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1146 i = cost_classes[k];
1147 add_cost = (move_in_cost[i][rclass] * scale) / 2;
1148 if (INT_MAX - add_cost < pp_costs[k])
1149 pp_costs[k] = INT_MAX;
1151 pp_costs[k] += add_cost;
1158 const char *fmt = GET_RTX_FORMAT (code);
1160 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1162 record_address_regs (mode, as, XEXP (x, i), context, code, SCRATCH,
1170 /* Calculate the costs of insn operands. */
1172 record_operand_costs (rtx_insn *insn, enum reg_class *pref)
1174 const char *constraints[MAX_RECOG_OPERANDS];
1175 enum machine_mode modes[MAX_RECOG_OPERANDS];
1176 rtx ops[MAX_RECOG_OPERANDS];
1180 for (i = 0; i < recog_data.n_operands; i++)
1182 constraints[i] = recog_data.constraints[i];
1183 modes[i] = recog_data.operand_mode[i];
1186 /* If we get here, we are set up to record the costs of all the
1187 operands for this insn. Start by initializing the costs. Then
1188 handle any address registers. Finally record the desired classes
1189 for any allocnos, doing it twice if some pair of operands are
1191 for (i = 0; i < recog_data.n_operands; i++)
1193 memcpy (op_costs[i], init_cost, struct_costs_size);
1195 ops[i] = recog_data.operand[i];
1196 if (GET_CODE (recog_data.operand[i]) == SUBREG)
1197 recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);
1199 if (MEM_P (recog_data.operand[i]))
1200 record_address_regs (GET_MODE (recog_data.operand[i]),
1201 MEM_ADDR_SPACE (recog_data.operand[i]),
1202 XEXP (recog_data.operand[i], 0),
1203 0, MEM, SCRATCH, frequency * 2);
1204 else if (constraints[i][0] == 'p'
1205 || (insn_extra_address_constraint
1206 (lookup_constraint (constraints[i]))))
1207 record_address_regs (VOIDmode, ADDR_SPACE_GENERIC,
1208 recog_data.operand[i], 0, ADDRESS, SCRATCH,
1212 /* Check for commutative in a separate loop so everything will have
1213 been initialized. We must do this even if one operand is a
1214 constant--see addsi3 in m68k.md. */
1215 for (i = 0; i < (int) recog_data.n_operands - 1; i++)
1216 if (constraints[i][0] == '%')
1218 const char *xconstraints[MAX_RECOG_OPERANDS];
1221 /* Handle commutative operands by swapping the constraints.
1222 We assume the modes are the same. */
1223 for (j = 0; j < recog_data.n_operands; j++)
1224 xconstraints[j] = constraints[j];
1226 xconstraints[i] = constraints[i+1];
1227 xconstraints[i+1] = constraints[i];
1228 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1229 recog_data.operand, modes,
1230 xconstraints, insn, pref);
1232 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1233 recog_data.operand, modes,
1234 constraints, insn, pref);
1236 /* If this insn is a single set copying operand 1 to operand 0 and
1237 one operand is an allocno with the other a hard reg or an allocno
1238 that prefers a hard register that is in its own register class
1239 then we may want to adjust the cost of that register class to -1.
1241 Avoid the adjustment if the source does not die to avoid
1242 stressing of register allocator by preferencing two colliding
1243 registers into single class.
1245 Also avoid the adjustment if a copy between hard registers of the
1246 class is expensive (ten times the cost of a default copy is
1247 considered arbitrarily expensive). This avoids losing when the
1248 preferred class is very expensive as the source of a copy
1250 if ((set = single_set (insn)) != NULL_RTX
1251 /* In rare cases the single set insn might have less 2 operands
1252 as the source can be a fixed special reg. */
1253 && recog_data.n_operands > 1
1254 && ops[0] == SET_DEST (set) && ops[1] == SET_SRC (set))
1256 int regno, other_regno;
1257 rtx dest = SET_DEST (set);
1258 rtx src = SET_SRC (set);
1260 dest = SET_DEST (set);
1261 src = SET_SRC (set);
1262 if (GET_CODE (dest) == SUBREG
1263 && (GET_MODE_SIZE (GET_MODE (dest))
1264 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))))
1265 dest = SUBREG_REG (dest);
1266 if (GET_CODE (src) == SUBREG
1267 && (GET_MODE_SIZE (GET_MODE (src))
1268 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
1269 src = SUBREG_REG (src);
1270 if (REG_P (src) && REG_P (dest)
1271 && find_regno_note (insn, REG_DEAD, REGNO (src))
1272 && (((regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
1273 && (other_regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER)
1274 || ((regno = REGNO (dest)) >= FIRST_PSEUDO_REGISTER
1275 && (other_regno = REGNO (src)) < FIRST_PSEUDO_REGISTER)))
1277 enum machine_mode mode = GET_MODE (src);
1278 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1279 enum reg_class *cost_classes = cost_classes_ptr->classes;
1283 i = regno == (int) REGNO (src) ? 1 : 0;
1284 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1286 rclass = cost_classes[k];
1287 if (TEST_HARD_REG_BIT (reg_class_contents[rclass], other_regno)
1288 && (reg_class_size[(int) rclass]
1289 == ira_reg_class_max_nregs [(int) rclass][(int) mode]))
1291 if (reg_class_size[rclass] == 1)
1292 op_costs[i]->cost[k] = -frequency;
1296 nr < hard_regno_nregs[other_regno][mode];
1298 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass],
1302 if (nr == hard_regno_nregs[other_regno][mode])
1303 op_costs[i]->cost[k] = -frequency;
1313 /* Process one insn INSN. Scan it and record each time it would save
1314 code to put a certain allocnos in a certain class. Return the last
1315 insn processed, so that the scan can be continued from there. */
1317 scan_one_insn (rtx_insn *insn)
1319 enum rtx_code pat_code;
1324 if (!NONDEBUG_INSN_P (insn))
1327 pat_code = GET_CODE (PATTERN (insn));
1328 if (pat_code == USE || pat_code == CLOBBER || pat_code == ASM_INPUT)
1331 counted_mem = false;
1332 set = single_set (insn);
1333 extract_insn (insn);
1335 /* If this insn loads a parameter from its stack slot, then it
1336 represents a savings, rather than a cost, if the parameter is
1337 stored in memory. Record this fact.
1339 Similarly if we're loading other constants from memory (constant
1340 pool, TOC references, small data areas, etc) and this is the only
1341 assignment to the destination pseudo.
1343 Don't do this if SET_SRC (set) isn't a general operand, if it is
1344 a memory requiring special instructions to load it, decreasing
1345 mem_cost might result in it being loaded using the specialized
1346 instruction into a register, then stored into stack and loaded
1347 again from the stack. See PR52208.
1349 Don't do this if SET_SRC (set) has side effect. See PR56124. */
1350 if (set != 0 && REG_P (SET_DEST (set)) && MEM_P (SET_SRC (set))
1351 && (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL_RTX
1352 && ((MEM_P (XEXP (note, 0))
1353 && !side_effects_p (SET_SRC (set)))
1354 || (CONSTANT_P (XEXP (note, 0))
1355 && targetm.legitimate_constant_p (GET_MODE (SET_DEST (set)),
1357 && REG_N_SETS (REGNO (SET_DEST (set))) == 1))
1358 && general_operand (SET_SRC (set), GET_MODE (SET_SRC (set))))
1360 enum reg_class cl = GENERAL_REGS;
1361 rtx reg = SET_DEST (set);
1362 int num = COST_INDEX (REGNO (reg));
1364 COSTS (costs, num)->mem_cost
1365 -= ira_memory_move_cost[GET_MODE (reg)][cl][1] * frequency;
1366 record_address_regs (GET_MODE (SET_SRC (set)),
1367 MEM_ADDR_SPACE (SET_SRC (set)),
1368 XEXP (SET_SRC (set), 0), 0, MEM, SCRATCH,
1373 record_operand_costs (insn, pref);
1375 /* Now add the cost for each operand to the total costs for its
1377 for (i = 0; i < recog_data.n_operands; i++)
1378 if (REG_P (recog_data.operand[i])
1379 && REGNO (recog_data.operand[i]) >= FIRST_PSEUDO_REGISTER)
1381 int regno = REGNO (recog_data.operand[i]);
1382 struct costs *p = COSTS (costs, COST_INDEX (regno));
1383 struct costs *q = op_costs[i];
1384 int *p_costs = p->cost, *q_costs = q->cost;
1385 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1388 /* If the already accounted for the memory "cost" above, don't
1392 add_cost = q->mem_cost;
1393 if (add_cost > 0 && INT_MAX - add_cost < p->mem_cost)
1394 p->mem_cost = INT_MAX;
1396 p->mem_cost += add_cost;
1398 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1400 add_cost = q_costs[k];
1401 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1402 p_costs[k] = INT_MAX;
1404 p_costs[k] += add_cost;
1413 /* Print allocnos costs to file F. */
1415 print_allocno_costs (FILE *f)
1419 ira_allocno_iterator ai;
1421 ira_assert (allocno_p);
1423 FOR_EACH_ALLOCNO (a, ai)
1427 int regno = ALLOCNO_REGNO (a);
1428 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1429 enum reg_class *cost_classes = cost_classes_ptr->classes;
1431 i = ALLOCNO_NUM (a);
1432 fprintf (f, " a%d(r%d,", i, regno);
1433 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1434 fprintf (f, "b%d", bb->index);
1436 fprintf (f, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
1437 fprintf (f, ") costs:");
1438 for (k = 0; k < cost_classes_ptr->num; k++)
1440 rclass = cost_classes[k];
1441 if (contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (regno)]
1442 && ! invalid_mode_change_p (regno, (enum reg_class) rclass))
1444 fprintf (f, " %s:%d", reg_class_names[rclass],
1445 COSTS (costs, i)->cost[k]);
1446 if (flag_ira_region == IRA_REGION_ALL
1447 || flag_ira_region == IRA_REGION_MIXED)
1448 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->cost[k]);
1451 fprintf (f, " MEM:%i", COSTS (costs, i)->mem_cost);
1452 if (flag_ira_region == IRA_REGION_ALL
1453 || flag_ira_region == IRA_REGION_MIXED)
1454 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->mem_cost);
1459 /* Print pseudo costs to file F. */
1461 print_pseudo_costs (FILE *f)
1465 cost_classes_t cost_classes_ptr;
1466 enum reg_class *cost_classes;
1468 ira_assert (! allocno_p);
1470 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1472 if (REG_N_REFS (regno) <= 0)
1474 cost_classes_ptr = regno_cost_classes[regno];
1475 cost_classes = cost_classes_ptr->classes;
1476 fprintf (f, " r%d costs:", regno);
1477 for (k = 0; k < cost_classes_ptr->num; k++)
1479 rclass = cost_classes[k];
1480 if (contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (regno)]
1481 && ! invalid_mode_change_p (regno, (enum reg_class) rclass))
1482 fprintf (f, " %s:%d", reg_class_names[rclass],
1483 COSTS (costs, regno)->cost[k]);
1485 fprintf (f, " MEM:%i\n", COSTS (costs, regno)->mem_cost);
1489 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1492 process_bb_for_costs (basic_block bb)
1496 frequency = REG_FREQ_FROM_BB (bb);
1499 FOR_BB_INSNS (bb, insn)
1500 insn = scan_one_insn (insn);
1503 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1506 process_bb_node_for_costs (ira_loop_tree_node_t loop_tree_node)
1510 bb = loop_tree_node->bb;
1512 process_bb_for_costs (bb);
1515 /* Find costs of register classes and memory for allocnos or pseudos
1516 and their best costs. Set up preferred, alternative and allocno
1517 classes for pseudos. */
1519 find_costs_and_classes (FILE *dump_file)
1521 int i, k, start, max_cost_classes_num;
1524 enum reg_class *regno_best_class;
1528 = (enum reg_class *) ira_allocate (max_reg_num ()
1529 * sizeof (enum reg_class));
1530 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1531 regno_best_class[i] = NO_REGS;
1532 if (!resize_reg_info () && allocno_p
1533 && pseudo_classes_defined_p && flag_expensive_optimizations)
1536 ira_allocno_iterator ai;
1539 max_cost_classes_num = 1;
1540 FOR_EACH_ALLOCNO (a, ai)
1542 pref[ALLOCNO_NUM (a)] = reg_preferred_class (ALLOCNO_REGNO (a));
1543 setup_regno_cost_classes_by_aclass
1544 (ALLOCNO_REGNO (a), pref[ALLOCNO_NUM (a)]);
1545 max_cost_classes_num
1546 = MAX (max_cost_classes_num,
1547 regno_cost_classes[ALLOCNO_REGNO (a)]->num);
1554 max_cost_classes_num = ira_important_classes_num;
1555 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1556 if (regno_reg_rtx[i] != NULL_RTX)
1557 setup_regno_cost_classes_by_mode (i, PSEUDO_REGNO_MODE (i));
1559 setup_regno_cost_classes_by_aclass (i, ALL_REGS);
1563 /* Clear the flag for the next compiled function. */
1564 pseudo_classes_defined_p = false;
1565 /* Normally we scan the insns once and determine the best class to
1566 use for each allocno. However, if -fexpensive-optimizations are
1567 on, we do so twice, the second time using the tentative best
1568 classes to guide the selection. */
1569 for (pass = start; pass <= flag_expensive_optimizations; pass++)
1571 if ((!allocno_p || internal_flag_ira_verbose > 0) && dump_file)
1573 "\nPass %i for finding pseudo/allocno costs\n\n", pass);
1577 max_cost_classes_num = 1;
1578 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1580 setup_regno_cost_classes_by_aclass (i, regno_best_class[i]);
1581 max_cost_classes_num
1582 = MAX (max_cost_classes_num, regno_cost_classes[i]->num);
1587 = sizeof (struct costs) + sizeof (int) * (max_cost_classes_num - 1);
1588 /* Zero out our accumulation of the cost of each class for each
1590 memset (costs, 0, cost_elements_num * struct_costs_size);
1594 /* Scan the instructions and record each time it would save code
1595 to put a certain allocno in a certain class. */
1596 ira_traverse_loop_tree (true, ira_loop_tree_root,
1597 process_bb_node_for_costs, NULL);
1599 memcpy (total_allocno_costs, costs,
1600 max_struct_costs_size * ira_allocnos_num);
1606 FOR_EACH_BB_FN (bb, cfun)
1607 process_bb_for_costs (bb);
1613 /* Now for each allocno look at how desirable each class is and
1614 find which class is preferred. */
1615 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1617 ira_allocno_t a, parent_a;
1618 int rclass, a_num, parent_a_num, add_cost;
1619 ira_loop_tree_node_t parent;
1620 int best_cost, allocno_cost;
1621 enum reg_class best, alt_class;
1622 cost_classes_t cost_classes_ptr = regno_cost_classes[i];
1623 enum reg_class *cost_classes = cost_classes_ptr->classes;
1624 int *i_costs = temp_costs->cost;
1626 int equiv_savings = regno_equiv_gains[i];
1630 if (regno_reg_rtx[i] == NULL_RTX)
1632 memcpy (temp_costs, COSTS (costs, i), struct_costs_size);
1633 i_mem_cost = temp_costs->mem_cost;
1637 if (ira_regno_allocno_map[i] == NULL)
1639 memset (temp_costs, 0, struct_costs_size);
1641 /* Find cost of all allocnos with the same regno. */
1642 for (a = ira_regno_allocno_map[i];
1644 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1646 int *a_costs, *p_costs;
1648 a_num = ALLOCNO_NUM (a);
1649 if ((flag_ira_region == IRA_REGION_ALL
1650 || flag_ira_region == IRA_REGION_MIXED)
1651 && (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1652 && (parent_a = parent->regno_allocno_map[i]) != NULL
1653 /* There are no caps yet. */
1654 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE
1655 (a)->border_allocnos,
1658 /* Propagate costs to upper levels in the region
1660 parent_a_num = ALLOCNO_NUM (parent_a);
1661 a_costs = COSTS (total_allocno_costs, a_num)->cost;
1662 p_costs = COSTS (total_allocno_costs, parent_a_num)->cost;
1663 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1665 add_cost = a_costs[k];
1666 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1667 p_costs[k] = INT_MAX;
1669 p_costs[k] += add_cost;
1671 add_cost = COSTS (total_allocno_costs, a_num)->mem_cost;
1673 && (INT_MAX - add_cost
1674 < COSTS (total_allocno_costs,
1675 parent_a_num)->mem_cost))
1676 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1679 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1682 if (i >= first_moveable_pseudo && i < last_moveable_pseudo)
1683 COSTS (total_allocno_costs, parent_a_num)->mem_cost = 0;
1685 a_costs = COSTS (costs, a_num)->cost;
1686 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1688 add_cost = a_costs[k];
1689 if (add_cost > 0 && INT_MAX - add_cost < i_costs[k])
1690 i_costs[k] = INT_MAX;
1692 i_costs[k] += add_cost;
1694 add_cost = COSTS (costs, a_num)->mem_cost;
1695 if (add_cost > 0 && INT_MAX - add_cost < i_mem_cost)
1696 i_mem_cost = INT_MAX;
1698 i_mem_cost += add_cost;
1701 if (i >= first_moveable_pseudo && i < last_moveable_pseudo)
1703 else if (equiv_savings < 0)
1704 i_mem_cost = -equiv_savings;
1705 else if (equiv_savings > 0)
1708 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1709 i_costs[k] += equiv_savings;
1712 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1714 alt_class = NO_REGS;
1715 /* Find best common class for all allocnos with the same
1717 for (k = 0; k < cost_classes_ptr->num; k++)
1719 rclass = cost_classes[k];
1720 /* Ignore classes that are too small or invalid for this
1722 if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)]
1723 || invalid_mode_change_p (i, (enum reg_class) rclass))
1725 if (i_costs[k] < best_cost)
1727 best_cost = i_costs[k];
1728 best = (enum reg_class) rclass;
1730 else if (i_costs[k] == best_cost)
1731 best = ira_reg_class_subunion[best][rclass];
1732 if (pass == flag_expensive_optimizations
1733 /* We still prefer registers to memory even at this
1734 stage if their costs are the same. We will make
1735 a final decision during assigning hard registers
1736 when we have all info including more accurate
1737 costs which might be affected by assigning hard
1738 registers to other pseudos because the pseudos
1739 involved in moves can be coalesced. */
1740 && i_costs[k] <= i_mem_cost
1741 && (reg_class_size[reg_class_subunion[alt_class][rclass]]
1742 > reg_class_size[alt_class]))
1743 alt_class = reg_class_subunion[alt_class][rclass];
1745 alt_class = ira_allocno_class_translate[alt_class];
1746 if (best_cost > i_mem_cost)
1747 regno_aclass[i] = NO_REGS;
1748 else if (!optimize && !targetm.class_likely_spilled_p (best))
1749 /* Registers in the alternative class are likely to need
1750 longer or slower sequences than registers in the best class.
1751 When optimizing we make some effort to use the best class
1752 over the alternative class where possible, but at -O0 we
1753 effectively give the alternative class equal weight.
1754 We then run the risk of using slower alternative registers
1755 when plenty of registers from the best class are still free.
1756 This is especially true because live ranges tend to be very
1757 short in -O0 code and so register pressure tends to be low.
1759 Avoid that by ignoring the alternative class if the best
1760 class has plenty of registers. */
1761 regno_aclass[i] = best;
1764 /* Make the common class the biggest class of best and
1767 = ira_reg_class_superunion[best][alt_class];
1768 ira_assert (regno_aclass[i] != NO_REGS
1769 && ira_reg_allocno_class_p[regno_aclass[i]]);
1771 if (pass == flag_expensive_optimizations)
1773 if (best_cost > i_mem_cost)
1774 best = alt_class = NO_REGS;
1775 else if (best == alt_class)
1776 alt_class = NO_REGS;
1777 setup_reg_classes (i, best, alt_class, regno_aclass[i]);
1778 if ((!allocno_p || internal_flag_ira_verbose > 2)
1779 && dump_file != NULL)
1781 " r%d: preferred %s, alternative %s, allocno %s\n",
1782 i, reg_class_names[best], reg_class_names[alt_class],
1783 reg_class_names[regno_aclass[i]]);
1785 regno_best_class[i] = best;
1788 pref[i] = best_cost > i_mem_cost ? NO_REGS : best;
1791 for (a = ira_regno_allocno_map[i];
1793 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1795 enum reg_class aclass = regno_aclass[i];
1796 int a_num = ALLOCNO_NUM (a);
1797 int *total_a_costs = COSTS (total_allocno_costs, a_num)->cost;
1798 int *a_costs = COSTS (costs, a_num)->cost;
1800 if (aclass == NO_REGS)
1804 /* Finding best class which is subset of the common
1806 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1807 allocno_cost = best_cost;
1809 for (k = 0; k < cost_classes_ptr->num; k++)
1811 rclass = cost_classes[k];
1812 if (! ira_class_subset_p[rclass][aclass])
1814 /* Ignore classes that are too small or invalid
1815 for this operand. */
1816 if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)]
1817 || invalid_mode_change_p (i, (enum reg_class) rclass))
1819 else if (total_a_costs[k] < best_cost)
1821 best_cost = total_a_costs[k];
1822 allocno_cost = a_costs[k];
1823 best = (enum reg_class) rclass;
1825 else if (total_a_costs[k] == best_cost)
1827 best = ira_reg_class_subunion[best][rclass];
1828 allocno_cost = MAX (allocno_cost, a_costs[k]);
1831 ALLOCNO_CLASS_COST (a) = allocno_cost;
1833 if (internal_flag_ira_verbose > 2 && dump_file != NULL
1834 && (pass == 0 || pref[a_num] != best))
1836 fprintf (dump_file, " a%d (r%d,", a_num, i);
1837 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1838 fprintf (dump_file, "b%d", bb->index);
1840 fprintf (dump_file, "l%d",
1841 ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
1842 fprintf (dump_file, ") best %s, allocno %s\n",
1843 reg_class_names[best],
1844 reg_class_names[aclass]);
1847 if (pass == flag_expensive_optimizations && best != aclass
1848 && ira_class_hard_regs_num[best] > 0
1849 && (ira_reg_class_max_nregs[best][ALLOCNO_MODE (a)]
1850 >= ira_class_hard_regs_num[best]))
1852 int ind = cost_classes_ptr->index[aclass];
1854 ira_assert (ind >= 0);
1855 ira_init_register_move_cost_if_necessary (ALLOCNO_MODE (a));
1856 ira_add_allocno_pref (a, ira_class_hard_regs[best][0],
1857 (a_costs[ind] - ALLOCNO_CLASS_COST (a))
1858 / (ira_register_move_cost
1859 [ALLOCNO_MODE (a)][best][aclass]));
1860 for (k = 0; k < cost_classes_ptr->num; k++)
1861 if (ira_class_subset_p[cost_classes[k]][best])
1862 a_costs[k] = a_costs[ind];
1867 if (internal_flag_ira_verbose > 4 && dump_file)
1870 print_allocno_costs (dump_file);
1872 print_pseudo_costs (dump_file);
1873 fprintf (dump_file,"\n");
1876 ira_free (regno_best_class);
1881 /* Process moves involving hard regs to modify allocno hard register
1882 costs. We can do this only after determining allocno class. If a
1883 hard register forms a register class, then moves with the hard
1884 register are already taken into account in class costs for the
1887 process_bb_node_for_hard_reg_moves (ira_loop_tree_node_t loop_tree_node)
1889 int i, freq, src_regno, dst_regno, hard_regno, a_regno;
1891 ira_allocno_t a, curr_a;
1892 ira_loop_tree_node_t curr_loop_tree_node;
1893 enum reg_class rclass;
1898 bb = loop_tree_node->bb;
1901 freq = REG_FREQ_FROM_BB (bb);
1904 FOR_BB_INSNS (bb, insn)
1906 if (!NONDEBUG_INSN_P (insn))
1908 set = single_set (insn);
1909 if (set == NULL_RTX)
1911 dst = SET_DEST (set);
1912 src = SET_SRC (set);
1913 if (! REG_P (dst) || ! REG_P (src))
1915 dst_regno = REGNO (dst);
1916 src_regno = REGNO (src);
1917 if (dst_regno >= FIRST_PSEUDO_REGISTER
1918 && src_regno < FIRST_PSEUDO_REGISTER)
1920 hard_regno = src_regno;
1921 a = ira_curr_regno_allocno_map[dst_regno];
1924 else if (src_regno >= FIRST_PSEUDO_REGISTER
1925 && dst_regno < FIRST_PSEUDO_REGISTER)
1927 hard_regno = dst_regno;
1928 a = ira_curr_regno_allocno_map[src_regno];
1933 rclass = ALLOCNO_CLASS (a);
1934 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass], hard_regno))
1936 i = ira_class_hard_reg_index[rclass][hard_regno];
1939 a_regno = ALLOCNO_REGNO (a);
1940 for (curr_loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
1941 curr_loop_tree_node != NULL;
1942 curr_loop_tree_node = curr_loop_tree_node->parent)
1943 if ((curr_a = curr_loop_tree_node->regno_allocno_map[a_regno]) != NULL)
1944 ira_add_allocno_pref (curr_a, hard_regno, freq);
1947 enum reg_class hard_reg_class;
1948 enum machine_mode mode;
1950 mode = ALLOCNO_MODE (a);
1951 hard_reg_class = REGNO_REG_CLASS (hard_regno);
1952 ira_init_register_move_cost_if_necessary (mode);
1953 cost = (to_p ? ira_register_move_cost[mode][hard_reg_class][rclass]
1954 : ira_register_move_cost[mode][rclass][hard_reg_class]) * freq;
1955 ira_allocate_and_set_costs (&ALLOCNO_HARD_REG_COSTS (a), rclass,
1956 ALLOCNO_CLASS_COST (a));
1957 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
1959 ALLOCNO_HARD_REG_COSTS (a)[i] -= cost;
1960 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[i] -= cost;
1961 ALLOCNO_CLASS_COST (a) = MIN (ALLOCNO_CLASS_COST (a),
1962 ALLOCNO_HARD_REG_COSTS (a)[i]);
1967 /* After we find hard register and memory costs for allocnos, define
1968 its class and modify hard register cost because insns moving
1969 allocno to/from hard registers. */
1971 setup_allocno_class_and_costs (void)
1973 int i, j, n, regno, hard_regno, num;
1975 enum reg_class aclass, rclass;
1977 ira_allocno_iterator ai;
1978 cost_classes_t cost_classes_ptr;
1980 ira_assert (allocno_p);
1981 FOR_EACH_ALLOCNO (a, ai)
1983 i = ALLOCNO_NUM (a);
1984 regno = ALLOCNO_REGNO (a);
1985 aclass = regno_aclass[regno];
1986 cost_classes_ptr = regno_cost_classes[regno];
1987 ira_assert (pref[i] == NO_REGS || aclass != NO_REGS);
1988 ALLOCNO_MEMORY_COST (a) = COSTS (costs, i)->mem_cost;
1989 ira_set_allocno_class (a, aclass);
1990 if (aclass == NO_REGS)
1992 if (optimize && ALLOCNO_CLASS (a) != pref[i])
1994 n = ira_class_hard_regs_num[aclass];
1995 ALLOCNO_HARD_REG_COSTS (a)
1996 = reg_costs = ira_allocate_cost_vector (aclass);
1997 for (j = n - 1; j >= 0; j--)
1999 hard_regno = ira_class_hard_regs[aclass][j];
2000 if (TEST_HARD_REG_BIT (reg_class_contents[pref[i]], hard_regno))
2001 reg_costs[j] = ALLOCNO_CLASS_COST (a);
2004 rclass = REGNO_REG_CLASS (hard_regno);
2005 num = cost_classes_ptr->index[rclass];
2008 num = cost_classes_ptr->hard_regno_index[hard_regno];
2009 ira_assert (num >= 0);
2011 reg_costs[j] = COSTS (costs, i)->cost[num];
2017 ira_traverse_loop_tree (true, ira_loop_tree_root,
2018 process_bb_node_for_hard_reg_moves, NULL);
2023 /* Function called once during compiler work. */
2025 ira_init_costs_once (void)
2030 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2033 this_op_costs[i] = NULL;
2038 /* Free allocated temporary cost vectors. */
2040 target_ira_int::free_ira_costs ()
2046 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2048 free (x_op_costs[i]);
2049 free (x_this_op_costs[i]);
2050 x_op_costs[i] = x_this_op_costs[i] = NULL;
2052 free (x_temp_costs);
2053 x_temp_costs = NULL;
2056 /* This is called each time register related information is
2059 ira_init_costs (void)
2063 this_target_ira_int->free_ira_costs ();
2064 max_struct_costs_size
2065 = sizeof (struct costs) + sizeof (int) * (ira_important_classes_num - 1);
2066 /* Don't use ira_allocate because vectors live through several IRA
2068 init_cost = (struct costs *) xmalloc (max_struct_costs_size);
2069 init_cost->mem_cost = 1000000;
2070 for (i = 0; i < ira_important_classes_num; i++)
2071 init_cost->cost[i] = 1000000;
2072 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2074 op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
2075 this_op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
2077 temp_costs = (struct costs *) xmalloc (max_struct_costs_size);
2082 /* Common initialization function for ira_costs and
2083 ira_set_pseudo_classes. */
2087 init_subregs_of_mode ();
2088 costs = (struct costs *) ira_allocate (max_struct_costs_size
2089 * cost_elements_num);
2090 pref_buffer = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
2091 * cost_elements_num);
2092 regno_aclass = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
2094 regno_equiv_gains = (int *) ira_allocate (sizeof (int) * max_reg_num ());
2095 memset (regno_equiv_gains, 0, sizeof (int) * max_reg_num ());
2098 /* Common finalization function for ira_costs and
2099 ira_set_pseudo_classes. */
2103 finish_subregs_of_mode ();
2104 ira_free (regno_equiv_gains);
2105 ira_free (regno_aclass);
2106 ira_free (pref_buffer);
2110 /* Entry function which defines register class, memory and hard
2111 register costs for each allocno. */
2116 cost_elements_num = ira_allocnos_num;
2118 total_allocno_costs = (struct costs *) ira_allocate (max_struct_costs_size
2119 * ira_allocnos_num);
2120 initiate_regno_cost_classes ();
2121 calculate_elim_costs_all_insns ();
2122 find_costs_and_classes (ira_dump_file);
2123 setup_allocno_class_and_costs ();
2124 finish_regno_cost_classes ();
2126 ira_free (total_allocno_costs);
2129 /* Entry function which defines classes for pseudos.
2130 Set pseudo_classes_defined_p only if DEFINE_PSEUDO_CLASSES is true. */
2132 ira_set_pseudo_classes (bool define_pseudo_classes, FILE *dump_file)
2135 internal_flag_ira_verbose = flag_ira_verbose;
2136 cost_elements_num = max_reg_num ();
2138 initiate_regno_cost_classes ();
2139 find_costs_and_classes (dump_file);
2140 finish_regno_cost_classes ();
2141 if (define_pseudo_classes)
2142 pseudo_classes_defined_p = true;
2149 /* Change hard register costs for allocnos which lives through
2150 function calls. This is called only when we found all intersected
2151 calls during building allocno live ranges. */
2153 ira_tune_allocno_costs (void)
2156 int cost, min_cost, *reg_costs;
2157 enum reg_class aclass, rclass;
2158 enum machine_mode mode;
2160 ira_allocno_iterator ai;
2161 ira_allocno_object_iterator oi;
2164 HARD_REG_SET *crossed_calls_clobber_regs;
2166 FOR_EACH_ALLOCNO (a, ai)
2168 aclass = ALLOCNO_CLASS (a);
2169 if (aclass == NO_REGS)
2171 mode = ALLOCNO_MODE (a);
2172 n = ira_class_hard_regs_num[aclass];
2174 if (ALLOCNO_CALLS_CROSSED_NUM (a)
2175 != ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2177 ira_allocate_and_set_costs
2178 (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2179 ALLOCNO_CLASS_COST (a));
2180 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2181 for (j = n - 1; j >= 0; j--)
2183 regno = ira_class_hard_regs[aclass][j];
2185 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2187 if (ira_hard_reg_set_intersection_p (regno, mode,
2188 OBJECT_CONFLICT_HARD_REGS
2197 rclass = REGNO_REG_CLASS (regno);
2199 crossed_calls_clobber_regs
2200 = &(ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
2201 if (ira_hard_reg_set_intersection_p (regno, mode,
2202 *crossed_calls_clobber_regs)
2203 && (ira_hard_reg_set_intersection_p (regno, mode,
2205 || HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
2206 cost += (ALLOCNO_CALL_FREQ (a)
2207 * (ira_memory_move_cost[mode][rclass][0]
2208 + ira_memory_move_cost[mode][rclass][1]));
2209 #ifdef IRA_HARD_REGNO_ADD_COST_MULTIPLIER
2210 cost += ((ira_memory_move_cost[mode][rclass][0]
2211 + ira_memory_move_cost[mode][rclass][1])
2213 * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno) / 2);
2215 if (INT_MAX - cost < reg_costs[j])
2216 reg_costs[j] = INT_MAX;
2218 reg_costs[j] += cost;
2219 if (min_cost > reg_costs[j])
2220 min_cost = reg_costs[j];
2223 if (min_cost != INT_MAX)
2224 ALLOCNO_CLASS_COST (a) = min_cost;
2226 /* Some targets allow pseudos to be allocated to unaligned sequences
2227 of hard registers. However, selecting an unaligned sequence can
2228 unnecessarily restrict later allocations. So increase the cost of
2229 unaligned hard regs to encourage the use of aligned hard regs. */
2231 const int nregs = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2235 ira_allocate_and_set_costs
2236 (&ALLOCNO_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a));
2237 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2238 for (j = n - 1; j >= 0; j--)
2240 regno = ira_non_ordered_class_hard_regs[aclass][j];
2241 if ((regno % nregs) != 0)
2243 int index = ira_class_hard_reg_index[aclass][regno];
2244 ira_assert (index != -1);
2245 reg_costs[index] += ALLOCNO_FREQ (a);
2253 /* Add COST to the estimated gain for eliminating REGNO with its
2254 equivalence. If COST is zero, record that no such elimination is
2258 ira_adjust_equiv_reg_cost (unsigned regno, int cost)
2261 regno_equiv_gains[regno] = 0;
2263 regno_equiv_gains[regno] += cost;