1 /* Integrated Register Allocator. Changing code and generating moves. 2 Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011 3 Free Software Foundation, Inc. 4 Contributed by Vladimir Makarov <vmakarov@redhat.com>. 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free 10 Software Foundation; either version 3, or (at your option) any later 11 version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16 for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 /* When we have more one region, we need to change the original RTL 23 code after coloring. Let us consider two allocnos representing the 24 same pseudo-register outside and inside a region respectively. 25 They can get different hard-registers. The reload pass works on 26 pseudo registers basis and there is no way to say the reload that 27 pseudo could be in different registers and it is even more 28 difficult to say in what places of the code the pseudo should have 29 particular hard-registers. So in this case IRA has to create and 30 use a new pseudo-register inside the region and adds code to move 31 allocno values on the region's borders. This is done by the code 32 in this file. 33 34 The code makes top-down traversal of the regions and generate new 35 pseudos and the move code on the region borders. In some 36 complicated cases IRA can create a new pseudo used temporarily to 37 move allocno values when a swap of values stored in two 38 hard-registers is needed (e.g. two allocnos representing different 39 pseudos outside region got respectively hard registers 1 and 2 and 40 the corresponding allocnos inside the region got respectively hard 41 registers 2 and 1). At this stage, the new pseudo is marked as 42 spilled. 43 44 IRA still creates the pseudo-register and the moves on the region 45 borders even when the both corresponding allocnos were assigned to 46 the same hard-register. It is done because, if the reload pass for 47 some reason spills a pseudo-register representing the original 48 pseudo outside or inside the region, the effect will be smaller 49 because another pseudo will still be in the hard-register. In most 50 cases, this is better then spilling the original pseudo in its 51 whole live-range. If reload does not change the allocation for the 52 two pseudo-registers, the trivial move will be removed by 53 post-reload optimizations. 54 55 IRA does not generate a new pseudo and moves for the allocno values 56 if the both allocnos representing an original pseudo inside and 57 outside region assigned to the same hard register when the register 58 pressure in the region for the corresponding pressure class is less 59 than number of available hard registers for given pressure class. 60 61 IRA also does some optimizations to remove redundant moves which is 62 transformed into stores by the reload pass on CFG edges 63 representing exits from the region. 64 65 IRA tries to reduce duplication of code generated on CFG edges 66 which are enters and exits to/from regions by moving some code to 67 the edge sources or destinations when it is possible. */ 68 69 #include "config.h" 70 #include "system.h" 71 #include "coretypes.h" 72 #include "tm.h" 73 #include "regs.h" 74 #include "rtl.h" 75 #include "tm_p.h" 76 #include "target.h" 77 #include "flags.h" 78 #include "obstack.h" 79 #include "bitmap.h" 80 #include "hard-reg-set.h" 81 #include "basic-block.h" 82 #include "expr.h" 83 #include "recog.h" 84 #include "params.h" 85 #include "timevar.h" 86 #include "tree-pass.h" 87 #include "output.h" 88 #include "reload.h" 89 #include "df.h" 90 #include "ira-int.h" 91 92 93 /* Data used to emit live range split insns and to flattening IR. */ 94 ira_emit_data_t ira_allocno_emit_data; 95 96 /* Definitions for vectors of pointers. */ 97 typedef void *void_p; 98 DEF_VEC_P (void_p); 99 DEF_VEC_ALLOC_P (void_p,heap); 100 101 /* Pointers to data allocated for allocnos being created during 102 emitting. Usually there are quite few such allocnos because they 103 are created only for resolving loop in register shuffling. */ 104 static VEC(void_p, heap) *new_allocno_emit_data_vec; 105 106 /* Allocate and initiate the emit data. */ 107 void 108 ira_initiate_emit_data (void) 109 { 110 ira_allocno_t a; 111 ira_allocno_iterator ai; 112 113 ira_allocno_emit_data 114 = (ira_emit_data_t) ira_allocate (ira_allocnos_num 115 * sizeof (struct ira_emit_data)); 116 memset (ira_allocno_emit_data, 0, 117 ira_allocnos_num * sizeof (struct ira_emit_data)); 118 FOR_EACH_ALLOCNO (a, ai) 119 ALLOCNO_ADD_DATA (a) = ira_allocno_emit_data + ALLOCNO_NUM (a); 120 new_allocno_emit_data_vec = VEC_alloc (void_p, heap, 50); 121 122 } 123 124 /* Free the emit data. */ 125 void 126 ira_finish_emit_data (void) 127 { 128 void_p p; 129 ira_allocno_t a; 130 ira_allocno_iterator ai; 131 132 ira_free (ira_allocno_emit_data); 133 FOR_EACH_ALLOCNO (a, ai) 134 ALLOCNO_ADD_DATA (a) = NULL; 135 for (;VEC_length (void_p, new_allocno_emit_data_vec) != 0;) 136 { 137 p = VEC_pop (void_p, new_allocno_emit_data_vec); 138 ira_free (p); 139 } 140 VEC_free (void_p, heap, new_allocno_emit_data_vec); 141 } 142 143 /* Create and return a new allocno with given REGNO and 144 LOOP_TREE_NODE. Allocate emit data for it. */ 145 static ira_allocno_t 146 create_new_allocno (int regno, ira_loop_tree_node_t loop_tree_node) 147 { 148 ira_allocno_t a; 149 150 a = ira_create_allocno (regno, false, loop_tree_node); 151 ALLOCNO_ADD_DATA (a) = ira_allocate (sizeof (struct ira_emit_data)); 152 memset (ALLOCNO_ADD_DATA (a), 0, sizeof (struct ira_emit_data)); 153 VEC_safe_push (void_p, heap, new_allocno_emit_data_vec, ALLOCNO_ADD_DATA (a)); 154 return a; 155 } 156 157 158 159 /* See comments below. */ 160 typedef struct move *move_t; 161 162 /* The structure represents an allocno move. Both allocnos have the 163 same origional regno but different allocation. */ 164 struct move 165 { 166 /* The allocnos involved in the move. */ 167 ira_allocno_t from, to; 168 /* The next move in the move sequence. */ 169 move_t next; 170 /* Used for finding dependencies. */ 171 bool visited_p; 172 /* The size of the following array. */ 173 int deps_num; 174 /* Moves on which given move depends on. Dependency can be cyclic. 175 It means we need a temporary to generates the moves. Sequence 176 A1->A2, B1->B2 where A1 and B2 are assigned to reg R1 and A2 and 177 B1 are assigned to reg R2 is an example of the cyclic 178 dependencies. */ 179 move_t *deps; 180 /* First insn generated for the move. */ 181 rtx insn; 182 }; 183 184 /* Array of moves (indexed by BB index) which should be put at the 185 start/end of the corresponding basic blocks. */ 186 static move_t *at_bb_start, *at_bb_end; 187 188 /* Max regno before renaming some pseudo-registers. For example, the 189 same pseudo-register can be renamed in a loop if its allocation is 190 different outside the loop. */ 191 static int max_regno_before_changing; 192 193 /* Return new move of allocnos TO and FROM. */ 194 static move_t 195 create_move (ira_allocno_t to, ira_allocno_t from) 196 { 197 move_t move; 198 199 move = (move_t) ira_allocate (sizeof (struct move)); 200 move->deps = NULL; 201 move->deps_num = 0; 202 move->to = to; 203 move->from = from; 204 move->next = NULL; 205 move->insn = NULL_RTX; 206 move->visited_p = false; 207 return move; 208 } 209 210 /* Free memory for MOVE and its dependencies. */ 211 static void 212 free_move (move_t move) 213 { 214 if (move->deps != NULL) 215 ira_free (move->deps); 216 ira_free (move); 217 } 218 219 /* Free memory for list of the moves given by its HEAD. */ 220 static void 221 free_move_list (move_t head) 222 { 223 move_t next; 224 225 for (; head != NULL; head = next) 226 { 227 next = head->next; 228 free_move (head); 229 } 230 } 231 232 /* Return TRUE if the move list LIST1 and LIST2 are equal (two 233 moves are equal if they involve the same allocnos). */ 234 static bool 235 eq_move_lists_p (move_t list1, move_t list2) 236 { 237 for (; list1 != NULL && list2 != NULL; 238 list1 = list1->next, list2 = list2->next) 239 if (list1->from != list2->from || list1->to != list2->to) 240 return false; 241 return list1 == list2; 242 } 243 244 /* Print move list LIST into file F. */ 245 static void 246 print_move_list (FILE *f, move_t list) 247 { 248 for (; list != NULL; list = list->next) 249 fprintf (f, " a%dr%d->a%dr%d", 250 ALLOCNO_NUM (list->from), ALLOCNO_REGNO (list->from), 251 ALLOCNO_NUM (list->to), ALLOCNO_REGNO (list->to)); 252 fprintf (f, "\n"); 253 } 254 255 extern void ira_debug_move_list (move_t list); 256 257 /* Print move list LIST into stderr. */ 258 void 259 ira_debug_move_list (move_t list) 260 { 261 print_move_list (stderr, list); 262 } 263 264 /* This recursive function changes pseudo-registers in *LOC if it is 265 necessary. The function returns TRUE if a change was done. */ 266 static bool 267 change_regs (rtx *loc) 268 { 269 int i, regno, result = false; 270 const char *fmt; 271 enum rtx_code code; 272 rtx reg; 273 274 if (*loc == NULL_RTX) 275 return false; 276 code = GET_CODE (*loc); 277 if (code == REG) 278 { 279 regno = REGNO (*loc); 280 if (regno < FIRST_PSEUDO_REGISTER) 281 return false; 282 if (regno >= max_regno_before_changing) 283 /* It is a shared register which was changed already. */ 284 return false; 285 if (ira_curr_regno_allocno_map[regno] == NULL) 286 return false; 287 reg = allocno_emit_reg (ira_curr_regno_allocno_map[regno]); 288 if (reg == *loc) 289 return false; 290 *loc = reg; 291 return true; 292 } 293 294 fmt = GET_RTX_FORMAT (code); 295 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 296 { 297 if (fmt[i] == 'e') 298 result = change_regs (&XEXP (*loc, i)) || result; 299 else if (fmt[i] == 'E') 300 { 301 int j; 302 303 for (j = XVECLEN (*loc, i) - 1; j >= 0; j--) 304 result = change_regs (&XVECEXP (*loc, i, j)) || result; 305 } 306 } 307 return result; 308 } 309 310 /* Attach MOVE to the edge E. The move is attached to the head of the 311 list if HEAD_P is TRUE. */ 312 static void 313 add_to_edge_list (edge e, move_t move, bool head_p) 314 { 315 move_t last; 316 317 if (head_p || e->aux == NULL) 318 { 319 move->next = (move_t) e->aux; 320 e->aux = move; 321 } 322 else 323 { 324 for (last = (move_t) e->aux; last->next != NULL; last = last->next) 325 ; 326 last->next = move; 327 move->next = NULL; 328 } 329 } 330 331 /* Create and return new pseudo-register with the same attributes as 332 ORIGINAL_REG. */ 333 static rtx 334 create_new_reg (rtx original_reg) 335 { 336 rtx new_reg; 337 338 new_reg = gen_reg_rtx (GET_MODE (original_reg)); 339 ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg); 340 REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg); 341 REG_POINTER (new_reg) = REG_POINTER (original_reg); 342 REG_ATTRS (new_reg) = REG_ATTRS (original_reg); 343 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 344 fprintf (ira_dump_file, " Creating newreg=%i from oldreg=%i\n", 345 REGNO (new_reg), REGNO (original_reg)); 346 return new_reg; 347 } 348 349 /* Return TRUE if loop given by SUBNODE inside the loop given by 350 NODE. */ 351 static bool 352 subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node) 353 { 354 for (; subnode != NULL; subnode = subnode->parent) 355 if (subnode == node) 356 return true; 357 return false; 358 } 359 360 /* Set up member `reg' to REG for allocnos which has the same regno as 361 ALLOCNO and which are inside the loop corresponding to ALLOCNO. */ 362 static void 363 set_allocno_reg (ira_allocno_t allocno, rtx reg) 364 { 365 int regno; 366 ira_allocno_t a; 367 ira_loop_tree_node_t node; 368 369 node = ALLOCNO_LOOP_TREE_NODE (allocno); 370 for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)]; 371 a != NULL; 372 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 373 if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node)) 374 ALLOCNO_EMIT_DATA (a)->reg = reg; 375 for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a)) 376 ALLOCNO_EMIT_DATA (a)->reg = reg; 377 regno = ALLOCNO_REGNO (allocno); 378 for (a = allocno;;) 379 { 380 if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL) 381 { 382 node = node->parent; 383 if (node == NULL) 384 break; 385 a = node->regno_allocno_map[regno]; 386 } 387 if (a == NULL) 388 continue; 389 if (ALLOCNO_EMIT_DATA (a)->child_renamed_p) 390 break; 391 ALLOCNO_EMIT_DATA (a)->child_renamed_p = true; 392 } 393 } 394 395 /* Return true if there is an entry to given loop not from its parent 396 (or grandparent) block. For example, it is possible for two 397 adjacent loops inside another loop. */ 398 static bool 399 entered_from_non_parent_p (ira_loop_tree_node_t loop_node) 400 { 401 ira_loop_tree_node_t bb_node, src_loop_node, parent; 402 edge e; 403 edge_iterator ei; 404 405 for (bb_node = loop_node->children; 406 bb_node != NULL; 407 bb_node = bb_node->next) 408 if (bb_node->bb != NULL) 409 { 410 FOR_EACH_EDGE (e, ei, bb_node->bb->preds) 411 if (e->src != ENTRY_BLOCK_PTR 412 && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node) 413 { 414 for (parent = src_loop_node->parent; 415 parent != NULL; 416 parent = parent->parent) 417 if (parent == loop_node) 418 break; 419 if (parent != NULL) 420 /* That is an exit from a nested loop -- skip it. */ 421 continue; 422 for (parent = loop_node->parent; 423 parent != NULL; 424 parent = parent->parent) 425 if (src_loop_node == parent) 426 break; 427 if (parent == NULL) 428 return true; 429 } 430 } 431 return false; 432 } 433 434 /* Set up ENTERED_FROM_NON_PARENT_P for each loop region. */ 435 static void 436 setup_entered_from_non_parent_p (void) 437 { 438 unsigned int i; 439 loop_p loop; 440 441 ira_assert (current_loops != NULL); 442 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop) 443 if (ira_loop_nodes[i].regno_allocno_map != NULL) 444 ira_loop_nodes[i].entered_from_non_parent_p 445 = entered_from_non_parent_p (&ira_loop_nodes[i]); 446 } 447 448 /* Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to 449 DEST_ALLOCNO (assigned to memory) can be removed beacuse it does 450 not change value of the destination. One possible reason for this 451 is the situation when SRC_ALLOCNO is not modified in the 452 corresponding loop. */ 453 static bool 454 store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno) 455 { 456 int regno, orig_regno; 457 ira_allocno_t a; 458 ira_loop_tree_node_t node; 459 460 ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL 461 && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL); 462 orig_regno = ALLOCNO_REGNO (src_allocno); 463 regno = REGNO (allocno_emit_reg (dest_allocno)); 464 for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno); 465 node != NULL; 466 node = node->parent) 467 { 468 a = node->regno_allocno_map[orig_regno]; 469 ira_assert (a != NULL); 470 if (REGNO (allocno_emit_reg (a)) == (unsigned) regno) 471 /* We achieved the destination and everything is ok. */ 472 return true; 473 else if (bitmap_bit_p (node->modified_regnos, orig_regno)) 474 return false; 475 else if (node->entered_from_non_parent_p) 476 /* If there is a path from a destination loop block to the 477 source loop header containing basic blocks of non-parents 478 (grandparents) of the source loop, we should have checked 479 modifications of the pseudo on this path too to decide 480 about possibility to remove the store. It could be done by 481 solving a data-flow problem. Unfortunately such global 482 solution would complicate IR flattening. Therefore we just 483 prohibit removal of the store in such complicated case. */ 484 return false; 485 } 486 /* It is actually a loop entry -- do not remove the store. */ 487 return false; 488 } 489 490 /* Generate and attach moves to the edge E. This looks at the final 491 regnos of allocnos living on the edge with the same original regno 492 to figure out when moves should be generated. */ 493 static void 494 generate_edge_moves (edge e) 495 { 496 ira_loop_tree_node_t src_loop_node, dest_loop_node; 497 unsigned int regno; 498 bitmap_iterator bi; 499 ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map; 500 move_t move; 501 502 src_loop_node = IRA_BB_NODE (e->src)->parent; 503 dest_loop_node = IRA_BB_NODE (e->dest)->parent; 504 e->aux = NULL; 505 if (src_loop_node == dest_loop_node) 506 return; 507 src_map = src_loop_node->regno_allocno_map; 508 dest_map = dest_loop_node->regno_allocno_map; 509 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (e->dest), 510 FIRST_PSEUDO_REGISTER, regno, bi) 511 if (bitmap_bit_p (DF_LR_OUT (e->src), regno)) 512 { 513 src_allocno = src_map[regno]; 514 dest_allocno = dest_map[regno]; 515 if (REGNO (allocno_emit_reg (src_allocno)) 516 == REGNO (allocno_emit_reg (dest_allocno))) 517 continue; 518 /* Remove unnecessary stores at the region exit. We should do 519 this for readonly memory for sure and this is guaranteed by 520 that we never generate moves on region borders (see 521 checking ira_reg_equiv_invariant_p in function 522 change_loop). */ 523 if (ALLOCNO_HARD_REGNO (dest_allocno) < 0 524 && ALLOCNO_HARD_REGNO (src_allocno) >= 0 525 && store_can_be_removed_p (src_allocno, dest_allocno)) 526 { 527 ALLOCNO_EMIT_DATA (src_allocno)->mem_optimized_dest = dest_allocno; 528 ALLOCNO_EMIT_DATA (dest_allocno)->mem_optimized_dest_p = true; 529 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 530 fprintf (ira_dump_file, " Remove r%d:a%d->a%d(mem)\n", 531 regno, ALLOCNO_NUM (src_allocno), 532 ALLOCNO_NUM (dest_allocno)); 533 continue; 534 } 535 move = create_move (dest_allocno, src_allocno); 536 add_to_edge_list (e, move, true); 537 } 538 } 539 540 /* Bitmap of allocnos local for the current loop. */ 541 static bitmap local_allocno_bitmap; 542 543 /* This bitmap is used to find that we need to generate and to use a 544 new pseudo-register when processing allocnos with the same original 545 regno. */ 546 static bitmap used_regno_bitmap; 547 548 /* This bitmap contains regnos of allocnos which were renamed locally 549 because the allocnos correspond to disjoint live ranges in loops 550 with a common parent. */ 551 static bitmap renamed_regno_bitmap; 552 553 /* Change (if necessary) pseudo-registers inside loop given by loop 554 tree node NODE. */ 555 static void 556 change_loop (ira_loop_tree_node_t node) 557 { 558 bitmap_iterator bi; 559 unsigned int i; 560 int regno; 561 bool used_p; 562 ira_allocno_t allocno, parent_allocno, *map; 563 rtx insn, original_reg; 564 enum reg_class aclass, pclass; 565 ira_loop_tree_node_t parent; 566 567 if (node != ira_loop_tree_root) 568 { 569 ira_assert (current_loops != NULL); 570 571 if (node->bb != NULL) 572 { 573 FOR_BB_INSNS (node->bb, insn) 574 if (INSN_P (insn) && change_regs (&insn)) 575 { 576 df_insn_rescan (insn); 577 df_notes_rescan (insn); 578 } 579 return; 580 } 581 582 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 583 fprintf (ira_dump_file, 584 " Changing RTL for loop %d (header bb%d)\n", 585 node->loop_num, node->loop->header->index); 586 587 parent = ira_curr_loop_tree_node->parent; 588 map = parent->regno_allocno_map; 589 EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos, 590 0, i, bi) 591 { 592 allocno = ira_allocnos[i]; 593 regno = ALLOCNO_REGNO (allocno); 594 aclass = ALLOCNO_CLASS (allocno); 595 pclass = ira_pressure_class_translate[aclass]; 596 parent_allocno = map[regno]; 597 ira_assert (regno < ira_reg_equiv_len); 598 /* We generate the same hard register move because the 599 reload pass can put an allocno into memory in this case 600 we will have live range splitting. If it does not happen 601 such the same hard register moves will be removed. The 602 worst case when the both allocnos are put into memory by 603 the reload is very rare. */ 604 if (parent_allocno != NULL 605 && (ALLOCNO_HARD_REGNO (allocno) 606 == ALLOCNO_HARD_REGNO (parent_allocno)) 607 && (ALLOCNO_HARD_REGNO (allocno) < 0 608 || (parent->reg_pressure[pclass] + 1 609 <= ira_available_class_regs[pclass]) 610 || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs 611 [ALLOCNO_MODE (allocno)], 612 ALLOCNO_HARD_REGNO (allocno)) 613 /* don't create copies because reload can spill an 614 allocno set by copy although the allocno will not 615 get memory slot. */ 616 || ira_reg_equiv_invariant_p[regno] 617 || ira_reg_equiv_const[regno] != NULL_RTX)) 618 continue; 619 original_reg = allocno_emit_reg (allocno); 620 if (parent_allocno == NULL 621 || (REGNO (allocno_emit_reg (parent_allocno)) 622 == REGNO (original_reg))) 623 { 624 if (internal_flag_ira_verbose > 3 && ira_dump_file) 625 fprintf (ira_dump_file, " %i vs parent %i:", 626 ALLOCNO_HARD_REGNO (allocno), 627 ALLOCNO_HARD_REGNO (parent_allocno)); 628 set_allocno_reg (allocno, create_new_reg (original_reg)); 629 } 630 } 631 } 632 /* Rename locals: Local allocnos with same regno in different loops 633 might get the different hard register. So we need to change 634 ALLOCNO_REG. */ 635 bitmap_and_compl (local_allocno_bitmap, 636 ira_curr_loop_tree_node->all_allocnos, 637 ira_curr_loop_tree_node->border_allocnos); 638 EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi) 639 { 640 allocno = ira_allocnos[i]; 641 regno = ALLOCNO_REGNO (allocno); 642 if (ALLOCNO_CAP_MEMBER (allocno) != NULL) 643 continue; 644 used_p = !bitmap_set_bit (used_regno_bitmap, regno); 645 ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true; 646 if (! used_p) 647 continue; 648 bitmap_set_bit (renamed_regno_bitmap, regno); 649 set_allocno_reg (allocno, create_new_reg (allocno_emit_reg (allocno))); 650 } 651 } 652 653 /* Process to set up flag somewhere_renamed_p. */ 654 static void 655 set_allocno_somewhere_renamed_p (void) 656 { 657 unsigned int regno; 658 ira_allocno_t allocno; 659 ira_allocno_iterator ai; 660 661 FOR_EACH_ALLOCNO (allocno, ai) 662 { 663 regno = ALLOCNO_REGNO (allocno); 664 if (bitmap_bit_p (renamed_regno_bitmap, regno) 665 && REGNO (allocno_emit_reg (allocno)) == regno) 666 ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true; 667 } 668 } 669 670 /* Return TRUE if move lists on all edges given in vector VEC are 671 equal. */ 672 static bool 673 eq_edge_move_lists_p (VEC(edge,gc) *vec) 674 { 675 move_t list; 676 int i; 677 678 list = (move_t) EDGE_I (vec, 0)->aux; 679 for (i = EDGE_COUNT (vec) - 1; i > 0; i--) 680 if (! eq_move_lists_p (list, (move_t) EDGE_I (vec, i)->aux)) 681 return false; 682 return true; 683 } 684 685 /* Look at all entry edges (if START_P) or exit edges of basic block 686 BB and put move lists at the BB start or end if it is possible. In 687 other words, this decreases code duplication of allocno moves. */ 688 static void 689 unify_moves (basic_block bb, bool start_p) 690 { 691 int i; 692 edge e; 693 move_t list; 694 VEC(edge,gc) *vec; 695 696 vec = (start_p ? bb->preds : bb->succs); 697 if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec)) 698 return; 699 e = EDGE_I (vec, 0); 700 list = (move_t) e->aux; 701 if (! start_p && control_flow_insn_p (BB_END (bb))) 702 return; 703 e->aux = NULL; 704 for (i = EDGE_COUNT (vec) - 1; i > 0; i--) 705 { 706 e = EDGE_I (vec, i); 707 free_move_list ((move_t) e->aux); 708 e->aux = NULL; 709 } 710 if (start_p) 711 at_bb_start[bb->index] = list; 712 else 713 at_bb_end[bb->index] = list; 714 } 715 716 /* Last move (in move sequence being processed) setting up the 717 corresponding hard register. */ 718 static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER]; 719 720 /* If the element value is equal to CURR_TICK then the corresponding 721 element in `hard_regno_last_set' is defined and correct. */ 722 static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER]; 723 724 /* Last move (in move sequence being processed) setting up the 725 corresponding allocno. */ 726 static move_t *allocno_last_set; 727 728 /* If the element value is equal to CURR_TICK then the corresponding 729 element in . `allocno_last_set' is defined and correct. */ 730 static int *allocno_last_set_check; 731 732 /* Definition of vector of moves. */ 733 DEF_VEC_P(move_t); 734 DEF_VEC_ALLOC_P(move_t, heap); 735 736 /* This vec contains moves sorted topologically (depth-first) on their 737 dependency graph. */ 738 static VEC(move_t,heap) *move_vec; 739 740 /* The variable value is used to check correctness of values of 741 elements of arrays `hard_regno_last_set' and 742 `allocno_last_set_check'. */ 743 static int curr_tick; 744 745 /* This recursive function traverses dependencies of MOVE and produces 746 topological sorting (in depth-first order). */ 747 static void 748 traverse_moves (move_t move) 749 { 750 int i; 751 752 if (move->visited_p) 753 return; 754 move->visited_p = true; 755 for (i = move->deps_num - 1; i >= 0; i--) 756 traverse_moves (move->deps[i]); 757 VEC_safe_push (move_t, heap, move_vec, move); 758 } 759 760 /* Remove unnecessary moves in the LIST, makes topological sorting, 761 and removes cycles on hard reg dependencies by introducing new 762 allocnos assigned to memory and additional moves. It returns the 763 result move list. */ 764 static move_t 765 modify_move_list (move_t list) 766 { 767 int i, n, nregs, hard_regno; 768 ira_allocno_t to, from; 769 move_t move, new_move, set_move, first, last; 770 771 if (list == NULL) 772 return NULL; 773 /* Creat move deps. */ 774 curr_tick++; 775 for (move = list; move != NULL; move = move->next) 776 { 777 to = move->to; 778 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0) 779 continue; 780 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)]; 781 for (i = 0; i < nregs; i++) 782 { 783 hard_regno_last_set[hard_regno + i] = move; 784 hard_regno_last_set_check[hard_regno + i] = curr_tick; 785 } 786 } 787 for (move = list; move != NULL; move = move->next) 788 { 789 from = move->from; 790 to = move->to; 791 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0) 792 { 793 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)]; 794 for (n = i = 0; i < nregs; i++) 795 if (hard_regno_last_set_check[hard_regno + i] == curr_tick 796 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to) 797 != ALLOCNO_REGNO (from))) 798 n++; 799 move->deps = (move_t *) ira_allocate (n * sizeof (move_t)); 800 for (n = i = 0; i < nregs; i++) 801 if (hard_regno_last_set_check[hard_regno + i] == curr_tick 802 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to) 803 != ALLOCNO_REGNO (from))) 804 move->deps[n++] = hard_regno_last_set[hard_regno + i]; 805 move->deps_num = n; 806 } 807 } 808 /* Toplogical sorting: */ 809 VEC_truncate (move_t, move_vec, 0); 810 for (move = list; move != NULL; move = move->next) 811 traverse_moves (move); 812 last = NULL; 813 for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--) 814 { 815 move = VEC_index (move_t, move_vec, i); 816 move->next = NULL; 817 if (last != NULL) 818 last->next = move; 819 last = move; 820 } 821 first = VEC_last (move_t, move_vec); 822 /* Removing cycles: */ 823 curr_tick++; 824 VEC_truncate (move_t, move_vec, 0); 825 for (move = first; move != NULL; move = move->next) 826 { 827 from = move->from; 828 to = move->to; 829 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0) 830 { 831 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)]; 832 for (i = 0; i < nregs; i++) 833 if (hard_regno_last_set_check[hard_regno + i] == curr_tick 834 && ALLOCNO_HARD_REGNO 835 (hard_regno_last_set[hard_regno + i]->to) >= 0) 836 { 837 int n, j; 838 ira_allocno_t new_allocno; 839 840 set_move = hard_regno_last_set[hard_regno + i]; 841 /* It does not matter what loop_tree_node (of TO or 842 FROM) to use for the new allocno because of 843 subsequent IRA internal representation 844 flattening. */ 845 new_allocno 846 = create_new_allocno (ALLOCNO_REGNO (set_move->to), 847 ALLOCNO_LOOP_TREE_NODE (set_move->to)); 848 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to); 849 ira_set_allocno_class (new_allocno, 850 ALLOCNO_CLASS (set_move->to)); 851 ira_create_allocno_objects (new_allocno); 852 ALLOCNO_ASSIGNED_P (new_allocno) = true; 853 ALLOCNO_HARD_REGNO (new_allocno) = -1; 854 ALLOCNO_EMIT_DATA (new_allocno)->reg 855 = create_new_reg (allocno_emit_reg (set_move->to)); 856 857 /* Make it possibly conflicting with all earlier 858 created allocnos. Cases where temporary allocnos 859 created to remove the cycles are quite rare. */ 860 n = ALLOCNO_NUM_OBJECTS (new_allocno); 861 gcc_assert (n == ALLOCNO_NUM_OBJECTS (set_move->to)); 862 for (j = 0; j < n; j++) 863 { 864 ira_object_t new_obj = ALLOCNO_OBJECT (new_allocno, j); 865 866 OBJECT_MIN (new_obj) = 0; 867 OBJECT_MAX (new_obj) = ira_objects_num - 1; 868 } 869 870 new_move = create_move (set_move->to, new_allocno); 871 set_move->to = new_allocno; 872 VEC_safe_push (move_t, heap, move_vec, new_move); 873 ira_move_loops_num++; 874 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 875 fprintf (ira_dump_file, 876 " Creating temporary allocno a%dr%d\n", 877 ALLOCNO_NUM (new_allocno), 878 REGNO (allocno_emit_reg (new_allocno))); 879 } 880 } 881 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0) 882 continue; 883 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)]; 884 for (i = 0; i < nregs; i++) 885 { 886 hard_regno_last_set[hard_regno + i] = move; 887 hard_regno_last_set_check[hard_regno + i] = curr_tick; 888 } 889 } 890 for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--) 891 { 892 move = VEC_index (move_t, move_vec, i); 893 move->next = NULL; 894 last->next = move; 895 last = move; 896 } 897 return first; 898 } 899 900 /* Generate RTX move insns from the move list LIST. This updates 901 allocation cost using move execution frequency FREQ. */ 902 static rtx 903 emit_move_list (move_t list, int freq) 904 { 905 int cost, regno; 906 rtx result, insn, set, to; 907 enum machine_mode mode; 908 enum reg_class aclass; 909 910 start_sequence (); 911 for (; list != NULL; list = list->next) 912 { 913 start_sequence (); 914 emit_move_insn (allocno_emit_reg (list->to), 915 allocno_emit_reg (list->from)); 916 list->insn = get_insns (); 917 end_sequence (); 918 for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn)) 919 { 920 /* The reload needs to have set up insn codes. If the 921 reload sets up insn codes by itself, it may fail because 922 insns will have hard registers instead of pseudos and 923 there may be no machine insn with given hard 924 registers. */ 925 recog_memoized (insn); 926 /* Add insn to equiv init insn list if it is necessary. 927 Otherwise reload will not remove this insn if it decides 928 to use the equivalence. */ 929 if ((set = single_set (insn)) != NULL_RTX) 930 { 931 to = SET_DEST (set); 932 if (GET_CODE (to) == SUBREG) 933 to = SUBREG_REG (to); 934 ira_assert (REG_P (to)); 935 regno = REGNO (to); 936 if (regno >= ira_reg_equiv_len 937 || (! ira_reg_equiv_invariant_p[regno] 938 && ira_reg_equiv_const[regno] == NULL_RTX)) 939 continue; /* regno has no equivalence. */ 940 ira_assert ((int) VEC_length (reg_equivs_t, reg_equivs) 941 >= ira_reg_equiv_len); 942 reg_equiv_init (regno) 943 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno)); 944 } 945 } 946 emit_insn (list->insn); 947 mode = ALLOCNO_MODE (list->to); 948 aclass = ALLOCNO_CLASS (list->to); 949 cost = 0; 950 if (ALLOCNO_HARD_REGNO (list->to) < 0) 951 { 952 if (ALLOCNO_HARD_REGNO (list->from) >= 0) 953 { 954 cost = ira_memory_move_cost[mode][aclass][0] * freq; 955 ira_store_cost += cost; 956 } 957 } 958 else if (ALLOCNO_HARD_REGNO (list->from) < 0) 959 { 960 if (ALLOCNO_HARD_REGNO (list->to) >= 0) 961 { 962 cost = ira_memory_move_cost[mode][aclass][0] * freq; 963 ira_load_cost += cost; 964 } 965 } 966 else 967 { 968 ira_init_register_move_cost_if_necessary (mode); 969 cost = ira_register_move_cost[mode][aclass][aclass] * freq; 970 ira_shuffle_cost += cost; 971 } 972 ira_overall_cost += cost; 973 } 974 result = get_insns (); 975 end_sequence (); 976 return result; 977 } 978 979 /* Generate RTX move insns from move lists attached to basic blocks 980 and edges. */ 981 static void 982 emit_moves (void) 983 { 984 basic_block bb; 985 edge_iterator ei; 986 edge e; 987 rtx insns, tmp; 988 989 FOR_EACH_BB (bb) 990 { 991 if (at_bb_start[bb->index] != NULL) 992 { 993 at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]); 994 insns = emit_move_list (at_bb_start[bb->index], 995 REG_FREQ_FROM_BB (bb)); 996 tmp = BB_HEAD (bb); 997 if (LABEL_P (tmp)) 998 tmp = NEXT_INSN (tmp); 999 if (NOTE_INSN_BASIC_BLOCK_P (tmp)) 1000 tmp = NEXT_INSN (tmp); 1001 if (tmp == BB_HEAD (bb)) 1002 emit_insn_before (insns, tmp); 1003 else if (tmp != NULL_RTX) 1004 emit_insn_after (insns, PREV_INSN (tmp)); 1005 else 1006 emit_insn_after (insns, get_last_insn ()); 1007 } 1008 1009 if (at_bb_end[bb->index] != NULL) 1010 { 1011 at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]); 1012 insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb)); 1013 ira_assert (! control_flow_insn_p (BB_END (bb))); 1014 emit_insn_after (insns, BB_END (bb)); 1015 } 1016 1017 FOR_EACH_EDGE (e, ei, bb->succs) 1018 { 1019 if (e->aux == NULL) 1020 continue; 1021 ira_assert ((e->flags & EDGE_ABNORMAL) == 0 1022 || ! EDGE_CRITICAL_P (e)); 1023 e->aux = modify_move_list ((move_t) e->aux); 1024 insert_insn_on_edge 1025 (emit_move_list ((move_t) e->aux, 1026 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))), 1027 e); 1028 if (e->src->next_bb != e->dest) 1029 ira_additional_jumps_num++; 1030 } 1031 } 1032 } 1033 1034 /* Update costs of A and corresponding allocnos on upper levels on the 1035 loop tree from reading (if READ_P) or writing A on an execution 1036 path with FREQ. */ 1037 static void 1038 update_costs (ira_allocno_t a, bool read_p, int freq) 1039 { 1040 ira_loop_tree_node_t parent; 1041 1042 for (;;) 1043 { 1044 ALLOCNO_NREFS (a)++; 1045 ALLOCNO_FREQ (a) += freq; 1046 ALLOCNO_MEMORY_COST (a) 1047 += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)] 1048 [read_p ? 1 : 0] * freq); 1049 if (ALLOCNO_CAP (a) != NULL) 1050 a = ALLOCNO_CAP (a); 1051 else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL 1052 || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL) 1053 break; 1054 } 1055 } 1056 1057 /* Process moves from LIST with execution FREQ to add ranges, copies, 1058 and modify costs for allocnos involved in the moves. All regnos 1059 living through the list is in LIVE_THROUGH, and the loop tree node 1060 used to find corresponding allocnos is NODE. */ 1061 static void 1062 add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node, 1063 bitmap live_through, int freq) 1064 { 1065 int start, n; 1066 unsigned int regno; 1067 move_t move; 1068 ira_allocno_t a; 1069 ira_copy_t cp; 1070 live_range_t r; 1071 bitmap_iterator bi; 1072 HARD_REG_SET hard_regs_live; 1073 1074 if (list == NULL) 1075 return; 1076 n = 0; 1077 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi) 1078 n++; 1079 REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through); 1080 /* This is a trick to guarantee that new ranges is not merged with 1081 the old ones. */ 1082 ira_max_point++; 1083 start = ira_max_point; 1084 for (move = list; move != NULL; move = move->next) 1085 { 1086 ira_allocno_t from = move->from; 1087 ira_allocno_t to = move->to; 1088 int nr, i; 1089 1090 bitmap_clear_bit (live_through, ALLOCNO_REGNO (from)); 1091 bitmap_clear_bit (live_through, ALLOCNO_REGNO (to)); 1092 1093 nr = ALLOCNO_NUM_OBJECTS (to); 1094 for (i = 0; i < nr; i++) 1095 { 1096 ira_object_t to_obj = ALLOCNO_OBJECT (to, i); 1097 if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL) 1098 { 1099 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 1100 fprintf (ira_dump_file, " Allocate conflicts for a%dr%d\n", 1101 ALLOCNO_NUM (to), REGNO (allocno_emit_reg (to))); 1102 ira_allocate_object_conflicts (to_obj, n); 1103 } 1104 } 1105 ior_hard_reg_conflicts (from, &hard_regs_live); 1106 ior_hard_reg_conflicts (to, &hard_regs_live); 1107 1108 update_costs (from, true, freq); 1109 update_costs (to, false, freq); 1110 cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL); 1111 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 1112 fprintf (ira_dump_file, " Adding cp%d:a%dr%d-a%dr%d\n", 1113 cp->num, ALLOCNO_NUM (cp->first), 1114 REGNO (allocno_emit_reg (cp->first)), 1115 ALLOCNO_NUM (cp->second), 1116 REGNO (allocno_emit_reg (cp->second))); 1117 1118 nr = ALLOCNO_NUM_OBJECTS (from); 1119 for (i = 0; i < nr; i++) 1120 { 1121 ira_object_t from_obj = ALLOCNO_OBJECT (from, i); 1122 r = OBJECT_LIVE_RANGES (from_obj); 1123 if (r == NULL || r->finish >= 0) 1124 { 1125 ira_add_live_range_to_object (from_obj, start, ira_max_point); 1126 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 1127 fprintf (ira_dump_file, 1128 " Adding range [%d..%d] to allocno a%dr%d\n", 1129 start, ira_max_point, ALLOCNO_NUM (from), 1130 REGNO (allocno_emit_reg (from))); 1131 } 1132 else 1133 { 1134 r->finish = ira_max_point; 1135 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 1136 fprintf (ira_dump_file, 1137 " Adding range [%d..%d] to allocno a%dr%d\n", 1138 r->start, ira_max_point, ALLOCNO_NUM (from), 1139 REGNO (allocno_emit_reg (from))); 1140 } 1141 } 1142 ira_max_point++; 1143 nr = ALLOCNO_NUM_OBJECTS (to); 1144 for (i = 0; i < nr; i++) 1145 { 1146 ira_object_t to_obj = ALLOCNO_OBJECT (to, i); 1147 ira_add_live_range_to_object (to_obj, ira_max_point, -1); 1148 } 1149 ira_max_point++; 1150 } 1151 for (move = list; move != NULL; move = move->next) 1152 { 1153 int nr, i; 1154 nr = ALLOCNO_NUM_OBJECTS (move->to); 1155 for (i = 0; i < nr; i++) 1156 { 1157 ira_object_t to_obj = ALLOCNO_OBJECT (move->to, i); 1158 r = OBJECT_LIVE_RANGES (to_obj); 1159 if (r->finish < 0) 1160 { 1161 r->finish = ira_max_point - 1; 1162 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 1163 fprintf (ira_dump_file, 1164 " Adding range [%d..%d] to allocno a%dr%d\n", 1165 r->start, r->finish, ALLOCNO_NUM (move->to), 1166 REGNO (allocno_emit_reg (move->to))); 1167 } 1168 } 1169 } 1170 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi) 1171 { 1172 ira_allocno_t to; 1173 int nr, i; 1174 1175 a = node->regno_allocno_map[regno]; 1176 if ((to = ALLOCNO_EMIT_DATA (a)->mem_optimized_dest) != NULL) 1177 a = to; 1178 nr = ALLOCNO_NUM_OBJECTS (a); 1179 for (i = 0; i < nr; i++) 1180 { 1181 ira_object_t obj = ALLOCNO_OBJECT (a, i); 1182 ira_add_live_range_to_object (obj, start, ira_max_point - 1); 1183 } 1184 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 1185 fprintf 1186 (ira_dump_file, 1187 " Adding range [%d..%d] to live through %s allocno a%dr%d\n", 1188 start, ira_max_point - 1, 1189 to != NULL ? "upper level" : "", 1190 ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a))); 1191 } 1192 } 1193 1194 /* Process all move list to add ranges, conflicts, copies, and modify 1195 costs for allocnos involved in the moves. */ 1196 static void 1197 add_ranges_and_copies (void) 1198 { 1199 basic_block bb; 1200 edge_iterator ei; 1201 edge e; 1202 ira_loop_tree_node_t node; 1203 bitmap live_through; 1204 1205 live_through = ira_allocate_bitmap (); 1206 FOR_EACH_BB (bb) 1207 { 1208 /* It does not matter what loop_tree_node (of source or 1209 destination block) to use for searching allocnos by their 1210 regnos because of subsequent IR flattening. */ 1211 node = IRA_BB_NODE (bb)->parent; 1212 bitmap_copy (live_through, DF_LR_IN (bb)); 1213 add_range_and_copies_from_move_list 1214 (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb)); 1215 bitmap_copy (live_through, DF_LR_OUT (bb)); 1216 add_range_and_copies_from_move_list 1217 (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb)); 1218 FOR_EACH_EDGE (e, ei, bb->succs) 1219 { 1220 bitmap_and (live_through, DF_LR_IN (e->dest), DF_LR_OUT (bb)); 1221 add_range_and_copies_from_move_list 1222 ((move_t) e->aux, node, live_through, 1223 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))); 1224 } 1225 } 1226 ira_free_bitmap (live_through); 1227 } 1228 1229 /* The entry function changes code and generates shuffling allocnos on 1230 region borders for the regional (LOOPS_P is TRUE in this case) 1231 register allocation. */ 1232 void 1233 ira_emit (bool loops_p) 1234 { 1235 basic_block bb; 1236 rtx insn; 1237 edge_iterator ei; 1238 edge e; 1239 ira_allocno_t a; 1240 ira_allocno_iterator ai; 1241 1242 FOR_EACH_ALLOCNO (a, ai) 1243 ALLOCNO_EMIT_DATA (a)->reg = regno_reg_rtx[ALLOCNO_REGNO (a)]; 1244 if (! loops_p) 1245 return; 1246 at_bb_start = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block); 1247 memset (at_bb_start, 0, sizeof (move_t) * last_basic_block); 1248 at_bb_end = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block); 1249 memset (at_bb_end, 0, sizeof (move_t) * last_basic_block); 1250 local_allocno_bitmap = ira_allocate_bitmap (); 1251 used_regno_bitmap = ira_allocate_bitmap (); 1252 renamed_regno_bitmap = ira_allocate_bitmap (); 1253 max_regno_before_changing = max_reg_num (); 1254 ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL); 1255 set_allocno_somewhere_renamed_p (); 1256 ira_free_bitmap (used_regno_bitmap); 1257 ira_free_bitmap (renamed_regno_bitmap); 1258 ira_free_bitmap (local_allocno_bitmap); 1259 setup_entered_from_non_parent_p (); 1260 FOR_EACH_BB (bb) 1261 { 1262 at_bb_start[bb->index] = NULL; 1263 at_bb_end[bb->index] = NULL; 1264 FOR_EACH_EDGE (e, ei, bb->succs) 1265 if (e->dest != EXIT_BLOCK_PTR) 1266 generate_edge_moves (e); 1267 } 1268 allocno_last_set 1269 = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ()); 1270 allocno_last_set_check 1271 = (int *) ira_allocate (sizeof (int) * max_reg_num ()); 1272 memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ()); 1273 memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check)); 1274 curr_tick = 0; 1275 FOR_EACH_BB (bb) 1276 unify_moves (bb, true); 1277 FOR_EACH_BB (bb) 1278 unify_moves (bb, false); 1279 move_vec = VEC_alloc (move_t, heap, ira_allocnos_num); 1280 emit_moves (); 1281 add_ranges_and_copies (); 1282 /* Clean up: */ 1283 FOR_EACH_BB (bb) 1284 { 1285 free_move_list (at_bb_start[bb->index]); 1286 free_move_list (at_bb_end[bb->index]); 1287 FOR_EACH_EDGE (e, ei, bb->succs) 1288 { 1289 free_move_list ((move_t) e->aux); 1290 e->aux = NULL; 1291 } 1292 } 1293 VEC_free (move_t, heap, move_vec); 1294 ira_free (allocno_last_set_check); 1295 ira_free (allocno_last_set); 1296 commit_edge_insertions (); 1297 /* Fix insn codes. It is necessary to do it before reload because 1298 reload assumes initial insn codes defined. The insn codes can be 1299 invalidated by CFG infrastructure for example in jump 1300 redirection. */ 1301 FOR_EACH_BB (bb) 1302 FOR_BB_INSNS_REVERSE (bb, insn) 1303 if (INSN_P (insn)) 1304 recog_memoized (insn); 1305 ira_free (at_bb_end); 1306 ira_free (at_bb_start); 1307 } 1308