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