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>. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 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" 66 67/* The flags is set up every time when we calculate pseudo register 68 classes through function ira_set_pseudo_classes. */ 69static bool pseudo_classes_defined_p = false; 70 71/* TRUE if we work with allocnos. Otherwise we work with pseudos. */ 72static bool allocno_p; 73 74/* Number of elements in array `costs'. */ 75static int cost_elements_num; 76 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. */ 80struct costs 81{ 82 int mem_cost; 83 /* Costs for register classes start here. We process only some 84 allocno classes. */ 85 int cost[1]; 86}; 87 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) 98 99/* Costs of each class for each allocno or pseudo. */ 100static struct costs *costs; 101 102/* Accumulated costs of each class for each allocno. */ 103static struct costs *total_allocno_costs; 104 105/* It is the current size of struct costs. */ 106static int struct_costs_size; 107 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)) 112 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) 117 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. */ 121static enum reg_class *pref; 122 123/* Allocated buffers for pref. */ 124static enum reg_class *pref_buffer; 125 126/* Record allocno class of each allocno with the same regno. */ 127static enum reg_class *regno_aclass; 128 129/* Record cost gains for not allocating a register with an invariant 130 equivalence. */ 131static int *regno_equiv_gains; 132 133/* Execution frequency of the current insn. */ 134static int frequency; 135 136 137 138/* Info about reg classes whose costs are calculated for a pseudo. */ 139struct cost_classes 140{ 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]; 151}; 152 153/* Types of pointers to the structure above. */ 154typedef struct cost_classes *cost_classes_t; 155typedef const struct cost_classes *const_cost_classes_t; 156 157/* Info about cost classes for each pseudo. */ 158static cost_classes_t *regno_cost_classes; 159 160/* Helper for cost_classes hashing. */ 161 162struct cost_classes_hasher 163{ 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 *); 169}; 170 171/* Returns hash value for cost classes info HV. */ 172inline hashval_t 173cost_classes_hasher::hash (const value_type *hv) 174{ 175 return iterative_hash (&hv->classes, sizeof (enum reg_class) * hv->num, 0); 176} 177 178/* Compares cost classes info HV1 and HV2. */ 179inline bool 180cost_classes_hasher::equal (const value_type *hv1, const compare_type *hv2) 181{ 182 return (hv1->num == hv2->num 183 && memcmp (hv1->classes, hv2->classes, 184 sizeof (enum reg_class) * hv1->num) == 0); 185} 186 187/* Delete cost classes info V from the hash table. */ 188inline void 189cost_classes_hasher::remove (value_type *v) 190{ 191 ira_free (v); 192} 193 194/* Hash table of unique cost classes. */ 195static hash_table<cost_classes_hasher> *cost_classes_htab; 196 197/* Map allocno class -> cost classes for pseudo of given allocno 198 class. */ 199static cost_classes_t cost_classes_aclass_cache[N_REG_CLASSES]; 200 201/* Map mode -> cost classes for pseudo of give mode. */ 202static cost_classes_t cost_classes_mode_cache[MAX_MACHINE_MODE]; 203 204/* Cost classes that include all classes in ira_important_classes. */ 205static cost_classes all_cost_classes; 206 207/* Use the array of classes in CLASSES_PTR to fill out the rest of 208 the structure. */ 209static void 210complete_cost_classes (cost_classes_t classes_ptr) 211{ 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++) 217 { 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--) 221 { 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; 225 } 226 } 227} 228 229/* Initialize info about the cost classes for each pseudo. */ 230static void 231initiate_regno_cost_classes (void) 232{ 233 int size = sizeof (cost_classes_t) * max_reg_num (); 234 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); 246} 247 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. */ 253static cost_classes_t 254setup_cost_classes (cost_classes_t from) 255{ 256 cost_classes_t classes_ptr; 257 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; 264} 265 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. */ 269static cost_classes_t 270restrict_cost_classes (cost_classes_t full, machine_mode mode, 271 const HARD_REG_SET ®s) 272{ 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++) 277 { 278 /* Assume that we'll drop the class. */ 279 map[i] = -1; 280 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; 285 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; 296 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. 302 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. 311 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) 322 { 323 enum reg_class cl2 = narrow.classes[pos]; 324 if (hard_reg_set_subset_p (valid_for_cl, reg_class_contents[cl2])) 325 break; 326 } 327 map[i] = pos; 328 if (pos == narrow.num) 329 { 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; 336 } 337 } 338 if (narrow.num == full->num) 339 return full; 340 341 cost_classes **slot = cost_classes_htab->find_slot (&narrow, INSERT); 342 if (*slot == NULL) 343 { 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++) 347 { 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]; 352 } 353 *slot = classes; 354 } 355 return *slot; 356} 357 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. */ 364static void 365setup_regno_cost_classes_by_aclass (int regno, enum reg_class aclass) 366{ 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; 374 375 if ((classes_ptr = cost_classes_aclass_cache[aclass]) == NULL) 376 { 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++) 384 { 385 cl = ira_important_classes[i]; 386 if (exclude_p) 387 { 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; 394 } 395 classes.classes[classes.num++] = cl; 396 } 397 slot = cost_classes_htab->find_slot (&classes, INSERT); 398 if (*slot == NULL) 399 { 400 classes_ptr = setup_cost_classes (&classes); 401 *slot = classes_ptr; 402 } 403 classes_ptr = cost_classes_aclass_cache[aclass] = (cost_classes_t) *slot; 404 } 405 if (regno_reg_rtx[regno] != NULL_RTX) 406 { 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 = ®_class_contents[ALL_REGS]; 414 classes_ptr = restrict_cost_classes (classes_ptr, 415 PSEUDO_REGNO_MODE (regno), 416 *valid_regs); 417 } 418 regno_cost_classes[regno] = classes_ptr; 419} 420 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. */ 427static void 428setup_regno_cost_classes_by_mode (int regno, machine_mode mode) 429{ 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 434 { 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]; 440 } 441} 442 443/* Finalize info about the cost classes for each pseudo. */ 444static void 445finish_regno_cost_classes (void) 446{ 447 ira_free (regno_cost_classes); 448 delete cost_classes_htab; 449 cost_classes_htab = NULL; 450} 451 452 453 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. */ 457static int 458copy_cost (rtx x, machine_mode mode, reg_class_t rclass, bool to_p, 459 secondary_reload_info *prev_sri) 460{ 461 secondary_reload_info sri; 462 reg_class_t secondary_class = NO_REGS; 463 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; 468 469 /* Get the class we will actually use for a reload. */ 470 rclass = targetm.preferred_reload_class (x, rclass); 471 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); 478 479 if (secondary_class != NO_REGS) 480 { 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)); 485 } 486 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)) 494 { 495 reg_class_t x_class = REGNO_REG_CLASS (REGNO (x)); 496 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]); 500 } 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); 505} 506 507 508 509/* Record the cost of using memory or hard registers of various 510 classes for the operands in INSN. 511 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. 518 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. 526 527 The cost of each class for this insn is its lowest cost among all 528 the alternatives. */ 529static void 530record_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) 533{ 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]; 539 540 for (i = 0; i < n_ops; i++) 541 insn_allows_mem[i] = 0; 542 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++) 547 { 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; 553 554 if (!TEST_BIT (preferred, alt)) 555 { 556 for (i = 0; i < recog_data.n_operands; i++) 557 constraints[i] = skip_alternative (constraints[i]); 558 559 continue; 560 } 561 562 for (i = 0; i < n_ops; i++) 563 { 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; 570 571 /* Initially show we know nothing about the register class. */ 572 classes[i] = NO_REGS; 573 allows_mem[i] = 0; 574 575 /* If this operand has no constraints at all, we can 576 conclude nothing about it since anything is valid. */ 577 if (*p == 0) 578 { 579 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER) 580 memset (this_op_costs[i], 0, struct_costs_size); 581 continue; 582 } 583 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++; 591 592 if (p[0] >= '0' && p[0] <= '0' + i) 593 { 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; 602 603 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER) 604 { 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) 614 { 615 alt_cost += copy_cost (op, mode, classes[j], 1, NULL); 616 win = 1; 617 } 618 } 619 else if (! REG_P (ops[j]) 620 || REGNO (ops[j]) < FIRST_PSEUDO_REGISTER) 621 { 622 /* This op is an allocno but the one it matches is 623 not. */ 624 625 /* If we can't put the other operand into a 626 register, this alternative can't be used. */ 627 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); 635 } 636 else 637 { 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]; 650 651 ira_init_register_move_cost_if_necessary (mode); 652 if (! in_p) 653 { 654 ira_assert (out_p); 655 if (op_class == NO_REGS) 656 { 657 mem_cost = ira_memory_move_cost[mode]; 658 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 659 { 660 rclass = cost_classes[k]; 661 pp_costs[k] = mem_cost[rclass][0] * frequency; 662 } 663 } 664 else 665 { 666 move_out_cost = ira_may_move_out_cost[mode]; 667 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 668 { 669 rclass = cost_classes[k]; 670 pp_costs[k] 671 = move_out_cost[op_class][rclass] * frequency; 672 } 673 } 674 } 675 else if (! out_p) 676 { 677 ira_assert (in_p); 678 if (op_class == NO_REGS) 679 { 680 mem_cost = ira_memory_move_cost[mode]; 681 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 682 { 683 rclass = cost_classes[k]; 684 pp_costs[k] = mem_cost[rclass][1] * frequency; 685 } 686 } 687 else 688 { 689 move_in_cost = ira_may_move_in_cost[mode]; 690 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 691 { 692 rclass = cost_classes[k]; 693 pp_costs[k] 694 = move_in_cost[rclass][op_class] * frequency; 695 } 696 } 697 } 698 else 699 { 700 if (op_class == NO_REGS) 701 { 702 mem_cost = ira_memory_move_cost[mode]; 703 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 704 { 705 rclass = cost_classes[k]; 706 pp_costs[k] = ((mem_cost[rclass][0] 707 + mem_cost[rclass][1]) 708 * frequency); 709 } 710 } 711 else 712 { 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--) 716 { 717 rclass = cost_classes[k]; 718 pp_costs[k] = ((move_in_cost[rclass][op_class] 719 + move_out_cost[op_class][rclass]) 720 * frequency); 721 } 722 } 723 } 724 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; 732 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) 738 { 739 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))]; 740 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]; 752 } 753 if (REGNO (ops[i]) != REGNO (ops[j]) 754 && ! find_reg_note (insn, REG_DEAD, op)) 755 alt_cost += 2; 756 757 p++; 758 } 759 } 760 761 /* Scan all the constraint letters. See if the operand 762 matches any of the constraints. Collect the valid 763 register classes and see if this operand accepts 764 memory. */ 765 while ((c = *p)) 766 { 767 switch (c) 768 { 769 case '*': 770 /* Ignore the next letter for this pass. */ 771 c = *++p; 772 break; 773 774 case '^': 775 alt_cost += 2; 776 break; 777 778 case '?': 779 alt_cost += 2; 780 break; 781 782 case 'g': 783 if (MEM_P (op) 784 || (CONSTANT_P (op) 785 && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op)))) 786 win = 1; 787 insn_allows_mem[i] = allows_mem[i] = 1; 788 classes[i] = ira_reg_class_subunion[classes[i]][GENERAL_REGS]; 789 break; 790 791 default: 792 enum constraint_num cn = lookup_constraint (p); 793 enum reg_class cl; 794 switch (get_constraint_type (cn)) 795 { 796 case CT_REGISTER: 797 cl = reg_class_for_constraint (cn); 798 if (cl != NO_REGS) 799 classes[i] = ira_reg_class_subunion[classes[i]][cl]; 800 break; 801 802 case CT_CONST_INT: 803 if (CONST_INT_P (op) 804 && insn_const_int_ok_for_constraint (INTVAL (op), cn)) 805 win = 1; 806 break; 807 808 case CT_MEMORY: 809 /* Every MEM can be reloaded to fit. */ 810 insn_allows_mem[i] = allows_mem[i] = 1; 811 if (MEM_P (op)) 812 win = 1; 813 break; 814 815 case CT_ADDRESS: 816 /* Every address can be reloaded to fit. */ 817 allows_addr = 1; 818 if (address_operand (op, GET_MODE (op)) 819 || constraint_satisfied_p (op, cn)) 820 win = 1; 821 /* We know this operand is an address, so we 822 want it to be allocated to a hard register 823 that can be the base of an address, 824 i.e. BASE_REG_CLASS. */ 825 classes[i] 826 = ira_reg_class_subunion[classes[i]] 827 [base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, 828 ADDRESS, SCRATCH)]; 829 break; 830 831 case CT_FIXED_FORM: 832 if (constraint_satisfied_p (op, cn)) 833 win = 1; 834 break; 835 } 836 break; 837 } 838 p += CONSTRAINT_LEN (c, p); 839 if (c == ',') 840 break; 841 } 842 843 constraints[i] = p; 844 845 /* How we account for this operand now depends on whether it 846 is a pseudo register or not. If it is, we first check if 847 any register classes are valid. If not, we ignore this 848 alternative, since we want to assume that all allocnos get 849 allocated for register preferencing. If some register 850 class is valid, compute the costs of moving the allocno 851 into that class. */ 852 if (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER) 853 { 854 if (classes[i] == NO_REGS && ! allows_mem[i]) 855 { 856 /* We must always fail if the operand is a REG, but 857 we did not find a suitable class and memory is 858 not allowed. 859 860 Otherwise we may perform an uninitialized read 861 from this_op_costs after the `continue' statement 862 below. */ 863 alt_fail = 1; 864 } 865 else 866 { 867 unsigned int regno = REGNO (op); 868 struct costs *pp = this_op_costs[i]; 869 int *pp_costs = pp->cost; 870 cost_classes_t cost_classes_ptr = regno_cost_classes[regno]; 871 enum reg_class *cost_classes = cost_classes_ptr->classes; 872 bool in_p = recog_data.operand_type[i] != OP_OUT; 873 bool out_p = recog_data.operand_type[i] != OP_IN; 874 enum reg_class op_class = classes[i]; 875 876 ira_init_register_move_cost_if_necessary (mode); 877 if (! in_p) 878 { 879 ira_assert (out_p); 880 if (op_class == NO_REGS) 881 { 882 mem_cost = ira_memory_move_cost[mode]; 883 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 884 { 885 rclass = cost_classes[k]; 886 pp_costs[k] = mem_cost[rclass][0] * frequency; 887 } 888 } 889 else 890 { 891 move_out_cost = ira_may_move_out_cost[mode]; 892 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 893 { 894 rclass = cost_classes[k]; 895 pp_costs[k] 896 = move_out_cost[op_class][rclass] * frequency; 897 } 898 } 899 } 900 else if (! out_p) 901 { 902 ira_assert (in_p); 903 if (op_class == NO_REGS) 904 { 905 mem_cost = ira_memory_move_cost[mode]; 906 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 907 { 908 rclass = cost_classes[k]; 909 pp_costs[k] = mem_cost[rclass][1] * frequency; 910 } 911 } 912 else 913 { 914 move_in_cost = ira_may_move_in_cost[mode]; 915 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 916 { 917 rclass = cost_classes[k]; 918 pp_costs[k] 919 = move_in_cost[rclass][op_class] * frequency; 920 } 921 } 922 } 923 else 924 { 925 if (op_class == NO_REGS) 926 { 927 mem_cost = ira_memory_move_cost[mode]; 928 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 929 { 930 rclass = cost_classes[k]; 931 pp_costs[k] = ((mem_cost[rclass][0] 932 + mem_cost[rclass][1]) 933 * frequency); 934 } 935 } 936 else 937 { 938 move_in_cost = ira_may_move_in_cost[mode]; 939 move_out_cost = ira_may_move_out_cost[mode]; 940 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 941 { 942 rclass = cost_classes[k]; 943 pp_costs[k] = ((move_in_cost[rclass][op_class] 944 + move_out_cost[op_class][rclass]) 945 * frequency); 946 } 947 } 948 } 949 950 if (op_class == NO_REGS) 951 /* Although we don't need insn to reload from 952 memory, still accessing memory is usually more 953 expensive than a register. */ 954 pp->mem_cost = frequency; 955 else 956 /* If the alternative actually allows memory, make 957 things a bit cheaper since we won't need an 958 extra insn to load it. */ 959 pp->mem_cost 960 = ((out_p ? ira_memory_move_cost[mode][op_class][0] : 0) 961 + (in_p ? ira_memory_move_cost[mode][op_class][1] : 0) 962 - allows_mem[i]) * frequency; 963 /* If we have assigned a class to this allocno in 964 our first pass, add a cost to this alternative 965 corresponding to what we would add if this 966 allocno were not in the appropriate class. */ 967 if (pref) 968 { 969 enum reg_class pref_class = pref[COST_INDEX (REGNO (op))]; 970 971 if (pref_class == NO_REGS) 972 { 973 if (op_class != NO_REGS) 974 alt_cost 975 += ((out_p 976 ? ira_memory_move_cost[mode][op_class][0] 977 : 0) 978 + (in_p 979 ? ira_memory_move_cost[mode][op_class][1] 980 : 0)); 981 } 982 else if (op_class == NO_REGS) 983 alt_cost 984 += ((out_p 985 ? ira_memory_move_cost[mode][pref_class][1] 986 : 0) 987 + (in_p 988 ? ira_memory_move_cost[mode][pref_class][0] 989 : 0)); 990 else if (ira_reg_class_intersect[pref_class][op_class] 991 == NO_REGS) 992 alt_cost += (ira_register_move_cost 993 [mode][pref_class][op_class]); 994 } 995 } 996 } 997 998 /* Otherwise, if this alternative wins, either because we 999 have already determined that or if we have a hard 1000 register of the proper class, there is no cost for this 1001 alternative. */ 1002 else if (win || (REG_P (op) 1003 && reg_fits_class_p (op, classes[i], 1004 0, GET_MODE (op)))) 1005 ; 1006 1007 /* If registers are valid, the cost of this alternative 1008 includes copying the object to and/or from a 1009 register. */ 1010 else if (classes[i] != NO_REGS) 1011 { 1012 if (recog_data.operand_type[i] != OP_OUT) 1013 alt_cost += copy_cost (op, mode, classes[i], 1, NULL); 1014 1015 if (recog_data.operand_type[i] != OP_IN) 1016 alt_cost += copy_cost (op, mode, classes[i], 0, NULL); 1017 } 1018 /* The only other way this alternative can be used is if 1019 this is a constant that could be placed into memory. */ 1020 else if (CONSTANT_P (op) && (allows_addr || allows_mem[i])) 1021 alt_cost += ira_memory_move_cost[mode][classes[i]][1]; 1022 else 1023 alt_fail = 1; 1024 } 1025 1026 if (alt_fail) 1027 continue; 1028 1029 op_cost_add = alt_cost * frequency; 1030 /* Finally, update the costs with the information we've 1031 calculated about this alternative. */ 1032 for (i = 0; i < n_ops; i++) 1033 if (REG_P (ops[i]) && REGNO (ops[i]) >= FIRST_PSEUDO_REGISTER) 1034 { 1035 struct costs *pp = op_costs[i], *qq = this_op_costs[i]; 1036 int *pp_costs = pp->cost, *qq_costs = qq->cost; 1037 int scale = 1 + (recog_data.operand_type[i] == OP_INOUT); 1038 cost_classes_t cost_classes_ptr 1039 = regno_cost_classes[REGNO (ops[i])]; 1040 1041 pp->mem_cost = MIN (pp->mem_cost, 1042 (qq->mem_cost + op_cost_add) * scale); 1043 1044 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 1045 pp_costs[k] 1046 = MIN (pp_costs[k], (qq_costs[k] + op_cost_add) * scale); 1047 } 1048 } 1049 1050 if (allocno_p) 1051 for (i = 0; i < n_ops; i++) 1052 { 1053 ira_allocno_t a; 1054 rtx op = ops[i]; 1055 1056 if (! REG_P (op) || REGNO (op) < FIRST_PSEUDO_REGISTER) 1057 continue; 1058 a = ira_curr_regno_allocno_map [REGNO (op)]; 1059 if (! ALLOCNO_BAD_SPILL_P (a) && insn_allows_mem[i] == 0) 1060 ALLOCNO_BAD_SPILL_P (a) = true; 1061 } 1062 1063} 1064 1065 1066 1067/* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudo registers. */ 1068static inline bool 1069ok_for_index_p_nonstrict (rtx reg) 1070{ 1071 unsigned regno = REGNO (reg); 1072 1073 return regno >= FIRST_PSEUDO_REGISTER || REGNO_OK_FOR_INDEX_P (regno); 1074} 1075 1076/* A version of regno_ok_for_base_p for use here, when all 1077 pseudo-registers should count as OK. Arguments as for 1078 regno_ok_for_base_p. */ 1079static inline bool 1080ok_for_base_p_nonstrict (rtx reg, machine_mode mode, addr_space_t as, 1081 enum rtx_code outer_code, enum rtx_code index_code) 1082{ 1083 unsigned regno = REGNO (reg); 1084 1085 if (regno >= FIRST_PSEUDO_REGISTER) 1086 return true; 1087 return ok_for_base_p_1 (regno, mode, as, outer_code, index_code); 1088} 1089 1090/* Record the pseudo registers we must reload into hard registers in a 1091 subexpression of a memory address, X. 1092 1093 If CONTEXT is 0, we are looking at the base part of an address, 1094 otherwise we are looking at the index part. 1095 1096 MODE and AS are the mode and address space of the memory reference; 1097 OUTER_CODE and INDEX_CODE give the context that the rtx appears in. 1098 These four arguments are passed down to base_reg_class. 1099 1100 SCALE is twice the amount to multiply the cost by (it is twice so 1101 we can represent half-cost adjustments). */ 1102static void 1103record_address_regs (machine_mode mode, addr_space_t as, rtx x, 1104 int context, enum rtx_code outer_code, 1105 enum rtx_code index_code, int scale) 1106{ 1107 enum rtx_code code = GET_CODE (x); 1108 enum reg_class rclass; 1109 1110 if (context == 1) 1111 rclass = INDEX_REG_CLASS; 1112 else 1113 rclass = base_reg_class (mode, as, outer_code, index_code); 1114 1115 switch (code) 1116 { 1117 case CONST_INT: 1118 case CONST: 1119 case CC0: 1120 case PC: 1121 case SYMBOL_REF: 1122 case LABEL_REF: 1123 return; 1124 1125 case PLUS: 1126 /* When we have an address that is a sum, we must determine 1127 whether registers are "base" or "index" regs. If there is a 1128 sum of two registers, we must choose one to be the "base". 1129 Luckily, we can use the REG_POINTER to make a good choice 1130 most of the time. We only need to do this on machines that 1131 can have two registers in an address and where the base and 1132 index register classes are different. 1133 1134 ??? This code used to set REGNO_POINTER_FLAG in some cases, 1135 but that seems bogus since it should only be set when we are 1136 sure the register is being used as a pointer. */ 1137 { 1138 rtx arg0 = XEXP (x, 0); 1139 rtx arg1 = XEXP (x, 1); 1140 enum rtx_code code0 = GET_CODE (arg0); 1141 enum rtx_code code1 = GET_CODE (arg1); 1142 1143 /* Look inside subregs. */ 1144 if (code0 == SUBREG) 1145 arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0); 1146 if (code1 == SUBREG) 1147 arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1); 1148 1149 /* If this machine only allows one register per address, it 1150 must be in the first operand. */ 1151 if (MAX_REGS_PER_ADDRESS == 1) 1152 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale); 1153 1154 /* If index and base registers are the same on this machine, 1155 just record registers in any non-constant operands. We 1156 assume here, as well as in the tests below, that all 1157 addresses are in canonical form. */ 1158 else if (INDEX_REG_CLASS 1159 == base_reg_class (VOIDmode, as, PLUS, SCRATCH)) 1160 { 1161 record_address_regs (mode, as, arg0, context, PLUS, code1, scale); 1162 if (! CONSTANT_P (arg1)) 1163 record_address_regs (mode, as, arg1, context, PLUS, code0, scale); 1164 } 1165 1166 /* If the second operand is a constant integer, it doesn't 1167 change what class the first operand must be. */ 1168 else if (CONST_SCALAR_INT_P (arg1)) 1169 record_address_regs (mode, as, arg0, context, PLUS, code1, scale); 1170 /* If the second operand is a symbolic constant, the first 1171 operand must be an index register. */ 1172 else if (code1 == SYMBOL_REF || code1 == CONST || code1 == LABEL_REF) 1173 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale); 1174 /* If both operands are registers but one is already a hard 1175 register of index or reg-base class, give the other the 1176 class that the hard register is not. */ 1177 else if (code0 == REG && code1 == REG 1178 && REGNO (arg0) < FIRST_PSEUDO_REGISTER 1179 && (ok_for_base_p_nonstrict (arg0, mode, as, PLUS, REG) 1180 || ok_for_index_p_nonstrict (arg0))) 1181 record_address_regs (mode, as, arg1, 1182 ok_for_base_p_nonstrict (arg0, mode, as, 1183 PLUS, REG) ? 1 : 0, 1184 PLUS, REG, scale); 1185 else if (code0 == REG && code1 == REG 1186 && REGNO (arg1) < FIRST_PSEUDO_REGISTER 1187 && (ok_for_base_p_nonstrict (arg1, mode, as, PLUS, REG) 1188 || ok_for_index_p_nonstrict (arg1))) 1189 record_address_regs (mode, as, arg0, 1190 ok_for_base_p_nonstrict (arg1, mode, as, 1191 PLUS, REG) ? 1 : 0, 1192 PLUS, REG, scale); 1193 /* If one operand is known to be a pointer, it must be the 1194 base with the other operand the index. Likewise if the 1195 other operand is a MULT. */ 1196 else if ((code0 == REG && REG_POINTER (arg0)) || code1 == MULT) 1197 { 1198 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale); 1199 record_address_regs (mode, as, arg1, 1, PLUS, code0, scale); 1200 } 1201 else if ((code1 == REG && REG_POINTER (arg1)) || code0 == MULT) 1202 { 1203 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale); 1204 record_address_regs (mode, as, arg1, 0, PLUS, code0, scale); 1205 } 1206 /* Otherwise, count equal chances that each might be a base or 1207 index register. This case should be rare. */ 1208 else 1209 { 1210 record_address_regs (mode, as, arg0, 0, PLUS, code1, scale / 2); 1211 record_address_regs (mode, as, arg0, 1, PLUS, code1, scale / 2); 1212 record_address_regs (mode, as, arg1, 0, PLUS, code0, scale / 2); 1213 record_address_regs (mode, as, arg1, 1, PLUS, code0, scale / 2); 1214 } 1215 } 1216 break; 1217 1218 /* Double the importance of an allocno that is incremented or 1219 decremented, since it would take two extra insns if it ends 1220 up in the wrong place. */ 1221 case POST_MODIFY: 1222 case PRE_MODIFY: 1223 record_address_regs (mode, as, XEXP (x, 0), 0, code, 1224 GET_CODE (XEXP (XEXP (x, 1), 1)), 2 * scale); 1225 if (REG_P (XEXP (XEXP (x, 1), 1))) 1226 record_address_regs (mode, as, XEXP (XEXP (x, 1), 1), 1, code, REG, 1227 2 * scale); 1228 break; 1229 1230 case POST_INC: 1231 case PRE_INC: 1232 case POST_DEC: 1233 case PRE_DEC: 1234 /* Double the importance of an allocno that is incremented or 1235 decremented, since it would take two extra insns if it ends 1236 up in the wrong place. */ 1237 record_address_regs (mode, as, XEXP (x, 0), 0, code, SCRATCH, 2 * scale); 1238 break; 1239 1240 case REG: 1241 { 1242 struct costs *pp; 1243 int *pp_costs; 1244 enum reg_class i; 1245 int k, regno, add_cost; 1246 cost_classes_t cost_classes_ptr; 1247 enum reg_class *cost_classes; 1248 move_table *move_in_cost; 1249 1250 if (REGNO (x) < FIRST_PSEUDO_REGISTER) 1251 break; 1252 1253 regno = REGNO (x); 1254 if (allocno_p) 1255 ALLOCNO_BAD_SPILL_P (ira_curr_regno_allocno_map[regno]) = true; 1256 pp = COSTS (costs, COST_INDEX (regno)); 1257 add_cost = (ira_memory_move_cost[Pmode][rclass][1] * scale) / 2; 1258 if (INT_MAX - add_cost < pp->mem_cost) 1259 pp->mem_cost = INT_MAX; 1260 else 1261 pp->mem_cost += add_cost; 1262 cost_classes_ptr = regno_cost_classes[regno]; 1263 cost_classes = cost_classes_ptr->classes; 1264 pp_costs = pp->cost; 1265 ira_init_register_move_cost_if_necessary (Pmode); 1266 move_in_cost = ira_may_move_in_cost[Pmode]; 1267 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 1268 { 1269 i = cost_classes[k]; 1270 add_cost = (move_in_cost[i][rclass] * scale) / 2; 1271 if (INT_MAX - add_cost < pp_costs[k]) 1272 pp_costs[k] = INT_MAX; 1273 else 1274 pp_costs[k] += add_cost; 1275 } 1276 } 1277 break; 1278 1279 default: 1280 { 1281 const char *fmt = GET_RTX_FORMAT (code); 1282 int i; 1283 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1284 if (fmt[i] == 'e') 1285 record_address_regs (mode, as, XEXP (x, i), context, code, SCRATCH, 1286 scale); 1287 } 1288 } 1289} 1290 1291 1292 1293/* Calculate the costs of insn operands. */ 1294static void 1295record_operand_costs (rtx_insn *insn, enum reg_class *pref) 1296{ 1297 const char *constraints[MAX_RECOG_OPERANDS]; 1298 machine_mode modes[MAX_RECOG_OPERANDS]; 1299 rtx ops[MAX_RECOG_OPERANDS]; 1300 rtx set; 1301 int i; 1302 1303 for (i = 0; i < recog_data.n_operands; i++) 1304 { 1305 constraints[i] = recog_data.constraints[i]; 1306 modes[i] = recog_data.operand_mode[i]; 1307 } 1308 1309 /* If we get here, we are set up to record the costs of all the 1310 operands for this insn. Start by initializing the costs. Then 1311 handle any address registers. Finally record the desired classes 1312 for any allocnos, doing it twice if some pair of operands are 1313 commutative. */ 1314 for (i = 0; i < recog_data.n_operands; i++) 1315 { 1316 memcpy (op_costs[i], init_cost, struct_costs_size); 1317 1318 ops[i] = recog_data.operand[i]; 1319 if (GET_CODE (recog_data.operand[i]) == SUBREG) 1320 recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]); 1321 1322 if (MEM_P (recog_data.operand[i])) 1323 record_address_regs (GET_MODE (recog_data.operand[i]), 1324 MEM_ADDR_SPACE (recog_data.operand[i]), 1325 XEXP (recog_data.operand[i], 0), 1326 0, MEM, SCRATCH, frequency * 2); 1327 else if (constraints[i][0] == 'p' 1328 || (insn_extra_address_constraint 1329 (lookup_constraint (constraints[i])))) 1330 record_address_regs (VOIDmode, ADDR_SPACE_GENERIC, 1331 recog_data.operand[i], 0, ADDRESS, SCRATCH, 1332 frequency * 2); 1333 } 1334 1335 /* Check for commutative in a separate loop so everything will have 1336 been initialized. We must do this even if one operand is a 1337 constant--see addsi3 in m68k.md. */ 1338 for (i = 0; i < (int) recog_data.n_operands - 1; i++) 1339 if (constraints[i][0] == '%') 1340 { 1341 const char *xconstraints[MAX_RECOG_OPERANDS]; 1342 int j; 1343 1344 /* Handle commutative operands by swapping the constraints. 1345 We assume the modes are the same. */ 1346 for (j = 0; j < recog_data.n_operands; j++) 1347 xconstraints[j] = constraints[j]; 1348 1349 xconstraints[i] = constraints[i+1]; 1350 xconstraints[i+1] = constraints[i]; 1351 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands, 1352 recog_data.operand, modes, 1353 xconstraints, insn, pref); 1354 } 1355 record_reg_classes (recog_data.n_alternatives, recog_data.n_operands, 1356 recog_data.operand, modes, 1357 constraints, insn, pref); 1358 1359 /* If this insn is a single set copying operand 1 to operand 0 and 1360 one operand is an allocno with the other a hard reg or an allocno 1361 that prefers a hard register that is in its own register class 1362 then we may want to adjust the cost of that register class to -1. 1363 1364 Avoid the adjustment if the source does not die to avoid 1365 stressing of register allocator by preferencing two colliding 1366 registers into single class. 1367 1368 Also avoid the adjustment if a copy between hard registers of the 1369 class is expensive (ten times the cost of a default copy is 1370 considered arbitrarily expensive). This avoids losing when the 1371 preferred class is very expensive as the source of a copy 1372 instruction. */ 1373 if ((set = single_set (insn)) != NULL_RTX 1374 /* In rare cases the single set insn might have less 2 operands 1375 as the source can be a fixed special reg. */ 1376 && recog_data.n_operands > 1 1377 && ops[0] == SET_DEST (set) && ops[1] == SET_SRC (set)) 1378 { 1379 int regno, other_regno; 1380 rtx dest = SET_DEST (set); 1381 rtx src = SET_SRC (set); 1382 1383 dest = SET_DEST (set); 1384 src = SET_SRC (set); 1385 if (GET_CODE (dest) == SUBREG 1386 && (GET_MODE_SIZE (GET_MODE (dest)) 1387 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))) 1388 dest = SUBREG_REG (dest); 1389 if (GET_CODE (src) == SUBREG 1390 && (GET_MODE_SIZE (GET_MODE (src)) 1391 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (src))))) 1392 src = SUBREG_REG (src); 1393 if (REG_P (src) && REG_P (dest) 1394 && find_regno_note (insn, REG_DEAD, REGNO (src)) 1395 && (((regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER 1396 && (other_regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER) 1397 || ((regno = REGNO (dest)) >= FIRST_PSEUDO_REGISTER 1398 && (other_regno = REGNO (src)) < FIRST_PSEUDO_REGISTER))) 1399 { 1400 machine_mode mode = GET_MODE (src); 1401 cost_classes_t cost_classes_ptr = regno_cost_classes[regno]; 1402 enum reg_class *cost_classes = cost_classes_ptr->classes; 1403 reg_class_t rclass; 1404 int k, nr; 1405 1406 i = regno == (int) REGNO (src) ? 1 : 0; 1407 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 1408 { 1409 rclass = cost_classes[k]; 1410 if (TEST_HARD_REG_BIT (reg_class_contents[rclass], other_regno) 1411 && (reg_class_size[(int) rclass] 1412 == ira_reg_class_max_nregs [(int) rclass][(int) mode])) 1413 { 1414 if (reg_class_size[rclass] == 1) 1415 op_costs[i]->cost[k] = -frequency; 1416 else 1417 { 1418 for (nr = 0; 1419 nr < hard_regno_nregs[other_regno][mode]; 1420 nr++) 1421 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass], 1422 other_regno + nr)) 1423 break; 1424 1425 if (nr == hard_regno_nregs[other_regno][mode]) 1426 op_costs[i]->cost[k] = -frequency; 1427 } 1428 } 1429 } 1430 } 1431 } 1432} 1433 1434 1435 1436/* Process one insn INSN. Scan it and record each time it would save 1437 code to put a certain allocnos in a certain class. Return the last 1438 insn processed, so that the scan can be continued from there. */ 1439static rtx_insn * 1440scan_one_insn (rtx_insn *insn) 1441{ 1442 enum rtx_code pat_code; 1443 rtx set, note; 1444 int i, k; 1445 bool counted_mem; 1446 1447 if (!NONDEBUG_INSN_P (insn)) 1448 return insn; 1449 1450 pat_code = GET_CODE (PATTERN (insn)); 1451 if (pat_code == USE || pat_code == CLOBBER || pat_code == ASM_INPUT) 1452 return insn; 1453 1454 counted_mem = false; 1455 set = single_set (insn); 1456 extract_insn (insn); 1457 1458 /* If this insn loads a parameter from its stack slot, then it 1459 represents a savings, rather than a cost, if the parameter is 1460 stored in memory. Record this fact. 1461 1462 Similarly if we're loading other constants from memory (constant 1463 pool, TOC references, small data areas, etc) and this is the only 1464 assignment to the destination pseudo. 1465 1466 Don't do this if SET_SRC (set) isn't a general operand, if it is 1467 a memory requiring special instructions to load it, decreasing 1468 mem_cost might result in it being loaded using the specialized 1469 instruction into a register, then stored into stack and loaded 1470 again from the stack. See PR52208. 1471 1472 Don't do this if SET_SRC (set) has side effect. See PR56124. */ 1473 if (set != 0 && REG_P (SET_DEST (set)) && MEM_P (SET_SRC (set)) 1474 && (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL_RTX 1475 && ((MEM_P (XEXP (note, 0)) 1476 && !side_effects_p (SET_SRC (set))) 1477 || (CONSTANT_P (XEXP (note, 0)) 1478 && targetm.legitimate_constant_p (GET_MODE (SET_DEST (set)), 1479 XEXP (note, 0)) 1480 && REG_N_SETS (REGNO (SET_DEST (set))) == 1)) 1481 && general_operand (SET_SRC (set), GET_MODE (SET_SRC (set)))) 1482 { 1483 enum reg_class cl = GENERAL_REGS; 1484 rtx reg = SET_DEST (set); 1485 int num = COST_INDEX (REGNO (reg)); 1486 1487 COSTS (costs, num)->mem_cost 1488 -= ira_memory_move_cost[GET_MODE (reg)][cl][1] * frequency; 1489 record_address_regs (GET_MODE (SET_SRC (set)), 1490 MEM_ADDR_SPACE (SET_SRC (set)), 1491 XEXP (SET_SRC (set), 0), 0, MEM, SCRATCH, 1492 frequency * 2); 1493 counted_mem = true; 1494 } 1495 1496 record_operand_costs (insn, pref); 1497 1498 /* Now add the cost for each operand to the total costs for its 1499 allocno. */ 1500 for (i = 0; i < recog_data.n_operands; i++) 1501 if (REG_P (recog_data.operand[i]) 1502 && REGNO (recog_data.operand[i]) >= FIRST_PSEUDO_REGISTER) 1503 { 1504 int regno = REGNO (recog_data.operand[i]); 1505 struct costs *p = COSTS (costs, COST_INDEX (regno)); 1506 struct costs *q = op_costs[i]; 1507 int *p_costs = p->cost, *q_costs = q->cost; 1508 cost_classes_t cost_classes_ptr = regno_cost_classes[regno]; 1509 int add_cost; 1510 1511 /* If the already accounted for the memory "cost" above, don't 1512 do so again. */ 1513 if (!counted_mem) 1514 { 1515 add_cost = q->mem_cost; 1516 if (add_cost > 0 && INT_MAX - add_cost < p->mem_cost) 1517 p->mem_cost = INT_MAX; 1518 else 1519 p->mem_cost += add_cost; 1520 } 1521 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 1522 { 1523 add_cost = q_costs[k]; 1524 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k]) 1525 p_costs[k] = INT_MAX; 1526 else 1527 p_costs[k] += add_cost; 1528 } 1529 } 1530 1531 return insn; 1532} 1533 1534 1535 1536/* Print allocnos costs to file F. */ 1537static void 1538print_allocno_costs (FILE *f) 1539{ 1540 int k; 1541 ira_allocno_t a; 1542 ira_allocno_iterator ai; 1543 1544 ira_assert (allocno_p); 1545 fprintf (f, "\n"); 1546 FOR_EACH_ALLOCNO (a, ai) 1547 { 1548 int i, rclass; 1549 basic_block bb; 1550 int regno = ALLOCNO_REGNO (a); 1551 cost_classes_t cost_classes_ptr = regno_cost_classes[regno]; 1552 enum reg_class *cost_classes = cost_classes_ptr->classes; 1553 1554 i = ALLOCNO_NUM (a); 1555 fprintf (f, " a%d(r%d,", i, regno); 1556 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL) 1557 fprintf (f, "b%d", bb->index); 1558 else 1559 fprintf (f, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num); 1560 fprintf (f, ") costs:"); 1561 for (k = 0; k < cost_classes_ptr->num; k++) 1562 { 1563 rclass = cost_classes[k]; 1564 fprintf (f, " %s:%d", reg_class_names[rclass], 1565 COSTS (costs, i)->cost[k]); 1566 if (flag_ira_region == IRA_REGION_ALL 1567 || flag_ira_region == IRA_REGION_MIXED) 1568 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->cost[k]); 1569 } 1570 fprintf (f, " MEM:%i", COSTS (costs, i)->mem_cost); 1571 if (flag_ira_region == IRA_REGION_ALL 1572 || flag_ira_region == IRA_REGION_MIXED) 1573 fprintf (f, ",%d", COSTS (total_allocno_costs, i)->mem_cost); 1574 fprintf (f, "\n"); 1575 } 1576} 1577 1578/* Print pseudo costs to file F. */ 1579static void 1580print_pseudo_costs (FILE *f) 1581{ 1582 int regno, k; 1583 int rclass; 1584 cost_classes_t cost_classes_ptr; 1585 enum reg_class *cost_classes; 1586 1587 ira_assert (! allocno_p); 1588 fprintf (f, "\n"); 1589 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--) 1590 { 1591 if (REG_N_REFS (regno) <= 0) 1592 continue; 1593 cost_classes_ptr = regno_cost_classes[regno]; 1594 cost_classes = cost_classes_ptr->classes; 1595 fprintf (f, " r%d costs:", regno); 1596 for (k = 0; k < cost_classes_ptr->num; k++) 1597 { 1598 rclass = cost_classes[k]; 1599 fprintf (f, " %s:%d", reg_class_names[rclass], 1600 COSTS (costs, regno)->cost[k]); 1601 } 1602 fprintf (f, " MEM:%i\n", COSTS (costs, regno)->mem_cost); 1603 } 1604} 1605 1606/* Traverse the BB represented by LOOP_TREE_NODE to update the allocno 1607 costs. */ 1608static void 1609process_bb_for_costs (basic_block bb) 1610{ 1611 rtx_insn *insn; 1612 1613 frequency = REG_FREQ_FROM_BB (bb); 1614 if (frequency == 0) 1615 frequency = 1; 1616 FOR_BB_INSNS (bb, insn) 1617 insn = scan_one_insn (insn); 1618} 1619 1620/* Traverse the BB represented by LOOP_TREE_NODE to update the allocno 1621 costs. */ 1622static void 1623process_bb_node_for_costs (ira_loop_tree_node_t loop_tree_node) 1624{ 1625 basic_block bb; 1626 1627 bb = loop_tree_node->bb; 1628 if (bb != NULL) 1629 process_bb_for_costs (bb); 1630} 1631 1632/* Find costs of register classes and memory for allocnos or pseudos 1633 and their best costs. Set up preferred, alternative and allocno 1634 classes for pseudos. */ 1635static void 1636find_costs_and_classes (FILE *dump_file) 1637{ 1638 int i, k, start, max_cost_classes_num; 1639 int pass; 1640 basic_block bb; 1641 enum reg_class *regno_best_class; 1642 1643 init_recog (); 1644 regno_best_class 1645 = (enum reg_class *) ira_allocate (max_reg_num () 1646 * sizeof (enum reg_class)); 1647 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--) 1648 regno_best_class[i] = NO_REGS; 1649 if (!resize_reg_info () && allocno_p 1650 && pseudo_classes_defined_p && flag_expensive_optimizations) 1651 { 1652 ira_allocno_t a; 1653 ira_allocno_iterator ai; 1654 1655 pref = pref_buffer; 1656 max_cost_classes_num = 1; 1657 FOR_EACH_ALLOCNO (a, ai) 1658 { 1659 pref[ALLOCNO_NUM (a)] = reg_preferred_class (ALLOCNO_REGNO (a)); 1660 setup_regno_cost_classes_by_aclass 1661 (ALLOCNO_REGNO (a), pref[ALLOCNO_NUM (a)]); 1662 max_cost_classes_num 1663 = MAX (max_cost_classes_num, 1664 regno_cost_classes[ALLOCNO_REGNO (a)]->num); 1665 } 1666 start = 1; 1667 } 1668 else 1669 { 1670 pref = NULL; 1671 max_cost_classes_num = ira_important_classes_num; 1672 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--) 1673 if (regno_reg_rtx[i] != NULL_RTX) 1674 setup_regno_cost_classes_by_mode (i, PSEUDO_REGNO_MODE (i)); 1675 else 1676 setup_regno_cost_classes_by_aclass (i, ALL_REGS); 1677 start = 0; 1678 } 1679 if (allocno_p) 1680 /* Clear the flag for the next compiled function. */ 1681 pseudo_classes_defined_p = false; 1682 /* Normally we scan the insns once and determine the best class to 1683 use for each allocno. However, if -fexpensive-optimizations are 1684 on, we do so twice, the second time using the tentative best 1685 classes to guide the selection. */ 1686 for (pass = start; pass <= flag_expensive_optimizations; pass++) 1687 { 1688 if ((!allocno_p || internal_flag_ira_verbose > 0) && dump_file) 1689 fprintf (dump_file, 1690 "\nPass %i for finding pseudo/allocno costs\n\n", pass); 1691 1692 if (pass != start) 1693 { 1694 max_cost_classes_num = 1; 1695 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--) 1696 { 1697 setup_regno_cost_classes_by_aclass (i, regno_best_class[i]); 1698 max_cost_classes_num 1699 = MAX (max_cost_classes_num, regno_cost_classes[i]->num); 1700 } 1701 } 1702 1703 struct_costs_size 1704 = sizeof (struct costs) + sizeof (int) * (max_cost_classes_num - 1); 1705 /* Zero out our accumulation of the cost of each class for each 1706 allocno. */ 1707 memset (costs, 0, cost_elements_num * struct_costs_size); 1708 1709 if (allocno_p) 1710 { 1711 /* Scan the instructions and record each time it would save code 1712 to put a certain allocno in a certain class. */ 1713 ira_traverse_loop_tree (true, ira_loop_tree_root, 1714 process_bb_node_for_costs, NULL); 1715 1716 memcpy (total_allocno_costs, costs, 1717 max_struct_costs_size * ira_allocnos_num); 1718 } 1719 else 1720 { 1721 basic_block bb; 1722 1723 FOR_EACH_BB_FN (bb, cfun) 1724 process_bb_for_costs (bb); 1725 } 1726 1727 if (pass == 0) 1728 pref = pref_buffer; 1729 1730 /* Now for each allocno look at how desirable each class is and 1731 find which class is preferred. */ 1732 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--) 1733 { 1734 ira_allocno_t a, parent_a; 1735 int rclass, a_num, parent_a_num, add_cost; 1736 ira_loop_tree_node_t parent; 1737 int best_cost, allocno_cost; 1738 enum reg_class best, alt_class; 1739 cost_classes_t cost_classes_ptr = regno_cost_classes[i]; 1740 enum reg_class *cost_classes = cost_classes_ptr->classes; 1741 int *i_costs = temp_costs->cost; 1742 int i_mem_cost; 1743 int equiv_savings = regno_equiv_gains[i]; 1744 1745 if (! allocno_p) 1746 { 1747 if (regno_reg_rtx[i] == NULL_RTX) 1748 continue; 1749 memcpy (temp_costs, COSTS (costs, i), struct_costs_size); 1750 i_mem_cost = temp_costs->mem_cost; 1751 } 1752 else 1753 { 1754 if (ira_regno_allocno_map[i] == NULL) 1755 continue; 1756 memset (temp_costs, 0, struct_costs_size); 1757 i_mem_cost = 0; 1758 /* Find cost of all allocnos with the same regno. */ 1759 for (a = ira_regno_allocno_map[i]; 1760 a != NULL; 1761 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 1762 { 1763 int *a_costs, *p_costs; 1764 1765 a_num = ALLOCNO_NUM (a); 1766 if ((flag_ira_region == IRA_REGION_ALL 1767 || flag_ira_region == IRA_REGION_MIXED) 1768 && (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL 1769 && (parent_a = parent->regno_allocno_map[i]) != NULL 1770 /* There are no caps yet. */ 1771 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE 1772 (a)->border_allocnos, 1773 ALLOCNO_NUM (a))) 1774 { 1775 /* Propagate costs to upper levels in the region 1776 tree. */ 1777 parent_a_num = ALLOCNO_NUM (parent_a); 1778 a_costs = COSTS (total_allocno_costs, a_num)->cost; 1779 p_costs = COSTS (total_allocno_costs, parent_a_num)->cost; 1780 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 1781 { 1782 add_cost = a_costs[k]; 1783 if (add_cost > 0 && INT_MAX - add_cost < p_costs[k]) 1784 p_costs[k] = INT_MAX; 1785 else 1786 p_costs[k] += add_cost; 1787 } 1788 add_cost = COSTS (total_allocno_costs, a_num)->mem_cost; 1789 if (add_cost > 0 1790 && (INT_MAX - add_cost 1791 < COSTS (total_allocno_costs, 1792 parent_a_num)->mem_cost)) 1793 COSTS (total_allocno_costs, parent_a_num)->mem_cost 1794 = INT_MAX; 1795 else 1796 COSTS (total_allocno_costs, parent_a_num)->mem_cost 1797 += add_cost; 1798 1799 if (i >= first_moveable_pseudo && i < last_moveable_pseudo) 1800 COSTS (total_allocno_costs, parent_a_num)->mem_cost = 0; 1801 } 1802 a_costs = COSTS (costs, a_num)->cost; 1803 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 1804 { 1805 add_cost = a_costs[k]; 1806 if (add_cost > 0 && INT_MAX - add_cost < i_costs[k]) 1807 i_costs[k] = INT_MAX; 1808 else 1809 i_costs[k] += add_cost; 1810 } 1811 add_cost = COSTS (costs, a_num)->mem_cost; 1812 if (add_cost > 0 && INT_MAX - add_cost < i_mem_cost) 1813 i_mem_cost = INT_MAX; 1814 else 1815 i_mem_cost += add_cost; 1816 } 1817 } 1818 if (i >= first_moveable_pseudo && i < last_moveable_pseudo) 1819 i_mem_cost = 0; 1820 else if (equiv_savings < 0) 1821 i_mem_cost = -equiv_savings; 1822 else if (equiv_savings > 0) 1823 { 1824 i_mem_cost = 0; 1825 for (k = cost_classes_ptr->num - 1; k >= 0; k--) 1826 i_costs[k] += equiv_savings; 1827 } 1828 1829 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1; 1830 best = ALL_REGS; 1831 alt_class = NO_REGS; 1832 /* Find best common class for all allocnos with the same 1833 regno. */ 1834 for (k = 0; k < cost_classes_ptr->num; k++) 1835 { 1836 rclass = cost_classes[k]; 1837 if (i_costs[k] < best_cost) 1838 { 1839 best_cost = i_costs[k]; 1840 best = (enum reg_class) rclass; 1841 } 1842 else if (i_costs[k] == best_cost) 1843 best = ira_reg_class_subunion[best][rclass]; 1844 if (pass == flag_expensive_optimizations 1845 /* We still prefer registers to memory even at this 1846 stage if their costs are the same. We will make 1847 a final decision during assigning hard registers 1848 when we have all info including more accurate 1849 costs which might be affected by assigning hard 1850 registers to other pseudos because the pseudos 1851 involved in moves can be coalesced. */ 1852 && i_costs[k] <= i_mem_cost 1853 && (reg_class_size[reg_class_subunion[alt_class][rclass]] 1854 > reg_class_size[alt_class])) 1855 alt_class = reg_class_subunion[alt_class][rclass]; 1856 } 1857 alt_class = ira_allocno_class_translate[alt_class]; 1858 if (best_cost > i_mem_cost) 1859 regno_aclass[i] = NO_REGS; 1860 else if (!optimize && !targetm.class_likely_spilled_p (best)) 1861 /* Registers in the alternative class are likely to need 1862 longer or slower sequences than registers in the best class. 1863 When optimizing we make some effort to use the best class 1864 over the alternative class where possible, but at -O0 we 1865 effectively give the alternative class equal weight. 1866 We then run the risk of using slower alternative registers 1867 when plenty of registers from the best class are still free. 1868 This is especially true because live ranges tend to be very 1869 short in -O0 code and so register pressure tends to be low. 1870 1871 Avoid that by ignoring the alternative class if the best 1872 class has plenty of registers. */ 1873 regno_aclass[i] = best; 1874 else 1875 { 1876 /* Make the common class the biggest class of best and 1877 alt_class. */ 1878 regno_aclass[i] 1879 = ira_reg_class_superunion[best][alt_class]; 1880 ira_assert (regno_aclass[i] != NO_REGS 1881 && ira_reg_allocno_class_p[regno_aclass[i]]); 1882 } 1883 if (pass == flag_expensive_optimizations) 1884 { 1885 if (best_cost > i_mem_cost) 1886 best = alt_class = NO_REGS; 1887 else if (best == alt_class) 1888 alt_class = NO_REGS; 1889 setup_reg_classes (i, best, alt_class, regno_aclass[i]); 1890 if ((!allocno_p || internal_flag_ira_verbose > 2) 1891 && dump_file != NULL) 1892 fprintf (dump_file, 1893 " r%d: preferred %s, alternative %s, allocno %s\n", 1894 i, reg_class_names[best], reg_class_names[alt_class], 1895 reg_class_names[regno_aclass[i]]); 1896 } 1897 regno_best_class[i] = best; 1898 if (! allocno_p) 1899 { 1900 pref[i] = best_cost > i_mem_cost ? NO_REGS : best; 1901 continue; 1902 } 1903 for (a = ira_regno_allocno_map[i]; 1904 a != NULL; 1905 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 1906 { 1907 enum reg_class aclass = regno_aclass[i]; 1908 int a_num = ALLOCNO_NUM (a); 1909 int *total_a_costs = COSTS (total_allocno_costs, a_num)->cost; 1910 int *a_costs = COSTS (costs, a_num)->cost; 1911 1912 if (aclass == NO_REGS) 1913 best = NO_REGS; 1914 else 1915 { 1916 /* Finding best class which is subset of the common 1917 class. */ 1918 best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1; 1919 allocno_cost = best_cost; 1920 best = ALL_REGS; 1921 for (k = 0; k < cost_classes_ptr->num; k++) 1922 { 1923 rclass = cost_classes[k]; 1924 if (! ira_class_subset_p[rclass][aclass]) 1925 continue; 1926 if (total_a_costs[k] < best_cost) 1927 { 1928 best_cost = total_a_costs[k]; 1929 allocno_cost = a_costs[k]; 1930 best = (enum reg_class) rclass; 1931 } 1932 else if (total_a_costs[k] == best_cost) 1933 { 1934 best = ira_reg_class_subunion[best][rclass]; 1935 allocno_cost = MAX (allocno_cost, a_costs[k]); 1936 } 1937 } 1938 ALLOCNO_CLASS_COST (a) = allocno_cost; 1939 } 1940 if (internal_flag_ira_verbose > 2 && dump_file != NULL 1941 && (pass == 0 || pref[a_num] != best)) 1942 { 1943 fprintf (dump_file, " a%d (r%d,", a_num, i); 1944 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL) 1945 fprintf (dump_file, "b%d", bb->index); 1946 else 1947 fprintf (dump_file, "l%d", 1948 ALLOCNO_LOOP_TREE_NODE (a)->loop_num); 1949 fprintf (dump_file, ") best %s, allocno %s\n", 1950 reg_class_names[best], 1951 reg_class_names[aclass]); 1952 } 1953 pref[a_num] = best; 1954 if (pass == flag_expensive_optimizations && best != aclass 1955 && ira_class_hard_regs_num[best] > 0 1956 && (ira_reg_class_max_nregs[best][ALLOCNO_MODE (a)] 1957 >= ira_class_hard_regs_num[best])) 1958 { 1959 int ind = cost_classes_ptr->index[aclass]; 1960 1961 ira_assert (ind >= 0); 1962 ira_init_register_move_cost_if_necessary (ALLOCNO_MODE (a)); 1963 ira_add_allocno_pref (a, ira_class_hard_regs[best][0], 1964 (a_costs[ind] - ALLOCNO_CLASS_COST (a)) 1965 / (ira_register_move_cost 1966 [ALLOCNO_MODE (a)][best][aclass])); 1967 for (k = 0; k < cost_classes_ptr->num; k++) 1968 if (ira_class_subset_p[cost_classes[k]][best]) 1969 a_costs[k] = a_costs[ind]; 1970 } 1971 } 1972 } 1973 1974 if (internal_flag_ira_verbose > 4 && dump_file) 1975 { 1976 if (allocno_p) 1977 print_allocno_costs (dump_file); 1978 else 1979 print_pseudo_costs (dump_file); 1980 fprintf (dump_file,"\n"); 1981 } 1982 } 1983 ira_free (regno_best_class); 1984} 1985 1986 1987 1988/* Process moves involving hard regs to modify allocno hard register 1989 costs. We can do this only after determining allocno class. If a 1990 hard register forms a register class, then moves with the hard 1991 register are already taken into account in class costs for the 1992 allocno. */ 1993static void 1994process_bb_node_for_hard_reg_moves (ira_loop_tree_node_t loop_tree_node) 1995{ 1996 int i, freq, src_regno, dst_regno, hard_regno, a_regno; 1997 bool to_p; 1998 ira_allocno_t a, curr_a; 1999 ira_loop_tree_node_t curr_loop_tree_node; 2000 enum reg_class rclass; 2001 basic_block bb; 2002 rtx_insn *insn; 2003 rtx set, src, dst; 2004 2005 bb = loop_tree_node->bb; 2006 if (bb == NULL) 2007 return; 2008 freq = REG_FREQ_FROM_BB (bb); 2009 if (freq == 0) 2010 freq = 1; 2011 FOR_BB_INSNS (bb, insn) 2012 { 2013 if (!NONDEBUG_INSN_P (insn)) 2014 continue; 2015 set = single_set (insn); 2016 if (set == NULL_RTX) 2017 continue; 2018 dst = SET_DEST (set); 2019 src = SET_SRC (set); 2020 if (! REG_P (dst) || ! REG_P (src)) 2021 continue; 2022 dst_regno = REGNO (dst); 2023 src_regno = REGNO (src); 2024 if (dst_regno >= FIRST_PSEUDO_REGISTER 2025 && src_regno < FIRST_PSEUDO_REGISTER) 2026 { 2027 hard_regno = src_regno; 2028 a = ira_curr_regno_allocno_map[dst_regno]; 2029 to_p = true; 2030 } 2031 else if (src_regno >= FIRST_PSEUDO_REGISTER 2032 && dst_regno < FIRST_PSEUDO_REGISTER) 2033 { 2034 hard_regno = dst_regno; 2035 a = ira_curr_regno_allocno_map[src_regno]; 2036 to_p = false; 2037 } 2038 else 2039 continue; 2040 rclass = ALLOCNO_CLASS (a); 2041 if (! TEST_HARD_REG_BIT (reg_class_contents[rclass], hard_regno)) 2042 continue; 2043 i = ira_class_hard_reg_index[rclass][hard_regno]; 2044 if (i < 0) 2045 continue; 2046 a_regno = ALLOCNO_REGNO (a); 2047 for (curr_loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a); 2048 curr_loop_tree_node != NULL; 2049 curr_loop_tree_node = curr_loop_tree_node->parent) 2050 if ((curr_a = curr_loop_tree_node->regno_allocno_map[a_regno]) != NULL) 2051 ira_add_allocno_pref (curr_a, hard_regno, freq); 2052 { 2053 int cost; 2054 enum reg_class hard_reg_class; 2055 machine_mode mode; 2056 2057 mode = ALLOCNO_MODE (a); 2058 hard_reg_class = REGNO_REG_CLASS (hard_regno); 2059 ira_init_register_move_cost_if_necessary (mode); 2060 cost = (to_p ? ira_register_move_cost[mode][hard_reg_class][rclass] 2061 : ira_register_move_cost[mode][rclass][hard_reg_class]) * freq; 2062 ira_allocate_and_set_costs (&ALLOCNO_HARD_REG_COSTS (a), rclass, 2063 ALLOCNO_CLASS_COST (a)); 2064 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), 2065 rclass, 0); 2066 ALLOCNO_HARD_REG_COSTS (a)[i] -= cost; 2067 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[i] -= cost; 2068 ALLOCNO_CLASS_COST (a) = MIN (ALLOCNO_CLASS_COST (a), 2069 ALLOCNO_HARD_REG_COSTS (a)[i]); 2070 } 2071 } 2072} 2073 2074/* After we find hard register and memory costs for allocnos, define 2075 its class and modify hard register cost because insns moving 2076 allocno to/from hard registers. */ 2077static void 2078setup_allocno_class_and_costs (void) 2079{ 2080 int i, j, n, regno, hard_regno, num; 2081 int *reg_costs; 2082 enum reg_class aclass, rclass; 2083 ira_allocno_t a; 2084 ira_allocno_iterator ai; 2085 cost_classes_t cost_classes_ptr; 2086 2087 ira_assert (allocno_p); 2088 FOR_EACH_ALLOCNO (a, ai) 2089 { 2090 i = ALLOCNO_NUM (a); 2091 regno = ALLOCNO_REGNO (a); 2092 aclass = regno_aclass[regno]; 2093 cost_classes_ptr = regno_cost_classes[regno]; 2094 ira_assert (pref[i] == NO_REGS || aclass != NO_REGS); 2095 ALLOCNO_MEMORY_COST (a) = COSTS (costs, i)->mem_cost; 2096 ira_set_allocno_class (a, aclass); 2097 if (aclass == NO_REGS) 2098 continue; 2099 if (optimize && ALLOCNO_CLASS (a) != pref[i]) 2100 { 2101 n = ira_class_hard_regs_num[aclass]; 2102 ALLOCNO_HARD_REG_COSTS (a) 2103 = reg_costs = ira_allocate_cost_vector (aclass); 2104 for (j = n - 1; j >= 0; j--) 2105 { 2106 hard_regno = ira_class_hard_regs[aclass][j]; 2107 if (TEST_HARD_REG_BIT (reg_class_contents[pref[i]], hard_regno)) 2108 reg_costs[j] = ALLOCNO_CLASS_COST (a); 2109 else 2110 { 2111 rclass = REGNO_REG_CLASS (hard_regno); 2112 num = cost_classes_ptr->index[rclass]; 2113 if (num < 0) 2114 { 2115 num = cost_classes_ptr->hard_regno_index[hard_regno]; 2116 ira_assert (num >= 0); 2117 } 2118 reg_costs[j] = COSTS (costs, i)->cost[num]; 2119 } 2120 } 2121 } 2122 } 2123 if (optimize) 2124 ira_traverse_loop_tree (true, ira_loop_tree_root, 2125 process_bb_node_for_hard_reg_moves, NULL); 2126} 2127 2128 2129 2130/* Function called once during compiler work. */ 2131void 2132ira_init_costs_once (void) 2133{ 2134 int i; 2135 2136 init_cost = NULL; 2137 for (i = 0; i < MAX_RECOG_OPERANDS; i++) 2138 { 2139 op_costs[i] = NULL; 2140 this_op_costs[i] = NULL; 2141 } 2142 temp_costs = NULL; 2143} 2144 2145/* Free allocated temporary cost vectors. */ 2146void 2147target_ira_int::free_ira_costs () 2148{ 2149 int i; 2150 2151 free (x_init_cost); 2152 x_init_cost = NULL; 2153 for (i = 0; i < MAX_RECOG_OPERANDS; i++) 2154 { 2155 free (x_op_costs[i]); 2156 free (x_this_op_costs[i]); 2157 x_op_costs[i] = x_this_op_costs[i] = NULL; 2158 } 2159 free (x_temp_costs); 2160 x_temp_costs = NULL; 2161} 2162 2163/* This is called each time register related information is 2164 changed. */ 2165void 2166ira_init_costs (void) 2167{ 2168 int i; 2169 2170 this_target_ira_int->free_ira_costs (); 2171 max_struct_costs_size 2172 = sizeof (struct costs) + sizeof (int) * (ira_important_classes_num - 1); 2173 /* Don't use ira_allocate because vectors live through several IRA 2174 calls. */ 2175 init_cost = (struct costs *) xmalloc (max_struct_costs_size); 2176 init_cost->mem_cost = 1000000; 2177 for (i = 0; i < ira_important_classes_num; i++) 2178 init_cost->cost[i] = 1000000; 2179 for (i = 0; i < MAX_RECOG_OPERANDS; i++) 2180 { 2181 op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size); 2182 this_op_costs[i] = (struct costs *) xmalloc (max_struct_costs_size); 2183 } 2184 temp_costs = (struct costs *) xmalloc (max_struct_costs_size); 2185} 2186 2187 2188 2189/* Common initialization function for ira_costs and 2190 ira_set_pseudo_classes. */ 2191static void 2192init_costs (void) 2193{ 2194 init_subregs_of_mode (); 2195 costs = (struct costs *) ira_allocate (max_struct_costs_size 2196 * cost_elements_num); 2197 pref_buffer = (enum reg_class *) ira_allocate (sizeof (enum reg_class) 2198 * cost_elements_num); 2199 regno_aclass = (enum reg_class *) ira_allocate (sizeof (enum reg_class) 2200 * max_reg_num ()); 2201 regno_equiv_gains = (int *) ira_allocate (sizeof (int) * max_reg_num ()); 2202 memset (regno_equiv_gains, 0, sizeof (int) * max_reg_num ()); 2203} 2204 2205/* Common finalization function for ira_costs and 2206 ira_set_pseudo_classes. */ 2207static void 2208finish_costs (void) 2209{ 2210 finish_subregs_of_mode (); 2211 ira_free (regno_equiv_gains); 2212 ira_free (regno_aclass); 2213 ira_free (pref_buffer); 2214 ira_free (costs); 2215} 2216 2217/* Entry function which defines register class, memory and hard 2218 register costs for each allocno. */ 2219void 2220ira_costs (void) 2221{ 2222 allocno_p = true; 2223 cost_elements_num = ira_allocnos_num; 2224 init_costs (); 2225 total_allocno_costs = (struct costs *) ira_allocate (max_struct_costs_size 2226 * ira_allocnos_num); 2227 initiate_regno_cost_classes (); 2228 calculate_elim_costs_all_insns (); 2229 find_costs_and_classes (ira_dump_file); 2230 setup_allocno_class_and_costs (); 2231 finish_regno_cost_classes (); 2232 finish_costs (); 2233 ira_free (total_allocno_costs); 2234} 2235 2236/* Entry function which defines classes for pseudos. 2237 Set pseudo_classes_defined_p only if DEFINE_PSEUDO_CLASSES is true. */ 2238void 2239ira_set_pseudo_classes (bool define_pseudo_classes, FILE *dump_file) 2240{ 2241 allocno_p = false; 2242 internal_flag_ira_verbose = flag_ira_verbose; 2243 cost_elements_num = max_reg_num (); 2244 init_costs (); 2245 initiate_regno_cost_classes (); 2246 find_costs_and_classes (dump_file); 2247 finish_regno_cost_classes (); 2248 if (define_pseudo_classes) 2249 pseudo_classes_defined_p = true; 2250 2251 finish_costs (); 2252} 2253 2254 2255 2256/* Change hard register costs for allocnos which lives through 2257 function calls. This is called only when we found all intersected 2258 calls during building allocno live ranges. */ 2259void 2260ira_tune_allocno_costs (void) 2261{ 2262 int j, n, regno; 2263 int cost, min_cost, *reg_costs; 2264 enum reg_class aclass, rclass; 2265 machine_mode mode; 2266 ira_allocno_t a; 2267 ira_allocno_iterator ai; 2268 ira_allocno_object_iterator oi; 2269 ira_object_t obj; 2270 bool skip_p; 2271 HARD_REG_SET *crossed_calls_clobber_regs; 2272 2273 FOR_EACH_ALLOCNO (a, ai) 2274 { 2275 aclass = ALLOCNO_CLASS (a); 2276 if (aclass == NO_REGS) 2277 continue; 2278 mode = ALLOCNO_MODE (a); 2279 n = ira_class_hard_regs_num[aclass]; 2280 min_cost = INT_MAX; 2281 if (ALLOCNO_CALLS_CROSSED_NUM (a) 2282 != ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)) 2283 { 2284 ira_allocate_and_set_costs 2285 (&ALLOCNO_HARD_REG_COSTS (a), aclass, 2286 ALLOCNO_CLASS_COST (a)); 2287 reg_costs = ALLOCNO_HARD_REG_COSTS (a); 2288 for (j = n - 1; j >= 0; j--) 2289 { 2290 regno = ira_class_hard_regs[aclass][j]; 2291 skip_p = false; 2292 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi) 2293 { 2294 if (ira_hard_reg_set_intersection_p (regno, mode, 2295 OBJECT_CONFLICT_HARD_REGS 2296 (obj))) 2297 { 2298 skip_p = true; 2299 break; 2300 } 2301 } 2302 if (skip_p) 2303 continue; 2304 rclass = REGNO_REG_CLASS (regno); 2305 cost = 0; 2306 crossed_calls_clobber_regs 2307 = &(ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a)); 2308 if (ira_hard_reg_set_intersection_p (regno, mode, 2309 *crossed_calls_clobber_regs) 2310 && (ira_hard_reg_set_intersection_p (regno, mode, 2311 call_used_reg_set) 2312 || HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))) 2313 cost += (ALLOCNO_CALL_FREQ (a) 2314 * (ira_memory_move_cost[mode][rclass][0] 2315 + ira_memory_move_cost[mode][rclass][1])); 2316#ifdef IRA_HARD_REGNO_ADD_COST_MULTIPLIER 2317 cost += ((ira_memory_move_cost[mode][rclass][0] 2318 + ira_memory_move_cost[mode][rclass][1]) 2319 * ALLOCNO_FREQ (a) 2320 * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno) / 2); 2321#endif 2322 if (INT_MAX - cost < reg_costs[j]) 2323 reg_costs[j] = INT_MAX; 2324 else 2325 reg_costs[j] += cost; 2326 if (min_cost > reg_costs[j]) 2327 min_cost = reg_costs[j]; 2328 } 2329 } 2330 if (min_cost != INT_MAX) 2331 ALLOCNO_CLASS_COST (a) = min_cost; 2332 2333 /* Some targets allow pseudos to be allocated to unaligned sequences 2334 of hard registers. However, selecting an unaligned sequence can 2335 unnecessarily restrict later allocations. So increase the cost of 2336 unaligned hard regs to encourage the use of aligned hard regs. */ 2337 { 2338 const int nregs = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)]; 2339 2340 if (nregs > 1) 2341 { 2342 ira_allocate_and_set_costs 2343 (&ALLOCNO_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a)); 2344 reg_costs = ALLOCNO_HARD_REG_COSTS (a); 2345 for (j = n - 1; j >= 0; j--) 2346 { 2347 regno = ira_non_ordered_class_hard_regs[aclass][j]; 2348 if ((regno % nregs) != 0) 2349 { 2350 int index = ira_class_hard_reg_index[aclass][regno]; 2351 ira_assert (index != -1); 2352 reg_costs[index] += ALLOCNO_FREQ (a); 2353 } 2354 } 2355 } 2356 } 2357 } 2358} 2359 2360/* Add COST to the estimated gain for eliminating REGNO with its 2361 equivalence. If COST is zero, record that no such elimination is 2362 possible. */ 2363 2364void 2365ira_adjust_equiv_reg_cost (unsigned regno, int cost) 2366{ 2367 if (cost == 0) 2368 regno_equiv_gains[regno] = 0; 2369 else 2370 regno_equiv_gains[regno] += cost; 2371} 2372 2373void 2374ira_costs_c_finalize (void) 2375{ 2376 this_target_ira_int->free_ira_costs (); 2377} 2378