1 /* IRA conflict builder. 2 Copyright (C) 2006, 2007, 2008, 2009, 2010 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 "regs.h" 27 #include "rtl.h" 28 #include "tm_p.h" 29 #include "target.h" 30 #include "flags.h" 31 #include "hard-reg-set.h" 32 #include "basic-block.h" 33 #include "insn-config.h" 34 #include "recog.h" 35 #include "diagnostic-core.h" 36 #include "params.h" 37 #include "df.h" 38 #include "sparseset.h" 39 #include "ira-int.h" 40 #include "addresses.h" 41 42 /* This file contains code responsible for allocno conflict creation, 43 allocno copy creation and allocno info accumulation on upper level 44 regions. */ 45 46 /* ira_allocnos_num array of arrays of bits, recording whether two 47 allocno's conflict (can't go in the same hardware register). 48 49 Some arrays will be used as conflict bit vector of the 50 corresponding allocnos see function build_object_conflicts. */ 51 static IRA_INT_TYPE **conflicts; 52 53 /* Macro to test a conflict of C1 and C2 in `conflicts'. */ 54 #define OBJECTS_CONFLICT_P(C1, C2) \ 55 (OBJECT_MIN (C1) <= OBJECT_CONFLICT_ID (C2) \ 56 && OBJECT_CONFLICT_ID (C2) <= OBJECT_MAX (C1) \ 57 && TEST_MINMAX_SET_BIT (conflicts[OBJECT_CONFLICT_ID (C1)], \ 58 OBJECT_CONFLICT_ID (C2), \ 59 OBJECT_MIN (C1), OBJECT_MAX (C1))) 60 61 62 /* Record a conflict between objects OBJ1 and OBJ2. If necessary, 63 canonicalize the conflict by recording it for lower-order subobjects 64 of the corresponding allocnos. */ 65 static void 66 record_object_conflict (ira_object_t obj1, ira_object_t obj2) 67 { 68 ira_allocno_t a1 = OBJECT_ALLOCNO (obj1); 69 ira_allocno_t a2 = OBJECT_ALLOCNO (obj2); 70 int w1 = OBJECT_SUBWORD (obj1); 71 int w2 = OBJECT_SUBWORD (obj2); 72 int id1, id2; 73 74 /* Canonicalize the conflict. If two identically-numbered words 75 conflict, always record this as a conflict between words 0. That 76 is the only information we need, and it is easier to test for if 77 it is collected in each allocno's lowest-order object. */ 78 if (w1 == w2 && w1 > 0) 79 { 80 obj1 = ALLOCNO_OBJECT (a1, 0); 81 obj2 = ALLOCNO_OBJECT (a2, 0); 82 } 83 id1 = OBJECT_CONFLICT_ID (obj1); 84 id2 = OBJECT_CONFLICT_ID (obj2); 85 86 SET_MINMAX_SET_BIT (conflicts[id1], id2, OBJECT_MIN (obj1), 87 OBJECT_MAX (obj1)); 88 SET_MINMAX_SET_BIT (conflicts[id2], id1, OBJECT_MIN (obj2), 89 OBJECT_MAX (obj2)); 90 } 91 92 /* Build allocno conflict table by processing allocno live ranges. 93 Return true if the table was built. The table is not built if it 94 is too big. */ 95 static bool 96 build_conflict_bit_table (void) 97 { 98 int i; 99 unsigned int j; 100 enum reg_class aclass; 101 int object_set_words, allocated_words_num, conflict_bit_vec_words_num; 102 live_range_t r; 103 ira_allocno_t allocno; 104 ira_allocno_iterator ai; 105 sparseset objects_live; 106 ira_object_t obj; 107 ira_allocno_object_iterator aoi; 108 109 allocated_words_num = 0; 110 FOR_EACH_ALLOCNO (allocno, ai) 111 FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi) 112 { 113 if (OBJECT_MAX (obj) < OBJECT_MIN (obj)) 114 continue; 115 conflict_bit_vec_words_num 116 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS) 117 / IRA_INT_BITS); 118 allocated_words_num += conflict_bit_vec_words_num; 119 if ((unsigned HOST_WIDEST_INT) allocated_words_num * sizeof (IRA_INT_TYPE) 120 > (unsigned HOST_WIDEST_INT) IRA_MAX_CONFLICT_TABLE_SIZE * 1024 * 1024) 121 { 122 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) 123 fprintf 124 (ira_dump_file, 125 "+++Conflict table will be too big(>%dMB) -- don't use it\n", 126 IRA_MAX_CONFLICT_TABLE_SIZE); 127 return false; 128 } 129 } 130 131 conflicts = (IRA_INT_TYPE **) ira_allocate (sizeof (IRA_INT_TYPE *) 132 * ira_objects_num); 133 allocated_words_num = 0; 134 FOR_EACH_ALLOCNO (allocno, ai) 135 FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi) 136 { 137 int id = OBJECT_CONFLICT_ID (obj); 138 if (OBJECT_MAX (obj) < OBJECT_MIN (obj)) 139 { 140 conflicts[id] = NULL; 141 continue; 142 } 143 conflict_bit_vec_words_num 144 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS) 145 / IRA_INT_BITS); 146 allocated_words_num += conflict_bit_vec_words_num; 147 conflicts[id] 148 = (IRA_INT_TYPE *) ira_allocate (sizeof (IRA_INT_TYPE) 149 * conflict_bit_vec_words_num); 150 memset (conflicts[id], 0, 151 sizeof (IRA_INT_TYPE) * conflict_bit_vec_words_num); 152 } 153 154 object_set_words = (ira_objects_num + IRA_INT_BITS - 1) / IRA_INT_BITS; 155 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) 156 fprintf 157 (ira_dump_file, 158 "+++Allocating %ld bytes for conflict table (uncompressed size %ld)\n", 159 (long) allocated_words_num * sizeof (IRA_INT_TYPE), 160 (long) object_set_words * ira_objects_num * sizeof (IRA_INT_TYPE)); 161 162 objects_live = sparseset_alloc (ira_objects_num); 163 for (i = 0; i < ira_max_point; i++) 164 { 165 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next) 166 { 167 ira_object_t obj = r->object; 168 ira_allocno_t allocno = OBJECT_ALLOCNO (obj); 169 int id = OBJECT_CONFLICT_ID (obj); 170 171 gcc_assert (id < ira_objects_num); 172 173 aclass = ALLOCNO_CLASS (allocno); 174 sparseset_set_bit (objects_live, id); 175 EXECUTE_IF_SET_IN_SPARSESET (objects_live, j) 176 { 177 ira_object_t live_obj = ira_object_id_map[j]; 178 ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj); 179 enum reg_class live_aclass = ALLOCNO_CLASS (live_a); 180 181 if (ira_reg_classes_intersect_p[aclass][live_aclass] 182 /* Don't set up conflict for the allocno with itself. */ 183 && live_a != allocno) 184 { 185 record_object_conflict (obj, live_obj); 186 } 187 } 188 } 189 190 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next) 191 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object)); 192 } 193 sparseset_free (objects_live); 194 return true; 195 } 196 197 /* Return true iff allocnos A1 and A2 cannot be allocated to the same 198 register due to conflicts. */ 199 200 static bool 201 allocnos_conflict_for_copy_p (ira_allocno_t a1, ira_allocno_t a2) 202 { 203 /* Due to the fact that we canonicalize conflicts (see 204 record_object_conflict), we only need to test for conflicts of 205 the lowest order words. */ 206 ira_object_t obj1 = ALLOCNO_OBJECT (a1, 0); 207 ira_object_t obj2 = ALLOCNO_OBJECT (a2, 0); 208 209 return OBJECTS_CONFLICT_P (obj1, obj2); 210 } 211 212 /* Return TRUE if the operand constraint STR is commutative. */ 213 static bool 214 commutative_constraint_p (const char *str) 215 { 216 int curr_alt, c; 217 bool ignore_p; 218 219 for (ignore_p = false, curr_alt = 0;;) 220 { 221 c = *str; 222 if (c == '\0') 223 break; 224 str += CONSTRAINT_LEN (c, str); 225 if (c == '#' || !recog_data.alternative_enabled_p[curr_alt]) 226 ignore_p = true; 227 else if (c == ',') 228 { 229 curr_alt++; 230 ignore_p = false; 231 } 232 else if (! ignore_p) 233 { 234 /* Usually `%' is the first constraint character but the 235 documentation does not require this. */ 236 if (c == '%') 237 return true; 238 } 239 } 240 return false; 241 } 242 243 /* Return the number of the operand which should be the same in any 244 case as operand with number OP_NUM (or negative value if there is 245 no such operand). If USE_COMMUT_OP_P is TRUE, the function makes 246 temporarily commutative operand exchange before this. The function 247 takes only really possible alternatives into consideration. */ 248 static int 249 get_dup_num (int op_num, bool use_commut_op_p) 250 { 251 int curr_alt, c, original, dup; 252 bool ignore_p, commut_op_used_p; 253 const char *str; 254 rtx op; 255 256 if (op_num < 0 || recog_data.n_alternatives == 0) 257 return -1; 258 op = recog_data.operand[op_num]; 259 commut_op_used_p = true; 260 if (use_commut_op_p) 261 { 262 if (commutative_constraint_p (recog_data.constraints[op_num])) 263 op_num++; 264 else if (op_num > 0 && commutative_constraint_p (recog_data.constraints 265 [op_num - 1])) 266 op_num--; 267 else 268 commut_op_used_p = false; 269 } 270 str = recog_data.constraints[op_num]; 271 for (ignore_p = false, original = -1, curr_alt = 0;;) 272 { 273 c = *str; 274 if (c == '\0') 275 break; 276 if (c == '#' || !recog_data.alternative_enabled_p[curr_alt]) 277 ignore_p = true; 278 else if (c == ',') 279 { 280 curr_alt++; 281 ignore_p = false; 282 } 283 else if (! ignore_p) 284 switch (c) 285 { 286 case 'X': 287 return -1; 288 289 case 'm': 290 case 'o': 291 /* Accept a register which might be placed in memory. */ 292 return -1; 293 break; 294 295 case 'V': 296 case '<': 297 case '>': 298 break; 299 300 case 'p': 301 if (address_operand (op, VOIDmode)) 302 return -1; 303 break; 304 305 case 'g': 306 return -1; 307 308 case 'r': 309 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': 310 case 'h': case 'j': case 'k': case 'l': 311 case 'q': case 't': case 'u': 312 case 'v': case 'w': case 'x': case 'y': case 'z': 313 case 'A': case 'B': case 'C': case 'D': 314 case 'Q': case 'R': case 'S': case 'T': case 'U': 315 case 'W': case 'Y': case 'Z': 316 { 317 enum reg_class cl; 318 319 cl = (c == 'r' 320 ? GENERAL_REGS : REG_CLASS_FROM_CONSTRAINT (c, str)); 321 if (cl != NO_REGS) 322 return -1; 323 #ifdef EXTRA_CONSTRAINT_STR 324 else if (EXTRA_CONSTRAINT_STR (op, c, str)) 325 return -1; 326 #endif 327 break; 328 } 329 330 case '0': case '1': case '2': case '3': case '4': 331 case '5': case '6': case '7': case '8': case '9': 332 if (original != -1 && original != c) 333 return -1; 334 original = c; 335 break; 336 } 337 str += CONSTRAINT_LEN (c, str); 338 } 339 if (original == -1) 340 return -1; 341 dup = original - '0'; 342 if (use_commut_op_p) 343 { 344 if (commutative_constraint_p (recog_data.constraints[dup])) 345 dup++; 346 else if (dup > 0 347 && commutative_constraint_p (recog_data.constraints[dup -1])) 348 dup--; 349 else if (! commut_op_used_p) 350 return -1; 351 } 352 return dup; 353 } 354 355 /* Check that X is REG or SUBREG of REG. */ 356 #define REG_SUBREG_P(x) \ 357 (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x)))) 358 359 /* Return X if X is a REG, otherwise it should be SUBREG of REG and 360 the function returns the reg in this case. *OFFSET will be set to 361 0 in the first case or the regno offset in the first case. */ 362 static rtx 363 go_through_subreg (rtx x, int *offset) 364 { 365 rtx reg; 366 367 *offset = 0; 368 if (REG_P (x)) 369 return x; 370 ira_assert (GET_CODE (x) == SUBREG); 371 reg = SUBREG_REG (x); 372 ira_assert (REG_P (reg)); 373 if (REGNO (reg) < FIRST_PSEUDO_REGISTER) 374 *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg), 375 SUBREG_BYTE (x), GET_MODE (x)); 376 else 377 *offset = (SUBREG_BYTE (x) / REGMODE_NATURAL_SIZE (GET_MODE (x))); 378 return reg; 379 } 380 381 /* Process registers REG1 and REG2 in move INSN with execution 382 frequency FREQ. The function also processes the registers in a 383 potential move insn (INSN == NULL in this case) with frequency 384 FREQ. The function can modify hard register costs of the 385 corresponding allocnos or create a copy involving the corresponding 386 allocnos. The function does nothing if the both registers are hard 387 registers. When nothing is changed, the function returns 388 FALSE. */ 389 static bool 390 process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p, 391 rtx insn, int freq) 392 { 393 int allocno_preferenced_hard_regno, cost, index, offset1, offset2; 394 bool only_regs_p; 395 ira_allocno_t a; 396 reg_class_t rclass, aclass; 397 enum machine_mode mode; 398 ira_copy_t cp; 399 400 gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2)); 401 only_regs_p = REG_P (reg1) && REG_P (reg2); 402 reg1 = go_through_subreg (reg1, &offset1); 403 reg2 = go_through_subreg (reg2, &offset2); 404 /* Set up hard regno preferenced by allocno. If allocno gets the 405 hard regno the copy (or potential move) insn will be removed. */ 406 if (HARD_REGISTER_P (reg1)) 407 { 408 if (HARD_REGISTER_P (reg2)) 409 return false; 410 allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2; 411 a = ira_curr_regno_allocno_map[REGNO (reg2)]; 412 } 413 else if (HARD_REGISTER_P (reg2)) 414 { 415 allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1; 416 a = ira_curr_regno_allocno_map[REGNO (reg1)]; 417 } 418 else 419 { 420 ira_allocno_t a1 = ira_curr_regno_allocno_map[REGNO (reg1)]; 421 ira_allocno_t a2 = ira_curr_regno_allocno_map[REGNO (reg2)]; 422 423 if (!allocnos_conflict_for_copy_p (a1, a2) && offset1 == offset2) 424 { 425 cp = ira_add_allocno_copy (a1, a2, freq, constraint_p, insn, 426 ira_curr_loop_tree_node); 427 bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num); 428 return true; 429 } 430 else 431 return false; 432 } 433 434 if (! IN_RANGE (allocno_preferenced_hard_regno, 435 0, FIRST_PSEUDO_REGISTER - 1)) 436 /* Can not be tied. */ 437 return false; 438 rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno); 439 mode = ALLOCNO_MODE (a); 440 aclass = ALLOCNO_CLASS (a); 441 if (only_regs_p && insn != NULL_RTX 442 && reg_class_size[rclass] <= ira_reg_class_max_nregs [rclass][mode]) 443 /* It is already taken into account in ira-costs.c. */ 444 return false; 445 index = ira_class_hard_reg_index[aclass][allocno_preferenced_hard_regno]; 446 if (index < 0) 447 /* Can not be tied. It is not in the allocno class. */ 448 return false; 449 ira_init_register_move_cost_if_necessary (mode); 450 if (HARD_REGISTER_P (reg1)) 451 cost = ira_register_move_cost[mode][aclass][rclass] * freq; 452 else 453 cost = ira_register_move_cost[mode][rclass][aclass] * freq; 454 do 455 { 456 ira_allocate_and_set_costs 457 (&ALLOCNO_HARD_REG_COSTS (a), aclass, 458 ALLOCNO_CLASS_COST (a)); 459 ira_allocate_and_set_costs 460 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass, 0); 461 ALLOCNO_HARD_REG_COSTS (a)[index] -= cost; 462 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost; 463 if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_CLASS_COST (a)) 464 ALLOCNO_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index]; 465 a = ira_parent_or_cap_allocno (a); 466 } 467 while (a != NULL); 468 return true; 469 } 470 471 /* Process all of the output registers of the current insn which are 472 not bound (BOUND_P) and the input register REG (its operand number 473 OP_NUM) which dies in the insn as if there were a move insn between 474 them with frequency FREQ. */ 475 static void 476 process_reg_shuffles (rtx reg, int op_num, int freq, bool *bound_p) 477 { 478 int i; 479 rtx another_reg; 480 481 gcc_assert (REG_SUBREG_P (reg)); 482 for (i = 0; i < recog_data.n_operands; i++) 483 { 484 another_reg = recog_data.operand[i]; 485 486 if (!REG_SUBREG_P (another_reg) || op_num == i 487 || recog_data.operand_type[i] != OP_OUT 488 || bound_p[i]) 489 continue; 490 491 process_regs_for_copy (reg, another_reg, false, NULL_RTX, freq); 492 } 493 } 494 495 /* Process INSN and create allocno copies if necessary. For example, 496 it might be because INSN is a pseudo-register move or INSN is two 497 operand insn. */ 498 static void 499 add_insn_allocno_copies (rtx insn) 500 { 501 rtx set, operand, dup; 502 const char *str; 503 bool commut_p, bound_p[MAX_RECOG_OPERANDS]; 504 int i, j, n, freq; 505 506 freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)); 507 if (freq == 0) 508 freq = 1; 509 if ((set = single_set (insn)) != NULL_RTX 510 && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set)) 511 && ! side_effects_p (set) 512 && find_reg_note (insn, REG_DEAD, 513 REG_P (SET_SRC (set)) 514 ? SET_SRC (set) 515 : SUBREG_REG (SET_SRC (set))) != NULL_RTX) 516 { 517 process_regs_for_copy (SET_DEST (set), SET_SRC (set), 518 false, insn, freq); 519 return; 520 } 521 /* Fast check of possibility of constraint or shuffle copies. If 522 there are no dead registers, there will be no such copies. */ 523 if (! find_reg_note (insn, REG_DEAD, NULL_RTX)) 524 return; 525 extract_insn (insn); 526 for (i = 0; i < recog_data.n_operands; i++) 527 bound_p[i] = false; 528 for (i = 0; i < recog_data.n_operands; i++) 529 { 530 operand = recog_data.operand[i]; 531 if (! REG_SUBREG_P (operand)) 532 continue; 533 str = recog_data.constraints[i]; 534 while (*str == ' ' || *str == '\t') 535 str++; 536 for (j = 0, commut_p = false; j < 2; j++, commut_p = true) 537 if ((n = get_dup_num (i, commut_p)) >= 0) 538 { 539 bound_p[n] = true; 540 dup = recog_data.operand[n]; 541 if (REG_SUBREG_P (dup) 542 && find_reg_note (insn, REG_DEAD, 543 REG_P (operand) 544 ? operand 545 : SUBREG_REG (operand)) != NULL_RTX) 546 process_regs_for_copy (operand, dup, true, NULL_RTX, freq); 547 } 548 } 549 for (i = 0; i < recog_data.n_operands; i++) 550 { 551 operand = recog_data.operand[i]; 552 if (REG_SUBREG_P (operand) 553 && find_reg_note (insn, REG_DEAD, 554 REG_P (operand) 555 ? operand : SUBREG_REG (operand)) != NULL_RTX) 556 /* If an operand dies, prefer its hard register for the output 557 operands by decreasing the hard register cost or creating 558 the corresponding allocno copies. The cost will not 559 correspond to a real move insn cost, so make the frequency 560 smaller. */ 561 process_reg_shuffles (operand, i, freq < 8 ? 1 : freq / 8, bound_p); 562 } 563 } 564 565 /* Add copies originated from BB given by LOOP_TREE_NODE. */ 566 static void 567 add_copies (ira_loop_tree_node_t loop_tree_node) 568 { 569 basic_block bb; 570 rtx insn; 571 572 bb = loop_tree_node->bb; 573 if (bb == NULL) 574 return; 575 FOR_BB_INSNS (bb, insn) 576 if (NONDEBUG_INSN_P (insn)) 577 add_insn_allocno_copies (insn); 578 } 579 580 /* Propagate copies the corresponding allocnos on upper loop tree 581 level. */ 582 static void 583 propagate_copies (void) 584 { 585 ira_copy_t cp; 586 ira_copy_iterator ci; 587 ira_allocno_t a1, a2, parent_a1, parent_a2; 588 589 FOR_EACH_COPY (cp, ci) 590 { 591 a1 = cp->first; 592 a2 = cp->second; 593 if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root) 594 continue; 595 ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root)); 596 parent_a1 = ira_parent_or_cap_allocno (a1); 597 parent_a2 = ira_parent_or_cap_allocno (a2); 598 ira_assert (parent_a1 != NULL && parent_a2 != NULL); 599 if (! allocnos_conflict_for_copy_p (parent_a1, parent_a2)) 600 ira_add_allocno_copy (parent_a1, parent_a2, cp->freq, 601 cp->constraint_p, cp->insn, cp->loop_tree_node); 602 } 603 } 604 605 /* Array used to collect all conflict allocnos for given allocno. */ 606 static ira_object_t *collected_conflict_objects; 607 608 /* Build conflict vectors or bit conflict vectors (whatever is more 609 profitable) for object OBJ from the conflict table. */ 610 static void 611 build_object_conflicts (ira_object_t obj) 612 { 613 int i, px, parent_num; 614 ira_allocno_t parent_a, another_parent_a; 615 ira_object_t parent_obj; 616 ira_allocno_t a = OBJECT_ALLOCNO (obj); 617 IRA_INT_TYPE *object_conflicts; 618 minmax_set_iterator asi; 619 int parent_min, parent_max ATTRIBUTE_UNUSED; 620 621 object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)]; 622 px = 0; 623 FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts, 624 OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi) 625 { 626 ira_object_t another_obj = ira_object_id_map[i]; 627 ira_allocno_t another_a = OBJECT_ALLOCNO (obj); 628 629 ira_assert (ira_reg_classes_intersect_p 630 [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]); 631 collected_conflict_objects[px++] = another_obj; 632 } 633 if (ira_conflict_vector_profitable_p (obj, px)) 634 { 635 ira_object_t *vec; 636 ira_allocate_conflict_vec (obj, px); 637 vec = OBJECT_CONFLICT_VEC (obj); 638 memcpy (vec, collected_conflict_objects, sizeof (ira_object_t) * px); 639 vec[px] = NULL; 640 OBJECT_NUM_CONFLICTS (obj) = px; 641 } 642 else 643 { 644 int conflict_bit_vec_words_num; 645 646 OBJECT_CONFLICT_ARRAY (obj) = object_conflicts; 647 if (OBJECT_MAX (obj) < OBJECT_MIN (obj)) 648 conflict_bit_vec_words_num = 0; 649 else 650 conflict_bit_vec_words_num 651 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS) 652 / IRA_INT_BITS); 653 OBJECT_CONFLICT_ARRAY_SIZE (obj) 654 = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE); 655 } 656 657 parent_a = ira_parent_or_cap_allocno (a); 658 if (parent_a == NULL) 659 return; 660 ira_assert (ALLOCNO_CLASS (a) == ALLOCNO_CLASS (parent_a)); 661 ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a)); 662 parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj)); 663 parent_num = OBJECT_CONFLICT_ID (parent_obj); 664 parent_min = OBJECT_MIN (parent_obj); 665 parent_max = OBJECT_MAX (parent_obj); 666 FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts, 667 OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi) 668 { 669 ira_object_t another_obj = ira_object_id_map[i]; 670 ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj); 671 int another_word = OBJECT_SUBWORD (another_obj); 672 673 ira_assert (ira_reg_classes_intersect_p 674 [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]); 675 676 another_parent_a = ira_parent_or_cap_allocno (another_a); 677 if (another_parent_a == NULL) 678 continue; 679 ira_assert (ALLOCNO_NUM (another_parent_a) >= 0); 680 ira_assert (ALLOCNO_CLASS (another_a) 681 == ALLOCNO_CLASS (another_parent_a)); 682 ira_assert (ALLOCNO_NUM_OBJECTS (another_a) 683 == ALLOCNO_NUM_OBJECTS (another_parent_a)); 684 SET_MINMAX_SET_BIT (conflicts[parent_num], 685 OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a, 686 another_word)), 687 parent_min, parent_max); 688 } 689 } 690 691 /* Build conflict vectors or bit conflict vectors (whatever is more 692 profitable) of all allocnos from the conflict table. */ 693 static void 694 build_conflicts (void) 695 { 696 int i; 697 ira_allocno_t a, cap; 698 699 collected_conflict_objects 700 = (ira_object_t *) ira_allocate (sizeof (ira_object_t) 701 * ira_objects_num); 702 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--) 703 for (a = ira_regno_allocno_map[i]; 704 a != NULL; 705 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 706 { 707 int j, nregs = ALLOCNO_NUM_OBJECTS (a); 708 for (j = 0; j < nregs; j++) 709 { 710 ira_object_t obj = ALLOCNO_OBJECT (a, j); 711 build_object_conflicts (obj); 712 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap)) 713 { 714 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j); 715 gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a)); 716 build_object_conflicts (cap_obj); 717 } 718 } 719 } 720 ira_free (collected_conflict_objects); 721 } 722 723 724 725 /* Print hard reg set SET with TITLE to FILE. */ 726 static void 727 print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set) 728 { 729 int i, start; 730 731 fputs (title, file); 732 for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++) 733 { 734 if (TEST_HARD_REG_BIT (set, i)) 735 { 736 if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1)) 737 start = i; 738 } 739 if (start >= 0 740 && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i))) 741 { 742 if (start == i - 1) 743 fprintf (file, " %d", start); 744 else if (start == i - 2) 745 fprintf (file, " %d %d", start, start + 1); 746 else 747 fprintf (file, " %d-%d", start, i - 1); 748 start = -1; 749 } 750 } 751 putc ('\n', file); 752 } 753 754 static void 755 print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a) 756 { 757 HARD_REG_SET conflicting_hard_regs; 758 basic_block bb; 759 int n, i; 760 761 if (reg_p) 762 fprintf (file, ";; r%d", ALLOCNO_REGNO (a)); 763 else 764 { 765 fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a)); 766 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL) 767 fprintf (file, "b%d", bb->index); 768 else 769 fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num); 770 putc (')', file); 771 } 772 773 fputs (" conflicts:", file); 774 n = ALLOCNO_NUM_OBJECTS (a); 775 for (i = 0; i < n; i++) 776 { 777 ira_object_t obj = ALLOCNO_OBJECT (a, i); 778 ira_object_t conflict_obj; 779 ira_object_conflict_iterator oci; 780 781 if (OBJECT_CONFLICT_ARRAY (obj) == NULL) 782 continue; 783 if (n > 1) 784 fprintf (file, "\n;; subobject %d:", i); 785 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) 786 { 787 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); 788 if (reg_p) 789 fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a)); 790 else 791 { 792 fprintf (file, " a%d(r%d", ALLOCNO_NUM (conflict_a), 793 ALLOCNO_REGNO (conflict_a)); 794 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1) 795 fprintf (file, ",w%d", OBJECT_SUBWORD (conflict_obj)); 796 if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL) 797 fprintf (file, ",b%d", bb->index); 798 else 799 fprintf (file, ",l%d", 800 ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop_num); 801 putc (')', file); 802 } 803 } 804 COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)); 805 AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs); 806 AND_HARD_REG_SET (conflicting_hard_regs, 807 reg_class_contents[ALLOCNO_CLASS (a)]); 808 print_hard_reg_set (file, "\n;; total conflict hard regs:", 809 conflicting_hard_regs); 810 811 COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_CONFLICT_HARD_REGS (obj)); 812 AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs); 813 AND_HARD_REG_SET (conflicting_hard_regs, 814 reg_class_contents[ALLOCNO_CLASS (a)]); 815 print_hard_reg_set (file, ";; conflict hard regs:", 816 conflicting_hard_regs); 817 putc ('\n', file); 818 } 819 820 } 821 822 /* Print information about allocno or only regno (if REG_P) conflicts 823 to FILE. */ 824 static void 825 print_conflicts (FILE *file, bool reg_p) 826 { 827 ira_allocno_t a; 828 ira_allocno_iterator ai; 829 830 FOR_EACH_ALLOCNO (a, ai) 831 print_allocno_conflicts (file, reg_p, a); 832 } 833 834 /* Print information about allocno or only regno (if REG_P) conflicts 835 to stderr. */ 836 void 837 ira_debug_conflicts (bool reg_p) 838 { 839 print_conflicts (stderr, reg_p); 840 } 841 842 843 844 /* Entry function which builds allocno conflicts and allocno copies 845 and accumulate some allocno info on upper level regions. */ 846 void 847 ira_build_conflicts (void) 848 { 849 enum reg_class base; 850 ira_allocno_t a; 851 ira_allocno_iterator ai; 852 HARD_REG_SET temp_hard_reg_set; 853 854 if (ira_conflicts_p) 855 { 856 ira_conflicts_p = build_conflict_bit_table (); 857 if (ira_conflicts_p) 858 { 859 ira_object_t obj; 860 ira_object_iterator oi; 861 862 build_conflicts (); 863 ira_traverse_loop_tree (true, ira_loop_tree_root, NULL, add_copies); 864 /* We need finished conflict table for the subsequent call. */ 865 if (flag_ira_region == IRA_REGION_ALL 866 || flag_ira_region == IRA_REGION_MIXED) 867 propagate_copies (); 868 869 /* Now we can free memory for the conflict table (see function 870 build_object_conflicts for details). */ 871 FOR_EACH_OBJECT (obj, oi) 872 { 873 if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)]) 874 ira_free (conflicts[OBJECT_CONFLICT_ID (obj)]); 875 } 876 ira_free (conflicts); 877 } 878 } 879 base = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, ADDRESS, SCRATCH); 880 if (! targetm.class_likely_spilled_p (base)) 881 CLEAR_HARD_REG_SET (temp_hard_reg_set); 882 else 883 { 884 COPY_HARD_REG_SET (temp_hard_reg_set, reg_class_contents[base]); 885 AND_COMPL_HARD_REG_SET (temp_hard_reg_set, ira_no_alloc_regs); 886 AND_HARD_REG_SET (temp_hard_reg_set, call_used_reg_set); 887 } 888 FOR_EACH_ALLOCNO (a, ai) 889 { 890 int i, n = ALLOCNO_NUM_OBJECTS (a); 891 892 for (i = 0; i < n; i++) 893 { 894 ira_object_t obj = ALLOCNO_OBJECT (a, i); 895 reg_attrs *attrs = REG_ATTRS (regno_reg_rtx [ALLOCNO_REGNO (a)]); 896 tree decl; 897 898 if ((! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0) 899 /* For debugging purposes don't put user defined variables in 900 callee-clobbered registers. */ 901 || (optimize == 0 902 && attrs != NULL 903 && (decl = attrs->decl) != NULL 904 && VAR_OR_FUNCTION_DECL_P (decl) 905 && ! DECL_ARTIFICIAL (decl))) 906 { 907 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 908 call_used_reg_set); 909 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), 910 call_used_reg_set); 911 } 912 else if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0) 913 { 914 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 915 no_caller_save_reg_set); 916 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 917 temp_hard_reg_set); 918 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), 919 no_caller_save_reg_set); 920 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), 921 temp_hard_reg_set); 922 } 923 924 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0) 925 { 926 int regno; 927 928 /* Allocnos bigger than the saved part of call saved 929 regs must conflict with them. */ 930 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) 931 if (!TEST_HARD_REG_BIT (call_used_reg_set, regno) 932 && HARD_REGNO_CALL_PART_CLOBBERED (regno, 933 obj->allocno->mode)) 934 { 935 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), regno); 936 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 937 regno); 938 } 939 } 940 } 941 } 942 if (optimize && ira_conflicts_p 943 && internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 944 print_conflicts (ira_dump_file, false); 945 } 946