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