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"
93 /* Data used to emit live range split insns and to flattening IR. */
94 ira_emit_data_t ira_allocno_emit_data;
96 /* Definitions for vectors of pointers. */
99 DEF_VEC_ALLOC_P (void_p,heap);
101 /* Pointers to data allocated for allocnos being created during
102 emitting. Usually there are quite few such allocnos because they
103 are created only for resolving loop in register shuffling. */
104 static VEC(void_p, heap) *new_allocno_emit_data_vec;
106 /* Allocate and initiate the emit data. */
108 ira_initiate_emit_data (void)
111 ira_allocno_iterator ai;
113 ira_allocno_emit_data
114 = (ira_emit_data_t) ira_allocate (ira_allocnos_num
115 * sizeof (struct ira_emit_data));
116 memset (ira_allocno_emit_data, 0,
117 ira_allocnos_num * sizeof (struct ira_emit_data));
118 FOR_EACH_ALLOCNO (a, ai)
119 ALLOCNO_ADD_DATA (a) = ira_allocno_emit_data + ALLOCNO_NUM (a);
120 new_allocno_emit_data_vec = VEC_alloc (void_p, heap, 50);
124 /* Free the emit data. */
126 ira_finish_emit_data (void)
130 ira_allocno_iterator ai;
132 ira_free (ira_allocno_emit_data);
133 FOR_EACH_ALLOCNO (a, ai)
134 ALLOCNO_ADD_DATA (a) = NULL;
135 for (;VEC_length (void_p, new_allocno_emit_data_vec) != 0;)
137 p = VEC_pop (void_p, new_allocno_emit_data_vec);
140 VEC_free (void_p, heap, new_allocno_emit_data_vec);
143 /* Create and return a new allocno with given REGNO and
144 LOOP_TREE_NODE. Allocate emit data for it. */
146 create_new_allocno (int regno, ira_loop_tree_node_t loop_tree_node)
150 a = ira_create_allocno (regno, false, loop_tree_node);
151 ALLOCNO_ADD_DATA (a) = ira_allocate (sizeof (struct ira_emit_data));
152 memset (ALLOCNO_ADD_DATA (a), 0, sizeof (struct ira_emit_data));
153 VEC_safe_push (void_p, heap, new_allocno_emit_data_vec, ALLOCNO_ADD_DATA (a));
159 /* See comments below. */
160 typedef struct move *move_t;
162 /* The structure represents an allocno move. Both allocnos have the
163 same origional regno but different allocation. */
166 /* The allocnos involved in the move. */
167 ira_allocno_t from, to;
168 /* The next move in the move sequence. */
170 /* Used for finding dependencies. */
172 /* The size of the following array. */
174 /* Moves on which given move depends on. Dependency can be cyclic.
175 It means we need a temporary to generates the moves. Sequence
176 A1->A2, B1->B2 where A1 and B2 are assigned to reg R1 and A2 and
177 B1 are assigned to reg R2 is an example of the cyclic
180 /* First insn generated for the move. */
184 /* Array of moves (indexed by BB index) which should be put at the
185 start/end of the corresponding basic blocks. */
186 static move_t *at_bb_start, *at_bb_end;
188 /* Max regno before renaming some pseudo-registers. For example, the
189 same pseudo-register can be renamed in a loop if its allocation is
190 different outside the loop. */
191 static int max_regno_before_changing;
193 /* Return new move of allocnos TO and FROM. */
195 create_move (ira_allocno_t to, ira_allocno_t from)
199 move = (move_t) ira_allocate (sizeof (struct move));
205 move->insn = NULL_RTX;
206 move->visited_p = false;
210 /* Free memory for MOVE and its dependencies. */
212 free_move (move_t move)
214 if (move->deps != NULL)
215 ira_free (move->deps);
219 /* Free memory for list of the moves given by its HEAD. */
221 free_move_list (move_t head)
225 for (; head != NULL; head = next)
232 /* Return TRUE if the the move list LIST1 and LIST2 are equal (two
233 moves are equal if they involve the same allocnos). */
235 eq_move_lists_p (move_t list1, move_t list2)
237 for (; list1 != NULL && list2 != NULL;
238 list1 = list1->next, list2 = list2->next)
239 if (list1->from != list2->from || list1->to != list2->to)
241 return list1 == list2;
244 /* Print move list LIST into file F. */
246 print_move_list (FILE *f, move_t list)
248 for (; list != NULL; list = list->next)
249 fprintf (f, " a%dr%d->a%dr%d",
250 ALLOCNO_NUM (list->from), ALLOCNO_REGNO (list->from),
251 ALLOCNO_NUM (list->to), ALLOCNO_REGNO (list->to));
255 extern void ira_debug_move_list (move_t list);
257 /* Print move list LIST into stderr. */
259 ira_debug_move_list (move_t list)
261 print_move_list (stderr, list);
264 /* This recursive function changes pseudo-registers in *LOC if it is
265 necessary. The function returns TRUE if a change was done. */
267 change_regs (rtx *loc)
269 int i, regno, result = false;
274 if (*loc == NULL_RTX)
276 code = GET_CODE (*loc);
279 regno = REGNO (*loc);
280 if (regno < FIRST_PSEUDO_REGISTER)
282 if (regno >= max_regno_before_changing)
283 /* It is a shared register which was changed already. */
285 if (ira_curr_regno_allocno_map[regno] == NULL)
287 reg = allocno_emit_reg (ira_curr_regno_allocno_map[regno]);
294 fmt = GET_RTX_FORMAT (code);
295 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
298 result = change_regs (&XEXP (*loc, i)) || result;
299 else if (fmt[i] == 'E')
303 for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
304 result = change_regs (&XVECEXP (*loc, i, j)) || result;
310 /* Attach MOVE to the edge E. The move is attached to the head of the
311 list if HEAD_P is TRUE. */
313 add_to_edge_list (edge e, move_t move, bool head_p)
317 if (head_p || e->aux == NULL)
319 move->next = (move_t) e->aux;
324 for (last = (move_t) e->aux; last->next != NULL; last = last->next)
331 /* Create and return new pseudo-register with the same attributes as
334 create_new_reg (rtx original_reg)
338 new_reg = gen_reg_rtx (GET_MODE (original_reg));
339 ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
340 REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
341 REG_POINTER (new_reg) = REG_POINTER (original_reg);
342 REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
343 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
344 fprintf (ira_dump_file, " Creating newreg=%i from oldreg=%i\n",
345 REGNO (new_reg), REGNO (original_reg));
349 /* Return TRUE if loop given by SUBNODE inside the loop given by
352 subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
354 for (; subnode != NULL; subnode = subnode->parent)
360 /* Set up member `reg' to REG for allocnos which has the same regno as
361 ALLOCNO and which are inside the loop corresponding to ALLOCNO. */
363 set_allocno_reg (ira_allocno_t allocno, rtx reg)
367 ira_loop_tree_node_t node;
369 node = ALLOCNO_LOOP_TREE_NODE (allocno);
370 for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
372 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
373 if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
374 ALLOCNO_EMIT_DATA (a)->reg = reg;
375 for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
376 ALLOCNO_EMIT_DATA (a)->reg = reg;
377 regno = ALLOCNO_REGNO (allocno);
380 if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
385 a = node->regno_allocno_map[regno];
389 if (ALLOCNO_EMIT_DATA (a)->child_renamed_p)
391 ALLOCNO_EMIT_DATA (a)->child_renamed_p = true;
395 /* Return true if there is an entry to given loop not from its parent
396 (or grandparent) block. For example, it is possible for two
397 adjacent loops inside another loop. */
399 entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
401 ira_loop_tree_node_t bb_node, src_loop_node, parent;
405 for (bb_node = loop_node->children;
407 bb_node = bb_node->next)
408 if (bb_node->bb != NULL)
410 FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
411 if (e->src != ENTRY_BLOCK_PTR
412 && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
414 for (parent = src_loop_node->parent;
416 parent = parent->parent)
417 if (parent == loop_node)
420 /* That is an exit from a nested loop -- skip it. */
422 for (parent = loop_node->parent;
424 parent = parent->parent)
425 if (src_loop_node == parent)
434 /* Set up ENTERED_FROM_NON_PARENT_P for each loop region. */
436 setup_entered_from_non_parent_p (void)
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 beacuse 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)
569 if (node->bb != NULL)
571 FOR_BB_INSNS (node->bb, insn)
572 if (INSN_P (insn) && change_regs (&insn))
574 df_insn_rescan (insn);
575 df_notes_rescan (insn);
580 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
581 fprintf (ira_dump_file,
582 " Changing RTL for loop %d (header bb%d)\n",
583 node->loop->num, node->loop->header->index);
585 parent = ira_curr_loop_tree_node->parent;
586 map = parent->regno_allocno_map;
587 EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
590 allocno = ira_allocnos[i];
591 regno = ALLOCNO_REGNO (allocno);
592 aclass = ALLOCNO_CLASS (allocno);
593 pclass = ira_pressure_class_translate[aclass];
594 parent_allocno = map[regno];
595 ira_assert (regno < ira_reg_equiv_len);
596 /* We generate the same hard register move because the
597 reload pass can put an allocno into memory in this case
598 we will have live range splitting. If it does not happen
599 such the same hard register moves will be removed. The
600 worst case when the both allocnos are put into memory by
601 the reload is very rare. */
602 if (parent_allocno != NULL
603 && (ALLOCNO_HARD_REGNO (allocno)
604 == ALLOCNO_HARD_REGNO (parent_allocno))
605 && (ALLOCNO_HARD_REGNO (allocno) < 0
606 || (parent->reg_pressure[pclass] + 1
607 <= ira_available_class_regs[pclass])
608 || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
609 [ALLOCNO_MODE (allocno)],
610 ALLOCNO_HARD_REGNO (allocno))
611 /* don't create copies because reload can spill an
612 allocno set by copy although the allocno will not
614 || ira_reg_equiv_invariant_p[regno]
615 || ira_reg_equiv_const[regno] != NULL_RTX))
617 original_reg = allocno_emit_reg (allocno);
618 if (parent_allocno == NULL
619 || (REGNO (allocno_emit_reg (parent_allocno))
620 == REGNO (original_reg)))
622 if (internal_flag_ira_verbose > 3 && ira_dump_file)
623 fprintf (ira_dump_file, " %i vs parent %i:",
624 ALLOCNO_HARD_REGNO (allocno),
625 ALLOCNO_HARD_REGNO (parent_allocno));
626 set_allocno_reg (allocno, create_new_reg (original_reg));
630 /* Rename locals: Local allocnos with same regno in different loops
631 might get the different hard register. So we need to change
633 bitmap_and_compl (local_allocno_bitmap,
634 ira_curr_loop_tree_node->all_allocnos,
635 ira_curr_loop_tree_node->border_allocnos);
636 EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
638 allocno = ira_allocnos[i];
639 regno = ALLOCNO_REGNO (allocno);
640 if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
642 used_p = !bitmap_set_bit (used_regno_bitmap, regno);
643 ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
646 bitmap_set_bit (renamed_regno_bitmap, regno);
647 set_allocno_reg (allocno, create_new_reg (allocno_emit_reg (allocno)));
651 /* Process to set up flag somewhere_renamed_p. */
653 set_allocno_somewhere_renamed_p (void)
656 ira_allocno_t allocno;
657 ira_allocno_iterator ai;
659 FOR_EACH_ALLOCNO (allocno, ai)
661 regno = ALLOCNO_REGNO (allocno);
662 if (bitmap_bit_p (renamed_regno_bitmap, regno)
663 && REGNO (allocno_emit_reg (allocno)) == regno)
664 ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
668 /* Return TRUE if move lists on all edges given in vector VEC are
671 eq_edge_move_lists_p (VEC(edge,gc) *vec)
676 list = (move_t) EDGE_I (vec, 0)->aux;
677 for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
678 if (! eq_move_lists_p (list, (move_t) EDGE_I (vec, i)->aux))
683 /* Look at all entry edges (if START_P) or exit edges of basic block
684 BB and put move lists at the BB start or end if it is possible. In
685 other words, this decreases code duplication of allocno moves. */
687 unify_moves (basic_block bb, bool start_p)
694 vec = (start_p ? bb->preds : bb->succs);
695 if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
698 list = (move_t) e->aux;
699 if (! start_p && control_flow_insn_p (BB_END (bb)))
702 for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
705 free_move_list ((move_t) e->aux);
709 at_bb_start[bb->index] = list;
711 at_bb_end[bb->index] = list;
714 /* Last move (in move sequence being processed) setting up the
715 corresponding hard register. */
716 static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER];
718 /* If the element value is equal to CURR_TICK then the corresponding
719 element in `hard_regno_last_set' is defined and correct. */
720 static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
722 /* Last move (in move sequence being processed) setting up the
723 corresponding allocno. */
724 static move_t *allocno_last_set;
726 /* If the element value is equal to CURR_TICK then the corresponding
727 element in . `allocno_last_set' is defined and correct. */
728 static int *allocno_last_set_check;
730 /* Definition of vector of moves. */
732 DEF_VEC_ALLOC_P(move_t, heap);
734 /* This vec contains moves sorted topologically (depth-first) on their
736 static VEC(move_t,heap) *move_vec;
738 /* The variable value is used to check correctness of values of
739 elements of arrays `hard_regno_last_set' and
740 `allocno_last_set_check'. */
741 static int curr_tick;
743 /* This recursive function traverses dependencies of MOVE and produces
744 topological sorting (in depth-first order). */
746 traverse_moves (move_t move)
752 move->visited_p = true;
753 for (i = move->deps_num - 1; i >= 0; i--)
754 traverse_moves (move->deps[i]);
755 VEC_safe_push (move_t, heap, move_vec, move);
758 /* Remove unnecessary moves in the LIST, makes topological sorting,
759 and removes cycles on hard reg dependencies by introducing new
760 allocnos assigned to memory and additional moves. It returns the
763 modify_move_list (move_t list)
765 int i, n, nregs, hard_regno;
766 ira_allocno_t to, from;
767 move_t move, new_move, set_move, first, last;
771 /* Creat move deps. */
773 for (move = list; move != NULL; move = move->next)
776 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
778 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
779 for (i = 0; i < nregs; i++)
781 hard_regno_last_set[hard_regno + i] = move;
782 hard_regno_last_set_check[hard_regno + i] = curr_tick;
785 for (move = list; move != NULL; move = move->next)
789 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
791 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
792 for (n = i = 0; i < nregs; i++)
793 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
794 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
795 != ALLOCNO_REGNO (from)))
797 move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
798 for (n = i = 0; i < nregs; i++)
799 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
800 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
801 != ALLOCNO_REGNO (from)))
802 move->deps[n++] = hard_regno_last_set[hard_regno + i];
806 /* Toplogical sorting: */
807 VEC_truncate (move_t, move_vec, 0);
808 for (move = list; move != NULL; move = move->next)
809 traverse_moves (move);
811 for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
813 move = VEC_index (move_t, move_vec, i);
819 first = VEC_last (move_t, move_vec);
820 /* Removing cycles: */
822 VEC_truncate (move_t, move_vec, 0);
823 for (move = first; move != NULL; move = move->next)
827 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
829 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
830 for (i = 0; i < nregs; i++)
831 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
832 && ALLOCNO_HARD_REGNO
833 (hard_regno_last_set[hard_regno + i]->to) >= 0)
836 ira_allocno_t new_allocno;
838 set_move = hard_regno_last_set[hard_regno + i];
839 /* It does not matter what loop_tree_node (of TO or
840 FROM) to use for the new allocno because of
841 subsequent IRA internal representation
844 = create_new_allocno (ALLOCNO_REGNO (set_move->to),
845 ALLOCNO_LOOP_TREE_NODE (set_move->to));
846 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
847 ira_set_allocno_class (new_allocno,
848 ALLOCNO_CLASS (set_move->to));
849 ira_create_allocno_objects (new_allocno);
850 ALLOCNO_ASSIGNED_P (new_allocno) = true;
851 ALLOCNO_HARD_REGNO (new_allocno) = -1;
852 ALLOCNO_EMIT_DATA (new_allocno)->reg
853 = create_new_reg (allocno_emit_reg (set_move->to));
855 /* Make it possibly conflicting with all earlier
856 created allocnos. Cases where temporary allocnos
857 created to remove the cycles are quite rare. */
858 n = ALLOCNO_NUM_OBJECTS (new_allocno);
859 gcc_assert (n == ALLOCNO_NUM_OBJECTS (set_move->to));
860 for (j = 0; j < n; j++)
862 ira_object_t new_obj = ALLOCNO_OBJECT (new_allocno, j);
864 OBJECT_MIN (new_obj) = 0;
865 OBJECT_MAX (new_obj) = ira_objects_num - 1;
868 new_move = create_move (set_move->to, new_allocno);
869 set_move->to = new_allocno;
870 VEC_safe_push (move_t, heap, move_vec, new_move);
871 ira_move_loops_num++;
872 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
873 fprintf (ira_dump_file,
874 " Creating temporary allocno a%dr%d\n",
875 ALLOCNO_NUM (new_allocno),
876 REGNO (allocno_emit_reg (new_allocno)));
879 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
881 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
882 for (i = 0; i < nregs; i++)
884 hard_regno_last_set[hard_regno + i] = move;
885 hard_regno_last_set_check[hard_regno + i] = curr_tick;
888 for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
890 move = VEC_index (move_t, move_vec, i);
898 /* Generate RTX move insns from the move list LIST. This updates
899 allocation cost using move execution frequency FREQ. */
901 emit_move_list (move_t list, int freq)
905 enum machine_mode mode;
906 enum reg_class aclass;
909 for (; list != NULL; list = list->next)
912 emit_move_insn (allocno_emit_reg (list->to),
913 allocno_emit_reg (list->from));
914 list->insn = get_insns ();
916 /* The reload needs to have set up insn codes. If the reload
917 sets up insn codes by itself, it may fail because insns will
918 have hard registers instead of pseudos and there may be no
919 machine insn with given hard registers. */
920 for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
921 recog_memoized (insn);
922 emit_insn (list->insn);
923 mode = ALLOCNO_MODE (list->to);
924 aclass = ALLOCNO_CLASS (list->to);
926 if (ALLOCNO_HARD_REGNO (list->to) < 0)
928 if (ALLOCNO_HARD_REGNO (list->from) >= 0)
930 cost = ira_memory_move_cost[mode][aclass][0] * freq;
931 ira_store_cost += cost;
934 else if (ALLOCNO_HARD_REGNO (list->from) < 0)
936 if (ALLOCNO_HARD_REGNO (list->to) >= 0)
938 cost = ira_memory_move_cost[mode][aclass][0] * freq;
939 ira_load_cost += cost;
944 ira_init_register_move_cost_if_necessary (mode);
945 cost = ira_register_move_cost[mode][aclass][aclass] * freq;
946 ira_shuffle_cost += cost;
948 ira_overall_cost += cost;
950 result = get_insns ();
955 /* Generate RTX move insns from move lists attached to basic blocks
967 if (at_bb_start[bb->index] != NULL)
969 at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
970 insns = emit_move_list (at_bb_start[bb->index],
971 REG_FREQ_FROM_BB (bb));
974 tmp = NEXT_INSN (tmp);
975 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
976 tmp = NEXT_INSN (tmp);
977 if (tmp == BB_HEAD (bb))
978 emit_insn_before (insns, tmp);
979 else if (tmp != NULL_RTX)
980 emit_insn_after (insns, PREV_INSN (tmp));
982 emit_insn_after (insns, get_last_insn ());
985 if (at_bb_end[bb->index] != NULL)
987 at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
988 insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
989 ira_assert (! control_flow_insn_p (BB_END (bb)));
990 emit_insn_after (insns, BB_END (bb));
993 FOR_EACH_EDGE (e, ei, bb->succs)
997 ira_assert ((e->flags & EDGE_ABNORMAL) == 0
998 || ! EDGE_CRITICAL_P (e));
999 e->aux = modify_move_list ((move_t) e->aux);
1001 (emit_move_list ((move_t) e->aux,
1002 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
1004 if (e->src->next_bb != e->dest)
1005 ira_additional_jumps_num++;
1010 /* Update costs of A and corresponding allocnos on upper levels on the
1011 loop tree from reading (if READ_P) or writing A on an execution
1014 update_costs (ira_allocno_t a, bool read_p, int freq)
1016 ira_loop_tree_node_t parent;
1020 ALLOCNO_NREFS (a)++;
1021 ALLOCNO_FREQ (a) += freq;
1022 ALLOCNO_MEMORY_COST (a)
1023 += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)]
1024 [read_p ? 1 : 0] * freq);
1025 if (ALLOCNO_CAP (a) != NULL)
1026 a = ALLOCNO_CAP (a);
1027 else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
1028 || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
1033 /* Process moves from LIST with execution FREQ to add ranges, copies,
1034 and modify costs for allocnos involved in the moves. All regnos
1035 living through the list is in LIVE_THROUGH, and the loop tree node
1036 used to find corresponding allocnos is NODE. */
1038 add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
1039 bitmap live_through, int freq)
1048 HARD_REG_SET hard_regs_live;
1053 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1055 REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
1056 /* This is a trick to guarantee that new ranges is not merged with
1059 start = ira_max_point;
1060 for (move = list; move != NULL; move = move->next)
1062 ira_allocno_t from = move->from;
1063 ira_allocno_t to = move->to;
1066 bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
1067 bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
1069 nr = ALLOCNO_NUM_OBJECTS (to);
1070 for (i = 0; i < nr; i++)
1072 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1073 if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
1075 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1076 fprintf (ira_dump_file, " Allocate conflicts for a%dr%d\n",
1077 ALLOCNO_NUM (to), REGNO (allocno_emit_reg (to)));
1078 ira_allocate_object_conflicts (to_obj, n);
1081 ior_hard_reg_conflicts (from, &hard_regs_live);
1082 ior_hard_reg_conflicts (to, &hard_regs_live);
1084 update_costs (from, true, freq);
1085 update_costs (to, false, freq);
1086 cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
1087 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1088 fprintf (ira_dump_file, " Adding cp%d:a%dr%d-a%dr%d\n",
1089 cp->num, ALLOCNO_NUM (cp->first),
1090 REGNO (allocno_emit_reg (cp->first)),
1091 ALLOCNO_NUM (cp->second),
1092 REGNO (allocno_emit_reg (cp->second)));
1094 nr = ALLOCNO_NUM_OBJECTS (from);
1095 for (i = 0; i < nr; i++)
1097 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
1098 r = OBJECT_LIVE_RANGES (from_obj);
1099 if (r == NULL || r->finish >= 0)
1101 ira_add_live_range_to_object (from_obj, start, ira_max_point);
1102 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1103 fprintf (ira_dump_file,
1104 " Adding range [%d..%d] to allocno a%dr%d\n",
1105 start, ira_max_point, ALLOCNO_NUM (from),
1106 REGNO (allocno_emit_reg (from)));
1110 r->finish = ira_max_point;
1111 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1112 fprintf (ira_dump_file,
1113 " Adding range [%d..%d] to allocno a%dr%d\n",
1114 r->start, ira_max_point, ALLOCNO_NUM (from),
1115 REGNO (allocno_emit_reg (from)));
1119 nr = ALLOCNO_NUM_OBJECTS (to);
1120 for (i = 0; i < nr; i++)
1122 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1123 ira_add_live_range_to_object (to_obj, ira_max_point, -1);
1127 for (move = list; move != NULL; move = move->next)
1130 nr = ALLOCNO_NUM_OBJECTS (move->to);
1131 for (i = 0; i < nr; i++)
1133 ira_object_t to_obj = ALLOCNO_OBJECT (move->to, i);
1134 r = OBJECT_LIVE_RANGES (to_obj);
1137 r->finish = ira_max_point - 1;
1138 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1139 fprintf (ira_dump_file,
1140 " Adding range [%d..%d] to allocno a%dr%d\n",
1141 r->start, r->finish, ALLOCNO_NUM (move->to),
1142 REGNO (allocno_emit_reg (move->to)));
1146 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1151 a = node->regno_allocno_map[regno];
1152 if ((to = ALLOCNO_EMIT_DATA (a)->mem_optimized_dest) != NULL)
1154 nr = ALLOCNO_NUM_OBJECTS (a);
1155 for (i = 0; i < nr; i++)
1157 ira_object_t obj = ALLOCNO_OBJECT (a, i);
1158 ira_add_live_range_to_object (obj, start, ira_max_point - 1);
1160 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1163 " Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1164 start, ira_max_point - 1,
1165 to != NULL ? "upper level" : "",
1166 ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
1170 /* Process all move list to add ranges, conflicts, copies, and modify
1171 costs for allocnos involved in the moves. */
1173 add_ranges_and_copies (void)
1178 ira_loop_tree_node_t node;
1179 bitmap live_through;
1181 live_through = ira_allocate_bitmap ();
1184 /* It does not matter what loop_tree_node (of source or
1185 destination block) to use for searching allocnos by their
1186 regnos because of subsequent IR flattening. */
1187 node = IRA_BB_NODE (bb)->parent;
1188 bitmap_copy (live_through, DF_LR_IN (bb));
1189 add_range_and_copies_from_move_list
1190 (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1191 bitmap_copy (live_through, DF_LR_OUT (bb));
1192 add_range_and_copies_from_move_list
1193 (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1194 FOR_EACH_EDGE (e, ei, bb->succs)
1196 bitmap_and (live_through, DF_LR_IN (e->dest), DF_LR_OUT (bb));
1197 add_range_and_copies_from_move_list
1198 ((move_t) e->aux, node, live_through,
1199 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1202 ira_free_bitmap (live_through);
1205 /* The entry function changes code and generates shuffling allocnos on
1206 region borders for the regional (LOOPS_P is TRUE in this case)
1207 register allocation. */
1209 ira_emit (bool loops_p)
1216 ira_allocno_iterator ai;
1218 FOR_EACH_ALLOCNO (a, ai)
1219 ALLOCNO_EMIT_DATA (a)->reg = regno_reg_rtx[ALLOCNO_REGNO (a)];
1222 at_bb_start = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1223 memset (at_bb_start, 0, sizeof (move_t) * last_basic_block);
1224 at_bb_end = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1225 memset (at_bb_end, 0, sizeof (move_t) * last_basic_block);
1226 local_allocno_bitmap = ira_allocate_bitmap ();
1227 used_regno_bitmap = ira_allocate_bitmap ();
1228 renamed_regno_bitmap = ira_allocate_bitmap ();
1229 max_regno_before_changing = max_reg_num ();
1230 ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1231 set_allocno_somewhere_renamed_p ();
1232 ira_free_bitmap (used_regno_bitmap);
1233 ira_free_bitmap (renamed_regno_bitmap);
1234 ira_free_bitmap (local_allocno_bitmap);
1235 setup_entered_from_non_parent_p ();
1238 at_bb_start[bb->index] = NULL;
1239 at_bb_end[bb->index] = NULL;
1240 FOR_EACH_EDGE (e, ei, bb->succs)
1241 if (e->dest != EXIT_BLOCK_PTR)
1242 generate_edge_moves (e);
1245 = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
1246 allocno_last_set_check
1247 = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1248 memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
1249 memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1252 unify_moves (bb, true);
1254 unify_moves (bb, false);
1255 move_vec = VEC_alloc (move_t, heap, ira_allocnos_num);
1257 add_ranges_and_copies ();
1261 free_move_list (at_bb_start[bb->index]);
1262 free_move_list (at_bb_end[bb->index]);
1263 FOR_EACH_EDGE (e, ei, bb->succs)
1265 free_move_list ((move_t) e->aux);
1269 VEC_free (move_t, heap, move_vec);
1270 ira_free (allocno_last_set_check);
1271 ira_free (allocno_last_set);
1272 commit_edge_insertions ();
1273 /* Fix insn codes. It is necessary to do it before reload because
1274 reload assumes initial insn codes defined. The insn codes can be
1275 invalidated by CFG infrastructure for example in jump
1278 FOR_BB_INSNS_REVERSE (bb, insn)
1280 recog_memoized (insn);
1281 ira_free (at_bb_end);
1282 ira_free (at_bb_start);