gcc/
[official-gcc.git] / gcc / ira-costs.c
blob774a958e353c996281dbde3b38d4ad2386672545
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
10 version.
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
15 for more details.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "hash-table.h"
26 #include "hard-reg-set.h"
27 #include "rtl.h"
28 #include "expr.h"
29 #include "tm_p.h"
30 #include "flags.h"
31 #include "basic-block.h"
32 #include "regs.h"
33 #include "addresses.h"
34 #include "insn-config.h"
35 #include "recog.h"
36 #include "reload.h"
37 #include "diagnostic-core.h"
38 #include "target.h"
39 #include "params.h"
40 #include "ira-int.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
54 allocno or pseudo. */
55 struct costs
57 int mem_cost;
58 /* Costs for register classes start here. We process only some
59 allocno classes. */
60 int cost[1];
63 #define max_struct_costs_size \
64 (this_target_ira_int->x_max_struct_costs_size)
65 #define init_cost \
66 (this_target_ira_int->x_init_cost)
67 #define temp_costs \
68 (this_target_ira_int->x_temp_costs)
69 #define op_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]) \
91 : (int) 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
95 cost calculation. */
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
105 equivalence. */
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. */
114 struct cost_classes
116 /* Number of the cost classes in the subsequent array. */
117 int num;
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 /* 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. */
147 inline hashval_t
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. */
154 inline bool
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. */
163 inline void
164 cost_classes_hasher::remove (value_type *v)
166 ira_free (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
173 class. */
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. */
180 static void
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;
203 enum reg_class cl;
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;
223 return classes_ptr;
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. */
232 static void
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;
237 enum reg_class cl;
238 int i;
239 cost_classes **slot;
240 HARD_REG_SET temp, temp2;
241 bool exclude_p;
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];
250 classes.num = 0;
251 for (i = 0; i < ira_important_classes_num; i++)
253 cl = ira_important_classes[i];
254 if (exclude_p)
256 /* Exclude non-uniform classes which are subsets of
257 ACLASS. */
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)
261 continue;
263 classes.classes[classes.num++] = cl;
265 slot = cost_classes_htab->find_slot (&classes, INSERT);
266 if (*slot == NULL)
268 classes_ptr = setup_cost_classes (&classes);
269 *slot = classes_ptr;
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 waisting CPU
281 time. */
282 static void
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;
287 enum reg_class cl;
288 int i;
289 cost_classes **slot;
290 HARD_REG_SET temp;
292 if ((classes_ptr = cost_classes_mode_cache[mode]) == NULL)
294 classes.num = 0;
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))
301 continue;
302 classes.classes[classes.num++] = cl;
304 slot = cost_classes_htab->find_slot (&classes, INSERT);
305 if (*slot == NULL)
307 classes_ptr = setup_cost_classes (&classes);
308 *slot = classes_ptr;
310 else
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 /* Finilize info about the cost classes for each pseudo. */
318 static void
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. */
331 static int
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)
341 return 0;
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
348 copy it. */
349 sri.prev_sri = prev_sri;
350 sri.extra_cost = 0;
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]
357 + sri.extra_cost
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];
367 else if (REG_P (x))
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]);
375 else
376 /* If this is a constant, we may eventually want to call rtx_cost
377 here. */
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
402 the alternatives. */
403 static void
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)
408 int alt;
409 int i, j, k;
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 for (alt = 0; alt < n_alts; alt++)
421 enum reg_class classes[MAX_RECOG_OPERANDS];
422 int allows_mem[MAX_RECOG_OPERANDS];
423 enum reg_class rclass;
424 int alt_fail = 0;
425 int alt_cost = 0, op_cost_add;
427 if (!TEST_BIT (recog_data.enabled_alternatives, alt))
429 for (i = 0; i < recog_data.n_operands; i++)
430 constraints[i] = skip_alternative (constraints[i]);
432 continue;
435 for (i = 0; i < n_ops; i++)
437 unsigned char c;
438 const char *p = constraints[i];
439 rtx op = ops[i];
440 enum machine_mode mode = modes[i];
441 int allows_addr = 0;
442 int win = 0;
444 /* Initially show we know nothing about the register class. */
445 classes[i] = NO_REGS;
446 allows_mem[i] = 0;
448 /* If this operand has no constraints at all, we can
449 conclude nothing about it since anything is valid. */
450 if (*p == 0)
452 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
453 memset (this_op_costs[i], 0, struct_costs_size);
454 continue;
457 /* If this alternative is only relevant when this operand
458 matches a previous operand, we do different things
459 depending on whether this operand is a allocno-reg or not.
460 We must process any modifiers for the operand before we
461 can make this test. */
462 while (*p == '%' || *p == '=' || *p == '+' || *p == '&')
463 p++;
465 if (p[0] >= '0' && p[0] <= '0' + i && (p[1] == ',' || p[1] == 0))
467 /* Copy class and whether memory is allowed from the
468 matching alternative. Then perform any needed cost
469 computations and/or adjustments. */
470 j = p[0] - '0';
471 classes[i] = classes[j];
472 allows_mem[i] = allows_mem[j];
473 if (allows_mem[i])
474 insn_allows_mem[i] = 1;
476 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
478 /* If this matches the other operand, we have no
479 added cost and we win. */
480 if (rtx_equal_p (ops[j], op))
481 win = 1;
482 /* If we can put the other operand into a register,
483 add to the cost of this alternative the cost to
484 copy this operand to the register used for the
485 other operand. */
486 else if (classes[j] != NO_REGS)
488 alt_cost += copy_cost (op, mode, classes[j], 1, NULL);
489 win = 1;
492 else if (! REG_P (ops[j])
493 || REGNO (ops[j]) < FIRST_PSEUDO_REGISTER)
495 /* This op is an allocno but the one it matches is
496 not. */
498 /* If we can't put the other operand into a
499 register, this alternative can't be used. */
501 if (classes[j] == NO_REGS)
502 alt_fail = 1;
503 /* Otherwise, add to the cost of this alternative
504 the cost to copy the other operand to the hard
505 register used for this operand. */
506 else
507 alt_cost += copy_cost (ops[j], mode, classes[j], 1, NULL);
509 else
511 /* The costs of this operand are not the same as the
512 other operand since move costs are not symmetric.
513 Moreover, if we cannot tie them, this alternative
514 needs to do a copy, which is one insn. */
515 struct costs *pp = this_op_costs[i];
516 int *pp_costs = pp->cost;
517 cost_classes_t cost_classes_ptr
518 = regno_cost_classes[REGNO (op)];
519 enum reg_class *cost_classes = cost_classes_ptr->classes;
520 bool in_p = recog_data.operand_type[i] != OP_OUT;
521 bool out_p = recog_data.operand_type[i] != OP_IN;
522 enum reg_class op_class = classes[i];
524 ira_init_register_move_cost_if_necessary (mode);
525 if (! in_p)
527 ira_assert (out_p);
528 if (op_class == NO_REGS)
530 mem_cost = ira_memory_move_cost[mode];
531 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
533 rclass = cost_classes[k];
534 pp_costs[k] = mem_cost[rclass][0] * frequency;
537 else
539 move_out_cost = ira_may_move_out_cost[mode];
540 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
542 rclass = cost_classes[k];
543 pp_costs[k]
544 = move_out_cost[op_class][rclass] * frequency;
548 else if (! out_p)
550 ira_assert (in_p);
551 if (op_class == NO_REGS)
553 mem_cost = ira_memory_move_cost[mode];
554 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
556 rclass = cost_classes[k];
557 pp_costs[k] = mem_cost[rclass][1] * frequency;
560 else
562 move_in_cost = ira_may_move_in_cost[mode];
563 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
565 rclass = cost_classes[k];
566 pp_costs[k]
567 = move_in_cost[rclass][op_class] * frequency;
571 else
573 if (op_class == NO_REGS)
575 mem_cost = ira_memory_move_cost[mode];
576 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
578 rclass = cost_classes[k];
579 pp_costs[k] = ((mem_cost[rclass][0]
580 + mem_cost[rclass][1])
581 * frequency);
584 else
586 move_in_cost = ira_may_move_in_cost[mode];
587 move_out_cost = ira_may_move_out_cost[mode];
588 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
590 rclass = cost_classes[k];
591 pp_costs[k] = ((move_in_cost[rclass][op_class]
592 + move_out_cost[op_class][rclass])
593 * frequency);
598 /* If the alternative actually allows memory, make
599 things a bit cheaper since we won't need an extra
600 insn to load it. */
601 pp->mem_cost
602 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
603 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
604 - allows_mem[i]) * frequency;
606 /* If we have assigned a class to this allocno in
607 our first pass, add a cost to this alternative
608 corresponding to what we would add if this
609 allocno were not in the appropriate class. */
610 if (pref)
612 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
614 if (pref_class == NO_REGS)
615 alt_cost
616 += ((out_p
617 ? ira_memory_move_cost[mode][op_class][0] : 0)
618 + (in_p
619 ? ira_memory_move_cost[mode][op_class][1]
620 : 0));
621 else if (ira_reg_class_intersect
622 [pref_class][op_class] == NO_REGS)
623 alt_cost
624 += ira_register_move_cost[mode][pref_class][op_class];
626 if (REGNO (ops[i]) != REGNO (ops[j])
627 && ! find_reg_note (insn, REG_DEAD, op))
628 alt_cost += 2;
630 /* This is in place of ordinary cost computation for
631 this operand, so skip to the end of the
632 alternative (should be just one character). */
633 while (*p && *p++ != ',')
636 constraints[i] = p;
637 continue;
641 /* Scan all the constraint letters. See if the operand
642 matches any of the constraints. Collect the valid
643 register classes and see if this operand accepts
644 memory. */
645 while ((c = *p))
647 switch (c)
649 case '*':
650 /* Ignore the next letter for this pass. */
651 c = *++p;
652 break;
654 case '?':
655 alt_cost += 2;
656 break;
658 case 'g':
659 if (MEM_P (op)
660 || (CONSTANT_P (op)
661 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))))
662 win = 1;
663 insn_allows_mem[i] = allows_mem[i] = 1;
664 classes[i] = ira_reg_class_subunion[classes[i]][GENERAL_REGS];
665 break;
667 default:
668 enum constraint_num cn = lookup_constraint (p);
669 enum reg_class cl;
670 switch (get_constraint_type (cn))
672 case CT_REGISTER:
673 cl = reg_class_for_constraint (cn);
674 if (cl != NO_REGS)
675 classes[i] = ira_reg_class_subunion[classes[i]][cl];
676 break;
678 case CT_CONST_INT:
679 if (CONST_INT_P (op)
680 && insn_const_int_ok_for_constraint (INTVAL (op), cn))
681 win = 1;
682 break;
684 case CT_MEMORY:
685 /* Every MEM can be reloaded to fit. */
686 insn_allows_mem[i] = allows_mem[i] = 1;
687 if (MEM_P (op))
688 win = 1;
689 break;
691 case CT_ADDRESS:
692 /* Every address can be reloaded to fit. */
693 allows_addr = 1;
694 if (address_operand (op, GET_MODE (op))
695 || constraint_satisfied_p (op, cn))
696 win = 1;
697 /* We know this operand is an address, so we
698 want it to be allocated to a hard register
699 that can be the base of an address,
700 i.e. BASE_REG_CLASS. */
701 classes[i]
702 = ira_reg_class_subunion[classes[i]]
703 [base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
704 ADDRESS, SCRATCH)];
705 break;
707 case CT_FIXED_FORM:
708 if (constraint_satisfied_p (op, cn))
709 win = 1;
710 break;
712 break;
714 p += CONSTRAINT_LEN (c, p);
715 if (c == ',')
716 break;
719 constraints[i] = p;
721 /* How we account for this operand now depends on whether it
722 is a pseudo register or not. If it is, we first check if
723 any register classes are valid. If not, we ignore this
724 alternative, since we want to assume that all allocnos get
725 allocated for register preferencing. If some register
726 class is valid, compute the costs of moving the allocno
727 into that class. */
728 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
730 if (classes[i] == NO_REGS && ! allows_mem[i])
732 /* We must always fail if the operand is a REG, but
733 we did not find a suitable class and memory is
734 not allowed.
736 Otherwise we may perform an uninitialized read
737 from this_op_costs after the `continue' statement
738 below. */
739 alt_fail = 1;
741 else
743 unsigned int regno = REGNO (op);
744 struct costs *pp = this_op_costs[i];
745 int *pp_costs = pp->cost;
746 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
747 enum reg_class *cost_classes = cost_classes_ptr->classes;
748 bool in_p = recog_data.operand_type[i] != OP_OUT;
749 bool out_p = recog_data.operand_type[i] != OP_IN;
750 enum reg_class op_class = classes[i];
752 ira_init_register_move_cost_if_necessary (mode);
753 if (! in_p)
755 ira_assert (out_p);
756 if (op_class == NO_REGS)
758 mem_cost = ira_memory_move_cost[mode];
759 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
761 rclass = cost_classes[k];
762 pp_costs[k] = mem_cost[rclass][0] * frequency;
765 else
767 move_out_cost = ira_may_move_out_cost[mode];
768 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
770 rclass = cost_classes[k];
771 pp_costs[k]
772 = move_out_cost[op_class][rclass] * frequency;
776 else if (! out_p)
778 ira_assert (in_p);
779 if (op_class == NO_REGS)
781 mem_cost = ira_memory_move_cost[mode];
782 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
784 rclass = cost_classes[k];
785 pp_costs[k] = mem_cost[rclass][1] * frequency;
788 else
790 move_in_cost = ira_may_move_in_cost[mode];
791 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
793 rclass = cost_classes[k];
794 pp_costs[k]
795 = move_in_cost[rclass][op_class] * frequency;
799 else
801 if (op_class == NO_REGS)
803 mem_cost = ira_memory_move_cost[mode];
804 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
806 rclass = cost_classes[k];
807 pp_costs[k] = ((mem_cost[rclass][0]
808 + mem_cost[rclass][1])
809 * frequency);
812 else
814 move_in_cost = ira_may_move_in_cost[mode];
815 move_out_cost = ira_may_move_out_cost[mode];
816 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
818 rclass = cost_classes[k];
819 pp_costs[k] = ((move_in_cost[rclass][op_class]
820 + move_out_cost[op_class][rclass])
821 * frequency);
826 if (op_class == NO_REGS)
827 /* Although we don't need insn to reload from
828 memory, still accessing memory is usually more
829 expensive than a register. */
830 pp->mem_cost = frequency;
831 else
832 /* If the alternative actually allows memory, make
833 things a bit cheaper since we won't need an
834 extra insn to load it. */
835 pp->mem_cost
836 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
837 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
838 - allows_mem[i]) * frequency;
839 /* If we have assigned a class to this allocno in
840 our first pass, add a cost to this alternative
841 corresponding to what we would add if this
842 allocno were not in the appropriate class. */
843 if (pref)
845 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
847 if (pref_class == NO_REGS)
849 if (op_class != NO_REGS)
850 alt_cost
851 += ((out_p
852 ? ira_memory_move_cost[mode][op_class][0]
853 : 0)
854 + (in_p
855 ? ira_memory_move_cost[mode][op_class][1]
856 : 0));
858 else if (op_class == NO_REGS)
859 alt_cost
860 += ((out_p
861 ? ira_memory_move_cost[mode][pref_class][1]
862 : 0)
863 + (in_p
864 ? ira_memory_move_cost[mode][pref_class][0]
865 : 0));
866 else if (ira_reg_class_intersect[pref_class][op_class]
867 == NO_REGS)
868 alt_cost += (ira_register_move_cost
869 [mode][pref_class][op_class]);
874 /* Otherwise, if this alternative wins, either because we
875 have already determined that or if we have a hard
876 register of the proper class, there is no cost for this
877 alternative. */
878 else if (win || (REG_P (op)
879 && reg_fits_class_p (op, classes[i],
880 0, GET_MODE (op))))
883 /* If registers are valid, the cost of this alternative
884 includes copying the object to and/or from a
885 register. */
886 else if (classes[i] != NO_REGS)
888 if (recog_data.operand_type[i] != OP_OUT)
889 alt_cost += copy_cost (op, mode, classes[i], 1, NULL);
891 if (recog_data.operand_type[i] != OP_IN)
892 alt_cost += copy_cost (op, mode, classes[i], 0, NULL);
894 /* The only other way this alternative can be used is if
895 this is a constant that could be placed into memory. */
896 else if (CONSTANT_P (op) && (allows_addr || allows_mem[i]))
897 alt_cost += ira_memory_move_cost[mode][classes[i]][1];
898 else
899 alt_fail = 1;
902 if (alt_fail)
903 continue;
905 op_cost_add = alt_cost * frequency;
906 /* Finally, update the costs with the information we've
907 calculated about this alternative. */
908 for (i = 0; i < n_ops; i++)
909 if (REG_P (ops[i]) && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
911 struct costs *pp = op_costs[i], *qq = this_op_costs[i];
912 int *pp_costs = pp->cost, *qq_costs = qq->cost;
913 int scale = 1 + (recog_data.operand_type[i] == OP_INOUT);
914 cost_classes_t cost_classes_ptr
915 = regno_cost_classes[REGNO (ops[i])];
917 pp->mem_cost = MIN (pp->mem_cost,
918 (qq->mem_cost + op_cost_add) * scale);
920 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
921 pp_costs[k]
922 = MIN (pp_costs[k], (qq_costs[k] + op_cost_add) * scale);
926 if (allocno_p)
927 for (i = 0; i < n_ops; i++)
929 ira_allocno_t a;
930 rtx op = ops[i];
932 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
933 continue;
934 a = ira_curr_regno_allocno_map [REGNO (op)];
935 if (! ALLOCNO_BAD_SPILL_P (a) && insn_allows_mem[i] == 0)
936 ALLOCNO_BAD_SPILL_P (a) = true;
943 /* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudo registers. */
944 static inline bool
945 ok_for_index_p_nonstrict (rtx reg)
947 unsigned regno = REGNO (reg);
949 return regno >= FIRST_PSEUDO_REGISTER || REGNO_OK_FOR_INDEX_P (regno);
952 /* A version of regno_ok_for_base_p for use here, when all
953 pseudo-registers should count as OK. Arguments as for
954 regno_ok_for_base_p. */
955 static inline bool
956 ok_for_base_p_nonstrict (rtx reg, enum machine_mode mode, addr_space_t as,
957 enum rtx_code outer_code, enum rtx_code index_code)
959 unsigned regno = REGNO (reg);
961 if (regno >= FIRST_PSEUDO_REGISTER)
962 return true;
963 return ok_for_base_p_1 (regno, mode, as, outer_code, index_code);
966 /* Record the pseudo registers we must reload into hard registers in a
967 subexpression of a memory address, X.
969 If CONTEXT is 0, we are looking at the base part of an address,
970 otherwise we are looking at the index part.
972 MODE and AS are the mode and address space of the memory reference;
973 OUTER_CODE and INDEX_CODE give the context that the rtx appears in.
974 These four arguments are passed down to base_reg_class.
976 SCALE is twice the amount to multiply the cost by (it is twice so
977 we can represent half-cost adjustments). */
978 static void
979 record_address_regs (enum machine_mode mode, addr_space_t as, rtx x,
980 int context, enum rtx_code outer_code,
981 enum rtx_code index_code, int scale)
983 enum rtx_code code = GET_CODE (x);
984 enum reg_class rclass;
986 if (context == 1)
987 rclass = INDEX_REG_CLASS;
988 else
989 rclass = base_reg_class (mode, as, outer_code, index_code);
991 switch (code)
993 case CONST_INT:
994 case CONST:
995 case CC0:
996 case PC:
997 case SYMBOL_REF:
998 case LABEL_REF:
999 return;
1001 case PLUS:
1002 /* When we have an address that is a sum, we must determine
1003 whether registers are "base" or "index" regs. If there is a
1004 sum of two registers, we must choose one to be the "base".
1005 Luckily, we can use the REG_POINTER to make a good choice
1006 most of the time. We only need to do this on machines that
1007 can have two registers in an address and where the base and
1008 index register classes are different.
1010 ??? This code used to set REGNO_POINTER_FLAG in some cases,
1011 but that seems bogus since it should only be set when we are
1012 sure the register is being used as a pointer. */
1014 rtx arg0 = XEXP (x, 0);
1015 rtx arg1 = XEXP (x, 1);
1016 enum rtx_code code0 = GET_CODE (arg0);
1017 enum rtx_code code1 = GET_CODE (arg1);
1019 /* Look inside subregs. */
1020 if (code0 == SUBREG)
1021 arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
1022 if (code1 == SUBREG)
1023 arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
1025 /* If this machine only allows one register per address, it
1026 must be in the first operand. */
1027 if (MAX_REGS_PER_ADDRESS == 1)
1028 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale);
1030 /* If index and base registers are the same on this machine,
1031 just record registers in any non-constant operands. We
1032 assume here, as well as in the tests below, that all
1033 addresses are in canonical form. */
1034 else if (INDEX_REG_CLASS
1035 == base_reg_class (VOIDmode, as, PLUS, SCRATCH))
1037 record_address_regs (mode, as, arg0, context, PLUS, code1, scale);
1038 if (! CONSTANT_P (arg1))
1039 record_address_regs (mode, as, arg1, context, PLUS, code0, scale);
1042 /* If the second operand is a constant integer, it doesn't
1043 change what class the first operand must be. */
1044 else if (CONST_SCALAR_INT_P (arg1))
1045 record_address_regs (mode, as, arg0, context, PLUS, code1, scale);
1046 /* If the second operand is a symbolic constant, the first
1047 operand must be an index register. */
1048 else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF)
1049 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale);
1050 /* If both operands are registers but one is already a hard
1051 register of index or reg-base class, give the other the
1052 class that the hard register is not. */
1053 else if (code0 == REG && code1 == REG
1054 && REGNO (arg0) < FIRST_PSEUDO_REGISTER
1055 && (ok_for_base_p_nonstrict (arg0, mode, as, PLUS, REG)
1056 || ok_for_index_p_nonstrict (arg0)))
1057 record_address_regs (mode, as, arg1,
1058 ok_for_base_p_nonstrict (arg0, mode, as,
1059 PLUS, REG) ? 1 : 0,
1060 PLUS, REG, scale);
1061 else if (code0 == REG && code1 == REG
1062 && REGNO (arg1) < FIRST_PSEUDO_REGISTER
1063 && (ok_for_base_p_nonstrict (arg1, mode, as, PLUS, REG)
1064 || ok_for_index_p_nonstrict (arg1)))
1065 record_address_regs (mode, as, arg0,
1066 ok_for_base_p_nonstrict (arg1, mode, as,
1067 PLUS, REG) ? 1 : 0,
1068 PLUS, REG, scale);
1069 /* If one operand is known to be a pointer, it must be the
1070 base with the other operand the index. Likewise if the
1071 other operand is a MULT. */
1072 else if ((code0 == REG && REG_POINTER (arg0)) || code1 == MULT)
1074 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale);
1075 record_address_regs (mode, as, arg1, 1, PLUS, code0, scale);
1077 else if ((code1 == REG && REG_POINTER (arg1)) || code0 == MULT)
1079 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale);
1080 record_address_regs (mode, as, arg1, 0, PLUS, code0, scale);
1082 /* Otherwise, count equal chances that each might be a base or
1083 index register. This case should be rare. */
1084 else
1086 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale / 2);
1087 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale / 2);
1088 record_address_regs (mode, as, arg1, 0, PLUS, code0, scale / 2);
1089 record_address_regs (mode, as, arg1, 1, PLUS, code0, scale / 2);
1092 break;
1094 /* Double the importance of an allocno that is incremented or
1095 decremented, since it would take two extra insns if it ends
1096 up in the wrong place. */
1097 case POST_MODIFY:
1098 case PRE_MODIFY:
1099 record_address_regs (mode, as, XEXP (x, 0), 0, code,
1100 GET_CODE (XEXP (XEXP (x, 1), 1)), 2 * scale);
1101 if (REG_P (XEXP (XEXP (x, 1), 1)))
1102 record_address_regs (mode, as, XEXP (XEXP (x, 1), 1), 1, code, REG,
1103 2 * scale);
1104 break;
1106 case POST_INC:
1107 case PRE_INC:
1108 case POST_DEC:
1109 case PRE_DEC:
1110 /* Double the importance of an allocno that is incremented or
1111 decremented, since it would take two extra insns if it ends
1112 up in the wrong place. */
1113 record_address_regs (mode, as, XEXP (x, 0), 0, code, SCRATCH, 2 * scale);
1114 break;
1116 case REG:
1118 struct costs *pp;
1119 int *pp_costs;
1120 enum reg_class i;
1121 int k, regno, add_cost;
1122 cost_classes_t cost_classes_ptr;
1123 enum reg_class *cost_classes;
1124 move_table *move_in_cost;
1126 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
1127 break;
1129 regno = REGNO (x);
1130 if (allocno_p)
1131 ALLOCNO_BAD_SPILL_P (ira_curr_regno_allocno_map[regno]) = true;
1132 pp = COSTS (costs, COST_INDEX (regno));
1133 add_cost = (ira_memory_move_cost[Pmode][rclass][1] * scale) / 2;
1134 if (INT_MAX - add_cost < pp->mem_cost)
1135 pp->mem_cost = INT_MAX;
1136 else
1137 pp->mem_cost += add_cost;
1138 cost_classes_ptr = regno_cost_classes[regno];
1139 cost_classes = cost_classes_ptr->classes;
1140 pp_costs = pp->cost;
1141 ira_init_register_move_cost_if_necessary (Pmode);
1142 move_in_cost = ira_may_move_in_cost[Pmode];
1143 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1145 i = cost_classes[k];
1146 add_cost = (move_in_cost[i][rclass] * scale) / 2;
1147 if (INT_MAX - add_cost < pp_costs[k])
1148 pp_costs[k] = INT_MAX;
1149 else
1150 pp_costs[k] += add_cost;
1153 break;
1155 default:
1157 const char *fmt = GET_RTX_FORMAT (code);
1158 int i;
1159 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1160 if (fmt[i] == 'e')
1161 record_address_regs (mode, as, XEXP (x, i), context, code, SCRATCH,
1162 scale);
1169 /* Calculate the costs of insn operands. */
1170 static void
1171 record_operand_costs (rtx_insn *insn, enum reg_class *pref)
1173 const char *constraints[MAX_RECOG_OPERANDS];
1174 enum machine_mode modes[MAX_RECOG_OPERANDS];
1175 rtx ops[MAX_RECOG_OPERANDS];
1176 rtx set;
1177 int i;
1179 for (i = 0; i < recog_data.n_operands; i++)
1181 constraints[i] = recog_data.constraints[i];
1182 modes[i] = recog_data.operand_mode[i];
1185 /* If we get here, we are set up to record the costs of all the
1186 operands for this insn. Start by initializing the costs. Then
1187 handle any address registers. Finally record the desired classes
1188 for any allocnos, doing it twice if some pair of operands are
1189 commutative. */
1190 for (i = 0; i < recog_data.n_operands; i++)
1192 memcpy (op_costs[i], init_cost, struct_costs_size);
1194 ops[i] = recog_data.operand[i];
1195 if (GET_CODE (recog_data.operand[i]) == SUBREG)
1196 recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);
1198 if (MEM_P (recog_data.operand[i]))
1199 record_address_regs (GET_MODE (recog_data.operand[i]),
1200 MEM_ADDR_SPACE (recog_data.operand[i]),
1201 XEXP (recog_data.operand[i], 0),
1202 0, MEM, SCRATCH, frequency * 2);
1203 else if (constraints[i][0] == 'p'
1204 || (insn_extra_address_constraint
1205 (lookup_constraint (constraints[i]))))
1206 record_address_regs (VOIDmode, ADDR_SPACE_GENERIC,
1207 recog_data.operand[i], 0, ADDRESS, SCRATCH,
1208 frequency * 2);
1211 /* Check for commutative in a separate loop so everything will have
1212 been initialized. We must do this even if one operand is a
1213 constant--see addsi3 in m68k.md. */
1214 for (i = 0; i < (int) recog_data.n_operands - 1; i++)
1215 if (constraints[i][0] == '%')
1217 const char *xconstraints[MAX_RECOG_OPERANDS];
1218 int j;
1220 /* Handle commutative operands by swapping the constraints.
1221 We assume the modes are the same. */
1222 for (j = 0; j < recog_data.n_operands; j++)
1223 xconstraints[j] = constraints[j];
1225 xconstraints[i] = constraints[i+1];
1226 xconstraints[i+1] = constraints[i];
1227 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1228 recog_data.operand, modes,
1229 xconstraints, insn, pref);
1231 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1232 recog_data.operand, modes,
1233 constraints, insn, pref);
1235 /* If this insn is a single set copying operand 1 to operand 0 and
1236 one operand is an allocno with the other a hard reg or an allocno
1237 that prefers a hard register that is in its own register class
1238 then we may want to adjust the cost of that register class to -1.
1240 Avoid the adjustment if the source does not die to avoid
1241 stressing of register allocator by preferrencing two colliding
1242 registers into single class.
1244 Also avoid the adjustment if a copy between hard registers of the
1245 class is expensive (ten times the cost of a default copy is
1246 considered arbitrarily expensive). This avoids losing when the
1247 preferred class is very expensive as the source of a copy
1248 instruction. */
1249 if ((set = single_set (insn)) != NULL_RTX
1250 /* In rare cases the single set insn might have less 2 operands
1251 as the source can be a fixed special reg. */
1252 && recog_data.n_operands > 1
1253 && ops[0] == SET_DEST (set) && ops[1] == SET_SRC (set))
1255 int regno, other_regno;
1256 rtx dest = SET_DEST (set);
1257 rtx src = SET_SRC (set);
1259 dest = SET_DEST (set);
1260 src = SET_SRC (set);
1261 if (GET_CODE (dest) == SUBREG
1262 && (GET_MODE_SIZE (GET_MODE (dest))
1263 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))))
1264 dest = SUBREG_REG (dest);
1265 if (GET_CODE (src) == SUBREG
1266 && (GET_MODE_SIZE (GET_MODE (src))
1267 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
1268 src = SUBREG_REG (src);
1269 if (REG_P (src) && REG_P (dest)
1270 && find_regno_note (insn, REG_DEAD, REGNO (src))
1271 && (((regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
1272 && (other_regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER)
1273 || ((regno = REGNO (dest)) >= FIRST_PSEUDO_REGISTER
1274 && (other_regno = REGNO (src)) < FIRST_PSEUDO_REGISTER)))
1276 enum machine_mode mode = GET_MODE (src);
1277 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1278 enum reg_class *cost_classes = cost_classes_ptr->classes;
1279 reg_class_t rclass;
1280 int k, nr;
1282 i = regno == (int) REGNO (src) ? 1 : 0;
1283 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1285 rclass = cost_classes[k];
1286 if (TEST_HARD_REG_BIT (reg_class_contents[rclass], other_regno)
1287 && (reg_class_size[(int) rclass]
1288 == ira_reg_class_max_nregs [(int) rclass][(int) mode]))
1290 if (reg_class_size[rclass] == 1)
1291 op_costs[i]->cost[k] = -frequency;
1292 else
1294 for (nr = 0;
1295 nr < hard_regno_nregs[other_regno][mode];
1296 nr++)
1297 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass],
1298 other_regno + nr))
1299 break;
1301 if (nr == hard_regno_nregs[other_regno][mode])
1302 op_costs[i]->cost[k] = -frequency;
1312 /* Process one insn INSN. Scan it and record each time it would save
1313 code to put a certain allocnos in a certain class. Return the last
1314 insn processed, so that the scan can be continued from there. */
1315 static rtx_insn *
1316 scan_one_insn (rtx_insn *insn)
1318 enum rtx_code pat_code;
1319 rtx set, note;
1320 int i, k;
1321 bool counted_mem;
1323 if (!NONDEBUG_INSN_P (insn))
1324 return insn;
1326 pat_code = GET_CODE (PATTERN (insn));
1327 if (pat_code == USE || pat_code == CLOBBER || pat_code == ASM_INPUT)
1328 return insn;
1330 counted_mem = false;
1331 set = single_set (insn);
1332 extract_insn (insn);
1334 /* If this insn loads a parameter from its stack slot, then it
1335 represents a savings, rather than a cost, if the parameter is
1336 stored in memory. Record this fact.
1338 Similarly if we're loading other constants from memory (constant
1339 pool, TOC references, small data areas, etc) and this is the only
1340 assignment to the destination pseudo.
1342 Don't do this if SET_SRC (set) isn't a general operand, if it is
1343 a memory requiring special instructions to load it, decreasing
1344 mem_cost might result in it being loaded using the specialized
1345 instruction into a register, then stored into stack and loaded
1346 again from the stack. See PR52208.
1348 Don't do this if SET_SRC (set) has side effect. See PR56124. */
1349 if (set != 0 && REG_P (SET_DEST (set)) && MEM_P (SET_SRC (set))
1350 && (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL_RTX
1351 && ((MEM_P (XEXP (note, 0))
1352 && !side_effects_p (SET_SRC (set)))
1353 || (CONSTANT_P (XEXP (note, 0))
1354 && targetm.legitimate_constant_p (GET_MODE (SET_DEST (set)),
1355 XEXP (note, 0))
1356 && REG_N_SETS (REGNO (SET_DEST (set))) == 1))
1357 && general_operand (SET_SRC (set), GET_MODE (SET_SRC (set))))
1359 enum reg_class cl = GENERAL_REGS;
1360 rtx reg = SET_DEST (set);
1361 int num = COST_INDEX (REGNO (reg));
1363 COSTS (costs, num)->mem_cost
1364 -= ira_memory_move_cost[GET_MODE (reg)][cl][1] * frequency;
1365 record_address_regs (GET_MODE (SET_SRC (set)),
1366 MEM_ADDR_SPACE (SET_SRC (set)),
1367 XEXP (SET_SRC (set), 0), 0, MEM, SCRATCH,
1368 frequency * 2);
1369 counted_mem = true;
1372 record_operand_costs (insn, pref);
1374 /* Now add the cost for each operand to the total costs for its
1375 allocno. */
1376 for (i = 0; i < recog_data.n_operands; i++)
1377 if (REG_P (recog_data.operand[i])
1378 && REGNO (recog_data.operand[i]) >= FIRST_PSEUDO_REGISTER)
1380 int regno = REGNO (recog_data.operand[i]);
1381 struct costs *p = COSTS (costs, COST_INDEX (regno));
1382 struct costs *q = op_costs[i];
1383 int *p_costs = p->cost, *q_costs = q->cost;
1384 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1385 int add_cost;
1387 /* If the already accounted for the memory "cost" above, don't
1388 do so again. */
1389 if (!counted_mem)
1391 add_cost = q->mem_cost;
1392 if (add_cost > 0 && INT_MAX - add_cost < p->mem_cost)
1393 p->mem_cost = INT_MAX;
1394 else
1395 p->mem_cost += add_cost;
1397 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1399 add_cost = q_costs[k];
1400 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1401 p_costs[k] = INT_MAX;
1402 else
1403 p_costs[k] += add_cost;
1407 return insn;
1412 /* Print allocnos costs to file F. */
1413 static void
1414 print_allocno_costs (FILE *f)
1416 int k;
1417 ira_allocno_t a;
1418 ira_allocno_iterator ai;
1420 ira_assert (allocno_p);
1421 fprintf (f, "\n");
1422 FOR_EACH_ALLOCNO (a, ai)
1424 int i, rclass;
1425 basic_block bb;
1426 int regno = ALLOCNO_REGNO (a);
1427 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1428 enum reg_class *cost_classes = cost_classes_ptr->classes;
1430 i = ALLOCNO_NUM (a);
1431 fprintf (f, " a%d(r%d,", i, regno);
1432 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1433 fprintf (f, "b%d", bb->index);
1434 else
1435 fprintf (f, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
1436 fprintf (f, ") costs:");
1437 for (k = 0; k < cost_classes_ptr->num; k++)
1439 rclass = cost_classes[k];
1440 if (contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (regno)]
1441 #ifdef CANNOT_CHANGE_MODE_CLASS
1442 && ! invalid_mode_change_p (regno, (enum reg_class) rclass)
1443 #endif
1446 fprintf (f, " %s:%d", reg_class_names[rclass],
1447 COSTS (costs, i)->cost[k]);
1448 if (flag_ira_region == IRA_REGION_ALL
1449 || flag_ira_region == IRA_REGION_MIXED)
1450 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->cost[k]);
1453 fprintf (f, " MEM:%i", COSTS (costs, i)->mem_cost);
1454 if (flag_ira_region == IRA_REGION_ALL
1455 || flag_ira_region == IRA_REGION_MIXED)
1456 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->mem_cost);
1457 fprintf (f, "\n");
1461 /* Print pseudo costs to file F. */
1462 static void
1463 print_pseudo_costs (FILE *f)
1465 int regno, k;
1466 int rclass;
1467 cost_classes_t cost_classes_ptr;
1468 enum reg_class *cost_classes;
1470 ira_assert (! allocno_p);
1471 fprintf (f, "\n");
1472 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1474 if (REG_N_REFS (regno) <= 0)
1475 continue;
1476 cost_classes_ptr = regno_cost_classes[regno];
1477 cost_classes = cost_classes_ptr->classes;
1478 fprintf (f, " r%d costs:", regno);
1479 for (k = 0; k < cost_classes_ptr->num; k++)
1481 rclass = cost_classes[k];
1482 if (contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (regno)]
1483 #ifdef CANNOT_CHANGE_MODE_CLASS
1484 && ! invalid_mode_change_p (regno, (enum reg_class) rclass)
1485 #endif
1487 fprintf (f, " %s:%d", reg_class_names[rclass],
1488 COSTS (costs, regno)->cost[k]);
1490 fprintf (f, " MEM:%i\n", COSTS (costs, regno)->mem_cost);
1494 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1495 costs. */
1496 static void
1497 process_bb_for_costs (basic_block bb)
1499 rtx_insn *insn;
1501 frequency = REG_FREQ_FROM_BB (bb);
1502 if (frequency == 0)
1503 frequency = 1;
1504 FOR_BB_INSNS (bb, insn)
1505 insn = scan_one_insn (insn);
1508 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1509 costs. */
1510 static void
1511 process_bb_node_for_costs (ira_loop_tree_node_t loop_tree_node)
1513 basic_block bb;
1515 bb = loop_tree_node->bb;
1516 if (bb != NULL)
1517 process_bb_for_costs (bb);
1520 /* Find costs of register classes and memory for allocnos or pseudos
1521 and their best costs. Set up preferred, alternative and allocno
1522 classes for pseudos. */
1523 static void
1524 find_costs_and_classes (FILE *dump_file)
1526 int i, k, start, max_cost_classes_num;
1527 int pass;
1528 basic_block bb;
1529 enum reg_class *regno_best_class;
1531 init_recog ();
1532 regno_best_class
1533 = (enum reg_class *) ira_allocate (max_reg_num ()
1534 * sizeof (enum reg_class));
1535 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1536 regno_best_class[i] = NO_REGS;
1537 if (!resize_reg_info () && allocno_p
1538 && pseudo_classes_defined_p && flag_expensive_optimizations)
1540 ira_allocno_t a;
1541 ira_allocno_iterator ai;
1543 pref = pref_buffer;
1544 max_cost_classes_num = 1;
1545 FOR_EACH_ALLOCNO (a, ai)
1547 pref[ALLOCNO_NUM (a)] = reg_preferred_class (ALLOCNO_REGNO (a));
1548 setup_regno_cost_classes_by_aclass
1549 (ALLOCNO_REGNO (a), pref[ALLOCNO_NUM (a)]);
1550 max_cost_classes_num
1551 = MAX (max_cost_classes_num,
1552 regno_cost_classes[ALLOCNO_REGNO (a)]->num);
1554 start = 1;
1556 else
1558 pref = NULL;
1559 max_cost_classes_num = ira_important_classes_num;
1560 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1561 if (regno_reg_rtx[i] != NULL_RTX)
1562 setup_regno_cost_classes_by_mode (i, PSEUDO_REGNO_MODE (i));
1563 else
1564 setup_regno_cost_classes_by_aclass (i, ALL_REGS);
1565 start = 0;
1567 if (allocno_p)
1568 /* Clear the flag for the next compiled function. */
1569 pseudo_classes_defined_p = false;
1570 /* Normally we scan the insns once and determine the best class to
1571 use for each allocno. However, if -fexpensive-optimizations are
1572 on, we do so twice, the second time using the tentative best
1573 classes to guide the selection. */
1574 for (pass = start; pass <= flag_expensive_optimizations; pass++)
1576 if ((!allocno_p || internal_flag_ira_verbose > 0) && dump_file)
1577 fprintf (dump_file,
1578 "\nPass %i for finding pseudo/allocno costs\n\n", pass);
1580 if (pass != start)
1582 max_cost_classes_num = 1;
1583 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1585 setup_regno_cost_classes_by_aclass (i, regno_best_class[i]);
1586 max_cost_classes_num
1587 = MAX (max_cost_classes_num, regno_cost_classes[i]->num);
1591 struct_costs_size
1592 = sizeof (struct costs) + sizeof (int) * (max_cost_classes_num - 1);
1593 /* Zero out our accumulation of the cost of each class for each
1594 allocno. */
1595 memset (costs, 0, cost_elements_num * struct_costs_size);
1597 if (allocno_p)
1599 /* Scan the instructions and record each time it would save code
1600 to put a certain allocno in a certain class. */
1601 ira_traverse_loop_tree (true, ira_loop_tree_root,
1602 process_bb_node_for_costs, NULL);
1604 memcpy (total_allocno_costs, costs,
1605 max_struct_costs_size * ira_allocnos_num);
1607 else
1609 basic_block bb;
1611 FOR_EACH_BB_FN (bb, cfun)
1612 process_bb_for_costs (bb);
1615 if (pass == 0)
1616 pref = pref_buffer;
1618 /* Now for each allocno look at how desirable each class is and
1619 find which class is preferred. */
1620 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1622 ira_allocno_t a, parent_a;
1623 int rclass, a_num, parent_a_num, add_cost;
1624 ira_loop_tree_node_t parent;
1625 int best_cost, allocno_cost;
1626 enum reg_class best, alt_class;
1627 cost_classes_t cost_classes_ptr = regno_cost_classes[i];
1628 enum reg_class *cost_classes = cost_classes_ptr->classes;
1629 int *i_costs = temp_costs->cost;
1630 int i_mem_cost;
1631 int equiv_savings = regno_equiv_gains[i];
1633 if (! allocno_p)
1635 if (regno_reg_rtx[i] == NULL_RTX)
1636 continue;
1637 memcpy (temp_costs, COSTS (costs, i), struct_costs_size);
1638 i_mem_cost = temp_costs->mem_cost;
1640 else
1642 if (ira_regno_allocno_map[i] == NULL)
1643 continue;
1644 memset (temp_costs, 0, struct_costs_size);
1645 i_mem_cost = 0;
1646 /* Find cost of all allocnos with the same regno. */
1647 for (a = ira_regno_allocno_map[i];
1648 a != NULL;
1649 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1651 int *a_costs, *p_costs;
1653 a_num = ALLOCNO_NUM (a);
1654 if ((flag_ira_region == IRA_REGION_ALL
1655 || flag_ira_region == IRA_REGION_MIXED)
1656 && (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1657 && (parent_a = parent->regno_allocno_map[i]) != NULL
1658 /* There are no caps yet. */
1659 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE
1660 (a)->border_allocnos,
1661 ALLOCNO_NUM (a)))
1663 /* Propagate costs to upper levels in the region
1664 tree. */
1665 parent_a_num = ALLOCNO_NUM (parent_a);
1666 a_costs = COSTS (total_allocno_costs, a_num)->cost;
1667 p_costs = COSTS (total_allocno_costs, parent_a_num)->cost;
1668 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1670 add_cost = a_costs[k];
1671 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1672 p_costs[k] = INT_MAX;
1673 else
1674 p_costs[k] += add_cost;
1676 add_cost = COSTS (total_allocno_costs, a_num)->mem_cost;
1677 if (add_cost > 0
1678 && (INT_MAX - add_cost
1679 < COSTS (total_allocno_costs,
1680 parent_a_num)->mem_cost))
1681 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1682 = INT_MAX;
1683 else
1684 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1685 += add_cost;
1687 if (i >= first_moveable_pseudo && i < last_moveable_pseudo)
1688 COSTS (total_allocno_costs, parent_a_num)->mem_cost = 0;
1690 a_costs = COSTS (costs, a_num)->cost;
1691 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1693 add_cost = a_costs[k];
1694 if (add_cost > 0 && INT_MAX - add_cost < i_costs[k])
1695 i_costs[k] = INT_MAX;
1696 else
1697 i_costs[k] += add_cost;
1699 add_cost = COSTS (costs, a_num)->mem_cost;
1700 if (add_cost > 0 && INT_MAX - add_cost < i_mem_cost)
1701 i_mem_cost = INT_MAX;
1702 else
1703 i_mem_cost += add_cost;
1706 if (i >= first_moveable_pseudo && i < last_moveable_pseudo)
1707 i_mem_cost = 0;
1708 else if (equiv_savings < 0)
1709 i_mem_cost = -equiv_savings;
1710 else if (equiv_savings > 0)
1712 i_mem_cost = 0;
1713 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1714 i_costs[k] += equiv_savings;
1717 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1718 best = ALL_REGS;
1719 alt_class = NO_REGS;
1720 /* Find best common class for all allocnos with the same
1721 regno. */
1722 for (k = 0; k < cost_classes_ptr->num; k++)
1724 rclass = cost_classes[k];
1725 /* Ignore classes that are too small or invalid for this
1726 operand. */
1727 if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)]
1728 #ifdef CANNOT_CHANGE_MODE_CLASS
1729 || invalid_mode_change_p (i, (enum reg_class) rclass)
1730 #endif
1732 continue;
1733 if (i_costs[k] < best_cost)
1735 best_cost = i_costs[k];
1736 best = (enum reg_class) rclass;
1738 else if (i_costs[k] == best_cost)
1739 best = ira_reg_class_subunion[best][rclass];
1740 if (pass == flag_expensive_optimizations
1741 /* We still prefer registers to memory even at this
1742 stage if their costs are the same. We will make
1743 a final decision during assigning hard registers
1744 when we have all info including more accurate
1745 costs which might be affected by assigning hard
1746 registers to other pseudos because the pseudos
1747 involved in moves can be coalesced. */
1748 && i_costs[k] <= i_mem_cost
1749 && (reg_class_size[reg_class_subunion[alt_class][rclass]]
1750 > reg_class_size[alt_class]))
1751 alt_class = reg_class_subunion[alt_class][rclass];
1753 alt_class = ira_allocno_class_translate[alt_class];
1754 if (best_cost > i_mem_cost)
1755 regno_aclass[i] = NO_REGS;
1756 else if (!optimize && !targetm.class_likely_spilled_p (best))
1757 /* Registers in the alternative class are likely to need
1758 longer or slower sequences than registers in the best class.
1759 When optimizing we make some effort to use the best class
1760 over the alternative class where possible, but at -O0 we
1761 effectively give the alternative class equal weight.
1762 We then run the risk of using slower alternative registers
1763 when plenty of registers from the best class are still free.
1764 This is especially true because live ranges tend to be very
1765 short in -O0 code and so register pressure tends to be low.
1767 Avoid that by ignoring the alternative class if the best
1768 class has plenty of registers. */
1769 regno_aclass[i] = best;
1770 else
1772 /* Make the common class the biggest class of best and
1773 alt_class. */
1774 regno_aclass[i]
1775 = ira_reg_class_superunion[best][alt_class];
1776 ira_assert (regno_aclass[i] != NO_REGS
1777 && ira_reg_allocno_class_p[regno_aclass[i]]);
1779 if (pass == flag_expensive_optimizations)
1781 if (best_cost > i_mem_cost)
1782 best = alt_class = NO_REGS;
1783 else if (best == alt_class)
1784 alt_class = NO_REGS;
1785 setup_reg_classes (i, best, alt_class, regno_aclass[i]);
1786 if ((!allocno_p || internal_flag_ira_verbose > 2)
1787 && dump_file != NULL)
1788 fprintf (dump_file,
1789 " r%d: preferred %s, alternative %s, allocno %s\n",
1790 i, reg_class_names[best], reg_class_names[alt_class],
1791 reg_class_names[regno_aclass[i]]);
1793 regno_best_class[i] = best;
1794 if (! allocno_p)
1796 pref[i] = best_cost > i_mem_cost ? NO_REGS : best;
1797 continue;
1799 for (a = ira_regno_allocno_map[i];
1800 a != NULL;
1801 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1803 enum reg_class aclass = regno_aclass[i];
1804 int a_num = ALLOCNO_NUM (a);
1805 int *total_a_costs = COSTS (total_allocno_costs, a_num)->cost;
1806 int *a_costs = COSTS (costs, a_num)->cost;
1808 if (aclass == NO_REGS)
1809 best = NO_REGS;
1810 else
1812 /* Finding best class which is subset of the common
1813 class. */
1814 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1815 allocno_cost = best_cost;
1816 best = ALL_REGS;
1817 for (k = 0; k < cost_classes_ptr->num; k++)
1819 rclass = cost_classes[k];
1820 if (! ira_class_subset_p[rclass][aclass])
1821 continue;
1822 /* Ignore classes that are too small or invalid
1823 for this operand. */
1824 if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)]
1825 #ifdef CANNOT_CHANGE_MODE_CLASS
1826 || invalid_mode_change_p (i, (enum reg_class) rclass)
1827 #endif
1830 else if (total_a_costs[k] < best_cost)
1832 best_cost = total_a_costs[k];
1833 allocno_cost = a_costs[k];
1834 best = (enum reg_class) rclass;
1836 else if (total_a_costs[k] == best_cost)
1838 best = ira_reg_class_subunion[best][rclass];
1839 allocno_cost = MAX (allocno_cost, a_costs[k]);
1842 ALLOCNO_CLASS_COST (a) = allocno_cost;
1844 if (internal_flag_ira_verbose > 2 && dump_file != NULL
1845 && (pass == 0 || pref[a_num] != best))
1847 fprintf (dump_file, " a%d (r%d,", a_num, i);
1848 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1849 fprintf (dump_file, "b%d", bb->index);
1850 else
1851 fprintf (dump_file, "l%d",
1852 ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
1853 fprintf (dump_file, ") best %s, allocno %s\n",
1854 reg_class_names[best],
1855 reg_class_names[aclass]);
1857 pref[a_num] = best;
1858 if (pass == flag_expensive_optimizations && best != aclass
1859 && ira_class_hard_regs_num[best] > 0
1860 && (ira_reg_class_max_nregs[best][ALLOCNO_MODE (a)]
1861 >= ira_class_hard_regs_num[best]))
1863 int ind = cost_classes_ptr->index[aclass];
1865 ira_assert (ind >= 0);
1866 ira_init_register_move_cost_if_necessary (ALLOCNO_MODE (a));
1867 ira_add_allocno_pref (a, ira_class_hard_regs[best][0],
1868 (a_costs[ind] - ALLOCNO_CLASS_COST (a))
1869 / (ira_register_move_cost
1870 [ALLOCNO_MODE (a)][best][aclass]));
1871 for (k = 0; k < cost_classes_ptr->num; k++)
1872 if (ira_class_subset_p[cost_classes[k]][best])
1873 a_costs[k] = a_costs[ind];
1878 if (internal_flag_ira_verbose > 4 && dump_file)
1880 if (allocno_p)
1881 print_allocno_costs (dump_file);
1882 else
1883 print_pseudo_costs (dump_file);
1884 fprintf (dump_file,"\n");
1887 ira_free (regno_best_class);
1892 /* Process moves involving hard regs to modify allocno hard register
1893 costs. We can do this only after determining allocno class. If a
1894 hard register forms a register class, then moves with the hard
1895 register are already taken into account in class costs for the
1896 allocno. */
1897 static void
1898 process_bb_node_for_hard_reg_moves (ira_loop_tree_node_t loop_tree_node)
1900 int i, freq, src_regno, dst_regno, hard_regno, a_regno;
1901 bool to_p;
1902 ira_allocno_t a, curr_a;
1903 ira_loop_tree_node_t curr_loop_tree_node;
1904 enum reg_class rclass;
1905 basic_block bb;
1906 rtx_insn *insn;
1907 rtx set, src, dst;
1909 bb = loop_tree_node->bb;
1910 if (bb == NULL)
1911 return;
1912 freq = REG_FREQ_FROM_BB (bb);
1913 if (freq == 0)
1914 freq = 1;
1915 FOR_BB_INSNS (bb, insn)
1917 if (!NONDEBUG_INSN_P (insn))
1918 continue;
1919 set = single_set (insn);
1920 if (set == NULL_RTX)
1921 continue;
1922 dst = SET_DEST (set);
1923 src = SET_SRC (set);
1924 if (! REG_P (dst) || ! REG_P (src))
1925 continue;
1926 dst_regno = REGNO (dst);
1927 src_regno = REGNO (src);
1928 if (dst_regno >= FIRST_PSEUDO_REGISTER
1929 && src_regno < FIRST_PSEUDO_REGISTER)
1931 hard_regno = src_regno;
1932 a = ira_curr_regno_allocno_map[dst_regno];
1933 to_p = true;
1935 else if (src_regno >= FIRST_PSEUDO_REGISTER
1936 && dst_regno < FIRST_PSEUDO_REGISTER)
1938 hard_regno = dst_regno;
1939 a = ira_curr_regno_allocno_map[src_regno];
1940 to_p = false;
1942 else
1943 continue;
1944 rclass = ALLOCNO_CLASS (a);
1945 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass], hard_regno))
1946 continue;
1947 i = ira_class_hard_reg_index[rclass][hard_regno];
1948 if (i < 0)
1949 continue;
1950 a_regno = ALLOCNO_REGNO (a);
1951 for (curr_loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
1952 curr_loop_tree_node != NULL;
1953 curr_loop_tree_node = curr_loop_tree_node->parent)
1954 if ((curr_a = curr_loop_tree_node->regno_allocno_map[a_regno]) != NULL)
1955 ira_add_allocno_pref (curr_a, hard_regno, freq);
1957 int cost;
1958 enum reg_class hard_reg_class;
1959 enum machine_mode mode;
1961 mode = ALLOCNO_MODE (a);
1962 hard_reg_class = REGNO_REG_CLASS (hard_regno);
1963 ira_init_register_move_cost_if_necessary (mode);
1964 cost = (to_p ? ira_register_move_cost[mode][hard_reg_class][rclass]
1965 : ira_register_move_cost[mode][rclass][hard_reg_class]) * freq;
1966 ira_allocate_and_set_costs (&ALLOCNO_HARD_REG_COSTS (a), rclass,
1967 ALLOCNO_CLASS_COST (a));
1968 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
1969 rclass, 0);
1970 ALLOCNO_HARD_REG_COSTS (a)[i] -= cost;
1971 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[i] -= cost;
1972 ALLOCNO_CLASS_COST (a) = MIN (ALLOCNO_CLASS_COST (a),
1973 ALLOCNO_HARD_REG_COSTS (a)[i]);
1978 /* After we find hard register and memory costs for allocnos, define
1979 its class and modify hard register cost because insns moving
1980 allocno to/from hard registers. */
1981 static void
1982 setup_allocno_class_and_costs (void)
1984 int i, j, n, regno, hard_regno, num;
1985 int *reg_costs;
1986 enum reg_class aclass, rclass;
1987 ira_allocno_t a;
1988 ira_allocno_iterator ai;
1989 cost_classes_t cost_classes_ptr;
1991 ira_assert (allocno_p);
1992 FOR_EACH_ALLOCNO (a, ai)
1994 i = ALLOCNO_NUM (a);
1995 regno = ALLOCNO_REGNO (a);
1996 aclass = regno_aclass[regno];
1997 cost_classes_ptr = regno_cost_classes[regno];
1998 ira_assert (pref[i] == NO_REGS || aclass != NO_REGS);
1999 ALLOCNO_MEMORY_COST (a) = COSTS (costs, i)->mem_cost;
2000 ira_set_allocno_class (a, aclass);
2001 if (aclass == NO_REGS)
2002 continue;
2003 if (optimize && ALLOCNO_CLASS (a) != pref[i])
2005 n = ira_class_hard_regs_num[aclass];
2006 ALLOCNO_HARD_REG_COSTS (a)
2007 = reg_costs = ira_allocate_cost_vector (aclass);
2008 for (j = n - 1; j >= 0; j--)
2010 hard_regno = ira_class_hard_regs[aclass][j];
2011 if (TEST_HARD_REG_BIT (reg_class_contents[pref[i]], hard_regno))
2012 reg_costs[j] = ALLOCNO_CLASS_COST (a);
2013 else
2015 rclass = REGNO_REG_CLASS (hard_regno);
2016 num = cost_classes_ptr->index[rclass];
2017 if (num < 0)
2019 num = cost_classes_ptr->hard_regno_index[hard_regno];
2020 ira_assert (num >= 0);
2022 reg_costs[j] = COSTS (costs, i)->cost[num];
2027 if (optimize)
2028 ira_traverse_loop_tree (true, ira_loop_tree_root,
2029 process_bb_node_for_hard_reg_moves, NULL);
2034 /* Function called once during compiler work. */
2035 void
2036 ira_init_costs_once (void)
2038 int i;
2040 init_cost = NULL;
2041 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2043 op_costs[i] = NULL;
2044 this_op_costs[i] = NULL;
2046 temp_costs = NULL;
2049 /* Free allocated temporary cost vectors. */
2050 static void
2051 free_ira_costs (void)
2053 int i;
2055 free (init_cost);
2056 init_cost = NULL;
2057 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2059 free (op_costs[i]);
2060 free (this_op_costs[i]);
2061 op_costs[i] = this_op_costs[i] = NULL;
2063 free (temp_costs);
2064 temp_costs = NULL;
2067 /* This is called each time register related information is
2068 changed. */
2069 void
2070 ira_init_costs (void)
2072 int i;
2074 free_ira_costs ();
2075 max_struct_costs_size
2076 = sizeof (struct costs) + sizeof (int) * (ira_important_classes_num - 1);
2077 /* Don't use ira_allocate because vectors live through several IRA
2078 calls. */
2079 init_cost = (struct costs *) xmalloc (max_struct_costs_size);
2080 init_cost->mem_cost = 1000000;
2081 for (i = 0; i < ira_important_classes_num; i++)
2082 init_cost->cost[i] = 1000000;
2083 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2085 op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
2086 this_op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
2088 temp_costs = (struct costs *) xmalloc (max_struct_costs_size);
2091 /* Function called once at the end of compiler work. */
2092 void
2093 ira_finish_costs_once (void)
2095 free_ira_costs ();
2100 /* Common initialization function for ira_costs and
2101 ira_set_pseudo_classes. */
2102 static void
2103 init_costs (void)
2105 init_subregs_of_mode ();
2106 costs = (struct costs *) ira_allocate (max_struct_costs_size
2107 * cost_elements_num);
2108 pref_buffer = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
2109 * cost_elements_num);
2110 regno_aclass = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
2111 * max_reg_num ());
2112 regno_equiv_gains = (int *) ira_allocate (sizeof (int) * max_reg_num ());
2113 memset (regno_equiv_gains, 0, sizeof (int) * max_reg_num ());
2116 /* Common finalization function for ira_costs and
2117 ira_set_pseudo_classes. */
2118 static void
2119 finish_costs (void)
2121 finish_subregs_of_mode ();
2122 ira_free (regno_equiv_gains);
2123 ira_free (regno_aclass);
2124 ira_free (pref_buffer);
2125 ira_free (costs);
2128 /* Entry function which defines register class, memory and hard
2129 register costs for each allocno. */
2130 void
2131 ira_costs (void)
2133 allocno_p = true;
2134 cost_elements_num = ira_allocnos_num;
2135 init_costs ();
2136 total_allocno_costs = (struct costs *) ira_allocate (max_struct_costs_size
2137 * ira_allocnos_num);
2138 initiate_regno_cost_classes ();
2139 calculate_elim_costs_all_insns ();
2140 find_costs_and_classes (ira_dump_file);
2141 setup_allocno_class_and_costs ();
2142 finish_regno_cost_classes ();
2143 finish_costs ();
2144 ira_free (total_allocno_costs);
2147 /* Entry function which defines classes for pseudos.
2148 Set pseudo_classes_defined_p only if DEFINE_PSEUDO_CLASSES is true. */
2149 void
2150 ira_set_pseudo_classes (bool define_pseudo_classes, FILE *dump_file)
2152 allocno_p = false;
2153 internal_flag_ira_verbose = flag_ira_verbose;
2154 cost_elements_num = max_reg_num ();
2155 init_costs ();
2156 initiate_regno_cost_classes ();
2157 find_costs_and_classes (dump_file);
2158 finish_regno_cost_classes ();
2159 if (define_pseudo_classes)
2160 pseudo_classes_defined_p = true;
2162 finish_costs ();
2167 /* Change hard register costs for allocnos which lives through
2168 function calls. This is called only when we found all intersected
2169 calls during building allocno live ranges. */
2170 void
2171 ira_tune_allocno_costs (void)
2173 int j, n, regno;
2174 int cost, min_cost, *reg_costs;
2175 enum reg_class aclass, rclass;
2176 enum machine_mode mode;
2177 ira_allocno_t a;
2178 ira_allocno_iterator ai;
2179 ira_allocno_object_iterator oi;
2180 ira_object_t obj;
2181 bool skip_p;
2182 HARD_REG_SET *crossed_calls_clobber_regs;
2184 FOR_EACH_ALLOCNO (a, ai)
2186 aclass = ALLOCNO_CLASS (a);
2187 if (aclass == NO_REGS)
2188 continue;
2189 mode = ALLOCNO_MODE (a);
2190 n = ira_class_hard_regs_num[aclass];
2191 min_cost = INT_MAX;
2192 if (ALLOCNO_CALLS_CROSSED_NUM (a)
2193 != ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2195 ira_allocate_and_set_costs
2196 (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2197 ALLOCNO_CLASS_COST (a));
2198 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2199 for (j = n - 1; j >= 0; j--)
2201 regno = ira_class_hard_regs[aclass][j];
2202 skip_p = false;
2203 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2205 if (ira_hard_reg_set_intersection_p (regno, mode,
2206 OBJECT_CONFLICT_HARD_REGS
2207 (obj)))
2209 skip_p = true;
2210 break;
2213 if (skip_p)
2214 continue;
2215 rclass = REGNO_REG_CLASS (regno);
2216 cost = 0;
2217 crossed_calls_clobber_regs
2218 = &(ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
2219 if (ira_hard_reg_set_intersection_p (regno, mode,
2220 *crossed_calls_clobber_regs))
2222 if (ira_hard_reg_set_intersection_p (regno, mode,
2223 call_used_reg_set)
2224 || HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
2225 cost += (ALLOCNO_CALL_FREQ (a)
2226 * (ira_memory_move_cost[mode][rclass][0]
2227 + ira_memory_move_cost[mode][rclass][1]));
2228 #ifdef IRA_HARD_REGNO_ADD_COST_MULTIPLIER
2229 cost += ((ira_memory_move_cost[mode][rclass][0]
2230 + ira_memory_move_cost[mode][rclass][1])
2231 * ALLOCNO_FREQ (a)
2232 * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno) / 2);
2233 #endif
2235 if (INT_MAX - cost < reg_costs[j])
2236 reg_costs[j] = INT_MAX;
2237 else
2238 reg_costs[j] += cost;
2239 if (min_cost > reg_costs[j])
2240 min_cost = reg_costs[j];
2243 if (min_cost != INT_MAX)
2244 ALLOCNO_CLASS_COST (a) = min_cost;
2246 /* Some targets allow pseudos to be allocated to unaligned sequences
2247 of hard registers. However, selecting an unaligned sequence can
2248 unnecessarily restrict later allocations. So increase the cost of
2249 unaligned hard regs to encourage the use of aligned hard regs. */
2251 const int nregs = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2253 if (nregs > 1)
2255 ira_allocate_and_set_costs
2256 (&ALLOCNO_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a));
2257 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2258 for (j = n - 1; j >= 0; j--)
2260 regno = ira_non_ordered_class_hard_regs[aclass][j];
2261 if ((regno % nregs) != 0)
2263 int index = ira_class_hard_reg_index[aclass][regno];
2264 ira_assert (index != -1);
2265 reg_costs[index] += ALLOCNO_FREQ (a);
2273 /* Add COST to the estimated gain for eliminating REGNO with its
2274 equivalence. If COST is zero, record that no such elimination is
2275 possible. */
2277 void
2278 ira_adjust_equiv_reg_cost (unsigned regno, int cost)
2280 if (cost == 0)
2281 regno_equiv_gains[regno] = 0;
2282 else
2283 regno_equiv_gains[regno] += cost;