PR sanitizer/65081
[official-gcc.git] / gcc / ira-costs.c
blobc19f2586affb562101b41b0c9a0cf5fd4681c647
1 /* IRA hard register and memory cost calculation for allocnos or pseudos.
2 Copyright (C) 2006-2015 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 "symtab.h"
29 #include "hashtab.h"
30 #include "hash-set.h"
31 #include "vec.h"
32 #include "machmode.h"
33 #include "input.h"
34 #include "function.h"
35 #include "flags.h"
36 #include "statistics.h"
37 #include "double-int.h"
38 #include "real.h"
39 #include "fixed-value.h"
40 #include "alias.h"
41 #include "wide-int.h"
42 #include "inchash.h"
43 #include "tree.h"
44 #include "insn-config.h"
45 #include "expmed.h"
46 #include "dojump.h"
47 #include "explow.h"
48 #include "calls.h"
49 #include "emit-rtl.h"
50 #include "varasm.h"
51 #include "stmt.h"
52 #include "expr.h"
53 #include "tm_p.h"
54 #include "predict.h"
55 #include "dominance.h"
56 #include "cfg.h"
57 #include "basic-block.h"
58 #include "regs.h"
59 #include "addresses.h"
60 #include "recog.h"
61 #include "reload.h"
62 #include "diagnostic-core.h"
63 #include "target.h"
64 #include "params.h"
65 #include "ira-int.h"
67 /* The flags is set up every time when we calculate pseudo register
68 classes through function ira_set_pseudo_classes. */
69 static bool pseudo_classes_defined_p = false;
71 /* TRUE if we work with allocnos. Otherwise we work with pseudos. */
72 static bool allocno_p;
74 /* Number of elements in array `costs'. */
75 static int cost_elements_num;
77 /* The `costs' struct records the cost of using hard registers of each
78 class considered for the calculation and of using memory for each
79 allocno or pseudo. */
80 struct costs
82 int mem_cost;
83 /* Costs for register classes start here. We process only some
84 allocno classes. */
85 int cost[1];
88 #define max_struct_costs_size \
89 (this_target_ira_int->x_max_struct_costs_size)
90 #define init_cost \
91 (this_target_ira_int->x_init_cost)
92 #define temp_costs \
93 (this_target_ira_int->x_temp_costs)
94 #define op_costs \
95 (this_target_ira_int->x_op_costs)
96 #define this_op_costs \
97 (this_target_ira_int->x_this_op_costs)
99 /* Costs of each class for each allocno or pseudo. */
100 static struct costs *costs;
102 /* Accumulated costs of each class for each allocno. */
103 static struct costs *total_allocno_costs;
105 /* It is the current size of struct costs. */
106 static int struct_costs_size;
108 /* Return pointer to structure containing costs of allocno or pseudo
109 with given NUM in array ARR. */
110 #define COSTS(arr, num) \
111 ((struct costs *) ((char *) (arr) + (num) * struct_costs_size))
113 /* Return index in COSTS when processing reg with REGNO. */
114 #define COST_INDEX(regno) (allocno_p \
115 ? ALLOCNO_NUM (ira_curr_regno_allocno_map[regno]) \
116 : (int) regno)
118 /* Record register class preferences of each allocno or pseudo. Null
119 value means no preferences. It happens on the 1st iteration of the
120 cost calculation. */
121 static enum reg_class *pref;
123 /* Allocated buffers for pref. */
124 static enum reg_class *pref_buffer;
126 /* Record allocno class of each allocno with the same regno. */
127 static enum reg_class *regno_aclass;
129 /* Record cost gains for not allocating a register with an invariant
130 equivalence. */
131 static int *regno_equiv_gains;
133 /* Execution frequency of the current insn. */
134 static int frequency;
138 /* Info about reg classes whose costs are calculated for a pseudo. */
139 struct cost_classes
141 /* Number of the cost classes in the subsequent array. */
142 int num;
143 /* Container of the cost classes. */
144 enum reg_class classes[N_REG_CLASSES];
145 /* Map reg class -> index of the reg class in the previous array.
146 -1 if it is not a cost class. */
147 int index[N_REG_CLASSES];
148 /* Map hard regno index of first class in array CLASSES containing
149 the hard regno, -1 otherwise. */
150 int hard_regno_index[FIRST_PSEUDO_REGISTER];
153 /* Types of pointers to the structure above. */
154 typedef struct cost_classes *cost_classes_t;
155 typedef const struct cost_classes *const_cost_classes_t;
157 /* Info about cost classes for each pseudo. */
158 static cost_classes_t *regno_cost_classes;
160 /* Helper for cost_classes hashing. */
162 struct cost_classes_hasher
164 typedef cost_classes value_type;
165 typedef cost_classes compare_type;
166 static inline hashval_t hash (const value_type *);
167 static inline bool equal (const value_type *, const compare_type *);
168 static inline void remove (value_type *);
171 /* Returns hash value for cost classes info HV. */
172 inline hashval_t
173 cost_classes_hasher::hash (const value_type *hv)
175 return iterative_hash (&hv->classes, sizeof (enum reg_class) * hv->num, 0);
178 /* Compares cost classes info HV1 and HV2. */
179 inline bool
180 cost_classes_hasher::equal (const value_type *hv1, const compare_type *hv2)
182 return (hv1->num == hv2->num
183 && memcmp (hv1->classes, hv2->classes,
184 sizeof (enum reg_class) * hv1->num) == 0);
187 /* Delete cost classes info V from the hash table. */
188 inline void
189 cost_classes_hasher::remove (value_type *v)
191 ira_free (v);
194 /* Hash table of unique cost classes. */
195 static hash_table<cost_classes_hasher> *cost_classes_htab;
197 /* Map allocno class -> cost classes for pseudo of given allocno
198 class. */
199 static cost_classes_t cost_classes_aclass_cache[N_REG_CLASSES];
201 /* Map mode -> cost classes for pseudo of give mode. */
202 static cost_classes_t cost_classes_mode_cache[MAX_MACHINE_MODE];
204 /* Cost classes that include all classes in ira_important_classes. */
205 static cost_classes all_cost_classes;
207 /* Use the array of classes in CLASSES_PTR to fill out the rest of
208 the structure. */
209 static void
210 complete_cost_classes (cost_classes_t classes_ptr)
212 for (int i = 0; i < N_REG_CLASSES; i++)
213 classes_ptr->index[i] = -1;
214 for (int i = 0; i < FIRST_PSEUDO_REGISTER; i++)
215 classes_ptr->hard_regno_index[i] = -1;
216 for (int i = 0; i < classes_ptr->num; i++)
218 enum reg_class cl = classes_ptr->classes[i];
219 classes_ptr->index[cl] = i;
220 for (int j = ira_class_hard_regs_num[cl] - 1; j >= 0; j--)
222 unsigned int hard_regno = ira_class_hard_regs[cl][j];
223 if (classes_ptr->hard_regno_index[hard_regno] < 0)
224 classes_ptr->hard_regno_index[hard_regno] = i;
229 /* Initialize info about the cost classes for each pseudo. */
230 static void
231 initiate_regno_cost_classes (void)
233 int size = sizeof (cost_classes_t) * max_reg_num ();
235 regno_cost_classes = (cost_classes_t *) ira_allocate (size);
236 memset (regno_cost_classes, 0, size);
237 memset (cost_classes_aclass_cache, 0,
238 sizeof (cost_classes_t) * N_REG_CLASSES);
239 memset (cost_classes_mode_cache, 0,
240 sizeof (cost_classes_t) * MAX_MACHINE_MODE);
241 cost_classes_htab = new hash_table<cost_classes_hasher> (200);
242 all_cost_classes.num = ira_important_classes_num;
243 for (int i = 0; i < ira_important_classes_num; i++)
244 all_cost_classes.classes[i] = ira_important_classes[i];
245 complete_cost_classes (&all_cost_classes);
248 /* Create new cost classes from cost classes FROM and set up members
249 index and hard_regno_index. Return the new classes. The function
250 implements some common code of two functions
251 setup_regno_cost_classes_by_aclass and
252 setup_regno_cost_classes_by_mode. */
253 static cost_classes_t
254 setup_cost_classes (cost_classes_t from)
256 cost_classes_t classes_ptr;
258 classes_ptr = (cost_classes_t) ira_allocate (sizeof (struct cost_classes));
259 classes_ptr->num = from->num;
260 for (int i = 0; i < from->num; i++)
261 classes_ptr->classes[i] = from->classes[i];
262 complete_cost_classes (classes_ptr);
263 return classes_ptr;
266 /* Return a version of FULL that only considers registers in REGS that are
267 valid for mode MODE. Both FULL and the returned class are globally
268 allocated. */
269 static cost_classes_t
270 restrict_cost_classes (cost_classes_t full, machine_mode mode,
271 const HARD_REG_SET &regs)
273 static struct cost_classes narrow;
274 int map[N_REG_CLASSES];
275 narrow.num = 0;
276 for (int i = 0; i < full->num; i++)
278 /* Assume that we'll drop the class. */
279 map[i] = -1;
281 /* Ignore classes that are too small for the mode. */
282 enum reg_class cl = full->classes[i];
283 if (!contains_reg_of_mode[cl][mode])
284 continue;
286 /* Calculate the set of registers in CL that belong to REGS and
287 are valid for MODE. */
288 HARD_REG_SET valid_for_cl;
289 COPY_HARD_REG_SET (valid_for_cl, reg_class_contents[cl]);
290 AND_HARD_REG_SET (valid_for_cl, regs);
291 AND_COMPL_HARD_REG_SET (valid_for_cl,
292 ira_prohibited_class_mode_regs[cl][mode]);
293 AND_COMPL_HARD_REG_SET (valid_for_cl, ira_no_alloc_regs);
294 if (hard_reg_set_empty_p (valid_for_cl))
295 continue;
297 /* Don't use this class if the set of valid registers is a subset
298 of an existing class. For example, suppose we have two classes
299 GR_REGS and FR_REGS and a union class GR_AND_FR_REGS. Suppose
300 that the mode changes allowed by FR_REGS are not as general as
301 the mode changes allowed by GR_REGS.
303 In this situation, the mode changes for GR_AND_FR_REGS could
304 either be seen as the union or the intersection of the mode
305 changes allowed by the two subclasses. The justification for
306 the union-based definition would be that, if you want a mode
307 change that's only allowed by GR_REGS, you can pick a register
308 from the GR_REGS subclass. The justification for the
309 intersection-based definition would be that every register
310 from the class would allow the mode change.
312 However, if we have a register that needs to be in GR_REGS,
313 using GR_AND_FR_REGS with the intersection-based definition
314 would be too pessimistic, since it would bring in restrictions
315 that only apply to FR_REGS. Conversely, if we have a register
316 that needs to be in FR_REGS, using GR_AND_FR_REGS with the
317 union-based definition would lose the extra restrictions
318 placed on FR_REGS. GR_AND_FR_REGS is therefore only useful
319 for cases where GR_REGS and FP_REGS are both valid. */
320 int pos;
321 for (pos = 0; pos < narrow.num; ++pos)
323 enum reg_class cl2 = narrow.classes[pos];
324 if (hard_reg_set_subset_p (valid_for_cl, reg_class_contents[cl2]))
325 break;
327 map[i] = pos;
328 if (pos == narrow.num)
330 /* If several classes are equivalent, prefer to use the one
331 that was chosen as the allocno class. */
332 enum reg_class cl2 = ira_allocno_class_translate[cl];
333 if (ira_class_hard_regs_num[cl] == ira_class_hard_regs_num[cl2])
334 cl = cl2;
335 narrow.classes[narrow.num++] = cl;
338 if (narrow.num == full->num)
339 return full;
341 cost_classes **slot = cost_classes_htab->find_slot (&narrow, INSERT);
342 if (*slot == NULL)
344 cost_classes_t classes = setup_cost_classes (&narrow);
345 /* Map equivalent classes to the representative that we chose above. */
346 for (int i = 0; i < ira_important_classes_num; i++)
348 enum reg_class cl = ira_important_classes[i];
349 int index = full->index[cl];
350 if (index >= 0)
351 classes->index[cl] = map[index];
353 *slot = classes;
355 return *slot;
358 /* Setup cost classes for pseudo REGNO whose allocno class is ACLASS.
359 This function is used when we know an initial approximation of
360 allocno class of the pseudo already, e.g. on the second iteration
361 of class cost calculation or after class cost calculation in
362 register-pressure sensitive insn scheduling or register-pressure
363 sensitive loop-invariant motion. */
364 static void
365 setup_regno_cost_classes_by_aclass (int regno, enum reg_class aclass)
367 static struct cost_classes classes;
368 cost_classes_t classes_ptr;
369 enum reg_class cl;
370 int i;
371 cost_classes **slot;
372 HARD_REG_SET temp, temp2;
373 bool exclude_p;
375 if ((classes_ptr = cost_classes_aclass_cache[aclass]) == NULL)
377 COPY_HARD_REG_SET (temp, reg_class_contents[aclass]);
378 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
379 /* We exclude classes from consideration which are subsets of
380 ACLASS only if ACLASS is an uniform class. */
381 exclude_p = ira_uniform_class_p[aclass];
382 classes.num = 0;
383 for (i = 0; i < ira_important_classes_num; i++)
385 cl = ira_important_classes[i];
386 if (exclude_p)
388 /* Exclude non-uniform classes which are subsets of
389 ACLASS. */
390 COPY_HARD_REG_SET (temp2, reg_class_contents[cl]);
391 AND_COMPL_HARD_REG_SET (temp2, ira_no_alloc_regs);
392 if (hard_reg_set_subset_p (temp2, temp) && cl != aclass)
393 continue;
395 classes.classes[classes.num++] = cl;
397 slot = cost_classes_htab->find_slot (&classes, INSERT);
398 if (*slot == NULL)
400 classes_ptr = setup_cost_classes (&classes);
401 *slot = classes_ptr;
403 classes_ptr = cost_classes_aclass_cache[aclass] = (cost_classes_t) *slot;
405 if (regno_reg_rtx[regno] != NULL_RTX)
407 /* Restrict the classes to those that are valid for REGNO's mode
408 (which might for example exclude singleton classes if the mode
409 requires two registers). Also restrict the classes to those that
410 are valid for subregs of REGNO. */
411 const HARD_REG_SET *valid_regs = valid_mode_changes_for_regno (regno);
412 if (!valid_regs)
413 valid_regs = &reg_class_contents[ALL_REGS];
414 classes_ptr = restrict_cost_classes (classes_ptr,
415 PSEUDO_REGNO_MODE (regno),
416 *valid_regs);
418 regno_cost_classes[regno] = classes_ptr;
421 /* Setup cost classes for pseudo REGNO with MODE. Usage of MODE can
422 decrease number of cost classes for the pseudo, if hard registers
423 of some important classes can not hold a value of MODE. So the
424 pseudo can not get hard register of some important classes and cost
425 calculation for such important classes is only wasting CPU
426 time. */
427 static void
428 setup_regno_cost_classes_by_mode (int regno, machine_mode mode)
430 if (const HARD_REG_SET *valid_regs = valid_mode_changes_for_regno (regno))
431 regno_cost_classes[regno] = restrict_cost_classes (&all_cost_classes,
432 mode, *valid_regs);
433 else
435 if (cost_classes_mode_cache[mode] == NULL)
436 cost_classes_mode_cache[mode]
437 = restrict_cost_classes (&all_cost_classes, mode,
438 reg_class_contents[ALL_REGS]);
439 regno_cost_classes[regno] = cost_classes_mode_cache[mode];
443 /* Finalize info about the cost classes for each pseudo. */
444 static void
445 finish_regno_cost_classes (void)
447 ira_free (regno_cost_classes);
448 delete cost_classes_htab;
449 cost_classes_htab = NULL;
454 /* Compute the cost of loading X into (if TO_P is TRUE) or from (if
455 TO_P is FALSE) a register of class RCLASS in mode MODE. X must not
456 be a pseudo register. */
457 static int
458 copy_cost (rtx x, machine_mode mode, reg_class_t rclass, bool to_p,
459 secondary_reload_info *prev_sri)
461 secondary_reload_info sri;
462 reg_class_t secondary_class = NO_REGS;
464 /* If X is a SCRATCH, there is actually nothing to move since we are
465 assuming optimal allocation. */
466 if (GET_CODE (x) == SCRATCH)
467 return 0;
469 /* Get the class we will actually use for a reload. */
470 rclass = targetm.preferred_reload_class (x, rclass);
472 /* If we need a secondary reload for an intermediate, the cost is
473 that to load the input into the intermediate register, then to
474 copy it. */
475 sri.prev_sri = prev_sri;
476 sri.extra_cost = 0;
477 secondary_class = targetm.secondary_reload (to_p, x, rclass, mode, &sri);
479 if (secondary_class != NO_REGS)
481 ira_init_register_move_cost_if_necessary (mode);
482 return (ira_register_move_cost[mode][(int) secondary_class][(int) rclass]
483 + sri.extra_cost
484 + copy_cost (x, mode, secondary_class, to_p, &sri));
487 /* For memory, use the memory move cost, for (hard) registers, use
488 the cost to move between the register classes, and use 2 for
489 everything else (constants). */
490 if (MEM_P (x) || rclass == NO_REGS)
491 return sri.extra_cost
492 + ira_memory_move_cost[mode][(int) rclass][to_p != 0];
493 else if (REG_P (x))
495 reg_class_t x_class = REGNO_REG_CLASS (REGNO (x));
497 ira_init_register_move_cost_if_necessary (mode);
498 return (sri.extra_cost
499 + ira_register_move_cost[mode][(int) x_class][(int) rclass]);
501 else
502 /* If this is a constant, we may eventually want to call rtx_cost
503 here. */
504 return sri.extra_cost + COSTS_N_INSNS (1);
509 /* Record the cost of using memory or hard registers of various
510 classes for the operands in INSN.
512 N_ALTS is the number of alternatives.
513 N_OPS is the number of operands.
514 OPS is an array of the operands.
515 MODES are the modes of the operands, in case any are VOIDmode.
516 CONSTRAINTS are the constraints to use for the operands. This array
517 is modified by this procedure.
519 This procedure works alternative by alternative. For each
520 alternative we assume that we will be able to allocate all allocnos
521 to their ideal register class and calculate the cost of using that
522 alternative. Then we compute, for each operand that is a
523 pseudo-register, the cost of having the allocno allocated to each
524 register class and using it in that alternative. To this cost is
525 added the cost of the alternative.
527 The cost of each class for this insn is its lowest cost among all
528 the alternatives. */
529 static void
530 record_reg_classes (int n_alts, int n_ops, rtx *ops,
531 machine_mode *modes, const char **constraints,
532 rtx_insn *insn, enum reg_class *pref)
534 int alt;
535 int i, j, k;
536 int insn_allows_mem[MAX_RECOG_OPERANDS];
537 move_table *move_in_cost, *move_out_cost;
538 short (*mem_cost)[2];
540 for (i = 0; i < n_ops; i++)
541 insn_allows_mem[i] = 0;
543 /* Process each alternative, each time minimizing an operand's cost
544 with the cost for each operand in that alternative. */
545 alternative_mask preferred = get_preferred_alternatives (insn);
546 for (alt = 0; alt < n_alts; alt++)
548 enum reg_class classes[MAX_RECOG_OPERANDS];
549 int allows_mem[MAX_RECOG_OPERANDS];
550 enum reg_class rclass;
551 int alt_fail = 0;
552 int alt_cost = 0, op_cost_add;
554 if (!TEST_BIT (preferred, alt))
556 for (i = 0; i < recog_data.n_operands; i++)
557 constraints[i] = skip_alternative (constraints[i]);
559 continue;
562 for (i = 0; i < n_ops; i++)
564 unsigned char c;
565 const char *p = constraints[i];
566 rtx op = ops[i];
567 machine_mode mode = modes[i];
568 int allows_addr = 0;
569 int win = 0;
571 /* Initially show we know nothing about the register class. */
572 classes[i] = NO_REGS;
573 allows_mem[i] = 0;
575 /* If this operand has no constraints at all, we can
576 conclude nothing about it since anything is valid. */
577 if (*p == 0)
579 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
580 memset (this_op_costs[i], 0, struct_costs_size);
581 continue;
584 /* If this alternative is only relevant when this operand
585 matches a previous operand, we do different things
586 depending on whether this operand is a allocno-reg or not.
587 We must process any modifiers for the operand before we
588 can make this test. */
589 while (*p == '%' || *p == '=' || *p == '+' || *p == '&')
590 p++;
592 if (p[0] >= '0' && p[0] <= '0' + i && (p[1] == ',' || p[1] == 0))
594 /* Copy class and whether memory is allowed from the
595 matching alternative. Then perform any needed cost
596 computations and/or adjustments. */
597 j = p[0] - '0';
598 classes[i] = classes[j];
599 allows_mem[i] = allows_mem[j];
600 if (allows_mem[i])
601 insn_allows_mem[i] = 1;
603 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
605 /* If this matches the other operand, we have no
606 added cost and we win. */
607 if (rtx_equal_p (ops[j], op))
608 win = 1;
609 /* If we can put the other operand into a register,
610 add to the cost of this alternative the cost to
611 copy this operand to the register used for the
612 other operand. */
613 else if (classes[j] != NO_REGS)
615 alt_cost += copy_cost (op, mode, classes[j], 1, NULL);
616 win = 1;
619 else if (! REG_P (ops[j])
620 || REGNO (ops[j]) < FIRST_PSEUDO_REGISTER)
622 /* This op is an allocno but the one it matches is
623 not. */
625 /* If we can't put the other operand into a
626 register, this alternative can't be used. */
628 if (classes[j] == NO_REGS)
629 alt_fail = 1;
630 /* Otherwise, add to the cost of this alternative
631 the cost to copy the other operand to the hard
632 register used for this operand. */
633 else
634 alt_cost += copy_cost (ops[j], mode, classes[j], 1, NULL);
636 else
638 /* The costs of this operand are not the same as the
639 other operand since move costs are not symmetric.
640 Moreover, if we cannot tie them, this alternative
641 needs to do a copy, which is one insn. */
642 struct costs *pp = this_op_costs[i];
643 int *pp_costs = pp->cost;
644 cost_classes_t cost_classes_ptr
645 = regno_cost_classes[REGNO (op)];
646 enum reg_class *cost_classes = cost_classes_ptr->classes;
647 bool in_p = recog_data.operand_type[i] != OP_OUT;
648 bool out_p = recog_data.operand_type[i] != OP_IN;
649 enum reg_class op_class = classes[i];
651 ira_init_register_move_cost_if_necessary (mode);
652 if (! in_p)
654 ira_assert (out_p);
655 if (op_class == NO_REGS)
657 mem_cost = ira_memory_move_cost[mode];
658 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
660 rclass = cost_classes[k];
661 pp_costs[k] = mem_cost[rclass][0] * frequency;
664 else
666 move_out_cost = ira_may_move_out_cost[mode];
667 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
669 rclass = cost_classes[k];
670 pp_costs[k]
671 = move_out_cost[op_class][rclass] * frequency;
675 else if (! out_p)
677 ira_assert (in_p);
678 if (op_class == NO_REGS)
680 mem_cost = ira_memory_move_cost[mode];
681 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
683 rclass = cost_classes[k];
684 pp_costs[k] = mem_cost[rclass][1] * frequency;
687 else
689 move_in_cost = ira_may_move_in_cost[mode];
690 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
692 rclass = cost_classes[k];
693 pp_costs[k]
694 = move_in_cost[rclass][op_class] * frequency;
698 else
700 if (op_class == NO_REGS)
702 mem_cost = ira_memory_move_cost[mode];
703 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
705 rclass = cost_classes[k];
706 pp_costs[k] = ((mem_cost[rclass][0]
707 + mem_cost[rclass][1])
708 * frequency);
711 else
713 move_in_cost = ira_may_move_in_cost[mode];
714 move_out_cost = ira_may_move_out_cost[mode];
715 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
717 rclass = cost_classes[k];
718 pp_costs[k] = ((move_in_cost[rclass][op_class]
719 + move_out_cost[op_class][rclass])
720 * frequency);
725 /* If the alternative actually allows memory, make
726 things a bit cheaper since we won't need an extra
727 insn to load it. */
728 pp->mem_cost
729 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
730 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
731 - allows_mem[i]) * frequency;
733 /* If we have assigned a class to this allocno in
734 our first pass, add a cost to this alternative
735 corresponding to what we would add if this
736 allocno were not in the appropriate class. */
737 if (pref)
739 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
741 if (pref_class == NO_REGS)
742 alt_cost
743 += ((out_p
744 ? ira_memory_move_cost[mode][op_class][0] : 0)
745 + (in_p
746 ? ira_memory_move_cost[mode][op_class][1]
747 : 0));
748 else if (ira_reg_class_intersect
749 [pref_class][op_class] == NO_REGS)
750 alt_cost
751 += ira_register_move_cost[mode][pref_class][op_class];
753 if (REGNO (ops[i]) != REGNO (ops[j])
754 && ! find_reg_note (insn, REG_DEAD, op))
755 alt_cost += 2;
757 /* This is in place of ordinary cost computation for
758 this operand, so skip to the end of the
759 alternative (should be just one character). */
760 while (*p && *p++ != ',')
763 constraints[i] = p;
764 continue;
768 /* Scan all the constraint letters. See if the operand
769 matches any of the constraints. Collect the valid
770 register classes and see if this operand accepts
771 memory. */
772 while ((c = *p))
774 switch (c)
776 case '*':
777 /* Ignore the next letter for this pass. */
778 c = *++p;
779 break;
781 case '^':
782 alt_cost += 2;
783 break;
785 case '?':
786 alt_cost += 2;
787 break;
789 case 'g':
790 if (MEM_P (op)
791 || (CONSTANT_P (op)
792 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))))
793 win = 1;
794 insn_allows_mem[i] = allows_mem[i] = 1;
795 classes[i] = ira_reg_class_subunion[classes[i]][GENERAL_REGS];
796 break;
798 default:
799 enum constraint_num cn = lookup_constraint (p);
800 enum reg_class cl;
801 switch (get_constraint_type (cn))
803 case CT_REGISTER:
804 cl = reg_class_for_constraint (cn);
805 if (cl != NO_REGS)
806 classes[i] = ira_reg_class_subunion[classes[i]][cl];
807 break;
809 case CT_CONST_INT:
810 if (CONST_INT_P (op)
811 && insn_const_int_ok_for_constraint (INTVAL (op), cn))
812 win = 1;
813 break;
815 case CT_MEMORY:
816 /* Every MEM can be reloaded to fit. */
817 insn_allows_mem[i] = allows_mem[i] = 1;
818 if (MEM_P (op))
819 win = 1;
820 break;
822 case CT_ADDRESS:
823 /* Every address can be reloaded to fit. */
824 allows_addr = 1;
825 if (address_operand (op, GET_MODE (op))
826 || constraint_satisfied_p (op, cn))
827 win = 1;
828 /* We know this operand is an address, so we
829 want it to be allocated to a hard register
830 that can be the base of an address,
831 i.e. BASE_REG_CLASS. */
832 classes[i]
833 = ira_reg_class_subunion[classes[i]]
834 [base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
835 ADDRESS, SCRATCH)];
836 break;
838 case CT_FIXED_FORM:
839 if (constraint_satisfied_p (op, cn))
840 win = 1;
841 break;
843 break;
845 p += CONSTRAINT_LEN (c, p);
846 if (c == ',')
847 break;
850 constraints[i] = p;
852 /* How we account for this operand now depends on whether it
853 is a pseudo register or not. If it is, we first check if
854 any register classes are valid. If not, we ignore this
855 alternative, since we want to assume that all allocnos get
856 allocated for register preferencing. If some register
857 class is valid, compute the costs of moving the allocno
858 into that class. */
859 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
861 if (classes[i] == NO_REGS && ! allows_mem[i])
863 /* We must always fail if the operand is a REG, but
864 we did not find a suitable class and memory is
865 not allowed.
867 Otherwise we may perform an uninitialized read
868 from this_op_costs after the `continue' statement
869 below. */
870 alt_fail = 1;
872 else
874 unsigned int regno = REGNO (op);
875 struct costs *pp = this_op_costs[i];
876 int *pp_costs = pp->cost;
877 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
878 enum reg_class *cost_classes = cost_classes_ptr->classes;
879 bool in_p = recog_data.operand_type[i] != OP_OUT;
880 bool out_p = recog_data.operand_type[i] != OP_IN;
881 enum reg_class op_class = classes[i];
883 ira_init_register_move_cost_if_necessary (mode);
884 if (! in_p)
886 ira_assert (out_p);
887 if (op_class == NO_REGS)
889 mem_cost = ira_memory_move_cost[mode];
890 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
892 rclass = cost_classes[k];
893 pp_costs[k] = mem_cost[rclass][0] * frequency;
896 else
898 move_out_cost = ira_may_move_out_cost[mode];
899 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
901 rclass = cost_classes[k];
902 pp_costs[k]
903 = move_out_cost[op_class][rclass] * frequency;
907 else if (! out_p)
909 ira_assert (in_p);
910 if (op_class == NO_REGS)
912 mem_cost = ira_memory_move_cost[mode];
913 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
915 rclass = cost_classes[k];
916 pp_costs[k] = mem_cost[rclass][1] * frequency;
919 else
921 move_in_cost = ira_may_move_in_cost[mode];
922 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
924 rclass = cost_classes[k];
925 pp_costs[k]
926 = move_in_cost[rclass][op_class] * frequency;
930 else
932 if (op_class == NO_REGS)
934 mem_cost = ira_memory_move_cost[mode];
935 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
937 rclass = cost_classes[k];
938 pp_costs[k] = ((mem_cost[rclass][0]
939 + mem_cost[rclass][1])
940 * frequency);
943 else
945 move_in_cost = ira_may_move_in_cost[mode];
946 move_out_cost = ira_may_move_out_cost[mode];
947 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
949 rclass = cost_classes[k];
950 pp_costs[k] = ((move_in_cost[rclass][op_class]
951 + move_out_cost[op_class][rclass])
952 * frequency);
957 if (op_class == NO_REGS)
958 /* Although we don't need insn to reload from
959 memory, still accessing memory is usually more
960 expensive than a register. */
961 pp->mem_cost = frequency;
962 else
963 /* If the alternative actually allows memory, make
964 things a bit cheaper since we won't need an
965 extra insn to load it. */
966 pp->mem_cost
967 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0)
968 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0)
969 - allows_mem[i]) * frequency;
970 /* If we have assigned a class to this allocno in
971 our first pass, add a cost to this alternative
972 corresponding to what we would add if this
973 allocno were not in the appropriate class. */
974 if (pref)
976 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))];
978 if (pref_class == NO_REGS)
980 if (op_class != NO_REGS)
981 alt_cost
982 += ((out_p
983 ? ira_memory_move_cost[mode][op_class][0]
984 : 0)
985 + (in_p
986 ? ira_memory_move_cost[mode][op_class][1]
987 : 0));
989 else if (op_class == NO_REGS)
990 alt_cost
991 += ((out_p
992 ? ira_memory_move_cost[mode][pref_class][1]
993 : 0)
994 + (in_p
995 ? ira_memory_move_cost[mode][pref_class][0]
996 : 0));
997 else if (ira_reg_class_intersect[pref_class][op_class]
998 == NO_REGS)
999 alt_cost += (ira_register_move_cost
1000 [mode][pref_class][op_class]);
1005 /* Otherwise, if this alternative wins, either because we
1006 have already determined that or if we have a hard
1007 register of the proper class, there is no cost for this
1008 alternative. */
1009 else if (win || (REG_P (op)
1010 && reg_fits_class_p (op, classes[i],
1011 0, GET_MODE (op))))
1014 /* If registers are valid, the cost of this alternative
1015 includes copying the object to and/or from a
1016 register. */
1017 else if (classes[i] != NO_REGS)
1019 if (recog_data.operand_type[i] != OP_OUT)
1020 alt_cost += copy_cost (op, mode, classes[i], 1, NULL);
1022 if (recog_data.operand_type[i] != OP_IN)
1023 alt_cost += copy_cost (op, mode, classes[i], 0, NULL);
1025 /* The only other way this alternative can be used is if
1026 this is a constant that could be placed into memory. */
1027 else if (CONSTANT_P (op) && (allows_addr || allows_mem[i]))
1028 alt_cost += ira_memory_move_cost[mode][classes[i]][1];
1029 else
1030 alt_fail = 1;
1033 if (alt_fail)
1034 continue;
1036 op_cost_add = alt_cost * frequency;
1037 /* Finally, update the costs with the information we've
1038 calculated about this alternative. */
1039 for (i = 0; i < n_ops; i++)
1040 if (REG_P (ops[i]) && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
1042 struct costs *pp = op_costs[i], *qq = this_op_costs[i];
1043 int *pp_costs = pp->cost, *qq_costs = qq->cost;
1044 int scale = 1 + (recog_data.operand_type[i] == OP_INOUT);
1045 cost_classes_t cost_classes_ptr
1046 = regno_cost_classes[REGNO (ops[i])];
1048 pp->mem_cost = MIN (pp->mem_cost,
1049 (qq->mem_cost + op_cost_add) * scale);
1051 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1052 pp_costs[k]
1053 = MIN (pp_costs[k], (qq_costs[k] + op_cost_add) * scale);
1057 if (allocno_p)
1058 for (i = 0; i < n_ops; i++)
1060 ira_allocno_t a;
1061 rtx op = ops[i];
1063 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
1064 continue;
1065 a = ira_curr_regno_allocno_map [REGNO (op)];
1066 if (! ALLOCNO_BAD_SPILL_P (a) && insn_allows_mem[i] == 0)
1067 ALLOCNO_BAD_SPILL_P (a) = true;
1074 /* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudo registers. */
1075 static inline bool
1076 ok_for_index_p_nonstrict (rtx reg)
1078 unsigned regno = REGNO (reg);
1080 return regno >= FIRST_PSEUDO_REGISTER || REGNO_OK_FOR_INDEX_P (regno);
1083 /* A version of regno_ok_for_base_p for use here, when all
1084 pseudo-registers should count as OK. Arguments as for
1085 regno_ok_for_base_p. */
1086 static inline bool
1087 ok_for_base_p_nonstrict (rtx reg, machine_mode mode, addr_space_t as,
1088 enum rtx_code outer_code, enum rtx_code index_code)
1090 unsigned regno = REGNO (reg);
1092 if (regno >= FIRST_PSEUDO_REGISTER)
1093 return true;
1094 return ok_for_base_p_1 (regno, mode, as, outer_code, index_code);
1097 /* Record the pseudo registers we must reload into hard registers in a
1098 subexpression of a memory address, X.
1100 If CONTEXT is 0, we are looking at the base part of an address,
1101 otherwise we are looking at the index part.
1103 MODE and AS are the mode and address space of the memory reference;
1104 OUTER_CODE and INDEX_CODE give the context that the rtx appears in.
1105 These four arguments are passed down to base_reg_class.
1107 SCALE is twice the amount to multiply the cost by (it is twice so
1108 we can represent half-cost adjustments). */
1109 static void
1110 record_address_regs (machine_mode mode, addr_space_t as, rtx x,
1111 int context, enum rtx_code outer_code,
1112 enum rtx_code index_code, int scale)
1114 enum rtx_code code = GET_CODE (x);
1115 enum reg_class rclass;
1117 if (context == 1)
1118 rclass = INDEX_REG_CLASS;
1119 else
1120 rclass = base_reg_class (mode, as, outer_code, index_code);
1122 switch (code)
1124 case CONST_INT:
1125 case CONST:
1126 case CC0:
1127 case PC:
1128 case SYMBOL_REF:
1129 case LABEL_REF:
1130 return;
1132 case PLUS:
1133 /* When we have an address that is a sum, we must determine
1134 whether registers are "base" or "index" regs. If there is a
1135 sum of two registers, we must choose one to be the "base".
1136 Luckily, we can use the REG_POINTER to make a good choice
1137 most of the time. We only need to do this on machines that
1138 can have two registers in an address and where the base and
1139 index register classes are different.
1141 ??? This code used to set REGNO_POINTER_FLAG in some cases,
1142 but that seems bogus since it should only be set when we are
1143 sure the register is being used as a pointer. */
1145 rtx arg0 = XEXP (x, 0);
1146 rtx arg1 = XEXP (x, 1);
1147 enum rtx_code code0 = GET_CODE (arg0);
1148 enum rtx_code code1 = GET_CODE (arg1);
1150 /* Look inside subregs. */
1151 if (code0 == SUBREG)
1152 arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
1153 if (code1 == SUBREG)
1154 arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
1156 /* If this machine only allows one register per address, it
1157 must be in the first operand. */
1158 if (MAX_REGS_PER_ADDRESS == 1)
1159 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale);
1161 /* If index and base registers are the same on this machine,
1162 just record registers in any non-constant operands. We
1163 assume here, as well as in the tests below, that all
1164 addresses are in canonical form. */
1165 else if (INDEX_REG_CLASS
1166 == base_reg_class (VOIDmode, as, PLUS, SCRATCH))
1168 record_address_regs (mode, as, arg0, context, PLUS, code1, scale);
1169 if (! CONSTANT_P (arg1))
1170 record_address_regs (mode, as, arg1, context, PLUS, code0, scale);
1173 /* If the second operand is a constant integer, it doesn't
1174 change what class the first operand must be. */
1175 else if (CONST_SCALAR_INT_P (arg1))
1176 record_address_regs (mode, as, arg0, context, PLUS, code1, scale);
1177 /* If the second operand is a symbolic constant, the first
1178 operand must be an index register. */
1179 else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF)
1180 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale);
1181 /* If both operands are registers but one is already a hard
1182 register of index or reg-base class, give the other the
1183 class that the hard register is not. */
1184 else if (code0 == REG && code1 == REG
1185 && REGNO (arg0) < FIRST_PSEUDO_REGISTER
1186 && (ok_for_base_p_nonstrict (arg0, mode, as, PLUS, REG)
1187 || ok_for_index_p_nonstrict (arg0)))
1188 record_address_regs (mode, as, arg1,
1189 ok_for_base_p_nonstrict (arg0, mode, as,
1190 PLUS, REG) ? 1 : 0,
1191 PLUS, REG, scale);
1192 else if (code0 == REG && code1 == REG
1193 && REGNO (arg1) < FIRST_PSEUDO_REGISTER
1194 && (ok_for_base_p_nonstrict (arg1, mode, as, PLUS, REG)
1195 || ok_for_index_p_nonstrict (arg1)))
1196 record_address_regs (mode, as, arg0,
1197 ok_for_base_p_nonstrict (arg1, mode, as,
1198 PLUS, REG) ? 1 : 0,
1199 PLUS, REG, scale);
1200 /* If one operand is known to be a pointer, it must be the
1201 base with the other operand the index. Likewise if the
1202 other operand is a MULT. */
1203 else if ((code0 == REG && REG_POINTER (arg0)) || code1 == MULT)
1205 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale);
1206 record_address_regs (mode, as, arg1, 1, PLUS, code0, scale);
1208 else if ((code1 == REG && REG_POINTER (arg1)) || code0 == MULT)
1210 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale);
1211 record_address_regs (mode, as, arg1, 0, PLUS, code0, scale);
1213 /* Otherwise, count equal chances that each might be a base or
1214 index register. This case should be rare. */
1215 else
1217 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale / 2);
1218 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale / 2);
1219 record_address_regs (mode, as, arg1, 0, PLUS, code0, scale / 2);
1220 record_address_regs (mode, as, arg1, 1, PLUS, code0, scale / 2);
1223 break;
1225 /* Double the importance of an allocno that is incremented or
1226 decremented, since it would take two extra insns if it ends
1227 up in the wrong place. */
1228 case POST_MODIFY:
1229 case PRE_MODIFY:
1230 record_address_regs (mode, as, XEXP (x, 0), 0, code,
1231 GET_CODE (XEXP (XEXP (x, 1), 1)), 2 * scale);
1232 if (REG_P (XEXP (XEXP (x, 1), 1)))
1233 record_address_regs (mode, as, XEXP (XEXP (x, 1), 1), 1, code, REG,
1234 2 * scale);
1235 break;
1237 case POST_INC:
1238 case PRE_INC:
1239 case POST_DEC:
1240 case PRE_DEC:
1241 /* Double the importance of an allocno that is incremented or
1242 decremented, since it would take two extra insns if it ends
1243 up in the wrong place. */
1244 record_address_regs (mode, as, XEXP (x, 0), 0, code, SCRATCH, 2 * scale);
1245 break;
1247 case REG:
1249 struct costs *pp;
1250 int *pp_costs;
1251 enum reg_class i;
1252 int k, regno, add_cost;
1253 cost_classes_t cost_classes_ptr;
1254 enum reg_class *cost_classes;
1255 move_table *move_in_cost;
1257 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
1258 break;
1260 regno = REGNO (x);
1261 if (allocno_p)
1262 ALLOCNO_BAD_SPILL_P (ira_curr_regno_allocno_map[regno]) = true;
1263 pp = COSTS (costs, COST_INDEX (regno));
1264 add_cost = (ira_memory_move_cost[Pmode][rclass][1] * scale) / 2;
1265 if (INT_MAX - add_cost < pp->mem_cost)
1266 pp->mem_cost = INT_MAX;
1267 else
1268 pp->mem_cost += add_cost;
1269 cost_classes_ptr = regno_cost_classes[regno];
1270 cost_classes = cost_classes_ptr->classes;
1271 pp_costs = pp->cost;
1272 ira_init_register_move_cost_if_necessary (Pmode);
1273 move_in_cost = ira_may_move_in_cost[Pmode];
1274 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1276 i = cost_classes[k];
1277 add_cost = (move_in_cost[i][rclass] * scale) / 2;
1278 if (INT_MAX - add_cost < pp_costs[k])
1279 pp_costs[k] = INT_MAX;
1280 else
1281 pp_costs[k] += add_cost;
1284 break;
1286 default:
1288 const char *fmt = GET_RTX_FORMAT (code);
1289 int i;
1290 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1291 if (fmt[i] == 'e')
1292 record_address_regs (mode, as, XEXP (x, i), context, code, SCRATCH,
1293 scale);
1300 /* Calculate the costs of insn operands. */
1301 static void
1302 record_operand_costs (rtx_insn *insn, enum reg_class *pref)
1304 const char *constraints[MAX_RECOG_OPERANDS];
1305 machine_mode modes[MAX_RECOG_OPERANDS];
1306 rtx ops[MAX_RECOG_OPERANDS];
1307 rtx set;
1308 int i;
1310 for (i = 0; i < recog_data.n_operands; i++)
1312 constraints[i] = recog_data.constraints[i];
1313 modes[i] = recog_data.operand_mode[i];
1316 /* If we get here, we are set up to record the costs of all the
1317 operands for this insn. Start by initializing the costs. Then
1318 handle any address registers. Finally record the desired classes
1319 for any allocnos, doing it twice if some pair of operands are
1320 commutative. */
1321 for (i = 0; i < recog_data.n_operands; i++)
1323 memcpy (op_costs[i], init_cost, struct_costs_size);
1325 ops[i] = recog_data.operand[i];
1326 if (GET_CODE (recog_data.operand[i]) == SUBREG)
1327 recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);
1329 if (MEM_P (recog_data.operand[i]))
1330 record_address_regs (GET_MODE (recog_data.operand[i]),
1331 MEM_ADDR_SPACE (recog_data.operand[i]),
1332 XEXP (recog_data.operand[i], 0),
1333 0, MEM, SCRATCH, frequency * 2);
1334 else if (constraints[i][0] == 'p'
1335 || (insn_extra_address_constraint
1336 (lookup_constraint (constraints[i]))))
1337 record_address_regs (VOIDmode, ADDR_SPACE_GENERIC,
1338 recog_data.operand[i], 0, ADDRESS, SCRATCH,
1339 frequency * 2);
1342 /* Check for commutative in a separate loop so everything will have
1343 been initialized. We must do this even if one operand is a
1344 constant--see addsi3 in m68k.md. */
1345 for (i = 0; i < (int) recog_data.n_operands - 1; i++)
1346 if (constraints[i][0] == '%')
1348 const char *xconstraints[MAX_RECOG_OPERANDS];
1349 int j;
1351 /* Handle commutative operands by swapping the constraints.
1352 We assume the modes are the same. */
1353 for (j = 0; j < recog_data.n_operands; j++)
1354 xconstraints[j] = constraints[j];
1356 xconstraints[i] = constraints[i+1];
1357 xconstraints[i+1] = constraints[i];
1358 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1359 recog_data.operand, modes,
1360 xconstraints, insn, pref);
1362 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
1363 recog_data.operand, modes,
1364 constraints, insn, pref);
1366 /* If this insn is a single set copying operand 1 to operand 0 and
1367 one operand is an allocno with the other a hard reg or an allocno
1368 that prefers a hard register that is in its own register class
1369 then we may want to adjust the cost of that register class to -1.
1371 Avoid the adjustment if the source does not die to avoid
1372 stressing of register allocator by preferencing two colliding
1373 registers into single class.
1375 Also avoid the adjustment if a copy between hard registers of the
1376 class is expensive (ten times the cost of a default copy is
1377 considered arbitrarily expensive). This avoids losing when the
1378 preferred class is very expensive as the source of a copy
1379 instruction. */
1380 if ((set = single_set (insn)) != NULL_RTX
1381 /* In rare cases the single set insn might have less 2 operands
1382 as the source can be a fixed special reg. */
1383 && recog_data.n_operands > 1
1384 && ops[0] == SET_DEST (set) && ops[1] == SET_SRC (set))
1386 int regno, other_regno;
1387 rtx dest = SET_DEST (set);
1388 rtx src = SET_SRC (set);
1390 dest = SET_DEST (set);
1391 src = SET_SRC (set);
1392 if (GET_CODE (dest) == SUBREG
1393 && (GET_MODE_SIZE (GET_MODE (dest))
1394 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))))
1395 dest = SUBREG_REG (dest);
1396 if (GET_CODE (src) == SUBREG
1397 && (GET_MODE_SIZE (GET_MODE (src))
1398 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
1399 src = SUBREG_REG (src);
1400 if (REG_P (src) && REG_P (dest)
1401 && find_regno_note (insn, REG_DEAD, REGNO (src))
1402 && (((regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
1403 && (other_regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER)
1404 || ((regno = REGNO (dest)) >= FIRST_PSEUDO_REGISTER
1405 && (other_regno = REGNO (src)) < FIRST_PSEUDO_REGISTER)))
1407 machine_mode mode = GET_MODE (src);
1408 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1409 enum reg_class *cost_classes = cost_classes_ptr->classes;
1410 reg_class_t rclass;
1411 int k, nr;
1413 i = regno == (int) REGNO (src) ? 1 : 0;
1414 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1416 rclass = cost_classes[k];
1417 if (TEST_HARD_REG_BIT (reg_class_contents[rclass], other_regno)
1418 && (reg_class_size[(int) rclass]
1419 == ira_reg_class_max_nregs [(int) rclass][(int) mode]))
1421 if (reg_class_size[rclass] == 1)
1422 op_costs[i]->cost[k] = -frequency;
1423 else
1425 for (nr = 0;
1426 nr < hard_regno_nregs[other_regno][mode];
1427 nr++)
1428 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass],
1429 other_regno + nr))
1430 break;
1432 if (nr == hard_regno_nregs[other_regno][mode])
1433 op_costs[i]->cost[k] = -frequency;
1443 /* Process one insn INSN. Scan it and record each time it would save
1444 code to put a certain allocnos in a certain class. Return the last
1445 insn processed, so that the scan can be continued from there. */
1446 static rtx_insn *
1447 scan_one_insn (rtx_insn *insn)
1449 enum rtx_code pat_code;
1450 rtx set, note;
1451 int i, k;
1452 bool counted_mem;
1454 if (!NONDEBUG_INSN_P (insn))
1455 return insn;
1457 pat_code = GET_CODE (PATTERN (insn));
1458 if (pat_code == USE || pat_code == CLOBBER || pat_code == ASM_INPUT)
1459 return insn;
1461 counted_mem = false;
1462 set = single_set (insn);
1463 extract_insn (insn);
1465 /* If this insn loads a parameter from its stack slot, then it
1466 represents a savings, rather than a cost, if the parameter is
1467 stored in memory. Record this fact.
1469 Similarly if we're loading other constants from memory (constant
1470 pool, TOC references, small data areas, etc) and this is the only
1471 assignment to the destination pseudo.
1473 Don't do this if SET_SRC (set) isn't a general operand, if it is
1474 a memory requiring special instructions to load it, decreasing
1475 mem_cost might result in it being loaded using the specialized
1476 instruction into a register, then stored into stack and loaded
1477 again from the stack. See PR52208.
1479 Don't do this if SET_SRC (set) has side effect. See PR56124. */
1480 if (set != 0 && REG_P (SET_DEST (set)) && MEM_P (SET_SRC (set))
1481 && (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL_RTX
1482 && ((MEM_P (XEXP (note, 0))
1483 && !side_effects_p (SET_SRC (set)))
1484 || (CONSTANT_P (XEXP (note, 0))
1485 && targetm.legitimate_constant_p (GET_MODE (SET_DEST (set)),
1486 XEXP (note, 0))
1487 && REG_N_SETS (REGNO (SET_DEST (set))) == 1))
1488 && general_operand (SET_SRC (set), GET_MODE (SET_SRC (set))))
1490 enum reg_class cl = GENERAL_REGS;
1491 rtx reg = SET_DEST (set);
1492 int num = COST_INDEX (REGNO (reg));
1494 COSTS (costs, num)->mem_cost
1495 -= ira_memory_move_cost[GET_MODE (reg)][cl][1] * frequency;
1496 record_address_regs (GET_MODE (SET_SRC (set)),
1497 MEM_ADDR_SPACE (SET_SRC (set)),
1498 XEXP (SET_SRC (set), 0), 0, MEM, SCRATCH,
1499 frequency * 2);
1500 counted_mem = true;
1503 record_operand_costs (insn, pref);
1505 /* Now add the cost for each operand to the total costs for its
1506 allocno. */
1507 for (i = 0; i < recog_data.n_operands; i++)
1508 if (REG_P (recog_data.operand[i])
1509 && REGNO (recog_data.operand[i]) >= FIRST_PSEUDO_REGISTER)
1511 int regno = REGNO (recog_data.operand[i]);
1512 struct costs *p = COSTS (costs, COST_INDEX (regno));
1513 struct costs *q = op_costs[i];
1514 int *p_costs = p->cost, *q_costs = q->cost;
1515 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1516 int add_cost;
1518 /* If the already accounted for the memory "cost" above, don't
1519 do so again. */
1520 if (!counted_mem)
1522 add_cost = q->mem_cost;
1523 if (add_cost > 0 && INT_MAX - add_cost < p->mem_cost)
1524 p->mem_cost = INT_MAX;
1525 else
1526 p->mem_cost += add_cost;
1528 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1530 add_cost = q_costs[k];
1531 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1532 p_costs[k] = INT_MAX;
1533 else
1534 p_costs[k] += add_cost;
1538 return insn;
1543 /* Print allocnos costs to file F. */
1544 static void
1545 print_allocno_costs (FILE *f)
1547 int k;
1548 ira_allocno_t a;
1549 ira_allocno_iterator ai;
1551 ira_assert (allocno_p);
1552 fprintf (f, "\n");
1553 FOR_EACH_ALLOCNO (a, ai)
1555 int i, rclass;
1556 basic_block bb;
1557 int regno = ALLOCNO_REGNO (a);
1558 cost_classes_t cost_classes_ptr = regno_cost_classes[regno];
1559 enum reg_class *cost_classes = cost_classes_ptr->classes;
1561 i = ALLOCNO_NUM (a);
1562 fprintf (f, " a%d(r%d,", i, regno);
1563 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1564 fprintf (f, "b%d", bb->index);
1565 else
1566 fprintf (f, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
1567 fprintf (f, ") costs:");
1568 for (k = 0; k < cost_classes_ptr->num; k++)
1570 rclass = cost_classes[k];
1571 fprintf (f, " %s:%d", reg_class_names[rclass],
1572 COSTS (costs, i)->cost[k]);
1573 if (flag_ira_region == IRA_REGION_ALL
1574 || flag_ira_region == IRA_REGION_MIXED)
1575 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->cost[k]);
1577 fprintf (f, " MEM:%i", COSTS (costs, i)->mem_cost);
1578 if (flag_ira_region == IRA_REGION_ALL
1579 || flag_ira_region == IRA_REGION_MIXED)
1580 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->mem_cost);
1581 fprintf (f, "\n");
1585 /* Print pseudo costs to file F. */
1586 static void
1587 print_pseudo_costs (FILE *f)
1589 int regno, k;
1590 int rclass;
1591 cost_classes_t cost_classes_ptr;
1592 enum reg_class *cost_classes;
1594 ira_assert (! allocno_p);
1595 fprintf (f, "\n");
1596 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1598 if (REG_N_REFS (regno) <= 0)
1599 continue;
1600 cost_classes_ptr = regno_cost_classes[regno];
1601 cost_classes = cost_classes_ptr->classes;
1602 fprintf (f, " r%d costs:", regno);
1603 for (k = 0; k < cost_classes_ptr->num; k++)
1605 rclass = cost_classes[k];
1606 fprintf (f, " %s:%d", reg_class_names[rclass],
1607 COSTS (costs, regno)->cost[k]);
1609 fprintf (f, " MEM:%i\n", COSTS (costs, regno)->mem_cost);
1613 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1614 costs. */
1615 static void
1616 process_bb_for_costs (basic_block bb)
1618 rtx_insn *insn;
1620 frequency = REG_FREQ_FROM_BB (bb);
1621 if (frequency == 0)
1622 frequency = 1;
1623 FOR_BB_INSNS (bb, insn)
1624 insn = scan_one_insn (insn);
1627 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1628 costs. */
1629 static void
1630 process_bb_node_for_costs (ira_loop_tree_node_t loop_tree_node)
1632 basic_block bb;
1634 bb = loop_tree_node->bb;
1635 if (bb != NULL)
1636 process_bb_for_costs (bb);
1639 /* Find costs of register classes and memory for allocnos or pseudos
1640 and their best costs. Set up preferred, alternative and allocno
1641 classes for pseudos. */
1642 static void
1643 find_costs_and_classes (FILE *dump_file)
1645 int i, k, start, max_cost_classes_num;
1646 int pass;
1647 basic_block bb;
1648 enum reg_class *regno_best_class;
1650 init_recog ();
1651 regno_best_class
1652 = (enum reg_class *) ira_allocate (max_reg_num ()
1653 * sizeof (enum reg_class));
1654 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1655 regno_best_class[i] = NO_REGS;
1656 if (!resize_reg_info () && allocno_p
1657 && pseudo_classes_defined_p && flag_expensive_optimizations)
1659 ira_allocno_t a;
1660 ira_allocno_iterator ai;
1662 pref = pref_buffer;
1663 max_cost_classes_num = 1;
1664 FOR_EACH_ALLOCNO (a, ai)
1666 pref[ALLOCNO_NUM (a)] = reg_preferred_class (ALLOCNO_REGNO (a));
1667 setup_regno_cost_classes_by_aclass
1668 (ALLOCNO_REGNO (a), pref[ALLOCNO_NUM (a)]);
1669 max_cost_classes_num
1670 = MAX (max_cost_classes_num,
1671 regno_cost_classes[ALLOCNO_REGNO (a)]->num);
1673 start = 1;
1675 else
1677 pref = NULL;
1678 max_cost_classes_num = ira_important_classes_num;
1679 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1680 if (regno_reg_rtx[i] != NULL_RTX)
1681 setup_regno_cost_classes_by_mode (i, PSEUDO_REGNO_MODE (i));
1682 else
1683 setup_regno_cost_classes_by_aclass (i, ALL_REGS);
1684 start = 0;
1686 if (allocno_p)
1687 /* Clear the flag for the next compiled function. */
1688 pseudo_classes_defined_p = false;
1689 /* Normally we scan the insns once and determine the best class to
1690 use for each allocno. However, if -fexpensive-optimizations are
1691 on, we do so twice, the second time using the tentative best
1692 classes to guide the selection. */
1693 for (pass = start; pass <= flag_expensive_optimizations; pass++)
1695 if ((!allocno_p || internal_flag_ira_verbose > 0) && dump_file)
1696 fprintf (dump_file,
1697 "\nPass %i for finding pseudo/allocno costs\n\n", pass);
1699 if (pass != start)
1701 max_cost_classes_num = 1;
1702 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1704 setup_regno_cost_classes_by_aclass (i, regno_best_class[i]);
1705 max_cost_classes_num
1706 = MAX (max_cost_classes_num, regno_cost_classes[i]->num);
1710 struct_costs_size
1711 = sizeof (struct costs) + sizeof (int) * (max_cost_classes_num - 1);
1712 /* Zero out our accumulation of the cost of each class for each
1713 allocno. */
1714 memset (costs, 0, cost_elements_num * struct_costs_size);
1716 if (allocno_p)
1718 /* Scan the instructions and record each time it would save code
1719 to put a certain allocno in a certain class. */
1720 ira_traverse_loop_tree (true, ira_loop_tree_root,
1721 process_bb_node_for_costs, NULL);
1723 memcpy (total_allocno_costs, costs,
1724 max_struct_costs_size * ira_allocnos_num);
1726 else
1728 basic_block bb;
1730 FOR_EACH_BB_FN (bb, cfun)
1731 process_bb_for_costs (bb);
1734 if (pass == 0)
1735 pref = pref_buffer;
1737 /* Now for each allocno look at how desirable each class is and
1738 find which class is preferred. */
1739 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1741 ira_allocno_t a, parent_a;
1742 int rclass, a_num, parent_a_num, add_cost;
1743 ira_loop_tree_node_t parent;
1744 int best_cost, allocno_cost;
1745 enum reg_class best, alt_class;
1746 cost_classes_t cost_classes_ptr = regno_cost_classes[i];
1747 enum reg_class *cost_classes = cost_classes_ptr->classes;
1748 int *i_costs = temp_costs->cost;
1749 int i_mem_cost;
1750 int equiv_savings = regno_equiv_gains[i];
1752 if (! allocno_p)
1754 if (regno_reg_rtx[i] == NULL_RTX)
1755 continue;
1756 memcpy (temp_costs, COSTS (costs, i), struct_costs_size);
1757 i_mem_cost = temp_costs->mem_cost;
1759 else
1761 if (ira_regno_allocno_map[i] == NULL)
1762 continue;
1763 memset (temp_costs, 0, struct_costs_size);
1764 i_mem_cost = 0;
1765 /* Find cost of all allocnos with the same regno. */
1766 for (a = ira_regno_allocno_map[i];
1767 a != NULL;
1768 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1770 int *a_costs, *p_costs;
1772 a_num = ALLOCNO_NUM (a);
1773 if ((flag_ira_region == IRA_REGION_ALL
1774 || flag_ira_region == IRA_REGION_MIXED)
1775 && (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1776 && (parent_a = parent->regno_allocno_map[i]) != NULL
1777 /* There are no caps yet. */
1778 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE
1779 (a)->border_allocnos,
1780 ALLOCNO_NUM (a)))
1782 /* Propagate costs to upper levels in the region
1783 tree. */
1784 parent_a_num = ALLOCNO_NUM (parent_a);
1785 a_costs = COSTS (total_allocno_costs, a_num)->cost;
1786 p_costs = COSTS (total_allocno_costs, parent_a_num)->cost;
1787 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1789 add_cost = a_costs[k];
1790 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k])
1791 p_costs[k] = INT_MAX;
1792 else
1793 p_costs[k] += add_cost;
1795 add_cost = COSTS (total_allocno_costs, a_num)->mem_cost;
1796 if (add_cost > 0
1797 && (INT_MAX - add_cost
1798 < COSTS (total_allocno_costs,
1799 parent_a_num)->mem_cost))
1800 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1801 = INT_MAX;
1802 else
1803 COSTS (total_allocno_costs, parent_a_num)->mem_cost
1804 += add_cost;
1806 if (i >= first_moveable_pseudo && i < last_moveable_pseudo)
1807 COSTS (total_allocno_costs, parent_a_num)->mem_cost = 0;
1809 a_costs = COSTS (costs, a_num)->cost;
1810 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1812 add_cost = a_costs[k];
1813 if (add_cost > 0 && INT_MAX - add_cost < i_costs[k])
1814 i_costs[k] = INT_MAX;
1815 else
1816 i_costs[k] += add_cost;
1818 add_cost = COSTS (costs, a_num)->mem_cost;
1819 if (add_cost > 0 && INT_MAX - add_cost < i_mem_cost)
1820 i_mem_cost = INT_MAX;
1821 else
1822 i_mem_cost += add_cost;
1825 if (i >= first_moveable_pseudo && i < last_moveable_pseudo)
1826 i_mem_cost = 0;
1827 else if (equiv_savings < 0)
1828 i_mem_cost = -equiv_savings;
1829 else if (equiv_savings > 0)
1831 i_mem_cost = 0;
1832 for (k = cost_classes_ptr->num - 1; k >= 0; k--)
1833 i_costs[k] += equiv_savings;
1836 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1837 best = ALL_REGS;
1838 alt_class = NO_REGS;
1839 /* Find best common class for all allocnos with the same
1840 regno. */
1841 for (k = 0; k < cost_classes_ptr->num; k++)
1843 rclass = cost_classes[k];
1844 if (i_costs[k] < best_cost)
1846 best_cost = i_costs[k];
1847 best = (enum reg_class) rclass;
1849 else if (i_costs[k] == best_cost)
1850 best = ira_reg_class_subunion[best][rclass];
1851 if (pass == flag_expensive_optimizations
1852 /* We still prefer registers to memory even at this
1853 stage if their costs are the same. We will make
1854 a final decision during assigning hard registers
1855 when we have all info including more accurate
1856 costs which might be affected by assigning hard
1857 registers to other pseudos because the pseudos
1858 involved in moves can be coalesced. */
1859 && i_costs[k] <= i_mem_cost
1860 && (reg_class_size[reg_class_subunion[alt_class][rclass]]
1861 > reg_class_size[alt_class]))
1862 alt_class = reg_class_subunion[alt_class][rclass];
1864 alt_class = ira_allocno_class_translate[alt_class];
1865 if (best_cost > i_mem_cost)
1866 regno_aclass[i] = NO_REGS;
1867 else if (!optimize && !targetm.class_likely_spilled_p (best))
1868 /* Registers in the alternative class are likely to need
1869 longer or slower sequences than registers in the best class.
1870 When optimizing we make some effort to use the best class
1871 over the alternative class where possible, but at -O0 we
1872 effectively give the alternative class equal weight.
1873 We then run the risk of using slower alternative registers
1874 when plenty of registers from the best class are still free.
1875 This is especially true because live ranges tend to be very
1876 short in -O0 code and so register pressure tends to be low.
1878 Avoid that by ignoring the alternative class if the best
1879 class has plenty of registers. */
1880 regno_aclass[i] = best;
1881 else
1883 /* Make the common class the biggest class of best and
1884 alt_class. */
1885 regno_aclass[i]
1886 = ira_reg_class_superunion[best][alt_class];
1887 ira_assert (regno_aclass[i] != NO_REGS
1888 && ira_reg_allocno_class_p[regno_aclass[i]]);
1890 if (pass == flag_expensive_optimizations)
1892 if (best_cost > i_mem_cost)
1893 best = alt_class = NO_REGS;
1894 else if (best == alt_class)
1895 alt_class = NO_REGS;
1896 setup_reg_classes (i, best, alt_class, regno_aclass[i]);
1897 if ((!allocno_p || internal_flag_ira_verbose > 2)
1898 && dump_file != NULL)
1899 fprintf (dump_file,
1900 " r%d: preferred %s, alternative %s, allocno %s\n",
1901 i, reg_class_names[best], reg_class_names[alt_class],
1902 reg_class_names[regno_aclass[i]]);
1904 regno_best_class[i] = best;
1905 if (! allocno_p)
1907 pref[i] = best_cost > i_mem_cost ? NO_REGS : best;
1908 continue;
1910 for (a = ira_regno_allocno_map[i];
1911 a != NULL;
1912 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1914 enum reg_class aclass = regno_aclass[i];
1915 int a_num = ALLOCNO_NUM (a);
1916 int *total_a_costs = COSTS (total_allocno_costs, a_num)->cost;
1917 int *a_costs = COSTS (costs, a_num)->cost;
1919 if (aclass == NO_REGS)
1920 best = NO_REGS;
1921 else
1923 /* Finding best class which is subset of the common
1924 class. */
1925 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1926 allocno_cost = best_cost;
1927 best = ALL_REGS;
1928 for (k = 0; k < cost_classes_ptr->num; k++)
1930 rclass = cost_classes[k];
1931 if (! ira_class_subset_p[rclass][aclass])
1932 continue;
1933 if (total_a_costs[k] < best_cost)
1935 best_cost = total_a_costs[k];
1936 allocno_cost = a_costs[k];
1937 best = (enum reg_class) rclass;
1939 else if (total_a_costs[k] == best_cost)
1941 best = ira_reg_class_subunion[best][rclass];
1942 allocno_cost = MAX (allocno_cost, a_costs[k]);
1945 ALLOCNO_CLASS_COST (a) = allocno_cost;
1947 if (internal_flag_ira_verbose > 2 && dump_file != NULL
1948 && (pass == 0 || pref[a_num] != best))
1950 fprintf (dump_file, " a%d (r%d,", a_num, i);
1951 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1952 fprintf (dump_file, "b%d", bb->index);
1953 else
1954 fprintf (dump_file, "l%d",
1955 ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
1956 fprintf (dump_file, ") best %s, allocno %s\n",
1957 reg_class_names[best],
1958 reg_class_names[aclass]);
1960 pref[a_num] = best;
1961 if (pass == flag_expensive_optimizations && best != aclass
1962 && ira_class_hard_regs_num[best] > 0
1963 && (ira_reg_class_max_nregs[best][ALLOCNO_MODE (a)]
1964 >= ira_class_hard_regs_num[best]))
1966 int ind = cost_classes_ptr->index[aclass];
1968 ira_assert (ind >= 0);
1969 ira_init_register_move_cost_if_necessary (ALLOCNO_MODE (a));
1970 ira_add_allocno_pref (a, ira_class_hard_regs[best][0],
1971 (a_costs[ind] - ALLOCNO_CLASS_COST (a))
1972 / (ira_register_move_cost
1973 [ALLOCNO_MODE (a)][best][aclass]));
1974 for (k = 0; k < cost_classes_ptr->num; k++)
1975 if (ira_class_subset_p[cost_classes[k]][best])
1976 a_costs[k] = a_costs[ind];
1981 if (internal_flag_ira_verbose > 4 && dump_file)
1983 if (allocno_p)
1984 print_allocno_costs (dump_file);
1985 else
1986 print_pseudo_costs (dump_file);
1987 fprintf (dump_file,"\n");
1990 ira_free (regno_best_class);
1995 /* Process moves involving hard regs to modify allocno hard register
1996 costs. We can do this only after determining allocno class. If a
1997 hard register forms a register class, then moves with the hard
1998 register are already taken into account in class costs for the
1999 allocno. */
2000 static void
2001 process_bb_node_for_hard_reg_moves (ira_loop_tree_node_t loop_tree_node)
2003 int i, freq, src_regno, dst_regno, hard_regno, a_regno;
2004 bool to_p;
2005 ira_allocno_t a, curr_a;
2006 ira_loop_tree_node_t curr_loop_tree_node;
2007 enum reg_class rclass;
2008 basic_block bb;
2009 rtx_insn *insn;
2010 rtx set, src, dst;
2012 bb = loop_tree_node->bb;
2013 if (bb == NULL)
2014 return;
2015 freq = REG_FREQ_FROM_BB (bb);
2016 if (freq == 0)
2017 freq = 1;
2018 FOR_BB_INSNS (bb, insn)
2020 if (!NONDEBUG_INSN_P (insn))
2021 continue;
2022 set = single_set (insn);
2023 if (set == NULL_RTX)
2024 continue;
2025 dst = SET_DEST (set);
2026 src = SET_SRC (set);
2027 if (! REG_P (dst) || ! REG_P (src))
2028 continue;
2029 dst_regno = REGNO (dst);
2030 src_regno = REGNO (src);
2031 if (dst_regno >= FIRST_PSEUDO_REGISTER
2032 && src_regno < FIRST_PSEUDO_REGISTER)
2034 hard_regno = src_regno;
2035 a = ira_curr_regno_allocno_map[dst_regno];
2036 to_p = true;
2038 else if (src_regno >= FIRST_PSEUDO_REGISTER
2039 && dst_regno < FIRST_PSEUDO_REGISTER)
2041 hard_regno = dst_regno;
2042 a = ira_curr_regno_allocno_map[src_regno];
2043 to_p = false;
2045 else
2046 continue;
2047 rclass = ALLOCNO_CLASS (a);
2048 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass], hard_regno))
2049 continue;
2050 i = ira_class_hard_reg_index[rclass][hard_regno];
2051 if (i < 0)
2052 continue;
2053 a_regno = ALLOCNO_REGNO (a);
2054 for (curr_loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2055 curr_loop_tree_node != NULL;
2056 curr_loop_tree_node = curr_loop_tree_node->parent)
2057 if ((curr_a = curr_loop_tree_node->regno_allocno_map[a_regno]) != NULL)
2058 ira_add_allocno_pref (curr_a, hard_regno, freq);
2060 int cost;
2061 enum reg_class hard_reg_class;
2062 machine_mode mode;
2064 mode = ALLOCNO_MODE (a);
2065 hard_reg_class = REGNO_REG_CLASS (hard_regno);
2066 ira_init_register_move_cost_if_necessary (mode);
2067 cost = (to_p ? ira_register_move_cost[mode][hard_reg_class][rclass]
2068 : ira_register_move_cost[mode][rclass][hard_reg_class]) * freq;
2069 ira_allocate_and_set_costs (&ALLOCNO_HARD_REG_COSTS (a), rclass,
2070 ALLOCNO_CLASS_COST (a));
2071 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2072 rclass, 0);
2073 ALLOCNO_HARD_REG_COSTS (a)[i] -= cost;
2074 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[i] -= cost;
2075 ALLOCNO_CLASS_COST (a) = MIN (ALLOCNO_CLASS_COST (a),
2076 ALLOCNO_HARD_REG_COSTS (a)[i]);
2081 /* After we find hard register and memory costs for allocnos, define
2082 its class and modify hard register cost because insns moving
2083 allocno to/from hard registers. */
2084 static void
2085 setup_allocno_class_and_costs (void)
2087 int i, j, n, regno, hard_regno, num;
2088 int *reg_costs;
2089 enum reg_class aclass, rclass;
2090 ira_allocno_t a;
2091 ira_allocno_iterator ai;
2092 cost_classes_t cost_classes_ptr;
2094 ira_assert (allocno_p);
2095 FOR_EACH_ALLOCNO (a, ai)
2097 i = ALLOCNO_NUM (a);
2098 regno = ALLOCNO_REGNO (a);
2099 aclass = regno_aclass[regno];
2100 cost_classes_ptr = regno_cost_classes[regno];
2101 ira_assert (pref[i] == NO_REGS || aclass != NO_REGS);
2102 ALLOCNO_MEMORY_COST (a) = COSTS (costs, i)->mem_cost;
2103 ira_set_allocno_class (a, aclass);
2104 if (aclass == NO_REGS)
2105 continue;
2106 if (optimize && ALLOCNO_CLASS (a) != pref[i])
2108 n = ira_class_hard_regs_num[aclass];
2109 ALLOCNO_HARD_REG_COSTS (a)
2110 = reg_costs = ira_allocate_cost_vector (aclass);
2111 for (j = n - 1; j >= 0; j--)
2113 hard_regno = ira_class_hard_regs[aclass][j];
2114 if (TEST_HARD_REG_BIT (reg_class_contents[pref[i]], hard_regno))
2115 reg_costs[j] = ALLOCNO_CLASS_COST (a);
2116 else
2118 rclass = REGNO_REG_CLASS (hard_regno);
2119 num = cost_classes_ptr->index[rclass];
2120 if (num < 0)
2122 num = cost_classes_ptr->hard_regno_index[hard_regno];
2123 ira_assert (num >= 0);
2125 reg_costs[j] = COSTS (costs, i)->cost[num];
2130 if (optimize)
2131 ira_traverse_loop_tree (true, ira_loop_tree_root,
2132 process_bb_node_for_hard_reg_moves, NULL);
2137 /* Function called once during compiler work. */
2138 void
2139 ira_init_costs_once (void)
2141 int i;
2143 init_cost = NULL;
2144 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2146 op_costs[i] = NULL;
2147 this_op_costs[i] = NULL;
2149 temp_costs = NULL;
2152 /* Free allocated temporary cost vectors. */
2153 void
2154 target_ira_int::free_ira_costs ()
2156 int i;
2158 free (x_init_cost);
2159 x_init_cost = NULL;
2160 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2162 free (x_op_costs[i]);
2163 free (x_this_op_costs[i]);
2164 x_op_costs[i] = x_this_op_costs[i] = NULL;
2166 free (x_temp_costs);
2167 x_temp_costs = NULL;
2170 /* This is called each time register related information is
2171 changed. */
2172 void
2173 ira_init_costs (void)
2175 int i;
2177 this_target_ira_int->free_ira_costs ();
2178 max_struct_costs_size
2179 = sizeof (struct costs) + sizeof (int) * (ira_important_classes_num - 1);
2180 /* Don't use ira_allocate because vectors live through several IRA
2181 calls. */
2182 init_cost = (struct costs *) xmalloc (max_struct_costs_size);
2183 init_cost->mem_cost = 1000000;
2184 for (i = 0; i < ira_important_classes_num; i++)
2185 init_cost->cost[i] = 1000000;
2186 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
2188 op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
2189 this_op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
2191 temp_costs = (struct costs *) xmalloc (max_struct_costs_size);
2196 /* Common initialization function for ira_costs and
2197 ira_set_pseudo_classes. */
2198 static void
2199 init_costs (void)
2201 init_subregs_of_mode ();
2202 costs = (struct costs *) ira_allocate (max_struct_costs_size
2203 * cost_elements_num);
2204 pref_buffer = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
2205 * cost_elements_num);
2206 regno_aclass = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
2207 * max_reg_num ());
2208 regno_equiv_gains = (int *) ira_allocate (sizeof (int) * max_reg_num ());
2209 memset (regno_equiv_gains, 0, sizeof (int) * max_reg_num ());
2212 /* Common finalization function for ira_costs and
2213 ira_set_pseudo_classes. */
2214 static void
2215 finish_costs (void)
2217 finish_subregs_of_mode ();
2218 ira_free (regno_equiv_gains);
2219 ira_free (regno_aclass);
2220 ira_free (pref_buffer);
2221 ira_free (costs);
2224 /* Entry function which defines register class, memory and hard
2225 register costs for each allocno. */
2226 void
2227 ira_costs (void)
2229 allocno_p = true;
2230 cost_elements_num = ira_allocnos_num;
2231 init_costs ();
2232 total_allocno_costs = (struct costs *) ira_allocate (max_struct_costs_size
2233 * ira_allocnos_num);
2234 initiate_regno_cost_classes ();
2235 calculate_elim_costs_all_insns ();
2236 find_costs_and_classes (ira_dump_file);
2237 setup_allocno_class_and_costs ();
2238 finish_regno_cost_classes ();
2239 finish_costs ();
2240 ira_free (total_allocno_costs);
2243 /* Entry function which defines classes for pseudos.
2244 Set pseudo_classes_defined_p only if DEFINE_PSEUDO_CLASSES is true. */
2245 void
2246 ira_set_pseudo_classes (bool define_pseudo_classes, FILE *dump_file)
2248 allocno_p = false;
2249 internal_flag_ira_verbose = flag_ira_verbose;
2250 cost_elements_num = max_reg_num ();
2251 init_costs ();
2252 initiate_regno_cost_classes ();
2253 find_costs_and_classes (dump_file);
2254 finish_regno_cost_classes ();
2255 if (define_pseudo_classes)
2256 pseudo_classes_defined_p = true;
2258 finish_costs ();
2263 /* Change hard register costs for allocnos which lives through
2264 function calls. This is called only when we found all intersected
2265 calls during building allocno live ranges. */
2266 void
2267 ira_tune_allocno_costs (void)
2269 int j, n, regno;
2270 int cost, min_cost, *reg_costs;
2271 enum reg_class aclass, rclass;
2272 machine_mode mode;
2273 ira_allocno_t a;
2274 ira_allocno_iterator ai;
2275 ira_allocno_object_iterator oi;
2276 ira_object_t obj;
2277 bool skip_p;
2278 HARD_REG_SET *crossed_calls_clobber_regs;
2280 FOR_EACH_ALLOCNO (a, ai)
2282 aclass = ALLOCNO_CLASS (a);
2283 if (aclass == NO_REGS)
2284 continue;
2285 mode = ALLOCNO_MODE (a);
2286 n = ira_class_hard_regs_num[aclass];
2287 min_cost = INT_MAX;
2288 if (ALLOCNO_CALLS_CROSSED_NUM (a)
2289 != ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2291 ira_allocate_and_set_costs
2292 (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2293 ALLOCNO_CLASS_COST (a));
2294 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2295 for (j = n - 1; j >= 0; j--)
2297 regno = ira_class_hard_regs[aclass][j];
2298 skip_p = false;
2299 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2301 if (ira_hard_reg_set_intersection_p (regno, mode,
2302 OBJECT_CONFLICT_HARD_REGS
2303 (obj)))
2305 skip_p = true;
2306 break;
2309 if (skip_p)
2310 continue;
2311 rclass = REGNO_REG_CLASS (regno);
2312 cost = 0;
2313 crossed_calls_clobber_regs
2314 = &(ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
2315 if (ira_hard_reg_set_intersection_p (regno, mode,
2316 *crossed_calls_clobber_regs)
2317 && (ira_hard_reg_set_intersection_p (regno, mode,
2318 call_used_reg_set)
2319 || HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
2320 cost += (ALLOCNO_CALL_FREQ (a)
2321 * (ira_memory_move_cost[mode][rclass][0]
2322 + ira_memory_move_cost[mode][rclass][1]));
2323 #ifdef IRA_HARD_REGNO_ADD_COST_MULTIPLIER
2324 cost += ((ira_memory_move_cost[mode][rclass][0]
2325 + ira_memory_move_cost[mode][rclass][1])
2326 * ALLOCNO_FREQ (a)
2327 * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno) / 2);
2328 #endif
2329 if (INT_MAX - cost < reg_costs[j])
2330 reg_costs[j] = INT_MAX;
2331 else
2332 reg_costs[j] += cost;
2333 if (min_cost > reg_costs[j])
2334 min_cost = reg_costs[j];
2337 if (min_cost != INT_MAX)
2338 ALLOCNO_CLASS_COST (a) = min_cost;
2340 /* Some targets allow pseudos to be allocated to unaligned sequences
2341 of hard registers. However, selecting an unaligned sequence can
2342 unnecessarily restrict later allocations. So increase the cost of
2343 unaligned hard regs to encourage the use of aligned hard regs. */
2345 const int nregs = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2347 if (nregs > 1)
2349 ira_allocate_and_set_costs
2350 (&ALLOCNO_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a));
2351 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
2352 for (j = n - 1; j >= 0; j--)
2354 regno = ira_non_ordered_class_hard_regs[aclass][j];
2355 if ((regno % nregs) != 0)
2357 int index = ira_class_hard_reg_index[aclass][regno];
2358 ira_assert (index != -1);
2359 reg_costs[index] += ALLOCNO_FREQ (a);
2367 /* Add COST to the estimated gain for eliminating REGNO with its
2368 equivalence. If COST is zero, record that no such elimination is
2369 possible. */
2371 void
2372 ira_adjust_equiv_reg_cost (unsigned regno, int cost)
2374 if (cost == 0)
2375 regno_equiv_gains[regno] = 0;
2376 else
2377 regno_equiv_gains[regno] += cost;
2380 void
2381 ira_costs_c_finalize (void)
2383 this_target_ira_int->free_ira_costs ();