Fix up CL.
[official-gcc.git] / gcc / ira-costs.c
blobd7299e658d713e87b41c65b68fd32ba555b46292
1 /* IRA hard register and memory cost calculation for allocnos or pseudos.
2 Copyright (C) 2006-2013 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 && memcmp (hv1->classes, hv2->classes,
158 sizeof (enum reg_class) * hv1->num);
161 /* Delete cost classes info V from the hash table. */
162 inline void
163 cost_classes_hasher::remove (value_type *v)
165 ira_free (v);
168 /* Hash table of unique cost classes. */
169 static hash_table <cost_classes_hasher> cost_classes_htab;
171 /* Map allocno class -> cost classes for pseudo of given allocno
172 class. */
173 static cost_classes_t cost_classes_aclass_cache[N_REG_CLASSES];
175 /* Map mode -> cost classes for pseudo of give mode. */
176 static cost_classes_t cost_classes_mode_cache[MAX_MACHINE_MODE];
178 /* Initialize info about the cost classes for each pseudo. */
179 static void
180 initiate_regno_cost_classes (void)
182 int size = sizeof (cost_classes_t) * max_reg_num ();
184 regno_cost_classes = (cost_classes_t *) ira_allocate (size);
185 memset (regno_cost_classes, 0, size);
186 memset (cost_classes_aclass_cache, 0,
187 sizeof (cost_classes_t) * N_REG_CLASSES);
188 memset (cost_classes_mode_cache, 0,
189 sizeof (cost_classes_t) * MAX_MACHINE_MODE);
190 cost_classes_htab.create (200);
193 /* Create new cost classes from cost classes FROM and set up members
194 index and hard_regno_index. Return the new classes. The function
195 implements some common code of two functions
196 setup_regno_cost_classes_by_aclass and
197 setup_regno_cost_classes_by_mode. */
198 static cost_classes_t
199 setup_cost_classes (cost_classes_t from)
201 cost_classes_t classes_ptr;
202 enum reg_class cl;
203 int i, j, hard_regno;
205 classes_ptr = (cost_classes_t) ira_allocate (sizeof (struct cost_classes));
206 classes_ptr->num = from->num;
207 for (i = 0; i < N_REG_CLASSES; i++)
208 classes_ptr->index[i] = -1;
209 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
210 classes_ptr->hard_regno_index[i] = -1;
211 for (i = 0; i < from->num; i++)
213 cl = classes_ptr->classes[i] = from->classes[i];
214 classes_ptr->index[cl] = i;
215 for (j = ira_class_hard_regs_num[cl] - 1; j >= 0; j--)
217 hard_regno = ira_class_hard_regs[cl][j];
218 if (classes_ptr->hard_regno_index[hard_regno] < 0)
219 classes_ptr->hard_regno_index[hard_regno] = i;
222 return classes_ptr;
225 /* Setup cost classes for pseudo REGNO whose allocno class is ACLASS.
226 This function is used when we know an initial approximation of
227 allocno class of the pseudo already, e.g. on the second iteration
228 of class cost calculation or after class cost calculation in
229 register-pressure sensitive insn scheduling or register-pressure
230 sensitive loop-invariant motion. */
231 static void
232 setup_regno_cost_classes_by_aclass (int regno, enum reg_class aclass)
234 static struct cost_classes classes;
235 cost_classes_t classes_ptr;
236 enum reg_class cl;
237 int i;
238 cost_classes **slot;
239 HARD_REG_SET temp, temp2;
240 bool exclude_p;
242 if ((classes_ptr = cost_classes_aclass_cache[aclass]) == NULL)
244 COPY_HARD_REG_SET (temp, reg_class_contents[aclass]);
245 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
246 /* We exclude classes from consideration which are subsets of
247 ACLASS only if ACLASS is an uniform class. */
248 exclude_p = ira_uniform_class_p[aclass];
249 classes.num = 0;
250 for (i = 0; i < ira_important_classes_num; i++)
252 cl = ira_important_classes[i];
253 if (exclude_p)
255 /* Exclude non-uniform classes which are subsets of
256 ACLASS. */
257 COPY_HARD_REG_SET (temp2, reg_class_contents[cl]);
258 AND_COMPL_HARD_REG_SET (temp2, ira_no_alloc_regs);
259 if (hard_reg_set_subset_p (temp2, temp) && cl != aclass)
260 continue;
262 classes.classes[classes.num++] = cl;
264 slot = cost_classes_htab.find_slot (&classes, INSERT);
265 if (*slot == NULL)
267 classes_ptr = setup_cost_classes (&classes);
268 *slot = classes_ptr;
270 classes_ptr = cost_classes_aclass_cache[aclass] = (cost_classes_t) *slot;
272 regno_cost_classes[regno] = classes_ptr;
275 /* Setup cost classes for pseudo REGNO with MODE. Usage of MODE can
276 decrease number of cost classes for the pseudo, if hard registers
277 of some important classes can not hold a value of MODE. So the
278 pseudo can not get hard register of some important classes and cost
279 calculation for such important classes is only waisting CPU
280 time. */
281 static void
282 setup_regno_cost_classes_by_mode (int regno, enum machine_mode mode)
284 static struct cost_classes classes;
285 cost_classes_t classes_ptr;
286 enum reg_class cl;
287 int i;
288 cost_classes **slot;
289 HARD_REG_SET temp;
291 if ((classes_ptr = cost_classes_mode_cache[mode]) == NULL)
293 classes.num = 0;
294 for (i = 0; i < ira_important_classes_num; i++)
296 cl = ira_important_classes[i];
297 COPY_HARD_REG_SET (temp, ira_prohibited_class_mode_regs[cl][mode]);
298 IOR_HARD_REG_SET (temp, ira_no_alloc_regs);
299 if (hard_reg_set_subset_p (reg_class_contents[cl], temp))
300 continue;
301 classes.classes[classes.num++] = cl;
303 slot = cost_classes_htab.find_slot (&classes, INSERT);
304 if (*slot == NULL)
306 classes_ptr = setup_cost_classes (&classes);
307 *slot = classes_ptr;
309 else
310 classes_ptr = (cost_classes_t) *slot;
311 cost_classes_mode_cache[mode] = (cost_classes_t) *slot;
313 regno_cost_classes[regno] = classes_ptr;
316 /* Finilize info about the cost classes for each pseudo. */
317 static void
318 finish_regno_cost_classes (void)
320 ira_free (regno_cost_classes);
321 cost_classes_htab.dispose ();
326 /* Compute the cost of loading X into (if TO_P is TRUE) or from (if
327 TO_P is FALSE) a register of class RCLASS in mode MODE. X must not
328 be a pseudo register. */
329 static int
330 copy_cost (rtx x, enum machine_mode mode, reg_class_t rclass, bool to_p,
331 secondary_reload_info *prev_sri)
333 secondary_reload_info sri;
334 reg_class_t secondary_class = NO_REGS;
336 /* If X is a SCRATCH, there is actually nothing to move since we are
337 assuming optimal allocation. */
338 if (GET_CODE (x) == SCRATCH)
339 return 0;
341 /* Get the class we will actually use for a reload. */
342 rclass = targetm.preferred_reload_class (x, rclass);
344 /* If we need a secondary reload for an intermediate, the cost is
345 that to load the input into the intermediate register, then to
346 copy it. */
347 sri.prev_sri = prev_sri;
348 sri.extra_cost = 0;
349 secondary_class = targetm.secondary_reload (to_p, x, rclass, mode, &sri);
351 if (secondary_class != NO_REGS)
353 ira_init_register_move_cost_if_necessary (mode);
354 return (ira_register_move_cost[mode][(int) secondary_class][(int) rclass]
355 + sri.extra_cost
356 + copy_cost (x, mode, secondary_class, to_p, &sri));
359 /* For memory, use the memory move cost, for (hard) registers, use
360 the cost to move between the register classes, and use 2 for
361 everything else (constants). */
362 if (MEM_P (x) || rclass == NO_REGS)
363 return sri.extra_cost
364 + ira_memory_move_cost[mode][(int) rclass][to_p != 0];
365 else if (REG_P (x))
367 reg_class_t x_class = REGNO_REG_CLASS (REGNO (x));
369 ira_init_register_move_cost_if_necessary (mode);
370 return (sri.extra_cost
371 + ira_register_move_cost[mode][(int) x_class][(int) rclass]);
373 else
374 /* If this is a constant, we may eventually want to call rtx_cost
375 here. */
376 return sri.extra_cost + COSTS_N_INSNS (1);
381 /* Record the cost of using memory or hard registers of various
382 classes for the operands in INSN.
384 N_ALTS is the number of alternatives.
385 N_OPS is the number of operands.
386 OPS is an array of the operands.
387 MODES are the modes of the operands, in case any are VOIDmode.
388 CONSTRAINTS are the constraints to use for the operands. This array
389 is modified by this procedure.
391 This procedure works alternative by alternative. For each
392 alternative we assume that we will be able to allocate all allocnos
393 to their ideal register class and calculate the cost of using that
394 alternative. Then we compute, for each operand that is a
395 pseudo-register, the cost of having the allocno allocated to each
396 register class and using it in that alternative. To this cost is
397 added the cost of the alternative.
399 The cost of each class for this insn is its lowest cost among all
400 the alternatives. */
401 static void
402 record_reg_classes (int n_alts, int n_ops, rtx *ops,
403 enum machine_mode *modes, const char **constraints,
404 rtx insn, enum reg_class *pref)
406 int alt;
407 int i, j, k;
408 int insn_allows_mem[MAX_RECOG_OPERANDS];
410 for (i = 0; i < n_ops; i++)
411 insn_allows_mem[i] = 0;
413 /* Process each alternative, each time minimizing an operand's cost
414 with the cost for each operand in that alternative. */
415 for (alt = 0; alt < n_alts; alt++)
417 enum reg_class classes[MAX_RECOG_OPERANDS];
418 int allows_mem[MAX_RECOG_OPERANDS];
419 enum reg_class rclass;
420 int alt_fail = 0;
421 int alt_cost = 0, op_cost_add;
423 if (!recog_data.alternative_enabled_p[alt])
425 for (i = 0; i < recog_data.n_operands; i++)
426 constraints[i] = skip_alternative (constraints[i]);
428 continue;
431 for (i = 0; i < n_ops; i++)
433 unsigned char c;
434 const char *p = constraints[i];
435 rtx op = ops[i];
436 enum machine_mode mode = modes[i];
437 int allows_addr = 0;
438 int win = 0;
440 /* Initially show we know nothing about the register class. */
441 classes[i] = NO_REGS;
442 allows_mem[i] = 0;
444 /* If this operand has no constraints at all, we can
445 conclude nothing about it since anything is valid. */
446 if (*p == 0)
448 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
449 memset (this_op_costs[i], 0, struct_costs_size);
450 continue;
453 /* If this alternative is only relevant when this operand
454 matches a previous operand, we do different things
455 depending on whether this operand is a allocno-reg or not.
456 We must process any modifiers for the operand before we
457 can make this test. */
458 while (*p == '%' || *p == '=' || *p == '+' || *p == '&')
459 p++;
461 if (p[0] >= '0' && p[0] <= '0' + i && (p[1] == ',' || p[1] == 0))
463 /* Copy class and whether memory is allowed from the
464 matching alternative. Then perform any needed cost
465 computations and/or adjustments. */
466 j = p[0] - '0';
467 classes[i] = classes[j];
468 allows_mem[i] = allows_mem[j];
469 if (allows_mem[i])
470 insn_allows_mem[i] = 1;
472 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
474 /* If this matches the other operand, we have no
475 added cost and we win. */
476 if (rtx_equal_p (ops[j], op))
477 win = 1;
478 /* If we can put the other operand into a register,
479 add to the cost of this alternative the cost to
480 copy this operand to the register used for the
481 other operand. */
482 else if (classes[j] != NO_REGS)
484 alt_cost += copy_cost (op, mode, classes[j], 1, NULL);
485 win = 1;
488 else if (! REG_P (ops[j])
489 || REGNO (ops[j]) < FIRST_PSEUDO_REGISTER)
491 /* This op is an allocno but the one it matches is
492 not. */
494 /* If we can't put the other operand into a
495 register, this alternative can't be used. */
497 if (classes[j] == NO_REGS)
498 alt_fail = 1;
499 /* Otherwise, add to the cost of this alternative
500 the cost to copy the other operand to the hard
501 register used for this operand. */
502 else
503 alt_cost += copy_cost (ops[j], mode, classes[j], 1, NULL);
505 else
507 /* The costs of this operand are not the same as the
508 other operand since move costs are not symmetric.
509 Moreover, if we cannot tie them, this alternative
510 needs to do a copy, which is one insn. */
511 struct costs *pp = this_op_costs[i];
512 int *pp_costs = pp->cost;
513 cost_classes_t cost_classes_ptr
514 = regno_cost_classes[REGNO (op)];
515 enum reg_class *cost_classes = cost_classes_ptr->classes;
516 bool in_p = recog_data.operand_type[i] != OP_OUT;
517 bool out_p = recog_data.operand_type[i] != OP_IN;
518 enum reg_class op_class = classes[i];
519 move_table *move_in_cost, *move_out_cost;
521 ira_init_register_move_cost_if_necessary (mode);
522 if (! in_p)
524 ira_assert (out_p);
525 move_out_cost = ira_may_move_out_cost[mode];
526 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
528 rclass = cost_classes[k];
529 pp_costs[k]
530 = move_out_cost[op_class][rclass] * frequency;
533 else if (! out_p)
535 ira_assert (in_p);
536 move_in_cost = ira_may_move_in_cost[mode];
537 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
539 rclass = cost_classes[k];
540 pp_costs[k]
541 = move_in_cost[rclass][op_class] * frequency;
544 else
546 move_in_cost = ira_may_move_in_cost[mode];
547 move_out_cost = ira_may_move_out_cost[mode];
548 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
550 rclass = cost_classes[k];
551 pp_costs[k] = ((move_in_cost[rclass][op_class]
552 + move_out_cost[op_class][rclass])
553 * frequency);
557 /* If the alternative actually allows memory, make
558 things a bit cheaper since we won't need an extra
559 insn to load it. */
560 pp->mem_cost
561 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
562 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
563 - allows_mem[i]) * frequency;
565 /* If we have assigned a class to this allocno in
566 our first pass, add a cost to this alternative
567 corresponding to what we would add if this
568 allocno were not in the appropriate class. */
569 if (pref)
571 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
573 if (pref_class == NO_REGS)
574 alt_cost
575 += ((out_p
576 ? ira_memory_move_cost[mode][op_class][0] : 0)
577 + (in_p
578 ? ira_memory_move_cost[mode][op_class][1]
579 : 0));
580 else if (ira_reg_class_intersect
581 [pref_class][op_class] == NO_REGS)
582 alt_cost
583 += ira_register_move_cost[mode][pref_class][op_class];
585 if (REGNO (ops[i]) != REGNO (ops[j])
586 && ! find_reg_note (insn, REG_DEAD, op))
587 alt_cost += 2;
589 /* This is in place of ordinary cost computation for
590 this operand, so skip to the end of the
591 alternative (should be just one character). */
592 while (*p && *p++ != ',')
595 constraints[i] = p;
596 continue;
600 /* Scan all the constraint letters. See if the operand
601 matches any of the constraints. Collect the valid
602 register classes and see if this operand accepts
603 memory. */
604 while ((c = *p))
606 switch (c)
608 case ',':
609 break;
610 case '*':
611 /* Ignore the next letter for this pass. */
612 c = *++p;
613 break;
615 case '?':
616 alt_cost += 2;
617 case '!': case '#': case '&':
618 case '0': case '1': case '2': case '3': case '4':
619 case '5': case '6': case '7': case '8': case '9':
620 break;
622 case 'p':
623 allows_addr = 1;
624 win = address_operand (op, GET_MODE (op));
625 /* We know this operand is an address, so we want it
626 to be allocated to a register that can be the
627 base of an address, i.e. BASE_REG_CLASS. */
628 classes[i]
629 = ira_reg_class_subunion[classes[i]]
630 [base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
631 ADDRESS, SCRATCH)];
632 break;
634 case 'm': case 'o': case 'V':
635 /* It doesn't seem worth distinguishing between
636 offsettable and non-offsettable addresses
637 here. */
638 insn_allows_mem[i] = allows_mem[i] = 1;
639 if (MEM_P (op))
640 win = 1;
641 break;
643 case '<':
644 if (MEM_P (op)
645 && (GET_CODE (XEXP (op, 0)) == PRE_DEC
646 || GET_CODE (XEXP (op, 0)) == POST_DEC))
647 win = 1;
648 break;
650 case '>':
651 if (MEM_P (op)
652 && (GET_CODE (XEXP (op, 0)) == PRE_INC
653 || GET_CODE (XEXP (op, 0)) == POST_INC))
654 win = 1;
655 break;
657 case 'E':
658 case 'F':
659 if (CONST_DOUBLE_AS_FLOAT_P (op)
660 || (GET_CODE (op) == CONST_VECTOR
661 && (GET_MODE_CLASS (GET_MODE (op))
662 == MODE_VECTOR_FLOAT)))
663 win = 1;
664 break;
666 case 'G':
667 case 'H':
668 if (CONST_DOUBLE_AS_FLOAT_P (op)
669 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, p))
670 win = 1;
671 break;
673 case 's':
674 if (CONST_SCALAR_INT_P (op))
675 break;
677 case 'i':
678 if (CONSTANT_P (op)
679 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op)))
680 win = 1;
681 break;
683 case 'n':
684 if (CONST_SCALAR_INT_P (op))
685 win = 1;
686 break;
688 case 'I':
689 case 'J':
690 case 'K':
691 case 'L':
692 case 'M':
693 case 'N':
694 case 'O':
695 case 'P':
696 if (CONST_INT_P (op)
697 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, p))
698 win = 1;
699 break;
701 case 'X':
702 win = 1;
703 break;
705 case 'g':
706 if (MEM_P (op)
707 || (CONSTANT_P (op)
708 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))))
709 win = 1;
710 insn_allows_mem[i] = allows_mem[i] = 1;
711 case 'r':
712 classes[i] = ira_reg_class_subunion[classes[i]][GENERAL_REGS];
713 break;
715 default:
716 if (REG_CLASS_FROM_CONSTRAINT (c, p) != NO_REGS)
717 classes[i] = ira_reg_class_subunion[classes[i]]
718 [REG_CLASS_FROM_CONSTRAINT (c, p)];
719 #ifdef EXTRA_CONSTRAINT_STR
720 else if (EXTRA_CONSTRAINT_STR (op, c, p))
721 win = 1;
723 if (EXTRA_MEMORY_CONSTRAINT (c, p))
725 /* Every MEM can be reloaded to fit. */
726 insn_allows_mem[i] = allows_mem[i] = 1;
727 if (MEM_P (op))
728 win = 1;
730 if (EXTRA_ADDRESS_CONSTRAINT (c, p))
732 /* Every address can be reloaded to fit. */
733 allows_addr = 1;
734 if (address_operand (op, GET_MODE (op)))
735 win = 1;
736 /* We know this operand is an address, so we
737 want it to be allocated to a hard register
738 that can be the base of an address,
739 i.e. BASE_REG_CLASS. */
740 classes[i]
741 = ira_reg_class_subunion[classes[i]]
742 [base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
743 ADDRESS, SCRATCH)];
745 #endif
746 break;
748 p += CONSTRAINT_LEN (c, p);
749 if (c == ',')
750 break;
753 constraints[i] = p;
755 /* How we account for this operand now depends on whether it
756 is a pseudo register or not. If it is, we first check if
757 any register classes are valid. If not, we ignore this
758 alternative, since we want to assume that all allocnos get
759 allocated for register preferencing. If some register
760 class is valid, compute the costs of moving the allocno
761 into that class. */
762 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
764 if (classes[i] == NO_REGS)
766 /* We must always fail if the operand is a REG, but
767 we did not find a suitable class.
769 Otherwise we may perform an uninitialized read
770 from this_op_costs after the `continue' statement
771 below. */
772 alt_fail = 1;
774 else
776 unsigned int regno = REGNO (op);
777 struct costs *pp = this_op_costs[i];
778 int *pp_costs = pp->cost;
779 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
780 enum reg_class *cost_classes = cost_classes_ptr->classes;
781 bool in_p = recog_data.operand_type[i] != OP_OUT;
782 bool out_p = recog_data.operand_type[i] != OP_IN;
783 enum reg_class op_class = classes[i];
784 move_table *move_in_cost, *move_out_cost;
786 ira_init_register_move_cost_if_necessary (mode);
787 if (! in_p)
789 ira_assert (out_p);
790 move_out_cost = ira_may_move_out_cost[mode];
791 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
793 rclass = cost_classes[k];
794 pp_costs[k]
795 = move_out_cost[op_class][rclass] * frequency;
798 else if (! out_p)
800 ira_assert (in_p);
801 move_in_cost = ira_may_move_in_cost[mode];
802 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
804 rclass = cost_classes[k];
805 pp_costs[k]
806 = move_in_cost[rclass][op_class] * frequency;
809 else
811 move_in_cost = ira_may_move_in_cost[mode];
812 move_out_cost = ira_may_move_out_cost[mode];
813 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
815 rclass = cost_classes[k];
816 pp_costs[k] = ((move_in_cost[rclass][op_class]
817 + move_out_cost[op_class][rclass])
818 * frequency);
822 /* If the alternative actually allows memory, make
823 things a bit cheaper since we won't need an extra
824 insn to load it. */
825 pp->mem_cost
826 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
827 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
828 - allows_mem[i]) * frequency;
829 /* If we have assigned a class to this allocno in
830 our first pass, add a cost to this alternative
831 corresponding to what we would add if this
832 allocno were not in the appropriate class. */
833 if (pref)
835 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
837 if (pref_class == NO_REGS)
838 alt_cost
839 += ((out_p
840 ? ira_memory_move_cost[mode][op_class][0] : 0)
841 + (in_p
842 ? ira_memory_move_cost[mode][op_class][1]
843 : 0));
844 else if (ira_reg_class_intersect[pref_class][op_class]
845 == NO_REGS)
846 alt_cost += ira_register_move_cost[mode][pref_class][op_class];
851 /* Otherwise, if this alternative wins, either because we
852 have already determined that or if we have a hard
853 register of the proper class, there is no cost for this
854 alternative. */
855 else if (win || (REG_P (op)
856 && reg_fits_class_p (op, classes[i],
857 0, GET_MODE (op))))
860 /* If registers are valid, the cost of this alternative
861 includes copying the object to and/or from a
862 register. */
863 else if (classes[i] != NO_REGS)
865 if (recog_data.operand_type[i] != OP_OUT)
866 alt_cost += copy_cost (op, mode, classes[i], 1, NULL);
868 if (recog_data.operand_type[i] != OP_IN)
869 alt_cost += copy_cost (op, mode, classes[i], 0, NULL);
871 /* The only other way this alternative can be used is if
872 this is a constant that could be placed into memory. */
873 else if (CONSTANT_P (op) && (allows_addr || allows_mem[i]))
874 alt_cost += ira_memory_move_cost[mode][classes[i]][1];
875 else
876 alt_fail = 1;
879 if (alt_fail)
880 continue;
882 op_cost_add = alt_cost * frequency;
883 /* Finally, update the costs with the information we've
884 calculated about this alternative. */
885 for (i = 0; i < n_ops; i++)
886 if (REG_P (ops[i]) && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
888 struct costs *pp = op_costs[i], *qq = this_op_costs[i];
889 int *pp_costs = pp->cost, *qq_costs = qq->cost;
890 int scale = 1 + (recog_data.operand_type[i] == OP_INOUT);
891 cost_classes_t cost_classes_ptr
892 = regno_cost_classes[REGNO (ops[i])];
894 pp->mem_cost = MIN (pp->mem_cost,
895 (qq->mem_cost + op_cost_add) * scale);
897 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
898 pp_costs[k]
899 = MIN (pp_costs[k], (qq_costs[k] + op_cost_add) * scale);
903 if (allocno_p)
904 for (i = 0; i < n_ops; i++)
906 ira_allocno_t a;
907 rtx op = ops[i];
909 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
910 continue;
911 a = ira_curr_regno_allocno_map [REGNO (op)];
912 if (! ALLOCNO_BAD_SPILL_P (a) && insn_allows_mem[i] == 0)
913 ALLOCNO_BAD_SPILL_P (a) = true;
920 /* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudo registers. */
921 static inline bool
922 ok_for_index_p_nonstrict (rtx reg)
924 unsigned regno = REGNO (reg);
926 return regno >= FIRST_PSEUDO_REGISTER || REGNO_OK_FOR_INDEX_P (regno);
929 /* A version of regno_ok_for_base_p for use here, when all
930 pseudo-registers should count as OK. Arguments as for
931 regno_ok_for_base_p. */
932 static inline bool
933 ok_for_base_p_nonstrict (rtx reg, enum machine_mode mode, addr_space_t as,
934 enum rtx_code outer_code, enum rtx_code index_code)
936 unsigned regno = REGNO (reg);
938 if (regno >= FIRST_PSEUDO_REGISTER)
939 return true;
940 return ok_for_base_p_1 (regno, mode, as, outer_code, index_code);
943 /* Record the pseudo registers we must reload into hard registers in a
944 subexpression of a memory address, X.
946 If CONTEXT is 0, we are looking at the base part of an address,
947 otherwise we are looking at the index part.
949 MODE and AS are the mode and address space of the memory reference;
950 OUTER_CODE and INDEX_CODE give the context that the rtx appears in.
951 These four arguments are passed down to base_reg_class.
953 SCALE is twice the amount to multiply the cost by (it is twice so
954 we can represent half-cost adjustments). */
955 static void
956 record_address_regs (enum machine_mode mode, addr_space_t as, rtx x,
957 int context, enum rtx_code outer_code,
958 enum rtx_code index_code, int scale)
960 enum rtx_code code = GET_CODE (x);
961 enum reg_class rclass;
963 if (context == 1)
964 rclass = INDEX_REG_CLASS;
965 else
966 rclass = base_reg_class (mode, as, outer_code, index_code);
968 switch (code)
970 case CONST_INT:
971 case CONST:
972 case CC0:
973 case PC:
974 case SYMBOL_REF:
975 case LABEL_REF:
976 return;
978 case PLUS:
979 /* When we have an address that is a sum, we must determine
980 whether registers are "base" or "index" regs. If there is a
981 sum of two registers, we must choose one to be the "base".
982 Luckily, we can use the REG_POINTER to make a good choice
983 most of the time. We only need to do this on machines that
984 can have two registers in an address and where the base and
985 index register classes are different.
987 ??? This code used to set REGNO_POINTER_FLAG in some cases,
988 but that seems bogus since it should only be set when we are
989 sure the register is being used as a pointer. */
991 rtx arg0 = XEXP (x, 0);
992 rtx arg1 = XEXP (x, 1);
993 enum rtx_code code0 = GET_CODE (arg0);
994 enum rtx_code code1 = GET_CODE (arg1);
996 /* Look inside subregs. */
997 if (code0 == SUBREG)
998 arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
999 if (code1 == SUBREG)
1000 arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
1002 /* If this machine only allows one register per address, it
1003 must be in the first operand. */
1004 if (MAX_REGS_PER_ADDRESS == 1)
1005 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale);
1007 /* If index and base registers are the same on this machine,
1008 just record registers in any non-constant operands. We
1009 assume here, as well as in the tests below, that all
1010 addresses are in canonical form. */
1011 else if (INDEX_REG_CLASS
1012 == base_reg_class (VOIDmode, as, PLUS, SCRATCH))
1014 record_address_regs (mode, as, arg0, context, PLUS, code1, scale);
1015 if (! CONSTANT_P (arg1))
1016 record_address_regs (mode, as, arg1, context, PLUS, code0, scale);
1019 /* If the second operand is a constant integer, it doesn't
1020 change what class the first operand must be. */
1021 else if (CONST_SCALAR_INT_P (arg1))
1022 record_address_regs (mode, as, arg0, context, PLUS, code1, scale);
1023 /* If the second operand is a symbolic constant, the first
1024 operand must be an index register. */
1025 else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF)
1026 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale);
1027 /* If both operands are registers but one is already a hard
1028 register of index or reg-base class, give the other the
1029 class that the hard register is not. */
1030 else if (code0 == REG && code1 == REG
1031 && REGNO (arg0) < FIRST_PSEUDO_REGISTER
1032 && (ok_for_base_p_nonstrict (arg0, mode, as, PLUS, REG)
1033 || ok_for_index_p_nonstrict (arg0)))
1034 record_address_regs (mode, as, arg1,
1035 ok_for_base_p_nonstrict (arg0, mode, as,
1036 PLUS, REG) ? 1 : 0,
1037 PLUS, REG, scale);
1038 else if (code0 == REG && code1 == REG
1039 && REGNO (arg1) < FIRST_PSEUDO_REGISTER
1040 && (ok_for_base_p_nonstrict (arg1, mode, as, PLUS, REG)
1041 || ok_for_index_p_nonstrict (arg1)))
1042 record_address_regs (mode, as, arg0,
1043 ok_for_base_p_nonstrict (arg1, mode, as,
1044 PLUS, REG) ? 1 : 0,
1045 PLUS, REG, scale);
1046 /* If one operand is known to be a pointer, it must be the
1047 base with the other operand the index. Likewise if the
1048 other operand is a MULT. */
1049 else if ((code0 == REG && REG_POINTER (arg0)) || code1 == MULT)
1051 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale);
1052 record_address_regs (mode, as, arg1, 1, PLUS, code0, scale);
1054 else if ((code1 == REG && REG_POINTER (arg1)) || code0 == MULT)
1056 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale);
1057 record_address_regs (mode, as, arg1, 0, PLUS, code0, scale);
1059 /* Otherwise, count equal chances that each might be a base or
1060 index register. This case should be rare. */
1061 else
1063 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale / 2);
1064 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale / 2);
1065 record_address_regs (mode, as, arg1, 0, PLUS, code0, scale / 2);
1066 record_address_regs (mode, as, arg1, 1, PLUS, code0, scale / 2);
1069 break;
1071 /* Double the importance of an allocno that is incremented or
1072 decremented, since it would take two extra insns if it ends
1073 up in the wrong place. */
1074 case POST_MODIFY:
1075 case PRE_MODIFY:
1076 record_address_regs (mode, as, XEXP (x, 0), 0, code,
1077 GET_CODE (XEXP (XEXP (x, 1), 1)), 2 * scale);
1078 if (REG_P (XEXP (XEXP (x, 1), 1)))
1079 record_address_regs (mode, as, XEXP (XEXP (x, 1), 1), 1, code, REG,
1080 2 * scale);
1081 break;
1083 case POST_INC:
1084 case PRE_INC:
1085 case POST_DEC:
1086 case PRE_DEC:
1087 /* Double the importance of an allocno that is incremented or
1088 decremented, since it would take two extra insns if it ends
1089 up in the wrong place. */
1090 record_address_regs (mode, as, XEXP (x, 0), 0, code, SCRATCH, 2 * scale);
1091 break;
1093 case REG:
1095 struct costs *pp;
1096 int *pp_costs;
1097 enum reg_class i;
1098 int k, regno, add_cost;
1099 cost_classes_t cost_classes_ptr;
1100 enum reg_class *cost_classes;
1101 move_table *move_in_cost;
1103 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
1104 break;
1106 regno = REGNO (x);
1107 if (allocno_p)
1108 ALLOCNO_BAD_SPILL_P (ira_curr_regno_allocno_map[regno]) = true;
1109 pp = COSTS (costs, COST_INDEX (regno));
1110 add_cost = (ira_memory_move_cost[Pmode][rclass][1] * scale) / 2;
1111 if (INT_MAX - add_cost < pp->mem_cost)
1112 pp->mem_cost = INT_MAX;
1113 else
1114 pp->mem_cost += add_cost;
1115 cost_classes_ptr = regno_cost_classes[regno];
1116 cost_classes = cost_classes_ptr->classes;
1117 pp_costs = pp->cost;
1118 ira_init_register_move_cost_if_necessary (Pmode);
1119 move_in_cost = ira_may_move_in_cost[Pmode];
1120 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1122 i = cost_classes[k];
1123 add_cost = (move_in_cost[i][rclass] * scale) / 2;
1124 if (INT_MAX - add_cost < pp_costs[k])
1125 pp_costs[k] = INT_MAX;
1126 else
1127 pp_costs[k] += add_cost;
1130 break;
1132 default:
1134 const char *fmt = GET_RTX_FORMAT (code);
1135 int i;
1136 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1137 if (fmt[i] == 'e')
1138 record_address_regs (mode, as, XEXP (x, i), context, code, SCRATCH,
1139 scale);
1146 /* Calculate the costs of insn operands. */
1147 static void
1148 record_operand_costs (rtx insn, enum reg_class *pref)
1150 const char *constraints[MAX_RECOG_OPERANDS];
1151 enum machine_mode modes[MAX_RECOG_OPERANDS];
1152 rtx ops[MAX_RECOG_OPERANDS];
1153 rtx set;
1154 int i;
1156 for (i = 0; i < recog_data.n_operands; i++)
1158 constraints[i] = recog_data.constraints[i];
1159 modes[i] = recog_data.operand_mode[i];
1162 /* If we get here, we are set up to record the costs of all the
1163 operands for this insn. Start by initializing the costs. Then
1164 handle any address registers. Finally record the desired classes
1165 for any allocnos, doing it twice if some pair of operands are
1166 commutative. */
1167 for (i = 0; i < recog_data.n_operands; i++)
1169 memcpy (op_costs[i], init_cost, struct_costs_size);
1171 ops[i] = recog_data.operand[i];
1172 if (GET_CODE (recog_data.operand[i]) == SUBREG)
1173 recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);
1175 if (MEM_P (recog_data.operand[i]))
1176 record_address_regs (GET_MODE (recog_data.operand[i]),
1177 MEM_ADDR_SPACE (recog_data.operand[i]),
1178 XEXP (recog_data.operand[i], 0),
1179 0, MEM, SCRATCH, frequency * 2);
1180 else if (constraints[i][0] == 'p'
1181 || EXTRA_ADDRESS_CONSTRAINT (constraints[i][0],
1182 constraints[i]))
1183 record_address_regs (VOIDmode, ADDR_SPACE_GENERIC,
1184 recog_data.operand[i], 0, ADDRESS, SCRATCH,
1185 frequency * 2);
1188 /* Check for commutative in a separate loop so everything will have
1189 been initialized. We must do this even if one operand is a
1190 constant--see addsi3 in m68k.md. */
1191 for (i = 0; i < (int) recog_data.n_operands - 1; i++)
1192 if (constraints[i][0] == '%')
1194 const char *xconstraints[MAX_RECOG_OPERANDS];
1195 int j;
1197 /* Handle commutative operands by swapping the constraints.
1198 We assume the modes are the same. */
1199 for (j = 0; j < recog_data.n_operands; j++)
1200 xconstraints[j] = constraints[j];
1202 xconstraints[i] = constraints[i+1];
1203 xconstraints[i+1] = constraints[i];
1204 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1205 recog_data.operand, modes,
1206 xconstraints, insn, pref);
1208 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1209 recog_data.operand, modes,
1210 constraints, insn, pref);
1212 /* If this insn is a single set copying operand 1 to operand 0 and
1213 one operand is an allocno with the other a hard reg or an allocno
1214 that prefers a hard register that is in its own register class
1215 then we may want to adjust the cost of that register class to -1.
1217 Avoid the adjustment if the source does not die to avoid
1218 stressing of register allocator by preferrencing two colliding
1219 registers into single class.
1221 Also avoid the adjustment if a copy between hard registers of the
1222 class is expensive (ten times the cost of a default copy is
1223 considered arbitrarily expensive). This avoids losing when the
1224 preferred class is very expensive as the source of a copy
1225 instruction. */
1226 if ((set = single_set (insn)) != NULL_RTX
1227 /* In rare cases the single set insn might have less 2 operands
1228 as the source can be a fixed special reg. */
1229 && recog_data.n_operands > 1
1230 && ops[0] == SET_DEST (set) && ops[1] == SET_SRC (set))
1232 int regno, other_regno;
1233 rtx dest = SET_DEST (set);
1234 rtx src = SET_SRC (set);
1236 dest = SET_DEST (set);
1237 src = SET_SRC (set);
1238 if (GET_CODE (dest) == SUBREG
1239 && (GET_MODE_SIZE (GET_MODE (dest))
1240 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))))
1241 dest = SUBREG_REG (dest);
1242 if (GET_CODE (src) == SUBREG
1243 && (GET_MODE_SIZE (GET_MODE (src))
1244 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
1245 src = SUBREG_REG (src);
1246 if (REG_P (src) && REG_P (dest)
1247 && find_regno_note (insn, REG_DEAD, REGNO (src))
1248 && (((regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
1249 && (other_regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER)
1250 || ((regno = REGNO (dest)) >= FIRST_PSEUDO_REGISTER
1251 && (other_regno = REGNO (src)) < FIRST_PSEUDO_REGISTER)))
1253 enum machine_mode mode = GET_MODE (src);
1254 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1255 enum reg_class *cost_classes = cost_classes_ptr->classes;
1256 reg_class_t rclass;
1257 int k, nr;
1259 i = regno == (int) REGNO (src) ? 1 : 0;
1260 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1262 rclass = cost_classes[k];
1263 if (TEST_HARD_REG_BIT (reg_class_contents[rclass], other_regno)
1264 && (reg_class_size[(int) rclass]
1265 == ira_reg_class_max_nregs [(int) rclass][(int) mode]))
1267 if (reg_class_size[rclass] == 1)
1268 op_costs[i]->cost[k] = -frequency;
1269 else
1271 for (nr = 0;
1272 nr < hard_regno_nregs[other_regno][mode];
1273 nr++)
1274 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass],
1275 other_regno + nr))
1276 break;
1278 if (nr == hard_regno_nregs[other_regno][mode])
1279 op_costs[i]->cost[k] = -frequency;
1289 /* Process one insn INSN. Scan it and record each time it would save
1290 code to put a certain allocnos in a certain class. Return the last
1291 insn processed, so that the scan can be continued from there. */
1292 static rtx
1293 scan_one_insn (rtx insn)
1295 enum rtx_code pat_code;
1296 rtx set, note;
1297 int i, k;
1298 bool counted_mem;
1300 if (!NONDEBUG_INSN_P (insn))
1301 return insn;
1303 pat_code = GET_CODE (PATTERN (insn));
1304 if (pat_code == USE || pat_code == CLOBBER || pat_code == ASM_INPUT)
1305 return insn;
1307 counted_mem = false;
1308 set = single_set (insn);
1309 extract_insn (insn);
1311 /* If this insn loads a parameter from its stack slot, then it
1312 represents a savings, rather than a cost, if the parameter is
1313 stored in memory. Record this fact.
1315 Similarly if we're loading other constants from memory (constant
1316 pool, TOC references, small data areas, etc) and this is the only
1317 assignment to the destination pseudo.
1319 Don't do this if SET_SRC (set) isn't a general operand, if it is
1320 a memory requiring special instructions to load it, decreasing
1321 mem_cost might result in it being loaded using the specialized
1322 instruction into a register, then stored into stack and loaded
1323 again from the stack. See PR52208.
1325 Don't do this if SET_SRC (set) has side effect. See PR56124. */
1326 if (set != 0 && REG_P (SET_DEST (set)) && MEM_P (SET_SRC (set))
1327 && (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL_RTX
1328 && ((MEM_P (XEXP (note, 0))
1329 && !side_effects_p (SET_SRC (set)))
1330 || (CONSTANT_P (XEXP (note, 0))
1331 && targetm.legitimate_constant_p (GET_MODE (SET_DEST (set)),
1332 XEXP (note, 0))
1333 && REG_N_SETS (REGNO (SET_DEST (set))) == 1))
1334 && general_operand (SET_SRC (set), GET_MODE (SET_SRC (set))))
1336 enum reg_class cl = GENERAL_REGS;
1337 rtx reg = SET_DEST (set);
1338 int num = COST_INDEX (REGNO (reg));
1340 COSTS (costs, num)->mem_cost
1341 -= ira_memory_move_cost[GET_MODE (reg)][cl][1] * frequency;
1342 record_address_regs (GET_MODE (SET_SRC (set)),
1343 MEM_ADDR_SPACE (SET_SRC (set)),
1344 XEXP (SET_SRC (set), 0), 0, MEM, SCRATCH,
1345 frequency * 2);
1346 counted_mem = true;
1349 record_operand_costs (insn, pref);
1351 /* Now add the cost for each operand to the total costs for its
1352 allocno. */
1353 for (i = 0; i < recog_data.n_operands; i++)
1354 if (REG_P (recog_data.operand[i])
1355 && REGNO (recog_data.operand[i]) >= FIRST_PSEUDO_REGISTER)
1357 int regno = REGNO (recog_data.operand[i]);
1358 struct costs *p = COSTS (costs, COST_INDEX (regno));
1359 struct costs *q = op_costs[i];
1360 int *p_costs = p->cost, *q_costs = q->cost;
1361 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1362 int add_cost;
1364 /* If the already accounted for the memory "cost" above, don't
1365 do so again. */
1366 if (!counted_mem)
1368 add_cost = q->mem_cost;
1369 if (add_cost > 0 && INT_MAX - add_cost < p->mem_cost)
1370 p->mem_cost = INT_MAX;
1371 else
1372 p->mem_cost += add_cost;
1374 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1376 add_cost = q_costs[k];
1377 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1378 p_costs[k] = INT_MAX;
1379 else
1380 p_costs[k] += add_cost;
1384 return insn;
1389 /* Print allocnos costs to file F. */
1390 static void
1391 print_allocno_costs (FILE *f)
1393 int k;
1394 ira_allocno_t a;
1395 ira_allocno_iterator ai;
1397 ira_assert (allocno_p);
1398 fprintf (f, "\n");
1399 FOR_EACH_ALLOCNO (a, ai)
1401 int i, rclass;
1402 basic_block bb;
1403 int regno = ALLOCNO_REGNO (a);
1404 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1405 enum reg_class *cost_classes = cost_classes_ptr->classes;
1407 i = ALLOCNO_NUM (a);
1408 fprintf (f, " a%d(r%d,", i, regno);
1409 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1410 fprintf (f, "b%d", bb->index);
1411 else
1412 fprintf (f, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
1413 fprintf (f, ") costs:");
1414 for (k = 0; k < cost_classes_ptr->num; k++)
1416 rclass = cost_classes[k];
1417 if (contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (regno)]
1418 #ifdef CANNOT_CHANGE_MODE_CLASS
1419 && ! invalid_mode_change_p (regno, (enum reg_class) rclass)
1420 #endif
1423 fprintf (f, " %s:%d", reg_class_names[rclass],
1424 COSTS (costs, i)->cost[k]);
1425 if (flag_ira_region == IRA_REGION_ALL
1426 || flag_ira_region == IRA_REGION_MIXED)
1427 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->cost[k]);
1430 fprintf (f, " MEM:%i", COSTS (costs, i)->mem_cost);
1431 if (flag_ira_region == IRA_REGION_ALL
1432 || flag_ira_region == IRA_REGION_MIXED)
1433 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->mem_cost);
1434 fprintf (f, "\n");
1438 /* Print pseudo costs to file F. */
1439 static void
1440 print_pseudo_costs (FILE *f)
1442 int regno, k;
1443 int rclass;
1444 cost_classes_t cost_classes_ptr;
1445 enum reg_class *cost_classes;
1447 ira_assert (! allocno_p);
1448 fprintf (f, "\n");
1449 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1451 if (REG_N_REFS (regno) <= 0)
1452 continue;
1453 cost_classes_ptr = regno_cost_classes[regno];
1454 cost_classes = cost_classes_ptr->classes;
1455 fprintf (f, " r%d costs:", regno);
1456 for (k = 0; k < cost_classes_ptr->num; k++)
1458 rclass = cost_classes[k];
1459 if (contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (regno)]
1460 #ifdef CANNOT_CHANGE_MODE_CLASS
1461 && ! invalid_mode_change_p (regno, (enum reg_class) rclass)
1462 #endif
1464 fprintf (f, " %s:%d", reg_class_names[rclass],
1465 COSTS (costs, regno)->cost[k]);
1467 fprintf (f, " MEM:%i\n", COSTS (costs, regno)->mem_cost);
1471 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1472 costs. */
1473 static void
1474 process_bb_for_costs (basic_block bb)
1476 rtx insn;
1478 frequency = REG_FREQ_FROM_BB (bb);
1479 if (frequency == 0)
1480 frequency = 1;
1481 FOR_BB_INSNS (bb, insn)
1482 insn = scan_one_insn (insn);
1485 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1486 costs. */
1487 static void
1488 process_bb_node_for_costs (ira_loop_tree_node_t loop_tree_node)
1490 basic_block bb;
1492 bb = loop_tree_node->bb;
1493 if (bb != NULL)
1494 process_bb_for_costs (bb);
1497 /* Find costs of register classes and memory for allocnos or pseudos
1498 and their best costs. Set up preferred, alternative and allocno
1499 classes for pseudos. */
1500 static void
1501 find_costs_and_classes (FILE *dump_file)
1503 int i, k, start, max_cost_classes_num;
1504 int pass;
1505 basic_block bb;
1506 enum reg_class *regno_best_class;
1508 init_recog ();
1509 regno_best_class
1510 = (enum reg_class *) ira_allocate (max_reg_num ()
1511 * sizeof (enum reg_class));
1512 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1513 regno_best_class[i] = NO_REGS;
1514 if (!resize_reg_info () && allocno_p
1515 && pseudo_classes_defined_p && flag_expensive_optimizations)
1517 ira_allocno_t a;
1518 ira_allocno_iterator ai;
1520 pref = pref_buffer;
1521 max_cost_classes_num = 1;
1522 FOR_EACH_ALLOCNO (a, ai)
1524 pref[ALLOCNO_NUM (a)] = reg_preferred_class (ALLOCNO_REGNO (a));
1525 setup_regno_cost_classes_by_aclass
1526 (ALLOCNO_REGNO (a), pref[ALLOCNO_NUM (a)]);
1527 max_cost_classes_num
1528 = MAX (max_cost_classes_num,
1529 regno_cost_classes[ALLOCNO_REGNO (a)]->num);
1531 start = 1;
1533 else
1535 pref = NULL;
1536 max_cost_classes_num = ira_important_classes_num;
1537 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1538 if (regno_reg_rtx[i] != NULL_RTX)
1539 setup_regno_cost_classes_by_mode (i, PSEUDO_REGNO_MODE (i));
1540 else
1541 setup_regno_cost_classes_by_aclass (i, ALL_REGS);
1542 start = 0;
1544 if (allocno_p)
1545 /* Clear the flag for the next compiled function. */
1546 pseudo_classes_defined_p = false;
1547 /* Normally we scan the insns once and determine the best class to
1548 use for each allocno. However, if -fexpensive-optimizations are
1549 on, we do so twice, the second time using the tentative best
1550 classes to guide the selection. */
1551 for (pass = start; pass <= flag_expensive_optimizations; pass++)
1553 if ((!allocno_p || internal_flag_ira_verbose > 0) && dump_file)
1554 fprintf (dump_file,
1555 "\nPass %i for finding pseudo/allocno costs\n\n", pass);
1557 if (pass != start)
1559 max_cost_classes_num = 1;
1560 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1562 setup_regno_cost_classes_by_aclass (i, regno_best_class[i]);
1563 max_cost_classes_num
1564 = MAX (max_cost_classes_num, regno_cost_classes[i]->num);
1568 struct_costs_size
1569 = sizeof (struct costs) + sizeof (int) * (max_cost_classes_num - 1);
1570 /* Zero out our accumulation of the cost of each class for each
1571 allocno. */
1572 memset (costs, 0, cost_elements_num * struct_costs_size);
1574 if (allocno_p)
1576 /* Scan the instructions and record each time it would save code
1577 to put a certain allocno in a certain class. */
1578 ira_traverse_loop_tree (true, ira_loop_tree_root,
1579 process_bb_node_for_costs, NULL);
1581 memcpy (total_allocno_costs, costs,
1582 max_struct_costs_size * ira_allocnos_num);
1584 else
1586 basic_block bb;
1588 FOR_EACH_BB (bb)
1589 process_bb_for_costs (bb);
1592 if (pass == 0)
1593 pref = pref_buffer;
1595 /* Now for each allocno look at how desirable each class is and
1596 find which class is preferred. */
1597 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1599 ira_allocno_t a, parent_a;
1600 int rclass, a_num, parent_a_num, add_cost;
1601 ira_loop_tree_node_t parent;
1602 int best_cost, allocno_cost;
1603 enum reg_class best, alt_class;
1604 cost_classes_t cost_classes_ptr = regno_cost_classes[i];
1605 enum reg_class *cost_classes = cost_classes_ptr->classes;
1606 int *i_costs = temp_costs->cost;
1607 int i_mem_cost;
1608 int equiv_savings = regno_equiv_gains[i];
1610 if (! allocno_p)
1612 if (regno_reg_rtx[i] == NULL_RTX)
1613 continue;
1614 memcpy (temp_costs, COSTS (costs, i), struct_costs_size);
1615 i_mem_cost = temp_costs->mem_cost;
1617 else
1619 if (ira_regno_allocno_map[i] == NULL)
1620 continue;
1621 memset (temp_costs, 0, struct_costs_size);
1622 i_mem_cost = 0;
1623 /* Find cost of all allocnos with the same regno. */
1624 for (a = ira_regno_allocno_map[i];
1625 a != NULL;
1626 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1628 int *a_costs, *p_costs;
1630 a_num = ALLOCNO_NUM (a);
1631 if ((flag_ira_region == IRA_REGION_ALL
1632 || flag_ira_region == IRA_REGION_MIXED)
1633 && (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1634 && (parent_a = parent->regno_allocno_map[i]) != NULL
1635 /* There are no caps yet. */
1636 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE
1637 (a)->border_allocnos,
1638 ALLOCNO_NUM (a)))
1640 /* Propagate costs to upper levels in the region
1641 tree. */
1642 parent_a_num = ALLOCNO_NUM (parent_a);
1643 a_costs = COSTS (total_allocno_costs, a_num)->cost;
1644 p_costs = COSTS (total_allocno_costs, parent_a_num)->cost;
1645 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1647 add_cost = a_costs[k];
1648 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1649 p_costs[k] = INT_MAX;
1650 else
1651 p_costs[k] += add_cost;
1653 add_cost = COSTS (total_allocno_costs, a_num)->mem_cost;
1654 if (add_cost > 0
1655 && (INT_MAX - add_cost
1656 < COSTS (total_allocno_costs,
1657 parent_a_num)->mem_cost))
1658 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1659 = INT_MAX;
1660 else
1661 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1662 += add_cost;
1664 if (i >= first_moveable_pseudo && i < last_moveable_pseudo)
1665 COSTS (total_allocno_costs, parent_a_num)->mem_cost = 0;
1667 a_costs = COSTS (costs, 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 < i_costs[k])
1672 i_costs[k] = INT_MAX;
1673 else
1674 i_costs[k] += add_cost;
1676 add_cost = COSTS (costs, a_num)->mem_cost;
1677 if (add_cost > 0 && INT_MAX - add_cost < i_mem_cost)
1678 i_mem_cost = INT_MAX;
1679 else
1680 i_mem_cost += add_cost;
1683 if (i >= first_moveable_pseudo && i < last_moveable_pseudo)
1684 i_mem_cost = 0;
1685 else if (equiv_savings < 0)
1686 i_mem_cost = -equiv_savings;
1687 else if (equiv_savings > 0)
1689 i_mem_cost = 0;
1690 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1691 i_costs[k] += equiv_savings;
1694 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1695 best = ALL_REGS;
1696 alt_class = NO_REGS;
1697 /* Find best common class for all allocnos with the same
1698 regno. */
1699 for (k = 0; k < cost_classes_ptr->num; k++)
1701 rclass = cost_classes[k];
1702 /* Ignore classes that are too small or invalid for this
1703 operand. */
1704 if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)]
1705 #ifdef CANNOT_CHANGE_MODE_CLASS
1706 || invalid_mode_change_p (i, (enum reg_class) rclass)
1707 #endif
1709 continue;
1710 if (i_costs[k] < best_cost)
1712 best_cost = i_costs[k];
1713 best = (enum reg_class) rclass;
1715 else if (i_costs[k] == best_cost)
1716 best = ira_reg_class_subunion[best][rclass];
1717 if (pass == flag_expensive_optimizations
1718 /* We still prefer registers to memory even at this
1719 stage if their costs are the same. We will make
1720 a final decision during assigning hard registers
1721 when we have all info including more accurate
1722 costs which might be affected by assigning hard
1723 registers to other pseudos because the pseudos
1724 involved in moves can be coalesced. */
1725 && i_costs[k] <= i_mem_cost
1726 && (reg_class_size[reg_class_subunion[alt_class][rclass]]
1727 > reg_class_size[alt_class]))
1728 alt_class = reg_class_subunion[alt_class][rclass];
1730 alt_class = ira_allocno_class_translate[alt_class];
1731 if (best_cost > i_mem_cost)
1732 regno_aclass[i] = NO_REGS;
1733 else
1735 /* Make the common class the biggest class of best and
1736 alt_class. */
1737 regno_aclass[i]
1738 = ira_reg_class_superunion[best][alt_class];
1739 ira_assert (regno_aclass[i] != NO_REGS
1740 && ira_reg_allocno_class_p[regno_aclass[i]]);
1742 if (pass == flag_expensive_optimizations)
1744 if (best_cost > i_mem_cost)
1745 best = alt_class = NO_REGS;
1746 else if (best == alt_class)
1747 alt_class = NO_REGS;
1748 setup_reg_classes (i, best, alt_class, regno_aclass[i]);
1749 if ((!allocno_p || internal_flag_ira_verbose > 2)
1750 && dump_file != NULL)
1751 fprintf (dump_file,
1752 " r%d: preferred %s, alternative %s, allocno %s\n",
1753 i, reg_class_names[best], reg_class_names[alt_class],
1754 reg_class_names[regno_aclass[i]]);
1756 regno_best_class[i] = best;
1757 if (! allocno_p)
1759 pref[i] = best_cost > i_mem_cost ? NO_REGS : best;
1760 continue;
1762 for (a = ira_regno_allocno_map[i];
1763 a != NULL;
1764 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1766 enum reg_class aclass = regno_aclass[i];
1767 int a_num = ALLOCNO_NUM (a);
1768 int *total_a_costs = COSTS (total_allocno_costs, a_num)->cost;
1769 int *a_costs = COSTS (costs, a_num)->cost;
1771 if (aclass == NO_REGS)
1772 best = NO_REGS;
1773 else
1775 /* Finding best class which is subset of the common
1776 class. */
1777 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1778 allocno_cost = best_cost;
1779 best = ALL_REGS;
1780 for (k = 0; k < cost_classes_ptr->num; k++)
1782 rclass = cost_classes[k];
1783 if (! ira_class_subset_p[rclass][aclass])
1784 continue;
1785 /* Ignore classes that are too small or invalid
1786 for this operand. */
1787 if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)]
1788 #ifdef CANNOT_CHANGE_MODE_CLASS
1789 || invalid_mode_change_p (i, (enum reg_class) rclass)
1790 #endif
1793 else if (total_a_costs[k] < best_cost)
1795 best_cost = total_a_costs[k];
1796 allocno_cost = a_costs[k];
1797 best = (enum reg_class) rclass;
1799 else if (total_a_costs[k] == best_cost)
1801 best = ira_reg_class_subunion[best][rclass];
1802 allocno_cost = MAX (allocno_cost, a_costs[k]);
1805 ALLOCNO_CLASS_COST (a) = allocno_cost;
1807 if (internal_flag_ira_verbose > 2 && dump_file != NULL
1808 && (pass == 0 || pref[a_num] != best))
1810 fprintf (dump_file, " a%d (r%d,", a_num, i);
1811 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1812 fprintf (dump_file, "b%d", bb->index);
1813 else
1814 fprintf (dump_file, "l%d",
1815 ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
1816 fprintf (dump_file, ") best %s, allocno %s\n",
1817 reg_class_names[best],
1818 reg_class_names[aclass]);
1820 pref[a_num] = best;
1821 if (pass == flag_expensive_optimizations && best != aclass
1822 && ira_class_hard_regs_num[best] > 0
1823 && (ira_reg_class_max_nregs[best][ALLOCNO_MODE (a)]
1824 >= ira_class_hard_regs_num[best]))
1826 int ind = cost_classes_ptr->index[aclass];
1828 ira_assert (ind >= 0);
1829 ira_add_allocno_pref (a, ira_class_hard_regs[best][0],
1830 (a_costs[ind] - ALLOCNO_CLASS_COST (a))
1831 / (ira_register_move_cost
1832 [ALLOCNO_MODE (a)][best][aclass]));
1833 for (k = 0; k < cost_classes_ptr->num; k++)
1834 if (ira_class_subset_p[cost_classes[k]][best])
1835 a_costs[k] = a_costs[ind];
1840 if (internal_flag_ira_verbose > 4 && dump_file)
1842 if (allocno_p)
1843 print_allocno_costs (dump_file);
1844 else
1845 print_pseudo_costs (dump_file);
1846 fprintf (dump_file,"\n");
1849 ira_free (regno_best_class);
1854 /* Process moves involving hard regs to modify allocno hard register
1855 costs. We can do this only after determining allocno class. If a
1856 hard register forms a register class, than moves with the hard
1857 register are already taken into account in class costs for the
1858 allocno. */
1859 static void
1860 process_bb_node_for_hard_reg_moves (ira_loop_tree_node_t loop_tree_node)
1862 int i, freq, src_regno, dst_regno, hard_regno, a_regno;
1863 bool to_p;
1864 ira_allocno_t a, curr_a;
1865 ira_loop_tree_node_t curr_loop_tree_node;
1866 enum reg_class rclass;
1867 basic_block bb;
1868 rtx insn, set, src, dst;
1870 bb = loop_tree_node->bb;
1871 if (bb == NULL)
1872 return;
1873 freq = REG_FREQ_FROM_BB (bb);
1874 if (freq == 0)
1875 freq = 1;
1876 FOR_BB_INSNS (bb, insn)
1878 if (!NONDEBUG_INSN_P (insn))
1879 continue;
1880 set = single_set (insn);
1881 if (set == NULL_RTX)
1882 continue;
1883 dst = SET_DEST (set);
1884 src = SET_SRC (set);
1885 if (! REG_P (dst) || ! REG_P (src))
1886 continue;
1887 dst_regno = REGNO (dst);
1888 src_regno = REGNO (src);
1889 if (dst_regno >= FIRST_PSEUDO_REGISTER
1890 && src_regno < FIRST_PSEUDO_REGISTER)
1892 hard_regno = src_regno;
1893 a = ira_curr_regno_allocno_map[dst_regno];
1894 to_p = true;
1896 else if (src_regno >= FIRST_PSEUDO_REGISTER
1897 && dst_regno < FIRST_PSEUDO_REGISTER)
1899 hard_regno = dst_regno;
1900 a = ira_curr_regno_allocno_map[src_regno];
1901 to_p = false;
1903 else
1904 continue;
1905 rclass = ALLOCNO_CLASS (a);
1906 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass], hard_regno))
1907 continue;
1908 i = ira_class_hard_reg_index[rclass][hard_regno];
1909 if (i < 0)
1910 continue;
1911 a_regno = ALLOCNO_REGNO (a);
1912 for (curr_loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
1913 curr_loop_tree_node != NULL;
1914 curr_loop_tree_node = curr_loop_tree_node->parent)
1915 if ((curr_a = curr_loop_tree_node->regno_allocno_map[a_regno]) != NULL)
1916 ira_add_allocno_pref (curr_a, hard_regno, freq);
1918 int cost;
1919 enum reg_class hard_reg_class;
1920 enum machine_mode mode;
1922 mode = ALLOCNO_MODE (a);
1923 hard_reg_class = REGNO_REG_CLASS (hard_regno);
1924 ira_init_register_move_cost_if_necessary (mode);
1925 cost = (to_p ? ira_register_move_cost[mode][hard_reg_class][rclass]
1926 : ira_register_move_cost[mode][rclass][hard_reg_class]) * freq;
1927 ira_allocate_and_set_costs (&ALLOCNO_HARD_REG_COSTS (a), rclass,
1928 ALLOCNO_CLASS_COST (a));
1929 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
1930 rclass, 0);
1931 ALLOCNO_HARD_REG_COSTS (a)[i] -= cost;
1932 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[i] -= cost;
1933 ALLOCNO_CLASS_COST (a) = MIN (ALLOCNO_CLASS_COST (a),
1934 ALLOCNO_HARD_REG_COSTS (a)[i]);
1939 /* After we find hard register and memory costs for allocnos, define
1940 its class and modify hard register cost because insns moving
1941 allocno to/from hard registers. */
1942 static void
1943 setup_allocno_class_and_costs (void)
1945 int i, j, n, regno, hard_regno, num;
1946 int *reg_costs;
1947 enum reg_class aclass, rclass;
1948 ira_allocno_t a;
1949 ira_allocno_iterator ai;
1950 cost_classes_t cost_classes_ptr;
1952 ira_assert (allocno_p);
1953 FOR_EACH_ALLOCNO (a, ai)
1955 i = ALLOCNO_NUM (a);
1956 regno = ALLOCNO_REGNO (a);
1957 aclass = regno_aclass[regno];
1958 cost_classes_ptr = regno_cost_classes[regno];
1959 ira_assert (pref[i] == NO_REGS || aclass != NO_REGS);
1960 ALLOCNO_MEMORY_COST (a) = COSTS (costs, i)->mem_cost;
1961 ira_set_allocno_class (a, aclass);
1962 if (aclass == NO_REGS)
1963 continue;
1964 if (optimize && ALLOCNO_CLASS (a) != pref[i])
1966 n = ira_class_hard_regs_num[aclass];
1967 ALLOCNO_HARD_REG_COSTS (a)
1968 = reg_costs = ira_allocate_cost_vector (aclass);
1969 for (j = n - 1; j >= 0; j--)
1971 hard_regno = ira_class_hard_regs[aclass][j];
1972 if (TEST_HARD_REG_BIT (reg_class_contents[pref[i]], hard_regno))
1973 reg_costs[j] = ALLOCNO_CLASS_COST (a);
1974 else
1976 rclass = REGNO_REG_CLASS (hard_regno);
1977 num = cost_classes_ptr->index[rclass];
1978 if (num < 0)
1980 num = cost_classes_ptr->hard_regno_index[hard_regno];
1981 ira_assert (num >= 0);
1983 reg_costs[j] = COSTS (costs, i)->cost[num];
1988 if (optimize)
1989 ira_traverse_loop_tree (true, ira_loop_tree_root,
1990 process_bb_node_for_hard_reg_moves, NULL);
1995 /* Function called once during compiler work. */
1996 void
1997 ira_init_costs_once (void)
1999 int i;
2001 init_cost = NULL;
2002 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2004 op_costs[i] = NULL;
2005 this_op_costs[i] = NULL;
2007 temp_costs = NULL;
2010 /* Free allocated temporary cost vectors. */
2011 static void
2012 free_ira_costs (void)
2014 int i;
2016 free (init_cost);
2017 init_cost = NULL;
2018 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2020 free (op_costs[i]);
2021 free (this_op_costs[i]);
2022 op_costs[i] = this_op_costs[i] = NULL;
2024 free (temp_costs);
2025 temp_costs = NULL;
2028 /* This is called each time register related information is
2029 changed. */
2030 void
2031 ira_init_costs (void)
2033 int i;
2035 free_ira_costs ();
2036 max_struct_costs_size
2037 = sizeof (struct costs) + sizeof (int) * (ira_important_classes_num - 1);
2038 /* Don't use ira_allocate because vectors live through several IRA
2039 calls. */
2040 init_cost = (struct costs *) xmalloc (max_struct_costs_size);
2041 init_cost->mem_cost = 1000000;
2042 for (i = 0; i < ira_important_classes_num; i++)
2043 init_cost->cost[i] = 1000000;
2044 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2046 op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
2047 this_op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
2049 temp_costs = (struct costs *) xmalloc (max_struct_costs_size);
2052 /* Function called once at the end of compiler work. */
2053 void
2054 ira_finish_costs_once (void)
2056 free_ira_costs ();
2061 /* Common initialization function for ira_costs and
2062 ira_set_pseudo_classes. */
2063 static void
2064 init_costs (void)
2066 init_subregs_of_mode ();
2067 costs = (struct costs *) ira_allocate (max_struct_costs_size
2068 * cost_elements_num);
2069 pref_buffer = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
2070 * cost_elements_num);
2071 regno_aclass = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
2072 * max_reg_num ());
2073 regno_equiv_gains = (int *) ira_allocate (sizeof (int) * max_reg_num ());
2074 memset (regno_equiv_gains, 0, sizeof (int) * max_reg_num ());
2077 /* Common finalization function for ira_costs and
2078 ira_set_pseudo_classes. */
2079 static void
2080 finish_costs (void)
2082 finish_subregs_of_mode ();
2083 ira_free (regno_equiv_gains);
2084 ira_free (regno_aclass);
2085 ira_free (pref_buffer);
2086 ira_free (costs);
2089 /* Entry function which defines register class, memory and hard
2090 register costs for each allocno. */
2091 void
2092 ira_costs (void)
2094 allocno_p = true;
2095 cost_elements_num = ira_allocnos_num;
2096 init_costs ();
2097 total_allocno_costs = (struct costs *) ira_allocate (max_struct_costs_size
2098 * ira_allocnos_num);
2099 initiate_regno_cost_classes ();
2100 calculate_elim_costs_all_insns ();
2101 find_costs_and_classes (ira_dump_file);
2102 setup_allocno_class_and_costs ();
2103 finish_regno_cost_classes ();
2104 finish_costs ();
2105 ira_free (total_allocno_costs);
2108 /* Entry function which defines classes for pseudos.
2109 Set pseudo_classes_defined_p only if DEFINE_PSEUDO_CLASSES is true. */
2110 void
2111 ira_set_pseudo_classes (bool define_pseudo_classes, FILE *dump_file)
2113 allocno_p = false;
2114 internal_flag_ira_verbose = flag_ira_verbose;
2115 cost_elements_num = max_reg_num ();
2116 init_costs ();
2117 initiate_regno_cost_classes ();
2118 find_costs_and_classes (dump_file);
2119 finish_regno_cost_classes ();
2120 if (define_pseudo_classes)
2121 pseudo_classes_defined_p = true;
2123 finish_costs ();
2128 /* Change hard register costs for allocnos which lives through
2129 function calls. This is called only when we found all intersected
2130 calls during building allocno live ranges. */
2131 void
2132 ira_tune_allocno_costs (void)
2134 int j, n, regno;
2135 int cost, min_cost, *reg_costs;
2136 enum reg_class aclass, rclass;
2137 enum machine_mode mode;
2138 ira_allocno_t a;
2139 ira_allocno_iterator ai;
2140 ira_allocno_object_iterator oi;
2141 ira_object_t obj;
2142 bool skip_p;
2144 FOR_EACH_ALLOCNO (a, ai)
2146 aclass = ALLOCNO_CLASS (a);
2147 if (aclass == NO_REGS)
2148 continue;
2149 mode = ALLOCNO_MODE (a);
2150 n = ira_class_hard_regs_num[aclass];
2151 min_cost = INT_MAX;
2152 if (ALLOCNO_CALLS_CROSSED_NUM (a)
2153 != ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2155 ira_allocate_and_set_costs
2156 (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2157 ALLOCNO_CLASS_COST (a));
2158 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2159 for (j = n - 1; j >= 0; j--)
2161 regno = ira_class_hard_regs[aclass][j];
2162 skip_p = false;
2163 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2165 if (ira_hard_reg_set_intersection_p (regno, mode,
2166 OBJECT_CONFLICT_HARD_REGS
2167 (obj)))
2169 skip_p = true;
2170 break;
2173 if (skip_p)
2174 continue;
2175 rclass = REGNO_REG_CLASS (regno);
2176 cost = 0;
2177 if (ira_hard_reg_set_intersection_p (regno, mode, call_used_reg_set)
2178 || HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
2179 cost += (ALLOCNO_CALL_FREQ (a)
2180 * (ira_memory_move_cost[mode][rclass][0]
2181 + ira_memory_move_cost[mode][rclass][1]));
2182 #ifdef IRA_HARD_REGNO_ADD_COST_MULTIPLIER
2183 cost += ((ira_memory_move_cost[mode][rclass][0]
2184 + ira_memory_move_cost[mode][rclass][1])
2185 * ALLOCNO_FREQ (a)
2186 * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno) / 2);
2187 #endif
2188 if (INT_MAX - cost < reg_costs[j])
2189 reg_costs[j] = INT_MAX;
2190 else
2191 reg_costs[j] += cost;
2192 if (min_cost > reg_costs[j])
2193 min_cost = reg_costs[j];
2196 if (min_cost != INT_MAX)
2197 ALLOCNO_CLASS_COST (a) = min_cost;
2199 /* Some targets allow pseudos to be allocated to unaligned sequences
2200 of hard registers. However, selecting an unaligned sequence can
2201 unnecessarily restrict later allocations. So increase the cost of
2202 unaligned hard regs to encourage the use of aligned hard regs. */
2204 const int nregs = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2206 if (nregs > 1)
2208 ira_allocate_and_set_costs
2209 (&ALLOCNO_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a));
2210 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2211 for (j = n - 1; j >= 0; j--)
2213 regno = ira_non_ordered_class_hard_regs[aclass][j];
2214 if ((regno % nregs) != 0)
2216 int index = ira_class_hard_reg_index[aclass][regno];
2217 ira_assert (index != -1);
2218 reg_costs[index] += ALLOCNO_FREQ (a);
2226 /* Add COST to the estimated gain for eliminating REGNO with its
2227 equivalence. If COST is zero, record that no such elimination is
2228 possible. */
2230 void
2231 ira_adjust_equiv_reg_cost (unsigned regno, int cost)
2233 if (cost == 0)
2234 regno_equiv_gains[regno] = 0;
2235 else
2236 regno_equiv_gains[regno] += cost;