* gcc.dg/store-motion-fgcse-sm.c (dg-final): Cleanup
[official-gcc.git] / gcc / ira-costs.c
blob2dabead6269c2821c2b4fdcb93a4b26e9f64be93
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 "predict.h"
32 #include "vec.h"
33 #include "hashtab.h"
34 #include "hash-set.h"
35 #include "machmode.h"
36 #include "input.h"
37 #include "function.h"
38 #include "dominance.h"
39 #include "cfg.h"
40 #include "basic-block.h"
41 #include "regs.h"
42 #include "addresses.h"
43 #include "insn-config.h"
44 #include "recog.h"
45 #include "reload.h"
46 #include "diagnostic-core.h"
47 #include "target.h"
48 #include "params.h"
49 #include "ira-int.h"
51 /* The flags is set up every time when we calculate pseudo register
52 classes through function ira_set_pseudo_classes. */
53 static bool pseudo_classes_defined_p = false;
55 /* TRUE if we work with allocnos. Otherwise we work with pseudos. */
56 static bool allocno_p;
58 /* Number of elements in array `costs'. */
59 static int cost_elements_num;
61 /* The `costs' struct records the cost of using hard registers of each
62 class considered for the calculation and of using memory for each
63 allocno or pseudo. */
64 struct costs
66 int mem_cost;
67 /* Costs for register classes start here. We process only some
68 allocno classes. */
69 int cost[1];
72 #define max_struct_costs_size \
73 (this_target_ira_int->x_max_struct_costs_size)
74 #define init_cost \
75 (this_target_ira_int->x_init_cost)
76 #define temp_costs \
77 (this_target_ira_int->x_temp_costs)
78 #define op_costs \
79 (this_target_ira_int->x_op_costs)
80 #define this_op_costs \
81 (this_target_ira_int->x_this_op_costs)
83 /* Costs of each class for each allocno or pseudo. */
84 static struct costs *costs;
86 /* Accumulated costs of each class for each allocno. */
87 static struct costs *total_allocno_costs;
89 /* It is the current size of struct costs. */
90 static int struct_costs_size;
92 /* Return pointer to structure containing costs of allocno or pseudo
93 with given NUM in array ARR. */
94 #define COSTS(arr, num) \
95 ((struct costs *) ((char *) (arr) + (num) * struct_costs_size))
97 /* Return index in COSTS when processing reg with REGNO. */
98 #define COST_INDEX(regno) (allocno_p \
99 ? ALLOCNO_NUM (ira_curr_regno_allocno_map[regno]) \
100 : (int) regno)
102 /* Record register class preferences of each allocno or pseudo. Null
103 value means no preferences. It happens on the 1st iteration of the
104 cost calculation. */
105 static enum reg_class *pref;
107 /* Allocated buffers for pref. */
108 static enum reg_class *pref_buffer;
110 /* Record allocno class of each allocno with the same regno. */
111 static enum reg_class *regno_aclass;
113 /* Record cost gains for not allocating a register with an invariant
114 equivalence. */
115 static int *regno_equiv_gains;
117 /* Execution frequency of the current insn. */
118 static int frequency;
122 /* Info about reg classes whose costs are calculated for a pseudo. */
123 struct cost_classes
125 /* Number of the cost classes in the subsequent array. */
126 int num;
127 /* Container of the cost classes. */
128 enum reg_class classes[N_REG_CLASSES];
129 /* Map reg class -> index of the reg class in the previous array.
130 -1 if it is not a cost class. */
131 int index[N_REG_CLASSES];
132 /* Map hard regno index of first class in array CLASSES containing
133 the hard regno, -1 otherwise. */
134 int hard_regno_index[FIRST_PSEUDO_REGISTER];
137 /* Types of pointers to the structure above. */
138 typedef struct cost_classes *cost_classes_t;
139 typedef const struct cost_classes *const_cost_classes_t;
141 /* Info about cost classes for each pseudo. */
142 static cost_classes_t *regno_cost_classes;
144 /* Helper for cost_classes hashing. */
146 struct cost_classes_hasher
148 typedef cost_classes value_type;
149 typedef cost_classes compare_type;
150 static inline hashval_t hash (const value_type *);
151 static inline bool equal (const value_type *, const compare_type *);
152 static inline void remove (value_type *);
155 /* Returns hash value for cost classes info HV. */
156 inline hashval_t
157 cost_classes_hasher::hash (const value_type *hv)
159 return iterative_hash (&hv->classes, sizeof (enum reg_class) * hv->num, 0);
162 /* Compares cost classes info HV1 and HV2. */
163 inline bool
164 cost_classes_hasher::equal (const value_type *hv1, const compare_type *hv2)
166 return (hv1->num == hv2->num
167 && memcmp (hv1->classes, hv2->classes,
168 sizeof (enum reg_class) * hv1->num) == 0);
171 /* Delete cost classes info V from the hash table. */
172 inline void
173 cost_classes_hasher::remove (value_type *v)
175 ira_free (v);
178 /* Hash table of unique cost classes. */
179 static hash_table<cost_classes_hasher> *cost_classes_htab;
181 /* Map allocno class -> cost classes for pseudo of given allocno
182 class. */
183 static cost_classes_t cost_classes_aclass_cache[N_REG_CLASSES];
185 /* Map mode -> cost classes for pseudo of give mode. */
186 static cost_classes_t cost_classes_mode_cache[MAX_MACHINE_MODE];
188 /* Cost classes that include all classes in ira_important_classes. */
189 static cost_classes all_cost_classes;
191 /* Use the array of classes in CLASSES_PTR to fill out the rest of
192 the structure. */
193 static void
194 complete_cost_classes (cost_classes_t classes_ptr)
196 for (int i = 0; i < N_REG_CLASSES; i++)
197 classes_ptr->index[i] = -1;
198 for (int i = 0; i < FIRST_PSEUDO_REGISTER; i++)
199 classes_ptr->hard_regno_index[i] = -1;
200 for (int i = 0; i < classes_ptr->num; i++)
202 enum reg_class cl = classes_ptr->classes[i];
203 classes_ptr->index[cl] = i;
204 for (int j = ira_class_hard_regs_num[cl] - 1; j >= 0; j--)
206 unsigned int hard_regno = ira_class_hard_regs[cl][j];
207 if (classes_ptr->hard_regno_index[hard_regno] < 0)
208 classes_ptr->hard_regno_index[hard_regno] = i;
213 /* Initialize info about the cost classes for each pseudo. */
214 static void
215 initiate_regno_cost_classes (void)
217 int size = sizeof (cost_classes_t) * max_reg_num ();
219 regno_cost_classes = (cost_classes_t *) ira_allocate (size);
220 memset (regno_cost_classes, 0, size);
221 memset (cost_classes_aclass_cache, 0,
222 sizeof (cost_classes_t) * N_REG_CLASSES);
223 memset (cost_classes_mode_cache, 0,
224 sizeof (cost_classes_t) * MAX_MACHINE_MODE);
225 cost_classes_htab = new hash_table<cost_classes_hasher> (200);
226 all_cost_classes.num = ira_important_classes_num;
227 for (int i = 0; i < ira_important_classes_num; i++)
228 all_cost_classes.classes[i] = ira_important_classes[i];
229 complete_cost_classes (&all_cost_classes);
232 /* Create new cost classes from cost classes FROM and set up members
233 index and hard_regno_index. Return the new classes. The function
234 implements some common code of two functions
235 setup_regno_cost_classes_by_aclass and
236 setup_regno_cost_classes_by_mode. */
237 static cost_classes_t
238 setup_cost_classes (cost_classes_t from)
240 cost_classes_t classes_ptr;
242 classes_ptr = (cost_classes_t) ira_allocate (sizeof (struct cost_classes));
243 classes_ptr->num = from->num;
244 for (int i = 0; i < from->num; i++)
245 classes_ptr->classes[i] = from->classes[i];
246 complete_cost_classes (classes_ptr);
247 return classes_ptr;
250 /* Return a version of FULL that only considers registers in REGS that are
251 valid for mode MODE. Both FULL and the returned class are globally
252 allocated. */
253 static cost_classes_t
254 restrict_cost_classes (cost_classes_t full, machine_mode mode,
255 const HARD_REG_SET &regs)
257 static struct cost_classes narrow;
258 int map[N_REG_CLASSES];
259 narrow.num = 0;
260 for (int i = 0; i < full->num; i++)
262 /* Assume that we'll drop the class. */
263 map[i] = -1;
265 /* Ignore classes that are too small for the mode. */
266 enum reg_class cl = full->classes[i];
267 if (!contains_reg_of_mode[cl][mode])
268 continue;
270 /* Calculate the set of registers in CL that belong to REGS and
271 are valid for MODE. */
272 HARD_REG_SET valid_for_cl;
273 COPY_HARD_REG_SET (valid_for_cl, reg_class_contents[cl]);
274 AND_HARD_REG_SET (valid_for_cl, regs);
275 AND_COMPL_HARD_REG_SET (valid_for_cl,
276 ira_prohibited_class_mode_regs[cl][mode]);
277 AND_COMPL_HARD_REG_SET (valid_for_cl, ira_no_alloc_regs);
278 if (hard_reg_set_empty_p (valid_for_cl))
279 continue;
281 /* Don't use this class if the set of valid registers is a subset
282 of an existing class. For example, suppose we have two classes
283 GR_REGS and FR_REGS and a union class GR_AND_FR_REGS. Suppose
284 that the mode changes allowed by FR_REGS are not as general as
285 the mode changes allowed by GR_REGS.
287 In this situation, the mode changes for GR_AND_FR_REGS could
288 either be seen as the union or the intersection of the mode
289 changes allowed by the two subclasses. The justification for
290 the union-based definition would be that, if you want a mode
291 change that's only allowed by GR_REGS, you can pick a register
292 from the GR_REGS subclass. The justification for the
293 intersection-based definition would be that every register
294 from the class would allow the mode change.
296 However, if we have a register that needs to be in GR_REGS,
297 using GR_AND_FR_REGS with the intersection-based definition
298 would be too pessimistic, since it would bring in restrictions
299 that only apply to FR_REGS. Conversely, if we have a register
300 that needs to be in FR_REGS, using GR_AND_FR_REGS with the
301 union-based definition would lose the extra restrictions
302 placed on FR_REGS. GR_AND_FR_REGS is therefore only useful
303 for cases where GR_REGS and FP_REGS are both valid. */
304 int pos;
305 for (pos = 0; pos < narrow.num; ++pos)
307 enum reg_class cl2 = narrow.classes[pos];
308 if (hard_reg_set_subset_p (valid_for_cl, reg_class_contents[cl2]))
309 break;
311 map[i] = pos;
312 if (pos == narrow.num)
314 /* If several classes are equivalent, prefer to use the one
315 that was chosen as the allocno class. */
316 enum reg_class cl2 = ira_allocno_class_translate[cl];
317 if (ira_class_hard_regs_num[cl] == ira_class_hard_regs_num[cl2])
318 cl = cl2;
319 narrow.classes[narrow.num++] = cl;
322 if (narrow.num == full->num)
323 return full;
325 cost_classes **slot = cost_classes_htab->find_slot (&narrow, INSERT);
326 if (*slot == NULL)
328 cost_classes_t classes = setup_cost_classes (&narrow);
329 /* Map equivalent classes to the representative that we chose above. */
330 for (int i = 0; i < ira_important_classes_num; i++)
332 enum reg_class cl = ira_important_classes[i];
333 int index = full->index[cl];
334 if (index >= 0)
335 classes->index[cl] = map[index];
337 *slot = classes;
339 return *slot;
342 /* Setup cost classes for pseudo REGNO whose allocno class is ACLASS.
343 This function is used when we know an initial approximation of
344 allocno class of the pseudo already, e.g. on the second iteration
345 of class cost calculation or after class cost calculation in
346 register-pressure sensitive insn scheduling or register-pressure
347 sensitive loop-invariant motion. */
348 static void
349 setup_regno_cost_classes_by_aclass (int regno, enum reg_class aclass)
351 static struct cost_classes classes;
352 cost_classes_t classes_ptr;
353 enum reg_class cl;
354 int i;
355 cost_classes **slot;
356 HARD_REG_SET temp, temp2;
357 bool exclude_p;
359 if ((classes_ptr = cost_classes_aclass_cache[aclass]) == NULL)
361 COPY_HARD_REG_SET (temp, reg_class_contents[aclass]);
362 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
363 /* We exclude classes from consideration which are subsets of
364 ACLASS only if ACLASS is an uniform class. */
365 exclude_p = ira_uniform_class_p[aclass];
366 classes.num = 0;
367 for (i = 0; i < ira_important_classes_num; i++)
369 cl = ira_important_classes[i];
370 if (exclude_p)
372 /* Exclude non-uniform classes which are subsets of
373 ACLASS. */
374 COPY_HARD_REG_SET (temp2, reg_class_contents[cl]);
375 AND_COMPL_HARD_REG_SET (temp2, ira_no_alloc_regs);
376 if (hard_reg_set_subset_p (temp2, temp) && cl != aclass)
377 continue;
379 classes.classes[classes.num++] = cl;
381 slot = cost_classes_htab->find_slot (&classes, INSERT);
382 if (*slot == NULL)
384 classes_ptr = setup_cost_classes (&classes);
385 *slot = classes_ptr;
387 classes_ptr = cost_classes_aclass_cache[aclass] = (cost_classes_t) *slot;
389 if (regno_reg_rtx[regno] != NULL_RTX)
391 /* Restrict the classes to those that are valid for REGNO's mode
392 (which might for example exclude singleton classes if the mode
393 requires two registers). Also restrict the classes to those that
394 are valid for subregs of REGNO. */
395 const HARD_REG_SET *valid_regs = valid_mode_changes_for_regno (regno);
396 if (!valid_regs)
397 valid_regs = &reg_class_contents[ALL_REGS];
398 classes_ptr = restrict_cost_classes (classes_ptr,
399 PSEUDO_REGNO_MODE (regno),
400 *valid_regs);
402 regno_cost_classes[regno] = classes_ptr;
405 /* Setup cost classes for pseudo REGNO with MODE. Usage of MODE can
406 decrease number of cost classes for the pseudo, if hard registers
407 of some important classes can not hold a value of MODE. So the
408 pseudo can not get hard register of some important classes and cost
409 calculation for such important classes is only wasting CPU
410 time. */
411 static void
412 setup_regno_cost_classes_by_mode (int regno, machine_mode mode)
414 if (const HARD_REG_SET *valid_regs = valid_mode_changes_for_regno (regno))
415 regno_cost_classes[regno] = restrict_cost_classes (&all_cost_classes,
416 mode, *valid_regs);
417 else
419 if (cost_classes_mode_cache[mode] == NULL)
420 cost_classes_mode_cache[mode]
421 = restrict_cost_classes (&all_cost_classes, mode,
422 reg_class_contents[ALL_REGS]);
423 regno_cost_classes[regno] = cost_classes_mode_cache[mode];
427 /* Finalize info about the cost classes for each pseudo. */
428 static void
429 finish_regno_cost_classes (void)
431 ira_free (regno_cost_classes);
432 delete cost_classes_htab;
433 cost_classes_htab = NULL;
438 /* Compute the cost of loading X into (if TO_P is TRUE) or from (if
439 TO_P is FALSE) a register of class RCLASS in mode MODE. X must not
440 be a pseudo register. */
441 static int
442 copy_cost (rtx x, machine_mode mode, reg_class_t rclass, bool to_p,
443 secondary_reload_info *prev_sri)
445 secondary_reload_info sri;
446 reg_class_t secondary_class = NO_REGS;
448 /* If X is a SCRATCH, there is actually nothing to move since we are
449 assuming optimal allocation. */
450 if (GET_CODE (x) == SCRATCH)
451 return 0;
453 /* Get the class we will actually use for a reload. */
454 rclass = targetm.preferred_reload_class (x, rclass);
456 /* If we need a secondary reload for an intermediate, the cost is
457 that to load the input into the intermediate register, then to
458 copy it. */
459 sri.prev_sri = prev_sri;
460 sri.extra_cost = 0;
461 secondary_class = targetm.secondary_reload (to_p, x, rclass, mode, &sri);
463 if (secondary_class != NO_REGS)
465 ira_init_register_move_cost_if_necessary (mode);
466 return (ira_register_move_cost[mode][(int) secondary_class][(int) rclass]
467 + sri.extra_cost
468 + copy_cost (x, mode, secondary_class, to_p, &sri));
471 /* For memory, use the memory move cost, for (hard) registers, use
472 the cost to move between the register classes, and use 2 for
473 everything else (constants). */
474 if (MEM_P (x) || rclass == NO_REGS)
475 return sri.extra_cost
476 + ira_memory_move_cost[mode][(int) rclass][to_p != 0];
477 else if (REG_P (x))
479 reg_class_t x_class = REGNO_REG_CLASS (REGNO (x));
481 ira_init_register_move_cost_if_necessary (mode);
482 return (sri.extra_cost
483 + ira_register_move_cost[mode][(int) x_class][(int) rclass]);
485 else
486 /* If this is a constant, we may eventually want to call rtx_cost
487 here. */
488 return sri.extra_cost + COSTS_N_INSNS (1);
493 /* Record the cost of using memory or hard registers of various
494 classes for the operands in INSN.
496 N_ALTS is the number of alternatives.
497 N_OPS is the number of operands.
498 OPS is an array of the operands.
499 MODES are the modes of the operands, in case any are VOIDmode.
500 CONSTRAINTS are the constraints to use for the operands. This array
501 is modified by this procedure.
503 This procedure works alternative by alternative. For each
504 alternative we assume that we will be able to allocate all allocnos
505 to their ideal register class and calculate the cost of using that
506 alternative. Then we compute, for each operand that is a
507 pseudo-register, the cost of having the allocno allocated to each
508 register class and using it in that alternative. To this cost is
509 added the cost of the alternative.
511 The cost of each class for this insn is its lowest cost among all
512 the alternatives. */
513 static void
514 record_reg_classes (int n_alts, int n_ops, rtx *ops,
515 machine_mode *modes, const char **constraints,
516 rtx_insn *insn, enum reg_class *pref)
518 int alt;
519 int i, j, k;
520 int insn_allows_mem[MAX_RECOG_OPERANDS];
521 move_table *move_in_cost, *move_out_cost;
522 short (*mem_cost)[2];
524 for (i = 0; i < n_ops; i++)
525 insn_allows_mem[i] = 0;
527 /* Process each alternative, each time minimizing an operand's cost
528 with the cost for each operand in that alternative. */
529 alternative_mask preferred = get_preferred_alternatives (insn);
530 for (alt = 0; alt < n_alts; alt++)
532 enum reg_class classes[MAX_RECOG_OPERANDS];
533 int allows_mem[MAX_RECOG_OPERANDS];
534 enum reg_class rclass;
535 int alt_fail = 0;
536 int alt_cost = 0, op_cost_add;
538 if (!TEST_BIT (preferred, alt))
540 for (i = 0; i < recog_data.n_operands; i++)
541 constraints[i] = skip_alternative (constraints[i]);
543 continue;
546 for (i = 0; i < n_ops; i++)
548 unsigned char c;
549 const char *p = constraints[i];
550 rtx op = ops[i];
551 machine_mode mode = modes[i];
552 int allows_addr = 0;
553 int win = 0;
555 /* Initially show we know nothing about the register class. */
556 classes[i] = NO_REGS;
557 allows_mem[i] = 0;
559 /* If this operand has no constraints at all, we can
560 conclude nothing about it since anything is valid. */
561 if (*p == 0)
563 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
564 memset (this_op_costs[i], 0, struct_costs_size);
565 continue;
568 /* If this alternative is only relevant when this operand
569 matches a previous operand, we do different things
570 depending on whether this operand is a allocno-reg or not.
571 We must process any modifiers for the operand before we
572 can make this test. */
573 while (*p == '%' || *p == '=' || *p == '+' || *p == '&')
574 p++;
576 if (p[0] >= '0' && p[0] <= '0' + i && (p[1] == ',' || p[1] == 0))
578 /* Copy class and whether memory is allowed from the
579 matching alternative. Then perform any needed cost
580 computations and/or adjustments. */
581 j = p[0] - '0';
582 classes[i] = classes[j];
583 allows_mem[i] = allows_mem[j];
584 if (allows_mem[i])
585 insn_allows_mem[i] = 1;
587 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
589 /* If this matches the other operand, we have no
590 added cost and we win. */
591 if (rtx_equal_p (ops[j], op))
592 win = 1;
593 /* If we can put the other operand into a register,
594 add to the cost of this alternative the cost to
595 copy this operand to the register used for the
596 other operand. */
597 else if (classes[j] != NO_REGS)
599 alt_cost += copy_cost (op, mode, classes[j], 1, NULL);
600 win = 1;
603 else if (! REG_P (ops[j])
604 || REGNO (ops[j]) < FIRST_PSEUDO_REGISTER)
606 /* This op is an allocno but the one it matches is
607 not. */
609 /* If we can't put the other operand into a
610 register, this alternative can't be used. */
612 if (classes[j] == NO_REGS)
613 alt_fail = 1;
614 /* Otherwise, add to the cost of this alternative
615 the cost to copy the other operand to the hard
616 register used for this operand. */
617 else
618 alt_cost += copy_cost (ops[j], mode, classes[j], 1, NULL);
620 else
622 /* The costs of this operand are not the same as the
623 other operand since move costs are not symmetric.
624 Moreover, if we cannot tie them, this alternative
625 needs to do a copy, which is one insn. */
626 struct costs *pp = this_op_costs[i];
627 int *pp_costs = pp->cost;
628 cost_classes_t cost_classes_ptr
629 = regno_cost_classes[REGNO (op)];
630 enum reg_class *cost_classes = cost_classes_ptr->classes;
631 bool in_p = recog_data.operand_type[i] != OP_OUT;
632 bool out_p = recog_data.operand_type[i] != OP_IN;
633 enum reg_class op_class = classes[i];
635 ira_init_register_move_cost_if_necessary (mode);
636 if (! in_p)
638 ira_assert (out_p);
639 if (op_class == NO_REGS)
641 mem_cost = ira_memory_move_cost[mode];
642 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
644 rclass = cost_classes[k];
645 pp_costs[k] = mem_cost[rclass][0] * frequency;
648 else
650 move_out_cost = ira_may_move_out_cost[mode];
651 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
653 rclass = cost_classes[k];
654 pp_costs[k]
655 = move_out_cost[op_class][rclass] * frequency;
659 else if (! out_p)
661 ira_assert (in_p);
662 if (op_class == NO_REGS)
664 mem_cost = ira_memory_move_cost[mode];
665 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
667 rclass = cost_classes[k];
668 pp_costs[k] = mem_cost[rclass][1] * frequency;
671 else
673 move_in_cost = ira_may_move_in_cost[mode];
674 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
676 rclass = cost_classes[k];
677 pp_costs[k]
678 = move_in_cost[rclass][op_class] * frequency;
682 else
684 if (op_class == NO_REGS)
686 mem_cost = ira_memory_move_cost[mode];
687 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
689 rclass = cost_classes[k];
690 pp_costs[k] = ((mem_cost[rclass][0]
691 + mem_cost[rclass][1])
692 * frequency);
695 else
697 move_in_cost = ira_may_move_in_cost[mode];
698 move_out_cost = ira_may_move_out_cost[mode];
699 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
701 rclass = cost_classes[k];
702 pp_costs[k] = ((move_in_cost[rclass][op_class]
703 + move_out_cost[op_class][rclass])
704 * frequency);
709 /* If the alternative actually allows memory, make
710 things a bit cheaper since we won't need an extra
711 insn to load it. */
712 pp->mem_cost
713 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
714 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
715 - allows_mem[i]) * frequency;
717 /* If we have assigned a class to this allocno in
718 our first pass, add a cost to this alternative
719 corresponding to what we would add if this
720 allocno were not in the appropriate class. */
721 if (pref)
723 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
725 if (pref_class == NO_REGS)
726 alt_cost
727 += ((out_p
728 ? ira_memory_move_cost[mode][op_class][0] : 0)
729 + (in_p
730 ? ira_memory_move_cost[mode][op_class][1]
731 : 0));
732 else if (ira_reg_class_intersect
733 [pref_class][op_class] == NO_REGS)
734 alt_cost
735 += ira_register_move_cost[mode][pref_class][op_class];
737 if (REGNO (ops[i]) != REGNO (ops[j])
738 && ! find_reg_note (insn, REG_DEAD, op))
739 alt_cost += 2;
741 /* This is in place of ordinary cost computation for
742 this operand, so skip to the end of the
743 alternative (should be just one character). */
744 while (*p && *p++ != ',')
747 constraints[i] = p;
748 continue;
752 /* Scan all the constraint letters. See if the operand
753 matches any of the constraints. Collect the valid
754 register classes and see if this operand accepts
755 memory. */
756 while ((c = *p))
758 switch (c)
760 case '*':
761 /* Ignore the next letter for this pass. */
762 c = *++p;
763 break;
765 case '?':
766 alt_cost += 2;
767 break;
769 case 'g':
770 if (MEM_P (op)
771 || (CONSTANT_P (op)
772 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))))
773 win = 1;
774 insn_allows_mem[i] = allows_mem[i] = 1;
775 classes[i] = ira_reg_class_subunion[classes[i]][GENERAL_REGS];
776 break;
778 default:
779 enum constraint_num cn = lookup_constraint (p);
780 enum reg_class cl;
781 switch (get_constraint_type (cn))
783 case CT_REGISTER:
784 cl = reg_class_for_constraint (cn);
785 if (cl != NO_REGS)
786 classes[i] = ira_reg_class_subunion[classes[i]][cl];
787 break;
789 case CT_CONST_INT:
790 if (CONST_INT_P (op)
791 && insn_const_int_ok_for_constraint (INTVAL (op), cn))
792 win = 1;
793 break;
795 case CT_MEMORY:
796 /* Every MEM can be reloaded to fit. */
797 insn_allows_mem[i] = allows_mem[i] = 1;
798 if (MEM_P (op))
799 win = 1;
800 break;
802 case CT_ADDRESS:
803 /* Every address can be reloaded to fit. */
804 allows_addr = 1;
805 if (address_operand (op, GET_MODE (op))
806 || constraint_satisfied_p (op, cn))
807 win = 1;
808 /* We know this operand is an address, so we
809 want it to be allocated to a hard register
810 that can be the base of an address,
811 i.e. BASE_REG_CLASS. */
812 classes[i]
813 = ira_reg_class_subunion[classes[i]]
814 [base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
815 ADDRESS, SCRATCH)];
816 break;
818 case CT_FIXED_FORM:
819 if (constraint_satisfied_p (op, cn))
820 win = 1;
821 break;
823 break;
825 p += CONSTRAINT_LEN (c, p);
826 if (c == ',')
827 break;
830 constraints[i] = p;
832 /* How we account for this operand now depends on whether it
833 is a pseudo register or not. If it is, we first check if
834 any register classes are valid. If not, we ignore this
835 alternative, since we want to assume that all allocnos get
836 allocated for register preferencing. If some register
837 class is valid, compute the costs of moving the allocno
838 into that class. */
839 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
841 if (classes[i] == NO_REGS && ! allows_mem[i])
843 /* We must always fail if the operand is a REG, but
844 we did not find a suitable class and memory is
845 not allowed.
847 Otherwise we may perform an uninitialized read
848 from this_op_costs after the `continue' statement
849 below. */
850 alt_fail = 1;
852 else
854 unsigned int regno = REGNO (op);
855 struct costs *pp = this_op_costs[i];
856 int *pp_costs = pp->cost;
857 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
858 enum reg_class *cost_classes = cost_classes_ptr->classes;
859 bool in_p = recog_data.operand_type[i] != OP_OUT;
860 bool out_p = recog_data.operand_type[i] != OP_IN;
861 enum reg_class op_class = classes[i];
863 ira_init_register_move_cost_if_necessary (mode);
864 if (! in_p)
866 ira_assert (out_p);
867 if (op_class == NO_REGS)
869 mem_cost = ira_memory_move_cost[mode];
870 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
872 rclass = cost_classes[k];
873 pp_costs[k] = mem_cost[rclass][0] * frequency;
876 else
878 move_out_cost = ira_may_move_out_cost[mode];
879 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
881 rclass = cost_classes[k];
882 pp_costs[k]
883 = move_out_cost[op_class][rclass] * frequency;
887 else if (! out_p)
889 ira_assert (in_p);
890 if (op_class == NO_REGS)
892 mem_cost = ira_memory_move_cost[mode];
893 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
895 rclass = cost_classes[k];
896 pp_costs[k] = mem_cost[rclass][1] * frequency;
899 else
901 move_in_cost = ira_may_move_in_cost[mode];
902 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
904 rclass = cost_classes[k];
905 pp_costs[k]
906 = move_in_cost[rclass][op_class] * frequency;
910 else
912 if (op_class == NO_REGS)
914 mem_cost = ira_memory_move_cost[mode];
915 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
917 rclass = cost_classes[k];
918 pp_costs[k] = ((mem_cost[rclass][0]
919 + mem_cost[rclass][1])
920 * frequency);
923 else
925 move_in_cost = ira_may_move_in_cost[mode];
926 move_out_cost = ira_may_move_out_cost[mode];
927 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
929 rclass = cost_classes[k];
930 pp_costs[k] = ((move_in_cost[rclass][op_class]
931 + move_out_cost[op_class][rclass])
932 * frequency);
937 if (op_class == NO_REGS)
938 /* Although we don't need insn to reload from
939 memory, still accessing memory is usually more
940 expensive than a register. */
941 pp->mem_cost = frequency;
942 else
943 /* If the alternative actually allows memory, make
944 things a bit cheaper since we won't need an
945 extra insn to load it. */
946 pp->mem_cost
947 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
948 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
949 - allows_mem[i]) * frequency;
950 /* If we have assigned a class to this allocno in
951 our first pass, add a cost to this alternative
952 corresponding to what we would add if this
953 allocno were not in the appropriate class. */
954 if (pref)
956 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
958 if (pref_class == NO_REGS)
960 if (op_class != NO_REGS)
961 alt_cost
962 += ((out_p
963 ? ira_memory_move_cost[mode][op_class][0]
964 : 0)
965 + (in_p
966 ? ira_memory_move_cost[mode][op_class][1]
967 : 0));
969 else if (op_class == NO_REGS)
970 alt_cost
971 += ((out_p
972 ? ira_memory_move_cost[mode][pref_class][1]
973 : 0)
974 + (in_p
975 ? ira_memory_move_cost[mode][pref_class][0]
976 : 0));
977 else if (ira_reg_class_intersect[pref_class][op_class]
978 == NO_REGS)
979 alt_cost += (ira_register_move_cost
980 [mode][pref_class][op_class]);
985 /* Otherwise, if this alternative wins, either because we
986 have already determined that or if we have a hard
987 register of the proper class, there is no cost for this
988 alternative. */
989 else if (win || (REG_P (op)
990 && reg_fits_class_p (op, classes[i],
991 0, GET_MODE (op))))
994 /* If registers are valid, the cost of this alternative
995 includes copying the object to and/or from a
996 register. */
997 else if (classes[i] != NO_REGS)
999 if (recog_data.operand_type[i] != OP_OUT)
1000 alt_cost += copy_cost (op, mode, classes[i], 1, NULL);
1002 if (recog_data.operand_type[i] != OP_IN)
1003 alt_cost += copy_cost (op, mode, classes[i], 0, NULL);
1005 /* The only other way this alternative can be used is if
1006 this is a constant that could be placed into memory. */
1007 else if (CONSTANT_P (op) && (allows_addr || allows_mem[i]))
1008 alt_cost += ira_memory_move_cost[mode][classes[i]][1];
1009 else
1010 alt_fail = 1;
1013 if (alt_fail)
1014 continue;
1016 op_cost_add = alt_cost * frequency;
1017 /* Finally, update the costs with the information we've
1018 calculated about this alternative. */
1019 for (i = 0; i < n_ops; i++)
1020 if (REG_P (ops[i]) && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
1022 struct costs *pp = op_costs[i], *qq = this_op_costs[i];
1023 int *pp_costs = pp->cost, *qq_costs = qq->cost;
1024 int scale = 1 + (recog_data.operand_type[i] == OP_INOUT);
1025 cost_classes_t cost_classes_ptr
1026 = regno_cost_classes[REGNO (ops[i])];
1028 pp->mem_cost = MIN (pp->mem_cost,
1029 (qq->mem_cost + op_cost_add) * scale);
1031 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1032 pp_costs[k]
1033 = MIN (pp_costs[k], (qq_costs[k] + op_cost_add) * scale);
1037 if (allocno_p)
1038 for (i = 0; i < n_ops; i++)
1040 ira_allocno_t a;
1041 rtx op = ops[i];
1043 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
1044 continue;
1045 a = ira_curr_regno_allocno_map [REGNO (op)];
1046 if (! ALLOCNO_BAD_SPILL_P (a) && insn_allows_mem[i] == 0)
1047 ALLOCNO_BAD_SPILL_P (a) = true;
1054 /* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudo registers. */
1055 static inline bool
1056 ok_for_index_p_nonstrict (rtx reg)
1058 unsigned regno = REGNO (reg);
1060 return regno >= FIRST_PSEUDO_REGISTER || REGNO_OK_FOR_INDEX_P (regno);
1063 /* A version of regno_ok_for_base_p for use here, when all
1064 pseudo-registers should count as OK. Arguments as for
1065 regno_ok_for_base_p. */
1066 static inline bool
1067 ok_for_base_p_nonstrict (rtx reg, machine_mode mode, addr_space_t as,
1068 enum rtx_code outer_code, enum rtx_code index_code)
1070 unsigned regno = REGNO (reg);
1072 if (regno >= FIRST_PSEUDO_REGISTER)
1073 return true;
1074 return ok_for_base_p_1 (regno, mode, as, outer_code, index_code);
1077 /* Record the pseudo registers we must reload into hard registers in a
1078 subexpression of a memory address, X.
1080 If CONTEXT is 0, we are looking at the base part of an address,
1081 otherwise we are looking at the index part.
1083 MODE and AS are the mode and address space of the memory reference;
1084 OUTER_CODE and INDEX_CODE give the context that the rtx appears in.
1085 These four arguments are passed down to base_reg_class.
1087 SCALE is twice the amount to multiply the cost by (it is twice so
1088 we can represent half-cost adjustments). */
1089 static void
1090 record_address_regs (machine_mode mode, addr_space_t as, rtx x,
1091 int context, enum rtx_code outer_code,
1092 enum rtx_code index_code, int scale)
1094 enum rtx_code code = GET_CODE (x);
1095 enum reg_class rclass;
1097 if (context == 1)
1098 rclass = INDEX_REG_CLASS;
1099 else
1100 rclass = base_reg_class (mode, as, outer_code, index_code);
1102 switch (code)
1104 case CONST_INT:
1105 case CONST:
1106 case CC0:
1107 case PC:
1108 case SYMBOL_REF:
1109 case LABEL_REF:
1110 return;
1112 case PLUS:
1113 /* When we have an address that is a sum, we must determine
1114 whether registers are "base" or "index" regs. If there is a
1115 sum of two registers, we must choose one to be the "base".
1116 Luckily, we can use the REG_POINTER to make a good choice
1117 most of the time. We only need to do this on machines that
1118 can have two registers in an address and where the base and
1119 index register classes are different.
1121 ??? This code used to set REGNO_POINTER_FLAG in some cases,
1122 but that seems bogus since it should only be set when we are
1123 sure the register is being used as a pointer. */
1125 rtx arg0 = XEXP (x, 0);
1126 rtx arg1 = XEXP (x, 1);
1127 enum rtx_code code0 = GET_CODE (arg0);
1128 enum rtx_code code1 = GET_CODE (arg1);
1130 /* Look inside subregs. */
1131 if (code0 == SUBREG)
1132 arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
1133 if (code1 == SUBREG)
1134 arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
1136 /* If this machine only allows one register per address, it
1137 must be in the first operand. */
1138 if (MAX_REGS_PER_ADDRESS == 1)
1139 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale);
1141 /* If index and base registers are the same on this machine,
1142 just record registers in any non-constant operands. We
1143 assume here, as well as in the tests below, that all
1144 addresses are in canonical form. */
1145 else if (INDEX_REG_CLASS
1146 == base_reg_class (VOIDmode, as, PLUS, SCRATCH))
1148 record_address_regs (mode, as, arg0, context, PLUS, code1, scale);
1149 if (! CONSTANT_P (arg1))
1150 record_address_regs (mode, as, arg1, context, PLUS, code0, scale);
1153 /* If the second operand is a constant integer, it doesn't
1154 change what class the first operand must be. */
1155 else if (CONST_SCALAR_INT_P (arg1))
1156 record_address_regs (mode, as, arg0, context, PLUS, code1, scale);
1157 /* If the second operand is a symbolic constant, the first
1158 operand must be an index register. */
1159 else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF)
1160 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale);
1161 /* If both operands are registers but one is already a hard
1162 register of index or reg-base class, give the other the
1163 class that the hard register is not. */
1164 else if (code0 == REG && code1 == REG
1165 && REGNO (arg0) < FIRST_PSEUDO_REGISTER
1166 && (ok_for_base_p_nonstrict (arg0, mode, as, PLUS, REG)
1167 || ok_for_index_p_nonstrict (arg0)))
1168 record_address_regs (mode, as, arg1,
1169 ok_for_base_p_nonstrict (arg0, mode, as,
1170 PLUS, REG) ? 1 : 0,
1171 PLUS, REG, scale);
1172 else if (code0 == REG && code1 == REG
1173 && REGNO (arg1) < FIRST_PSEUDO_REGISTER
1174 && (ok_for_base_p_nonstrict (arg1, mode, as, PLUS, REG)
1175 || ok_for_index_p_nonstrict (arg1)))
1176 record_address_regs (mode, as, arg0,
1177 ok_for_base_p_nonstrict (arg1, mode, as,
1178 PLUS, REG) ? 1 : 0,
1179 PLUS, REG, scale);
1180 /* If one operand is known to be a pointer, it must be the
1181 base with the other operand the index. Likewise if the
1182 other operand is a MULT. */
1183 else if ((code0 == REG && REG_POINTER (arg0)) || code1 == MULT)
1185 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale);
1186 record_address_regs (mode, as, arg1, 1, PLUS, code0, scale);
1188 else if ((code1 == REG && REG_POINTER (arg1)) || code0 == MULT)
1190 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale);
1191 record_address_regs (mode, as, arg1, 0, PLUS, code0, scale);
1193 /* Otherwise, count equal chances that each might be a base or
1194 index register. This case should be rare. */
1195 else
1197 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale / 2);
1198 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale / 2);
1199 record_address_regs (mode, as, arg1, 0, PLUS, code0, scale / 2);
1200 record_address_regs (mode, as, arg1, 1, PLUS, code0, scale / 2);
1203 break;
1205 /* Double the importance of an allocno that is incremented or
1206 decremented, since it would take two extra insns if it ends
1207 up in the wrong place. */
1208 case POST_MODIFY:
1209 case PRE_MODIFY:
1210 record_address_regs (mode, as, XEXP (x, 0), 0, code,
1211 GET_CODE (XEXP (XEXP (x, 1), 1)), 2 * scale);
1212 if (REG_P (XEXP (XEXP (x, 1), 1)))
1213 record_address_regs (mode, as, XEXP (XEXP (x, 1), 1), 1, code, REG,
1214 2 * scale);
1215 break;
1217 case POST_INC:
1218 case PRE_INC:
1219 case POST_DEC:
1220 case PRE_DEC:
1221 /* Double the importance of an allocno that is incremented or
1222 decremented, since it would take two extra insns if it ends
1223 up in the wrong place. */
1224 record_address_regs (mode, as, XEXP (x, 0), 0, code, SCRATCH, 2 * scale);
1225 break;
1227 case REG:
1229 struct costs *pp;
1230 int *pp_costs;
1231 enum reg_class i;
1232 int k, regno, add_cost;
1233 cost_classes_t cost_classes_ptr;
1234 enum reg_class *cost_classes;
1235 move_table *move_in_cost;
1237 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
1238 break;
1240 regno = REGNO (x);
1241 if (allocno_p)
1242 ALLOCNO_BAD_SPILL_P (ira_curr_regno_allocno_map[regno]) = true;
1243 pp = COSTS (costs, COST_INDEX (regno));
1244 add_cost = (ira_memory_move_cost[Pmode][rclass][1] * scale) / 2;
1245 if (INT_MAX - add_cost < pp->mem_cost)
1246 pp->mem_cost = INT_MAX;
1247 else
1248 pp->mem_cost += add_cost;
1249 cost_classes_ptr = regno_cost_classes[regno];
1250 cost_classes = cost_classes_ptr->classes;
1251 pp_costs = pp->cost;
1252 ira_init_register_move_cost_if_necessary (Pmode);
1253 move_in_cost = ira_may_move_in_cost[Pmode];
1254 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1256 i = cost_classes[k];
1257 add_cost = (move_in_cost[i][rclass] * scale) / 2;
1258 if (INT_MAX - add_cost < pp_costs[k])
1259 pp_costs[k] = INT_MAX;
1260 else
1261 pp_costs[k] += add_cost;
1264 break;
1266 default:
1268 const char *fmt = GET_RTX_FORMAT (code);
1269 int i;
1270 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1271 if (fmt[i] == 'e')
1272 record_address_regs (mode, as, XEXP (x, i), context, code, SCRATCH,
1273 scale);
1280 /* Calculate the costs of insn operands. */
1281 static void
1282 record_operand_costs (rtx_insn *insn, enum reg_class *pref)
1284 const char *constraints[MAX_RECOG_OPERANDS];
1285 machine_mode modes[MAX_RECOG_OPERANDS];
1286 rtx ops[MAX_RECOG_OPERANDS];
1287 rtx set;
1288 int i;
1290 for (i = 0; i < recog_data.n_operands; i++)
1292 constraints[i] = recog_data.constraints[i];
1293 modes[i] = recog_data.operand_mode[i];
1296 /* If we get here, we are set up to record the costs of all the
1297 operands for this insn. Start by initializing the costs. Then
1298 handle any address registers. Finally record the desired classes
1299 for any allocnos, doing it twice if some pair of operands are
1300 commutative. */
1301 for (i = 0; i < recog_data.n_operands; i++)
1303 memcpy (op_costs[i], init_cost, struct_costs_size);
1305 ops[i] = recog_data.operand[i];
1306 if (GET_CODE (recog_data.operand[i]) == SUBREG)
1307 recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);
1309 if (MEM_P (recog_data.operand[i]))
1310 record_address_regs (GET_MODE (recog_data.operand[i]),
1311 MEM_ADDR_SPACE (recog_data.operand[i]),
1312 XEXP (recog_data.operand[i], 0),
1313 0, MEM, SCRATCH, frequency * 2);
1314 else if (constraints[i][0] == 'p'
1315 || (insn_extra_address_constraint
1316 (lookup_constraint (constraints[i]))))
1317 record_address_regs (VOIDmode, ADDR_SPACE_GENERIC,
1318 recog_data.operand[i], 0, ADDRESS, SCRATCH,
1319 frequency * 2);
1322 /* Check for commutative in a separate loop so everything will have
1323 been initialized. We must do this even if one operand is a
1324 constant--see addsi3 in m68k.md. */
1325 for (i = 0; i < (int) recog_data.n_operands - 1; i++)
1326 if (constraints[i][0] == '%')
1328 const char *xconstraints[MAX_RECOG_OPERANDS];
1329 int j;
1331 /* Handle commutative operands by swapping the constraints.
1332 We assume the modes are the same. */
1333 for (j = 0; j < recog_data.n_operands; j++)
1334 xconstraints[j] = constraints[j];
1336 xconstraints[i] = constraints[i+1];
1337 xconstraints[i+1] = constraints[i];
1338 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1339 recog_data.operand, modes,
1340 xconstraints, insn, pref);
1342 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1343 recog_data.operand, modes,
1344 constraints, insn, pref);
1346 /* If this insn is a single set copying operand 1 to operand 0 and
1347 one operand is an allocno with the other a hard reg or an allocno
1348 that prefers a hard register that is in its own register class
1349 then we may want to adjust the cost of that register class to -1.
1351 Avoid the adjustment if the source does not die to avoid
1352 stressing of register allocator by preferencing two colliding
1353 registers into single class.
1355 Also avoid the adjustment if a copy between hard registers of the
1356 class is expensive (ten times the cost of a default copy is
1357 considered arbitrarily expensive). This avoids losing when the
1358 preferred class is very expensive as the source of a copy
1359 instruction. */
1360 if ((set = single_set (insn)) != NULL_RTX
1361 /* In rare cases the single set insn might have less 2 operands
1362 as the source can be a fixed special reg. */
1363 && recog_data.n_operands > 1
1364 && ops[0] == SET_DEST (set) && ops[1] == SET_SRC (set))
1366 int regno, other_regno;
1367 rtx dest = SET_DEST (set);
1368 rtx src = SET_SRC (set);
1370 dest = SET_DEST (set);
1371 src = SET_SRC (set);
1372 if (GET_CODE (dest) == SUBREG
1373 && (GET_MODE_SIZE (GET_MODE (dest))
1374 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))))
1375 dest = SUBREG_REG (dest);
1376 if (GET_CODE (src) == SUBREG
1377 && (GET_MODE_SIZE (GET_MODE (src))
1378 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
1379 src = SUBREG_REG (src);
1380 if (REG_P (src) && REG_P (dest)
1381 && find_regno_note (insn, REG_DEAD, REGNO (src))
1382 && (((regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
1383 && (other_regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER)
1384 || ((regno = REGNO (dest)) >= FIRST_PSEUDO_REGISTER
1385 && (other_regno = REGNO (src)) < FIRST_PSEUDO_REGISTER)))
1387 machine_mode mode = GET_MODE (src);
1388 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1389 enum reg_class *cost_classes = cost_classes_ptr->classes;
1390 reg_class_t rclass;
1391 int k, nr;
1393 i = regno == (int) REGNO (src) ? 1 : 0;
1394 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1396 rclass = cost_classes[k];
1397 if (TEST_HARD_REG_BIT (reg_class_contents[rclass], other_regno)
1398 && (reg_class_size[(int) rclass]
1399 == ira_reg_class_max_nregs [(int) rclass][(int) mode]))
1401 if (reg_class_size[rclass] == 1)
1402 op_costs[i]->cost[k] = -frequency;
1403 else
1405 for (nr = 0;
1406 nr < hard_regno_nregs[other_regno][mode];
1407 nr++)
1408 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass],
1409 other_regno + nr))
1410 break;
1412 if (nr == hard_regno_nregs[other_regno][mode])
1413 op_costs[i]->cost[k] = -frequency;
1423 /* Process one insn INSN. Scan it and record each time it would save
1424 code to put a certain allocnos in a certain class. Return the last
1425 insn processed, so that the scan can be continued from there. */
1426 static rtx_insn *
1427 scan_one_insn (rtx_insn *insn)
1429 enum rtx_code pat_code;
1430 rtx set, note;
1431 int i, k;
1432 bool counted_mem;
1434 if (!NONDEBUG_INSN_P (insn))
1435 return insn;
1437 pat_code = GET_CODE (PATTERN (insn));
1438 if (pat_code == USE || pat_code == CLOBBER || pat_code == ASM_INPUT)
1439 return insn;
1441 counted_mem = false;
1442 set = single_set (insn);
1443 extract_insn (insn);
1445 /* If this insn loads a parameter from its stack slot, then it
1446 represents a savings, rather than a cost, if the parameter is
1447 stored in memory. Record this fact.
1449 Similarly if we're loading other constants from memory (constant
1450 pool, TOC references, small data areas, etc) and this is the only
1451 assignment to the destination pseudo.
1453 Don't do this if SET_SRC (set) isn't a general operand, if it is
1454 a memory requiring special instructions to load it, decreasing
1455 mem_cost might result in it being loaded using the specialized
1456 instruction into a register, then stored into stack and loaded
1457 again from the stack. See PR52208.
1459 Don't do this if SET_SRC (set) has side effect. See PR56124. */
1460 if (set != 0 && REG_P (SET_DEST (set)) && MEM_P (SET_SRC (set))
1461 && (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL_RTX
1462 && ((MEM_P (XEXP (note, 0))
1463 && !side_effects_p (SET_SRC (set)))
1464 || (CONSTANT_P (XEXP (note, 0))
1465 && targetm.legitimate_constant_p (GET_MODE (SET_DEST (set)),
1466 XEXP (note, 0))
1467 && REG_N_SETS (REGNO (SET_DEST (set))) == 1))
1468 && general_operand (SET_SRC (set), GET_MODE (SET_SRC (set))))
1470 enum reg_class cl = GENERAL_REGS;
1471 rtx reg = SET_DEST (set);
1472 int num = COST_INDEX (REGNO (reg));
1474 COSTS (costs, num)->mem_cost
1475 -= ira_memory_move_cost[GET_MODE (reg)][cl][1] * frequency;
1476 record_address_regs (GET_MODE (SET_SRC (set)),
1477 MEM_ADDR_SPACE (SET_SRC (set)),
1478 XEXP (SET_SRC (set), 0), 0, MEM, SCRATCH,
1479 frequency * 2);
1480 counted_mem = true;
1483 record_operand_costs (insn, pref);
1485 /* Now add the cost for each operand to the total costs for its
1486 allocno. */
1487 for (i = 0; i < recog_data.n_operands; i++)
1488 if (REG_P (recog_data.operand[i])
1489 && REGNO (recog_data.operand[i]) >= FIRST_PSEUDO_REGISTER)
1491 int regno = REGNO (recog_data.operand[i]);
1492 struct costs *p = COSTS (costs, COST_INDEX (regno));
1493 struct costs *q = op_costs[i];
1494 int *p_costs = p->cost, *q_costs = q->cost;
1495 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1496 int add_cost;
1498 /* If the already accounted for the memory "cost" above, don't
1499 do so again. */
1500 if (!counted_mem)
1502 add_cost = q->mem_cost;
1503 if (add_cost > 0 && INT_MAX - add_cost < p->mem_cost)
1504 p->mem_cost = INT_MAX;
1505 else
1506 p->mem_cost += add_cost;
1508 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1510 add_cost = q_costs[k];
1511 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1512 p_costs[k] = INT_MAX;
1513 else
1514 p_costs[k] += add_cost;
1518 return insn;
1523 /* Print allocnos costs to file F. */
1524 static void
1525 print_allocno_costs (FILE *f)
1527 int k;
1528 ira_allocno_t a;
1529 ira_allocno_iterator ai;
1531 ira_assert (allocno_p);
1532 fprintf (f, "\n");
1533 FOR_EACH_ALLOCNO (a, ai)
1535 int i, rclass;
1536 basic_block bb;
1537 int regno = ALLOCNO_REGNO (a);
1538 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1539 enum reg_class *cost_classes = cost_classes_ptr->classes;
1541 i = ALLOCNO_NUM (a);
1542 fprintf (f, " a%d(r%d,", i, regno);
1543 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1544 fprintf (f, "b%d", bb->index);
1545 else
1546 fprintf (f, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
1547 fprintf (f, ") costs:");
1548 for (k = 0; k < cost_classes_ptr->num; k++)
1550 rclass = cost_classes[k];
1551 fprintf (f, " %s:%d", reg_class_names[rclass],
1552 COSTS (costs, i)->cost[k]);
1553 if (flag_ira_region == IRA_REGION_ALL
1554 || flag_ira_region == IRA_REGION_MIXED)
1555 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->cost[k]);
1557 fprintf (f, " MEM:%i", COSTS (costs, i)->mem_cost);
1558 if (flag_ira_region == IRA_REGION_ALL
1559 || flag_ira_region == IRA_REGION_MIXED)
1560 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->mem_cost);
1561 fprintf (f, "\n");
1565 /* Print pseudo costs to file F. */
1566 static void
1567 print_pseudo_costs (FILE *f)
1569 int regno, k;
1570 int rclass;
1571 cost_classes_t cost_classes_ptr;
1572 enum reg_class *cost_classes;
1574 ira_assert (! allocno_p);
1575 fprintf (f, "\n");
1576 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1578 if (REG_N_REFS (regno) <= 0)
1579 continue;
1580 cost_classes_ptr = regno_cost_classes[regno];
1581 cost_classes = cost_classes_ptr->classes;
1582 fprintf (f, " r%d costs:", regno);
1583 for (k = 0; k < cost_classes_ptr->num; k++)
1585 rclass = cost_classes[k];
1586 fprintf (f, " %s:%d", reg_class_names[rclass],
1587 COSTS (costs, regno)->cost[k]);
1589 fprintf (f, " MEM:%i\n", COSTS (costs, regno)->mem_cost);
1593 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1594 costs. */
1595 static void
1596 process_bb_for_costs (basic_block bb)
1598 rtx_insn *insn;
1600 frequency = REG_FREQ_FROM_BB (bb);
1601 if (frequency == 0)
1602 frequency = 1;
1603 FOR_BB_INSNS (bb, insn)
1604 insn = scan_one_insn (insn);
1607 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1608 costs. */
1609 static void
1610 process_bb_node_for_costs (ira_loop_tree_node_t loop_tree_node)
1612 basic_block bb;
1614 bb = loop_tree_node->bb;
1615 if (bb != NULL)
1616 process_bb_for_costs (bb);
1619 /* Find costs of register classes and memory for allocnos or pseudos
1620 and their best costs. Set up preferred, alternative and allocno
1621 classes for pseudos. */
1622 static void
1623 find_costs_and_classes (FILE *dump_file)
1625 int i, k, start, max_cost_classes_num;
1626 int pass;
1627 basic_block bb;
1628 enum reg_class *regno_best_class;
1630 init_recog ();
1631 regno_best_class
1632 = (enum reg_class *) ira_allocate (max_reg_num ()
1633 * sizeof (enum reg_class));
1634 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1635 regno_best_class[i] = NO_REGS;
1636 if (!resize_reg_info () && allocno_p
1637 && pseudo_classes_defined_p && flag_expensive_optimizations)
1639 ira_allocno_t a;
1640 ira_allocno_iterator ai;
1642 pref = pref_buffer;
1643 max_cost_classes_num = 1;
1644 FOR_EACH_ALLOCNO (a, ai)
1646 pref[ALLOCNO_NUM (a)] = reg_preferred_class (ALLOCNO_REGNO (a));
1647 setup_regno_cost_classes_by_aclass
1648 (ALLOCNO_REGNO (a), pref[ALLOCNO_NUM (a)]);
1649 max_cost_classes_num
1650 = MAX (max_cost_classes_num,
1651 regno_cost_classes[ALLOCNO_REGNO (a)]->num);
1653 start = 1;
1655 else
1657 pref = NULL;
1658 max_cost_classes_num = ira_important_classes_num;
1659 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1660 if (regno_reg_rtx[i] != NULL_RTX)
1661 setup_regno_cost_classes_by_mode (i, PSEUDO_REGNO_MODE (i));
1662 else
1663 setup_regno_cost_classes_by_aclass (i, ALL_REGS);
1664 start = 0;
1666 if (allocno_p)
1667 /* Clear the flag for the next compiled function. */
1668 pseudo_classes_defined_p = false;
1669 /* Normally we scan the insns once and determine the best class to
1670 use for each allocno. However, if -fexpensive-optimizations are
1671 on, we do so twice, the second time using the tentative best
1672 classes to guide the selection. */
1673 for (pass = start; pass <= flag_expensive_optimizations; pass++)
1675 if ((!allocno_p || internal_flag_ira_verbose > 0) && dump_file)
1676 fprintf (dump_file,
1677 "\nPass %i for finding pseudo/allocno costs\n\n", pass);
1679 if (pass != start)
1681 max_cost_classes_num = 1;
1682 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1684 setup_regno_cost_classes_by_aclass (i, regno_best_class[i]);
1685 max_cost_classes_num
1686 = MAX (max_cost_classes_num, regno_cost_classes[i]->num);
1690 struct_costs_size
1691 = sizeof (struct costs) + sizeof (int) * (max_cost_classes_num - 1);
1692 /* Zero out our accumulation of the cost of each class for each
1693 allocno. */
1694 memset (costs, 0, cost_elements_num * struct_costs_size);
1696 if (allocno_p)
1698 /* Scan the instructions and record each time it would save code
1699 to put a certain allocno in a certain class. */
1700 ira_traverse_loop_tree (true, ira_loop_tree_root,
1701 process_bb_node_for_costs, NULL);
1703 memcpy (total_allocno_costs, costs,
1704 max_struct_costs_size * ira_allocnos_num);
1706 else
1708 basic_block bb;
1710 FOR_EACH_BB_FN (bb, cfun)
1711 process_bb_for_costs (bb);
1714 if (pass == 0)
1715 pref = pref_buffer;
1717 /* Now for each allocno look at how desirable each class is and
1718 find which class is preferred. */
1719 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1721 ira_allocno_t a, parent_a;
1722 int rclass, a_num, parent_a_num, add_cost;
1723 ira_loop_tree_node_t parent;
1724 int best_cost, allocno_cost;
1725 enum reg_class best, alt_class;
1726 cost_classes_t cost_classes_ptr = regno_cost_classes[i];
1727 enum reg_class *cost_classes = cost_classes_ptr->classes;
1728 int *i_costs = temp_costs->cost;
1729 int i_mem_cost;
1730 int equiv_savings = regno_equiv_gains[i];
1732 if (! allocno_p)
1734 if (regno_reg_rtx[i] == NULL_RTX)
1735 continue;
1736 memcpy (temp_costs, COSTS (costs, i), struct_costs_size);
1737 i_mem_cost = temp_costs->mem_cost;
1739 else
1741 if (ira_regno_allocno_map[i] == NULL)
1742 continue;
1743 memset (temp_costs, 0, struct_costs_size);
1744 i_mem_cost = 0;
1745 /* Find cost of all allocnos with the same regno. */
1746 for (a = ira_regno_allocno_map[i];
1747 a != NULL;
1748 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1750 int *a_costs, *p_costs;
1752 a_num = ALLOCNO_NUM (a);
1753 if ((flag_ira_region == IRA_REGION_ALL
1754 || flag_ira_region == IRA_REGION_MIXED)
1755 && (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1756 && (parent_a = parent->regno_allocno_map[i]) != NULL
1757 /* There are no caps yet. */
1758 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE
1759 (a)->border_allocnos,
1760 ALLOCNO_NUM (a)))
1762 /* Propagate costs to upper levels in the region
1763 tree. */
1764 parent_a_num = ALLOCNO_NUM (parent_a);
1765 a_costs = COSTS (total_allocno_costs, a_num)->cost;
1766 p_costs = COSTS (total_allocno_costs, parent_a_num)->cost;
1767 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1769 add_cost = a_costs[k];
1770 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1771 p_costs[k] = INT_MAX;
1772 else
1773 p_costs[k] += add_cost;
1775 add_cost = COSTS (total_allocno_costs, a_num)->mem_cost;
1776 if (add_cost > 0
1777 && (INT_MAX - add_cost
1778 < COSTS (total_allocno_costs,
1779 parent_a_num)->mem_cost))
1780 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1781 = INT_MAX;
1782 else
1783 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1784 += add_cost;
1786 if (i >= first_moveable_pseudo && i < last_moveable_pseudo)
1787 COSTS (total_allocno_costs, parent_a_num)->mem_cost = 0;
1789 a_costs = COSTS (costs, a_num)->cost;
1790 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1792 add_cost = a_costs[k];
1793 if (add_cost > 0 && INT_MAX - add_cost < i_costs[k])
1794 i_costs[k] = INT_MAX;
1795 else
1796 i_costs[k] += add_cost;
1798 add_cost = COSTS (costs, a_num)->mem_cost;
1799 if (add_cost > 0 && INT_MAX - add_cost < i_mem_cost)
1800 i_mem_cost = INT_MAX;
1801 else
1802 i_mem_cost += add_cost;
1805 if (i >= first_moveable_pseudo && i < last_moveable_pseudo)
1806 i_mem_cost = 0;
1807 else if (equiv_savings < 0)
1808 i_mem_cost = -equiv_savings;
1809 else if (equiv_savings > 0)
1811 i_mem_cost = 0;
1812 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1813 i_costs[k] += equiv_savings;
1816 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1817 best = ALL_REGS;
1818 alt_class = NO_REGS;
1819 /* Find best common class for all allocnos with the same
1820 regno. */
1821 for (k = 0; k < cost_classes_ptr->num; k++)
1823 rclass = cost_classes[k];
1824 if (i_costs[k] < best_cost)
1826 best_cost = i_costs[k];
1827 best = (enum reg_class) rclass;
1829 else if (i_costs[k] == best_cost)
1830 best = ira_reg_class_subunion[best][rclass];
1831 if (pass == flag_expensive_optimizations
1832 /* We still prefer registers to memory even at this
1833 stage if their costs are the same. We will make
1834 a final decision during assigning hard registers
1835 when we have all info including more accurate
1836 costs which might be affected by assigning hard
1837 registers to other pseudos because the pseudos
1838 involved in moves can be coalesced. */
1839 && i_costs[k] <= i_mem_cost
1840 && (reg_class_size[reg_class_subunion[alt_class][rclass]]
1841 > reg_class_size[alt_class]))
1842 alt_class = reg_class_subunion[alt_class][rclass];
1844 alt_class = ira_allocno_class_translate[alt_class];
1845 if (best_cost > i_mem_cost)
1846 regno_aclass[i] = NO_REGS;
1847 else if (!optimize && !targetm.class_likely_spilled_p (best))
1848 /* Registers in the alternative class are likely to need
1849 longer or slower sequences than registers in the best class.
1850 When optimizing we make some effort to use the best class
1851 over the alternative class where possible, but at -O0 we
1852 effectively give the alternative class equal weight.
1853 We then run the risk of using slower alternative registers
1854 when plenty of registers from the best class are still free.
1855 This is especially true because live ranges tend to be very
1856 short in -O0 code and so register pressure tends to be low.
1858 Avoid that by ignoring the alternative class if the best
1859 class has plenty of registers. */
1860 regno_aclass[i] = best;
1861 else
1863 /* Make the common class the biggest class of best and
1864 alt_class. */
1865 regno_aclass[i]
1866 = ira_reg_class_superunion[best][alt_class];
1867 ira_assert (regno_aclass[i] != NO_REGS
1868 && ira_reg_allocno_class_p[regno_aclass[i]]);
1870 if (pass == flag_expensive_optimizations)
1872 if (best_cost > i_mem_cost)
1873 best = alt_class = NO_REGS;
1874 else if (best == alt_class)
1875 alt_class = NO_REGS;
1876 setup_reg_classes (i, best, alt_class, regno_aclass[i]);
1877 if ((!allocno_p || internal_flag_ira_verbose > 2)
1878 && dump_file != NULL)
1879 fprintf (dump_file,
1880 " r%d: preferred %s, alternative %s, allocno %s\n",
1881 i, reg_class_names[best], reg_class_names[alt_class],
1882 reg_class_names[regno_aclass[i]]);
1884 regno_best_class[i] = best;
1885 if (! allocno_p)
1887 pref[i] = best_cost > i_mem_cost ? NO_REGS : best;
1888 continue;
1890 for (a = ira_regno_allocno_map[i];
1891 a != NULL;
1892 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1894 enum reg_class aclass = regno_aclass[i];
1895 int a_num = ALLOCNO_NUM (a);
1896 int *total_a_costs = COSTS (total_allocno_costs, a_num)->cost;
1897 int *a_costs = COSTS (costs, a_num)->cost;
1899 if (aclass == NO_REGS)
1900 best = NO_REGS;
1901 else
1903 /* Finding best class which is subset of the common
1904 class. */
1905 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1906 allocno_cost = best_cost;
1907 best = ALL_REGS;
1908 for (k = 0; k < cost_classes_ptr->num; k++)
1910 rclass = cost_classes[k];
1911 if (! ira_class_subset_p[rclass][aclass])
1912 continue;
1913 if (total_a_costs[k] < best_cost)
1915 best_cost = total_a_costs[k];
1916 allocno_cost = a_costs[k];
1917 best = (enum reg_class) rclass;
1919 else if (total_a_costs[k] == best_cost)
1921 best = ira_reg_class_subunion[best][rclass];
1922 allocno_cost = MAX (allocno_cost, a_costs[k]);
1925 ALLOCNO_CLASS_COST (a) = allocno_cost;
1927 if (internal_flag_ira_verbose > 2 && dump_file != NULL
1928 && (pass == 0 || pref[a_num] != best))
1930 fprintf (dump_file, " a%d (r%d,", a_num, i);
1931 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1932 fprintf (dump_file, "b%d", bb->index);
1933 else
1934 fprintf (dump_file, "l%d",
1935 ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
1936 fprintf (dump_file, ") best %s, allocno %s\n",
1937 reg_class_names[best],
1938 reg_class_names[aclass]);
1940 pref[a_num] = best;
1941 if (pass == flag_expensive_optimizations && best != aclass
1942 && ira_class_hard_regs_num[best] > 0
1943 && (ira_reg_class_max_nregs[best][ALLOCNO_MODE (a)]
1944 >= ira_class_hard_regs_num[best]))
1946 int ind = cost_classes_ptr->index[aclass];
1948 ira_assert (ind >= 0);
1949 ira_init_register_move_cost_if_necessary (ALLOCNO_MODE (a));
1950 ira_add_allocno_pref (a, ira_class_hard_regs[best][0],
1951 (a_costs[ind] - ALLOCNO_CLASS_COST (a))
1952 / (ira_register_move_cost
1953 [ALLOCNO_MODE (a)][best][aclass]));
1954 for (k = 0; k < cost_classes_ptr->num; k++)
1955 if (ira_class_subset_p[cost_classes[k]][best])
1956 a_costs[k] = a_costs[ind];
1961 if (internal_flag_ira_verbose > 4 && dump_file)
1963 if (allocno_p)
1964 print_allocno_costs (dump_file);
1965 else
1966 print_pseudo_costs (dump_file);
1967 fprintf (dump_file,"\n");
1970 ira_free (regno_best_class);
1975 /* Process moves involving hard regs to modify allocno hard register
1976 costs. We can do this only after determining allocno class. If a
1977 hard register forms a register class, then moves with the hard
1978 register are already taken into account in class costs for the
1979 allocno. */
1980 static void
1981 process_bb_node_for_hard_reg_moves (ira_loop_tree_node_t loop_tree_node)
1983 int i, freq, src_regno, dst_regno, hard_regno, a_regno;
1984 bool to_p;
1985 ira_allocno_t a, curr_a;
1986 ira_loop_tree_node_t curr_loop_tree_node;
1987 enum reg_class rclass;
1988 basic_block bb;
1989 rtx_insn *insn;
1990 rtx set, src, dst;
1992 bb = loop_tree_node->bb;
1993 if (bb == NULL)
1994 return;
1995 freq = REG_FREQ_FROM_BB (bb);
1996 if (freq == 0)
1997 freq = 1;
1998 FOR_BB_INSNS (bb, insn)
2000 if (!NONDEBUG_INSN_P (insn))
2001 continue;
2002 set = single_set (insn);
2003 if (set == NULL_RTX)
2004 continue;
2005 dst = SET_DEST (set);
2006 src = SET_SRC (set);
2007 if (! REG_P (dst) || ! REG_P (src))
2008 continue;
2009 dst_regno = REGNO (dst);
2010 src_regno = REGNO (src);
2011 if (dst_regno >= FIRST_PSEUDO_REGISTER
2012 && src_regno < FIRST_PSEUDO_REGISTER)
2014 hard_regno = src_regno;
2015 a = ira_curr_regno_allocno_map[dst_regno];
2016 to_p = true;
2018 else if (src_regno >= FIRST_PSEUDO_REGISTER
2019 && dst_regno < FIRST_PSEUDO_REGISTER)
2021 hard_regno = dst_regno;
2022 a = ira_curr_regno_allocno_map[src_regno];
2023 to_p = false;
2025 else
2026 continue;
2027 rclass = ALLOCNO_CLASS (a);
2028 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass], hard_regno))
2029 continue;
2030 i = ira_class_hard_reg_index[rclass][hard_regno];
2031 if (i < 0)
2032 continue;
2033 a_regno = ALLOCNO_REGNO (a);
2034 for (curr_loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2035 curr_loop_tree_node != NULL;
2036 curr_loop_tree_node = curr_loop_tree_node->parent)
2037 if ((curr_a = curr_loop_tree_node->regno_allocno_map[a_regno]) != NULL)
2038 ira_add_allocno_pref (curr_a, hard_regno, freq);
2040 int cost;
2041 enum reg_class hard_reg_class;
2042 machine_mode mode;
2044 mode = ALLOCNO_MODE (a);
2045 hard_reg_class = REGNO_REG_CLASS (hard_regno);
2046 ira_init_register_move_cost_if_necessary (mode);
2047 cost = (to_p ? ira_register_move_cost[mode][hard_reg_class][rclass]
2048 : ira_register_move_cost[mode][rclass][hard_reg_class]) * freq;
2049 ira_allocate_and_set_costs (&ALLOCNO_HARD_REG_COSTS (a), rclass,
2050 ALLOCNO_CLASS_COST (a));
2051 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2052 rclass, 0);
2053 ALLOCNO_HARD_REG_COSTS (a)[i] -= cost;
2054 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[i] -= cost;
2055 ALLOCNO_CLASS_COST (a) = MIN (ALLOCNO_CLASS_COST (a),
2056 ALLOCNO_HARD_REG_COSTS (a)[i]);
2061 /* After we find hard register and memory costs for allocnos, define
2062 its class and modify hard register cost because insns moving
2063 allocno to/from hard registers. */
2064 static void
2065 setup_allocno_class_and_costs (void)
2067 int i, j, n, regno, hard_regno, num;
2068 int *reg_costs;
2069 enum reg_class aclass, rclass;
2070 ira_allocno_t a;
2071 ira_allocno_iterator ai;
2072 cost_classes_t cost_classes_ptr;
2074 ira_assert (allocno_p);
2075 FOR_EACH_ALLOCNO (a, ai)
2077 i = ALLOCNO_NUM (a);
2078 regno = ALLOCNO_REGNO (a);
2079 aclass = regno_aclass[regno];
2080 cost_classes_ptr = regno_cost_classes[regno];
2081 ira_assert (pref[i] == NO_REGS || aclass != NO_REGS);
2082 ALLOCNO_MEMORY_COST (a) = COSTS (costs, i)->mem_cost;
2083 ira_set_allocno_class (a, aclass);
2084 if (aclass == NO_REGS)
2085 continue;
2086 if (optimize && ALLOCNO_CLASS (a) != pref[i])
2088 n = ira_class_hard_regs_num[aclass];
2089 ALLOCNO_HARD_REG_COSTS (a)
2090 = reg_costs = ira_allocate_cost_vector (aclass);
2091 for (j = n - 1; j >= 0; j--)
2093 hard_regno = ira_class_hard_regs[aclass][j];
2094 if (TEST_HARD_REG_BIT (reg_class_contents[pref[i]], hard_regno))
2095 reg_costs[j] = ALLOCNO_CLASS_COST (a);
2096 else
2098 rclass = REGNO_REG_CLASS (hard_regno);
2099 num = cost_classes_ptr->index[rclass];
2100 if (num < 0)
2102 num = cost_classes_ptr->hard_regno_index[hard_regno];
2103 ira_assert (num >= 0);
2105 reg_costs[j] = COSTS (costs, i)->cost[num];
2110 if (optimize)
2111 ira_traverse_loop_tree (true, ira_loop_tree_root,
2112 process_bb_node_for_hard_reg_moves, NULL);
2117 /* Function called once during compiler work. */
2118 void
2119 ira_init_costs_once (void)
2121 int i;
2123 init_cost = NULL;
2124 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2126 op_costs[i] = NULL;
2127 this_op_costs[i] = NULL;
2129 temp_costs = NULL;
2132 /* Free allocated temporary cost vectors. */
2133 void
2134 target_ira_int::free_ira_costs ()
2136 int i;
2138 free (x_init_cost);
2139 x_init_cost = NULL;
2140 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2142 free (x_op_costs[i]);
2143 free (x_this_op_costs[i]);
2144 x_op_costs[i] = x_this_op_costs[i] = NULL;
2146 free (x_temp_costs);
2147 x_temp_costs = NULL;
2150 /* This is called each time register related information is
2151 changed. */
2152 void
2153 ira_init_costs (void)
2155 int i;
2157 this_target_ira_int->free_ira_costs ();
2158 max_struct_costs_size
2159 = sizeof (struct costs) + sizeof (int) * (ira_important_classes_num - 1);
2160 /* Don't use ira_allocate because vectors live through several IRA
2161 calls. */
2162 init_cost = (struct costs *) xmalloc (max_struct_costs_size);
2163 init_cost->mem_cost = 1000000;
2164 for (i = 0; i < ira_important_classes_num; i++)
2165 init_cost->cost[i] = 1000000;
2166 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2168 op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
2169 this_op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
2171 temp_costs = (struct costs *) xmalloc (max_struct_costs_size);
2176 /* Common initialization function for ira_costs and
2177 ira_set_pseudo_classes. */
2178 static void
2179 init_costs (void)
2181 init_subregs_of_mode ();
2182 costs = (struct costs *) ira_allocate (max_struct_costs_size
2183 * cost_elements_num);
2184 pref_buffer = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
2185 * cost_elements_num);
2186 regno_aclass = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
2187 * max_reg_num ());
2188 regno_equiv_gains = (int *) ira_allocate (sizeof (int) * max_reg_num ());
2189 memset (regno_equiv_gains, 0, sizeof (int) * max_reg_num ());
2192 /* Common finalization function for ira_costs and
2193 ira_set_pseudo_classes. */
2194 static void
2195 finish_costs (void)
2197 finish_subregs_of_mode ();
2198 ira_free (regno_equiv_gains);
2199 ira_free (regno_aclass);
2200 ira_free (pref_buffer);
2201 ira_free (costs);
2204 /* Entry function which defines register class, memory and hard
2205 register costs for each allocno. */
2206 void
2207 ira_costs (void)
2209 allocno_p = true;
2210 cost_elements_num = ira_allocnos_num;
2211 init_costs ();
2212 total_allocno_costs = (struct costs *) ira_allocate (max_struct_costs_size
2213 * ira_allocnos_num);
2214 initiate_regno_cost_classes ();
2215 calculate_elim_costs_all_insns ();
2216 find_costs_and_classes (ira_dump_file);
2217 setup_allocno_class_and_costs ();
2218 finish_regno_cost_classes ();
2219 finish_costs ();
2220 ira_free (total_allocno_costs);
2223 /* Entry function which defines classes for pseudos.
2224 Set pseudo_classes_defined_p only if DEFINE_PSEUDO_CLASSES is true. */
2225 void
2226 ira_set_pseudo_classes (bool define_pseudo_classes, FILE *dump_file)
2228 allocno_p = false;
2229 internal_flag_ira_verbose = flag_ira_verbose;
2230 cost_elements_num = max_reg_num ();
2231 init_costs ();
2232 initiate_regno_cost_classes ();
2233 find_costs_and_classes (dump_file);
2234 finish_regno_cost_classes ();
2235 if (define_pseudo_classes)
2236 pseudo_classes_defined_p = true;
2238 finish_costs ();
2243 /* Change hard register costs for allocnos which lives through
2244 function calls. This is called only when we found all intersected
2245 calls during building allocno live ranges. */
2246 void
2247 ira_tune_allocno_costs (void)
2249 int j, n, regno;
2250 int cost, min_cost, *reg_costs;
2251 enum reg_class aclass, rclass;
2252 machine_mode mode;
2253 ira_allocno_t a;
2254 ira_allocno_iterator ai;
2255 ira_allocno_object_iterator oi;
2256 ira_object_t obj;
2257 bool skip_p;
2258 HARD_REG_SET *crossed_calls_clobber_regs;
2260 FOR_EACH_ALLOCNO (a, ai)
2262 aclass = ALLOCNO_CLASS (a);
2263 if (aclass == NO_REGS)
2264 continue;
2265 mode = ALLOCNO_MODE (a);
2266 n = ira_class_hard_regs_num[aclass];
2267 min_cost = INT_MAX;
2268 if (ALLOCNO_CALLS_CROSSED_NUM (a)
2269 != ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2271 ira_allocate_and_set_costs
2272 (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2273 ALLOCNO_CLASS_COST (a));
2274 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2275 for (j = n - 1; j >= 0; j--)
2277 regno = ira_class_hard_regs[aclass][j];
2278 skip_p = false;
2279 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2281 if (ira_hard_reg_set_intersection_p (regno, mode,
2282 OBJECT_CONFLICT_HARD_REGS
2283 (obj)))
2285 skip_p = true;
2286 break;
2289 if (skip_p)
2290 continue;
2291 rclass = REGNO_REG_CLASS (regno);
2292 cost = 0;
2293 crossed_calls_clobber_regs
2294 = &(ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
2295 if (ira_hard_reg_set_intersection_p (regno, mode,
2296 *crossed_calls_clobber_regs)
2297 && (ira_hard_reg_set_intersection_p (regno, mode,
2298 call_used_reg_set)
2299 || HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
2300 cost += (ALLOCNO_CALL_FREQ (a)
2301 * (ira_memory_move_cost[mode][rclass][0]
2302 + ira_memory_move_cost[mode][rclass][1]));
2303 #ifdef IRA_HARD_REGNO_ADD_COST_MULTIPLIER
2304 cost += ((ira_memory_move_cost[mode][rclass][0]
2305 + ira_memory_move_cost[mode][rclass][1])
2306 * ALLOCNO_FREQ (a)
2307 * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno) / 2);
2308 #endif
2309 if (INT_MAX - cost < reg_costs[j])
2310 reg_costs[j] = INT_MAX;
2311 else
2312 reg_costs[j] += cost;
2313 if (min_cost > reg_costs[j])
2314 min_cost = reg_costs[j];
2317 if (min_cost != INT_MAX)
2318 ALLOCNO_CLASS_COST (a) = min_cost;
2320 /* Some targets allow pseudos to be allocated to unaligned sequences
2321 of hard registers. However, selecting an unaligned sequence can
2322 unnecessarily restrict later allocations. So increase the cost of
2323 unaligned hard regs to encourage the use of aligned hard regs. */
2325 const int nregs = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2327 if (nregs > 1)
2329 ira_allocate_and_set_costs
2330 (&ALLOCNO_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a));
2331 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2332 for (j = n - 1; j >= 0; j--)
2334 regno = ira_non_ordered_class_hard_regs[aclass][j];
2335 if ((regno % nregs) != 0)
2337 int index = ira_class_hard_reg_index[aclass][regno];
2338 ira_assert (index != -1);
2339 reg_costs[index] += ALLOCNO_FREQ (a);
2347 /* Add COST to the estimated gain for eliminating REGNO with its
2348 equivalence. If COST is zero, record that no such elimination is
2349 possible. */
2351 void
2352 ira_adjust_equiv_reg_cost (unsigned regno, int cost)
2354 if (cost == 0)
2355 regno_equiv_gains[regno] = 0;
2356 else
2357 regno_equiv_gains[regno] += cost;
2360 void
2361 ira_costs_c_finalize (void)
2363 this_target_ira_int->free_ira_costs ();