1 /* Integrated Register Allocator. Changing code and generating moves.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
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/>. */
22 /* When we have more one region, we need to change the original RTL
23 code after coloring. Let us consider two allocnos representing the
24 same pseudo-register outside and inside a region respectively.
25 They can get different hard-registers. The reload pass works on
26 pseudo registers basis and there is no way to say the reload that
27 pseudo could be in different registers and it is even more
28 difficult to say in what places of the code the pseudo should have
29 particular hard-registers. So in this case IRA has to create and
30 use a new pseudo-register inside the region and adds code to move
31 allocno values on the region's borders. This is done by the code
34 The code makes top-down traversal of the regions and generate new
35 pseudos and the move code on the region borders. In some
36 complicated cases IRA can create a new pseudo used temporarily to
37 move allocno values when a swap of values stored in two
38 hard-registers is needed (e.g. two allocnos representing different
39 pseudos outside region got respectively hard registers 1 and 2 and
40 the corresponding allocnos inside the region got respectively hard
41 registers 2 and 1). At this stage, the new pseudo is marked as
44 IRA still creates the pseudo-register and the moves on the region
45 borders even when the both corresponding allocnos were assigned to
46 the same hard-register. It is done because, if the reload pass for
47 some reason spills a pseudo-register representing the original
48 pseudo outside or inside the region, the effect will be smaller
49 because another pseudo will still be in the hard-register. In most
50 cases, this is better then spilling the original pseudo in its
51 whole live-range. If reload does not change the allocation for the
52 two pseudo-registers, the trivial move will be removed by
53 post-reload optimizations.
55 IRA does not generate a new pseudo and moves for the allocno values
56 if the both allocnos representing an original pseudo inside and
57 outside region assigned to the same hard register when the register
58 pressure in the region for the corresponding pressure class is less
59 than number of available hard registers for given pressure class.
61 IRA also does some optimizations to remove redundant moves which is
62 transformed into stores by the reload pass on CFG edges
63 representing exits from the region.
65 IRA tries to reduce duplication of code generated on CFG edges
66 which are enters and exits to/from regions by moving some code to
67 the edge sources or destinations when it is possible. */
71 #include "coretypes.h"
80 #include "hard-reg-set.h"
81 #include "basic-block.h"
86 #include "tree-pass.h"
92 /* Data used to emit live range split insns and to flattening IR. */
93 ira_emit_data_t ira_allocno_emit_data;
95 /* Definitions for vectors of pointers. */
98 DEF_VEC_ALLOC_P (void_p,heap);
100 /* Pointers to data allocated for allocnos being created during
101 emitting. Usually there are quite few such allocnos because they
102 are created only for resolving loop in register shuffling. */
103 static VEC(void_p, heap) *new_allocno_emit_data_vec;
105 /* Allocate and initiate the emit data. */
107 ira_initiate_emit_data (void)
110 ira_allocno_iterator ai;
112 ira_allocno_emit_data
113 = (ira_emit_data_t) ira_allocate (ira_allocnos_num
114 * sizeof (struct ira_emit_data));
115 memset (ira_allocno_emit_data, 0,
116 ira_allocnos_num * sizeof (struct ira_emit_data));
117 FOR_EACH_ALLOCNO (a, ai)
118 ALLOCNO_ADD_DATA (a) = ira_allocno_emit_data + ALLOCNO_NUM (a);
119 new_allocno_emit_data_vec = VEC_alloc (void_p, heap, 50);
123 /* Free the emit data. */
125 ira_finish_emit_data (void)
129 ira_allocno_iterator ai;
131 ira_free (ira_allocno_emit_data);
132 FOR_EACH_ALLOCNO (a, ai)
133 ALLOCNO_ADD_DATA (a) = NULL;
134 for (;VEC_length (void_p, new_allocno_emit_data_vec) != 0;)
136 p = VEC_pop (void_p, new_allocno_emit_data_vec);
139 VEC_free (void_p, heap, new_allocno_emit_data_vec);
142 /* Create and return a new allocno with given REGNO and
143 LOOP_TREE_NODE. Allocate emit data for it. */
145 create_new_allocno (int regno, ira_loop_tree_node_t loop_tree_node)
149 a = ira_create_allocno (regno, false, loop_tree_node);
150 ALLOCNO_ADD_DATA (a) = ira_allocate (sizeof (struct ira_emit_data));
151 memset (ALLOCNO_ADD_DATA (a), 0, sizeof (struct ira_emit_data));
152 VEC_safe_push (void_p, heap, new_allocno_emit_data_vec, ALLOCNO_ADD_DATA (a));
158 /* See comments below. */
159 typedef struct move *move_t;
161 /* The structure represents an allocno move. Both allocnos have the
162 same original regno but different allocation. */
165 /* The allocnos involved in the move. */
166 ira_allocno_t from, to;
167 /* The next move in the move sequence. */
169 /* Used for finding dependencies. */
171 /* The size of the following array. */
173 /* Moves on which given move depends on. Dependency can be cyclic.
174 It means we need a temporary to generates the moves. Sequence
175 A1->A2, B1->B2 where A1 and B2 are assigned to reg R1 and A2 and
176 B1 are assigned to reg R2 is an example of the cyclic
179 /* First insn generated for the move. */
183 /* Array of moves (indexed by BB index) which should be put at the
184 start/end of the corresponding basic blocks. */
185 static move_t *at_bb_start, *at_bb_end;
187 /* Max regno before renaming some pseudo-registers. For example, the
188 same pseudo-register can be renamed in a loop if its allocation is
189 different outside the loop. */
190 static int max_regno_before_changing;
192 /* Return new move of allocnos TO and FROM. */
194 create_move (ira_allocno_t to, ira_allocno_t from)
198 move = (move_t) ira_allocate (sizeof (struct move));
204 move->insn = NULL_RTX;
205 move->visited_p = false;
209 /* Free memory for MOVE and its dependencies. */
211 free_move (move_t move)
213 if (move->deps != NULL)
214 ira_free (move->deps);
218 /* Free memory for list of the moves given by its HEAD. */
220 free_move_list (move_t head)
224 for (; head != NULL; head = next)
231 /* Return TRUE if the move list LIST1 and LIST2 are equal (two
232 moves are equal if they involve the same allocnos). */
234 eq_move_lists_p (move_t list1, move_t list2)
236 for (; list1 != NULL && list2 != NULL;
237 list1 = list1->next, list2 = list2->next)
238 if (list1->from != list2->from || list1->to != list2->to)
240 return list1 == list2;
243 /* Print move list LIST into file F. */
245 print_move_list (FILE *f, move_t list)
247 for (; list != NULL; list = list->next)
248 fprintf (f, " a%dr%d->a%dr%d",
249 ALLOCNO_NUM (list->from), ALLOCNO_REGNO (list->from),
250 ALLOCNO_NUM (list->to), ALLOCNO_REGNO (list->to));
254 extern void ira_debug_move_list (move_t list);
256 /* Print move list LIST into stderr. */
258 ira_debug_move_list (move_t list)
260 print_move_list (stderr, list);
263 /* This recursive function changes pseudo-registers in *LOC if it is
264 necessary. The function returns TRUE if a change was done. */
266 change_regs (rtx *loc)
268 int i, regno, result = false;
273 if (*loc == NULL_RTX)
275 code = GET_CODE (*loc);
278 regno = REGNO (*loc);
279 if (regno < FIRST_PSEUDO_REGISTER)
281 if (regno >= max_regno_before_changing)
282 /* It is a shared register which was changed already. */
284 if (ira_curr_regno_allocno_map[regno] == NULL)
286 reg = allocno_emit_reg (ira_curr_regno_allocno_map[regno]);
293 fmt = GET_RTX_FORMAT (code);
294 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
297 result = change_regs (&XEXP (*loc, i)) || result;
298 else if (fmt[i] == 'E')
302 for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
303 result = change_regs (&XVECEXP (*loc, i, j)) || result;
309 /* Attach MOVE to the edge E. The move is attached to the head of the
310 list if HEAD_P is TRUE. */
312 add_to_edge_list (edge e, move_t move, bool head_p)
316 if (head_p || e->aux == NULL)
318 move->next = (move_t) e->aux;
323 for (last = (move_t) e->aux; last->next != NULL; last = last->next)
330 /* Create and return new pseudo-register with the same attributes as
333 ira_create_new_reg (rtx original_reg)
337 new_reg = gen_reg_rtx (GET_MODE (original_reg));
338 ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
339 REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
340 REG_POINTER (new_reg) = REG_POINTER (original_reg);
341 REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
342 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
343 fprintf (ira_dump_file, " Creating newreg=%i from oldreg=%i\n",
344 REGNO (new_reg), REGNO (original_reg));
348 /* Return TRUE if loop given by SUBNODE inside the loop given by
351 subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
353 for (; subnode != NULL; subnode = subnode->parent)
359 /* Set up member `reg' to REG for allocnos which has the same regno as
360 ALLOCNO and which are inside the loop corresponding to ALLOCNO. */
362 set_allocno_reg (ira_allocno_t allocno, rtx reg)
366 ira_loop_tree_node_t node;
368 node = ALLOCNO_LOOP_TREE_NODE (allocno);
369 for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
371 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
372 if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
373 ALLOCNO_EMIT_DATA (a)->reg = reg;
374 for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
375 ALLOCNO_EMIT_DATA (a)->reg = reg;
376 regno = ALLOCNO_REGNO (allocno);
379 if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
384 a = node->regno_allocno_map[regno];
388 if (ALLOCNO_EMIT_DATA (a)->child_renamed_p)
390 ALLOCNO_EMIT_DATA (a)->child_renamed_p = true;
394 /* Return true if there is an entry to given loop not from its parent
395 (or grandparent) block. For example, it is possible for two
396 adjacent loops inside another loop. */
398 entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
400 ira_loop_tree_node_t bb_node, src_loop_node, parent;
404 for (bb_node = loop_node->children;
406 bb_node = bb_node->next)
407 if (bb_node->bb != NULL)
409 FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
410 if (e->src != ENTRY_BLOCK_PTR
411 && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
413 for (parent = src_loop_node->parent;
415 parent = parent->parent)
416 if (parent == loop_node)
419 /* That is an exit from a nested loop -- skip it. */
421 for (parent = loop_node->parent;
423 parent = parent->parent)
424 if (src_loop_node == parent)
433 /* Set up ENTERED_FROM_NON_PARENT_P for each loop region. */
435 setup_entered_from_non_parent_p (void)
440 ira_assert (current_loops != NULL);
441 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop)
442 if (ira_loop_nodes[i].regno_allocno_map != NULL)
443 ira_loop_nodes[i].entered_from_non_parent_p
444 = entered_from_non_parent_p (&ira_loop_nodes[i]);
447 /* Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to
448 DEST_ALLOCNO (assigned to memory) can be removed because it does
449 not change value of the destination. One possible reason for this
450 is the situation when SRC_ALLOCNO is not modified in the
451 corresponding loop. */
453 store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
455 int regno, orig_regno;
457 ira_loop_tree_node_t node;
459 ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
460 && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
461 orig_regno = ALLOCNO_REGNO (src_allocno);
462 regno = REGNO (allocno_emit_reg (dest_allocno));
463 for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
467 a = node->regno_allocno_map[orig_regno];
468 ira_assert (a != NULL);
469 if (REGNO (allocno_emit_reg (a)) == (unsigned) regno)
470 /* We achieved the destination and everything is ok. */
472 else if (bitmap_bit_p (node->modified_regnos, orig_regno))
474 else if (node->entered_from_non_parent_p)
475 /* If there is a path from a destination loop block to the
476 source loop header containing basic blocks of non-parents
477 (grandparents) of the source loop, we should have checked
478 modifications of the pseudo on this path too to decide
479 about possibility to remove the store. It could be done by
480 solving a data-flow problem. Unfortunately such global
481 solution would complicate IR flattening. Therefore we just
482 prohibit removal of the store in such complicated case. */
485 /* It is actually a loop entry -- do not remove the store. */
489 /* Generate and attach moves to the edge E. This looks at the final
490 regnos of allocnos living on the edge with the same original regno
491 to figure out when moves should be generated. */
493 generate_edge_moves (edge e)
495 ira_loop_tree_node_t src_loop_node, dest_loop_node;
498 ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
501 src_loop_node = IRA_BB_NODE (e->src)->parent;
502 dest_loop_node = IRA_BB_NODE (e->dest)->parent;
504 if (src_loop_node == dest_loop_node)
506 src_map = src_loop_node->regno_allocno_map;
507 dest_map = dest_loop_node->regno_allocno_map;
508 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (e->dest),
509 FIRST_PSEUDO_REGISTER, regno, bi)
510 if (bitmap_bit_p (DF_LR_OUT (e->src), regno))
512 src_allocno = src_map[regno];
513 dest_allocno = dest_map[regno];
514 if (REGNO (allocno_emit_reg (src_allocno))
515 == REGNO (allocno_emit_reg (dest_allocno)))
517 /* Remove unnecessary stores at the region exit. We should do
518 this for readonly memory for sure and this is guaranteed by
519 that we never generate moves on region borders (see
520 checking ira_reg_equiv_invariant_p in function
522 if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
523 && ALLOCNO_HARD_REGNO (src_allocno) >= 0
524 && store_can_be_removed_p (src_allocno, dest_allocno))
526 ALLOCNO_EMIT_DATA (src_allocno)->mem_optimized_dest = dest_allocno;
527 ALLOCNO_EMIT_DATA (dest_allocno)->mem_optimized_dest_p = true;
528 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
529 fprintf (ira_dump_file, " Remove r%d:a%d->a%d(mem)\n",
530 regno, ALLOCNO_NUM (src_allocno),
531 ALLOCNO_NUM (dest_allocno));
534 move = create_move (dest_allocno, src_allocno);
535 add_to_edge_list (e, move, true);
539 /* Bitmap of allocnos local for the current loop. */
540 static bitmap local_allocno_bitmap;
542 /* This bitmap is used to find that we need to generate and to use a
543 new pseudo-register when processing allocnos with the same original
545 static bitmap used_regno_bitmap;
547 /* This bitmap contains regnos of allocnos which were renamed locally
548 because the allocnos correspond to disjoint live ranges in loops
549 with a common parent. */
550 static bitmap renamed_regno_bitmap;
552 /* Change (if necessary) pseudo-registers inside loop given by loop
555 change_loop (ira_loop_tree_node_t node)
561 ira_allocno_t allocno, parent_allocno, *map;
562 rtx insn, original_reg;
563 enum reg_class aclass, pclass;
564 ira_loop_tree_node_t parent;
566 if (node != ira_loop_tree_root)
568 ira_assert (current_loops != NULL);
570 if (node->bb != NULL)
572 FOR_BB_INSNS (node->bb, insn)
573 if (INSN_P (insn) && change_regs (&insn))
575 df_insn_rescan (insn);
576 df_notes_rescan (insn);
581 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
582 fprintf (ira_dump_file,
583 " Changing RTL for loop %d (header bb%d)\n",
584 node->loop_num, node->loop->header->index);
586 parent = ira_curr_loop_tree_node->parent;
587 map = parent->regno_allocno_map;
588 EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
591 allocno = ira_allocnos[i];
592 regno = ALLOCNO_REGNO (allocno);
593 aclass = ALLOCNO_CLASS (allocno);
594 pclass = ira_pressure_class_translate[aclass];
595 parent_allocno = map[regno];
596 ira_assert (regno < ira_reg_equiv_len);
597 /* We generate the same hard register move because the
598 reload pass can put an allocno into memory in this case
599 we will have live range splitting. If it does not happen
600 such the same hard register moves will be removed. The
601 worst case when the both allocnos are put into memory by
602 the reload is very rare. */
603 if (parent_allocno != NULL
604 && (ALLOCNO_HARD_REGNO (allocno)
605 == ALLOCNO_HARD_REGNO (parent_allocno))
606 && (ALLOCNO_HARD_REGNO (allocno) < 0
607 || (parent->reg_pressure[pclass] + 1
608 <= ira_class_hard_regs_num[pclass])
609 || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
610 [ALLOCNO_MODE (allocno)],
611 ALLOCNO_HARD_REGNO (allocno))
612 /* don't create copies because reload can spill an
613 allocno set by copy although the allocno will not
615 || ira_reg_equiv_invariant_p[regno]
616 || ira_reg_equiv_const[regno] != NULL_RTX))
618 original_reg = allocno_emit_reg (allocno);
619 if (parent_allocno == NULL
620 || (REGNO (allocno_emit_reg (parent_allocno))
621 == REGNO (original_reg)))
623 if (internal_flag_ira_verbose > 3 && ira_dump_file)
624 fprintf (ira_dump_file, " %i vs parent %i:",
625 ALLOCNO_HARD_REGNO (allocno),
626 ALLOCNO_HARD_REGNO (parent_allocno));
627 set_allocno_reg (allocno, ira_create_new_reg (original_reg));
631 /* Rename locals: Local allocnos with same regno in different loops
632 might get the different hard register. So we need to change
634 bitmap_and_compl (local_allocno_bitmap,
635 ira_curr_loop_tree_node->all_allocnos,
636 ira_curr_loop_tree_node->border_allocnos);
637 EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
639 allocno = ira_allocnos[i];
640 regno = ALLOCNO_REGNO (allocno);
641 if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
643 used_p = !bitmap_set_bit (used_regno_bitmap, regno);
644 ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
647 bitmap_set_bit (renamed_regno_bitmap, regno);
648 set_allocno_reg (allocno, ira_create_new_reg (allocno_emit_reg (allocno)));
652 /* Process to set up flag somewhere_renamed_p. */
654 set_allocno_somewhere_renamed_p (void)
657 ira_allocno_t allocno;
658 ira_allocno_iterator ai;
660 FOR_EACH_ALLOCNO (allocno, ai)
662 regno = ALLOCNO_REGNO (allocno);
663 if (bitmap_bit_p (renamed_regno_bitmap, regno)
664 && REGNO (allocno_emit_reg (allocno)) == regno)
665 ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
669 /* Return TRUE if move lists on all edges given in vector VEC are
672 eq_edge_move_lists_p (VEC(edge,gc) *vec)
677 list = (move_t) EDGE_I (vec, 0)->aux;
678 for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
679 if (! eq_move_lists_p (list, (move_t) EDGE_I (vec, i)->aux))
684 /* Look at all entry edges (if START_P) or exit edges of basic block
685 BB and put move lists at the BB start or end if it is possible. In
686 other words, this decreases code duplication of allocno moves. */
688 unify_moves (basic_block bb, bool start_p)
695 vec = (start_p ? bb->preds : bb->succs);
696 if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
699 list = (move_t) e->aux;
700 if (! start_p && control_flow_insn_p (BB_END (bb)))
703 for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
706 free_move_list ((move_t) e->aux);
710 at_bb_start[bb->index] = list;
712 at_bb_end[bb->index] = list;
715 /* Last move (in move sequence being processed) setting up the
716 corresponding hard register. */
717 static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER];
719 /* If the element value is equal to CURR_TICK then the corresponding
720 element in `hard_regno_last_set' is defined and correct. */
721 static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
723 /* Last move (in move sequence being processed) setting up the
724 corresponding allocno. */
725 static move_t *allocno_last_set;
727 /* If the element value is equal to CURR_TICK then the corresponding
728 element in . `allocno_last_set' is defined and correct. */
729 static int *allocno_last_set_check;
731 /* Definition of vector of moves. */
733 DEF_VEC_ALLOC_P(move_t, heap);
735 /* This vec contains moves sorted topologically (depth-first) on their
737 static VEC(move_t,heap) *move_vec;
739 /* The variable value is used to check correctness of values of
740 elements of arrays `hard_regno_last_set' and
741 `allocno_last_set_check'. */
742 static int curr_tick;
744 /* This recursive function traverses dependencies of MOVE and produces
745 topological sorting (in depth-first order). */
747 traverse_moves (move_t move)
753 move->visited_p = true;
754 for (i = move->deps_num - 1; i >= 0; i--)
755 traverse_moves (move->deps[i]);
756 VEC_safe_push (move_t, heap, move_vec, move);
759 /* Remove unnecessary moves in the LIST, makes topological sorting,
760 and removes cycles on hard reg dependencies by introducing new
761 allocnos assigned to memory and additional moves. It returns the
764 modify_move_list (move_t list)
766 int i, n, nregs, hard_regno;
767 ira_allocno_t to, from;
768 move_t move, new_move, set_move, first, last;
772 /* Creat move deps. */
774 for (move = list; move != NULL; move = move->next)
777 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
779 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
780 for (i = 0; i < nregs; i++)
782 hard_regno_last_set[hard_regno + i] = move;
783 hard_regno_last_set_check[hard_regno + i] = curr_tick;
786 for (move = list; move != NULL; move = move->next)
790 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
792 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
793 for (n = i = 0; i < nregs; i++)
794 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
795 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
796 != ALLOCNO_REGNO (from)))
798 move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
799 for (n = i = 0; i < nregs; i++)
800 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
801 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
802 != ALLOCNO_REGNO (from)))
803 move->deps[n++] = hard_regno_last_set[hard_regno + i];
807 /* Toplogical sorting: */
808 VEC_truncate (move_t, move_vec, 0);
809 for (move = list; move != NULL; move = move->next)
810 traverse_moves (move);
812 for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
814 move = VEC_index (move_t, move_vec, i);
820 first = VEC_last (move_t, move_vec);
821 /* Removing cycles: */
823 VEC_truncate (move_t, move_vec, 0);
824 for (move = first; move != NULL; move = move->next)
828 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
830 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
831 for (i = 0; i < nregs; i++)
832 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
833 && ALLOCNO_HARD_REGNO
834 (hard_regno_last_set[hard_regno + i]->to) >= 0)
837 ira_allocno_t new_allocno;
839 set_move = hard_regno_last_set[hard_regno + i];
840 /* It does not matter what loop_tree_node (of TO or
841 FROM) to use for the new allocno because of
842 subsequent IRA internal representation
845 = create_new_allocno (ALLOCNO_REGNO (set_move->to),
846 ALLOCNO_LOOP_TREE_NODE (set_move->to));
847 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
848 ira_set_allocno_class (new_allocno,
849 ALLOCNO_CLASS (set_move->to));
850 ira_create_allocno_objects (new_allocno);
851 ALLOCNO_ASSIGNED_P (new_allocno) = true;
852 ALLOCNO_HARD_REGNO (new_allocno) = -1;
853 ALLOCNO_EMIT_DATA (new_allocno)->reg
854 = ira_create_new_reg (allocno_emit_reg (set_move->to));
856 /* Make it possibly conflicting with all earlier
857 created allocnos. Cases where temporary allocnos
858 created to remove the cycles are quite rare. */
859 n = ALLOCNO_NUM_OBJECTS (new_allocno);
860 gcc_assert (n == ALLOCNO_NUM_OBJECTS (set_move->to));
861 for (j = 0; j < n; j++)
863 ira_object_t new_obj = ALLOCNO_OBJECT (new_allocno, j);
865 OBJECT_MIN (new_obj) = 0;
866 OBJECT_MAX (new_obj) = ira_objects_num - 1;
869 new_move = create_move (set_move->to, new_allocno);
870 set_move->to = new_allocno;
871 VEC_safe_push (move_t, heap, move_vec, new_move);
872 ira_move_loops_num++;
873 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
874 fprintf (ira_dump_file,
875 " Creating temporary allocno a%dr%d\n",
876 ALLOCNO_NUM (new_allocno),
877 REGNO (allocno_emit_reg (new_allocno)));
880 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
882 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
883 for (i = 0; i < nregs; i++)
885 hard_regno_last_set[hard_regno + i] = move;
886 hard_regno_last_set_check[hard_regno + i] = curr_tick;
889 for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
891 move = VEC_index (move_t, move_vec, i);
899 /* Generate RTX move insns from the move list LIST. This updates
900 allocation cost using move execution frequency FREQ. */
902 emit_move_list (move_t list, int freq)
905 rtx result, insn, set, to;
906 enum machine_mode mode;
907 enum reg_class aclass;
910 for (; list != NULL; list = list->next)
913 emit_move_insn (allocno_emit_reg (list->to),
914 allocno_emit_reg (list->from));
915 list->insn = get_insns ();
917 for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
919 /* The reload needs to have set up insn codes. If the
920 reload sets up insn codes by itself, it may fail because
921 insns will have hard registers instead of pseudos and
922 there may be no machine insn with given hard
924 recog_memoized (insn);
925 /* Add insn to equiv init insn list if it is necessary.
926 Otherwise reload will not remove this insn if it decides
927 to use the equivalence. */
928 if ((set = single_set (insn)) != NULL_RTX)
931 if (GET_CODE (to) == SUBREG)
932 to = SUBREG_REG (to);
933 ira_assert (REG_P (to));
935 if (regno >= ira_reg_equiv_len
936 || (! ira_reg_equiv_invariant_p[regno]
937 && ira_reg_equiv_const[regno] == NULL_RTX))
938 continue; /* regno has no equivalence. */
939 ira_assert ((int) VEC_length (reg_equivs_t, reg_equivs)
940 >= ira_reg_equiv_len);
941 reg_equiv_init (regno)
942 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
945 emit_insn (list->insn);
946 mode = ALLOCNO_MODE (list->to);
947 aclass = ALLOCNO_CLASS (list->to);
949 if (ALLOCNO_HARD_REGNO (list->to) < 0)
951 if (ALLOCNO_HARD_REGNO (list->from) >= 0)
953 cost = ira_memory_move_cost[mode][aclass][0] * freq;
954 ira_store_cost += cost;
957 else if (ALLOCNO_HARD_REGNO (list->from) < 0)
959 if (ALLOCNO_HARD_REGNO (list->to) >= 0)
961 cost = ira_memory_move_cost[mode][aclass][0] * freq;
962 ira_load_cost += cost;
967 ira_init_register_move_cost_if_necessary (mode);
968 cost = ira_register_move_cost[mode][aclass][aclass] * freq;
969 ira_shuffle_cost += cost;
971 ira_overall_cost += cost;
973 result = get_insns ();
978 /* Generate RTX move insns from move lists attached to basic blocks
990 if (at_bb_start[bb->index] != NULL)
992 at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
993 insns = emit_move_list (at_bb_start[bb->index],
994 REG_FREQ_FROM_BB (bb));
997 tmp = NEXT_INSN (tmp);
998 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
999 tmp = NEXT_INSN (tmp);
1000 if (tmp == BB_HEAD (bb))
1001 emit_insn_before (insns, tmp);
1002 else if (tmp != NULL_RTX)
1003 emit_insn_after (insns, PREV_INSN (tmp));
1005 emit_insn_after (insns, get_last_insn ());
1008 if (at_bb_end[bb->index] != NULL)
1010 at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
1011 insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
1012 ira_assert (! control_flow_insn_p (BB_END (bb)));
1013 emit_insn_after (insns, BB_END (bb));
1016 FOR_EACH_EDGE (e, ei, bb->succs)
1020 ira_assert ((e->flags & EDGE_ABNORMAL) == 0
1021 || ! EDGE_CRITICAL_P (e));
1022 e->aux = modify_move_list ((move_t) e->aux);
1024 (emit_move_list ((move_t) e->aux,
1025 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
1027 if (e->src->next_bb != e->dest)
1028 ira_additional_jumps_num++;
1033 /* Update costs of A and corresponding allocnos on upper levels on the
1034 loop tree from reading (if READ_P) or writing A on an execution
1037 update_costs (ira_allocno_t a, bool read_p, int freq)
1039 ira_loop_tree_node_t parent;
1043 ALLOCNO_NREFS (a)++;
1044 ALLOCNO_FREQ (a) += freq;
1045 ALLOCNO_MEMORY_COST (a)
1046 += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)]
1047 [read_p ? 1 : 0] * freq);
1048 if (ALLOCNO_CAP (a) != NULL)
1049 a = ALLOCNO_CAP (a);
1050 else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
1051 || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
1056 /* Process moves from LIST with execution FREQ to add ranges, copies,
1057 and modify costs for allocnos involved in the moves. All regnos
1058 living through the list is in LIVE_THROUGH, and the loop tree node
1059 used to find corresponding allocnos is NODE. */
1061 add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
1062 bitmap live_through, int freq)
1071 HARD_REG_SET hard_regs_live;
1076 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1078 REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
1079 /* This is a trick to guarantee that new ranges is not merged with
1082 start = ira_max_point;
1083 for (move = list; move != NULL; move = move->next)
1085 ira_allocno_t from = move->from;
1086 ira_allocno_t to = move->to;
1089 bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
1090 bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
1092 nr = ALLOCNO_NUM_OBJECTS (to);
1093 for (i = 0; i < nr; i++)
1095 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1096 if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
1098 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1099 fprintf (ira_dump_file, " Allocate conflicts for a%dr%d\n",
1100 ALLOCNO_NUM (to), REGNO (allocno_emit_reg (to)));
1101 ira_allocate_object_conflicts (to_obj, n);
1104 ior_hard_reg_conflicts (from, &hard_regs_live);
1105 ior_hard_reg_conflicts (to, &hard_regs_live);
1107 update_costs (from, true, freq);
1108 update_costs (to, false, freq);
1109 cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
1110 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1111 fprintf (ira_dump_file, " Adding cp%d:a%dr%d-a%dr%d\n",
1112 cp->num, ALLOCNO_NUM (cp->first),
1113 REGNO (allocno_emit_reg (cp->first)),
1114 ALLOCNO_NUM (cp->second),
1115 REGNO (allocno_emit_reg (cp->second)));
1117 nr = ALLOCNO_NUM_OBJECTS (from);
1118 for (i = 0; i < nr; i++)
1120 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
1121 r = OBJECT_LIVE_RANGES (from_obj);
1122 if (r == NULL || r->finish >= 0)
1124 ira_add_live_range_to_object (from_obj, start, ira_max_point);
1125 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1126 fprintf (ira_dump_file,
1127 " Adding range [%d..%d] to allocno a%dr%d\n",
1128 start, ira_max_point, ALLOCNO_NUM (from),
1129 REGNO (allocno_emit_reg (from)));
1133 r->finish = ira_max_point;
1134 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1135 fprintf (ira_dump_file,
1136 " Adding range [%d..%d] to allocno a%dr%d\n",
1137 r->start, ira_max_point, ALLOCNO_NUM (from),
1138 REGNO (allocno_emit_reg (from)));
1142 nr = ALLOCNO_NUM_OBJECTS (to);
1143 for (i = 0; i < nr; i++)
1145 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1146 ira_add_live_range_to_object (to_obj, ira_max_point, -1);
1150 for (move = list; move != NULL; move = move->next)
1153 nr = ALLOCNO_NUM_OBJECTS (move->to);
1154 for (i = 0; i < nr; i++)
1156 ira_object_t to_obj = ALLOCNO_OBJECT (move->to, i);
1157 r = OBJECT_LIVE_RANGES (to_obj);
1160 r->finish = ira_max_point - 1;
1161 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1162 fprintf (ira_dump_file,
1163 " Adding range [%d..%d] to allocno a%dr%d\n",
1164 r->start, r->finish, ALLOCNO_NUM (move->to),
1165 REGNO (allocno_emit_reg (move->to)));
1169 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1174 a = node->regno_allocno_map[regno];
1175 if ((to = ALLOCNO_EMIT_DATA (a)->mem_optimized_dest) != NULL)
1177 nr = ALLOCNO_NUM_OBJECTS (a);
1178 for (i = 0; i < nr; i++)
1180 ira_object_t obj = ALLOCNO_OBJECT (a, i);
1181 ira_add_live_range_to_object (obj, start, ira_max_point - 1);
1183 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1186 " Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1187 start, ira_max_point - 1,
1188 to != NULL ? "upper level" : "",
1189 ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
1193 /* Process all move list to add ranges, conflicts, copies, and modify
1194 costs for allocnos involved in the moves. */
1196 add_ranges_and_copies (void)
1201 ira_loop_tree_node_t node;
1202 bitmap live_through;
1204 live_through = ira_allocate_bitmap ();
1207 /* It does not matter what loop_tree_node (of source or
1208 destination block) to use for searching allocnos by their
1209 regnos because of subsequent IR flattening. */
1210 node = IRA_BB_NODE (bb)->parent;
1211 bitmap_copy (live_through, DF_LR_IN (bb));
1212 add_range_and_copies_from_move_list
1213 (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1214 bitmap_copy (live_through, DF_LR_OUT (bb));
1215 add_range_and_copies_from_move_list
1216 (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1217 FOR_EACH_EDGE (e, ei, bb->succs)
1219 bitmap_and (live_through, DF_LR_IN (e->dest), DF_LR_OUT (bb));
1220 add_range_and_copies_from_move_list
1221 ((move_t) e->aux, node, live_through,
1222 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1225 ira_free_bitmap (live_through);
1228 /* The entry function changes code and generates shuffling allocnos on
1229 region borders for the regional (LOOPS_P is TRUE in this case)
1230 register allocation. */
1232 ira_emit (bool loops_p)
1239 ira_allocno_iterator ai;
1241 FOR_EACH_ALLOCNO (a, ai)
1242 ALLOCNO_EMIT_DATA (a)->reg = regno_reg_rtx[ALLOCNO_REGNO (a)];
1245 at_bb_start = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1246 memset (at_bb_start, 0, sizeof (move_t) * last_basic_block);
1247 at_bb_end = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1248 memset (at_bb_end, 0, sizeof (move_t) * last_basic_block);
1249 local_allocno_bitmap = ira_allocate_bitmap ();
1250 used_regno_bitmap = ira_allocate_bitmap ();
1251 renamed_regno_bitmap = ira_allocate_bitmap ();
1252 max_regno_before_changing = max_reg_num ();
1253 ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1254 set_allocno_somewhere_renamed_p ();
1255 ira_free_bitmap (used_regno_bitmap);
1256 ira_free_bitmap (renamed_regno_bitmap);
1257 ira_free_bitmap (local_allocno_bitmap);
1258 setup_entered_from_non_parent_p ();
1261 at_bb_start[bb->index] = NULL;
1262 at_bb_end[bb->index] = NULL;
1263 FOR_EACH_EDGE (e, ei, bb->succs)
1264 if (e->dest != EXIT_BLOCK_PTR)
1265 generate_edge_moves (e);
1268 = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
1269 allocno_last_set_check
1270 = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1271 memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
1272 memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1275 unify_moves (bb, true);
1277 unify_moves (bb, false);
1278 move_vec = VEC_alloc (move_t, heap, ira_allocnos_num);
1280 add_ranges_and_copies ();
1284 free_move_list (at_bb_start[bb->index]);
1285 free_move_list (at_bb_end[bb->index]);
1286 FOR_EACH_EDGE (e, ei, bb->succs)
1288 free_move_list ((move_t) e->aux);
1292 VEC_free (move_t, heap, move_vec);
1293 ira_free (allocno_last_set_check);
1294 ira_free (allocno_last_set);
1295 commit_edge_insertions ();
1296 /* Fix insn codes. It is necessary to do it before reload because
1297 reload assumes initial insn codes defined. The insn codes can be
1298 invalidated by CFG infrastructure for example in jump
1301 FOR_BB_INSNS_REVERSE (bb, insn)
1303 recog_memoized (insn);
1304 ira_free (at_bb_end);
1305 ira_free (at_bb_start);