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