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>.
6 This file is part of GCC.
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
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
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/>. */
25 #include "coretypes.h"
34 #include "hard-reg-set.h"
35 #include "basic-block.h"
40 #include "tree-pass.h"
48 typedef struct move *move_t;
50 /* The structure represents an allocno move. Both allocnos have the
51 same origional regno but different allocation. */
54 /* The allocnos involved in the move. */
55 ira_allocno_t from, to;
56 /* The next move in the move sequence. */
58 /* Used for finding dependencies. */
60 /* The size of the following array. */
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
68 /* First insn generated for the move. */
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;
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;
81 /* Return new move of allocnos TO and FROM. */
83 create_move (ira_allocno_t to, ira_allocno_t from)
87 move = (move_t) ira_allocate (sizeof (struct move));
93 move->insn = NULL_RTX;
94 move->visited_p = false;
98 /* Free memory for MOVE and its dependencies. */
100 free_move (move_t move)
102 if (move->deps != NULL)
103 ira_free (move->deps);
107 /* Free memory for list of the moves given by its HEAD. */
109 free_move_list (move_t head)
113 for (; head != NULL; head = next)
120 /* Return TRUE if the the move list LIST1 and LIST2 are equal (two
121 moves are equal if they involve the same allocnos). */
123 eq_move_lists_p (move_t list1, move_t list2)
125 for (; list1 != NULL && list2 != NULL;
126 list1 = list1->next, list2 = list2->next)
127 if (list1->from != list2->from || list1->to != list2->to)
129 return list1 == list2;
132 /* Print move list LIST into file F. */
134 print_move_list (FILE *f, move_t list)
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));
143 extern void ira_debug_move_list (move_t list);
145 /* Print move list LIST into stderr. */
147 ira_debug_move_list (move_t list)
149 print_move_list (stderr, list);
152 /* This recursive function changes pseudo-registers in *LOC if it is
153 necessary. The function returns TRUE if a change was done. */
155 change_regs (rtx *loc)
157 int i, regno, result = false;
162 if (*loc == NULL_RTX)
164 code = GET_CODE (*loc);
167 regno = REGNO (*loc);
168 if (regno < FIRST_PSEUDO_REGISTER)
170 if (regno >= max_regno_before_changing)
171 /* It is a shared register which was changed already. */
173 if (ira_curr_regno_allocno_map[regno] == NULL)
175 reg = ALLOCNO_REG (ira_curr_regno_allocno_map[regno]);
182 fmt = GET_RTX_FORMAT (code);
183 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
186 result = change_regs (&XEXP (*loc, i)) || result;
187 else if (fmt[i] == 'E')
191 for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
192 result = change_regs (&XVECEXP (*loc, i, j)) || result;
198 /* Attach MOVE to the edge E. The move is attached to the head of the
199 list if HEAD_P is TRUE. */
201 add_to_edge_list (edge e, move_t move, bool head_p)
205 if (head_p || e->aux == NULL)
207 move->next = (move_t) e->aux;
212 for (last = (move_t) e->aux; last->next != NULL; last = last->next)
219 /* Create and return new pseudo-register with the same attributes as
222 create_new_reg (rtx original_reg)
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));
237 /* Return TRUE if loop given by SUBNODE inside the loop given by
240 subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
242 for (; subnode != NULL; subnode = subnode->parent)
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. */
251 set_allocno_reg (ira_allocno_t allocno, rtx reg)
255 ira_loop_tree_node_t node;
257 node = ALLOCNO_LOOP_TREE_NODE (allocno);
258 for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
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);
268 if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
273 a = node->regno_allocno_map[regno];
277 if (ALLOCNO_CHILD_RENAMED_P (a))
279 ALLOCNO_CHILD_RENAMED_P (a) = true;
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. */
287 entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
289 ira_loop_tree_node_t bb_node, src_loop_node, parent;
293 for (bb_node = loop_node->children; bb_node != NULL; bb_node = bb_node->next)
294 if (bb_node->bb != NULL)
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)
300 for (parent = src_loop_node->parent;
302 parent = parent->parent)
303 if (parent == loop_node)
306 /* That is an exit from a nested loop -- skip it. */
308 for (parent = loop_node->parent;
310 parent = parent->parent)
311 if (src_loop_node == parent)
320 /* Set up ENTERED_FROM_NON_PARENT_P for each loop region. */
322 setup_entered_from_non_parent_p (void)
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]);
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. */
339 store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
341 int regno, orig_regno;
343 ira_loop_tree_node_t node;
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);
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. */
358 else if (bitmap_bit_p (node->modified_regnos, orig_regno))
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. */
371 /* It is actually a loop entry -- do not remove the store. */
375 /* Generate and attach moves to the edge E. This looks at the final
376 regnos of allocnos living on the edge with the same original regno
377 to figure out when moves should be generated. */
379 generate_edge_moves (edge e)
381 ira_loop_tree_node_t src_loop_node, dest_loop_node;
384 ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
387 src_loop_node = IRA_BB_NODE (e->src)->parent;
388 dest_loop_node = IRA_BB_NODE (e->dest)->parent;
390 if (src_loop_node == dest_loop_node)
392 src_map = src_loop_node->regno_allocno_map;
393 dest_map = dest_loop_node->regno_allocno_map;
394 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (e->dest),
395 FIRST_PSEUDO_REGISTER, regno, bi)
396 if (bitmap_bit_p (DF_LR_OUT (e->src), regno))
398 src_allocno = src_map[regno];
399 dest_allocno = dest_map[regno];
400 if (REGNO (ALLOCNO_REG (src_allocno))
401 == REGNO (ALLOCNO_REG (dest_allocno)))
403 /* Remove unnecessary stores at the region exit. We should do
404 this for readonly memory for sure and this is guaranteed by
405 that we never generate moves on region borders (see
406 checking ira_reg_equiv_invariant_p in function
408 if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
409 && ALLOCNO_HARD_REGNO (src_allocno) >= 0
410 && store_can_be_removed_p (src_allocno, dest_allocno))
412 ALLOCNO_MEM_OPTIMIZED_DEST (src_allocno) = dest_allocno;
413 ALLOCNO_MEM_OPTIMIZED_DEST_P (dest_allocno) = true;
414 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
415 fprintf (ira_dump_file, " Remove r%d:a%d->a%d(mem)\n",
416 regno, ALLOCNO_NUM (src_allocno),
417 ALLOCNO_NUM (dest_allocno));
420 move = create_move (dest_allocno, src_allocno);
421 add_to_edge_list (e, move, true);
425 /* Bitmap of allocnos local for the current loop. */
426 static bitmap local_allocno_bitmap;
428 /* This bitmap is used to find that we need to generate and to use a
429 new pseudo-register when processing allocnos with the same original
431 static bitmap used_regno_bitmap;
433 /* This bitmap contains regnos of allocnos which were renamed locally
434 because the allocnos correspond to disjoint live ranges in loops
435 with a common parent. */
436 static bitmap renamed_regno_bitmap;
438 /* Change (if necessary) pseudo-registers inside loop given by loop
441 change_loop (ira_loop_tree_node_t node)
447 ira_allocno_t allocno, parent_allocno, *map;
448 rtx insn, original_reg;
449 enum reg_class cover_class;
450 ira_loop_tree_node_t parent;
452 if (node != ira_loop_tree_root)
455 if (node->bb != NULL)
457 FOR_BB_INSNS (node->bb, insn)
458 if (INSN_P (insn) && change_regs (&insn))
460 df_insn_rescan (insn);
461 df_notes_rescan (insn);
466 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
467 fprintf (ira_dump_file,
468 " Changing RTL for loop %d (header bb%d)\n",
469 node->loop->num, node->loop->header->index);
471 parent = ira_curr_loop_tree_node->parent;
472 map = parent->regno_allocno_map;
473 EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
476 allocno = ira_allocnos[i];
477 regno = ALLOCNO_REGNO (allocno);
478 cover_class = ALLOCNO_COVER_CLASS (allocno);
479 parent_allocno = map[regno];
480 ira_assert (regno < ira_reg_equiv_len);
481 /* We generate the same hard register move because the
482 reload pass can put an allocno into memory in this case
483 we will have live range splitting. If it does not happen
484 such the same hard register moves will be removed. The
485 worst case when the both allocnos are put into memory by
486 the reload is very rare. */
487 if (parent_allocno != NULL
488 && (ALLOCNO_HARD_REGNO (allocno)
489 == ALLOCNO_HARD_REGNO (parent_allocno))
490 && (ALLOCNO_HARD_REGNO (allocno) < 0
491 || (parent->reg_pressure[cover_class] + 1
492 <= ira_available_class_regs[cover_class])
493 || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
494 [ALLOCNO_MODE (allocno)],
495 ALLOCNO_HARD_REGNO (allocno))
496 /* don't create copies because reload can spill an
497 allocno set by copy although the allocno will not
499 || ira_reg_equiv_invariant_p[regno]
500 || ira_reg_equiv_const[regno] != NULL_RTX))
502 original_reg = ALLOCNO_REG (allocno);
503 if (parent_allocno == NULL
504 || REGNO (ALLOCNO_REG (parent_allocno)) == REGNO (original_reg))
506 if (internal_flag_ira_verbose > 3 && ira_dump_file)
507 fprintf (ira_dump_file, " %i vs parent %i:",
508 ALLOCNO_HARD_REGNO (allocno),
509 ALLOCNO_HARD_REGNO (parent_allocno));
510 set_allocno_reg (allocno, create_new_reg (original_reg));
514 /* Rename locals: Local allocnos with same regno in different loops
515 might get the different hard register. So we need to change
517 bitmap_and_compl (local_allocno_bitmap,
518 ira_curr_loop_tree_node->all_allocnos,
519 ira_curr_loop_tree_node->border_allocnos);
520 EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
522 allocno = ira_allocnos[i];
523 regno = ALLOCNO_REGNO (allocno);
524 if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
526 used_p = bitmap_bit_p (used_regno_bitmap, regno);
527 bitmap_set_bit (used_regno_bitmap, regno);
528 ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
531 bitmap_set_bit (renamed_regno_bitmap, regno);
532 set_allocno_reg (allocno, create_new_reg (ALLOCNO_REG (allocno)));
536 /* Process to set up flag somewhere_renamed_p. */
538 set_allocno_somewhere_renamed_p (void)
541 ira_allocno_t allocno;
542 ira_allocno_iterator ai;
544 FOR_EACH_ALLOCNO (allocno, ai)
546 regno = ALLOCNO_REGNO (allocno);
547 if (bitmap_bit_p (renamed_regno_bitmap, regno)
548 && REGNO (ALLOCNO_REG (allocno)) == regno)
549 ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
553 /* Return TRUE if move lists on all edges given in vector VEC are
556 eq_edge_move_lists_p (VEC(edge,gc) *vec)
561 list = (move_t) EDGE_I (vec, 0)->aux;
562 for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
563 if (! eq_move_lists_p (list, (move_t) EDGE_I (vec, i)->aux))
568 /* Look at all entry edges (if START_P) or exit edges of basic block
569 BB and put move lists at the BB start or end if it is possible. In
570 other words, this decreases code duplication of allocno moves. */
572 unify_moves (basic_block bb, bool start_p)
579 vec = (start_p ? bb->preds : bb->succs);
580 if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
583 list = (move_t) e->aux;
584 if (! start_p && control_flow_insn_p (BB_END (bb)))
587 for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
590 free_move_list ((move_t) e->aux);
594 at_bb_start[bb->index] = list;
596 at_bb_end[bb->index] = list;
599 /* Last move (in move sequence being processed) setting up the
600 corresponding hard register. */
601 static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER];
603 /* If the element value is equal to CURR_TICK then the corresponding
604 element in `hard_regno_last_set' is defined and correct. */
605 static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
607 /* Last move (in move sequence being processed) setting up the
608 corresponding allocno. */
609 static move_t *allocno_last_set;
611 /* If the element value is equal to CURR_TICK then the corresponding
612 element in . `allocno_last_set' is defined and correct. */
613 static int *allocno_last_set_check;
615 /* Definition of vector of moves. */
617 DEF_VEC_ALLOC_P(move_t, heap);
619 /* This vec contains moves sorted topologically (depth-first) on their
621 static VEC(move_t,heap) *move_vec;
623 /* The variable value is used to check correctness of values of
624 elements of arrays `hard_regno_last_set' and
625 `allocno_last_set_check'. */
626 static int curr_tick;
628 /* This recursive function traverses dependencies of MOVE and produces
629 topological sorting (in depth-first order). */
631 traverse_moves (move_t move)
637 move->visited_p = true;
638 for (i = move->deps_num - 1; i >= 0; i--)
639 traverse_moves (move->deps[i]);
640 VEC_safe_push (move_t, heap, move_vec, move);
643 /* Remove unnecessary moves in the LIST, makes topological sorting,
644 and removes cycles on hard reg dependencies by introducing new
645 allocnos assigned to memory and additional moves. It returns the
648 modify_move_list (move_t list)
650 int i, n, nregs, hard_regno;
651 ira_allocno_t to, from, new_allocno;
652 move_t move, new_move, set_move, first, last;
656 /* Creat move deps. */
658 for (move = list; move != NULL; move = move->next)
661 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
663 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
664 for (i = 0; i < nregs; i++)
666 hard_regno_last_set[hard_regno + i] = move;
667 hard_regno_last_set_check[hard_regno + i] = curr_tick;
670 for (move = list; move != NULL; move = move->next)
674 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
676 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
677 for (n = i = 0; i < nregs; i++)
678 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
679 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
680 != ALLOCNO_REGNO (from)))
682 move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
683 for (n = i = 0; i < nregs; i++)
684 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
685 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
686 != ALLOCNO_REGNO (from)))
687 move->deps[n++] = hard_regno_last_set[hard_regno + i];
691 /* Toplogical sorting: */
692 VEC_truncate (move_t, move_vec, 0);
693 for (move = list; move != NULL; move = move->next)
694 traverse_moves (move);
696 for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
698 move = VEC_index (move_t, move_vec, i);
704 first = VEC_last (move_t, move_vec);
705 /* Removing cycles: */
707 VEC_truncate (move_t, move_vec, 0);
708 for (move = first; move != NULL; move = move->next)
712 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
714 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
715 for (i = 0; i < nregs; i++)
716 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
717 && ALLOCNO_HARD_REGNO
718 (hard_regno_last_set[hard_regno + i]->to) >= 0)
720 set_move = hard_regno_last_set[hard_regno + i];
721 /* It does not matter what loop_tree_node (of TO or
722 FROM) to use for the new allocno because of
723 subsequent IRA internal representation
726 = ira_create_allocno (ALLOCNO_REGNO (set_move->to), false,
727 ALLOCNO_LOOP_TREE_NODE (set_move->to));
728 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
729 ira_set_allocno_cover_class
730 (new_allocno, ALLOCNO_COVER_CLASS (set_move->to));
731 ALLOCNO_ASSIGNED_P (new_allocno) = true;
732 ALLOCNO_HARD_REGNO (new_allocno) = -1;
733 ALLOCNO_REG (new_allocno)
734 = create_new_reg (ALLOCNO_REG (set_move->to));
735 ALLOCNO_CONFLICT_ID (new_allocno) = ALLOCNO_NUM (new_allocno);
736 /* Make it possibly conflicting with all earlier
737 created allocnos. Cases where temporary allocnos
738 created to remove the cycles are quite rare. */
739 ALLOCNO_MIN (new_allocno) = 0;
740 ALLOCNO_MAX (new_allocno) = ira_allocnos_num - 1;
741 new_move = create_move (set_move->to, new_allocno);
742 set_move->to = new_allocno;
743 VEC_safe_push (move_t, heap, move_vec, new_move);
744 ira_move_loops_num++;
745 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
746 fprintf (ira_dump_file,
747 " Creating temporary allocno a%dr%d\n",
748 ALLOCNO_NUM (new_allocno),
749 REGNO (ALLOCNO_REG (new_allocno)));
752 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
754 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
755 for (i = 0; i < nregs; i++)
757 hard_regno_last_set[hard_regno + i] = move;
758 hard_regno_last_set_check[hard_regno + i] = curr_tick;
761 for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
763 move = VEC_index (move_t, move_vec, i);
771 /* Generate RTX move insns from the move list LIST. This updates
772 allocation cost using move execution frequency FREQ. */
774 emit_move_list (move_t list, int freq)
778 enum machine_mode mode;
779 enum reg_class cover_class;
782 for (; list != NULL; list = list->next)
785 emit_move_insn (ALLOCNO_REG (list->to), ALLOCNO_REG (list->from));
786 list->insn = get_insns ();
788 /* The reload needs to have set up insn codes. If the reload
789 sets up insn codes by itself, it may fail because insns will
790 have hard registers instead of pseudos and there may be no
791 machine insn with given hard registers. */
792 for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
793 recog_memoized (insn);
794 emit_insn (list->insn);
795 mode = ALLOCNO_MODE (list->to);
796 cover_class = ALLOCNO_COVER_CLASS (list->to);
798 if (ALLOCNO_HARD_REGNO (list->to) < 0)
800 if (ALLOCNO_HARD_REGNO (list->from) >= 0)
802 cost = ira_memory_move_cost[mode][cover_class][0] * freq;
803 ira_store_cost += cost;
806 else if (ALLOCNO_HARD_REGNO (list->from) < 0)
808 if (ALLOCNO_HARD_REGNO (list->to) >= 0)
810 cost = ira_memory_move_cost[mode][cover_class][0] * freq;
811 ira_load_cost += cost;
816 cost = (ira_get_register_move_cost (mode, cover_class, cover_class)
818 ira_shuffle_cost += cost;
820 ira_overall_cost += cost;
822 result = get_insns ();
827 /* Generate RTX move insns from move lists attached to basic blocks
839 if (at_bb_start[bb->index] != NULL)
841 at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
842 insns = emit_move_list (at_bb_start[bb->index],
843 REG_FREQ_FROM_BB (bb));
846 tmp = NEXT_INSN (tmp);
847 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
848 tmp = NEXT_INSN (tmp);
849 if (tmp == BB_HEAD (bb))
850 emit_insn_before (insns, tmp);
851 else if (tmp != NULL_RTX)
852 emit_insn_after (insns, PREV_INSN (tmp));
854 emit_insn_after (insns, get_last_insn ());
857 if (at_bb_end[bb->index] != NULL)
859 at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
860 insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
861 ira_assert (! control_flow_insn_p (BB_END (bb)));
862 emit_insn_after (insns, BB_END (bb));
865 FOR_EACH_EDGE (e, ei, bb->succs)
869 ira_assert ((e->flags & EDGE_ABNORMAL) == 0
870 || ! EDGE_CRITICAL_P (e));
871 e->aux = modify_move_list ((move_t) e->aux);
873 (emit_move_list ((move_t) e->aux,
874 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
876 if (e->src->next_bb != e->dest)
877 ira_additional_jumps_num++;
882 /* Update costs of A and corresponding allocnos on upper levels on the
883 loop tree from reading (if READ_P) or writing A on an execution
886 update_costs (ira_allocno_t a, bool read_p, int freq)
888 ira_loop_tree_node_t parent;
893 ALLOCNO_FREQ (a) += freq;
894 ALLOCNO_MEMORY_COST (a)
895 += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)]
896 [read_p ? 1 : 0] * freq);
897 if (ALLOCNO_CAP (a) != NULL)
899 else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
900 || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
905 /* Process moves from LIST with execution FREQ to add ranges, copies,
906 and modify costs for allocnos involved in the moves. All regnos
907 living through the list is in LIVE_THROUGH, and the loop tree node
908 used to find corresponding allocnos is NODE. */
910 add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
911 bitmap live_through, int freq)
916 ira_allocno_t to, from, a;
918 allocno_live_range_t r;
920 HARD_REG_SET hard_regs_live;
925 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
927 REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
928 /* This is a trick to guarantee that new ranges is not merged with
931 start = ira_max_point;
932 for (move = list; move != NULL; move = move->next)
936 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (to) == NULL)
938 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
939 fprintf (ira_dump_file, " Allocate conflicts for a%dr%d\n",
940 ALLOCNO_NUM (to), REGNO (ALLOCNO_REG (to)));
941 ira_allocate_allocno_conflicts (to, n);
943 bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
944 bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
945 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (from), hard_regs_live);
946 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (to), hard_regs_live);
947 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from),
949 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (to), hard_regs_live);
950 update_costs (from, true, freq);
951 update_costs (to, false, freq);
952 cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
953 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
954 fprintf (ira_dump_file, " Adding cp%d:a%dr%d-a%dr%d\n",
955 cp->num, ALLOCNO_NUM (cp->first),
956 REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
957 REGNO (ALLOCNO_REG (cp->second)));
958 r = ALLOCNO_LIVE_RANGES (from);
959 if (r == NULL || r->finish >= 0)
961 ALLOCNO_LIVE_RANGES (from)
962 = ira_create_allocno_live_range (from, start, ira_max_point, r);
963 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
964 fprintf (ira_dump_file,
965 " Adding range [%d..%d] to allocno a%dr%d\n",
966 start, ira_max_point, ALLOCNO_NUM (from),
967 REGNO (ALLOCNO_REG (from)));
971 r->finish = ira_max_point;
972 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
973 fprintf (ira_dump_file,
974 " Adding range [%d..%d] to allocno a%dr%d\n",
975 r->start, ira_max_point, ALLOCNO_NUM (from),
976 REGNO (ALLOCNO_REG (from)));
979 ALLOCNO_LIVE_RANGES (to)
980 = ira_create_allocno_live_range (to, ira_max_point, -1,
981 ALLOCNO_LIVE_RANGES (to));
984 for (move = list; move != NULL; move = move->next)
986 r = ALLOCNO_LIVE_RANGES (move->to);
989 r->finish = ira_max_point - 1;
990 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
991 fprintf (ira_dump_file,
992 " Adding range [%d..%d] to allocno a%dr%d\n",
993 r->start, r->finish, ALLOCNO_NUM (move->to),
994 REGNO (ALLOCNO_REG (move->to)));
997 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
999 a = node->regno_allocno_map[regno];
1000 if ((to = ALLOCNO_MEM_OPTIMIZED_DEST (a)) != NULL)
1002 ALLOCNO_LIVE_RANGES (a)
1003 = ira_create_allocno_live_range (a, start, ira_max_point - 1,
1004 ALLOCNO_LIVE_RANGES (a));
1005 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1008 " Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1009 start, ira_max_point - 1,
1010 to != NULL ? "upper level" : "",
1011 ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
1015 /* Process all move list to add ranges, conflicts, copies, and modify
1016 costs for allocnos involved in the moves. */
1018 add_ranges_and_copies (void)
1023 ira_loop_tree_node_t node;
1024 bitmap live_through;
1026 live_through = ira_allocate_bitmap ();
1029 /* It does not matter what loop_tree_node (of source or
1030 destination block) to use for searching allocnos by their
1031 regnos because of subsequent IR flattening. */
1032 node = IRA_BB_NODE (bb)->parent;
1033 bitmap_copy (live_through, DF_LR_IN (bb));
1034 add_range_and_copies_from_move_list
1035 (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1036 bitmap_copy (live_through, DF_LR_OUT (bb));
1037 add_range_and_copies_from_move_list
1038 (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1039 FOR_EACH_EDGE (e, ei, bb->succs)
1041 bitmap_and (live_through, DF_LR_IN (e->dest), DF_LR_OUT (bb));
1042 add_range_and_copies_from_move_list
1043 ((move_t) e->aux, node, live_through,
1044 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1047 ira_free_bitmap (live_through);
1050 /* The entry function changes code and generates shuffling allocnos on
1051 region borders for the regional (LOOPS_P is TRUE in this case)
1052 register allocation. */
1054 ira_emit (bool loops_p)
1061 ira_allocno_iterator ai;
1063 FOR_EACH_ALLOCNO (a, ai)
1064 ALLOCNO_REG (a) = regno_reg_rtx[ALLOCNO_REGNO (a)];
1067 at_bb_start = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1068 memset (at_bb_start, 0, sizeof (move_t) * last_basic_block);
1069 at_bb_end = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1070 memset (at_bb_end, 0, sizeof (move_t) * last_basic_block);
1071 local_allocno_bitmap = ira_allocate_bitmap ();
1072 used_regno_bitmap = ira_allocate_bitmap ();
1073 renamed_regno_bitmap = ira_allocate_bitmap ();
1074 max_regno_before_changing = max_reg_num ();
1075 ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1076 set_allocno_somewhere_renamed_p ();
1077 ira_free_bitmap (used_regno_bitmap);
1078 ira_free_bitmap (renamed_regno_bitmap);
1079 ira_free_bitmap (local_allocno_bitmap);
1080 setup_entered_from_non_parent_p ();
1083 at_bb_start[bb->index] = NULL;
1084 at_bb_end[bb->index] = NULL;
1085 FOR_EACH_EDGE (e, ei, bb->succs)
1086 if (e->dest != EXIT_BLOCK_PTR)
1087 generate_edge_moves (e);
1090 = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
1091 allocno_last_set_check
1092 = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1093 memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
1094 memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1097 unify_moves (bb, true);
1099 unify_moves (bb, false);
1100 move_vec = VEC_alloc (move_t, heap, ira_allocnos_num);
1102 add_ranges_and_copies ();
1106 free_move_list (at_bb_start[bb->index]);
1107 free_move_list (at_bb_end[bb->index]);
1108 FOR_EACH_EDGE (e, ei, bb->succs)
1110 free_move_list ((move_t) e->aux);
1114 VEC_free (move_t, heap, move_vec);
1115 ira_free (allocno_last_set_check);
1116 ira_free (allocno_last_set);
1117 commit_edge_insertions ();
1118 /* Fix insn codes. It is necessary to do it before reload because
1119 reload assumes initial insn codes defined. The insn codes can be
1120 invalidated by CFG infrastructure for example in jump
1123 FOR_BB_INSNS_REVERSE (bb, insn)
1125 recog_memoized (insn);
1126 ira_free (at_bb_end);
1127 ira_free (at_bb_start);