Mercurial > hg > CbC > CbC_gcc

comparison gcc/ira-costs.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 58ad6c70ea60
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* IRA hard register and memory cost calculation for allocnos.
2 Copyright (C) 2006, 2007, 2008
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "hard-reg-set.h"
27 #include "rtl.h"
28 #include "expr.h"
29 #include "tm_p.h"
30 #include "flags.h"
31 #include "basic-block.h"
32 #include "regs.h"
33 #include "addresses.h"
34 #include "insn-config.h"
35 #include "recog.h"
36 #include "toplev.h"
37 #include "target.h"
38 #include "params.h"
39 #include "ira-int.h"
40
41 /* The file contains code is similar to one in regclass but the code
42 works on the allocno basis. */
43
44 #ifdef FORBIDDEN_INC_DEC_CLASSES
45 /* Indexed by n, is TRUE if allocno with number N is used in an
46 auto-inc or auto-dec context. */
47 static bool *in_inc_dec;
48 #endif
49
50 /* The `costs' struct records the cost of using hard registers of each
51 class considered for the calculation and of using memory for each
52 allocno. */
53 struct costs
54 {
55 int mem_cost;
56 /* Costs for register classes start here. We process only some
57 register classes (cover classes on the 1st cost calculation
58 iteration and important classes on the 2nd iteration). */
59 int cost[1];
60 };
61
62 /* Initialized once. It is a maximal possible size of the allocated
63 struct costs. */
64 static int max_struct_costs_size;
65
66 /* Allocated and initialized once, and used to initialize cost values
67 for each insn. */
68 static struct costs *init_cost;
69
70 /* Allocated once, and used for temporary purposes. */
71 static struct costs *temp_costs;
72
73 /* Allocated once, and used for the cost calculation. */
74 static struct costs *op_costs[MAX_RECOG_OPERANDS];
75 static struct costs *this_op_costs[MAX_RECOG_OPERANDS];
76
77 /* Original and accumulated costs of each class for each allocno. */
78 static struct costs *allocno_costs, *total_costs;
79
80 /* Classes used for cost calculation. They may be different on
81 different iterations of the cost calculations or in different
82 optimization modes. */
83 static enum reg_class *cost_classes;
84
85 /* The size of the previous array. */
86 static int cost_classes_num;
87
88 /* Map: cost class -> order number (they start with 0) of the cost
89 class. The order number is negative for non-cost classes. */
90 static int cost_class_nums[N_REG_CLASSES];
91
92 /* It is the current size of struct costs. */
93 static int struct_costs_size;
94
95 /* Return pointer to structure containing costs of allocno with given
96 NUM in array ARR. */
97 #define COSTS_OF_ALLOCNO(arr, num) \
98 ((struct costs *) ((char *) (arr) + (num) * struct_costs_size))
99
100 /* Record register class preferences of each allocno. Null value
101 means no preferences. It happens on the 1st iteration of the cost
102 calculation. */
103 static enum reg_class *allocno_pref;
104
105 /* Allocated buffers for allocno_pref. */
106 static enum reg_class *allocno_pref_buffer;
107
108 /* Record register class of each allocno with the same regno. */
109 static enum reg_class *common_classes;
110
111 /* Execution frequency of the current insn. */
112 static int frequency;
113
114
115
116 /* Compute the cost of loading X into (if TO_P is TRUE) or from (if
117 TO_P is FALSE) a register of class RCLASS in mode MODE. X must not
118 be a pseudo register. */
119 static int
120 copy_cost (rtx x, enum machine_mode mode, enum reg_class rclass, bool to_p,
121 secondary_reload_info *prev_sri)
122 {
123 secondary_reload_info sri;
124 enum reg_class secondary_class = NO_REGS;
125
126 /* If X is a SCRATCH, there is actually nothing to move since we are
127 assuming optimal allocation. */
128 if (GET_CODE (x) == SCRATCH)
129 return 0;
130
131 /* Get the class we will actually use for a reload. */
132 rclass = PREFERRED_RELOAD_CLASS (x, rclass);
133
134 /* If we need a secondary reload for an intermediate, the cost is
135 that to load the input into the intermediate register, then to
136 copy it. */
137 sri.prev_sri = prev_sri;
138 sri.extra_cost = 0;
139 secondary_class = targetm.secondary_reload (to_p, x, rclass, mode, &sri);
140
141 if (ira_register_move_cost[mode] == NULL)
142 ira_init_register_move_cost (mode);
143
144 if (secondary_class != NO_REGS)
145 {
146 if (!move_cost[mode])
147 init_move_cost (mode);
148 return (move_cost[mode][secondary_class][rclass] + sri.extra_cost
149 + copy_cost (x, mode, secondary_class, to_p, &sri));
150 }
151
152 /* For memory, use the memory move cost, for (hard) registers, use
153 the cost to move between the register classes, and use 2 for
154 everything else (constants). */
155 if (MEM_P (x) || rclass == NO_REGS)
156 return sri.extra_cost + ira_memory_move_cost[mode][rclass][to_p != 0];
157 else if (REG_P (x))
158 {
159 if (!move_cost[mode])
160 init_move_cost (mode);
161 return (sri.extra_cost + move_cost[mode][REGNO_REG_CLASS (REGNO (x))][rclass]);
162 }
163 else
164 /* If this is a constant, we may eventually want to call rtx_cost
165 here. */
166 return sri.extra_cost + COSTS_N_INSNS (1);
167 }
168
169
170
171 /* Record the cost of using memory or hard registers of various
172 classes for the operands in INSN.
173
174 N_ALTS is the number of alternatives.
175 N_OPS is the number of operands.
176 OPS is an array of the operands.
177 MODES are the modes of the operands, in case any are VOIDmode.
178 CONSTRAINTS are the constraints to use for the operands. This array
179 is modified by this procedure.
180
181 This procedure works alternative by alternative. For each
182 alternative we assume that we will be able to allocate all allocnos
183 to their ideal register class and calculate the cost of using that
184 alternative. Then we compute, for each operand that is a
185 pseudo-register, the cost of having the allocno allocated to each
186 register class and using it in that alternative. To this cost is
187 added the cost of the alternative.
188
189 The cost of each class for this insn is its lowest cost among all
190 the alternatives. */
191 static void
192 record_reg_classes (int n_alts, int n_ops, rtx *ops,
193 enum machine_mode *modes, const char **constraints,
194 rtx insn, struct costs **op_costs,
195 enum reg_class *allocno_pref)
196 {
197 int alt;
198 int i, j, k;
199 rtx set;
200 int insn_allows_mem[MAX_RECOG_OPERANDS];
201
202 for (i = 0; i < n_ops; i++)
203 insn_allows_mem[i] = 0;
204
205 /* Process each alternative, each time minimizing an operand's cost
206 with the cost for each operand in that alternative. */
207 for (alt = 0; alt < n_alts; alt++)
208 {
209 enum reg_class classes[MAX_RECOG_OPERANDS];
210 int allows_mem[MAX_RECOG_OPERANDS];
211 int rclass;
212 int alt_fail = 0;
213 int alt_cost = 0, op_cost_add;
214
215 for (i = 0; i < n_ops; i++)
216 {
217 unsigned char c;
218 const char *p = constraints[i];
219 rtx op = ops[i];
220 enum machine_mode mode = modes[i];
221 int allows_addr = 0;
222 int win = 0;
223
224 /* Initially show we know nothing about the register class. */
225 classes[i] = NO_REGS;
226 allows_mem[i] = 0;
227
228 /* If this operand has no constraints at all, we can
229 conclude nothing about it since anything is valid. */
230 if (*p == 0)
231 {
232 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
233 memset (this_op_costs[i], 0, struct_costs_size);
234 continue;
235 }
236
237 /* If this alternative is only relevant when this operand
238 matches a previous operand, we do different things
239 depending on whether this operand is a allocno-reg or not.
240 We must process any modifiers for the operand before we
241 can make this test. */
242 while (*p == '%' || *p == '=' || *p == '+' || *p == '&')
243 p++;
244
245 if (p[0] >= '0' && p[0] <= '0' + i && (p[1] == ',' || p[1] == 0))
246 {
247 /* Copy class and whether memory is allowed from the
248 matching alternative. Then perform any needed cost
249 computations and/or adjustments. */
250 j = p[0] - '0';
251 classes[i] = classes[j];
252 allows_mem[i] = allows_mem[j];
253 if (allows_mem[i])
254 insn_allows_mem[i] = 1;
255
256 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
257 {
258 /* If this matches the other operand, we have no
259 added cost and we win. */
260 if (rtx_equal_p (ops[j], op))
261 win = 1;
262 /* If we can put the other operand into a register,
263 add to the cost of this alternative the cost to
264 copy this operand to the register used for the
265 other operand. */
266 else if (classes[j] != NO_REGS)
267 {
268 alt_cost += copy_cost (op, mode, classes[j], 1, NULL);
269 win = 1;
270 }
271 }
272 else if (! REG_P (ops[j])
273 || REGNO (ops[j]) < FIRST_PSEUDO_REGISTER)
274 {
275 /* This op is an allocno but the one it matches is
276 not. */
277
278 /* If we can't put the other operand into a
279 register, this alternative can't be used. */
280
281 if (classes[j] == NO_REGS)
282 alt_fail = 1;
283 /* Otherwise, add to the cost of this alternative
284 the cost to copy the other operand to the hard
285 register used for this operand. */
286 else
287 alt_cost += copy_cost (ops[j], mode, classes[j], 1, NULL);
288 }
289 else
290 {
291 /* The costs of this operand are not the same as the
292 other operand since move costs are not symmetric.
293 Moreover, if we cannot tie them, this alternative
294 needs to do a copy, which is one insn. */
295 struct costs *pp = this_op_costs[i];
296
297 if (ira_register_move_cost[mode] == NULL)
298 ira_init_register_move_cost (mode);
299
300 for (k = 0; k < cost_classes_num; k++)
301 {
302 rclass = cost_classes[k];
303 pp->cost[k]
304 = ((recog_data.operand_type[i] != OP_OUT
305 ? ira_may_move_in_cost[mode][rclass]
306 [classes[i]] * frequency : 0)
307 + (recog_data.operand_type[i] != OP_IN
308 ? ira_may_move_out_cost[mode][classes[i]]
309 [rclass] * frequency : 0));
310 }
311
312 /* If the alternative actually allows memory, make
313 things a bit cheaper since we won't need an extra
314 insn to load it. */
315 pp->mem_cost
316 = ((recog_data.operand_type[i] != OP_IN
317 ? ira_memory_move_cost[mode][classes[i]][0] : 0)
318 + (recog_data.operand_type[i] != OP_OUT
319 ? ira_memory_move_cost[mode][classes[i]][1] : 0)
320 - allows_mem[i]) * frequency;
321
322 /* If we have assigned a class to this allocno in our
323 first pass, add a cost to this alternative
324 corresponding to what we would add if this allocno
325 were not in the appropriate class. We could use
326 cover class here but it is less accurate
327 approximation. */
328 if (allocno_pref)
329 {
330 enum reg_class pref_class
331 = allocno_pref[ALLOCNO_NUM
332 (ira_curr_regno_allocno_map
333 [REGNO (op)])];
334
335 if (pref_class == NO_REGS)
336 alt_cost
337 += ((recog_data.operand_type[i] != OP_IN
338 ? ira_memory_move_cost[mode][classes[i]][0]
339 : 0)
340 + (recog_data.operand_type[i] != OP_OUT
341 ? ira_memory_move_cost[mode][classes[i]][1]
342 : 0));
343 else if (ira_reg_class_intersect
344 [pref_class][classes[i]] == NO_REGS)
345 alt_cost += (ira_register_move_cost
346 [mode][pref_class][classes[i]]);
347 }
348 if (REGNO (ops[i]) != REGNO (ops[j])
349 && ! find_reg_note (insn, REG_DEAD, op))
350 alt_cost += 2;
351
352 /* This is in place of ordinary cost computation for
353 this operand, so skip to the end of the
354 alternative (should be just one character). */
355 while (*p && *p++ != ',')
356 ;
357
358 constraints[i] = p;
359 continue;
360 }
361 }
362
363 /* Scan all the constraint letters. See if the operand
364 matches any of the constraints. Collect the valid
365 register classes and see if this operand accepts
366 memory. */
367 while ((c = *p))
368 {
369 switch (c)
370 {
371 case ',':
372 break;
373 case '*':
374 /* Ignore the next letter for this pass. */
375 c = *++p;
376 break;
377
378 case '?':
379 alt_cost += 2;
380 case '!': case '#': case '&':
381 case '0': case '1': case '2': case '3': case '4':
382 case '5': case '6': case '7': case '8': case '9':
383 break;
384
385 case 'p':
386 allows_addr = 1;
387 win = address_operand (op, GET_MODE (op));
388 /* We know this operand is an address, so we want it
389 to be allocated to a register that can be the
390 base of an address, i.e. BASE_REG_CLASS. */
391 classes[i]
392 = ira_reg_class_union[classes[i]]
393 [base_reg_class (VOIDmode, ADDRESS, SCRATCH)];
394 break;
395
396 case 'm': case 'o': case 'V':
397 /* It doesn't seem worth distinguishing between
398 offsettable and non-offsettable addresses
399 here. */
400 insn_allows_mem[i] = allows_mem[i] = 1;
401 if (MEM_P (op))
402 win = 1;
403 break;
404
405 case '<':
406 if (MEM_P (op)
407 && (GET_CODE (XEXP (op, 0)) == PRE_DEC
408 || GET_CODE (XEXP (op, 0)) == POST_DEC))
409 win = 1;
410 break;
411
412 case '>':
413 if (MEM_P (op)
414 && (GET_CODE (XEXP (op, 0)) == PRE_INC
415 || GET_CODE (XEXP (op, 0)) == POST_INC))
416 win = 1;
417 break;
418
419 case 'E':
420 case 'F':
421 if (GET_CODE (op) == CONST_DOUBLE
422 || (GET_CODE (op) == CONST_VECTOR
423 && (GET_MODE_CLASS (GET_MODE (op))
424 == MODE_VECTOR_FLOAT)))
425 win = 1;
426 break;
427
428 case 'G':
429 case 'H':
430 if (GET_CODE (op) == CONST_DOUBLE
431 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, p))
432 win = 1;
433 break;
434
435 case 's':
436 if (GET_CODE (op) == CONST_INT
437 || (GET_CODE (op) == CONST_DOUBLE
438 && GET_MODE (op) == VOIDmode))
439 break;
440
441 case 'i':
442 if (CONSTANT_P (op)
443 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op)))
444 win = 1;
445 break;
446
447 case 'n':
448 if (GET_CODE (op) == CONST_INT
449 || (GET_CODE (op) == CONST_DOUBLE
450 && GET_MODE (op) == VOIDmode))
451 win = 1;
452 break;
453
454 case 'I':
455 case 'J':
456 case 'K':
457 case 'L':
458 case 'M':
459 case 'N':
460 case 'O':
461 case 'P':
462 if (GET_CODE (op) == CONST_INT
463 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, p))
464 win = 1;
465 break;
466
467 case 'X':
468 win = 1;
469 break;
470
471 case 'g':
472 if (MEM_P (op)
473 || (CONSTANT_P (op)
474 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))))
475 win = 1;
476 insn_allows_mem[i] = allows_mem[i] = 1;
477 case 'r':
478 classes[i] = ira_reg_class_union[classes[i]][GENERAL_REGS];
479 break;
480
481 default:
482 if (REG_CLASS_FROM_CONSTRAINT (c, p) != NO_REGS)
483 classes[i] = ira_reg_class_union[classes[i]]
484 [REG_CLASS_FROM_CONSTRAINT (c, p)];
485 #ifdef EXTRA_CONSTRAINT_STR
486 else if (EXTRA_CONSTRAINT_STR (op, c, p))
487 win = 1;
488
489 if (EXTRA_MEMORY_CONSTRAINT (c, p))
490 {
491 /* Every MEM can be reloaded to fit. */
492 insn_allows_mem[i] = allows_mem[i] = 1;
493 if (MEM_P (op))
494 win = 1;
495 }
496 if (EXTRA_ADDRESS_CONSTRAINT (c, p))
497 {
498 /* Every address can be reloaded to fit. */
499 allows_addr = 1;
500 if (address_operand (op, GET_MODE (op)))
501 win = 1;
502 /* We know this operand is an address, so we
503 want it to be allocated to a hard register
504 that can be the base of an address,
505 i.e. BASE_REG_CLASS. */
506 classes[i]
507 = ira_reg_class_union[classes[i]]
508 [base_reg_class (VOIDmode, ADDRESS, SCRATCH)];
509 }
510 #endif
511 break;
512 }
513 p += CONSTRAINT_LEN (c, p);
514 if (c == ',')
515 break;
516 }
517
518 constraints[i] = p;
519
520 /* How we account for this operand now depends on whether it
521 is a pseudo register or not. If it is, we first check if
522 any register classes are valid. If not, we ignore this
523 alternative, since we want to assume that all allocnos get
524 allocated for register preferencing. If some register
525 class is valid, compute the costs of moving the allocno
526 into that class. */
527 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER)
528 {
529 if (classes[i] == NO_REGS)
530 {
531 /* We must always fail if the operand is a REG, but
532 we did not find a suitable class.
533
534 Otherwise we may perform an uninitialized read
535 from this_op_costs after the `continue' statement
536 below. */
537 alt_fail = 1;
538 }
539 else
540 {
541 struct costs *pp = this_op_costs[i];
542
543 if (ira_register_move_cost[mode] == NULL)
544 ira_init_register_move_cost (mode);
545
546 for (k = 0; k < cost_classes_num; k++)
547 {
548 rclass = cost_classes[k];
549 pp->cost[k]
550 = ((recog_data.operand_type[i] != OP_OUT
551 ? ira_may_move_in_cost[mode][rclass]
552 [classes[i]] * frequency : 0)
553 + (recog_data.operand_type[i] != OP_IN
554 ? ira_may_move_out_cost[mode][classes[i]]
555 [rclass] * frequency : 0));
556 }
557
558 /* If the alternative actually allows memory, make
559 things a bit cheaper since we won't need an extra
560 insn to load it. */
561 pp->mem_cost
562 = ((recog_data.operand_type[i] != OP_IN
563 ? ira_memory_move_cost[mode][classes[i]][0] : 0)
564 + (recog_data.operand_type[i] != OP_OUT
565 ? ira_memory_move_cost[mode][classes[i]][1] : 0)
566 - allows_mem[i]) * frequency;
567 /* If we have assigned a class to this allocno in our
568 first pass, add a cost to this alternative
569 corresponding to what we would add if this allocno
570 were not in the appropriate class. We could use
571 cover class here but it is less accurate
572 approximation. */
573 if (allocno_pref)
574 {
575 enum reg_class pref_class
576 = allocno_pref[ALLOCNO_NUM
577 (ira_curr_regno_allocno_map
578 [REGNO (op)])];
579
580 if (pref_class == NO_REGS)
581 alt_cost
582 += ((recog_data.operand_type[i] != OP_IN
583 ? ira_memory_move_cost[mode][classes[i]][0]
584 : 0)
585 + (recog_data.operand_type[i] != OP_OUT
586 ? ira_memory_move_cost[mode][classes[i]][1]
587 : 0));
588 else if (ira_reg_class_intersect[pref_class][classes[i]]
589 == NO_REGS)
590 alt_cost += (ira_register_move_cost
591 [mode][pref_class][classes[i]]);
592 }
593 }
594 }
595
596 /* Otherwise, if this alternative wins, either because we
597 have already determined that or if we have a hard
598 register of the proper class, there is no cost for this
599 alternative. */
600 else if (win || (REG_P (op)
601 && reg_fits_class_p (op, classes[i],
602 0, GET_MODE (op))))
603 ;
604
605 /* If registers are valid, the cost of this alternative
606 includes copying the object to and/or from a
607 register. */
608 else if (classes[i] != NO_REGS)
609 {
610 if (recog_data.operand_type[i] != OP_OUT)
611 alt_cost += copy_cost (op, mode, classes[i], 1, NULL);
612
613 if (recog_data.operand_type[i] != OP_IN)
614 alt_cost += copy_cost (op, mode, classes[i], 0, NULL);
615 }
616 /* The only other way this alternative can be used is if
617 this is a constant that could be placed into memory. */
618 else if (CONSTANT_P (op) && (allows_addr || allows_mem[i]))
619 alt_cost += ira_memory_move_cost[mode][classes[i]][1];
620 else
621 alt_fail = 1;
622 }
623
624 if (alt_fail)
625 continue;
626
627 op_cost_add = alt_cost * frequency;
628 /* Finally, update the costs with the information we've
629 calculated about this alternative. */
630 for (i = 0; i < n_ops; i++)
631 if (REG_P (ops[i]) && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
632 {
633 struct costs *pp = op_costs[i], *qq = this_op_costs[i];
634 int scale = 1 + (recog_data.operand_type[i] == OP_INOUT);
635
636 pp->mem_cost = MIN (pp->mem_cost,
637 (qq->mem_cost + op_cost_add) * scale);
638
639 for (k = 0; k < cost_classes_num; k++)
640 pp->cost[k]
641 = MIN (pp->cost[k], (qq->cost[k] + op_cost_add) * scale);
642 }
643 }
644
645 for (i = 0; i < n_ops; i++)
646 {
647 ira_allocno_t a;
648 rtx op = ops[i];
649
650 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER)
651 continue;
652 a = ira_curr_regno_allocno_map [REGNO (op)];
653 if (! ALLOCNO_BAD_SPILL_P (a) && insn_allows_mem[i] == 0)
654 ALLOCNO_BAD_SPILL_P (a) = true;
655 }
656
657 /* If this insn is a single set copying operand 1 to operand 0 and
658 one operand is an allocno with the other a hard reg or an allocno
659 that prefers a hard register that is in its own register class
660 then we may want to adjust the cost of that register class to -1.
661
662 Avoid the adjustment if the source does not die to avoid
663 stressing of register allocator by preferrencing two colliding
664 registers into single class.
665
666 Also avoid the adjustment if a copy between hard registers of the
667 class is expensive (ten times the cost of a default copy is
668 considered arbitrarily expensive). This avoids losing when the
669 preferred class is very expensive as the source of a copy
670 instruction. */
671 if ((set = single_set (insn)) != 0
672 && ops[0] == SET_DEST (set) && ops[1] == SET_SRC (set)
673 && REG_P (ops[0]) && REG_P (ops[1])
674 && find_regno_note (insn, REG_DEAD, REGNO (ops[1])))
675 for (i = 0; i <= 1; i++)
676 if (REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER)
677 {
678 unsigned int regno = REGNO (ops[!i]);
679 enum machine_mode mode = GET_MODE (ops[!i]);
680 int rclass;
681 unsigned int nr;
682
683 if (regno < FIRST_PSEUDO_REGISTER)
684 for (k = 0; k < cost_classes_num; k++)
685 {
686 rclass = cost_classes[k];
687 if (TEST_HARD_REG_BIT (reg_class_contents[rclass], regno)
688 && (reg_class_size[rclass]
689 == (unsigned) CLASS_MAX_NREGS (rclass, mode)))
690 {
691 if (reg_class_size[rclass] == 1)
692 op_costs[i]->cost[k] = -frequency;
693 else
694 {
695 for (nr = 0;
696 nr < (unsigned) hard_regno_nregs[regno][mode];
697 nr++)
698 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass],
699 regno + nr))
700 break;
701
702 if (nr == (unsigned) hard_regno_nregs[regno][mode])
703 op_costs[i]->cost[k] = -frequency;
704 }
705 }
706 }
707 }
708 }
709
710
711
712 /* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudo registers. */
713 static inline bool
714 ok_for_index_p_nonstrict (rtx reg)
715 {
716 unsigned regno = REGNO (reg);
717
718 return regno >= FIRST_PSEUDO_REGISTER || REGNO_OK_FOR_INDEX_P (regno);
719 }
720
721 /* A version of regno_ok_for_base_p for use here, when all
722 pseudo-registers should count as OK. Arguments as for
723 regno_ok_for_base_p. */
724 static inline bool
725 ok_for_base_p_nonstrict (rtx reg, enum machine_mode mode,
726 enum rtx_code outer_code, enum rtx_code index_code)
727 {
728 unsigned regno = REGNO (reg);
729
730 if (regno >= FIRST_PSEUDO_REGISTER)
731 return true;
732 return ok_for_base_p_1 (regno, mode, outer_code, index_code);
733 }
734
735 /* Record the pseudo registers we must reload into hard registers in a
736 subexpression of a memory address, X.
737
738 If CONTEXT is 0, we are looking at the base part of an address,
739 otherwise we are looking at the index part.
740
741 MODE is the mode of the memory reference; OUTER_CODE and INDEX_CODE
742 give the context that the rtx appears in. These three arguments
743 are passed down to base_reg_class.
744
745 SCALE is twice the amount to multiply the cost by (it is twice so
746 we can represent half-cost adjustments). */
747 static void
748 record_address_regs (enum machine_mode mode, rtx x, int context,
749 enum rtx_code outer_code, enum rtx_code index_code,
750 int scale)
751 {
752 enum rtx_code code = GET_CODE (x);
753 enum reg_class rclass;
754
755 if (context == 1)
756 rclass = INDEX_REG_CLASS;
757 else
758 rclass = base_reg_class (mode, outer_code, index_code);
759
760 switch (code)
761 {
762 case CONST_INT:
763 case CONST:
764 case CC0:
765 case PC:
766 case SYMBOL_REF:
767 case LABEL_REF:
768 return;
769
770 case PLUS:
771 /* When we have an address that is a sum, we must determine
772 whether registers are "base" or "index" regs. If there is a
773 sum of two registers, we must choose one to be the "base".
774 Luckily, we can use the REG_POINTER to make a good choice
775 most of the time. We only need to do this on machines that
776 can have two registers in an address and where the base and
777 index register classes are different.
778
779 ??? This code used to set REGNO_POINTER_FLAG in some cases,
780 but that seems bogus since it should only be set when we are
781 sure the register is being used as a pointer. */
782 {
783 rtx arg0 = XEXP (x, 0);
784 rtx arg1 = XEXP (x, 1);
785 enum rtx_code code0 = GET_CODE (arg0);
786 enum rtx_code code1 = GET_CODE (arg1);
787
788 /* Look inside subregs. */
789 if (code0 == SUBREG)
790 arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
791 if (code1 == SUBREG)
792 arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
793
794 /* If this machine only allows one register per address, it
795 must be in the first operand. */
796 if (MAX_REGS_PER_ADDRESS == 1)
797 record_address_regs (mode, arg0, 0, PLUS, code1, scale);
798
799 /* If index and base registers are the same on this machine,
800 just record registers in any non-constant operands. We
801 assume here, as well as in the tests below, that all
802 addresses are in canonical form. */
803 else if (INDEX_REG_CLASS == base_reg_class (VOIDmode, PLUS, SCRATCH))
804 {
805 record_address_regs (mode, arg0, context, PLUS, code1, scale);
806 if (! CONSTANT_P (arg1))
807 record_address_regs (mode, arg1, context, PLUS, code0, scale);
808 }
809
810 /* If the second operand is a constant integer, it doesn't
811 change what class the first operand must be. */
812 else if (code1 == CONST_INT || code1 == CONST_DOUBLE)
813 record_address_regs (mode, arg0, context, PLUS, code1, scale);
814 /* If the second operand is a symbolic constant, the first
815 operand must be an index register. */
816 else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF)
817 record_address_regs (mode, arg0, 1, PLUS, code1, scale);
818 /* If both operands are registers but one is already a hard
819 register of index or reg-base class, give the other the
820 class that the hard register is not. */
821 else if (code0 == REG && code1 == REG
822 && REGNO (arg0) < FIRST_PSEUDO_REGISTER
823 && (ok_for_base_p_nonstrict (arg0, mode, PLUS, REG)
824 || ok_for_index_p_nonstrict (arg0)))
825 record_address_regs (mode, arg1,
826 ok_for_base_p_nonstrict (arg0, mode, PLUS, REG)
827 ? 1 : 0,
828 PLUS, REG, scale);
829 else if (code0 == REG && code1 == REG
830 && REGNO (arg1) < FIRST_PSEUDO_REGISTER
831 && (ok_for_base_p_nonstrict (arg1, mode, PLUS, REG)
832 || ok_for_index_p_nonstrict (arg1)))
833 record_address_regs (mode, arg0,
834 ok_for_base_p_nonstrict (arg1, mode, PLUS, REG)
835 ? 1 : 0,
836 PLUS, REG, scale);
837 /* If one operand is known to be a pointer, it must be the
838 base with the other operand the index. Likewise if the
839 other operand is a MULT. */
840 else if ((code0 == REG && REG_POINTER (arg0)) || code1 == MULT)
841 {
842 record_address_regs (mode, arg0, 0, PLUS, code1, scale);
843 record_address_regs (mode, arg1, 1, PLUS, code0, scale);
844 }
845 else if ((code1 == REG && REG_POINTER (arg1)) || code0 == MULT)
846 {
847 record_address_regs (mode, arg0, 1, PLUS, code1, scale);
848 record_address_regs (mode, arg1, 0, PLUS, code0, scale);
849 }
850 /* Otherwise, count equal chances that each might be a base or
851 index register. This case should be rare. */
852 else
853 {
854 record_address_regs (mode, arg0, 0, PLUS, code1, scale / 2);
855 record_address_regs (mode, arg0, 1, PLUS, code1, scale / 2);
856 record_address_regs (mode, arg1, 0, PLUS, code0, scale / 2);
857 record_address_regs (mode, arg1, 1, PLUS, code0, scale / 2);
858 }
859 }
860 break;
861
862 /* Double the importance of an allocno that is incremented or
863 decremented, since it would take two extra insns if it ends
864 up in the wrong place. */
865 case POST_MODIFY:
866 case PRE_MODIFY:
867 record_address_regs (mode, XEXP (x, 0), 0, code,
868 GET_CODE (XEXP (XEXP (x, 1), 1)), 2 * scale);
869 if (REG_P (XEXP (XEXP (x, 1), 1)))
870 record_address_regs (mode, XEXP (XEXP (x, 1), 1), 1, code, REG,
871 2 * scale);
872 break;
873
874 case POST_INC:
875 case PRE_INC:
876 case POST_DEC:
877 case PRE_DEC:
878 /* Double the importance of an allocno that is incremented or
879 decremented, since it would take two extra insns if it ends
880 up in the wrong place. If the operand is a pseudo-register,
881 show it is being used in an INC_DEC context. */
882 #ifdef FORBIDDEN_INC_DEC_CLASSES
883 if (REG_P (XEXP (x, 0))
884 && REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER)
885 in_inc_dec[ALLOCNO_NUM (ira_curr_regno_allocno_map
886 [REGNO (XEXP (x, 0))])] = true;
887 #endif
888 record_address_regs (mode, XEXP (x, 0), 0, code, SCRATCH, 2 * scale);
889 break;
890
891 case REG:
892 {
893 struct costs *pp;
894 int i, k;
895
896 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
897 break;
898
899 ALLOCNO_BAD_SPILL_P (ira_curr_regno_allocno_map[REGNO (x)]) = true;
900 pp = COSTS_OF_ALLOCNO (allocno_costs,
901 ALLOCNO_NUM (ira_curr_regno_allocno_map
902 [REGNO (x)]));
903 pp->mem_cost += (ira_memory_move_cost[Pmode][rclass][1] * scale) / 2;
904 if (ira_register_move_cost[Pmode] == NULL)
905 ira_init_register_move_cost (Pmode);
906 for (k = 0; k < cost_classes_num; k++)
907 {
908 i = cost_classes[k];
909 pp->cost[k]
910 += (ira_may_move_in_cost[Pmode][i][rclass] * scale) / 2;
911 }
912 }
913 break;
914
915 default:
916 {
917 const char *fmt = GET_RTX_FORMAT (code);
918 int i;
919 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
920 if (fmt[i] == 'e')
921 record_address_regs (mode, XEXP (x, i), context, code, SCRATCH,
922 scale);
923 }
924 }
925 }
926
927
928
929 /* Calculate the costs of insn operands. */
930 static void
931 record_operand_costs (rtx insn, struct costs **op_costs,
932 enum reg_class *allocno_pref)
933 {
934 const char *constraints[MAX_RECOG_OPERANDS];
935 enum machine_mode modes[MAX_RECOG_OPERANDS];
936 int i;
937
938 for (i = 0; i < recog_data.n_operands; i++)
939 {
940 constraints[i] = recog_data.constraints[i];
941 modes[i] = recog_data.operand_mode[i];
942 }
943
944 /* If we get here, we are set up to record the costs of all the
945 operands for this insn. Start by initializing the costs. Then
946 handle any address registers. Finally record the desired classes
947 for any allocnos, doing it twice if some pair of operands are
948 commutative. */
949 for (i = 0; i < recog_data.n_operands; i++)
950 {
951 memcpy (op_costs[i], init_cost, struct_costs_size);
952
953 if (GET_CODE (recog_data.operand[i]) == SUBREG)
954 recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);
955
956 if (MEM_P (recog_data.operand[i]))
957 record_address_regs (GET_MODE (recog_data.operand[i]),
958 XEXP (recog_data.operand[i], 0),
959 0, MEM, SCRATCH, frequency * 2);
960 else if (constraints[i][0] == 'p'
961 || EXTRA_ADDRESS_CONSTRAINT (constraints[i][0],
962 constraints[i]))
963 record_address_regs (VOIDmode, recog_data.operand[i], 0, ADDRESS,
964 SCRATCH, frequency * 2);
965 }
966
967 /* Check for commutative in a separate loop so everything will have
968 been initialized. We must do this even if one operand is a
969 constant--see addsi3 in m68k.md. */
970 for (i = 0; i < (int) recog_data.n_operands - 1; i++)
971 if (constraints[i][0] == '%')
972 {
973 const char *xconstraints[MAX_RECOG_OPERANDS];
974 int j;
975
976 /* Handle commutative operands by swapping the constraints.
977 We assume the modes are the same. */
978 for (j = 0; j < recog_data.n_operands; j++)
979 xconstraints[j] = constraints[j];
980
981 xconstraints[i] = constraints[i+1];
982 xconstraints[i+1] = constraints[i];
983 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
984 recog_data.operand, modes,
985 xconstraints, insn, op_costs, allocno_pref);
986 }
987 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands,
988 recog_data.operand, modes,
989 constraints, insn, op_costs, allocno_pref);
990 }
991
992
993
994 /* Process one insn INSN. Scan it and record each time it would save
995 code to put a certain allocnos in a certain class. Return the last
996 insn processed, so that the scan can be continued from there. */
997 static rtx
998 scan_one_insn (rtx insn)
999 {
1000 enum rtx_code pat_code;
1001 rtx set, note;
1002 int i, k;
1003
1004 if (!INSN_P (insn))
1005 return insn;
1006
1007 pat_code = GET_CODE (PATTERN (insn));
1008 if (pat_code == USE || pat_code == CLOBBER || pat_code == ASM_INPUT
1009 || pat_code == ADDR_VEC || pat_code == ADDR_DIFF_VEC)
1010 return insn;
1011
1012 set = single_set (insn);
1013 extract_insn (insn);
1014
1015 /* If this insn loads a parameter from its stack slot, then it
1016 represents a savings, rather than a cost, if the parameter is
1017 stored in memory. Record this fact. */
1018 if (set != 0 && REG_P (SET_DEST (set)) && MEM_P (SET_SRC (set))
1019 && (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL_RTX
1020 && MEM_P (XEXP (note, 0)))
1021 {
1022 enum reg_class cl = GENERAL_REGS;
1023 rtx reg = SET_DEST (set);
1024 int num = ALLOCNO_NUM (ira_curr_regno_allocno_map[REGNO (reg)]);
1025
1026 if (allocno_pref)
1027 cl = allocno_pref[num];
1028 COSTS_OF_ALLOCNO (allocno_costs, num)->mem_cost
1029 -= ira_memory_move_cost[GET_MODE (reg)][cl][1] * frequency;
1030 record_address_regs (GET_MODE (SET_SRC (set)), XEXP (SET_SRC (set), 0),
1031 0, MEM, SCRATCH, frequency * 2);
1032 }
1033
1034 record_operand_costs (insn, op_costs, allocno_pref);
1035
1036 /* Now add the cost for each operand to the total costs for its
1037 allocno. */
1038 for (i = 0; i < recog_data.n_operands; i++)
1039 if (REG_P (recog_data.operand[i])
1040 && REGNO (recog_data.operand[i]) >= FIRST_PSEUDO_REGISTER)
1041 {
1042 int regno = REGNO (recog_data.operand[i]);
1043 struct costs *p
1044 = COSTS_OF_ALLOCNO (allocno_costs,
1045 ALLOCNO_NUM (ira_curr_regno_allocno_map[regno]));
1046 struct costs *q = op_costs[i];
1047
1048 p->mem_cost += q->mem_cost;
1049 for (k = 0; k < cost_classes_num; k++)
1050 p->cost[k] += q->cost[k];
1051 }
1052
1053 return insn;
1054 }
1055
1056
1057
1058 /* Print allocnos costs to file F. */
1059 static void
1060 print_costs (FILE *f)
1061 {
1062 int k;
1063 ira_allocno_t a;
1064 ira_allocno_iterator ai;
1065
1066 fprintf (f, "\n");
1067 FOR_EACH_ALLOCNO (a, ai)
1068 {
1069 int i, rclass;
1070 basic_block bb;
1071 int regno = ALLOCNO_REGNO (a);
1072
1073 i = ALLOCNO_NUM (a);
1074 fprintf (f, " a%d(r%d,", i, regno);
1075 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1076 fprintf (f, "b%d", bb->index);
1077 else
1078 fprintf (f, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
1079 fprintf (f, ") costs:");
1080 for (k = 0; k < cost_classes_num; k++)
1081 {
1082 rclass = cost_classes[k];
1083 if (contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (regno)]
1084 #ifdef FORBIDDEN_INC_DEC_CLASSES
1085 && (! in_inc_dec[i] || ! forbidden_inc_dec_class[rclass])
1086 #endif
1087 #ifdef CANNOT_CHANGE_MODE_CLASS
1088 && ! invalid_mode_change_p (regno, (enum reg_class) rclass,
1089 PSEUDO_REGNO_MODE (regno))
1090 #endif
1091 )
1092 {
1093 fprintf (f, " %s:%d", reg_class_names[rclass],
1094 COSTS_OF_ALLOCNO (allocno_costs, i)->cost[k]);
1095 if (flag_ira_region == IRA_REGION_ALL
1096 || flag_ira_region == IRA_REGION_MIXED)
1097 fprintf (f, ",%d", COSTS_OF_ALLOCNO (total_costs, i)->cost[k]);
1098 }
1099 }
1100 fprintf (f, " MEM:%i\n", COSTS_OF_ALLOCNO (allocno_costs, i)->mem_cost);
1101 }
1102 }
1103
1104 /* Traverse the BB represented by LOOP_TREE_NODE to update the allocno
1105 costs. */
1106 static void
1107 process_bb_node_for_costs (ira_loop_tree_node_t loop_tree_node)
1108 {
1109 basic_block bb;
1110 rtx insn;
1111
1112 bb = loop_tree_node->bb;
1113 if (bb == NULL)
1114 return;
1115 frequency = REG_FREQ_FROM_BB (bb);
1116 if (frequency == 0)
1117 frequency = 1;
1118 FOR_BB_INSNS (bb, insn)
1119 insn = scan_one_insn (insn);
1120 }
1121
1122 /* Find costs of register classes and memory for allocnos and their
1123 best costs. */
1124 static void
1125 find_allocno_class_costs (void)
1126 {
1127 int i, k;
1128 int pass;
1129 basic_block bb;
1130
1131 init_recog ();
1132 #ifdef FORBIDDEN_INC_DEC_CLASSES
1133 in_inc_dec = ira_allocate (sizeof (bool) * ira_allocnos_num);
1134 #endif /* FORBIDDEN_INC_DEC_CLASSES */
1135 allocno_pref = NULL;
1136 /* Normally we scan the insns once and determine the best class to
1137 use for each allocno. However, if -fexpensive-optimizations are
1138 on, we do so twice, the second time using the tentative best
1139 classes to guide the selection. */
1140 for (pass = 0; pass <= flag_expensive_optimizations; pass++)
1141 {
1142 if (internal_flag_ira_verbose > 0 && ira_dump_file)
1143 fprintf (ira_dump_file, "\nPass %i for finding allocno costs\n\n",
1144 pass);
1145 /* We could use only cover classes. Unfortunately it does not
1146 work well for some targets where some subclass of cover class
1147 is costly and wrong cover class is chosen. */
1148 for (i = 0; i < N_REG_CLASSES; i++)
1149 cost_class_nums[i] = -1;
1150 for (cost_classes_num = 0;
1151 cost_classes_num < ira_important_classes_num;
1152 cost_classes_num++)
1153 {
1154 cost_classes[cost_classes_num]
1155 = ira_important_classes[cost_classes_num];
1156 cost_class_nums[cost_classes[cost_classes_num]]
1157 = cost_classes_num;
1158 }
1159 struct_costs_size
1160 = sizeof (struct costs) + sizeof (int) * (cost_classes_num - 1);
1161 /* Zero out our accumulation of the cost of each class for each
1162 allocno. */
1163 memset (allocno_costs, 0, ira_allocnos_num * struct_costs_size);
1164 #ifdef FORBIDDEN_INC_DEC_CLASSES
1165 memset (in_inc_dec, 0, ira_allocnos_num * sizeof (bool));
1166 #endif
1167
1168 /* Scan the instructions and record each time it would save code
1169 to put a certain allocno in a certain class. */
1170 ira_traverse_loop_tree (true, ira_loop_tree_root,
1171 process_bb_node_for_costs, NULL);
1172
1173 memcpy (total_costs, allocno_costs,
1174 max_struct_costs_size * ira_allocnos_num);
1175 if (pass == 0)
1176 allocno_pref = allocno_pref_buffer;
1177
1178 /* Now for each allocno look at how desirable each class is and
1179 find which class is preferred. */
1180 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1181 {
1182 ira_allocno_t a, parent_a;
1183 int rclass, a_num, parent_a_num;
1184 ira_loop_tree_node_t parent;
1185 int best_cost, allocno_cost;
1186 enum reg_class best, alt_class;
1187 #ifdef FORBIDDEN_INC_DEC_CLASSES
1188 int inc_dec_p = false;
1189 #endif
1190
1191 if (ira_regno_allocno_map[i] == NULL)
1192 continue;
1193 memset (temp_costs, 0, struct_costs_size);
1194 /* Find cost of all allocnos with the same regno. */
1195 for (a = ira_regno_allocno_map[i];
1196 a != NULL;
1197 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1198 {
1199 a_num = ALLOCNO_NUM (a);
1200 if ((flag_ira_region == IRA_REGION_ALL
1201 || flag_ira_region == IRA_REGION_MIXED)
1202 && (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1203 && (parent_a = parent->regno_allocno_map[i]) != NULL
1204 /* There are no caps yet. */
1205 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
1206 ALLOCNO_NUM (a)))
1207 {
1208 /* Propagate costs to upper levels in the region
1209 tree. */
1210 parent_a_num = ALLOCNO_NUM (parent_a);
1211 for (k = 0; k < cost_classes_num; k++)
1212 COSTS_OF_ALLOCNO (total_costs, parent_a_num)->cost[k]
1213 += COSTS_OF_ALLOCNO (total_costs, a_num)->cost[k];
1214 COSTS_OF_ALLOCNO (total_costs, parent_a_num)->mem_cost
1215 += COSTS_OF_ALLOCNO (total_costs, a_num)->mem_cost;
1216 }
1217 for (k = 0; k < cost_classes_num; k++)
1218 temp_costs->cost[k]
1219 += COSTS_OF_ALLOCNO (allocno_costs, a_num)->cost[k];
1220 temp_costs->mem_cost
1221 += COSTS_OF_ALLOCNO (allocno_costs, a_num)->mem_cost;
1222 #ifdef FORBIDDEN_INC_DEC_CLASSES
1223 if (in_inc_dec[a_num])
1224 inc_dec_p = true;
1225 #endif
1226 }
1227 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1228 best = ALL_REGS;
1229 alt_class = NO_REGS;
1230 /* Find best common class for all allocnos with the same
1231 regno. */
1232 for (k = 0; k < cost_classes_num; k++)
1233 {
1234 rclass = cost_classes[k];
1235 /* Ignore classes that are too small for this operand or
1236 invalid for an operand that was auto-incremented. */
1237 if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)]
1238 #ifdef FORBIDDEN_INC_DEC_CLASSES
1239 || (inc_dec_p && forbidden_inc_dec_class[rclass])
1240 #endif
1241 #ifdef CANNOT_CHANGE_MODE_CLASS
1242 || invalid_mode_change_p (i, (enum reg_class) rclass,
1243 PSEUDO_REGNO_MODE (i))
1244 #endif
1245 )
1246 continue;
1247 if (temp_costs->cost[k] < best_cost)
1248 {
1249 best_cost = temp_costs->cost[k];
1250 best = (enum reg_class) rclass;
1251 }
1252 else if (temp_costs->cost[k] == best_cost)
1253 best = ira_reg_class_union[best][rclass];
1254 if (pass == flag_expensive_optimizations
1255 && temp_costs->cost[k] < temp_costs->mem_cost
1256 && (reg_class_size[reg_class_subunion[alt_class][rclass]]
1257 > reg_class_size[alt_class]))
1258 alt_class = reg_class_subunion[alt_class][rclass];
1259 }
1260 alt_class = ira_class_translate[alt_class];
1261 if (pass == flag_expensive_optimizations)
1262 {
1263 if (best_cost > temp_costs->mem_cost)
1264 best = alt_class = NO_REGS;
1265 else if (best == alt_class)
1266 alt_class = NO_REGS;
1267 setup_reg_classes (i, best, alt_class);
1268 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1269 fprintf (ira_dump_file,
1270 " r%d: preferred %s, alternative %s\n",
1271 i, reg_class_names[best], reg_class_names[alt_class]);
1272 }
1273 if (best_cost > temp_costs->mem_cost)
1274 common_classes[i] = NO_REGS;
1275 else if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
1276 /* Make the common class the biggest class of best and
1277 alt_class. */
1278 common_classes[i] = alt_class == NO_REGS ? best : alt_class;
1279 else
1280 /* Make the common class a cover class. Remember all
1281 allocnos with the same regno should have the same cover
1282 class. */
1283 common_classes[i] = ira_class_translate[best];
1284 for (a = ira_regno_allocno_map[i];
1285 a != NULL;
1286 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1287 {
1288 a_num = ALLOCNO_NUM (a);
1289 if (common_classes[i] == NO_REGS)
1290 best = NO_REGS;
1291 else
1292 {
1293 /* Finding best class which is subset of the common
1294 class. */
1295 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
1296 allocno_cost = best_cost;
1297 best = ALL_REGS;
1298 for (k = 0; k < cost_classes_num; k++)
1299 {
1300 rclass = cost_classes[k];
1301 if (! ira_class_subset_p[rclass][common_classes[i]])
1302 continue;
1303 /* Ignore classes that are too small for this
1304 operand or invalid for an operand that was
1305 auto-incremented. */
1306 if (! contains_reg_of_mode[rclass][PSEUDO_REGNO_MODE (i)]
1307 #ifdef FORBIDDEN_INC_DEC_CLASSES
1308 || (inc_dec_p && forbidden_inc_dec_class[rclass])
1309 #endif
1310 #ifdef CANNOT_CHANGE_MODE_CLASS
1311 || invalid_mode_change_p (i, (enum reg_class) rclass,
1312 PSEUDO_REGNO_MODE (i))
1313 #endif
1314 )
1315 ;
1316 else if (COSTS_OF_ALLOCNO (total_costs, a_num)->cost[k]
1317 < best_cost)
1318 {
1319 best_cost
1320 = COSTS_OF_ALLOCNO (total_costs, a_num)->cost[k];
1321 allocno_cost
1322 = COSTS_OF_ALLOCNO (allocno_costs, a_num)->cost[k];
1323 best = (enum reg_class) rclass;
1324 }
1325 else if (COSTS_OF_ALLOCNO (total_costs, a_num)->cost[k]
1326 == best_cost)
1327 {
1328 best = ira_reg_class_union[best][rclass];
1329 allocno_cost
1330 = MAX (allocno_cost,
1331 COSTS_OF_ALLOCNO (allocno_costs,
1332 a_num)->cost[k]);
1333 }
1334 }
1335 ALLOCNO_COVER_CLASS_COST (a) = allocno_cost;
1336 }
1337 ira_assert (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY
1338 || ira_class_translate[best] == common_classes[i]);
1339 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL
1340 && (pass == 0 || allocno_pref[a_num] != best))
1341 {
1342 fprintf (ira_dump_file, " a%d (r%d,", a_num, i);
1343 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
1344 fprintf (ira_dump_file, "b%d", bb->index);
1345 else
1346 fprintf (ira_dump_file, "l%d",
1347 ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
1348 fprintf (ira_dump_file, ") best %s, cover %s\n",
1349 reg_class_names[best],
1350 reg_class_names[common_classes[i]]);
1351 }
1352 allocno_pref[a_num] = best;
1353 }
1354 }
1355
1356 if (internal_flag_ira_verbose > 4 && ira_dump_file)
1357 {
1358 print_costs (ira_dump_file);
1359 fprintf (ira_dump_file,"\n");
1360 }
1361 }
1362 #ifdef FORBIDDEN_INC_DEC_CLASSES
1363 ira_free (in_inc_dec);
1364 #endif
1365 }
1366
1367
1368
1369 /* Process moves involving hard regs to modify allocno hard register
1370 costs. We can do this only after determining allocno cover class.
1371 If a hard register forms a register class, than moves with the hard
1372 register are already taken into account in class costs for the
1373 allocno. */
1374 static void
1375 process_bb_node_for_hard_reg_moves (ira_loop_tree_node_t loop_tree_node)
1376 {
1377 int i, freq, cost, src_regno, dst_regno, hard_regno;
1378 bool to_p;
1379 ira_allocno_t a;
1380 enum reg_class rclass, hard_reg_class;
1381 enum machine_mode mode;
1382 basic_block bb;
1383 rtx insn, set, src, dst;
1384
1385 bb = loop_tree_node->bb;
1386 if (bb == NULL)
1387 return;
1388 freq = REG_FREQ_FROM_BB (bb);
1389 if (freq == 0)
1390 freq = 1;
1391 FOR_BB_INSNS (bb, insn)
1392 {
1393 if (! INSN_P (insn))
1394 continue;
1395 set = single_set (insn);
1396 if (set == NULL_RTX)
1397 continue;
1398 dst = SET_DEST (set);
1399 src = SET_SRC (set);
1400 if (! REG_P (dst) || ! REG_P (src))
1401 continue;
1402 dst_regno = REGNO (dst);
1403 src_regno = REGNO (src);
1404 if (dst_regno >= FIRST_PSEUDO_REGISTER
1405 && src_regno < FIRST_PSEUDO_REGISTER)
1406 {
1407 hard_regno = src_regno;
1408 to_p = true;
1409 a = ira_curr_regno_allocno_map[dst_regno];
1410 }
1411 else if (src_regno >= FIRST_PSEUDO_REGISTER
1412 && dst_regno < FIRST_PSEUDO_REGISTER)
1413 {
1414 hard_regno = dst_regno;
1415 to_p = false;
1416 a = ira_curr_regno_allocno_map[src_regno];
1417 }
1418 else
1419 continue;
1420 rclass = ALLOCNO_COVER_CLASS (a);
1421 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass], hard_regno))
1422 continue;
1423 i = ira_class_hard_reg_index[rclass][hard_regno];
1424 if (i < 0)
1425 continue;
1426 mode = ALLOCNO_MODE (a);
1427 hard_reg_class = REGNO_REG_CLASS (hard_regno);
1428 cost = (to_p ? ira_register_move_cost[mode][hard_reg_class][rclass]
1429 : ira_register_move_cost[mode][rclass][hard_reg_class]) * freq;
1430 ira_allocate_and_set_costs (&ALLOCNO_HARD_REG_COSTS (a), rclass,
1431 ALLOCNO_COVER_CLASS_COST (a));
1432 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
1433 rclass, 0);
1434 ALLOCNO_HARD_REG_COSTS (a)[i] -= cost;
1435 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[i] -= cost;
1436 ALLOCNO_COVER_CLASS_COST (a) = MIN (ALLOCNO_COVER_CLASS_COST (a),
1437 ALLOCNO_HARD_REG_COSTS (a)[i]);
1438 }
1439 }
1440
1441 /* After we find hard register and memory costs for allocnos, define
1442 its cover class and modify hard register cost because insns moving
1443 allocno to/from hard registers. */
1444 static void
1445 setup_allocno_cover_class_and_costs (void)
1446 {
1447 int i, j, n, regno, num;
1448 int *reg_costs;
1449 enum reg_class cover_class, rclass;
1450 enum machine_mode mode;
1451 HARD_REG_SET *pref;
1452 ira_allocno_t a;
1453 ira_allocno_iterator ai;
1454
1455 FOR_EACH_ALLOCNO (a, ai)
1456 {
1457 i = ALLOCNO_NUM (a);
1458 mode = ALLOCNO_MODE (a);
1459 cover_class = common_classes[ALLOCNO_REGNO (a)];
1460 ira_assert (allocno_pref[i] == NO_REGS || cover_class != NO_REGS);
1461 ALLOCNO_MEMORY_COST (a) = COSTS_OF_ALLOCNO (allocno_costs, i)->mem_cost;
1462 ira_set_allocno_cover_class (a, cover_class);
1463 if (cover_class == NO_REGS)
1464 continue;
1465 ALLOCNO_AVAILABLE_REGS_NUM (a) = ira_available_class_regs[cover_class];
1466 pref = &reg_class_contents[allocno_pref[i]];
1467 if (optimize && ALLOCNO_COVER_CLASS (a) != allocno_pref[i])
1468 {
1469 n = ira_class_hard_regs_num[cover_class];
1470 ALLOCNO_HARD_REG_COSTS (a)
1471 = reg_costs = ira_allocate_cost_vector (cover_class);
1472 for (j = n - 1; j >= 0; j--)
1473 {
1474 regno = ira_class_hard_regs[cover_class][j];
1475 if (TEST_HARD_REG_BIT (*pref, regno))
1476 reg_costs[j] = ALLOCNO_COVER_CLASS_COST (a);
1477 else
1478 {
1479 rclass = REGNO_REG_CLASS (regno);
1480 num = cost_class_nums[rclass];
1481 if (num < 0)
1482 {
1483 /* The hard register class is not a cover class or a
1484 class not fully inside in a cover class -- use
1485 the allocno cover class. */
1486 ira_assert (ira_hard_regno_cover_class[regno]
1487 == cover_class);
1488 num = cost_class_nums[cover_class];
1489 }
1490 reg_costs[j] = COSTS_OF_ALLOCNO (allocno_costs, i)->cost[num];
1491 }
1492 }
1493 }
1494 }
1495 if (optimize)
1496 ira_traverse_loop_tree (true, ira_loop_tree_root,
1497 process_bb_node_for_hard_reg_moves, NULL);
1498 }
1499
1500
1501
1502 /* Function called once during compiler work. */
1503 void
1504 ira_init_costs_once (void)
1505 {
1506 int i;
1507
1508 init_cost = NULL;
1509 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
1510 {
1511 op_costs[i] = NULL;
1512 this_op_costs[i] = NULL;
1513 }
1514 temp_costs = NULL;
1515 cost_classes = NULL;
1516 }
1517
1518 /* Free allocated temporary cost vectors. */
1519 static void
1520 free_ira_costs (void)
1521 {
1522 int i;
1523
1524 if (init_cost != NULL)
1525 free (init_cost);
1526 init_cost = NULL;
1527 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
1528 {
1529 if (op_costs[i] != NULL)
1530 free (op_costs[i]);
1531 if (this_op_costs[i] != NULL)
1532 free (this_op_costs[i]);
1533 op_costs[i] = this_op_costs[i] = NULL;
1534 }
1535 if (temp_costs != NULL)
1536 free (temp_costs);
1537 temp_costs = NULL;
1538 if (cost_classes != NULL)
1539 free (cost_classes);
1540 cost_classes = NULL;
1541 }
1542
1543 /* This is called each time register related information is
1544 changed. */
1545 void
1546 ira_init_costs (void)
1547 {
1548 int i;
1549
1550 free_ira_costs ();
1551 max_struct_costs_size
1552 = sizeof (struct costs) + sizeof (int) * (ira_important_classes_num - 1);
1553 /* Don't use ira_allocate because vectors live through several IRA calls. */
1554 init_cost = (struct costs *) xmalloc (max_struct_costs_size);
1555 init_cost->mem_cost = 1000000;
1556 for (i = 0; i < ira_important_classes_num; i++)
1557 init_cost->cost[i] = 1000000;
1558 for (i = 0; i < MAX_RECOG_OPERANDS; i++)
1559 {
1560 op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
1561 this_op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size);
1562 }
1563 temp_costs = (struct costs *) xmalloc (max_struct_costs_size);
1564 cost_classes = (enum reg_class *) xmalloc (sizeof (enum reg_class)
1565 * ira_important_classes_num);
1566 }
1567
1568 /* Function called once at the end of compiler work. */
1569 void
1570 ira_finish_costs_once (void)
1571 {
1572 free_ira_costs ();
1573 }
1574
1575
1576
1577 /* Entry function which defines cover class, memory and hard register
1578 costs for each allocno. */
1579 void
1580 ira_costs (void)
1581 {
1582 ira_allocno_t a;
1583 ira_allocno_iterator ai;
1584
1585 allocno_costs = (struct costs *) ira_allocate (max_struct_costs_size
1586 * ira_allocnos_num);
1587 total_costs = (struct costs *) ira_allocate (max_struct_costs_size
1588 * ira_allocnos_num);
1589 allocno_pref_buffer
1590 = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
1591 * ira_allocnos_num);
1592 common_classes
1593 = (enum reg_class *) ira_allocate (sizeof (enum reg_class)
1594 * max_reg_num ());
1595 find_allocno_class_costs ();
1596 setup_allocno_cover_class_and_costs ();
1597 /* Because we could process operands only as subregs, check mode of
1598 the registers themselves too. */
1599 FOR_EACH_ALLOCNO (a, ai)
1600 if (ira_register_move_cost[ALLOCNO_MODE (a)] == NULL
1601 && have_regs_of_mode[ALLOCNO_MODE (a)])
1602 ira_init_register_move_cost (ALLOCNO_MODE (a));
1603 ira_free (common_classes);
1604 ira_free (allocno_pref_buffer);
1605 ira_free (total_costs);
1606 ira_free (allocno_costs);
1607 }
1608
1609
1610
1611 /* Change hard register costs for allocnos which lives through
1612 function calls. This is called only when we found all intersected
1613 calls during building allocno live ranges. */
1614 void
1615 ira_tune_allocno_costs_and_cover_classes (void)
1616 {
1617 int j, n, regno;
1618 int cost, min_cost, *reg_costs;
1619 enum reg_class cover_class, rclass;
1620 enum machine_mode mode;
1621 ira_allocno_t a;
1622 ira_allocno_iterator ai;
1623
1624 FOR_EACH_ALLOCNO (a, ai)
1625 {
1626 cover_class = ALLOCNO_COVER_CLASS (a);
1627 if (cover_class == NO_REGS)
1628 continue;
1629 mode = ALLOCNO_MODE (a);
1630 n = ira_class_hard_regs_num[cover_class];
1631 min_cost = INT_MAX;
1632 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
1633 {
1634 ira_allocate_and_set_costs
1635 (&ALLOCNO_HARD_REG_COSTS (a), cover_class,
1636 ALLOCNO_COVER_CLASS_COST (a));
1637 reg_costs = ALLOCNO_HARD_REG_COSTS (a);
1638 for (j = n - 1; j >= 0; j--)
1639 {
1640 regno = ira_class_hard_regs[cover_class][j];
1641 rclass = REGNO_REG_CLASS (regno);
1642 cost = 0;
1643 if (! ira_hard_reg_not_in_set_p (regno, mode, call_used_reg_set)
1644 || HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1645 cost += (ALLOCNO_CALL_FREQ (a)
1646 * (ira_memory_move_cost[mode][rclass][0]
1647 + ira_memory_move_cost[mode][rclass][1]));
1648 #ifdef IRA_HARD_REGNO_ADD_COST_MULTIPLIER
1649 cost += ((ira_memory_move_cost[mode][rclass][0]
1650 + ira_memory_move_cost[mode][rclass][1])
1651 * ALLOCNO_FREQ (a)
1652 * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno) / 2);
1653 #endif
1654 reg_costs[j] += cost;
1655 if (min_cost > reg_costs[j])
1656 min_cost = reg_costs[j];
1657 }
1658 }
1659 if (min_cost != INT_MAX)
1660 ALLOCNO_COVER_CLASS_COST (a) = min_cost;
1661 }
1662 }