1 /* Building internal representation for IRA. 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 "rtl.h" 27 #include "tm_p.h" 28 #include "target.h" 29 #include "regs.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 "output.h" 39 #include "reload.h" 40 #include "sparseset.h" 41 #include "ira-int.h" 42 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */ 43 44 static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx, 45 ira_loop_tree_node_t); 46 47 /* The root of the loop tree corresponding to the all function. */ 48 ira_loop_tree_node_t ira_loop_tree_root; 49 50 /* Height of the loop tree. */ 51 int ira_loop_tree_height; 52 53 /* All nodes representing basic blocks are referred through the 54 following array. We can not use basic block member `aux' for this 55 because it is used for insertion of insns on edges. */ 56 ira_loop_tree_node_t ira_bb_nodes; 57 58 /* All nodes representing loops are referred through the following 59 array. */ 60 ira_loop_tree_node_t ira_loop_nodes; 61 62 /* Map regno -> allocnos with given regno (see comments for 63 allocno member `next_regno_allocno'). */ 64 ira_allocno_t *ira_regno_allocno_map; 65 66 /* Array of references to all allocnos. The order number of the 67 allocno corresponds to the index in the array. Removed allocnos 68 have NULL element value. */ 69 ira_allocno_t *ira_allocnos; 70 71 /* Sizes of the previous array. */ 72 int ira_allocnos_num; 73 74 /* Count of conflict record structures we've created, used when creating 75 a new conflict id. */ 76 int ira_objects_num; 77 78 /* Map a conflict id to its conflict record. */ 79 ira_object_t *ira_object_id_map; 80 81 /* Array of references to all copies. The order number of the copy 82 corresponds to the index in the array. Removed copies have NULL 83 element value. */ 84 ira_copy_t *ira_copies; 85 86 /* Size of the previous array. */ 87 int ira_copies_num; 88 89 90 91 /* LAST_BASIC_BLOCK before generating additional insns because of live 92 range splitting. Emitting insns on a critical edge creates a new 93 basic block. */ 94 static int last_basic_block_before_change; 95 96 /* Initialize some members in loop tree node NODE. Use LOOP_NUM for 97 the member loop_num. */ 98 static void 99 init_loop_tree_node (struct ira_loop_tree_node *node, int loop_num) 100 { 101 int max_regno = max_reg_num (); 102 103 node->regno_allocno_map 104 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno); 105 memset (node->regno_allocno_map, 0, sizeof (ira_allocno_t) * max_regno); 106 memset (node->reg_pressure, 0, sizeof (node->reg_pressure)); 107 node->all_allocnos = ira_allocate_bitmap (); 108 node->modified_regnos = ira_allocate_bitmap (); 109 node->border_allocnos = ira_allocate_bitmap (); 110 node->local_copies = ira_allocate_bitmap (); 111 node->loop_num = loop_num; 112 node->children = NULL; 113 node->subloops = NULL; 114 } 115 116 117 /* The following function allocates the loop tree nodes. If 118 CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except 119 the root which corresponds the all function) will be not allocated 120 but nodes will still be allocated for basic blocks. */ 121 static void 122 create_loop_tree_nodes (void) 123 { 124 unsigned int i, j; 125 bool skip_p; 126 edge_iterator ei; 127 edge e; 128 VEC (edge, heap) *edges; 129 loop_p loop; 130 131 ira_bb_nodes 132 = ((struct ira_loop_tree_node *) 133 ira_allocate (sizeof (struct ira_loop_tree_node) * last_basic_block)); 134 last_basic_block_before_change = last_basic_block; 135 for (i = 0; i < (unsigned int) last_basic_block; i++) 136 { 137 ira_bb_nodes[i].regno_allocno_map = NULL; 138 memset (ira_bb_nodes[i].reg_pressure, 0, 139 sizeof (ira_bb_nodes[i].reg_pressure)); 140 ira_bb_nodes[i].all_allocnos = NULL; 141 ira_bb_nodes[i].modified_regnos = NULL; 142 ira_bb_nodes[i].border_allocnos = NULL; 143 ira_bb_nodes[i].local_copies = NULL; 144 } 145 if (current_loops == NULL) 146 { 147 ira_loop_nodes = ((struct ira_loop_tree_node *) 148 ira_allocate (sizeof (struct ira_loop_tree_node))); 149 init_loop_tree_node (ira_loop_nodes, 0); 150 return; 151 } 152 ira_loop_nodes = ((struct ira_loop_tree_node *) 153 ira_allocate (sizeof (struct ira_loop_tree_node) 154 * VEC_length (loop_p, ira_loops.larray))); 155 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop) 156 { 157 if (loop != ira_loops.tree_root) 158 { 159 ira_loop_nodes[i].regno_allocno_map = NULL; 160 skip_p = false; 161 FOR_EACH_EDGE (e, ei, loop->header->preds) 162 if (e->src != loop->latch 163 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)) 164 { 165 skip_p = true; 166 break; 167 } 168 if (skip_p) 169 continue; 170 edges = get_loop_exit_edges (loop); 171 FOR_EACH_VEC_ELT (edge, edges, j, e) 172 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)) 173 { 174 skip_p = true; 175 break; 176 } 177 VEC_free (edge, heap, edges); 178 if (skip_p) 179 continue; 180 } 181 init_loop_tree_node (&ira_loop_nodes[i], loop->num); 182 } 183 } 184 185 /* The function returns TRUE if there are more one allocation 186 region. */ 187 static bool 188 more_one_region_p (void) 189 { 190 unsigned int i; 191 loop_p loop; 192 193 if (current_loops != NULL) 194 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop) 195 if (ira_loop_nodes[i].regno_allocno_map != NULL 196 && ira_loop_tree_root != &ira_loop_nodes[i]) 197 return true; 198 return false; 199 } 200 201 /* Free the loop tree node of a loop. */ 202 static void 203 finish_loop_tree_node (ira_loop_tree_node_t loop) 204 { 205 if (loop->regno_allocno_map != NULL) 206 { 207 ira_assert (loop->bb == NULL); 208 ira_free_bitmap (loop->local_copies); 209 ira_free_bitmap (loop->border_allocnos); 210 ira_free_bitmap (loop->modified_regnos); 211 ira_free_bitmap (loop->all_allocnos); 212 ira_free (loop->regno_allocno_map); 213 loop->regno_allocno_map = NULL; 214 } 215 } 216 217 /* Free the loop tree nodes. */ 218 static void 219 finish_loop_tree_nodes (void) 220 { 221 unsigned int i; 222 loop_p loop; 223 224 if (current_loops == NULL) 225 finish_loop_tree_node (&ira_loop_nodes[0]); 226 else 227 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop) 228 finish_loop_tree_node (&ira_loop_nodes[i]); 229 ira_free (ira_loop_nodes); 230 for (i = 0; i < (unsigned int) last_basic_block_before_change; i++) 231 { 232 if (ira_bb_nodes[i].local_copies != NULL) 233 ira_free_bitmap (ira_bb_nodes[i].local_copies); 234 if (ira_bb_nodes[i].border_allocnos != NULL) 235 ira_free_bitmap (ira_bb_nodes[i].border_allocnos); 236 if (ira_bb_nodes[i].modified_regnos != NULL) 237 ira_free_bitmap (ira_bb_nodes[i].modified_regnos); 238 if (ira_bb_nodes[i].all_allocnos != NULL) 239 ira_free_bitmap (ira_bb_nodes[i].all_allocnos); 240 if (ira_bb_nodes[i].regno_allocno_map != NULL) 241 ira_free (ira_bb_nodes[i].regno_allocno_map); 242 } 243 ira_free (ira_bb_nodes); 244 } 245 246 247 248 /* The following recursive function adds LOOP to the loop tree 249 hierarchy. LOOP is added only once. If LOOP is NULL we adding 250 loop designating the whole function when CFG loops are not 251 built. */ 252 static void 253 add_loop_to_tree (struct loop *loop) 254 { 255 int loop_num; 256 struct loop *parent; 257 ira_loop_tree_node_t loop_node, parent_node; 258 259 /* We can not use loop node access macros here because of potential 260 checking and because the nodes are not initialized enough 261 yet. */ 262 if (loop != NULL && loop_outer (loop) != NULL) 263 add_loop_to_tree (loop_outer (loop)); 264 loop_num = loop != NULL ? loop->num : 0; 265 if (ira_loop_nodes[loop_num].regno_allocno_map != NULL 266 && ira_loop_nodes[loop_num].children == NULL) 267 { 268 /* We have not added loop node to the tree yet. */ 269 loop_node = &ira_loop_nodes[loop_num]; 270 loop_node->loop = loop; 271 loop_node->bb = NULL; 272 if (loop == NULL) 273 parent = NULL; 274 else 275 { 276 for (parent = loop_outer (loop); 277 parent != NULL; 278 parent = loop_outer (parent)) 279 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL) 280 break; 281 } 282 if (parent == NULL) 283 { 284 loop_node->next = NULL; 285 loop_node->subloop_next = NULL; 286 loop_node->parent = NULL; 287 } 288 else 289 { 290 parent_node = &ira_loop_nodes[parent->num]; 291 loop_node->next = parent_node->children; 292 parent_node->children = loop_node; 293 loop_node->subloop_next = parent_node->subloops; 294 parent_node->subloops = loop_node; 295 loop_node->parent = parent_node; 296 } 297 } 298 } 299 300 /* The following recursive function sets up levels of nodes of the 301 tree given its root LOOP_NODE. The enumeration starts with LEVEL. 302 The function returns maximal value of level in the tree + 1. */ 303 static int 304 setup_loop_tree_level (ira_loop_tree_node_t loop_node, int level) 305 { 306 int height, max_height; 307 ira_loop_tree_node_t subloop_node; 308 309 ira_assert (loop_node->bb == NULL); 310 loop_node->level = level; 311 max_height = level + 1; 312 for (subloop_node = loop_node->subloops; 313 subloop_node != NULL; 314 subloop_node = subloop_node->subloop_next) 315 { 316 ira_assert (subloop_node->bb == NULL); 317 height = setup_loop_tree_level (subloop_node, level + 1); 318 if (height > max_height) 319 max_height = height; 320 } 321 return max_height; 322 } 323 324 /* Create the loop tree. The algorithm is designed to provide correct 325 order of loops (they are ordered by their last loop BB) and basic 326 blocks in the chain formed by member next. */ 327 static void 328 form_loop_tree (void) 329 { 330 basic_block bb; 331 struct loop *parent; 332 ira_loop_tree_node_t bb_node, loop_node; 333 334 /* We can not use loop/bb node access macros because of potential 335 checking and because the nodes are not initialized enough 336 yet. */ 337 FOR_EACH_BB (bb) 338 { 339 bb_node = &ira_bb_nodes[bb->index]; 340 bb_node->bb = bb; 341 bb_node->loop = NULL; 342 bb_node->subloops = NULL; 343 bb_node->children = NULL; 344 bb_node->subloop_next = NULL; 345 bb_node->next = NULL; 346 if (current_loops == NULL) 347 parent = NULL; 348 else 349 { 350 for (parent = bb->loop_father; 351 parent != NULL; 352 parent = loop_outer (parent)) 353 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL) 354 break; 355 } 356 add_loop_to_tree (parent); 357 loop_node = &ira_loop_nodes[parent == NULL ? 0 : parent->num]; 358 bb_node->next = loop_node->children; 359 bb_node->parent = loop_node; 360 loop_node->children = bb_node; 361 } 362 ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (0); 363 ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0); 364 ira_assert (ira_loop_tree_root->regno_allocno_map != NULL); 365 } 366 367 368 369 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop 370 tree nodes. */ 371 static void 372 rebuild_regno_allocno_maps (void) 373 { 374 unsigned int l; 375 int max_regno, regno; 376 ira_allocno_t a; 377 ira_loop_tree_node_t loop_tree_node; 378 loop_p loop; 379 ira_allocno_iterator ai; 380 381 ira_assert (current_loops != NULL); 382 max_regno = max_reg_num (); 383 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, l, loop) 384 if (ira_loop_nodes[l].regno_allocno_map != NULL) 385 { 386 ira_free (ira_loop_nodes[l].regno_allocno_map); 387 ira_loop_nodes[l].regno_allocno_map 388 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) 389 * max_regno); 390 memset (ira_loop_nodes[l].regno_allocno_map, 0, 391 sizeof (ira_allocno_t) * max_regno); 392 } 393 ira_free (ira_regno_allocno_map); 394 ira_regno_allocno_map 395 = (ira_allocno_t *) ira_allocate (max_regno * sizeof (ira_allocno_t)); 396 memset (ira_regno_allocno_map, 0, max_regno * sizeof (ira_allocno_t)); 397 FOR_EACH_ALLOCNO (a, ai) 398 { 399 if (ALLOCNO_CAP_MEMBER (a) != NULL) 400 /* Caps are not in the regno allocno maps. */ 401 continue; 402 regno = ALLOCNO_REGNO (a); 403 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a); 404 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno]; 405 ira_regno_allocno_map[regno] = a; 406 if (loop_tree_node->regno_allocno_map[regno] == NULL) 407 /* Remember that we can create temporary allocnos to break 408 cycles in register shuffle. */ 409 loop_tree_node->regno_allocno_map[regno] = a; 410 } 411 } 412 413 414 /* Pools for allocnos, allocno live ranges and objects. */ 415 static alloc_pool allocno_pool, live_range_pool, object_pool; 416 417 /* Vec containing references to all created allocnos. It is a 418 container of array allocnos. */ 419 static VEC(ira_allocno_t,heap) *allocno_vec; 420 421 /* Vec containing references to all created ira_objects. It is a 422 container of ira_object_id_map. */ 423 static VEC(ira_object_t,heap) *ira_object_id_map_vec; 424 425 /* Initialize data concerning allocnos. */ 426 static void 427 initiate_allocnos (void) 428 { 429 live_range_pool 430 = create_alloc_pool ("live ranges", 431 sizeof (struct live_range), 100); 432 allocno_pool 433 = create_alloc_pool ("allocnos", sizeof (struct ira_allocno), 100); 434 object_pool 435 = create_alloc_pool ("objects", sizeof (struct ira_object), 100); 436 allocno_vec = VEC_alloc (ira_allocno_t, heap, max_reg_num () * 2); 437 ira_allocnos = NULL; 438 ira_allocnos_num = 0; 439 ira_objects_num = 0; 440 ira_object_id_map_vec 441 = VEC_alloc (ira_object_t, heap, max_reg_num () * 2); 442 ira_object_id_map = NULL; 443 ira_regno_allocno_map 444 = (ira_allocno_t *) ira_allocate (max_reg_num () 445 * sizeof (ira_allocno_t)); 446 memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t)); 447 } 448 449 /* Create and return an object corresponding to a new allocno A. */ 450 static ira_object_t 451 ira_create_object (ira_allocno_t a, int subword) 452 { 453 enum reg_class aclass = ALLOCNO_CLASS (a); 454 ira_object_t obj = (ira_object_t) pool_alloc (object_pool); 455 456 OBJECT_ALLOCNO (obj) = a; 457 OBJECT_SUBWORD (obj) = subword; 458 OBJECT_CONFLICT_ID (obj) = ira_objects_num; 459 OBJECT_CONFLICT_VEC_P (obj) = false; 460 OBJECT_CONFLICT_ARRAY (obj) = NULL; 461 OBJECT_NUM_CONFLICTS (obj) = 0; 462 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs); 463 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs); 464 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), 465 reg_class_contents[aclass]); 466 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 467 reg_class_contents[aclass]); 468 OBJECT_MIN (obj) = INT_MAX; 469 OBJECT_MAX (obj) = -1; 470 OBJECT_LIVE_RANGES (obj) = NULL; 471 472 VEC_safe_push (ira_object_t, heap, ira_object_id_map_vec, obj); 473 ira_object_id_map 474 = VEC_address (ira_object_t, ira_object_id_map_vec); 475 ira_objects_num = VEC_length (ira_object_t, ira_object_id_map_vec); 476 477 return obj; 478 } 479 480 /* Create and return the allocno corresponding to REGNO in 481 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the 482 same regno if CAP_P is FALSE. */ 483 ira_allocno_t 484 ira_create_allocno (int regno, bool cap_p, 485 ira_loop_tree_node_t loop_tree_node) 486 { 487 ira_allocno_t a; 488 489 a = (ira_allocno_t) pool_alloc (allocno_pool); 490 ALLOCNO_REGNO (a) = regno; 491 ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node; 492 if (! cap_p) 493 { 494 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno]; 495 ira_regno_allocno_map[regno] = a; 496 if (loop_tree_node->regno_allocno_map[regno] == NULL) 497 /* Remember that we can create temporary allocnos to break 498 cycles in register shuffle on region borders (see 499 ira-emit.c). */ 500 loop_tree_node->regno_allocno_map[regno] = a; 501 } 502 ALLOCNO_CAP (a) = NULL; 503 ALLOCNO_CAP_MEMBER (a) = NULL; 504 ALLOCNO_NUM (a) = ira_allocnos_num; 505 bitmap_set_bit (loop_tree_node->all_allocnos, ALLOCNO_NUM (a)); 506 ALLOCNO_NREFS (a) = 0; 507 ALLOCNO_FREQ (a) = 0; 508 ALLOCNO_HARD_REGNO (a) = -1; 509 ALLOCNO_CALL_FREQ (a) = 0; 510 ALLOCNO_CALLS_CROSSED_NUM (a) = 0; 511 #ifdef STACK_REGS 512 ALLOCNO_NO_STACK_REG_P (a) = false; 513 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false; 514 #endif 515 ALLOCNO_DONT_REASSIGN_P (a) = false; 516 ALLOCNO_BAD_SPILL_P (a) = false; 517 ALLOCNO_ASSIGNED_P (a) = false; 518 ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno)); 519 ALLOCNO_COPIES (a) = NULL; 520 ALLOCNO_HARD_REG_COSTS (a) = NULL; 521 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL; 522 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL; 523 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL; 524 ALLOCNO_CLASS (a) = NO_REGS; 525 ALLOCNO_UPDATED_CLASS_COST (a) = 0; 526 ALLOCNO_CLASS_COST (a) = 0; 527 ALLOCNO_MEMORY_COST (a) = 0; 528 ALLOCNO_UPDATED_MEMORY_COST (a) = 0; 529 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0; 530 ALLOCNO_NUM_OBJECTS (a) = 0; 531 532 ALLOCNO_ADD_DATA (a) = NULL; 533 VEC_safe_push (ira_allocno_t, heap, allocno_vec, a); 534 ira_allocnos = VEC_address (ira_allocno_t, allocno_vec); 535 ira_allocnos_num = VEC_length (ira_allocno_t, allocno_vec); 536 537 return a; 538 } 539 540 /* Set up register class for A and update its conflict hard 541 registers. */ 542 void 543 ira_set_allocno_class (ira_allocno_t a, enum reg_class aclass) 544 { 545 ira_allocno_object_iterator oi; 546 ira_object_t obj; 547 548 ALLOCNO_CLASS (a) = aclass; 549 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi) 550 { 551 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), 552 reg_class_contents[aclass]); 553 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 554 reg_class_contents[aclass]); 555 } 556 } 557 558 /* Determine the number of objects we should associate with allocno A 559 and allocate them. */ 560 void 561 ira_create_allocno_objects (ira_allocno_t a) 562 { 563 enum machine_mode mode = ALLOCNO_MODE (a); 564 enum reg_class aclass = ALLOCNO_CLASS (a); 565 int n = ira_reg_class_max_nregs[aclass][mode]; 566 int i; 567 568 if (GET_MODE_SIZE (mode) != 2 * UNITS_PER_WORD || n != 2) 569 n = 1; 570 571 ALLOCNO_NUM_OBJECTS (a) = n; 572 for (i = 0; i < n; i++) 573 ALLOCNO_OBJECT (a, i) = ira_create_object (a, i); 574 } 575 576 /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the 577 ALLOCNO_OBJECT structures. This must be called after the allocno 578 classes are known. */ 579 static void 580 create_allocno_objects (void) 581 { 582 ira_allocno_t a; 583 ira_allocno_iterator ai; 584 585 FOR_EACH_ALLOCNO (a, ai) 586 ira_create_allocno_objects (a); 587 } 588 589 /* Merge hard register conflict information for all objects associated with 590 allocno TO into the corresponding objects associated with FROM. 591 If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS. */ 592 static void 593 merge_hard_reg_conflicts (ira_allocno_t from, ira_allocno_t to, 594 bool total_only) 595 { 596 int i; 597 gcc_assert (ALLOCNO_NUM_OBJECTS (to) == ALLOCNO_NUM_OBJECTS (from)); 598 for (i = 0; i < ALLOCNO_NUM_OBJECTS (to); i++) 599 { 600 ira_object_t from_obj = ALLOCNO_OBJECT (from, i); 601 ira_object_t to_obj = ALLOCNO_OBJECT (to, i); 602 603 if (!total_only) 604 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj), 605 OBJECT_CONFLICT_HARD_REGS (from_obj)); 606 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj), 607 OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj)); 608 } 609 #ifdef STACK_REGS 610 if (!total_only && ALLOCNO_NO_STACK_REG_P (from)) 611 ALLOCNO_NO_STACK_REG_P (to) = true; 612 if (ALLOCNO_TOTAL_NO_STACK_REG_P (from)) 613 ALLOCNO_TOTAL_NO_STACK_REG_P (to) = true; 614 #endif 615 } 616 617 /* Update hard register conflict information for all objects associated with 618 A to include the regs in SET. */ 619 void 620 ior_hard_reg_conflicts (ira_allocno_t a, HARD_REG_SET *set) 621 { 622 ira_allocno_object_iterator i; 623 ira_object_t obj; 624 625 FOR_EACH_ALLOCNO_OBJECT (a, obj, i) 626 { 627 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), *set); 628 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), *set); 629 } 630 } 631 632 /* Return TRUE if a conflict vector with NUM elements is more 633 profitable than a conflict bit vector for OBJ. */ 634 bool 635 ira_conflict_vector_profitable_p (ira_object_t obj, int num) 636 { 637 int nw; 638 int max = OBJECT_MAX (obj); 639 int min = OBJECT_MIN (obj); 640 641 if (max < min) 642 /* We prefer a bit vector in such case because it does not result 643 in allocation. */ 644 return false; 645 646 nw = (max - min + IRA_INT_BITS) / IRA_INT_BITS; 647 return (2 * sizeof (ira_object_t) * (num + 1) 648 < 3 * nw * sizeof (IRA_INT_TYPE)); 649 } 650 651 /* Allocates and initialize the conflict vector of OBJ for NUM 652 conflicting objects. */ 653 void 654 ira_allocate_conflict_vec (ira_object_t obj, int num) 655 { 656 int size; 657 ira_object_t *vec; 658 659 ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL); 660 num++; /* for NULL end marker */ 661 size = sizeof (ira_object_t) * num; 662 OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size); 663 vec = (ira_object_t *) OBJECT_CONFLICT_ARRAY (obj); 664 vec[0] = NULL; 665 OBJECT_NUM_CONFLICTS (obj) = 0; 666 OBJECT_CONFLICT_ARRAY_SIZE (obj) = size; 667 OBJECT_CONFLICT_VEC_P (obj) = true; 668 } 669 670 /* Allocate and initialize the conflict bit vector of OBJ. */ 671 static void 672 allocate_conflict_bit_vec (ira_object_t obj) 673 { 674 unsigned int size; 675 676 ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL); 677 size = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS) 678 / IRA_INT_BITS * sizeof (IRA_INT_TYPE)); 679 OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size); 680 memset (OBJECT_CONFLICT_ARRAY (obj), 0, size); 681 OBJECT_CONFLICT_ARRAY_SIZE (obj) = size; 682 OBJECT_CONFLICT_VEC_P (obj) = false; 683 } 684 685 /* Allocate and initialize the conflict vector or conflict bit vector 686 of OBJ for NUM conflicting allocnos whatever is more profitable. */ 687 void 688 ira_allocate_object_conflicts (ira_object_t obj, int num) 689 { 690 if (ira_conflict_vector_profitable_p (obj, num)) 691 ira_allocate_conflict_vec (obj, num); 692 else 693 allocate_conflict_bit_vec (obj); 694 } 695 696 /* Add OBJ2 to the conflicts of OBJ1. */ 697 static void 698 add_to_conflicts (ira_object_t obj1, ira_object_t obj2) 699 { 700 int num; 701 unsigned int size; 702 703 if (OBJECT_CONFLICT_VEC_P (obj1)) 704 { 705 ira_object_t *vec = OBJECT_CONFLICT_VEC (obj1); 706 int curr_num = OBJECT_NUM_CONFLICTS (obj1); 707 num = curr_num + 2; 708 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < num * sizeof (ira_object_t)) 709 { 710 ira_object_t *newvec; 711 size = (3 * num / 2 + 1) * sizeof (ira_allocno_t); 712 newvec = (ira_object_t *) ira_allocate (size); 713 memcpy (newvec, vec, curr_num * sizeof (ira_object_t)); 714 ira_free (vec); 715 vec = newvec; 716 OBJECT_CONFLICT_ARRAY (obj1) = vec; 717 OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size; 718 } 719 vec[num - 2] = obj2; 720 vec[num - 1] = NULL; 721 OBJECT_NUM_CONFLICTS (obj1)++; 722 } 723 else 724 { 725 int nw, added_head_nw, id; 726 IRA_INT_TYPE *vec = OBJECT_CONFLICT_BITVEC (obj1); 727 728 id = OBJECT_CONFLICT_ID (obj2); 729 if (OBJECT_MIN (obj1) > id) 730 { 731 /* Expand head of the bit vector. */ 732 added_head_nw = (OBJECT_MIN (obj1) - id - 1) / IRA_INT_BITS + 1; 733 nw = (OBJECT_MAX (obj1) - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1; 734 size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE); 735 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) >= size) 736 { 737 memmove ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE), 738 vec, nw * sizeof (IRA_INT_TYPE)); 739 memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE)); 740 } 741 else 742 { 743 size 744 = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE); 745 vec = (IRA_INT_TYPE *) ira_allocate (size); 746 memcpy ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE), 747 OBJECT_CONFLICT_ARRAY (obj1), nw * sizeof (IRA_INT_TYPE)); 748 memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE)); 749 memset ((char *) vec 750 + (nw + added_head_nw) * sizeof (IRA_INT_TYPE), 751 0, size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE)); 752 ira_free (OBJECT_CONFLICT_ARRAY (obj1)); 753 OBJECT_CONFLICT_ARRAY (obj1) = vec; 754 OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size; 755 } 756 OBJECT_MIN (obj1) -= added_head_nw * IRA_INT_BITS; 757 } 758 else if (OBJECT_MAX (obj1) < id) 759 { 760 nw = (id - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1; 761 size = nw * sizeof (IRA_INT_TYPE); 762 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < size) 763 { 764 /* Expand tail of the bit vector. */ 765 size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE); 766 vec = (IRA_INT_TYPE *) ira_allocate (size); 767 memcpy (vec, OBJECT_CONFLICT_ARRAY (obj1), OBJECT_CONFLICT_ARRAY_SIZE (obj1)); 768 memset ((char *) vec + OBJECT_CONFLICT_ARRAY_SIZE (obj1), 769 0, size - OBJECT_CONFLICT_ARRAY_SIZE (obj1)); 770 ira_free (OBJECT_CONFLICT_ARRAY (obj1)); 771 OBJECT_CONFLICT_ARRAY (obj1) = vec; 772 OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size; 773 } 774 OBJECT_MAX (obj1) = id; 775 } 776 SET_MINMAX_SET_BIT (vec, id, OBJECT_MIN (obj1), OBJECT_MAX (obj1)); 777 } 778 } 779 780 /* Add OBJ1 to the conflicts of OBJ2 and vice versa. */ 781 static void 782 ira_add_conflict (ira_object_t obj1, ira_object_t obj2) 783 { 784 add_to_conflicts (obj1, obj2); 785 add_to_conflicts (obj2, obj1); 786 } 787 788 /* Clear all conflicts of OBJ. */ 789 static void 790 clear_conflicts (ira_object_t obj) 791 { 792 if (OBJECT_CONFLICT_VEC_P (obj)) 793 { 794 OBJECT_NUM_CONFLICTS (obj) = 0; 795 OBJECT_CONFLICT_VEC (obj)[0] = NULL; 796 } 797 else if (OBJECT_CONFLICT_ARRAY_SIZE (obj) != 0) 798 { 799 int nw; 800 801 nw = (OBJECT_MAX (obj) - OBJECT_MIN (obj)) / IRA_INT_BITS + 1; 802 memset (OBJECT_CONFLICT_BITVEC (obj), 0, nw * sizeof (IRA_INT_TYPE)); 803 } 804 } 805 806 /* The array used to find duplications in conflict vectors of 807 allocnos. */ 808 static int *conflict_check; 809 810 /* The value used to mark allocation presence in conflict vector of 811 the current allocno. */ 812 static int curr_conflict_check_tick; 813 814 /* Remove duplications in conflict vector of OBJ. */ 815 static void 816 compress_conflict_vec (ira_object_t obj) 817 { 818 ira_object_t *vec, conflict_obj; 819 int i, j; 820 821 ira_assert (OBJECT_CONFLICT_VEC_P (obj)); 822 vec = OBJECT_CONFLICT_VEC (obj); 823 curr_conflict_check_tick++; 824 for (i = j = 0; (conflict_obj = vec[i]) != NULL; i++) 825 { 826 int id = OBJECT_CONFLICT_ID (conflict_obj); 827 if (conflict_check[id] != curr_conflict_check_tick) 828 { 829 conflict_check[id] = curr_conflict_check_tick; 830 vec[j++] = conflict_obj; 831 } 832 } 833 OBJECT_NUM_CONFLICTS (obj) = j; 834 vec[j] = NULL; 835 } 836 837 /* Remove duplications in conflict vectors of all allocnos. */ 838 static void 839 compress_conflict_vecs (void) 840 { 841 ira_object_t obj; 842 ira_object_iterator oi; 843 844 conflict_check = (int *) ira_allocate (sizeof (int) * ira_objects_num); 845 memset (conflict_check, 0, sizeof (int) * ira_objects_num); 846 curr_conflict_check_tick = 0; 847 FOR_EACH_OBJECT (obj, oi) 848 { 849 if (OBJECT_CONFLICT_VEC_P (obj)) 850 compress_conflict_vec (obj); 851 } 852 ira_free (conflict_check); 853 } 854 855 /* This recursive function outputs allocno A and if it is a cap the 856 function outputs its members. */ 857 void 858 ira_print_expanded_allocno (ira_allocno_t a) 859 { 860 basic_block bb; 861 862 fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a)); 863 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL) 864 fprintf (ira_dump_file, ",b%d", bb->index); 865 else 866 fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num); 867 if (ALLOCNO_CAP_MEMBER (a) != NULL) 868 { 869 fprintf (ira_dump_file, ":"); 870 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a)); 871 } 872 fprintf (ira_dump_file, ")"); 873 } 874 875 /* Create and return the cap representing allocno A in the 876 parent loop. */ 877 static ira_allocno_t 878 create_cap_allocno (ira_allocno_t a) 879 { 880 ira_allocno_t cap; 881 ira_loop_tree_node_t parent; 882 enum reg_class aclass; 883 884 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent; 885 cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent); 886 ALLOCNO_MODE (cap) = ALLOCNO_MODE (a); 887 aclass = ALLOCNO_CLASS (a); 888 ira_set_allocno_class (cap, aclass); 889 ira_create_allocno_objects (cap); 890 ALLOCNO_CAP_MEMBER (cap) = a; 891 ALLOCNO_CAP (a) = cap; 892 ALLOCNO_CLASS_COST (cap) = ALLOCNO_CLASS_COST (a); 893 ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a); 894 ira_allocate_and_copy_costs 895 (&ALLOCNO_HARD_REG_COSTS (cap), aclass, ALLOCNO_HARD_REG_COSTS (a)); 896 ira_allocate_and_copy_costs 897 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), aclass, 898 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)); 899 ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a); 900 ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a); 901 ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a); 902 ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a); 903 904 merge_hard_reg_conflicts (a, cap, false); 905 906 ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a); 907 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 908 { 909 fprintf (ira_dump_file, " Creating cap "); 910 ira_print_expanded_allocno (cap); 911 fprintf (ira_dump_file, "\n"); 912 } 913 return cap; 914 } 915 916 /* Create and return a live range for OBJECT with given attributes. */ 917 live_range_t 918 ira_create_live_range (ira_object_t obj, int start, int finish, 919 live_range_t next) 920 { 921 live_range_t p; 922 923 p = (live_range_t) pool_alloc (live_range_pool); 924 p->object = obj; 925 p->start = start; 926 p->finish = finish; 927 p->next = next; 928 return p; 929 } 930 931 /* Create a new live range for OBJECT and queue it at the head of its 932 live range list. */ 933 void 934 ira_add_live_range_to_object (ira_object_t object, int start, int finish) 935 { 936 live_range_t p; 937 p = ira_create_live_range (object, start, finish, 938 OBJECT_LIVE_RANGES (object)); 939 OBJECT_LIVE_RANGES (object) = p; 940 } 941 942 /* Copy allocno live range R and return the result. */ 943 static live_range_t 944 copy_live_range (live_range_t r) 945 { 946 live_range_t p; 947 948 p = (live_range_t) pool_alloc (live_range_pool); 949 *p = *r; 950 return p; 951 } 952 953 /* Copy allocno live range list given by its head R and return the 954 result. */ 955 live_range_t 956 ira_copy_live_range_list (live_range_t r) 957 { 958 live_range_t p, first, last; 959 960 if (r == NULL) 961 return NULL; 962 for (first = last = NULL; r != NULL; r = r->next) 963 { 964 p = copy_live_range (r); 965 if (first == NULL) 966 first = p; 967 else 968 last->next = p; 969 last = p; 970 } 971 return first; 972 } 973 974 /* Merge ranges R1 and R2 and returns the result. The function 975 maintains the order of ranges and tries to minimize number of the 976 result ranges. */ 977 live_range_t 978 ira_merge_live_ranges (live_range_t r1, live_range_t r2) 979 { 980 live_range_t first, last, temp; 981 982 if (r1 == NULL) 983 return r2; 984 if (r2 == NULL) 985 return r1; 986 for (first = last = NULL; r1 != NULL && r2 != NULL;) 987 { 988 if (r1->start < r2->start) 989 { 990 temp = r1; 991 r1 = r2; 992 r2 = temp; 993 } 994 if (r1->start <= r2->finish + 1) 995 { 996 /* Intersected ranges: merge r1 and r2 into r1. */ 997 r1->start = r2->start; 998 if (r1->finish < r2->finish) 999 r1->finish = r2->finish; 1000 temp = r2; 1001 r2 = r2->next; 1002 ira_finish_live_range (temp); 1003 if (r2 == NULL) 1004 { 1005 /* To try to merge with subsequent ranges in r1. */ 1006 r2 = r1->next; 1007 r1->next = NULL; 1008 } 1009 } 1010 else 1011 { 1012 /* Add r1 to the result. */ 1013 if (first == NULL) 1014 first = last = r1; 1015 else 1016 { 1017 last->next = r1; 1018 last = r1; 1019 } 1020 r1 = r1->next; 1021 if (r1 == NULL) 1022 { 1023 /* To try to merge with subsequent ranges in r2. */ 1024 r1 = r2->next; 1025 r2->next = NULL; 1026 } 1027 } 1028 } 1029 if (r1 != NULL) 1030 { 1031 if (first == NULL) 1032 first = r1; 1033 else 1034 last->next = r1; 1035 ira_assert (r1->next == NULL); 1036 } 1037 else if (r2 != NULL) 1038 { 1039 if (first == NULL) 1040 first = r2; 1041 else 1042 last->next = r2; 1043 ira_assert (r2->next == NULL); 1044 } 1045 else 1046 { 1047 ira_assert (last->next == NULL); 1048 } 1049 return first; 1050 } 1051 1052 /* Return TRUE if live ranges R1 and R2 intersect. */ 1053 bool 1054 ira_live_ranges_intersect_p (live_range_t r1, live_range_t r2) 1055 { 1056 /* Remember the live ranges are always kept ordered. */ 1057 while (r1 != NULL && r2 != NULL) 1058 { 1059 if (r1->start > r2->finish) 1060 r1 = r1->next; 1061 else if (r2->start > r1->finish) 1062 r2 = r2->next; 1063 else 1064 return true; 1065 } 1066 return false; 1067 } 1068 1069 /* Free allocno live range R. */ 1070 void 1071 ira_finish_live_range (live_range_t r) 1072 { 1073 pool_free (live_range_pool, r); 1074 } 1075 1076 /* Free list of allocno live ranges starting with R. */ 1077 void 1078 ira_finish_live_range_list (live_range_t r) 1079 { 1080 live_range_t next_r; 1081 1082 for (; r != NULL; r = next_r) 1083 { 1084 next_r = r->next; 1085 ira_finish_live_range (r); 1086 } 1087 } 1088 1089 /* Free updated register costs of allocno A. */ 1090 void 1091 ira_free_allocno_updated_costs (ira_allocno_t a) 1092 { 1093 enum reg_class aclass; 1094 1095 aclass = ALLOCNO_CLASS (a); 1096 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL) 1097 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass); 1098 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL; 1099 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL) 1100 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a), 1101 aclass); 1102 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL; 1103 } 1104 1105 /* Free and nullify all cost vectors allocated earlier for allocno 1106 A. */ 1107 static void 1108 ira_free_allocno_costs (ira_allocno_t a) 1109 { 1110 enum reg_class aclass = ALLOCNO_CLASS (a); 1111 ira_object_t obj; 1112 ira_allocno_object_iterator oi; 1113 1114 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi) 1115 { 1116 ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj)); 1117 ira_object_id_map[OBJECT_CONFLICT_ID (obj)] = NULL; 1118 if (OBJECT_CONFLICT_ARRAY (obj) != NULL) 1119 ira_free (OBJECT_CONFLICT_ARRAY (obj)); 1120 pool_free (object_pool, obj); 1121 } 1122 1123 ira_allocnos[ALLOCNO_NUM (a)] = NULL; 1124 if (ALLOCNO_HARD_REG_COSTS (a) != NULL) 1125 ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), aclass); 1126 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL) 1127 ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass); 1128 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL) 1129 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass); 1130 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL) 1131 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a), 1132 aclass); 1133 ALLOCNO_HARD_REG_COSTS (a) = NULL; 1134 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL; 1135 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL; 1136 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL; 1137 } 1138 1139 /* Free the memory allocated for allocno A. */ 1140 static void 1141 finish_allocno (ira_allocno_t a) 1142 { 1143 ira_free_allocno_costs (a); 1144 pool_free (allocno_pool, a); 1145 } 1146 1147 /* Free the memory allocated for all allocnos. */ 1148 static void 1149 finish_allocnos (void) 1150 { 1151 ira_allocno_t a; 1152 ira_allocno_iterator ai; 1153 1154 FOR_EACH_ALLOCNO (a, ai) 1155 finish_allocno (a); 1156 ira_free (ira_regno_allocno_map); 1157 VEC_free (ira_object_t, heap, ira_object_id_map_vec); 1158 VEC_free (ira_allocno_t, heap, allocno_vec); 1159 free_alloc_pool (allocno_pool); 1160 free_alloc_pool (object_pool); 1161 free_alloc_pool (live_range_pool); 1162 } 1163 1164 1165 1166 /* Pools for copies. */ 1167 static alloc_pool copy_pool; 1168 1169 /* Vec containing references to all created copies. It is a 1170 container of array ira_copies. */ 1171 static VEC(ira_copy_t,heap) *copy_vec; 1172 1173 /* The function initializes data concerning allocno copies. */ 1174 static void 1175 initiate_copies (void) 1176 { 1177 copy_pool 1178 = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy), 100); 1179 copy_vec = VEC_alloc (ira_copy_t, heap, get_max_uid ()); 1180 ira_copies = NULL; 1181 ira_copies_num = 0; 1182 } 1183 1184 /* Return copy connecting A1 and A2 and originated from INSN of 1185 LOOP_TREE_NODE if any. */ 1186 static ira_copy_t 1187 find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx insn, 1188 ira_loop_tree_node_t loop_tree_node) 1189 { 1190 ira_copy_t cp, next_cp; 1191 ira_allocno_t another_a; 1192 1193 for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp) 1194 { 1195 if (cp->first == a1) 1196 { 1197 next_cp = cp->next_first_allocno_copy; 1198 another_a = cp->second; 1199 } 1200 else if (cp->second == a1) 1201 { 1202 next_cp = cp->next_second_allocno_copy; 1203 another_a = cp->first; 1204 } 1205 else 1206 gcc_unreachable (); 1207 if (another_a == a2 && cp->insn == insn 1208 && cp->loop_tree_node == loop_tree_node) 1209 return cp; 1210 } 1211 return NULL; 1212 } 1213 1214 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST, 1215 SECOND, FREQ, CONSTRAINT_P, and INSN. */ 1216 ira_copy_t 1217 ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq, 1218 bool constraint_p, rtx insn, 1219 ira_loop_tree_node_t loop_tree_node) 1220 { 1221 ira_copy_t cp; 1222 1223 cp = (ira_copy_t) pool_alloc (copy_pool); 1224 cp->num = ira_copies_num; 1225 cp->first = first; 1226 cp->second = second; 1227 cp->freq = freq; 1228 cp->constraint_p = constraint_p; 1229 cp->insn = insn; 1230 cp->loop_tree_node = loop_tree_node; 1231 VEC_safe_push (ira_copy_t, heap, copy_vec, cp); 1232 ira_copies = VEC_address (ira_copy_t, copy_vec); 1233 ira_copies_num = VEC_length (ira_copy_t, copy_vec); 1234 return cp; 1235 } 1236 1237 /* Attach a copy CP to allocnos involved into the copy. */ 1238 void 1239 ira_add_allocno_copy_to_list (ira_copy_t cp) 1240 { 1241 ira_allocno_t first = cp->first, second = cp->second; 1242 1243 cp->prev_first_allocno_copy = NULL; 1244 cp->prev_second_allocno_copy = NULL; 1245 cp->next_first_allocno_copy = ALLOCNO_COPIES (first); 1246 if (cp->next_first_allocno_copy != NULL) 1247 { 1248 if (cp->next_first_allocno_copy->first == first) 1249 cp->next_first_allocno_copy->prev_first_allocno_copy = cp; 1250 else 1251 cp->next_first_allocno_copy->prev_second_allocno_copy = cp; 1252 } 1253 cp->next_second_allocno_copy = ALLOCNO_COPIES (second); 1254 if (cp->next_second_allocno_copy != NULL) 1255 { 1256 if (cp->next_second_allocno_copy->second == second) 1257 cp->next_second_allocno_copy->prev_second_allocno_copy = cp; 1258 else 1259 cp->next_second_allocno_copy->prev_first_allocno_copy = cp; 1260 } 1261 ALLOCNO_COPIES (first) = cp; 1262 ALLOCNO_COPIES (second) = cp; 1263 } 1264 1265 /* Make a copy CP a canonical copy where number of the 1266 first allocno is less than the second one. */ 1267 void 1268 ira_swap_allocno_copy_ends_if_necessary (ira_copy_t cp) 1269 { 1270 ira_allocno_t temp; 1271 ira_copy_t temp_cp; 1272 1273 if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second)) 1274 return; 1275 1276 temp = cp->first; 1277 cp->first = cp->second; 1278 cp->second = temp; 1279 1280 temp_cp = cp->prev_first_allocno_copy; 1281 cp->prev_first_allocno_copy = cp->prev_second_allocno_copy; 1282 cp->prev_second_allocno_copy = temp_cp; 1283 1284 temp_cp = cp->next_first_allocno_copy; 1285 cp->next_first_allocno_copy = cp->next_second_allocno_copy; 1286 cp->next_second_allocno_copy = temp_cp; 1287 } 1288 1289 /* Create (or update frequency if the copy already exists) and return 1290 the copy of allocnos FIRST and SECOND with frequency FREQ 1291 corresponding to move insn INSN (if any) and originated from 1292 LOOP_TREE_NODE. */ 1293 ira_copy_t 1294 ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq, 1295 bool constraint_p, rtx insn, 1296 ira_loop_tree_node_t loop_tree_node) 1297 { 1298 ira_copy_t cp; 1299 1300 if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL) 1301 { 1302 cp->freq += freq; 1303 return cp; 1304 } 1305 cp = ira_create_copy (first, second, freq, constraint_p, insn, 1306 loop_tree_node); 1307 ira_assert (first != NULL && second != NULL); 1308 ira_add_allocno_copy_to_list (cp); 1309 ira_swap_allocno_copy_ends_if_necessary (cp); 1310 return cp; 1311 } 1312 1313 /* Print info about copy CP into file F. */ 1314 static void 1315 print_copy (FILE *f, ira_copy_t cp) 1316 { 1317 fprintf (f, " cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num, 1318 ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first), 1319 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq, 1320 cp->insn != NULL 1321 ? "move" : cp->constraint_p ? "constraint" : "shuffle"); 1322 } 1323 1324 /* Print info about copy CP into stderr. */ 1325 void 1326 ira_debug_copy (ira_copy_t cp) 1327 { 1328 print_copy (stderr, cp); 1329 } 1330 1331 /* Print info about all copies into file F. */ 1332 static void 1333 print_copies (FILE *f) 1334 { 1335 ira_copy_t cp; 1336 ira_copy_iterator ci; 1337 1338 FOR_EACH_COPY (cp, ci) 1339 print_copy (f, cp); 1340 } 1341 1342 /* Print info about all copies into stderr. */ 1343 void 1344 ira_debug_copies (void) 1345 { 1346 print_copies (stderr); 1347 } 1348 1349 /* Print info about copies involving allocno A into file F. */ 1350 static void 1351 print_allocno_copies (FILE *f, ira_allocno_t a) 1352 { 1353 ira_allocno_t another_a; 1354 ira_copy_t cp, next_cp; 1355 1356 fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a)); 1357 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp) 1358 { 1359 if (cp->first == a) 1360 { 1361 next_cp = cp->next_first_allocno_copy; 1362 another_a = cp->second; 1363 } 1364 else if (cp->second == a) 1365 { 1366 next_cp = cp->next_second_allocno_copy; 1367 another_a = cp->first; 1368 } 1369 else 1370 gcc_unreachable (); 1371 fprintf (f, " cp%d:a%d(r%d)@%d", cp->num, 1372 ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq); 1373 } 1374 fprintf (f, "\n"); 1375 } 1376 1377 /* Print info about copies involving allocno A into stderr. */ 1378 void 1379 ira_debug_allocno_copies (ira_allocno_t a) 1380 { 1381 print_allocno_copies (stderr, a); 1382 } 1383 1384 /* The function frees memory allocated for copy CP. */ 1385 static void 1386 finish_copy (ira_copy_t cp) 1387 { 1388 pool_free (copy_pool, cp); 1389 } 1390 1391 1392 /* Free memory allocated for all copies. */ 1393 static void 1394 finish_copies (void) 1395 { 1396 ira_copy_t cp; 1397 ira_copy_iterator ci; 1398 1399 FOR_EACH_COPY (cp, ci) 1400 finish_copy (cp); 1401 VEC_free (ira_copy_t, heap, copy_vec); 1402 free_alloc_pool (copy_pool); 1403 } 1404 1405 1406 1407 /* Pools for cost vectors. It is defined only for allocno classes. */ 1408 static alloc_pool cost_vector_pool[N_REG_CLASSES]; 1409 1410 /* The function initiates work with hard register cost vectors. It 1411 creates allocation pool for each allocno class. */ 1412 static void 1413 initiate_cost_vectors (void) 1414 { 1415 int i; 1416 enum reg_class aclass; 1417 1418 for (i = 0; i < ira_allocno_classes_num; i++) 1419 { 1420 aclass = ira_allocno_classes[i]; 1421 cost_vector_pool[aclass] 1422 = create_alloc_pool ("cost vectors", 1423 sizeof (int) * ira_class_hard_regs_num[aclass], 1424 100); 1425 } 1426 } 1427 1428 /* Allocate and return a cost vector VEC for ACLASS. */ 1429 int * 1430 ira_allocate_cost_vector (reg_class_t aclass) 1431 { 1432 return (int *) pool_alloc (cost_vector_pool[(int) aclass]); 1433 } 1434 1435 /* Free a cost vector VEC for ACLASS. */ 1436 void 1437 ira_free_cost_vector (int *vec, reg_class_t aclass) 1438 { 1439 ira_assert (vec != NULL); 1440 pool_free (cost_vector_pool[(int) aclass], vec); 1441 } 1442 1443 /* Finish work with hard register cost vectors. Release allocation 1444 pool for each allocno class. */ 1445 static void 1446 finish_cost_vectors (void) 1447 { 1448 int i; 1449 enum reg_class aclass; 1450 1451 for (i = 0; i < ira_allocno_classes_num; i++) 1452 { 1453 aclass = ira_allocno_classes[i]; 1454 free_alloc_pool (cost_vector_pool[aclass]); 1455 } 1456 } 1457 1458 1459 1460 /* The current loop tree node and its regno allocno map. */ 1461 ira_loop_tree_node_t ira_curr_loop_tree_node; 1462 ira_allocno_t *ira_curr_regno_allocno_map; 1463 1464 /* This recursive function traverses loop tree with root LOOP_NODE 1465 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC 1466 correspondingly in preorder and postorder. The function sets up 1467 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P, 1468 basic block nodes of LOOP_NODE is also processed (before its 1469 subloop nodes). */ 1470 void 1471 ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node, 1472 void (*preorder_func) (ira_loop_tree_node_t), 1473 void (*postorder_func) (ira_loop_tree_node_t)) 1474 { 1475 ira_loop_tree_node_t subloop_node; 1476 1477 ira_assert (loop_node->bb == NULL); 1478 ira_curr_loop_tree_node = loop_node; 1479 ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map; 1480 1481 if (preorder_func != NULL) 1482 (*preorder_func) (loop_node); 1483 1484 if (bb_p) 1485 for (subloop_node = loop_node->children; 1486 subloop_node != NULL; 1487 subloop_node = subloop_node->next) 1488 if (subloop_node->bb != NULL) 1489 { 1490 if (preorder_func != NULL) 1491 (*preorder_func) (subloop_node); 1492 1493 if (postorder_func != NULL) 1494 (*postorder_func) (subloop_node); 1495 } 1496 1497 for (subloop_node = loop_node->subloops; 1498 subloop_node != NULL; 1499 subloop_node = subloop_node->subloop_next) 1500 { 1501 ira_assert (subloop_node->bb == NULL); 1502 ira_traverse_loop_tree (bb_p, subloop_node, 1503 preorder_func, postorder_func); 1504 } 1505 1506 ira_curr_loop_tree_node = loop_node; 1507 ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map; 1508 1509 if (postorder_func != NULL) 1510 (*postorder_func) (loop_node); 1511 } 1512 1513 1514 1515 /* The basic block currently being processed. */ 1516 static basic_block curr_bb; 1517 1518 /* This recursive function creates allocnos corresponding to 1519 pseudo-registers containing in X. True OUTPUT_P means that X is 1520 a lvalue. */ 1521 static void 1522 create_insn_allocnos (rtx x, bool output_p) 1523 { 1524 int i, j; 1525 const char *fmt; 1526 enum rtx_code code = GET_CODE (x); 1527 1528 if (code == REG) 1529 { 1530 int regno; 1531 1532 if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER) 1533 { 1534 ira_allocno_t a; 1535 1536 if ((a = ira_curr_regno_allocno_map[regno]) == NULL) 1537 a = ira_create_allocno (regno, false, ira_curr_loop_tree_node); 1538 1539 ALLOCNO_NREFS (a)++; 1540 ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb); 1541 if (output_p) 1542 bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno); 1543 } 1544 return; 1545 } 1546 else if (code == SET) 1547 { 1548 create_insn_allocnos (SET_DEST (x), true); 1549 create_insn_allocnos (SET_SRC (x), false); 1550 return; 1551 } 1552 else if (code == CLOBBER) 1553 { 1554 create_insn_allocnos (XEXP (x, 0), true); 1555 return; 1556 } 1557 else if (code == MEM) 1558 { 1559 create_insn_allocnos (XEXP (x, 0), false); 1560 return; 1561 } 1562 else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC || 1563 code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY) 1564 { 1565 create_insn_allocnos (XEXP (x, 0), true); 1566 create_insn_allocnos (XEXP (x, 0), false); 1567 return; 1568 } 1569 1570 fmt = GET_RTX_FORMAT (code); 1571 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1572 { 1573 if (fmt[i] == 'e') 1574 create_insn_allocnos (XEXP (x, i), output_p); 1575 else if (fmt[i] == 'E') 1576 for (j = 0; j < XVECLEN (x, i); j++) 1577 create_insn_allocnos (XVECEXP (x, i, j), output_p); 1578 } 1579 } 1580 1581 /* Create allocnos corresponding to pseudo-registers living in the 1582 basic block represented by the corresponding loop tree node 1583 BB_NODE. */ 1584 static void 1585 create_bb_allocnos (ira_loop_tree_node_t bb_node) 1586 { 1587 basic_block bb; 1588 rtx insn; 1589 unsigned int i; 1590 bitmap_iterator bi; 1591 1592 curr_bb = bb = bb_node->bb; 1593 ira_assert (bb != NULL); 1594 FOR_BB_INSNS_REVERSE (bb, insn) 1595 if (NONDEBUG_INSN_P (insn)) 1596 create_insn_allocnos (PATTERN (insn), false); 1597 /* It might be a allocno living through from one subloop to 1598 another. */ 1599 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (bb), FIRST_PSEUDO_REGISTER, i, bi) 1600 if (ira_curr_regno_allocno_map[i] == NULL) 1601 ira_create_allocno (i, false, ira_curr_loop_tree_node); 1602 } 1603 1604 /* Create allocnos corresponding to pseudo-registers living on edge E 1605 (a loop entry or exit). Also mark the allocnos as living on the 1606 loop border. */ 1607 static void 1608 create_loop_allocnos (edge e) 1609 { 1610 unsigned int i; 1611 bitmap live_in_regs, border_allocnos; 1612 bitmap_iterator bi; 1613 ira_loop_tree_node_t parent; 1614 1615 live_in_regs = DF_LR_IN (e->dest); 1616 border_allocnos = ira_curr_loop_tree_node->border_allocnos; 1617 EXECUTE_IF_SET_IN_REG_SET (DF_LR_OUT (e->src), 1618 FIRST_PSEUDO_REGISTER, i, bi) 1619 if (bitmap_bit_p (live_in_regs, i)) 1620 { 1621 if (ira_curr_regno_allocno_map[i] == NULL) 1622 { 1623 /* The order of creations is important for right 1624 ira_regno_allocno_map. */ 1625 if ((parent = ira_curr_loop_tree_node->parent) != NULL 1626 && parent->regno_allocno_map[i] == NULL) 1627 ira_create_allocno (i, false, parent); 1628 ira_create_allocno (i, false, ira_curr_loop_tree_node); 1629 } 1630 bitmap_set_bit (border_allocnos, 1631 ALLOCNO_NUM (ira_curr_regno_allocno_map[i])); 1632 } 1633 } 1634 1635 /* Create allocnos corresponding to pseudo-registers living in loop 1636 represented by the corresponding loop tree node LOOP_NODE. This 1637 function is called by ira_traverse_loop_tree. */ 1638 static void 1639 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node) 1640 { 1641 if (loop_node->bb != NULL) 1642 create_bb_allocnos (loop_node); 1643 else if (loop_node != ira_loop_tree_root) 1644 { 1645 int i; 1646 edge_iterator ei; 1647 edge e; 1648 VEC (edge, heap) *edges; 1649 1650 ira_assert (current_loops != NULL); 1651 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds) 1652 if (e->src != loop_node->loop->latch) 1653 create_loop_allocnos (e); 1654 1655 edges = get_loop_exit_edges (loop_node->loop); 1656 FOR_EACH_VEC_ELT (edge, edges, i, e) 1657 create_loop_allocnos (e); 1658 VEC_free (edge, heap, edges); 1659 } 1660 } 1661 1662 /* Propagate information about allocnos modified inside the loop given 1663 by its LOOP_TREE_NODE to its parent. */ 1664 static void 1665 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node) 1666 { 1667 if (loop_tree_node == ira_loop_tree_root) 1668 return; 1669 ira_assert (loop_tree_node->bb == NULL); 1670 bitmap_ior_into (loop_tree_node->parent->modified_regnos, 1671 loop_tree_node->modified_regnos); 1672 } 1673 1674 /* Propagate new info about allocno A (see comments about accumulated 1675 info in allocno definition) to the corresponding allocno on upper 1676 loop tree level. So allocnos on upper levels accumulate 1677 information about the corresponding allocnos in nested regions. 1678 The new info means allocno info finally calculated in this 1679 file. */ 1680 static void 1681 propagate_allocno_info (void) 1682 { 1683 int i; 1684 ira_allocno_t a, parent_a; 1685 ira_loop_tree_node_t parent; 1686 enum reg_class aclass; 1687 1688 if (flag_ira_region != IRA_REGION_ALL 1689 && flag_ira_region != IRA_REGION_MIXED) 1690 return; 1691 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--) 1692 for (a = ira_regno_allocno_map[i]; 1693 a != NULL; 1694 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 1695 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL 1696 && (parent_a = parent->regno_allocno_map[i]) != NULL 1697 /* There are no caps yet at this point. So use 1698 border_allocnos to find allocnos for the propagation. */ 1699 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos, 1700 ALLOCNO_NUM (a))) 1701 { 1702 if (! ALLOCNO_BAD_SPILL_P (a)) 1703 ALLOCNO_BAD_SPILL_P (parent_a) = false; 1704 ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a); 1705 ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a); 1706 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a); 1707 merge_hard_reg_conflicts (a, parent_a, true); 1708 ALLOCNO_CALLS_CROSSED_NUM (parent_a) 1709 += ALLOCNO_CALLS_CROSSED_NUM (a); 1710 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a) 1711 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a); 1712 aclass = ALLOCNO_CLASS (a); 1713 ira_assert (aclass == ALLOCNO_CLASS (parent_a)); 1714 ira_allocate_and_accumulate_costs 1715 (&ALLOCNO_HARD_REG_COSTS (parent_a), aclass, 1716 ALLOCNO_HARD_REG_COSTS (a)); 1717 ira_allocate_and_accumulate_costs 1718 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a), 1719 aclass, 1720 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)); 1721 ALLOCNO_CLASS_COST (parent_a) 1722 += ALLOCNO_CLASS_COST (a); 1723 ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a); 1724 } 1725 } 1726 1727 /* Create allocnos corresponding to pseudo-registers in the current 1728 function. Traverse the loop tree for this. */ 1729 static void 1730 create_allocnos (void) 1731 { 1732 /* We need to process BB first to correctly link allocnos by member 1733 next_regno_allocno. */ 1734 ira_traverse_loop_tree (true, ira_loop_tree_root, 1735 create_loop_tree_node_allocnos, NULL); 1736 if (optimize) 1737 ira_traverse_loop_tree (false, ira_loop_tree_root, NULL, 1738 propagate_modified_regnos); 1739 } 1740 1741 1742 1743 /* The page contains function to remove some regions from a separate 1744 register allocation. We remove regions whose separate allocation 1745 will hardly improve the result. As a result we speed up regional 1746 register allocation. */ 1747 1748 /* The function changes the object in range list given by R to OBJ. */ 1749 static void 1750 change_object_in_range_list (live_range_t r, ira_object_t obj) 1751 { 1752 for (; r != NULL; r = r->next) 1753 r->object = obj; 1754 } 1755 1756 /* Move all live ranges associated with allocno FROM to allocno TO. */ 1757 static void 1758 move_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to) 1759 { 1760 int i; 1761 int n = ALLOCNO_NUM_OBJECTS (from); 1762 1763 gcc_assert (n == ALLOCNO_NUM_OBJECTS (to)); 1764 1765 for (i = 0; i < n; i++) 1766 { 1767 ira_object_t from_obj = ALLOCNO_OBJECT (from, i); 1768 ira_object_t to_obj = ALLOCNO_OBJECT (to, i); 1769 live_range_t lr = OBJECT_LIVE_RANGES (from_obj); 1770 1771 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) 1772 { 1773 fprintf (ira_dump_file, 1774 " Moving ranges of a%dr%d to a%dr%d: ", 1775 ALLOCNO_NUM (from), ALLOCNO_REGNO (from), 1776 ALLOCNO_NUM (to), ALLOCNO_REGNO (to)); 1777 ira_print_live_range_list (ira_dump_file, lr); 1778 } 1779 change_object_in_range_list (lr, to_obj); 1780 OBJECT_LIVE_RANGES (to_obj) 1781 = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj)); 1782 OBJECT_LIVE_RANGES (from_obj) = NULL; 1783 } 1784 } 1785 1786 static void 1787 copy_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to) 1788 { 1789 int i; 1790 int n = ALLOCNO_NUM_OBJECTS (from); 1791 1792 gcc_assert (n == ALLOCNO_NUM_OBJECTS (to)); 1793 1794 for (i = 0; i < n; i++) 1795 { 1796 ira_object_t from_obj = ALLOCNO_OBJECT (from, i); 1797 ira_object_t to_obj = ALLOCNO_OBJECT (to, i); 1798 live_range_t lr = OBJECT_LIVE_RANGES (from_obj); 1799 1800 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) 1801 { 1802 fprintf (ira_dump_file, " Copying ranges of a%dr%d to a%dr%d: ", 1803 ALLOCNO_NUM (from), ALLOCNO_REGNO (from), 1804 ALLOCNO_NUM (to), ALLOCNO_REGNO (to)); 1805 ira_print_live_range_list (ira_dump_file, lr); 1806 } 1807 lr = ira_copy_live_range_list (lr); 1808 change_object_in_range_list (lr, to_obj); 1809 OBJECT_LIVE_RANGES (to_obj) 1810 = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj)); 1811 } 1812 } 1813 1814 /* Return TRUE if NODE represents a loop with low register 1815 pressure. */ 1816 static bool 1817 low_pressure_loop_node_p (ira_loop_tree_node_t node) 1818 { 1819 int i; 1820 enum reg_class pclass; 1821 1822 if (node->bb != NULL) 1823 return false; 1824 1825 for (i = 0; i < ira_pressure_classes_num; i++) 1826 { 1827 pclass = ira_pressure_classes[i]; 1828 if (node->reg_pressure[pclass] > ira_available_class_regs[pclass] 1829 && ira_available_class_regs[pclass] > 1) 1830 return false; 1831 } 1832 return true; 1833 } 1834 1835 #ifdef STACK_REGS 1836 /* Return TRUE if LOOP has a complex enter or exit edge. We don't 1837 form a region from such loop if the target use stack register 1838 because reg-stack.c can not deal with such edges. */ 1839 static bool 1840 loop_with_complex_edge_p (struct loop *loop) 1841 { 1842 int i; 1843 edge_iterator ei; 1844 edge e; 1845 VEC (edge, heap) *edges; 1846 bool res; 1847 1848 FOR_EACH_EDGE (e, ei, loop->header->preds) 1849 if (e->flags & EDGE_EH) 1850 return true; 1851 edges = get_loop_exit_edges (loop); 1852 res = false; 1853 FOR_EACH_VEC_ELT (edge, edges, i, e) 1854 if (e->flags & EDGE_COMPLEX) 1855 { 1856 res = true; 1857 break; 1858 } 1859 VEC_free (edge, heap, edges); 1860 return res; 1861 } 1862 #endif 1863 1864 /* Sort loops for marking them for removal. We put already marked 1865 loops first, then less frequent loops next, and then outer loops 1866 next. */ 1867 static int 1868 loop_compare_func (const void *v1p, const void *v2p) 1869 { 1870 int diff; 1871 ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p; 1872 ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p; 1873 1874 ira_assert (l1->parent != NULL && l2->parent != NULL); 1875 if (l1->to_remove_p && ! l2->to_remove_p) 1876 return -1; 1877 if (! l1->to_remove_p && l2->to_remove_p) 1878 return 1; 1879 if ((diff = l1->loop->header->frequency - l2->loop->header->frequency) != 0) 1880 return diff; 1881 if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0) 1882 return diff; 1883 /* Make sorting stable. */ 1884 return l1->loop_num - l2->loop_num; 1885 } 1886 1887 /* Mark loops which should be removed from regional allocation. We 1888 remove a loop with low register pressure inside another loop with 1889 register pressure. In this case a separate allocation of the loop 1890 hardly helps (for irregular register file architecture it could 1891 help by choosing a better hard register in the loop but we prefer 1892 faster allocation even in this case). We also remove cheap loops 1893 if there are more than IRA_MAX_LOOPS_NUM of them. Loop with EH 1894 exit or enter edges are removed too because the allocation might 1895 require put pseudo moves on the EH edges (we could still do this 1896 for pseudos with caller saved hard registers in some cases but it 1897 is impossible to say here or during top-down allocation pass what 1898 hard register the pseudos get finally). */ 1899 static void 1900 mark_loops_for_removal (void) 1901 { 1902 int i, n; 1903 ira_loop_tree_node_t *sorted_loops; 1904 loop_p loop; 1905 1906 ira_assert (current_loops != NULL); 1907 sorted_loops 1908 = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t) 1909 * VEC_length (loop_p, 1910 ira_loops.larray)); 1911 for (n = i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++) 1912 if (ira_loop_nodes[i].regno_allocno_map != NULL) 1913 { 1914 if (ira_loop_nodes[i].parent == NULL) 1915 { 1916 /* Don't remove the root. */ 1917 ira_loop_nodes[i].to_remove_p = false; 1918 continue; 1919 } 1920 sorted_loops[n++] = &ira_loop_nodes[i]; 1921 ira_loop_nodes[i].to_remove_p 1922 = ((low_pressure_loop_node_p (ira_loop_nodes[i].parent) 1923 && low_pressure_loop_node_p (&ira_loop_nodes[i])) 1924 #ifdef STACK_REGS 1925 || loop_with_complex_edge_p (ira_loop_nodes[i].loop) 1926 #endif 1927 ); 1928 } 1929 qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func); 1930 for (i = 0; n - i + 1 > IRA_MAX_LOOPS_NUM; i++) 1931 { 1932 sorted_loops[i]->to_remove_p = true; 1933 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) 1934 fprintf 1935 (ira_dump_file, 1936 " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n", 1937 sorted_loops[i]->loop_num, sorted_loops[i]->loop->header->index, 1938 sorted_loops[i]->loop->header->frequency, 1939 loop_depth (sorted_loops[i]->loop), 1940 low_pressure_loop_node_p (sorted_loops[i]->parent) 1941 && low_pressure_loop_node_p (sorted_loops[i]) 1942 ? "low pressure" : "cheap loop"); 1943 } 1944 ira_free (sorted_loops); 1945 } 1946 1947 /* Mark all loops but root for removing. */ 1948 static void 1949 mark_all_loops_for_removal (void) 1950 { 1951 int i; 1952 loop_p loop; 1953 1954 ira_assert (current_loops != NULL); 1955 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop) 1956 if (ira_loop_nodes[i].regno_allocno_map != NULL) 1957 { 1958 if (ira_loop_nodes[i].parent == NULL) 1959 { 1960 /* Don't remove the root. */ 1961 ira_loop_nodes[i].to_remove_p = false; 1962 continue; 1963 } 1964 ira_loop_nodes[i].to_remove_p = true; 1965 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) 1966 fprintf 1967 (ira_dump_file, 1968 " Mark loop %d (header %d, freq %d, depth %d) for removal\n", 1969 ira_loop_nodes[i].loop_num, 1970 ira_loop_nodes[i].loop->header->index, 1971 ira_loop_nodes[i].loop->header->frequency, 1972 loop_depth (ira_loop_nodes[i].loop)); 1973 } 1974 } 1975 1976 /* Definition of vector of loop tree nodes. */ 1977 DEF_VEC_P(ira_loop_tree_node_t); 1978 DEF_VEC_ALLOC_P(ira_loop_tree_node_t, heap); 1979 1980 /* Vec containing references to all removed loop tree nodes. */ 1981 static VEC(ira_loop_tree_node_t,heap) *removed_loop_vec; 1982 1983 /* Vec containing references to all children of loop tree nodes. */ 1984 static VEC(ira_loop_tree_node_t,heap) *children_vec; 1985 1986 /* Remove subregions of NODE if their separate allocation will not 1987 improve the result. */ 1988 static void 1989 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node) 1990 { 1991 unsigned int start; 1992 bool remove_p; 1993 ira_loop_tree_node_t subnode; 1994 1995 remove_p = node->to_remove_p; 1996 if (! remove_p) 1997 VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, node); 1998 start = VEC_length (ira_loop_tree_node_t, children_vec); 1999 for (subnode = node->children; subnode != NULL; subnode = subnode->next) 2000 if (subnode->bb == NULL) 2001 remove_uneccesary_loop_nodes_from_loop_tree (subnode); 2002 else 2003 VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, subnode); 2004 node->children = node->subloops = NULL; 2005 if (remove_p) 2006 { 2007 VEC_safe_push (ira_loop_tree_node_t, heap, removed_loop_vec, node); 2008 return; 2009 } 2010 while (VEC_length (ira_loop_tree_node_t, children_vec) > start) 2011 { 2012 subnode = VEC_pop (ira_loop_tree_node_t, children_vec); 2013 subnode->parent = node; 2014 subnode->next = node->children; 2015 node->children = subnode; 2016 if (subnode->bb == NULL) 2017 { 2018 subnode->subloop_next = node->subloops; 2019 node->subloops = subnode; 2020 } 2021 } 2022 } 2023 2024 /* Return TRUE if NODE is inside PARENT. */ 2025 static bool 2026 loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent) 2027 { 2028 for (node = node->parent; node != NULL; node = node->parent) 2029 if (node == parent) 2030 return true; 2031 return false; 2032 } 2033 2034 /* Sort allocnos according to their order in regno allocno list. */ 2035 static int 2036 regno_allocno_order_compare_func (const void *v1p, const void *v2p) 2037 { 2038 ira_allocno_t a1 = *(const ira_allocno_t *) v1p; 2039 ira_allocno_t a2 = *(const ira_allocno_t *) v2p; 2040 ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1); 2041 ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2); 2042 2043 if (loop_is_inside_p (n1, n2)) 2044 return -1; 2045 else if (loop_is_inside_p (n2, n1)) 2046 return 1; 2047 /* If allocnos are equally good, sort by allocno numbers, so that 2048 the results of qsort leave nothing to chance. We put allocnos 2049 with higher number first in the list because it is the original 2050 order for allocnos from loops on the same levels. */ 2051 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1); 2052 } 2053 2054 /* This array is used to sort allocnos to restore allocno order in 2055 the regno allocno list. */ 2056 static ira_allocno_t *regno_allocnos; 2057 2058 /* Restore allocno order for REGNO in the regno allocno list. */ 2059 static void 2060 ira_rebuild_regno_allocno_list (int regno) 2061 { 2062 int i, n; 2063 ira_allocno_t a; 2064 2065 for (n = 0, a = ira_regno_allocno_map[regno]; 2066 a != NULL; 2067 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 2068 regno_allocnos[n++] = a; 2069 ira_assert (n > 0); 2070 qsort (regno_allocnos, n, sizeof (ira_allocno_t), 2071 regno_allocno_order_compare_func); 2072 for (i = 1; i < n; i++) 2073 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i]; 2074 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL; 2075 ira_regno_allocno_map[regno] = regno_allocnos[0]; 2076 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) 2077 fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno); 2078 } 2079 2080 /* Propagate info from allocno FROM_A to allocno A. */ 2081 static void 2082 propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a) 2083 { 2084 enum reg_class aclass; 2085 2086 merge_hard_reg_conflicts (from_a, a, false); 2087 ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a); 2088 ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a); 2089 ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a); 2090 ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a); 2091 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) 2092 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a); 2093 if (! ALLOCNO_BAD_SPILL_P (from_a)) 2094 ALLOCNO_BAD_SPILL_P (a) = false; 2095 aclass = ALLOCNO_CLASS (from_a); 2096 ira_assert (aclass == ALLOCNO_CLASS (a)); 2097 ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), aclass, 2098 ALLOCNO_HARD_REG_COSTS (from_a)); 2099 ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), 2100 aclass, 2101 ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a)); 2102 ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a); 2103 ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a); 2104 } 2105 2106 /* Remove allocnos from loops removed from the allocation 2107 consideration. */ 2108 static void 2109 remove_unnecessary_allocnos (void) 2110 { 2111 int regno; 2112 bool merged_p, rebuild_p; 2113 ira_allocno_t a, prev_a, next_a, parent_a; 2114 ira_loop_tree_node_t a_node, parent; 2115 2116 merged_p = false; 2117 regno_allocnos = NULL; 2118 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--) 2119 { 2120 rebuild_p = false; 2121 for (prev_a = NULL, a = ira_regno_allocno_map[regno]; 2122 a != NULL; 2123 a = next_a) 2124 { 2125 next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a); 2126 a_node = ALLOCNO_LOOP_TREE_NODE (a); 2127 if (! a_node->to_remove_p) 2128 prev_a = a; 2129 else 2130 { 2131 for (parent = a_node->parent; 2132 (parent_a = parent->regno_allocno_map[regno]) == NULL 2133 && parent->to_remove_p; 2134 parent = parent->parent) 2135 ; 2136 if (parent_a == NULL) 2137 { 2138 /* There are no allocnos with the same regno in 2139 upper region -- just move the allocno to the 2140 upper region. */ 2141 prev_a = a; 2142 ALLOCNO_LOOP_TREE_NODE (a) = parent; 2143 parent->regno_allocno_map[regno] = a; 2144 bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a)); 2145 rebuild_p = true; 2146 } 2147 else 2148 { 2149 /* Remove the allocno and update info of allocno in 2150 the upper region. */ 2151 if (prev_a == NULL) 2152 ira_regno_allocno_map[regno] = next_a; 2153 else 2154 ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a; 2155 move_allocno_live_ranges (a, parent_a); 2156 merged_p = true; 2157 propagate_some_info_from_allocno (parent_a, a); 2158 /* Remove it from the corresponding regno allocno 2159 map to avoid info propagation of subsequent 2160 allocno into this already removed allocno. */ 2161 a_node->regno_allocno_map[regno] = NULL; 2162 finish_allocno (a); 2163 } 2164 } 2165 } 2166 if (rebuild_p) 2167 /* We need to restore the order in regno allocno list. */ 2168 { 2169 if (regno_allocnos == NULL) 2170 regno_allocnos 2171 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) 2172 * ira_allocnos_num); 2173 ira_rebuild_regno_allocno_list (regno); 2174 } 2175 } 2176 if (merged_p) 2177 ira_rebuild_start_finish_chains (); 2178 if (regno_allocnos != NULL) 2179 ira_free (regno_allocnos); 2180 } 2181 2182 /* Remove allocnos from all loops but the root. */ 2183 static void 2184 remove_low_level_allocnos (void) 2185 { 2186 int regno; 2187 bool merged_p, propagate_p; 2188 ira_allocno_t a, top_a; 2189 ira_loop_tree_node_t a_node, parent; 2190 ira_allocno_iterator ai; 2191 2192 merged_p = false; 2193 FOR_EACH_ALLOCNO (a, ai) 2194 { 2195 a_node = ALLOCNO_LOOP_TREE_NODE (a); 2196 if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL) 2197 continue; 2198 regno = ALLOCNO_REGNO (a); 2199 if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL) 2200 { 2201 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root; 2202 ira_loop_tree_root->regno_allocno_map[regno] = a; 2203 continue; 2204 } 2205 propagate_p = a_node->parent->regno_allocno_map[regno] == NULL; 2206 /* Remove the allocno and update info of allocno in the upper 2207 region. */ 2208 move_allocno_live_ranges (a, top_a); 2209 merged_p = true; 2210 if (propagate_p) 2211 propagate_some_info_from_allocno (top_a, a); 2212 } 2213 FOR_EACH_ALLOCNO (a, ai) 2214 { 2215 a_node = ALLOCNO_LOOP_TREE_NODE (a); 2216 if (a_node == ira_loop_tree_root) 2217 continue; 2218 parent = a_node->parent; 2219 regno = ALLOCNO_REGNO (a); 2220 if (ALLOCNO_CAP_MEMBER (a) != NULL) 2221 ira_assert (ALLOCNO_CAP (a) != NULL); 2222 else if (ALLOCNO_CAP (a) == NULL) 2223 ira_assert (parent->regno_allocno_map[regno] != NULL); 2224 } 2225 FOR_EACH_ALLOCNO (a, ai) 2226 { 2227 regno = ALLOCNO_REGNO (a); 2228 if (ira_loop_tree_root->regno_allocno_map[regno] == a) 2229 { 2230 ira_object_t obj; 2231 ira_allocno_object_iterator oi; 2232 2233 ira_regno_allocno_map[regno] = a; 2234 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL; 2235 ALLOCNO_CAP_MEMBER (a) = NULL; 2236 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi) 2237 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), 2238 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)); 2239 #ifdef STACK_REGS 2240 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a)) 2241 ALLOCNO_NO_STACK_REG_P (a) = true; 2242 #endif 2243 } 2244 else 2245 finish_allocno (a); 2246 } 2247 if (merged_p) 2248 ira_rebuild_start_finish_chains (); 2249 } 2250 2251 /* Remove loops from consideration. We remove all loops except for 2252 root if ALL_P or loops for which a separate allocation will not 2253 improve the result. We have to do this after allocno creation and 2254 their costs and allocno class evaluation because only after that 2255 the register pressure can be known and is calculated. */ 2256 static void 2257 remove_unnecessary_regions (bool all_p) 2258 { 2259 if (current_loops == NULL) 2260 return; 2261 if (all_p) 2262 mark_all_loops_for_removal (); 2263 else 2264 mark_loops_for_removal (); 2265 children_vec 2266 = VEC_alloc (ira_loop_tree_node_t, heap, 2267 last_basic_block + VEC_length (loop_p, ira_loops.larray)); 2268 removed_loop_vec 2269 = VEC_alloc (ira_loop_tree_node_t, heap, 2270 last_basic_block + VEC_length (loop_p, ira_loops.larray)); 2271 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root) ; 2272 VEC_free (ira_loop_tree_node_t, heap, children_vec); 2273 if (all_p) 2274 remove_low_level_allocnos (); 2275 else 2276 remove_unnecessary_allocnos (); 2277 while (VEC_length (ira_loop_tree_node_t, removed_loop_vec) > 0) 2278 finish_loop_tree_node (VEC_pop (ira_loop_tree_node_t, removed_loop_vec)); 2279 VEC_free (ira_loop_tree_node_t, heap, removed_loop_vec); 2280 } 2281 2282 2283 2284 /* At this point true value of allocno attribute bad_spill_p means 2285 that there is an insn where allocno occurs and where the allocno 2286 can not be used as memory. The function updates the attribute, now 2287 it can be true only for allocnos which can not be used as memory in 2288 an insn and in whose live ranges there is other allocno deaths. 2289 Spilling allocnos with true value will not improve the code because 2290 it will not make other allocnos colorable and additional reloads 2291 for the corresponding pseudo will be generated in reload pass for 2292 each insn it occurs. 2293 2294 This is a trick mentioned in one classic article of Chaitin etc 2295 which is frequently omitted in other implementations of RA based on 2296 graph coloring. */ 2297 static void 2298 update_bad_spill_attribute (void) 2299 { 2300 int i; 2301 ira_allocno_t a; 2302 ira_allocno_iterator ai; 2303 ira_allocno_object_iterator aoi; 2304 ira_object_t obj; 2305 live_range_t r; 2306 enum reg_class aclass; 2307 bitmap_head dead_points[N_REG_CLASSES]; 2308 2309 for (i = 0; i < ira_allocno_classes_num; i++) 2310 { 2311 aclass = ira_allocno_classes[i]; 2312 bitmap_initialize (&dead_points[aclass], ®_obstack); 2313 } 2314 FOR_EACH_ALLOCNO (a, ai) 2315 { 2316 aclass = ALLOCNO_CLASS (a); 2317 if (aclass == NO_REGS) 2318 continue; 2319 FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi) 2320 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) 2321 bitmap_set_bit (&dead_points[aclass], r->finish); 2322 } 2323 FOR_EACH_ALLOCNO (a, ai) 2324 { 2325 aclass = ALLOCNO_CLASS (a); 2326 if (aclass == NO_REGS) 2327 continue; 2328 if (! ALLOCNO_BAD_SPILL_P (a)) 2329 continue; 2330 FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi) 2331 { 2332 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) 2333 { 2334 for (i = r->start + 1; i < r->finish; i++) 2335 if (bitmap_bit_p (&dead_points[aclass], i)) 2336 break; 2337 if (i < r->finish) 2338 break; 2339 } 2340 if (r != NULL) 2341 { 2342 ALLOCNO_BAD_SPILL_P (a) = false; 2343 break; 2344 } 2345 } 2346 } 2347 for (i = 0; i < ira_allocno_classes_num; i++) 2348 { 2349 aclass = ira_allocno_classes[i]; 2350 bitmap_clear (&dead_points[aclass]); 2351 } 2352 } 2353 2354 2355 2356 /* Set up minimal and maximal live range points for allocnos. */ 2357 static void 2358 setup_min_max_allocno_live_range_point (void) 2359 { 2360 int i; 2361 ira_allocno_t a, parent_a, cap; 2362 ira_allocno_iterator ai; 2363 #ifdef ENABLE_IRA_CHECKING 2364 ira_object_iterator oi; 2365 ira_object_t obj; 2366 #endif 2367 live_range_t r; 2368 ira_loop_tree_node_t parent; 2369 2370 FOR_EACH_ALLOCNO (a, ai) 2371 { 2372 int n = ALLOCNO_NUM_OBJECTS (a); 2373 2374 for (i = 0; i < n; i++) 2375 { 2376 ira_object_t obj = ALLOCNO_OBJECT (a, i); 2377 r = OBJECT_LIVE_RANGES (obj); 2378 if (r == NULL) 2379 continue; 2380 OBJECT_MAX (obj) = r->finish; 2381 for (; r->next != NULL; r = r->next) 2382 ; 2383 OBJECT_MIN (obj) = r->start; 2384 } 2385 } 2386 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--) 2387 for (a = ira_regno_allocno_map[i]; 2388 a != NULL; 2389 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 2390 { 2391 int j; 2392 int n = ALLOCNO_NUM_OBJECTS (a); 2393 2394 for (j = 0; j < n; j++) 2395 { 2396 ira_object_t obj = ALLOCNO_OBJECT (a, j); 2397 ira_object_t parent_obj; 2398 2399 if (OBJECT_MAX (obj) < 0) 2400 continue; 2401 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL); 2402 /* Accumulation of range info. */ 2403 if (ALLOCNO_CAP (a) != NULL) 2404 { 2405 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap)) 2406 { 2407 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j); 2408 if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj)) 2409 OBJECT_MAX (cap_obj) = OBJECT_MAX (obj); 2410 if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj)) 2411 OBJECT_MIN (cap_obj) = OBJECT_MIN (obj); 2412 } 2413 continue; 2414 } 2415 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL) 2416 continue; 2417 parent_a = parent->regno_allocno_map[i]; 2418 parent_obj = ALLOCNO_OBJECT (parent_a, j); 2419 if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj)) 2420 OBJECT_MAX (parent_obj) = OBJECT_MAX (obj); 2421 if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj)) 2422 OBJECT_MIN (parent_obj) = OBJECT_MIN (obj); 2423 } 2424 } 2425 #ifdef ENABLE_IRA_CHECKING 2426 FOR_EACH_OBJECT (obj, oi) 2427 { 2428 if ((0 <= OBJECT_MIN (obj) && OBJECT_MIN (obj) <= ira_max_point) 2429 && (0 <= OBJECT_MAX (obj) && OBJECT_MAX (obj) <= ira_max_point)) 2430 continue; 2431 gcc_unreachable (); 2432 } 2433 #endif 2434 } 2435 2436 /* Sort allocnos according to their live ranges. Allocnos with 2437 smaller allocno class are put first unless we use priority 2438 coloring. Allocnos with the same class are ordered according 2439 their start (min). Allocnos with the same start are ordered 2440 according their finish (max). */ 2441 static int 2442 object_range_compare_func (const void *v1p, const void *v2p) 2443 { 2444 int diff; 2445 ira_object_t obj1 = *(const ira_object_t *) v1p; 2446 ira_object_t obj2 = *(const ira_object_t *) v2p; 2447 ira_allocno_t a1 = OBJECT_ALLOCNO (obj1); 2448 ira_allocno_t a2 = OBJECT_ALLOCNO (obj2); 2449 2450 if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0) 2451 return diff; 2452 if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0) 2453 return diff; 2454 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2); 2455 } 2456 2457 /* Sort ira_object_id_map and set up conflict id of allocnos. */ 2458 static void 2459 sort_conflict_id_map (void) 2460 { 2461 int i, num; 2462 ira_allocno_t a; 2463 ira_allocno_iterator ai; 2464 2465 num = 0; 2466 FOR_EACH_ALLOCNO (a, ai) 2467 { 2468 ira_allocno_object_iterator oi; 2469 ira_object_t obj; 2470 2471 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi) 2472 ira_object_id_map[num++] = obj; 2473 } 2474 qsort (ira_object_id_map, num, sizeof (ira_object_t), 2475 object_range_compare_func); 2476 for (i = 0; i < num; i++) 2477 { 2478 ira_object_t obj = ira_object_id_map[i]; 2479 2480 gcc_assert (obj != NULL); 2481 OBJECT_CONFLICT_ID (obj) = i; 2482 } 2483 for (i = num; i < ira_objects_num; i++) 2484 ira_object_id_map[i] = NULL; 2485 } 2486 2487 /* Set up minimal and maximal conflict ids of allocnos with which 2488 given allocno can conflict. */ 2489 static void 2490 setup_min_max_conflict_allocno_ids (void) 2491 { 2492 int aclass; 2493 int i, j, min, max, start, finish, first_not_finished, filled_area_start; 2494 int *live_range_min, *last_lived; 2495 int word0_min, word0_max; 2496 ira_allocno_t a; 2497 ira_allocno_iterator ai; 2498 2499 live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num); 2500 aclass = -1; 2501 first_not_finished = -1; 2502 for (i = 0; i < ira_objects_num; i++) 2503 { 2504 ira_object_t obj = ira_object_id_map[i]; 2505 2506 if (obj == NULL) 2507 continue; 2508 2509 a = OBJECT_ALLOCNO (obj); 2510 2511 if (aclass < 0) 2512 { 2513 aclass = ALLOCNO_CLASS (a); 2514 min = i; 2515 first_not_finished = i; 2516 } 2517 else 2518 { 2519 start = OBJECT_MIN (obj); 2520 /* If we skip an allocno, the allocno with smaller ids will 2521 be also skipped because of the secondary sorting the 2522 range finishes (see function 2523 object_range_compare_func). */ 2524 while (first_not_finished < i 2525 && start > OBJECT_MAX (ira_object_id_map 2526 [first_not_finished])) 2527 first_not_finished++; 2528 min = first_not_finished; 2529 } 2530 if (min == i) 2531 /* We could increase min further in this case but it is good 2532 enough. */ 2533 min++; 2534 live_range_min[i] = OBJECT_MIN (obj); 2535 OBJECT_MIN (obj) = min; 2536 } 2537 last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point); 2538 aclass = -1; 2539 filled_area_start = -1; 2540 for (i = ira_objects_num - 1; i >= 0; i--) 2541 { 2542 ira_object_t obj = ira_object_id_map[i]; 2543 2544 if (obj == NULL) 2545 continue; 2546 2547 a = OBJECT_ALLOCNO (obj); 2548 if (aclass < 0) 2549 { 2550 aclass = ALLOCNO_CLASS (a); 2551 for (j = 0; j < ira_max_point; j++) 2552 last_lived[j] = -1; 2553 filled_area_start = ira_max_point; 2554 } 2555 min = live_range_min[i]; 2556 finish = OBJECT_MAX (obj); 2557 max = last_lived[finish]; 2558 if (max < 0) 2559 /* We could decrease max further in this case but it is good 2560 enough. */ 2561 max = OBJECT_CONFLICT_ID (obj) - 1; 2562 OBJECT_MAX (obj) = max; 2563 /* In filling, we can go further A range finish to recognize 2564 intersection quickly because if the finish of subsequently 2565 processed allocno (it has smaller conflict id) range is 2566 further A range finish than they are definitely intersected 2567 (the reason for this is the allocnos with bigger conflict id 2568 have their range starts not smaller than allocnos with 2569 smaller ids. */ 2570 for (j = min; j < filled_area_start; j++) 2571 last_lived[j] = i; 2572 filled_area_start = min; 2573 } 2574 ira_free (last_lived); 2575 ira_free (live_range_min); 2576 2577 /* For allocnos with more than one object, we may later record extra conflicts in 2578 subobject 0 that we cannot really know about here. 2579 For now, simply widen the min/max range of these subobjects. */ 2580 2581 word0_min = INT_MAX; 2582 word0_max = INT_MIN; 2583 2584 FOR_EACH_ALLOCNO (a, ai) 2585 { 2586 int n = ALLOCNO_NUM_OBJECTS (a); 2587 ira_object_t obj0; 2588 2589 if (n < 2) 2590 continue; 2591 obj0 = ALLOCNO_OBJECT (a, 0); 2592 if (OBJECT_CONFLICT_ID (obj0) < word0_min) 2593 word0_min = OBJECT_CONFLICT_ID (obj0); 2594 if (OBJECT_CONFLICT_ID (obj0) > word0_max) 2595 word0_max = OBJECT_CONFLICT_ID (obj0); 2596 } 2597 FOR_EACH_ALLOCNO (a, ai) 2598 { 2599 int n = ALLOCNO_NUM_OBJECTS (a); 2600 ira_object_t obj0; 2601 2602 if (n < 2) 2603 continue; 2604 obj0 = ALLOCNO_OBJECT (a, 0); 2605 if (OBJECT_MIN (obj0) > word0_min) 2606 OBJECT_MIN (obj0) = word0_min; 2607 if (OBJECT_MAX (obj0) < word0_max) 2608 OBJECT_MAX (obj0) = word0_max; 2609 } 2610 } 2611 2612 2613 2614 static void 2615 create_caps (void) 2616 { 2617 ira_allocno_t a; 2618 ira_allocno_iterator ai; 2619 ira_loop_tree_node_t loop_tree_node; 2620 2621 FOR_EACH_ALLOCNO (a, ai) 2622 { 2623 if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root) 2624 continue; 2625 if (ALLOCNO_CAP_MEMBER (a) != NULL) 2626 create_cap_allocno (a); 2627 else if (ALLOCNO_CAP (a) == NULL) 2628 { 2629 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a); 2630 if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a))) 2631 create_cap_allocno (a); 2632 } 2633 } 2634 } 2635 2636 2637 2638 /* The page contains code transforming more one region internal 2639 representation (IR) to one region IR which is necessary for reload. 2640 This transformation is called IR flattening. We might just rebuild 2641 the IR for one region but we don't do it because it takes a lot of 2642 time. */ 2643 2644 /* Map: regno -> allocnos which will finally represent the regno for 2645 IR with one region. */ 2646 static ira_allocno_t *regno_top_level_allocno_map; 2647 2648 /* Find the allocno that corresponds to A at a level one higher up in the 2649 loop tree. Returns NULL if A is a cap, or if it has no parent. */ 2650 ira_allocno_t 2651 ira_parent_allocno (ira_allocno_t a) 2652 { 2653 ira_loop_tree_node_t parent; 2654 2655 if (ALLOCNO_CAP (a) != NULL) 2656 return NULL; 2657 2658 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent; 2659 if (parent == NULL) 2660 return NULL; 2661 2662 return parent->regno_allocno_map[ALLOCNO_REGNO (a)]; 2663 } 2664 2665 /* Find the allocno that corresponds to A at a level one higher up in the 2666 loop tree. If ALLOCNO_CAP is set for A, return that. */ 2667 ira_allocno_t 2668 ira_parent_or_cap_allocno (ira_allocno_t a) 2669 { 2670 if (ALLOCNO_CAP (a) != NULL) 2671 return ALLOCNO_CAP (a); 2672 2673 return ira_parent_allocno (a); 2674 } 2675 2676 /* Process all allocnos originated from pseudo REGNO and copy live 2677 ranges, hard reg conflicts, and allocno stack reg attributes from 2678 low level allocnos to final allocnos which are destinations of 2679 removed stores at a loop exit. Return true if we copied live 2680 ranges. */ 2681 static bool 2682 copy_info_to_removed_store_destinations (int regno) 2683 { 2684 ira_allocno_t a; 2685 ira_allocno_t parent_a = NULL; 2686 ira_loop_tree_node_t parent; 2687 bool merged_p; 2688 2689 merged_p = false; 2690 for (a = ira_regno_allocno_map[regno]; 2691 a != NULL; 2692 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 2693 { 2694 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]) 2695 /* This allocno will be removed. */ 2696 continue; 2697 2698 /* Caps will be removed. */ 2699 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL); 2700 for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent; 2701 parent != NULL; 2702 parent = parent->parent) 2703 if ((parent_a = parent->regno_allocno_map[regno]) == NULL 2704 || (parent_a 2705 == regno_top_level_allocno_map[REGNO 2706 (allocno_emit_reg (parent_a))] 2707 && ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p)) 2708 break; 2709 if (parent == NULL || parent_a == NULL) 2710 continue; 2711 2712 copy_allocno_live_ranges (a, parent_a); 2713 merge_hard_reg_conflicts (a, parent_a, true); 2714 2715 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a); 2716 ALLOCNO_CALLS_CROSSED_NUM (parent_a) 2717 += ALLOCNO_CALLS_CROSSED_NUM (a); 2718 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a) 2719 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a); 2720 merged_p = true; 2721 } 2722 return merged_p; 2723 } 2724 2725 /* Flatten the IR. In other words, this function transforms IR as if 2726 it were built with one region (without loops). We could make it 2727 much simpler by rebuilding IR with one region, but unfortunately it 2728 takes a lot of time. MAX_REGNO_BEFORE_EMIT and 2729 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and 2730 IRA_MAX_POINT before emitting insns on the loop borders. */ 2731 void 2732 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit) 2733 { 2734 int i, j; 2735 bool keep_p; 2736 int hard_regs_num; 2737 bool new_pseudos_p, merged_p, mem_dest_p; 2738 unsigned int n; 2739 enum reg_class aclass; 2740 ira_allocno_t a, parent_a, first, second, node_first, node_second; 2741 ira_copy_t cp; 2742 ira_loop_tree_node_t node; 2743 live_range_t r; 2744 ira_allocno_iterator ai; 2745 ira_copy_iterator ci; 2746 2747 regno_top_level_allocno_map 2748 = (ira_allocno_t *) ira_allocate (max_reg_num () 2749 * sizeof (ira_allocno_t)); 2750 memset (regno_top_level_allocno_map, 0, 2751 max_reg_num () * sizeof (ira_allocno_t)); 2752 new_pseudos_p = merged_p = false; 2753 FOR_EACH_ALLOCNO (a, ai) 2754 { 2755 ira_allocno_object_iterator oi; 2756 ira_object_t obj; 2757 2758 if (ALLOCNO_CAP_MEMBER (a) != NULL) 2759 /* Caps are not in the regno allocno maps and they are never 2760 will be transformed into allocnos existing after IR 2761 flattening. */ 2762 continue; 2763 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi) 2764 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 2765 OBJECT_CONFLICT_HARD_REGS (obj)); 2766 #ifdef STACK_REGS 2767 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a); 2768 #endif 2769 } 2770 /* Fix final allocno attributes. */ 2771 for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--) 2772 { 2773 mem_dest_p = false; 2774 for (a = ira_regno_allocno_map[i]; 2775 a != NULL; 2776 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 2777 { 2778 ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a); 2779 2780 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL); 2781 if (data->somewhere_renamed_p) 2782 new_pseudos_p = true; 2783 parent_a = ira_parent_allocno (a); 2784 if (parent_a == NULL) 2785 { 2786 ALLOCNO_COPIES (a) = NULL; 2787 regno_top_level_allocno_map[REGNO (data->reg)] = a; 2788 continue; 2789 } 2790 ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL); 2791 2792 if (data->mem_optimized_dest != NULL) 2793 mem_dest_p = true; 2794 parent_data = ALLOCNO_EMIT_DATA (parent_a); 2795 if (REGNO (data->reg) == REGNO (parent_data->reg)) 2796 { 2797 merge_hard_reg_conflicts (a, parent_a, true); 2798 move_allocno_live_ranges (a, parent_a); 2799 merged_p = true; 2800 parent_data->mem_optimized_dest_p 2801 = (parent_data->mem_optimized_dest_p 2802 || data->mem_optimized_dest_p); 2803 continue; 2804 } 2805 new_pseudos_p = true; 2806 for (;;) 2807 { 2808 ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a); 2809 ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a); 2810 ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a); 2811 ALLOCNO_CALLS_CROSSED_NUM (parent_a) 2812 -= ALLOCNO_CALLS_CROSSED_NUM (a); 2813 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a) 2814 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a); 2815 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0 2816 && ALLOCNO_NREFS (parent_a) >= 0 2817 && ALLOCNO_FREQ (parent_a) >= 0); 2818 aclass = ALLOCNO_CLASS (parent_a); 2819 hard_regs_num = ira_class_hard_regs_num[aclass]; 2820 if (ALLOCNO_HARD_REG_COSTS (a) != NULL 2821 && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL) 2822 for (j = 0; j < hard_regs_num; j++) 2823 ALLOCNO_HARD_REG_COSTS (parent_a)[j] 2824 -= ALLOCNO_HARD_REG_COSTS (a)[j]; 2825 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL 2826 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL) 2827 for (j = 0; j < hard_regs_num; j++) 2828 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j] 2829 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j]; 2830 ALLOCNO_CLASS_COST (parent_a) 2831 -= ALLOCNO_CLASS_COST (a); 2832 ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a); 2833 parent_a = ira_parent_allocno (parent_a); 2834 if (parent_a == NULL) 2835 break; 2836 } 2837 ALLOCNO_COPIES (a) = NULL; 2838 regno_top_level_allocno_map[REGNO (data->reg)] = a; 2839 } 2840 if (mem_dest_p && copy_info_to_removed_store_destinations (i)) 2841 merged_p = true; 2842 } 2843 ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point); 2844 if (merged_p || ira_max_point_before_emit != ira_max_point) 2845 ira_rebuild_start_finish_chains (); 2846 if (new_pseudos_p) 2847 { 2848 sparseset objects_live; 2849 2850 /* Rebuild conflicts. */ 2851 FOR_EACH_ALLOCNO (a, ai) 2852 { 2853 ira_allocno_object_iterator oi; 2854 ira_object_t obj; 2855 2856 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))] 2857 || ALLOCNO_CAP_MEMBER (a) != NULL) 2858 continue; 2859 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi) 2860 { 2861 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) 2862 ira_assert (r->object == obj); 2863 clear_conflicts (obj); 2864 } 2865 } 2866 objects_live = sparseset_alloc (ira_objects_num); 2867 for (i = 0; i < ira_max_point; i++) 2868 { 2869 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next) 2870 { 2871 ira_object_t obj = r->object; 2872 2873 a = OBJECT_ALLOCNO (obj); 2874 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))] 2875 || ALLOCNO_CAP_MEMBER (a) != NULL) 2876 continue; 2877 2878 aclass = ALLOCNO_CLASS (a); 2879 sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj)); 2880 EXECUTE_IF_SET_IN_SPARSESET (objects_live, n) 2881 { 2882 ira_object_t live_obj = ira_object_id_map[n]; 2883 ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj); 2884 enum reg_class live_aclass = ALLOCNO_CLASS (live_a); 2885 2886 if (ira_reg_classes_intersect_p[aclass][live_aclass] 2887 /* Don't set up conflict for the allocno with itself. */ 2888 && live_a != a) 2889 ira_add_conflict (obj, live_obj); 2890 } 2891 } 2892 2893 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next) 2894 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object)); 2895 } 2896 sparseset_free (objects_live); 2897 compress_conflict_vecs (); 2898 } 2899 /* Mark some copies for removing and change allocnos in the rest 2900 copies. */ 2901 FOR_EACH_COPY (cp, ci) 2902 { 2903 if (ALLOCNO_CAP_MEMBER (cp->first) != NULL 2904 || ALLOCNO_CAP_MEMBER (cp->second) != NULL) 2905 { 2906 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) 2907 fprintf 2908 (ira_dump_file, " Remove cp%d:%c%dr%d-%c%dr%d\n", 2909 cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a', 2910 ALLOCNO_NUM (cp->first), 2911 REGNO (allocno_emit_reg (cp->first)), 2912 ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a', 2913 ALLOCNO_NUM (cp->second), 2914 REGNO (allocno_emit_reg (cp->second))); 2915 cp->loop_tree_node = NULL; 2916 continue; 2917 } 2918 first 2919 = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))]; 2920 second 2921 = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))]; 2922 node = cp->loop_tree_node; 2923 if (node == NULL) 2924 keep_p = true; /* It copy generated in ira-emit.c. */ 2925 else 2926 { 2927 /* Check that the copy was not propagated from level on 2928 which we will have different pseudos. */ 2929 node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)]; 2930 node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)]; 2931 keep_p = ((REGNO (allocno_emit_reg (first)) 2932 == REGNO (allocno_emit_reg (node_first))) 2933 && (REGNO (allocno_emit_reg (second)) 2934 == REGNO (allocno_emit_reg (node_second)))); 2935 } 2936 if (keep_p) 2937 { 2938 cp->loop_tree_node = ira_loop_tree_root; 2939 cp->first = first; 2940 cp->second = second; 2941 } 2942 else 2943 { 2944 cp->loop_tree_node = NULL; 2945 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) 2946 fprintf (ira_dump_file, " Remove cp%d:a%dr%d-a%dr%d\n", 2947 cp->num, ALLOCNO_NUM (cp->first), 2948 REGNO (allocno_emit_reg (cp->first)), 2949 ALLOCNO_NUM (cp->second), 2950 REGNO (allocno_emit_reg (cp->second))); 2951 } 2952 } 2953 /* Remove unnecessary allocnos on lower levels of the loop tree. */ 2954 FOR_EACH_ALLOCNO (a, ai) 2955 { 2956 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))] 2957 || ALLOCNO_CAP_MEMBER (a) != NULL) 2958 { 2959 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) 2960 fprintf (ira_dump_file, " Remove a%dr%d\n", 2961 ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a))); 2962 finish_allocno (a); 2963 continue; 2964 } 2965 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root; 2966 ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a)); 2967 ALLOCNO_CAP (a) = NULL; 2968 /* Restore updated costs for assignments from reload. */ 2969 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a); 2970 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a); 2971 if (! ALLOCNO_ASSIGNED_P (a)) 2972 ira_free_allocno_updated_costs (a); 2973 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL); 2974 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL); 2975 } 2976 /* Remove unnecessary copies. */ 2977 FOR_EACH_COPY (cp, ci) 2978 { 2979 if (cp->loop_tree_node == NULL) 2980 { 2981 ira_copies[cp->num] = NULL; 2982 finish_copy (cp); 2983 continue; 2984 } 2985 ira_assert 2986 (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root 2987 && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root); 2988 ira_add_allocno_copy_to_list (cp); 2989 ira_swap_allocno_copy_ends_if_necessary (cp); 2990 } 2991 rebuild_regno_allocno_maps (); 2992 if (ira_max_point != ira_max_point_before_emit) 2993 ira_compress_allocno_live_ranges (); 2994 ira_free (regno_top_level_allocno_map); 2995 } 2996 2997 2998 2999 #ifdef ENABLE_IRA_CHECKING 3000 /* Check creation of all allocnos. Allocnos on lower levels should 3001 have allocnos or caps on all upper levels. */ 3002 static void 3003 check_allocno_creation (void) 3004 { 3005 ira_allocno_t a; 3006 ira_allocno_iterator ai; 3007 ira_loop_tree_node_t loop_tree_node; 3008 3009 FOR_EACH_ALLOCNO (a, ai) 3010 { 3011 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a); 3012 ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos, 3013 ALLOCNO_NUM (a))); 3014 if (loop_tree_node == ira_loop_tree_root) 3015 continue; 3016 if (ALLOCNO_CAP_MEMBER (a) != NULL) 3017 ira_assert (ALLOCNO_CAP (a) != NULL); 3018 else if (ALLOCNO_CAP (a) == NULL) 3019 ira_assert (loop_tree_node->parent 3020 ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL 3021 && bitmap_bit_p (loop_tree_node->border_allocnos, 3022 ALLOCNO_NUM (a))); 3023 } 3024 } 3025 #endif 3026 3027 /* Identify allocnos which prefer a register class with a single hard register. 3028 Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are 3029 less likely to use the preferred singleton register. */ 3030 static void 3031 update_conflict_hard_reg_costs (void) 3032 { 3033 ira_allocno_t a; 3034 ira_allocno_iterator ai; 3035 int i, index, min; 3036 3037 FOR_EACH_ALLOCNO (a, ai) 3038 { 3039 reg_class_t aclass = ALLOCNO_CLASS (a); 3040 reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a)); 3041 3042 if (reg_class_size[(int) pref] != 1) 3043 continue; 3044 index = ira_class_hard_reg_index[(int) aclass] 3045 [ira_class_hard_regs[(int) pref][0]]; 3046 if (index < 0) 3047 continue; 3048 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL 3049 || ALLOCNO_HARD_REG_COSTS (a) == NULL) 3050 continue; 3051 min = INT_MAX; 3052 for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--) 3053 if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a) 3054 && min > ALLOCNO_HARD_REG_COSTS (a)[i]) 3055 min = ALLOCNO_HARD_REG_COSTS (a)[i]; 3056 if (min == INT_MAX) 3057 continue; 3058 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), 3059 aclass, 0); 3060 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] 3061 -= min - ALLOCNO_CLASS_COST (a); 3062 } 3063 } 3064 3065 /* Create a internal representation (IR) for IRA (allocnos, copies, 3066 loop tree nodes). The function returns TRUE if we generate loop 3067 structure (besides nodes representing all function and the basic 3068 blocks) for regional allocation. A true return means that we 3069 really need to flatten IR before the reload. */ 3070 bool 3071 ira_build (void) 3072 { 3073 bool loops_p; 3074 3075 df_analyze (); 3076 initiate_cost_vectors (); 3077 initiate_allocnos (); 3078 initiate_copies (); 3079 create_loop_tree_nodes (); 3080 form_loop_tree (); 3081 create_allocnos (); 3082 ira_costs (); 3083 create_allocno_objects (); 3084 ira_create_allocno_live_ranges (); 3085 remove_unnecessary_regions (false); 3086 ira_compress_allocno_live_ranges (); 3087 update_bad_spill_attribute (); 3088 loops_p = more_one_region_p (); 3089 if (loops_p) 3090 { 3091 propagate_allocno_info (); 3092 create_caps (); 3093 } 3094 ira_tune_allocno_costs (); 3095 #ifdef ENABLE_IRA_CHECKING 3096 check_allocno_creation (); 3097 #endif 3098 setup_min_max_allocno_live_range_point (); 3099 sort_conflict_id_map (); 3100 setup_min_max_conflict_allocno_ids (); 3101 ira_build_conflicts (); 3102 update_conflict_hard_reg_costs (); 3103 if (! ira_conflicts_p) 3104 { 3105 ira_allocno_t a; 3106 ira_allocno_iterator ai; 3107 3108 /* Remove all regions but root one. */ 3109 if (loops_p) 3110 { 3111 remove_unnecessary_regions (true); 3112 loops_p = false; 3113 } 3114 /* We don't save hard registers around calls for fast allocation 3115 -- add caller clobbered registers as conflicting ones to 3116 allocno crossing calls. */ 3117 FOR_EACH_ALLOCNO (a, ai) 3118 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0) 3119 ior_hard_reg_conflicts (a, &call_used_reg_set); 3120 } 3121 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 3122 print_copies (ira_dump_file); 3123 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) 3124 { 3125 int n, nr, nr_big; 3126 ira_allocno_t a; 3127 live_range_t r; 3128 ira_allocno_iterator ai; 3129 3130 n = 0; 3131 nr = 0; 3132 nr_big = 0; 3133 FOR_EACH_ALLOCNO (a, ai) 3134 { 3135 int j, nobj = ALLOCNO_NUM_OBJECTS (a); 3136 3137 if (nobj > 1) 3138 nr_big++; 3139 for (j = 0; j < nobj; j++) 3140 { 3141 ira_object_t obj = ALLOCNO_OBJECT (a, j); 3142 n += OBJECT_NUM_CONFLICTS (obj); 3143 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) 3144 nr++; 3145 } 3146 } 3147 fprintf (ira_dump_file, " regions=%d, blocks=%d, points=%d\n", 3148 current_loops == NULL ? 1 : VEC_length (loop_p, ira_loops.larray), 3149 n_basic_blocks, ira_max_point); 3150 fprintf (ira_dump_file, 3151 " allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n", 3152 ira_allocnos_num, nr_big, ira_copies_num, n, nr); 3153 } 3154 return loops_p; 3155 } 3156 3157 /* Release the data created by function ira_build. */ 3158 void 3159 ira_destroy (void) 3160 { 3161 finish_loop_tree_nodes (); 3162 finish_copies (); 3163 finish_allocnos (); 3164 finish_cost_vectors (); 3165 ira_finish_allocno_live_ranges (); 3166 } 3167