1 /* Integrated Register Allocator. Changing code and generating moves.
2 Copyright (C) 2006, 2007, 2008
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 /* This recursive function changes pseudo-registers in *LOC if it is
133 necessary. The function returns TRUE if a change was done. */
135 change_regs (rtx *loc)
137 int i, regno, result = false;
142 if (*loc == NULL_RTX)
144 code = GET_CODE (*loc);
147 regno = REGNO (*loc);
148 if (regno < FIRST_PSEUDO_REGISTER)
150 if (regno >= max_regno_before_changing)
151 /* It is a shared register which was changed already. */
153 if (ira_curr_regno_allocno_map[regno] == NULL)
155 reg = ALLOCNO_REG (ira_curr_regno_allocno_map[regno]);
162 fmt = GET_RTX_FORMAT (code);
163 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
166 result = change_regs (&XEXP (*loc, i)) || result;
167 else if (fmt[i] == 'E')
171 for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
172 result = change_regs (&XVECEXP (*loc, i, j)) || result;
178 /* Attach MOVE to the edge E. The move is attached to the head of the
179 list if HEAD_P is TRUE. */
181 add_to_edge_list (edge e, move_t move, bool head_p)
185 if (head_p || e->aux == NULL)
187 move->next = (move_t) e->aux;
192 for (last = (move_t) e->aux; last->next != NULL; last = last->next)
199 /* Create and return new pseudo-register with the same attributes as
202 create_new_reg (rtx original_reg)
206 new_reg = gen_reg_rtx (GET_MODE (original_reg));
207 ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
208 REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
209 REG_POINTER (new_reg) = REG_POINTER (original_reg);
210 REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
211 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
212 fprintf (ira_dump_file, " Creating newreg=%i from oldreg=%i\n",
213 REGNO (new_reg), REGNO (original_reg));
217 /* Return TRUE if loop given by SUBNODE inside the loop given by
220 subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
222 for (; subnode != NULL; subnode = subnode->parent)
228 /* Set up member `reg' to REG for allocnos which has the same regno as
229 ALLOCNO and which are inside the loop corresponding to ALLOCNO. */
231 set_allocno_reg (ira_allocno_t allocno, rtx reg)
235 ira_loop_tree_node_t node;
237 node = ALLOCNO_LOOP_TREE_NODE (allocno);
238 for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
240 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
241 if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
242 ALLOCNO_REG (a) = reg;
243 for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
244 ALLOCNO_REG (a) = reg;
245 regno = ALLOCNO_REGNO (allocno);
248 if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
253 a = node->regno_allocno_map[regno];
257 if (ALLOCNO_CHILD_RENAMED_P (a))
259 ALLOCNO_CHILD_RENAMED_P (a) = true;
263 /* Return TRUE if move of SRC_ALLOCNO to DEST_ALLOCNO does not change
264 value of the destination. One possible reason for this is the
265 situation when SRC_ALLOCNO is not modified in the corresponding
268 not_modified_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
270 int regno, orig_regno;
272 ira_loop_tree_node_t node;
274 ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
275 && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
276 orig_regno = ALLOCNO_REGNO (src_allocno);
277 regno = REGNO (ALLOCNO_REG (dest_allocno));
278 for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
281 if ((a = node->regno_allocno_map[orig_regno]) == NULL)
283 else if (REGNO (ALLOCNO_REG (a)) == (unsigned) regno)
285 else if (bitmap_bit_p (node->modified_regnos, orig_regno))
290 /* Generate and attach moves to the edge E. This looks at the final
291 regnos of allocnos living on the edge with the same original regno
292 to figure out when moves should be generated. */
294 generate_edge_moves (edge e)
296 ira_loop_tree_node_t src_loop_node, dest_loop_node;
299 ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
302 src_loop_node = IRA_BB_NODE (e->src)->parent;
303 dest_loop_node = IRA_BB_NODE (e->dest)->parent;
305 if (src_loop_node == dest_loop_node)
307 src_map = src_loop_node->regno_allocno_map;
308 dest_map = dest_loop_node->regno_allocno_map;
309 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (e->dest),
310 FIRST_PSEUDO_REGISTER, regno, bi)
311 if (bitmap_bit_p (DF_LR_OUT (e->src), regno))
313 src_allocno = src_map[regno];
314 dest_allocno = dest_map[regno];
315 if (REGNO (ALLOCNO_REG (src_allocno))
316 == REGNO (ALLOCNO_REG (dest_allocno)))
318 /* Remove unnecessary stores at the region exit. We should do
319 this for readonly memory for sure and this is guaranteed by
320 that we never generate moves on region borders (see
321 checking ira_reg_equiv_invariant_p in function
323 if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
324 && ALLOCNO_HARD_REGNO (src_allocno) >= 0
325 && not_modified_p (src_allocno, dest_allocno))
327 ALLOCNO_MEM_OPTIMIZED_DEST (src_allocno) = dest_allocno;
328 ALLOCNO_MEM_OPTIMIZED_DEST_P (dest_allocno) = true;
329 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
330 fprintf (ira_dump_file, " Remove r%d:a%d->a%d(mem)\n",
331 regno, ALLOCNO_NUM (src_allocno),
332 ALLOCNO_NUM (dest_allocno));
335 move = create_move (dest_allocno, src_allocno);
336 add_to_edge_list (e, move, true);
340 /* Bitmap of allocnos local for the current loop. */
341 static bitmap local_allocno_bitmap;
343 /* This bitmap is used to find that we need to generate and to use a
344 new pseudo-register when processing allocnos with the same original
346 static bitmap used_regno_bitmap;
348 /* This bitmap contains regnos of allocnos which were renamed locally
349 because the allocnos correspond to disjoint live ranges in loops
350 with a common parent. */
351 static bitmap renamed_regno_bitmap;
353 /* Change (if necessary) pseudo-registers inside loop given by loop
356 change_loop (ira_loop_tree_node_t node)
362 ira_allocno_t allocno, parent_allocno, *map;
363 rtx insn, original_reg;
364 enum reg_class cover_class;
365 ira_loop_tree_node_t parent;
367 if (node != ira_loop_tree_root)
370 if (node->bb != NULL)
372 FOR_BB_INSNS (node->bb, insn)
373 if (INSN_P (insn) && change_regs (&insn))
375 df_insn_rescan (insn);
376 df_notes_rescan (insn);
381 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
382 fprintf (ira_dump_file,
383 " Changing RTL for loop %d (header bb%d)\n",
384 node->loop->num, node->loop->header->index);
386 parent = ira_curr_loop_tree_node->parent;
387 map = parent->regno_allocno_map;
388 EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
391 allocno = ira_allocnos[i];
392 regno = ALLOCNO_REGNO (allocno);
393 cover_class = ALLOCNO_COVER_CLASS (allocno);
394 parent_allocno = map[regno];
395 ira_assert (regno < ira_reg_equiv_len);
396 /* We generate the same hard register move because the
397 reload pass can put an allocno into memory in this case
398 we will have live range splitting. If it does not happen
399 such the same hard register moves will be removed. The
400 worst case when the both allocnos are put into memory by
401 the reload is very rare. */
402 if (parent_allocno != NULL
403 && (ALLOCNO_HARD_REGNO (allocno)
404 == ALLOCNO_HARD_REGNO (parent_allocno))
405 && (ALLOCNO_HARD_REGNO (allocno) < 0
406 || (parent->reg_pressure[cover_class] + 1
407 <= ira_available_class_regs[cover_class])
408 || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
409 [ALLOCNO_MODE (allocno)],
410 ALLOCNO_HARD_REGNO (allocno))
411 /* don't create copies because reload can spill an
412 allocno set by copy although the allocno will not
414 || ira_reg_equiv_invariant_p[regno]
415 || ira_reg_equiv_const[regno] != NULL_RTX))
417 original_reg = ALLOCNO_REG (allocno);
418 if (parent_allocno == NULL
419 || REGNO (ALLOCNO_REG (parent_allocno)) == REGNO (original_reg))
421 if (internal_flag_ira_verbose > 3 && ira_dump_file)
422 fprintf (ira_dump_file, " %i vs parent %i:",
423 ALLOCNO_HARD_REGNO (allocno),
424 ALLOCNO_HARD_REGNO (parent_allocno));
425 set_allocno_reg (allocno, create_new_reg (original_reg));
429 /* Rename locals: Local allocnos with same regno in different loops
430 might get the different hard register. So we need to change
432 bitmap_and_compl (local_allocno_bitmap,
433 ira_curr_loop_tree_node->all_allocnos,
434 ira_curr_loop_tree_node->border_allocnos);
435 EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
437 allocno = ira_allocnos[i];
438 regno = ALLOCNO_REGNO (allocno);
439 if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
441 used_p = bitmap_bit_p (used_regno_bitmap, regno);
442 bitmap_set_bit (used_regno_bitmap, regno);
443 ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
446 bitmap_set_bit (renamed_regno_bitmap, regno);
447 set_allocno_reg (allocno, create_new_reg (ALLOCNO_REG (allocno)));
451 /* Process to set up flag somewhere_renamed_p. */
453 set_allocno_somewhere_renamed_p (void)
456 ira_allocno_t allocno;
457 ira_allocno_iterator ai;
459 FOR_EACH_ALLOCNO (allocno, ai)
461 regno = ALLOCNO_REGNO (allocno);
462 if (bitmap_bit_p (renamed_regno_bitmap, regno)
463 && REGNO (ALLOCNO_REG (allocno)) == regno)
464 ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
468 /* Return TRUE if move lists on all edges given in vector VEC are
471 eq_edge_move_lists_p (VEC(edge,gc) *vec)
476 list = (move_t) EDGE_I (vec, 0)->aux;
477 for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
478 if (! eq_move_lists_p (list, (move_t) EDGE_I (vec, i)->aux))
483 /* Look at all entry edges (if START_P) or exit edges of basic block
484 BB and put move lists at the BB start or end if it is possible. In
485 other words, this decreases code duplication of allocno moves. */
487 unify_moves (basic_block bb, bool start_p)
494 vec = (start_p ? bb->preds : bb->succs);
495 if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
498 list = (move_t) e->aux;
499 if (! start_p && control_flow_insn_p (BB_END (bb)))
502 for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
505 free_move_list ((move_t) e->aux);
509 at_bb_start[bb->index] = list;
511 at_bb_end[bb->index] = list;
514 /* Last move (in move sequence being processed) setting up the
515 corresponding hard register. */
516 static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER];
518 /* If the element value is equal to CURR_TICK then the corresponding
519 element in `hard_regno_last_set' is defined and correct. */
520 static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
522 /* Last move (in move sequence being processed) setting up the
523 corresponding allocno. */
524 static move_t *allocno_last_set;
526 /* If the element value is equal to CURR_TICK then the corresponding
527 element in . `allocno_last_set' is defined and correct. */
528 static int *allocno_last_set_check;
530 /* Definition of vector of moves. */
532 DEF_VEC_ALLOC_P(move_t, heap);
534 /* This vec contains moves sorted topologically (depth-first) on their
536 static VEC(move_t,heap) *move_vec;
538 /* The variable value is used to check correctness of values of
539 elements of arrays `hard_regno_last_set' and
540 `allocno_last_set_check'. */
541 static int curr_tick;
543 /* This recursive function traverses dependencies of MOVE and produces
544 topological sorting (in depth-first order). */
546 traverse_moves (move_t move)
552 move->visited_p = true;
553 for (i = move->deps_num - 1; i >= 0; i--)
554 traverse_moves (move->deps[i]);
555 VEC_safe_push (move_t, heap, move_vec, move);
558 /* Remove unnecessary moves in the LIST, makes topological sorting,
559 and removes cycles on hard reg dependencies by introducing new
560 allocnos assigned to memory and additional moves. It returns the
563 modify_move_list (move_t list)
565 int i, n, nregs, hard_regno;
566 ira_allocno_t to, from, new_allocno;
567 move_t move, new_move, set_move, first, last;
571 /* Creat move deps. */
573 for (move = list; move != NULL; move = move->next)
576 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
578 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
579 for (i = 0; i < nregs; i++)
581 hard_regno_last_set[hard_regno + i] = move;
582 hard_regno_last_set_check[hard_regno + i] = curr_tick;
585 for (move = list; move != NULL; move = move->next)
589 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
591 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
592 for (n = i = 0; i < nregs; i++)
593 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
594 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
595 != ALLOCNO_REGNO (from)))
597 move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
598 for (n = i = 0; i < nregs; i++)
599 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
600 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
601 != ALLOCNO_REGNO (from)))
602 move->deps[n++] = hard_regno_last_set[hard_regno + i];
606 /* Toplogical sorting: */
607 VEC_truncate (move_t, move_vec, 0);
608 for (move = list; move != NULL; move = move->next)
609 traverse_moves (move);
611 for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
613 move = VEC_index (move_t, move_vec, i);
619 first = VEC_last (move_t, move_vec);
620 /* Removing cycles: */
622 VEC_truncate (move_t, move_vec, 0);
623 for (move = first; move != NULL; move = move->next)
627 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
629 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
630 for (i = 0; i < nregs; i++)
631 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
632 && ALLOCNO_HARD_REGNO
633 (hard_regno_last_set[hard_regno + i]->to) >= 0)
635 set_move = hard_regno_last_set[hard_regno + i];
636 /* It does not matter what loop_tree_node (of TO or
637 FROM) to use for the new allocno because of
638 subsequent IRA internal representation
641 = ira_create_allocno (ALLOCNO_REGNO (set_move->to), false,
642 ALLOCNO_LOOP_TREE_NODE (set_move->to));
643 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
644 ira_set_allocno_cover_class
645 (new_allocno, ALLOCNO_COVER_CLASS (set_move->to));
646 ALLOCNO_ASSIGNED_P (new_allocno) = true;
647 ALLOCNO_HARD_REGNO (new_allocno) = -1;
648 ALLOCNO_REG (new_allocno)
649 = create_new_reg (ALLOCNO_REG (set_move->to));
650 ALLOCNO_CONFLICT_ID (new_allocno) = ALLOCNO_NUM (new_allocno);
651 /* Make it possibly conflicting with all earlier
652 created allocnos. Cases where temporary allocnos
653 created to remove the cycles are quite rare. */
654 ALLOCNO_MIN (new_allocno) = 0;
655 ALLOCNO_MAX (new_allocno) = ira_allocnos_num - 1;
656 new_move = create_move (set_move->to, new_allocno);
657 set_move->to = new_allocno;
658 VEC_safe_push (move_t, heap, move_vec, new_move);
659 ira_move_loops_num++;
660 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
661 fprintf (ira_dump_file,
662 " Creating temporary allocno a%dr%d\n",
663 ALLOCNO_NUM (new_allocno),
664 REGNO (ALLOCNO_REG (new_allocno)));
667 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
669 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
670 for (i = 0; i < nregs; i++)
672 hard_regno_last_set[hard_regno + i] = move;
673 hard_regno_last_set_check[hard_regno + i] = curr_tick;
676 for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
678 move = VEC_index (move_t, move_vec, i);
686 /* Generate RTX move insns from the move list LIST. This updates
687 allocation cost using move execution frequency FREQ. */
689 emit_move_list (move_t list, int freq)
693 enum machine_mode mode;
694 enum reg_class cover_class;
697 for (; list != NULL; list = list->next)
700 emit_move_insn (ALLOCNO_REG (list->to), ALLOCNO_REG (list->from));
701 list->insn = get_insns ();
703 /* The reload needs to have set up insn codes. If the reload
704 sets up insn codes by itself, it may fail because insns will
705 have hard registers instead of pseudos and there may be no
706 machine insn with given hard registers. */
707 for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
708 recog_memoized (insn);
709 emit_insn (list->insn);
710 mode = ALLOCNO_MODE (list->to);
711 cover_class = ALLOCNO_COVER_CLASS (list->to);
713 if (ALLOCNO_HARD_REGNO (list->to) < 0)
715 if (ALLOCNO_HARD_REGNO (list->from) >= 0)
717 cost = ira_memory_move_cost[mode][cover_class][0] * freq;
718 ira_store_cost += cost;
721 else if (ALLOCNO_HARD_REGNO (list->from) < 0)
723 if (ALLOCNO_HARD_REGNO (list->to) >= 0)
725 cost = ira_memory_move_cost[mode][cover_class][0] * freq;
726 ira_load_cost += cost;
731 cost = ira_register_move_cost[mode][cover_class][cover_class] * freq;
732 ira_shuffle_cost += cost;
734 ira_overall_cost += cost;
736 result = get_insns ();
741 /* Generate RTX move insns from move lists attached to basic blocks
753 if (at_bb_start[bb->index] != NULL)
755 at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
756 insns = emit_move_list (at_bb_start[bb->index],
757 REG_FREQ_FROM_BB (bb));
760 tmp = NEXT_INSN (tmp);
761 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
762 tmp = NEXT_INSN (tmp);
763 if (tmp == BB_HEAD (bb))
764 emit_insn_before (insns, tmp);
765 else if (tmp != NULL_RTX)
766 emit_insn_after (insns, PREV_INSN (tmp));
768 emit_insn_after (insns, get_last_insn ());
771 if (at_bb_end[bb->index] != NULL)
773 at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
774 insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
775 ira_assert (! control_flow_insn_p (BB_END (bb)));
776 emit_insn_after (insns, BB_END (bb));
779 FOR_EACH_EDGE (e, ei, bb->succs)
783 ira_assert ((e->flags & EDGE_ABNORMAL) == 0
784 || ! EDGE_CRITICAL_P (e));
785 e->aux = modify_move_list ((move_t) e->aux);
787 (emit_move_list ((move_t) e->aux,
788 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
790 if (e->src->next_bb != e->dest)
791 ira_additional_jumps_num++;
796 /* Update costs of A and corresponding allocnos on upper levels on the
797 loop tree from reading (if READ_P) or writing A on an execution
800 update_costs (ira_allocno_t a, bool read_p, int freq)
802 ira_loop_tree_node_t parent;
807 ALLOCNO_FREQ (a) += freq;
808 ALLOCNO_MEMORY_COST (a)
809 += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)]
810 [read_p ? 1 : 0] * freq);
811 if (ALLOCNO_CAP (a) != NULL)
813 else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
814 || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
819 /* Process moves from LIST with execution FREQ to add ranges, copies,
820 and modify costs for allocnos involved in the moves. All regnos
821 living through the list is in LIVE_THROUGH, and the loop tree node
822 used to find corresponding allocnos is NODE. */
824 add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
825 bitmap live_through, int freq)
830 ira_allocno_t to, from, a;
832 allocno_live_range_t r;
834 HARD_REG_SET hard_regs_live;
839 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
841 REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
842 /* This is a trick to guarantee that new ranges is not merged with
845 start = ira_max_point;
846 for (move = list; move != NULL; move = move->next)
850 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (to) == NULL)
852 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
853 fprintf (ira_dump_file, " Allocate conflicts for a%dr%d\n",
854 ALLOCNO_NUM (to), REGNO (ALLOCNO_REG (to)));
855 ira_allocate_allocno_conflicts (to, n);
857 bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
858 bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
859 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (from), hard_regs_live);
860 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (to), hard_regs_live);
861 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from),
863 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (to), hard_regs_live);
864 update_costs (from, true, freq);
865 update_costs (to, false, freq);
866 cp = ira_add_allocno_copy (from, to, freq, move->insn, NULL);
867 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
868 fprintf (ira_dump_file, " Adding cp%d:a%dr%d-a%dr%d\n",
869 cp->num, ALLOCNO_NUM (cp->first),
870 REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
871 REGNO (ALLOCNO_REG (cp->second)));
872 r = ALLOCNO_LIVE_RANGES (from);
873 if (r == NULL || r->finish >= 0)
875 ALLOCNO_LIVE_RANGES (from)
876 = ira_create_allocno_live_range (from, start, ira_max_point, r);
877 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
878 fprintf (ira_dump_file,
879 " Adding range [%d..%d] to allocno a%dr%d\n",
880 start, ira_max_point, ALLOCNO_NUM (from),
881 REGNO (ALLOCNO_REG (from)));
884 r->finish = ira_max_point;
886 ALLOCNO_LIVE_RANGES (to)
887 = ira_create_allocno_live_range (to, ira_max_point, -1,
888 ALLOCNO_LIVE_RANGES (to));
891 for (move = list; move != NULL; move = move->next)
893 r = ALLOCNO_LIVE_RANGES (move->to);
896 r->finish = ira_max_point - 1;
897 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
898 fprintf (ira_dump_file,
899 " Adding range [%d..%d] to allocno a%dr%d\n",
900 r->start, r->finish, ALLOCNO_NUM (move->to),
901 REGNO (ALLOCNO_REG (move->to)));
904 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
906 a = node->regno_allocno_map[regno];
907 if (ALLOCNO_MEM_OPTIMIZED_DEST (a) == NULL)
909 ALLOCNO_LIVE_RANGES (a)
910 = ira_create_allocno_live_range (a, start, ira_max_point - 1,
911 ALLOCNO_LIVE_RANGES (a));
912 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
915 " Adding range [%d..%d] to live through allocno a%dr%d\n",
916 start, ira_max_point - 1, ALLOCNO_NUM (a),
917 REGNO (ALLOCNO_REG (a)));
922 /* Process all move list to add ranges, conflicts, copies, and modify
923 costs for allocnos involved in the moves. */
925 add_ranges_and_copies (void)
930 ira_loop_tree_node_t node;
933 live_through = ira_allocate_bitmap ();
936 /* It does not matter what loop_tree_node (of source or
937 destination block) to use for searching allocnos by their
938 regnos because of subsequent IR flattening. */
939 node = IRA_BB_NODE (bb)->parent;
940 bitmap_copy (live_through, DF_LR_IN (bb));
941 add_range_and_copies_from_move_list
942 (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
943 bitmap_copy (live_through, DF_LR_OUT (bb));
944 add_range_and_copies_from_move_list
945 (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
946 FOR_EACH_EDGE (e, ei, bb->succs)
948 bitmap_and (live_through, DF_LR_IN (e->dest), DF_LR_OUT (bb));
949 add_range_and_copies_from_move_list
950 ((move_t) e->aux, node, live_through,
951 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
954 ira_free_bitmap (live_through);
957 /* The entry function changes code and generates shuffling allocnos on
958 region borders for the regional (LOOPS_P is TRUE in this case)
959 register allocation. */
961 ira_emit (bool loops_p)
967 ira_allocno_iterator ai;
969 FOR_EACH_ALLOCNO (a, ai)
970 ALLOCNO_REG (a) = regno_reg_rtx[ALLOCNO_REGNO (a)];
973 at_bb_start = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
974 memset (at_bb_start, 0, sizeof (move_t) * last_basic_block);
975 at_bb_end = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
976 memset (at_bb_end, 0, sizeof (move_t) * last_basic_block);
977 local_allocno_bitmap = ira_allocate_bitmap ();
978 used_regno_bitmap = ira_allocate_bitmap ();
979 renamed_regno_bitmap = ira_allocate_bitmap ();
980 max_regno_before_changing = max_reg_num ();
981 ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
982 set_allocno_somewhere_renamed_p ();
983 ira_free_bitmap (used_regno_bitmap);
984 ira_free_bitmap (renamed_regno_bitmap);
985 ira_free_bitmap (local_allocno_bitmap);
988 at_bb_start[bb->index] = NULL;
989 at_bb_end[bb->index] = NULL;
990 FOR_EACH_EDGE (e, ei, bb->succs)
991 if (e->dest != EXIT_BLOCK_PTR)
992 generate_edge_moves (e);
995 = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
996 allocno_last_set_check
997 = (int *) ira_allocate (sizeof (int) * max_reg_num ());
998 memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
999 memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1002 unify_moves (bb, true);
1004 unify_moves (bb, false);
1005 move_vec = VEC_alloc (move_t, heap, ira_allocnos_num);
1007 add_ranges_and_copies ();
1011 free_move_list (at_bb_start[bb->index]);
1012 free_move_list (at_bb_end[bb->index]);
1013 FOR_EACH_EDGE (e, ei, bb->succs)
1015 free_move_list ((move_t) e->aux);
1019 VEC_free (move_t, heap, move_vec);
1020 ira_free (allocno_last_set_check);
1021 ira_free (allocno_last_set);
1022 commit_edge_insertions ();
1023 ira_free (at_bb_end);
1024 ira_free (at_bb_start);